Turing Compliant?

[Stephan Houben]

David Oppenheimer <davidopp at megsinet.net> writes:

> 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

class ParseError(Exception):
    pass

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