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.
LIFO
Rue Léonard de Vinci, B.P.6759
Orléans Cedex 2, 45067
France
Email:
Gaetan.Hains@lifo.univ-orleans.fr
Home page:
http://web.univ-orleans.fr/~ghains/
Back to the list of talks