Table of Contents
Calispel is a Common Lisp library for thread-safe message-passing channels, in the style of the occam programming language.
Calispel channels let one thread communicate with another, facilitating unidirectional communication of any Lisp object. Channels may be unbuffered, where a sender waits for a receiver (or vice versa) before either operation can continue, or channels may be buffered with flexible policy options.
Because sending and receiving on a channel may block, either operation can time out after a specified amount of time.
A syntax for alternation is provided (like ALT
in occam, or Unix select()): given a sequence of
operations, any or all of which may block, alternation selects
the first operation that doesn't block and executes associated
code. Alternation can also time out, executing an "otherwise"
clause if no operation becomes available within a set amount of
time.
Many CSP- and occam-style channel libraries offer features
like parallel execution (i.e. occam PAR). Calispel
is a message-passing library, and as such leaves the role of
threading abstractions and utilities left to be filled by
perfectly good, complementary libraries such
as Bordeaux-Threads
and Eager
Future.
The latest version of Calispel, with accompanying documentation, can be found at: http://www.thoughtcrime.us/software/calispel/
The most recent release is 0.1, released 2009-10-19. It depends on: jpl-queues 0.1, cl-jpl-util 0.2, Eager Future 0.1, Bordeaux Threads
I sign all my software with OpenPGP, key ID 0x80555CED7394F948, fingerprint 2771 AF53 5D09 BDFB A8D0 BEF3 8055 5CED 7394 F948.
The software and this document are licensed under permissive, BSD-like terms, copied from the ISC license:
Copyright © 2009, Jean-Paul Guy Larocque
Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies.
THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
This software was directly derived from "csp.tgz", dated 2006-07-03, and published by Roger Peppe. No copyright notice giving attribution to Roger Peppe or any specific licensing terms seem to have been included in that version.
That software was derived from "channel.c" of Plan 9 libthread:
Copyright © 2005 Russ Cox, Massachusetts Institute of Technology
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
That software contains parts derived from an earlier library by Rob Pike, Sape Mullender, and Russ Cox:
Copyright © 2003 by Lucent Technologies.
Permission to use, copy, modify, and distribute this software for any purpose without fee is hereby granted, provided that this entire notice is included in all copies of any software which is or includes a copy or modification of this software and in all copies of the supporting documentation for such software.
THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR LUCENT TECHNOLOGIES MAKE ANY REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
Create a channel with no buffering:
(defparameter *chan* (make-instance 'calispel:channel))
In another thread, sleep for 1 second, then send the number
42 to the channel. In the current thread, receive from the
channel. At first, there will be no value available,
so ?
will wait until the other thread sends the value.
(progn
(eager-future:pexec
(sleep 1)
(calispel:! *chan* 42))
(calispel:? *chan*))
=> 42
T(42 is the value received,
and T indicates that the receive was
successful—it did not time out.)
Sending to the channel will also block without a waiting receiver, because channels are unbuffered by default. This will attempt to send to the channel, then time out after 2 seconds:
(calispel:! *chan* 'foo 2) => NIL
(NIL indicates that the send was not
successful—it timed out.)
Create a new channel that is buffered:
(defparameter *chan*
(make-instance 'calispel:channel
:buffer (make-instance 'jpl-queues:bounded-fifo-queue :capacity 2)))This channel will accept up to two values that have not yet been received before sends will block:
(loop for i from 1
while (calispel:! *chan* i 0)
finally (format t "~&Stopped before ~:R value.~&" i))
>> Stopped before third value.Now let's print them back out:
(loop
(multiple-value-bind (value success?)
(calispel:? *chan* 0)
(when success?
(format t "~&Value: ~S~&" value))
(unless success?
(return))))
>> Value: 1
Value: 2Suppose that we have many channels that we're interested in receiving from or sending to. We can use alternation to select the first operation that is available, and then perform some action associated with the operation:
(let ((chan1 (make-instance 'calispel:channel)) ; chan1 goes unused
(chan2 (make-instance 'calispel:channel)))
(eager-future:pexec
(calispel:! chan2 42))
(calispel:pri-alt
((calispel:? chan1)
;; Nothing is sent to CHAN1, so it can't be ready.
(format t "~&Got a value from CHAN1, but that should never happen.~&"))
((calispel:? chan2 value)
;; CHAN2 has either had something sent to it, or it soon will,
;; so this will execute.
(format t "~&Got value from CHAN2: ~S~&" value))))
>> Got value from CHAN2: 42What if there's more than one operation that is immediately
possible? PRI-ALT
chooses the first one available...
(let ((chan1 (make-instance 'calispel:channel))
(chan2 (make-instance 'calispel:channel)))
(eager-future:pexec
(calispel:! chan1 'foo))
(eager-future:pexec
(calispel:! chan2 'bar))
(sleep 1) ; Wait for both CHAN1 and CHAN2 to become ready.
(calispel:pri-alt
((calispel:? chan1 value)
(format t "~&Got value from CHAN1: ~S~&" value))
((calispel:? chan2 value)
(format t "~&Got value from CHAN2: ~S~&" value))))
>> Got value from CHAN1: FOO...whereas FAIR-ALT
chooses any of the available operations:
(let ((chan1 (make-instance 'calispel:channel))
(chan2 (make-instance 'calispel:channel)))
(eager-future:pexec
(calispel:! chan1 'foo))
(eager-future:pexec
(calispel:! chan2 'bar))
(sleep 1) ; Wait for both CHAN1 and CHAN2 to become ready.
(calispel:fair-alt
((calispel:? chan1 value)
(format t "~&Got value from CHAN1: ~S~&" value))
((calispel:? chan2 value)
(format t "~&Got value from CHAN2: ~S~&" value))))
>> Got value from CHAN1: FOO
(or, determined randomly)
>> Got value from CHAN2: BARJust
like ?
and !, PRI-ALT
and FAIR-ALT allow time outs to be
specified. An OTHERWISE clause is executed if no
operation can be immediately performed, effectively putting a
time out of 0 on all the operations:
(let ((chan1 (make-instance 'calispel:channel))
(chan2 (make-instance 'calispel:channel)))
(eager-future:pexec
(sleep 1)
(calispel:! chan1 'foo))
(calispel:pri-alt
((calispel:? chan1 value)
(format t "~&Got value from CHAN1: ~S~&" value))
((calispel:? chan2 value)
(format t "~&Got value from CHAN2: ~S~&" value))
(otherwise (format t "~&Timed-out.~&"))))
>> Timed-out.You can also wait up to a certain amount of time before
executing the OTHERWISE clause:
(let ((chan1 (make-instance 'calispel:channel))
(chan2 (make-instance 'calispel:channel)))
(eager-future:pexec
(sleep 1)
(calispel:! chan1 'foo))
(calispel:pri-alt
((calispel:? chan1 value)
(format t "~&Got value from CHAN1: ~S~&" value))
((calispel:? chan2 value)
(format t "~&Got value from CHAN2: ~S~&" value))
((otherwise :timeout 5)
(format t "~&Timed-out.~&"))))
>> Got value from CHAN1: FOO(Try increasing the SLEEP delay to 6
to see that the PRI-ALT will still time
out.)
Syntax.
(MAKE-INSTANCE'CHANNEL&keyBUFFER) => (ACHANNELinstance.)
A channel is a medium that communicates messages from one thread to another.
All channels have a buffer. The default buffer doesn't do anything—it's always full and always empty. It has no storage.
BUFFER specifies
the jpl-queues
queue to buffer messages with.
Sending to a channel blocks when there is no other thread
waiting to receive from it and there is no room in the buffer
(i.e. JPL-QUEUES:FULL?
returns true). Receiving from a channel blocks when there is
no other thread waiting to send to it and there are no objects
in the buffer
(i.e. JPL-QUEUES:EMPTY?
returns true).
To improve throughput with better parallelism, a meaningful buffer is recommended so that threads can perform useful work instead of waiting on other threads. Any jpl-queues queue may be used, but note:
JPL-QUEUES:SYNCHRONIZED-QUEUE): Calispel has
its own synchronization, so external synchronization will only
add overhead.Syntax.
(?CHANNEL&optionalTIMEOUT) =>VALUERECEIVED-OK?
(!CHANNELVALUE&optionalTIMEOUT) =>SENT-OK?
? receives a value
from CHANNEL, waiting up
to TIMEOUT seconds (a
non-negative REAL
number; or indefinitely if unspecified
or NIL). If a value can be received before
the time out, the value and T (indicating
success) are returned. Otherwise, NIL
and NIL (indicating failure) are
returned.
! sends VALUE
to CHANNEL, waiting up
to TIMEOUT seconds (a
non-negative REAL
number; or indefinitely if unspecified
or NIL). If the value can be sent before
the time out, T (indicating success) is
returned. Otherwise, NIL (indicating
failure) is returned.
Syntax.
(PRI-ALToperation-clause* [otherwise-clause]) (FAIR-ALToperation-clause* [otherwise-clause]) => (For either macro: the result of the final evaluatedform, or no values if no clause was executed.) operation-clause ::= (operationform*) otherwise-clause ::= ({otherwise | (otherwise [:timeouttimeout])}form*) operation ::= (?channel[lambda-list[condition]]) ; receive | (!channelvalue[condition]) ; send
Performs one of the given channel operations, choosing one
from the set of operations that first becomes available, then
evaluates each of the forms associated with the selected
operation. If no operation can immediately be made, waits
until an operation is available (optionally up to a given
timeout).
When there are multiple operations that can be immediately
carried-out, PRI-ALT selects the first
one listed, whereas FAIR-ALT chooses one
at random.
channelEvaluated to produce
a CHANNEL
to send to or receive from. The channel forms
associated with operations that do not pass the
condition are not evaluated.
lambda-listEither a symbol naming a variable to be bound to the value received from the channel, or a destructuring lambda list[1] naming a set of variables to be bound to the destructured value received from the channel. The bindings are visible to the associated forms. If the value cannot be destructured according to the lambda list, an error is signalled. Note that multiple receive clauses for the same channel with different destructuring lambda-lists cannot be used for pattern matching.
valueAn expression whose primary value is used as the message to send to the channel. All value expressions are evaluated before selecting an operation, except for those associated with operations that do not pass the condition.
conditionEvaluated to produce a generalized boolean indicating whether the associated operation-clause should receive further consideration. When condition is not given or its resulting value is true, the associated operation is kept for consideration. When the resulting value is false, the operation is removed from consideration (as if its associated channel never becomes ready for sending/receiving).
formEvaluated in sequence when the associated clause is executed. The values of the evaluation of the last form of the effective clause become the result of the macro.
timeoutEvaluated to produce the duration, as a non-negative
REAL
number of seconds, to wait for an effective operation to
become available before resorting to the
otherwise-clause. The result may also
be NIL to specify no time out. When
an otherwise-clause exists, the default
time out is 0, meaning that if none of the channels in
the operation-clauses are immediately available, the
otherwise-clause forms are executed
immediately. When there is
no otherwise-clause, the default time out
is
NIL.
It is useful to specify a timeout expression that
conditionally evaluates to NIL, in order to
disable the time out and inhibit the execution of the
otherwise-clause (provided that there are channel
operations to wait for that haven't been excluded by false
conditions).
If there are no effective operations (because all the
conditions evaluated to false, or because no operations were
specified), then the otherwise-clause (if any) is
executed immediately (even if the specified time out
is NIL).
Stylistically and for future compatibility, avoid
side-effects
in channel, value, condition,
and timeout expressions.
It is possible to dynamically construct a set of operations to alternate upon.
The general procedure is to
instantiate OPERATION for each kind of operation
you wish to perform. For sending operations, you will need to
give the value to send with :VALUE. Pass
the OPERATION instances, as a list,
to OPERATION-ALTERNATE. OPERATION-ALTERNATE
will either immediately execute one of
the OPERATION instances, or block until another
thread executes an operation which allows one of the given
operations to execute. The selected operation, after having
been executed, is returned. If the selected operation was a
receive operation, the value received will available with
the VALUE accessor.
Please see the documentation in the source code
for OPERATION-ALTERNATE and
the OPERATION class.