Forem: Jeff Kreeftmeijer

How To Reduce Reductions in Elixir

Jeff Kreeftmeijer — Thu, 05 Oct 2023 10:47:17 +0000

In this article, we'll show how you can use Elixir's profile.eprof mix task to evaluate and improve code performance in your Elixir application. You'll see how we used the profiling mix task to lower reductions in our instrument/3 function and custom instrumentation functionality, both key parts of our Elixir integration.

Our Key Components

Before we explain how we used Elixir's profile.eprof mix task to improve our instrument function's performance, let's take a moment to understand what profile.eprof does.

Elixir's `profile.eprof` Mix Task

Elixir's profile.eprof mix task evaluates a piece of code with the eprof profiling tool enabled. When the code runs, it outputs a time profile report, which shows the number of calls to each function and the amount of time spent in each function.

AppSignal's `instrument` Function

In its most basic form, the instrument/3 function wraps a piece of code to gain performance insights:

Appsignal.instrument("slow", fn ->
  :timer.sleep(1000)
end)

The example above creates a new trace (named "slow" when there's no current trace) or a child span in a trace that's already running.

With AppSignal, we can save and query our application's performance samples to quickly find similar samples or retrieve older samples when debugging issues.

Profiling our `instrument` Function

To look into the Appsignal.Instrumentation.instrument/3 function, we evaluated the following code snippet through the eprof task:

mix profile.eprof -e "(1..1_000) |> Enum.each(fn _ -> Appsignal.Instrumentation.instrument(\"name\", \"category\", fn -> :ok end) end)"

For convenience, this is a formatted version of the executed code, which calls the instrument/3 function a thousand times to eliminate any outliers and gauge the average performance of functions called by the instrument function:

(1..1_000)
|> Enum.each(fn _ ->
  Appsignal.Instrumentation.instrument(\"name\", \"category\", fn -> :ok end)
end)

Interpreting Profiling Data

Running the profiler produced the following report:

# This report sample has been redacted for brevity

Profile results of #PID<0.315.0>
#                                                        CALLS     %  TIME µS/CALL
Total                                                    11701 100.0 53586    0.46
:application.get_env/2                                    4000  0.90   484    0.12
:ets.lookup/2                                             6000  7.62  4083    0.68
Appsignal.Nif._create_root_span/1                         1000 13.82  7404    7.40
Appsignal.Nif._close_span/1                               1000 29.76 15947   15.95

The report shows all function calls executed as a result of calling instrument/3, with the rightmost column showing the time per call in microseconds.

We then interpreted the profiling data for our instrument function to understand how our function performed and find places in our code to reduce the number of functions called by our instrument function.

Looking for Reductions

Looking back at our report, we can see that the Appsignal.Nif._close_span/1 and Appsignal.Nif._create_root_span/1 functions took the most time, at roughly 16 and 7 microseconds per call, respectively.

Both functions were called 1,000 times, which made sense because that equated to the number of started and stopped spans. Although some performance gains might be had here, we skipped these function calls, as they were called a reasonable amount of times.

One place above these is :ets.lookup/2, which only took 0.68 microseconds per call, but was called 6,000 times, or $6n$ (where $n$ is the number of calls to the instrument/3 function).

  def instrument(name, category, fun) do
    instrument(fn span ->
      _ =
        span
        |> @span.set_name(name)
        |> @span.set_attribute("appsignal:category", category)

      call_with_optional_argument(fun, span)
    end)
  end

Investigating the instrument/3 function revealed that the Span.set_name/1 function called :ets.lookup/2 twice.

Reducing Calls

Although AppSignal uses ets internally to store the currently open spans, from checking the configuration, it turned out that the lookups in the set_name/1 function actually happened.

Internally, the integration checked to see if set_name/1 was active before calling Span.set_name/2, the function used to set the span name.

def set_name(%Span{reference: reference} = span, name)
    when is_reference(reference) and is_binary(name) do
  if Config.active?() do
    :ok = @nif.set_span_name(reference, name)
    span
  end
end

However, this call wasn't needed, as calling this function with a nil value instead of a span is a no-op. When the integration isn't active, nils are passed around instead of spans so this extra check could be safely removed.

After making these changes to our code and re-running our profiler, we saw a reduction in the number of calls by $2n$, leaving $4n$ calls to the :ets.lookup/2 function:

:ets.lookup/2                                             4000  5.06  2458    0.61
Appsignal.Nif._create_root_span/1                         1000 16.30  7922    7.92
Appsignal.Nif._close_span/1                               1000 32.91 16001   16.00

Another lookup was caused by a duplicate call to Application.get_env/1. Since the application environment is stored in ets as well, each get_env/1 call also does a lookup.

Previously, the environment was checked twice, in both the active?/0 and valid?/0 functions. If either of these is false, the integration is disabled. The implementation looked like this:

  def active? do
    :appsignal
    |> Application.get_env(:config, @default_config)
    |> do_active?
  end

  defp do_active?(%{active: true}), do: valid?()
  defp do_active?(_), do: false
  def valid? do
    do_valid?(Application.get_env(:appsignal, :config)[:push_api_key])
  end

  defp do_valid?(push_api_key) when is_binary(push_api_key) do
    !empty?(String.trim(push_api_key))
  end

  defp do_valid?(_push_api_key), do: false

Exposing valid?/1 (which takes a configuration and only tests if the push API key is present) saved a call to Application.get_env/2, which internally called another ets lookup:

  def active? do
    :appsignal
    |> Application.get_env(:config, @default_config)
    |> active?
  end

  defp active?(%{active: true} = config) do
    valid?(config)
  end

  defp active?(_config), do: false

  def valid? do
    :appsignal
    |> Application.get_env(:config)
    |> valid?
  end

  defp valid?(%{push_api_key: key}) when is_binary(key) do
    !(key
      |> String.trim()
      |> empty?())
  end

  defp valid?(_config), do: false

Having re-run the profiler, we saw the number of calls to :ets.lookup/2 was $3n$:

:erlang.whereis/1                                         4000  1.88   757    0.19
Appsignal.Nif._set_span_attribute_string/3                1000  1.90   766    0.77
Appsignal.Tracer.create_span/3                            1000  2.02   813    0.81
Process.whereis/1                                         4000  2.17   875    0.22
Appsignal.Tracer.running?/0                               4000  2.30   926    0.23
:ets.lookup/2                                             3001  3.91  1576    0.53
Appsignal.Nif._create_root_span/1                         1000 17.12  6903    6.90
Appsignal.Nif._close_span/1                               1000 33.97 13696   13.70

There was one call to try and find the parent, another call to see if the PID at the time was ignored, and a last call to check if the integration was active at that time.

It might be possible to remove the check that sees if the integration is active, which happens before starting every span. However, this particular update only consists of performance enhancements, so changes in functionality aren't included.

Removing Unnecessary Calls

A line above the :ets.lookup/2 function is Appsignal.Tracer.running?/0, a function that's called to ensure ets is running before executing lookups, inserts, and deletions.

Because ets produces an ArgumentError when it's not active, a check was called to ensure the registry was running every time the table was evaluated.

For example, this included a function to find the current span for a process named Tracer.lookup/1:

def lookup(pid) do
  if running?(), do: :ets.lookup(@table, pid)
end

This patch removed those checks and added error handling around each function that called ets, removing Appsignal.Tracer.running?/0 completely:

def lookup(pid) do
  try do
    :ets.lookup(@table, pid)
  rescue
    ArgumentError -> []
  end
end

The Final Profile

To summarise, we utilized profile.eprof to locate and reduce $7n$ unnecessary calls, including:

Calls to :ets.lookup/2 from $6n$ to $3n$
All $4n$ calls to Appsignal.Tracer.running

This resulted in a small but significant improvement in our instrument function's performance.

Sample AppSignal's Performance Monitoring

The ability to save and search performance samples is just one of AppSignal's many developer-driven features designed to help you get the most out of your application's metrics. Developers say they also love us thanks to our:

Intuitive interface that is easy to navigate.
Simple and predictable pricing.
Developer-to-developer support.

If you experience any issues when using AppSignal for Elixir, our support team is on hand to help! And remember, if you're new to AppSignal, we'll welcome you onboard with an exceptionally delicious shipment of stroopwafels 🍪 😋

Emacs package management with straight.el and use-package

Jeff Kreeftmeijer — Mon, 16 Aug 2021 16:37:12 +0000

Emacs includes a package manager named package.el, which installs packages from the official Emacs Lisp Package Archive, named GNU ELPA. GNU ELPA hosts a selection of packages, but most are available on MELPA, which is an unofficial package archive that implements the ELPA specification. To use MELPA, it has to be installed by adding it to the list of package.el package archives.

The built-in package manager installs packages through the package-install function. For example, to install the "evil-commentary" package from MELPA, call package-install inside Emacs:

M-x package-install <RET> evil-commentary <RET>

Straight.el

Straight.el is an alternative package manager that installs packages through Git checkouts instead of downloading tarballs from one of the package archives. Doing so allows installing forked packages, altering local package checkouts, and locking packages to exact versions for reproducable setups.

Installation

The Getting started section in the straight.el README provides the bootstrap code to place inside ~/.emacs.d/init.el in order to install it:

;; Install straight.el
(defvar bootstrap-version)
(let ((bootstrap-file
       (expand-file-name "straight/repos/straight.el/bootstrap.el" user-emacs-directory))
      (bootstrap-version 5))
  (unless (file-exists-p bootstrap-file)
    (with-current-buffer
    (url-retrieve-synchronously
     "https://raw.githubusercontent.com/raxod502/straight.el/develop/install.el"
     'silent 'inhibit-cookies)
      (goto-char (point-max))
      (eval-print-last-sexp)))
  (load bootstrap-file nil 'nomessage))

Straight.el uses package archives like GNU ELPA as registries to find the linked repositories to clone from. Since these are checked automatically, there's no need to add them to the list of package archives.

While package.el loads all installed packages on startup, straight.el only loads packages that are referenced in the init file. This allows for installing packages temporarily without slowing down Emacs' startup time on subsequent startups.

To create a truly reproducable setup, disable package.el in favor of straight.el by turning off package-enable-at-startup. Because this step needs to happen before package.el gets a chance to load packages, it this configuration needs to be set in the early init file:

;; Disable package.el in favor of straight.el
(setq package-enable-at-startup nil)

With this configuration set, Emacs will only load the packages installed through straight.el.

Usage

To use straight.el to install a package for the current session, execute the straight-use-package command:

M-x straight-use-package <RET> evil-commentary <RET>

To continue using the package in future sessions, add the straight-use-package call to ~/.emacs/init.el:

(straight-use-package 'evil-commentary)

To update an installed package, execute the straight-pull-package command:

M-x straight-pull-package <RET> evil-commentary <RET>

To update the version lockfile, which is used to target the exact version to check out when installing, run straight-freeze-versions:

M-x straight-freeze-versions <RET>

Use-package

Use-package is a macro to configure and load packages in Emacs configurations. It interfaces with package managers like package.el or straight.el to install packages, but is not a package manager by itself.

For example, when using straight.el without use-package, installing and starting evil-commentary requires installing the package and starting it as two separate steps:

(straight-use-package 'evil-commentary)
(evil-commentary-mode)

Combined with use-package, the installation and configuration are unified into a single call to use-package:

(use-package evil-commentary
         :config (evil-commentary-mode))

Aside from keeping configuration files tidy, having package configuration contained within a single call allows for more advanced package setups. For example, packages can be lazy-loaded, keeping their configuration code from executing until the package they configure is needed.

Installation

To install use-package with straight.el, use straight-use-package:

;; Install use-package
(straight-use-package 'use-package)

Using straight.el with use-package

By default, use-package uses package.el to install packages. To use straight.el instead of package.el, pass the :straight option:

(use-package evil-commentary
         :straight t)

To configure use-package to always use straight.el, use use-package to configure straight.el to turn on straight-use-package-by-default¹:

;; Configure use-package to use straight.el by default
(use-package straight
         :custom (straight-use-package-by-default t))

Now, installing any package using use-package uses straight.el, even when omitting the :straight.el option.

Having both straight.el and use-package installed and configured to work together, the straight-use-package function isn't used anymore. Instead, all packages are installed and configured through use-package.

Usage

Use the use-package macro to load a package. If the package is not installed yet, it is installed automatically:

(use-package evil-commentary)

Use-package provides keywords to add configuration, key bindings and variables. Although there are many more options, some examples include :config, :init, :bind, and :custom:

:config and :init: The :config and :init configuration keywords define code that's run right after, or right before a package is loaded, respectively.

For example, call evil-mode from the :config keyword to start Evil after loading its package. To turn off evil-want-C-i-jump right before evil is loaded (instead of adding it to the early init file), configure it in the :init keyword:
```
(use-package evil
         :init (setq evil-want-C-i-jump nil)
         :config (evil-mode))
```
:bind: Adds key bindings after a module is loaded. For example, to use consult-buffer instead of the built-in switch-to-buffer after loading the consult package, add a binding through the :bind keyword:
```
(use-package consult
         :bind ("C-x b" . consult-buffer)
```
:custom: Sets customizable variables. The variables set through use-package are not saved in Emacs' custom file. Instead, all custom variables are expected to be set through use-package. In an example from before, the :custom keyword is used to set the straight-use-package-by-default configuration option after loading straight.el:
```
(use-package straight
         :custom (straight-use-package-by-default t))
```

Summary

The resulting ~/.emacs.d/init.el file installs straight.el and use-package, and configures straight.el as the package manager for use-package to use:

;; Install straight.el
(defvar bootstrap-version)
(let ((bootstrap-file
       (expand-file-name "straight/repos/straight.el/bootstrap.el" user-emacs-directory))
      (bootstrap-version 5))
  (unless (file-exists-p bootstrap-file)
    (with-current-buffer
    (url-retrieve-synchronously
     "https://raw.githubusercontent.com/raxod502/straight.el/develop/install.el"
     'silent 'inhibit-cookies)
      (goto-char (point-max))
      (eval-print-last-sexp)))
  (load bootstrap-file nil 'nomessage))

;; Install use-package
(straight-use-package 'use-package)

;; Configure use-package to use straight.el by default
(use-package straight
         :custom (straight-use-package-by-default t))

The ~/.emacs.d/early-init.el file disables package.el to disable its auto-loading, causing all packages to be loaded through straight.el in the init file:

;; Disable package.el in favor of straight.el
(setq package-enable-at-startup nil)

This is the only configuration set in the early init file. All other packages are installed and configured through use-package, which makes sure to load configuration options before packages are loaded, if configured with the :init keyword.

Footnotes

¹ Calling use-package would normally install straight.el, but since it's already installed, the installation is skipped and the configuration is set. Here, the call to use-package is only used to configure straight.el, by setting the straight-use-package-by-default option.

Combine Git repositories with unrelated histories

Jeff Kreeftmeijer — Tue, 10 Aug 2021 09:58:49 +0000

To combine two separate Git repositories into one, add the repository to merge in as a remote to the repository to merge into. Then, combine their histories by merging while using the --allow-unrelated-histories command line option.

As an example, there are two repositories that both have a single root commit. Running git log produces the log for the first repository, as that repository's directory is the current directory:

git log

commit 733ed008d41505623d6f3b5dbee7d1841a959c34
Author: Alice <alice@example.com>
Date:   Sun Aug 8 20:12:38 2021 +0200

    Add one.txt

To get the logs for the second repository, pass a path to that repository's .git directory to the git log command via the --git-dir command line option:

git --git-dir=../two/.git log

commit 43d2970b4dafa21477e1a5a86cad45bc5e798696
Author: Bob <bob@example.com>
Date:   Sun Aug 8 20:12:44 2021 +0200

    Add two.txt

To combine the two repositories, first add the second repository as a remote to the first. Then, run git fetch to fetch its branch information:

git remote add two ../two
git fetch two

Then merge, with the remote set up, merge the second repository's history into the first by using the --allow-unrelated-histories flag:

git merge two/main --allow-unrelated-histories

Merge made by the 'recursive' strategy.
 two.txt | 0
 1 file changed, 0 insertions(+), 0 deletions(-)
 create mode 100644 two.txt

Unlike extracting part of a repository—which rewrites history by definition—combining repositories is done by merging their two histories. This means the commits from the second repository are appended to the ones from the first, retaining history:

git log

commit 0bd5727a597077b5a5db9590b3f6aaf70eb10b60
Merge: 733ed00 43d2970
Author: Alice <alice@example.com>
Date:   Sun Aug 8 20:13:01 2021 +0200

    Merge remote-tracking branch 'two/main' into main

commit 43d2970b4dafa21477e1a5a86cad45bc5e798696
Author: Bob <bob@example.com>
Date:   Sun Aug 8 20:12:44 2021 +0200

    Add two.txt

commit 733ed008d41505623d6f3b5dbee7d1841a959c34
Author: Alice <alice@example.com>
Date:   Sun Aug 8 20:12:38 2021 +0200

    Add one.txt

References

https://git-scm.com/docs/git-merge:

By default, git merge command refuses to merge histories that do not share a common ancestor. [The --allow-unrelated-histories] option can be used to override this safety when merging histories of two projects that started their lives independently.

Testing input and output in Rust command line applications

Jeff Kreeftmeijer — Tue, 29 Jun 2021 17:01:08 +0000

Working with complex input and output can make command line applications challenging to test, as it is inconvenient to capture the output stream to test if the program returns the correct output. Using abstraction through Rust's Read and Write traits, we can swap the input and output for byte arrays and vectors during testing instead.

Standard Streams

Standard streams are abstractions used to handle data input and output to an operating system process.
Each program has access to an input stream (standard input, or stdin), an output stream (standard output, or stdout), and an error stream (standard error, or stderr) inherited from the parent process.

Example 1. grep(1) filters lines read from stdin with a search pattern ("three" in this case) and prints the matching lines to stdout. After starting, grep halts to wait for input from stdin. By typing this input into the terminal, we can see that grep prints any line that matches the pattern back to stdout, which the terminal displays. Then, the program returns to waiting for input until it receives an EOF (end-of-file), which we pass by pressing kbd:[ctrl]+kbd:[D] in the terminal.

$ grep three
one
two
three
three

Because of this abstraction, programs can use pipelines to pass the output from one program as the input to another by piping stdout from one process to stdin for another.

Example 2. ls(1) prints the current directory's contents to stdout. This example uses a pipe (|) to create a pipeline, to pass the output from ls as input to grep. grep then filters to only print lines matching the passed pattern ("Cargo").

$ ls -l ~/pager | grep Cargo
Cargo.lock
Cargo.toml

`Stdin`, `Stdout` and `Stderr` in Rust

Rust provides handles to the standard streams through the Stdin, Stdout and Stderr structs, which are created with the io::stdin(), io::stdout() and io::stderr() functions respectively.

Example 3. This program takes input through stdin, converts the received string to uppercase and prints it back out to the terminal through stdout.

src/main.rs

use std::io;
use std::io::{Read, Write};

fn main() -> io::Result<()> {
    let mut buffer = "".to_string();

    io::stdin().read_to_string(&mut buffer)?;
    io::stdout().write_all(buffer.to_uppercase().as_bytes())?;

    Ok(())
}

The stream handlers implement the Read and Write traits to read from and write to the streams. Because of that, they share part of their implementation with other "Readers" and "Writers", like File.

Abstraction using the `Read` and `Write` traits

One of the issues¹ in the example above is that it uses the Stdout and Stdin structs directly, making our program challenging to test because it is inconvenient to pass input through stdin and capture stdout to assert that the program produces the correct results.

To make our program more modular, we will decouple it from the Stdin and Stdout structs and pass the input and output as arguments to a more abstract, separate function.

Example 4. In the test for the extracted function, we swap Stdin and Stdout out for other implementors of the Read and Write traits: a byte array for input and a vector for output.

src/lib.rs

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn writes_upcased_input_to_output() {
        let mut output: Vec<u8> = Vec::new();

        upcase(&mut "Hello, world!\n".as_bytes(), &mut output).unwrap();
        assert_eq!(&output, b"HELLO, WORLD!\n");
    }
}

Example 5. The implementation that satisfies the test looks like the original example, with one significant difference. Because the test passes the input and output as arguments, we can use trait objects to allow any type as long as it implements the Read and Write traits:

src/lib.rs

pub fn upcase(
    input: &mut impl Read,
    output: &mut impl Write,
) -> Result<(), Error> {
    let mut buffer = "".to_string();

    input.read_to_string(&mut buffer)?;
    output.write_all(buffer.to_uppercase().as_bytes())?;

    Ok(())
}

Example 6. Finally, we replace the prototype in src/main.rs with a call to our new implementation with a Stdin and Stdout struct for the input and output:

src/main.rs

use std::io;

fn main() -> io::Result<()> {
    upcase::upcase(&mut io::stdin(), &mut io::stdout())
}

By abstracting Stdin and Stdout out of the implementation, we made our program more modular, allowing us to test the code without resorting to capturing stdout to assert that the printed result matched our expectations.

Aside from better testability, making our implementation more modular will allow us to work with other data types in the future.
For example, we might add a command-line option that takes a filename and pass a File to upcase().
Since File also implements the Read trait, that would work without further modifications in our implementation.

Another issue with this example is that it uses Read::read_to_string(), which will read the contents of the whole stream from the input before writing everything to stdout at once, which is inefficient, especially for larger inputs. A more efficient implementation could use buffered reading through the BufRead trait to read and write the input stream line by line. ↩

Embrace email, mute Slack. A policy for handling incoming messages

Jeff Kreeftmeijer — Fri, 08 Jan 2021 16:22:59 +0000

After coming back from a two-week break—in which I didn't check my
work email or Slack—I prepared to spend most of a day catching up to
whatever happened in my absence.

Somewhat to my surprise, that wasn't the case. I cleared my inbox in
about two hours, in which I responded to everything that I could do
immediately and moved everything that'd take more time to the correct
project boards to be prioritized and picked up later. After clearing my
unread messages in slack, I realized I was all caught up in record time.

This hasn't always been the case. I remember coming back from some
holidays and spending a couple of days catching up by checking multiple
communication channels, after which I still wasn't really sure I missed
anything.

Part of this is thanks to my policy of handling incoming messages. I try
to make any communication as asynchronous as possible, even while using
synchronous, distracting tools like Slack.

Funneling everything through email

I use Email, Basecamp, Github, Intercom and Slack as communication
tools.

Others seem to view email as a productivity killer. It's my Fortress of
Solitude. I try to funnel all incoming messages through email. Most of
the items in my inbox are from Github, Intercom, and Basecamp. I also
have email notifications set up for Slack channels I idle in, to let me
know when I receive a direct message so I don't have to check in there
too often.

Email is my single source of truth. I have email notifications set up
for everything, so I know I don't miss anything if I keep up with my
inbox.

I'll go through my inbox at least twice a day. Once when I start
working, and once before I leave.
I'll respond immediately if I can, or schedule time to look into it
(by blocking out time in my calendar) if I need some more time.
If it'll take more than a day to produce a response because of other
tasks, I'll let the other party know that it'll be a while.
I'll unsubscribe from issues, un-watch repositories or ignore
threads on Basecamp if I'm not needed.

By handling email this way, I don't need to separately check Github and
Basecamp to see if there's anything waiting for me to pick up. It's all
in email.

Managing Slack direct messages and unreads

By definition, Slack is more difficult to turn asynchronous like email.
I try to keep work-related messages I need a response to off Slack as
much as I can to keep it from becoming a distraction for others. GitHub
or Basecamp are better channels for that.

I've struggled with Slack, but lately I feel like I arrived at setup I
quite like.

I have Do Not Disturb turned on at all times, which means mentioning
me or sending me a direct message won't send me a notification. When
direct messaging me, Slack shows a message explaining I won't be
notified, complete with a button to notify me anyway. This button
gives the sender the ability to push an urgent message through; and
notify me anyway.
If I get a Slack notification, I'll drop whatever I'm doing and will
get back on the message as soon as I can.
I check Slack multiple times a day, usually in between tasks, to see
if anything new came in. Unless I'm working on finishing a big task,
I'll read messages within two hours during my workday.
I'm in as few channels as possible. I'm not in notification channels
if I don't need the notifications, or if I can move them over to
email.

I love Do Not Disturb in, as it puts the decision to notify me in the
senders hands instead of taking me off my work to determine how urgent
something is.

Thanks Maarten, Jankees, Jeroen, Piotr, Antek and Thijs for your input, and Jelte for typo-hunting.

Multiplayer Go with Elixir's Registry, PubSub and dynamic supervisors

Jeff Kreeftmeijer — Tue, 13 Aug 2019 10:16:22 +0000

Welcome back to Elixir Alchemy, and to the third part in our series on implementing the Go game using Phoenix LiveView. In part one, we set up the game using LiveView and in part two, we added Game history and implemented the ko rule.

Currently, our game is a local "hot seat" multiplayer game where players take turns on the same browser window. Our next adventure aims to turn the game into a true multiplayer experience by allowing players to play with others online.

In this article, we'll take the first step towards that goal. We'll allow the creation of new games as well as inviting others to join in by turning the Game struct into a dynamically supervised GenServer, we'll keep track of games using Elixir's Registry, we'll allow players to connect to already started games, and we'll broadcast moves to all connected players using Phoenix.PubSub.

Where We Left Off

The starter app for this episode is where we left off last time. We have an implementation of the game with buttons to undo and redo moves.

The final result can be played online, and the code for the completed application can be found in the repository's master branch (if you prefer to jump straight into the code).

We have a lot to do, so let's get started!

Dynamically Supervised GenServers

Currently, the game's state is kept in the player's socket connection. This works for games with a single player, but there's no way for another socket connection to access an existing game. To allow two players to play the game together over two socket connections, we need to store each started game in a separate process that both can access.

We'll use a dynamically supervised GenServer to keep each game's state. The dynamic supervisor allows players to start games and it also automatically restarts them when a game process crashes.

First, let's turn our Game module into a GenServer to allow multiple processes to access it.

# lib/hayago/game.ex
defmodule Hayago.Game do
  # ...
  use GenServer

  def start_link(options) do
    GenServer.start_link(__MODULE__, %Game{}, options)
  end

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

  @impl true
  def handle_call(:game, _from, game) do
    {:reply, game, game}
  end

  @impl true
  def handle_cast({:place, position}, game) do
    {:noreply, Game.place(game, position)}
  end

  @impl true
  def handle_cast({:jump, destination}, game) do
    {:noreply, Game.jump(game, destination)}
  end

  # ...
end

Our GenServer handles the :game call, which returns the current game's Game struct. The {:place, position} and {:jump, destination} cast callbacks update the game by calling Game.place/2 and Game.jump/2, respectively.

With our GenServer callbacks in place, we can spawn a process that keeps a game's state. To supervise these processes, we'll use Elixir's DynamicSupervisor, which allows spawning children on demand. We'll use it to start a new game when a player opens the page.

# lib/hayago/application.ex
defmodule Hayago.Application do
  # ...

  def start(_type, _args) do
    # List all child processes to be supervised
    children = [
      HayagoWeb.Endpoint,
      {DynamicSupervisor, strategy: :one_for_one, name: Hayago.GameSupervisor}
    ]

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

  # ...
end

We'll set up our dynamic supervisor in the app's Application module. The :one_for_one strategy (which is the only one available for dynamic supervisors) ensures that a game is restarted whenever it crashes.

Pids, Atoms and the Registry

Because our Game module now implements GenServer callbacks, we can spawn a Game through the GenServer module.

% iex -S mix
iex(1)> {:ok, pid} = DynamicSupervisor.start_child(Hayago.GameSupervisor, Hayago.Game)
{:ok, #PID<0.286.0>}
iex(2)> GenServer.cast(pid, {:place, 0})
:ok

The returned pid is used to get and update the game's state. In this case, we use it to place a stone on the top-left position of the board.

Instead of keeping the game in the socket for every connection, we could add the pid to the socket and then request and update its state through that.

However, our supervisor is tasked with restarting any game process that crashes. When that happens, the game is restarted in a new process with a new pid. When that happens, the players will still be disconnected from the game because the only reference they have to the game will no longer be working, and they'll have no way of getting the new pid.

iex(3)> Process.exit(pid, :kill)
true
iex(4)> Process.alive?(pid)
false

A solution to this is naming processes when they're spawned so that we can refer to them by name. Whenever a named process is restarted by a supervisor, the newly started process automatically receives the name of the process it replaces.

iex(5)> {:ok, pid} = DynamicSupervisor.start_child(Hayago.GameSupervisor, {Hayago.Game, name: :game_1})
{:ok, #PID<0.285.0>}
iex(6)> Process.whereis(:game_1)
#PID<0.285.0>
iex(7)> Process.exit(pid, :kill)
true
iex(8)> Process.whereis(:game_1)
#PID<0.288.0>
iex(9)> GenServer.cast(pid, {:place, 0})
:ok

Here, we start a new game and use :game_1 as its name. If we kill the game process, another one is automatically spawned to replace it. The new process shares the same name, so we can continue using :game_1 to refer to the new process.

This way, we could generate a unique name for each process when spawning it, and keep that in our socket to refer to the game later. But, wait! We're naming our processes with atoms here. Since atoms aren't garbage collected, spawning a lot of games can exhaust our memory. Instead, we'd like to use strings, which are garbage collected.

Because we can't name a process with a string, we need to use a Registry to link string names to game pids. Elixir's GenServer implementation has a built-in way of referring to processes in a registry through it's :via-tuples. First, let's start the registry in our main supervisor whenever the application starts.

# lib/hayago/application.ex
defmodule Hayago.Application do
  # ...

  def start(_type, _args) do
    children = [
      HayagoWeb.Endpoint,
      {Registry, keys: :unique, name: Hayago.GameRegistry},
      {DynamicSupervisor, strategy: :one_for_one, name: Hayago.GameSupervisor}
    ]

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

  # ...
end

With the new registry in place, we can start processes using a string as their name, and refer to them later without creating an atom for every spawned game.

iex(1)> {:ok, pid} = DynamicSupervisor.start_child(Hayago.GameSupervisor, {Hayago.Game, name: {:via, Registry, {Hayago.GameRegistry, "game_1"}}})
{:ok, #PID<0.294.0>}
iex(2)> Process.exit(pid, :kill)
iex(3)> GenServer.cast({:via, Registry, {Hayago.GameRegistry, "game_1"}}, {:place, 0})
:ok

Switching to Game Processes

Instead of creating a new game struct and assigning it directly to the socket, we'll update the GameLive.mount/2 function to start a supervised process that holds a game's state.

# lib/hayago_web/live/game_live.ex
defmodule HayagoWeb.GameLive do
  # ...

  def mount(_session, socket) do
    name =
      ?a..?z
      |> Enum.take_random(6)
      |> List.to_string()

    {:ok, _pid} =
      DynamicSupervisor.start_child(Hayago.GameSupervisor, {Game, name: via_tuple(name)})

    {:ok, assign_game(socket, name)}
  end

  # ...

  defp via_tuple(name) do
    {:via, Registry, {Hayago.GameRegistry, name}}
  end

  defp assign_game(socket, name) do
    socket
    |> assign(name: name)
    |> assign_game()
  end

  defp assign_game(%{assigns: %{name: name}} = socket) do
    game = GenServer.call(via_tuple(name), :game)
    assign(socket, game: game, state: Game.state(game))
  end
end

We create a random six-character string as the name of our process, which we use when spawning the process through our GameSupervisor. The via_tuple/1 convenience function returns the :via-tuple that we'll need to register the process' name in the registry.

Finally, we add an assign_game/1-2 function that takes a socket of the game's registered name. It calls out to the GenServer process to get the game's current state before assigning it to the socket.

Next, we'll switch both handle_event/3 variants to use the game via the GenServer.

# lib/hayago_web/live/game_live.ex
defmodule HayagoWeb.GameLive do
  # ...

  def handle_event("place", index, %{assigns: %{name: name}} = socket) do
    :ok = GenServer.cast(via_tuple(name), {:place, String.to_integer(index)})
    {:noreply, assign_game(socket)}
  end

  def handle_event("jump", destination, %{assigns: %{name: name}} = socket) do
    :ok = GenServer.cast(via_tuple(name), {:jump, String.to_integer(destination)})
    {:noreply, assign_game(socket)}
  end

  # ...
end

Again, we use the via_tuple/1 function to cast both our :place and :jump functions directly on the game's process. We then reassign the game to the socket by calling our assign_game/1 function.

Multiplayer URL Sharing

To allow multiple players to connect to the same game, we'll add the game's name to a URL that the first user can share. When a user starts a new game, we'll use the pushState function from the HTML5 history API to add the game's name to the URL without reloading the page.

We'll use Phoenix LiveView's live_redirect/2 function for that⁠—which was added recently after we started working on the game. To make sure we're on a recent enough version, let's update the dependency before continuing.

% mix deps.update phoenix_live_view

When a player visits the game without a game name in the URL, the app will start a new one and update the URL to include the newly created game's name. In our case, the game is served on the root of our application, so visiting http://localhost:4000 will redirect to http://localhost:4000?name=abcdef, where "abcdef" is the game's name.

To do this, we'll replace our mount/2 function with two variants of the handle_params/3 function.

# lib/hayago_web/live/game_live.ex
defmodule HayagoWeb.GameLive do
  # ...

  def handle_params(%{"name" => name} = _params, _uri, socket) do
    {:noreply, assign_game(socket, name)}
  end

  def handle_params(_params, _uri, socket) do
    name =
      ?a..?z
      |> Enum.take_random(6)
      |> List.to_string()

    {:ok, _pid} =
      DynamicSupervisor.start_child(Hayago.GameSupervisor, {Game, name: via_tuple(name)})

    {:ok,
    live_redirect(
      socket,
      to: HayagoWeb.Router.Helpers.live_path(socket, HayagoWeb.GameLive, name: name)
    )}
  end

  # ...
end

The first variant handles requests that have a name in the URL parameters. In that case, the latest game state is fetched from the process corresponding to the name from the parameters and assigned to the socket using the assign_game/2 function.

The second is a lot like the mount/2 function that we're replacing. We're generating a name and starting a game. However, instead of assigning the game to the socket and returning, this function uses LiveView's live_redirect/2 function to add the name to the current URL. After the URL changes, the first variant is automatically executed, assigning the name and game state to the socket.

Broadcasting Moves to All Clients

If we open our game right now, we'll see that every visit to http://localhost:4000 gets redirected to a URL with a name query parameter. Opening that URL twice connects two sockets to the same game.

However, when a stone is placed in one of the windows, it doesn't automatically appear in the other one. Only after refreshing the window do we see the correct placement of stones.

Everything is wired up correctly, but the second socket isn't getting notified when the first makes a move. We need a way to get all connected sockets to subscribe to a system that publishes updates to all clients when one makes a move.

We'll use Phoenix.PubSub to make that happen. Back in our GameLive module, we'll subscribe each socket connection to a channel when a game is created, and then we'll broadcast a message over that channel whenever we place a stone or travel in history.

# lib/hayago_web/live/game_live.ex
defmodule HayagoWeb.GameLive do
  # ...

  def handle_params(%{"name" => name} = _params, _uri, socket) do
    :ok = Phoenix.PubSub.subscribe(Hayago.PubSub, name)
    {:noreply, assign_game(socket, name)}
  end

  # ...

  def handle_event("place", index, %{assigns: %{name: name}} = socket) do
    :ok = GenServer.cast(via_tuple(name), {:place, String.to_integer(index)})
    :ok = Phoenix.PubSub.broadcast(Hayago.PubSub, name, :update)
    {:noreply, assign_game(socket)}
  end

  def handle_event("jump", destination, %{assigns: %{name: name}} = socket) do
    :ok = GenServer.cast(via_tuple(name), {:jump, String.to_integer(destination)})
    :ok = Phoenix.PubSub.broadcast(Hayago.PubSub, name, :update)
    {:noreply, assign_game(socket)}
  end

  def handle_info(:update, socket) do
    {:noreply, assign_game(socket)}
  end

  # ...
end

In handle_params/3 (the variant that matches on URLs with name query parameters), we call out to Phoenix.PubSub.subscribe/2. We use the game's name as the channel's topic. Because all connected clients will hit this function, we know they'll all be subscribed to this topic.

In both handle_event/3 functions, we use Phoenix.PubSub.broadcast/3 to send a message to all subscribers in the topic. We send :update as the message, which is then picked up in a newly added handle_info/2 function, which fetches the current Game's state and updates the view whenever it receives an update message.

To make sure games are cleaned up, we need to terminate their processes when they're no longer being used. For now, we'll add a timeout to the GenServer's callback functions. When a game hasn't had any interaction for ten minutes, the process will send itself a :timeout message to stop the process.

# lib/hayago/game.ex
defmodule Hayago.Game do
  # ...
  use GenServer, restart: :transient

  @timeout 600_000

  def start_link(options) do
    GenServer.start_link(__MODULE__, %Game{}, options)
  end

  @impl true
  def init(game) do
    {:ok, game, @timeout}
  end

  @impl true
  def handle_call(:game, _from, game) do
    {:reply, game, game, @timeout}
  end

  @impl true
  def handle_cast({:place, position}, game) do
    {:noreply, Game.place(game, position), @timeout}
  end

  @impl true
  def handle_cast({:jump, destination}, game) do
    {:noreply, Game.jump(game, destination), @timeout}
  end

  @impl true
  def handle_info(:timeout, game) do
    {:stop, :normal, game}
  end

  # ...
end

By adding a timeout in milliseconds to every callback's response tuple, we tell the GenServer to send itself a timeout message when the process hasn't received a message for ten minutes. The :timeout callback returns a :stop-tuple to tell the process to stop.

We also make sure to set the :restart value to :transient when including the GenServer code to ensure that the supervisor only restarts the game when it terminates abnormally.

What's Next?

This concludes the third part on implementing the Go game in Phoenix. We've come quite a long way in implementing a true multiplayer game, and we've learned about Elixir's dynamic supervisors, the Registry, and Phoenix.PubSub along the way.

In a future episode, we'll continue turning our game into a multiplayer game by assigning each connection as a separate player by assigning each of them a color of stones on the board. See you then!

Building the Go Game in Elixir: Time Travel and the Ko Rule

Jeff Kreeftmeijer — Thu, 04 Jul 2019 11:53:11 +0000

Welcome back to Elixir Alchemy! Two weeks ago, we started our adventure implementing the Go game in Elixir using Phoenix LiveView. Today, we return to the game to add the ability to undo and redo moves, then we'll implement Go's ko rule.

Onward!

In this article we will mostly focus on the implementation of the game, but still learn about Phoenix LiveView on the way. The final result of today's article includes undo and redo buttons, and the game prevents you from making moves that would revert the game to a previous state.

The new starter app contains the result of the last episode, which is a Phoenix application that uses LiveView to render and update the board. It implements some of Go's rules in its State module and keeps track of each player's captured stones. This time, we'll add a Game module that keeps the state of the whole game, including the previous moves.

Prefer to skip ahead and read the code? The master branch includes all the changes we'll make in this episode, along with test coverage and thorough documentation of all functions.

Time travel preparations

Before we do some time traveling and let players undo and redo moves, the game needs to keep a history of the moves made since it started. Currently, it keeps one State struct, which is accessible as @state in the template.

Whenever a player makes a move by clicking one of the invisible buttons on the board, the GameLive module handles the event. It uses State.place/2 to create a new state struct and assigns that as the new state to update the view.

# lib/hayago_web/live/game_live.ex
defmodule HayagoWeb.GameLive do
  # ...

  def handle_event("place", index, %{assigns: assigns} = socket) do
    new_game = Game.place(assigns.game, String.to_integer(index))
    {:noreply, assign(socket, game: new_game, state: Game.state(new_game))}
  end
end

Because of this implementation, there's currently no way of jumping back in history, as our game replaces the state with each move, and forgets the previous state.

To retain history, we'll add a struct named Game, which keeps a history of states in its :history attribute. When the game starts, it has a single, empty state in its history list to represent the empty board.

# lib/hayago/game.ex
defmodule Hayago.Game do
  alias Hayago.{Game, State}
  defstruct history: [%State{}]

  # ...
end

We'll add a convenience function to get the current state from a game. The first state in the history list is always the current state, so we can take the list's first element to get the current state.

# lib/hayago/game.ex
defmodule Hayago.Game do
  # ...

  def state(%Game{history: [state | _]}) do
    state
  end

  # ...
end

Finally, we'll implement a place/2 function to the Game module. It uses State.place/2 to create a new state struct, then prepends that to the history list.

# lib/hayago/game.ex
defmodule Hayago.Game do
  # ...

  def place(%Game{history: [state | _] = history} = game, position) do
    %{game | history: [State.place(state, position) | history]}
  end
end

Now, let's use the new game struct in the GameLive module. The mount/2 function is used to set up the game. Instead of creating a state struct and assigning it directly to the socket, we'll create a new game struct and assign that to the :game assign.

We'll still use the state struct in the template, so we'll preload it in the live view by calling our new Game.state/1 function and assigning the result as :state.

# lib/hayago_web/live/game_live.ex
defmodule HayagoWeb.GameLive do
  alias Hayago.Game
  use Phoenix.LiveView

  # ...

  def mount(_session, socket) do
    game = %Game{}
    {:ok, assign(socket, game: game, state: Game.state(game))}
  end

  # ...
end

When placing a stone, we'll now call the Game.place/2 function to update the current state while retaining the history list. Again, we use Game.state/1 on the updated game to preload the state.

# lib/hayago_web/live/game_live.ex
defmodule HayagoWeb.GameLive do
  alias Hayago.Game
  use Phoenix.LiveView

  # ...

  def handle_event("place", index, %{assigns: assigns} = socket) do
    new_game = Game.place(assigns.game, String.to_integer(index))
    {:noreply, assign(socket, game: new_game, state: Game.state(new_game))}
  end
end

If we try the game again, we won't see any changes. While we're keeping the history of all moves, we aren't doing anything with it yet.

Time Travel

Although we're now keeping a history of game states, all functions in our Game module still only use the first state in the list. As each move prepends a state to the history list, the first in the list is always the latest state.

To allow jumping back and forward, we'll add an attribute named :index to the Game struct, which defaults to 0.

# lib/hayago/game.ex
defmodule Hayago.Game do
  alias Hayago.{Game, State}
  defstruct history: [%State{}], index: 0

  # ...
end

By having an index, we can jump back to a previous state without having to drop states from the front of the list. Instead, we'll update our state/1 function to take the index into account. Instead of returning the first state in the list, it uses the game's index to find the current state in the list.

# lib/hayago/game.ex
defmodule Hayago.Game do
  # ...

  def state(%Game{history: history, index: index}) do
    Enum.at(history, index)
  end

  # ...
end

Now, if we have a game with a three-state history, setting the :index attribute to 1 returns the second state in the list, essentially reverting to that state.

To jump to a different index, we'll add a convenience function called jump/2, which overwrites a Game struct's :index attribute.

defmodule Hayago.Game do
  # ...

  def jump(game, destination) do
    %{game | index: destination}
  end
end

Now that our game module keeps a history of moves and we can jump between them, let's add buttons to undo and redo moves when playing the game.

# lib/hayago_web/templates/game/index.html.leex
# ...

<div class="history">
  <button phx-click="jump" phx-value="<%= @game.index + 1%>">Undo</button>
  <button phx-click="jump" phx-value="<%= @game.index - 1%>">Redo</button>
</div>

We use "jump" as the value for both buttons' phx-click attributes, which is the name of a function we'll implement shortly in the GameLive module.

The phx-value attribute is used to pass the history index we'd like to jump to. The history list reverses because new moves prepend to the history list. So to undo a move, we'll increase the current index by 1, and we'll decrease it by 1 to redo.

In the GameLive module, we'll handle the jump event by calling Game.jump/2 with the current game and the passed index, giving us a new game struct that we'll assign on the socket. Like before, we update the state assign for convenience.

# lib/hayago_web/live/game_live.ex
defmodule HayagoWeb.GameLive do
  # ...

  def handle_event("jump", destination, %{assigns: %{game: game}} = socket) do
    new_game = Game.jump(game, String.to_integer(destination))
    {:noreply, assign(socket, game: new_game, state: Game.state(new_game))}
  end
end

If we open our browser and navigate to https://localhost:4000, we can see that the undo and redo buttons work. After placing a few stones, we can click the undo button to get the last one removed, and the redo button to get it back again.

Branching off in History

However, if we undo a move and try to place a stone, we notice that the new stone doesn't get added to the board. Instead, the stone we just removed by pressing the undo button reappears.

It turns out we have one more step to take before we can place a new stone after pressing the undo button. Let's break down what's happening.

We place a stone on the board, which prepends a new state to the history list.
We press the undo button to increase the history index to 1, bringing us back to our initial state, giving us an empty board again.
We try to place a new stone, which prepends a new state to the history list. The Game's index remains at 1.

The new state is the first in the list, meaning its index is 0, but the Game index is still 1. That index belongs to the move we've undone by pressing the undo button. Essentially, our newly added stones are delayed by one move.

To fix this, we need to slice any undone states from the list whenever we add a new state by placing a new stone. Removing states from the history allows users to branch off in a different direction after undoing moves.

# lib/hayago/game.ex
defmodule Hayago.Game do
  # ...

  def place(%Game{history: history, index: index} = game, position) do
    new_state =
      game
      |> Game.state()
      |> State.place(position)

    %{game | history: [new_state | Enum.slice(history, index..-1)], index: 0}
  end

  # ...
end

In the new version of our place/2 function, we use Enum.slice/2 to drop the undone moves from the history list. We'll also reset our game's index attribute to 0, which makes sure our newly added stones always immediately appear. Now time travel works, though we are not sure whether this means we need to worry about avoiding the predestination paradox.

Disabling Inapplicable Undo and Redo Buttons

Now when there are no moves to undo or redo, we need to make sure the undo and redo buttons are disabled. To do that, we'll implement a function named history?/2, which takes a game struct and an index and returns whether that index is part of the game's history.

# lib/hayago/game.ex
defmodule Hayago.Game do
  # ...

  def history?(%Game{history: history}, index) when index >= 0 and length(history) > index do
    true
  end

  def history?(_game, _index), do: false
end

Our function checks if the requested index is above 0 to make sure the game doesn't allow jumping forward when there are no moves done yet. Then, it checks if the length of the history list is higher than the index, to make sure we don't overshoot the list when undoing moves.

With our new function in place, we can check if the game can undo and redo to the previous and next move before rendering the button. If it can't, it renders a disabled version.

# lib/hayago_web/templates/game/index.html.leex
<div class="history">
  <%= if Hayago.Game.history?(@game, @game.index + 1) do %>
    <button phx-click="jump" phx-value="<%= @game.index + 1%>">Undo</button>
  <% else %>
    <button disabled="disabled">Undo</button>
  <% end %>

  <%= if Hayago.Game.history?(@game, @game.index - 1) do %>
    <button phx-click="jump" phx-value="<%= @game.index - 1%>">Redo</button>
  <% else %>
    <button disabled="disabled">Redo</button>
  <% end %>
</div>

Trying the game again, we'll see that we can't undo further than the list of previous moves, and we can't redo into the future.

The Ko Rule

Aside from allowing the player to undo and redo moves, keeping history allows us to implement Go's ko rule.

A play is illegal if it would have the effect (after all steps of the play have been completed) of creating a position that has occurred previously in the game.

Go prevents players from making moves that revert the board to a previous state. In practice, this happens when a player captures a stone, and the other player makes a move that immediately captures the newly added stone.

Currently, we validate moves in the State.legal?/2 function, which checks if a position is empty, and makes sure placing a stone on that position has liberties.

To implement the ko rule, we need the history of game states, meaning we need access to the Game struct. To do that, we add a function named Game.legal?/2.

# lib/hayago/game.ex
defmodule Hayago.Game do
  # ...

  def legal?(game, position) do
    State.legal?(Game.state(game), position) and not repeated_state?(game, position)
  end

  defp repeated_state?(game, position) do
    %Game{history: [%State{positions: tentative_positions} | history]} =
      Game.place(game, position)

    Enum.any?(history, fn %State{positions: positions} ->
      positions == tentative_positions
    end)
  end

  # ...
end

Our new function takes the game struct as its first argument and the position a new stone is placed as the second. It calls State.legal?/2 to make sure the already-implemented rules are satisfied. Then, it makes sure the new state hasn't already happened using repeated_state?/2, a private function that places the stone and compares the new state to the history list.

Finally, we'll update the template to switch from using State.legal?/2 directly to using Game.legal?/2, which takes the game history into account.

# lib/hayago_web/templates/game/index.html.leex
# ...

<div class="board <%= @state.current %>">
  <%= for {value, index} <- Enum.with_index(@state.positions) do %>
    <%= if Hayago.Game.legal?(@game, index) do %>
      <button phx-click="place" phx-value="<%= index %>" class="<%= value %>"></button>
    <% else %>
      <button class="<%= value %>" disabled="disabled"></button>
    <% end %>
  <% end %>
</div>

# ...

Back in the game, we'll see that we can't make a move that reverts the game's state to one that's in the history anymore.

Time travel and the ko rule

We've improved our game by adding a smart way to revert moves, and through that, we were able to implement the Ko rule. Along the way, we've learned how flexible LiveView is, as we hardly touched the live view code, although we've changed quite a bit in the game.

This concludes part two of our series on implementing the Go game with Elixir and Phoenix LiveView. We'd love to know how you're enjoying it so far, and what you'd like to learn about next.

If you want to have this article in your inbox as soon as it appears, travel back in time and subscribe to the Elixir Alchemy list. Until next time, and in the meantime, be careful with your newfound time travel abilities!

Building and Playing the Go Game with Phoenix LiveView

Jeff Kreeftmeijer — Tue, 18 Jun 2019 13:49:04 +0000

Welcome back to another Elixir Alchemy! This time, we'll discover the power of Phoenix LiveView by building an interactive game.

By rendering HTML on the server and communicating between the frontend and backend over web sockets, LiveView helps us build real-time interfaces without writing JavaScript or worrying about updating the state in the browser. By updating the state on the server side, LiveView makes sure to only update the parts of the page that need to be, resulting in fast applications that send minimal amounts of data over the wire.

To illustrate this, we’ll build our game in Phoenix, and we’ll use LiveView to make it interactive. Although tic-tac-toe is fun, we’ll go for something a bit more ambitious by building Go.

Go is an abstract strategy board game for two players, in which the aim is to surround more territory than the opponent. The game was invented in China more than 2,500 years ago and is believed to be the oldest board game continuously played to the present day.

The final result is an implementation of the Go game that allows players to take turns placing stones on the board. Players can capture each other's stones, and the game keeps track of which stones were captured.

Along the way, we’ll learn how Phoenix LiveView can help you build interactive applications without duplicating code between the frontend and the backend by keeping everything in Elixir.

Let’s Go!

The starter app is a Phoenix application with some parts already set up. It cleans up some generated files, adds styling for the Go board, pre-installs Phoenix LiveView according to the install guide in the README, and has a module that keeps track of the game’s state.

In our game, the State module describes the state of the game. The starter app already comes with the State module so we can focus on working with LiveView.

The State struct keeps track of which stones are on the board in its :positions list, and it knows which player is up next in its :current key.

# lib/hayago/state.ex
defmodule Hayago.State do
  alias Hayago.State
  defstruct positions: Enum.map(1..81, fn _ -> nil end), current: :black

  # ...
end

A newly created state is initialized with list of 81 nil values as its :positions, as the board is empty and has 9 by 9 positions. The player with the black stones is the first to move, so the :current key is set to :black for any new state.

The State module exposes two functions. The first is place/2 which places a new stone on the board. If the new stone steals all the liberties of another stone, the captured stone is removed from the board automatically.

The legal?/2 function checks if a move is legal by checking if another stone already occupies the position and making sure the stone wouldn't be immediately captured.

-> If you’d like to learn more about the implementation of the State module that we’ll use, check out the module’s documentation, which explains how it handles placing stones on the board, capturing stones and validating possible moves.

The `GameLive` Module

We’ll start by rendering the board. First, we add a live view to our application to handle rendering and updating the board. It’s called GameLive, and it has render/1 and mount/2 callback functions.

# lib/hayago_web/live/game_live.ex
defmodule HayagoWeb.GameLive do
  use Phoenix.LiveView

  def render(assigns) do
    HayagoWeb.GameView.render("index.html", assigns)
  end

  def mount(_session, socket) do
    {:ok, assign(socket, state: %Hayago.State{})}
  end
end

The mount/2 callback sets up the assigns in the socket to set the initial state for the view. We use it to create a new state, then add it to the socket assigns to make it available in the template.

Next, we’ll add a template to render the board. We name it index.html.leex, making it a Live EEx template. Although similar to regular EEx templates, live templates track changes in order to send a minimal amount of data over the wire whenever the view updates.

# lib/hayago_web/templates/game/index.html.leex
<div class="board <%= @state.current %>">
  <%= for _position <- @state.positions do %>
    <button></button>
  <% end %>
</div>

We loop over all positions in the @state struct we assigned in the live view and an empty <button> elements for each. The buttons are in a <div> element, which the stylesheet automatically styles as a Go board. We’ll also add the current color as a class name to the board, to allow the stylesheet to show the stone you’re about to place when you hover over a position.

Finally, we route any requests to / to our GameLive module in our router:

# lib/hayago_web/router.ex
defmodule HayagoWeb.Router
  # ...

  scope "/", HayagoWeb do
    pipe_through :browser

    live "/", GameLive
  end
end

If we start the Phoenix server and navigate to https://localhost:4000 in our browser, we'll see the app render an empty Go board. While we can't place stones just yet, hovering over the positions on the board shows us where a new stone would be placed.

Making Moves

To place stones on the board, State implements a place/2 function that takes a State struct and an index. It replaces the position that corresponds to the index with the value in the :current key, which is either :black or :white, depending on which player’s turn it is.

In the template, we add phx-click and phx-value attributes to our buttons. These attributes tell LiveView to send an event to our GameLive module.

# lib/hayago_web/templates/game/index.html.leex
<div class="board">
  <%= for {value, index} <- Enum.with_index(@state.positions) do %>
    <button phx-click="place" phx-value="<%= index %>" class="<%= value %>"></button>
  <% end %>
</div>

In our live view, we handle the event by matching on the attributes we set in the template. We use the passed index to call State.place/2, which returns a new state with the stone placed on the board. We'll return a :noreply-tuple with the new state.

# lib/hayago_web/live/game_live.ex
defmodule HayagoWeb.GameLive do
  # ...

  def handle_event("place", index, %{assigns: assigns} = socket) do
    new_state = State.place(assigns.state, String.to_integer(index))
    {:noreply, assign(socket, state: new_state)}
  end
end

By updating the state in the socket, LiveView knows to rerender the parts of the template that changed. The updated page is then compared to the rendered page to apply a minimal patch to the already-rendered page.

Back in our browser, which automatically refreshed the page after we made our changes, our project is already starting to look like a proper Go game. We can place stones on the board and even surround an enemy stone to have it removed!

Look at all the things we're not doing! We didn't have to write any code to send data to the browser, and we didn't have to worry about updating the rendered page. LiveView took care of updating the page whenever the state changed.

However, if we click the same position twice, an already placed stone is replaced by another. To prevent this from happening, we should disable the buttons that represent illegal moves.

Preventing Illegal Moves

To prevent illegal moves, we’ll render a disabled button for every position that either has a stone on it already or one where a newly placed stone has no liberties.

To make that work, we’ll use State.legal?/2, which takes the current state and an index, and returns a value indicating whether the current player can place a stone there or not.

<div class="board <%= @state.current %>">
  <%= for {value, index} <- Enum.with_index(@state.positions) do %>
    <%= if Hayago.State.legal?(@state, index) do %>
      <button phx-click="place" phx-value="<%= index %>" class="<%= value %>"></button>
    <% else %>
      <button class="<%= value %>" disabled="disabled"></button>
    <% end %>
  <% end %>
</div>

Because LiveView takes care of updating the page, we can add an if-statement to the template that checks if placing a stone on each position is a legal move. If it is, we render the same button as before. Otherwise, we render a disabled button.

The stylesheet makes sure not to show hovers for disabled buttons, and changes the cursor to indidcate that a stone can be placed there.

Capturing Stones

When capturing a stone, the place/2 function increments a counter in the current state's :captures map, which holds a counter for both the black and the white stones.

For each captured stone, we’ll show a stone above the board. Since the captures are already available in the @state struct we receive from the live view, we’ll loop over each of the counters to render a <span> with the correct class name for the stylesheet to turn into a button.

<div class="captures">
  <div>
    <%= for _ <- 1..@state.captures.black, @state.captures.black > 0 do %>
      <span class="black"></span>
    <% end %>
  </div>
  <div>
    <%= for _ <- 1..@state.captures.white, @state.captures.white > 0 do %>
      <span class="white"></span>
    <% end %>
  </div>
</div>

Since we’re using a range in our list comprehension, we’ll make sure to add a filter that ensures that the list isn’t empty when looping over it.

Now, we have a way to keep track of which stones were captured, as the stones are displayed above the board.

Scoring, History and the Ko Rule

We've made some strides implementing Go, and we’ve now learned how to set up a LiveView project. We've seen that carefully updating the state is enough to make build an interface without having to worry about updating the view. Instead, we focussed on rendering a static representation of the current state, and left the work of updating the page the player sees up to LiveView. Aside from setting up our live view module, the code we wrote to show the state of the board was all done by adding logic to the template, and we didn't have to write any JavaScript ourselves.

However, there are still some things we should do. The next time we meet, we’ll add history to our game to allow players to undo moves and we’ll implement the ko rule to prevent repeating moves. Finally, we’ll add a score counter to show each player’s current score. See you then!

Inside Enumeration in Ruby

Jeff Kreeftmeijer — Tue, 28 May 2019 14:40:00 +0000

Welcome back to another edition of Ruby Magic! A year ago, we learned about Ruby’s Enumerable module, which provides the methods you use when working with enumerable objects like arrays, ranges, and hashes.

Back then, we created a LinkedList class to show how to make an object enumerable by implementing the #each method on it. By including the Enumerable module, we were able to call methods like #count, #map and #select on any linked list without having to implement them ourselves.

We've learned how to use enumerables, but how do they work? Part of the magic in enumerables in Ruby comes from their internal implementation, which is all based on the single #each method, and even allows chaining enumerators.

Today, we’ll learn how the methods in the Enumerable class are implemented and how Enumerator objects allow chaining enumeration methods.

As you've become accustomed to, we'll dive in deep by implementing our own versions of the Enumerable module and Enumerator class. So, put on your over-engineering helmet and let's go!

Linked Lists

Before we begin, let’s start with a new version of the linked list class we wrote previously.

class LinkedList
  def initialize(head = nil, *rest)
    @head = head

    if rest.first.is_a?(LinkedList)
      @tail = rest.first
    elsif rest.any?
      @tail = LinkedList.new(*rest)
    end
  end

  def <<(head)
    @head ? LinkedList.new(head, self) : LinkedList.new(head)
  end

  def inspect
    [@head, @tail].compact
  end

  def each(&block)
    yield @head if @head
    @tail.each(&block) if @tail
  end
end

Unlike the previous version, this implementation allows empty lists to be created, as well as lists with more than two items. This version also allows passing a linked list as the tail when initializing another.

irb> LinkedList.new
=> []
irb> LinkedList.new(1)
=> [1]
irb> LinkedList.new(1, 2)
=> [1,[2]]
irb> LinkedList.new(1, 2, 3)
=> [1,[2,[3]]]
irb> LinkedList.new(1, LinkedList.new(2, 3))
=> [1,[2,[3]]]
irb> LinkedList.new(1, 2, LinkedList.new(3))
=> [1,[2,[3]]]

Previously, our LinkedLIst class included the Enumerable module. When mapping over an object using one of Enumerable's methods, the result are stored in an array. This time, we'll implement our own version to make sure our methods return new linked lists instead.

Enumerable Methods

Ruby's Enumerable module comes with enumeration methods like #map, #count, and #select. By implementing the #each method and including the Enumerable module in our class, we'd be able to use those methods directly on our linked lists.

Instead, we'll implement DIYEnumerable and import that instead of Ruby's version. This isn't something you'd typically do, but it will give us a clear insight into how enumeration works internally.

Let's start with #count. Each of the importable methods in the Enumerable class uses the #each method we implemented in our LinkedList class to loop over the object to calculate their results.

module DIYEnumerable
  def count
    result = 0
    each { |element| result += 1 }
    result
  end
end

In this example, we've implemented the #count method on a new DIYEnumerable module that we’ll include in our linked list. It starts a counter at zero and calls the #each method to add one to the counter for every loop. After looping over all elements, the method returns the resulting counter.

module DIYEnumerable
  # ...

  def map
    result = LinkedList.new
    each { |element| result = result << yield(element) }
    result
  end
end

The #map method is implemented similarly. Instead of keeping a counter, it uses an accumulator, which starts as an empty list. We'll loop over all elements in the list, and yield the passed block on each element. The result of each yield is appended to the accumulator list.

The method returns the accumulator after looping over all of the elements in the input list.

class LinkedList
  include DIYEnumerable

  #...
end

After including the DIYEnumerable in our LinkedList, we can test our newly added #count and #map methods.

irb> list = LinkedList.new(73, 12, 42)
=> [73, [12, [42]]]
irb> list.count
=> 3
irb> list.map { |element| element * 10 }
=> [420, [120, [730]]]

Both methods work! The #count method correctly counts the items in the list, and the #map method runs a block for each item and returns an updated list.

Reversed lists

However, the #map method seems to have reverted the list. That’s understandable, as the #<< method on our linked list class prepends items to the list instead of appending them, which is a feature of the recursive nature of linked lists.

For situations where it’s essential that the order of the list is retained, we need a way to reverse the list when mapping over it. Ruby implements Enumerable#reverse_each, which loops over an object in reverse. That which sounds like an excellent solution to our problem. Sadly, we can’t use an approach like that because our list is nested. We don’t know how long the list is until we loop over it entirely.

Instead of running the block over the list in reverse, we’ll add a version of #reverse_each that does this two steps. It first loops over the list to reverse it by creating a new list. After that, it runs the block over the reversed list.

module DIYEnumerable
  # ...

  def reverse_each(&block)
    list = LinkedList.new
    each { |element| list = list << element }
    list.each(&block)
  end

  def map
    result = LinkedList.new
    reverse_each { |element| result = result << yield(element) }
    result
  end
end

Now, we'll use #reverse_each in our #map method, to make sure it's returned in the correct order.

irb> list = LinkedList.new(73, 12, 42)
=> [73, [12, [42]]]
irb> list.map { |element| element * 10 }
=> [730, [120, [420]]]

It works! Whenever we call our #map method on a linked list, we'll get a new list back in the same order as the original.

Chaining Enumeration with Enumerators

Through the #each method implemented on our linked list class and the included DIYEnumerator, we can now loop both ways and map over linked lists.

irb> list.each { |x| p x }
73
12
42
irb> list.reverse_each { |x| p x }
42
12
73
irb> list.reverse_each.map { |x| x * 10 }
=> [420, [120, [730]]]

However, what if we need to map over a list in reverse? Since we now reverse the list before mapping over it, it always returns in the same order as the original list. We've already implemented both #reverse_each and #map, so we should be able to chain them together to be able to map backwards. Luckily, Ruby's Enumerator class can help with that.

Last time, we made sure to call Kernel#to_enum if the LinkedList#each method was called without a block. This allowed for chaining enumerable methods by returning an Enumerator object. To find out how the Enumerator class works, we’ll implement our own version.

class DIYEnumerator
  include DIYEnumerable

  def initialize(object, method)
    @object = object
    @method = method
  end

  def each(&block)
    @object.send(@method, &block)
  end
end

Like Ruby's Enumerator, our enumerator class is a wrapper around a method on an object. By bubbling up to the wrapped object, we can chain enumeration methods.

This works because a DIYEnumerator instance is enumerable itself. It implements #each by calling the wrapped object, and includes the DIYEnumerable module so all enumerable methods can be called on it.

We’ll return an instance of our DIYEnumerator class if no block is passed to the LinkedList#each method.

class LinkedList
  # ...

  def each(&block)
    if block_given?
      yield @head
      @tail.each(&block) if @tail
    else
      DIYEnumerator.new(self, :each)
    end
  end
end

Using our own enumerator, we can now chain enumeration to get the result in the original order without having to pass an empty block to the #reverse_each method call.

irb> list = LinkedList.new(73, 12, 42)
=> [73, [12, [42]]]
irb> list.map { |element| element * 10 }
=> [420, [120, [730]]]

Eager and lazy enumeration

This concludes our peek into the implementation of the Enumerable module and the Enumerator class for now. We've learned how some of the enumerable methods work and how an enumerator helps chaining enumeration by wrapping an enumerable object.

There are some issues with our approach, though. By its nature, enumeration is eager, meaning it loops over the list as soon as one of the enumerable methods is called on it. While that's fine in most cases, mapping over a list in reverse reverses the list twice, which should be unnecessary.

To lower the number of loops, we could employ Enumerator::Lazy to delay looping to the last moment, and have duplicate list reversing cancel itself out.

We'll have to save that for a future episode, though. Don't want to miss that, and further expeditions into Ruby's magical inner workings? Subscribe to the Ruby Magic e-mail newsletter, to get new articles delivered to your inbox as soon as they're published.

Iteration, recursion, and tail-call optimization in Elixir

Jeff Kreeftmeijer — Tue, 19 Mar 2019 13:52:37 +0000

Elixir uses recursion for looping over data structures like lists. Although most of it's hidden away through higher-level abstractions on the Enum class, in some cases writing a recursive function yourself can be more performant. In this episode of Elixir Alchemy, we’ll try to find some of these cases.

Along the way, we’ll learn about body-recursive and tail-recursive functions. Although the latter is often touted as being faster, we’ll also look at cases where that’s not necessarily true. Let’s dive right in!

Enumeration

Elixir provides functions on the Enum module to enumerate over collections.

def sum_numbers1(list) do
  list
  |> Enum.filter(&is_number/1)
  |> Enum.reduce(0, fn n, sum -> n + sum end)
end

This example takes a list and returns the sum of all numbers in that list. Because there might be non-numeric items in the input list, it uses Enum.filter/2 to select only the items that is_number/1 returns true on. After that, the remaining values are added together through Enum.reduce/3.

sum_numbers1([1, 2, "three", 4, %{}]) # => 7

While this solution works, it iterates over the whole list twice to get to the result. To make this more performant, we might instead choose to write a recursive function that can do this in one go.

Recursion

A recursive function can do both tasks (removing the non-numeric items and adding the rest together) in one run. It will call itself for every item in the list, and use pattern matching to decide what to do with each item.

# 1
def sum_numbers2([head | tail]) when is_number(head) do
  sum_numbers2(tail) + head
end

# 2
def sum_numbers2([_head | tail]) do
  sum_numbers2(tail)
end

# 3
def sum_numbers2([]) do
  0
end

Instead of using the functions provided by the Enum module, this solution calls itself until the list is empty. It does so using three function heads:

When the first item in the list (the head) is a number, we'll call sum_numbers2/1 with the rest of list (anything but the head, called the tail). This call returns a number we'll add our current head to.
When the head is not a number, we'll drop it by calling the sum_numbers2/1 function with just the tail.
When the list is empty, we'll return 0.

sum_numbers2([1, 2, "three", 4, %{}]) # => 7

When calling this function with [1, 2, "three", 4, %{}], the sum_numbers2/1 function is called repeatedly in the following order to get to the result:

sum_numbers2([1, 2, "three", 4, %{}])
sum_numbers2([2, "three", 4, %{}]) + 1
sum_numbers2(["three", 4, %{}]) + 1 + 2
sum_numbers2([4, %{}]) + 1 + 2
sum_numbers2([%{}]) + 1 + 2 + 4
sum_numbers2([]) + 1 + 2 + 4
0 + 1 + 2 + 4

This list shows the how the function is simplified until we get to a result, which shows the function being called six times. Once for each item, plus once more for the empty list at the end.

Because the function calls itself for each iteration, each item in the list causes a stack frame to be added to the call stack. That’s because each item warrants a call to a function, which needs to be executed to claim its result. Adding a stack frame to the call stack requires some memory to be allocated, and can cause some overhead.

Tail recursion and tail-call optimization

To keep the memory footprint to a minimum, some languages—like Erlang and thus Elixir—implement tail-call optimization. With a small rewrite of our code, we can prevent the stack frame being added and that memory allocated.

# 1
def sum_numbers3(list) do
  do_sum_numbers3(list, 0)
end

# 2
defp do_sum_numbers3([head | tail], sum) when is_number(head) do
  do_sum_numbers3(tail, sum + head)
end

# 3
defp do_sum_numbers3([_head | tail], sum) do
  do_sum_numbers3(tail, sum)
end

# 4
defp do_sum_numbers3([], sum) do
  sum
end

This example is yet another implementation of the function from before. However, this example is tail-recursive, meaning it doesn’t need to await a call to itself before continuing. It does so by keeping an accumulator (sum) that keeps the current value instead of stacking function calls.

The sum_numbers3/1 function is the public function, which calls the private do_sum_numbers3/2 function with the passed list and an accumulator of 0 to start with.
Much like the previous example, do_sum_numbers3/2's first function head matches lists with a numeric head. It calls itself with the list's tail, and the head added to the accumulator.
When the head is not a number, the third function head drops it by calling itself with the tail and the current accumulator, without changing anything.
Finally, the exit clause returns the accumulator.

By calling itself at the end of the function and passing the accumulator with all calculated values, the Erlang VM can execute a trick called tail-call optimization, which allows it to circumvent adding new stack frames. Instead, it uses the current frame by jumping back up to the beginning of the function.

Tail call optimization allows functions calling themselves without running into stack problems.

def sleep, do: sleep

This example implements a function that continually calls itself. Without tail-call optimization, this function would produce a stack error.

Which is faster?

We've written three implementations of the same function. The first used Enum.filter/2 and Enum.reduce/3 to filter and sum the list, and iterated over the list twice. To fix that, we used a recursive function that did it in one go, which we further improved using tail-call optimization.

letters = Enum.map(?a..?z, fn x -> <<x::utf8>> end)
numbers = Enum.to_list(0..10_000)
list = Enum.shuffle(letters ++ numbers)

Benchee.run(
  %{
    "Enum.filter/2 and Enum.reduce/3" => fn -> Recursion.sum_numbers1(list) end,
    "Body-recursive" => fn -> Recursion.sum_numbers2(list) end,
    "Tail-recursive" => fn -> Recursion.sum_numbers3(list) end
  },
  time: 10,
  memory_time: 2
)

To benchmark our solutions, we'll use Benchee. We'll prepare a shuffled list of strings and numbers for each function to sum for ten seconds.

Name                                      ips        average  deviation         median         99th %
Tail-recursive                       107.35 K        9.32 μs    ±21.39%           9 μs          14 μs
Body-recursive                        55.65 K       17.97 μs   ±662.77%          14 μs          34 μs
Enum.filter/2 and Enum.reduce/3       20.86 K       47.94 μs    ±51.46%          46 μs          85 μs

Comparison:
Tail-recursive                       107.35 K
Body-recursive                        55.65 K - 1.93x slower
Enum.filter/2 and Enum.reduce/3       20.86 K - 5.15x slower

Memory usage statistics:

Name                               Memory usage
Tail-recursive                              0 B
Body-recursive                              0 B
Enum.filter/2 and Enum.reduce/3         16064 B

In this test on this machine, we see that the body-recursive version is almost three times as fast as the original implementation that used Enum.filter/2 and Enum.reduce/3. The tail-recursive version was almost twice as fast ad the body-recursive one.

Is tail-call recursion always faster?

While the results of that benchmark look quite convincing, tail-recursion isn't always faster than body recursion. In fact, that's one of the 7 myths of Erlang performance.

While tail-recursive calls are usually faster for list reductions—like the example we’ve seen before—body-recursive functions can be faster in some situations. That's often true when mapping over a list, where the function takes a list and returns a list without reducing it to a single value.

def double_numbers1(list) do
  list
  |> Enum.filter(&is_number/1)
  |> Enum.map(fn n -> n * 2 end)
end

def double_numbers2([]) do
  []
end

def double_numbers2([head | tail]) when is_number(head) do
  [head * 2 | double_numbers2(tail)]
end

def double_numbers2([_head | tail]) do
  double_numbers2(tail)
end

def double_numbers3(list) do
  list
  |> do_double_numbers3([])
  |> Enum.reverse()
end

defp do_double_numbers3([], acc) do
  acc
end

defp do_double_numbers3([head | tail], acc) when is_number(head) do
  do_double_numbers3(tail, [head * 2 | acc])
end

defp do_double_numbers3([_head | tail], acc) do
  do_double_numbers3(tail, acc)
end

This example is a lot like the example we've seen before, but instead of adding all numbers together and reducing them to a single number, the double_numbers/1 function doubles all numbers and returns them in a list.

Like before, we have three implementations. The first uses Enum.filter/2 and Enum.map/2 to iterate over the list twice, the second is body-recursive and the last is tail-recursive. Before returning, the tail-recursive function needs to reverse the list, because the values get prepended to the accumulator.

Note: Check out the example project for a comparison of more possible implementations, like list comprehensions and a tail-recursive version that doesn't reverse the list.

Name                                   ips        average  deviation         median         99th %
body-recursive                     36.86 K       27.13 μs    ±39.82%          26 μs          47 μs
tail-recursive                     27.46 K       36.42 μs  ±1176.74%          27 μs          80 μs
Enum.filter/2 and Enum.map/2       12.62 K       79.25 μs   ±194.81%          62 μs         186 μs

Comparison:
body-recursive                     36.86 K
tail-recursive                     27.46 K - 1.34x slower
Enum.filter/2 and Enum.map/2       12.62 K - 2.92x slower

Memory usage statistics:

Name                            Memory usage
body-recursive                      15.64 KB
tail-recursive                      20.09 KB - 1.28x memory usage
Enum.filter/2 and Enum.map/2        31.33 KB - 2.00x memory usage

When running a benchmark for each of these implementations, we can see that the body-recursive version is fastest in this case. Having to reverse the list in the tail-recursive version negates the improved performance tail-call optimization adds in this specific case.

As always, it depends

This concludes our look into recursion in Elixir. As a rule of thumb; tail-recursive functions are faster if they don't need to reverse the result before returning it. That's because that requires another iteration over the whole list. Tail-recursive functions are usually faster at reducing lists, like our first example.

Which is the best approach depends on the situation. For mission-critical loops, writing a benchmark to measure which solution is faster is usually your best bet, as it's not immediately obvious which will perform better.

To learn more about recursion, also be sure to read this overview of the available methods, and when to use which. If you liked this article, don't forget to subscribe to the mailing list if you'd like to read more Elixir Alchemy!

Unraveling Classes, Instances and Metaclasses in Ruby

Jeff Kreeftmeijer — Tue, 05 Feb 2019 13:57:50 +0000

Welcome to a new episode of Ruby Magic! This month's edition is all about metaclasses, a subject sparked by a discussion between two developers (Hi Maud!).

Through examining metaclasses, we'll learn how class and instance methods work in Ruby. Along the way, discover the difference between defining a method by passing an explicit "definee" and using class << self or instance_eval. Let's go!

Class Instances and Instance Methods

To understand why metaclasses are used in Ruby, we'll start by examining what the differences are between instance- and class methods.

In Ruby, a class is an object that defines a blueprint to create other objects. Classes define which methods are available on any instance of that class.

Defining a method inside a class creates an instance method on that class. Any future instance of that class will have that method available.

class User
  def initialize(name)
    @name = name
  end

  def name
    @name
  end
end

user = User.new('Thijs')
user.name # => "Thijs"

In this example, we create a class named User, with an instance method named #name that returns the user's name. Using the class, we then create a class instance and store it in a variable named user. Since user is an instance of the User class, it has the #name method available.

A class stores its instance methods in its method table. Any instance of that class refers to its class’ method table to get access to its instance methods.

Class Objects

A class method is a method that can be called directly on the class without having to create an instance first. A class method is created by prefixing its name with self. when defining it.

A class is itself an object. A constant refers to the class object, so class methods defined on it can be called from anywhere in the application.

class User
  # ...

  def self.all
    [new("Thijs"), new("Robert"), new("Tom")]
  end
end

User.all # => [#<User:0x00007fb01701efb8 @name="Thijs">, #<User:0x00007fb01701ef68 @name="Robert">, #<User:0x00007fb01701ef18 @name="Tom">]

Methods defined with a self.-prefix aren’t added to the class’s method table. They’re instead added to the class’ metaclass.

Metaclasses

Aside from a class, each object in Ruby has a hidden metaclass. Metaclasses are singletons, meaning they belong to a single object. If you create multiple instances of a class, they’ll share the same class, but they’ll all have separate metaclasses.

thijs, robert, tom = User.all

thijs.class # => User
robert.class # => User
tom.class # => User

thijs.singleton_class  # => #<Class:#<User:0x00007fb71a9a2cb0>>
robert.singleton_class # => #<Class:#<User:0x00007fb71a9a2c60>>
tom.singleton_class    # => #<Class:#<User:0x00007fb71a9a2c10>>

In this example, we see that although each of the objects has the class User, their singleton classes have different object IDs, meaning they’re separate objects.

By having access to a metaclass, Ruby allows adding methods directly to existing objects. Doing so won’t add a new method to the object’s class.

robert = User.new("Robert")

def robert.last_name
  "Beekman"
end

robert.last_name # => "Beekman"
User.new("Tom").last_name # => NoMethodError (undefined method `last_name' for #<User:0x00007fe1cb116408>)

In this example, we add a #last_name to the user stored in the robert variable. Although robert is an instance of User, any newly created instances of User won’t have access to the #last_name method, as it only exists on robert’s metaclass.

What Is `self`?

When defining a method and passing a receiver, the new method is added to the receiver’s metaclass, instead of adding it to the class’ method table.

tom = User.new("Tom")

def tom.last_name
  "de Bruijn"
end

In the example above, we've added #last_name directly on the tom object, by passing tom as the receiver when defining the method.

This is also how it works for class methods.

class User
  # ...

  def self.all
    [new("Thijs"), new("Robert"), new("Tom")]
  end
end

Here, we explicitly pass self as a receiver when creating the .all method. In a class definition, self refers to the class (User in this case), so the .all method gets added to User's metaclass.

Because User is an object stored in a constant, we’ll access the same object—and the same metaclass—whenever we reference it.

Opening the Metaclass

We’ve learned that class methods are methods in the class object’s metaclass. Knowing this, we’ll look at some other techniques of creating class methods that you might have seen before.

`class << self`

Although it has gone out of style a bit, some libraries use class << self to define class methods. This syntax trick opens up the current class's metaclass and interacts with it directly.

class User
  class << self
    self # => #<Class:User>

    def all
      [new("Thijs"), new("Robert"), new("Tom")]
    end
  end
end

User.all # => [#<User:0x00007fb01701efb8 @name="Thijs">, #<User:0x00007fb01701ef68 @name="Robert">, #<User:0x00007fb01701ef18 @name="Tom">]

This example creates a class method named User.all by adding a method to User's metaclass. Instead of explicitly passing a receiver for the method as we saw previously, we set self to User's metaclass instead of User itself.

As we learned before, any method definition without an explicit receiver gets added as an instance method of the current class. Inside the block, the current class is User's metaclass (#<Class:User>).

`instance_eval`

Another option is by using instance_eval, which does the same thing with one major difference. Although the class's metaclass receives the methods defined in the block, self remains a reference to the main class.

class User
  instance_eval do
    self # => User

    def all
      [new("Thijs"), new("Robert"), new("Tom")]
    end
  end
end

User.all # => [#<User:0x00007fb01701efb8 @name="Thijs">, #<User:0x00007fb01701ef68 @name="Robert">, #<User:0x00007fb01701ef18 @name="Tom">]

In this example, we define an instance method on User's metaclass just like before, but self still points to User. Although it usually points to the same object, the "default definee" and self can point to different objects.

What We've Learned

We've learned that classes are the only objects that can have methods, and that instance methods are actually methods on an object's metaclass. We know that class << self simply swaps self around to allow you to define methods on the metaclass, and we know that instance_eval does mostly the same thing (but without touching self).

Although you won't explicitly work with metaclasses, Ruby uses them extensively under the hood. Knowing what happens when you define a method can help you understand why Ruby behaves like it does (and why you have to prefix class methods with self.).

Thanks for reading. If you liked what you read, you might like to subscribe to Ruby Magic to receive an e-mail when we publish a new article about once a month.

Serving Plug: Building an Elixir HTTP server from scratch

Jeff Kreeftmeijer — Tue, 22 Jan 2019 14:06:38 +0000

Welcome back to another edition of Elixir Alchemy! In our continued quest to find out what’s happening under the hood, we'll take a deep dive into HTTP servers in Elixir.

To understand how HTTP servers work, we'll implement a minimal example of one that can run a Plug application. We’ll learn about decoding requests and encoding responses, as well as how Plug interacts with the web server by building a minimal subset of an HTTP server that can accept HTTP requests and run a Plug application.

-> The HTTP server we’re building is for educational purposes. We won’t build a production-ready HTTP server. If you're looking for one that is, please try cowboy, which is the default choice of HTTP server in Elixir applications.

HTTP over TCP

We’ll start with the fundamentals. HTTP is a protocol that commonly uses TCP to transport requests and responses between an HTTP client—like a web browser—and a web server.

Erlang provides the :gen_tcp module that can be used to start a TCP socket that receives and transmits data. We'll use that library as the basis of our server.

# lib/http.ex
defmodule Http do
  require Logger

  def start_link(port: port) do
    {:ok, socket} = :gen_tcp.listen(port, active: false, packet: :http_bin, reuseaddr: true)
    Logger.info("Accepting connections on port #{port}")

    {:ok, spawn_link(Http, :accept, [socket])}
  end

  def accept(socket) do
    {:ok, request} = :gen_tcp.accept(socket)

    spawn(fn ->
      body = "Hello world! The time is #{Time.to_string(Time.utc_now())}"

      response = """
      HTTP/1.1 200\r
      Content-Type: text/html\r
      Content-Length: #{byte_size(body)}\r
      \r
      #{body}
      """

      send_response(request, response)
    end)

    accept(socket)
  end

  def send_response(socket, response) do
    :gen_tcp.send(socket, response)
    :gen_tcp.close(socket)
  end

  def child_spec(opts) do
    %{id: Http, start: {Http, :start_link, [opts]}}
  end
end

In this example, we’ve created a TCP server that responds to every request with the current time in an HTTP response.

We start a socket to listen to the passed in port in start_link/1, and we'll spawn accept/1 in a new process that waits until a request comes in over the socket by calling :gen_tcp.accept/1.

When it does, we put it into the request variable and create a response to send to the client. In this case, we'll be sending a response that shows the current time.

Building HTTP responses
HTTP/1.1 200\r\nContent-Type: text/html\r\n\r\n\Hello world! The time is 14:45:49.058045
An HTTP response contains a couple of parts:

A status line, with the protocol version (HTTP/1.1) and a response code (200)

A carriage return, followed by a line feed (\r\n) to split the status line from the rest of the response

(Optional) header lines (Content-Type: text/html), separated by CRLFs

A double CRLF, to separate the headers from the response body

The response body that will be shown in the browser (Hello world! The time is 14:45:49.058045)

We pass the body we built to send_response/2, which takes care of sending the response over the socket and finally closing the socket connection.

We spawn a process for each request so the server can call accept/1 again to accept new requests. This way, we can respond to requests in parallel, instead of subsequent requests having to wait for previous ones to complete being processed.

Running the Server

Let's try it out. We'll use a supervisor to run our HTTP server to make sure it's restarted immediately when if it fails.

Our server implementation has a child_spec/1 function that specifies how it should be started. It states that it should call the Http.start/1 function with the passed options, which will return the newly spawned process' ID.

# lib/http.ex
defmodule Http do
  # ...

  def child_spec(opts) do
    %{id: Http, start: {Http, :start_link, [opts]}}
  end
end

Because of that, we can add it to the list of children managed by the supervisor in lib/http/application.ex.

# lib/http/application.ex
defmodule Http.Application do
  @moduledoc false
  use Application

  def start(_type, _args) do
    children = [
      {Http, port: 8080}
    ]

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

We pass {Http, port: 8080} as one of our supervisor's children to start the server at port 8080 when the application is started.

$ mix run --no-halt
19:39:29.454 [info]  Accepting connections on port 8080

If we start the server and use our browser to send a request, we can see that it indeed returns the current time.

Plug

Now that we know how a web server works, let's take it to the next level. Our current implementation has the response hard-coded into the server. To allow our web server to run different apps, we'll move the app out into a separate Plug module.

# lib/current_time.ex
defmodule CurrentTime do
  import Plug.Conn

  def init(options), do: options

  def call(conn, _opts) do
    conn
    |> put_resp_content_type("text/html")
    |> send_resp(200, "Hello world! The time is #{Time.to_string(Time.utc_now())}")
  end
end

The CurrentTime module defines a call/2 function that takes the passed in %Plug.Conn struct. It then sets the response content type to "text/html" before sending the "Hello world!" message—together with the current time—back as a response.

Our new module behaves the same as the web server example, but it's detached from the web server. Because of Plug, we could swap out servers without having to change the application's code, and we can also change the application without having to touch the web server.

Writing a Plug Adapter

To make sure our web server can communicate with our web application, we need to build a %Plug.Conn{} struct to pass to CurrentTime.call/2. We'll also need to turn the sent response into a string that our web server can send back over the socket.

To do this, we'll create an adapter that handles the communication between our Plug app and our web server.

# lib/http/adapter.ex
defmodule Http.PlugAdapter do
  def dispatch(request, plug) do
    %Plug.Conn{
      adapter: {Http.PlugAdapter, request},
      owner: self()
    }
    |> plug.call([])
  end

  def send_resp(socket, status, headers, body) do
    response = "HTTP/1.1 #{status}\r\n#{headers(headers)}\r\n#{body}"

    Http.send_response(socket, response)
    {:ok, nil, socket}
  end

  def child_spec(plug: plug, port: port) do
    Http.child_spec(port: port, dispatch: &dispatch(&1, plug))
  end

  defp headers(headers) do
    Enum.reduce(headers, "", fn {key, value}, acc ->
      acc <> key <> ": " <> value <> "\n\r"
    end)
  end
end

Instead of responding directly from Http.accept/2, we'll use our adapter's dispatch/2 function to build a %Plug.Conn{} struct and pass that to our plug's call/2 function.

In the %Plug.Conn{}, we'll set the :adapter to link to our Adapter module, and then pass the socket the response that should be sent over. This ensures that the Plug app knows which module to call send_resp/4 on.

Our adapter's send_resp/4 takes the socket connection, the response status, a list of headers and a body, which are all prepared by the Plug application. It uses the passed in arguments to build the response and calls out to Http.send_response/2 that we've implemented before.

The child_spec/1 for our adapter returns the child_spec/1 for the Http module. This causes the web server to start when we supervise our adapter. We'll pass the dispatch function as the dispatch so that it can be called by our web server when it receives a response.

# lib/http/application.ex
defmodule Http.Application do
  @moduledoc false
  use Application

  def start(_type, _args) do
    children = [
      {Http.PlugAdapter, plug: CurrentTime, port: 8080}
    ]

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

Instead of starting Http in our application module, we'll start Http.PlugAdapter, which will take care of setting the plug, preparing the dispatch function and starting the web server.

# lib/http.ex
defmodule Http do
  require Logger

  def start_link(port: port, dispatch: dispatch) do
    {:ok, socket} = :gen_tcp.listen(port, active: false, packet: :http_bin, reuseaddr: true)
    Logger.info("Accepting connections on port #{port}")

    {:ok, spawn_link(Http, :accept, [socket, dispatch])}
  end

  def accept(socket, dispatch) do
    {:ok, request} = :gen_tcp.accept(socket)

    spawn(fn ->
      dispatch.(request)
    end)

    accept(socket, dispatch)
  end

  # ...
end

Since we now handle requests in our Plug, we can remove most of the code in Http.accept/2. The Http.start_link/2 function will now receive the dispatch function from the adapter, which is used to send the request to in Http.accept/2.

$ mix run --no-halt
19:39:29.454 [info]  Accepting connections on port 8080

Running the server again, everything still works exactly as before. However, our HTTP server, web application and Plug adapter are now three separate modules.

Swapping out Plug Applications

Because our server is now separate from our adapter and web application, we can swap the Plug out to run another application on the server. Let's give that a shot.

# mix.exs
defmodule Http.MixProject do
  # ...

  defp deps do
    [
      {:plug_octopus, github: "jeffkreeftmeijer/plug_octopus"},
      {:plug, "~> 1.7"}
    ]
  end
end

In our mix.exs file, we add :plug_octopus as a dependency.

# lib/http/application.ex
defmodule Http.Application do
  @moduledoc false
  use Application

  def start(_type, _args) do
    children = [
      {Http.PlugAdapter, plug: Plug.Octopus, port: 8080}
    ]

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

We then swap CurrentTime for Plug.Octopus in our Http.Application module. Starting the server and visiting http://localhost:8080 now shows an octopus!

However, clicking the flip! and crash! buttons doesn't do anything and any URL that's called shows the same page. That's because we skipped over parsing the requests altogether. Since we don't read the requests, we'll always pass the same response back. Let's fix that.

Parsing Requests

To read requests, we'll need to read the response from the socket. Thanks to the http_bin option that we're passing when calling :gen_tcp.listen/2, the request is returned in a format we can pattern match on.

# lib/http.ex
defmodule Http do
  # ...

  def read_request(request, acc \\ %{headers: []}) do
    case :gen_tcp.recv(request, 0) do
      {:ok, {:http_request, :GET, {:abs_path, full_path}, _}} ->
        read_request(request, Map.put(acc, :full_path, full_path))

      {:ok, :http_eoh} ->
        acc

      {:ok, {:http_header, _, key, _, value}} ->
        read_request(
          request,
          Map.put(acc, :headers, [{String.downcase(to_string(key)), value} | acc.headers])
        )

      {:ok, line} ->
        read_request(request, acc)
    end
  end

  # ...
end

The Http.read_request/2 function takes a socket connection and will be called from the dispatch function. It will keep calling :gen_tcp.recv/2 to accept lines from the request until it receives an :http_eoh response, indicating the end of the requests headers.

We match on the :http_request line, which includes the full request path. We'll use that to extract the path and URL parameters later. We'll also match on all :http_header lines, which we convert to a list we can pass to our Plug application later.

# lib/http/adapter.ex
defmodule Http.PlugAdapter do
  def dispatch(request, plug) do
    %{full_path: full_path} = Http.read_request(request)

    %Plug.Conn{
      adapter: {Http.PlugAdapter, request},
      owner: self(),
      path_info: path_info(full_path),
      query_string: query_string(full_path)
    }
    |> plug.call([])
  end

  # ...

  defp headers(headers) do
    Enum.reduce(headers, "", fn {key, value}, acc ->
      acc <> key <> ": " <> value <> "\n\r"
    end)
  end

  defp path_info(full_path) do
    [path | _] = String.split(full_path, "?")
    path |> String.split("/") |> Enum.reject(&(&1 == ""))
  end

  defp query_string([_]), do: ""
  defp query_string([_, query_string]), do: query_string

  defp query_string(full_path) do
    full_path
    |> String.split("?")
    |> query_string
  end
end

We call Http.read_request/1 from Http.PlugAdapter.dispatch/2. Having the full_path, we can extract the path_info (a list of path segments), and query_string (all URL parameters after the "?"). We add these to the %Plug.Conn{} to have our Plug app handle the rest.

Restarting the server, we can now flip and crash the lobster.

A Minimal Web Server Example that flips and crashes

With everyone in place, and no screws on the floor, our project to look into HTTP servers in Elixir is done. We've implemented a web server that extracts data from requests and used it to send a request to a Plug application. It even has concurrency included: since each request spawns a separate process, our web server can handle multiple concurrent users.

There's more to HTTP servers than we've shown in this article, but we hope implementing one from the ground up gave you some insight into how a web server could work.

Check out the finished project if you'd like to review the code, and don't forget to subscribe to the mailing list if you'd like to read more Elixir Alchemy!

Forem: Jeff Kreeftmeijer

How To Reduce Reductions in Elixir

Our Key Components

Elixir's profile.eprof Mix Task

AppSignal's instrument Function

Profiling our instrument Function

Interpreting Profiling Data

Looking for Reductions

Reducing Calls

Removing Unnecessary Calls

The Final Profile

Sample AppSignal's Performance Monitoring

Emacs package management with straight.el and use-package

Straight.el

Installation

Usage

Use-package

Installation

Using straight.el with use-package

Usage

Summary

Footnotes

Combine Git repositories with unrelated histories

References

Testing input and output in Rust command line applications

Standard Streams

Stdin, Stdout and Stderr in Rust

Abstraction using the Read and Write traits

Embrace email, mute Slack. A policy for handling incoming messages

Funneling everything through email

Managing Slack direct messages and unreads

Multiplayer Go with Elixir's Registry, PubSub and dynamic supervisors

Where We Left Off

Dynamically Supervised GenServers

Pids, Atoms and the Registry

Switching to Game Processes

Multiplayer URL Sharing

Broadcasting Moves to All Clients

What's Next?

Building the Go Game in Elixir: Time Travel and the Ko Rule

Onward!

Time travel preparations

Time Travel

Branching off in History

Disabling Inapplicable Undo and Redo Buttons

The Ko Rule

Time travel and the ko rule

Building and Playing the Go Game with Phoenix LiveView

Let’s Go!

The GameLive Module

Making Moves

Preventing Illegal Moves

Capturing Stones

Scoring, History and the Ko Rule

Inside Enumeration in Ruby

Linked Lists

Enumerable Methods

Reversed lists

Chaining Enumeration with Enumerators

Eager and lazy enumeration

Iteration, recursion, and tail-call optimization in Elixir

Enumeration

Recursion

Tail recursion and tail-call optimization

Which is faster?

Is tail-call recursion always faster?

As always, it depends

Unraveling Classes, Instances and Metaclasses in Ruby

Class Instances and Instance Methods

Class Objects

Metaclasses

What Is self?

Opening the Metaclass

class << self

instance_eval

What We've Learned

Serving Plug: Building an Elixir HTTP server from scratch

HTTP over TCP

Building HTTP responses

Running the Server

Elixir's `profile.eprof` Mix Task

AppSignal's `instrument` Function

Profiling our `instrument` Function

`Stdin`, `Stdout` and `Stderr` in Rust

Abstraction using the `Read` and `Write` traits

The `GameLive` Module

What Is `self`?

`class << self`

`instance_eval`