狂信者は「関数型プログラミング」と「手続き型プログラミング」の差が分かった気がするよ。怪文だよ。以降は「関数型」、「手続き型」とそれぞれを略称するよ。

結論だよ

ここでは計算のステップに関する「関数型」と「手続き型」の違いを纏めるよ。

「関数型」には副作用がないよ
「手続き型」には副作用があるよ

でもこれらは表面的な違いだよ。実は「計算資源」の利用についてそもそも大きな違いを持つよ。

「関数型」は計算資源を記述する
「手続き型」は計算資源の利用を記述する

これが本質だよ。よく言われる「関数型では関数が第一級オブジェクトだ」という主張はね、「関数=計算資源」と読み替えていいよ。つまり
「関数型では計算資源が第一級オブジェクト」
だよ。反対に
「手続き型では計算資源の利用が第一級オブジェクト」
だよ。

僕らの計算機は半導体で出来ているよ。買ってきたCPUもメモリも有限の「計算資源」で、その多くはシリコンの土台に回路を組んでいるよ。シリコン土台の面積は有限だからコンピュータの「計算資源」は本質的に有限だよ。そのことを忘れないで欲しいよ。

計算資源とその利用について述べるよ

関数型言語では計算の一連の処理である関数を第一級オブジェクトとして、それらを組み合わせて計算を作り上げるよ。例えば3つの数a, b, cの和を取ってdに代入するよ。

d := add(add(a,b), c)

回路で書けばこれはこうだよ。

でも実際の計算機の加算回路が3変数を一気に足せるとは限らないね。もしも2変数の加算器を1つしか持たない計算機ではこれを2回の計算ステップに分解するね。

[1] d := add(a, b)
[2] d := add(d, c)

計算ステップという未定義な言葉を使ってしまって申し訳ない。でもこのステップの分割が関数型と手続き型を根本から分けているんだ。こうやって計算をステップに分けると、有限の「計算資源」を繰り返し他の用途に使うことが出来るんだ。実際に

[1] d := ADD(a, b)
[2] d := ADD(d, c)

と同じ回路を繰り返し使えるようになるよ。予めネタバラシをすると最初の計算方法が関数型の記述で、後半の計算方法が手続き型の記述だよ。

回路屋としてはこの2つの回路の差は「クリティカルパス」の話に帰着するんだ。加算器の入り口から出口まで出力が出てくるには現実的な時間が必要になるよ。例えばナノ秒とかね。
1つの加算器が正常に作動するのに必要な時間はΔtとすると、2つの加算器が正常に動作するには2Δtの時間がかかるよ。僕らは回路の一定面積を同じクロック信号で管理するから、その範囲の回路はこのクロック信号の周期の間に処理を正常完了してくれないと困るよ。でないと回路にグリッチと呼ばれる異常信号が流れてしまう。

3変数の加算器では違いが曖昧かもしれないね。でもすぐ違いを実感することが出来るよ。次は3変数a, b, cではなく10000変数a_1, …a_10000を加算して欲しいんだ。
デジタル回路の気持ちに戻ると、関数型で記述した10000変数の加算が通るにはざっと10000Δtの時間がかかるよ。もしも樹上に加算をして巧みにやってもlog2(10000)Δt時間かかって、10000個の加算器を必要とするよ。
手続き型で10000個の計算が通るにはもっと大変な思いをするよ。1個しか加算器がないならやっぱり10000Δtの時間がかけて、単一で同じ加算器を繰り返し利用するよ。もし10000個の加算器を用意できたとしても、僕らの計算機にはこれら10000個の加算器を同時に動かす単一命令が必要になるよ。そんな単一命令があればlog2(10000)Δt時間で再び計算できるよ。とっても変だね。それでもクリティカルパスはなお加算器を1度通過する時間Δtで抑えられてるよ。(とはいえ本当は10000の半分5000個の加算器があれば実のところは大丈夫だよ。ステップ数は変わらないよ)
そして重要なことだよ。回路は一番長いパスの部分が、回路全体が動ける周期を決定しているよ。だから10000個の計算をステップに分けずに計算しようとする関数型の考え方は「長大な回路」が出来上がって回路屋的にはいつか破綻するよ。

