『関数型プログラミングに目覚めた！』のレビュー（Day-2）

Day1のレビューからの続きです。Day3のレビューに続きます。

もう一度注意

私は計算機科学者ではありませんし、プログラミングについては単なる素人です。職業上の個人的な関心（文系の1,2年次学生に対する教育をどうするか）から本書について思うところを記しているに過ぎませんのであまり技術的正確性を期待しないでください（そういう意味ではQiitaを利用すべきではなかったかもしれません）。以下で少しだけ書いたJavaScriptコードについてもJavaScriptをこの15年ほど触ってこなかったので大概なシロモノだと思いますが、問題があればお知らせください（一応どれも動作を確かめましたが）。

「0から999までの数を足すコードを書け」

Day2の主人公は悩み始めます(p. 44)。[0,1,2,...999]と手で並べ立てる気力はもちろんわかないし、なにより[0,1,2,3,4,5,6,7,8,9]のようなものは、ただ直に数字を並べているだけで「0から9までの数」というものを書き写した論理というものではないから『論理構造』として認めにくい、のだそうです（そうか？）。

[0,...,n]という配列を返すrangeといった関数を定義すればいいではないか、と思うわけですが（そして最終的にはそうなるのですが）、話はなぜか、まったく違った方向へと展開していきます。なので、この話は最後に。

『フローのない論理の宣言書』？

p. 50以降で、著者は命令型のコードがマシン操作手順書であり、フローそのものである、としています。これと「計算の命令ではなく論理をならべるコード」が対比されています。次のような純粋な関数型のコードを考えてみます：

fib(0) = 0
fib(1) = 1
fib(n) = fib (n-1) + fib (n-2)

著者は恐らくこれを「フローのない論理の宣言書」と認めてくれるのではないでしょうか。しかし、この3つが仮に「フローのない論理の宣言書」である等式だとしたら、これはコードにはなりません。5番目のフィボナッチ数が知りたいと思っても、この等式からはfib(5) = fib(4) + fib(3)やfib(4) = fib(5)- fib(3)といった等式を論理的に導出できるでしょうが、導出できる無数の等式の中からたとえばfib(5) = 5こそを導出すべき理由はこの等式の集合にはないからです。

一見等式に見えるfib(n) = fib (n-1) + fib (n)は、関数型プログラミング言語のコードとしては理念的には「fib(n)に該当する項に出会ったらfib(n-1) + fib(n-2)に書き換えなさい」という項書換えシステムの規則になります（細かいことを抜きにしてざっくり言えば）。したがって、fib(n) → fib(n-1) + fib(n-2)と書く方がわかりやすいかもしれません。fib(5)をこれらの書き換え規則に従って書き換えていってそれ以上書き換えができなくなったときに5になる、ということになります。ともあれ、それは等式（そのもの）ではありませんし、実際、書き換え規則なので、x = x + 1は（たとえば実際にHaskellでは）問題ないコードになります。これは評価しても単にx, x+1, x+1+1と順次書き換えられていくだけです（もちろんこの書き換えプロセスは終わらないのでプログラムは停止しなくなりますがコードそれ自体は完全に有意味なものです）。

つまるところ、関数型の宣言的（に見える）コードは、書き換え規則という形で書き換えシステムの操作を定めているものなのです（著者のいう『計算命令』そのもの！）。なお、書き換えシステムが複雑な項を書き換えていく際にどこからどのように手を付けるべきかは一意には決まらず、それについての方針が「評価戦略」です。

実際のところ、関数プログラミングは著者が思うほど都合のいいものではなく、「次にどう計算されていくか」を考えること抜きには遂行できません。

『計算』は『論理』の物質化？？

本書で何度となく繰り返されるフレーズ「計算は論理の物質化」にやってきました。ここでも相変わらず意味はよくわかりませんが、しかしDay1で出てきた「論理」云々よりは若干マシな気がします。1+1=2について、1+1が2であることが「論理」なのだそうです。この「論理」の意味はわからないでもありません。1+1が2に等しいことが論理的必然である、という程度の意味でしょう。細かいことを抜きにして、特に異論はありません。

問題は『計算』です。明瞭には書かれていないのですが、恐らく1+1から2を得ることを『計算』だと言っていて、それが人間の脳内なりハードウェアなりの因果的過程によってのみ存在するという主張だと理解しました。

『論理世界』の中だけで、ひとりで完結するような『計算』なんてどこにも存在しないから。（p. 65）

