Imagining Iteratee IO in Scheme

Oleg's Iteratee IO is an application of collection traversal to stream processing. He has been interested in coming up with a good technique to traverse general collection. I think Iteratee IO is an excellent and exciting application of collection traversal, but it's implemented in Haskell and it's kind of odd that he didn't come up with a Scheme version considering that he was very involved in Scheme.

So, I just had to try bringing it over to Scheme, at the risk of marring his work.

Here's my first attempt at imagining what the Iteratee examples in his slide would look like in Scheme. There are some repetitions that really should be streamlined or reduced in subsequent attempts.

What missing are: 1. lack of error resumption, and 2. resumption of partial computation through Monads. Instead partial computation has to be passed manually on each call.

imagining-iteratee-io-in-scheme.scm

Dealing with external library and single-threaded runtime environment

My recent works with using external C libraries with chicken and gambit cue me to two problems that are shared by other language implementation that runs on a single OS threads (ruby, phyton, for example).

The problems are: (1) how to not block when calling external C library,  (2) how to service callback, and (3)how to service parallel callbacks.

There are many solutions to these problems. The ones that I think can be applied to *nix, windows, osx, ios and android are as follows:
[Assumptions: pthread and pipe are available on the intended platform, and pthread creates threads that do not block other pthread threads. If there is no pthread, use other threading libraries with the above properties]

For the problem of blocking when calling an external library

Setup: Use pthread to create worker threads. Create two pipes for each worker thread. One for signaling to worker thread of a pending request, the other for signalling the master of a waiting response. Each thread should have its own mailbox. The mailbox should be able to take request and response data. It can be as simple as having void* slots. As a worker thread can work only with a request at a time, it does not have to be assigned a perennial mailbox. A new one can be created for each request and a pointer to it is send in the request notification signal. This simplifies the management of the mailboxes.

Operation: Use FFI to populate the mailbox's request slot with pertinent data. Send a request notification signal to an idle worker. If using a temporary mailbox, pass along a pointer to it in the signal. At this point, there should be a language thread that monitors the response notification pipe. It could be a dedicated thread or the current thread.

An idle worker thread should block reading the request notification pipe for signal. If a signal is received, it should access its mailbox for request data and proceed accordingly. The response should be put in the mailbox's response slot and a signal should be send to the response notification pipe.
 

For the problem of accepting [parallel] callbacks

It would have been nice to be able to call into the implementation directly from the external library. But it won't work with gambit and chicken which impose its own structure on the stack to support TCO. Even if it is not a factor, it will not support parallel callbacks because the implementations will perform unsynchronized modifications to internal global structures.

So, a solution to this is to use mailbox and pthread again. Presumably the parallel callbacks are done through pthread. Each callback is performed on a different pthread thread.

Setup: this time only one pipe is needed. It will be used to send request notification from external to scheme-land.

Operation: upon a callback, create a new mailbox. Stuff a pthread conditional variable in there along with request data. Send a request notification with a pointer to the mailbox. Make sure that the writing to the pipe is synchronized so that only one thread writes at a time. Then wait on the CV.

On scheme land, the thread that monitors the request notification pipe should spawn a new scheme thread to handle the request. After the request is processed and response put in the appropriate mailbox slot,  signal the CV and be done.

Back to the pthread thread: upon the CV signal, the thread execution is resumed and can return from the callback properly.