The patterns of Barricelli

I've been obsessed recently with the work of Nils Aall Barricelli who pioneered cellular automata 15 years before John Conway, artificial life 20 years before Christopher Langton and chaos theory 15 years before Benoit Mandelbrot. Barricelli called his creation "symbioorganisms", but it's interesting to try to demystify them without any analogies with living organisms.

The playing field is a finite, circular 1D space of discrete squares. Squares can be occupied by one of many different kinds of elements. Each kind of element has a propensity to move through the space with a constant step. To this space of elements striding around, Barricelli adds 3 rules. (Well, he experimented with many different tweaks in his papers, but this is one concrete, elegant formulation.)

• Destruction: When two objects collide, delete both. (This isn't quite what Barricelli says. But it suffices!)
• Creation: When an object A moves to where a second object B used to be, make a new copy of it, somewhere nearby that depends on B.
• Mutation: This rule is slightly more difficult to explain, and I found the rules plenty interesting without using it in this post. In brief, empty squares sometimes create new kinds of elements.

Just adding the first 2 rules gives rise to some very interesting behavior. Here's a pretty picture:

In this picture, each row of pixels represents the state of the space at one point in time. Time moves from the bottom of the picture to the top. The space is seeded randomly with a few different kinds of elements. Elements that stride rightward are colored shades of green. Elements that stride leftward are colored shades of blue. Red pixels are empty squares.

This picture shows that at the start we have a lot more differences in color, but in a few generations the "populations" (coherent bands of color) quickly become more stable.

Zooming in, we see that what looks like flat shades of color are really extremely regular patterns of the different kinds of elements. These are Barricelli's "symbioorganisms".

How could this be? The different colors of elements stride in different directions at different rates. How do stable patterns emerge? Here's one example that shows what's going on:

Here I've annotated the zoomed-in view with each element's stride, and lines showing each element's motion. The blues (B) move 3 squares left per time step, while the greens (G) move 2 steps right. However, a configuration of BBGGG is stable with just these rules. Each pair of blues "switches partners" with a different triple of greens going the other way. The effect is of a stable periodic pattern with a period of 5 squares.

I've tried many different random initial conditions, and such periodic patterns always occur. Barricelli calls this phenomenon "spontaneous generation", and it is remarkably robust. The BBGGG pattern above is nowhere near the only possible organism. Another simple one is BBBGG:

Very similar phenomenon of groups of like elements "switching partners."

One example that suggests why these patterns robustly occur is to introduce a single empty (red) square into a field of BBBGG. What we see is the empty square "move" leftwards at a rate of 3 squares per time step — and it leaves to its right a growing field of BBGGG. Similar effect to a catalyst or enzyme.

The consistency with which periodic patterns occur is largely due to the balance between creation and destruction rules. Here's a different and much more complex periodic pattern elsewhere in the same space:

This is a complex pattern with a period of 25 squares, and for its stability it requires both destruction (places where the white lines of movement intersect, annihilating colliding elements) and creation (red lines that cause a square to create a second copy of itself).

Open questions

• I haven't dug into the third rule (mutation) yet to understand its effects in detail.
• Barricelli describes complex organisms arising from a random field of just +1s and -1s (i.e. elements striding 1 element leftward or rightward), but I have a simple proof that that can't happen with the rules as I've described them above. I'd like to understand how to tweak the rules to reproduce this result.
• Barricelli describes patterns that aren't stable by themselves, but can spread in the presence of "host patterns". He calls these parasites, though it may be more precise to compare them to viruses. I'd like to reproduce some of the patterns he mentions.

Philosophical aside #1

One interesting claim Barricelli makes (pg 2): a pattern that reproduces itself tends to also propagate the environment that it arose in. If something about the environment caused an organism to spontaneously arise, almost by definition the organism is required to preserve that property to reproduce itself. So he claims that the insides of cells likely are very similar in some ways to life on earth back when RNA spontaneously emerged. No way to be sure, of course, but the argument kinda hangs together for me. And the empirical evidence for this is that the Earth is 4.3 billion years old, and life on the earth is around 4 billion years old. Once conditions were right, life basically emerged in a cosmic eyeblink. One way to view all of later life is as ways to protect that initial environment in the face of more and more hostile environment changes, to create little bubbles of the primordial soup inside us all.

And it's fractal. As new structures arise to protect old bubbles, they are themselves self-propagating and they need their own environments preserved.

A specific property of the environment isn't necessarily helpful to all life. One organism may need some environmental property that another organism finds utterly hostile. Just by being first, an organism will tend to propagate the environment it needs. And by doing so it's competing with even the possibility of other organisms that don't exist yet.

This line of thought leads me to wonder if it may be easier than I thought to find new conditions suitable for the emergence of life. I know physicists run large simulations of the early universe on supercomputers, which generate plausible compositions of elements over time as supernovas occur. I also vaguely remember from TV programs long ago that we've tried to run simulations of earth's primordial soup using best guesses of its early composition. What if we put these two ideas together? Given a simulation of the early cosmos, generate candidate stars, candidate planets around those stars, plausible initial distributions of elements on those planets, conditions of temperature and pressure. Then simulate brief slices of time. If (my interpretation of) Barricelli is correct, life either emerges instantly or not at all, and we may be able to try out a variety of conditions relatively cheaply. And maybe identify candidate chemistries that help molecules reproduce.

There's probably some professor somewhere who is aware of past research in this vein and can point me at papers :)

Philosophical aside #2

One way to view the story of our evolution is as a leveling-up of goals:

• Life: "cells maintain the environment in which RNA molecules originated."
• Bureaucracy: you create a system that can outlive you. The system outlives its own usefulness.
• Permaculture: design systems to try to make themselves less and less necessary to the functioning of the ecosystem.

Credits

Some example code from Simone Conradi and some pointers to literature from Karsten Schmidt got me going. This paper was my primary source.

permalink

Inspired by Cristóbal Sciutto, here's a little piece of purely client-side html for creating tables.

Save a copy for yourself. You'll need to edit the html to tailor the table dimensions for a specific context.

Saving the table downloads a new copy. (You'll probably want to rename it to the original; that bit is kinda janky.)

As I said before, just view source on this beauty! 😍

permalink

For the past month I've been doing something very unnatural to me: throwing the first one away. Going back and rewriting some aspect of a working program just to improve one property of the code, here eliminating all derived data structures and re-deriving everything all the time in a performant way.

The problem: implementing text editor operations as lines might wrap or scroll.

e.g. clicking with the mouse to reposition the cursor, or pressing the down arrow (which might cause a scroll)

The key new solution: an API of primitives that make such operations fairly self-evident to build.

• to_loc: (x, y) -> loc
  Identify the location at pixel coordinates (x,y) on screen.
  Returns nil if (x,y) is not on screen.
• to_coord: loc -> x, y
  Identify the top-left coordinate on screen of location loc.
  Returns nil if loc is not on screen.
• down: loc, dy -> loc
  Find the location at the start of a screen line dy pixels down from loc.
  Returns nil if dy is taller than the screen.
  Returns bottom of file if we hit it.
• up: loc, dy -> loc Find the location at the start of a screen line dy pixels up from loc.
  Returns nil if dy is taller than the screen.
  Returns top of file if we hit it.
• hor: loc, x -> loc
  Find the location at x=x0 on the same screen line as loc.

I think they might be applicable to any pixel-based editors that use proportional fonts. They seem independent of the data structure used by the editor. I use an array of lines, and so locations are defined as (line_index, pos) tuples, where pos counts in utf-8 code-points.

There's probably a few bugs but hopefully it'll stabilize quickly. I'd appreciate people trying it out.

Lessons from this experience:

• There's a "hard part" to programming beyond the reach of tools or methods. Sometimes a problem needs the right "algebraic" abstraction, designed around an invariant and preserving it across any composition of operations.
• Not all programs get this hard.
• It's useful to notice when some part calls out for doing this hard, focused work.

I think I now better understand the "abyss".

permalink

Quick and dirty prototype of the previous algo/shape/code using Vim syntax highlighting.

The code in the screenshot is a function to convert a mouse click (mx, my) into the location (line_index, pos) of the character at that point on the screen.

The problem is much of this function is boilerplate shared with several other places, such as the code to draw text on screen, compute the height of a wrapped line, etc. The boilerplate makes it difficult to see the business logic unique to this particular function, and so creates pressure to prematurely create an abstraction to "DRY things out". Highlighting the shape of the boilerplate in pink helps the eye to focus on the unique business logic in the protrusions, and so counters the pressure to hide the boilerplate before I've figured out the best way to do so.

(As an aside, this is an example of what I think of as "programmer-configured highlighting". We've gotten used to our editors deciding what to highlight for us, and we just pick the colors. One little tool I use everyday is the ability to highlight specific identifiers which flips this around: I pick a word, and the editor picks a color at random to highlight it with. And the highlight persists across sessions. The color of the State variable in the screenshot was selected in this manner.)

permalink

I've been slowly reading "The Nature of Order" by Christopher Alexander and slowly thinking about how to make my editor for text and line drawings more timeless. (And mostly sleeping a lot, if I'm honest.) Today the combination of the two led me to draw this shape for the line-wrapping algorithm.

Until now I've been developing the editor the "usual" way, which for me consists of needing some computation, figuring out the most convenient place to perform the computation, then squirreling away the result somewhere it's available when needed. In an effort to get myself out of the rut of the inevitable problems of indirection and cache invalidation that result, I've been trying to replace all my ad hoc data structures with on-demand computation based on the base state of the program. And what I've been ending up with is umpteen variations of this pictured algorithm, just with different code stuck on to the protrusions.

There may be an abstraction that comes out of all this, but I don't see it yet. And as CA says, a flower isn't made up of identical petals. Each one evolves uniquely as a part of the whole.

Here's the Lua code skeleton corresponding to that drawing. The ellipses correspond to protrusions in the drawing:

for line_index, line in array.each(State.lines, State.screen_top.line) do
  if line.mode == 'text' then
    local initpos = 1
    if line_index == State.screen_top.line then
      -- top screen line
      initpos = State.screen_top.pos
    end
    for pos, char in utf8chars(line.data, initpos) do
      if char:match('%s') then
        if line_wrap_at_word_boundary(State) then
          ...
        else
          ...
        end
      else
        if x+w > State.right then
          ...
        else
          ...
        end
      end
    end
  else  -- drawing
    ...
  end
end

permalink

This morning I'm thinking about turning my previous paper notation into a visual notation for something we typically use keyword args for. For example, the following glyph:

…might represent a function for initializing a text editor widget with the following signature:

edit.initialize(top, left, right, bottom, font_size)

And the numbers indicate a specific call to this function:

edit.initialize(15, 15, 115, 215, 20)

Interestingly, these alternative semantics would make for a more pleasing glyph.

edit.initialize(margin-top, margin-left, margin-right, margin-bottom, font-size)

permalink

Umpteenth attempt at stripping away unnecessary rules when teaching programming.

(Just a mockup to convey the idea. Plan is just to use this notation with pen and paper.)

Is this picture intelligible without any explanation?

permalink

Here's the most recent bugfix I had to make, along with a fairly lengthy but still incomplete post-mortem in the commit description.

Still several things left to investigate.

• Really small windows probably crash.
• Really wide and short windows probably crash.
• Pressing and releasing mouse really quickly within a single frame will probably crash.

I want to delete some data structures and just recompute them all the time.

permalink

All the bugs in my software that others run into have the following story template:

• t = n: my program was responsible for x and y
• t = nn: my program became responsible for x, y and z
• t = nnnnnn: bug in z (interacting with x/y)

Adding z required rethinking the entire program. I tried to patch it in. Implications were not fully worked out.

permalink

Trying to build software for others is extremely disheartening. I can be eating my own dogfood on a daily basis for years and still newcomers hit bugs in their first 10 minutes.

I wonder if this is the major reason to huddle together on top of jenga stacks with tons of dependencies, terrified of fragmentation: You always need more testing than you think, and there's no way to compete with something that's been through that much testing.

I come stare at this abyss every year or two.

• 2022-03-31
• 2024-12-03

Doesn't do me any good, though.

(This post spawned a sprawling, constructive conversation.)

permalink