Green Red Strategy

Introduction

The basic principle of Casio is deriving a floating point program with less error from a starting program through a series of incremental changes. While at any given time there are several different possible paths being explored, from any given node in exploration one can trace a path backwards of incremental changes that led from the starting node to this node. Since the goal is to reduce error, these changes can be separated into three categories: changes which immediately reduce error in the program overall (ones which the program after the change is evaluated to have less error than the program before the change) [Green], changes which do not immediately reduce error, but are essential in enabling green changes [Orange], and changes which do not lead to an increase in error [Red]. While all three type of changes can be part of a path to the optimal program, the most promising leads and thus the ones that Casio should pursue with the highest priority are the first and second categories of changes (green and orange changes).

Ultimately, the goal will be to be able to eliminate red changes, and to use orange changes to both set up more green changes and simplify the final program. To do this we first want to, for each node in the search, record a history of all of the changes that the node went through from the starting node. These changes should be categorized into the aforementioned categories. Next, we want to, after every green change, go back and try to “undo” all of the red changes that were part of the path to arrive at the current node but did not contribute to the green change. Finally, we want to after every green change use a series of educated guesses to try to simplify the current program using orange changes.

Identifying Changes

Identifying green changes is simple: when the error of a program is significantly less after a change is made than before the change is made, a green change has occurred. Deciding at what threshold a change in error becomes “significant” is something that for now will be found through trial and error. Identifying the red and orange changes is more tricky, since at the time the change is made, any non-green change is a potential red or orange change. To identify which one a change is, we need to develop the concept of “direct dependency” between two changes. A change can directly depend on one or more other changes. Thus, an orange change can be recursively defined as a change that is directly depended on either by a green change or a confirmed orange change.

Direct dependency, it appears, is actually fairly straightforward to determine. Casio makes changes by matching patterns on sub-expressions of the current program, and then using the rules to transform the expression which matches that pattern to another equivalent expression. Thus, the only thing that any given change directly depends on is that the relevant sub-expression be matched. We can define direct dependencies as those changes which cause the pattern to be matched.

Past this, though, it gets tricky. Obviously the last change which causes the pattern to immediately be matched is a dependency of the pattern matching change, but what of other, earlier changes which operate on other parts of the pattern? For example, suppose we have the rules:

1. (- (+ a b) (- a b)) => (* 2 b)
2. (+ a (- b)) => (- a b)
3. (+ a b) => (+ b a)

And we start with the expression (- (+ y x) (+ x (-y))). It becomes

• (- (+ x y) (+ x (-y))) by rule #3,
• (- (+ x y) (- x y)) by rule #2, and finally
• (* 2 y) by rule #1.

Let's suppose that by eliminating a variable, the last change significantly reduced error, making it a green change. We know that the second change is a direct dependency of our new green change since before the second change, the expression was (- (+ x y) (+ x (-y))), which did not match the pattern (- (+ a b) (- a b)), but after the change the expression was (- (+ x y) (- x y)), which did match the pattern. Therefore, the second change is an orange change. Consider, also, that we can tell intuitively that the first change is also a direct dependency of the green change, making it an orange change, since without that change the expression would have been (- (+ y x) (- x y)), which does not match the pattern. However, if we are only going off the rule that a direct dependency is a change that, before the change the pattern was not matched for the dependent change, but afterwards it was, this first change will not be considered a direct dependency of the green change. The second change, a confirmed orange change, also does not depend on the first change, since they operate on different parts of the expression. Therefore, this method is not sufficient to identify the first change as orange, and is therefore not sufficient for out purposes.