コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
削除された内容 追加された内容
m "Template:" を含むテンプレート呼び出し
(同じ利用者による、間の42版が非表示)
3行目: 3行目:
{{プログラミング・パラダイム}}
{{プログラミング・パラダイム}}


'''関数型言語'''({{lang-en-short|''functional language''}})は、'''関数型プログラミング'''のスタイルまたは[[プログラミングパラダイム|パラダイム]]を扱う[[プログラミング言語]]の総称である。関数型プログラミングは関数の[[写像|適用]]ベースにした[[宣言型プログラミング]]の一形態であり、関数は[[引数]]の適用から先行式の評価を後続式の適用につなげて終端の[[評価戦略|評価]]を導き出す[[式 (プログラミング)|式]]の[[ツリー構造]]として定義される。式の評価に伴う[[副作用 (プログラム)|副作用]]の発生には大きな注意が払われる。関数は引数ないし返り値として渡せる[[第一級オブジェクト]]として扱われる。
'''関数型言語'''({{lang-en-short|''functional language''}})は、'''関数型プログラミング'''のスタイルまたは[[プログラミングパラダイム|パラダイム]]を扱う[[プログラミング言語]]の総称である。関数型プログラミングは関数定義と関数適用を基礎にした[[宣言型プログラミング]]の一形態であり、関数は[[引数]]の適用から先行式の評価を後続式の適用につなげて終端の[[評価戦略|評価]]を導き出す[[式 (プログラミング)|式]]の[[ツリー構造]]として定義される。式の評価に伴う[[副作用 (プログラム)|副作用]]の発生には大きな注意が払われる。関数は引数ないし返り値として渡せる[[第一級オブジェクト]]として扱われる。


関数型プログラミングは[[数理論理学]]と代数系をルーツにし、[[ラムダ計算]]と[[コンビネータ論理]]を幹にして構築され、[[LISP]]言語が実装面の先駆になっている。関数の数学的な純粋性を指向したものは純粋関数型言語と個別に定義されている。[[命令型プログラミング]]言語([[手続き型プログラミング|手続き型]]や[[オブジェクト指向プログラミング|オブジェクト指向]]を指す)では単に有用な構文スタイルとして扱われている事が多い。[[高階関数]]、[[第一級関数]]、{{仮ンク|関数合成|en|Function composition (computer science)|label=}}、{{仮リンク|部分適用|en|Partial application|label=}}、[[クロージャ]]、[[継続]]、{{仮リンク|ポイントフリー|en|Tacit programming|label=}}、[[イテレータ]]、[[ジェネレータ (プログラミング)|ジェネレータ]]、[[評価戦略|名前渡し]]、[[遅延評価]]、[[Cons (Lisp)|コンス]]、[[代数的データ型]]、[[型推論]]、[[パタンマッチング]]、{{仮リンク|パラメトリック多相|en|Parametric polymorphism|label=}}、[[イミュータブル]]、[[再帰]]、[[モナド (プログラミング)|モナド]]などが{{誰範囲|date=2020年5月|関数型プログラミングのスタイル要素として挙げられる}}。
関数型プログラミングは[[数理論理学]]と代数系をルーツにし、[[ラムダ計算]]と[[コンビネータ論理]]を幹にして構築され、[[LISP]]言語が実装面の先駆になっている。関数の数学的な純粋性を指向したものは純粋関数型言語と個別に定義されている。[[命令型プログラミング]]言語では単に有用な構文スタイルとして扱われている事が多い。[[高階関数]]、[[第一級関数]]、[[カー化]]、[[クロージャ]]、[[継続]]、[[イテレータ]]、[[ジェネレータ (プログラミング)|ジェネレータ]]、[[再帰]]、[[型推論]]、[[パターンマッチング]]、[[評価戦略|名前渡し]]、[[遅延評価]]、[[Cons (Lisp)|コンス]]、[[代数的データ型]]、[[ポリモフィズム|型の多相]]、[[イミュータブル]]、[[モナド (プログラミング)|モナド]]などが{{誰範囲|date=2020年5月|関数型プログラミングの様式項目として挙げられる}}。

== 一般的な関数型スタイル ==
最も身近な関数型プログラミングとは、データ集合に対する反復作用であり、リスト処理などと呼ばれているものである。手続き型言語やオブジェクト指向言語において、いわゆる関数型と呼ばれる構文が多用されるのもリスト処理の分野である。関数型思想の原点は「[[LISP]]」であるが、その実用性を知らしめた最初の言語は[[表計算ソフト|表計算]]処理に効率性を発揮した「[[APL]]」であった。リストを走査して各要素を順々に取り出すプロセスと、各要素に作用するプロセスを別々の関数にまとめて、前者に後者を渡すようにした仕組みが一般に言われる関数型の基本例である。他の関数を引数として受け取る事ができる関数は'''[[高階関数]]'''と呼ばれ、引数として渡す事ができる関数は'''[[第一級関数]]'''と呼ばれる。この二つの機能が関数型の支柱である。そのようなスタイルとしての意味での関数型プログラミングにおける代表的な機能または構文には以下のようなものが挙げられる。

'''ラムダ式''' / '''[[無名関数]]''' / '''[[クロージャ]]'''
: ラムダ式と無名関数は同じものである。無名関数は<code>引数→式</code>(例:<code>x→x+1</code>)の形式で表現され、与えられた引数を加工して結果値を返す働きをする。高階関数への引数として使われることが多い。無名関数の式内に外部データを含んだものはクロージャと呼ばれる。クロージャの結果値はその時の外部データの状態に左右される事になる。

'''map''' / '''filter''' / '''reduce'''
: リスト処理用の高階関数であり、対象リストと無名関数を引数にする。mapはリスト内の各要素を無名関数の結果値に置き換える高階関数である。filterはリスト内の各要素を無名関数の真偽判定値で真なら抽出し、その抽出要素のリストを生成する高階関数である。reduceはリスト内の各要素の総和の結果値を生成する高階関数である。reduceの無名関数は前要素までの総和と現要素の二引数を取る。総和の和は和に限らず無名関数内で好きな計算にできる。

'''名前渡し''' / '''[[遅延評価]]'''
: 引数を当てはめた無名関数(コードブロックまたはプロセス)を未計算のまま高階関数に渡せる仕組みを名前渡しという。予め組み立てた想定プロセスを全て高階関数に渡しておき、その高階関数側で必要になったプロセス結果値だけを求めるようにして計算量を減らすのが主な用途になる。引数確定時とは別タイミングで計算することを遅延評価という。遅延評価では高階関数側で無名関数の確定引数を設定し直したり、[[クロージャ]]ならばその時の計算タイミングの外部データ状態に従った結果値を得ることが可能になる。

'''[[型推論]]'''
: [[命令型プログラミング|命令型プログラミング言語]]での型推論は、ローカル変数の型宣言/型注釈を省略することで表現に幅を持たせるための[[糖衣構文]]に近い機能と考えてよい。[[テンプレート (プログラミング)|型テンプレート]]的な表現の幅である。[[プリミティブ型|リテラル]](数値/実数/文字列)および文脈上で型が明確な[[インスタンス]]の初期代入は、同時に対象変数の型注釈になると再考されたことに基づいている。従来の{{仮リンク|明示的型付け|en|Manifest typing|label=}}(型宣言/型注釈の使用)と[[型推論]]の共存は、C言語世代プログラミングに対する一つのパラダイムシフトでもある。


== 特徴 ==
== 特徴 ==
{{出典の明記| date = 2020年5月6日 (水) 02:29 (UTC)| section = 1}}
{{出典の明記| date = 2020年5月6日 (水) 02:29 (UTC)| section = 1}}
ここでは関数型プログラミング本来の構文スタルを元て説明する。式を基本文にする関数型に対して、[[文 (プログラミング)|ステートメント]]を基本文にする[[命令型プログラミング]]言語必要応じて構文スタルを変えて実装さてい。代表的なのは「式引数を適用する」に対する「関数引数を渡す」である。値その型付けに対するコンセプトおよびデータストラクチャの実装スタイルも異なっている。
ここでは関数型プログラミング本来の考え方([[プログラミングパラダム|パラダイム]])基づいて説明する。[[文 (プログラミング)|ステートメント]]を基本文にする[[命令型プログラミング|命令型言語]]と、[[式 (プログラミング)|式]]を基本文にする関数型言語はどちらも最終的は[[命令型プログラミング|命令型パラダム]]に沿った[[機械コード]]に落とし込まれる事にるが、双方はプログラミングに対する考え方比較的大きな隔たりがあると言える。


=== 式と関数 ===
=== 式と関数 ===
関数型プログラムの基本文は[[式 (プログラミング)|式]](''expression'')である。式は個体である値(''value'')と写像である関数(''function'')の二つから構成される。関数の定義には[[演算子]](''operator'')も含まれている。値は[[基本データ型]](プリミティブ)と{{仮リンク|複合データ型(コンポジット)|en|Composite data type|label=}}および[[ラムダ計算]]で言われる変数(''variable'')を意味する。変数は[[束縛変数]]と[[自由変数と束縛変数|自由変数]]を指す。評価(''evaluation'')される前の式は、ラムダ計算で言われるネーム(''name'')と同義になる。ネームは数学上の数式または代数式に相当するものである。式は、式内の変数部分が確定される前は評価できない[[ボトム型]]であり、これはラムダ抽象(''abstraction'')と同義である。式内の変数部分を確定するのはラムダ適用(''application'')と同義である。このネームが評価されると値になり、これはラムダ計算で言われる簡約(''reduction'')と同義である。式は値と同一視されるのですなわち式と値は相互再帰の関係にある。式内の値は他の式の評価値である事があり、その式内にもまた他の値があるといった具合である。この仕組みは[[高階論理]]''と呼ばれる。''
関数型プログラムの基本文は[[式 (プログラミング)|式]](''expression'')である。式は個体(''individual'')である値(''value'')と写像(''mapping'')である関数(''function'')の二つから構成される。関数の定義には[[演算子]](''operator'')も含まれている。値は[[基本データ型]](プリミティブ)と{{仮リンク|複合データ型(コンポジット)|en|Composite data type|label=}}および[[ラムダ計算]]で言われる変数(''variable'')を意味する。変数は[[束縛変数]]と[[自由変数と束縛変数|自由変数]]を指す。評価(''evaluation'')される前の式は、ラムダ計算で言われるネーム(''name'')と同義になる。ネームは数学上の数式または代数式に相当するものである。式内の変数部分が確定される前の式はラムダ抽象(''abstraction'')と同義になる。式内の変数部分を確定するのはラムダ適用(''application'')と同義になる。この式=ネームが評価されると値になり、これはラムダ計算で言われる簡約(''reduction'')と同義になる。式は値と同一視されるのですなわち式と値は相互再帰の関係にある。式内の値は他の式の評価値である事があり、その式内にもまた他の値があるといった具合である。この解釈は[[高階論理|高階述語論理]]''と呼ばれる。高階述語論理=[[高階関数]]の解釈下で引数または返り値として扱われる関数は[[第一級関数]]と呼ばれる。''

関数型プログラミングの関数は’’関数の型’’(''function type'')で分類される[[存在量化子|存在量]]の値である。プログラム的には式に引数を結び付ける機能であり、これは関数を引数に[[写像|適用]]する(''applying a function to an argument'')とされる。関数の式内の仮引数(''parameter'')箇所に渡された実引数(''argument'')が[[パターンマッチング]]手法で当てはめられ、先行(その時)または遅延(その後)タイミングで評価されて結果値が導出される。この仮引数箇所は束縛変数と呼ばれる。関数呼び出し時とは異なるタイミングで内容が決定される変数箇所は自由変数と呼ばれる。letとwhereで特定の式に向けて定義される変数は、その式への束縛変数になる。関数型での自由変数の意味合いは他の[[宣言型プログラミング|宣言型パラダイム]]とは異なっている。パターンマッチング手法は、関数にそれぞれ異なる引数パターン候補の[[選言]]列挙を可能にさせておりこれは[[多重定義|関数オーバーロード]]と同義の機能になる。[[パターンマッチング]]は非交和型による等価性(''equivalent'')区別と、それ以外の等値性(''equality'')区別では引数値の組み合わせ照合とそれにワイルドカードを用いた部分的総称化照合で行われ、更にそれに[[ガード (プログラミング)|ガード]]と呼ばれる値の比較照合と範囲照合を加えることもできる。渡される実引数によっては[[ボトム型]]になる関数もありこれは部分関数(''partial function'')と呼ばれる。ボトム型は式ないし関数の評価の失敗した終着点を意味する。演算子はデフォルトの式内容を持ち、その引数が単項演算子なら1個、二項演算子なら2個に限定された関数と同義である。


’’関数の型’’は「第1引数の型→第x引数の型→評価値の型」というように形式化されておりこれはカリー化(''currying'')と呼ばれる。例として関数funcの型を<code>func::A→B→C</code>とするとこの場合、A型値に適用されたfuncは<code>B→C</code>という’’関数の型の値’’を返す事になり、それをB型値に適用するとC型の評価値が返る事になる。左からの引数にひとつひとつ適用する形にして、<code>B→C</code>のような中間的な’’関数の型の値’’が導出されるようにする仕組みが関数の[[カリー化]]である。カリー化は写像の[[量化]](''quantify'')を扱う[[二階述語論理]]の実装である。カリー化によって関数funcの型は<code>func::A→(B→C)</code>と読み替えられるようになり、この場合にAにのみ適用して<code>B→C</code>という’’関数の型の値’’のまま保留することは部分適用(''partial application'')と呼ばれる。またカリー化による重要概念に関数合成(''function composition'')がある。これは合成演算子<code>.</code>(専用の二項演算子)を関数<code>f::B→C</code>に適用すると<code>(*→B)→(*→C)</code>が導出され、それを関数<code>g::A→B</code>に適用すると<code>(A→B)→(A→C)</code>となり関数<code>f . g::A→C</code>が導出されるというものである。合成演算子の左側の[[定義域]]と右側の[[値域]]が同じ型の場合のみ合成できる。高階関数的な連結である<code>f (g A)</code>と働きかた的には同じであるが、[[パイプライン処理]]の方に該当する関数連結(関数チェーン)と、カリー化に則った関数合成は異なる概念である。カリー化による部分適用や合成演算子から導出された’’関数の型の値’’を任意の変数に束縛して扱うのはポイントフリースタイル(''point-free style'')と呼ばれる。ポイントフリースタイルの変数を値に適用すると、他の値が返されるか又は他の’’関数の型の値’’が返される事になる。引数を部分適用された演算子はセクションと呼ばれてポイントフリースタイルでよく用いられる。[[カリー化]]準拠の’’関数の型’’は[[型理論]]の指数型(''quotient type'')に分類されるものである。
関数も値と同一視される。関数は写像の型の値であるが、プログラム的には式に引数を結び付ける機能であり、これは式に引数を[[写像|適用]](''application'')すると呼ばれる。式内の仮引数(''parameter'')箇所に実引数(''argument'')が順次当てはめられ、式ツリーの終端式が評価値になる。仮引数箇所は束縛変数と同義になる。引数によっては[[ボトム型]]になる関数もありこれは部分関数と呼ばれる。ボトム型は虚(''falsity'')と見なされており、式の評価および個体の写像の失敗した終着点になる。関数は、式に第1引数を適用したもの→第x引数を適用したもの→評価値、という形をとる。引数を1個ずつ適用する形態は[[カリー化]]と呼ばれる。2個以上の引数を同時適用する形態は非カリー化と呼ばれる。関数の型(''function type'')は「A→B→C」のように各引数値から評価値までの写像のつながりとして表現される。片方の評価値と片方の第1引数が同じ型の両関数は任意に連結して新たな関数にできる。この双方の写像のつなぎ合わせは関数合成と呼ばれる。カリー化された関数は引数の適用を途中で止めて残り引数を後から適用するように保留できる。この保留状態の関数の生成は部分適用と呼ばれる。任意のタイミングで遅延評価(''call/cc'')するために評価を保留している関数は[[継続]]と呼ばれる。その応用に一つの式を個々の演算子適用(関数適用)に分解して[[継続]]チェーン化する[[継続渡しスタイル]]がある。部分適用と継続はネームと同義である。関数も当然ながら[[高階論理]]に組み込まれている。引数値または評価値として扱うことができる関数は[[第一級関数]]と呼ばれる。その第一級関数を扱うことができる関数は[[高階関数]]と呼ばれる。


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


