I am not sure if you want more examples, but: Spreadsheets often carefully avoid recomputation (a.k.a. caching or memoization) Gosper's HashLife is an example of clever memoization Blelloch, Acar and Harper have a couple papers called "Selective Memoization" and "Adaptive Functional Programming" about memoization and incremental recomputation that seem (to my idiot eyes) to offer a programming language theory-based approach to control of memoization (you can memoize everything and some programming languages do but it's not usually practical.)
Soar has a form of memoization called chunking that is a little bit "lifted". Rather than a function computing an output from an input, and then storing an input/output pair, there's a backtracing step and the thing that is memoized is a rule that has variables in it - it may be able to apply to sufficiently similar inputs, a form of explanation-based generalization. I think it's also a bit like just-in-time compilation. Just-in-time compilation is an example of selective memoization - the compiled code (as you mention) is the output of a computation, and keeping an executable around is a cache. However, you don't necessarily want to do the compilation step; the heuristics around just-in-time computation are about how to decide when it would be worthwhile to start a cache. Johnicholas
-- To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss
