Edited at

『関数型プログラミングに目覚めた!』のレビュー(Day-3)

More than 3 years have passed since last update.

Day1のレビューDay2のレビューからの続きです。(これでおしまい。)


さらにもう一度注意

私は社会科学分野を専門とする研究者で、情報科学研究者でもなければ職業的プログラマでもありませんので、そうした方々と混同しないでください。なるべく正確であるように努めてはいますが、確実に存在する技術的瑕疵を、私と別のしかも専門家の方々に帰されるのは心が痛みます。本書のレビューは、文系の学部1,2年次生向けのプログラミング教育という観点から、本書の前半214頁までを対象としてレビューしているものです。


「宣言型のコードはイベント駆動」?

さて、命令型のコードがフロー駆動であるのと対比されて、宣言型のコードはイベント駆動なのだそうです(p. 134)。フロー駆動でないからイベント駆動だという主張は理解困難な飛躍を含んでいます。そもそも、本書でここまで出てきたようなコードのどこがイベント駆動なのでしょうか(ということは実はそれらは宣言型のコードでなかったということでしょうか)1


「宣言型コードは参照透明である」とはどういうことなのか

さて、イベント駆動云々がどうであるにせよ、その直後に(p. 137)、次のようなコード:


interval_clock.js

var f = function(){

console.log(moment().format('MMMM Do YYYY, h:mm:ss a'));
};

var clock = setInterval(f, 1000);


が「宣言型のコード」だと言われてしまうと、「いやいやいやいやいや」といわざるを得ません。というのも、pp.147-8で著者は「宣言型のコードは参照透過である」としているのですが、このコードは明らかに参照透明性を破壊するものだからです。setInterval(f, 1000)はその値(TimerID)の他に当然ながら副作用を持っています。実際に:

var clock = setInterval(f, 1000);

var clock2 = setInterval(f, 1000);

というコードと、その同じ値の式同士setInterval(f,1000)clockを入れ替えた

var clock = setInterval(f, 1000);

var clock2 = clock;

というコードの挙動が違うことは実行してみれば一目瞭然です(参照透明なコードであれば両者を入れ替えても挙動が同じでなければなりません)2。したがって、先のコードは参照透明ではありません。(さらに言えば、実際には前者の中だけでも2つのsetInterval(f,1000)の返り値が異なってしまっているのでなおさら参照透明ではありません。)

なお、上記のコードを参照透明になるように書き換えること自体は難しくなく (参照透明ではないものの)宣言的に書くようにすること自体は難しくなく(訂正&追記参照):


interval_clock_alt.js

var moment = require('moment');

var f = function(){
console.log(moment().format('MMMM Do YYYY, h:mm:ss a'));
};

function setIntervalAction(f,t){
return function(_){
return setInterval(f,t);
};
}

var clock = setIntervalAction(f,1000);
var clock2 = setIntervalAction(f,1000);

/*
clock();
clock2();
*/


と副作用を持ったsetInervalをラップして返すようにしてやればいいのです(こうすればこの部分に関する限りは―つまり少なくともclock()などとして実際にアクションを起動するまでは―宣言型コードだと言い張ることはできますが、実際にはそうなっていないのが問題なわけです)。

(追記:JavaScriptのfunction式は関数オブジェクトを作って返すので、上記のclockclock2は関数としては等価ながら異なったオブジェクトを指すことになります。ですので、var clock2 = setIntervalAction(f,1000);var clock2 = clock;とした場合とではclock === clock2;の評価値が異なってしまいますので残念ながら参照透明性が成り立ちません。ただし、物理的等価性を見たりしないで普通に関数プログラミングをする限りでは、ほぼ参照透明なものとして扱うことができます。)

いずれにせよ、著者の「宣言型コードは参照透過だ」の対偶を取って、先に掲出した本書のコードが「宣言型コードではない」ことが導かれます。したがって、著者の主張は明らかに矛盾していますが、だとすると、どこがまずかったのでしょう?


多義性の誤謬(Fallacy of Equivocation)

その答えは本書で「宣言型コード」という言葉が2つの異なった意味をもって使われているところにあります。

