Implementing Scheme in Python

My first approach for the parser was to use PLY, which I’ve used before. Having been spoiled by the excellent Instaparse library for Clojure, upon returning to PLY I found the library’s interface relatively clumsy and abstruse.

Then I thought I’d try a regex to parse everything, since Scheme’s base syntax and grammar are so simple. The following regex actually worked well for awhile:

pat = """^\s*\((?P<list>.*)\)$   # Something beginning/ending with parens, or
         |
         (?P<bool>(\#t|\#f))\s*  # A boolean true/false value, or
         |                       # An atom starting w/ a letter or arithmetic op:
         (?P<atom>[a-zA-Z\+\-\*\/]+[a-zA-Z0-9\+\-\*\/]*)\s*
         |
         (?P<num>[0-9]+)\s*"""   # Or, a positive natural number.

(I had not gotten to negative or floating point numbers at this stage of the project.)

Expressions of the form (+ 1 2 (+ 1 1 1)), for example, parsed correctly. However, the regex didn’t handle lists that nested in other than the last position, for example, (+ (* 2 3) 4). It might be possible to do the whole problem with regular expressions, but at this point I decided to look for a nice modern parser library that let me write down the grammer in EBNF notation and simply returned a parse tree when given a valid expression. I found Lark, which is roughly as featureful as Instaparse and worked well. Here’s the Lark grammar as it currently stands:

start  : _exprs
_exprs : _e* _e
_e     : ATOM
       | _num
       | BOOL
       | list
TRUE   : "#t"
FALSE  : "#f"
BOOL   : TRUE | FALSE
list   : "(" _exprs? ")"
INT    : /[-+]?[0-9]+/
ATOM   : /[a-zA-Z]+[a-zA-Z0-9\-\?]*/
       | /[\*\/\=\>\<]/
       | /[\-\+](?![0-9])/
FLOAT  : /[-+]?[0-9]+\.[0-9]*/
_num   : INT | FLOAT
%import common.WS
%ignore WS

Note that while libraries like Lark and Instaparse are a nice way to turn out a powerful parser quickly, Norvig’s lis.py just splits the inputs on open/close parens and uses them to increase/decrease nesting level as they appear. The approach to parsing numbers is also elegant: try to parse it as an integer; if that fails, as a float; otherwise, it’s a symbol (what my grammar calls ATOM). I suspect that using a “real” parser makes it easier to add more syntax to your language if needed, though.

Once Lark parses an expression, I convert to my own internal representation before evaluation (function convert_ast). I did not use objects to represent lists, atoms, etc., but just simple tuples and lists:

It might be more idiomatic Python to use objects, but I’m more used to thinking in terms of nested structures of base data types (lists, tuples, dictionaries), which have the advantage of being easily printable while debugging.

Here’s an example expression, parsed with Lark and then converted into my internal representation:

Evaluation turned out, not surprisingly, to be where most of the work is; specifically, the individual cases for special forms. These were:

• quote
• cond / if (I implemented these separately but, had I implemented macros, I might implement one in terms of the other)
• define
• lambda
• or
• and

Aside from these, there was code for normal function application rules, with a slight variance between internally-defined functions and functioned defined by the user with define.

I did not, as Paul Graham did, attempt to find the minimal subset of language elements needed to bootstrap a complete Lisp, though that is certainly an interesting exercise. My goal was to get my tests green in a straightforward way, as described below.

The Print stage needed to convert the internal representation of the evaluated result to a string, both for a user running a REPL, and for my unit tests. This turned out to be simple enough that I can put the entire function here:

def printable_value(ast):
    k, v = ast
    if k == 'int' or k == 'float':
        return str(v)
    if k == 'bool':
        return {True: "#t",
                False: "#f"}.get(v)
    if k == 'intproc':
        return "Internal procedure '%s'" % v
    if k == 'atom':
        return v
    if k == 'list':
        return '(' + ' '.join([printable_value(x)
                               for x in v]) + ')'
    if k == 'nop':
        return ''
    if k == 'fn':
        (fn_name, _, _) = v
        if fn_name == 'lambda':
            return "Anonymous-function"
        return "Function-'%s'" % str(fn_name)
    raise Exception('Unprintable ast "%s"' % str(ast))

The primitive data types (int, float, bool and atom) are obvious enough; intproc and fn are for internally-defined and user-defined functions, respectively; finally, nop is for when you don’t want any value shown to the user (i.e., after one enters a define expression, there is no output printed before the next prompt):

scheme> (define a 3)
scheme>

I used a fairly strict test-driven development workflow for this project: write just enough new test code to fail; write just enough production code to get the test to pass; then refactor. This workflow generally serves me well for harder problems where I’m unlikely to see the best way to do things from the outset and I expect to make many improvements: I know the tests will have my back when I make changes. This turned out to be the right approach, since I had to pivot several times.

I didn’t just use tests drive the code forward, but let SICP drive the tests forward as well. When I needed the next thing to work on, all I had to do was turn forward a few pages in the book, and the page count gave me a measure of my progress.

A few of the tests, with the corresponding page numbers:

# Adapted from SICP p. 8:
t("(define pi 3.14159)")
t("(define radius 10)")
t("(* pi (* radius radius))", "314.159")
...
# p. 19:
t("(define x 7)")
t("(and (> x 5) (< x 10))", "#t")
...
# p. 37
t("""(define (fib n)
       (cond ((= n 0) 0)
             ((= n 1) 1)
             (else (+ (fib (- n 1))
                      (fib (- n 2))))))""")
t("(fib 5)", "5")

Here t (a very short function name since it’s used so many times) is a testing function which evaluates the code supplied in the first argument, using the current “environment” (scope). If a second argument (a string) is supplied, it also asserts that the code in the first argument evaluates to the second.

One of my favorite things about this project was when I started writing nontrivial tests which already passed, because enough of the language had been implemented already. This happened more often as the project progressed, and it made me feel like I’d implemented a “real” language, an oddly compelling feeling.

The code, in its entirety, can be found here.

For example, I don’t have strings yet in my implementation!

Implement Python interop and shell features. This could be genuinely fun and useful, but there’s already a fairly full-featured Lisp skin for Python called Hy.

Do it again, but in a faster, lower-level language. Python is relatively slow compared to Clojure for long-running programs, and slower than Common Lisp or C for program startup. I’ve been wanting to dust off my C chops, and this would be an excuse to do so, though C is a bit primitive compared to, say, Rust. (Go is not to my taste so I wouldn’t pick it for a fun project like this one.) So, either an excuse to learn Rust or to improve my C chops. Which leads me to the final question: would I rather implement Lisps, or program in them? Up until now it has been the latter, but after the past few weeks I can definitely taste the appeal of the former.