Implementing Scheme in Python

code python lisp .....

Later: A Daily Journal in Org Mode
Earlier: Show at NUPOC

Background

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 me1 and why I've returned to it over and over throughout my career. In the mean timeā€¦.

Scheming in Python

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.

Prior Art

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

The Stages

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.

Parsing

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.

Data Model

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:

Data Type Example
Atom ('atom', 'foo')
Boolean ('bool', True)
Int ('int', 123)
Float ('float', 3.14)
List ('list', [('atom', 'define'), ('atom', 'x'), ('int', 3)])

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:

Scheme raw source

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

Lark output

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

Internal representation used in the interpreter

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

Evaluation

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.

Printing

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>

Testing Approach

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.

The Code Comes To Life

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.

Next Steps

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

Implement more of Scheme

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

Extend it Further

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.

Go Low Level

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.

Thoughts Upon Revisiting Python

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.

Conclusion

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

Postscript

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.


1

So compelling that I left an exciting science project partly in order to do Lisp (Clojure) programming full time.

Later: A Daily Journal in Org Mode
Earlier: Show at NUPOC