=== 値とデータストラクチャ ===
=== 値とデータストラクチャ ===
関数型プログラミングの値(''value'')は[[基本データ型]](プリミティブ)と{{仮リンク|複合データ型(コンポジット)|en|Composite data type|label=}}のいずれかで表現される。プリミティブは数値、論理値、文字値、文字列を指す。様々なプリミティブを様々な形式で組み合わせたものがコンポジットであり、その例はC言語の[[構造体]]や[[共用体]]などである。その組み合わせ方に焦点を当てた用語が[[データ構造|データストラクチャ]](''data structure'')である。データストラクチャという概念には入れ子構造、再帰構造、木構造、ハッ構造、グラフ構造、注釈構造、操作的意味構造といった様々な暗黙情報を含められるので、コンポジットの具体的形式といった意味で用いられる。関数型言語で用いられるデータストラクチャの代表は[[代数的データ型]]と[[S式]]である。双方とも構築子(''type constructor'')から構築される。まず、プリミティブが構築子によってまとめられる。正確ではないが構築子はC言語の構造体または共用体と同じものと見てよい。構築子は入れ子にできるので、構築子をまとめた構築子定義できる。自分自身(型構築子を入れ子にした再帰構造も定義できる。プリミティブと構築子を任意に組み合わせて代数的データ型やS式といったデータストラクチャが構築される。データストラクチャ内のプリミティブと構築子の組み合わせ方はパターン(''pattern'')と呼ばれる。パターンには[[アノテーション]]要素や[[ガード (プログラミング)|ガード]]要素が加えられることもある。そのパターンが型になり、パターンの構築が型付けになり、パターンを[[量化]](''quantify'')すると型付け値になり、これはターム(''term'')と呼ばれる。タームは冒頭の値(''value'')を指す。構築子のパターンの末端は必ずプリミティブになるので、パターン内の全てのプリミティブの値を決定することが量化になる。特定文脈が求めるパターンマッチするタームは等価(''equivalent'')とされる。この等価は同じ型と読み替えてもよい。等価性はあらゆる計算の可否(計算可能性)を決定する。計算とは関数適用または演算子適用を指し、それらが求める仮引数と実引数にするタームが等価であればその計算は成立する事になる。データストラクチャのパターンは基礎パターンに分解されて解釈される。基礎パターンは[[型理論]]に従って直積型、非交和型、帰納型、ユニット型、ユニオン型、オプション型、詳細型、交差型などに分類されている。
関数型プログラミングの値(''value'')は型(''type'')で分類される[[定数 (プログラミング)|定数]]または[[全称量化子|全称量]]の[[変数 (プログラミング)|変数]]である。これは[[基本データ型]](プリミティブ)と{{仮リンク|複合データ型(コンポジット)|en|Composite data type|label=}}のいずれかで表現される。プリミティブは数値、論理値、文字値、文字列を指す。様々なプリミティブを様々な形式で組み合わせたものがコンポジットであり、その例はC言語の[[構造体]]や[[共用体]]などである。その組み合わせ方に焦点を当てた用語が[[データ構造|データストラクチャ]](''data structure'')である。データストラクチャという概念には[[再帰]]構造、[[アノテーョン]]付き構造、[[ガード (プログラミング)|ガード]]付き構造、[[操作的意味論|操作的意味]]付き構造といった様々な暗黙情報を含められるので、コンポジットの具体的形式といった意味で用いられる。関数型言語で用いられるデータストラクチャの代表は[[代数的データ型]]と[[S式]]である。双方ともデータ構築子(''data constructor'')から構築される。まず、プリミティブがデータ構築子によってまとめられる。正確ではないがデータ構築子はC言語の構造体または共用体と同じものと見てよい。データ構築子は入れ子にできるので、データ構築子をまとめたデータ構築子定義できる他、同名データ構築子を入れ子にした再帰構造も定義できる。プリミティブとデータ構築子を任意に組み合わせて代数的データ型やS式といったデータストラクチャが構築される。データストラクチャ内のプリミティブとデータ構築子の組み合わせ方はパターン(''pattern'')と呼ばれる。そのパターンが型になり、パターンの構築が型付けになり、パターンを[[量化]](''quantify'')すると型付け値になり、これはターム(''term'')と呼ばれる。タームは冒頭の値(''value'')を指す。データ構築子のパターンの末端は必ずプリミティブになるので、パターン内の全てのプリミティブの値を決定することが量化になる。お互いのパターンマッチするターム同士は等価(''equivalent'')とされる。この等価は同じ型と読み替えてもよい。等価性はあらゆる計算の可否(計算可能性)を決定する。計算とは関数適用または演算子適用を指し、それらが求める仮引数と実引数にするタームが等価であればその計算は成立する事になる。データストラクチャのパターンは基礎パターンに分解されて解釈される。基礎パターンは[[型理論]]に従って直積型、非交和型、ユニオン型、オプション型、帰納型、ユニット型などに分類されている。


[[S式]]は[[二分木|二分木構造]]のデータストラクチャである。これはコンス(''cons'')と呼ばれる二項の構築子の連結で形成される。コンスは二つの要素を持つものであり、要素はプリミティブまたは他のコンスのどちらかである。S式はコンスを実行時に連結して任意のパターンを構築する[[動的型付け]]の値である。コンスの連結による要素の並びは[[直積集合|直積型]](''product type'')となる。直積型は[[タプル]]のパターンを表わすが三要素以上の並びはコンスの連結にるの[[線形リスト|リスト]]と呼ばれる。コンスの要素はあらゆるプリミティブと入れ子コンスにできるので形式化されていない[[非交和|非交和型]](''sum type'')でもある。ただしそ別は完全にプログラマ側の裁量に委ねられている。
[[S式]]は[[二分木|二分木構造]]のデータストラクチャである。これはコンス(''cons'')と呼ばれる二項のデータ構築子の連結で形成される。コンスは二つの要素を持つ[[タプル]]であり、要素はプリミティブまたは他のコンスのどちらかである。S式はコンスを実行時に連結して任意のパターンを構築する[[動的型付け]]の値である。コンス要素二つの[[直積集合|直積型]](''product type'')であり、コンスの連結に要素並びは[[線形リスト|リスト]]と呼ばれる。コンスの要素は形式化されていない[[非交和|非交和型]](''sum type'')でもあり、要素別はプログラマ側の裁量に委ねられている。コンスの組み合わせによるパターンは任意の識別名に結び付けられる。


[[代数的データ型]]は{{仮リンク|AND-OR木構造|en|And–or tree|label=}}のデータストラクチャである。これは[[直積集合|直積型]]または[[非交和|非交和型]]を表現する多項の構築子の組み合わせで形成される。構築子は任意個数の要素を持つものであり、要素はプリミティブまたは他の構築子のどちらかである。代数的データ型は構築子を事前に組成定義して任意のパターンを構築する[[静的型付け]]の値である。直積型は[[タプル]]または[[構造体|レコード]]のパターンを表わす。非交和型は[[列挙型]]または[[共用体|タグ共用体]]のパターンを表わす。前者は等値性(''equality'')で識別される一般的な非交和である。後者は等価性(''equivalent'')で識別される非交和であるが、ユニオン型(''union type'')と個別定義されている。自分自身の型構築子のネスティングは型理論の帰納型(''inductive type'')とされる。非交和型と帰納型とユニット型の組み合わせは[[連結リスト]]や[[二分木]]のパターンを表わす。ユニット型(''unit type'')はnilないしvoidであり空集合のパターンを表わ。ユニット型とそうでない型の二択の非交和型はオプション型(''option type'')とされMaybe値のパターンをわす代数的データ[[述語論理]]の関数記号で包含(''comprehension'')したパターンは詳細型(''refinement type'')とされる。これ「ターム集合→[[ガード (プログラミング)|ガード]]→抽出タームリスト」の[[リスト内包表記]]である。パターンに[[アノテーション]]加えてそれが表わす任意意味づけ性との[[論理積]]で新たな等価性を表現す交差型(''intersection type'')とさ[[型クラス]]を表わす。こはアドホック多相相当する。パターン内のプリミティブと型構築子は型変数(''type variable'')に置き換えることで[[ジェネリックプログラミング|ジェネリック化]]でき、型引数(''type parameter'')の定でスペシフィック化できる。れはパラメトリック多相相当する。代数的データ型は義と実装を分後者隠蔽するという意味でしばしば抽象化される。これは識別名を重複させる仕組みで実現され、型シノニムまたは型エイリアスと呼ばれる。
[[代数的データ型]]は{{仮リンク|AND-OR木構造|en|And–or tree|label=}}のデータストラクチャである。これは[[直積集合|直積型]](''product type'')または[[非交和|非交和型]](''sum type'')を表現する多項のデータ構築子の組み合わせで形成される。データ構築子は任意個数の要素を持つものであり、要素はプリミティブまたは他のデータ構築子のどちらかである。代数的データ型はデータ構築子を事前に組成定義して任意のパターンを構築する[[静的型付け]]の値である。直積型は[[タプル]]または[[構造体|レコード]]のパターンを表わす。レコードは指定フィールド取得用関数を随伴させたものである。非交和型は[[列挙型]]または[[共用体|タグ共用体]]のパターンを表わす。前者は等値性(''equality'')で識別される非交和である。後者は等価性(''equivalent'')で識別される非交和であこちらはユニオン型(''union type'')とも呼ばれる。ユニット型(''unit type'')は空集合のパターンを表わし、実装面ではnilまたはvoidの表現になる。ユニット型とそうでない型の二択の非交和型はオプション型(''option type'')とされ、実装面ではMaybe値の表現になる。データ構築子再帰的にネスティングするパターンは帰納型(''inductive type'')とされる。非交和型と帰納型とユニット型の組み合わせは[[連結リスト]]や[[二分木]]パターンを表わす。データ構築子組み合わせによパターン任意の構築子(''type constructor'')に結び付けらて同時にそが識別名義る。データ構築子がパターンの表現に用いられるのに対して、型構築子はパターン内の要素(プリミティブないしデータ構築子)の多相化に用いられる。多相化パターン内の要素を型変数(''type variable'')に置き換え、型構築子への型引数(''type parameter'')で要素型を決するという形行われる。型構築子が必要とする型引数の個数および形態によるパターンは[[カインド (型理論)|カインド]](''kind'')と呼ばる。型構築子カインドよって分類される。代数的データ型は識別名義と構成内容を分離し双方自由に組み合わせるという意味でしばしば抽象化される。これは型構築子名に他の型構築子名を結び付ける仕組みで実現され、型シノニムまたは型エイリアスと呼ばれる。


=== 評価戦略 ===
=== 評価戦略 ===
関数型プログラミングの[[評価戦略]](''evaluation strategy'')は、ネーム存在を値存在にする評価タイミング、引数の渡し方のcall-by-What、関数のボトム型の発生タイミングのつを定義している。これまず正格評価(''strict evaluation'')と非正格評価(''non-strict evaluation'')の二つに大別される。正格評価のネーム存在は、関数適用と同時に評価されて値存在になり、またによる束縛と同時に評価されて値存在になる。この評価タイミングに注目した方は[[先行評価]](''eager evaluation'')と呼ばれる。引数のどれか一つがボトム型の値存在にな数は反駁(''refutable'')されてそのままボトム型になの意味も包括した呼称が正格評価である。正格評価=先行評価のcall-by-Whatは値渡しになる関数型プグラミングの性格から参照渡しと共有渡(ポインタ渡し)は用いられない。
関数型プログラミングの[[評価戦略]](''evaluation strategy'')は、関数を値にする評価タイミング、引数欄内関数の評価タイミング(''call-by-What'')つを定義している。関数を値にする評価タイミング正格評価(''strict evaluation'')と非正格評価(''non-strict evaluation'')の二つに大別されている。正格評価の関数は確定と同時に評価されて値になる。この評価タイミングに注目した方は[[先行評価]](''eager evaluation'')と呼ばれる。引数確定と同時に[[ボトム型]](評価失敗)が発生することも包括した呼称が正格評価である。非正格評価関数は、引数確定されても未評価のまま保留状態にされる。後続式で改めて他の関数/演算子の引数にされた時に初めて評価されて値になり、まは改めて変に束縛された時に初めて評価されて値になる。この評価タイミングに注目した方[[遅延評価]](''lazy evaluation'')と呼ばれる。評価されボトム型の発生が保留されるこも包括した呼称が正格評価である。これが遅延評価のデフォルトタイミングであるが、好きタイミングで遅延評価でき無名関数/クージャもあり、それは[[継続]](''continuation'')と呼ばれる。その任意タイミングの評価値導出はcall/cc(現行継続呼出)と呼ばれる。遅延評価は必要以外の評価をスキップて処理を高速化するが、評価値未評価関数の区別が難るとうジレンマがある


引数欄内関数の評価タイミング(''call-by-What'')には、値渡し(''call by value'')と名前渡し(''call by name'')がある。値渡しは先行評価に相当するものであり、関数の評価値が引数として渡される。名前渡しは遅延評価に相当するものであり、未評価のまま保留された関数が引数として渡される。なお、双方ともに引数確定されていない場合はただの第一級関数(関数の型の値)として渡されることになる。また名前渡しの亜流に必要渡し(''call by need'')があり、これは一度名前渡しされた関数+引数はその評価値を[[メモ化]]されて、同じ関数+引数が再度名前渡しされた時はそのメモ化評価値の方を渡すという仕組みである。必要渡しは純粋関数型言語で実装されている。
非正格評価の評価タイミングに注目した方は[[遅延評価]](''lazy evaluation'')と呼ばれる。非正格評価=遅延評価のcall-by-Whatは名前渡し(ネーム渡し)または必要渡し(メモ化渡し)が用いられる。名前渡しによる遅延評価のネーム存在は、関数に適用されてもネーム存在のままであり、または変数に束縛されてもネーム存在のままである。後続式において改めて他の関数ないし演算子に適用される時に初めて評価されて値存在になり、または改めて他の変数に束縛される時に初めて評価されて値存在になる。これは数理的には束縛項が他の項に束縛された時は必ず簡約化されるという規則に準じている。評価の遅延により、ボトム型になる引数があってもそれが確定するまでは関数が反駁されないという意味も包括した呼称が非正格評価である。これが遅延評価のデフォルトタイミングであるが、[[継続]]コール(''call/cc'')手法や不可反駁(''irrefutable'')指定によって更に評価を遅延させる事もできる。継続コールは任意の第一級関数またはクロージャを任意のタイミングで評価して値を導出できる機能である。これは値の導出後もネーム存在のままなので再利用できる。コール前の部分適用とコール時の引数適用、クロージャの方では自由変数への任意時代入も可能である。不可反駁指定はそのネーム存在の変数部分が不特定で[[ボトム型]]を導出する場合は評価を取り止め、特定している場合のみに評価を成立させて値存在にする機能である。ただしこれは遅延パターンマッチングで等価性審査から評価値写像につなげる為の用途にほぼ限定されている。必要渡し(メモ化渡し)による遅延評価は参照透過性を忠実履行するものであり、ネーム存在評価後の値存在は同時に[[メモ化]]されて、同一のネーム存在が再び引数にされた時は再評価されずにメモ化された値存在の方を渡すという仕組みである。この強制的な最適化による遅延評価は純粋関数型言語でのみ実装される事になる。評価の遅延は、[[帰納]]、[[再帰]]、[[無限]]、[[極限]]といった代数的表現の実装を可能にする。フロー分岐によって参照されなくなる式評価を結果的にスキップできることは処理の高速化につながり、しばしばテクニックとしても用いられる。また[[ボトム型]]が発生する式評価のスキップは[[フォールトトレラント設計|フォールトトレランス]]にもつながる。ただし柔軟な評価タイミングは同時にネーム存在と値存在の区別を困難にしてバグの温床になりがちなので、遅延評価が必要になる場所以外では、評価タイミングが明白の先行評価をデフォルトにするのが理想またはスタンダードとされている。代数的データ型では[[共用体|タグ共用体]]、[[線形リスト|連結リスト]]、[[再帰データ型]]の構造は遅延評価対象である。連結リストは無限リストと構造上同義である。

データストラクチャでも遅延評価の概念は扱われており、[[帰納]]、[[再帰]]、[[無限]]、[[極限]]といった代数表現の実装手段になっている。代数的データ型では[[共用体|タグ共用体]]、[[線形リスト|連結リスト]]、[[再帰データ型]]は遅延評価対象である。連結リストは無限リストと構造上同義であり遅延評価が無限性質の実装を可能にしている。


=== 参照透過性 ===
=== 参照透過性 ===
[[参照透過性]](''referential transparency'')とは関数は同じ引数値に対して必ず同じ評価値を恒久的に導出し、その評価過程において現行計算枠外の情報資源に一切の作用を及ぼさないというプロセス上の枠組みを意味する。現行計算枠外のいずれかの情報資源が変化するのと同時にいずれかの関数の評価過程も変化してしまう現象が[[副作用 (プログラム)|副作用]]と呼ばれる。参照透過性はこの副作用の論理的排除も同時に意味している。参照透過性に則した関数実装は関数の純粋化と呼ばれる。副作用の論理的排除関数純粋化の他、あらゆる再代入処理をプログラムから排除する事成立する。によってプログラム内に存在するあらゆる個体(値)写像(関数)によるつながりが[[有向グラフ]]化されて、プログラム開始時に宣言(''declarative'')された初期値まで遡れるようになる。宣言値からあらゆる存在値をつなぐ言わば写像の履歴の図表であるプロセス[[有向グラフ]]の解析と模型化は、[[プロセス計算|プロセス微積分]]ないし[[プロセス代数]]と呼ばれ[[並行プログラミング]]などの支柱になる。関数型プログラミングの世界で再代入がタブーとされるのは、それが写像の履歴の改ざんにるからである。従ってある時点の写像をただ書き留めておく[[束縛変数]]と、旧値の更新を新値の産出で代替した[[イミュータブル]]が重視される。[[構造化プログラミング|制御フロー]]の反復(ループは関数の再帰で表現され、選択(分岐非交和の関係でつげた写像で表現される。再代入処理は自由変数の他、リスト更新、クロージャ、継続、オプション型生成、ボトム型処理、システムコール、各種I/O作業なども指しており、参照透過性を維持しつつそれらを実装するための仕組みが[[型理論]]由来の派生構造型であり、[[圏論]]由来の[[モナド (プログラミング)|モナド]]ある。
[[参照透過性]](''referential transparency'')とは関数は同じ引数値に対する同じ評価値を恒久的に導出し、その評価過程において現行計算枠外の情報資源に一切の影響を及ぼさないというプロセス上の枠組みを意味する。現行計算枠外のいずれかの情報資源が変化するのと同時にいずれかの関数の評価過程も変化してしまう現象が[[副作用 (プログラム)|副作用]](''side effect'')と呼ばれる。参照透過性副作用の排除る。副作用を持ない関数を純粋関数(''pure function'')と呼。副作用の代表例の再代入と入出力処理でる。参照透過性が完全順守さプログラムでは、あらゆる個体(値)写像(関数)つながりが初期宣言値まで遡れるようになる。宣言値からあらゆる値をつなぐ写像の履歴の図表であるプロセス[[有向グラフ]]の解析と模型化は、[[プロセス代数]]と呼ばれ[[並行プログラミング]]などの支柱になる。関数型プログラミングの世界で値の再代入がタブーとされるのは、それが写像の履歴の改ざんになってプロセス有向グラフの整合性を崩壊させるからである。従ってある時点のをただ書き留めておく[[束縛変数]]と、旧値の更新を新値の産出で代替した[[イミュータブル]]が重視される。ループは関数の[[再帰]]で表現され、分岐は[[選言]]パターンマッチングで表現される。参照透過性を維持しなが入出力処理行うための機能には、派生構造型システム(''substructural type system'')と[[モナド (プログラミング)|モナド]](''monad'')がある。


参照透過性が保証されたプロセス[[有向グラフ]]は、一定の[[証明論]]に基づいたプルーフアシスタント(''proof asistant'')による[[正当性 (計算機科学)|プログラム正当性]]の[[形式的検証]]および[[数学的証明]]を可能にする。純粋関数型言語はその為に参照透過性をプログラム体の枠組みにしている。プログラム全体に参照透過性を適用するには関数の純粋化と再代入処理の排除の他にプログラムレベルでは回避できない各種I/O作業に伴う必然的副作用の論理的排除も必要ので専用のランタイム環境上での動作が必須になる。ここでの論理的とは[[公理的意味論]]に沿った正当性を意味する。ランタイム環境は「コンテキスト」を走行プログラムとの仲介にする。プログラム内の各関数は、ライナー型引数値として渡されたコンテキストに作用するという形で各種I/O作業を行う。の仮想的I/O作業はランタイム環境側実際に行されそのI/O作業で変化したピュータ環境はその都度コンテキストに反映される。関数はコンテキストをライナー型返り値として渡し返す。ライナ―型(''linear type'')は[[型理論]]の派生構造型(''substructural type'')の一形態であり、[[線形合同法]]に似たユニーク値生成アルゴリズムによってプロセス有向グラフの正当性を維持するための[[型システム]]である。これはユニークネス型呼ばれる。コンテキストに「関連を注入する仕組みはアフィン型(''affine type'')、抽出する仕組みは関連型(''relevant type'')と呼ばれる。双方とも派生構造型の一形態である。このように各種I/O作業をコンテキストへの作用という形にする事で副作用を論理的に排除し、ライナー型の疑似乱数列に似た仕組みで参照透過性を論理的に維持している。常にユニークな値に生成されるライナー型は、I/O作業の副作用によって実際には変化しているランタイム環境の時系列状態を完全に抽象化して、それらを理論上各個照会可能にしているマッピングキーである。これによってランタイム環境の変化もプロセス有向グラフで論理的に辿れるようている、型理論代わ[[圏論]]に基づてプロセス有向グラフの正当性を維持するめの手法が[[モナド (プログラミング)|モナド]]である。参照透過性を維持する以上の機能を持たない派生構造型に対して、モナドの方は関連値とコンテキストの連携を高度に柔軟化して様々に応用可能にした計算の構造化手法であり、その中の共変性を軸にした仕組みにライナー型が注入されて参照透過性の維持を実現している。
参照透過性が保証されたプロセス[[有向グラフ]]は、{{仮リンク|プルーフアシスタント|en|Proof asistant|label=}}による[[正当性 (計算機科学)|プログラム正当性]]の[[形式的検証]]および[[数学的証明]]を可能にする。参照透過性を順守するには、各種入出力に伴う副作用の論理的排除も必要なので専用のランタイム環境上での動作が必須になる。ランタイム環境は「コンテキスト」を走行プログラムとの仲介にする。プログラムは専用IDを包するコンテキストに作用するという形で各種入出力を行う。コンテキストへの仮想的入出力ランタイム環境側によって実際に行される。その入出力で変化したンタイム環境が反映された新生IDを内包するコンテキストがプログラム側される。コンテキストIDが毎時ユニク生成される仕組みは、派生構造システムのライナ―型(''linear type'')と呼ばれる。コンテキストに対象値を注入する仕組みはアフィン型(''affine type'')、コンテキストから対象値を抽出する仕組みは関連型(''relevant type'')と呼ばれる。毎時ユニーク生成されるライナー型IDは、各種入出力に伴う副作用によって実際には変化しているランタイム環境の時系列状態を完全に抽象化して、それらを理論上各個照会可能にしているマッピングキーである。これによってランタイム環境の変化もプロセス有向グラフで論理的に辿れることなるので同時に参照透過性も維持されていることにる。派生構造型システムの実装例にユニークネス型(''uniqueness type'')がある。ライナー型アフィン、関連型を組み合わせて特にその応用コーディングは煩雑なボイラープレートコードにながちだったので、それらを[[圏論]]視点の[[関手]]の合成とった仕組みでより平易かつ簡潔にした手法が[[モナド (プログラミング)|モナド]]である。


=== 型システム ===
=== 型システム ===
{{型システム}}
{{型システム}}
関数型プログラミングの[[型システム]](''type system'')は、[[型付きラムダ計算|型付けラムダ計算]]準拠の[[型理論]]に基づいて構築されている。ここでは型システム上の対比に沿った形で記述する。関数型言語の二大系統の内、[[ML (プログラミング言語)|ML系]]は[[静的型付け]]ベースであり、[[LISP|LISP系]]は[[動的型付け]]ベースである。
関数型プログラミング[[型システム]](''type system'')は、[[型付きラムダ計算|型付けラムダ計算]]ベースの[[型理論]]に基づいたスタイルで実装されている。型システムの分類に従った対比で述べると関数型では、性質や役割による[[セマンティクス|意味づけ]]によって値を分類する明示的型付け(''manifest typing'')よりも、計算可能性に基づく[[等価性]]によって値を分類する推論的型付け(''inferred typing'')が多用される。前者の意味づけとはプログラマによる型定義、型宣言、型注釈を指しており人間寄りの視点である。後者の等価性とは値を関数または演算子に適用できるかどうかの判別を指し、値への関心がそこで計算可能かどうかに絞られているので計算機寄りの視点である。明示的型付けではソースコード上の型宣言と型注釈から値の型が特定されるのに対し、推論的型付けでは[[型推論]]機能で特定される。型推論とはソースコードの解析によって値それぞれの等価性を導き出す機能である。数値や文字列といったリテラルはそのまま特定され、変数などのシンボルはその扱われ方や[[等式]]を並べた任意の法則の定義によって型(=等価性)が特定されるといった具合である。推論的型付けでは値への関心をその計算可能性に絞っているので、型宣言と型注釈は必要とされなくなる。例としてint型を型シノニムで金額型と数量型にした場合、明示的型付けではこの両者は区別されるが、推論的型付けでは区別されない。ソースコードの解析でどちらもint型準拠の等価と見られるからである。ただし注釈を強制すれば区別されるので等価性と意味づ性を使い分けられる。型注釈無しのままで値の意味づけ性も表現する場合は、構築子で値を包む[[ボックス化]]に似た手法が用いられる。また関数型では、所属する部品に注目して全体を識別する造的型付け(''structural typing'')よりも、記名か全体識別しその文脈所属す部品も識別する記名的型付け(''nominal typing'')方がよく用いられる。その実例は[[型クラス]]でありこれはアドホック多相とも言われる。型クラスは型理論における文脈を形式化したもので[[インタフェース (抽象型)|インターフェース]]のように用いられる。


'''静的型付け'''
関数型初期の[[LISP]]系の[[S式]]は、二項型構築子(コンス)の実行時の連結で形式化されていないパターンを構築し、プログラマの裁量による実行時の逐次チェックでパターン(型)の意味づけと計算に用いるための等価性を判別するといったものであり、これは潜在的型付け(''latent typing'')とも呼ばれる。この仕組みは[[動的型付け]](''dynamic typing'')の原点であり、実行時の逐次パターン判別は[[ダックタイピング]]の源流にもなった。[[ML (プログラミング言語)|ML]]系を境にしてパターンを事前形成する[[静的型付け]](''static typing'')が主流になった。その実装の[[代数的データ型]]は多項な型構築子の組み合わせであり、パラメトリック多相で[[ジェネリックプログラミング|ジェネリック化]]された。''Hindley–Milner''型体系はこのパラメトリック多相に対応した[[型推論]]機能を提供した。関数型では強い型付け(''strong typing'')が主流であるが、ユニオン型(等価性による非交和型)による値の扱いは弱い型付け(''weak typing'')相当と見なせる。


関数型言語静的型付けでは、性質や役割による[[セマンティクス|意味づけ]]によって値を分類する明示的型付け(''manifest typing'')よりも、計算可能性に基づく[[等価性]]によって値を分類する推論的型付け(''inferred typing'')が主流である。前者の意味づけとはプログラマによる型定義、型宣言、型注釈を指しており人間寄りの視点である。後者の等価性とは値を関数/演算子の引数にできるかどうかの判別を指し、値への関心がそこで計算可能かどうかに絞られているので計算機寄りの視点である。明示的型付けではソースコード上の型宣言と型注釈から値の型が特定されるのに対し、推論的型付けでは[[型推論]]機能で特定される。型推論とはソースコードの解析によって値それぞれの等価性を導き出す機能である。数値や文字列といったリテラルはそのまま特定され、変数などのシンボルはその扱われ方や、任意の[[等式]]を並べて定義した法則から分析によって型(=等価性)が特定されるといった具合である。推論的型付けでは値への関心をその計算可能性に絞っているので、型宣言と型注釈は必要とされなくなる。例としてint型を型シノニムで金額型と数量型にした場合、明示的型付けではこの両者は区別されるが、推論的型付けでは区別されない。ソースコードの解析でどちらもint型準拠の等価と見られるからである。推論的けで値の意味づけ性も表現する場合は、データ構築子で値を包む[[ボックス化]]が用いられる。データ築子(''data constructor'')は与えれた要素直積または非交和まとめるのと同時に[[型理論]]で言われる文脈(''context'')各要素の等価性に上乗せ付加するものでもある。
型は、それを量化したターム(型付け値)を普通に扱える[[全称量化子|全称量]](''for all'')のパターンと、そのタームの扱いに制限がある[[存在量化子|存在量]](''exists'')のパターンに分かれる。全称量のパターンはプロパータイプ(''proper type'')と呼ばれる。プロパータイプは1個以上のタイプ(''type'')から形成される。タイプは[[プリミティブ型|プリミティブ]]またはコンポジットの総称である。型構築子はプロパータイプを構成するタイプを決めて同時にそのプロパータイプの識別子になる。プロパータイプはそれらタイプに依存(''dependent'')しているとされその依存関係の表現は、例えばタイプAとタイプBからなるプロパータイプCでは「A→B→C」のように表される。プロパータイプ内の1個以上のタイプが抽象化されると存在量のパターンになる。タイプの抽象化とは、型構築子内の要素を型変数にする[[ジェネリックプログラミング|ジェネリック化]]と同義でありこれはパラトメトリック多相と言われる。存在量のパターンのタームは、抽象部分を残している型付け値になるのでその取扱いには様々な制限がかかる。これを全称量のパターンであるプロパータイプにするには、その型構築子への型引数の指定が必要になる。全称量のパターンであるプロパータイプと、そうでない存在量のパターンを区別する仕組みが[[型理論]]の[[カインド (型理論)|カインド]]である。カインドではタイプは*という総称記号になる。プロパータイプは「*」と表現される。型引数を1個必要とするものは「*→*」になる。2個必要なら「*→*→*」になり、これに型引数が1つ適用されると「*→*」になる。また、タイプに依存してプロパータイプを導出する仕組みが型構築子と呼ばれるのに対し、タームに依存してプロパータイプを導出する仕組みの方は[[型理論]]の[[依存型]]と呼ばれる。依存型の導出は、依存値×写像の直積で表現される。写像は依存関数とも呼ばれる。依存関数から導出される「型」も[[全称量化子|全称量]]のパターンと[[存在量化子|存在量]]のパターンに分かれており、依存型ではそれらが部分的に量化されていることもある。部分的に量化されている型とは、未確定の変数部分=量化されていない部分を内包しているネーム存在と同義になる。この型としてのネーム存在は任意に簡約されてより柔軟なパターンマッチングを可能にする。型としてのネーム存在は量化されるとタームとしての値存在になり、それをまた依存値にした別の型の導出も可能である。依存型は型構築子をメインにするそれとは異なる型システムの下で実装されている。


静的型付けにおける[[データ構造|データストラクチャ]]のパターン(型)はコンパイル前ないし実行前に全て事前形成される。その実装例である[[代数的データ型]]はデータ構築子の組み合わせでパターンを構築し、パラメトリック多相に基づいて[[ジェネリックプログラミング|総称化]]したパターン内の要素=型変数を、型構築子への型引数の組み合わせで特定した。''Hindley–Milner''型体系はこのパラメトリック多相に対応した[[型推論]]機能を提供している。型構築子(''type constructor'')は必要とする型引数の個数によって分類され、これは[[カインド (型理論)|カインド]](''kind'')と呼ばれる。カインドは総称記号である<code>*</code>の写像で型構築子の型種を表現する。型引数を必要としない型構築子と必要な型引数を全て付与された型構築子はプロパータイプと呼ばれ<code>*</code>と表現される。プロパータイプは[[全称量化子|全称量]]の型である。型引数を1個必要とするものは<code>*→*</code>になり、2個必要なら<code>*→*→*</code>になる。これらは[[存在量化子|存在量]]の型になる。<code>*→*→*</code>に型引数が1つ付与されると<code>*→*</code>になり更に1つ付与すると<code>*</code>のプロパータイプになる。全称量の型付け値(ターム)は普通に扱えるが、存在量の型付け値はその一部分が抽象化(大抵は環境依存値と同義)されたままの特別な値と見なされて一定の制限下で扱われる。
[[多態性]]三種の三番目であるサブタイプ多相は、構造的サブタイピング(''structural subtyping'')と振る舞いサブタイピング(''behavioral subtyping'')に分かれている。構造的サブタイピングは前述の構造的型付けを汎化と特化の多相に応用したものであり、参照透過性の節で述べた派生構造型はその一つのパターン化である。また[[モナド (プログラミング)|モナド]]も広義の構造的サブタイピングである。振る舞いサブタイピングの方は、データの[[操作的意味論]]の多相を扱うことから関数型とは相容れない部分が多い。関数型の[[代数的データ型]]と[[オブジェクト指向プログラミング|オブジェクト指向]]の[[抽象データ型]]は対象的なデータストラクチャと見なされている。前者がデータを主にしたデータ構造であるのに対して、後者は[[操作的意味論]]を主にしたデータ構造である。しかしオブジェクト指向との連携が模索される中で数々の手法も提示されている。動的型付けメインのLISP系ではS式の代わりに、各スロットに任意の変数を[[動的束縛|動的バインディング]]できるフレームレコードを用いる。その動的バインディング用レコードを1個以上引数にできる関数によって[[多重ディスパッチ]]が表現される。動的バインディング用レコードの型チェックは[[ダックタイピング]]で行われる。静的型付けメインのML系では、[[ジェネリックプログラミング|ジェネリック]][[クラス (コンピュータ)|クラス]](パラメトリック多相である総称的抽象データ型)の型変数の[[共変性と反変性 (計算機科学)|バリアンス]](''variance'')を用いる。バリアンスとは型変数の派生関係を有効にして、型変数に適用できるクラスの幅を持たせることを指す。型変数のバリアンスには[[共変性と反変性 (計算機科学)|共変性]](''covariance'')と[[共変性と反変性 (計算機科学)|反変性]](''contravariance'')がある。共変性の型変数には適用クラスとその派生クラスを当てはめることができる。それに対して反変性の型変数には適用クラスとその基底クラスを当てはめることができる。反変性の用途はやや想像しにくいが、特化させた実装データに対するデータ抽象の汎化などに用いられる。また、関数の写像において基底クラスの引数→派生クラスの返り値は共変性、派生クラスの引数→基底クラスの返り値は反変性となる。バリアンスは境界的定量化(''bounded quantification'')の手法でも行われる。これは型引数または型変数を、共変ないし反変の基準とする注釈クラスで記号修飾するものである。共変である上限境界は、クラスのコンストラクタ(総称的抽象データ型の型構築子)の型引数を注釈クラスの派生クラスの適用に限定できる。反変である下限境界は、クラス内の型変数を注釈クラスの基底クラス範囲に差し戻せる。

推論的型付け下の関数の扱いでは、人為的表記による意味づけを重視した記名的型付け(''nominal typing'')が取り入れられており、これで推論的型付けの枠組み内での[[多重定義|関数オーバーロード]]が表現されている。ここでの人為的表記による意味づけとは、型構築子/データ構築子/関数の型それぞれのパターン内の型変数に、[[型理論]]で言われる文脈(''context'')を付加することを指している。文脈の付加は制約(''constraint'')と呼ばれる。文脈の付加はアドホック多相と考えられており、代表的な実装例はそれと[[ジェネリックプログラミング]]を組み合わせた[[型クラス]]である。型クラスは、引数/計算値/評価値などを[[総称型]]化したジェネリック関数群を定義できる機能であり、同時に推論的型付けと共存する関数オーバーロードの実装と、特定の意味づけ型を扱うための関数モジュールを定義するための手段になっている。型クラスの定義構文では上述のジェネリック関数群が定義され、その型クラス名が文脈記号になる。型構築子の定義に文脈を付加すると、その型クラスのジェネリック関数群にその型構築子=型を当てはめた関数群がコンパイル時に自動生成される(deriving)。また文脈を付加して当てはめ関数群を自動生成(instance)した上で、その型構築子=型のための当てはめ関数も個別定義(where)できる構文もある。この双方がジェネリック関数の特有インスタンス化になる。明示的型付けでは型注釈を付けた引数パターンの列挙というシンプルな手段で関数オーバーロードを表現できるが、推論的型付けでは等価性に上乗せした文脈という二段階の手段が必要になる。記名的型付けと併せた推論的型付けでのオーバーローディング関数の選択決定は、始めに仮引数と実引数の型クラスのみに注目した照合が行われ、次にその型クラスの制約内での型推論照合が行われるという形になる。

'''動的型付け'''

動的型付けにおける[[データ構造|データストラクチャ]]のパターン(型)はコンパイル前ないし実行前の事前形成に加えて、実行中の随時にも事後形成できる。その実装例である[[S式]]は、二項データ構築子([[Cons (Lisp)|コンス]])の実行時の連結で形式化されていないパターンを構築し、プログラマの裁量による任意の実行時チェックでパターンの意味づけと計算に用いるための等価性を判別するといったものである。パターンの組み合わせが明確に形式化されておらずその識別をプログラマの裁量に委ねており、またチェックタイミングも委ねられている事から、これは潜在的型付け(''latent typing'')と呼ばれている。潜在的型付けは動的型付けの原型的位置づけである。

もう一つの実装例として動的なレコード(''record'')がある。この動的レコードは内部的には[[動的配列]]と同じものであり、配列の各スロットに任意の値の[[参照 (情報工学)|参照]]が納められて、そのスロットは[[構造体]]のフィールドと同じものになる。スロットは増設削減可能である。レコードのタグ名はそのまま型名になる。レコードを量化した値([[インスタンス]])には、システム側が別途用意する型情報が結び付けられており、変数への束縛ないし代入および関数/演算子への引数代入時に毎回自動的に型判別される。型情報と型判別タイミングが形式化されているのでこれは動的型付けとなる。動的型付けのインスタンスを関数の引数にすることは動的な[[多重定義|関数オーバーロード]]を自然表現し、これはオブジェクト指向に倣って[[多重ディスパッチ]]とも呼ばれる。レコード・フィールドのアクセスは、フィールド名関数をインスタンスに適用するという方法で行われる。オブジェクト指向の<code>instance.field</code>が関数型では<code>field instance</code>のようになる。同じフィールド名関数から得られる値の型は、適用するインスタンスの型構造による実行時多態になる。この仕組みは構造的型付け(''structural typing'')に沿ったものである。


=== モナド ===
=== モナド ===
{{Quotation|''A monad is just a monoid in the category of endofunctors, what's the problem?''<br/>(モナドは自己関手の圏のただのモノイドだよ。何か問題でも?)|Philip Wadler}}[[モナド (プログラミング)|モナド]](''monad'')の説明でよく引用されるこの文言はその特徴を明快に表したヒントと言われる。モナドは[[圏論]]由来の自己[[関手]]の合成の仕組みで[[参照透過性]]を維持しつつ、[[代数的構造]]由来の[[モノイド]]の仕組みで非純粋関数の連結体を平易に表現する機能である。非純粋関数の連結体がそのまま一連の[[副作用 (プログラム)|副作用]]内包プロセスになりそれを参照透過性の枠内で実行できる。モナドはプログラム的には、関数の量化を扱う[[二階述語論理]]の実装である[[カリー化]]の活用形態である関数合成と部分適用の応用手法であり、参照透過性欄で説明した派生構造型システムのライナー型の役割を[[圏 (数学)|圏]]に見立てたデータ構築子に持たせている。またデザインパターン的には、関数を引数値に適用する(''applying a function to an argument'')通常の関数とは正反対に、モナドでは値を関数に適用する(''applying a value to a function'')形態を取っており、値を同名関数に反復適用しての特殊な再帰を表現できる。モナドでは値に特殊な演算子を適用することでそれを関数に適用できるようにしている。

モナドの世界では、基本値から導出されるモナド値をモナド関数に次々と適用して状態遷移を表現する。モナド値(''monadic value'')とはMaybe値、例外発生、入出力環境、システムコール、クロージャ、継続といったあらゆる副作用プロセスを扱うためのオブジェクトである。モナド関数(''monadic function'')とはそのオブジェクトのメソッドと考えてよいものである。モナド値とモナド関数は合成演算子を通した表裏一体の存在であり、これがモノイドを指している。合成演算子をモナド値に適用したものをモナド関数に適用して導出されたモナド値を、また同じ手順でモナド関数に適用するといった繰り返しになる。これはモナド合成体(''monadic composition'')と呼ばれる。モナド値は<code>MA</code>のように型表現され、<code>A</code>は基本値、<code>M</code>は基本値を包むコンテキストまたはコンテナである。モナド関数は<code>(A→MB)</code>を基本とする関数の型の値であり、与えられた基本値からモナド値を操作して新たなモナド値を返す。モナド値は<code>MA</code>の型を基本とし、対象内容によって<code>M(A?)</code>、<code>M(A+E)</code>、<code>M(W×A)</code>、<code>E→MA</code>、<code>S→M(A×S)</code>、<code>(A→MR)→MR</code>といった型の値または関数の型の値にリフト(''lift'')される。これはモナド変換子(''monad transformer'')と呼ばれる。また、モナド値の<code>MA</code>の<code>M</code>を空データにして事実上の<code>A</code>にしモナド関数も事実上の<code>(A→B)</code>にした恒等モナド(''identity monad'')もあるがこれは全くの便宜目的である。モナド値は状態遷移の記録媒体であり、η自然変換演算子を基本値に適用することで導出される。基本値+αから成るモナド値または基本値を包含するモナド値はデータ構築子として表現されて自己関手の圏の枠組みとなり、そのデータ構築子を束縛した型構築子への型引数でモナド値内の型決定がなされる。モナドは大まかに言うと以下の六つの要素から実装されている。

* モナドの文脈を付加された型構築子。一つの副作用内包プロセスを扱う関数群モジュールに見立てられる。
* 基本値+αのコンテナであるモナド値=データ構築子。圏に見立てられる。
* μ自然変換演算子(join)kleisli-star拡張演算子(bind)といった合成用の二項演算子。
*基本値とη自然変換演算子(return)とモナド値。モナド値+二項演算子でモノイドに見立てられる。
* モナド関数。パターンマッチング分岐可能でモジュール内の操作を一手に扱う。自己関手内容に見立てられる。
*ファンクタ文脈からの持ち上げ演算子(fmap)は補助的機能。関手に見立てられる。

モナド値は付加モナドと自由モナド(Maybe/例外/有限リストモナドなど)以外では、実質的に存在量の値になるので普通の値のように扱うことは出来ない。ただし付加/自由モナドでも参照透過性を維持するためには存在量と同等に扱う必要が出てくる。<code>return</code>を基本値に適用してモナド値を表現することからモナド処理は始まる。基本値とは扱うモナドに合わせた任意の値である。そのモナド値は圏としてのユニークIDを持つことになる。ここで基本値を<code>A</code>としそのモナド値を<code>MA</code>とする。<code>MA</code>にbindを適用して<code>(A→MB)→MB</code>という写像を導出する。その写像は先の<code>MA</code>と同じ圏IDを備えたものになる。その写像をモナド関数<code>(A→MB)</code>に適用すると、そのモナド関数内では渡された<code>A</code>やその他の値などに<code>return</code>を適用して表現されるモナド値の圏IDは<code>MA</code>のもので共通化される。モナド関数内においての<code>return</code>は基本値をモナド値に代入する機能と見てよい。<code>return</code>は用途別関数にそれぞれラッピングされて使われるのが普通である。空引数からモナド値を表現する<code>return</code>もありこれはモナドプリミティブ(''monadic primitive'')と呼ばれ、この場合はモナド値の圏IDが暗黙引数になっている。モナド値はファイルハンドルのようなものと考えると分かりやすくなり、モナド値を直接引数にできる専用関数も存在する。モナド関数内ではモナド値から基本値を取り出す演算子が有効になる。それは<code>A←MA</code>のように表現されてコモナド(''comonad'')と呼ばれる機能になる。抽出した基本値からの処理の中で再度<code>return</code>が行われる。モナド関数は自己関手内容に見立てられているので、その中では<code>return</code>の繰り返しによる事実上の再代入処理が許されている。その論理的な辻褄合わせの要点になる<code>bind</code>の正当性および計算可能性を表現するためにファンクタ則とモナド則の等式がプログラム内で定義されている。ここでいわゆる圏論の知識が必要になるがその説明は先送りする。モナド関数はモナド値を返しそれに再度<code>bind</code>を適用できるのでこれがモノイドを意味している。モナド関数の外での<code>return</code>は毎時ユニークな圏IDのモナド値を表現するので同じ基本値でもその都度異なる圏が表現される事になり、これが[[自然変換]]([[関手圏]]の[[射 (圏論)|射]])演算子の呼称由来になっている。

モナドは'''ファンクタ'''(''functor'')の派生文脈にされることが多いが、これは<code>bind</code>を形成するクライスリ射と<code>join</code>の合成の持ち上げ(関手)に<code>fmap</code>が使われるからである。ファンクタ文脈は関数<code>fmap</code>を持つ。そのままファンクタの機能名で呼ばれることが多い<code>fmap</code>は、関数<code>(A→B)</code>から関数<code>(TA→TB)</code>を導出する関手=関数である。この関数は<code>TA</code>に適用できて<code>TB</code>を導出できる。<code>T</code>は基本値を包むコンテキストまたはコンテナでありその代表例はリストである。基本値に対する作用をコンテキストで拡張解釈できるのがファンクタの利点である。例えば基本値への+1という作用をリストのコンテキストで拡張解釈するのはリストの全要素に+1するという意味になる。これはリストをそのまま計算対象にできる利便性に繋がる。ファンクタの派生文脈に'''アプリカティブ'''(''applicative'')がある。アプリカティブは、ファンクタのコンテキストに包まれた関数を「コンテキストに包まれた先頭引数→コンテキストに包まれた残り引数&評価値」という1引数の関数に変換する演算子<code><*></code>を持つ。<code><*></code>は<code>F(A→B)</code>から<code>(FA→FB)</code>を導出する演算子である。<code>F</code>はコンテキスト、<code>(A→B)</code>は元の関数、<code>(FA→FB)</code>は1引数の関数である。この<code>B</code>は多相であり実際は値<code>*</code>関数<code>(*→*)</code> 関数<code>(*→*→*)</code>などになっている。アプリカティブは、2個以上の引数の関数をファンクタするための機能と考えてよい。2個以上の引数の関数は<code>fmap</code>でそのまま持ち上げられないのでアプリカティブ関手の<code>pure</code>が用いられる。これは<code>A→FA</code>と表現され<code>A</code>が関数、<code>F</code>がコンテキストである。<code>pure</code>によって好きな引数個数の関数をコンテキストで包み<code><*></code>をそれに適用して導出された関数を<code>FA</code>に適用できる。アプリカティブ関手<code>pure::A→FA</code>とモナドのη自然変換演算子<code>return::A→MA</code>は同じ働きに見えるが、前者は関数(関数の型の値)を純粋に持ち上げるだけの[[関手]]なのに対して、後者は持ち上げる関手を毎時垂直合成していく[[関手圏]]の[[射 (圏論)|射]]の[[自然変換]]であるという性質上の違いがある。


== 歴史 ==
== 歴史 ==
1930年代に数学者[[アロンゾ・チャーチ]]によって発明された[[ラムダ計算]]は[[写像|関数適用]]をベースにした計算用[[形式体系]]であり、1937年に数学者[[アラン・チューリング]]自身により[[チューリング完全]]の性質が明らかにされて、[[チューリングマシン]]と等価な[[計算模型]]である事が証明されている。この経緯からラムダ計算は関数型プログラミングの基底に据えられた。ラムダ計算と同等の[[計算理論]]に[[コンビネータ論理]]があり、1920年代から1930年代にかけて数学者[[ハスケル・カリー]]らによって発明されている。こちらは関数型プログラミングの原点である[[高階論理]]式の基礎モデルにされた。チャーチはラムダ計算を拡張してその各タームに型を付与した[[型付きラムダ計算|型付けラムダ計算]]も考案しており、これは関数型プログラミングにおける[[型理論]]と[[型システム]]の源流になった。
1930年代に数学者[[アロンゾ・チャーチ]]によって発明された[[ラムダ計算]]は[[写像|関数適用]]を計算単位にした[[形式体系]]であり、1937年に数学者[[アラン・チューリング]]自身により[[チューリング完全]]の性質が明らかにされて、[[チューリングマシン]]と等価な[[計算模型]]である事が証明されている。この経緯からラムダ計算は関数型プログラミングの基底に据えられた。ラムダ計算と同等の[[計算理論]]に[[コンビネータ論理]]があり、1920年代から1930年代にかけて数学者[[ハスケル・カリー]]らによって発明されている。こちらは関数型プログラミングの原点である[[高階論理|高階述語論理]]式の基礎モデルにされた。チャーチはラムダ計算を拡張してその各タームに型を付与した[[型付きラムダ計算|型付けラムダ計算]]も考案しており、これは関数型プログラミングにおける[[型理論]]と[[型システム]]の源流になった。


'''1950年代'''
'''1950年代'''


初の関数型プログラミング言語とされる「[[LISP]]」は、1958年に[[マサチューセッツ工科大学]]の計算機科学者[[ジョン・マッカーシー]]によって開発された。LISPの関数はラムダ計算の形式を元に定義され再帰可能に拡張されており、式のリスト化とその遅延評価および高階評価など幾つかの関数型的特徴を備えていた。LISPは数多くの”方言”を生み出しているが、その中でも「[[Scheme]]」「[[Dylan]]」「[[Racket]]」「[[Clojure]]」「Julia」は関数型の特徴を明確にした言語である。1956年に公開された「[[Information Processing Language]]」の方が先駆であるが、こちらはアセンブリベースの[[低水準言語]]なので前段階扱いである。IPLが備えていた[[ニーモニック・コード|ニーモニックコード]]のリストをオペランドにできるジェネレータ機能はLISPに影響を与えたと言われる。高階オペランド演算処理は高階関数と同じ働きをし、メモリ一括処理のストリング命令の効率を高めるなどした。
初の関数型プログラミング言語とされる「[[LISP]]」は、1958年に[[マサチューセッツ工科大学]]の計算機科学者[[ジョン・マッカーシー]]によって開発された。LISPの関数はラムダ計算の形式を元に定義され再帰可能に拡張されており、式のリスト化とその遅延評価および高階評価など幾つかの関数型的特徴を備えていた。LISPは数多くの”方言”を生み出しているが、その中でも「[[Scheme]]」「[[Dylan]]」「[[Racket]]」「[[Clojure]]」「Julia」は関数型の特徴を明確にした言語である。1956年に公開された「[[Information Processing Language]]」の方が先駆であるが、こちらはアセンブリベースの[[低水準言語]]なので前段階扱いである。IPLが備えていた[[ニーモニック・コード|ニーモニックコード]]のリストをオペランドにできるジェネレータ機能はLISPに影響を与えたと言われる。高階オペランド演算は高階関数と同じ働きをし、メモリ一括処理のストリング命令の効率を高めるなどした。


'''1960年代'''
'''1960年代'''


1964年に計算機科学者[[ケネス・アイバーソン]]が開発した「[[APL]]」は、数多く定義された関数記号に多次元配列データを適用する機能を中心にした言語であり、取り分け[[スプレッドシート]]処理に対する効率性が見出されて、1960年代以降の商業分野と産業分野に積極導入された。APLは関数型言語ではなく配列プログラミング言語に位置付けられているが、配列を始めとするデータ集合に対する関数適用の有用性を特に証明した言語になった。そのデータ集合処理の可能性に注目た「[[J言語|J]]」「K」「Q」といった派生言語が後年に登場している。また後年の「[[FP (プログラミング言語)|FP]]」にも影響を与えている。続く1966年に発表された「[[ISWIM]]」は関数型を有用な構文スタイルとして扱うマルチパラダイム言語の原点とされ、[[ALGOL]]を参考にした構造化プログラミングに高階関数とwhereスコープが加えられていた。60年代の関数型プログラミングの歴史はもっぱらLISPの発展を中心にしていたが、ISWIMは後年の「ML」「Scheme」のモデルにされている。
1964年に計算機科学者[[ケネス・アイバーソン]]が開発した「[[APL]]」は、計算タイプを定義された関数記号に各種配列データを適用する機能を中心にした言語であり、特に[[スプレッドシート]]処理に対する効率性が認められて、1960年代以降の商業分野と産業分野に積極導入された。APLは多次元配列などのデータ集合に対する関数適用の有用性を特に証明した言語になった。そのデータ集合処理注目されAPLからは「[[J言語]]」「S」「A」「K」「Q」といった派生言語が生み出されている。APLの記号構文は一つの手本になりその流れは後年の「[[FP (プログラミング言語)|FP]]」から「[[Haskell]]」にも汲まれた。続く1966年に発表された「[[ISWIM]]」は手続き型と関数型を組み合わせたマルチパラダイムの原点的言語であり、[[ALGOL]]を参考にした構造化プログラミングに高階関数とwhereスコープが加えられていた。60年代の関数型プログラミングの歴史はもっぱらLISPの発展を中心にしていたが、ISWIMは後年の「ML」「Scheme」のモデルにされている。


'''1970年代'''
'''1970年代'''


相互[[自動定理証明]]に向けて始められた「''Logic for computable functions''」プロジェクトの中で1973年に導入された「[[ML (プログラミング言語)|ML]]」は[[代数的データ型]]、[[多態性|パラメトリック多相]]、[[型推論]]などを備えた関数型言語であり、計算機科学者[[ロビン・ミルナー]]によって開発された。また1975年に[[MIT人工知能研究所]]の計算機科学者[[ガイ・スティール・ジュニア|ガイ・スティール]]と工学者[[ジェラルド・ジェイ・サスマン|ジェ・サスマン]]が設計してAIリサーチ用に導入された「[[Scheme]]」は任意タイミング評価(call/cc)可能な[[継続]]と[[ガーベジコレクション]]を備え、レキシカルスコープで構造化が図られており[[末尾再帰]]を最適化していた。MLとScheme双方の登場は関数型プログラミングのマイルストーンになった。また同年代に代数的データ型を初めて導入し[[クリーネの再帰定理]]を証明実装した「Hope」と、関数の数学的純粋性を初めて重視した「SASL」も発表されている。1977年、[[バッカス・ナウア記法|BNF記法]]と[[FORTRAN]]開発の功績でこの年の[[チューリング賞]]を受けた計算機科学者[[ジョン・バッカス]]は「''Can Programming Be Liberated From the von Neumann Style? -A Functional Style and Its Algebra of Programs-''」と題した記念講演を行い、一説にはこれを境にして関数型(''functional'')というパラダイム名が定着したと言われている。なお同時に発表された「[[FP (プログラミング言語)|FP]]」は関数水準(''function-level'')言語として紹介されている。[[ノイマン型]]からの脱却を題目に掲げたバッカスは、FPのプログラムをアトム+関数+フォーム(=高階関数)の階層構造と定義し、[[プロセス代数|代数]]を用いるフォームの結合で構築されると提唱した。
[[スタンフォード大学]]と[[エディンバラ大学]]で実施された[[対話型証明系|対話型]][[自動定理証明]]プロジェクト「''Logic for computable functions''」の中で1973年に導入された「[[ML (プログラミング言語)|ML]]」は[[代数的データ型]]、[[多態性|パラメトリック多相]]、[[型推論]]などを備えた関数型言語であり、計算機科学者[[ロビン・ミルナー]]によって開発された。また1975年に[[MIT人工知能研究所]]の計算機科学者[[ガイ・スティール・ジュニア|ガイ・スティール]]と工学者[[ジェラルド・ジェイ・サスマン|ジェラルド・サスマン]]が設計してAIリサーチ用に導入された「[[Scheme]]」は任意タイミング評価(call/cc)可能な[[継続]]と[[ガーベジコレクション]]を備え、レキシカルスコープで構造化が図られており[[末尾再帰]]を最適化していた。MLとScheme双方の登場は関数型プログラミングのマイルストーンになった。同年代に代数的データ型を初めて導入し[[クリーネの再帰定理]]を証明実装した「Hope」と、関数の数学的純粋性を初めて重視した「SASL」も発表されている。1977年、[[バッカス・ナウア記法|BNF記法]]と[[FORTRAN]]開発の功績でこの年の[[チューリング賞]]を受けた計算機科学者[[ジョン・バッカス]]は「''Can Programming Be Liberated From the von Neumann Style? -A Functional Style and Its Algebra of Programs-''」と題した記念講演を行い、一説にはこれを境にして関数型(''functional'')というパラダイム名が定着したと言われているが、同時に発表された「[[FP (プログラミング言語)|FP]]」は関数水準(''function-level'')言語として紹介されている。[[ノイマン型]]からの脱却を題目に掲げたバッカスは、FPのプログラムをアトム+関数+フォーム(=高階関数)の階層構造と定義し、[[プロセス代数|代数]]を用いるフォームの結合で構築されると提唱した。


'''1980年代'''
'''1980年代'''


1978年にMLの開発者ミルナーが発表した型推論アルゴリズムが1982年に証明されると、パラメトリック多相に対応した[[型推論]]機能を眼目にした''Hindley–Milner''型体系が確立され、関数型プログラミング型システムは一つの完成水準に達した。1983年にML標準化目的の下で''Hindley–Milner''型体系を導入した「[[Standard ML]]」が発表された。続1985年にML派生の代表格「Caml」が公開された。同じく1985年にSASLの後継として発表された「[[Miranda]]」は、遅延評価を標準にしながら関数の数学的純粋性を追求した言語であり、関数型プログラミング研究用[[オープン標準|オープンスタンダード]]のコンセンサスで1987年から策定が開始された[[Haskell]]のモデルになりその進捗を大きく後押しした。それと前後してMirandaは1987年公開の純粋関数型言語「[[Clean]]」にも大きな影響を与えている。Cleanは後発のHaskellをも叩き台にして改良を続けた。また関数型と[[並行計算]]の適性が認識される中で1986年の通信業界で開発された「[[Erlang]]」は[[並行プログラミング]]指向の面で特に注目を集めている言語である。1988年公開の「[[Wolfram (プログラミング言語)|Wolfram]]」はAPLスタイルのリスト処理に強力なパターンマッチングやイテレーションを加えた言語で90年代を通して改良が続けられていた。
MLの開発者ミルナーが発表していた型推論アルゴリズムが1982年に証明されると、パラメトリック多相に対応した[[型推論]]機能を眼目にした''Hindley–Milner''型体系が確立されて代的データ型の実用性が高められた。80入ると共に方言が多様化していたLISPとMLの両コミュニティで一定の標準化が求められようになり、1983年に''Hindley–Milner''型体系を導入した「[[Standard ML]]」が発表された。それに対して1984年に発表された「[[Common Lisp]]」では[[手き型プログラミング|手続き型パラダイム]]が強調されて関数型の枠組みからやや外れた方向性を示したので、関数型言語の枢軸はMLに置かれた。1985年にML言の代表格となる「Caml」が公開された。同じく1985年にSASLの後継として発表された「[[Miranda]]」は、遅延評価を標準にしながら関数の数学的純粋性を追求した言語であり、関数型プログラミング研究用[[オープン標準|オープンスタンダード]]のコンセンサスで1987年から策定が開始された[[Haskell]]のモデルになりその進捗を大きく後押しした。それと前後してMirandaは1987年公開の純粋関数型言語「[[Clean]]」にも大きな影響を与えている。Cleanは後発のHaskellをも叩き台にして改良を続けた。また関数型と[[並行計算]]の適性が認識される中で1986年の通信業界で開発された「[[Erlang]]」は[[並行プログラミング]]指向の面で特に注目を集めている言語である。1988年公開の「[[Wolfram (プログラミング言語)|Wolfram]]」はAPLスタイルのデータ集合処理に機能を豊富にしたパターンマッチングやイテレーションを加えた言語で90年代を通して改良が続けられていた。


'''1990年代'''
'''1990年代'''


1990年に関数型プログラミングの第二のマイルストーンと言える純粋関数型言語「[[Haskell]]」が初リリースされた。Haskellは遅延評価と型理論の文脈を形式化した型クラスと圏論由来のデザインパターンであるモナドの導入を特徴にしていた。1992年に[[動的型付け]]レコードクラスと[[多重ディスパッチ]]メソッドを扱う関数型言語「[[Dylan]]」が登場した。1993年に[[ベクトル]]、[[行列]]、[[表 (データベース)|表テーブル]]などのデータストラクチャを扱えて[[統計的検定]]、[[時系列分析]]、[[データ・クラスタリング|クラスタリング]]分野に特化した関数型言語「[[R言語|R]]」が発表された。1995年にLISPの[[マクロ (コンピュータ用語)|マクロ]]機能を大幅に強化したコンポーネント指向により各分野に合わせた[[ドメイン固有言語]]として振る舞える「[[Racket]]」が登場した。1996年にはML系列のCamlにオブジェクト指向視点の[[抽象データ型]]を導入した「[[OCaml]]」が公開された。90年代の関数型プログラミングの歴史では関数の数学的純粋性に則った[[参照透過性]]の重視の他、[[オブジェクト指向プログラミング|オブジェクト指向]]との連携の模索が目立っていた。日本ではStandard MLに独自の拡張を施した「SML#」が発表されている。風変りなものに[[コンビネータ論理]]の形式に立ち返った「[[Unlambda]]」がある。[[数理論理学]]拠る関数型に対しての[[古典論理学]]に拠る[[論理プログラミング]]親和性も見直されるようなり、1995年に「Mercury」が公開された。論理型のパラダイムは主に[[パターンマッチング|パターンマッチング式]]の拡張と応用に適していた。
1990年に関数型プログラミングの第二のマイルストーンと言える純粋関数型言語「[[Haskell]]」が初リリースされた。Haskellは遅延評価と型理論の文脈を形式化した型クラスと圏論由来のデザインパターンであるモナドの導入を特徴にしていた。1992年に[[動的型付け]]レコードと[[多重ディスパッチ]]を扱う関数型言語「[[Dylan]]」が登場した。1993年に[[ベクトル]]、[[行列]]、[[表 (データベース)|表テーブル]]などのデータストラクチャを扱えて[[統計的検定]]、[[時系列分析]]、[[データ・クラスタリング|クラスタリング]]分野に特化した関数型言語「[[R言語|R]]」が発表された。1995年にLISPの[[マクロ (コンピュータ用語)|マクロ]]機能を大幅に強化したコンポーネント指向により各分野に合わせた[[ドメイン固有言語]]として振る舞える「[[Racket]]」が登場した。1996年にはML方言のCamlにオブジェクト指向視点の[[抽象データ型]]を導入した「[[OCaml]]」が公開された。90年代の関数型プログラミングの歴史では関数の数学的純粋性に則った[[参照透過性]]の重視の他、[[オブジェクト指向プログラミング|オブジェクト指向]]との連携の模索が目立っていた。日本ではStandard MLに独自の拡張を施した「SML#」が発表されている。風変りなものに[[コンビネータ論理]]の形式に立ち返った「[[Unlambda]]」がある。1995年公開された「Mercury」は関数型[[論理型プログラミング|論理プログラミング]]の合の子のような言語であり、[[自動推論]]分野への応用に特化されていた。


'''2000年代'''
'''2000年代'''


2000年代になると関数型プログラミングへの注目度は更に高まり、マルチパラダイムに応用された関数型言語が様々に登場した。2003年のJava仮想マシン動作でオブジェクト指向と関数型を融合した「[[Scala]]」、2005年のマイクロソフト製のML派生「[[F Sharp|F#]]」、2007年のJava仮想マシン動作のLISP方言「[[Clojure]]」など数々のポピュラー言語が生み出されている。また、[[カリー=ハワード同型対応|カリー=ハワード同型対応]]の理論に基づいたプルーフアシスタント(''proof assistant'')によるプログラム正当性の数学的証明を指向した関数型言語が支持され、2004年に「Epigram」2007年に「[[Agda]]」および純粋関数型「Idris」が発表されている。これらの言語では{{仮リンク|直感的型理論|en|Intuitionistic type theory}}で解釈された[[依存型]]も導入されて一歩進んだ型システム実現ている。関数型構文の有用性がより広く認識されるに従い、オブジェクト指向言語やスクリプト言語にも積極的に導入されるようになった。産業分野からも注目されるようになり、[[Constructive Solid Geometry|CSG]]幾何フレームワーク上で動く[[CAD]]への導入も始められた。しかし関数型コンセプトに馴染まないオペレーターが定数化規則による値の再代入制限に困惑して設計作業に支障をきたすなどの弊害も明らかになっている。
2000年代になると関数型プログラミングへの注目度は更に高まり、マルチパラダイムに応用された関数型言語が様々に登場した。2003年のJava仮想マシン動作でオブジェクト指向と関数型を融合した「[[Scala]]」、2005年のマイクロソフト製のML言「[[F Sharp|F#]]」、2007年のJava仮想マシン動作のLISP方言「[[Clojure]]」など数々のポピュラー言語が生み出されている。また、[[カリー=ハワード同型対応|カリー=ハワード同型対応]]の理論に基づいた{{仮リンク|プルーフアシスタント|en|Proof asistant|label=}}によるプログラム正当性の数学的証明を指向した関数型言語が支持され、2004年に「Epigram」2007年に「[[Agda]]」および純粋関数型「Idris」が発表されている。これらの言語では数学者[[ペール・マルティン=レーフ|マルティン・レーフ]]による{{仮リンク|直感的型理論|en|Intuitionistic type theory}}準拠の[[依存型]]を中心にした型システム実現されている。関数型構文の有用性がより広く認識されるに従い、オブジェクト指向言語やスクリプト言語にも積極的に導入されるようになった。産業分野からも注目されるようになり、[[Constructive Solid Geometry|CSG]]幾何フレームワーク上で動く[[CAD]]への導入も始められた。しかし関数型コンセプトに馴染まないオペレーターが定数化規則による値の再代入制限に困惑して設計作業に支障をきたすなどの弊害も明らかになっている。


== 代表的な関数型言語 ==
== 代表的な関数型言語 ==
78行目: 119行目:


: 動的型付け、先行評価
: 動的型付け、先行評価

'''[[APL]]''' (1964年)

: 配列プログラミング言語、動的型付け、先行評価


'''[[ISWIM]]''' (1966年)← LISP、[[ALGOL]]
'''[[ISWIM]]''' (1966年)← LISP、[[ALGOL]]
97行目: 142行目:
'''[[Standard ML]]''' (1983年)← ML、Hope、[[Pascal|PASCAL]]
'''[[Standard ML]]''' (1983年)← ML、Hope、[[Pascal|PASCAL]]


: ML派生、静的型付け、先行評価
: ML方言、静的型付け、先行評価


'''Caml''' (1985年)← ML
'''Caml''' (1985年)← ML


: ML派生、静的型付け、先行評価
: ML方言、静的型付け、先行評価


'''[[Miranda]]''' (1985年)← ML、Hope、SASL
'''[[Miranda]]''' (1985年)← ML、Hope、SASL


: 純粋関数型、静的型付け、遅延評価
: 純粋関数型言語、静的型付け、遅延評価


'''[[Erlang]]''' (1986年)← LISP、[[Prolog]]、[[Smalltalk]]
'''[[Erlang]]''' (1986年)← LISP、[[Prolog]]、[[Smalltalk]]
113行目: 158行目:
'''[[Clean]]''' (1987年)← Miranda
'''[[Clean]]''' (1987年)← Miranda


: 純粋関数型、静的型付け、遅延評価
: 純粋関数型言語、静的型付け、遅延評価


'''[[Haskell]]''' (1990年)← Scheme、Standard ML、Miranda、FP
'''[[Haskell]]''' (1990年)← Scheme、Standard ML、Miranda、FP


: 純粋関数型、静的型付け、遅延評価
: 純粋関数型言語、静的型付け、遅延評価


'''[[Dylan]]''' (1993年)← Scheme、[[Common Lisp Object System|CLOS]]、[[ALGOL]]
'''[[Dylan]]''' (1993年)← Scheme、[[Common Lisp Object System|CLOS]]、[[ALGOL]]
125行目: 170行目:
[[R言語|'''R''']] (1993年)← Scheme、[[Common Lisp Object System|CLOS]]
[[R言語|'''R''']] (1993年)← Scheme、[[Common Lisp Object System|CLOS]]


: 動的型付け、先行評価
: 配列プログラミング言語、動的型付け、先行評価


'''[[Racket]]''' (1995年)← Scheme、[[Eiffel]]
'''[[Racket]]''' (1995年)← Scheme、[[Eiffel]]
133行目: 178行目:
'''[[OCaml]]''' (1996年)← Caml、Standard ML、[[Modula-3]]
'''[[OCaml]]''' (1996年)← Caml、Standard ML、[[Modula-3]]


: ML派生、静的型付け、先行評価、オブジェクト指向
: ML方言、静的型付け、先行評価、オブジェクト指向


'''[[Scala]]''' (2003年)← Scheme、Standard ML、Haskell、Erlang、[[Smalltalk]]、[[Java]]
'''[[Scala]]''' (2003年)← Scheme、Standard ML、Haskell、Erlang、[[Smalltalk]]、[[Java]]
141行目: 186行目:
[[F Sharp|'''F#''']] (2005年)← Standard ML、Haskell、Erlang、Scala、[[Python]]、[[C♯]]
[[F Sharp|'''F#''']] (2005年)← Standard ML、Haskell、Erlang、Scala、[[Python]]、[[C♯]]


: ML派生、静的型付け、先行評価
: ML方言、静的型付け、先行評価


'''[[Clojure]]''' (2007年)← Scheme、Haskell、Erlang、[[Java]]
'''[[Clojure]]''' (2007年)← Scheme、Haskell、Erlang、[[Java]]

2021年1月13日 (水) 15:08時点における版

関数型言語: functional language)は、関数型プログラミングのスタイルまたはパラダイムを扱うプログラミング言語の総称である。関数型プログラミングは関数定義と関数適用を基礎にした宣言型プログラミングの一形態であり、関数は引数への適用から先行式の評価を後続式の適用につなげて終端の評価を導き出すツリー構造として定義される。式の評価に伴う副作用の発生には大きな注意が払われる。関数は引数ないし返り値として渡せる第一級オブジェクトとして扱われる。

関数型プログラミングは数理論理学と代数系をルーツにし、ラムダ計算コンビネータ論理を幹にして構築され、LISP言語が実装面の先駆になっている。関数の数学的な純粋性を指向したものは純粋関数型言語と個別に定義されている。命令型プログラミング言語では単に有用な構文スタイルとして扱われている事が多い。高階関数第一級関数カリー化クロージャ継続イテレータジェネレータ再帰型推論パターンマッチング名前渡し遅延評価コンス代数的データ型型の多相イミュータブルモナドなどが関数型プログラミングの様式項目として挙げられる[誰?]

一般的な関数型スタイル

最も身近な関数型プログラミングとは、データ集合に対する反復作用であり、リスト処理などと呼ばれているものである。手続き型言語やオブジェクト指向言語において、いわゆる関数型と呼ばれる構文が多用されるのもリスト処理の分野である。関数型思想の原点は「LISP」であるが、その実用性を知らしめた最初の言語は表計算処理に効率性を発揮した「APL」であった。リストを走査して各要素を順々に取り出すプロセスと、各要素に作用するプロセスを別々の関数にまとめて、前者に後者を渡すようにした仕組みが一般に言われる関数型の基本例である。他の関数を引数として受け取る事ができる関数は高階関数と呼ばれ、引数として渡す事ができる関数は第一級関数と呼ばれる。この二つの機能が関数型の支柱である。そのようなスタイルとしての意味での関数型プログラミングにおける代表的な機能または構文には以下のようなものが挙げられる。

ラムダ式 / 無名関数 / クロージャ

ラムダ式と無名関数は同じものである。無名関数は引数→式(例:x→x+1)の形式で表現され、与えられた引数を加工して結果値を返す働きをする。高階関数への引数として使われることが多い。無名関数の式内に外部データを含んだものはクロージャと呼ばれる。クロージャの結果値はその時の外部データの状態に左右される事になる。

map / filter / reduce

リスト処理用の高階関数であり、対象リストと無名関数を引数にする。mapはリスト内の各要素を無名関数の結果値に置き換える高階関数である。filterはリスト内の各要素を無名関数の真偽判定値で真なら抽出し、その抽出要素のリストを生成する高階関数である。reduceはリスト内の各要素の総和の結果値を生成する高階関数である。reduceの無名関数は前要素までの総和と現要素の二引数を取る。総和の和は和に限らず無名関数内で好きな計算にできる。

名前渡し / 遅延評価

引数を当てはめた無名関数(コードブロックまたはプロセス)を未計算のまま高階関数に渡せる仕組みを名前渡しという。予め組み立てた想定プロセスを全て高階関数に渡しておき、その高階関数側で必要になったプロセス結果値だけを求めるようにして計算量を減らすのが主な用途になる。引数確定時とは別タイミングで計算することを遅延評価という。遅延評価では高階関数側で無名関数の確定引数を設定し直したり、クロージャならばその時の計算タイミングの外部データ状態に従った結果値を得ることが可能になる。

型推論

命令型プログラミング言語での型推論は、ローカル変数の型宣言/型注釈を省略することで表現に幅を持たせるための糖衣構文に近い機能と考えてよい。型テンプレート的な表現の幅である。リテラル(数値/実数/文字列)および文脈上で型が明確なインスタンスの初期代入は、同時に対象変数の型注釈になると再考されたことに基づいている。従来の明示的型付け英語版(型宣言/型注釈の使用)と型推論の共存は、C言語世代プログラミングに対する一つのパラダイムシフトでもある。

特徴

ここでは関数型プログラミング本来の考え方(パラダイム)に基づいて説明する。ステートメントを基本文にする命令型言語と、を基本文にする関数型言語はどちらも最終的には命令型パラダイムに沿った機械コードに落とし込まれる事になるが、双方の間にはプログラミングに対する考え方に比較的大きな隔たりがあると言える。

式と関数

関数型プログラムの基本文はexpression)である。式は個体(individual)である値(value)と写像(mapping)である関数(function)の二つから構成される。関数の定義には演算子operator)も含まれている。値は基本データ型(プリミティブ)と複合データ型(コンポジット)英語版およびラムダ計算で言われる変数(variable)を意味する。変数は束縛変数自由変数を指す。評価(evaluation)される前の式は、ラムダ計算で言われるネーム(name)と同義になる。ネームは数学上の数式または代数式に相当するものである。式内の変数部分が確定される前の式はラムダ抽象(abstraction)と同義になる。式内の変数部分を確定するのはラムダ適用(application)と同義になる。この式=ネームが評価されると値になり、これはラムダ計算で言われる簡約(reduction)と同義になる。式は値と同一視されるのですなわち式と値は相互再帰の関係にある。式内の値は他の式の評価値である事があり、その式内にもまた他の値があるといった具合である。この解釈は高階述語論理と呼ばれる。高階述語論理=高階関数の解釈下で引数または返り値として扱われる関数は第一級関数と呼ばれる。

関数型プログラミングの関数は’’関数の型’’(function type)で分類される存在量の値である。プログラム的には式に引数を結び付ける機能であり、これは関数を引数に適用する(applying a function to an argument)とされる。関数の式内の仮引数(parameter)箇所に渡された実引数(argument)がパターンマッチング手法で当てはめられ、先行(その時)または遅延(その後)タイミングで評価されて結果値が導出される。この仮引数箇所は束縛変数と呼ばれる。関数呼び出し時とは異なるタイミングで内容が決定される変数箇所は自由変数と呼ばれる。letとwhereで特定の式に向けて定義される変数は、その式への束縛変数になる。関数型での自由変数の意味合いは他の宣言型パラダイムとは異なっている。パターンマッチング手法は、関数にそれぞれ異なる引数パターン候補の選言列挙を可能にさせておりこれは関数オーバーロードと同義の機能になる。パターンマッチングは非交和型による等価性(equivalent)区別と、それ以外の等値性(equality)区別では引数値の組み合わせ照合とそれにワイルドカードを用いた部分的総称化照合で行われ、更にそれにガードと呼ばれる値の比較照合と範囲照合を加えることもできる。渡される実引数によってはボトム型になる関数もありこれは部分関数(partial function)と呼ばれる。ボトム型は式ないし関数の評価の失敗した終着点を意味する。演算子はデフォルトの式内容を持ち、その引数が単項演算子なら1個、二項演算子なら2個に限定された関数と同義である。

’’関数の型’’は「第1引数の型→第x引数の型→評価値の型」というように形式化されておりこれはカリー化(currying)と呼ばれる。例として関数funcの型をfunc::A→B→Cとするとこの場合、A型値に適用されたfuncはB→Cという’’関数の型の値’’を返す事になり、それをB型値に適用するとC型の評価値が返る事になる。左からの引数にひとつひとつ適用する形にして、B→Cのような中間的な’’関数の型の値’’が導出されるようにする仕組みが関数のカリー化である。カリー化は写像の量化quantify)を扱う二階述語論理の実装である。カリー化によって関数funcの型はfunc::A→(B→C)と読み替えられるようになり、この場合にAにのみ適用してB→Cという’’関数の型の値’’のまま保留することは部分適用(partial application)と呼ばれる。またカリー化による重要概念に関数合成(function composition)がある。これは合成演算子.(専用の二項演算子)を関数f::B→Cに適用すると(*→B)→(*→C)が導出され、それを関数g::A→Bに適用すると(A→B)→(A→C)となり関数f . g::A→Cが導出されるというものである。合成演算子の左側の定義域と右側の値域が同じ型の場合のみ合成できる。高階関数的な連結であるf (g A)と働きかた的には同じであるが、パイプライン処理の方に該当する関数連結(関数チェーン)と、カリー化に則った関数合成は異なる概念である。カリー化による部分適用や合成演算子から導出された’’関数の型の値’’を任意の変数に束縛して扱うのはポイントフリースタイル(point-free style)と呼ばれる。ポイントフリースタイルの変数を値に適用すると、他の値が返されるか又は他の’’関数の型の値’’が返される事になる。引数を部分適用された演算子はセクションと呼ばれてポイントフリースタイルでよく用いられる。カリー化準拠の’’関数の型’’は型理論の指数型(quotient type)に分類されるものである。

関数は名前付きと名前無しの二通りある。名前無しの関数は専らラムダ抽象を模した構文で定義される。式内に自由変数を内包しない方は単に無名関数と呼ばれ、自由変数を内包する方はそれを囲い込むという意味でクロージャと呼ばれる。自由変数は外部データへの接点になる。無名関数は引数をピュアマッピングする純粋関数である。クロージャの引数のマッピングは式内の自由変数に影響され、またその自由変数に作用する事もあるという副作用要素を閉包した非純粋関数である。リスト処理時にリストの各要素への作用子として渡される無名関数またはクロージャはイテレータと呼ばれる。同様にリスト処理時に渡されて各要素を参照しながらそれらの総和値または選別リストまたは更新リストを生成する方はジェネレータと呼ばれる。これはイミュータブル重視時に多用される。関数の名前は、それに結び付けられた式または式ツリーの不動点の表現になる。自式の不動点を式内に置いて新たな引数と共に高階述語論理の式として評価する手法は再帰と呼ばれる。関数の終端式での再帰は実引数の更新+先端式へのアドレスジャンプと同等に見なせるのでもっぱらそちらに最適化されてこれは末尾再帰と呼ばれる。末尾再帰は論理性を損なわずにスタックフリーの無制限ループを可能にする実装概念として重視されている。

値とデータストラクチャ

関数型プログラミングの値(value)は型(type)で分類される定数または全称量変数である。これは基本データ型(プリミティブ)と複合データ型(コンポジット)英語版のいずれかで表現される。プリミティブは数値、論理値、文字値、文字列を指す。様々なプリミティブを様々な形式で組み合わせたものがコンポジットであり、その例はC言語の構造体共用体などである。その組み合わせ方に焦点を当てた用語がデータストラクチャdata structure)である。データストラクチャという概念には再帰構造、アノテーション付き構造、ガード付き構造、操作的意味付き構造といった様々な暗黙情報を含められるので、コンポジットの具体的形式といった意味で用いられる。関数型言語で用いられるデータストラクチャの代表は代数的データ型S式である。双方ともデータ構築子(data constructor)から構築される。まず、プリミティブがデータ構築子によってまとめられる。正確ではないがデータ構築子はC言語の構造体または共用体と同じものと見てよい。データ構築子は入れ子にできるので、データ構築子をまとめたデータ構築子も定義できる他、同名データ構築子を入れ子にした再帰構造も定義できる。プリミティブとデータ構築子を任意に組み合わせて代数的データ型やS式といったデータストラクチャが構築される。データストラクチャ内のプリミティブとデータ構築子の組み合わせ方はパターン(pattern)と呼ばれる。そのパターンが型になり、パターンの構築が型付けになり、パターンを量化quantify)すると型付け値になり、これはターム(term)と呼ばれる。タームは冒頭の値(value)を指す。データ構築子のパターンの末端は必ずプリミティブになるので、パターン内の全てのプリミティブの値を決定することが量化になる。お互いのパターンがマッチするターム同士は等価(equivalent)とされる。この等価は同じ型と読み替えてもよい。等価性はあらゆる計算の可否(計算可能性)を決定する。計算とは関数適用または演算子適用を指し、それらが求める仮引数と実引数にするタームが等価であればその計算は成立する事になる。データストラクチャのパターンは基礎パターンに分解されて解釈される。基礎パターンは型理論に従って直積型、非交和型、ユニオン型、オプション型、帰納型、ユニット型などに分類されている。

S式二分木構造のデータストラクチャである。これはコンス(cons)と呼ばれる二項のデータ構築子の連結で形成される。コンスは二つの要素を持つタプルであり、要素はプリミティブまたは他のコンスのどちらかである。S式はコンスを実行時に連結して任意のパターンを構築する動的型付けの値である。コンスは要素二つの直積型product type)であり、コンスの連結による要素の並びはリストと呼ばれる。コンスの要素は形式化されていない非交和型sum type)でもあり、要素の識別はプログラマ側の裁量に委ねられている。コンスの組み合わせによるパターンは任意の識別名に結び付けられる。

代数的データ型AND-OR木構造英語版のデータストラクチャである。これは直積型product type)または非交和型sum type)を表現する多項のデータ構築子の組み合わせで形成される。データ構築子は任意個数の要素を持つものであり、要素はプリミティブまたは他のデータ構築子のどちらかである。代数的データ型はデータ構築子を事前に組成定義して任意のパターンを構築する静的型付けの値である。直積型はタプルまたはレコードのパターンを表わす。レコードは指定フィールド取得用関数を随伴させたものである。非交和型は列挙型またはタグ共用体のパターンを表わす。前者は等値性(equality)で識別される非交和である。後者は等価性(equivalent)で識別される非交和であり、こちらはユニオン型(union type)とも呼ばれる。ユニット型(unit type)は空集合のパターンを表わし、実装面ではnilまたはvoidの表現になる。ユニット型とそうでない型の二択の非交和型はオプション型(option type)とされ、実装面ではMaybe値の表現になる。データ構築子を再帰的にネスティングするパターンは帰納型(inductive type)とされる。非交和型と帰納型とユニット型の組み合わせは連結リスト二分木のパターンを表わす。データ構築子の組み合わせによるパターンは任意の型構築子(type constructor)に結び付けられて同時にそれが識別名義になる。データ構築子がパターンの表現に用いられるのに対して、型構築子はパターン内の要素(プリミティブないしデータ構築子)の多相化に用いられる。多相化はパターン内の要素を型変数(type variable)に置き換え、型構築子への型引数(type parameter)で要素の型を決定するという形で行われる。型構築子が必要とする型引数の個数および形態によるパターンはカインドkind)と呼ばれる。型構築子はカインドによって分類される。代数的データ型は識別名義と構成内容を分離して双方を自由に組み合わせるという意味でしばしば抽象化される。これは型構築子名に他の型構築子名を結び付ける仕組みで実現され、型シノニムまたは型エイリアスと呼ばれる。

