A lisp interpreter

lisp_parser.py

"""
A Lisp parser and interpreter supporting the following operators:
    - (mutl a b), returns a * b
    - (add a b), returns a + b
    - (let a 1 b 2 a), assigns a = 1, b = 2, then returns a,
        this supports an arbitrary number of even params, the
        last param being the return value

Very similar to the parser David and I wrote years ago:
    https://github.com/keyan/schemeling/blob/master/parser.py

Written in the style of Peter Norvig:
    http://norvig.com/lispy.html
"""
import copy
import unittest
from typing import Any, List


def tokenize(s: str) -> [str]:
    """
    Convert the raw string into a list of each individual token.
    e.g. '(add 1 2)' -> ['(', 'add', '1', '2', ')']
    """
    return s.replace('(', ' ( ').replace(')', ' ) ').split()


def get_ast(expr) -> [Any]:
    """
    Convert the tokenized list into a nested list representing
    the abstract syntax tree for the whole expression.
    """
    # Remove the first token, assuming well formed input it should
    # always be (, a variable, or an int.
    token = expr.pop(0)
    if token == '(':
        # Create a new nested list, inside are the elements
        # we gather recursively.
        res = []
        # Each call to get_ast mutates the original expr list,
        # eventually we will reach a closing brace.
        while expr[0] != ')':
            res.append(get_ast(expr))
        # Pop off the closing brace.
        expr.pop(0)
        # If this is the outer list of the AST we will return
        # the whole AST, otherwise this is just returning a nested
        # AST to the recursive caller.
        return res
    else:
        # This is the standard path for most calls.
        try:
            token = int(token)
        except:
            pass
        return token


def eval(ast, scope) -> int:
    # We only support strings which are variables, int literals, or one
    # of the few operators.
    if isinstance(ast, str):
        return scope[ast]
    if isinstance(ast, int):
        return ast

    operation, *args = ast
    if operation == 'let':
        expr_idx = len(args) - 1
        i = 0
        # Copy the existing scope before the let function is going to
        # potentially overwrite variables locally in a deeper scope.
        # We need to ensure the top level scope is not mutated.
        new_scope = copy.deepcopy(scope)
        while i < expr_idx:
            new_scope[args[i]] = eval(args[i+1], copy.deepcopy(new_scope))
            i += 2
        # No need to copy the scope here because we aren't assigning variables.
        return eval(args[expr_idx], new_scope)
    elif operation == 'add':
        return eval(args[0], scope) + eval(args[1], scope)
    elif operation == 'mult':
        return eval(args[0], scope) * eval(args[1], scope)
    else:
        raise Exception(f'Received unknown operation: {operation}')


def parse(expression: str) -> int:
    """
    The entrypoint for evaulating strings, input goes through this
    pipeline, each step reads input and writes output, no mutation
    of shared state:
        expression -> tokens -> AST -> evaluation -> result
    """
    tokens = tokenize(expression)
    ast = get_ast(tokens)

    return eval(ast, {})


class TestParser(unittest.TestCase):
    def test_stuff(self):
        res = parse("(let x 2 (mult x (let x 3 y 4 (add x y))))")
        self.assertEqual(res, 14)

        res = parse("(let x 3 x 2 x)")
        self.assertEqual(res, 2)

        res = parse("(let x 1 y 2 x (add x y) (add x y))")
        self.assertEqual(res, 5)

        res = parse("(let x 2 (add (let x 3 (let x 4 x)) x))")
        self.assertEqual(res, 6)

        res = parse("(let a1 3 b2 (add a1 1) b2)")
        self.assertEqual(res, 4)


if __name__ == '__main__':
    unittest.main()