[project @ 1996-01-08 20:28:12 by partain]

[ghc-hetmet.git] / ghc / docs / abstracts / abstracts89.tex

\documentstyle[11pt,slpj]{article}

\newcommand{\reference}[4]{     % authors, title, details, abstract
\large
#1, {\em #2}, #3.
\normalsize
\begin{quotation}
#4
\end{quotation}
\vspace{0.2in}
}

\newcommand{\Haskell}[1]{{\sc Haskell}}

\begin{document}

\title{Abstracts of GRIP/GRASP-related papers and reports till 1989\\
Dept of Computing Science \\
University of Glasgow G12 8QQ}

\author{
Cordelia Hall (cvh@cs.glasgow.ac.uk) \and
Kevin Hammond (kh@cs.glasgow.ac.uk) \and
Will Partain (partain@cs.glasgow.ac.uk) \and
Simon L Peyton Jones (simonpj@cs.glasgow.ac.uk) \and
Phil Wadler (wadler@cs.glasgow.ac.uk) 
}

\maketitle

\begin{abstract}
We present a list of papers and reports related to the GRIP 
and GRASP projects,
covering {\em the design, compilation technology,
and parallel implementations of functional programming languages, especially
\Haskell{}}.

Most of them can be obtained by writing to 
Teresa Currie, Dept of Computing Science,
University of Glasgow G12 8QQ, UK.   Her electronic mail address is
teresa@uk.ac.glasgow.cs.

Those marked ($\spadesuit$) can be obtained from the School of Information
Systems, University of East Anglia, Norwich, UK.
Those marked ($\clubsuit$) can be obtained from Chris Clack at the
Department of Computer Science, University College London, Gower St, 
London WC1E 6BT, UK.
\end{abstract}

\section{Published papers}

\reference{Simon L Peyton Jones and Jon Salkild}
{The Spineless Tagless G-machine}
{Proc IFIP Symposium on Functional Programming Languages and Computer
Architecture, London, Sept 1989}
{
The Spineless Tagless G-machine is an abstract machine based on graph
reduction, designed as a target for compilers for non-strict functional
languages.
As its name implies, it is a development of earlier work, especially
the G-machine and Tim.

It has a number of unusual features: the abstract machine code is
rather higher-level than is common, allowing better code generation;
the representation of the graph eliminates most interpretive overheads;
vectored returns from data structures give fast case-analysis;
and the machine is readily extended for a parallel implementation.

The resulting implementation runs at least 75\% faster 
than the Chalmers G-machine.
}

\reference{Simon L Peyton Jones}
{Parallel implementations of functional programming languages}
{Computer Journal 32(2), pp175-186, April 1989}
{
It is now very nearly as easy to build a parallel computer
as to build a sequential one, and there are strong incentives to do so:
parallelism seems to offer the opportunity to improve both the 
absolute performance level and the cost/performance ratio of our machines.

One of the most attractive features of functional programming languages
is their suitability for programming such parallel computers.
This paper is devoted to a discussion of this claim.

First of all, we discuss parallel functional programming
from the programmer's point of view.
Most parallel functional language implementations are based on graph reduction,
we proceed to a discussion of some implementation issues raised by parallel 
graph reduction.
The paper concludes with a case study of a particular parallel graph reduction
machine, GRIP, and a brief survey of other similar machines.
}

\reference{Kevin Hammond}
{Implementing Functional Languages for Parallel Machines}
{PhD thesis, University of East Anglia, 1989 ($\spadesuit$)}
{Commencing with the Standard ML language, dialects  XSML  and  PSML  are
defined,  which permit parallel evaluation of functional programs.  XSML
is Standard ML with a novel mechanism for handling exceptions; PSML is a
side-effect  free  version  of  XSML.  A formal semantics for PSML and a
translation algorithm from this language into Dactl, a  compiler  target
language  based  on  the  theory of graph-rewriting, are presented.  The
thesis proves that a simplified version of  this  translation  preserves
meaning  for flat domains, and that the strategy for reduction to normal
form is correct.

The implementation of standard compilation techniques such as strictness
analysis, maximal free sub-expression elision and common sub-expresssion
elimination  is  considered  with  respect  to   Dactl,   and   problems
highlighted.     Techniques    are    also   presented   for   compiling
exception-handling  correctly  in  a  parallel  environment,   and   for
compiling  side-effect  for a parallel machine.  Metrics for performance
evaluation are presented and results obtained using the Dactl  reference
interpreter are presented.}


