Explicit Process Locations and Functional Parallel Programming

Gaétan Hains
Université d'Orléans

This work (conducted in collaboration with John Mullins, Univ. Brest, France) is part of our attempt to base the design of parallel programming languages on a new denotational approach. We are motivated by the observation that parallel algorithms (the complexity class NC) are a special case of good sequential algorithms (the complexity class P). So instead of the standard approach where communication/synchronisation operations are added to a sequential language, we specialise known models of the lambda-calculus so as to allow a parallel interpretation. The key technical tool in doing so was introduced by Brookes and Geva: generalised concrete data structures. In this context, deadlock-freedom and deterministic I/O behaviour are automatic. Instead of the open-ended problem of defining new constructs, the language designer has the closed problem of designing efficient implementations for expressive and safe semantic models.
Goal: To parametrise denotational semantics by the number (and possibly network) of physical processors.
Result: A CCC of concrete domains with explicitly distributed (and possibly timed) Brookes-Geva non-deterministic algorithms.
Application: A purely functional language similar to Berry and Curien's CDS0 with the above-stated properties.
Missing: A mathematically-derived implementation, a co-product for recursive- and sum types.
Pointers: See references lip94, europar95, isis95-1E, gdrp95 and europar96 under "Publications" on my web page.

Gaétan Hains

Rue Léonard de Vinci, B.P.6759
Orléans Cedex 2, 45067
Email: Gaetan.Hains@lifo.univ-orleans.fr
Home page: http://web.univ-orleans.fr/~ghains/

Back to the list of talks