Parametric heap usage analysis for functional programs

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.