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

'''関数型言語'''（{{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月|関数型プログラミングのスタイル要素様式項目として挙げられる}}。

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

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

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

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

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

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

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

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

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

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

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

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

相互[[スタンフォード大学]]と[[エディンバラ大学]]で実施された[[対話型証明系|対話型]][[自動定理証明]]に向けて始められたプロジェクト「''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のプログラムをアトム+関数+フォーム（=高階関数）の階層構造と定義し、[[プロセス代数|代数]]を用いるフォームの結合で構築されると提唱した。

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

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

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

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

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

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

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

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

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

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