SExpr: Lisp Interpreter

An Eccentric Anomaly: Ed Davies's Blog

Starting about this time last year then through the winter I wrote and played with a little Lisp interpreter. I didn't mean to, honest.

What happened was I wanted to write a list: specifically, a list of the bits of timber and fastenings I'd need for my house frame. The idea was to do a quick-and-dirty domain specific language (DSL), implemented in Python, which would allow parts and sub-parts to be defined then expanded to get lists of what needed to be ordered at different stages.

This is quite simple but not quite as trivial as it first looks. E.g., having worked out that one application needs 162 mm long bolts and another 167 mm ones you want to amalgamate them into the right total number of 180 mm ones.

Unlike many programmers, I like languages with significant indentation, modulo some concerns about confusion with tab expansion, so I'd been giving some thought to DSLs like that and decided to first write a little module to read in generic significantly-indented code. An S-expression-like representation of the result seemed natural.

(I did consider some sort of RDF-triple representation but decided it'd need more thinking through than I was willing to give to a quick bit of code like this. Still, a language represented in and manipulating triples in the way that Lisp does for S-expressions is intriguing.)

Having got the basic reading working I, more or less as a joke, implemented a bit of Lisp and it just grewed. It doesn't even have a name - I'll just refer to it as “sexpr” after the main module (actually sexpr/, short for S-expression.

In many ways it's a toy. Firstly, the error reporting is horrid: it is, I think, quite good at picking up errors but the resulting messages are mostly just Python stack traces from asserts failing. Secondly, it doesn't do any form of tail-call optimization so processing a long list without use of built-ins like map and reduce is likely to blow its (Python's) little stack. Fortunately, my house doesn't need very long lists.

I'll do some separate posts on different aspects of sexpr as I feel like it.