[e-lang] The observer in CML

[Mark Miller]

Michael Sperber wrote:
>>>>>>"Mark" == Mark Miller <markm at cs.jhu.edu> writes:
> 
>>>>>    ((set-request? request)
>>>>>     (let ((value (set-request-value request)))
>>>>>       (for-each (lambda (channel)
>>>>>		   (send channel value))
>>>>>		 observer-channels)
>>>>>       (server value observer-channels))))))))
> 
> Ah---you're right, there's a bug here.  This needs to be wrapped in a
> SPAWN.  Sorry about that, and thanks for being persistent in pointing
> it out!


At this point, I should admit that I was waiting for you to propose that. 
That's the kind of answer to this issue that appears repeatedly in Reppy's 
book. You have now recapitulated the transition from slide 4 of 
<https://www.cypherpunks.to/erights/talks/promises/promises.pdf> to slide 5. 
Your code has the same "new problem" that I mysteriously refer to on that slide:

Your observers might now be notified out of order. If Sally first tells Ralph 
to change his value to 3 and then to 7, Ralph's final value is 7. However, if 
Ralph spawns processes to notify Lisa about each change, the process spawned 
to tell Lisa the value's changed to 7 might race ahead of the process spawned 
to tell Lisa the value's changed to 3. Lisa's logic now can no longer assume 
that the order of notifications reflects the order in which the side effects 
were performed. You lose the "FIFO" delivery property that distributed systems 
programmers have rightly come to prize.

Now, this isn't fatal. We could enhance the protocol so that Ralph keeps a 
sequence number, which he increments on each value change and sends on each 
notification. And Lisa can keep track of which sequence numbers she's seen -- 
either reordering these to FIFO if she cares about all notifications, or 
discarding older notifications ("value has changed to 3") if she doesn't. 
However,

* Javasoft, in recommending the pattern in slide 5 over slide 4 never pointed
   out this loss of ordering.
* Reppy's book, when it shows how to use spawn to avoid deadlock in this same
   manner, never points this out either.
* Above, you didn't point it out either. Did you notice this issue when you
   suggested this "fix"?

The point isn't that the problem is fatal. The point, as it says on slide 5, 
is "Seemingly simple patterns become minefields." The original sequential 
observer pattern was trivially correct. Or rather, in the absence of a 
specification, we can say that any competent sequential object programmer, 
Orville, when faced with this problem, could trivially invent this pattern 
even if they've never heard of it before. Further, when seeing this pattern, 
Orville is able to trivially understand its actual properties without 
confusion, and to use it correctly.

Refering to slide 6, you have not escaped the dilemma. Your first code 
example, by being conservative enough about what interleavings it would allow, 
like side 4, created an abstraction which could be used with high confidence 
of preserving consistency but low confidence of avoiding deadlock. Your "fix" 
above, by allowing more interleavings, perhaps allows too many. It creates an 
abstraction that could be used with high confidence of avoiding deadlock, but 
with much lower confidence that clients, such as Lisa, will successfully 
maintain their consistency.

Further, this response (both your's and in Reppy's book) throws away the main 
advantage that Reppy's book claims for rendezvous over asynchronous messaging. 
As I quoted earlier:

"In asynchronous systems, the typical failure mode is an overflow of the 
memory used to buffer messages, which is likely to be far removed in time (and 
possibly place) from the source of the problem. In synchronous systems, the 
typical failure mode is deadlock, which is immediate and easily detected. 
Thus, detecting and fixing bugs in a synchronous message-passing program is 
easier."

The out-of-memory problem with asynchronous messages that Reppy points to here 
is what we call Gridlock. (For a brief definition, see 
<http://www.erights.org/elib/concurrency/event-loop.html>.)

You have not avoided the unbounded memory needed to buffer messages. Rather, 
with this "fix", you're buffering your outgoing message by allocating a 
process. The corresponding problem would be an overflow of the memory used to 
allocate processes. I doubt that debugging such out of memory problems is 
easier than debugging gridlock. The contrast Reppy makes is between (in our 
terms) gridlock vs deadlock. As we see, a fair comparison should contrast 
three possibilities:

* Slide 4, or your first example: easy consistency but deadlock danger.
* Slide 5, or your proposed fix: difficult to preserve consistency, and
   possibility of running out of process memory.
* Slide 7 -- asynchronous FIFO message passing between communicating event
   loops: easy consistency but gridlock danger.


> Hmm---I guess this comes down to experience.  Had I actually run
> anything but trivial examples, this bug would have manifested itself
> almost immediately.  This is my general experience with CML.  The
> non-determinism comes from the true concurrency inherent in the
> program.

As we see above, to avoid deadlock, you introduced non-determinism, creating 
hazards you didn't even think to mention (and perhaps didn't notice). Lisa's 
programmer now has a new burden born from this non-determinism, and the burden 
is completely an artifact. It has nothing to do with any inherent concurrency 
in the problem being solved.


> I would think you'd the same kind of non-determinism in an E
> program as soon as it becomes interactive.

It is true that concurrency control must involve non-determinism. Any 
programming language in which non-determinism cannot be expressed might be 
able to be parallelized, but it cannot do concurrency control.

You raise the issue here in exactly the right way: To what degree does the 
programming model force the programmer to deal with non-determinism beyond 
that inherent in the problem being solved? Please let's revisit the matter in 
these terms once you've spent more time learning E.


> Mark> Would it help you learn E if I were to translate your example
> Mark> into E syntax, but using CML primitives rather than E's
> Mark> concurrency control model?
> 
> I don't think so---I really need to spend more time with the docs, and
> possibly play with the implementation.


Glad to hear it! As you run into further questions, please ask.


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

     Cheers,
     --MarkM