「関数型プログラミング」の版間の差分
編集の要約なし |
Goldensundown2 (会話 | 投稿記録) 編集の要約なし |
||
4行目: | 4行目: | ||
'''関数型プログラミング'''(かんすうがたプログラミング、{{lang-en-short|''functional programming''}})は、[[プログラミングパラダイム]]の一つであり、[[ソフトウェア工学]]における主にプログラムリスト作成とコード記述の分野で用いられる考え方である。一説には[[数理論理学]]の[[ラムダ計算]]をモデルにして考案されたと言われる。 |
'''関数型プログラミング'''(かんすうがたプログラミング、{{lang-en-short|''functional programming''}})は、[[プログラミングパラダイム]]の一つであり、[[ソフトウェア工学]]における主にプログラムリスト作成とコード記述の分野で用いられる考え方である。一説には[[数理論理学]]の[[ラムダ計算]]をモデルにして考案されたと言われる。 |
||
プログラムの基本要素である値(''value'')を限りなく抽象化して、入力と出力の同時表現体にすると共にその変換式も併せ持たせたものが、ターム的に'''関数'''(''function'')と定義されている。関数は同時にパラメータ値とリターン値にも出来るので変換式の連鎖が可能 |
プログラムの基本要素である値(''value'')を限りなく抽象化して、入力と出力の同時表現体にすると共にその変換式も併せ持たせたものが、ターム的に'''関数'''(''function'')と定義されている。関数は同時にパラメータ値とリターン値にも出来るので変換式の連鎖が可能である。 |
||
プログラムは値の宣言(''declaration'')とそれらを演算子で繋いだ式(''expression'')の連続で構成され、これが順次処理となる。値は数値、構造体、関数、関数連鎖として随時抽象化される。分岐処理は条件式とthen式とelse式を合わせた式の一形態で行なわれる事が多い。反復処理は関数の[[再帰]](''recursion'')として行なわれ、その関数内の評価(''eval'')が変わらなくなるまで繰り返される。関数型プログラミングの流れはこの様なものである。 |
|||
== 特徴 == |
== 特徴 == |
||
12行目: | 10行目: | ||
=== 第一級関数と高階関数 === |
=== 第一級関数と高階関数 === |
||
⚫ | |||
=== 純粋関数 === |
=== 純粋関数 === |
||
=== 厳格評価と遅延評価 === |
|||
⚫ | |||
=== 再帰 === |
=== 再帰 === |
||
たとえば、1 から 10 までの整数を足し合わせるプログラムを考える<ref>本来は[[等差数列]]の和の公式を用いて定数時間で問題を解く方法が最適解だが、ここではプログラミングスタイルの比較のため数値計算的手法を用いる。</ref>とき、手続き型プログラミングでは以下のように[[ループ (プログラミング)|ループ]]文を使って一時変数に数値を足していく(一時変数の内容を書き換える)命令を繰り返し実行するという形を取る。 |
たとえば、1 から 10 までの整数を足し合わせるプログラムを考える<ref>本来は[[等差数列]]の和の公式を用いて定数時間で問題を解く方法が最適解だが、ここではプログラミングスタイルの比較のため数値計算的手法を用いる。</ref>とき、手続き型プログラミングでは以下のように[[ループ (プログラミング)|ループ]]文を使って一時変数に数値を足していく(一時変数の内容を書き換える)命令を繰り返し実行するという形を取る。 |
||
* |
*[[Pascal]]による例: |
||
<source lang="pascal"> |
<source lang="pascal"> |
||
program test; |
program test; |
||
32行目: | 36行目: | ||
一方、関数型プログラミングでは、繰り返しには一時変数およびループを使わず、[[サブルーチン|関数]]の[[再帰呼び出し]]を使う。 |
一方、関数型プログラミングでは、繰り返しには一時変数およびループを使わず、[[サブルーチン|関数]]の[[再帰呼び出し]]を使う。 |
||
* |
*[[F Sharp|F#]]による例: |
||
<source lang="fsharp"> |
<source lang="fsharp"> |
||
printfn "%d" (let rec sum x = if x > 0 then x + sum (x - 1) else 0 |
printfn "%d" (let rec sum x = if x > 0 then x + sum (x - 1) else 0 |
||
49行目: | 53行目: | ||
ただし再帰呼び出しは[[スタックオーバーフロー]]の危険性やオーバーヘッドを伴うため、注意深く使用しなければならない<ref>[https://msdn.microsoft.com/ja-jp/library/dd233229(v=vs.120).aspx 関数 (F#) | MSDN]</ref>。通例、関数型言語では、[[末尾再帰]]呼び出し (tail-recursive call) の形で書かれた関数をループに展開する[[コンパイラ最適化]]により、スタックオーバーフローの危険性および再帰のオーバーヘッドを解消する。[[Scheme]]など、関数型言語の中には末尾再帰呼び出しの最適化を仕様で保証するものもある。 |
ただし再帰呼び出しは[[スタックオーバーフロー]]の危険性やオーバーヘッドを伴うため、注意深く使用しなければならない<ref>[https://msdn.microsoft.com/ja-jp/library/dd233229(v=vs.120).aspx 関数 (F#) | MSDN]</ref>。通例、関数型言語では、[[末尾再帰]]呼び出し (tail-recursive call) の形で書かれた関数をループに展開する[[コンパイラ最適化]]により、スタックオーバーフローの危険性および再帰のオーバーヘッドを解消する。[[Scheme]]など、関数型言語の中には末尾再帰呼び出しの最適化を仕様で保証するものもある。 |
||
=== |
=== データストラクチャ === |
||
⚫ | |||
⚫ | |||
=== データ構造体 === |
|||
=== ファンクタ、モナド、アプリカティブ === |
|||
== 概要 ==<!--関数型プログラミングではプログラムの構成に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>を出力と考えると、コンピュータプログラムはある種の関数であると考えることができる。ここで、入力や出力は記憶装置中のファイルのようなものばかりではなく、キーボードや[[ポインティングデバイス]]によってユーザーから与えられる情報や、画面への表示といった入出力形態も考えられる。関数型プログラミングにおいては実際にそれらを扱う関数としてモデル化する。 |
コンピュータプログラムは通例入力を受け取って何らかの処理を行ない、出力を返すことを目的として書かれる。数学の関数<math>y = f(x)</math>において、<math>x</math>を入力、<math>y</math>を出力と考えると、コンピュータプログラムはある種の関数であると考えることができる。ここで、入力や出力は記憶装置中のファイルのようなものばかりではなく、キーボードや[[ポインティングデバイス]]によってユーザーから与えられる情報や、画面への表示といった入出力形態も考えられる。関数型プログラミングにおいては実際にそれらを扱う関数としてモデル化する。 |
2019年7月19日 (金) 02:50時点における版
![]() | この記事には独自研究が含まれているおそれがあります。 |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8f/Orange_lambda.svg/160px-Orange_lambda.svg.png)
関数型プログラミング(かんすうがたプログラミング、英: functional programming)は、プログラミングパラダイムの一つであり、ソフトウェア工学における主にプログラムリスト作成とコード記述の分野で用いられる考え方である。一説には数理論理学のラムダ計算をモデルにして考案されたと言われる。
プログラムの基本要素である値(value)を限りなく抽象化して、入力と出力の同時表現体にすると共にその変換式も併せ持たせたものが、ターム的に関数(function)と定義されている。関数は同時にパラメータ値とリターン値にも出来るので変換式の連鎖が可能である。
特徴
何をもって関数型プログラミングとするか、ということに関して、関数型プログラミングのコミュニティ内でも正確な定義や合意というものは存在しない。したがって関数型言語の定義も明確な境界はない。ただし、手続き型プログラミングが命令実行の列としてプログラムを記述していくのに対し、関数型プログラミングは複数の式を関数の適用によって組み合わせていくプログラミングスタイルである[1]。手続き型プログラミングの発端は計算機の命令 (instruction/command) や構造に密接にかかわりがある一方、関数型プログラミングは数学の理論を発端としている。
第一級関数と高階関数
参照透過性
純粋関数
厳格評価と遅延評価
型推論
再帰
たとえば、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)
ただし再帰呼び出しはスタックオーバーフローの危険性やオーバーヘッドを伴うため、注意深く使用しなければならない[3]。通例、関数型言語では、末尾再帰呼び出し (tail-recursive call) の形で書かれた関数をループに展開するコンパイラ最適化により、スタックオーバーフローの危険性および再帰のオーバーヘッドを解消する。Schemeなど、関数型言語の中には末尾再帰呼び出しの最適化を仕様で保証するものもある。
データストラクチャ
概要
関数型プログラミングでは関数を第一級オブジェクトとして扱う。理論的な計算モデルとして第一級オブジェクトとしての関数を扱えるラムダ計算や項書き換えを採用している。
コンピュータプログラムは通例入力を受け取って何らかの処理を行ない、出力を返すことを目的として書かれる。数学の関数において、を入力、を出力と考えると、コンピュータプログラムはある種の関数であると考えることができる。ここで、入力や出力は記憶装置中のファイルのようなものばかりではなく、キーボードやポインティングデバイスによってユーザーから与えられる情報や、画面への表示といった入出力形態も考えられる。関数型プログラミングにおいては実際にそれらを扱う関数としてモデル化する。
純粋関数型言語では、参照透過性が常に保たれるという意味において、全ての式や関数の評価時に副作用を生まない。純粋関数型言語であるHaskellやCleanは非正格な評価を基本としており、引数はデフォルトで遅延評価される。一方、Idrisは純粋だが正格評価を採用している。入出力などを参照透過性を保ったまま実現するために、たとえば Haskell ではモナド、Clean では一意型という特殊な型を通して一貫性のある表現を提供する。
非純粋関数型言語では、参照透過性を壊す、副作用があるような式や関数も存在する。LISPなどでデータ構造の破壊的変更などの副作用を多用したプログラミングを行うと、それはもはや手続き型プログラミングである。多くの場合、非純粋関数型言語の評価戦略は正格評価(先行評価)であるが、遅延評価する部分を明示することで、無限リストなどを扱えるものもある。
JavaScriptやJavaなど近年[いつ?]の高水準言語には、関数型言語の機能や特徴を取り入れているものがあるが、変数の値やオブジェクトの状態を書き換えるプログラミングスタイルを通常とするため、関数型言語とは分類されない。一方LISPは、その多くが副作用のある式や関数が多数あり、手続き型スタイルでのプログラミングがされることも多いが、理論的なモデル(「純LISP」)の存在や副作用を使わないプログラミングが基本であること、ないし主には歴史的理由から、関数型言語だとされることが多い。なお、Pascalでは「手続き」と呼ばれるような値を返さないサブルーチンを、C言語では「関数」と呼んでいるが、これは単にルーチンについて、細分類して別の呼称を付けているか、細分類せず総称しているか、という分類と呼称の違いに過ぎず、「Pascalは手続き型言語で、C言語は関数型言語」[4]という一部の書籍に見られる記述は明確に誤りである。また、OCamlやHaskellなどでは、「自明な値(例えば()
)を返す」と、値を返さない(Void
など)は違うものであり、後者は停止しないか例外を出す(そのため結果がない)ようなプログラムを表す。
なお、「関数型言語である」と「関数型プログラミングをする」は同値ではなく、関数型には分類されない言語で関数型プログラミングをすること[5]や、関数型プログラミングを基本とする言語の上で他のパラダイムを実現する例もある[6]。
データフロープログラミング言語も関数型言語と共通した特徴を部分的に持つ。
歴史
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[7]と題した受賞記念講演で関数型プログラミングの重要性を訴えた。講演では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など、後発の規格においてラムダ式(無名関数)をサポートするようになった言語もある。
その他の関数型プログラミング的性質を持つ言語
外部リンク
参考文献
- ^ “Frequently Asked Questions for comp.lang.functional”. May 14, 2015閲覧。
- ^ 本来は等差数列の和の公式を用いて定数時間で問題を解く方法が最適解だが、ここではプログラミングスタイルの比較のため数値計算的手法を用いる。
- ^ 関数 (F#) | MSDN
- ^ 共立出版『ANSI C/C++辞典』ISBN 4-320-02797-3 など
- ^ 関数型プログラミングのエッセンスとして、MISRA CのようにC言語でも副作用を極力用いないプログラミングを推奨しているコーディング標準もある。
- ^ Oleg Kiselyov, Ralf Lämmel. “Haskell's overlooked object system”. Sep 10, 2005閲覧。
- ^ 「プログラミングはフォン・ノイマン・スタイルから解放されうるか?: 関数型プログラミング・スタイルとそのプログラム代数」、米澤明憲訳『ACMチューリング賞講演集』(共立出版)pp. 83-156