Phil Trinder (Ed)


Functional Programming, Glasgow 1996


Proceedings of the 1996 Glasgow

Workshop on Functional Programming,

Ullapool, Scotland, 8th-10th July, 1996


Contents

The contents of these proceedings are available in two formats:
1. a gzipped Postscript file
2. a PDF file, readable with the Adobe Acrobat Reader available free from Adobe.

List of Participants

A Model for Representing Ruby Circuits [ Abstract, Postscript , PDF ]
C.J. Block

Are Ours Really Smaller than Theirs? [ Abstract, Postscript , PDF ]
S.P. Booth and S.B. Jones

Functional Hypersheets [ Abstract, Postscript , PDF ]
A. Davie and K. Hammond

Towards a System for Directional Types for Ruby [ Abstract, Postscript , PDF ]
A.B. Ferguson

An Introduction to Program Specialisation by Type Inference [ Abstract, Postscript , PDF ]
R.J.M. Hughes

A Sized Time System for a Parallel Functional Language [ Abstract, Postscript , PDF ]
H-W. Loidl and K. Hammond

An Exploration of Modular Programs [ Abstract, Postscript , PDF ]
J. Nicklisch and S.L. Peyton Jones

Bulk types with class [ Abstract, Postscript , PDF ]
S.L. Peyton Jones

Modules, Interfaces and Recompilation in Glasgow Haskell [ Abstract, Postscript , PDF ]
P.M. Sansom

A Monad of Imperative Streams [ Abstract, Postscript , PDF ]
E. Scholz

Puzzling Permutations [ Abstract, Postscript , PDF ]
M. Sheeran

A Case Study of Data-intensive Programs in Parallel Haskell [ Abstract, Postscript , PDF ]
P.W. Trinder, K. Hammond, H-W. Loidl, S.L. Peyton Jones and J. Wu


List of Participants

C.J. Block, Chalmers University of Technology, Sweden.
S.P. Booth, University of Stirling, Scotland.
A. Davie, St Andrews University, Scotland.
D. Dussart, K.U. Leven, Belgium.
A.B. Ferguson, University College Cork, Ireland.
C.V. Hall, University of Glasgow, Scotland.
K. Hammond, St Andrews University, Scotland.
R.J.M. Hughes, Chalmers University of Technology, Sweden.
S.B. Jones, University of Stirling, Scotland.
S. Kahrs, University of Edinburgh, Scotland.
H-W. Loidl, University of Glasgow, Scotland.
J. Nicklisch, University of Glasgow, Scotland
R. Noble, Canon, England.
J.T. O'Donnell, University of Glasgow, Scotland.
J. Ovlinger, University of Glasgow, Scotland.
S.L. Peyton Jones, University of Glasgow, Scotland.
A. Reid, Yale University, U.S.A.
M. Robinson, University of Stirling, Scotland.
P.M. Sansom, University of Glasgow, Scotland.
M. Schmidt-Schauss, Johann Wolfgang Goethe-Universitat, Germany.
E. Scholz, Freie Universitat Berlin, Germany.
M. Sheeran, Chalmers University of Technology, Sweden.
P. Thiemann, Universitat Tubingen, Germany.
P.W. Trinder, University of Glasgow, Scotland.
R. Virding, Ericsson, Sweden.
P.Wadler, Bell Laboratories, U.S.A.
J. Wu, University College London, England.


A Model for Representing Ruby Circuits
C.J. Block

This paper presents a method for drawing Ruby circuit descriptions. The method contains a sophisticated algorithm that calculates the placing of circuits and the connections between them, and sometimes transforms circuits from one shape to another. For some instances of Ruby circuits, ambiguities in the visualisation appear and this can make it very tricky to know how a circuit is supposed to be drawn. The algorithm makes a good choice when to transform and when not. The pictures are constructed in a compositional way, which reduces re-calculation and simplifies the building of a system that implements the algorithm. This approach gives layouts that are easy to read and the system can support different layout policies. The model is used in a project to develop a software system that draws Ruby circuit descriptions and is a part of the Glasgow Ruby Compiler.

