コンテンツにスキップ

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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
削除された内容 追加された内容
m い抜き言葉「やってる」「してる」の使用を回避
式と関数
(同じ利用者による、間の34版が非表示)
1行目: 1行目:
{{独自研究|date=2014年4月}}
{{独自研究|date=2014年4月}}
{{プログラミング言語|index=かんすうかたけんこ}}
[[ファイル:Orange_lambda.svg|代替文=|境界|右|フレームなし|209x209px]]
[[ファイル:Orange_lambda.svg|代替文=|境界|右|フレームなし|209x209px]]
{{Template:プログラミング・パラダイム}}


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


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


== 特徴 ==
== 特徴 ==
{{出典の明記| date = 2020年5月6日 (水) 02:29 (UTC)| section = 1}}
ここでは関数型プログラミング本来の構文スタイルを元にして説明する。式を基本文にする関数型に対して、[[文 (プログラミング)|ステートメント]]を基本文にする[[命令型プログラミング]]言語では必要に応じて構文スタイルを変えて実装されている。代表的なのは「式に引数を適用する」に対する「関数に引数を渡す」である。値とその型付けに対するコンセプトおよびデータストラクチャの実装スタイルも異なっている。ただし双方ともアセンブリコード上では同様なものに符号化される。


=== 式と関数 ===
ここでは関数型プログラミング本来の構文スタイルを元にして説明する。式を基本文にする関数型に対して、[[文 (プログラミング)|ステートメント]]を基本文にする[[手続き型プログラミング|手続き型]]や[[オブジェクト指向プログラミング|オブジェクト指向]]などの[[命令型プログラミング]]言語では必要に応じて構文スタイルを変えて実装されている。代表的なのは「式の引数への適用」に対する「引数を関数に渡す」である。ただし双方ともアセンブリコード上では同様なものに符号化される。
関数型プログラムの基本文は[[式 (プログラミング)|式]](''expression'')である。式は値(''value'')と関数(''function'')で構成される。関数の定義には[[演算子]](''operator'')も含まれている。値は後節で述べる[[データ構造|データストラクチャ]]と、[[ラムダ計算]]で言われる変数(''variable'')の双方を意味する。データストラクチャの定義には数値、論理値、文字値、文字列といった基本データ型=[[プリミティブ型|プリミティブ]]も含まれている。変数は[[束縛変数]]と[[自由変数と束縛変数|自由変数]]を指す。評価(''evaluation'')される前の式は、ラムダ計算で言われるネーム(''name'')と同義になる。ネームは数学上の数式または代数式に相当するものである。式は、式内の変数部分が確定される前は評価できない[[ボトム型]]であり、これはラムダ抽象(''abstraction'')と同義である。式内の変数部分を確定するのはラムダ適用(''application'')と同義である。このネームが評価されると値になり、これはラムダ計算で言われる簡約(''reduction'')と同義である。式は値と同一視されるので、すなわち式と値は相互再帰の関係にある。式内の値は他の式の評価値である事があり、その式内にもまた他の値があるといった具合である。この仕組みは[[高階論理]]''と呼ばれる。''


関数も値と同一視される。関数は写像の型の値であるが、プログラム的には式に引数を結び付ける機能であり、これは式に引数を[[写像|適用]](''application'')すると呼ばれる。式内の仮引数(''parameter'')箇所に実引数(''argument'')が順次当てはめられ、式ツリーの終端式が評価値になる。引数によっては[[ボトム型]]になる関数もありこれは部分関数と呼ばれる。ボトム型は虚(''falsity'')と見なされており、式のツリーないし写像の連鎖の失敗した終着点になる。関数は、式に第1引数を適用したもの→第x引数を適用したもの→評価値、という形をとる。引数を1個ずつ適用する形態は[[カリー化]]と呼ばれる。2個以上の引数を同時適用する形態は非カリー化と呼ばれる。関数の型(''function type'')は「A→B→C」のように各引数値から評価値までの写像パターンで表現される。片方の評価値と片方の第1引数が同じ型の両関数は任意に連結して新たな関数にできる。この双方の写像のつなぎ合わせは関数合成と呼ばれる。カリー化された関数は引数の適用を途中で止めて残り引数を後から適用するように保留できる。この保留状態の関数の生成は部分適用と呼ばれる。任意のタイミングで遅延評価(''call/cc'')するために評価を保留してる関数は[[継続]]と呼ばれる。その応用に、一つの式を個々の演算子適用(関数適用)に分解して各個[[継続]]化し、それらをボトムアップで組み上げて一つの継続集合体を生成する[[継続渡しスタイル]]がある。部分適用と継続はネームと同義である。関数も当然ながら[[高階論理]]に組み込まれている。引数値または評価値として扱うことができる関数は[[第一級関数]]と呼ばれる。その第一級関数を扱うことができる関数は[[高階関数]]と呼ばれる。
値(''value'')は代数的データ型(''algebraic data type'')として表現される。代数的データ型は[[型理論]]にある様々なタイプの複合体であり、各タイプの表現代数式を各言語仕様に沿ったプログラムパーツで置き換えてあらゆる値を数学的に表現する仕組みである。代数的データ型は言わば「型の式」であり、その式パターンが「型」になり、式パターンの構築が「型付け」になる。結果的に全ての値は「型」で分類される事になる。代数的データ型の実装方法はそれを意識させない位単純なものから忠実なものまで言語ごとに様々である。代数的データ型は単体値を兼ねたあらゆる[[多重集合]]の表現になる。命令型言語での導入例はまず無くより平易で直感的な構造体やクラスが型付けに使われている。


関数は名前付きと名前無しの二通りある。名前無しの関数は専らラムダ抽象を模した構文で定義される。式内に自由変数を内包しない方は[[無名関数]]と呼ばれ、自由変数を内包する方はそれを囲い込むという意味で[[クロージャ]]と呼ばれる。自由変数は外部データへの接点になる。[[無名関数]]は引数をピュア[[写像|マッピング]]する純粋関数である。[[クロージャ]]の引数の[[写像|マッピング]]は式内の自由変数に影響され、またその自由変数に作用する事もあるという副作用要素を閉包した非純粋関数である。関数の名前は、それに結び付けられた式または式ツリーの[[不動点]]の表現になる。自式の不動点を式内に置いて新たな引数と共に[[高階論理]]の式として評価する手法は[[再帰]]と呼ばれる。関数の終端式での再帰は実引数の更新+先端式へのアドレスジャンプと同等に見なせるのでもっぱらそちらに最適化されてこれは[[末尾再帰]]と呼ばれる。末尾再帰は論理性を損なわずにスタック資源から離れた無制限ループを可能にする実装概念として重視されている。名前付き関数で、仮引数記述を省略したものはポイントフリーと呼ばれ、その省略箇所に先行式評価値が実引数として暗黙適用される。名前無し関数で、先行式評価値を実引数にする記述を省略して、その仮引数箇所に暗黙適用するのもポイントフリーと呼ばれる。この暗黙適用の式を並べて連鎖させる手法は[[パイプライン処理|パイプライン]]と呼ばれるが、言語によっては特別な演算子と併せて明示する。リスト処理時にリストの各要素に対する作用子として渡される第一級関数は[[反復子|イテレータ]]と呼ばれる。作用後の各要素を別の新生リストに向けて複製する働きを加えたものは[[ジェネレータ (プログラミング)|ジェネレータ]]と呼ばれる。これは[[イミュータブル]]重視時に多用される。イテレータはポイントフリーの無名関数、ジェネレータはポイントフリーのクロージャとして定義される事が多い。
=== 式と関数 ===
{{出典の明記|date=2020年5月6日 (水) 02:29 (UTC)|section=1}}
*関数型プログラムの基本文は[[式 (プログラミング)|式]](''expression'')である。
*式は、値(''value'')と演算子(''operator'')と関数(''function'')で構成される。値は[[束縛変数]]と[[自由変数と束縛変数|自由変数]]を包括する。式内の変数部分が特定される前の式は評価できない[[ボトム型]]存在である。特定後は[[評価戦略]]に従ったタイミングで評価(''evaluation'')されて式存在から値存在になる。
*式は値と同一視されるので上述の式と値は相互再帰の関係にある。式内の値は他の式の評価値である事があり、その式内にもまた他の値があるといった具合である。この仕組みは[[高階論理]]''と呼ばれる。''
*関数も値と同一視される。関数は式に引数を結び付ける機能であり、これは式の引数への[[写像|適用]](''application'')と呼ばれる。式内の仮引数(''parameter'')箇所に実引数(''argument'')が順次当てはめられ、式ツリーの終端式が評価値になる。
*関数は、式を第1引数に適用したもの→第2引数に適用したもの→第x引数に適用したもの→評価値、という形をとる。引数を1個ずつ適用する形態は[[カリー化]]と呼ばれる。2個以上の引数を同時適用する形態は非カリー化と呼ばれる。関数の型は「A→B→C→D」のように各引数値から評価値までの写像パターンで表現される。
*関数も[[高階論理]]に組み込まれている。引数値または評価値として扱うことができる関数は[[第一級関数]]と呼ばれる。その第一級関数を扱うことができる関数は[[高階関数]]と呼ばれる。
*カリー化された関数は引数の適用を途中で止めて残り引数を後から適用できる第一級関数を生成できる。これは部分適用と呼ばれる。
*片方の評価値と片方の第1引数が同じ型の両関数は任意に連結できる。この双方の写像のつなぎ合わせは関数合成と呼ばれる。
*仮引数記述を省略した関数はポイントフリーと呼ばれ、その省略箇所に先行式評価値が実引数として暗黙適用される。実引数記述を省略して先行式評価値を後続関数の仮引数箇所に暗黙適用するのもポイントフリーと呼ばれる。この暗黙適用の式を並べて連鎖させる手法は[[パイプライン処理|パイプライン]]と呼ばれる。言語によっては特別な演算子と併せて明示する。
*関数は名前付きと名前無しの二通りある。後者はラムダ抽象を模した構文で式中に直接定義される。これは[[無名関数]]と呼ばれる。式内に自由変数を持った無名関数は[[クロージャ]]と個別に定義される。自由変数には外部データが代入される。自身を参照する無名関数を内包したデータ構造体(=[[関数オブジェクト]])もクロージャに相当する。
*[[無名関数]]は引数をピュア[[写像|マッピング]]する純粋関数であるが、毎回違う値が渡される用途から事実上[[メモ化]]できない事がコーディング上の利便性を除いた存在理由になっている。[[クロージャ]]の引数[[写像|マッピング]]は式内の自由変数に影響され、またその自由変数に作用する事もあるという副作用要素を閉包した非純粋関数である。
*関数の名前は、それに結び付けられた式または式ツリーの[[不動点]]の表現になる。自式の不動点を式内に置いて新たな引数と共に[[高階論理]]の式として評価する手法は[[再帰]]と呼ばれる。
*イミュータブル性が重視されない場合、関数の終端式での再帰は、実引数の更新+先端式へのアドレスジャンプと同等に見なせるので専らそちらに最適化される。これは[[末尾再帰]]と呼ばれる。同様の仕組みで相互再帰を最適化した兄弟再帰(''sibling recursion'')もある。
*リスト処理時にリストの各要素に対する作用子として渡される第一級関数は[[反復子|イテレータ]]と呼ばれる。作用後の各要素を別の新生リストに向けて複製する働きを加えたものは[[ジェネレータ (プログラミング)|ジェネレータ]]と呼ばれる。これは[[イミュータブル]]重視時に多用される。前者はポイントフリーの無名関数、後者はポイントフリーのクロージャとして定義される事が多い。
*任意のタイミングで遅延評価(''call/cc'')される用途の第一級関数は特別に[[継続]]と呼ばれる。関数の引数を順々に評価して間に分岐などを挟める[[継続渡しスタイル]]はその応用例である。
*部分関数は引数によって[[ボトム型]]になる関数である。ボトム型は虚(''falsity'')と見なされており、式のツリーないし写像の連鎖の失敗した終着点になる。
*演算子はデフォルトの式内容を持ち、引数が1~2個に限定された関数と同義である。部分適用された演算子はセクションと呼ばれる第一級関数になる。演算子は任意の型にフックさせた再定義および追加定義ができる。これはアドホック多相と呼ばれる。


関数名は[[関手]]の識別子と同義なので、同じ識別子に個別の引数パターン候補を付けたものを列挙することで[[非交和]]または[[選言]]の関係でつなげる事ができる。これは[[多重定義|関数のパターンマッチング]]と呼ばれる。また、変数名を直接[[関手]]の識別子と見なしてパターンマッチ候補を列挙して非交和の関係でつなげる方は[[パターンマッチング|パターンマッチング式]]と呼ばれる。パターンマッチングは等価性照合、等値性照合、任意の要素をワイルドカードにした部分的等値性照合のいずれかで行われる。パターンマッチで特定された実引数値ないし変数値を更に任意の等値式または比較式で真偽判定し、その結果に従った写像の二択分岐や、偽の場合はパターンマッチをそこで無効にして写像をキャンセルする事もできる。これは[[ガード (プログラミング)|ガード]]と呼ばれる。
=== 値と代数的データ型 ===
{{出典の明記|date=2020年5月6日 (水) 02:30 (UTC)|section=1}}
*値(''value'')は代数的データ型(''algebraic data type'')として表現される。代数的データ型は[[型理論]]にある様々なタイプの複合体である。代数的データ型は言わば「型の式」である。
*代数的データ型の式パターンは型構築子(''type constructor'')に束縛される。型構築子は新たな代数的データ型の識別名になる。式パターン内で代数的データ型は入れ子にできる。その入れ子とプロパー型は式パターン内で型変数(''type variable'')として扱われ、パラメトリック多相で総称化できる。型構築子は型引数(''type parameter'')と併せて定義され、総称化された各要素を決定する。
*数値、論理値、文字値、文字列は[[プリミティブ型|プロパー型]](''proper type'')に分類され、最も基本的な式パターン要素になる。
*代数的データ型は、代数的データ型の入れ子で帰納的に構成される事もあるがその末端は必ずプロパー型になる。この帰納的な仕組みは[[高階論理|高階]]型(''higher-order types'')と呼ばれる。
*代数的データ型は、プロパー型に到るまでの帰納パターンである[[カインド (型理論)|カインド]]で抽象化分類される。カインドは「*→*」「*」のように表現される。カインドはパターンマッチングと型シノニムの成立基準になる。
*左辺のもので右辺のものを置き換えられるという代数的データ型間の代用(''substitution'')規則を定義できる。これは型シノニムと呼ばれる。これは厳密には異なるが[[継承 (プログラミング)|継承]]の[[リスコフの置換原則]]をイメージすると分かりやすい。
*代数的データ型は、[[直積集合|直積型]](''product type'')[[非交和|非交和型]](''sum type'')帰納型(''inductive type'')[[依存型]](''dependent type'')ユニット型(''unit type'')などのタイプを持つ。式的役割は直積型=×演算子、非交和型=+演算子、帰納型=式再帰または高階式、依存型=パターンマッチング式、ユニット型=NILである。この5タイプで大半の値を表現できる。
*直積型は、(A, B) のような[[タプル]]または標準的な[[構造体|レコード]]のパターンを表わす。
*非交和型は、(A | B) のような[[共用体|修飾共用体]]または[[列挙型]]のパターンを表わす。前者は型推論による等価性で、後者は評価による等値性で識別される非交和である。前者はユニオン型(''union type'')と個別定義されてもいる。
*帰納型は、[[ボックス化]]と前述の入れ子のパターンを表わす。また帰納型と非交和型とユニット型は併用されて[[連結リスト]]、[[二分木]]、[[ツリー構造|データツリー]]のパターンを表わす。
*依存型は、一つの依存値による[[パターンマッチング]]式をそのままタイプと見なしたものである。その[[パターンマッチング|ケース節]]パターンのみはオプション型(''option type'')[[ガード (プログラミング)|ガード節]]パターンのみはリファイン型(''refinement type'')と個別定義される。これらは[[動的配列]]、Maybe値、リスト内包表記などの構造を表わす。
*ユニット型は、NILないしVOIDであり空集合のパターンを表わす。
*交差型(''intersection type'')は、型クラスや型エイリアスなどのアドホック多相によるパターンの表現に用いられる。
*[[パターンマッチング]]式は、CASE式の値に依存した依存型またはオプション型のその場構築である。条件分岐式(IF-THEN-ELSE)は、IF式の値に依存したリファイン型のその場構築である。前者は型推論と式評価による等価性または等値性のパターン審査を行う。後者は式評価による等値性または順序性の論理的審査を行う。
*関数の写像パターンは指数型(''exponential type'')で説明される。”関数適用の評価値”は指数型と直積型の併用で表現される。そのまま関数の型(''function type'')と呼ばれる事が多い。関数のパターンマッチングはもっぱらアドホック多相の方で解釈される。
*[[型推論]]は、代数的データ型の式パターンを等価性を審査できる形まで演繹する機能である。これはいわゆる「型」を導き出すのと同義である。この機能により束縛変数の型注釈はもっぱら省略される。型推論は値の等価性審査の手段であり、いわゆる型チェックや遅延パターンマッチングなどを実現する。


演算子はデフォルトの式内容を持ち、その引数が単項演算子なら1個、二項演算子なら2個に限定された関数と同義である。部分適用された演算子はセクションと呼ばれる。演算子は任意の型をフックした、又は任意の型にフックさせた再定義および追加定義ができる。前者のフックしたは関数のパターンマッチングと同じ仕組みで、後者のフックさせたは抽象データ型の静的メンバ関数と同じ仕組みで実装される。双方ともアドホック多相に該当するものである。
=== 評価戦略 ===
関数型プログラミングにおける[[評価戦略]]とは「式存在」を「値存在」にする評価タイミングの定義を指す。これはまず正格評価(''strict evaluation'')と非正格評価(''non-strict evaluation'')の二つに大別される。正格評価の式存在は、関数による適用と同時に評価されて値存在になり、または変数による束縛と同時に評価されて値存在になる。関数の引数節で直積された式存在は理論上全て同時に評価される事になる。その実装は直積された式存在を副作用を伴わずに並行計算するか一つ一つ評価していく事になる。単に一つ一つ評価していくものは[[先行評価]]になり、ここでも副作用を伴わない事が原則とされるが必須ではなくなる。


=== 値とデータストラクチャ ===
後者の非正格評価はほとんどのケースで[[遅延評価]]と同義の言葉になる。遅延評価の式存在は、関数に適用されても式存在のままであり、または変数に束縛されても式存在のままである。後続式において改めて他の関数ないし演算子に適用される時に初めて評価されて値存在になり、または改めて他の変数に束縛される時に初めて評価されて値存在になる。これが遅延評価のデフォルトタイミングであるが、[[継続]]コール(''call/cc'')手法や不可反駁(''irrefutable'')指定によって更に評価を遅延させる事もできる。継続コールは変数束縛した第一級関数またはクロージャを任意のタイミングで評価して値を導出できる機能である。これは値の導出後も式存在のままなので再利用できる。コール前の部分適用とコール時の引数適用、クロージャの方では自由変数への任意時代入も可能である。不可反駁指定はその式存在の変数部分が不特定で[[ボトム型]]を導出する場合は評価を取り止め、特定している場合のみに評価を成立させて値存在にする機能である。ただしこれは遅延パターンマッチングで等価性審査から評価値写像につなげる為の内包表記用途にほぼ限定されている。また代数的データ型の式パターンの多くは遅延評価対象であり、[[共用体]]、無限リスト、[[再帰データ型]]の表現が可能になっている。
関数型プログラミングの値(''value'')は、単体値を兼ねたあらゆる[[多重集合]]を表わすデータストラクチャ(''data structure'')として実装される。単体値なデータストラクチャはただの[[プリミティブ型|プリミティブ]]である。そうでないの方のデータストラクチャは[[プリミティブ型|プリミティブ]]と[[構造体|コンポジット]]のミックスである。ただしこれは端的な表現であり、より正確な説明は後節に先送りする。プリミティブは数値、論理値、文字値、文字列を指す。コンポジットはC言語などの構造体と同等である。まずプリミティブが型構築子(''type constructor'')によってまとめられる。正確ではないが型構築子=構造体と見てもよい。型構築子は入れ子にできるので、型構築子をまとめた型構築子を定義できる。自分自身(型構築子)を入れ子にした再帰構造も定義できる。プリミティブと型構築子を任意に組み合わせた様々な型構築子の総称がデータストラクチャである。関数型言語で用いられるデータストラクチャの代表例は[[代数的データ型]]と[[S式]]である。データストラクチャ内のプリミティブとコンポジットの組み合わせはパターン(''pattern'')と呼ばれる。パターンには[[アノテーション]]要素や[[ガード (プログラミング)|ガード]]要素も加えられる。そのパターンが型になり、パターンの構築が型付けになり、パターンを[[量化]](''quantify'')すると型付け値になり、これはターム(''term'')と呼ばれる。タームは冒頭の値(''value'')を指す。型構築子のパターンの末端は必ずプリミティブになるので、パターン内の全てのプリミティブの値を決定することが量化になる。特定の文脈が求めるパターンにマッチするタームは等価(''equivalent'')とされる。この等価は同じ型と読み替えてもよい。等価性はあらゆる計算の可否を決定する。計算とは関数適用または演算子適用を指し、それらが求める仮引数と実引数にするタームが等価であればその計算は成立する事になる。各パターンが持つ数々の特徴は、[[型理論]]に従って直積型、非交和型、帰納型、ユニット型、ユニオン型、オプション型、詳細型、交差型などに分類されている。

[[S式]]は、コンス(''cons'')と呼ばれる双子セルを持つ二項型構築子のみで形成されるデータストラクチャである。S式はコンスを実行時に連結して任意のパターンを構築する[[動的型付け]]の値である。セルにはプリミティブまたは入れ子コンスが入る。コンスの連結によるセル要素の並びは[[型理論]]の[[直積集合|直積型]](''product type'')と見なされる。直積型は[[タプル]]のパターンを表わすが、S式では3要素以上の並びはコンスの再帰連結になるので[[線形リスト|リスト]]と呼ばれる。コンスのセルにはあらゆるタームが入れられるので事実上の[[非交和|非交和型]](''sum type'')として扱う事もできる。

[[代数的データ型]]は、[[型理論]]の[[直積集合|直積型]]と[[非交和|非交和型]]を定義できる型構築子の組み合わせで任意のパターンを構築する[[静的型付け]]の値である。直積型は[[タプル]]または[[構造体|レコード]]のパターンを表わす。非交和型は[[列挙型]]または[[共用体|タグ共用体]]のパターンを表わす。前者は等値性(''equality'')で識別される一般的な非交和である。後者は等価性(''equivalent'')で識別される非交和であるが、ユニオン型(''union type'')と個別定義されてもいる。自分自身の型構築子のネスティングは型理論の帰納型(''inductive type'')とされる。非交和型と帰納型とユニット型の組み合わせは[[連結リスト]]や[[二分木]]のパターンを表わす。ユニット型(''unit type'')はnilないしvoidであり空集合のパターンを表わす。ユニット型とそうでない型の二択の非交和型はオプション型(''option type'')とされMaybe値のパターンを表わす。上述の連結リストの要素になるタームは全て等価(同じ型)であることが原則である。「ターム集合→[[ガード (プログラミング)|ガード]]→抽出タームリスト」のパターンは詳細型(''refinement type'')とされ[[リスト内包表記]]を表わす。パターンに[[アノテーション]]を加えて元々の等価性に上乗せした任意の用途性で代数的データ型を分類するのは交差型(''intersection type'')とされ[[型クラス]]または型アノテーションを表わす。これはアドホック多相に相当する。パターン内のプリミティブと型構築子は、型変数(''type variable'')に置き換えることで[[ジェネリックプログラミング|ジェネリック化]]でき、型引数(''type parameter'')の指定でスペシフィック化できる。これはパラメトリック多相に相当する。代数的データ型は定義と実装を分けて後者を隠蔽するという意味でしばしば抽象化される。これは識別名を重複させる仕組みで実現され、型シノニムまたは型エイリアスと呼ばれる。

=== 評価戦略 ===
関数型プログラミングの[[評価戦略]](''evaluation strategy'')は、ネーム存在を値存在にする評価タイミング、引数の渡し方のcall-by-What、関数のボトム型の発生タイミングの三つを定義している。これはまず正格評価(''strict evaluation'')と非正格評価(''non-strict evaluation'')の二つに大別される。正格評価のネーム存在は、関数適用と同時に評価されて値存在になり、または変数による束縛と同時に評価されて値存在になる。この評価タイミングに注目した方は[[先行評価]](''eager evaluation'')と呼ばれる。引数のどれか一つがボトム型の値存在になった関数は反駁(''refutable'')されてそのままボトム型になる。この意味も包括した呼称が正格評価である。正格評価=先行評価のcall-by-Whatは値渡しになる。関数型プログラミングの性格から参照渡しと共有渡し(ポインタ渡し)は用いられない。代数的データ型では、型構築子に渡された型引数は型構築用とパラメトリック多相用の双方ともに先行評価対象である。


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


=== 参照透過性 ===
=== 参照透過性 ===
[[参照透過性]]とは関数は同じ引数値に対して必ず同じ評価値を恒久的に導出し、その評価過程において現行計算枠外の情報資源に一切の作用を及ぼさないというプロセス上の枠組みを意味する。現行計算枠外のいずれかの情報資源が変化するのと同時にいずれかの関数の評価過程も変化してしまう現象[[副作用 (プログラム)|副作用]]と呼ばれる。参照透過性はこの副作用の排除も同時に意味している。参照透過性に則した関数実装は関数の純粋化と呼ばれる。参照透過性は関数の純粋化の他、変数の再代入をプログラムから排除する事で成立する。それによってあらゆる値の写像の履歴がプログラム開始時に宣言(''declarative'')された初期値まで遡れるようになる。この膨大な写像の履歴ツリーの解析と模型化は[[プロセス計算|プロセス微積分]]ないし[[プロセス代数]]と呼ばれ並行プログラミングの支柱にされている。並行プログラミングの基本メカニズムは、全プロセスをまず無制約に並行実行させておき、どこか不整合(''conflict'')発生した場合は一定の関連プロセスを整合性が取れる履歴ツリ上の写像位置まで巻き戻すいうものである。過去に戻ったプロセスは不整合が反映された別の写像ルートを辿ことになるが、そルート変化未来情報の反映になるので副作用には当たらない。この時に履歴ツリー用いられる。従って写像履歴の改ざんにつながる再代入は厳禁になり、ある時点の写像をただ書き留めておく[[束縛変数]]と、旧値の更新を新値の産出で代替した[[イミュータブル]]が不可欠になる。ループは再帰で行われ、条件分岐は[[代数的デ型]]の[[依存型]]で表現される。
[[参照透過性]](''referential transparency'')とは関数は同じ引数値に対して必ず同じ評価値を恒久的に導出し、その評価過程において現行計算枠外の情報資源に一切の作用を及ぼさないというプロセス上の枠組みを意味する。現行計算枠外のいずれかの情報資源が変化するのと同時にいずれかの関数の評価過程も変化してしまう現象[[副作用 (プログラム)|副作用]]と呼ばれる。参照透過性はこの副作用の論理的排除も同時に意味している。参照透過性に則した関数実装は関数の純粋化と呼ばれる。副作用の論理的排除は関数の純粋化の他、あらゆる再代入処理をプログラムから排除する事で成立する。それによってプログラム内に存在するあらゆる値の写像の履歴が[[有向グラフ]]化されて、プログラム開始時に宣言(''declarative'')された初期値まで遡れるようになる。宣言値からあらゆる存在値をつ写像の履歴であるプロセス[[有向グラフ]]の解析と模型化は[[プロセス計算|プロセス微積分]]ないし[[プロセス代数]]と呼ばれ[[並行プログラミング]]などの支柱にる。関数型プログラミングの世界再代入タブーとされるのは、それが写像履歴の改ざんにつながるからである。従ってある時点の写像をただ書き留めておく[[束縛変数]]と、旧値の更新を新値の産出で代替した[[イミュータブル]]が重視される。[[構造化プログラミング|制御フロー]]の反復(ループ関数の再帰で表現され、選択(分岐非交和の関係でつなげた写像で表現される。再入処理は自由変の他、リスト更新、クロジャ、継続、オプション生成、ボトム型処理、システムコール、各種I/O作業なども指しており、参照透過性を維持しつつそれらを実装するための仕組みが[[型理論]]由来派生構造型であり、[[圏論]]由来の[[モナド (プログラミング)|モナド]]でる。


また参照透過性効になる写像の履歴ツリーは、一定の[[証明論]]に基づいたプルーフアシスタントによる[[正当性 (計算機科学)|プログラム正当性]]の自動的な[[形式的検証]]および[[論証|数学的証]]を可能にする。プルーフアシスタントはソフトウェアツールである。純粋関数型言語はその為に参照透過性をプログラム全体の枠組みにしている。ただしプログラム正当性が[[数学的証明|証明]]されてもランタイム環境側のプログラム運用部分のデバッグは残される事になる。プログラム全体に参照透過性を適用するには前述コーディング上注意の他に、プログラムレベルでは回避できない各種I/O作業に伴う必然的副作用の論理的排除も必要になるので専用のランタイム環境上での動作が必須になる。ランタイム環境は”環境データ”を走行プログラムとの仲介にする。プログラム内の各関数は、ライナー型引数値として渡された”環境データ”に作用するという形で各種I/O作業を行う。その仮想的I/O作業はランタイム環境側で実際に代行され、そのI/O作業で変化したコンピュータ環境はその都度”環境データ”に反映される。関数は”環境データ”をライナー型返り値として渡し返す。ライナ―型(''linear type'')は[[型理論]]における派生構造型(''substructural type'')の一形態であり[[線形合同法]]に似た生成アルゴリズムによる写像履歴を維持するための[[型システム]]である。これはユニークネス型とも呼ばれる。”環境データ”関連値を注入する仕組みはアフィン型(''affine type'')、抽出する仕組みは関連型(''relevant type'')と呼ばれる。双方とも派生構造型の一形態である。このように各種I/O作業を”環境データ”への作用という形にする事で副作用を論理的に排除し、ライナー型の疑似乱数列に似た仕組みで参照透過性を論理的に維持している。常にユニーク生されるライナー型値は、I/O作業の副作用によって実際には変化しているランタイム環境の時系列状態を各個照会可能にしているマッピングキーである。これによってランタイム環境の変化も写像の履歴ツリーで論理的に辿れるようにしている。ここでの論理的とは言わば見せかけの意味に近いが、一定の問題をプログラム側から綺麗に切り離してランタイム環境側に丸投げできるメカニズムは開発上極めて有益と見なされている。なお、型システムの代わりに[[圏論]]を利用して写像履歴を維持するための[[デザインパターン (ソフトウェア)|デザインパターン]]手法が[[モナド (プログラミング)|モナド]]である。”環境データ”を加工するモナド演算子は数学問題における[[公理]]や[[公式]]と同等の存在であり、決められたルールに従って用いるだけで副作用の排除と参照透過性の維持を論理的に表現できる。
参照透過性が保証されたプロセス[[向グラフ]]は、一定の[[証明論]]に基づいたプルーフアシスタントによる[[正当性 (計算機科学)|プログラム正当性]]の[[形式的検証]]および[[数学的証]]を可能にする。プルーフアシスタントはソフトウェアツールである。純粋関数型言語はその為に参照透過性をプログラム全体の枠組みにしている。プログラム全体に参照透過性を適用するには関数純粋化と再代入処理排除の他に、プログラムレベルでは回避できない各種I/O作業に伴う必然的副作用の論理的排除も必要になるので専用のランタイム環境上での動作が必須になる。ランタイム環境は「コンテキスト」を走行プログラムとの仲介にする。プログラム内の各関数は、ライナー型引数値として渡されたコンテキストに作用するという形で各種I/O作業を行う。その仮想的I/O作業はランタイム環境側で実際に代行され、そのI/O作業で変化したコンピュータ環境はその都度コンテキストに反映される。関数はコンテキストをライナー型返り値として渡し返す。ライナ―型(''linear type'')は[[型理論]]派生構造型(''substructural type'')の一形態であり[[線形合同法]]に似たユニク値生成アルゴリズムによってプロセス有向グラフの正当性を維持するための[[型システム]]である。これはユニークネス型とも呼ばれる。コンテキスト関連値を注入する仕組みはアフィン型(''affine type'')、抽出する仕組みは関連型(''relevant type'')と呼ばれる。双方とも派生構造型の一形態である。このように各種I/O作業をコンテキストへの作用という形にする事で副作用を論理的に排除し、ライナー型の疑似乱数列に似た仕組みで参照透過性を論理的に維持している。常にユニークな値にされるライナー型値は、I/O作業の副作用によって実際には変化しているランタイム環境の時系列状態を完全に抽象化して、それらを理論上各個照会可能にしているマッピングキーである。これによってランタイム環境の変化もプロセス有向グラフで論理的に辿れるようにしている。なお、型システムの代わりに[[圏論]]を利用してプロセス有向グラフの正当性を維持するための[[デザインパターン (ソフトウェア)|デザインパターン]]手法が[[モナド (プログラミング)|モナド]]である。コンテキストに作用するモナド演算子は数学問題における[[公理]]や[[公式]]と同等の存在であり、決められたルールに従って用いるだけで副作用の排除と参照透過性の維持を論理的に表現できる。


=== 型システム ===
=== 型システム ===
関数型プログラミングの[[型システム]](''type system'')は、[[型付きラムダ計算|型付けラムダ計算]]ベースの[[型理論]]に基づいたスタイルで実装されている。型システムの分類に従った対比で述べると、[[命令型言語]]では明示的型付け(''manifest typing'')が多用されるのに対し、関数型では推論的型付け(''inferred typing'')が多用される。また関数型では、所属する部品に注目して全体を識別する構造的型付け(''structural typing'')よりも、記名から全体を識別しその文脈で所属する部品も識別する記名的型付け(''nominal typing'')の方がよく用いられる。これはアドホック多相に相当するものであり、実例は[[型クラス]]と型アノテーションである。型クラスは型理論における”文脈”を形式化したものでインターフェースのように用いられる。型アノテーションはそれ自体が構造体化される実装もあり、この場合は様々な情報が付加されてやや無節操に応用される。なお、構造的型付けは[[ダックタイピング]]の考え方と同義である。

関数型初期の[[LISP]]系の[[S式]]は、二項型構築子(コンス)の実行時の連結でパターンを形成する潜在的型付け(''latent typing'')であり、これは形式化されていない推論的型付けと言えるもので[[動的型付け]](''dynamic typing'')に分類されている。[[ML (プログラミング言語)|ML]]系を境にしてパターンを事前形成する[[静的型付け]](''static typing'')が主流になった。その実装の[[代数的データ型]]は多項な型構築子の組み合わせであり、パラメトリック多相で[[ジェネリックプログラミング|ジェネリック化]]された。''Hindley–Milner''型体系は、このパラメトリック多相に対応した[[型推論]]機能を提供して強い静的型付けの実装をサポートした。値をメモリ上のビット列ではなく、構造的な代数式と見なすのが関数型プログラミングの特徴である。前者はただのビット列を識別するためにコンパイラがその識別情報を他に持ち、それを参照する為に予め型名を明示(''manifest'')せねばならないが、後者は値自体が識別情報を兼ねているので常時その推論(''inferred'')で型名を識別できる。この時に用いられる[[型推論]]は、代数的データ型のパターンを等価性を審査できる形まで簡約するという型理論に沿った用法だけでなく、ソースコードの前後の文脈までシークして型を導き出せるという実用面にも特化された機能である。これによって関数型言語での型注釈と型宣言はもっぱら省略される。値を構造的な代数式と見なす仕組みは、メモリ上のビット列の幅拡張や恣意解釈を利用した[[型変換]]を全排除するので結果的に強い型付け(''strong typing'')に結び付く。しかし随所で多用されるユニオン型(等価性による非交和型)の値は弱い型付け(''weak typing'')相当である。関数型プログラミングでは強を基軸にしつつも弱のジョイントで解釈の選択が図られている。

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

タイプに依存してプロパータイプを導出する仕組みが型構築子と呼ばれるのに対し、タームに依存してプロパータイプを導出する仕組みの方は[[型理論]]の[[依存型]]と呼ばれる。依存型の導出は、依存値×写像の直積で表現される。写像は依存関数とも呼ばれる。依存関数から導出される「型」とは、量化前のプロパータイプか、未確定の変数部分=量化されてない部分を内包しているネーム存在である。この型としてのネーム存在は簡約されるなどして柔軟な等価性照合を可能にする。型としてのネーム存在は量化されるとタームとしての値存在になり、それをまた依存値にした別の型の導出も可能である。依存関数は、依存値によって量化部分は異なるが同じ等価性の型を導出する[[全称量化子|全称量]](''for all'')と、依存値によって異なる等価性の型を導出する[[存在量化子|存在量]](''there exists'')に分かれる。依存型は、型構築子をメインにするそれとは異なる型システムの下で実装される事になった。

[[多態性]]三種の三番目であるサブタイプ多相は、データの[[セマンティクス]]または[[メソッド (計算機科学)|振る舞い]]の多相を扱う性質から関数型とは相容れない部分が多い。関数型の[[代数的データ型]]と[[オブジェクト指向プログラミング|オブジェクト指向]]の[[抽象データ型]]は対象的なデータストラクチャと見なされている。前者がデータのみの表現体であるのに対して、後者はセマンティクスを主にしたデータの表現体である。しかしオブジェクト指向との連携が模索される中で数々の手法も提示されている。動的型付けメインのLISP系ではS式の代わりに、各スロットに任意の変数を[[動的束縛|動的バインディング]]できるレコードを用いる。その動的バインディング用レコードを1個以上引数にできる関数によって[[多重ディスパッチ]]が表現される。動的バインディング用レコードの型チェックは[[ダックタイピング]]で行われる。静的型付けメインのML系ではパラメトリック多相による[[ジェネリックプログラミング|ジェネリック]]抽象データ型が用いられる。その型引数=型変数には抽象データ型が代入される。関数型プログラミングのサブタイプ多相はジェネリッククラスの[[継承 (プログラミング)|継承関係]]ではなく、型変数の方の継承関係を用いるのが特徴である。型変数の方の継承関係で結ばれたジェネリックインスタンスの機構はヴァリアンス(''variance'')と呼ばれる。ヴァリアンスはジェネリッククラスを中間媒体にしてサブタイプ多相のための継承構造を扱う仕組みである。ヴァリアンスには[[共変性と反変性 (計算機科学)|共変性]](''covariance'')と[[共変性と反変性 (計算機科学)|反変性]](''contravariance'')がある。共変性は指定の型変数を抽象軸にしたその子孫の型変数たちによる横並びのサブタイピングである。反変性は指定の型変数からその祖先の型変数までの階層的な縦並びのサブタイピングである。この時にアドホック多相に該当する型境界(''type bound'')または型制約(''type constraint'')で型引数=型変数を修飾させて静的な型チェックをサポートさせる事が多い。


== 歴史 ==
== 歴史 ==
72行目: 55行目:
'''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」「K」「Q」といった派生言語が後年に登場している。続く1966年に発表された「[[ISWIM]]」は関数型を有用な構文スタイルとして扱うマルチパラダイム言語の原点とされ、[[ALGOL]]を参考にした構造化プログラミングに高階関数とwhereスコープが加えられていた。60年代の関数型プログラミングの歴史はもっぱらLISPの発展を中心にしていたが、ISWIMは後年の「ML」「Scheme」のモデルにされている。
1964年に計算機科学者[[ケネス・アイバーソン]]が開発した「[[APL]]」は、数多く定義された関数記号多次元配列データ適用する機能を中心にした言語であり、取り分け[[スプレッドシート]]処理に対する効率性が見出されて、1960年代以降の商業分野と産業分野に積極導入された。APLは関数型ではなく配列プログラミング型に位置付けられているが、配列を始めとするデータ集合に対する関数適用の有用性を特に証明した言語になった。そのデータ集合処理の可能性に注目した「J」「K」「Q」といった派生言語が後年に登場している。また後年の「[[FP (プログラミング言語)|FP]]」にも影響を与えている。続く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双方の登場は関数型プログラミングのマイルストーンになった。また同年代にの数学純粋性重視た「SASL」と[[クリーネの再帰定理]]実装を主な目的にした「Hope」も発表されている。1977年、[[バッカス・ナウア記法]]と[[FORTRAN]]開発の功績でこの年の[[チューリング賞]]を受けた計算機科学者[[ジョン・バッカス]]は「''Can Programming Be Liberated From the von Neumann Style? -A Functional Style and Its Algebra of Programs-''」と題した記念講演を行い、一説にはこれを境にして関数型(''functional'')というパラダイム名が定着したと言われる。なお同時に発表された「[[FP (プログラミング言語)|FP]]」は関数水準(''function-level'')言語として紹介されている。バッカスはFPのプログラムをアトム+関数+フォーム(=高階関数)の階層構造と定義し、[[プロセス代数|代数]]を用いるフォームの結合で全体構築されると提唱した。[[ノイマン型]]からの脱却を題目に掲げているバッカスの理論は、後年のCPUに導入される並列[[パイプライン処理]]に通じる構想であった。
相互[[自動定理証明]]に向けて始められた「''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年代'''


数学者[[ペール・マルティン=レーフ|マルティン=レーフ]]が1972年から提唱していた直感的型理論は、関数型プログラミングの世界に[[型理論]]の[[依存型]]の重要性を認識させて[[型システム]]の拡張に貢献した。1978年にML設計ミルナーが発表した型推論アルゴリズムが1982年に証明されると、''Hindley–Milner''型体系と定義され型システムは更にした。1983年にML標準化目的した「[[Standard ML]]」が発表され続く1985年にML派生言語「Caml」が公開された。同じく1985年にSASLの後継として発表された「[[Miranda]]」は、遅延評価を標準にしながら関数の数学的純粋性を追求した言語であり、関数型プログラミング研究用[[オープン標準|オープンスタンダード]]のコンセンサスで1987年から策定が開始された[[Haskell]]のモデルになりその進捗を大きく後押しした。それと前後してMirandaは1987年公開の純粋関数型言語「[[Clean]]」にも大きな影響を与えている。Cleanは後発のHaskellをも叩き台にして改良を続けた。また関数型と[[並行計算]]の適性が認識される中で1986年の通信業界で開発された「[[Erlang]]」は[[並行プログラミング]]指向の面で特に注目を集めている言語である。
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年代を通して改良が続けられていた


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


1990年にこれも関数型プログラミングのマイルストーン的な純粋関数型言語「[[Haskell]]」が初リリースされた。1992年に[[動的型付け]]レコードクラスと[[多重ディスパッチ]]メソッドを扱う関数型言語「[[Dylan]]」が登場した。1993年に[[ベクトル]]、[[行列]]、[[表 (データベース)|表テーブル]]などのデータストラクチャを扱えて[[統計的検定]]、[[時系列分析]]、[[データ・クラスタリング|クラスタリング]]分野に特化した関数型言語「[[R言語|R]]」が発表された。1995年にLISPの[[マクロ (コンピュータ用語)|マクロ]]機能を大幅に強化したコンポーネント指向により各分野に合わせた[[ドメイン固有言語]]として振る舞える「[[Racket]]」が登場した。1996年にはML系列のCamlにオブジェクト指向視点の[[抽象データ型]]を導入した「[[OCaml]]」が公開された。90年代の関数型プログラミングの歴史では、関数の数学的純粋さを追求する[[参照透過性]]指向とオブジェクト指向との連携が比較的目立っていた。日本ではStandard MLに独自の拡張を施した「SML#」が発表されている。風変りなものに[[コンビネータ論理]]の形式に立ち返った「[[Unlambda]]」がある。[[論理型プログラミング]]との親和性も見直されるようになり1995年に「Mercury」が公開された。論理型のルール&ファクトパラダイムはデータ集合対するフィルタリングなどに活用された。1988年公開の「[[Wolfram (プログラミング言語)|Wolfram]]」はAPLスイルのリスト処理に一定のデータリレショを定義できる[[項書き換え]]を組み合わせた言語で90年代を通て改良が続けられていた。
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年のマイクロソフト製「[[F Sharp|F#]]」、2007年のLISP方言「[[Clojure]]」など数々のポピュラー言語が生み出されている。また直感的型理論と[[カリー=ハワード同型対応|カリー=ハワード同型対応]]の理論に基づいたプルーフアシスタント(''Proof assistant'')によるプログラム正当性の数学的証明を指向した関数型言語が支持され、2004年に「Epigram」2007年に「[[Agda]]」および純粋関数型「Idris」が発表されている。関数型構文の有用性がより広く認識されるに従い、オブジェクト指向言語やスクリプト言語にも積極的に導入されるようになった。産業分野からも注目されるようになり、[[Constructive Solid Geometry|CSG]]幾何フレームワーク上で動く[[CAD]]への導入も始められた。しかし関数型コンセプトに馴染まないオペレーターが定数化規則による値の再代入制限に困惑して設計作業に支障をきたすなどの弊害も明らかになっている。
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]]への導入も始められた。しかし関数型コンセプトに馴染まないオペレーターが定数化規則による値の再代入制限に困惑して設計作業に支障をきたすなどの弊害も明らかになっている。


== 代表的な関数型言語 ==
== 代表的な関数型言語 ==
'''[[LISP]]''' (1958年)
'''[[LISP]]''' (1958年)


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


'''[[ISWIM]]''' (1966年)← LISP、[[ALGOL]]
'''[[ISWIM]]''' (1966年)← LISP、[[ALGOL]]


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


[[ML (プログラミング言語)|'''ML''']] (1973年)← ISWIM
[[ML (プログラミング言語)|'''ML''']] (1973年)← ISWIM


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


'''[[Scheme]]''' (1975年)← LISP、ISWIM
'''[[Scheme]]''' (1975年)← LISP、ISWIM


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


[[FP (プログラミング言語)|'''FP''']] (1977年
[[FP (プログラミング言語)|'''FP''']] (1977年)← APL


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


'''[[Standard ML]]''' (1983年)← ML、Hope、[[Pascal|PASCAL]]
'''[[Standard ML]]''' (1983年)← ML、Hope、[[Pascal|PASCAL]]


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


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


: 純粋、静的型付け
: ML派生、静的型付け、先行評価

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

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


'''[[Erlang]]''' (1986年)← LISP、[[Prolog]]、[[Smalltalk]]
'''[[Erlang]]''' (1986年)← LISP、[[Prolog]]、[[Smalltalk]]


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


'''[[Clean]]''' (1987年)← Miranda
'''[[Clean]]''' (1987年)← Miranda


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


'''[[Haskell]]''' (1990年)← ML、Scheme、Miranda、Clean、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]]


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


[[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]]


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


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


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


'''[[Scala]]''' (2003年)← Scheme、HaskellOCaml、Erlang、[[Smalltalk]]、[[Java]]
'''[[Scala]]''' (2003年)← Scheme、Standard MLHaskell、Erlang、[[Smalltalk]]、[[Java]]


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


[[F Sharp|'''F#''']] (2005年)← HaskellOCaml、Erlang、Scala、[[Python]]、[[C♯]]
[[F Sharp|'''F#''']] (2005年)← Standard MLHaskell、Erlang、Scala、[[Python]]、[[C♯]]


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


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


: LISP方言、動的型付け
: LISP方言、動的型付け、先行評価
'''[[Rust (プログラミング言語)|Rust]]''' (2010年)← Scheme、Standard ML、Haskell、Erlang、[[C♯]]
: 静的型付け、先行評価


== 関数型プログラミングの例 ==
== 関数型プログラミングの例 ==
アルゴリズムの[[Hello world|Hello World]]と言える[[フィボナッチ数列|フィボナッチ数]]を求めるプログラムは、チュートリアルなどでよく引き合いに出されるものであり、本稿でも手続き型言語との比較を兼ねて取り上げる。一般的な手続き型言語によるソースコードは以下のようになる。<syntaxhighlight lang="pascal">
関数型プログラミングは「計算とは何か」という数学の理論を基礎にしており、関数型プログラミングがもつ[[計算モデル]]は'''関数モデル'''である<ref>計算モデル2 関数モデル. (中略) 関数モデルに基づくプログラミング言語. 関数型言語. Lisp [http://nous.web.nitech.ac.jp/individual/inuzuka/lecture/PLT/PLT07/ 犬塚信博 (2007)「プログラミング言語論 第1回 イントロダクション」名古屋工業大学]</ref>。たとえば、1 から 10 までの整数を足し合わせるプログラムを考える{{efn|本来は[[等差数列]]の和の公式を用いて定数時間で問題を解く方法が最適解だが、ここではプログラミングスタイルの比較のため数値計算的手法を用いる。}}。[[命令型プログラミング]]では以下のように[[ループ (プログラミング)|ループ]]文を使って変数に数値を足していく(計算機の状態を書き換える)命令を繰り返し実行するという形を取る。
FUNCTION fibona (num: INTEGER): INTEGER;

VAR
* [[Pascal]]による例:
x, y, tmp: INTEGER;
<syntaxhighlight lang="pascal">
BEGIN
program test;
var total, i : Integer;
x := 1;
y := 1;
begin
FOR i := 2 TO num DO
total := 0;
BEGIN
for i := 1 to 10 do
total := total + i;
tmp := x;
x := y;
WriteLn(total)
y := y + tmp;
end.
END;
fibona := y;
END;
</syntaxhighlight>
</syntaxhighlight>


それに対して一般的な関数型言語によるソースコードは以下のようになる。<syntaxhighlight lang="haskell">
一方、関数型プログラミングでは、繰り返しには一時変数およびループを使わず、[[サブルーチン|関数]]の[[再帰呼び出し]]を使う。
let rec fibona num = if num < 2 then 1 else fibona (num-2) + fibona (num-1)
</syntaxhighlight>
コード行の羅列であるテキスト的な手続き型プログラミングと比較すると関数型プログラミングの方は、ガードとリミットによる分岐終点ルールで枠組みされたリーフ値と再帰関数のノードによるツリー化手順が一目で把握可能であり、ソースコードから式のツリー構造が直感的に浮かび上がってくる。同様のアルゴリズムで後続値とのペア(2-tuple)を表示するものは以下のようになる。<syntaxhighlight lang="haskell">
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)
* [[F Sharp|F#]]による例:
<syntaxhighlight lang="fsharp">
printfn "%d" (let rec sum x = if x > 0 then x + sum (x - 1) else 0
sum 10)
</syntaxhighlight>
</syntaxhighlight>
<!--
<!--
194行目: 190行目:
</syntaxhighlight>
</syntaxhighlight>
-->
-->

ただし再帰呼び出しは[[スタックオーバーフロー]]の危険性やオーバーヘッドを伴うため、注意深く使用しなければならない<ref>[https://msdn.microsoft.com/ja-jp/library/dd233229(v=vs.120).aspx 関数 (F#) | MSDN]</ref>。通例、関数型言語では、[[末尾再帰]]呼び出し (tail-recursive call) の形で書かれた関数をループに展開する[[末尾再帰#末尾呼出し最適化|末尾呼出し最適化]]により、スタックオーバーフローの危険性および再帰のオーバーヘッドを解消できる。[[Scheme]]など、関数型言語の中には末尾再帰呼び出しの最適化を仕様で保証するものもある。再帰関数を末尾再帰に書き換えることが難しいケースも有り、そのような場合は一般的なループが採用される。

また、関数型言語は文 (statement) よりも式 (expression) を中心とした言語仕様となっていることも特徴である。前述の例において、再帰関数<code>sum</code>を[[束縛 (情報工学)|束縛]]する<code>let</code>は式である。また、条件分岐の<code>if-then-else</code>も式である。文よりも式で書けることが多いほうが都合がよい。

関数型言語は関数型プログラミングをサポートする言語ではあるが、手続き型プログラミングを行なうことも可能である。例えばF#では以下のようなPascal風の書き方もできる。

<syntaxhighlight lang="fsharp">
let mutable total = 0
for i = 1 to 10 do
total <- total + i
printfn "%d" total
</syntaxhighlight>

ただし[[Haskell]]のようにループ構文をサポートせず、従来の手続き型プログラミングが難しいケースもある。

逆に手続き型言語を使って関数型プログラミングを行なうことも可能であるが、末尾再帰呼び出しの最適化がサポートされるかどうかはコンパイラ次第である。


== 脚注 ==
== 脚注 ==

2020年8月1日 (土) 06:38時点における版

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

関数型プログラミングは数理論理学と代数系をルーツにし、ラムダ計算コンビネータ論理を幹にして構築され、LISP言語が実装面の先駆になっている。関数の数学的な純粋性を指向したものは純粋関数型言語と個別に定義されている。命令型プログラミング言語(手続き型オブジェクト指向を指す)では単に有用な構文スタイルとして扱われている事が多い。高階関数第一級関数関数合成英語版部分適用英語版無名関数クロージャ継続ポイントフリー英語版パイプラインイテレータジェネレータ代数的データ型型推論パターンマッチングガードパラメトリック多相英語版アドホック多相英語版再帰束縛変数イミュータブル純粋関数英語版などが関数型プログラミングのスタイル要素として挙げられる[誰?]

特徴

ここでは関数型プログラミング本来の構文スタイルを元にして説明する。式を基本文にする関数型に対して、ステートメントを基本文にする命令型プログラミング言語では必要に応じて構文スタイルを変えて実装されている。代表的なのは「式に引数を適用する」に対する「関数に引数を渡す」である。値とその型付けに対するコンセプトおよびデータストラクチャの実装スタイルも異なっている。ただし双方ともアセンブリコード上では同様なものに符号化される。

式と関数

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

関数も値と同一視される。関数は写像の型の値であるが、プログラム的には式に引数を結び付ける機能であり、これは式に引数を適用application)すると呼ばれる。式内の仮引数(parameter)箇所に実引数(argument)が順次当てはめられ、式ツリーの終端式が評価値になる。引数によってはボトム型になる関数もありこれは部分関数と呼ばれる。ボトム型は虚(falsity)と見なされており、式のツリーないし写像の連鎖の失敗した終着点になる。関数は、式に第1引数を適用したもの→第x引数を適用したもの→評価値、という形をとる。引数を1個ずつ適用する形態はカリー化と呼ばれる。2個以上の引数を同時適用する形態は非カリー化と呼ばれる。関数の型(function type)は「A→B→C」のように各引数値から評価値までの写像パターンで表現される。片方の評価値と片方の第1引数が同じ型の両関数は任意に連結して新たな関数にできる。この双方の写像のつなぎ合わせは関数合成と呼ばれる。カリー化された関数は引数の適用を途中で止めて残り引数を後から適用するように保留できる。この保留状態の関数の生成は部分適用と呼ばれる。任意のタイミングで遅延評価(call/cc)するために評価を保留してる関数は継続と呼ばれる。その応用に、一つの式を個々の演算子適用(関数適用)に分解して各個継続化し、それらをボトムアップで組み上げて一つの継続集合体を生成する継続渡しスタイルがある。部分適用と継続はネームと同義である。関数も当然ながら高階論理に組み込まれている。引数値または評価値として扱うことができる関数は第一級関数と呼ばれる。その第一級関数を扱うことができる関数は高階関数と呼ばれる。

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

関数名は関手の識別子と同義なので、同じ識別子に個別の引数パターン候補を付けたものを列挙することで非交和または選言の関係でつなげる事ができる。これは関数のパターンマッチングと呼ばれる。また、変数名を直接関手の識別子と見なしてパターンマッチ候補を列挙して非交和の関係でつなげる方はパターンマッチング式と呼ばれる。パターンマッチングは等価性照合、等値性照合、任意の要素をワイルドカードにした部分的等値性照合のいずれかで行われる。パターンマッチで特定された実引数値ないし変数値を更に任意の等値式または比較式で真偽判定し、その結果に従った写像の二択分岐や、偽の場合はパターンマッチをそこで無効にして写像をキャンセルする事もできる。これはガードと呼ばれる。

演算子はデフォルトの式内容を持ち、その引数が単項演算子なら1個、二項演算子なら2個に限定された関数と同義である。部分適用された演算子はセクションと呼ばれる。演算子は任意の型をフックした、又は任意の型にフックさせた再定義および追加定義ができる。前者のフックしたは関数のパターンマッチングと同じ仕組みで、後者のフックさせたは抽象データ型の静的メンバ関数と同じ仕組みで実装される。双方ともアドホック多相に該当するものである。

値とデータストラクチャ

関数型プログラミングの値(value)は、単体値を兼ねたあらゆる多重集合を表わすデータストラクチャ(data structure)として実装される。単体値なデータストラクチャはただのプリミティブである。そうでないの方のデータストラクチャはプリミティブコンポジットのミックスである。ただしこれは端的な表現であり、より正確な説明は後節に先送りする。プリミティブは数値、論理値、文字値、文字列を指す。コンポジットはC言語などの構造体と同等である。まずプリミティブが型構築子(type constructor)によってまとめられる。正確ではないが型構築子=構造体と見てもよい。型構築子は入れ子にできるので、型構築子をまとめた型構築子を定義できる。自分自身(型構築子)を入れ子にした再帰構造も定義できる。プリミティブと型構築子を任意に組み合わせた様々な型構築子の総称がデータストラクチャである。関数型言語で用いられるデータストラクチャの代表例は代数的データ型S式である。データストラクチャ内のプリミティブとコンポジットの組み合わせはパターン(pattern)と呼ばれる。パターンにはアノテーション要素やガード要素も加えられる。そのパターンが型になり、パターンの構築が型付けになり、パターンを量化quantify)すると型付け値になり、これはターム(term)と呼ばれる。タームは冒頭の値(value)を指す。型構築子のパターンの末端は必ずプリミティブになるので、パターン内の全てのプリミティブの値を決定することが量化になる。特定の文脈が求めるパターンにマッチするタームは等価(equivalent)とされる。この等価は同じ型と読み替えてもよい。等価性はあらゆる計算の可否を決定する。計算とは関数適用または演算子適用を指し、それらが求める仮引数と実引数にするタームが等価であればその計算は成立する事になる。各パターンが持つ数々の特徴は、型理論に従って直積型、非交和型、帰納型、ユニット型、ユニオン型、オプション型、詳細型、交差型などに分類されている。

S式は、コンス(cons)と呼ばれる双子セルを持つ二項型構築子のみで形成されるデータストラクチャである。S式はコンスを実行時に連結して任意のパターンを構築する動的型付けの値である。セルにはプリミティブまたは入れ子コンスが入る。コンスの連結によるセル要素の並びは型理論直積型product type)と見なされる。直積型はタプルのパターンを表わすが、S式では3要素以上の並びはコンスの再帰連結になるのでリストと呼ばれる。コンスのセルにはあらゆるタームが入れられるので事実上の非交和型sum type)として扱う事もできる。

代数的データ型は、型理論直積型非交和型を定義できる型構築子の組み合わせで任意のパターンを構築する静的型付けの値である。直積型はタプルまたはレコードのパターンを表わす。非交和型は列挙型またはタグ共用体のパターンを表わす。前者は等値性(equality)で識別される一般的な非交和である。後者は等価性(equivalent)で識別される非交和であるが、ユニオン型(union type)と個別定義されてもいる。自分自身の型構築子のネスティングは型理論の帰納型(inductive type)とされる。非交和型と帰納型とユニット型の組み合わせは連結リスト二分木のパターンを表わす。ユニット型(unit type)はnilないしvoidであり空集合のパターンを表わす。ユニット型とそうでない型の二択の非交和型はオプション型(option type)とされMaybe値のパターンを表わす。上述の連結リストの要素になるタームは全て等価(同じ型)であることが原則である。「ターム集合→ガード→抽出タームリスト」のパターンは詳細型(refinement type)とされリスト内包表記を表わす。パターンにアノテーションを加えて元々の等価性に上乗せした任意の用途性で代数的データ型を分類するのは交差型(intersection type)とされ型クラスまたは型アノテーションを表わす。これはアドホック多相に相当する。パターン内のプリミティブと型構築子は、型変数(type variable)に置き換えることでジェネリック化でき、型引数(type parameter)の指定でスペシフィック化できる。これはパラメトリック多相に相当する。代数的データ型は定義と実装を分けて後者を隠蔽するという意味でしばしば抽象化される。これは識別名を重複させる仕組みで実現され、型シノニムまたは型エイリアスと呼ばれる。

評価戦略

関数型プログラミングの評価戦略evaluation strategy)は、ネーム存在を値存在にする評価タイミング、引数の渡し方のcall-by-What、関数のボトム型の発生タイミングの三つを定義している。これはまず正格評価(strict evaluation)と非正格評価(non-strict evaluation)の二つに大別される。正格評価のネーム存在は、関数適用と同時に評価されて値存在になり、または変数による束縛と同時に評価されて値存在になる。この評価タイミングに注目した方は先行評価eager evaluation)と呼ばれる。引数のどれか一つがボトム型の値存在になった関数は反駁(refutable)されてそのままボトム型になる。この意味も包括した呼称が正格評価である。正格評価=先行評価のcall-by-Whatは値渡しになる。関数型プログラミングの性格から参照渡しと共有渡し(ポインタ渡し)は用いられない。代数的データ型では、型構築子に渡された型引数は型構築用とパラメトリック多相用の双方ともに先行評価対象である。

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

参照透過性

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

参照透過性が保証されたプロセス有向グラフは、一定の証明論に基づいたプルーフアシスタントによるプログラム正当性形式的検証および数学的証明を可能にする。プルーフアシスタントはソフトウェアツールである。純粋関数型言語はその為に参照透過性をプログラム全体の枠組みにしている。プログラム全体に参照透過性を適用するには関数の純粋化と再代入処理の排除の他に、プログラムレベルでは回避できない各種I/O作業に伴う必然的副作用の論理的排除も必要になるので専用のランタイム環境上での動作が必須になる。ランタイム環境は「コンテキスト」を走行プログラムとの仲介にする。プログラム内の各関数は、ライナー型引数値として渡されたコンテキストに作用するという形で各種I/O作業を行う。その仮想的I/O作業はランタイム環境側で実際に代行され、そのI/O作業で変化したコンピュータ環境はその都度コンテキストに反映される。関数はコンテキストをライナー型返り値として渡し返す。ライナ―型(linear type)は型理論の派生構造型(substructural type)の一形態であり、線形合同法に似たユニーク値生成アルゴリズムによってプロセス有向グラフの正当性を維持するための型システムである。これはユニークネス型とも呼ばれる。コンテキストに「関連値」を注入する仕組みはアフィン型(affine type)、抽出する仕組みは関連型(relevant type)と呼ばれる。双方とも派生構造型の一形態である。このように各種I/O作業をコンテキストへの作用という形にする事で副作用を論理的に排除し、ライナー型の疑似乱数列に似た仕組みで参照透過性を論理的に維持している。常にユニークな値に生成されるライナー型値は、I/O作業の副作用によって実際には変化しているランタイム環境の時系列状態を完全に抽象化して、それらを理論上各個照会可能にしているマッピングキーである。これによってランタイム環境の変化もプロセス有向グラフで論理的に辿れるようにしている。なお、型システムの代わりに圏論を利用してプロセス有向グラフの正当性を維持するためのデザインパターン手法がモナドである。コンテキストに作用するモナド演算子は数学問題における公理公式と同等の存在であり、決められたルールに従って用いるだけで副作用の排除と参照透過性の維持を論理的に表現できる。

型システム

関数型プログラミングの型システムtype system)は、型付けラムダ計算ベースの型理論に基づいたスタイルで実装されている。型システムの分類に従った対比で述べると、命令型言語では明示的型付け(manifest typing)が多用されるのに対し、関数型では推論的型付け(inferred typing)が多用される。また関数型では、所属する部品に注目して全体を識別する構造的型付け(structural typing)よりも、記名から全体を識別しその文脈で所属する部品も識別する記名的型付け(nominal typing)の方がよく用いられる。これはアドホック多相に相当するものであり、実例は型クラスと型アノテーションである。型クラスは型理論における”文脈”を形式化したものでインターフェースのように用いられる。型アノテーションはそれ自体が構造体化される実装もあり、この場合は様々な情報が付加されてやや無節操に応用される。なお、構造的型付けはダックタイピングの考え方と同義である。

関数型初期のLISP系のS式は、二項型構築子(コンス)の実行時の連結でパターンを形成する潜在的型付け(latent typing)であり、これは形式化されていない推論的型付けと言えるもので動的型付けdynamic typing)に分類されている。ML系を境にしてパターンを事前形成する静的型付けstatic typing)が主流になった。その実装の代数的データ型は多項な型構築子の組み合わせであり、パラメトリック多相でジェネリック化された。Hindley–Milner型体系は、このパラメトリック多相に対応した型推論機能を提供して強い静的型付けの実装をサポートした。値をメモリ上のビット列ではなく、構造的な代数式と見なすのが関数型プログラミングの特徴である。前者はただのビット列を識別するためにコンパイラがその識別情報を他に持ち、それを参照する為に予め型名を明示(manifest)せねばならないが、後者は値自体が識別情報を兼ねているので常時その推論(inferred)で型名を識別できる。この時に用いられる型推論は、代数的データ型のパターンを等価性を審査できる形まで簡約するという型理論に沿った用法だけでなく、ソースコードの前後の文脈までシークして型を導き出せるという実用面にも特化された機能である。これによって関数型言語での型注釈と型宣言はもっぱら省略される。値を構造的な代数式と見なす仕組みは、メモリ上のビット列の幅拡張や恣意解釈を利用した型変換を全排除するので結果的に強い型付け(strong typing)に結び付く。しかし随所で多用されるユニオン型(等価性による非交和型)の値は弱い型付け(weak typing)相当である。関数型プログラミングでは強を基軸にしつつも弱のジョイントで解釈の選択が図られている。

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

タイプに依存してプロパータイプを導出する仕組みが型構築子と呼ばれるのに対し、タームに依存してプロパータイプを導出する仕組みの方は型理論依存型と呼ばれる。依存型の導出は、依存値×写像の直積で表現される。写像は依存関数とも呼ばれる。依存関数から導出される「型」とは、量化前のプロパータイプか、未確定の変数部分=量化されてない部分を内包しているネーム存在である。この型としてのネーム存在は簡約されるなどして柔軟な等価性照合を可能にする。型としてのネーム存在は量化されるとタームとしての値存在になり、それをまた依存値にした別の型の導出も可能である。依存関数は、依存値によって量化部分は異なるが同じ等価性の型を導出する全称量for all)と、依存値によって異なる等価性の型を導出する存在量there exists)に分かれる。依存型は、型構築子をメインにするそれとは異なる型システムの下で実装される事になった。

多態性三種の三番目であるサブタイプ多相は、データのセマンティクスまたは振る舞いの多相を扱う性質から関数型とは相容れない部分が多い。関数型の代数的データ型オブジェクト指向抽象データ型は対象的なデータストラクチャと見なされている。前者がデータのみの表現体であるのに対して、後者はセマンティクスを主にしたデータの表現体である。しかしオブジェクト指向との連携が模索される中で数々の手法も提示されている。動的型付けメインのLISP系ではS式の代わりに、各スロットに任意の変数を動的バインディングできるレコードを用いる。その動的バインディング用レコードを1個以上引数にできる関数によって多重ディスパッチが表現される。動的バインディング用レコードの型チェックはダックタイピングで行われる。静的型付けメインのML系ではパラメトリック多相によるジェネリック抽象データ型が用いられる。その型引数=型変数には抽象データ型が代入される。関数型プログラミングのサブタイプ多相はジェネリッククラスの継承関係ではなく、型変数の方の継承関係を用いるのが特徴である。型変数の方の継承関係で結ばれたジェネリックインスタンスの機構はヴァリアンス(variance)と呼ばれる。ヴァリアンスはジェネリッククラスを中間媒体にしてサブタイプ多相のための継承構造を扱う仕組みである。ヴァリアンスには共変性covariance)と反変性contravariance)がある。共変性は指定の型変数を抽象軸にしたその子孫の型変数たちによる横並びのサブタイピングである。反変性は指定の型変数からその祖先の型変数までの階層的な縦並びのサブタイピングである。この時にアドホック多相に該当する型境界(type bound)または型制約(type constraint)で型引数=型変数を修飾させて静的な型チェックをサポートさせる事が多い。

歴史

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は関数型ではなく配列プログラミング型に位置付けられているが、配列を始めとするデータ集合に対する関数適用の有用性を特に証明した言語になった。そのデータ集合処理の可能性に注目した「J」「K」「Q」といった派生言語が後年に登場している。また後年の「FP」にも影響を与えている。続く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年代

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」は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」など数々のポピュラー言語が生み出されている。また、カリー=ハワード同型対応の理論に基づいたプルーフアシスタント(Proof assistant)によるプログラム正当性の数学的証明を指向した関数型言語が支持され、2004年に「Epigram」2007年に「Agda」および純粋関数型「Idris」が発表されている。これらの言語では直感的型理論英語版で解釈された型理論依存型も導入されて一歩進んだ型システムを実現している。関数型構文の有用性がより広く認識されるに従い、オブジェクト指向言語やスクリプト言語にも積極的に導入されるようになった。産業分野からも注目されるようになり、CSG幾何フレームワーク上で動くCADへの導入も始められた。しかし関数型コンセプトに馴染まないオペレーターが定数化規則による値の再代入制限に困惑して設計作業に支障をきたすなどの弊害も明らかになっている。

代表的な関数型言語

LISP (1958年)

動的型付け、先行評価

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)

脚注

注釈

出典

外部リンク