Re: ANN: Etiquette: a protocol construction tool

"Thomas F. Burdick" <[email protected]> writes:

> Continuations are too general, though -- the state machine doesn't
> consist of all possible state, just the stat it consists.

I agree for many cases. Having an explicit set of states is nice in
that it focuses your attention on minimizing the states, which means
minimizing the interactions, which leads to nice protocols.

On the other hand, for some real protocols the state you want to
capture _is_ a continuation -- i.e. a stack and a program
counter. Continuations are awfully handy in those cases :-)

Consider reading an S-expression from a stream without blocking. Your
state has to include a stack so you know if you're reading a top-level
object, or if you're reading an element of a list within a vector
within a list, and so on. You also need to keep track of where you're
up to with reading the current object - maybe you're reading a symbol
and you have ten characters of it so far, etc.

If you have capturable continuations, either from your host language
or in your Little Language, then this is easy. If you don't, then you
have to CPS-convert the program by hand, which is much more
complicated (at least I don't know any tricks to make it really simple).

There's also a tempting way to "cheat": buffer up all the data, and
each time you get some more try a whole READ from scratch -- if it
fails, wait until some more data arrives and then try again. The only
trouble is that it takes O(n^2) time on the number of retries.


We've just gone through this whole rigmarole while writing an ILISP
clone based on a Hemlock-style TCP communication channel. We used WIRE
to talk between Emacs and CMUCL, and the WIRE protocol has the same
characteristics of S-expressions described above.

The initial Emacs Lisp implementation used blocking I/O and was quite
simple. But then we didn't like blocking Emacs while waiting for I/O,
so next we did a non-blocking version using heavy macrology to capture
continuations. This works fine, but it takes a lot of pretty heavy
code and, as it turned out, a fair bit of CPU.

Finally (?), we exchanged WIRE for a simple protocol that writes a
fixed-size length header followed by an S-expression as a string. This
is much simpler. You only need one state, represented as an array of
available bytes (an Emacs buffer). Each time some new data arrives you
add it to the array and check if you have a whole message.  If so you
extract the message and READ it, then continue. It's efficient since
the length header makes the "do I have a whole message?" test fast.

So for a protocol like WIRE you really want continuations, but if you
can tweak the protocol a little bit by adding framing information then
you're just fine without them. Quite an "if" though :-)

> After learning SmallTalk, I wrote a Lisp server using ST-style
> message passing for network I/O.  Personally, I found
> message-passing to be a wonderful interface to nonblocking I/O.

I'd enjoy reading any code you'd care to post!

Cheers,
Luke