エンジニアのソフトウェア的愛情

または私は如何にして心配するのを止めてプログラムを・愛する・ようになったか

Rustlerでコンウェイの Game of Life を書く

かつてセルラオートマトンに魅了されていた時期がありまして。

熱を上げていた時期はそれほど長くはなかったのですが、その後も伴奏のように背景でずっと鳴り続けていました。

最近、セルラオートマトンの新しい本を手に入れて、再び熱が上がってきています。

まずは手始めに。 このところ気に入って使っているElixirと、高速化のためのRustを使って、コンウェイGame of Lifeを再実装してみることにしました。

心臓部をRustで実装する

「Elixirと、高速化のためのRust」、と言っているそばから心臓部はRustでの実装です。

ElixirからRustの実装を利用するにならrustler。 というわけで、rustlerで生成した雛形にGame of Lifeの心臓部、現在の状態から次の状態を生成する部分をRustで実装します。

hex.pm

// native/game_of_life_nif/src/lib.rs

use rustler::Binary;
use rustler::OwnedBinary;

#[rustler::nif]
fn next(field: Binary, width: usize, height: usize) -> OwnedBinary {
    let mut next_field = OwnedBinary::new(width * height).unwrap();

    next_field.fill(0);
    for y in 0..height {
        for x in 0..width {
            let mut count = 0u8;
            let left = (x + width - 1) % width;
            let right = (x + 1) % width;
            let top = (y + height - 1) % height;
            let bottom = (y + 1) % height;

            count += field[top * width + left];
            count += field[top * width + x];
            count += field[top * width + right];

            count += field[y * width + left];
            count += field[y * width + right];

            count += field[bottom * width + left];
            count += field[bottom * width + x];
            count += field[bottom * width + right];

            if field[y * width + x] == 0 {
                next_field[y * width + x] = if count == 3 { 1 } else { 0 };
            } else {
                next_field[y * width + x] = if count == 2 || count == 3 { 1 } else { 0 };
            }
        }
    }

    next_field
}

rustler::init!("Elixir.GameOfLife.Nif", [next]);

現在の状態をあらわすバイナリと幅と高さを受け取り、次の状態をあらわすバイナリを返します。

右と左、上と下が接続している、いわゆるトーラスとしてあつかっています。 Rustも学習途上で、naiveな実装になっていますが、そこはご容赦を。

次にRustの実装を読み込み、関数を呼び出せるようにするためのElixirのモジュールを実装します。

# lib/game_of_life/nif.ex

defmodule GameOfLife.Nif do
  @moduledoc false
  use Rustler, otp_app: :game_of_life, crate: :game_of_life_nif

  def next(_field, _width, _height), do: :erlang.nif_error(:nif_not_loaded)
end

きちんと機能するか試してみます。

次のようなスクリプトを用意します。 見ての通りblinkerの実装です。

# blinker.exs

~w(
  0 0 0 0 0
  0 0 1 0 0
  0 0 1 0 0
  0 0 1 0 0
  0 0 0 0 0
)
|> Enum.into(<<>>, &<<String.to_integer(&1)>>)
|> GameOfLife.Nif.next(5, 5)
|> String.to_charlist()
|> Enum.chunk_every(5)
|> IO.inspect()

これを実行すると、次の状態をえられることが確認できました。

$ mix run blinker.exs
[
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0]
]

入力しやすくする、出力を見やすくする

肝となる部分は GameOfLife.Nif.next/3 ですべてなので、結果のバイナリを次の段の入力にすれば、繰り返した分だけの世代の状態をえることができます。

とはいえ入力や出力を、もっと人が扱いやす形にしたい。

と、いうわけで。 文字の並びから入力となるバイナリを生成するシジルと、結果を文字の並びとして出力する関数を追加してみました。

ついでに GameOfLife.Nif.next/3 へ移譲して GameOfLife.next/3 という自然な記述で呼び出せるようにしました。

defmodule GameOfLife do
  defdelegate next(field, width, height), to: GameOfLife.Nif

  defmacro sigil_F({:<<>>, _meta, [string]}, _) do
    quote bind_quoted: [string: string] do
      for <<c <- string>>, c not in ' \r\n\t', into: <<>> do
        case c do
          ?@ -> <<1>>
          _ -> <<0>>
        end
      end
    end
  end

  def show(field, width, height) do
    for <<c <- field>> do
      case c do
        1 -> "@ "
        _ -> '. '
      end
    end
    |> Stream.chunk_every(width)
    |> Enum.each(&IO.puts/1)

    field
  end
end

先ほどの blinker を次のように書き換えます。

~F は、@1 に、それ以外の文字を 0 としてバイナリを生成します。 空白文字(空白、改行、タブ)は無視するので、自由にスペーシングや改行を含めることができます。

show/3 は、バイナリの内容の 0.1@ で、指定された幅と高さで出力します。 また入力のバイナリをそのまま戻り値とするので、パイプで繋げて次の段の入力にすることができます。

# blinker.exs

import GameOfLife

~F(
  . . . . .
  . . @ . .
  . . @ . .
  . . @ . .
  . . . . .
)
|> show(5, 5)
|> GameOfLife.next(5, 5)
|> show(5, 5)
|> GameOfLife.next(5, 5)
|> show(5, 5)

実行。

$ mix run blinker.exs
. . . . . 
. . @ . . 
. . @ . . 
. . @ . . 
. . . . . 
. . . . . 
. . . . . 
. @ @ @ . 
. . . . . 
. . . . . 
. . . . . 
. . @ . . 
. . @ . . 
. . @ . . 
. . . . . 

定番のgliderも。

# glider.exs

import GameOfLife

~F(
  . @ . . .
  . . @ . .
  @ @ @ . .
  . . . . .
  . . . . .
)
|> show(5, 5)
|> GameOfLife.next(5, 5)
|> show(5, 5)
|> GameOfLife.next(5, 5)
|> show(5, 5)
|> GameOfLife.next(5, 5)
|> show(5, 5)
|> GameOfLife.next(5, 5)
|> show(5, 5)
|> GameOfLife.next(5, 5)
|> show(5, 5)
|> GameOfLife.next(5, 5)
|> show(5, 5)

実行。

$ mix run glider.exs
. @ . . . 
. . @ . . 
@ @ @ . . 
. . . . . 
. . . . . 
. . . . . 
@ . @ . . 
. @ @ . . 
. @ . . . 
. . . . . 
. . . . . 
. . @ . . 
@ . @ . . 
. @ @ . . 
. . . . . 
. . . . . 
. @ . . . 
. . @ @ . 
. @ @ . . 
. . . . . 
. . . . . 
. . @ . . 
. . . @ . 
. @ @ @ . 
. . . . . 
. . . . . 
. . . . . 
. @ . @ . 
. . @ @ . 
. . @ . . 
. . . . . 
. . . . . 
. . . @ . 
. @ . @ . 
. . @ @ . 

悪くない感じ。

最初に書いたようにnaiveな実装なので、ElixirやRustの利点を活かした実装 − 複数のプロセスで処理するとか − をしてみたいと考えています。

いつか読むはずっと読まない:ライフゲイム

en.wikipedia.org

John Horton Conway FRS (26 December 1937 – 11 April 2020) was an English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory.

...

On 11 April 2020, at age 82, he died of complications from COVID-19.

熱を上げるきっかけの一つになった本(の新装版)。