Python-flavored Lisp

I mentioned in lab this week that a sufficiently crazy person could write a programming language with Lisp semantics and Python syntax. I found this idea useful when I was learning, so I want to expand upon it here by making a rudimentary evaluator for such a language. But let’s first explore the premise.

The Reader

Every modern program written by humans is a merely an array of characters. It’s up to the parser interpret the document as a program in a given language. If the parser succeeds, it outputs a data structure representing that code, called the Abstract Syntax Tree (AST).

For every dialect of Lisp, this parser is called the Reader. Readers are much less complex than parsers for most languages like Java or Python because the syntax model is so much simpler: Every Lisp expression is either a symbol (e.g. cons), a literal (e.g. 5), or a nested list thereof (e.g. (+ 1 2)); whereas we write Python lists like [1,2,3] in Lisp they look like (1 2 3).¹ All we did was change square brackets into parentheses and commas into spaces.

So when the Reader sees

(+ 1 2 
   (* 3 4))

it interprets that expression the same way that the Python parser interprets

[add, 1, 2, 
      [multiply, 3, 4]]

where add and multiply are functions.

You’re probably wondering how Racket’s list syntax fits into this. Firstly, expressions like '(1 2 3) are automatically expanded into (quote (1 2 3)). Hence this

(cons 1 '(2 3))

will, in Python syntax, become this:

[cons, 1, [quote, [1, 2]]]

Now, quote has special semantics: it tells the evaluator to take the given expression literally instead of trying to evaluate it. So our Pythonic evaluator should do

[+, 1, [*, 2, 3]]  -->  
[+, 1, (2*3)] --> 
[+, 1, 6]  -->  
1+6  --> 
7

but:

[cons, 1, [quote, [2, 3]]] --> 
cons(1, [2, 3]) --> 
[1, 2, 3]

Notice how we didn’t try to evaluate the expression [1, 2] because it was quoted. This is, by the way, why

(let ([a 1]
      [b 2])
  '(a b))

evaluates to (a b) instead of (1 2).

The point I want to get across is that your Racket code is as much a data structure as a Python list or an HTML document.² Moreover, unlike Java, this data has the same structure as the code itself; this property is called homoiconicity, and makes Lisp code particularly amenable to manipulation via macros - more on that in a couple of weeks.

Pictured: Abstract Syntax Tree for a Java program. Try to guess what it does.

The Evaluator

It’s actually extremely easy to write an evaluator for Python-flavoured Lisp because Python is enlightened enough to support first-class functions.

So here’s the evaluator! The code is simple and well-commented, so I hope you don’t have any problems with it. In order to support quoting in an idiomatic way, I made a dummy function called quote - when the evaluator sees it, it simply doesn’t evaluate the arguments, just like you’d expect.

def quote(x):
    return x 

def eval(code):
    # Code is an S-expression to be evaluated, e.g. (+ 1 5)
    if type(code) is list:

        # The first thing in a list is a function, the rest are arguments
        fn = code[0]
        
        # Don't evaluate quoted expressions
        if fn is quote:
            return code[1]

        # Before we can call the function with arguments, we need to evaluate
        # those arguments.
        args = []
        for expr in code[1:]:
            args.append(eval(expr))

        # Now we need to pass all these arguments to the function.
        # A little detail: To apply the list of arguments to `fn', we use a
        # special python feature:
        #   f(*args) == f(arg[1], arg[2], ...)
        return fn(*args)

    # If it's not an expression, just return that thing.
    # For example, in Racket the literal 5 just evaluates to 5.
    else:
        return code

And here’s the evaluator in action. Unlike Racket, Python’s + isn’t a real function, so we need to make a function add that has the same behavior.

import copy

def add(a, b):
    return a + b

def times(a, b):
    return a * b

def cons(x, xs):
    # Python's `insert` mutates the list, but `cons` should not.
    ys = copy.deepcopy(xs)
    ys.insert(0,x)
    return ys

# This code has EXACTLY the same meaning as
#   (+ 1 (* 2 3))
# does in Racket.
arithmetic = [add, 1, [times, 2, 3]]

# i.e. (cons 1 '(2 3))
lists = [cons, 1, [quote, [2, 3]]]

print(eval(arithmetic)) # => 7
print(eval(lists))      # => [1,2,3]