Planet Lisp

LispjobsSenior Software Engineer: D-Wave, Burnaby, British Columbia, Canada

· 31 hours ago

D-Wave is looking for exceptionally motivated people who love to see the impact of their work on a daily basis, who will do whatever it takes to ensure success of the company, and who want to be a part of something special.

D-Wave is working to radically change what it is possible to do with computers. Our mission is to integrate new discoveries in physics and computer science into new breakthrough approaches to computation. We are committed to commercializing quantum computers. The company’s flagship product, the D-Wave Two, is built around a novel type of superconducting quantum processor. D-Wave Two systems are currently in use by on-line customers and by customers in the field such as NASA & Google

Position:

D-Wave is seeking an experienced Software Developer to join the Processor Development group. The successful candidate will work closely with physicists to develop and optimize measurement routines used to calibrate D-Wave’s quantum processor. You will be self-driven, but comfortable working closely with others. You will share responsibility for designing, implementing, testing and maintaining the suite of software necessary to support the testing and operation of D-Wave's quantum computing hardware. The software is implemented in Common Lisp (SBCL) and is an integral part of the quantum computing system. It is used for a variety of purposes including calibration, operation, testing and benchmarking.

Responsibilities:

  • Work closely with physicists and other software engineers to develop any and all aspects of quantum processor calibration, operation infrastructure, performance optimization and profiling
  • Analyze and optimize existing software and newly developed routines for performance and reliability. Develop and support software related to architecture, usage of libraries and functions, the best ways of solving a problem or implementing a new feature, and layer efficiency and performance optimization
  • Software development, support, and troubleshooting systems hardware including fridge control and processor electronics
  • Full life-cycle support of software products from development, test and validation, production deployment, through to decommissioning
  • Configuring and upgrading quantum processor control servers and software development servers

Qualifications:

  • Masters Degree in Computer Science with 4+ years relevant experience, or Bachelor’s degree and 8+ years experience.
  • Experience developing and optimizing software in compiled languages; ability to consider both algorithm choice and how your code is compiled when tuning performance.
  • At least 4 years of professional software development experience including software design, code and test, and maintenance
  • Familiarity with Common Lisp is a definite asset
  • Comfortable working alongside one or two other scientists or software engineers, such as in a pair programming

    We thank all applicants for their interest, however, only those who are selected for interviews will be contacted. It is D-Wave Systems Inc policy to provide equal employment opportunity (EEO) to all persons regardless of race, color, religion, sex, national origin, age, sexual orientation, genetic information, physical or mental disability, protected veteran status, or any other characteristic protected by federal, state/provincial, local law.

Contact:

Lindsay Andrea <landrea@dwavesys.com>

Talent Acquisition Specialist, Human Resources

D-Wave Systems Inc.

http://www.dwavesys.com

604.630.1428  Ext. 119


Paul KhuongPerformance Tuning ~ Writing an Essay

· 4 days ago

Skip to the meaty bits.

My work at AppNexus mostly involves performance optimisation, at any level from microarchitecture-driven improvements to data layout and assembly code to improving the responsiveness of our distributed system under load. Technically, this is similar to what I was doing as a lone developer on research-grade programs. However, the scale of our (constantly changing) code base and collaboration with a dozen other coders mean that I approach the task differently: e.g., rather than single-mindedly improving throughput now, I aim to pick an evolution path that improves throughput today without imposing too much of a burden on future development or fossilising ourselves in a design dead-end. So, although numbers still don’t lie (hah), my current approach also calls for something like judgment and taste, as well as a fair bit of empathy for others. Rare are the obviously correct choices, and, in that regard, determining what changes to make and which to discard as over-the-top ricing feels like I’m drafting a literary essay.

This view is probably tainted by the fact that, between English and French classes, I spent something like half of my time in High School critiquing essays, writing essays, or preparing to write one. Initially, there was a striking difference between the two languages: English teachers had us begin with the five paragraph format where one presents multiple arguments for the same thesis, while French teachers imposed a thesis/antithesis/synthesis triad (and never really let it go until CÉGEP, but that’s another topic). When I write that performance optimisation feels like drafting essays, I’m referring to the latter “Hegelian” process, where one exposes arguments and counterarguments alike in order to finally make a stronger case.

I’ll stretch the analogy further. Reading between the lines gives us access to more arguments, but it’s also easy to get the context wrong and come up with hilariously far-fetched interpretations. When I try to understand a system’s performance, the most robust metrics treat the system as a black box: it’s hard to get throughput under production data wrong. However, I need finer grained information (e.g., performance counters, instruction-level profiling, or application-specific metrics) to guide my work, and, the more useful that information can be – like domain specific metrics that highlight what we could do differently rather than how to do the same thing more efficiently – the easier it is to measure incorrectly. That’s not a cause for despair, but rather a fruitful line of skepticism that helps me find more opportunities.

Just two weeks ago, questioning our application-specific metrics lead to an easy 10% improvement in throughput for our biggest consumer of CPU cycles. The consumer is an application that determines whether internet advertising campaigns are eligible to bid on an ad slot, and if so, which creative (ad) to show and at what bid price. For the longest time, the most time-consuming part of that process was the first step, testing for campaign eligibility. Consequently, we tracked the execution of that step precisely and worked hard to minimise the time spent on ineligible campaigns, without paying much attention to the rest of the pipeline. However, we were clearly hitting diminishing returns in that area, so I asked myself how an adversary could use our statistics to mislead us. The easiest way I could think of was to have campaigns that are eligible to bid, but without any creative compatible with the ad slot (e.g., because it’s the wrong size or because the website forbids Flash ads): although the campaigns are technically eligible, they are unable to bid on the ad slot. We added code to track these cases and found that almost half of our “eligible” campaigns simply had no creative in the right size. Filtering these campaigns early proved to be a low-hanging fruit with an ideal code complexity:performance improvement ratio.

Trust no one, not even performance counters

I recently learned that we also had to second-guess instruction level profiles. Contemporary x86oids are out of order, superscalar, and speculative machines, so profiles are always messy: “blame” is scattered around the real culprit, and some instructions (pipeline hazards like conditional jumps and uncached memory accesses, mostly) seem to account for more than their actual share. What I never realised is that, in effect, some instructions systematically mislead and push their cycles to others.

Some of our internal spinlocks use mfence. I expected that to be suboptimal, since it’s common knowledge that locked instruction are more efficient barriers: serialising instructions like mfence have to affect streaming stores and other weakly ordered memory accesses, and that’s a lot more work than just preventing store/load reordering. However, our profiles showed that we spent very little time on locking so I never gave it much thought... until eliminating a set of locks had a much better impact on performance than I would have expected from the profile. Faced with this puzzle, I had to take a closer look at the way mfence and locked instructions affect hardware-assisted instruction profiles on our production Xeon E5s.

I came up with a simple synthetic microbenchmark to simulate locking on my E5-4617: the loop body is an adjustable set of memory accesses (reads and writes of out-of-TLB or uncached locations) or computations (divisions) bracketed by pairs of normal stores, mfence, or lock inc/dec to cached memory (I would replace the fences with an increment/decrement pair and it looks like all read-modify-write instructions are implemented similarly on Intel). Comparing runtimes for normal stores with the other instructions helps us gauge their overhead. I can then execute each version under perf and estimate the overhead from the instruction-level profile. If mfence is indeed extra misleading, there should be a greater discrepancy between the empirical impact of the mfence pair and my estimate from the profile.

You can find the super crufty code here, along with a rdtscp version of cycle.h.

With locked instructions and random reads that miss the L3 cache, the (cycle) profile for the microbenchmark loop is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
$ perf annotate -s cache_misses
[...]
    0.06 :        4006b0:       and    %rdx,%r10
    0.00 :        4006b3:       add    $0x1,%r9
    ;; random (out of last level cache) read
    0.00 :        4006b7:       mov    (%rsi,%r10,8),%rbp
   30.37 :        4006bb:       mov    %rcx,%r10
    ;; foo is cached, to simulate our internal lock
    0.12 :        4006be:       mov    %r9,0x200fbb(%rip)        # 601680 <foo>
    0.00 :        4006c5:       shl    $0x17,%r10
    [... Skipping arithmetic with < 1% weight in the profile]
    ;; locked increment of an in-cache "lock" byte
    1.00 :        4006e7:       lock incb 0x200d92(%rip)        # 601480 <private+0x200>
   21.57 :        4006ee:       add    $0x1,%rax
    [...]
    ;; random out of cache read
    0.00 :        400704:       xor    (%rsi,%r10,8),%rbp
   21.99 :        400708:       xor    %r9,%r8
    [...]
    ;; locked in-cache decrement
    0.00 :        400729:       lock decb 0x200d50(%rip)        # 601480 <private+0x200>
   18.61 :        400730:       add    $0x1,%rax
    [...]
    0.92 :        400755:       jne    4006b0 <cache_misses+0x30>

Looking at that profile, I’d estimate that the two random reads account for ~50% of runtime, and the pair of lock inc/dec for ~40%.

The picture is completely different for mfence.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
$ perf annotate -s cache_misses
[...]
    0.00 :        4006b0:       and    %rdx,%r10
    0.00 :        4006b3:       add    $0x1,%r9
    ;; random read
    0.00 :        4006b7:       mov    (%rsi,%r10,8),%rbp
   42.04 :        4006bb:       mov    %rcx,%r10
    ;; store to cached memory (lock word)
    0.00 :        4006be:       mov    %r9,0x200fbb(%rip)        # 601680 <foo>
    [...]
    0.20 :        4006e7:       mfence 
    5.26 :        4006ea:       add    $0x1,%rax
    [...]
    ;; random read
    0.19 :        400700:       xor    (%rsi,%r10,8),%rbp
   43.13 :        400704:       xor    %r9,%r8
    [...]
    0.00 :        400725:       mfence 
    4.96 :        400728:       add    $0x1,%rax
    0.92 :        40072c:       add    $0x1,%rax
    [...]
    0.36 :        40074d:       jne    4006b0 <cache_misses+0x30>

It looks like the loads from uncached memory represent ~85% of the runtime, while the mfence pair might account for at most ~15%, if I include all the noise from surrounding instructions.

If I trusted the profile, I would worry about eliminating locked instructions, but not so much for mfence. However, runtimes (in cycles), which is what I’m ultimately interested in, tell a different story. The same loop of LLC load misses takes 2.81e9 cycles for 32M iterations without any atomic or fence, versus 3.66e9 for lock inc/dec and 19.60e9 cycles for mfence. So, while the profile for the mfence loop would let me believe that only ~15% of the time is spent on synchronisation, the mfence pair really represents 86% \(((19.6 - 2.81) / 19.6)\) of the runtime for that loop! Inversely, the profile for the locked pair would make me guess that we spend about 40% of the time there, but, according to the timings, the real figure is around 23%.

The other tests all point to the same conclusion: the overhead of mfence is strongly underestimated by instruction level profiling, and that of locked instructions exaggerated, especially when adjacent instructions write to memory.

  setup     cycles   (est. overhead)  ~actual overhead

div [ALU] (100 Mi iterations)
 atomic: 20153782848   (20%)          ~ 3.8%
 mfence: 28202315112   (25%)          ~31.3%
vanilla: 19385020088

Reads:

TLB misses (64Mi iterations)
 atomic:  3776164048   (80%)          ~39.3%
 mfence: 12108883816   (50%)          ~81.1%
vanilla:  2293219400 

LLC misses (32Mi iterations)
 atomic:  3661686632   (40%)          ~23.3%
 mfence: 19596840824   (15%)          ~85.7%
vanilla:  2807258536

Writes:

TLB (64Mi iterations)
 atomic:  3864497496   (80%)          ~10.4%
 mfence: 13860666388   (50%)          ~75.0%
vanilla:  3461354848

LLC (32Mi iterations)
 atomic:  4023626584   (60%)          ~16.9%
 mfence: 21425039912   (20%)          ~84.4%
 vanilla: 3345564432

I can guess why we observe this effect; it’s not like Intel is intentionally messing with us. mfence is a full pipeline flush: it slows code down because it waits for all in-flight instructions to complete their execution. Thus, while it’s flushing that slows us down, the profiling machinery will assign these cycles to any of the instructions that are being flushed. Locked instructions instead affect stores that are still queued. By forcing such stores to retire, locked instructions become responsible for the extra cycles and end up “paying” for writes that would have taken up time anyway.

Losing faith in hardware profiling being remotely representative of reality makes me a sad panda; I now have to double check perf profiles when hunting for misleading metrics. At least I can tell myself that knowing about this phenomenon helps us make better informed – if less definite – decisions and ferret out more easy wins.

