## 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) -- http://mail.python.org/mailman/listinfo/python-list