ACE revisited

Quite a few years ago I built a system called ACE - the Algorithm Composition Engine. It was both a success and a failure that contains a pile of ideas that have nagged me ever since. It was roughly a macro preprocessor like CPP, except that it delt in parse trees instead of characters.

Ace's equivalent of a macro was based on a pattern match in a parse tree rather than a token match in a characters stream. So one could write:

$replace $0*2; $with $0<<1;

The most powerful function in ACE was $tradeoff(a,b) which took as parameters two code fragments that were assumed to perform the same computation. Tradeoff would compute time and space estimates for each code fragment, then choose one or the other based on the probability of reaching that point. ACE was fed branch probabilities and loop lap-counts to compute an expected execution count for each point in the program. For tradeoff, if one code fragment was large and slow, and the other was small and fast, the choice is clear. More commonly one is large and fast, the other is small and slow. If the expected execution count was low, the small and slow version would be picked, otherwise the large and fast version would be picked. ACE essentially had a dial that let the developer say "give me the fastest version of this function that fit in N bytes".

The parameters to tradeoff were usually based on different performance motivated refactorings. These could usually be done cleanly using ACE, as described in the paper.

ACE was very successful in that it made it possible for us to write simple clean code for high performance algorithms that was robust and flexible. The downside was that very few developers could figure out how to use it. It was a very different way to think about coding. I came to think of ACE as a complete failure when I visited the group again to answer some questions about old pieces of code and I discovered that instead of fixing problems in the input to ACE, they had taken the output from ACE (which was just plain C code) and checked it into the source repository, throwing away the preprocessor and it's input files.

In later years I wrote yet another rule engine as a part of what became the Jackpot plugin for NetBeans. It's syntax was a little more humane and a lot more powerful:

$a/2 => $a>>1 :  $a instanceof int && $a>=0

Read "=>" as "becomes" and ":" as "where". The "where" clause allowed boolean predicates based on type and value inferencing. The predicates used a three state logic: true/false/maybe. For every point in a program Jackpot maintained a set of things-known-to-be-true. This most commonly came from if statements. Following if(b) b was known-to-be-true in the then clause, and !b was known-to-be-true in the else clause. It wasn't good enough for anyone in the theorem-proving community to find respectable, but it was good enough to be remarkably useful (I'm a huge fan of "good enough").

The parser in both ACE and Jackpot was somewhat lenient. Particularly in ACE, this was used in a manner similar to how closures are used in languages like Scala and Ruby to create what look like new statements. But they were much more powerful because it was possible to introspect on the body in a very detailed way. Writing a set of transformation rules that would construct a Newton's-method function from an equation was possible in ACE.

Food for thought.

Update: One reader commented:

These map precisely to Scala pattern-match expressions: $replace $0*2; $with $0<<1; could look like: case Mul(a,Num(2)) => LeftShift(a, 1) and $a/2 => $a>>1 : $a instanceof int && $a>=0 would be case Div(a,2) if a.isInstanceOf[Int] && a >= 0 except that it seems like the predicate in ACE could be evaluated lazily on a per-execution basis if I understand correctly.

This is roughly correct, but the "could be evaluated lazily" point is crucial. The really hard part in these systems is getting them to perform. Jackpot would take thousands of rules and compile them down to optimized inline code that was extremely fast. To understand how this worked, read up on database query optimization and the constructive equivalence of deterministic and non-deterministic finite state automata. In jackpot the rule matcher's performance was (almost) independent of the number of rules or their complexity. Applying thousands of rules to millions of lines of code worked remarkably well.

Also, both exploited algebraic transformations in matching. For example, !(a<b) was matched by the same patterns as a>=b

May 27, 2011