[e-lang] The observer in CML

Mark Miller markm at cs.jhu.edu
Wed Dec 22 23:18:27 EST 2004


Michael Sperber wrote:
> The CML operations are implemented 1:1.  The only terminology
> difference is that I call "events" "rendezvous", given that "event" is
> used for many other things.  I've commented the CML operations in the
> annotated version of the code.
> 
> Mark> And Scheme seems to have changed substantially since I last knew
> Mark> the language: I wasn't aware that it had a define-record-type or
> Mark> keyword arguments.
> 
> This is a SRFI; I've put a reference in the annotated code.  No
> keyword arguments anywhere in the code, though.


Thanks! This was a tremendous help. I've read your define-record-type SRFI and
then your annotated code. I have also gotten far enough through Reppy's book
(page 78) that I understand all the constructs you use. AFAIK, I now fully
understand your annotated example code.

Would it help you learn E if I were to translate your example into E syntax,
but using CML primitives rather than E's concurrency control model? I thinking
of doing that anyway, since it'll also help bring everyone here into the
discussion. I think this example is indeed a good one for comparing the
paradigms, and it would be good to get the distracting syntactic differences
out of the way.

In any case, for now, I'll explain the deadlock issue while using your Scheme
syntax.


>>>	    ((set-request? request)
>>>	     (let ((value (set-request-value request)))
>>>	       (for-each (lambda (channel)
>>>			   (send channel value))
>>>			 observer-channels)
>>>	       (server value observer-channels))))))))
> 
> 
> Mark> leave you open to the same deadlock problem that the original Java code
> Mark> (slide 4 of <https://www.cypherpunks.to/erights/talks/promises/promises.pdf>)
> Mark> was vulnerable to?
> 
> No.  I find it hard to provide a more elaborate answer----how do you
> see a deadlock happening?


Let's say that a particular ref cell, Ralph, has two clients, each in their
own processes: Sally the setter and Lisa the listener.


Sally goes through her loop of activities, doing various things, implicitly
with various channels, including occasionally doing a
     (set-ref! ralph newValue)
Hidden within this operation is a
     (send (ref-request-channel ralph)
	(make-set-request newValue)))
but that's encapsulated from her, since, presumably, it shouldn't concern her.


Lisa adds herself as an observer to Ralph, by doing
     (define ob (make-ref-observer ref))
Afterwards, she also goes through her loop of activities, doing various 
things, implicitly with various channels, including occasionally doing a
     (define newValue (sync (ref-observer-rv ob)))
This 'sync' might also be hidden from her by an encapsulating abstraction.


Sally and Lisa occasionally talk to each other.


We can easily enter into a situation where
* Lisa is waiting to talk to Sally.
* Ralph is waiting to inform Lisa about the last value set by Sally.
* Sally is waiting to set Ralph to a new value.

This kind of cyclic waiting graph among processes can occurs vastly more
non-deterministically than normal bugs. By contrast, data-lock bugs (the bugs
E programs have instead of deadlock) seem to manifest as deterministically as
normal bugs <http://www.eros-os.org/pipermail/e-lang/2001-May/005287.html>.

By normal software engineering standards, for Lisa and Sally to be *correct*,
they should only depend on the *specified* properties of the abstractions they
use. ML throws all sorts of heavy machinery into having an expressive
language for specifying type compatibility issues in a statically machine
checked way. But so far (page 78) I see no hint of how one would express
Ralph's specification, independent of his implementation, such that the
composition of individually correct Ralphs, Lisas, and Sallys could not 
deadlock. Is there such a specification sublanguage later in the book?

Model checking is not an answer; it is surrender. It retreats from the goal of 
using specifications to firewall correctness arguments.


The above rant applies more to CML itself than to your CML-in-Scheme, since
Scheme doesn't try to statically check type compatibility either. But if it
actually is much harder to specify Ralph's concurrency contract than it is to
specify his type contract, then I think this indicates a real difficulty even
in languages where programmers reason only informally about both.

-- 
Text by me above is hereby placed in the public domain

     Cheers,
     --MarkM




More information about the e-lang mailing list