Reuse old subterms

[ngsankha]

Many programs have the form: (str.substr name (+ (str.indexof name "-" 0) 1) (+ (str.indexof name "-" 0) 4)) where (str.indexof name "-" 0) is repeated. Absynthe spends a lot of time duplicating the work to synthesize such repeated subterms. We just need to cache any concrete subterms that are synthesized and reuse them directly. Special care needs to be taken such that a cached subterm can only refer to synthesized terms before it (to avoid expressions becoming a cycle).

This has been done before:

• RbSyn does this to synthesize let bindings while keeping track of the usage count of the subterm. If the usage count is 1 it is inlined at the call site, else if the count is > 1 the subterm is refactored into a let binding.
• DryadSynth (sec 4.1) does this to divide the target problem into smaller parts.

I suspect implementing this will give good performance boosts, but from the point of view of research there is no new contribution here.

[ngsankha]

Partially done with the Cache class. There is no good heuristic to cache expressions now, so we cache on select few. Keeping this open.