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({}))

scnerd · Accepted Answer · 2019-09-10 22:29:33Z

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

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
– YvesgereY, Commented Sep 12, 2019 at 11:04
That being said, I'am interested in your multi-args implementation! — YvesgereY
– YvesgereY, Commented Sep 12, 2019 at 11:06

Stack Exchange Network

Meta-circular interpreter for lambda calculus in Python

1 Answer 1

You must log in to answer this question.

Linked

Hot Network Questions

Meta-circular interpreter for lambda calculus in Python

1 Answer 1

You must log in to answer this question.

Linked

Related

Hot Network Questions