Glasgow FP Abstracts

This document contains details of all the papers in the Glasgow FTP directory from March 1993 onwards.

Author: Patrick Sansom and Simon L Peyton Jones
Title: "Time and Space Profiling for Non-Strict Higher-Order Functional Languages"
Pubn: Submitted to POPL '95
Date: August 1994
File: profiling.ps.Z

Abstract

We present the first profiler for a compiled, non-strict, higher-order, purely functional language capable of measuring {\em time} as well as {\em space} usage. Our profiler is implemented in a production-quality optimising compiler for Haskell, has low overheads, and can successfully profile large applications.

A unique feature of our approach is that we give a formal specification of the attribution of execution costs to cost centres. This specification enables us to discuss our design decisions in a precise framework. Since it is not obvious how to map this specification onto a particular implementation, we also present an implementation-oriented operational semantics, and prove it equivalent to the specification.

Author: Kevin Hammond
Title: "Parallel Functional Programming: an Introduction"
Pubn: PASCO '94 (Invited Paper)
Date: September 1994
File: parallel-introduction.ps.Z

Abstract

This paper introduces the general area of parallel functional programming, surveying the current state of research and suggesting areas which could profitably be explored in the future. No new results are presented. The paper contains 97 references selected from the 500 or so publications in this field.

Author: Kevin Hammond, Jim Mattson and Simon L Peyton Jones
Title: "Automatic Spark Strategies and Granularity for a Parallel Functional Language Reducer"
Pubn: CONPAR '94
Date: September 1994
File: spark-strategies-and-granularity.ps.Z

Abstract

This paper considers the issue of dynamic task control in the context of a parallel Haskell implementation on the GRIP multiprocessor. For the first time, we report the effect of our task control strategies on task granularity, as measured in terms of dynamic heap allocations. This gives a concrete means of measuring the effectiveness of these strategies other than wall-clock timings, which are notoriously uninformative.

Author: Cordelia V Hall, Kevin Hammond, Simon L Peyton Jones and Philip L Wadler
Title: "Type Classes in Haskell"
Pubn: ESOP '94
Date: January 1994
File: type-classes-in-haskell.ps.Z

Abstract

This paper defines a set of type inference rules for resolving overloading introduced by type classes. Programs including type classes are transformed into ones which may be typed by the Hindley-Milner inference rules. In contrast to other work on type classes, the rules presented here relate directly to user programs. An innovative aspect of this work is the use of second-order lambda calculus to record type information in the program.

Author: Simon L Peyton Jones, John Hughes and John Launchbury
Title: "How to Give a Good Research Talk"
Pubn: ACM SIGPLAN Notices, 28:11
Date: November 1993
File: giving-a-talk.ps.Z

Abstract

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.

Author: John Launchbury
Title: "Lazy Imperative Programming"
Pubn: ACM SigPlan Workshop on State in Prog. Langs., Copenhagen
Date: June 1993
File: lazy-imperative-programming.ps.Z

Abstract

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.

Author: Cordelia V. Hall
Title: "Using Overloading to Express Distinctions Between Evaluators"
Pubn: Information Processing Letters
Date: July 1993
File: overloading-evaluators.ps.Z

Abstract

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.

Author: Gert Akerholt, Kevin Hammond, Simon L. Peyton Jones and Phil Trinder
Title: "Processing Transactions on GRIP"
Pubn: PARLE '93, Munich, June 1993
Date: June 1993
File: grip-transactions.ps.Z

Abstract

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.

Author: Andy Gill, John Launchbury and Simon L. Peyton Jones
Title: "A Short Cut to Deforestation"
Pubn: Functional Programming Languages and Computer Architecture, Copenhagen, June 1993
Date: April 1993
File: deforestation-short-cut.ps.Z

Abstract

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.

Author: Patrick M. Sansom and Simon L. Peyton Jones
Title: "Generation garbage collection for Haskell"
Pubn: Functional Programming Languages and Computer Architecture, Copenhagen, June 1993
Date: March 1993
File: gen-gc-for-haskell.ps.Z

Abstract

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.

Author: Simon L Peyton Jones
Title: "Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine"
Date: July 1992
Pubn: Journal of Functional Programming 2(2), July 1992, pp. 127-202
File: spineless-tagless-gmachine.ps.Z

Abstract

The Spineless Tagless G-machine is an abstract machine designed to support non-strict higher-order functional languages. This presentation of the machine falls into three parts. Firstly, we give a general discussion of the design issues involved in implementing non-strict functional languages.

Next, we present the STG language, an austere but recognisably-functional language, which as well as a denotational meaning has a well-defined operational semantics. The STG language is the ``abstract machine code'' for the Spineless Tagless G-machine.

Lastly, we discuss the mapping of the STG language onto stock hardware. The success of an abstract machine model depends largely on how efficient this mapping can be made, though this topic is often relegated to a short section. Instead, we give a detailed discussion of the design issues and the choices we have made. Our principal target is the C language, treating the C compiler as a portable assembler.

Author: Simon L Peyton Jones, Cordy Hall, Kevin Hammond, Will Partain and Philip Wadler
Title: "The Glasgow Haskell compiler: a technical overview"
Pubn: Proc. UK Joint Framework for Information Technology (JFIT) Technical Conference, Keele, 1993.
Date: March 1993
File: grasp-jfit.ps.Z

Abstract

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.

Author: Simon L Peyton Jones and John Launchbury
Title: "Unboxed values as first class citizens in a non-strict functional language"
Pubn: Proc. 1991 Conf. on Functional Programming Languages and Computer Architecture, Cambridge Mass., Sept 1991.
Date: September 1991
File: unboxed-values.ps.Z

Abstract

The code compiled from a non-strict functional program usually manipulates heap-allocated boxed numbers. Compilers for such languages often go to considerable trouble to optimise operations on boxed numbers into simpler operations on their unboxed forms. These optimisations are usually handled in an ad hoc manner in the code generator, because earlier phases of the compiler have no way to talk about unboxed values.

We present a new approach, which makes unboxed values into (nearly) first-class citizens. The language, including its type system, is extended to handle unboxed values. The optimisation of boxing and unboxing operations can now be reinterpreted as a set of correctness-preserving program transformations. Indeed the particular transformations required are ones which a compiler would want to implement anyway. The compiler becomes both simpler and more modular.

Two other benefits accrue. Firstly, the results of strictness analysis can be exploited within the same uniform transformational framework. Secondly, new algebraic data types with unboxed components can be declared. Values of these types can be manipulated much more efficiently than the corresponding boxed versions.

Both a static and a dynamic semantics are given for the augmented language. The denotational dynamic semantics is notable for its use of unpointed domains.

Author: Kei Davis
Title: "Higher-order Binding-time Analysis"
Pubn: ACM PEPM '93
Date: 1993
File: ho-binding-time-analysis.ps.Z

Author: Simon Peyton Jones and Philip Wadler
Title: "Imperative Functional Programming"
Pubn: ACM POPL, Charleston, South Carolina
Date: January 1993
File: imperative.ps.Z

Abstract

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.