Planet Lisp

Zach BeaneGoogle-hosted Lisp Talk in Boston

· 4 hours ago

On Tuesday, June 9th, Dr. Christian Schafmeister will present his talk on Clasp at the Google office at Kendall Red Line station. It’s the talk he presented at ELS last month, and worth seeing if you can make it.

Martin Cracauer is hosting, and has written up all the details on the boston-lisp list.

Luís OliveiraPretty printer puzzle

· 3 days ago
This past week, I came across a Lisp challenge that turned out to be trickier than one might expect at first. I needed to pretty-print a Lisp form to a string and identify the positions of certain subforms. Here's an example:
CL-USER> (with-output-to-string (*standard-output*)
           (pprint '(defun factorial (x) (if (zerop x) 1 (* x (factorial (1- x)))))))
      (* X (FACTORIAL (1- X)))))"
In this, output the bounding indices of the IF form are 24 and 77. In other words:
CL-USER> (subseq * 24 77)
      (* X (FACTORIAL (1- X))))"
The challenge, then, is to write a function that, given a form and list of subforms, returns a string with the pretty-printed output and a list of bounding indices for each subform. E.g.
CL-USER> (pprinted-bounds '(defun factorial (x) #1=(if (zerop x) 1 (* x #2=(factorial (1- x)))))
                          (list '#1# '#2#))
      (* X (FACTORIAL (1- X)))))"
((24 77) (57 75))
I'll post my solution later. Have fun. :-)

drmeisterClasp has a developers mailing list

· 7 days ago

The mailing list is

If you are interested in following developments to the next release you can join at:

drmeisterTagged pointers and immediate fixnums, characters, and single-floats in Clasp

· 10 days ago

In preparation for making Clasp generate performant code, I’ve switched to using tagged pointers and immediate fixnums, characters and single-floats.  This is a common technique in dynamic language implementations where you represent small values directly within pointers rather than storing them on the heap. The tagging scheme in Clasp is as follows for 64-bit systems (32-bit is not supported at the moment).

A pointer provides 64-bits (63 … 0) to work with.

FIXNUM 0b0 The other 63 bits are used to store a signed FIXNUM. The 0b0 bit allows certain arithmetic operations (addition, subtraction, comparison) to be very fast.
OTHER 0b001 In the lower three bits represents a pointer to an object on the heap.  The pointer is 8-byte aligned in memory.
CONS 0b011 A pointer to a CONS cell. Robert Strandh suggested this so that Common Lisp code can easily distinguish CONS cells from non CONS cells and speed up list traversal.
FRAME 0b101 A pointer to an array on the stack.  I’m not sure if I’ll continue to use this going forward – it’s really just for bootstrapping. I may reuse this tag to represent a pointer to C++ objects on the C++ heap.
CHARACTER 0b00111 A character in a 32-bit value (>> 5 to unbox).
SINGLE-FLOAT 0b01111 Represents a single precision C/C++ float, a 32-bit value (>>5 to unbox).
UNUSED1 0b10111 Suggestions?
UNUSED2 0b11111 Suggestions?

I’m especially interested in peoples thoughts on embedding something like a double-precision float within 61 bits. I’m 99.9(repeating)% sure it can’t be done but I’d love something like that. Arithmetic, Arrr! she be a harsh mistress.

All pointer access in Clasp is performed using a C++ template class called smart_ptr and it was relatively easy to modify this class to manage the tagged pointers. The untagging/tagging of OTHER-PTR and CONS-PTR pointers is carried out by overloading the C++ dereferencing operators: operator-> and operator*, of the smart_ptr template class.

It was a bit tricky to get these immediate values to play nice with C++ types and inheritance because the Clasp C++ code does not treat all Common Lisp types as a single undifferentiated pointer type. Clasp uses C++ types like T_sp, List_sp, Cons_sp, Float_sp, Symbol_sp, HashTable_sp etc. to distinguish different Common Lisp pointer types from each other within the C++ code. An assignment like:

Symbol_sp y(...);
T_sp x = y;

is valid and very common within the Clasp C++ code. But:

T_sp a(...);
Symbol_sp s = gc::As<Symbol_sp>(a);

will signal a Common Lisp error if a doesn’t point to a SYMBOL at the time of the assignment to s.

To deal with this I defined a template class: TaggedCast<ToPtr,FromPtr> that provides an “isA” function and a “castOrNULL” function that can be specialized to simulate inheritance between classes that represent immediate values to the regular C++ class hierarchy.

Zach BeaneCLISP supporting libraries need maintainers, too

· 15 days ago

Jörg Höhle: “it seems to me that part of the difficulties with compiling, packaging and obtaining clisp stem from the core libraries that it uses, namely libffi and esp. libsigsegv. Both were created by Bruno Haible decades ago and both are in need of a maintainer.”

You can read the entire article on gmane.

Sam Steingold follows up: “note that libffi is actively maintained[, ] clisp uses libffcall”

Quicklisp newsASDF 3 is coming to Quicklisp soon

· 18 days ago
In the next week or two, I'm going to update Quicklisp so that if ASDF is missing, or not at least version 3.1, it will fetch and load ASDF 3.1.4. This should be a pretty conservative change. Almost all implementations already include ASDF 3.

If you'd like to try the new Quicklisp client that fetches ASDF 3 if needed, see this post to the Quicklisp mailing list.

Zach BeaneCLISP needs maintainers

· 19 days ago

Jörg Höhle writes: "[…] we’re looking for a maintainer, i.e. somebody who has time to donate to assess patches, test and build a new release. It would be nice if somebody younger than us, the old guys, who have been with clisp for over 20 years, would jump in and care."

Quicklisp newsMay 2015 Quicklisp dist update now available

· 21 days ago

This Quicklisp update is supported by my employer, Clozure Associates. If you need commercial support for Quicklisp, or any other Common Lisp programming needs, it's available via Clozure Associates.

New projects:

  • bytecurry.asdf-ext — ASDF extension(s) for generating atdoc documentation. — MIT
  • cl-durian — dynamic html generation from list structures (interpolation friendly) — WTFPL
  • cl-marklogic — Common Lisp library for accessing MarkLogic Server. — LGPL3
  • cl-pslib — A CFFI wrapper for the pslib library, a library for generating PostScript files. — LLGPL
  • cl-pslib-barcode — A barcode generator for the cl-pslib library. — LLGPL
  • cl-simple-concurrent-jobs — A simple API for running concurrent jobs and collecting the results — BSD 2-Clause
  • cl-sophia — High-level API for Sophia key-value storage — WTFPL
  • cl-strftime — Common Lisp compiler for the strftime language. — MIT
  • cl-tga — TGA file loader — MIT
  • erudite — Literate Programming System for Common Lisp — MIT
  • intel-hex — A library to handle Intel HEX format. — MIT
  • snakes — Python style generators for Common Lisp. — Apache 2.0

Updated projects: alexandria, antik, arrow-macros, babel, beirc, birch, blackbird, buffalo, bytecurry.mocks, caveman, chanl, chipz, cl+ssl, cl-ana, cl-async, cl-charms, cl-enumeration, cl-gobject-introspection, cl-grace, cl-graph, cl-i18n, cl-launch, cl-mtgnet, cl-netstring-plus, cl-ply, cl-quickcheck, cl-rabbit, cl-read-macro-tokens, cl-readline, cl-rethinkdb, cl-sdl2, cl-singleton-mixin, cl-slug, cl-voxelize, cl-yaml, clack, clack-errors, clim-widgets, climacs, clinch, clipper, closer-mop, colleen, common-doc, common-html, common-lisp-stat, commonqt, corona, dartsclhashtree, dartsclmessagepack, defclass-std, dyna, eazy-process, exscribe, f2cl, fare-csv, fast-http, function-cache, gbbopen, generic-comparability, gsll, hu.dwim.delico, hu.dwim.stefil, hu.dwim.syntax-sugar, hu.dwim.util, immutable-struct, inferior-shell, jonathan, json-responses, lass, let-over-lambda, lev, lisp-interface-library, lisp-invocation, lisp-matrix, lquery, lucerne, metap, mexpr, mgl-pax, nibbles, ningle, nsort, perlre, plump, proc-parse, qlot, qtools, quadtree, quasiquote-2.0, scalpl, scriba, scribble, serapeum, shellpool, should-test, shuffletron, staple, stmx, stumpwm, thorn, transparent-wrap, trivial-download, usocket, with-c-syntax, wookie.

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

Quicklisp newsApril 2015 download stats

· 21 days ago
Here are the top 100 downloads for last month:
 4230  alexandria
3401 trivial-features
3377 babel
3366 cl-ppcre
3102 cffi
2717 bordeaux-threads
2620 closer-mop
2611 trivial-garbage
2605 cl-fad
2575 flexi-streams
2574 trivial-gray-streams
2471 cl+ssl
2366 nibbles
2245 usocket
2228 cl-base64
2210 split-sequence
2191 chunga
2087 slime
2047 iterate
2046 trivial-backtrace
2042 drakma
2002 anaphora
1925 ironclad
1691 puri
1682 chipz
1653 local-time
1520 named-readtables
1455 md5
1399 hunchentoot
1259 metabang-bind
1152 cl-colors
1124 let-plus
1070 optima
1051 cl-unicode
1020 trivial-utf-8
992 cl-syntax
950 rfc2388
946 cl-interpol
943 trivial-types
941 cl-annot
934 cl-ansi-text
846 postmodern
839 prove
803 parse-number
799 asdf-system-connections
791 uuid
780 cl-utilities
765 cl-containers
765 metatilities-base
760 quicklisp-slime-helper
701 fast-io
695 jsown
672 ieee-floats
671 lparallel
664 static-vectors
658 cl-json
640 plump
605 fiveam
601 zpng
594 lquery
590 trivial-indent
587 clss
578 buildapp
566 array-utils
559 xsubseq
557 cl-sqlite
547 salza2
546 quri
542 command-line-arguments
540 osicat
521 garbage-pools
520 fast-http
515 cl-mssql
509 cl-who
508 cl-vectors
506 clx
505 iolib
503 py-configparser
499 dynamic-classes
497 asdf-finalizers
497 cl-log
496 cl-marshal
494 cl-markdown
484 trivial-mimes
483 cl-abnf
477 clack
465 fare-utils
450 ningle
418 zpb-ttf
408 cl-dbi
408 st-json
404 http-body
403 circular-streams
398 closure-common
392 fare-quasiquote
380 cl-csv
380 cxml
377 parenscript
373 myway
352 map-set

Zach BeaneLispWorks 7.0 is released

· 22 days ago

Dave Fox just posted this message to the LispWorks mailing list:

LispWorks Ltd is pleased to announce the release of LispWorks 7.0 on Windows®, Macintosh®, x86/x86_64 Linux®, ARM Linux®, FreeBSD®, AIX®, x86/x64 Solaris™ and SPARC/Solaris™ platforms. Also, new LispWorks for Mobile Runtime products target Android and iOS apps.

LispWorks 7.0 brings these new features:

  • 32-bit implementation for ARM Linux.
  • 32-bit and 64-bit implementations for PowerPC/AIX.
  • Java interface.
  • Characters and strings support all Unicode planes.
  • Editor supports Unicode entire range, including Chinese and Japanese characters.
  • Improved documentation including consolidation of CAPI manuals with more cross references, and more self-contained examples.
  • Code coverage tools.
  • Asynchronous socket I/O and UDP sockets.
  • Editor supports more fonts on Cocoa.
  • Support for multi-touch gestures.
  • Graphic Tools API (beta quality).
  • More CAPI enhancements including efficient transient display on output-panes.
  • Improvements in the IDE including Directory mode and buffers list options in Editor.
  • Various other new features including:
    • Thread-safe operations for ensuring a hash table entry.
    • Efficient access for 8-bit simple vectors.
    • FLI type for holding the address of a foreign symbol (suitable for C to Lisp callbacks).
    • 64-bit integer FLI types in 32-bit LispWorks.
    • Efficient raw 64-bit arithmetic and vector access in 64-bit LispWorks.
    • UTF-16 and KOI8-R encodings.
    • CLOS optimizations for copying objects.
    • On Windows, delivered DLLs can use a private copy of the MSVCRT runtime.
    • On Macintosh, the Cocoa IDE’s event loop has better error handling and a new defense against deadlocks.
  • Bug fixes.

Not all features are supported for every LispWorks product and platform. For details please see the feature table at

LispWorks Professional (64-bit implementation now available) and Enterprise Editions still offer excellent value to commercial users and academic institutions with no runtime license fees. An annual maintenance contract is available.