評価戦略

関数型プログラミングの評価戦略evaluation strategy)は、関数を値にする評価タイミングと、引数欄内関数の評価タイミング(call-by-What)の二つを定義している。関数を値にする評価タイミングは、正格評価(strict evaluation)と非正格評価(non-strict evaluation)の二つに大別されている。正格評価の関数は引数確定と同時に評価されて値になる。この評価タイミングに注目した方は先行評価eager evaluation)と呼ばれる。引数確定と同時にボトム型(評価失敗)が発生することも包括した呼称が正格評価である。非正格評価の関数は、引数確定されても未評価のまま保留状態にされる。後続式で改めて他の関数/演算子の引数にされた時に初めて評価されて値になり、または改めて変数に束縛された時に初めて評価されて値になる。この評価タイミングに注目した方は遅延評価lazy evaluation)と呼ばれる。評価されるまでボトム型の発生が保留されることも包括した呼称が非正格評価である。これが遅延評価のデフォルトタイミングであるが、好きなタイミングで遅延評価できる無名関数/クロージャもあり、それは継続continuation)と呼ばれる。その任意タイミングの評価値導出はcall/cc(現行継続呼出)と呼ばれる。遅延評価は必要以外の評価をスキップして処理を高速化するが、評価値と未評価関数の区別が難しくなるというジレンマがある。

