Erlang仮想マシンBEAM

この記事は英語の原文を日本語に翻訳したものです。原文: https://blog.stenmans.org/theBeamBook/#CH-BEAM

翻訳元: happi/theBeamBook 7998e22e78417dbe20e5136b9aee862a1ecaa404（コミット 7998e22）

BEAM(Bogdan’s/Björn’s Abstract Machine)は、Erlangランタイムシステム内でコードを実行するマシンです。 ガベージコレクションを行い、リダクションを数え、仮想的で、非プリエンプティブで、直接スレッデッドな、レジスタマシンです。 これだけではぴんと来なくても心配は要りません。以下の節で、これらの言葉がここでどういう意味を持つのかを順に見ていきます。

仮想マシンであるBEAMは、Erlangノードの中核にあります。 Erlangのコードを実行するのはBEAMです。つまり、アプリケーションのコードを実行しているのもBEAMです。 BEAMがどのようにコードを実行するかを理解することは、コードのプロファイリングやチューニングを行ううえで欠かせません。

BEAMの設計は、ERTSの他の大部分に影響を与えています。 スケジューリングのプリミティブはスケジューラに、Erlangの項の表現は型システムに、そしてメモリとのやり取りはガベージコレクタに、それぞれ影響を与えています。 BEAMの基本的な設計を理解しておけば、これらほかのコンポーネントの実装もより理解しやすくなります。

非スタックマシンとしてのワーキングメモリ

前身であるスタックマシンのJAM(Joe’s Abstract Machine)とは違い、BEAMはWAM(Warren)を緩やかに基にしたレジスタマシンです。 スタックマシンでは、命令への各オペランドはまず作業用スタックにプッシュされ、命令がそのオペランドをポップしたうえで結果をスタックにプッシュします。

スタックマシンは、コードを生成しやすくコードが非常にコンパクトになることから、仮想マシンやプログラミング言語の実装者の間で広く使われています。 コンパイラはレジスタ割り当てを行う必要がなく、ほとんどの操作は(命令列の中に)オペランドを必要としません。

式 "8 + 17 * 2." をスタックマシン向けにコンパイルすると、次のようなコードになります。

push 8
push 17
push 2
multiply
add

このコードは、式の構文木から直接生成できます。 Erlangの式とerl_scanモジュールおよびerl_parseモジュールを使えば、世界一単純なコンパイラを作れます。

スタックマシン向けの簡単なコンパイラ

compile(String) ->
    [ParseTree] = element(2,
              erl_parse:parse_exprs(
                element(2,
                    erl_scan:string(String)))),
    generate_code(ParseTree).

generate_code({op, _Line, '+', Arg1, Arg2}) ->
    generate_code(Arg1) ++ generate_code(Arg2) ++ [add];
generate_code({op, _Line, '*', Arg1, Arg2}) ->
    generate_code(Arg1) ++ generate_code(Arg2) ++ [multiply];
generate_code({integer, _Line, I}) -> [push, I].

さらに単純な仮想スタックマシンも書いてみましょう。

スタックマシンインタプリタ

interpret(Code) -> interpret(Code, []).

interpret([push, I |Rest], Stack)              -> interpret(Rest, [I|Stack]);
interpret([add     |Rest], [Arg2, Arg1|Stack]) -> interpret(Rest, [Arg1+Arg2|Stack]);
interpret([multiply|Rest], [Arg2, Arg1|Stack]) -> interpret(Rest, [Arg1*Arg2|Stack]);
interpret([],              [Res|_])            -> Res.

実際に動かしてみると、次のように答えが返ってきます。

1> stack_machine:interpret(stack_machine:compile("8 + 17 * 2.")).
42

これで最初の仮想マシンができました。減算や除算、その他のErlangの言語機能への対応は、読者への課題として残しておきます。

BEAMのレジスタ

さて、BEAMはスタックマシンではなく、レジスタマシンです。 レジスタマシンでは、命令のオペランドはスタックではなくレジスタに格納され、操作の結果は通常特定のレジスタに入ります。 BEAMでは、レジスタはワードサイズのメモリ位置であり、実行中のプロセスに private なXレジスタ(X0、X1、……)と呼ばれます。

