8-4. ZINC 抽象機械 (ZAM) と ZAM へのコンパイル

8-2, 8-3節で説明した CAM および CAM へのコンパイル方式には後述する2つの無駄が存在する。ZINC 抽象機械 (ZAM) はそれらの無駄を解消し、関数プログラムをより効率的に実行できるように CAM を改良したものである。そこで本節では、まず CAM の2つの無駄をしっかりと理解してから、それらが ZAM および ZAM へのコンパイル方式でどのように解消されるかを見ていこう。

CAM と CAM へのコンパイル方式に存在する 2 つの無駄

次のプログラム例について考えよう。

  let rec sum x =
    if x = 0 then 0 else x + sum (x + (-1))
  in
  sum 3

ここで sum x は 0 から x までの和を求める関数である。このプログラムを (インタプリタで) 実行すると

     sum 3
  -> 3 + sum 2
  -> 3 + (2 + sum 1)
  -> 3 + (2 + (1 + sum 0))
  -> 3 + (2 + (1 + 0))
  -> 3 + (2 + 1)
  -> 3 + 3
  -> 6

のように計算が進む。ここでは CAM 上での対応する実行をいちいち示さないが、このプログラムをコンパイルして CAM 上で実行すると再帰のたびにスタックが使われる。例えば、sum 3 の計算中 sum 2 が再帰的に呼ばれた時点で、その戻り値として a が返ってきた後、sum 3 の残りの処理として、「 3 + a を計算する」ということを、CAM はコードと環境をスタックに退避することによって記憶する。

実は、このプログラムそのものは ZAM を使って実行してもスタックを使うことを避けられないのだが、このプログラムを次のように書き換えたものでは CAM と ZAM で実行効率の違いが現れる。

  let rec sum x =
    fun a -> if x = 0 then a else sum (x + (-1)) (x + a)
  in
  sum 3 0

このプログラムを (インタプリタで) 実行すると

     sum 3 0
  -> sum 2 3
  -> sum 1 5
  -> sum 0 6
  -> 6

のように計算が進む。(ここでは、追加された仮引数 a に、残りの計算 (の一部を先に行った結果) を渡していることに注目してほしい。) この実行列中の関数呼び出しのように、戻り値が返ってきた後の残りの処理を、スタックを使って記憶しておく必要がない関数呼び出しのことを「末尾呼び出し (tail call)」という。末尾呼び出しはそうでない関数呼び出しよりも本来は効率的に実行できるはずのものである。

ところが、8-2, 8-3節で説明した関数プログラムの CAM による実行方式は、末尾呼び出しかどうかと無関係に、常にコードと環境をスタックに退避してしまう。上のプログラムの末尾呼び出しも例外ではない。この点をもう少し詳しく見てみよう。上のプログラムを前節の方法で CAM の命令列にコンパイルすると、

    C(let rec sum x = fun a -> ... in sum 3 0, [ ])
  = Closure(C(fun a -> ..., [x; sum]); Return);
    Let; C(sum 3 0, [sum]); EndLet
  = Closure
      (Closure
        (C(if x = 0 then a else sum (x + (-1)) (x + a), [a; _; x; sum]);
         Return);
       Return);
    Let; C(sum 3 0, [sum]); EndLet
  = Closure
      (Closure
        (Ldi(0); Access(2); Eq;
         Test
           (C(a, [a; _; x; sum]),
            C(sum (x + (-1)) (x + a), [a; _; x; sum]));
         Return);
       Return);
    Let; C(sum 3 0, [sum]); EndLet
  = Closure
      (Closure
        (Ldi(0); Access(2); Eq;
         Test
           (Access(0),
            Access(0); Access(2); Add; Ldi(-1); Access(2); Add; Access(3); Apply; Apply);
         Return);
       Return);
    Let; C(sum 3 0, [sum]); EndLet
  = Closure
      (Closure
        (Ldi(0); Access(2); Eq;
         Test
           (Access(0),
            Access(0); Access(2); Add; Ldi(-1); Access(2); Add; Access(3); Apply; Apply);
         Return);
       Return);
    Let; Ldi(0); Ldi(3); Access(0); Apply; Apply; EndLet

