「関数型プログラミング」の版間の差分

関数型プログラムの基本文は[[式 (プログラミング)|式]]（''expression''）である。式は個体である値（''value''）と写像である関数（''function''）の二つから構成される。関数の定義には[[演算子]]（''operator''）も含まれている。値は後節で述べる[[データ構造|データストラクチャ]]と、[[ラムダ計算]]で言われる変数（''variable''）の双方を意味する。データストラクチャの定義には数値、論理値、文字値、文字列といった基本データ型＝[[プリミティブ型|プリミティブ]]も含まれている。変数は[[束縛変数]]と[[自由変数と束縛変数|自由変数]]を指す。評価（''evaluation''）される前の式は、ラムダ計算で言われるネーム（''name''）と同義になる。ネームは数学上の数式または代数式に相当するものである。式は、式内の変数部分が確定される前は評価できない[[ボトム型]]であり、これはラムダ抽象（''abstraction''）と同義である。式内の変数部分を確定するのはラムダ適用（''application''）と同義である。このネームが評価されると値になり、これはラムダ計算で言われる簡約（''reduction''）と同義である。式は値と同一視されるので、すなわち式と値は相互再帰の関係にある。式内の値は他の式の評価値である事があり、その式内にもまた他の値があるといった具合である。この仕組みは[[高階論理]]''と呼ばれる。''

 

 

関数は名前付きと名前無しの二通りある。名前無しの関数は専らラムダ抽象を模した構文で定義される。式内に自由変数を内包しない方は[[無名関数]]と呼ばれ、自由変数を内包する方はそれを囲い込むという意味で[[クロージャ]]と呼ばれる。自由変数は外部データへの接点になる。[[無名関数]]は引数をピュア[[写像|マッピング]]する純粋関数である。[[クロージャ]]の引数の[[写像|マッピング]]は式内の自由変数に影響され、またその自由変数に作用する事もあるという副作用要素を閉包した非純粋関数である。関数の名前は、それに結び付けられた式または式ツリーの[[不動点]]の表現になる。自式の不動点を式内に置いて新たな引数と共に[[高階論理]]の式として評価する手法は[[再帰]]と呼ばれる。関数の終端式での再帰は実引数の更新＋先端式へのアドレスジャンプと同等に見なせるのでもっぱらそちらに最適化されてこれは[[末尾再帰]]と呼ばれる。末尾再帰は論理性を損なわずにスタック資源から離れた無制限ループを可能にする実装概念として重視されている。名前付き関数で、仮引数記述を省略したものはポイントフリーと呼ばれ、その省略箇所に先行式評価値が実引数として暗黙適用される。名前無し関数で、先行式評価値を実引数にする記述を省略して、その仮引数箇所に暗黙適用するのもポイントフリーと呼ばれる。この暗黙適用の式を並べて連鎖させる手法は[[パイプライン処理|パイプライン]]と呼ばれるが、言語によっては特別な演算子と併せて明示する。リスト処理時にリストの各要素に対する作用子として渡される第一級関数は[[反復子|イテレータ]]と呼ばれる。作用後の各要素を別の新生リストに向けて複製する働きを加えたものは[[ジェネレータ (プログラミング)|ジェネレータ]]と呼ばれる。これは[[イミュータブル]]重視時に多用される。イテレータはポイントフリーの無名関数、ジェネレータはポイントフリーのクロージャとして定義される事が多い。関数名は[[関手]]の識別子と同義なので、同じ識別子に個別の引数パターン候補を付けたものを列挙することで[[選言]]の関係でつなげる事ができる。これは[[多重定義|関数のパターンマッチング]]と呼ばれる。また、変数名をその場限りの[[関手]]の識別子と見なしてパターンマッチ候補を列挙して[[選言]]の関係でつなげる方は[[パターンマッチング|パターンマッチング式]]と呼ばれる。パターンマッチングは単純照合だけでなく比較的照合や任意の要素をワイルドカードにした部分的照合でも行われる。