ほとんどのレジスタマシンには、関数への引数を渡したり戻りアドレスを保存したりするためのスタックが依然として存在します。 特定の関数呼び出しに関する情報を保持するスタックの区画はスタックフレームと呼ばれ、戻りアドレス、レジスタに収まらない入力引数やローカル変数、サブルーチン呼び出し中に一時的に保存される値を保持します。¹

BEAMには、スタックフレーム内のすべてのエントリがXレジスタと同様にワードサイズで揃っているスタックがあり、そのため単にYレジスタ(Y0、Y1、……)と呼ばれます。これはWAMから借用した用語です。 言い換えると、BEAM命令がY0を参照するとき、それは現在の呼び出しのスタックフレーム内のスロット0を意味します。

Xレジスタは汎用レジスタですが、呼び出す関数への引数渡しにも使われ、レジスタX0(R0とも呼ばれることがあります)は戻り値に使われます。 これらのレジスタはハードウェアレジスタではなく単なるメモリ位置なので、実機のCPU(32個のレジスタでもかなり多いとされます)ほど限られた資源ではありません。 BEAMには1024個のXレジスタが用意されているため、関数の引数がスタック経由で渡される必要は決してありません。(ただし、関数呼び出しをまたいで生存する他のXレジスタの内容は、「呼び出し側保存」方式によってYレジスタとしてスタックに保存しておく必要があります。)

Xレジスタは(スケジューラごとに個別の)BEAMエミュレータ内のC配列に格納されており、すべての関数からグローバルにアクセスできます。 X0レジスタはローカル変数にキャッシュされ、ほとんどのアーキテクチャでは物理的なマシンレジスタに保持されます。 X0は非常に頻繁に使われるため、これは重要な最適化です。

Yレジスタは現在のスタックフレームに格納され、実行中の関数からのみアクセスできます。 関数呼び出しをまたいで値を保存するために、BEAMはスタックフレームにその値のための領域を確保し、値を対応するYレジスタへ移動します。 予約されていない領域のYレジスタへの書き込みは許されません。ヒープを上書きしてしまう可能性があるからです。

XレジスタとYレジスタのほかにも、BEAMにはいくつかの特殊用途レジスタがあります。

特殊用途レジスタ

• Htop：ヒープの先頭(htop)
• E：スタックの先頭(stop)
• I：命令ポインタ
• FP：フレームポインタ(現在のフレームの先頭)
• CP：コンティニュエーションポインタ、つまり関数の戻りアドレス
• fcalls：リダクションカウンタ

HtopやEのようなレジスタは、PCB内の対応するフィールドのキャッシュされたコピーです。 プロセスがタイムスライスを使い切ると、値はPCBに書き戻され、別のプロセスが実行される番になります。 BEAMがあるプロセスを別のプロセスに切り替える方法は、一種の協調的マルチタスク(プロセス切り替えを参照)と考えられるため、この切り替えが起きるときにすべてのXレジスタを保存・復元する必要はありません。そのとき保存が必要なものはすべてYレジスタに入っているからです。

フレームポインタ(FP)は必ずしも「実在の」BEAMレジスタとは限りません。スタックフレームの現在のサイズがわかっていれば、スタックの先頭から計算できるからです。 とはいえ、これを別個に追跡しておくと実装上ほかの部分が楽になることもあり、ここでは説明を単純にするため、あたかも実在するかのように扱います。

コンティニュエーションポインタ(CP)は、BEAMがcall命令を実行するときに戻りアドレスへ設定されます。 戻りアドレスを直接スタックにプッシュする代わりにCPに保持しておくことで、return命令はIの新しい値をCPと同じにするだけで実行を継続できます。 これは、(末尾呼び出しを除く)すべての呼び出しのうち平均して半分は、それ以上関数を呼び出さない関数であるリーフ関数への呼び出しになるという事実に基づいた最適化です。 リーフ関数を呼び出す場合、戻りアドレスをスタックに保存する必要はありません。 その代わり、リーフ関数でない関数だけが、CPをスタックに保存し、戻る前に復元する必要があります。