プログラミング言語によって関数型か手続き型か違うの？

プログラミングにはいつも関数型なところと手続き的なところがあるはずなんだよ。

C言語は手続き型言語であるよね。書いてる四則演算は単一ステップで実行されるしメモリとのアクセスも手続きを記述する。四則演算器(普通なALU, Arithmetic Logic Unitという回路)やメモリの計算資源の利用によって計算を記述しているよ。でも関数型の記述、つまり処理をひとまとめにして副作用は見えない関数にする、を支援しているよ。

多くの関数型言語はより低層の有限な「計算資源」を感じさせないね。だから確かに手続き型の記述、つまり計算資源を利用する方法を提供する、は支援していないよ。関数型言語で記述してるのは、あくまで計算資源のあり方なんだよ。記述した計算資源の利用、つまり計算資源を繰り返し使うとか、この条件の時使うとか、それらは本質的に存在しないよ。でも関数型言語で有限な資源もあるよ。哲学的だから気づきづらいかもしれないね、でもそれは実は使える言葉だよ。関数型には本質的に書き換えの概念はなく、計算資源のあり方を書いてるから、その計算資源のワイヤーのどこそこの値がというのは問えるけど、問うためにそこに名前(変数名、ワイヤー名)をつけると、それが有限ではあるよ。

こういう話をしていて回路記述言語(HDL, Hardware Description Language)を書いてる皆んなは気づいたよね。そうだよ、HDLでは計算資源のあり方ばっかり書いてるから、そりゃ関数型チックになるに決まってるんだよ。

計算と計算のモデルは違う

計算と計算のモデルについて知っている貴方には関数型と手続き型の違いをこう言うこともできるよ。つまり、関数型で記述しているのは計算だよ。手続き型で記述しているのは計算モデルの操作手順だよ。

関数型のバックグラウンドにはラムダ計算とかコンビネーターがいるって言うね。この考えでは関数型言語はあくまでラムダ計算やコンビネーターという計算モデルの操作を記述しているように見えるかもしれないね。でも思い出して欲しいんだけど、これらのモデルではモデルそのものにデータ(あるいは数)とアルゴリズムが符号化されているよ。λ式にはチャーチ数もアルゴリズムも符号化されるよね。

プログラムをデータ部分とアルゴリズム部分に分解すると、データ部分に共有の計算資源を割り当てることが容易になるよ。データ部分とはメモリや四則演算器のことだよ。したがってプログラムをデータとアルゴリズムに分解すれば外部化された計算モデル(データ)と内部化されたその操作(アルゴリズム)に分解されて、手続き型で計算することになるよ。
でもプログラムをデータ部分とアルゴリズム部分に分解しないと、それらは一体の計算資源となるよ。古く関数型と呼ばれたLISPが思い起こされるね。関数型ではとりもなおさず計算資源のあり方を記述するからプログラムをデータとアルゴリズムという名に分かれた単位には分けられないよ。関数型データ構造という言葉があるけど、あれは変だよ。関数型で表現したコードは全てがデータ構造でありアルゴリズムであり、そしてプログラムなんだよ。個人の自由で関数型言語で書かれたコード断片を外部化(外部の計算資源と化す)してその利用を記述するのは構わないよ。でもやっぱりステップを議論した時点でそれは手続き型の計算資源を再利用するところに行き着いてしまうよ。
(なおこの考え方を推し進めると計算手順を書き換えて実行できるC言語ないしアセンブラは関数型言語になってしまうよ。コード部分を書き換えない良い子はこの問題にぶち当たらないけれど)

全てはノイマンが悪い

ノイマン型コンピュータではデータとアルゴリズムが同じメモリに乗ってしまっていて、データとアルゴリズムお互いがお互いを書き換えられてしまうよ。ROMやアーキテクチャ以外には書き変わらない計算資源がないよ。むしろ書き変わる計算資源に自由がありすぎだよ。そのせいで手続き型と関数型の階層性が二重にも三重にも積み重なって難しいよ。いや、計算とは実はそういうものなんだよ。世界そのものだよ。ありがとう。

式と文と計算資源の関係は？