となる。ここで、赤く強調されたApplyは元のプログラムの sum (x + (-1)) (x + a) に対応する末尾呼び出しであり、CAMによるこの命令の実行では、残りの命令列 [Return] と関数適用時における環境 env がスタックに退避される (8-2節のCAMの遷移表を参照)。ここで注目して欲しいのは、戻り値が返ってきた後の残りの処理は、Return 命令によって戻り値を (さらに上位の呼び出し元に) 返すだけであり、環境 env が Access されることはない、ということである。したがって、この末尾呼び出しで環境 env をスタックに退避したことは完全に無駄になってしまっている。

上の CAM 命令列は CAM のもう一つの無駄を示す例にもなっている。青く強調された Apply に注目してほしい。これは元のプログラムの関数適用 sum 3 に対応しており、呼び出し先では Closure 命令によって元のプログラムの fun a -> ... に対応するクロージャが生成され、すぐに Return される。このクロージャはその後すぐ緑色の Apply 命令によって引数 0 に適用されて消滅するので短命である。一般に N 引数関数にちょうどN 個の実引数を渡して呼び出す全適用 (total application) では、このような中間的で短命なクロージャ生成とそのためだけの関数呼び出しがそれぞれ N-1 回ずつ起こってしまうので CAM は実行効率が悪い。

以上のように、CAM による関数プログラムの実行には 2 つの無駄が存在する。以下では、関数プログラムをより効率的に実行するために、ZAM および ZAM へのコンパイル方式がどのように設計されているか、という本題に入っていこう。

ZAMの構成

ZAMは以下の4つの要素を持つ。

Code (コード): 実行すべき命令列である。1つ1つの命令は、次の項で説明する。
Environment (環境)：CAMの環境と同じ役割を果たす。
Argument Stack (引数スタック): 計算途中の値を保持したり、関数引数や戻り値を関数間でやりとりするためのスタックである。
Return Stack (リターンスタック): 関数呼び出しから戻ってきた後に行う「残りの処理」を記憶しておくためのスタックである。

上の構成で、引数スタックとリターンスタックを、CAM のように一つにまとめることも実は可能である。しかし、抽象機械の動作が若干複雑になってしまうため、説明を簡単にするために本実験では分けている。

ZAM の「値」

ZAM の実行時の値は、以下のように定義される。

type zam_value =  
  | ZAM_IntVal  of int   (* ZAM の値に対するタグにはZAM_ をつける *)
  | ZAM_BoolVal of bool
  | ZAM_ClosVal of zam_code * zam_env  (* 再帰関数に対応するクロージャ *)
  | ZAM_Epsilon  (* 渡されたすべての引数を使い切ったことを表す値ε *)
and zam_stack = zam_value list (* スタック *)
and zam_env = zam_value list (* 環境は、1つのスタックフレームに相当する。 *)

CAM の値に加えて新しく値εが追加されているが、その用途は後述する。

ZAMの命令, 状態遷移, ミニOCamlからのコンパイル

ZAMの命令は、以下のように定義される。

type zam_instr =
  | ZAM_Ldi of int                    (* CAM_Ldiと同じ *)
  | ZAM_Ldb of bool                   (* CAM_Ldbと同じ *)
  | ZAM_Access of int                 (* CAM_Accessと同じ *)
  | ZAM_Closure of zam_code           (* CAM_Closureと同じ *)
  | ZAM_Let                           (* CAM_Letと同じ *)
  | ZAM_EndLet                        (* CAM_EndLetと同じ *)
  | ZAM_Test of zam_code * zam_code   (* CAM_Testと同じ *)
  | ZAM_Add                           (* CAM_Addと同じ *)
  | ZAM_Eq                            (* CAM_Eqと同じ *)

  | ZAM_Apply                         (* 関数呼び出し *)
  | ZAM_TailApply                     (* 末尾呼び出し *)
  | ZAM_PushMark                      (* 引数スタックに特殊な値εを積む *)
  | ZAM_Grab                          (* 引数スタックトップの値を環境に移す *)
  | ZAM_Return                        (* 関数呼び出し元に戻る *)
and zam_code = zam_instr list  (* コードは、命令の列である *)