LispWorks Hobbyist and HobbyistDV Editions now offer an affordable fully functional Common Lisp IDE for non-commercial and non-academic use by individuals.

LispWorks for Android Runtime allows you to deliver (non-GUI) Lisp libraries which you can incorporate into Android apps (“mobile Lisp libraries”). It is available as an add-on to customers with LispWorks 7.0, which you use to develop your code before creating the mobile Lisp library. We do not charge runtime license fees for mobile Lisp libraries generated by LispWorks for Android Runtime.

LispWorks for iOS Runtime allows you to deliver (non-GUI) Lisp libraries which you can incorporate into iOS apps. It is available as an add-on to customers with LispWorks 7.0, which you use to develop your code before creating the mobile Lisp library. We do not charge runtime license fees for mobile Lisp libraries generated by LispWorks for iOS Runtime.

More details of the improvements in this release can be found in the Release Notes at

Pricing, sales, and other information is available in the original lisp-hug article.

Vladimir SedachSymbolics MacIvory auctions

· 22 days ago
For anyone interested in acquiring a Symbolics system, here is an email I just received from David K. Schmidt, director of sales at Symbolics:

We are in the process of consolidating two storage facilities into one new one. To reduce the amount that needs to be moved we are liquidating some of the inventory that is not needed for future operations.

Along with auctions for 36xx boards and other spare parts we are going to sell the following 4 MacIvory systems in serial auctions one after the other:

1. MacIvory model 3 with 8 MWords in a Quadra 700 with 20 MBs and a 9GB 10000 rpm disk

2. MacIvory model 3 with 8 MWords in a Mac IIci with 20 MBs, a 4GB 7200 rpm disk and a Radius Accelerated 24-bit graphics card

3. MacIvory model 2 with 2.6 MWords in a Mac IIfx with 20 MBs, a 4GB 7200 rpm disk, a Radius Accelerated 24-bit graphics card and an ethernet card

4. MacIvory model 2 with 1.3 MWords in a Quadra 650 with 64 MBs and a 9GB 10000 disk

I will send you a link to each auction as they are put on line.

If you are interested in any 36xx part that you don't see an auction for, email me for a quote.

You can contact David at

Dimitri FontaineQuicklisp and debian

· 25 days ago

Common Lisp users are very happy to use Quicklisp when it comes to downloading and maintaining dependencies between their own code and the librairies it is using.

Sometimes I am pointed that when compared to other programming languages Common Lisp is lacking a lot in the batteries included area. After having had to package about 50 common lisp librairies for debian I can tell you that I politely disagree with that.

And this post is about the tool and process I use to maintain all those librairies.

Quicklisp is good at ensuring a proper distribution of all those libs it supports and actually tests that they all compile and load together, so I've been using it as my upstream for debian packaging purposes. Using Quicklisp here makes my life much simpler as I can grovel through its metadata and automate most of the maintenance of my cl related packages.

It's all automated in the ql-to-deb software which, unsurprisingly, has been written in Common Lisp itself. It's a kind of a Quicklisp client that will fetch Quicklisp current list of releases with version numbers and compare to the list of managed packages for debian in order to then build new version automatically.

The current workflow I'm using begins with using `ql-to-deb` is to `check` for the work to be done today:

$ /vagrant/build/bin/ql-to-deb check
Fetching ""
Fetching ""
update: cl+ssl cl-csv cl-db3 drakma esrap graph hunchentoot local-time lparallel nibbles qmynd trivial-backtrace
upload: hunchentoot

After careful manual review of the automatic decision, let's just `update` all what `check` decided would have to be:

$ /vagrant/build/bin/ql-to-deb update
Fetching ""
Fetching ""

Updating package cl-plus-ssl from 20140826 to 20150302.
     see logs in "//tmp/ql-to-deb/logs//cl-plus-ssl.log"
Fetching ""
Checksum test passed.
     File: "/tmp/ql-to-deb/archives/cl+ssl-20150302-git.tgz"
      md5: 61d9d164d37ab5c91048827dfccd6835
Building package cl-plus-ssl

Updating package cl-csv from 20140826 to 20150302.
     see logs in "//tmp/ql-to-deb/logs//cl-csv.log"
Fetching ""
Checksum test passed.
     File: "/tmp/ql-to-deb/archives/cl-csv-20150302-git.tgz"
      md5: 32f6484a899fdc5b690f01c244cd9f55
Building package cl-csv

Updating package cl-db3 from 20131111 to 20150302.
     see logs in "//tmp/ql-to-deb/logs//cl-db3.log"
Fetching ""
Checksum test passed.
     File: "/tmp/ql-to-deb/archives/cl-db3-20150302-git.tgz"
      md5: 578896a3f60f474742f240b703f8c5f5
Building package cl-db3

Updating package cl-drakma from 1.3.11 to 1.3.13.
     see logs in "//tmp/ql-to-deb/logs//cl-drakma.log"
Fetching ""
Checksum test passed.
     File: "/tmp/ql-to-deb/archives/drakma-1.3.13.tgz"
      md5: 3b548bce10728c7a058f19444c8477c3
Building package cl-drakma

Updating package cl-esrap from 20150113 to 20150302.
     see logs in "//tmp/ql-to-deb/logs//cl-esrap.log"
Fetching ""
Checksum test passed.
     File: "/tmp/ql-to-deb/archives/esrap-20150302-git.tgz"
      md5: 8b198d26c27afcd1e9ce320820b0e569
Building package cl-esrap

Updating package cl-graph from 20141106 to 20150407.
     see logs in "//tmp/ql-to-deb/logs//cl-graph.log"
Fetching ""
Checksum test passed.
     File: "/tmp/ql-to-deb/archives/graph-20150407-git.tgz"
      md5: 3894ef9262c0912378aa3b6e8861de79
Building package cl-graph

Updating package hunchentoot from 1.2.29 to 1.2.31.
     see logs in "//tmp/ql-to-deb/logs//hunchentoot.log"
Fetching ""
Checksum test passed.
     File: "/tmp/ql-to-deb/archives/hunchentoot-1.2.31.tgz"
      md5: 973eccfef87e81f1922424cb19884d63
Building package hunchentoot

Updating package cl-local-time from 20150113 to 20150407.
     see logs in "//tmp/ql-to-deb/logs//cl-local-time.log"
Fetching ""
Checksum test passed.
     File: "/tmp/ql-to-deb/archives/local-time-20150407-git.tgz"
      md5: 7be4a31d692f5862014426a53eb1e48e
Building package cl-local-time

Updating package cl-lparallel from 20141106 to 20150302.
     see logs in "//tmp/ql-to-deb/logs//cl-lparallel.log"
Fetching ""
Checksum test passed.
     File: "/tmp/ql-to-deb/archives/lparallel-20150302-git.tgz"
      md5: dbda879d0e3abb02a09b326e14fa665d
Building package cl-lparallel

Updating package cl-nibbles from 20141106 to 20150407.
     see logs in "//tmp/ql-to-deb/logs//cl-nibbles.log"
Fetching ""
Checksum test passed.
     File: "/tmp/ql-to-deb/archives/nibbles-20150407-git.tgz"
      md5: 2ffb26241a1b3f49d48d28e7a61b1ab1
Building package cl-nibbles

Updating package cl-qmynd from 20141217 to 20150302.
     see logs in "//tmp/ql-to-deb/logs//cl-qmynd.log"
Fetching ""
Checksum test passed.
     File: "/tmp/ql-to-deb/archives/qmynd-20150302-git.tgz"
      md5: b1cc35f90b0daeb9ba507fd4e1518882
Building package cl-qmynd

Updating package cl-trivial-backtrace from 20120909 to 20150407.
     see logs in "//tmp/ql-to-deb/logs//cl-trivial-backtrace.log"
Fetching ""
Checksum test passed.
     File: "/tmp/ql-to-deb/archives/trivial-backtrace-20150407-git.tgz"
      md5: 762b0acf757dc8a2a6812d2f0f2614d9
Building package cl-trivial-backtrace

Quite simple.

To be totally honnest, I first had a problem with the parser generator library esrap wherein the README documentation changed to be a file, and I had to tell my debian packaging about that. See the 0ef669579cf7c07280eae7fe6f61f1bd664d337e commit to ql-to-deb for details.

What about trying to install those packages locally? That's usually a very good test. Sometimes some dependencies are missing at the dpkg command line, so another apt-get install -f is needed:

$ /vagrant/build/bin/ql-to-deb install
sudo dpkg -i /tmp/ql-to-deb/cl-plus-ssl_20150302-1_all.deb /tmp/ql-to-deb/cl-csv_20150302-1_all.deb /tmp/ql-to-deb/cl-csv-clsql_20150302-1_all.deb /tmp/ql-to-deb/cl-csv-data-table_20150302-1_all.deb /tmp/ql-to-deb/cl-db3_20150302-1_all.deb /tmp/ql-to-deb/cl-drakma_1.3.13-1_all.deb /tmp/ql-to-deb/cl-esrap_20150302-1_all.deb /tmp/ql-to-deb/cl-graph_20150407-1_all.deb /tmp/ql-to-deb/cl-hunchentoot_1.2.31-1_all.deb /tmp/ql-to-deb/cl-local-time_20150407-1_all.deb /tmp/ql-to-deb/cl-lparallel_20150302-1_all.deb /tmp/ql-to-deb/cl-nibbles_20150407-1_all.deb /tmp/ql-to-deb/cl-qmynd_20150302-1_all.deb /tmp/ql-to-deb/cl-trivial-backtrace_20150407-1_all.deb
(Reading database ... 79689 files and directories currently installed.)
Preparing to unpack .../cl-plus-ssl_20150302-1_all.deb ...
Unpacking cl-plus-ssl (20150302-1) over (20140826-1) ...
Selecting previously unselected package cl-csv.
Preparing to unpack .../cl-csv_20150302-1_all.deb ...
Unpacking cl-csv (20150302-1) ...
Selecting previously unselected package cl-csv-clsql.
Preparing to unpack .../cl-csv-clsql_20150302-1_all.deb ...
Unpacking cl-csv-clsql (20150302-1) ...
Selecting previously unselected package cl-csv-data-table.
Preparing to unpack .../cl-csv-data-table_20150302-1_all.deb ...
Unpacking cl-csv-data-table (20150302-1) ...
Selecting previously unselected package cl-db3.
Preparing to unpack .../cl-db3_20150302-1_all.deb ...
Unpacking cl-db3 (20150302-1) ...
Preparing to unpack .../cl-drakma_1.3.13-1_all.deb ...
Unpacking cl-drakma (1.3.13-1) over (1.3.11-1) ...
Preparing to unpack .../cl-esrap_20150302-1_all.deb ...
Unpacking cl-esrap (20150302-1) over (20150113-1) ...
Preparing to unpack .../cl-graph_20150407-1_all.deb ...
Unpacking cl-graph (20150407-1) over (20141106-1) ...
Preparing to unpack .../cl-hunchentoot_1.2.31-1_all.deb ...
Unpacking cl-hunchentoot (1.2.31-1) over (1.2.29-1) ...
Preparing to unpack .../cl-local-time_20150407-1_all.deb ...
Unpacking cl-local-time (20150407-1) over (20150113-1) ...
Preparing to unpack .../cl-lparallel_20150302-1_all.deb ...
Unpacking cl-lparallel (20150302-1) over (20141106-1) ...
Preparing to unpack .../cl-nibbles_20150407-1_all.deb ...
Unpacking cl-nibbles (20150407-1) over (20141106-1) ...
Preparing to unpack .../cl-qmynd_20150302-1_all.deb ...
Unpacking cl-qmynd (20150302-1) over (20141217-1) ...
Preparing to unpack .../cl-trivial-backtrace_20150407-1_all.deb ...
Unpacking cl-trivial-backtrace (20150407-1) over (20120909-2) ...
Setting up cl-plus-ssl (20150302-1) ...
dpkg: dependency problems prevent configuration of cl-csv:
 cl-csv depends on cl-interpol; however:
  Package cl-interpol is not installed.

dpkg: error processing package cl-csv (--install):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of cl-csv-clsql:
 cl-csv-clsql depends on cl-csv; however:
  Package cl-csv is not configured yet.

dpkg: error processing package cl-csv-clsql (--install):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of cl-csv-data-table:
 cl-csv-data-table depends on cl-csv; however:
  Package cl-csv is not configured yet.

dpkg: error processing package cl-csv-data-table (--install):
 dependency problems - leaving unconfigured
