コンテンツにスキップ

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

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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
削除された内容 追加された内容
m 改名が終了したのでテンプレートを剥がす
タグ: 手動差し戻し
m Template:Cite_Q のバグを修正したので、それに対応するためだった特殊な記述を消す
(同じ利用者による、間の25版が非表示)
1行目: 1行目:
{{工事中}}
{{独自研究|date=2014年4月}}
{{独自研究|date=2014年4月}}
{{プログラミング言語|index=かんすうかたけんこ}}
{{プログラミング・パラダイム}}

'''関数型言語'''(かんすうがたげんご、{{lang-en-short|functional language}}、関数型プログラミング言語とも)は、関数型プログラミングを基本スタイルとする[[プログラミング言語]]の総称である{{efn|{{lang-en-short|functional programming language}}}}。
'''関数型プログラミング'''(かんすうがたプログラミング、{{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>。次の <code>square</code> 関数は、 <code>2</code> となるような式を与えれば必ず <code>4</code> を返し、 <code>3</code> となるような式を与えれば必ず <code>9</code> を返し、いかなる状況でも別の値を返すということはなく、これが参照透過性を持つ関数の一例となる<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。

<syntaxhighlight lang="python" >
def square(n):
return n ** 2
</syntaxhighlight>

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

<syntaxhighlight lang="python" >
counter = 0
def countup(n):
global counter
counter += n
return counter
</syntaxhighlight>

関数型プログラミングは、参照透過性を持つような数学的な関数を使って組み立てた'''式'''が主役となる<ref>{{harvnb|本間|類地|逢坂|2017|p=3}}</ref>。別の箇所に定義されている処理を利用することを、手続き型プログラミング言語では「関数を実行する」や「関数を呼び出す」などと表現するが、関数型プログラミング言語では「式を評価する」という表現も良く使われる<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>。

=== 参照透過性 ===

{{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=6}}</ref>。このような外界とのやり取りを '''I/O (入出力)''' と呼ぶ<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。数学的な計算をするだけ、つまり <code>1 + 1</code> のようなプログラム内で完結する処理ならば、入出力を記述できなくても問題ないが、現実的なプログラムにおいてはそうでない<ref>{{harvnb|本間|類地|逢坂|2017|p=6}}</ref>。

非純粋な関数型プログラミング言語においては、式を評価すると同時に 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月}}。

=== 手法 ===

最初に解の集合となる候補を生成し、それらの要素に対して 1 つ(もしくは複数)の解に辿り着くまで関数の適用とフィルタリングを繰り返す手法は、関数型プログラミングでよく用いられるパターンである<ref>{{harvnb|Lipovača|2012|p=22}}</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=4}}</ref>。ラムダ計算はコンピュータの計算をモデル化する体系の一つであり、記号の列を規則に基づいて変換していくことで計算が行われるものである<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>。

