Entry

Lambda calculus interpreter (was: Turing compliant?)

Jul 5th, 2000 10:01
Nathan Wallace, unknown unknown, Hans Nowak, Snippet 214, Stephan Houben

"""
Packages: maths;functional_programming
"""
"""
> What the heck does Turing Compliant mean?  I've heard discussion that
> Python is not Turing Compliant.  Is this true and why would this be an
> important consideration for someone who is programming in Python?
I'm sorry. I'm probably to blame for this.  Someone asked a question whether
Python was suited for his goals, without ever mentioning what his goals
where. So I asked him what his goals where, and -as a joke- if Turing
Completeness was perhaps required. 
Every programming language is Turing Complete. This is a bit like when
somebody asks which car he should buy, and I ask him if it is supposed to be
able to drive. So it was a lame joke, and it confused people.
So to make mends for all this, I will now give a constructive proof that
Python is, indeed, Turing Complete. I will do this by including the
following Python program, which is an evaluator for the Lambda calculus.
(The Lambda calculus is Turing complete, almost by definition.) 
Note the syntax: angles are required around applications, like in
(f g), but forbidden diectly around lambda abstractions.
Lambda abstractions are written as:
 \x.expr
The interpreter reads one line at a time. An empty line exits the
interpreter.
I actually tried to do some sane error recovery.
However, the implementation is NOT efficient.
But who cares. It terminates.
Greetings,
Stephan
"""
# Lambda calculus interpreter in Python.
# This is a constructive proof that Python is Turing-complete.
# Written by Stephan Houben
import string
import types
try:
    import exceptions
    class ParseError(Exception):
        pass
except:
    ParseError = "ParseError"
def parse(str):
    # crude hack to have "(", ")", "." and "\\" always stand out 
    str = string.replace(str, "(", " ( ")
    str = string.replace(str, ")", " ) ")
    str = string.replace(str, ".", " . ")
    str = string.replace(str, "\\", " \\ ")
    # split in tokens
    tokens = string.split(str)
    expr, i = parse_expr(tokens, 0)
    if i < len(tokens):
	raise ParseError, "Superfluous input found" 
    else:
	return expr
def get_token(tokens, i):
    if i >= len(tokens):
	raise ParseError, "More input expected"
    else:
	return tokens[i], i+1
def check_token(tokens, i, token):
    token2, i = get_token(tokens, i)
    if token != token2:
	raise ParseError, "Token %s expected instead of %s" % (token, token2)
    else:
	return i
def parse_expr(tokens, i):
    token, i = get_token(tokens, i)
    if token == "(":
	expr1, i = parse_expr(tokens, i)
	expr2, i = parse_expr(tokens, i)
	i = check_token(tokens, i, ")")
	return (expr1, expr2), i
    elif token == "\\":
	var, i = get_token(tokens, i)
	check_var(var)
	i = check_token(tokens, i, ".")
	expr, i = parse_expr(tokens, i)
	return ("\\", var, expr), i
    else:
	check_var(token)
	return token, i
def check_var(token):
    if token in ("//", "(", ")", "."):
	raise ParseError, "Variable expected instead of %s" % token
def is_var(expr):
    return type(expr) == types.StringType
def is_application(expr):
    return type(expr) == types.TupleType and len(expr) == 2 
def is_lambda(expr):
    return type(expr) == types.TupleType and len(expr) == 3 
def substitute(expr, var, subst):
    if is_var(expr):
	if expr == var:
	    return subst
	else:
	    return expr
    elif is_application(expr):
	return (substitute(expr[0], var, subst),
		substitute(expr[1], var, subst))
    else:
	lambda_var = expr[1]
	if lambda_var == var:
	    return expr
	else:
	    return ("\\", lambda_var, substitute(expr[2], var, subst))
def evaluate(expr):
    while is_application(expr):
	f, g = expr
	f = evaluate(f)
	if is_lambda(f):
	    lambda_var = f[1]
	    lambda_body = f[2]
	    expr = substitute(lambda_body, lambda_var, g)
	else:
	    break
    return expr    
def prettyprint(expr):
    if is_var(expr):
	print expr,
    elif is_application(expr):
	print "(",
	prettyprint(expr[0])
	prettyprint(expr[1])
	print ")",
    else:
	print "\\",
	prettyprint(expr[1])
	print ".",
	prettyprint(expr[2])
def main():
    while 1:
	line = raw_input("> ")
	if line:
	    try:
		prettyprint(evaluate(parse(line)))
		print
	    except ParseError, msg:
		print "Error: %s\n" % msg
	else:
	    break
main()