□

(これは 2015/12/10 23:42 に書かれたものです)

想定される読者:プログラミングの記憶はないが、経験したことがあるはずのひと

末尾呼び出しって知ってる？　英語だとテイル・コール(tail call)なんだけど。
例えば「0からxまでの総和を返してくれる関数sum」を考えてみるじゃん。
C言語だと、

int sum(int x){
  int ret = 0;
  while(x>0){
    ret += x;
    x--;
  }
  return ret;
}
int main(){
  return sum(10);
}

こんな感じかな。Cとかは手続き型っていうんだけど、再帰っていう、自分自身が呼び出せる関数型の言語だと、

let rec sum1 x = if x < 0 then 0 else sum1 (x-1) + x

丁度こんな感じで書ける。これはOCaml。
ただこれは再帰呼び出しになってなくて、次が再帰呼び出しになってる例。 sum1 x と sum2 x 0 は同じ値が返ってくる。

let rec sum2 x i = if x < 0 else sum2 (x-1) (i+x)

何が違っているかっていうと、 else の後を見てほしいのだけど。 sum1 は、 sum1 (x-1) を実行したあとに、その値を使って x を足し込んで値を返さなきゃいけない。 sum2 は、呼び出した sum2 (x-1) (i+x) がそのまま sum2 の返す値になっている。自分自身を呼び出したあとに残っている仕事がなくて、再帰したあとの値がそのまま自分の返すべき値になっているというのが、末尾呼び出し。
これを最適化するのは結構簡単なんだけど、関数型言語においてはそれなりに強力なのです。演算が劇的に高速になる。
例えるなら、
「家から大学に来て授業を受けたあと、塾でバイトをして、お店にごはんを食べに行き、家に帰って寝る」
ということをしなきゃいけないとき、これを末尾呼び出し最適化しないままでは、
「家から大学に来て授業を受けたあと、塾でバイトをして、お店にごはんを食べに行き、塾へ戻ってごはんを食べて来たと言って、大学に戻ってバイトをしてきたと言って、家に帰って寝る」
ということをしている。仕事があるならもちろん戻らなきゃいけないんだけど(まだ塾で予習をしなきゃいけないとか、大学に荷物を置いて来たので取ってこなきゃいけないとか)、用もないのに戻るのはしんどいよね。
末尾呼び出し最適化をすると戻らなくて良くなる。つまり直帰ができるということ。
「家から大学に来て授業を受けたあと、塾でバイトをして、お店にごはんを食べに行き、すぐさま家に帰って寝る」
ということができる。それはなぜかというと、大学と塾を去るときに仕事を残してきていないことが分かっているから。
仕事を残して来てないかどうか判断して、ないなら直帰できることを覚えて行動するのが末尾呼び出し最適化なんだよねー、って先生が説明してて、超分かりやすくて面白かったのでした。えっ、それだけ？　うん、それだけ。

想定される読者:末尾呼び出し最適化を知っている人

先生が末尾呼び出し最適化を家から大学に行って帰るのに例えてて面白かったんだけど。
「みなさん大学が終わったらアルバイトがあるのでと塾に行って仕事をし、腹が減ったなあとお店へ行ってごはんを食べたら、もう直帰したいですよね？　そこからまた塾へ戻ってごはんを食べて来ましたと報告をして大学へ戻り、バイトしてきましたと言ってやっと家に帰ってベッドに入るなんてことはしませんよね。流石に仕事がまだ残っているときはレストランでごはんを食べた後に塾へ一度戻って仕事をしなきゃなりませんが、基本的には直帰したいという想いをみなさん持っているわけです。末尾呼び出し最適化をすると、みなさんはこの授業が終わったら塾でバイトをして、レストランで夜ごはんを食べ、そして家にすぐ帰って眠れるというわけです」
と、先生が末尾呼び出し最適化を説明するとこうなったのですが。ユニークだよね。