Last active
December 17, 2015 05:18
-
-
Save suranap/5556531 to your computer and use it in GitHub Desktop.
A Python implementation of tree combinators described in "Building Program Optimizers with Rewriting Strategies" (1998, Visser, Benaissa, Tolmach)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Tree transformation combinators | |
# portable strategies | |
def seqS(*strategies): | |
def seqaux(tree): | |
tmp = tree | |
for s in strategies: | |
tmp = s(tmp) | |
if tmp == False: | |
return False | |
return tmp | |
return seqaux | |
def choiceS(*strategies): | |
def choiceaux(tree): | |
for s in strategies: | |
tmp = s(tree) | |
if tmp: | |
return tmp | |
return False | |
return choiceaux | |
def fail(tree): | |
return False | |
def identity(tree): | |
return tree | |
def tryS(strategy): | |
return choiceS(strategy, identity) | |
def repeatS(strategy): | |
def recur(tree): | |
return tryS(seqS(strategy, recur))(tree) | |
return recur | |
def repeat1S(strategy): | |
def recur(tree): | |
return seqS(strategy, repeatS(strategy))(tree) | |
return recur | |
def bottomupS(strategy): | |
def recur(tree): | |
return seqS(allS(recur), strategy)(tree) | |
return recur | |
def topdownS(strategy): | |
def recur(tree): | |
return seqS(strategy, allS(recur))(tree) | |
return recur | |
def oncebuS(strategy): | |
def recur(tree): | |
return choiceS(oneS(recur), strategy)(tree) | |
return recur | |
def oncetdS(strategy): | |
def recur(tree): | |
return choiceS(strategy, oneS(recur))(tree) | |
return recur | |
def somebuS(strategy): | |
def recur(tree): | |
return choiceS(someS(recur), strategy)(tree) | |
return recur | |
def sometdS(strategy): | |
def recur(tree): | |
return choiceS(strategy, someS(recur))(tree) | |
return recur | |
def allbuS(strategy): | |
def recur(tree): | |
return seqS(allS(recur), tryS(strategy))(tree) | |
return recur | |
def alltdS(strategy): | |
def recur(tree): | |
return choiceS(strategy, allS(recur))(tree) | |
return recur | |
def manybuS(strategy): | |
def recur(tree): | |
return choiceS(seqS(someS(recur), tryS(strategy)), strategy)(tree) | |
return recur | |
def manytd(strategy): | |
def recur(tree): | |
return choiceS(seqS(strategy, allS(tryS(recur))), someS(recur))(tree) | |
return recur | |
def manydownupS(strategy): | |
def recur(tree): | |
return choiceS(seqS(strategy, allS(tryS(recur)), tryS(strategy)), | |
seqS(someS(recur), tryS(strategy)))(tree) | |
return recur | |
def outermostS(strategy): | |
def recur(tree): | |
return repeatS(oncetdS(strategy))(tree) | |
return recur | |
def innermost(strategy): | |
def recur(tree): | |
return repeatS(oncebuS(strategy))(tree) | |
return recur | |
def reduceS(strategy): | |
def recur(tree): | |
return repeatS(manybu(strategy))(tree) | |
# --------------------------------------- | |
# core strategies on boolean operations: and, or, not | |
def allS(strategy): | |
def allaux(tree): | |
if tree[0] == 'and' or tree[0] == 'or': | |
left = strategy(tree[1]) | |
if left: | |
right = strategy(tree[2]) | |
if right: | |
return [tree[0], left, right] | |
return False | |
elif tree[0] == 'not': | |
left = strategy(tree[1]) | |
if left: | |
return ['not', left] | |
else: | |
return False | |
else: | |
return tree | |
return allaux | |
def someS(strategy): | |
def someaux(tree): | |
if tree[0] == 'and' or tree[0] == 'or': | |
left = strategy(tree[1]) | |
right = strategy(tree[2]) | |
if left == False and right == False: | |
return False | |
else: | |
return [tree[0], left, right] | |
elif tree[0] == 'not': | |
left = strategy(tree[1]) | |
if left: | |
return ['not', left] | |
else: | |
return False | |
else: | |
return tree | |
return someaux | |
def oneS(strategy): | |
def oneaux(tree): | |
if tree[0] == 'and' or tree[0] == 'or': | |
left = strategy(tree[1]) | |
if left == False: | |
right = strategy(tree[2]) | |
if right == False: | |
return False | |
else: | |
return [tree[0], tree[1], right] | |
else: | |
return [tree[0], left, tree[2]] | |
elif tree[0] == 'not': | |
left = strategy(tree[1]) | |
if left: | |
return ['not', left] | |
else: | |
return False | |
else: | |
return tree | |
# ------------------------------------------- | |
# simplification rules | |
def doubleNeg(tree): | |
if tree[0] == 'not': | |
if tree[1][0] == 'not': | |
return tree[1][1] | |
return False | |
def demorgan1(tree): | |
if tree[0] == 'not': | |
if tree[1][0] == 'and': | |
return ['or', ['not', tree[1][1]], ['not', tree[1][2]]] | |
return False | |
def demorgan2(tree): | |
if tree[0] == 'not': | |
if tree[1][0] == 'or': | |
return ['and', ['not', tree[1][1]], ['not', tree[1][2]]] | |
return False | |
def distribute1(tree): | |
if tree[0] == 'or': | |
if tree[1][0] == 'and': | |
c = tree[2] | |
return ['and', ['or', tree[1][1], c], ['or', tree[1][2], c]] | |
elif tree[2][0] == 'and': | |
a = tree[1] | |
return ['and', ['or', a, tree[2][1]], ['or', a, tree[2][2]]] | |
return False | |
def printTerm(tree): | |
print tree | |
return tree | |
# Test cases | |
# ["not", ["not", "A"]] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment