Elixir Concurrency Primitives and GenServer

Using Basic Arithmetic on Fractions

Elixir not only provides the powerful concurrency primitives it inherits from Erlang, but also offers macros to eliminate boiler-plate code from OTP behaviours. In this article, we’re going to discover how a problem involving both synchronous and asynchronous requests can be implemented in a separate BEAM process, and how this implementation can be simplified using GenServer.

Working with Fractions

Those programming techniques shall be demonstrated by implementing basic arithmetic operations on fractions. A fraction has a dividend and a divisor, which express an arithmetic operation: division. However, instead of dividing those two numbers, which could lead to imprecise floating point results, the dividend and divisor shall be retained during calculation. However, the fraction shall be canceled when retrieving the result of a (possibly long) chain of arithmetic operations.

The following operations shall be implemented:

• Addition: Two fractions (left and right) are added up by first multiplying the left dividend with the right divisor, second multiplying the right dividend with the left divisor, third adding up the two resulting dividends, resulting in the final divisor; and fourth multiplying the two divisors, resulting in the final divisor.
• Subtraction: The same as addition, but the dividends are subtracted rather than added up.
• Multiplication: The two dividends are multiplied, resulting in the final dividend; same with the divisors.
• Division: The same as multiplication, but dividend and divisor of the right fraction are swapped before.

Cancel Fractions

Since such operations (e.g. 3/4 + 7/8) produce results that could be simplified (52/32 to 13/8), cancellation shall also be implemented. This can be done by computing the greatest common divider (GCD) of dividend and divisor, and then dividing both dividend and divisor by their GCD.

Finding the GCD can be done both easily and efficiently using Euclid’s algorithm: Subtract the smaller from the bigger number, and continue doing so with the result and the smaller of the two numbers, until they are equal, e.g.:

Implementation

First, a new mix project shall be created:

mix new fractions

In lib/fraction.ex, a module for the fraction computations described above shall be implemented:

defmodule Fraction do
  defstruct dividend: 0, divisor: 0

  # additional code described below
end

The module defines a struct consisting of a dividend and a divisor. The former has the default value 0, the latter the default value 1, so that a default fraction has the value 0 rather than being undefined (due to a division by zero).

The four basic arithmetic operations are implemented within that module, as described above:

def add(this, that) do
  %Fraction{
    dividend: this.dividend * that.divisor + that.dividend * this.divisor,
    divisor: this.divisor * that.divisor
  }
end

def subtract(this, that) do
  %Fraction{
    dividend: this.dividend * that.divisor - that.dividend * this.divisor,
    divisor: this.divisor * that.divisor
  }
end

def multiply(this, that) do
  %Fraction{
    dividend: this.dividend * that.dividend,
    divisor: this.divisor * that.divisor
  }
end

def divide(this, that) do
  %Fraction{
    dividend: this.dividend * that.divisor,
    divisor: this.divisor * that.dividend
  }
end

Fractions are simplified using the cancel operation described above:

def cancel(fraction) do
  gcd = greatest_common_divisor(fraction.dividend, fraction.divisor)
  %Fraction{dividend: div(fraction.dividend, gcd), divisor: div(fraction.divisor, gcd)}
end

The GCD is found using the following function, implementing Euclid’s algorithm:

def greatest_common_divisor(a, b) when a > 0 and b > 0 do
  cond do
    a > b -> greatest_common_divisor(a - b, b)
    a < b -> greatest_common_divisor(a, b - a)
    a == b -> a
  end
end

This module can be used interactively as follows (output reduced to its essence):

$ iex -S mix
iex(1)> a = %Fraction{dividend: 3, divisor: 4}
iex(2)> b = %Fraction{dividend: 2, divisor: 3}
iex(3)> c = Fraction.add(a, b)
%Fraction{dividend: 17, divisor: 12}
iex(4)> d = Fraction.subtract(c, %Fraction{dividend: 1, divisor: 12})
%Fraction{dividend: 192, divisor: 144}
iex(5)> Fraction.cancel(d)
%Fraction{dividend: 4, divisor: 3}

So far, all computations take place synchronously, i.e. no concurrent execution is taking place.

Concurrent Implementation Using Primitives

Performing arithmetic operations on fractions is not a typical concurrency task. However, the given implementation that allows for performing a set of computation, and only performs cancellation on demand, is a good candidate for a asynchronous mode of operation:

1. A sequence of arithmetic operations is performed on a fraction asynchronously. No result is retrieved yet.
2. The result of the submitted operations is requested and canceled synchronously. The result is retrieved now.

This model of computation is a perfect fit for Elixir’s concurrency model using light-weight processes and message passing.

Such a process is implemented in lib/fraction_process.ex:

defmodule FractionProcess do
  # additional code described below
end

Its start function spawns a new process:

def start(init \\ %Fraction{dividend: 0, divisor: 1}) do
  spawn(fn -> run(init) end)
end

An initial fraction can be supplied optionally, otherwise 0/1 is assumed as a default start value. The spawn function runs the message processing loop in a new process, which is defined in the private tail-recursive run function as follows:

defp run(state) do
  state =
    receive do
      {:add, fraction} ->
        Fraction.add(state, fraction)

      {:subtract, fraction} ->
        Fraction.subtract(state, fraction)

      {:multiply, fraction} ->
        Fraction.multiply(state, fraction)

      {:divide, fraction} ->
        Fraction.divide(state, fraction)

      {:compute, caller} ->
        state = Fraction.cancel(state)
        send(caller, {:result, state})
        state
    end

  run(state)
end

The initial fraction is passed as the state argument. This is crucial: the state is advanced by invoking the run function again with its updated value. The recursive call to run with the new state must be made as a tail-call, i.e. be the last thing the function does, in order to allow for tail-call optimization, which prevents a stack overflow.

Two kinds of messages, both defined as two-element tuples, are supported:

1. Arithmetic operations, with the operation defined as an atom (:add, :subtract, etc.) as the first element, and the second operand of the operation as the second element. (The first operand is given as the state.)
2. Result retrieval, with the :compute atom as the first tuple element, and a reference to the caller (its process ID or short PID).

The messages are processed in a serializing message loop defined using the receive keyword. Pattern matching is performed on the incoming message, which is either delegated to an arithmetic operation of the Fraction module defined above, or, if the :compute message is retrieved, the current fraction, given as the state argument, is canceled and sent as a result to the calling process. Since this result could be intermediate, and further calculations may be performed on the resulting fraction, the state is also advanced.

A client can send such messages to a FractionProcess by using the send primitive with the according message format. However, it is less error-prone to offer interface functions that handle the messaging details, as the following functions do:

def add(pid, fraction), do: send(pid, {:add, fraction})
def subtract(pid, fraction), do: send(pid, {:subtract, fraction})
def multiply(pid, fraction), do: send(pid, {:multiply, fraction})
def divide(pid, fraction), do: send(pid, {:divide, fraction})

def compute(pid) do
  send(pid, {:compute, self()})

  receive do
    {:result, result} -> result
  end
end

The first four functions simply encapsulate the message sending by wrapping the given fraction into a proper message tuple.

The last function, compute, sends the :compute message to the given PID, with a reference of the caller’s PID (retrieved by the self primitive), so that the FractionProcess has a proper reference to send its answer to. Having sent this message, a response is awaited immediately using another receive block, which simply returns the result as it’s coming in.

The functions for the arithmetic operations, however, do not wait for a response, but just send a request to the target process in a fire and forget manner.

The FractionProcess can be used (with the same computations as in the above example) as follows:

$ iex -S mix
iex(1)> a = %Fraction{dividend: 3, divisor: 4}
iex(2)> b = %Fraction{dividend: 2, divisor: 3}
iex(3)> pid = FractionProcess.start(a)
iex(4)> FractionProcess.add(pid, b)
iex(5)> FractionProcess.subtract(p, %Fraction{dividend: 1, divisor: 12})
iex(6)> FractionProcess.compute(pid)
%Fraction{dividend: 4, divisor: 3}

Notice how the intermediate result is not carried around in an explicit variable, but lingers within the FractionProcess being referred to as pid. Also, the add and subtract function calls do not yield an intermediary result, which is only returned when compute is called. All the computations are performed concurrently, i.e. on another CPU core, if the machine has more than one. No memory is shared between the two processes, so no race-conditions can occur.

Concurrent Re-Implementation Using GenServer

This kind of concurrent implementation, combining synchronous and asynchronous operations, is very common in Elixir. Its underlying Erlang/OTP framework defines a set of behaviours, and the mode of computation described above is a perfect fit for the GenServer (as in “generic server”) behaviour.

All the messaging, advancement of the state, and implementation of both synchronous and asynchronous requests are handled by generic, pre-defined code provided by the GenServer module.

This is demonstrated in a module called FractionServer in lib/fraction_server.ex:

defmodule FractionServer do
  use GenServer

  # additional code described below
end

The start operation delegates the initialization of the state to GenServer.start:

def start(fraction \\ %Fraction{dividend: 0, divisor: 1}) do
  GenServer.start(FractionServer, fraction)
end

A generic server process provides various callback functions that are plugged into the server lifecycle (initialization, message loop, termination). The state is initialized using the init callback function, which is defined as follows:

@impl GenServer
def init(fraction) do
  {:ok, fraction}
end

Notice that the function is annotated using @impl GenServer, which allows for certain compile-time checks concerning the function’s name and signature. Also, the result of the initialization process is wrapped in a tuple, here with the :ok atom as its first element, signalling that initialization worked as intended.

Instead of implementing the entire message loop, only a couple of handler functions need to be implemented—one function per message format:

@impl GenServer
def handle_cast({:add, fraction}, state) do
  {:noreply, Fraction.add(state, fraction)}
end

@impl GenServer
def handle_cast({:subtract, fraction}, state) do
  {:noreply, Fraction.subtract(state, fraction)}
end

@impl GenServer
def handle_cast({:multiply, fraction}, state) do
  {:noreply, Fraction.multiply(state, fraction)}
end

@impl GenServer
def handle_cast({:divide, fraction}, state) do
  {:noreply, Fraction.divide(state, fraction)}
end

@impl GenServer
def handle_call({:compute}, _, state) do
  state = Fraction.cancel(state)
  {:reply, state, state}
end

All those functions are annotated using @impl GenServer again. There are four asynchronous function clauses with the name handle_cast for the arithmetic operations. They all expect a message as their first argument, and the current state of the process (i.e. the fraction) as the second one.

The pattern matching is performed on the function argument rather than using the receive construct from before. The functions return the state after the computation in a two-element tuple, starting with the :noreply atom.

The synchronous handle_call function expects three arguments: the incoming message, the sender PID (which is discarded here), and the current state of the process. It returns a three-element tuple starting with the :reply atom and containing both the result and next state—which are equivalent in this case.

The module also defines the interface functions known from FractionProcess, which are implemented in a slightly different way:

def add(pid, fraction), do: GenServer.cast(pid, {:add, fraction})
def subtract(pid, fraction), do: GenServer.cast(pid, {:subtract, fraction})
def multiply(pid, fraction), do: GenServer.cast(pid, {:multiply, fraction})
def divide(pid, fraction), do: GenServer.cast(pid, {:divide, fraction})

def compute(pid), do: GenServer.call(pid, {:compute})

They do not send messages on their own, but use the GenServer functions cast and call, which sends the message to the proper PID to be processed in the according callback function defined further above.

Using the FractionServer based on GenServer is slightly different than using the custom-made FractionProcess from before:

$ iex -S mix
iex(1)> a = %Fraction{dividend: 3, divisor: 4}
iex(2)> b = %Fraction{dividend: 2, divisor: 3}
iex(3)> {:ok, pid} = FractionServer.start(a)
iex(4)> FractionServer.add(pid, b)
iex(5)> FractionServer.subtract(pid, %Fraction{dividend: 1, divisor: 12})
iex(6)> FractionServer.compute(pid)
%Fraction{dividend: 4, divisor: 3}

Notice that FractionServer.start returns a two-element tuple {:ok, pid} instead of just the PID; so pattern matching is needed on the client side. Otherwise, both FractionServer and FractionProcess behave the same. However, GenServer also implementes mechanism for timeouts and the like, which aren’t an issue here.

But most importantly, the code of FractionServer is way less involved than implementing the message loop and state advancement manually, as it was done in FractionProcess.

Conclusion

The Fraction module defines a data structure to express fractions using a dividend and a divisor, as well as basic arithmetic operations (add, subtract, multiply, and divide) and an operation for cancelling fractions, i.e. reducing them to their simplest form.

The module has been wrapped for concurrent usage: first using a manually implemented FractionProcess, and then using the GenServer behaviour as FractionServer.

Even though the issue at hand is not a typical text-book concurrency problem, implementing its functionality as a set of asynchronous operations and a single synchronous operation demonstrates how processes are used in the Erlang/Elixir ecosystem: Not only to express concurrent (and potentially: parallel) computations, but also to handle state in a safe manner: Using light-weight BEAM processes rather than objects as a means of encapsulation, as most main-stream languages do.

The example code can be found on github.com/patrickbucher/elixir-basics.