引数欄内関数の評価タイミング(call-by-What)には、値渡し(call by value)と名前渡し(call by name)がある。値渡しは先行評価に相当するものであり、関数の評価値が引数として渡される。名前渡しは遅延評価に相当するものであり、未評価のまま保留された関数が引数として渡される。なお、双方ともに引数確定されていない場合はただの第一級関数(関数の型の値)として渡されることになる。また名前渡しの亜流に必要渡し(call by need)があり、これは一度名前渡しされた関数+引数はその評価値をメモ化されて、同じ関数+引数が再度名前渡しされた時はそのメモ化評価値の方を渡すという仕組みである。必要渡しは純粋関数型言語で実装されている。

データストラクチャでも遅延評価の概念は扱われており、帰納再帰無限極限といった代数表現の実装手段になっている。代数的データ型ではタグ共用体連結リスト再帰データ型は遅延評価対象である。連結リストは無限リストと構造上同義であり遅延評価が無限性質の実装を可能にしている。

参照透過性

参照透過性referential transparency)とは、関数は同じ引数値に対する同じ評価値を恒久的に導出し、その評価過程において現行計算枠外の情報資源に一切の影響を及ぼさないというプロセス上の枠組みを意味する。現行計算枠外のいずれかの情報資源が変化するのと同時にいずれかの関数の評価過程も変化してしまう現象が副作用side effect)と呼ばれる。参照透過性=副作用の排除でもある。副作用を持たない関数を純粋関数(pure function)と呼ぶ。副作用の代表例は値の再代入と入出力処理である。参照透過性が完全順守されたプログラムでは、あらゆる個体(値)と写像(関数)のつながりが初期宣言値まで遡れるようになる。宣言値からのあらゆる値をつなぐ写像の履歴の図表であるプロセス有向グラフの解析と模型化は、プロセス代数と呼ばれ並行プログラミングなどの支柱になる。関数型プログラミングの世界で値の再代入がタブーとされるのは、それが写像の履歴の改ざんになってプロセス有向グラフの整合性を崩壊させるからである。従ってある時点の値をただ書き留めておく束縛変数と、旧値の更新を新値の産出で代替したイミュータブルが重視される。ループは関数の再帰で表現され、分岐は選言パターンマッチングなどで表現される。参照透過性を維持しながら入出力処理を行うための機能には、派生構造型システム(substructural type system)とモナドmonad)がある。

