Demand -driven type analysis for dynamically-typed functional languages

We present a new static type analysis for dynamically-typed languages that produces high quality results at a cost that remains practicable. The analysis has the ability to adapt to the needs of the optimiser and to the characteristics of the program at hand. The result is an analyser that quickly transforms itself to be better equipped to attack the program. Experiments show that our approach can be pretty clever in the optimisations that it enables.

The analysis is adaptable because it is accomplished using a parametric analysis framework that can instantiate analyses by building them from abstract models. The abstract models can be changed during the analysis of the program. Many properties of the analysis framework are presented and proved in the dissertation. Among which there is the guarantee of termination of any analysis instance it produces, the capacity to analyse perfectly well error-free terminating programs, and the ability to mimic many conventional static analyses.

Modifications to the abstract model in response to the needs of the optimiser are realised through the use of demands and demand processing rules. Demands express a request for the demonstration of a property deemed useful to the optimiser. The processing rules allow demands that directly express the needs of the optimiser to be translated into precise proposals of modifications to the abstract model. Each modification to the model that is proposed is potentially directly helpful to the optimiser because the processing rules ensure that pertinent demands are translated into other pertinent demands.

A complete approach of demand-driven analysis based on pattern-matching is exposed and has been implemented. The prototype implementing the approach has demonstrated that our work has great potential. Further research has to be conducted to make the method usable in everyday compilers. Still, this is understandable, considering that our whole work, except the notions related to conventional static analysis, is original material.