I've been learning Common Lisp since some time at the end of 2016. I wrote a little bit about why in my previous post. This text describes what I have been doing in some more detail. Specifically it describes an experimental data structure and—more importantly—a programming system or pattern.
For no particularly good reason I have named this system
The code is at https://github.com/inconvergent/snek.
I do not really know if this pattern is particularly novel, but at least I have not seen anything quite like this before. Moreover, I haven't decided whether I think that this is a good pattern. Having said that: it does seem quite useful to me, it is also fun to work with. Implementing it in Lisp has also proven to be an interesting challenge.
I tend to write code that performs some kind of growth. As an example, let us consider this differential growth algorithm.
For this to work I need to be able to iterate over all vertices in the structure, calculate a set of forces, and move the vertices according to those forces. I also want to be able to split edges by inserting new vertices at the middle of the edge. The important thing to notice here is that the forces depend on distances between vertices. This means that if we were to start moving vertices around while we are iterating, we will affect future distance calculations within the same iteration. This is not what you want.
In general this situation is common when doing simulation, and there are multiple ways of solving this. For instance you can introduce some kind of temporary state. That is, you can iterate over the vertices, calculate the new positions of each vertex, then append those changes later. Similarly, you can calculate a list of edges that need to be split, then perform the splits later.
Instead of working this way I propose the idea of alterations. An
alteration is an object that represents an action (alteration) that can be
performed on the structure at a later time. For instance
(20.0 10.0)) will create an alteration that, when (eventually)
applied to the structure, will move vertex
a 20.0 units along
the x-axis, and 10.0 units along the y-axis.
Similarly, you can have alterations like:
(join-verts a b), which will create edge
(a b)between vertices
(append-edge a 10.0 30.0), which will create a new vertex at
(10.0 30.0), and add an edge between that vertex and
(split-edge (a b)), which will split edge
(a b)by inserting a vertex in the middle.
Let us assume that we have an instance of
snk. For this pattern to work, you will need a way to apply
these changes to
snk. My solution is to create a context,
(with-snek (snk) ...), which will apply all alterations
created within it to
snk once the context is closed.
For instance, if you wanted to randomly move every vertex in
snk by some small amount, it will look like this:
; context start (with-snek (snk) ; iterate over all vertices in snk ; v is the current vertex in the iteration (with-all-verts (snk v) ; an alteration for each v (move-vert v (rnd-in-circ)))) ; context end ; alterations have been applied
(rnd-in-circ) returns a random coordinate from a uniform
distribution over the unit circle.
This is not entirely different from the original strategy of states, but
there are a few differences. With this method there is no need to
explicitly save state, the alterations represent changes that will be
applied at the end of the context. But the context will do this for you.
This also means that
snk does not change at all inside of the
context. This is important because it means you can freely grab information
snk without having to worry about the state.
In the above example the state does not actually matter. To illustrate
better, let's assume you also want to select a random vertex,
w, and create edge,
(v w). But you only want to
create this edge if they are within a certain distance of each other. Now
it looks like this:
; context start (with-snek (snk) ; iterate (with-all-verts (snk v) ; move alteration (move-vert v (rnd-in-circ)) ; w will be an arbitrary ; vertex in snk (with-rnd-vert (snk w) ; join v and w if they are closer than d (if (< (vert-dst snk (v w)) d) (join-verts v w)))) ; context end ; alterations have been applied
Here we can move vertices around without worrying that it will affect the
conditional join. We can also be certain that
...) will not select a vertex that has been inserted in the
current context: those alterations have not been applied yet.
Another useful thing about this pattern is that the code that generates the
alterations does not have to know anything about the underlying data
structure . In fact, you
can create alterations without even knowing anything about
snk. This makes it easy to generate alterations in code. It
also makes it easier to write code that generates code that creates
alterations. The latter is something I would like to achieve eventually.
This pattern also has the useful property of making it possible to
parallelize everything that happens inside of
Since alterations are created independently of each other there is nothing stopping you from creating alterations that does not make sense, or that will leave the structure in an inconsistent state. This means that we need a few strategies for how to apply alterations. I have not really experimented a lot with this yet, but a simple example is that we can simply silently discard alterations that will create duplicate edges. We can also implement the logic that applies each alterations such that we are certain that it is only applied provided that it does not create an inconsistent state.
More advanced structures will probably need more involved rules for applying the alterations. One might also want to randomize the order in which the alterations are applied. This way we can avoid systemic behaviour that we do not intend.
As mentioned earlier, this method is interesting for my kind of work, but obviously it has some important weaknesses. These weaknesses make it unsuitable in many cases. Most notably, if you need strict control over the final result, the discarding behaviour mentioned above could be impractical or catastrophic.
Finally I would like to mention that there is no specific reason why this
needs to be done in Lisp.
However, Lisp does have some highly useful constructs that makes it
appealing for a system like this. For instance, it is Lisp
macros that make it possible to elegantly create the contexts
(with-snek ...) and
(with-rnd-vert ...) above.
In addition, I think Lisp will be excellent for eventually writing code
that is capable of generating code that creates (and applies) alterations.
In the event that you would like to learn Lisp, I enjoyed reading Common LISP: A Gentle Introduction to Symbolic Computation. If you want to read more about Macros, and Lisp in general, I recommend On Lisp by Paul Graham.
- If you are unfamiliar with Lisp:
(func a b)is equivalent to
(a b), not
- Admittedly this can be achieved with most other structures and patterns as well.
- If you were to write this in another language you could use a map-reduce like pattern where you have a function that generates a list of alterations, and another function that applies those alterations to the structure.