「CやJavaで関数型(3)」関数型プログラミング事始め (48) 増補版(4)

関数型プログラミングがはじめての方へ贈る入門の書
前節：CやJavaで関数型(2)　次節：未定
参考書：
・五味 弘「はじめてのLisp関数型プログラミング」技術評論社(2016)
・大山口 通夫、五味 弘「プログラミング言語論」コロナ社(2008)
・五味 弘「関数型プログラミングと数学(ITと数学)」技術評論社(2021)

「CやJavaなどの普段使いの言語で関数型プログラミングに挑戦」の3回目の記事になります。今回は関数をファーストクラスにする方法を見ていきます。このようにCやJavaでは関数型の仕掛けを自作する必要があり、多少（？）の苦労が必要です。でも関数型のご利益が得られますので、楽をするためにはどんな苦労もしてください。

2.6 関数をファーストクラスに

関数型プログラミングでは、関数を整数などの普通のデータと同じように、ファーストクラスのデータとして扱います。つまり関数は他の関数の引数やその値にすることも可能で、また配列の要素としても関数を扱えます。

(1) 関数型言語にはラムダ式

関数型言語では、関数も普通のデータ型として扱える機能があります。例えばラムダ式(*)のような機能を持っている言語もあります。便利です。

このラムダ式はJavaなどの他の言語でも最近、採用されました。匿名関数を実装する手段として利用されている場合が多いですが、このように非関数型の言語でも関数型プログラミングの萌芽が出てきています。まさに関数型プログラミングの有用性は広く認識されてきています。

ここではJavaはラムダ式がありますので、例としてはCに絞って見ていくことにします。

(*) ラムダ式
コンピュータの計算モデルとして、ラムダ計算 (λ(lambda) calculus)があります。ラムダ計算はα変換(α-conversion、名前変換)とβ簡約(β-reduction、関数適用)、η変換(η-conversion、関数の等価/外延性)の規則からなります。このラムダ計算の表記にラムダ式(lambda expression)があります。

このラムダ計算は関数型プログラミングの計算モデルであるとともに、すべてのプログラミング言語の関数適用の基礎にもなっています。

ラムダ式については以下の記事を参考にしてください。
関数型プログラミング事始め (34) ラムダ計算(1)
関数型プログラミング事始め (35) ラムダ計算(2)

(2) 関数をファーストクラスにする方法

ラムダ式がない言語で、関数を普通のデータ（ファーストクラスのデータ）にする方法を見ていきます。

(a) ジャンプテーブル
一番、簡単な（手抜きな）方法としては、関数にラベル(整数で可)を付け、ラベルによって関数呼び出しを行う方法があります。よくジャーゴンとして言われるジャンプテーブルがこの方法による実装例です。

この実装のメリットとしては手抜き、いえ、簡単に実装できることですが、デメリットとしては間接呼び出しになり効率が悪いことになります。

(b) 関数ポインタ
Cなどのように関数ポインタが実装されている言語では、これが使えます。これは原始的な実装なので、なんでも自分でできます。なんでも自分でしなければいけません。関数をファーストクラスにするための始まりになります。

この実装のメリットは原始的なので効率がよく何でもできることで、デメリットはすべての面倒を見なくてはいけないことです。

2.7 関数をファーストクラスにする例(関数ポインタ)

ここではCの関数ポインタによる関数のファーストクラスの実装を見ていきます。

例として引数に関数を与えて、その関数を実行する関数funcallをCで作ってみます。

ただし（面倒なので）funcallの引数に与える関数は、その引数のタイプや個数、値を限定している実装にしています。

int funcall(int (*fun)(int, int), int x, int y){
  return (*fun)(x, y);
}

このように簡単に実装できます。
次にこのfuncallを使う例を見ていきます。

引数に与えるサンプルの関数
　int add(int x, int y){ return x + y; }
　int mul(int x, int y){ return x * y; }

なおここではサンプルを簡単にするために関数に名前を付けていますが、関数のアドレスだけ（匿名）でも可能です。

funcallの使用例
　int answer = funcall(&add, 3, 4) ;
　int answer = funcall(&mul, 3, 4) ;

2.8 再帰呼び出し

関数型プログラミングには再帰呼び出しができる必要があります。関数プログラミングの計算モデルのひとつである原始再帰関数(primitive recursive function)を実装するために必要になります。

なお再帰プログラミングについては以下を参考にしてください（ただし例はLispです）
関数型プログラミング事始め (25) 再帰プログラミング(1)

この再帰呼び出しについては、CでもJavaでも実装されていますので、そのまま関数型プログラミングでの再帰プログラミングができます。再帰を楽しんでください。

初期のFORTRANなどのように、再帰呼び出しを実装していない言語では再帰呼び出しを手動で実装する必要があります。

再帰呼び出しを実装する手段としては、配列とスタックポインタを使ったスタックを用いる方法が多くなっています。リストなどでも実装できますがこの再帰呼び出し用のスタックを使った実装が効率的に優れています。

スタックによる再帰呼び出しの実装は、
(1) 関数呼び出しをするときに引数の情報をスタックにプッシュし
(2) 呼び出し元のリターンアドレスをスタックにプッシュし
(3) 呼び出し先の関数で引数とリターンアドレスの情報を受け取り
(4) 呼び出し先の関数を実行し
(5) 実行した結果の値の情報をスタックにプッシュし
(6) リターンアドレスに制御を移す
のように実行します。

なお(1)のときに引数を左側からただちに実行すれば、正格評価（内側優先、左側優先）になりますが、正格評価するかどうかはプログラマの意図により変更できるのが関数型プログラミングの醍醐味です。

2.9 まとめ

普段使いのプログラミング言語で、関数型プログラミングをする方法として、副作用なし（参照透過性）と関数のファーストクラス、再帰呼び出しの3点の仕掛けについて見てきました。

この３点の仕掛けができれば、遅延評価や無限リスト、モナドなどの実装も可能になります。

元々、関数型言語もノイマン型コンピュータで実装されていますから、プログラムを格納できる配列があれば、関数型プログラミングが可能です。しかし、上記の３点の仕掛けが言語処理系で実装されていないと、それを手動で作るのは面倒です。この面倒をなくしているのが関数型言語のいいところです。

しかしそのような仕掛けがなくても、３点の仕掛け全部ではなく、必要な仕掛けだけ必要な範囲で作るのは簡単です。例えば副作用の範囲を限定するだけでも関数型プログラミングの恩恵を受けることができます。

ということで今日辺りの結論「関数型プログラミングは部分的でも可」以上です。