BEAMのレジスタとスタックフレームは、2つのYレジスタを使いCPをスタックに保存した関数について、BEAMにおけるレジスタとスタックフレームのレイアウトを示しています。 XレジスタとYレジスタには即値か、ヒープを指すタグ付きポインタ(型システムを参照)が入りますが、スタックのスロットを指すことは決してありません。たとえばスタックフレームにタプルが格納されることはありません。

BEAMのレジスタとスタックフレーム

          Stack/Heap                 X registers

  hend ->  +------+                   +------+
           |......|           X1023   |      |
           +------+                   +------+
    FP ->  |  CP  |           X1022   |      |
           +------+                   +------+
    Y0 ->  |      |                   |      |
           +------+             ...   |......|
    Y1 ->  |      |                   |      |
           +------+                   +------+
     E ->  |      |              X2   |      |
           |      |                   +------+
           |......|              X1   |      |
           |      |                   +------+
  Htop ->  |      |             (X0)  |      |
           |......|                   +------+
           |......|
  heap ->  +------+

スタックレイアウトの例

次のプログラムを ‘S’ フラグ付きでコンパイルしてみましょう。

-module(add).
-export([add/2]).

add(A,B) ->  id(A) + id(B).

id(I) -> I.

すると、add/2 関数について次のようなコードが得られます。

{function, add, 2, 2}.
  {label,1}.
    {line,[{location,"add.erl",4}]}.
    {func_info,{atom,add},{atom,add},2}.
  {label,2}.
    {allocate,1,2}.
    {move,{x,1},{y,0}}.
    {call,1,{f,4}}.
    {swap,{y,0},{x,0}}.
    {call,1,{f,4}}.
    {gc_bif,'+',{f,0},1,[{y,0},{x,0}],{x,0}}.
    {deallocate,1}.
    return.

関数に入った時点で、慣習により第1引数の A はX0に、第2引数の B はX1に渡されます。 (ラベル2から始まる)コードはまず、単一のスタックスロット分の領域を確保します。² これは、関数呼び出し id(A) の間X1の値をY0に保存しておくためのもので、これは {move,{x,1},{y,0}} 命令(「X1をY0へmoveする」、あるいは命令的なスタイルで書けば y0 := x1)によって行われます。

引数 A はすでに(第1引数レジスタである)X0に入っているため、ラベル {f,4} にある id/1 関数(ここには示していません)は {call,1,{f,4}} によって直接呼び出せます。(オペランド「1」が何を表すかは後で説明します。) その後、呼び出しの結果(X0に返される)をスタックに保存する必要がありますが、Y0のスロットはすでに引数 B に占有されています。 幸い、この場合に対応する swap 命令があるため、Y0をX1へ、X0をY0へ、そしてX1をX0へと3つの命令を使って移し替える必要はありません。

これで第2引数 B がX0に入ったので、再び {call,1,{f,4}} で id/1 関数を呼び出せます。 この後、X0には id(B) が、Y0には id(A) が入っています。 組み込み関数 +/2 を呼び出すことで加算を実行できます: {gc_bif,'+',{f,0},1,[{y,0},{x,0}],{x,0}}。(BIF呼び出しとGCの詳細は後で扱います。) 結果は再びX0に入り、これは add/2 から戻るのにちょうど必要な場所です。 戻る前に必要なのは、deallocate命令でスタックポインタを元に戻すことだけで、これで関数は完了です。

BEAMインタプリタ

BEAMインタプリタは、直接スレッデッドコードと呼ばれる技法で実装されています。 ここでの「スレッデッド」という言葉は、OSのスレッドや並行性、並列性とは何の関係もありません。仮想マシン自体を貫通するように実行パスが「編まれている」ことを指します。

バイトコードエミュレーション

算術式のための、先ほどの素朴なスタックマシンを見てみると、どの命令を実行するかを選ぶためにErlangのアトムとパターンマッチングを使っていることがわかります。 これは、単に機械命令をデコードするだけにしては非常に重い仕組みです。 実際のマシンの実装では、各命令を「マシンワード」の整数、あるいは1バイトとしてコード化するでしょう。

