Concurrent ML
=============

Scheme48 provides a high-level event synchronization facility based on on Reppy's Concurrent ML [Reppy 99].  The primary object in CML is the rendezvous (In the original CML, these were called events, but that term was deemed too overloaded and confusing when Scheme48's library was developed.), which represents a point of process synchronization.  A rich library for manipulating rendezvous and several useful, high-level synchronization abstractions are built atop rendezvous.

Rendezvous concepts
-------------------

When access to a resource must be synchronized between multiple processes, for example to transmit information from one process to another over some sort of communication channel, the resource provides a rendezvous to accomplish this, which represents a potential point of synchronization between processes.  The use of rendezvous occurs in two stages: synchronization and enablement.  Note that creation of rendezvous is an unrelated matter, and it does not (or should not) itself result in any communication or synchronization between processes.

When a process requires an external resource for which it has a rendezvous, it synchronizes that rendezvous.  This first polls whether the resource is immediately available; if so, the rendezvous is already enabled, and a value from the resource is immediately produced from the synchronization.  Otherwise, the synchronization of the rendezvous is recorded somehow externally, and the process is blocked until the rendezvous is enabled by an external entity, usually one that made the resource available.  Rendezvous may be reüsed arbitrarily many times; the value produced by an enabled, synchronized rendezvous is not cached.  Note, however, that the construction of a rendezvous does not (or should not) have destructive effect, such as sending a message to a remote server or locking a mutex; the only destructive effects should be incurred at synchronization or enablement time.  For effecting initialization prior to the synchronization of a rendezvous, see below on delayed rendezvous.

Rendezvous may consist of multiple rendezvous choices, any of which may be taken when enabled but only one of which actually is.  If, when a composite rendezvous is initially synchronized, several components are immediately enabled, each one has a particular numeric priority which is used to choose among them.  If several are tied for the highest priority, a random one is chosen.  If none is enabled when the choice is synchronized, however, the synchronizer process is suspended until the first one is enabled and revives the process.  When this happens, any or all of the other rendezvous components may receive a negative acknowledgement; see below on delayed rendezvous with negative acknowledgement.

A rendezvous may also be a rendezvous wrapped with a procedure, which means that, when the internal rendezvous becomes enabled, the wrapper one also becomes enabled, and the value it produces is the result of applying its procedure to the value that the internal rendezvous produced.  This allows the easy composition of complex rendezvous from simpler ones, and it also provides a simple mechanism for performing different actions following the enablement of different rendezvous, rather than conflating the results of several possible rendezvous choices into one value and operating on that (though this, too, can be a useful operation).

Delayed rendezvous
------------------

A rendezvous may be delayed, which means that its synchronization requires some processing that could not or would not be reasonable to perform at its construction.  It consists of a nullary procedure to generate the actual rendezvous to synchronize when the delayed rendezvous is itself synchronized.

For example, a rendezvous for generating unique identifiers, by sending a request over a network to some server and waiting for a response, could not be constructed by waiting for a response from the server, because that may block, which should not occur until synchronization. It also could not be constructed by first sending a request to the server at all, because that would have a destructive effect, which is not meant to happen when creating a rendezvous, only when synchronizing or enabling one.

Instead, the unique identifier rendezvous would be implemented as a delayed rendezvous that, when synchronized, would send a request to the server and generate a rendezvous for the actual synchronization that would become enabled on receiving the server's response.

Negative acknowledgements
.........................

Delayed rendezvous may also receive negative acknowledgements.  Rather than a simple nullary procedure being used to generate the actual rendezvous for synchronization, the procedure is unary, and it is passed a negative acknowledgement rendezvous, or nack for short.  This nack is enabled if the actual rendezvous was not chosen among a composite group of rendezvous being synchronized.  This allows not only delaying initialization of rendezvous until necessary but also aborting or rescinding initialized transactions if their rendezvous are unchosen and therefore unused.

For example, a complex database query might be the object of some rendezvous, but it is pointless to continue constructing the result if that rendezvous is not chosen.  A nack can be used to prematurely abort the query to the database if another rendezvous was chosen in the stead of that for the database query.

Rendezvous combinators
----------------------

The rendezvous structure exports several basic rendezvous combinators.

 -- Constant: never-rv returns rendezvous
     A rendezvous that is never enabled.  If synchronized, this will block the synchronizing thread indefinitely.

 -- procedure: always-rv value returns rendezvous
     Returns a rendezvous that is always enabled with the given value.  This rendezvous will never block the synchronizing thread.

 -- procedure: guard rv-generator returns rendezvous
 -- procedure: with-nack rv-generator returns rendezvous
     Guard returns a delayed rendezvous, generated by the given procedure RV-GENERATOR, which is passed zero arguments whenever the resultant rendezvous is synchronized.  With-nack returns a delayed rendezvous for which a negative acknowledgement rendezvous is constructed.  If the resultant rendezvous is synchronized as a part of a composite rendezvous, the procedure rv-generator is passed a nack for the synchronization, and it returns the rendezvous to actually synchronize.  If the delayed rendezvous was synchronized as part of a composite group of rendezvous, and another rendezvous among that group is enabled and chosen first, the nack is enabled.

 -- procedure: choose rendezvous ... returns composite-rendezvous
     Returns a rendezvous that, when synchronized, synchronizes all of the given components, and chooses only the first one to become enabled, or the highest priority one if there are any that are already enabled.  If any of the rendezvous that were not chosen when the composite became enabled were delayed rendezvous with nacks, their nacks are enabled.

 -- procedure: wrap rendezvous procedure returns rendezvous
     Returns a rendezvous equivalent to RENDEZVOUS but wrapped with PROCEDURE, so that, when the resultant rendezvous is synchronized, RENDEZVOUS is transitively synchronized, and when RENDEZVOUS is enabled, the resultant rendezvous is also enabled, with the value that PROCEDURE returns when passed the value produced by RENDEZVOUS.

          (sync (wrap (always-rv 4)
                      (lambda (x) (* x x))))      returns 16 lisp

 -- procedure: sync rendezvous returns value (may block)
 -- procedure: select rendezvous ... returns value (may block)
     Sync and select synchronize rendezvous.  Sync synchronizes a single one; select synchronizes any from the given set of them.  Select is equivalent to (sync (apply choose RENDEZVOUS ...)), but it may be implemented more efficiently.

Timing rendezvous
.................

The rendezvous-time structure exports two constructors for rendezvous that become enabled only at a specific time or after a delay in time.

 -- procedure: at-real-time-rv milliseconds returns rendezvous
 -- procedure: after-time-rv milliseconds returns rendezvous
     At-real-time-rv returns a rendezvous that becomes enabled at the time MILLISECONDS relative to the start of the Scheme program. After-time-rv returns a rendezvous that becomes enabled at least MILLISECONDS after synchronization (not construction).

Rendezvous communication channels
---------------------------------

Synchronous channels
....................

The rendezvous-channels structure provides a facility for synchronous channels: channels for communication between threads such that any receiver blocks until another thread sends a message, or any sender blocks until another thread receives the sent message.  In CML, synchronous channels are also called merely `channels.'

 -- procedure: make-channel returns channel
 -- procedure: channel? object returns boolean
     Make-channel creates and returns a new channel.  Channel? is the disjoint type predicate for channels.

 -- procedure: send-rv channel message returns rendezvous
 -- procedure: send channel message returns unspecified (may block)
     Send-rv returns a rendezvous that, when synchronized, becomes enabled when a reception rendezvous for CHANNEL is synchronized, at which point that reception rendezvous is enabled with a value of MESSAGE.  When enabled, the rendezvous returned by send-rv produces an unspecified value.  Send is like send-rv, but it has the effect of immediately synchronizing the rendezvous, so it therefore may block, and it does not return a rendezvous; (send CHANNEL MESSAGE) is equivalent to (sync (send-rv CHANNEL MESSAGE)).

 -- procedure: receive-rv channel returns rendezvous
 -- procedure: receive channel returns value (may block)
     Receive-rv returns a rendezvous that, when synchronized, and when a sender rendezvous for CHANNEL with some message is synchronized, becomes enabled with that message, at which point the sender rendezvous is enabled with an unspecified value.  Receive is like receive-rv, but it has the effect of immediately synchronizing the reception rendezvous, so it therefore may block, and it does not return the rendezvous but rather the message that was sent; (receive CHANNEL) is equivalent to (sync (receive-rv CHANNEL)).

Asynchronous channels
.....................

The rendezvous-async-channels provides an asynchronous channel (Known as mailboxes in Reppy's original CML.) facility.  Like synchronous channels, any attempts to read from an asynchronous channel will block if there are no messages waiting to be read.  Unlike synchronous channels, however, sending a message will never block.  Instead, a queue of messages or a queue of recipients is maintained: if a message is sent and there is a waiting recipient, the message is delivered to that recipient; otherwise it is added to the queue of messages.  If a thread attempts to receive a message from an asynchronous channel and there is a pending message, it receives that message; otherwise it adds itself to the list of waiting recipients and then blocks.

Note: Operations on synchronous channels from the structure rendezvous-channels do not work on asynchronous channels.

 -- procedure: make-async-channel returns async-channel
 -- procedure: async-channel? obj returns boolean
     Make-async-channel creates and returns an asynchronous channel. Async-channel? is the disjoint type predicate for asynchronous channels.

 -- procedure: receive-async-rv channel returns rendezvous
 -- procedure: receive-async channel returns value (may block)
     Receive-async-rv returns a rendezvous that, when synchronized, becomes enabled when a message is available in CHANNEL's queue of messages.  Receive-async has the effect of immediately synchronizing such a rendezvous and, when the rendezvous becomes enabled, returning the value itself, rather than the rendezvous; (receive-async CHANNEL) is equivalent to (sync (receive-async-rv CHANNEL)).

 -- procedure: send-async channel message returns unspecified
     Sends a message to the asynchronous channel CHANNEL.  Unlike the synchronous channel send operation, this procedure never blocks arbitrarily long. (However, asynchronous channels are implemented by a thread that manages two synchronous channels (one for sends & one for receives), so this may block briefly if the thread is busy receiving other send or receive requests.)  There is, therefore, no need for a send-async-rv like the send-rv for synchronous channels.  If there is a waiting message recipient, the message is delivered to that recipient; otherwise, it is added to the channel's message queue.

Rendezvous-synchronized cells
-----------------------------

Placeholders: single-assignment cells
.....................................

Placeholders (Called I-variables in Reppy's CML, and I-structures in ID-90.) are single-assignment cells on which readers block until they are assigned.

Note: These placeholders are disjoint from and incompatible with the placeholder mechanism provided in the placeholders structure, and attempts to apply operations on one to values of the other are errors.

 -- procedure: make-placeholder [id] empty placeholder
 -- procedure: placeholder? object returns boolean
     Make-placeholder creates and returns a new, empty placeholder. ID is used only for debugging purposes; it is included in the printed representation of the placeholder.  Placeholder? is the disjoint type predicate for placeholders.

 -- procedure: placeholder-value-rv placeholder returns rendezvous
 -- procedure: placeholder-value placeholder returns value (may block)
     Placeholder-value-rv returns a rendezvous that, when synchronized, becomes enabled when PLACEHOLDER has a value, with that value.  Placeholder-value has the effect of immediately synchronizing such a rendezvous, and it returns the value directly, but possibly after blocking.

 -- procedure: placeholder-set! placeholder value returns unspecified
     Sets PLACEHOLDER's value to be VALUE, and enables all rendezvous for PLACEHOLDER's value with that value.  It is an error if PLACEHOLDER has already been assigned.

Jars: multiple-assignment cells
...............................

Jars (Termed M-variables in Reppy's CML.) are multiple-assignment cells on which readers block.  Reading from a full jar has the effect of emptying it, enabling the possibility of subsequent assignment, unlike placeholders; and jars may be assigned multiple times, but, like placeholders, only jars that are empty may be assigned.

 -- procedure: make-jar [id] returns empty jar
 -- procedure: jar? object returns boolean
     Make-jar creates and returns a new, empty jar.  ID is used only for debugging purposes; it is included in the printed representation of the jar.  Jar? is the disjoint type predicate for jars.

 -- procedure: jar-take-rv jar returns rendezvous
 -- procedure: jar-take jar returns value (may block)
     Jar-take-rv returns a rendezvous that, when synchronized, becomes enabled when JAR has a value, which is what value the rendezvous becomes enabled with; when that rendezvous is enabled, it also removes the value from JAR, putting the jar into an empty state.  Jar-take has the effect of synchronizing such a rendezvous, may block because of that, and returns the value of the jar directly, not a rendezvous.

 -- procedure: jar-put! jar value returns unspecified
     Jar-put! puts VALUE into the empty jar JAR.  If any taker rendezvous are waiting, the first is enabled with the value, and the jar is returned to its empty state; otherwise, the jar is put in the full state.  Jar-put! is an error if applied to a full jar.

Concurrent ML to Scheme correspondence
--------------------------------------

CML name   Scheme name
structure CML        structure threads
version              (no equivalent)
banner               (no equivalent)
spawnc               (no equivalent; use spawn and lambda)
spawn                spawn
yield                relinquish-timeslice
exit                 terminate-current-thread
getTid               current-thread
sameTid              eq? (R5RS)
tidToString          (no equivalent; use the writer)
  structure threads-internal
hashTid              thread-uid
  structure rendezvous
wrap                 wrap
guard                guard
withNack             with-nack
choose               choose
sync                 sync
select               select
never                never-rv
alwaysEvt            always-rv
joinEvt              (no equivalent)
  structure rendezvous-channels
channel              make-channel
sameChannel          eq? (R5RS)
send                 send
recv                 receive
sendEvt              send-rv
recvEvt              receive-rv
sendPoll             (no equivalent)
recvPoll             (no equivalent)
  structure rendezvous-time
timeOutEvt           after-time-rv
atTimeEvt            at-real-time-rv
structure SyncVar    structure rendezvous-placeholders
exception Put        (no equivalent)
iVar                 make-placeholder
iPut                 placeholder-set!
iGet                 placeholder-value
iGetEvt              placeholder-value-rv
iGetPoll             (no equivalent)
sameIVar             eq? (R5RS)
  structure jars
mVar                 make-jar
mVarInit             (no equivalent)
mPut                 jar-put!
mTake                jar-take
mTakeEvt             jar-take-rv
mGet                 (no equivalent)
mGetEvt              (no equivalent)
mTakePoll            (no equivalent)
mGetPoll             (no equivalent)
mSwap                (no equivalent)
mSwapEvt             (no equivalent)
sameMVar             eq? (R5RS)
structure Mailbox    structure rendezvous-async-channels
mailbox              make-async-channel
sameMailbox          eq? (R5RS)
send                 send-async
recv                 receive-async
recvEvt              receive-async-rv
recvPoll             (no equivalent)