• distributed and fault-tolerant (a piece of failing software or hardware should not bring the system down)
• concurrent (it can spawn many processes, each executing a small and well-defined piece of work, and isolated from one another but able to communicate via messaging)
• hot-swappable (code can be swapped into the system while it’s running, leading to high availability and minimal system downtime)

Syntax

Erlang makes heavy use of recursion. Since data is immutable in Erlang, the use of while and for loops (where a variable needs to keep changing its value) is not allowed.

Here’s an example of recursion, showing how a function repeatedly strips the first letter from the front of a name and prints it, only stopping when the last letter has been encountered.

-module(name).

-export([print_name/1]).

print_name([RemainingLetter | []]) ->
  io:format("~c~n", [RemainingLetter]);
print_name([FirstLetter | RestOfName]) ->
  io:format("~c~n", [FirstLetter]),
  print_name(RestOfName).

Output:

> name:print_name("Mike").
M
i
k
e
ok

There is also a heavy emphasis on pattern-matching, which frequently eliminates the need for an if structure or case statement. In the following example, there are two matches for specific names, followed by a catch-all for any other names.

-module(greeting).

-export([say_hello/1]).

say_hello("Mary") ->
  "Welcome back Mary!";
say_hello("Tom") ->
  "Howdy Tom.";
say_hello(Name) ->
  "Hello " ++ Name ++ ".".

Output:

> greeting:say_hello("Mary").
"Welcome back Mary!"
> greeting:say_hello("Tom").
"Howdy Tom."
> greeting:say_hello("Beth").
"Hello Beth."

Erlang Term Storage

Erlang Term Storage, normally abbreviated as ETS, is an in-memory database built into OTP. It’s accessible within Elixir, and is a powerful alternative to solutions like Redis when your application runs on a single node.

Quick Start

To create an ETS table you first need to initialize a table tableName = :ets.new(:table_otp_name, []), once you have initialized a table you can: insert data, lookup values, delete data, and more.

ETS Demo in IEX

iex(1)> myETSTable = :ets.new(:my_ets_table, [])
#Reference<0.1520230345.550371329.65846>
iex(2)> :ets.insert(myETSTable, {"favoriteWebSite", "freeCodeCamp"})
true
iex(3)> :ets.insert(myETSTable, {"favoriteProgrammingLanguage", "Elixir"})
true
iex(4)> :ets.i(myETSTable)
<1   > {<<"favoriteProgrammingLanguage">>,<<"Elixir">>}
<2   > {<<"favoriteWebSite">>,<<"freeCodeCamp">>}
EOT  (q)uit (p)Digits (k)ill /Regexp -->

Persistence

ETS Tables are not persistent and are destroyed once the process which owns it terminates. If you would like to store data persistently a traditional database and/or file-based storage is recommended.

Use cases

ETS Tables are commonly used for caching data in the application, for example account data fetched from a database may be stored in an ETS Table to reduce the amount of queries to the database. Another use case is for rate limiting use of features in a web application - ETS’s fast read and write speed make it great for this. ETS Tables are a powerful tool for developing highly concurrent web applications at the lowest possible hardware cost.

Try it out

There are websites where you can try running Erlang commands without having to install anything locally, like these:

• Give it a try! (a hands-on tutorial)
• TutorialsPoint CodingGround

If you’d like to install it on your (or a virtual) machine, you can find installation files at Erlang.org or on Erlang Solutions.

More Information:

• About Erlang
• Erlang (programming language)

I wrote my first game in Elixir. It is a popular thing — Conway’s Game of Life — but it gets quite interesting when you solve it in a functional language, especially when you can see how the actor model works and how actors are distributed across servers in the network.

Game of Life

In this blog post I am going to show:

• how to write rules for the game of life with tests in Elixir,
• parallel tasks across lightweight processes (actors) in order to utilize all CPU cores,
• how to distribute work across nodes so the game can be executed by many servers in the cluster,
• how to use GenServer behaviour, TaskSupervisor and Agents in Elixir.

This project and the full source code can be found here.

Demo

Let’s start with watching quick demo of how the game works.

GameOfLife
_Recorded by ArturT_asciinema.org

As you can see, node1 represents running game and board on the screen. The second node was also started and connected to the first one. From the second node, we added new cells to the board. Both nodes are responsible for processing the game, but only the first node is a primary with information about the current state of the game. We can connect more nodes to the cluster so game processing can happen on all of the nodes. You are going to learn in this article how to make it happen.

Game of Life rules

If you already know about the game of life problem just jump to the next header. If not, in this section you can learn the basic concept.

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

• Any live cell with fewer than two live neighbours dies as if caused by under-population.
• Any live cell with two or three live neighbours lives on to the next generation.
• Any live cell with more than three live neighbours dies, as if by over-population.
• Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed — births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations.

Create new application in Elixir

First things first, so we are going to create a new Elixir OTP application with supervision tree. We will use supervisor for our game server, you will learn more about it a bit later.

$ mix new --sup game_of_life

A --sup option is given to generate an OTP application skeleton including a supervision tree. Normally an app is generated without a supervisor and without the app callback.

In lib/game_of_life.ex file you will find an example of how to add child worker to supervisor.

# lib/game_of_life.exdefmodule GameOfLife do  use Application  # See http://elixir-lang.org/docs/stable/elixir/Application.html  # for more information on OTP Applications  def start(_type, _args) do    import Supervisor.Spec, warn: false    children = [      # Define workers and child supervisors to be supervised      # worker(GameOfLife.Worker, [arg1, arg2, arg3]),    ]    # See http://elixir-lang.org/docs/stable/elixir/Supervisor.html    # for other strategies and supported options    opts = [strategy: :one_for_one, name: GameOfLife.Supervisor]    Supervisor.start_link(children, opts)  endend

Represent the board in Game of Life

We need to represent the alive cells on the board in our game. A single cell can be a tuple {x, y} with coordinates in the 2-dimensional board.

All alive cells on the board will be on the list alive_cells.

alive_cells = [{0, 0}, {1, 0}, {2, 0}, {1, 1}, {-1,-2}]

Here is an example of how this board with alive cells looks like:

Board with alive cells

and here are proper x & y coordinates:

Coordinates of alive cells

Now when we have the idea of how we are going to store our alive cells we can jump to write some code.

Game of Life rules with tests

We can create GameOfLife.Cell module with function keep_alive?/2 responsible for determining if a particular alive cell {x, y} should be still alive on the next generation or not.

Here is the function with expected arguments:

# lib/game_of_life/cell.exdefmodule GameOfLife.Cell do  def keep_alive?(alive_cells, {x, y} = _alive_cell) do    # TODO  endend

Let’s write some tests to cover the first of the requirements of the Game of Life:

Any live cell with fewer than two live neighbours dies, as if caused by under-population.

We wrote tests to ensure GameOfLife.Cell.keep_alive?/2 function returns false in a case when the alive cell has no neighbours or has just one.

# test/game_of_life/cell_test.exsdefmodule GameOfLife.CellTest do  use ExUnit.Case, async: true  test "alive cell with no neighbours dies" do    alive_cell = {1, 1}    alive_cells = [alive_cell]    refute GameOfLife.Cell.keep_alive?(alive_cells, alive_cell)  end  test "alive cell with 1 neighbour dies" do    alive_cell = {1, 1}    alive_cells = [alive_cell, {0, 0}]    refute GameOfLife.Cell.keep_alive?(alive_cells, alive_cell)  endend

GameOfLife.Cell.keep_alive?/2 function needs to return false just to pass our tests so let’s add more tests to cover other requirements.

Any live cell with more than three live neighbours dies, as if by over-population.

# test/game_of_life/cell_test.exstest "alive cell with more than 3 neighbours dies" do  alive_cell = {1, 1}  alive_cells = [alive_cell, {0, 0}, {1, 0}, {2, 0}, {2, 1}]  refute GameOfLife.Cell.keep_alive?(alive_cells, alive_cell)end

Any live cell with two or three live neighbours lives on to the next generation.

# test/game_of_life/cell_test.exstest "alive cell with 2 neighbours lives" do  alive_cell = {1, 1}  alive_cells = [alive_cell, {0, 0}, {1, 0}]  assert GameOfLife.Cell.keep_alive?(alive_cells, alive_cell)endtest "alive cell with 3 neighbours lives" do  alive_cell = {1, 1}  alive_cells = [alive_cell, {0, 0}, {1, 0}, {2, 1}]  assert GameOfLife.Cell.keep_alive?(alive_cells, alive_cell)end

Now, we can implement our GameOfLife.Cell.keep_alive?/2 function.

# lib/game_of_life/cell.exdefmodule GameOfLife.Cell do  def keep_alive?(alive_cells, {x, y} = _alive_cell) do    case count_neighbours(alive_cells, x, y, 0) do      2 -> true      3 -> true      _ -> false    end  end  defp count_neighbours([head_cell | tail_cells], x, y, count) do    increment = case head_cell do      {hx, hy} when hx == x - 1 and hy == y - 1 -> 1      {hx, hy} when hx == x     and hy == y - 1 -> 1      {hx, hy} when hx == x + 1 and hy == y - 1 -> 1      {hx, hy} when hx == x - 1 and hy == y     -> 1      {hx, hy} when hx == x + 1 and hy == y     ->; 1      {hx, hy} when hx == x - 1 and hy == y + 1 ->; 1      {hx, hy} when hx == x     and hy == y + 1 -> 1      {hx, hy} when hx == x + 1 and hy == y + 1 -> 1      _not_neighbour -> 0    end    count_neighbours(tail_cells, x, y, count + increment)  end  defp count_neighbours([], _x, _y, count), do: countend

