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)