s48-refman/thread/cml.texi

@node Concurrent ML
@section Concurrent ML

@cindex rendezvous
@cindex event
Scheme48 provides a high-level event synchronization facility based on
on Reppy's @dfn{Concurrent ML} [Reppy 99].  The primary object in CML
is the @dfn{rendezvous}@footnote{In the original CML, these were called
@dfn{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.

@menu

* Rendezvous concepts::
* Rendezvous base combinators::
* Rendezvous communication channels::
* Rendezvous-synchronized cells::
* Concurrent ML to Scheme correspondence::

@end menu

@node Rendezvous concepts
@subsection 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 @dfn{rendezvous} to accomplish this, which represents a potential
point of synchronization between processes.  The use of rendezvous
occurs in two stages: @dfn{synchronization} and @dfn{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 @dfn{synchronizes} that rendezvous.  This first polls
whether the resource is immediately available; if so, the rendezvous is
already @dfn{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@"used
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 @dfn{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 @dfn{delayed rendezvous with negative
acknowledgement}.

A rendezvous may also be a rendezvous @dfn{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).

@subsection Delayed rendezvous

A rendezvous may be @dfn{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.

@subsubsection 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 @dfn{negative acknowledgement rendezvous}, or @dfn{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.

@node Rendezvous base combinators
@subsection Rendezvous combinators

@stindex rendezvous
The @code{rendezvous} structure exports several basic rendezvous
combinators.

@defvr Constant never-rv @returns{} rendezvous
A rendezvous that is never enabled.  If synchronized, this will block
the synchronizing thread indefinitely.
@end defvr

@deffn 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.
@end deffn

@deffn procedure guard rv-generator @returns{} rendezvous
@deffnx procedure with-nack rv-generator @returns{} rendezvous
@code{Guard} returns a delayed rendezvous, generated by the given
procedure @var{rv-generator}, which is passed zero arguments whenever
the resultant rendezvous is synchronized.  @code{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 @code{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.
@end deffn

@deffn procedure choose rendezvous @dots{} @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.
@end deffn

@deffn procedure wrap rendezvous procedure @returns{} rendezvous
Returns a rendezvous equivalent to @var{rendezvous} but wrapped with
@var{procedure}, so that, when the resultant rendezvous is
synchronized, @var{rendezvous} is transitively synchronized, and when
@var{rendezvous} is enabled, the resultant rendezvous is also enabled,
with the value that @var{procedure} returns when passed the value
produced by @var{rendezvous}.

@lisp
(sync (wrap (always-rv 4)
            (lambda (x) (* x x))))      @returns{} 16@end lisp
@end deffn

@deffn procedure sync rendezvous @returns{} value (may block)
@deffnx procedure select rendezvous @dots{} @returns{} value (may block)
@code{Sync} and @code{select} synchronize rendezvous.  @code{Sync}
synchronizes a single one; @code{select} synchronizes any from the
given set of them.  @code{Select} is equivalent to @code{(sync (apply
choose @var{rendezvous @dots{}}))}, but it may be implemented more
efficiently.
@end deffn

@subsubsection Timing rendezvous

@cindex time
@stindex rendezvous-time
The @code{rendezvous-time} structure exports two constructors for
rendezvous that become enabled only at a specific time or after a delay
in time.

@deffn procedure at-real-time-rv milliseconds @returns{} rendezvous
@deffnx procedure after-time-rv milliseconds @returns{} rendezvous
@code{At-real-time-rv} returns a rendezvous that becomes enabled at the
time @var{milliseconds} relative to the start of the Scheme program.
@code{After-time-rv} returns a rendezvous that becomes enabled at least
@var{milliseconds} after synchronization (@emph{not} construction).
@end deffn

@node Rendezvous communication channels
@subsection Rendezvous communication channels

@subsubsection Synchronous channels

@cindex channels
@cindex synchronous channels
@cindex message-passing
@stindex rendezvous-channels
The @code{rendezvous-channels} structure provides a facility for
@dfn{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.'

@deffn procedure make-channel @returns{} channel
@deffnx procedure channel? object @returns{} boolean
@code{Make-channel} creates and returns a new channel.  @code{Channel?}
is the disjoint type predicate for channels.
@end deffn

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

@deffn procedure receive-rv channel @returns{} rendezvous
@deffnx procedure receive channel @returns{} value (may block)
@code{Receive-rv} returns a rendezvous that, when synchronized, and
when a sender rendezvous for @var{channel} with some message is
synchronized, becomes enabled with that message, at which point the
sender rendezvous is enabled with an unspecified value.  @code{Receive}
is like @code{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;
@code{(receive @var{channel})} is equivalent to @code{(sync (receive-rv
@var{channel}))}.
@end deffn

@subsubsection Asynchronous channels

@cindex channels
@cindex asynchronous channels
@cindex message-passing
@stindex rendezvous-async-channels
The @code{rendezvous-async-channels} provides an @dfn{asynchronous
channel}@footnote{Known as @dfn{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.

@strong{Note:} Operations on synchronous channels from the structure
@code{rendezvous-channels} do not work on asynchronous channels.

@deffn procedure make-async-channel @returns{} async-channel
@deffnx procedure async-channel? obj @returns{} boolean
@code{Make-async-channel} creates and returns an asynchronous channel.
@code{Async-channel?} is the disjoint type predicate for asynchronous
channels.
@end deffn

@deffn procedure receive-async-rv channel @returns{} rendezvous
@deffnx procedure receive-async channel @returns{} value (may block)
@code{Receive-async-rv} returns a rendezvous that, when synchronized,
becomes enabled when a message is available in @var{channel}'s queue of
messages.  @code{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;
@code{(receive-async @var{channel})} is equivalent to @code{(sync
(receive-async-rv @var{channel}))}.
@end deffn

@deffn procedure send-async channel message @returns{} unspecified
Sends a message to the asynchronous channel @var{channel}.  Unlike the
synchronous channel @code{send} operation, this procedure never blocks
arbitrarily long.@footnote{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 @code{send-async-rv} like the @code{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.
@end deffn

@node Rendezvous-synchronized cells
@subsection Rendezvous-synchronized cells

@subsubsection Placeholders: single-assignment cells

@stindex rendezvous-placeholders
@dfn{Placeholders}@footnote{Called @dfn{I-variables} in Reppy's CML,
and @dfn{I-structures} in ID-90.} are single-assignment cells on which
readers block until they are assigned.

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

@deffn procedure make-placeholder [id] @returns empty placeholder
@deffnx procedure placeholder? object @returns{} boolean
@code{Make-placeholder} creates and returns a new, empty placeholder.
@var{Id} is used only for debugging purposes; it is included in the
printed representation of the placeholder.  @code{Placeholder?} is the
disjoint type predicate for placeholders.
@end deffn

@deffn procedure placeholder-value-rv placeholder @returns{} rendezvous
@deffnx procedure placeholder-value placeholder @returns{} value (may block)
@code{Placeholder-value-rv} returns a rendezvous that, when
synchronized, becomes enabled when @var{placeholder} has a value, with
that value.  @code{Placeholder-value} has the effect of immediately
synchronizing such a rendezvous, and it returns the value directly, but
possibly after blocking.
@end deffn

@deffn procedure placeholder-set! placeholder value @returns{} unspecified
Sets @var{placeholder}'s value to be @var{value}, and enables all
rendezvous for @var{placeholder}'s value with that value.  It is an
error if @var{placeholder} has already been assigned.
@end deffn

@subsubsection Jars: multiple-assignment cells

@stindex rendezvous-jars
@dfn{Jars}@footnote{Termed @dfn{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.

@deffn procedure make-jar [id] @returns{} empty jar
@deffnx procedure jar? object @returns{} boolean
@code{Make-jar} creates and returns a new, empty jar.  @var{Id} is used
only for debugging purposes; it is included in the printed
representation of the jar.  @code{Jar?} is the disjoint type predicate
for jars.
@end deffn

@deffn procedure jar-take-rv jar @returns{} rendezvous
@deffnx procedure jar-take jar @returns{} value (may block)
@code{Jar-take-rv} returns a rendezvous that, when synchronized,
becomes enabled when @var{jar} has a value, which is what value the
rendezvous becomes enabled with; when that rendezvous is enabled, it
also removes the value from @var{jar}, putting the jar into an empty
state.  @code{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.
@end deffn

@deffn procedure jar-put! jar value @returns{} unspecified
@code{Jar-put!} puts @var{value} into the empty jar @var{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.  @code{Jar-put!} is an error if applied to a full jar.
@end deffn

@node Concurrent ML to Scheme correspondence
@subsection Concurrent ML to Scheme correspondence

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