The History of Parallel Functional Programming 
Author Message
 The History of Parallel Functional Programming

A few weeks ago Greg Wilson asked for some help in gathering
entries for his timeline of parallel computing.  However,
it was quickly realised that a large number of the submited
entries would never make it to the final document (due to
lack of relevance to the entire parallel community).  As
a result we decided to develop two versions: one for the
functional programming community and one for the rest of
the world.  The first draft is included below, but is very
patchy so additional entries and/or corrections are needed
if the history is to be of any use.  The primary areas of
weakness are strictness analysis, none pure FPL's, the
G-machine and specialist hardware.

I would be very grateful in any help you could offer (individuals
will certainly be credited with any contributions - so get in
early and avoid the rush :)  The final version will hopefully prove
invaluable to anyone starting up in the field.

        Thanks,

        Andy.

P.S. It's probably best if you email me your additions/corrections/
suggestions and I will repost the new editions every week or so
until a steady state is reached.

P.P.S. If any one has any comments to make on how to increase the
usefulness of the history (incoorporate a short biblio of key
papers or include more general events) then I'd be interested to
hear them.

  The History of Parallel Functional Programming
  ==============================================

                          August 10, 1993

1   Introduction
================

This report describes the major landmarks in the arena of parallel functional
programming, including the hardware, language and theoretical aspects of
the field.

1.1   Contributors
------------------

Help in compiling this history has been received from the following people
(in no particular order):  Greg Wilson (Parallel Timeline) and John Feo
(SISAL).

2   Theory
==========

1978  -

        o John Backus (inventor of fortran) publishes paper on FP sys-
          tems, arguing that dependence on conventional languages has
          made the development and use of non-von Neumann architec-
          tures uneconomical, and has deprived computer architects of an
          intellectual foundation for new computers.

1980  -

        o Burton approaches the problem of non-determinism by recording
          all such choices made during the first run, enabling the same
          result to be recalculated after the event.

1982  -

        o Henderson describes a functional operating system based on a
          non-deterministic merge operation.

1984  -

        o Johnsson develops the G-machine - a highly efficient graph re-
          ducer. Chalmers.

        o Stoye proposes the use of a sorting office model for functional OS
          and other concurrent systems.

1985  -

        o Hudak and Goldberg develop serial combinators - automatically
          derived, optimally sized, grains of parallelism. Yale.

        o Johnsonn develops the process of lambda lifting. Chalmers.

1986    o Hudak and Smith propose parafunctional programming - based
          on a normal FPL with annotations to guide the operational be-
          haviour.  Provides annotations for controlling mapping (process
          and data), scheduling and data routing. Yale.

        o Arvind (MIT), Nikhil (MIT) and Pingali (Cornell) propose the
          I-structure - a parallel structure similar to arrays, but having
          side effects (therefore would result in an impure FPL). This is
          incorporated into the Id language.

1987  -

        o Burns develops evaluation transformers - a form of strictness anal-
          ysis. GEC Marconi, Hirst.

        o Hudak and Anderson develop the theory of Pomsets - for speci-
          fying the order of evaluation of function arguments in a parallel
          context. Yale.

        o Appel develops an efficient parallel garbage collection system.

        o Harrison develops the idea of time stamping for enabling non-
          deterministic behaviour in FPLs.

        o Bird outlines the basic theory of lists (Bird-Meertens formalism).

1988  -

        o Sabot describes the Paralation model, using the concept of shape,
          move and elwise to achieve parallelism. Harvard.

1989    o Lennart Augustsson and Thomas Johnsson develop a parallel
          version of the G-machine - the < v; G > machine. Initial results
          prove promising. Chalmers.

        o Cole proposes the use of algorithmic skeletons as a basis for a
          parallel paradigm. Edingburgh.

        o Hertzberger and Vree develop the sandwich model for exploiting
          parallelism in FPL. Amsterdam.

        o Marino and Succi describe the bag data type and it's application
          to parallel FPL.

        o Bolton and Hankin and Kelly describe a parallel graph reducer,
          based on director strings, in terms of parallel objects using the
          POOL language. Imperial.

        o Springsteel and Stojmenovic describe the use of the scan function
          in a PRAM system.

1990  -

        o Skillicorn propose that the Bird-Meertens formalism can be used
          as a basis for an architecture independent FP system.  Queens,
          Canada.

1991  -

        o Lester develops an efficient garbage collector for the G-machine
          based upon reference counting and copy methods. GEC Marconi.

        o Axford (Birmingham) and Joy (Warwick) propose list represen-
          tations based on the divide and conquer paradigm.

