% % (Compiled by) 1993 % % Wolfgang Schreiner % Research Institute for Symbolic Computation (RISC-Linz) % Johannes Kepler University, A-4040 Linz, Austria % % PLEASE DO NOT REMOVE THIS NOTICE. % @incollection{AFJ91, author = {Ashcroft, E. A. and Faustini, A. A. and Jagannathan, R.}, title = {{An Intensional Language for Parallel Application Programming}}, booktitle = {Parallel Functional Languages and Compilers}, editor = {Szymanski, Boleslaw K.}, publisher = {ACM Press}, address = {New York}, year = {1991}, series = {Frontier Series}, chapter = {2}, pages = {11--50}, abstract = {Programming languages that are not based on a sequential model of computation --- i.e., declarative languages --- can exhibit significant amount of implicit parallelism. The declarative languages are therefore important parallel programming languages. Within the declarative paradigm, we feel that the languages based on intensional logic are unique in that they permit data structures such as arrays, lists, and trees to be implemented in a manner that is easily distributable. Also, intensional programs are concise and elegant. To illustrate the concepts, we have chosen a particular intensional language, namely Lucid. Lucid's simplicity and semantic elegance make possible the inclusion of nontrivial application programs --- an adaptive solution to the n-body problem and programs for LU decomposition of matrices. We present an analysis of the implicit parallelism available in these programs and show ways in which we can harness this parallelism.}, keywords = {Dataflow, Lucid}, } @inproceedings{AnHu90, author = {Anderson, Steven and Hudak, Paul}, title = {{Compilation of Haskell Array Comprehensions for Scientific Computing}}, booktitle = {SIGPLAN '90 Conference on Programming Language Design and Implementation}, address = {White Plains, New York, June 20--22}, year = {1990}, series = {SIGPLAN NOTICES}, volume = {25(6)}, pages = {137--149}, abstract = {Monolithic approaches to functional language arrays, such as Haskell {\em array comprehensions\/}, define elements all at once, at the time the array is created, instead of incrementally. Although monolithic arrays are elegant, a naive implementation can be very inefficient. For example, if a compiler does not know whether an element has zero or many definitions, it must compile runtime tests. If a compiler does not know inter-element data dependences, it must resort to pessimistic strategies such as compiling elements as thunks, or making unnecessary copies when updating an array. Subscript analysis, originally developed for imperative language vectorizing and parallelizing compilers, can be adapted to provide a functional language compiler with the information needed for efficient compilation of monolithic arrays. Our contribution is to develop the number-theoretic basis of subscript analysis with assumptions appropriate to functional arrays, detail the kinds of dependence information subscript analysis can uncover, and apply that dependence information to sequential efficient compilation of functional arrays.}, keywords = {Arrays, Updating Aggregates}, } @inproceedings{Ary89, author = {Arya, Kavi}, title = {{Processes in a Functional Animation System}}, booktitle = {{FPCA '89, Functional Programming Languages and Computer Architecture}}, address = {London, UK, September 11--13}, year = {1989}, publisher = {ACM Press, New York}, pages = {382--395}, abstract = {We investigate the problem of rapidly prototyping animation sequences. Conventional programming languages such as `C' result in programs that are notoriously difficult to develop and to change. We show how a functional approach leads to a fresh perspective on the problem. A compact set of primitive operations over movies (i.e.\ {\em picture sequences\/}) is used as the basis for an animation system. We investigate the problem of interaction between components of an animation sequence and then show how lazy evaluation may be used to devise a process-oriented metaphor within a purely functional framework. This allows to arrange the interaction of animation sequences by encapsulating them within processes.}, keywords = {Operating Systems, Process Networks}, } @inproceedings{BaHu89, author = {Gebreselassi, Baraki and Hughes, John}, title = {{Abstract Interpretation of Polymorphic Functions}}, booktitle = {Functional Programming: Proceedings of the 1989 Glasgow Workshop}, address = {Fraserburgh, Scotland, August 21--23}, year = {1989}, editor = {Davis, Kei and Hughes, John}, series = {Workshops in Computing}, publisher = {Springer, Berlin}, pages = {31--40}, abstract = {Abstract interpretation is one of the popular techniques used in doing program analysis. In this paper, we define an abstract interpretation of polymorphic functions which may be used to perform strictness analysis. The abstract functions of polymorphic functions are again polymorphic. Finally, it is proved that the abstract interpretation is safe.}, keywords = {Abstract Interpretation, Strictness Analysis, Polymorphism}, } @inproceedings{BaMe89, author = {Banatre, Jean-Pierre and Le Metayer, Daniel}, title = {{Chemical Reaction as a Computational Model}}, booktitle = {Functional Programming: Proceedings of the 1989 Glasgow Workshop}, address = {Fraserburgh, Scotland, August 21--23}, year = {1989}, editor = {Davis, Kei and Hughes, John}, series = {Workshops in Computing}, publisher = {Springer, Berlin}, pages = {103--117}, abstract = {We present a new formalism called GAMMA which relies on the chemical reaction metaphor; the only data structure is the multiset and the computation can be seen as a succession of chemical reactions consuming elements of the multiset and producing new elements according to specific rules. We show the relevance of this formalism with respect to program development by proposing a systematic program derivation method.}, keywords = {Multiset, Non-Determinism}, } @inproceedings{BEG*87, author = {Barendregt, H. P. and van Eekelen, M. C. J. D. and Glauert, J. R. W. and Kennaway, J. R. and Plassmeijer, M. J. and Sleep, M. R.}, title = {{Term Graph Rewriting}}, booktitle = {PARLE '87 Parallel Architectures and Languages Europe, Volume 2: Parallel Languages}, address = {Eindhoven, The Netherlands, June 15--19}, year = {1987}, volume = {259}, editor = {de Bakker, J. W. and Nijman, A. J. and Treleaven, P. C.}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {141--158}, abstract = {Graph rewriting (also called reduction) as defined by Wadsworth was introduced in order to be able to give a more efficient implementation of functional programming languages in the form of lambda calculus or term rewrite systems: identical subterms are shared using pointers. Several other authors, e.g.\ Ehrig, Staples, Raoult and van den Broek have given mathematical descriptions of graph rewriting, usually employing concepts from category theory. These papers prove among other things the correctness of graph rewriting in the form of the Church-Rosser property for ``well-behaved'' (i.e.\ regular) rewrite systems. However, only Staples has formally studied the soundness and completeness of graph rewriting with respect to term rewriting. In this paper we give a direct operational description of graph rewriting that avoids the category theoretic notions. We show that if a term $t$ is interpreted as graph $g(t)$ and is reduced in the graph world, then the result represents an actual reduct of the original term $t$ ({\em soundness\/}). For weakly regular term rewrite systems, there is also a {\em completeness\/} result: every normal form of a term $t$ can be obtained from the graphical implementation. We also show completeness for all term rewrite systems which possess a so called hypernormalizing strategy, and in that case the strategy also gives a normalizing strategy for the graphical implementation. Besides having nice theoretical properties, weakly regular systems offer opportunities for parallelism, since redexes at different places can be executed independently or in parallel, without affecting the final result.}, keywords = {Graph Reduction, Semantics}, } @inproceedings{BEG*87a, author = {Barendregt, H. P. and van Eekelen, M. C. J. D. and Glauert, J. R. W. and Kennaway, J. R. and Plassmeijer, M. J. and Sleep, M. R.}, title = {{Towards an Intermediate Language based on Graph Rewriting}}, booktitle = {PARLE '87 Parallel Architectures and Languages Europe, Volume 2: Parallel Languages}, address = {Eindhoven, The Netherlands, June 15--19}, year = {1987}, volume = {259}, editor = {de Bakker, J. W. and Nijman, A. J. and Treleaven, P. C.}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {159--175}, abstract = {Lean is an experimental language for specifying computations in terms of graph rewriting. It is based on an alternative to Term Rewriting Systems (TRS) in which the terms are replaced by graphs. Such a Graph Rewriting System (GRS) consists of a set of graph rewrite rules which specify how a graph may be rewritten. Besides supporting functional programming, Lean also describes imperative constructs and allows the manipulation of cyclic graphs. Programs may exhibit non-determinism as well as parallelism. In particular, Lean can serve as an intermediate language between declarative languages and machine architectures, both sequential and parallel.}, keywords = {Graph Rewriting, Semantics, Abstract Machine}, } @book{BiWa88, author = {Bird, Richard and Wadler, Philip}, title = {{Introduction to Functional Programming}}, series = {Series in Computer Science}, publisher = {Prentice-Hall International}, address = {Englewood Cliffs, NJ}, year = {1988}, abstract = {}, keywords = {Functional Programming, Streams}, } @inproceedings{Bloss87, author = {Bloss, Adrienne}, title = {{Update Analysis and the Efficient Implementation of Functional Aggregates}}, booktitle = {FPCA '87, Functional Programming Language and Computer Architecture}, address = {Portland, Oregon, USA, September 14--16}, year = {1987}, editor = {Kahn, Gilles}, publisher = {Springer, Berlin}, volume = {274}, series = {Lecture Notes in Computer Science}, pages = {26--38}, abstract = {In this paper we introduce a technique for efficiently implementing updatable aggregates in sequential first-order lazy functional languages. The technique is based on {\em path analysis\/}, a compile time analysis that yields information about {\em order of evaluation of expressions\/} and produces speedups over both the naive implementation and another optimization technique involving {\em trailers\/}.}, keywords = {Aggregate Updates}, } @incollection{Burn90, author = {Burn, G. L.}, title = {{Implementing Lazy Functional Languages on Parallel Architectures}}, booktitle = {Parallel Computers --- Object-Oriented, Functional, Logic}, editor = {Treleaven, P. C.}, publisher = {John Wiley {\&} Sons}, series = {Series in Parallel Computing}, address = {Chichester}, year = {1990}, chapter = {5}, pages = {101--140}, abstract = {Lazy functional languages are a very powerful programming paradigm. In this chapter, we show how such languages, with no parallel constructs, can be implemented on parallel architectures. Troughout the project, we have taken a ``language-first'' approach to architecture development, allowing the programming language style and its semantics to drive the parallel implementation model and architectural development.}, keywords = {Parallel Graph Reduction, Evaluation Transformers}, } @book{Burn91, author = {Burn, Geoffrey}, title = {{Lazy Functional Languages: Abstract Interpretation and Compilation}}, series = {Research Monographs in Parallel and Distributed Computing}, publisher = {Pitman, London}, year = {1991}, abstract = {The author's Ph.D.\ thesis describes in large detail the concepts of abstract interpretation for the semantic analysis of functional languages. This book introduces the evaluation transformers approach to strictness analysis.}, keywords = {Abstract Interpretation, Evaluation Transformers}, } @incollection{CCL91, author = {Chen, Marina and Choo, Young-il and Li, Jingke}, title = {{Crystal: Theory and Pragmatics of Generating Efficient Parallel Code}}, booktitle = {Parallel Functional Languages and Compilers}, editor = {Szymanski, Boleslaw K.}, publisher = {ACM Press}, address = {New York}, year = {1991}, series = {Frontier Series}, chapter = {7}, pages = {255--308}, abstract = {The Crystal project has focused on making the task of programming massively parallel machines practical while not sacrificing the efficiency of the target code. We believe that these goals can be achieved by starting from a high-level problem specification, through a sequence of optimizations tuned for particular parallel machines, leading to the generation of efficient target code with explicit communications or synchronization. Our approach to automation is to design a compiler that classifies source programs according to the communication primitives and their cost on the target machine and that maps the data structures to distributed memory, and then generates parallel code with explicit communication commands. Regarding those classes of problems for which the default mapping strategies of the compiler are inadequate, we provide special language constructs for incorporating domain specific knowledge and directing the compiler in its mapping.}, keywords = {Compilation, Crystal}, } @inproceedings{CGR89, author = {Cox, Stuart and Glaser, Hugh and Reeve, Mike}, title = {{Implementing Functional Languages on the Transputer}}, booktitle = {Functional Programming: Proceedings of the 1989 Glasgow Workshop}, address = {Fraserburgh, Scotland, August 21--23}, year = {1989}, editor = {Davis, Kei and Hughes, John}, series = {Workshops in Computing}, publisher = {Springer, Berlin}, pages = {287--295}, abstract = {The aim of work presented here is to develop a method for implementing lazy, curried functional languages for such architectures, giving performance comparable with imperative languages and supporting interlanguage working. The system described in this paper confirms to the interlanguage standard of the transputer and, for example, as a result it can use a functional language to map a C function over a list that has been constructed by the functional program.}, keywords = {Parallel Graph Reduction}, } @inproceedings{DaWa89, author = {Davis, K. and Wadler, P.}, title = {{Backwards Strictness Analysis: Proved and Improved.}}, booktitle = {Functional Programming: Proceedings of the 1989 Glasgow Workshop}, address = {Fraserburgh, Scotland, August 21--23}, year = {1989}, editor = {Davis, Kei and Hughes, John}, series = {Workshops in Computing}, publisher = {Springer, Berlin}, pages = {12--30}, abstract = {Given a syntax tree representing an expression, and some information regarding that expression, a {\em backwards analysis\/} will involve propagating the information (with appropriate transformation) towards the leaves of the tree, to yield information about the subexpressions. Here, the information at the root will describe the required definedness of the value of the expression, with the results of the analysis describing the definedness of the values lower in the tree sufficient or necessary to meet the condition at the root. In {\em Projections for Strictness Analysis\/}, such an analysis is described in which the information at each node is encoded by a special kind of function called a {\em projection\/}, with the results of the analysis leaving strictness information about the expression. This paper describes a more general and powerful technique, and provides proofs that both techniques meet a corresponding generalization of the safety condition.}, keywords = {Strictness Analysis, Backwards Analysis, Projections}, } @inproceedings{Desc89, author = {Deschner, J. M.}, title = {{Simulating Multiprocessor Architectures for Compiled Graph-Reduction}}, booktitle = {Functional Programming: Proceedings of the 1989 Glasgow Workshop}, address = {Fraserburgh, Scotland, August 21--23}, year = {1989}, editor = {Davis, Kei and Hughes, John}, series = {Workshops in Computing}, publisher = {Springer, Berlin}, pages = {225--237}, abstract = {Software simulations of hardware architectures are useful tools for evaluating a systems performance prior to its construction. This is especially true of multi-processor architectures where the design complexity is increased by orders of magnitude. It is also necessary to be able to simulate accurately the behavior of a parallel machine after it has been built. Statistics may then continue to be gathered without adversely affecting the behavior of the hardware. This paper describes in detail a system for simulating the parallel execution of functional programs based on compiled graph-reduction.}, keywords = {Parallel Graph Reduction, Simulation}, } @inproceedings{DLH90, author = {Debray, Saumya K. and Lin, Nai-Wei and Hermenegildo, Manuel}, title = {{Task Granularity Analysis in Logic Programs}}, booktitle = {SIGPLAN '90 Conference on Programming Language Design and Implementation}, address = {White Plains, New York, June 20--22}, year = {1990}, series = {SIGPLAN NOTICES}, volume = {25(6)}, pages = {174--188}, abstract = {While logic programming languages offer a great deal of scope for parallelism, there is usually some overhead associated with the execution of goals in parallel because of the work involved in task creation and scheduling. In practice, therefore, the ``granularity'' of a goal, i.e.\ an estimate of the work available under it, should be taken into account when deciding whether or not to executed a goal concurrently as a separate task. This paper describes a method for estimating the granularity of a goal at compile time. The runtime overhead associated with our approach is usually quite small, and the performance improvements resulting from the incorporation of grainsize control can be quite good. This is shown by means of experimental results.}, keywords = {Granularity Analysis}, } @inproceedings{ENG89, author = {Evripidou, P. and Najjar, W. and Gaudiot, J.-L.}, title = {{A Single-Assignment Language on a Distributed Memory Multiprocessor}}, booktitle = {{PARLE '89, Parallel Architectures and Languages Europe, Volume I: Parallel Architectures}}, address = {Eindhoven, The Netherlands, June 12--16}, year = {1989}, editor = {Odijk, E. and Rem, M. and Syre, J.-C.}, series = {Lecture Notes in Computer Science}, volume = {365}, publisher = {Springer, Berlin}, pages = {304--320}, abstract = {Large-scale distributed memory multiprocessors have become commercially available and have proved to be a low-cost alternative to supercomputers for many scientific computations. The programming, and debugging, of such systems remains, however, a difficult and tedious task. Single-assignment and applicative languages have proved to be a serious alternative to imperative languages for the programming of parallel computer systems. They offer the advantage of a high level of programmability and eliminate the problem of detecting parallelism. Their functional property allows an asynchronous parallel execution that does not comprise the correctness of the computation. This paper describes the implementation of a single-assignment language, SISAL, on a distributed memory multiprocessor.}, keywords = {Dataflow, SISAL, Compilation}, } @incollection{Ekan91, author = {Ekanadham, Kattamuri}, title = {{A Perspective on Id}}, booktitle = {Parallel Functional Languages and Compilers}, editor = {Szymanski, Boleslaw K.}, publisher = {ACM Press}, address = {New York}, year = {1991}, series = {Frontier Series}, chapter = {6}, pages = {197--254}, abstract = {This chapter is a comprehensive exposition of many aspects of the Id language. Section 6.2 introduces the principal features of the language to the reader unfamiliar with. Section 6.3 thus discusses three examples in detail. These are from numerical applications and are all self-contained. Section 6.4 gives the operational semantics for the language in terms of rewrite rules. Section 6.5 illustrates a few optimizations to show how they can be expressed in this framework. Section 6.6 discusses the lower level abstraction of I-structures which is used to implement the higher level abstractions.}, keywords = {Dataflow, Id}, } @book{FiHa88, author = {Field, Anthony J. and Harrison, Peter G.}, title = {{Functional Programming}}, publisher = {Addison-Wesley}, address = {Wokingham, England}, series = {International Computer Science Series}, year = {1988}, abstract = {This book covers all aspects of functional programming languages including their implementation, compilation and optimization. It also discusses the functional description of process networks, streams, dataflow and strictness analysis by abstract interpretation.}, keywords = {Functional Programming}, } @inproceedings{GaCa84, author = {Gabriel, Richard P. and McCarthy, John}, title = {{Queue-based Multi-processing Lisp}}, booktitle = {1984 ACM Symposium on Lisp and Functional Programming}, address = {Austin, Texas, August 6--8}, year = {1984}, publisher = {ACM Press, New York}, pages = {25--44}, abstract = {A the need for high-speed computers increases, the need for multi-processors will become more apparent. One of the major stumbling blocks to the development of useful multi-processors has been the lack of a good multi-processing language --- one which is both powerful and understandable to programmers. Among the most compute-intensive programs are artificial intelligence (AI) programs, and researchers hope that the potential degree of parallelism in AI programs is higher than in many other applications. In this paper we propose multi-processing extensions to Lisp. Unlike other proposed multi-processing Lisps, this one provides only a few very powerful and intuitive primitives rather than a number of parallel variants of familiar constructs.}, keywords = {Lisp, Queues}, } @inproceedings{GaWe90, author = {Garsden, H. and Wendelborn, A. L.}, title = {{A Comparison of Microtasking Implementation of the Applicative Langague SISAL}}, booktitle = {CONPAR 90 --- VAPP IV, Joint International Conference on Vector and Parallel Processing}, address = {Zurich, Switzerland, September 10--13}, year = {1990}, editor = {Burkhart, H.}, volume = {457}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {697--708}, abstract = {The applicative parallel programming language SISAL has been implemented on conventional multiprocessors with the use of microtasking systems designed to support fine-grained parallelism. Experiments with different versions of such a system, including an implementation under the Mach operating system using its lightweight processes, are reported.}, keywords = {Sisal, Dataflow}, } @inproceedings{GGS89, author = {Goldman, Ron and Gabriel, Richard P. and Sexton, Carol}, title = {{Qlisp: An Interim Report}}, booktitle = {Parallel Lisp: Languages and Systems}, address = {Sendai, Japan, June 5--8}, year = {1988}, editor = {Ito, T. and Halstead, R. H.}, volume = {441}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {161--181}, abstract = {One of the major problems in writing programs to take advantage of parallel processing has been the lack of good multiprocessing languages --- ones which are both powerful and understandable to programmers. In this paper we describe multiprocessing extensions to Common Lisp designed to be suitable for studying styles of parallel programming at the medium-grain level in a shared memory architecture. The resulting language is called Qlisp. A problem with parallel programming is the degree to which the programmer must explicitly address synchronization problems. Two new approaches to this problem look promising: the first is the concept of heavyweight futures, and the second is a new type of function called a partially, multiply invoked function.}, keywords = {Lisp, Futures}, } @inproceedings{Grit90, author = {Grit, Dale H.}, title = {{Sisal on a Message Passing Architecture}}, booktitle = {CONPAR 90 --- VAPP IV, Joint International Conference on Vector and Parallel Processing}, address = {Zurich, Switzerland, September 10--13}, year = {1990}, editor = {Burkhart, H.}, volume = {457}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {721--731}, abstract = {{\sc Sisal} is a general-purpose applicative language intended for use on both conventional and novel multiprocessor systems. In this paper we describe the port of a shared memory implementation to a message passing environment. The issues underlying the main features of this implementation are discussed.}, keywords = {Sisal, Dataflow}, } @inproceedings{GrSu87, author = {Gross, Thomas and Sussman, Alan}, title = {{Mapping a Single-Assignment Language onto the Warp Systolic Array}}, booktitle = {FPCA '87, Functional Programming Language and Computer Architecture}, address = {Portland, Oregon, USA, September 14--16}, year = {1987}, editor = {Kahn, Gilles}, publisher = {Springer, Berlin}, volume = {274}, series = {Lecture Notes in Computer Science}, pages = {347--363}, abstract = {Single-assignment languages offer the potential to efficiently program parallel processors. This paper discusses issues that arise in mapping SISAL programs onto the Warp array, a linear systolic array in use at Carnegie Mellon. A Warp machine with ten cells can deliver up to 100 million floating point operations per second. The paper begins with a discussion of systolic arrays as targets for single-assignment languages and the suitability of the Warp machine for this purpose. Systolic arrays can take advantage of both large-grain parallelism and fine-grain parallelism. The communication bandwidth of the systolic array gives the translator great flexibility in mapping a SISAL program onto the linear array. We present two principal methods to exploit parallelism on Warp, data partitioning and pipelining. Data partitioning is effective for local computations that depend on only a small neighborhood of values. Since SISAL allows the specification of array sizes at run-time, we have to provide static and dynamic methods for dynamic data partitioning. Pipelining allows the overlapping of different states of a computation or of function invocations. This method is well suited for Warp since the systolic array has high inter-cell communication bandwidth. This makes it possible to send large data sets to the next processor in a computation pipeline without performance degradation. We use matrix multiplication and a relaxation algorithm, respectively, as examples to illustrate the data partitioning and pipeline models for mapping SISAL programs onto the Warp array.}, keywords = {Dataflow, SISAL, SIMD}, } @inproceedings{HaHu92, author = {Hankin, Chris and Hunt, Sebastian}, title = {{Approximate Fixed Points in Abstract Interpretation}}, booktitle = {ESOP '92, 4th European Symposium on Programming}, address = {Rennes, France, February 26--28}, year = {1992}, editor = {Krieg-Br{\"u}ckner, B.}, series = {Lecture Notes in Computer Science}, volume = {582}, publisher = {Springer, Berlin}, pages = {219--232}, abstract = {Much of the earlier development of abstract interpretation, and its application to imperative programming languages, has concerned techniques for finding fixed points in large (often infinite) lattices. The standard approach in the abstract interpretation of functional languages has been to work with small, finite lattices and this supposedly circumvents the need for such techniques. However, practical experience has shown that, in the presence of higher order functions, the lattices soon become too large (although still finite) for the fixed-point finding problem to be tractable. This paper develops some approximation techniques which were first proposed by Hunt and shows how these techniques relate to the earlier use of widening and narrowing operations by the Cousots.}, keywords = {Fixpoints, Abstract Interpretation}, } @inproceedings{Harr87, author = {Harrison, Dave}, title = {{RUTH: A Functional Language for Real-Time Programming}}, booktitle = {PARLE '87 Parallel Architectures and Languages Europe, Volume 2: Parallel Languages}, address = {Eindhoven, The Netherlands, June 15--19}, year = {1987}, volume = {259}, editor = {de Bakker, J. W. and Nijman, A. J. and Treleaven, P. C.}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {297--314}, abstract = {This paper introduces the real-time programming language RUTH which is a functional language based on the lazy language LispKit LISP. RUTH is a semantically pure functional language in which the concept of a process is encapsulated by the more general concept of a function. Communication between processes is modelled by streams of timestamped values. RUTH programs take as input a tree of integers which is lazily evaluated as the program executes to produce node values representing the current time. Taking real-time information as an input data structure allows RUTH programs to define and react to real-time events without loosing referential transparency and allows us to define a formal semantics without the complication of including time information.}, keywords = {Real-Time, Process Networks, Streams}, } @book{Hend80, author = {Henderson, Peter}, title = {{Functional Programming: Application and Implementation}}, series = {International Series in Computer Science}, publisher = {Prentice Hall}, address = {New Jersey}, year = {1980}, abstract = {}, keywords = {Streams, Process Networks}, } @inproceedings{HiDy90, author = {Hieb, Robert and Dybvig, R. Kent}, title = {{Continuations and Concurrency}}, booktitle = {PPoPP '90, Symposium on Principles and Practice of Parallel Programming}, address = {Seattle, Washington, March 14--16}, year = {1990}, series = {SIGPLAN NOTICES}, volume = {25(3)}, publisher = {ACM Press, New York}, pages = {128--136}, abstract = {Continuations have proven to be useful for implementing a variety of control structures, including exception handling facilities and breadth-first searching algorithms. However, traditional continuations are not useful in the presence of concurrency, because the notion of the rest of the computation represented by a continuation does not in general make sense. This paper presents a new type of continuation, called a {\em process continuation\/}, that may be used to control tree-structured concurrency. Just as a traditional continuation represents the rest of a computation from a given point in the computation from a given point in the computation, a process continuation represents the rest of a {\em subcomputation\/}, or {\em process\/}, from a given point in the {\em subcomputation\/}. Process continuations allow nonlocal exits to arbitrary points in the process tree and allow the capture of a subtree of a computation as a composable continuation for later use. Even in the absence of multiple processes, the precise control achievable with process continuations makes them more useful than traditional continuations.}, keywords = {Continuations}, } @inproceedings{HKL92, author = {Hogen, Guido and Kindler, Andrea and Loogen, Rita}, title = {{Automatic Parallelization of Lazy Functional Programs}}, booktitle = {ESOP '92, 4th European Symposium on Programming}, address = {Rennes, France, February 26--28}, year = {1992}, editor = {Krieg-Br{\"u}ckner, B.}, series = {Lecture Notes in Computer Science}, volume = {582}, publisher = {Springer, Berlin}, pages = {254--268}, abstract = {We present a parallelizing compiler for lazy functional programs that uses strictness analysis to detect the implicit parallelism within programs. It generates an intermediate functional program, where a special syntactic construct {\em 'letpar'\/}, which is semantically equivalent to the well-known {\em let\/}-construct, is used to indicate subexpressions for which a parallel execution is allowed. Only for sufficiently complex expressions a parallelization will be worthwile. For small expressions the communication overhead may outweigh the benefits of the parallel execution. Therefore, the parallelizing compiler uses some heuristics to estimate the complexity of expressions. The distributed implementation of parallelized functional programs enabled us to investigate the impact of various parallelization strategies on the runtimes and speedups. The strategy, which only allows the parallel execution of non-predefined function calls in strict positions shows the best runtimes and reasonable speedup results.}, keywords = {Compilation, Strictness Analysis, Evaluation Transformers}, } @inproceedings{Hals84, author = {Halstead, Robert H.}, title = {{Implementation of Multilisp: Lisp on a Multiprocessor}}, booktitle = {1984 ACM Symposium on Lisp and Functional Programming}, address = {Austin, Texas, August 6--8}, year = {1984}, publisher = {ACM Press, New York}, pages = {9--17}, abstract = {Multilisp is an extension of Lisp (more specifically, of the Lisp dialect Scheme) with additional operators and additional semantics to deal with parallel execution. It is being implemented on th 32-processor {\em Concert\/} multiprocessor. The current implementation is complete enough to run the Multilisp compiler itself, and has been run on Concert prototypes including up to four processors. Novel techniques are used for task scheduling and garbage collection. The task scheduler helps control excessive resource utilization by means of an unfair scheduling policy: the garbage collector uses a multiprocessor algorithm modeled after the incremental garbage collector of Baker. A companion paper discusses language design issues relating to Multilisp.}, keywords = {Multilisp}, } @inproceedings{Hals89, author = {Halstead, Robert H.}, title = {{New Ideas in Parallel Lisp: Language Design, Implementation, and Programming Tools}}, booktitle = {Parallel Lisp: Languages and Systems}, address = {Sendai, Japan, June 5--8}, year = {1988}, editor = {Ito, T. and Halstead, R. H.}, volume = {441}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {2--57}, abstract = {A Lisp-based approach is attractive for parallel computing since Lisp languages and systems assume significant clerical burdens, such as storage management. Parallel Lisps thus enable programmers to focus on the new problems introduced by using concurrency. Parallel Lisps now exist that can execute realistic applications with ``industrial-strength'' performance, but there are applications whose requirements they do not handle elegantly. Recent Work has contributed new, elegant ideas in the area of speculative computation, continuations, exception handling, aggregate data structures, and scheduling. Using these ideas, it should be possible to build ``second generation'' parallel Lisp systems that are as powerful and elegantly structured as sequential Lisp systems. This paper surveys these recent ideas and explores how they could fit together in the parallel Lisp systems of the future, examining issues at three levels: language design, implementation techniques, and programming tools. The discussion is based on the Multilisp programming language, which is Scheme (a Lisp dialect) extended with the {\tt future} construct. The paper outlines three criteria for judging Scheme extensions for parallel computing: compatibility with sequential Scheme, invariance of the result when {\tt future} is introduced into side-effect-free Scheme programs, and modularity. Proposed language mechanisms, such as support of first-class continuations, are evaluated against these criteria. In the area of implementation techniques, results of experiments with lazy task creation, unfair scheduling, and parallel garbage collection are surveyed; some areas that need more investigation, such as scheduler implementation for speculative computing, and interaction between user-level and operating-system schedulers, are identified. Finally, past work in tools to help with the development of Multilisp programs is surveyed, and needs for additional tools is discussed.}, keywords = {Lisp, Futures}, } @inproceedings{HaAm89, author = {Harrison III, William Ludwell and Ammarguella, Zahira}, title = {{The Design of Automatic Parallelizers for Symbolic and Numeric Programs}}, booktitle = {Parallel Lisp: Languages and Systems}, address = {Sendai, Japan, June 5--8}, year = {1988}, editor = {Ito, T. and Halstead, R. H.}, volume = {441}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {235--253}, abstract = {Parcel is a compiler and run-time system that automatically parallelizes a scheme program for execution on a shared memory multiprocessor. Parcel's inter-procedural analysis makes it capable of extracting high-level parallelism from complex applications; it introduced a number of program transformations that are especially useful in parallelizing symbolic computations; and its run-time system makes good use of multiple procedure versions to achieve parallelism without undue inefficiency. In this paper we will describe the strengths and weaknesses of Parcel, and outline the design of Miprac in light of our experience with Parcel.}, keywords = {Lisp, Parallelization}, } @inproceedings{HaFr84, author = {Haynes, Christopher T. and Friedman, Daniel P.}, title = {{Engines Build Process Abstractions}}, booktitle = {1984 ACM Symposium on Lisp and Functional Programming}, address = {Austin, Texas, August 6--8}, year = {1984}, publisher = {ACM Press, New York}, pages = {18--24}, abstract = {{\em Engines\/} are a new programming language abstraction for timed preemption. In conjunction with first class continuations, engines allow the language to be extended with a time-sharing implementation of process abstraction facilities. To illustrate engine programming techniques, we implement a round-robin process scheduler. The importance of simple but powerful primitives such as engines is discussed.}, keywords = {Continuations, Process Scheduling}, } @inproceedings{HFW84, author = {Haynes, Christopher T. and Friedman, Daniel, P. and Wand, Mitchell}, title = {{Continuation and Coroutines}}, booktitle = {1984 ACM Symposium on Lisp and Functional Programming}, address = {Austin, Texas, August 6--8}, year = {1984}, publisher = {ACM Press, New York}, pages = {293--298}, abstract = {The power of first class continuations is demonstrated by implementing a variety of coroutine mechanisms using only continuations and functional abstractions. The importance of general abstraction mechanisms such as coroutines is discussed.}, keywords = {Continuations, Coroutines}, } @article{HiCo88, author = {Hickey, Timothy and Cohen, Jacques}, title = {{Automatic Program Analysis}}, journal = jacm, volume = {35}, number = {1}, pages = {185--220}, month = {January}, year = {1988}, abstract = {The first part of the paper shows that previous theoretical work on the semantics of probabilistic programs (Kozen) and on the correctness of performance annotated programs (Ramshaw) can be used to automate the average-case analysis of simple programs containing assignments, conditionals, and loops. A performance compiler has been developed using this theoretical foundations. The compiler is described, and it is shown that special cases of symbolic simplifications of formulas play a major role in rendering the system usable. The performance compiler generates a system of recurrence equations derived from a given program whose efficiency one wishes to analyze. This generation is always possible, but the problem of solving the resulting equations may be complex. The second part of the paper presents an original method that generalizes our previous approach and is applicable to functional programs that make use of recursion and complex data structures. Several examples are presented including an analysis of binary tree sort. A key feature of the analysis of such programs is that distributions on complex data structures are represented using attributed probabilistic grammars.}, keywords = {Granularity Analysis}, } @inproceedings{HuAn87, author = {Hudak, Paul and Anderson, Steve}, title = {{Pomset Interpretations of Parallel Functional Programs}}, booktitle = {{Functional Programming Languages and Computer Architecture}}, editor = {Kahn, Gilles}, address = {Portland, Oregon, USA, September 14--16}, year = {1987}, pages = {234--256}, series = {Lecture Notes in Computer Science}, volume = {274}, publisher = {Springer, Berlin}, abstract = {A new framework is presented, based on the notion of a {\em partially ordered multiset\/} (or {\em pomset\/}), which is able to provide not only a precise operational semantics of parallel functional program evaluation, but also a handle through which to control such behavior. As an operational semantics, pomsets are able to distinguish between call-by-value, call-by-name, call-by-need, and call-by-speculation evaluation strategies (even though all but the first of these have the same standard semantics); and as a ``handle'' from which to control operational behavior, pomsets can express most of the behaviors achieved by previously proposed annotations that control not only evaluation order but also the spatial mapping of program to machine.}, keywords = {Semantics, Speculative Parallelism}, } @incollection{Huda91, author = {Hudak, Paul}, title = {{Para-Functional Programming in Haskell}}, booktitle = {Parallel Functional Languages and Compilers}, editor = {Szymanski, Boleslaw K.}, publisher = {ACM Press}, address = {New York}, year = {1991}, series = {Frontier Series}, chapter = {5}, pages = {159--196}, abstract = {In this chapter I will introduce an extension to the functional programming paradigm, called {\em para-functional programming\/}, that allows us to express the aforementioned kinds of behavior without losing any of the well-known benefits of functional languages. The idea is based on preserving the qualitative difference between {\em functional\/} behavior (that is, {\em what\/} the program computes) and {\em operational\/} behavior (that is, {\em how\/} the answer is computed). The ideas can be adopted in any functional language, but I will express them in {\em Haskell\/}, a recently designed functional language that captures most of the major innovations in functional language research.}, keywords = {Para-Functional Programming, Process Scheduling, Mapping}, } @inproceedings{HuGo84, author = {Hudak, Paul and Goldberg, Benjamin}, title = {{Experiments in Diffused Combinator Reduction}}, booktitle = {1984 ACM Symposium on Lisp and Functional Programming}, address = {Austin, Texas, August 6--8}, year = {1984}, publisher = {ACM Press, New York}, pages = {167--176}, abstract = {In recent years there has been a fair amount of interest both in using {\em combinators\/} to represent functional programs, and in using {\em graph reduction\/} as an underlying evaluation strategy. Combining these ideas within a single framework for an ``applicative architecture'' is very appealing because: (1) the normally ubiquitous ``environment'' is eliminated, (2) the evaluation strategy becomes very simple (amenable to VLSI), and (3) there is a great potential for parallelism. We have been exploring a model of diffused combinator reduction in which the reduction process is distributed ``by demand'' among a network of closely-coupled processors. We have tested our ideas via simulation, with encouraging results.}, keywords = {Parallel Graph Reduction, Combinators}, } @inproceedings{HuDo89, author = {Hughes, John and O'Donnell, John}, title = {{Expressing and Reasoning about Non-deterministic Functional Programs}}, booktitle = {Functional Programming: Proceedings of the 1989 Glasgow Workshop}, address = {Fraserburgh, Scotland, August 21--23}, year = {1989}, editor = {Davis, Kei and Hughes, John}, series = {Workshops in Computing}, publisher = {Springer, Berlin}, pages = {287--295}, abstract = {In this paper we introduce a new way of expressing non-determinism functionally. Our approach is unsurprising --- we simply add sets of possible value as a new datatype --- yet it avoids many of the pitfalls of earlier attempts. We are able to prove theorems about non-deterministic programs using equational reasoning, just as we do in the deterministic case.}, keywords = {Non-Determinism}, } @inproceedings{Hugh85, author = {Hughes, John}, title = {{Strictness Analysis in Non-Flat Domains}}, booktitle = {Programs as Data Objects, Proceedings of a Workshop}, address = {Copenhagen, Denmark, October 17--19}, year = {1985}, volume = {217}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, editor = {Ganzinger, H. and Jones, N. D.}, pages = {112--135}, abstract = {In this paper, a strictness analysis method is introduced which works for functions on non-flat domains.}, keywords = {Strictness Analysis, Contexts}, } @inproceedings{Hugh89b, author = {Hughes, R. J. M.}, title = {{Projections for Polymorphic Strictness Analysis}}, booktitle = {Category Theory and Computer Science}, address = {Manchester, September 5--8}, year = {1989}, editor = {Pitt, D. H. and Rydeheard, D. E. and Dybjer, P. and Pitts, A. M. and Poigne, A.}, volume = {389}, series = {Lecture Notes in Computer Science}, pages = {82--100}, publisher = {Springer, Berlin}, abstract = {We apply the categorical properties of polymorphic functions to compile-time analysis, specifically projection-based strictness analysis. First we interpret parameterized types as functors in a suitable category, and show that they preserve monics and epics. Then we define ``strong'' and ``weak'' polymorphism --- the latter admitting certain projections that are not polymorphic in the usual sense. We prove that, under the right conditions, a weakly polymorphic function is characterized by a single instance. It follows that the strictness analysis of one simple instance of a polymorphic function yields results that apply to all. We show how this theory may be applied. In comparison to earlier polymorphic strictness analysis methods, ours can apply polymorphic information to a particular instance very simply. The categorical approach simplifies our proofs enabling them to be carried out at a higher level, and making them independent of the precise form of the programming language to be analyzed.}, keywords = {Strictness Analysis, Projections, Category Theory}, } @incollection{Hugh90, author = {Hughes, John}, title = {{Compile-time Analysis of Functional Programs}}, booktitle = {Research Topics in Functional Programming}, editor = {Turner, David A.}, publisher = {Addison-Wesley}, address = {Reading, Massachusetts}, year = {1990}, chapter = {5}, pages = {117-154}, abstract = {Good compilers for functional languages increasingly rely on sophisticated compile-time analysis to detect opportunities for optimization. As a result, techniques for performing these analyses are developing very rapidly. In this paper we give an informal introduction to two kinds of analysis technique: forwards and backwards analysis. Forwards analysis, or {\em abstract interpretation\/}, essentially consists of running the program with partial information about its inputs, to derive partial information about its result. This technique has been widely used for a number of different analysis problems. Backwards analysis is used to derive contextual information by ``running the program backwards'': It has an efficiency advantage. We will show how the techniques are applied to first-order functional languages, taking strictness analysis as our principal example, and then we will go on to describe three other applications of backwards analysis. We show how backwards analysis can be extended to analyze data structures. Finally we give some pointers to related work.}, keywords = {Strictness Analysis, Abstract Interpretation, Backwards Analysis}, } @inproceedings{HuLe89, author = {Hurson, A. R. and Lee, B.}, title = {{Hybrid Structure: A Scheme for Handling Data Structuress in a Data Flow Environment}}, booktitle = {{PARLE '89, Parallel Architectures and Languages Europe, Volume I: Parallel Architectures}}, address = {Eindhoven, The Netherlands, June 12--16}, year = {1989}, editor = {Odijk, E. and Rem, M. and Syre, J.-C.}, series = {Lecture Notes in Computer Science}, volume = {365}, publisher = {Springer, Berlin}, pages = {323--340}, abstract = {The asynchronous nature of data flow model of computation allows the exploitation of maximum inherent parallelism in many application programs. However, before data flow model of computation can become a viable alternative to control flow model of computation, one has to find practical solutions to some major problems such as efficient handling of data structures. This article introduces a new model for handling data structures in a data flow environment. The proposed model combines both aspects of copying and sharing to optimize the storage and processing overhead incurred during the operation on data structures. In addition, using simulation, a comparative analysis of our model against other data structure models proposed in literature is presented.}, keywords = {Distributed Data Structures}, } @inproceedings{HuSm86, author = {Hudak, Paul and Smith, Lauren}, title = {{Para-Functional Programming: A Paradigm for Programming Multiprocessor Systems}}, booktitle = {Thirteenth Annual ACM Symposium on Principles of Programming Languages}, address = {St.\ Petersburg Beach, Florida, January 15--16}, year = {1986}, publisher = {ACM Press, New York}, pages = {243--254}, abstract = {One of the most important pragmatic advantages of functional languages is that concurrency in a program is {\em implicit\/} --- there is no need for special constructs to express parallelism as is required in most conventional languages. Furthermore, it is fairly easy for compilers to automatically determine the concurrency as a step toward decomposing a program for execution on a suitable parallel architecture. Yet it is often the case that one knows precisely the {\em optimal decomposition\/} for execution on a particular machine, and one can never expect a compiler to determine such optimal mappings in all cases. This paper is concerned with ways to allow the programmer to {\em explicitly\/} express this mapping of program to machine, by using annotations that, given a few minor constraints, cannot alter the functional semantics of the program. We show through several detailed examples the expressiveness and conciseness of the resulting ``para-functional'' programming methodology, using an experimental language called {\em ParAlfl\/} based on our ideas. We also give a formal denotational description of the mapping semantics using a notion of {\em execution trees\/}.}, keywords = {Para-Functional Programming, Annotations, Process Mappings}, } @inproceedings{HuYo86, author = {Hudak, Paul and Young, Jonathan}, title = {{Higher-Order Strictness Analysis in Untyped Lambda Calculus}}, booktitle = {Thirteenth Annual ACM Symposium on Principles of Programming Languages}, address = {St.\ Petersburg Beach, Florida, January 15--16}, year = {1986}, publisher = {ACM Press, New York}, pages = {97--109}, abstract = {A function is said to be {\em strict\/} in one of its formal parameters if, in all calls to the function, either the corresponding actual parameter is evaluated, or the call does not terminate. Detecting which arguments a function will surely evaluate is a problem that arises often in program transformation and compiler optimization. We present a strategy that allows one to infer strictness properties of functions expressed in the lambda calculus. Our analysis improves on previous work in that (1) a set-theoretic characterization of strictness is used that permits treatment of {\em free variables\/}, which in turn permits a broader range of interpretations, and (2) the analysis provides an effective treatment of higher-order functions. We also prove a result due to Meyr: the problem of first-order strictness analysis is complete in deterministic exponential time. However, because the size of most functions is small, the complexity seems to be tractable in practice.}, keywords = {Strictness Analysis, Abstract Interpretation}, } @inproceedings{IlTh91, author = {Ilmberger Hermann, Th{\"u}rmel, Sabine}, title = {{A Toolkit for Debugging Parallel Lisp Programs}}, booktitle = {PARLE '91, Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms}, address = {Eindhoven, The Netherlands, June 10--13}, year = {1991}, pages = {406--422}, editor = {Aarts, E.H.L. and van Leeuwen, J. and Rem, M.}, publisher = {Springer, Berlin}, volume = {505}, series = {Lecture Notes in Computer Science}, abstract = {As part of the ESPRIT-II project EDS a toolkit (called Delphi) is under development for the debugging of Lisp programs with explicit parallelism being executed on a homogeneous distributed machine. It assists in the detection of functional and synchronisation errors. It also helps to detect unexpected nondeterminacy and sources of poor program performance. Specific mechanisms allow the user to effectively control several processes in a debugging session. The paper introduces the basic concepts behind the tools and how the user may benefit from them.}, keywords = {Lisp, Debugging}, } @inproceedings{ItMa89, author = {Ito, Takayasu and Matsu, Manabu}, title = {{A Parallel Lisp Language PaiLisp and its Kernel Specification}}, booktitle = {Parallel Lisp: Languages and Systems}, address = {Sendai, Japan, June 5--8}, year = {1988}, editor = {Ito, T. and Halstead, R. H.}, volume = {441}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {58--100}, abstract = {Parallel Lisp languages have been proposed and developed for parallel programming of Lisp programs in Artificial Intelligence and Symbolic computing. PaiLisp is a parallel Lisp language based on a shared-memory parallel architecture. PaiLisp has been designed so as to include (1) parallel constructs such as {\tt future} and {\tt pcall} of Multilisp, and {\tt exlambda} for mutual exclusion and {\tt spawn} and {\tt par} for process creation and (2) parallelized Lisp constructs such as parallel conditional expression, parallel mapcar, parallel and/or etc. The first parallel version of PaiLisp, designed in 1986, was based on FranzLisp and the next version was based on Common Lisp. The current version of PaiLisp is based on Scheme. That is, the current version of PaiLisp may be viewed as an extension of Scheme with parallel Lisp constructs mentioned above. In this paper we present (1) the language specification of PaiLisp, (2) PaiLisp-Kernel, which is a compact kernel of PaiLisp, (3) Description of PaiLisp using PaiLisp-Kernel.}, keywords = {Lisp, Futures}, } @inproceedings{Iwas89, author = {Iwasaki, Hideya}, title = {{mUtilisp: a Lisp Dialect for Parallel Processing}}, booktitle = {Parallel Lisp: Languages and Systems}, address = {Sendai, Japan, June 5--8}, year = {1988}, editor = {Ito, T. and Halstead, R. H.}, volume = {441}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {316--321}, abstract = {The mUtilisp (multiprocessing Utilisp) language is a Lisp dialect which allows multiprocessing computation. since it is an extension of the Utilisp (University of Tokyo Interactive Lisp) system, almost all functions of Utilisp are implemented with the same meaning in the mUtilisp system. This paper proposes an aproach to the multiprocessing carried out in the mUtilisp system.}, keywords = {Lisp, Processes}, } @inproceedings{JaPl87, author = {Jayaraman, Bharat and Plaisted, David A.}, title = {{Functional Programming with Sets}}, booktitle = {FPCA '87, Functional Programming Language and Computer Architecture}, address = {Portland, Oregon, USA, September 14--16}, year = {1987}, editor = {Kahn, Gilles}, publisher = {Springer, Berlin}, volume = {274}, series = {Lecture Notes in Computer Science}, pages = {194--211}, abstract = {Set abstraction, originally introduced in functional languages by Turner, is an appealing construct because it leads to concise definitions of many interesting operations. However, existing approaches treat sets as lists for the sake of efficiency, and thereby sacrifice a simple declarative semantics. In this paper, we present a novel language based on sets and equations, where sets are treated as sets, consistent with their semantics. The language is called SEL, for Set-Equational Language. Equations are assumed to define a confluent rewriting system when oriented left to right. Sets are defined in terms of their subsets; these rules define a nonconfluent rewriting system when oriented left to right. We show examples of programs in this language, and provide an operational semantics for such programs. Programs are executed by innermost reduction, which may be nondeterministic or deterministic. Nondeterministic reduction is used when one of the elements of a set is desired. Deterministic reduction is used to simplify a term via an equation or to obtain all the elements of a set. The correctness of the operational semantics is also established.}, keywords = {Non-Determinism, Sets}, } @inproceedings{Johns91, author = {Johnsson, Thomas}, title = {{Parallel Evaluation of Functional Programs: The $\langle\nu,G\rangle$ Approach (Summary)}}, booktitle = {PARLE '91, Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms}, address = {Eindhoven, The Netherlands, June 10--13}, year = {1991}, editor = {Aarts, E. H. L. and van Leeuwen, J. and Rem, M.}, volume = {505}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {1--5}, abstract = {An overview on the abstract parallel graph reduction machine $\langle\nu,G\rangle$ is given.}, keywords = {Parallel Graph Reduction}, } @inproceedings{JoMe89, author = {Jones, Simon B. and Le Metayer, Daniel Le}, title = {{A New Method for Strictness Analysis on Non-Flat Domains}}, booktitle = {Functional Programming: Proceedings of the 1989 Glasgow Workshop}, address = {Fraserburgh, Scotland, August 21--23}, year = {1989}, editor = {Davis, Kei and Hughes, John}, series = {Workshops in Computing}, publisher = {Springer, Berlin}, pages = {1--11}, abstract = {There are two sides of strictness analysis to be investigated: methods for performing the strictness analysis, and exploitation of the results of the analysis. In this paper we shall address the former, in particular in the case of lazily evaluated data structures. Our approach to this problem is novel in that it is based on an abstract domain of very general {\em necessity patterns\/} which allow us to model in great detail the requirements that a function has for the components of the data structures which form its arguments, and to generate finite abstract domains in a systematic way (to enable the computation of fixpoints at compile time), and in a way that can be easily customized for the application. We refer to the analysis using necessity patterns as {\em necessity analysis\/}. This is essentially a form of {\em backwards analysis\/} but carried out in a different framework.}, keywords = {Strictness Analysis, Abstract Interpretation, Backwards Analysis}, } @inproceedings{KaWe89, author = {Katz, Morry and Weise, Daniel}, title = {{Continuing Into the Future: On the Interaction of Futures and First-Class Continuations (A Capsule Summary)}}, booktitle = {Parallel Lisp: Languages and Systems}, address = {Sendai, Japan, June 5--8}, year = {1988}, editor = {Ito, T. and Halstead, R. H.}, volume = {441}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {101--102}, note = {Full paper published in 1990 ACM Conference on Lisp and Functional Programming}, abstract = {One of the nicest features of the {\em future\/} construct originally presented in Multilisp is its near orthogonality with respect to a functional subset of Scheme. Introducing futures into most functional programs does not affect the value returned, even though the parallel execution order might differ from the sequential. When futures and continuations are used in the same program, however, parallel and sequential executions can yield different results. No existing implementation of futures has yet addressed this issue. We make futures and continuations interact properly through a simple, yet important, change to the implementation of the future construct. This change causes a second problem to manifest itself: the creation of extraneous computation threads. The second problem is addressed by making an additional change to the future construct.}, keywords = {Lisp, Futures, Continuations}, } @inproceedings{KeGl89, author = {Kewley, John M. and Glynn, Kevin}, title = {{Evaluation Annotations for Hope+}}, booktitle = {Functional Programming: Proceedings of the 1989 Glasgow Workshop}, address = {Fraserburgh, Scotland, August 21--23}, year = {1989}, editor = {Davis, Kei and Hughes, John}, series = {Workshops in Computing}, publisher = {Springer, Berlin}, pages = {329--337}, abstract = {To fully exploit the parallelism of the Flagship Machine it is desirable to be able to experiment with a variety of evaluation strategies. The ability to control the behavior of individual functions via annotations is of enormous help in understanding the behavior of a parallel system and permits the comparison of ``lazy'' and ``eager'' versions of languages as well as providing the opportunity to intermix the two evaluation orders. The primary functional language used by the Flagship project is Hope+. Hope+ has a mixed evaluation strategy, with strict function application combined with lazy data constructors. This can result in both unnecessary evaluation and loss of parallelism. Annotations enable user-control of the evaluation strategy so that such problems are avoided.}, keywords = {Para-Functional Programming, Annotations}, } @inproceedings{Kell80, author = {Keller, Robert M.}, title = {{Divide and CONCer: Data Structuring in Applicative Multiprocessing Systems}}, booktitle = {1980 LISP Conference}, pages = {196--202}, address = {Stanford, California, August 25--27}, year = {1980}, abstract = {The conc representation of lists in implementations of applicative languages is introduced. This representation is based on an operator conc which supplements the usual cons, the representation itself being able to coexist with the conventional nested-pair representation. Advantages of the conc representation are presented which relate to multiprocessing and conventional systems. Qualitative comparison with other compact list representations is made. The conc representation exploits demand-driven evaluation and provides further justification for the ``tagged-data'' approach.}, keywords = {Lisp, Distributed Data Structures}, } @book{Kell89, author = {Kelly, Paul}, title = {{Functional Programming for Loosely-coupled Multiprocessors}}, publisher = {Pitman, London}, year = {1989}, series = {Research Monographs in Parallel and Distributed Computing}, abstract = {The author's Ph.D.\ thesis gives an extensive overview on the state of the art in (parallel) functional programming and describes several techniques for the construction of parallel functional programs. The para-functional programming language Caliban is introduced that allows the declarative description of processor networks and the mapping of processes to processors.}, keywords = {Para-Functional Languages, Process Mapping, Streams}, } @inproceedings{KeSw89, author = {Kessler, Robert R. and Swanson, Mark R.}, title = {{Concurrent Scheme}}, booktitle = {Parallel Lisp: Languages and Systems}, address = {Sendai, Japan, June 5--8}, year = {1988}, editor = {Ito, T. and Halstead, R. H.}, volume = {441}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {200--234}, abstract = {This paper describes an evolution of the Scheme language to support parallelism with tight coupling of control and data. Mechanisms are presented to address the difficult and related problem of mutual exclusion and data sharing which arise in concurrent language systems. The mechanisms are tailored to preserve Scheme semantics as much as possible while allowing for efficient implementation. Prototype implementations of the resulting language are described which have been completed. A third implementation is underway for the Mayfly, a distributed memory, twisted-torus communication topology, parallel processor, under development at the Hewlett-Packard Research Laboratories. The language model is particularly well-suited for the Mayfly processor, as will be shown.}, keywords = {Lisp, Threads}, } @inproceedings{KHM89a, author = {Kranz, David A. and {Halstead, Jr.}, Robert H. and Mohr, Eric}, title = {{Mul-T: A High-Performance Parallel Lisp (Extended Abstract)}}, booktitle = {Parallel Lisp: Languages and Systems}, address = {Sendai, Japan, June 5--8}, year = {1988}, editor = {Ito, T. and Halstead, R. H.}, volume = {441}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {306--311}, abstract = {Mul-T is a parallel Lisp system that has been developed to run on an Encore Multimax processor. Mul-T is an extended version of the T version 3 (or ``T3'') system that supports parallel processing using Multilisp's {\tt future} construct. Multilisp's implementation uses a layer of interpretation that limits its speed, but Mul-T uses T3's ORBIT compiler (suitably modified) to generate native code for the Multimax's NS32332 processors, leading to a dramatic increase in speed (about a factor of 100 over the Multilisp system).}, keywords = {Lisp, Futures}, } @inproceedings{KuMi89, author = {Kuo Tsung-Min and Mishra, Prateek}, title = {{Strictness Analysis: A New Perspective Based on Type Inference}}, booktitle = {{FPCA '89, Functional Programming Languages and Computer Architecture}}, address = {London, UK, September 11--13}, year = {1989}, publisher = {ACM Press, New York}, abstract = {In this work we develop a new framework for strictness analysis. We provide a new definition of strictness based on operational semantics which directly addresses the primary aspect of the strictness analysis problem: non-termination of evaluation. Our definition excludes other irrelevant details such as the type system of the language, and imposes minimal constraints on semantic equality of expressions. We provide a new syntactic representation for strictness properties of programs and a new computational technique for strictness analysis. The syntactic representation takes the from of a simple type language for expressing strictness properties and is much simpler than representations used in previous work. The computational technique is based on well-understood type inference techniques and improves on previous work as it does not require fixpoint iteration. Our framework is parameterized with respect to the language of strictness properties and type inference techniques. As improvements in computational methods become available, both the language and type inference technique can be naturally extended to more complex and accurate strictness analysis.}, keywords = {Strictness Analysis}, } @incollection{KPB*90, author = {Kurfe{\ss}, F. and Pandolfi, X. and Belmesk, Z. and Ertel, W. and Letz, R. and Schumann, J.}, title = {{PARTHEO and FP2: Design of a Parallel Inference Machine}}, booktitle = {Parallel Computers --- Object-Oriented, Functional, Logic}, editor = {Treleaven, P. C.}, publisher = {John Wiley {\&} Sons}, series = {Series in Parallel Computing}, address = {Chichester}, year = {1990}, chapter = {9}, pages = {259--297}, abstract = {The language FP2 provides a simple and consistent set of constructs for the description of parallel systems. Such a parallel system is seen as a network of concurrent communicating processes which, apart from their specified interconnections, are independent. Computations to be performed are expressed in the form of a functional specification of the behavior of processes via rewrite rules; communication consists of the exchange of information between processes trough ports with an extended rendezvous mechanism based on unification.}, keywords = {FP2, Process Networks}, } @inproceedings{LCD*86, author = {Lemaitre, M. and Castan, M. and Durand, M.-H. and Durrieu, G. and Lecussan, B.}, title = {{Mechanisms for Efficient Multiprocessor Combinator Reduction}}, booktitle = {1986 ACM Conference on Lisp and Functional Programming}, address = {Cambridge, Massachusetts, August 4--6}, year = {1986}, publisher = {ACM Press, New York}, pages = {113--121}, abstract = {We are currently designing a multiprocessor architecture for a parallel reduction machine named MaRS, based on a combinator machine language. Since the seminal papers, several projects and studies close to our own have appeared, such as the SKIM2 processor, the DAPS model, the COBWEB project. Other studies like the rediflow multiprocessor or the Multilisp experiments, although involving different hypotheses, are worth considering in this context. So, this paper will just describe briefly the MaRS machine, and focus on more original features which, as far as we know, do not appear in other projects.}, keywords = {Parallel Graph Reduction, Combinators}, } @inproceedings{LiMu89, author = {Livezey, Brian K. and Muntz, Richard R.}, title = {{ASPEN: A Stream Processing Environment}}, booktitle = {{PARLE '89, Parallel Architectures and Languages Europe, Volume I: Parallel Architectures}}, address = {Eindhoven, The Netherlands, June 12--16}, year = {1989}, editor = {Odijk, E. and Rem, M. and Syre, J.-C.}, series = {Lecture Notes in Computer Science}, volume = {365}, publisher = {Springer, Berlin}, pages = {374--388}, abstract = {In this paper, we describe ASPEN, a concurrent stream processing environment. ASPEN is novel in that it provides a programming model in which programmers use simple annotations to exploit varying degrees and types of concurrency. The degree of concurrency to be exploited is not fixed by the program specification or by the underlying system. Increasing or decreasing the degree of concurrency to be exploited during execution does not require rewriting the entire program, but rather, simply re-annotating it. Examples are given to illustrate the varying types of concurrency inherent in programs written within the stream processing paradigm. We show how programs may be annotated to exploit these varying degrees of concurrency. We briefly describe our implementation of ASPEN.}, keywords = {Para-Functional Programming, Annotations, Streams}, } @inproceedings{LSF88, author = {Lee, Ching-Cheng and Skedzielewski, Stephen and Feo, John}, title = {{On the Implementation of Applicative Languages on Shared-Memory, MIMD Multiprocessors}}, booktitle = {{PPEALS 1988, Parallel Programming: Experience with Applications, Languages and Systems}}, address = {New Haven, Conneticut, July 19--21}, year = {1988}, series = {SIGPLAN Notices}, number = {23(9)}, month = {September}, publisher = {ACM Press, New York}, pages = {188-197}, abstract = {This paper presents the performance of a set of algorithms written in {\sc Sisal} and run on multiprocessor Sequent, DEC, and Cray computers. We describe our current runtime system and discuss its implementation on each machine. We indicate where our automatic approach to parallelization works well, as well as sources of inefficient behavior. Overall we find our systems encouraging for the first release of the native-code generating software. We suggest improvements to the compiler and runtime systems, many already developed but not yet implemented, to alleviate the inefficiencies.}, keywords = {SISAL, Algorithms}, } @book{Loog90, author = {Loogen, Rita}, title = {{Parallele Implementierung Funktionaler Programmiersprachen (Parallel Implementation of Functional Programming Languages) (in German)}}, series = {Informatik Fachberichte}, number = {232}, publisher = {Springer, Berlin}, year = {1990}, abstract = {The author's Ph.D.\ thesis describes the implementation of a lazy functional language on a transputer network by parallel graph reduction. The book contains an extensive section on the formal framework of compilation e.g.\ on lambda-lifting and on strictness analysis by evaluation transformers.}, keywords = {Strictness Analysis, Evaluation Transformers, Parallel Graph Reduction}, } @inproceedings{Mart80, author = {Marti, Jed B.}, title = {{Compilation Techniques for a Control-Flow Concurrent Lisp System}}, booktitle = {1980 LISP Conference}, pages = {203--207}, address = {Stanford, California, August 25--27}, year = {1980}, abstract = {Described is a strategy for the compilation of LISP programs for a concurrent processing system in the presence of global side effects. The method supports ``horizontal'' concurrency, the concurrency available when two arguments of a function can be evaluated simultaneously and without violating the semantics of sequential LISP. The method works for Standard LISP and is not restricted to ``pure'' LISP. Conventional programs may usually be compiled without modification.}, keywords = {Lisp, Parallelization, Compilation}, } @inproceedings{MaSu89, author = {Marino, Giuseppe and Succi, Giancarlo}, title = {{Data Structures for Parallel Execution of Functional Languages}}, booktitle = {{PARLE '89, Parallel Architectures and Languages Europe, Volume I: Parallel Architectures}}, address = {Eindhoven, The Netherlands, June 12--16}, year = {1989}, editor = {Odijk, E. and Rem, M. and Syre, J.-C.}, series = {Lecture Notes in Computer Science}, volume = {365}, publisher = {Springer, Berlin}, pages = {346--356}, abstract = {After a short review of some data structures proposed by traditional functional languages, some requirements that a data structuring primitive should meet for suitable implementation on parallel architectures are introduced; the drawbacks of the classic {\em list\/} data structure are evidenced and consequently two alternative structures are proposed; the first is based on unordered collection of objects (and hereafter called {\em bag\/}); its formal definition is given and the non-determinism of the related primitive operators are discussed; the second, {\em limited function\/}, is a way of defining functions over finite and countable domains; its significant implications, mainly related with parallel architectures, are described. Examples of programs based on these concepts are integrated within the framework of an existing functional language are proposed and properties about the primitives for manipulating unordered collections of objects are stated and proved in Appendix.}, keywords = {Distributed Data Structures, Non-Determinism}, } @inproceedings{Maur85, author = {Maurer, Dieter}, title = {{Strictness Computation Using Special $\lambda$-Expressions}}, booktitle = {Programs as Data Objects, Proceedings of a Workshop}, address = {Copenhagen, Denmark, October 17--19}, year = {1985}, volume = {217}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, editor = {Ganzinger, H. and Jones, N. D.}, pages = {136--155}, abstract = {In order to exploit the implicit parallelism in demand driven functional programs the inference of information about the strictness of user defined functions is helpful. This article extends results of Mycroft about strictness detection in first order programs to higher order programs. Information about the strictness of higher order functions is represented by special $\lambda$-expressions, so called need expressions. A program over $\lambda$-expressions is translated into a program over need expressions by interpreting the constants as closed need expressions. After a suitable approximation --- essentially a partial typing --- expressions are computed by an iterative method allowing to derive strictness information for the functions defined in the original program.}, keywords = {Strictness Analysis}, } @inproceedings{McSh80, author = {McKay, Donald P. and Shapiro, Stuart C.}, title = {{MULTI --- A LISP Based Multiprocessing System}}, booktitle = {1980 LISP Conference}, pages = {29--37}, address = {Stanford, California, August 25--27}, year = {1980}, abstract = {A package of LISP functions, collectively called MULTI, which extends LISP 1.5 to multiprogramming is presented. MULTI defines the notion of a process within a LISP implementation using function invocation as the only control primitive. A process is an executable entity consisting of a process template and a set of register values. The process template defines the operations the process carries out. Process environments are saved in what can be viewed as function call instances, i.e.\ LISP forms which have the name of a process template in functional position and the register values following it. The flexibility of this simple conceptualization of processes is demonstrated by several examples which use MULTI to implement recursion, backtracking, generators, agendas and AND/OR graph searching. The implementation of MULTI does not assume that the host LISP system provides any data or control environment saving mechanisms such as funarg or Interlisp's spaghetti stack. Thus, MULTI is portable to other LISP systems. }, keywords = {LISP}, } @inproceedings{Mode80, author = {Model, Mitchell L.}, title = {{Multiprocessing via Intercommunicating Lisp Systems}}, booktitle = {1980 LISP Conference}, pages = {188--195}, address = {Stanford, California, August 25--27}, year = {1980}, abstract = {Multiprocess environments comprising several intercommunicating LISP systems are straightforward to implement due to certain fundamental characteristics of the LISP language. Experiences with four methods of establishing the necessary communications linkages are described. The features of LISP which support experimentation with interprocess communication are identified. Two key characteristics of the language are important in this regard: 1. LISP programs can construct and interpret new code as they run; 2. Structures within LISP systems are accessible by name. The most flexible of the communication methods use only the ordinary LISP input and output functions, supplemented by a small amount of system-dependent code to create communication linkages that can be treated by LISP as file structures.}, keywords = {Lisp}, } @inproceedings{MoSw80, author = {Morris, F. Lockwood and Schwarz, Jerald S.}, title = {{Computing Cyclic List Structures}}, booktitle = {1980 LISP Conference}, pages = {144--153}, address = {Stanford, California, August 25--27}, year = {1980}, abstract = {It is argued that list structures containing cycles are useful and unobjectionable Lisp entities. If this is so, it is desirable to have a means of computing them less foreign to the equational-definition style characteristic of Lisp than are the list-structure-altering primitives {\em rplaca\/} and {\em rplacd\/}. A notion is developed of a reasonable system of mutually recursive equations, guaranteed to have a unique solution is list structures. The notion is given in termis of the computations invoked by the equations, without reference to the forms of expressions appearing in them. A variety of programming examples are presented, including a curious implementation of the Knuth-Morris-Pratt string matching algorithm. Two methods of implementing the recursive definition facility are discussed.}, keywords = {Circular Programs, Streams}, } @inproceedings{MSWY87, author = {Michelson, R. and Smith, L. and Williams, E. and Yantis, B.}, title = {{Parallel Graph Reduction on a Supercomputer: A Status Report}}, booktitle = {Graph Reduction: Proceedings of a Workshop}, address = {Santa Fe, New Mexico, September 29 -- October 1}, year = {1986}, volume = {279}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {114--118}, editor = {Fasel, Joseph H. and Keller, Robert M.}, abstract = {We describe an ongoing effort to develop a parallel graph reduction run-time system hosted on a multiprocessor supercomputer. This run-time system is presented augmented by the functional language compiler of the ALFALA system. Admittedly, parallel graph reduction is hardly a novel idea. The interesting notion is the provision of a parallel execution environment sufficiently powerful to support development of large prototypical scientific and symbolic codes in a functional language. This will allow the investigation of the functional programming paradigm within these application domains in an empirical fashion. In this paper, we discuss the motivation for the effort, describe the basic elements of the implementation, and provide some preliminary insight distilled from our experience with an initial version of the runtime system.}, keywords = {Parallel Graph Reduction, Runtime System}, } @inproceedings{MyJo85, author = {Mycroft, Alan and Jones, Neil D.}, title = {{A Relational Framework for Abstract Interpretation}}, booktitle = {Programs as Data Objects, Proceedings of a Workshop}, address = {Copenhagen, Denmark, October 17--19}, year = {1985}, volume = {217}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, editor = {Ganzinger, H. and Jones, N. D.}, pages = {156--171}, abstract = {Abstract interpretation is a very general framework for proving certain properties of programs. This is done by interpreting the symbols of the program, or the symbols of a denotational metalanguage translation, in two different ways (the standard interpretation and the abstract interpretation) and relating them. We set up a new framework for abstract interpretation based on relations (with the intent of inclusive or logical relations). This avoids problems with power domains and enables certain higher-order frameworks to be proved correct. As an example we show how the Hindley/Milner type system can be viewed as a special case of our system and is thus automatically correct.}, keywords = {Abstract Interpretation}, } @inproceedings{Niel89, author = {Nielson, Flemming}, title = {{The Typed $\lambda$-Calculus with First-Class Processes}}, booktitle = {{PARLE '89, Parallel Architectures and Languages Europe, Volume I: Parallel Architectures}}, address = {Eindhoven, The Netherlands, June 12--16}, year = {1989}, editor = {Odijk, E. and Rem, M. and Syre, J.-C.}, series = {Lecture Notes in Computer Science}, volume = {365}, publisher = {Springer, Berlin}, pages = {357--373}, abstract = {We extend the typed $\lambda$-calculus with CCS- or CSP-like processes and allow these to be first-class citizens just as functions are first-class citizens in functional languages. The main novel feature of the language is the use of {\em types\/} to record the {\em communication possibilities\/} possessed by processes and in this we give up the {\em causality\/} between communications, i.e.\ the types do not model whether or not one communication may takeplace before another. In analogy with the semantics of the $\lambda$-calculus, and of CCS, we develop a structural operational semantics for the language. We then prove that the operational semantics preserves the types and we use this to give examples of `errors' that cannot arise for well-typed programs.}, keywords = {Lambda Calculus, Processes, Semantics}, } @inproceedings{NSEP91, author = {N{\"o}cker, E. G. J. M. H. and Smetsers, J. E. W. and Eekelen, M. C. J. D. and Plasmeijer, M. J.}, title = {{Concurrent Clean}}, booktitle = {PARLE '91, Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms}, address = {Eindhoven, The Netherlands, June 10--13}, year = {1991}, editor = {Aarts, E. H. L. and van Leeuwen, J. and Rem, M.}, volume = {505}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {202--219}, abstract = {Concurrent Clean is an experimental, lazy, higher-order parallel functional programming language based on term graph rewriting. An important difference with other languages is that in Clean graphs are manipulated and not terms. This can be used by the programmer to control communication and sharing of computation. Cyclic structures can be defined. Concurrent Clean furthermore allows to control the (parallel) order of evaluation to make efficient evaluation possible. With help of sequential annotations the default lazy evaluation can locally be changed into eager evaluation. The language enables the definition of partially strict data structures which make a whole new class of algorithms feasible in a functional language. A powerful and fast strictness analyzer is incorporated in the system. The quality of the code generated by the Clean compiler has been greatly improved such that it is one of the best code generators for a lazy functional language. Two very powerful parallel annotations enable the programmer to define concurrent functional programs with arbitrary process topologies. Concurrent Clean is set up in such a way that the efficiency achieved for the sequential case can largely be maintained for a parallel implementation on loosely coupled parallel machine architectures.}, keywords = {Para-Functional Programming, Annotations, Strictness Analysis}, } @inproceedings{Osbo89, author = {Osborne, Randy B.}, title = {{Speculative Computation in Multilisp}}, booktitle = {Parallel Lisp: Languages and Systems}, address = {Sendai, Japan, June 5--8}, year = {1988}, editor = {Ito, T. and Halstead, R. H.}, volume = {441}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {103--137}, abstract = {We demonstrate by experiments that performing computations in parallel before their results are known to be required can yield performance improvements over conventional approaches to parallel computing. We call such eager computation of expressions {\em speculative\/} computation, as opposed to conventional {\em mandatory\/} computation that is used in almost all contemporary parallel programming languages and systems. The two major requirements for speculative computation are: 1) a means to control computation to favor the most promising computation and 2) a means to abort computation and reclaim computation resources. We discuss these requirements in the parallel symbolic language Multilisp and present a {\em sponsor model\/} for speculative computation in Multilisp which handles control and reclamation of computation in a single, elegant framework. We describe an implementation of this sponsor model and present performance results for several applications of speculative computation. The results demonstrate that our support for speculative computation adds expressive and computational power to Multilisp, with observed performance improvement as great as 26 times over conventional approaches to parallel computation.}, keywords = {Lisp, Speculative Parallelism}, } @inproceedings{PeWe89, author = {Pehoushek, Joseph D. and Weening, Joseph S.}, title = {{Low-Cost Process Creation and Dynamic Partitioning in Qlisp}}, booktitle = {Parallel Lisp: Languages and Systems}, address = {Sendai, Japan, June 5--8}, year = {1988}, editor = {Ito, T. and Halstead, R. H.}, volume = {441}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {182--199}, abstract = {Our experiments with Qlisp have lead to two ways of improving the performance of parallel Lisp programs. One is to reduce the cost of process creation and scheduling; the other is to use a dynamic partitioning and scheduling method. We describe these techniques and present the results of several experiments that use them. We also present an analysis of the dynamic partitioning method to explain the reasons for its success.}, keywords = {Lisp, Process Creation, Scheduling}, } @inproceedings{PCS89, author = {Peyton Jones, S. L. and Clack, C. and Salkid, J.}, title = {{High-Performance Parallel Graph Reduction}}, booktitle = {{PARLE '89, Parallel Architectures and Languages Europe, Volume I: Parallel Architectures}}, address = {Eindhoven, The Netherlands, June 12--16}, year = {1989}, editor = {Odijk, E. and Rem, M. and Syre, J.-C.}, series = {Lecture Notes in Computer Science}, volume = {365}, publisher = {Springer, Berlin}, pages = {193--206}, abstract = {Parallel graph reduction is an attractive implementation for functional programming languages becaue of its simplicity and inherently distributed nature. This paper outlines some of the issues raised by parallel compiled graph reduction, and presents the approach we have adopted for our parallel machine, GRIP. We concentrate on two main areas: Static and dynamic techniques to control the growth of parallelism, so as to provide enough parallelism of an appropriate granularity to keep the machine busy without swamping it. Dynamic techniques to exploit the memory hierarchy, so that frequently-referenced data is held near to the processor that references it.}, keywords = {Parallel Graph Reduction, Growth of Parallelism}, } @book{Peyt87, author = {Peyton Jones, Simon L.}, title = {{The Implementation of Functional Programming Languages}}, publisher = {Prentice-Hall}, series = {International Series in Computer Science}, address = {New York}, year = {1987}, abstract = {This standard work on the implementation of functional languages by graph reduction also contains a section on parallel graph reduction discussing the issues of conservative/speculative parallelism, task granularity and task locality.}, keywords = {Parallel Graph Reduction}, } @article{Peyt92, author = {Peyton Jones, Simon L.}, title = {{Implementing Lazy Functional Languages on Stock Hardware: The Spineless Tagless G-machine}}, journal = {Journal of Functional Programming}, volume = {2}, number = {2}, pages = {127--202}, month = {April}, year = {1992}, abstract = {The Spineless Tagless G-Machine is an abstract machine designed to support 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 {\em STG language\/}, an austere but recognizably-functional language, which as well as a {\em denotational\/} meaning has a well-defined {\em 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.}, keywords = {Parallel Graph Reduction, Abstract Machine}, } @incollection{Ping90, author = {Pingali, Keshav K.}, title = {{Lazy Evaluation and the Logic Variable}}, booktitle = {Research Topics in Functional Programming}, editor = {Turner, David A.}, publisher = {Addison-Wesley}, address = {Reading, Massachusetts}, year = {1990}, chapter = {7}, pages = {171-198}, abstract = {Functional languages can be enriched with logic variables to provide new computational features such as incremental construction of data structures. In this paper, we present a novel application for logic variables that highlights their importance: we argue that they are essential for efficient implementations of functional languages. This point is made by demonstrating that logic variables are required for explicating the process of demand propagation in lazy evaluation of functional programs. There are two applications of this result. For dataflow researchers, it offers a simple and efficient implementation of laziness on dataflow machines. For researchers investigating lazy graph reduction, it suggests new strictness analysis algorithms in which logic variables play an important role.}, keywords = {Logic Variables, Strictness Analysis}, } @inproceedings{Prin80, author = {Prini, G.}, title = {{Explicit Parallelism in LISP-like Languages}}, booktitle = {1980 LISP Conference}, pages = {13--18}, address = {Stanford, California, August 25--27}, year = {1980}, abstract = {We introduce a LISP-like language whose parameter passing mechanism and control primitives allow for the creation and the synchronization of an arbitrary number of concurrent computations. The parameter passing mechanism is a parallel version of call-by-need: an argument of a function is evaluated only the first time the value of the corresponding formal parameter is needed during the evaluation of the function body, but such an evaluation is only {\em initiated\/} by-need and is then performed in parallel with all the other computations. Some primitives allow the user to initiate new computations {\em explicitly\/} and to check/wait for the termination of already initiated computations. Several examples illustrate how classical problems in multiprogramming have natural and elegant solutions using parallel call-by-need and the above mentioned primitives.}, keywords = {Lisp, Parallel Lazy Evaluation, Streams}, } @inproceedings{Roe89, author = {Roe, Paul}, title = {{Some Ideas on Parallel Functional Programming}}, booktitle = {Functional Programming: Proceedings of the 1989 Glasgow Workshop}, address = {Fraserburgh, Scotland, August 21--23}, year = {1989}, editor = {Davis, Kei and Hughes, John}, series = {Workshops in Computing}, publisher = {Springer, Berlin}, pages = {338--352}, abstract = {This paper argues that parallel functional programs must be efficient in order to achieve speed-up on parallel machines. This to end parallelism expression and parallelism efficiency are discussed. Different classes of parallel algorithms and their expression are considered, along with two particular sources of inefficiency: task size and expression re-evaluation}, keywords = {Parallel Functional Programming}, } @inproceedings{SaHe86, author = {Sarkar, Vivek and Hennessy, John}, title = {{Compile-time Partitioning and Scheduling of Parallel Programs}}, booktitle = {{SIGLAN '86 Symposium on Compiler Construction}}, address = {Palo Alto, California, June 25--27}, series = {SIGPLAN NOTICES}, volume = {21(7)}, pages = {17--26}, year = {1986}, publisher = {ACM Press, New York}, abstract = {Partitioning and scheduling techniques are necessary to implement parallel languages on multiprocessors. Multiprocessor performance is maximized when parallelism between tasks is optimally traded off with communication and synchronization overhead. We present compile-time partitioning and scheduling techniques to achieve this tradeoff.}, keywords = {Scheduling, Partitioning}, } @inproceedings{Sand89, author = {Sands, David}, title = {{Complexity Analysis for a Lazy Higher-Order Language}}, booktitle = {Functional Programming: Proceedings of the 1989 Glasgow Workshop}, address = {Fraserburgh, Scotland, August 21--23}, year = {1989}, editor = {Davis, Kei and Hughes, John}, series = {Workshops in Computing}, publisher = {Springer, Berlin}, pages = {56--79}, abstract = {This paper is concerned with the time-analysis of functional programs. Techniques which enable us to reason formally about a program's execution costs have had relatively little attention in the study of functional programming. We concentrate here on the construction of equations which compute the time-complexity of expressions in a lazy higher-order language. The problem with higher-order functions is that complexity is dependent on the cost of applying functional parameters. Structures called {\em cost closures\/} are introduced to allow us to model both functional parameters {\em and\/} the cost of their application. The problem with laziness is that complexity is dependent on {\em context\/}. Projections are used to characterise the context in which an expression is evaluated, and cost-equations are parameterized by this context-description to give a compositional time-analysis. Using this form of context information we introduce two types of time-equation: {\em sufficient-time\/} equations and {\em necessary-time\/} equations, which together provide bounds on the exact time-complexity.}, keywords = {Granularity Analysis}, } @incollection{Sked91, author = {Skedzielewski, Stephen K.}, title = {{Sisal}}, booktitle = {Parallel Functional Languages and Compilers}, editor = {Szymanski, Boleslaw K.}, publisher = {ACM Press}, address = {New York}, year = {1991}, series = {Frontier Series}, chapter = {4}, pages = {105--158}, abstract = {The Sisal language is designed to be a notation for expressing solutions to large-scale scientific problems. In contrast to conventional {\em imperative\/} languages, Sisal belongs to a class of languages called {\em applicative languages\/}. This chapter describes Sisal Version 1.2 which is described in the reference manual dated March, 1985. This chapter does not attempt to describe {\em all\/} the features of Sisal. Rather, it will use a subset of the language as it attempts to motivate the use of Sisal in writing programs to exploit parallel computers.}, keywords = {Dataflow, Sisal}, } @book{Szym91, editor = {Szymanski, Boleslaw K.}, title = {{Parallel Functional Languages and Compilers}}, publisher = {ACM Press}, address = {New York}, year = {1991}, series = {Frontier Series}, abstract = {A collection of articles on parallel implementations of functional languages.}, keywords = {Parallel Functional Programming}, } @inproceedings{Take89, author = {Takeuchi, Ikuo}, title = {{Concurrent Programming in TAO --- Practice and Experience}}, booktitle = {Parallel Lisp: Languages and Systems}, address = {Sendai, Japan, June 5--8}, year = {1988}, editor = {Ito, T. and Halstead, R. H.}, volume = {441}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {271--291}, abstract = {This paper describes various aspects of the concurrent programming in the Lisp language and related problems, based on our practice and experience with a concurrent Lisp dialect TAO. TAO realizes a multiple process and multiple user environment of practical performance and significance on a single ELIS processor by its powerful concurrent primitives. Topics described in this paper include: a Lisp-style process management, sharing Lisp programs among processes and users, name space problems around symbol packages, concurrent primitives, concurrent program debugging, and some performance figures. Further extension of TAO towards to a multiple ELIS processor system is also discussed briefly.}, keywords = {Lisp}, } @incollection{Thom90, author = {Thompson, Simon}, title = {{Interactive Functional Programs}}, booktitle = {Research Topics in Functional Programming}, editor = {Turner, David A.}, publisher = {Addison-Wesley}, address = {Reading, Massachusetts}, year = {1990}, chapter = {10}, pages = {249-286}, abstract = {In this chapter, we present a model of interactive programs in a purely functional style. We exploit lazy evaluation in the modeling of streams as lazy lists. We show how programs may be constructed in an {\em ad hoc\/} way, and then we present as small set of interactions and combinators that form the basis for a disciplined approach to writing such programs. One of the difficulties of the {\em ad hoc\/} approach is that the way in which input and output are interleaved by the functions can be unpredictable. In the second half of the paper we use traces, i.e., partial histories of behavior, to explain the interleaving of input and output, and we give a formal explanation of our combinators. We argue that this justifies our claim that the combinators have the intuitively expected behavior, and finally, we contrast our approach with another.}, keywords = {Process Networks, Streams, Non-determinism}, } @book{Trau91, author = {Traub, Kenneth R.}, title = {{Implementation of Non-Strict Functional Programming Languages}}, series = {Research Monographs in Parallel and Distributed Computing}, publisher = {Pitman, London}, year = {1991}, abstract = {The authors' Ph.D.\ thesis introduces a new view on the compilation of functional languages with lenient (i.e.\ dataflow) semantics. The central task of the compiler is to partition a program into a set of sequential threads that execute sequentially and are scheduled by the runtime system. The details of the program analysis and the generation of the target code are described in large detail.}, keywords = {Lenient Evaluation, Functional Quads, Dependence Analysis}, } @inproceedings{Turn87, author = {Turner, David}, title = {{Functional Programming and Communicating Processes}}, booktitle = {PARLE '87 Parallel Architectures and Languages Europe, Volume 2: Parallel Languages}, address = {Eindhoven, The Netherlands, June 15--19}, year = {1987}, volume = {259}, editor = {de Bakker, J. W. and Nijman, A. J. and Treleaven, P. C.}, series = {Lecture Notes in Computer Science}, publisher = {Springer, Berlin}, pages = {54--74}, abstract = {This paper reports some of the initial results of a research project at the University of Kent for the construction of an operating system written entirely in a functional language. We are here primarily concerned with the internal structure of the operating system, seen as a network of communicating processes. The description in purely functional terms of such a network has until recently posed logical problems, a solution to which was proposed by W.\ Stoye in 1984. We have developed a refinement of Stoye's model which has stronger synchronization properties and permits each process to run in a separate address space, facilitating a distributed implementation. By introducing the concept of a wrapper-function, we enable message passing code to be statically type checked.}, keywords = {Operating System, Process Networks, Streams, Non-determinism}, } @incollection{Turn90, author = {Turner, David}, title = {{An Approach to Functional Operating Systems}}, booktitle = {Research Topics in Functional Programming}, editor = {Turner, David A.}, publisher = {Addison-Wesley}, address = {Reading, Massachusetts}, year = {1990}, chapter = {8}, pages = {199-218}, abstract = {This chapter reports some of the initial results of a research project at the University of Kent for the construction of an operating system written entirely in a functional language. We are here primarily concerned with the internal structure of the operating system, seen as a network of communicating processes. The description in purely functional terms of such a network has until recently posed logical problems, a solution to which was proposed by W.\ Stoye in 1984. We have developed a refinement of Stoye's model which has stronger synchronization properties and permits each process to run in a separate address space, facilitating a distributed implementation. By introducing the concept of a wrapper-function, we enable message passing code to be statically type checked.}, keywords = {Operating System, Process Networks, Streams, Non-determinism}, } @book{WaAs85, author = {Wadge, William W. and Ashcroft, Edward A.}, title = {{Lucid, the Dataflow Programming Language}}, publisher = {Academic Press}, address = {London}, series = {A.P.I.C. Studies in Data Processing}, number = {22}, year = {1985}, abstract = {An extensive description of dataflow programming in Lucid.}, keywords = {Dataflow, Lucid}, } @inproceedings{Wand80, author = {Wand, Mitchell}, title = {{Continuation-Based Multiprocessing}}, booktitle = {1980 LISP Conference}, pages = {19--28}, address = {Stanford, California, August 25--27}, year = {1980}, abstract = {Any multiprocessing facility must include three features: elementary exclusion, data protection, and process saving. While elementary exclusion must rest on some hardware facility (e.g.\ a test-and-set instruction), the other two requirements are fulfilled by features already presented in applicative languages. Data protection may be obtained through the use of procedures (closures or funargs), and process saving may be obtained through the use of the CATCH operator. The use of CATCH, in particular, allows an elegant treatment of process saving. We demonstrate these techniques by writing the kernel and some modules for a multiprocessing system. The kernel is very small. Many functions which one would normally expect to find inside the kernel are completely decentralized. We consider the implementation of other schedulers, interrupts and the implications of these ideas for language design.}, keywords = {Lisp, Continuations, Operating Systems}, } @article{Wegb75, author = {Wegbreit, Ben}, title = {{Mechanical Program Analysis}}, journal = cacm, volume = {18}, number = {9}, pages = {528--539}, month = {September}, year = {1975}, abstract = {One means of analyzing program performance is by deriving closed-form expressions for their execution behavior. This paper discusses the mechanization of such analysis, and describes a system, Metric, which is able to analyze simple Lisp programs and produce, for example, closed-form expressions for their running time expressed in terms of size of input. This paper presents the reasons for mechanizing program analysis, describes the operation of Metric, explains its implementation, and discusses its limitations.}, keywords = {Granularity Analysis}, } @article{Koor93, author = {Koorey Willcock, Diane M.}, title = {{Tlisp: A Concurrent Lisp for the Transputer}}, journal = {SIGSAM Bulletin}, volume = {26}, number = {4}, month = {November}, year = {1992}, pages = {15--23}, abstract = {Tlisp is an experimental concurrent lisp based on Xlisp. It is designed to run on an array of transputers with the Helios operating system. The eval-server model of parallelism is used with each transputer in the network reading, evaluating and printing s-expressions independently of the others. Tlisp has been developed for work with computer algebra algorithms, in particular, an interpolation algorithm for computing greatest common divisors of multivariate polynomials. Satisfactory performance has been observed with this application.}, keywords = {Lisp}, } @inproceedings{Wise87, author = {Wise, David}, title = {{Matrix Algebra and Applicative Programming}}, booktitle = {FPCA '87, Functional Programming Language and Computer Architecture}, address = {Portland, Oregon, USA, September 14--16}, year = {1987}, editor = {Kahn, Gilles}, publisher = {Springer, Berlin}, volume = {274}, series = {Lecture Notes in Computer Science}, pages = {134--153}, abstract = {The broad problem of matrix algebra is taken up from the perspective of functional programming. A key question is how arrays should be represented in order to admit good implementations of well-known efficient algorithms, and whether functional architecture sheds any new light on these or other solutions. It relates directly to disarming the ``aggregate update'' problem. The major thesis is that $2^d$-ary trees should be used to represent $d$-dimensional arrays; examples are matrix operations ($d=2$), and a particularly interesting vector ($d=1$) algorithm. Sparse and dense matrices are represented homogeneously, but at some overhead that appears tolerable; encouraging results are retrieved and extended. A Pivot Step algorithm is described which offers optimal stability at no extra cost for searching. The new results include proposed sparseness measures for matrices, improved performance of stable matrix inversion through repeated pivoting while deep within a matrix-tree (extendible to solving linear systems), and a clean matrix derivation of the vector algorithm for the fast Fourier transform. Running code is offered in the appendices. This work is particularly important because of the importance of this family of problems. Progress would be of simultaneous use in decomposing algorithms over traditional vector multiprocessors, as well as motivate practical interest in highly parallel functional architectures}, keywords = {Distributed Data Structures. Aggregate Update}, } @phdthesis{Wray86, author = {Wray, Stuart Charles}, title = {{Implementation and Programming Techniques for Functional Languages}}, school = {Computer Laboratory}, address = {University of Cambridge, England}, month = {June}, year = {1986}, note = {Technical Report No.\ 92}, abstract = {In this thesis I describe a new method of strictness analysis for lazily evaluated functional languages, and a method of code generation making use of the information provided by this analysis. I also describe techniques for practical programming in lazily evaluated functional languages, based on my experience of writing substantial functional programs. My new strictness analyzer is both faster and more powerful than that of Mycroft. It can be used on any program expressed as super-combinator definitions and it uses the additional classifications {\em absent\/} and {\em dangerous\/} as well as strict and lazy. This analyzer assumes that functional arguments to higher order functions are completely lazy. I describe an extension of my analyzer which discovers more strictness in the presence of higher-order functions, and I compare this with higher order analyzers based on Mycroft's work. I also describe an extension of my analyzer to lazy pairs and discuss strictness analyzers for lazy lists. Strictness analysis brings useful performance improvements for programs running on conventional machines. I have implemented my analyzer in a compiler for Ponder, a lazily evaluated functional language with polymorphic typing. Results are given, including the surprising result that higher order strictness analysis is no better than first order strictness analysis for speeding up real programs on conventional machines. I have written substantial programs in Ponder, and I describe in some detail the largest of these, which is about 2500 lines long. This program is an interactive spreadsheet using a mouse and bit-mapped display. I discuss programming techniques and practical problems facing functional languages with illustrative examples from programs I have written.}, keywords = {Strictness Analysis, Abstract Interpretation}, }