参照透過性が保証されたプロセス有向グラフは、プルーフアシスタント英語版によるプログラム正当性形式的検証および数学的証明を可能にする。参照透過性を完全順守するには、各種入出力に伴う副作用の論理的排除も必要なので専用のランタイム環境上での動作が必須になる。ランタイム環境は「コンテキスト」を走行プログラムとの仲介にする。プログラムは専用IDを内包するコンテキストに作用するという形式で各種入出力を行う。コンテキストへの仮想的入出力は、ランタイム環境側によって実際に実行される。その入出力で変化したランタイム環境が反映された新生IDを内包するコンテキストがプログラム側に渡される。コンテキストIDが毎時ユニーク生成される仕組みは、派生構造型システムのライナ―型(linear type)と呼ばれる。コンテキストに対象値を注入する仕組みはアフィン型(affine type)、コンテキストから対象値を抽出する仕組みは関連型(relevant type)と呼ばれる。毎時ユニーク生成されるライナー型IDは、各種入出力に伴う副作用によって実際には変化しているランタイム環境の時系列状態を完全に抽象化して、それらを理論上各個照会可能にしているマッピングキーである。これによってランタイム環境の変化もプロセス有向グラフで論理的に辿れることになるので同時に参照透過性も維持されていることになる。派生構造型システムの実装例にユニークネス型(uniqueness type)がある。ライナー型、アフィン型、関連型を組み合わせての特にその応用コーディングは煩雑なボイラープレートコードになりがちだったので、それらを圏論視点の関手の合成といった仕組みでより平易かつ簡潔にした手法がモナドである。