[[量化]]可能なパターン（型）はプロパータイプ（''proper type''）と呼ばれる。量化されたパターンはターム（型付け値）である。プリミティブではないプロパータイプは1個以上のタイプ（''type''）から形成される。型構築子はプロパータイプとタイプの依存関係を決めて同時にそのプロパータイプの識別子になる。タイプはプリミティブまたは型構築子（入れ子）を指す。タイプAとタイプBからなるプロパータイプCは、AとBに依存（''dependent''）している事になりその関係は「A→B→C」と表現される。型構築子内の任意のタイプを型変数にして[[ジェネリックプログラミング|ジェネリック化]]（=パラトメトリック多相）すると、プロパータイプ未満の存在になって量化不可になる。これを量化可能なプロパータイプ存在にするには、その型構築子への型引数の指定が別途必要になる。プロパータイプ存在とその未満存在を区別する仕組みが[[型理論]]の[[カインド (型理論)|カインド]]である。カインドではタイプを＊と総称表現する。カインドでは、プロパータイプ存在は「＊」と表現される。型引数1個必要のプロパータイプ未満存在は「＊→＊」になる。2個必要なら「＊→＊→＊」になり、これに型引数が1つ適用されると「＊→＊」になる。カインドは量化の可否の他、型構築子が設定する依存関係の要素箇所に当てはめられるかどうかの判別になる。

 

 

[[多態性]]三種の三番目であるサブタイプ多相は、データの[[セマンティクス]]または[[メソッド (計算機科学)|振る舞い]]の多相を扱う性質から関数型とは相容れない部分が多い。関数型の[[代数的データ型]]と[[オブジェクト指向プログラミング|オブジェクト指向]]の[[抽象データ型]]は対象的なデータストラクチャと見なされている。前者がデータのみの表現体であるのに対して、後者はセマンティクスを主にしたデータの表現体である。しかしオブジェクト指向との連携が模索される中で数々の手法も提示されている。動的型付けメインのLISP系ではS式の代わりに、各スロットに任意の変数を[[動的束縛|動的バインディング]]できるフレームレコードを用いる。その動的バインディング用レコードを1個以上引数にできる関数によって[[多重ディスパッチ]]が表現される。動的バインディング用レコードの型チェックは[[ダックタイピング]]で行われる。静的型付けメインのML系では、[[ジェネリックプログラミング|ジェネリック]][[クラス (コンピュータ)|クラス]]（パラメトリック多相に分類される総称的抽象データ型）の型変数の[[共変性と反変性 (計算機科学)|バリアンス]]（''variance''）を用いる。バリアンスとは型変数の派生関係を有効にして、型変数に適用できるクラスの幅を持たせることを指す。これはクラスのメンバ関数の引数と返り値をサブタイプ多相の対象にすることを明確にしている。派生関係を無効にした型変数は不変性（''invariance''）となる。型変数のバリアンスには[[共変性と反変性 (計算機科学)|共変性]]（''covariance''）と[[共変性と反変性 (計算機科学)|反変性]]（''contravariance''）がある。共変性の型変数には適用クラスとその派生クラスを当てはめることができる。それに対して反変性の型変数には適用クラスとその基底クラスを当てはめることができる。反変性の用途はやや想像しにくいが、型変数を主要メンバ変数の型注釈にしてクラスを特化し、そのメンバ変数を扱うメンバ関数の方は汎化させる事などに使われる。また、関数の写像において基底クラスの引数→派生クラスの返り値は共変性、派生クラスの引数→基底クラスの返り値は反変性となる。バリアンスは境界的定量化（''bounded quantification''）の手法でも行われる。これは型引数または型変数を、共変ないし反変の基準とする注釈クラスで記号修飾するものである。共変である上限境界は、クラスのコンストラクタ（総称的抽象データ型の型構築子）の型引数を注釈クラスの派生クラスの適用に限定できる。反変である下限境界は、クラス内の型変数を注釈クラスの基底クラス範囲に差し戻せる。