MCNA Dental of Ft Lauderdale has landed every contract it went for and is quickly becoming a standout in the field of dental insurance. We are developing cutting-edge enterprise software to help manage that growth. Management has asked me to let the world know MCNA is looking for solid, self-starting Common Lisp and/or Ruby/Rails developers who can self-manage on significant sub-projects and execute them efficiently, handling everything from design to coding on their own.

“Candidates should be willing to relocate to sunny Ft Lauderdale, FL for permanent or consulting positions, permanent preferred.

“We are doing very cool things in Common Lisp and Postgres but using Ruby/Rails3 as a bridge to manage the new business now. Ruby/Rails developers can expect to be doing Lisp in the future. The future also includes the IT department spinning off as a standalone enterprise involved in more than just dental insurance. We have a strong team of five developers but given the ambitious software goals and rapid growth MCNA has room for several strong candidates. Note that a strong developer in any Lispy language will be considered for a permanent position.

“Resumes and letters of interest can be sent to ktilton at mcna dot net

lispjobs.wordpress.com | 2/3/12 1:04 AM

Which sorting algorithm should one implement when developing a program? The best answer is probably none. Use the sort provided by your system/library/etc. Unless you know your input data has some special properties that you can take advantage of, the provided sort should be enough for your needs and probably is more efficiently implemented.

However, I think it is important to know what sorting algorithm is implemented. If one knows the properties of the data, it is possible to understand if the provided sort can or will pose a problem. In the same way a programmer shouldn’t implement a sorting algorithm every time it needs to sort something, the programmer should also be aware of the limitations/advantages of the system sort. That way one can decide if a special sort is needed or not.

Common Lisp provides the functions sort and stable-sort. The HyperSpec describes their operation well but it does not define the sorting algorithm. That decision is left free to the implementations. In addition, both functions don’t necessarily share the same algorithm. The difference between the two is that the second function sorts in a way that guarantees stability, i.e., two elements that are equal remain in the same position after sorting is completed. The use of sort and stable-sort requires some care (see the section sort pitfalls) but lets focus on the algorithms and not on its usage.

What sorting algorithms do the major open source CL implementations actually implement? I was curious about it and went to check the source for ABCL, CCL, CLISP, CMUCL, ECL and SBCL. Not surprising, we find some differences between the implementations. What it was more unexpected to discover is that some implementations also use different sorting algorithms according to the sequence type. A quick survey of the findings is summarized in the following table (if anythings is incorrect, please tell me). The links for the source code are in the implementation name (careful, in CCL and SBCL there are two links).

Implementation sort stable-sort ABCL merge sort (lists) / quicksort merge sort C CL merge sort (lists) / quicksort merge sort CLISP tree sort tree sort CMUCL heapsort merge sort ECL merge sort (lists) / quicksort quicksort (strings + bit vectors) / merge sort SB CL merge sort (lists) / heapsort merge sort

 
In terms of the implementation of sort, quicksort is the most used algorithm, followed by heapsort. The choice for these algorithms is expected. Both have an average-case performance of O(nlgn) and heapsort guarantees a worst-case performace of O(nlgn) too. Quicksort has a worst-case performance of O(n2) but it can be optimized in several ways so that it also gives an expected worst-case performance of O(nlgn). However, it seems that the quicksort implementations are not completely optimized. In ECL (and ABCL) quicksort implements a partition scheme which deals better with duplicate elements (although is not the three-way partitioning) but it always picks as pivot the first element. CCL chooses the pivot with a median-of-3 method and always sorts the smaller partition to ensure a worst-case stack depth of O(lgn).

As for CLISP, I think it uses a tree sort but I am not entirely sure. The only source file I could find with a sort implementation was sort.d and it looks like it contains an implementation of tree sort with a self-balanced binary tree, which also gives this algorithm an average and worst-case performance of O(nlgn).

As expected, most of the implementations use merge sort to implement stable-sort since it is a stable sort with average and worst-case performance of O(nlgn). Apparently, all implementations are bottom-up merge sorts with the exception of CCL and ECL. Another interesting thing is that merge sort is also used for lists in sort, in most of the implementations. However, I found it surprising to find quicksort in the stable-sort column because it is not a stable algorithm. Since it is only used for strings and bit vectors, it is not really an issue. While reading the source code of the implementations, I realized that ABCL was using quicksort in stable-sort for all non-list sequences. This is a problem that exists in the current 1.0.1 release but I’ve sent a bug report with a quick fix to the maintainers. The next release should have stable-sort fixed.

This exploration of the sorting algorithms used in the open source implementations was very educational and interesting to me. I’ve learned what algorithms are actually used and enjoyed seing how they were implemented. Just spotting the issue in ABCL stable-sort made this review worthwhile. I think there is still room for improvement in some implementations but knowing now the strengths and weaknesses of the sorts in CL is already good enough. On a final note, I just wonder what are the algorithms used in ACL and LW.

Filed under: Programming Tagged: Common Lisp , Lisp , Sorting Algorithms , Survey jorgetavares.com | 2/2/12 11:45 AM

For reasons which are not apparent* even to myself (although I suspect it had to do with general contrariness mixed with regret for some arrogant comments from the past) I spent 2011 emacs-free. More than that, I spent it using only vi (or, rather, vim) to do my text – including program text – editing. Since I couldn’t get SLIMV to work at the beginning of 2011 – it is in much better shape now – I even gave up the wonder that is Slime/Swank.

I can report that, even for a duffer like me, it is possible to develop very efficiently with vi(m) and a repl running in another terminal. So there, old-splittist!

And just to make sure I’m not making any forward progress, I’ve switched back to emacs for 2012. Now my buffers are full of “jjjj” and “kkkk”…

* I do this a lot, don’t I?

blog.splittist.com | 1/31/12 4:24 PM

My Common Lisp documentation search engine has been published to http://lisp-search.acceleration.net. In a previous post I wrote about using the montezuma full-text search engine to build an index of documentation available from within my common lisp runtime. I ended up going the extra mile on this one and indexing all of the documentation available for all of the packages in quicklisp (as well as readme files and other packages that sbcl had already loaded). The result is a 90M search index (4M tar.gz) that can be used search through all of the doc strings of all of the easily loadable packages.

The user interface is a bit clunky, searches don't always return the most relevant results first, but it is live, fast, and seems already useful. Perhaps with some help from the internet, this search engine can reach its full potential. I named the software package that does this manifest-search-web, because it was inspired by gigamonkey's manifest project. I still have not come up with a reasonable name for the published search engine (lisp-search seems a touch blasé and under-descriptive).

Hopefully, I will never again spend time writing a library only to find the already written, open source alternative after I publish mine. Also, perhaps this will inspire better doc-strings, now that doc-strings might be what leads to someone finding your project.

Other things todo:

• Integrate manifest-search with slime
• Have the documentation index be distributable in quicklisp (not sure how to do that efficiently)
• Find a way to unify CLIKI, l1sp.org, lisp-search and other lisp documentation resources into a more cohesive single website / search
• Improve the query language to ensure that it behaves according to user expectations as opposed to lucene expectations

As always, please report bugs and make suggestions for improvements. Cheers and happy lisping.

russ.unwashedmeme.com | 1/30/12 11:13 PM

TXR is a text extraction and reporting pattern language with support for imperative and functional programming.

www.topix.net | 1/28/12 2:15 AM

cl-cairo2 was one of the first Common Lisp libraries I wrote, but I haven't been using it much for the last year or so (currently I am experimenting with cl-pdf as a backend for my new plotting library, which will be released soon). I have been pretty busy with research, so I didn't have time to merge (and test) patches, also, I didn't even contemplate updating the library to make use of the latest version of cairo. So when Ryan Pavlik contacted me about adding compatibility with cl-freetype2, I asked him whether he wants to take over as a maintaner. He kindly agreed, so I have transferred the repository to him, and he already merged a lot of patches.

One last thing that I wanted to fix before handing the repository over is the license. Originally, the library was licensed under the GPL — in retrospect, I think that

1. I was very naive about software licenses, and didn't really understand what GPL means in the context if Common Lisp (I still don't claim that I do :-P), and
2. I didn't realize that there are a lot of commercial applications in the Common Lisp world, whose authors are wary of depending on GPL'ed libraries.

Consequently, I received many complaints about the license of the library, and decided to change it. I picked the Boost Software License, and contacted all who contributed to the library for permission. All contributors approved the change, so now the library has a simple, permissive non-copyleft free software license. However, it is always possible that I missed someone, so if you contributed to cl-cairo2 in the past but didn't hear from me regarding the license change, please get in touch (eg via the Github issue tracker).