1992  -

        o Aharoni, Barak and Farber develop an adaptive granuality con-
          trol algorithm for parallel FPL systems. Jerusalem.

        o Glas, Hofman and Vree propose the {*filter*} annotation for devel-
          oping efficient, parallel branch and bound FP systems. Amster-
          dam.

        o Maasen describes several parallel data types, including sequences,
          trees and tables.

        o Rabhi a parallel structure for static iterative transformation al-
          gorithms

1993  -

        o Hains and Mullin extends Skillicorn's work on the Bird-Meertens
          formalism to arrays.

3   Implementations
===================

1987  -

        o SC (SISAL Compiler) released by LLNL and Colorado State Uni-
          versity. First functional language, native-code compiler and run-
          time system for shared-memory multiprocessor systems.

1988  -

        o The Alfalfa system (running on the Intel iPSC MIMD machine
          - 128 80286 connected in a hypercube) and Buckwheat (Encore
          MultiMax - 12 processor GMSV machine) are developed at Yale,
          based on serial combinators.

1989  -

        o Cox (Imperial), Glaser (Southampton) and Reeve (Munich) de-
          velop Tuki - a transputer based intermediate language.

        o OSC (Optimising SISAL Compiler) released by LLNL and CSU.
          The compiler optimises the copy and memory management; SISAL
          programs achieve Fortran speeds on conventional shared-memory
          multiprocessors.

1990  -

        o The HDG Machine - a system based on evaluation transformers,
          running on a 5 processor transputer network was developed by
          Hugh Kingdon, David Lester and Geoffrey Burn. GEC Marconi.

        o Lal George develops a FPL system running on the BBN Butterfly.
          Utah.

        o Marangent develops GAML - a parallel implementation of lazy
          ML on a shared memory computer. INRIA Rocquencourt.

        o Mou develops Divacon - a parallel FPL based on the divide and
          conquer paradigm - the system runs on the connection machine
          (CM-2 I think). Brandeis.

1991  -

        o Jouret develops a data parallel FPL language for SIMD machines.
          Imperial.

        o OSC 12.0, released by LLNL and CSU. First functional lan-
          guage compiler for multiprocessor vector supercomputers. SISAL
          programs achieve Fortran speeds on the Cray-X/MP and Cray-
          Y/MP supercomputers.

        o Boudillet, Gupta and Winter implement a director string system
          on the CTDnet.

1992  -

        o EQUALS - a lazy FPL base on ee-strictness analysis is devel-
          oped by Kaser , Pawagi, Ramakrishnan (all at SUNY) and Sekar
          (Bellcore), running on the Sequent Symmetry.

        o Cox, Huang, Kelly, Liu and Taylor develop an implementation of
          Caliban, but it is restricted to static process networks. Imperial.

        o Joy develops Ginger - a simple FPL with DC extensions.  War-
          wick.

        o Kuchen and Gladitz describe the implementation of the bag data
          type, using the GAMMA model, on a Sequent Symmetry with 6
          processors.

1993  -

        o NESL, a nested, data parallel language, is ported to the CM-2 and
          Cray Y-MP C90 by Blelloch, Chatterjee, Hardwick, Sipelstein
          and Zagha. Carnegie Mellon.

        o Jonathan Hill develops a lazy data parallel version of Haskell on
          the DAP machine. Queens Mary and Westfield.

4   Languages
=============

1983  -

        o Sisal 1.0 (Streams and Iterations in a Single-Assignment Lan-
          guage) language definition released by Lawrence Livermore Na-
          tional Laboratory (LLNL), Colorado State University, DEC, and
          University of Manchester.  A derivative of VAL, the language
          included array operations, streams, and iterations.

1985  -

        o Sisal 1.2 language definition released; language definition does
          not change for another seven years.

1987  -

        o EPL - a parallel programming language with recurrent equations
          is developed by Szymanski, running on dataflow architectures.
          Rensselaer.

1988  -

        o Crystal - a parallel FPL based upon domains and indexing - is de-
          veloped by Chen, Choo and Li. A version running on the iPSC/2
          machine has been developed. Yale.

1989 ...

read more »



Sat, 27 Jan 1996 20:48:35 GMT  
 The History of Parallel Functional Programming
I've finally managed to incorporate all the corrections and additions that
a great many people were kind enough to send in.  I've included the history
in it's entirety, but in future I think storing it in an ftp site would
be more appropriate (suggestions welcome for potential sites).

The history is still far from perfect and I'm still very interested in
additional info.  However, I'm going to be busy for a couple of
weeks, so a new history wouldn't be produced until the first or second week
of Sepetmeber.

Once again, thanks to everyone who contributed.

        Cheers,

                Andy.

  The History of Parallel Functional Programming
  ==============================================

1   Introduction
================