1+1を計算して2を得るという作業を1+1=2という式を算術体系によって証明するということだと理解しましょう。『証明』は『計算』だということなので（p.96）これは問題ないでしょう。1+1から2を得ることができるかどうかは適切な算術の体系（たとえばペアノ算術）の下で1+1=2という記号列に至るような証明図（当該体系の規則に従った記号列の連鎖）があるかどうかということなので、これは人間がいようがいまいが、また物理的な因果過程とも独立に決まっているア・プリオリな事柄です。つまり計算それ自体は『論理世界』の中で完結している対象です。実際、そうでないと計算論はア・ポステリオリな経験科学になってしまいます（がもちろんそんなことはありません）¹。

JavaScriptが「Scheme+Javaのハイブリッド言語」？

pp. 73-5ではJavaScriptが関数型プログラミング言語だとされています。それも「Scheme+Javaのハイブリッド言語」なのだそうです（p. 75）。

私はJavaScriptを殆ど読み書きできませんから、間違っているかもしれませんが、私の見る限りではJavaScriptにSchemeに近いところは殆ど無いように思います。Javaについても構文がC言語系の波括弧の多いシロモノだという点以外で似ているところは無いように見えます。

Brendan Eich自身のブログに拠る限り、JavaScriptの美点として述べられているのは、Schemeの第1級関数(first-class function)とJavaではなくSelf風のプロトタイプベースのオブジェクトシステムです。そもそも、JavaScriptとSchemeで共通の特徴だと言えそうなのは「動的型付け」と「第1級関数＆クロージャ」くらいだと思います（末尾呼び再帰の最適化をサポートしないし継続を第1級で扱えないしリストが手軽に扱えないしマクロもないしなによりステキな丸括弧が圧倒的に足りない）。その基準ならPythonやらRubyやら近年の言語はみんなSchemeとのハイブリッド言語で関数型プログラミング言語ですね。

動的型付けは関数型プログラミング言語かどうかとはなんの関係もない。第1級関数なしに関数プログラミングをするのはまったくの不可能事ではないにせよかなりつらいと思いますが、それで充分なわけでもなく。敢えてJavaScriptが「関数型プログラミング言語」だと主張するのはかなりムリがありそうです。

もし著者が「JavaScriptは関数型プログラミング言語だ」と誰かが言ったのを真に受けて本書を執筆したのだとしたら、それは残念なことです。

本書でのreduceの説明について

Amazon.co.jpのレビューで提示されている、本書でのreduceの扱いが適切でない、という点について私が理解する限りで、考えてみます。

reduce(f)を適用する際に、配列の最初の要素は関数fの第一引数の型を持たねばならず残りの要素は第二引数の型を持たなければなりませんからこの配列は本質的にヘテロジニアスなものですし、左畳込(いわゆるfoldl)と右畳込(foldr)の違いを考えれば、結局は関数fの適用順と蓄積の経過を理解しなければfoldを理解したことにはなりません。

配列の型とreduce

前半から取り上げてみます。まず、本書の中心的テーマである「0〜9までの数をすべて足す」について、本書とは少し違ったやり方でreduceを使って書いてみましょう。本書のようにreduceの第2引数として空配列時の初期値・蓄積値を指定しない使い方をしようとすると：

functional_sum_alt.js

function p(x){
  function f(y){
    return y+x;
  }
  return f;
} // これはクロージャの典型的使用例ですが、
  // 著者によるクロージャの説明 pp. 383-4に反して、
  // 参照透明性を損なうような副作用はありません。

function apply(x,f){
  return f(x);
}

var s = [0, p(1),p(2),p(3),p(4),p(5),p(6),p(7),p(8),p(9)].reduce(apply);

// (((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9) の
//「論理そのものをそのまま書く」ならこう書けるでしょう。

console.log(s);

というふうに書くことができます²。

reduceされる配列の最初の要素が一般的に残りの要素と型が違い（この場合はNumber 0とFunction p(1),...,p(9)）、いわば「身分」が違うことが、上のように「論理そのものをそのまま書いて」みれば明らかになります。つまり、一般にreduceの対象になっている配列はreduceに渡される関数との関係が違い型の異なった要素を一緒くたに収納している異質(heterogenous)な配列であることになります。

実は、reduceの第2引数を指定していいなら（つまり空配列に対してエラーを返さずにデフォルト値として0を返すのなら）、もう少しスッキリ書けます：

