「関数型プログラミング」の版間の差分
編集の要約なし |
編集の要約なし |
||
(同じ利用者による、間の9版が非表示) | |||
1行目: | 1行目: | ||
{{独自研究|date=2014年4月}} |
{{独自研究|date=2014年4月}} |
||
{{プログラミング言語|index=かんすうかたけんこ}} |
{{プログラミング言語|index=かんすうかたけんこ}} |
||
[[ファイル:Orange_lambda.svg|リンク=https://ja-two.iwiki.icu/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Orange_lambda.svg|代替文=|境界|右|フレームなし|167x167ピクセル]] |
|||
'''関数型言語'''(かんすうがたげんご、{{lang-en-short|functional language}}、関数型プログラミング言語とも)は、関数型プログラミングを基本スタイルとする[[プログラミング言語]]の総称である{{efn|{{lang-en-short|functional programming language}}}}。 |
|||
'''関数型プログラミング言語'''({{lang-en-short|''functional programming language''}})は、関数型プログラミングの[[プログラミングパラダイム|パラダイム]]を扱う[[プログラミング言語]]の総称である。'''純粋関数型'''(''purely functional'')と'''非純粋関数型'''(''impure functional'')の二つに大別され、後者の方が幅広く用いられている。[[マルチパラダイムプログラミング言語|マルチパラダイム言語]]に組み込まれているものは例外なく非純粋である。 |
|||
非純粋関数型は、関数を値として扱える[[高階関数]]、値として扱われる[[第一級関数]]、型を体系化ないし抽象化する[[型システム]]をそれぞれ連携させた計算式の構文スタイルに着目している部分が大きい。それに加えて純粋関数型は、プログラム概念上の[[副作用 (プログラム)|副作用]]をイメージ的に排除する[[参照透過性]]をプロセスの原則にしたものであり、その仕様実現の為に専用のランタイム環境上でプログラムは走行される。 |
|||
== 関数型プログラミング == |
|||
広く認められた関数型プログラミングの正確な定義は存在しないが、関数型プログラミングと呼ばれるパラダイムは[[命令型プログラミング]]と比較してプログラムに対する見方が次のように異なる<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>計算モデル1 状態モデル. 計算とは、計算機の内部状態を変えてゆくもの。(中略) 状態モデルに基づくプログラミング言語. 命令型言語. (中略) 状態を変えるための命令手順書の形式. [http://nous.web.nitech.ac.jp/individual/inuzuka/lecture/PLT/PLT07/ 犬塚信博 (2007)「プログラミング言語論 第1回 イントロダクション」名古屋工業大学]</ref> |
|||
* 関数型プログラミング: プログラムは関数とその適用の組み合わせ |
|||
=== 構文視点 === |
|||
すなわち[[命令型プログラミング]]は計算機(あるいは[[CPU]])の状態を変える命令をプログラムとして書くという見方を基礎としており、これはその発祥が計算機の命令 (instruction/command) や構造に密接にかかわっていることによる。一方、関数型プログラミングは「計算とは何か」という数学の理論を基礎にしており、関数型プログラミングがもつ[[計算モデル]]は'''関数モデル'''である<ref>計算モデル2 関数モデル. (中略) 関数モデルに基づくプログラミング言語. 関数型言語. Lisp [http://nous.web.nitech.ac.jp/individual/inuzuka/lecture/PLT/PLT07/ 犬塚信博 (2007)「プログラミング言語論 第1回 イントロダクション」名古屋工業大学]</ref>。 |
|||
関数型プログラミングの基本要素である関数(''function'')とは、与えられた入力値から任意の出力値を導き出す変換式を意味するが、[[数理論理学]]の[[型付きラムダ計算]]がモデルにされてる背景からそれに加えた性質を持つ。関数はそれ自体が型付きの値として扱われるが、その「関数の型」は各引数値一つ一つへの適用から結果値までのパターンである型の連鎖として表現される。関数を値として扱える関数の仕組みは[[高階関数]](''higher-order function'')、値そのものとして扱われる関数の仕組みは[[第一級関数]](''first-class function'')と呼ばれる。型(''type'')を体系化ないし抽象化する仕組みは[[型システム]](''type system'')と呼ばれる。引数になった関数もまた引数を持つといった連鎖は広義の[[相互再帰]]になり[[複雑系]]のプロセスを自然に表現する。それらの連携による計算式のスタイルが関数型プログラミングをユニークなものにしている。 |
|||
この[[ラムダ計算]]の論理を背景にした関数の用法を、一般的な手続き型プログラミングの視点から眺めると、手続き型では関数定義を識別する[[シグネチャ]]でしかなかった関数の「引数欄」を、関数型の方ではその順序構成に厳格に意味を持たせたプログラム要素にして「関数の型」の表現法に組み込んでいる点が大きな違いになる。高階、第一級関数に加えて、この引数欄構造の明確な有意義化が、[[カリー化]]と合わせたラムダ計算視点の式分析と、その論理に則った各種変換および各種簡約による式の再構成を可能にし、また部分適用や関数合成による式の組み換えも可能にして、式の平易化と関数アルゴリズムの最適化を実現している。 |
|||
たとえば、1 から 10 までの整数を足し合わせるプログラムを考える{{efn|本来は[[等差数列]]の和の公式を用いて定数時間で問題を解く方法が最適解だが、ここではプログラミングスタイルの比較のため数値計算的手法を用いる。}}。[[命令型プログラミング]]では以下のように[[ループ (プログラミング)|ループ]]文を使って変数に数値を足していく(計算機の状態を書き換える)命令を繰り返し実行するという形を取る。 |
|||
=== 設計視点 === |
|||
* [[Pascal]]による例: |
|||
関数型プログラミングは[[宣言型プログラミング]](''declarative programming'')のカテゴリに属するパラダイムである。宣言型と対照的関係にあるのが[[命令型プログラミング]](''imperative programming'')であり、そのカテゴリには[[手続き型プログラミング]]と[[オブジェクト指向プログラミング]]などが属している。命令型と宣言型を分ける一つの基準は[[副作用 (プログラム)|副作用]](''side-effects'')に対する考え方および扱い方である。この副作用については改めて後述するが、簡潔に述べると現行プロセスの閉包領域の外にある様々な情報資源の状態=いわゆる「環境」の変化と、その変化によって各プロセスの処理過程もまた影響を受ける事を指す。ここでの情報資源とは、プログラムの各種入出力(I/O)を担う[[オペレーティングシステム]]の現行状態と、プログラムを走行させている[[仮想マシン|ランタイム環境]]が提供する各種データリソースを意味する。データリソースには純粋関数型では扱いにくい動的配列と動的連想配列も含まれる。 |
|||
<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> |
|||
命令型プログラミングは前述の「環境」に対して自由に作用を及ぼせるパラダイムであり、それが”''imperative''”の由来にもなっている。それに対して宣言型プログラミングは作用を及ぼせる対象と、自身がその影響を受ける事になる対象が、あらかじめ初期値または入力値として”''declarative''”された情報資源(=データ)のみに限られている。加えて関数型プログラミングは原則的に、宣言されたデータに対しても作用を及ぼさず、他の値を導き出す為の因子として扱う。 |
|||
一方、関数型プログラミングでは、繰り返しには一時変数およびループを使わず、[[サブルーチン|関数]]の[[再帰呼び出し]]を使う。 |
|||
== 特徴 == |
|||
* [[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> |
|||
--> |
|||
=== 参照透過性(''referential transparency'') === |
|||
ただし再帰呼び出しは[[スタックオーバーフロー]]の危険性やオーバーヘッドを伴うため、注意深く使用しなければならない<ref>[https://msdn.microsoft.com/ja-jp/library/dd233229(v=vs.120).aspx 関数 (F#) | MSDN]</ref>。通例、関数型言語では、[[末尾再帰]]呼び出し (tail-recursive call) の形で書かれた関数をループに展開する[[コンパイラ最適化]]により、スタックオーバーフローの危険性および再帰のオーバーヘッドを解消する。[[Scheme]]など、関数型言語の中には末尾再帰呼び出しの最適化を仕様で保証するものもある。 |
|||
=== データ機構(''data structure'') === |
|||
また、関数型言語は文 (statement) よりも式 (expression) を中心とした言語仕様となっていることも特徴である。前述の例において、再帰関数<code>sum</code>を[[束縛 (情報工学)|束縛]]する<code>let</code>は式である。また、条件分岐の<code>if-then-else</code>も式である。文よりも式で書けることが多いほうが都合がよい。 |
|||
=== 再帰(''recursion'') === |
|||
関数型言語は関数型プログラミングをサポートする言語ではあるが、手続き型プログラミングを行なうことも可能である。例えばF#では以下のようなPascal風の書き方もできる。 |
|||
=== 評価戦略(''evaluation strategy'') === |
|||
<source lang="fsharp"> |
|||
let mutable total = 0 |
|||
for i = 1 to 10 do |
|||
total <- total + i |
|||
printfn "%d" total |
|||
</source> |
|||
=== 型の体系(''type system'') === |
|||
ただし[[Haskell]]のようにループ構文をサポートせず、従来の手続き型プログラミングが難しいケースもある。 |
|||
=== 高階関数と第一級関数(''higher-order and first-class function'') === |
|||
逆に手続き型言語を使って関数型プログラミングを行なうことも可能であるが、末尾再帰呼び出しの最適化がサポートされるかどうかはコンパイラ次第である。 |
|||
=== 純粋関数(''pure function'') === |
|||
== 概要 == |
|||
<!--関数型プログラミングではプログラムの構成にC言語のように関数を多用する<ref>The C language is purely functional http://conal.net/blog/posts/the-c-language-is-purely-functional</ref>。[[Wikipedia:検証可能性#通常は信頼できないとされる情報源]]-->関数型プログラミング(パラダイム)に合意された定義がないことと同じく、広く認められた関数型言語の正確な定義は存在しない。関数型プログラミングでは関数を[[第一級オブジェクト]]として扱う。理論的な計算モデルとして第一級オブジェクトとしての関数を扱える[[ラムダ計算]]や[[項書き換え]]を採用している。 |
|||
コンピュータプログラムは通例入力を受け取って何らかの処理を行ない、出力を返すことを目的として書かれる。数学の関数<math>y = f(x)</math>において、<math>x</math>を入力、<math>y</math>を出力と考えると、コンピュータプログラムはある種の関数であると考えることができる。ここで、入力や出力は記憶装置中のファイルのようなものばかりではなく、キーボードや[[ポインティングデバイス]]によってユーザーから与えられる情報や、画面への表示といった入出力形態も考えられる。関数型プログラミングにおいては実際にそれらを扱う関数としてモデル化する。 |
|||
純粋関数型言語では、[[参照透過性]]が常に保たれるという意味において、全ての[[式 (プログラミング)|式]]や関数の評価時に[[副作用 (プログラム)|副作用]]を生まない。純粋関数型言語である{{lang|en|[[Haskell]]}}や{{lang|en|[[Clean]]}}は非[[正格]]な評価を基本としており、引数はデフォルトで[[遅延評価]]される。一方、{{lang|en|[[Idris]]}}は純粋だが正格評価を採用している。入出力などを[[参照透過性]]を保ったまま実現するために、たとえば {{lang|en|Haskell}} では[[モナド (プログラミング)|モナド]]、{{lang|en|Clean}} では{{仮リンク|一意型|en|Uniqueness type}}という特殊な型を通して一貫性のある表現を提供する。 |
|||
非純粋関数型言語では、参照透過性を壊す、副作用があるような式や関数も存在する。{{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>など)は違うものであり、後者は停止しないか例外を出す(そのため結果がない)ようなプログラムを表す。 |
|||
なお、「関数型言語である」と「関数型プログラミングをする」は同値ではなく、関数型には分類されない言語で関数型プログラミングをすること{{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:検証可能性#通常は信頼できないとされる情報源]]--> |
|||
[[データフロープログラミング]]言語も関数型言語と共通した特徴を部分的に持つ。 |
|||
== 歴史 == |
== 歴史 == |
||
90行目: | 51行目: | ||
== 代表的な関数型言語 == |
== 代表的な関数型言語 == |
||
{|class="wikitable sortable" |
{| class="wikitable sortable" |
||
!言語 |
!言語 |
||
!純粋さ |
!純粋さ |
||
127行目: | 88行目: | ||
|{{lang|en|[[Unlambda]]}}||非純粋||型なし |
|{{lang|en|[[Unlambda]]}}||非純粋||型なし |
||
|} |
|} |
||
純粋関数型言語では、[[参照透過性]]が常に保たれるという意味において、全ての[[式 (プログラミング)|式]]や関数の評価時に[[副作用 (プログラム)|副作用]]を生まない。純粋関数型言語である{{lang|en|[[Haskell]]}}や{{lang|en|[[Clean]]}}は非[[正格]]な評価を基本としており、引数はデフォルトで[[遅延評価]]される。一方、{{lang|en|[[Idris]]}}は純粋だが正格評価を採用している。入出力などを[[参照透過性]]を保ったまま実現するために、たとえば {{lang|en|Haskell}} では[[モナド (プログラミング)|モナド]]、{{lang|en|Clean}} では{{仮リンク|一意型|en|Uniqueness type}}という特殊な型を通して一貫性のある表現を提供する。 |
|||
非純粋関数型言語では、参照透過性を壊す、副作用があるような式や関数も存在する。{{lang|en|LISP}}などでデータ構造の破壊的変更などの副作用を多用したプログラミングを行うと、それはもはや手続き型プログラミングである。多くの場合、非純粋関数型言語の[[評価戦略]]は正格評価(先行評価)であるが、遅延評価する部分を明示することで、無限リストなどを扱えるものもある。 |
|||
従来の手続き型と分類されるプログラミング言語においても、関数型プログラミングを行ないやすくなる機能を備えているものもある。[[C言語]]および[[C++]]は[[関数へのポインタ]]をサポートし、関数をオブジェクトのように扱うことができるが、関数ポインタによって[[第一級関数]]をサポートしているとみなされてはいない。なお、C# 3.0、[[C++11]]、Java 8など、後発の規格においてラムダ式([[無名関数]])をサポートするようになった言語もある。 |
従来の手続き型と分類されるプログラミング言語においても、関数型プログラミングを行ないやすくなる機能を備えているものもある。[[C言語]]および[[C++]]は[[関数へのポインタ]]をサポートし、関数をオブジェクトのように扱うことができるが、関数ポインタによって[[第一級関数]]をサポートしているとみなされてはいない。なお、C# 3.0、[[C++11]]、Java 8など、後発の規格においてラムダ式([[無名関数]])をサポートするようになった言語もある。 |
||
{{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|[[APL]]}} |
|||
なお、「関数型言語である」と「関数型プログラミングをする」は同値ではなく、関数型には分類されない言語で関数型プログラミングをすること{{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:検証可能性#通常は信頼できないとされる情報源]]--> |
|||
* {{lang|en|[[XSL Transformations|XSLT]]}} |
|||
'''その他の関数的性質を持つ言語''' |
|||
*{{lang|en|[[APL]]}} |
|||
*{{lang|en|[[XSL Transformations|XSLT]]}} |
|||
== 関数型プログラミングの例 == |
|||
関数型プログラミングは「計算とは何か」という数学の理論を基礎にしており、関数型プログラミングがもつ[[計算モデル]]は'''関数モデル'''である<ref>計算モデル2 関数モデル. (中略) 関数モデルに基づくプログラミング言語. 関数型言語. Lisp [http://nous.web.nitech.ac.jp/individual/inuzuka/lecture/PLT/PLT07/ 犬塚信博 (2007)「プログラミング言語論 第1回 イントロダクション」名古屋工業大学]</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> |
|||
--> |
|||
ただし再帰呼び出しは[[スタックオーバーフロー]]の危険性やオーバーヘッドを伴うため、注意深く使用しなければならない<ref>[https://msdn.microsoft.com/ja-jp/library/dd233229(v=vs.120).aspx 関数 (F#) | MSDN]</ref>。通例、関数型言語では、[[末尾再帰]]呼び出し (tail-recursive call) の形で書かれた関数をループに展開する[[コンパイラ最適化]]により、スタックオーバーフローの危険性および再帰のオーバーヘッドを解消する。[[Scheme]]など、関数型言語の中には末尾再帰呼び出しの最適化を仕様で保証するものもある。 |
|||
また、関数型言語は文 (statement) よりも式 (expression) を中心とした言語仕様となっていることも特徴である。前述の例において、再帰関数<code>sum</code>を[[束縛 (情報工学)|束縛]]する<code>let</code>は式である。また、条件分岐の<code>if-then-else</code>も式である。文よりも式で書けることが多いほうが都合がよい。 |
|||
関数型言語は関数型プログラミングをサポートする言語ではあるが、手続き型プログラミングを行なうことも可能である。例えばF#では以下のようなPascal風の書き方もできる。 |
|||
<source lang="fsharp"> |
|||
let mutable total = 0 |
|||
for i = 1 to 10 do |
|||
total <- total + i |
|||
printfn "%d" total |
|||
</source> |
|||
ただし[[Haskell]]のようにループ構文をサポートせず、従来の手続き型プログラミングが難しいケースもある。 |
|||
逆に手続き型言語を使って関数型プログラミングを行なうことも可能であるが、末尾再帰呼び出しの最適化がサポートされるかどうかはコンパイラ次第である。 |
|||
== 脚注 == |
== 脚注 == |
2020年2月26日 (水) 13:02時点における版
![]() | この記事には独自研究が含まれているおそれがあります。 |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8f/Orange_lambda.svg/160px-Orange_lambda.svg.png)
関数型プログラミング言語(英: functional programming language)は、関数型プログラミングのパラダイムを扱うプログラミング言語の総称である。純粋関数型(purely functional)と非純粋関数型(impure functional)の二つに大別され、後者の方が幅広く用いられている。マルチパラダイム言語に組み込まれているものは例外なく非純粋である。
非純粋関数型は、関数を値として扱える高階関数、値として扱われる第一級関数、型を体系化ないし抽象化する型システムをそれぞれ連携させた計算式の構文スタイルに着目している部分が大きい。それに加えて純粋関数型は、プログラム概念上の副作用をイメージ的に排除する参照透過性をプロセスの原則にしたものであり、その仕様実現の為に専用のランタイム環境上でプログラムは走行される。
概要
構文視点
関数型プログラミングの基本要素である関数(function)とは、与えられた入力値から任意の出力値を導き出す変換式を意味するが、数理論理学の型付きラムダ計算がモデルにされてる背景からそれに加えた性質を持つ。関数はそれ自体が型付きの値として扱われるが、その「関数の型」は各引数値一つ一つへの適用から結果値までのパターンである型の連鎖として表現される。関数を値として扱える関数の仕組みは高階関数(higher-order function)、値そのものとして扱われる関数の仕組みは第一級関数(first-class function)と呼ばれる。型(type)を体系化ないし抽象化する仕組みは型システム(type system)と呼ばれる。引数になった関数もまた引数を持つといった連鎖は広義の相互再帰になり複雑系のプロセスを自然に表現する。それらの連携による計算式のスタイルが関数型プログラミングをユニークなものにしている。
このラムダ計算の論理を背景にした関数の用法を、一般的な手続き型プログラミングの視点から眺めると、手続き型では関数定義を識別するシグネチャでしかなかった関数の「引数欄」を、関数型の方ではその順序構成に厳格に意味を持たせたプログラム要素にして「関数の型」の表現法に組み込んでいる点が大きな違いになる。高階、第一級関数に加えて、この引数欄構造の明確な有意義化が、カリー化と合わせたラムダ計算視点の式分析と、その論理に則った各種変換および各種簡約による式の再構成を可能にし、また部分適用や関数合成による式の組み換えも可能にして、式の平易化と関数アルゴリズムの最適化を実現している。
設計視点
関数型プログラミングは宣言型プログラミング(declarative programming)のカテゴリに属するパラダイムである。宣言型と対照的関係にあるのが命令型プログラミング(imperative programming)であり、そのカテゴリには手続き型プログラミングとオブジェクト指向プログラミングなどが属している。命令型と宣言型を分ける一つの基準は副作用(side-effects)に対する考え方および扱い方である。この副作用については改めて後述するが、簡潔に述べると現行プロセスの閉包領域の外にある様々な情報資源の状態=いわゆる「環境」の変化と、その変化によって各プロセスの処理過程もまた影響を受ける事を指す。ここでの情報資源とは、プログラムの各種入出力(I/O)を担うオペレーティングシステムの現行状態と、プログラムを走行させているランタイム環境が提供する各種データリソースを意味する。データリソースには純粋関数型では扱いにくい動的配列と動的連想配列も含まれる。
命令型プログラミングは前述の「環境」に対して自由に作用を及ぼせるパラダイムであり、それが”imperative”の由来にもなっている。それに対して宣言型プログラミングは作用を及ぼせる対象と、自身がその影響を受ける事になる対象が、あらかじめ初期値または入力値として”declarative”された情報資源(=データ)のみに限られている。加えて関数型プログラミングは原則的に、宣言されたデータに対しても作用を及ぼさず、他の値を導き出す為の因子として扱う。
特徴
関数型プログラミングを構成する考え方には以下のものがある。
参照透過性(referential transparency)
データ機構(data structure)
再帰(recursion)
評価戦略(evaluation strategy)
型の体系(type system)
高階関数と第一級関数(higher-order and first-class function)
純粋関数(pure function)
歴史
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[1]と題した受賞記念講演で関数型プログラミングの重要性を訴えた。講演では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)をランタイムとする関数型プログラミング言語を実装しようという動きが現れ、Scala・Clojure・F#などが登場した。
代表的な関数型言語
言語 | 純粋さ | 型付け |
---|---|---|
Clean | 純粋 | 強い、静的 |
Clojure | 非純粋 | 動的 |
Erlang | 非純粋 | 動的 |
F# | 非純粋 | 強い、静的 |
Haskell | 純粋 | 強い、静的 |
Idris | 純粋 | 強い、静的 |
Lazy K | 純粋 | 型なし |
LISP | 非純粋 | 動的 |
Miranda | 純粋 | 強い、静的 |
ML | 非純粋 | 強い、静的 |
SML# | 非純粋 | 強い、静的 |
Standard ML | 非純粋 | 強い、静的 |
OCaml | 非純粋 | 強い、静的 |
Scala | 非純粋 | 強い、静的 |
Scheme | 非純粋 | 動的 |
Unlambda | 非純粋 | 型なし |
純粋関数型言語では、参照透過性が常に保たれるという意味において、全ての式や関数の評価時に副作用を生まない。純粋関数型言語であるHaskellやCleanは非正格な評価を基本としており、引数はデフォルトで遅延評価される。一方、Idrisは純粋だが正格評価を採用している。入出力などを参照透過性を保ったまま実現するために、たとえば Haskell ではモナド、Clean では一意型という特殊な型を通して一貫性のある表現を提供する。
非純粋関数型言語では、参照透過性を壊す、副作用があるような式や関数も存在する。LISPなどでデータ構造の破壊的変更などの副作用を多用したプログラミングを行うと、それはもはや手続き型プログラミングである。多くの場合、非純粋関数型言語の評価戦略は正格評価(先行評価)であるが、遅延評価する部分を明示することで、無限リストなどを扱えるものもある。
従来の手続き型と分類されるプログラミング言語においても、関数型プログラミングを行ないやすくなる機能を備えているものもある。C言語およびC++は関数へのポインタをサポートし、関数をオブジェクトのように扱うことができるが、関数ポインタによって第一級関数をサポートしているとみなされてはいない。なお、C# 3.0、C++11、Java 8など、後発の規格においてラムダ式(無名関数)をサポートするようになった言語もある。
JavaScriptやJavaなど近年[いつ?]の高水準言語には、関数型言語の機能や特徴を取り入れているものがあるが、変数の値やオブジェクトの状態を書き換えるプログラミングスタイルを通常とするため、関数型言語とは分類されない。一方LISPは、その多くが副作用のある式や関数が多数あり、手続き型スタイルでのプログラミングがされることも多いが、理論的なモデル(「純LISP」)の存在や副作用を使わないプログラミングが基本であること、ないし主には歴史的理由から、関数型言語だとされることが多い。なお、Pascalでは「手続き」と呼ばれるような値を返さないサブルーチンを、C言語では「関数」と呼んでいるが、これは単にルーチンについて、細分類して別の呼称を付けているか、細分類せず総称しているか、という分類と呼称の違いに過ぎず、「Pascalは手続き型言語で、C言語は関数型言語」[2]という一部の書籍に見られる記述は明確に誤りである。また、OCamlやHaskellなどでは、「自明な値(例えば()
)を返す」と、値を返さない(Void
など)は違うものであり、後者は停止しないか例外を出す(そのため結果がない)ようなプログラムを表す。
なお、「関数型言語である」と「関数型プログラミングをする」は同値ではなく、関数型には分類されない言語で関数型プログラミングをすること[注釈 1]や、関数型プログラミングを基本とする言語の上で他のパラダイムを実現する例もある[3]。データフロープログラミング言語も関数型言語と共通した特徴を部分的に持つ。
その他の関数的性質を持つ言語
関数型プログラミングの例
関数型プログラミングは「計算とは何か」という数学の理論を基礎にしており、関数型プログラミングがもつ計算モデルは関数モデルである[4]。たとえば、1 から 10 までの整数を足し合わせるプログラムを考える[注釈 2]。命令型プログラミングでは以下のようにループ文を使って変数に数値を足していく(計算機の状態を書き換える)命令を繰り返し実行するという形を取る。
- Pascalによる例:
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)
ただし再帰呼び出しはスタックオーバーフローの危険性やオーバーヘッドを伴うため、注意深く使用しなければならない[5]。通例、関数型言語では、末尾再帰呼び出し (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のようにループ構文をサポートせず、従来の手続き型プログラミングが難しいケースもある。
逆に手続き型言語を使って関数型プログラミングを行なうことも可能であるが、末尾再帰呼び出しの最適化がサポートされるかどうかはコンパイラ次第である。
脚注
注釈
出典
- ^ 「プログラミングはフォン・ノイマン・スタイルから解放されうるか?: 関数型プログラミング・スタイルとそのプログラム代数」、米澤明憲訳『ACMチューリング賞講演集』(共立出版)pp. 83-156
- ^ 共立出版『ANSI C/C++辞典』ISBN 4-320-02797-3 など
- ^ Oleg Kiselyov, Ralf Lämmel. “Haskell's overlooked object system”. Sep 10, 2005閲覧。
- ^ 計算モデル2 関数モデル. (中略) 関数モデルに基づくプログラミング言語. 関数型言語. Lisp 犬塚信博 (2007)「プログラミング言語論 第1回 イントロダクション」名古屋工業大学
- ^ 関数 (F#) | MSDN
外部リンク