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.)