Steffen Jost, University of St Andrews

Title: Type-based amortised heap-space analysis (for an object-oriented 
language)

Abstract:
	We present a type system for a compile-time analysis of heap-space 
requirements of Java style object-oriented programs with explicit 
deallocation.

   	Our system is based on an amortised complexity analysis: the data is 
assigned a potential related to its size and layout; allocations must be 
"payed for" from this potential. The potential of each input then 
furnishes an upper bound on the heap space usage for the computation on 
this input. We speculate that the amortised approach can be extended to 
other resources such as time, stack size, and perhaps even functional 
properties.

	We successfully treat inheritance, downcast, update and aliasing. 
Example applications for the analysis include destination-passing style 
and doubly-linked lists.