Planet Lisp

Nicolas HafnerProject Listing - Confession 76

· 10 days ago

This is a listing of projects that I've started, some of which I've completed. The intent is to spread awareness about the work I've done, as I speculate that a lot of people don't know about most of it, even though it might prove useful to their own projects. So, hopefully this article will help a bit in that regard.

I won't go into much detail in the descriptions, as that would take too much of both your and my own time. You can however click on the title of each project to get to its "homepage" if you want to find out more. Naturally, you're also free to contact me if you're interested.

Major Projects

Major projects are ones that have no completion in sight. There are always improvements and additions that could be made to improve the project. Generally they serve as a launch pad for other, minor projects that are completable.


Lichat is an attempt at a simple, light-weight chat protocol. There's currently full implementations of the protocol available that allow you to host a TCP or WebSockets server, and to write clients in JavaScript and CL. A Java library, with the intent of writing an Android client is planned.


Maiden is an event coordination framework and bot construction toolkit. It includes a plethora of pre-made modules to provide common chat bot functionality, as well as a couple of different backends for various chat protocols.


Parasol is a native painting application for graphics tablet users. It has been dormant for some years now as I've still not figured out a good way to architecture everything.


Portacle is the portable development environment for Common Lisp. It gives you an easy-to-deploy, contained development studio that you can use to program. It is especially suited and geared towards beginners that have not used Lisp before, but it's also convenient for quick setups on unconfigured machines.


Radiance is a web application environment, allowing you to easily deploy and run different web applications in the same lisp instance, increasing sharing of common resources. This article is actually hosted on an application running in Radiance. Imagine that!


Trial is an OpenGL game engine with a heavy focus on modularity. It is supposed to provide a large toolkit of useful bits and pieces from which you can create a game. I use this engine together with some of my co-conspirators to write games for the Ludum Dare game jam. Hopefully the engine will at some point also give birth to bigger games.

Minor Projects

These projects all either spawned out of the requirements of the major projects, or happened simply for fun. Most of them are already complete and thus ready for use.


A library implementing common matrix calculations, with an emphasis on 2x2,3x3, and 4x4 matrices as commonly used in graphics. It provides some numerical functions as well, but those are not the focus. The library is heavily optimised, so it is not made of pretty code.


This is the counter-piece to 3d-matrices, providing vector operations optimised for 2, 3, and 4-component vectors. Also just like 3d-matrices, the library is heavily optimised and thus not pretty on the eyes.


CSS-Like Simple Selectors implements a DOM search engine using the CSS selectors as the query format. It is reasonably optimised, but only usable with the DOM provided the Plump system.


Lisp Augmented Style Sheets is a compiler for a custom CSS syntax. It allows you to write CSS files in a much more convenient and homely-feeling syntax. I've been using this to write pretty much all of my CSS for the past couple of years.


A small library to provide vector manipulation functions that are sorely missing from the standard. Allows to push to any place in the array while maintaining the proper shifting logic.


A Continuous Integration system with a focus on running directly on your machine, rather than in a container or otherwise segregated environment. This is currently being rewritten from scratch.


A Radiance application for a web interface to a chatlog database. The database is recorded through the Colleen or Maiden chatlog modules.


A chat application based on the Twitter direct messages system. Allows you to chat directly with your twitter friends as if it were a regular chat room. Easy to set up, and runs on all major desktop platforms.


A client library implementing the full Twitter REST API. If you want to interact with Twitter, this is your best bet.


A bindings library to libfond, allowing you to use its functionality easily from Lisp out. Libfond allows the rendering of TrueType fonts onto OpenGL textures.


A bindings library to libstem_gamepad, providing easy gamepad and joystick event processing from Lisp. This is useful if you don't want to use some kind of framework that brings all sorts of other baggage with it, not just gamepad processing.


A wrapper library for the Linux General Purpose IO device present on embedded systems such as the Raspberry Pi. It allows you to conveniently access and control the IO pins on the board.


A bindings library for the k8055 analog input board. Allows you to read its various values and set outputs.


A bindings library to libmixed, allowing you to use its functionality from Lisp. Libmixed allows you to perform digital audio mixing and processing. Thus, with this, you can do efficient DSP from Lisp.


A bindings library to libmonitors, providing convenient access to information about the currently attached monitors, and giving you the ability to control the resolution thereof.


A bindings library to libmpg123, giving you fast and easy to use MP3 decoding. This covers the complete API exposed by libmpg123, and thus easily your best bet for MP3 processing.


A bindings library to libout123, giving you cross-platform audio output. The API is very simple to use, and can thus give you a quick start if you need to play some audio.


A bindings library to SoLoud, an open source C++ sound engine for the use in video games. I've completed this, but dropped it, as it was too hostile to extension from CL. I've since developed Harmony (see below).


A wrapper library for the Linux Serial Port Interface device. With this you can do serial port input/output, which is present on some embedded devices like the Raspberry Pi.


Clip is an alternative approach to templating, expressing the template within valid HTML. This allows a different development approach, wherein you can hammer out a mock-up for a website in an HTML document, and then simply add templating logic through further tags and attributes, maintaining browser-viewability.


This is the predecessor to Maiden, with a more narrow focus and feature base. Since it has been superseded, and the code is quite crusty, I heavily urge you to look at the Maiden project instead.


A tiny library to provide commonly used cryptography functions in a more accessible format, as some of the tools provided by Ironclad & co. can be a bit cumbersome to use.


Deeds is an Extensible and Event Delivery System. It offers both flexible and performant creation of event systems. Deeds is used heavily in Maiden.


This was an attempt at making optional dependency wrangling more convenient. It gives you a few tools that attempt to make it possible to write code that is only considered once another system becomes available.


With Qtools I developed a very convenient mechanism to generate deployments of my systems. This is the evolution of that, allowing you to use it independent from Qt. It takes care of your foreign libraries and the general shutdown and boot sequence, making the whole binary deployment process much smoother.


Sadly a lot of projects use the "trivial-backtrace" system that just gives them a string with a backtrace. Dissect allows you to capture, step, and completely inspect the stack trace on a variety of Lisp implementations. The introspection abilities allow you to write a good chunk of a portable debugger. It's also very useful for logging and other situations where execution is automatically continued, but the information of the current stack is still useful to store somewhere.


I like to keep my code nice and clean, and as such docstrings are quite cumbersome clutter. This library allows you to easily and conveniently put all the docstrings in a file outside of the rest of your code.


This is a Radiance application that provides you with a very simple file storage. Coupled with the filebox-client, you get a Dropbox-like system.


Flare is a particle simulation framework. Unlike most particle systems, it does not focus on the emission of small dots, but rather on the precise coordination of a hierarchy of entities. It allows you to describe sequences of events, and then lets you play those sequences back, performing the actual transformations. You can even rewind time and interactively work on your sequences.


This is a flowchart-like graph library. It gives you access to nodes which, unlike in mathematical graphs, have dedicated ports from which connections are made. These ports can have semantic meaning and syntactic properties. Thus, this gives you a toolkit to make flowchart-like graphs and compute with them.


Since I couldn't come to terms with Iterate, I decided to write my own extensible iteration construct. Unlike Loop or Iterate, For has a particular syntax to it that makes extensions feel much more integrated.


This small library allows you to wrangle lambda forms and destructure them into their individual components (docstring, declarations, arguments, etc).


A toolkit to allow you to process and manipulate OpenGL Shader Language code. It includes a full GLSL4 parser, printer, and code-walker. Using this you can even do stuff like merge separate shaders together automatically, preserving input/output semantics.


A sample application for the Qtools system, providing you with a minimal, but pretty image viewer. Works on all major desktop platforms.


Harmony is a fully-fledged audio system, allowing you to control playback of multiple sources, and even to position them in 3D space. It also allows you to build your own sound processing pipelines, to add in effects and other sound processing capabilities.


This is a client library for the Tumblr REST API. It has full coverage of the documented features and properly wrangles all the oddities and inconsistencies of the API for you.


This is still in the works, but is intended to become a website (using Radiance) that provides useful information about Kanji, as well as an optimised sequence by which to learn them. Hopefully this will help me and other people to learn Japanese.


Another Radiance application that provides a very minimalist site for product reviews. The twist of this site is that your review should be very short, if possible reduced to keywords only. The idea is that this should make for interesting descriptions and interpretations.


The counterpart to form-fiddle, this allows you to wrangle and destructure lambda-lists (argument lists).


An interface to the Git binary. Using this library you can run all the available Git commands using a more convenient and streamlined function interface. An object-oriented high-level interface is also available, but doesn't cover the full API.


A small C library to allow you to render TrueType fonts to OpenGL textures. Text rendering is something that's often left out of minimal game engines, and so libfond can provide you with that aspect.


A small C library to allow you to mix and process digital audio. It is reasonably optimised and comes with a set of processing and mixer components out of the box. One of the components also allows you to integrate LADSPA plugins, so you can use those directly as well.


A small C library to handle the management and information retrieval of connected Monitors. Currently Linux, Windows, and OS X are supported.


A native GUI for the Lichat system. While this works well enough as it currently stands, I'd like to rewrite it at some point to use Maiden, and thus allow connecting to other chat systems as well.


A library modelled after jQuery to allow you to conveniently and succinctly wrangle HTML and XML documents. This is Particularly useful for web scraping tasks.


This is a system that gives you an extension to the package system, by allowing you to add other metadata to it. This should facilitate the construction of "modules," individual components of a larger system. The metadata can be used to give meaning to the modules and model their relations to the whole system.


This augments the modularize system by giving you hooks and triggers. Thus, modules can provide opaque entry points for other modules to provide additional functionality.


This augments the modularize system by giving you "interfaces"- contract-like descriptions of the functionality provided through a package. While the interface description is abstract and only includes the signatures of functions, another module can then opt to implement the actual functionality behind the interface.


The successor to the South (Simple OaUTH) library, implementing the full oAuth 1.0a protocol, both client and server sides. Using North you can easily become an oAuth provider or consumer.


Parachute is a testing framework with an emphasis on being extensible. As proof of this, it includes "compatibility layers" for a couple of other popular testing frameworks. Using such a layer you can immediately convert to using Parachute by just changing a package :use and system :depends-on.


A small library to help with common pathname wrangling tasks. If you need to work with pathnames a lot, you'll probably find one or two things in here that will prove useful to you. Note that the library is restricted to pathnames, so it won't provide anything that actually touches the file system.


A library implementing the public interface for the PiPlates DAQ plates that you can use in combination with the Raspberry Pi. The library is currently untested, but "should work" as it is a fairly straightforward translation of the official Python code. I haven't yet found the will to actually test it myself.


Piping allows you to write "pipelines." Pipelines are systems of pipe segments that pass along and transform or compute based on the object currently being passed through the pipeline.


Plaster is another Radiance application. It gives you a usable paste service. The Radiance tutorial even shows you how to write the application from scratch.


An implementation of a binary storage format for the Plump DOM. It allows you to save a DOM into a more efficiently parseable representation on disk.


A parser and printer for an s-expression based syntax of an HTML DOM, using the Plump DOM as a back-end.


A parser and printer for a TeX based syntax, using the Plump DOM as a back-end. With this you can parse TeX sources into a DOM and render them as HTML.


A Practically Lenient and Unimpressive Markup Parser for XML and HTML documents. It provides a fast and lenient parser, allowing you to chuck all sorts of malformed data at it. Since it integrates with a bunch of my other systems, it's a pretty good choice for HTML.


This is a small library to allow you to post content to multiple services at once. I use this to post my art online, as there's a couple of different places I'd otherwise have to upload to manually every time.


Purplish is yet another Radiance application. It provides you with a slick and simple image board software. If you ever want to run a chan, this could be a good choice.


This system provides you with the Qt4 library binaries. Usually all you have to do is load this system, and you'll be set up and ready to go writing Qt applications. It also includes tools to automatically build the libraries from scratch.


Qtools allows you to write Qt GUIs in a syntax and manner much more similar to how you'd write any other Lisp code. It provides all sorts of conveniences and abstractions to make life a whole lot easier.


This is a collection of UI components and systems that Qt does not provide on its own. Being completely written in Lisp, it is also ripe for extension and adaptation in your own projects. If you have a reusable component that you wrote, it would be a great idea to integrate it here, so that others can benefit as well.


Random-state gives you access to a bunch of different random number generation algorithms, and allows you to portably seed them. This is primarily useful where number generation needs to be controllable.


This system allows you to verify and parse a variety of string-based formats. It is primarily geared towards validating input from web forms, or other unauthorised sources.


A Radiance application providing you with a simple blogging platform with tags and Atom feeds. This article was published on Reader!


A tiny library implementing a gray stream that redirects the output written to it to another stream. This is useful when you want to switch out the stream of a particular system on the fly.


A small library to do simple task issuing and processing. You create tasks that execute some code, and then send them off to be processed on a dedicated background thread.


This gives you a single function, which returns the lambda-list of a function, if the list is known. Useful for introspective and descriptive tasks.


A small library to do simple benchmarking work. This library uses CLOS to be easy to extend, which incurs a bit of overhead for the benchmarks themselves. Thus, it is sadly not suitable for micro-benchmarking.


If you make a macro with a bit of a more advanced syntax, it's likely Slime will not pick up the proper indentation for it. With this, you can help it out by declaring the proper indentation form manually.


Sometimes it's necessary to ensure that code is run in the main thread, especially when you want to do graphics on OS X. This library helps you with that.


The detection and handling of mime-types for files is sometimes necessary to validate the correctness of a specified content type. This library implements both a binary lookup, and a file-name lookup.


This tiny library uses the ImageMagick binaries to create thumbnails of images for you.


Ubiquitous provides a persistent configuration storage. It gives you convenient traversal through the configuration and offers easy file-based serialisation for a good range of Lisp object types. If you need your application to be configurable through external files, or just need a simple storage, check a look!

Other Stuff

That's about it. I have a bunch of other projects that I haven't mentioned here, either because they're old, abandoned, not even close to finishing, or simply uninteresting.

Since I'm constantly doing things, this list is bound to become outdated before long. So, please be mindful of the date. When in doubt, just look at the project's own page, or contact me directly. I love to chat, so even if you don't care about any of this, I definitely wouldn't mind if you stopped by at #shirakumo on Freenode some time.

Quicklisp newsSomething to try out: Quicklisp with OpenPGP and SHA verification

· 19 days ago
I've got a test version of Quicklisp available. It uses pure Common Lisp code to verify file SHA digests and OpenPGP signatures, from bootstrap to library loading.

To try it out, fetch the following file:

Load it into a Lisp implementation with (load "quicklisp.lisp") and follow the prompts. It's best to start with a Lisp that doesn't have Quicklisp already loaded automatically from the init file.

The PGP public key for Quicklisp releases is embedded directly in quicklisp.lisp, but you can also fetch it from another source and use :public-key-file "/path/to/separate/key" as an argument to quicklisp-quickstart:install to use a specific key file.

If you do try it, move your existing, working Quicklisp install out of the way first, or use the :path option to install to a test location. Otherwise, you could clobber a working Quicklisp setup.

This verification code slows things down a bit because it does a lot of arithmetic. The slowdown is most dramatic in implementations like ABCL and CLISP.

If everything works as it should, you won't notice anything very different from the normal Quicklisp install, except some slowdown during verification and some output indicating what checks were attempted and passed.

If you run into problems where something doesn't work as you expect, please let me know at


Paul KhuongRendezvous Hashing: My Baseline "Consistent" Distribution Method

· 23 days ago

2017-10-15: Tweaked the hash merge function to actually deliver the claims (one-universality isn’t enough).

Whenever I mention a data or work distribution problem where I ideally want everything related to a given key to hit the same machine, everyone jumps to consistent hashing. I don’t know how this technique achieved the mindshare it has, although I suspect Amazon’s 2007 Dynamo DB paper is to blame (by introducing the problem to many of us, and mentioning exactly one decentralised solution)... or maybe some Google interview prep package.

Karger et al’s paper doesn’t help, since they introduce the generic concept of a consistent hash function and call their specific solution... “consistent hashing.” I’m not sure where I first encountered rendezvous hashing, but I vaguely remember a technical report by Karger, so it’s probably not some MIT vs UMich thing.

Regardless of the reason for consistent hashing’s popularity, I feel the go-to technique should instead be rendezvous hashing. Its basic form is simple enough to remember without really trying (one of those desert island algorithms), it is more memory efficient than consistent hashing in practice, and its downside–a simple implementation assigns a location in time linear in the number of hosts–is not a problem for small deployments, or even medium (a couple racks) scale ones if you actually think about failure domains.

Side question: why did rendez-vous have to lose its hyphen to cross the Channel?

Basic rendezvous hashing takes a distribution key (e.g., a filename), and a set of destinations (e.g., hostnames). It then uses a hash function to pseudorandomly map each (distribution_key, destination) pair to a value in [0, 1) or [0, 2^64 - 1), and picks the destination that gives the minimal hash value. If it needs k destinations for redundancy, it can pick the destinations that yield the least k hash values. If there are ties (unlikely with a good hash function), it breaks them arbitrarily but consistently, e.g., by imposing a total order on hostnames.

A Python implementation could look like the following.

basic rendezvous hashing
Destination = namedtuple('Destination', ['host', 'hash'])