型システム

関数型プログラミングの型システムtype system)は、型付けラムダ計算準拠の型理論に基づいて構築されている。ここでは型システム上の対比に沿った形で記述する。関数型言語の二大系統の内、ML系静的型付けベースであり、LISP系動的型付けベースである。

静的型付け

関数型言語の静的型付けでは、性質や役割による意味づけによって値を分類する明示的型付け(manifest typing)よりも、計算可能性に基づく等価性によって値を分類する推論的型付け(inferred typing)が主流である。前者の意味づけとはプログラマによる型定義、型宣言、型注釈を指しており人間寄りの視点である。後者の等価性とは値を関数/演算子の引数にできるかどうかの判別を指し、値への関心がそこで計算可能かどうかに絞られているので計算機寄りの視点である。明示的型付けではソースコード上の型宣言と型注釈から値の型が特定されるのに対し、推論的型付けでは型推論機能で特定される。型推論とはソースコードの解析によって値それぞれの等価性を導き出す機能である。数値や文字列といったリテラルはそのまま特定され、変数などのシンボルはその扱われ方や、任意の等式を並べて定義した法則からの分析によって型(=等価性)が特定されるといった具合である。推論的型付けでは値への関心をその計算可能性に絞っているので、型宣言と型注釈は必要とされなくなる。例としてint型を型シノニムで金額型と数量型にした場合、明示的型付けではこの両者は区別されるが、推論的型付けでは区別されない。ソースコードの解析でどちらもint型準拠の等価と見られるからである。推論的型付けで値の意味づけ性も表現する場合は、データ構築子で値を包むボックス化が用いられる。データ構築子(data constructor)は与えられた要素を直積または非交和でまとめるのと同時に型理論で言われる文脈(context)を各要素の等価性に上乗せ付加するものでもある。