{| class="wikitable sortable"<!-- 名前の欄には、それが関数型プログラミング言語であるという出典を付ける。型付けの欄には、その記述の根拠になる出典を付ける。評価戦略の欄には、その記述の根拠になる出典を付ける。純粋性の欄には、それが純粋か非純粋かの出典を付ける。理論的背景の欄には、その記述の根拠になる出典を付ける。 -->
|+ 関数型プログラミング言語
|-
! 名前
! 型付け
! 純粋性
! 評価戦略
! 理論的背景
|-
| [[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>
|-
| [[LISP]]<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>
| 動的型付け{{要出典|date=2021年3月}}
| 非純粋{{要出典|date=2021年3月}}
| 方言による{{要出典|date=2021年3月}}
| 型無しラムダ計算<ref>{{harvnb|本間|類地|逢坂|2017|p=4}}</ref>
|}

=== 命令型プログラミングとの比較 ===


== 関数型プログラミング ==
広く認められた関数型プログラミングの正確な定義は存在しないが、関数型プログラミングと呼ばれるパラダイムは[[命令型プログラミング]]と比較してプログラムに対する見方が次のように異なる<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 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>。


59行目: 135行目:
逆に手続き型言語を使って関数型プログラミングを行なうことも可能であるが、末尾再帰呼び出しの最適化がサポートされるかどうかはコンパイラ次第である。
逆に手続き型言語を使って関数型プログラミングを行なうことも可能であるが、末尾再帰呼び出しの最適化がサポートされるかどうかはコンパイラ次第である。


== 概要 ==
== 歴史 ==

=== 1930年代 ===

関数型言語の開発において、[[アロンゾ・チャーチ]]が1932年<ref group="注釈">{{harv|Church|1932}}</ref>と1941年<ref group="注釈">{{harv|Church|1941}}</ref>に発表した[[ラムダ計算]]の研究ほど基本的で重要な影響を与えたものはない<ref>{{harvnb|Hudak|p=363}}</ref>。ラムダ計算は、それが考え出された当時は[[プログラム]]を実行するような[[コンピュータ]]が存在しなかったために[[プログラミング言語]]として見なされなかったにも関わらず、今では最初の関数型言語とされている<ref>{{harvnb|Hudak|p=363}}</ref>。現代(1989年)の関数型言語は、その殆どがラムダ計算に装飾を加えたものとして見なせる<ref>{{harvnb|Hudak|p=363}}</ref>。

=== 1950年代 ===

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

== 概要 (old) ==
<!--関数型プログラミングではプログラムの構成にC言語のように関数を多用する<ref>The C language is purely functional http://conal.net/blog/posts/the-c-language-is-purely-functional</ref>。[[Wikipedia:検証可能性#通常は信頼できないとされる情報源]]-->関数型プログラミング(パラダイム)に合意された定義がないことと同じく、広く認められた関数型言語の正確な定義は存在しない。関数型プログラミングでは関数を[[第一級オブジェクト]]として扱う。理論的な計算モデルとして第一級オブジェクトとしての関数を扱える[[ラムダ計算]]や[[項書き換え]]を採用している。
<!--関数型プログラミングではプログラムの構成にC言語のように関数を多用する<ref>The C language is purely functional http://conal.net/blog/posts/the-c-language-is-purely-functional</ref>。[[Wikipedia:検証可能性#通常は信頼できないとされる情報源]]-->関数型プログラミング(パラダイム)に合意された定義がないことと同じく、広く認められた関数型言語の正確な定義は存在しない。関数型プログラミングでは関数を[[第一級オブジェクト]]として扱う。理論的な計算モデルとして第一級オブジェクトとしての関数を扱える[[ラムダ計算]]や[[項書き換え]]を採用している。


68行目: 154行目:
非純粋関数型言語では、参照透過性を壊す、副作用があるような式や関数も存在する。{{lang|en|LISP}}などでデータ構造の破壊的変更などの副作用を多用したプログラミングを行うと、それはもはや手続き型プログラミングである。多くの場合、非純粋関数型言語の[[評価戦略]]は正格評価(先行評価)であるが、遅延評価する部分を明示することで、無限リストなどを扱えるものもある。
非純粋関数型言語では、参照透過性を壊す、副作用があるような式や関数も存在する。{{lang|en|LISP}}などでデータ構造の破壊的変更などの副作用を多用したプログラミングを行うと、それはもはや手続き型プログラミングである。多くの場合、非純粋関数型言語の[[評価戦略]]は正格評価(先行評価)であるが、遅延評価する部分を明示することで、無限リストなどを扱えるものもある。


{{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>[[共立出版]]『{{lang|en|ANSI C/C++}}辞典』ISBN 4-320-02797-3 など</ref>という一部の書籍に見られる記述は明確に誤りである。また、{{lang|en|OCaml}}や{{lang|en|Haskell}}などでは、「自明な値(例えば<code>()</code>)を返す」と、値を返さない(<code>Void</code>など)は違うものであり、後者は停止しないか例外を出す(そのため結果がない)ようなプログラムを表す。
{{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>など)は違うものであり、後者は停止しないか例外を出す(そのため結果がない)ようなプログラムを表す。


なお、「関数型言語である」と「関数型プログラミングをする」は同値ではなく、関数型には分類されない言語で関数型プログラミングをすること{{efn|関数型プログラミングのエッセンスとして、[[MISRA C]]のように[[C言語]]でも副作用を極力用いないプログラミングを推奨しているコーディング標準もある。}}や、関数型プログラミングを基本とする言語の上で他のパラダイムを実現する例もある<ref 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:検証可能性#通常は信頼できないとされる情報源]]-->
なお、「関数型言語である」と「関数型プログラミングをする」は同値ではなく、関数型には分類されない言語で関数型プログラミングをすること{{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:検証可能性#通常は信頼できないとされる情報源]]-->


[[データフロープログラミング]]言語も関数型言語と共通した特徴を部分的に持つ。
[[データフロープログラミング]]言語も関数型言語と共通した特徴を部分的に持つ。


== 歴史 ==
=== 歴史 (old) ===
{{lang|en|LISP}}は、その基本機能のモデルとして関数型の純{{lang|en|LISP}}を持つなどといった特徴がある、最初の関数型言語である。今日広く使われている{{lang|en|LISP}}方言のうち特に{{lang|en|[[Scheme]]}}は関数型としての特徴が強い。
{{lang|en|LISP}}は、その基本機能のモデルとして関数型の純{{lang|en|LISP}}を持つなどといった特徴がある、最初の関数型言語である。今日広く使われている{{lang|en|LISP}}方言のうち特に{{lang|en|[[Scheme]]}}は関数型としての特徴が強い。


81行目: 167行目:
また{{lang|en|LISP}}において、変数のスコープに静的スコープを採用した{{lang|en|Scheme}}が誕生したのが1975年である。
また{{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>「プログラミングはフォン・ノイマン・スタイルから解放されうるか?: 関数型プログラミング・スタイルとそのプログラム代数」、[[米澤明憲]]訳『ACMチューリング賞講演集』([[共立出版]])pp. 83-156</ref>と題した受賞記念講演で関数型プログラミングの重要性を訴えた。講演では[[FP (プログラミング言語)|FP]]という関数型プログラミング言語の紹介もした(サブタイトルの後半の「プログラムの代数」はこれを指す)が、これは{{lang|en|[[APL]]}}(特に、[[高階関数]]の意味がある記号({{lang|en|APL}}の用語ではオペレーター([[作用素]])という))の影響を受けている。
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|FP}}は広く使用されることはなかったが、この後関数型プログラミング言語の研究・開発は広まることとなった。1985年に{{lang|en|[[Miranda]]}}が登場した。1987年に、遅延評価の純粋関数型プログラミング言語の標準の必要性が認識され{{lang|en|Haskell}}の策定が始まった。1990年に{{lang|en|Haskell}} 1.0仕様がリリースされた。同じく1990年には{{lang|en|ML}}の標準である{{lang|en|[[Standard ML]]}}もリリースされている。
89行目: 175行目:
21世紀に入ると、[[Java仮想マシン|{{lang|en|Java}}仮想マシン]]や[[共通言語基盤]]({{lang|en|CLI}})をランタイムとする関数型プログラミング言語を実装しようという動きが現れ、{{lang|en|[[Scala]]}}・{{lang|en|[[Clojure]]}}・{{lang|en|[[F Sharp|F#]]}}などが登場した。
21世紀に入ると、[[Java仮想マシン|{{lang|en|Java}}仮想マシン]]や[[共通言語基盤]]({{lang|en|CLI}})をランタイムとする関数型プログラミング言語を実装しようという動きが現れ、{{lang|en|[[Scala]]}}・{{lang|en|[[Clojure]]}}・{{lang|en|[[F Sharp|F#]]}}などが登場した。


== 代表的な関数型言語 ==
=== 代表的な関数型言語 ===
{|class="wikitable sortable"
{|class="wikitable sortable"
!言語
!言語
130行目: 216行目:
従来の手続き型と分類されるプログラミング言語においても、関数型プログラミングを行ないやすくなる機能を備えているものもある。[[C言語]]および[[C++]]は[[関数へのポインタ]]をサポートし、関数をオブジェクトのように扱うことができるが、関数ポインタによって[[第一級関数]]をサポートしているとみなされてはいない。なお、C# 3.0、[[C++11]]、Java 8など、後発の規格においてラムダ式([[無名関数]])をサポートするようになった言語もある。
従来の手続き型と分類されるプログラミング言語においても、関数型プログラミングを行ないやすくなる機能を備えているものもある。[[C言語]]および[[C++]]は[[関数へのポインタ]]をサポートし、関数をオブジェクトのように扱うことができるが、関数ポインタによって[[第一級関数]]をサポートしているとみなされてはいない。なお、C# 3.0、[[C++11]]、Java 8など、後発の規格においてラムダ式([[無名関数]])をサポートするようになった言語もある。


=== その他の関数的性質を持つ言語 ===
==== その他の関数的性質を持つ言語 ====
* {{lang|en|[[APL]]}}
* {{lang|en|[[APL]]}}
* {{lang|en|[[XSL Transformations|XSLT]]}}
* {{lang|en|[[XSL Transformations|XSLT]]}}


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

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

=== 注釈 ===
=== 注釈 ===

{{Notelist}}
{{Notelist}}

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

{{Reflist}}
{{Reflist}}

== 参考文献 ==

* {{Cite Q|Q55890017|last=Church|firstAlonzo}}
* {{Cite Q|Q105884272|last=Church|firstAlonzo}}
* {{Cite Q|Q55871443|last=Hudak|first=Paul}}
* {{Cite Q|Q56048080|last=McCarthy|first=John}}
* {{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=時響}}


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

* [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}}]
* [http://www.topxml.com/xsl/articles/fp/ {{lang|en|The Functional Programming Language XSLT - A proof through examples}}]



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


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

2021年3月12日 (金) 07:29時点における版

関数型プログラミング(かんすうがたプログラミング、: 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]

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

手法

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

言語

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

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

関数型プログラミング言語
名前 型付け 純粋性 評価戦略 理論的背景
Haskell[35] 静的型付け[36] 純粋[37] 遅延評価[38] 型付きラムダ計算[39]
LISP[40] 動的型付け[要出典] 非純粋[要出典] 方言による[要出典] 型無しラムダ計算[41]

命令型プログラミングとの比較

広く認められた関数型プログラミングの正確な定義は存在しないが、関数型プログラミングと呼ばれるパラダイムは命令型プログラミングと比較してプログラムに対する見方が次のように異なる[42]

  • 命令型プログラミング: プログラムは計算機の内部状態を変更する命令実行の列[43]
  • 関数型プログラミング: プログラムは関数とその適用の組み合わせ

すなわち命令型プログラミングは計算機(あるいはCPU)の状態を変える命令をプログラムとして書くという見方を基礎としており、これはその発祥が計算機の命令 (instruction/command) や構造に密接にかかわっていることによる。一方、関数型プログラミングは「計算とは何か」という数学の理論を基礎にしており、関数型プログラミングがもつ計算モデル関数モデルである[44]

たとえば、1 から 10 までの整数を足し合わせるプログラムを考える[注釈 1]命令型プログラミングでは以下のようにループ文を使って変数に数値を足していく(計算機の状態を書き換える)命令を繰り返し実行するという形を取る。

program test;
var total, i : Integer;
begin
total := 0;
for i := 1 to 10 do
    total := total + i;
WriteLn(total)
end.

一方、関数型プログラミングでは、繰り返しには一時変数およびループを使わず、関数再帰呼び出しを使う。

  • F#による例:
printfn "%d" (let rec sum x = if x > 0 then x + sum (x - 1) else 0
              sum 10)

ただし再帰呼び出しはスタックオーバーフローの危険性やオーバーヘッドを伴うため、注意深く使用しなければならない[45]。通例、関数型言語では、末尾再帰呼び出し (tail-recursive call) の形で書かれた関数をループに展開するコンパイラ最適化により、スタックオーバーフローの危険性および再帰のオーバーヘッドを解消する。Schemeなど、関数型言語の中には末尾再帰呼び出しの最適化を仕様で保証するものもある。

また、関数型言語は文 (statement) よりも式 (expression) を中心とした言語仕様となっていることも特徴である。前述の例において、再帰関数sum束縛するletは式である。また、条件分岐のif-then-elseも式である。文よりも式で書けることが多いほうが都合がよい。

関数型言語は関数型プログラミングをサポートする言語ではあるが、手続き型プログラミングを行なうことも可能である。例えばF#では以下のようなPascal風の書き方もできる。

let mutable total = 0
for i = 1 to 10 do
    total <- total + i
printfn "%d" total

ただしHaskellのようにループ構文をサポートせず、従来の手続き型プログラミングが難しいケースもある。

逆に手続き型言語を使って関数型プログラミングを行なうことも可能であるが、末尾再帰呼び出しの最適化がサポートされるかどうかはコンパイラ次第である。

歴史

1930年代

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

1950年代

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

概要 (old)

関数型プログラミング(パラダイム)に合意された定義がないことと同じく、広く認められた関数型言語の正確な定義は存在しない。関数型プログラミングでは関数を第一級オブジェクトとして扱う。理論的な計算モデルとして第一級オブジェクトとしての関数を扱えるラムダ計算項書き換えを採用している。

コンピュータプログラムは通例入力を受け取って何らかの処理を行ない、出力を返すことを目的として書かれる。数学の関数において、を入力、を出力と考えると、コンピュータプログラムはある種の関数であると考えることができる。ここで、入力や出力は記憶装置中のファイルのようなものばかりではなく、キーボードやポインティングデバイスによってユーザーから与えられる情報や、画面への表示といった入出力形態も考えられる。関数型プログラミングにおいては実際にそれらを扱う関数としてモデル化する。

純粋関数型言語では、参照透過性が常に保たれるという意味において、全てのや関数の評価時に副作用を生まない。純粋関数型言語であるHaskellCleanは非正格な評価を基本としており、引数はデフォルトで遅延評価される。一方、Idrisは純粋だが正格評価を採用している。入出力などを参照透過性を保ったまま実現するために、たとえば Haskell ではモナドClean では一意型英語版という特殊な型を通して一貫性のある表現を提供する。

非純粋関数型言語では、参照透過性を壊す、副作用があるような式や関数も存在する。LISPなどでデータ構造の破壊的変更などの副作用を多用したプログラミングを行うと、それはもはや手続き型プログラミングである。多くの場合、非純粋関数型言語の評価戦略は正格評価(先行評価)であるが、遅延評価する部分を明示することで、無限リストなどを扱えるものもある。

JavaScriptJavaなど近年[いつ?]高水準言語には、関数型言語の機能や特徴を取り入れているものがあるが、変数の値やオブジェクトの状態を書き換えるプログラミングスタイルを通常とするため、関数型言語とは分類されない。一方LISPは、その多くが副作用のある式や関数が多数あり、手続き型スタイルでのプログラミングがされることも多いが、理論的なモデル(「LISP」)の存在や副作用を使わないプログラミングが基本であること、ないし主には歴史的理由から、関数型言語だとされることが多い。なお、Pascalでは「手続き」と呼ばれるような値を返さないサブルーチンを、C言語では「関数」と呼んでいるが、これは単にルーチンについて、細分類して別の呼称を付けているか、細分類せず総称しているか、という分類と呼称の違いに過ぎず、「Pascalは手続き型言語で、C言語は関数型言語」[注釈 5]という一部の書籍に見られる記述は明確に誤りである。また、OCamlHaskellなどでは、「自明な値(例えば())を返す」と、値を返さない(Voidなど)は違うものであり、後者は停止しないか例外を出す(そのため結果がない)ようなプログラムを表す。

なお、「関数型言語である」と「関数型プログラミングをする」は同値ではなく、関数型には分類されない言語で関数型プログラミングをすること[注釈 6]や、関数型プログラミングを基本とする言語の上で他のパラダイムを実現する例もある[注釈 7]

データフロープログラミング言語も関数型言語と共通した特徴を部分的に持つ。

歴史 (old)

LISPは、その基本機能のモデルとして関数型の純LISPを持つなどといった特徴がある、最初の関数型言語である。今日広く使われているLISP方言のうち特にSchemeは関数型としての特徴が強い。

現代的な関数型プログラミング言語の祖としてはアイディアが1966年に発表されたISWIMが挙げられるが、1970年前後までは関数型プログラミング言語の歴史はLISPの発展が主である。1970年代にプロジェクトが開始されたロジック・フォー・コンピュータブル・ファンクションズ英語版のための言語としてMLが作られている。

またLISPにおいて、変数のスコープに静的スコープを採用したSchemeが誕生したのが1975年である。

1977年、FORTRANの設計とバッカス・ナウア記法の発明の業績でこの年のチューリング賞を受賞したジョン・バッカスは、Can Programming Be Liberated From the von Neumann Style?: A Functional Style and Its Algebra of Programs[注釈 8]と題した受賞記念講演で関数型プログラミングの重要性を訴えた。講演ではFPという関数型プログラミング言語の紹介もした(サブタイトルの後半の「プログラムの代数」はこれを指す)が、これはAPL(特に、高階関数の意味がある記号(APLの用語ではオペレーター(作用素)という))の影響を受けている。

バッカスのFPは広く使用されることはなかったが、この後関数型プログラミング言語の研究・開発は広まることとなった。1985年にMirandaが登場した。1987年に、遅延評価の純粋関数型プログラミング言語の標準の必要性が認識されHaskellの策定が始まった。1990年にHaskell 1.0仕様がリリースされた。同じく1990年にはMLの標準であるStandard MLもリリースされている。

Cleanは1987年に登場したが、発展の過程でHaskellの影響を受けている。1996年に、ML処理系のひとつであったCamlオブジェクト指向を追加したOCamlが登場した。また日本ではSMLに独自の拡張を施したSML#が開発されている。

21世紀に入ると、Java仮想マシン共通言語基盤CLI)をランタイムとする関数型プログラミング言語を実装しようという動きが現れ、ScalaClojureF#などが登場した。

代表的な関数型言語

言語 純粋さ 型付け
Clean 純粋 強い、静的
Clojure 非純粋 動的
Erlang 非純粋 動的
F# 非純粋 強い、静的
Haskell 純粋 強い、静的
Idris 純粋 強い、静的
Lazy K 純粋 型なし
LISP 非純粋 動的
Miranda 純粋 強い、静的
ML 非純粋 強い、静的
SML# 非純粋 強い、静的
Standard ML 非純粋 強い、静的
OCaml 非純粋 強い、静的
Scala 非純粋 強い、静的
Scheme 非純粋 動的
Unlambda 非純粋 型なし

従来の手続き型と分類されるプログラミング言語においても、関数型プログラミングを行ないやすくなる機能を備えているものもある。C言語およびC++関数へのポインタをサポートし、関数をオブジェクトのように扱うことができるが、関数ポインタによって第一級関数をサポートしているとみなされてはいない。なお、C# 3.0、C++11、Java 8など、後発の規格においてラムダ式(無名関数)をサポートするようになった言語もある。

その他の関数的性質を持つ言語

脚注

注釈

  1. ^ 本来は等差数列の和の公式を用いて定数時間で問題を解く方法が最適解だが、ここではプログラミングスタイルの比較のため数値計算的手法を用いる。
  2. ^ (Church 1932)
  3. ^ (Church 1941)
  4. ^ (McCarthy 1978)
  5. ^ 共立出版ANSI C/C++辞典』ISBN 4-320-02797-3 など
  6. ^ 関数型プログラミングのエッセンスとして、MISRA CのようにC言語でも副作用を極力用いないプログラミングを推奨しているコーディング標準もある。
  7. ^ Oleg Kiselyov, Ralf Lämmel. “Haskell's overlooked object system”. Sep 10, 2005閲覧。
  8. ^ 「プログラミングはフォン・ノイマン・スタイルから解放されうるか?: 関数型プログラミング・スタイルとそのプログラム代数」、米澤明憲訳『ACMチューリング賞講演集』(共立出版)pp. 83-156

出典

  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. ^ 本間, 類地 & 逢坂 2017, p. 6
  17. ^ 本間, 類地 & 逢坂 2017, p. 6
  18. ^ 本間, 類地 & 逢坂 2017, p. 6
  19. ^ 本間, 類地 & 逢坂 2017, p. 6
  20. ^ 本間, 類地 & 逢坂 2017, p. 6
  21. ^ 本間, 類地 & 逢坂 2017, p. 6
  22. ^ 本間, 類地 & 逢坂 2017, p. 6
  23. ^ 本間, 類地 & 逢坂 2017, p. 6
  24. ^ 本間, 類地 & 逢坂 2017, p. 23
  25. ^ 本間, 類地 & 逢坂 2017, p. 6
  26. ^ 本間, 類地 & 逢坂 2017, p. 31
  27. ^ 本間, 類地 & 逢坂 2017, p. 32
  28. ^ Lipovača 2012, p. 22
  29. ^ 本間, 類地 & 逢坂 2017, p. 3
  30. ^ 本間, 類地 & 逢坂 2017, p. 3
  31. ^ 本間, 類地 & 逢坂 2017, p. 5
  32. ^ 本間, 類地 & 逢坂 2017, p. 6
  33. ^ 本間, 類地 & 逢坂 2017, p. 4
  34. ^ 本間, 類地 & 逢坂 2017, p. 4
  35. ^ 本間, 類地 & 逢坂 2017, p. 2
  36. ^ 本間, 類地 & 逢坂 2017, p. 2
  37. ^ 本間, 類地 & 逢坂 2017, p. 2
  38. ^ 本間, 類地 & 逢坂 2017, p. 2
  39. ^ 本間, 類地 & 逢坂 2017, p. 4
  40. ^ 本間, 類地 & 逢坂 2017, p. 4
  41. ^ 本間, 類地 & 逢坂 2017, p. 4
  42. ^ Frequently Asked Questions for comp.lang.functional”. May 14, 2015閲覧。
  43. ^ 計算モデル1 状態モデル. 計算とは、計算機の内部状態を変えてゆくもの。(中略) 状態モデルに基づくプログラミング言語. 命令型言語. (中略) 状態を変えるための命令手順書の形式. 犬塚信博 (2007)「プログラミング言語論 第1回 イントロダクション」名古屋工業大学
  44. ^ 計算モデル2 関数モデル. (中略) 関数モデルに基づくプログラミング言語. 関数型言語. Lisp 犬塚信博 (2007)「プログラミング言語論 第1回 イントロダクション」名古屋工業大学
  45. ^ 関数 (F#) | MSDN
  46. ^ Hudak, p. 363
  47. ^ Hudak, p. 363
  48. ^ Hudak, p. 363
  49. ^ Hudak, p. 367
  50. ^ Hudak, pp. 367–368

参考文献

  • Church (1932年4月), “A Set of Postulates for the Foundation of Logic” (英語), Annals of Mathematics 33 (2): 346, doi:10.2307/1968337, ISSN 0003-486X, JSTOR 1968337, https://jstor.org/stable/1968337 , Wikidata Q55890017
  • Church (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
  • McCarthy, John (1978年), History of LISP, doi:10.1145/800025.808387 , Wikidata Q56048080
  • 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

外部リンク