Full Paper: [ Postscript , PDF ]


Are Ours Really Smaller than Theirs?
S.P. Booth and S.B. Jones

The claim is often made that functional programs are "more'' expressive than their imperative counterparts. This paper examines this claim using a particular measure of (i) program length and (ii) programming language "level'' (a measure of expressive power) both from the work of Halstead on software metrics.

Full Paper: [ Postscript , PDF ]


Functional Hypersheets
A. Davie and K. Hammond

This paper introduces hypersheets, an extension of conventional programming language modules. Whereas modules are static, and usually textually based, hypersheets constitute a local or distributed network of hyperlinks: dynamically evolving links to either values or definitions. Hypersheets integrate notions of persistence, hyperprogramming and user interface design.

In the purely functional context we consider here, hypersheets provide a software development environment for functional programming that supports version control, sophisticated scoping, evolution of values, and distributed program development.

This paper reports on very early work. We are therefore unable at present to report on either implementation results or user experience.

A full version of this paper has been submitted to the 1996 International Workshop on Implementing Functional Languages, Bonn, September 1996.

Full Paper: [ Postscript , PDF ]


Towards a System for Directional Types for Ruby
A.B. Ferguson

A modified type system for the Ruby VLSI design language is described, which adds directional information to the types of Ruby relations. Reasons for wishing to do so are discussed, and a realisation of the refined typing scheme is outlined. In order to deal with one otherwise troublesome case, constraints are added to the type system to maintain principal types in the presence of direction information.

Full Paper: [ Postscript , PDF ]


An Introduction to Program Specialisation by Type Inference
R.J.M. Hughes

In this paper we present a new paradigm for partial evaluation, based not on transforming terms into terms, but on transforming terms and types into terms and types. An immediate advantage is that residual programs need not involve the same types as source programs, so {\em type specialisation} can be accomplished naturally. Furthermore, while a conventional partial evaluator handles a static expression by reducing it to a constant residual {\em term}, we carry the static information in the residual {\em type}, which leads to improved static information flow and thereby better specialisations. Thanks to this, {\em optimal specialisation} of a typed interpreter is possible. Our partial evaluator is specified in a very modular fashion: each feature is associated with a type in the source language, and its specialisation is specified via corresponding introduction and elimination rules. As a result, specialisation features can be freely combined: for example, we have for the first time combined constructor specialisation with higher-order functions, deriving a firstification transformation and a closure analyses as a consequence.

This paper is an introduction to the material which appeared in the Proceedings of the Dagstuhl Workshop on Partial Evaluation, 1996 (Springer LNCS).

Full Paper: [ Postscript , PDF ]


A Sized Time System for a Parallel Functional Language
H-W. Loidl and K. Hammond

This paper describes an inference system, whose purpose is to determine the cost of evaluating expressions in a strict purely functional language. Upper bounds can be derived for both computation cost and the size of data structures. We outline a static analysis based on this inference system for inferring size and cost information. The analysis is a synthesis of the sized types of Hughes et al., and the polymorphic time system of Dornic et al., which was extended to static dependent costs by Reistad and Gifford.

Our main interest in cost information is for scheduling tasks in the parallel execution of functional languages. Using the GranSim parallel simulator, we show that the information provided by our analysis is sufficient to characterise relative task granularities for a simple functional program. This information can be used in the runtime-system of the Glasgow Parallel Haskell compiler to improve dynamic program performance.

Full Paper: [ Postscript , PDF ]


An Exploration of Modular Programs
J. Nicklisch and S.L. Peyton Jones

Recently, Mark Jones introduced first class structures as a means to express modular structure. In this paper we elaborate on this idea by comparing the module systems of Standard ML and Haskell 1.3, two widely used functional languages, and a Haskell variant equipped with such first class structures. Moreover, we look at another obvious and well-known extension to Hindley-Milner type systems, namely higher order type variables, to explore its usefulness in solving problems occuring when one attempts to structure larger programs into maintainable pieces.