まず第1に「宣言型コードは参照透明になる」という主張が真になるような意味での「宣言型コード」がどのようでなければならないか考えましょう。コードにコントロール・フローがないといった意味での「宣言型コード」であるためには、基本的にそのコードの各ステートメントが並べられているその順序に依存して挙動が変化することがないことが求められます。参照透明でない副作用を伴ったコードはこの条件を満たしません。したがって、そのような宣言型コードは少なくとも参照透明でなければならないことになります3。純粋関数型プログラミング言語やPrologのような論理型言語や制約プログラミングなどでは典型的にそうしたコードが書かれることになります。また、これらの場合に見るように、ある同じステートメントを複数回宣言しても、コードの挙動に影響はありません(宣言型コードの冪等性:余剰・多重定義として排除されるかもしれませんがそこは本質的ではありません)。実際、もし:

var clock = setInterval(f, 1000);

というコードが宣言的で参照透明ならば、それを2回繰り返しても

var clock = setInterval(f, 1000);

var clock = setInterval(f, 1000);

コードの挙動は変わらないはずです。が、実際にはもちろん挙動が変わるのですから、件のJavaScriptコードは参照透明ではなく、この意味での「宣言的コード」ではありません。

これに対して、本書に於ける第2の「宣言型コード」の意味は、「『問題の論理をそのまま書き写した』コード」です。『問題の論理をそのまま書き写す』なることがどのようなことであるかはともかく(それはDay1からずっと私にはよくわからないのですが)、その際に副作用のあるコードが、この意味での「宣言型コード」に入っていることが重要です。

var clock = setInterval(f, 1000);

は、(著者が自分でそう言っているからには)この意味での「宣言型コード」であるようですが、副作用を持つので参照透明ではなく、第1の意味での「宣言型コード」ではありません(『問題の論理』をそのまま書き写すことを念には念を入れて複数回するとコードの挙動が変わってしまうというのは実に皮肉な事態ですが)。

要するに、ここではあるコードが第2の意味で「宣言的コード」であるとされながら、またそれが参照透明性を含意する第1の意味での「宣言的コード」へと(意識的にせよ無意識的にせよ)すり替えられているのです。これは「多義性の誤謬 fallacy of equivocation」にほかなりません。

第1の意味で「宣言的」であるようなコードが、多くの場合に、第2の意味で「宣言的」であるということはあるでしょう。しかし、既に見たとおり第2の意味で「宣言的」であるからといって、そのことから「参照透過性」はなんら保証されないのです。

ともあれ、「宣言型」と「参照透過」を巡って著者と本書になにかひどい混乱・混同が生じていることは明らかです(そしてそれは本書の論旨からするとかなり致命的であるとも思います)。


n = n + 1 は論理破綻」か?

さて、「宣言型」の話が長くなってしまいましたから、次は軽く済ませましょう。


なるほど先輩。これは確かに論理ではないです。方程式の左辺と右辺の値が異なります。(……)宣言型のコードは問題の論理のみを扱い、計算結果を扱わないの。 (p. 144)


既にAmazonのレビューで指摘されている通り、命令型プログラミング言語でのn = n + 1というステートメントは、等式・方程式ではありません。そもそも=は等価性ではなくassignmentを表しており、また左辺のnは場所・記憶域を、右辺のnはそこに格納された値を指しています4。つまるところ、命令型プログラミング言語でのn = n + 1は端から方程式でもなんでもないので、登場人物セキヤによって「論理ではない」と言われるいわれもないのです。記号がでありさえすれば、n ← n + 1となって、このような誤解を産まなかったのかもしれません。

こうしてみると、登場人物サクラが力説する


命令型のコードでの問題は、『物質世界』の時間要素がコードの中に紛れ込んじゃうことよ。n = n + 1という方程式の右辺にあるn命令前の値。左辺にあるnは、命令後の値。命令前と命令後、つまり『時間』が違うの。方程式という論理に『時間』が違う『同じ変数』があり、=とされてしまっている(p. 145)


という主張がまったくの的外れであることも明らかになります。まずそもそもこのコードは方程式ではありません。しかも、左右でnの指示するものが異なっているのであり5、左辺はあくまで「場所」であって「命令後の値」なのではありません。むしろ両辺のnは同じ時間に属しています。ある時点でのある領域と同時にそこに収納されている値が取り扱われているのですから6

なお、関数型のコードとして見た場合にも、これが「方程式」ではなく項書換えシステムの書き換え規則n → n + 1であるという点はDay2のレビューに述べたとおりです。


こういう論理を破壊するような代入のやり方を特に破壊的代入って呼んだりするわね。(p. 144)


……そういうことじゃないと思います。


それが「参照透過性」なの? 本当に?

