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

関数型プログラミングは[[数理論理学]]と代数系をルーツにし、[[ラムダ計算]]と[[コンビネータ論理]]を幹にして構築され、[[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月|関数型プログラミングのスタイル要素として挙げられる}}。

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

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

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

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

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

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

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

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