ghc/docs/abstracts/abstracts90.tex

   1 \documentstyle[11pt,slpj,abstracts]{article}
   2
   3 \begin{document}
   4
   5 \title{Abstracts of GRIP/GRASP-related papers and reports, 1990
   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 {Philip Wadler}
  35 {Comprehending monads}
  36 {{\em ACM Conference on Lisp and Functional Programming},
  37 Nice, France, pp.\ 61--78, June 1990.}
  38 {
  39 Category theorists invented {\em monads\/} in the 1960's
  40 to concisely express certain aspects of universal algebra.
  41 Functional programmers invented {\em list comprehensions\/}
  42 in the 1970's to concisely express certain programs involving lists.
  43 This paper shows how list comprehensions may be generalised
  44 to an arbitrary monad, and how the resulting programming feature
  45 can concisely express in a pure functional language some
  46 programs that manipulate state,
  47 handle exceptions, parse text, or invoke continuations.
  48 A new solution to the old problem
  49 of destructive array update is also presented.
  50 No knowledge of category theory is assumed.
  51 }
  52
  53 \reference
  54 {Philip Wadler}
  55 {Linear types can change the world!}
  56 {{\em IFIP TC 2 Working Conference on Programming
  57 Concepts and Methods}, Sea of Galilee, Israel, April 1990.}
  58 {
  59 The linear logic of J.-Y.~Girard suggests a new type
  60 system for functional languages, one which supports operations
  61 that ``change the world''.
  62 Values belonging to a linear type must be used exactly once:
  63 like the world, they cannot be duplicated or destroyed.
  64 Such values require no reference counting or garbage collection,
  65 and safely admit destructive array update.
  66 Linear types extend Schmidt's notion of single threading;
  67 provide an alternative to Hudak and Bloss' update analysis;
  68 and offer a practical complement to Lafont and Holmstr\"om's elegant
  69 linear languages.
  70 }
  71
  72 \reference{K Hammond and SL Peyton Jones}
  73 {Some early experiments on the GRIP parallel reducer}
  74 {Proc Nijmegen Workshop on Parallel Implementations of Functional Languages, TR 90-16, Dept
  75 of Informatics, University of Nijmegen, ed Plasmeijer, 1990, pp51-72}
  76 {
  77 GRIP is a multiprocessor designed to execute functional programs in
  78 parallel using graph reduction.  We have implemented a compiler for
  79 GRIP, based on the Spineless Tagless G-machine
  80 and can now run parallel functional programs with substantial absolute
  81 speedup over the same program running on a uniprocessor Sun.
  82
  83 Parallel functional programming shifts some of the burden of resource
  84 allocation from the programmer to the system.  Examples of such
  85 decisions include: when to create a new concurrent activity (or {\em
  86 thread}), when to execute such threads, where to execute them, and so
  87 on.
  88
  89 It is clearly desirable that the system should take such decisions,
  90 {\em provided it does
  91 a good enough job}.  For example, a paged virtual memory system
  92 almost always does an adequate job, and a programmer very seldom
  93 has to intefere with it.
  94 The big question for parallel functional programming is whether good
  95 resource-allocation strategies exist, and how well they perform under a
  96 variety of conditions.
  97
  98 Now that we have an operational system, we are starting to carry out
  99 experiments to develop resource-allocation strategies, and measure
 100 their effectiveness.  This paper reports on some very preliminary
 101 results.  They mainly concern the question of when, or even whether,
 102 to create a new thread.  This is an aspect which has so far received
 103 little attention --- existing work has focused mainly
 104 on load sharing rather than on thread creation.
 105 }
 106
 107
 108 \section{Technical reports}
 109
 110 \reference
 111 {Simon L Peyton Jones and Philip Wadler}
 112 {A static semantics for \Haskell{}}
 113 {Dept of Computing Science, University of Glasgow}
 114 {
 115 This paper gives a static semantics for a large subset of \Haskell{}, including
 116 giving a translation into a language without overloading.
 117 It is our intention to cover the complete language in due course.
 118
 119 One innovative aspect is the use of ideas from the second-order lambda
 120 calculus to record type information in the program.
 121
 122 The paper is long (40 pages) and is more of a reference document than
 123 a narrative one.
 124 }
 125
 126 \reference
 127 {Philip Wadler}
 128 {A simple type inference algorithm}
 129 {Dept of Computing Science, University of Glasgow}
 130 {
 131 This program is intended as a showcase for Haskell's
 132 literate programming facility and for the monadic style
 133 of programming.  It implements Hindley-Milner type inference.
 134 Monads are used for parsing and to simplify ``plumbing'' in the type
 135 checker. The monads for parsing, exceptions, and state as well
 136 as the routines for unparsing are designed to be of general utility.
 137 }
 138
 139 \reference{The Grasp team}
 140 {The Glasgow Haskell I/O system}
 141 {Dept of Computing Science, University of Glasgow, Nov 1991}
 142 {
 143 Most input/output systems for non-strict functional languages
 144 feature a rather large ``operating system
 145 The Glasgow Haskell system implements input and output
 146 very largely within Haskell itself, without the conventional
 147 enclosing ``printing mechanism''.  This paper explains how the
 148 IO system works in some detail.
 149 }
 150
 151 \end{document}
 152
 153