As you can see, we implemented the private function count_neighbours/4 responsible for counting neighbours. It will be helpful to meet the next rule.

There is one more requirement we forgot about:

Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

We are going to write a new function GameOfLife.Cell.become_alive?/2 expecting the coordinates of the dead cell and returning if the dead cell should become alive or not.

# lib/game_of_life/cell.exdefmodule GameOfLife.Cell do  def become_alive?(alive_cells, {x, y} = _dead_cell) do    3 == count_neighbours(alive_cells, x, y, 0)  endend

And here is the test for that:

# test/game_of_life/cell_test.exstest "dead cell with three live neighbours becomes a live cell" do  alive_cells = [{2, 2}, {1, 0}, {2, 1}]  dead_cell = {1, 1}  assert GameOfLife.Cell.become_alive?(alive_cells, dead_cell)endtest "dead cell with two live neighbours stays dead" do  alive_cells = [{2, 2}, {1, 0}]  dead_cell = {1, 1}  refute GameOfLife.Cell.become_alive?(alive_cells, dead_cell)end

There is one more thing which might be helpful for us. We have the list of alive cells but we don’t know much about the dead cells. The number of dead cells is infinite so we need to cut down the number of dead cells for which we want to check if they should become alive. The simple way would be to check only dead cells with alive neighbours. Hence the GameOfLife.Cell.dead_neighbours/1function.

Let’s write some tests first:

# test/game_of_life/cell_test.exstest "find dead cells (neighbours of alive cell)" do  alive_cells = [{1, 1}]  dead_neighbours = GameOfLife.Cell.dead_neighbours(alive_cells) |> Enum.sort  expected_dead_neighbours = [    {0, 0}, {1, 0}, {2, 0},    {0, 1}, {2, 1},    {0, 2}, {1, 2}, {2, 2}  ] |>; Enum.sort  assert dead_neighbours == expected_dead_neighboursendtest "find dead cells (neighbours of alive cells)" do  alive_cells = [{1, 1}, {2, 1}]  dead_neighbours = GameOfLife.Cell.dead_neighbours(alive_cells) |> Enum.sort  expected_dead_neighbours = [    {0, 0}, {1, 0}, {2, 0}, {3, 0},    {0, 1}, {3, 1},    {0, 2}, {1, 2}, {2, 2}, {3, 2}  ] |> Enum.sort  assert dead_neighbours == expected_dead_neighboursend

and here is the implemented function:

# lib/game_of_life/cell.exdef dead_neighbours(alive_cells) do  neighbours = neighbours(alive_cells, [])  (neighbours |> Enum.uniq) -- alive_cellsenddefp neighbours([{x, y} | cells], neighbours) do  neighbours(cells, neighbours ++ [    {x - 1, y - 1}, {x    , y - 1}, {x + 1, y - 1},    {x - 1, y    }, {x + 1, y    },    {x - 1, y + 1}, {x    , y + 1}, {x + 1, y + 1}  ])enddefp neighbours([], neighbours), do: neighbours

Basically, these are all rules implemented in the single module GameOfLife.Cell. You can see the whole module file with tests on GitHub.

The architecture of distributed Game of Life

The architecture of distributed Game of Life in Elixir

Our main supervisor is GameOfLife.Supervisor which I mentioned at the beginning of the article. Below you can see how we defined its children like Task.Supervisor, workers for BoardServer and GamePrinter.

# lib/game_of_life.exdefmodule GameOfLife do  use Application  # See http://elixir-lang.org/docs/stable/elixir/Application.html  # for more information on OTP Applications  def start(_type, _args) do    import Supervisor.Spec, warn: false    init_alive_cells = []    children = [      # Define workers and child supervisors to be supervised      # worker(GameOfLife.Worker, [arg1, arg2, arg3]),      supervisor(Task.Supervisor, [[name: GameOfLife.TaskSupervisor]]),      worker(GameOfLife.BoardServer, [init_alive_cells]),      # We will uncomment this line later      # worker(GameOfLife.GamePrinter, []),    ]    # See http://elixir-lang.org/docs/stable/elixir/Supervisor.html    # for other strategies and supported options    opts = [strategy: :one_for_one, name: GameOfLife.Supervisor]    Supervisor.start_link(children, opts)  endend

Let me describe what each component on the image is responsible for.

Task.Supervisor is an Elixir module defining a new supervisor which can be used to dynamically supervise tasks. We are going to use it to spin off tasks like determining if the particular cell should live or die. Those tasks can be run across nodes connected into the cluster.

In the above code, we gave the name GameOfLife.TaskSupervisor for our supervisor. We will use this name to tell the Task.Supervisor.async function which Task Supervisor should handle our task. You can read more about Task.Supervisor here.

GameOfLife.BoardServer is our module implemented as GenServer behaviour. It is responsible for holding the state of the game. By that I mean it keeps the list of alive cells on the board along with generation counter and TRef. TRef is a timer reference returned by the Erlang timer module and the apply_interval function.

We want to start the game and generate a new list of alive cells for the next generation with a specified time interval. With each new generation, we will update the generation counter. The other interesting thing is that GameOfLife.BoardServer is running only on a single node. Once another node is connected to the cluster where is already running GameOfLife.BoardServer then GameOfLife.BoardServer won’t be started just like that on the newly connected node.

Instead on the new node GameOfLife.BoardServer will keep the only reference to the PID of the process existing on the first node. We want to have the single source of truth about the state of our game in one primary GameOfLife.BoardServer process existing on the first node started in the cluster.

GameOfLife.GamePrinter is a simple module using Agent in order to keep TRef (time reference) so we can print the board to STDOUT with the specified interval. We will use Erlang timer module to print the board on the screen every second.

You may wonder what’s the difference between GenServer and Agent.

A GenServer is a process like any other Elixir process and it can be used to keep state, execute code asynchronously, and so on. The advantage of using a generic server process (GenServer) is that it will have a standard set of interface functions and include functionality for tracing and error reporting. It also fits into a supervision tree as this is what we did in the GameOfLife module.

On the other hand, Agent is a much simpler solution than GenServer. Agents are a simple abstraction around state. Often in Elixir there is a need to share or store state that must be accessed from different processes or by the same process at different points in time. The Agent module provides a basic server implementation that allows state to be retrieved and updated via a simple API. This is what we are going to do in GameOfLife.GamePrinter as we only need to keep time reference to our timer interval.

Create node manager for task supervisor

Let’s start with something simple just to see if we can distribute work across nodes in the cluster. We assume each new process created by task supervisor will be assigned randomly to one of the connected nodes. Each node should be equally overloaded with the assumption that each task is pretty similar and all nodes are machines with the same configuration and overload.

# lib/game_of_life/node_manager.exdefmodule GameOfLife.NodeManager do  def all_nodes do    [Node.self | Node.list]  end  def random_node do    all_nodes |> Enum.random  endend

Our node manager has random_node/0 function which returns the name of a random node connected to the cluster. Basically, that’s it. A simple solution should be enough for now.

Create board helper functions

We need some helper functions for operations we can do on the board like adding and removing cells. Let’s start with tests for the module GameOfLife.Board and function add_cells/2.

# test/game_of_life/board_test.exsdefmodule GameOfLife.BoardTest do  use ExUnit.Case, async: true  test "add new cells to alive cells without duplicates" do    alive_cells = [{1, 1}, {2, 2}]    new_cells = [{0, 0}, {1, 1}]    actual_alive_cells = GameOfLife.Board.add_cells(alive_cells, new_cells)                          |> Enum.sort    expected_alive_cells = [{0, 0}, {1, 1}, {2, 2}]    assert actual_alive_cells == expected_alive_cells  endend

We need to ensure we won’t allow adding the same cell twice to the board so we test that there are no duplicates. Here is the implementation for add_cells/2 function:

# lib/game_of_life/board.exdefmodule GameOfLife.Board do  def add_cells(alive_cells, new_cells) do    alive_cells ++ new_cells    |> Enum.uniq  endend

Another thing is removing cells from the list of alive cells:

# test/game_of_life/board_test.exstest "remove cells which must be killed from alive cells" do  alive_cells = [{1, 1}, {4, -2}, {2, 2}, {2, 1}]  kill_cells = [{1, 1}, {2, 2}]  actual_alive_cells = GameOfLife.Board.remove_cells(alive_cells, kill_cells)  expected_alive_cells = [{4, -2}, {2, 1}]  assert actual_alive_cells == expected_alive_cellsend

Implementation is super simple:

# lib/game_of_life/board.exdef remove_cells(alive_cells, kill_cells) do  alive_cells -- kill_cellsend

Let’s create something more advanced. We should determine which cells should still live in the next generation after the tick. Here is a test for the GameOfLife.Board.keep_alive_tick/1 function:

# test/game_of_life/board_test.exstest "alive cell with 2 neighbours lives on to the next generation" do  alive_cells = [{0, 0}, {1, 0}, {2, 0}]  expected_alive_cells = [{1, 0}]  assert GameOfLife.Board.keep_alive_tick(alive_cells) == expected_alive_cellsend

The function keep_alive_tick does a few things like creating a new task with Task.Supervisor for each alive cell. Tasks will be created across available nodes in the cluster. We calculate if alive cells should stay alive or be removed. The keep_alive_or_nilify/2 function returns if the cell should live or nil otherwise.

We wait with Task.await/1 until all tasks across all nodes finished their work. Tasks are working in parallel but we need to wait for results from each task. We remove from the list the nil values so at the end we end up with only alive cells for the next generation.

# lib/game_of_life/board.ex@doc "Returns cells that should still live on the next generation"def keep_alive_tick(alive_cells) do  alive_cells  |> Enum.map(&(Task.Supervisor.async(                {GameOfLife.TaskSupervisor, GameOfLife.NodeManager.random_node},                GameOfLife.Board, :keep_alive_or_nilify, [alive_cells, &1])))  |>; Enum.map(&Task.await/1)  |> remove_nil_cellsenddef keep_alive_or_nilify(alive_cells, cell) do  if GameOfLife.Cell.keep_alive?(alive_cells, cell), do: cell, else: nilenddefp remove_nil_cells(cells) do  cells  |> Enum.filter(fn cell -> cell != nil end)end

There is one more case we should handle which is a situation when dead cells should become alive. GameOfLife.Board.become_alive_tick/1 function will be responsible for that.

# test/game_of_life/board_test.exstest "dead cell with three live neighbours becomes a live cell" do  alive_cells = [{0, 0}, {1, 0}, {2, 0}, {1, 1}]  born_cells = GameOfLife.Board.become_alive_tick(alive_cells)  expected_born_cells = [{1, -1}, {0, 1}, {2, 1}]  assert born_cells == expected_born_cellsend

This is how our function looks like:

# lib/game_of_life/board.ex@doc "Returns new born cells on the next generation"def become_alive_tick(alive_cells) do  GameOfLife.Cell.dead_neighbours(alive_cells)  |> Enum.map(&(Task.Supervisor.async(                {GameOfLife.TaskSupervisor, GameOfLife.NodeManager.random_node},                GameOfLife.Board, :become_alive_or_nilify, [alive_cells, &1])))  |>; Enum.map(&Task.await/1)  |> remove_nil_cellsenddef become_alive_or_nilify(alive_cells, dead_cell) do  if GameOfLife.Cell.become_alive?(alive_cells, dead_cell), do: dead_cell, else: nilend

It works similarly to GameOfLife.Board.keep_alive_tick/1. First, we are looking for the dead neighbours of alive cells. Then for each dead cell we create a new process across the nodes in the cluster to determine if the dead cell should become alive in the next generation.

You can see the full source code of GameOfLife.Board module and tests on github.

Create BoardServer

Let’s create GameOfLife.BoardServer generic server behaviour. We define a public interface for the server.

# lib/game_of_life/board_server.exdefmodule GameOfLife.BoardServer do  use GenServer  require Logger  @name {:global, __MODULE__}  @game_speed 1000 # miliseconds  # Client  def start_link(alive_cells) do    case GenServer.start_link(__MODULE__, {alive_cells, nil, 0}, name: @name) do      {:ok, pid} ->        Logger.info "Started #{__MODULE__} master"        {:ok, pid}      {:error, {:already_started, pid}} ->        Logger.info "Started #{__MODULE__} slave"        {:ok, pid}    end  end  def alive_cells do    GenServer.call(@name, :alive_cells)  end  def generation_counter do    GenServer.call(@name, :generation_counter)  end  def state do    GenServer.call(@name, :state)  end  @doc """  Clears board and adds only new cells.  Generation counter is reset.  """  def set_alive_cells(cells) do    GenServer.call(@name, {:set_alive_cells, cells})  end  def add_cells(cells) do    GenServer.call(@name, {:add_cells, cells})  end  def tick do    GenServer.cast(@name, :tick)  end  def start_game(speed \\ @game_speed) do    GenServer.call(@name, {:start_game, speed})  end  def stop_game do    GenServer.call(@name, :stop_game)  end  def change_speed(speed) do    stop_game    start_game(speed)  endend

As you can see, we use GenServer behaviour in our module. The module requires also Logger as we would like to print some info to the STDOUT.

In the start_link/1 function we start a new GenServer. When our generic server starts, it is as a first process in the cluster. Then it becomes the primary process. In the case when there is already a running process with a globally registered name {:global,__MODULE__}, we log info that our process will be a replica process with a reference to the existing PID on another node in the cluster.

We store the global name for our server in the attribute @name. We use another attribute @game_speed for default game speed which is 1000 milliseconds.

In our public interface, we have the alive_cells/1 function which returns the list of alive cells. Basically, it is the current state of the game (alive cells on the board). This function calls GenServer with the registered @name and requests :alive_cells. We need to implement the handle_call/3 function for this type of request (:alive_cells).

There is another public function generation_counter/1 which returns how many generations were already processed by the board server.

The state/1 function returns state that is held by our generic server. The state is represented as the tuple with 3 values like alive cells, TRef (time reference - we want to regenerate board every second) and generation counter. TRef is a very internal thing for the board server so we won’t return this to the outside world. That’s why we will return just alive cells and the generation counter. You will see it later in the implementation for handle_call(:state, _from, state).

You can use the set_alive_cells/1 function in the case when you want to override the current list of alive cells with a new list.

The add_cells/1 function will be very useful as we want to be able to add new cells or figures to the board. For instance, we may want to add a blinker pattern to the existing game. You will learn more about patterns later.

blinker pattern

We can manually force the game to calculate the next generation of cells with the tick/1 function.

The start_game/1 function is responsible for starting a new timer which calls every second a tick/1 function. Thanks to that our game will update the list of alive cells within a specified interval which is @game_speed.

The last 2 functions are stop_game/1 and change_speed/1 which just restart the game and start a new one with the provided speed.

Now you can see how the above functions are working. They are calling server callbacks.

# lib/game_of_life/board_server.exdefmodule GameOfLife.BoardServer do  use GenServer  # ...  # Server (callbacks)  def handle_call(:alive_cells, _from, {alive_cells, _tref, _generation_counter} = state) do    {:reply, alive_cells, state}  end  def handle_call(:generation_counter, _from, {_alive_cells, _tref, generation_counter} = state) do    {:reply, generation_counter, state}  end  def handle_call(:state, _from, {alive_cells, _tref, generation_counter} = state) do    {:reply, {alive_cells, generation_counter}, state}  end  def handle_call({:set_alive_cells, cells}, _from, {_alive_cells, tref, _generation_counter}) do    {:reply, cells, {cells, tref, 0}}  end  def handle_call({:add_cells, cells}, _from, {alive_cells, tref, generation_counter}) do    alive_cells = GameOfLife.Board.add_cells(alive_cells, cells)    {:reply, alive_cells, {alive_cells, tref, generation_counter}}  end  def handle_call({:start_game, speed}, _from, {alive_cells, nil = _tref, generation_counter}) do    {:ok, tref} = :timer.apply_interval(speed, __MODULE__, :tick, [])    {:reply, :game_started, {alive_cells, tref, generation_counter}}  end  def handle_call({:start_game, _speed}, _from, {_alive_cells, _tref, _generation_counter} = state) do    {:reply, :game_already_running, state}  end  def handle_call(:stop_game, _from, {_alive_cells, nil = _tref, _generation_counter} = state) do    {:reply, :game_not_running, state}  end  def handle_call(:stop_game, _from, {alive_cells, tref, generation_counter}) do    {:ok, :cancel} = :timer.cancel(tref)    {:reply, :game_stoped, {alive_cells, nil, generation_counter}}  end  def handle_cast(:tick, {alive_cells, tref, generation_counter}) do    keep_alive_task = Task.Supervisor.async(                      {GameOfLife.TaskSupervisor, GameOfLife.NodeManager.random_node},                      GameOfLife.Board, :keep_alive_tick, [alive_cells])    become_alive_task = Task.Supervisor.async(                        {GameOfLife.TaskSupervisor, GameOfLife.NodeManager.random_node},                        GameOfLife.Board, :become_alive_tick, [alive_cells])    keep_alive_cells = Task.await(keep_alive_task)    born_cells = Task.await(become_alive_task)    alive_cells = keep_alive_cells ++ born_cells    {:noreply, {alive_cells, tref, generation_counter + 1}}  endend

Oh, we forgot about tests. In this case, we can use DocTest. It allows us to generate tests from the code examples existing in a module/function/macro’s documentation.

Our test file is super short:

# test/game_of_life/board_server_test.exsdefmodule GameOfLife.BoardServerTest do  use ExUnit.Case  doctest GameOfLife.BoardServerend

Let’s add @moduledoc to GameOfLife.BoardServer.