This report describes the various advancements in the arena of parallel func-
tional programming, including the hardware, language and theoretical as-
pects of the field. The major landmarks will also appear in Greg Wilson's
general timeline.

1.1   Contributors
------------------

The following people have helped compile this history (email addresses will
not be included unless the contributors have given their permission to do
so):

          Edo Biagioni           EB
          Tony Davie             TD
          John Feo               JF
          Stefan U. Haenssgen    SH
          Pieter H. Hartel       PH
          Martin Honnen          MH
          Paul Hudak             PH
          Robert M. Keller       RK
          Herbert Kuchen         HK
          Sanjiva Prasad         SP
          Paul Whiting          PGW
          Greg Wilson           GVW
          Kim Yates              KY

Additions or amendments to the history should be sent to Andy Ben-Dyke.

2   Theory
==========

1975:

  Burge mentions the possibility of parallel functional programming in his
     book "Recursive Programming Techniques". He also discusses laziness
     and speculative parallelism.(TD.)

1978:

  John Backus (inventor of Fortran) publishes paper on FP systems, argu-
     ing that dependence on conventional languages has made the develop-
     ment and use of non-von Neumann architectures uneconomical, and
     has deprived computer architects of an intellectual foundation for new
     computers.(PGW.)

1979:

  Turner develops SASL, basing the implementation on SK combinators.(TD.)

1980:

  Burton approaches the problem of non-determinism by recording all such
     choices made during the first run of a program, enabling the same
     result to be returned on subsequent runs.(ABD.)

  Keller describes the use of parallel data structures for divide and conquer
     algorithms, in the context of the AMPS dataflow project. Utah.(RK.)

1982:

  Henderson describes a functional operating system based on a non-deterministic
     merge operation.(ABD.)

  Corovessis develops a simulator for the SASL language, which offers ex-
     tensions for call-by-parallel parameter passing and speculative paral-
     lelism.(TD.)

  Hughes develops the notion of super combinators and lambda lifting,
     removing the need for global environments (as used in such systems
     as the SECD machine).(TD.)

  Kennaway and Sleep describe the use of director symbols as combinators.
     East Anglia.(ABD.)

1984:

  Johnsson develops the G-machine - a highly efficient graph reducer.
  Chalmers.(ABD.)

  Stoye proposes the use of a sorting office model for functional OS and
     other concurrent systems.(ABD.)

  Hudak and Goldberg develop notion of serial combinators, a variation on
     super combinators targeted towards medium-grain parallelism.
     Yale.(ABD,PH.)

  Abramsky and Sykes develop the SECD-M virtual machine for imple-
     menting parallel FPL.(MH.)

1986:

  Hudak and Smith propose parafunctional programming - based on normal
     FPL with annotations to guide the operational behaviour.  Provides
     annotations for controlling mapping (process and data), scheduling
     and data routing. Yale.(ABD.)

  Arvind (MIT), Nikhil (MIT) and Pingali (Cornell) propose the I-structure
     - a parallel structure similar to arrays, but having side effects (there-
     fore would result in an impure FPL). This is incorporated into the Id
     language.(ABD.)

1987:

  Burn develops evaluation transformers - a form of strictness analysis.
     GEC Marconi, Hirst. (ABD.)

  Hudak and Anderson apply the theory of Pomsets to express parallel
     operational semantics. Yale.(ABD,PH,KY.)

  Appel develops an efficient parallel garbage collection system.(ABD.)

  Harrison develops the idea of time stamping for enabling non-deterministic
     behaviour in FPLs.(ABD.)

  Bird outlines the basic theory of lists (Bird-Meertens formalism).(ABD.)

1988:

  Sabot describes the Paralation model, using the concept of shape, move
     and elwise to achieve parallelism. Harvard.(ABD.)

1989:

  Lennart Augustsson and Thomas Johnsson develop a parallel version of
     the G-machine - the <v; G>-machine.  Initial results prove promising.
     Chalmers.(ABD.)

  Cole proposes the use of algorithmic skeletons as a basis for a parallel
     paradigm. Edingburgh.(ABD.)

  Hertzberger and Vree develop the sandwich model for exploiting paral-
     lelism in FPL. Amsterdam.(ABD, PH.)

  Marino and Succi describe the bag data type and its application to par-
     allel FPL.(ABD.)

  Bolton and Hankin and Kelly describe a parallel graph reducer, based on
     director strings, in terms of parallel objects using the POOL language.
     Imperial.(ABD.)

  Springsteel and Stojmenovic describe the use of the scan function in a
     PRAM system.(ABD.)

  Lester develops analysis techniques for determining maximum memory
     usage by recursive functions, enabling heap allocated memory to be
     used to safely replace a normal stack in distributed architectures.(ABD.)

