In the first post of this series I've introduced a very simple pool in the form of an Elixir process. The elements of the pool were atoms, and it was possible to add and remove atoms to the pool. We will now extend the pool to contain and interpret Joy programs (an extended family of Joy quines, to be precise). As a side-effect we will learn about tasks and task supervision in Elixir.

Code

We have already established that [dup cons] dup cons is a quine in Joy. We could also define duco == dup cons so that the above quine can be written in a form that elegantly separates the “use” and “mention” parts with only a single function: [duco] duco. The question now arises as to whether we can also introduce an arbitrary “state” part to the quine. That is, a piece of program that can be manipulated independently? It turns out that this is possible with the help of the rest function, which takes a quotation and discards its head. Consider the execution steps of the program [[] dup rest cons] dup rest cons, which once again ends with a quoted form of itself:

[[] dup rest cons] [[] dup rest cons] rest cons (dup applied)
[[] dup rest cons] [   dup rest cons] cons      (rest applied)
[[[] dup rest cons] dup rest cons]              (cons applied)

The program above includes an empty quotation [] as a piece of state that gets passed from generation to generation untouched and unexecuted. Interestingly, it is also possible to slightly alter the state on each execution:

[[] [unit] infra dup rest cons]
  [unit] infra dup rest cons

[[[]] [unit] infra dup rest cons]
  dup rest cons                               (infra applied)

[[[]] [unit] infra dup rest cons]
  [[[]] [unit] infra dup rest cons] rest cons (dup applied)

[[[]] [unit] infra dup rest cons]
  [[unit] infra dup rest cons] cons           (rest applied)

[
  [[[]] [unit] infra dup rest cons]
  [unit] infra dup rest cons
]                                             (cons applied)

...

[
  [[[[[[]]]]] [unit] infra dup rest cons]
  [unit] infra dup rest cons
]

Each time this program is executed, it wraps its state in a further pair of brackets. Some discussion of infra is warranted here. This combinator reads two quotations from the stack, it treats the first as a program to be executed, and the second as a temporary new stack. This means that the infra step above applied the [unit] program to a temporary stack of which [] was at the top. This yielded [[]], which was returned to the top of the temporary stack, which was in turn placed on top of the original stack.

Armed with the above, we can now create a nested quine like this:

[
  [
    [dup cons]
    dup cons
  ]
  [i] infra dup rest cons
]
[i] infra dup rest cons

Here we use infra to interpret (using [i]) the state ([[dup cons] dup cons]), which happens to be a quine itself. Unfortunately this is not very productive, since the state just evaluates to itself. What if we could produce a program that oscillates between two forms in which one produces the other? For this we need to add one more state part and one more rest call:

[STATE1 STATE2 dup rest rest cons] dup rest rest cons

Now, let’s combine the basic two-state structure above with the infra-mechanism using [cat] and [dup] as the two arbitrary states and [swap] as the quotation to be applied to them. This yields the following:

[
  [cat] [dup] [swap] infra dup rest rest cons
]
[swap] infra dup rest rest cons

(infra applied):
[
  [dup] [cat] [swap] infra dup rest rest cons
]
dup rest rest cons

(dup applied):
[
  [dup] [cat] [swap] infra dup rest rest cons
]
[
  [dup] [cat] [swap] infra dup rest rest cons
]
rest rest cons

(rest applied twice):
[
  [dup] [cat] [swap] infra dup rest rest cons
]
[
  [swap] infra dup rest rest cons
]
cons

(cons applied):
[
  [
    [dup] [cat] [swap] infra dup rest rest cons
  ]
  [swap] infra dup rest rest cons
]

In the program above, the two states [cat] and [dup] are swapped on every execution, trivially constituting two programs that give rise to one another on execution. Many more quines and different ways of keeping state can be found in the Survey of reproducing programs article by Manfred von Thun.

We now return to the primordial soup cauldron Slyk.Pool, updated to accommodate Joy programs (lists of atoms) as opposed to just atoms. On initialization it reads a file containing Joy programs from disk and parses them. These are then stored in a list representing the state of the pool. As before, it is possible to retrieve random elements from the pool and to insert new elements. But more interestingly, we now let the pool periodically select an element for activation. The activated element (Joy program) is removed from the pool, interpreted, and the results are returned to the pool as new elements.

Here are the updated parts of the pool process module:

defmodule Slyk.Pool do
  require Logger
  use GenServer

  # Client (public API)

  ...

  # Server (callbacks)

  def init(path) do
    # Immediately schedule a future "activate"
    Process.send_after(self(), :activate, 1000)

    # Read from disk and parse programs
    programs =
      :slyk
      |> :code.priv_dir()
      |> Path.join(path)
      |> File.open!([:read], &IO.read(&1, :all))
      |> String.split(".", trim: true)
      |> Enum.map(&Joy.Parser.parse/1)

    # Set the programs as state
    {:ok, programs}
  end

  # This gets called about 1000 ms after the process is first
  # initialized, as scheduled in the init function.
  def handle_info(:activate, []) do
    # Schedule a future "activate"
    Process.send_after(self(), :activate, 1000)

    # There are no programs to execute...

    {:noreply, []}
  end

  def handle_info(:activate, state) do
    Process.send_after(self(), :activate, 1000)

    # Find a random program
    [head | tail] = Enum.shuffle(state)

    # Run it in a new process
    Slyk.ProgramRunner.run_program(head)

    # Return the rest as the new state
    {:noreply, tail}
  end

  # callbacks for get and put as previously discussed
  ...