先ほどのスタックマシンを、Cで実装したバイトコードマシンとして書き直せます。 まず、先ほどの簡単なコンパイラを書き直して、バイトコードを出力するようにします。 これは単純な作業で、アトムとしてエンコードされていた各命令を、その命令を表す1バイトに置き換えるだけです(下記参照)。 255より大きい整数を扱えるようにするため、整数はサイズを表す1バイトに続けてバイト列としてエンコードされた整数、という形でエンコードします。

簡単なバイトコードコンパイラ

compile(Expression, FileName) ->
    [ParseTree] = element(2,
              erl_parse:parse_exprs(
                element(2,
                    erl_scan:string(Expression)))),
    file:write_file(FileName, generate_code(ParseTree) ++ [stop()]).

generate_code({op, _Line, '+', Arg1, Arg2}) ->
    generate_code(Arg1) ++ generate_code(Arg2) ++ [add()];
generate_code({op, _Line, '*', Arg1, Arg2}) ->
    generate_code(Arg1) ++ generate_code(Arg2) ++ [multiply()];
generate_code({integer, _Line, I}) -> [push(), integer(I)].

stop()     -> 0.
add()      -> 1.
multiply() -> 2.
push()     -> 3.
integer(I) ->
    L = binary_to_list(binary:encode_unsigned(I)),
    [length(L) | L].

それでは、Cで簡単な仮想マシンとバイトコードインタプリタを書いてみましょう。(完全なコードはオンライン付録にあります。)

#define STOP 0
#define ADD  1
#define MUL  2
#define PUSH 3

#define pop()   (stack[--sp])
#define push(X) (stack[sp++] = X)

int run(char *code) {
  int stack[1000];
  int sp = 0, size = 0, val = 0;
  char *ip = code;

  while (*ip != STOP) {
    switch (*ip++) {
    case ADD: push(pop() + pop()); break;
    case MUL: push(pop() * pop()); break;
    case PUSH:
      size = *ip++;
      val = 0;
      while (size--) { val = val * 256 + *ip++; }
      push(val);
      break;
    }
  }
  return pop();
}

見ての通り、Cで書かれた仮想マシンはそれほど複雑にする必要はありません。 このマシンは単なるループであり、命令ポインタ(ip)が指す値を見ることで各命令のバイトコードを調べます。

各バイトコード命令について、命令のバイトコードでswitchし、その命令を実行するcase節へジャンプします。 これには命令のデコードと、正しいコードへのジャンプが必要です。 vsm.cのアセンブリ(gcc -S vsm.c)を見ると、デコーダの内側のループが見えます。

L11:
        movl    -16(%ebp), %eax
        movzbl  (%eax), %eax
        movsbl  %al, %eax
        addl    $1, -16(%ebp)
        cmpl    $2, %eax
        je      L7
        cmpl    $3, %eax
        je      L8
        cmpl    $1, %eax
        jne     L5

バイトコードを各命令コードと比較し、条件分岐ジャンプを行わなければなりません。 命令数の多い実際のマシンでは、これはかなりのコストになりえます。

スレッデッドコード

もっと良い解決策は、コードのアドレスを保持するテーブルを用意することです。そうすれば、比較を一切行わずにテーブルへのインデックスを使ってアドレスをロードし、ジャンプできます。 この技法はトークンスレッデッドコードと呼ばれることがあります。 これをさらに一歩進めると、命令を実装するコード片のアドレス自体を、コードメモリ内の「命令」そのものとして格納することもできます。 そうすればインタプリタのループは、1バイトの代わりに次のアドレスを読み込み、そのアドレスにあるルーチンを呼び出し、戻ってきたら次のアドレスへ進むだけでよくなります。 これはサブルーチンスレッデッドコードと呼ばれます。 ただし、このコードは1命令あたり1バイトではなく1ワード丸ごとを占めるため、はるかに多くの容量を必要とすることに注意してください。とはいえ、メモリが潤沢なハードウェアでは、速度面の利点がその分を補って余りあることがほとんどです。(トークンスレッデッドコードは、メモリが逼迫していて速度がそれほど重要でない場合によく使われます。)

