This thesis describes some techniques that can be used to reduce this overhead. Specifically, we eliminate thunk and eval operations, use unboxed data representations and try to avoid updating thunks. These optimizations depend on information gained by a program-wide dataflow analysis which is based on a polymorphic subtype inference system.
The techniques have been implemented in a compiler for a simple lazy functional language called Plain, and this implementation is described in some detail. The issue of memory management is also discussed and the compilers garbage collector is presented.
Finally, some experimental results are given.
Postscript,
compressed Postscript
We address these shortcomings with an approach based on a novel type system integrating recursive types, subtyping with liberal union types, and system F style polymorphism, in a constraint based formulation. The type system is "soft" in the sense that it does not reject programs. It is also not decidable, but there is a broad spectrum of sound and terminating, though incomplete, algorithms whose precision can be characterized by restricting the substitutions used for instantiation of type schemes.
We give an inference algorithm which is based on constraint solving and which
has the important property that the constraints generated from a function
definition can be simplified before being put in a type scheme. Thus we
believe that combinatorial explosion can be avoided in practice. Type schemes
are also a suitable representation for communicationg the analysis result
over module boundaries, making separate compilation feasible.
Postscript,
compressed Postscript
This thesis describes some techniques that can be used to reduce this overhead. Specifically, we eliminate thunk and eval operations, use unboxed data representations and try to avoid updating thunks. These optimizations depend on information gained by a program-wide dataflow analysis which is based on a polymorphic subtype inference system.
The techniques have been implemented in a compiler for a simple lazy functional language called Plain, and this implementation is described in some detail. Some experimental results are also given.
A different method for flow analysis is also presented. It can be seen as
a soft type system based on higher order polymorphism, and is closely
related to the kind of polyvariance found in abstract interpretation
based approaches. Starting from this technique for flow analysis, a
combined analysis and transformation system is defined. It performs the
transformations mentioned above,
but without ever constructing the flow information for the entire program.
These transformations also incorporate cloning, to improve the results
on large programs.
Postscript,
compressed Postscript
This paper presents a global approach to representation analysis based on program-wide data and control flow information. Coercions can be placed around any variable occurrence, not only where values are produced and consumed.
The analysis first constructs a graph representing all legal coercion placements, then selects one of them using a coercion placement strategy. Several such strategies are discussed and preliminary measurements are presented.
When combined with function cloning, the analysis is powerful enough to eliminate almost all coercions from several nonstrict programs, including a simple polymorphic type checker.
The analysis allows the use of unboxed data in data structures and as arguments in indirect function calls, yet it uses only simple coercions (box or unbox integers and other scalar data). No coercions which traverse recursive data structures are needed.
Our method is applicable
to a wide variety of functional languages; we formulate it over an untyped
call-by-value language called Fleet, which contains explicit graph reduction
constructs. Fleet can be used as an intermediate language for strict as well as
nonstrict and typed as well as untyped languages.
DVI, Postscript,
compressed Postscript
In this paper we try to quantify both the benefits and costs of cloning in
the context of an optimizing compiler for a simple lazy functional language.
We will also evaluate a few techniques for reducing the number of instruction
cache misses.
DVI, Postscript,
compressed Postscript
In this paper we show that significant speedups are achievable by cheap eagerness.
Our cheapness analysis uses the results of a program-wide data and control flow
analysis to find out which variables may be unevaluated and which
variables may be bound to functions which are dangerous to call.
DVI, compressed Postscript
Overloading is translated into explicit dictionary passing, as in all current implementations of Haskell. The target language of this translation is a variant of the Girard-Reynolds polymorphic lambda calculus featuring higher order polymorphism and explicit type abstraction and application in the term language. Translated programs can thus still be type checked, although the implicit version of this system is impredicative.
A surprising result of this formalization effort is that the monomorphism
restriction, when rendered in a system of inference rules, compromises the
principal type property.
DVI, compressed Postscript
We also discuss how these problems can be solved by introducing quantified class
constraints and strengthening the monomorphism restriction from prohibiting
only the generalization of constrained type variables to prohibiting any
generalization
at all. We also give an inference algorithm producing principal
types for the new system.
Postscript, PDF