ghc/docs/abstracts/abstracts91.tex

   1 \documentstyle[11pt,slpj,abstracts]{article}
   2
   3 \begin{document}
   4
   5 \title{Abstracts of GRIP/GRASP-related papers and reports, 1991
   6 }
   7
   8 \author{The GRASP team \\ Department of Computing Science \\
   9 University of Glasgow G12 8QQ
  10 }
  11
  12 \maketitle
  13
  14 \begin{abstract}
  15 We present a list of papers and reports related to the GRIP
  16 and GRASP projects,
  17 covering {\em the design, compilation technology,
  18 and parallel implementations of functional programming languages, especially
  19 \Haskell{}}.
  20
  21 Most of them can be obtained by FTP.  Connect to {\tt ftp.dcs.glasgow.ac.uk},
  22 and look in {\tt pub/glasgow-fp/papers}, {\tt pub/glasgow-fp/drafts}, {\tt pub/glasgow-fp/tech\_reports},
  23 or {\tt pub/glasgow-fp/grasp-and-aqua-docs}.
  24
  25 They can also be obtained by writing to
  26 Alexa Stewart, Department of Computing Science,
  27 University of Glasgow G12 8QQ, UK.   Her electronic mail address is
  28 alexa@dcs.glasgow.ac.uk.
  29 \end{abstract}
  30
  31 \section{Published papers}
  32
  33 \reference
  34 {Simon L Peyton Jones and David Lester}
  35 {A modular fully-lazy lambda lifter in \Haskell{}}
  36 {{\em Software Practice and Experience}, 21(5) (May 1991)}
  37 {An important step in many compilers for functional languages is
  38 {\em lambda lifting}.  In his thesis, Hughes showed that by doing lambda
  39 lifting in a particular way, a useful property called {\em full laziness}
  40 can be preserved;
  41 full laziness has been seen as intertwined with
  42 lambda lifting ever since.
  43
  44 We show that, on the contrary, full laziness can be regarded as a completely
  45 separate process to lambda lifting, thus making it easy to use different
  46 lambda lifters following a full-laziness transformation, or to use
  47 the full-laziness transformation in compilers which do not require lambda
  48 lifting.
  49
  50 On the way, we present the complete code for our modular fully-lazy
  51 lambda lifter, written in the \Haskell{} functional programming language.
  52 }
  53
  54 \reference{Simon L Peyton Jones and Mark Hardie}
  55 {A Futurebus interface from off-the-shelf parts}
  56 {IEEE Micro, Feb 1991}
  57 {
  58 As part of the GRIP project we have designed a Futurebus interface using
  59 off-the-shelf parts.
  60 We describe our implementation, which is unusual in its use of fully
  61 asynchronous finite-state machines.
  62 Based on this experience we draw some lessons for future designs.
  63 }
  64
  65 \reference{Simon L Peyton Jones and John Launchbury}
  66 {Unboxed values as first class citizens}
  67 {Functional Programming Languages and Computer Architecture (FPCA), Boston,
  68 ed Hughes, Springer LNCS 523, Sept 1991, pp636--666}
  69 {The code compiled from a non-strict functional program usually
  70 manipulates heap-allocated {\em boxed} numbers.
  71 Compilers for such languages often go to considerable trouble to
  72 optimise operations on boxed numbers into simpler operations
  73 on their unboxed forms.  These optimisations are usually handled
  74 in an {\em ad hoc} manner in
  75 the code generator, because earlier phases of the compiler have
  76 no way to talk about unboxed values.
  77
  78 We present a new approach, which makes unboxed values into (nearly) first-class
  79 citizens.  The language, including its type system, is extended to
  80 handle unboxed values.  The optimisation of boxing and unboxing operations
  81 can now be reinterpreted as a set of correctness-preserving program
  82 transformations.  Indeed the particular transformations
  83 required are ones which a compiler would want to implement anyway.
  84 The compiler becomes both simpler and more modular.
  85
  86 Two other benefits accrue.
  87 Firstly, the results of strictness analysis can be exploited within
  88 the same uniform transformational framework.
  89 Secondly, new algebraic data types with
  90 unboxed components can be declared.  Values of these types can be
  91 manipulated much more efficiently than the corresponding boxed versions.
  92
  93 Both a static and a dynamic semantics are given for the augmented language.
  94 The denotational dynamic semantics is notable for its use of
  95 {\em unpointed domains}.
  96 }
  97
  98 \reference{Philip Wadler}
  99 {Is there a use for linear logic?}
 100 {ACM/IFIP Symposium on Partial Evaluation
 101 and Semantics Based Program Manipulation (PEPM), Yale
 102 University, June 1991}
 103 {
 104 Past attempts to apply Girard's linear logic have either had a clear
 105 relation to the theory (Lafont, Holmstr\"om, Abramsky) or a clear
 106 practical value (Guzm\'an and Hudak, Wadler), but not both.  This paper
 107 defines a sequence of languages based on linear logic that span the gap
 108 between theory and practice.  Type reconstruction in a linear type
 109 system can derive information about sharing.  An approach to linear type
 110 reconstruction based on {\em use types\/} is presented.  Applications
 111 to the {\em array update\/} problem are considered.
 112 }
 113
 114 \reference{Simon L Peyton Jones}
 115 {The Spineless Tagless G-machine: a second attempt}
 116 {Proc Workshop on Parallel Implementations of Functional Languages,
 117 University of Southampton, ed Glaser \& Hartel, June 1991}
 118 {The Spineless Tagless G-machine is an abstract machine designed
 119 to support functional languages.  This presentation of the machine
 120 falls into two parts.  Firstly, we present the {\em STG language},
 121 an austere but recognisably-functional language, which as well as
 122 a {\em denotational} meaning has a well-defined {\em operational} semantics.
 123 The STG language is the ``abstract machine code'' for the Spineless
 124 Tagless G-machine, but it is sufficiently abstract that it can readily be
 125 compiled into G-machine Gcode or TIM code instead.
 126
 127 Secondly, we discuss the mapping of the STG language onto stock hardware.
 128 The success of an abstract machine model depends largely on how efficient
 129 this mapping can be made, though this topic is often relegated to a short
 130 section.  Instead, we give a detailed discussion of the design issues and
 131 the choices we have made.  Our principal target is the C language, treating
 132 the C compiler as a portable assembler.
 133
 134 A revised version is in preparation for the Journal of Functional Programming.
 135 }
 136
 137 \reference{Gert Akerholt, Kevin Hammond, Simon Peyton Jones and Phil Trinder}
 138 {A parallel functional database on GRIP}
 139 {\GlasgowNinetyOne{}, pp1-24}
 140 {
 141 GRIP is a shared-memory multiprocessor designed for efficient parallel
 142 evaluation of functional languages, using compiled graph reduction.
 143 In this paper, we consider the feasibility of implementing a database
 144 manager on GRIP, and present results obtained from a pilot
 145 implementation.  A database implemented in a pure functional language
 146 must be modified {\em non-destructively}, i.e.\ the original database
 147 must be preserved and a new copy constructed.  The naive
 148 implementation provides evidence for the feasibility of a pure
 149 functional database in the form of modest real-time speed-ups, and
 150 acceptable real-time performance.  This performance can be tentatively
 151 compared with results for existing machines running a more
 152 sophisticated database benchmark.
 153 The functional database is also used to investigate the GRIP
 154 architecture, compared with an idealised machine.  The particular
 155 features investigated are the thread-creation costs and caching of
 156 GRIP's distributed memory.
 157 }
 158
 159 \reference{PM Sansom}
 160 {Combining single-space and two-space compacting garbage collectors}
 161 {\GlasgowNinetyOne{}, pp312-324}
 162 {The garbage collector presented in this paper makes use of
 163 two well known compaction garbage collection algorithms with very
 164 different performance characteristics: Cheney's two-space copying
 165 collector and Jon\-ker's single-space sliding compaction collector. We
 166 propose a scheme which allows either collector to be used. The
 167 run-time memory requirements of the program being executed are used to
 168 determine the most appropriate collector. This enables us to achieve a
 169 fast collector for heap requirements less than half of the heap memory
 170 but allows the heap utilization to increase beyond this threshold.
 171 Using these ideas we develop a particularly attractive extension to
 172 Appel's generational collector.
 173 }
 174
 175 \reference{PM Sansom}
 176 {Dual-mode garbage collection}
 177 {Proc Workshop on the Parallel Implementation of Functional Languages, Southampton,
 178 ed Glaser \& Hartel, pp283-310}
 179 {
 180 The garbage collector presented in this paper makes use of two well
 181 known compaction garbage collection algorithms with very different
 182 performance characteristics: Cheney's two-space copying collector and
 183 Jonker's sliding compaction collector. We propose a scheme which
 184 allows either collector to be used. The run-time memory requirements
 185 of the program being executed are used to determine the most
 186 appropriate collector. This enables us to achieve a fast collector for
 187 heap requirements less than half of the heap memory but allows the
 188 heap utilization to increase beyond this threshold. Using these ideas
 189 we develop a particularly attractive extension to Appel's generational
 190 collector.
 191
 192 We also describe a particularly fast implementation of the garbage
 193 collector which avoids interpreting the structure and current state of
 194 closures by attaching specific code to heap objects. This code {\em
 195 knows} the structure and current state of the object and performs the
 196 appropriate actions without having to test any flag or arity fields.
 197 The result is an implementation of these collection schemes which does
 198 not require any additional storage to be associated with the heap
 199 objects.
 200
 201 This paper is an earlier, and fuller, version of ``Combining
 202 single-space and two-space compacting garbage collectors'' above.
 203 }
 204
 205 \reference{K Hammond}
 206 {Efficient type inference using monads}
 207 {\GlasgowNinetyOne{}, pp146-157}
 208 {{\em Efficient} type inference algorithms are based on
 209 graph-rewriting techniques.  Consequently, at first sight they seem
 210 unsuitable for functional language implementation.  In fact, most
 211 compilers written in functional languages use substitution-based
 212 algorithms, at a considerable cost in performance.  In this paper, we
 213 show how monads may be used to transform a substutition-based inference
 214 algorithm into one using a graph representation.  The resulting
 215 algorithm is faster than the corresponding substitution-based one.}
 216
 217
 218 \section{Technical reports}
 219
 220 \reference{The Grasp team}
 221 {The Glasgow Haskell I/O system}
 222 {Dept of Computing Science, University of Glasgow, Nov 1991}
 223 {
 224 Most input/output systems for non-strict functional languages
 225 feature a rather large ``operating system
 226 The Glasgow Haskell system implements input and output
 227 very largely within Haskell itself, without the conventional
 228 enclosing ``printing mechanism''.  This paper explains how the
 229 IO system works in some detail.
 230 }
 231
 232 \end{document}