A Python implementation of tree combinators described in "Building Program Optimizers with Rewriting Strategies" (1998, Visser, Benaissa, Tolmach)

strategy.py

# 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"]]