CMP.3:4.4 - Retain what remains live, and recompute selectively

A value is live while a later operation will need it and cannot obtain it more cheaply by another means. Find its last planned consumer. After that use, the storage can be reused unless the requested final output needs the value for reconstruction.

Compare full retention, a moving set of recent values, and selected stored checkpoints from which intervening work is recomputed. Include key storage, lookup, copying, arithmetic size and transfer costs when they can change the choice. The mathematical dependency graph can be unchanged while these execution costs differ substantially.

Recomputation must reproduce the needed value from retained inputs and conditions. If it repeats an external effect or uses changed data, its meaning needs separate treatment. A stored checkpoint is useful only if it contains enough information to restart that part of the computation.