ZEAM開発ログ v.0.4.0 型多相かつ型安全なNIFをC言語で書いてみる

はじめに

ZACKY こと山崎進です。今回から micro Elixir / ZEAM の開発に向けて新シリーズです。micro Elixir / ZEAM 構想についてはこちらの資料をご覧ください。

「耐障害性が高くマルチコア性能を最大限発揮できるElixir(エリクサー)を学んでみよう」

「ZEAM開発ログ 目次」はこちら

さて本題

今回から新シリーズということで，コード生成について検討してみたいと思います。まず最初は算術演算について型多相で型安全なコードを記述してみたいと思います。

2018/09/11 追記

Dai MIKURUBE さん @dmikurube のツイート

作るもの・作ったものの設計をドキュメント化するときには、「なぜそうするか」「なぜこうはしないか」の理由と問題の背景、それを補助する実験・実測値が一番大事で、設計そのものの詳細を微に入り細に入り記述しておいてもドキュメントとして大して価値がない…、というのは定期的に言っていきたい

という主張に全面的に賛同したので，今回の設計について「なぜそうするか」「なぜこうはしないのか」を書き留めたいと思います。

折しもコメントにて @cooldaemon さんが型検査を C言語側ではなく Elixir 側で行った理由について尋ねてきたので，この点を中心に説明を追記します。

型多相(Polymorphic)とは？

Elixirで加算をする関数について考えてみます。

iex> add = fn (a, b) -> a + b end

この関数は，a, b それぞれが整数型でも浮動小数点型でも機能します。

iex> add.(1, 2)
3
iex> add.(1, 2.0)
3.0
iex> add.(1.0, 2.0)
3.0
iex> add.(1.0, 2)  
3.0

このように，複数の型で同じように機能することを型多相(polymorphic)といいます。

型安全(type safe)とは？

先ほどの加算の関数に無理やりリストを与えるとどうなるでしょうか。

iex> add.(1.0, [1])
** (ArithmeticError) bad argument in arithmetic expression
    :erlang.+(1.0, [1])

きちんとエラーが発生し，無理やりの実行が続くことはありません。

このように，型に当てはまらない値を与えた時に，どんな場合でも適切にエラーとして処理してくれる性質のことを型安全(type safe)と言います。

型に当てはまるかどうかの検査のことを型検査(type checking)と言います。Elixir の型検査は，コンパイル時に検出する場合と実行時に検出する場合があります。コンパイル時に型検査することを静的型検査，実行時に型検査することを動的型検査と言います。できるかぎり静的型検査が効いてくれれば，実行するまでもなく型安全性を保証できるので好都合ですが，コンパイル時間がかかったり融通が利かなくなったりします。これに対し動的型検査は，コンパイル時間がかからず柔軟性がありますが，テストしたり証明をしたりして型安全性を保証してやる必要があります。

C言語における型多相と型安全

C言語は型多相でも型安全でもありません。

C言語では1つの関数や変数で複数の型の値を受け入れることができないという点で型多相ではありません。

またC言語にはキャストのような型安全性を破壊する機能が備わっています。

ElixirとNIFで型多相を実現する方針

Elixirにはガードという機能があり，ガードの中で型検査を行うことができます。これを利用して次のように書きます。

lib/nif_llvm.ex

  def add(a, b) do
    case {a, b} do
        {a, b} when is_integer(a) and is_integer(b) -> # a, b ともに整数型
        {a, b} when is_integer(a) and is_float(b)   -> # aが整数型，b が浮動小数点数型
        {a, b} when is_float(a) and is_integer(b)   -> # aが浮動小数点数型，bが整数型
        {a, b} when is_float(a) and is_float(b)     -> # a, b ともに浮動小数点数型
        _ -> raise ArithmeticError, message: "bad argument in arithmetic expression" # a, b の少なくとも一方が数ではない
    end
  end

もちろん，型検査をC言語側でも書くことはできます。しかし今回は次の理由で Elixir 側で型検査をしました。

1. Elixir の方がC言語よりも，パターンマッチが使える，case 文が強力である，ガード(when)が使えるなど，条件分岐の記法が豊富でパワフルです。
2. 今回はたまたまC言語でNIFを記述していますが，近い将来，Elixir の処理系 ZEAM を開発する過程で LLVM IR によるアセンブリコード記述で NIF のコードを生成したいと考えています。しかし LLVM IR では条件分岐が貧弱です。そこで Elixir に条件分岐を任せたいのです。
3. 将来的には Elixir による条件分岐の記述を元に LLVM を生成するように拡張していきます。その際には型検査の最適化も実装します。そのためパフォーマンスに関する懸念は解消される見込みです。
4. 仮に型が合っていなかった場合は ArithmeticError を発生させる必要があるのですが，NIF側から例外を発生させた場合には ErlangError しか生成できないので，Elixir 側で型検査した方が良いという理由もあります。

C言語でNIFを書く方法

次のようにビルドファイルを書いていきます。

mix.exs

defmodule NifLlvm.MixProject do
  use Mix.Project

  def project do
    [
      app: :nif_llvm,
      version: "0.1.0",
      elixir: "~> 1.6",
      compilers: [:nif_llvm] ++ Mix.compilers,  # 追加しました。
      start_permanent: Mix.env() == :prod,
      deps: deps()
    ]
  end

  # Run "mix help compile.app" to learn about applications.
  def application do
    [
      extra_applications: [:logger]
    ]
  end

  # Run "mix help deps" to learn about dependencies.
  defp deps do
    [
    ]
  end
end

# ここから追加しました。
defmodule Mix.Tasks.Compile.NifLlvm do
  def run(_) do
    if match? {:win32, _}, :os.type do
      # libpostal does not support Windows unfortunately.
      IO.warn("Windows is not supported.")
      exit(1)
    else
      File.mkdir_p("priv")
      {result, _error_code} = System.cmd("make", ["priv/libnifllvm.so"], stderr_to_stdout: true)
      IO.binwrite result
    end
    :ok
  end
end

Makefile

MIX := mix
CFLAGS := -O3 -g -ansi -pedantic -femit-all-decls


ERLANG_PATH = $(shell erl -eval 'io:format("~s", [lists:concat([code:root_dir(), "/erts-", erlang:system_info(version), "/include"])])' -s init stop -noshell)
CFLAGS += -I$(ERLANG_PATH)

CFLAGS += -I/usr/local/include -I/usr/include -L/usr/local/lib -L/usr/lib
CFLAGS += -std=gnu99 -Wno-unused-function

ifneq ($(OS),Windows_NT)
    CFLAGS += -fPIC

    ifeq ($(shell uname),Darwin)
        LDFLAGS += -dynamiclib -undefined dynamic_lookup
    endif
endif

.PHONY: all libnifllvm clean

all: libnifllvm


libnifllvm:
    $(MIX) compile

native/lib.ll: native/lib.c
    clang $(CFLAGS) -c -S -emit-llvm -o $@ $^

native/lib.s: native/lib.ll
    llc -o $@ $^

priv/libnifllvm.so: native/lib.s
    # $(CC) $(CFLAGS) -shared $(LDFLAGS) -o $@ native/lib.c
    $(CC) -shared $(LDFLAGS) -o $@ $^

clean:
    $(MIX) clean
    $(RM) priv/*

後々のために LLVM コードとアセンブリコードを出力するようにしました。処理系ZEAMの開発の研究材料にするためです。

native/lib.c

#include <limits.h>
#include "erl_nif.h"
#include "loader.c"

/* ここにinit_nif_llvm，NIF関数，nif_func を書く */

ERL_NIF_INIT(Elixir.NifLlvm, nif_funcs, &load, &reload, &upgrade, &unload)

native/loader.c

#include "erl_nif.h"

static void init_nif_llvm(ErlNifEnv *env);

static int
load(ErlNifEnv *env, void **priv, ERL_NIF_TERM info)
{
  init_nif_llvm(env);
  return 0;
}

static void
unload(ErlNifEnv *env, void *priv)
{
}

static int
reload(ErlNifEnv *env, void **priv, ERL_NIF_TERM info)
{
  return 0;
}

static int
upgrade(ErlNifEnv *env, void **priv, void **old_priv, ERL_NIF_TERM info)
{
  return load(env, priv, info);
}

コンパイルにあたって LLVM をインストールする必要があります。また，llc などのコマンドにパスを通す必要があります。(次のコマンド)

$ brew install llvm
$ brew link llvm --force

型多相かつ型安全なNIFをC言語で書いてみる

こんな感じで実装してみました。コード全体は GitHub https://github.com/zeam-vm/nif_llvm に置きました。

lib/nif_llvm.ex

defmodule NifLlvm do
  @on_load :load_nifs

  def load_nifs do
    :erlang.load_nif('./priv/libnifllvm', 0)
  end

  @max_int 9_223_372_036_854_775_807
  @min_int -9_223_372_036_854_775_808

  @moduledoc """
  Documentation for NifLlvm.
  """

  def main do
    IO.puts asm_1(1, 2)
    IO.puts asm_1(1.0, 2)
    IO.puts asm_1(1, 2.0)
    IO.puts asm_1(1.0, 2.0)
    IO.puts asm_1(@max_int, 0)
    IO.puts asm_1(@min_int, 0)
    try do
      IO.puts asm_1(@max_int, 1)
    rescue
      error in [ArithmeticError] -> IO.puts "it needs BigNum!: #{Exception.message(error)}"
    end
    try do
      IO.puts asm_1(@max_int + 1, 1)
    rescue
      error in [ArithmeticError] -> IO.puts "it needs BigNum!: #{Exception.message(error)}"
    end
  end

  def asm_1(a, b) do
    case {a, b} do
        {a, b} when is_integer(a) and a <= @max_int and a >=@min_int
          and is_integer(b) and b <= @max_int and b >=@min_int
          -> case asm_1_nif_ii(a, b) do
            x when is_integer(x) -> x
            :error -> raise ArithmeticError, message: "bad argument in arithmetic expression"
          end
        {a, b} when is_integer(a) and a <= @max_int and a >=@min_int and is_float(b) -> asm_1_nif_if(a, b)
        {a, b} when is_float(a) and is_integer(b) and b <= @max_int and b >=@min_int -> asm_1_nif_fi(a, b)
        {a, b} when is_float(a) and is_float(b) -> asm_1_nif_ff(a, b)
        _ -> raise ArithmeticError, message: "bad argument in arithmetic expression"
    end
  end

  def asm_1_nif_ii(a, b) when is_integer(a) and is_integer(b), do: raise "NIF asm_1_nif_ii/2 not implemented"
  def asm_1_nif_if(a, b) when is_integer(a) and is_float(b),   do: raise "NIF asm_1_nif_if/2 not implemented"
  def asm_1_nif_fi(a, b) when is_float(a)   and is_integer(b), do: raise "NIF asm_1_nif_fi/2 not implemented"
  def asm_1_nif_ff(a, b) when is_float(a)   and is_float(b),   do: raise "NIF asm_1_nif_ff/2 not implemented"

end

native/lib.c

#include <limits.h>
#include "erl_nif.h"
#include "loader.c"

static ERL_NIF_TERM arithmetic_error;
static ERL_NIF_TERM error_atom;

static void init_nif_llvm(ErlNifEnv *env)
{
    arithmetic_error = enif_raise_exception(env, enif_make_atom(env, "ArithmeticError"));
    error_atom = enif_make_atom(env, "error");
}

static
ERL_NIF_TERM asm_1_nif_ii(ErlNifEnv *env, int argc, const ERL_NIF_TERM argv[])
{
    long a, b;
    if(enif_get_int64(env, argv[0], &a) == 0) {
        goto error;
    }
    if(enif_get_int64(env, argv[1], &b) == 0) {
        goto error;
    }
    if(a > LONG_MAX - b) {
        return error_atom;
    }
    long result =  a + b;
    return enif_make_int64(env, result);
error:
    return arithmetic_error;
}

static
ERL_NIF_TERM asm_1_nif_if(ErlNifEnv *env, int argc, const ERL_NIF_TERM argv[])
{
    long a;
    double b;
    if(enif_get_int64(env, argv[0], &a) == 0) {
        goto error;
    }
    if(enif_get_double(env, argv[1], &b) == 0) {
        goto error;
    }
    double result = ((double)a) + b;
    return enif_make_double(env, result);
error:
    return arithmetic_error;
}

static
ERL_NIF_TERM asm_1_nif_fi(ErlNifEnv *env, int argc, const ERL_NIF_TERM argv[])
{
    double a;
    long b;
    if(enif_get_double(env, argv[0], &a) == 0) {
        goto error;
    }
    if(enif_get_int64(env, argv[1], &b) == 0) {
        goto error;
    }
    double result = a + ((double) b);
    return enif_make_double(env, result);
error:
    return arithmetic_error;
}

static
ERL_NIF_TERM asm_1_nif_ff(ErlNifEnv *env, int argc, const ERL_NIF_TERM argv[])
{
    double a, b;
    if(enif_get_double(env, argv[0], &a) == 0) {
        goto error;
    }
    if(enif_get_double(env, argv[1], &b) == 0) {
        goto error;
    }
    double result = a + b;
    return enif_make_double(env, result);
error:
    return arithmetic_error;
}

static
ErlNifFunc nif_funcs[] =
{
  // {erl_function_name, erl_function_arity, c_function}
  {"asm_1_nif_ii", 2, asm_1_nif_ii},
  {"asm_1_nif_if", 2, asm_1_nif_if},
  {"asm_1_nif_fi", 2, asm_1_nif_fi},
  {"asm_1_nif_ff", 2, asm_1_nif_ff}
};

ERL_NIF_INIT(Elixir.NifLlvm, nif_funcs, &load, &reload, &upgrade, &unload)

実行結果

$ mix run -e "NifLlvm.main"
clang -O3 -g -ansi -pedantic -femit-all-decls -I/Users/zacky/.erlenv/releases/21.0/lib/erlang/erts-10.0/include -I/usr/local/include -I/usr/include -L/usr/local/lib -L/usr/lib -std=gnu99 -Wno-unused-function -fPIC -c -S -emit-llvm -o native/lib.ll native/lib.c
clang-6.0: warning: argument unused during compilation: '-L/usr/local/lib' [-Wunused-command-line-argument]
clang-6.0: warning: argument unused during compilation: '-L/usr/lib' [-Wunused-command-line-argument]
llc -o native/lib.s native/lib.ll
# cc -O3 -g -ansi -pedantic -femit-all-decls -I/Users/zacky/.erlenv/releases/21.0/lib/erlang/erts-10.0/include -I/usr/local/include -I/usr/include -L/usr/local/lib -L/usr/lib -std=gnu99 -Wno-unused-function -fPIC -shared -dynamiclib -undefined dynamic_lookup -o priv/libnifllvm.so native/lib.c
cc -shared -dynamiclib -undefined dynamic_lookup -o priv/libnifllvm.so native/lib.s
3
3.0
3.0
3.0
9223372036854775807
it needs BigNum!: bad argument in arithmetic expression
it needs BigNum!: bad argument in arithmetic expression
$ 

解説

defmodule NifLlvm do
  @on_load :load_nifs

  def load_nifs do
    :erlang.load_nif('./priv/libnifllvm', 0)
  end

NIFをロードする部分です。

  @max_int 9_223_372_036_854_775_807
  @min_int -9_223_372_036_854_775_808

long (INT64) の最大値を設定しています。Elixirでは整数値に上限・下限はありませんが，NIFで受け取れる整数値は long (INT64) の範囲なので，この情報が必要になってきます。NIFで long (INT64) の範囲を超えて BigNum で受け取れるようにするのは今後の課題です。BigNum判定を Elixir 側にしたのは型検査と同様の理由です。

  def asm_1(a, b) do
    case {a, b} do
        {a, b} when is_integer(a) and a <= @max_int and a >=@min_int
          and is_integer(b) and b <= @max_int and b >=@min_int
          -> case asm_1_nif_ii(a, b) do
            x when is_integer(x) -> x
            :error -> raise ArithmeticError, message: "bad argument in arithmetic expression"
          end
        {a, b} when is_integer(a) and a <= @max_int and a >=@min_int and is_float(b) -> asm_1_nif_if(a, b)
        {a, b} when is_float(a) and is_integer(b) and b <= @max_int and b >=@min_int -> asm_1_nif_fi(a, b)
        {a, b} when is_float(a) and is_float(b) -> asm_1_nif_ff(a, b)
        _ -> raise ArithmeticError, message: "bad argument in arithmetic expression"
    end
  end

型多相かつ型安全にするためにガード条件をいろいろ設定しています。整数の場合に，上限・下限を設定しています。a,bともに整数だった場合には asm_1_nif_ii を呼び出します。末尾のiiはa,bともに整数であることを意味します。以下同様です。

a,bともに整数だった場合には，結果が long(INT64) の範囲を超えてしまった場合に ArithmeticError を発生させるようにしています。 Elixir 側で例外を発生させる理由は，NIF側で例外を発生させると ErlangError になってしまうからです。

  def asm_1_nif_ii(a, b) when is_integer(a) and is_integer(b), do: raise "NIF asm_1_nif_ii/2 not implemented"
  def asm_1_nif_if(a, b) when is_integer(a) and is_float(b),   do: raise "NIF asm_1_nif_if/2 not implemented"
  def asm_1_nif_fi(a, b) when is_float(a)   and is_integer(b), do: raise "NIF asm_1_nif_fi/2 not implemented"
  def asm_1_nif_ff(a, b) when is_float(a)   and is_float(b),   do: raise "NIF asm_1_nif_ff/2 not implemented"

NIFの呼び出しをしています。ここでも型検査をしています。すでに asm_1 の方で型検査をしているので冗長ではありますが，念押しです。冗長な型検査により実行速度が低下する問題の解決については今後の課題です。

static
ErlNifFunc nif_funcs[] =
{
  // {erl_function_name, erl_function_arity, c_function}
  {"asm_1_nif_ii", 2, asm_1_nif_ii},
  {"asm_1_nif_if", 2, asm_1_nif_if},
  {"asm_1_nif_fi", 2, asm_1_nif_fi},
  {"asm_1_nif_ff", 2, asm_1_nif_ff}
};

NIFの4つの関数を登録しています。数字の2は引数の数を表します。

static
ERL_NIF_TERM asm_1_nif_ii(ErlNifEnv *env, int argc, const ERL_NIF_TERM argv[])
{
    long a, b;
    if(enif_get_int64(env, argv[0], &a) == 0) {
        goto error;
    }
    if(enif_get_int64(env, argv[1], &b) == 0) {
        goto error;
    }
    if(a > LONG_MAX - b) {
        return error_atom;
    }
    long result =  a + b;
    return enif_make_int64(env, result);
error:
    return arithmetic_error;
}

a,b ともに整数の場合のみを解説します。NIF関数は決まった型をしていて，引数に env, argc, argv を取り，戻り値の型は ERL_NIF_TERM です。

enif_get_int64 は引数から整数値を読み出す関数です。もし型が合っていなかった場合には 0 が返ってくるので，その場合はエラー処理に飛ばします。(ここではエラー処理としてあえて goto を使っています。あとでブランチ命令について分岐予測を考慮した最適化を施すためです。)

if(a > LONG_MAX - b) は加算により long (INT64) の上限値を超えないかを判定しています。超えた場合には，仮に :error を返します。BigNum 対応は今後の課題です。例外を投げなかったのは，例外を投げるとペナルティが大きくなるためです。ここで atom を生成してもいいのですが，エラー処理でメモリを確保できるとは限らないので，あらかじめ静的に確保しておきます。

enif_make_int64 は整数の戻り値を生成する関数です。

エラー処理では別途あらかじめ静的に定義・生成する arithmetic_error を返します。ここで例外を生成してもいいのですが，エラー処理でメモリを確保できるとは限らないので，あらかじめ静的に確保した例外を返すようにした方が良いです。

static ERL_NIF_TERM arithmetic_error;
static ERL_NIF_TERM error_atom;

static void init_nif_llvm(ErlNifEnv *env)
{
    arithmetic_error = enif_raise_exception(env, enif_make_atom(env, "ArithmeticError"));
    error_atom = enif_make_atom(env, "error");
}

静的に :error と arithmetic_error を定義する部分です。enif_raise_exception と enif_make_atom を組み合わせるのは例外処理の定番です。

  def main do
    IO.puts asm_1(1, 2)
    IO.puts asm_1(1.0, 2)
    IO.puts asm_1(1, 2.0)
    IO.puts asm_1(1.0, 2.0)
    IO.puts asm_1(@max_int, 0)
    IO.puts asm_1(@min_int, 0)
    try do
      IO.puts asm_1(@max_int, 1)
    rescue
      error in [ArithmeticError] -> IO.puts "it needs BigNum!: #{Exception.message(error)}"
    end
    try do
      IO.puts asm_1(@max_int + 1, 1)
    rescue
      error in [ArithmeticError] -> IO.puts "it needs BigNum!: #{Exception.message(error)}"
    end
  end

実際の使用例です。両方整数型だった場合には整数型の値が，少なくとも一方が浮動小数点数型だった場合には浮動小数点数型の値が返ります。@max_int, @min_int までは扱えます。
@max_int, @min_int の範囲を超えるとエラーを返します。

• asm_1(@max_int, 1) のときには，加算結果が @max_int を超えるので，NIF関数が :error を返し，それを受けて asm_1 が例外を投げます。
• asm_1(@max_int + 1, 1) のときには，引数値が @max_int を超えるので，asm_1 の中で例外が発生します。

まとめと将来課題

• 関数が複数の型で同じように機能することを型多相(polymorphic)と言います。
• 型に当てはまらない値を与えた時に，どんな場合でも適切にエラーとして処理してくれる性質のことを型安全(type safe)と言います。
• 型に当てはまるかどうかの検査のことを型検査(type checking)と言います。
• C言語はもともと型多相でも型安全でもありません。
• Elixir とC言語によるNIFの組み合わせで型多相にするためには， case とガード(when)と型検査を使って引数の型によって分岐するようにします。
• C言語を使ってNIFを作るには，erl_nif.h をインクルードし，ERL_NIF_INIT を使って登録します。
• C言語によるNIFで型安全にするためには，ElixirとC言語のコードに型検査をするコードを適切に入れることとが必要です。型検査の最適化については今後の課題です。
• C言語によるNIFでは，Elixirの整数型は値に上限・下限がない点に留意すべきです。long (INT64) の上限・下限を超えた整数値をNIFでどのように扱うかについては今後の課題です。

というわけで，次回はZEAM開発ログ v.0.4.1 型多相かつ型安全なNIFの LLVM IR コードを読み解くです。お楽しみに！

　お知らせ：Elixirもくもく会（リモート参加OK、入門トラック有）を9月28日に開催します　

「fukuoka.ex#14：Elixir／Phoenixもくもく会～入門もあるよ」を2018年9月28日金曜日に開催します

前回は，ゲリラ的に募った「Zoomによるリモート参加」を，今回から正式に受け付けるようになりましたので，福岡以外の首都圏や地方からでも参加できます（申し込みいただいたら、追ってZoom URLをconnpassメールでお送りします）

また，これまではElixir／Phoenix経験者を対象とした，もくもく会オンリーでしたが，今回から，入門者トラックも併設し，fukuoka.exアドバイザーズ／キャストに質問できるようにアップグレードしました

私，山崎も参加します！ この記事の延長線上のものを作ろうと思っています。

お申込みはコチラから
https://fukuokaex.connpass.com/event/100659/