(c) Software Lab. Alexander Burger
PicoLisp has a Discrete-Event
Simulation library in
The simulated objects (often called "Agents") are implemented as separate coroutines. These are created the normal way with co, and the library functions use yield to transfer control between them.
Only one coroutine may be running at one point in time. All others are either
A running coroutine can suspend itself, and cause another coroutine to resume, by either
The simulation can optionally run in realtime mode. In that case, it sleeps between the scheduled points in time, and accepts key strokes for user interaction.
The library consists of five global variables and four functions.
NIL, or 1 for wall clock speed, 2 for double speed etc.
(des [. prg])
*Readyuntil that queue is empty. Then - if
*Nextis not empty - advances the simulation to the next point in time, and resumes the corresponding coroutine. In that case, if in realtime mode, it delays execution as necessary, handles possible key presses, and runs
prgafter each key.
(pause ['cnt|sym] ..) -> any
*Nextfor a point in time after that number of time units. For symbolic arguments, the current coroutine is queued into those symbol's event queues. In any case, control is passed to the next coroutine.
(event 'sym [. prg])
symto all coroutines waiting in that symbol's event queue. As a result, these coroutines are removed from the queue and appended to the
*Readyqueue, with the optional
prgbody to be executed when resumed. The current coroutine continues to run.
(wake 'sym [. prg])
sym, by appending it to the
*Readyqueue with the optional 'prg' body to be executed when resumed. This means that if
symis currently waiting for a point in time in
*Next, it is removed from that index (i.e. the pause is aborted). Also, if
symis waiting for signals, it is removed from those event queues. The current coroutine continues to run.
A typical DES program will start some coroutines and let them perform their initial work until they need to pause.
That means, if a given operation in the simulation is supposed to take
cnt time units, this coroutine calls
pause with that
number. Or, if it depends on some signals from another part of the program, it
pause with those symbols. In any case - as it has nothing
else to do - it goes to sleep.
When all of them wait for a time or signal, control is returned to the main
program. All coroutines are now waiting in
*Next or some signal
event queue (or in
*Ready if they just gave up control with
The main program may now check
*Next and perhaps
*Ready. If both are empty, no further events can occur, and the
program may terminate.
Otherwise, it calls
des to continue with the next step(s).
At any time, a coroutine or the main program may call
example to interrupt another coroutine and cause it to throw into some other
context, or have that coroutine's
pause return a special value by
Let's use DES to demonstrate the well-known Dining Philosophers Problem.
Put the following code into a file "dining.l".
# 07sep23 Software Lab. Alexander Burger # Dining Philosophers # pil dining.l -dining~main + (load "@lib/simul.l") (symbols 'dining 'simul 'pico) (off *Rt) # Realtime mode off (local) (*ForkA *ForkB *ForkC *ForkD *ForkE now think) (de now (Str) (prinl (tim$ (* 60 *Time)) " " (co) " " Str) ) (de think (Left Right) (loop (now "thinking") (pause (rand 180 240)) # 3 to 4 hours (now "hungry") (while (or (val Left) (val Right)) (now "waiting") (pause Left Right) ) (set Left (set Right (co))) (now "eating") (pause 20) # 20 minutes (set Left (set Right NIL)) (event Left) (event Right) ) ) (local) main (de main () (symbols '(dining simul pico)) (co 'Aristotle (think '*ForkA '*ForkB) ) (co 'Kant (think '*ForkB '*ForkC) ) (co 'Spinoza (think '*ForkC '*ForkD) ) (co 'Marx (think '*ForkD '*ForkE) ) (co 'Russell (think '*ForkE '*ForkA) ) )
It uses five global variables
and five coroutines
Russell. They all run
the same function
think, with their neighboring forks as
think, each philospher is first "thinking" for a random time
between three and four hours. Then it gets "hungry", tries to pick up both
forks, and - if at least one of the forks is in use - starts "waiting" for a
left or right fork signal from another philosopher, and checks the forks again.
Now both forks are free. The philosopher puts himself into both (it could put
in fact any non-
NIL value), then is "eating" for 20 minutes,
releases both forks by setting them to
NIL, and sends a left and a
right fork signal to the neighboring philosophers possibly waiting for the
The simulation cannot deadlock, because both forks are picked up and released atomically, and because coroutines waiting for fork signals are always queued after the other waiting coroutines.
$ ./pil misc/dining.l -dining~main + 00:00 Aristotle thinking 00:00 Kant thinking 00:00 Spinoza thinking 00:00 Marx thinking 00:00 Russell thinking dining: (more (stack)) (Russell . 62) (Marx . 62) (Spinoza . 62) (Kant . 62) (Aristotle . 62) (T . 155) -> NIL dining: *Ready -> NIL dining: *Next -> ((229 . Kant) ((201 . Spinoza) ((198 . Russell) ((194 . Marx) ((180 . Aristotle)))))) dining: (des) 03:00 Aristotle hungry 03:00 Aristotle eating -> NIL dining: (des) 03:14 Marx hungry 03:14 Marx eating -> NIL dining: (des) 03:18 Russell hungry 03:18 Russell waiting -> NIL dining: (do 40 (des)) 03:20 Aristotle thinking 03:20 Russell waiting 03:21 Spinoza hungry 03:21 Spinoza waiting 03:34 Marx thinking 03:34 Spinoza eating 03:34 Russell eating 03:49 Kant hungry 03:49 Kant waiting 03:54 Russell thinking 03:54 Spinoza thinking 03:54 Kant eating 04:14 Kant thinking 06:27 Aristotle hungry 06:27 Aristotle eating 06:47 Aristotle thinking 06:47 Marx hungry 06:47 Marx eating 07:07 Marx thinking 07:40 Russell hungry 07:40 Russell eating 07:41 Kant hungry 07:41 Kant eating 07:47 Spinoza hungry 07:47 Spinoza waiting 08:00 Russell thinking 08:01 Kant thinking 08:01 Spinoza eating 08:21 Spinoza thinking 09:57 Aristotle hungry 09:57 Aristotle eating 10:17 Aristotle thinking 10:41 Marx hungry 10:41 Marx eating 11:01 Marx thinking 11:45 Spinoza hungry 11:45 Spinoza eating 11:50 Russell hungry 11:50 Russell eating 11:52 Kant hungry 11:52 Kant waiting 12:05 Spinoza thinking 12:05 Kant eating 12:10 Russell thinking 12:25 Kant thinking 13:57 Aristotle hungry 13:57 Aristotle eating 14:02 Marx hungry 14:02 Marx eating 14:17 Aristotle thinking 14:22 Marx thinking 15:40 Russell hungry 15:40 Russell eating 15:46 Spinoza hungry 15:46 Spinoza eating 15:52 Kant hungry 15:52 Kant waiting 16:00 Russell thinking 16:06 Spinoza thinking 16:06 Kant eating 16:26 Kant thinking 17:52 Aristotle hungry 17:52 Aristotle eating 18:12 Aristotle thinking 18:22 Marx hungry 18:22 Marx eating -> NIL dining: