View article

Many program analyses depend on the sizes of each function’s inputs and outputs, and their relations. Relational size analysis, through a form of dependent typing (called sized type), has been successfully applied to declarative programs, and to restricted imperative programs; but it has been elusive for object-based programs. The main difficulty is that objects may mutate and they may be aliased. In this paper, we introduce several key ideas to help track size properties of mutable objects. Our approach strikes a balance between mutability and sharing. We introduce the concept of size-immutability to facilitate sharing, and also a set of alias controls to identify unique mutable objects in support of precision in sized typing. We formalise our results through a set of advance typechecking rules for an object-based imperative language. Through a set of safety theorems, we confirm key properties on both the uniqueness …