Compiling Curried Functional Languages to .NET
Jason Smith
Department of Computer Science
University of Canterbury
Abstract
Recent trends in programming language implementation are moving more and more towards “managed” runtime environments. These offer many ben- efits, including static and dynamic type checking, security, profiling, bounds checking and garbage collection. The Common Language Infrastructure (CLI) is Microsoft’s attempt to define a managed runtime environment. However, since it was designed with more mainstream languages in mind, including C] and C++, CLI proves restrictive when compiling functional languages. More specifically, for compilers such as GHC, which compiles Haskell, the CLI provides little support for lazy evaluation, currying (partial applications) and static type checking. The CLI does not provide any way of representing a computation in an evaluated and non-evaluated form. It does not allow functions to directly manipulate the runtime stack, and it restricts static typing in various forms; including subsumption over function types.
In this thesis, we describe a new compilation method that removes the need for runtime argument checks. Runtime argument checking is required to ensure proper reduction semantics in situations where the arity of a function may be statically unknown. We introduce a new set of annotations, called operational types, which provide an abstract model of reduction. From these operational annotations we can construct a transformation, called lambda doping, which saturates all partial applications, removing the need for run- time argument checks. This enables the CLI to support an eager, curried, higher order functional language.
We also describe a type inference algorithm that infers universally quan- tified types with implicit widening coercions. We show that we can easily include the generation of operational typings from type inference. We restrict type inference to simple extensions of the usual unification algorithm, given by Hindley-Milner, so that inference is immediately applicable to most com- mercial functional languages. We also develop a set of transformations which demonstrate that for the most part inferred types can be readily mapped to the CLI.
Finally, we develop a practical implementation of a higher-order, curried eager functional language, called Mondrian.