さて、まだまだ続きます(まだDay3の半分にも到達していない)。例の配列[0,1,2,3,4,5,6,7,8,9]の要素を順にコンソールに出力せよ、という新たな問いに対する解答がこれ(p. 151):


print_numbers.js

var out = function(n)

{
console.info('value:', n);
return n;
};

var after10 = map(range(10), out);

console.log(after10);


見ての通り、after10の代入・束縛のところで副作用として配列の要素を出力しているのですが、これがまたもや「宣言型コード」扱いを受けています(outの定義の中のconsole.log()は流石に命令型だとされている)。その点は前述の通りなので繰り返しません。

問題はoutの定義の中で最後にreturn n;として値を返していることを褒めていることです(なんだか「え〜そこはユニット()とかそういうの返すんじゃないの〜?」という声が聞こえます):


 入出力という命令であっても、入出力の目的が達成されたからもうあとは関係ない、じゃなくて、ちゃんとその計算結果の値は、論理世界に還流させて、続く論理操作につなげてやらないといけないのよ。それが参照透過性ね。

 よくわかります。『匠』はBeforeAfterで必ず結果をOUTPUTしなければいけない。(p.154-5, 強調引用者)


まず第1に、「入出力という計算結果の値」を論理世界に還流するというなら

var out = function(n){

return console.info('value:', n);
};

と書くべきでしょう。after10[undefined,undefined,...,undefined]になります(普通の関数プログラミング感覚からはこれは普通に適切なやり方です)。著者がreturn n;としているのは、入出力という『計算』の結果でもなんでもありません。

そして肝腎の第2点。関数が常に値を返すということが著者の言う「参照透過性」なのだそうです。それはいったいどこの星の「参照透過性」なんですか?


それ「全部一緒」なの?

引用するのが早そうなので:


クールなコーディングでは、宣言型の参照透過なコードになるわけだけれども、駆動するのはイベントよね?時間のフローでコードが駆動させる。『必要な時に必要な分だけ計算する方法』というのは、そのイベント駆動とピタリと合わさる。つまり、

『宣言型』『関数』『イベント駆動』『必要な時に必要な分だけ計算する方法』って全部一緒よね。


なお、『必要な時に必要な分だけ計算する方法』はおそらく遅延評価と、関数定義内部の式が関数が実際に呼び出されて評価されるまでは評価されない、ということの2つをひっくるめたもののようです(p. 164)。(あと「メモ化」もなぜかここに入るらしい……(p. 202))

ともあれ、なにがなにやら……

まずサンク(thunk)使えば、著者言うところの「必要な時に必要な分だけ計算する方法」は実現できるし、特に関数型に限らず使われているわけで、関係がありません。著者言うところの独自の『宣言型』は普通の意味での参照透明性とは関係がありません。イベント駆動ももちろん関係ないです。唐突な『関数』の出現も謎です。最後のものも、純粋かつlazyでなくeagerな関数型プログラミング言語は普通に存在します(すぐ思いつくものだとIdrisとUr)。


イデアとかそういうの

プログラミングに関する著者のここまでの主張を考えるに、哲学的主張についても、同じような信頼度だと思えば充分だと思うので割愛します。


そのメモ化の必要性と遅延評価に何の関係が??

ここも引用(疲れてきている):


 『必要な時に必要な分だけ計算する方法』を貫く限り、まったく同じ『計算』を何度も何度もやることもあるという『物質世界』の制限が厳然とあることを認識して、ここはあらかじめ解決しておく必要があるわけ。(……)だから、一回コードで計算したものは、メモリにキャッシュしておく仕組みをかましてやるの。『メモ化』っていうわ。

 なんかちょっとそのハードウェアモードめんどうくさそうですね。

 まあね、だから『車輪の再発明』なんてする必要ないじゃない。すでにそういう関数が用意されてあるのよ。

 おお、さすが関数型プログラミングだ! (p. 201)


……どこから突っ込んだものか。

まず、関数内部の式は呼び出しまで評価されない&遅延評価としての『必要な時に必要な分だけ計算する方法』なるものと、フィボナッチ数列を定義に従って素直に書き下ろした単純な木再帰(tree-recursion)の非効率性はまったく関係がありません。C言語でやったって同じです。

メモ化が「ハードウェアモード」てのも間違いです。普通に関数プログラミングでメモ化は書けます(フィボナッチ数列のメモ化はよく出てくる例題です)。疲労したアタマでいま適当に書いた何も考えてないコードで恐縮ですが、Haskellなら


