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

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

\documentstyle[11pt,slpj,abstracts]{article}

\begin{document}

% ======================================================

\title{Abstracts of GRIP/GRASP/AQUA-related papers and reports, 1993
}

\author{The AQUA team \\ Department of Computing Science \\
University of Glasgow G12 8QQ
}

\maketitle

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

Most of them can be obtained by FTP.  Connect to {\tt ftp.dcs.glasgow.ac.uk},
and look in {\tt pub/glasgow-fp/papers}, {\tt pub/glasgow-fp/drafts}, {\tt pub/glasgow-fp/tech\_reports},
or {\tt pub/glasgow-fp/grasp-and-aqua-docs}.

They can also be obtained by writing to 
Alexa Stewart, Department of Computing Science,
University of Glasgow G12 8QQ, UK.   Her electronic mail address is
alexa@dcs.glasgow.ac.uk.
\end{abstract}

\section{Published papers}

\reference{CV Hall}
{Using overloading to express distinctions}
{Information Processing Letters (to appear)}
{
Evaluators, also called ``interpreters'', play a variety of roles
in the study of programming languages.  Given this, it's surprising
that we don't have a better framework for developing evaluators and
specifying their relationship to each other. This paper
shows that type classes in Haskell provide an excellent 
framework for exploring relationships between evaluators, using
abstract interpretation as a motivating example.
}

\reference{A Gill, J Launchbury and SL Peyton Jones}
{A short cut to deforestation}
{ACM Conference on Functional Programming and Computer Architecture, Copenhagen, pp223-232}
{Lists are often used as ``glue'' to connect
separate parts of a program together.
We propose an automatic technique for 
improving the efficiency of such programs,
by removing many of these intermediate lists,
based on a single, simple, local transformation.
We have implemented the method in the Glasgow Haskell compiler.
}

\reference{P Sansom and SL Peyton Jones}
{Generational garbage collection for Haskell}
{ACM Conference on Functional Programming and Computer Architecture, Copenhagen, pp106-116}
{This paper examines the use of generational garbage collection
techniques for a lazy implementation of a non-strict functional
language. Detailed measurements which demonstrate that a generational
garbage collector can substantially out-perform non-generational
collectors, despite the frequency of write operations in the
underlying implementation, are presented.

Our measurements are taken from a state-of-the-art compiled
implementation for Haskell, running substantial benchmark programs.
We make measurements of dynamic properties (such as object lifetimes)
which affect generational collectors, study their interaction with a
simple generational scheme, make direct performance comparisons with
simpler collectors, and quantify the interaction with a paging system.

The generational collector is demonstrably superior.  At least for our
benchmarks, it reduces the net storage management overhead, and it
allows larger programs to be run on a given machine before thrashing
ensues.}

\reference{J Launchbury}
{Lazy imperative programming}
{Proc ACM Sigplan Workshop on State in Programming Languages, Copenhagen, June 1993 (available as
YALEU/DCS/RR-968, Yale University), pp46-56}
{
In this paper we argue for the importance of lazy state, that is,
sequences of imperative (destructive) actions in which the actions are
delayed until their results are required. This enables state-based
computations to take advantage of the control power of lazy evaluation.
We provide some examples of its use, and describe an implementation
within Glasgow Haskell.
}

\reference{G Akerholt, K Hammond, P Trinder and SL Peyton Jones}
{Processing transactions on GRIP, a parallel graph reducer}
{Proc Parallel Architectures and Languages Europe (PARLE), Munich, June 1993, pp634-647}
{
The GRIP architecture allows efficient execution of functional
programs on a multi-processor built from standard hardware components.
State-of-the-art compilation techniques are combined with
sophisticated runtime resource-control to give good parallel
performance.  This paper reports the results of running GRIP on an
application which is apparently unsuited to the basic functional
model: a database transaction manager incorporating updates as well as
lookup transactions.  The results obtained show good relative speedups
for GRIP, with real performance advantages over the same application
executing on sequential machines.
}

