[Mini Kanren] Benchmarking different substitution data structures

In logic programming, a substitution is a mapping from logic variables to values (including other logic variables). Logic programs are composed of goals, with the type signature Subst => Subst* — i.e. it might fail (thus generating 0 possible substitution), succeed once, or succeed multiple times, or even an infinite number of times.

It is necessary for substitutions to behave as values — if you take a substitution, and add a binding, you better get a new substitution, rather than do the modification in place, because that substitution might be used by other goals. In Lisp, the traditional data structure for this is the association list: a list of lists, where the cars (first elements) of each inner list are the keys. Clojure takes Phil Bagwell’s Hash Array Mapped Trie and adds persistency on top of it, to the effect that you have a copy-on-write trie map, with logarithmic rather than linear lookup times.

Technorati Tags: , , , , , , ,

Continue reading

Gnoetry 1-2-3

I’ve been fascinated with Jon Trowbridge and Eric Elshtain’s Gnoetry for quite some time, but have until recently contented myself with watching from the sidelines. There are several reasons — being busy with other projects, and mostly that the code is rather well-hidden from the public eye; there is a Subversion repository, but one has to jump through some hoops to get to it (I forgot how I got to the code; I think I might have emailed Jon about it).

After you get the code, there’s still the matter of setting things up. And SVN is a rather messy interface to use if one does not have commit access…

I’ve decided to take the plunge, though. I used git-svn to make a clone of the official repository, committed some usability improvements to a bugfix branch, and pushed the code to GitHub. Get it here (the master branch is Jon’s latest SVN code; the bugfix branch has a Makefile added that let you run Gnoetry by simply running ‘make’ — it does all the setting-up for you. ‘make clean’ cleans up the generated files).

Now, time to fix that unreleased-mutex-on-exit bug…

Technorati Tags: , , , ,

Discovering Rosetta Code

I discovered Rosetta Code over the weekend. It bills itself as a programming chrestomathy site, offering a place to learn, compare and contrast different programming languages by reading and writing solutions to different programming tasks.

So far, I’ve been using it to brush up on my Clojure, Pure and Scala fu. I’ve just added the Pure category, so the examples are a bit sparse still. If you want to see the solution to any particular problem in it, just drop me a note.

Also check out the stair climbing exercise I borrowed from Chung-chieh Shan’s Lambda the Ultimate post.

[Packaging] Ships that pass in the night

Amusing (or depressing?) trail of bug-hunting:

  • During the package review process for pure, we discovered that a dlsym-ed strcmp does not produce the right result on F-12
  • The same problem turned out to be the case with avahi-sharp; its dlsym-ed strlen produces incorrect results, causing segmentation faults in Banshee (which uses it through mono-zeroconf)
  • Switching zeroconf to use avahi through DBUS would fix things, but when poking through the sources, it is discovered that its developer has been bundling a private copy of NDesk.DBus, against Fedora guidelines and the wishes of NDesk.DBus upstream
  • Said upstream has not released a stable release since January 2008, though the code is still actively developed in Git, and there is a (quiet) bugtracker on Launchpad. Nobody appears to be using the upstream code; even openSUSE Factory is still using 0.6.1 (not even the latest 0.6.1a).
  • Meanwhile, Fedora’s ndesk-dbus carries a patch, at the request of sugar-sharp, that changes the public API by adding some public methods. The API version, however, is unchanged.

I’ve notified upstream, as well as the zeroconf developers. The Fedora bugs affected are linked from the upstream bug report as well. Meanwhile, let’s hope the glibc bug gets fixed soon too. It’s nice having a seconder, especially as the test case is much smaller than the test case I submitted for pure.