\reference{Simon L Peyton Jones, Chris Clack and Jon Salkild}
{High-performance parallel graph reduction}
{Proc Parallel Architectures and Languages Europe (PARLE), LNCS 365, pp193-207, 
July 1989}
{
Parallel graph reduction is an attractive implementation for functional 
programming languages because of its simplicity and inherently distributed
nature.
This paper outlines some of the issues raised by parallel compiled
graph reduction, and presents the solutions we have adopted to produce an
efficient implementation.

We concentrate on two particular issues:
the efficient control of parallelism, resulting in an ability to alter
the granularity of parallelism 
{\em dynamically};
and the efficient use of the memory hierachy to improve locality.
}

\reference
{Phil Trinder and Philip Wadler}
{Improving list comprehension database queries}
{{\em TENCON '89\/} (IEEE Region 10 Conference),
Bombay, India, November 1989.}
{
The task of increasing the efficiency of database queries has recieved
considerable attention. In this paper we describe the improvement of
queries expressed as list comprehensions in a lazy functional
language. The database literature identifies four algebraic and two
implementation-based improvement strategies. For each strategy we show
an equivalent improvement for queries expressed as list
comprehensions.  This means that well-developed database algorithms
that improve queries using several of these strategies can be emulated
to improve comprehension queries.  We are also able to improve queries
which require greater power than that provided by the relational
algebra.  Most of the improvements entail transforming a simple,
inefficient query into a more complex, but more efficient form. We
illustrate each improvement using examples drawn from the database
literature.
}

\reference{Kevin Hammond}
{Exception Handling in a Parallel Functional Language: PSML}
{Proc TENCON '89, Bombay, India, Nov 1989}
{
Handling exception occurrences during computation is a problem  in  most
functional programming languages, even when the computation is eager and
sequential.  This paper presents a version of  the  error  value  method
which  allows lazy computation with deterministic semantics for parallel
evaluation even in the presence of  errors.   The  realisation  of  this
technique   is   illustrated  by  reference  to  PSML,  a  referentially
transparent variant of Standard ML designed for parallel evaluation.
}

\reference
{Philip Wadler}
{Theorems for free!}
{{\em 4'th International Conference on Functional Programming
Languages and Computer Architecture}, London, September 1989.}
{
From the type of a polymorphic function we can derive a theorem
that it satisfies.  Every function of the same type satisfies the same
theorem.  This provides a free source of useful theorems,
courtesy of Reynolds' abstraction theorem for the polymorphic lambda
calculus.
}

\reference
{Philip Wadler and Stephen Blott}
{How to make {\em ad-hoc\/} polymorphism less {\em ad hoc}}
{{\em 16'th ACM Symposium on Principles of Programming Languages},
Austin, Texas, January 1989.}
{
This paper presents {\em type classes}, a new approach to {\em
ad-hoc\/} polymorphism.  Type classes permit overloading of arithmetic
operators such as multiplication, and generalise the ``eqtype variables''
of Standard ML.
Type classes extend the Hindley\X Milner polymorphic type system, and
provide a new approach to issues that arise in object-oriented
programming, bounded type quantification, and abstract data types.
This paper provides an informal introduction to type classes, and
defines them formally by means of type inference rules.
}

\reference{Kevin Hammond}
{Implementing Type Classes for Haskell}
{Proc Glasgow  Workshop  on  Functional  Programming,  Fraserburgh, Aug 1989}
{
This  paper describes the implementation of the type class mechanism for
the functional language Haskell, which has been  undertaken  at  Glasgow
University.  A simple introduction to type classes discusses the methods
used to  select  operators  and  dictionaries  in  the  Glasgow  Haskell
compiler.    A   solution   to  the  problem  of  selecting  super-class
dictionaries, not considered by the original paper  on  type  class,  is
also  presented.   The  modifications which must be made to the standard
Hindley/Milner type-checking algorithm  to  permit  the  translation  of
operators  are  described,  and  a  revised definition of algorithm W is
provided. Finally, a set of performance figures  compares  the  run-time
efficiency of Haskell and LML programs, indicating the overhead inherent
in the original, naive method of operator selection, and the improvement
which may be obtained through simple optimisations.
}

\reference{Simon L Peyton Jones}
{FLIC - a functional language intermediate code}
{SIGPLAN Notices 23(8) 1988, revised 1989}
{
FLIC is a Functional Language Intermediate Code, intended to
provide a common intermediate language between diverse
implementations of functional languages, including parallel
ones.
This paper gives a formal definition of FLIC's syntax and
semantics, in the hope that its existence may encourage greater
exchange of programs and benchmarks between research groups.
}

\reference{Simon L Peyton Jones, Chris Clack, Jon Salkild, Mark Hardie}
{Functional programming on the GRIP multiprocessor}
{Proc IEE Seminar on Digital Parallel Processors, Lisbon, Portugal, 1988}
{
Most MIMD computer architectures can be classified as 
tightly-coupled or loosely-coupled,
depending on the relative latencies seen by a processor accessing different
parts of its address space.

By adding microprogrammable functionality to the memory units, we have
developed a MIMD computer architecture which explores the middle region
of this spectrum.
This has resulted in an unusual and flexible bus-based multiprocessor,
which we are using as a base for our research in parallel functional programming
languages.

In this paper we introduce parallel functional programming, and describe
the architecture of the GRIP multiprocessor.
}

\reference{Geoffrey Burn, Simon L Peyton Jones, and John Robson}
{The spineless G-machine}
{Proc ACM Conference on Lisp and Functional Programming, Snowbird, pp244-258,
August 1988}
{
Recent developments in functional language implementations have
resulted in the G-machine, a programmed graph-reduction machine.
Taking this as a basis, we introduce an optimised method of
performing graph reduction, which does not need to build the
spine of the expression being reduced.
This Spineless G-machine only updates shared expressions, and
then only when they have been reduced to weak head normal form.
It is thus more efficient than the standard method of performing
graph reduction.

We begin by outlining the philosophy and key features of the
Spineless G-machine, and comparing it with the standard
G-machine.
Simulation results for the two machines are then presented and
discussed.

The Spineless G-machine is also compared with Tim, giving a
series of transformations by which they can be interconverted.
These open up a wide design space for abstract graph reduction
machines, which was previously unknown.

A full specification of the machine is given in the appendix,
together with compilation rules for a simple functional language.
}

\reference{Chris Hankin, Geoffrey Burn, and Simon L Peyton Jones}
{A safe approach to parallel combinator reduction}
{Theoretical Computer Science 56, pp17-36, North Holland, 1988}
{
In this paper we present the results of two pieces of work which, when
combined, allow us to take a program text of a functional langauge and
produce a parallel implementation of that program.
We present the techniques for discovering sources of parallelism in 
a program at compile time, and then show how this parallelism is
naturally mapped onto a parallel combinator set that we will define.

To discover sources of parallelism in a program, we use 
{\em abstract interpretation} a compile-time technique which is used
to gain information about a program which may then be used to optimise
the program's execution.
A particular use of abstract interpretation is in 
{\em strictness analysis}
of functional program.
In a language that has lazy semantics, the main potential for parallelism
arises in the evaluation of arguments of strict operators.

Having identified the sources of parallelism at compile time, it is 
necessary to communicate these to the run-time system.
In the second part of the paper we introduce an extended set of combinators,
including some parallel combinators, to achieve this purpose.
}

\reference{Simon L Peyton Jones}
{GRIP - a parallel processor for functional languages}
{Electronics and Power, pp633-636, Oct 1987;
also in ICL Technical Journal 5(3), May 1987}
{
A brief 4-page article about the GRIP architecture.
}

\reference{Simon L Peyton Jones, Chris Clack, Jon Salkild, and Mark Hardie}
{GRIP - a high-performance architecture for parallel graph reduction}
{Proc IFIP conference on Functional Programming Languages and 
Computer Architecture, Portland,
ed Kahn, Springer Verlag LNCS 274, pp98-112, Sept 1987}
{
GRIP is a high-performance parallel machine designed to execute
functional programs using supercombinator graph reduction.
It uses a high-bandwidth bus to provide access to a
large, distributed shared memory, using intelligent memory units and
packet-switching protocols to increase the number of processors
which the bus can support.
GRIP is also being programmed to support parallel Prolog and
DACTL.

We outline GRIP's architecture and firmware, discuss the major design
issues, and describe the current state of the project and
our plans for the future.
}

\reference{Simon L Peyton Jones and Chris Clack}
{Finding fixpoints in abstract interpretation} 
{in Abstract Interpretation of Declarative Languages,
ed Hankin \& Abramsky, Ellis Horwood, pp246-265, 1987.}
{
Abstract interpretation is normally used as the basis for
a static, compile-time analysis of a program.
For example, strictness analysis attempts to establish which
functions in the program are strict (we will use strictness
analysis as a running example).

Using abstract interpretation in this way requires the
compile-time evaluation of expressions in the abstract domain.
It is obviously desirable that this evaluation should
always terminate, since otherwise the compiler would risk
non-termination.
In the case of non-recursive functions there is no problem, and
termination is guaranteed.
Recursive functions, however, present more of a problem, and it
is the purpose of this paper to explain the problem and to
offer some practical solutions.
}

\reference{Chris Clack and Simon L Peyton Jones}
{The four-stroke reduction engine}
{Proc ACM Conference on Lisp and Functional Programming,
Boston, pp220-232, Aug 1986}
{
Functional languages are widely claimed to be amenable to concurrent
execution by multiple processors.  This paper presents an algorithm for
the parallel graph reduction of a functional program.
The algorithm supports transparent management of parallel 
tasks with no explicit
communication between processors.
}

\reference{Simon L Peyton Jones}
{Functional programming languages as a software engineering tool}
{in Software Engineering - the critical decade D Ince,
Peter Peregrinus, pp124-151, 1986}
{
It is the purpose of this paper to suggest that functional
languages are an appropriate tool for supporting the activity
of programming in the large, and to present a justification of
this claim.
}

\reference{Simon L Peyton Jones}
{Using Futurebus in a fifth generation computer architecture}
{Microprocessors and Microsystems 10(2), March 1986}
{
Despite the bandwidth limitations of a bus, we present a design
for a parallel computer (GRIP) based on Futurebus, which limits bus
bandwidth requirements by using intelligent memories.

Such a machine offers higher performance than a uniprocessor
and lower cost than a more extensible multiprocessor, as well
as serving as a vehicle for research in parallel architectures.
}


\section{Internal reports}

\reference{Kevin Hammond and John Glauert}
{Implementing Pattern-Matching Functional Languages using Dactl}
{University of Glasgow, 1989}
{
This paper describes the implementation of a family of  pattern-matching
functional  languages  in  the  parallel graph-rewriting language Dactl.
Attention  is   focussed   on   the   direct   implementation   of   the
pattern-matching   constructs   in  the  context  of  various  reduction
strategies: eager, lazy, and lazy with  strictness  analysis.   Two  new
reduction  strategies  combining  lazy  evaluation  with a technique for
compiling non-overlapping patterns are  also  illustrated.   The  latter
strategies   provide   improved  termination  properties  compared  with
conventional functional  language  implementations  for  non-overlapping
patterns.  The implementations described here cover all pattern-matching
constructs found in Standard  ML,  including  named  patterns  and  deep
patterns.   The  use  of  Dactl  renders  explicit  the  complexities of
pattern-matching which are obscured by implementation in a  conventional
intermediate language or abstract machine.
}

\reference{Simon L Peyton Jones}
{A practical technique for designing asynchronous finite-state machines}
{Proc Glasgow Workshop on Functional Programming, Fraserburgh,Aug 1989}
{
The literature on asynchronous logic design is mostly of a fairly theoretical
nature.   We present a practical technique for generating asynchronous finite-state
machines from a description of their states and transitions.  The technique
has been used successfully to design a number of state machines in
the GRIP mulitprocessor.
}

\reference{Kevin Hammond}
{A Proposal for an Implementation of Full Dactl on a Meiko Transputer Rack}
{SYS-C89-02, University of East Anglia, 1989}
{
The  design  of  an  abstract  machine  instruction  set  for  Dactl  is
described.   The  instruction set is sufficient to encapsulate all Dactl
constructs; it will also permit  parallel  execution  where  applicable.
The  paper  considers the difficulties involved in the implementation of
this abstract instruction set on the  UEA  Meiko  M40  transputer  rack,
using  a  ZAPP-style  kernel.  Part of the code for a simulation of this
instruction set is included as an appendix to the report.
}

\reference{Chris Clack}
{Tuning the four-stroke reduction engine}
{University College London, January 1989 ($\clubsuit$)}
{
This paper analyses the current implementation of the four-stroke reduction
engine (a virtual machine for parallel graph reduction).
The current implementation is shown to be inefficient, and a number of 
enhancements are suggested.
This paper proposes that major performance benefits will accrue from
increasing the intelligence of the memory units and giving them a more 
important role in the four-stroke cycle.
}

\reference{Chris Clack}
{Performance cost accounting for GRIP}
{University College London, January 1989 ($\clubsuit$)}
{
This paper presents a general model for efficiency anakysis of shared-memory
parallel graph reduction architectures.
The efficiency of the GRIP implementation of the four-stroke reduction engine
is subsequently analysed by approtioning costs to the various components
of the general model.

In particular, attention is focussed on the two aspects of execution 
profiling, and analysis of resource utilsation.
}

\reference{Chris Clack}
{Diagnosis and cure for dislocated spines}
{University College London, June 1988 ($\clubsuit$)}
{
Locality of reference is a key issue for parallel machines, and especially
for parallel implementations of graph reduction.
If locality can be achieved then communications costs fall,
and we are better able to exploit distributed architectures.
This paper analyses a particular implementation of graph reduction -- 
the four-stroke reduction engine -- and introduces the concept of 
spine-locality as a basis for graph building and task-scheduling strategies
that enhance locality.
}

\end{document}