Lambda calculus parser

parser.py

class Lambda(object):
    pass

class Var(Lambda):
    def __init__(self, var):
        self.var = var
    def __repr__(self):
        return "Var(%r)" % self.var

class Abs(Lambda):
    def __init__(self, var, body):
        self.var = var
        self.body = body
    def __repr__(self):
        return "Abs(%r, %r)" % (self.var, self.body)

class App(Lambda):
    def __init__(self, func, arg):
        self.func = func
        self.arg = arg
    def __repr__(self):
        return "App(%r, %r)" % (self.func, self.arg)

def to_list(l):
    result = None
    for e in reversed(l):
        result = e, result
    return result

def lex(s):
    import re
    pattern = re.compile(r'\w+|[()^.]')
    return to_list(pattern.findall(s))

def parse_lambda(l):
    h, _ = l
    if h.isalpha(): return parse_var(l)
    if h == '^': return parse_abs(l)
    if h == '(': return parse_app(l)

def parse_var(l):
    var, l = l
    return Var(var), l

def parse_abs(l):
    h, l = l # ^
    var, l = parse_var(l)
    h, l = l # .
    body, l = parse_lambda(l)
    return Abs(var, body), l

def parse_app(l):
    h, l = l # (
    func, l = parse_lambda(l)
    arg, l = parse_lambda(l)
    h, l = l # )
    return App(func, arg), l

def parse(s):
    l = lex(s)
    result, l = parse_lambda(l)
    assert not l
    return result