以下に掲載する ZAM の状態遷移を見てもらえば分かるように、Ldi 〜 Eq の動作は引数スタックを操作するという点以外は CAM と同じである。その他の Apply 〜 Return は ZAM 独特の動作をするので、本項で詳しく説明する。

遷移の表
遷移前の状態遷移後の状態

コード環境引数スタックリターンスタックコード環境引数スタックリターンスタック

Ldi(n) :: c env s r c env n :: s r

Ldb(b) :: c env s r c env b :: s r

Access(i) :: c env s r c env env(i) :: s r

Closure(c') :: c env s r c env <c', env> :: s r

Let :: c env v :: s r c v :: env s r

EndLet :: c v :: env s r c env s r

Test(c1, c2) :: c env true :: s r c1; c env s r

Test(c1, c2) :: c env false :: s r c2; c env s r

Add :: c env n1 :: n2 :: s r c env (n1 + n2) :: s r

Eq :: c env n1 :: n2 :: s r c env (n1 = n2) :: s r

Apply :: c env <c', env'> :: v :: s r c' v :: <c', env'> :: env' s <c, env> :: r

TailApply :: c env <c', env'> :: v :: s r c' v :: <c', env'> :: env' s r

PushMark :: c env s r c env ε :: s r

Grab :: c env ε :: s <c', env'> :: r c' env' <c, env> :: s r

Grab :: c env v :: s r c v :: <c, env> :: env s r

Return :: c env v :: ε :: s <c', env'> :: r c' env' v :: s r

Return :: c env <c', env'> :: v :: s r c' v :: <c', env'> :: env' s r

遷移の表
遷移前の状態	遷移後の状態
コード	環境	引数スタック	リターンスタック	コード	環境	引数スタック	リターンスタック
Ldi(n) :: c	env	s	r	c	env	n :: s	r
Ldb(b) :: c	env	s	r	c	env	b :: s	r
Access(i) :: c	env	s	r	c	env	env(i) :: s	r
Closure(c') :: c	env	s	r	c	env	<c', env> :: s	r
Let :: c	env	v :: s	r	c	v :: env	s	r
EndLet :: c	v :: env	s	r	c	env	s	r
Test(c1, c2) :: c	env	true :: s	r	c1; c	env	s	r
Test(c1, c2) :: c	env	false :: s	r	c2; c	env	s	r
Add :: c	env	n1 :: n2 :: s	r	c	env	(n1 + n2) :: s	r
Eq :: c	env	n1 :: n2 :: s	r	c	env	(n1 = n2) :: s	r




Apply :: c	env	<c', env'> :: v :: s	r	c'	v :: <c', env'> :: env'	s	<c, env> :: r
TailApply :: c	env	<c', env'> :: v :: s	r	c'	v :: <c', env'> :: env'	s	r
PushMark :: c	env	s	r	c	env	ε :: s	r
Grab :: c	env	ε :: s	<c', env'> :: r	c'	env'	<c, env> :: s	r
Grab :: c	env	v :: s	r	c	v :: <c, env> :: env	s	r
Return :: c	env	v :: ε :: s	<c', env'> :: r	c'	env'	v :: s	r
Return :: c	env	<c', env'> :: v :: s	r	c'	v :: <c', env'> :: env'	s	r

ZAM は上記の遷移を繰返してコード (命令列) を消費していき、コードが空になったら引数スタックトップにある値を最終結果として返す。ただし、その時、引数スタックの要素が 2 つ以上あったり、リターンスタックが空でなかったり、環境が空でなかったら、何らかのエラーなので (ミニOCamlのプログラムを正しくコンパイルしたコードであれば、そのようなことは起きないはずなので)、エラーとする。

新しく説明が必要な Apply 〜 Return は、すべて関数と関数適用に関する ZAM 命令である。そこで、これらの命令の動作を理解するために、ミニOCamlの関数と関数適用がどのような ZAM 命令列にコンパイルされるか見てみよう。ZAM のためのコンパイル関数 C の定義のうち、関数と関数適用に関係する部分だけを抜粋したものを以下に掲載する。

  C(fun x -> e, venv) = Closure(T(e, x :: _ :: venv))
  C(let rec f x = e1 in e2, venv) = Closure(T(e1, x :: f :: venv)); Let; C(e2, f :: venv); EndLet
  C(e e1 ... eN, venv) = PushMark; C(eN, venv); ...; C(e1, venv); C(e, venv); Apply

  T(fun x -> e, venv) = Grab; T(e, x :: _ :: venv)
  T(let rec f x = e1 in e2, venv) = Closure(T(e1, x :: f :: venv)); Let; T(e2, f :: venv)
  T(e e1 ... eN, venv) = C(eN, venv); ...; C(e1, venv); C(e, venv); TailApply

ここで、補助関数 T は、式 e の実行が終わった後の (e を包含する関数における) 残りの計算が何もないと分かっている時、そのことを利用して (関数 C が生成するより) 効率的なコードを生成するために使われている。たとえば、fun x -> e に現れる式 e の実行はそのようなケースに該当するので、T を使ってコンパイルされている。C と T を使い分けることによって、前項で説明した末尾呼び出しを効率的に ZAM で実行することが可能になる。関数適用を C でコンパイルすると Apply 命令が使われるが、T でコンパイルすると TailApply 命令が使われる。前掲の ZAM 状態遷移表を見てもらえば分かるが、ZAM の Apply 命令は基本的に CAM のそれと同じであり、違うのは現在のコードと環境を、引数が積まれるスタックとは別のリターンスタックに退避することである。一方、TailApply 命令は Apply 命令と違ってコードと環境をリターンスタックに退避しないため効率的である。

ZAM と CAM のコンパイル方式に関するもう 1 つの大きな違いは、関数適用 e e1 ... eN (ただし e は関数適用でない) のコンパイルにおいて、ZAM では、N 個の実引数 e1, ... eN に対して Apply (もしくは TailApply) 命令が 1 つしか導入されないように設計されている点である（一方、CAM では N 個の Apply が導入される）。これによって前項で説明した N-1 回の無駄な関数呼び出し＆クロージャ生成が起きてしまうという CAM の問題を避けているのだが、そのように変更しても抽象機械全体が整合的に動作するようにするため、ZAM には Grab と PushMark という新しい命令が追加され、Return 命令の動作も変更されている。

まず、新しく追加された Grab 命令について説明しよう。Apply 命令が実行された際、CAM はスタックにちょうど 1 つの実引数が積まれているものとして動作すればよかった。一方、ZAM では、スタックに 1 つ以上の実引数が積まれている可能性を考慮する必要がある。Apply命令は、スタックトップにある 1 番目の実引数しか環境に移してくれないので、2 番目以降の実引数については、呼び出された関数側が、必要に応じてGrab 命令を使ってスタックから環境に移すようになっている。

その際、呼び出された関数側は、スタックにまだ実引数が残っているかどうか判定する必要がある。そのために、ZAM のコンパイル方式では、関数適用 e e1 ... eN のコンパイルにおいて、N 個の実引数をスタックに積み始める前に PushMark 命令で特殊な値εを積んでおくことによって、実引数が残っているかどうかをスタックトップの値がεかどうか調べるだけで判定できるようにしている。

実際に ZAM は、Grab 命令や Return 命令の実行時に、スタックに実引数が残っているかどうか判定し、その結果に応じて動作を変えている。なぜか？それは、ミニOCaml言語においては、

  プログラム 1: (fun x -> fun y -> x + y) 3

や

  プログラム 2: (fun f -> fun x -> f x) (fun x -> fun y -> x + y) 1 2

のように、関数が (字面上) 要求している引数の数と、(字面上) 渡されている実引数の数が一致しないことがあるからである。プログラム 1 では、2 つ要求しているのに 1 つだけ、プログラム 2 では 2 つ要求しているのに 3 つも渡されている！このようなプログラムを ZAM 上で実行しようとすると、プログラム 1 では Grab 命令を実行したのに引数スタックに実引数が残っていなかったり (つまり引数スタックトップがε)、プログラム 2 では Return 命令を実行したのに引数スタックに実引数が余っていたりする。プログラム 1 の場合、ZAM は (fun y -> 3 + y に対応する) クロージャを生成して呼び出し元に返す必要があるし、プログラム 2 の場合、戻り値の (fun y -> 1 + y に対応する) クロージャを余っている実引数 (ここでは 2) に適用しなければならない。前掲の状態遷移表における Grab 命令や Return 命令のところを見て、実際そのように動作することを確認してほしい。

コンパイル関数 C と補助関数 T の残りの定義は以下の通りである。

  C(x, venv) = Access(position x venv)
  C(n, venv) = Ldi(n)
  C(b, venv) = Ldb(b)
  C(e1 + e2, venv) = C(e2, venv); C(e1, venv); Add
  C(e1 = e2, venv) = C(e2, venv); C(e1, venv); Eq
  C(let x = e1 in e2, venv) = C(e1, venv); Let; C(e2, x :: venv); EndLet
  C(if e1 then e2 else e3, venv) = C(e1, venv); Test(C(e2, venv), C(e3, venv))

  T(x, venv) = Access(position x venv); Return
  T(n, venv) = Ldi(n); Return
  T(b, venv) = Ldb(b); Return
  T(e1 + e2, venv) = C(e2, venv); C(e1, venv); Add; Return
  T(e1 = e2, venv) = C(e2, venv); C(e1, venv); Eq; Return
  T(let x = e1 in e2, venv) = C(e1, venv); Let; T(e2, x :: venv)
  T(if e1 then e2 else e3, venv) = C(e1, venv); Test(T(e2, venv), T(e3, venv))

上の定義は、末尾呼び出しかどうか区別できるように CAM のコンパイル方式を拡張しただけのものである。以下に、末尾呼び出し版 sum 関数の ZAM 命令列へのコンパイル例を掲載するので、ZAM 上でこれが (CAM と比べて) 効率的に実行できることを自分で確認してほしい。

    C(let rec sum x = fun a -> ... in sum 3 0, [ ])
  = Closure(T(fun a -> ..., [x; sum]));
    Let; C(sum 3 0, [sum]); EndLet
  = Closure(Grab; T(if x = 0 then a else sum (x + (-1)) (x + a), [a; _; x; sum])));
    Let; C(sum 3 0, [sum]); EndLet
  = Closure
      (Grab; Ldi(0); Access(2); Eq;
       Test
         (T(a, [a; _; x; sum]),
          T(sum (x + (-1)) (x + a), [a; _; x; sum])));
    Let; C(sum 3 0, [sum]); EndLet
  = Closure
      (Grab; Ldi(0); Access(2); Eq;
       Test
         (Access(0); Return,
          Access(0); Access(2); Add; Ldi(-1); Access(2); Add; Access(3); TailApply));
    Let; C(sum 3 0, [sum]); EndLet
  = Closure
      (Grab; Ldi(0); Access(2); Eq;
       Test
         (Access(0); Return,
          Access(0); Access(2); Add; Ldi(-1); Access(2); Add; Access(3); TailApply));
    Let; PushMark; Ldi(0); Ldi(3); Access(0); Apply; EndLet

発展課題 8-4.

ZAM に対するインタープリタ、つまり、ZAM の状態を受けとると、それを本節で説明した ZAM の実行方式に従って実行し、最終的な答えを返す関数を実装しなさい。
上の実装の正しさを示すための命令列をいくつか用意して実行してみなさい。
ここでの実装では、基本演算は、Eq (=) と Plus (+) しかない。これに、引き算、かけ算、大小比較をする演算などを追加してみなさい。このためには、抽象機械の命令を増やすとともに、それに対応する処理を書かなければいけない。
本節の ZAM のコンパイラの説明を参考にして、ミニOCaml言語から ZAM の機械語へのコンパイラを実装しなさい。
コンパイラが正しく変換できていることを示す例を与えて実行しなさい。
また、変換されたコードを、ZAM の実装にかけて実行し、正しい答えが返ってくるかを試しなさい。
いろいろなプログラム例をインタープリタ, CAM, ZAM それぞれで実行し、実行速度を比較しなさい。

トップ, 前へ,

亀山幸義 (このページは、2023年度まで筑波大学にいた海野広志先生(現在、東北大学)に作成いただいたものです。もちろん質問は亀山あてにしてください。)