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).

• YvesgereY: Thanks for the tips! I'm not convinced by the env handling, tough. Too much indirections. Isn't "Explicit better than implicit"? :) Here, we really want to say the interpreter needs an environnement, and that this environnement is empty at the beginning. I'll definitively look at dataclass@. Con: even more "magic". Pro: if it becomes idiomatic, it sure can make things clearer. In lambda calculus, you handle several arguments by currying. In python: >>> m = lambda x: lambda y: x*y >>> m(6)(7) 42
• YvesgereY: That being said, I'am interested in your multi-args implementation!