Meta-circular interpreter for lambda calculus in Python 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 &amp; Wrong.
# Terms: Cons, Var, Lam, App &amp; 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({}))
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).