このアプローチは実行時の処理を単純にしますが、その一方でローダーが必要になるためVM自体は複雑になります。 ローダーは、バイトコード命令をその命令を実装する関数のアドレスに置き換えます。

ローダーは次のようになるでしょう。

typedef void (*instructionp_t)(void);

void add()  { int x,y; x = pop(); y = pop(); push(x + y); }
void mul()  { int x,y; x = pop(); y = pop(); push(x * y); }
void pushi(){ int x;   x = (int)*ip++;       push(x); }
void stop() { running = 0; }

instructionp_t *read_file(char *name) {
  FILE *file;
  instructionp_t *code;
  instructionp_t *cp;
  long  size;
  char ch;
  unsigned int val;

  file = fopen(name, "r");

  if(file == NULL) exit(1);

  fseek(file, 0L, SEEK_END);
  size = ftell(file);
  code = calloc(size, sizeof(instructionp_t));
  if(code == NULL) exit(1);
  cp = code;

  fseek(file, 0L, SEEK_SET);
  while ( ( ch = fgetc(file) ) != EOF )
    {
      switch (ch) {
      case ADD: *cp++ = &add; break;
      case MUL: *cp++ = &mul; break;
      case PUSH:
    *cp++ = &pushi;
    ch = fgetc(file);
    val = 0;
    while (ch--) { val = val * 256 + fgetc(file); }
    *cp++ = (instructionp_t) val;
    break;
      }
    }
  *cp = &stop;

  fclose(file);
  return code;
}

見ての通り、255より大きい整数のデコードも含め、ロード時により多くの作業を行っています。(もちろん、このコードは非常に大きな整数に対しては安全ではありません。)

その代わり、VMのデコード・ディスパッチループは非常に単純になります。

int run() {
  sp = 0;
  running = 1;

  while (running) (*ip++)();

  return pop();
}

最後に、各命令のスニペットを戻り値のある関数にする代わりに、各スニペットの末尾に、メインループが次の命令を読んでジャンプするのに使っていたのと同じ小さなコードを置くという書き方もできます。 こうすればメインループとスニペットの間を行き来する必要がなくなります。実際、メインループ自体が消え去り、各命令のスニペットが個別に次の命令へ進む責任を負うことになります。 この技法は直接スレッデッドコードと呼ばれます。 これをCで実装するために、BEAMはGCCの拡張機能である「値としてのラベル(labels as values)」を使っています。

実際のBEAM

BEAMエミュレータについては後でより詳しく見ていきますが、ここではひとまず、実際のBEAMの add 命令がどのように実装されているかを簡単に見てみましょう。 マクロが多用されているため、コードはやや追いにくくなっています。 STORE_ARITH_RESULT マクロは、実際にはディスパッチ関数を隠しており、それはおおよそ次のようなものです: I += 4; Goto(*I);。

#define OpCase(OpCode)    lb_##OpCode
#define Goto(Rel) goto *(Rel)

...

 OpCase(i_plus_jId):
 {
     Eterm result;

     if (is_both_small(tmp_arg1, tmp_arg2)) {
     Sint i = signed_val(tmp_arg1) + signed_val(tmp_arg2);
     ASSERT(MY_IS_SSMALL(i) == IS_SSMALL(i));
     if (MY_IS_SSMALL(i)) {
         result = make_small(i);
         STORE_ARITH_RESULT(result);
     }

     }
     arith_func = ARITH_FUNC(mixed_plus);
     goto do_big_arith2;
 }

BEAMのディスパッチャがどのように実装されているかをもう少し理解しやすくするために、少し架空の例を見てみましょう。 実際の外部BEAMコードから出発し、その後いくつか内部的なBEAM命令を考え出してCで実装してみます。

Erlangで書かれた単純な加算関数から始めます。

add(A,B) -> id(A) + id(B).

これをBEAMコードにコンパイルすると、(swap 命令が追加される前は、スタックレイアウトの例を参照)次のようになります。

