Drinkable Chicken

As you might recall, Liquid is my attempt at writing a Lisp interpreter, with the purpose of exploring some ideas I have had for a while, and to eventually produce a system that can be used to write non-trivial programs.

That last goal took a serious hit the other day, and I’ll have to go back to the drawing board. The core interpreter, as it stands, is simply too slow. I know, premature optimization is evil and all that, but if simple evaluations take several seconds, it’s probably time for a critical look at the design, at the very least.

For example, I had a range function, defined like this:

(define (range n)
  (define (range-aux n acc)
    (if (<= n 0)
        acc
        (range-aux (- n 1) (pair (- n 1) acc))))
  (range-aux n ()))

(A Scheme version would look much the same, except pair would be called cons, and the empty list would be written as ‘(). None of the more interesting features of Liquid are in this example.)

(range N) produces a list of numbers from 0 to N, e.g. (range 5) gives (0 1 2 3 4), etc. As it turned out, this function was horribly inefficient; (range 10) needed ~3000 “evaluation steps”, and (range 1000) took over 13 seconds to complete.

As it turned out, the major culprit was <=. I foolishly figured I could implement = and < as built-ins, and derive the other comparison operators from that. So <= was defined as

(define (<= a b)
  (or (= a b) (< a b)))

This doesn’t look so bad, except that or is written in pure Liquid as well, and it’s pretty damn slow.

Rewriting <= to make it a builtin was easy, and made range much faster. This didn’t solve the general problem though; one of the big ideas of Liquid is that you can write “syntax” like or, and, case, cond, when, while, etc, in Liquid itself, without using macros. (Not to mention, all kinds of other stuff.) While it does work, apparently it makes code unacceptably slow. :-(

The way an “evaluation step” currently handles code and figures out what to do next, is hairy, partially due to the way rest args and keyword args are handled. I am now thinking of doing a rewrite with a different way to handle delayed arguments. Hopefully that will be faster…

(The implementation language for this version is D, by the way… so I was expecting more speed than with the Python prototype.)

(P.S. For whoever is interested, the current version of the interpreter can be found here.)

I am currently hacking on the latest incarnation of Liquid. This version is written in D.

(I chose D for various reasons, over languages like Java, C#, OCaml and ActionScript… maybe someday I’ll write more about that. It’s not impossible that there will be another implementation in one of those languages, by the way. But for now, it’s D. D 1.0 to be precise, as I am developing it on an old iBook G3 that runs Tiger. Yes, not the most efficient of setups… but it’s fun! :-)

D is OK as far as statically typed languages go. It has a lot of improvements over C, but is less anal than Java, and less of a mess than C++. :-) It can be low-level if you wish (e.g. it has pointers much like C), but some of the features and library functions are pretty high-level, almost Python-like. It comes with a decent standard library, Unicode support, garbage collection, modules, dynamic arrays, real strings, a foreach loop and much more.

Of course, the static typing bites me every now and then… Often the error messages are actual bugs, but sometimes it’s just the type system being difficult.

I do hope that in the future, I will be able to link with some C libraries… maybe some GUI stuff. Right now everything is command line, which I wanted to avoid, but that’s how it goes. (An implementation in ActionScript would fix this, but it would lack a command line, and would likely be much slower.)

Anyway, I recommend D if you need to use a low-level language that isn’t too painful. =)

For the past 2-3 months or so, I’ve been tinkering with a Lisp dialect called Liquid. Current prototype is in Python, but the idea is that I will eventually port this to a different platform; maybe the JVM, .NET, or Actionscript. (I should probably write a separate post discussing these choices.)

The prototype works, to some extent, and can be played with, for those who like this kind of stuff. (Just run the liquid script to get a REPL… error handling etc isn’t too good, but this should be better in future versions.)

Constructive criticism and ideas welcome (but keep in mind that this is just a prototype and that I am not an old Lisp hand :-).