Leena Unnikrishnan and Scott D. Stoller

This paper presents an analysis that derives a formula describing
the worst-case live heap space usage of programs in a functional
language with automated memory management (garbage collection).
First, the given program is automatically transformed into
*bound functions* that describe upper bounds on the live heap space
usage and other related space metrics in terms of the sizes of function
arguments. The bound functions are simplified and rewritten
to obtain recurrences, which are then solved to obtain the desired
formulas characterizing the worst-case space usage. These recurrences
may be difficult to solve due to uses of the *maximum* operator.
We give methods to automatically solve categories of such recurrences.
Our analysis determines and exploits monotonicity and
monotonicity-like properties of bound functions to derive upper
bounds on heap usage, without considering behaviors of the program
that cannot lead to maximal space usage.