「関数型プログラミング」の版間の差分
編集の要約なし |
編集の要約なし |
||
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 programming language''}})は、関数型プログラミングの[[プログラミングパラダイム|パラダイム]]を扱う[[プログラミング言語]]の総称である。本稿ではそのパラダイムについても説明する。'''純粋関数型'''(''purely functional'')と'''非純粋関数型'''(''impure functional'')の二つに大別され、後者の方が幅広く用いられている。[[マルチパラダイムプログラミング言語|マルチパラダイム言語]]に組み込まれているものは例外なく非純粋であり、関数型パラダイムの一部分をかいつまんだものと考えてよい。 |
'''関数型プログラミング言語'''({{lang-en-short|''functional programming language''}})は、関数型プログラミングの[[プログラミングパラダイム|パラダイム]]を扱う[[プログラミング言語]]の総称である。本稿ではそのパラダイムについても説明する。'''純粋関数型'''(''purely functional'')と'''非純粋関数型'''(''impure functional'')の二つに大別され、後者の方が幅広く用いられている。[[マルチパラダイムプログラミング言語|マルチパラダイム言語]]に組み込まれているものは例外なく非純粋であり、関数型パラダイムの一部分をかいつまんだものと考えてよい。 |
||
'''関数'''とは与えられた入力値から任意の出力値を導き出す変換式を意味する。関数はそれ自体が値として扱われるので前述の入力値または出力値にする事もできる。関数を値として扱える関数の仕組みは[[高階関数]](''higher-order function'')、値そのものとして扱われる関数の仕組みは[[第一級関数]](''first-class function'')と呼ばれる。非純粋関数型はほとんどこの高階関数と第一級関数の構文仕様に着目したものである。純粋関数型は |
'''関数'''とは与えられた入力値から任意の出力値を導き出す変換式を意味する。関数はそれ自体が値として扱われるので前述の入力値または出力値にする事もできる。関数を値として扱える関数の仕組みは[[高階関数]](''higher-order function'')、値そのものとして扱われる関数の仕組みは[[第一級関数]](''first-class function'')と呼ばれる。非純粋関数型はほとんどこの高階関数と第一級関数の構文仕様に着目したものである。純粋関数型は[[副作用 (プログラム)|副作用]](''side-effect'')をイメージ的に排除する[[参照透過性]](''referential transparency'')を中心にしたものであり、その仕様実現の為に専用のランタイム環境上でプログラムは走行される。 |
||
== 特徴 == |
|||
⚫ | |||
関数型プログラミングは[[宣言型プログラミング]](''declarative programming'')のカテゴリに属するパラダイムである。宣言型と対照的関係にあるのが[[命令型プログラミング]](''imperative programming'')であり、そのカテゴリには[[手続き型プログラミング]]と[[オブジェクト指向プログラミング]]などが属している。命令型と宣言型を分ける一つの基準は[[副作用 (プログラム)|副作用]](''side-effects'')に対する扱い方である。この「副作用」については独立項目にて後述するが、簡単に言うと現行プロセスの閉包領域の外にある、あらゆる情報資源の状態=いわゆる「環境」を指す。ここでの情報資源とは、プログラムの各種入出力(I/O)を担う[[オペレーティングシステム]]の現行状態と、プログラムを走行させている[[仮想マシン|ランタイム環境]]が提供する各種データリソースを意味する。データリソースには純粋関数型では扱いにくい動的配列と動的連想配列も含まれている。 |
|||
広く認められた関数型プログラミングの正確な定義は存在しないが、関数型プログラミングと呼ばれるパラダイムは[[命令型プログラミング]]と比較してプログラムに対する見方が次のように異なる<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>。 |
|||
命令型プログラミングは「[[副作用 (プログラム)|副作用]]」に対して自由に作用を及ぼせるパラダイムであり、それが”''imperative''”の由来にもなっているが、宣言型プログラミングは作用を及ぼせる対象が、あらかじめ初期値または入力値として”''declarative''”された情報資源(=データ)のみに限られている。加えて関数型プログラミングは原則的に宣言されたデータに対しても作用を及ぼさず、他の値を導き出す為の因子として扱う。 |
|||
*[[命令型プログラミング]]: プログラムは計算機の内部状態を変更する命令実行の列<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>。 |
|||
=== 参照透過性(''referential transparency'') === |
|||
⚫ | |||
=== 副作用(''side-effects'') === |
|||
=== データ機構(''data structures'') === |
|||
=== 再帰(''recursion'') === |
|||
=== 評価戦略(''evaluation strategy'') === |
|||
=== 純粋関数(''pure functions'') === |
|||
=== 型の体系(''type systems'') === |
|||
=== 高階関数と第一級関数(''first-class and higher-order functions'') === |
|||
=== その他 === |
|||
⚫ | |||
⚫ | 関数型プログラミングは「計算とは何か」という数学の理論を基礎にしており、関数型プログラミングがもつ[[計算モデル]]は'''関数モデル'''である<ref>計算モデル2 関数モデル. (中略) 関数モデルに基づくプログラミング言語. 関数型言語. Lisp [http://nous.web.nitech.ac.jp/individual/inuzuka/lecture/PLT/PLT07/ 犬塚信博 (2007)「プログラミング言語論 第1回 イントロダクション」名古屋工業大学]</ref>。たとえば、1 から 10 までの整数を足し合わせるプログラムを考える{{efn|本来は[[等差数列]]の和の公式を用いて定数時間で問題を解く方法が最適解だが、ここではプログラミングスタイルの比較のため数値計算的手法を用いる。}}。[[命令型プログラミング]]では以下のように[[ループ (プログラミング)|ループ]]文を使って変数に数値を足していく(計算機の状態を書き換える)命令を繰り返し実行するという形を取る。 |
||
* [[Pascal]]による例: |
* [[Pascal]]による例: |
2020年2月17日 (月) 04:50時点における版
![]() | この記事には独自研究が含まれているおそれがあります。 |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8f/Orange_lambda.svg/160px-Orange_lambda.svg.png)
関数型プログラミング言語(英: functional programming language)は、関数型プログラミングのパラダイムを扱うプログラミング言語の総称である。本稿ではそのパラダイムについても説明する。純粋関数型(purely functional)と非純粋関数型(impure functional)の二つに大別され、後者の方が幅広く用いられている。マルチパラダイム言語に組み込まれているものは例外なく非純粋であり、関数型パラダイムの一部分をかいつまんだものと考えてよい。
関数とは与えられた入力値から任意の出力値を導き出す変換式を意味する。関数はそれ自体が値として扱われるので前述の入力値または出力値にする事もできる。関数を値として扱える関数の仕組みは高階関数(higher-order function)、値そのものとして扱われる関数の仕組みは第一級関数(first-class function)と呼ばれる。非純粋関数型はほとんどこの高階関数と第一級関数の構文仕様に着目したものである。純粋関数型は副作用(side-effect)をイメージ的に排除する参照透過性(referential transparency)を中心にしたものであり、その仕様実現の為に専用のランタイム環境上でプログラムは走行される。
特徴
関数型プログラミングは宣言型プログラミング(declarative programming)のカテゴリに属するパラダイムである。宣言型と対照的関係にあるのが命令型プログラミング(imperative programming)であり、そのカテゴリには手続き型プログラミングとオブジェクト指向プログラミングなどが属している。命令型と宣言型を分ける一つの基準は副作用(side-effects)に対する扱い方である。この「副作用」については独立項目にて後述するが、簡単に言うと現行プロセスの閉包領域の外にある、あらゆる情報資源の状態=いわゆる「環境」を指す。ここでの情報資源とは、プログラムの各種入出力(I/O)を担うオペレーティングシステムの現行状態と、プログラムを走行させているランタイム環境が提供する各種データリソースを意味する。データリソースには純粋関数型では扱いにくい動的配列と動的連想配列も含まれている。
命令型プログラミングは「副作用」に対して自由に作用を及ぼせるパラダイムであり、それが”imperative”の由来にもなっているが、宣言型プログラミングは作用を及ぼせる対象が、あらかじめ初期値または入力値として”declarative”された情報資源(=データ)のみに限られている。加えて関数型プログラミングは原則的に宣言されたデータに対しても作用を及ぼさず、他の値を導き出す為の因子として扱う。
関数型プログラミングを構成する考え方には以下のものがある。
参照透過性(referential transparency)
副作用(side-effects)
データ機構(data structures)
再帰(recursion)
評価戦略(evaluation strategy)
純粋関数(pure functions)
型の体系(type systems)
高階関数と第一級関数(first-class and higher-order functions)
その他
関数型プログラミングの例
関数型プログラミングは「計算とは何か」という数学の理論を基礎にしており、関数型プログラミングがもつ計算モデルは関数モデルである[1]。たとえば、1 から 10 までの整数を足し合わせるプログラムを考える[注釈 1]。命令型プログラミングでは以下のようにループ文を使って変数に数値を足していく(計算機の状態を書き換える)命令を繰り返し実行するという形を取る。
- 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)
ただし再帰呼び出しはスタックオーバーフローの危険性やオーバーヘッドを伴うため、注意深く使用しなければならない[2]。通例、関数型言語では、末尾再帰呼び出し (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のようにループ構文をサポートせず、従来の手続き型プログラミングが難しいケースもある。
逆に手続き型言語を使って関数型プログラミングを行なうことも可能であるが、末尾再帰呼び出しの最適化がサポートされるかどうかはコンパイラ次第である。
概要
関数型プログラミング(パラダイム)に合意された定義がないことと同じく、広く認められた関数型言語の正確な定義は存在しない。関数型プログラミングでは関数を第一級オブジェクトとして扱う。理論的な計算モデルとして第一級オブジェクトとしての関数を扱えるラムダ計算や項書き換えを採用している。
コンピュータプログラムは通例入力を受け取って何らかの処理を行ない、出力を返すことを目的として書かれる。数学の関数において、を入力、を出力と考えると、コンピュータプログラムはある種の関数であると考えることができる。ここで、入力や出力は記憶装置中のファイルのようなものばかりではなく、キーボードやポインティングデバイスによってユーザーから与えられる情報や、画面への表示といった入出力形態も考えられる。関数型プログラミングにおいては実際にそれらを扱う関数としてモデル化する。
純粋関数型言語では、参照透過性が常に保たれるという意味において、全ての式や関数の評価時に副作用を生まない。純粋関数型言語であるHaskellやCleanは非正格な評価を基本としており、引数はデフォルトで遅延評価される。一方、Idrisは純粋だが正格評価を採用している。入出力などを参照透過性を保ったまま実現するために、たとえば Haskell ではモナド、Clean では一意型という特殊な型を通して一貫性のある表現を提供する。
非純粋関数型言語では、参照透過性を壊す、副作用があるような式や関数も存在する。LISPなどでデータ構造の破壊的変更などの副作用を多用したプログラミングを行うと、それはもはや手続き型プログラミングである。多くの場合、非純粋関数型言語の評価戦略は正格評価(先行評価)であるが、遅延評価する部分を明示することで、無限リストなどを扱えるものもある。
JavaScriptやJavaなど近年[いつ?]の高水準言語には、関数型言語の機能や特徴を取り入れているものがあるが、変数の値やオブジェクトの状態を書き換えるプログラミングスタイルを通常とするため、関数型言語とは分類されない。一方LISPは、その多くが副作用のある式や関数が多数あり、手続き型スタイルでのプログラミングがされることも多いが、理論的なモデル(「純LISP」)の存在や副作用を使わないプログラミングが基本であること、ないし主には歴史的理由から、関数型言語だとされることが多い。なお、Pascalでは「手続き」と呼ばれるような値を返さないサブルーチンを、C言語では「関数」と呼んでいるが、これは単にルーチンについて、細分類して別の呼称を付けているか、細分類せず総称しているか、という分類と呼称の違いに過ぎず、「Pascalは手続き型言語で、C言語は関数型言語」[3]という一部の書籍に見られる記述は明確に誤りである。また、OCamlやHaskellなどでは、「自明な値(例えば()
)を返す」と、値を返さない(Void
など)は違うものであり、後者は停止しないか例外を出す(そのため結果がない)ようなプログラムを表す。
なお、「関数型言語である」と「関数型プログラミングをする」は同値ではなく、関数型には分類されない言語で関数型プログラミングをすること[注釈 2]や、関数型プログラミングを基本とする言語の上で他のパラダイムを実現する例もある[4]。
データフロープログラミング言語も関数型言語と共通した特徴を部分的に持つ。
歴史
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[5]と題した受賞記念講演で関数型プログラミングの重要性を訴えた。講演では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 | 非純粋 | 型なし |
従来の手続き型と分類されるプログラミング言語においても、関数型プログラミングを行ないやすくなる機能を備えているものもある。C言語およびC++は関数へのポインタをサポートし、関数をオブジェクトのように扱うことができるが、関数ポインタによって第一級関数をサポートしているとみなされてはいない。なお、C# 3.0、C++11、Java 8など、後発の規格においてラムダ式(無名関数)をサポートするようになった言語もある。
その他の関数的性質を持つ言語
脚注
注釈
出典
- ^ 計算モデル2 関数モデル. (中略) 関数モデルに基づくプログラミング言語. 関数型言語. Lisp 犬塚信博 (2007)「プログラミング言語論 第1回 イントロダクション」名古屋工業大学
- ^ 関数 (F#) | MSDN
- ^ 共立出版『ANSI C/C++辞典』ISBN 4-320-02797-3 など
- ^ Oleg Kiselyov, Ralf Lämmel. “Haskell's overlooked object system”. Sep 10, 2005閲覧。
- ^ 「プログラミングはフォン・ノイマン・スタイルから解放されうるか?: 関数型プログラミング・スタイルとそのプログラム代数」、米澤明憲訳『ACMチューリング賞講演集』(共立出版)pp. 83-156
外部リンク