[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

Advertisements

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.

Logic programming on the JVM

Just a quick post (the time is rather late) to note that my port of the Mini Kanren logic programming system to Scala is now available for download (and bug reports) on GitHub; for the scaladoc API documentation and a presentation discussing the porting effort, visit the project homepage.

It has an almost-complete numerical stack — the missing arithmetic relations are not coded yet because I was documenting and/or getting larger test cases to work — and likewise with list-processing support. The years-old stack overflow problem I initially attributed (when taking a programming language course, and having no time to debug thoroughly) to Java’s lack of TCO turns out to be fixable by some judicious call-by-name optimizations.

Having just discovered metalua and its macro goodness, I’d say that after bringing Kanren to the JVM, the next step would be to have a C-embeddable Kanren written in metalua. There might be some performance snags, though — the Scala port is currently about 3x slower than Mini Kanren running on Petite Chez Scheme.

Technorati Tags: , , , , , ,

OOP in Lua: abstract methods

I discovered Python’s delightful abc module (introduced in PEP 3119) a while back, and have been wondering how a similar functionality could be introduced to other dynamic languages (e.g. Lua and Ruby).

Being more familiar with the former, over the weekend I decided to try and write an equivalent module. Two problems came to mind:

  • Python uses an @abstractmethod decorator to mark an otherwise-normal function definition. While a decorator pattern can be used in Lua (though not a standard practice), this Python decorator works by setting an attribute in the function it decorates:

    funcobj.__isabstractmethod__ = True

    This is not an option in Lua, because functions don’t have individual metatables.

  • Python has a standard way of doing OOP, and the enforcement that an instantiated class does not contain any abstract method is done in the __new__ method of the ABCMeta metaclass. Contrast to Lua, where OOP is normally done in an ad-hoc manner — and even the LOOP library provides several OOP inheritance mechanisms.

The solution I adopted is delightfully simple: the abc module provides two functions: an amethod function that throws an exception no matter what arguments it is passed, and a verify function that takes a classname, and reflects on the members (using loop.cached.allmembers if possible, falling back to pairs if loop is not installed) and check if any of them is equal to amethod.

This works even on simple tables, though it shifts the responsibility a bit to the programmer: unit tests should be used to verify each created class. As a fallback, attempts to use the abstract methods will fail at runtime, but that’s taking dynamism a bit too far…

Still working out how to get the Pythonic behavior (instantiating a class with some abstract members should fail) when using LOOP. Meanwhile, try it out for yourself and make sure to file bug reports!

Technorati Tags: , , , , , , ,