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

出典: フリー百科事典『ウィキペディア（Wikipedia）』
履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
タグ: モバイル編集 モバイルウェブ編集 改良版モバイル編集
(同じ利用者による、間の5版が非表示)
1行目: 1行目:
{{プログラミング・パラダイム}}
{{プログラミング・パラダイム}}
'''関数型プログラミング'''（かんすうがたプログラミング、{{lang-en-short|functional programming}}）とは、[[関数 (数学)|数学的な関数]]の適用を中心にした[[プログラミングパラダイム]]、または[[コンピュータプログラミング|プログラミング]]のスタイルである<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref><ref name=":0">{{Cite book|和書|title=関数型プログラミングの基礎|date=2016-11|year=2016|publisher=リックテレコム|page=1,3 関数型モデル}}</ref>。 関数プログラミングとも邦訳される<ref>{{harvnb|本間|類地|逢坂|2017|p=2}}</ref>。このスタイルに準拠した言語は、'''関数型プログラミング言語'''または'''関数型言語'''（{{lang-en-short|functional language}}）と呼ばれる<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。


数学的な関数は、[[副作用 (プログラム)|副作用]]を排除して[[参照透過性]]を順守している。参照透過性順守の度合いは言語ごとに異なっている。副作用を容認している関数型言語も多く、それらは非純粋と言われる<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。数学的な関数の実装に専念している本来のものは、{{仮リンク|純粋関数型言語|en|purely functional programming language}}と呼ばれている<ref>{{harvnb|本間|類地|逢坂|2017|p=5}}</ref>。関数型言語の多くはその設計に[[ラムダ計算]]が関わっている。ラムダ計算は、計算を記号列の規則的な変換として模型化した[[形式体系]]である<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>。
'''関数型プログラミング'''（かんすうがたプログラミング、{{lang-en-short|functional programming}}）とは、[[関数 (数学)|数学的な意味での関数]]を主に使うプログラミングのスタイルである<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。 functional programming は、'''関数プログラミング'''（かんすうプログラミング）などと訳されることもある<ref>{{harvnb|本間|類地|逢坂|2017|p=2}}</ref>。


== 特徴 ==
'''関数型プログラミング言語'''（{{lang-en-short|functional programming language}}）とは、関数型プログラミングを推奨している[[プログラミング言語]]である<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。略して'''関数型言語'''（{{lang-en-short|functional language}}）ともいう<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。
関数型プログラムは、数学的な[[関数 (数学)|関数]]を値に適用して別の値を得るという機構を組み合わせての[[宣言型プログラミング|宣言的]]な[[式 (プログラミング)|式]]の集まりになる。関数の適用とは、引数を入れて関数を呼び出して返り値を出すことと同じ意味になる<ref name=":0">{{Cite book|和書|title=関数型プログラミングの基礎|date=2016-11|year=2016|publisher=リックテレコム|page=1,3 関数型モデル}}</ref>。返り値を出すことは関数の評価と表現される<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>。数学的な関数とは[[参照透過性|参照透過]]な関数と同義である<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。


宣言的な式では、例えば関数記号と引数記号の適用部分を抜粋した表記の取り扱いと、その表記の詳細な処理内容の把握を分離することができる。その数式相当の性質はしばしば[[表示的意味論]]で説明される。
== 概要 ==


<syntaxhighlight lang="standardml">
関数型プログラミングは、[[関数 (数学)|関数]]を主軸にしたプログラミングを行うスタイルである<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。ここでの関数は、数学的なものを指し、引数の値が定まれば結果も定まるという[[参照透過性]]を持つものである<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。
(* 階乗の数式 *)
0! = 1
n! = n×(n-1)!


(* そのプログラム投影 *)
'''参照透過性'''とは、数学的な関数と同じように同じ値を返す式を与えたら必ず同じ値を返すような性質である<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。次の <code>square</code> 関数は、 <code>2</code> となるような式を与えれば必ず <code>4</code> を返し、 <code>3</code> となるような式を与えれば必ず <code>9</code> を返し、いかなる状況でも別の値を返すということはなく、これが参照透過性を持つ関数の一例となる<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。
fun func 0 = 1
| func n = n * func (n - 1)
</syntaxhighlight>上記の例では、関数<code>func</code>は[[参照透過性|参照透過]]であり[[再帰]]を用いており、その再帰関数は二項演算子<code>-</code>を引数に取っている[[高階関数]]になっている。<code>-</code>は[[第一級関数]]と同等である。再帰での<code>0</code>とそれ以外の分岐および[[停止性問題]]は[[パターンマッチング]]で解決されている。数学的な関数を中心にした宣言的な[[式 (プログラミング)|式]]では、自然とそれらのテクニックが必要になり、それ以外にも主に数学背景の様々なテクニックが導入されることになる<ref>{{Cite web|title=Declarative programming in Ch.3. Introduction to ML programming in SML# Document|url=https://www.pllab.riec.tohoku.ac.jp/smlsharp/docs/1.0/en/Ch3.S2.xhtml|website=www.pllab.riec.tohoku.ac.jp|accessdate=2021-1}}</ref>。

関数型プログラミングの最大特徴である数学的、宣言的、参照透過といった概念および意味は、このような実践の反復で徐々に把握していく。

=== 参照透過性 ===
{{main|参照透過性}}
参照透過性とは、数学的な関数と同じように同じ値を返す式を与えたら必ず同じ値を返すような性質である<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。次の <code>square</code> 関数は、 <code>2</code> となるような式を与えれば必ず <code>4</code> を返し、 <code>3</code> となるような式を与えれば必ず <code>9</code> を返し、いかなる状況でも別の値を返すということはなく、これが参照透過性を持つ関数の一例となる<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。


<syntaxhighlight lang="python" >
<syntaxhighlight lang="python" >
24行目: 38行目:
counter += n
counter += n
return counter
return counter
</syntaxhighlight>参照透過性を持つことは、その関数が'''状態を持たない'''ことを保証する<ref>{{harvnb|本間|類地|逢坂|2017|p=5}}</ref>。状態を持たない数学的な関数は、並列処理を実現するのに適している<ref>{{harvnb|本間|類地|逢坂|2017|p=5}}</ref>。関数型プログラミング言語の内で、全ての関数が参照透過性を持つようなものを純粋関数型プログラミング言語という<ref>{{harvnb|本間|類地|逢坂|2017|p=5}}</ref>。
</syntaxhighlight>


=== 第一級関数と高階関数 ===
関数型プログラミングは、参照透過性を持つような数学的な関数を使って組み立てた'''式'''が主役となる<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。別の箇所に定義されている処理を利用することを、手続き型プログラミング言語では「関数を実行する」や「関数を呼び出す」などと表現するが、関数型プログラミング言語では「式を評価する」という表現も良く使われる<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>。
{{main|第一級関数|高階関数}}
関数型プログラミングの関数は、他の関数への引数や返り値にもできるのが標準である。これを[[第一級オブジェクト|第一級]]という。他の関数を自身の引数や返り値にできる関数は、[[高階論理|高階]]といわれる。第一級関数は値と同等に扱われるので、変数に束縛したり[[データ構造]]に当てはめることができる<ref>{{cite book|first1=Harold|last1=Abelson|authorlink1=Harold Abelson|first2=Gerald Jay|last2=Sussman|authorlink2=Gerald Jay Sussman|title=Structure and Interpretation of Computer Programs|at=[https://archive.org/details/structureinterpr00abel/page/ Formulating Abstractions with Higher-Order Procedures]|publisher=MIT Press|year=1984|isbn=0-262-01077-1|url=https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3}}</ref>。値に名前が付けられないのと同様に名前無しの関数も定義できて、それは式内スコープ使用前提の[[無名関数]]になる<ref name="test">[http://www.worldcat.org/oclc/222529448 Programming language pragmatics], by Michael Lee Scott, section 11.2 "Functional Programming".</ref>。第一級関数は、{{仮リンク|関数の型|en|Function type}}で型付けされた値として扱われる<ref>{{cite journal|date=2005|title=The Implementation of Lua 5.0|journal=Journal of Universal Computer Science|volume=11|issue=7|pages=1159–1176|doi=10.3217/jucs-011-07-1159|author1=Roberto Ierusalimschy|author1-link=Roberto Ierusalimschy|author2=Luiz Henrique de Figueiredo|author3=Waldemar Celes|doi-access=free}}</ref>。


高階関数の性質は、[[カリー化]]や{{仮リンク|部分適用|en|Partial application}}などの実装を可能にする。関数を一つずつ引数に適用させる形式にするのをカリー化と呼ぶ。引数への適用を途中で止めたままにするのが部分適用である。それは変数に束縛して保存でき、後続式で残り引数を適用して最終的な返り値にできる。カリー化は、先行関数の返り値と後続関数の第一引数を連結した{{仮リンク|関数合成|en|Function composition}}を可能にする。
=== 参照透過性 ===


第一級関数の性質は、[[クロージャ]]や[[継続]]などの実装を可能にする。クロージャは後続式で引数を与えられることを前提にした抽象的な値を表現する。クロージャはしばしば特定の状態を囲い込んでそれをデータ抽象化する。継続は後続式で評価されることを前提にした関数式の[[スナップショット (ファイルシステム)|スナップショット]]を実現する。継続は計算式の挿入や入れ替えや再利用による計算フローの制御に役立てられる。
{{main|参照透過性}}


=== 純粋関数 ===
参照透過性とは、同じ値を与えたら返り値も必ず同じになるような性質である<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。参照透過性を持つことは、その関数が'''状態を持たない'''ことを保証する<ref>{{harvnb|本間|類地|逢坂|2017|p=5}}</ref>。状態を持たない数学的な関数は、並列処理を実現するのに適している<ref>{{harvnb|本間|類地|逢坂|2017|p=5}}</ref>。関数型プログラミング言語の内で、全ての関数が参照透過性を持つようなものを純粋関数型プログラミング言語という<ref>{{harvnb|本間|類地|逢坂|2017|p=5}}</ref>。
参照透過性を順守した関数は、{{仮リンク|純粋関数|en|Pure function}}と呼ばれる。これは機能と言うよりも、関数型プログラミングが目指すべきコンセプトに近い<ref>{{cite web|url=https://github.com/MostlyAdequate/mostly-adequate-guide/blob/master/ch03.md|title=Professor Frisby's Mostly Adequate Guide to Functional Programming|author=Brian Lonsdorf|date=2015|website=GitHub|publisher=|access-date=2020-03-20|quote=A pure function is a function that, given the same input, will always return the same output and does not have any observable side effect.}}</ref>。純粋関数は、同じ引数から常に同じ返り値が算出されるという[[冪等性]]を保証し、その計算が外部状態の影響を受けず、また外部状態に影響を与えないという[[副作用 (プログラム)|副作用]]の排除を保証している<ref>{{cite web|url=https://www.schoolofhaskell.com/school/starting-with-haskell/basics-of-haskell/3-pure-functions-laziness-io|title=Basics of Haskell|author=Bartosz Milewski|date=2013|website=School of Haskell|publisher=FP Complete|access-date=2018-07-13|quote=Here are the fundamental properties of a pure function: 1. A function returns exactly the same result every time it's called with the same set of arguments. In other words a function has no state, nor can it access any external state. Every time you call it, it behaves like a newborn baby with blank memory and no knowledge of the external world. 2. A function has no side effects. Calling a function once is the same as calling it twice and discarding the result of the first call.|archive-url=https://web.archive.org/web/20161027145455/https://www.schoolofhaskell.com/school/starting-with-haskell/basics-of-haskell/3-pure-functions-laziness-io|archive-date=2016-10-27|url-status=dead}}</ref>。外部状態はグローバル変数と読み替えてもよい。純粋関数はローカル変数などの内部状態も持たない。


純粋関数とは、冪等な計算式と可変な状態を完全に分離する機構であり、冪等な計算式は不変な状態としての定数群をしばしば内包している。この概念はinvariantや[[イミュータブル]]にも繋がっている。コンパイル[[最適化 (情報工学)|最適化]]の対象としても適当であり、純粋関数はコードの最適化で重要な役割を果たす。
=== 入出力 ===


純粋関数は、ミュータブルな状態を参照透過に処理するためのアプローチでもある。純粋関数は引数から状態を扱い、遷移させた状態を返り値にする。その参照透過性の維持ロジックには[[線形論理]]などが使われる。状態の構造化には[[適切さの論理|適切性論理]]などが使われる。それらの[[部分構造論理]]をより最適化した[[デザインパターン (ソフトウェア)|デザインパターン]]には[[圏論]]由来の[[モナド (プログラミング)|モナド]]がある。

=== 再帰 ===
{{main|再帰}}
関数型プログラミングの反復処理とループ処理は専ら、関数の再帰を通して行われる。再帰は、無限の項を有限の式で扱えるようにする手法である<ref>{{cite book|last=Wirth|first=Niklaus|author-link=Niklaus Wirth|title=Algorithms + Data Structures = Programs|publisher=[[Prentice-Hall]]|isbn=978-0-13022418-7|date=1976|page=[https://archive.org/details/algorithmsdatast00wirt/page/126 126]|url=https://archive.org/details/algorithmsdatast00wirt/page/126}}</ref>。再帰で取り沙汰される[[スタックオーバーフロー]]問題は、[[末尾再帰]]によるコード最適化で解決されることが多い<ref>{{cite book|chapter=Proper tail recursion and space efficiency|last=Clinger|first=William|title=Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation - PLDI '98|date=1998|pages=174–185|doi=10.1145/277650.277719|isbn=0897919874|s2cid=16812984}}</ref>。再帰は関数型のアルゴリズムの最要点であり<ref>{{cite book|author-last=Epp|author-first=Susanna|title=Discrete Mathematics with Applications|date=1995|isbn=978-0-53494446-9|edition=2nd|page=[https://archive.org/details/discretemathema000epps/page/427 427]|url=https://archive.org/details/discretemathema000epps/page/427}}</ref>、しばしば[[パターンマッチング]]や[[ガード (プログラミング)|ガード]]と組み合わせて使用される。再帰は[[データ構造]]でも多用され、こちらでは無限の要素を有限の構造で扱えるようにする手法になり、これは[[再帰データ型]]とも呼ばれる。

=== 先行評価と遅延評価 ===
{{main|評価戦略}}
関数型プログラミングでは、引数に適用した関数式を評価するタイミングの区別が重視される。引数確定と同時に評価して返り値にするのが先行評価である。引数確定してもその返り値が本当に必要になるまで評価を先送りにして、関数式の状態のままにしておくのが遅延評価である。

先行と遅延の区別は、引数渡しされる第一級関数でよく用いられる。全引数を評価してから関数コールするのが先行評価の用例になり、未評価の引数があるままで関数コールするのが遅延評価の用例になる。必要になった時に計算するという遅延評価は、計算量を減らしてのプロセスの軽量化をもたらす。また、評価を遅延した関数式を保管して別途使用ないし反復使用するという機能（[[継続]]、[[ジェネレータ (プログラミング)|ジェネレータ]]、[[例外処理|例外]]、[[コルーチン]]）は、計算解釈順序を操作してのプロセスの柔軟化をもたらす。

=== 型システム ===
{{main|型システム}}
Hindley–Milner型システムの登場以降の関数型プログラミングは、[[型付きラムダ計算]]を背景にした[[静的型付け]]が標準になっている。[[LISP|Lisp]]系で実践されていた[[型無しラムダ計算]]を背景にした[[動的型付け]]は、その対極に位置付けられている。{{仮リンク|Hindley–Milner型システム|en|Hindley–Milner type system}}がもたらした[[型推論]]もまた関数型プログラミングの標準になっている。型推論ルールでの各変数の型は、それに束縛される値を導出した各項と各評価値から演繹的に判別されるので、各変数への型説明や型注釈の表記を省略できる。

項の[[直積集合|直積]]および項の[[直和 (圏論)|直和]]の形式的な組み合わせ構造である[[代数的データ型]]は、[[型推論]]ルールに適した[[データ構造]]の表現方法として関数型プログラミングの標準になっている。代数的データ型は{{仮リンク|パラメトリック多相|en|Parametric polymorphism}}で[[総称プログラミング|総称化]]されているのが標準であり、Hindley–Milner型システムはその型変数化された項への[[型推論]]にも対応可能である。

=== 入出力 ===
関数型プログラミングでは、数学的な関数を組み合わせて計算を表現するが、それだけではファイルの読み書きのような外界とのやり取りを要する処理を直接的に表現できない<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。このような外界とのやり取りを '''I/O (入出力)''' と呼ぶ<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。数学的な計算をするだけ、つまり <code>1 + 1</code> のようなプログラム内で完結する処理ならば、入出力を記述できなくても問題ないが、現実的なプログラムにおいてはそうでない<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。
関数型プログラミングでは、数学的な関数を組み合わせて計算を表現するが、それだけではファイルの読み書きのような外界とのやり取りを要する処理を直接的に表現できない<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。このような外界とのやり取りを '''I/O (入出力)''' と呼ぶ<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。数学的な計算をするだけ、つまり <code>1 + 1</code> のようなプログラム内で完結する処理ならば、入出力を記述できなくても問題ないが、現実的なプログラムにおいてはそうでない<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。


44行目: 80行目:
[[Clean]] では、一意型を用いて入出力を表す{{要出典|date=2021年3月}}。
[[Clean]] では、一意型を用いて入出力を表す{{要出典|date=2021年3月}}。


=== 手法 ===
== 応用的な手法 ==

{{節スタブ|1=[[モナド]]・[[永続データ構造]]|date=2021年3月}}
{{節スタブ|1=[[モナド]]・[[永続データ構造]]|date=2021年3月}}


=== ポイントフリースタイル ===
最初に解の集合となる候補を生成し、それらの要素に対して1つ（もしくは複数）の解にたどり着くまで関数の適用とフィルタリングを繰り返す手法は、関数型プログラミングでよく用いられるパターンである<ref>{{harvnb|Lipovača|2012|p=22}}</ref>。
最初に解の集合となる候補を生成し、それらの要素に対して1つ（もしくは複数）の解にたどり着くまで関数の適用とフィルタリングを繰り返す手法は、関数型プログラミングでよく用いられるパターンである<ref>{{harvnb|Lipovača|2012|p=22}}</ref>。


Haskell では、関数合成の二項演算子を使って'''ポイントフリースタイル'''で関数を定義することができる<ref>{{harvnb|Lipovača|2012|p=22}}</ref>。関数をポイントフリースタイルで定義すると、データより関数に目が行くようになり、どのようにデータが移り変わっていくかではなく、どんな関数を合成して何になっているかということへ意識が向くため、定義が読みやすく簡潔になることがある<ref>{{harvnb|Lipovača|2012|p=22}}</ref>。関数が複雑になりすぎると、ポイントフリースタイルでは逆に可読性が悪くなることもある<ref>{{harvnb|Lipovača|2012|p=22}}</ref>。
Haskell では、関数合成の二項演算子を使って'''ポイントフリースタイル'''で関数を定義することができる<ref>{{harvnb|Lipovača|2012|p=22}}</ref>。関数をポイントフリースタイルで定義すると、データより関数に目が行くようになり、どのようにデータが移り変わっていくかではなく、どんな関数を合成して何になっているかということへ意識が向くため、定義が読みやすく簡潔になることがある<ref>{{harvnb|Lipovača|2012|p=22}}</ref>。関数が複雑になりすぎると、ポイントフリースタイルでは逆に可読性が悪くなることもある<ref>{{harvnb|Lipovača|2012|p=22}}</ref>。


=== 言語 ===
=== モナド ===
{{main|モナド (プログラミング)}}「モナドは値と計算を文脈で包むものだ<ref name=":1">{{Cite web|url=https://wiki.haskell.org/Monad_tutorials_timeline#year_2021|title=Monad tutorials timeline, year2011|accessdate=2021-1}}</ref>」「モナドには三通りある―計算順序の制御、副作用の制御、コンテナとしてのそれ<ref name=":1">{{Cite web|url=https://wiki.haskell.org/Monad_tutorials_timeline#year_2021|title=Monad tutorials timeline, year2011|accessdate=2021-1}}</ref>」「クライスリ圏はモナドへのもう一つの基本視点だ<ref name=":1">{{Cite web|url=https://wiki.haskell.org/Monad_tutorials_timeline#year_2021|title=Monad tutorials timeline, year2011|accessdate=2021-1}}</ref>」「モナドは文脈の型である―文脈に値を注入し、文脈内で関数を適用する<ref name=":1">{{Cite web|url=https://wiki.haskell.org/Monad_tutorials_timeline#year_2021|title=Monad tutorials timeline, year2011|accessdate=2021-1}}</ref>」「モナドは他の型を包むラッパー型である―内側の型を構造化し、内側の型の計算を合成する<ref name=":1">{{Cite web|url=https://wiki.haskell.org/Monad_tutorials_timeline#year_2021|title=Monad tutorials timeline, year2011|accessdate=2021-1}}</ref>」「モナドは自己関手の圏のただのモノイド<ref>Philip Wadler</ref>」


モナドは概ね、値を包んだコンテナの計算を合成する仕組みとイメージできる。コンテナはあくまで抽象的な概念であり、環境、状態、文脈とも解釈される。コンテナは[[副作用 (プログラム)|副作用]]の記録媒体としても扱われて、その中で得られた値をラッピングし、それは自由に取り出して次の計算に使える。値のコンテナ収納をここではunitと呼ぶ。<code>unit: a->ma</code>となる。<code>ma</code>は<code>[a]</code>と読み替えてもよい。コンテナは入れ子にできるので<code>mma</code>や<code><nowiki>[[a]]</nowiki></code>にもなる。これには[[圏論]]の[[関手]]の概念が用いられている。<code>mma</code>を<code>ma</code>に整理することをここではjoinと呼ぶ。これには[[代数的構造]]の[[モノイド]]の概念が用いられている。unitとjoinの組み合わせで<code>m</code>入れ子を内部で揃えることをここではflatmapと呼ぶ。
関数型プログラミング言語とは、関数型プログラミングを推奨している[[プログラミング言語]]である<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。略して関数型言語ともいう<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。全ての関数が参照透過性を持つようなものを、特に{{仮リンク|純粋関数型プログラミング言語|en|purely functional programming language}}という<ref>{{harvnb|本間|類地|逢坂|2017|p=5}}</ref>。そうでないものを非純粋であるという<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。


モナドの源流は[[クライスリ圏]]である。関数<code>f': a->b</code>とunitを融合した[[クライスリ圏|クライスリ射]]<code>f</code>があった。クライスリ射<code>f: a->mb</code>をunit値<code>ma</code>に適用できるflatmapの形成がモナドの基本かつ本質であり、それによって値の構造化やその計算の合成といった無限の拡張性が生まれる。
関数型プログラミング言語の多くは、言語の設計において何らかの形で[[ラムダ計算]]が関わっている<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>。ラムダ計算はコンピュータの計算をモデル化する体系の一つであり、記号の列を規則に基づいて変換していくことで計算が行われるものである<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>。


それへの第1ステップは、[[クライスリ圏|クライスリ射]]の合成<code><=<: (b->mc)->(a->mb)->(a->mc)</code>であり、これは<code>join . unit (b->mc).(a->mb)</code>とされる。<code>.</code>は関数合成演算子である。関数合成の概念は以下の三つ組でも[[テンソル積]]として使用される。このようなjoinが可能なのは、その三つ組<code>(f, <=<, unit)</code>が結合律と左右単位律（モナド則）を満たして[[モノイド]]相当になっているからである。第2ステップは、クライスリ合成の第1引数のクライスリ射をunit値にした拡張演算子<code>=<<: (b->mc)->mb->mc</code>である。これは<code>(join . unit b->mc) mb</code>とされる。その三つ組<code>(f, unit, =<<)</code>も結合律と左右単位律（モナド則）を満たす。それはクライスリトリプルと呼ばれ、<code>=<< f</code>はクライスリスター<code>f*: mb->mc</code>と呼ばれる。<code>=<<</code>の逆引数版が、本命のモナドflatmap<code>>>=: mb->(b->mc)->mc</code>である。モナドflatmapは、その返り値を後続flatmapの引数にして合成できるようにもなった。三つ組は<code>(m, join, unit)</code>になる。<code>m</code>は<code>*->*</code>[[カインド (型理論)|カインド]]の型であり、自己型/自己派生型に依存しているので自己関手（同型→同型）の[[圏 (数学)|圏]]の[[対象 (圏論)|対象]]に例えられる。unit値<code>ma</code>はモナド値と言われる。

モナド値の型は構造を持つ。上述のコンテナに入れるだけのシンプル構造の<code>a->ma</code>は付加モナドと言われる。ListモナドやMaybeモナドがそれに当たる。コンテナを環境、状態、文脈といった抽象構造にしたものはコモナドと言われる。例えば、例外モナド<code>a->m(a+e)</code>、Readerモナド<code>a->(e->ma)</code>、Writerモナド<code>a->m(w×a)</code>、状態モナド<code>a->(s->m(a×s))</code>、継続モナド<code>a->((a->mr)->mr)</code>などがある。それらの抽象構造は、[[副作用 (プログラム)|副作用]]を封入し、また[[線形論理]]の媒体にもなって[[参照透過性]]を維持する働きがある。

== 手続き型プログラミングとの比較 ==
[[C|C 言語]]や [[Java]] 、 [[JavaScript]] 、 [[Python]] 、 [[Ruby]] などの2017年現在に使われている言語の多くは、手続き型の文法を持っている<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。そのような言語では、文法として式 (expression) と文 (statement) を持つ<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。ここでの式は、計算を実行して結果を得るような処理を記述するための文法要素であり、加減乗除や関数呼び出しなどから構成されている<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。ここでの文は、何らかの動作を行うようにコンピュータへ指示するための文法要素であり、条件分岐の [[if文|if 文]]やループの [[for文|for 文]]と [[while文|while 文]]などから構成されている<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。手続き型の文法では、式で必要な計算を進め、その結果を元にして文でコンピュータ命令を行うという形で、プログラムを記述する<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。このように、[[手続き型言語]]で重要なのは文である<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。

それに対して、[[関数型言語]]で重要なのは式である<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。関数型言語のプログラムはたくさんの式で構成され、プログラムそのものも一つの式である<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。たとえば、 Haskell では、プログラムの処理の記述において文は使われず、外部の定義を取り込む import 宣言も処理の一部として扱えない<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。関数型言語におけるプログラムの実行とは、プログラムを表す式の計算を進めて、その結果として値 (value) を得ることである<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。式を計算することを、'''評価する''' (evaluate) という<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。

手続き型言語ではコンピュータへの指示を文として上から順に並べて書くのに対して、関数型言語では数多く定義した細かい式を組み合わせてプログラムを作る<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。手続き型言語では文が重要であり、関数型言語では式が重要である<ref>{{harvnb|本間|類地|逢坂|2017|pp=22–23}}</ref>。

式と文の違いとして、型が付いているかどうかというのがある<ref>{{harvnb|本間|類地|逢坂|2017|pp=22–23}}</ref>。式は型を持つが、文は型を持たない<ref>{{harvnb|本間|類地|逢坂|2017|pp=22–23}}</ref>。プログラム全てが式から構成されていて、強い静的型付けがされているのならば、プログラムの全体が細部まで型付けされることになる<ref>{{harvnb|本間|類地|逢坂|2017|pp=22–23}}</ref>。このように細部まで型付けされているようなプログラムは堅固なものになる<ref>{{harvnb|本間|類地|逢坂|2017|pp=22–23}}</ref>。

== 代表的な関数型言語 ==
{| class="wikitable sortable"<!-- 名前の欄には、それが関数型プログラミング言語であるという出典を付ける。型付けの欄には、その記述の根拠になる出典を付ける。評価戦略の欄には、その記述の根拠になる出典を付ける。純粋性の欄には、それが純粋か非純粋かの出典を付ける。理論的背景の欄には、その記述の根拠になる出典を付ける。 -->
{| class="wikitable sortable"<!-- 名前の欄には、それが関数型プログラミング言語であるという出典を付ける。型付けの欄には、その記述の根拠になる出典を付ける。評価戦略の欄には、その記述の根拠になる出典を付ける。純粋性の欄には、それが純粋か非純粋かの出典を付ける。理論的背景の欄には、その記述の根拠になる出典を付ける。 -->
|+ 関数型プログラミング言語
|-
|-
! 名前
! 名前
!公開年
! 型付け
! 型付け
! 純粋性
! 純粋性
67行目: 118行目:
! 理論的背景
! 理論的背景
|-
|-
|[[APL]]
| [[Clean]]{{要出典|date=2021年3月}}
|1964
| 静的型付け{{要出典|date=2021年3月}}
|動的
| 純粋{{要出典|date=2021年3月}}
| 遅延評価{{要出典|date=2021年3月}}
|
|
|先行
|
|-
|[[Agda]]
|2007
|静的型付け
|純粋
|先行
|[[直観主義型理論]]
|-
|-
|[[Rust (プログラミング言語)|Rust]]
| [[Clojure]]{{要出典|date=2021年3月}}
|2010
| 動的型付け{{要出典|date=2021年3月}}
|静的型付け
| 非純粋{{要出典|date=2021年3月}}
|
| 正格評価{{要出典|date=2021年3月}}
|先行
|
|
|-
|-
|[[JavaScript]]
| [[Erlang]]{{要出典|date=2021年3月}}
|1996
| 動的型付け{{要出典|date=2021年3月}}
|動的型付け
| 非純粋{{要出典|date=2021年3月}}
|
| 正格評価{{要出典|date=2021年3月}}
|先行
|
|
|-
|-
|[[R言語|R]]
| [[F Sharp|F#]]{{要出典|date=2021年3月}}
|1993
| 静的型付け{{要出典|date=2021年3月}}
|動的
| 非純粋{{要出典|date=2021年3月}}
|
| 正格評価{{要出典|date=2021年3月}}
|先行
|
|-
|[[Common Lisp]]
|1984
|動的
|
|先行
|
|-
|[[Racket]]
|1995
|動的
|
|先行
|
|-
|[[Dylan]]
|1993
|動的
|
|先行
|
|-
|Caml
|1985
|静的型付け
|
|先行
|
|-
|[[FP (プログラミング言語)|FP]]
|1977
|動的
|純粋
|先行
|
|-
|[[ISWIM]]
|1966
|静的型付け
|
|先行
|
|-
| [[Clean]]
|1987
| 静的型付け
| 純粋
| 遅延評価
|
|-
| [[Clojure]]
|2007
| 動的
|
| 先行
|
|-
| [[Erlang]]
|1986
| 動的
|
| 先行
|
|-
| [[F Sharp|F#]]
|2005
| 静的型付け
|
| 先行
|
|
|-
|-
| [[Haskell]]<ref>{{harvnb|本間|類地|逢坂|2017|p=2}}</ref>
| [[Haskell]]<ref>{{harvnb|本間|類地|逢坂|2017|p=2}}</ref>
|1990
| 静的型付け<ref>{{harvnb|本間|類地|逢坂|2017|p=2}}</ref>
| 静的型付け<ref>{{harvnb|本間|類地|逢坂|2017|p=2}}</ref>
| 純粋<ref>{{harvnb|本間|類地|逢坂|2017|p=2}}</ref>
| 純粋<ref>{{harvnb|本間|類地|逢坂|2017|p=2}}</ref>
| 遅延評価<ref>{{harvnb|本間|類地|逢坂|2017|p=2}}</ref>
| 遅延評価
| [[型付きラムダ計算]]<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>
| 型付きラムダ計算<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>
|-
|-
| Idris
| [[Idris]]{{要出典|date=2021年3月}}
|2007
| 静的型付け{{要出典|date=2021年3月}}
| 静的型付け
| 純粋{{要出典|date=2021年3月}}
| 純粋
| 正格評価{{要出典|date=2021年3月}}
| 先行
| 型付きラムダ計算{{要出典|date=2021年3月}}
|-
|
| [[Lazy K]]{{要出典|date=2021年3月}}
| 型なし{{要出典|date=2021年3月}}
| 純粋{{要出典|date=2021年3月}}
| 遅延評価{{要出典|date=2021年3月}}
| コンビネータ論理{{要出典|date=2021年3月}}
|-
|-
| [[LISP]]<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>
| [[LISP]]<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>
|1958
| 動的型付け{{要出典|date=2021年3月}}
| 動的
| 非純粋{{要出典|date=2021年3月}}
|
| 方言による{{要出典|date=2021年3月}}
| 先行
| 型無しラムダ計算<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>
| [[型無しラムダ計算]]<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>
|-
|-
| [[Miranda]]{{要出典|date=2021年3月}}
| [[Miranda]]
|1985
| 静的型付け{{要出典|date=2021年3月}}
| 静的型付け
| 純粋{{要出典|date=2021年3月}}
| 純粋
| 遅延評価{{要出典|date=2021年3月}}
| 遅延評価
|
|
|-
|-
| [[ML (プログラミング言語)|ML]]{{要出典|date=2021年3月}}
| [[ML (プログラミング言語)|ML]]
|1973
| 静的型付け{{要出典|date=2021年3月}}
| 静的型付け
| 非純粋{{要出典|date=2021年3月}}
|
| 先行評価{{要出典|date=2021年3月}}
| 先行
|
|
|-
|-
| [[Standard ML|SML]]{{要出典|date=2021年3月}}
| [[Standard ML]]
|1983
| 静的型付け{{要出典|date=2021年3月}}
| 静的型付け
| 非純粋{{要出典|date=2021年3月}}
|
| 正格評価{{要出典|date=2021年3月}}
| 先行
|
|
|-
|-
| [[OCaml]]{{要出典|date=2021年3月}}
| [[OCaml]]
|1996
| 静的型付け{{要出典|date=2021年3月}}
| 静的型付け
| 非純粋{{要出典|date=2021年3月}}
|
| 正格評価{{要出典|date=2021年3月}}
| 先行
|
|
|-
|-
| [[Scala]]{{要出典|date=2021年3月}}
| [[Scala]]
|2003
| 静的型付け{{要出典|date=2021年3月}}
| 静的型付け
| 非純粋{{要出典|date=2021年3月}}
|
| 正格評価{{要出典|date=2021年3月}}
| 先行
|
|
|-
|-
| [[Scheme]]{{要出典|date=2021年3月}}
| [[Scheme]]
|1975
| 動的型付け{{要出典|date=2021年3月}}
| 動的
| 非純粋{{要出典|date=2021年3月}}
|
| 正格評価{{要出典|date=2021年3月}}
| 先行
|
|
|-
|-
| [[Unlambda]]{{要出典|date=2021年3月}}
| [[Unlambda]]
|1999
| 型なし{{要出典|date=2021年3月}}
| 型なし
| 非純粋{{要出典|date=2021年3月}}
|
| 正格評価{{要出典|date=2021年3月}}
| 先行
| コンビネータ論理{{要出典|date=2021年3月}}
| [[コンビネータ論理]]
|}
|}

=== 手続き型プログラミングとの比較 ===

[[C|C 言語]]や [[Java]] 、 [[JavaScript]] 、 [[Python]] 、 [[Ruby]] などの2017年現在に使われている言語の多くは、手続き型の文法を持っている<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。そのような言語では、文法として式 (expression) と文 (statement) を持つ<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。ここでの式は、計算を実行して結果を得るような処理を記述するための文法要素であり、加減乗除や関数呼び出しなどから構成されている<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。ここでの文は、何らかの動作を行うようにコンピュータへ指示するための文法要素であり、条件分岐の [[if文|if 文]]やループの [[for文|for 文]]と [[while文|while 文]]などから構成されている<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。手続き型の文法では、式で必要な計算を進め、その結果を元にして文でコンピュータ命令を行うという形で、プログラムを記述する<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。このように、[[手続き型言語]]で重要なのは文である<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。

それに対して、[[関数型言語]]で重要なのは式である<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。関数型言語のプログラムはたくさんの式で構成され、プログラムそのものも一つの式である<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。たとえば、 Haskell では、プログラムの処理の記述において文は使われず、外部の定義を取り込む import 宣言も処理の一部として扱えない<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。関数型言語におけるプログラムの実行とは、プログラムを表す式の計算を進めて、その結果として値 (value) を得ることである<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。式を計算することを、'''評価する''' (evaluate) という<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。

手続き型言語ではコンピュータへの指示を文として上から順に並べて書くのに対して、関数型言語では数多く定義した細かい式を組み合わせてプログラムを作る<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。手続き型言語では文が重要であり、関数型言語では式が重要である<ref>{{harvnb|本間|類地|逢坂|2017|pp=22–23}}</ref>。

式と文の違いとして、型が付いているかどうかというのがある<ref>{{harvnb|本間|類地|逢坂|2017|pp=22–23}}</ref>。式は型を持つが、文は型を持たない<ref>{{harvnb|本間|類地|逢坂|2017|pp=22–23}}</ref>。プログラム全てが式から構成されていて、強い静的型付けがされているのならば、プログラムの全体が細部まで型付けされることになる<ref>{{harvnb|本間|類地|逢坂|2017|pp=22–23}}</ref>。このように細部まで型付けされているようなプログラムは堅固なものになる<ref>{{harvnb|本間|類地|逢坂|2017|pp=22–23}}</ref>。


== 歴史 ==
== 歴史 ==
'''1930年代'''


関数型プログラミングのルーツは、[[アロンゾ・チャーチ]]が1932年<ref group="注釈">{{harv|Church|1932}}</ref>と1941年<ref group="注釈">{{harv|Church|1941}}</ref>に発表した[[ラムダ計算]]の研究とされている<ref>{{harvnb|Hudak|1989|p=363}}</ref>。電子計算機発明以前のラムダ計算は、当然ながらコンピュータプログラムに使われることはなかったが、後のプログラミング言語のモデルにされたことで最初の関数型言語としての認識も得ている<ref>{{harvnb|Hudak|1989|p=363}}</ref>。1989年現在までに登場した関数型言語の多くは、ラムダ計算に装飾を加えた発展形と見なすことができる<ref>{{harvnb|Hudak|1989|p=363}}</ref>。また、ラムダ計算と同様に関数型プログラミングの背景と見なされている理論的公式に、モイセイ・シェインフィンケリと[[ハスケル・カリー]]が1920～30年代に発表した[[コンビネータ論理]]がある<ref>{{cite book|author1=Haskell Brooks Curry|author2=Robert Feys|title=Combinatory Logic|url=https://archive.org/details/combinatorylogic0002curr|url-access=registration|access-date=10 February 2013|year=1958|publisher=North-Holland Publishing Company}}</ref>。
=== 1930年代 ===


'''1950年代'''
{{節スタブ|date=2021年3月}}


1950年代後半に[[マサチューセッツ工科大学]]の[[ジョン・マッカーシー]]が発表した「[[LISP]]」は最初の高水準な関数型言語として知られており<ref>{{cite conference|first=John|last=McCarthy|author-link=John McCarthy (computer scientist)|title=History of Lisp|journal=History of Programming Languages|pages=173–185|date=June 1978|url=http://jmc.stanford.edu/articles/lisp/lisp.pdf|doi=10.1145/800025.808387|place=Los Angeles, CA}}</ref>、関数プログラミング史の中でも特別な位置付けにある<ref>{{harvnb|Hudak|1989|p=367}}</ref>。LISPはラムダ計算ベースという認識が一般的であるが、1978年のマッカーシーの言及によると<ref group="注釈">{{harv|McCarthy|1978}}</ref>LISPの開発では[[匿名関数]]を表現したいという動機の方が先にあり、ラムダ計算の選択はそのための手段に過ぎなかったという<ref>{{harvnb|Hudak|1989|pp=367–368}}</ref>。
関数型言語の開発において、[[アロンゾ・チャーチ]]が1932年<ref group="注釈">{{harv|Church|1932}}</ref>と1941年<ref group="注釈">{{harv|Church|1941}}</ref>に発表した[[ラムダ計算]]の研究ほど基本的で重要な影響を与えたものはない<ref>{{harvnb|Hudak|1989|p=363}}</ref>。ラムダ計算は、それが考え出された当時は[[プログラム (コンピュータ)|プログラム]]を実行するような[[コンピュータ]]が存在しなかったために[[プログラミング言語]]として見なされなかったにも関わらず、今では最初の関数型言語とされている<ref>{{harvnb|Hudak|1989|p=363}}</ref>。1989年現在の関数型言語は、そのほとんどがラムダ計算に装飾を加えたものとして見なせる<ref>{{harvnb|Hudak|1989|p=363}}</ref>。


=== 1950年代 ===
'''1960年代'''

{{節スタブ|date=2021年3月}}

1950年代後半に[[ジョン・マッカーシー]]が発表した [[LISP]] は関数型言語の歴史において重要である<ref>{{harvnb|Hudak|1989|p=367}}</ref>。ラムダ計算は LISP の基礎であると言われるが、マッカーシー自身が1978年<ref group="注釈">{{harv|McCarthy|1978}}</ref>に説明したところによると、[[匿名関数]]を表現したいというのが最初にあって、その手段としてマッカーシーはチャーチのラムダ計算を選択したに過ぎない<ref>{{harvnb|Hudak|1989|pp=367–368}}</ref>。

=== 1960年代 ===


歴史的に言えば、 [[LISP]] に続いて関数型プログラミングパラダイムへ刺激を与えたのは、1960年代半ばの{{仮リンク|ピーター・ランディン|en|Peter Landin}}の成果である<ref>{{harvnb|Hudak|1989|p=371}}</ref>。ランディンの成果は[[ハスケル・カリー]]と[[アロンゾ・チャーチ]]に大きな影響を受けていた<ref>{{harvnb|Hudak|1989|p=371}}</ref>。ランディンの初期の論文は、ラムダ計算と、機械および高級言語 ([[ALGOL 60]]) との関係について議論している<ref>{{harvnb|Hudak|1989|p=371}}</ref>。ランディンは、1964年<ref group="注釈">{{harv|Landin|1964}}</ref>に、 [[SECDマシン|SECD マシン]]と呼ばれる抽象的な機械を使って機械的に式を評価する方法を論じ、1965年<ref group="注釈">{{harv|Landin|1965}}</ref>に、ラムダ計算で ALGOL 60 の非自明なサブセットを形式化した<ref>{{harvnb|Hudak|1989|p=371}}</ref>。1966年<ref group="注釈">{{harv|Landin|1966}}</ref>にランディンが発表した [[ISWIM]]（If You See What I Mean の略）という言語（群）は、間違いなく、これらの研究の成果であり、[[構文]]や[[意味論]]において多くの重要なアイデアを含んでいた<ref>{{harvnb|Hudak|1989|p=371}}</ref>。 ISWIM は、ランディン本人によれば、「 LISP を、その名前にも表れた[[リスト (抽象データ型)|リスト]]へのこだわり、手作業のメモリ割り当て、ハードウェアに依存した教育方法、[[S式|重い括弧]]、伝統への妥協、から解放しようとする試みとして見ることができる」<ref>{{harvnb|Hudak|1989|p=371}}</ref>。関数型言語の歴史において ISWIM は次のような貢献を果たした<ref>{{harvnb|Hudak|1989|pp=371–372}}</ref>。
歴史的に言えば、 [[LISP]] に続いて関数型プログラミングパラダイムへ刺激を与えたのは、1960年代半ばの{{仮リンク|ピーター・ランディン|en|Peter Landin}}の成果である<ref>{{harvnb|Hudak|1989|p=371}}</ref>。ランディンの成果は[[ハスケル・カリー]]と[[アロンゾ・チャーチ]]に大きな影響を受けていた<ref>{{harvnb|Hudak|1989|p=371}}</ref>。ランディンの初期の論文は、ラムダ計算と、機械および高級言語 ([[ALGOL 60]]) との関係について議論している<ref>{{harvnb|Hudak|1989|p=371}}</ref>。ランディンは、1964年<ref group="注釈">{{harv|Landin|1964}}</ref>に、 [[SECDマシン|SECD マシン]]と呼ばれる抽象的な機械を使って機械的に式を評価する方法を論じ、1965年<ref group="注釈">{{harv|Landin|1965}}</ref>に、ラムダ計算で ALGOL 60 の非自明なサブセットを形式化した<ref>{{harvnb|Hudak|1989|p=371}}</ref>。1966年<ref group="注釈">{{harv|Landin|1966}}</ref>にランディンが発表した [[ISWIM]]（If You See What I Mean の略）という言語（群）は、間違いなく、これらの研究の成果であり、[[構文]]や[[意味論]]において多くの重要なアイデアを含んでいた<ref>{{harvnb|Hudak|1989|p=371}}</ref>。 ISWIM は、ランディン本人によれば、「 LISP を、その名前にも表れた[[リスト (抽象データ型)|リスト]]へのこだわり、手作業のメモリ割り当て、ハードウェアに依存した教育方法、[[S式|重い括弧]]、伝統への妥協、から解放しようとする試みとして見ることができる」<ref>{{harvnb|Hudak|1989|p=371}}</ref>。関数型言語の歴史において ISWIM は次のような貢献を果たした<ref>{{harvnb|Hudak|1989|pp=371–372}}</ref>。
199行目: 320行目:
[[ケネス・アイバーソン]]が1962年<ref group="注釈">{{harv|Iverson|1962}}</ref>に発表した [[APL]] は、純粋な関数型プログラミング言語ではないが、その関数型的な部分を取り出したサブセットがラムダ式に頼らずに関数型プログラミングを実現する方法の一例であるという点で、関数型プログラミング言語の歴史を考察する際に言及する価値はある<ref>{{harvnb|Hudak|1989|p=372}}</ref>。実際に、アイバーソンが APL を設計した動機は、配列のための代数的なプログラミング言語を開発したいというものであり、アイバーソンのオリジナル版は基本的に関数型的な記法を用いていた<ref>{{harvnb|Hudak|1989|p=372}}</ref>。その後の APL では、いくつかの命令型的な機能が追加されている<ref>{{harvnb|Hudak|1989|p=372}}</ref>。
[[ケネス・アイバーソン]]が1962年<ref group="注釈">{{harv|Iverson|1962}}</ref>に発表した [[APL]] は、純粋な関数型プログラミング言語ではないが、その関数型的な部分を取り出したサブセットがラムダ式に頼らずに関数型プログラミングを実現する方法の一例であるという点で、関数型プログラミング言語の歴史を考察する際に言及する価値はある<ref>{{harvnb|Hudak|1989|p=372}}</ref>。実際に、アイバーソンが APL を設計した動機は、配列のための代数的なプログラミング言語を開発したいというものであり、アイバーソンのオリジナル版は基本的に関数型的な記法を用いていた<ref>{{harvnb|Hudak|1989|p=372}}</ref>。その後の APL では、いくつかの命令型的な機能が追加されている<ref>{{harvnb|Hudak|1989|p=372}}</ref>。


'''1970年代'''
== 脚注 ==


1973年に[[エディンバラ大学]]の[[ロビン・ミルナー]]が[[静的型付け]]の「[[ML (プログラミング言語)|ML]]」を開発した。同大学では[[クリーネの再帰定理]]をプログラミング投影するための「NPL」も開発された<ref>R.M. Burstall. Design considerations for a functional programming language. Invited paper, Proc. Infotech State of the Art Conf. "The Software Revolution", Copenhagen, 45–57 (1977)</ref>。同時期にマサチューセッツ工科大学で[[ガイ・スティール・ジュニア|ガイ・スティール]]と[[ジェラルド・ジェイ・サスマン|ジェラルド・サスマン]]が「[[Scheme]]」を開発した。ここでは[[末尾再帰]]が実装された。1977年に[[ジョン・バッカス]]は、[[チューリング賞]]表彰式で「Can Programming Be Liberated From the von Neumann Style? -A Functional Style and Its Algebra of Programs-」と題したスピーチを行った<ref name="Backus 1977">{{Cite journal|last1=Backus|first1=J.|year=1978|title=Can programming be liberated from the von Neumann style?: A functional style and its algebra of programs|journal=Communications of the ACM|volume=21|issue=8|pages=613–641|doi=10.1145/359576.359579|doi-access=free}}</ref>。「プログラミングはノイマン型から解放され得るか？関数型スタイルとプログラムの代数学」と訳せるこのスピーチは、世間の関数型プログラミングへの関心を高めてその研究促進の契機になった。
{{脚注ヘルプ}}


'''1980年代'''
=== 注釈 ===


1982年にHindley–Milner型システムが確立され、関数型プログラミングにパラメトリック多相にも対応可能で実用的になった[[型推論]]の機能をもたらした。1983年にHindley–Milner型システムを導入した「[[Standard ML]]」が開発され、これは関数型プログラミングの主流を[[LISP]]以来の[[動的型付け]]から静的型付けにシフトさせた。1980年代に[[ペール・マルティン＝レーフ|マルティン・レーフ]]が考案した[[直観主義型理論|直感主義型理論]]は、関数型プログラミングに[[依存型]]の概念をもたらして、特に2000年代世代の関数型言語に大きな影響を与えた。1986年開発の「[[Erlang]]」の[[並行プログラミング]]特性は注目を集めて、元祖[[オブジェクト指向]]のメッセージングとの関連性も後に提起された。1985年にデビッド・ターナーが[[遅延評価]]を基本にした純粋関数型言語「[[Miranda]]」を開発した。これは1987年から関数型言語研究の[[オープン標準]]下で開発が始められた「[[Haskell]]」に大きな影響を及ぼしている。

== 脚注 ==
{{脚注ヘルプ}}
{{Notelist}}
{{Notelist}}


=== 出典 ===
== 出典 ==

{{Reflist}}
{{Reflist}}


== 参考文献 ==
== 参考文献 ==

* {{Cite Q|Q55890017|last=Church|first=Alonzo}}
* {{Cite Q|Q55890017|last=Church|first=Alonzo}}
* {{Cite Q|Q105884272|last=Church|first=Alonzo}}
* {{Cite Q|Q105884272|last=Church|first=Alonzo}}
225行目: 348行目:


== 外部リンク ==
== 外部リンク ==

* [http://www.sampou.org/haskell/article/whyfp.html なぜ関数プログラミングは重要か]
* [http://www.sampou.org/haskell/article/whyfp.html なぜ関数プログラミングは重要か]
* [http://www.topxml.com/xsl/articles/fp/ {{lang|en|The Functional Programming Language XSLT - A proof through examples}}]{{リンク切れ|date=2021年3月}}
* [http://www.topxml.com/xsl/articles/fp/ {{lang|en|The Functional Programming Language XSLT - A proof through examples}}]{{リンク切れ|date=2021年3月}}


== 関連項目 ==
== 関連項目 ==

* [[カリー化]]

{{プログラミング言語の関連項目}}
{{プログラミング言語の関連項目}}

{{Normdaten}}
{{Normdaten}}

{{DEFAULTSORT:かんすうかたふろくらみんく}}
{{DEFAULTSORT:かんすうかたふろくらみんく}}
[[Category:関数型プログラミング|*]]
[[Category:関数型プログラミング|*]]

2021年12月30日 (木) 03:18時点における版

プログラミング・パラダイム

命令型プログラミング

宣言型プログラミング

マルチパラダイム

関数型プログラミング（かんすうがたプログラミング、英: functional programming）とは、数学的な関数の適用を中心にしたプログラミングパラダイム、またはプログラミングのスタイルである[1][2]。 関数プログラミングとも邦訳される[3]。このスタイルに準拠した言語は、関数型プログラミング言語または関数型言語（英: functional language）と呼ばれる[4]。

数学的な関数は、副作用を排除して参照透過性を順守している。参照透過性順守の度合いは言語ごとに異なっている。副作用を容認している関数型言語も多く、それらは非純粋と言われる[5]。数学的な関数の実装に専念している本来のものは、純粋関数型言語（英語版）と呼ばれている[6]。関数型言語の多くはその設計にラムダ計算が関わっている。ラムダ計算は、計算を記号列の規則的な変換として模型化した形式体系である[7]。

特徴

関数型プログラムは、数学的な関数を値に適用して別の値を得るという機構を組み合わせての宣言的な式の集まりになる。関数の適用とは、引数を入れて関数を呼び出して返り値を出すことと同じ意味になる[2]。返り値を出すことは関数の評価と表現される[8]。数学的な関数とは参照透過な関数と同義である[9]。

宣言的な式では、例えば関数記号と引数記号の適用部分を抜粋した表記の取り扱いと、その表記の詳細な処理内容の把握を分離することができる。その数式相当の性質はしばしば表示的意味論で説明される。 

(* 階乗の数式 *)
0! = 1
n! = n×(n-1)!	

(* そのプログラム投影 *)
fun func 0 = 1
  | func n = n * func (n - 1)

上記の例では、関数funcは参照透過であり再帰を用いており、その再帰関数は二項演算子-を引数に取っている高階関数になっている。-は第一級関数と同等である。再帰での0とそれ以外の分岐および停止性問題はパターンマッチングで解決されている。数学的な関数を中心にした宣言的な式では、自然とそれらのテクニックが必要になり、それ以外にも主に数学背景の様々なテクニックが導入されることになる[10]。

関数型プログラミングの最大特徴である数学的、宣言的、参照透過といった概念および意味は、このような実践の反復で徐々に把握していく。

参照透過性

詳細は「参照透過性」を参照

参照透過性とは、数学的な関数と同じように同じ値を返す式を与えたら必ず同じ値を返すような性質である[11]。次の square 関数は、 2 となるような式を与えれば必ず 4 を返し、 3 となるような式を与えれば必ず 9 を返し、いかなる状況でも別の値を返すということはなく、これが参照透過性を持つ関数の一例となる[12]。 

def square(n):
  return n ** 2

次の countup 関数は、同じ 1 を渡しても、それまでに countup 関数がどのような引数で呼ばれていたかによって、返り値が 1, 2, 3, ... と変化するため、引数の値だけで結果の値が定まらないような参照透過性のない関数であり、数学的な関数とはいえない[13]。 

counter = 0
def countup(n):
  global counter
  counter += n
  return counter

参照透過性を持つことは、その関数が状態を持たないことを保証する[14]。状態を持たない数学的な関数は、並列処理を実現するのに適している[15]。関数型プログラミング言語の内で、全ての関数が参照透過性を持つようなものを純粋関数型プログラミング言語という[16]。

第一級関数と高階関数

詳細は「第一級関数」および「高階関数」を参照

関数型プログラミングの関数は、他の関数への引数や返り値にもできるのが標準である。これを第一級という。他の関数を自身の引数や返り値にできる関数は、高階といわれる。第一級関数は値と同等に扱われるので、変数に束縛したりデータ構造に当てはめることができる[17]。値に名前が付けられないのと同様に名前無しの関数も定義できて、それは式内スコープ使用前提の無名関数になる[18]。第一級関数は、関数の型（英語版）で型付けされた値として扱われる[19]。

高階関数の性質は、カリー化や部分適用（英語版）などの実装を可能にする。関数を一つずつ引数に適用させる形式にするのをカリー化と呼ぶ。引数への適用を途中で止めたままにするのが部分適用である。それは変数に束縛して保存でき、後続式で残り引数を適用して最終的な返り値にできる。カリー化は、先行関数の返り値と後続関数の第一引数を連結した関数合成（英語版）を可能にする。

第一級関数の性質は、クロージャや継続などの実装を可能にする。クロージャは後続式で引数を与えられることを前提にした抽象的な値を表現する。クロージャはしばしば特定の状態を囲い込んでそれをデータ抽象化する。継続は後続式で評価されることを前提にした関数式のスナップショットを実現する。継続は計算式の挿入や入れ替えや再利用による計算フローの制御に役立てられる。

純粋関数

参照透過性を順守した関数は、純粋関数（英語版）と呼ばれる。これは機能と言うよりも、関数型プログラミングが目指すべきコンセプトに近い[20]。純粋関数は、同じ引数から常に同じ返り値が算出されるという冪等性を保証し、その計算が外部状態の影響を受けず、また外部状態に影響を与えないという副作用の排除を保証している[21]。外部状態はグローバル変数と読み替えてもよい。純粋関数はローカル変数などの内部状態も持たない。

純粋関数とは、冪等な計算式と可変な状態を完全に分離する機構であり、冪等な計算式は不変な状態としての定数群をしばしば内包している。この概念はinvariantやイミュータブルにも繋がっている。コンパイル最適化の対象としても適当であり、純粋関数はコードの最適化で重要な役割を果たす。

純粋関数は、ミュータブルな状態を参照透過に処理するためのアプローチでもある。純粋関数は引数から状態を扱い、遷移させた状態を返り値にする。その参照透過性の維持ロジックには線形論理などが使われる。状態の構造化には適切性論理などが使われる。それらの部分構造論理をより最適化したデザインパターンには圏論由来のモナドがある。

再帰

詳細は「再帰」を参照

関数型プログラミングの反復処理とループ処理は専ら、関数の再帰を通して行われる。再帰は、無限の項を有限の式で扱えるようにする手法である[22]。再帰で取り沙汰されるスタックオーバーフロー問題は、末尾再帰によるコード最適化で解決されることが多い[23]。再帰は関数型のアルゴリズムの最要点であり[24]、しばしばパターンマッチングやガードと組み合わせて使用される。再帰はデータ構造でも多用され、こちらでは無限の要素を有限の構造で扱えるようにする手法になり、これは再帰データ型とも呼ばれる。

先行評価と遅延評価

詳細は「評価戦略」を参照

関数型プログラミングでは、引数に適用した関数式を評価するタイミングの区別が重視される。引数確定と同時に評価して返り値にするのが先行評価である。引数確定してもその返り値が本当に必要になるまで評価を先送りにして、関数式の状態のままにしておくのが遅延評価である。

先行と遅延の区別は、引数渡しされる第一級関数でよく用いられる。全引数を評価してから関数コールするのが先行評価の用例になり、未評価の引数があるままで関数コールするのが遅延評価の用例になる。必要になった時に計算するという遅延評価は、計算量を減らしてのプロセスの軽量化をもたらす。また、評価を遅延した関数式を保管して別途使用ないし反復使用するという機能（継続、ジェネレータ、例外、コルーチン）は、計算解釈順序を操作してのプロセスの柔軟化をもたらす。

型システム

詳細は「型システム」を参照

Hindley–Milner型システムの登場以降の関数型プログラミングは、型付きラムダ計算を背景にした静的型付けが標準になっている。Lisp系で実践されていた型無しラムダ計算を背景にした動的型付けは、その対極に位置付けられている。Hindley–Milner型システム（英語版）がもたらした型推論もまた関数型プログラミングの標準になっている。型推論ルールでの各変数の型は、それに束縛される値を導出した各項と各評価値から演繹的に判別されるので、各変数への型説明や型注釈の表記を省略できる。

項の直積および項の直和の形式的な組み合わせ構造である代数的データ型は、型推論ルールに適したデータ構造の表現方法として関数型プログラミングの標準になっている。代数的データ型はパラメトリック多相（英語版）で総称化されているのが標準であり、Hindley–Milner型システムはその型変数化された項への型推論にも対応可能である。

入出力

関数型プログラミングでは、数学的な関数を組み合わせて計算を表現するが、それだけではファイルの読み書きのような外界とのやり取りを要する処理を直接的に表現できない[25]。このような外界とのやり取りを I/O (入出力) と呼ぶ[26]。数学的な計算をするだけ、つまり 1 + 1 のようなプログラム内で完結する処理ならば、入出力を記述できなくても問題ないが、現実的なプログラムにおいてはそうでない[27]。

非純粋な関数型プログラミング言語においては、式を評価すると同時に I/O が発生する関数を用意することで入出力を実現する[28]。たとえば、 F# 言語では、printfn "Hi." が評価されると、 () という値が戻ってくると同時に、画面に Hi. と表示される I/O が発生する[29]。

Haskell では、評価と同時に I/O が行われる関数は存在しない[30]。たとえば、 putStrLn "Hi." という式が評価されると IO () 型を持つ値が返されるが画面には何も表示されず、この値が Haskell の処理系によって解釈されて初めて画面に Hi. と表示される[31]。 I/O アクションとは、ファイルの読み書きやディスプレイへの表示などのような I/O を表現する式のことである[32][33]。 IO a という型は、コンピュータへの指示を表す I/O アクションを表現している[34][35]。ここでの IO はモナドと呼ばれるものの一つである[36]。

Clean では、一意型を用いて入出力を表す[要出典]。

応用的な手法

ポイントフリースタイル

最初に解の集合となる候補を生成し、それらの要素に対して1つ（もしくは複数）の解にたどり着くまで関数の適用とフィルタリングを繰り返す手法は、関数型プログラミングでよく用いられるパターンである[37]。

Haskell では、関数合成の二項演算子を使ってポイントフリースタイルで関数を定義することができる[38]。関数をポイントフリースタイルで定義すると、データより関数に目が行くようになり、どのようにデータが移り変わっていくかではなく、どんな関数を合成して何になっているかということへ意識が向くため、定義が読みやすく簡潔になることがある[39]。関数が複雑になりすぎると、ポイントフリースタイルでは逆に可読性が悪くなることもある[40]。

モナド

詳細は「モナド (プログラミング)」を参照

「モナドは値と計算を文脈で包むものだ[41]」「モナドには三通りある―計算順序の制御、副作用の制御、コンテナとしてのそれ[41]」「クライスリ圏はモナドへのもう一つの基本視点だ[41]」「モナドは文脈の型である―文脈に値を注入し、文脈内で関数を適用する[41]」「モナドは他の型を包むラッパー型である―内側の型を構造化し、内側の型の計算を合成する[41]」「モナドは自己関手の圏のただのモノイド[42]」

モナドは概ね、値を包んだコンテナの計算を合成する仕組みとイメージできる。コンテナはあくまで抽象的な概念であり、環境、状態、文脈とも解釈される。コンテナは副作用の記録媒体としても扱われて、その中で得られた値をラッピングし、それは自由に取り出して次の計算に使える。値のコンテナ収納をここではunitと呼ぶ。unit: a->maとなる。maは[a]と読み替えてもよい。コンテナは入れ子にできるのでmmaや[[a]]にもなる。これには圏論の関手の概念が用いられている。mmaをmaに整理することをここではjoinと呼ぶ。これには代数的構造のモノイドの概念が用いられている。unitとjoinの組み合わせでm入れ子を内部で揃えることをここではflatmapと呼ぶ。

モナドの源流はクライスリ圏である。関数f': a->bとunitを融合したクライスリ射fがあった。クライスリ射f: a->mbをunit値maに適用できるflatmapの形成がモナドの基本かつ本質であり、それによって値の構造化やその計算の合成といった無限の拡張性が生まれる。

それへの第1ステップは、クライスリ射の合成<=<: (b->mc)->(a->mb)->(a->mc)であり、これはjoin . unit (b->mc).(a->mb)とされる。.は関数合成演算子である。関数合成の概念は以下の三つ組でもテンソル積として使用される。このようなjoinが可能なのは、その三つ組(f, <=<, unit)が結合律と左右単位律（モナド則）を満たしてモノイド相当になっているからである。第2ステップは、クライスリ合成の第1引数のクライスリ射をunit値にした拡張演算子=<<: (b->mc)->mb->mcである。これは(join . unit b->mc) mbとされる。その三つ組(f, unit, =<<)も結合律と左右単位律（モナド則）を満たす。それはクライスリトリプルと呼ばれ、=<< fはクライスリスターf*: mb->mcと呼ばれる。=<<の逆引数版が、本命のモナドflatmap>>=: mb->(b->mc)->mcである。モナドflatmapは、その返り値を後続flatmapの引数にして合成できるようにもなった。三つ組は(m, join, unit)になる。mは*->*カインドの型であり、自己型/自己派生型に依存しているので自己関手（同型→同型）の圏の対象に例えられる。unit値maはモナド値と言われる。

モナド値の型は構造を持つ。上述のコンテナに入れるだけのシンプル構造のa->maは付加モナドと言われる。ListモナドやMaybeモナドがそれに当たる。コンテナを環境、状態、文脈といった抽象構造にしたものはコモナドと言われる。例えば、例外モナドa->m(a+e)、Readerモナドa->(e->ma)、Writerモナドa->m(w×a)、状態モナドa->(s->m(a×s))、継続モナドa->((a->mr)->mr)などがある。それらの抽象構造は、副作用を封入し、また線形論理の媒体にもなって参照透過性を維持する働きがある。

手続き型プログラミングとの比較

C 言語や Java 、 JavaScript 、 Python 、 Ruby などの2017年現在に使われている言語の多くは、手続き型の文法を持っている[43]。そのような言語では、文法として式 (expression) と文 (statement) を持つ[44]。ここでの式は、計算を実行して結果を得るような処理を記述するための文法要素であり、加減乗除や関数呼び出しなどから構成されている[45]。ここでの文は、何らかの動作を行うようにコンピュータへ指示するための文法要素であり、条件分岐の if 文やループの for 文と while 文などから構成されている[46]。手続き型の文法では、式で必要な計算を進め、その結果を元にして文でコンピュータ命令を行うという形で、プログラムを記述する[47]。このように、手続き型言語で重要なのは文である[48]。

それに対して、関数型言語で重要なのは式である[49]。関数型言語のプログラムはたくさんの式で構成され、プログラムそのものも一つの式である[50]。たとえば、 Haskell では、プログラムの処理の記述において文は使われず、外部の定義を取り込む import 宣言も処理の一部として扱えない[51]。関数型言語におけるプログラムの実行とは、プログラムを表す式の計算を進めて、その結果として値 (value) を得ることである[52]。式を計算することを、評価する (evaluate) という[53]。

手続き型言語ではコンピュータへの指示を文として上から順に並べて書くのに対して、関数型言語では数多く定義した細かい式を組み合わせてプログラムを作る[54]。手続き型言語では文が重要であり、関数型言語では式が重要である[55]。

式と文の違いとして、型が付いているかどうかというのがある[56]。式は型を持つが、文は型を持たない[57]。プログラム全てが式から構成されていて、強い静的型付けがされているのならば、プログラムの全体が細部まで型付けされることになる[58]。このように細部まで型付けされているようなプログラムは堅固なものになる[59]。

代表的な関数型言語

名前 公開年 型付け 純粋性 評価戦略 理論的背景
APL 1964 動的 先行
Agda 2007 静的型付け 純粋 先行 直観主義型理論
Rust 2010 静的型付け 先行
JavaScript 1996 動的型付け 先行
R 1993 動的 先行
Common Lisp 1984 動的 先行
Racket 1995 動的 先行
Dylan 1993 動的 先行
Caml 1985 静的型付け 先行
FP 1977 動的 純粋 先行
ISWIM 1966 静的型付け 先行
Clean 1987 静的型付け 純粋 遅延評価
Clojure 2007 動的 先行
Erlang 1986 動的 先行
F# 2005 静的型付け 先行
Haskell[60] 1990 静的型付け[61] 純粋[62] 遅延評価 型付きラムダ計算[63]
Idris 2007 静的型付け 純粋 先行
LISP[64] 1958 動的 先行 型無しラムダ計算[65]
Miranda 1985 静的型付け 純粋 遅延評価
ML 1973 静的型付け 先行
Standard ML 1983 静的型付け 先行
OCaml 1996 静的型付け 先行
Scala 2003 静的型付け 先行
Scheme 1975 動的 先行
Unlambda 1999 型なし 先行 コンビネータ論理

歴史

1930年代

関数型プログラミングのルーツは、アロンゾ・チャーチが1932年[注釈 1]と1941年[注釈 2]に発表したラムダ計算の研究とされている[66]。電子計算機発明以前のラムダ計算は、当然ながらコンピュータプログラムに使われることはなかったが、後のプログラミング言語のモデルにされたことで最初の関数型言語としての認識も得ている[67]。1989年現在までに登場した関数型言語の多くは、ラムダ計算に装飾を加えた発展形と見なすことができる[68]。また、ラムダ計算と同様に関数型プログラミングの背景と見なされている理論的公式に、モイセイ・シェインフィンケリとハスケル・カリーが1920～30年代に発表したコンビネータ論理がある[69]。

1950年代

1950年代後半にマサチューセッツ工科大学のジョン・マッカーシーが発表した「LISP」は最初の高水準な関数型言語として知られており[70]、関数プログラミング史の中でも特別な位置付けにある[71]。LISPはラムダ計算ベースという認識が一般的であるが、1978年のマッカーシーの言及によると[注釈 3]LISPの開発では匿名関数を表現したいという動機の方が先にあり、ラムダ計算の選択はそのための手段に過ぎなかったという[72]。

1960年代

歴史的に言えば、 LISP に続いて関数型プログラミングパラダイムへ刺激を与えたのは、1960年代半ばのピーター・ランディン（英語版）の成果である[73]。ランディンの成果はハスケル・カリーとアロンゾ・チャーチに大きな影響を受けていた[74]。ランディンの初期の論文は、ラムダ計算と、機械および高級言語 (ALGOL 60) との関係について議論している[75]。ランディンは、1964年[注釈 4]に、 SECD マシンと呼ばれる抽象的な機械を使って機械的に式を評価する方法を論じ、1965年[注釈 5]に、ラムダ計算で ALGOL 60 の非自明なサブセットを形式化した[76]。1966年[注釈 6]にランディンが発表した ISWIM（If You See What I Mean の略）という言語（群）は、間違いなく、これらの研究の成果であり、構文や意味論において多くの重要なアイデアを含んでいた[77]。 ISWIM は、ランディン本人によれば、「 LISP を、その名前にも表れたリストへのこだわり、手作業のメモリ割り当て、ハードウェアに依存した教育方法、重い括弧、伝統への妥協、から解放しようとする試みとして見ることができる」[78]。関数型言語の歴史において ISWIM は次のような貢献を果たした[79]。

  • 構文についての革新[80]
    • 演算子を前置記法で記述するのをやめて中置記法を導入した[81]。
    • let 節と where 節を導入して、さらに、関数を順序なく同時に定義でき、相互再帰も可能なようにした[82]。
    • 宣言などを記述する構文に、インデントに基づいたオフサイドルールを使用した[83]。
  • 意味論についての革新[84]
    • 非常に小さいが表現力があるコア言語を使って、構文的に豊かな言語を定義するという戦略を導入した[85]。
    • 等式推論 (equational reasoning) を重視した[86]。
    • 関数によるプログラムを実行するための単純な抽象機械としての SECD マシンを導入した[87]。

ランディンは「それをどうやって行うか」ではなく「それの望ましい結果とは何か」を表現することに重点を置いており、そして、 ISWIM の宣言的なプログラミング・スタイルは命令的なプログラミング・スタイルよりも優れているというランディンの主張は、今日まで関数型プログラミングの賛同者たちから支持されてきた[88]。その一方で、関数型言語への関心が高まるまでは、さらに10年を要した[89]。その理由の一つは、 ISWIM ライクな言語の実用的な実装がなかったことであり、実のところ、この状況は1980年代になるまで変わらなかった[90]。

ケネス・アイバーソンが1962年[注釈 7]に発表した APL は、純粋な関数型プログラミング言語ではないが、その関数型的な部分を取り出したサブセットがラムダ式に頼らずに関数型プログラミングを実現する方法の一例であるという点で、関数型プログラミング言語の歴史を考察する際に言及する価値はある[91]。実際に、アイバーソンが APL を設計した動機は、配列のための代数的なプログラミング言語を開発したいというものであり、アイバーソンのオリジナル版は基本的に関数型的な記法を用いていた[92]。その後の APL では、いくつかの命令型的な機能が追加されている[93]。

1970年代

1973年にエディンバラ大学のロビン・ミルナーが静的型付けの「ML」を開発した。同大学ではクリーネの再帰定理をプログラミング投影するための「NPL」も開発された[94]。同時期にマサチューセッツ工科大学でガイ・スティールとジェラルド・サスマンが「Scheme」を開発した。ここでは末尾再帰が実装された。1977年にジョン・バッカスは、チューリング賞表彰式で「Can Programming Be Liberated From the von Neumann Style? -A Functional Style and Its Algebra of Programs-」と題したスピーチを行った[95]。「プログラミングはノイマン型から解放され得るか？関数型スタイルとプログラムの代数学」と訳せるこのスピーチは、世間の関数型プログラミングへの関心を高めてその研究促進の契機になった。

1980年代

1982年にHindley–Milner型システムが確立され、関数型プログラミングにパラメトリック多相にも対応可能で実用的になった型推論の機能をもたらした。1983年にHindley–Milner型システムを導入した「Standard ML」が開発され、これは関数型プログラミングの主流をLISP以来の動的型付けから静的型付けにシフトさせた。1980年代にマルティン・レーフが考案した直感主義型理論は、関数型プログラミングに依存型の概念をもたらして、特に2000年代世代の関数型言語に大きな影響を与えた。1986年開発の「Erlang」の並行プログラミング特性は注目を集めて、元祖オブジェクト指向のメッセージングとの関連性も後に提起された。1985年にデビッド・ターナーが遅延評価を基本にした純粋関数型言語「Miranda」を開発した。これは1987年から関数型言語研究のオープン標準下で開発が始められた「Haskell」に大きな影響を及ぼしている。

脚注

[脚注の使い方]
  1. ^ (Church 1932)
  2. ^ (Church 1941)
  3. ^ (McCarthy 1978)
  4. ^ (Landin 1964)
  5. ^ (Landin 1965)
  6. ^ (Landin 1966)
  7. ^ (Iverson 1962)

出典

  1. ^ 本間, 類地 & 逢坂 2017, p. 3
  2. ^ a b 『関数型プログラミングの基礎』リックテレコム、2016年11月、1,3 関数型モデル頁。 
  3. ^ 本間, 類地 & 逢坂 2017, p. 2
  4. ^ 本間, 類地 & 逢坂 2017, p. 3
  5. ^ 本間, 類地 & 逢坂 2017, p. 6
  6. ^ 本間, 類地 & 逢坂 2017, p. 5
  7. ^ 本間, 類地 & 逢坂 2017, p. 4
  8. ^ 本間, 類地 & 逢坂 2017, p. 4
  9. ^ 本間, 類地 & 逢坂 2017, p. 3
  10. ^ “Declarative programming in Ch.3. Introduction to ML programming in SML# Document”. www.pllab.riec.tohoku.ac.jp. 2021年1月閲覧。
  11. ^ 本間, 類地 & 逢坂 2017, p. 3
  12. ^ 本間, 類地 & 逢坂 2017, p. 3
  13. ^ 本間, 類地 & 逢坂 2017, p. 3
  14. ^ 本間, 類地 & 逢坂 2017, p. 5
  15. ^ 本間, 類地 & 逢坂 2017, p. 5
  16. ^ 本間, 類地 & 逢坂 2017, p. 5
  17. ^ Abelson, Harold; Sussman, Gerald Jay (1984). Structure and Interpretation of Computer Programs. MIT Press. Formulating Abstractions with Higher-Order Procedures. ISBN 0-262-01077-1. https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3 
  18. ^ Programming language pragmatics, by Michael Lee Scott, section 11.2 "Functional Programming".
  19. ^ Roberto Ierusalimschy; Luiz Henrique de Figueiredo; Waldemar Celes (2005). “The Implementation of Lua 5.0”. Journal of Universal Computer Science 11 (7): 1159–1176. doi:10.3217/jucs-011-07-1159. 
  20. ^ Brian Lonsdorf (2015年). “Professor Frisby's Mostly Adequate Guide to Functional Programming”. GitHub. 2020年3月20日閲覧。 “A pure function is a function that, given the same input, will always return the same output and does not have any observable side effect.”
  21. ^ Bartosz Milewski (2013年). “Basics of Haskell”. School of Haskell. FP Complete. 2016年10月27日時点のオリジナルよりアーカイブ。2018年7月13日閲覧。 “Here are the fundamental properties of a pure function: 1. A function returns exactly the same result every time it's called with the same set of arguments. In other words a function has no state, nor can it access any external state. Every time you call it, it behaves like a newborn baby with blank memory and no knowledge of the external world. 2. A function has no side effects. Calling a function once is the same as calling it twice and discarding the result of the first call.”
  22. ^ Wirth, Niklaus (1976). Algorithms + Data Structures = Programs. Prentice-Hall. p. 126. ISBN 978-0-13022418-7. https://archive.org/details/algorithmsdatast00wirt/page/126 
  23. ^ Clinger, William (1998). “Proper tail recursion and space efficiency”. Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation - PLDI '98. pp. 174–185. doi:10.1145/277650.277719. ISBN 0897919874 
  24. ^ Discrete Mathematics with Applications (2nd ed.). (1995). p. 427. ISBN 978-0-53494446-9. https://archive.org/details/discretemathema000epps/page/427 
  25. ^ 本間, 類地 & 逢坂 2017, p. 6
  26. ^ 本間, 類地 & 逢坂 2017, p. 6
  27. ^ 本間, 類地 & 逢坂 2017, p. 6
  28. ^ 本間, 類地 & 逢坂 2017, p. 6
  29. ^ 本間, 類地 & 逢坂 2017, p. 6
  30. ^ 本間, 類地 & 逢坂 2017, p. 6
  31. ^ 本間, 類地 & 逢坂 2017, p. 6
  32. ^ 本間, 類地 & 逢坂 2017, p. 6
  33. ^ 本間, 類地 & 逢坂 2017, p. 23
  34. ^ 本間, 類地 & 逢坂 2017, p. 6
  35. ^ 本間, 類地 & 逢坂 2017, p. 31
  36. ^ 本間, 類地 & 逢坂 2017, p. 32
  37. ^ Lipovača 2012, p. 22
  38. ^ Lipovača 2012, p. 22
  39. ^ Lipovača 2012, p. 22
  40. ^ Lipovača 2012, p. 22
  41. ^ a b c d e “Monad tutorials timeline, year2011”. 2021年1月閲覧。
  42. ^ Philip Wadler
  43. ^ 本間, 類地 & 逢坂 2017, p. 22
  44. ^ 本間, 類地 & 逢坂 2017, p. 22
  45. ^ 本間, 類地 & 逢坂 2017, p. 22
  46. ^ 本間, 類地 & 逢坂 2017, p. 22
  47. ^ 本間, 類地 & 逢坂 2017, p. 22
  48. ^ 本間, 類地 & 逢坂 2017, p. 22
  49. ^ 本間, 類地 & 逢坂 2017, p. 22
  50. ^ 本間, 類地 & 逢坂 2017, p. 22
  51. ^ 本間, 類地 & 逢坂 2017, p. 22
  52. ^ 本間, 類地 & 逢坂 2017, p. 22
  53. ^ 本間, 類地 & 逢坂 2017, p. 22
  54. ^ 本間, 類地 & 逢坂 2017, p. 22
  55. ^ 本間, 類地 & 逢坂 2017, pp. 22–23
  56. ^ 本間, 類地 & 逢坂 2017, pp. 22–23
  57. ^ 本間, 類地 & 逢坂 2017, pp. 22–23
  58. ^ 本間, 類地 & 逢坂 2017, pp. 22–23
  59. ^ 本間, 類地 & 逢坂 2017, pp. 22–23
  60. ^ 本間, 類地 & 逢坂 2017, p. 2
  61. ^ 本間, 類地 & 逢坂 2017, p. 2
  62. ^ 本間, 類地 & 逢坂 2017, p. 2
  63. ^ 本間, 類地 & 逢坂 2017, p. 4
  64. ^ 本間, 類地 & 逢坂 2017, p. 4
  65. ^ 本間, 類地 & 逢坂 2017, p. 4
  66. ^ Hudak 1989, p. 363
  67. ^ Hudak 1989, p. 363
  68. ^ Hudak 1989, p. 363
  69. ^ Haskell Brooks Curry; Robert Feys (1958). Combinatory Logic. North-Holland Publishing Company. https://archive.org/details/combinatorylogic0002curr 2013年2月10日閲覧。 
  70. ^ McCarthy, John (June 1978). History of Lisp (PDF). History of Programming Languages. Los Angeles, CA. pp. 173–185. doi:10.1145/800025.808387。
  71. ^ Hudak 1989, p. 367
  72. ^ Hudak 1989, pp. 367–368
  73. ^ Hudak 1989, p. 371
  74. ^ Hudak 1989, p. 371
  75. ^ Hudak 1989, p. 371
  76. ^ Hudak 1989, p. 371
  77. ^ Hudak 1989, p. 371
  78. ^ Hudak 1989, p. 371
  79. ^ Hudak 1989, pp. 371–372
  80. ^ Hudak 1989, p. 371
  81. ^ Hudak 1989, p. 371
  82. ^ Hudak 1989, p. 371
  83. ^ Hudak 1989, p. 371
  84. ^ Hudak 1989, pp. 371–372
  85. ^ Hudak 1989, p. 371
  86. ^ Hudak 1989, p. 371
  87. ^ Hudak 1989, pp. 371–372
  88. ^ Hudak 1989, p. 372
  89. ^ Hudak 1989, p. 372
  90. ^ Hudak 1989, p. 372
  91. ^ Hudak 1989, p. 372
  92. ^ Hudak 1989, p. 372
  93. ^ Hudak 1989, p. 372
  94. ^ R.M. Burstall. Design considerations for a functional programming language. Invited paper, Proc. Infotech State of the Art Conf. "The Software Revolution", Copenhagen, 45–57 (1977)
  95. ^ Backus, J. (1978). “Can programming be liberated from the von Neumann style?: A functional style and its algebra of programs”. Communications of the ACM 21 (8): 613–641. doi:10.1145/359576.359579. 

参考文献

外部リンク

関連項目

コンピュータ・プログラミング言語の関連項目
言語水準
言語処理系
言語分類
その他
関連項目
「https://ja.wikipedia.org/w/index.php?title=関数型プログラミング&oldid=87264028」から取得