Let's Encryptの証明書失効から学ぶループと末尾再帰の関係

この間、Let's Encryptがバグで300万近くの証明書を失効させたというニュース流れました。

事の詳しい顛末は以下のBlogにかかれています。かなり詳しく書かれており、どのようなコードでバグが出たのか？というところまで解説されています。

jovi0608.hatenablog.com

さて、ちょっと話が飛ぶようなのですが、このBlogを読んで「ループと末尾再帰は本当に同等なのか？」という前々から私の頭の片隅にあった疑問がまたむくむくと頭を持ち上げてきましたので書き散らしました。

「ループと末尾再帰は同等である」というのはなんか関数型言語をかじった人の口からよく聞くような気がするのですが、私はそれに対して「そんな簡単に言ってしまっていいのか？」とずっと疑問を抱いていました。今回それを言語化しておこうと思います。

えっ？Let's Encryptの証明書失効と「ループと末尾再帰」になんの関係があるのかって？まぁちょっと話を聞いてください。

詳しくは上述したBlogを読んでほしいのですが、Go言語では以下のようなコードを書くと

func main() {
     var out []*int
     for i := 0; i < 3; i++ {
         out = append(out, &i)
     }
     fmt.Println("Values:", *out[0], *out[1], *out[2])
     fmt.Println("Addresses:", out[0], out[1], out[2])
}

$ ./test_gomistake
Values: 3 3 3
Addresses: 0xc0000160a0 0xc0000160a0 0xc0000160a0

このような結果になるそうです。要はoutに一時変数iの参照を入れてしまい、すると、ループが抜けたあとはiの値はfor文が進むにつれて変化しており最終的には3になります。結果、for文を抜けたあとoutの中身が全部3なってしまうという仕様です。

このgoの仕様をうっかりミスで忘れてしまい、outのなかは0, 1, 2になるという仮定してコードを書いてしまいバグを作り込んでしまったそうです。その結果が300万近くの証明書失効につながったと。恐ろしい。。。

これを受けて、Gauche開発者のShiro Kawaiさんがこんな事をつぶやいておられました

あああ、SchemerがCommon Lispでよくやるミスだ。参照取っちゃう以外にクロージャに閉じ込んじゃうのもありがち。やはりループ変数を破壊的変更するのは人類の手に余るのではhttps://t.co/k6AdNy068V
— Shiro Kawai (@anohana) 2020年3月9日

Shiroさんは「クロージャに閉じ込んじゃうのもありがち。」といってますが、そう。それですよ、私が言いたかったのは。ちょっとCommon Lispで以下のようなコードを書いてみましょうか。

CL-USER 1 > (do ((i 0 (+ i 1))
     (j '() (cons #'(lambda () i) j)))
    ((>= i 3) j))

(#<anonymous interpreted function 21CE99DA> #<anonymous interpreted function 21CCEA4A> #<anonymous interpreted function 20107912>)

このプログラムがやっていることはdoループ構文でiの値を0から3まで回して、lambdaでiの値を返すクロージャを作りそのクロージャのリストを返すプログラムです。つまり、このループが返すのは作ったクロージャへのポインタのリストです。

返ってきたのはクロージャのリストなので、リストの中にあるクロージャを改めて評価してみます。

CL-USER 2 > (mapcar #'funcall *)
(3 3 3)

どうでしょう？golangと似たような事が起こりました。もう分かると思いますが、要は、doループ内部のlambdaで束縛したiは、doループ外に出るときにはすでに3になってますので、doループから出たあとにlambdaを評価すると全部3になるんですね。

ちなみに、私はLispWorksを使いましたが、ANSI Common Lispの仕様としてこうなってるはずですので、どの処理系でも同じ結果が得られるはずです。

一方で、次のコードを考えてみましょう。

CL-USER 1 >(defun test ()
  (labels ((rec (acc i)
        (if (>= i 3)
            acc
          (rec (cons #'(lambda () i) acc) (incf i)))))
    (rec '() 0)))
TEST

CL-USER 2 > (test)
(#<anonymous interpreted function 21ACAE52> #<anonymous interpreted function 21ACAE3A> #<anonymous interpreted function 21ACAE22>)

CL-USER 3 > (mapcar #'funcall *)
(3 2 1)

こちらは先ほどと同じようにiで3回ループを回してそのiを束縛したlambdaを作りconsでリストに放り込んでいます。傍目には先のdo構文で上げた例と似た結果が得られているように見えます。

しかし、今回はdoループではなく、末尾再帰を使ったコードになっているのがわかるかと思います。

結果を見てましょう。3, 2, 1と異なる結果が得られました。つまり、末尾再帰とループとではiの束縛内容が異なると言えます。

ループの場合がある意味でdynamic binding的な挙動を示すのに対して、末尾再帰を用いた場合、iはlexical closureとして明確にiが閉じ込められていることがわかります。ですので、ループの場合は3, 3, 3となりますが、末尾再帰の場合は3, 2, 1となります（2, 1, 0とならないのはincfを使って破壊的に変更してるからです。やはり怖い破壊的変更）

僕が言いたかったのはこういうことです。ループと末尾再帰は「同じだ」と言われることがある気がするのですが、その実、束縛される変数。つまり環境のことを考えると同じと言えないのではないのでしょうか？また変数がどのように束縛されるかといった多分に言語仕様に依存してくる話だと思うのでそんな乱暴な話でまとめちゃっていいのかなぁと思います。関数型言語を標榜しているがloopもサポートする言語はたくさんあると思うので。

とういわけで、ループと末尾再帰が同じという言を聞くと本当かなぁ？と首を傾げてしまいます。ここらへん理論的にはどうなってんでしょうね？

p.s. いやShiroさんの件のツイートをみてつい懐かしいような気がして書きなぐってしまいした。