useless python - term rewriter

[Sean McIlroy]

## term rewriter (python 3.1.1)

def gettokens(string):
spaced = string.replace('(',' ( ').replace(')',' ) ')
return spaced.split()

def getterm(tokens):
if tokens[0] in '()':
term = []
assert tokens[0] == '('
tokens.pop(0)
while not tokens[0] == ')': term.append(getterm(tokens))
tokens.pop(0)
return term
return tokens.pop(0)

def parse(strg):
tokens = gettokens(strg)
term = getterm(tokens)
assert not tokens
return term

def unparse(term):
if type(term) == str: return term
subterms = [unparse(subterm) for subterm in term]
return '({})'.format(' '.join(subterms))

def atom(term):
return type(term) == str

def compound(term):
return type(term) == list

def variable(term):
return atom(term) and term[0].isupper()

def constant(term):
return atom(term) and not term[0].isupper()

def conformable(term1,term2):
return compound(term1) and compound(term2) and len(term1) ==
len(term2)

def getrule(string):
left, right = string.split('=')
return [parse(left), parse(right)]

def getrules(string):
nonblank = lambda substring: substring and not substring.isspace()
return [getrule(substring) for substring in string.splitlines() if
nonblank(substring)]

def substitute(bindings,term):
if constant(term): return term
if variable(term): return bindings.get(term,term)
return [substitute(bindings,subterm) for subterm in term]

def match(term,pattern):
from operator import concat
from functools import reduce
if variable(pattern): return [[pattern, term]]
if constant(pattern) and pattern == term: return []
if conformable(pattern,term):
matches = [match(subterm,subpattern) for subterm, subpattern
in zip(term,pattern)]
return reduce(concat,matches)
raise Exception

def rewrite(term,rule):
if type(rule) == dict:
function = rule[term[0]]
arguments = [int(subterm) for subterm in term[1:]]
return str(function(*arguments))
left, right = rule
bindings = dict(match(term,left))
return substitute(bindings,right)

def apply(rule,term):
try: return [rewrite(term,rule), True]
except:
if atom(term): return [term, False]
applications = [apply(rule,subterm) for subterm in term]
subterms = [subterm for subterm, change in applications]
changes = [change for subterm, change in applications]
return [subterms, any(changes)]

def normalize(term,rules):
while True:
changes = []
for rule in rules:
term, change = apply(rule,term)
changes.append(change)
if not any(changes): break
return term

def translate(rules):
string = input('>>> ')
if string and not string.isspace():
try:
term = parse(string)
normal = normalize(term,rules)
string = unparse(normal)
print(string)
except: print('parse error')

def interpret(equations):
import operator
rules = [vars(operator)] + getrules(equations)
while True:
try: translate(rules)
except KeyboardInterrupt:
print('end session')
break

example = """

(factorial 0) = 1
(factorial N) = (mul N (factorial (sub N 1)))

(fibonacci 0) = 0
(fibonacci 1) = 1
(fibonacci N) = (add (fibonacci (sub N 1)) (fibonacci (sub N 2)))

"""

interpret(example)