\reference{SL Peyton Jones and  PL Wadler}
{Imperative functional programming}
{ACM conference on Principles of Programming Languages, Charleston, Jan 1993}
{We present a new model, based on monads, for performing input/output
in a non-strict, purely functional language.  It
is composable, extensible, efficient, requires no extensions
to the type system, and extends smoothly to incorporate mixed-language
working and in-place array updates.
}

\reference{J Launchbury}
{An operational semantics for lazy evaluation}
{ACM conference on Principles of Programming Languages, Charleston, Jan 1993}
{We define an operational semantics for lazy evaluation which provides
an accurate model for sharing. The only computational structure
we introduce is a set of bindings which corresponds closely to a
heap. The semantics is set at a considerably higher level of abstraction
than operational semantics for particular abstract machines, so is
more suitable for a variety of proofs. Furthermore, because a heap
is explicitly modelled, the semantics provides a suitable framework
for studies about space behaviour of terms under lazy evaluation.
}

\reference{SL Peyton Jones, CV Hall, K Hammond, WD Partain, and PL Wadler}
{The Glasgow Haskell compiler: a technical overview}
{JFIT Technical Conference, Keele, March 1993}
{We give an overview of the Glasgow Haskell compiler,
focusing especially on way in which we have been able
to exploit the rich theory of functional languages to give
very practical improvements in the compiler.

The compiler is portable, modular, generates good code, and is 
freely available.
}

\reference{PL Wadler}
{A syntax for linear logic}
{Mathematical Foundations of 
Programming Language Semantics, New Orleans, April 1993}
{There is a standard syntax for Girard's linear logic, due
to Abramsky, and a standard semantics, due to Seely.  Alas, the
former is incoherent with the latter: different derivations of
the same syntax may be assigned different semantics.  This paper
reviews the standard syntax and semantics, and discusses the problem
that arises and a standard approach to its solution.  A new solution
is proposed, based on ideas taken from Girard's Logic of Unity.
The new syntax is based on pattern matching, allowing for concise
expression of programs.}

\reference{SL Peyton Jones, J Hughes, J Launchbury}
{How to give a good research talk}
{SIGPLAN Notices 28(11), Nov 1993, 9-12}
{
Giving a good research talk is not easy. We try to identify some things
which we have found helpful, in the hope that they may be useful to you. 
}


\section{Workshop papers and technical reports}

The 1993 Glasgow Functional Programming Workshop papers exist in
the draft proceedings at the moment.  They are being refereed, and will
be published by Springer Verlag in due course.

\reference{DJ King and J Launchbury}
{Lazy Depth-First Search and Linear Graph Algorithms in Haskell}
{\GlasgowNinetyThree{}}
{
Depth-first search is the key to a wide variety of graph algorithms.
In this paper we explore the implementation of depth first search in a
lazy functional language. For the first time in such languages we
obtain a linear-time implementation.  But we go further.  Unlike
traditional imperative presentations, algorithms are constructed from
individual components, which may be reused to create new
algorithms. Furthermore, the style of program is quite amenable to
formal proof, which we exemplify through a calculational-style proof
of a strongly-connected components algorithm.

{\em This paper has been submitted to Lisp \& Functional Programming 1994.}
}

\reference{K Hammond, GL Burn and DB Howe}
{Spiking your caches}
{\GlasgowNinetyThree{}}
{
Despite recent advances, predicting the performance of functional
programs on real machines remains something of a black art.  This
paper reports on one particularly unexpected set of results where
small variations in the size of a dynamic heap occasionally gave rise
to 50\% differences in CPU performance.  These performance {\em
spikes} can be traced to the cache architecture of the machine being
benchmarked, the widely-used Sun Sparcstation~1.  A major contribution
of our work is the provision of a tool which allows cache conflicts
to be located by the type of access (heap, stack etc.).  This can
be used to improve the functional language implementation, or to
study the memory access patterns of a particular program.
}

\reference{S Marlow}
{Update avoidance analysis}
{\GlasgowNinetyThree{}}
{
A requirement  of lazy    evaluation  is that     the value  of    any
subexpression in the program is calculated no more than once.  This is
achieved by updating an expression with its value, once computed.  The
problem is that  updating is a  costly operation,  and experimentation
has shown that it is only necessary  in about 30\%  of cases (that is,
70\% of expressions represent values that  are only ever required once
during execution).  The aim of the analysis presented in this paper is
to discover  expressions  that do not  need  to be  updated,  and thus
reduce  the  execution time  of  the program.   The  analysis has been
implemented in the Glasgow Haskell Compiler, and results are given.

FTP: @pub/glasgow-fp/authors/Simon_Marlow/update-avoidance.ps.gz@
}

