Once Upon a Polymorphic Type

K Wansbrough, Simon Peyton Jones

26th ACM Symposium on Principles of Programming Languages (POPL'99) |

Published by ACM Press

Submitted to The Twenty-sixth ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'99)

View Publication | View Publication

We present a sound type-based `usage analysis’ for a realistic lazy functional language. Accurate information on the usage of program subexpressions in a lazy functional language permits a compiler to perform a number of useful optimisations. However, existing analyses are either ad-hoc and approximate, or defined over restricted languages.

Our work extends the Once Upon A Type system of Turner, Mossin, and Wadler (FPCA’95). Firstly, we add type polymorphism, an essential feature of typed functional programming languages. Secondly, we include general Haskell-style user-defined algebraic data types. Thirdly, we explain and solve the `poisoning problem’, which causes the earlier analysis to yield poor results. Interesting design choices turn up in each of these areas.

Our analysis is sound with respect to a Launchbury-style operational semantics, and it is straightforward to implement. Good results have been obtained from a prototype implementation, and we intend to integrate the system into a production compiler.