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

*式は値と同一視されるので、上述の式と値は相互再帰の関係にある。式内の値は他の式の評価値である事があり、その式内にもまた他の値があるといった具合である。これは[[高階述語論理|高階論理]]（''higher-order logic''）''と呼ばれる。''

*関数の引数値を[[高階論理]]は関数にする事も可能であり、また関数の評価値を関数にする事も可能であ当然適用される。他の関数を引数値または評価値として扱えうことができる関数は[[高階第一級関数]]と呼ばれる。他その第一級関数から引数値または評価値としてを扱われえる関数は[[第一級高階関数]]と呼ばれる。

*代数的データ型（=型の式）は、直積型（''product type''）非交和型（''sum type''）帰納型（''inductive type''）依存型（''dependent type''）ユニット型（''unit type''）などの五構造を持つ。式的役割は、直積型=×演算子、非交和型=＋演算子、帰納型=式再帰、依存型=型関数、ユニット型=NILと同義である。

*帰納型は、[[ボックス化]]の構造を表わす。また帰納型は非交和型およびユニット型と併用されて、[[連結リスト]]、[[二分木]]、[[ツリー構造|多分木]]などの構造を表わす。

*依存型は、もっぱら関数+環境値+対象値のセットで対象値は参照時に常時関数適用される。その写像は環境値によって変化する。依存型は他の型構造と併用されて動的配列、Maybe値などの構造を表わす。依存型の写像パターンはカインド（''kind''）と呼ばれる。

*ユニット型は、NIL、NULL、VOIDであり空集合の構造を表わす。

*プリミティブ値はあくまで理論上ではあるが、数値は非交和型、論理値は非交和型、文字は非交和型、文字列は直積型と非交和型と依存型（可変長文字列のみ時）の併用、複素数は直積型と非交和型の併用で実装されている事になる。

相互[[自動定理証明]]に向けて始められた「''Logic for computable functions''」プロジェクトの中で1973年に導入された「[[ML (プログラミング言語)|ML]]」は、[[代数的データ型]]と[[多態性|パラメトリック多相]]などを備えたマルチパラダイム関数型言語であり、計算機科学者[[ロビン・ミルナー]]によって開発された。また1975年に[[MIT人工知能研究所]]の計算機科学者[[ガイ・スティール・ジュニア|ガイ・スティール]]と[[ジェラルド・ジェイ・サスマン|ジェイ・サスマン]]が設計してAIリサーチ用に導入された「[[Scheme]]」もMLに劣らぬ言語仕様を備えており、関数用レキシカルスコープが採用されて構造化が図られていた。MLとScheme双方の登場は関数型プログラミングのマイルストーン更に再帰構造になっも着目した。MLは90年代に「[[OCaml]]」「[[Standard ML]]」を派生させている。Scheme設計者のスティールとサスマンは後年のラムダペーパーの中で[[末尾再帰]]最適化の必要性を訴えている。MLとScheme双方の登場は関数型プログラミングのマイルストーンになった。また同年代に関数の数学的純粋性を重視した「SASL」と[[クリーネの再帰定理]]の実装を主な目的にした「NPL」とその後継「Hope」も発表されている。

数学者[[ペール・マルティン＝レーフ|マルティン＝レーフ]]が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]]」は[[LISP]]、[[Prolog]]、[[Smalltalk]]といったパイオニア言語をモチーフにデザインされ、[[並行プログラミング]]指向の面で特に注目を集めている言語である。

1990年にこれも関数型プログラミングのマイルストーン的な純粋関数型言語「[[Haskell]]」が初リリースされた。同年にMLの標準化を目的にした「[[Standard ML]]」も公開されている。1992年にアップル社による動的型付けデザインの関数型言語「[[Dylan]]」が登場した。1993年に[[オブジェクト指向プログラミング|オブジェクト指向]]のクラスを模した[[抽象データ型]]を扱う関数型言語「[[R言語|R]]」が発表された。1995年にLISPのマクロ機能を大幅に強化したコンポーネント指向により各分野に合わせた[[ドメイン固有言語]]として振る舞える「[[Racket]]」が登場した。1996年にはML系列のCamlに当時流行していたオブジェクト指向を導入した「[[OCaml]]」が公開された。90年代の関数型プログラミングの歴史では、関数の数学的純粋さを追求する[[参照透過性]]指向と、オブジェクト指向との連携ないしその観点下の抽象データ型の導入が比較的目立っていた。日本ではStandard MLに独自の拡張を施した「SML#」が発表されている。研究用または教育用を目的にした関数型言語も続々と発表されており[[コンビネータ論理]]に立ち返った「[[Unlambda]]」や、[[論理型プログラミング]]を組み合わせた「[[Wolfram (プログラミング言語)|Wolfram]]」「Mercury」などが挙げられるが、それらも大抵関数。論理型の数学的純粋性導入は[[項書き換え|項置き換え]]のロジックを重視応用した強力なパターンマッチングを表現していた。

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