Steffen Jost, Amortized Analysis and Lazy Evaluation

Steffen Jost
Amortized Analysis & Lazy Evaluation

We will discuss the development process of extending the type-based amortised analysis technique to automatically infer heap-space bounds for a lazily evaluated first-order functional language. Of course, the analysis has to deal with streams whose processing consumes fresh memory at each step and streams who simply evaluate to cyclic data, whose processing thus does not requiring any additional memory.
At the first glance a solution semeed to be relatively straightforward, but as we will see, our first naive approach had many pitfalls. In the end a mixture of our reference-based potential and the classic memory-based potential as used by Tarjan saves the day.