Browse by author
Lookup NU author(s): Professor Paul WatsonORCiD
Full text is not currently available for this publication.
Models of computation for the evaluation of Functional Programs are based on the rules for reducing Lambda Calculus expressions. Reduction is achieved by the application of the ß-conversion rule to suitable redexes, but few models of computation provide a full implementation of this rule because of the complexity of avoiding variable name clashes. Consequently, evaluation orders are restricted to those in which name clashes cannot occur. This thesis develops a model of computation for the parallel reduction of Lambda Calculus expressions, represented in De Bruijn's name-free notation, which does provide a full implementation of ß-conversion, allowing expressions to be reduced by any evaluation order. The model is designed to allow reduction to be performed on a parallel machine comprised of a set of processor/store pairs connected by a communications network. A data-driven, graph reduction execution mechanism is used to exploit the parallel hardware efficiently. A language for specifying graph reduction models of computation is proposed, and is used to give a full specification of the Lambda Calculus reduction model. Specifications in the language can be compiled to the . instruction set of a virtual machine. The code produced can then be executed by a virtual machine emulator, or could be recompiled to the order code of a physical processor to allow the high performance simulation of models of computation. The virtual machine is used as the foundation for the design of a physical machine which would support the parallel reduction of lambda calculus expressions. One of the major issues in the design of graph reduction models of computation is the removal of redundant parts of the expression graph. Neither of the two standard Garbage Collection schemes: Reference Count, or Mark-Scan is entirely suitable for a distributed machine, mainly because of the synchronisation they require. A modified Reference Count Garbage Collection scheme is described which removes the need for synchronisation, and enhances some of the attractive properties of Reference Count Garbage Collection.
Author(s): Watson P
Publication type: Authored Book
Publication status: Published
Year: 1986
Number of Pages: 137
Print publication date: 31/07/1986
Online publication date: 05/12/1986
Acceptance date: 05/12/1986
Publisher: University of Manchester
Place Published: Manchester