I would like to thank (in alphabetical order) Ala'a Mohammad Alawi, Jay Bromley, Pau Fernández, Johann Korndoerfer, Peter Mikula, and especially Kei Suzuki (who did the last major reorganization) for their contributions to the library. I would also like to thank Ryan for taking over — I am convinced that the library is in good hands.

tkpapp.blogspot.com | 1/26/12 11:12 AM

abcl-dev.blogspot.com | 1/25/12 12:32 AM

The Shuffletron music player, in various branches, has accumulated some neat features (particularly last.fm scrobbling in Brit Butler's branch) that deserve merging, and ought to be cleanly separated from the core of the program. Leslie Polzer sent me a novel implementation early on which used generic functions for extensibility, adding/removing methods via the MOP as plugins load/unload. Clever as that was (and I'm impressed how little code is required, rereading the patch now), I wasn't comfortable with it, and the lack of a pressing need for a plugin interface let me put it off for a good long while.

Building extensibility around generic functions seemed the right thing to do though, and a slightly different idea, of writing plugins in the style of mixins and calling CHANGE-CLASS to enable them at runtime, stuck in the back of my head until (with some prodding) I was motivated to try it out. It's hardly a new idea (both Gsharp and McCLIM contain implementations of similar ideas, as does the AMOP book, just to name a few examples), and a minimal implementation doesn't take much code at all:

(defvar *configurations* (make-hash-table :test 'equal)) (defun configuration (plugins) (or (gethash plugins *configurations*) (setf (gethash plugins *configurations*) (make-instance 'standard-class :name (format nil "MY-APPLICATION~{/~A~}" plugins) :direct-superclasses (cons (find-class 'my-application) (mapcar #'find-class plugins)))))) (defun reconfigure (application plugins &rest; initargs) (apply #'change-class application (configuration plugins) initargs)) (defun active-plugins (instance) (mapcar #'class-name (rest (sb-mop:class-direct-superclasses (class-of instance))))) (defun enable-plugin (application plugin &rest; initargs) (apply #'reconfigure application (adjoin plugin (active-plugins application)) initargs)) (defun disable-plugin (application plugin) (reconfigure application (remove plugin (active-plugins application)))) (defun make-application (&rest; initargs) (apply 'make-instance (configuration '()) initargs))

This isn't an ideal implementation, and there's a limit to how good it's going to get when CLOS doesn't fully support anonymous classes. However, a more serious attempt should work on arbitrary classes, provide a place to hang init/shutdown code for plugins, and the ability to list which plugins are enabled within an instance.

Piddling Plugins

Piddling-plugins adds these features using only slightly more code than above, along with some superfluous macro magic for writing defun-style definitions that are extensible by plugins. I've made light use of it in a branch of Shuffletron, confirming to myself that it's a good fit.

The code is tiny and self-explanatory, so I'll just post the examples from the README file for fun.

Examples

Imagine we have written a music player, looking something like this deliberately simplified code:

(defclass music-player () ()) (defun run-music-player () ;; You need to set or bind *application* to your application instance ;; if you use defun-extensible. It's a good idea even if you don't. (let ((*application* (make-instance 'music-player))) (init-audio) (init-library *application*) (loop (execute-command (read-line)))))

Functions extensible by plugins can be defined using DEFUN-EXTENSIBLE. This is just syntactic sugar for defining a generic function specialized on the application object, with a wrapper that passes in the value of *APPLICATION*.

(defun-extensible execute-command (command) ...) (defun-extensible play-song (song) ...) (defun-extensible song-finished (song) ...)

Plugins extend the behavior of the application by defining methods on the extensible functions (or rather the generic functions defined behind the scenes, which are prefixed by "EXTENDING-"):

(defclass scrobbler () ((auth-token :accessor auth-token))) (defmethod plugin-enabled (app (plugin-name (eql 'scrobbler)) &key &allow-other-keys) (setf (auth-token app) (get-auth-token)) (format t "~&Scrobbler enabled.~%")) (defmethod plugin-disabled (app (plugin-name (eql 'scrobbler))) (format t "~&Scrobbler disabled.~%")) (defmethod extending-song-finished :after ((plugin scrobbler) song) (scrobble song (auth-token plugin))) (defclass status-bar () ()) (defmethod extending-play-song :after ((plugin status-bar) song) (redraw-status-bar)) (defmethod extending-execute-command :after ((plugin status-bar) command-line) (declare (ignore command-line)) (redraw-status-bar))

To enable a plugin:

(enable-plugin *application* NAME [INITARGS...])

To disable a plugin:

(disable-plugin *application* NAME)

To set precisely which plugins are enabled:

(reconfigure *application* LIST-OF-PLUGINS [INITARGS...]) References

• Strandh R., Hamer J., Baumann G. "Using Stealth Mixins to Achieve Modularity" (2007)
  • Implentation in Gsharp: http://common-lisp.net/cgi-bin/gitweb.cgi?p=projects/gsharp/gsharp.git;a=blob;f=utilities.lisp
• "Modes" implementation in McCLIM's ESA framework (formerly part of Climacs)
  • http://git.boinkor.net/gitweb/mcclim.git/blob/HEAD:/ESA/utils.lisp#l446
• Throwaway classes (comp.lang.lisp): http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/78ef4a5fcd6a1661?pli=1
• The Art of the Metaobject Protocol, Section 2.4
  • http://www.foldr.org/~michaelw/lisp/amop-programmatic-class.lisp
• ContextL - http://common-lisp.net/project/closer/contextl.html
• Dynamic Classes - http://common-lisp.net/project/dynamic-classes/

ahefner.livejournal.com | 1/23/12 2:15 PM

TXR is a text extraction and reporting pattern language with support for imperative and functional programming.

www.topix.net | 1/22/12 5:07 AM

I updated ZS3 , my CL library for interacting with Amazon S3, with a few new features.

First, there's support for S3's new multi-object deletion system. In the past, S3 required one API call per object to delete stuff. Now you can delete up to 1000 objects with a single call, and ZS3's existing delete-objects function has been updated to use the new interface and will automatically split up the objects to be deleted into groups of 1000 as needed.

Multi-object deletion can be a big deal, since each API call costs money.

Second, there's support for the "reduced redundancy" storage class. Reduced redundancy storage is less durable than standard storage, and it comes with a corresponding reduction in cost. You can choose reduced redundancy when using put-object or related functions, or set the storage class after the fact with set-storage-class .

Third, there's support for automatic object expiration, aka bucket lifecycle configuration. With bucket lifecycle rules you can specify that objects with names that match a certain prefix expire after a certain period of time. You can change a bucket's lifecycle configuration with bucket-lifecycle and related functions.

Automatic expiration of objects is another way to save money on API calls. If objects are deleted automatically, you don't need to use any API calls at all to get rid of them.

Please let me know if there's an S3 feature you really want to see in ZS3. I feel like I'm on a roll and would love to add some more stuff that people need. xach.livejournal.com | 1/21/12 5:35 PM

I'm going to be giving a talk about Parenscript to the Montreal Scheme/Lisp Users Group on Thursday, January 19 (meeting details here ).

The slides I'm going to be using are here , and a list of links referenced in the talk is below. The last time I gave a presentation on Parenscript was to LispNYC in 2007. Parenscript has received a huge number of changes and improvements since then, and continues to be the best language/compiler to JavaScript and one of the best tools available for web application development. What's also new since 2007 are libraries and tools that extend Parenscript: Red Daly has added CLOS and the Common Lisp condition system to JavaScript as a Parenscript library, and there are now several options for interactive development with SLIME in your browser.

Links:

• Parenscript
  
• Moritz Heidkamp's survey of Lisp-in-JavaScript implementations
  
• Jason Kantz's JSGEN
  
• Peter Seibel's Lispscript
  
• Red Daly's PSOS
  
• Catherine Gaudron and Marc Feeley's JavaScriptScheme Scheme to JavaScript compiler
  
• Web frameworks: BKNR, UCW, Weblocks, teepeedee2
  
• Libraries: Suave, css-lite, clouchdb, uri-template, cl-closure-template
  
• Scheme2JS
  
• Parenscript mailing list thread on multiple value return
  
• Manuel Odendahl's original Parenscript announcement
  
• slime-proxy
  

carcaddar.blogspot.com | 1/19/12 2:06 AM

This blog has been going for five years. Back then, it seemed like the only widely-used static blog generators were Blosxom or pyBlosxom. They weren’t that hard to set up, but getting everything right rather than good enough is a lot of work. Latex and MathML support was also very weak, so I wound up using a (insane) one-off hack with tex4ht. I feel like Octopress and MathJax now do everything I need out of the box, better than anything I could design by myself.

The permalinks from the old blog are still around, but not the rss feeds or the date-based links.

I figure this is a good opportunity to make sure the (marginally useful) permalinks are available somewhere else than via google.

Lisp-related posts

Another way to accumulate data in vectors describes a copying-free extendable vector. The advantage over the usual geometric growth with copy is that the performance with respect to the number of elements added is much smoother. Runtimes are then more easily predictable, and sometimes improved (e.g. right when a copy would be needed). It’s also more amenable to a lock-free adaptation, while preserving O(1) operation complexity (assuming that integer-length on machine integers is constant time), as shown in Dechev et al’s “Lock-free Dynamically Resizable Arrays”.

Common Cold is a really old hack to get serialisable closures in SBCL, with serialisable continuations built on top of that. Nowadays, I’d do the closure part differently, without any macro or change to the source.

Concurrency with MVars has short and simple(istic) code for mvars, and uses it to implement same-fringe with threads.

Constraint sets in SBCL: preliminary exploration summarises some statistics on how constraint sets (internal SBCL data structures) are used by SBCL’s compiler.

SBCL’s flow sensitive analysis pass explores what operations on constraint sets actually mean. This, along with the stats from the previous post, guided a rewrite, not of constraint sets, but of the analysis pass that uses them. The frequency of slow operations or bad usage patterns is reduced enough to take care of most (all?) the performance regression associated with the original switch to bit-vector-based constraint sets, without penalising the common case.

Finalizing foreign pointers just late enough is a short reminder that attaching finalizers to system area pointers isn’t a good idea: SAPs are randomly unboxed and consed back, like numbers.

Hacking SSE Intrinsics in SBCL (part 1) walks through an SBCL branch that adds support for SSE operations. Alexander Gavrilov has kept a fork on life support on github. There’s still no part 2, in which the branch is polished enough to merge it in the mainline.

In the meantime, Complex float improvements for sbcl 1.0.30/x86-64 built upon the original work on SSE intrinsics to implement operations on (complex single-float) and (complex double-float) with SIMD code on x86-64. That sped up most complex arithmetic operations by 100%. That work also came with support for references to unboxed constants on x86oids, that also significantly improved floating point performance, for both real and complex values.

Initialising structure objects modularly is a solution to a problem that I hit, trying to implement non-trivial initialisation for structures, while allowing inheritance. Tobias Rittweiler points out that the protocol is very similar to a common CLOS pattern where, instead of functions that allocate objects, class designators are passed. It also looks a bit like the way Factor libraries seem to do struct initialisation, but with actual initialisation instead of assignment (which matters for read-only slots).

An Impure Persistent Dictionary is an example of a technique I find really useful to implement persistent versions of side-effectful data structures. Henry Baker has a paper that shows how shallow binding can be used to implement persistent arrays on top of functional arrays, with constant-time overhead for operations on the latest version. It’s a really nice generalisation of trailing in backtracking searches. Here, I use it to get persistent hash tables in only a couple dozen lines of code.

Pipes is an early attempt to develop a DSL for stream processing, like an 80% SERIES. I’ve refocused my efforts on Xecto, which only handles vectors, rather than potentially unbounded streams. The advantage is that Xecto looks like it has the potential to be simpler while achieving near-peak performance to me; the main downside is that vectors don’t allow us to represent control flow as data via lazy evaluation… and I’m not sure that’s such a bad thing.

The post on string-case is an overview of how I structured a CL macro to dispatch that compares with string= instead of eql. If I were to do this again, I’d probably try and improve string=; I later tested an SSE comparison routine, and it ended up being, in a lot of cases, faster and simpler (with a linear search) than the search tree generated by string-case.

The type-lower-bound branch describes early work on a branch that provides a way to shut the compiler up about certain failed type-directed optimisations. A lot of the output from SBCL’s compiler amounts to reports of optimisations that couldn’t be performed (e.g. converting multiplication by a constant power of two to a shift), and why (e.g. the variant argument isn’t known to be small enough). Sometimes, there’s nothing we can do about it: we can’t show the compiler that the argument is small enough because we know that it will sometimes be too large! Yet, CL’s type system (like most) does not let us express that information. Programmers are expected to provide upper bounds on the best static type of values (e.g. we can specify that a value is always a fixnum, although it may really only be integers between 0 and 1023). We would like a way to specify lower bounds as well: “I know that this will take arbitrary fixnum values.” Once we have that, the compiler can skip reporting optimisations that we know can’t be performed (as opposed to those we don’t know whether they can be performed).

Finally, Yet another way to fake continuations sketches a simple but somewhat inefficient way to implement continuations for pure programs. It may be useful for IO-heavy applications (web programming), or in certain cases similar to backtracking search, but in which most of the work is performed outside of backtracking (e.g. during constraint propagation).

General low-level programming issues

SWAR implementation of (some #’zerop …) sketches how we can use SIMD-within-a-register techniques to have fast search for patterns of sub-word size. A degenerate case is when we look for 0 or 1 in bit vectors; in these case, it’s clear how we can test whole words at a time. The idea can be extended to testing vectors of 2, 4, 8 (or any size) -bit elements. I haven’t found time to move this in SBCL’s runtime library (yet), but it would probably be a neat and feasible first project.

Revisiting VM tricks for safepoints explores the performance impact of switching from instrumented pseudo-atomic code sequences to safepoints. The bottom line is that it’s noise. However, some members of the russian Lisp mafia have used it as inspiration, and have managed to implement seemingly solid threaded SBCL on Windows! It’s still a third-party fork for now, but some committers are working on merging it with the mainline.

Fast Constant Integer Division has some stuff on integer division by constants. It’s mostly superseded by Lutz Euler’s work to implement the same algorithm as GCC. There are some interesting identities that can be used to improve on that algorithm a tiny bit and, more interestingly, to implement truncated multiplication by arbitrary fractions. I only stumbled upon those a long after I wrote the post, but I’ll try and come back to this topic in the coming months.

There’s more to locality than caches tracks my attempts to understand why a data structure designed to be cache-efficient did not perform as well as expected. It turns out that cache lines aren’t exactly read atomically (so reading two adjacent addresses may be significantly slower than only one), and that sometimes L2 matters less than TLB. The latter point was an important lesson for me. TLBs are used to accelerate the translation of virtual addresses to physical; every memory access must be translated. TLBs are usually fully associative (behave like content-addressed memory or hash tables, basically), but with a small fixed size, on the order of 512 pages for the slower level. With normal (on x86oids) 4KB pages, that’s only enough for 2 MB of data! Even worse: a cache miss results in a single access to main memory, which is equivalent to ~60-100 cycles at most; a TLB miss, however, results in a lookup in a 4 level page table on x86-64, which often takes on the order of 2-300 cycles. Luckily, there are workarounds, like using 2 MB pages.

Napa-FFT(2) implementation notes is where I try to make the code I wrote for a Fast Fourier transform understandable, especially why it does what it does. Napa-FFT and Napa-FFT2 are vastly faster than Bordeaux-FFT (and than all other CL FFT codes I know, on SBCL), but it’s still around 20-50% slower than the usual benchmark, FFTW. Napa-FFT3 is coming, and it’s a completely different approach which manages to be within a couple percent points of FFTW, and is faster on some operations.

0x7FDE623822FC16E6 : a magic constant for double float reciprocal is a surprisingly popular post. I was trying to approximate reciprocals as fast as possible for a mathematical optimization method. The usual way to do that is to use a hardware-provided approximation and then improve it with a couple iterations of Newton’s method. The post shows how we can instead use the way floats are laid out in memory to provide a surprisingly accurate guess with an integer subtraction. I actually think the interesting part was that it made for a practical use case for the golden section search…

Some notes on Warren has a couple notes about stuff in Warren’s book Hacker’s Delight. The sign extension bit probably deserves more attention; it seems like someone on #lisp asks how they can sign-extend unsigned integers at least once a month.

Two variations on old themes has some stuff on Linux’s ticket spinaphores, and is the beginning of my looking into Robin Hood hashing with linear probing for cache-friendly hash tables.

Interlude: Numerical experiments in hashing covers a first stab at designing a hash table that exploits cache memory. 2-left hashing looks interesting, but its performance was worse than expected, for various reasons, mostly related to the fact that caches can be surprisingly complicated. Two years later, More numerical experiments in hashing: a conclusion revisits the question, and settles on Robin Hood hashing with linear probing. It’s a tiny tweak to normal open addressing (insertions can bump previously-inserted items farther from their insertion point), but it suffices to greatly improve the worst and average probing length, while preserving the nice practical characteristics of linear probing. I’ve also started some work on implementing SBCL’s hash table this way, but there are practical issues with weak hash functions, GC and mutations.

Miscellaneous stuff

In Specify absolute deadlines, not relative timeouts and the sequel, I argue that we should have interfaces that allow users to specify an absolute timeout, with respect to a monotonous clock. Timeouts are convenient, but don’t compose well: how do we implement a timeout version of an operation that sequences two calls to functions that only offer timeouts as well? Any solution will be full of race conditions.

Finally, Space-complexity of SSA in practices has some early thoughts on how Static single assignment scales for typical functional programs. It’s fairly clear that many compilers for functional languages have inefficient (wrt to compiler performance) internal representations; however, it’s not as clear that the industry standard, SSA, would fare much better.

www.pvk.ca | 1/19/12 1:56 AM

If you're interested in Lisp, audio/music hacking, just intonation, or microtonality, then this is the sort of thing you're interested in.

First, we'll need a way to play audio. In the past, I dumped the raw audio out to a file in /tmp and played it by shelling out to SoX. These days I can just play it out of an array in memory using my Mixalot library (of which this code requires the latest version, having only recently added support for playback of floating point vectors).

Audio playback through Mixalot is straightforward:

(defparameter *mixer* (mixalot:create-mixer)) (defgeneric play (this)) (defun normalize (vector) (let ((rescale (/ (reduce #'max vector :key #'abs :initial-value 0.0d0)))) (map-into vector (lambda (x) (* x rescale 0.8d0)) vector))) (defmethod play ((this vector)) (mixalot:mixer-add-streamer *mixer* (mixalot:make-vector-streamer-mono-double-float (normalize this))))

Next, synthesis - we'll need some audio to play. I'll define a function of frequency called TONE that produces a buffer of audio:

(defparameter *len* 1 "Note length") (deftype buffer () '(simple-array double-float 1)) (defun make-buffer (size) (make-array size :element-type 'double-float :adjustable nil :fill-pointer nil)) ;;; Generate an audible tone. (defun tone (freq &key; (duration 40000) (len *len*)) (declare (optimize (speed 3))) (loop with nsamples = (round (* duration len)) with output = (the buffer (make-buffer nsamples)) with decay-rate = (expt 0.07 1/65000) with omega = (float (/ (* freq 2.0d0 pi) 44100.0d0) 0.0d0) for amp of-type double-float = 1.0d0 then (* amp decay-rate) for phase of-type double-float = 0.0d0 then (+ phase omega) for n from 0 below nsamples do (setf (aref output n) (* amp ;; A simple FM (PM) oscillator. Tweaking the magic ;; numbers produces a variety of mostly chime-like ;; timbres. (sin (+ phase (* 1.5 (expt amp 2) (sin (* phase 5))))))) finally (return output)))

Next I'll define a simple language for constructing musical phrases from the output of this function. There are two fundamental building blocks:

1. Sequencing of events serially in time:

(defun seq (&rest; args) (apply #'concatenate 'buffer args))

..of which repetition is a special case:

(defun repeat (n &rest; args) (apply #'seq (mapcan #'copy-list (loop repeat n collect args))))

2. Events in parallel:

(defun para (&rest; args) (reduce (lambda (out in) (declare (type buffer out in)) (map-into out #'+ out in)) args :initial-value (make-buffer (reduce #'max args :key #'length))))

Originally I wrote a simpler definition for this:

(defun para (&rest; args) (apply #'map '(simple-array double-float 1) #'+ args))

This defintion has the disadvantage of truncating the output length to that of the shortest component. Also, using SBCL, it's much slower. (apply #'map ...) is a hairy expression that defied optimization by the compiler, whereas it can inline the map-into operation. Combined with the type declaration, it expands to a nice fast addition loop.

Here's some syntactic sugar to make the pieces fit together more nicely, and print some useful information to the REPL:

(defmacro chord (properties &body; body) `(let ,properties (print :chord) (para ,@body))) (defparameter *tonic* 261.0d0) ; Middle C. (defmacro just (numerators denominators &rest; args) `(progn ;; It's useful to see the both reduced fraction and its decimal representation: (print (list ',numerators ',denominators (* ,@numerators (/ 1 ,@denominators)) (float (* ,@numerators (/ 1 ,@denominators))))) (tone (* *tonic* ,@numerators (/ 1 ,@denominators)) ,@args)))

Now, to combine these tools to some musical end. First test: start with a major chord, invert the intervals each way we can, then resolve down to an inversion of the original chord. Note the two different senses of "invert".

(play (seq (chord () (just (1) (1)) ; Root (just (5) (4)) ; Major 3rd - 5:4 (just (3) (2))) ; Fifth - 3:2 (chord () (just (1) (1)) (just (4) (5)) ; 5:4 becomes 4:5 - The major 3rd is reflected about the octave. (just (3) (2))) (chord () (just (1) (1)) (just (5) (4)) (just (2) (3))) ; This time, the fifth. (chord () (just (1) (1)) (just (4) (5)) ; - Now both are reflected. (just (2) (3))) ; - (chord () ; Resolve down.. (just (1) (1)) (just (5) (4 2)) (just (3) (2 2)))))

Here's a pair of chords used by Harry Partch (see http://en.wikipedia.org/wiki/Tonality_flux):

(let ((*tonic* 196.0) (*len* 3)) (play (repeat 2 (seq (chord () (just (8) (7)) (just (10) (7)) (just (12) (7))) (chord () (just (7) (6)) (just (7) (5)) (just (7) (4)))))))

See what he did there? The major chord, built starting 8/7 above the tonic, is reflected around the octave. I find it clearer to consider the minor chord first, built upon an interval of 7/6 above the tonic, then interpret the major as as built symmetrically downward from the next octave.

It's clearer after rewriting the fractions without simplification to separate the 8:7 and octave components from the intervals of the chord:

(let ((*tonic* 196.0) (*len* 3)) (play (repeat 2 (seq (chord () (just (8 1) (1 7)) ; 8/7 (just (8 5) (4 7)) ; 10/7 (just (8 3) (2 7))) ; 12/7 (chord () (just (2 7 1) (1 8 1)) ; 7/4, i.e. (2*7*1)/(1*8*1), if it isn't clear. (just (2 7 4) (5 8 1)) ; 7/5 (just (2 7 2) (3 8 1))))))) ; 7/6

Applying that construction under equal temperament, the middle notes of the chords would be the same. Since this is just-intoned, the frequencies differ by about a third of a semitone, and we find ourselves in the uncanny valley of microtonal voice leading.

I've never developed an ear for microtonal music, so I'll run with the idea of this pivoting around the octave and try something conventional. Take the same two chords, add a minor chord on the tonic (without the 8/7 offset) before, and its reflection around the next octave after. Then tack on a little ending to make a more satisfying musical snippet: move down by a fourth, then back, with a couple added notes for color.

(let ((*tonic* 196.0) (*len* 2)) (play (seq (chord () ; 1 (just (1) (1)) (just (6) (5)) (just (3) (2))) (chord () ; 2 (just (8 ) ( 7)) (just (8 5) (4 7)) (just (8 3) (2 7))) (chord () ; 3: Built downward from next octave, symmetric with 2. (just (2 7 2) (3 8)) (just (2 7 4) (5 8)) (just (2 7 1) (1 8))) (chord () ; 4: Built downward from next octave, symmetric with 1. (just (2 ) (1)) (just (2 5) (6)) (just (2 2) (3))) ;; Build and release tension. (chord ((*len* 3)) (just (2 3 ) ( 4)) (just (2 3 4) (3 4)) (just (2 3 3) (2 4))) (chord ((*len* 1)) (just (2 3 ) ( 4)) (just (2 3 4) ( 3 4)) (just (2 3 3) ( 2 4)) (just (2 3 4 4) (3 3 4))) ; 4/3*4/3, let's call it a dominant seventh. (chord ((*len* 4)) (just (1) (1)) (just (6) (5)) (just (3) (2)) (just (2) (1)) (just (3) (1)))))) ; ..and that's a ninth. The 7th resolved here.

Stacking fourths:

(let ((*tonic* 262.0) (*len* 2)) (play (seq (chord () (just (1) (1)) (just (4) (3))) (chord () (just ( ) ( )) ; Did I mention the ones are optional? (just (4 ) ( 3)) (just (4 4) (3 3))) (chord () (just ( ) ( )) (just (4 ) ( 3)) (just (4 4 ) ( 3 3)) (just (4 4 4) (3 3 3))) (chord () (just ( ) ( )) (just (4 ) ( 3)) (just (4 4 ) ( 3 3)) (just (4 4 4 ) ( 3 3 3)) (just (4 4 4 4) (3 3 3 3))) (chord () (just ( ) ( )) (just (4 ) ( 3)) (just (4 4 ) ( 3 3)) (just (4 4 4 ) ( 3 3 3)) (just (4 4 4 4 ) ( 3 3 3 3)) (just (4 4 4 4 4) (3 3 3 3 3))))))

Stacking fifths and fourths:

(let ((*tonic* 262.0) (*len* 1)) (play (seq (chord () (just ( ) ( )) (just (3 ) ( 2)) (just (3 4) (3 2))) (chord () (just ( ) ( )) (just (4 ) ( 3)) (just (4 4) (3 3))) (chord ((*len* 2)) (just ( ) ( )) (just (3 ) ( 2)) (just (3 3 ) ( 4 2)) (just (3 3 4) (3 4 2))) (chord () (just ( ) ( )) (just (4 ) ( 3)) (just (4 4 ) ( 3 3)) (just (4 4 4) (3 3 3))) (chord () (just ( ) ( )) (just (3 ) ( 2)) (just (3 4 ) ( 3 2)) (just (3 4 4) (3 3 2))) (chord ((*len* 4)) (just ( ) ( )) (just (4 ) ( 3)) (just (4 3 ) ( 2 3)) (just (4 3 4) (3 2 3))))))

Various ways to express the a major triad:

(play (seq (chord () ; Three separate notes. (just (1) (1)) (just (5) (4)) (just (3) (2))) (chord () (just (1 ) ( 1)) (just (1 5 ) ( 4 1)) ; A major 3rd.. (just (1 5 6) (5 4 1))) ; ..and a minor 3rd on top of that. (chord () (just (1 ) ( 1)) (just (1 3 ) ( 2 1)) ; Or, you could nest the third inside (just (1 3 5) (6 2 1))))) ; the fifth by a downward interval.

The Tristan Chord (in equal temperament)

(play (chord ((*tonic* 349.0) ; F (*len* 3)) (tone (* *tonic* (print (expt 2.0 0/12)))) (tone (* *tonic* (print (expt 2.0 6/12)))) (tone (* *tonic* (print (expt 2.0 10/12)))) (tone (* *tonic* (print (expt 2.0 15/12))))))

Assume we're in A minor, and the chord is inverted such that the root is B. The tritone between B and F is problematic. It's an unnatural interval in just-intonation, and there are various ways to interpret it relative to the other notes.

(play (chord ((*tonic* 440.0) (*len* 3)) (just (9 ) ( 8)) ; B (just (9 5 ) ( 4 8)) ; B * 5/4 = D# (just (9 5 4) (3 4 8)) ; D * 4/3 = G# ;; Now we need that F. Three ways to get there spring to mind: ;; 1. Two intervals of 3/4 downward from D#. Yields intervals of ;; 45/64, 9/16, and 27/64 versus the other notes in the chord, and ;; an ungainly 405/512 versus the tonic. The ratios are ugly, but ;; the sound is quite close. ;; (just (9 5 9) (16 4 8)) ;; 2. An intervals of 5/9 downward from D# yields intervals of ;; 25/36, 5/9, and 5/12 versus the rest of the chord, and 25/32 ;; against the tonic. The pitch ratios within the chord are mostly ;; nice and simple, but the F sounds oddly flat. ;; (just (9 5 5) (9 4 8)) ;; 3. An interval of 7/10 downward from the root, yielding ;; intervals of 7/10, 14/25, and 21/50 versus the rest of the ;; chord, and 63/80 against the tonic. Constructing the F relative ;; to the root of the chord seems preferable, even if it introduces ;; a new factor of 7 into the ratios, which make the intervals ;; against D# and G# odd. Overall, I prefer the sound of this ;; one. The F is slightly flat compared to the equal-tempered ;; chord, but not unpleasantly so. (just (9 7) (10 8))))

When you uncomment more than one of the above versions of 'F', they're slightly detuned and beat against each other. This could be a cool compositional device to highlight shifts in the tonality. I'll try it with the two Partch chords:

(let ((*tonic* 196.0) (*len* 3)) (play (repeat 2 (seq (chord () (just (8 1) (1 7)) (just (8 5) (4 7)) (just (8 3) (2 7))) (chord () (just (8 1) (1 7)) (just (8 5) (4 7)) (just (2 7 4) (5 8 1)) ; Presages the following chord.. (just (8 3) (2 7))) (chord () (just (2 7 1) (1 8 1)) (just (2 7 4) (5 8 1)) (just (2 7 2) (3 8 1))) (chord () (just (2 7 1) (1 8 1)) (just (2 7 4) (5 8 1)) (just (8 5) (4 7)) ; And again.. (just (2 7 2) (3 8 1)))))))

That suggests a more subtle trick. Rather than playing both tones to mark the shift, replace one with the similar tone from the next chord.

(let ((*tonic* 196.0) (*len* 3)) (play (repeat 2 (seq (chord () (just (8 1) (1 7)) (just (8 5) (4 7)) (just (8 3) (2 7))) (chord () (just (8 1) (1 7)) (just (2 7 4) (5 8 1)) ; Replaced (8 5) (4 7) to lead into the next chord. (just (8 3) (2 7))) (chord () (just (2 7 1) (1 8 1)) (just (2 7 4) (5 8 1)) (just (2 7 2) (3 8 1))) (chord () (just (2 7 1) (1 8 1)) (just (8 5) (4 7)) ; Likewise, replaced (2 7 4) (5 8 1) (just (2 7 2) (3 8 1)))))))

That's all for now. I've published the code on Github here.

Incidentally, I've concluded my world tour (my Thailand visa having expired, and an additional season of leisure and international intrigue being financially unwise), so if you're looking for a versatile young Lisp/C/C++ hacker with a background in computer/network security and an equal penchant for spiffy user interfaces and gritty low-level trawling around in debuggers and disassemblers, you could do worse than to get in touch.

ahefner.livejournal.com | 1/17/12 10:18 AM

I just finished reading Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists .

www.topix.net | 1/17/12 5:50 AM

Steel Bank Common Lisp is a development environment for Common Lisp, with excellent support for the ANSI standard: garbage collection, lexical closures, powerful macros, strong dynamic typing, incremental compilation, and the famous Common Lisp Object System .

www.topix.net | 1/15/12 4:54 AM

Lists are the most important data structures in functional languages. it is not for nothing that the first functional programming language, that is by the way the second oldest programming language is called LISP which stands for "LISt Processing languages". LISP is all about working with lists to the point that even its source code is written with ... (more)

www.topix.net | 1/13/12 2:24 PM

TXR is a text extraction and reporting pattern language with support for imperative and functional programming.

www.topix.net | 1/12/12 9:23 AM

All users of abcl-1.0.0 are recommended to migrate to abcl-1.0.1 as it fixes the abcl-contrib mechanism, an unfortunate oversight in our giddiness at being able to release at ECLM 2011. abcl-dev.blogspot.com | 1/11/12 1:29 AM

From Wikipedia : "Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features.

www.topix.net | 1/10/12 7:25 PM

You are kindly invited to the next Berlin Lispers Meetup, an informal gathering for anyone interested in Common Lisp and other languages in the Lisp family.

Berlin Lispers Meetup
Tuesday January 24, 2012
8 pm onwards
co.up (bell: Upstream Agile) , Adalbertstraße 7, 10999 Berlin (U-Bahn Kottbusser Tor)

There will be two presentations:

• "Further notes on sparql processing" by James Anderson and Arto Bendiken who are affiliated with Datagraph, Inc.
• "A suggestion for parentheses representation in a Common Lisp IDE" by Nuno Rocha.

Please join for another evening of parentheses!

Twitter: @BerlinLispers

netzhansa.blogspot.com | 1/10/12 8:55 AM

My CDB changes to the Quicklisp clients caused a few subtle problems.

First, the system CDB file was built with incorrect keys. That could lead to a spurious SYSTEM-NOT-FOUND error when trying to use ql:quickload something.

Second, the CDB files were not cleared out when updating dist metadata. The CDB indexes would point to old systems and software even after everything was meant to be updated.

If you run into a Quicklisp problem that seems like it might be related to these issues, here's a way to fix things:

1. (ql:update-client) to make sure you have the latest client
2. Restart your Lisp
3. (in-package #:ql-dist-user)
4. (map nil 'delete-file (directory (relative-to (dist "quicklisp") "*.cdb")))

blog.quicklisp.org | 1/9/12 3:33 PM

Skimming through the Genera source just now, I enjoyed this description of the compiler structure (from sys2/compiler_protocol.lisp), which precedes a very modern-feeling definition of the interface in terms of classes (or rather Flavors ) and generic functions. I wonder who wrote it.

;;; This file defines the base flavors for compiler objects and their protocols.
;;;
;;; The function of a compiler object is fairly simple: it must translate some
;;; program source into an appropriate object representation, and put that representation
;;; somewhere.
;;;
;;; A compiler object is made up of several components, which may be inter-related:
;;; - The Language Parser, which differentiates between various dialects of Lisp
;;; - The Target Architecture on which the object representation should run
;;; - The Compilation Environment
;;; - The Intermediate-Representation Optimizer
;;; - The Compilation Target, which actually disposes of the object representation
;;; (e.g. load it into virtual memory, or store it in a file)
;;;
;;; A Language Parser is responsible for all of the steps required to translate
;;; the source into an intermediate representation, including all source-to-source
;;; and source-to-pseudo-source transformations. [By pseudo-source we mean constructs
;;; which are similar in syntax to those of the source language, but which may not be
;;; understood correctly by an interpreter of the source language - "compiler-only forms",
;;; to put it another way.] The Language Parser may make use of the Target Architecture,
;;; and will certainly make use of the Compilation Environment.
;;;
;;; The task of the Target Architecture is to translate the program from its intermediate
;;; representation into an object representation that corresponds to the Instruction-Set
;;; Architecture of the machine on which the target is to be run. [Note that a "machine"
;;; can be a software emulation as well as a physical computer.] As previously stated, the
;;; Target Architecture may also be used by the Language Parser in the source-to-intermediate
;;; translation step. The Target Architecture may also interact with the
;;; Intermediate-Representation Optimizer, as described below.
;;;
;;; The Compilation Environment contains an evaluator and definitions that are needed at
;;; compile-time. Its main function is to support macroexpansion and compile-time
;;; error-checking.
;;;
;;; The Intermediate-Representation Optimizer does just what its name implies. It bases its
;;; decisions on advise from the user (e.g. the CL OPTIMIZE declaration). It may interact
;;; with the Target Architecture when the optimization is more easily implemented or disabled
;;; at this level, rather than during the intermediate-to-object translation.
;;;
;;; The Compilation Target's reponsibility is to put the object representation somewhere.
;;; This could either be the local Lisp virtual memory, a remote Lisp, either running on
;;; another piece of hardware or in a software emulation, or a file of some kind.
ahefner.livejournal.com | 1/9/12 1:45 PM

There's an updated Quicklisp client available now. This version fixes up several problems with the support for looking up metadata in CDB files . To get the new client, use (ql:update-client).

I've also updated the software available in Quicklisp. To get the update, use (ql:update-dist "quicklisp").

New projects:

• bitfield-schema - SIMPLE-BIT-VECTOR low level routines and convenient eDSL over it.
• cl-bloom - Simple Bloom filters with efficient hashing.
• cl-dropbox - Common Lisp Client for the Dropbox API.
• cl-gpu
• cl-murmurhash - 32-bit version of MurmurHash3.
• cl-rsvg2 - Bindings for RSVG Library.
• cl-sam
• cl-scribd - Commong Lisp Client for the Scribd API.
• cl-yahoo-finance - CL interface to Yahoo's finance API
• computable-reals - Computable real numbers.
• deoxybyte-unix
• do-urlencode - Percent Encoding (aka URL Encoding) library
• ext-blog - A BLOG engine which supports custom theme
• image - An image-drawing with some drawing primitives
• kl-verify - A library to generate simple verify code picture
• lisp-executable - Library for defining and creating executables that can be called from the Unix shell.
• pettomato-deque - A set of double-ended queue implementations.
• pettomato-indexed-priority-queue - A binary heap based priority queue implementation with efficient support for find, update, replace, and delete operations.
• priority-queue - A priority queue for Common Lisp.
• restas.file-publisher - A restas module which can publish static files
• stumpwm - A tiling, keyboard driven window manager

Updated projects: 3b-swf, 3bil, 3bmd, babel, bknr-datastore, cl-azure, cl-csv, cl-data-format-validation, cl-docutils, cl-fluidinfo, cl-llvm, cl-locale, cl-marshal, cl-oauth, cl-opengl, cl-quickcheck, cl-stomp, cl-string-complete, clack, clfswm, closer-mop, clpmr, clsql, cobstor, collectors, data-table, deoxybyte-gzip, deoxybyte-io, deoxybyte-systems, diff, doplus, fare-utils, gbbopen, gtk-cffi, hu.dwim.asdf, hu.dwim.delico, hu.dwim.logger, hu.dwim.perec, hu.dwim.rdbms, hu.dwim.reiterate, hu.dwim.stefil, hu.dwim.syntax-sugar, hu.dwim.util, hu.dwim.walker, idna, let-plus, lhstats, linedit, lisp-unit, lla, manifest, mime4cl, mixalot, monkeylib-html, relational-objects-for-lisp, restas, restas-directory-publisher, rfc2388, sclf, shuffletron, slime, static-vectors, stem, thread-pool, toot, trivial-features, trivial-garbage, uffi, wuwei, xcvb, yason, zcdb.

Removed projects: cl-bson-tim.

If you have a project that is available in Quicklisp, please check your system definition. Make sure it has useful metadata in it, like :description, :author, and :license. Several systems have empty description strings; for me, that's worse than a missing description.

SLIME has been updated with a new wire protocol. Please report any SLIME issues to the SLIME maintainers.

If you have any problems getting or using Quicklisp updates, let me know by email or on the Quicklisp mailing list .
blog.quicklisp.org | 1/8/12 3:29 PM

For lack of anything more interesting to say I will tell you about something that for some reason remained not entirely obvious to me until very recently.

When using ZMQ_PUB/ZMQ_SUB sockets and ZMQ_SUBSCRIBE message filters on one side of the interaction it is possible to separate the sending of messages from the sending of subscription channel information using multipart messages.

While working on Clubot with Sean Bryant earlier it became frustrating to consume the output of the bot since the messages coming out were coming out as single strings of JSON prefixed with a series of subscription symbols and strings as in:

:PRIVMSG :CHATTER "#somechan" "Origin_nick" {..[json]..}

So to consume the message symbols and strings have to be consumed from the beginning of the string until we can start to read JSON from an offset. This was no good.

ZeroMQ promises in the documentation of zmq_send that multipart messages will be delivered either as a complete sequences or not at all. Following this logic, we should be able to send subscription information up front in a single frame then follow up the body in a second and still have the full benefits of filtering using ZMQ_SUBSCRIBE with the added benefit of being able to slurp in the entire second message on the assumption that it contains JSON data.

So putting it all together. The publisher creates a message body and subscription information as two strings. It then sends the message as a pair of multipart messages with the subscription information first as in:

(zmq:send *pub-sock* header-message ZMQ:SNDMORE)

The ZMQ_SNDMORE flag indicates that this message will be followed by additional parts and should not be consumed individually.

The body is then written as usual:

(zmq:send *pub-sock* body-message)

The message will be published to any interested peers and the the pair of messages will be filtered by the contents of the first message with the body just tagging along.

To read a multipart message stream correctly we have to use the ZMQ_RCVMORE socket option to check for additional messages in the message stream. We can skip this step if our protocol is precise and we have foreknowledge of the number of message parts arriving, but doing so would leave a potential problem in the future.

The ZMQ_RCVMORE option when queried with zmq_getsockopt from a socket will return either 0 or 1 for either completing the multipart read (0) or having additional data available (1) as message components that were delivered with ZMQ_SNDMORE.

So we can receive the orignal example message when sent as a two-part multipart message following something like the following:

;; Still filter on the first part of the entire sequence (zmq:subscribe *sub-socket* ":PRIVMSG") (zmq:recv *sub-socket* subscription-header)

Now subscription-header will contain a string containing just the message prefix. If we use the same message it would be :PRIVMSG :CHATTER "#somechan" "Origin_nick"

We can then check to make sure that there is additional data to read and read the data component of the message or signal an error.

(if (= (zmq:getsockopt *sub-socket* zmq:rcvmore) 1) (zmq:recv *sub-socket* data-message) (error "No message followed subscription header!"))

If that form evaluates without error then data-message should contain just the data JSON without any more required to separate it! Isn't that exciting?

Happy cooking.

sshrkv.tumblr.com | 1/7/12 5:38 AM

Quicklisp uses two text files for information about project releases (releases.txt) and systems (systems.txt). Whenever information about a system was needed (for example, where its system file can be found), both files were loaded completely, from scratch.

I made it that way because it was pretty easy. People immediately noticed that it was also pretty slow, especially when using (asdf:load-system "...") instead of (ql:quickload "..."). The penalty for frequent loading and reloading of the metadata got worse as the number of Quicklisp systems grew.

Today I released a client update that can load metadata from a fast on-disk hash table, a CDB file . The big flat files are converted to CDB once, as needed, and thereafter getting metadata is super-speedy. On my laptop, the improvement for lookups is about 100x; your results will depend on the speed of your disk.

To get the update , use (ql:update-client) and restart Lisp.

If this change causes you any trouble, please let me know via the Quicklisp mailing list . blog.quicklisp.org | 1/4/12 4:52 AM

Last week I was doing some cleanup work (short holiday weeks are great for paying off technical debt), and was deleting some supposedly unused code. This was a pretty tedious process of running functions like slime-who-calls and slime-who-references, running git grep -i on the command line, and undefining functions in just the right order.

I’ve seen a lot of articles recently on static analysis of code, and spent some time playing with the introspection features of slime to identify unused code (short holiday weeks are also great for following a tangents). I ended up with a slow mudball of code that worked pretty well.

Warning, large images coming up.

The code itself is up on github, but there’s no ASDF system yet, so you have to load it manually:

(require :iterate) (require :alexandria) (require :swank) (load "~/lisp/static-analysis/static-analysis.lisp") (in-package :static-analysis)

An truncated example:

STATIC-ANALYSIS> (call-graph->dot :alexandria ) digraph g{ subgraph clusterG982{ label="PACKAGE STATIC-ANALYSIS" G983 [label="ENSURE-PACKAGE-LIST"] } subgraph clusterG949{ label="PACKAGE ALEXANDRIA.0.DEV" ... } G983 -> G995 ... G951 -> G950 } NIL

Here’s what it actually looks like:

The code currently scans all loaded code, and puts functions from each package in it’s own graphviz subgraph. The graph for an entire package for all loaded code isn’t really that useful, so I made another function to narrow it down. Here I’m specifying the list of packages to render, and the list of functions to show.

STATIC-ANALYSIS> (->dot (function-call-graph '(:alexandria) '(alexandria:rotate))) digraph g{ subgraph clusterG1109{ label="PACKAGE ALEXANDRIA.0.DEV" G1040 [label="ROTATE-HEAD-TO-TAIL"] G1049 [label="SAFE-ENDP"] G1054 [label="CIRCULAR-LIST-ERROR"] G1051 [label="PROPER-LIST-LENGTH"] G1042 [label="ROTATE-TAIL-TO-HEAD"] G1041 [label="ROTATE"] } G1040 -> G1051 G1051 -> G1049 G1051 -> G1054 G1042 -> G1051 G1041 -> G1040 G1041 -> G1042 } NIL

Some systems have very complicated call graphs. At work we do a lot with clsql, and the overall call graph even from one function can get complicated quick:

So I added a depth param to keep the graph smaller, let’s say 3:

STATIC-ANALYSIS> (->dot (function-call-graph '(:clsql-sys :clsql-sqlite3) '(clsql:map-query) 2))

Anyhoo, a fun toy, and I had a fun time writing it.

ryepup.unwashedmeme.com | 1/4/12 1:40 AM

In the REPL, +, ++, and +++ have as values the three most recently evaluated expressions. A quick way to evaluate the previous expression, especially handy in a REPL without input history, is

#.+

It's equivalent to (eval +).

(Thanks to Anton Kovalenko.)

lisptips.com | 1/3/12 3:50 PM

When writing applications based on SBCL for work or leisure I often find myself needing the final product to be an executable lisp core. SBCL has built-in support for this with save-lisp-and-die and external support through Buildapp and they work well for most cases.

The issue that I continuously ran head-first into was the behavior of the lisp image with regard to opening any shared objects at runtime after a restart. save-lisp-and-die has the option to disable or enable the reloading of these objects, but when it is enabled the object it will attempt to load will be searched for by an absolute path. So an application built with a library at /opt/local/lib/foo.so will fail on a system where the library exists at /usr/local/lib/foo.so even if the dynamic linker is configured to find the library foo.so at both paths.

To solve this problem we must first find the code responsible for reloading the objects in the first place and it is: SB-ALIEN::TRY-REOPEN-SHARED-OBJECT

As a parameter it takes an object that it should attempt to reload. If we're reloading a core on a machine it was not compiled on the paths of these objects will be absolute and absolutely incorrect. What can be done is the function can be intercepted and the path stripped from the absolute name of the object to just the last component. This will signal the dynamic linker to search for the named library in accordance with its configuration. Obviously, since this happens at run time, if the object can be found at the exact path it should be favored over whatever would be found if left up to the dynamic linker.

The code to accomplish something like this would look almost exactly like this:

[Gist: https://gist.github.com/1549389]

(with-unlocked-packages (:sb-alien) (let ((function (symbol-function 'sb-alien::try-reopen-shared-object))) (setf (symbol-function 'sb-alien::try-reopen-shared-object) #'(lambda (obj) (declare (type sb-alien::shared-object obj)) (let ((path (sb-alien::shared-object-pathname obj))) (when (pathname-directory path) (unless (probe-file path) (let ((sub-path (make-pathname :name (pathname-name path) :type (pathname-type path)))) (setf (sb-alien::shared-object-pathname obj) sub-path (sb-alien::shared-object-namestring obj) (namestring sub-path)))))) (funcall function obj)))))

This code can sit in a helper outside of the dependency chain configured by ASDF and be loaded into the image only when producing a core either programmatically or with an explicit —load or —eval  during the build step. As long as the patch ends up in the resulting image that specific class of headaches should go away.

sshrkv.tumblr.com | 1/2/12 7:03 AM

Here's a function to get the underlying array on which a displaced array is based:

(defun undisplace-array (array) "Return the fundamental array and the start and end positions into it of a displaced array." (let ((length (length array)) (start 0)) (loop (multiple-value-bind (to offset) (array-displacement array) (if to (setq array to start (+ start offset)) (return (values array start (+ start length))))))))

From an article by Erik Naggum.

lisptips.com | 1/1/12 5:00 PM

Matthew Snyder has a great introductory post on his blog where he converts the Mustache spec into a runnable fiveam test suite. Very cool stuff - I hope he posts more (-:

boinkor.net | 12/31/11 12:16 AM

In POPL '87: Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages , pp.

www.topix.net | 12/30/11 5:21 PM

In defmethod lambda lists, required parameters that aren't explicitly specialized default to specializing on the system class t. But there's a difference between an implicit and explicit specialization on t. The hyperspec explains:

The expansion of the defmethod macro "refers to" each specialized parameter (see the description of ignore within the description of declare). This includes parameters that have an explicit parameter specializer name of t. This means that a compiler warning does not occur if the body of the method does not refer to a specialized parameter, while a warning might occur if the body of the method does not refer to an unspecialized parameter. For this reason, a parameter that specializes on t is not quite synonymous with an unspecialized parameter in this context.

This makes a difference in Clozure CL; here's what you get if you don't use an implicitly specialized required parameter:

(defmethod foo (bar) 42) ;Compiler warnings : ; In (FOO (T)) inside an anonymous lambda form: Unused lexical variable BAR #

There is no warning with an explicit specialization:

? (defmethod bar ((baz t)) 42) # lisptips.com | 12/30/11 3:47 PM

Logically speaking, POSITION with trivial :KEY and :TEST arguments should be much faster on bit-vectors than on simple vectors: the system should be able to pull one words worth of bits out of the vector at a single go, check if any are set (or unset), and if so locate the one we're interested in -- else going on to grab the next word.

Practically speaking, no-one who needed fast POSITION on bit-vectors seems to have cared enough to implement it, and so until yesterday (1.0.54.101) SBCL painstakingly pulled things one bit at a time from the vector, creating a lot of unnecessary memory traffic and branches.

How much of a difference does this make? I think the technical term is "quite a bit of a difference." See here for the benchmark results. First chart is from the new implementation, second from the new one. Other calls to POSITION are included for comparison: ones prefixed with generic- all go through the full generic POSITION, while the others know the type of the sequence at the call-site, and are able to sidestep a few things.

So, if you at some point considered using bit-vectors, but decided against them because POSITION wasn't up to snuff, now might be a good time to revisit that decision.

Gory details at the end of src/code/bit-bash.lisp, full story (including how the system dispatches to the specialized version) best read from git.

Also, if you're looking for an SBCL project for next year, consider the following:

• Using a similar strategy for POSITION on base-strings: on a 64-bit system one memory read will net you 8 base-chars.
• Using similar strategy for POSITION on all vectors with element-type width of half-word or less.
• Improving the performance of the generic POSITION for other cases, using eg. specialized out-of-line versions.

Happy Hacking and New Year!

random-state.net | 12/30/11 11:35 AM

A Samsung Electronics' Galaxy Tab 10.1 is displayed at the showroom of its headquarters in Seoul, South Korea, Friday, Dec.

www.topix.net | 12/30/11 8:52 AM

A Samsung Electronics' Galaxy Tab 10.1 is displayed at the showroom of its headquarters in Seoul, South Korea, Friday, Dec.

www.topix.net | 12/30/11 8:52 AM

Clozure CL was forked from Macintosh Common Lisp in 1998 and the development has been entirely separate since.

www.topix.net | 12/29/11 2:58 PM

They say that famous deaths come in threes. That's no doubt just an artifact of our strange sense of coincidence, but after Jobs and Ritchie, tonight we learn of the death of John McCarthy , AI pioneer and creator of LISP.

www.topix.net | 12/27/11 11:02 PM

John Wiegley 's ledger is a popular double-entry accounting system with a Unix command line interface.

What many people don't know is that version 3 of ledger was written in Common Lisp. This version was never made into an official release. In a FLOSS weekly podcast , Wiegley explains (31:00) that Common Lisp wasn't the best choice for ledger's users.

I emailed John to learn more about this. He replied that there were only two major problems: building cl-ledger was more difficult than building ledger, and that cl-ledger could no longer be scripted from the command line. In effect, the Common Lisp REPL had stolen the place of the Unix command line as ledger's interface.

cl-ledger was written in 2007, and there are now good solutions to these problems. ASDF works well as a build system, but before Quicklisp , dependency management for Common Lisp applications was difficult. Quicklisp solved the biggest outstanding problem in building Common Lisp applications. (PS - you can give Zach a Christmas gift for his work on Quicklisp)

Didier Verna 's Command-Line Options Nuker is a widely portable Unix CLI library with many features that you can use to build command-line driven Common Lisp applications. carcaddar.blogspot.com | 12/24/11 7:27 PM

At fun4j's core there is a lambda-to-JVM bytecode compiler. Thanks to some optimization techniques like tail code optimization the compiler produces code that runs as fast as hand optimized Java code.

www.topix.net | 12/24/11 10:20 AM

Clozure CL is a fast, mature, open source Common Lisp implementation that runs on Linux, Mac OS X and BSD on either Intel x86-64 or PPC.

www.topix.net | 12/24/11 6:16 AM

You can get SBCL binaries from www.sbcl.org and that works pretty nicely. However, if you use M-. in slime to jump to the definition of a SBCL-defined function (e.g. sb-ext:run-program or cl:car), you might get something like this:

xach.livejournal.com | 12/24/11 3:43 AM

A common complaint from a co-worker is not being able to find relevant library functionality. We have libraries that do some tasks well, but if you haven't used it before, how are you to know that it is there. More over, how do you find what you are looking for from all of the available utility libraries currently loaded.

After seeing Peter Seibel's Manifest screencast. I was struck by the idea that you could index all the doc strings to provide a powerful search tool. I dont know about powerful yet, but this idea has turned into at least a search tool: Manifest-Search. This is the product of one days hacking and so should not be construed as the end-all-be-all common lisp search tool, however, it is at least a step in that direction.

I would like to eventually get this integrated more fully with both quicklisp and manifest, but that is all in the future. I think it would be amazing to search for functionality I need, and get documentation for a library I have not yet installed, but is distributed by quicklisp.

russ.unwashedmeme.com | 12/23/11 8:44 PM

I’ve spent the last few hours dusting off my Common Lisp Growl client library. The last time I worked on it was before the Mac Growl Application supported GNTP (Growl Notification Transport Protocol).

Today, working on it, I’m not quite sure what’s up, but I am not succeeding in communicating with the server using encryption. I’ll have to look more closely. Last time that I worked on it, I extended Ironclad, but I never got those changes pushed fully into Ironclad’s main line. But, I think I’m using the same version of Ironclad that I was using when I tested against the Windows Growl Application. *shrug*

I’ve also run into a snag with the Callbacks. Essentially, your Lisp program could get a callback when the user has clicked on your Growl notification. This actually works except for the fact that I am calling READ-SEQUENCE into a buffer that is longer than the message. The server, I believe, is supposed to close the socket after the callback. But, it does not. So, I am stuck waiting for more bytes that will never come.

Now, I either have to do one of the following:

• refactor it to use READ-LINE instead
• switch from using USocket to using IOLib (and hope that :dont-wait works as expected)
• extend USocket to support SOCKET-RECEIVE even on TCP sockets

Anyone have a preference?

nklein.com | 12/22/11 6:42 AM

My IDNA library now supports decoding IDNA strings via the to-unicode function:

(to-unicode "xn-mller-kva.example.com") ;; => "müller.example.com"

That’s in addition to the regular encoding for unicode domain names:

(to-ascii "müller.example.com") ;; => "xn-mller-kva.example.com"

Sadly, I haven’t managed to get the logic for case-sensitive punycode encoding to work yet. But fortunately, IDNA domain name encoding doesn’t require that! Anyone looking for some low-hanging fruit-shaped lisp projects is welcome to add that! (-:

boinkor.net | 12/22/11 5:27 AM

From Matt Emerson on the Clozure CL mailing list:

Several people have wondered whether CCL or CCL-developed applications
would meet Apple's requirements for being distributed via the Mac App
Store.

There's only one way to test that...you have to submit an app to the
store. So I did. It was accepted.

http://itunes.apple.com/us/app/clozure-cl/id489900618?ls=1&mt=12
xach.livejournal.com | 12/21/11 3:20 AM

I use defstruct a lot, even when execution speed or space usage isn’t an issue: they’re better suited to static analysis than standard-objects and that makes code easier to reason about, both for me and SBCL. In particular, I try to exploit read-only and typed slots as much as possible.

Structures also allow single-inheritance – and Christophe has a branch to allow multiple subclassing – but don’t come with a default protocol like CLOS’s make-instance/initialize-instance. Instead, we can only provide default value forms for each slot (we can also define custom constructors, but they don’t carry over to subtypes).

What should we do when we want to allow inheritance but need complex initialisation which would usually be hidden in a hand-written constructor function?

I’ll use the following as a completely artificial example. The key parts are that I have typed and read-only slots, that the initialisation values depend on arguments, and that we also have some post-processing that needs a reference to the newly-constructed structure (finalization is a classic).

(defstruct (foo (:constructor %make-foo)) (x (error "Missing arg") :type cons :read-only t) (y (error "Missing arg") :read-only t)) (defun make-foo (x y) ;; non-trivial initial values (multiple-value-bind (x y) (%frobnicate x y) (let ((foo (%make-foo :x x :y y))) ;; post-processing (%quuxify foo) foo)))

The hand-written constructor is a good, well-known, way to hide the complexity, as long as we don’t want to allow derived structure types. But what if we do want inheritance?

One way to work around the issue is to instead have an additional slot for arbitrary extension data. I’m not a fan.

Another way is to move the complexity from make-foo into initialize-foo, which mutates an already-allocated instance of foo (or a subtype). I’m even less satisfied by this approach than by the previous one. It means that I lose read-only slots, and when I don’t have sane default values, typed slots as well. I also have to track whether or not each object is fully initialised, adding yet more state to take into account.

For now, I’ve settled on an approach that parameterises allocation. Instead of calling %make-foo directly, an allocation function is received as an argument. The hand-written constructor becomes:

(defun make-foo (x y &optional (allocator ’%make-foo) &rest arguments) ;; the &rest list avoids having to build (a chain of) ;; closures in the common case (multiple-value-bind (x y) (%frobnicate x y) ;; allocation is parameterised (let ((foo (apply allocator :x x :y y arguments))) (%quuxify foo) foo)))

This way, I can define a subtype and still easily initialize it:

(defstruct (bar (:constructor %make-bar) (:include foo)) z) (defun make-bar (x y z) (make-foo x y ’%make-bar :z z))

The pattern is nicely applied recursively as well:

(defun make-bar (x y z &optional (allocator ’%make-bar) &rest arguments) (apply ’make-foo x y allocator :z z arguments))

Consing-averse people will note that the &rest arguments are only used for apply. SBCL (and many other implementations, most likely) handles this case specially and doesn’t even allocate a list: the arguments are used directly on the call stack.

I’m sure others have encountered this issue. What other solutions are there? How can the pattern of parameterising allocation be improved or generalised?

www.pvk.ca | 12/16/11 1:29 AM