Exploiting Parallelism in Multi-way Recursive Methods
My code generator which is still in the prototyping and experimentation phase does a lot of recursive tree traversals which is quite obvious since it needs to match tree patterns and emit code for abstract syntax trees (AST).
Especially during the code emission phase which does a top down left to right tree traversal it would be nice to recursively evaluate child nodes of an AST in parallel if the evaluation of the child nodes does not yield any side effects. The following paper nicely describes how to transform standard multi-way recursive methods into parallel mutli-way recursive methods in Java.
The transformation described is quite simple and works well for direct recursion. However, due to the attribute type grammar I want to use for my tree pattern matching code generator and the way most tree patterns are augmented with semantic actions, it seems that it would cause a bit of a mess, or at least require a lot of careful thinking how to integrate such parallelism into the tree pattern matching grammar and the code generator which is produced by the grammar specification.
Unfortunately right now this idea can not be assigned a high priority and must be post-poned…
