Planet Lisp

Joe MarshallJust a small puzzle

· 3 hours ago
You can get the most significant digit (the leftmost) of a number pretty quickly this way
(define (leftmost-digit base n)
  (if (< n base)
      n
      (let ((leftmost-pair (leftmost-digit (* base base) n)))
        (if (< leftmost-pair base)
            leftmost-pair
            (quotient leftmost-pair base)))))
The puzzle is to adapt this code to return the position of the leftmost digit.

(leftmost-digit+ 10 46729885)  would return two values, 4 and 7

Common Lisp TipsDeclining to handle a condition

· 9 hours ago

Occasionally it is convenient for a handler to decide whether to deal with a condition after it already has control.

Sometimes I see that idiom written with a `handler-case` that resignals the condition if it decides it can't take care of it. The downside of that approach is that `handler-case` only resignals the condition after unwinding the stack and removing any restarts that were in place.

`handler-bind` avoids those downsides. When a `handler-bind` handler does not transfer control it is said to "decline to handle" the condition. The condition will then percolate up to surrounding handlers or the debugger with the stack and restarts still in tact, as if the handler had never been entered.

(defun baz ()
  (handler-bind ((error (lambda (c)
                          (when (i-got-this-p c)
                            (return-from baz (quux))))))
    (foo)))

LispjobsCommon Lisp or Clojure Developer, Adelaide or remote

· 14 hours ago

Common Lisp or Clojure Developer
A fantastic opportunity for a Common Lisp developer or Clojure developer that is fast, adaptable and can work independently or fit in well into a team

Experience with Common Lisp or Clojure is a must (could be non-commercial) as well as general knowledge of relational databases and web technologies.

This role could be 100% remote for the right person, to join a top class team and on a great product which could became the Common Lisp application with largest customer base in the world.   The successful applicant will join a small, focused team in maintaining and furthering the development of a leading multivariate testing platform.

Familiarity in the following areas would be considered a plus: backend web server technology, Javascript, PostgreSQL, SQL Server, statistics, distributed computing, Lispworks, any distributed version control system. A high degree of autonomy and self-motivation will be expected.

This is a great career building opportunity and salary package on offer! Although will consider contractors!

If this is of interest I’d be keen to discuss with you, please email me onstewart@totalresource.com.au or call 0061 (0)415 344 427


Nick LevineBrief teaching gig

· 39 hours ago
If anyone knows anyone who'd be qualified and available to give a one day tutorial, in the Barcelona region, on the LispWorks development environment and in particular the debugger, could they get it touch? Thanks.

Nick LevineILC 2014

· 2 days ago

I counted about sixty people in the hall — really not very many for an ILC where one might typically hope for twice that. I didn't see anyone from the CL vendors, hardly anyone from any of the other CL implementations, few people I knew from previous outings, indeed really not many of the "usual suspects" at all. But note that some of this works two ways: I could equally be upbeat and say there wasn't much overlap between Montreal and the recent ELS in Paris: this conference had netted a different audience, which is fine.

My only fault with the program was that there wasn't enough of it. For an ILC there really should be enough material to fill four days. At two and a half, this gig felt like one of the European local meetings, translocated.