{function, add, 2, 2}.
  {label,1}.
    {func_info,{atom,add},{atom,add},2}.
  {label,2}.
    {allocate,1,2}.
    {move,{x,1},{y,0}}.
    {call,1,{f,4}}.
    {move,{x,0},{x,1}}.
    {move,{y,0},{x,0}}.
    {move,{x,1},{y,0}}.
    {call,1,{f,4}}.
    {gc_bif,'+',{f,0},1,[{y,0},{x,0}],{x,0}}.
    {deallocate,1}.
    return.

(完全なコードはオンライン付録のadd.erlとadd.Sを参照してください。)

このコードの、2つの関数呼び出しの間にある3つの命令に注目してみましょう。

    {move,{x,0},{x,1}}.
    {move,{y,0},{x,0}}.
    {move,{x,1},{y,0}}.

このコードはまず、関数呼び出しの戻り値(x0)をレジスタ x1 へ移します。 次に、先ほどスタックスロット y0 に保存しておいた B を第1引数レジスタ(x0)へ移します。 最後に x1 の値をスタックスロット(y0)へ移し、次の関数呼び出しをまたいで生き残るようにします。

BEAMに move_xx、move_yx、move_xy という3つの命令を実装するとしましょう(これらの命令は執筆時点の実際のBEAMには存在しません。あくまでこの例を説明するためのものです)。

#define OpCase(OpCode)    lb_##OpCode
#define Goto(Rel) goto *((void *)Rel)
#define Arg(N) (Eterm *) I[(N)+1]

  OpCase(move_xx):
  {
     x(Arg(1)) = x(Arg(0));
     I += 3;
     Goto(*I);
  }

  OpCase(move_yx): {
    x(Arg(1)) = y(Arg(0));
    I += 3;
    Goto(*I);
  }

  OpCase(move_xy): {
    y(Arg(1)) = x(Arg(0));
    I += 3;
    Goto(*I);
  }

goto * の * はデリファレンスを意味するのではなく、アドレスへのポインタへジャンプするという意味であることに注意してください。本来は goto* と書くべきでしょう。

