world as value
P.R. Serrarens
pascalrs@cs.kun.nl
Wed, 14 Jul 1999 10:22:54 +0200
Adrian Hey wrote:
As your questions contain a lot of 'concurrent' words, I will try to clarify
some things about this.
> Q1: Is 'Concurrent Clean' concurrent or not?
> --------------------------------------------
> When I think about concurrency I'm thinking about concurrent IO performing
> processes. I think this is what most other people mean by concurrency also.
I would not count on that to be the 'right' definition for concurrency (if
there is any...) For example, the book 'Research directions in Parallel
Functional Programming' (to appear) discusses concurrency:
" In our mind, concurrency is concerned with semantic expressiveness (for
example when programming a Graphical User Interface), while parallelism is
concerned with performance (by exploiting archirtectural characteristics). (...)
There is an alternative view of concurrency, under which logically independent
computations are considered to be concurrent. Concurrency in this form is thus
a logical property of a program (...)
"
You seem to use the first definition, while the 'concurrent' in Concurrent
Clean refers to the second.
> The paper about Concurrent Haskell (which Simon Peyton Jones mentioned)
> makes the point that all concurrent languages are non-deterministic (third
> page).
I think this is not true. There are plenty of concurrent functional languages
which provide non-determinism via a special primitive. What do we have when we
leave this primitive out? A non-concurrent language? No, it is concurrent, but
not as powerful as those with the primitive included.
> So we have 3 contradictory 'facts'..
> 1- Clean is a concurrent programming language.
> 2- All Clean programs are deterministic.
> 3- Every concurrent programming language is non-deterministic.
1 and 2 do not conflict, while 3 is false. See above.
> Actually, it is possible to implement deterministic concurrent programs for
> some systems. I do a lot of DSP work where all events are strictly periodic
> and synchronous and the time taken to compute the response to an event is
> fixed. But, for systems in general, we don't know when events will occur
> or how long it will take to compute the response. So it's usually
> necessary to accept non-determinism in order to prevent all IO activity
> being blocked by lengthy computation.
Yes, in many cases you can keep out non-determinism, but that takes a lot of
unconventional thinking and the result is often less efficient or less
powerful.
> Q2: Concurrency via multiple environments?
> ------------------------------------------
> Consider somethimg like..
>
> doit :: *World -> *World
> doit world =
> let (world1,file1)= openafile world
> file2 = writesomedata file1
> world2 = dosomethingelse world1
> world3 = closeafile file2 world2
> in world3
>
> If my understanding of Clean semantics is correct, then we could say that
> because world1 and file1 are independent environments then writesomedata and
> dosomethingelse can be performed concurrently (perhaps with additional
> concurrency annotations).
>
> I think this could be regarded as a form of deterministic concurrency, but it
> seems to suffer from the same problem as the 'symFork' construct (mentioned
> in the Concurrent Haskell paper). The problem is that all IO activity after
> doit will be blocked (unnecessarily) until both writesomedata and
> dosomethingelse have completed.
This may not be a real problem, but more a different way of thinking. The
continuation of the main thread is not contained in <dosomthingelse>.
But let me present you some real concurrency (following definition 1). I have
been working on this last year and published a paper on it (Explicit Message
Passing for Concurrent Clean, look on http://www.cs.kun.nl/~pascalrs). With
the thread creating functions you can create multiple concurrent threads, and
give you the possibility of introduce non-determinism (yes!). Your <doit>
example can be written as:
doit :: *World -> *World
doit w
# (f, w) = openFile w
f = {| I |} writesomedata f
w = newIThread dosomethingelse w
w = close f w
= w
where
writesomedata :: *File -> *File
dosomethingelse :: *TState -> *TState
The *TState type is the World for threads: it is used in the same way, but has
some small restrictions at the moment compored to the World. I notice that only
<dosomethingelse> is evalutated concurrently with the main thread. The function
<close> waits for the result of the <writesomedata> thread and can therefore
only proceed when that thread has finished. A better implementation is:
doit :: *World -> *World
doit w
# w = newIThread openfileandwrite w
w = newIThread dosomethingelse w
= w
where
openfileandwrite :: *TState -> *TState
openfileandwrite ts
# (f, w) = openFile w
f = writesomedata f
= close f w
Now both <openfileandwrite> and <dosomethingelse> can run concurrently with
the main thread.
> One problem I can see with this is that the collection of independent
> environments is effectively determined by the Clean run time system, and
> there is no way I can introduce new (IO) environments of my own using Clean.
With the new Concurrent Clean you can, as I showed you.
> This seems a little inflexible to me. The best I could do would be to dust
> down my trusty C compiler and hack it. Correct?
If you like that, fine.
> Q3: What is a value?
> --------------------
> My problem with this is: What if we don't care in what order the operations
> are performed? We still have to pick an order and pass the environment
> value between operations, thereby making the operations strictly sequential.
> For an environment like a file, this is probably exactly what we want, but
> is this true for environments in general?
First, updating environments in a non-sequential order may result in errors
which are hard to detect. In some cases it may be fine, but when it this so?
When the updates are independent. In Clean this is then modeled by letting
these updates work of different environments.
Secondly, retrieving data from some environments in a non-sequential order may
be fine, take for example reading from files. If one only reads from a file,
one can use the <sfread...> functions, which do not require the file to be uniques.
And thirdly, if these two cases to do apply, one wants to implement a
non-deterministic system! There is only 1 environment which allows independent
updating access to an environment and this is the message passing channel I
introduced in the `Explicit Message Passing...' paper I mentioned above. Most
other environments can be build on top of that. See for example the shared
state example in the paper.
> BTW, after reading about Concurrent Haskell I had a look for info about
> a language called 'Pict' (mentioned in the Concurrent Haskell paper).
> If anybody's interested you can read about it here..
>
> http://www.cis.upenn.edu/~bcpierce/papers/pict/Html/Pict.html
>
> This is apparently based on the pi-calculus. I don't think I'll trade in
> Clean for Pict just yet, but Pict reminded me of an informal graphical
> notation I'd been playing with to represent actions and dependencies.
> In fact I'm pretty sure my graphical notation could be translated into
> Pict without too much difficulty. Alternatively, I think one could define a
> data type which represented Pict programs and calculate values of this
> type using pure functions. Maybe some additional syntactic constructs which
> did for Pict structures what 'do notation' does for monadic IO would help.
> (I guess that's what the Pict language really is.)
>
> So we could make a Clean program something like..
>
> Start :: PictProg
> or
> execute :: PictProg -> *World -> *World
> Start :: *World -> *World
> Start = execute pictprog
>
> .. and the Clean runtime environment would contain a PictProg interpreter
> and scheduler. Just an idea, but maybe implementing forkIO and MVar would
> be simpler.
I know Pict quite well, and it had quite some influence on the message passing
for Concurrent Clean. For Concurrent Clean, I am working toward a system where
programs and threads are indistuiguishable (with the help of dynamic typing).
Both have either the type (*World -> *World) or (*World -> (a, *World)). A
program can then be started just like a thread:
startProgram :: String *World -> *World
startProgram progname w
# (prog, w) = load progname w
= newIThread prog w
(For bevety, I assume that prog has type (*World -> *World)')
--
Pascal Serrarens
Concurrent Clean developer
University of Nijmegen, NL