xref: /dports/lang/scheme48/scheme48-1.9.2/doc/src/thread.tex

% Part of Scheme 48 1.9.  See file COPYING for notices and license.

% Authors: Richard Kelsey, Jonathan Rees, Mike Sperber, Robert Ransom

\chapter{Threads}

% safety (and the lack thereof)

This chapter describes Scheme~48's thread system: Scheme~48 threads
are fully preemptive; all threads (currently) run within a single
operating system process.  Scheme~48 allows writing customized, nested
schedulers, and provides numerous facilities for the synchronization
of shared-memory programs, most importantly \textit{proposals} for
optimistic concurrency.

\section{Creating and controlling threads}

The bindings described in this section are part of the \code{threads}
structure.
%
\begin{protos}
\proto{spawn}{ thunk}{thread}
\proto{spawn}{ thunk name}{thread}
\end{protos}
%
\code{Spawn} creates a new thread, passes that thread to the current
scheduler, and instructs the scheduler to run \cvar{thunk} in that
thread.  The \cvar{name} argument (a symbol) associates a symbolic
name with the thread; it is purely for debugging purposes.
%
\begin{protos}
\protonoresult{relinquish-timeslice}{}
\protonoresult{sleep}{ time-in-milliseconds}
\protonoresult{terminate-current-thread}{}
\end{protos}
%
\code{Relinquish-timeslice} instructs the scheduler to run another
thread, thus relinquishing the timeslice of the current thread.
\code{Sleep} does the same and asks the scheduler to suspend the
current thread for at least \cvar{time-in-milliseconds} milliseconds
before resuming it.  Finally, \code{terminate-current-thread}
terminates the current thread.