# lib/game_of_life/board_server.exdefmodule GameOfLife.BoardServer do  use GenServer  require Logger  @moduledoc """  ## Example      iex> GameOfLife.BoardServer.start_game      :game_started      iex> GameOfLife.BoardServer.start_game      :game_already_running      iex> GameOfLife.BoardServer.stop_game      :game_stoped      iex> GameOfLife.BoardServer.stop_game      :game_not_running      iex> GameOfLife.BoardServer.change_speed(500)      :game_started      iex> GameOfLife.BoardServer.stop_game      :game_stoped      iex> GameOfLife.BoardServer.set_alive_cells([{0, 0}])      [{0, 0}]      iex> GameOfLife.BoardServer.alive_cells      [{0, 0}]      iex> GameOfLife.BoardServer.add_cells([{0, 1}])      [{0, 0}, {0, 1}]      iex> GameOfLife.BoardServer.alive_cells      [{0, 0}, {0, 1}]      iex> GameOfLife.BoardServer.state      {[{0, 0}, {0, 1}], 0}      iex> GameOfLife.BoardServer.generation_counter      0      iex> GameOfLife.BoardServer.tick      :ok      iex> GameOfLife.BoardServer.generation_counter      1      iex> GameOfLife.BoardServer.state      {[], 1}  """end

As you can see we have grouped 3 examples in the @moduledoc attribute and they are separated by a new line. When you run tests you will see 3 separate tests.

$ mix test test/game_of_life/board_server_test.exsCompiled lib/game_of_life/board_server.ex20:54:30.637 [info]  Started Elixir.GameOfLife.BoardServer master...Finished in 0.1 seconds (0.1s on load, 0.00s on tests)3 tests, 0 failuresRandomized with seed 791637

In GameOfLife.BoardServer you probably noticed 2 interesting things. First is GameOfLife.Board which is called in:

# lib/game_of_life/board_server.exdef handle_call({:add_cells, cells}, _from, {alive_cells, tref, generation_counter}) do  alive_cells = GameOfLife.Board.add_cells(alive_cells, cells)  {:reply, alive_cells, {alive_cells, tref, generation_counter}}end

As you saw before we added some useful functions to GameOfLife.Board module which helps us to do operations on the list of alive cells.

Another interesting thing is how we use Task.Supervisor in:

# lib/game_of_life/board_server.exdef handle_cast(:tick, {alive_cells, tref, generation_counter}) do    keep_alive_task = Task.Supervisor.async(                      {GameOfLife.TaskSupervisor, GameOfLife.NodeManager.random_node},                      GameOfLife.Board, :keep_alive_tick, [alive_cells])    become_alive_task = Task.Supervisor.async(                        {GameOfLife.TaskSupervisor, GameOfLife.NodeManager.random_node},                        GameOfLife.Board, :become_alive_tick, [alive_cells])    keep_alive_cells = Task.await(keep_alive_task)    born_cells = Task.await(become_alive_task)    alive_cells = keep_alive_cells ++ born_cells    {:noreply, {alive_cells, tref, generation_counter + 1}}  end

What we are doing here is spinning off a new async process to run the GameOfLife.keep_alive_tick/1 function with the argument alive_cells.

# lib/game_of_life/board_server.exkeep_alive_task = Task.Supervisor.async(                  {GameOfLife.TaskSupervisor, GameOfLife.NodeManager.random_node},                  GameOfLife.Board, :keep_alive_tick, [alive_cells])

The tuple {GameOfLife.TaskSupervisor, GameOfLife.NodeManager.random_node} tells Task.Supervisor that we want to use task supervisor with the name GameOfLife.TaskSupervisor and we want to run the process on the node returned by the GameOfLife.NodeManager.random_node function.

Create game printer and console presenter

GameOfLife.GamePrinter module is running as a worker under the supervision of the GameOfLife supervisor. GameOfLife.GamePrinter is using Agent to store TRef for timer reference as we want to print the board to the STDOUT with the specified interval.

You have already seen the example of using Agent so this shouldn’t be new for you. Basically, we wrote the public interface to start and stop printing the board to the screen. For tests we used DocTest.

# lib/game_of_life/game_printer.exdefmodule GameOfLife.GamePrinter do  @moduledoc """  ## Example      iex> GameOfLife.GamePrinter.start_printing_board      :printing_started      iex> GameOfLife.GamePrinter.start_printing_board      :already_printing      iex> GameOfLife.GamePrinter.stop_printing_board      :printing_stopped      iex> GameOfLife.GamePrinter.stop_printing_board      :already_stopped  """  @print_speed 1000  def start_link do    Agent.start_link(fn -> nil end, name: __MODULE__)  end  def start_printing_board do    Agent.get_and_update(__MODULE__, __MODULE__, :do_start_printing_board, [])  end  def do_start_printing_board(nil = _tref) do    {:ok, tref} = :timer.apply_interval(@print_speed, __MODULE__, :print_board, [])    {:printing_started, tref}  end  def do_start_printing_board(tref), do: {:already_printing, tref}  def print_board do    {alive_cells, generation_counter} = GameOfLife.BoardServer.state    alive_counter = alive_cells |> Enum.count    GameOfLife.Presenters.Console.print(alive_cells, generation_counter, alive_counter)  end  def stop_printing_board do    Agent.get_and_update(__MODULE__, __MODULE__, :do_stop_printing_board, [])  end  def do_stop_printing_board(nil = _tref), do: {:already_stopped, nil}  def do_stop_printing_board(tref) do    {:ok, :cancel} = :timer.cancel(tref)    {:printing_stopped, nil}  endend

GameOfLife.Presenters.Console is responsible for printing the board nicely with X & Y axes, the number of alive cells, and the generation counter. Let’s start with tests. We are going to capture STDOUT and compare if data printed to the screen are looking as we expect.

# test/game_of_life/presenters/console_test.exsdefmodule GameOfLife.Presenters.ConsoleTest do  use ExUnit.Case  # allows to capture stuff sent to stdout  import ExUnit.CaptureIO  test "print cells on the console output" do    cell_outside_of_board = {-1, -1}    cells = [{0, 0}, {1, 0}, {2, 0}, {1, 1}, {0, 2}, cell_outside_of_board]    result = capture_io fn -&gt;      GameOfLife.Presenters.Console.print(cells, 123, 6, 0, 2, 2, 2)    end    assert result == (    "    2| O,,\n" <>    "    1| ,O,\n" <>    "    0| OOO\n" <>    "     | _ _ \n" <;&gt;    "    /  0    \n" &lt;>    "Generation: 123\n" &lt;&gt;    "Alive cells: 6\n"    )  endend

Here is the implementation of our print function:

# lib/game_of_life/presenters/console.exdefmodule GameOfLife.Presenters.Console do  @doc """  Print cells to the console output.  Board is visible only for specified size for x and y.  Start x and y are in top left corner of the board.  `x_padding` Must be a prime number. Every x divided by the prime number  will be visible on x axis.  `y_padding` Any number. Padding for numbers on y axis.  """  def print(cells, generation_counter, alive_counter, start_x \\ -10, start_y \\ 15, x_size \\ 60,            y_size \\ 20, x_padding \\ 5, y_padding \\ 5) do    end_x = start_x + x_size    end_y = start_y - y_size    x_range = start_x..end_x    y_range = start_y..end_y    for y &lt;- y_range, x <- x_range do      # draw y axis      if x == start_x do        (y        |>; Integer.to_string        |> String.rjust(y_padding)) <&gt; "| "        |&gt; IO.write      end      IO.write(if Enum.member?(cells, {x, y}), do: "O", else: ",")      if x == end_x, do: IO.puts ""    end    # draw x axis    IO.write String.rjust("| ", y_padding + 2)    x_length = (round((end_x-start_x)/2))    for x &lt;- 0..x_length, do: IO.write "_ "    IO.puts ""    IO.write String.rjust("/  ", y_padding + 2)    for x <- x_range do      if rem(x, x_padding) == 0 do        x        |&gt; Integer.to_string        |> String.ljust(x_padding)        |&gt; IO.write      end    end    IO.puts ""    IO.puts "Generation: #{generation_counter}"    IO.puts "Alive cells: #{alive_counter}"  endend

The board with the bigger visible part looks like this:

   15| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,   14| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,   13| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,   12| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,   11| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,   10| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,    9| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,    8| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,    7| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,    6| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,    5| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,    4| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,    3| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,    2| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,    1| ,,,,,,,,,,OO,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,    0| ,,,,,,,,,,OO,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,   -1| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,   -2| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,   -3| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,   -4| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,   -5| ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,     | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _    /  -10  -5   0    5    10   15   20   25   30   35   40   45   50Generation: 18Alive cells: 4

Last step is to uncomment the GameOfLife.GamePrinter worker in:

# lib/game_of_life.exdefmodule GameOfLife do  use Application  # See http://elixir-lang.org/docs/stable/elixir/Application.html  # for more information on OTP Applications  def start(_type, _args) do    import Supervisor.Spec, warn: false    init_alive_cells = []    children = [      # Define workers and child supervisors to be supervised      # worker(GameOfLife.Worker, [arg1, arg2, arg3]),      supervisor(Task.Supervisor, [[name: GameOfLife.TaskSupervisor]]),      worker(GameOfLife.BoardServer, [init_alive_cells]),      # This line is uncommented now      worker(GameOfLife.GamePrinter, []),    ]    # See http://elixir-lang.org/docs/stable/elixir/Supervisor.html    # for other strategies and supported options    opts = [strategy: :one_for_one, name: GameOfLife.Supervisor]    Supervisor.start_link(children, opts)  endend

