The implementation of practical functional programming languages.
Author(s)
Perry, Nigel
Abstract
This thesis is about the design and implementation of practical functional languages. We begin with a discussion of functional language 1/0, and survey existing 1/0 schemes highlighting their drawbacks. We then present a new 1/0 scheme, based on what we term result continuations, which overcomes these drawbacks. Result continuations solve the 1/0 problem by arranging for all I/O to be performed on behalf of the program by the O/S outside the functional domain, thus maintaining referential transparency and providing 1/0 sequence control. We later extend our I/O system to provide an inter-language interface between functional and imperative programs. We describe a new implementation method for functional languages, based upon a conventional imperative model modified to support and optimize the execution of functional· languages. This provides comparable performance to imperative languages, and can be extended to coarse-grained implementations for current MIMD machines. The ability to overload identifiers with multiple definitions is a convenient programming feature, allowing for example the same symbol to be used for integer and matrix multiplication. Our interlanguage calling mechanism together with certain useful abstractions, such as abstract data types, require existential quantification of type variables in type definitions. We show how these two can be supported in a language with polymorphism and type inference, and detail both a type system and type-checking algorithm for handling the combination of all four. We demonstrate that despite the fundamental impact existential quantification has on the type system its implementation in a type-checker can share the same mechanism as polymorphism. We further demonstrate that overloading resolution can be handled without introducing an unacceptable performance penalty. Our research was undertaken as part of the Hope* project, part of Alvey Flagship, the aim of which was to construct a practical pure functional language system running on conventional sequential hardware.
Version
Open Access
Date Awarded
1991
Copyright Statement
Attribution-Non Commercial-No Derivatives 4.0 International Licence (CC BY-NC-ND)
Sponsor
Alvey Flagship project.
Publisher Department
Department of Computing
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)