Finding upper bounds of component instances with deallocation beyond local scope

Abstract

We develop an abstract component language and a static type system that can tells us the maximum resources a program may use. We prove that the upper resource bound is sharp and we point out a polynomial algorithm that can infer the sharp bound. Knowing the maximal resources a program may request allows us to adjust resource usage of the program and to prevent it from raising exceptions or behaving unexpectedly on systems that do not have enough resources. This work extends our previous works in one crucial point: the deallocation primitive can free an instance beyond its local scope. This semantics makes the language much closer to practical ones.