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

出典: フリー百科事典『ウィキペディア（Wikipedia）』
履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
→‎応用的な手法: 修正しました。
1行目: 1行目:
{{告知|提案|直近に行われた編集を差し戻す|section=出典が明示されていない記述の追加について|date=2021年12月}}
{{告知|提案|直近に行われた編集を差し戻す|section=出典が明示されていない記述の追加について|date=2021年12月}}
{{プログラミング・パラダイム}}
{{プログラミング・パラダイム}}
'''関数型プログラミング'''（かんすうがたプログラミング、{{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>{{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>。
数学的な関数は、[[副作用 (プログラム)|副作用]]を排除して[[参照透過性]]を順守している。参照透過性順守の度合いは言語ごとに異なっている。副作用を容認している関数型言語も多く、それらは非純粋と言われる<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。数学的な関数の実装に専念している本来のものは、{{仮リンク|純粋関数型言語|en|purely functional programming language}}と呼ばれている<ref>{{harvnb|本間|類地|逢坂|2017|p=5}}</ref>。関数型言語の多くはその設計に[[ラムダ計算]]が関わっている。ラムダ計算は、計算を記号列の規則的な変換として模型化した[[形式体系]]である<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>。
18行目: 18行目:
fun func 0 = 1
fun func 0 = 1
| func n = n * func (n - 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>。
</syntaxhighlight>上記の例では、関数<code>func</code>は[[参照透過性|参照透過]]であり[[再帰]]を用いており、その再帰<code>func(n-1)</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>。


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


=== 純粋関数 ===
=== 純粋関数 ===
参照透過性を順守した関数は、{{仮リンク|純粋関数|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>。外部状態はグローバル変数と読み替えてもよい。純粋関数はローカル変数などの内部状態も持たない。
参照透過性を順守した関数は、{{仮リンク|純粋関数|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や[[イミュータブル]]にも繋がっている。コンパイル[[最適化 (情報工学)|最適化]]の対象としても適当であり、純粋関数はコードの最適化で重要な役割を果たす。
純粋関数とは、参照透過な計算式と可変な状態を完全に分離する機構であり、参照透過な計算式は不変な状態としての定数群をしばしば内包している。この概念はinvariantや[[イミュータブル]]にも繋がっている。コンパイル[[最適化 (情報工学)|最適化]]の対象としても適当であり、純粋関数はコードの最適化で重要な役割を果たす。


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


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


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


=== 型システム ===
=== 型システム ===
91行目: 91行目:
'''モナド'''{{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>」
'''モナド'''{{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>」


モナドは概ね、値を包んだコンテナの計算を合成する仕組みとイメージできる。コンテナはあくまで抽象的な概念であり、環境、状態、文脈とも解釈される。コンテナは[[副作用 (プログラム)|副作用]]の記録媒体としても扱われて、その中で得られた値をラッピングし、それは取り出されて次の計算に使える。値のコンテナ収納をここでは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>に、<code><nowiki>[[a]]</nowiki></code>を<code>[a]</code>に整理することをここではjoinと呼ぶ。unitとjoinの組み合わせで<code>a</code> <code>ma</code> <code>mma</code>などを内部で揃えて<code>ma</code>にすることをここではflatmapと呼ぶ。
モナドは概ね、値を包んだコンテナの計算を合成する仕組みとイメージできる。コンテナはあくまで抽象的な概念であり、環境、状態、文脈とも解釈される。コンテナは[[副作用 (プログラム)|副作用]]の記録媒体としても扱われて、その中で得られた値をラッピングし、それは取り出されて次の計算に使える。値のコンテナ収納をここでは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>に、<code><nowiki>[[a]]</nowiki></code>を<code>[a]</code>に整理することをここではjoinと呼ぶ。<code>join: m(ma)->ma</code>のようになる。unitとjoinの組み合わせで<code>a</code> <code>ma</code> <code>mma</code>などを内部で揃えて<code>ma</code>にすることをここではflatmapと呼ぶ。


モナドの土台の一つは[[クライスリ圏]]であり、関数<code>f': a->b</code>とunitを融合したような[[クライスリ圏|クライスリ射]]<code>f: a->mb</code>があった。この<code>a->mb</code>をunit値<code>ma</code>に適用できるようにしたflatmapがモナドの基本であり、それによって値の構造化やその計算の合成といった様々な拡張性が生まれる。それへの第1ステップは、[[クライスリ圏|クライスリ射]]の合成<code><=<: (b->mc)->(a->mb)->(a->mc)</code>であり、これは<code>join . unit (b->mc).(a->mb)</code>とされる。第2ステップは、<code><=<</code>の<code>(a->mb)</code>をunit値にした拡張演算子<code>=<<: (b->mc)->mb->mc</code>である。これは<code>(join . unit b->mc) mb</code>とされる。この<code>=<<</code>の逆さ引数版が、本命のモナドflatmap<code>>>=: mb->(b->mc)->mc</code>になる。モナドflatmapは<code>b->mc</code>をunit値<code>mb</code>に適用できて、その返り値を次のflatmapの引数にして連結できるようにもなった。unit値<code>ma</code>や<code>mb</code>はモナド値と言われる。
モナドの土台の一つは[[クライスリ圏]]であり、関数<code>f': a->b</code>とunitを融合したような[[クライスリ圏|クライスリ射]]<code>f: a->mb</code>があった。この<code>a->mb</code>をunit値<code>ma</code>に適用できるようにしたflatmapがモナドの基本である。そこから値の構造化やその計算の合成といった様々な拡張性が生まれる。
それへの第1ステップは、[[クライスリ圏|クライスリ射]]の合成<code><=<: (b->mc)->(a->mb)->(a->mc)</code>であり、これは<code>join . unit (b->mc).(a->mb)</code>とされる。第2ステップは、<code><=<</code>の<code>(a->mb)</code>をunit値にした拡張演算子<code>=<<: (b->mc)->mb->mc</code>である。これは<code>(join . unit b->mc) mb</code>とされる。この<code>=<<</code>の逆さ引数版が、本命のモナドflatmap<code>>>=: mb->(b->mc)->mc</code>になる。モナドflatmapは<code>b->mc</code>をunit値<code>mb</code>に適用できて、その返り値を次のflatmapの引数にして連結できるようにもなった。unit値<code>ma</code>や<code>mb</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>などである。それらの抽象構造は[[副作用 (プログラム)|副作用]]を封入し、また[[参照透過性]]を維持する働きがある。
モナド値の型は構造を持つ。上述のコンテナに入れるだけのシンプル構造の<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>などである。それらの抽象構造は[[副作用 (プログラム)|副作用]]を封入し、また[[参照透過性]]を維持する働きがある。

2022年1月6日 (木) 04:20時点における版

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

命令型プログラミング

宣言型プログラミング

マルチパラダイム

関数型プログラミング（かんすうがたプログラミング、英: 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は参照透過であり再帰を用いており、その再帰func(n-1)は二項演算子-を引数に取っている高階関数と見なされる。-は第一級関数と同等である。再帰での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]。

第一級関数と高階関数

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

関数型プログラミングの関数は、他の関数への引数や返り値にもできるのが標準である。これを第一級という。他の関数を自身の引数や返り値にできる関数は、高階といわれる。map filter reduceは高階関数の代表例である。第一級関数は値と同等に扱われるので、変数に束縛したりデータ構造に当てはめることができる[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]」

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

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

それへの第1ステップは、クライスリ射の合成<=<: (b->mc)->(a->mb)->(a->mc)であり、これはjoin . unit (b->mc).(a->mb)とされる。第2ステップは、<=<の(a->mb)をunit値にした拡張演算子=<<: (b->mc)->mb->mcである。これは(join . unit b->mc) mbとされる。この=<<の逆さ引数版が、本命のモナドflatmap>>=: mb->(b->mc)->mcになる。モナドflatmapはb->mcをunit値mbに適用できて、その返り値を次のflatmapの引数にして連結できるようにもなった。unit値maやmbはモナド値と言われる。

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

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

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

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

代表的な関数型言語

名前 公開年 型付け 純粋性 評価戦略 理論的背景
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[59] 1990 静的型付け[60] 純粋[61] 遅延評価 型付きラムダ計算[62]
Idris 2007 静的型付け 純粋 先行
LISP[63] 1958 動的 先行 型無しラムダ計算[64]
Miranda 1985 静的型付け 純粋 遅延評価
ML 1973 静的型付け 先行
Standard ML 1983 静的型付け 先行
OCaml 1996 静的型付け 先行
Scala 2003 静的型付け 先行
Scheme 1975 動的 先行
Unlambda 1999 型なし 先行 コンビネータ論理

歴史

1930年代

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

1950年代

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

1960年代

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

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

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

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

1970年代

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

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. ^ 本間, 類地 & 逢坂 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, p. 22
  53. ^ 本間, 類地 & 逢坂 2017, p. 22
  54. ^ 本間, 類地 & 逢坂 2017, pp. 22–23
  55. ^ 本間, 類地 & 逢坂 2017, pp. 22–23
  56. ^ 本間, 類地 & 逢坂 2017, pp. 22–23
  57. ^ 本間, 類地 & 逢坂 2017, pp. 22–23
  58. ^ 本間, 類地 & 逢坂 2017, pp. 22–23
  59. ^ 本間, 類地 & 逢坂 2017, p. 2
  60. ^ 本間, 類地 & 逢坂 2017, p. 2
  61. ^ 本間, 類地 & 逢坂 2017, p. 2
  62. ^ 本間, 類地 & 逢坂 2017, p. 4
  63. ^ 本間, 類地 & 逢坂 2017, p. 4
  64. ^ 本間, 類地 & 逢坂 2017, p. 4
  65. ^ Hudak 1989, p. 363
  66. ^ Hudak 1989, p. 363
  67. ^ Hudak 1989, p. 363
  68. ^ Haskell Brooks Curry; Robert Feys (1958). Combinatory Logic. North-Holland Publishing Company. https://archive.org/details/combinatorylogic0002curr 2013年2月10日閲覧。 
  69. ^ McCarthy, John (June 1978). History of Lisp (PDF). History of Programming Languages. Los Angeles, CA. pp. 173–185. doi:10.1145/800025.808387。
  70. ^ Hudak 1989, p. 367
  71. ^ Hudak 1989, pp. 367–368
  72. ^ Hudak 1989, p. 371
  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, pp. 371–372
  79. ^ Hudak 1989, p. 371
  80. ^ Hudak 1989, p. 371
  81. ^ Hudak 1989, p. 371
  82. ^ Hudak 1989, p. 371
  83. ^ Hudak 1989, pp. 371–372
  84. ^ Hudak 1989, p. 371
  85. ^ Hudak 1989, p. 371
  86. ^ Hudak 1989, pp. 371–372
  87. ^ Hudak 1989, p. 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. ^ 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)
  94. ^ 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=87378084」から取得