Lem And Trurl
Thu Sep 7, 2017So cellular automata.
It turns out that things like life and Brian's Brain are the tip of the iceberg. I mentioned a series of videos by Dave Ackley that talks about Robust-First Computing, and simulating the sorts of machines he's got in mind for the deep future involves a surprising1 number of cells or similar constructs.
I've been thinking about this while putting together a basic testing/playing sandbox in the form of lem and trurl2.
By the way, in addition to the repo, you can play around with a trurl server here, assuming it hasn't exploded in the meantime. No promises; there's no uptime guarantee on this one yet. There are multi-player implications that I haven't really worked out yet, and I'm hoping to target them a lot more specifically in a forthcoming spin-off project. Stay tuned.
lem
lem itself is minimal. Apart from the system/package definition boilerplate, it's contained inside of one file. Its core, not counting the grid simulator that I'll also explain to you, is one macro that currently exposes an interface for defining new machines, and then instantiating them.
;;; lem.lisp
...
(defmacro define-machine (name &body body)
(let ((neighborhood (gensym "NEIGH")))
`(progn
(defclass ,name (unit)
((code :initform ',body)
(behavior
:initform
(lambda (,neighborhood)
(flet ((neighbor (x y) (get-neighbor ,neighborhood x y)))
(let* ((here (neighbor 0 0))
(self (occupant here)))
(declare (ignorable here self))
,@body))))))
(defun ,name (&rest state-k/v-pairs)
(make-instance ',name :state (alexandria:plist-hash-table state-k/v-pairs))))))
...
At a high level, this lets you use the form define-machine, passing it a name and a body, and get from it a representation of your machine. The body you pass in also has access to the locally-scoped function neighbor, and the locally scoped symbols here and self, all of which let you more naturally refer to the neighborhood of the cell that will eventually be running your machine. That body form can best be thought of as a behavior; it's what an instance of your machine will do to its neighborhood whenever its "turn" comes around.
The current underlying representation of a machine is a subclass of unit which sets some defaults, and a function that creates an instance of that class with the potential for some initial state. This is likely only temporary, and I entirely reserve the right to change said representation once I start thinking about multiplayer and game-related implications.
One of the simplest3 machines you could define is
...
(define-machine ray
(spawn-in! (neighbor -1 0) self))
...
Which is an example machine that Dave goes through in one of his videos. What this does, is start an infinite line that goes west. Whenever it's a ray cell's turn, it will spawn a copy of itself in the neighbor immediately to its left. Note that we're following Ackley's very necessary convention here; there is no absolute cell index, and each cell thinks of itself as 0,0 with its surrounding neighborhood as some offset from that. The neighborhood a given cell has access to on its turn also doesn't extend infinitely in all directions.
A demo of ray might be in order before we get into how turns work, and how a grid is simulated...
; SLIME 2.19
CL-USER> (ql:quickload :lem)
To load "lem":
Load 1 ASDF system:
lem
; Loading "lem"
..
(:LEM)
CL-USER> (in-package :lem)
#<PACKAGE "LEM">
LEM> (defparameter +grid+ (make-grid 30 10))
+GRID+
LEM> (seed! +grid+ 25 5 (ray))
NIL
LEM> (show! +grid+)
..............................
..............................
..............................
..............................
..............................
.........................+....
..............................
..............................
..............................
..............................
NIL
LEM> (play! +grid+)
..............................
..............................
..............................
..............................
..............................
........................++....
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
.......................+++....
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
......................++++....
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
.....................+++++....
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
....................++++++....
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
...................+++++++....
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..................++++++++....
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
.................+++++++++....
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
................++++++++++....
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
..............................
...............+++++++++++....
..............................
..............................
..............................
..............................
C-c C-c
Interrupt from Emacs
[Condition of type SIMPLE-ERROR]
Restarts:
0: [CONTINUE] Continue from break.
1: [RETRY] Retry SLIME REPL evaluation request.
2: [*ABORT] Return to SLIME's top level.
3: [ABORT] abort thread (#<THREAD "repl-thread" RUNNING {1002A47FA3}>)
LEM>
So you saw the basic interface to our grid simulations here. We can make a new grid by giving it a width and height, print it using show!, and put down cells using seed!. Finally, play! loops forever by stepping the grid once and show!ing it afterwards. The only part of this process you might not be able to infer reliably is what exactly it means to step! a grid...
...
(defmethod step! ((sim-grid grid))
(loop for y from 0 repeat (height sim-grid)
do (loop for x from 0 repeat (width sim-grid)
for g = (get-cell sim-grid x y)
unless (empty? g)
do (funcall
(behavior (occupant g))
(neighborhood-of sim-grid x y))))
nil)
...
...and that turns out to be the simplest cellular automata game I've ever written. For each cell, unless it's empty?, run its occupants behavior, passing it pointers to its immediate neighborhood. Note that this means that a given cell can mutate all of its neighboring cells arbitrarily during its "turn". Note also that this particular implementation of step! assumes a fixed order for cells to be given a turn. That's something I'm thinking about fixing by randomizing the order on each step!.
Something like
...
(let ((indices (loop for y from 0 repeat (height sim-grid) append (loop for x from 0 repeat (width sim-grid) collect (cons x y)))))
(loop for (x . y) in (shuffle indices)
do ... ))
...
would make sure that a given cell can't count on beating out any particular neighbor in terms of turn order. This is relevant, because we're building a grid simulation. The real situation we're anticipating is that each cell is going to be its own node on a massive network, which means that there can't possibly be a central authority for turn order.
In fact, that gives me the thought that turn consistency can't really be guaranteed in the real world. Which makes perfect sense if you think of each cell as a separate computer. It can compute anything, any time it likes, but all that taking a "turn" means is that it has consent from its neighbors to perform mutations on their memories for some duration of time. So in some sense, when your "turn" hits is a decision made collectively by your immediate neighborhood. The whole neighborhood might not agree, whether maliciously or through a coordination error, which seems to imply that a given cell might have to act on its neighborhood in partial "turns" during which it'll only have permission to write to some of its immediate neighbors. It seems like this doesn't materially change the behavior of the grid, other than to make it mildly less consistent. So maybe the "fix" should include something more like ... (shuffle (drop (5% (length indices)) indices)) ....
There seems to be a bunch of interesting ways you could change the behavior of these simulations without even considering the behaviors of the individual cells. We could introduce various degrees of inconsitency or order in the step! procedure as seen above, we might introduce more elaborate behavior for the spawn-in! procedure, or we could mess with the size/shape of a neighborhood a given cell gets access to during its turn. We could do the same sort of randomized dropping of neighbor cells when generating a neighborhood for behavior consumption, and those changes might have visible effects on the macro scale behavior of a grid.
The current structure of a neighborhood, rather than those experimental ones, is a three-cell-radius region centered on the cell whose "turn" it is.
CL-USER> lem:n*extended
((-4 0) (-3 -1) (-3 0) (-3 1) (-2 -2) (-2 -1) (-2 0) (-2 1) (-2 2) (-1 -3)
(-1 -2) (-1 -1) (-1 0) (-1 1) (-1 2) (-1 3) (0 -4) (0 -3) (0 -2) (0 -1) (0 0)
(0 1) (0 2) (0 3) (0 4) (1 -3) (1 -2) (1 -1) (1 0) (1 1) (1 2) (1 3) (2 -2)
(2 -1) (2 0) (2 1) (2 2) (3 -1) (3 0) (3 1) (4 0))
CL-USER>
or, in a slightly more readable format,
( (0 -4)
(-1 -3)(0 -3)(1 -3)
(-2 2)(-1 -2)(0 -2)(1 -2)(2 -2)
(-3 -1)(-2 1)(-1 -1)(0 -1)(1 -1)(2 -1)(3 -1)
(-4 0)(-3 0)(-2 0)(-1 0)(0 0)(1 0)(2 0)(3 0)(4 0)
(-3 1)(-2 -1)(-1 1)(0 1)(1 1)(2 1)(3 1)
(-2 -2)(-1 2)(0 2)(1 2)(2 2)
(-1 3)(0 3)(1 3)
(0 4))
Its implementation isn't all that relevant because, if you recall the define-machine macro, the only access a behavior has into its given neighborhood is through the local neighbor function. That function takes x/y, and returns a cell, so the underlying datastructure is effectively hidden from the user.
...
(defmethod neighborhood-of ((grid grid) x y)
(loop for (xd yd) in n*extended
for new-x = (+ xd x) for new-y = (+ yd y)
when (array-in-bounds-p (spaces grid) new-x new-y)
collect (cons (cons xd yd) (get-cell grid new-x new-y))))
...
Factually, it's an alist at the moment, but you don't have to care about that in order to understand the intent.
So that's about it. You understand the basic behavior of this cell simulator, as well as the basic concepts underpinning the definition of new machines, and you understand a few axes on which we might vary the base rules of a system in order to possibly vary its macro-scale behavior. It'd be nice if we could test this in some way...
trurl
trurl is a minimal web interface and API hooked up to allow modification of a lem:grid by spawning a fixed set of new cells. It still doesn't have all the machines I'm hoping to put in as defaults, and it still doesn't allow design of custom machines, but it does allow someone to poke at a grid graphically and observe the macro-level behavior.
This is the least complete part of the project at the moment, but there are enough unanswered questions bouncing around my head that I thought it better to record them now rather than waiting on completion before starting this blog post. The main default cell types I'd want to implement before calling that part "done" are ff and gg.
gg is the thing I built the simulator to consider more fully. It's a fairly simple machine definition:
(define-machine gg
(loop for (x y) in n*extended
for (spawn-in! (neighbor x y) self)))
For each neighbor in its given neighborhood, it replicates itself (overwriting whatever was there). It seems like, in a giant distributed system where each "grid space" is going to be running code that it can't really trust, someone somewhere is going to think about evaluating something like this, and I want to know what possible mitigation strategies are4.
ff is sort of a benign version of gg. I guess. For some value of "benign".
(define-machine ff
(loop for (x y) in n*extended
for c = (neighbor x y)
do (when (empty? c) (spawn-in! c self))))
It has most of the same implications as gg, but it avoids stomping on existing cells and instead "merely" consumes all available space.
The big feature I'd like apart from additional default machines is the ability for users to define their own machines in-flight. And that's going to take some thought. The first approach I can see is defining a separate package that doesn't do the usual (:use #:cl) for machine definition, and doing a separate interning step on incoming definitions to make sure any symbols we try to evaluate come from that package. We could still use the usual shadowing tricks to provide some extra symbols, or contingent definitions for some of them. The key, though, is making sure that only a "safe" subset of Common Lisp, which means cherrypicking only things from cl that don't allow any kind of file, socket or probably stream output. I'd want to deny arbitrary mutation too, otherwise it'd be possible for a sufficiently clever attacker to get shit through. If I did this well enough, it would naturally allow multiple definition languages with varying power (which could provide a decent skill progression tree in a game context).
That's that. I'll keep you posted on further developments, probably something like a week or two after they unfold.
- Or possibly unsurprising, depending on exactly how much thinking you've done on the subject.↩
lem, by pun-analogy to the Ulam platform that Ackley uses, andtrurlas a further appropriate joke that, fortunately, needs no explanation.↩- Not the simplest, obviously, because that would be
(define-machine lemon nil), which merely keeps existing until something changes that. As a side note, I'm using the namelemonbecause of the vernacular expression regarding "sitting there like a"; I'm well aware that in reality, lemons at the very least know how to build a new lemon tree out of soil, water and oxygen.↩ - There is the obvious; introduce some sort of cost for calling
spawn-in!. If there's no better way, that's a decent approach, but I have this conceit that you could have a post-scarcity situation where grey goo or analogues still don't necessarily take over. And applying costs has implications for that conceit. Beyond that though, introducing cost for spawning isn't an in-system solution to the problem. So it doesn't translate to situations where you'd want to mitigategg-like scenarios, but don't necessarily have alteration privileges on the underlying substrate.↩