式っていうのはいわゆる計算資源そのものだよ。つまりa+bというのは式呼ばれるけど、それは計算資源そのもので、そこに加算器が実体として存在して、式と対応するもののことだよ。

文ていうのは計算資源の利用そのものだよ。つまり僕らは有限の計算資源である四則演算器やメモリの利用をif文やwhile文、goto文で制御するよ。このような文は計算資源をどの順で、どの繰り返しで利用するか記述するよ。

関数型言語は式が重要で文は出てこないっていうけど、それは当たり前なんだ。だって関数型では計算資源のあり方を記述するんだもん。関数型では加算、乗算、セレクタなどの計算がどういう順序でかみ合わさっているかという計算資源のあり方、つまり式ばかり書くよ。

反対に手続き型言語では文が重要に決まってるよ。だって、手続き型において、式は現実に有限な計算資源に対応していて、それの利用する順番を記述しているんだもの。ある瞬間には加算器を使ってその結果をレジスタに書き込むし、ある瞬間はメモリからデータを引っ張ってくるし、ある瞬間にはループの位置を巻き戻るよ、計算資源を再利用するために。

関数型にループは存在しない

関数型にはループは存在しないよ。ループを直線上の処理の連続に書き直すことでループが存在しないことがすぐわかるよ。

どうでもいいけど、関数型言語でもfor文はあるしループはできるという議論に反論しておくよ。つまり僕がここで言ってる関数型とは原始再起関数論で限定最小化しか許してないってことだよ。非限定最小化にあたるμ作用が入った再起関数論を根本的に扱っていないよ。無限ループが使えないとしても、それでもかなりの計算を行えることは重要だよ。全再起関数(total recursive function)はご存知の通り全ての再起関数の部分集合だよ。Totalityとは入力全てに値を返す関数のことだよ。そしてTotalであるためには、長大でも構わないけど、回路として記述できるんだよ。あるいは回路と言わずともブロック図でループ無しに書けるはずだよ。ただし間違わないで。入力値に応じてもちろん回路ないしブロック図の規模は変わりうるよ。入力1に対する関数型の計算回路と、入力10000に対する関数型の計算回路は規模が違いうるよ。そして予め十分大きな規模の回路を用意すれば、その回路で十分小さな入力に対する結果は全て計算できるよ。何度も言ってるけど関数型では計算資源のあり方そのものを記述するよ。

評価順序と遅延評価

プログラムの記述について関数型は計算資源のあり方を、手続き型は計算資源の利用を記述すると言ったね。お分かりの通りこのままでは関数型で書かれたプログラムは実行できないよ。なぜなら、書かれた計算資源を何で実装するか決まってないからね。いいんだよ74シリーズの石で実装しても。いいんだよ手計算しても。いいんだよ手続き型の計算モデルで計算しても。いいんだよ。お分かりの通り、このようなプログラムの実行に関する悩みは手続き型にはないよ。だって既に外部化された計算資源(データのあるところ)があって、その利用方法(アルゴリズム)を記述したんだから。計算資源が目の前にハードウェアとしてあるならば、そのまま手続き型の記述する指示通りプログラムを実行できるよ。

手続き型でこういう単純思考ができなくなるのはね、最適化のとき。なぜなら最適化とは記述された計算資源の利用方法を、別の利用方法に変えて計算を高速化することだから。この時には一度手続き型の計算資源の利用記述を、その意味する計算資源のあり方へ一度昇格して(あるいは関数型化して)再び手続き型での計算資源の利用に落とし込まなければいけない。

遠回りをしたよ。さて、関数型で書かれたプログラムを何らかの手続きに分解することを評価というよ。評価はね、関数型で書かれたプログラムで「入力の揃ったところから順次」実行することができるよ。これは遅延評価ではないよ。一方で「出力から遡ってどの順で計算する必要があるか」考えて計算してもいいよ。これが遅延評価だよ。

終わりに

世の中には「仕組みがわからないけど動くもの」があるよ。例えば時間だよ。例えば宇宙だよ。とりあえずそれを動かしたとき出てくるものに名前(あるいは型)をつけよう。僕は「りんご」という名前のものをここに入れてみよう。ガチャコリ。「ジュース」という名前のものが出てきたよ。こういう名前の付け方をネガティブな名前付けというよ。

