#### Paul Khuong — Rendezvous Hashing: My Baseline "Consistent" Distribution Method

· 1 hour ago

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
 1 2 3 4 5 6 7 8 9 10 11 12 13  Destination = namedtuple('Destination', ['host', 'hash']) def merge_hashes(x, y): return ((x * 3) ^ y) % 2**64 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), dest.host) 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
 1 2 3 4 5 6 7 8 9 10 11 12 13  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), dest.host) 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 is 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é Rideau — A tale of many nests

· 20 hours 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 ...)
(when x1
(multiple-value-bind (a2 b2 p2) (foo2)
(with-open-file (f2 p2 ...)
(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 previous 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:

(nest
(multiple-value-bind (a1 b1 p1) (foo1))
(with-open-file (f1 p1 ...))
(when x1)
(multiple-value-bind (a2 b2 p2) (foo2))
(with-open-file (f2 p2 ...))
(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 things that are not expressions stricto sensu! For instance, it will work with case or match clauses:

(nest
(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 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 utility collection that is transcluded in ASDF, the build system used by nearly all software written in Common Lisp today. Thus, every Common Lisp program today 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 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 ...)
(letrec-syntax
((r
(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. 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 are just source-processing functions):

(define-syntax nest
(syntax-rules ()
((_ . forms)
(letrec-syntax
((nest-error
(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 name 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 meta programmation 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)))
(cond
((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)))
(cond
((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)))
(cond
((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)
acc
(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).

#### Nicolas Hafner — Portacle Release - Confession 75

· 17 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 Beane — September of Sly

· 17 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

Stay tuned for more!

· 20 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.

### Motivation

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

#### Checks

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.

#### Tests

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.

#### Suites

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 https://github.com/uint/quasirpg.git

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 https://github.com/sionescu/fiveam.git

#### Groundwork

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!
#:all-tests))

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%)

T
NIL

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)

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:

(QUASIRPG::ROLL-DICE 1 1)

evaluated to

0

which is not

=

to

1

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.

#### REASON-ARGS

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.

(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:
--------------------------------
MAKE-CHARACTER-TESTS []:

NAME

evaluated to

"tom"

which is not

STRING=

to

"Tom"

..
--------------------------------

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-TESTS []:
MAKE-CHARACTER should capitalize the name "tom", but we got: "tom".
--------------------------------

#### Reorganizing

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 Zaikonnikov — Also ALSA

· 21 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 news — August 2017 Quicklisp dist update now available

· 25 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
• 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

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

Enjoy!

#### Wimpie Nortje — Getting started with Common Lisp

· 28 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.

## 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

$svn co http://svn.clozure.com/publicsvn/openmcl/release/1.11/linuxx86/ccl 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

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 https://beta.quicklisp.org/quicklisp.lisp

2. Install Quicklisp in CCL:

Start CCL

$ccl In the REPL, execute (load "quicklisp.lisp") (quicklisp-quickstart:install) (ql:add-to-init-file)  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" Start SLIME 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 CL-USER>  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 Lisp-lang Cliki Find libraries and their documentation Quickdocs Common Lisp Language reference HyperSpec Help with Emacs EmacsWiki 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 Footnotes: 1. SLIME - The Superior Lisp Interaction Mode for Emacs. 2. See the "Tools" section in the Reddit sidebar #### Quicklisp news — July 2017 Quicklisp download stats · 45 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 Shatrov — Your personal DIY image search · 57 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/ichi.moe 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' services: match: image: pavlov/match:latest ports: - 127.0.0.1:8888:8888 command: ["/wait-for-it.sh", "-t", "60", "elasticsearch:9200", "--", "gunicorn", "-b", "0.0.0.0:8888", "-w", "4", "--preload", "server:app"] links: - elasticsearch elasticsearch: image: elasticsearch environment: - "ES_JAVA_OPTS=-Xms256m -Xmx256m" - bootstrap.mlockall=true expose: - "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)) (cond ((<= 400 return-code 499) (jsown:new-js ("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" (parse-request (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))) (unwind-protect (loop for value in (alexandria:hash-table-values *cache*) collect (worker value) into futures finally (map nil 'lparallel:force futures)) (lparallel:end-kernel))) (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*) (terpri) (apply 'format t str args) (force-output)))  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 */  with // 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. #### McCLIM — Progress report #9 · 58 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 (daniel@turtleware.eu) or on IRC (my nick is jackdaniel).

Sincerely yours,
Daniel Kochmański

· 61 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 news — July 2017 Quicklisp dist update now available

· 61 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

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").

Enjoy!

#### ECL News — Lisp (ECL) and QML (Qt5) on Android?

· 72 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 lisp-cffi-qt4.zip (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 3-build-apk.sh (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 sokoban_desktop.pro
$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: $ ./1-copy-libs.sh


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 sokoban.pro
$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: utils/cross-compile.lisp (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: $ ./2-install-lib.sh


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:


$./3-build-apk.sh  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 android-libsokoban.so-deployment-settings.json \
--output android-build \
--deployment ministro \
--verbose


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: Lisp.call("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:

sokoban.apk

Enjoy!

#### Quicklisp news — June 2017 Quicklisp dist update now available

· 85 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
• 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 http://zlib.net/ — 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

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

#### Paul Khuong — Chubanov's Projection Methods for 0/1 Programming

· 99 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.

#### McCLIM — Progress report #8

· 105 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).

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 (daniel@turtleware.eu) or on IRC (my nick is jackdaniel).

Sincerely yours,
Daniel Kochmański

#### ABCL Dev — ABCL 1.5.0

· 105 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.

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 Hafner — Trial "Study Session" Next Saturday, 17th of June

· 106 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!

#### Lispjobs — Lisp programmer, Keepit.com, Lviv, Ukraine

· 107 days ago

Keepit.com 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: mhn@keepit.com, Skype: maryna.hnatyk

#### ABCL Dev — ABCL 1.5.0-rc-0 draft of upcoming User Manual

· 109 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.

http://abcl.org/trac/milestone/1.5.0

http://abcl.org/releases/1.5.0/

Draft of upcoming User Manual to which corrections are solicited.

http://abcl.org/releases/1.5.0/abcl-1.5.0-rc-0.pdf

#### Paul Khuong — Relaxed Revocable Locks: Mutual Exclusion Modulo Preemption

· 111 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.

“rlock.c”
 1 2 3 4 5 6 7 8 9 10 11  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.

“rlock.c”
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  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.

“rlock.c”
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33  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); snapshot.sequence++; ck_pr_fas_64(&self->seq.bits, snapshot.bits); return true; } static inline struct rlock_owner * get_self(void) { struct rlock_owner *self; self = rlock_self; if (UNLIKELY(self == NULL)) { self = allocate_self(); } update_self(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.c”
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39  rlock_owner_seq_t 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! */ break; } /* CAS failed. snapshot.bits has the new owner. */ /* Eagerly observe any cancellation. */ update_self(self); /* CAS failed. Spin a bit. */ ck_pr_stall(); } return seq; } 

Most of the trickiness hides in rlock_owner_cancel.

“rlock.c”
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80  bool 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.c”
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69  bool 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. */ "1:\n\t" /* * 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" ".popsection\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)) { update_self(self); return false; } /* Force lock reacquisition after a couple thousand writes. */ if (UNLIKELY(op_count >= OP_LIMIT)) { self->op_count = 0; rlock_owner_release(); } 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.c”
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38  void 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; (void)signal; (void)info; 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) { continue; } assert(self != NULL); /* skip the critical instruction. */ mctx->gregs[REG_RIP] = record.end; /* set the interrupted flag. */ mctx->gregs[REG_RAX] = 1; return; } /* Might as well publish that we observed any cancellation request. */ if (self != NULL) { ck_pr_fas_32(&self->acked_sequence, ck_pr_load_32(&self->cancel_sequence)); } return; } 

## 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 Stein — Fog of Light - Starting to Add Star-Fields

· 119 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.

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

· 120 days ago

#### Quicklisp news — May 2017 Quicklisp dist update now available

· 127 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
• markdown.cl — 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

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 Stein — Fog of Light - Getting Underway

· 132 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."
))

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

#### Lispjobs — Linux systems engineer with Common Lisp experience, m-creations, Mainz, Germany

· 145 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

– 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,

questions.

m-creations gmbh
Acker 2
55116 Mainz

#### Zach Beane — Common Lisp Standard Draft

· 146 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.)

#### François-René Rideau — Design at the confluence of programming languages and build systems

· 147 days ago

This short article discusses upcoming changes and future challenges for ASDF, the Common Lisp build system. It also draws lessons for a hypothetical successor to ASDF, for build systems in general, languages in which to write them, and languages that would have an internal build system that could rival with modern build systems.

ASDF, "Another System Definition Facility", is the de facto standard build system for Common Lisp (CL). It is relatively lightweight (13 kloc, over half of which for the portability layer UIOP, the "Utilities for Implementation- and OS- Portability"), quite portable (17 supported implementations), configurable (though importantly it "just works" by default), well-featured (it can create standalone executables), extensible (e.g. with support for linking C code, or for compiling FORTRAN through Lisp, etc.). But it lacks many features of modern build systems like e.g. Bazel: it does not support determinism and reproducibility, distribution and caching, cross-compilation to other platforms, building software written in languages other than CL, integration with non-CL build systems, management of multiple versions of the same software, or scaling to millions of files, etc. Historically, these limitations are due to ASDF being at heart an in-image build system in direct line of the original Lisp Machine DEFSYSTEM: it is designed to build and load software into the current Lisp image. But the challenges in possibly transforming ASDF into a modern build system touch limitations of Common Lisp itself and tell us something about language design in general.

I have essentially two development branches more or less ready for merge in the upcoming ASDF 3.3: the "plan" branch that provides proper phase separation (briefly discussed in my ELS 2017 demo), and the "syntax-control" branch that binding for syntax variables around ASDF evaluation (briefly discussed in my ELS 2014 extended article, section 3.5 "Safety before Ubiquity").

### Phase Separation

The first branch solves the problem of phase separation. The branch is called "plan" because I started with the belief that most of the changes would be centered around how ASDF computes its plan. But the changes run deeper than that: 970 lines were added or modified all over the source code, not counting hundreds more were moved around as the code got reorganized. That's double the number of lines of the original ASDF, and it took me several months (part time, off hours) to get just right. Still, it is up-to-date, passes all tests, and works fine for me.

To understand what this is about, consider that a basic design point in ASDF 1.0 to 3.2 is that it first plans your entire build, then it performs the plan. The plan is a list of actions (pair of OPERATION and COMPONENT), obtained by walking the action dependency graph implicitly defined by the COMPONENT-DEPENDS-ON methods. Performing the plan is achieved by calling the PERFORM generic function on each action, which in turn will call INPUT-FILES and OUTPUT-FILES to locate its inputs and outputs.

This plan-then-perform strategy works perfectly fine as long as you don't need ASDF extensions (such as, e.g. cffi-grovel, or f2l). However, if you need extensions, there is a problem: how do you load it? Well, it's written in Lisp, so you could use a Lisp build system to load it, for instance, ASDF! And so people either use load-system (or an older equivalent) from their .asd files, or more declaratively use :defsystem-depends-on in their (defsystem ...) form, which in practice is about the same. Now, since ASDF up until 3.2 has no notion of multiple loading phases, what happens is that a brand new separate plan is computed then performed every time you use this feature. This works well enough in simple cases: some actions may be planned then performed in multiple phases, but performing should be idempotent (or else you deserve to lose), therefore ASDF wastes some time rebuilding a few actions that were planned before an extension was loaded that also depended on them. However, the real problems arise when something causes an extension to be invalidated: then the behavior of the extension may change (even subtly) due to its modified dependency, and the extension and all the systems that directly or indirectly depend on should be invalidated and recomputed. But ASDF up until 3.2 fail to do so, and the resulting build can thus be incorrect.

The bug is quite subtle: to experience it, you must be attempting an incremental build, while meaningful changes were made that affect the behavior of an ASDF extension. This kind of situation is rare enough in the small. And it is easily remedied by manually building from scratch. In the small, you can afford to always build from scratch the few systems that you modify, anyway. But when programming in the large, the bug may become very serious. What is more, it is a hurdle on the road to making a future ASDF a robust system with deterministic builds.

Addressing the issue was not a simple fix, but required deep and subtle changes that introduce notions neglected in the previous simpler build models: having a session that spans multiple plan-then-perform phases and caches the proper information not too little not too much; having a notion that loading a .asd file is itself an action that must be taken into account in the plan; having a notion of dynamically detecting the dependencies of loading a .asd file; being able to check cross-phase dependencies before to keep or invalidate a previously loaded version of a .asd file without causing anything to be loaded in the doing; expanding the state space associated to actions as they are traversed potentially many times while building the now multi-phase dependency graph. And all these things interfere with each other and have to be gotten just right.

Now, while my implemented solution is obviously very specific to ASDF, the issue of properly staging build extensions is a common user need; and addressing the issue would require the introduction of similar notions in any build system. Yet, most build systems, like ASDF up until 3.2, fail to offer proper dependency tracking when extensions change: e.g. with GNU Make you can include the result of a target into the Makefile, but there is no attempt to invalidate targets if recipes have changed or the Makefile or some included file was modified. Those build systems that do implement proper phase separation to track these dependencies are usually language-specific build systems (like ASDF); but most of them (unlike ASDF) only deal with staging macros or extensions inside the language (e.g. Racket), not with building arbitrary code outside the language. An interesting case is Bazel, which does maintain a strict plan-then-perform model yet allows user-provided extensions (e.g. to support Lisp). However, its extensions, written in a safe restricted DSL (that runs into plan phase only, with two subphases, "load" and "analysis") are not themselves subject to extension using the build system (yet the DSL being a universal language, you could implement extensibility the hard way).

Fixing the build model in ASDF 3.3 led to subtle backward-incompatible changes. Libraries available on Quicklisp were inspected, and their authors contacted if they depended on modified functionality or abandoned internals. Those libraries that are still maintained were fixed. Still, I'd just like to see how compatible it is with next month's Quicklisp before I can recommend releasing these changes upon the masses.

### Syntax Control

The current ASDF has no notion of syntax, and uses whatever *readtable*, *print-pprint-dispatch*, *read-default-float-format* or many other syntax variables are ambient at the time ASDF is called. This means that if you ever side-effect those variables and/or the tables that underlie the first two, (e.g. to enable fare-quasiquote for the sake of matching with optima or trivia), then call ASDF, the code will be compiled with those modified tables, which will make fasl that are unloadable unless the same side-effects are present. If systems are modified and compiled that do not have explicit dependencies on those side-effects, or worse, that those side-effects depend on (e.g. fare-utils, that fare-quasiquote depends on), then your fasl cache will be polluted and the only way out will be to rm -rf the contaminated parts of the fasl cache and/or to build with :force :all until all parts are overwritten. Which is surprising and painful. In practice, this means that using ASDF is not compatible with making non-additive modifications to the syntax.

Back in the 3.1 days, I wrote a branch whereby each system has its own bindings for the syntax variables, whereas the default tables be read-only (if possible, which it is in many implementations). With that branch, the convention is each system can do modify the syntax in whatever way it wants, and that will only affect that system; however, changes to syntax tables must be done after explicitly creating new tables, and any attempt to side-effect the default global tables will result in an error.

This was the cleanest solution, but alas it is not compatible with a few legacy systems that explicitly depend on modifying the syntax tables (and/or variables?) for the next system to use, as ugly as that is. My initial opinion was that this should be forbidden, and that these legacy systems should be fixed; however, these were legacy systems at a notable Lisp company, with no one willing to fix them; also, I had resigned from maintainership and the new maintainer is more conservative than I am, so in the end the branch was delayed until after said Lisp company would investigate, which never happened, and the branch was never merged.

A simpler and more backward-compatible change to ASDF would have been to have global settings for the variables that are bound around any ASDF session. Then, the convention would be that you are not allowed to use ASDF again to load regular CL systems after you modify these variables in a non-additive way; and the only additive changes you can make are to add new entries to the shared *readtable* and *print-pprint-dispatch* tables that do not conflict with any default entry or earlier entry (and that includes default entries on any implementation that you may want to support, so e.g. no getting #_ or #/ if you want to support CCL). Even additive changes, if made, must somehow not clash with each other, or they become non-additive; but there is no way to automatically check that this is the case and issue a warning. After you make non-additive changes (if you do), then ASDF can't be used anymore to build normal systems that may conflict with those changes, and if they are modified and you call ASDF on a system that depends on them, you lose (or you must first make all those systems immutable).

Note that because ASDF would already break in those cases, most of these constraints de facto exist, are enforced, and are respected by all ASDF users. There remains the question of binding the variables around the build, which allows normal systems to be built even if a user changes the variables, or to not bind them, which puts the onus on most users of keeping these variables bound to reasonable values around calls to ASDF for the benefit of a few users would want their own breaking changes to persist after the build. I believe the first option (bind the variables) is cleaner, though the second (basically, do nothing) is more backward-compatible.

In all cases, you can always make non-additive changes to a readtable (such as enabling fare-quasiquote) by locally binding *readtable* to a different value, e.g. using named-readtables:in-readtable. A local binding won't adversely affect the ASDF build; but unless ASDF is changed to enforce its own bindings, you'll have to make sure to manually undo your local bindings before you call ASDF again.

The problem with not adding any syntax-control to ASDF is that it forces Lispers to always be conservative about modifying the readtable and calling ASDF (or having it called indirectly by any function whatsoever that they call, which they can't always predict). In practice this makes hacking CL code hostile to interactive development with non-additive syntax modification; which defeats in social conventions a technical feature of the language often touted as cool by its zealots. If syntax-control is added to ASDF, then you can freely do your syntax modifications and be confident that building code won't be adversely affected.

The current branch implements the simpler option of binding variables around ASDF sessions, and using a mutable shared readtable that should only be modified additively. It has probably bitrotten, and should be updated or rewritten. The current maintainer, Robert Goldman, should probably opine on which change to adopt with what schedule (3.3.0? 3.2.2? 3.3.1? 3.4.0?) and sign off the API.

### Vanquishing Language Limitations

These two modifications are ((now)low)-hanging fruits in making ASDF a more robust build tool, one that supports working with non-trivial extension to the build system or the Lisp syntax. And in both cases, the limit reached by ASDF is ultimately that CL is a hippie language that allows unrestricted global side-effects and disallows disallowing. Therefore extensions necessarily introduce potential conflict with each other that have to be solved in wetware via convention, whereby all users are to be trusted not go wild with side-effects. The system cannot even detect violations and warn users of a potential mistake; users will have to experience subtle or catastrophic failure and figure out what went wrong.

A better language for a build system should be purer: inasmuch as it has "global" side-effects, it should allow to "fork" the "global" state in an efficient incremental way. Or even better, it should make it easy to catch side-effects and write this forking support in userland. At the very least, it would make it possible to detect violations and warn the user. Bazel is an example build system with an extension language that has local side-effects, but globally has pure forked environments. A successor to ASDF could similarly provide a suitably pure dialect of Lisp for extensions.

Happily, adding better syntax control to ASDF suggests an obvious solution: ASDF extensions could be written in an enforceable subset of a suitable extension of Common Lisp. Thus, ASDF extensions, if not random Common Lisp programs, can be made to follow a discipline compatible with a deterministic, reproducible build.

What would be an ideal language in which to write a extensible build system? Well, I tackled that question in another article, the Chapter 9: "Build Systems" of my blog "Ngnghm". That's probably too far from CL to be in the future of ASDF as such, though: the CL extension would be too large to fit ASDF's requirement of minimalism. On the other hand, if such a language and build system is ever written, interest for CL and ASDF might wane in favor of said latter build system.

In any case, in addition to not being a blub language, features that will make for a great programming language for an integrated build system include the following: making it possible to directly express functional reactive programming, determinism as well as system I/O, laziness as well as strictness, reflection to map variables to filesystem and/or version control as well as to stage computations in general including dynamic build plans, hygiene in syntax extension and file reference, modularity in the large as well as in the small, programmable namespace management, the ability to virtualize computations at all sizes and levels of abstractions, to instrument code, etc.

### Towards cross-compilation

Now, before we get reproducible builds, we also need to enable cross-compilation for ASDF systems, so the necessarily unrestricted side-effects of compiling Common Lisp code cannot interfere with the rest of the build. Cross-compilation also allows building on a different platform, which would be important to properly support MOCL, but would probably also mesh well with support for building software in arbitrary other languages.

Importantly, instead of the (perform operation component) protocol that specifies how to build software in the current image, a (perform-form target operation component) protocol (or maybe one where the target information has been made part of the operation object) would return forms specifying how to build software, which could then happen in separate Lisp or non-Lisp process, on the same machine or on another worker of a distributed build farm.

Note however, that one essential constraint of ASDF is that it should keep working in-image in the small and not depend on external processes or additional libraries. Any serious effort towards a "deterministic build" should therefore remain an extension indeed (though one users would load early).

Still, if this extension is to remain compatible with ASDF and its .asd files, providing a backward-compatible path forward, then modifications and cleanups may have to be done to ASDF itself so it behaves well. Even keeping that hypothetical deterministic build separate, I expect non-trivial changes to the ASDF API to enable it, such as the perform-form protocol mentioned above. But backward-compatibility and smooth transition paths have always been the name of the game for ASDF; they are what make possible an ecosystem with thousands of packages.

There is a precedent to an ASDF extension leading to (most positive) changes in ASDF: POIU, the "Parallel Operators on Independent Units", Andreas Fuchs' extension to compile files in forks (but still load them in-image). Making sure that POIU can be expressed as an extension of ASDF without redefining or breaking the provided abstractions, was instrumental in the evolution of ASDF: it led to many cleanups in ASDF 2, it inspired several of the breakthroughs that informed what became ASDF 3, and it kept influencing ASDF 3.3.

Thus, even though ASDF will stay forever an in-image build system, and even though a deterministic build extension (let's call it FDSA, the Federated Deterministic System Assembler) may ultimately remain as little used as POIU (i.e. because it lacks sufficient benefits to justify the transition costs), I expect the design of the base ASDF to be deeply influenced by the development of such a tool (if it happens).

### Looking for new developers

Robert Goldman and I are not getting younger, not getting more interested in ASDF, and we're not getting paid to hack on it. We are looking for young Common Lisp hackers to join us as developers, and maybe some day become maintainers, while we're still there to guide them through the code base. Even without the ambition (and resources) to actually work towards a hypothetical FDSA, our TODO file is full of items of all sizes and difficulties that could use some love. So, whatever your level of proficiency, if you feel like hacking on a build system both quite practical and full of potentiality, there are plenty of opportunities for you to work on ASDF (or a successor?) and do great, impactful work.

#### McCLIM — Progress report #7

· 152 days ago

Dear Community,

During this iteration I have worked on the Debugger (system clim-debugger) to bring it closer to sldb:

More work on the module is planned with a final goal to integrate it with the Listener and to have it as a default debugger for McCLIM applications. Suggestions on how to improve the interface, testing and help with coding are appreciated. Preliminary documentation has been written and put in the McCLIM manual draft.

I've started working on a library called Slim[1] the goal of which is to provide some of the CLIM interfaces in easy to learn and write manner (i.e more context dependent, less verbose names, unified abstractions etc.). For now it is only a skeleton having barely four macros, but I'd love to hear suggestions, what should it contain, in what form etc. A sketch may be found in the source code Libraries/Slim/. If you think it is a bad idea to have such library shipped with McCLIM - let me know about that too!

The documentation was extended in some places. Also building the info document works now (long standing issue). An updated version of manual draft may be found on the McCLIM website. The Drei documentation has been put in a separate document due to its size and independent scope from the rest of McCLIM.

Nisar Ahmad has solved one of the bounties related to menus and command tables. He also submitted documentation for the menu functionality, thereby earning $150. Congratulations! Speaking of finances - all money is now accumulated solely for bounties and development tasks, none is withdrawn by me since the beginning of year 2017. Currently we have$1226 at our disposal and active bounties worth $700. Declared monthly donations at the moment equal$297. Additionally one-time contributions come every month. That means that we can post two or three bounties a month without draining the current resources, or spawn a bunch of worthwhile tasks and keep going as money comes. This is fantastic news. Thank you all for your support to the project!

At the moment we have five active bounties worth \$700 which may be found here:

https://www.bountysource.com/teams/mcclim/bounties

New bounties have a time limit assigned to them (six months) - thanks to that we are able to reclaim money from unresolved issues and propose it somewhere else (or repost the same bounty).

To improve the visibility of the issues which have bounties on them I've added a label to GitHub issue tracker: bounty.

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 (daniel@turtleware.eu) or on IRC (my nick is jackdaniel`).

We are very happy that the number of McCLIM users grows, which may be infered from number of questions on the IRC channel, bug reports and pull requests.

Sincerely yours,
Daniel Kochmański

[1] Simplified Lisp Interface Manager.

For older items, see the Planet Lisp Archives.

Last updated: 2017-09-25 02:41