Implementing Scheme in Python

Lately I've been a bit of a Lisp kick again, reading On Lisp and Practical Common Lisp, working problems and re-casting my Clojure-based blog software into Common Lisp to see how that goes. The urge to do these things caught me somewhat by surprise: in the past few years I haven't done much programming outside of my day job because I've been focused more on painting and drawing. It seems, though, that these things are cyclical and right now I'm in the grips of Lisp mania again.

This cycle goes back to the mid-1980s when I was a college student studying physics and learning how to program. It's hard to say how I got the Lisp bug initially. I remember reading Douglas Hofstadter's explanation of recursive Lisp functions; hanging out near the AI workstations in the basement of the Madison Academic Computing Center where I worked (the sans-serif Lisp program printouts looked way better than anybody else's output); and reading about AI and Lisp on Usenet. At any rate, I managed to pick up a copy of PC-Lisp, a port of Franz Lisp to IBM PCs which apparently is still a thing after all these years. Somewhat astonishingly, the interpreter ran on my underpowered IBM PCjr, loading from floppy disk in half a minute or so. I remember how even fairly small programs would pause for several seconds while the garbage collector did its thing. This interpreter, along with a Lisp textbook I picked up somewhere, was enough to get me started learning about atoms, lists, quote, car and cdr, symbolic computing, and simple recursive algorithms.

I also wrote a small s-expression parser in Turbo Pascal on the same PCjr as a way of graphing arbitrary math functions of two variables. I had no compiler class but my roommate taught me enough about finite state machines, lexers, parsers, etc. to be dangerous… enough knowledge to get my grapher up and running. (I wish I still had some of these old programs, but they vanished when I "lent" the computer and all my diskettes to a friend; they are probably landfill somewhere.)

This all subsided for several years while I got sucked into physics, then painting, then capoeira, then physics, then painting, then software engineering in C, Perl, and Python. In the early aughts I got interested in Paul Graham's writing, which led to a few skirmishes with Common Lisp every couple of years, and ultimately to me getting totally hooked on Clojure starting in 2011.

I intend to write more about what makes Lisps in general compelling for me¹ and why I've returned to it over and over throughout my career. In the mean time….

Happily, my Lisp mania has crested coincidentally with Chicago Python teacher David Beazley announcing another class on The Structure and Interpretation of Computer Programs, a classic MIT computing text based on a dialect of Lisp called Scheme, and I managed to get on the list before it filled up. Since it's been awhile since I've written much Python, I thought I'd warm up for the class by trying to write a small Scheme implementation in Python. My hope was to refresh my memory of the basics of Scheme, improve my slightly-dusty Python, and have fun.

Researching this post (after most of the code was done), I noticed that there are a ton of small Lisps written in Python (including two I worked on the better part of a decade ago). One that stuck out in my memory was Peter Norvig's hundred-odd-line Lispy, which is particularly striking in its elegance (in style, it reminds me of the Lisp programs in PAIP).

My plan for writing the interpreter was to follow the actual REPL stages: Read, Eval, and Print. Read would involve parsing input expressions and turning them into data structures to be evaluated; Eval would be a (presumably recursive) step whereby, for function calls, arguments would be Eval'ed first, with the results handed to the appropriate code implementing the actual function, implemented either in Python (for a few primitive functions) or, eventually, through user-defined functions. An exception to the argument evaluation rule would have to be made for a few special forms, which would have to be handled on a case-by-case basis.

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.

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

(define (abs x)
  (if (< x 0)
      (- x)
      x))

Tree(start,
     [Tree(list,
           [Token(ATOM, 'define'),
            Tree(list,
                 [Token(ATOM, 'abs'),
                  Token(ATOM, 'x')]),
            Tree(list, [Token(ATOM, 'if'),
                        Tree(list,
                             [Token(ATOM, '<'),
                              Token(ATOM, 'x'),
                              Token(INT, '0')]),
                        Tree(list,
                             [Token(ATOM, '-'),
                              Token(ATOM, 'x')]),
                        Token(ATOM, 'x')])])])

[('list', [('atom', 'define'),
           ('list', [('atom', 'abs'),
                     ('atom', 'x')]),
           ('list', [('atom', 'if'),
                     ('list', [('atom', '<'),
                               ('atom', 'x'),
                               ('int', 0)]),
                     ('list', [('atom', '-'),
                               ('atom', 'x')]),
                     ('atom', 'x')])])]

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))

scheme> (define a 3)
scheme>

    # 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")

Though I have already gone far past my goals for the project, there are a few directions which I could take this.

This was the biggest Python project I've done in five years, so it was interesting to check my experience of the language after some time away in Clojure-land. I was a big Python fan for many years but my enthusiasm for the language has definitely cooled. This is partly due to the performance comparison I just mentioned, but the two other things I really missed were REPL integration and structural editing.

In Lisps such as Clojure and Common Lisp I can send expressions to the REPL directly from Emacs and see the results instantly. It's difficult to describe how helpful this short feedback cycle is until you've experienced it. Writing the interpreter, I got sort of close by using conttest plus nosetests: my unit tests ran every time I saved a source file, and if I wanted to inspect some object I could add a print or two temporarily to the code I was working on. But this is definitely more clumsy than a Lisp REPL directly integrated with my editor.

Structural editing (via Paredit) is another thing that is hard to explain the utility of but which is hard to live without once you're used to it. The basic idea is that you are no longer editing strings of text, but the actual tree of nested lists comprising your code - killing, splitting, joining, absorbing ("slurping") into and expelling ("barfing") from those lists. Working with the code at the tree level is a powerful way to edit your code, and watching this video might help may give a hint of it. Once you're used to the affordances of Paredit or its cousins, it feels clunky and primitive to go back to editing plain old text.

Other value propositions of Clojure, such as macros, immutable data structures and concurrency, weren't really an issue for this project, though I would certainly miss them for bigger projects.

Implementing your own Lisp is surprisingly do-able (and fun!). Python is certainly a fine tool for the job (though if you want to skip straight to programming in a modern Lisp for your day job, please contact me).

While digging through my digital and mental archives for Lisp things I remembered something I hadn't seen in a long time: the use of closing square brackets to terminate a deeply-nested collection of s-expressions (i.e. ] instead of )))))))). Did I imagine it? While not necessarily a good idea, it's an interesting one. Then, while reading through Gabriel and Steele's Evolution of Lisp this morning, I came across the following snippet:

"One of the minor, but interesting, syntactic extensions that Interlisp made was the introduction of the superparenthesis, or superbracket. If a right square bracket ] is encountered during a read operation, it balances all outstanding open left parentheses, or back to the last outstanding left square bracket [."

DEFINEQ((FACTORIAL
  (LAMBDA (N)
   (COND [(ZEROP N) 1]
         (T (TIMES N (FACTORIAL (SUB1 N]

Bingo! I wasn't imagining it. This suggests those workstations in the basement of MACC at UW-Madison were probably running Interlisp.