Thursday, May 31, 2012

My attempt at a small Lisp

On Tuesday, I decided to check whether I could implement a small Lisp-like language in two hours.  Turns out I could.  The attempt is saved as the first commit in the Sparse repo, and supports arithmetic, definitions, conditionals, and lambdas.  I'm fairly sure it is Turing complete, although I haven't proven it.

Since then, I've been adding little bits, primarily working towards defmacro (which I've now implemented -- yay!).  A few interesting things that caught my attention:

  • The core language can actually be very small, with most functions being specified as functions in the runtime environment.  Most still need to be defined in Python at this point and end up calling eval, but it's nice to see that eval doesn't need to be aware of them.
  • The way type information works is different from what I thought.  I had initially been stripping it when passing things to functions -- this made it easier to pass things to Python functions, but completely broke down when I started implementing quote.  Now everything carries its type information with it; I think I've finally understood what "code is data" is about.
  • I had been messing around with how to separate special forms and macros from normal functions when calling them and eventually decided to go with a bit of a hack: if the first element of a list is a ~, the arguments are passed in as they are; otherwise, they are evaluated.  This means that (~f a b c) is the same as (f 'a 'b 'c).  I like how explicit this is, although it does lead to some strange errors.
  • The way quasiquote works bugs me a little, although it's also funny.  While unquote looks like a function, it isn't actually anything meaningful: quasiquote just goes through the list and checks for things that look like calls to unquote and unquote-splice.  This has the side effect of making quote not need nor allow a ~ before it, which I'm not sure I like.
  • Writing a Lisp interpreter that feels powerful is really, really easy.  The sense of accomplishment of writing a function that can be used in a different language is much greater than just of writing a function.
As for the language itself: I haven't gotten around to writing any kind of specification yet, although I should probably document it at least a little.  The main unusual bit so far is the ~ magic, and that's just syntactic sugar.  

I'm not really sure what to do next with it -- I think support for executing files (and fixing the multiple statements bug) is probably the next step, and then perhaps compilation to Python bytecode and self-hosting.

By the way, here's the code of defmacro:

    (~define defmacro
      (~lambda (name args . body)
        (eval `(~define ,name
                 (~lambda ,args
                   (eval ((~lambda () ,@body))
                         (parent (this-env)))))
               (parent (this-env)))))

This defines a macro that takes a name, argument, and any number of body statements, then creates a function of the given name and taking the given args, and which evaluates the given body and then evaluates the result of that.  There's some environment changes going on to make sure things don't end up going out of scope just after they are defined.

No comments:

Post a Comment