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