var s0 = [p(0),p(1),p(2),p(3),p(4),p(5),p(6),p(7),p(8),p(9)].reduce(apply,0);
var s1 = [0,1,2,3,4,5,6,7,8,9].map(p).reduce(apply,0);
var s2 = [0,1,2,3,4,5,6,7,8,9].reduce(plus,0)
// (((((((((((デフォルト値の0)+0)+1)+2)+3)+4)+5)+6)+7)+8)+9) 

この場合、行われていることは「0に1〜9をすべて足す」ではなくて、「初期値・デフォルト値の0に対して0〜9をすべて足す」になります。先ほどとは違いreduce対象の配列の各要素が先頭の要素を含めて型が同じであり、配列が同質(homogenous)なものであることに注意してください。これは重要な点で、そのお蔭でmapからreduceにそのまま連鎖したりできます（つまりs0をs1のように書くことができます）。

この[0..9].reduce(plus)と[0..9].reduce(plus,0)の違いは関数プログラミングで重要なreduceを理解する上で、決して瑣末なものではありません（そして後者の方が関数プログラミングで用いるにはずっと筋のよいものだと思います³）。逆に言えば、本書での著者の説明がもっぱら前者のみであることが、関数プログラミングとしての筋の悪さを示していることになるかと思います。

foldlとfoldr

左からのfoldと右からのfoldの違いとそれがもたらす効率の違いは関数プログラミングの勉強を始めると最初に問題になる重要な点です。左foldは末尾再帰、右foldはストリーム・無限リストの場合にも使える、リストからリストを作るときに順番を維持したければ右foldを、反転したければ左foldを使う、などの点を理解するにはまさに左右のfoldの（ここではreduceですが）の具体的な動作の仕方をきちんと理解する必要があります。ですので、これまた決して瑣末な点ではありません。しかし、80頁あるDay2でそのような理解を可能にする説明はまったく行われていません⁴。

reduce, map, rangeは命令型のループでしか書けない？？

Amazonレビューの続きを取り上げます。

また著者はreduce関数やrange関数やmap関数を命令型のループでしか書けないとしていますが（たとえばpp. 88,96,106）、これは明らかに誤りです

Day2を読んだときに確かにひどく気になった点です。実際、命令型のループ（著者はそれを「ハードウェアモード」と呼んでいます）を用いることなく（極力）副作用を伴わない関数型のコードでこれらを書くことはなんら難しくありませんし、関数プログラミングを勉強し始めて1〜2日目くらいに取り組む課題だと思います⁵。reduceがあればrangeやmapは容易に作れますから、ここではreduceだけ取り上げれば充分でしょう。

実際、以下の通りです：

recursive_reduce_sum.js

function head(arr) {
  return arr[0];
}

function tail(arr) {
  _arr = arr.concat(); _arr.shift(); return _arr;
} // 新たに配列を作成して返す

function fold_left(f, acc, arr){
  return !arr.length ? acc : fold_left(f, f(acc,head(arr)), tail(arr)); // 末尾呼び
}

/*
function fold_right(f, ini, arr) {
  return !arr.length ? ini : f(head(arr), fold_right(f, ini, tail(arr)));
}
*/

Array.prototype._reduce = function(f){
  return fold_left(f, head(this), tail(this));
};

function plus(x, y){
  return x + y;
}

var s = [0,1,2,3,4,5,6,7,8,9]._reduce(plus);
console.log(s);

コードの本体はfold_leftですが、それがなんら破壊的更新・副作用を伴うことなく再帰で書かれていることは見ての通りです。なんでまた「命令型のループでしか書けない」とか言ってしまったのでしょうか……⁶

効率が悪いのは誰のせいか

上記のコードについて、配列を破壊的に更新しないようにする関係上、再帰呼び出しが行われるたびに配列がコピーされます。これはかなり効率が悪いのですが、扱っているのが配列である以上は避ける事が困難です。配列の大きさを増やすにも全部のコピーが必要なので、関数型でやろうとすると色々とつらいです。これが配列ではなくイミュータブルなリストであれば、こうした操作でのコピーなどはもっと効率的になります（たとえばtailなら全体をコピーするのではなく単に次の要素への参照を返すだけで済みます）。

どうしてもJavaScriptで関数プログラミングの説明をしたいのならば⁷、最初からFacebook-Immutable.jsなどの不変データのライブラリを使ってリストをベースにして説明をすべきだったのでは、というのが率直な感想です。

