CEK abstract machine

cek.py

class Var(object):
    def __init__(self, name):
        self.name = name

    def __repr__(self):
        return self.name

class Lam(object):
    def __init__(self, bind, expr):
        self.bind = bind
        self.expr = expr

    def __repr__(self):
        return "(.: {} . {})".format(self.bind, self.expr)

class Call(object):
    def __init__(self, lhs, rhs):
        self.lhs = lhs
        self.rhs = rhs

    def __repr__(self):
        return "({} {})".format(self.lhs, self.rhs)

class Env(object):
    def __init__(self, parent, bind, expr):
        self.parent = parent
        self.bind = bind
        self.expr = expr

    def __call__(self, var):
        if self.bind is var:
            return self.expr
        return self.parent(var)

    def __repr__(self):
        return "{}.[{}: {}]".format(self.parent, self.bind, self.expr)

class Arg(object):
    def __init__(self, expr, env, cont):
        self.expr = expr
        self.env = env
        self.cont = cont

    def __repr__(self):
        return "Arg({}, {})::{}".format(self.expr, self.env, self.cont)

class Fun(object):
    def __init__(self, expr, env, cont):
        self.expr = expr
        self.env = env
        self.cont = cont

    def __repr__(self):
        return "Fun({}, {})::{}".format(self.expr, self.env, self.cont)

class Add(object):
    def __init__(self, var1, var2):
        self.var1 = var1
        self.var2 = var2

    def __repr__(self):
        return "(+ {} {})".format(self.var1, self.var2)

Return = '__CEK_Return__'

def step(expr, env, cont):
    if isinstance(expr, Var):
        return env(expr), env, cont
    if isinstance(expr, Call):
        return expr.lhs, env, Arg(expr.rhs, env, cont)
    if isinstance(expr, Add):
        v1 = env(expr.var1)
        v2 = env(expr.var2)
        return v1 + v2, env, cont
    if isinstance(expr, Lam) and isinstance(cont, Arg):
        return cont.expr, cont.env, Fun(expr, env, cont.cont)
    if isinstance(cont, Fun):
        return cont.expr.expr, Env(cont.env, cont.expr.bind, expr), cont.cont
    return expr, env, Return

def CEK_eval(_expr, _env=None):
    env = _env
    expr = _expr
    cont = None

    while True:
        if cont == Return:
            break

        expr, env, cont = step(expr, env, cont)

        print 'expr:', expr
        print ' env:', env
        print 'cont:', cont, '\n'

    return expr

if __name__ == '__main__':
    x = Var('x')
    y = Var('y')
    add = Lam(x, Lam(y, Add(x, y)))
    call_add = lambda x, y: Call(Call(add, x), y)
    program = call_add(2, call_add(3, 4))
    CEK_eval(program)

Output

expr: ((.: x . (.: y . (+ x y))) 2)
 env: None
cont: Arg((((.: x . (.: y . (+ x y))) 3) 4), None)::None 

expr: (.: x . (.: y . (+ x y)))
 env: None
cont: Arg(2, None)::Arg((((.: x . (.: y . (+ x y))) 3) 4), None)::None 

expr: 2
 env: None
cont: Fun((.: x . (.: y . (+ x y))), None)::Arg((((.: x . (.: y . (+ x y))) 3) 4), None)::None 

expr: (.: y . (+ x y))
 env: None.[x: 2]
cont: Arg((((.: x . (.: y . (+ x y))) 3) 4), None)::None 

expr: (((.: x . (.: y . (+ x y))) 3) 4)
 env: None
cont: Fun((.: y . (+ x y)), None.[x: 2])::None 

expr: ((.: x . (.: y . (+ x y))) 3)
 env: None
cont: Arg(4, None)::Fun((.: y . (+ x y)), None.[x: 2])::None 

expr: (.: x . (.: y . (+ x y)))
 env: None
cont: Arg(3, None)::Arg(4, None)::Fun((.: y . (+ x y)), None.[x: 2])::None 

expr: 3
 env: None
cont: Fun((.: x . (.: y . (+ x y))), None)::Arg(4, None)::Fun((.: y . (+ x y)), None.[x: 2])::None 

expr: (.: y . (+ x y))
 env: None.[x: 3]
cont: Arg(4, None)::Fun((.: y . (+ x y)), None.[x: 2])::None 

expr: 4
 env: None
cont: Fun((.: y . (+ x y)), None.[x: 3])::Fun((.: y . (+ x y)), None.[x: 2])::None 

expr: (+ x y)
 env: None.[x: 3].[y: 4]
cont: Fun((.: y . (+ x y)), None.[x: 2])::None 

expr: 7
 env: None.[x: 3].[y: 4]
cont: Fun((.: y . (+ x y)), None.[x: 2])::None 

expr: (+ x y)
 env: None.[x: 2].[y: 7]
cont: None 

expr: 9
 env: None.[x: 2].[y: 7]
cont: None 

expr: 9
 env: None.[x: 2].[y: 7]
cont: __CEK_Return__