末尾呼び出し最適化についてあれこれ

この記事は「言語実装 Advent Calendar 2018」の22日目の記事です。

はじめに

「関数の最後の処理が関数呼び出しのときは、その関数呼び出しを goto に変換できる」「できねーよ」のやりとりを年一回ぐらいのペースで見かける気がしています。このあたりについて説明しようとすると結構長くなります。何度も同じ話を繰り返すのもなんなので、この手の議論が出てきたら「いろいろあるんじゃよ…いろいろ…」と言えるような記事を残しておこうかと思いました。

というわけで「末尾呼び出し最適化についてあれこれ」です。

言葉の定義

最初に、混乱を避けるために言葉を定義しておきたいと思います。

「末尾呼び出し」と「末尾再帰」

• 「末尾呼び出し」は「ある関数の末尾文脈で関数を呼び出すこと」です。
• 「末尾再帰」は「ある関数の末尾文脈でその関数自身を呼び出すこと」です。

「末尾再帰」では呼び出すのはその関数自身に限られますが、「末尾呼び出し」ではその関数自身を呼び出すかもしれないし、その関数以外を呼び出すかもしれません。「末尾再帰」は「末尾呼び出し」の特別な場合です。

末尾文脈

「末尾文脈」の定義ですが、「関数の最後の処理を行うところ」程度のゆるい定義としておきます。実のところ「末尾文脈」や「末尾呼び出し」、それに類する言葉の定義は言語によります。末尾呼び出し最適化を保証するプログラミング言語では、何が末尾文脈/末尾呼び出しであるか、言語仕様書で定めているはずです。

例として、 William D Clinger の Proper Tail Recursion and Space Efficiency という論文では lambda, if, set!, quote, 定数, 識別子 だけからなる小さな Scheme を定義した上で、末尾呼び出しを次のように定義しています。

• lambda式の本体は末尾式である
• (if E0 E1 E2) が末尾式であれば、E1とE2は末尾式である
• それ以外は末尾式ではない
• 末尾呼び出しとは、手続き呼び出しである末尾式のことである

R7RS では 3.5. Proper tail recursion で何が末尾文脈であるか、ずらずらと並べられています。

scala 2.12 specification では 6.6 Function Application の次の記述がそうでしょうか？

A function application usually allocates a new frame on the program's run-time stack. However, if a local method or a final method calls itself as its last action, the call is executed using the stack-frame of the caller.

(拙訳)関数適用は通常新しいフレームをプログラムの run-time スタックに割り当てる。しかし、ローカルなメソッドもしくは final なメソッドの呼び出しがそれ自身を最後のアクションとして呼び出す場合、その呼び出しは呼び出し元のスタックフレームを使用して実行される。

お使いの言語の言語仕様書を眺めてみるのも一興かと思います。

真正末尾再帰

「真正末尾再帰」に関しては R7RS の 3.5. に次のような記述があります。

A Scheme implementation is properly tail-recursive if it supports an unbounded number of active tail calls.

(拙訳) Scheme の実装は、回数に制限のない活性な末尾呼び出しをサポートしていれば、真正末尾再帰である。

「活性な末尾呼び出し」というのは「帰ってくるかもしれない末尾呼び出し」ぐらいの意味です。

条件とされているのは「回数に制限がないこと」です。呼び出しをジャンプ命令に置き換えることではありません。

真正末尾再帰の形式的な定義は William D Clinger の Proper Tail Recursion and Space Efficiency という論文で述べられています。読んでみるとわかるのですが、厳密に定義しようとするとかなりめんどくさい話になるので、深追いはしないことにします。

末尾呼び出しの除去

とりあえず wikipedia の Tail_call の項目から引きます(2018/12/18閲覧)。

Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is no longer needed, and can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination.
(拙訳) 末尾呼び出しはコールスタックに新しいスタックフレームを追加することなく実装できる。現在の手続きのフレームの殆どは最早必要なく、適切に変更された末尾呼び出しのフレームに書き換えることができる(プロセスのオーバーレイに似ているが、それの関数版である)。このときプログラムは呼び出されるサブルーチンへジャンプすることができる。通常の呼び出しシーケンスの代わりにこのようなコードを生成することは、末尾呼び出しの除去(tail call elimination)と呼ばれる。

本記事では「末尾呼び出しの除去」を「末尾文脈での手続き呼び出しを、駆動レコードを再利用し、呼び出す手続きの先頭へのジャンプに変換すること」と定義しましょう。

末尾再帰をgotoに変換できるケース

定義が終わったところで、末尾再帰をgotoに変換できる典型的な例を見てみましょう。

よくある単方向連結リストの foreach です。

// よくある単方向連結リスト
struct list {
    void *data;
    struct list *next;
};

typedef void function(void *);

// 単方向連結リスト lst の全要素に対し、関数 f を適用する
void foreach(function f, struct list *lst) {
    if (!lst) {
        return;
    } else {
        f(lst->data);
        return foreach(f, lst->next); // 末尾再帰
    }
}

関数foreachの末尾文脈でforeach自身を呼び出しています。これは末尾再帰です。いわゆる「引数付きのgoto」に変換できます。

void foreach(function f, struct list *lst) {
  head:
    if (!lst) {
        return;
    } else {
        f(lst->data);
        
        // 末尾呼び出しが除去されたコード
        f = f; // 引数を書き換える
        lst = lst->next; // 引数を書き換える
        goto head; // 関数の先頭へジャンプ
    }
}

この記事のタイトルを見て読んでみようと思うような方は、これは知っているんじゃないかな、と思います。

単純に goto に変換できないケースあれこれ

本題です。

末尾呼び出し/末尾再帰は call 命令を goto 命令に置き換えるだけの簡単な最適化だ、と思われている向きがあるんじゃないかな、と感じています。が、実はそんなに簡単な最適化ではないんです。いろいろあるんです。いろいろ。

というわけで、その「いろいろ」を思いついただけ書いてみます。

一時変数が必要なケース

次の関数を見てみましょう。特に意味のない関数です。

int f(int a, int b) {
    if (a == 0) return b;
    return f(b - 1, a - 1);
}

先ほどと同じように「いわゆる引数付きの goto」に置き換えてみましょう。

int f(int a, int b) {
  head:
    if (a == 0) return b;
    a = b - 1;
    b = a - 1;
    goto head;
}

a = b - 1 の時点でaの値が書き換わってしまいますから、これは元のプログラムと異なる振る舞いをします。

これを引数付きのgotoにするためには、一次退避用のメモリを用意する必要があります。

int f(int a, int b) {
  head:
    if (a == 0) return b;
    
    int tmp_a = b - 1;
    int tmp_b = a - 1;
    a = tmp_a;
    b = tmp_b;
    goto head;
}

これ自体は大した話ではないのですが、一時変数の使用を最小限にしようとすると、自明とはいえない最適化が必要になります。

一見末尾再帰だが実は末尾呼び出しのケース(1)

言語によっては一見末尾再帰だけれども、実は末尾呼び出しであるのケースがあります。

Scheme の my-for-each を見てみましょう。

(define (my-for-each f lst)
  (cond ((null? lst)
        '())
        (else
         (f (car lst))
         (my-for-each f (cdr lst)))) ; 「末尾呼び出し」だが「末尾再帰」ではない

Scheme コンパイラは、例えば次のようなコードを出力するでしょう(C風の疑似コードです)。

var my_for_each(var f, var lst) {
    var t0 = call(nullp, lst);
    if (t0) return nil;
    
    var t1 = call(f, lst);
    var t2 = call(cdr, lst);

    var t3 = call(my_for_each, f, t2);
    return t3;
}

これを次のような goto で先頭にジャンプできるコードにできるか、というとできません。

var my_for_each(var f, var lst) {
  head:
    var t0 = call(nullp, lst);
    if (t0) return nil;

    var t1 = call(f, lst);
    var t2 = call(cdr, lst);

    f = f;
    lst = t2;
    goto head;
}

というのも、my-for-eachは次のように呼び出されるかもしれないからです。

(define (g n)
  (set! my-for-each (lambda (n) '())) ; my-for-each を別の関数に束縛している
  (display n))

(my-for-each g '(1 2 3)) ; 1 とだけ表示されなければならない

(my-for-each f (cdr lst)) はあくまで my-for-each が束縛する手続きを呼び出します。もし処理系が (my-for-each f (cdr lst)) を手続きの先頭にジャンプする命令に書き換えてしまった場合、gのような手続きを渡したときの挙動が、言語仕様と異なったものになってしまいます。

末尾文脈で呼び出す手続きが変わり得る言語仕様では、一見末尾再帰でも実は末尾呼び出しであることがあります。この場合、「先頭へのgoto」には変換できません。言語仕様を参照なり決定なりした上で、注意深く見極める必要があります。

一見末尾再帰だが実は末尾呼び出しのケース(2)

次の手続きfは一見するとn回gを呼ぶ手続きですが、処理系の観点ではそうではありません。

(define (f n)
  (cond ((= n 0)
         0)
        (else
         (g)
         (f (- n 1)))))

理屈としては先ほどと同じです。gがfの束縛を変更するかもしれません。

gがfを書き換えるか否かが静的にわかる場合は良いのですが、分割コンパイルや動的ロードなどが絡むと一般には先頭へのgotoに変換できません。

(更に極端なことを言うと cond の展開後のコードや =、 - 等がfの束縛を変更するかもしれません)

Lexical closure が絡むケース

たとえばこんなコードを考えましょう。

(define (f n acc)
  (if (= n 0)
      acc
      (f (- n 1) (cons (lambda () n) acc))))

コンパイラはこのコードを次の疑似コードのようなコードに変換するでしょう。

var anonymous_procedure_0(var *n)
{
    return *n;
}

var f(var n, var acc)
{
    var t0 = funcall(eqv, n, 0);
    if (t0) return acc;

    // 話を簡単にするために、変数 n の寿命は無限とします。
    // make_closure_1 は手続きを作成する関数で、
    // 「第二引数を第一引数に渡して呼び出す手続き」を作成します。
    var t1 = make_closure_1(anonymous_procedure_0, &n);
    var t2 = n - 1;
    var t3 = funcall(cons, n, acc)
    var t4 = funcall(f, t2, t3);
    return t3;
}

この場合、(f 3 '())は「3を返す手続き」「2を返す手続き」「1を返す手続き」からなるリストを返すはずです。

ここで末尾の呼び出しを先頭へのgotoに変換したコードを見てみましょう。

var f(var n, var acc)
{
  head:
    var t0 = funcall(eqv, n, 0);
    if (t0) return acc;

    var t1 = make_closure_1(anonymous_function_0, &n);
    var t2 = funcall(cons, n, acc)
    var t3 = funcall(f, t1, t2);
    
    n = n - 1;
    acc = t2;
    goto head;
}

この場合(f 3 '())は「一回目のfの呼び出しで生成されたローカル変数nの中身を返す手続き3つからなるリスト」つまり、「0を返す手続き3つのリスト」を返します。

再帰呼び出しでは nはfが呼び出されるたびに新しく生成されるはずですが、変換後のコードでは全ての closure で n が共有されることになります。

自由変数を持つ手続きを返すような手続きで単に先頭へのgotoに変換するとプログラムの意味が変わってしまうことがあります。

末尾再帰を先頭へのgotoに変換しようとすると、単純に駆動レコードを再利用するわけにはいかないケースがあります。

(ただしこれは言語仕様や実装方法にも依ります。例えばOCamlのようなローカル変数の書き換えができない言語では、make_closure_1相当の処理は値のコピーを受け取るようにして実現できます。C++のように値をコピーするかするか参照を保持するか選べるようにする選択もありえます。)

x86 の cdecl で引数の数が増える末尾呼び出し

末尾呼び出しの除去ができるかどうかはABIに依存することがあります。

特に意味のない末尾呼び出しのコードです。

int g(int b, int c) {
    return b + c;
}
int f(int a) {
    return g(a, 1);
}
int main() {
    f(0);
    return 0;
}

x86 の Win32 の cdecl では、末尾呼び出しの除去を行わない場合、 g の呼び出し直後のスタックは以下のようになっているはずです。

+-----+
|     | ← SP はここを指している
+-----+
| IP2 | g の return 先のアドレス
+-----+
| b   | g への引数(b)
+-----+
| c   | g への引数(c)
+-----+
| BP1 | main の bp
+-----+
| IP1 | f の return 先のアドレス
+-----+
| a   | f への引数(a)
+-----+
| ?   | main 内で使われる何か

ここで末尾呼び出しの除去（スタックフレームの流用）を行おうとすると、IP2, b, c の3ワードを IP1, a の2ワードに書き込まなければいけません。当然ながら、不可能です。

というわけで、末尾呼び出しの除去ができるかどうかはABIに依存することがあります。

x86 の stdcall で引数の数が違う末尾呼び出し

ABIのせいで末尾呼び出しの除去ができない例もうひとつ、stdcallで引数の数が違う場合です。

stdcall の特徴は、関数から帰る際に呼ばれた側が引数を pop することです(x86 には ESP に定数を加算して ret する命令があり、それを利用できる)。

再度特に意味のない末尾呼び出しのコードです。引数の数が先ほどと違います。

int g(int b) {
    return b + c;
}
int f(int a, int b) {
    return g(a + b);
}
int main() {
    f(0);
    return 0;
}

stdcall では、末尾呼び出しの除去を行わない場合、 g の return 直前のスタックは以下のようになっているはずです。

+-----+
|     | ← SP はここを指している
+-----+
| IP2 | g の return 先のアドレス
+-----+
| c   | g への引数(c)
+-----+
| BP1 | main の bp
+-----+
| IP1 | f の return 先のアドレス
+-----+
| b   | f への引数(b)
+-----+
| a   | f への引数(a)
+-----+
| ?   | main 内で使われる何か

単純に末尾呼び出しの除去を行った場合、 g の return 直前のスタックは以下のようになっているでしょう。

+-----+
|     | ← SP はここを指している
+-----+
| IP1 | f の return 先のアドレス かつ、 g の return 先のアドレス
+-----+
| c   | g への引数(c)
+-----+
| -   | ゴミ(f への引数(a)が入っていた)
+-----+
| ?   | main 内で使われる何か

stdcall では詰んだ引数を pop するのは呼ばれた側(g)の役割です。gの引数はひとつなので、gはreturnするときIPを含めて2ワードをpopします。すると、スタックは次のようになります。

+-----+
|     | ← SP はここを指している
+-----+
| -   | ゴミ(f への引数(a)が入っていた)
+-----+
| ?   | main 内で使われる何か

SP がずれてしまいました。

というわけで、やはり末尾呼び出しの除去ができるかどうかはABIに依存することがあります。

真正末尾再帰

gotoの話から離れて、真正末尾再帰の話です。

末尾呼び出しの除去ができるか否かの議論でよく出てくる「末尾呼び出しは無条件に goto に置き換えられるものではないが、真正末尾再帰にはできる。ただし、 利点欠点がある」という話です。

定義の項でも述べましたが、「真正末尾再帰」の条件とされているのは「末尾文脈での呼び出しの回数に制限がないこと」です。呼び出しをジャンプ命令に置き換えることでも、駆動レコードを再利用することでもありません。

プログラムを真正末尾再帰にする方法は複数あるのですが、ざっと思いつくのは次のような感じです。

• 末尾呼び出し時、古い駆動レコードを削除してから、新しい駆動レコードを追加する
  • 「関数の戻り先」より後に引数を積まないとしんどい。そのため、x86のcall命令と相性が悪い。
• 駆動レコードを全て heap に置き、回収は gc に任せる
  • Lexical closure の扱いが簡単になる反面、遅い
• スタックがオーバーフローしたとき、使う必要のない駆動レコードを削除する
  • 実行速度が速い、とどこかで聞いたことがある
  • いかにも実装が難しそうではある(私はやったことがありません)

いずれも利点/欠点があり、また、ABIレベルで考慮が必要な話になります。ですので、無条件に真正末尾再帰が良いというものでもありません。しかしながら、ABIレベルでの変更が可能であれば、多くの場合真正末尾再帰にできます。

おわりに

というわけで「末尾呼び出し最適化は単純な話じゃなくて、いろいろあるんじゃよ…いろいろ…」という話をつらつらと書きました。