Add figure patterns and place them on the board

To play our game of life, it would be great to have an easy way to add figures to the board. There are many commonly known patterns like still lifes, oscillators, and spaceships. You can learn more about them here.

One interesting pattern is the gun. The Gosper Glider Gun is a very popular pattern. Here it is how it looks:

Gosper Glider Gun

When you run game the pattern behaves as you see. The gun is shooting.

Gosper Glider Gun pattern live cycle

Let’s write this pattern down. Imagine you want to put the pattern in a rectangle. Left bottom corner of the rectangle is at {0,0} position.

# lib/game_of_life/patterns/guns.exdefmodule GameOfLife.Patterns.Guns do  @moduledoc """  https://en.wikipedia.org/wiki/Gun_(cellular_automaton)  """  @doc """  https://en.wikipedia.org/wiki/File:Game_of_life_glider_gun.svg  """  def gosper_glider do    [      {24, 8},      {22, 7}, {24, 7},      {12, 6}, {13, 6}, {20, 6}, {21, 6}, {34, 6}, {35, 6},      {11, 5}, {15, 5}, {20, 5}, {21, 5}, {34, 5}, {35, 5},      {0, 4}, {1, 4}, {10, 4}, {16, 4}, {20, 4}, {21, 4},      {0, 3}, {1, 3}, {10, 3}, {14, 3}, {16, 3}, {17, 3}, {22, 3}, {24, 3},      {10, 2}, {16, 2}, {24, 2},      {11, 1}, {15, 1},      {12, 0}, {13, 0},    ]  endend

It would be also useful if we could place the pattern on the board in the position specified by us. Let’s write a pattern converter.

# lib/game_of_life/pattern_converter.exdefmodule GameOfLife.PatternConverter do  @doc """  ## Example      iex> GameOfLife.PatternConverter.transit([{0, 0}, {1, 3}], -1, 2)      [{-1, 2}, {0, 5}]  """  def transit([{x, y} | cells], x_padding, y_padding) do    [{x + x_padding, y + y_padding} | transit(cells, x_padding, y_padding)]  end  def transit([], _x_padding, _y_padding), do: []end

This is the way you can add the Gosper glider pattern to the board with the specified position.

GameOfLife.Patterns.Guns.gosper_glider|> GameOfLife.PatternConverter.transit(-2, -3)|> GameOfLife.BoardServer.add_cells

You can find more patterns in modules here.

Run game across multiple nodes

Now it is time to run our game. The full source code can be found here.

Let’s run the first node where the GameOfLife.BoardServer will be running.

$ iex --sname node1 -S mixErlang/OTP 18 [erts-7.3] [source] [64-bit] [smp:4:4] [async-threads:10] [hipe] [kernel-poll:false] [dtrace]Interactive Elixir (1.2.4) - press Ctrl+C to exit (type h() ENTER for help)16:54:08.554 [info]  Started Elixir.GameOfLife.BoardServer masteriex(node1@Artur)1> GameOfLife.BoardServer.start_game:game_startediex(node1@Artur)2> GameOfLife.GamePrinter.start_printing_board:printing_started

In another terminal window, you can start the second node. We will connect it with the first node.

$ iex --sname node2 -S mixErlang/OTP 18 [erts-7.3] [source] [64-bit] [smp:4:4] [async-threads:10] [hipe] [kernel-poll:false] [dtrace]Interactive Elixir (1.2.4) - press Ctrl+C to exit (type h() ENTER for help)16:55:17.395 [info]  Started Elixir.GameOfLife.BoardServer masteriex(node2@Artur)1> Node.connect :node1@Arturtrue16:55:17.691 [info]  Started Elixir.GameOfLife.BoardServer slaveiex(node2@Artur)2> Node.list[:node1@Artur]iex(node2@Artur)3> Node.self:node2@Arturiex(node2@Artur)4> GameOfLife.Patterns.Guns.gosper_glider |> GameOfLife.BoardServer.add_cells[{24, 8}, {22, 7}, {24, 7}, {12, 6}, {13, 6}, {20, 6}, {21, 6}, {34, 6}, {35, 6}, {11, 5}, {15, 5}, {20, 5}, {21, 5}, {34, 5}, {35, 5}, {0, 4}, {1, 4}, {10, 4}, {16, 4}, {20, 4}, {21, 4}, {0, 3}, {1, 3}, {10, 3}, {14, 3}, {16, 3}, {17, 3}, {22, 3}, {24, 3}, {10, 2}, {16, 2}, {24, 2}, {11, 1}, {15, 1}, {12, 0}, {13, 0}]

Both nodes are executing a calculation to determine a new state for living cells. You can run the game also across different servers in the network like this:

# start node1$ iex --name node1@192.168.0.101 --cookie "token_for_cluster" -S mix# start node2 on another server$ iex --name node2@192.168.0.102 --cookie "token_for_cluster" -S mixiex> Node.connect :"node1@192.168.0.101"true

You already saw how the game works in the demo at the beginning of the article. You can try it on your own machine, just clone the repository.

Summary

Finally, we managed to get to the end. It was a pretty long road but we have a working game, distributed across nodes. We learned how to write GenServer, use Agents, split processes across nodes with TaskSupervisor and connect nodes into the cluster. You also saw examples of tests in Elixir and how to use DocTest.

Hope you found something interesting in the article. Please share your thoughts in the comments.

Nowadays I work on CI parallelisation problem to run tests fast on CI servers. I built Knapsack Pro which splits your Ruby and JavaScript tests on parallel CI nodes to save time on testing. You can check one of my articles about Cypress in JavaScript test suite parallelisation or Heroku CI parallelisation. Let me know how slow or fast your tests are in your Elixir projects — just leave a comment. :) I’d like to add support for CI parallelisation testing into Elixir as well.

Algorithms are often difficult for people to understand. I believe that this is because they are most often programmed or explained in a language that encourages thinking in procedures or instructions which are not intuitive.

Very often the meat of an algorithm (how you solve a particular problem logically without computer coding) looks very simple and understandable when described graphically. Surprisingly, however, it often does not translate well into code written in languages like Python, Java, or C++. Therefore it becomes much more difficult to understand.

In other words, the algorithmic concept doesn’t map directly to how the code should be written and read.

Why are algorithms so difficult to code?

Well, we could blame it on the inner workings of early electro-mechanic computers. The early inventors of some of the most used programming languages today could never get rid of those features. Or perhaps they couldn’t help leaving their fingerprints on their inventions. Once you understand computers that well, there’s no undoing that.

To make matters worse, on top of already micro-managing languages, somebody had to invent an API for better micro-management. They called it object-oriented programming (OOP), and added the concept of classes to programming — but I think modules and functions could handle the same things just fine, thank you very much.

C++ didn’t make C any better, but it did pave a way by inspiring more descendants of OOP. And all together, all these things make abstract algorithmic thinking hard for the aforementioned reasons.

The case study: merge sort

For our discussion, we will use a merge sort algorithm as a specimen. Take a look at the diagram below. If you can count and put together jigsaw puzzles, then you can probably understand how it works in a few minutes.

