Wed Jul 15 09:37:11 CEST 2009
Program analysis (PA) is undecidable because of state dependent
control flow. The culprit is the "IF" statement, or anything that
boils down to turning a form of data into an execution branch target.
Partial evaluation (PE) is a form of PA. Effective partial evaluation
is essentially about trying to figure out which "IF" statements can be
computed at run time. Picking the wrong one can lead to infinite code
An interesting approach is to mix lazyness with PE to keep infinite
code structures under control.
The problem with PE is time/space resource analysis. It is not always
possible to assess how much time or space recursive/looping code will
Given the right representation I think it becomes more practical to
get close to some reasonable definition of optimal behaviour. You
need to `dodge the recursion' by concentrating on combinators with
easy-to-manage time and space properties.