The last post was about coroutines. Now we will show how these coroutines can be used for Discrete Event Simulation (DES).
Discrete Event Simulation in PicoLisp
As the name suggests, Discrete Event Simulation (DES) models systems by focusing on a sequence of distinct events. Instead of continuously tracking a system's state, DES jumps from one distinct event to another. This approach is frequently employed in gaming to simulate aspects like character behavior and crowd movements. By focusing on these key events, it gets much easier to understand and design complex behaviors without tracking every little detail.
Since pil21 version 22.1.18 (January 2022), PicoLisp has a DES library. You can find the code in lib/simul.l and the documentation in doc/des.html.
Using the DES library, we can simulate the behavior of agents which are realized as coroutines. These coroutines are driven by events. To manage these coroutines, we have several control options:
pause: pauses the coroutine either for a set duration or until a designated event takes place.event: Sends a signal to all coroutines awaiting that specific event.wake: Resumes a previously suspended coroutine.des: enables the simulation to "jump" from one event to another.
To understand how DES works, let's look at a famous programming problem: E. W. Dijkstra's "Dining Philosophers".
Note: The link to the final code can be found at the bottom of the page.
The Dining Philosophers
Task Description
Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers. Each philosopher thinks deeply and, intermittently, and interrupts their thoughts to eat from a bowl of spaghetti placed in front of them. However, to eat, they need two forks. A single fork is placed between each pair of adjacent philosophers. The crux of the problem is that each philosopher can only eat when they have both their left and right forks.
The problem was designed to illustrate the challenges of ensuring that several concurrent processes (e.g. the philosophers) can access shared resources (the forks) without conflict:
No two philosophers should be able to pick up the same fork at the same time (preventing race conditions).
Philosophers should not starve (fairness in accessing resources).
Deadlocks should be prevented (e.g. all philosophers having one fork in their left hand).
The Dining Philosophers is one of my favorite problem descriptions because it leaves so many questions hanging in the air: Why do they use two forks? Do the forks get cleaned in between? And which type of spaghetti is being served?
(Unfortunately, these questions will not be answered by the algorithm).
Because this is a modern blog, we will host a gender-parity party. Our dinner guests are Hannah Arendt, Hildegard v. Bingen, Rosa Luxemburg, Immanuel Kant, Friedrich Nietzsche and Ludwig Wittgenstein.
Loading the simul.l library
To use the DES functions, we need to load the library and declare the namespaces:
(load "@lib/simul.l")
(symbols 'dining-philosophers 'simul 'pico)
The symbols function defines the search hierarchy for symbols (e.g. variables, functions...). Initially, it searches within the local namespace, labeled dining-philosophers. If not found, it proceeds to the simul namespace specified in simul.l, and finally checks the pil21 namespace pico.
Defining the agents
Simply put, in our simulation each philosopher acts as an agent. And as previously mentioned, every agent operates as a coroutine. These agents have a singular task - dining - and to do so, they require two forks.
The forks are shared within all agents, e.g. they are globals. Following the PicoLisp conventions, we declare these global variables at the beginning and their name starts with an asterisk.
(local) (*ForkA *ForkB *ForkC *ForkD *ForkE *ForkF)
(co 'Arendt
(dining '*ForkA '*ForkB) )
(co 'v.-Bingen
(dining '*ForkB '*ForkC) )
(co 'Luxemburg
(dining '*ForkC '*ForkD) )
(co 'Kant
(dining '*ForkD '*ForkE) )
(co 'Nietzsche
(dining '*ForkE '*ForkF) )
(co 'Wittgenstein
(dining '*ForkF '*ForkA) )
(Since it's a round table, Wittgenstein is sharing his fork with Hannah Arendt.)
The "dining" function
Now to the heart of our program. We can define five stages for each agent:
Thinking: The philosopher is in a contemplative state and isn't looking to eat.
Hungry: The philosopher feels the need to eat.
Waiting for Forks: The philosopher waits to acquire the two forks if they're unavailable.
Picking Up Forks and Eating: Once the forks are free, the philosopher picks them up and begins to eat.
Putting Down the Forks: After eating, the philosopher releases the forks for others to use.
These five stages are continuously looped throughout the simulation.
The initial stage is straightforward: We display "<philosopher> is hungry..." and then pause the simulation. Assuming our simulation time is measured in minutes, each pause duration ranges between 180 and 240 minutes.
(de dining (LeftFork RightFork)
(loop
(prinl (pack (co) " is thinking... 💭"))
(pause (rand 180 240))
Note: To extract the coroutine tag we use (co), and the pack function converts all arguments to a single string.
Now we can simulate 20 event steps by calling the des function 20 times.
<...>
(co 'Wittgenstein
(dining '*ForkE '*ForkA) )
(do 20 (des))
Starting the script, we find all philosophers in deep thought.
$ ~/pil21/pil dining-philosophers.l
Arendt is thinking... 💭
v.-Bingen is thinking... 💭
Luxemburg is thinking... 💭
Kant is thinking... 💭
Nietzsche is thinking... 💭
<...>
After between 180 to 240 time units, the coroutine resumes. Now is the time to declare the next step: The philosopher is getting hungry. If both forks are available, they proceed to eat.
For our simulation, the act of "eating" involves setting the global fork values to a non-NIL value. It is convenient to set the value to the coroutine's tag, e.g. the philosopher's name:
(set LeftFork (set RightFork (co)))
(prinl (pack (co) " is eating! 🍝"))
(pause 20)
First, we need to check if both forks are free. If one or both forks are taken, our coroutine pauses. It will start again when it gets an event signal related to LeftFork or RightFork.
(while (or (val LeftFork) (val RightFork))
(prinl (pack (co) " has no fork!! 🤬🤬🤬" ) )
(pause LeftFork RightFork) )
Note: This part will be changed later to something more expressive.
Fortunately for our hungry philosophers, each meal lasts only 20 minutes. After that, the philosopher releases the forks. This action sends an event signal for the paused coroutines to resume:
(prinl (pack (co) " finished eating."))
(set LeftFork (set RightFork NIL))
(event LeftFork)
(event RightFork)
This is all we need for a fully functional simulation:
$ ~/pil21/pil dining-philosophers.l
Arendt is thinking... 💭
v.-Bingen is thinking... 💭
<...>
Nietzsche has no fork!! 🤬🤬🤬
Arendt finished eating.
Arendt is thinking... 💭
This simulation avoids deadlocks by two factors: both forks are always handled simultaneously, and coroutines waiting for forks are consistently queued behind others that are already waiting.
Managing the time
We've outlined the basic program structure but have yet to address an important aspect: Time simulation.
Within DES, there are two modes: Realtime and Simulated Time. These modes are determined by the *Rt global variable. If *Rt is set to NIL, it indicates simulated time. A value of 1 represents real-world clock speed, 2 double speed, and so on.
Since we do not want to wait 4 hours for all philosophers to finish thinking, let's stick with simulated time. To do so, we set *Rt to NIL at the beginning of our program:
(off *Rt)
To provide better insights into our program's process, we want to include a timestamp in our output. For this we introduce a function called now that prints the current time in HH:MM format, followed by the coroutine tag and a specified string. We can utilize the built-in tim$ function for this purpose.
(de now (Str)
(prinl (tim$ (* 60 *Time)) " " (co) " " Str) )
If we replace prinl with the now function in our code and run the program, the output will show timestamps. This makes it easy to verify that the thinking phase indeed lasts at least 3 "hours" and the eating phase takes exactly 20 "minutes".
$ ~/pil21/pil dining-philosophers.l
<...>
03:18 Nietzsche is hungry... 😋
03:18 Nietzsche has no fork!! 🤬🤬🤬
03:20 Arendt finished eating.
03:20 Arendt is thinking... 💭
03:20 Wittgenstein has no fork!! 🤬🤬🤬
As a last little gimmick, let's also add which fork is missing and who is using it:
<...>
(use (L R)
(while
(or
(setq L (val LeftFork))
(setq R (val RightFork)) )
(now (pack "waiting for " L (and L R " and ") R " 🤬🤬🤬 "))
(pause LeftFork RightFork) ) )
Which adds quite some drama to the dinner table!
11:05 Luxemburg is hungry... 😋
11:05 Luxemburg waiting for Kant 🤬🤬🤬
11:21 Nietzsche is hungry... 😋
11:21 Nietzsche waiting for Kant 🤬🤬🤬
Adding the main function
Having a main function is not a must, but it makes debugging the program easier. To set it up, we start by defining the main symbol. Next, we set up the namespace search order, and then we add the rest of our code.
(local) (main)
(de main()
(symbols '(dining-philosophers simul pico))
(co 'Arendt
<...>
Now we can start the script like this:
$ ~/pil21/pil dining-philosophers.l -dining-philosophers~main +
00:00 Arendt is thinking... 💭
00:00 v.-Bingen is thinking... 💭
00:00 Luxemburg is thinking... 💭
00:00 Kant is thinking... 💭
00:00 Nietzsche is thinking... 💭
00:00 Wittgenstein is thinking... 💭
dining-philosophers:
This will directly open a PicoLisp REPL in the correct namespace for debugging. Now you can verify the stack or run some more simulation steps with (des).
You can find the final code here.