Clicky

Harry R. Schwartz

Software engineer, nominal scientist, gentleman of the internet. Member, ←Hotline Webring→.

· 1B41 8F2C 23DE DD9C 807E A74F 841B 3DAE 25AE 721B

Implementing Blueprint

Published 24 Oct 2015. Tags: computer-science, lisp, ruby.

I started implementing a little toy language about a month ago. It’s got enough functionality now that I’m willing to stick it up here on my blag.

It’s called Blueprint. It’s an interpreted language similar to Scheme, roughly based on the metacircular evaluator described in §4.1 of Structure and Interpretation of Computer Programs. It’s implemented in Ruby (it’s a prototype, so I’m not concerned about performance) and fairly well-tested.

Its syntax is based on s-expressions. Comments start with a #, like in most scripting languages, instead of the traditional Lisp ;.

It’s a Lisp-1, so variables and functions share a namespace.

I knew that I wanted to include macros. I opted for non-hygienic macros, since (1) they make it easy to play with nifty techniques like anaphora and (2) the implementation is much simpler. However, Blueprint doesn’t have a gensym yet,1 so its non-hygienic macros are really just downright filthy. Use caution.

It includes the usual quasiquoting/backquoting operators:

(defmacro (let bindings body)
  `((lambda ,(map first bindings)
      ,body)
    ,@(map (lambda (binding) (first (rest binding))) bindings)))

There’s no concept of phase separation, so everything happens during evaluation. This means that there’s no static analysis performed on the code before it’s handed off to the evaluator. Since there’s no separate macro-expansion phase, macros are expanded at run time. This is dreadful for performance but doesn’t seem to generate incorrect results. I’ll admit that I don’t know exactly what sorts of incorrect results might be caused, but it smells a bit suspicious to me.

An interesting side-effect of doing macro-expansion at run time is that macros can be passed around and apply‘d as first-class objects. I decided to carry that philosophy a bit further and made special forms (like apply or cons) first-class, too, so you can say wacky stuff like (apply eval '((foo bar baz))).

It’s got a tiny standard library, written in Blueprint, which includes just enough of a testing framework to test itself.

I followed current fashion and renamed car and cdr to first and rest. They’re just better names.

I’m really pleased with it! It’s the first compiler-ish thing I’ve written since grad school, and it was a ton of fun to implement. It’s just a learning exercise, so I don’t mind that its performance is atrocious, and I’m not really planning on extending it too much further.

One of these days, though, and maybe before too long, I’d like to get my hands on a copy of Quiennec’s Lisp in Small Pieces so I can learn how to build a full Lisp compiler the right way.

  1. My understanding is that Common Lisp’s implementation of gensym leverages the package system by, effectively, creating a unique package for each generated symbol. Blueprint doesn’t have a concept of packages (or any namespacing mechanism at all, for that matter), so that ain’t gonna work. My alternative idea is to prefix each gensym with a character that the parser can’t handle (like &), but that just feels like too much of a hack. Blargh.