Jason’s musings

We recently covered the paper “The Generation of Optimal Code for Arithmetic Expressions” in compiler design class, so I thought I’d implement the first two algorithms described in it in Python.

The one and two functions are the names that he calls his procedures.

#!/usr/bin/env python
# encoding: utf-8
"""
optimal_code_for_arithmetic_expressions.py

Created by Jason McCandless on 2006-11-27.
Copyright (c) 2006 Jason McCandless All rights reserved.

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.
"""

class Node:
    def __init__(self,label,left = None,right = None):
        if left and right: #not a leaf
            self.op = label
            self.label = left.label + label + right.label
        else:
            self.label = label
        self.left = left
        self.right = right

    def print_labels(self):
        for node in self.postorder():
            print node.label, node.L

    def postorder(self):
        if self.left:
            for x in self.left.postorder():
                yield x
        if self.right:
            for x in self.right.postorder():
                yield x
        yield (self)

def postorder(t):
    if t:
        for x in postorder(t.left):
            yield x
        for x in postorder(t.right):
            yield x
        yield (t)

def label(node,leftLeaf=False):
    if node.left:
        l = label(node.left,True)
    if node.right:
        r = label(node.right,False)
    if not (node.left or node.right): #leaf
        if leftLeaf:
            node.L = 1
        else:
            node.L = 0
    else:
        if l != r:
            node.L = max(l,r)
        else:
            node.L = l + 1

        if node.L > 1:
            if (not (node.left.left or node.left.right)) and (node.op == "+" or node.op == "*"): #left descentent is a leaf, commutative
                node.left,node.right = node.right,node.left
                node.right.L = 0
                node.L = r

    return node.L

memory = 0
def getMemory():
    global memory
    memory = memory + 1
    return "m" + str(memory)

def one(root,n):
    two(root,n,1)

def two(node,n,m):
    if node.L == 1:
        if not (node.left or node.right): #leaf
            print "r" + str(m) + " := " + node.label
        else:
            two(node.left,n,m)
            print "r" + str(m) + " := " + "r" + str(m) + node.op + node.right.label
    else: #node.L > 1
        if node.left.L >= n and node.right.L >= n:
            two(node.right,n,m)
            mem = getMemory()
            print mem + " := " + "r" + str(m)
            two(node.left,n,m)
            print "r" + str(m) + " := " + "r" + str(m) + node.op + mem
            memory = memory -1
        else:
            if node.left.L >= node.right.L:
                higher, lower = node.left, node.right
            else:
                higher, lower = node.right , node.left
            two(higher,n,m)
            if (lower.L) > 0:
                two(lower,n,m+1)
                print "r" + str(m) + " := " + "r" + str(m) + node.op + "r" + str(m+1)
            else:
                print "r" + str(m) + " := " + "r" + str(m) + node.op + node.right.label

def main():
    root = Node("-",Node("/",Node("a"),Node("+",Node("b"),Node("c"))),Node("*",Node("d"),Node("+",Node("e"),Node("f"))))
    label(root)
    root.print_labels(); print
    one(root,2);

if __name__ == '__main__':
    main()