関数型プログラミング

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

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

一般的な関数型スタイル

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

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

無名関数はもっぱら引数→式（例：x→x+1）のように書式され、与えられた引数に作用した結果値を返す働きをする。書式的特徴から言語によってはラムダ式と呼ばれている。高階関数への引数として使われることが多い。無名関数の式内に外部データを含んだものはクロージャと呼ばれる。クロージャの結果値はその時の外部データ状態に左右される事になる。

map / filter / reduce

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

名前渡し / 遅延評価

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

型推論

型推論は静的型付けの機能であり、コンパイル時の解析でソースコード内のあらゆる関数適用や変数束縛が求める等価性と値のそれが一致しているかをチェックする。値の等価性は推論的型付け視点の「型」になる。同じ型でなかったら計算不可の型エラーになってコンパイルエラーになる。型の推論はソースコード内のあらゆるプリミティブ記述、データ構築子定義、変数束縛（Var）関数定義（Abs）関数適用（App）等式（Let）汎用型構築子定義（Gen）実例型構築子定義（Inst）の記述箇所を拾い上げて総合解析するという専用の型推論アルゴリズムで行われる。端的に言うとプリミティブという原子の組み合わせとその写像による変遷を精密に辿ってそれぞれの型を判別していると考えてよい。推論的型付けでは変数/引数/返り値に対する型宣言と型注釈は不要になり、むしろ計算全体の整合性を損ねるものとして倦厭される。

手続き型やオブジェクト指向言語での型推論の使用対象はローカル変数や引数渡しが中心になる。その場合の利点はローカル変数に型テンプレート的な表現の幅を持たせてソースコードの保守修正作業を容易にすることなどである。従来の型宣言と型注釈を用いる明示的型付けと、型推論の共存はC言語世代プログラミングに対する一つのパラダイムシフトでもある。

特徴

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

式と関数

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

関数型プログラミングの関数は”関数の型”（function type）で分類される存在量の値である。プログラム的には式に引数を結び付ける機能であり、これは関数を引数に適用する（applying a function to an argument）とされる。関数の式内の仮引数（parameter）箇所に渡された実引数（argument）がパターンマッチング手法で当てはめられ、先行（eager）または遅延（lazy）タイミングで評価されて結果値が導出される。この仮引数箇所は束縛変数と呼ばれる。関数呼び出し時とは異なるタイミングで内容が決定される変数箇所は自由変数と呼ばれる。letとwhereで特定の式に向けて定義される変数はその式への束縛変数になる。なお関数型パラダイムでの自由変数の意味合いは他の宣言型パラダイムとはやや異なっている。関数適用時に用いられるパターンマッチング手法は、仮引数パターンの選言的な列挙を可能にしている。このパターンマッチングは”関数の型”に沿った等値性（equality）で仮引数と実引数を照合する。更にそれにガードと呼ばれる値の比較照合と範囲照合を加えることもできる。仮引数が非交和型の場合はその中で列挙されている型との等価性（equivalent）でも仮引数と実引数を照合できる。渡される実引数によってはボトム型になる関数もありこれは部分関数（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に適用すると関数f.g::A→Cが導出されるというものである。合成演算子の左側の定義域と右側の値域が同じ型の場合のみ合成できる。高階関数的な連結であるf(g A)と働きかた的には同じであるが、パイプライン処理の方に該当する関数連結（関数チェーン）と、カリー化に則った関数合成は異なる概念である。カリー化による部分適用や合成演算子から導出された”関数の型の値”を、任意の変数に束縛して扱うのはポイントフリースタイル（point-free style）と呼ばれる。ポイントフリースタイルの変数を値に適用すると、評価された値が返されるかまたは”関数の型の値”が返される事になる。ポイントフリースタイル変数はvar valueの書式で自身の右の値を暗黙的に引数として取る。ポイントフリースタイルは高階述語論理と存在量化子の表現手法でもあり、継続渡しスタイルにも応用される。引数を部分適用された演算子はセクションと呼ばれてポイントフリースタイルでよく用いられる。カリー化準拠の”関数の型”は型理論の指数型（quotient type）に分類されるものである。

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

値とデータ構造

