Quasiquote

Today I added support for “non-hygenic” macros to my interpreter. I decided to implement the quasiquote feature of Lisp, which is very useful for writing macros, so that I can more comfortably implement more special-forms such as let.

I found an implementation of quasiquote here. My interpreter does not support all the functions it uses so I couldn’t drop it in. It was rather more complicated than I expected and I do not understand exactly how it works. I have written my own version:

(define (expand-quasiquote x)
  (if (pair? x)
      (if (is? (car x) 'unquote)
          (cadr x)
          (list 'cons
                (expand-quasiquote (car x))
                (expand-quasiquote (cdr x))))
      (list 'quote x)))

(define-macro (quasiquote x) (expand-quasiquote x))

(Note: is? is a pointer comparison roughly like Scheme’s eqv?)

I haven’t tested thoroughly, but it seems to work just fine. It uses simple recursive strategy: replace atoms by quotation of the atom, replace an unquote form by the raw argument of unquote so it can be evaluated, and replace non-unquoted pairs by the code to cons the car and cdr which are recursively handled. Quasiquotes inside unquotes inside quasiquotes inside … are automatically handled by macro expansion. It doesn’t handle vectors since the interpreter doesn’t have them yet. It is also doesn’t handle unquote-splicing which might complicate matters.

Am I missing something?

The dataflow language

Turns out that the book I wanted, Lisp in Small Pieces, was already checked out. A little blue book, “Lucid, the Dataflow Programming Language” caught my eye, so I picked it up instead. I’d heard about the language before and found the imperative style but declarative semantics quite intriguing.

I’ve been warming to the idea of lazy evaluation recently; I might try it in my Lisp. It has the nice effect that you can replace a function call with the function body with argument expressions inserted as-is, which is not strictly true with strict evaluation, because it forces the arguments to be evaluated first. This is nice because you can define control structures using plain old functions, they do not even have to be built into the language core.

I’ve been thinking how it might be possible bring some Lucid features into Lisp. For example, a looping construct which iterates the loop variables with Lucid-like semantics (re-ording doesn’t matter). SICP demonstrates infinite lazy streams, which are the same sort of thing as Lucid variables.

I haven’t read much yet due to work and tiredness. I might make some progress this weekend if I can stop playing Continuum!

The rock has started to roll (time to lose some moss)

For a long time I’ve been thinking about getting a blog, so here goes!

My current project is developing a Lisp-like language, in Lisp, with a bootstrap interpreter in C. I hope to generate machine code and executable binaries without using an external assembler or linker.

Here is the current version of the bootstrap interpreter. It’s a bit rough around the edges and is missing many important features. At the moment all it does is run some demo programs (factorial, gcd, map, reduce, etc.). I just recently got the garbage collector working so I can only run a collection in the top-level loop, since most of the code is not GC-safe yet.

amp-2006-11-19.tgz