\reference{SL Peyton Jones and WD Partain}
{Measuring the effectiveness of a simple strictness analyser}
{\GlasgowNinetyThree{}}
{
A lot has been written about strictness analysis for non-strict
functional programs, usually in the hope that the results of the
analysis can be used to reduce runtime.  On the other hand, few papers
present measurements of how well it works in practice.  Usually, all
that is presented are the run-times of a variety of (usually small)
programs, with and without strictness analysis enabled.  The goal of
this paper is to provide detailed quantitative insight about the
effectiveness of a simple strictness analyser, in the context of a
state-of-the art compiler running serious application programs.
}

\reference{J Mattson}
{Local speculative evaluation for distributed graph reduction}
{\GlasgowNinetyThree{}}
{
Speculative evaluation attempts to increase parallelism by
performing potentially useful computations before they are known to be
necessary.  Speculative computations may be coded explicitly in a
program, or they may be scheduled implicitly by the reduction system
as idle processors become available.  A general approach to both kinds
of speculation incurs a great deal of overhead which may outweigh the
benefits of speculative evaluation for fine-grain speculative tasks.  

Suppose that implicit speculative computations are restricted to
execution on the local processor, with the hope of performing
potentially useful work while the local mandatory tasks are all
blocked.  This restriction greatly simplifies the problems of
speculative task management, and it opens the door for fine-grain
speculative tasks.  More complex mechanisms for distributing
and managing coarse-grain speculative tasks can later be added on top of
the basic foundation provided for local speculative evaluation.
}

\reference{PM Sansom}
{Time profiling a lazy functional compiler}
{\GlasgowNinetyThree{}}
{
Recent years has seen the development of profiling tools for lazy
functional language implementations. This paper presents the results
of using a time profiler to profile the Glasgow Haskell compiler.
}

\reference{D King and J Launchbury}
{Functional graph algorithms with depth-first search}
{\GlasgowNinetyThree{}}
{Performing a depth-first search of a graph is one of the fundamental
approaches for solving a variety of graph algorithms.  Implementing
depth-first search efficiently in a pure functional language has only
become possible with the advent of imperative functional programming.
In this paper we mix the techniques of pure functional programming in
the same cauldron as depth-first search, to yield a more lucid
approach to viewing a variety of graph algorithms. This claim will be
illustrated with several examples.}

\reference{A Santos and SL Peyton Jones}
{Tuning a compiler's allocation policy}
{\GlasgowNinetyThree{}}
{There are many different costs involved in the allocation of
closures during the execution of functional programs.  Even more so
for closures that are not in normal form, as they have to be
allocated and then possibley entered and updated.  We compare several
different policies for closure allocation, trying to minimise these
costs.  The issues of laziness and full laziness are discussed.
}

\reference{CV Hall}
{A framework for optimising abstract data types}
{\GlasgowNinetyThree{}}
{Two trends have been developing in functional programming language
research. First, compilers are supporting optimisations of data
types, such as unboxed types and parallel bags.  Second, functional
programmers are increasingly writing code in a style that treats
data types as if they were abstract. Abstract data types offer
opportunities for optimisation because the representation of the
type can be optimised without affecting the program, allowing the
programmer to use operations on it and improve performance. At the
same time, the original type is often required by some part of the
program, and the programmer is left to figure out which to use
where.

This paper presents a general framework in which good functional
style automatically supports the efficient implementation of data
types.  It has been implemented in the Glasgow Haskell compiler
specifically to introduce an optimised list representation, and
this has been shown to cut execution time in half on a Sun
SPARCstation-1 for a substantial program.  Recent tests show that
it improves performance by more than a factor of 4 on the GRIP
parallel processor for short tests, however more experiments will
be necessary before we can assert that this speedup holds in
general.
}
\end{document}