関数型プログラミングの値（value）は型（type）で分類される定数または全称量の変数である。これは基本データ型（プリミティブ）と複合データ型（コンポジット）のいずれかで表現される。プリミティブは数値、論理値、文字値、文字列を指す。コンポシットはプリミティブを任意に組み合わせた複合体であり、例としては構造体や共用体などを指す。その組み合わせ方に焦点を当てた用語がデータ構造（data structure）である。データ構造という概念には再帰、アノテーション、ガード、操作的意味といった暗黙情報をも含められるので、コンポジットの具体的形式といった意味で用いられる。関数型言語で用いられるデータ構造の代表例は、代数的データ型とS式である。双方ともデータ構築子（data constructor）から構築される。まず、プリミティブがデータ構築子によってまとめられる。データ構築子はC言語の構造体/共用体と同性質のものであり、むしろ言い換えると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）と呼ぶ。副作用が伴なう操作の代表例は値の再代入と入出力処理とシステムコールである。この参照透過性は、副作用発生部分とそうでない部分を分けて処理構成の見通しを良くするなどのプログラム設計の視点から語られる事が多く、手続き型やオブジェクト指向ではその利点から解釈してよいものであるが、関数型パラダイムではプロセス有向グラフの整合性を維持するという視点から解釈する必要がある。プロセス有向グラフとはプログラム初期値からのあらゆる個体（値）と写像（関数）の繋がりを表わす図式である。あらゆる値の変遷が初期値まで遡れるという参照透過性が保証された関数型プログラムは、その正当性の形式的検証および数学的証明の自動化が可能になりこれが本質的な利点になる。プロセス有向グラフの解析と模型化は、プロセス代数と呼ばれ並行プログラミングの支柱になる。関数型の世界で値の再代入がタブーとされるのは、それが言わば履歴の改竄になってプロセス有向グラフの整合性を崩すからである。従って束縛変数と、旧値の更新を新値の生成で代替したイミュータブルが重視される。ループは関数の再帰で表現され、分岐は選言パターンマッチングとガードで表現される。以上が参照透過性の仕様上の意味である。

参照透過性の実装はコーディングレベルで副作用を排除できる部分への対応と、そうではない部分への対応に大別される。前者は再代入などを指しプログラマに委ねられる問題になる。後者は入出力処理やシステムコールなどを指しこちらではそうはいかない。後者の参照透過性は、副作用原因になる全ての情報要素を関数の引数に収納し、副作用結果になった全ての情報要素を関数の返り値に収納するという形式で表現される。情報要素には理論上は関連するコンピュータ環境状態が全て内包されている事になるが、その忠実な実践は当然不可能なので、コンピュータ環境状態を抽象化した「抽象環境」で代用される。抽象環境は言語処理系から提供される特殊データである。この抽象環境を関数の引数とその返り値に常時含めて、コーディングレベルの副作用排除はプログラマが解決する事で理論上は参照透過性が順守されている事になる。この論理的なトリック方式が参照透過性の実装上の意味である。抽象環境を用いて参照透過性を維持しつつ再代入/入出力/システムコールなどを行うための機能には、派生構造型システムとモナドがある。派生構造型システムは、抽象環境をライナー型（linear type）にして関数に渡される度にその中のIDデータをユニーク更新させる。抽象環境にユーザーデータを注入する仕組みはアフィン型（affine type）、抽象環境からユーザーデータを抽出する仕組みは関連型（relevant type）と呼ばれる。毎時ユニーク更新されるライナー型のIDデータは、各種入出力によって実際には変化しているコンピュータ環境の時系列状態を完全に抽象化して、それらを理論上各個照会可能にしているマッピングキーである。これによってコンピュータ環境状態の変化もプロセス有向グラフで論理的に辿れることになるので同時に参照透過性も維持されていることになる。派生構造型システムの実装例にはユニークネス型がある。ライナー型、アフィン型、関連型を組み合わせての特にその応用コーディングは煩雑なボイラープレートコードになりがちだったので、それらを圏論と代数的構造由来のアイディアでより平易かつ簡潔にした手法がモナドである。

型システム

関数型プログラミングの型システム（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→MA、S→M(A×S)、(A→MR)→MRといった型の値または関数の型の値にリフト（lift）される。これはモナド変換子（monad transformer）と呼ばれる。また、モナド値のMAのMを空データにして事実上の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引数の関数である。このFBは多相であり実際は値F＊関数F(＊→＊) 関数F(＊→＊→＊)などになっているのでそれに<*>を再び適用できる。アプリカティブは、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、Prolog、Smalltalk

動的型付け、先行評価、並行計算

Clean　（1987年）←　Miranda

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

Haskell　（1990年）←　Scheme、Standard ML、Miranda、FP

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

Dylan　（1993年）←　Scheme、CLOS、ALGOL

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、Smalltalk、Java

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

F#　（2005年）←　Standard ML、Haskell、Erlang、Scala、Python、C♯

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)

脚注

注釈

出典

外部リンク

• なぜ関数プログラミングは重要か
• The Functional Programming Language XSLT - A proof through examples