DEV Community: Danie Palm

GenServer: from first principles

Danie Palm — Mon, 30 Jun 2025 15:29:53 +0000

This is an adaptation of a knowledge base article that I've written at The Internet of Behaviors Company.

At its heart, Elixir (and other BEAM languages) has only:

processes (lightweight/green threads, not OS processes),
functions, and
data.

There are no language level "objects" like in object-oriented languages that tie these into a stateful combination. However, it has been argued that the things you can build on top of these primitives, bring you closer to the true ideal of object-oriented programming than languages like, say, Java. BEAM might even be the only true OO runtime! 😜

Anyway, you might have noticed that keeping state is quite different in Elixir compared to OO/other languages. You don't have instances of objects in which you can keep state. Sure there are data structures like structs, maps and lists that you can pass around, but where do they live? Nowhere. You just pass them around, transform them, and return the result. Of course, you can read and write data to and from external sources, such as a DB and that is what libraries like Ecto helps with. But is there no other way of keeping state in Elixir?

Yes there is. There are actually a couple of ways, some built into the runtime (like ETS tables), and others just arise naturally: functions can call themselves recursively, passing the result as the next input. This may sound like a recipe for a stack overflow, but Elixir eats this for breakfast.

The standard library comes with an abstraction around this recursion-based way of keeping state: GenServer. You can get pretty far in Elixir without caring about GenServers and related concepts, but under the hood they are the foundation for everything from connections, to high throughput data processing pipelines, and even real-time server side rendered content like in Phoenix LiveView.

Understanding GenServers can be daunting to newcomers. You are told to implement a couple of callbacks, but the inner workings can feel like a mystery.

Let's change that by building a GenServer from first principles!

Preliminaries

There are three operators that are fundamental to how GenServer works:

spawn/3 - spawns a new process

spawn(MyModule, :my_function, [my, args])
# calls MyModule.myfunction(my, args) in a new process

send/2 - sends message to a target process, possibly itself (fire and forget style)

send(target_process_id, message)

receive/1 - blocks a process until it receives a message from another process (or itself)

receive do
  message -> do_something_with_the_message(message)
end

A process that can receive messages

Here is a simple process that is able to receive an arbitrary number of messages. It is very rudimentary and doesn't (yet) keep any state. We'll build on this in iterations.

defmodule StatelessProcess do
  def loop do
    receive do
      message -> 
        IO.puts("Received: #{message}")
        loop()  # Keep listening for new messages
    end
  end
end

# Spawn a new process and make it call StatelessProcess.loop()
pid = spawn(StatelessProcess, :loop, [])

# Then send a message to the new process
send(pid, "Hello, process!")  # Output: Received: Hello, process!

The basic idea is that the loop/0 function calls itself recursively until infinity. On every execution, it waits for a message with receive/1. receive/1 is blocking, so it keeps waiting for a message until it gets one before re-entering the loop.

Problem

We have no record of previous messages. We are not keeping state.

Adding state

Let's modify the process to keep track of a counter.

defmodule StatefulProcess do
  def loop(count) do
    receive do
      :increment -> 
        IO.puts("Incrementing: #{count + 1}")
        loop(count + 1)  # Update the state by passing it forward
      :get_value -> 
        IO.puts("Current count: #{count}")
        loop(count)  # State remains unchanged
    end
  end
end

pid = spawn(StatefulProcess, :loop, [0])

send(pid, :increment)  # Output: Incrementing: 1
send(pid, :increment)  # Output: Incrementing: 2
send(pid, :get_value)  # Output: Current count: 2

Now loop/1 calls itself with an argument: the count. We've also modified the receive block to wait until it receives very specific messages. It will wait indefinitely until it receives either an :increment or a :get_value. It will crash when receiving an unexpected message. Finally it re-enters the loop, possibly altering the counter.

We can now send messages to the process to alter its state and to interrogate its state.

Problem

We can make the process print its state, but we can't actually retrieve its state. There's no way to get a response back.

Allowing requests to return data

Let's teach the process to talk back.

defmodule SyncStatefulProcess do
  def loop(count) do
    receive do
      {:increment, sender} -> 
        new_count = count + 1
        send(sender, {:ok, new_count})  # Send response back
        loop(new_count)  # Update state

      {:get_value, sender} -> 
        send(sender, {:ok, count})  # Send state back
        loop(count)  # State remains unchanged
    end
  end
end

pid = spawn(SyncStatefulProcess, :loop, [0])

send(pid, {:increment, self()})  # We pass our own PID to receive a response
receive do
  {:ok, new_value} -> IO.puts("New count: #{new_value}")  
end

send(pid, {:get_value, self()})
receive do
  {:ok, value} -> IO.puts("Current count: #{value}")  
end

In addition to sending data to the process, we also send along the process id (pid) of the calling process, so that the callee process knows to whom to respond. We can now communicate with the process synchronously. That is, we are waiting for a response.

Problem

The process doesn't support asynchronous calls and it takes a lot of typing to call it.

Supporting asynchronous calls and removing boilerplate

defmodule MyGenServerLike do
  def start do
    spawn(MyGenServerLike, :loop, [0])
  end

  def call(pid, request) do
    send(pid, {:call, self(), request})
    receive do
      response -> {:ok, response}
    end
  end

  def cast(pid, request) do
    send(pid, {:cast, request})
    :ok
  end

  def loop(state) do
    receive do
      {:call, from, request} ->  
        {reply, new_state} = handle_call(request, state)  
        send(from, {:response, reply})  
        loop(new_state)  

      {:cast, request} ->  
        new_state = handle_cast(request, state)  
        loop(new_state)  
    end
  end

  defp handle_call(:get_value, state), do: {state, state}

  defp handle_cast(:increment, state), do: state + 1
end

pid = MyGenServerLike.start()
:ok = MyGenServerLike.cast(pid, :increment)
{:ok, count} = MyGenServerLike.call(pid, :get_value)

We can now interact very nicely with the process.

Problem

Among others, it is not reusable.

GenServer

Implementing the code above can get old very quickly. That is why Elixir comes with a prepackaged solution: GenServer. We can get the same functionality as before with this:

defmodule Counter do
  use GenServer

  # --- Public Client API ---
  # These execute in the caller process

  def start_link(initial_value) do
    GenServer.start_link(__MODULE__, initial_value)
  end

  def increment(pid) do
    GenServer.cast(pid, :increment)
  end

  def get_value(pid) do
    GenServer.call(pid, :get_value)
  end

  # --- Server Callbacks ---
  # These execute in the callee process. So while
  # they are public, calling them directly will
  # be useless.

  def init(initial_value) do
    {:ok, initial_value}  # Initial state
  end

  def handle_cast(:increment, state) do
    {:noreply, state + 1}
  end

  def handle_call(:get_value, _from, state) do
    {:reply, state, state}
  end
end

{:ok, pid} = Counter.start_link(0)
:ok = Counter.increment(pid)
value = Counter.get_value(pid)

The reusability lies in the use GenServer line. It expands the GenServer.__using__ macro, which hides a ton of repetitive code like the loop function and much much more. You strictly only have to implement the server callbacks, but the start_link, increment, and get_value functions just make it even nicer (hides the calling and casting) to interact with the counter.

Conclusion

Can you see how counter (the process id) now almost behaves like an instance?

{:ok, counter} = Counter.start_link(0)
Counter.increment(counter)
value = Counter.get_value(counter)

Compare this to the following OO pseudocode:

counter = new Counter(0)
counter.increment()
value = counter.get_value()

One of the differences is that we have thread-safety out of the box in Elixir. No process can change the state of another process except through message passing. But in your day to day usage of Elixir you will barely be aware of all the message passing that happens under the hood.

Efficient and reliable message publishing with RabbitMQ and Elixir

Danie Palm — Mon, 26 May 2025 09:33:17 +0000

I recently had to build convenience wrappers around producers and consumers for RabbitMQ in a pub-sub architecture.

There are many obstacles to ensuring reliable (at-least-once) message delivery when using a distributed message broker like RabbitMQ.

Messages may be lost between the producer and the broker, inside the broker, and between the broker and consumers. And there are many subtleties.

In a nutshell, you need to enable:

publisher confirms - so that the broker acks messages
message persistence - so that the broker acks messages only after flushing it to disk
durable queues (with a durable exchange) - so that queues survive broker and consumer restarts
consumer acking - so that the queue retains messages until acked by a consumer

The official RabbitMQ website has some great documentation, including this Elixir tutorial, but examples of using the AMQP primitives in a robust OTP setting are sparse.

In this post I specifically want to address efficient publisher confirms.

Synchronously awaiting publisher confirmations

Here are two projects with examples of publisher modules:

AMQPX
GenRMQ

Unfortunately, both make use of the AMQP.Confirm.wait_for_confirms/2 primitive inside a GenServer callback. In this way, messages are published (with AMQP.Basic.publish/5) and immediately awaited inside a handle_call/3 callback and thus creates a bottleneck that effectively prevents concurrent publishing. Throughput will certainly suffer.

Async handling of publisher confirmations

There is another way. AMQP.Confirm.register_handler/2 allows you to register a process that will receive broker confirmations asynchronously. The acks (or nacks) will then invoke handle_info with one of these sets of arguments:

{:basic_ack, seqno, multiple}, state
{:basic_nack, seqno, multiple}, state

This indicates that the publish with sequence number seqno was either acked or nacked. If we somehow had a mapping between seqno and the original process that called the our GenServer's publish callback, we would be able to reply to it with a success or error message.

Fortunately, the ampq library provides us with AMQP.Confirm.next_publish_seqno so that we can get a handle on seqno at the same point in time where we have a handle on from (the process that called us in the first place), allowing us to store a mapping between them.

Enough high-level talk. Let's step through an outline of the solution. First we get the boilerplate out of the way:

defmodule MyPublisher do
  use GenServer

  ...

  def start_link(channel) do
    # Start the process
    GenServer.start_link(__MODULE__, channel, name: __MODULE__)
  end

  def init(channel) do
    # Initialize the process state and do setup. We
    # assume you have an exchange called "pub_sub"
    # already set up.

    # Enable publisher confirms
    AMQP.Confirm.select(channel)

    # Register the current process as the async handler
    # for acks and nacks
    AMQP.Confirm.register_handler(channel, self())

    ...

    # Put the channel in the state. Proper
    # connection and channel management is
    # not covered in this post.
    {:ok, %{channel: channel}}
  end

  ...
end

Now we'll add the API for publishing messages:

  def publish(topic, payload) do
    # This function runs in the calling process
    GenServer.call(__MODULE__, {:publish, topic, payload})
  end

  def handle_call({:publish, topic, payload}, from, state) do
    # This function runs in the GenServer
    ...

    # Perform the actual publishing (ensure it is persistent)
    AMQP.Basic.publish(state.channel, "pub_sub", topic, payload, persistent: true)

    # Note that we are NOT replying here
    {:noreply, state}
  end

And, having registered the GenServer as the handler of confirmation messages, we need to implement some confirmation handling callbacks:

  def handle_info({:basic_ack, seqno, multiple}, state) do
    # The broker is saying that the publish with `seqno`
    # has been received. If `multiple` is true, all messages
    # up to `seqno` have been received.
    confirm_messages(seqno, multiple, fn from ->
      # For each of the received messages,
      # we can reply with `:ok`.
      GenServer.reply(from, :ok)
    end)

    {:noreply, state}
  end

  def handle_info({:basic_nack, seqno, multiple}, state) do
    # The broker is saying that the publish with `seqno`
    # has been lost. If `multiple` is true, all messages
    # up to `seqno` have been lost.
    confirm_messages(seqno, multiple, fn from ->
      # For each of the lost messages,
      # we can reply with `{:error, :nack}`.
      GenServer.reply(from, {:error, :nack})
    end)

    {:noreply, state}
  end

We next need to understand the implementation of confirm_messages, but first, some updates to the boilerplate and publishing code:

def init(channel) do
    ...

    # Create an ETS table in which the elements are ordered. It
    # will be owned by the GenServer process. We make it private
    # because there is no need for other processes to read or
    # write to it.
    :ets.new(@table_name, [:ordered_set, :private, :named_table])

    {:ok, %{channel: channel}}
  end

  ...

  def handle_call({:publish, topic, payload}, from, state) do
    # Before we publish, get a hold of the next publish
    # sequence number `seqno`.
    seqno = AMQP.Confirm.next_publish_seqno(state.channel)

    # Store the caller reference (`from`) against
    # the `seqno` in ETS
    :ets.insert(@table_name, {seqno, from})

    # Perform the actual publishing
    ...
  end

And now finally, when receiving an ack or a nack, we can lookup
the corresponding caller reference by seqno and reply appropriately:

  defp confirm_messages(seqno, _multiple = false, reply_fun) do
    # Lookup and remove the entries for seqno
    case :ets.take(@table_name, seqno) do
      [{^seqno, from}] -> reply_fun.(from)
      _ -> :ok
    end
  end

The case where the broker chooses to acknowledge multiple messages
at once is somewhat less readable and involves a clunky ETS-specific match specification, but you can largely gloss over that:

  defp confirm_messages(seqno, true = _multiple, reply_fun) do
    :ets.select(@table_name, [
      {
        # bind `seqno` and `from` to $1 and $2
        {:"$1", :"$2"},
        # match entries where the bound seqno is =< to the incoming seqno 
        [{:"=<", :"$1", seqno}],
        # and return all the matching entries as tuples of $1 and $2
        [{{:"$1", :"$2"}}]}
    ])
    |> Enum.each(fn {key, from} ->
      reply_fun.(from)
      :ets.delete(@table_name, key)
    end)
  end

Full outline

Here is the module in full. But keep in mind that we did not include any fault-tolerance in terms of connections or channels dying. We also do not include exchange declaration.

defmodule MyPublisher do
  use GenServer

  @table_name :pending_confirms

  def start_link(channel) do
    GenServer.start_link(__MODULE__, channel, name: __MODULE__)
  end

  def init(channel) do
    AMQP.Confirm.select(channel)
    AMQP.Confirm.register_handler(channel, self())

    :ets.new(@table_name, [:ordered_set, :private, :named_table])

    {:ok, %{channel: channel}}
  end

  def publish(topic, payload) do
    GenServer.call(__MODULE__, {:publish, topic, payload})
  end

  def handle_call({:publish, topic, payload}, from, state) do
    seqno = AMQP.Confirm.next_publish_seqno(state.channel)

    # Store the caller reference in ETS
    :ets.insert(@table_name, {seqno, from})

    # Perform the actual publishing
    AMQP.Basic.publish(state.channel, "pub_sub", topic, payload, persistent: true)

    {:noreply, state}
  end

  def handle_info({:basic_ack, seqno, multiple}, state) do
    confirm_messages(seqno, multiple, fn from ->
      GenServer.reply(from, :ok)
    end)

    {:noreply, state}
  end

  def handle_info({:basic_nack, seqno, multiple}, state) do
    confirm_messages(seqno, multiple, fn from ->
      GenServer.reply(from, {:error, :nack})
    end)

    {:noreply, state}
  end

  defp confirm_messages(seqno, true = _multiple, reply_fun) do
    :ets.select(@table_name, [
      {{:"$1", :"$2"}, [{:"=<", :"$1", seqno}], [{{:"$1", :"$2"}}]}
    ])
    |> Enum.each(fn {key, from} ->
      reply_fun.(from)
      :ets.delete(@table_name, key)
    end)
  end

  defp confirm_messages(seqno, false, reply_fun) do
    case :ets.take(@table_name, seqno) do
      [{^seqno, from}] -> reply_fun.(from)
      _ -> :ok
    end
  end
end

Conclusion

We have outlined a solution for efficient publisher confirmations. This enables the calling process (the one that invokes MyPublisher.publish/2) to know for certain whether a published message successfully made it to the broker or not.

The solution is efficient, because even though the call to MyPublisher.publish/2 is synchronous, it does not block calls to the same function from within other processes while waiting for confirmation from the broker. Processing of the confirmation is asynchronous.

The power of this solution lies in the, perhaps, underappreciated fact that synchronous GenServer callbacks (like handle_call) do not need to reply immediately. As long as it keeps track of who called, it can always reply at a later stage (keeping timeouts in mind), after some async work is complete.

Finally, if you don't need to support very high throughput, but still want to benefit from the async publisher confirmation handling, you can also use a plain old map instead of an ETS table to match seqno to from.

Binary pattern matching <<1::1, 0::1, 1::1>>

Danie Palm — Tue, 23 Apr 2024 05:41:29 +0000

I recently had to write a parser for a proprietary binary file format that stores photoplethysmography (PPG) and accelerometry data and various other health-related metrics derived from a wearable device. The format is similar in spirit to protocol buffers, but exploits domain knowledge to achieve an even more compact representation.

Elixir is not necessarily the most performant language for this kind of raw computation, being generally better suited to IO-bound tasks, but it does sport impressive binary handling capabilities that it inherits from Erlang.

In this post I want to share some of the basics and some of the more advanced techniques I used to parse this binary format. The format itself is not relevant, so we will use contrived examples.

Basics

The = operator looks and behaves much like an assignment operator in Elixir, but is actually a match operator that allows you to match and destructure values. Also, strings are just binaries in Elixir, so we will often use strings in illustrations. A binary is simply a sequence of bytes. More specifically, they are bitstrings (sequences of bits) that are multiples of 8 bits long. Binaries and bitstrings are represented in Elixir as comma-separated values enclosed in double-angle brackets (<< and >>).

So let's have a look at the simplest string pattern matches:

# SUCCESS: match a string to another string of the same value
"string" = "string"

# FAILURE: match a string to another string of a different value
"string" = "not the same string"

# SUCCESS: match a string to a variable
# assigns "string" to `string`
string = "string"

# SUCCESS: match a string to a concatenation that shares the same prefix
# assigns "ing" to `ing`
"str" <> ing = "string"

# FAILURE: putting the variable part first (logically fine, but not allowed)
str <> "ing" = "string"

# FAILURE: not sharing the same prefix
"not the same str" <> ing = "string"

But strings are just binaries, so much the same can be achieved using the binary syntax:

# SUCCESS: an empty string matches an empty binary
<<>> = ""

# SUCCESS: a string matches a binary of the same value
<<"string">> = "string"

# SUCCESS: a string matches a variable of type binary
# assigns `"string"` to `string`
<<string::binary>> = "string"

# SUCCESS: a string matches a concatenation that shares the same prefix
# assigns `"ing"` to `ing`
<<"str", ing::binary>> = "string"

# FAILURE: putting the variable part first (logically fine, but not allowed)
<<str::binary, "ing">> = "string"

# SUCCESS: the parts make up the whole
<<"st", "ri", "ng">> = "string"

# SUCCESS: and you can even do nesting
# assigns `"ng"` to `ng`
<<"st", <<"ri", ng::binary>> >> = "string"

Enter the bytes

As mentioned earlier, a binary is a sequence of bits with a total length that is a multiple of 8. In other words, a binary is a sequence of bytes. While the underlying representation is a sequence of bits, it can be constructed from and destructured into almost any Elixir data type. To understand how, for instance, "st" is a sequence of bytes, let's add another (0) byte to it in iex:

iex> <<"st", 0>>
<<115, 116, 0>>

