Since I started learning Common Lisp in late 2016 I have been working on
several iterations of my own generative art framework. The first
library was named snek.
Some time later,
snek was rewritten and renamed as weir. The most essential parts
of these frameworks were a graph
data structure, utilities for dealing with (primarily 2d/3d)
vectors, as well
After getting more comfortable with Common
and armed with some suggestions from my friend Jack Rusher, I started to rewrite the
vector part of
In order to use the
weir was rewritten yet again.
Despite all the rewrites, some version of all this code has been used to make most of the art I have made in the period since then.
For the most part I have been pretty happy with it as well. But there has also been a number of things that didn't work very well. In particular, the graph had a number of issues that kept causing headaches.
As a result of this—ever so slight—obsession with building my own tools for things, I have once again committed programming crimes. This time I have written a new graph library called cl-grph. Writing a lot of kind of terrible code can be quite educational, and I have tried to improve on some of the mistakes of my (not so distant) past.
Immutable Data Structures
As many people have learned before me, dealing with state can be rather tedious. Mutating state even more so. Particularly when you have a series of complicated things you want to alter at the same time. Frequently without knowing up front whether it will work or not.
To improve on this I decided to use immutable data structures. This makes it trivial to access the state as it was before you started making any changes. If you discover any conflicts along the way, rolling back is simply a matter of not keeping the reference to the mutated state. Transactions are now almost trivial.
Immutable data structures have a few other neat properties as well. What immediately comes to mind is that they make it a lot easier to store multiple states of a structure as it is growing. Among other things this can be used for animation and debugging. Not to mention that it reduces the probability of causing unintended changes when sharing data from inside the library with the outside environment.
Unlike my previous graph structures, the new graph is directed. This creates a few complications, but it is also extremely useful. It is now possible to represent much more complex information. Where previously I could only easily represent that two vertices are associated, I can now model detailed hierarchies, trees and transport networks. Which will certainly be useful.
Which brings me to another major difference. In the new graph structure the edge properties are an integral part of the data structure. Not just an afterthought. This makes it more seamless to propagate edge properties when manipulating the datas tructure.
To utilise the graph structure more easily I have implemented a Datalog query compiler. Datalog is declarative logic programming language, with its roots in Prolog. I quite recommend looking into Datalog in more detail on your own. But I will give a small introduction to how my implementation works, using the following graph as an example.
Considering the example graph, we can write a Datalog query to return every edge:
g is the current graph(qry g :select (?x ?y) :where (?x _ ?y)) ;; ;; ((0 7) (0 8) (1 2) (1 8) ;; (2 7) (3 4) (3 6) (4 8) ;; (5 7) (5 8) (6 7))
In this query we are effectively saying "
pair of vertices
?x has any (
_) edge pointing at vertex
:where part must always contain at least
one "triplet" like you see above. It can contain more complex expressions, as
we will illustrate shortly.
Notice that the edges have direction, so
(0 7) is distinct from
(7 0). Also note that it is possible to have both directions of an
edge present in the graph at the same time. We avoid that here for practical
reasons. Likewise, it is possible to have conflicting properties on edges.
To select the combination of every edge, and its corresponding properties, we can do the following:
(qry g :select (?x ?p ?y) :where (?x ?p ?y)) ;; ;;
The result is sorted by property and;;
formatted slightly for readability:;; ((6 :black 7) (5 :black 8) (5 :black 7) ;; (4 :black 8) (3 :black 6) (3 :black 4) ;; (5 :bold 8) (5 :bold 7) (2 :bold 7) ;; (1 :bold 8) (1 :bold 2) ;; (6 :dots 7) (5 :dots 8) (5 :dots 7) ;; (4 :dots 8) (3 :dots 6) (3 :dots 4) ;; (2 :red 7) (1 :red 8) (1 :red 2) ;; (0 :red 8) (0 :red 7) ;; (2 :solid 7) (1 :solid 8) (1 :solid 2) ;; (0 :solid 8) (0 :solid 7) ;; (6 :thin 7) (4 :thin 8) (3 :thin 6) ;; (3 :thin 4) (0 :thin 8) (0 :thin 7))
We see that every edge is returned once for every property it has. If we want
to select all
:red edges that are
:bold, we can do
(qry g :select (?x ?y) :where (and (?x :red ?y) (?x :bold ?y))) ;; ;; ((2 7) (1 8) (1 2))
If you compare this result to the full list of properties and edges, you
should be able to see a pattern; the three resulting edges are all listed in
the full result with both a
:red and a
property. In other words, the
and clause performs a set intersection.
If you do the same query with
or instead, you get the larger set
of edges that are either a
corresponds to the set union:
(qry g :select (?x ?y) :where (or (?x :red ?y) (?x :bold ?y))) ;; ;; ((5 8) (5 7) (2 7) (1 8) ;; (1 2) (0 8) (0 7))Expanding on this we can select all
:boldedges, except those that are
(qry g :select (?x ?y) :where (and (or (?x :red ?y) (?x :bold ?y)) (not (?x :dots ?y)))) ;; ;; ((0 7) (0 8) (1 2) (1 8) (2 7))
not is the set
All the examples so far have effectively selected edges. But this is not necessary. To get all vertices we can write:
(qry g :select ?x :where (or (?x _ _) (_ _ ?x)) :collect ?x) ;; ;; (0 1 2 3 4 5 6 7 8)
:collect isn't strictly necessary, but so far the library
always returns each result as a list, unless otherwise specified.
If you for some reason only want even vertex indices, you can use a filter
(qry g :select ?x :where (and (or (?x _ _) (_ _ ?x)) (% (evenp ?x))) :collect ?x) ;; ;; (0 2 4 6 8)
Filters are similar to
not, but they support arbitrary code.
You can reference all variables in the query as long as they are "bound" by
What if you want all vertices that are associated with a
edge? An immediate attempt at a query might be
(qry g :select ?x :where (and (?x :red _)) :collect ?x) ;; ;; (0 1 2)
We quickly see that there are some vertices missing. Remembering that the edges in the graph are directed, we can get the correct result with:
(qry g :select ?x :where (or (?x :red _) (_ :red ?x)) :collect ?x) ;; ;; (1 2 7 0 8)
Vertex properties are not supported in
grph yet, but it is still
possible to reference vertices directly. Here is a query that will find all
vertices connected to
(qry g :select ?x :where (or (0 _ ?x) (?x _ 0)) :collect ?x) ;; ;; (7 8)
If we need any part of the query to be more dynamic, it is possible to use the
(let ((?v (rnd:rndi 9))) ;
random integer(qry g :select ?x :in ?v :where (or (?v _ ?x) (?x _ ?v)) :collect (list ?x ?v)) ;; ;;
which might yield:;; ((0 7) (2 7) (5 7) (6 7))
Before we move on, note that dynamic input can be used for any variable in the query. But every triplet must have at least one free variable.
Queries and Mutation
This is by no means a comprehensive description of Datalog, but it's a pretty good start. To illustrate what the library can do a little bit further, here are two short examples of how to use queries to modify the graph.
Say you want to change a particular set of edges. The following query finds
:blue edges, deletes them, and makes reversed
:green :bold edges instead:
^g references the mutated graph; g the initial(qry g :select (?x ?y) :using ^g :where (?x :blue ?y) :then (progn (del! ^g ?x ?y) (add! ^g ?y ?x '(:green :bold))))
Similarly, if you want to split all the
:dots edges at a random
point along the edge:
p is the initial spatial data associated with the graph;
as above ^g and ^p are mutated in the query(grph:qry g :select (?x ?y) :using (^g ^p) :where (?x :dots ?y) :collect (xgrph:2split! ^g ^p ?x ?y (veq:f2lerp (xgrph:[email protected] p ?x ?y) (rnd:rnd)))) ;; ;;
collects and yields the result of 2split!;;
In this case, the newly created vertices:;; (9 10 11 12 13 14)
This looks more involved, and I won't go into details of how this works. I include it here at the end as an example of how I hope to experiment with this system further.
Hopefully I have been able to nudge your interest or imagination a tiny bit. I have yet to use this library a lot, but the artworks included in this article are all created using the new library (as well as cl-veq and weird).
The algorithm is named
idling, and It is an amalgamation of a
few different things I have experimented with at different times in the past. Including
wide paths for plotter drawings and "spiraling" random walks.
There is an interesting dissonance in the juxtaposition of something that is obviously drawn by a computer, and something that someone might have drawn during an exceedingly boring meeting.
- Jack should not be blamed for any of the bad decisions in the code; which is to say he is not to blame for any of the code.
- Here is a related talk i enjoy. And here is a shorter version of the same talk if you are pressed for time.
- This solves some issues I was trying to solve in the old version of this code in a much more round-about way.
- I would say eliminates, but it is remarkable how many new and exciting ways you can make a foot-gun with code.
- What Datalog looks like will vary depending on the programming language and library involved. This particular implementation and behaviour is modeled after the query language in Datomic, but you should not take this to be a comprehensive (or even correct) representation of how Datalog works. Perhaps I will learn that myself some day.
- This is a little more complex in the actual code. For an edge to
have a matchable property
:colorwith the value
:red, it actually has two different properties, with corresponding values;
(:red t). This is a limitation of my implementation, and I won't go into the details here. Sorry.
- Until I decide to rewrite everything yet again.