「関数型プログラミング」の版間の差分
削除された内容 追加された内容
-{{工事中}}（テンプレート貼付から72時間以上経過）、脚注の整理 |
出典の意味を正確に理解していないのを修正する |
||
| (同じ利用者による、間の20版が非表示) | |||
| 1行目: | 1行目: | ||
{{独自研究|date=2014年4月}} |
|||
{{プログラミング・パラダイム}} |
{{プログラミング・パラダイム}} |
||
'''関数型プログラミング'''（かんすうがたプログラミング、{{lang-en-short|functional programming}}）とは、[[関数 (数学)|数学的な意味での関数]]を主に使うプログラミングのスタイルである<ref name="本間類地逢坂2017p3">{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。 functional programming は、'''関数プログラミング'''（かんすうプログラミング）などと訳されることもある<ref name="本間類地逢坂2017p2">{{harvnb|本間|類地|逢坂|2017|p=2}}</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>。 |
|||
== 概要 == |
== 概要 == |
||
関数型プログラミングは、[[関数]]を主軸にしたプログラミングを行うスタイルである{{R|本間類地逢坂2017p3}}。ここでの関数は、[[関数 (数学)|数学的なもの]]を指し、引数の値が定まれば結果も定まるという[[参照透過性]]を持つものである{{R|本間類地逢坂2017p3}}。 |
|||
関数型プログラミングは、[[関数]]を主軸にしたプログラミングを行うスタイルである<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。ここでの関数は、[[関数 (数学)|数学的なもの]]を指し、引数の値が定まれば結果も定まるという[[参照透過性]]を持つものである<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。 |
|||
'''参照透過性'''とは、数学的な関数と同じように同じ値を返す式を与えたら必ず同じ値を返すような性質である<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" > |
||
| 15行目: | 16行目: | ||
</syntaxhighlight> |
</syntaxhighlight> |
||
次の <code>countup</code> 関数は、同じ <code>1</code> を渡しても、それまでに <code>countup</code> 関数がどのような引数で呼ばれていたかによって、返り値が <code>1</code>, <code>2</code>, <code>3</code>, ... と変化するため、引数の値だけで結果の値が定まらないような参照透過性のない関数であり、数学的な関数とはいえない{{ |
次の <code>countup</code> 関数は、同じ <code>1</code> を渡しても、それまでに <code>countup</code> 関数がどのような引数で呼ばれていたかによって、返り値が <code>1</code>, <code>2</code>, <code>3</code>, ... と変化するため、引数の値だけで結果の値が定まらないような参照透過性のない関数であり、数学的な関数とはいえない<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。 |
||
<syntaxhighlight lang="python" > |
<syntaxhighlight lang="python" > |
||
| 25行目: | 26行目: | ||
</syntaxhighlight> |
</syntaxhighlight> |
||
関数型プログラミングは、参照透過性を持つような数学的な関数を使って組み立てた'''式'''が主役となる{{ |
関数型プログラミングは、参照透過性を持つような数学的な関数を使って組み立てた'''式'''が主役となる<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。別の箇所に定義されている処理を利用することを、手続き型プログラミング言語では「関数を実行する」や「関数を呼び出す」などと表現するが、関数型プログラミング言語では「式を評価する」という表現も良く使われる<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>。 |
||
=== 参照透過性 === |
=== 参照透過性 === |
||
{{main|参照透過性}} |
{{main|参照透過性}} |
||
参照透過性とは、同じ値を与えたら返り値も必ず同じになるような性質である{{R|本間類地逢坂2017p3}}。参照透過性を持つことは、その関数が'''状態を持たない'''ことを保証する<ref name="本間類地逢坂2017p5">{{harvnb|本間|類地|逢坂|2017|p=5}}</ref>。状態を持たない数学的な関数は、並列処理を実現するのに適している{{R|本間類地逢坂2017p5}}。関数型プログラミング言語の内で、全ての関数が参照透過性を持つようなものを純粋関数型プログラミング言語という{{R|本間類地逢坂2017p5}}。 |
|||
参照透過性とは、同じ値を与えたら返り値も必ず同じになるような性質である<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 name="本間類地逢坂2017p6">{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。このような外界とのやり取りを '''I/O (入出力)''' と呼ぶ{{R|本間類地逢坂2017p6}}。数学的な計算をするだけ、つまり <code>1 + 1</code> のようなプログラム内で完結する処理ならば、入出力を記述できなくても問題ないが、現実的なプログラムにおいてはそうでない{{R|本間類地逢坂2017p6}}。 |
|||
関数型プログラミングでは、数学的な関数を組み合わせて計算を表現するが、それだけではファイルの読み書きのような外界とのやり取りを要する処理を直接的に表現できない<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。このような外界とのやり取りを '''I/O (入出力)''' と呼ぶ<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。数学的な計算をするだけ、つまり <code>1 + 1</code> のようなプログラム内で完結する処理ならば、入出力を記述できなくても問題ないが、現実的なプログラムにおいてはそうでない<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。 |
|||
非純粋な関数型プログラミング言語においては、式を評価すると同時に I/O が発生する関数を用意することで入出力を実現する{{R|本間類地逢坂2017p6}}。たとえば、 [[F Sharp|F# 言語]]では、<code>printfn "Hi."</code> が評価されると、 <code>()</code> という値が戻ってくると同時に、画面に <code>Hi.</code> と表示される I/O が発生する{{R|本間類地逢坂2017p6}}。 |
|||
[[Haskell]] では、評価と同時に I/O が行われる関数は存在しない{{ |
非純粋な関数型プログラミング言語においては、式を評価すると同時に 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>。 |
||
[[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>。 |
|||
[[Clean]] では、一意型を用いて入出力を表す{{要出典|date=2021年3月}}。 |
[[Clean]] では、一意型を用いて入出力を表す{{要出典|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>。 |
|||
=== 言語 === |
=== 言語 === |
||
関数型プログラミング言語とは、関数型プログラミングを推奨している[[プログラミング言語]]である{{R|本間類地逢坂2017p3}}。略して関数型言語ともいう{{R|本間類地逢坂2017p3}}。全ての関数が参照透過性を持つようなものを、特に{{仮リンク|純粋関数型プログラミング言語|en|purely functional programming language}}という{{R|本間類地逢坂2017p5}}。そうでないものを非純粋であるという{{R|本間類地逢坂2017p6}}。 |
|||
関数型プログラミング言語 |
関数型プログラミング言語とは、関数型プログラミングを推奨している[[プログラミング言語]]である<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=4}}</ref>。ラムダ計算はコンピュータの計算をモデル化する体系の一つであり、記号の列を規則に基づいて変換していくことで計算が行われるものである<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>。 |
|||
{| class="wikitable sortable"<!-- 名前の欄には、それが関数型プログラミング言語であるという出典を付ける。型付けの欄には、その記述の根拠になる出典を付ける。評価戦略の欄には、その記述の根拠になる出典を付ける。純粋性の欄には、それが純粋か非純粋かの出典を付ける。理論的背景の欄には、その記述の根拠になる出典を付ける。 --> |
{| class="wikitable sortable"<!-- 名前の欄には、それが関数型プログラミング言語であるという出典を付ける。型付けの欄には、その記述の根拠になる出典を付ける。評価戦略の欄には、その記述の根拠になる出典を付ける。純粋性の欄には、それが純粋か非純粋かの出典を付ける。理論的背景の欄には、その記述の根拠になる出典を付ける。 --> |
||
| 57行目: | 67行目: | ||
! 理論的背景 |
! 理論的背景 |
||
|- |
|- |
||
| [[ |
| [[Clean]]{{要出典|date=2021年3月}} |
||
| 静的型付け{{ |
| 静的型付け{{要出典|date=2021年3月}} |
||
| 純粋{{ |
| 純粋{{要出典|date=2021年3月}} |
||
| 遅延評価{{ |
| 遅延評価{{要出典|date=2021年3月}} |
||
| |
|||
| 型付きラムダ計算{{R|本間類地逢坂2017p4}} |
|||
|- |
|- |
||
| [[ |
| [[Clojure]]{{要出典|date=2021年3月}} |
||
| 動的型付け{{要出典|date=2021年3月}} |
|||
| 非純粋{{要出典|date=2021年3月}} |
|||
| 正格評価{{要出典|date=2021年3月}} |
|||
| |
|||
|- |
|||
| [[Erlang]]{{要出典|date=2021年3月}} |
|||
| 動的型付け{{要出典|date=2021年3月}} |
|||
| 非純粋{{要出典|date=2021年3月}} |
|||
| 正格評価{{要出典|date=2021年3月}} |
|||
| |
|||
|- |
|||
| [[F Sharp|F#]]{{要出典|date=2021年3月}} |
|||
| 静的型付け{{要出典|date=2021年3月}} |
|||
| 非純粋{{要出典|date=2021年3月}} |
|||
| 正格評価{{要出典|date=2021年3月}} |
|||
| |
|||
|- |
|||
| [[Haskell]]<ref>{{harvnb|本間|類地|逢坂|2017|p=2}}</ref> |
|||
| 静的型付け<ref>{{harvnb|本間|類地|逢坂|2017|p=2}}</ref> |
|||
| 純粋<ref>{{harvnb|本間|類地|逢坂|2017|p=2}}</ref> |
|||
| 遅延評価<ref>{{harvnb|本間|類地|逢坂|2017|p=2}}</ref> |
|||
| 型付きラムダ計算<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref> |
|||
|- |
|||
| [[Idris]]{{要出典|date=2021年3月}} |
|||
| 静的型付け{{要出典|date=2021年3月}} |
|||
| 純粋{{要出典|date=2021年3月}} |
|||
| 正格評価{{要出典|date=2021年3月}} |
|||
| 型付きラムダ計算{{要出典|date=2021年3月}} |
|||
|- |
|||
| [[Lazy K]]{{要出典|date=2021年3月}} |
|||
| 型なし{{要出典|date=2021年3月}} |
|||
| 純粋{{要出典|date=2021年3月}} |
|||
| 遅延評価{{要出典|date=2021年3月}} |
|||
| コンビネータ論理{{要出典|date=2021年3月}} |
|||
|- |
|||
| [[LISP]]<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref> |
|||
| 動的型付け{{要出典|date=2021年3月}} |
| 動的型付け{{要出典|date=2021年3月}} |
||
| 非純粋{{要出典|date=2021年3月}} |
| 非純粋{{要出典|date=2021年3月}} |
||
| 方言による{{要出典|date=2021年3月}} |
| 方言による{{要出典|date=2021年3月}} |
||
| 型無しラムダ計算{{ |
| 型無しラムダ計算<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref> |
||
|- |
|||
| [[Miranda]]{{要出典|date=2021年3月}} |
|||
| 静的型付け{{要出典|date=2021年3月}} |
|||
| 純粋{{要出典|date=2021年3月}} |
|||
| 遅延評価{{要出典|date=2021年3月}} |
|||
| |
|||
|- |
|||
| [[ML (プログラミング言語)]]{{要出典|date=2021年3月}} |
|||
| 静的型付け{{要出典|date=2021年3月}} |
|||
| 非純粋{{要出典|date=2021年3月}} |
|||
| 先行評価{{要出典|date=2021年3月}} |
|||
| |
|||
|- |
|||
| [[SML]]{{要出典|date=2021年3月}} |
|||
| 静的型付け{{要出典|date=2021年3月}} |
|||
| 非純粋{{要出典|date=2021年3月}} |
|||
| 正格評価{{要出典|date=2021年3月}} |
|||
| |
|||
|- |
|||
| [[OCaml]]{{要出典|date=2021年3月}} |
|||
| 静的型付け{{要出典|date=2021年3月}} |
|||
| 非純粋{{要出典|date=2021年3月}} |
|||
| 正格評価{{要出典|date=2021年3月}} |
|||
| |
|||
|- |
|||
| [[Scala]]{{要出典|date=2021年3月}} |
|||
| 静的型付け{{要出典|date=2021年3月}} |
|||
| 非純粋{{要出典|date=2021年3月}} |
|||
| 正格評価{{要出典|date=2021年3月}} |
|||
| |
|||
|- |
|||
| [[Scheme]]{{要出典|date=2021年3月}} |
|||
| 動的型付け{{要出典|date=2021年3月}} |
|||
| 非純粋{{要出典|date=2021年3月}} |
|||
| 正格評価{{要出典|date=2021年3月}} |
|||
| |
|||
|- |
|||
| [[Unlambda]]{{要出典|date=2021年3月}} |
|||
| 型なし{{要出典|date=2021年3月}} |
|||
| 非純粋{{要出典|date=2021年3月}} |
|||
| 正格評価{{要出典|date=2021年3月}} |
|||
| コンビネータ論理{{要出典|date=2021年3月}} |
|||
|} |
|} |
||
=== |
=== 手続き型プログラミングとの比較 === |
||
広く認められた関数型プログラミングの正確な定義は存在しないが、関数型プログラミングと呼ばれるパラダイムは[[命令型プログラミング]]と比較してプログラムに対する見方が次のように異なる<ref name="faq">{{cite web|url=http://www.cs.nott.ac.uk/~gmh/faq.html|title=Frequently Asked Questions for comp.lang.functional|accessdate=May 14, 2015}}</ref>。 |
|||
*[[命令型プログラミング]]: プログラムは計算機の内部状態を変更する命令実行の列<ref>計算モデル１ 状態モデル. 計算とは、計算機の内部状態を変えてゆくもの。(中略) 状態モデルに基づくプログラミング言語. 命令型言語. (中略) 状態を変えるための命令手順書の形式. [http://nous.web.nitech.ac.jp/individual/inuzuka/lecture/PLT/PLT07/ 犬塚信博 (2007)「プログラミング言語論 第１回 イントロダクション」名古屋工業大学]</ref> |
|||
* 関数型プログラミング: プログラムは関数とその適用の組み合わせ |
|||
すなわち[[命令型プログラミング]]は計算機（あるいは[[CPU]]）の状態を変える命令をプログラムとして書くという見方を基礎としており、これはその発祥が計算機の命令 (instruction/command) や構造に密接にかかわっていることによる。一方、関数型プログラミングは「計算とは何か」という数学の理論を基礎にしており、関数型プログラミングがもつ[[計算モデル]]は'''関数モデル'''である<ref>計算モデル２ 関数モデル. (中略) 関数モデルに基づくプログラミング言語. 関数型言語. Lisp [http://nous.web.nitech.ac.jp/individual/inuzuka/lecture/PLT/PLT07/ 犬塚信博 (2007)「プログラミング言語論 第１回 イントロダクション」名古屋工業大学]</ref>。 |
|||
たとえば、1 から 10 までの整数を足し合わせるプログラムを考える{{efn|本来は[[等差数列]]の和の公式を用いて定数時間で問題を解く方法が最適解だが、ここではプログラミングスタイルの比較のため数値計算的手法を用いる。}}。[[命令型プログラミング]]では以下のように[[ループ (プログラミング)|ループ]]文を使って変数に数値を足していく（計算機の状態を書き換える）命令を繰り返し実行するという形を取る。 |
|||
* [[Pascal]]による例: |
|||
<source lang="pascal"> |
|||
program test; |
|||
var total, i : Integer; |
|||
begin |
|||
total := 0; |
|||
for i := 1 to 10 do |
|||
total := total + i; |
|||
WriteLn(total) |
|||
end. |
|||
</source> |
|||
一方、関数型プログラミングでは、繰り返しには一時変数およびループを使わず、[[サブルーチン|関数]]の[[再帰呼び出し]]を使う。 |
|||
* [[F Sharp|F#]]による例: |
|||
<source lang="fsharp"> |
|||
printfn "%d" (let rec sum x = if x > 0 then x + sum (x - 1) else 0 |
|||
sum 10) |
|||
</source> |
|||
<!-- |
|||
<source lang="haskell"> |
|||
let |
|||
sum x = if x == 0 then 0 |
|||
else x + sum (x - 1) |
|||
in |
|||
sum 10 |
|||
</source> |
|||
--> |
|||
[[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>[https://msdn.microsoft.com/ja-jp/library/dd233229(v=vs.120).aspx 関数 (F#) | MSDN]</ref>。通例、関数型言語では、[[末尾再帰]]呼び出し (tail-recursive call) の形で書かれた関数をループに展開する[[コンパイラ最適化]]により、スタックオーバーフローの危険性および再帰のオーバーヘッドを解消する。[[Scheme]]など、関数型言語の中には末尾再帰呼び出しの最適化を仕様で保証するものもある。 |
|||
それに対して、[[関数型言語]]で重要なのは式である<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>。 |
|||
また、関数型言語は文 (statement) よりも式 (expression) を中心とした言語仕様となっていることも特徴である。前述の例において、再帰関数<code>sum</code>を[[束縛 (情報工学)|束縛]]する<code>let</code>は式である。また、条件分岐の<code>if-then-else</code>も式である。文よりも式で書けることが多いほうが都合がよい。 |
|||
手続き型言語ではコンピュータへの指示を文として上から順に並べて書くのに対して、関数型言語では数多く定義した細かい式を組み合わせてプログラムを作る<ref>{{harvnb|本間|類地|逢坂|2017|p=22}}</ref>。手続き型言語では文が重要であり、関数型言語では式が重要である<ref>{{harvnb|本間|類地|逢坂|2017|pp=22–23}}</ref>。 |
|||
関数型言語は関数型プログラミングをサポートする言語ではあるが、手続き型プログラミングを行なうことも可能である。例えばF#では以下のようなPascal風の書き方もできる。 |
|||
式と文の違いとして、型が付いているかどうかというのがある<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>。 |
|||
<source lang="fsharp"> |
|||
let mutable total = 0 |
|||
for i = 1 to 10 do |
|||
total <- total + i |
|||
printfn "%d" total |
|||
</source> |
|||
ただし[[Haskell]]のようにループ構文をサポートせず、従来の手続き型プログラミングが難しいケースもある。 |
|||
逆に手続き型言語を使って関数型プログラミングを行なうことも可能であるが、末尾再帰呼び出しの最適化がサポートされるかどうかはコンパイラ次第である。 |
|||
== 歴史 == |
== 歴史 == |
||
=== 1930年代 === |
|||
関数型言語の開発において、[[アロンゾ・チャーチ]]が1932年<ref group="注釈">{{harv|Church|1932}}</ref>と1941年<ref group="注釈">{{harv|Church|1941}}</ref>に発表した[[ラムダ計算]]の研究ほど基本的で重要な影響を与えたものはない<ref name="Hudakp363">{{harvnb|Hudak|p=363}}</ref>。ラムダ計算は、それが考え出された当時は[[プログラム]]を実行するような[[コンピュータ]]が存在しなかったために[[プログラミング言語]]として見なされなかったにも関わらず、今では最初の関数型言語とされている{{R|Hudakp363}}。現代（1989年）の関数型言語は、その殆どがラムダ計算に装飾を加えたものとして見なせる{{R|Hudakp363}}。 |
|||
=== |
=== 1930 年代 === |
||
1950年代後半に[[ジョン・マッカーシー]]が発表した [[LISP]] は関数型言語の歴史において重要である<ref>{{harvnb|Hudak|p=367}}</ref>。ラムダ計算は LISP の基礎であると言われるが、マッカーシー自身が1978年<ref group="注釈">{{harv|McCarthy|1978}}</ref>に説明したところによると、[[匿名関数]]を表現したいというのが最初にあって、その手段としてマッカーシーはチャーチのラムダ計算を選択したに過ぎない<ref>{{harvnb|Hudak|pp=367–368}}</ref>。 |
|||
{{節スタブ|date=2021年3月}} |
|||
== 概要 (old) == |
|||
<!--関数型プログラミングではプログラムの構成にC言語のように関数を多用する<ref>The C language is purely functional http://conal.net/blog/posts/the-c-language-is-purely-functional</ref>。[[Wikipedia:検証可能性#通常は信頼できないとされる情報源]]-->関数型プログラミング（パラダイム）に合意された定義がないことと同じく、広く認められた関数型言語の正確な定義は存在しない。関数型プログラミングでは関数を[[第一級オブジェクト]]として扱う。理論的な計算モデルとして第一級オブジェクトとしての関数を扱える[[ラムダ計算]]や[[項書き換え]]を採用している。 |
|||
関数型言語の開発において、[[アロンゾ・チャーチ]]が 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>。 |
|||
コンピュータプログラムは通例入力を受け取って何らかの処理を行ない、出力を返すことを目的として書かれる。数学の関数<math>y = f(x)</math>において、<math>x</math>を入力、<math>y</math>を出力と考えると、コンピュータプログラムはある種の関数であると考えることができる。ここで、入力や出力は記憶装置中のファイルのようなものばかりではなく、キーボードや[[ポインティングデバイス]]によってユーザーから与えられる情報や、画面への表示といった入出力形態も考えられる。関数型プログラミングにおいては実際にそれらを扱う関数としてモデル化する。 |
|||
=== 1950 年代 === |
|||
純粋関数型言語では、[[参照透過性]]が常に保たれるという意味において、全ての[[式 (プログラミング)|式]]や関数の評価時に[[副作用 (プログラム)|副作用]]を生まない。純粋関数型言語である{{lang|en|[[Haskell]]}}や{{lang|en|[[Clean]]}}は非[[正格]]な評価を基本としており、引数はデフォルトで[[遅延評価]]される。一方、{{lang|en|[[Idris]]}}は純粋だが正格評価を採用している。入出力などを[[参照透過性]]を保ったまま実現するために、たとえば {{lang|en|Haskell}} では[[モナド (プログラミング)|モナド]]、{{lang|en|Clean}} では{{仮リンク|一意型|en|Uniqueness type}}という特殊な型を通して一貫性のある表現を提供する。 |
|||
{{節スタブ|date=2021年3月}} |
|||
非純粋関数型言語では、参照透過性を壊す、副作用があるような式や関数も存在する。{{lang|en|LISP}}などでデータ構造の破壊的変更などの副作用を多用したプログラミングを行うと、それはもはや手続き型プログラミングである。多くの場合、非純粋関数型言語の[[評価戦略]]は正格評価（先行評価）であるが、遅延評価する部分を明示することで、無限リストなどを扱えるものもある。 |
|||
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>。 |
|||
{{lang|en|[[JavaScript]]}}や{{lang|en|[[Java]]}}など{{いつ範囲|date=2018年10月|近年}}の[[高水準言語]]には、関数型言語の機能や特徴を取り入れているものがあるが、変数の値やオブジェクトの状態を書き換えるプログラミングスタイルを通常とするため、関数型言語とは分類されない。一方{{lang|en|[[LISP]]}}は、その多くが副作用のある式や関数が多数あり、手続き型スタイルでのプログラミングがされることも多いが、理論的なモデル（「[[純LISP|純{{lang|en|LISP}}]]」）の存在や副作用を使わないプログラミングが基本であること、ないし主には歴史的理由から、関数型言語だとされることが多い。なお、{{lang|fr|Pascal}}では「手続き」と呼ばれるような値を返さない[[サブルーチン]]を、C言語では<!--<code>void</code>型の値を返す関数と捉える--><!--void型の値というものは存在せず、存在しないものについて、それを返す関数と「捉える」ことは常人には困難-->「関数」と呼んでいるが、これは単にルーチンについて、細分類して別の呼称を付けているか、細分類せず総称しているか、という分類と呼称の違いに過ぎず、「{{lang|fr|Pascal}}は手続き型言語で、C言語は関数型言語」<ref group="注釈">[[共立出版]]『{{lang|en|ANSI C/C++}}辞典』ISBN 4-320-02797-3 など</ref>という一部の書籍に見られる記述は明確に誤りである。また、{{lang|en|OCaml}}や{{lang|en|Haskell}}などでは、「自明な値(例えば<code>()</code>)を返す」と、値を返さない（<code>Void</code>など）は違うものであり、後者は停止しないか例外を出す(そのため結果がない)ようなプログラムを表す。 |
|||
=== 1960 年代 === |
|||
なお、「関数型言語である」と「関数型プログラミングをする」は同値ではなく、関数型には分類されない言語で関数型プログラミングをすること{{efn|関数型プログラミングのエッセンスとして、[[MISRA C]]のように[[C言語]]でも副作用を極力用いないプログラミングを推奨しているコーディング標準もある。}}や、関数型プログラミングを基本とする言語の上で他のパラダイムを実現する例もある<ref group="注釈" name="Novatchev">{{cite web | url = http://arxiv.org/abs/cs/0509027 | author = Oleg Kiselyov, Ralf Lämmel | title = Haskell's overlooked object system | accessdate = Sep 10, 2005}}</ref>。<!--<ref>「関数型言語」に関するFAQ形式の一般的説明 https://qiita.com/esumii/items/ec589d138e72e22ea97e</ref>[[Wikipedia:検証可能性#通常は信頼できないとされる情報源]]--> |
|||
歴史的に言えば、 [[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>。 |
|||
[[データフロープログラミング]]言語も関数型言語と共通した特徴を部分的に持つ。 |
|||
* 構文についての革新<ref>{{harvnb|Hudak|1989|p=371}}</ref> |
|||
=== 歴史 (old) === |
|||
** 演算子を前置記法で記述するのをやめて中置記法を導入した<ref>{{harvnb|Hudak|1989|p=371}}</ref>。 |
|||
{{lang|en|LISP}}は、その基本機能のモデルとして関数型の純{{lang|en|LISP}}を持つなどといった特徴がある、最初の関数型言語である。今日広く使われている{{lang|en|LISP}}方言のうち特に{{lang|en|[[Scheme]]}}は関数型としての特徴が強い。 |
|||
** 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>。 |
|||
ランディンは「それをどうやって行うか」ではなく「それの望ましい結果とは何か」を表現することに重点を置いており、そして、 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>。 |
|||
現代的な関数型プログラミング言語の祖としてはアイディアが1966年に発表された{{lang|en|[[ISWIM]]}}が挙げられるが、1970年前後までは関数型プログラミング言語の歴史は{{lang|en|LISP}}の発展が主である。1970年代にプロジェクトが開始された{{仮リンク|ロジック・フォー・コンピュータブル・ファンクションズ|en|Logic for Computable Functions}}のための言語として[[ML (プログラミング言語)|ML]]が作られている。 |
|||
[[ケネス・アイバーソン]]が 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>。 |
|||
また{{lang|en|LISP}}において、変数のスコープに静的スコープを採用した{{lang|en|Scheme}}が誕生したのが1975年である。 |
|||
== 脚注 == |
|||
1977年、{{lang|en|FORTRAN}}の設計と[[バッカス・ナウア記法]]の発明の業績でこの年の[[チューリング賞]]を受賞した[[ジョン・バッカス]]は、{{lang|en|''Can Programming Be Liberated From the von Neumann Style?: A Functional Style and Its Algebra of Programs''}}<ref group="注釈">「プログラミングはフォン・ノイマン・スタイルから解放されうるか？: 関数型プログラミング・スタイルとそのプログラム代数」、[[米澤明憲]]訳『ACMチューリング賞講演集』（[[共立出版]]）pp. 83-156</ref>と題した受賞記念講演で関数型プログラミングの重要性を訴えた。講演では[[FP (プログラミング言語)|FP]]という関数型プログラミング言語の紹介もした（サブタイトルの後半の「プログラムの代数」はこれを指す）が、これは{{lang|en|[[APL]]}}（特に、[[高階関数]]の意味がある記号（{{lang|en|APL}}の用語ではオペレーター（[[作用素]]）という））の影響を受けている。 |
|||
バッカスの{{lang|en|FP}}は広く使用されることはなかったが、この後関数型プログラミング言語の研究・開発は広まることとなった。1985年に{{lang|en|[[Miranda]]}}が登場した。1987年に、遅延評価の純粋関数型プログラミング言語の標準の必要性が認識され{{lang|en|Haskell}}の策定が始まった。1990年に{{lang|en|Haskell}} 1.0仕様がリリースされた。同じく1990年には{{lang|en|ML}}の標準である{{lang|en|[[Standard ML]]}}もリリースされている。 |
|||
{{lang|en|Clean}}は1987年に登場したが、発展の過程で{{lang|en|Haskell}}の影響を受けている。1996年に、ML処理系のひとつであった{{lang|en|Caml}}に[[オブジェクト指向]]を追加した{{lang|en|OCaml}}が登場した。また日本ではSMLに独自の拡張を施した{{lang|en|[[SML#]]}}が開発されている。 |
|||
21世紀に入ると、[[Java仮想マシン|{{lang|en|Java}}仮想マシン]]や[[共通言語基盤]]（{{lang|en|CLI}}）をランタイムとする関数型プログラミング言語を実装しようという動きが現れ、{{lang|en|[[Scala]]}}・{{lang|en|[[Clojure]]}}・{{lang|en|[[F Sharp|F#]]}}などが登場した。 |
|||
=== 代表的な関数型言語 === |
|||
{|class="wikitable sortable" |
|||
!言語 |
|||
!純粋さ |
|||
!型付け |
|||
|- |
|||
|{{lang|en|[[Clean]]}}||純粋||強い、静的 |
|||
|- |
|||
|{{lang|en|[[Clojure]]}}||非純粋||動的 |
|||
|- |
|||
|{{lang|en|[[Erlang]]}}||非純粋||動的 |
|||
|- |
|||
|{{lang|en|[[F Sharp|F#]]}}||非純粋||強い、静的 |
|||
|- |
|||
|{{lang|en|[[Haskell]]}}||純粋||強い、静的 |
|||
|- |
|||
|{{lang|en|[[Idris]]}}||純粋||強い、静的 |
|||
|- |
|||
|{{lang|en|[[Lazy K]]}}||純粋||型なし |
|||
|- |
|||
|{{lang|en|[[LISP]]}}||非純粋||動的 |
|||
|- |
|||
|{{lang|en|[[Miranda]]}}||純粋||強い、静的 |
|||
|- |
|||
|{{lang|en|[[ML (プログラミング言語)|ML]]}}||非純粋||強い、静的 |
|||
|- |
|||
|{{lang|en|[[SML#]]}}||非純粋||強い、静的 |
|||
|- |
|||
|{{lang|en|[[Standard ML]]}}||非純粋||強い、静的 |
|||
|- |
|||
|{{lang|en|[[OCaml]]}}||非純粋||強い、静的 |
|||
|- |
|||
|{{lang|en|[[Scala]]}}||非純粋||強い、静的 |
|||
|- |
|||
|{{lang|en|[[Scheme]]}}||非純粋||動的 |
|||
|- |
|||
|{{lang|en|[[Unlambda]]}}||非純粋||型なし |
|||
|} |
|||
{{脚注ヘルプ}} |
|||
従来の手続き型と分類されるプログラミング言語においても、関数型プログラミングを行ないやすくなる機能を備えているものもある。[[C言語]]および[[C++]]は[[関数へのポインタ]]をサポートし、関数をオブジェクトのように扱うことができるが、関数ポインタによって[[第一級関数]]をサポートしているとみなされてはいない。なお、C# 3.0、[[C++11]]、Java 8など、後発の規格においてラムダ式（[[無名関数]]）をサポートするようになった言語もある。 |
|||
=== 注釈 === |
|||
==== その他の関数的性質を持つ言語 ==== |
|||
* {{lang|en|[[APL]]}} |
|||
* {{lang|en|[[XSL Transformations|XSLT]]}} |
|||
== 脚注 == |
|||
{{脚注ヘルプ}} |
|||
=== 注釈 === |
|||
{{Notelist}} |
{{Notelist}} |
||
=== 出典 === |
=== 出典 === |
||
{{Reflist}} |
{{Reflist}} |
||
== 参考文献 == |
== 参考文献 == |
||
* {{Cite Q|Q55890017|last=Church|firstAlonzo}} |
|||
* {{Cite Q| |
* {{Cite Q|Q55890017|last=Church|first=Alonzo}} |
||
* {{Cite Q|Q105884272|last=Church|first=Alonzo}} |
|||
* {{Cite Q|Q55871443|last=Hudak|first=Paul}} |
* {{Cite Q|Q55871443|last=Hudak|first=Paul}} |
||
* {{Cite Q|Q105954505|last=Iverson|first=Kenneth}} |
|||
* {{Cite Q|Q56048080|last=McCarthy|first=John}} |
* {{Cite Q|Q56048080|last=McCarthy|first=John}} |
||
* {{Cite Q|Q30040385|last=Landin|first=Peter}} |
|||
* {{Cite Q|Q105941120|last=Landin|first=Peter}} |
|||
* {{Cite Q|Q54002422|last=Landin|first=Peter}} |
|||
* {{Cite Q|Q105845956|edition=1st (1st printing)|last=Lipovača|first=Miran}} |
* {{Cite Q|Q105845956|edition=1st (1st printing)|last=Lipovača|first=Miran}} |
||
* {{Cite Q|Q105833610|edition=1st (1st printing)|last=本間|first=雅洋|last2=類地|first2=孝介|last3=逢坂|first3=時響}} |
* {{Cite Q|Q105833610|edition=1st (1st printing)|last=本間|first=雅洋|last2=類地|first2=孝介|last3=逢坂|first3=時響}} |
||
== 外部リンク == |
== 外部リンク == |
||
* [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年5月1日 (土) 14:41時点における版
| プログラミング・パラダイム |
|---|
関数型プログラミング（かんすうがたプログラミング、英: functional programming）とは、数学的な意味での関数を主に使うプログラミングのスタイルである[1]。 functional programming は、関数プログラミング（かんすうプログラミング）などと訳されることもある[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]。このような外界とのやり取りを I/O (入出力) と呼ぶ[17]。数学的な計算をするだけ、つまり 1 + 1 のようなプログラム内で完結する処理ならば、入出力を記述できなくても問題ないが、現実的なプログラムにおいてはそうでない[18]。
非純粋な関数型プログラミング言語においては、式を評価すると同時に I/O が発生する関数を用意することで入出力を実現する[19]。たとえば、 F# 言語では、printfn "Hi." が評価されると、 () という値が戻ってくると同時に、画面に Hi. と表示される I/O が発生する[20]。
Haskell では、評価と同時に I/O が行われる関数は存在しない[21]。たとえば、 putStrLn "Hi." という式が評価されると IO () 型を持つ値が返されるが画面には何も表示されず、この値が Haskell の処理系によって解釈されて始めて画面に Hi. と表示される[22]。 I/O アクションとは、ファイルの読み書きやディスプレイへの表示などのような I/O を表現する式のことである[23][24]。 IO a という型は、コンピュータへの指示を表す I/O アクションを表現している[25][26]。ここでの IO はモナドと呼ばれるものの一つである[27]。
手法
![[icon]](/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Wiki_letter_w_cropped.svg){kind=small} | この節の加筆が望まれています。 |
最初に解の集合となる候補を生成し、それらの要素に対して 1 つ（もしくは複数）の解に辿り着くまで関数の適用とフィルタリングを繰り返す手法は、関数型プログラミングでよく用いられるパターンである[28]。
Haskell では、関数合成の二項演算子を使ってポイントフリースタイルで関数を定義することができる[29]。関数をポイントフリースタイルで定義すると、データより関数にに目が行くようになり、どのようにデータが移り変わっていくかではなく、どんな関数を合成して何になっているかということへ意識が向くため、定義が読みやすく簡潔になることがある[30]。関数が複雑になりすぎると、ポイントフリースタイルでは逆に可読性が悪くなることもある[31]。
言語
関数型プログラミング言語とは、関数型プログラミングを推奨しているプログラミング言語である[32]。略して関数型言語ともいう[33]。全ての関数が参照透過性を持つようなものを、特に純粋関数型プログラミング言語という[34]。そうでないものを非純粋であるという[35]。
関数型プログラミング言語の多くは、言語の設計において何らかの形でラムダ計算が関わっている[36]。ラムダ計算はコンピュータの計算をモデル化する体系の一つであり、記号の列を規則に基づいて変換していくことで計算が行われるものである[37]。
| 名前 | 型付け | 純粋性 | 評価戦略 | 理論的背景 |
|---|---|---|---|---|
| Clean[要出典] | 静的型付け[要出典] | 純粋[要出典] | 遅延評価[要出典] | |
| Clojure[要出典] | 動的型付け[要出典] | 非純粋[要出典] | 正格評価[要出典] | |
| Erlang[要出典] | 動的型付け[要出典] | 非純粋[要出典] | 正格評価[要出典] | |
| F#[要出典] | 静的型付け[要出典] | 非純粋[要出典] | 正格評価[要出典] | |
| Haskell[38] | 静的型付け[39] | 純粋[40] | 遅延評価[41] | 型付きラムダ計算[42] |
| Idris[要出典] | 静的型付け[要出典] | 純粋[要出典] | 正格評価[要出典] | 型付きラムダ計算[要出典] |
| Lazy K[要出典] | 型なし[要出典] | 純粋[要出典] | 遅延評価[要出典] | コンビネータ論理[要出典] |
| LISP[43] | 動的型付け[要出典] | 非純粋[要出典] | 方言による[要出典] | 型無しラムダ計算[44] |
| Miranda[要出典] | 静的型付け[要出典] | 純粋[要出典] | 遅延評価[要出典] | |
| ML (プログラミング言語)[要出典] | 静的型付け[要出典] | 非純粋[要出典] | 先行評価[要出典] | |
| SML[要出典] | 静的型付け[要出典] | 非純粋[要出典] | 正格評価[要出典] | |
| OCaml[要出典] | 静的型付け[要出典] | 非純粋[要出典] | 正格評価[要出典] | |
| Scala[要出典] | 静的型付け[要出典] | 非純粋[要出典] | 正格評価[要出典] | |
| Scheme[要出典] | 動的型付け[要出典] | 非純粋[要出典] | 正格評価[要出典] | |
| Unlambda[要出典] | 型なし[要出典] | 非純粋[要出典] | 正格評価[要出典] | コンビネータ論理[要出典] |
手続き型プログラミングとの比較
C 言語や Java や JavaScript や Python や Ruby などの 2017 年現在に使われている言語の多くは、手続き型の文法を持っている[45]。そのような言語では、文法として式 (expression) と文 (statement) を持つ[46]。ここでの式は、計算を実行して結果を得るような処理を記述するための文法要素であり、加減乗除や関数呼び出しなどから構成されている[47]。ここでの文は、何らかの動作を行うようにコンピュータへ指示するための文法要素であり、条件分岐の if 文やループの for 文と while 文などから構成されている[48]。手続き型の文法では、式で必要な計算を進め、その結果を元にして文でコンピュータ命令を行うという形で、プログラムを記述する[49]。このように、手続き型言語で重要なのは文である[50]。
それに対して、関数型言語で重要なのは式である[51]。関数型言語のプログラムはたくさんの式で構成され、プログラムそのものも一つの式である[52]。たとえば、 Haskell では、プログラムの処理の記述において文は使われず、外部の定義を取り込む import 宣言も処理の一部として扱えない[53]。関数型言語におけるプログラムの実行とは、プログラムを表す式の計算を進めて、その結果として値 (value) を得ることである[54]。式を計算することを、評価する (evaluate) という[55]。
手続き型言語ではコンピュータへの指示を文として上から順に並べて書くのに対して、関数型言語では数多く定義した細かい式を組み合わせてプログラムを作る[56]。手続き型言語では文が重要であり、関数型言語では式が重要である[57]。
式と文の違いとして、型が付いているかどうかというのがある[58]。式は型を持つが、文は型を持たない[59]。プログラム全てが式から構成されていて、強い静的型付けがされているのならば、プログラムの全体が細部まで型付けされることになる[60]。このように細部まで型付けされているようなプログラムは堅固なものになる[61]。
歴史
1930 年代
| この節の加筆が望まれています。 |
関数型言語の開発において、アロンゾ・チャーチが 1932 年[注釈 1]と 1941 年[注釈 2]に発表したラムダ計算の研究ほど基本的で重要な影響を与えたものはない[62]。ラムダ計算は、それが考え出された当時はプログラムを実行するようなコンピュータが存在しなかったためにプログラミング言語として見なされなかったにも関わらず、今では最初の関数型言語とされている[63]。 1989 年現在の関数型言語は、その殆どがラムダ計算に装飾を加えたものとして見なせる[64]。
1950 年代
| この節の加筆が望まれています。 |
1950 年代後半にジョン・マッカーシーが発表した LISP は関数型言語の歴史において重要である[65]。ラムダ計算は LISP の基礎であると言われるが、マッカーシー自身が 1978 年[注釈 3]に説明したところによると、匿名関数を表現したいというのが最初にあって、その手段としてマッカーシーはチャーチのラムダ計算を選択したに過ぎない[66]。
1960 年代
歴史的に言えば、 LISP に続いて関数型プログラミングパラダイムへ刺激を与えたのは、 1960 年代半ばのピーター・ランディンの成果である[67]。ランディンの成果はハスケル・カリーとアロンゾ・チャーチに大きな影響を受けていた[68]。ランディンの初期の論文は、ラムダ計算と、機械および高級言語 (ALGOL 60) との関係について議論している[69]。ランディンは、 1964 年[注釈 4]に、 SECD マシンと呼ばれる抽象的な機械を使って機械的に式を評価する方法を論じ、 1965 年[注釈 5]に、ラムダ計算で ALGOL 60 の非自明なサブセットを形式化した[70]。1966 年[注釈 6]にランディンが発表した ISWIM (If You See What I Mean の略) という言語（群）は、間違いなく、これらの研究の成果であり、構文や意味論において多くの重要なアイデアを含んでいた[71]。 ISWIM は、ランディン本人によれば、「 LISP を、その名前にも表れたリストへのこだわり、手作業のメモリ割り当て、ハードウェアに依存した教育方法、重い括弧、伝統への妥協、から解放しようとする試みとして見ることができる」[72]。関数型言語の歴史において ISWIM は次のような貢献を果たした[73]。
ランディンは「それをどうやって行うか」ではなく「それの望ましい結果とは何か」を表現することに重点を置いており、そして、 ISWIM の宣言的なプログラミング・スタイルは命令的なプログラミング・スタイルよりも優れているというランディンの主張は、今日まで関数型プログラミングの賛同者たちから支持されてきた[82]。その一方で、関数型言語への関心が高まるまでは、さらに 10 年を要した[83]。その理由の一つは、 ISWIM ライクな言語の実用的な実装がなかったことであり、実のところ、この状況は 1980 年代になるまで変わらなかった[84]。
ケネス・アイバーソンが 1962 年[注釈 7]に発表した APL は、純粋な関数型プログラミング言語ではないが、その関数型的な部分を取り出したサブセットがラムダ式に頼らずに関数型プログラミングを実現する方法の一例であるという点で、関数型プログラミング言語の歴史を考察する際に言及する価値はある[85]。実際に、アイバーソンが APL を設計した動機は、配列のための代数的なプログラミング言語を開発したいというものであり、アイバーソンのオリジナル版は基本的に関数型的な記法を用いていた[86]。その後の APL では、いくつかの命令型的な機能が追加されている[87]。
脚注
注釈
- ^ (Church 1932)
- ^ (Church 1941)
- ^ (McCarthy 1978)
- ^ (Landin 1964)
- ^ (Landin 1965)
- ^ (Landin 1966)
- ^ (Iverson 1962)
出典
- ^ 本間, 類地 & 逢坂 2017, p. 3
- ^ 本間, 類地 & 逢坂 2017, p. 2
- ^ 本間, 類地 & 逢坂 2017, p. 3
- ^ 本間, 類地 & 逢坂 2017, p. 3
- ^ 本間, 類地 & 逢坂 2017, p. 3
- ^ 本間, 類地 & 逢坂 2017, p. 3
- ^ 本間, 類地 & 逢坂 2017, p. 3
- ^ 本間, 類地 & 逢坂 2017, p. 3
- ^ 本間, 類地 & 逢坂 2017, p. 3
- ^ 本間, 類地 & 逢坂 2017, p. 3
- ^ 本間, 類地 & 逢坂 2017, p. 4
- ^ 本間, 類地 & 逢坂 2017, p. 3
- ^ 本間, 類地 & 逢坂 2017, p. 5
- ^ 本間, 類地 & 逢坂 2017, p. 5
- ^ 本間, 類地 & 逢坂 2017, p. 5
- ^ 本間, 類地 & 逢坂 2017, p. 6
- ^ 本間, 類地 & 逢坂 2017, p. 6
- ^ 本間, 類地 & 逢坂 2017, p. 6
- ^ 本間, 類地 & 逢坂 2017, p. 6
- ^ 本間, 類地 & 逢坂 2017, p. 6
- ^ 本間, 類地 & 逢坂 2017, p. 6
- ^ 本間, 類地 & 逢坂 2017, p. 6
- ^ 本間, 類地 & 逢坂 2017, p. 6
- ^ 本間, 類地 & 逢坂 2017, p. 23
- ^ 本間, 類地 & 逢坂 2017, p. 6
- ^ 本間, 類地 & 逢坂 2017, p. 31
- ^ 本間, 類地 & 逢坂 2017, p. 32
- ^ Lipovača 2012, p. 22
- ^ Lipovača 2012, p. 22
- ^ Lipovača 2012, p. 22
- ^ Lipovača 2012, p. 22
- ^ 本間, 類地 & 逢坂 2017, p. 3
- ^ 本間, 類地 & 逢坂 2017, p. 3
- ^ 本間, 類地 & 逢坂 2017, p. 5
- ^ 本間, 類地 & 逢坂 2017, p. 6
- ^ 本間, 類地 & 逢坂 2017, p. 4
- ^ 本間, 類地 & 逢坂 2017, p. 4
- ^ 本間, 類地 & 逢坂 2017, p. 2
- ^ 本間, 類地 & 逢坂 2017, p. 2
- ^ 本間, 類地 & 逢坂 2017, p. 2
- ^ 本間, 類地 & 逢坂 2017, p. 2
- ^ 本間, 類地 & 逢坂 2017, p. 4
- ^ 本間, 類地 & 逢坂 2017, p. 4
- ^ 本間, 類地 & 逢坂 2017, p. 4
- ^ 本間, 類地 & 逢坂 2017, p. 22
- ^ 本間, 類地 & 逢坂 2017, p. 22
- ^ 本間, 類地 & 逢坂 2017, p. 22
- ^ 本間, 類地 & 逢坂 2017, p. 22
- ^ 本間, 類地 & 逢坂 2017, p. 22
- ^ 本間, 類地 & 逢坂 2017, p. 22
- ^ 本間, 類地 & 逢坂 2017, p. 22
- ^ 本間, 類地 & 逢坂 2017, p. 22
- ^ 本間, 類地 & 逢坂 2017, p. 22
- ^ 本間, 類地 & 逢坂 2017, p. 22
- ^ 本間, 類地 & 逢坂 2017, p. 22
- ^ 本間, 類地 & 逢坂 2017, p. 22
- ^ 本間, 類地 & 逢坂 2017, pp. 22–23
- ^ 本間, 類地 & 逢坂 2017, pp. 22–23
- ^ 本間, 類地 & 逢坂 2017, pp. 22–23
- ^ 本間, 類地 & 逢坂 2017, pp. 22–23
- ^ 本間, 類地 & 逢坂 2017, pp. 22–23
- ^ Hudak 1989, p. 363
- ^ Hudak 1989, p. 363
- ^ Hudak 1989, p. 363
- ^ Hudak 1989, p. 367
- ^ Hudak 1989, pp. 367–368
- ^ Hudak 1989, p. 371
- ^ Hudak 1989, p. 371
- ^ Hudak 1989, p. 371
- ^ Hudak 1989, p. 371
- ^ Hudak 1989, p. 371
- ^ Hudak 1989, p. 371
- ^ Hudak 1989, pp. 371–372
- ^ Hudak 1989, p. 371
- ^ Hudak 1989, p. 371
- ^ Hudak 1989, p. 371
- ^ Hudak 1989, p. 371
- ^ Hudak 1989, pp. 371–372
- ^ Hudak 1989, p. 371
- ^ Hudak 1989, p. 371
- ^ Hudak 1989, pp. 371–372
- ^ Hudak 1989, p. 372
- ^ Hudak 1989, p. 372
- ^ Hudak 1989, p. 372
- ^ Hudak 1989, p. 372
- ^ Hudak 1989, p. 372
- ^ 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, 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
