SNEK is Not an Acronym

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 snek. 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 (snek:move-vert? a (20d0 10d0)) will create an alteration that, when (eventually) applied to the structure, will move vertex a 20 units along the x-axis, and 10 units along the y-axis.

Similarly, you can have alterations like:

• (snek:join-verts? a b), which will create edge (a b) between vertices a and b;
• (snek:append-edge? a 10d0 30d0), which will create a new vertex at (10d0 30d0), and add an edge between that vertex and a; and
• (snek: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 snek called snk. For this pattern to work, you will need a way to apply these changes to snk. We do this by creating a context, (snek:with (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
(snek:with (snk)
  ; iterate over all vertices in snk
  ; v is the current vertex in the iteration
  (snek:itr-all-verts (snk v)
    ; an alteration for each v
    (snek:move-vert? v (rnd:in-circ 10d0))))
; context end
; alterations have been applied

Here (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 from 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
(snek:with (snk)
  ; iterate
  (snek:itr-all-verts (snk v)
    ; move alteration
    (snek:move-vert? v (rnd:in-circ 10d0))
    ; w will be an arbitrary
    ; vertex in snk
    (snek:with-rnd-vert (snk w)
      ; join v and w if they are closer than d
      (if (< (snek:vert-dst snk (list v w)) d)
        (snek: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 (snek:with-rnd-vert ...) 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 (snek:with ...).

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 (snek:with ...) and (snek: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.