さて、これらの命令に対応するコンパイル済みCコードが、メモリアドレス0x3000、0x3100、0x3200に置かれたとしましょう。 BEAMコードがロードされると、コード中の3つのmove命令は、それぞれの命令の実装のメモリアドレスに置き換えられます。 コード({move,{x,0},{x,1}}, {move,{y,0},{x,0}}, {move,{x,1},{y,0}})がアドレス0x1000にロードされたとしましょう。

                    / 0x1000: 0x3000 -> 0x3000: OpCase(move_xx): x(Arg(1)) = x(Arg(0))
{move,{x,0},{x,1}} {  0x1004: 0x0                                I += 3;
                    \ 0x1008: 0x1                                Goto(*I);
                    / 0x100c: 0x3100
{move,{y,0},{x,0}} {  0x1010: 0x0
                    \ 0x1014: 0x0
                    / 0x1018: 0x3200
{move,{x,1},{y,0}} {  0x101c: 0x1
                    \ 0x1020: 0x0

アドレス0x1000のワードは、move_xx 命令の実装を指しています。 レジスタ I が命令ポインタとして0x1000を指しているなら、ディスパッチは *I(すなわち0x3000)を取得し、そのアドレスへジャンプする(goto* *I)ことになります。

実際のBEAM命令の実装については、BEAM命令の章でより詳しく見ていきます。

プロセス切り替え

現代のマルチスレッドOSの多くはプリエンプティブスケジューリングを使っています。 これは、あるプロセスが何をしていようと、通常は割り込みを介して、OSがプロセスの切り替えのタイミングを決めることを意味します。 これにより、時間内にyieldしない行儀の悪いプロセスから他のプロセスが保護されます。

非プリエンプティブなスケジューラを使う協調的マルチタスクでは、実行中のプロセス自身がyieldするタイミングを決めます。 これには、行儀の悪いプロセスがCPUを占有し続け、他のプロセスがまったく実行されなくなりうるという欠点があります(古いバージョンのMicrosoft WindowsやMac OS、あるいはasync/awaitで並行性を扱うJavaScriptのようなシングルスレッド言語と同様です)。

一方で、yieldするプロセスが既知の状態でのみyieldすることを選べるという利点もあります。 たとえば、動的メモリ管理とタグ付き値を持つErlangのような言語では、作業用メモリにタグなしの値やダングリングポインタ、未初期化のメモリアドレスが存在しないときにのみプロセスがyieldするよう実装を設計できます。

add命令を例に考えてみましょう。2つのErlangの整数を足すには、エミュレータはまず整数のタグを外し、それらを加算し、結果を整数としてタグ付けする必要があります。 完全にプリエンプティブなスケジューラを使っていた場合、整数のタグが外れている間にプロセスがサスペンドされないという保証はありません。 あるいは、ヒープ上にタプルを作っている最中にプロセスがサスペンドされ、半端なタプルが残ってしまうかもしれません。 これでは、サスペンドされたプロセスのスタックとヒープをたどるのが非常に困難になってしまいます。

言語のレベルでは、すべてのプロセスは並行に動作しており、プログラマは明示的なyieldを扱う必要はありません。 BEAMはこれを、プロセスがどれだけの時間実行されてきたかを追跡することで解決しています。 これはリダクションを数えることで行われます。 この用語はもともと、ラムダ計算で使われる数学用語のβ簡約に由来します。

BEAMにおけるリダクションの定義はあまり厳密ではありませんが、「あまり時間のかからない小さな作業単位」と考えられます。 各関数呼び出しは1リダクションとして数えられます。 BEAMは各関数に入るたびに、プロセスがリダクションを使い切っていないかどうかをテストします。 リダクションが残っていれば関数は実行され、そうでなければプロセスはサスペンドされ、スケジューラはタイムスライスと呼ばれる一定数のリダクション分だけ、別の実行可能なプロセスを選んで実行します。 これは、コンパイラによって実装された協調的マルチタスクと見なせます。すべてのプログラムがきちんと行儀よく振る舞うことを保証しているわけです。

Erlangには直接的なループがなく末尾再帰の関数呼び出ししかないため、リダクションを使い切らずにまとまった量の作業を行うプログラムを書くのは非常に困難です。

スケジューラがどのように動作するかの詳細は、スケジューラの章で扱います。

メモリ管理

Erlangはガベージコレクションを行う言語であり、Erlangのプログラマとして明示的なメモリ管理を行う必要はありません。 とはいえBEAMコードのレベルでは、データ構造の初期化、スタックとヒープのオーバーランのチェック、スタックとヒープに十分な領域を確保することはコード自身の責任です。 これを正しく行わないと、クラッシュを引き起こすことがあります。

BEAM命令test_heapは、要求された分の領域がヒープにあることを保証します。 必要であれば、この命令はガベージコレクタを呼び出してヒープの領域を回収します。 ガベージコレクタはさらに、必要に応じてメモリを確保したり解放したりするために、メモリサブシステムのより低いレベルを呼び出します。 メモリ管理とガベージコレクションの詳細は、メモリ管理の章で扱います。

仮想機械としてのBEAM

BEAMは仮想マシンです。ここで言う「仮想」とは、ハードウェアではなくソフトウェアとして実装されているという意味です。 BEAMをFPGAで実装しようというプロジェクトもこれまでにあり、BEAMをハードウェアで実装することを妨げるものは何もありません。 BEAMを抽象マシンと呼び、BEAMのコードを実行できるマシンの設計図と見なすほうが、より的確な説明かもしれません。 実際、BEAMの「AM」は「Abstract Machine(抽象マシン)」の略です。

本書では、抽象マシンと仮想マシン、あるいはそれらの実装との間に区別を設けません。 より形式的な文脈では、抽象マシンはコンピュータの理論的なモデルであり、仮想マシンは抽象マシンのソフトウェア実装か、実際の物理マシンのソフトウェアエミュレータのいずれかを指します。

残念ながらBEAMの公式な仕様は存在せず、現時点ではErlang/OTPの実装によってのみ定義されています。 自分でBEAMを実装しようとするなら、どの部分が本質的でどの部分が偶発的なものかわからないまま、現在の実装を真似ようとするしかないでしょう。 妥当なBEAMインタプリタを作るには、観測可能なすべての振る舞いを真似る必要があります。