Steffen Jost, Amortized Analysis and Lazy Evaluation
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.