本記事は「2024年!初アウトプットをしよう」の参加記事です。
TL; DR
以下の流れで大小比較
- モジュール名の名前の辞書順
- 関数名の名前の辞書順
- 関数のアリティの大小
はじめに
Elixirでは、任意の型のオブジェクト同士を（異なる型同士であっても）大小比較することができます。マップや関数等、他の言語では比較できないようなオブジェクトにも順序を付けられます。
Elixir では二つの異なる型を比較できます。
これはプラグマティズム(実用主義)が理由です。よって異なる型をソートする際に、その違いを心配する必要がないのです。
number < atom < reference < function < port < pid < tuple < map < list < bitstring
ところで、マップやリストはともかく 関数同士の大小比較 というのはどういう規則で行われているのでしょうか？少し探しても見つからなかったので調べてみました。
Elixirの実装を見る
kernel.ex に、2項演算子 > の定義が書かれています。
@doc guard: true
@spec term > term :: boolean
def left > right do
:erlang.>(left, right)
end
Erlangの定義をそのまま利用していました。Erlangの比較演算子のドキュメントを見ると、Elixirと全く同じ説明が書かれています。
同じ型のオブジェクト同士の比較についても説明されています。
Listは要素ごとに比較されます。Tupleはサイズによって順序付けられます。サイズが同じ場合は、要素ごとに比較されます。
BitStringはビットごとに比較されます。片方のstringがもう片方のprefixとなる場合、短い方が小さいとみなされます。
Mapはサイズによって順序付けられます。サイズが同じ場合はキーの昇順で比較したのち、キー順に値で比較されます。キーの順序では、integerはfloatよりも小さいとみなされます。
AtomはStringの値によって、コードポイントごとに比較されます。
(拙訳、原文は英語)
しかし、関数同士の場合の記述は残念ながらありませんでした。
Erlangの実装を見る
気を取り直して、Erlangの実装を読みます。比較演算子は compare_flatmap_atom_keys で定義されていました。
1000行越えの関数で分岐も多いですが、関数については以下の流れで比較が行われています。
- external functionは local functionよりも大きい
- local function同士の場合
- 名前のatomで大小比較
- indexで大小比較
-
old_uniqで大小比較
- external function同士の場合
- モジュール名のatomで大小比較
- 関数名のatomで大小比較
- アリティ（仮引数の個数）で大小比較
static
Sint compare_flatmap_atom_keys(const Eterm* a_keys,
const Eterm* b_keys,
int n_atoms)
{
// ...
switch (primary_tag(a)) {
// ...
case TAG_PRIMARY_BOXED:
// ...
case (_TAG_HEADER_FUN >> _TAG_PRIMARY_SIZE):
if (is_not_any_fun(b)) {
a_tag = FUN_DEF;
goto mixed_types;
} else {
ErlFunThing* f1 = (ErlFunThing *) fun_val(a);
ErlFunThing* f2 = (ErlFunThing *) fun_val(b);
if (is_local_fun(f1) && is_local_fun(f2)) {
ErlFunEntry* fe1 = f1->entry.fun;
ErlFunEntry* fe2 = f2->entry.fun;
Sint diff;
if (fe1 != fe2) {
diff = erts_cmp_atoms(fe1->module, (fe2)->module);
if (diff != 0) {
RETURN_NEQ(diff);
}
diff = fe1->index - fe2->index;
if (diff != 0) {
RETURN_NEQ(diff);
}
diff = fe1->old_uniq - fe2->old_uniq;
if (diff != 0) {
RETURN_NEQ(diff);
}
}
diff = fun_num_free(f1) - fun_num_free(f2);
if (diff != 0) {
RETURN_NEQ(diff);
}
i = fun_num_free(f1);
if (i == 0) goto pop_next;
aa = f1->env;
bb = f2->env;
goto term_array;
} else if (is_external_fun(f1) && is_external_fun(f2)) {
Export* a_exp = f1->entry.exp;
Export* b_exp = f2->entry.exp;
if ((j = erts_cmp_atoms(a_exp->info.mfa.module,
b_exp->info.mfa.module)) != 0) {
RETURN_NEQ(j);
}
if ((j = erts_cmp_atoms(a_exp->info.mfa.function,
b_exp->info.mfa.function)) != 0) {
RETURN_NEQ(j);
}
ON_CMP_GOTO((Sint) a_exp->info.mfa.arity -
(Sint) b_exp->info.mfa.arity);
} else {
/* External funs compare greater than local ones. */
RETURN_NEQ(is_external_fun(f1) - is_external_fun(f2));
}
// ...
}
}
// ...
}
index も old_uniq も内部的なIDに見えたのですが、具体的な用途までは追いきれませんでした...
確かめる
確かに上記の通りの順序になっています1。
defmodule Bar do
def b, do: nil
def a, do: nil
end
defmodule Foo do
def a, do: nil
def a(_x), do: nil
end
# モジュールの名前が辞書順で大きい
IO.puts ((&Foo.a/0) > (&Bar.b/0)) # true
# 関数名が辞書順で大きい
IO.puts ((&Bar.b/0) > (&Bar.a/0)) # true
# アリティが大きい
IO.puts ((&Foo.a/1) > (&Foo.a/0)) # true
おわりに
以上、Elixir(Erlang)の関数の大小比較についての紹介でした。今年最初の記事がこんなマイナーネタでいいのだろうか...
これからも役に立つか立たないか分からないネタを投稿していきますので、今年もよろしくお願いいたします。
-
ElixirでErlangのlocal functionに相当するものは分からず...ローカル変数に代入できる匿名関数だと名前が無いので条件が異なってしまいます。 ↩