10/20/2016

クヌース博士が最初のErlangプログラマだった

Hacker Newsより。RabbitMQの開発者、Alvaro Videlaのエッセイ

ドナルド・クヌースのThe Art of Computer Programming(TAOCP)を綿密に調べ、興味深いものを発見した。丁度、彼がアルゴリズムの重要事項を説明する本のはじめで、彼はアルゴリズムの説明に別の表記を提出している。1.1節のそこに限って使われているように思え、本の他の部分は忘れ去れている。

ここに私が言っているその表記があり、クヌースが最大公約数アルゴリズムを示している。

Algorithm e

私にはErlangのシンタックスとほぼ同じように見える。関数節を分けるためにセミコロン(;)を使っている。実行する関数本体はその引数にマッチするパターンで選択される。最後の関数節はピリオド(.)で終わっている。if r=0 形式の中のガードがこれを実行する、など。erlangに翻訳してみよう。

-module(algorithm_e).

-export([f/1]).

f({M, N}) -> f({M, N, 0, 1});
f({N}) -> {N};
f({M, N, R, 1}) -> f({M, N, M rem N, 2});
f({M, N, R, 2}) when R =:= 0 -> f({N});
f({M, N, R, 2}) -> f({M, N, R, 3});
f({M, N, P, 3}) -> f({N, P, P, 1}).

大文字で変数を書くことは、Erlangで要求されていることで、erlangで期待される通り、()の代わりに{}を使ってタプルを囲んでいる。そして、最終的にキーワードを使う時に使われるガードを書いた。等号(=)で関数本体をあてがう代わりに、矢印(->)を使った。

面白いことに、Erlangシンタックスはある種のプラトニック形式の理想的な言語(Platonic Language Ideal)であることの証明は、全プログラミング言語以前にさかのぼる。さぁ、JoeRobertがひらめきを得たと認める時が来た。