def merge_hashes(x, y):
    """murmurhash3 mix.  Alternatively, ((x | 1) * (y | 1)) % 2**64 should
    be fine.
    acc = x ^ y
    acc ^= acc >> 33
    acc = (acc * 0xff51afd7ed558ccd) % 2**64
    acc ^= acc >> 33
    acc = (acc * 0xc4ceb9fe1a85ec53) % 2**64
    acc ^= acc >> 33
    return acc

def pick_destinations(key, destinations, k=1):
    key_hash = hash_key(key)  # hash the key once, instead of hash(key + host)
    annotated = [(merge_hashes(key_hash, dest.hash),
                 for dest in destinations]
    ordered = sorted(annotated)  # lexicographic sort on merged hash, host.
    return [host for _, host in ordered[:k]]  # grab host from the first k

We only need to store the list of destinations, and we can convince ourselves that data distribution is pretty good (close to uniform) and that small changes in the set of destinations only affects a small fraction of keys (those going to destinations added/removed), either with pen and paper or with a few simulations. That compares positively with consistent hashing, where a practical implementation has to create a lot (sometimes hundreds) of pseudo-nodes for each real destination in order to mitigate clumping in the hash ring.

The downside is that we must iterate over all the nodes, while consistent hashing is easily \(\mathcal{O}(\log n)\) time, or even \(\mathcal{O}(\log \log n)\), with respect to the number of (pseudo-)nodes. However, that’s only a problem if you have a lot of nodes, and rendezvous hashing, unlike consistent hashing, does not inflate the number of nodes.

Another thing I like about rendezvous hashing is that it naturally handles weights. With consistent hashing, if I want a node to receive ten times as much load as another, I create ten times more pseudo-nodes. As the greatest common divisor of weights shrinks, the number of pseudo-node per node grows, which makes distribution a bit slower, and, more importantly, increases memory usage (linear in the number of pseudo-nodes). Worse, if you hit the fundamental theorem of arithmetic (as a coworker once snarked out in a commit message), you may have to rescale everything, potentially causing massive data movement.

Rendezvous hashing generates pseudorandom scores by hashing, and ranks them to find the right node(s). Intuitively, we want to use weights so that the distribution of pseudorandom scores generated for a node A with twice the weight as another node B has the same shape as that of node B, but is linearly stretched so that the average hash value for A is twice that for B. We also want the distribution to cover [0, infty), otherwise a proportion of hashes will always go to the heavier node, regardless of what the lighter node hashes to, and that seems wrong.

The trick, as explained by Jason Resch at Cleversafe, is to map our hashes from uniform in [0, 1) to [0, infty) not as an exponential, but with -weight / log(h). If you simulate just using an exponential, you can quickly observe that it doesn’t reweigh things correctly: while the mean is correctly scaled, the mass of the probability density function isn’t shifted quite right. Resch’s proof of correctness for this tweaked exponential fits on a single page.

The Python code becomes something like:

weighted rendezvous hashing
Destination = namedtuple('Destination', ['host', 'hash', 'weight'])

def score(hash_value, weight):
    return -weight / math.log(hash_value / HASH_MAX)

def pick_destinations(key, destinations, k=1):
    key_hash = hash_key(key)
    annotated = [(score(merge_hashes(key_hash, dest.hash), dest.weight),
                 for dest in destinations]
    ordered = sorted(annotated)
    return [host for _, host in ordered[:k]]

There are obvious micro-optimisations here (for example, computing the inverse of the score lets us precompute the reciprocal of each destination’s weight), but that’s all details. The salient part to me is that space and time are still linear in the number of nodes, regardless of the weights; consistent hashing instead needs space pseudolinear(!) in the weights, and is thus a bit slower than its \(\mathcal{O}(\log n)\) runtime would have us believe.

The linear-time computation for weighted rendezvous hashing is also CPU friendly. The memory accesses are all linear and easily prefetchable (load all metadata from an array of nodes), and the computational kernel is standard vectorisable floating point arithmetic.

In practice, I’m also not sure I ever really want to distribute between hundreds of machines: what kind of failure/resource allocation domain encompasses that many equivalent nodes? For example, when distributing data, I would likely want a hierarchical consistent distribution scheme, like Ceph’s CRUSH: something that first assigns data to sections of a datacenter, then to racks, and only then to individual machines. I should never blindly distribute data across hundreds of machines; I need to distribute between a handful of sections of the network, then one of a dozen racks, and finally to one of twenty machines. The difference between linear and logarithmic time at each level of this “failure trie” is marginal and is easily compensated by a bit of programming.

The simplicity of basic rendezvous hashing, combined with its minimal space usage and the existence of a weighted extension, makes me believe it’s a better initial/default implementation of consistent hash functions than consistent hashing. Moreover, consistent hashing’s main advantage, sublinear-time distribution, isn’t necessarily compelling when you think about the whole datacenter (or even many datacenters) as a resilient system of failure-prone domains. Maybe rendezvous hashing deserves a rebranding campaign (:

François-René RideauA tale of many nests

· 24 days ago

This short essay will tell you about my favorite macro, nest, discuss the modularity of syntax extension, and use the implementation of that macro as an illustration for how to use defmacro, syntax-rules and syntax-case, providing along the way a comparison between these respective macro definition systems.

Using the nest macro

When I started using Scheme as my main Lisp, the first macro I wrote was the nest macro. What macro? The nest macro. The one that in Common Lisp helps my code avoid drifting hopelessly to the right as I nest binding form inside binding form... by doing the nesting for me. To illustrate the kind of issues that I'm concerned with, consider the Common Lisp code snippet below:

(multiple-value-bind (a1 b1 p1) (foo1)
  (with-open-file (f1 p1 ...)
    (let ((x1 (read f1)))
      (when x1
        (multiple-value-bind (a2 b2 p2) (foo2)
          (with-open-file (f2 p2 ...)
            (let ((x2 (read f2)))
              (when x2
                (bar x1 x2 ...))))))))

You're doing the same thing twice, but because of all those binding forms, the code moves right, the symmetry is broken, and the line limit makes you cut your lines more and more as you nest more forms, until you run out of space. It's really ugly. So much so that it makes me miss block-oriented languages in the ALGOL tradition (like C, OCaml or Python) where all the bindings (at least simple ones) go at the same level of indentation, and symmetry is preserved between consecutive bindings, and the line limit isn't an increasing threat as my functions get more complex.

Of course, it is always better when you can break down your functions into simpler chunks, at which point it doesn't matter that you move a little bit to the right, because no function is long enough for this right shift to matter much. However, when you are really computing some correspondence between two (or more) sets of entities, there's no way around doing a lot of nested bindings before you have all the input elements aligned together in a way that you can even start your computation. That's what happened for instance with my famous macros implementing the isomorphisms between pure and stateful data structures and between interface-passing-style (typeclasses) and object-oriented style (classes): the more complex macros, to "classify" interfaces, had up to 18 levels of nesting. That's a lot of indentation, that reflects as much context to fit in your limited brain registers at once (and indeed, it took me over a month to complete the first in that series of macros). Happily there is a lot of symmetry, that will be more readily apparent if only your code doesn't have to get indented so much.

The traditional solution to this approach, in Common Lisp, was to invent a "mother of all" binding macro, that could replace all the other ones at once: Attempts at providing such universal binding form include metabang-bind, let+, at least one attempt internal at ITA that I saw, and probably many more attempts that I don't know about, not to mention pattern matchers like my old fare-matcher and its better replacements optima and trivia. Now, the problem with this approach is that whoever writes this universal binding form must offer a way to supersede each and every binding form in the language. But since the language is extensible and people keep defining new binding forms (especially using CALL-WITH-* style), the task is an endless, sisyphean endeavor. What more, it is also a modularity nightmare, as there is no clear responsible party for each of the N*M extensions of N universal binding forms to each match each of M new kinds of bindings. I believe the best universal binding system in town these days is trivia, the extensible pattern matcher; but even it has only limited mind share. (Of course, I'm partial to pattern matchers: when, decades ago, I switched from OCaml to Common Lisp, I missed pattern-matching so much that the first thing I did was to write the first ML-style pattern matcher for Common Lisp; which could of course be done within the language using macros.)

As I was discussing this topic a few years ago, and potential extensions to macro-expanders to support capture of syntactic "block" continuations so they would work well with python-like syntax, my then colleague Marco Baringer, of arnesi fame, told me about this beautiful, simple solution that he knew of: the nest macro. This one remarkable macro already supports all binding forms past, present and future, without anyone having to write any code whatsoever to extend it — because it trivially embraces the syntax of them all with one weird trick: recognizing that all binding macros end with a body of code inside which the variable are bound, and nesting each form passed to the macro inside the body of the previous form, at the end. Thus, for instance the above snippet is flattened this way:

 (multiple-value-bind (a1 b1 p1) (foo1))
 (with-open-file (f1 p1 ...))
 (let ((x1 (read f1))))
 (when x1)
 (multiple-value-bind (a2 b2 p2) (foo2))
 (with-open-file (f2 p2 ...))
 (let ((x2 (read f2))))
 (when x2)
 (bar x1 x2 ...))

Notice how all these binding forms are now neatly indented at the same level! Remark that each of the forms is closed before its body ends (sometimes before its body begins), said body being present or completed in the next form. And see how it also works for forms that are not binding forms, but still provide context for the body inside, such as the when forms. And note that if you didn't want your when form to wrap around all the rest, but simply to contribute a side-effect before the rest is evaluated, then you might want to wrap your when form inside a progn form (in Common Lisp) or begin form (in Scheme), that would provide this sequential behavior. Thus the nest macro works not only with binding forms, but with all kinds of expressions. Better yet, the nest macro even works with forms that are not expressions stricto sensu (though the overall form has to be an expression for the macro to be expanded)! For instance, it will work with case or match clauses:

 (for-each! list1) (lambda (elem1))
 (match elem1) ((list x1 y1 z1 ...))
 (for-each! list2) (lambda (elem2))
 (match elem2) ((list x2 y2 z2 ...))
 (begin (assert (equal x1 x2)) ...)
 (case (foo y1 y2) ((A B C ...) easy-caseA ...) ((D E F ...) easy-caseD ...))
 ((G H I ...) (hard-caseG main-body ...)) ...)

Notice how the (list x1 y1 z1 ...) or the (G H I ...) are not expressions but one a matching pattern and the other a list of cases. Each of their syntactic roles is different from that of normal expressions, and each follows its own distinct grammar. That's some additional expressive power that the nest macro has in Lisp that other more sophisticated macros do not have in Lisp or in any other language. Notice also how this style allows to detach the lambda expressions and their bindings from the rest of their body (which covers the rest of the arguments to the nest macro), and to place the head of these lambda expressions right next to the calling expression that calls them and binds the lambda variables: thus it becomes very clear that elem1 will be bound to each of the elements in list1, or that x2 y2 z2 will be bound to elements of a list that matches the contents of elem2. Meanwhile, the body below each of these forms doesn't have to care what kind of form it is the body of. This is all a beautiful division of labor, with power, expressiveness, brevity, relevance, symmetry, etc. All that for the price of understanding one simple macro.

I like this macro so much that I made it available as UIOP:NEST, as part of UIOP, the Common Lisp "Utilities for Implementation- and OS- Portability", a library is transcluded in ASDF, the build system used by nearly all software written in Common Lisp today. Thus, every contemporary Common Lisp program can assume that this macro is readily available. And ASDF itself is making good use of the macro: the macro shines not just to keep indentation in check, but also in conjunction with Common Lisp reader conditionals, so that some wrapping forms are only used on relevant implementations and not other implementations.

Implementing the nest macro

But just how simple is the nest macro? So simple it's literally a one liner in Common Lisp:

(defmacro nest (&rest r) (reduce (lambda (o i) `(,@o ,i)) r :from-end t))

That is, it is just a right fold (hence the :from-end t) on the list of forms r, to nest each (rightmost) form i into the end of the previous one o.

Now, moving to Scheme, the benefits of nest are about the same, just better, since there are even more higher-order function that call functions; if only we reorganize the order of their arguments so the function comes last (as with the for-each! variant of the standard for-each function above), then we can easily chain together the bindings and bodies of all these forms with the nest macro. And so, soon enough, I wrote a Scheme version of the nest macro. Here was my first, naive, attempt; can you tell what was wrong with it without reading what follows?

(define-syntax nest
  (syntax-rules ()
    ((nest (x ...) y z ...) (x ... (nest y z ...)))
    ((nest x) x)))

This macro uses the simple but limited pattern-matching macro-defining macro syntax-rules. It recurses into each of the forms to nest by inserting itself as the head of successive shorter sub-lists of forms, that will recursively expand it, until a single form is left that is returned as the innermost form with nothing to nest in it. And the problem with this simple macro is... that the recursive inner form (nest y z ...) will only expand this inner nest if it is an expression, i.e. the kind of form that gets evaluated into a value by the evaluator (whether based on an interpreter, compiler, JIT, or whatever else), and corresponds to a single non-terminal of the language grammar. Therefore, the macro won't work when (y z ...) is a case or match clause, a type level expression, or anything but a normal expression (I was tempted to say regular expression or normal form, but these are terms of art with their own entrenched meaning). And so began my quest for a correct implementation of nest.

The difficulty here is that you really want to fold-right, starting with the inner form and bubbling up inside each consecutive outer form; but what was trivial to express recursively, yet not quite correct, was that fold-left above, assuming each nested form was an expression. My first correct solution used two macros as follows:

(define-syntax Rnest
  (syntax-rules ()
    ;;((_ () ()) ()) ;; This case is an error, actually
    ((_ (rev ...) (one more ...)) (Rnest (one rev ...) (more ...))) ;; reverse the outer form list
    ((_ (x (y ...) z ...) ()) (Rnest ((y ... x) z ...) ())) ;; recursively nest
    ((_ (x) ()) x))) ;; return
(define-syntax nest
  (syntax-rules ()
    ((_ x ...) (Rnest () (x ...)))))

The Rnest macro that does the job of nesting the forms, in two phases: first by reversing the list by accumulating its elements one by one into an accumulator list; and second by folding left on the accumulated list. Each step is tail recursive so the macro always remains in control of the expansion until the end, without having to rely on any sub-form to itself be an expression that partakes in the expansion protocol (syntax-rules, like maybe all but one macro systems, only allows macro-expansion for one kind of grammatical non-terminal, the expression; the only exception I know to this rule is Racket's syntax/parse, where multiple kind of grammatical non-terminals each can have their own macro extensions). The reverse step will be familiar to anyone who ever tried to prove correct an implementation of reverse in e.g. Coq; or to prove correct an implementation of append, which often involves the append-reverse function.

Now, exposing the binding to the Rnest macro above isn't very hygienic. Ideally, you'd like to have Rnest itself be lexically defined, such that it is seen by nest but not anything else. Here is how I eventually did it, after someone tipped me that (... ...) was the proper way of quoting the ellipsis ... so it could be present in nested macros:

(define-syntax nest
  (syntax-rules ()
    ((_ x ...)
           (syntax-rules ()
             ((_ (xx (... ...)) (y z (... ...))) (r (y xx (... ...)) (z (... ...)))) ;; reverse the list
             ((_ (xx (y (... ...)) z (... ...)) ()) (r ((y (... ...) xx) z (... ...)) ())) ;; nest
             ((_ (xx) ()) xx)))) ;; bottom case
       (r () (x ...))))))

Note how it's essentially the same macro as previously, except for some ugly renamings: the internal version of Rnest is just called r, but its ellipsis has to be quoted as (... ...), and its variable x has to be renamed xx not to clash with the outer x that further demands to be used with an ellipsis (unless I suppose you quote it everywhere as (... x)). So, this hygienic version of nest using syntax-rules works but is particularly ugly. That said, it is not quite as ugly as what I had to go through before I was told how to quote the ellipsis...

Without quoting the ellipsis, you can still use syntax-rules to define the nest macro, but now you have to get creative, and use tail-recursion only with continuation-passing style so that all your transformations are done without requiring expansion from any subform, none of which might be an expression. That's where we actually use this tail-recursive append-reverse macro rev-app (in the body of the macro, at the bottom of the definition); its continuation will be calling the left-folding macro nest-rev that nests the reversed list of forms. It's all straightforward if you know continuation-passing style applied to macros (or even just to functions in general; macros being just source-transforming functions):

(define-syntax nest
  (syntax-rules ()
    ((_ . forms)
           (syntax-rules ()
             ((_ . args) (error "nest error" 'args))))
          (rev-app ;; k ctx lst acc ==> k ctx ,(append (reverse lst) acc))
           (syntax-rules ()
             ((_ k ctx (hd . tl) rev) (rev-app k ctx tl (hd . rev)))
             ((_ k ctx () rev) (k ctx rev))
             ((_ k ctx x ()) (k ctx x))))
          (app ;; k ctx l1 l2 ==> (k ctx ,(append l1 l2))
           (syntax-rules ()
             ((_ k ctx l1 l2) (rev-app app-ret (k ctx l2) l1 ()))))
          (app-ret ;; (k ctx l2) rev-l1 ==> (k ctx ,(append (reverse rev-l1) l2))
           (syntax-rules ()
             ((_ (k ctx l2) revl1) (rev-app k ctx revl1 l2))))
          (nest-rev ;; given the reverse list of forms, setup the recursion
           (syntax-rules ()
             ((_ () ()) (nest-error))
             ((_ () (final . more)) (nest-rev2 more final))))
          (nest-rev2 ;; recurse
           (syntax-rules ()
             ((_ () done) done)
             ((_ (form . more) done) (app nest-rev2 more form (done))))))
       (rev-app nest-rev () forms ())))))

However, straightforward or not, this macro CPS work is extremely tedious; and if you want to do non-trivial processing in this style, you'll have to develop a library of macros in continuation-passing style to mirror each of the list-transforming functions you might have wanted to use if only you had the full power of the language while meta-programming. And then debugging meta-programs written this way will be atrocious, lacking adequate debugging support from your regular tools (the only exception here being Racket, that sports dedicated support for debugging macros). This horrible situation of having a braindamaged meta-programming language completely disconnected from your base language in which you must reinvent all data structures and libraries from scratch, without proper tooling, of course is remindful of template metaprogramming in C++, which, dreadful as it is, is still one of the more powerful of blub languages with respect to metaprogramming (then there is compile-time reflection in Java, but by the time you've handled all the boilerplate to do the simplest of things, you'll either have forgotten why you were doing it in the first place, or will have committed suicide in disgust — unless you embrace the Greenspunning and re-create Clojure or such).

Of course, if you're willing to assume that your nesting level will still remain small, and that macro-expansion of nested forms won't be a significant drag on your compilation time, then you could use this much simpler version that uses an O(n²) algorithm instead of an O(n) algorithm, by expressing your fold-right in a more direct though less efficient way (implementation courtesy of gwatt on IRC #Scheme):

(define-syntax nest
  (syntax-rules ()
    ((nest x) x)
    ((nest x ... (y ...) z) (nest x ... (y ... z)))))

Now, all this may have finished convincing you that while syntax-rules makes it simple to write simple macros, it might not be the best tool to write more elaborate macros that do not fit its simplistic assumptions. It is then time to unleash a more powerful macro-defining macro, syntax-case. Syntax-case, like syntax-rules, is hygienic, in that it tracks source location and naming contexts, so that you don't have to do it manually and carefully insert gensym everywhere; but unlike syntax-rules, it is not limited to a simple pattern language, it allows for metaprogramming using the very same language. Here is a straightforward version of the nest macro using syntax-case:

(define-syntax (nest stx)
  (syntax-case stx ()
    ((nest . xs)
     (let loop ((forms (syntax->list #'xs)))
        ((null? forms) #'xs)
        ((null? (cdr forms)) (car forms))
        (else #`(#,@(syntax->list (car forms)) #,(loop (cdr forms)))))))))

The above loop follows the same naive approach as we were initially trying to use with syntax-rules: it manually does a left fold on the list of forms; unlike the syntax-rules version, though, it works even if the forms are not expressions, because we recurse directly inside the macro-expanding function, rather than by hoping that the next form will be an expression that recursively macro-expands. Recursion is much easier and nicer to use with syntax-case, because you have the full power of your language as a meta-language, instead of an ad hoc term-rewrite engine.

Now, if the #`(#,@ characters looked like line noise to you, they were quasisyntax and unsyntax-splicing, the syntax-case analogue to quasiquote and unquote-splicing that you use with Common Lisp style macros. But if quasisyntax is alien to you or unimplemented in your Scheme, you can also manipulate the syntax directly, using the datum->syntax and syntax->list primitives:

(define-syntax (nest stx)
  (syntax-case stx ()
    ((nest . xs)
     (let loop ((forms (syntax->list #'xs)))
        ((null? forms) #'xs)
        ((null? (cdr forms)) (car forms))
        (else (datum->syntax #'nest
                (append (syntax->list (car forms)) (list (loop (cdr forms)))))))))))

Of course, instead of doing the recursion manually, you could explicitly use a left fold, just like the reduce in Common Lisp (there again thanks to gwatt for his help):

(define-syntax (nest stx)
  (syntax-case stx ()
    ((nest outer ... inner)
     (foldl (lambda (o i) #`(#,@o #,i)) #'inner (reverse (syntax->list #'(outer ...)))))))

And there again, we can write the same thing without quasisyntax:

(define-syntax (nest stx)
  (syntax-case stx ()
    ((nest outer ... inner)
     (foldl (lambda (o i) (datum->syntax #'nest `(,@(syntax->list o) ,i)))
            #'inner (reverse (syntax->list #'(outer ...)))))))

And of course we can directly use a right fold, instead of a left fold on the reverse. That's very similar to the Common Lisp macro, just with some extra wrapping and unwrapping to maintain hygiene.

(define-syntax (nest stx)
  (syntax-case stx ()
    ((nest outer ... inner)
     (foldr (lambda (o i) #`(#,@o #,i)) #'inner (syntax->list #'(outer ...))))))

And as always, we can do it without quasisyntax, instead using quasiquote to implicitly express a call to the append function:

(define-syntax (nest stx)
  (syntax-case stx ()
    ((nest outer ... inner)
     (foldr (lambda (o i) (datum->syntax #'nest `(,@(syntax->list o) ,i)))
            #'inner (syntax->list #'(outer ...))))))

Now the macro is so simple, with a single trivial pattern to match, that you could even write the expander directly without syntax-case:

(define-syntax (nest stx)
  (let ((forms (syntax->list stx)))
    (let loop ((more (cdr forms)))
       ((null? more) #'stx)
       ((null? (cdr more)) (car more))
       (else (datum->syntax (car forms) ;; in Racket, stx would do
               (append (syntax->list (car more)) (list (loop (cdr more))))))))))

Also, you could use syntax->datum instead of syntax->list but that would needlessly lose syntax location data on the recursive objects:

(define-syntax (nest stx)
  (syntax-case stx ()
    ((nest . xs)
     (datum->syntax #'nest ;; Gerbil wants an identifier; Racket works well with stx.
       (let ((forms (reverse (syntax->datum #'xs))))
         (let loop ((acc (car forms)) (more (cdr forms)))
           (if (null? more)
             (loop `(,@(car more) ,acc) (cdr more)))))))))

Last but not least, here is the version I actually use in my code, as proposed by vyzo. It uses ellipses to do the appending directly on syntax; to achieve this, it first uses with-syntax to establish a binding between the macro's runtime variable o and i and the macro's compile-time syntax variables outer and inner; outer can then use the ellipsis to express the appending (note that Gerbil unlike Racket does not need the (syntax->list ...) wrapper):

(define-syntax (nest stx)
  (syntax-case stx ()
    ((nest outer ... inner)
     (foldr (lambda (o i)
              (with-syntax (((outer ...) o)
                            (inner i))
                #'(outer ... inner)))
            #'inner (syntax->list #'(outer ...))))))

So there, we've seen a simple macro, nest, how it interestingly trivializes a problem that others tried very hard to solve with extremely elaborate macros, how it can be implemented in three different widely used macro systems, and what are some issues with writing macros in Scheme rather than Lisp — the price you pay for hygiene (mind that just because I do not discuss the benefits does not mean there aren't such very valuable benefits). Note that this macro is pretty much the worst case scenario when translating a Common Lisp macro into a Scheme macro: it doesn't use any gensym so doesn't benefit from any of the hygiene machinery, and its pattern is just a bit off from what is easy with syntax-rules. Yet in the end, it isn't too hard to translate it. Translating it was a good exercise in learning Scheme macro systems.

Nicolas HafnerPortacle Release - Confession 75

· 40 days ago

I've written about Portacle on a previous occasion, where I talked mostly about the issues I've faced. This time, however, I'm excited to announce that Portacle has finally reached version 1.0. This means that there are no obvious remaining issues that I am aware of. Everything should Just Work™.

In case you're confused about what Portacle even is, it stands for the Portable Common Lisp development Environment. It's a combination of Emacs, SBCL, Quicklisp, GIT, and a variety of other, smaller components that together bring you a fully-fledged IDE that runs on the three major operating systems in use today. It is installable with a simple extraction and fully contained in its own directory. It can thus be loaded onto a USB stick for use on the go as well.

Portacle is primarily intended to target both complete newcomers, for which the installation procedure of a full Emacs setup otherwise involves a lot of confusing and complicated steps, and advanced users that simply need a quick way to set up a running environment on a machine. Portacle is especially convenient to test your libraries on different systems.

I have personally tested Portacle to run properly on the following platforms:

  • Windows 7
  • Windows 10
  • OS X 10.11
  • OS X 10.12
  • Ubuntu 16.04
  • Linux Mint 17.3
  • Debian 8
  • Fedora 25
  • Arch Linux

Note that currently the following platform versions are supported:

  • Windows 7+ x64
  • OS X 10.11+ x64
  • Linux 3.13+ x64

You can download the current release here. If your system falls within these constraints and Portacle won't run properly for you, please do file an issue so that I can see what else needs fixing.

If you otherwise have suggestions regarding documentation extension, adding features, or smoothing out rough edges, please file an issue as well, or hop onto the #shirakumo IRC channel on Freenode to chat directly with me. I'd be happy to hear your thoughts.

Zach BeaneSeptember of Sly

· 40 days ago

I like the idea of sly: like slime, but cooler. Less conservative with changes, less concerned about backwards-compatibility, more features, cleaner implementation, etc. But I don’t know that much about it in detail, and I’ve never tried it - until now.

I’m going to use sly exclusively for the month of September. As I bump into differences from slime, I’m taking notes and will share them here. I hope to give people an idea about what it’s like to switch and help them decide if it’s worthwhile for them, and figure out if I’ll be switching back on October 1.

So here are a few quick notes from getting started:

  • Pretty easy to install, but not as easy as quicklisp-slime-helper - I can make a sly-helper in the future
  • Would not start initially because I had a reference to the swank package in my ~/.swank.lisp file. Referencing swank in a swank init file seems reasonable so it was a little annoying to have to add some #+swank/#+sly conditionalization.
  • I use slime-selector a lot, and it’s moved into a keymap in sly - I like that it now uses a standard Emacs UI instead of a custom UI
    • …but it’s missing the “l” binding, which I use a hundred times a day, so I wrote a little bit of elisp to add it back
    • docstring of sly-selector-map helps explain what to do
    • Window management in sly-selector confuses me - expect REPL to replace current window, but it seems to go somewhere else every time
  • comma commands are different! I use ,chTAB and ,cdRET a hundred times a day, and now they are ,set package (which has nice completion) and ,set directory
  • Much more verbose repl output for integers at least:
    • (+ 1 1) => 2 (2 bits, #x2, #o2, #b10)
  • M-RET in REPL history does what I expect
  • Not 100% sure how to get started with stickers, but C-c C-s ? has good starting points
  • Should read manual…

Stay tuned for more!

TurtleWareTutorial: Working with FiveAM

· 43 days ago

What is FiveAM?

FiveAM is a simple-yet-mature test framework. It makes test suites for your project easy to implement, maintain, organize and run.


While it can't be said that there are no learning materials provided for FiveAM, it feels like they are lacking in both clarity and detail. Beginners are in need of gentle, friendly guidance. Experienced Lisp hackers are able to make do without it, but even they probably spend a little extra time tinkering, experimenting and skimming source code to "get" the framework. This shouldn't be necessary.

This tutorial assumes familiarity with Common Lisp and a basic understanding of ASDF system definitions.

Our building blocks

We will start with a bit of theorizing. Be not afraid, however - there won't be too much of it.

The essential terms you will need to be familiar with are:

  • Checks
  • Tests
  • Test suites


A check is, essentially, a single assertion - a line of code that makes sure something that should be true is indeed true. FiveAM tries to make assertions as simple as possible. The form of a basic check definition looks like this:

(is test &rest reason-args)

In this case,test is the assertion we want to make. A function (or special operator) application with any number of arguments can be used as the assertion. If it returns a true value, the assertion succeeds; if it returns NIL, it fails.

If the test parameter matches any of the 4 "templates" below, FiveAM will try to reason a little about what is what and attempt to print the explanations of failures in a more readable way. Arguably.

(predicate value)
(predicate expected value)
(not (predicate value))
(not (predicate expected value))

The logic FiveAM follows when reasoning is thus:

The first expression checks whether value satisfies predicate.

In the second one, the predicate is usually some form of equality test. The assertion makes sure the value we got (by calling some function we're testing) matches the expected value according to the predicate.

The last two tests are the same things, only negated.

In practice, these declarations look like this:

(is (listp (list 1 2)))   ; is (list 1 2) a list?
(is (= 5 (+ 2 3)))        ; is (+ 2 3) equal 5?

Simple, right? If we were implementing standard Lisp functions, we could use the above to test whether list generates a list as it should, and whether + sums properly. Or, well, at least we'd ascertain that for the above cases.

And if we wanted to negate:

(is (not (listp (list 1 2))))  ; is (list 1 2) not a list?
(is (not (= 5 (+ 2 3))))       ; is (+ 2 3) not equal 5?

As you may have noticed, we haven't used the optional reason-args argument. It's used to specify what's printed as the reason for a failed check. Sometimes FiveAM's reasoning just isn't good enough. We will get back to it when we start hacking away.


We know how to write checks, but there's not much we can actually do with just this knowledge. The is syntax is only available in the context of a test definition.

A test, as defined by FiveAM, is simply a collection of checks. Each such collection has a name so that we can easily run it later. Defining one is easy:

(test test-+
  "Test the + function"     ;optional description
  (is (= 0 (+ 0 0)))
  (is (= 4 (+ 2 2)))
  (is (= 1/2 (+ 1/4 1/4))))

We're sticking to the basics for now, but you should know there are some additional keyword parameters you can pass in order to declare dependencies, explicitly specify the parent suite, specify the fixture, change the time of compilation and/or collect profiling information.

A fixture is something that ensures a test is run in a specific context. Sometimes it's necessary to reproduce results consistently. For example, if you had a pathfinding algorithm, you'd probably have to load some sort of a map before you could test it. Apparently, using FiveAM's fixture functionality isn't recommended by the current maintainer. Perhaps it's best to just set up macros for those.

As for profiling information, this functionality doesn't seem to actually be implemented yet. Instead, Metering is a good option if needed.

You'll most likely end up defining a single test for a single function, but nothing stops you from slicing the pie up differently. Maybe a particularly complex function requires a lot of checks that are best divided into categories? Maybe a set of simple, related functions can be covered by a single test for simplicity? Your common sense is the best advisor here.


The final piece of the puzzle. These are not obligatory, but very useful. Suites are containers for tests, good if you need more hierarchy - which, honestly, you will. Speaking of hierarchy: suites can parent other suites, so you can have plenty of that.

The way suites are defined and used is roughly analogous to packages.

(def-suite tutorial-suite
    :description "A poor man's suite"
    :in some-parent-suite)

(in-suite tutorial-suite)

The first form defines a test suite called tutorial-suite. The in keyword is used to set the parent suite.

Just like in-package sets the *package* special variable, in-suite sets the *suite* one. Test definitions pick up on it when provided. Thanks to that, any test definitions after (in-suite tutorial-suite) will be included in tutorial-suite. Other suite definitions, however, won't be automagically contained in the suite pointed to by *suite*. For that reason, you always need to explicitly set the in keyword when defining a child suite.

And that's actually all there is to suites.

The story so far

Time for a quick summary - from the top, our tests are organized like this:

  • (optional) Top-level test suites defined with (def-suite)
  • (optional) Child test suites defined with (def-suite) with :in set
  • Tests defined with the (test) macro
  • Checks (assertions) defined with (is) expressions within a (test) form

A practical example

Now that all that is clear, let's try doing something with it. Imagine you are building an RPG game according to some existing pen-and-paper system. One day, it will surely rival the likes of AAA+ titles out there.

...for now, though, you only have the character generation facility down. Oh well, got to start somewhere. According to the specification of the system you're using, the stats of a character are generated randomly, but prior to the generation, a player can choose two stats they wish to "favor". Unfavored stats are decided on with a roll of two 8-sided dice, while favored ones - a roll of three 8-sided dice. You've defined a little utility function for rolling an arbitrary number of dice with an arbitrary number of sides.

You've written this basic functionality, wrapped it up in a package, defined an ASDF system, checked that everything compiles without warnings... So far, so good. But now you want to go the extra mile to make sure this is going to be a well-built piece of software. You want to integrate tests.

If you'd like to follow all the outlined steps and integrate FiveAM with me, just clone the master branch of the quasirpg repository.

git clone

Ideally, if you have quicklisp, do that in ~/quicklisp/local-projects/. Otherwise, clone the repository to either ~/common-lisp/ or ~/.local/share/common-lisp/source/.

If you wish, you can also look through the commit history of the test branch to see exactly how I've done all the work detailed in the following sections. It might come in useful if you get stuck.

If you want to see the code in action, try these:

CL-USER> (ql:quickload 'quasirpg)
CL-USER> (in-package #:quasirpg)
QUASIRPG> (roll-dice 3 6) ; throw three 6-sided dice
QUASIRPG> (make-character)
QUASIRPG> (make-character "Bob" '("str" "int"))

In case you don't have quicklisp, you can use this to load the system:

CL-USER> (asdf:load-system 'quasirpg)

Keep in mind that without quicklisp, you will also have to download FiveAM by hand. In the same directory you cloned quasirpg to, try:

git clone


Tests shouldn't be a part of your software's main system. Why would they be? People who simply want to download your application and use it don't need them. Neither do they need to pull FiveAM as a dependency. So let's define a new system for tests. We could create a separate .asd file, but I like to have just one .asd file around. In this case, any additional systems defined after the main quasirpg one should be named quasirpg/some-name. So we append this to our quasirpg.asd:

(asdf:defsystem #:quasirpg/tests
  :depends-on (:quasirpg :fiveam)
  :components ((:module "tests"
            :serial t
            :components ((:file "package")
                         (:file "main")))))

We also create the new files tests/package.lisp and tests/main.lisp to make true to the above declaration. As you might guess, we're planning to define a separate package for tests. This isn't as important as separate systems, but it's always good to keep namespaces separate. Nice and tidy.

;;;; tests/package.lisp

(defpackage #:quasirpg-tests
  (:use #:cl #:fiveam)
  (:export #:run!

And finally the star of the show:

;;;; tests/main.lisp

(in-package #:quasirpg-tests)

(def-suite all-tests
    :description "The master suite of all quasiRPG tests.")

(in-suite all-tests)

(defun test-quasi ()
  (run! 'all-tests))

(test dummy-tests
  "Just a placeholder."
  (is (listp (list 1 2)))
  (is (= 5 (+ 2 3))))

Defining a simple, argument-less test runner for the whole system (test-quasi here) isn't strictly necessary, but it's going to spare us some potential headaches with ASDF.

We define a meaningless test just so we can check whether the whole setup works. If you've done everything correctly, you should be able to load the test system in your REPL

CL-USER> (ql:quickload 'quasirpg/tests)

and run the test runner

CL-USER> (quasirpg-tests:test-quasi)

Running test suite ALL-TESTS
 Running test DUMMY-TESTS ..
 Did 2 checks.
    Pass: 2 (100%)
    Skip: 0 ( 0%)
    Fail: 0 ( 0%)


So far, so good!

ASDF integration

Integrating the tests with ASDF is a good idea. That way we get hooked up to the standard, abstracted way of triggering system tests. First, we add this somewhere to our quasirpg/tests system definition.

:perform (test-op (o s)
            (uiop:symbol-call :fiveam :run! 'quasirpg-tests:all-tests))

From now on, we can run all-tests with:

CL-USER> (asdf:test-system 'quasirpg/tests)

Next, we tell ASDF that when someone wants to test quasirpg, they really want to run the quasirpg/tests test-op. Somewhere in the quasirpg system definition:

:in-order-to ((test-op (test-op "quasirpg/tests")))

Now all we need to do to test our game is:

CL-USER> (asdf:test-system 'quasirpg)

Adding real tests

Most of the character generation system's math is within the dice-rolling function - it's probably a good idea to tackle that one. The only problem is it's not a very predictable one. We can, however, still do some useful things.

(defun test-a-lot-of-dice ()
  (every #'identity (loop for i from 1 to 100
                       collecting (let ((result (quasirpg::roll-dice 2 10)))
                                    (and (>= result 2)
                                         (<= result 20))))))

(test dice-tests
  :description "Test the `roll-dice` function."
  (is (= 1 (quasirpg::roll-dice 1 1)))
  (is (= 3 (quasirpg::roll-dice 3 1)))
  (is-true (test-a-lot-of-dice)))

The first two checks simply provide arguments for which the function should always spew out the same values - we're throwing one-sided dice. Just... try not to think too hard about it.

The function test-a-lot-of-dice returns true only if every one of 100 throws of two 10-sided dice is within the expected bounds, that is 2-20. All we have to do is check whether that function returns true. We can just write (is (test-a-lot-of-dice)), but I recommend using is-true instead, since the way it prints failures is more readable in cases like this.

In all honesty, test-a-lot-of-dice could be improved in terms of optimization (for example by making it a macro that wraps the 100 checks in an and) or functionality (the parameters passed to roll-dice could be random). But this version is simple and sufficient for this tutorial.

Now let's see this thing in action.

Running test suite ALL-TESTS
 Running test DICE-TESTS fff
 Did 3 checks.
    Pass: 0 ( 0%)
    Skip: 0 ( 0%)
    Fail: 3 (100%)

And there we go. We've just detected a bug that would never be caught by the compiler. A look at the first fail gives us a hint:


 evaluated to 


 which is not 




A look at the function in question should be enough to see the problem.

  (let ((result (loop for i from 1 to n summing (random sides))))

What (random sides) does is generate a number from 0 to (sides - 1). That's not what we want.

  (let ((result (loop for i from 1 to n summing (1+ (random sides)))))

And now we re-run the tests:

Running test suite ALL-TESTS
 Running test DICE-TESTS ...
 Did 3 checks.
    Pass: 3 (100%)
    Skip: 0 ( 0%)
    Fail: 0 ( 0%)

The true power of tests, however, is that if we now ever decide to modify our dice-throwing facility, any bugs we introduce by accident will most likely be caught by the tests already in place. And so we'll avoid nasty, hard-to-debug consequences further down the line. All that without having to test things by hand each time we make changes.

Handling invalid parameters

What happens when someone passes a non-positive integer to roll-dice? Or a fractional one? We should probably control that behavior. And we should probably test to make sure when the unexpected happens, it's handled as expected.

Let's say our specification tells us that when any of the arguments is fractional, it should just be rounded down. So we append two additional tests to dice-tests:

  (is (= 3 (quasirpg::roll-dice 3.8 1)))
  (is (= 3 (quasirpg::roll-dice 3 1.9)))

The first one actually passes. It just so happens that loop is responsible for looping N times over the random number generation for each die. loop rounds down a fractional number if it's passed one.

The second test requires our attention. It fails. The problem is that random is passed a fractional argument, and it thinks it's meant to give a fractional number in response. Simple fix and we're back on track:

  (let ((result (loop for i from 1 to n summing (1+ (floor (random sides))))))

Now for something more interesting. Let's say our specification tells us that if any argument is not a positive number, we should get a SIMPLE-TYPE-ERROR. It's time to introduce yet another kind of check.

(signals condition &body body)

Not a lot to explain here. BODY is expected to cause CONDITION to be signaled. Our check only succeeds if it does. We can use this:

  (signals simple-type-error (quasirpg::roll-dice 3 -1))
  (signals simple-type-error (quasirpg::roll-dice 3 0))
  (signals simple-type-error (quasirpg::roll-dice -1 2))
  (signals simple-type-error (quasirpg::roll-dice 0 2))
  (signals simple-type-error (quasirpg::roll-dice -1 1))

Again, some of the work is already done for us. random will signal a SIMPLE-TYPE-ERROR in response to a non-positive arg. What's left to do is to handle the number of throws, so we add the appropriate code to the beginning of roll-dice:

(if (< n 1)
      (error 'simple-type-error
         :expected-type '(integer 1)
         :datum n
         :format-control "~@<Attempted to throw dice ~a times.~:>"
         :format-arguments (list n)))

And voila. Once more, all checks pass.

Random number generators

So far, we've used specific numbers. We can do better, though. We can run a large amount of checks based on random data. This is where the fiveam:for-all check comes in that runs tests 100 times, randomizing specified variables each time.

(for-all bindings &body; body)

bindings is a list of forms of this type:

(variable generator)

generator is a function (or function-bound symbol) that returns random data. variable is the variable binding that stores the results from generator.

body can contain other kinds of checks.

For example, let's try replacing (is-true (test-a-lot-of-dice)) with something more comprehensive.

(for-all ((n (gen-integer :min 1 :max 10))
          (sides (gen-integer :min 1 :max 10)))
  "Test whether calls with random positive integers give results within expected bounds."
  (let ((min n)
        (max (* n sides))
        (result (quasirpg::roll-dice n sides)))
    (is (<= min result))
    (is (>= max result))))

(gen-integer :min 1 :max 10) is a function provided by FiveAM that returns a random integer generator with the specified bounds. We keep the numbers small here so that the tests don't take forever trying to throw a lot of dice, and so that there's a reasonable chance of edge cases getting tested.

We can also replace the rounding checks. Since FiveAM doesn't provide a suitable generator, we have to write our own. It's not difficult, though, thanks to CL's ease of creating higher-order functions:

(defun gen-long-float (&key (max (1+ most-positive-long-float))
                            (min (1- most-negative-long-float)))
  (lambda () (+ min (random (1+ (- max min))))))

With that definition in place, we can write the new checks:

  (for-all ((valid-float (gen-long-float :min 1 :max 100)))
    "Test whether floats are rounded down."
    (is (= (floor valid-float) (quasirpg::roll-dice valid-float 1)))
    (is (>= (floor valid-float) (quasirpg::roll-dice 1 valid-float))))

Finally, we can replace our condition checking too:

  (for-all ((invalid-int (gen-integer :max 0))
            (invalid-int2 (gen-integer :max 0))
            (valid-int (gen-integer :min 1)))
    "Test whether non-positive numbers signal SIMPLE-TYPE-ERROR."
    (signals simple-type-error (quasirpg::roll-dice valid-int invalid-int))
    (signals simple-type-error (quasirpg::roll-dice invalid-int valid-int))
    (signals simple-type-error (quasirpg::roll-dice invalid-int invalid-int2))))

If you run these tests, you'll notice only a few checks in the results. That's because FiveAM treats each for-all declaration as a single check, regardless of the contents or the hundreds of tests that actually get run.


When the tests we've written failed, the output we got was mostly descriptive enough. That's not always the case. It's hard to expect the testing framework to know what sort of information is meaningful to us, or what the concept behind the functions we write is.

So let's say when we make-character, we want the name to be automatically capitalized. We care about punctuation and won't allow our players to get sloppy with it. Pshaw.

We add a new test:

(test make-character-tests
  :description "Test the `make-character` function."
  (let ((name (quasirpg::name (quasirpg::make-character "tom" '("str" "dex")))))
    (is (string= "Tom" name))))

Obviously, it fails.

 Failure Details:

 evaluated to 


 which is not 





We can understand it, but put yourself in the position of someone who isn't all that familiar with the make-character function. Imagine that person just got the above output while testing the entire game. They're probably really scratching their head trying to piece this together. Let's make life easy for them. Attempt number 2:

(test make-character-tests
  :description "Test the `make-character` function."
  (let ((name (quasirpg::name (quasirpg::make-character "tom" '("str" "dex")))))
    (is (string= "Tom" name)
    "MAKE-CHARACTER should capitalize the name \"tom\", but we got: ~s" name)))

We use the &rest reason-args parameter of the is check. You can use format directives and pass it arguments, just like in a format call. Now the test result is much easier to interpret:

 Failure Details:
      MAKE-CHARACTER should capitalize the name "tom", but we got: "tom".


Let's imagine what happens when the project grows. For one thing, we'll probably write many more tests, until having all of them in one file looks rather messy.

We'll also probably eventually end up reorganizing the code. roll-dice might eventually end up a part of a collection of utilities for generating randomized results, while make-character could get moved to chargen.lisp. It would be good if the hierarchy of our tests reflected those changes and let us test only random-utils.lisp or chargen.lisp if we want to.

So above all of our dice-testing code we tuck this in:

(def-suite random-utils-tests
    :description "Test the random utilities."
    :in all-tests)

(in-suite random-utils-tests)

Now all-tests contains random-utils-tests, which in turn contains dice-tests.

Let's do the same for character generation:

(def-suite character-generation-tests
    :description "Test the random utilities."
    :in all-tests)

(in-suite character-generation-tests)

(test make-character-tests
  :description "Test the `make-character` function."
  (let ((name (quasirpg::name (quasirpg::make-character "tom" '("str" "dex")))))
    (is (string= "Tom" name)
    "MAKE-CHARACTER should capitalize the name \"tom\", but we got: ~s" name)))

You can check that running (asdf:test-system 'quasirpg) still runs all of our tests, since it launches the parent suite all-tests. But we can also do (fiveam:run! 'quasirpg-tests::make-character-tests).

The next logical step is moving the test suites to separate files. If you wish to see how I've done it, just look at this commit or at the end result in the test branch.

What else is there?

A few different kinds of checks and a way to customize the way test results and statistics are presented.

So far, we've always used run! to run all the tests, which is really a wrapper for (explain! (run 'some-test)). You can, therefore, replace the explain! function with your own.

How can you learn about those things? The best I can do is point you to the FiveAM documentation and possibly source code.

Happy hacking!

Eugene ZaikonnikovAlso ALSA

· 44 days ago

After having some issues with microphone input handling in portaudio I took a shortcut and sketched Also ALSA: an interface to Advanced Linux Sound Architecture library. As the name suggests, it's not the first CL wrapping of it. It is however small, reasonably self-contained and can handle both input and output.

LGPL to comply with alsa-lib.

Quicklisp newsAugust 2017 Quicklisp dist update now available

· 48 days ago
New projects:
  • cl-cognito — Amazon Cognito Utilities — BSD
  • cl-conllu — Common Lisp corpus conllu utilities — Apache 2.0
  • cl-json-helper — Handy extras for cl-json — BSD
  • cl-moss — Common Lisp submission mechanism for Stanford's MOSS system — GPLv3
  • cl-tiled — Tiled ( Loader — zlib/libpng License
  • configuration.options — An extensible configuration system that supports multiple option sources. — LLGPLv3
  • gamebox-sprite-packer — A spritesheet packer for games. — MIT
  • jose — JSON Object Signing and Encryption (JOSE) implementation — BSD 2-Clause
  • pngload — A reader and writer for the PNG image format. — MIT
  • poiu — Parallel Operator on Independent Units — MIT
  • shorty — Shorten URLs using third-party services. — MIT
  • trivial-file-size — Stat a file's size. — MIT
  • trivial-project — A simple project skeleton generator with key-value substitution — BSD Simplified (2-clause)
  • trivial-renamer — rename and manage categorized named objects — BSD 3-clause license
  • trivial-with — Replace nested with-xxx invocations with a single with:all form — BSD 3-clause license
Updated projects3bgl-shader3d-matrices3d-vectorsacclimationalexandriaarchitecture.builder-protocolarray-utilsasd-generatorcalispelceplcepl.glopcepl.sdl2checklchirpcl-anacl-fondcl-formscl-gamepadcl-gpiocl-groupbycl-k8055cl-marshalcl-mixedcl-monitorscl-mpg123cl-ntp-clientcl-online-learningcl-out123cl-pixmancl-random-forestcl-soloudcl-spidevcl-tidyclipclmlcloser-mopclssclxcoleslawcolleencroatoancrypto-shortcutsdeedsdeferreddeploydexadordirtdissectdo-urlencodedocumentation-utilsdrakmaeasy-routesecoesrapfast-iofiascoflac-parserflareflowfnforform-fiddlefs-utilsfsetfxmlgamebox-dgengamebox-gridsglkitglsl-specglsl-toolkithalftoneharmonyhu.dwim.graphvizhu.dwim.perechu.dwim.reiteratehumblerieee-floatsjson-streamslambda-fiddlelasslegitliblmdblichat-protocollichat-serverliblichat-tcp-clientlichat-tcp-serverlichat-ws-serverlionchatlquerymagicffimaidenmcclimmitomodularizemodularize-hooksmodularize-interfacesninevehnorthopticloverlordpapyrusparachuteparse-floatparseqpathname-utilspipingplumpplump-bundleplump-sexpplump-texpng-readqt-libsqtoolsqtools-uiquux-hunchentootracerrandom-stateratifyredirect-streamsanitized-paramsscalplserapeumsimple-inferiorssimple-tasksskitterslimesoftdrinksouthspinneretstaplestumpwmsxqltrivial-argumentstrivial-benchmarktrivial-indenttrivial-main-threadtrivial-mimestrivial-thumbnailubiquitousunit-formulavarjoverbosewebsocket-driverwooworkout-timerxsubseq.

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


Wimpie NortjeGetting started with Common Lisp

· 51 days ago

Are you trying to get started with Common Lisp but find it difficult to make progress? People keep on saying that there are plenty free resources available online. Maybe you have even found most of them ... and yet the questions remain ... What is the Lisp syntax? Are there any libraries and how do I find them? Can I compile my program into a binary or are users forced to install a compiler?

The list goes on: What is the meaning of those asterisks around the *VARIABLE* names? Which implementation should I use? Where do I go for help when I get stuck?

How do I connect my IDE to the debugger because really ... who in their right mind want learn Emacs just to use Common Lisp?

There are plenty learning resources on the web. For free. In the wonderful world of Common Lisp you always have multiple choices to achieve your goal. Starting with the choice of which implementation you should use.

In some aspects this post is similar to many of the other "Getting Started" articles and in some aspects it is different. This is my take on which initial choices to make and why. The choices are neither better nor worse than the alternatives but importantly, they are not binding. At any point in the future you can switch away from any of the choices I made without severe impact on your progress. The important thing is to accept some set of initial choices and to get started. You will only discover through experience whether you agree or disagree with the choices.

Common Lisp is a vast ocean of possibilities, stretching infinitely and with no horizon... And here I am pretending to understand the MOP while trying not to end up in r/badcode, like a child playing in the surf...

Comment in the Crane library's source code

The steps

Before you can start working seriously you need a functional development environment. The Portacle project can give you a jump start here. It packages all the recommended tools to provide a ready-made Lisp development environment. If you choose this option configure Portacle then start with step 4 below. Installation instructions are on the Portacle page.

I prefer to install software natively. If you choose this option follow the steps from the beginning.

  1. Set up a Lisp implementation.
  2. Set up the library installer.
  3. Set up the development environment.
  4. Locate reference documentation.
  5. Pick a project.
  6. Deploy your program.

Set up an implementation

There are a number of Common Lisp implementations available, each with its own unique features. If you don't know why you need to use a specific implementation, use CCL (Clozure Common Lisp) or SBCL (Steel Bank Common Lisp). They are easy to set up because they don't have any external dependencies. Since Common Lisp is a standardised language you can trivially switch implementations later if you really need to.

Many people prefer SBCL. If your OS has an installation package for it, use that. Otherwise you can find the installation instructions on the website.

I prefer to use CCL because it has faster compile times than SBCL.

Install CCL

Download the version for your OS. Use the SVN method because that makes it easier to upgrade later on.

$ svn co

Copy the file ccl/scripts/ccl64 to a directory that is in your path. On Linux a good place is /usr/local/bin. Rename it to "ccl"

$ cp ccl/scripts/ccl64 /usr/local/bin/ccl

Edit the script in /usr/local/bin. Change CCL_DEFAULT_DIRECTORY=/usr/local/src/ccl to point to the place where you installed CCL

Run "Hello world"

Start CCL

$ ccl

In the REPL, execute

? (format t "Hello world!")

The command should print

Hello world!

Exit the REPL with

? (quit)

Set up the library installer

The easiest way to obtain and install libraries is to use Quicklisp.

The following steps set up Quicklisp in your Lisp implementation:

  1. Download the setup script. In Linux it would be

    $ wget

  2. Install Quicklisp in CCL:

    Start CCL

    $ ccl

    In the REPL, execute

    (load "quicklisp.lisp")
  3. Test the installation

    ? (ql:system-apropos "alexandria")

    The command should print information about the Alexandria library. Something like this:

    #<SYSTEM alexandria / alexandria-20170630-git / quicklisp 2017-07-25>
    #<SYSTEM alexandria-tests / alexandria-20170630-git / quicklisp 2017-07-25>

Set up a development environment

Picking a text editor

One of Common Lisp's biggest productivity advantages is the REPL (Read-Evaluate-Print Loop). It looks and functions a lot like the operating system's command line interface which executes commands as they are entered. Variables and defined functions remain available throughout the REPL session. New functions can be defined one at time.

In contrast to languages like C where your program must be compilable before you can test any change, in the REPL you can compile only the function you want to test without having a complete application.

To understand the implication, suppose you have function A which is called by many other functions throughout the application and you want to change A's argument list. In C you'd have to update all the functions that call A before you can compile the program to actually test the change. In Common Lisp you can make the change, update one function and test it. Only when you are satisfied with the results you have to update the other calling functions.

The described workflow is completely possible with any random text editor and loading the source files directly in the REPL. After making and testing changes in the REPL only the final modifications need to be transferred to the source files. While using Lisp in this way is possible, there is a disconnect between the text editor and the Lisp implementation which can negate the advantages brought by the REPL.

When the text editor is able to control the REPL it allows you to make exploratory changes directly in the source files then compile and test only the modifications. At the end of this exploratory cycle the source files are already up-to-date and all that remain is to update the rest of the calling functions.

The tool that enables control over the REPL is called SLIME1. It is the most advanced and mature tool for this purpose and it is specifically developed for Emacs. SLIME has been adapted for use in other editors2 but they have fewer users and contributors and thus always lag behind the latest SLIME development.

When setting out to learn Common Lisp the path of least resistance is to use Emacs, even with all its foreign concepts and non-standard shortcut keys. Once one appreciates the power and productivity because of SLIME it is easier to look past Emacs' aged appearance and arcane user interface.

Install SLIME

In the CCL REPL, run the following:

? (ql:quickload "quicklisp-slime-helper")

Install Emacs

Installing Emacs should be trivial. Most Linux distributions provide installation packages in their repositories and the Emacs web page provides installation instructions for Windows and macOS.

When Emacs is working, edit or create the file ~/.emacs. To locate the file on Windows, use the File | Visit New File menu item and type ~/.emacs as the filename.

Place the following code in .emacs.

;; Set up CCL
(setq inferior-lisp-program "ccl")

;;Load Quicklisp slime-helper
(load (expand-file-name "~/quicklisp/slime-helper.el"))

Exit and restart Emacs.

Using Emacs

Emacs' key bindings (i.e. shortcut keys) differ significantly from the standard shortcut keys used in most other editors. If you don't know some basics and your menu bar happens to become hidden you will be helpless. This is a bare minimum introduction to using Emacs so that you will be able to edit Lisp files and run them with SLIME. The EmacsWiki key reference page has a much more thorough list.

Emacs shortcuts are a combination of a modifier key with a normal key. The modifiers are:

  • C - Control key.
  • M - Meta key. ALT on PCs and on Apple.
  • S - Shift key.

Key combinations are written as C-x which means press and hold Control and then press x.

C-x C-c Exit Emacs
C-x C-f Open or create file
C-x C-s Save file
C-x k Close file
M-w Copy selected text
C-w Cut selected text
C-y Paste text
C-/ Undo
C-x h Select all
C-x b Switch between buffers
M-x slime Start SLIME
C-c C-z Switch to SLIME from a Lisp buffer
C-c C-c Compile the function at the cursor
C-c M-q Indent the function at the cursor
C-up/down Move through history in SLIME buffer

If you really want to do copy, cut and paste with the same keys used in other applications then you can search for Emacs CUA mode.

Run "Hello world"


M-x slime

The first time you run SLIME there may be some delay while it is being compiled. When it is ready you should see the following in Emacs:

; SLIME 2.19

In the REPL, execute

CL-USER> (format t "Hello world!")

You should see

Hello world!

printed on the screen.

Programming and debugging

With the power of the SLIME / Emacs combination and Common Lisp's "vast ocean of possibilities" there are many ways to use the tools. Each programmer will eventually develop his or her own distinct technique.

Without spending too much time learning Emacs or SLIME early on one can become quite productive using the following approach:

Big changes:

  1. Edit a file
  2. Save the file - C-x C-s
  3. Jump to the SLIME REPL - C-c C-z
  4. Load the file - (load "app.lisp")
  5. Run the code - (some-function)

Small changes

  1. Edit a file
  2. Save the file - C-x C-s
  3. Compile the function - C-c C-c
  4. Jump to the SLIME REPL - C-c C-z
  5. Run the code - (some-function)

Locate reference documentation

When you get stuck Stack Overflow can be useful but often you get answers faster if you know about other sources of information. I posted previously on the topic of finding answers. Here is another list which is more relevant if you are only getting started.

Learn the language
Practical Common Lisp
Naming conventions
Find libraries and their documentation
Common Lisp Language reference
Help with Emacs
Use SLIME more effectively
SLIME manual
More introductory material
Articulate Lisp
When all these are not enough
Reddit r/lisp sidebar

Pick a project

To learn a new language you must write a program and for that you need a project. I have posted some ideas for beginner projects before but I think it is easier to stay motivated when you work on your own idea.

With the project in hand you now have everything to start programming and learning. At the very beginning it is easier to write all the code in one file. Loading the program is straightforward and it removes a lot of extra variables introduced when system definition files and multiple source files come into play. They are essential for bigger programs but they cause an unnecessary mental burden when you are still finding your feet.

The moment a single file becomes too convoluted to continue, stop programming and create a project skeleton with Quickproject. It creates a minimal project with all the necessary files to make it loadable with ASDF and Quicklisp.

The steps to create a project skeleton are:

(ql:quickload :quickproject)
(quickproject:make-project "path/to/project/")

Deploy your program

Common Lisp programs can be compiled into standalone executables or they can run from source code.

Buildapp is my tool of choice for creating executables. I posted before on how use it.

Server-side software are usually run from source code. Depending on how your application startup code looks like it can be as simple as

ccl -l app.lisp


  1. SLIME - The Superior Lisp Interaction Mode for Emacs. 

  2. See the "Tools" section in the Reddit sidebar

Quicklisp newsJuly 2017 Quicklisp download stats

· 68 days ago
Here are the raw download stats for the top 100 projects in Quicklisp for July:
11470  alexandria
8732 babel
8521 closer-mop
7779 split-sequence
7534 trivial-features
7197 cffi
7170 iterate
7095 cl-ppcre
7061 bordeaux-threads
6863 trivial-gray-streams
6526 anaphora
6062 flexi-streams
5589 cl+ssl
5588 trivial-garbage
5327 trivial-backtrace
5122 let-plus
5071 nibbles
4811 cl-fad
4648 usocket
4353 puri
4124 cl-base64
4119 drakma
4107 local-time
4006 named-readtables
3949 chunga
3661 chipz
3201 ironclad
3164 esrap
3058 cl-unicode
3043 cl-interpol
3010 cl-yacc
2807 more-conditions
2789 md5
2526 utilities.print-items
2523 fiveam
2511 asdf-flv
2472 log4cl
2250 slime
2198 parse-number
2178 trivial-types
2154 trivial-indent
2152 cl-annot
2122 trivial-utf-8
2113 cl-syntax
1969 array-utils
1914 cl-json
1913 gettext
1894 symbol-munger
1882 plump
1875 arnesi
1826 collectors
1825 cl-slice
1805 access
1794 djula
1767 cl-locale
1766 cl-parser-combinators
1742 cl-utilities
1732 metabang-bind
1695 lift
1668 cl-containers
1666 asdf-system-connections
1664 optima
1662 metatilities-base
1633 quri
1631 hunchentoot
1599 simple-date-time
1567 lparallel
1566 fast-io
1562 uuid
1531 cl-clon
1461 bt-semaphore
1438 trivial-mimes
1437 closure-common
1421 cxml
1409 static-vectors
1406 mcclim
1327 clack
1322 cl-vectors
1281 ieee-floats
1220 salza2
1197 fast-http
1165 clx
1160 fare-utils
1116 fare-quasiquote
1114 lack
1105 architecture.hooks
1087 prove
1087 cl-colors
1057 uffi
1040 cl-ansi-text
997 inferior-shell
997 fare-mop
991 postmodern
979 rfc2388
978 proc-parse
961 quicklisp-slime-helper
942 pythonic-string-reader
940 xsubseq
940 plexippus-xpath
934 cl-jpeg

Timofei ShatrovYour personal DIY image search

· 80 days ago

Hi everyone, it's been a while! I bet you forgot this blog even existed. I happen to be a big supporter of quality over quantity, so while my work on parsing Japanese counters earlier this year was pretty interesting, I already wrote way too many articles about Ichiran/ so I decided to keep it to myself. Recently I've been working on a little side-project and now that it finally works, I think it deserves a full-fledged blog post.

For a bit of a nostalgia trip, let’s go back to the early 00s. Remember when TinEye first appeared? It was amazing. For the first time you could easily find where that one image you once saved from some random phpBB forum is really from. It didn’t matter if your image was resized, or slightly edited from the original, it still worked. That shit was magic, my friends. Of course these days nobody is impressed by this stuff. Google Image Search indexes pretty much anything that exists on the Internet and even uses neural networks to identify content of an image.

Back to the present day. I discovered I have an image hoarding problem. Over the years of using the Intertubes, I have accumulated a massive number of images on my hard drive. When I see an image I like my first thought is “do I have this one saved already?” because how could I possibly remember? At this point I need my own personal Google Image Search. And (spoiler alert) now I have one.

First of all, I needed an actual image matching technology. These days the cloud is all the rage, so I definitely wanted to have this thing running in the cloud (as opposed to my local PC) so that I could search my images from anywhere in the world. After a cursory search, my eyes fell on a thing called Pavlov Match which runs from a Docker container, so should be pretty easy to install. I installed docker and docker-compose on my VPS, and then git-cloned Match and ran make dev according to instructions. This will actually run an Elasticsearch instance on the same VPS, and apparently the damn thing eats memory for breakfast, at least with the default settings. I’m using a cheap 2GB RAM Linode, so the memory is actually a very finite resource here, as I will find out later. The default settings will also completely expose your match installation AND elasticsearch to the world. But don’t worry, I figured this out so that you don’t have to. Let’s edit docker-compose.yml from match repository as follows:

version: '2'
    image: pavlov/match:latest
    command: ["/", "-t", "60", "elasticsearch:9200", "--", "gunicorn", "-b", "", "-w", "4", "--preload", "server:app"]
    - elasticsearch
    image: elasticsearch
      - "ES_JAVA_OPTS=-Xms256m -Xmx256m"
      - bootstrap.mlockall=true
    - "9200"

This will make match server only available on local network within the VPS on port 8888, and elasticsearch only available to these two docker containers. It will also restrict elasticsearch RAM consumption to 512mb and --preload flag reduces the amount of memory gunicorn workers consume.

To make match server available from outside I recommend proxying it through nginx or some other proper web server. You can also add authentication/IP whitelist in nginx because the match server has no authentication features whatsoever, so anyone will be able to search/add/delete the data on it.

That was the backend part. No programming required here! But this is a Lisp blog, so the next step is writing a Lisp client that can communicate with this server. The first step is reading the match API documentation. You might notice it’s a bit… idiosyncratic. I guess REST is out of fashion these days. Anyway, I started implementing a client using the trusty drakma, but I quickly hit a limitation: match expects all parameters to be sent encoded as form data, but drakma can only encode POST parameters as form data and not, say, DELETE parameters. Not to be foiled by a badly designed API, I tried dexador, and while dex:delete does not encode parameters as form data, dex:request is flexible enough to do so. Each response (a JSON string) is parsed using jsown.

(defun parse-request (&rest args)
  (when *auth*
    (setf args `(,@args :basic-auth ,*auth*)))
  (multiple-value-bind (content return-code)
      (handler-bind ((dex:http-request-failed #'dex:ignore-and-continue))
        (apply 'dex:request args))
      ((<= 400 return-code 499)
        ("status" "fail")
        ("error" content)
        ("code" return-code)))
      (t (let ((obj (jsown:parse content)))
           (jsown:extend-js obj ("code" return-code)))))))

(defun add-local (file &key path (metadata "{}"))
  "Add local image to Match server"
   (api-url "/add")
   :method :post
   :content `(("image" . ,(pathname file))
              ("filepath" . ,(or path file))
              ("metadata" . ,metadata))))

With this basic client in place, I can add and delete individual images, but it would be incredibly cumbersome to manage thousands of images with it. I had to write some code that would scan specified directories for images, track any changes and then add/update/delete information from Match server as needed. I already wrote something like this before, so this was pretty easy. Of course SBCL’s “sb-posix:stat doesn’t work on Unicode filenames” bug has reared its head again, but I already knew the workaround. This time I completely relied on UIOP for recursively walking directories (uiop:subdirectories and uiop:directory-files are your friends). Each image file is represented as CLOS object and saved into a hash-table which is serialized to a file using CL-STORE. The object has a status attribute which can be :new, :update, :delete, :ok and so on. Based on status, an action needs to be performed, such as uploading an image to Match server (for :new and :update).

Now, I could just send a bunch of requests one after another, but that would be a waste. Remember, we have 4 gunicorn workers running on our server! This clearly calls for a thread pool. I thought PCALL would be perfect for this, but nope. It uses sb-thread:interrupt-thread which is incredibly unsafe and the result is that you basically can’t safely make http requests from thread workers. Debugging this took way too much time. In the end, I implemented a thread pool based on lparallel promises which is kind of an overkill for such a simple use case, but at least it worked.

  (setf *cache* (update-cache))
  (let ((lparallel:*kernel* (lparallel:make-kernel threads)))
         (loop for value in (alexandria:hash-table-values *cache*)
            collect (worker value) into futures
            finally (map nil 'lparallel:force futures))
  (save-cache *cache*))

Note that you must be very careful when doing things that affect global state inside the threads. For example :delete action removes a key from the hash table *cache*. This is not guaranteed to be an atomic operation, so it’s necessary to grab a global lock when doing it.

(defvar *cache-lock* (bordeaux-threads:make-lock "match-cache-lock"))
   (bordeaux-threads:with-lock-held (*cache-lock*)
      (remhash key *cache*))

Printing messages to REPL from inside threads also requires a separate lock and (force-output), otherwise it will look like a complete mess!

(defun format-msg (str &rest args)
  (bordeaux-threads:with-lock-held (*msg-lock*)
    (apply 'format t str args)

Now that the required functionality is implemented, it’s time to test upload a bunch of stuff… and get back a bunch of errors. It took some sleuthing to discover that gunicorn workers of my Match server are routinely getting killed by “OOM killer”. Basically, the server runs out of memory and the system in desperation kills a process that it doesn’t like. Remember, I only have 2Gb of memory there!

I figured out that it’s images with very large dimensions that are the most problematic in terms of memory usage. If I were to resize these images to some reasonable size, the matching should still work pretty well. In order to execute this plan, I thought I’d use some Lisp to ImageMagick interface. There’s in fact a pure Lisp solution called OptiCL but would it really handle any image? Remind me to test that later! Anyway, back to ImageMagick. Neither lisp-magick nor lisp-magick-wand would work with the most recent ImageMagick version (seems its API has changed a bit). However the last one I tried cl-graphicsmagick, which uses a fork of ImageMagick called GraphicsMagick, has unexpectedly worked (at least on my Windows laptop. Note that you need to install Microsoft Visual C Redistributable 2008 otherwise the library wouldn’t load with CFFI) so I went with that.

Using very useful temporary files functionality of UIOP (uiop:with-temporary-file), I resize each oversized image to reasonable dimensions and save into a temporary file, which is then uploaded to Match server. I also send the file’s original and resized dimensions as metadata. Thankfully this completely eradicated the memory issue. There’s a minor problem where GraphicsMagick cannot do Unicode pathnames on Windows, so I copy the original image into a temporary file with ASCII-only name in that case.

(defun resize-image (input-path output-path
                     &key (max-width *max-dimension*) (max-height *max-dimension*)
                       (filter :%QuadraticFilter) (blur 1))
  (gm::with-magick-wand (wand)
    (handler-case (gm::%MagickReadImage wand input-path)
      ;; graphicsmagick cannot read Unicode filenames on Windows so attempt to load a copy
      (gm::magick-error ()
        (uiop:with-temporary-file (:pathname tmp :prefix "gm" :type (pathname-type input-path))
          (uiop:copy-file input-path tmp)
          (setf wand (gm::%NewMagickWand))
          (gm::%MagickReadImage wand (namestring tmp)))))
    (let ((w (gm::%MagickGetImageWidth wand))
          (h (gm::%MagickGetImageHeight wand))
          (res nil))
      (multiple-value-bind (fw fh) (gm::fit-width-height w h max-width max-height)
        (unless (and (= w fw) (= h fh))
          (gm::%MagickResizeImage wand fw fh filter blur)
          (gm::%MagickWriteImage wand output-path)
          (setf res output-path))
        (values res w h fw fh)))))

Later I tested this code on an Ubuntu machine with GraphicsMagick installed from Apt repository and SBCL crashed into ldb debugger mode straight away… Welp. The helpful folks of #lisp told me the problem is with signal handlers established by GraphicsMagick library, somehow they confuse SBCL. Based on that advice, eventually I succeeded making this work. Uninstall apt Graphicsmagick and grab the sources. Find the file called magick.c and replace the line

InitializeMagickSignalHandlers(); /* Signal handlers */


// InitializeMagickSignalHandlers(); /* Signal handlers */

(commenting it out). Then do configure --enable-shared (see readme for possible options), make and sudo make install. This will make it work when called from SBCL on Linux.

Anyways, the full code of MATCH-CLIENT can be found at my Github. It’s not installable from quicklisp for obvious reasons, in fact it’s a complete pain to install as you might’ve already guessed, but if you wanna try it, you’re welcome. The main two commands are update and match. The first is called to upload all images in your *root-dirs* to the server and then to update them if anything changes. match is used to match any image on the Internet (passed as URL string) or a local pathname (passed as pathname object) compared to the server. It returns a list of jsown objects (basically alists) that contain score (up to 100 for exact match), path (with “local tag” which can be different per device) and metadata containing original and resized dimensions.

((:OBJ ("score" . 96.00956)
  ("filepath" . "[HOME] d:/foo/bar/baz.jpg")
  ("metadata" :OBJ ("rw" . 1218) ("rh" . 2048) ("w" . 3413) ("h" . 5736))))

Anyway, this was a fun (although often frustrating) thing to build and ended up being quite useful! Thanks for reading and see you next time.

McCLIMProgress report #9

· 81 days ago

Dear Community,

McCLIM code is getting better on a weekly basis depending on developer time. We are happy to see the project moving forward.

Some highlights for this iteration:

  • Scigraph code cleanup and bug fixes,
  • Bezier curves improvements,
  • PostScript and PDF improvements,
  • CLX-fb and mcclim-renderer speed improvements and refactor,
  • various code cleanups from unused and broken constructs,
  • editorial corrections to the CLIM 2 specification sources we bundle with McCLIM

Moreover many bug fixes have been proposed and merged into the codebase.

All McCLIM bounties (both active and already solved) may be found here. Default bounty expiration date is 6 months after posting it (a bounty may be reissued after that time period).

To answer recurring requests for native Windows and OSX support, we have posted bountes for finishing the Windows backend and fixing the OSX backend. Moreover, to improve portability a bounty for closer-mop support has been posted.

Bounties solved this iteration:

  • [$100] Caps lock affects non-alphabetic keys.

Active bounties ($1700):

  • [$500] Windows Backend (new).
  • [$400] Fix Beagle backend (new).
  • [$300] Replace MOP things with closer-mop portability layer (new).
  • [$150] When flowing text in a FORMATTING-TABLE, the pane size is used instead of the column size.
  • [$150] clx: input: english layout.
  • [$100] Add PDF file generation (PDF backend).
  • [$100] Keystroke accelerators may shadow keys even if inactive.

Our current financial status is $800 for bounties and $267 recurring monthly contributions from the supporters (thanks!).

Suggestions as to which other issues should have a bounty on them are appreciated and welcome. Please note that Bountysource has a functionality "Suggest an Issue" which may be found on the bounties page. If you would like to work on an issue that is not covered by the existing bounties, feel free to suggest a new bounty.

If you have any questions, doubts or suggestions - please contact me either by email ( or on IRC (my nick is jackdaniel).

Sincerely yours,
Daniel Kochmański

Quicklisp newsJune 2017 Quicklisp download stats

· 84 days ago
Here are the raw download stats for the top 100 projects in Quicklisp for June:

 9081  alexandria
7797 closer-mop
7437 split-sequence
6863 cl-ppcre
6790 babel
6498 trivial-features
6303 iterate
6222 bordeaux-threads
6173 anaphora
6099 trivial-gray-streams
5522 trivial-garbage
5367 cffi
5056 flexi-streams
4911 nibbles
4729 let-plus
4702 usocket
4592 puri
4582 cl-base64
4286 trivial-backtrace
4181 chipz
4145 cl+ssl
4021 cl-fad
3959 chunga
3381 drakma
3292 named-readtables
3281 ironclad
3221 more-conditions
3153 esrap
3144 local-time
2928 utilities.print-items
2587 parse-number
2439 cl-yacc
2149 metabang-bind
2142 cl-unicode
2131 cl-interpol
2101 trivial-utf-8
2084 md5
2083 fiveam
2056 asdf-flv
1930 optima
1918 lparallel
1897 log4cl
1879 slime
1869 lift
1854 trivial-indent
1822 closure-common
1808 cxml
1795 array-utils
1746 plump
1743 uuid
1612 bt-semaphore
1561 trivial-types
1541 simple-date-time
1513 cl-clon
1472 cl-json
1429 cl-utilities
1392 architecture.hooks
1390 quri
1342 cl-containers
1340 metatilities-base
1330 cl-annot
1319 cl-syntax
1317 asdf-system-connections
1291 ieee-floats
1253 plexippus-xpath
1113 salza2
1079 trivial-mimes
1070 postmodern
1067 arnesi
1052 cl-slice
1050 fare-utils
1047 fast-io
1040 static-vectors
1027 fare-quasiquote
1015 symbol-munger
1009 djula
1007 collectors
1003 access
996 gettext
982 cl-parser-combinators
980 cl-locale
925 hunchentoot
904 cl-sqlite
896 inferior-shell
894 fare-mop
887 prove
885 rfc2388
868 cl-log
865 command-line-arguments
859 trivia
858 lisp-namespace
851 cl-colors
824 py-configparser
821 cl-markdown
821 cl-ansi-text
821 asdf-finalizers
820 dynamic-classes
819 cl-mssql
818 garbage-pools
805 cl-abnf

Quicklisp newsJuly 2017 Quicklisp dist update now available

· 84 days ago
New projects:
  • 3bgl-shader — CL-hosted CL-like DSL for generating GLSL — MIT
  • cl-forms — A web forms handling library — MIT
  • cl-ksuid — K-sortable unique identifiers — GPLv3
  • cl-pixman — Low-level pixel manipulation. — LLGPL
  • cl-yesql — Common Lisp library for using SQL. — MIT
  • easy-routes — Yet another routes handling utility on top of Hunchentoot — MIT
  • laap — A Common Lisp multi-threaded event loop. — MIT
  • matplotlib-cl — A 2D Plotting library for Common Lisp using Matplotlib. — MIT
  • oook — Some magic on the shoulders of CLSQL — MIT
  • overlord — Experimental build/module system. — MIT
  • semantic-spinneret — A set of Semantic UI components for use with Spinneret — MIT
  • with-setf — Macros for setting a place for the duration of a scope — Unlicense
  • xlsx — Basic reader for Excel files. — MIT
Updated projects3d-vectorsassoc-utilsceplcl+sslcl-anacl-autowrapcl-dbicl-emojicl-fluent-loggercl-fondcl-hash-utilcl-kanrencl-mixedcl-openglcl-pdfcl-railcl-random-forestcl-ssdbcl-strcl-typesettingcl-webdavclaviercloser-mopclsql-fluidcoleslawcroatoandeedsdexadordoubly-linked-listfemlispflac-parserfs-utilsgamebox-dgengamebox-ecsgamebox-frame-managergamebox-gridsgamebox-mathgenieglkitharmonyhu.dwim.web-serverhu.dwim.zlibhunchentootinfix-mathinquisitorjsonrpckenzolacklakelichat-protocollichat-serverliblichat-tcp-serverlichat-ws-serverlocal-timemaidenmcclimmitomito-authningleparseqpgloaderphysical-quantitiesplumppy-configparserqlotratifyroanrtg-mathrutilssanitized-paramsserapeumsimple-loggersketchspinneretstaplestumpwmtriviawebsocket-driverwoo.

Removed projects: gtfl, s-dot.

gtfl and s-dot are related projects. The website hosting them has disappeared, and the author has not responded to email queries. So they are not in Quicklisp any more.

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


ECL NewsLisp (ECL) and QML (Qt5) on Android?

· 95 days ago
(please note that I'm assuming a Linux/64 bit platform or VirtualBox image)

Preamble: about a month ago, I was completely void of any android experience.
This is to say: using both QML (which is easy to learn) and Common Lisp (which I assume you already know) to develop android apps is not a difficult task at all, as you'll see.

So, if you are like me just a month ago, there are no excuses not to write your own, first android app using this new "EQL5-Android" project!

We will build a small game (Sokoban), which uses Lisp for the program logic, and QML for the UI, and build an APK for the android platform.

Being the author of that very first attempt of integrating Lisp and Qt4 (see lisp-cffi-qt4), what I would like to accomplish is providing you with a ca. 3 MB download, which can be tried out instantly.

10 years ago, the (a runnable win32 binary version), was a 3 MB download, including both ECL and Qt4 (UPX compressed, but still).
10 years later, this time on android, what download size is to be expected?
We will see...

Since all the documentation needed for preparing the development environment is already covered in the "EQL5-Android" project itself, I will give only the link here:


So, I'm assuming that you already have everything installed and set up (Qt 5.7.1, Android NDK 10e, Android SDK, Java JDK, and obviously the EQL5-Android sources from gitlab), in order to build android packages (APK files).

(EQL5 itself, the desktop version, is not strictly needed to follow this example; but for developing your own apps, you will obviously need it; even here it's very helpful for testing and debugging, if something doesn't work as expected.)

If you already know the process of building EQL5 apps for the desktop, you will find that building (cross-compiling) to android is very similar, with only a few more steps involved.

Since we use an example of EQL5-Android itself, everything has already been set up. But I want to remember the steps that are not obvious, if you are not familiar with Qt and EQL:

  • you need to add all your external resources, like QML files, PNG files etc. to a Qt resource file (ending .qrc); this will integrate them (compressed) directly into the executable
  • you need to add all your Lisp files, in exact order of loading, to make.lisp (in a future version of EQL5, I will try to integrate this step with ASDF)

And that's it, basically (except the app name, which needs to be adapted to the *.qrc file name, to your *.pro file name and contents (see TARGET and RESOURCES), and to the contents of the third script (see *.json file name).

Everything else will stay the same for every project.

Now I want to call your attention on the huge advantage of using Qt for your android apps: you can first build a desktop exe, with the exact same sources, and try/debug it. If the desktop version works, the android app will generally work too (the only things that may need adaption are e.g. font sizes and similar).

So, let's get practical! In the EQL5-Android sources, switch to 'examples/sokoban/'.

Building a desktop exe would be this 3 liner:

  $ eql5 make-desktop.lisp
  $ qmake
  $ make

(To test if all resources have really been included in the sokoban_desktop executable, you need to move it to a different directory, and launch it from there.)

Here's a screenshot of our app running on the desktop:

But now let's do the cross-compile dance!

First let's copy the needed shared libraries to the 'android-build/' directory.
Just run script number 1:

  $ ./

This step needs only be done once for every new project. It will copy the cross-compiled ECL and EQL5 libs into our android build directory.

The next steps are very similar to a desktop build:

  $ ecl-android -shell make.lisp
  $ qmake-android
  $ make

Since cross-compiling requires a special "host ECL", which needs to match the target platform (that is, 32 bit, no double floats), we would be in trouble with cross-compiling EQL5 code: we certainly don't want a seperate EQL5 32 bit version, only for cross-compiling...

But there is a solution to this (see 'utils/EQL5-symbols.lisp' in sources): for cross-compiling -- which is the job of our "host ECL" -- we pretend to be the eql5 executable, by defining all packages and symbols, defining all EQL5 macros (otherwise we can't compile), and simply defining dummy-functions for all EQL5 functions, so the compiler will not complain.

So, loading 'utils/EQL5-symbols.lisp' in our host ECL will be sufficient for cross-compiling EQL5 code.

If you are interested in how the cross-compile environment is set up, please see:


(thanks to Sylvain Ageneau, who wrote the original version; this is a simplified version not depending on ASDF; the latter will be integrated in a future version)

So, the above 3 liner will build the shared library of our app, ready to be included in the android build. To copy it where the android build expects it, use script number 2:

  $ ./

The last step, which will build our APK file, is a verbose one (for eventual debugging), and a little time consuming: it will create the whole package structure, and compile the whole thing into an APK file, ready to be installed on an android device.

There is this great tool (courtesy Qt) called androiddeployqt, which automates the whole and complex process of creating an APK file, with all the needed options already set in our 3rd script:

  $ ./

Here the contents of the above script, where you can see all the selected options:

  $ ~/Qt5.7.1/5.7/android_armv7/bin/androiddeployqt \
        --input \
        --output android-build \
        --deployment ministro \
        --gradle \

If it will tell you BUILD SUCCESSFUL, then you'll find the APK file (ready for deployment) in 'android-build/build/outputs/apk/'.

The last step is copying over the APK file to your android device, and install / run it. Normally you're not allowed to do this, because it requires special developer settings (please search the web for instructions how to enable them, as they are different for every android version).

After connecting via USB and copying the APK file over to your device, just tap it from there. This will ask for installing, and then for opening the app.

Here's a screenshot of the sokoban app running on a tablet:

Above you see the splash screen, because startup will take a few seconds.

Below the game:

After seeing the result, I'd like to consider a few QML and Lisp snippets.

QML is easy to learn. You just need to declare what you want (and it will do the how behind the scenes).
Let's see this snippet for defining and placing our arrow buttons:

  // container for arrow buttons
  Item {
      id: arrows
      width: up.width * 3
      height: up.height * 3
      anchors.margins: 10
      anchors.right: parent.right
      anchors.verticalCenter: parent.verticalCenter

      Ext.Button {
          id: up
          objectName: "up"
          source: "img/up.png"
          anchors.horizontalCenter: parent.horizontalCenter

      Ext.Button {
          objectName: "left"
          source: "img/left.png"
          anchors.verticalCenter: parent.verticalCenter

      Ext.Button {
          objectName: "right"
          source: "img/right.png"
          anchors.verticalCenter: parent.verticalCenter
          anchors.right: parent.right

      Ext.Button {
          objectName: "down"
          source: "img/down.png"
          anchors.horizontalCenter: parent.horizontalCenter
          anchors.bottom: parent.bottom

So, we define an Item as container for the buttons, giving it the width (up.width * 3) and height (up.height * 3), according to the button sizes: this may be any calculation or function call, and may refer to any item of the file, referred to by its id.

For placing the container itself, and the single arrow buttons, we just need to define anchors, which can be relative to other items (here: the parent item).

The Ext.Button is a user defined item class, which can be found in 'qml/ext/Button.qml. That is, the whole directory 'ext/' is imported as Ext:

  import "ext/" as Ext

This means that every file in 'ext/' is now a new QML class, which can be referred to via Ext (like a namespace).

The definition of our image button class (see 'qml/ext/Button.qml') is:

  import QtQuick 2.0

  Image {
      signal pressed()

      MouseArea {
          anchors.fill: parent
          onPressed: { parent.pressed() }

So, we don't need a real button, but only a clickable image: adding a mouse area will allow us to capture mouse events; this event is then passed to the parent (that is, the Image class), where a Qt signal will be emitted: this will allow us to connect to it from Lisp:

  (defun connect ()
    (macrolet ((pressed (item function)
                 `(qconnect (find-quick-item ,item) "pressed()"
                            (lambda () ,function))))
      (pressed "up"       (sokoban:move :north *maze*))
      (pressed "down"     (sokoban:move :south *maze*))
      (pressed "left"     (sokoban:move :west *maze*))
      (pressed "right"    (sokoban:move :east *maze*))
      (pressed "previous" (change-level :previous))
      (pressed "next"     (change-level :next))
      (pressed "undo"     (undo))
      (pressed "restart"  (reset-maze))
      (pressed "solve"    (solve))))

If you already played the game finishing a level, you will have noticed that there are 2 animations (rotation of the player, wiggling of all boxes) which run queued.
This is a little tricky to do, but with the help of a Lisp macro, we only need these lines in Lisp (being queued a macro):

  (defun final-animation ()
    (queued (qml-set "rotate_player" "running" t)
            (qml-set-all "wiggle_box" "running" t)))

Please see the sources for all the details. And this would not be possible without a Lisp function called from QML for notifying us whenever an animation state changes, see 'qml/ext/RotationAnimation.qml':

  import QtQuick 2.0
  import EQL5 1.0

  RotationAnimation {
      onRunningChanged:"qsoko:animation-change", running)

What I left out to explain is the dynamic (at run time) creation of QML items (see 'qml/items/*' and 'lisp/sokoban.lisp'); let's just say that this is left as an exercise to the reader, as all sources will patiently stay there to be read...

Well. But I still didn't answer the initial question: how big of a download is to be expected, 10 years later?

Since our APK file uses the ministro service for automatically installing the needed Qt libraries at the first launch of the app, it will only need to include both the ECL and EQL5 libraries (you can therefore use different ECL and EQL5 versions for every app you deploy).

So, to finally answer the question: our download will be ca. 3.5 MB (instead of 3 MB, 10 years ago, although we obviously compare apples and oranges here).

Seems acceptable.

And since I promised you to test it instantly (if you own a device with ARM processor), here you are:






Quicklisp newsJune 2017 Quicklisp dist update now available

· 108 days ago
New projects:
  • cepl.spaces — Adds abstractions over vector spaces to CEPL — BSD 2 Clause
  • cl-cpus — Get number of CPUs — ISC
  • cl-diskspace — List disks, get disk total/free/usable space information. — ISC
  • cl-fixtures — A simple library to create and use parameterized fixtures — MIT
  • cl-fluent-logger — A structured logger for Fluentd — BSD 3-Clause
  • cl-mixed — Bindings to libmixed, a sound mixing and processing library. — Artistic
  • cl-rail — Unspecified — Unspecified
  • cl-random-forest — Random Forest and Global Refinement for Common Lisp — MIT Licence
  • cl-soloud — Bindings to SoLoud, a multi-platform, multi-backend, minimal dependencies sound mixing and output library — Artistic
  • cl-ssdb — SSDB client for Common Lisp. — MIT
  • cl-threadpool — Implementation of a thread pool — MIT
  • deploy — Tools to aid in the deployment of a fully standalone application. — Artistic
  • doplus — DO+ (doplus) is a high-level, extensible iteration construct for Common Lisp with a reasonably simple implementation, which in particular does not use a code walker. — GPLv3
  • flow — A flowchart and generalised graph library. — Artistic
  • gtk-tagged-streams — Text I/O using streams for GTK text buffers, including tags for styling. — BSD Simplified (2-clause)
  • harmony — A common lisp sound server and sound processing library. — Artistic
  • hu.dwim.zlib — Common Lisp FFI wrapper for zlib, aka — BSD or Bugroff
  • modest-config — A modest config file loader library — MIT
  • nineveh — A library of common gpu functions — BSD 2 Clause
  • papyrus — A Literate Programming Tool — MIT
  • parseq — A parser for sequences such as strings, lists, vectors as well as trees. — GPLv2
  • physical-quantities — Use lisp numbers for physical quantities with unit and error. — GPLv2
  • roan — A library to support change ringing applications, including methods library support — MIT
  • sanitized-params — Sanitizer for parameters — BSD 2-Clause
  • sdl2-game-controller-db — Lets you easily load the lovely sdl2 gamecontroller db into cl-sdl2 — BSD 3 Clause
  • trivial-battery — Getting the battery information — BSD 2-Clause
  • trivial-swank — swank server communications — BSD simplified
  • trivial-wish — Create 'wishes' which are requests to compute something later — BSD 2-clause
Updated projects3d-matrices3d-vectorsarchitecture.builder-protocolarchitecture.service-providerayah-captchacavemancaveman2-widgets-bootstrapceplcepl.cameracepl.devilcepl.sdl2cepl.sdl2-imagecepl.sdl2-ttfcepl.skittercfficl+sslcl-anacl-ansi-termcl-bloomcl-dbicl-emojicl-fondcl-gamepadcl-gistscl-glfw3cl-graphcl-hamlcl-hash-utilcl-jpegcl-monitorscl-mssqlcl-ntp-clientcl-ohmcl-openglcl-out123cl-plplotcl-readlinecl-scsucl-soilcl-strcl-twitterclackclim-widgetscloser-mopclsql-fluidclssclxcroatoancurry-compose-reader-macrosdeedsdendritedirtdocumentation-utilsdoubly-linked-listdrakmaeasingeruditeesrapf2clfare-scriptsfast-httpfast-iofemlispfs-utilsfxmlgamebox-dgengamebox-ecsgamebox-frame-managergamebox-gridsgamebox-mathgettextglawglkitglopglsl-specglsl-toolkithornerhttp-get-cachehu.dwim.asdfhu.dwim.utilhu.dwim.web-serverinquisitoriolibjsonrpcjwacsl-systemlichat-protocollivesupportlog4clmacrodynamicsmaidenmcclimmedia-typesmetatilitiesmitomk-string-metricsopticlparachutepng-readprbsqlotqmyndqtoolsrtg-mathrutilsscalplscriptlsdl2kitserapeumsimple-loggersketchskittersmackjackspinneretstaplestructy-defclassstumpwmthe-cost-of-nothingtmtranslate-clienttrivial-main-threadtrivial-mmaptrivial-shelltrivial-updateuffiumlispunix-optsvarjoweblockswebsocket-driverwhofieldswith-cached-reader-conditionalswooyaclml.

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

Paul KhuongChubanov's Projection Methods for 0/1 Programming

· 122 days ago

I’ve long felt that compilers (and symbolic processing in general) would benefit from embedding integer programming solvers. However, I was never comfortable with actually doing so for a production system that others would have to run: industrial strength integer linear programming solvers are large systems with complex runtime behaviour, and that’s not the kind of black box you want to impose on people who just want to build their project. (That’s also true of SAT solvers, though, so maybe embedding complicated black boxes is the new normal?)

However, if we had something simple enough to implement natively in the compiler, we could hope for the maintainers to understand what the ILP solver is doing. This seems realistic to me mostly because the generic complexity tends to lie in the continuous optimisation part. Branching, bound propagation, etc. is basic, sometimes domain specific, combinatorial logic; cut generation is probably the most prominent exception, and even that tends to be fairly combinatorial. (Maybe that’s why we seem to be growing comfortable with SAT solvers: no scary analysis.) So, for the past couple years, I’ve been looking for simple enough specialised solvers I could use in branch-and-bound for large 0/1 ILP.

Some stuff with augmented lagrangians and specialised methods for box-constrained QP almost panned out, but nested optimisation sucks when the inner solver is approximate: you never know if you should be more precise in the lower level or if you should aim for more outer iterations.

A subroutine in Chubanov’s polynomial-time linear programming algorithm [PDF] (related journal version) seems promising, especially since it doesn’t suffer from the numerical issues inherent to log barriers.

Chubanov’s subroutine in branch-and-bound

Chubanov’s “Basic Subroutine” accepts a problem of the form \(Ax = 0\), \(x > 0\), and either:

  1. returns a solution;
  2. returns a non-empty subset of variables that must be 0 in any feasible solution;
  3. returns a non-empty subset of variables \(x\sb{i}\) that always satisfy \(x\sb{i} \leq u\) in feasible solutions with \(x\sp{\star} \in [0, 1]\), for some constant \(u < 1\) (Chubanov sets \(u = \frac{1}{2}\)).

The class of homogeneous problems seems useless (never mind the nondeterministic return value), but we can convert “regular” 0/1 problems to that form with a bit of algebra.

Let’s start with \(Ax = b\), \(0 \leq x \leq 1\), we can reformulate that in the homogeneous form:

\[Ax - by = 0,\] \[x + s - \mathbf{1}y = 0,\] \[x, s, y \geq 0.\]

Any solution to the original problem in \([0, 1]\) may be translated to the homogeneous form (let \(y = 1\) and \(s = 1 - x\)). Crucially, any 0/1 (binary) solution to the original problem is still 0/1 in the homogeneous form. In the other direction, any solution with \(y > 0\) may be converted to the box-constrained problem by dividing everything by \(y\).

If we try to solve the homogenous form with Chubanov’s subroutine, we may get:

  1. a strictly positive (for all elements) solution. In that case, \(y > 0\) and we can recover a solution to the box-constrained problem.
  2. a subset of variables that must be 0 in any feasible solution. If that subset includes \(y\), the box-constrained problem is infeasible. Otherwise, we can take out the variables and try again.
  3. a subset of variables that are always strictly less than 1 in feasible solutions. We exploit the fact that we only really care about 0/1 solutions (to the original problem or to the homogenous reformulation) to also fix these variables to 0; if the subset includes \(y\), the 0/1 problem is infeasible.

As soon as we invoke the third case to recursively solve a smaller problem, we end up solving an interesting ill-specified relaxation of the initial 0/1 linear program: it’s still a valid relaxation of the binary problem, but is stricter than the usual box linear relaxation.

That’s more than enough to drive a branch-and-bound process. In practice, branch-and-bound is much more about proving the (near-) optimality of an existing solution than coming up with strong feasible solutions. That’s why the fact that the subroutine “only” solves feasibility isn’t a blocker. We only need to prove the absence of 0/1 solutions (much) better than the incumbent solution, and that’s a constraint on the objective value. If we get such a proof, we can prune away that whole search subtree; if we don’t, the subroutine might have fixed some variables 0 or 1 (always useful), and we definitely have a fractional solution. That solution to the relaxation could be useful for primal heuristics, and will definitely be used for branching (solving the natural LP relaxation of constraint satisfaction problems ends up performing basic propagation for us, so we get some domain propagation for free by only branching on variables with fractional values).

At the root, if we don’t have any primal solution yet, we should probably run some binary search on the objective value at the root node and feed the resulting fractional solutions to rounding heuristics. However, we can’t use the variables fixed by the subroutine: until we have a feasible binary solution with objective value \(Z\sp{\star}\), we can’t assume that we’re only interested in binary solutions with object value \(Z < Z\sp{\star}\), so the subroutine might fix some variables simply because there is no 0/1 solution that satisfy \(Z < k\) (case 3 is vacuously valid if there is no 0/1 solution to the homogeneous problem).

That suffices to convince me of correctness. I still have to understand Chubanov’s “Basic Subroutine.”

Understanding the basic subroutine

This note by Cornelis/Kees Roos helped me understand what makes the subroutine tick.

The basic procedure updates a dual vector \(y\) (not the same \(y\) as the one I had in the reformulation... sorry) such that \(y \geq 0\) and \(|y|_1 = 1\), and constantly derives from the dual vector a tentative solution \(z = P\sb{A}y\), where \(P\sb{A}\) projects (orthogonally) in the null space of the homogeneous constraint matrix \(A\) (the tentative solution is \(x\) in Chubanov’s paper).

At any time, if \(z > 0\), we have a solution to the homogenous system.

If \(z = P\sb{A}y = 0\), we can exploit the fact that, for any feasible solution \(x\), \(x = P\sb{A}x\): any feasible solution is alrady in the null space of \(A\). We have

\[x\sp{\top}y = x\sp{\top}P\sb{A}y = x\sp{\top}\mathbf{0} = 0\]

(the projection matrix is symmetric). The solution \(x\) is strictly positive and \(y\) is non-negative, so this must mean that, for every component of \(y\sb{k} > 0\), \(x\sb{k} = 0\). There is at least one such component since \(|y|_1 = 1\).

The last condition is how we bound the number of iterations. For any feasible solution \(x\) and any component \(j\),

\[y\sb{j}x\sb{j} \leq y\sp{\top}x = y\sp{\top}P\sb{A}x \leq |x| |P\sb{A}y| \leq \sqrt{n} |z|.\]

Let’s say the max element of \(y\), \(y\sb{j} \geq 2 \sqrt{n}|z|\). In that case, we have \[x\sb{j} \leq \frac{\sqrt{n}|z|}{y\sb{j}} \leq \frac{1}{2}.\]

Chubanov uses this criterion, along with a potential argument on \(|z|\), to bound the number of iterations. However, we can apply the result at any iteration where we find that \(x\sp{\top}z < y\sb{j}\): any such \(x\sb{j} = 0\) in binary solutions. In general, we may upper bound the left-hand side with \(x\sp{\top}z \leq |x||z| \leq \sqrt{n}|z|\), but we can always exploit the structure of the problem to have a tighter bound (e.g., by encoding clique constraints \(x\sb{1} + x\sb{2} + … = 1\) directly in the homogeneous reformulation).

The rest is mostly applying lines 9-12 of the basic procedure in Kees’s note. Find the set \(K\) of all indices such that \(\forall k\in K,\ z\sb{k} \leq 0\) (Kees’s criterion is more relaxed, but that’s what he uses in experiments), project the vector \(\frac{1}{|K|} \sum\sb{k\in K}e\sb{k}\) in the null space of \(A\) to obtain \(p\sb{K}\), and update \(y\) and \(z\).

The potential argument here is that after updating \(z\), \(\frac{1}{|z|\sp{2}}\) has increased by at least \(|K| > 1\). We also know that \(\max y \geq \frac{1}{n}\), so we can fix a variable to 0 as soon as \(\sqrt{n} |z| < \frac{1}{n}\), or, equivalently, \(\frac{1}{|z|} > n\sp{3/2}\). We need to increment \(\frac{1}{|z|\sp{2}}\) to at most \(n\sp{3}\), so we will go through at most \(1 + n\sp{3})\) iterations of the basic procedure before it terminates; if the set \(K\) includes more than one coordinate, we should need fewer iterations to reach the same limit.

Chubanov shows how to embed the basic procedure in a basic iterative method to solve binary LPs. The interesting bit is that we reuse the dual vector \(y\) as much as we can in order to bound the total number of iterations in the basic procedure. We fix at least one variable to \(0\) after a call to the basic procedure that does not yield a fractional solution; there are thus at most \(n\) such calls.

Next step

In contrast to regular numerical algorithms, the number of iterations and calls so far have all had exact (non asymptotic) bounds. The asymptotics hide in the projection step, where we average elementary unit vectors and project them in the null space of \(A\). We know there will be few (at most \(n\)) calls to the basic procedure, so we can expend a lot of time on matrix factorisation. In fact, Chubanov outright computes the projection matrix in \(\mathcal{O}(n\sp{3})\) time to get his complexity bound of \(\mathcal{O}(n\sp{4})\). In practice, this approach is likely to fill a lot of zeros in, and thus run out of RAM.

I’d start with the sparse projection code in SuiteSparse. The direct sparse solver spends less time on precomputation than fully building the projection matrix (good if we don’t expect to always hit the worst case iteration bound), and should preserve sparsity (good for memory usage). In return, computing projections is slower, which brings the worst-case complexity to something like \(\mathcal{O}(n\sp{5})\), but that can be parallelised, should be more proportional to the number of non-zeros in the constraint matrix (\(\mathcal{O}(n)\) in practice), and may even exploit sparsity in the right-hand side. Moreover, we can hope that the \(n\sp{3}\) iteration bound is pessimistic; that certainly seems to be the case for most experiments with random matrices.

The worst-case complexity, between \(\mathcal{O}(n\sp{4})\) and \(\mathcal{O}(n\sp{5})\), doesn’t compare that well to interior point methods (\(\mathcal{O}(\sqrt{n})\) sparse linear solutions). However, that’s all worst-case (even for IPMs). We also have different goals when embedding linear programming solvers in branch-and-bound methods. Warm starts and the ability to find solution close to their bounds are key to efficient branch-and-bound; that’s why we still use simplex methods in such methods. Chubanov’s projection routine seems like it might come close to the simplex’s good fit in branch-and-bound, while improving efficiency and parallelisability on large LPs.

McCLIMProgress report #8

· 128 days ago

Dear Community,

During this iteration we had many valuable contributions. It's a joy to see how McCLIM gains more mindshare and people are willing to put their time and wallet in fixing issues and writing applications in McCLIM.

Some highlights for this iteration:

  • many Listener fixes,
  • major tab layout extension refactor,
  • new extension for Bezier curves (based on older internal implementation),
  • interactor improvements,
  • layout improvements,
  • fixes for redisplay and transformations,
  • documentation cleanups,
  • cleanup of the issues (closed the obsolete and fixed ones).

Bezier Curves

All McCLIM bounties (both active and already solved) may be found here.

Bounties solved this iteration:

  • [$200] Interactor CLI prompt print problem

Fixed by Gabriel Laddel. Waiting for a pull request and a bounty claim.

  • [$200] Problem with coordinate swizzling (probably).

Fixed by Alessandro Serra and merged. Waiting for a bounty claim.

  • [$100] menu for input-prompt in lisp-listener does not disappear after use.

Fixed by Alessandro Serra and merged. Waiting for a bounty claim.

Active bounties:

  • [$150] When flowing text in a FORMATTING-TABLE, the pane size is used instead of the column size.

  • [$150] clx: input: english layout. (someone already works on it).

  • [$100] Caps lock affects non-alphabetic keys. (new)

  • [$100] Add PDF file generation (PDF backend). (new)

  • [$100] Keystroke accelerators may shadow keys even if inactive. (new)

Our current financial status is $1,429 for bounties and $267 recurring monthly contributions from the supporters (thanks!).

Suggestions as to which other issues should have a bounty on them are appreciated and welcome. Please note that Bountysource has a functionality "Suggest an Issue" which may be found on the bounties page. If you feel that you may solve some problem, but there is no bounty on it, feel free to suggest it too.

If you have any questions, doubts or suggestions - please contact me either by email ( or on IRC (my nick is jackdaniel).

Sincerely yours,
Daniel Kochmański

ABCL DevABCL 1.5.0

· 128 days ago
We are pleased to announce that we have released the Sixth Edition of the Armed Bear Common Lisp implementation as ABCL 1.5.0.

Due to the lack of a publicly available Java 5 implementation, with this release we drop support for that platform, and henceforth support running on Java 6, Java 7, and Java 8. 

In addition to consolidating eight months of bug fixes, the following notable features are now also present in the implementation.

The compiler now records more complete debugging information on the SYS:SOURCE symbol property.

ABCL-INTROSPECT offers improved inspection of backtraces to the point that local variables may be inspected in Lisp debug frames.  Patches to SLIME to use this feature are in the process of being merged into the upstream repository. The OBJECTWEB system allows the user to disassemble JVM bytecode via dependencies managed by Maven.

JSS now contains a syntax for accessing Java static and member fields.

For declaring dependencies on Java artifacts ABCL-ASDF,  we have added an experimental syntax to address JRE/JDK artifacts via the ASDF:JDK-JAR class, as well as the ability to more finely control Maven dependencies with the  ASDF:MVN-MODULE class.

A complete list of changes may be viewed in the source repository.

Binaries for this release may either be downloaded directly from from the distributed Maven POM graph, or run from Docker via
    docker run -it easye/abcl:1.5.0
Many thanks to all who have contributed to nurturing the Bear's execution of conforming ANSI Common Lisp on the Java Virtual Machine.

Nicolas HafnerTrial "Study Session" Next Saturday, 17th of June

· 129 days ago

Next Saturday, the 17th of June, there is going to be a live "study session" about Shirakumo's game engine Trial. The intention of this event is to get people acquainted with the internal structure and features of Trial, so that they may work on it by themselves, and thus help improve it in the future.

The study session is going to be held on my regular stream from 10:00-16:00 UTC. That's 12:00-18:00 CEST, 6:00-12:00 EST, 19:00-3:00 JST. We might stop earlier if people run out of steam or there isn't as much to cover as I anticipated.

Participants that want to actively ask questions and follow along are encouraged to download and set up Mumble for voice communication, and to download the source code of Trial and its dependencies ahead of time, so that they may follow along on their own screens, rather than being subject to the stream delay.

You are expected to have a decent understanding of Common Lisp, as I won't have time to teach you that. While an understanding of modern OpenGL is advantageous, it won't be required. I'll try to explain OpenGL as much as possible or necessary as we go along. Likely there will be another stream at a later point, where modern OpenGL is explained from the ground up.

Hope to see you there!

LispjobsLisp programmer,, Lviv, Ukraine

· 130 days ago

(See also: is expanding and we are looking for candidates to join our strong cloud software development team.

We use Lisp systems to implement business logic operations such as resource accounting, data mining, billing, automated operations (AI), full system test suites and more. We wish to extend our team with another skilled colleague, to work with us in this area.

We expect a strong technical mind coupled with a visionary outlook and ability to work closely together with the entire team, from architecture through development, QA and ultimately production.

Keepit can offer a passionate working environment with bright minded colleagues bringing out the next generations of data consolidation, data security and data sharing solutions coupled with the ability to bring-out real value of the data of our customers.

Required skills:

Good understanding of Common Lisp;

Good algorithmic knowledge

Will be a plus:

Good understanding of HTTP, REST and XML;

Shell scripting and ability to read/write Makefiles;

Experience with Emacs, slime/swank and SBCL;

Some knowledge of C++

Desired communication skills:

Team player, but with high degree of ability to work independently;

Upper-intermediary level of English for daily written and video calls communication;

Person who is gladly willing to share knowledge within the team;

Willingness to take initiative and suggest alternative ways of solving problems;

Quick learner, self starter.

Contact information:

e-mail:, Skype: maryna.hnatyk

ABCL DevABCL 1.5.0-rc-0 draft of upcoming User Manual

· 132 days ago
An unsigned ABCL 1.5.0-rc-0 release now available to test the distributions mechanisms for the upcoming ABCL-1.5.0 release.

Draft of upcoming User Manual to which corrections are solicited.

Paul KhuongRelaxed Revocable Locks: Mutual Exclusion Modulo Preemption

· 135 days ago

Update: there’s a way to detect “running” status even across cores. It’s not pretty. Search for /proc/sched_debug.

The hard part about locking tends not to be the locking itself, but preemption. For example, if you structure a memory allocator like jemalloc, you want as few arenas as possible; one per CPU would be ideal, while one per thread would affect fragmentation and make some operations scale linearly with the number of threads. However, you don’t want to get stuck when a thread is preempted while it owns an arena. The usual fix is two-pronged:

  1. have a few arenas per CPU (e.g., jemalloc defaults to 4x the number of CPUs);
  2. hold exclusive ownership for short critical sections.

The first tweak isn’t that bad; scaling the number of arenas, stats regions, etc. with the number of CPUs is better than scaling with the number of threads. The second one really hurts performance: each allocation must acquire a lock with an interlocked write. Even if the arena is (mostly) CPU-local, the atomic wrecks your pipeline.

It would be nice to have locks that a thread can acquire once per scheduling quantum, and benefit from ownership until the thread is scheduled out. We could then have a few arenas per CPU (if only to handle migration), but amortise lock acquisition over the timeslice.

That’s not a new idea. Dice and Garthwaite described this exact application in 2002 (PDF) and refer to older work for uniprocessors. However, I think the best exposition of the idea is Harris and Fraser’s Revocable locks for non-blocking programming, published in 2005 (PDF). Harris and Fraser want revocable locks for non-blocking multiwriter code; our problem is easier, but only marginally so. Although the history of revocable locks is pretty Solaris-centric, Linux is catching up. Google, Facebook, and EfficiOS (LTTng) have been pushing for restartable sequences, which is essentially OS support for sections that are revoked on context switches. Facebook even has a pure userspace implementation with Rseq; they report good results for jemalloc.

Facebook’s Rseq implements almost exactly what I described above, for the exact same reason (speeding up a memory allocator or replacing miscellaneous per-thread structs with ~per-CPU data). However, they’re trying to port a kernel idiom directly to userspace: restartable sequences implement strict per-CPU data. With kernel supports, that makes sense. Without such support though, strict per-CPU data incurs a lot of extra complexity when a thread migrates to a new CPU: Rseq needs an asymmetric fence to ensure that the evicted thread observes its eviction and publishes any write it performed before being evicted.

I’m not sure that’s the best fit for userspace. We can avoid a lot of complexity by instead dynamically allocating a few arenas (exclusive data) per CPU and assuming only a few threads at a time will be migrated while owning arenas.

Here’s the relaxed revocable locks interface I propose:

  1. Each thread has a thread state struct. That state struct has:

    • a generation counter;
    • a canceled counter (generation - 1 or equal to generation);
    • a signaled counter (generation - 1 or equal to generation);
    • an acknowledged cancel counter (generation - 1 or equal to generation);
    • an “in critical section” flag (pointer to a revocable lock).
  2. Locks are owned by a pair of thread state struct and generation counter (ideally packed in one word, but two words are doable). Threads acquire locks with normal compare-and-swap, but may bulk revoke every lock they own by advancing their generation counter.

  3. Threads may execute any number of conditional stores per lock acquisition. Lock acquisition returns an ownership descriptor (pair of thread state struct and generation counter), and rlock_store_64(descriptor, lock, dst, value) stores value in dst if the descriptor still owns the lock and the ownership has not been cancelled.

  4. Threads do not have to release lock ownership to let others make progress: any thread may attempt to cancel another thread’s ownership of a lock. After rlock_owner_cancel(descriptor, lock) returns successfully, the victim will not execute a conditional store under the notion that it still owns lock with descriptor.

The only difference from Rseq is that rlock_owner_cancel may fail. In practice, it will only fail if a thread on CPU A attempts to cancel ownership for a thread that’s currently running on another CPU B. That could happen after migration, but also when an administrative task iterates through every (pseudo-)per-CPU struct without changing its CPU mask. Being able to iterate through all available pseudo-per-CPU data without migrating to the CPU is big win for slow paths; another advantage of not assuming strict per-CPU affinity.

Rather than failing on migration, Rseq issues an asymmetric fence to ensure both its writes and the victim’s writes are visible. At best, that’s implemented with inter-processor interrupts (IPIs) that scale linearly with the number of CPUs... for a point-to-point signal. I oversubscribed a server with 2-4x more threads than CPUs, and thread migrations happened at a constant frequency per CPU. Incurring O(#CPU) IPIs for every migration makes the per-CPU overhead of Rseq linear with the number of CPUs (cores) in the system. I’m also wary of the high rate of code self/cross -modification in Rseq: mprotect incurs IPIs when downgrading permissions, so Rseq must leave some code page with writes enabled. These downsides (potential for IPI storm and lack of W^X) aren’t unique to Rseq. I think they’re inherent to emulating unpreempted per-CPU data in userspace without explicit OS support.

When rlock_owner_cancel fails, I expect callers to iterate down the list of pseudo-per-CPU structs associated with the CPU and eventually append a new struct to that list. In theory, we could end up with as many structs in that list as the peak number of thread on that CPU; in practice, it should be a small constant since rlock_owner_cancel only fails after thread migration.

Code for Rlock (Linux/x86-64 only)

I dumped my code as a gist, but it is definitely hard to follow, so I’ll try to explain it here.

Bitpacked ownership records must include the address of the owner struct and a sequence counter. Ideally, we’d preallocate some address space and only need 20-30 bits to encode the address. For now, I’m sticking to 64 byte aligned allocations and rely on x86-64’s 48 bits of address space. With 64 bit owner/sequence records, an rlock is a 64 bit spinlock.

typedef union rlock_owner_seq {
        uint64_t bits;
        struct {
                uint64_t sequence:22;
                uint64_t address:42;
} rlock_owner_seq_t;

struct rlock {
        rlock_owner_seq_t owner;

In the easy case, acquiring an rlock means:

  1. reading the owner field (with a 64 bit load);
  2. confirming that the owner has advanced its sequence;
  3. CASing in our own rlock_owner_seq_t.

But first, we must make canonicalise our own owner struct.

struct rlock_owner {
        /* SPMC. */
        rlock_owner_seq_t seq;
        /* MPMC: Asked to cancel up to here (inclusively). */
        uint32_t cancel_sequence;
        /* MPMC: Signaled to cancel up to here (inclusively). */
        uint32_t signal_sequence;
        /* SPMC: Acked cancel ask up to here (inclusively). */
        uint32_t acked_sequence;
        /* Private: forcibly release lock after too many ops. */
        uint32_t op_count;
        /* SPMC */
        pid_t tid;
        /* SPMC; "in critical section" flag. */
        struct rlock *critical_section;
} __attribute__((__aligned__(64)));

Rlock lazily allocates an rlock_owner per thread and stores it in TLS; we can’t free that memory without some safe memory reclamation scheme (and I’d like to use Rlock to implement SMR), but it is possible to use a type-stable freelist.

Regardless of the allocation/reuse strategy, canonicalising an rlock means making sure we observe any cancellation request.

static inline bool
update_self(struct rlock_owner *self)
        rlock_owner_seq_t snapshot = { .bits = self->seq.bits };
        uint32_t cancel_sequence = ck_pr_load_32(&self->cancel_sequence);

        /* We've been asked to cancel if cancel_sequence == seq.sequence. */
        if (LIKELY(self->seq.sequence != cancel_sequence)) {
                return false;

        ck_pr_fas_32(&self->cancel_sequence, snapshot.sequence);
        ck_pr_fas_32(&self->signal_sequence, snapshot.sequence);
        ck_pr_fas_32(&self->acked_sequence, snapshot.sequence);

        ck_pr_fas_64(&self->seq.bits, snapshot.bits);
        return true;

static inline struct rlock_owner *
        struct rlock_owner *self;

        self = rlock_self;
        if (UNLIKELY(self == NULL)) {
                self = allocate_self();

        return self;

To acquire a lock we observe the current owner, attempt to cancel its ownership, and (if we did cancel ownership) CAS in our own owner/sequence descriptor.

rlock_lock(struct rlock *lock)
        struct rlock_owner *self = get_self();
        rlock_owner_seq_t seq, snapshot;

        /* Load the current owner. */
        snapshot.bits = ck_pr_load_64(&lock->owner.bits);
        /* Easy case: we already own the lock. */
        if (snapshot.bits == self->seq.bits) {
                return self->seq;

        for (;;) {
                seq.bits = self->seq.bits;

                /* Make sure the current owner isn't anymore. */
                if (!rlock_owner_cancel(snapshot, lock)) {
                        /* Couldn't; return 0. */
                        seq.bits = 0;
                        return seq;

                /* Replace the old owner with ourself. */
                if (ck_pr_cas_64_value(&lock->owner.bits,
                    snapshot.bits, seq.bits, &snapshot.bits)) {
                        /* Success! */

                /* CAS failed.  snapshot.bits has the new owner. */
                /* Eagerly observe any cancellation. */
                /* CAS failed. Spin a bit. */

        return seq;

Most of the trickiness hides in rlock_owner_cancel.

rlock_owner_cancel(union rlock_owner_seq owner,
    struct rlock *evict)
        struct rlock_owner *victim = (void *)((uintptr_t)owner.address * 64);
        rlock_owner_seq_t snapshot;
        uint32_t acked;
        uint32_t sequence = owner.sequence;

        assert(evict != NULL);
        /* Easy case: no owner. */
        if (victim == NULL) {
                return true;

        snapshot.bits = ck_pr_load_64(&victim->seq.bits);
        if (snapshot.bits != owner.bits) {
                /* The victim has already moved on to a new sequence value. */
                return true;

        acked = ck_pr_load_32(&victim->acked_sequence);
        if (mod_lte(sequence, acked)) {
                /* We already have acked cancellation >= sequence. */
                return true;

        /* Advance the victim's cancel counter to sequence. */
        if (!ensure_cancel_sequence(victim, sequence)) {
                /* Already advanced; nothing to do! */
                return true;

        if (victim_running(victim)) {
                /* The victim isn't obviously scheduled out;

                /* See if we must ensure visibility of our cancel. */
                snapshot.bits = ck_pr_load_64(&victim->seq.bits);
                if (snapshot.bits == owner.bits) {
                        ensure_signal_sequence(victim, sequence);

                return false;

        if (ck_pr_load_ptr(&victim->critical_section) != evict) {
                 * Easy case: victim isn't in a critical section with
                 * our lock.  The victim has either been scheduled out
                 * since we called `ensure_cancel_sequence`, our went
                 * through a context switch at least once.  In either
                 * case, it has already observed the cancellation or
                 * will before the next critical section.
                return true;

         * The victim might be in the middle of a critical section.
         * Send a signal that'll skip the critical section if
         * necessary.
        ensure_signal_sequence(victim, sequence);
         * If the victim is definitely not running, it either has
         * already executed the signal handler or will before resuming
         * normal execution.  If the victim might be running,
         * we can only hope we got lucky.
        if (!victim_running(victim)) {
                return true;

         * We know the vitim was scheduled out before we signaled for
         * cancellation.  We can see if the victim has released our
         * critical section at least once since then.
        return (ck_pr_load_ptr(&victim->critical_section) != evict);

The fancy stuff begins around ensure_cancel_sequence(victim, sequence);. Our code maintains the invariant that the MPMC sequences (cancel_sequence, signal_sequence) are either the SPMC sequence - 1 (normal state), or exactly the SPMC sequence (cancellation request).

ensure_cancel_sequence CASes the cancel_sequence field from its expected value of owner.sequence - 1 to owner.sequence. If the actual value is neither of them, the owner has already advanced to a new sequence value, and we’re done.

Otherwise, we have to hope the victim isn’t running.

Now comes the really tricky stuff. Our CAS is immediately visible globally. The issue is that the victim might already be in the middle of a critical section. When writers executes a critical sections, they:

  1. Set the critical section flag (with a normal write);
  2. Check that the lock hasn’t been revoked;
  3. Perform the write;
  4. Clear the critical section flag.

It’s really hard to guarantee that the write in step 1 is visible (without killing performance in the common case), and if it is, that the victim isn’t about to execute step 3.

We get that guarantee by determining that the victim hasn’t been continuously executing since the time we attempted to CAS the cancel_sequence forward. That’s (hopefully) enough of a barrier to order the CAS, step 1, and our read of the critical section flag.

That’s not information that Linux exposes directly. However, we can borrow a trick from Rseq and read /proc/self/task/[tid]/stat. The contents of that file include whether the task is (R)unnable (or (S)leeping, waiting for (D)isk, etc.), and the CPU on which the task last executed.

If the task isn’t runnable, it definitely hasn’t been running continuously since the CAS. If the task is runnable but last ran on the CPU the current thread is itself running on (and the current thread wasn’t migrated in the middle of reading the stat file), it’s not running now.

If the task is runnable on another CPU, we can try to look at /proc/sched_debug: each CPU has a .curr->pid line that tells us the PID of the task that’s currently running (0 for none). That file has a lot of extra information so reading it is really slow, but we only need to do that after migrations.

Finally, the victim might really be running. Other proposals would fire an IPI; we instead ask the caller to allocate a few more pseudo-per-CPU structs.

Assuming we did get a barrier out of the scheduler, we hopefully observe that the victim’s critical section flag is clear. If that happens, we had:

  1. CAS the cancellation sequence;
  2. Barrier in the victim from being scheduled out;
  3. Critical section flag was empty after the CAS.

This guarantees that the victim hasn’t been in the same critical section since the CAS in step 1. Either it’s not in a critical section, or if it is, it’s a fresh one that will observe the CAS. It’s safe to assume the victim has been successfully evicted.

The less happy path happens when we observe that the victim’s critical section flag is set. We must assume that it was scheduled out in the middle of a critical section. We’ll send a (POSIX) signal to the victim: the handler will skip over the critical section if the victim is still in one. Once that signal is sent, we know that the first thing Linux will do is execute the handler when the victim resumes execution. If the victim is still not running after tgkill returned, we’re good to go: if the victim is still in the critical section, the handler will fire when it resumes execution.

Otherwise, the victim might have been scheduled in between the CAS and the signal; we still have the implicit barrier given by the context switch between CAS and signal, but we can’t rely on signal execution. We can only hope to observe that the victim has noticed the cancellation request and advanced its sequence, or that it cleared its critical section flag.

The rest is straightforward. The rlock_store_64 must observe any cancellation, ensure that it still holds the lock, and enter the critical section:

  1. set the critical section flag (overwrite with the lock’s address);
  2. check again that we still hold the lock and have not been asked to cancel;
  3. flip the result flag to “success”;
  4. store.

Once it leaves the critical section, rlock_store_64 clears the critical section flags, looks for any cancellation request, and returns success/failure. The critical section is in inline assembly for the signal handler: executing the store in step 4 implicitly marks the end of the critical section.

rlock_store_64(rlock_owner_seq_t snapshot,
    struct rlock *lock, uint64_t *dst, uint64_t value)
        struct rlock_owner *self = (void *)((uintptr_t)snapshot.address * 64);
        rlock_owner_seq_t seq;
        uint32_t op_count;
        int status;

        seq.bits = self->seq.bits;
        op_count = ++self->op_count;
        /* We cancelled this lock. */
        if (UNLIKELY(seq.bits != snapshot.bits)) {
                return false;

        /* The handler will reset RAX to 1 on skip. */
        status = 1;
        asm volatile(
            /* Move the lock's address in the critical section flag. */
            "0: movq %[lock], %[critical_section]\n\t"
            /* Do we still own the lock? */
            "cmpq %[owner], %[snapshot]\n\t"
            "jne 1f\n\t"
            /* Were we asked to cancel? */
            "cmpl %[cancelled], %[seq]\n\t"
            "je 1f\n\t"
            /* Success path! Set status to 0. */
            "xorl %[status], %[status]\n\t"
            /* Store the value in *dst. */
            "movq %[value], %[dst]\n\t"
            /* End of critical section. */

             * Make sure the signal handler knows where the
             * critical section code begins & ends.
            ".pushsection rlock_store_list, \"a\", @progbits\n\t"
            ".quad 0b, 1b\n\t"
                : [status] "+a"(status),
                  [critical_section] "+m"(self->critical_section),
                  [dst] "=m"(*dst)
                : [lock] "r"(lock),
                  [snapshot] "r"(snapshot.bits),
                  [owner] "m"(lock->owner.bits),
                  [seq] "r"((uint32_t)seq.sequence),
                  [cancelled] "m"(self->cancel_sequence),
                  [value] "r"(value)
                : "memory", "cc");

        /* Clear the flag. */
        ck_pr_store_ptr(&self->critical_section, NULL);

        /* Acknowledge any cancellation request. */
        if (UNLIKELY(status != 0)) {
                return false;

        /* Force lock reacquisition after a couple thousand writes. */
        if (UNLIKELY(op_count >= OP_LIMIT)) {
                self->op_count = 0;

        return true;

Finally, the signal handler for rlock cancellation requests iterates through the rlock_store_list section until it finds a record that strictly includes the instruction pointer. If there is such a record, the thread is in a critical section, and we can skip it by overwriting RIP (to the end of the critical section) and setting RAX to 1.

rlock_signal_handler(int signal, siginfo_t *info, void *arg)
        ucontext_t *ctx = arg;
        mcontext_t *mctx = &ctx->uc_mcontext;
        struct rlock_owner *self = rlock_self;
        uintptr_t rip;
        size_t nloc = __stop_rlock_store_list - __start_rlock_store_list;


        rip = (uintptr_t)mctx->gregs[REG_RIP];
        for (size_t i = 0; i < nloc; i++) {
                struct rlock_store record;

                record = __start_rlock_store_list[i];
                if (rip < record.begin || rip >= record.end) {

                assert(self != NULL);

                /* skip the critical instruction. */
                mctx->gregs[REG_RIP] = record.end;
                /* set the interrupted flag. */
                mctx->gregs[REG_RAX] = 1;

        /* Might as well publish that we observed any cancellation request. */
        if (self != NULL) {


Silly benchmarks

On my 2.9 GHz Sandy Bridge, a baseline loop to increment a counter a billion times takes 6.9 cycles per increment, which makes sense given that I use inline assembly loads and stores to prevent any compiler cleverness.

The same loop with an interlocked store (xchg) takes 36 cycles per increment.

Interestingly, an xchg-based spinlock around normal increments only takes 31.7 cycles per increment (0.44 IPC). If we wish to back our spinlocks with futexes, we must unlock with an interlocked write; releasing the lock with a compare-and-swap brings us to 53.6 cycles per increment (0.30 IPC)! Atomics really mess with pipelining: unless they’re separated by dozens or even hundreds of instructions, their barrier semantics (that we usually need) practically forces an in-order, barely pipelined, execution.

FWIW, 50ish cycles per transaction is close to what I see in microbenchmarks for Intel’s RTM/HLE. So, while the overhead of TSX is non-negligible for very short critical sections, it seems more than reasonable for adaptive locks (and TSX definitely helps when preemption happens, as shown by Dice and Harris in Lock Holder Preemption Avoidance via Transactional Lock Elision).

Finally, the figure that really matters: when incrementing with rlock_store_64, we need 13 cycles per increment. That loop hits 2.99 IPC, so I think the bottleneck is just the number of instructions in rlock_store_64. The performance even seems independent of the number of worker threads, as long as they’re all on the same CPU.

In tabular form:

| Method               | Cycle / increment | IPC  |
| Vanilla              |             6.961 | 1.15 |
| xchg                 |            36.054 | 0.22 |
| FAS spinlock         |            31.710 | 0.44 |
| FAS-CAS lock         |            53.656 | 0.30 |
| Rlock, 1 thd         |            13.044 | 2.99 |
| Rlock, 4 thd / 1 CPU |            13.099 | 2.98 |
| Rlock, 256 / 1       |            13.952 | 2.96 |
| Rlock, 2 / 2         |            13.047 | 2.99 |

Six more cycles per write versus thread-private storage really isn’t that bad (accessing TLS in a shared library might add as much overhead)... especially compared to 25-50 cycles (in addition to indirect slowdowns from the barrier semantics) with locked instructions.

I also have a statistics-gathering mode that lets me vary the fraction of cycles spent in critical sections. On my server, the frequency of context switches between CPU-intensive threads scheduled on the same CPU increases in steps until seven or eight threads; at that point, the frequency tops out at one switch per jiffy (250 Hz). Apart from this scheduling detail, evictions act as expected (same logic as for sampled profiles). The number of evictions is almost equal to the number of context switches, which is proportional to the runtime. However, the number of hard evictions (with the victim in a critical section) is always proportional to the number of critical section executed: roughly one in five million critical section is preempted. That’s even less than the one in two million we’d expect from the ~six cycle per critical section: that kind of makes sense with out of order execution, given that the critical section should easily flow through the pipeline and slip past timer interrupts.


The main trade-off is that rlocks do not attempt to handle thread migrations: when a thread migrates to another CPU, we let it assume (temporary) exclusive ownership of its pseudo-per-CPU struct instead of issuing IPIs. That’s good for simplicity, and also – arguably – for scaling. The scaling argument is weak, given how efficient IPIs seem to be. However, IPIs feel like one of these operations for which most of the cost is indirect and hard to measure. The overhead isn’t only (or even mostly) incurred by the thread that triggers the IPIs: each CPU must stop what it’s currently doing, flush the pipeline, switch to the kernel to handle the interrupt, and resume execution. A scheme that relies on IPIs to handle events like thread migrations (rare, but happens at a non-negligible base rate) will scale badly to really large CPU counts, and, more importantly, may make it hard to identify when the IPIs hurt overall system performance.

The other important design decision is that rlocks uses signals instead of cross-modifying code. I’m not opposed to cross-modifying code, but I cringe at the idea of leaving writable and executable pages lying around just for performance. Again, we could mprotect around cross-modification, but mprotect triggers IPIs, and that’s exactly what we’re trying to avoid. Also, if we’re going to mprotect in the common case, we might as well just mmap in different machine code; that’s likely a bit faster than two mprotect and definitely safer (I would use this mmap approach for revocable multi-CPU locks à la Harris and Fraser).

The downside of using signals is that they’re more invasive than cross-modifying code. If user code expects any (async) signal, its handlers must either mask the rlock signal away and not use rlocks, or call the rlock signal handler... not transparent, but not exacting either.

Rlocks really aren’t that much code (560 LOC), and that code is fairly reasonable (no mprotect or self-modification trick, just signals). After more testing and validation, I would consider merging them in Concurrency Kit for production use.

Next step: either mmap-based strict revocable locks for non-blocking concurrent code, or a full implementation of pseudo-per-CPU data based on relaxed rlocks.

Patrick SteinFog of Light - Starting to Add Star-Fields

· 143 days ago

I have finally written my first OpenGL code using GLSL. Whew. That took way too long to get all working correctly. I promise, soon, I will upload some sample code so that others may not have to stumble as long as I did.

For the star-field, I generate a few thousand 2-D points. Each point has its own radius, its own opacity, and its own color.

I put these all into an OpenGL array buffer. Then, the vertex shader copies data out of my struct to set the color and the point size. Then, the fragment shader turns the color into two, overlapping radial gradients (one that is half the radius of the other) by modulating the color’s opacity.

screenshot of sample starfield

Next up will be nebulae, then planets/asteroids in the local system.

Zach BeaneRoger Corman talk in the Bay Area

· 143 days ago

Quicklisp newsMay 2017 Quicklisp dist update now available

· 150 days ago
New projects:
  • cepl.glop — glop host for cepl — BSD 2 Clause
  • cepl.sdl2-image — Some helper methods for using sdl2-image to load images to CEPL types — BSD 2 Clause
  • cepl.sdl2-ttf — A few additional helpers for making working with sdl2-ttf even easier from CEPL — BSD 2 Clause
  • cl-clblas — clBLAS binding — Apache License, Version 2.0
  • cl-emoji — cl-emoji provides the Unicode emoji characters — MIT
  • cl-fond — Bindings to libfond, a simple text rendering engine for OpenGL — Artistic
  • cl-hamcrest — This library makes your CL unittests more readable. — New BSD
  • cl-ntp-client — A simple NTP (Network Time Protocol) client in Common Lisp — BSD
  • cl-pcg — A bare-bones Permuted Congruential Generator implementation in pure Common Lisp. — MIT
  • cl-sdl2-mixer — Bindings for SDL2_mixer — MIT
  • cl-trie — Common Lisp implementation of Trie data structure. — MIT
  • cl-why — (X)HTML generation macros — BSD
  • doubly-linked-list — An implementation of the doubly linked list data structure. — MIT
  • flac-parser — A parser for FLAC audio files. — MIT
  • fs-utils — Utilities for working with files and file paths. — MIT
  • gamebox-dgen — A procedural dungeon generator. — MIT
  • gamebox-ecs — An implementation of the Entity-Component System (ECS) pattern, popular with game development. — MIT
  • gamebox-frame-manager — A manager for frames within a game loop. — MIT
  • gamebox-grids — Create and manipulate tiles in a two-dimensional grid layout. — MIT
  • gamebox-math — A high performance math library useful for making games. — MIT
  • genie — A simple wrapper to generate portably seedable pseudo-random numbers. — MIT
  • — A markdown parser for Common Lisp — MIT
  • narrowed-types — Type definitions narrowed with predicates — BSD
  • simple-logger — A simple message logging system. — MIT
  • simple-routes — Facility for straightforward http routing on top of Hunchentoot. — 2 clause BSD
  • stealth-mixin — Library for creating stealth mixin classes. — FreeBSD, see file LICENSE.text
  • the-cost-of-nothing — Determine the cost of things in Common Lisp. — GPLv3
  • trivial-clipboard — trivial-clipboard let access system clipboard. — MIT
Updated projects3d-matrices3d-vectorsalexandriaarchitecture.builder-protocolarchitecture.service-providerarray-utilsbabelbeastcaveman2-widgetsceplcepl.cameracepl.devilcepl.sdl2cepl.skitterchirpcl-anacl-ascii-artcl-bencodecl-cache-tablescl-cuddcl-custom-hash-tablecl-digraphcl-enumerationcl-gamepadcl-gpiocl-html5-parsercl-ixfcl-jpegcl-json-templatecl-k8055cl-monitorscl-mpg123cl-oclapicl-openglcl-out123cl-passcl-pslibcl-pythoncl-sandboxcl-sdl2cl-sdl2-imagecl-sdl2-ttfcl-slugcl-soilcl-spidevcl-strcl-tasuketecl-unificationcl-vectorscl-videocl-xkbclackclassimpclazyclinchclipclmlcloser-mopclssclxcoleslawcolleencolorizecroatoancrypto-shortcutsdeedsdefenumdeferreddendritedexadordirtdissectdocumentation-utilsdynaesrapfare-memoizationfast-ioflarefnforform-fiddleglsl-specglsl-toolkithu.dwim.asdfhu.dwim.debughu.dwim.defhu.dwim.perechu.dwim.presentationhu.dwim.rdbmshu.dwim.reiteratehu.dwim.urihu.dwim.utilhu.dwim.web-serverhumblerinquisitoriolibironcladjonathanjson-streamsjsonrpckenzolambda-fiddlelasslegitlichat-protocollichat-serverliblichat-tcp-clientlichat-tcp-serverlichat-ws-serverlisp-namespacelocal-timelquerymaidenmcclimmd5mel-basemodularizemodularize-hooksmodularize-interfacesmonkeylib-htmlmonkeylib-jsonneo4clnew-opninglenorthoclclomer-countparachuteparser.common-rulespathname-utilspipingplumpplump-bundleplump-sexpqlotqt-libsqtoolsqtools-uirandom-stateratifyread-csvredirect-streamrtg-mathrutilsserapeumsimple-inferiorssimple-tasksskittersoftdrinksouthspinneretstaplestructy-defclassstumpwmtemporal-functionstmtranslatetriviatrivial-argumentstrivial-benchmarktrivial-indenttrivial-main-threadtrivial-mimestrivial-thumbnailubiquitousuiopvarjoverboseweblocksxhtmlambda.

Removed projects: cl-geo, cl-wkb, cl4l, clim-pkg-doc, gsharp, lifoo, lisp-binary.

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

Patrick SteinFog of Light - Getting Underway

· 155 days ago

Dauntless (The Lost Fleet, Book 1) was the first science-fiction book I read that tried to deal with space combat with the real-world constraint that light only travels so fast. It takes light eight minutes to get from the Sun to Earth. It takes light more than a second to get from the Earth to the Moon. Depending on where they are in their orbits, it takes between three minutes and twenty-two minutes to get light from Mars to Earth.

Imagine that you’re a star-ship. You and your companions have just warped into a new star system. You see a flotilla of enemy ships about 45 light-minutes away. That means, you’ve got 45 minutes before that flotilla can possibly even know that you’re in their star system. How much can you get done in that time? Once they can see you, how much can you mislead them on your target if they’re going to be operating on data about where you were heading more than half an hour ago?

For years, I have been batting around this concept, hammering it into a game. I have finally gotten started on it.

Armed with some functions like these, I am constructing values which change at points in space-time and querying the value visible from other points in space-time.

(defgeneric get-nearest-value (space-time-value space-time-point)
  (:documentation "Find the observable value of a quantity
SPACE-TIME-VALUE when observed from a given location
SPACE-TIME-POINT. This method finds the most-recent
value V0 (at location P0) for this data when viewed from
the given location. This method returns (VALUES V0 P0).
This method makes no effort to interpolate the results."

Here are my first, visually-demonstrable results:

Hopefully, there will be plenty more coming in the near future.

LispjobsLinux systems engineer with Common Lisp experience, m-creations, Mainz, Germany

· 168 days ago

Full time position for German speaking Linux admin with Docker and
Common Lisp experience near Frankfurt, Germany

We are a small German software shop based in Mainz, Germany, founded in
2000. We create custom software solutions for mid-size to big companies
in finance/payment, health care, and media research.

For some of our customers, we also cover operational aspects of the
software lifecycle by creating and running Docker containers in
development, test, and production environments on clusters of servers
running Apache Mesos.

Missing pieces of infrastructure are written in Common Lisp (CL) and
interact with existing software components of the cluster (DNS, load
balancer etc.). Docker images are based on the embedded Linux
distribution OpenWrt.

We are looking for new colleagues who ideally

– have 3+ years of Linux experience (e.g. are fluent in shell scripting
and have a good overview of the GNU/Linux tools)

– have a working knowledge of Docker, its interaction with the host, and
the role of the container image

– have experience in Common Lisp (not necessarily professional)

– want to use CL to solve systems engineering problems (e.g. dynamic
load balancing, DNS re-configuration)

– are interested in mastering the OpenWrt build system (buildroot +
make/cmake) to create a secure in-container distribution

Experience in the mentioned areas is not as important as curiosity,
intelligence and open-mindedness. You will get the necessary time to
learn the missing skills. We are interested in a long-term relationship
rather than just staffing a project with ‘resources’.

Due to our size as a small company, we do care about each one of our
colleagues and react flexibly to the (sometimes changing) necessities of
their life. Together we try to develop a plan for your personal career,
depending on your own goals.

Curious? Please contact Kambiz Darabi at
He’ll be happy to give you more information and answer all your

m-creations gmbh
Acker 2
55116 Mainz

Zach BeaneCommon Lisp Standard Draft

· 169 days ago
Common Lisp Standard Draft:

This is a nice PDF version of the CL spec built from the final draft TeX sources. There's also a gitlab repo that can be used to reproduce the PDF locally. (Thanks to Rainer Joswig for sharing this on twitter.)

For older items, see the Planet Lisp Archives.

Last updated: 2017-10-07 15:57