The goals of the concurrency standard?

[oleg at pobox.com]

John Meacham wrote
> [Rule 1]
> * in a cooperative implementation of threading, any thread with value
>   _|_ may cause the whole program to have value _|_. In a preemtive one,
>   this is not true.

> would the simple qualifier
> 'if there exists another runnable thread'
> solve the issues?

  if there exists another runnable thread of at least the same
priority.


I am afraid I must ask for the clarification of the goals of this
discrimination between pre-emptive and cooperative scheduling -- which
leads me to further questions.

One one hand, I understand the motivation: providing guidance to the
end programmer. In a cooperative thread system, the programmer just
can't write code imagining the current thread is the only one. If the
thread is to compute the Nth Mersenne prime, it would effectively hang
the whole system. So, the user must specifically insert calls to yield
-- which means that the whole code has to be converted into a monadic
style, because yield is most certainly a monadic operation _and_
because we must be sure that computations before yield are indeed
finished, rather than snowball up to the very end. So, we have to
re-write pure functional code (like the Mersenne prime computation)
into a monadic one, and thus explicitly serialize it. That negates one
of the significant benefits of Haskell -- no longer code looks like a
specification or mathematical notation. If we're forced to write
everything in the A-normal form, we might as well use a better
language for that, like SML.

In a preemptive thread system, we can indeed program a thread as if it
were the only thread in the system -- and the scheduler would do the
rest.

Problem solved? Only if threads do not interact, which is not
likely. At least they have to write something, and so contend for the
access to stdout (assuming multi-line output). A thread running a long
computation while holding a critical resource can just as well hang
the whole system, pre-emptive scheduler notwithstanding. Lazy
evaluation of Haskell makes this problem quite subtle:

	do
	r <- return (mersenne' 44)
	acquire'lock
	putStrLn "Great success"
	print r
	release'lock

One may think that the long computation occurs in the "r <- ..." line.
Alas, it may just as well occur in the "print r" line, when the digits
of the number are really required to print. So, we will be running a
long computation while holding a lock. This isn't much better than the
situation with the cooperative scheduling, is it?

It appears that just pre-emptiveness does not guarantee us much. We
need to add, for example, hyper-strict evaluation -- or, effectively,
give up on the lazy evaluation because otherwise we can never be
certain about the length of the computation -- and without that
information, we can never be certain if our locking strategy is
fair. The latter has nothing to do with pre-emptiveness.

There seems to be another, Erlang way. The programmer must have an
impression that threads do not share absolutely anything, and must
communicate exclusively via message passing. Incidentally, how this
message passing implemented on a shared memory multi-processor is
another matter entirely: Erlang is quite good at taking advantage of
shared memory while giving the user impression of complete isolation.
Message passing in Erlang is quite advanced: a thread may snoop the
message queue looking for a specific message. The user may code a
process as if no other processes exist. Erlang's scheduler does the
right thing (I think it pre-empts based on the number of reductions;
the scheduler may take the size of the message queue into
account). The example above becomes

	do
	r <- return (mersenne' 45)
	send "Great success"
	send $ show r
	send "print it now"

the output thread won't write anything until it catches the sight of
"print it now" message in its message queue. In a sense, this strategy
isn't quite different from STM.

There is a price to pay however: absolutely no IORefs, no MVars
etc. All system calls must be converted to a message-passing
style. The latter isn't a huge problem: Erlang has managed. But for
us, that entails the re-design of FFI, IO, and the banishment of
IORefs and MVars...