ネガティブな名前っていうのはね、この世の中での「名前」の「流通」を記述するよ。だからね、ジュースは飲めるんだよ。りんごは飲めないんだよ。ヒトに流通するときはね、水っぽい液体しか喉を通らないんだよ。ネガティブな名前の付け方をするとね、世の中に氾濫する利用可能なものを全て全て名前付けていかないといけないよ。

関数型で書かれたプログラムっていうのはね、どんなネガティブな名前付けられた計算資源で実行しても構わないんだよ。CPU、GPU、FPGA、ASICなんでも構わないよ。でも手続き型はね、ネガティブなものの利用ばかり記述するよ。既に付けられた名前、例えば加算器とかね、プログラムカウンタの移動とかね、メモリvsレジスタ転送とかね、そういう中身の動き方は分からないけど、動いてしまうものの利用を書くんだよ。反対に関数型はね、計算資源のあり方を書くから、ブロックみたいに構成物を組み上げて計算はこういうものなんだっていうグラフ構造を組むよ。そのグラフ構造はもちろん結節の短絡をしたり辺を縮めることができる。これが最適化に相当するよ。逆に3+4をするのにそれにずっと+0を100回無駄にしてもいいよ。これは計算グラフにおける辺を同じ意味のまま延長してるだけだよ。

仕組みの分からないものに一度名前を付けるとね、今度こそは僕らの側でそのネガティブな名前を組み合わせて新たな言葉を作れるよ。例えばね、「りんご添えジュース、りんごの器入り」。こういうね、既存の言葉を使って「りんご添えジュース、りんごの器入り」みたいな単語のデータを組むのはポジティブな名前付けって言うよ。ネガティブな名前はその利用方法しかわからないんだ。なぜならその動く仕組みが分からないし、きっと動くということを盲信してるし、あるいは計算そのものが外在的だから。ポジティブな名前はんね、その構成方法しか分からない。だって、「添える」って君らが勝手に位置関係について名前つけてるでしょ。それただ距離空間で一定より小さい位置に置かれてるだけだよ。「入り」って君らがかってに位置関係に名前つけてるだけでしょ。それただ重力にしたがって落ち着いているだけだよ。

ポジティブな名前をつけると、「りんご添えジュース、りんごの器入り」の「りんご」の部分と「ジュース」の部分と「りんごの器」の部分に分けることができるよ。例えば、「ジュース」部分は器に口をつけて啜れば飲めるよ。造語っていうのはね、造語であるからこそその構成物を「自ずからどう機能させられるか」分かるの。「りんご」は食べられるよ。「ジュース」は飲めるよ。「りんごの器」？洗いなよ。

こう考えるとね、ネガティブな名前「りんご」、「ジュース」、「りんごの器」と、ポジティブな言葉「りんご添えジュース、りんごの器入り」は成り立ちが全然違うんだ。前者は「その利用」によって名前が付けられていてね、後者は「その構成」によって名前が付けられているんだ。ネガティブでは「その利用」が「もの」を定め、ポジティブでは「もの」が「その利用」を定める。「赤くて」、「甘くて」、「齧れる」「食べれる」それはきっと「りんご」と名付けていいよ。そういう哲学を知らない人はこれをダックタイピングなんて呼ぶけどね、ただのネガティブな名前付けのことだけど。逆に「りんご添えジュース、りんごの器入り」は、啜って齧って洗いなよ。そういう「利用方法」が「もの」から決まる。ポジティブな名前付けって言うよ。

関数型っていうのはね、ポジティブな記述なの。手続き型っていうのはネガティブな記述なの。でも、どっちも実行する時にはネガティブになっちゃうんだよ。だって関数型は評価によってネガティブ化するし、手続き型はそもそもネガティブだし。そして実行するときには必ず「有限」で「その利用」によって定まったネガティブに名前付けられた計算資源が待っているのさ。

プログラムっていうのは実行の反対だよ。プログラムっていうのは何らかの形でネガティブなものをポジティブに書いておくことを意味するんだ。だけど、この話はまた今度にするよ。今日はこのくらいにしよう。眠くなってしまったよ。じゃあ、おやすみなさい。