あと、関数型プログラミング言語の処理系では末尾呼び再帰はスタックを消費せずにループにするのが普通のはずですが（Schemeではそもそも規格上要求されていたと思います）、JavaScriptの処理系はまずそうしてくれないようです。お蔭でますますJavaScriptで関数プログラミングを試みるのがつらいです（残念）。

で、「0〜999までの数をすべて足すコードを書け」はどうなったのか

結局、Day2では露骨に命令型のループを使ってreduce, map, range といった関数を定義し、それを使って

reduce(range(1000), plus)

という解答が与えられています（p. 109）。p. 44で問題が提示されてからこれだけのことになぜ65頁もかかってしまったのかですが、端的に言えばこういうことだと思います。

著者は[0,1,2,...,999]を生成するのにrange(1000) == [0,1,2,...,999]となるような関数rangeを必要としていました。しかし、著者はこのrangeを関数型では書けず命令型のループでしか書けないと考えたために、「関数プログラミングに目覚めた」はずがなぜか露骨な命令型でループを回すコードを書かなければならない事情を延々と正当化しなければならなかったのでしょう。しかし、それが著者の誤解か理解不足に基づくものであることは既に述べたとおりです。

なお、個人的には、命令型のコード（ただし外部に副作用がないものに限る）を関数型コードをグルーとしてつなぎ合わせるというプログラミングスタイル自体には別に文句はありません。ただ、そこに至る理屈付けがまたもやムチャクチャなのと著者の関数プログラミングに関する理解を疑わせるというのがDay2全体の感想です。しかも、これだとグルーには関数型が使えるが、グルーでつなぎ合わされる基本部品は命令型のループでなければ書けないかのような誤解を生むので、勘弁して欲しいなあと思います。

つづくかどうか

激しく疲労しました。Day3の疲労度はこんなものでは済まないだろうことが既にわかっているので、しばらく間が空くと思います。
　
　

1. なんというべきか、数学的対象としてのオートマトンとその物理的実現としての機械とを混同するのとちょうど同じような混乱があるのでしょう（たぶん）。 ↩

2. 0+1+2+3+4+5+6+7+8+9を正確に? (((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9) と書けば、1〜9はどれも二項演算子(+)の右側に出現するのに対して、0だけが左側に現れることに注意してください。 ↩

3. たとえばHaskellでfoldl1なんてまず使わないですよね（渡せる関数の型がa->a->aになってしまうせいもあるでしょうけど）。 ↩

4. 著者はブログで当該のAmazonレビューについて「そして私は実際に、このreduce(f)の「具体的特性」については、Qiitaでの貴重なフィードバックから重要性を認識していました。その結果どうしたか？というと、Day2で事細かく説明したのです。 」としていますが、少なくとも私にはそのような箇所は見当たりません（Day2でreduceを命令型のループで書いてみせている箇所はpp. 85-93ですが……どこに？）。ついでながら、次節で左foldを命令型のループ（著者のいう「ハードウェアモード」というやつですが）を使わずに関数プログラミングの作法で定義する際に、しばしばreduceの対としてreduceRightなどとして提供されている右foldもコメントアウトして定義しておきました。見ただけでもfold_leftとの違いは明らかですが（まず末尾呼び再帰でない）、本書にそうした説明は残念ながらありません。（なにか色々なことがデータ構造としてリストでなく配列を使っているせいだという気もしてきました。） ↩

5. ですので、「命令型のループでしか書けない」と言われるとぎょっとすると同時に、そもそも著者が本当に関数プログラミングを試みたことがあるのかどうかについての疑念が萌さざるを得ません。 ↩

6. 著者は自身のブログで「当たり前のことで、繰り返しますが、reduce関数やrange関数やmap関数は、命令型のループでしか書けません。なぜならば、ノイマン型コンピュータというハードウェアは究極的には命令型でしか動作しないからです。関数型の機械語なんて存在しません。」としていますが、この議論に従うならば著者自身のものを含めて全てのノイマン型計算機上のコードは命令型のループでしか書けないことになるわけですから、関数プログラミングはおよそ最初からまったくの不可能事だということになります。そうだとすれば本書が主張するような「関数型プログラミングに目覚める」などということは最初から不可能だったということになるはずで、関数プログラミングを巡る著者の思考の根の深い混乱がここでも明らかになっています。（ついでに言うと命令型かどうかはともかく再帰は一般的にスタックの様子がループとは違っていて再帰で書かれた関数は機械語レベルでもループになるわけではありません。） ↩

7. なぜ不向きな話題に使うほどそんなにJavaScriptが好きなのか…… ↩