_By Swfung8 — Own work, CC BY-SA 3.0, [https://commons.wikimedia.org/w/index.php?curid=14961648](https://commons.wikimedia.org/w/index.php?curid=14961648" rel="noopener" target="blank" title=")

The key steps of producing a merge sort are few and simple. In fact, I can explain it using my daughter’s number blocks (helpful to follow these by going back to the animated diagram for reference):

• First, we need to keep subdividing a list of numbers (or letters, or any type of sortable values) by half until we end up with many single-element lists. A list with one element is technically sorted. This is called trivially sorted.
• Then, we create a new empty list in which we could start re-arranging the elements and putting them one by one according to which one is less/smaller than the other.
• Then we need to “merge” each pair of lists back together, effectively reversing the subdivision steps. But this time, at every step of the way, we have to make sure that the smaller element in the pair in question is being put into the empty list first.

For the sake of the argument, we will try to map out the above processes by making each one a subroutine (function in normal speak). The meatiest part of this algorithm is the merging, so let’s start with that first.

def merge(a, b):
    out = []

    while (len(a) > 0 and len(b) > 0): 
        if (a[0] <= b[0]):
            out.append(a[0])
            del a[0]
        else:
            out.append(b[0])
            del b[0]

    while (len(a) > 0):
        out.append(a[0])
        del a[0]
    while (len(b) > 0):
        out.append(b[0])
        del b[0]

    return out

Go on and spend some time looking it over. You might notice that with imperative Python code, it is designed to be spoken out and then understood. It is very understandable in English, but not in logic.

Our first attempt

Here is one attempt (that you could possibly use in a whiteboarding session):

To merge list a and b, we’ll have to first create an empty list named out for clarity (because in Python we can’t be sure it will really be “out” in the end). Then, as long as (or while) both lists are not empty, we’ll keep putting the head of both lists to a fight-off. Whichever is less than or equal to the opponent wins and gets to enter out first. The loser will have to stay and wait there for the new contestant down the line. The rematches continue on until the first while loop breaks.

Now, at some point either a or b will be empty, leaving the other with one or more elements hanging. Without any contestants left in the other list, the two while loops make sure to fast track those poor elements into out so both list are exhausted. Then, when that’s all done, we return out.

And this is the test cases for merge:

assert(merge([1], [2]) == [1, 2])
assert(merge([2], [1]) == [1, 2])
assert(merge([4, 1], [3, 0, 2]) == [3, 0, 2, 4, 1])

I hope at this point it is clear to you why we end up with the result in the last case. If it isn’t, try drawing on a whiteboard or a piece of paper and simulating the explanation.

Divide and Conquer

Now we will carry on with the subdivision part. This process is also known as partitioning or, in somewhat grander language, Divide and Conquer (by the way, the definition in politics is equally interesting).

Gold Medallion of Philip II of Macedonia who is said to have coined the maxim divide et impera (divide and conquer). Bibliothèque nationale de France, Paris

Basically, if anything is hard to conquer or understand, you should break it down until it becomes smaller and more easily understood. Do that until the parts are unbreakable and repeat the process with the rest.

def half(arr):
    mid = len(arr) / 2
    return arr[:mid], arr[mid:]

What the half routine does is find the middle index, slice the input list into roughly equal sublists, and return both as a pair. It only needs to do this once, since the parent function will eventually call it recursively.

Since we have the pieces, now we just need to put them together into a coherent scheme. This is where the water gets murky, because recursions are involved.

Before going into more code, let me explain why recursions and imperative programming languages like Python do not fit together so well. I won’t go into the topic of optimization, because that does not concern today’s discussion and is not as interesting.

One distinct irony here is that, even in a language with iterative looping like Python, it still cannot entirely avoid recursion (it might get away without recursion, but I’m sure that would make it even more bizarre). Recursion is a territory where iterative constructs, such as for and while loops, become utterly useless.

Moreover, recursion is not natural in Python. It does not feel natural and transparent, but rather feels quite half-baked the way its lambda is. An attempt at voicing over recursions in Python would be like, “then we do this recursively and just pray it all works out and hits the base case in the end so it doesn’t spiral into the infinite darkness of stack overflow.” Wow, right?

So here is the mergesort function:

def mergesort(arr):

    if (len(arr) <= 1):
        return arr

    left, right = half(arr)
    L = mergesort(left)
    R = mergesort(right)

    return merge(L, R)

Apparently, this is really clean and easy to read. But it isn’t clear what happens after the call to half , at least semantically. Because of this “non-nativity” to recursion, recursive calls are very opaque and obstructive to educational endeavors.

The only way to visualize this mergesort process is probably to track the changes in the sublists in every step:

input: [0, 3, 1, 3, 2, 6, 5]
A alias for mergesort / half
B alias for merge

## subdividing by half ...

                 A([0, 3, 1, 3, 2, 6, 5])
              A([0, 3, 1])    A([3, 2, 6, 5])
          A([0])  A([3, 1])  A([3, 2])   A([6, 5])
    A([]) A([0]) A([3])  A([1]) A([3]) A([2]) A([6]) A([5]) 

## base case reached, start merging ...

       B([], [0]) B([3], [1]) B([3], [2]) B([6], [5])
          B([0], [1, 3])         B([2, 3], [5, 6])
                B([0, 1, 3], [2, 3, 5, 6])
                 B([0, 1, 2, 3, 3, 5, 6])

output: [0, 1, 2, 3, 3, 5, 6]

On an asymptotic side note, dividing and conquering almost always incurs a logarithmic runtime. When you keep dividing a collection into N sub-collections, whether it contains 10 or 100,000,000 items, the number of steps taken in the latter case increases at the rate of log base N.

For instance, it takes about 3 steps to keep dividing 10 by 2 until it gets as close to 1 as it can (or exactly 3 steps to reach 1 in integer division). But it takes only about 26 steps to do the same and divide 100,000,000 by 2 until you reach 1. This fact can be expressed as follows:

2^3.321928 = 10
2^6.643856 = 100

...

2^26.575425 = 100000000

or 

log base 2 of 100000000 = 26.575425

The takeaway here is that we had to visualize the recursive processes in order to understand the inner workings of the algorithm — even though it looked so trivial in the animated diagram.

Why is there a divide between the conceptual processes of the algorithm itself and the code that instructs the computer to compute such processes?

It’s because in a way, by using imperative languages, we are in fact still mentally enslaved by the machines.

Not quite like this, but you get the point.

Diving deeper into the code

“There’s a difference between knowing the path and walking the path.”
― Morpheus, The Matrix

Programming is hard, we all know that. And understanding programming in a really deep way is even harder on your soul (and your career). But I would argue that, like Morpheus said, sometimes walking the path is all that matters. Being able to see clearly is one of most rewarding things in programming.

In functional programming, the programmer (you) gets the front seat in seeing how data change recursively. This means that you have the ability to decide how the data of a certain form should be transformed to the data of another based on the snapshot of how it looks. This isn’t unlike how we have visualized the mergesort process. Let me give you a preview.

Let’s say you want to create a base case in Python. In it, you want to return the list in question when it has only one element, and an empty list when there’s two elements. So you’d need to write something like this:

if (len(arr) == 1):
    return arr
elif (len(arr) == 2):
    return []

Or to make this worse but more interesting, you could try to access the first element by index 0 and the second element by index 1 and get ready to handle IndexError exception.

In a functional language like Erlang — which is what I’ll be using in this article for its dynamic type system like Python — you more or less would do something like this:

case Arr of
  [_] -> Arr;
  [_,_] -> []
end.

This gives you a clearer view of the state of the data. Once it’s trained enough, it requires much less cognitive power to read and comprehend what the code does than len(arr) . Just keep in mind: a programmer who doesn’t speak English might ask, “what is len?” Then you get distracted by the literal meaning of the function instead of the value of that expression.

However, this comes with a price: you don’t have the luxury of a looping construct. A language like Erlang is recursion-native. Almost every meaningful Erlang program will make use of rigorous recursive function calls. And that’s why it is mapped more closely to the algorithmic concepts which usually consist of recursion.

Let’s try to retrace our steps in producing mergesort, but this time in Erlang, starting with the merge function.

merge([], [], Acc) -> Acc;
merge([], [H | T], Acc) -> [H | merge([], T, Acc)];
merge([H | T], [], Acc) -> [H | merge(T, [], Acc)];
merge([Ha | Ta], [Hb | Tb], Acc) ->
  case Ha =< Hb of
    true  -> [Ha | merge(Ta, [Hb | Tb], Acc)];
    false -> [Hb | merge([Ha | Ta], Tb, Acc)]
  end.

What an abomination! Definitely not an improvement in terms of readability, you think. Yes, Erlang admittedly won’t win any prizes for beautiful language. In fact, many functional languages can look like gibberish to the untrained eyes.

But let’s give it a chance. We will go through each step like we did before, and perhaps in the end some of us will see the light. But before we go on, for those of you who are not familiar with Erlang, these are some points worth noting:

• Each block of merge is considered a function clause of the same function. They are separated by ;. When an expression ends in Erlang, it ends with a period (.). It’s a convention to separate a function into several clauses for different cases. For instance, merge([], [], Acc) -> Acc; clause maps the case where the first two arguments are empty lists to the value of the last argument.
• Arity plays an important role in Erlang. Two functions with the same name and arity are considered the same function. Otherwise, they aren’t. For example, merge/1 and merge/3 (how functions and their arity are addressed in Erlang) are two different functions.
• Erlang uses rigorous pattern matching (This is used in many other functional languages, but especially in Erlang). Since values in pure functional languages are immutable, it is safe to bind variables in a similar shape of data to the existing one with a matched shape. Here is a trivial example:

{X, Y} = {0.5, 0.13}.
X.  %% 0.5
Y.  %% 0.13

[A, B, C | _] = [alice, jane, bob, kent, ollie].
[A, B, C].  %% [alice, jane, bob]

• Note that we will seldom talk about returning values when we work with Erlang functions, because they don’t really “return” anything per se. It maps an input value to a new value. This isn’t the same as outputting or returning it from the function. The function application itself is the value. For instance, if Add(N1, N2) -> N1+N2., Add(1, 2) is 3. There’s no way for it to return anything other than 3, hence we can say it is 3. This is why you could easily do add_one = add(1) and then add_one(2) is 3, add_one(5) is 6, and so on.

For those who are interested, see referential transparency. To make this point clearer and risking redundancy, here is something to think about:

when f(x) is a function with one arity, and the mapping is f(x) ->; x , then it's conclusive that f(1) -&gt; 1, f(2) -> 2, f(3.1416) -> 3.1416, and f("foo") -> "foo".

This may look like a no-brainer, but in an impure function there's no such guaranteed mapping:

a = 1
def add_to_a(b):
return b + a

Now a might as well be anything before add_to_a gets called. Thus in Python, you could write a pure version of the above as:

def add(a, b):
return a + b
or lambda a, b: a + b .

Now it’s time to bumble into the unknown.

That’s what Frank O. Gehry said.

Forging ahead with Erlang

merge([], [], Acc) -> Acc;

The first clause of the merge/3 function means that when the first two arguments are empty lists, map the entire expression to (or “return”) the third argument Acc.

Interestingly, in a pure function, there’s no way of retaining and mutating state outside of itself. We can only work with what we have received as inputs into the function, transform it, then feed the new state into another function’s argument (most often this is another recursive call to itself).

Here, Acc stands for accumulator, which you can think of as a state container. In the case of merge/3, Acc is a list that starts empty. But as the recursive calls get on, it accumulates values from the first two lists using the logic we program (which we will talk about next).

This process of exhausting a value to build up another value is collectively known as reduction. Therefore, in this case it we can conclude that since the first two lists are exhausted (empty), Acc must be ripe for pick up.

merge([], [H | T], Acc) -> [H | merge([], T, Acc)];

The second clause matches the case when the first list is already empty, but there’s still at least one more element in the second list. [H | T] means a list has a head element H which cons onto another list T. In Erlang, a list is a linked list, and the head has a pointer to the rest of the list. So a list of [1, 2, 3, 4] can be thought of as:

%% match A, B, C, and D to 1, 2, 3, and 4, respectively

[A | [B | [C | [D | []]]]] = [1, 2, 3, 4].

In this case, as you can see in the conning example, T can just be an empty tail list. So in this second case, we map it to a value of a new list in which the H element of the second list is conned onto the recursive result of calling merge/3 when T is the second argument.

merge([H | T], [], Acc) -> [H | merge(T, [], Acc)];

The third case is just a flip side of the second case. It matches the case when the first list is not empty, but the second is. This clause maps to a value in a similar pattern, except it calls merge/3 with the tail of the first list as the first argument and keeps the second list empty.

merge([Ha | Ta], [Hb | Tb], Acc) ->
  case Ha =< Hb of
    true  -> [Ha | merge(Ta, [Hb | Tb], Acc)];
    false -> [Hb | merge([Ha | Ta], Tb, Acc)]
  end.

Let’s begin with the meat of merge/3 first. This clause matches the case when the first and second arguments are non-empty lists. In this case, we enter a case … of clause (equivalent to switch case in other languages) to test if the head element of the first list (Ha) is less than or equal to the head element of the second list (Hb).

If that is true, we con Ha onto the resulting list of the next recursive call to merge with the tail list of the previous first list (Ta) as the new first argument. We keep the second and third arguments the same.

These clauses constitute to a single function, merge/3. You can imagine that it could have been a single function clause. We could use complex case … of and/or if conditional plus pattern-matching to weed out each case and map it to the right result. That would have made it more chaotic, when you can easily read each case the function is matching quite nicely on separate lines.

However, things got a little hairy for the subdividing operation, which needs two functions: half/1 and half/3.

half([]) -> {[], []};
half([X]) -> {[X], []};
half([X,Y]) -> {[X], [Y]};
half(L) ->
  Len = length(L),
  half(L, {0, Len}, {[], []}).

half([], _, {Acc1, Acc2}) ->
  {lists:reverse(Acc1), lists:reverse(Acc2)};
half([X], _, {Acc1, Acc2}) ->
  {lists:reverse(Acc1), lists:reverse([X | Acc2])};
half([H|T], {Cnt, Len}, {Acc1, Acc2}) ->
  case Cnt >= (Len div 2) of
      true -> half(T, {Cnt + 1, Len}, {Acc1, [H|Acc2]});
      false -> half(T, {Cnt + 1, Len}, {[H|Acc1], Acc2})
  end.

This is where you’ll miss Python and its destructive nature. In a pure functional language, lists are linked lists. When you work with them, there’s no looking back. There’s no logic that says “I want to divide a list in half, so I’m going to get the middle index, and slice it into two left and right portions.”

If your mind is set in working with linked lists, you’re more along the lines of “I can only go forward through the list, working with a few elements at a time. I need to create two empty lists and keep count of how many items I’ve retrieve from the source list and put into the first one so I know when it’s time to switch to another bucket. All the aforementioned needs to be passed in as arguments in the recursive calls.” Whew!

In other words, cutting a list in half can be compared to chopping a block of cheese with a knife in the middle of it. On the other hand, a functional comparison for doing so is like pouring coffee into two cups equally — you just need to know when it’s time to stop pouring into the first one and move on to the second one.

The half/1 function, although it isn’t really necessary, is there for convenience.

half([]) -> {[], []};
half([X]) -> {[X], []};
half([X,Y]) -> {[X], [Y]};
half(L) ->
  Len = length(L),
  half(L, {0, Len}, {[], []}).

By now, you should get the sense of what each Erlang function clause is doing. The new bracket pairs here represent tuples in Erlang. Yes, we are returning a left and right value pair, like in the Python version. The half/1 function is here to handle simple, explicit base cases which don’t warrant the worthiness of passing in other arguments.

However, take note of the last case when the argument has a list with more than two elements. (Note: those with less than or equal to two elements are already handled by the first three clauses.) It simply computes the following:

• the length of the list L and calls half/3 with L as the first argument
• a pair of counter variables and list’s length, which will be used to signal the switching from list one to list two
• and of course, a pair of empty lists to fill the elements from L in.

half([], _, {Acc1, Acc2}) ->
  {lists:reverse(Acc1), lists:reverse(Acc2)};

half/3 looks like a mess, but only to the untrained eyes. The first clause matches a pattern when the source list is drained. In this case, the second pair of counter and length won’t matter since it’s already the end. We simply know that Acc1 and Acc2 are ripe for yielding. But wait, what’s with the reversing of both?

Appending an element to a linked list is a very slow operation. It runs O(N) times for every append, because it needs to create a new list, copy the existing one onto it, and create a pointer to the new element and assign it to the last element. It’s like redoing the whole list. Couple this with recursions and you are bound for disaster.

The only good way to add something to a linked list is to prepend it at the head. Then all it needs to do is create a memory for that new value and give it a reference to the head of the linked list. A simple O(1) operation. So even though we could concatenate lists using ++ like [1, 2, 3] ++ [4], we rarely want to do it this way, especially with recursions.

The technique here is to reverse the source list first, then con an element onto it like [4 | [3, 2, 1]] , and reverse them again to get the right result. This may sound terrible, but reversing a list and reversing it back is an O(2N) operation, which is O(N). But in between, conning elements onto the list takes only O(1), so it basically costs no extra runtime.

half([H|T], {Cnt, Len}, {Acc1, Acc2}) ->
  case Cnt >= (Len div 2) of
      true -> half(T, {Cnt + 1, Len}, {Acc1, [H|Acc2]});
      false -> half(T, {Cnt + 1, Len}, {[H|Acc1], Acc2})
  end.

Getting back to half/3. The second clause, the meat of the function, does exactly the same thing as the coffee pouring metaphor we visited earlier. Since the source list is still “emitting” data, we want to keep track of the time we have been pouring values from it into the first coffee cup Acc1.

Remember that in half/1’s last clause, we calculated the length of the original list? That is the Len variable here, and it stays the same throughout all the calls. It’s there so that we can compare Cnt counter to it divided by 2 to see if we have come to the middle of the source list and should switch to filling up Acc2 . That is where the case … of comes in.

Now, let’s put them all together in mergesort/1 . This should be as simple as the Python version, and can be easily compared.

mergesort([A]) -> [A];
mergesort([A, B]) ->
  case A =< B of
      true -> [A,B];
      false -> [B,A]
  end;
mergesort(L) ->
  {Left, Right} = half(L),
  merge(mergesort(Left), mergesort(Right), []).

That’s it!

At this point, either you think this is a novel and useful way of thinking about a problem, or you find it just plain confusing. But I hope you got something out of this programming approach that helps shine new light on how we can think about algorithms.

Update

The Python implementation of merge function isn’t efficient because in each while loop the first element in the list is removed. Although this is a common pattern in functional languages like Erlang, in Python it is very costly to remove or insert an element anywhere other than the last position because unlike a list in Erlang which is a linked list which is very efficient to remove or add element at the head of the list, Python list behaves like an array which has to reposition all other elements when one is removed or added, incurring a O(n) runtime.

The better way is to sacrifice little space to define a counter variable for each list which can be incremented and used to access the current element of the source list without the need to remove the top-most element at all.

def merge(a, b):
    out = []

    ai = 0
    bi = 0

    while (ai <= len(a) - 1 and bi <= len(b) - 1): 
        if (a[ai] <= b[bi]):
            out.append(a[ai])
            ai += 1
        else:
            out.append(b[bi])            
            bi += 1

    while (ai <= len(a) - 1):
        out.append(a[ai])
        ai += 1

    while (bi <= len(b) - 1):
        out.append(b[bi])
        bi += 1

    return out

Elixir makes programmers better at their work, and it makes their work better

About a year ago, I decided to pursue the chance to work with Elixir full time as lead engineer at CityBase. Since I began using the programming language in 2014, my goal has been to use, grow, and learn more from Elixir.

CityBase attracted me for other reasons, too. I’ve always been curious about making complex systems work better. With government technology, we have the challenge to make some of the most complex systems work more effectively for people on a massive scale, to massive impact.

These objectives — growing Elixir and coding for large-scale impact — are in my opinion the same. I really believe that today, reliability, concurrency, and fault tolerance are foundational qualities that most applications should be built on. Elixir can help with that based on a battle-proven list of applications and concepts.

_(Photo: [Unsplash](https://unsplash.com/photos/w7ZyuGYNpRQ?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText" rel="noopener" target="_blank" title="">Kevin, <a href="https://unsplash.com/?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText" rel="noopener" target="blank" title="))

A New Language with Tested Roots

Elixir is a new language created in 2011. It’s built with the principles of Erlang, a system developed in 1986 for the telecom industry. Erlang is the reason your phone is never temporarily shut down for maintenance. It’s responsible for hardware flexibility and scalability, so you can replace a phone and have your account work the same, and add new phone lines without affecting performance.

Even though Elixir is relatively young, it relies on Erlang’s proven virtual machine (VM), called BEAM, and its principles of high availability, adaptability, and scalability. These features are exceptionally important in govtech applications, where the fundamental services delivered by technology must be available to everyone.

The Programmer’s Programing Language

Engineers like me are excited to work with Elixir because it helps us be better at our jobs. To code with Elixir, developers need to be in tune with overall business objectives, and code with the future flexibility in mind.

It includes tools that encourage programmers to plan around what can go wrong, and focus on getting as close as possible to the ideal outcome for the end user.

Having programmers who understand the desired big-picture outcomes can be a game changer.

If you ask someone to write code that performs a certain function, they’ll write that code. But if you ask them to write code that leads to an experience or solves a problem, they may think of a solution you never considered — and foresee problems you didn’t know existed.

Elixir encourages this kind of big-picture thinking in its DNA. A shared characteristic of Elixir and Erlang is that they are holistic programming languages. You could easily use Elixir to develop just one service, but it is optimized for developing large systems of many services.

A Language That’s Fault-Tolerant

Like death and taxes, another certainty in life is that things will go wrong.

Elixir has native fault tolerance for the two major types of programming errors.

Error Type 1

The rarest issues are usually discovered in production and are by definition harder to test for. For instance, connectivity (when a service goes down or is taking longer than expected) between a third-party service or a system resource, such as a database.

To be fault-tolerant to these issues, your system must always be available to customers by using at least two servers. This is to address hardware issues, network problems, or other errors that live outside your program.

Elixir runs on Erlang’s BEAM VM, which is configured as a mini OS on top of the server OS. The VM is responsible for the communication between servers and nodes. A node will be notified when another node is down, and the system will act in response.

Error Type 2

Issues associated with data are easier to test and can be reproduced locally. For example, if a function that does any math calculation receives a string instead of a number, that function will fail.

For a program to be fault-tolerant here, your system must be able to “heal” itself during errors stemming from logic bugs, wrong input data, and other internal failures.

As Elixir is a compiled language, any mistakes in the code prevent the application from starting. This ensures that running applications at least have a valid starting state.

For this to work smoothly, the Erlang VM uses something called the supervision principle, which goes like this:

• Processes are structured based on the idea that there are both “worker” and “supervisor” modules built into a given program.
• Workers perform computations, and supervisors monitor workers.
• If something goes wrong, a supervisor can restart a worker to its initial valid state.

The supervision principle is associated with process isolation, when one module can run in one isolated process. This ensures that errors in one module will not affect other parts of the application, and you can restart that module in isolation as well.

A Language That’s Modular and Built to Scale

Elixir is a modular language, meaning that you can modify self-contained parts without worrying about impacting other, unrelated parts. Microservices function concurrently. These code-based actions all play roles in the greater program you’ve created, but tasks are distributed so that they are not dependent on one another to work. This reinforces the benefits of failing fast — you take one faulty player out, and the game still continues.

This also becomes crucial as a codebase grows: in non-modular systems, it’s not always clear when one part impacts others — or which other parts it might impact. This means that even the smallest change requires that you test everything to ensure that the change didn’t break anything. This makes for a daunting amount of work, which means projects move slowly and require lots of people.

It also means that training new developers is difficult and time-consuming, as they must familiarize themselves with a complex code legacy in order to effectively expand it.

With Elixir, developers focus on the future, and ensure they’re coding for new or evolving goals, rather than a previous vision that’s baked into overly complex code.

Beyond its modularity, Elixir is also highly scalable. The language enables you to start building an application running only one or two servers and to add more as needed. Together, the servers function as part of a cluster in a distributed system to achieve high availability and scalability.

Within that cluster, servers communicate using an Erlang-based protocol, rather than having to implement or use any application protocol like HTTP, and pick a data serialization/deserialization option like JSON or Protocol Buffers. That means you don’t need to implement anything to pass data between services in different servers/nodes. This is huge in terms of complexity of logic for communication.

A Language That Has No Niche

Obviously, I’m a fan of Elixir. It’s got a lot going for it, from its proven infrastructure to its scalability. But maybe the coolest thing about this language is that it’s industry agnostic. Already, it’s been adopted by a range of companies, for a variety of purposes: WhatsApp, Bleacher Report, Netflix, Pinterest, Postmates, and a handful of .gov sites all use Elixir or Erlang.

This is a plus for several reasons: first, it means that the language is likely to continue to grow in popularity as companies recognize the benefits it can offer. That, in turn, means that developers will continue to learn it, which means there’s not likely to be a shortage of developers who know Elixir. Companies of all sizes should be able to find developers at all levels to work with Elixir.

Given the power this language has to improve user experience, minimize downtime, and make life easier for dev teams, these are indicators everyone should be cheering — especially those of us in engineering and programming fields.

For those of us in govtech, Elixir is especially promising, as it embodies the kind of resilience and long-term focus essential to making governments function better for everyone.

• • •

By Pedro Assumpcao, Lead Software Engineer at CityBase

Calculating collision probabilities of hashed values

Say you built an API that generates public keys, and these keys all need to be unique and hard to guess. The most common way to do this is to use a hash function to generate a random series of numbers and letters. A typical hash looks something like the text below.

AFGG2piXh0ht6dmXUxqv4nA1PU120r0yMAQhuc13i8

A question that often comes up is, “How long does my hash need to be in order to ensure uniqueness?” Most people assume this is a difficult calculation. So they default to some very large number, like a 50-digit hash. The equation to approximate collision probability is actually quite simple.

How do I calculate?

Let’s assume you’re using a good cryptographic algorithm (i.e. not JavaScript’s Math.random). Every language has a decent crypto package for generating random hashes. With Phoenix, you can use the Erlang :crypto package.

There are only two pieces of information you need to do the calculation:

1. How many possible unique hash values can you create with the given inputs? We’ll assign this to the variable N.
2. How many values could you possibly need to generate in the lifetime of your project? We’ll assign this to the variable k.

To calculate the first value, add up all the possible characters that can go into your hash. Raise it to the power of the length of your hash.

So for example, if your hash value contains numbers, lowercase, and uppercase letters, that adds up to 62 total characters (10 + 26 + 26) that we can use. If we are generating a hash of only 3 characters in length, then:

N = 62³ = 238,328 possible values

To calculate the second value, you need to think about what your app does and make some reasonable assumptions.

Let’s say your app is generating a hash to assign to each of your customers. Let’s also say that your app is very niche. The absolute-best case scenario, your app will have 1000 customers over its lifetime. Then, for safety’s sake, we’ll multiply that by 10. We assume that you may need to generate 10,000 values over the course of your app’s life.

k = 10,000 upper bound for possible values that need to be created

So now we need to calculate. There are many algorithms we can use. We’ll use one of the simple approximations, where e is the mathematical constant (the base of the natural log), and k and N are the same values as above.

The base equation gives us the probability that all values are unique. Then we subtract that result from 1 to get the odds that you have a collision. If you don’t feel like writing your own equation, I’ve provided one below written in JavaScript.

So in the example above, calculate(N, k) yields a probability of approximately 100% that you will have a collision. So for that use case, you should use a hash of more than 3 characters in length.

Now, if we were to take that same example but change the length of our hash from 3 to 5, we would get an N that is much larger (exponentials are good like that).

N = 62⁵ = ~900,000,000

Assuming the same value k, our new probability of a collision is down to only 5.4%. What if we bumped that from 5 characters to 10?

N = 62¹⁰ = ~800,000,000,000,000,000

Yes, that’s ~800 quintillion unique hashes. Which bring your odds of a collision down to 0.000000000062%. This is about a 1-in-50-billion chance that you have a conflict. And that’s with a hash of 10 digits — something like: BwQ1W6soXk.

For another example, let’s say you’re a data processing company that deals with lots of transactions. We’ll say you deal with 1 million processes per second and you need to generate a hash for each of them. Let’s also say that you think this company could run for the next 100 years.

_k = ~_3,000,000,000,000,000

That comes out to about 3 quadrillion hashes that you need made that all need to be unique. That’s a lot of data! But even with this extremely large number to work with, you only need a 21-digit hash to ensure a 1-in-10-million chance of collision over the lifetime of the project.

So the next time you’re worried about the length of your hash in ensuring uniqueness, know that you don’t need one as long as you think you do. Plus, you can do the calculation yourself without much effort.

Sam Corcos is the lead developer and co-founder of Sightline Maps, the most intuitive platform for 3D printing topographical maps, as well as LearnPhoenix.io, an intermediate-advanced tutorial site for building scalable production apps with Phoenix and React.