静的型付けにおけるデータストラクチャのパターン(型)はコンパイル前ないし実行前に全て事前形成される。その実装例である代数的データ型はデータ構築子の組み合わせでパターンを構築し、パラメトリック多相に基づいて総称化したパターン内の要素=型変数を、型構築子への型引数の組み合わせで特定した。Hindley–Milner型体系はこのパラメトリック多相に対応した型推論機能を提供している。型構築子(type constructor)は必要とする型引数の個数によって分類され、これはカインドkind)と呼ばれる。カインドは総称記号であるの写像で型構築子の型種を表現する。型引数を必要としない型構築子と必要な型引数を全て付与された型構築子はプロパータイプと呼ばれと表現される。プロパータイプは全称量の型である。型引数を1個必要とするものは*→*になり、2個必要なら*→*→*になる。これらは存在量の型になる。*→*→*に型引数が1つ付与されると*→*になり更に1つ付与するとのプロパータイプになる。全称量の型付け値(ターム)は普通に扱えるが、存在量の型付け値はその一部分が抽象化(大抵は環境依存値と同義)されたままの特別な値と見なされて一定の制限下で扱われる。

推論的型付け下の関数の扱いでは、人為的表記による意味づけを重視した記名的型付け(nominal typing)が取り入れられており、これで推論的型付けの枠組み内での関数オーバーロードが表現されている。ここでの人為的表記による意味づけとは、型構築子/データ構築子/関数の型それぞれのパターン内の型変数に、型理論で言われる文脈(context)を付加することを指している。文脈の付加は制約(constraint)と呼ばれる。文脈の付加はアドホック多相と考えられており、代表的な実装例はそれとジェネリックプログラミングを組み合わせた型クラスである。型クラスは、引数/計算値/評価値などを総称型化したジェネリック関数群を定義できる機能であり、同時に推論的型付けと共存する関数オーバーロードの実装と、特定の意味づけ型を扱うための関数モジュールを定義するための手段になっている。型クラスの定義構文では上述のジェネリック関数群が定義され、その型クラス名が文脈記号になる。型構築子の定義に文脈を付加すると、その型クラスのジェネリック関数群にその型構築子=型を当てはめた関数群がコンパイル時に自動生成される(deriving)。また文脈を付加して当てはめ関数群を自動生成(instance)した上で、その型構築子=型のための当てはめ関数も個別定義(where)できる構文もある。この双方がジェネリック関数の特有インスタンス化になる。明示的型付けでは型注釈を付けた引数パターンの列挙というシンプルな手段で関数オーバーロードを表現できるが、推論的型付けでは等価性に上乗せした文脈という二段階の手段が必要になる。記名的型付けと併せた推論的型付けでのオーバーローディング関数の選択決定は、始めに仮引数と実引数の型クラスのみに注目した照合が行われ、次にその型クラスの制約内での型推論照合が行われるという形になる。

動的型付け

動的型付けにおけるデータストラクチャのパターン(型)はコンパイル前ないし実行前の事前形成に加えて、実行中の随時にも事後形成できる。その実装例であるS式は、二項データ構築子(コンス)の実行時の連結で形式化されていないパターンを構築し、プログラマの裁量による任意の実行時チェックでパターンの意味づけと計算に用いるための等価性を判別するといったものである。パターンの組み合わせが明確に形式化されておらずその識別をプログラマの裁量に委ねており、またチェックタイミングも委ねられている事から、これは潜在的型付け(latent typing)と呼ばれている。潜在的型付けは動的型付けの原型的位置づけである。

もう一つの実装例として動的なレコード(record)がある。この動的レコードは内部的には動的配列と同じものであり、配列の各スロットに任意の値の参照が納められて、そのスロットは構造体のフィールドと同じものになる。スロットは増設削減可能である。レコードのタグ名はそのまま型名になる。レコードを量化した値(インスタンス)には、システム側が別途用意する型情報が結び付けられており、変数への束縛ないし代入および関数/演算子への引数代入時に毎回自動的に型判別される。型情報と型判別タイミングが形式化されているのでこれは動的型付けとなる。動的型付けのインスタンスを関数の引数にすることは動的な関数オーバーロードを自然表現し、これはオブジェクト指向に倣って多重ディスパッチとも呼ばれる。レコード・フィールドのアクセスは、フィールド名関数をインスタンスに適用するという方法で行われる。オブジェクト指向のinstance.fieldが関数型ではfield instanceのようになる。同じフィールド名関数から得られる値の型は、適用するインスタンスの型構造による実行時多態になる。この仕組みは構造的型付け(structural typing)に沿ったものである。

モナド

A monad is just a monoid in the category of endofunctors, what's the problem?
(モナドは自己関手の圏のただのモノイドだよ。何か問題でも?) — Philip Wadler

モナドmonad)の説明でよく引用されるこの文言はその特徴を明快に表したヒントと言われる。モナドは圏論由来の自己関手の合成の仕組みで参照透過性を維持しつつ、代数的構造由来のモノイドの仕組みで非純粋関数の連結体を平易に表現する機能である。非純粋関数の連結体がそのまま一連の副作用内包プロセスになりそれを参照透過性の枠内で実行できる。モナドはプログラム的には、関数の量化を扱う二階述語論理の実装であるカリー化の活用形態である関数合成と部分適用の応用手法であり、参照透過性欄で説明した派生構造型システムのライナー型の役割をに見立てたデータ構築子に持たせている。またデザインパターン的には、関数を引数値に適用する(applying a function to an argument)通常の関数とは正反対に、モナドでは値を関数に適用する(applying a value to a function)形態を取っており、値を同名関数に反復適用しての特殊な再帰を表現できる。モナドでは値に特殊な演算子を適用することでそれを関数に適用できるようにしている。

