Concurrency in FL languages [was Re: Curry design]

From: Manuel Chakravarty <chak_at_greyarea.is.tsukuba.ac.jp>
Date: Fri, 4 Jul 1997 14:06:57 +0900

As there are by now multiple threads of discussion, I like to divide my
comments by topic into different messages. Let's start with concurrency.

But before going into details, John asked

> Which Goffin paper is the best place to look?

``Goffin -- Higher-Order Functions Meet Concurrent Constraints'',
Chakravarty, Guo, K"ohler & Lock, due to appear in a special issue of
Science of Computer Programming in October, preprint at

  http://www.score.is.tsukuba.ac.jp/~chak/papers/papers.html#goffin

This introduces the languages and provides a denotational and
operational semantics. An alternative semantic characterization, based
on linear logic, can be found in Chapter 3 of my thesis

  http://www.score.is.tsukuba.ac.jp/~chak/papers/diss.html


Concurrent Haskell vs. Goffin
=============================

John argued for the use of the monadic operators from Concurrent
Haskell in Escher, whereas the lattest Curry proposal adopts the
Goffin-style coordination approach (actually, I am not completely
happy with some of the technical details in Curry here, but I save
this for a latter message).

What I am missing is the *reason* for supporting concurrency in Escher
and Curry (I mean, apart from the fact that it is a cool thing to do).
Actually, the basic motivations that led to the development of
Concurrent Haskell and Goffin are quite different. In Concurrent
Haskell the emphasis is on an interleaved execution of multiple
threads of control on a single processor (or if you like, also on a
small number of processors coupled by shared-memory) -- this kind of
concurrency is, e.g., important for GUI-based applications. On the
other hand, Goffin's aim is the programming of parallel computers that
consist of many processors and usually have distributed memory.

Although both aims have common aspects, there are differences that
have an impact on language design. For example, problems such as
locking of resources and bounded buffers are important for the
applications programmed in Concurrent Haskell, but they are secondary
to Goffin (this is, on the application level; they are important on
the implementation level). The difference becomes obvious if you have
a look at the examples in the papers about Goffin and the papers about
Concurrent Haskell.

Technically, an important difference between Concurrent Haskell and
Goffin are the objects used for communication. In Concurrent Haskell,
we have `MVars'. These are mutable variables that may have different
values at different times. In contrast Goffin uses logical variables,
which, once bound, cannot change their value anymore. As a
consequence, `readers' of MVars in Concurrent Haskell must be monads
(i.e., be of type (IO a)); but `readers' in Goffin can be of any type
(i.e., need not be of the type O, which contains agents). This has an
impact on the structure of programs.

BTW, nobody prevents you from using monads in Goffin. Goffin is a
conservative extension of Haskell that just adds one more type plus
some operators to Haskell.


Bool /= Constraint
==================

As I understand Michael, the reason for the introduction of two
different types `Bool' (the well known two-valued data type) and
`Constraint' (the type of concurrent constraint expressions) is the
same as in Goffin (where we call `Constraint' simply `O'). The reason
for the distinction is a completely different operational
interpretation of the expressions of these two types and, in fact,
only one of them, namely `Constraint' is a primitive, built-in
type. (`Bool' can be defined as an algebraic data type.)

To illustrate the different operational interpretation, consider the
conjunction over `Bool' and `Constraint'. For `Bool', we have the well
known

  (&&) :: Bool -> Bool -> Bool
  True && x = x
  False && x = False

and the operational behaviour that comes with this definition, but for
`Constraint' (this is Goffin-syntax, Curry may deviate)

  and :: Constraint -> Constraint -> Constraint
  and p q = {p, q}

where `{p, q}' means that the `p' and `q' are evaluated in parallel
and, in Goffin, nobody cares about the result (actually in case of
failure of `p' or `q', the overall program fails).

In some sense you can say, what `IO' is for Concurrent Haskell that is
`Constraint' for Goffin.


Fine grain vs. coarse grain concurrency
=======================================

John wrote

> Second, I don't regard delay due to insufficiently
> instantiated redexes as concurrency at all. It just affects the
> choice of redex. The Escher concurrency is big, chunky,
> coarse-grained, explicit concurrency. (I'm trying to get something
> written on this, so a more detailed debate can be had.)

The same holds for Goffin, as the predicate level (i.e., expressions
of type `O' -- or `Constraint' if you want) is only used to express
parallel operations, or more precisely, coordination. All raw
computation is performed in the purely functional part of Goffin,
i.e., in Haskell.

The reason why you have difficulties to regard the Goffin-model as
concurrent is because you are not willing to adopt two boolean types
(see above), which carry different operational interpretations. On the
other hand, you agree to adopt the new type `IO' (and the operators
that come with it) to introduce some dedicated operational behaviour...

Manuel
Received on Fr Jul 04 1997 - 08:08:00 CEST

This archive was generated by hypermail 2.3.0 : Sa Dez 07 2019 - 07:15:05 CET