As for the presentations: the one that left me totally gaping in amazement was the lightning talk from a 14 year old (sorry kid, I didn't make a note of your name) who'd implemented his own lisp dialect along with embedded image processing and all manner of other bells and whistles. Of the named speakers, I should mention: Dave Cooper's hands-on Gendl tutorial; Christian Queinnec's Small (but Massive) Open Online Course; François-René Rideau's CL scripting; Dave Penkler's amalgam of LISP 1.5 and APL\360; and Robert Strandh's SICL implementation notes. All that time we spent building bigger and better caches is now just history.

My own (co-)talk about work on an NLP project went OK (I think). Judging by the questions, the audience found Michael Young's social science side much more interesting than my comments about the lisp, and I'm not going to disagree with them.

So for two and a half days, some part of the lisp community had come face-to-face. We presented and listened to the talks, we drank the coffee and ate the food, we explored Montreal from below. And when it was all over we all went away again, back to our separate corners. I think the next "lisp community" meet will be European Lisp Symposium 2015, in London next April / May. I mention this "community" idea, because it came up in the panel on the last day, and it's an interesting thought to mull over: is there one? (or more than one?) should there be one? and if you had it in front of you what would you do with it?

LispjobsClojure/ClojureScript and Datomic engineer at Listoria, London or remote

· 4 days ago

Listora is seeking a Clojure/ClojureScript and Datomic engineer

Reply to Henry dot ec at Gmail dot com

London based start up with highly experienced (and awesome) distributed team of researchers, engineers and designers. Although the project is still in its infancy (very greenfield), we have a big vision of being the global leader in high-quality structured events data, which will help to drive the contextual and personalised event discovery experiences of the future.

We're developing our platform along with applications that meet the needs (jobs/outcomes) of content data partners, event organisers, publishers and developers. It's both a huge CS and product challenge and we need exceptional and ambitious people to solve the problems that we'll come up against.

We've been developing our core platform with Clojure + Datomic/Cassandra and our applications with ClojureScript/Om. We have a very advanced stack that any passionate FP engineer would be excited about working on. We also regularly work in the open source community and are already releasing libraries.

In terms of product, we have an upfront investment in high quality research and concept evaluation taken from years of experience using both customer and outcome driven development methodologies. We are very open in what we do and have a toolset to build our products very closely with our customers. We don't work to deadlines, but we do spend a lot of time thinking about the prioritisation of what we are and could be building.

We are looking for engineers to join our team that can hit the ground running. The right person will be self-motivated, conscientious, humble and a great communicator. We are looking for people with many years FP experience in senior, lead or architectural roles and are used to working in a start up environment with start up tooling.

We want to work with fantastic engineers and passionate people. This is one of the things that motivates us. We don't mind where in the world you're based or whether you want a permanent or contracting relationship.

If you're the right fit with our team we will work hard to look after you - from giving you the flexibility to explore ideas and technologies for the job at hand to remuneration.

If you have any questions, we would love to hear from you.


LispjobsClojure/Clojurescript positions: DiligenceEngine, Toronto, Ontario, or remote

· 5 days ago

DiligenceEngine, a Toronto-based startup using machine learning to automate legal work, is hiring two Clojure/Clojurescript developers. They say:

We're looking for a developer to work on our clojure/clojurescript/om web stack. Our team is small, pragmatic, and inquisitive; we love learning new technologies and balance adoption with good analysis. We prefer to hire near us, but also welcome remote work in a time zone within North America.

See the full job descriptions on the DiligenceEngine website.


Paul KhuongHow to Define New Intrinsics in SBCL

· 5 days ago

This Stack Overflow post points out an obscure and undocumented weakness in Intel’s implementation of the POPCNT instruction: although the population count (number of bits equal to 1) is only a function of the source argument, hardware schedules it as though it also depended on the destination. GCC, clang and MSVC all fail to take this issue into account.

Until a new patched version of my favourite C compiler is released, there aren’t many tasteful workarounds for this performance bug. I’d have to switch to inline asm, and either force the compiler to allocate the same register to the input and the result, or force different registers and clear the spurious dependency with a xor. Ideally, I wouldn’t impose any additional constraint on the register allocator and only insert a xor if the destination and source registers don’t match.

SBCL easily supports this use case, without having to re-release or even recompile the implementation: VOPs (virtual operations) execute arbitrary CL code during code generation and they can be defined at runtime.

The first step is to make sure that SBCL’s assembler knows how to emit popcnt: the assembler can also be extended at runtime, but that’s more hairy and a topic for another post. Instruction encodings are defined in src/compiler/$ARCH/insts.lisp, and a quick grep reveals (define-instruction popcnt (segment dst src) ...): the x86-64 backend learned about popcnt in May 2013 (thanks to Douglas Katzman).

We define VOPs via define-vop, a macro that exposes many options. Most of the time, it’s easiest to look at a pre-existing definition for an operation that’s similar to the one we want to add. Popcount looks like integer negation: it has a single (machine integer) argument and returns another integer. Integer negation is defined in src/compiler/$ARCH/arith.lisp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
;;;; unary operations

(define-vop (fast-safe-arith-op)
  (:policy :fast-safe)
  (:effects)
  (:affected))

(define-vop (fixnum-unop fast-safe-arith-op)
  (:args (x :scs (any-reg) :target res))
  (:results (res :scs (any-reg)))
  (:note "inline fixnum arithmetic")
  (:arg-types tagged-num)
  (:result-types tagged-num))

(define-vop (signed-unop fast-safe-arith-op)
  (:args (x :scs (signed-reg) :target res))
  (:results (res :scs (signed-reg)))
  (:note "inline (signed-byte 64) arithmetic")
  (:arg-types signed-num)
  (:result-types signed-num))

(define-vop (fast-negate/fixnum fixnum-unop)
  (:translate %negate)
  (:generator 1
    (move res x)
    (inst neg res)))

(define-vop (fast-negate/signed signed-unop)
  (:translate %negate)
  (:generator 2
    (move res x)
    (inst neg res)))

(define-vop (fast-negate/unsigned signed-unop)
  (:args (x :scs (unsigned-reg) :target res))
  (:arg-types unsigned-num)
  (:translate %negate)
  (:generator 3
    (move res x)
    (inst neg res)))

The code snippet above includes a bit of boilerplate to factor out commonalities via inheritance. The first definition introduces fast-safe-arith-op, VOPs that apply in both high speed and high safety settings (the rest is copy/pasted noise from earlier ports that sport a scheduler); the second one extends fast-safe-arith-op to define fixnum-unop, a base definition for single-argument operations on fixnums, while the third one is the same, but for machine integers. The last three definitions fill in the blanks so the compiler can compile %negate of fixnum, signed and unsigned integers. The (:translate %negate) bit means that these VOPs can be emitted instead of calls to %negate. The integer after :generator defines the “cost” of each variant; the compiler will choose the (applicable) variant with the least cost and execute the code sequence that follows to convert a call to %negate into machine code.

This kind of implementation inheritance is fine for an SBCL backend, where we define many VOPs and expect developers to understand the system. I doubt it’s a didactic win. Let’s do something simpler for popcnt. In the interest of simplicity, I’ll also completely disregard powerful details in define-vop that are rarely relevant when defining intrinsics that map directly to machine instructions.

First, we need to tell the compiler that we’re about to do special things to a function named popcnt (and to blow away any pre-existing information if the defknown form is re-evaluated).

1
2
3
4
5
6
7
8
9
(defpackage "POPCNT"
  (:use "CL")
  (:export "POPCNT"))

(in-package "POPCNT")

(sb-c:defknown popcnt ((unsigned-byte 64)) (integer 0 64)
    (sb-c:foldable sb-c:flushable sb-c:movable)
  :overwrite-fndb-silently t)

This says that popcnt accepts a 64-bit unsigned integer and returns an integer between 0 and 64 (inclusively), and that the function can be constant-folded, flushed (eliminated as dead code) and moved around (it’s pure).

Now, to define a VOP that implements popcnt:

1
2
3
4
5
6
7
8
9
10
11
12
13
(in-package "SB-VM")

(define-vop (popcnt:popcnt)
  (:policy :fast-safe)
  (:translate popcnt:popcnt)
  (:args (x :scs (unsigned-reg) :target r))
  (:arg-types unsigned-num)
  (:results (r :scs (unsigned-reg)))
  (:result-types unsigned-num)
  (:generator 3
    (unless (location= r x) ; only break the spurious dep. chain
      (inst xor r r))       ; if r isn't the same register as x.
    (inst popcnt r x)))

We define a new VOP named popcnt:popcnt (the name is arbitrary, as long as it doesn’t collide with another VOP) that is applicable at all optimization policies (both high speed and high debug level), and that implements popcnt:popcnt. Its first and only argument, x, is an unsigned-num, an unsigned machine integer, that can only be stored in a register. Moreover, if possible, we’d like x to be allocated the same register as the result, r. There’s only one result (r) and it’s an unsigned machine integer in a register, just like x. The generator, of cost 3 (a common default for arithmetic operations), breaks any dependency chain in r if necessary, and stores the population count of x in r.

At first sight, the defknown form seems to conflict with the VOP. We declare that the return value of popcnt is a small integer, clearly a fixnum, and then define a VOP that returns a machine integer. The subtlety is that defknown is concerned with IR1, the higher level intermediate representation, which works on CL types (i.e, types as sets) and abstract values. VOPs, on the other hand, are defined for the lower level IR2, where types describe concrete representations (like C). It is perfectly meaningful to say that a small integer will be represented as an untagged machine integer.

The next step isn’t strictly necessary, but helps people who like their REPL. The compiler knows how to compile calls to popcnt, so we can define popcnt… as a call to popcnt. Our new function is now a first-class value that can be called from interpreted code and passed to higher-order functions, like the compiler’s constant-folding pass.

1
2
3
4
(in-package "POPCNT")

(defun popcnt (x)
  (popcnt x))
CL-USER> (disassemble 'popcnt:popcnt)
; disassembly for POPCNT:POPCNT
; Size: 25 bytes
; 07FCDB6E:       4831D2           XOR RDX, RDX               ; no-arg-parsing entry point
;       71:       F3480FB8D1       POPCNT RDX,RCX
;       76:       48D1E2           SHL RDX, 1
;       79:       488BE5           MOV RSP, RBP
;       7C:       F8               CLC
;       7D:       5D               POP RBP
;       7E:       C3               RET
[ error trap noise ]
CL-USER> (popcnt:popcnt 42)
3

The disassembly shows that we get the code that we expect, including the dependency-breaking workaround, and the smoke test passes. There’s one interesting detail: we only defined a VOP that returns a machine integer. However, popcnt returns a tagged value (a fixnum), and does so with an efficient shift. IR2 takes care of inserting any coercion needed between VOPs (e.g., between popcnt and the VOP used to return boxed values from functions), and the IR1 defknown guarantees that the result of popcnt, despite being represented in an unsigned machine integer, is small enough for a fixnum.

Let’s see what happens when we feed arithmetic into popcnt, e.g.:

CL-USER> (disassemble (lambda (x y)
                        (declare (type (unsigned-byte 32) x y))
                        (popcnt:popcnt (+ x y))))
; disassembly for (LAMBDA (X Y))
; Size: 55 bytes
; 0752BD59:       4801FA           ADD RDX, RDI               ; no-arg-parsing entry point
;       5C:       48D1FA           SAR RDX, 1
;       5F:       F3480FB8D2       POPCNT RDX,RDX
;       64:       48D1E2           SHL RDX, 1
;       67:       488BE5           MOV RSP, RBP
;       6A:       F8               CLC
;       6B:       5D               POP RBP
;       6C:       C3               RET

After adding two fixnums, an automatic coercion unboxes the resulting fixnum into a machine integer which is then passed to popcnt (note the lack of dependency-breaking xor now that the source and destination are the same register).

That’s pretty good code, but we can do better: fixnums are tagged with 0, so we can simply feed fixnums to popcnt without untagging.

This is where the cost parameter to :generator comes in: we can define another VOP for popcnt of fixnums and bias the compiler to prefer the fixnum VOP.

1
2
3
4
5
6
7
8
9
10
11
12
13
(in-package "SB-VM")

(define-vop (popcnt/fx)
  (:policy :fast-safe)
  (:translate popcnt:popcnt)
  (:args (x :scs (any-reg) :target r))
  (:arg-types positive-fixnum)
  (:results (r :scs (unsigned-reg)))
  (:result-types unsigned-num)
  (:generator 2 ; 2 is lower than 3, so popcnt/fx is preferable to popcnt
    (unless (location= r x)
      (inst xor r r))
    (inst popcnt r x)))
CL-USER> (disassemble (lambda (x y)
                        (declare (type (unsigned-byte 32) x y))
                        (popcnt:popcnt (+ x y))))
; disassembly for (LAMBDA (X Y))
; Size: 47 bytes
; 07BEABE9:       4801FA           ADD RDX, RDI               ; no-arg-parsing entry point
;      BEC:       F3480FB8D2       POPCNT RDX,RDX
;      BF1:       48D1E2           SHL RDX, 1
;      BF4:       488BE5           MOV RSP, RBP
;      BF7:       F8               CLC
;      BF8:       5D               POP RBP
;      BF9:       C3               RET

Unlike many low-level languages, CL includes a standard function for population count, logcount. SBCL includes a VOP for logcount (with a cost of 14), which we can supersede with our own popcnt-based VOPs: we only have to replace (:translate popcnt:popcnt) with (:translate logcount). That’s an easy improvement but isn’t in trunk because popcnt is a recent x86 extension.

Adding VOPs for (ad-hoc) polymorphic or otherwise generic functions can be surprising: a VOP will only be considered if the arguments and the return values are known to have CL types that are compatible with the VOP’s representation specification. For popcnt, we guarantee that the return value is a positive integer between 0 and 64; for cl:logcount, the defknown guarantees that the return value is a positive fixnum. In both cases, the return values can always be represented as an unsigned machine integer, so our new VOPs will always match if the argument fits in positive fixnums or unsigned machine integers (and will have priority over the generic x86-64 VOP because their cost is lower). More complex cases depend on derive-type optimizers, but that’s rarely necessary when defining instrinsics for low-level code.

Colin LuptonQuantum Computing and Lisp

· 7 days ago

Quantum Computing is a fascinating field, but currently a contentious one. The only examples we have of real-world, hardware quantum computers are the line of adiabatic quantum computers from D-Wave Systems—and many voices in the scientific community still protest its identification as such simply because it is not a full-fledged gate-model quantum computer complete with persistent quantum data storage and QRAM. However, by the strictest definition, any machine which exploits quantum mechanical phenomena for the purpose of computation is a quantum computer, and the D-Wave One and Two meet this definition.

For us in the Lisp community, Quantum Computing is even more important; one of the most surprising secrets of the D-Wave line of adiabatic quantum computers is that their low-level operating system is programmed in Common Lisp. Specifically, D-Wave uses SBCL. This choice is not accidental or arbitrary—Common Lisp is uniquely suited to the task of quantum computer programming.

Lambda Calculus, Functional Programming, and Quantum Computing

Peter Selinger, a Professor of Mathematics at Dalhousie University, has been publishing papers regarding Quantum Computer programming languages and Lambda Calculus for a number of years, extending the work of van Tonder and others. In particular, he formalized his argument in favor of Lambda Calculus as a natural expression of quantum algorithms for classically-controlled quantum computers in the following papers:

Selinger made one mistake, in my opinion: he chose Haskell to implement his quantum computer simulator and quantum computer programming language, Quipper. While he could have chosen Scheme without any complaint, he should have chosen Common Lisp, just like D-Wave—and to prove this point, I took my work on a Quantum Common Lisp I originally designed for my science-fiction novel and started the BLACK-STONE open-source project to create a faster quantum computer simulator and programming environment, in less lines of code. While the BLACK-STONE project is still in its infancy (and I haven’t had the time to work on it at all in recent months), the simplicity, elegance, clarity, and succinctness of the Common Lisp source compared to Haskell is already heavily apparent.

D-Wave One and Two are rudimentary Quantum Lisp Machines

I was surprised and pleased to discover in my personal conversations with the lead physicists, engineers, and developers at D-Wave, that they had come to the same conclusion as me, but had the means to act on those insights. They had already accomplished what I set out to do with Quantum Common Lisp and BLACK-STONE; unfortunately, their source code is very much proprietary, and even as a registered D-Wave developer, I had no access to their Lisp operating system for the D-Wave One and Two.

All I can do, as an outsider looking in, is make certain informed assumptions. I could easily be completely wrong, but it seems to me fairly self-evident that the D-Wave platforms qualify as rudimentary prototype Quantum Lisp Machines. The D-Wave hardware was clearly designed with Lisp in mind, and the low-level Operating System of the D-Wave hardware is written entirely in Common Lisp. Personally, I don’t think it would have even been possible for them to build a quantum computer at all without Lisp.

As I understand the integration model, the D-Wave platforms rely on classical supercomputers for their interface, memory, and persistent storage—so that limits the types of quantum algorithms that can be run to those that must accept from and return measured, classical data to the interface; algorithms which expect unmeasured, raw quantum data for input, and persistence of such data existing unmeasured in memory are not currently possible.

Still, any quantum computer at all is an amazing feat—and certainly D-Wave’s customer base seems quite happy with the platform. They are purpose built for a specific class of optimization problems, which classical computers have a great deal of difficulty solving.

Regarding their former developer program, which has now been closed for some time, it is interesting to ponder why—when the core platform is 100% Lisp—they would only release a Python Pack as their developer API and not a Lisp interface. I suspect it came down to the matter of perceived value and a hope for rapid adoption: they put a lot of time and effort into writing a quantum computer simulator for Python, and a number of excellent tutorials to go with it, but still they did not get the adoption they hoped for—and as a result, they closed the developer program and scrapped the Quantum Cloud platform that I was relying on and waiting for, to finish some of my more interesting (to me at least), software projects.

The problem with the choice of Python, however, is that Quantum Computer programming only actually makes sense in Lisp, and as a result only Lisp Hackers can understand Quantum Computer Programming. Other programming languages only serve to conflate the simple elegance of quantum energy programming into a terrifying, obtuse, impenetrable subject, while in Lisp it is expressed so naturally and intuitively—it’s almost as if Lisp itself was purpose designed for quantum computing.

You can see this for yourself in my project SILVER-SWORD, a Common Lisp bridge to the D-Wave Python Pack. Unfortunately, as I’ve said before, you can’t actually use the library since D-Wave no longer distributes their Python Pack, but you can view the translated tutorial examples in the repo and see for yourself—quantum energy programming is really easy in Lisp. And SILVER-SWORD would be even better if the underlying Lisp–Python bridge, BURGLED-BATTERIES, supported Python Class to CLOS translation.

Cons-cells, qubits, chimera-graphs, and the human brain

The reason I say that only Lispers can understand Quantum Computer programming is based on the observation of the fundamental structural similarities between a generalized model Lisp program, the D-Wave hardware, and the human brain. From an experiential perspective, learning and using one of the many Lisp-family languages offers the individual programmer specific insight into the functioning of their own internal platform.

Consider a general, recursive function in Common Lisp. Its internal representation within the Lisp run-time is an acyclic graph of cons-cells, pairs of pointers that map to memory or other cons-cells. Every Lisper eventually learns to think in terms of cons-cells, and is concerned about the efficiency of their code in terms of tree-walking—which path through all possible cons-cells to the desired return value is the shortest?—and, which path reduces the number of conses to the absolute minimum?

Now consider a learned skill, such as the art of programming; it can be a lengthy process for some, a seemingly effortless task for others. Many people brush this off as a simple matter of intelligence—but in fact, it is due to another learned skill: the art of learning itself, whereby the individual learns to integrate and categorize new information more efficiently than others, thus appearing smarter. Technically speaking, as we have been learning from the field of neuroscience, all human beings are born with roughly equal potential, but they are shaped and molded into individuals by their experiences and environment; in short, since so few of us know any better, we allow ourselves and our children to be automatically programmed by effectively random, chaotic, and unpredictable perceptions, instead of learning and teaching a methodology of self-mastery where the individual programs themselves. At the moment, intelligence and an aptitude for the sciences, engineering, mathematics and programming in individuals is more or less an accident, much like all talents; but in the near future, all talents could easily be engineered by the individual into themselves.

Then consider the concept of Quantum Computer energy programming, introduced by D-Wave as the programming paradigm to support their novel adiabatic quantum computer hardware. Because the underlying flux-qubits of the D-Wave processors exist in superposition until they are measured, they effectively process every probable result of a program simultaneously. The most efficient answer, the lowest energy solution, is returned first; even though all other results returned are also correct, from a traditional standpoint, the lowest energy solution is the most correct, even when other results have a higher probability. This point corresponds to both the question of intelligence, and the most efficient recursive function in Lisp, above. The most obvious path is not always the most correct, but a strong case can always be made to favor efficiency over all other factors.

These three points correspond to a psychological/computational Occam’s Razor—when faced with multiple solutions of high probability, the most efficient solution is the most correct.

Alongside a cursory study of neuroscience and theoretical physics, you can begin to see the similarities between the structure of Lisp programs, the implementation of the D-Wave quantum annealing processor, and the structure of the human brain itself.

As I have said before, Lisp is the language of the Universe, the Voice and Will of the True Self. This is simply a poetic expression of super-symmetry, and how it relates to the concept of Grokking in the Lisp community. The point is, the acyclic graph structure of cons-cells allows for a natural description of the fundamental (and inherently quantum) phenomenon of the physical universe, as well as of the humain brain itself.

Thus, when programmed in Lisp, a sufficiently complex neural-net application running natively on D-Wave style hardware of equal complexity and efficiency as the human brain is capable of emergent machine intelligence. The less it is programmed to behave intelligently, the better—it only requires a diverse selection of sensory input to perceive its external environment, a means to differentiate the internal from the external, and a core low-level operating system to manage its internal state. Experiments at D-Wave have already confirmed this.

One might even be so bold as to say that the super-symmetry is so perfectly expressed, that we human beings are naturally-occurring, organic quantum lisp machines. And this point holds whether you are an evolutionist, creationist, or otherwise.

The Future of Computing and Lisp

If quantum computing is the future of computer science as a whole, then by extension, so is Lisp. As Lisp Hackers, we have a responsibility to push computing to its limits, remind the world that Common Lisp is still the most advanced and powerful programming language, and ensure that the next generation of consumer-grade computers are all—every single one of them—Quantum Lisp Machines.

The inherent super-symmetry of Lisp programs, the central nervous system, and the physical universe is perhaps the strongest argument in favor of this. After all, human evolution has been marked out since the beginning of history not by advantageous genetic mutation, but by technological innovation—and what tool is more powerful than a language which can naturally express the fundamental laws of physics, the underlying structure of the human brain, and the ultimate model of computation?

Together, Quantum Computing and Lisp can help us better understand ourselves, our true nature, the universe we live in, and the limitless potential of our species—that the combination will almost certainly lead to emergent machine intelligence and the technological singularity is pure gravy, after that. Some days it is truly staggering to live in such a time in human history, living with the knowledge that we Lisp Hackers hold the future of the entire human race in our hands, at our keyboards.

The next time you fire up Emacs and type M-x slime, remember this. Hack like the whole world is counting on you and every line of code you write; hack like you’re channeling the Will of the universe itself. Because the future is here, now—the future is Quantum Common Lisp.


Colin LuptonLET-OVER-LAMBDA fixed for SBCL 1.2.2

· 7 days ago

Thanks go out to Orivej Desh—he pointed out what I overlooked, and the LET-OVER-LAMBDA package now works with full functionality restored in SBCL 1.2.2. I have preserved the :safe-sbcl feature used for testing the version of SBCL, so that descending into comma-expr of sb-impl::comma is only enabled for SBCL 1.2.2+.

The updated code should be available in the August release of Quicklisp. If you have a fork or clone, please be certain to pull the latest changes from the master branch.


Colin LuptonLET-OVER-LAMBDA broken in SBCL 1.2.2

· 9 days ago

As expected, the Quicklisp distribution of LET-OVER-LAMBDA is broken by the changes to the backquote reader macro in SBCL 1.2.2; although I expect this change breaks a good portion of Paul Graham’s macro code examples from On Lisp, as well.

A quick-fix suggested on Reddit is to use a “pseudo-flatten” for SBCL that also descends into sb-impl::comma-expr of sb-impl::comma. I will be testing this fix today, and hopefully pushing an updated version for the August release of Quicklisp.

Stay tuned.

UPDATE: modified LOL:FLATTEN to descend into comma-expr of sb-impl::comma objects, but no joy. I have currently disabled DEFMACRO! based code in LET-OVER-LAMBDA until I can find a better solution, and tested this against both v1.2.2 and v1.2.0-1 of SBCL (so if nothing else, it will at least build without errors).

If anyone knows of a better solution, feel free to leave a comment here or on the GitHub Issue thread.


Joe MarshallMini regex golf 3: set cover

· 13 days ago
I'm computing the set cover by incrementally adding items to be covered. Naturally, the order in which you add items changes the way the program progresses. I added code that picks an item to be added each iteration rather than just pulling the car off the front of a list.
(define (cover8 value->keys-table better-solution)

  (define (add-v-k-entry solution-set v-k-entry)
    (let ((value (car v-k-entry))
          (keys  (cdr v-k-entry)))

      (write-string "Adding value ") (write value) (newline)
      (write-string "   with keys ") (write keys) (newline)
      (write-string "   to ") (write (length solution-set))
      (write-string " partial solutions.") (newline)

      (let ((new-solutions
             (map make-new-solution (cartesian-product solution-set keys))))

        (let ((trimmed-solutions 
                (trim-partial-solutions value->keys-table new-solutions)))

          (write-string "Returning ") (write (length trimmed-solutions))
          (write-string " of ") (write (length new-solutions))
          (write-string " new partial solutions.") (newline)

          trimmed-solutions))))

  (define (cover v-k-entries)
    (cond ((pair? v-k-entries)
           (pick-v-k-entry value->keys-table v-k-entries
                           (lambda (selected remaining)
                             (add-v-k-entry (cover remaining) selected))))
          ((null? v-k-entries)
           (list '()))
          (else (improper-list-error 'cover v-k-entries))))

  (let ((minimized (minimize-vktable value->keys-table better-solution)))
    (least-elements (cover minimized) better-solution)))

(define (pick-v-k-entry value->keys-table v-k-entries receiver)
  (define (score v-k-entry)
    (let* ((matched-all 
     (count-matching-items value->keys-table
      (lambda (other)
        (there-exists? (cdr v-k-entry)
                 (lambda (key) (member key (cdr other)))))))
           (matched-remaining
            (count-matching-items v-k-entries
                                  (lambda (other)
                                    (there-exists? (cdr v-k-entry)
                                       (lambda (key) (member key (cdr other)))))))
           (matched-forward (- matched-all matched-remaining)))
      (cons matched-remaining matched-forward)))

  (let ((scored (map (lambda (v-k-entry) (cons (score v-k-entry) v-k-entry))
                      v-k-entries)))

    (let ((picked 
    (cdar
     (least-elements scored
       (lambda (left right)
         (let* ((len-l (length (cdr left)))
         (len-r (length (cdr right)))
         (lmr (caar left))
         (lmf (cdar left))
         (rmr (caar right))
         (rmf (cdar right)))
    (or (> len-l len-r)
        (and (= len-l len-r)
      (or (> lmf rmf)
          (and (= lmf rmf)
        (< lmr rmr)))))
    ))))))

      (display "Picking ") (write picked) (newline)
      (receiver picked (delete picked v-k-entries)))))

(define (trim-partial-solutions value->keys-table partial-solutions)
    (let ((equivalent-solutions
           (map (lambda (entry) (cons (cdr entry) (car entry)))
                (collect-equivalent-partial-solutions value->keys-table
                                                      partial-solutions))))
      (write-string "  Deleting ")
      (write (- (length partial-solutions) (length equivalent-solutions)))
      (write-string " equivalent partial solutions.")
      (newline)

      (remove-dominated-solutions value->keys-table
                                  (map lowest-scoring-equivalent-partial-solution
                                       equivalent-solutions))))
Finally, it turns out that computing dominating partial solutions is expensive, so I changed the set operations to use a bitmap representation:
(define (remove-dominated-solutions value->keys-table partial-solutions)
  (let ((before-length (length partial-solutions))
        (all-values (get-values value->keys-table))) 
    (let ((table
           ;; put the long ones in first
           (sort
            (map (lambda (partial-solution)
                   (cons partial-solution
                     (lset->bset all-values 
                       (map car (partial-solution-matches value->keys-table 
                                                          partial-solution)))))
                 partial-solutions)
            (lambda (left right)
              (> (length (bset->lset all-values (cdr left)))
                 (length (bset->lset all-values (cdr right))))))))

      (let ((answer (map car
                         (fold-left (lambda (answer solution)
                                      (if (there-exists? answer 
                                                         (dominates-solution? solution))
                                          answer
                                          (cons solution answer)))
                                    '()
                                    table))))
        (let ((after-length (length answer)))
          (write-string "  Removing ") (write (- before-length after-length))
          (write-string " dominated solutions.")
          (newline)
          answer)))))

(define (dominates-solution? solution)
  (let* ((partial-solution (car solution))
         (partial-solution-score (score partial-solution))
         (solution-matches-raw (cdr solution)))
    (lambda (other-solution)
      (let* ((other-partial-solution (car other-solution))
             (other-matches-raw (cdr other-solution)))
        (and
         (bset-superset? other-matches-raw solution-matches-raw)
         (<= (score other-partial-solution) partial-solution-score))))))

(define (get-values v-k-table)
  (fold-left (lambda (answer entry) (lset-adjoin equal? answer (car entry)))
             '()
             v-k-table))

(define (bset-element->bit universe element)
  (cond ((null? element) 0)
        (else (expt 2 (list-index (lambda (item) (eq? item element)) universe)))))

(define (bset-adjoin universe bset element)
  (bset-union bset (bset-element->bit universe element)))

(define (lset->bset universe lset)
  (fold-left (lambda (answer element)
               (bset-adjoin universe answer element))
             0
             lset))

(define (bset->lset universe bset)
  (cond ((zero? bset) '())
        ((even? bset) (bset->lset (cdr universe) (/ bset 2)))
        (else (cons (car universe) (bset->lset (cdr universe) (/ (- bset 1) 2))))))

(define (bset-union left right) (bitwise-ior left right))

(define (bset-superset? bigger smaller)
  ;; Is every element of smaller in bigger?
  (zero? (bitwise-andc2 smaller bigger)))
This code can now find the shortest regular expression consisting of letters and dots (and ^$) that matches one set of strings but not another.

Depending on the strings, this can take quite a bit of time to run. Dotted expressions cause a combinatorical explosion in matching regexps (or substrings), but what makes it worse is that the dotted expressions tend to span different sets of strings. If two different dotted expressions, each with different matching sets of strings, appear in a single string, then the number of partial solutions will be multiplied by two as we try each different dotted expression.

It is characteristic of NP problems that it is easy to determine if you have a good solution, but quite hard to find it among a huge number of other, poor solutions. This problem exhibits this characteristic, but there is a bit more structure in the problem that we are exploiting. The word lists are drawn from the English language. This makes some bigrams, trigrams, etc. far, far, more likely to appear than others.

Short words are much easier to process than longer ones because they simply contain fewer things to match. On the other hand, longer words tend to be dominated by shorter ones anyway.

To be continued...

Joe MarshallMini regex golf 2: adding regular expressions

· 14 days ago
It wasn't too hard to add regular expressions to the substring version. What took a while was just tinkering with the code, breaking it, fixing it again, noticing an optimization, tinkering, etc. etc. In any case it works and here is some of it.
(define (make-extended-ngram-table winners losers)
  (let* ((initial-ngrams (generate-ngrams winners losers)))
    (write-string "Initial ngrams: ") (write (length initial-ngrams))
    (newline)
    (map (lambda (winner)
           (cons winner
                 (keep-matching-items initial-ngrams
                    (lambda (ngram) (re-string-search-forward ngram winner)))))
         winners)))

(define (generate-ngrams winners losers)
  (write-string "Generating ngrams...")(newline)
  (let ((losing-ngram? (string-list-matcher losers)))
    (fold-left (lambda (answer winner)
                 (lset-union equal? answer (extended-ngrams losing-ngram? winner)))
               '()
               winners)))

(define (string-list-matcher string-list)
  (lambda (test-ngram)
    (there-exists? string-list
                   (lambda (string)
                     (re-string-search-forward test-ngram string)))))

(define *dotification-limit* 4)
(define *generate-ends-of-words* #t)
(define *generate-dotted* #t)

(define (ngrams-of-length n string)
  (do ((start    0 (1+ start))
       (end      n (1+ end))
       (answer '() (lset-adjoin string=? answer (substring string start end))))
      ((> end (string-length string)) answer)))

(define (generate-dotted answer losing-ngram?)
  (do ((tail answer (cdr tail))
       (answer '() (let ((item (car tail)))
                     (fold-left (lambda (answer dotted)
                                  (if (losing-ngram? dotted)
                                      answer
                                      (lset-adjoin string=? answer dotted)))
                                answer
                                (dotify item)))))
      ((not (pair? tail))
       (if (null? tail)
           answer
           (improper-list-error 'generate-dotted tail)))))

(define (dotify word)
  (cond ((string=? word "") (list ""))
        ((> (string-length word) *dotification-limit*) (list word))
        (else
         (fold-left (lambda (answer dotified)
                      (fold-left (lambda (answer replacement)
                                   (lset-adjoin equal? answer 
                                        (string-append replacement dotified)))
                                 answer
                                 (replacements (substring word 0 1))))
                    '()
                    (dotify (substring word 1 (string-length word)))))))

(define (replacements string)
  (if (or (string=? string "^")
          (string=? string "$"))
      (list string)
      (list string ".")))

(define (extended-ngrams losing-ngram? string)
  (let ((string (if *generate-ends-of-words*
                    (string-append "^" string "$")
                    string)))
    (do ((n 1    (+ n 1))
         (answer '() (lset-union
                      string=? answer
                      (delete-matching-items (ngrams-of-length n string)
                                             losing-ngram?))))
        ((> n (string-length string))
         (if *generate-dotted*
             (generate-dotted answer losing-ngram?)
             answer)))))
Adding the dotification greatly increases the number of ways to match words:
1 ]=> (extended-ngrams (string-list-matcher losers) "lincoln")

;Value 15: ("li" "ln" "ln$" "oln" ".ln" "col" "lin" "li." "^li" "o.n$" "oln$" ".ln$" "col." "c.ln" "..ln" "coln" ".oln" "co.n" "n.ol" "..ol" "ncol" ".col" "nc.l" "i.co" "inco" "i..o" "in.o" "lin." "li.." "l.nc" "linc" "l..c" "li.c" "^li." "^lin" "coln$" "ncoln" "incol" "linco" "^linc" "ncoln$" "incoln" "lincol" "^linco" "incoln$" "lincoln" "^lincol" "lincoln$" "^lincoln" "^lincoln$")
The table that maps words to their extended ngrams is quite large, but it can be reduced in size without affecting the solution to the set cover problem. If two regexps match exactly the same set of winning strings, then one can be substituted for the other in any solution, so we can discard all but the shortest of these. If a regexp matches a proper superset of another regexp, and the other regexp is at least the same length or longer, then the first regexp dominates the second one, so we can discard the second one.
(define (minimize-keys value->keys-table better-solution)
  (let* ((all-keys (get-keys value->keys-table))
         (equivalents (collect-equivalent-partial-solutions value->keys-table
                         (map list all-keys)))
         (reduced (map (lambda (equivalent)
                         (cons (car equivalent)
                               (car (least-elements (cdr equivalent)
                                                    better-solution))))
                       equivalents))
         (dominants (collect-dominant-partial-solutions reduced better-solution))
         (good-keys (fold-left (lambda (answer candidate)
                                 (lset-adjoin equal? answer (cadr candidate)))
                               '()
                               dominants)))

    (define (rebuild-entry entry)
      (cons (car entry) (keep-matching-items (cdr entry)
                             (lambda (item) (member item good-keys)))))

    (write-string "Deleting ") (write (- (length all-keys) (length good-keys)))
    (write-string " of ") (write (length all-keys)) (write-string " keys.  ")
    (write (length good-keys)) (write-string " keys remain.")(newline)
    (map rebuild-entry value->keys-table)))

(define (partial-solution-matches value->keys-table partial-solution)
  (keep-matching-items
   value->keys-table
   (lambda (entry)
     (there-exists? partial-solution (lambda (key) (member key (cdr entry)))))))

(define (collect-equivalent-partial-solutions value->keys-table partial-solutions)
  (let ((answer-table (make-equal-hash-table)))

    (for-each (lambda (partial-solution)
                (hash-table/modify! answer-table
                                   (map car (partial-solution-matches 
                                               value->keys-table 
                                               partial-solution))
                                    (list)
                                    (lambda (other)
                                      (lset-adjoin equal? other partial-solution))))
              partial-solutions)

    (hash-table->alist answer-table)))

(define (collect-dominant-partial-solutions equivalents better-solution)
  (define (dominates? left right)
    (and (superset? (car left) (car right))
         (not (better-solution (cdr right) (cdr left)))))

  (let ((sorted (sort equivalents 
                      (lambda (l r) (> (length (car l)) (length (car r)))))))
    (fold-left (lambda (answer candidate)
                 (if (there-exists? answer (lambda (a) (dominates? a candidate)))
                     answer
                     (lset-adjoin equal? answer candidate)))
               '()
               sorted)))
We can minimize the value->key-table in another way. If two values in the table are matched by the exact same set of keys, then we can delete one without changing the solution. If a value is matched by a small set of keys, and if another values is matched by a superset of these keys, then we can delete the larger one because if the smaller one matches, the larger one must match as well.
(define (minimize-values v-k-table)
  (let ((size-before (length v-k-table)))

    (define (dominated-value? entry)
      (let ((entry-value (car entry))
            (entry-keylist (cdr entry)))
        (there-exists? v-k-table
          (lambda (other-entry)
            (and (not (eq? entry other-entry))
                 (let ((other-value (car other-entry))
                       (other-keylist (cdr other-entry)))
                   (let ((result (and (superset? entry-keylist other-keylist)
                                      (not (superset? other-keylist entry-keylist)))))
                     (if result
                         (begin (display "Removing ")
                                (write entry-value)
                                (display " dominated by ")
                                (write other-value)
                                (display ".")
                                (newline)
                                ))
                     result)))))))

    (define (equivalent-value-in-answer? answer entry)
      (let ((entry-value (car entry))
            (entry-keylist (cdr entry)))
        (there-exists? answer
          (lambda (other-entry)
            (let ((other-value (car other-entry))
                  (other-keylist (cdr other-entry)))
              (let ((result (equal? entry-keylist other-keylist)))
                (if result
                    (begin (display "Removing ")
                           (write entry-value)
                           (display " equivalent to ")
                           (write other-value)
                           (display ".")
                           (newline)
                           ))
                result))))))

    (define (add-entry answer entry)
      (if (or (equivalent-value-in-answer? answer entry)
              (dominated-value? entry))
          answer
          (cons entry answer)))

    (let ((answer (fold-left add-entry '() v-k-table)))
      (write-string "Removed ") (write (- size-before (length answer)))
      (write-string " dominated and equivalent values.")
      (newline)
      answer)))
Each time we remove values or keys, we might make more keys and values equivalent or dominated, so we iterate until we can no longer remove anything.
(define (minimize-vktable value->keys-table better-solution)
  (let* ((before-size (fold-left + 0 (map length value->keys-table)))
         (new-table
          (minimize-values
           (minimize-keys value->keys-table better-solution)))
         (after-size (fold-left + 0 (map length new-table))))
    (if (= before-size after-size)
        value->keys-table
        (minimize-vktable new-table better-solution))))
The minimized table for the presidents looks like this:
(("washington" "sh" "g..n" "n..o" ".h.n" "a..i")
 ("adams" "a.a" "am" "ad")
 ("madison" "m..i" "i..n" "is." "i.o" "di" "ma" "ad")
 ("monroe" "r.e$" "oe")
 ("van-buren" "u..n" "r.n" ".b" "bu" "-")
 ("harrison" "r..s" "r.i" "i..n" "is." "i.o" "a..i")
 ("polk" "po")
 ("taylor" "ay." "ta")
 ("pierce" "ie." "rc" "r.e$")
 ("buchanan" "bu" "a.a" ".h.n")
 ("lincoln" "i..o" "li")
 ("grant" "an.$" "a.t" "ra" "r.n" "g..n")
 ("hayes" "h..e" "ye" "ay.")
 ("garfield" "el.$" "i.l" "ga" "ie." "r.i" ".f" "a..i")
 ("cleveland" "v.l" "an.$")
 ("mckinley" "n.e" "nl" "i.l" "m..i")
 ("roosevelt" ".se" "oo" "v.l" "el.$" "r..s")
 ("taft" "a.t" "ta" ".f")
 ("wilson" "ls" "i..o")
 ("harding" "r.i" "di" "a..i")
 ("coolidge" "oo" "li")
 ("hoover" "ho" "oo")
 ("truman" "u..n" "ma")
 ("eisenhower" "ho" ".se" "h..e" "i..n" "is.")
 ("kennedy" "nn" "n.e")
 ("johnson" "j")
 ("nixon" "^n" "i..n" "i.o" "n..o")
 ("carter" "rt" "a.t")
 ("reagan" "ga" "a.a")
 ("bush" "bu" "sh")
 ("obama" ".b" "ma" "a.a" "am"))
As you can see, we have reduced the original 2091 matching regexps to fifty.

Changes to the set-cover code coming soon....

Nick LevineMontréal

· 15 days ago
I'm arriving on Tuesday. Will anyone else be around before the lisp conference starts, and are they interested in a little touristing / dining experiences?

Joe MarshallMini regex golf

· 20 days ago
I was intrigued by Peter Norvig's articles about regex golf.

To make things easier to think about, I decided to start with the simpler problem of looking for substrings. Here's code to extract the ngrams of a string:
(define (ngrams-of-length n string)
  (do ((start    0 (1+ start))
       (end      n (1+ end))
       (answer '() (lset-adjoin string=? answer (substring string start end))))
      ((> end (string-length string)) answer)))

(define (ngrams string)
  (do ((n 1 (+ n 1))
       (answer '() (append (ngrams-of-length n string) answer)))
      ((> n (string-length string)) answer)))
A solution is simply a list of ngrams. (Although not every list of ngrams is a solution!)
(define (solution? solution winners losers)
  (let ((matches-solution? (ngram-list-matcher solution)))
    (and (for-all? winners matches-solution?)
         (not (there-exists? losers matches-solution?)))))

(define (ngram-list-matcher ngram-list)
  (lambda (test-string)
    (there-exists? ngram-list 
     (lambda (ngram)
       (string-search-forward ngram test-string)))))
We also want to know if an ngram appears in a given list of strings.
(define (string-list-matcher string-list)
  (lambda (test-ngram)
    (there-exists? string-list
     (lambda (string)
       (string-search-forward test-ngram string)))))

(fluid-let ((*unparser-list-breadth-limit* 10))
    (let ((matches-loser? (string-list-matcher losers)))
      (for-each
       (lambda (winner) (write-string winner) (write-string ": ") 
        (write (reverse (delete-matching-items (ngrams winner) matches-loser?)))
        (newline))
       winners)))

washington: ("sh" "hi" "gt" "to" "was" "ash" "shi" "hin" "ngt" "gto" ...)
adams: ("ad" "am" "ms" "ada" "dam" "ams" "adam" "dams" "adams")
jefferson: ("j" "je" "ef" "ff" "fe" "rs" "jef" "eff" "ffe" "fer" ...)
madison: ("ma" "ad" "di" "mad" "adi" "dis" "iso" "madi" "adis" "diso" ...)
monroe: ("oe" "onr" "nro" "roe" "monr" "onro" "nroe" "monro" "onroe" "monroe")
jackson: ("j" "ja" "ac" "ks" "jac" "ack" "cks" "kso" "jack" "acks" ...)
van-buren: ("-" "va" "n-" "-b" "bu" "van" "an-" "n-b" "-bu" "bur" ...)
harrison: ("har" "arr" "rri" "ris" "iso" "harr" "arri" "rris" "riso" "ison" ...)
polk: ("po" "pol" "olk" "polk")
taylor: ("ta" "yl" "lo" "tay" "ayl" "ylo" "lor" "tayl" "aylo" "ylor" ...)
pierce: ("rc" "ce" "pie" "ier" "erc" "rce" "pier" "ierc" "erce" "pierc" ...)
buchanan: ("bu" "uc" "ch" "na" "buc" "uch" "cha" "ana" "nan" "buch" ...)
lincoln: ("li" "ln" "lin" "col" "oln" "linc" "inco" "ncol" "coln" "linco" ...)
grant: ("ra" "gra" "ran" "ant" "gran" "rant" "grant")
hayes: ("ye" "hay" "aye" "yes" "haye" "ayes" "hayes")
garfield: ("ga" "rf" "fi" "gar" "arf" "rfi" "fie" "iel" "eld" "garf" ...)
cleveland: ("lev" "vel" "ela" "clev" "leve" "evel" "vela" "elan" "cleve" "level" ...)
mckinley: ("nl" "mck" "inl" "nle" "mcki" "kinl" "inle" "nley" "mckin" "ckinl" ...)
roosevelt: ("oo" "os" "lt" "roo" "oos" "ose" "sev" "vel" "elt" "roos" ...)
taft: ("ta" "af" "ft" "taf" "aft" "taft")
wilson: ("ls" "ils" "lso" "wils" "ilso" "lson" "wilso" "ilson" "wilson")
harding: ("di" "har" "ard" "rdi" "din" "hard" "ardi" "rdin" "ding" "hardi" ...)
coolidge: ("oo" "li" "coo" "ool" "oli" "lid" "cool" "ooli" "olid" "lidg" ...)
hoover: ("ho" "oo" "hoo" "oov" "hoov" "oove" "hoove" "oover" "hoover")
truman: ("tr" "ru" "ma" "tru" "rum" "uma" "man" "trum" "ruma" "uman" ...)
eisenhower: ("ei" "nh" "ho" "ow" "eis" "ise" "sen" "enh" "nho" "how" ...)
kennedy: ("nn" "ed" "dy" "ken" "enn" "nne" "ned" "edy" "kenn" "enne" ...)
johnson: ("j" "jo" "oh" "hn" "joh" "ohn" "hns" "john" "ohns" "hnso" ...)
nixon: ("ni" "ix" "xo" "nix" "ixo" "xon" "nixo" "ixon" "nixon")
carter: ("rt" "car" "art" "rte" "cart" "arte" "rter" "carte" "arter" "carter")
reagan: ("ea" "ag" "ga" "rea" "eag" "aga" "gan" "reag" "eaga" "agan" ...)
bush: ("bu" "us" "sh" "bus" "ush" "bush")
clinton: ("li" "to" "cli" "lin" "int" "nto" "ton" "clin" "lint" "into" ...)
obama: ("ob" "ba" "am" "ma" "oba" "bam" "ama" "obam" "bama" "obama")
We can discard ngrams like "shi" because the shorter ngram "sh" will also match.
(define (dominant-ngrams string losing-ngram?)
  (do ((n 1 (+ n 1))
       (answer '() (append
                     (delete-matching-items
                      (ngrams-of-length n string)
                      (lambda (item)
                        (or (there-exists? answer
                                           (lambda (ngram)
                                             (string-search-forward ngram item)))
                            (losing-ngram? item))))
                    answer)))
      ((> n (string-length string)) answer)))


(fluid-let ((*unparser-list-breadth-limit* 10))
    (let ((matches-loser? (string-list-matcher losers)))
      (for-each
       (lambda (winner) (write-string winner) (write-string ": ") 
        (write (dominant-ngrams winner matches-loser?))
        (newline))
       winners)))

washington: ("was" "to" "gt" "hi" "sh")
adams: ("ms" "am" "ad")
jefferson: ("rs" "fe" "ff" "ef" "j")
madison: ("iso" "di" "ad" "ma")
monroe: ("nro" "onr" "oe")
jackson: ("ks" "ac" "j")
van-buren: ("ren" "ure" "bu" "va" "-")
harrison: ("iso" "ris" "rri" "arr" "har")
polk: ("olk" "po")
taylor: ("lo" "yl" "ta")
pierce: ("ier" "pie" "ce" "rc")
buchanan: ("na" "ch" "uc" "bu")
lincoln: ("inco" "col" "ln" "li")
grant: ("ant" "ra")
hayes: ("hay" "ye")
garfield: ("eld" "iel" "fi" "rf" "ga")
cleveland: ("ela" "vel" "lev")
mckinley: ("mck" "nl")
roosevelt: ("vel" "sev" "lt" "os" "oo")
taft: ("ft" "af" "ta")
wilson: ("ls")
harding: ("ard" "har" "di")
coolidge: ("li" "oo")
hoover: ("oo" "ho")
truman: ("ma" "ru" "tr")
eisenhower: ("wer" "sen" "ise" "ow" "ho" "nh" "ei")
kennedy: ("ken" "dy" "ed" "nn")
johnson: ("hn" "oh" "j")
nixon: ("xo" "ix" "ni")
carter: ("car" "rt")
reagan: ("ga" "ag" "ea")
bush: ("sh" "us" "bu")
clinton: ("int" "to" "li")
obama: ("ma" "am" "ba" "ob")
It's time to tackle the set cover problem. We want a set of ngrams that match all the strings. Obviously, if we pick an ngram from each of the strings we want to cover, we'll have a solution. For instance,
(let ((matches-loser? (string-list-matcher losers)))
  (solution? (delete-duplicates
                 (map
                    (lambda (winner) (car (dominant-ngrams winner matches-loser?)))
                    winners))
                winners losers))
;Value: #t
We can cycle through all the possible solutions and then select the best one.
(define (mini-golf0 winners losers)
  (lowest-scoring
   (cover0 (make-dominant-ngram-table
            winners
            (delete-losing-superstrings winners losers)))))

(define (delete-losing-superstrings winners losers)
  (delete-matching-items
   losers
   (lambda (loser)
     (there-exists? winners
                    (lambda (winner)
                      (string-search-forward winner loser))))))

(define (make-dominant-ngram-table winners losers)
  (let ((losing-ngram? (string-list-matcher losers)))
    (map (lambda (winner)
           (cons winner (dominant-ngrams winner losing-ngram?)))
         winners)))

(define (cover0 v-k-table)
  (let ((empty-solution-set (list '())))
    (fold-left add-v-k-entry0 empty-solution-set v-k-table)))

(define (add-v-k-entry0 solution-set v-k-entry)
  (let ((value (car v-k-entry))
        (keys  (cdr v-k-entry)))

    (write-string "Adding value ") (write value) (newline)
    (write-string "   with keys ") (write keys) (newline)
    (write-string "   to ") (write (length solution-set))
    (write-string " partial solutions.") (newline)

    (let ((new-solutions
           (map make-new-solution (cartesian-product solution-set keys))))

      (write-string "Returning ") (write (length new-solutions))
      (write-string " new partial solutions.") (newline)

      new-solutions)))

(define (lowest-scoring list)
  (least-elements list (lambda (l r) (< (score l) (score r)))))

(define (cartesian-product left-list right-list)
  (fold-left (lambda (answer left)
               (fold-left (lambda (answer right)
                            (cons (cons left right) answer))
                          answer
                          right-list))
             '()
             left-list))

(define (make-new-solution cp-term)
  (let ((solution (car cp-term))
        (key (cdr cp-term)))
    (lset-adjoin equal? solution key)))

(define (improper-list-error procedure thing)
  (error (string-append "Improper list found by " procedure ": ") thing))

(define (least-elements list <)
  (define (accumulate-least answer item)
    (cond ((< (car answer) item) answer)
          ((< item (car answer)) (cons item '()))
          (else (cons item answer))))

  (cond ((pair? list) (fold-left accumulate-least
                                 (cons (car list) '())
                                 (cdr list)))
        ((null? list) (error "List must have at least one element." list))
        (else (improper-list-error 'LEAST-ELEMENTS list))))

(define (score solution)
  (do ((tail solution (cdr tail))
       (score -1      (+ score (string-length (car tail)) 1)))
      ((not (pair? tail))
       (if (null? tail)
           score
           (improper-list-error 'score solution)))))
This works for small sets:
1 ]=> (mini-golf0 boys girls)
Adding value "jacob"
   with keys ("ob" "c" "j")
   to 1 partial solutions.
Returning 3 new partial solutions.
Adding value "mason"
   with keys ("as")
   to 3 partial solutions.
Returning 3 new partial solutions.
Adding value "ethan"
   with keys ("an" "ha")
   to 3 partial solutions.
Returning 6 new partial solutions.
Adding value "noah"
   with keys ("ah" "oa" "no")
   to 6 partial solutions.
Returning 18 new partial solutions.
Adding value "william"
   with keys ("lia" "lli" "ill" "am" "w")
   to 18 partial solutions.
Returning 90 new partial solutions.
Adding value "liam"
   with keys ("lia" "am")
   to 90 partial solutions.
Returning 180 new partial solutions.
Adding value "jayden"
   with keys ("en" "de" "yd" "ay" "j")
   to 180 partial solutions.
Returning 900 new partial solutions.
Adding value "michael"
   with keys ("ae" "ha" "c")
   to 900 partial solutions.
Returning 2700 new partial solutions.
Adding value "alexander"
   with keys ("de" "nd" "an" "le" "al" "r" "x")
   to 2700 partial solutions.
Returning 18900 new partial solutions.
Adding value "aiden"
   with keys ("en" "de" "id")
   to 18900 partial solutions.
Returning 56700 new partial solutions.
;Value 41: (("de" "am" "ah" "ha" "as" "j")
            ("de" "am" "ah" "ha" "as" "j")
            ("de" "am" "oa" "ha" "as" "j")
            ("de" "am" "oa" "ha" "as" "j")
            ("de" "am" "no" "ha" "as" "j")
            ("de" "am" "no" "ha" "as" "j")
            ("de" "am" "ah" "ha" "as" "c")
            ("de" "am" "ah" "ha" "as" "c")
            ("de" "am" "oa" "ha" "as" "c")
            ("de" "am" "oa" "ha" "as" "c")
            ("de" "am" "no" "ha" "as" "c")
            ("de" "am" "no" "ha" "as" "c")
            ("de" "am" "ah" "an" "as" "c")
            ("de" "am" "ah" "an" "as" "c")
            ("en" "am" "ah" "an" "as" "c")
            ("de" "am" "oa" "an" "as" "c")
            ("de" "am" "oa" "an" "as" "c")
            ("en" "am" "oa" "an" "as" "c")
            ("de" "am" "no" "an" "as" "c")
            ("de" "am" "no" "an" "as" "c")
            ("en" "am" "no" "an" "as" "c"))
But you can see that we won't be able to go much beyond this because there are just too many combinations. We can cut down on the intermediate partial solutions by noticing that many of them are redundant. We don't need to keep partial solutions that cannot possibly lead to a shortest final solution. The various partial solutions each (potentially) match different sets of words. We only need keep the shortest solution for each different set of matched words. Furthermore, if a solution's matches are a superset of another's matches, and the other is the same length or longer, then the solution is dominated by the other and will always be at least the length of the longer.
(define (mini-golf1 winners losers)
  (cover1
   (make-dominant-ngram-table winners (delete-losing-superstrings winners losers))
   lowest-scoring))

(define (cover1 v-k-table lowest-scoring)
  (let ((empty-solution-set (list '())))

    (define (add-v-k-entry solution-set v-k-entry)
      (let ((value (car v-k-entry))
            (keys  (cdr v-k-entry)))

        (write-string "Adding value ") (write value) (newline)
        (write-string "   with keys ") (write keys) (newline)
        (write-string "   to ") (write (length solution-set))
        (write-string " partial solutions.") (newline)

        (let ((new-solutions
               (map make-new-solution (cartesian-product solution-set keys))))

          (let ((trimmed-solutions (trim-partial-solutions new-solutions)))

            (write-string "Returning ") (write (length trimmed-solutions))
            (write-string " of ") (write (length new-solutions))
            (write-string " new partial solutions.") (newline)

            trimmed-solutions))))

    (define (trim-partial-solutions partial-solutions)
      (let ((equivalent-solutions (collect-equivalent-partial-solutions partial-solutions)))
        (write-string "  Deleting ")
        (write (- (length partial-solutions) (length equivalent-solutions)))
        (write-string " equivalent partial solutions.")
        (newline)

        (remove-dominated-solutions
         (map lowest-scoring-equivalent-partial-solution equivalent-solutions))))

    (define (lowest-scoring-equivalent-partial-solution entry)
      (first (lowest-scoring (car entry))))

    (define (collect-equivalent-partial-solutions alist)
      ;; Add each entry in turn.
      (fold-left (lambda (equivalents partial-solution)
                   (add-equivalent-partial-solution
                    partial-solution
                    (partial-solution-matches partial-solution)
                    equivalents))
                 '() alist))

    (define (partial-solution-matches partial-solution)
      (keep-matching-items v-k-table
        (lambda (entry)
          (there-exists? partial-solution
                         (lambda (key) (member key (cdr entry)))))))

    (define (remove-dominated-solutions partial-solutions)
      (let ((before-length (length partial-solutions)))
        (let ((answer  (map car (fold-left (lambda (answer solution)
                                             (if (there-exists? answer (dominates-solution? solution))
                                                 answer
                                                 (cons solution answer)))
                                           '()
                                           (map (lambda (partial-solution)
                                                  (cons partial-solution (partial-solution-matches partial-solution)))
                                                partial-solutions)))))
          (let ((after-length (length answer)))
            (write-string "  Deleting ") (write (- before-length after-length))
            (write-string " dominated solutions.")
            (newline)
            answer))))

    (lowest-scoring
     (fold-left add-v-k-entry empty-solution-set v-k-table))))

(define (dominates-solution? solution)
  (let ((partial-solution (car solution))
        (solution-matches (cdr solution)))
    (lambda (other-solution)
      (let ((other-partial-solution (car other-solution))
            (other-matches (cdr other-solution)))
        (and (not (equal? solution-matches other-matches))
             (superset? other-matches solution-matches)
             (<= (score other-partial-solution) (score partial-solution)))))))

(define (add-equivalent-partial-solution solution value alist)
  (cond ((pair? alist)
         (let ((entry (car alist))
               (tail (cdr alist)))
           (let ((entry-solutions (car entry))
                 (entry-value (cdr entry)))
             (if (equal? value entry-value)
                 (if (member solution entry-solutions)
                     alist
                     (cons (cons (cons solution entry-solutions) value)
                           tail))
                 (cons entry (add-equivalent-partial-solution solution value tail))))))
        ((null? alist) (list (cons (list solution) value)))
        (else (improper-list-error 'collect-equivalents alist))))
1 ]=> (mini-golf1 winners losers)
Adding value "washington"
   with keys ("was" "to" "gt" "hi" "sh")
   to 1 partial solutions.
  Deleting 2 equivalent partial solutions.
  Removing 1 dominated solutions.
Returning 2 of 5 new partial solutions.
Adding value "adams"
   with keys ("ms" "am" "ad")
   to 2 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 2 dominated solutions.
Returning 4 of 6 new partial solutions.
Adding value "jefferson"
   with keys ("rs" "fe" "ff" "ef" "j")
   to 4 partial solutions.
  Deleting 12 equivalent partial solutions.
  Removing 4 dominated solutions.
Returning 4 of 20 new partial solutions.
Adding value "madison"
   with keys ("iso" "di" "ad" "ma")
   to 4 partial solutions.
  Deleting 2 equivalent partial solutions.
  Removing 2 dominated solutions.
Returning 12 of 16 new partial solutions.
Adding value "monroe"
   with keys ("nro" "onr" "oe")
   to 12 partial solutions.
  Deleting 24 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 12 of 36 new partial solutions.
Adding value "jackson"
   with keys ("ks" "ac" "j")
   to 12 partial solutions.
  Deleting 24 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 12 of 36 new partial solutions.
Adding value "van-buren"
   with keys ("ren" "ure" "bu" "va" "-")
   to 12 partial solutions.
  Deleting 36 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 24 of 60 new partial solutions.
Adding value "harrison"
   with keys ("iso" "ris" "rri" "arr" "har")
   to 24 partial solutions.
  Deleting 96 equivalent partial solutions.
  Removing 12 dominated solutions.
Returning 12 of 120 new partial solutions.
Adding value "polk"
   with keys ("olk" "po")
   to 12 partial solutions.
  Deleting 12 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 12 of 24 new partial solutions.
Adding value "taylor"
   with keys ("lo" "yl" "ta")
   to 12 partial solutions.
  Deleting 12 equivalent partial solutions.
  Removing 12 dominated solutions.
Returning 12 of 36 new partial solutions.
Adding value "pierce"
   with keys ("ier" "pie" "ce" "rc")
   to 12 partial solutions.
  Deleting 36 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 12 of 48 new partial solutions.
Adding value "buchanan"
   with keys ("na" "ch" "uc" "bu")
   to 12 partial solutions.
  Deleting 39 equivalent partial solutions.
  Removing 3 dominated solutions.
Returning 6 of 48 new partial solutions.
Adding value "lincoln"
   with keys ("inco" "col" "ln" "li")
   to 6 partial solutions.
  Deleting 15 equivalent partial solutions.
  Removing 6 dominated solutions.
Returning 3 of 24 new partial solutions.
Adding value "grant"
   with keys ("ant" "ra")
   to 3 partial solutions.
  Deleting 3 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 3 of 6 new partial solutions.
Adding value "hayes"
   with keys ("hay" "ye")
   to 3 partial solutions.
  Deleting 3 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 3 of 6 new partial solutions.
Adding value "garfield"
   with keys ("eld" "iel" "fi" "rf" "ga")
   to 3 partial solutions.
  Deleting 9 equivalent partial solutions.
  Removing 3 dominated solutions.
Returning 3 of 15 new partial solutions.
Adding value "cleveland"
   with keys ("ela" "vel" "lev")
   to 3 partial solutions.
  Deleting 3 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 6 of 9 new partial solutions.
Adding value "mckinley"
   with keys ("mck" "nl")
   to 6 partial solutions.
  Deleting 6 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 6 of 12 new partial solutions.
Adding value "roosevelt"
   with keys ("vel" "sev" "lt" "os" "oo")
   to 6 partial solutions.
  Deleting 24 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 6 of 30 new partial solutions.
Adding value "taft"
   with keys ("ft" "af" "ta")
   to 6 partial solutions.
  Deleting 12 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 6 of 18 new partial solutions.
Adding value "wilson"
   with keys ("ls")
   to 6 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 6 of 6 new partial solutions.
Adding value "harding"
   with keys ("ard" "har" "di")
   to 6 partial solutions.
  Deleting 12 equivalent partial solutions.
  Removing 2 dominated solutions.
Returning 4 of 18 new partial solutions.
Adding value "coolidge"
   with keys ("li" "oo")
   to 4 partial solutions.
  Deleting 4 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 4 of 8 new partial solutions.
Adding value "hoover"
   with keys ("oo" "ho")
   to 4 partial solutions.
  Deleting 4 equivalent partial solutions.
  Removing 2 dominated solutions.
Returning 2 of 8 new partial solutions.
Adding value "truman"
   with keys ("ma" "ru" "tr")
   to 2 partial solutions.
  Deleting 4 equivalent partial solutions.
  Removing 1 dominated solutions.
Returning 1 of 6 new partial solutions.
Adding value "eisenhower"
   with keys ("wer" "sen" "ise" "ow" "ho" "nh" "ei")
   to 1 partial solutions.
  Deleting 6 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 1 of 7 new partial solutions.
Adding value "kennedy"
   with keys ("ken" "dy" "ed" "nn")
   to 1 partial solutions.
  Deleting 3 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 1 of 4 new partial solutions.
Adding value "johnson"
   with keys ("hn" "oh" "j")
   to 1 partial solutions.
  Deleting 2 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 1 of 3 new partial solutions.
Adding value "nixon"
   with keys ("xo" "ix" "ni")
   to 1 partial solutions.
  Deleting 2 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 1 of 3 new partial solutions.
Adding value "carter"
   with keys ("car" "rt")
   to 1 partial solutions.
  Deleting 1 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 1 of 2 new partial solutions.
Adding value "reagan"
   with keys ("ga" "ag" "ea")
   to 1 partial solutions.
  Deleting 2 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 1 of 3 new partial solutions.
Adding value "bush"
   with keys ("sh" "us" "bu")
   to 1 partial solutions.
  Deleting 2 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 1 of 3 new partial solutions.
Adding value "clinton"
   with keys ("int" "to" "li")
   to 1 partial solutions.
  Deleting 2 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 1 of 3 new partial solutions.
Adding value "obama"
   with keys ("ma" "am" "ba" "ob")
   to 1 partial solutions.
  Deleting 3 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 1 of 4 new partial solutions.
;Value 47: (("rt" "ni" "nn" "ho" "ls" "nl" "vel" "ga" "ye" "ra" "li" "rc" "ta" "po" "har" "bu" "oe" "ma" "j" "ad" "sh"))
The cover procedure takes a table that maps values to the keys that cover them. If we can reduce the size of that table without changing the solution, we'll run faster. If there are two entries in the table such that the keys of one are a superset of the keys of the other, we can discard the superset: the smaller of the two entries will be in the solution, and any key that matches the smaller one will automatically match the larger one as well. Also, if two values have the same set of keys that match them, we need only include one of the values in the table.
(define (delete-dominated-values v-k-table)
  (let ((size-before (length v-k-table)))

    (define (dominated-value? entry)
      (let ((entry-value (car entry))
            (entry-keylist (cdr entry)))
        (there-exists? v-k-table
          (lambda (other-entry)
            (and (not (eq? entry other-entry))
                 (let ((other-value (car other-entry))
                       (other-keylist (cdr other-entry)))
                   (and (superset? entry-keylist other-keylist)
                        (not (equal? other-keylist entry-keylist)))))))))

    (define (equivalent-value-in-answer? answer entry)
      (let ((entry-value (car entry))
            (entry-keylist (cdr entry)))
        (there-exists? answer
          (lambda (other-entry)
            (let ((other-value (car other-entry))
                  (other-keylist (cdr other-entry)))
              (equal? entry-keylist other-keylist))))))

    (define (add-entry answer entry)
      (if (or (equivalent-value-in-answer? answer entry)
              (dominated-value? entry))
          answer
          (cons entry answer)))

    (let ((answer (fold-left add-entry '() v-k-table)))
      (write-string "Removed ") (write (- size-before (length answer)))
      (write-string " dominated and equivalent values.")
      (newline)
      answer)))

(define (superset? bigger smaller)
  (for-all? smaller (lambda (s) (member s bigger))))

(define (mini-golf2 winners losers)
  (cover1
   (delete-dominated-values
    (make-dominant-ngram-table winners (delete-losing-superstrings winners losers)))
   lowest-scoring))

;;;;;;;;
;; Delete dominated keys from the keylists.

(define (mini-golf3 winners losers)
  (cover1
   (delete-dominated-keys-and-values
    (make-dominant-ngram-table winners (delete-losing-superstrings winners losers))
    (lambda (left right)
      (or (< (string-length left) (string-length right))
          (and (= (string-length left) (string-length right))
               (string<? left right)))))
   lowest-scoring))

(define (delete-dominated-keys-and-values v-k-table better-key)
  (let ((before-size (fold-left * 1 (map length v-k-table))))
    (let ((new-table (delete-dominated-values
                      (delete-dominated-keys v-k-table better-key))))
      (let ((after-size (fold-left * 1 (map length new-table))))
        (if (= before-size after-size)
            v-k-table
            (delete-dominated-keys-and-values new-table better-key))))))

(define (delete-dominated-keys v-k-table better-key)
  (let ((all-keys (get-all-keys v-k-table)))

    (define (lookup-key key)
      (cons key
            (map car
                 (keep-matching-items v-k-table
                                      (lambda (v-k-entry)
                                        (member key (cdr v-k-entry)))))))

    (let ((k-v-table (map lookup-key all-keys)))

      (define (dominated-key? key)
        (let ((values (cdr (assoc key k-v-table))))
          (there-exists? k-v-table
                         (lambda (entry)
                           (let ((entry-key (car entry))
                                 (entry-values (cdr entry)))
                             (and (superset? entry-values values)
                                  (not (equal? values entry-values))
                                  (or (< (string-length entry-key) (string-length key))
                                      (and (= (string-length entry-key) (string-length key))
                                           (string<? entry-key key)))))))))

      (define (equivalent-key-in-answer? answer key)
        (let ((values (cdr (assoc key k-v-table))))
          (there-exists? answer
                         (lambda (entry-key)
                           (let ((entry-values (cdr (lookup-key entry-key))))
                             (equal? values entry-values))))))

      (define (add-keys answer key)
        (if (or (dominated-key? key)
                (equivalent-key-in-answer? answer key))
            answer
            (cons key answer)))

      (let ((good-keys (fold-left add-keys '() (sort all-keys better-key))))
        (write-string "Removed ") (write (- (length all-keys) (length good-keys)))
        (write-string " of ") (write (length all-keys)) (write-string " keys.")(newline)

        (map (lambda (entry)
               (cons (car entry)
                     (keep-matching-items (cdr entry) (lambda (key) (member key good-keys)))))
             v-k-table)))))

(define (get-all-keys v-k-table)
  (fold-left (lambda (answer entry)
               (fold-left (lambda (answer key)
                            (lset-adjoin equal? answer key))
                          answer
                          (cdr entry)))
             '()
             v-k-table))
Trimming the table this way helps a lot. We can now compute the dogs vs. cats.
1 ]=> (mini-golf3 dogs cats)

Removed 294 of 405 keys.
Removed 44 dominated and equivalent values.
Removed 25 of 93 keys.
Removed 15 dominated and equivalent values.
Removed 7 of 62 keys.
Removed 0 dominated and equivalent values.
Removed 0 of 55 keys.
Removed 0 dominated and equivalent values.
Adding value "BORZOIS"
   with keys ("OIS" "BOR" "RZ")
   to 1 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 3 of 3 new partial solutions.
Adding value "GIANT SCHNAUZERS"
   with keys ("SCH" "HN")
   to 3 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 6 of 6 new partial solutions.
Adding value "BASENJIS"
   with keys ("JI")
   to 6 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 6 of 6 new partial solutions.
Adding value "ENGLISH SETTERS"
   with keys ("TERS" "ETT")
   to 6 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 12 of 12 new partial solutions.
Adding value "JAPANESE CHIN"
   with keys ("CHI")
   to 12 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 12 of 12 new partial solutions.
Adding value "BOUVIERS DES FLANDRES"
   with keys ("S F" "DES" " DE" "IER" "FL" "VI")
   to 12 partial solutions.
  Deleting 8 equivalent partial solutions.
  Removing 8 dominated solutions.
Returning 56 of 72 new partial solutions.
Adding value "PEKINGESE"
   with keys ("EKI")
   to 56 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 56 of 56 new partial solutions.
Adding value "BELGIAN MALINOIS"
   with keys (" MAL" "OIS" "LG")
   to 56 partial solutions.
  Deleting 96 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 72 of 168 new partial solutions.
Adding value "GERMAN WIREHAIRED POINTERS"
   with keys ("TERS" "D P")
   to 72 partial solutions.
  Deleting 108 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 36 of 144 new partial solutions.
Adding value "CHOW CHOWS"
   with keys ("W ")
   to 36 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 36 of 36 new partial solutions.
Adding value "SAMOYEDS"
   with keys ("DS")
   to 36 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 36 of 36 new partial solutions.
Adding value "DOGUES DE BORDEAUX"
   with keys ("BOR" " DE" "GU")
   to 36 partial solutions.
  Deleting 88 equivalent partial solutions.
  Removing 2 dominated solutions.
Returning 18 of 108 new partial solutions.
Adding value "DALMATIANS"
   with keys ("ANS" "LM")
   to 18 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 36 of 36 new partial solutions.
Adding value "LHASA APSOS"
   with keys ("LH")
   to 36 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 36 of 36 new partial solutions.
Adding value "CANE CORSO"
   with keys (" COR" "ORS")
   to 36 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 72 of 72 new partial solutions.
Adding value "ALASKAN MALAMUTES"
   with keys (" MAL" "TES" "LAS" "KA")
   to 72 partial solutions.
  Deleting 184 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 104 of 288 new partial solutions.
Adding value "WHIPPETS"
   with keys ("IP")
   to 104 partial solutions.
  Deleting 0 equivalent partial solutions.
;GC #199: took:   0.20   (1%) CPU time,   0.10   (1%) real time; free: 16754359
  Removing 0 dominated solutions.
Returning 104 of 104 new partial solutions.
Adding value "SHIBA INU"
   with keys ("SHI" " I")
   to 104 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 208 of 208 new partial solutions.
Adding value "AKITAS"
   with keys ("AK")
   to 208 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 208 of 208 new partial solutions.
Adding value "RHODESIAN RIDGEBACKS"
   with keys ("DES" "DG" "OD")
   to 208 partial solutions.
  Deleting 304 equivalent partial solutions.
  Removing 144 dominated solutions.
Returning 176 of 624 new partial solutions.
Adding value "BICHONS FRISES"
   with keys ("S F" "FR")
   to 176 partial solutions.
  Deleting 224 equivalent partial solutions.
  Removing 16 dominated solutions.
Returning 112 of 352 new partial solutions.
Adding value "PAPILLONS"
   with keys ("API")
   to 112 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 112 of 112 new partial solutions.
Adding value "COLLIES"
   with keys ("IES")
   to 112 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 112 of 112 new partial solutions.
Adding value "VIZSLAS"
   with keys ("LAS" "IZ" "VI")
   to 112 partial solutions.
;GC #200: took:   0.10   (0%) CPU time,   0.10   (1%) real time; free: 16757322
  Deleting 272 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 64 of 336 new partial solutions.
Adding value "BRITTANYS"
   with keys ("ITT")
   to 64 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 64 of 64 new partial solutions.
Adding value "PUGS"
   with keys ("GS")
   to 64 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 64 of 64 new partial solutions.
Adding value "HAVANESE"
   with keys ("HAVANE")
   to 64 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 64 of 64 new partial solutions.
Adding value "COCKER SPANIELS"
   with keys ("ANI" "LS")
   to 64 partial solutions.
  Deleting 80 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 48 of 128 new partial solutions.
Adding value "MASTIFFS"
   with keys ("FS")
   to 48 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 48 of 48 new partial solutions.
Adding value "MALTESE"
   with keys ("TES" "LT")
   to 48 partial solutions.
  Deleting 72 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 24 of 96 new partial solutions.
Adding value "PEMBROKE WELSH CORGIS"
   with keys (" COR" "LS")
   to 24 partial solutions.
  Deleting 32 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 16 of 48 new partial solutions.
Adding value "BOSTON TERRIERS"
   with keys ("IER" " T")
   to 16 partial solutions.
  Deleting 24 equivalent partial solutions.
  Removing 4 dominated solutions.
Returning 4 of 32 new partial solutions.
Adding value "POMERANIANS"
   with keys ("ANS" "ANI")
   to 4 partial solutions.
  Deleting 6 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 2 of 8 new partial solutions.
Adding value "GREAT DANES"
   with keys ("GR")
   to 2 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 2 of 2 new partial solutions.
Adding value "DOBERMAN PINSCHERS"
   with keys ("SCH" " PI")
   to 2 partial solutions.
  Deleting 3 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 1 of 4 new partial solutions.
Adding value "SHIH TZU"
   with keys ("SHI" " T")
   to 1 partial solutions.
  Deleting 1 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 1 of 2 new partial solutions.
Adding value "ROTTWEILERS"
   with keys ("EI")
   to 1 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 1 of 1 new partial solutions.
Adding value "POODLES"
   with keys ("DL" "OD")
   to 1 partial solutions.
  Deleting 1 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 1 of 2 new partial solutions.
Adding value "BOXERS"
   with keys ("OX")
   to 1 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 1 of 1 new partial solutions.
Adding value "BEAGLES"
   with keys ("AGL")
   to 1 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 1 of 1 new partial solutions.
Adding value "LABRADOR RETRIEVERS"
   with keys ("VE")
   to 1 partial solutions.
  Deleting 0 equivalent partial solutions.
  Removing 0 dominated solutions.
Returning 1 of 1 new partial solutions.
;Value 50: (("VE" "AGL" "OX" "EI" "GR" " T" "FS" "LS" "HAVANE" "GS" "ITT" "IES" "API" "FR" "OD" "AK" " I" "IP" "TES" "ORS" "LH" "ANS" "GU" "DS" "W " "EKI" "VI" "CHI" "TERS" "JI" "SCH" "OIS"))
We appear to have the substring version of regex golf under control. Can we extend it to actual regular expressions? Of course we can. In the next installment...

Colin LuptonHacking Lisp in the Cloud, Pt. 3

· 28 days ago

Cloud9 -- New website and 3rd gen browser-based IDEToday Cloud9 announced the release of their new IDE to all customers. They also released their new website. The hiccups in the beta were all pretty minor, and were resolved quickly after reporting the bugs. Now, everyone can enjoy all the awesome new features.

The Cloud9 IDE supports more than 40 programming languages, Common Lisp included. As I mentioned in my previous post about the Beta, there are all sorts of new features that support a cleaner Lisp development cycle over the previous version—including auto-completion, file outline of top-level definition forms, custom runners, split-screen views, and more, all built on top of an Ubuntu workspace with sudo privileges. They’ve also streamlined the interface, collaboration tools, terminal, and over-all performance of the IDE.

workspace There are so many new features to go through, it’s a little hard to know where to start. But let’s start with the custom runners, since you’ll definitely be wanting to run your Lisp software you write in your shiny new integrated, collaborative development and testing environment.

First of all, after you create a new workspace or migrate an old one to the new Cloud9, you’ll want to install SBCL, RLWRAP, and Quicklisp. You can install SBCL and RLWRAP from Apt, but if you want the latest and greatest version of SBCL, see SBCL: Getting Started and follow the instructions to install the binary release of the latest SBCL for Linux x86-64. You will need to run the install script with sudo.

Verify that SBCL and RLWRAP are installed correctly: in your terminal, run sudo rlwrap sbcl. If you get to the SBCL prompt, and you can evaluate an expression, you’re good to go. You can then proceed with installing Quicklisp as normal.

Writing a Runner is pretty simple. In the project directory tree, you’ll notice a little gear icon with an arrow. Click on this menu, and make sure “Show Hidden Files” is checked. Then from Run > Run With > New Runner, you can create a new Runner script from the built-in template. Save it as “SBCL.run” under .c9/runners/, and edit it to look like this:

{
    "cmd" : ["sudo", "rlwrap", "sbcl", "--load", "$file", "$args"],
    "info" : "Started SBCL :: $project_path$file_name",
    "env" : {},
    "selector" : "source.ext"
}

If you have a full ASDF project, you can create a Lisp load script to send to the Runner that adds your workspace folder to asdf:*central-registry*, loads it and all its dependencies with Quicklisp, and (say, in the case of a web-app), starts it for you. You can also add some sanity checks to this file, and output some status messages based on your app. Please note, the address and port to run your web-apps is 0.0.0.0:8080.

Armed with this load script, you can now create a new Run Configuration with Run > Run Configurations > New Run Configuration. This will open a new Runner tab where your terminal is, at the bottom of the screen. You can give this Run Configuration a name, enter a “command” to run, select the Runner you want to use, and set up any environment variables you might need. In the case of this Run Configuration, the Command should just be the name of your Lisp load script. Once you’re done all that, you can just press the Run button in the runner tab next to the fields you completed, and the Runner will drop you into the SBCL REPL. If it’s a web app, you can see it with the built-in browser preview. Select the Preview button on the main menu, and then Preview with Web Server menu item that pops down. Otherwise, you can interact with your application in the Runner REPL just like you normally would on your computer.

If you just want to run an individual file, you can set up the SBCL Runner as your project default. Then you can just hit “Run” on the main menu, and it will run the currently active file by loading it in SBCL.

Go ahead and create your own Runners now, to fit into your normal workflow! And don’t forget to explore some of the other cool new features, like auto-completion and the file outline of your top-level definition forms.

That’s all for now. As always, Happy Hacking!


Pascal CostanzaA Lisper's first impression of Julia

· 32 days ago
I have recently looked at Julia, a new programming language developed at MIT that promises to be a dynamic programming language that is suitable for scientific computing with a high-performance implementation. It is an interesting project that heavily borrows from Common Lisp, Dylan, and Scheme, and you can rightfully argue that Julia itself is actually a Lisp dialect. While I wasn't very impressed with some other recent Lisp dialects (Arc, Clojure), Julia puts a couple of very interesting features on the table. Below is a discussion of the more salient aspects of Julia, as seen from a Common Lispers perspective. It is based on the documentation of the prerelease version 0.3 of Julia.

Julia is closest to Dylan in many regards. It uses a somewhat mainstream syntax rather than s-expressions. Unlike Dylan, you can nevertheless write 'full' macros, since macro definitions are implemented in Julia, not some template language, and backquote/quasiquote is integrated with the Julia syntax. Julia is a Lisp-1 (like Scheme or Dylan) rather than a Lisp-2 (like Common Lisp or ISLISP), which makes it necessary to add macro hygiene features. Fortunately, this does not mean you have to deal with the rather painful syntax-case construct of some Scheme dialects, but you can still use far simpler backquote/quasiquote constructions, just with macro hygiene taken care of by default. Julia also allows you to selectively break hygiene. Although I usually strongly prefer the simplicity of Common Lisp's non-hygienic macro system, the fact that Julia is a Lisp-1 turns macro hygiene into a real problem, so I guess this is a reasonable design.

Julia provides object-oriented programming from the ground up, similar to Dylan. It centers on generic functions rather than classes, where methods are defined outside classes and allow for multiple dispatch, just like in Dylan and Common Lisp. Like Dylan, and unlike Common Lisp, it does not distinguish between functions and generic functions: All functions can have methods, you do not have to make up your mind whether you want methods or plain functions. Unlike in Common Lisp, there are no method combinations, no before/after/around methods, and call-next-method is not directly supported, but has to be done manually. This is probably to simplify method dispatch, maybe to have some performance advantages, though I find it hard to imagine that adding method combinations would make things substantially worse.

You still need a class hierarchy to drive method dispatch. Unlike in Common Lisp, there is no multiple inheritance, only single inheritance. In fact, there is actually no real inheritance, because in Julia, only leaf classes of the class hierarchy are allowed to define slots/fields. All superclasses are required to be "abstract," without any slot definitions. Also, Julia classes cannot be redefined at runtime, so in fact Julia classes are much closer to Common Lisp's structured types rather than classes.

Julia's execution model is based on dynamic compilation. As a user, you don't have to compile your code at all, source code is just compiled on the fly (similar as in Clozure Common Lisp). Julia inlines functions on the fly, including generic functions, and can de-optimize when function definitions change at runtime. This is more flexible than in Common Lisp, where inlined functions can get out of sync with their potentially changed definitions. Also, while the Common Lisp specification does not say anything with regard to being able to inline generic functions or not, there are aspects in the CLOS MOP specification that prevent generic functions from being inlined, at least for user-defined extensions of generic functions. Julia definitely seems more "modern" here.

In Julia, there is no distinction between variable binding and variable assignment. If you assign to a variable that has not been used before in the same lexical environment, it is silently introduced. In Common Lisp/Scheme/Dylan, there is a distinction between 'let forms that introduce variable bindings, and assignments (setq/setf/set!) that perform assignments. I'm highly skeptical of Julia's design here, because this potentially leads to bugs that are hard to find: A simple typo in your source code just may go unnoticed.

In Julia, all variables are lexically scoped (except for some seemingly quirky scoping semantics for global variables, see below). There are no special / dynamically scoped variables in Julia, which is a major omission in my book. Some academics don't like special scoping, but their presence in Common Lisp is incredibly useful in practice, especially but not only for multi-threading!

Julia's default representation for integers is either 32-bit or 64-bit integers, depending on the target architecture, which silently wrap around. Julia also supports "BigInts" that can be arbitrarily large, but you have to ask for them explicitly. In Common Lisp, integers are by default arbitrarily large, which I think is an advantage. Due to type tagging in Common Lisp implementations, even "big" integers are typically allocated as immediate values rather than on the heap when they fall into the "fixnum" range. I didn't find anything in the Julia documentation that discusses this aspect of "BigInt."

In Julia, all mathematical operations are generic functions and can be extended by user-defined methods. This is a strong advantage for Julia. In Common Lisp, mathematical operations are "plain" functions which cannot be extended. Due to some aspects in the design of Common Lisp's generic functions, it's hard to inline (or open-code) them, which is why for performance reasons, it's better to express mathematical (and other such performance-critical functions) as "plain" functions. Apart from that, the support for number types seems to be on par between Julia and Common Lisp (complex types, rational numbers, floating point numbers, etc.)

In Julia, strings are unicode strings by default. My knowledge about unicode support in Common Lisp implementations is limited, so I cannot really make any comparisons here. One interesting aspect in Julia's string support is that there can be user-defined macros to parse them and construct other syntactic entities out of them. This feels somewhat similar to read macros in Common Lisp, although with a slightly different scope.

Julia's support for functions is similar to Common Lisp: They can be first class and anonymous (lambda expressions). There are varargs (&rest), optional and keyword arguments. In Common Lisp, optional and keyword arguments cannot be dispatched on in methods. In Julia, optional arguments can be dispatched on, but not keywords. (This is a pity, dispatch on keyword arguments would be very interesting, and is something I wanted to add as part of Closer to MOP for a long time!)

Julia's support for control flow is much more limited than in Common Lisp. There are equivalents for progn, cond/if, for and while loops. Unlike Common Lisp, there is no support for a full loop facility, or even for a simple goto construct. Common Lisp clearly wins here. Julia's support for exception handling is also limited: No handler-bind, no restarts, unlike in Common Lisp, which are also really useful features.

Julia's type system has some interesting differences to Common Lisp: There is a distinction between mutable and immutable classes. Immutable classes disallow any side effects on their fields. This seems to be primarily directed at enabling stack allocation as an optimization. In Common Lisp, you would use dynamic extent declarations when allocating structs (or other data types) to achieve similar performance improvements. I'm not sure why it would matter that the fields need to be read-only for such an optimization, but if this covers most cases, maybe this is good enough.

Julia allows for returning and receiving multiple values from function calls, similar to Common Lisp. This is a feature I like a lot in Common Lisp, so I'm happy it's also in Julia. In Julia, this is achieved by an explicit tuple type representation which doesn't exist in this form in Common Lisp. In Lisp, you could also return/receive lists instead of multiple values, which would correspond to this kind of tuple type, but lists add an additional performance overhead, which multiple values and, presumably, tuples in Julia don't have.

Julia supports parametric types. I don't see at the moment why this is relevant. You could achieve similar functionality also with some macrology. Maybe I'm missing something here.

There is a whole section on constructors (make-instance / make-struct) in the Julia manual. This makes me suspicious, this should be an easier topic.

Julia has a module system. It supports export and automatic import of explicitly exported identifiers. You can also still access non-exported identifiers with additional syntax. This is good, because module designers may not always perfectly anticipate what users actually need to access. Common Lisp's package system supports a similar distinction between external and internal definitions that can be accessed in different ways. I slightly prefer Common Lisp's ability to use the package name as a prefix even for explicitly exported definitions. There is no feature in Julia to rename imported identifiers, which is something where Common Lisp's support for explicit package name prefixes can come in very handy. I would like to see something like Oberon's support for renaming identifiers on import in some Lisp dialect someday, because I believe that is the most complete solution for dealing with potential name conflicts.

In terms of meta-programming, apart from macros, Julia also supports (top-level) eval, like Common Lisp. Julia's support for "reflection" is much weaker than Common Lisp's CLOS MOP: You can only inspect types at runtime, but you cannot modify them (and language designers should stop calling something "reflection" that is clearly just "introspection").

Both Julia and Common Lisp support multi-dimensional arrays. Common Lisp's arrays are in row-major order, starting at index 0 in every dimension. Julia's arrays are column-major order, starting at index 1 in every dimension. Julia's support for multi-dimensional arrays is a library feature, whereas Common Lisp's support is built into the language. Julia supports both dense and sparse matrices, where Common Lisp supports only dense matrices out of the box.

There are a lot of libraries that ship with Julia targeted at scientific computing.

Julia supports parallel programming with a model built on top of message passing: If you want to run parallel algorithms, you essentially start several instances of Julia that communicate with each other. The model does not support shared memory, and there is no multi-threading within a Julia instance (although there seem to be discussions among the Julia designers to add this in the future). The model is built on top of MPI as an implementation backend. However, the actual programming model supports single-sided communication: You can ask a function to be executed in some other Julia worker process, and can later synchronize with it to fetch results. On top of that, there are some high-level constructs provided as library features, such parallel maps and loops. Julia's message passing model ensures that within a Julia instance, only one task is executed at a time, so there is yet no need to provide low-level synchronization mechanisms, such as locks or atomic operations. The lack of shared-memory parallelism is problematic because many parallel algorithms that are very easy to express with shared memory become quite complicated in a distributed memory setting. On the other hand, Julia's model easily supports true distributed programming: You can configure Julia to run several instances across a cluster, and use them in a quite straightforward way: substantially easier than what you have to do with, say, MPI, and much closer with regard to ease of use to modern PGAS languages like Chapel or X10.

The ANSI specification for Common Lisp does not mention anything about multi-threading or parallel programming at all, but many Common Lisp implementations add support for shared-memory parallelism. I will not go into details here, but let me just briefly state that, for example, the LispWorks implementation of Common Lisp provides excellent support for symmetric multiprocessing that is at least on par with what you can find in most other language implementations in terms of parallel programming support. However, unfortunately, support for true distributed memory models seems almost non-existent in Common Lisp, apart for some basic support for MPI in a library that was maintained only for a very short period of time a couple of years ago. Julia looks like a good source of inspiration for adding such features to Common Lisp.

However, one aspect of Julia's message passing approach seems problematic, as far as I can tell: You can pass closures between different instances of Julia, but it's not clear how free variables in a lambda expression are bound. It seems that lexical variables are bound and serialized to another process, but global variables are not serialized and need to be present in any presence that may execute the closure. Experiments with adding side effects to free variables in lambda expressions that are passed to other processes seem to suggest that the semantics of this combination of features are unpredictable. At least, I have not been able to figure out what happens when — sometimes variables seem to be updated at the sender's side, sometimes not — and I didn't find a discussion of this topic in the Julia manual.

Anyway, as you can tell, there are a lot of interesting features in Julia, and it's definitely worth a try.

Colin LuptonSLIME for Emacs Live

· 35 days ago

Emacs Live is a frakkin’ epic compilation of customizations and packages, streamlined for the ultimate hacking experience. As I mentioned in my last post, Adventures in Clojure, it’s under development by the same team as the Clojure bridge to SuperCollider, Overtone. The one downside? It was designed for hacking Clojure, so it doesn’t include SLIME and Common Lisp support out of the box, and of course, it completely replaces your ~/.emacs.d/ directory and ~/.emacs config file, so you lose your existing SLIME setup (and all your other customizations) when you install Emacs Live. Don’t panic, the Emacs Live installer is smart enough to move your existing ~/.emacs.d/ folder and ~/.emacs config file to a safe place.

Emacs Live does, however, offer a pretty neat interface for creating Live Packs, boxed collections of Emacs packages and customizations, that can all be loaded together as a single package via ~/.emacs-live.el, stored outside the managed ~/emacs.d/ directory so that they can be maintained across updates. This made it only slightly less trivial than normal to get SLIME set up and running in Emacs Live.

To get the full Emacs Live experience for Common Lisp, however, you also need another package, AC-SLIME. It provides the auto-completion and pop-up documentation for Common Lisp, both in file buffers and the REPL.

I have packaged both together in an Emacs Live pack, which you can get at: https://github.com/thephoeron/slime-pack. Installation is a cinch. After installing Emacs Live, just clone SLIME-PACK into your ~/.live-packs/ directory, and add the following line to your ~/.emacs-live.el config file:

(live-append-packs '(~/.live-packs/slime-pack))

The default inferior-lisp-program for SLIME-PACK is SBCL. You can change this, as normal, by setq‘ing inferior-lisp-program to your chosen Lisp implementation after the code above.

Once that’s all done and saved, either restart Emacs or compile and load your modified config file. You can then simply M-x slime as normal, and enjoy all the extra Emacs Live awesomeness for Common Lisp!


Quicklisp newsJuly 2014 Quicklisp dist update now available

· 38 days ago
New projects:
Updated projects: 3bmd, access, aws-sign4, btrie, caveman, chirp, cl-ana, cl-async, cl-autowrap, cl-charms, cl-colors, cl-conspack, cl-coroutine, cl-ftp, cl-fuse-meta-fs, cl-html5-parser, cl-ltsv, cl-mustache, cl-plplot, cl-ply, cl-project, cl-qrencode, cl-rdfxml, cl-rethinkdb, cl-sdl2, cl-xul, clack, closer-mop, clsql-helper, coleslaw, colleen, com.informatimago, conium, contextl, crane, datafly, drakma-async, esrap, function-cache, gbbopen, glyphs, hctsmsl, ieee-floats, lisp-interface-library, lisp-unit2, marching-cubes, mime4cl, ningle, packet, paiprolog, plump, protobuf, racer, readable, repl-utilities, rutils, sexml, shelly, slime, spinneret, talcl, trivial-ldap, vgplot, weblocks, weblocks-utils, wookie.

SBCL 1.2.1 changed some internals that SLIME 2.7 relied on. This update includes SLIME 2.8, which works fine with SBCL 1.2.1.

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

Enjoy!

Zach BeaneInternational Lisp Conference 2014

· 39 days ago
I'm going to the International Lisp Conference in 2014 and so should you. It's great to meet Lispers in person and swap stories. Montreal is also a great city.

The deadline for early registration is tomorrow, Monday, July 14th. If you join the ALU for $25, early registration is only $300. (If you don't join the ALU, early registration is $400.) After tomorrow the registration fee goes up signifcantly!

Go register today! See you in Montreal next month!

Colin LuptonHacking Lisp in the Cloud, Part 2

· 44 days ago

This morning I got access to the new Cloud9 IDE beta—and I have to say… WOW. It’s slicker, it’s faster, it’s more stable, auto-complete recognizes Lisp definition forms from your open workspace files such as defun and defmacro, and most importantly, it only takes seconds to get your workspace set up with RLWRAP, SBCL and Quicklisp.

The new Cloud9 IDE is running on an Ubuntu backend workspace. Cloud9 has had terminal access to your project workspace for quite some time now, but I’ve found the terminal experience to be significantly smoother in the new beta. It stays connected now, no longer timing-out on you when switching tabs or stepping away from the computer for a minute. Users can also use sudo for root access, and as a result install any debian package from apt (amongst many other things, of course). Emacs 24 is already installed by default. I suspect that SSH tunneling to a remote SWANK server from the Cloud9 workspace is also now possible.

The Collaboration tools seem to be more streamlined. Workspace Members, Notifications, and Group Chat all appear together in one panel. I expect, with all the other improvements in the beta, that collaborative editing of your workspace files is likewise improved.

There’s a new Outline panel that lists the symbol-names of your top-level definition forms for the current active view—yes, even for Lisp. You can select a symbol-name and jump right to its definition in the file. Also, this functionality appears to be integrated with auto-complete, allowing you to jump to a definition of a function, macro, or variable from the auto-complete list as you type.

An interesting set of features I have not yet tried, is the custom Run/Build configurations. These features appear to allow you to write custom Run/Build scripts for arbitrary programming languages, so you should now be able to integrate Lisp into the IDE better, and write/test/debug/deploy your Lisp applications for the most part automatically.

One step closer to my hopes stated in my previous post on Cloud9 IDE from January, the Cloud9 IDE beta includes a JavaScript REPL. Combined with all the other helpful tools that they’ve included to support Lisp cloud development, it seems reasonable to suppose that a full REPL plugin is in the works.

I’ve barely scratched the surface here—there are so many new features to try out, I’ll probably be discovering new things every day for the next week. And to think, this is just the Beta! If you do your part and show your support for Cloud9 as a Lisp Hacker, I’m quite certain that the next full version of Cloud9 IDE will include everything we need to Hack on Lisp seamlessly in the Cloud.

If you want to get beta access to the new Cloud9 IDE yourself, all you have to do is follow the instructions on their blog post. If your Cloud9 username is different from your Twitter handle, you may need to provide that to them as well to get Beta access.

As always, Happy Hacking!


Zach BeaneCommon Lisp bits

· 44 days ago
A collection of Lisp Usenet gems, including articles from Kent Pitman, Erik Naggum, Chris Riesbeck, Pascal Costanza, and Will Hartung.

Things I Want in Common Lisp by Robert Smith.

Video demo of cl-notebook by lnaimathi. By the same author: [T]he primary endeavor of every programmer is twofold: To understand, and to be understood, which demonstrates generating code from a visual diagram.

Looking to start a band? Stumped on a name? See this twitter thread for inspiration.

simple-search is a "smaller alternative to Montezuma" that "allows you to index documents you have stored in-memory and query them in various ways." Looks good. From Andrew Lyon.

It is not hard to read Lisp code, by Jisang Yoo.

mathkit is "
a purely math-related utility kit, providing functions which can be useful for games, 3D, and GL in general" by Ryan Pavlik.

Nick LevineInternational Lisp Conference, Montréal

· 50 days ago
(Updated) Program and registration details of next month's International Lisp Conference can now be found at http://international-lisp-conference.org/. Note the changed dates; note that the deadline for early registration is July 14.

Ben HydeDocker, part 2

· 56 days ago

The San Francisco Hook

I played with Docker some more.  It’s still in beta so, unsurprisingly, I ran into some problems.   It’s cool, none the less.

I made a repository for running OpenMCL, aka ccl, inside a container.   I set this up so the Lisp process expects to be managed using slime/swank.  So it exports port where swank listens for clients to connect.  When you run it you export that port, i.e. “-p 1234:4005″ in the example below.

Docker shines at making it easy to try things like this.  Fire it up: “docker run –name=my_ccl -i -d -p 1234:4005 bhyde/crate-of-ccl”.   Docker will spontaneously fetch the everything you need.   Then you M-x slime-connect to :1234 and you are all set.  Well, almost, the hard part is  .

I have run this in two ways, on my Mac, and on DigitalOcean.  On the Mac you need to have a virtual machine running linux that will hold your containers – the usual way to do that is the boot2docker package.  On Digital Ocean you can either run a Linux droplet and then installed Docker, or you can use the application which bundles that for you.

I ran into lots of challenges getting access to the exported port.  In the end I settled on using good old ssh LocalForward statements in my ~/.ssh/config to bring the exported port back to my workstation.  Something like “LocalForward 91234 172.17.42.1:1234″ where that IP address that of an interface (docker0 for example) on the machine where the container is running.  Lots of other things look like they will work, but didn’t.

Docker consists of a client and a server (i.e. daemon).  Both are implemented in the same executable.  The client chats with the server using HTTP (approximately).  This usually happens over a Unix socket.  But you can ask the daemon to listen on a TCP port, and if you LocalForward that back to your workstation you can manage everything from there.  This is nice since you can avoid cluttering you container hosting machine with source files.  I have bash functions like this one “dfc () { docker -H tcp://localhost:2376 $@ ; }” which provides a for chatting with the docker daemon on my Digital Ocean machine.

OpenMCL/ccl doesn’t really like to be run as a server.   People work around by running it under something like screen (or tmux, detachtty, etc.).  Docker bundles this functionality, that’s what the -i switch (for interactive) requests in that docker run command.  Having done that you can then uses “docker log my_ccl” or “docker attach my_ccl” to dump the output or open a connection to Lisp process’ REPL.   You exit a docker attach session using control-C.  That can be difficult if you are inside of an Emacs comint session, in which case M-x comint-kill-subjob is sometimes helpful.

For reasons beyond my keen doing “echo ‘(print :hi)’ | docker attach my_ccl” get’s slightly different results depending on Digital Ocean v.s. boot2docker.  Still you can use that to do assorted simple things.   UIOP is included in the image along with Quicklisp, so you can do uiop:runprogram calls … for example to apt-get etc.

Of course if you really want to do apt-get, install a bundle of Lisp code, etc. you ought to create a new container built on this one.  That kind of layering is another place where Docker shines.

So far I haven’t puzzled out how to run one liners.  Something like: “docker run –rm bhyde/crate-of-ccl ccl -e ‘(print :hi)’” doesn’t work out as I’d expect.  It appears that argument pass thru, arg. quoting, and that the plumbing of standard IO et. al. is full of personality which I haven’t comprehended.  Or maybe there are bugs.

That’s frustrating - I undermines my desire to do sterile testing.

 

LispjobsLisp Developer, Ravenpack, Marbella, Spain

· 58 days ago

Location: Marbella, Spain
No. of positions available: 1

Position immediately available for an experienced software professional. You will work with an international team of developers skilled in Common Lisp, PL/SQL, Java and Python.

The ideal candidate will have excellent skills as a software engineer, with a strong computer science background and professional experience delivering quality software. You must be fluent in modern software development practices, including multi-threading, distributed systems, and cloud computing. If you are not already an expert in Common Lisp, you aspire to become one. Innovative problem solving and engaging human interaction drive you. With high degree of independence, you will design and implement maintainable software in Common Lisp based on loose and changing specifications.

Familiarity with SQL including query optimization and PL/SQL is very much a plus. Comfort in a growing, fast-paced environment with a premium on problem solving is required. Must be adaptable and willing to learn new technologies. You work successfully in a small team environment, with a willingness to teach and to learn. Lead reviews of your code and participate in the reviews of others.

The ability to communicate effectively in English, both in writing and verbally is a must. Knowledge of Spanish is not a business requirement. European Union legal working status is strongly preferred.

Email CV and a Cover Letter to employment@ravenpack.com with subject “Lisp Developer”.


Colin LuptonAnnouncing BIT-SMASHER

· 58 days ago

BIT-SMASHER is a lean, straightforward and admittedly naive Common Lisp library for handling the oft-overlooked bit-vector type, bit-vector arithmetic, and type conversion between bit-vectors, octet-vectors, hexadecimal strings, and non-negative integers, extending the related functionality in the Common Lisp standard. While of little use to the average Lisp project, it was designed for those cases where working with bit-vectors is either necessary, or would be ideal if it were not for the lack of the functions this library provides.

You can get BIT-SMASHER now at: https://github.com/thephoeron/bit-smasher — or wait for it to come out in the next Quicklisp release.

The most obvious use-case for BIT-SMASHER is when you need to convert universally between bit-vectors, octet-vectors, hexadecimal strings, and non-negative integers. The library provides manual conversion functions for all twelve cases, plus type-checking, type-casting style convenience functions:

For example:

; universal type-casting style functions
(bits<- "F0") => #*11110000
(bits<- 240) => #*11110000
(int<- #*11110000) => 240

; manual conversions without type-checking
(hex->bits "F0") => #*11110000
(int->bits 10) => #*00001010
(octets->bits (int->octets 244)) => #*11110100

The lack of bit-vector arithmetic in the Common Lisp standard was my main motivation to write this library. However, an obvious limitation of the type to values in the set of non-negative integers forced an equal limitation on return results from the bit-vector arithmetic functions. That is to say, when an arithmetic function would normally return a negative integer, float, or fraction as one of its values, it returns the absolute ceiling value (as a bit-vector) instead. For example:

(bit+ #*0100 #*0010) => #*00000110 ; +6, as expected

(bit- #*0000 #*0010) => #*00000010 ; returns +2, not -2

(bit/ #*1010 #*0010 #*0010) => #*00000010 #*00000001 ; returns +2, remainder +1, not 0.5

The library also contains measurement and predicate utility functions, hopefully serving all your bit-vector needs excluded from the standard.

If you encounter any bugs, or have a feature you would like to see, let me know in the comments or create an issue on GitHub.


Hans HübnerBerlin Lispers Meetup: Tuesday June 24th, 2014, 8.00pm

· 58 days ago
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, June 24th, 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!

Quicklisp newsJune 2014 dist update now available

· 66 days ago
New projects:
Updated projects: bknr-web, cffi, cl-6502, cl-ana, cl-async, cl-async-future, cl-autowrap, cl-cairo2, cl-charms, cl-closure-template, cl-glfw3, cl-html5-parser, cl-launch, cl-mustache, cl-permutation, cl-protobufs, cl-reexport, cl-rethinkdb, cl-sdl2, cl-spark, cl-test-more, cl-xul, clickr, clos-fixtures, closer-mop, clss, coleslaw, colleen, com.informatimago, common-lisp-actors, crane, csv-parser, data-table, drakma-async, function-cache, gbbopen, gendl, graph, helambdap, ieee-floats, iolib, lisp-unit2, lquery, more-conditions, plump, postmodern, qmynd, repl-utilities, slime, stumpwm, trivial-download, verbose, vgplot, vom, weblocks, weblocks-stores, weblocks-utils, yason.

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

Nick LevineMoving to Spain

· 72 days ago

I've taken up a position with RavenPack, and so my 14 years at Ravenbrook come to an end. I'm sorry to be leaving, but I hadn't been able to generate anywhere enough income recently and something had to change. I've never worked anywhere for so long, and although the dips in available work sometimes made life very stressy I've also been very happy there. If you ever need someone to help you increase the value of the software industry to society, this is the place to look.

A job! Lisp! The lean times are over! This is all very exciting.

RavenPack are based in Marbella. We'd been wondering for some time whether we would ever get around to leaving Cambridge, and it turns out now that the answer is "yes". But it's all going to be very strange. My name badge might not be changing by very much, but there's no mistaking either consulting for full-time employment, or the Fens for the Costa del Sol.

We'll be staying somewhere temporary over the summer, and then when the tourists have gone home we'll find somewhere to live which has space for visitors. Enough said.

PS: leaving do probably Saturday July 12th

Zach BeaneCL news

· 72 days ago
Crane is a new Common Lisp ORM by Fernando Borretti. "Crane doesn't drink the ORM Kool Aid: You won't spend a single minute struggling with an interface that claims to be 'simple' yet forces you into a limited vision of how databases should work."

Mark Fedurin surveys ASDF system version strings in the wild. The cartoon at the end is great.

From Rainer Joswig: Why Lisp is Different (2007) and 30 years of Common Lisp (2014).

a-cl-logger is a Common Lisp logging library with node-logstash integration, support for swank presentations, context-sensitive logging, and more.


For older items, see the Planet Lisp Archives.


Last updated: 2014-08-22 00:43