So Elixir takes the bytes that encode the "s", the "t" and the 0 and packs them in sequence in the binary. You are not limited to integers and strings and can construct binaries from floats, individual bits, and many more:

iex> <<"s", 116, 1.2, 0x00>>
<<115, 116, 63, 243, 51, 51, 51, 51, 51, 51, 0>>

One byte for the string "s", one byte for the integer 116, 8 bytes for the float 1.2, and a final null byte given in hex for fun. You can even construct the binary, in part or in full, from individual bits or from groups of arbitrary bite size:

# construct a binary from bits, note that 1::5 is effectively 00001
iex> <<1::1, 0::1, 1::1, 1::5>>
<<161>>

# to verify, let's construct the same binary from an integer in base 2
iex(7)> <<0b10100001>>
<<161>>

When possible, Elixir will display a binary as a string (strings are like syntactic sugar for binaries that meet the right criteria), but if the sequence of bytes does not make up a valid utf8-encoded string, it will display 8-bit unsigned integers instead.

Constructing and destructuring binaries

Several modifiers can be provided to signify to Elixir exactly how you intend a sequence of values to be converted to an underlying sequence of bits, or how to destructure bits into a sequence of values.

By default, integers without any modifiers (also called options) are treated as unsigned, big-endian integers of size 8 and unit 1 (i.e. 8 bits long). As such these are all equivalent:

<<101::unsigned-big-integer-size(8)-unit(1)>>
<<101::unsigned-big-integer-size(8)>>
<<101::unsigned-big-integer-8>>
<<101::unsigned-integer-8>>
<<101::integer-8>>
<<101::8>>
<<101>>

Similar options exist for floats, bits, and binaries where applicable.

We can now use these options, which can be provided in any order as long as they are separated with - and follow a ::, to match any particular parts of an incoming binary:

iex> <<elves::bytes-3, men::bytes-9, dwarves::bytes-7, dark_lord::bytes-1>> = "elfmortalmendwarves1"
iex> elves
"elf"
iex> men
"mortalmen"
iex> dwarves
"dwarves"
iex> dark_lord
"1"

Note that bytes is an alias for binary and by default the unit for binaries is 8 and the size is unspecified (if not provided, will eagerly match as much as possible). The following are therefore equivalent:

<<"st"::binary-size(2)-unit(8)>>
<<"st"::bytes-size(2)-unit(8)>>
<<"st"::bytes-size(2)>>
<<"st"::bytes-2>>

If no size is specified along with the binary modifier, it must be the final segment to be matched.

In addition to matching or destructuring, we can also construct a binary using the above options:

binary = <<
  1::1, # the integer 1 encoded as one bit,
  -100::unsigned-big-integer, # -100 encoded as unsigned int,
  "followed by some text",
  <<0,1,1>>, # and even nested raw binaries,
  1::7 # 1 encoded as 7 bits
>>

The above assigns the following value to binary:

<<
  206, 51, 55, 182, 54, 55, 187, 178, 178, 16, 49, 60, 144, 
  57, 183, 182, 178, 144, 58, 50, 185, 186, 0, 0, 128, 129
>>

We could also have mixed in floats. They must consist of 16, 32, or 64 bits and are always signed.

Advanced pattern matching

Now let's get to some actual parsing. Suppose you have a binary "message" that encodes data in the following format (intentionally looking somewhat like protobuff):

message SomeData {
  uint8 height_in_mm;
  float16 weight_in_kg;
}

Using binary pattern matching, you can extract the values like this:

<<
  height_in_mm::unsigned-integer,
  weight_in_kg::float-16
>> = binary

That's it, you've extracted the data from the message in a single match operation. But nothing fancy so far. A slightly more interesting example is one where a binary stores array data. The message spec could look like this:

message SomeData {
  uint8 non_array;
  uint8[4] data_array;
}

And it could be parsed like this:

<<
  non_array::unsigned-integer,
  data_array_binary::binary-size(4)
>> = binary

data_array =
  for <<value::unsigned-integer <- data_array_binary>> do
    value
  end

A hardcoded array length like that is hardly useful. What if we could encode the array length in the message itself?

message SomeData {
  uint8 length;
  uint8[length] data_array;
}

A binary encoding the information in the above message would start with a byte that indicates the length of the array, followed by length bytes and could be parsed like this:

<<
  length::unsigned-integer,
  data_array_binary::binary-size(length)
>> = binary

data_array =
  for <<value::unsigned-integer <- data_array_binary>> do
    value
  end

This would also work when the array length is 0. The binary could then consist of only a single null-byte. The length would be extracted as 0, and data_array_binary::binary-size(0) will then effectively match on the remaining empty binary and be happy.

This opens the door for conditional pattern matching. Suppose you have a message in which the first byte provides all kinds of information about the rest of the message:

message ConditionalMatching {
  1bit contains_height;
  1bit contains_weight;
  6bit six_more_unused_bits;
  optional(uint8, contains_height) height;
  optional(uint8, contains_weight) weight;
}

Then in principle you would be able to parse height and weight conditionally:

<<
  contains_height::1,
  contains_weight::1,
  _::6,
  height::unsigned-integer-size(contains_height*8),
  weight::unsigned-integer-size(contains_weight*8)
>> = binary

You will have noticed that you can do arithmetic within the size option. You are however limited to only the operators that are also allowed in guards: comparison, basic arithmentic, bitwise operators, in/not in etc. Note however that && and || are not allowed, and neither are function calls.

A similar interesting scenario is when a message contains dynamically typed data. For instance:

message SomeData {
  dynamic_value value;
}

Here the binary could contain one or more bytes that can be used to first identify the type of the data that is to follow, followed by the actual data. One could parse it as follows:

<<
  dynamic_type_id::unsigned-integer,
  rest::binary
>> = binary

type = Types.lookup(dynamic_type_id)

# type-specific parsing of `rest`

However, this strategy prevents you from parsing the entire message in one go (supposing you want to support the case of messages that contain multiple dynamically typed values), because you have no information about the length of the rest of the binary. A better way is to encode information about the type inside the type id. As a simple example, one could take the first 4 bits of the first byte to indicate size, and the last 4 to encode information about the type (integer vs float, signed vs unsigned). Obviously, there are countless ways of efficiently encoding information in this way, but lets assume the first 4 bits encode the bit size:

<<
  first_nibble_type_id::unsigned-integer-4,
  last_nibble_type_id::unsigned-integer-4,
  data_binary::binary-size(first_nibble_type_id)-unit(1),
  potentially_more_fields_here::binary
>> = binary

data = parse_according_to_type(last_nibble_type_id, data_binary)

Assuming that some further info was encoded in the last nibble. We might not have been able to fully parse the data all the way to its final type, but we were at least able to extract it from the parent binary without first stopping and doing a lookup. Many more such tricks exist, and remember that you can always try multiple patterns to deal with special cases:

case binary do
  <<first_pattern::unsigned-integer-8> -> ...
  <<second_pattern::float-16>> -> ...
end

Bonus

In one scenario I had to parse a message that contains multiple values with dynamic types. Unfortunately the type id was specced in such a way that you could determine the bit size from it only in certain cases.

I basically needed logic like:

bit_size =
  if last_nibble == 10 do
    if first_nibble == 0 do
      4
    else
      first_nibble
    end
  else
    first_nibble
  end

Unfortunately, if statements and the like are not allowed in the size option.

I could have matched on two patterns (one for the exception and one for the rule), but the possibilities double on every additional dynamically typed value and even though I generate the parsing code from the message specs, it didn't feel like the best way to go. Alternatively I could have parsed fields one by one, doing lookups on every step as needed, but this would have sacrificed leveraging binary parsing optimizations that are built into the BEAM.

I ended up with this kind of logic to determine the bit_size (taking inspiration from this SO) post):

import Bitwise

bit_size =  first_nibble +
   (1 + ((last_nibble - 10 ||| 10 - last_nibble) >>> 32)) *
     (1 +
        ((first_nibble - 0 ||| 0 - first_nibble) >>>
           32)) * 4

This accomplishes the same logic achieved earlier with if blocks. Of course, the RHS goes straight into the size option and is not first assigned to any value like I did here.

Another bonus

This one isn't strictly about pattern matching, but it is surprizing enough to warrant honourary mention. You may be aware that it is efficient to construct lists with the "cons" operator (|). That is, prepending an element to a list doesn't involve copying the old list into the new list, the new list simply points to the old one:

old_list = [1, 2, 3]
new_list = [0 | old_list]

Well, it turns out that there is a similar way to efficiently extend binaries under certain conditions. The Erlang runtime system optimizes appending elements to an existing binary, avoiding copying when possible. Suppose you want to append some bytes to a binary:

for byte <- [0, 1, 2, 3], reduce: <<>> do
  acc ->
    <<acc::binary, byte>>
end

In the above code, the binary is updated, not copied!!??!! It sounds crazy, you can read all about it here.

There is a built-in function for this specific case (turning a list into a binary), but it's good to know about the underlying principle.

Conclusion

Elixir's binary pattern matching and construction is insanely powerful. It differs from many other languages in that is has superb support for matching even individual bits. Most other languages require you to first extract the byte, and then use shifts and masks to get to the bit of interest.

Elixir is not the most performant, but if the binary data you are parsing is a sequence of independent messages, you can likely find ways to parse it concurrently.

Doing things only once in Elixir

Danie Palm — Fri, 07 Oct 2022 12:45:06 +0000

Listen very carefully, I shall say zis only once

It often so happens that multiple processes need the same, potentially expensive function to be executed. A common solution is to cache the computed value for future callers, but on a cold cache (or when a cached value expires) it could still happen that the function is executed multiple times. Such a spike in resource usage is known as the stampeding herd problem. If only the animals would proceed in an orderly fashion.

Elixir's GenServer provides the handle_call callback, which is guaranteed to execute synchronously. As such, if several processes make a call to a GenServer, they would execute sequentially, and the value could even be cached for the benefit of the next caller. Problem solved.

However, anything that runs within the handle_call or any other callback is blocking, potentially making the GenServer appear unresponsive and turn it into a bottleneck. Ever heard of Python's GIL :)

But what if the GenServer could dish out tasks to be executed as separate processes and keep the execution time of the callback to a minimum? To make this work, we need to cover two concepts.

`handle_call` doesn't have to reply immediately

You are probably familiar with the anatomy of a typical handle_call implementation:

def handle_call(request, from, state) do
  result, new_state = calculate_state(request, state )
  {:reply, result, new_state}
end

The :reply in the tuple means that the result will be sent immediately to the caller (the from). But handle_call may also return {:noreply, new_state} in which case the caller will be left hanging until it receives a reply or times out.

To send a reply to a caller after having initially returned {:noreply, new_state} we have to use GenServer.reply/2, which needs the from and some kind of result. This can be called from within any callback implementation.

`Task` is built on message passing

It's good advice to only call Task.async if you are also going to await the result. Typically you would do so with Task.await or some of the other functions available in the Task module. But under the hood these functions rely on receiving the result from the task by means of message passing. That is, they make use of Kernel.SpecialForms.receive/1 to wait for the result to roll in.

When you call Task.async from within a GenServer callback, you could await it with Task.await as usual, but for the duration of the computation of the task, the callback would be blocking, preventing the GenServer from handling any other calls. Depending on what you want from your GenServer this may defeat the purpose altogether.

Fortunately, within a GenServer you can await the success or failure of a task as you would await any other message - with a handle_info callback implementation:

def handle_info({ref, result}, state) do
  handle_task_success(ref, result, state)
end

def handle_info({:DOWN, ref, _, _, reason}, state) do
  handle_task_failure(ref, reason, state)
end

Make sure to guard that ref is a reference, otherwise you might catch unintended calls.

A solution

So here is a broad overview of a solution to the stampeding herd problem. Processes that are interested in the results of a function, can call a GenServer to provide them with the result. The GenServer returns the result if it has it, or spawns a Task to compute it and keeps track of the caller, or if it has spawned a Task in the past, it doesn't do so again, but still keeps track of the caller. On receiving the response, it notifies all the callers using GenServer.reply.

Here is the whole thing together:

defmodule GenHerder do
  use GenServer

  def start_link(opts \\ []) do
    GenServer.start_link(__MODULE__, [], Keyword.put(opts, :name, __MODULE__))
  end

  @impl true
  def init(_opts) do
    {:ok, %{}}
  end

  @impl true
  def handle_call(request, from, state) do
    case state[request] do
      nil ->
        task =
          Task.Supervisor.async_nolink(__MODULE__.TaskSupervisor, fn ->
            handle_request(request)
          end)

        {:noreply, Map.put(state, request, {:task, task, [from]})}

      {:task, task, froms} ->
        {:noreply, Map.put(state, request, {:task, task, [from | froms]})}

      {:result, result} ->
        {:reply, result, state}
    end
  end

  defp handle_request(_request) do
    :only_once_kenobi
  end

  @impl true
  def handle_info({ref, result}, state) when is_reference(ref) do
    handle_task_success(ref, result, state)
  end

  @impl true
  def handle_info({:DOWN, ref, _, _, reason}, state) do
    handle_task_failure(ref, reason, state)
  end

  defp handle_task_success(ref, result, state) do
    # The task succeeded so we can cancel the monitoring and discard the DOWN message
    Process.demonitor(ref, [:flush])

    {request, _task_and_froms} =
      Enum.find(state, fn
        {_request, {:task, task, _forms}} -> task.ref == ref
        _ -> false
      end)

    {{:task, _task, froms}, state} = Map.pop(state, request)

    state = Map.put(state, request, {:result, result})

    # Send the result to everyone that asked for it
    for from <- froms do
      GenServer.reply(from, result)
    end

    {:noreply, state}
  end

  defp handle_task_failure(ref, reason, state) do
    {request, _task_and_froms} =
      Enum.find(state, fn
        {_request, {:task, task, _forms}} -> task.ref == ref
        _ -> false
      end)

    {{:task, _task, froms}, state} = Map.pop(state, request)

    # Send the result to everyone that asked for it
    for from <- froms do
      GenServer.reply(from, {:error, reason})
    end

    {:noreply, state}
  end
end

You have to start it with something like this in a supervision tree:

children = [
          {Task.Supervisor, name: GenHerder.TaskSupervisor},
          GenHerder
        ]

Supervisor.start_link(children, Keyword.put(opts, :strategy, :one_for_one))

And then you can call it with:

GenServer.call(GenHerder, request, timeout)

Obviously, you can add nice wrappers around it. But a simpler way might be to use my package on hexpm. Call mix hex.info gen_herder for more info.

It implements the above with some sugar and also adds optional expiry of results.

Church encoding in the concatenative language Joy

Danie Palm — Sat, 25 Dec 2021 18:15:24 +0000

I've previously written about Church encoding in the Joy programming language. The article focused on booleans, logic and predicates, but didn't touch on numbers. Church numerals have been haunting me ever since, and after stumbling on two other concatenative languages, Dawn and Stck, things have finally fallen in place for me (avoiding an obvious pun here) and I've been able to simplify the Church boolean scheme as well. Instead of
updating my previous article, which would be a rewrite anyway, I'm doing a new article on Church encoding in Joy.

This article is technically part of the series Elixir of Life, but is intended to be self-contained.

Joy

Feel free to skip this intro to Joy if you've read any of my other Joy articles.

Joy is a functional, stack-based concatenative programming language developed by Manfred von Thun. It has many similarities to lambda calculus, combinatory logic, and Lisp. Like combinatory logic it differs from lambda calculus in that it doesn't feature lambda abstraction, the way in which formal parameters are specified in lambda calculus, and therefore does not have the concept of free variables. Joy differs from combinatory logic in that it is not based on function application, but rather on function composition. All joy functions, often called combinators, take a stack as its sole input and returns an updated stack as result. Joy uses postfix notation, also often called reverse Polish notation.

Joy is a fully-fledged programming language packed with all kinds of convenience functions that facilitate everyday program flow, such as conditional execution, repeated execution, recursion, and IO. It also comes with a rich set of types. But in this article, we begin to show how almost all of that can be thrown away and rebuilt from only a handful of functions and quotations. A quotations is essentially a program literal that takes the form of a list of functions that remain unevaluated unless explicitly executed. The following set of combinators, which can actually be reduced even more, is enough to render Joy Turing-complete:

dup  - duplicates the top of the stack
pop  - removes the top of the stack
swap - swaps the two tops elements of the stack
i    - executes a quotation (removes wrapping []'s)
unit - quotes the top of the stack (wraps it in []'s)
cons - prepends the element below the top of the stack to a quotation on top
cat  - concatenates the two top elements (quotations) of the stack

Here is a simple Joy program: [] [dup] [pop] swap i i, it evaluates to []. Terms are executed from left to right. We first place [], [dup], and [pop] on the stack. Then swap reads [pop] and [dup] from the stack, switches them around and puts them back on the stack. Next i unquotes [dup] which was on top of the stack, and thus causes it to be executed, duplicating [pop] which was right below it on the stack. Finally, the next i unquotes [pop] which then removes its duplicate that was below it on the stack. This leaves only [] on the stack.

Church encoding

Church encoding is a scheme by which any calculable operator and its data (operands) can be expressed purely in terms of functions. It has traditionally been explored mostly in the context of lambda calculus, but works well in concatenative languages, and - I imagine - Lisp, and combinatory logic. In fact, it works in
any Turing-complete language.

In simple terms, you only need a single primitive: the function. All other primitives (numbers, booleans, pairs, lists) can be encoded in terms of functions.

For example, in Joy (remember it uses postfix notation)it is possible to express the predicate 1 + 2 = 3 as follows:

1 2 + 3 =

where each of 1, 2, +, 3, and = is a composite function that is defined in terms of a handful of primitive functions such as dup, pop, swap, cat, unit, and cons. When executed, it leaves the value true on the stack (since the sum of 1 and 2 does in fact equal 3), where true is also a composite function defined in terms of a handful of primitives.

According to our scheme, the definition of true happens to be:

true == [pop]

But there are numerous different schemes, each with its own pros and cons (not avoiding an obvious pun here). There is no canonical representation of any literal, and its semantics as an operator (say +) or operand (say 1) arises from the scheme as a whole and how it maps onto logic and arithmetic.

In this article we employ a scheme in which literals are represented as quotations - function compositions that remain unevaluated until explicitly evaluated.

Church booleans

Booleans can be represented as functions that expect two values on the stack, returning the one argument if true and the other if false. In other words, we can write reduction rules for true and false as follows:

A B true i == A

and

A B false i == B

These reduction rules lead to the following definitions:

A B true i == A
A B true i == A B pop
A B true i == A B [pop] i
    true   ==     [pop]

A B false i == B
A B false i == B A pop
A B false i == A B swap pop
A B false i == A B [swap pop] i
    false   ==     [swap pop]

Don't stress if you don't quite yet follow the derivation process, we'll get back to it in more detail.

Note that we could easily reverse the definitions of true and false. As long as we construct the boolean operators correctly, the definitions of true and false are largely arbitrary.

While it is convenient to think of A and B as arguments of the functions true and false, they are in fact two elements on top of a stack that is the only argument of the functions.

Let's see true in action:

A B true i
A B [pop] i   # definition of true
A B pop       # i unquotes the element on top of the stack
A             # pop discards the top of the stack

Admittedly, there is nothing "boolean" here yet. The boolean nature of true and false will only appear once we introduce some operators. Note the need for i (apply) after the boolean function. It is required because true and false are quotations and therefore "inert" unless applied.

The first operator that we'll consider is and.

The `and` operator

The semantics we expect from and is as follows:

false false and == false
false true and == false
true false and == false
true true and == true

And we achieve that with the following definition of and:

and == dup i

It is easy to verify that the above definition works as expected, but it
is not immediately clear how we arrived at the solution. Let's start with
some reduction rules and work our way down to a definition. In case B is
true, the reduction rule is:

A B and == A

And in case B is false, the rule is:

A B and == B

In order to derive a definition for and we want to rewrite the reduction rules in the form:

A B and == A B C

where C is the definition of and. We do this by systematically introducing function compositions to the right hand side that are equivalent to the identity function id. This is similar to how introducing + 0 or + x - x to to a mathematical expression has no effect on its value.

We start with the case where B is true.

A B and == A                 # if B is true, only A counts
        == A B pop           # since B pop == id
        == A B [pop] i       # i unquotes [pop]
        == A B true i        # definition of true
        == A B B i           # since B is true

And in case B is false:

A B and == B                 # if B is false, we can ignore A
        == B A pop           # since A pop is a no-op
        == A B swap pop      # A B swap == B A
        == A B [swap pop] i  # [swap pop] i == swap pop
        == A B false i       # definition of false
        == A B B i           # since B is false

And so we arrive at a common reduction rule that is independent of the value of B:

A B and == A B B i
        == A B dup i

And therefore:

and == dup i

The `or` operator

We expect the following semantics from an or operator:

false false or == false
false true or == true
true false or == true
true true or == true

Using the same deductive process as before, we arrive at the following
definition:

or == [dup] swap unit cat i swap i
   == [dup] dip swap i      # defining dip == swap unit cat i

At first glance this is quite a bit more involved than the and operator,
but we'll get to a more elegant definition below.

The `not` operator

The not operator should simply negate the boolean that is on top of the
stack:

false not == true
true not == false

Let us once again work our way down from reduction rules to a definition. If A is true, then:

A not == false
      == false true pop     # true pop == id
      == false true [pop] i # quote then unquote
      == false true true i  # definition of true
      == false true A i     # since A is true

And similarly, when A is false:

A not == true
      == true false pop
      == false true swap pop
      == false true [swap pop] i
      == false true false i
      == false true A i  # since A is false

Now, regardless of the value of A:

A not == false true A i
A not == A [false true] dip i
  not == [false true] dip i

Armed with not, the definition of or simplifies to:

or == dup not i

We can also define nand == and not and nor == or not. Incidentally, nand
and nor are the only two functionally complete operators, meaning that reduction rules for any other boolean operator can be written purely in terms of either nand or nor. Let's briefly look at how nand can be implemented using only nor:

A B nand == A A nor B B nor nor A A nor B B nor nor nor

And, for symmetry, how nor can be implemented using only nand:

A B nor == A A nand B B nand nand A A nand B B nand nand nand

The reader is invited to check the veracity of these reduction rules and to derive definitions for nand and nor from them.

Conditionals

So far we have seen how choosing true == [pop] and false == [swap pop] has
allowed us to devise definitions for all the usual boolean operators. Our choice, which is not the only possible choice, is based on the idea of selectively discarding functions. I.e., pop the top of the stack, or pop the value below the top of the stack.

It is not surprizing then that we can also define functions that behave like
conditionals or if-then-else blocks. We have essentially already come across a primitive if-then-else block in the definition of not.

We can take this one step further and define branch with the following reduction rule:

cond [then] [else] branch == then # if cond is true
cond [then] [else] branch == else # if cond is false

cond [then] [else] branch == [then] i # if cond is true
cond [then] [else] branch == [else] i # if cond is false

cond [then] [else] branch == [then] i # if cond is true
cond [then] [else] branch == [else] i # if cond is false

cond [then] [else] branch == [then] [else] pop i # if cond is true
cond [then] [else] branch == [then] [else] swap pop i # if cond is false

cond [then] [else] branch == [then] [else] [pop] i i # if cond is true
cond [then] [else] branch == [then] [else] [swap pop] i i # if cond is false

cond [then] [else] branch == [then] [else] true i i # if cond is true
cond [then] [else] branch == [then] [else] false i i # if cond is false

cond [then] [else] branch == [then] [else] cond i i # if cond is true
cond [then] [else] branch == [then] [else] cond i i # if cond is false

# from this point onward the reduction rule is valid for any value of cond
cond [then] [else] branch == [then] [else] cond i i
cond [then] [else] branch == cond [then] [else] dig2 i i
cond [then] [else] branch == cond [then] [else] unit cons dip i i
                   branch == unit cons dip i i

We now have a simple conditional. If the condition is true we execute a then-block, otherwise we execute an else-block. It would be more useful if we also had a conditional block, so to speak. I.e. a quotation that, when executed, yields a boolean. This is where comparators like =, <, and > would be useful.

In order to arrive at definitions for such comparators, we need to look at Church numbers first.

Church numerals

Where Church booleans were centred around optional execution, Church numbers are centred around multiple execution.

A quick note on terminology. I will use "numeral" and "number" interchangeably, but they are not the same thing. "Numeral" is syntax, "number" is semantics. Both the Arabic numeral "3" and the Roman numeral "III" can have the meaning of the number three in the right context.

The semantics we are looking for is this:

[A] 0 i ==
[A] 1 i == A
[A] 2 i == A A
[A] 3 i == A A A
.
.
.
[A] N i == A A A ... A

A definition for 0 that satisfies the above reduction rule is 0 == [pop]. Similarly, 1 == [i] will do as a definition for 1. For 2, things are slightly more complicated:

[A] 2 i == A A
        == [A A] i
        == [A] [A] cat i
        == [A] dup cat i
        == [A] [dup cat i] i
      2 == [dup cat i]

We are hoping for some kind of pattern to emerge, so that we don't need a new definition for every
numeral. Let's take a look at 3:

[A] 3 i == A A A
        == [A A A] cat i
        == [A A] [A] cat i
        == [A] [A] [A] cat cat i
        == [A] [A] dup cat cat i
        == [A] dup dup cat cat i
        == [A] [dup] 2 i [cat] 2 i i
        == [A] [[dup] 2 i [cat] 2 i i] i
      3 == [[dup] 2 i [cat] 2 i i]

That gives us a definition of 3 in terms of its predecessor 2. We could expand the definition
all the way and replace 2 with [dup cat i], but we won't gain much in doing so. Let's rather find out whether the pattern continues. I.e. can we define 4 in terms of its predecessor 3? It turns out that we can - the reader is invited to find a derivation - and it also turns out that the pattern holds for all n where n > 0.

We now have a way to apply a quotation n times, but that in itself doesn't really mean that 2 has the semantics of the number two. Not without operators.

As a stepping stone to addition, the first operator that we'll consider is succ, the successor function.

The successor function `succ`

We expect the following semantics from a successor function:

0 succ == 1
1 succ == 2
2 succ == 3
.
.
.

In order to derive a definition for succ, we will exploit the fact that numbers are defined in
terms of their predecessors. That is, if N is our starting point, then by carefully positioning and manipulating N to arrive at [[dup] N i [cat] N i i], we will have found a definition for succ:

N succ == [[dup] N i [cat] N i i]
.
.
.
  succ == unit [i] cat [[dup]] swap dup [[cat]] swap [i] cat cat cat cat

Addition

Addition is the repetition of succession. Adding m to n is equivalent to calculating the m*th successor of *n. This leads us to the following reduction rule:

N M + == N succ succ ... succ         # succ repeated M times
N M + == N [succ] M i
N M + == N M [succ] swap i
    + == [succ] swap i

For example:

2 3 +
2 3 [succ] swap i
2 [succ] 3 i
2 succ succ succ
3 succ succ
4 succ
5

Multiplication

Multiplication can be defined in terms of addition. The product of n and m is equivalent to adding n m times to 0. That is, 2 times 3 is 0 + 2 + 2 + 2. We can generalize multiplication with the following reduction rule:

N M × == 0 N + N + ... N +      # "N +" repeated M times
N M × == 0 [N +] M i
N M × == [N +] M 0 bury2 i
N M × == N [+] cons M 0 bury2 i
N M × == N M [[+] cons] dip 0 bury2 i
    × == [[+] cons] dip 0 bury2 i

For example:

2 3 ×
2 3 [[+] cons] dip 0 bury2 i
2 [+] cons 3 0 bury2 i
[2 +] 3 0 bury2 i
0 [2 +] 3 i
0 2 + 2 + 2 +
2 2 + 2 +
4 2 +
6

Exponentiation

The derivation of the pow function is very similar to that of ×. However, instead of repetitively adding a value to 0, we now rather multiply 1 repetitively by some value. That is 2^3 is equivalent to 1 times 2 times 2 times 2. Or, in general:

N M pow == 1 N × N × ... N ×       # N × repeated M times
N M pow == 1 [N ×] M i
.
.
.
    pow == [[×] cons] dip 1 bury2 i

For example:

2 3 pow
2 3 [[×] cons] dip 1 bury2 i
2 [×] cons 3 1 bury2 i
[2 ×] 3 1 bury2 i
1 [2 ×] 3 i
1 2 × 2 × 2 ×
2 2 × 2 ×
4 2 ×
8

Predecessor function

So far, we've only dealt with functions that increase the value of a number. To get to subtraction, division, and roots, we need to start with
a predecessor function pred. Here is what we expect from a predecessor function:

0 pred == 0       # I'll explain this later
1 pred == 0
2 pred == 1
3 pred == 2
.
.
.

Defining pred using Church encoding is quite complicated. Here is how we will go about it. We want to start at 0 and repetitively add 1 to it, but instead of repeating this n times, we'll repeat it n - 1 times. In a sense, that just defers the problem, because now we have to figure out when to stop. The secret lies in applying some
function that will act like succ n times, except for the very first application. This we can achieve by maintaining a boolean along with our numerical value that keeps track of whether we are at the first function application or not. This leads us to the following reduction rule:

N pred == 0 false [[succ true] [true] branch] N i

From which we can derive a definition:

pred == 0 false dig2 [[succ true] [true] branch] swap i pop

To illustrate how it works, let's consider 2 pred:

2 pred
2 0 false dig2 [[succ true] [true] branch] swap i pop
0 false 2 [[succ true] [true] branch] swap i pop
0 false [[succ true] [true] branch] 2 i pop
0 false [succ true] [true] branch [succ true] [true] branch pop
0 true [succ true] [true] branch pop
0 succ true pop
1 true pop
1

Note that the predecessor of 0 is 0. The encoding we are dealing with here only applies to the natural numbers, so
no negatives. Extending the encoding to integers and reals and even complex numbers is possible, but not within
the scope of this article.

Subtraction

Equipped with pred, we can move on to subtraction (-):

N M - == N [pred] M i

And thus:

- == [pred] swap i

Church comparators and predicates

So far we have looked at Church booleans and Church numbers. We even had to combine them to arrive at a definition for pred. We now
turn to predicates. The first predicate we look at is is-zero. In order to arrive at a definition for is-zero, we will exploit the
fact that the numeral 0 can be used to apply some quoted function zero times, whereas any other numeral n, will apply the quoted
function n times. If we choose the quotation to be [pop false] and start with a value of true, then if we apply the function zero times,
we end up with true, which is what we want. If on the other hand we apply the function once or more, we will pop the initial true value
and replace it with false, only to pop false and replace it with false again, repeat n times. This leads us to the following reduction rules:

0 is-zero == true
1 is-zero == true pop false
2 is-zero == true pop false pop false
3 is-zero == true pop false pop false pop false
.
.
.
N is-zero == true [pop false] N i

And thus:

is-zero == [true [pop false]] dip i

Also, since n - m = 0 when m is larger than or equal to n, we can also make the following definitions:

<= == - is-zero

and

>= == swap - is-zero

Finally, if n <= m and n >= m, then we know that n = m:

m n = == m n <= m n >= and
m n = == [m n] i <= [m n] i >= and
m n = == [m n] [m n] [i <=] dip i >= and
m n = == [m n] [m n] [i <=] swap unit cat i i >= and
m n = == [m n] dup [i <=] swap unit cat i i >= and
m n = == m [n] cons dup [i <=] swap unit cat i i >= and
m n = == m n unit cons dup [i <=] swap unit cat i i >= and
    = ==     unit cons dup [i <=] dip i >= and

Advanced numerical operators

We have now built up a sizeable arsenal of composite operators and operands. It is time to address division and root extraction.

Division

The basic principle that we'll follow is that the quotient is the number of times that you can subtract the divisor from the dividend before you reach 0.
In other words 10 2 ÷ 5 = means that 10 [2 -] 5 i 0 = (subtracting 2 five times from 10 yields 0). In other words, in order to determine N M ÷ we want to start with a quotient of 1 (Q) and increment its value iteratively until the following no longer holds:

N [M -] Q i 0 >=

One way to achieve this is to use the y combinator, which makes anonymous recursion possible. In the base case, when our condition no longer holds, we terminate and only leave the quotient on the stack. In the recursive case, we increment the quotient and recheck the condition. The resulting reduction rule for division is:

N M ÷ == 0 true [
  bury2
  [
    succ dup [N [M -]] dip i 0 >= dig2 i
  ]
  [swap pop]
  branch
] y

The objective is to extract N and M to the front of the right hand side. The result is a definition for ÷:

÷ == [
  [[bury2] dip] dip
  [
    [[succ dup ] dip] dip [[-] cons] cons cons dip i 0 >= dig2 i
  ] cons cons
  [swap pop]
  branch
] cons cons [0 true] dip y

Root extraction

Determining the *n*th root is very similar to division. But instead of repetitive subtraction, we now employ repetitive division. This time we increment the root R until the following no longer holds:

N [M ÷] R i 1 >=

The reduction rule for root extraction looks like this:

N M √ == 0 true [
                    bury2
                    [
                      succ dup [N [M ÷]] dip i 1 >= dig2 i
                    ]
                    [swap pop]
                    branch
                  ] y

From which we can derive the definition of √:

√ == [
  [[bury2] dip] dip
  [
    [[succ dup ] dip] dip [[÷] cons] cons cons dip i 1 >= dig2 i
  ] cons cons
  [swap pop]
  branch
] cons cons [0 true] dip y

Putting it all together

We started out with the ambition to devise an encoding using only basic functions by which the following would evaluate to true:

1 2 + 3 =

Let's put it to the test (taking a few shortcuts here and there):

1 2 + 3 =
3 3 =
3 3 unit cons dup [i <=] dip i >= and      # definition of =
3 [3] cons dup [i <=] dip i >= and
[3 3] dup [i <=] dip i >= and
[3 3] [3 3] [i <=] dip i >= and
[3 3] i <= [3 3] i >= and
3 3 <= 3 3 >= and
3 3 - is-zero 3 3 swap - is-zero and
3 3 - is-zero 3 3 swap - is-zero and
0 is-zero 3 3 swap - is-zero and
0 is-zero 3 3 - is-zero and
0 is-zero 0 is-zero and
0 [true [pop false]] dip i 0 [true [pop false]] dip i and
true [pop false] 0 i true [pop false] 0 i and
true true and
true true [dup] dip swap i                # definition of and
true dup true swap i
true true true swap i
true true true i
true true [pop] i                         # definition of true
true true pop
true

Applications

Besides the ability to do simple arithmetic and logic, we can also put Church-encoding numerals to other use.

Digging and burying

One such application lies in generalizing stack shuffling functions like dig and bury.

The dig family of functions are used to dig values up from deep down on the stack. dig, or dig1 is equivalent to swap, whereas dig2 brings the second value below the top to the top. And so on. Here are definitions for some dig functions:

dig1 == [] cons dip
dig2 == [] cons cons dip
dig3 == [] cons cons cons dip

Clearly, the deeper you want to dig, the more cons functions are required. We can generalize dig as follows:

dign == [] [cons] N i dip

The bury family does the opposite. It buries the top of the stack. Once again, bury1 is equivalent to swap. Here are definitions for some bury functions:

bury1 == [[] cons] dip swap i
bury2 == [[] cons cons] dip swap i
bury3 == [[] cons cons cons] dip swap i

And likewise, we can generalize this to:

buryn === [[] [cons] N i] dip swap i

Summary of definitions

Miscellaneous helpers:

dip   == swap unit cat i
y     == [dup cons] swap cat dup cons i
dign  == [] [cons] N i dip
buryn == [[] [cons] N i] dip swap i

Boolean operators:

true   == [pop]
false  == [swap pop]
and    == dup i
or     == [dup] dip swap i
not    == [false true] dip i
nand   == and not
nor    == or not

Numerical operators:

N       == [[dup] M i [cat] M i i]
succ    == unit [i] cat [[dup]] swap dup [[cat]] swap [i] cat cat cat cat
+       == [succ] swap i
×       == [[+] cons] dip 0 bury2 i
pow     == [[×] cons] dip 1 bury2 i
pred    == 0 false dig2 [[succ true] [true] branch] swap i pop
-       == [pred] swap i
is-zero == [true [pop false]] dip i
÷       == [[[bury2] dip] dip [[[succ dup ] dip] dip [[-] cons] cons cons dip i 0 >= dig2 i] cons cons [swap pop] branch] cons cons [0 true] dip y
√       == [[[bury2] dip] dip [[[succ dup ] dip] dip [[÷] cons] cons cons dip i 1 >= dig2 i] cons cons [swap pop] branch] cons cons [0 true] dip y

where N is any natural number and M is the predecessor of N.

Conditionals and comparators:

branch == unit cons dip i i
<=     == - is-zero
>=     == swap - is-zero
=      == unit cons dup [i <=] dip i >= and

Sources and further reading:

Proteins as programs - to mock a matchingbird

Danie Palm — Wed, 28 Jul 2021 19:39:23 +0000

In this instalment of Elixir of Life we devise a mechanism by which chemical affinity and binding can be realized in our artificial life system. As a refresher, we are trying to build an artificial life system using an artificial chemistry that is based on programs that interact with one another. These programs are written in a restricted version of the stack-based Joy programming language in which we permit only functions and quotations. This restricted version of Joy is implemented in Elixir, and as a side-effect we explore several features of Elixir along the way.

One of the Elixir features that we encounter in this post is the idea of using mocks to fulfil explicit contracts when testing code using the mox library. Coincidentally, Joy has strong ties to combinatory logic, its applicative cousin. Combinatory logic was invented by Moses Schönfinkel (German for something like "pretty finch"), elaborated on by Haskell Curry, and popularized by Raymond Smullyan in the delightful little book To Mock a Mockingbird.

In this book Smullyan likens function application in combinatory logic to birds (some of which are finches) calling out the name of a bird upon hearing the name of a bird. One of the popular birds in the book is the Mockingbird, which when hearing the bird name x will make the same call that x would have made hearing its own name. When a mocking bird hears its own name, it results in one of the most elegant self-reproducing "programs" or quines in existence.

If functions are birds, then this post will introduce a couple of matchingbirds. That kind of explains the title.

Chemical recognition, affinity, and binding

The enzymatic complexes that initiate or catalyse the processes of transcription and translation often rely on recognizing patterns within the substrate sequences on which they operate. Examples of such patterns are the TATA box sequence, a stretch of DNA that indicates where transcription should begin, and the Shine-Dalgarno sequence, which lies upstream of the start codon AUG in bacterial and archaeal mRNA. We could even consider the start and stop codons of the genetic code to fall into this category of "sequences with meanings that need to be recognized".

While we could implement functionality that allows enzymes to recognize such sequences
with a predicate function like equal (as we have done up to now), the strict matching that we
get in such an implementation precludes any mistakes and variations from creeping in. Moreover, in biochemistry, sequences often match one another in a complementary way. Consider, for instance, how purines (A and G) strongly prefer to pair with pyrimidines (C and T/U) and weakly, if at all, with themselves. At first glance, such strong complementarity might not be obvious elsewhere in biochemistry, but consider how enzymatic substrate binding sites are really complementary to their substrates. Also consider how a single binding site could bind multiple related substrates, perhaps with different affinities or strengths.

So we turn to something fuzzy instead.

The `match` predicate function

The match function is a predicate that returns true with a probability that is proportional to the degree to which a candidate C matches a given pattern P, taking complementary binding into account as appropriate. In other words:

C P match == B

where B is a boolean value or, when using Church-encoding, [pop i] for true and [swap pop i] for false. In other words, match is more likely to return [pop i] for values of C that strongly match P. Let us consider a few concrete examples involving nucleotide bases. Note that the results are probabilistic, I'm providing the most probable answer:

# individual RNA bases
a u match == true
a g match == false

# sequences of bases
[] [] match == true
[] [a] match == false
[a u g] [u a c] match == true

But how does match determine how well the candidate matches the pattern?

Recall the second post of this series in which we've implemented the Needleman-Wunsch global sequence alignment algorithm and hinted at using (complementary) sequence alignment scores as mechanisms by which binding affinity could be determined. In the meantime, I've extended that work to include the Smith-Waterman local sequence alignment algorithm, and modularized the code to allow pluggable implementations of the similarity score. These alignment algorithms are available in the belign library which I hope to open-source at some point.

This will allow us to determine a similarity or rather "match" score for any two molecules in our system.

Let's have a look at the implementation of match in our base language Elixir:

def match([pattern, candidate | tail] = _stack) do
  # Determine the match score between the pattern and the candidate
  score = Belign.Similarity.Global.similarity(pattern, candidate)
  # Calculate a binding probability from the score
  binding_probability = Float.pow(score * 1.0, 10)
  # Pick a random pivot
  pivot = Slyk.Random.random()

  # Consider it a match if the binding probability is larger than the pivot.
  # @truthy equals [pop i] and @falsy equals [swap pop i] as per a previous
  # post on Church-encoding of booleans
  if binding_probability > pivot do
    [@truthy | tail]
  else
    [@falsy | tail]
  end
end

The comments explain the code fairly well. The heavy lifting is of course done in Belign.Similarity.Global.similarity/2. Without going into the details, you can imagine that function as representing a similarity matrix that has rows and columns for each molecule (function or quotation) in our artificial life system. The value at i,j in this matrix represents how well the candidate j matches the pattern i.

One aspect to highlight is that the similarity function can also deal with cases in which the pattern or candidate is not just a single function, but a list of functions (a quotation). This is where the Needleman-Wunsch algorithm comes in. When dealing with quotations, the similarity function delegates to
Belign.align_global(pattern, candidate, opts). One of the options that is passed as the final argument is
this: similarity: Belign.Similarity.Global which tells the Needleman-Wunsch algorithm to use Belign.Similarity.Global.similarity/2 as it's similarity score function. This recursive relationship between Belign.Similarity.Global.similarity/2 and Belign.align_global/3 means that we can determine the degree to which molecules, containing arbitrary levels of nesting, match one another.

Testing the `match` predicate function

We have not discussed testing in any of the posts so far. However, a solid suite of tests at every level of abstraction
is going to be indispensable as we go forward. For most of the functions we've come across so far, unit tests are trivial to implement. The pure nature of these functions means that a given input will always lead to a given output. So we just have to think of all the cases we can hit, and we're done.

Here is a first approach at testing the match function.

test "match/1 correctly matches complementary mRNA sequences" do
  assert ~J"[a u g] [u a c] match" == ~J"true"
  assert ~J"[a u u] [u a c] match" == ~J"false"
  assert ~J"[a u c] [u a c] match" == ~J"false"
  assert ~J"[a u a] [u a c] match" == ~J"false"
  # ... and many more
end

However, the test only passes for a fraction of the times that we run it. This is because the match function is not a pure function. It has a random component to it. This is where mox comes in. Slyk.Random.random/0 delegates to an underlying implementation. Under normal operating
conditions, it delegates to a function that calculates a uniform random floating point number between 0 and 1. An implementation of which looks like this:

defmodule Slyk.Random.Uniform do
  @behaviour Slyk.Random.Behaviour

  @impl Slyk.Random.Behaviour
  @spec random :: float
  def random() do
    :rand.uniform()
  end
end

When we test however, we want a controlled environment, which we can obtain by using a mock implementation of Slyk.Random. We add the following to our test/test_helpers.exs file:

Mox.defmock(Slyk.Random.Mock, for: Slyk.Random.Behaviour)

And then modify the test like this:

test "match/1 correctly matches complementary mRNA sequences" do
  # Tell Slyk.Random to delegate to Slyk.Random.Mock
  Application.put_env(:slyk, Slyk.Random, implementation: Slyk.Random.Mock)

  # Provide a case-specific stub implementation of Slyk.Random.Mock
  Slyk.Random.Mock
  |> stub(:random, fn ->
    0.8
  end)

  # The score is always above 0.8 for the first case
  assert ~J"[a u g] [u a c] match" == ~J"true"
  # The score is always below 0.8 for the last three cases
  assert ~J"[a u u] [u a c] match" == ~J"false"
  assert ~J"[a u c] [u a c] match" == ~J"false"
  assert ~J"[a u a] [u a c] match" == ~J"false"
end

A primordial soup, a slimy pool

We are now finally getting close to a point where we have all the basic components required to realize our artificial life system. One of the last hurdles that we need to overcome is to devise a mechanism by which molecules (programs) in our system can bind, react, and dissociate.

For illustration purposes, the ribosome has been used like this so far:

mrna ribosome # leaves an unfolded protein on the stack

This of course doesn't tell us how the mRNA ended up on the stack in the first place. What we really want is for molecules, and specifically enzymes like the ribosome, to bind their substrates from a pool of possibilities according to an inherent affinity. And to explicitly release any products to the pool, rather than leaving them on the stack.

Enter getl, getg, and put. The former two are similar to Joy's built-in get function which waits for input from the standard input. But they are actually closer to Elixir's IO.gets/1 which takes a prompt as argument and then waits for input. Likewise, put is similar to Joy's put and Elixir's IO.puts/1 that write a string to the standard output.

But instead of writing and reading strings to and from standard IO, we implement getl and getg to "read" a candidate program that matches a pattern (prompt) from a pool of programs using, respectively, the local (Smith-Waterman) and global (Needleman-Wunsch) alignment algorithms and placing the program on the stack as a quotation. Similarly, put takes a program from the top of the stack and inserts it into a pool of programs.

The pool that I'm referring to here is similar enough to the slimy one that we've described in the very first post of this series that I will not discuss it again, except to say that in its latest incarnation it implements the Slyk.Pool behaviour so that we can easily test programs that rely on it using a mock pool implementation. More on this in upcoming posts.

Here are the Elixir implementations for getl (getg is similar) and put:

def getl([pattern | tail] when is_list(pattern)) do
    {:ok, match} = Slyk.Pool.getl(pattern)
    [match | tail]
  end
end

def put([head | tail] when is_list(head)) do
  Slyk.Pool.put(head)
  tail
end

The default Slyk.Pool implementation is backed by a GenServer. This means that, for instance, Slyk.Pool.getl delegates to Slyk.Pool.Default.getl, which uses GenServer.call to make a synchronous request to a GenServer process, which when it deals with the incoming message, executes a callback that looks like this:

def handle_call({:getl, prompt}, _from, state) do
  # Get a random pivot value
  pivot = Slyk.Random.random()

  # Find the index of the first element that has a
  # binding probability that is larger than the random pivot
  state
  |> Enum.find_index(fn candidate ->
    score = Belign.Similarity.Local.similarity(prompt, candidate)

    binding_probability = Float.pow(score * 1.0, 10)
    binding_probability > pivot
  end)
  |> case do
    nil ->
      {:reply, {:error, :no_match}, state}

    index ->
      {winner, rest} = List.pop_at(state, index)
      {:reply, {:ok, winner}, rest}
  end
end

The probability function is a tenth-degree polynomial. We might refine this later, but for now it maps 0 to 0, 1 to 1, and most values in between to something close to 0.

For completeness, here is the callback that handles put. Slyk.Pool.Default.put uses GenServer.cast, which makes it asynchronous. This is appropriate because we are not interested in a reply from the pool process after it inserts the element in the pool.

def handle_cast({:put, element}, state) do
  {:noreply, [element | state]}
end

Testing the waters

There are various levels of abstraction at play here that require testing. We need to test Slyk.Pool.Default to ensure that Slyk.Pool.Default.put, Slyk.Pool.Default.getl and Slyk.Pool.Default.getg behave as expected. In these tests we care about the implementation details and so essentially wish to test the callback functions. The callback for put is easy to test because it is pure. The callback for getl, on the other hand again calls Slyk.Random.random() for which we will use a mock:

  describe "handle_call({:getl, [:a, :u, :g]}" do
    test "binds [:u, :a, :c], regardless of where it is located in the pool" do
      Slyk.Random.Mock
      |> stub(:random, fn ->
        0.8
      end)

      # winning candidate at end of pool
      pool = [[:random], [:molecules], [:u, :a, :c]]

      assert {:reply, {:ok, [:u, :a, :c]}, [[:random], [:molecules]]} =
               Slyk.Pool.Default.handle_call({:getl, [:a, :u, :g]}, make_ref(), pool)

      # winning candidate in middle of pool
      pool = [[:random], [:u, :a, :c], [:molecules]]

      assert {:reply, {:ok, [:u, :a, :c]}, [[:random], [:molecules]]} =
               Slyk.Pool.Default.handle_call({:getl, [:a, :u, :g]}, make_ref(), pool)

      verify!()
    end

    test "fails if [:u, :a, :c] or something similar is not present" do
      Slyk.Random.Mock
      |> stub(:random, fn ->
        0.8
      end)

      # the pool
      state = [[:random], [:molecules]]

      assert {:reply, {:error, :no_match}, [[:random], [:molecules]]} =
               Slyk.Pool.Default.handle_call({:getl, [:a, :u, :g]}, make_ref(), state)

      verify!()
    end
  end

At a higher level, we should be testing our newly introduced Joy functions getl, getg, and put. Their functionality is, however, independent of the underlying pool implementation, so instead of mocking Slyk.Random, we can opt to mock Slyk.Pool instead. At yet a higher level, we need tests for entire programs (proteins) and how they interact with their environment. More on that in another post.

Conclusion

We are now approaching a chemical system in which molecules can be "activated" one at a time (or concurrently - effortlessly because of Elixir). Molecules are Joy programs and activation means execution. Joy programs are really function compositions (syntactically, whitespace represents the composition operator) that are made up of functions like pop and swap, and quotations which are lists of functions. A quotation is actually also just a function that places itself on the stack.

Using special getl/getg and put IO-like functions, molecules can "bind" or recruit other molecules from the mix, just like enzymes or proteins would bind their substrates. They can also "release" products back into the pool. It might turn out that only one of getl and getg is required. That will be a happy day, but for now getl will probably be more useful in binding polymers and getg will be more useful in binding oligomers/monomers.

In addition, we have explored preliminary implementations of a ribosome (something like a universal constructor) and a "chaperone" (something like a universal assembler). We have also defined a preliminary artificial genetic code. Armed with the notions of affinity, association, and dissociation developed in this post, we can now develop fully-fledged ribosomes, chaperones, and the multitude of other enzymes that we'll need (this is only the beginning). We can also then define the final version of an artificial genetic code, which we'll use to reverse-construct something like DNA, which will contain recipes for all the enzymes and rRNA in our system.

LiveJoy with Phoenix LiveView

Danie Palm — Sat, 21 Nov 2020 13:24:28 +0000

In a previous post, I've introduced an interpreter for the Joy programming language implemented in Elixir. The library includes a REPL that allows one to play with Joy in an interactive session.

While it is straightforward to get the Joy REPL up and running, it is perhaps too much effort for someone with only a mild interest in Joy and Elixir. So here is LiveJoy, a web-based Joy REPL:

https://live-joy.herokuapp.com

It runs on free tier Heroku, so please be patient with the start up.

No JavaScript added

LiveJoy is peculiar in the sense that it doesn't require a single line of added JavaScript, and yet it is very much interactive.

To be fair, LiveJoy does use JavaScript - a relatively small piece of it that ships with Phoenix LiveView. Phoenix is a lean and performant web-framework for Elixir, and LiveView is a Phoenix add-on that gives you real-time server-rendered pages. There is just enough JavaScript in LiveView to communicate client-side events to the server and to cleverly update the DOM from server-side generated diffs.

Phoenix LiveView

LiveView pages are backed by GenServer-like processes which keep as state a websocket connection as well as information about which parts of the page are static and which parts are dynamic (those parts that are likely to change with state changes).

Client-side initiated socket requests end up as messages in the inbox of the server-side process that backs the page, and are thus able to alter the page state. In response, a diff is sent back to the client with the information required to update the DOM.

The server can also initiate page updates without any prompt from the client. For instance, a timer could be associated with the LiveView process to fire periodically, sending updates to the client.

Apart from the initial page render, which uses normal HTTP, everything happens via websockets.

LiveJoy implementation

With LiveJoy being a kind of REPL, the state we need to keep is as follows:

input - a list of strings representing the historical input
output - a list of strings representing the historical output
stack - because Joy is a stack-based language
current_input - the current unsubmitted and unevaluated input

Template

Here is a LiveView template that relies on the state to yield an interactive REPL. I first show the whole template and then break it up into parts.

<div class="Terminal__body" phx-window-keyup="input">
  <div class="Terminal__splash">&nbsp;&nbsp;&nbsp;_</div>
  <div class="Terminal__splash">&nbsp;&nbsp;|_|___ _ _</div>
  <div class="Terminal__splash">&nbsp;&nbsp;| | . | | |</div>
  <div class="Terminal__splash">&nbsp;_|&nbsp;|___|_&nbsp;&nbsp;|</div>
  <div class="Terminal__splash">|___|&nbsp;&nbsp;&nbsp;|___|</div>

  <div class="Terminal__splash">Interactive Joy</div>

  <%= for {input, output} <- Enum.reverse(Enum.zip(@input, @output)) do %>
    <div class="Terminal__prompt">
      <span class="Prompt__location">joy> </span>
      <span class="Prompt__dollar"><%= input %></span>
    </div>
    <div class="Terminal__text"><%= output %></div>
  <% end %>

  <div class="Terminal__prompt">
    <span class="Prompt__location">joy> </span>
    <span class="Prompt__dollar"><%= Enum.join(Enum.reverse(elem(@current_input, 0))) %></span><span class="Prompt__cursor"><%= case elem(@current_input, 1) do
      [] -> raw("&nbsp;")
      seq -> hd(seq)
    end %></span><span class="Prompt__dollar"><%= case elem(@current_input, 1) do
      [] -> ""
      seq -> Enum.join(tl(seq))
    end %></span>
  </div>
</div>

The outermost element is a plain old div:

<div class="Terminal__body" phx-window-keyup="input">
  ...
</div>

The only special part is the phx-window-keyup attribute. This tells LiveView to send key-up events to the server. These are the only events we'll be using. More on that later.

Next up, is a static piece of HTML that simply renders the Joy splash:

  ...
  <div class="Terminal__splash">&nbsp;&nbsp;&nbsp;_</div>
  <div class="Terminal__splash">&nbsp;&nbsp;|_|___ _ _</div>
  <div class="Terminal__splash">&nbsp;&nbsp;| | . | | |</div>
  <div class="Terminal__splash">&nbsp;_|&nbsp;|___|_&nbsp;&nbsp;|</div>
  <div class="Terminal__splash">|___|&nbsp;&nbsp;&nbsp;|___|</div>

  <div class="Terminal__splash">Interactive Joy</div>
  ...

And then we get to the historic inputs and outputs:

  ...
  <%= for {input, output} <- Enum.reverse(Enum.zip(@input, @output)) do %>
    <div class="Terminal__prompt">
      <span class="Prompt__location">joy> </span>
      <span class="Prompt__dollar"><%= input %></span>
    </div>
    <div class="Terminal__text"><%= output %></div>
  <% end %>
  ...

Both input and output are lists. We zip them together to produce a list of input/output tuples, which we reverse to put the oldest ones at the top. And then for each pair we create markup that mimics terminal input and output. If either input or output changes, the server will rerender the HTML (the affected parts at least) and send the change info to the client. The end result is that a new input/output pair appears on each evaluation of user input.

And here is the part that handles the current input line of the terminal:

   ...
   <div class="Terminal__prompt">
    <span class="Prompt__location">joy> </span>
    <span class="Prompt__dollar"><%= Enum.join(Enum.reverse(elem(@current_input, 0))) %></span><span class="Prompt__cursor"><%= case elem(@current_input, 1) do
      [] -> raw("&nbsp;")
      seq -> hd(seq)
    end %></span><span class="Prompt__dollar"><%= case elem(@current_input, 1) do
      [] -> ""
      seq -> Enum.join(tl(seq))
    end %></span>
  </div>
  ...

The current_input is a tuple of two lists. The first/left list represents all the characters to the left of the cursor (in reverse). Whereas the second/right list contains all the characters to the right of the cursor (if any) and at the cursor itself. The head of the left list is the character immediately to the left of the cursor. The head of the right list is the character at the cursor.

We render the characters in the left list, reversing them first, with:

<span class="Prompt__dollar"><%= Enum.join(Enum.reverse(elem(@current_input, 0))) %></span>

Followed by the cursor (which could be over the head character of the right list):

<span class="Prompt__cursor"><%= case elem(@current_input, 1) do
      [] -> raw("&nbsp;")
      seq -> hd(seq)
    end %></span>

And finally any characters to the right of the cursor (excluding the first one if we are not at the end of the line):

<span class="Prompt__dollar"><%= case elem(@current_input, 1) do
      [] -> ""
      seq -> Enum.join(tl(seq))
    end %></span>

That's all there is to the template. You may have noticed that we are not making use of any HTML inputs whatsoever. This is probably an abuse of LiveView and you should really make use of inputs instead. But how did we get away without them?

Event handling

The basic idea is to rely on key-up events that represent character key strokes, arrow navigation, backspace or enter. Remember that phx-window-keyup attribute? Here are the events for which the server is listening and the callbacks that are invoked for each case:

Enter - evaluates and clears current_input and updates input, output, and the stack

  def handle_event("input", %{"key" => "Enter"}, socket) do
    %{
      assigns: %{
        current_input: current_input,
        input: input_rest,
        output: output_rest,
        stack: stack
      }
    } = socket

    {left, right} = current_input
    input = Enum.join(Enum.reverse(left)) <> Enum.join(right)

    case evaluate(input, stack) do
      {:ok, output, stack} ->
        {:noreply,
         socket
         |> assign(
           current_input: {[], []},
           input: [input | input_rest],
           output: [output | output_rest],
           stack: stack
         )}

      {:error, output, stack} ->
        {:noreply,
         socket
         |> assign(
           current_input: {[], []},
           input: [input | input_rest],
           output: [output | output_rest],
           stack: stack
         )}
    end
  end

Backspace - pops the head off the left list in current_input

  def handle_event("input", %{"key" => "Backspace"}, socket) do
    %{assigns: %{current_input: {left, right}}} = socket

    left =
      case left do
        [] -> []
        [_] -> []
        [_ | tail] -> tail
      end

    {:noreply,
     socket
     |> assign(current_input: {left, right})}
  end

LeftArrow - pops the head off the left list in current_input and pushes it onto the right list

  def handle_event("input", %{"key" => "ArrowLeft"}, socket) do
    %{assigns: %{current_input: {left, right}}} = socket

    {left, right} =
      case {left, right} do
        {[], right} -> {[], right}
        {[left_head | left_tail], right} -> {left_tail, [left_head | right]}
      end

    {:noreply,
     socket
     |> assign(current_input: {left, right})}
  end

RightArrow - pops the head off the right list in current_input and pushes it onto the left list

  def handle_event("input", %{"key" => "ArrowRight"}, socket) do
    %{assigns: %{current_input: {left, right}}} = socket

    {left, right} =
      case {left, right} do
        {left, []} -> {left, []}
        {left, [right_head | right_tail]} -> {[right_head | left], right_tail}
      end

    {:noreply,
     socket
     |> assign(current_input: {left, right})}
  end

any single character key - pushes the character onto the left list in current_input

  def handle_event("input", %{"key" => <<key :: binary-size(1)>>}, socket) do
    %{assigns: %{current_input: {left, right}}} = socket

    {:noreply,
     socket
     |> assign(current_input: {[key | left], right})}
  end

any thing else - leaves the state as is

  def handle_event("input", %{"key" => _key}, socket) do
    {:noreply, socket}
  end

Evaluation

The actual evaluation involves first parsing and then interpreting the input using the joy library that we've introduced in a previous post.

  defp evaluate(input, stack) do
    with {:ok, parsed_input} <- Joy.Parser.parse(input),
         {:ok, stack} <- Joy.Interpreter.interpret(parsed_input, stack) do
      output = Joy.Formatter.format(stack, direction: :stack)

      {:ok, output, stack}
    else
      {:error, reason} ->
        {:error, "Error: #{inspect(reason)}", stack}
    end
  end

The rest is LiveView boilerplate that you can read about in the official LiveView docs.

Styling

For the styling I've relied extensively on the following post:

Ubuntu Terminal in CSS

Cody Pearce ・ Feb 15 '20

#css #codepen #webdev #showdev

Here is my tweaked version, using some colours from the Aurora X VS Code theme:

body {
  margin: 0px;
  margin-left: 24px;
  background:#07090F;
  font-size: 13px;
}

.Terminal__body {
  background:#07090F;
  height: calc(100% - 25px);
  margin-top: -1px;
  padding-top: 2px;
  font-family: "Lucida Console", Monaco, monospace;
  width: 75%;
  float: left;
}

.Terminal__help {
  background:#07090F;
  height: calc(100% - 25px);
  margin-top: -1px;
  margin-left: 75%;
  color:#FFCB6B;
  padding-top: 2px;
  font-family: "Lucida Console", Monaco, monospace;
}

.Terminal__text {
  color: white;
}
.Terminal__splash {
  color: #82AAFF;
}

.Terminal__Prompt {
  margin-top: 10px;
  display: flex;
}

.Prompt__location {
  color: #C792EA;
}
.Prompt__dollar {
  color: white;
}

.Prompt__cursor {
  height: 13px;
  width: 8px;
  background: white;
}

Dockerized deploy on Heroku

LiveJoy is deployed on Heroku as a Docker container. The most important parts are the Dockerfile and heroku.yml files in the project root.

The Dockerfile is fairly standard for a Phoenix project. Notice the separation between the build and app stages. In the build stage, we build an Elixir release, which includes the Erlang runtime. The app stage is an almost vanilla alpine image, containing only the release that we copy over from the build stage, no extra Erlang/Elixir installation is required in the app stage:

FROM elixir:1.10.0-alpine AS build

# install build dependencies
RUN apk add --no-cache build-base npm git

# prepare build dir
WORKDIR /app

# install hex + rebar
RUN mix local.hex --force && \
    mix local.rebar --force

# set build ENV
ENV MIX_ENV=prod

# install mix dependencies
COPY mix.exs mix.lock ./
COPY config config
RUN mix do deps.get, deps.compile

# build assets
COPY assets/package.json assets/package-lock.json ./assets/
RUN npm --prefix ./assets ci --progress=false --no-audit --loglevel=error

COPY priv priv
COPY assets assets
RUN npm run --prefix ./assets deploy
RUN mix phx.digest

# compile and build release
COPY lib lib
# uncomment COPY if rel/ exists
COPY rel rel
RUN mix do compile, release

# prepare release image
FROM alpine:3.9 AS app
RUN apk add --no-cache openssl ncurses-libs

WORKDIR /app

RUN chown nobody:nobody /app

USER nobody:nobody

COPY --from=build --chown=nobody:nobody /app/_build/prod/rel/live_joy ./

ENV HOME=/app

CMD ["bin/live_joy", "start"]

The heroku.yml file tells Heroku how to build and run the image:

build:
  docker:
    web: Dockerfile

Having already set up an Heroku app according to the Heroku documentation, the only changes required are to set the stack type to "container" and to add some config:

heroku stack:set container
heroku config:set SECRET_KEY_BASE=Y0uRvErYsecr3TANDL0ngStr1ng

Heroku requires that you honour the PORT environment variable. And Phoenix will also need access to the SECRET_KEY_BASE we've set above. Let's set up the releases.exs file accordingly:

import Config

secret_key_base =
  System.get_env("SECRET_KEY_BASE") ||
    raise """
    environment variable SECRET_KEY_BASE is missing.
    You can generate one by calling: mix phx.gen.secret
    """

config :live_joy, LiveJoyWeb.Endpoint,
  http: [
    port: String.to_integer(System.get_env("PORT") || "4000"),
    transport_options: [socket_opts: [:inet6]]
  ],
  secret_key_base: secret_key_base,
  server: true

We can now deploy with the trusty old git push heroku master command.

Conclusion

Phoenix LiveView is an excellent framework for implementing rich real-time user experiences. The current project, which is close to an event-based editor is perhaps not the best application of Phoenix LiveView, but it was nevertheless fun to implement. Some of the drawbacks of this approach is that copy and paste is not supported. It would be possible to implement copy and paste behaviour using some JavaScript hooks, but this is a "no JavaScript added" post.

The Elixir Web Console is a more serious attempt at a REPL that uses Phoenix LiveView, which also supports copy and paste.

Church Booleans in Joy

Danie Palm — Sat, 24 Oct 2020 12:21:04 +0000

Update: I've since extended the post such that the composed ifte function is now semantically identical to the built-in primitive ifte function.

In some of the preceding posts of this series on an artificial life system in the Joy programming language, we have programmed a number of proteins. Conditional execution has been a crucial component of these protein programs. The need for branching logic has surfaced mostly in the recursive sections of our programs: if the base case is met then terminate else recurse.

Nevertheless, the use of the ifte (if-then-else) and true and false Joy functions isn't as pure as it could be for our purposes. First, I would like to limit the data types to only functions and quotations (lists of functions). We have already banished numbers and sets, but had to hold on to Booleans. Second, the ifte function strikes me as being too high-level to be implemented as a primitive.

To be fair, "high-level primitives", numbers, sets, booleans, and strings are perfectly acceptable in Joy proper. For our purposes of constructing an artificial life system, however, we are looking for a minimal but useful subset of Joy.

Interdependence of Joy primitives

The small set of functions/combinators dup, pop, swap, cons, uncons, i, dip, cat, unit that we have encountered so far is enough to render Joy Turing-complete. It's actually more than enough because it turns out that a set of only two appropriately defined combinators will suffice. Take for instance the Ess-Kay (SK) system or some of the more exotic systems invented by Brent Kirby in his Theory of Concatenative Combinators. As such, it is not surprizing that many of these primitive combinators can be expressed in terms of some of the others:

cat  == [[i] dip i] cons cons
unit == [] cons
cons == [unit] dip cat
swap == unit dip
dip  == swap unit cat i
i    == [[]] dip dip pop

Could it also be possible to express ifte, true, and false in terms of these combinators?

`ifte` as a primitive

We have treated ifte as a primitive function so far. This means that it isn't a composite of other Joy functions. It is instead considered to be a given of the language, implemented in Elixir, the language in which we have implemented the Joy interpreter. Here is the implementation in Elixir:

def ifte(stack) do
  [else_quot, then_quot, if_quot | rest] = stack
  [result | _] = __execute(rest, if_quot)

  quot =
    if result !== false do
      then_quot
    else
      else_quot
    end

  __execute(rest, quot)
end

It expects three quotations on the stack. At the top it expects the quoted else-block, below it the quoted then-block and below that the quoted if-block (the predicate). After having popped these quotations from the stack, it executes the if-block against the remainder of the stack. It then pops the resulting (usually boolean) value from the stack, checks that it is not equal to false, in which case it executes the then-block against the stack as if the if-block was never executed. That is, before executing the then-block the stack is restored to the state in which is was prior to executing the if-block. If, on the other hand, the if-block leaves a false on the stack, the else-block is executed, also against a restored stack.

This implementation allows us to call ifte like this:

[if-block] [then-block] [else-block] ifte

For example (allowing integers and strings):

2 3 [<] ["the first value is smaller"] ["the second value is smaller"] ifte

Which would leave 2 3 "the first value is smaller" on the stack. There are two things to notice. All three of the quotations (if, then and else), when executed, only see 2 3 on the stack. In addition, if the if-block is executed and leaves anything other than false on the stack, the then-block will be executed.

`true` and `false` as primitives

Our Elixir implementation of Joy treats all functions that don't have explicit definitions as if they simply place themselves on the stack. This means that the boolean true and false, which are actually functions, would simply place themselves on the stack when executed. However, we could also explicitly implement true and false in Elixir like this:

def unquote(true)(stack) do
  [true | stack]
end

def unquote(false)(stack) do
  [false | stack]
end

The unquote macro is required, because true and false are something like reserved words in Elixir. In fact, true and false are not strictly speaking booleans, but rather atoms:

iex(1)> true == :true
true
iex(2)> false == :false
true

Their boolean semantics comes from the functions and macros (if, not, and, etc.) that act on them. This is also true for our Joy implementation. The fact that the true Joy function acts in the way that one would expect from the boolean true can be entirely ascribed to the implementation of the ifte function that acts on it.

This is good news because it means that we can make (compositions) of other Joy functions to assume the behaviour and meaning of booleans simply by how we implement ifte and other functions that act on booleans. Let's take a short detour to the land of Church encoding, before we attempt to eliminate ifte, true and false as Joy primitives.

Church encoding

Functions are the only primitive data types in untyped lambda calculus. It is nevertheless possible to represent numerals, booleans, lists, sets, characters and strings as higher order functions in untyped lambda calculus using Church encoding (named after Alonzo Church).

Similarly, everything in Joy is either a function or a quotation (list of functions). Some functions look like numerals, for instance the function 2 looks like the numeral 2, but it is still strictly speaking only a function. However, because of the Church-Turing thesis we can go one step further and eliminate even these literal-mimicking functions and replace them with compositions of a minimal base of primitive functions.

Church booleans are representations of the boolean true and false data types in terms of higher order functions (functions and quotations in Joy). Church booleans revolve around the concept of choice. Given a and b, selecting a represents truth, whereas selecting b represents falsity:

true == λa.λb.a
false == λa.λb.b

In case the lambda calculus notation is not all that clear, here are the same definitions as anonymous functions in Elixir:

true = fn a, b do a end
false = fn a, b do b end

Let's turn to Joy to help us understand these definitions a bit better.

`ifte`, `true`, and `false` as composites

The two definitions of true and false as seen above can be represented in Joy as follows:

A B true == A
A B false == B

That is, supposing that A is below B on the stack, then the function true effectively pops B off the stack. Whereas, for an identical stack, the function false would first swap A and B, then pop A off the stack. While these definitions agree with their counterparts in lambda calculus, they are still treated here as primitives. Let's see if we can change that.

We have already hinted at the solution.

true == [pop i]
false == [swap pop i]

In what way do these definitions confer the semantics of boolean data types on the true and false functions? There is nothing in these definitions that inherently make them boolean. Instead, the boolean semantics comes from how we define other functions such as ifte that act on true and false.

Suppose that then is a function that we would like to execute if a certain program pred evaluates to true and that else is a function that we would like to execute if pred evaluates to false. We could make use of the primitive ifte, which would expect [else] to be on top of the stack, with [then] just below it, and [pred] below that. ifte first executes [pred] which evaluates (hopefully) to a boolean. If false, [else] is executed, otherwise [then] is executed.

In other words, we'd like [true] [then] [else] ifte to evaluate to then and [false] [then] [else] ifte to else. But we are in search of a pure Joy implementation. Here is a first attempt:

ifte == dig2 i i

where dig2 == [] cons cons dip digs out the element that is two positions below the top of the stack and places it on top of the stack. Let's see how it pans out:

[true] [then] [else] ifte
[true] [then] [else] dig2 i i    (definition of ifte)
[then] [else] [true] i i         (dig2)
[then] [else] true i             (i)
[then] [else] [pop i] i          (definition of true)
[then] [else] pop i              (i)
[then] i                         (pop)
then                             (i)

Similarly, for when [pred] evaluates to false.

[false] [then] [else] ifte
[false] [then] [else] dig2 i i     (definition of ifte)
[then] [else] [false] i i          (dig2)
[then] [else] false i              (i)
[then] [else] [swap pop i] i       (definition of false)
[then] [else] swap pop i           (i)
[else] [then] pop i                (swap)
[else]                             (pop)
else                               (i)

However, this definition of ifte is only sufficient if pred doesn't have to perform operations on the stack. If pred needs to operate on the stack, it would need to dig below [then] [else] in order to get to the stack. While that is an option, we can get around this problem with a more robust definition of ifte:

ifte == unit cons unit cat i swap cat i

Let's see it in action (again permitting the numeral-like functions 2 and 3, and the comparison function <):

2 3 [<] [then] [else] ifte
2 3 [<] [then] [else] unit cons unit cat i swap cat i  (definition of ifte)
2 3 [<] [then] [[else]] cons unit cat i swap cat i     (unit)
2 3 [<] [[then] [else]] unit cat i swap cat i          (cons)
2 3 [<] [[[then] [else]]] cat i swap cat i             (unit)
2 3 [< [[then] [else]]] i swap cat i                   (cat)
2 3 < [[then] [else]] swap cat i                       (i)
true [[then] [else]] swap cat i                        (<)
[pop i] [[then] [else]] swap cat i                     (definition of true)
[[then] [else]] [pop i] cat i                          (swap)
[[then] [else] pop i] i                                (cat)
[then] [else] pop i                                    (i)
[then] i                                               (pop)
then                                                   (i)

The corresponding evaluation with > instead of < is left as an exercise to the reader. This definition of ifte essentially ensures that [pred] is evaluated against the stack that is below [then] [else] and assumes that the result is a quoted boolean. It then brings the boolean to the top of the stack and executes it, which in turn conditionally executes either the [then] or the [else] quotations. It only works as expected if [pred] evaluates to exactly true or false.

Finally, after executing [pred], the ifte primitive restored the stack to what it was before executing [pred]. This allows [then] and [else] to operate on the data that [pred] used to make a decision. Our composite definition of ifte doesn't have this property (yet -- see two sections down).

Boolean operators

We can now also define or, and, not and xor.

First we define the function branch. It is similar to ifte, but expects a boolean instead of a predicate:

true [then] [else] branch == then

false [then] [else] branch == else

branch is roughly the composition of dig2 and dip. We can define it as:

branch == unit cons swap cat i

branch turns out to be very useful in the definitions of the boolean operators or, and, not, and xor. First up, here is or.

or == [pop true] [] branch

We expect that the following holds:

true true or == true

true false or == true

false true or == true

false false or == false

Here are some worked examples.

false true or
false true [pop true] [] unit cons swap cat i  (definition of or and branch)
false true [pop true] [[]] cons swap cat i     (unit)
false true [[pop true] []] swap cat i          (cons)
false [[pop true] []] true cat i               (swap)
false [[pop true] []] [pop i] cat i            (definition of true)
false [[pop true] [] pop i] i                  (cat)
false [pop true] [] pop i                      (i)
false [pop true] i                             (pop)
true                                           (i pop true)

true false or
true false [pop true] [] branch
true false [pop true] [] unit cons swap cat i
true false [pop true] [[]] cons swap cat i
true false [[pop true] []] swap cat i
true [[pop true][]] false cat i
true [[pop true][]] [swap pop i] cat i
true [[pop true][] swap pop i] i
true [pop true][] swap pop i
true [][pop true] pop i
true [] i
true

The definition of and uses the same line of logic:

and == [] [pop false] branch

A worked example:

true true and
true true [] [pop false] branch
true true [] [pop false] unit cons swap cat i
true true [] [[pop false]] cons swap cat i
true true [[] [pop false]] swap cat i
true [[] [pop false]] true cat i
true [[] [pop false]] [pop i] cat i
true [[] [pop false] pop i] i
true [] [pop false] pop i
true [] i
true

The function not essentially replaces true with false and the other way around:

not == [false] [true] branch

Here are worked examples for the only two cases that we have to consider:

false not
false [false] [true] branch
false [false] [true] unit cons swap cat i
false [false] [[true]] cons swap cat i
false [[false] [true]] swap cat i
[[false] [true]] false cat i
[[false] [true]] [swap pop i] cat i
[[false] [true] swap pop i] i
[[true] [false] pop i] i
[true] [false] pop i
[true] i
true

true not
true [false] [true] branch
true [false] [true] unit cons swap cat i
true [[false] [true]] swap cat i
[[false] [true]] true cat i
[[false] [true]] [pop i] cat i
[[false] [true] pop i] i
[false] [true] pop i
[false] i
false

Finally, we can define xor in terms of not:

xor == [[false] [true] branch] [] branch

xor == [not] [] branch

And here are worked examples for all the possible cases:

true true xor
true true [not] [] branch
true true [not] [] unit cons swap cat i
true true [[not] []] swap cat i
true [[not] []] true cat i
true [[not] []] [pop i] cat i
true [[not] [] pop i] i
true [not] [] pop i
true [not] i
true not
false

false false xor
false false [not] [] branch
false false [not] [] unit cons swap cat i
false false [[not] []] swap cat i
false [[not] []] false cat i
false [[not] []] [swap pop i] cat i
false [[not] [] swap pop i] i
false [] [not] pop i
false [] i
false

true false xor
true false [not] [] branch
true false [not] [] unit cons swap cat i
true false [[not] []] swap cat i
true [[not] []] false  cat i
true [[not] []] [swap pop i]  cat i
true [[not] [] swap pop i] i
true [not] [] swap pop i
true [] i
true

false true xor
false true [not] [] branch
false true [not] [] unit cons swap cat i
false true [[not] []] swap cat i
false [[not] []] true cat i
false [[not] []] [pop i]  cat i
false [[not] [] pop i] i
false [not] [] pop i
false [not] i
false not
true

A composed `ifte` with identical semantics to the built-in Joy `ifte` combinator

So far, we've developed a composite implementation of ifte that comes close to the built-in ifte primitive of standard Joy:

ifte == unit cons unit cat i swap cat i

But in order to get semantics that are identical to the built-in Joy primitive, the stack should be restored after the predicate is evaluated to the state in which it was before the predicate was executed. This makes it possible the then and else clauses to potentially make use of data on the stack that would otherwise be consumed by the predicate.

A viable remedy looks like this:

ifte == unit cons [[stack] swap unit cat i infra uncons pop] swap unit cat i swap cat i

In this definition, stack is a function that puts the stack itself as a quotation on the top of the stack; and infra is a function that executes the quotation on top of the stack while treating another quotation below it as a temporary stack. Let's see how it works:

2 3 [<] [then] [else] ifte
2 3 [<] [then] [else] unit cons [[stack] swap unit cat i infra uncons pop] swap unit cat i swap cat i
2 3 [<] [then] [else] unit cons [[stack] dip infra uncons pop] dip swap cat i
2 3 [<] [[then] [else]] [[stack] dip infra uncons pop] dip swap cat i
2 3 [<] [stack] dip infra uncons pop [[then] [else]] swap cat i
2 3 stack [<] infra uncons pop [[then] [else]] swap cat i
2 3 [3 2] [<] infra uncons pop [[then] [else]] swap cat i
2 3 [true] uncons pop [[then] [else]] swap cat i
2 3 true [] pop [[then] [else]] swap cat i
2 3 true [[then] [else]] swap cat i
2 3 [pop i] [[then] [else]] swap cat i
2 3 [[then] [else]] [pop i] cat i
2 3 [[then] [else] pop i] i
2 3 [then] [else] pop i
2 3 [then] i
2 3 then
2 3 +         # treating `then` as the addition function
5

As before, for illustration purposes, we allow integers and arithmetic and predicates like <. In this case we see that, since 2 is smaller than 3, the then clause is executed, which we arbitrarily choose to be addition. Note that the predicate and the then clause operated on the same data. I.e. the 2 and 3 were available to both.

While this definitions works, I find the following one more elegant in that the two functions that have to be introduced are inverses of one another:

ifte == unit cons [[stack] dip dip] dip dig2 cat [unstack] dip i

Here unstack replaces the current stack with the quotation that is on top of it. This means that stack followed by unstack is the identity function: stack unstack == id. Let's see how it works:

2 3 [<] [then] [else] ifte
2 3 [<] [then] [else] unit cons [[stack] dip dip] dip dig2 cat [unstack] dip i
2 3 [<] [[then] [[else]] cons [[stack] dip dip] dip dig2 cat [unstack] dip i
2 3 [<] [[then] [else]] [[stack] dip dip] dip dig2 cat [unstack] dip i
2 3 [<] [stack] dip dip [[then] [else]] dig2 cat [unstack] dip i
2 3 stack [<] dip [[then] [else]] dig2 cat [unstack] dip i
2 3 stack [<] dip [[then] [else]] dig2 cat [unstack] dip i
2 3 [3 2] [<] dip [[then] [else]] dig2 cat [unstack] dip i
2 3 true [3 2] [[then] [else]] dig2 cat [unstack] dip i
2 3 [3 2] [[then] [else]] true cat [unstack] dip i
2 3 [3 2] [[then] [else]] [pop i] cat [unstack] dip i
2 3 [3 2] [[then] [else] pop i] [unstack] dip i  
2 3 [[then] [else] pop i] i
2 3 [then] [else] pop i
2 3 [then] i
2 3 then
2 3 +
5

So what's the big deal? We were able to drop ifte, true, and false, but had to introduce stack and unstack. That is not a big win in terms of the number of functions we have to deal with, but it does free us from a pre-imposed notion of what conditional program flow should look like. While the compositional form of ifte that we've developed here helps us to reason about and write programs, our artificial cell is not required in any way to make use of this exact compositional definition of ifte. There are multiple ways in which the same semantics can be achieved, some even without stack and unstack. The important bit is that we equip our system with a strong enough base to evolve on.

Suddenly there is also no real reason to require the strict predicate-then-else ordering. A protein in our artificial life system could contain these components at different locations
and still end up with the same overall outcome. For instance, a program that looks like this:

2 3 stack [<] dip [[then] [else]] dig2 cat [unstack] dip i

is equivalent to one that looks like this:

2 3 [<] [then] [else] unit cons [[stack] dip dip] dip dig2 cat [unstack] dip i

with less "dipping" and could be employed by a cell to the same effect. Ultimately, this is a matter of personal preference, and sticking to the built-in primitive ifte would not have prevented us from reaching our goal.

Conclusion

By defining ifte, true and false in some of the more low-level Joy primitives, we have eliminated the need to treat them as amino acids in our artificial life system. Doing so is mostly a matter of personal preference. The goal is not to minimize the number of required amino acids to the bare minimum, but rather to arrive at a pleasing middle ground.

One aspect that we have neglected in this post is the requirement of a predicate function that will actually yield [pop i] for true and [swap pop i] for false. In our example we used the primitive <, which isn't actually part of our artificial life system. While it is trivial to come up with a function (or function composition) that will yield either one of these booleans, such a function would still have to know when to yield the one or the other in some meaningful way that is arbitrary yet deterministic.

Knowing that 2 is less than 3 was built into the definition of <, which is therefore primitive. Therefore, in order to use ifte, or rather unit cons unit cat i swap cat i in a way that makes it mean what the primitive ifte meant, we still need a predicate function of sorts. The predicate that we have relied on in our protein programs up to know has been equal, a function that checks if the two top elements of the stack are equal. We'll see how we can replace that with something more fuzzy. Life loves fuzzy.

Programs as proteins - an artificial genetic code

Danie Palm — Sun, 13 Sep 2020 12:44:24 +0000

In the previous two posts of this series, we've developed two Joy programs. The first of these acts as a ribosome and is capable of translating any mRNA sequence into a corresponding polypeptide sequence. The second program acts as a chaperone that helps the polypeptide sequence to fold into its final and functional conformation. However, the situation is somewhat confusing, because the ribosome makes use of the real genetic code. And while it would be possible to consider the output as a valid Joy program, the functions of this program would correspond to real amino acids and therefore would not have any meaning in Joy.

In this post, we define an artificial genetic code so that the output of the ribosome composed with the chaperone would produce quoted Joy programs made up of conventional Joy functions. This will allow the ribosome (with the help of the chaperone) to produce quoted versions of itself and of the chaperone.

Biology

Code biology is a research field that is centred around the notion that so called organic codes are ubiquitous in biology and in fact underpin a new mechanism of evolution: adaptation by natural convention.

An organic code is a mapping by which a biological sign (usually in the form a a molecule or molecular sequence) is made to correspond to a biological meaning (either as a molecule or a molecular effect) in a fixed yet arbitrary way.

Much of code biology is based on the work of Marcello Barbieri, who proposed the following criteria by which organic codes can be identified:

The code must join two otherwise independent "worlds"
The code must be realized by an adapter that brings these worlds together
The code must be arbitrary as demonstrated by the ability to modify it experimentally

The genetic code was the first to be recognized as an organic code. It joins the otherwise independent worlds of RNA and polypeptides. Aminoacyl-tRNA molecules function as the adapters that realize the code. Genetic engineering of aminoacyl-tRNA synthetases allows for introducing changes to the standard genetic code. The genetic code therefore satisfies all three criteria.

Here is also an example of a mapping that does not satisfy these criteria. DNA is transcribed to mRNA during the process of translation. DNA and mRNA are both nucleic acids and do not as such necessarily represent independent worlds, but even if we give them the benefit of the doubt in this regard, there is no adapter molecule that maps DNA bases to RNA bases. And finally the mapping depends on the chemically deterministic pairing of pyrimidines to purines and cannot be altered experimentally without changing the laws of chemistry. The process of translation, while catalysed by enzymes, is therefore not governed by an organic code, but rather by the chemistry of nucleic acids.

Many other organic codes have been identified or proposed since the discovery of the genetic code. These include the histone code, epigenetic codes, metabolic codes, sugar codes, and many others. It is important to remember that, since these codes are arbitrary, the rules of the code must be contained and maintained inside the cell and ultimately in the genome. That is, the genetic code itself (and any other organic codes) is encoded in the genomes of organisms, allowing different species to use slightly different codes.

As a refresher, the genetic code maps codons (mRNA subsequences that are three bases long) onto amino acids (the building blocks of polypeptides/proteins). Since each of the three bases in a codon can have one of 4 values (A, C, G, U), there are 64 possible codons. There are however only 20 amino acids and as such the genetic code is a degenerative code - multiple codons map onto the same amino acid.

In the artificial life system that we are developing, the role of amino acids and nitrogen bases alike are played by Joy functions. An artificial genetic code in our system would therefore map functions that act as nitrogen bases onto functions that act as amino acids. The code will be realized by the ribosome (that for the time being also plays the role of aminoacyl-tRNA). Our code will not yet be modifiable because it is implemented in the primitive function translate. Future posts will address these shortcomings.

Code

The following is a list of all the Joy functions that we have required in order to program our artificial ribosome and chaperone. We may need a few additions later on and, because there is some redundancy, could even omit a few.

bra
ket
dup
pop (or zap)
swap
dip
i
cons
unit
cat
equal
ifte
a
c
g
u
translate

Technically we never made use of c and while a, u, and g were present in the ribosome implementation, they only occurred in quoted form and were never executed. Nevertheless, since they were present at all, we are forced to treat them as "amino acids", despite the fact that semantically they are nucleic acids. We include c for the sake of symmetry.

We also regrettably include translate, which embodies the actual mapping. We are treating translate as a primitive function. That is, the implementation is considered to be opaque. I have mentioned before that this amounts to cheating, but we permit it for now, because it is in fact easy, though tedious, to represent translate in terms of the other functions that are already on the list. However, the real reason for keeping translate around is that we will get rid of it in a more comprehensive way later that mimics biology more closely.

We now have a list of 17 functions that we will treat as amino acids. This means that the minimum number of nucleic acid bases in a codon needs to be 3, as is also the case in the real genetic code. We could trivially reduce the number of amino acids to below 17, which would allow us to make use of 2-base codons (as in the typogenetics system discussed in a previous post). We stick to a 3-bases code, however, because the redundancy of the genetic code is a key mechanism by which it absorbs mutation and allow for drift without necessarily altering function.

Here then is an artificial genetic code:

Base 1	Base 2	Base 3	Amino acid
a	a	a	a
a	a	c	i
a	a	g	dip
a	a	u	u
a	c	a	dip
a	c	c	dip
a	c	g	dip
a	c	u	pop
a	g	a	bra
a	g	c	ket
a	g	g	bra
a	g	u	ket
a	u	a	ifte
a	u	c	ifte
a	u	g	ifte
a	u	u	equal
c	a	a	dup
c	a	c	dup
c	a	g	dup
c	a	u	pop
c	c	a	dip
c	c	c	c
c	c	g	g
c	c	u	i
c	g	a	cons
c	g	c	cons
c	g	g	cons
c	g	u	cons
c	u	a	equal
c	u	c	equal
c	u	g	equal
c	u	u	ifte
g	a	a	pop
g	a	c	pop
g	a	g	pop
g	a	u	swap
g	c	a	i
g	c	c	i
g	c	g	i
g	c	u	dip
g	g	a	unit
g	g	c	c
g	g	g	g
g	g	u	unit
g	u	a	translate
g	u	c	translate
g	u	g	bra
g	u	u	ket
u	a	a	swap
u	a	c	swap
u	a	g	swap
u	a	u	dip
u	c	a	cons
u	c	c	cons
u	c	g	cons
u	c	u	cons
u	g	a	cat
u	g	c	cat
u	g	g	cat
u	g	u	cat
u	u	a	a
u	u	c	{stop}
u	u	g	{stop}
u	u	u	u

It is completely arbitrary, otherwise it wouldn't be a code, but I did build in some themes. aaa, for instance, maps onto a and ccc map onto c, etc. Furthermore, amino acids with similar functions were grouped together so that mutations generally convert amino acids into other amino acids with similar functions. The broad functions that I've considered are the following:

stack manipulation
unquoting / interpreting
quotation / list manipulation
conditionals
structural
misc
RNA
translation
stop codon

Let us consider the example Joy program (protein) from the previous post:

[[[] swap dup] i]

It's primary structure is:

[ bra bra ket swap dup ket i]

We can now finally map the primary amino acid sequence back to mRNA. One possibility could be:

[ a g a a g a a g c g a u c a a a g c a a c]

We are also in a position to derive the mRNA sequences for both our ribosome and chaperone implementation. However, these sequences are too long to be useful here.

Let us instead reflect on the role of context in cells. The genetic code is realized by the aminoacyl-tRNA synthetases that are present in cells. However, these very aminoacyl-tRNA synthetases can only be active when folded up into a functional tertiary structure. Successful protein folding on the other hand rely on cellular conditions that are conducive to proper folding and on chaperones. These conditions or intracellular milieu is in turn maintained by active transporters. And so we see that there is a circular dependency of cellular agents, being represented in the genome, relying on one another. How does one bootstrap such a system?

Protolife forms perhaps relied much more on the environment and on the laws of chemistry and were at the mercy of fluctuations in these conditions. In time, life forms internalized the maintenance of the conditions under which they thrive and so started to actively fabricate not only themselves, but the conditions that they require to survive. As soon as they could take these new conditions for granted, they could build on them and develop extraordinary degrees complexity by means of adaptation by natural convention: multiple layers of organic codes on top of the genetic code.

Programs as proteins - a chaperone programmed in Joy

Danie Palm — Sat, 27 Jun 2020 12:12:30 +0000

Predicting the tertiary structure and function of a protein, given only the primary amino acid sequence, is one of the big open questions in biology. Some proteins fold entirely on their own, but most multi-domain proteins rely on so called chaperones, proteins that assist other proteins to fold.

In this post we develop a scheme by which non-functional flat Joy programs (enzymes in our artificial life system) can be converted into functional structured Joy programs with the help of chaperone programs. Such a scheme is required to turn Joy programs produced by the process of translation into fully fledged artificial enzymes.

Biology

Anfinsen's dogma states, broadly speaking, that the tertiary structure of a protein in a physiological cellular context is determined completely by its primary structure (its amino acid sequence). Deducing a protein's tertiary structure from its primary structure is, however, one of the big open questions of molecular biology, and has given rise to Levinthal's paradox, which roughly states that even for simple proteins the universe isn't old enough to allow for the sequential traversal of conformational space in order to reach the lowest energy conformation.

Of course, in cells, proteins fold in microsecond to millisecond time scales. Clearly the physiological context within which proteins fold significantly reduce the search space.

Most multidomain proteins actually rely on other proteins, called chaperones to help them fold. Some chaperones do speed up the folding process, but mostly they prevent aggregation of partially folded proteins. As such, these chaperones don't violate Anfinsen's dogma because they don't lower the final free energy state of the folded protein.

However, the native structure of some proteins is less stable than their unfolded structures, requiring chaperones to guide them into their functional conformation. In these cases Anfinsen's dogma is in fact violated.

Anfinsen's dogma perhaps overemphasizes the role of the protein primary structure. While the primary structure is undoubtedly of paramount significance, the intracellular context or intracellular milieu, which includes factors such as the pH, ionic strength, and chaperones, is an indispensible contributor to the functional folding of proteins.

It is also of significance to note that the intracellular milieu is actively maintained by the cell itself using active cross-membrane transport and strict regulation of the expression of chaperones.

In some sense therefore, the intracellular milieu can itself be regarded as an "enzyme" that catalyses the transformation of polypeptide primary structures into polypeptide tertiary structures. And this "enzyme" is itself the product of translation and protein folding. The role of the intracellular milieu is unpacked in more detail in the article Basic biological anticipation by Jannie Hofmeyr.

Code

In the previous post we have developed the first iteration of a ribosome, programmed in a subset of Joy, that is able to convert an mRNA strand (a flat list of RNA bases) to one or more polypeptides (flat lists of amino acids).

One of our ultimate goals is to produce polypeptides that are made up of artificial amino acids in the form Joy functions so that they can operate as artifical enzymes in the form of Joy programs. Most useful Joy programs are however highly structured compared to the flat programs produced by our ribosome.

Here we devise a scheme by which such unstructured Joy programs can be converted into their fully functional structured counterparts by means of a chaperone Joy program.

It turns out that a crucial part of the work has already been done by Joy language enthusiasts (see Floy - a flat concatenative subset of Joy). The Joy language community posed the question as to whether it would be possible to create a subset of Joy, called Floy, that only allows for functions and empty or single-element lists and no nesting of lists.

It was subsequently shown that any Joy program P can be converted by a flattening program j2f into its flat counterpart Floy program F such that:

[J] j2f == [F]

Evaluating [F] results in [J], which needs to be evaluated a second time should one want to execute the original program J:

[F] i == [J]
[F] i i == J

There is more than one way to implement j2f, but without going into the details, we will be using the "forwards" variant from the article linked above. It can be defined like this:

[j2f-f]
[
    [ list ] 
    [ [[[]] cat] dip [j2f-f] step [[] cons cat] cat ] 
    [ [] cons [cat] cons cat ] 
    ifte
]
define

[j2f]
[
    [[]] swap [j2f-f] step
]
define

(Remember that this define function is my own creation and not part of standard Joy.)

Given a program P defined as

[1 2 3] [dup *] map

the output of [P] j2f is [F] or:

[[] [] [1] cat [2] cat [3] cat [] cons cat [] [dup] cat [*] cat [] cons cat [map] cat]

With the appropriate amount of eye strain it can be seen that there is a mapping between the symbols in [P] (left) and the symbols in [F] (right):

[        -> []
]        -> [] cons cat
function -> [function] cat

where function is any of the Joy functions/combinators, including numbers and other data types. The only symbol present in [F] that is not represented in [P] is an initial []. We will address this discrepancy is due time.

F is flat in the sense that it contains no nested quotations and all quotations are either empty or only contain single elements. Despite being flat, F still contains symbols, all the [s and ]s, that cannot be produced as individual elements of the polypeptide sequence produced by the ribosome developed in the previous post. I.e. there are no codons that map to either [ or ]. And it is in fact not possible to devise such codons.

What we really need is a mapping, similar to the one above, but in which all the symbols on the left hand side are functions. Here is a mapping that will do:

bra      -> []
ket      -> [] cons cat
function -> [function] cat

Where bra and ket are identity functions or functions with any inconsequential effects. If we can now devise a chaperone Joy program that takes a list of Joy functions (artificial amino acids) and map each one according to the mapping above, then we have a scheme by which we can turn completely flat (no lists at all) Joy programs into kind of flat Joys programs (ones like F that only contain empty or unit lists), which when executed yield fully structured Joy programs:

      ribosome                        chaperone
mRNA ---------> unfolded polypeptide ----------> folded polypeptide

Or in Joy:

[mrna] ribosome chaperone == folded_protein

As a first step, here is a chaperone programmed in Elixir. Note that I'm deliberately refraining from using idiomatic Elixir and high-level functions like Enum.map and Enum.reduce to facilitate easier translation to Joy.

def chaperone_worker(protein \\ [], polypeptide) do
    if Enum.empty?(polypeptide) do
        protein
    else
        [head | rest] = polypeptide

        protein =
            if head == :bra do
                protein ++ [[]]
            else
                if head == :ket do
                    protein ++ [[], :cons, :cat]
                else
                    protein ++ [[head], :cat]
                end
            end

        chaperone_worker(protein, rest)
    end
end

The chaperone_worker function above covers the core mapping, but does not include the initial extra [] that needs to be inserted and also does not unquote or execute its results so as to yield a final quoted "protein". We will use a wrapper function to accomplish these final touches, but here is the corresponding Joy chaperone-worker:

[chaperone-worker]
[
    # We expect the stack to look like this from bottom to top:
    # protein polypeptide [q]

    [swap empty]              # if the polypeptide is empty
    []                        # do nothing
    [
        swap                  # dig out polypeptide
        dup [rest] dip first  # split into rest and first

        [bra equal]           # if head equals bra
        [                     # then
            pop               # get rid of bra (!)
            [[]]              # put mapped value on the stack

        ]
        [                     # else
            [ket equal]       # if head equals ket
            [                 # then
                pop           # get rid of ket
                [[] cons cat] # put mapped value on the stack
            ]
            [                 # else
                unit          # wrap function in quotes
                [cat] cons    # cons it into a list containing cat
            ] ifte
        ] ifte

        dig3        # dig out protein
        swap        # dig out mapped value
        cat         # append mapped value to protein
        bury2       # bury protein below rest of polypeptide and [q]
        swap        # bury polypeptide below [q]
        i           # recurse
    ]
]
define

And here is the full chaperone definition:

[chaperone]
[
    [] swap               # start with an empty protein
    [chaperone-worker] y  # convert worker to recursive function
    pop                   # remove the empty polypeptide
    [] swap cons          # introduce initial [] into protein
    i                     # unquote to fully structured protein        
]
define

As in the previous post, we don't want intermediate functions and chunked definitions like buryn and dign and will replace all definitions recursively until they are irreducible. But there is nothing to be gained from doing that now.

Let's rather look at an example. Suppose the following program is the output of a ribosome:

[bra bra ket swap dup ket i]

The ribosome function produced this from an input mRNA sequence according to an artificial genetic code that we haven't defined yet. The chaperone function now converts this to an intermediate form (a Floy program):

[[] [] [] [] cons cat [swap] cat [dup] cat [] cons cat [i] cat]

And then, right before releasing it, it converts it to its final form (a Joy program again) by unquoting it with i:

[[] [] [] [] cons cat [swap] cat [dup] cat [] cons cat [i] cat] i
 [] [] [] [] cons cat [swap] cat [dup] cat [] cons cat [i] cat  # by i
 [] [] [[]]       cat [swap] cat [dup] cat [] cons cat [i] cat  # by cons
 []    [[]]           [swap] cat [dup] cat [] cons cat [i] cat  # by cat
 []    [[] swap]                 [dup] cat [] cons cat [i] cat  # by cat
 []    [[] swap dup]                       [] cons cat [i] cat  # by cat
 []   [[[] swap dup]]                              cat [i] cat  # by cons
      [[[] swap dup]]                                  [i] cat  # by cat
      [[[] swap dup] i]                                         # by cat

We now have a quoted protein

[[[] swap dup] i]

which may as well have been a quoted ribosome or chaperone, had we provided the appropriate input. It is tempting to draw parallels between the primary, secondary, and tertiary structure of proteins and the three stages of Joy programs we see here. The primary structure corresponds to:

[bra bra ket swap dup ket i]

The secondary structure corresponds to the intermediate step, which is never directly observed:

[[] [] [] [] cons cat [swap] cat [dup] cat [] cons cat [i] cat]

And finally the tertiary structure corresponds to:

[[[] swap dup] i]

There is clearly a strong link between the primary and tertiary forms:

[ bra bra ket swap dup ket i]
[ [   [   ]   swap dup ]   i]

which highlights the role of the primary structure in determining the tertiary structure, but this fidelity is at the mercy of the chaperone, which we have devised here to honour the mapping. The chaperone is however free to evolve (at least it will be) and could therefore conceivably deviate from this strict mapping.

Just as the intracellular milieu, of which chaperones could be considered to form a part, actively participates in protein folding in real cells, we have here devised a scheme by which a programmatic chaperone facilitates the construction of higher-order Joy functions from flat primary templates.

In coming posts, we will define an artificial genetic code and update the previously developed ribosome to make use of this code. This will then allow us to produce quoted ribosomes and chaperones from appropriately crafted mRNA templates:

[ribosomal-mrna] ribosome chaperone == [ribosome]
[chaperone-mrna] ribosome chaperone == [chaperone]

Programs as proteins - a ribosome programmed in Joy

Danie Palm — Sat, 20 Jun 2020 21:12:44 +0000

Ribosomes are enzymes that are part protein and part RNA. They play a central role in the translation of messenger RNA to proteins according to the genetic code. And yet all the protein subunits of ribosomes are themselves the products of messenger RNA that was translated according to the genetic code by... a ribosome. Ultimately, the messenger RNA that codes for the protein subunits and the ribosomal RNA that directly contributes to the translation function of the ribosome are both the products of DNA transcription, so that the ribosome, like other enzymes, are fully represented in the genome. Without the ribosome there would be no interpreter of the genetic code and no point in having any genes. The ribosome is therefore the most suitable starting place for our Joy-based artificial life system.

We have previously touched on the Y combinator, a function that is able to produce a fixed point of other functions (or function compositions, such as entire Joy programs). In this post we will finally put the Y combinator and its anonymous recursion to good use when we loop through the catalytic steps of the ribosome.

Biology

Ribosomes are roughly half rRNA and half protein. The rRNA component is made up of 4 rRNA strands and the protein component comprises about 80 proteins. The exact composition differs between bacteria, archaea, and eukaryotes, but the overall function and structure is largely comparable: all ribosomes are made up of a small and a large subunit, both of which is a mix of rRNA and proteins.

The process of translation begins when the small ribosomal subunit binds to mRNA, either at the start (the 5'-end) or just prior to the start codon (AUG). It then scans towards the 3'-end until it reaches the start codon, at which point the large ribosomal subunit is also recruited to form the full ribosome.

Once the ribosomal complex is fully initiated, an amino acid-charged tRNA that is complementary to the start codon of the mRNA strand binds to a position called site A. Right after binding, the ribosome moves one codon to the right, so that the amino acid-charged tRNA is now located at a position known as site P. The next codon of the mRNA is now located at site A and once again a complementary charged tRNA binds to it. The amino acid at site P is now transfered to the amino acid at site A, and then the ribosome once again moves one codon to the right. Site P is now bound to a tRNA molecule that is charged with a peptide chain of two amino acids. This process continues until a stop codon is reached and on each iteration the peptide chain at site P grows by one amino acid, building up a protein of which the amino acid sequence is dictated by the mRNA strand being translated.

It is somewhat interesting to note that the protein subunits of the ribosome are not actively involved at the translation sites, but rather seem to support the rRNA that catalyses the elongation reaction. This could perhaps be an indication that primitive ribosomes were entirely made up of rRNA.

Code

Let's dive right in and take a look at the high-level logic that we want from a ribosome in the form of an Elixir function. The function takes a polypeptide (protein) list as the first argument and an mRNA list as the second. The first invocation should be with an empty polypeptide and an mRNA list of any length. It calls some undefined functions of which the names are hopefully self-explanatory.

def ribosome_worker(polypeptide, mrna) do
    if Enum.count(mrna) >= 3 do
        if polypeptide == [] do
            {codon, mrna} = Enum.split(mrna, 3)

            if codon == [:a, :u, :g] do
                # Initiate translation
                amino_acid = translate(codon)
                polypeptide = polypeptide ++ amino_acid

                ribosome_worker(polypeptide, mrna)
            else
                # Continue searching for start codon (AUG)
                [_first_base | last_two_bases] = codon
                mrna = last_two_bases ++ mrna

                ribosome_worker(polypeptide, mrna)
            end
        else
            # Elongate previously initiated polypeptide
            {codon, mrna} = Enum.split(mrna, 3)
            amino_acid = translate(codon)

            if amino_acid == [] do
                # the proper Elixir counterpart of what we're doing here
                # detracts from the argument, so we move along instead
                stash_current_polypeptide_somewhere_and_start_a_new_one()
            else
                polypeptide = polypeptide ++ amino_acid
            end

            ribosome_worker(polypeptide, mrna)
        end
    else
        polypeptide
    end 
end

In short, we want to scan over a messenger RNA (mRNA) strand (a list of atoms :a, :c, :g or :u) for as long as it is longer than or equal to 3 bases. As soon as the sublist [:a, :u, :g] is reached, protein synthesis is initiated. This initiation involves translating the AUG codon to its corresponding amino acid (methionine in this case), which forms the first amino acid of the polypeptide (protein) chain. After initiation we recurse. This time however, the polypeptide is not empty and so we don't search for the initiating AUG codon, but instead translate the next codon and attach the corresponding amino acid to the end of the growing polypeptide. Unless the codon corresponds to a stop codon, returning an empty amino acid, in which case the existing polypeptide chain is stashed (code for this is not shown) and a new chain is started. In either case, we once a again recurse, so that we either elongate the polypeptide or search for a new start codon. This process continues until the mRNA strand has less than 3 bases left, in which case it can contain no more codons so that the translation process is terminated.

The sequence as described above does not correspond exactly to the real process of translation of which there are many variations. For instance, when a ribosome encounters a stop codon, it detaches from the mRNA strand instead of continuing to search for the next occurence of AUG.

The problem we now face, is to turn the above pseudocode into Joy. Some of the challenges we encounter in this process are:

Joy, even without the restrictions we place on it, does not have the notion of variables
the ribosome_worker function is recursive, but since it is not one of our primitives (like dup, swap, etc.) there is no direct way to make a recursive call in the Joy version
we are using a minimal subset of Joy in which we don't have numbers
the pseudocode is in a mixture of Polish and infix notation, but Joy exclusively makes use of the reverse Polish notation

Joy doesn't have variables. Functions can only manipulate or act on values on the stack. Most Joy primitives only operate on the topmost one or two stack values. Before executing a function, it is therefore usually necessary to first manipulate the stack to make sure that the values expected by the function are located at the correct stack positions. Similarly, it may be necessary to do some stack cleanup after a function has been executed. In other words, it is sometimes necessary to dig out values from deep in the stack and place them on top, and other times it is necessary to bury values from the top of the stack deep underneath some others. Let's look at a family of such dig and bury functions.

We are already familiar with a function that will bury the top element (and simultaneously dig out the second element) - swap. But it is possible to bury the top element n positions deep with:

bury1 == [[] cons] dip swap i
bury2 == [[] cons cons] dip swap i
bury3 == [[] cons cons cons] dip swap i

in which cons is repeated n times.

For example:

[A] [B] [C] bury2 == [C] [A] [B]

Here is how it works:

[A] [B] [C] bury2
[A] [B] [C] [[] cons cons] dip swap i     (definition)
[A] [B] [] cons cons [C] swap i           (dip)
[A] [[B]] cons [C] swap i                 (cons)
[[A] [B]] [C] swap i                      (cons)
[C] [[A] [B]] i                           (swap)
[C] [A] [B]                               (i)

We cons up two items into a single list. Then we swap the list with the top element and unpack the consed up list again. Similary, we can dig out n elements with:

dig1 == [] cons dip
dig2 == [] cons cons dip
dig3 == [] cons cons cons dip

Note that dig1 and bury1 are both equivalent to swap. See The Theory of Concatenative Combinators for a more detailed treatment. We will not be using dign or buryn directly because we generally want to employ as few as possible amino acids. Instead, we will be writing out the bury and dig family of functions in full whenever they are needed.

Let's put this to the test. Suppose we have a function that takes 3 parameters: a number n and two strings even_string and odd_string. The function must print the value of even_string if n is even and the value of odd_string otherwise. In Elixir, it could look like this:

def odd_or_even(n, even_string, odd_string) do
  if rem(n, 2) == 0 do
    IO.puts(even_string)
  else
    IO.puts(odd_string)
  end
end

A corresponding Joy function, allowing the use of numbers and strings, could look like this:

[odd_or_even]
[
    [
        # check if the remainder of n divided by 2 is 0
    ]
    [
        # print odd string
    ]
    [
        # print even string
    ]
    ifte
]
define

Remember that ifte is the Joy counterpart of an if-then-else block. Now, the remainder check could look like:

2 rem 0 equal

This assumes that the value representing n is at the top of the stack. However, if the function is to be called like 4 "I am odd" "I am even" odd_or_even, then n is two places below the top and needs to be dug up first.

Similarly, for the case in which we want to print the value of even_string, we can't just write puts (the Joy built-in that writes to the standard output), because that would expect even_string to be at the top of the stack. Instead we have to dig once (or swap) to get it. Lastly, in order to print the value of odd_string, we can simply use puts because odd_string is indeed at the top. Here is the full Joy version:

[odd_or_even]
[
    [
        dig2          # dig up n
        2 rem 0 equal # check if n is even
    ]
    [
        swap puts     # print even_string if n is even
    ]
    [
        puts          # print odd_string otherwise
    ]
    ifte
]
define

Now that we know how to manipulate the stack, it is time to tackle recursion. Consider the following recursive function (assuming only non-negative values of n):

def sum(total, n) do
    if n == 0 do
        IO.puts(total)
    else
        sum(total + n, n - 1)
    end
end

Calling sum(0, 3) should print out the number 6. Here is the corresponding Joy version, with all the necessary digging and burying:

[sum]
[
    [0 equal] # n is at the top, so no digging
    [
        swap  # dig out total, which is below n
        puts  # ... and print it
    ]
    [
        dup   # duplicate n, which is at the top
        dig2  # dig out total which is now buried under two n's
        +     # sum total and the n below it
        swap  # so that the new total is under the n that remains from the earlier dup
        1 -   # subtract 1 from the n on top
        sum   # recurse
    ]
    ifte
]
define

The else-block that makes the recursive call is particularly involved, because it needs to first manipulate the stack so that it is ready for the first calculation total = total + n and then to prepare for the secod calculation n = n - 1. And finally it has to place total and n on the stack in the order that is expected by the sum function in preparation for the recursive call.

While the function above works, we are interested in a version of it that uses anonymous recursion. That is, instead of directly calling sum recursively, we need to execute something that is equivalent but unnamed. In a previous post, we have established the following effect of the Y combinator:

[p] y == [q] p

where [q] (short for [[dup cons p] dup cons p]), when executed, again yields [q] p. This means that if the program p decides to execute q by for instance invoking i when [q] is on top of the stack, then the result is that [q] is once again placed on top of the stack and p is once again executed, having again the option to unquote [q] whenever its logic requires it to do so. In this way p can effectively call itself anonymously.

We can now modify the definition of sum to make use of the Y combinator as follows:

[sum]
[
    [
        [dig1 0 equal] # [q] is now above n, so we have to dig n out
        [
            dig2       # dig out total, which is below n and [q]
            puts       # ... and print it
        ]
        [
            dig1 dup   # dig out and duplicate n
            dig3       # dig out total which is now buried under two n's and [q]
            +          # sum total and the n below it
            bury2      # bury the new total under [q]
            1 -        # subtract 1 from the n that is now on top
            bury1      # bury n under [q]
            i          # recurse: execute [q] which is on top
        ]
        ifte
    ] y
]
define

We have now directly or indirectly addressed all the challenges we faced in translating pseudcode to restricted Joy. Perhaps a final note on the absence of numbers is warranted. While we won't support numbers (there are too many of them and we aim to use as few symbols as possible), there is no limitation on performing certain operations a number of times. For instance, the predicate Enum.count(mrna) >= 3, can be calculated without using numbers:

not Enum.empty?(mrna) and not Enum.empty?(tl(mrna)) and not Enum.empty?(tl(tl(mrna)))

which is readily converted to Joy.

Without further ado, here is our ribosome, first with high-level functions like buryn and dign and itermediate definitions, and then in austere form using only primitives.

High-level ribosome:

[ribosome]
[
    [] swap
    [ribosome-worker]
    y
]
define

[ribosome-worker]
[
    # check if the mrna list contains at least 3 items
    [swap empty] [ ] [[swap rest empty] [ ] [[swap rest rest empty] [ ] [
        [dig2 empty]            # if polypeptide is empty
        [                       # then initiate
            swap split3 swap    # dig up mrna and split at 3

            [[a u g] equal]     # if codon equals [a u g]
            [                   # then
                translate       # translate codon to amino acid
                dig3            # dig out polypeptide
                swap cat        # dig out amino acid and concatenate to polypeptide
                bury2           # bury polypeptide
                swap            # bury mrna below [q]
                i               # recurse
            ]
            [                   # else
                rest            # drop the first element of the codon
                swap cat        # prepend the rest to mrna 
                swap            # bury mrna below [q]
                i               # recurse
            ]
            ifte
        ]
        [                       # else elongate
            swap split3 swap    # dig up mrna and split at 3
            translate           # translate codon to amino acid

            [empty]             # if amino acid is empty
            [                   # then
                bury2           # bury it as a new polypeptide
            ]
            [                   # else
                dig3            # dig out polypeptide
                swap cat        # dig out amino acid and concatenate to polypeptide
                bury2           # bury polypeptide
            ]
            ifte

            swap                # bury mrna below [q]
            i                   # recurse
        ]
        ifte
    ] ifte] ifte] ifte
]
define

[split3]
[
    [] swap
    dup [first unit cat] dip rest
    dup [first unit cat] dip rest
    dup [first unit cat] dip rest
]
define

The split3 function is the counterpart of the Elixir function Enum.split(mrna, 3). Its first effect is to bury an empty list underneath the mRNA, which it expects to be on top of the stack. It then duplicates the mRNA and concatenates the head of the first copy to the list underneath it on the stack, and then it drops the head of the second copy. This duplication process is repeated 3 times to correspond to the 3 in split3.

Austere, but verbose ribosome:

[ribosome]
[
    [] swap
    [
        [swap empty] [ ] [[swap rest empty] [ ] [[swap rest rest empty] [ ] [
            [[] cons cons dip empty]
            [
                swap
                [] swap
                dup [first unit cat] dip rest
                dup [first unit cat] dip rest
                dup [first unit cat] dip rest
                swap

                [[a u g] equal]
                [
                    translate
                    [] cons cons cons dip
                    swap cat
                    [[] cons cons] dip swap i
                    swap
                    i
                ]
                [
                    rest
                    swap cat
                    swap
                    i
                ]
                ifte
            ]
            [
                swap
                dup [first unit] dip rest
                dup [first unit cat] dip rest
                dup [first unit cat] dip rest
                swap
                translate

                [empty]
                [
                    [[] cons cons] dip swap i
                ]
                [
                    [] cons cons cons dip
                    swap cat
                    [[] cons cons] dip swap i
                ]
                ifte

                swap
                i
            ]
            ifte
        ] ifte] ifte] ifte
    ]
    [dup cons] swap cat dup cons i pop pop
]
define

We've sneaked in a few things not present in the initial Elixir code, but only so that we don't have to provide the initial empty polypeptide to the function. I.e. we can call ribosome with just an mRNA sequence:

[c a u g a a c a u u g a a a u g u g a a a a a u g a a a c] ribosome

The output of the above program are two lists of amino acids (a stop codon in the mix triggered the start of a new polypeptide):

[met asn ile glu met] [met lys]

So the Joy ribosome does what we set out to do at the beginning of this post, but it is not quite what we ultimately want and I've slipped in some cheating. Here are some things that still need to be addressed:

The ribosome translates mRNA to amino acids according to the real genetic code, whereas we really want it to translate mRNA to primitive Joy functions or combinators (artificial amino acids) according to an artificial genetic code.
The ribosome can output multiple polypeptides, but these peptides are hopelessly flat - they contain no quotations. In essence the produced lists correspond to unfolded (primary structure) proteins, but Joy programs without quotations would hardly be capable of any interesting behaviour.
I've treated the translate function as a primitive of Joy. This explains why I haven't provided its definition above. I wasn't able to provide it, because it is only defined at a language level, i.e. in the underlying Elixir implementation of Joy. The end result is that I've hardcoded the genetic code, injecting it from the outside, instead of representing it within the system. For completeness, here is the definition of translate:

  def translate(stack) do
    [head | rest] = stack

    amino_acid =
      case head do
        [:u, :u, :u] -> [:phe]
        [:u, :c, :u] -> [:ser]
        [:u, :a, :u] -> [:tyr]
        [:u, :g, :u] -> [:cys]
        [:u, :u, :c] -> [:phe]
        [:u, :c, :c] -> [:ser]
        [:u, :a, :c] -> [:tyr]
        [:u, :g, :c] -> [:cys]
        [:u, :u, :a] -> [:leu]
        [:u, :c, :a] -> [:ser]
        [:u, :a, :a] -> [] # stop codon
        [:u, :g, :a] -> [] # stop codon
        [:u, :u, :g] -> [:leu]
        [:u, :c, :g] -> [:ser]
        [:u, :a, :g] -> [] # stop codon
        [:u, :g, :g] -> [:trp]
        [:c, :u, :u] -> [:leu]
        [:c, :c, :u] -> [:pro]
        [:c, :a, :u] -> [:his]
        [:c, :g, :u] -> [:arg]
        [:c, :u, :c] -> [:leu]
        [:c, :c, :c] -> [:pro]
        [:c, :a, :c] -> [:his]
        [:c, :g, :c] -> [:arg]
        [:c, :u, :a] -> [:leu]
        [:c, :c, :a] -> [:pro]
        [:c, :a, :a] -> [:gln]
        [:c, :g, :a] -> [:arg]
        [:c, :u, :g] -> [:leu]
        [:c, :c, :g] -> [:pro]
        [:c, :a, :g] -> [:gln]
        [:c, :g, :g] -> [:arg]
        [:a, :u, :u] -> [:ile]
        [:a, :c, :u] -> [:thr]
        [:a, :a, :u] -> [:asn]
        [:a, :g, :u] -> [:ser]
        [:a, :u, :c] -> [:ile]
        [:a, :c, :c] -> [:thr]
        [:a, :a, :c] -> [:asn]
        [:a, :g, :c] -> [:ser]
        [:a, :u, :a] -> [:ile]
        [:a, :c, :a] -> [:thr]
        [:a, :a, :a] -> [:lys]
        [:a, :g, :a] -> [:arg]
        [:a, :u, :g] -> [:met]
        [:a, :c, :g] -> [:thr]
        [:a, :a, :g] -> [:lys]
        [:a, :g, :g] -> [:arg]
        [:g, :u, :u] -> [:val]
        [:g, :c, :u] -> [:ala]
        [:g, :a, :u] -> [:asp]
        [:g, :g, :t] -> [:gly]
        [:g, :u, :c] -> [:val]
        [:g, :c, :c] -> [:ala]
        [:g, :a, :c] -> [:asp]
        [:g, :g, :c] -> [:gly]
        [:g, :u, :a] -> [:val]
        [:g, :c, :a] -> [:ala]
        [:g, :a, :a] -> [:glu]
        [:g, :g, :a] -> [:gly]
        [:g, :u, :g] -> [:val]
        [:g, :c, :g] -> [:ala]
        [:g, :a, :g] -> [:glu]
        [:g, :g, :g] -> [:gly]
      end

    [amino_acid | rest]
  end

To end with, the Joy programs I've presented here, while very pleasing to me, are by no means readable; not to the untrained eye. I should remind the reader that firstly I'm not an expert in Joy and am probably not using the most idiomatic code and secondly that I'm purposefully using tediously repetitive code in order to limit the number of different functions that are used. Anonymous recursion is for instance built into the standard Joy libraries, which I'm not using. Using real Joy is probably much closer to real joy.

Be that as it may. We have now built a workable first iteration of the most important enzyme of our artificial life system. In the next few posts we will focus on ironing out the remaining three issues with this implementation. This will bring us to a critical milestone: having a ribosome that can produce itself given an appropriate mRNA template.

A typogenetics implementation in Elixir

Danie Palm — Sun, 14 Jun 2020 11:37:14 +0000

One of my favourite artificial life systems is called Typographical Genetics, or typogenetics in short. It was introduced by Douglas Hofstadter in his book Gödel, Escher, Bach. It is purposefully simplistic, but captures a number of principles found in "real" genetics remarkably well. In a sense, typogenetics was developed as a game for the amusement of the reader, and as such a crucial part of its functionality is left to the reader to play: the role of the ribosome.

In this post we take a look at typogenetics as a friendly introduction to the biological process of translation according to the rules of the genetic code. We then continue to implement typogenetics in Elixir.

Biology

There are two types of molecules or strings in typogenetics - typographical DNA and typographical enzymes. Just as real DNA is a strand made up of the nitrogen bases A, C, G and T, the DNA in typogenetics (which also plays the role of RNA) is made up of the letters "A", "C", "G", and "T". Similarly, just as real enzymes are chains of amino acids (each of which is usually represented as a three letter abbreviation), so enzymes in typogenetics are strings of three-letter "amino acids" like "cut", "cop", "swi".

Such a typographical enzyme is really a composition of the individual functions that correspond to each of the amino acids of the enzyme. Enzymes take DNA strands as input and never act on other enzymes.

Once bound to a DNA strand, an enzyme executes each of its amino acids or functions on the strand. In this way, an enzyme can introduce additional letters into the strand, delete letters, copy the strand, search for specific types of letters, or even switch to the complementary strand and continue its execution there. Here is the full list of typographical amino acids and their effect on DNA strands (the letters in parentheses represent a twist that we'll discuss later):

cut (s) - cut the DNA strand(s) to the right of the current position
del (s)- delete a base from the strand and move to the unit on the right
swi (r)- switch the enzyme to the other strand
mvr (s)- move the enzyme one DNA unit to the right
mvl (s)- move the enzyme one DNA unit to the left
cop (r)- enable copy mode
off (l)- disable copy mode
ina (s)- insert an A to the right of the current position
inc (r)- insert a C to the right of the current position
ing (r)- insert a G to the right of the current position
int (l)- insert a T to the right of the current position
rpy (r)- move to the nearest pyrimidine (C or T) to the right
rpu (l)- move to the nearest purine (A or G) to the right
lpy (l)- move to the nearest pyrimidine to the left
lpu (l)- move to the nearest purine to the left

Initially, copy mode is off. Any invocation of off has no effect in this case. Likewise, cop turns on copy mode only if it is not already on. The insert functions (in<x>) insert the given letter in the active strand, but also insert the complement of the given letter in the complementary strand if copy mode is on. del on the other hand always only acts on the active strand, whereas cut again acts on both strands. Switching (swi) terminates the enzyme execution if no base is present on the complementary strand at that position. Execution is also halted when moving or searching past the boundaries of the active strand, or when all the amino acids have been executed.

Like real enzymes, enzymes in typogenetics also fold up into a tertiary structure that ultimately depends on its primary amino acid sequence. And the tertiary structure in turn determines the binding preference of the enzyme, much like the tertiary structure of real enzymes forms binding sites that are specific to the enzyme's substrates. Each typogenetics amino acid is assigned a "kink" (straight, left, or right) that determines how the enzyme turns at every point. These kinks are listed in the table of amino acids above. Finally, the relative angles between the first and last amino acids (of which only four unique values exist: 0, 90, 180, and 270 degrees) are mapped onto the four bases in DNA, determining its affinity.

If the enzyme is always oriented so that the first segment points in an eastern direction, and if the last amino acid's kink is ignored, then the enzyme's affinity can effectively be determined by considering only the direction of the final segment of the enzyme:

First segment	Last segment	Affinity
East	East	A
East	North	C
East	South	G
East	West	T

Note that all of the inner amino acids (excluding only the first and last) determine the enzyme's affinity as a whole.

The typogenetics game starts off with a pool of DNA strands. First, a DNA strand is selected from the pool and translated according to the typogenetic code into an enzyme. The enzyme is then folded according to the kinks of its amino acids, its binding affinity is determined, it binds to a random DNA strand at a random position that matches its affinity, and starts to execute its amino acids one by one.

There are 15 amino acids, and hence we need pairs of DNA letters (called codons) to represent single amino acids. There are 16 possible pairs, leaving one pair that is not assigned to any amino acid. This extra unmatched codon (which is chosen to be "AA") will be used as punctuation, i.e. a stop codon. In real genetics, in contrast, codons are made up of 3 bases and there are 20 amino acids. This leaves a lot of room for redundancy. The table below summarizes the typogenetic code (rows represent the first letter and columns the second letter of the codon).

	A	C	G	T
A		cut	del	swi
C	mvr	mvl	cop	off
G	ina	inc	ing	int
T	rpy	rpu	lpy	lpu

Let's consider a quick end-to-end example. We pick a random DNA strand 'CGGATACTAAACCGA' and translate it to an enzyme. First, we chunk the strand by subsequences of length 2 (the length of a codon):

CG GA TA CT AA AC CG A

According to the typogenetic code, this maps to the following amino acids:

cop ina rpy off

and

cut cop

Note how the AA codon resulted in the initiation of a new enzyme and how the terminal unpaired A was discarded. Now let's pick the first enzyme cop-ina-rpy-off and fold it. The corresponding kinks are r s r l. We ignore the first kink and start of with the direction east, we go straight and hence the direction remains east, we turn right and now face south and finally we turn left to face east again.

cop - ina
       |
      rpy - off

The folded enzyme has three segments: east, south, east. The final segment is east so that the enzyme only has a binding affinity for the letter A.

Now consider another random DNA strand, CAGAGAGT that will serve as input to the enzyme above. Suppose the enzyme binds to the second A. It immediately switches on copy mode (cop) and then inserts an A (ina):

    T
CAGAAGAGT

Since copy mode is active, a complementary T is inserted in the complementary strand. Next we move right until a pyrimidine is reached (rpy). As the enzyme moves, it copies the active strand by inserting complementary bases in the inactive strand:

    TCTC
CAGAAGAGT

When T, a pyrimidine, is reached, copy mode is switched off (off). The enzyme has now executed all its amino acids and so terminates and is discarded. This releases the input and complementary strands back into the DNA pool. Note however that the complementary strand is inserted in reverse: CAGAAGAGT and CTCT.

Code

The Elixir implementation of typogenetics has many similarities to the "pool of protein" prototypes that we have developed so far in this series. I will not discuss it in detail here. Interested readers are invited to look at the source code on GitHub:

palm86 / typogenetics

Hofstadter's typographical genetics in Elixir

One interesting aspect is perhaps the data structure that is used to represent DNA strands. I have toyed with the idea of implementing typogenetics on a few occasions, but was never quite happy with the strand representations that I came up with. Approaching the problem from a functional angle finally led me to something that I find elegant.

Strands are complicated because they consist of a main sequence of letters, to which a complementary letter could be bound at any position, forming a potentially discontinuous complementary sequence. Moreover, strands are directional - the conventional "forward" direction is in the so called 5' to 3' direction. But when two strands pair up, they do so in opposite directions. Take for instance the sequence ACGT bound to its complementary sequence:

3'-TGCA-5'
5'-ACGT-3'

The final complication is that, apart from the letters in the strands, it is also necessary to keep track of the position at which the enzyme is bound to the strands.

+---+---+---+---+
|   |   | C |   | <- complementary
+---------------+
| A | C | G | T | <- active
+---+---+---+---+
      ^
   pointer

There are of course many ways to represent an enzyme-bound strand. One solution is to employ two arrays, one for the main strand and one for the complementary strand, and a pointer that keeps track of the index at which the enzyme is bound. This solution is not ideal because it requires resizing the arrays as the strands grow. And whenever the swi (switch) operation is encountered, the arrays have to be reversed and the pointer needs to be recalculated.

+---+---+---+---+
|   |   | C |   | <- complementary
| A | C | G | T | <- active
+---+---+---+---+
      ^
   pointer

A slightly better solution is to use only a single array in which the elements are 2-tuples or pairs - the first element of the tuple corresponding to a base of the active strand and the second element corresponding to a base of the complementary strand. This solution requires only a single array to be resized or reversed, but it still requires a separate pointer that has to be recalculated on swi.

    +-----+      +-----+
    | C,  |      | G,C |
    +-----+      +-----+
    | A,  |      | T,  |
    +-----+      +-----+
       ^            ^
  left_stack    right_stack

But we can still do better. Instead of using an array of pairs, two stacks can be used to elegantly get rid of the pointer. In other words, a pair of stacks of pairs. The top of the first stack represents the current position to which the enzyme is bound. The elements below it represent, in reverse order, all the bases up to the start. The second stack represents all the remaining base pairs in the usual order. The enzyme's position can be moved to the right by pushing the top of the right stack onto the left stack. Similarly, pushing the top of the left stack onto the right stack, moves the enzyme one step to the left. Switching strands is accomplished by swapping the left and right stacks and by swapping the base pairs in each stack.

In the stack-based solution, a bound strand is somewhat analogous to an open book. The stack of pages on the left hand side is sorted in descending order and the stack on the right is sorted in ascending order. The current position is implied by the number of pages on each stack. Let's arbitrarily suppose that the current page is the top page of the left hand stack. The current position can easily be changed by flipping pages from the right hand stack to the left hand stack, or the other way around. One could force the analogy and say that the "active" text is on one side of a page, and its complement or reverse shines through when viewing the page in the light. Pages can also be inserted in theory.

Let's consider an example representation in Elixir. Take for example the strand

  A|A
GAT|TACA

The | represents the current position. The active strand is at the bottom and the complementary strand is at the top. The current position is just left of the | in the active strand. We can represent this in Elixir with a 2-tuple of lists of 2-tuples:

{left_stack, right_stack}

With left_stack being:

[{:T, :A}, {:A, nil}, {:G, nil}]

Each entry of the list is a 2-tuple with the active strand base as first position, and its complement or nil (if no complementary base is present) as the second. Note that the list is reversed in comparison the the string representation above.

Similarly, the right_stack looks like this:

[{:T, :A}, {:A, nil}, {:C, nil}, {:A, nil}]

The only difference being that this time the order agrees with the string representation. Note that lists in Elixir are linked lists, which means that they behave pretty much like stacks.

You can clone the GitHub repo and run a simulation with:

$ iex -S mix
iex> Typogenetics.run()

This will generate 20 random strands of length 20 and start the execution. The output will look something like:

13:31:14.323 [info]  Consumed: ATACGAGCCGTCTATGGCCG

13:31:14.325 [info]  Produced: ATACCGCAGCCGTCTATGGCCG

13:31:14.722 [info]  Consumed: TGTCTGCAGGTTTGACCACT

13:31:14.722 [info]  Produced: TGTCTGCAGGTTTGCTTACCACT

13:31:14.722 [info]  Produced: AAGCA

Alternatively, you can use the package as a dependency and wire up the subcomponents for all kinds of experiments.

To conclude, typogenetics was designed as a game to introduce readers of Gödel, Escher, Bach to real genetics. But Hofstadter also posed the question as to whether typogenetics would be capable of self-reproduction. I.e. would it be possible to seed the game with just the right set of strands so that all of the strands will eventually (if not directly) be reproduced. Self-reproduction in typogenetics has been the topic of a number of theses and blogs and the system does indeed lend itself to all kinds of self-reproducing schemes.

However, a critical missing piece in typogenetics is the ribosome, an enzyme that is able to translate DNA into amino acids according to the Typogenetic Code. As it stands, the rules of typogenetics doesn't allow for a ribosome that is a true internal typogenetics enzyme. Such an enzyme would have to be able to act on DNA and produce an amino acids sequence. Instead, an external ribosome is pulled in, the player of the game.

Hofstadter was very much aware of the central role played by ribosomes, and purposefully omitted it to keep typogenetics digestible. Nevertheless, it is tempting to contemplate the minimal set of changes that can be elegantly introduced to typogenetics that would allow for ribosomes as first class citizens.

In the artificial life system that we are developing in this series, there will be no fixed rules to the effect that enzymes can only act on and produce DNA. Any such rules should come from within the system and should in principle be able to evolve with the system. This will allow us to develop a ribosome as first-class citizen.

DEV Community: Danie Palm

GenServer: from first principles

Preliminaries

A process that can receive messages

Problem

Adding state

Problem

Allowing requests to return data

Problem

Supporting asynchronous calls and removing boilerplate

Problem

GenServer

Conclusion

Efficient and reliable message publishing with RabbitMQ and Elixir

Synchronously awaiting publisher confirmations

Async handling of publisher confirmations

Full outline

Conclusion

Binary pattern matching <<1::1, 0::1, 1::1>>

Basics

Enter the bytes

Constructing and destructuring binaries

Advanced pattern matching

Bonus

Another bonus

Conclusion

Doing things only once in Elixir

handle_call doesn't have to reply immediately

Task is built on message passing

A solution

Church encoding in the concatenative language Joy

Joy

Church encoding

Church booleans

The and operator

The or operator

The not operator

Conditionals

Church numerals

The successor function succ

Addition

Multiplication

Exponentiation

Predecessor function

Subtraction

Church comparators and predicates

Advanced numerical operators

Division

Root extraction

Putting it all together

Applications

Digging and burying

Summary of definitions

Sources and further reading:

Proteins as programs - to mock a matchingbird

Chemical recognition, affinity, and binding

The match predicate function

Testing the match predicate function

A primordial soup, a slimy pool

Testing the waters

Conclusion

LiveJoy with Phoenix LiveView

No JavaScript added

Phoenix LiveView

LiveJoy implementation

Template

Event handling

Evaluation

Styling

Ubuntu Terminal in CSS

Cody Pearce ・ Feb 15 '20

Dockerized deploy on Heroku

Conclusion

Church Booleans in Joy

Interdependence of Joy primitives

ifte as a primitive

true and false as primitives

Church encoding

ifte, true, and false as composites

Boolean operators

`handle_call` doesn't have to reply immediately

`Task` is built on message passing

The `and` operator

The `or` operator

The `not` operator

The successor function `succ`

The `match` predicate function

Testing the `match` predicate function

`ifte` as a primitive

`true` and `false` as primitives

`ifte`, `true`, and `false` as composites

A composed `ifte` with identical semantics to the built-in Joy `ifte` combinator