1990:

  Skillicorn propose that the Bird-Meertens formalism can be used as a ba-
     sis for an architecture independent FP system. Queens, Canada.(ABD.)

1991:

  Lester develops an efficient garbage collector for the G-machine based
     upon reference counting and copy methods. GEC Marconi.(ABD.)

  Axford (Birmingham) and Joy (Warwick) propose list representations
     based on the divide and conquer paradigm.(ABD.)

1992:

  Aharoni, Barak and Farber develop an adaptive granuality control algo-
     rithm for parallel FPL systems. Jerusalem.(ABD.)

  Glas, Hofman and Vree propose the {*filter*} annotation for developing
     efficient, parallel branch and bound FP systems. Amsterdam.(ABD.)

  Maasen describes several parallel data types, including sequences, trees
     and tables.(ABD.)

  Rabhi develops a parallel structure for static iterative transformation
     algorithms. Hull.(ABD.)

  Hwang and Rushall develop the  -STG machine, a parallel graph reducer
     for distributed memory architectures. Manchester.(ABD, SH.)

1993:

  Hains and Mullin extends Skillicorn's work on the Bird-Meertens formal-
     ism to arrays.(ABD.)

3   Languages
=============

1978:

  Arvind, Kim Gostelow and Wil Plouffe (at the University of California,
     Irvine) introduce the dataflow language Id (Irvine dataflow).(PGW.)

1979:

  Ackerman and Dennis develop VAL (Value-Orientated Algorithmic Lan-
     guage), a static dataflow language designed explicitly for efficient par-
     allel execution. The predecessor of Sisal. MIT.(KY.)

1983:

  Sisal 1.0 (Streams and Iterations in a Single-Assignment Language) lan-
     guage definition released by Lawrence Livermore National Laboratory
     (LLNL), Colorado State University, DEC, and University of Manch-
     ester.  A derivative of VAL, the language included array operations,
     streams, and iterations.(JF.)

  Keller outlines FEL (Function Equation Language) for use on the new
     Rediflow architecture.  Introduces array comprehension for the first
     time. Utah.(RK.)

1984:

  van Eeklen, Huitema, N"ocker, Smetsers and Plasmeijer develop Clean,
     based on the ABC machine.  Currently there are efficient implemen-
     tations running on sun's, macintoshes and transputer (ZAPP) based
     systems.(SH.)

1985:

  Sisal 1.2 language definition released; language definition does not change
     for another seven years.(JF.)

1986:

  ParAlfl, a functional language with meta-linguistic control of parallel op-
     erational semantics, was developed by Hudak at Yale.(PH.)

1987:

  EPL - a parallel programming language with recurrent equations is de-
     veloped by Szymanski, running on dataflow architectures.  Rensse-
     laer.(ABD.)

1988:

  Crystal - a parallel FPL based upon domains and indexing - is developed
     by Chen, Choo and Li. A version running on the iPSC/2 machine has
     been developed. Yale.(ABD.)

1989:

  Giacalone, Mishra and Prasad develop Facile - a symmetric integration of
     concurrent and functional programming. Based on CCS and using a
     modified SECD machine for the implementation. Stony Brook.(ABD,
     SP.)

  Kelly describes the Caliban language for loosely connected MIMD ma-
     chines. Imperial.(ABD.)

  Ariola (Harvard) and Arvind (MIT) develop P-TAC a parallel, interme-
     diate language for Id, incorporating I-structures.(ABD.)

1990:

  Mou develops Divacon - a parallel FPL based on the divide and conquer
     paradigm - the system runs on the connection machine (CM-2 I think).
     Yale.(ABD,PH.)

1991:

  Reppy develops CML a concurrent extension to standard ML (SML) -
     based on the CSP methodology. Cornell.(ABD.)

  Rabhi and Manson describe the divide and conquer technique within a
     graph reduction framework.(ABD.)

  Yang and Choo describe a meta language for controlling program trans-
     formation in their Crystal language. Yale.(ABD.)

1992:

  Chakravarty and K"ohler the JUMP-machine, an FPL with equational
     constraints for explicit specification
...

read more »



Sat, 03 Feb 1996 19:41:00 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. Parallel Functional Programming book

2. PhD Studentship: Parallel Functional Programming

3. Parallel Functional Programming Bibliography (2nd ed)

4. Parallel Functional Programming Bibliography

5. summary on developing functional parallel program

6. Develop parallel program by functional approach

7. parallel functional programming

8. History of the ! (spark) annotation in parallel FPLs

9. functional.py 0.6 - Functional Programming in Python

10. functional.py 0.7 - Functional programming in Python

11. functional.py - functional programming in Python

12. functional.py 0.7 - Functional programming in Python

 

 
Powered by phpBB® Forum Software