Meta-circular interpreter for lambda calculus in Python

Question

For learning purpose, I've written a simple lambda calculus interpreter (plus 'Add'). I would like it to be the cleanest and most idiomatic possible.

Can we make it as neat as the Haskell version?

# lambda interpreter example. # Values: Num, Fun & Wrong. # Terms: Cons, Var, Lam, App & Add. class Num: def __init__(self, v): self.v = v def __str__(self): return str(self.v) class Fun: def __init__(self, f): self.f = f def __call__(self, *args, **kargs): return self.f(*args, **kargs) def __str__(self): return 'function' class Wrong: def __str__(self): return 'Wrong' def add(v1, v2): return Num(v1.v + v2.v) def apply(v1, v2): return v1(v2) class Cons: def __init__(self, v): self.v = int(v) def interp(self, env): return Num(self.v) class Var: def __init__(self, x): self.x = x def interp(self, env): return env[self.x] class Lam: def __init__(self, arg, body): self.arg = arg self.body = body def interp(self, env): def f(v): env2 = env.copy() env2[self.arg] = v return self.body.interp(env2) return Fun(f) class App: def __init__(self, fun, param): self.fun = fun self.param = param def interp(self, env): return apply(self.fun.interp(env), self.param.interp(env)) class Add: def __init__(self, a, b): self.a = a self.b = b def interp(self, env): return add(self.a.interp(env), self.b.interp(env)) expr = App( Lam('x', Add(Var('x'), Var('x'))), Add(Cons(10), Cons(11)) ) print(expr.interp({})) 

Answer 1

I don't quite know what lambda calculus is (I'm assuming it's a mathematical annotation for what we might call "purely functional programming"?), but I'll give this a quick shot.

First, I'd love to have env populate itself if not provided. You really shouldn't have mutable default values for functions, though; the typical practice is to define:

interp(self, env=None): env = env or {} # ... 

but that's really bloat'y in this case, so let's use a little inheritance:

class Op: def interp(self, env=None): return self._interp(env if env is not None else {}) def _interp(self, env): raise NotImplementedError() class Cons(Op): def __init__(self, v): self.v = int(v) def _interp(self, env): # update name to "_interp" return Num(self.v) # ... print(expr.interp()) # Yay for no boilerplate arguments! 

Now we can just call interp() and the rest handles itself.

The next thing I'd do to make things a bit more concise is to leverage Python 3.7's new dataclass feature; while this doesn't seem to remove any lines of code, it's certainly more concise and descriptive, and adds some useful meta-features like allowing our AST objects to be intelligently compared and printed:

from dataclasses import dataclass # ... @dataclass class App(Op): fun: Lam param: Op def _interp(self, env): return self.fun.interp(env)(self.param.interp(env)) @dataclass class Add(Op): a: Op b: Op def _interp(self, env): return add(self.a.interp(env), self.b.interp(env)) # ... print(expr) # App(fun=Lam(arg='x', body=Add(a=Var(x='x'), b=Var(x='x'))), param=Add(a=Cons(v=10), b=Cons(v=11))) 

Moving beyond Add, we can start using inheritance to make things clearer and more concise:

@dataclass class BinOp(Op): a: Op b: Op @staticmethod def _func(v1, v2): raise NotImplementedError() def _interp(self, env): return self._func(self.a.interp(env), self.b.interp(env)) class Add(BinOp): @staticmethod def _func(v1, v2): return Num(v1.v + v2.v) class Sub(BinOp): @staticmethod def _func(v1, v2): return Num(v1.v - v2.v) 

Some minor nit-pick details to finish off:

• 4-space indentation is more common than 2-space, which can look a bit cramped.

• I'm not sure if it's typically allowed in lambda calculus, but I'd like to see Lam/functions that can take any number of arguments (I have a working implementation that's pretty clean that I'd be happy to share if you're interested).