Dsim.cljc
Idiomatic and purely functional discrete event-simulation
Install / Use
/learn @helins/Dsim.cljcREADME
DSim
Compatible with Clojurescript.
Event-driven engine for Clojure(script) heavily borrowing ideas from discrete-event simulation and hybrid dynamical systems.
Uniquely useful for programs involving time or prioritization, in some way or another. Data science, simulations, games, animations, etc. Any program where any state needs to evolve methodically over time, over some order.
(inspired by the contrapuntal works of J.S. Bach)
- Socratic rationale
- Discrete-event simulation
- Continuous and hybrid simulation
- Serialization
- Async, parallelization, and optimizations problems
- Writing your own specific engine
- Last few words
- Running tests
- Development
Socratic rationale <a name="socratic-rationale">
Framing most of our programs as simulations opens up a new perspective that many software developers do not consider. However, Clojure already holds a special place when it comes to having notions about how values evolve over time. Starting slowly, step by step, we shall try to build a deeper understanding of time in the majority of programs we write. After a few entertaining examples, we hope the reader will reach an "Aha!" moment. We won't lie to you, it might need more than one read, but we believe that it is useful and that anyone can benefit from reconsidering the role of time in computation.
One might not have to strictly read linearly and might attempt to jump to sections of interest. After reading the first few sections, at least.
Ensuring you grabbed a nice cup of coffee, let us require what we need for our special hammock time to come:
(require '[dvlopt.dsim :as dsim])
Or clone this repo:
$ git clone https://github.com/dvlopt/dsim.clj
$ cd dsim.clj
$ clj -A:dev:test
# and your favorite REPL
Knowing our priorities <a name="knowing-our-priorities">
In one way or another, what is time but an information about ordering? In its simplest definition, time unravels as a sequence of events. A simple way to order function in Clojure would be to use sorted maps.
(sorted-map 41 event-1
42 (sorted-map 1 event-2
2 event-3))
By using a sorted map, it is trivial to "schedule" an event for any moment,
supposing that keys represent some point in time. By nesting them, it is trivial
to have higher-order prioritization. We can say that each event has ranks, a
lower rank meaning a higher priority. For instance, event-3 is ranked at [42 2].
Mixing time and space <a name="mixing-time-and-space">
For given ranks, more than one event might occur. We need to differentiate them.
(sorted-map 41 {:asteroids {:b-612 sunset}}
42 (sorted-map 1 {:characters {:little-prince watch-sunset}
37 {:characters {:little-prince feeling-happy}
:baobab grow}))
Instead of mere event functions, we now have nested unsorted maps of event
functions. Following ranks and then a path, the event we discover is now
located both in time and space. We can say that the feeling-happy event
happens to [:characters :little-prince] (which is the path, space) exactly at
[42 2] (which are ranks, time). A the same time, a :baobab is growing.
Such a data structure is what we decided to call a ranked tree, as our
unsorted maps are indeed "ranked" using sorted ones. Those ranked trees are the
core of DSim engines but are also available as an external library:
At the same time, but not exactly <a name="same-time">
Following the previous excerpt, we know that :little-prince first watches the
sunset and then feels happy. What really matters is that relative order.
Instead of using further ranking within [42], it would actually be best using
a queue.
(sorted-map 42 {:characters {:little-prince (dsim/queue watch-sunset
feeling-happy)}
:baobab grow})
A queue is simply a Clojure persistent queue, a lesser known data structure,
more convenient than a vector as we shall demonstrate all along. Besides clarity,
they bring safety. Indeed, if something fails and :little-prince is unable to
watch the sunset as intended, he will not feel happy because the whole queue
will fail.
While sorted maps provide precise timing towards the roots of our tree, queues as
leaves allow several events to be grouped at the same path, same ranks,
while usefully providing sequential ordering.
When modelling events happening conceptually at the same time, sometimes it is
still required to execute them in some sequence. We understand that
:little-prince feels happy right from the moment he stars watching the sunset,
virtually at the same time, but without watching it he would not be happy.
Feeling happy is dependent on watching the sunset, whereas :baobab growing
has nothing to do with all that and is independent from what is happening to
the :little-prince.
Modelling dependencies using a queue as a leaf is like saying: "Event B happens only after Event A".
Modelling dependencies using further ranking, as in our previous version, is like saying: "Event B happens no matter what, but if Event A happens, it must execute before Event B".
Creating time in our universe <a name="creating-time">
We have not discussed what those events actually do. What does it mean to feel happy? How does it impact the world, anything?
(defn feeling-happy
[ctx]
(assoc-in ctx
(conj (dsim/path ctx)
:mood)
:happy))
(def ctx
(dsim/e-conj {}
[42]
[:characters :little-prince]
feeling-happy))
Our universe is called a ctx (context). It contains some state as well as the
events modifying that state through time. Starting from an empty map, we have
scheduled happiness for path [:characters :little-prince] at ranks [42],
and void transformed into world. The API provides several e-XXX functions for
scheduling, removing, or retrieving events.
An event takes a ctx and returns an updated ctx. When it is executed, an
event has access to its path (a call to dvlopt.dsim/path suffice), meaning
it knows where it happens, what for. Feeling happy is not specific to the
:little-prince, we can easily reuse it for anyone else as evidenced by the
implementation.
Events scheduling events <a name="events-scheduling-events">
Because an event modifies a ctx and a ctx contains all scheduled events,
it stands to reason an event can schedule other events.
(defn feeling-happy
[ctx]
(let [path (dsim/path ctx)
future-ranks (update (dsim/ranks ctx)
0
+
100)]
(-> ctx
(assoc-in (conj path
:mood)
:happy)
(dsim/e-conj future-ranks
path
feeling-happy))))
Happiness is addictive. When someone feels happy, it is automatically
rescheduled in the future, at the same path. An event can easily retrieve its
ranks (calling dvlopt.dsim/ranks) and update them, just as happiness is here
rescheduled for 100 time units later.
Setting the universe into motion <a name="setting-into-motion">
Like Isaac Newton's god, after designing our universe, scheduling first events, we need to set it into motion. We shall use the "ptime engine". It considers that the first rank represent a specific point in time and applies additional contraints. For instance, that point in time can only increase and never decrease as one cannot go back in time. Following that first rank, it jumps from point in time to point in time, executing everything there is for a given point in time while respecting further ranking (if any).
(def run
(dsim/ptime-engine))
(def ctx
(run (dsim/e-conj {}
[42]
[:me]
feeling-happy)))
(= ctx
{:me {:mood :happy}
::dsim/events (sorted-map 142 {:me (dsim/queue feeling-happy)})
::dsim/ptime 42})
After our first run happening at point in time 42 (as indicated by the `::dsim/pti
