コンテンツにスキップ

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

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』
履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
タグ: モバイル編集 モバイルウェブ編集 改良版モバイル編集
1行目: 1行目:
{{プログラミング・パラダイム}}
{{プログラミング・パラダイム}}
⚫
'''関数型プログラミング'''（かんすうがたプログラミング、{{lang-en-short|functional programming}}）とは、[[関数 (数学)|数学的な意味での関数]]の使用を中心にした[[コンピュータプログラミング]]のスタイルである<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。 '''関数プログラミング'''とも邦訳される<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>。

⚫
'''関数型プログラミング'''（かんすうがたプログラミング、{{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>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。ここでの関数は、数学的なものを指し、引数の値が定まれば結果も定まるという[[参照透過性]]を持つものである<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。
関数型プログラミングは、[[関数 (数学)|関数]]を主軸にしたプログラミングを行うスタイルである<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。ここでの関数は、数学的なものを指し、引数の値が定まれば結果も定まるという[[参照透過性]]を持つものである<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。


29行目: 25行目:


=== 参照透過性 ===
=== 参照透過性 ===

{{main|参照透過性}}
{{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>。


=== 第一級関数と高階関数 ===
⚫
参照透過性とは、同じ値を与えたら返り値も必ず同じになるような性質である<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。参照透過性を持つことは、その関数が'''状態を持たない'''ことを保証する<ref>{{harvnb|本間|類地|逢坂|2017|p=5}}</ref>。状態を持たない数学的な関数は、並列処理を実現するのに適している<ref>{{harvnb|本間|類地|逢坂|2017|p=5}}</ref>。関数型プログラミング言語の内で、全ての関数が参照透過性を持つようなものを純粋関数型プログラミング言語という<ref>{{harvnb|本間|類地|逢坂|2017|p=5}}</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|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>。外部状態はグローバル変数と読み替えてもよい。純粋関数はローカル変数などの内部状態も持たない。

純粋関数とは、冪等な計算式と可変な状態を完全に分離する機構であり、冪等な計算式は不変な状態としての定数をしばしば内包する。これはコンパイル[[最適化 (情報工学)|最適化]]の対象にされやすく、純粋関数はコードの最適化で重要な役割を果たす。純粋関数は、ミュータブルな状態を参照透過に処理するためのアプローチでもある。純粋関数は引数から状態を扱い、遷移させた状態を返り値にする。その参照透過性の維持ロジックには[[線形論理]]などが使われる。状態の構造化には[[適切さの論理|適切性論理]]などが使われる。それらの[[部分構造論理]]をより最適化した[[デザインパターン (ソフトウェア)|デザインパターン]]には[[圏論]]由来の[[モナド (プログラミング)|モナド]]がある。

⚫
=== 再帰 ===
{{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型システム|en|Hindley–Milner type system}}登場以降の関数型プログラミングは、[[型付きラムダ計算]]を背景にした[[静的型付け]]が標準になっている。[[LISP|Lisp]]系で実践されていた[[型無しラムダ計算]]を背景にした[[動的型付け]]は、その対極に位置付けられている。Hindley–Milner型システムがもたらした[[型推論]]もまた関数型プログラミングの標準になっている。型推論ルールでの各変数の型は、各項と各評価値から演繹的に導き出されるので、各変数への型説明、型注釈の表記を省略できる。項の[[直積集合|直積]]および項の[[直和 (圏論)|直和]]の形式的な組み合わせ表記である[[代数的データ型]]は、型推論ルールに適した[[データ構造]]の表現法として関数型プログラミングの標準になっている。代数的データ型は{{仮リンク|パラメトリック多相|en|Parametric polymorphism}}で[[総称プログラミング|総称化]]されて利便性が高められている。

⚫
=== 入出力 ===
関数型プログラミングでは、数学的な関数を組み合わせて計算を表現するが、それだけではファイルの読み書きのような外界とのやり取りを要する処理を直接的に表現できない<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行目: 60行目:
[[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>。


=== 言語 ===
=== 手続き型との比較 ===
⚫
[[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>。

== 代表的な関数型言語 ==
関数型プログラミング言語とは、関数型プログラミングを推奨している[[プログラミング言語]]である<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>。
関数型プログラミング言語とは、関数型プログラミングを推奨している[[プログラミング言語]]である<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>。


59行目: 81行目:


{| class="wikitable sortable"<!-- 名前の欄には、それが関数型プログラミング言語であるという出典を付ける。型付けの欄には、その記述の根拠になる出典を付ける。評価戦略の欄には、その記述の根拠になる出典を付ける。純粋性の欄には、それが純粋か非純粋かの出典を付ける。理論的背景の欄には、その記述の根拠になる出典を付ける。 -->
{| class="wikitable sortable"<!-- 名前の欄には、それが関数型プログラミング言語であるという出典を付ける。型付けの欄には、その記述の根拠になる出典を付ける。評価戦略の欄には、その記述の根拠になる出典を付ける。純粋性の欄には、それが純粋か非純粋かの出典を付ける。理論的背景の欄には、その記述の根拠になる出典を付ける。 -->
|+ 関数型プログラミング言語
|-
|-
! 名前
! 名前
157行目: 178行目:
| コンビネータ論理{{要出典|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年代 ===
=== 1930年代 ===

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

関数型言語の開発において、[[アロンゾ・チャーチ]]が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>。
関数型言語の開発において、[[アロンゾ・チャーチ]]が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年代 ===
=== 1950年代 ===

{{節スタブ|date=2021年3月}}
{{節スタブ|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>。
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年代 ===
=== 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>。


200行目: 205行目:


== 脚注 ==
== 脚注 ==

{{脚注ヘルプ}}
{{脚注ヘルプ}}

⚫
=== 注釈 ===

{{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行目: 224行目:


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

* [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月25日 (土) 06:11時点における版

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

命令型プログラミング

宣言型プログラミング

マルチパラダイム

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

概要

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

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

def square(n):
  return n ** 2

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

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

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

参照透過性

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

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

第一級関数と高階関数

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

関数型プログラミングの関数は、他の関数への引数や返り値にもできるのが標準である。これを第一級という。他の関数を自身の引数や返り値にできる関数は、高階といわれる。第一級関数は値と等価なので変数に束縛したりデータ構造に当てはめることができる[16]。値と等価なことで無名関数表記も可能になる[17]。値と等価である関数は関数の型（英語版）で型付けされた値として扱われる[18]。

高階関数の性質は、カリー化や部分適用（英語版）の実装を可能にする。関数を一つずつ引数に適用させる形式にするのをカリー化と呼ぶ。引数への適用を途中で止めたままにするのが部分適用である。それは変数に束縛して保存でき、後続式で残り引数を適用して最終的な返り値にできる。第一級関数の性質は、クロージャや継続の実装を可能にする。クロージャは後続式で引数を与えられることを前提にした抽象的な値を表現できる。継続は後続式で評価されることを前提にした関数式のスナップショットを表現できる。

純粋関数

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

純粋関数とは、冪等な計算式と可変な状態を完全に分離する機構であり、冪等な計算式は不変な状態としての定数をしばしば内包する。これはコンパイル最適化の対象にされやすく、純粋関数はコードの最適化で重要な役割を果たす。純粋関数は、ミュータブルな状態を参照透過に処理するためのアプローチでもある。純粋関数は引数から状態を扱い、遷移させた状態を返り値にする。その参照透過性の維持ロジックには線形論理などが使われる。状態の構造化には適切性論理などが使われる。それらの部分構造論理をより最適化したデザインパターンには圏論由来のモナドがある。

再帰

→詳細は「再帰」を参照

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

先行評価と遅延評価

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

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

先行と遅延の区別は、引数渡しされる第一級関数でよく用いられる。全引数を評価してから関数コールするのが先行評価の用例になり、未評価の引数があるままで関数コールするのが遅延評価の用例になる。遅延評価は、後で不要になることもある計算をしないで計算量を減らすプロセス速度の最適化をもたらす。また、現行関数式または後続関数式の評価を遅延できる仕組みは、関数式のカット/コピー/ペースト的な継続を実現する。これは関数式解釈順序の操作によるプロセス構造の最適化をもたらす。

型システム

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

Hindley–Milner型システム（英語版）登場以降の関数型プログラミングは、型付きラムダ計算を背景にした静的型付けが標準になっている。Lisp系で実践されていた型無しラムダ計算を背景にした動的型付けは、その対極に位置付けられている。Hindley–Milner型システムがもたらした型推論もまた関数型プログラミングの標準になっている。型推論ルールでの各変数の型は、各項と各評価値から演繹的に導き出されるので、各変数への型説明、型注釈の表記を省略できる。項の直積および項の直和の形式的な組み合わせ表記である代数的データ型は、型推論ルールに適したデータ構造の表現法として関数型プログラミングの標準になっている。代数的データ型はパラメトリック多相（英語版）で総称化されて利便性が高められている。

入出力

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

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

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

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

備考

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

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

手続き型との比較

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

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

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

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

代表的な関数型言語

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

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

名前 型付け 純粋性 評価戦略 理論的背景
Clean[要出典] 静的型付け[要出典] 純粋[要出典] 遅延評価[要出典]
Clojure[要出典] 動的型付け[要出典] 非純粋[要出典] 正格評価[要出典]
Erlang[要出典] 動的型付け[要出典] 非純粋[要出典] 正格評価[要出典]
F#[要出典] 静的型付け[要出典] 非純粋[要出典] 正格評価[要出典]
Haskell[63] 静的型付け[64] 純粋[65] 遅延評価[66] 型付きラムダ計算[67]
Idris[要出典] 静的型付け[要出典] 純粋[要出典] 正格評価[要出典] 型付きラムダ計算[要出典]
Lazy K[要出典] 型なし[要出典] 純粋[要出典] 遅延評価[要出典] コンビネータ論理[要出典]
LISP[68] 動的型付け[要出典] 非純粋[要出典] 方言による[要出典] 型無しラムダ計算[69]
Miranda[要出典] 静的型付け[要出典] 純粋[要出典] 遅延評価[要出典]
ML[要出典] 静的型付け[要出典] 非純粋[要出典] 先行評価[要出典]
SML[要出典] 静的型付け[要出典] 非純粋[要出典] 正格評価[要出典]
OCaml[要出典] 静的型付け[要出典] 非純粋[要出典] 正格評価[要出典]
Scala[要出典] 静的型付け[要出典] 非純粋[要出典] 正格評価[要出典]
Scheme[要出典] 動的型付け[要出典] 非純粋[要出典] 正格評価[要出典]
Unlambda[要出典] 型なし[要出典] 非純粋[要出典] 正格評価[要出典] コンビネータ論理[要出典]

歴史

1930年代

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

1950年代

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

1960年代

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

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

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

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

脚注

[脚注の使い方]
  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. ^ 本間, 類地 & 逢坂 2017, p. 2
  3. ^ 本間, 類地 & 逢坂 2017, p. 3
  4. ^ 本間, 類地 & 逢坂 2017, p. 3
  5. ^ 本間, 類地 & 逢坂 2017, p. 3
  6. ^ 本間, 類地 & 逢坂 2017, p. 3
  7. ^ 本間, 類地 & 逢坂 2017, p. 3
  8. ^ 本間, 類地 & 逢坂 2017, p. 3
  9. ^ 本間, 類地 & 逢坂 2017, p. 3
  10. ^ 本間, 類地 & 逢坂 2017, p. 3
  11. ^ 本間, 類地 & 逢坂 2017, p. 4
  12. ^ 本間, 類地 & 逢坂 2017, p. 3
  13. ^ 本間, 類地 & 逢坂 2017, p. 5
  14. ^ 本間, 類地 & 逢坂 2017, p. 5
  15. ^ 本間, 類地 & 逢坂 2017, p. 5
  16. ^ 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 
  17. ^ Programming language pragmatics, by Michael Lee Scott, section 11.2 "Functional Programming".
  18. ^ 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. 
  19. ^ 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.”
  20. ^ 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.”
  21. ^ Wirth, Niklaus (1976). Algorithms + Data Structures = Programs. Prentice-Hall. p. 126. ISBN 978-0-13022418-7. https://archive.org/details/algorithmsdatast00wirt/page/126 
  22. ^ 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 
  23. ^ Discrete Mathematics with Applications (2nd ed.). (1995). p. 427. ISBN 978-0-53494446-9. https://archive.org/details/discretemathema000epps/page/427 
  24. ^ 本間, 類地 & 逢坂 2017, p. 6
  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. 23
  33. ^ 本間, 類地 & 逢坂 2017, p. 6
  34. ^ 本間, 類地 & 逢坂 2017, p. 31
  35. ^ 本間, 類地 & 逢坂 2017, p. 32
  36. ^ Lipovača 2012, p. 22
  37. ^ Lipovača 2012, p. 22
  38. ^ Lipovača 2012, p. 22
  39. ^ Lipovača 2012, p. 22
  40. ^ 本間, 類地 & 逢坂 2017, p. 22
  41. ^ 本間, 類地 & 逢坂 2017, p. 22
  42. ^ 本間, 類地 & 逢坂 2017, p. 22
  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, pp. 22–23
  53. ^ 本間, 類地 & 逢坂 2017, pp. 22–23
  54. ^ 本間, 類地 & 逢坂 2017, pp. 22–23
  55. ^ 本間, 類地 & 逢坂 2017, pp. 22–23
  56. ^ 本間, 類地 & 逢坂 2017, pp. 22–23
  57. ^ 本間, 類地 & 逢坂 2017, p. 3
  58. ^ 本間, 類地 & 逢坂 2017, p. 3
  59. ^ 本間, 類地 & 逢坂 2017, p. 5
  60. ^ 本間, 類地 & 逢坂 2017, p. 6
  61. ^ 本間, 類地 & 逢坂 2017, p. 4
  62. ^ 本間, 類地 & 逢坂 2017, p. 4
  63. ^ 本間, 類地 & 逢坂 2017, p. 2
  64. ^ 本間, 類地 & 逢坂 2017, p. 2
  65. ^ 本間, 類地 & 逢坂 2017, p. 2
  66. ^ 本間, 類地 & 逢坂 2017, p. 2
  67. ^ 本間, 類地 & 逢坂 2017, p. 4
  68. ^ 本間, 類地 & 逢坂 2017, p. 4
  69. ^ 本間, 類地 & 逢坂 2017, p. 4
  70. ^ Hudak 1989, p. 363
  71. ^ Hudak 1989, p. 363
  72. ^ Hudak 1989, p. 363
  73. ^ Hudak 1989, p. 367
  74. ^ Hudak 1989, pp. 367–368
  75. ^ Hudak 1989, p. 371
  76. ^ Hudak 1989, p. 371
  77. ^ Hudak 1989, p. 371
  78. ^ Hudak 1989, p. 371
  79. ^ Hudak 1989, p. 371
  80. ^ Hudak 1989, p. 371
  81. ^ Hudak 1989, pp. 371–372
  82. ^ Hudak 1989, p. 371
  83. ^ Hudak 1989, p. 371
  84. ^ Hudak 1989, p. 371
  85. ^ Hudak 1989, p. 371
  86. ^ Hudak 1989, pp. 371–372
  87. ^ Hudak 1989, p. 371
  88. ^ Hudak 1989, p. 371
  89. ^ Hudak 1989, pp. 371–372
  90. ^ Hudak 1989, p. 372
  91. ^ Hudak 1989, p. 372
  92. ^ Hudak 1989, p. 372
  93. ^ Hudak 1989, p. 372
  94. ^ Hudak 1989, p. 372
  95. ^ Hudak 1989, p. 372

参考文献

外部リンク

関連項目

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