P.S., if you find this stuff interesting, feel free to send an email (pkhuong at $WORK.com). My team is hiring both experienced developers and recent graduates (:

Gábor MelisTranscripts

· 4 days ago

I've just committed a major feature to MGL-PAX: the ability to include code examples in docstrings. Printed output and return values are marked up with ".." and "=>", respectively.

 (values (princ :hello) (list 1 2))
 .. HELLO
 => :HELLO
 => (1 2)

The extras are:

  • parsing back and updating a transcript
  • auto-checking of up-to-dateness at documentation generation time
  • readable return values can be commented, hand-indented without breaking consistency checks and updates will not destroy those changes
  • Emacs integration: transcribing the last expression and updating a transcript in a region.
  • TRANSCRIBE works without the rest of MGL-PAX so it can be used to format bug reports or as a poor man's expect script.

The documentation provides a tutorialish treatment. I hope you'll find it useful.

Christophe Rhodesstill working on reproducible builds

· 10 days ago

It's been nearly fifteen years, and SBCL still can't be reliably built by other Lisp compilers.

Of course, other peoples' definition of "reliably" might differ. We did achieve successful building under unrelated Lisp compilers twelve years ago; there were a couple of nasty bugs along the way, found both before and after that triumphant announcement, but at least with a set of compilers whose interpretation of the standard was sufficiently similar to SBCL's own, and with certain non-mandated but expected features (such as the type (array (unsigned-byte 8) (*)) being distinct from simple-vector, and single-float being distinct from double-float), SBCL achieved its aim of being buildable on a system without an SBCL binary installed (indeed, using CLISP or XCL as a build host, SBCL could in theory be bootstrapped starting with only gcc).

For true "reliability", though, we should not be depending on any particular implementation-defined features other than ones we actually require - or if we are, then the presence or absence of them should not cause a visible difference in the resulting SBCL. The most common kind of leak from the host lisp to the SBCL binary was the host's value of most-positive-fixnum influencing the target, causing problems from documentation errors all the way up to type errors in the assembler. Those leaks were mostly plugged a while ago, though they do recur every so often; there are other problems, and over the last week I spent some time tracking down three of them.

The first: if you've ever done (apropos "PRINT") or something similar at the SBCL prompt, you might wonder at the existence of functions named something like SB-VM::|CACHED-FUN--PINSRB[(EXT-2BYTE-XMM-REG/MEM ((PREFIX (QUOTE (102))) (OP1 (QUOTE (58))) (OP2 (QUOTE (32))) (IMM NIL TYPE (QUOTE IMM-BYTE))) (QUOTE (NAME TAB REG , REG/MEM ...)))]-EXT-2BYTE-XMM-REG/MEM-PRINTER|.

What is going on there? Well, these functions are a part of the disassembler machinery; they are responsible for taking a certain amount of the machine code stream and generating a printed representation of the corresponding assembly: in this case, for the PINSRB instruction. Ah, but (in most instruction sets) related instructions share a fair amount of structure, and decoding and printing a PINSRD instruction is basically the same as for PINSRB, with just one #x20 changed to a #x22 - in both cases we want the name of the instruction, then a tab, then the destination register, a comma, the source, another comma, and the offset in the destination register. So SBCL arranges to reuse the PINSRB instruction printer for PINSRD; it maintains a cache of printer functions, looked up by printer specification, and reuses them when appropriate. So far, so normal; the ugly name above is the generated name for such a function, constructed by interning a printed, string representation of some useful information.

Hm, but wait. See those (QUOTE (58)) fragments inside the name? They result from printing the list (quote (58)). Is there a consensus on how to print that list? Note that *print-pretty* is bound to nil for this printing; prior experience has shown that there are strong divergences between implementations, as well as long-standing individual bugs, in pretty-printer support. So, what happens if I do (write-to-string '(quote foo) :pretty nil)?

So, if SBCL was compiled using CLISP, the name of the same function in the final image would be SB-VM::|CACHED-FUN--PINSRB[(EXT-2BYTE-XMM-REG/MEM ((PREFIX '(102)) (OP1 '(58)) (OP2 '(32)) (IMM NIL TYPE 'IMM-BYTE)) '(NAME TAB REG , REG/MEM ...))]-EXT-2BYTE-XMM-REG/MEM-PRINTER|. Which is shorter, and maybe marginally easier to read, but importantly for my purposes is not bitwise-identical.

Thus, here we have a difference between host Common Lisp compilers which leaks over into the final image, and it must be eliminated. Fortunately, this was fairly straightforward to eliminate; those names are never in fact used to find the function object, so generating a unique name for functions based on a counter makes the generated object file bitwise identical, no matter how the implementation prints two-element lists beginning with quote.

The second host leak is also related to quote, and to our old friend backquote - though not related in any way to the new implementation. Consider this apparently innocuous fragment, which is a simplified version of some code to implement the :type option to defstruct:

(macrolet ((def (name type n)
             `(progn
                (declaim (inline ,name (setf ,name)))
                (defun ,name (thing)
                  (declare (type simple-vector thing))
                  (the ,type (elt thing ,n)))
                (defun (setf ,name) (value thing)
                  (declare (type simple-vector thing))
                  (declare (type ,type value))
                  (setf (elt thing ,n) value)))))
  (def foo fixnum 0)
  (def bar string 1))

What's the problem here? Well, the functions are declaimed to be inline, so SBCL records their source code. Their source code is generated by a macroexpander, and so is made up of conses that are generated programmatically (as opposed to freshly consed by the reader). That source code is then stored as a literal object in an object file, which means in practice that instructions for reconstructing a similar object are dumped, to be executed when the object file is processed by load.

Backquote is a reader macro that expands into code that, when evaluated, generates list structure with appropriate evaluation and splicing of unquoted fragments. What does this mean in practice? Well, one reasonable implementation of reading `(type ,type value) might be:

(cons 'type (cons type '(value)))

and indeed you might (no guarantees) see something like that if you do

(macroexpand '`(type ,type value))

in the implementation of your choice. Similarly, reading `(setf (elt thing ,n) value) will eventually generate code like

(cons 'setf (cons (cons 'elt (list 'thing n)) '(value)))

Now, what is "similar"? In this context, it has a technical definition: it relates two objects in possibly-unrelated Lisp images, such that they can be considered to be equivalent despite the fact that they can't be compared:

similar adj. (of two objects) defined to be equivalent under the similarity relationship.

similarity n. a two-place conceptual equivalence predicate, which is independent of the Lisp image so that two objects in different Lisp images can be understood to be equivalent under this predicate. See Section 3.2.4 (Literal Objects in Compiled Files).

Following that link, we discover that similarity for conses is defined in the obvious way:

Two conses, S and C, are similar if the car of S is similar to the car of C, and the cdr of S is similar to the cdr of C.

and also that implementations have some obligations:

Objects containing circular references can be externalizable objects. The file compiler is required to preserve eqlness of substructures within a file.

and some freedom:

With the exception of symbols and packages, any two literal objects in code being processed by the file compiler may be coalesced if and only if they are similar [...]

Put this all together, and what do we have? That def macro above generates code with similar literal objects: there are two instances of '(value) in it. A host compiler may, or may not, choose to coalesce those two literal '(value)s into a single literal object; if it does, the inline expansion of foo (and bar) will have a circular reference, which must be preserved, showing up as a difference in the object files produced during the SBCL build. The fix? It's ugly, but portable: since we can't stop an aggressive compiler from coalescing constants which are similar but not identical, we must make sure that any similar substructure is in fact identical:

(macrolet ((def (name type n)
             (let ((value '(value)))
               `(progn
                  (declaim (inline ,name (setf ,name)))
                  (defun ,name (thing)
                    (declare (type simple-vector thing))
                    (the ,type (elt thing ,n)))
                  (defun (setf ,name) (value thing)
                    (declare (type simple-vector thing))
                    (declare (type ,type . ,value))
                    (setf (elt thing ,n) . ,value)))))
  (def foo fixnum 0)
  (def bar string 1))

Having dealt with a problem with quote, and a problem with backquote, what might the Universe serve up for my third problem? Naturally, it would be a problem with a code walker. This code walker is somewhat naïve, assuming as it does that its body is made up of forms or tags; it is the assemble macro, which is used implicitly in the definition of VOPs (reusable assembly units); for example, like

(assemble ()
  (move ptr object)
  (zeroize count)
  (inst cmp ptr nil-value)
  (inst jmp :e DONE)
 LOOP
  (loadw ptr ptr cons-cdr-slot list-pointer-lowtag)
  (inst add count (fixnumize 1))
  (inst cmp ptr nil-value)
  (inst jmp :e DONE)
  (%test-lowtag ptr LOOP nil list-pointer-lowtag)
  (error-call vop 'object-not-list-error ptr)
 DONE))

which generates code to compute the length of a list. The expander for assemble scans its body for any atoms, and generates binding forms for those atoms to labels:

(let ((new-labels (append labels
                          (set-difference visible-labels inherited-labels))))
  ...
  `(let (,@(mapcar (lambda (name) `(,name (gen-label))) new-labels))
     ...))

The problem with this, from a reproducibility point of view, is that set-difference (and the other set-related functions: union, intersection, set-exclusive-or and their n-destructive variants) do not return the sets with a specified order - which is fine when the objects are truly treated as sets, but in this case the LOOP and DONE label objects ended up in different stack locations depending on the order of their binding. Consequently the machine code for the function emitting code for computing a list's length - though not the machine code emitted by that function - would vary depending on the host's implementation of set-difference. The fix here was to sort the result of the set operations, knowing that all the labels would be symbols and that they could be treated as string designators.

And after all this is? We're still not quite there: there are three to four files (out of 330 or so) which are not bitwise-identical for differing host compilers. I hope to be able to rectify this situation in time for SBCL's 15th birthday...

Timofei ShatrovWords made out of words

· 14 days ago

Since my last post I’ve done a lot of work on my Japanese sentence-segmenting algorithm, so it’s time for an update.

First of all, I added conjugations. Here’s how JMdict does conjugations. That’s for a single verb. There’s a note saying “this table has been automatically generated”; indeed, in JMdict conjugations are generated on a basis of a rather large .csv file and are not stored in the database. Obviously for my purposes it is more efficient to have these in my database, so I ported a (rather simple) algorithm to Common Lisp and wrote a (really complex) procedure to load them. It takes quite a while to INSERT those one by one, which made me wish postmodern had some sort of bulk inserting mechanism. Some time later I discovered that some of these conjugations are themselves verbs that can be (and often are) conjugated. So I added “second level” conjugations that point both to first level conjugation and to the original verb. Hopefully “third level” conjugations are rarely used.

Meanwhile I’ve been trying to improve the segmentation algorithm. The first major change was calculating n best segmentations instead of just one. That would allow me to have a better picture of what the algorithm prefers. I came up with the structure that I call top-array, which is basically an array of n scores sorted from the biggest to smallest and when a new score is added, we go from the end and push everything smaller than the new score to the right. I thought it was pretty elegant and probably the fastest way to do this for small n (obviously some sort of tree would work better for large n).

(defstruct (top-array-item (:conc-name tai-)) score payload)

(defclass top-array ()
  ((array :reader top-array)
   (count :reader item-count :initform 0)
   ))

