%A Kish Shen
%T An investigation of the Argonne model of OR-parallel Prolog
%R M.Sc. thesis
%I Department of Computer Science,
University of Manchester
%D November 1986
%P 212

%A Andy Cheese
%T The applicability of SKI(BC) combinators
in a parallel rewrite rule environment
%R M.Sc. thesis
%I Department of Computer Science,
University of Manchester
%D October 1985
%X ABSTRACT:
     Functional programming languages possess two major advantages
over traditional imperative languages, they are free from side effects
and explicit commands.  This means that they are referentially
transparent instead of being referentially opaque. This property
implies that it is possible to reason about functional language
programs on a basis of a static analysis of the program text.  Because
of their mathematical properties, functional languages will prove to
be more amenable to formal verification methods, leading to the long
awaited reduction in software costs.
     The main obstacle against their widespread use has been the
difficulty of achieving a tolerable performance on existing hardware.
The main reason behind this inefficiency has been the need to support
an environment, a mapping of variables currently in scope to their
current values.  Maintaining storage for this environment and
constantly searching through it for the value of a variable are the
major causes of this inefficiency. By using combinatory logic, a
functional program can be translated into a form from which all bound
variables have been removed. The chief advantages of this approach is
that the problem of needing a ubiquitous environment is now replaced
by a small number of primitive constants which selectively ship to
each subexpression of the program only that part of the environment
that is referenced in the subexpression.
     There have been a number of proposals for implementations that
are based on conventional serial techniques. A parallel implementation
based on a graphical packet based rewrite rule model is investigated
and a comparative assessment of this and the implementation proposed
by the alvey Flagship project is undertaken.  In the light of this the
combinator set is modified in order for it to be more suited to
parallel evaluation schemes.