モナドの世界では、基本値から導出されるモナド値をモナド関数に次々と適用して状態遷移を表現する。モナド値(monadic value)とはMaybe値、例外発生、入出力環境、システムコール、クロージャ、継続といったあらゆる副作用プロセスを扱うためのオブジェクトである。モナド関数(monadic function)とはそのオブジェクトのメソッドと考えてよいものである。モナド値とモナド関数は合成演算子を通した表裏一体の存在であり、これがモノイドを指している。合成演算子をモナド値に適用したものをモナド関数に適用して導出されたモナド値を、また同じ手順でモナド関数に適用するといった繰り返しになる。これはモナド合成体(monadic composition)と呼ばれる。モナド値はMAのように型表現され、Aは基本値、Mは基本値を包むコンテキストまたはコンテナである。モナド関数は(A→MB)を基本とする関数の型の値であり、与えられた基本値からモナド値を操作して新たなモナド値を返す。モナド値はMAの型を基本とし、対象内容によってM(A?)M(A+E)M(W×A)E→MAS→M(A×S)(A→MR)→MRといった型の値または関数の型の値にリフト(lift)される。これはモナド変換子(monad transformer)と呼ばれる。また、モナド値のMAMを空データにして事実上のAにしモナド関数も事実上の(A→B)にした恒等モナド(identity monad)もあるがこれは全くの便宜目的である。モナド値は状態遷移の記録媒体であり、η自然変換演算子を基本値に適用することで導出される。基本値+αから成るモナド値または基本値を包含するモナド値はデータ構築子として表現されて自己関手の圏の枠組みとなり、そのデータ構築子を束縛した型構築子への型引数でモナド値内の型決定がなされる。モナドは大まかに言うと以下の六つの要素から実装されている。

  • モナドの文脈を付加された型構築子。一つの副作用内包プロセスを扱う関数群モジュールに見立てられる。
  • 基本値+αのコンテナであるモナド値=データ構築子。圏に見立てられる。
  • μ自然変換演算子(join)kleisli-star拡張演算子(bind)といった合成用の二項演算子。
  • 基本値とη自然変換演算子(return)とモナド値。モナド値+二項演算子でモノイドに見立てられる。
  • モナド関数。パターンマッチング分岐可能でモジュール内の操作を一手に扱う。自己関手内容に見立てられる。
  • ファンクタ文脈からの持ち上げ演算子(fmap)は補助的機能。関手に見立てられる。

モナド値は付加モナドと自由モナド(Maybe/例外/有限リストモナドなど)以外では、実質的に存在量の値になるので普通の値のように扱うことは出来ない。ただし付加/自由モナドでも参照透過性を維持するためには存在量と同等に扱う必要が出てくる。returnを基本値に適用してモナド値を表現することからモナド処理は始まる。基本値とは扱うモナドに合わせた任意の値である。そのモナド値は圏としてのユニークIDを持つことになる。ここで基本値をAとしそのモナド値をMAとする。MAにbindを適用して(A→MB)→MBという写像を導出する。その写像は先のMAと同じ圏IDを備えたものになる。その写像をモナド関数(A→MB)に適用すると、そのモナド関数内では渡されたAやその他の値などにreturnを適用して表現されるモナド値の圏IDはMAのもので共通化される。モナド関数内においてのreturnは基本値をモナド値に代入する機能と見てよい。returnは用途別関数にそれぞれラッピングされて使われるのが普通である。空引数からモナド値を表現するreturnもありこれはモナドプリミティブ(monadic primitive)と呼ばれ、この場合はモナド値の圏IDが暗黙引数になっている。モナド値はファイルハンドルのようなものと考えると分かりやすくなり、モナド値を直接引数にできる専用関数も存在する。モナド関数内ではモナド値から基本値を取り出す演算子が有効になる。それはA←MAのように表現されてコモナド(comonad)と呼ばれる機能になる。抽出した基本値からの処理の中で再度returnが行われる。モナド関数は自己関手内容に見立てられているので、その中ではreturnの繰り返しによる事実上の再代入処理が許されている。その論理的な辻褄合わせの要点になるbindの正当性および計算可能性を表現するためにファンクタ則とモナド則の等式がプログラム内で定義されている。ここでいわゆる圏論の知識が必要になるがその説明は先送りする。モナド関数はモナド値を返しそれに再度bindを適用できるのでこれがモノイドを意味している。モナド関数の外でのreturnは毎時ユニークな圏IDのモナド値を表現するので同じ基本値でもその都度異なる圏が表現される事になり、これが自然変換関手圏)演算子の呼称由来になっている。

モナドはファンクタfunctor)の派生文脈にされることが多いが、これはbindを形成するクライスリ射とjoinの合成の持ち上げ(関手)にfmapが使われるからである。ファンクタ文脈は関数fmapを持つ。そのままファンクタの機能名で呼ばれることが多いfmapは、関数(A→B)から関数(TA→TB)を導出する関手=関数である。この関数はTAに適用できてTBを導出できる。Tは基本値を包むコンテキストまたはコンテナでありその代表例はリストである。基本値に対する作用をコンテキストで拡張解釈できるのがファンクタの利点である。例えば基本値への+1という作用をリストのコンテキストで拡張解釈するのはリストの全要素に+1するという意味になる。これはリストをそのまま計算対象にできる利便性に繋がる。ファンクタの派生文脈にアプリカティブapplicative)がある。アプリカティブは、ファンクタのコンテキストに包まれた関数を「コンテキストに包まれた先頭引数→コンテキストに包まれた残り引数&評価値」という1引数の関数に変換する演算子<*>を持つ。<*>F(A→B)から(FA→FB)を導出する演算子である。Fはコンテキスト、(A→B)は元の関数、(FA→FB)は1引数の関数である。このBは多相であり実際は値関数(*→*) 関数(*→*→*)などになっている。アプリカティブは、2個以上の引数の関数をファンクタするための機能と考えてよい。2個以上の引数の関数はfmapでそのまま持ち上げられないのでアプリカティブ関手のpureが用いられる。これはA→FAと表現されAが関数、Fがコンテキストである。pureによって好きな引数個数の関数をコンテキストで包み<*>をそれに適用して導出された関数をFAに適用できる。アプリカティブ関手pure::A→FAとモナドのη自然変換演算子return::A→MAは同じ働きに見えるが、前者は関数(関数の型の値)を純粋に持ち上げるだけの関手なのに対して、後者は持ち上げる関手を毎時垂直合成していく関手圏自然変換であるという性質上の違いがある。

歴史

1930年代に数学者アロンゾ・チャーチによって発明されたラムダ計算関数適用を計算単位にした形式体系であり、1937年に数学者アラン・チューリング自身によりチューリング完全の性質が明らかにされて、チューリングマシンと等価な計算模型である事が証明されている。この経緯からラムダ計算は関数型プログラミングの基底に据えられた。ラムダ計算と同等の計算理論コンビネータ論理があり、1920年代から1930年代にかけて数学者ハスケル・カリーらによって発明されている。こちらは関数型プログラミングの原点である高階述語論理式の基礎モデルにされた。チャーチはラムダ計算を拡張してその各タームに型を付与した型付けラムダ計算も考案しており、これは関数型プログラミングにおける型理論型システムの源流になった。

1950年代

初の関数型プログラミング言語とされる「LISP」は、1958年にマサチューセッツ工科大学の計算機科学者ジョン・マッカーシーによって開発された。LISPの関数はラムダ計算の形式を元に定義され再帰可能に拡張されており、式のリスト化とその遅延評価および高階評価など幾つかの関数型的特徴を備えていた。LISPは数多くの”方言”を生み出しているが、その中でも「Scheme」「Dylan」「Racket」「Clojure」「Julia」は関数型の特徴を明確にした言語である。1956年に公開された「Information Processing Language」の方が先駆であるが、こちらはアセンブリベースの低水準言語なので前段階扱いである。IPLが備えていたニーモニックコードのリストをオペランドにできるジェネレータ機能はLISPに影響を与えたと言われる。高階オペランド演算は高階関数と同じ働きをし、メモリ一括処理のストリング命令の効率を高めるなどした。

1960年代

1964年に計算機科学者ケネス・アイバーソンが開発した「APL」は、計算タイプを定義された関数記号に各種配列データを適用する機能を中心にした言語であり、特にスプレッドシート処理に対する効率性が認められて、1960年代以降の商業分野と産業分野に積極導入された。APLは多次元配列などのデータ集合に対する関数適用の有用性を特に証明した言語になった。そのデータ集合処理を注目されたAPLからは「J言語」「S」「A」「K」「Q」といった派生言語が生み出されている。APLの記号構文は一つの手本になりその流れは後年の「FP」から「Haskell」にも汲まれた。続く1966年に発表された「ISWIM」は手続き型と関数型を組み合わせたマルチパラダイムの原点的言語であり、ALGOLを参考にした構造化プログラミングに高階関数とwhereスコープが加えられていた。60年代の関数型プログラミングの歴史はもっぱらLISPの発展を中心にしていたが、ISWIMは後年の「ML」「Scheme」のモデルにされている。

1970年代

スタンフォード大学エディンバラ大学で実施された対話型自動定理証明プロジェクト「Logic for computable functions」の中で1973年に導入された「ML」は代数的データ型パラメトリック多相型推論などを備えた関数型言語であり、計算機科学者ロビン・ミルナーによって開発された。また、1975年にMIT人工知能研究所の計算機科学者ガイ・スティールと工学者ジェラルド・サスマンが設計してAIリサーチ用に導入された「Scheme」は任意タイミング評価(call/cc)可能な継続ガーベジコレクションを備え、レキシカルスコープで構造化が図られており末尾再帰を最適化していた。MLとScheme双方の登場は関数型プログラミングのマイルストーンになった。同年代に代数的データ型を初めて導入しクリーネの再帰定理を証明実装した「Hope」と、関数の数学的純粋性を初めて重視した「SASL」も発表されている。1977年、BNF記法FORTRAN開発の功績でこの年のチューリング賞を受けた計算機科学者ジョン・バッカスは「Can Programming Be Liberated From the von Neumann Style? -A Functional Style and Its Algebra of Programs-」と題した記念講演を行い、一説にはこれを境にして関数型(functional)というパラダイム名が定着したと言われているが、同時に発表された「FP」は関数水準(function-level)言語として紹介されている。ノイマン型からの脱却を題目に掲げたバッカスは、FPのプログラムをアトム+関数+フォーム(=高階関数)の階層構造と定義し、代数を用いるフォームの結合で構築されると提唱した。

1980年代

MLの開発者ミルナーが発表していた型推論アルゴリズムが1982年に証明されると、パラメトリック多相に対応した型推論機能を眼目にしたHindley–Milner型体系が確立されて代数的データ型の実用性が高められた。80年代に入ると共に方言が多様化していたLISPとMLの両コミュニティで一定の標準化が求められるようになり、1983年にHindley–Milner型体系を導入した「Standard ML」が発表された。それに対して1984年に発表された「Common Lisp」では手続き型パラダイムが強調されて関数型の枠組みからやや外れた方向性を示したので、関数型言語の枢軸はMLに置かれた。1985年にはML方言の代表格となる「Caml」が公開された。同じく1985年にSASLの後継として発表された「Miranda」は、遅延評価を標準にしながら関数の数学的純粋性を追求した言語であり、関数型プログラミング研究用オープンスタンダードのコンセンサスで1987年から策定が開始されたHaskellのモデルになりその進捗を大きく後押しした。それと前後してMirandaは1987年公開の純粋関数型言語「Clean」にも大きな影響を与えている。Cleanは後発のHaskellをも叩き台にして改良を続けた。また関数型と並行計算の適性が認識される中で1986年の通信業界で開発された「Erlang」は並行プログラミング指向の面で特に注目を集めている言語である。1988年公開の「Wolfram」はAPLスタイルのデータ集合処理に機能を豊富にしたパターンマッチングやイテレーションを加えた言語で90年代を通して改良が続けられていた。

1990年代

1990年に関数型プログラミングの第二のマイルストーンと言える純粋関数型言語「Haskell」が初リリースされた。Haskellは遅延評価と型理論の文脈を形式化した型クラスと圏論由来のデザインパターンであるモナドの導入を特徴にしていた。1992年に動的型付けレコードと多重ディスパッチを扱う関数型言語「Dylan」が登場した。1993年にベクトル行列表テーブルなどのデータストラクチャを扱えて統計的検定時系列分析クラスタリング分野に特化した関数型言語「R」が発表された。1995年にLISPのマクロ機能を大幅に強化したコンポーネント指向により各分野に合わせたドメイン固有言語として振る舞える「Racket」が登場した。1996年にはML方言のCamlにオブジェクト指向視点の抽象データ型を導入した「OCaml」が公開された。90年代の関数型プログラミングの歴史では関数の数学的純粋性に則った参照透過性の重視の他、オブジェクト指向との連携の模索が目立っていた。日本ではStandard MLに独自の拡張を施した「SML#」が発表されている。風変りなものにコンビネータ論理の形式に立ち返った「Unlambda」がある。1995年に公開された「Mercury」は関数型と論理プログラミングの合の子のような言語であり、自動推論分野への応用に特化されていた。

2000年代

2000年代になると関数型プログラミングへの注目度は更に高まり、マルチパラダイムに応用された関数型言語が様々に登場した。2003年のJava仮想マシン動作でオブジェクト指向と関数型を融合した「Scala」、2005年のマイクロソフト製のML方言「F#」、2007年のJava仮想マシン動作のLISP方言「Clojure」など数々のポピュラー言語が生み出されている。また、カリー=ハワード同型対応の理論に基づいたプルーフアシスタント英語版によるプログラム正当性の数学的証明を指向した関数型言語が支持され、2004年に「Epigram」2007年に「Agda」および純粋関数型「Idris」が発表されている。これらの言語では数学者マルティン・レーフによる直感的型理論英語版準拠の依存型を中心にした型システムが実現されている。関数型構文の有用性がより広く認識されるに従い、オブジェクト指向言語やスクリプト言語にも積極的に導入されるようになった。産業分野からも注目されるようになり、CSG幾何フレームワーク上で動くCADへの導入も始められた。しかし関数型コンセプトに馴染まないオペレーターが定数化規則による値の再代入制限に困惑して設計作業に支障をきたすなどの弊害も明らかになっている。

代表的な関数型言語

LISP (1958年)

動的型付け、先行評価

APL (1964年)

配列プログラミング言語、動的型付け、先行評価

ISWIM (1966年)← LISP、ALGOL

静的型付け、先行評価

ML (1973年)← ISWIM

静的型付け、先行評価

Scheme (1975年)← LISP、ISWIM

LISP方言、動的型付け、先行評価

FP (1977年)← APL

関数水準言語、動的型付け、先行評価

Standard ML (1983年)← ML、Hope、PASCAL

ML方言、静的型付け、先行評価

Caml (1985年)← ML

ML方言、静的型付け、先行評価

Miranda (1985年)← ML、Hope、SASL

純粋関数型言語、静的型付け、遅延評価

Erlang (1986年)← LISP、PrologSmalltalk

動的型付け、先行評価

Clean (1987年)← Miranda

純粋関数型言語、静的型付け、遅延評価

Haskell (1990年)← Scheme、Standard ML、Miranda、FP

純粋関数型言語、静的型付け、遅延評価

Dylan (1993年)← Scheme、CLOSALGOL

LISP方言、動的型付け、先行評価

R (1993年)← Scheme、CLOS

配列プログラミング言語、動的型付け、先行評価

Racket (1995年)← Scheme、Eiffel

LISP方言、動的型付け、先行評価

OCaml (1996年)← Caml、Standard ML、Modula-3

ML方言、静的型付け、先行評価、オブジェクト指向

Scala (2003年)← Scheme、Standard ML、Haskell、Erlang、SmalltalkJava

静的型付け、先行評価、オブジェクト指向

F# (2005年)← Standard ML、Haskell、Erlang、Scala、PythonC♯

ML方言、静的型付け、先行評価

Clojure (2007年)← Scheme、Haskell、Erlang、Java

LISP方言、動的型付け、先行評価

Rust (2010年)← Scheme、Standard ML、Haskell、Erlang、C♯

静的型付け、先行評価

関数型プログラミングの例

アルゴリズムのHello Worldと言えるフィボナッチ数を求めるプログラムは、チュートリアルなどでよく引き合いに出されるものであり、本稿でも手続き型言語との比較を兼ねて取り上げる。一般的な手続き型言語によるソースコードは以下のようになる。

FUNCTION fibona (num: INTEGER): INTEGER;
VAR
  x, y, tmp: INTEGER;
BEGIN
  x := 1;
  y := 1;
  FOR i := 2 TO num DO
  BEGIN
    tmp := x;
    x := y;
    y := y + tmp;
  END;    
  fibona := y;
END;

それに対して一般的な関数型言語によるソースコードは以下のようになる。

let rec fibona num = if num < 2 then 1 else fibona (num-2) + fibona (num-1)

コード行の羅列であるテキスト的な手続き型プログラミングと比較すると関数型プログラミングの方は、ガードとリミットによる分岐終点ルールで枠組みされたリーフ値と再帰関数のノードによるツリー化手順が一目で把握可能であり、ソースコードから式のツリー構造が直感的に浮かび上がってくる。同様のアルゴリズムで後続値とのペア(2-tuple)を表示するものは以下のようになる。

let rec fibona num =
  if num = 0 then (1, 1) else let (x, y) = fibona (num-1) in (y, x+y)
in
  fibona 5

result is (5, 8)

脚注

注釈

出典

外部リンク