memoized_fibonacci.hs

mFib n = memo ! n

where
memo = listArray (0,n) $ map fib [0..n]
fib 0 = 1
fib 1 = 1
fib i = memo ! (i-1) + memo ! (i-2)

です(もうJavaScriptでやる気力がわきません)。

で、メモ化は関数プログラミングではできない「ハードウェアモード」だけど親切な誰かがライブラリとして用意してくれてるよ、と言われて「さすがは関数型プログラミングだ!」というのは、それはさすがに関数プログラミングを馬鹿にしてるんですよね?7


フィボナッチ数列

Day3の最後はフィボナッチ数列を求める問題です。

凄い、ここで初めて再帰が出てきた!8 (いや本当にそうなんですよ)

まず最初に出てくるのは単純な下記のものです(p. 202):


fibonacci.js

var fibF = function(n){

return n <= 1 ? 1 : fibF(n-2) + fibF(n-1);
};

で、もちろん効率が悪いので、いっさいの無駄口は叩かずに、親切な人が用意してくれたlodashライブラリのメモ化関数memoizeを使って(p.204):


fibonacci_memoized.js

var fibF = _.memoize(function(n){

return n <= 1 ? 1 : fibF(n-2) + fibF(n-1);
});

一発で効率が改善出来ました。というわけで、「関数型プログラミングに目覚める」特訓の3日目は終了です。

……メモ化を実装しろとはいいません。ですが、せめてメモ化の前に蓄積引数使って末尾呼び再帰にする話くらいできなかったんでしょうか……本書で「関数型プログラミングに目覚め」てしまうと関数呼び出しのスタックがどうなっているかというような「些末事」は想像の埒外になってしまうようです。


というわけで、もう一度結論

私は本書を学生に読ませようとは思いませんし、率直に言って「どうにも困った本だなあ」と思います。このDay3までのレビューを見れば、なぜ私がそうした判断に到ったのかは多くの方に納得して頂けるのではないかと思います。


続かない

気力が尽きたので、Day3で本書のレビューは終了です。

研究関連の本1冊余裕で読めるくらいの時間を浪費した気がするのでもうやりません。

あとは誰か他の人がやってくだされば幸いです。

 





  1. もし入出力についても宣言型プログラミングを本当に徹底しようとすればそれを関数型リアクティヴプログラミング(FRP)によって行うというのが現状ではひとつの有力な方策だという程度のことであれば、その限りではそのような気がします(超絶的解釈的慈悲)。FRPが魔法の弾丸であるということは全然なさそうですが、手続き型に偽装された長大な関数適用のチェインでIO アクションを直接に構成するのではなくて、小規模なIO アクションに関連する値を関数プログラミングらしく合成していって最終的なIO アクションを構成しようという点についてはFRPがどうとかは別にして異論はありません(IOを長大なdo構文で書いているとわけわかんなくなってくるのは事実です)。 



  2. 変数があるひとつの値を取るが(意図された意味はその単一の値であるが)しかしそれがある集合のどの要素であるかはわからない(この場合に参照自体はこの集合であるとみなされる)、というような非決定性を許すと微妙な話になるはずですが、ここでは関係がありません。 



  3. (訂正:ここは最初「参照透明なら順序に依存しない」と書いていました。しかしよく考えたら宣言型スタイルで書くHaskellのパターンマッチングはorder-sensitiveでした。m(_ _)m) 



  4. 言わずと知れたL-valueとR-valueの話ですが、著者が入門的教科書を一読さえしていればこうはならなかったのではないか、と思います。 



  5. なお、このことを以って「nが参照透明でない」ということもできます(がそれは殆ど「趣味の問題にすぎない」かもしれません)。cf. Søndergaard & Sestoft, "Referential Transparency, Definiteness and Unfoldability", Acta Informatica, 27: 505-17, 1990., p. 507. 



  6. なお、「静的単一代入形式っていうのがあって」みたいな話は秘密です。命令型プログラミングに熟達すれば自動的に変数のバージョンが見えるに違いないのです。ワザマエ! 



  7. 本書でここまでほぼずっとサクラに唯々諾々のセキヤですが、ついにここでサクラのご託宣に逆らって見せたのだと思うことにします。 



  8. ところで、再帰は(JavaScriptが)関数型プログラミング言語だからできるのではなくてC言語でももちろんできます。(cf. p. 203)