Setting up cl-db3 (20150302-1) ...
Setting up cl-drakma (1.3.13-1) ...
Setting up cl-esrap (20150302-1) ...
Setting up cl-graph (20150407-1) ...
Setting up cl-local-time (20150407-1) ...
Setting up cl-lparallel (20150302-1) ...
Setting up cl-nibbles (20150407-1) ...
Setting up cl-qmynd (20150302-1) ...
Setting up cl-trivial-backtrace (20150407-1) ...
Setting up cl-hunchentoot (1.2.31-1) ...
Errors were encountered while processing:

Let's make sure that our sid users will be happy with the update here:

$ sudo apt-get install -f
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Correcting dependencies... Done
The following packages were automatically installed and are no longer required:
  g++-4.7 git git-man html2text libaugeas-ruby1.8 libbind9-80
  libclass-isa-perl libcurl3-gnutls libdns88 libdrm-nouveau1a
  libegl1-mesa-drivers libffi5 libgraphite3 libgssglue1 libisc84 libisccc80
  libisccfg82 liblcms1 liblwres80 libmpc2 libopenjpeg2 libopenvg1-mesa
  libpoppler19 librtmp0 libswitch-perl libtiff4 libwayland-egl1-mesa luatex
  openssh-blacklist openssh-blacklist-extra python-chardet python-debian
  python-magic python-pkg-resources python-six ttf-dejavu-core ttf-marvosym
Use 'apt-get autoremove' to remove them.
The following extra packages will be installed:
The following NEW packages will be installed:
0 upgraded, 1 newly installed, 0 to remove and 51 not upgraded.
3 not fully installed or removed.
Need to get 20.7 kB of archives.
After this operation, 135 kB of additional disk space will be used.
Do you want to continue? [Y/n] 
Get:1 sid/main cl-interpol all 0.2.1-2 [20.7 kB]
Fetched 20.7 kB in 0s (84.5 kB/s)
debconf: unable to initialize frontend: Dialog
debconf: (Dialog frontend will not work on a dumb terminal, an emacs shell buffer, or without a controlling terminal.)
debconf: falling back to frontend: Readline
Selecting previously unselected package cl-interpol.
(Reading database ... 79725 files and directories currently installed.)
Preparing to unpack .../cl-interpol_0.2.1-2_all.deb ...
Unpacking cl-interpol (0.2.1-2) ...
Setting up cl-interpol (0.2.1-2) ...
Setting up cl-csv (20150302-1) ...
Setting up cl-csv-clsql (20150302-1) ...
Setting up cl-csv-data-table (20150302-1) ...

All looks fine, time to sign those packages. There's a trick here, where you want to be sure you're using a GnuPG setup that allows you to enter your passphrase only once, see ql-to-deb vm setup for details, and the usual documentations about all that if you're interested into the details.

$ /vagrant/build/bin/ql-to-deb sign
 signfile /tmp/ql-to-deb/cl-plus-ssl_20150302-1.dsc 60B1CB4E
 signfile /tmp/ql-to-deb/cl-plus-ssl_20150302-1_amd64.changes 60B1CB4E
Successfully signed dsc and changes files
 signfile /tmp/ql-to-deb/cl-csv_20150302-1.dsc 60B1CB4E
 signfile /tmp/ql-to-deb/cl-csv_20150302-1_amd64.changes 60B1CB4E
Successfully signed dsc and changes files
 signfile /tmp/ql-to-deb/cl-db3_20150302-1.dsc 60B1CB4E
 signfile /tmp/ql-to-deb/cl-db3_20150302-1_amd64.changes 60B1CB4E
Successfully signed dsc and changes files
 signfile /tmp/ql-to-deb/cl-drakma_1.3.13-1.dsc 60B1CB4E
 signfile /tmp/ql-to-deb/cl-drakma_1.3.13-1_amd64.changes 60B1CB4E
Successfully signed dsc and changes files
 signfile /tmp/ql-to-deb/cl-esrap_20150302-1.dsc 60B1CB4E
 signfile /tmp/ql-to-deb/cl-esrap_20150302-1_amd64.changes 60B1CB4E
Successfully signed dsc and changes files
 signfile /tmp/ql-to-deb/cl-graph_20150407-1.dsc 60B1CB4E
 signfile /tmp/ql-to-deb/cl-graph_20150407-1_amd64.changes 60B1CB4E
Successfully signed dsc and changes files
 signfile /tmp/ql-to-deb/hunchentoot_1.2.31-1.dsc 60B1CB4E
 signfile /tmp/ql-to-deb/hunchentoot_1.2.31-1_amd64.changes 60B1CB4E
Successfully signed dsc and changes files
 signfile /tmp/ql-to-deb/cl-local-time_20150407-1.dsc 60B1CB4E
 signfile /tmp/ql-to-deb/cl-local-time_20150407-1_amd64.changes 60B1CB4E
Successfully signed dsc and changes files
 signfile /tmp/ql-to-deb/cl-lparallel_20150302-1.dsc 60B1CB4E
 signfile /tmp/ql-to-deb/cl-lparallel_20150302-1_amd64.changes 60B1CB4E
Successfully signed dsc and changes files
 signfile /tmp/ql-to-deb/cl-nibbles_20150407-1.dsc 60B1CB4E
 signfile /tmp/ql-to-deb/cl-nibbles_20150407-1_amd64.changes 60B1CB4E
Successfully signed dsc and changes files
 signfile /tmp/ql-to-deb/cl-qmynd_20150302-1.dsc 60B1CB4E
 signfile /tmp/ql-to-deb/cl-qmynd_20150302-1_amd64.changes 60B1CB4E
Successfully signed dsc and changes files
 signfile /tmp/ql-to-deb/cl-trivial-backtrace_20150407-1.dsc 60B1CB4E
 signfile /tmp/ql-to-deb/cl-trivial-backtrace_20150407-1_amd64.changes 60B1CB4E
Successfully signed dsc and changes files

Ok, with all tested and signed, it's time we upload our packages on debian servers for our dear debian users to be able to use newer and better versions of their beloved Common Lisp librairies:

$ /vagrant/build/bin/ql-to-deb upload
Trying to upload package to ftp-master (
Checking signature on .changes
gpg: Signature made Sat 02 May 2015 05:06:48 PM MSK using RSA key ID 60B1CB4E
gpg: Good signature from "Dimitri Fontaine <>"
Good signature on /tmp/ql-to-deb/cl-plus-ssl_20150302-1_amd64.changes.
Checking signature on .dsc
gpg: Signature made Sat 02 May 2015 05:06:46 PM MSK using RSA key ID 60B1CB4E
gpg: Good signature from "Dimitri Fontaine <>"
Good signature on /tmp/ql-to-deb/cl-plus-ssl_20150302-1.dsc.
Uploading to ftp-master (via ftp to
  Uploading cl-plus-ssl_20150302-1.dsc: done.
  Uploading cl-plus-ssl_20150302.orig.tar.gz: done.
  Uploading cl-plus-ssl_20150302-1.debian.tar.xz: done.
  Uploading cl-plus-ssl_20150302-1_all.deb: done.
  Uploading cl-plus-ssl_20150302-1_amd64.changes: done.
Successfully uploaded packages.

Of course the same text or abouts is then repeated for all the other packages.

Enjoy using Common Lisp in debian!

Oh and remember, the only reason I've written ql-to-deb and signed myself up to maintain those upteens Common Lisp librairies as debian package is to be able to properly package pgloader in debian, as you can see at and in particular in the Other Packages Related to pgloader section of the debian source package for pgloader at

That level of effort is done to ensure that we respect the Debian Social Contract wherein debian ensures its users that it's possible to rebuild anything from sources as found in the debian repositories.

Quicklisp newsA small step in the right direction: https for

· 26 days ago
I had a joke slide at ELS last week that explained why Quicklisp was so easy to install: just use curl | sudo sh.  (Don't try this.) Although Quicklisp's installation isn't as risky as piping random code into a root shell, it does have its own problems. Several people at the conference asked me when I would add more security features to Quicklisp.

As of this week, is available through an https connection. Any requests that come in over http are redirected to the equivalent https location. That means you can have some confidence that the information there is provided by me, rather than intercepted and replaced by a third party.

The main Quicklisp website is only part of the story. The software to install and use Quicklisp is hosted on another domain, That domain now has optional https access, so that any URL may be accessed either through https or http.

That means the bootstrap file quicklisp.lisp is available via https, and so is the PGP key I use to sign client software and dist metadata. (That key is also available via various PGP keyservers.) If you have programs that fetch quicklisp.lisp or software archives directly from, I encourage you to update them to use https instead of http.

Why doesn't use https exclusively? Unfortunately, the Quicklisp client code itself does not know how to connect via https, so turning off http access would break Quicklisp completely. It will take more time to update the Quicklisp client code to use https.

Implementing https for is a small, but important, first step toward making the use of Quicklisp safer. If you have any questions or concerns, please get in touch via

ECL NewsECL Quarterly - Volume I

· 26 days ago

ECL Quarterly - Volume I


Hello everyone!

From time to time there are misleading signals, that ECL is "floating dead". This FUD is mostly spread by IRC newcomers with little orientation, but it's good! This is a signal, that this particular implementation of Common Lisp needs to make a bit more noise, instead of silently fixing stuff (however it obviously needs a bit of work on stuff as well ;-)).

Some projects make new release each month to prevent such disinformation. It solves this particular problem, but introduces a new one - it's a bit fuzzy, if a new release introduces any significant improvements, or if it's just a release number bump. Yet, updating it requires recompilation of personal projects, which depending on machine might take a while and is surely a bit annoying.

This is how the ECL Quarterly idea was born. To show a bit activity from time to time - post will be published every three months. I want to make it an e-zine containing info about development, tutorials, comparisons, benchmarks and anything what is at least slightly related to ECL. Everyone is welcome to contribute - such material will also be published on wiki, added to git tree, and if appropriate - incorporated in documentation. If you have such material, don't hesitate to contact me at dkochmanski[at]turtle-solutions[dot]eu.

This chapter highlights:

  • Changes, development status etc.
  • Contributing to ECL

If you have any suggestions regarding ECL Quarterly, you like it, or maybe hate it - please tell me either by commenting this post, or writing an e-mail. Thank you!

Daniel Kochmański
Poznań, Poland
May 2015

Changes and development status

After the 15.3.7 release there are a few changes going on. We are now hosted at (however it would be nice to move to, just not now), a few wiki entries are added, official site is Domain is already bought (not configured properly yet).

Until now we have updated libraries that we depend on. Namely:

  • libffi to version 3.2.1,
  • asdf to version 3.1.4,
  • bdwgc to version 7.4.2.

There was also an update of GMP to more recent version, but we won't include it - yes, we are staying LGPLv2, to remain GPLv2 compatible. All changes were tested on Windows with MSVC2012.

For now we have also reworked the ROTATEF, SHIFTF and PSETF macros, to conform ANSI standard in regard to places (multiple values weren't held properly).

The experimental branch contains Android (as name suggests - experimental) port, which is preview only for now (this branch is LGPLv3, because included GMP enforces it, and doesn't build on Windows).

Loads of things are to be done, and we're slowly making progress. After all we won't change release versioning scheme. No ETA for next release, but I assure you - if you contribute, it will be sooner ;-). What leads us to the next part.

Contributing to ECL

Documentation, tutorials, wiki, others

You can contribute in numerous ways. One way is to code and fix bugs - and it's very important part. But equally important is to find bugs and report them, so developers can improve codebase. Feature requests are also welcome (however we are focused now on fixing stuff rather than adding functionality, so even good proposition might wait in queue behind something maybe less exciting).

Testing on various platform and architectures is essential. Thanks to Anton Vodonosov and cl-test-grid it is as easy as setting environment, tweaking two configuration files and invoking ./ Run may take a while (depending on computer) and is limited to operating systems and architectures supported by Clozure Common Lisp.

If ECL doesn't build, crashes, or works non-conforming to specification, please do report at It requires account on GitLab, but setting it up is free. I'm still struggling to produce some time and move all tickets from to above mentioned issue tracking site - volunteers are more then welcome to do it.

If you encounter problem, please write to mailing list. There are many kind souls there more then willing to help - and usually they do. On the other hand, if someone asks for help and you know the answer - act! :-)

Wiki is a place, where many resources are gathered. It is incomplete and barely usable, because I don't have time to improve it. If you successfully build ECL on Android - great! Please add page to wiki, so others may reproduce your work! Do you have some nifty idea, and you believe it is worth to keep it there - do it. See a typo? Bug? Outdated information? You know what to do! You spot some nice blog post about ECL? Please share with others - wiki is best place to do so. You did successful project using ECL? Share this information! All this, and so much more, may be done here:

You can also write something for ECL Quarterly (e-mail me at dkochmanski[at]turtle-solutions[dot]eu).

Source code contributions

Development takes place on git repository located at

If you want your code in Embeddable Common-Lisp project, please send a patch to mailing list with additional tag [PATCH] in subject. Generally we want to follow convention used by U-Boot development team (, which borrows a lot from Linux policy. Please read this guide, it's really worthwhile reading. If you submit a significant change, please report it in CHANGELOG located in top directory.

Basically, if you want to contribute to code, you have at least two choices. You may improve C code (which is probably less interesting for lispers). Most of the sources are written in lisp however, and require no knowledge about C. Problems vary from fairly easy even for seasoned developer to hard conceptual riddles, so everyone can find something interesting for himself.. Please consult appropriate directories under src/ sub-directory (i.e. src/lsp, src/clos etc.) - it's pure lisp! And it's fun to hack. Improving both C and Lisp sources might be a great learning experience. To figure what's wrong requires often getting your hands dirty, and then cleaning proposed solution. This, connected with peer review, might be a next step to become a better programmer.

There is also a third part, which is tiresome (for me at least) - improving build system - it is buggy and inconsistent. First person who will fix this has granted a free dinner when we meet in person. Remember however, that we support many operating systems, so it might be tricky to do it properly without introducing new problems.

If you are a library or application developer, please test against as many implementations as possible - its hard, it takes time, but in my humble opinion it is essential for CL ecosystem. Each implementation has it's weak and strong sides, and you never know, when you'll need one, or who and in what purpose is using your code :-).

Quicklisp newsDealing with "redundant" libraries

· 27 days ago
People sometimes submit libraries to Quicklisp that have significant functional overlap with other libraries. When someone wants to add a new library for functionality that is well-covered by other libraries, I don't always add it right away. There are a few questions I ask first.

First, are you aware that there are many other libraries that fit a similar need? If not, is it possible to use one of those instead? It is possible that an existing library is more complete and mature than a new library. And adding a new library can make it harder for someone else to choose a good option.

If you're aware of other libraries, is it possible that the essential new functionality your library provides can be incorporated into an existing library? 

If you're aware of other libraries, but still feel you need a new one, and it can't be incorporated into an existing library, I'll go ahead and add the library. 

Here are a few recent examples of that process playing out:
I don't reject libraries for lack of novelty. It's always possible that a new library becomes so clearly superior to all other options that it is the go-to library of the future. But it's best when that happens because you're aware of the existing options (and their strengths and limitations) rather than ignorant of them.

Zach BeaneCommon Lisp and Docker

· 27 days ago

Florian Margaine wrote up a page about using Common Lisp and Docker. (via reddit)

Zach BeaneEdi Weitz is writing a Common Lisp book

· 28 days ago

This year marks the 10 year anniversary of Apress's last Common Lisp book, Practical Common Lisp. Edi Weitz, who with cl-ppcre and many other libraries helped support the CL resurgence of the 2000s, is working on a new Common Lisp book for Apress. It will be a cookbook-style book in their "Recipes" series. Part of it will be about useful open source libraries, ASDF, and Quicklisp.

You can see very preliminary preorder pages at Springer and Amazon.

I'm looking forward to it!

drmeisterHow C++ interoperation works in Clasp "under the hood"

· 28 days ago
A “core::Functoid” in Clasp is a base class for an object that can be called from Common Lisp. It implements a method that is the calling convention from Common Lisp. It can wrap an environment and whatever it needs to call some code.
It is the base class of core::Closure which also wraps an environment.
I have core::InterpretedClosure that also wraps a List_sp which is an S-expression that is walked to interpret it.
I have CompiledClosure that wraps an LLVM function pointer that can be called.
I have BuiltInClosure that wraps a pointer to a C++ function that can be called.
There are also VariadicMethoid objects that call C++ class instance methods with different numbers of arguments.
In many cases these classes are generated at C++ compile time using template code that generates everything needed to convert Common Lisp types to C++ types and back again.  All that needs to be specified to expose a C++ function to Clasp Common Lisp is a string that becomes the name of the symbol that binds the C++ function and a pointer to the C++ function.  Since Common Lisp types in Clasp are all implemented as C++ types the overhead of these conversions should be pretty low. You can write from_object and to_object (template classes) translators that do the translation back and forth.

drmeisterAn update on Clasp

· 28 days ago

I’ve been really busy incorporating a new compiler into Clasp to eventually allow it to generate performant code. My goal is code that runs as fast as the best Common Lisp compilers out there (I’m looking at you Steel Bank Common Lisp! :-)).

I’m also incorporating a pointer tagging scheme within Clasp so that FIXNUM, CHARACTER, SHORT-FLOAT (32bit IEEE float) and SINGLE-FLOAT (a hacked 59bit pseudo double-precision representation) are all immediate values.  CONS cells will have their own tag as well to make iteration over Common Lisp LISTs as fast as possible.

Stay tuned.

Quicklisp newsNew feature: Quicklisp library bundles

· 29 days ago
Quicklisp library bundles are self-contained sets of systems that are exported from Quicklisp and loadable without involving Quicklisp.

I added the feature to the Quicklisp client on April 18th and announced it at ELS on the 20th. To get it, use (ql:update-client). It will be available when you restart for the next session.

I've wanted to provide this feature since the beginning of Quicklisp. I primarily pictured this as a kind of delivery tool, where your project should have access to a specific set of supporting libraries without the complexity of Quicklisp loaded in as well.

The interface is pretty simple: (ql:bundle-systems '("foo" "bar" "baz") :to "my-bundle/") will produce a file named "my-bundle/bundle.lisp" that, when loaded, will make "foo", "bar", and "baz" accessible via ASDF without involving Quicklisp at all. All the libraries on which "foo", "bar", and "baz" depend are also included in the bundle, recursively.

The bundle can be relocated without any issues. All its pathnames and indexes are relative to its bundle.lisp.

When bundle.lisp is loaded, the systems in the bundle take precedence over all other ASDF systems. Multiple bundles can be loaded at the same time; the most recently loaded one has the highest precedence. And a bundle can be loaded more than once. If loaded again, it will be moved to the top of the precedence list again.

Bundles also have a local-projects directory that adds some of the automagic from the Quicklisp local-projects feature. Bundle local-projects systems take precedence over the bundle's "built-in" systems.

Quicklisp library bundles are also documented! But they are only lightly tested. If you think library bundles might help you solve a problem, please give them a try and let me know if you have any problems or questions.

ABCL Devabcl-1.3.2 released

· 29 days ago
While basking in the lovely London weather and thoroughly enjoying last week's 8th European Lisp Symposium, the Bear managed to slough off a much needed spring cleaning maintenance release in the form of abcl-1.3.2.

The full description of changes can be found in <>.

Zach BeaneThe 8th European Lisp Symposium, 2015

· 29 days ago

The ELS last week was fantastic. Nicolas Hafner's writeup is a good and detailed rundown of the event. I'd like to talk about a few of the things that stood out to me from my perspective.

The attendance was great. 89 official registrants made for a good crowd, even without many of the familiar faces I've seen at European Lisp events in the past. I suspect the unfortunate cancellation of ECLM "helped" in this regard. I also talked to a few local Londoners who were at the conference mostly because it was so close. London: hotbed of the Lisp-curious!

89 isn't a lot of people in an absolute sense, but it was a vigorous and engaged group. I met many new people and enjoyed hearing about their interest in Lisp.

It was an honor to be an invited speaker. I gave the opening talk, "Quicklisp: On Beyond Beta". (The subtitle is inspired by a book I've had to read about 100 times, so far.) The talk is in two parts: a retrospective on some of the trends and changes in Quicklisp and Common Lisp over the past five years, and what I want to do to drop "beta" from Quicklisp. If you'd like to see the slides and the script of the talk, I've posted them to github. The talk was recorded, but I'm not sure how or when the video will be made available.

One of the missing features described in my talk, library bundles, is now available in the Quicklisp client. I'm going to write more about it on the Quicklisp blog soon. If you'd like to try library bundles, make sure you're using the latest client via (ql:update-client).

There were some things I didn't get to in the talk. 

I didn't talk about security changes for Quicklisp, partly because I'm not completely sure what form they will take. I do intend to offer https access to and the Quicklisp software archives. I also intend to integrate cryptographic signature checking into the client.

There wasn't enough time to process my raw data for what the approximate "market share" of CL implementations over time. SBCL dominates, but I think the percentages and proportions will be interesting to chart.

And I talked about a few new contributors, but of course there are many new contributors, including eudoxia0, orthecreedenceguicho271828, and more.

Dave Cooper's demonstration of gendl has evolved. I last saw it in Amsterdam in 2011, and I remember it mostly as a "look, but don't touch" demo. At this ELS, he was able to get people up and running with the latest Gendl with just one Quicklisp command, and from my view in the back row I could see people starting up Gendl and trying his exercises as he ran through them. Out of the dozens of people who tried it out, only one or two people had problems getting it running. The vast majority were able to try a complex project almost instantly. It felt good to have a hand in making it that easy.

I heard "Thanks for Quicklisp!" a dozen times, and it never got old. It's one of the things that keeps me energized. People are deriving real benefit from what Quicklisp does and aren't shy about telling me.

My web of trust expanded when Paul van der Walt proposed, and Christophe Rhodes and others helped execute, a keysigning party. I now have several more signatures on my Quicklisp release signing key.

Baggers' CEPL demo was a lot of fun to see, and I can't wait to try it out myself. It's going to be fun impressing my kids with some simple code producing pretty graphics.

It was also fun to hang out with Lispers before, after, and between the scheduled events. Nick Levine proposed a pre-conference dinner that ballooned to more than 40 attendees, maxing out the back room of a Vietnamese restaurant. The Mercure hotel was home base for many conference-goers, and there were a few late nights in the lounge where we gathered and talked about a wide range of topics, Lispy and otherwise. There were lunches and dinners for meeting new friends and catching up with old.

The weather was fantastic. Spring in London is about three weeks ahead of Maine. The sun shone and it was almost a pity that we couldn't hold some of the talks outside on the green. It was a joy to walk around the city before and after the conference, sightseeing at all the tourist traps and taking in even just a narrow impression of a city many centuries older than my home.

ELS was a blast. Although I'm still physically recovering from the conference and the travel, it has given me new energy for contributing to the Common Lisp community. A huge thanks to everyone involved with staging it, and to everyone who came up to me and said hello. I can't wait for the next ELS!

Paul KhuongPointer-less Scapegoat Trees

· 30 days ago

I’m trying something new this week: gathering a small group after work for 90 minutes of short talks and discussions. We’ll also have one longer slot because not everything fits in a postcard, but my main goal is really to create opportunities for everyone to infect us with their excitement for and interest in an idea or a question. I successfully encouraged a couple people to present, although many seemed intimidated by the notion... perhaps because we have grown to expect well researched and rehearsed performances. However, I believe that simple presentations of preliminary work are worthwhile, and probably more likely to spark fresh conversations than the usual polished fare: it’s healthy to expose our doubts, trials, and errors, and there’s certainly value in reminding ourselves that everyone else is in that same boat.

Here’s what I quickly (so quickly that my phone failed to focus correctly) put together on embedding search trees in sorted arrays. You’ll note that the “slides” are very low tech; hopefully, more people will contribute their own style to the potluck next time (:

I didn’t really think about implementing search trees until 3-4 years ago. I met an online collaborator in Paris who, after a couple G&T, brought up the topic of “desert island” data structures: if you were stuck with a computer and a system programming guide on a desert island, how would you rebuild a standard library from scratch? Most data structures and algorithms that we use every day are fairly easy to remember, especially if we don’t care about proofs of performance: basic dynamic memory allocation, hash tables, sorting, not-so-bignum arithmetic, etc. are all straightforward. He even had a mergeable priority queue, with skew heaps. However, we both got stuck on balanced search trees: why would anyone want to remember rotation rules? (Tries were rejected on what I argue are purely theoretical grounds ;)

I love searching in sorted arrays, so I kept looking for a way to build simpler search trees on top of that. That lead me to Bentley and Saxe’s (PDF) dynamisation trick. The gist of it is that there’s a family of methods to build dynamic sets on top of static versions. For sorted arrays, one extreme is an unsorted list with fast inserts and slow reads, and the other exactly one sorted array, with slow inserts and fast lookups. The most interesting design point lies in the middle, with \( \log n \) sorted arrays, yielding \( \mathcal{O}(\lg n) \) time inserts and \( \mathcal{O}(\lg\sp{2}n) \) lookups; we can see that design in write-optimised databases. The problem is that my workloads tend to be read heavy.

Some time later, I revisited a paper by Brodal, Fagerberg, and Jacob (PDF). They do a lot of clever things to get interesting performance bounds, but I’m really not convinced it’s all worth the complexity1... especially in the context of our desert island challenge. I did find one trick very interesting: they preserve logarithmic time lookups when binary searching arrays with missing values by recasting these arrays as implicit binary trees and guaranteeing that “NULLs” never have valid entries as descendants. That’s a lot simpler than other arguments based on guaranteeing a minimum density. It’s so much simpler that we can easily make it work with a branch-free binary search: we only need to treat NULLs as \( \pm \infty \) (depending on whether we want a predecessor or a successor).

While lookups are logarithmic time, inserts are \(\mathcal{O}(\lg\sp{2} n) \) time. Still no satisfying answer to the desert island challenge.

I went back to my real research in optimisation, and somehow stumbled on Igal Galperin’s PhD thesis on both on-line optimisation/learning and... simpler balanced binary search trees!

Scapegoat trees (PDF) rebalance by guaranteeing a bound \( \alpha > 0 \) on the relative difference between the optimal depth (\( \lceil\lg n\rceil \)) for a set of \(n\) values and the height (maximal depth) of the balanced tree (at most \( (1+\alpha)\lceil\lg n\rceil \)). The only property that a scapegoat tree has (in addition to those of binary search trees) is this bound on the height of the tree, as a function of its size. Whenever a new node would be inserted at a level too deep for the size of the tree, we go up its ancestors to find a subtree that is small enough to accomodate the newcomer and rebuild it from scratch. I will try to provide an intuition of how they work, but the paper is a much better source.

For a tree of \(n = 14\) elements, we could have \(\alpha = 0.25\), for a maximum depth of \(1.25 \lceil\lg 14\rceil = 5\). Let’s say we attempt to insert a new value, but the tree is structured such that the value would be the child of a leaf that’s already at depth \(5\); we’d violate the (im)balance bound. Instead, we go up until we find an ancestor \(A\) at depth, e.g., \(3\) with \(4\) descendants. The ancestor is shallow enough that it has space for \(5 - 3 = 2\) levels of descendants, for a total height of \(2 + 1 = 3\) for the subtree. A full binary tree of height \(3\) has \(2\sp{3} - 1 = 7\) nodes, and we thus have enough space for \(A\), its \(4\) descendants, and the new node! These 6 values are rebuilt in a near-perfect binary tree: every level must be fully populated, except for the last one.

The criteria to find the scapegoat subtree are a bit annoying to remember–especially given that we don’t want to constantly rebuild the whole tree–but definitely simpler than rotation rules. I feel like that finally solves the desert island balanced search tree challenge... but we still have gapped sorted arrays to address.

What’s interesting about scapegoat trees is that rebalancing is always localised to a subtree. Rotating without explicit pointers is hard (not impossible, amazingly enough), but scapegoat trees just reconstruct the whole subtree, i.e., a contiguous section of the sorted array. That’s easy: slide non-empty values to the right, and redistribute recursively. But, again, finding the scapegoat subtree is annoying.

The \(\alpha\lg (n)\) above should read \((1 + \alpha)\lg n\), and \(\lg\lg n + \mathrm{Exp}\cdot\lg n\) should be \((\lg\lg n) (1 + \mathrm{Exp})\).

That made me think: what if I randomised scapegoat selection? Rather than counting elements in subtrees, I could approximate that probabilistically by sampling from an exponential distribution... which we can easily approximate with the geometric for \(p = 0.5\) by counting leading zeros in bitstrings.

I’m still not totally convinced that it works, but I vaguely remember successfully testing an implementation and sketching a proof that we can find the scapegoat subtree by going up according to a scaled geometric to preserve amortised logarithmic time inserts. The probability function decreases quickly enough that we preserve logarithmic time inserts on average, yet slowly enough that we can expect to redistribute a region before it runs out of space.

The argument is convoluted, but the general idea is based on the observation that, in a tree of maximum height \(m\), a subtree at depth \(k\) can contain at most \(n\sp\prime = 2\sp{m - k + 1} - 1\) elements (including the subtree’s root).

We only violate the imbalance bound in a subtree if we attempt to insert more than \(n\sp\prime\) elements in it. Rebalancing works by designating the shallowest subtree that’s not yet full as the scapegoat. We could simplify the selection of the scapegoat tree by counting the number of inserts in each subtree, but that’d waste a lot of space. Instead, we count probabilistically and ensure that there’s a high probability (that’s why we always go up by at least \(\lg \lg n\) levels) that each subtree will be rebalanced at least once before it hits its insertion count limit. The memoryless property of the geometric distribution means that this works even after a rebalance. If we eventually fail to find space, it’s time to completely rebuild the subtree; this case happens rarely enough (\(p \approx \frac{\lg n}{n}\)) that the amortised time for insertions is still logarithmic.

Again \(2\sp{\alpha \lg n}\) should be \(2\sp{(1 + \alpha)\lg n}\).

We can do the same thing when embedding scapegoat trees in implicit trees. The problem is that a multiplicative overhead in depth results in an exponential space blowup. The upside is that the overhead is tunable: we can use less space at the expense of slowing down inserts.

In fact, if we let \( \alpha \rightarrow 0 \), we find Brodal et al’s scheme (I don’t know why they didn’t just cite Galperin and Rivest on scapegoat trees)! The difference is that we are now pretty sure that we can easily let a random number generator guide our redistribution.

I only covered insertions and lookups so far. It turns out that deletions in scapegoat trees are easy: replace the deleted node with one of its leaves. Deletions should also eventually trigger a full rebalance to guarantee logarithmic time lookups.

Classical implicit representations for sorted sets make us choose between appallingly slow (linear time) inserts and slow lookups. With stochastic scapegoat trees embedded in implicit binary trees, we get logarithmic time lookups, and we have a continuum of choices between wasting an exponential amount of space and slow \( \mathcal{O}(\lg\sp{2} n) \) inserts. In order to get there, we had to break one rule: we allowed ourselves \(\mathcal{O}(n)\) additional space, rather than \(\mathcal{o}(n)\), but it’s all empty space.

What other rule or assumption can we challenge (while staying true to the spirit of searching in arrays)?

I’ve been thinking about interpolation lately: what if we had a monotone (not necessarily injective) function to map from the set’s domain to machine integers? That’d let us bucket values or interpolate to skip the first iterations of the search. If we can also assume that the keys are uniformly distributed once mapped to integers, we can use a linear Robin Hood hash table: with a linear (but small) space overhead, we get constant time expected inserts and lookups, and what seems to be \( O(\lg \lg n) \) worst case2 lookups with high probability.

Something else is bothering me. We embed in full binary trees, and thus binary search over arrays of size \(2\sp{n} - 1\)... and we know that’s a bad idea. We could switch to ternary trees, but that means inserts and deletes must round to the next power of three. Regular div-by-mul and scaling back up by the divisor always works; is there a simpler way to round to a power of three or to find the remainder by such a number?

I don’t know! Can anyone offer insights or suggest new paths to explore?

  1. I think jumping the van Emde Boa[s] is a thing, but they at least went for the minor version, the van Emde Boas layout ;)

  2. The maximal distance between the interpolation point and the actual location appears to scale logarithmically with the number of elements. We perform a binary search over a logarithmic-size range, treating empty entries as \(\infty\).

LispjobsCommon Lisp Web Developer, Somewrite, Tokyo or remote

· 33 days ago

We’re looking for Common Lisp web developers. The number of positions available is 2 at most (for the current phase).

## About Us

Somewrite is located in Tokyo, Japan. We have an office in Aoyama, however, no programmers are working at there. Working at home, pushing commits and reviewing on GitHub. We talk via Slack usually, and via Google Hangouts once in a week.

## What We Do

* Advertising delivery
* Recommendation engine for ads
* Internal admin pages

There’re a lot of technical challenges. The applications must be fast and scalable.

## Technologies We Use

* Caveman2
* Integral
* Woo
* Roswell
* Qlot
* React.js
* Ansible
* AWS EC2, S3, RDS and ELB

## Must

* Experience of development in Common Lisp
* Experience of web application development with a certain web application framework (not necessary in Common Lisp)
* Basic knowledges of \*nix OS and RDBMS
* English or Japanese

## Preferable

* Experience of web application development in Common Lisp
* High-performance Common Lisp development
* High-traffic website experience
* Rich UI development with JavaScript
* Basic knowledges about algorithm and various data structures

Send CV and a Cover Letter to if you’re interested.

Nicolas Hafner8th European Lisp Symposium - Confession 53

· 34 days ago

I'm currently sitting in a lecture hall at the ETH in Zürich. It's 8 AM9 in the morning, and despite having had a long night's sleep, I'm still quite tired. It's amazing what two days of just listening and talking can do to you. It also feels so much longer than that, just because of all the things that happened. I suppose I should start from the beginning though.

The European Lisp Symposium is an annual conference organised by fellow Lispers. This year it took place at the Goldsmiths university of London from the 20th to the 21st of April and featured two keynotes1, twelve talks, and thirteen lightning talks. Aside from the symposium's talks, there was also a lot of discussion and chatter during the coffee breaks and even at the end of the days, long into the nights. With a new record of 89 registrants, there were a lot of people to meet and talk to.

When I decided to take part, it was mostly in order to meet the people I knew from Freenode's #lisp channel, but I was very pleasantly surprised to find that the various talks too turned out to be very interesting to me, even opening new ways to solve existing problems in my projects2. Of the people I've met, everyone was nice, interesting, and fun to talk to. I spent the most time with Robert Strandh (beach), Christian Schafmeister (drmeister), and Masatoshi Sano (@snmsts), but I would have loved to speak more with others as well, if only there had been more time to do so. Hopefully I'll be able to join again next year and have a chance to do so then.

My journey began on Sunday afternoon, flying to London. The airport was quite crowded and the flight fully booked out, crying children and babies included. Though the amount of people for the flight was not altogether surprising given that it departed at acceptable hours and was just at the beginning of the school holidays in Zürich. Regardless, the flight went well thanks to being able to drown out the noise with headphones. Arriving in Luton, the next challenge was to find my way through London to Greenwich, where my hotel was located. It turns out that Google Maps does not plan the best routes through the city, as it took me through districts I had no idea about, and I had to wander about aimlessly in the night more than once before reaching my destination. As I would learn on my trip back home, it's much better to ask the clerks at the railway stations for directions.

I arrived at the hotel around 9 'o clock local time, which was unfortunately too late to join the pre-ELS dinner that had been arranged. Though with over forty people, it would probably not have been very enjoyable to me to begin with. I had other things on my plate anyway. Apparently my booking (through did not go into Mercure's systems, so they had to arrange something for me on the fly. Fortunately that was solved without a hitch, so after a quarter of an hour of standing around at the reception I was finally allowed into my freezing cold air-conditioned hotel room. Eager to meet people, I left my room again soon after and tried to lure whoever I could get into the hotel's bar by offering chocolate on the mailing list.

After waiting for a very brief while, I met a German guy3 and we talked about all sorts of interesting things. Turns out he's sneaking Common Lisp into high-performance computing. Later we were joined by Christian Schafmeister, who had just arrived after a long plane ride, and the discussion turned to Clasp, LLVM, and I forgot what all else we talked about until after midnight.

The next morning I woke up way too early, even escaping my phone's alarm. I made my way through the streets over to Goldsmiths, grabbing a croissant on the way. The weather was very nice; blue skies all over, and a nicely cool temperature to boot. I couldn't have asked for anything better. Finding my way through the campus I was surprised to find that a bunch of people had already arrived before me. I picked up my badge4 and sat down to wait for everyone to show up.

The first keynote was lead by Zach Beane and showed a really nice overview of what happened in the five years of Quicklisp's existence, and gave a taste of all the things to come in the future. I was very surprised and humbled by the brief shout-out he gave to me for my library contributions. I wanted to speak with Zach about a few plans5 regarding dists and versioning in Quicklisp later on, but I never got the chance to do so, unfortunately.

After a brief coffee break followed the first session of talks of which I most remember the Racket-powered computer vision and the lisp-backed visual data-flow system. There were a surprising number of Racket-related talks overall, suggesting to me that I really should invest some time some day soon to take a good look at it. I'm not quite sure what to think of the visual data-flow system, it seems really slow and inconvenient to work with, even if it offers a nice way to write automatically parallelised programs. I don't remember much about the last talk about Processing in Racket, which I'm really sorry about.

For the lunch break I remained in the building and spent the time talking to Robert Strandh, his wife6, and Christian Schafmeister. I'm not sure why, but for the entire time that I was in London I never felt hungry, so I barely ate anything and still always had the same amount of energy as I always do. It'd be neat if that could continue on for a while longer, to be honest.

After lunch we had a change of plans, due to the second keynote being rescheduled for the next day. What followed in its place was the second session of talks, which included a very interesting one about executable pseudo-code. Using this system (composed of a couple of CL macros), translating pseudo-code from textbooks to similar-looking, but actually executable code, became trivial and even rivalled the speed of optimised C++ implementations thereof for a specific example. The group is now testing the same for more algorithms, to see if this holds true. Exciting! We also heard about a Racket based system of language-generating specifications in order to allow for a better system to constrain an application's permissions in situations like that of Android, and we heard about a new algorithm to implement fast processing of lists in reverse order, using the stack for an implicit reversing operation.

A second coffee break with cookies ensured, followed by another Keynote talk, this time from a Googler at the ITA-Software group, speaking about unwanted memory retention despite garbage collection. He spoke about a long journey through the madness of debugging GC, with the end-result being that -if I understood correctly- the problem didn't lie in the GC at all, but instead in the way mmaped resources weren't being properly cleaned up by hand. Oh dear!

Closing off the first day we had a round of lightning talks, where I too took part and raced through my presentation about Qtools. We also heard about asynchronous hash-table operations, a mobile game engine using MOCL, OpenCV interaction from CL, an Erlang-like system for CL, and using Common Lisp in high-performance computing.

I had invited Christopher Hurley (Mithent) over for the conference banquet, and he luckily managed to make it fine, so I spent a large part of the remaining evening talking with him. It was really nice to finally meet in person again, if only we didn't live so far apart we could have that opportunity more often. Later, Masatoshi Sano joined us at the table and for a long while we spoke about the various cultural and lingual challenges involved in learning a new language. I was too embarrassed to try to say anything in Japanese to him, my mind completely locked up when I tried to form a sentence. I clearly still have a long, long way to go! By comparison, his English was immaculate, especially once he started to feel more comfortable talking to us.

After the banquet I once again hung around the hotel bar with a bunch of lispers, talking about this and that, but mostly compilers. I had to excuse myself around midnight, since I didn't want to be exhausted for the next day.

We started into the morning with an introduction to Gendl, a system that engineers use to build models for complex machinery. Apparently it has a long history and is mostly used in the aircraft industry. Unfortunately we didn't have time to get into any more involved stuff with the system, but what we did get was nonetheless a very interesting way to build and compose models using Common Lisp.

Following the subsequent coffee break we had a talk about Lambdatalk, a lisp-like extensible markup system, that reminded me a lot of my FuncEM project from back when I was still clueless about lisp. It was unfortunately also rather clearly apparent to me that the author didn't have much experience as a web-designer. The previews and examples he showed were stuffed with the kind of design I did when I first started out. Stuffed with shadows, gradients, and all sorts of other effects that don't do anything but distract from the important things. Anyway, before I go off on another rant about bad design, I'll move on to the second talk, which was about a symbolic pattern-matching system in Clojure. I was immediately reminded of the chapters about that in PAIP, which I should really pick up again soon. The main motivation behind this kind of system was the hope of better engaging students for the author's CS course. I myself would definitely be interested! We then had a talk about various data structures optimised for fast persistent access, which are currently used for Franz' AllegroGraph database.

My lunch break was once again spent talking to Robert Strandh about various things, this time less Lisp related, and more about general politics, ethics, and all the various hard problems that are fun to complain about, but almost insurmountably difficult to do anything about.

The afternoon was the highlight of the entire symposium. We had absolutely amazing talks, most notably Christian Schafmeister's about Clasp and his struggles of writing a C++-interoperating Common Lisp implementation in order to build gigantic molecules, Robert Strandh's first-class global environments that allow for a clean bootstrapping environment in CL, Eitaro Fukamachi's Woo beating node.js in HTTP server benchmarks and now shooting for the stars by aiming to be the fastest HTTP server ever, Miroslav Urbanek using CL in high-performance computing to crunch numbers for quantum physics simulations, and finally Chris Bagley introducing a modern approach to writing and experimenting with OpenGL comfortably in CL. Now I'm noticing that I put all the talks in the 'most notably' listing, though I think that is well-deserved.7

But the excitement wasn't over yet for me, as I had another lightning talk to do. Since I knew I had a lot to say on Radiance, even if I did cut it down to a minimum already, I had to ramp up my talking speed to eleven and raced through it as quickly as I could. I hope people managed to follow along regardless! The rest of the lightning talks were about lisp job hiring at RavenPack, information about the Common Lisp Foundation, an update on the status and plans for the project, a tool to quickly install and set up CL implementations, and closing off with physics simulations for chocolate.

While the symposium had ended, the journey wasn't over quite yet. I spent the rest of the evening going for a drink with a couple of folks (beach, drmeister, and splittist were there too), where they gave me valuable advice on how to schedule my work. I left them around eight, as I was getting a headache and wanted to head back before it got dark. After relaxing in my hotel room for a brief while and swallowing a pain-killer, I felt well enough again to head back down to the bar. A couple of people once again gathered, and probably talked late into the night. I had to leave them early, even though there wasn't anything that I wanted to do more than stay and talk to them. I was too anxious about oversleeping and messing things up with my journey back home in the morning, so I had to go to bed on time.

Fortunately my alarm clock did its job proper; still tired I beat myself out of bed, did my packing, and checked out. I then set out for Greenwich Station, which confused me a lot at first, as there was a front entrance that didn't have any clerks, only ticket machines that didn't take my 50£. After wandering about worried for a good while I found the main entrance, and a very nice clerk printed out a good travel-route for me. Thanks to that, my journey to Luton was very comfortable and easy, with the only hiccup being a delay in the Tube line due to some clog up in the system somewhere. So I arrived at Luton about two hours too early. I spent my time there drinking a hot chocolate and paying five pounds for their WiFi. Getting onto the plane went by very quickly, and I'm quite sure the plane wasn't even half-full by the end. There was quite a bit of turbulence during the flight though, so my sketch didn't go as well as the ones from the flight over, though even those weren't great to begin with. Oh well!

I arrived at Zürich airport in the afternoon, euphoric about having successfully undergone such a wild journey, but also still dead tired from travelling, listening, and talking so much. I originally wanted to do post-recordings of my lightning talks to put on Youtube still8, but I just didn't have the energy to. I couldn't even get myself to stay up until midnight as I usually do, so I just called it an early night. And here we are already!

In conclusion, it was an absolute blast. I really hope that I can do it again next year, but depending on university and similar circumstances, it might not be as easily possible as it was in this case. A tremendous "Thank you!" goes to everyone who attended, and especially those who took the time to write a talk and organise the event. I'm also extremely thankful for all the people I had the chance to speak to personally; I enjoyed every minute of it.

Now that this is all over, I have to focus all the more on university, so that I may pass the coming exams in summer. Due to this I'll also most likely have to heavily tune down the amount of work I can spend on my lisp projects, maybe drop it altogether for a while. Still, if you have anything you'd be interested in knowing or speaking to me about, I'll be available. Send me a mail, hit me up on twitter, or preferably find me on Freenode's #lisp IRC channel.

Edit: Zach Beane also wrote a nice article about his ELS experience:

[1] Originally three, though one was cancelled due to unfortunate illness. Get well soon, Bodil Stokke!

[2] Mostly Chris Bagley's CEPL, which I hope to use to implement Parasol's shaders with, but Eitaro Fukamachi's talk about Woo also reminded me to finish off the Radiance driver for it, and probably switch to it in production soon.

[3] Whose name escapes me, I'm so sorry! I'm awful at remembering names!

[4] Which were very stylish. The only mishap was that they didn't include a field for the IRC nickname or twitter username, and printed the name a tad too small, so you had to squint to read it from afar. Hopefully that'll be corrected for the next one.

[5] Mostly I'm interested in adding GIT capabilities to Quicklisp and allowing some kind of 'version fluidity', analogous to allowing certain systems to be upgraded, while keeping others in place.

[6] I don't think I ever caught her name, but if I did, I must have forgotten again. As I said, I am terrible with names and am very sorry about that. Edit: I've been helpfully informed that her first name is Kathleen.

[7] The videos are going to be put up in a couple of weeks, so that you may experience the excitement as well if you couldn't make it to the conference.

[8] I'll do that later today and link it here

[9] Now that I'm done writing, which is almost all I did for the time, it's 12 'o clock. If only writing didn't take that much time to do, I'd do it oh so more often!


Christophe Rhodesels2015 it happened

· 34 days ago

Oh boy.

It turns out that organizing a conference is a lot of work. Who'd have thought? And it's a lot of work even after accounting for the benefits of an institutional Conference Services division, who managed things that only crossed my mind very late: signage, extra supplies for college catering outlets - the kinds of things that are almost unnoticeable if they're present, but whose absence would cause real problems. Thanks to Julian Padget, who ran the programme, and Didier Verna, who handled backend-financials and the website; but even after all that there were still a good number of things I didn't manage to delegate - visa invitation letters, requests for sponsorship, printing proceedings, attempting to find a last-minute solution for recording talks after being reminded of it on the Internet somewhere... I'm sure there is more (e.g. overly-restrictive campus WiFi, blocking outbound ssh and TLS-enabled IMAP) but it's beginning to fade into a bit of a blur. (An enormous "thank you" to Richard Lewis for stepping in to handle recording the talks as best he could at very short notice).

And the badges! People said nice things about the badges on twitter, but... I used largely the same code for the ILC held in Cambridge in 2007, and the comment passed back to me then was that while the badges were clearly going to become collectors' items, they failed in the primary purpose of a badge at a technical conference, which is to give to the introvert with poor facial recognition some kind of clue who they are talking to: the font size for the name was too small. Inevitably, I got round to doing the badges at the last minute, and between finding the code to generate PDFs of badges (I'd lost my local copy, but the Internet had one), finding a supplier for double-sided sheets of 10 85x54mm business cards, and fighting with the office printer (which insisted it had run out of toner) the thought of modifying the code beyond the strictly necessary didn't cross my mind. Since I asked for feedback in the closing session, it was completely fair for a couple of delegates to say that the badges could have been better in this respect, so in partial mitigation I offer a slightly cleaned-up and adjusted version of the badge code with the same basic design but larger names: here you go (sample output). (Another obvious improvement suggested to me at dinner on Tuesday: print a list of delegate names and affiliations and pin it up on a wall somewhere).

My experience of the conference is likely to be atypical - being the responsible adult, I did have to stay awake at all times, and do some of the necessary behind-the-scenes stuff while the event was going on. But I did get to participate; I listened to most of most of the talks, with particular highlights for me being Breanndán Ó Nualláin's talk about a DSL for graph algorithms, Martin Cracauer's dense and technical discussion of conservative garbage collection, and the demo session on Tuesday afternoon: three distinct demos in three different areas, each both well-delivered and with exciting content. Those highlights were merely the stand-out moments for me; the rest of the programme was pretty good, too, and it looked like there were some good conversations happening in the breaks, over lunch, and at the banquet on Monday evening. We ended up with 90 registrations all told, with people travelling in from 18 other countries; the delegate with the shortest distance to travel lived 500m from Goldsmiths; the furthest came from 9500km away.

The proceedings are now available for free download from the conference website; some speakers have begun putting up their talk materials, and in the next few weeks we'll try to collect as much of that as we can, along with getting release permissions from the speakers to edit and publish the video recordings. At some point there will be a financial reckoning, too; Goldsmiths has delivered a number of services on trust, while ELSAA has collected registration fees in order to pay for those services - one of my next actions is to figure out the bureaucracy to enable these two organizations to talk to each other. Of course, Goldsmiths charges in pounds, while ELSAA collected fees in euros, and there's also the small matter of cross-border sales tax to wrap my head around... it's exciting being a currency speculator!

In summary, things went well - at least judging by the things people said to my face. I'm not quite going to say "A+ would organize again", because it is a lot of work - but organizing it once is fine, and a price worth paying to help sustain and to contribute to the communication between multiple different Lisp communities. It would be nice to do some Lisp programming myself some day: some of the stuff that you can do with it is apparently quite neat!

Vsevolod DyomkinAnnouncing SHOULD-TEST

· 43 days ago

Once upon a time, it occurred to me that all sound software should be slightly self-ironic. That is how this library's name came into being: yes, you should test even Common Lisp code sometimes. :) But that's not the whole irony...

So, y u makes YATF?

Testing software always fascinated me because it is both almost always necessary and at the same time almost always excessive - it's extremely hard to find the right amount of resources you should allocate to it. You will most likely end up fearing to change your system either because you have too few tests, and some of the important scenarios aren't covered, or too many tests and you need to be constantly re-writing them. Surely, in Lisp the problem is not so drastic because in many cases you can rely on the REPL to help, but it's not a one-fit-all solution. There's also too much dogma in the space of general error handling in programming (that I addressed a little bit in this post). So, to find out how to test properly, around 7 years ago I had written my first test framework, which was called NUTS (non-unit test suite). It worked ok, and I used it in a couple of projects including the huge test suite of CL-REDIS that I'm really proud of. However, it was the first version, and you always have to re-write the first version. :) This is how MUTEST (microtest) appeared. In it, I was aiming at making a tool with the smallest footprint possible. It was also partially inspired by RT, which I consider to be the simplest (with a positive connotation) Lisp test framework (before ST). But both of them, MUTEST and RT, are not lispy because they are not extensible, and it's a shame to not have extensibility in Lisp, which provides excellent tools for building it in.

Well, "version 2 always sucks, but version 3..." So, SHOULD-TEST is version 3, and I'm really happy with it. It's truly minimal and intuitive to the extreme: like in the popular BDD approach you just write (in Yodaspeak, obviously): should be = 1 this-stuff and then st:test. And it's extensible - you can add specialized assertion strategies to the provided 3 basic ones: normal testing, exception catching, and capturing output streams.

I wasn't content with the existing Lisp test frameworks because they aren't concerned first and foremost with the things I care about:

  • intuitive defining and running arbitrary tests
  • testing from the REPL and ease of analyzing the test output
  • piping the test output to upstream systems like CI (by supporting common protocols, such as xUnit and TAP)

These are the 3 things that SHOULD-TEST should do the best.

Over more than a year, I have written or re-written with it the whole test suites for the main open-source libraries I support - RUTILS, CL-REDIS, and CL-NLP (which doesn't yet have an extensive test coverage). And I also use it for all my in-house projects.

Working with ST

Here's a quick overview of the SHOULD-TEST workflow.

Test are defined with deftest:

(deftest some-fn ()
(should be = 1 (some-fn 2))
(should be = 2 (some-fn 1)))

Being run, the defined test returns either T or NIL as a primary value. Secondary and third values in case of NIL are lists of:

  • all failed assertions returned by individual assertions
  • and all uncaught errors signaled inside assertions

should is a macro that takes care of checking assertions. If the assertion doesn't hold should signals a condition of types should-failed or should-erred which are aggregated by deftest. Also, should returns either T or NIL and a list of a failed expression with expected and actual outputs as values.

Under the hood, should calls the generic function should-check and passes it a keyword produced from the first symbol (in this case, :be), a test predicate (here, '=), and a tested expression as thunk (here it will be e.g. (lambda () (some-fn 1))), and expected results if any. If multiple expected results are given, like in (should be eql nil #{:failed 1} (some-other-fn :dummy)), it means that multiple values are expected. As you see, the keyword and test predicate are passed unevaluated, so you can't use expressions here.

The pre-defined types of assertions are be, signal, and print-to. They check correspondingly.

deftest and should write the summary of test results to *test-output* (by default bound to *standard-output*). The var *verbose* (default T) controls if the summary contains full failure reports or just test names.

Tests are defined as lambda-functions attached to a symbol's test property, so (deftest some-fn ... will do the following:

(setf (get some-fn 'test)
(lambda () ...))
One feature that is pending implementation is establishing dependencies between tests while defining them, i.e. specifying the partial order in which they should be run. However, I haven't seen heavy demand for it in my test code so far.

To run the tests, use test. Without arguments, it runs all the tests in the current package. Given a :package argument it will do the same for that package, and given a :test argument it will run that individual test. In case of individual test's failure, it will return NIL and a list of failed assertions and a list of assertions, which triggered uncaught errors. In case of failed test of a package, it will return NIL and 2 hash-tables holding the same lists as above keyed by failed test's names.

As you see, the system uses a somewhat recursive protocol for test results:

  • at the lowest level should returns T or NIL and signals information about the failed assertion
  • this information is aggregated by deftest which will return aggregate information about all the failed assertions in the hash-table
  • at the highest level test will once again aggregate information over all tests

So, the structure of the summary, returned from test, will be the following:

failed-test-1 ((failed-assertion-1 expected actual)
(failed-assertion-2 ...
failed-test-2 ...

There's also :failed key to test that will re-test only tests which failed at their last run.

Usage patterns

As SHOULD-TEST is agnostic, it doesn't impose any restrictions on how each project organizes its tests. Yet, having established patterns and best-practices never hearts. Below is the approach I use...

There's no restriction on naming tests. Though, it seems like a good approach to name them the same as functions they test. As for generic functions, I have different tests for different methods. In this case, I add some suffix to the test's name to indicate which method is tested (like transform-string for one of the methods of gf transform that is specialized for the string class of arguments).

As for code organization, I use the following directory structure of the typical project:

| `----module
| `-----file.lisp

I also usually place the tests in the same package as the code they test but protect them with #+dev guard, so that in production environment they are not compiled and loaded altogether.

ASDF provides a way to define the standard for testing a system that can be invoked with asdf:test-system. The easiest way to hook into this facility is to define the following method for asdf:test-op somewhere either in package.lisp or in some common file in the test module (in the example above: some-general-tests.lisp):

(defmethod asdf:perform ((o asdf:test-op)
(s (eql (asdf:find-system <your-system>))))
(asdf:load-system <your-system>)
(st:test :package <your-package>))

There's also a minimal test suite defined in src/self-test.lisp. The test suite is also hooked to asdf:test-op for the should-test system - just as described above :)
Finally, there's an idea that ST will provide useful connector facilities that are mostly lacking in the existing Lisp test frameworks, to be able to integrate into the general testing landscape (primarily, CI systems). As a start, xUnit support was implemented by us (most of the thanks go to Maxim Zholoback). As it often happens, it was, actually, almost impossible to find the proper xUnit spec, but this SO answer saved the day for us. test-for-xunit generates appropriate XML string to *test-output*. I also plan on implementing TAP support some day (this should be pretty easy, actually), but I'm not in a hurry.

Well, if SHOULD-TEST proves useful to some of you, I'd be glad. Enjoy the hacking!

François-René RideauCommon Lisp as a Scripting Language, 2015 edition

· 43 days ago

The first computer I used had about 2KB of RAM. The other day, I compiled a 2KB Common Lisp script into a 16MB executable to get its startup (and total execution) time down from 2s to subjectively instantaneous — and that didn't bother me the least, for my current computer has 8GB of working memory and over 100GB of persistent memory. But it did bother me that it didn't bother me, for 16MB was also the memory on the first computer in which I felt I wasn't RAM-starved: I could run an X server, an Emacs editor and a shell terminal simultaneously without swapping! Now an entire comfortable software development universe could be casually wasted over a stupid optimization — that I have to care about because software systems still suck. And to imagine that before sentientkind reaches its malthusian future, code bumming will have become a popular activity again...

Background (skip to the next paragraph if you don't care for hardware war stories): I just returned my many-years old work laptop (a Lenovo Thinkpad X230), because of various hardware issues I was starting to experience: mostly a bad connection with the batteries at times causing the machine to shutdown at the least auspicious moment, in addition to the traditional overheating and the wifi card that often failed to connect requiring the wpa_supplicant daemon to be killed. I liked the Thinkpad form factor a lot, but my employer wasn't offering Thinkpad-s anymore, so I opted instead for a slim HP EliteBook Folio 1040: its form factor is obviously inspired from the macbook air, except it is running a Linux system whereby I was master of my ship. Now, the EliteBook has a touchpad that is particularly bad, even worse than the Thinkpad's in being triggered all the time by my thumb as I type; I decided to disable it immediately, just like I did eventually with the Thinkpad; however, unlike the Thinkpad, the EliteBook doesn't have a "clit" interface to supplement the touchpad. Therefore I had to toggle the touchpad on and off instead of permanently disabling it. A Google search quickly found a shell script to toggle the touchpad, and instructions on how to map Penguin-Space to it (the Penguin is Super, much more so than the Windows it replaces). But the shell script frankly made me puke, and I decided to rewrite it in Lisp, which yielded a very nice program less than 2KB long...

Indeed for several years now, I've been peddling the use of Common Lisp as a scripting language: the combination of syntactic abstraction, higher-order functions and an advanced object system, the relatively simple semantic model allowing for efficient compilation, the robust compilers with decent performance and portability to all platforms that matter, and the support for interactive debugging and structured editing — all put it years ahead of all the other dynamically typed scripting languages in common use (shell, perl, python, ruby, javascript), even though it was initially developed years or decades before them. However, until recently, it was missing a few bits to be usable as a scripting language, and I am proud of having hammered the last few nails on the coffin: zero-configuration in looking for source libraries, zero-management in storing compiled outputs, portable invocation from other programs, portable invocation of other program — if you implement these, you too can make your favorite programming language suitable for "scripting".

Well, I recently added an extra nail to the coffin, that addresses the remaining tradeoff between startup times and memory occupancy: it is now possible to easily share a dumped image between all the scripts you need, to achieve instant startup without massive bloat of either working memory or persistent storage. Admittedly, you could already do it semi-portably on SBCL and CCL using Xach's buildapp; but now you can do it fully portably on all implementations using the cl-launch utility that you would use to invoke the program as a script.

The portable way to write a Common Lisp script is to use cl-launch, typically via a #!/usr/bin/cl script specification line when you're using Unix. However, when launching a script this way, even a relatively simple program can take one to several seconds to start: the Lisp compiler locates and loads all the object files into memory, linking the code into symbol, class and method tables; and this somehow takes a non-negligible amount of time even when the files were precompiled, because compilers were never optimized to make this fast; indeed the typical Lisp hacker only recompiles and reloads one file at a time at his interactive REPL, and doesn't often reload all the files from scratch. By installing ASDF 3.1.4 over the one provided by SBCL using the provided install-asdf.lisp script, and by using the provided cl-source-registry-cache.lisp script to avoid search through my quite large collection of CL source code, I could get the startup time down to around .7 or .8s, but that was still too much. This is fine for computation-intensive and/or long-running programs for which this startup latency doesn't matter. But that makes this solution totally impractical for interactive scripts where execution latency is all-important, as compared to other scripting languages, that while inferior as languages, at least start up instantaneously in subjective time.

/bin/sh or perl execute an empty command in about 5 ms of wall clock time, python in about 18ms (all timing and sizes rough averages and estimates on my current linux x86-64 laptop). Without my portability infrastructure, you can also do the same with sbcl in 10 ms or clisp in 15 ms, but then you lose the portability and are either restricted to not using any software library, or are back in non-portable configuration and compilation hell in addition to having the same slow loading issue. With such startup pause, Common Lisp might remain somewhat suitable to scripting, unlike the vast majority of compiled programming languages, that require a explicit compilation step with non-trivial configuration of source and object files; still it finds itself unsuitable for producing scripts destined for use as instantaneous interactive commands outside its own autistic interactive development environment.

Now, all serious Common Lisp implementations also allow you to dump a memory image, with all the code already loaded and linked, and such images start quite fast, about 20 ms for a fully loaded image on sbcl, about 35 ms on clisp; and you can portably dump an image using my cl-launch utility by just adding --output /path/to/executable --dump ! to the very same command you'd use to start a script. Thus, at the expense of an extra but trivial build step that takes many seconds once, you can portably transform your slow-starting scripts into a precompiled executable, that will have startup time competitive with other scripting language, and efficiency competitive with other compiled languages.

The problem is that such an image has a significant overhead in terms of space: an empty cl-launch program has an image of size 13MB with CLISP, 28MB on CCL, or 52MB on SBCL (which isn't that bad when you consider this contains the entire compiler and basic libraries — GCC is bigger than that!); an image with all the code I want loaded takes 27MB on CLISP, 50MB on CCL, 82MB on SBCL. A poly-deca-megabyte image file is no big deal. The biggest of these images is 1% of the memory of my laptop. So, by today's standards, it's a small additive overhead. But if you need one image per script, then 80MB of memory to execute a 2KB script is a multiplicative factor 40000 in memory waste — and that is not acceptable if like me you want to replace lots of small shell scripts with Common Lisp code. Compare that to the incremental space expenditure for each additional 1KB of scripting code, which is typically between 1KB and 10KB of additional size for the image, a reasonable factor of 1 to 10. This suggests an obvious solution: to share the image-dumping expenditure between all your CL scripts, so the space overhead is back to a negligible additive overhead and reasonable multiplicative factor, instead of being an outrageous multiplicative factor.

busybox made popular the old concept of a multi-call binary: a same executable binary program that when executed behaves differently based on what name the program was called, such that by using multiple symbolic links (or hardlinks) to the same program, you can replace multiple different binaries with a single one, benefitting from both the sharing effects of dynamic linking and the optimizations of static linking. The same can be done for Common Lisp code. Xach's buildapp already let you do that on SBCL then on CCL using its option --dispatched-entry. I just enriched cl-launch 4.1.2 to support the very same interface on all its 12+ supported implementations (well, the same interface, modulo a different treatment of corner cases). Now, I already share the same executable for 7 personal use scripts, and will only use CL for new scripts while slowly migrating all my old scripts.

The feature was a hundred lines of code total, including comments, documentation and a new cl-launch-dispatch.asd file; the Lisp support for this feature is only loaded on-demand if you use --dispatched-entry, at which point it is marginally free to load a tiny additional ASDF system. I love how Common Lisp lets me implement this feature in such a modular way. Here is the documentation:

  • If option -DE --dispatch-entry is used, then the next argument must follow the format NAME/ENTRY, where NAME is a name that the program may be invoked as (the basename of the uiop:argv0 argument), and ENTRY is a function to be invoked as if by --entry when that is the case. Support for option -DE --dispatch-entry is delegated to a dispatch library, distributed with cl-launch but not part of cl-launch itself, by
    1. registering a dependency on the dispatch library as if --system cl-launch-dispatch had been specified (if not already)
    2. if neither --restart nor --entry was specified yet, registering a default entry function as if by --entry cl-launch-dispatch:dispatch-entry.
    3. registering an init-form that registers the dispatch entry as if (cl-launch-dispatch:register-name/entry "NAME/ENTRY" :PACKAGE) had been specified where PACKAGE is the current package. See the documentation of said library for further details.

    Now, this is a great workaround, but doesn't fully solve the original issue. To completely solve it, an obvious strategy would be for some implementation to radically optimize loading of compiled objects (so called FASL files, for FASt Loading, which some jest should be renamed SLOw Loading), so it becomes actually fast. For instance, the compiler could produce a prelinked object that optimistically assumes it knows the load address, that there will be no conflict in symbol tables, class and method definitions, etc., and at runtime patches only a minimal set of pointers in the usual case. Doing it for 12+ implementations is not doable, but only one suffices, say SBCL or CCL. Alternatively, an "incremental image" feature might do, whereby one could dump all the symbols in some set of packages and not others, with associated functions, classes, etc.; it would require minor change in programmers' habits, though, so is less likely to happen. But any such complete solution will require hacking into the guts of a CL implementation, and that's no small undertaking.

    Assuming we are not going to improve the underlying implementations, a more long-winded "solution" might be to extend the workaround until it becomes a solution: enabling the automatic sharing of executables between all the programs that matter. The old Common-Lisp-Controller from Debian could be resurrected, to create shared images and/or shared executables for software installed by the system's package manager; a similar mechanism could declaratively manage all the programs of a given user (possibly layered on top of the above when available). This might require some tweaks to ASDF so that it doesn't try to build pre-built software from system-managed directories using system-managed implementations, but compiles the usual way when there is a user-specified upgrade, the software wasn't built, or the implementation isn't system-managed. Importantly, there must not be an insecure writeable system-wide FASL cache. (i.e. reverting to per-user cache when any write access is required, or somehow talking to a trusted daemon to compile trusted sources with trusted compilers). This workaround through system management is somewhat ugly, though.

    Note that these issues do not affect Common Lisp developers who run the functionality provided by these scripts from the Common Lisp REPL; they can already do that. It only affect users who run the functionality from these scripts from the shell command line or some other external non-Lisp programs. To a Common Lisp developer who needs such a use case, the solution to these issues is now trivial thanks to this new cl-launch feature. But these issues do make it hard for people to publish scripts that will "just work" for end-users — an end-user being someone who shan't be required to manage an installation or configuration step. These end-users will have to either suffer a multi-second pause at startup, or be burdened with a poly-deca-mega-byte executable for every script or set of related scripts they use. And so, the temporary conclusion is that while Common Lisp is in many ways far ahead of competition with respect to being a low-overhead "scripting language", it does at the moment have an issue putting it at a disadvantage against this competition in one crucial way with respect to deployment to end-users.

    Quicklisp newsApril 2015 Quicklisp dist update now available

    · 49 days ago
    This Quicklisp update is supported by my employer, Clozure Associates. If you need commercial support for Quicklisp, or any other Common Lisp programming needs, it's available via Clozure Associates.

    New projects:
    • birch — A simple Common Lisp IRC client library — MIT
    • bytecurry.mocks — Tools to mock functions for unit tests — MIT
    • carrier — An async HTTP client — MIT
    • cl-cookie — HTTP cookie manager — BSD 2-Clause
    • cl-coveralls — Coverage tracker for Coveralls — BSD 2-Clause
    • cl-groupby — groupby: A higher order function named groupby as known from Scala. — MIT
    • cl-openstack-client — OpenStack client libraries — Apache-2.0
    • cl-poker-eval — 7-card hand poker evaluator — BSD
    • cl-shellwords — Common Lisp port of Ruby's shellwords.rb, for escaping and splitting strings to be passed to a shell. — MIT
    • cl-singleton-mixin — provides singleton-mixin class. — MIT
    • dexador — Yet another HTTP client for Common Lisp — MIT
    • duologue — High-level user interaction library for Common Lisp — MIT
    • dyna — Dyna is an AWS DynamoDB ORM for Common Lisp. — MIT
    • find-port — Find open ports programmatically. — MIT
    • fmt — Extensible format-like facility — MIT
    • folio2 — the folio2 functional-idioms system — Lisp Lesser GNU Public License
    • immutable-struct — Library that encourage the use of functional programming + pattern matching — LLGPL
    • jonathan — JSON encoder and decoder. — MIT
    • json-responses — Canned JSON responses for Hunchentoot — MIT
    • kebab — Common Lisp string,symbol,keyword PascalCase <=> camelCase <=> snake_case <=> kebab-case(lisp-case) converter. — LLGPL
    • lack — A minimal Clack — LLGPL
    • metap — Metap provides metaclass propagation along class inheritance structure. — MIT
    • nsort — Natural or Numeric Sort — BSD Simplified
    • plump-bundle — A binary storage format for Plump documents. — Artistic
    • proc-parse — Procedural vector parser — BSD 2-Clause
    • quadtree — Quadtree data structure in Common Lisp — MIT
    • quasiquote-2.0 — Writing macros that write macros. Effortless. — MIT
    • scriba — A markup format similar to Scribe. — MIT
    • should-test — Minimal yet feature-rich Common Lisp test framework. — MIT
    • string-escape — Emacs and Python style string escapes in #"..." form. — GPLv3
    • thorn — A CommonDoc extension for entering special characters. — MIT
    • trivia — NON-optimized pattern matcher compatible with OPTIMA, with extensible optimizer interface and clean codebase — LLGPL
    • trivia.balland2006 — Optimizer for Trivia based on (Balland 2006) — LLGPL
    • type-i — Type Inference Utility on Fundamentally 1-arg Predicates — LLGPL
    • type-r — Collections of accessor functions and patterns to access the elements in compound type specifier, e.g. `dimensions' in `(array element-type dimensions)' — LLGPL
    • unix-opts — minimalistic parser of command line arguments — MIT
    Updated projects: 3bmd, access, antik, arrow-macros, buffalo, buildapp, chanl, cl-ana, cl-annot, cl-ansi-term, cl-async, cl-charms, cl-dbi, cl-dot, cl-factoring, cl-gobject-introspection, cl-grace, cl-indeterminism, cl-launch, cl-libyaml, cl-mlep, cl-mtgnet, cl-mw, cl-netstring-plus, cl-openid, cl-ply, cl-python, cl-quickcheck, cl-random, cl-readline, cl-reddit, cl-redis, cl-rlimit, cl-sdl2, cl-slug, cl-svg, cl-syntax, cl-tcod, cl-vectors, cl-voxelize, cl-yaml, clack, classimp, clavier, clhs, clim-widgets, clinch, clipper, clos-fixtures, closer-mop, clsql-helper, clx, codata-recommended-values, colleen, com.informatimago, common-doc, common-doc-plump, common-html, commonqt, croatoan, defclass-std, djula, drakma, eazy-project, esrap-liquid, fare-memoization, fast-http, fast-io, femlisp, gendl, graph, gsll, hdf5-cffi, hl7-client, hl7-parser, http-body, hu.dwim.util, hunchentoot, hyperluminal-mem, integral, interface, introspect-environment, js-parser, jsown, jwacs, lass, let-over-lambda, lfarm, linedit, lisp-interface-library, lisp-invocation, lisp-namespace, local-time, lucerne, magicffi, mcclim, media-types, mgl-pax, mk-string-metrics, nibbles, ningle, nst, plump, protobuf, qtools, quri, quux-time, racer, rutils, scalpl, scriptl, sdl2kit, serapeum, shellpool, simple-rgb, skippy, slime, st-json, staple, stumpwm, symbol-munger, trivial-backtrace, trivial-benchmark, trivial-debug-console, trivial-download, trivial-update, umlisp, verbose, vertex, vgplot, weblocks-stores, weft, workout-timer, xmls, zaws, zcdb, zpb-exif, zpng.

    Removed projects: autoproject, brlapi, cambl, cl-couch, cl-ledger, hctsmsl, nekthuth, red-black.

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


    Quicklisp newsMarch 2015 download stats

    · 50 days ago
    Here are the top 100 download for last month:

     5853   alexandria
    4149 cl-ppcre
    3465 closer-mop
    3382 trivial-features
    3296 babel
    3086 named-readtables
    2977 cffi
    2814 flexi-streams
    2795 bordeaux-threads
    2785 trivial-gray-streams
    2784 cl+ssl
    2722 cl-fad
    2641 trivial-garbage
    2315 nibbles
    2313 usocket
    2277 chunga
    2251 anaphora
    2235 cl-base64
    2218 optima
    2142 split-sequence
    1942 ironclad
    1839 puri
    1803 fiveam
    1768 iterate
    1753 drakma
    1729 chipz
    1641 cl-colors
    1629 trivial-backtrace
    1586 local-time
    1559 md5
    1493 slime
    1486 let-plus
    1401 fare-utils
    1392 fare-quasiquote
    1340 cl-ansi-text
    1190 prove
    1180 hunchentoot
    1098 cl-unicode
    1072 trivial-types
    1053 rfc2388
    1021 metabang-bind
    1010 cl-utilities
    986 cl-interpol
    961 cl-syntax
    950 trivial-utf-8
    889 introspect-environment
    846 quicklisp-slime-helper
    827 cl-annot
    802 parse-number
    757 st-json
    716 quri
    710 osicat
    709 postmodern
    686 cl-marshal
    658 trivial-mimes
    654 xsubseq
    651 lparallel
    648 plump
    645 jsown
    641 asdf-system-connections
    614 ieee-floats
    613 trivial-indent
    605 metatilities-base
    604 uuid
    603 array-utils
    601 cl-containers
    596 cl-json
    590 lquery
    584 fast-http
    572 cl-sqlite
    567 salza2
    556 clss
    538 clack
    500 static-vectors
    495 clx
    490 command-line-arguments
    464 cl-markdown
    463 py-configparser
    462 dynamic-classes
    455 circular-streams
    446 asdf-finalizers
    446 zpb-ttf
    446 cl-log
    445 fast-io
    443 cl-abnf
    442 garbage-pools
    440 buildapp
    435 cl-mssql
    425 cl-who
    399 zpng
    397 esrap
    395 http-body
    394 vecto
    391 cl-csv
    389 cl-vectors
    388 iolib
    358 closure-common
    353 lisp-namespace
    351 cl-opengl
    351 cl-dbi

    For older items, see the Planet Lisp Archives.

    Last updated: 2015-05-27 11:30