We argue that there are surprisingly few applications where the module system currently provided by Haskell cannot keep pace with Standard ML's expressiveness. When one adds first class structures to Haskell, the module system reaches the expressiveness of Standard ML and even exceeds it.

Full Paper: [ Postscript , PDF ]


Bulk types with class
S.L. Peyton Jones

Bulk types - such as lists, bags, sets, finite maps, and priority queues - are ubiquitous in programming. Yet many languages don't support them well, even though they have received a great deal of attention, especially from the database community. Haskell is currently among the culprits.

This paper has two aims: to identify some of the technical difficulties, and to attempt to address them using Haskell's constructor classes.

The paper can also be read as a concrete proposal for new Haskell bulk type libraries.

Full Paper: [ Postscript , PDF ]


Modules, Interfaces and Recompilation in Glasgow Haskell
P. Sansom

This paper describes the system of interface files and recompilation checking in the Glasgow Haskell 1.3 Compiler. In developing this system our aim is to provide a separate compilation system which avoids unnecessary recompilation while performing significant inter-module optimisations. We associate a version number (based on the current timestamp) with each declaration and record the versions of all the imported declarations used when a module is compiled. When the module is recompiled the usage numbers are compared with the current version numbers to determine if the recompilation is unnecessary.

The paper also describes a proposed system of source interfaces designed to deal with the problem of cyclic module dependencies. This avoids the error-prone duplication of declarations by extracting the interface directly from the source code.

Full Paper: [ Postscript , PDF ]


A Monad of Imperative Streams
E. Scholz

A new approach is presented for performing I/O in a functional programming language in the presence of multiple input devices. A new monad St is introduced which generalizes Haskell's IO monad: A value of type St a represents an imperative program which, at certain times during its execution, will produce a value of type a. In contrast, a value of type IO a represents an imperative program which, at the end of its execution , will produce a value of type a. Not only may values of type St a be used to represent imperative commands, additionally, they serve to create so-called imperative streams. The computer's physical input devices are represented as primitive streams. Composite streams may be constructed and interleaved in a non-preemptive way using, for instance, the monad's bind operation. By way of a series of example programs, the usage of imperative streams is illustrated. Moreover, an implementation in terms of the IO monad is given that is suitable for executing the example programs on the Gofer interpreter. An extension of the graphical user interface system PIDGETS with imperative streams is planned.

Full Paper: [ Postscript , PDF ]


Puzzling Permutations
M. Sheeran

We show how to describe and analyse multistage interconnection networks in a relational framework. We give simple elegant descriptions of butterfly networks, using only two functions for building networks from smaller networks. By studying the algebra of these functions, we can give a clear account of the properties of networks, without resorting to the standard methods of reasoning in terms of binary representations of the addresses of data elements. The paper is intended as a tutorial introduction to multistage interconnection networks.

Full Paper: [ Postscript , PDF ]


A Case Study of Data-intensive Programs in Parallel Haskell
P.W. Trinder, K. Hammond, H-W. Loidl,
S.L. Peyton Jones and J. Wu

Accidents happen:
``An invisible car came out of nowhere, struck my vehicle and vanished.''
``I pulled away from the side of the road, glanced at my mother-in-law, and headed for the embankment.''
``As I approached the intersection a sign suddenly appeared in a place
where no stop sign had ever appeared before.''
Luckily, we don't normally have to deal with problems as bizarre as these. One interesting application that does arise at the Centre for Transport Studies consists of matching police reports of several accidents so as to locate accident blackspots. The application provides an interesting, data-intensive, test-bed for the persistent functional language PFL. We report here on an approach aimed at improving the performance of this application using Glasgow Parallel Haskell.

The accident application is one of several large parallel Haskell programs under development at Glasgow. Our objective is to achieve wall-clock speedups over the best sequential implementations, and we report modest wall-clock speedups for a demonstration program. From experience with these and other programs the group is developing a methodology for parallelising large functional programs. We have also developed strategies, a mechanism to separately specify a function's algorithm and its dynamic behaviour.

A shorter version of this paper has been submitted to the 8th Int. Workshop on Implementing Functional Languages (IFL'96).

Full Paper: [ Postscript , PDF ]