Recently in Lisp Category

In this blog post Ingvar Mattsson was wondering about the printed line resulting from evaluating:

(defun frob (x) (format t 'Frob: ~a~%' x))
(frob (defun frob (x) (format t 'New frob: ~a~%' x))

This provides an example where I think the ANSI Common Lisp standard is actually very helpful, since it often tries to go out of its way to point out things that are explicitly left undefined, instead of simply leaving them left undefined by not defining them, as many other standards (out of fear of being ambiguous) do. Quoting from the HyperSpec, Section 3.1.2.1.2.3 Function Forms:

Although the order of evaluation of the argument subforms themselves is strictly left-to-right, it is not specified whether the definition of the operator in a function form is looked up before the evaluation of the argument subforms, after the evaluation of the argument subforms, or between the evaluation of any two argument subforms if there is more than one such argument subform. For example, the following might return 23 or 24.

(defun foo (x) (+ x 3))
(defun bar () (setf (symbol-function 'foo) #'(lambda (x) (+ x 4))))
(foo (progn (bar) 20))

Thus we can see that the effect of evaluating the orginal two forms is indeed undefined (as already suspected by Ingvar Mattsson) as to which function definition is called in the second form, without going to the trouble of trying to take into account possible differences between evaluation and compilation, compile-time effects of defun, etc.

Which is my long-winded way of saying a big thank you to the people involved in creating the ANSI Common Lisp standards document (with special thanks to all involved in creating, releasing and maintaining the HyperSpec online text equivalent thereof, especially of course Kent Pitman), which is one of the nicest language standards I have had the pleasure of working with and against.

So it seems the best way of finding out about lisp packages is releasing a similar package yourself ;): Right on the foot of releasing Deflate, I get to notice Chipz, a similar, but more capable package by Nathan Froyd, the release of which in early 2008 seems to have slipped my notice completely. So anyone who is interested in RFC 1951 Deflate (or even BZIP2 decompression), please have a look at Chipz as well, which is likely to better fit your needs!

Since I can’t let any benchmarking opportunity go to waste, here’s an overview of performance when decompressing a 18.6MB gzip-compressed file into 81.9 MB uncompressed form with Deflate 1.0.0, Chipz 0.7.3 and inflate.cl from Franz, version 2.6, on various CL implementations, and gzip 1.3.10:

Since CRC-32 calculations can overshadow deflate performance itself on some implementations, and since inflate.cl does not perform CRC-32 checksum calculations at all, the columns showing Deflate and Chipz without CRC-32 calculations might be more indicative of actual deflate performance.

Note that this was all done on a MacBook Air 1.8GHz Core2 Duo under Mac OS X 10.5.7, timing was done as an average of 3 runs each.

What can be learned from the results is that 64bit implementations with their bigger fixnum range help quite a bit in performing 32bit algorithms (like CRC-32) well even without extensive/effective declaration fine-tuning or special 32bit arithmetics operators.

I have finally gotten around to separating out and cleaning up the Deflate (RFC 1951) decompression routines we have been using in-house for quite some time, and released them under an X-style free license (see links below), for those who need something with a less restrictive license or better performance than is currently freely available¹.

The library supports decompression of pure deflate streams, zlib-style (RFC 1950) and gzip-style (RFC 1952) streams, including optional checksum checking. The code should be fully portable across all conforming ANSI Common Lisp implementations, and has been performance tuned for SBCL and CMU CL, and somewhat for Lispworks (CRC-32 checksum code). While the performance does not reach the level of zlib/gzip (by a factor of around 3 to 3.5² on my most recent tests with SBCL), mostly due to stream I/O overhead and a not very sophisticated huffman decoder, it is eminently usable.

Support for compression and ZIP-file handling are currently not included.

Enjoy.

Links

• PMSF Resources Page
• GitHub Project Page

1. Since publishing this entry, I’ve been made aware of Chipz from Nathan Froyd, which achieves comparable levels of performance and is as free as Deflate; see my newer blog entry for more information.

2. It seems that on larger files the factor is actually nearer to 1.25-1.5, see this entry for details.

LispWorks Ltd has released LispWorks 5.1, with a long list of improvements, see the release notes for all the gory details.

Sticking out for Mac users are the following improvements:

• 64bit Version with full Cocoa support on Leopard
• Services and Dock menu support in CAPI
• LispWorks as a dynamic library (on Linux as well, Windows already had this support in 5.0)
• Support for drag and drop of text and files

Windows users get:

• OLE embedding i.e. LispWorks as ActiveX control
• Documented windows registry access API
• Support for drag and drop of text and files

General improvements:

• Compiler optimization hints
• Various IDE and CAPI improvements

Regarding Zach Beane’s query what people are working on in Common Lisp in 2008, here is the stuff I’m currently working on in CL, all of which is in use by industrial customers:

• Bit-accurate Reference Interpreter for Simulink/TargetLink discrete-time models, used to validate full code-generation tool-chains, comprising code-generator, compiler, linker and target hardware.

  Implementations used are both SBCL and LispWorks on Windows and Mac OS X for Intel and Power PC, to ensure diversity of implementation and prevent common-cause errors.

  Most of the code is self-written including some internal support libraries, but the code base uses ASDF, CL-PPCRE, CL-YACC, CXML, Puri, SLIME, and trivial-gray-streams. Thanks to everyone who put so much work into those.

• Framework for target-based testing of generated code, including test-harness generation, stimulus/result management and differencing. This is also used in the validation of code-generators, same as the Reference Interpreter above.

  Also uses both SBCL and LispWorks as implementations, and makes use of many of the same libraries.

• Model-differencing and translation toolbox, with support for FIBEX, ASCET and UML-RT. Used in the maintenance and integration of inter-ECU models in automotive development.

  This tool is implemented using LispWorks on Windows, and employs CL-PPCRE and a modified early version of xmls. Note that the tool has been used in production usage for a couple of years, and is mostly in maintenance mode.

Well, there you have it, looking forward to hearing about other users/uses!

Kent M. Pitman has restored and made available on the net The Revised Maclisp Manual (The Pitmanual), that gives great insights into MACLISP, which had a great influence, both directly, and indirectly via Zetalisp (the Lisp Machine Lisp), on the evolution of Common Lisp.

For those interested in such things, the Lisp Machine Manual (Chinual) is also a rich source of information on the MIT Lisp Machine Lisp, before it diverged into different dialects in the Symbolics and LMI commercial Lisp machines.

(Via Geoff Wozniak.)

Reading Gary King’s query for users of advice (see also What is advice?), I’d like to add that advice and friends have uses beyond the usual debugging and patching uses that normally come to mind:

The ability to dynamically add or remove instrumentation code at runtime can be quite useful in cases such as event-driven simulations: When you are modeling complex systems, where long-running simulations can see billions of events and sub-events (i.e. sequences of distinct steps taking place during one event), it is often vitally important to efficiently log and analyze only those events or sub-events that really matter to the purpose of this particular simulation run: The simple approach of logging everything under the sun, and only later deciding what to analyse is often impractical due to speed and space constraints.

So the better approach is to only log that which is necessary, however the difficulty lies in determining which events matter and which don’t, especially since for different simulation runs, the things that matter might be completely different, depending on which analysis the user wants performed.

The approach we took in our logistics simulation framework was to use advice, or rather a home-built instrumentation framework built on frobbing CMU CL’s fdefn-function directly, similar to Gerd Möllmann’s fwrappers code now present in CMU CL: Using this facility report developers could define which methods they wanted instrumented, and, having full access to all information the methods had, use this to record all the information they needed for a particular report.

The instrumentation code was packaged together with the code that analyzed the recorded information and produced the final output, and the simulation user could then switch on or off individual reports at runtime for a simulation run, and only the overhead needed for those reports was inflicted on that particular run.

So a simple analysis which hooks two methods, melde-einlagerung and melde-auslagerung might look like this (sorry for the german names):

(define-analysis lager-umsatz-analysis
    ((laeger)
     (zugang-table :initform (make-hash-table :test #'eq))
     (abgang-table :initform (make-hash-table :test #'eq)))
  (:setup
   (setf laeger (find-subjekt-types 'Lagergruppe)))
  (:instrument
   (melde-einlagerung (element quelle gebinde)
     (when (typep element 'Lagergruppe)
       (incf (gethash element zugang-table 0) (gebinde-volumen gebinde)))
     (call-real-function element quelle gebinde))
   (melde-auslagerung (element quelle gebinde)
     (when (typep element 'Lagergruppe)
       (incf (gethash element abgang-table 0) (gebinde-volumen gebinde)))
     (call-real-function element quelle gebinde)))
  (:update
   (multiple-value-bind (sim-zeit-string real-zeit-string)
       (analysis-zeit-strings lager-umsatz-analysis
                              (- (aktive-zeit)
                                 (analysis-interval lager-umsatz-analysis)))
     (loop
        for lager in laeger
        for bestand = (lagerelement-belegt lager)
        for kapazitaet = (lagerelement-kapazitaet lager)
        for zugang = (gethash lager zugang-table 0)
        for abgang = (gethash lager abgang-table 0)
        do
          (format t "~A;~A;~A;~,2F;~,2F;~,2F;~,2F~%"
                  sim-zeit-string real-zeit-string (subjekt-name lager)
                  (safe-prozent zugang bestand)
                  (safe-prozent abgang bestand)
                  (safe-prozent zugang kapazitaet)
                  (safe-prozent abgang kapazitaet))
        finally
          (clrhash zugang-table)
          (clrhash abgang-table)))))

Of course with Lisp there are also other solutions to this problem, like runtime-compilation of conditionally-instrumented methods, however using advice was a simple and effective solution to this particular problem, which also works without access to the source of methods to be hooked.

Dan Weinreb has invested quite a lot of effort into producing an up-to-date survey of Common Lisp implementations which is in my humble opinion much more useful than many of the out-dated or all-inclusive surveys that float around the net.

(Via Dan Weinreb’s Weblog, which has lots of other interesting posts.)