Analysis of Recursive Types in Lisp-like Languages

We introduce a new algorithm to analyze recursive, structured types. It derives information from object uses (accesser functions with type checking), as well as from object allocation. The type description is a form of graph grammar and is naturally finite even in the presence of loops. The intended use of the algorithm is to discover and remove unnecessary type checks, but it can be augmented to provide alias information as well. 1 Introduction We are interested in the behavior of programs in an untyped language with data structures constructed from records containing pointers, typified by Lisp programs that manipulate structures built from cons cells. In this paper, we will introduce a new algorithm to analyze such programs. Unlike many type-inference algorithms, it is designed to work on partial programs (with or without declarations) and to produce partial inferences. The main goal is to remove unnecessary type checks. The algorithm uses information from both object creation and t..