Future Alterations

When I started learning Common Lisp I also started writing a framework for generative art. The first version was named snek. After a large refactoring it was renamed to weir. This is the current version.

In this framework drawings are represented as graphs. One of the ideas I wanted to explore was the ability to queue up future changes that will be applied to the graph. In weir this kind of future change is named an alteration.

The main motivation was to make it possible to create and collect a series of alterations, knowing that the current state of the graph is unaltered. When all alterations have been created, they will be applied, discarding any alterations that turn out to be invalid. This is made possible with a macro called (weir:with ...).

Another motivation was to create an expressive and readable DSL. Hiding some of the complexity of applying the alterations behind the scenes.

For simple cases this worked well enough, but I quickly realised that I wanted to create alterations that were dependent on other alterations inside the same context. Essentially I wanted a dependency graph of futures. Implementing this dependency graph seemed rather complicated, so I had mostly discarded it.

Since I made the first version of this functionality, I have only made a few technical improvements to the (weir:with ...) macro.

A few days ago I suddenly realised how I could easily implement the dependency graph.

The implementation isn't that interesting in itself. And I assume there are other people who have implemented this kind of dependency resolving more elegantly. However, I thought I'd share an example of how it lets me write an algorithm that almost looks like pseudo code.

The example below is an iterative algorithm that selects an edge in the graph at random. The selected edge is rotated by some angle, then split at the middle. Additionally, two new edges are appended at the split, perpendicular to the rotated edge. This process is repeated a number of times.

We assume that we have an initial graph instance, wer, with an initial seed edge. Furthermore the alteration, (add-edge? ...), will only do anything with a certain probability, and if the new edge does not intersect any existing edges.

; repeats n times:
; select a random edge, ee, from wer
(with-rnd-edge (wer ee)
  (let* ((vv (get-verts wer ee)) ; positions of edge
         (mid (get-mid vv)) ; midpoint of edge
         (angle (get-rnd-angle)) ; random angle
         (rotated (rotate vv mid angle))) ; rotate vv around mid

    (with (wer %)
      ; delete the selected edge
      (% (ldel-edge? ee))
      ; nev vertex in the middle, named :mid
      (% (add-vert? mid) :res :mid)
      ; two new verts, rotated relative to
      ;  initial edge, named :r1 and :r2
      (% (add-vert? (first rotated)) :res :r1)
      (% (add-vert? (second rotated)) :res :r2)

      ; four new edges from :mid to the
      ; new vertices :r1 and :r2; and the existing
      ; vertices of edge, ee
      ; :arg (:mid :r1) means that this alteration
      ; depends on :mid and :r1
      (% (add-edge? :mid :r1) :arg (:mid :r1))
      (% (add-edge? :mid :r2) :arg (:mid :r2))
      (% (add-edge? :mid (first ee)) :arg (:mid))
      (% (add-edge? :mid (second ee)) :arg (:mid)))))

You can read more about this functionality in the next post.