(defmethod initialize-instance :after ((obj top-array) &key (limit 5))
  (setf (slot-value obj 'array) (make-array limit :initial-element nil)))

(defgeneric register-item (collection score payload)
  (:method ((obj top-array) score payload)
    (with-slots (array count) obj
      (let ((item (make-top-array-item :score score :payload payload))
            (len (length array)))
        (loop for idx from (min count len) downto 0
           for prev-item = (when (> idx 0) (aref array (1- idx)))
           for done = (or (not prev-item) (>= (tai-score prev-item) score))
           when (< idx len) do (setf (aref array idx) (if done item prev-item))
           until done)
        (incf count)))))

(defgeneric get-array (collection)
  (:method ((obj top-array))
    (with-slots (array count) obj
      (if (>= count (length array)) array (subseq array 0 count)))))
    

An instance of top-array is created for every segment (found word in a sentence), as well as one for the entire sentence, from which the best path (a sequence of words) is taken in the end. Then the basic algorithm is similar to the one described in my previous post, but gains an extra inner loop.

(loop for (seg1 . rest) on segments
      for score1 = (get-segment-score seg1)
      do (register-item (segment-top seg1) score1 (list seg1))
         (register-item top score1 (list seg1))
      (loop for seg2 in rest
            for score2 = (get-segment-score seg2)
            when (>= (segment-start seg2) (segment-end seg1)) do
            (loop for tai across (get-array (segment-top seg1))
                 for path = (cons seg2 (tai-payload tai))
                 for score = (+ score2 (tai-score tai))
                 do (register-item (segment-top seg2) score path)
                    (register-item top score path))))

Then (get-array top) would return n best paths.

After this I started thinking on how to make my algorithm more context-sensitive. The way in which every segment is scored is completely independent of the other segments, which might cause best scored path to be a sequence of words that make no sense when put next to each other! The above algorithm is easy to modify to add some sort of bonus to two subsequent segments, so my first attempt was to encourage words that like to be next to each other in natural language with some extra score (I called that “synergy”). So, for example, there are “no-adjectives”, which are basically nouns, but when followed by particle “no” they become adjectives. I added a synergy that adds 15 points if such word is followed by particle “no”. In the end this way to do things has proven itself limited. Words can have wildly different scores and when things go wrong, extra 15 points might not be enough to make them right. On the other hand, if I increase this bonus too much, this might erroneously break up words that just so happen to have “no” in them.

Later I came up with the concept of compound words, which are “words” that don’t exist in the database, but rather consist of several words that do exist in the database. Right now, it’s mostly a primary word + one or several suffixes, but potentially there could be prefixes too. For the purposes of segmentation a compound word acts like one single word. One example of a common suffix would be “たい” (-tai) , which follows a verb (“to X”) conjugated in a certain way and the resultant meaning is “to want to X”. Most of these suffixes themselves have many conjugations. To check if a word can be understood as a compound word, I need to check if it ends with one of many suffixes, and then check if the part before the suffix has correct part of speech or conjugation. All possible suffixes and their meanings are put into a hashtable and then we can check if a word ends with some of them by checking all its endings versus the hashtable.

(defun get-suffixes (word)
  (init-suffixes)
  (loop for start from (1- (length word)) downto 1
       for substr = (subseq word start)
       for val = (gethash substr *suffix-cache*)
       when val
       collect (cons substr val)))

The concept of suffixes has fared much better as now I am able to calculate scores of compound words in a more versatile way.

I would still sometimes encounter phrases that are split badly by my algorithm, but a human would segment easily. For example if the words “AB” and “ABC” both exist in database, but “AB” happens to score higher (e.g. because it’s a really common word, while ABC is not so much), then “ABC” would never be segmented as one word “ABC”, it would be “AB”+”C”, even if “C” is a completely worthless word, or even not a word at all (a gap). An example of a “worthless” word is a hiragana spelling of one-syllable word that would normally be spelled with a kanji. I didn’t care about those much, because they had really low scores and thus only appeared when something went awry. However getting rid of these low-scoring words would allow me to place a large penalty on gaps and thus “ABC” will be able to score higher than “AB”+gap. In the path-finding algorithm above the same score is put into top and segment-top top-arrays. But if we want to penalize gaps, the score put into top should also include a penalty for the gap to the right of the last segment, if it exists. Penalties for gaps to the left of the leftmost segment and in-between segments should be added to both.

Anyway, I’m pretty happy with how this thing is progressing, and I’m going to switch my efforts to building a web-interface. Here’s how it currently works in REPL:

(click here for full-res image)

image

Kinda messy, isn’t it? The challenge would be to display all this information in reasonable manner. I already have some ideas, but it would still probably take some effort to decipher. But then again, translating the sentence was never the goal, just romanizing it, which ichiran does pretty well right now.

drmeisterDebugging with the Clasp debugger

· 15 days ago

Clasp provides two ways of debugging code. In interactive sessions Clasp invokes a built in Common Lisp debugger when errors or other exceptional situations arise. The Clasp compiler also generates DWARF debugging information that can be used by the GDB debugger (and hopefully soon the LLDB debugger) to display Clasp Common Lisp source information interleaved with C++ source information.

To see this start up clasp and type what follows the > prompt:

Top level.
> (defun c () (break "In c"))

C
> (defun b () (c))

B
> (defun a () (b))

A
> (a)

Condition of type: SIMPLE-CONDITION
In c

Available restarts:
(use :r1 to invoke restart 1)

1. (CONTINUE) Return from BREAK.
2. (RESTART-TOPLEVEL) Go back to Top-Level REPL.

Broken at frame[14] CORE::REP.
 File: #<CORE:SOURCE-FILE-INFO #P"/Users/meister/Development/clasp/src/lisp/kernel/lsp/top.lsp"> (Position #573)
>> 

The double prompt >> indicates that we are now in the Clasp Common Lisp debugger. This debugger is inherited from ECL (because Clasp uses the excellent Common Lisp source code from ECL). To get a list of commands that are available in the debugger type:


>> :h

Top level commands:
:cf		Compile file.
:exit or ^D	Exit Lisp.
:ld		Load file.
:step		Single step form.
:tr(ace)	Trace function.
:untr(ace)	Untrace function.
:pwd	Print the current value of *default-pathname-defaults*.
:cd	Change the current value of *default-pathname-defaults*.

Help commands:
:apropos	Apropos.
:doc(ument)	Document.
:h(elp) or ?	Help.  Type ":help help" for more information.

Break commands:
:q(uit)		Return to some previous break level.
:pop		Pop to previous break level.
:c(ontinue)	Continue execution.
:b(acktrace)	Print backtrace.
:f(unction)	Show current function.
:p(revious)	Go to previous function.
:d(own)         Alias to :previous.
:n(ext)		Go to next function.
:u(p)           Alias to :next.
:g(o)		Go to next function.
:fs             Search forward for function.
:bs             Search backward for function.
:disassemble	Disassemble current function.
:l(ambda-)e(expression)	Show lisp code for current function.
:v(ariables)	Show local variables, functions, blocks, and tags.
:hide		Hide function.
:unhide		Unhide function.
:hp		Hide package.
:unhp		Unhide package.
:unhide-all     Unhide all variables and packages.
:bds            Show binding stack.
:frs            Show frame stack.
:m(essage)      Show error message.
:hs		Help stack.
:i(nspect)      Inspect value of local variable.

Restart commands:
:r1             Return from BREAK. (CONTINUE).
:r2             Go back to Top-Level REPL. (RESTART-TOPLEVEL).
>> 


Clasp/ECL use Common Lisp keywords to activate debugger functionality.

To generate a backtrace type:


>> :b

--------STACK TRACE--------
   frame#  0toplevel         epilogueForm     0/0   REPL
   frame#  1/c              top.lsp   419/2   CORE::TOP-LEVEL
   frame#  2/c              top.lsp   615/21  CORE::TPL
   frame#  3/c              top.lsp   605/32  CORE::REP
   frame#  4/b         evaluator.cc  2353/0   CORE:TOP-LEVEL-EVAL-WITH-ENV
   frame#  5/b         evaluator.cc  2351/0   CORE:COMPILE-FORM-AND-EVAL-WITH-ENV
   frame#  6/c            -no-file-     1/0   nil
   frame#  7/c            -no-file-     1/0   A
   frame#  8/c            -no-file-     1/0   B
   frame#  9/c            -no-file-     1/0   C
   frame# 10/c       conditions.lsp   457/8   COMMON-LISP:BREAK
   frame# 11/c              top.lsp  1507/9   COMMON-LISP:INVOKE-DEBUGGER
   frame# 12/c              top.lsp  1489/5   CORE::DEFAULT-DEBUGGER
   frame# 13/c              top.lsp   618/7   CORE::TPL
-->frame# 14/c              top.lsp   605/32  CORE::REP
   frame# 15/b         evaluator.cc  2353/0   CORE:TOP-LEVEL-EVAL-WITH-ENV
   frame# 16/b         evaluator.cc  2351/0   CORE:COMPILE-FORM-AND-EVAL-WITH-ENV
   frame# 17/c            -no-file-     0/0   nil
   frame# 18/c              top.lsp  1088/3   CORE::TPL-BACKTRACE
   frame# 19/b            stacks.cc   712/0   CORE:IHS-BACKTRACE

NIL
>> 

The —-> indicates the current frame that the debugger has stopped on. Since the error handling code and the debugger functions are all written in Common Lisp, those functions also appear on the backtrace. The functions we entered are in frames 7, 8, and 9.

At this point we could go to a specific frame using :g and view the environment of that frame using :v or we can print variables by just typing their names.

For now we will just leave the debugger and return to the top level REPL by invoking a restart.


>> :r2

> 

Now we are back in the top level REPL and can continue working.

Next I’ll show you how to use the DWARF generated debugging information embedded in compiled Common Lisp code to debug Clasp using GDB or LLDB.


Quicklisp newsOctober 2014 Quicklisp dist update now available

· 17 days ago
New projects:
Updated projects: asteroids, avatar-api, babel, basic-binary-ipc, caveman, cffi, checkl, cl-ana, cl-async, cl-autowrap, cl-base58, cl-charms, cl-cli, cl-cli-parser, cl-conspack, cl-dbi, cl-dot, cl-gdata, cl-gss, cl-locatives, cl-mediawiki, cl-opengl, cl-project, clack, clip, closer-mop, clss, coleslaw, colleen, com.informatimago, cqlcl, datafly, dbus, djula, docbrowser, drakma, dynamic-mixins, fast-io, floating-point, gbbopen, gendl, graph, hdf5-cffi, lisp-executable, lisp-interface-library, lisp-unit2, mel-base, metabang-bind, mgl-pax, micmac, modularize-hooks, modularize-interfaces, nibbles, osicat, pg, plump, postmodern, quickproject, ratify, restas, rucksack, rutils, s-xml, scriptl, serapeum, shelly, smug, spinneret, staple, stumpwm, trivial-download, trivial-mimes, trivial-signal, universal-config, utils-kt, yason.

Removed projects: cl-test-more, phemlock.

cl-test-more hasn't really been removed. It's been renamed to prove.

I removed phemlock by request; it represents an old, dead branch of development, hosted on CVS. You can still get hemlock through Quicklisp by loading one of hemlock.tty, hemlock.qt, or hemlock.clx, all provided by the hemlock project on gitorious.

To get this update, use (ql:update-dist "quicklisp").


Christophe Rhodesinteresting pretty-printer bug

· 17 days ago

One of SBCL's Google Summer of Code students, Krzysztof Drewniak (no relation) just got to merge in his development efforts, giving SBCL a far more complete set of Unicode operations.

Given that this was the merge of three months' out-of-tree work, it's not entirely surprising that there were some hiccups, and indeed we spent some time diagnosing and fixing a 1000-fold slowdown in char-downcase. Touch wood, all seems mostly well, except that Jan Moringen reported that, when building without the :sb-unicode feature (and hence having a Lisp with 8-bit characters) one of the printer consistency tests was resulting in an error.

Tracking this down was fun; it in fact had nothing in particular to do with the commit that first showed the symptom, but had been lying latent for a while and had simply never shown up in automated testing. I've expressed my admiration for the Common Lisp standard before, and I'll do it again: both as a user of the language and as an implementor, I think the Common Lisp standard is a well-executed document. But that doesn't stop it from having problems, and this is a neat one:

When a line break is inserted by any type of conditional newline, any blanks that immediately precede the conditional newline are omitted from the output and indentation is introduced at the beginning of the next line.

(from pprint-newline)

For the graphic standard characters, the character itself is always used for printing in #\ notation---even if the character also has a name[5].

(from CLHS 22.1.3.2)

Space is defined to be graphic.

(from CLHS glossary entry for 'graphic')

What do these three requirements together imply? Imagine printing the list (#\a #\b #\c #\Space #\d #\e #\f) with a right-margin of 17:

(write-to-string '(#\a #\b #\c #\Space #\d #\e #\f) :pretty t :right-margin 17)
; => "(#\\a #\\b #\\c #\\
; #\\d #\\e #\\f)"

The #\Space character is defined to be graphic; therefore, it must print as #\ rather than #\Space; if it happens to be printed just before a conditional newline (such as, for example, generated by using pprint-fill to print a list), the pretty-printer will helpfully remove the space character that has just been printed before inserting the newline. This means that a #\Space character, printed at or near the right margin, will be read back as a #\Newline character.

It's interesting to see what other implementations do. CLISP 2.49 in its default mode always prints #\Space; in -ansi mode it prints #\ but preserves the space even before a conditional newline. CCL 1.10 similarly preserves the space; there's an explicit check in output-line-and-setup-for-next for an "escaped" space (and a comment that acknowledges that this is a heuristic that can be wrong in the other direction). I'm not sure what the best fix for this is; it's fairly clear that the requirements on the printer aren't totally consistent. For SBCL, I have merged a one-line change that makes the printer print using character names even for graphic characters, if the *print-readably* printer control variable is true; it may not be ideal that print/read round-tripping was broken in the normal case, but in the case where it's explicitly been asked for it is clearly wrong.

ABCL DevShort tip :: Booting quicklisp via SLIME

· 20 days ago
For the truly lazy, the following forms will quickly load Quicklisp:

   (require :abcl-contrib) (asdf:load-system :quicklisp-abcl)


drmeisterThings you can do with Clasp #1

· 23 days ago

Now that people are starting to build Clasp I thought I would say a few things about what you can do with it.

Clasp is an implementation of Common Lisp (80-90% complete) and I plan to make it an ANSI compliant Common Lisp as soon as possible. I also plan to add a faster compiler and expose some powerful C++ libraries to extend its capabilities.

But here are a few things you can do right away to get a sense of what Clasp does and to test some of its capabilities. Code that you type will (look-like-this). Don’t worry about how what you see isn’t colored or highlighted as shown here, I’m exploring different ways of rendering program output in this blog.

(defun add (x y) (+ x y))

ADD

(add 3 5)

8

(disassemble 'add)

Disassembling function: #<COMMON-LISP:COMPILED-FUNCTION CORE:ADD>

"#<LLVM-SYS::FUNCTION 
define internal void @ADD({ {}*, i32 }* %result-ptr, { {}* }* %closed-af-ptr, i32 %num-varargs, {}* %farg0, {}* %farg1, {}* %farg2, i8* %va-list) {
\"(TRY-0).entry\":
  %lambda-args-42- = alloca { {}* }
  call void @newAFsp({ {}* }* %lambda-args-42-)
  %temp = alloca { {}* }
  call void @newTsp({ {}* }* %temp)
  %0 = alloca { {}* }
  call void @newTsp({ {}* }* %0)
  call void @makeValueFrame({ {}* }* %lambda-args-42-, i32 2, i32 2000058)
  call void @setParentOfActivationFrame({ {}* }* %lambda-args-42-, { {}* }* %closed-af-ptr)
  %correct-num-args = icmp eq i32 %num-varargs, 2
  br i1 %correct-num-args, label %\"(TRY-0).continue3\", label %\"(TRY-0).error\"

\"(TRY-0).error\":                                  ; preds = %\"(TRY-0).entry\"
  %enough-args = icmp slt i32 %num-varargs, 2
  br i1 %enough-args, label %\"(TRY-0).error1\", label %\"(TRY-0).continue\"
...

That gobbledy-gook is pure LLVM-IR code generated by the Clasp Common Lisp compiler and using the fantastic LLVM library. It is exactly the same intermediate language that the Clang compiler converts C++/C/Objective-C into before it lowers it to machine code. Clasp shares the same LLVM backend library with the Clang compiler and once Clasp generates LLVM-IR, that is as efficient as that generated by Clang, then Clasp will generate code that runs as fast as C++ and C!

For some more information on Common Lisp you can check out the following links or use Google. I haven’t tested the tutorial against Clasp but almost everything should work.

For a tutorial:

http://en.wikibooks.org/wiki/Common_Lisp/First_steps/Beginner_tutorial

For beginners:

Land of Lisp: Learn to Program in Lisp, One Game at a Time!

Land of Lisp: Learn to Program in Lisp, One Game at a Time!

Buy from Amazon

I’ll post more later.


Hans Hübner

· 24 days ago

Berlin Lispers Meetup: Tuesday September 30th, 2014, 8.00pm

You are kindly invited to the next "Berlin Lispers Meetup", an informal gathering for anyone interested in Lisp, beer or coffee:

Berlin Lispers Meetup
Tuesday, September 30th, 2014
8 pm onwards

St Oberholz, Rosenthaler Straße 72, 10119 Berlin
U-Bahn Rosenthaler Platz

We will try to occupy a large table on the first floor, but in case you don't see us,
please contact Christian: 0157 87 05 16 14.

Please join for another evening of parentheses!

drmeisterHow Clasp compiles itself

· 27 days ago

This is the process that Clasp uses to compile itself from the repository. I wrote it stream-of-consciousness in response to a question on IRC and I thought I should document this for later.

Clasp starts up running with a slow S-expression walking interpreter.
It loads clasp/src/lisp/kernel/init.lsp. Within init.lsp is a list of modules that it loads to build everything. The list is in the variable *init-files* which contains a list of symbols that are translated to file pathnames by the system. The list also includes keywords like :base and :cmp – these denote way-points in the build process. Clasp then loads files from :start to :cmp into the interpreter. That loads in the Common Lisp code for the Clasp compiler. Then Clasp COMPILE-FILE(s) each source file from :start to :cmp and after compiling each file it loads the new bitcode file that is generated.
It’s slow to start but once the compiler starts compiling the files between :pre-cmp and :cmp it gets faster and faster as interpreted functions are replaced by compiled functions. Then it loads cmp/cmprepl (these files are all in src/lisp/kernel/lsp/* and src/lisp/kernel/cmp/*)
cmp/cmprepl installs a function that automatically compiles every form passed to EVAL before it evaluates it. Then it loads the files from :cmp to :min and then COMPILE-FILE(s) them. Then Clasp links all the bitcode files together with a bitcode file generated from src/llvmo/intrinsics.cc. So C++ code gets inlined into the compiled Lisp code. Then it generates min-boehm:image.bundle this is a minimal common lisp without CLOS. Then Clasp starts compiling the full-boehm version. It boots with the min-boehm:image.bundle and LOADs everything from :base to :all. Then it COMPILE-FILE(s) everything from :base to :all.
Then it links all of that together with intrinsics.cc and some epilogue code to start up the REPL.

Whew – that’s the build system.


drmeisterBuilding Clasp and externals-clasp

· 28 days ago

Hey folks,

— Update 18:00 EST Sept 29, 2014 —

Things are starting to stabilize and multiple people are getting Clasp built on OS X and Linux. The precise systems that Clasp has been built on are listed in the README.md file on github.

We have a chatroom on IRC on freenode in #clasp. Drop in if you have some time.

On linux you need either (a) gcc 4.8 -or- (b) gcc 4.9 and clang 3.5. In the (a) case, the clang 3.6 compiler that comes with externals-clasp can be used. (Sorry, it’s a bit complicated).

These linux requirements are so specific because of changes that have been made to gcc 4.9 and llvm/clang that are outside of my control.

Thank you for being so brave and installing a new package like clasp in the first days after it was released.

You need to install externals-clasp first before installing clasp.

People are starting to post notifications about bugs in Clasp and that’s fantastic! Thank you. I’ll get to them as quickly as possible.

I love to hear peoples comments, feedback and suggestions regarding how to improve clasp.

Best,

.Chris.


Christophe Rhodescode walking for pipe sequencing

· 28 days ago

Since it seems still topical to talk about Lisp and code-transformation macros, here's another worked example - this time inspired by the enthusiasm for the R magrittr package.

The basic idea behind the magrittr package is, as Hadley said at EARL2014, to convert from a form of code where arguments to the same function are far apart to one where they're essentially close together; the example he presented was converting

arrange(
  summarise
    group_by(
      filter(babynames, name == "Hadley"),
      year),
    total = sum(n)
  desc(year))

to

b0 <- babynames
b1 <- filter(b0, name == "Hadley")
b2 <- group_by(b1, year)
b3 <- summarise(b2, total = sum(n))
b4 <- arrange(b3, desc(year))

only without the danger of mistyping one of the variable names along the way and failing to perform the computation that was intended.

R, as I have said before, is a Lisp-1 with weird syntax and wacky evaluation semantics. One of the things that ordinary user code can do is inspect the syntactic form of its arguments, before evaluating them. This means that when looking at a fragment of code such as

foo(bar(2,3), 4)

where a call-by-value language would first evaluate bar(2,3), then call foo with two arguments (the value resulting from the evaluation, and 4), R instead uses a form of call-by-need evaluation, and also provides operators for inspecting the promise directly. This means R users can do such horrible things as

foo <- function(x) {
    tmp <- substitute(x)
    sgn <- 1
    while(class(tmp) == "(") {
        tmp <- tmp[[2]]
        sgn <- sgn * -1
    }
    sgn * eval.parent(tmp)
}
foo(3) # 3
foo((3)) # -3
foo(((3))) # 3
foo((((3)))) # -3 (isn't this awesome?  I did say "wacky")

In the case of magrittr, the package authors have taken advantage of this to invent some new syntax; the pipe operator %>% is charged with inserting its first argument (its left-hand side, in normal operation) as the first argument to the call of its second argument (right-hand side). Hadley's example is

babynames %>%
  filter(name == "Hadley") %>%
  group_by(year) %>%
  summarise(total = sum(n)) %>%
  arrange(desc(year))

and this is effective because the data flow in this case really is a pipeline: there's a dataset, which needs filtering, then grouping, then summarization, then sorting, and each operation works on the result of the previous. This already needs to inspect the syntactic form of the argument; an additional feature is recognizing the presence of .s in the call, and placing the left-hand side value in that argument position instead of as the first argument if it is present.

In Common Lisp, there are some piping or chaining operators out there (e.g. one two three (search for ablock) four and probably many others), and they do well enough. However! They mostly suffer from similar problems that we've seen before: doing code transformations with not quite enough understanding of the semantics of the code that they're transforming; again, that's fine for normal use, but for didactic purposes let's pretend that we really care about this.

The -> macro from http://stackoverflow.com/a/11080068 is basically the same as the magrittr %>% operator: it converts symbols in the pipeline to function calls, and places the result of the previous evaluation as the first argument of the current operator, except if a $ is present in the arguments, in which case it replaces that. (This version doesn't support more than one $ in the argument list; it would be a little bit of a pain to support that, needing a temporary name, but it's straightforward in principle).

Since the -> macro does its job, a code-walker implementation isn't strictly necessary: pure syntactic manipulation is good enough, and if it's used with just the code it expects, it will do it well. It is of course possible to express what it does using a code-walker; we'll fix the multiple-$ 'bug' along the way, by explicitly introducing bindings rather than replacements of symbols:

(defmacro -> (form &body body)
  (labels ((find-$ (form env)
             (sb-walker:walk-form form env
              (lambda (f c e)
                (cond
                  ((eql f '$) (return-from find-$ t))
                  ((eql f form) f)
                  (t (values f t)))))
             nil)
           (walker (form context env)
             (cond
               ((symbolp form) (list form))
               ((atom form) form)
               (t (if (find-$ form env)
                      (values `(setq $ ,form) t)
                      (values `(setq $ ,(list* (car form) '$ (cdr form))) t))))))
    `(let (($ ,form))
       ,@(mapcar (lambda (f) (sb-walker:walk-form f nil #'walker)) body))))

How to understand this implementation? Well, clearly, we need to understand what sb-walker:walk does. Broadly, it calls the walker function (its third argument) on successive evaluated subforms of the original form (and on variable names set by setq); the primary return value is used as the interim result of the walk, subject to further walking (macroexpansion and walking of its subforms) except if the second return value from the walker function is t.

Now, let's start with the find-$ local function: its job is to walk a form, and returns t if it finds a $ variable to be evaluated at toplevel and nil otherwise. It does that by returning t if the form it's given is $; otherwise, if the form it's given is the original form, we need to walk its subforms, so return f; otherwise, return its form argument f with a secondary value of t to inhibit further walking. This operation is slightly at odds with the use of a code walker: we are explicitly not taking advantage of the fact that it understands the semantics of the code it's walking. This might explain why the find-$ function itself looks a bit weird.

The walker local function is responsible for most of the code transformation. It binds $ to the value of the first form, then repeatedly sets $ to the value of successive forms, rewritten to interpolate a $ in the first argument position if there isn't one in the form already (as reported by find-$). If any of the forms is a symbol, it gets listified and subsequently re-walked. Thus

(macroexpand-1 '(-> "THREE" string-downcase (char 0)))
; => (LET (($ "THREE"))
;      (SETQ $ (STRING-DOWNCASE $))
;      (SETQ $ (CHAR $ 0))),
;    T

So far, so good. Now, what could we do with a code-walker that we can't without? Well, the above implementation of -> supports chaining simple function calls, so one answer is "chaining things that aren't just function calls". Another refinement is to support eliding the insertion of $ when there are any uses of $ in the form, not just as a bare argument. Looking at the second one first, since it's less controversial:

(defmacro -> (form &body body)
  (labels ((find-$ (form env)
             (sb-walker:walk-form form env
              (lambda (f c e)
                (cond
                  ((and (eql f '$) (eql c :eval))
                   (return-from find-$ t))
                  (t f))))
             nil)
           (walker (form context env)
             (cond
               ((symbolp form) (list form))
               ((atom form) form)
               (t (if (find-$ form env)
                      (values `(setq $ ,form) t)
                      (values `(setq $ ,(list* (car form) '$ (cdr form))) t))))))
    `(let (($ ,form))
       ,@(mapcar (lambda (f) (sb-walker:walk-form f nil #'walker)) body))))

The only thing that's changed here is the definition of find-$, and in fact it's a little simpler: the task is now to walk the entire form and find uses of $ in an evaluated position, no matter how deep in the evaluation. Because this is a code-walker, this will correctly handle macros, backquotes, quoted symbols, and so on, and this allows code of the form

(macroexpand-1 '(-> "THREE" string-downcase (char 0) char-code (complex (1+ $) (1- $))))
; => (LET (($ "THREE"))
;      (SETQ $ (STRING-DOWNCASE $))
;      (SETQ $ (CHAR-CODE $))
;      (SETQ $ (COMPLEX (1+ $) (1- $)))),
;    T

which, as far as I can tell, is not supported in magrittr: doing 3 %>% complex(.+1,.-1) is met with the error that "object '.' not found". Supporting this might, of course, not be a good idea, but at least the code walker shows that it's possible.

What if we wanted to augment -> to handle binding forms, or special forms in general? This is probably beyond the call of duty, but let's just briefly imagine that we wanted to be able to support binding special variables around the individual calls in the chain; for example, we want

(-> 3 (let ((*random-state* (make-random-state))) rnorm) mean)

to expand to

(let (($ 3))
  (setq $ (let ((*random-state* (make-random-state))) (rnorm $)))
  (setq $ (mean $)))

and let us also say, to make it interesting, that uses of $ in the bindings clauses of the let should not count against inhibiting the insertion of $ in the first argument position of the first form in the body of the let, so

(-> 3 (let ((y (1+ $))) (atan y)))

should expand to

(let (($ 3)) (setq $ (let ((y (1+ $))) (atan $ y))))

So our code walker needs to walk the bindings of the let, merely collecting information into the walker's lexical environment, then walk the body performing the same rewrite as before. CHALLENGE ACCEPTED:

(defmacro -> (&body forms)
  (let ((rewrite t))
    (declare (special rewrite))
    (labels ((find-$ (form env)
               (sb-walker:walk-form form env
                (lambda (f c e)
                  (cond
                    ((and (eql f '$) (eql c :eval))
                     (return-from find-$ t))
                    (t f))))
               nil)
             (walker (form context env)
               (declare (ignore context))
               (typecase form
                 (symbol (if rewrite (list form) form))
                 (atom form)
                 ((cons (member with-rewriting without-rewriting))
                  (let ((rewrite (eql (car form) 'with-rewriting)))
                    (declare (special rewrite))
                    (values (sb-walker:walk-form (cadr form) env #'walker) t)))
                 ((cons (member let let*))
                  (unless rewrite
                    (return-from walker form))
                  (let* ((body (member 'declare (cddr form)
                                       :key (lambda (x) (when (consp x) (car x))) :test-not #'eql))
                         (declares (ldiff (cddr form) body))
                         (rewritten (sb-walker:walk-form
                                     `(without-rewriting
                                          (,(car form) ,(cadr form)
                                            ,@declares
                                            (with-rewriting
                                                ,@body)))
                                     env #'walker)))
                    (values rewritten t)))
                 (t
                  (unless rewrite
                    (return-from walker form))
                  (if (find-$ form env)
                      (values `(setq $ ,form) t)
                      (values `(setq $ ,(list* (car form) '$ (cdr form))) t))))))
      `(let (($ ,(car forms)))
         ,@(mapcar (lambda (f) (sb-walker:walk-form f nil #'walker)) (cdr forms))))))

Here, find-$ is unchanged from the previous version; all the new functionality is in walker. How does it work? The default branch of the walker function is also unchanged; what has changed is handling of let and let* forms. The main trick is to communicate information between successive calls to the walker function, and turn the rewriting on and off appropriately: we wrap parts of the form in new pseudo-special operators with-rewriting and without-rewriting, which is basically a tacky and restricted implementation of compiler-let - if we needed to, we could do a proper one with macrolet. Within the scope of a without-rewriting, walker doesn't do anything special, but merely return the form it was given, except if the form it's given is a with-rewriting form. This is a nice illustration, incidentally, of the idea that lexical scope in the code translates nicely to dynamic scope in the compiler; I can't remember where I read that first (but it's certainly not a new idea).

And now

(macroexpand '(-> 3 (let ((*random-state* (make-random-state))) rnorm) mean))
; => (LET (($ 3))
;      (LET ((*RANDOM-STATE* (MAKE-RANDOM-STATE)))
;        (SETQ $ (RNORM $)))
;      (SETQ $ (MEAN $))),
;    T
(macroexpand '(-> 3 (let ((y (1+ $))) (atan y))))
; => (LET (($ 3))
;      (LET ((Y (1+ $)))
;        (SETQ $ (ATAN $ Y)))),
;    T

Just to be clear: this post isn't advocating a smarter pipe operator; I don't have a clear enough view, but I doubt that the benefits of the smartness outweigh the complexity. It is demonstrating what can be done, in a reasonably controlled way, using a code-walker: ascribing semantics to fragments of Common Lisp code, and combining those fragments in a particular way, and of course it's another example of sb-walker:walk in use.

Finally, if something like this does in fact get used, people sometimes get tripped up by the package system: the special bits of syntax are symbols, and importing or package-qualifying -> without doing the corresponding thing to $ would lead to cryptic errors, wrong results and/or confusion. One possibility to handle that is to invent a bit more reader syntax:

(set-macro-character #\¦
 (defun pipe-reader (stream char)
   (let ((*readtable* (copy-readtable)))
     (set-macro-character #\·
      (lambda (stream char)
        (declare (ignore stream char))
        '$) t)
   (cons '-> (read-delimited-list char stream t)))) nil)
¦"THREE" string-downcase (find-if #'alpha-char-p ·) char-code¦

If this is the exported syntax, it has the advantage that the interface can only be misused intentionally: the actual macro and its anaphoric symbol are both hidden from the programmer; and the syntax is reasonably easy to type - on my keyboard ¦ is AltGr+| and · is AltGr+. - and moderately mnemonic from shell pipes and function notation respectively. It also has all the usual disadvantages of reader-based interfaces, such as composability, somewhat mitigated if pipe-reader is part of the macro's exported interface.

Gábor MelisMigration to github

· 29 days ago

Due to the bash security hole that keeps giving, I had to disable gitweb at http://quotenil.com/git/ and move all non-obsolete code over to github. This affects Six the Hex AI, the Planet Wars bot, MiCMaC, FSVD, Lassie and cl-libsvm.

drmeisterBinding C++ to Clasp

· 30 days ago

This document borrows heavily from the luabind documentation. http://luabind.sourceforge.net/docs.html#intro

Clbind is a C++ template library that helps you create bindings between C++ and Clasp Common Lisp. It is very different from a typical FFI (foreign function interfaces) libraries. It allows you to expose functions, classes, methods, enums and other C++ features to Clasp. Clbind also provides the functionality to create classes in Common Lisp that subclass C++ classes and add CLOS slots to those derived classes. Common Lisp functions can override C++ methods.

Clbind is implemented using C++ template meta programming. It is heavily inspired by boost::python and luabind, two other C++ template libraries that provide interoperation between C++ and Python and Lua respectively. Clbind doesn’t require you to run extra preprocessing passes to compile your project (all of the work is done by the C++ compiler). Clbind doesn’t require you to know the exact signature of each function that you register because the C++ template library will determine this information at compile time.

Clbind closely follows the API used by luabind. I will more fully describe the Clbind API in the coming weeks.

For examples of how Clbind is used see:  clasp/src/asttooling/astExpose.cc::initialize_astExpose()  or clasp/src/asttooling/clangTooling.cc::initialize_clangTooling()

in the Clasp source code.


Joe MarshallA couple more homographic function tricks

· 31 days ago
A generalized continued fraction is an expression of the form:
You can partly apply a homographic function to a generalized continued fraction if you have a stream of the ai and bi
(define (partly-apply-general hf nums dens)
  (let ((a (first  hf))
        (b (second hf))
        (c (third  hf))
        (d (fourth hf)))
    (if (empty-stream? nums)
        (values (list a a
                      c c)
                nums
                dens)
        (let ((num (head nums))
              (den (head dens)))
          (values (list (+ (* a den) (* b num)) a
                        (+ (* c den) (* d num)) c)
                  (tail nums)
                  (tail dens))))))

(define (print-hf-general hf nums dens)
  (call-with-values (lambda () (partly-evaluate hf))
    (lambda (term hf*)
      (if (not term)
          (call-with-values (lambda () (partly-apply-general hf nums dens))
            print-hf-general)
          (begin
            (display term) 
            ;; take reciprocal and multiply by 10
            (let ((a (first hf*))
                  (b (second hf*))
                  (c (third hf*))
                  (d (fourth hf*)))
              (print-hf-general (list (* c 10) (* d 10)
                                      a        b)
                           nums dens)))))))
For example, we can compute pi from this generalized continued fraction:
(print-hf-general (list 0 4 1 0)
              ;; [1 1 4 9 16 25 ...]
       (cons-stream 1
      (let squares ((i 1))
    (cons-stream (* i i) (squares (1+ i)))))
              ;; [1 3 5 7 9 11 ...]
       (let odds ((j 1)) 
     (cons-stream j (odds (+ j 2)))))

314159265358979323846264338327950^G
; Quit!
A bi-homographic function is a function of the form:
(define (bi-homographic a b c d e f g h)
  (lambda (x y)
    (/ (+ (* a x y) (* b x) (* c y) d)
       (+ (* e x y) (* f x) (* g y) h))))
Like a homographic function, you can partly evaluate a bi-homographic function and generate a continued fraction. You can also partly apply a bi-homographic function to a pair of continued fractions. When you do this, you have a choice of which continued fraction to be the object of the partial application. There's about twice as much nasty math involved, but the gist is that a bi-homographic function takes two continued fractions as arguments and produces one continued fraction as a result.

It turns out that addition, subtraction, multiplication and division are bi-homographic functions, so one can incrementally compute sums and products of continued fractions.

Gábor MelisHiggs Boson Machine Learning Challenge Bits and Pieces

· 31 days ago

The Higgs Boson contest on Kaggle has ended. Sticking to my word at ELS 2014, I released some code that came about during these long four months.

MGL-GPR is no longer a Genetic Programming only library because it got another Evolutionary Algorithm implementation: Differential Evolution. My original plan for this contest was to breed input features that the physicists in their insistence on comprehensibility overlooked, but it didn't work as well as I had hoped for reasons specific to this contest and also because evolutionary algorithms just do not scale to larger problem sizes.

In other news, MGL got cross-validation, bagging and stratification support in the brand new MGL-RESAMPLE package documented with MGL-PAX which all of you will most definitely want to use. My winning submission used bagged cross-validated dropout neural networks with stratified splits so this is where it's coming from.

MGL itself and MGL-MAT were updated to work with the latest CL-CUDA. The neural network code also saw some additions such as ->MAX-CHANNEL activation (which originated as LWTA) and also gaussian multiplicative noise. The next steps here are further cleanups to MGL, writing documentation and moving it to github. Also, there is some hope that one day CL-CUDA can be included in quicklisp allowing my stuff there to be updated to their latest versions.

The code for this contest is available at higgsml which from now on doubles as my skeleton for lisp projects that need to be delivered as source and as binary. It sucks in all dependencies from quicklisp available at a certain date, clones the necessary repositories not available in quicklisp, builds an executable, and has a simple 'make dist' rule as well.

There is also a fairly generic ensembling algorithm that I will factor out of the code later.

common-lisp.net newsServer migration completed

· 31 days ago

Thanks to the hard work of everyone in the team we have successfully (it seems) migrated common-lisp.net to a new machine.

While a lot of care went into ensuring that all services could be preserved, it is quite unlikely that we didn’t miss something. Please let us know if you find something that used to work but doesn’t anymore by writing to clo-devel(at)common-lisp.net.

Brit ButlerBig Changes for Coleslaw

· 32 days ago

I'm working towards 1.0 and Coleslaw's basic architecture seems to have settled down. The areas of focus for 1.0 will be better error handling, command-line conveniences, more content types, and possibly some new ways to ingest data.

Coleslaw 0.9.6 will be released this Saturday and, not long after, make it into the next quicklisp release. Seeing as it contains big changes, some of them breaking, I thought I'd put out an announcement.

Coleslaw 0.9.6

Coleslaw 0.9.6 unifies how we handles URLs throughout the application and simplifies the deploy strategy. The good news is, this makes the install process easier for new users. The bad news is, if you've got an existing install, you'll need to add a new plugin (versioned) to your config file for the old deploy behavior.

That's not so rough, right? In addition, custom themes and plugins that haven't been upstreamed may need some minor tweaks. The NEWS has more details.

Feel free to grab the basic-deploy branch from my repo and try it out. There are some new docs and the README has been cleaned up. There's also a plugin for Twitter Summary Card support and the usual smattering of bugfixes.

Going Forward

While I'm happy to maintain Coleslaw if no one else steps up to work on it, I'm going to try and shift my focus towards emulation work and weird lisp noodling. If you're interested in taking on a co-maintainer role or working with me on the project please get in touch. I've been very appreciative of the help and interest thus far. If there's anything I can do to make the project more approachable or help people get started, do let me know.

common-lisp.net newsServer migration on monday (2014.09.22) at 11:00 am CET

· 34 days ago

We will migrate the site to a newer, more powerful machine with an up-to-date Debian stable on monday, at 11:00 am CET. Quite a bit of work has gone into preparations to ensure that the disruption will be as brief as possible (hopefully less than an hour, plus the DNS propagation lag)

All services will continue to be available in their current form. By monday afternoon, the big difference will be a shiny new website with new content, as well as a more responsive experience.

The move to a new server marks the beginning of a new era for the site. You can read some background on the migration here.

Joe MarshallA useful, if somewhat pointless, trick with homographic functions

· 35 days ago
In my previous posts I showed that if you are applying a homographic function to a continued fraction, you can partly evaluate the answer before you completely apply the function. Instead of representing homographic functions as lambda expressions, I'll represent them as a list of the coefficients a, b, c, and d in (lambda (t) (/ (+ (* a t) b) (+ (* c t) d))). I'll represent a simple continued fraction as a stream of the integer terms in the denominators.
Here is how you partly apply a homographic function to a continued fraction:
(define (partly-apply hf cf)
  (let ((a (first  hf))
        (b (second hf))
        (c (third  hf))
        (d (fourth hf)))
    (if (empty-stream? cf)
        (values (list a a
                      c c)
                cf)
        (let ((term (head cf)))
          (values (list (+ (* a term) b) a
                        (+ (* c term) d) c)
                  (tail cf))))))
Partly evaluating a homographic function involves looking at the limits of the function as t starts at 1 and goes to infinity:
(define (partly-evaluate hf)
  (let ((a (first hf))
        (b (second hf))
        (c (third hf))
        (d (fourth hf)))

    (if (and (same-sign? c (+ c d))
             (let ((limit1 (quotient      a       c))
                   (limit2 (quotient (+ a b) (+ c d))))
               (= limit1 limit2)))
        (let ((term (quotient a c)))
          (let ((new-c (- a (* c term)))
                (new-d (- b (* d term))))
            (values term (list c d new-c new-d))))
        (values #f #f))))
We can combine these two steps and make something useful. For example, we can print the value of applying a homographic function to a continued fraction incrementally, printing the most significant digits before computing further digits.
(define (print-hf-cf hf cf)
  (call-with-values (lambda () (partly-evaluate hf))
    (lambda (term hf*)
      (if (not term)
          (call-with-values (lambda () (partly-apply hf cf))
            print-hf-cf)
          (begin
            (display term) 
            ;; take reciprocal and multiply by 10
            (let ((a (first hf*))
                  (b (second hf*))
                  (c (third hf*))
                  (d (fourth hf*)))
              (print-hf-cf (list (* c 10) (* d 10)
                                 a        b)
                           cf)))))))
But how often are you going to apply a homographic function to a continued fraction? Fortunately, the identity function is homographic (coefficients are 1 0 0 1), so applying it to a continued fraction doesn't change the value. The square root of 2 is a simple continued fraction with coefficients [1 2 2 2 ...] where the 2s repeat forever. We apply the identity homographic function to it and print the results:
(printcf (list 1 0 0 1) sqrt-two)
14142135623730950488016887242096980785696718^G
; Quit!
As you can see, we start printing the square root of two and we don't stop printing digits until the user interrupts.

A fancier version could truncate the output and print a decimal point after the first iteration.

drmeisterAnnouncing Clasp

· 36 days ago

Hello, everyone!

Click here for up to date build instructions

Today I am happy to make the first release of the Common Lisp implementation "Clasp". Clasp uses LLVM as its back-end and generates native code. Clasp is a super-set of Common Lisp that interoperates smoothly with C++. The goal is to integrate these two very different languages together as seamlessly as possible to provide the best of both worlds. The C++ interoperation allows Common Lisp programmers to easily expose powerful C++ libraries to Common Lisp and solve complex programming challenges using the expressive power of Common Lisp.  Clasp is licensed under the LGPL.

Common Lisp is considered by many to be one of the most expressive programming languages in existence. Individuals and small teams of programmers have created fantastic applications and operating systems within Common Lisp that require much larger effort when written in other languages. Common Lisp has many language features that have not yet made it into the C++ standard. Common Lisp has first-class functions, dynamic variables, true macros for meta-programming, generic functions, multiple return values, first-class symbols, exact arithmetic, conditions and restarts, optional type declarations, a programmable reader, a programmable printer and a configurable compiler. Common Lisp is the ultimate programmable programming language.

Clasp has several features that make it unique and of interest to the wider programming community.

This is a “very alpha” release — it’s not fully tested. Clasp compiles and runs itself and its garbage collection static-analyzer. Clasp is not yet a complete Common Lisp - about 10% of the standard 978 Common Lisp symbols are not yet implemented. A faster Clasp compiler is coming soon – the current Clasp compiler generates slow native code that is about 100x slower than highly tuned Common Lisp compilers like Steel Bank Common Lisp. Currently Clasp builds on OS X 10.9 and Linux.

The Clasp project is actively looking for developers who want to contribute to this exciting open-source project. Future enhancements include - achieving full Common Lisp standard compliance, direct incorporation of C++ code within Common Lisp, a port to Windows, multi-threading (Clasp is single threaded at the moment) and incorporation of a new compiler (under development) that makes many language level optimizations. Our goal is to make Clasp the fastest and most capable dynamic scripting language for C++ libraries.

with best regards, Christian Schafmeister.

Links:

Link to Clasp github repository

Link to llvm.org

Link to ECL – Embedded Common Lisp

Link to Ravenbrook (MPS compacting garbage collector)

A Youtube video that I made that shows of Clasp C++ AST searching/refactoring


Zach BeaneCommon Lisp bits

· 36 days ago
Heinrich Apfelmus has updated to the source code from Computer Models of Musical Creativity and put it on github. Looks like it's meant to work with RMCL.

"CEPL is an extension for common lisp that makes working with OpenGL simple and familiar," according to Baggers. There is a blog and a number of videos about CEPL. The readme cautions: PRE-ALPHA.

"BG" gives a take on the history of Macintosh Common Lisp. Rainer Joswig responded to a number of points in the ensuing /r/lisp discussion.

3bgl-shader is "a Common Lisp DSL for generating GLSL shaders," by Bart Botta. Needs people to try it out and provide feedback.

Pseudo is a Lisp-powered roguelike multiplayer browser game, with AGPLv3-licensed source code available. Created by Matthew Carter.

The Infected is a roguelke survival horror game in Common Lisp, by Jan Tatham.

Mariano Montone writes about embedding Python syntax (and functionality) in Common Lisp sources.

Quicklisp newsSeptember 2014 Quicklisp dist update now available

· 39 days ago
New projects:
Updated projects: bknr-datastore, caveman, cl-ana, cl-async, cl-conspack, cl-css, cl-gendoc, cl-gss, cl-inflector, cl-oauth, cl-olefs, cl-quickcheck, cl-redis, cl-sdl2, cl-tld, clip, closer-mop, coleslaw, colleen, crane, crypto-shortcuts, function-cache, gbbopen, hermetic, hu.dwim.walker, let-over-lambda, lisp-unit2, lquery, mel-base, mexpr, mgl-pax, modularize, modularize-hooks, modularize-interfaces, mpc, open-vrp, pgloader, plump, policy-cond, protobuf, qmynd, repl-utilities, restas, scriptl, shelly, smug, software-evolution, south, staple, stumpwm, trivial-mimes, weblocks-tree-widget.

To get this update, use (ql:update-dist "quicklisp").

Just as a friendly reminder, Quickdocs is a great way to find libraries in Quicklisp. I don't run the site and it's not an official part of Quicklisp, it's just a great project that uses Quicklisp's metadata to build a really useful service. So check it out!

Timofei ShatrovWho needs graph theory anyway?

· 39 days ago

In my last post I discussed how to make a Japanese->English transliterator and outlined some problems that limited its usefulness. One problem is that there’s no obvious way to segment a sentence into words. I looked up existing solutions, and a lightweight Javascript implementation caught my eye. I quickly ported it to Common Lisp and to the surprise of absolutely no one, the results were awful

It was clear that I needed an actual database of Japanese words to do segmentation properly. This would also solve the “kanji problem” since this database would also include how to pronounce the words. My first hunch was Wiktionary, but it’s dump format turned out to be pretty inefficient for parsing.

Fortunately I quickly discovered a free JMDict database which was exactly what I needed. It even had open-source code in Python for parsing and loading its XML dumps. Naturally, I wrote my own code to parse it since its database schema looked too complex for my needs. But I’m not going to discuss that in this post, as it is quite boring.

Since now I had a comprehensive Postgres database of every word in Japanese language (not really, as it doesn’t include conjugations) it was only a matter of identifying the words in the sentence. To do this, for every substring of a sentence look up the database for exact matches. There are n(n+1)/2 substrings in a string, so we aren’t doing too badly in terms of performance (and the string wouldn’t be too long anyway since prior to running this procedure I’ll be splitting it by punctuation etc.)

(defstruct segment
  start end word))

(defun find-substring-words (str)
  (loop for start from 0 below (length str)
       nconcing 
       (loop for end from (1+ start) upto (length str)
          for substr = (subseq str start end)
            nconcing (mapcar 
                      (lambda (word)
                        (make-segment :start start :end end :word word))
                      (find-word substr)))))

The problem is that there’s a lot of words, and many of them are spelled identically. I decided to assign a score to each word based on its length (longer is better), whether it’s a preferred spelling of the word, how common the word is and whether it’s a particle (which tend to be short and thus need a boost to increase their prominence).

Now we have the following problem: for a sentence, find the set of non-intersecting segments with the maximum total score. Now, you might have better mathematical intuition than I, but my first thought was:

This looks NP-hard, man. This problem has “travelling salesman" written all over it.

My first attempt to crack it was to calculate score per letter for each word and select words with the highest scores. But a counterexample comes to mind rather easily: in a sentence “ABC” with words “AB” (score=5), “BC” (score=5) and “ABC” (score=6), words “AB” and “BC” have a higher score per letter (2.5), but the optimal covering is provided by the word “ABC” with its score per letter a measly 2.

At this point I was working with the most convenient mathematical instrument, which is pen and paper. The breakthrough came when I started to consider a certain relation between two segments: the segment a can be followed by the segment iff (segment-start b) is greater or equal to (segment-end a). Under this relation our segments form transitive directed acyclic graph. The proof is left as an exercise for the reader. Clearly we just need to do a transitive reduction and use something similar to Dijkstra’s algorithm to find the path with the maximal score! This problem is clearly solvable in polynomial time!

Pictured: actual notes drawn by me

image

In reality the algorithm turns out to be quite simple. Since find-substring-words always returns segments sorted by their start and then by their end, every segment can only be followed by the segments after it. We can then accumulate the largest total score and the path used for it for every segment by using a nested loop:

(defstruct segment
  start end word (score nil) (accum 0) (path nil))

(defun find-best-path (segments)
  ;;assume segments are sorted by (start, end) (as is the result of find-substring-words)
  (let ((best-accum 0)
        (best-path nil))
    (loop for (seg1 . rest) on segments
       when (> (segment-score seg1) (segment-accum seg1))
         do (setf (segment-accum seg1) (segment-score seg1)
                  (segment-path seg1) (list seg1))
            (when (> (segment-accum seg1) best-accum)
              (setf best-accum (segment-accum seg1)
                    best-path (segment-path seg1)))
       when (> (segment-score seg1) 0)
         do (loop for seg2 in rest
               if (>= (segment-start seg2) (segment-end seg1))
               do (let ((accum (+ (segment-accum seg1) (segment-score seg2))))
                    (when (> accum (segment-accum seg2))
                      (setf (segment-accum seg2) accum
                            (segment-path seg2) (cons seg2 (segment-path seg1)))
                      (when (> accum best-accum)
                        (setf best-accum accum
                              best-path (segment-path seg2)))))))
    (values (nreverse best-path) best-accum)))

Of course when I actually tried to run this algorithm, SBCL just crashed. How could that be? It took me a while to figure out, but notice how segment-path contains a list that includes the segment itself. A recursive self-referential structure! When SBCL tried to print that in the REPL, it didn’t result in dragons flying out of my nose but a crash still happened. Interestingly, Common Lisp has a solution to this: if *print-circle* is set to t, it will actually print the structure using referential tokens. Anyway, I just added the following before returning the result to remove self-references:

    (dolist (segment segments)
      (setf (segment-path segment) nil))

So, did it work? Yes, it did, and the result was impressive! Even though my scoring system is pretty barebones, it’s on par or even better than Google Translate’s romanization on a few test sentences I tried. I still need to add conjugations, and it can’t do personal names at all, but considering how little code there is and the fact that it doesn’t even attempt grammatical analysis of the sentence (due to me not knowing the language) I am very happy with the result. Also I plan to add a web interface to it so that it’s possible to hover over words and see the translation. That would be pretty useful. The work in progress code is on my Github.

Paul KhuongDoodle: Hybridising SBCL's GENCGC With Mark and Sweep

· 40 days ago

Meta-note: this is more of a journal entry than the usual post here. I’ll experiment with the format and see if I like publishing such literal and figurative doodles.

Garbage collection is in the air. My friend Maxime is having issues with D’s garbage collector, and Martin Cracauer has a large patch to improve SBCL’s handling of conservative references. I started reviewing that patch today, and, after some discussion with Alastair Bridgewater, I feel like adding a mark-and-sweep component to SBCL’s GC might be easier than what the patch does, while achieving its goal of reducing the impact of conservative references. That lead to the whiteboarding episode below and a plan to replace the garbage collecting half of SBCL’s generational GC. But first, a summary of the current implementation.

The present, and how we got here

CMUCL started out with a Cheney-style two-space collector. Two-space collectors free up space for more allocations by copying objects that might still be useful (that are reachable from “roots,” e.g., variables on the stack) from the old space to the new space. Cheney’s algorithm elegantly simplifies this task by storing bookkeeping information in the data itself. When we copy an object to the new space (because it is reachable), we want to make sure that all other references to that object are also replaced with references to the copy. Cheney’s solution to that desideratum is obvious: overwrite the old object with a broken heart (forwarding pointer), a marker that

  1. the object has already been copied to the new space;
  2. the copy lives at address x.

This adds a constraint that heap-allocated objects can never be smaller than a broken heart, but they’re usually one or two words (two in SBCL’s case) so the constraint is rarely binding.

When the garbage collector traverses the roots (the stack, for example) and finds a pointer, the code only has to dereference that pointer to determine if the objects it points to has been moved. If so, the GC replaces the root pointer with a pointer to the copy in the new space. Otherwise, the GC copies the object to the new space, repoints to that copy, and overwrites the old object with a broken heart.

We also need to traverse objects recursively: when we find that an object is live and copy it to the new space, we must also make sure that anything that objects points to is also preserved, and that any pointer in that object is updated with pointers to copies in the new space.

That’s a graph traversal, and the obvious implementation maintains a workset of objects to visit which, in the worst case, could include all the objects in old space. The good news is we don’t have to worry about objects re-entering that workset: we always overwrite objects (in old space) with a broken heart when we visit them for the first time.

Cheney proposed a clever trick to implement this workset. Whenever an object enters the workset, it has just been copied to the new space; as long as we allocate in the new space by incrementing an allocation pointer, the new space itself can serve as the workset! In addition to the allocation pointer, we now need a “to-scan” pointer. Any object in the new space that’s below the to-scan pointer has already been scanned for pointers and fixed to point in the new space; any object between the to-scan pointer and the allocation pointer must be scanned for pointers to the old space. We pop an element from the workset by looking at the next object (in terms of address) after the to-scan pointer and incrementing that pointer by the object’s size. When the to-scan and the allocation pointers meet, the workset is empty and GC terminates.

Some SBCL platforms still use this two-space collector, but it doesn’t scale very well to large heaps (throughput is usually fine, but we waste a lot of space and GC pauses can be long). The generational conservative garbage collector (GENCGC, GENGC on precise/non-conservative platforms) is a hack on top of that Cheney GC.

The GC is “generational” because most passes only collect garbage from a small fraction of the heap, and “conservative” because we have to deal with values that may or may not be pointers (e.g., we don’t always know if the value in a register is a Lisp reference or just a machine integer) by considering some objects as live (not up for collection) while pinning them at their current address.

The runtime uses mprotect to record writes to the heap, except for the nursery (newly allocated objects) where we expect most writes to land. The heap is partitioned in pages, and the first write to a page after a GC triggers a protection fault; the signal handler marks that page as mutated and changes the protection to allow writes.

When a GC is triggered, we usually want to collect only the nursery, i.e., only objects that were allocated after the previous GC pass. GEN(C)GC adapts Cheney to this use case by building the set of all pages that might have been mutated to point somewhere in the nursery (thanks to the mprotect write barrier) and scanning them for roots, like the stack in Cheney GC. The default GENGC configuration has 7 generations and we extend this scheme by flagging pages with pointers to younger generations (newer objects), without noting what these generations might be.

Pinned objects are also handled by abusing the root set: pages that contain at least one pinned object don’t undergo garbage collection and are directly scanned for pointers, like the stack in Cheney GC.

Instead of having two heaps, an old space and a new space, we now have a lot of pages, and each page belongs to a generation. When we want to collect a given generation, pages in that generation form the old space, and pages allocated during GC the new space. This means that we lose the simplicity of Cheney’s new-space-is-the-workset trick: the new space isn’t contiguous, so a single to-scan pointer doesn’t cut it anymore! GENGC works around that by scanning the page table, but it’s not pretty and I really don’t know if Cheney is a good fit anymore.

Martin Cracauer’s patch

GENCGC’s approach to pinned objects is stupid. If a page has no reference except for one conservative pointer, the whole page is considered live and scanned for references.

Martin’s solution is to allocate additional temporary metadata only for pinned pages and track the pinned status of individual objects. When the GC encounters a pointer to a page with pinned objects, it checks if it’s a pointer to a pinned object. If so, the pointee is left in place. Otherwise, it’s copied normally.

The patch has code to mark objects as live (pinned) and to overwrite objects once they have been copied. Basically, it is half of a mark-and-sweep garbage collector. The main difference is that the set of pinned objects doesn’t grow (being pinned isn’t a contagious property), so we don’t need a worklist for pinned objects. However, I already noted that I’m not convinced the worklist hack in GENGC is a good idea.

A hybrid collector!

Instead of marking pages as containing pinned objects, I feel it may be simpler to collect some pages by copying, and others by marking. Any pinned page would have the “mark” GC policy, while pages that likely contain few live objects (e.g., the nursery and pages with a lot of unused memory) would be collected by copying. This too would avoid the issue with considering whole pages as live when pinned, and I think that having the choice of copying or marking at a page granularity will be simpler than toggling at the level of individual object.

Each “mark” page now has two (bit)sets, one for live objects and another for live objects that have already been scanned. We can maintain a worklist at the page granularity with an embedded linked list: whenever a “mark” page gains a new live object and it’s not already in the worklist, that page is enqueued for scanning.

Instead of emulating Cheney’s trick by looking for newly allocated pages in our page table, we can add pages in new space to the worklist whenever they become full.

Finally, at the end of the pass, we traverse all “mark” pages and clear dead objects.

That’s pretty simple (arguably simpler than the current implementation!), and shouldn’t involve too many changes to the rest of the code. Mostly, I’d have to adapt the weak pointer machinery to stop assuming that it can use forwarding pointers to determine when objects have been marked as live.

However, we might lose the ability to run medium GCs, to collect more than the nursery but less than the whole heap. If we only want to GC the nursery, the mprotect write barrier gives us all the information we need to find references from the rest of the heap to the nursery. If we wish to collect the whole heap, we only have to consider stacks and some statically allocated space as roots.

For medium GCs, e.g., collect only generations 1-4 out of 7, GENGC exploits the way that garbage collection (almost) always copies to easily track pages with pointers to younger generations. It’s coarse, but usually acceptable thanks to the copying. I don’t know that it would work as well if the default is to only copy the nursery. Moreover, if we have a hybrid GC, it probably makes sense to focus copying on pages that are mostly empty, regardless of their age. If we do want medium GCs, we might have to track, for each page, the set of pages that point there. This set can include false positives, so it’s probably easiest to clear it before major GCs, and otherwise only add to that set (removing pages that were emptied by a GC pass sounds reasonable). I also expect that some pages will have many refererrers; I’m thinking we might use a distinguished value to mean “referred by every pages” and not consider them for medium GC.

What’s next

Martin’s patch clearly addresses an important weakness in SBCL’s garbage collector. If I can’t make good progress on the hybrid GC soon, I’ll make sure the patch is cleaned up for master, hopefully by Thanksgiving.

Clozure CL BlogClozure CL 1.10 is available

· 41 days ago

Clozure CL 1.10 is now available.  See http://ccl.clozure.com/download.html for instructions on how to get it.

Christophe Rhodesnaive vs proper code-walking

· 45 days ago

I said in my discussion about backquote representations that some utilities had defects made manifest by SBCL 1.2.2's new internal representation for backquote and related operators, and that those defects could have been avoided by using a code-walker. I'm going to look at let-over-lambda code here, to try to demonstrate what I meant by that, and show how a proper code-walker can quite straightforwardly be used for the code transformations that have been implemented using a naïve walker (typically walking over a tree of conses), removing whole classes of defects in the process.

The let-over-lambda code I'm discussing is from https://github.com/thephoeron/let-over-lambda, specifically this version. This isn't intended to be a hatchet job on the utility - clearly, it is of use to its users - but to show up potential problems and offer solutions for how to fix them. I should also state up front that I haven't read the Let over Lambda book, but it's entirely possible that discussing and using a full code-walker would have been out of scope (as it explicitly was for On Lisp).

Firstly, let's deal with how the maintainer of the let-over-lambda code is dealing with the change in backquote representations, since it's still topical:

;; package definition here just in case someone decides to paste
;; things into a Lisp session, and for private namespacing
(defpackage "LOL" (:use "CL"))
(in-package "LOL")
;; actual excerpts from let-over-lambda code from
;; <https://github.com/thephoeron/let-over-lambda/blob/a202167629cb421cbc2139cfce1db22a84278f9f/let-over-lambda.lisp>
;; begins here:
#+sbcl
(if (string-lessp (lisp-implementation-version) "1.2.2")
    (pushnew :safe-sbcl *features*)
    (setq *features* (remove :safe-sbcl *features*)))
(defun flatten (x)
  (labels ((rec (x acc)
             (cond ((null x) acc)
                   #+(and sbcl (not safe-sbcl))
                   ((typep x 'sb-impl::comma) (rec (sb-impl::comma-expr x) acc))
                   ((atom x) (cons x acc))
                   (t (rec (car x) (rec (cdr x) acc))))))
    (rec x nil)))

The issues around the (*features*) handling here have been reported at github; for the purpose of this blog entry, I will just say that I wrote about them in Maintaining Portable Lisp Programs, a long time ago, and that a better version might look a bit like this:

#+sbcl
(eval-when (:compile-toplevel :execute)
  (defun comma-implementation ()
    (typecase '`,x
      (symbol 'old)
      ((cons symbol (cons structure-object)) 'new)))
  (if (eql (comma-implementation) 'old)
      (pushnew 'cons-walkable-backquote *features*)
      (setq *features* (remove 'cons-walkable-backquote *features*))))
(defun flatten (x)
  (labels ((rec (x acc)
             (cond ((null x) acc)
                   #+lol::cons-walkable-backquote
                   ((typep x 'sb-impl::comma) (rec (sb-impl::comma-expr x) acc))
                   ((atom x) (cons x acc))
                   (t (rec (car x) (rec (cdr x) acc))))))
    (rec x nil)))

With these changes, the code is (relatively) robustly testing for the particular feature it needs to know about at the time that it needs to know, and recording it in a way that doesn't risk confusion or contention with any other body of code. What is the let-over-lambda library using flatten for?

(defun g!-symbol-p (thing)
  (and (symbolp thing)
       (eql (mismatch (symbol-name thing) "G!") 2)))
(defmacro defmacro/g! (name args &rest body)
  (let ((syms (remove-duplicates
               (remove-if-not #'g!-symbol-p (flatten body)))))
    `(defmacro ,name ,args
       (let ,(mapcar
              (lambda (s)
                `(,s (gensym ,(subseq (symbol-name s) 2))))
              syms)
         ,@body))))

The intent behind this macro-defining macro, defmacro/g!, appears to be automatic gensym generation: being able to write

(defmacro/g! with-foo ((foo) &body body)
  `(let ((,g!foo (activate-foo ,foo)))
     (unwind-protect
         (progn ,@body)
       (deactivate-foo ,g!foo))))

without any explicit calls to gensym but retaining the protection that gensyms give against name capture:

(macroexpand-1 '(with-foo (3) 4))
; => (let ((#1=#:FOO1 (activate-foo 3)))
;      (unwind-protect
;          (progn 4)
;        (deactivate-foo #1#)))

That's fine; it's reasonable to want something like this. Are there any issues with this, apart from the one exposed by SBCL's new backquote implementation? In its conventional use, probably not - essentially, all uses of g! symbols are unquoted (i.e. behind commas) - but there are a couple of more theoretical points. One issue is that flatten as it currently stands will look for all symbols beginning with g! in the macroexpander function source, whether or not they are actually variable evaluations:

(defmacro/g! with-bar ((bar) &body body)
  `(block g!block
     (let ((,g!bar ,bar)) ,@body)))
; unused variable G!BLOCK
(macroexpand-1 '(with-bar (3) 4))
; => (block g!block (let ((#:BAR1 3)) 4))

In this example, that's fair enough: it's probably user error to have those g! symbols not be unquoted; this probably only becomes a real problem if there are macro-defining macros, with both the definer and the definition using g! symbols. It's not totally straightforward to demonstrate other problems with this simple approach to Lisp code transformation using just this macro; the transformation is sufficiently minimal, and the symptoms of problems relatively innocuous, that existing programming conventions are strong enough to prevent anything seriously untoward going wrong.

Before getting on to another example where the problems with this approach become more apparent, how could this transformation be done properly? By "properly" here I mean that the defmacro/g! should arrange to bind gensyms only for those g! symbols which are to be evaluated by the macroexpander, and not for those which are used for any other purpose. This is a task for a code-walker: a piece of code which exploits the fact that Lisp code is made up of Lisp data structures, all of which are introspectable, and the semantics of which in terms of effect on environment and execution are known. It is tedious, though possible, to write a mostly-portable code-walker (there needs to be some hook into the implementation's representation of environments); I'm not going to do that here, but instead will use SBCL's built-in code-walker.

The sb-walker:walk-form function takes three arguments: a form to walk, an initial environment to walk it in, and a walker function to perform whatever action is necessary on the walk. That walker function itself takes three arguments, a form, context and environment, and the walker arranges for it to be called on every macroexpanded or evaluated subform in the original form. The walker function should return a replacement form for the subform it is given (or the subform itself if it doesn't want to take any action), and a secondary value of t if no further walking of that form should take place.

To do g! symbol detection and binding is fairly straightforward. If a symbol is in a context for evaluation, we collect it, and here we can take the first benefit from a proper code walk: we only collect g! symbols if the code-walker deems that they will be evaluated and there isn't an already-existing lexical binding for it:

(defmacro defmacro/g!-walked (name args &body body)
  (let* (g!symbols)
    (flet ((g!-walker (subform context env)
             (declare (ignore context))
             (typecase subform
               (symbol
                (when (and (g!-symbol-p subform)
                           (not (sb-walker:var-lexical-p subform env)))
                  (pushnew subform g!symbols))
                subform)
               (t subform))))
      (sb-walker:walk-form `(progn ,@body) nil #'g!-walker)
      `(defmacro ,name ,args
         (let ,(mapcar (lambda (s) (list s `(gensym ,(subseq (symbol-name s) 2))))
                       g!symbols)
           ,@body)))))

The fact that we only collect symbols which will be evaluated deals with the problem exhibited by with-bar, above:

(defmacro/g!-walked with-bar/walked ((bar) &body body)
  `(block g!block
     (let ((,g!bar ,bar)) ,@body)))
(macroexpand-1 '(with-bar/walked (3) 4))
; => (block g!block (let ((#:BAR1 3)) 4))

Only gathering symbols which don't have lexical bindings (testing sb-walker:var-lexical-p) deals with another minor problem:

(defmacro/g!-walked with-baz ((baz) &body body)
  (let ((g!sym 'sym))
    `(let ((,g!sym ,baz)) ,@body)))
(macroexpand-1 '(with-baz (3) 4))
; => (let ((sym 3)) 4)

(the cons-walker - flatten - would not be able to detect that there is already a binding for g!sym, and would introduce another one, again leading to an unused variable warning.)

OK, time to recap. So far, we've corrected the code that tests for particular backquote implementations, which was used in flatten, which itself was used to perform a code-walk; we've also seen some low-impact or theoretical problems with that simple code-walking technique, and have used a proper code-walker instead of flatten to deal with those problems. If the odd extra unused variable binding were the worst thing that could happen, there wouldn't be much benefit from using a code-walker (other than the assurance that the walker is dealing with forms for execution); however, let us now turn our attention to the other macro in let-over-lambda's code which does significant codewalking:

(defun dollar-symbol-p (thing)
  (and (symbolp thing)
       (char= (char (symbol-name thing) 0) #\$)
       (ignore-errors (parse-integer (subseq (symbol-name thing) 1)))))
(defun prune-if-match-bodies-from-sub-lexical-scope (tree)
  (if (consp tree)
      (if (or (eq (car tree) 'if-match)
              (eq (car tree) 'when-match))
          (cddr tree)
          (cons (prune-if-match-bodies-from-sub-lexical-scope (car tree))
                (prune-if-match-bodies-from-sub-lexical-scope (cdr tree))))
      tree))
;; WARNING: Not %100 correct. Removes forms like (... if-match ...) from the
;; sub-lexical scope even though this isn't an invocation of the macro.
#+cl-ppcre
(defmacro! if-match ((test str) conseq &optional altern)
  (let ((dollars (remove-duplicates
                  (remove-if-not #'dollar-symbol-p
                                 (flatten (prune-if-match-bodies-from-sub-lexical-scope conseq))))))
    (let ((top (or (car (sort (mapcar #'dollar-symbol-p dollars) #'>)) 0)))
      `(let ((,g!str ,str))
         (multiple-value-bind (,g!s ,g!e ,g!ms ,g!me) (,test ,g!str)
           (declare (ignorable ,g!e ,g!me))
           (if ,g!s
               (if (< (length ,g!ms) ,top)
                   (error "ifmatch: too few matches")
                   ;; lightly edited here to remove irrelevant use of #`
                   (let ,(mapcar (lambda (a1) `(,(symb "$" a1)
                                                (subseq ,g!str (aref ,g!ms ,(1- a1))
                                                               (aref ,g!me ,(1- a1)))))
                                 (loop for i from 1 to top collect i))
                     ,conseq))
               ,altern))))))
(defmacro when-match ((test str) conseq &rest more-conseq)
  `(if-match (,test ,str)
     (progn ,conseq ,@more-conseq)))

What's going on here? We have a prune-if-match-bodies-from-sub-lexical-scope function which, again, performs some kind of cons-based tree walk, removing some conses whose car is if-match or when-match. We have a trivial macro when-match which transforms into an if-match; the if-match macro is more involved. Any symbols named as a $ sign followed by an integer (in base 10) are treated specially; the intent is that they will be bound to capture groups of the cl-ppcre match. So it would be used in something like something like

(defun key-value (line)
  (if-match ((lambda (s) (scan "^\\(.*\\): \\(.*\\)$" s)) line)
      (list $1 $2)
      (error "not actually a key-value line: ~S" line)))

and that would macroexpand to, roughly,

(defun key-value (line)
  (multiple-value-bind (s e ms me)
      ((lambda (s) (scan "^\\(.*\\): \\(.*\\)$" s)) line)
    (if s
        (if (< (length ms) 2)
            (error "if-match: not enough matches)
            (let (($1 (subseq line (aref ms 0) (aref me 0)))
                  ($2 (subseq line (aref ms 1) (aref me 1))))
              (list $1 $2)))
        (error "not actually a key-value line: ~S" line))))

(there's additional reader macrology in let-over-lambda to make that lambda form unnecessary, but we can ignore that for our purposes).

Now, if-match has a similar problem that defmacro/g! had: since the tree walker doesn't make a distinction between symbols present for evaluation and symbols for any other purpose, it is possible to confuse the walker. For example:

(if-match (scanner string)
    (if (> (length $1) 6)
        '|$1000000|
        'less-than-$1000000))

This form, if macroexpanded, will attempt to bind one million variables to matched groups; even if the compiler doesn't choke on that, evaluation will go wrong, as the matcher is unlikely to match one million groups (so the "not enough matches" error branch will be taken) - whereas of course the quoted one million dollar symbol is not intended for evaluation.

But the nesting problems are more obvious in this case than for defmacro/g!. Firstly, take the simple case:

(if-match (scanner string)
    (list $1
          (if-match (scanner2 string)
              $2
              nil))
    nil)

Here, the $2 is in the scope of the inner if-match, and so mustn't be included for the macroexpansion of the outer if-match. This case is handled in let-over-lambda's implementation by the prune-if-match-bodies-from-sub-lexical-scope: the consequent of the inner if-match is pruned from the dollar-symbol accumulator. However, there are several issues with this; the first is that the test is pruned:

(if-match (scanner string)
    (if-match (scanner2 $2)
        $1
        nil)
    nil)

In this example, the $2 is 'invisible' to the outer if-match, and so won't get a binding. That's straightforwardly fixable, along with the mishandling of when-let's syntax (the entire body of when-let should be pruned, not just the first form), and what I think is an error in the pruning of if-match (it should recurse on the cdddr, not the cddr; github issue).

Not fixable at all while still using naïve code-walking are two other problems, one of which is noted in the comment present in the let-over-lambda code: the pruner doesn't distinguish between if-match forms for evaluation and other conses whose car is if-match. Triggering this problem does involve some contortions - in order for it to matter, we need an if-match not for evaluation followed by a dollar symbol which is to be evaluated; but, for example:

(defmacro list$/q (&rest args)
  `(list ,@(mapcar (lambda (x) (if (dollar-symbol-p x) x `',x)) args)))
(if-match (scanner string)
    (list$/q foo if-match $2)
    nil)

Here, although the $2 is in a position for evaluation (after macroexpansion), it will have no binding because it will have been pruned when naïvely walking the outer if-match macro. The if-match symbol argument to `list$/q ends up quoted, and should not be treated as a macro call.

Also, the pruner function must have special knowledge not just about the semantics of if-match, but also of any macro which can expand to if-match - see the attempt to handle when-match in the pruner. If a user were to have the temerity to define case-match

(defmacro case-match (string &rest clauses)
  (if (null clauses)
      nil
      `(if-match (,(caar clauses) ,string)
           (progn ,@(cdar clauses))
           (case-match string ,@(cdr clauses)))))

any attempt to nest a case-match inside an outer if-match is liable to fail, as the pruner has no knowledge of how to handle the case-match form.

All of these problems are solvable by using a proper code-walker. The code-walker should collect up all dollar symbols to be evaluated in the consequent of an if-match form, so that bindings for them can be generated, except for those with already existing lexical bindings within the if-match (not those from outside, otherwise nesting won't work). For testing purposes, we'll also signal a diagnostic condition within the macroexpander to indicate which dollar symbols we've found.

(define-condition if-match/walked-diagnostic (condition)
  ((symbols :initarg :symbols :reader if-match-symbols)))
(defmacro if-match/walked ((test string) consequent &optional alternative)
  (let* (dollar-symbols)
    (flet ((dollar-walker (subform context env)
             (declare (ignore context))
             (typecase subform
               (symbol
                (when (and (dollar-symbol-p subform)
                           (not (sb-walker:var-lexical-p subform env)))
                  (pushnew subform dollar-symbols))
                subform)
               (t subform))))
      (handler-bind ((if-match/walked-diagnostic #'continue))
        (sb-walker:walk-form consequent nil #'dollar-walker))
      (let* ((dollar-symbols (sort dollar-symbols #'> :key #'dollar-symbol-p))
             (top (dollar-symbol-p (car dollar-symbols))))
        (with-simple-restart (continue "Ignore diagnostic condition")
          (signal 'if-match/walked-diagnostic :symbols dollar-symbols))
        (sb-int:with-unique-names (start end match-start match-end)
          (sb-int:once-only ((string string))
            `(multiple-value-bind (,start ,end ,match-start ,match-end)
                 (,test ,string)
               (declare (ignore ,end) (ignorable ,match-end))
               (if ,start
                   (if (< (length ,match-start) ,top)
                       (error "~S: too few matches: needed ~D, got ~D." 'if-match
                              ,top (length ,match-start))
                       (let ,(mapcar (lambda (s)
                                       (let ((i (1- (dollar-symbol-p s))))
                                         `(,s (subseq ,string (aref ,match-start ,i) (aref ,match-end ,i)))))
                                     (reverse dollar-symbols))
                         ,consequent))
                   ,alternative))))))))

(I'm using sb-int:once-only and sb-int:with-unique-names to avoid having to include their definitions in this post, which is getting a bit lengthy). Testing this looks like

(defmacro test-if-match (form expected-symbols)
  `(handler-case (macroexpand-1 ',form)
     (if-match/walked-diagnostic (c)
       (assert (equal (if-match-symbols c) ',expected-symbols)))
     (:no-error (&rest values) (declare (ignore values)) (error "no diagnostic"))))
(test-if-match (if-match/walked (test string) (list $1 $2) 'foo) ($2 $1))
(test-if-match (if-match/walked (test string) (if (> (length $1) 6) '$10 '$8) nil) ($1))
(test-if-match (if-match/walked (scanner string)
                   (list $1
                         (if-match/walked (scanner2 string)
                             $2
                             nil))
                   nil)
               ($1))
(test-if-match (if-match/walked (scanner string) (list$/q foo if-match/walked $3) nil) ($3))
(defmacro case-match/walked (string &rest clauses)
  (if (null clauses)
      nil
      `(if-match/walked (,(caar clauses) ,string)
           (progn ,@(cdar clauses))
           (case-match/walked string ,@(cdr clauses)))))
(test-if-match (if-match/walked (scanner string)
                   (case-match/walked $1
                     (foo $2)
                     (bar $3)))
               ($1))

To summarize: I've shown here how to make use of a full code-walker to make a couple of code transforming macros more robust. Full code-walkers can do more than just what I've shown here: the sb-walker:walk-form interface can also inhibit macroexpansion, transform function calls into calls to other functions, while respecting the semantics of the Lisp operators in the code that is being walked and allowing some introspection of the lexical environment. Here, we have called sb-walker:walk-form for side effects from the walker function we've provided; it is also possible to use its value (that's how sb-cltl2:macroexpand-all is implemented, for example). I hope that this can help users affected by the change in internal representation of backquote, as well as others who want to write advanced code-transforming macros. If the thought of using an SBCL-internal code-walker makes you a bit queasy (as well it might), you could instead start by looking at one or two other more explicitly-portable code-walkers out there, for example John Fremlin's macroexpand-dammit, the walker in Alex Plotnick's CLWEB literate programming system (github link), or the code walker in iterate.

Pascal Costanza"Why I like Common Lisp"

· 46 days ago
In a recent email exchange discussion, Charlotte Herzeel gave a summary of Common Lisp that I believe is worth repeating publicly. With her permission, I repeat her statements here.

"An important reason why I like Common Lisp a lot is that the language has a layered design that supports incremental development. The language provides very high-level programming abstractions, such as object-oriented programming, dynamic multiple dispatch, garbage collection, a meta-object protocol, and so on. These abstractions are typically open implementations, built on top of more efficient low-level abstractions the user can also choose to access directly.

Common Lisp is typically implemented as a compiled language, compiling directly to machine code. The runtime components are sparse, the garbage collector being an important one. Common Lisp provides the means to steer the compiler and runtime components to do low-level optimizations. Examples of this include: type declarations to remove type-checking at runtime; inline declarations to avoid dispatch; dynamic extent declarations to perform stack allocation instead of heap allocation; disassembly of code snippets; tuning of the garbage collector to switch between collection strategies; and so on. Optimizations such as these are optional and localized. Hence it is very easy in Common Lisp to rapidly prototype and then incrementally optimize the code by identifying the hotspots through profiling. This way you can often be as efficient as with C code, without being forced to program in a low-level style from the start throughout your whole program.

Hence in contrast to C/C++, Common Lisp allows you to optimize code incrementally and locally for a particular snippet of code. In contrast to Java - or any other language with an implementation that performs optimization at runtime through tracing or JIT compiling or so - Common Lisp implementations employ in a sense a more classic compilation approach. In this sense, Common Lisp makes it easier to 'control' what you are measuring when profiling programs.

The Common Lisp Object System (CLOS) is a library in Common Lisp for object-oriented programming. Common Lisp is a multi-paradigm language, so it depends on your problem whether it is a good idea to use object-oriented programming or not. That said, CLOS is very different from mainstream object-oriented programming. It allows multiple inheritance, multiple dispatch, and is based on generic functions, i.e. classes define types, and methods are defined separately as part of generic functions. The CLOS implementation performs a lot of clever optimizations at runtime, for example for method lookup. What is of course special about CLOS, is that it has a meta-object protocol, which allows you to extend/modify CLOS in an organized way. For example, you have hooks into the method dispatch protocol, the slot (= field) access protocol, etc. If you want to know more about the CLOS implementation and the meta-object protocol, read 'The Art of the Meta-Object Protocol' by Kiczales, des Rivieres, Bobrow.

Common Lisp just has a lot of advanced language features that you just don't find in other languages.

From a practical point of view, I can recommend LispWorks as a Common Lisp implementation. LispWorks is very user-friendly because it comes with an integrated development environment. This means you get Smalltalk-like features such as code browsers and inspector tools. Another user-friendly implementation that is free is Clozure Common Lisp. The most widely used open-source implementation is SBCL, which is very stable and very efficient. There are lots of other Common Lisp implementations out there, but I recommend one of these three.

If you want to learn about Common Lisp, I can recommend "Ansi Common Lisp" by Graham. Maybe also interesting: 'Pascal Costanza's highly opinionated guide to Common Lisp' ;-). If you want a funny introduction to Common Lisp, check out the Lisperati. A good place to snoop for Common Lisp war stories is Planet Lisp. If you want to get an idea about libraries, see quicklisp."


For older items, see the Planet Lisp Archives.


Last updated: 2014-10-23 01:05