In the beginning there was a primordial soup

I've had a fascination with living things for as long as I can remember. And for a somewhat shorter part of my life, I've been intrigued by the idea of simulating life with code.

This is the first of hopefully many posts in which I aim to develop an artificial life system. In code and biology. Most of the posts will be fairly academic/technical, but I will try to make it as digestible as possible. I hope it will be fun.

Biology

We all recognize life when we see it. But it is hard to pinpoint the exact properties that make something alive. Some candidates include reproduction, energy metabolism, homeostasis, adaptation to the immediate environment, evolution. But perhaps the most fundamental property of any living system is the ability to self-produce or to self-fabricate.

At the molecular level, every part of a living system is expendable. And yet, all living things are able to continuously self-fabricate from a biological recipe - its genetic material. And crucially, even the recipe and the systems that are able to read and execute this recipe must be continuously fabricated faithfully.

This self-fabrication property of living systems is sometimes referred to as semantic closure or closure to efficient causation. The concept of closure to efficient causation is unpacked most thoroughly in the work of Robert Rosen and Jan-Hendrik Hofmeyr. Much of the underlying theory in this series of posts is based on their work. If you are willing to accept self-fabrication as the most fundamental property of life, then invariably the following questions come up:

How did it all begin? How do you bootstrap life?

Whatever the answer to these questions may be, what happened was so unlikely that, as far as we know, it only ever happened once. I will not dwell on these questions, but when you build a self-fabricating artificial life system, you need to start somewhere. Knowing which components are required initially, is critical.

In the beginning there was a primordial soup, a slimy pool.

Code

We will be building the artificial life system using the Elixir programming language. You don't have to know Elixir to follow, and I'll highlight some non-obvious things, but this will potentially be much more fun if you actually like Elixir.

Despite being built in Elixir, we will rely extensively on concepts from stack-based, concatenative languages, and combinatory logic. These features are best exemplified in the language Joy; at least in my humble opinion and for our current purposes. Joy was developed by Manfred von Thun as an alternative to applicative languages, such as Lisp, which are influenced by the lambda calculus. You don't have to be an expert in Joy, and neither am I.

An empty pool is not very interesting. So we start by agreeing that a pool can contain things (elements). And perhaps things can be added to a pool or removed from it. We will not yet link any biological meaning to pool membership, or the comings and goings of things in the pool. So don't push any analogy too far just yet.

A pool has state, its current elements, and the standard way to keep state in Elixir is to use a process. A GenServer is an abstraction around low-level process callbacks such as sending and receiving synchronous or asynchronous messages to the process inbox. It keeps state by essentially calling its own internal functions (or callbacks) in a kind of loop, continuously passing its state to itself as an argument. Callbacks receive state, potentially modify it, and then return it. Rinse and repeat.

We represent our pool with a GenServer that has a list of elements as its initial state ([:a, :b, :c]). The pool has an external facing client or public API and an internal facing server or callback API.

Processes are usually started by supervisors that are themselves processes. This goes all the way up to the application level. For now, it is enough to know that a supervisor is tasked with restarting and restoring any crashed process that it supervises to its initial state. We can also start the pool outside of a supervision tree using the start_link function that is part of its public API (we are doing this interactively with IEx):

iex(1)> Slyk.Pool.start_link()
{:ok, #PID<0.176.0>}

The result is a tuple with a process id (pid) as its second element. All our future interactions with the pool will use this pid under the hood.

Once the pool has been started, elements can be added to and removed from the pool:

iex(2)> Slyk.Pool.put(:d)
:ok
iex(3)> Slyk.Pool.get()
{:ok, :a}

The elements in the pool are all atoms. An atom is a special primitive type with the property that its name is also its value. You can think of an atom as a glorified string literal prefixed with a colon. So we added the atom :d to the pool. And then we randomly retrieved (and removed) the atom :a from the pool.

Let's have a look at the implementation and the docs for the public API and then discuss the internal API.

defmodule Slyk.Pool do
  require Logger
  use GenServer

  # Client (public API)

  @doc """
  Start the pool.

  Under the hood this starts a process and associates the pid with the
  name Slyk.Pool, so that future calls can use Slyk.Pool instead of the
  pid, which will change if the process needs to be restarted.

  The state is initialized by calling the init callback with the provided
  init_args.
  """
  def start_link(init_args \\ []) do
    # Start the process and associate the pid with the name Slyk.Pool
    GenServer.start_link(Slyk.Pool, init_args, name: Slyk.Pool)
  end

  @doc """
  Add the element to the pool synchronously.

  Under the hood, this will call the handle_call callback with
  {:put, element} as first argument.
  """
  def put(element) do
    GenServer.call(Slyk.Pool, {:put, element})
  end

  @doc """
  Retrieve a random element from the pool synchronously.

  Under the hood, this will call the handle_call callback with
  :get as first argument.
  """
  def get() do
    GenServer.call(Slyk.Pool, :get)
  end

  # Server (callbacks)

  def init(_init_args) do
    # Ignore the init_args and initialize the state to [:a, :b, :c]
    {:ok, [:a, :b, :c]}
  end

  def handle_call({:put, element}, _from, state) do
    {:reply, :ok, [element | state]}
  end

  def handle_call(:get, _from, [] = state) do
    {:reply, {:error, :empty}, state}
  end

  def handle_call(:get, _from, state) do
    [head | tail] = Enum.shuffle(state)
    {:reply, {:ok, head}, tail}
  end
end

The callbacks (internal API) deal with the concurrency and "thread-safety" of calls and also implements the state transformations involved in each case. To insert a pool element, we set the state to a new list with the element at its head and the old state as the rest.

To retrieve a pool element, we shuffle the list of elements, return the head, and update the process state to what is left. There is only one problem. If the state is empty, there is nothing to retrieve. So we have to add a function clause that will match on the state being empty and return {:error, :empty} without altering the state and without crashing.

Note that we have three function clauses for the handle_call function. On each invocation of handle_call, Elixir will match the provided arguments to each function clause, starting at the top and execute the first (and only the first) one that matches.

In closing, our pool is essentially a complicated stack. Except that the stack is randomized just-in-time before each retrieval or "pop". In fact, if all you need is a stack, you can rely on a plain old Elixir list. Elixir lists are linked lists and thus ideal for stack implementations. We could have implemented our pool as just a list. The only reason for wrapping it in a GenServer is so that it becomes addressable and accessible to other processes.