+++ /dev/null
-\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}
projects / ghc-hetmet.git / blobdiff