ftp. Most are also
available in paper report form from the address below at the prices
indicated.Functional Programming Group
Process Semantics of Graph Reduction
Load Bounding for Implicit Parallelism
Pi-Calculus Characterizations of Some Practical
Lambda-Calculus Reduction Strategies
Modelling Parallel Graph Reduction in the Pi-Calculus
Models for Persistence in Lazy Functional
Programming Systems
Parallel Functional Programming for
Message-Passing Multiprocessors
PCASE - A Persistent Lazy Version of an SECD Machine
Parallel Functional Computation on STAR:DUST
Two Models for Integrating Persistence and Lazy
Functional Languages
CASE - A Lazy Version of an SECD Machine with a Flat
Environment
Statically Typed Applicative Persistent Language Environment
(STAPLE) User's Manual
Process Semantics of Graph Reduction
Brock, S., Ostheimer, G.
University of St Andrews Technical Report CS/95/2, March 1995
We present an operational semantics for call-by-need reduction in terms of an encoding of the lambda calculus in Milner's pi-calculus. Correctness of the encoding is proved with respect to the call-by-need lambda-calculus of Ariola et al. The compactness and intuitiveness of the process calculus presentation makes it interesting as an alternative method for defining what is meant by 'call-by-need'. With respect to applications, the interest of this work lies in the use of pi-calculus as an abstract yet realistic target language. The practical value of the encoding is demonstrated with an outline for a parallel code generator.
Compared to the work presented in TR CS/93/14, this report focusses on a single reduction strategy, call-by-need, and strengthens the theoretical foundations of the encoding. The section on implementation is new and has prompted some small changes to the encodings (e.g, we now use only the asynchronous subset of the monadic pi-calculus).
Download process-semantics.ps.Z (93K)
Printed report: £1.00
--------------------
Load Bounding for Implicit Parallelism
Ostheimer, G., Davie, A.J.T
University of St Andrews Technical Report CS/94/11, first presented at the Fourth
International Workshop on the Parallel Implementation of Functional Languages, Aachen,
Germany, September 1992
It is well known that exploiting parallelism beyond the available machine parallelism can lead to vastly increased resource requirements. Programs which can run in linear space under a sequential execution regime may require exponential space in the context of unrestricted parallelism.
In this paper we present an efficient adaptive software solution for the problem of avoiding excessive parallelism when evaluating implicitly parallel functional programs. We give an informal proof for the effectiveness of our method and discuss its limitations. The solution and the proof are based on a compilation scheme mapping lazy functional programs onto message-passing parallel architectures. Our strategy is completely distributed and can be expected to scale well to large machine configurations.
Download load-bounding.ps.Z (55K)
Printed report: £1.00
--------------------
Pi-Calculus Characterizations of Some Practical Lambda-Calculus
Reduction Strategies
Ostheimer, G., Davie, A.J.T
University of St Andrews Technical Report CS/93/14, October 1993
We give pi-calculus encodings of some reduction strategies that have been found useful in the functional programming community: call-by-value, parallel call-by-value, call-by-need and call-by-process. The ease with which the pi-calculus lends itself to expressing these different reduction strategies is remarkable. All four of our encodings can be 'mixed and matched' in that different reduction strategies can be applied to different parts of the program, as is routinely done in functional programming systems. (This is an extended version of the workshop paper below.)
Printed report: £1.00
--------------------
Modelling Parallel Graph Reduction in the Pi-Calculus
Ostheimer, G., Davie, A.J.T
Proc. Fifth International Workshop on the Implementation of Functional Languages,
Nijmegen, The Netherlands, September 1993
We have derived from a practical compilation scheme presented previously a formal model for parallel graph reduction of the lambda-calculus in the pi-calculus. This work solves the known open problem of modelling a call-by-need reduction strategy in the pi-calculus. Models for call-by-name and a parallel version of call-by-value have been given by Robin Milner. We can apply different reduction strategies to different parts of a lambda-term to combine the benefits of lazy semantics with those of safe parallelism.
--------------------
Models for Persistence in Lazy Functional Programming
Systems
McNally, D.
PhD Thesis, University of St Andrews Technical Report CS/93/9
Research into providing support for long term data in lazy functional programming systems is presented in this thesis. The motivation for this work has been to reap the benefits of integrating lazy functional programming languages and persistence. Two models are porposed which make persistence available to the functional programmer. The first, persistent modules, allows values named in modules to be stored in persistent storage for later reuse. The second model, stream persistence allows dynamic, interactive access to persistent storage. These models are supported by a system architecture which incorporates a persistent abstract machine, PCASE, integrated with a persistent object store. The resulting persistent lazy functional programming system, Staple, is used in prototyping and functional database modelling experiments.
Download lazy-persistence.ps.Z (242K)
Printed report: £5.00
--------------------
Parallel Functional Programming for Message-Passing
Multiprocessors
Ostheimer, G.
PhD Thesis, University of St Andrews Technical Report CS/93/8, March 1993
We propose a framework for the evaluation of implicitly parallel functional programs on message passing multiprocessors with special emphasis on the issue of load bounding. The model is based on a new encoding of the lambda-calculus in Milner's pi-calculus and combines lazy evaluation and eager (parallel) evaluation in the same framework. The pi-calculus encoding serves as the specification of a more concrete compilation scheme mapping a simple functional language into a message passing, parallel program. We show how and under which conditions we can guarantee successful load bounding based on this compilation scheme. Finally we discuss the architectural requirements for a machine to support our model efficiently and we present a simple RISC-style processor architecture which meets those criteria.
Printed report: £5.00
--------------------
PCASE - A Persistent Lazy Version of an SECD Machine
Davie, A.J.T, McNally, D.J.
University of St Andrews Technical Report CS/92/7
This document describes a machine suitable for persistent applicative programming. It is a variation of Landin's classical SECD machine but its environment is organized in a novel efficient way based on a method given in a previous report. It has features allowing the execution of code to reflect a lazy semantics and others to allow the persistence of objects in their current state of evaluation after the machine has ceased execution. It is a development of a similar non-persistent machine (CASE). It has been used to implement two kinds of lazy persistence in the programming language STAPLE.
Printed report: £1.00
--------------------
Parallel Functional Computation on STAR:DUST
Ostheimer, G.
University of St Andrews Technical Report CS/92/2, also appeared in Proc.
Workshop on the Parallel Implementation of Functional Languages, Southampton,
June 1991
STAR:DUST ('St. Andrews RISC: Dataflow Using Sequential Threads') is a processor design optimized for efficient execution of sequential threads while supporting plug-and-play construction of large multiprocessor systems. Besides satisfying the major RISC criteria (small instruction set, simple instruction format, load/store principle, pipelining), STAR:DUST employs a dataflow approach to communication and parallelism. We describe the architecture and propose a runtime model for parallel functional computation based on STAR:DUST's dataflow primitives.
Printed report: £1.00
--------------------
Two Models for Integrating Persistence and Lazy Functional
Languages
McNally, D.J., Davie, A.J.T
University of St Andrews Technical Report CS/91/1
A new programming system--STAPLE (Statically Typed Applicative Persistent Language Environment)--which integrates a lazy functional programming language and a persistent store is described. The motivation for introducing orthogonal persistence into a functional setting is given. Two models for achieving this integration are then described together with a discussion of the way laziness interacts with persistence and the benefits resulting from this interaction. In the first model, a system of persistent modules allows the pgrammer to create persistent values by naming them in a module. In the second model, a combination of stream I/O and a dynamic type allows functional programs to manipulate values already in the persistent store and to allow dynamically created values to become persistent.
Printed report: £1.00
--------------------
CASE - A Lazy Version of an SECD Machine with a Flat
Environment
Davie, A.J.T, McNally, D.J.
University of St Andrews Technical Report CS/90/19
Graph reduction has been the basis of most fast running implementations of functional languages, with little attention being paid recently to Landin's SECD approach. CASE is an abstract machine which supports applicative programming and is a variation of Landin's classical SECD machine. Its environment is organized in a novel way which makes variable access more efficient by removing the overhead of following a static chain or of setting up a display as in more conventional stack architectures. The CASE machine also has features allowing the execution of code to reflect lazy evaluation semantics. We describe the architecture of the machine, its operational semantics, and code generated by a typcial compiler for some sample programs. We also discuss some optimisations made to facilitate efficient code generation on real hardware and give some measurements of the efficiency of the machine.
Printed report: £1.00
--------------------
Statically Typed Applicative Persistent Language Environment (STAPLE)
User's Manual
Davie, A.J.T, McNally, D.J.
University of St Andrews Technical Report CS/90/14
The STAPLE persistent functional programming environment is a system allowing the development and testing of prototype functional modules and their combination into packages. These form an environment which allows the interactive evaluation of expressions using the bindings in modules. The system was developed as part of ESPRIT project 891.
--------------------
gerald@dcs.st-andrews.ac.uk 16/9/94.