Representing Demand by Partial Projections
John Launchbury and Gebreselassie Baraki, in J. Functional Programming,
Vol 6, Number 4, CUP, 1996.
The projection-based strictness analysis of Wadler and Hughes is elegant and theoretically satisfying except in one respect: the need for lifting. The domains and functions over which the analysis is performed need to be transformed, leading to a less direct correspondence than might be hoped for. In this paper we shall see that the projection analysis may be reformulated in terms of partial projections, so removing this infelicity. There are additional benefits of the formulation: the two forms of information captured by the projection are distinguished, and the operational significance of the range of the projection fits exactly with the theory of unboxed types. On a technical note, it is intriguing that the partiality of the projections occurs in a very different place from its occurrence in Hunt's PERs.
Projections for Polymorphic First-Order
Strictness Analysis
John Hughes and John Launchbury,
in J. Mathematical Structures in Computer Science, Vol. 2, CUP, 1992.
We apply the categorical properties of polymorphic functions to compile-time analysis, specifically projection-based strictness analysis. First we interpret parameterised types as functors in a suitable category, and show that they preserve monics and epics. Then we define ``strong'' and ``weak'' polymorphism, the latter admitting certain projections that are not polymorphic in the usual sense. We prove that, under the right conditions, a weakly polymorphic function is characterised by a single instance. It follows that the strictness analysis of one simple instance of a polymorphic function yields results that apply to all. We show how this theory may be applied. In comparison to earlier polymorphic strictness analysis methods, ours can apply polymorphic information to a particular instance very simply. The categorical approach simplifies our proofs, enabling them to be carried out at a higher level, and making them independent of the precise form of the programming language to be analysed. The major limitation of our results is that they apply only to first-order functions.
Implementing Projection-based
Strictness Analysis
Ryszard Kubiak, John Hughes, and John Launchbury,
in Proc. Glasgow Workshop on Functional Programming, Springer-Verlag Workshops
in Computing, 1992.
Projection-based backwards strictness analysis has been understood for some years. Surprisingly, even though the method is fairly simple and quite general, no reports of its implementation have appeared. This paper describes ideas underlying our prototype implementation of the analysis for a simple programming language. The implementation serves as a case study before applying the method in the Glasgow Haskell compiler.
Avoiding Unnecessary Updates
John Launchbury, Andy Gill, John Hughes, Simon Marlow, Simon Peyton Jones,
Philip Wadler,
in Proc. Glasgow Workshop on Functional Programming, Springer-Verlag Workshops
in Computing, 1993.
Graph reduction underlies most implementations of lazy functional languages, allowing separate computations to share results when sub-terms are evaluated. Once a term is evaluated, the node of the graph representing the computation is {\em updated} with the value of the term. However, in many cases, no other computation requires this value, so the update is unnecessary. In this paper we take some steps towards an analysis for determining when these updates may be omitted.