# Strategies Programming control flow

In my last post I showed how unification and rewrite rules allow us to express *what* we want without specifying *how* to compute it. As an example we were able to turn the mathematical identity `sin(x)**2 + cos(x)**2 -> 1`

into a function with relatively simple code

```
# Transformation : sin(x)**2 + cos(x)**2 -> 1
>>> sincos_to_one = rewriterule(sin(x)**2 + cos(x)**2, 1, wilds=[x])
>>> sincos_to_one(sin(a+b)**2 + cos(a+b)**2).next()
1
```

However we found that this function did not work deep within an expression tree

```
>>> list(sincos_to_one(2 + c**(sin(a+b)**2 + cos(a+b)**2))) # no matches
[]
```

`sincos_to_one`

does not know *how* to traverse a tree. It is pure logic and has no knowledge of control. We define traverals separately using strategies.

*Short version*: we give you a higher order function, `top_down`

which turns a
expression-wise function into a tree-wise function. We provide a set of similar functions which can be composed to various effects.

## A Toy Example

How do we express control programmatically?

Traditional control flow is represented with constructs like `if`

, `for`

, `while`

, `def`

, `return`

, `try`

, etc…. These terms direct the flow of what computation occurs when. Traditionally we mix control and logic. Consider the following toy problem that reduces a number until it reaches a multiple of ten

```
def reduce_to_ten(x):
""" Reduce a number to the next lowest multiple of ten
>>> reduce_ten(26)
20
"""
old = None
while(old != x):
if (x % 10 != 0):
x -= 1
return x
```

While the logic in this function is somewhat trivial

```
if (x % 10 != 0):
x -= 1
```

the control pattern is quite common in serious code

```
while(old != expr):
old = expr
expr = f(expr)
return expr
```

It is the “Exhaustively apply this function until there is no effect” control pattern. It occurs often in general programming and very often in the SymPy sourcecode. We separate this control pattern into a higher order function named `exhaust`

```
def exhaust(rule):
""" Apply a rule repeatedly until it has no effect """
def exhaustive_rl(expr):
old = None
while(expr != old):
expr, old = rule(expr), expr
return expr
return exhaustive_rl
```

We show how to use this function to achieve the previous result.

```
def dec_10(x): # Close to pure logic
if (x % 10 != 0): return x - 1
else: return x
reduce_to_ten = exhaust(dec_10)
```

By factoring out the control strategy we achieve several benefits

- Code reuse of the
`while(old != new)`

control pattern - Exposure of logic - we can use the
`dec_10`

function in other contexts more easily. This version is more extensible. - Programmability of control - the control pattern is now first class. We can manipulate and compose it as we would manipulate or compose a variable or function.

## Example - Debug

When debugging code we often want to see the before and after effects of running a function. We often do something like the following

```
new = f(old)
if new != old:
print "Before: ", old
print "After: ", new
```

This common structure is encapsulated in the debug strategy

```
def debug(rule):
""" Print out before and after expressions each time rule is used """
def debug_rl(expr):
result = rule(expr)
if result != expr:
print "Rule: ", rule.func_name
print "In: ", expr
print "Out: ", result
return result
return debug_rl
```

Because control is separated we can inject this easily into our function

```
>>> reduce_to_ten = exhaust(debug(dec_10))
>>> reduce_to_ten(23)
Rule: dec_10
In: 23
Out: 22
Rule: dec_10
In: 22
Out: 21
Rule: dec_10
In: 21
Out: 20
20
```

## Traversals

Finally we show off the use of a tree traversal strategy which applies a function at each node in an expression tree. Here we use the `Basic`

type to denote a tree of generic nodes.

```
def top_down(rule):
""" Apply a rule down a tree running it on the top nodes first """
def top_down_rl(expr):
newexpr = rule(expr)
if is_leaf(newexpr):
return newexpr
return new(type(newexpr), *map(top_down_rl, newexpr.args))
return top_down_rl
>>> reduce_to_ten_tree = top_down(exhaust(tryit(dec_10)))
>>> expr = Basic(23, 35, Basic(10, 13), Basic(Basic(5)))
>>> reduce_to_ten_tree(expr)
Basic(20, 30, Basic(10, 10), Basic(Basic(0)))
```

## Use in Practice

We have rewritten the canonicalization code in the Matrix Expression module to use these strategies. There are a number of small functions to represent atomic logical transformations of expressions. We call these rules. Rules are functions from expressions to expressions

```
rule :: expr -> expr
```

And there are a number of strategies like `exhaust`

and `top_down`

which transform rules and parameters into larger rules

```
strategy :: parameters, rule -> rule
```

For example there are general rules like `flatten`

that simplify nested expressions like

`Add(1, 2, Add(3, 4)) -> Add(1, 2, 3, 4)`

```
def flatten(expr):
""" Flatten T(a, b, T(c, d), T2(e)) to T(a, b, c, d, T2(e)) """
cls = expr.__class__
args = []
for arg in expr.args:
if arg.__class__ == cls:
args.extend(arg.args)
else:
args.append(arg)
return new(expr.__class__, *args)
```

We compose these general rules (e.g. ‘flatten’, ‘unpack’, ‘sort’, ‘glom’) with strategies to create large canonicalization functions

```
rules = (rm_identity(lambda x: x == 0 or isinstance(x, ZeroMatrix)),
unpack,
flatten,
glom(matrix_of, factor_of, combine),
sort(str))
canonicalize = exhaust(top_down(typed({MatAdd: do_one(*rules)})))
```

## Going Farther

We use strategies to build large rules out of small rules. Can we build large strategies out of small strategies? The `canonicalize`

function above follows a common pattern “Apply a set of rules down a tree, repeat until they have no effect.” This is built into the `canon`

strategy.

```
def canon(*rules):
""" Strategy for canonicalization """
return exhaust(top_down(do_one(*rules)))
```

## Previous Work

This implementation of strategies was inspired by the work in the language StrategoXT. Stratego is a language for control that takes these ideas much farther and implements them more cleanly. It is a language where control structure are the primitives that can be built up, composed, and compiled down. It is a language in which ideas like “breadth first search” and “dynamic programming” are natural expressions.

## References

- Ralf Lämmel , Eelco Visser , Joost Visser,
*The Essence of Strategic Programming*, 2002 - Eelco Visser,
*Program Transformation with Stratego/XT*

blog comments powered by Disqus