misc_python

Sean's miscellaneous Python code that's not big enough for its own repo.
Log | Files | Refs | README | LICENSE

commit 30fdb929977161075c7314f0523ffa0f6ec7e50f
parent caa729e372bc6e14d8e486a84d28aad4de3c5a14
Author: Sean Lynch <seanl@literati.org>
Date:   Tue, 28 Dec 2010 21:01:54 -0800

Implementation of Lambda Calculus

Diffstat:
Alam.py | 259+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 259 insertions(+), 0 deletions(-)

diff --git a/lam.py b/lam.py @@ -0,0 +1,259 @@ +#!/usr/bin/env python + + +class Expression(object): + def __call__(self, applicand): + return Application(self, applicand) + + def __eq__(self, other): + return self is other + + def __hash__(self): + return hash(id(self)) + + def __repr__(self): + return "<{0}{1!r} at {2:x}>".format(self.__class__.__name__, + self.__dict__, + id(self)) + + @staticmethod + def wrap(expression): + if isinstance(expression, Expression): + return expression + elif isinstance(expression, tuple) or isinstance(expression, list): + return reduce(Application, expression) + else: + return FreeVariable(expression) + + def beta_reduce(self): + return False + + def bind(self, name, variable): + return self + + def substitute(self, variable, value, cache=None): + return self + + +class FreeVariable(Expression): + """A free variable""" + def __init__(self, name): + self.name = name + + def bind(self, name, variable): + if name == self.name: + return variable + else: + return self + + def de_brujin(self, variables=None): + return self.name + + +class Variable(Expression): + """A variable in a lambda expression""" + next_index = 0 + def __init__(self): + self.index = self.next_index + self.__class__.next_index += 1 + + def __eq__(self, other): + return self is other or self.__class__ is other.__class__ and \ + self.index == other.index + + def __hash__(self): + return hash((self.__class__, self.index)) + + def contains(self, variable): + return variable == self + + def de_brujin(self, variables=None, **kwargs): + if variables is None: + variables = [] + + try: + return str(len(variables) - variables.index(self) - 1) + except: + print variables + print self + raise + + def substitute(self, variable, value, cache=None): + assert isinstance(variable, Variable) + if self == variable: + return value + else: + return self + + +class Application(Expression): + """An application""" + def __init__(self, left, right): + self.left = self.wrap(left) + self.right = self.wrap(right) + + def __eq__(self, other): + return self is other or self.__class__ is other.__class__ and \ + self.left == other.left and self.right == other.right + + def __hash__(self): + return hash((self.__class__, self.left, self.right)) + + def beta_reduce(self): + if isinstance(self.left, Lambda): + result = self.left.apply(self.right) + if self == result: + return False + else: + self.__class__ = result.__class__ + self.__dict__ = result.__dict__ + return True + else: + return self.left.beta_reduce() or self.right.beta_reduce() + + def bind(self, name, variable): + self.left = self.left.bind(name, variable) + self.right = self.right.bind(name, variable) + return self + + def contains(self, variable): + return self.left.contains(variable) or self.right.contains(variable) + + def de_brujin(self, variables=None, omit_parens=False): + if variables is None: + variables = [] + + left = self.left.de_brujin(variables, omit_parens=True) + right = self.right.de_brujin(variables) + fmt = "{0} {1}" if omit_parens else "({0} {1})" + return fmt.format(left, right) + + def substitute(self, variable, value, cache=None): + if cache is None: + cache = {} + + result = cache.get(self) + if result is not None: + print "apply substitute hit" + return result + + new_left = self.left.substitute(variable, value, cache) + new_right = self.right.substitute(variable, value, cache) + if new_left is self.left and new_right is self.right: + result = cache[self] = self + else: + result = cache[self] = self.__class__(new_left, new_right) + + return result + + +class Lambda(Expression): + """A lambda expression""" + def __init__(self, variable, body): + body = self.wrap(body) + if isinstance(variable, Variable): + self.variable = variable + else: + var = self.variable = Variable() + body = body.bind(variable, var) + + self.body = body + + def apply(self, argument): + """Perform beta reduction on self""" + return self.body.substitute(self.variable, argument) + + def beta_reduce(self): + return self.body.beta_reduce() + + def bind(self, name, variable): + self.body = self.body.bind(name, variable) + return self + + def de_brujin(self, variables=None, **kwargs): + if variables is None: + variables = [] + + variables.append(self.variable) + result = "[{0}]".format(self.body.de_brujin(variables, + omit_parens=True)) + variables.pop() + return result + + def substitute(self, variable, value, cache=None): + if self.variable == variable: + print "lambda variable renaming" + return self + + if cache is None: + cache = {} + result = cache.get(self) + if result is not None: + print "lambda substitute hit" + return result + + new_body = self.body.substitute(variable, value, cache) + if new_body is self.body: + result = cache[self] = self + else: + result = cache[self] = self.__class__(self.variable, new_body) + + return result + + +def print_reductions(name, expression): + print name + reduced = True + while reduced: +# print expression + print expression.de_brujin(omit_parens=True) + reduced = expression.beta_reduce() + + print + + +def main(): + I = Lambda('x', 'x') + K = T = Lambda('x', Lambda('y', 'x')) + F = Lambda('x', I) + S = Lambda('x', Lambda('y', Lambda('z', Application('x', 'z')(Application('y', 'z'))))) + W = Lambda('x', Application('x', 'x')) + O = W(W) + print_reductions("I", I) + print_reductions("K", K) + print_reductions("F", F) + print_reductions("S", S) + print_reductions("SKK", S(K)(K)) + print_reductions("W", W) + print_reductions("O", O) + zero = F + one = Lambda("s", Lambda("z", ("s", "z"))) + succ = Lambda("x", Lambda("s", Lambda("z", ("s", ("x", "s", "z"))))) + print_reductions("zero", zero) + print_reductions("succ", succ) + print_reductions("one", one) + print_reductions("succ(zero)", succ(zero)) + plus = Lambda("x", ("x", succ)) + print_reductions("plus", plus) + print_reductions("1+1", plus(one)(one)) + print_reductions("succ(one)", succ(one)) + two = succ(one) + three = succ(two) + pred = Lambda("n", Lambda("f", Lambda("x", ("n", Lambda("g", Lambda("h", ("h", ("g", "f")))), Lambda("u", "x"), Lambda("u", "u"))))) + print_reductions("three", three) + print_reductions("pred(three)", pred(three)) + sub = Lambda("m", Lambda("n", ("n", pred, "m"))) + print_reductions("sub", sub) + Y = Lambda("g", (Lambda("x", ("g", ("x", "x"))), Lambda("x", ("g", ("x", "x"))))) + ifthenelse = Lambda("p", Lambda("a", Lambda("b", ("p", "a", "b")))) + iszero = Lambda("n", ("n", Lambda("x", F), T)) + times = Lambda("m", Lambda("n", ("m", plus("n"), zero))) + g = Lambda("r", Lambda("n", ifthenelse(iszero("n"))(one)(times("n")(("r", "r", sub("n")(one)))))) + print_reductions("g", g) + print_reductions("KIO", K(I)(O)) + print_reductions("bad", Lambda("y", Lambda("x", ("x", "x"))(Lambda("x", "x")("y")))) + print_reductions("g (Y g) three", g(Y(g))(three)) + + +if __name__ == "__main__": + main()