end

Everytime one of the pool members is "activated", the following call is made: Slyk.ProgramRunner.run_program(head), where head is the program or element that is activated. To understand what this does, we need to look at the code for Slyk.ProgramRunner:

defmodule Slyk.ProgramRunner do
  def child_spec(opts) do
    default = %{
      id: __MODULE__,
      start: {__MODULE__, :start_link, [opts]},
      type: :supervisor
    }

    Supervisor.child_spec(default, [])
  end

  def start_link(_opts) do
    Task.Supervisor.start_link(name: __MODULE__)
  end

  def run_program(program) do
    Task.Supervisor.start_child(__MODULE__, Slyk.Program, :run, [program])
  end
end

The child_spec function tells the process that will supervise the program runner how to start it and to treat it as a supervisor itself. line turns this module into a supervisor. It implements a start_link function that enables it to be started (as part of a supervision tree) and a run_program function that starts and supervises a task process. The sole purpose of the task process is to invoke Slyk.Program.run(program), after which it will exit normally. Any exceptions that are raised in the task process will cause it to terminate, but since tasks are "temporary" processed (by default), no attempt will be made to restart them.

Here is the Slyk.Program module. Its run function is executed in the task process. It interprets the Joy program and returns all the elements on the result stack to the pool.

defmodule Slyk.Program do
  def run(program) do
    program
    |> Joy.Interpreter.interpret()
    |> Enum.each(&Slyk.Pool.put(&1))
  end
end

Running our Slyk application in IEx now yields something like the following (we log every program as it is inserted into the pool again:

iex(1)>
19:29:09.168 [info]  Put: [[:dup, :cons], :dup, :cons]

19:29:10.155 [info]  Put: [[[[]], [:unit], :infra, :dup, :rest, :cons], [:unit], :infra, :dup, :rest, :cons]

19:29:11.156 [info]  Put: [[[], [], :dup, :rest, :rest, :cons], :dup, :rest, :rest, :cons]

19:29:12.157 [info]  Put: [[[], [], :dup, :rest, :rest, :cons], :dup, :rest, :rest, :cons]

19:29:13.158 [info]  Put: [[:dup, :cons], :dup, :cons]

19:29:14.159 [info]  Put: [[[:dup], [:cat], [:swap], :infra, :dup, :rest, :rest, :cons], [:swap], :infra, :dup, :rest, :rest, :cons]

19:29:15.160 [info]  Put: [[[[[], :dup, :rest, :cons], :dup, :rest, :cons], [:i], :infra, :dup, :rest, :cons], [:i], :infra, :dup, :rest, :cons]

19:29:16.161 [info]  Put: [[[], [], :dup, :rest, :rest, :cons], :dup, :rest, :rest, :cons]

19:29:17.162 [info]  Put: [[[], :dup, :rest, :cons], :dup, :rest, :cons]

19:29:18.163 [info]  Put: [[:dup, :cons], :dup, :cons]

19:29:19.164 [info]  Put: [[[:cat], [:dup], [:swap], :infra, :dup, :rest, :rest, :cons], [:swap], :infra, :dup, :rest, :rest, :cons]

The pool churning above automatically starts as a result of including the pool and program runners in the application supervision tree:

defmodule Slyk.Application do
  use Application

  def start(_type, _args) do
    children = [
      # quine.pool is a file containing the quines
      {Slyk.Pool, ["quine.pool"]},
      Slyk.ProgramRunner
    ]

    opts = [strategy: :one_for_one, name: Slyk.Supervisor]
    Supervisor.start_link(children, opts)
  end
end

Biology

While the quines we've introduced above can all be considered to be self-reproducing in one way or another, they are not quite analogous to organisms, not even lower organisms like bacteria.

A number of such ultra-primitive life-like or protolife elements can however be found to operate in association with organisms. Some of the most primitive such elements are transposable elements or transposons. There is quite a large variety of transposons. The simplest ones are able to move themselves around in their host genome (sometimes very precisely) without reproducing. Others copy themselves and insert multiple copies back into the genome.

Endogenous viruses are somewhat more sophisticated. They appear in the form of primitive viruses that have not yet acquired the ability to leave their host or have lost the ability to do so as a result of mutation. These are fairly benign and are even transferred from parent to child - not infectiously but as part of normal vertical gene transfer.

Finally there are full-blown viruses. Pieces of DNA or RNA that encode a set of genes that replicate and package themselves in order to leave their host and infect other hosts.

The components of a virus can be broadly subdivided into "use" and "mention" parts. The DNA or RNA of the virus is its "mention" part, whereas the protein coat and protrusions from it that protect it and help it to gain entry into host cells partially constitute the "use" part. Viruses also sometimes package their own transcription machinery (from DNA to RNA), but crucially lack ribosomes, which are required to translate the viral RNA into proteins. Instead, they rely on the host to unquote the "mention" part into the "use" part.

In closing, in order to realize an artificial life system that is capable of open-ended evolution, it will be necessary to consider higher levels of organization. Instead of representing life with single Joy programs (or even a family of non-interacting Joy programs), it will be necessary to consider an ecosystem of Joy programs that interact to provide all the functions required to constitute closure to efficient causation.