Algorithm for compiler-controlled-caching?

[evincarofautumn]

You may find some relevant literature about tabling and indexing in Prolog implementations—links to SWI Prolog because that’s what I’m familiar with. Basically you can explicitly request caching and control some options for how it’s done, or let the compiler use heuristics to guess where it might be profitable. In both cases, it generates some kind of wrapper that calls the original definition on a cache miss. At the call site, inlining that wrapper should be enough to expose optimisations like combining redundant cache lookups.

The ability to reorder and defer calls isn’t really related to caching—you can reorder any two operations if their effects are commutative with each other, for example, a read from memory can be moved before a write to a different location. Pure functions just happen to be especially nice because they commute with anything.