Each thread is represented by a thread object.  The following
procedures operate on that object:
%
\begin{protos}
\proto{current-thread}{}{thread}
\proto{thread?}{ thing}{boolean}
\proto{thread-name}{ thread}{name}
\proto{thread-uid}{ thread}{integer}
\end{protos}
%
\code{Current-thread} returns the thread object associated with the
currently running thread.
\code{Thread?} is the predicate for thread objects.
\code{Thread-name} extracts the name of the thread, if one was
specified in the call to \code{spawn}, \code{\#f} otherwise.
\code{Thread-uid} returns the \textit{uid} of the thread, a unique
integer assigned by the thread system.

\section{Advanced thread handling}

The following bindings are part of the \code{threads-internal} structure:
%
\begin{protos}
\protonoresultnoindex{terminate-thread!}{ thread}\mainschindex{terminate-thread"!}
\protonoresultnoindex{kill-thread!}{ thread}\mainschindex{kill-thread"!}
\end{protos}
%
\code{Terminate-thread!} unwinds the thread
associated with \cvar{thread}, running any pending \code{dynamic-wind}
\cvar{after} thunks (in that thread), after which the thread
terminates.  \code{Kill-thread!} causes the thread associated with
\cvar{thread} to terminate immediately without unwinding its continuation.
%


\section{Debugging multithreaded programs}

Debugging multithreaded programs can be difficult.

As described in section~\ref{command-threads}, when any thread signals an
 error, Scheme~48 stops running all of the threads at that command level.

 The following procedure (exported by the structure
 \code{debug-messages}) is useful in debugging multi-threaded
 programs.
\begin{protos}
\protonoresult{debug-message}{ element$_0$ \ldots}
\end{protos}
\code{Debug-message} prints the elements to `\code{stderr}', followed by a
 newline.
The only types of values that \code{debug-message} prints in full are small
 integers (fixnums), strings, characters, symbols, booleans, and the empty list.
Values of other types are abbreviated as follows:
%
\begin{center}
\begin{tabular}{ll}
 pair       &   \code{(...)}\\
 vector     &   \code{\#(...)}\\
 procedure  &   \code{\#\{procedure\}}\\
 record     &   \code{\#\{<name of record type>\}}\\
 all others &   \code{???}\\
\end{tabular}
\end{center}
%
The great thing about \code{debug-message} is that it bypasses Scheme~48's
 I/O and thread handling.
The message appears immediately, with no delays or errors.

\section{Optimistic concurrency}
\label{sec:optimistic-concurrency}

Most of the bindings described in this section are part of the \code{proposals}
structure---the low-level bindings described at the very end of the
section are part of the \code{low-proposals} structure.

A \cvar{proposal} is a record of reads from and and writes to locations in
 memory.  Each thread has an associated \textit{current proposal}
 (which may be \code{\#f}).
The \cvar{logging} operations listed below record any values read or
 written in the current proposal.
A reading operation, such as \code{provisional-vector-ref}, first checks to
 see if the current proposal contains a value for the relevant location.
If so, that value is returned as the result of the read.
If not, the current contents of the location are stored in the proposal and
 then returned as the result of the read.
A logging write to a location stores the new value as the current contents of
 the location in the current proposal; the contents of the location itself
 remain unchanged.

\cvar{Committing} to a proposal verifies that any reads logged in
 the proposal are still valid and, if so, performs any writes that
 the proposal contains.
A logged read is valid if, at the time of the commit, the location contains
 the same value it had at the time of the original read (note that this does
 not mean that no change occurred, simply that the value now is the same as
 the value then).
If a proposal has an invalid read then the effort to commit fails; no change
 is made to the value of any location.
The verifications and subsequent writes to memory are performed atomically
 with respect to other proposal commit attempts.
% Explain better?

The \code{queues} structure (with source in \code{scheme/big/queue.scm})
 is a thoroughly commented example of a moderately complex data structure
 made thread-safe using optimistic concurrency.

\begin{protos}
\proto{call-ensuring-atomicity}{ thunk}{value \ldots}
\protonoresultnoindex{call-ensuring-atomicity!}{ thunk}\mainschindex{call-ensuring-atomicity"!}
\syntaxproto{ensure-atomicity}{ \cvar{exp} \ldots}{value \ldots}
\syntaxprotonoresultnoindex{ensure-atomicity!}{ \cvar{exp} \ldots}\mainschindex{ensure-atomicity"!}
\end{protos}
\noindent
If there is a proposal in place
 \code{call-ensuring-atomicity} and \code{call-ensuring-atomicity!}
 simply make a (tail-recursive) call to \cvar{thunk}.
If the current proposal is \code{\#f} they create a new proposal,
 install it, call \cvar{thunk}, and then try to commit to the proposal.
This process repeats, with a new proposal on each iteration, until
 the commit succeeds.
\code{Call-ensuring-atomicity} returns whatever values are returned by \cvar{thunk}
 on its final invocation, while \code{ensure-atomicity!} discards any such
 values and returns nothing.

\code{Ensure-atomicity} and \code{ensure-atomicity!} are macro versions of
\code{call-ensuring-atomicity} and \code{call-ensuring-atomicity!}:
\code{(ensure-atomicity \cvar{exp} \ldots)} expands into
\code{(call-ensuring-atomicity (lambda () \cvar{exp} \ldots))}; likewise for
\code{ensure-atomicity!} and \code{call-ensuring-atomicity!}.

\begin{protos}
\proto{provisional-car}{ pair}{value}
\proto{provisional-cdr}{ pair}{value}
\protonoresultnoindex{provisional-set-car!}{ pair value}\mainschindex{provisional-set-car"!}
\protonoresultnoindex{provisional-set-cdr!}{ pair value}\mainschindex{provisional-set-cdr"!}
\proto{provisional-cell-ref}{ cell}{value}
\protonoresultnoindex{provisional-cell-set!}{ cell value}\mainschindex{provisional-cell-set"!}
\proto{provisional-vector-ref}{ vector i}{value}
\protonoresultnoindex{provisional-vector-set!}{ vector i value}\mainschindex{provisional-vector-set"!}
\proto{provisional-string-ref}{ vector i}{char}
\protonoresultnoindex{provisional-string-set!}{ vector i char}\mainschindex{provisional-string-set"!}
\proto{provisional-byte-vector-ref}{ vector i}{k}
\protonoresultnoindex{provisional-byte-vector-set!}{ vector i k}\mainschindex{provisional-byte-vector-set"!}
\end{protos}
\noindent
These are all logging versions of their Scheme counterparts.
Reads are checked when the current proposal is committed and writes are
 delayed until the commit succeeds.
If the current proposal is \code{\#f} these perform exactly as their Scheme
 counterparts.

The following implementation of a simple counter may not function properly
 when used by multiple threads.
\begin{example}
(define (make-counter)
  (let ((value 0))
    (lambda ()
      (set! value (+ value 1))
      value)))
\end{example}

Here is the same procedure using a proposal to ensure that each
 increment operation happens atomically.
The value of the counter is kept in a
cell (see section~\ref{cells})
 to allow the use of
 logging operations.
\begin{example}
(define (make-counter)
  (let ((value (make-cell 0)))
    (lambda ()
      (ensure-atomicity
        (lambda ()
          (let ((v (+ (provisional-cell-ref value)
                      1)))
            (provisional-cell-set! value v)
            v))))))
\end{example}

Because \code{ensure-atomicity} creates a new proposal only if there is
 no existing proposal in place, multiple atomic actions can be merged
 into a single atomic action.
For example, the following procedure increments an arbitrary number of
 counters at the same time.
This works even if the same counter appears multiple times;
 \code{(step-counters! c0 c0)} would add two to the value of counter \code{c0}.
\begin{example}
(define (step-counters! . counters)
  (ensure-atomicity
    (lambda ()
      (for-each (lambda (counter)
                  (counter))
                counters))))
\end{example}

\begin{example}
(define-synchronized-record-type \cvar{tag} \cvar{type-name}
  (\cvar{constructor-name} \cvar{field-tag} \ldots)
  [(\cvar \cvar{field-tag} \ldots)]
  \cvar{predicate-name}
  (\cvar{field-tag} \cvar{accessor-name} [\cvar{modifier-name}])
  \ldots)
\end{example}
This is the same as \code{define-record-type}
 except all field reads and
 writes are logged in the current proposal.
If the optional list of field tags is present then only those fields will
 be logged.

\begin{protos}
\proto{call-atomically}{ thunk}{value(s)}
\protonoresultnoindex{call-atomically!}{ thunk}\mainschindex{call-atomically"!}
\syntaxproto{atomically}{ \cvar{exp} \ldots}{value(s)}
\syntaxprotonoresultnoindex{atomically!}{ \cvar{exp} \ldots}\mainschindex{atomically"!}
\end{protos}
\noindent
\code{Call-atomically} and \code{call-atomically!} are identical
 to \code{call-ensuring-atomicity} and \code{call-ensuring-atomicity!} except that they
 always install a new proposal before calling \code{thunk}.
The current proposal is saved and then restored after \code{thunk} returns.
\code{Call-atomically} and \code{call-atomically!} are useful if \code{thunk} contains
 code that is not to be combined with any other operation.

\code{Atomically} and \code{atomically!} are macro versions of
\code{call-atomically} and \code{call-atomically!}:
\code{(atomically \cvar{exp} \ldots)} expands into
\code{(call-atomically (lambda () \cvar{exp} \ldots))}; likewise for
\code{atomically!} and \code{call-atomically!}.

% example?

The following procedures and macro are intended primarily for use in
 implementing new synchronization primitives or complex thread-safe data
 structures.
\begin{protos}
\syntaxproto{with-new-proposal}{ (\cvar{lose}) \cvar{exp} \ldots}{value \ldots}
\proto{maybe-commit}{}{boolean}
\proto{proposal-active?}{}{boolean}
\protonoresultnoindex{remove-current-proposal!}{}\mainschindex{remove-current-proposal"!}
\protonoresultnoindex{invalidate-current-proposal!}{}\mainschindex{invalidate-current-proposal"!}
\end{protos}
\noindent
\code{With-new-proposal} saves the current proposal, installs a new one,
 executes the forms in the body, reinstalls the formerly current proposal,
 and returns whatever the last body form returned.
It also binds \cvar{lose} to a thunk repeating the procedure of installing
 a new procedure and running the body.
Typically, the body will call \code{maybe-commit} and, if that fails,
 tail-call \cvar{lose} to try again.
If \cvar{lose} is called from a non-tail position of the body, the results
 are unspecified (and probably harmful).

\code{Maybe-commit} verifies that any reads logged in the current proposal are
 still valid and, if so, performs any writes that it contains.
A logged read is valid if, at the time of the commit, the location read contains
 the same value it had at the time of the original read (note that this does
 not mean that no change occurred, simply that the value now is the same as
 the value then).
\code{Maybe-commit} returns \code{\#t} if the commit succeeds and \code{\#f}
 if it fails.

\code{Proposal-active?} returns \code{\#t} if a proposal is active, and
 \code{\#f} otherwise.
\code{Remove-current-proposal!} removes and discards the current proposal;
 this can be used to clean up before raising an error.
\code{Invalidate-current-proposal!} ensures that any attempt to commit the
 current proposal will fail; this can be used if an operation on a
 thread-safe data structure detects that it has seen the data structure in an
 inconsistent state.



The following procedures give access to the low-level proposal
mechanism.  They are defined in the \code{low-proposals} structure.
\begin{protos}
\proto{make-proposal}{}{proposal}
\proto{current-proposal}{}{proposal}
\protonoresultnoindex{set-current-proposal!}{ proposal}\mainschindex{set-current-proposal"!}
\end{protos}
\noindent

\code{Make-proposal} creates a new proposal.
\code{Current-proposal} and \code{set-current-proposal} access and set
 the current thread's proposal.
It is an error to pass to \code{set-current-proposal!} a proposal that
 is already in use.


\section{Condition variables}
\label{sec:condition-variables}
% these require proposals

\textit{Condition variables} (defined in the \code{condvars}
structure) allow threads perform condition synchronization: It allows
threads to block, waiting for a specified condition---associated with a
condition variable---to occur, and other threads to wake up the waiting
threads when the condition is fulfilled.

Note that, in Scheme~48, condition variables work in conjunction with
proposals, not with mutex locks or semaphores, as in most other
implementations of this concept.

\begin{protos}
\proto{make-condvar}{}{condvar}
\proto{make-condvar}{ id}{condvar}
\proto{condvar?}{ thing}{boolean}
\protonoresultnoindex{set-condvar-has-value?!}{ condvar boolean}\mainschindex{set-condvar-has-value?"!}
\proto{condvar-has-value?}{ condvar}{boolean}
\protonoresultnoindex{set-condvar-value!}{ condvar value}\mainschindex{set-condvar-value"!}
\proto{condvar-value}{ condvar}{value}
\proto{maybe-commit-and-wait-for-condvar}{ condvar}{boolean}
\protonoindex{maybe-commit-and-set-condvar!}{ condvar value}{boolean}\mainschindex{maybe-commit-and-set-condvar"!}
\end{protos}
%
\code{Make-condvar} creates a condition variable.  (The optional
\cvar{id} argument is only for debugging purposes; the discloser for
condition variables prints it out if present.)  \code{Condvar?} is the
predicate for condition variables.

Each condition variable has an associated value and a flag
\code{has-value?} signalling if the condition has already occured.
The accessor for flag is \code{condvar-has-value?};
\code{set-condvar-has-value?!} sets it.  Both are provisional
operations and go through the current proposal.
\code{Set-condvar-value!} sets the value of the condition variable
(provisionally), and \code{condvar-value} extracts it.

\code{Maybe-commit-and-wait-for-condvar} attempts to commit the
current proposal.  If the commit succeeds, it suspends the current
thread and registers it with the \cvar{condvar} condition variable.
Upon waking up again \code{maybe-commit-and-wait-for-condvar} returns
\code{\#t}, If the commit fails, \code{maybe-commit-and-set-condvar}
returns \code{\#f}.

\code{Maybe-commit-and-set-condvar!} sets the value of the
\cvar{condvar} condition variable to \cvar{value}, (provisionally)
sets the \code{has-value?} flag to \code{\#t}, and then attempt to
commit the current proposal.  Upon success, it wakes up all suspended
threads registered with \cvar{condvar} and returns \code{\#t},
otherwise, it returns \code{\#f}.

\section{Mutual exclusion}

Scheme~48 also has more traditional mutual-exclusion synchronization
abstractions, specifically mutex locks and placeholders.  Note that
typically synchronization via optimistic concurrency is usually
preferable: Mutual exclusion often puts the running program into an
inconsistent state for the time of the inclusion, which has adverse
effects on modularity and interruptibility.

\subsection{Locks}

The \code{locks} structure contains bindings that implement standard
mutex locks:
%
\begin{protos}
\proto{make-lock}{}{lock}
\proto{lock?}{ thing}{boolean}
\protonoresult{obtain-lock}{ lock}
\proto{maybe-obtain-lock}{ lock}{boolean}
\protonoresult{release-lock}{ lock}
\end{protos}
%
\code{Make-lock} creates a lock in the ``released'' state.
\code{Lock?} is the predicate for locks.

\code{Obtain-lock} atomically checks if \cvar{lock} is in the
``released'' state.  If it is, the lock is put into the ``obtained''
state, and \code{obtain-lock} returns immediately.  If the lock is in
the ``obtained'' state, the current thread is suspended and registered
with the lock.
\code{Maybe-obtain-lock}, like \code{obtain-lock}, checks the state of
\cvar{lock}: if it is ``released,'' the lock is put into the
``obtained'' state, if it is ``obtained,'' \code{maybe-obtain-lock}
returns immediately.  \code{Maybe-obtain-lock} returns \code{\#t} if
it was able to obtain the lock, and \code{\#f} otherwise.

\code{Release-lock} does nothing if \cvar{lock} is in the ``released''
state.  If it is in the ``obtained'' state, \code{release-lock}
causes one of the threads suspended on an \code{obtain-lock} lock
operation to continue execution.  If that thread is the last thread
registered with the lock, the lock is transferred to the ``released''
state.  In any case, \code{release-lock} returns immediately.

\subsection{Placeholders}
\label{placeholders}

The \code{placeholders} structure contains bindings for
\textit{placeholders}---thread-safe, write-once variables, akin to
ID-90 I-structures or CML I-variables.

The typical scenario for placeholders is that, say, a thread~A
computes a value needed by another thread~B at some unspecified time.
Both threads share access to a placeholder; when A has computed the
value, it places it into the placeholder.  When B needs the value, it
extracts it from placeholder, blocking if necessary.
%
\begin{protos}
\proto{make-placeholder}{}{placeholder}
\proto{make-placeholder}{ id}{placeholder}
\proto{placeholder?}{ thing}{boolean}
\protonoresultnoindex{placeholder-set!}{ placeholder value}\mainschindex{placeholder-set"!}
\proto{placeholder-value}{ placeholder}{value}
\end{protos}
%
\code{Make-placeholder} creates an empty placeholder.  (The optional
\cvar{id} argument is only for debugging purposes; the discloser for
placeholders prints it out if present.)  \code{Placeholder?} is the
predicate for placeholders.

\code{Placeholder-set!} places a value into a placeholder.  Doing this
more than once signals an error.  \code{Placeholder-value} extracts
the value from the placeholder and returns it.  If the placeholder is
empty, it blocks the current thread until it becomes full.



\section{Writing custom synchronization abstractions}

The bindings explained in this section are part of the
\code{threads-internal} structure.  They are concerned with suspending
threads and making them runnable again upon some later event.

Typically, a suspended thread needs to be recorded in a queue
somewhere for later waking-up.  To allow a thread to be recorded in
multiple queues (say, when it waits for one of a number of events),
such \textit{thread queues} are ordinary queues containing cells that,
in turn, contain the thread objects themselves.  Each thread has at
most one such cell associated with it which is shared among all queues
(or other data structures) holding on to the suspended thread.  The
cell is cleared when the thread is woken up.
%
\begin{protos}
\proto{thread-queue-empty?}{ thread-queue}{boolean}
\protonoindex{maybe-dequeue-thread!}{ thread-queue}{boolean}\mainschindex{maybe-dequeue-thread"!}
\end{protos}
%
\code{Thread-queue-empty?} atomically checks whether the
\cvar{thread-queue} thread queue is empty, i.e., if it does not
contain non-empty cells.  \code{Maybe-dequeue-thread!} provisionally
dequeues a thread from \cvar{thread-queue} if it contains one.  It
returns the dequeued thread or \code{\#f} if the queue is empty.
%
\begin{protos}
\proto{maybe-commit-and-block}{ cell}{boolean}
\proto{maybe-commit-and-block-on-queue}{ thread-queue}{boolean}
\proto{maybe-commit-and-make-ready}{ thread-or-queue}{boolean}
\end{protos}
%
\code{Maybe-commit-and-block} attempts to commit the current proposal.
If this succeeds, the current thread is blocked, the thread's cell is
set to \cvar{cell}, and \code{\#t} is returned.  Otherwise, \code{\#f}
is returned.  \code{Maybe-commit-and-block-on-queue} is like
\code{maybe-commit-and-block}, excepts that it creates a fresh cell
for the thread and enqueues it in \cvar{thread-queue} if the commit
succeeds.

\code{Maybe-commit-and-make-ready} accepts either a thread object or a
thread queue as an argument.  In either case,
\code{maybe-commit-and-make-ready} tries to commit the current
proposal.  If that succeeds, \code{maybe-commit-and-make-ready}
makes its argument runnable: if \cvar{thread-or-queue} is a thread,
that thread is made runnable, if it is a thread queue, all threads on
the queue are made runnable.  (In the latter case, none of the threads
actually runs until all have been made runnable.)
\code{Maybe-commit-and-make-ready} returns \code{\#t} if it succeeded,
and \code{\#f} otherwise.

% \section{Writing your own schedulers}

\section{Concurrent ML abstractions}

The interface to the Concurrent ML abstractions in Scheme~48 is
mostly analogous to the original implementation shipped with
SML/NJ~\cite{Reppy:CML-book}.  Note that both the interface and
implementation are new and may change in future releases.

The main terminological difference is that CML events are called
\textit{rendezvous} in Scheme~48.  For more information on programming
with the CML abstractions, Reppy's book~\cite{Reppy:CML-book} is
recommended.

\subsection{Basic rendezvous combinators}

The basic rendezvous combinators live in the \code{rendezvous}
structure.
%
\begin{protos}
\constproto{never-rv}{rendezvous}
\proto{always-rv}{ value}{rendezvous}
\end{protos}
%
\code{Never-rv} is a rendezvous that is never enabled for
synchronization.  (It is the same as the \code{never} event in CML.)
\code{Always-rv} returns a rendezvous that is always enabled for
synchronization, and always yields the same value \cvar{value}.  (This
is the same as the \code{alwaysEvt} function in CML.)
%
\begin{protos}
\proto{choose}{ rendezvous \ldots}{rendezvous}
\end{protos}
%
\code{Choose} creates a rendezvous representing the choice of its
arguments:  Synchronization on the resulting rendezvous will
synchronize on one of the arguments to \code{choose}, depending on
which becomes enabled first.  (This is the same as the \code{choose}
function in CML.)
%
\begin{protos}
\proto{wrap}{ rendezvous proc}{rendezvous}
\end{protos}
%
\code{Wrap} wraps a post-synchronization procedure around \cvar{rendezvous}:
When the resulting rendezvous is synchronized, \cvar{rendezvous} is
synchronized, and the value it yields is passed to \cvar{proc}; the
value returned by \cvar{proc} then is the result of the
synchronization.  (This is the same as the CML \code{wrap} function.)
%
\begin{protos}
\proto{guard}{ thunk}{rendezvous}
\end{protos}
%
\code{Guard} delays the creation of a rendezvous until synchronization
time: It returns a rendezvous that will, upon synchronization, turn
into the rendezvous returned by \cvar{thunk}.  \code{Guard} can be
used to perform pre-synchronization actions such as resource
allocation.  (This is the same as the CML \code{guard} function.)
%
\begin{protos}
\proto{with-nack}{ proc}{rendezvous}
\end{protos}
%
\code{With-nack}, like \code{guard}, creates a delayed rendezvous: Upon
synchronization, the rendezvous actually used is the one returned by
\cvar{proc}.  In addition to the functionality offered by
\code{guard}, \cvar{proc} receives, as an argument, another rendezvous
which becomes enabled when \emph{another} rendezvous involved in the
synchronization (via \code{choose}) is picked instead of the one
produced by \cvar{proc}.  (This is the same as the CML \code{withNack}
function.)
%
\begin{protos}
\proto{sync}{ rendezvous}{value}
\proto{select}{ rendezvous \ldots}{value}
\end{protos}
%
\code{Sync} synchronizes the current thread on rendezvous
\cvar{rendezvous}, returning the value it yields.  \code{Select}
synchronizes on the choice of its argument; \code{(select $r_1$ \ldots
  $r_n$)} is semantically equivalent to \code{(sync (choose select $r_1$ \ldots
  $r_n$))}, but may be implemented more efficiently.  (These are the
same as the CML functions \code{sync} and \code{select}.)

\subsection{Synchronous channels}

The \code{rendezvous-channels} structure contains abstractions for
bidirectional, synchronous channels for communicating between two
threads.
%
\begin{protos}
\proto{make-channel}{}{channel}
\proto{channel?}{ x}{boolean}
\end{protos}
%
\code{Make-channel} creates a new synchronous channel.  (This is the
same as the CML \code{channel} function.)  \code{Channel?} is the
predicate for synchronous channels.
%
\begin{protos}
\proto{send-rv}{ channel value}{rendezvous}
\protonoresult{send}{ channel value}
\end{protos}
%
\code{Send-rv} creates a rendezvous that, upon synchronization, sends
message \cvar{value} on the synchronous channel \cvar{channel}.  The
synchronization suceeds only when another thread attempts to receive a
message from \cvar{channel}.  (This is the same as the CML
\code{sendEvt} function.)  \code{Send} directly sends a message
\cvar{value} on channel \cvar{channel}; \code{(send $c$ $v$)} is
equivalent to \code{(sync (send-rv $c$ $v$))}.  (\code{Send} is the
same as the CML \code{send} function.)
%
\begin{protos}
\proto{receive-rv}{ channel}{rendezvous}
\protonoresult{receive}{ channel}
\end{protos}
%
\code{Receive-rv} creates a rendezvous which, upon synchronization,
receives a message on channel \cvar{channel}.  (This is the same as
the CML \code{recEvt} function.)  \code{Receive} directly
receives a message on channel \cvar{channel}; \code{(receive $c$ $v$)} is
equivalent to \code{(sync (receive-rv $c$ $v$))}.  (\code{Receive} is
the same as the CML \code{recv} function.)

\subsection{Synchronous variables}

Two structures contain abstractions for synchronous variables: the
\code{rendezvous-placeholders} structure for so-called
\textit{placeholders} (write-once variables), and the
\code{rendezvous-jars} structure for \textit{jars} (which allow
multiple updates.)

\subsubsection{Placeholders}
%
Placeholders are write-once variables.  The placeholders implemented
by the \code{rendezvous-placeholders} structure offer equivalent
functionality to the placeholders implemented by the
\code{placeholders} structure (see Section~\ref{placeholders}), but
additionally allow converting a placeholder into a rendezvous.  Note,
however, that placeholders from \code{placeholders} are different from
and not interchangeable with placeholders from
\code{rendezvous-placeholders}.
%
\begin{protos}
\proto{make-placeholder}{}{placeholder}
\proto{make-placeholder}{ id}{placeholder}
\proto{placeholder?}{ x}{boolean}
\end{protos}
%
\code{Make-placeholder} creates an empty placeholder.  (The optional
\cvar{id} argument is only for debugging purposes; the discloser for
placeholders prints it out if present.)  (This is the same as the CML
\code{iVar} function.)  \code{Placeholder?} is the predicate for
placeholders.
%
\begin{protos}
\protonoresultnoindex{placeholder-set!}{ placeholder value}\mainschindex{placeholder-set"!}
\end{protos}
%
\code{Placeholder-set!} places a value into a placeholder.  Doing this
more than once signals an error.  (This is the same as the CML
\code{iPut} function.)
%
\begin{protos}
\proto{placeholder-value-rv}{ placeholder}{rendezvous}
\proto{placeholder-value}{ placeholder}{value}
\end{protos}
%
\code{Placeholder-value} extracts the value from the placeholder and
returns it.  If the placeholder is empty, it blocks the current thread
until it becomes full.  (This is the same as the CML \code{iGet}
function.)  \code{Placeholder-value-rv} creates a rendezvous that
will, upon synchronization, extract the value from the placeholder
and yield it as a result.  (This is the same as the CML \code{iGetEvt}
function.)

\subsubsection{Jars}

A jar is a synchronous variable which can have two states: full and
empty.  It becomes full when a value it put into it; putting a value
into a full jar is an error.  Conversely, it becomes empty when a
value is taken out of it.  Trying to take a value out of an empty jar
blocks until it becomes full.  (Jars are similar to ID-90
M-structures.)  Jars live in the \code{rendezvous-jars} structure.
%
\begin{protos}
\proto{make-jar}{}{jar}
\proto{make-jar}{ id}{jar}
\proto{jar?}{ x}{boolean}
\end{protos}
%
\code{Make-jar} creates an empty jar.  (The optional \cvar{id}
argument is only for debugging purposes; the discloser for jars prints
it out if present.)  (This is the same as the CML \code{mVar}
function.)  \code{Jar?} is the predicate for jars.

\begin{protos}
\protonoresultnoindex{jar-put!}{ jar value}\mainschindex{jar-put"!}
\end{protos}
%
\code{Jar-put!} places a value into a jar if it is empty.  Applying
\code{jar-put!} to a full jar is an error.  (This is the same as the
CML \code{mPut} function.)
%
\begin{protos}
\proto{jar-take-rv}{ placeholder}{rendezvous}
\proto{jar-take}{ placeholder}{value}
\end{protos}
%
\code{Jar-take} takes a value from a full jar, emptying it in the
process.  If the jar is empty, \code{jar-take} blocks until it becomes
full.  (This is the same as the CML \code{mTake} function.)
\code{Jar-take-rv} creates a rendezvous that, upon synchronization,
will extract the value from a jar and empty it in the process.  (This
is the same as the CML \code{mTakeEvt} function.)

\subsection{Timeouts}

The \code{rendezvous-time} structure allows creating rendezvous for
alarms and timeouts:
%
\begin{protos}
\proto{after-time-rv}{ milliseconds}{rendezvous}
\proto{at-real-time-rv}{ time}{rendezvous}
\end{protos}
%
\code{After-time-rv} creates a rendezvous that becomes enabled at time
interval \cvar{milliseconds} after synchronization.  (Actually,
\cvar{milliseconds} is a minimum waiting time; the actual delay may be
longer.)  (This is the same as the CML \code{timeOutEvt} function.)
\code{At-real-time-rv} creates a rendezvous that becomes enabled at an
absolute time specified by \cvar{time}; this absolute time is
specified in the same way as the return value \code{real-time} from
the \code{time} structure.  (This is the same as the CML
\code{atTimeEvt} function.)

\subsection{CML to Scheme correspondence}

The following table lists the Scheme names that correspond to
particular CML names.

\texonly\begin{longtable}{ll}\endtexonly
\htmlonly\begin{tabular}{ll}\endhtmlonly
  CML name & Scheme name\\\hline
  \multicolumn{2}{c}{\code{rendezvous}}\\
  \code{never} & \code{never-rv}\\
  \code{alwaysEvt} & \code{always-rv}\\
  \code{choose} & \code{choose}\\
  \code{wrap} & \code{wrap}\\
  \code{guard} & \code{guard}\\
  \code{withNack} & \code{with-nack}\\
  \code{sync} & \code{sync}\\
  \code{select} & \code{select}\\[1ex]
  \multicolumn{2}{c}{\code{rendezvous-channels}}\\
  \code{channel} & \code{make-channel}\\
  \code{sendEvt} & \code{send-rv}\\
  \code{send} & \code{send}\\
  \code{recEvt} & \code{receive-rv}\\
  \code{rec} & \code{receive}\\[1ex]
  \multicolumn{2}{c}{\code{rendezvous-placeholders}}\\
  \code{iVar} & \code{make-placeholder}\\
  \code{iPut} & \code{placeholder-set!}\\
  \code{iGet} & \code{placeholder-value}\\
  \code{iGetEvt} & \code{placeholder-value-rv}\\[1ex]
  \multicolumn{2}{c}{\code{rendezvous-jars}}\\
  \code{mVar} & \code{make-jar}\\
  \code{mTake} & \code{jar-take}\\
  \code{mTakeEvt} & \code{jar-take-rv}\\
  \code{mPut} & \code{jar-put!}\\[1ex]
  \multicolumn{2}{c}{\code{rendezvous-time}}\\
  \code{timeOutEvt} & \code{after-time-rv}\\
  \code{atTimeEvt} & \code{at-real-time-rv}
\texonly\end{longtable}\endtexonly
\htmlonly\end{tabular}\endhtmlonly


%%% Local Variables:
%%% mode: latex
%%% TeX-master: "manual"
%%% End: