関数型プログラミング

関数型プログラミング（かんすうがたプログラミング、英: functional programming）とは、数学的な意味での関数を主に使うプログラミングのスタイルである^[1]。 functional programming は、関数プログラミング（かんすうプログラミング）などと訳されることもある^[2]。

関数型プログラミング言語（英: functional programming language）とは、関数型プログラミングを推奨しているプログラミング言語である^[1]。略して関数型言語（英: functional language）ともいう^[1]。

概要

関数型プログラミングは、関数を主軸にしたプログラミングを行うスタイルである^[1]。ここでの関数は、数学的なものを指し、引数の値が定まれば結果も定まるという参照透過性を持つものである^[1]。

参照透過性とは、数学的な関数と同じように同じ値を返す式を与えたら必ず同じ値を返すような性質である^[1]。次の square 関数は、 2 となるような式を与えれば必ず 4 を返し、 3 となるような式を与えれば必ず 9 を返し、いかなる状況でも別の値を返すということはなく、これが参照透過性を持つ関数の一例となる^[1]。

def square(n):
  return n ** 2

次の countup 関数は、同じ 1 を渡しても、それまでに countup 関数がどのような引数で呼ばれていたかによって、返り値が 1, 2, 3, ... と変化するため、引数の値だけで結果の値が定まらないような参照透過性のない関数であり、数学的な関数とはいえない^[1]。

counter = 0
def countup(n):
  global counter
  counter += n
  return counter

関数型プログラミングは、参照透過性を持つような数学的な関数を使って組み立てた式が主役となる^[1]。別の箇所に定義されている処理を利用することを、手続き型プログラミング言語では「関数を実行する」や「関数を呼び出す」などと表現するが、関数型プログラミング言語では「式を評価する」という表現も良く使われる^[3]。

参照透過性

→詳細は「参照透過性」を参照

参照透過性とは、同じ値を与えたら返り値も必ず同じになるような性質である^[1]。参照透過性を持つことは、その関数が状態を持たないことを保証する^[4]。状態を持たない数学的な関数は、並列処理を実現するのに適している^[4]。関数型プログラミング言語の内で、全ての関数が参照透過性を持つようなものを純粋関数型プログラミング言語という^[4]。

入出力

関数型プログラミングでは、数学的な関数を組み合わせて計算を表現するが、それだけではファイルの読み書きのような外界とのやり取りを要する処理を直接的に表現できない^[5]。このような外界とのやり取りを I/O (入出力) と呼ぶ^[5]。数学的な計算をするだけ、つまり 1 + 1 のようなプログラム内で完結する処理ならば、入出力を記述できなくても問題ないが、現実的なプログラムにおいてはそうでない^[5]。

非純粋な関数型プログラミング言語においては、式を評価すると同時に I/O が発生する関数を用意することで入出力を実現する^[5]。たとえば、 F# 言語では、printfn "Hi." が評価されると、 () という値が戻ってくると同時に、画面に Hi. と表示される I/O が発生する^[5]。

Haskell では、評価と同時に I/O が行われる関数は存在しない^[5]。たとえば、 putStrLn "Hi." という式が評価されると IO () 型を持つ値が返されるが画面には何も表示されず、この値が Haskell の処理系によって解釈されて初めて画面に Hi. と表示される^[5]。 I/O アクションとは、ファイルの読み書きやディスプレイへの表示などのような I/O を表現する式のことである^[5]^[6]。 IO a という型は、コンピュータへの指示を表す I/O アクションを表現している^[5]^[7]。ここでの IO はモナドと呼ばれるものの一つである^[8]。

Clean では、一意型を用いて入出力を表す。

手法

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

Haskell では、関数合成の二項演算子を使ってポイントフリースタイルで関数を定義することができる^[9]。関数をポイントフリースタイルで定義すると、データより関数に目が行くようになり、どのようにデータが移り変わっていくかではなく、どんな関数を合成して何になっているかということへ意識が向くため、定義が読みやすく簡潔になることがある^[9]。関数が複雑になりすぎると、ポイントフリースタイルでは逆に可読性が悪くなることもある^[9]。

言語

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

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

関数型プログラミング言語
名前	型付け	純粋性	評価戦略	理論的背景
Clean	静的型付け	純粋	遅延評価
Elm	静的型付け	純粋	正格評価
Erlang	動的型付け	非純粋	正格評価
F#	静的型付け	非純粋	正格評価
Haskell^[2]	静的型付け^[2]	純粋^[2]	遅延評価^[2]	型付きラムダ計算^[3]
Idris	静的型付け	純粋	正格評価	型付きラムダ計算
Lazy K	型なし	純粋	遅延評価	コンビネータ論理
LISP 1.5 Scheme Common Lisp Clojure	動的型付け	非純粋	正格評価	型無しラムダ計算^[3]
LISPの各種方言^[3]	方言による	方言による	方言による
Miranda	静的型付け	純粋	遅延評価
ML Standard ML OCaml	静的型付け	非純粋	正格評価
Scala	静的型付け	非純粋	正格評価
Unlambda	型なし	非純粋	正格評価	コンビネータ論理
Lean	静的型付け	純粋	正格評価	型付きラムダ計算

手続き型プログラミングとの比較

C 言語や Java 、 JavaScript 、 Python 、 Ruby などの2017年現在に使われている言語の多くは、手続き型の文法を持っている^[10]。そのような言語では、文法として式 (expression) と文 (statement) を持つ^[10]。ここでの式は、計算を実行して結果を得るような処理を記述するための文法要素であり、加減乗除や関数呼び出しなどから構成されている^[10]。ここでの文は、何らかの動作を行うようにコンピュータへ指示するための文法要素であり、条件分岐の if 文やループの for 文と while 文などから構成されている^[10]。手続き型の文法では、式で必要な計算を進め、その結果を元にして文でコンピュータ命令を行うという形で、プログラムを記述する^[10]。このように、手続き型言語で重要なのは文である^[10]。

それに対して、関数型言語で重要なのは式である^[10]。関数型言語のプログラムはたくさんの式で構成され、プログラムそのものも一つの式である^[10]。たとえば、 Haskell では、プログラムの処理の記述において文は使われず、外部の定義を取り込む import 宣言も処理の一部として扱えない^[10]。関数型言語におけるプログラムの実行とは、プログラムを表す式の計算を進めて、その結果として値 (value) を得ることである^[10]。式を計算することを、評価する (evaluate) という^[10]。

手続き型言語ではコンピュータへの指示を文として上から順に並べて書くのに対して、関数型言語では数多く定義した細かい式を組み合わせてプログラムを作る^[10]。手続き型言語では文が重要であり、関数型言語では式が重要である^[11]。

式と文の違いとして、型が付いているかどうかというのがある^[11]。式は型を持つが、文は型を持たない^[11]。プログラム全てが式から構成されていて、強い静的型付けがされているのならば、プログラムの全体が細部まで型付けされることになる^[11]。このように細部まで型付けされているようなプログラムは堅固なものになる^[11]。

歴史

1930年代

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

1960年代

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

歴史的に言えば、 LISP に続いて関数型プログラミングパラダイムへ刺激を与えたのは、1960年代半ばのピーター・ランディン（英語版）の成果である^[15]。ランディンの成果はハスケル・カリーとアロンゾ・チャーチに大きな影響を受けていた^[15]。ランディンの初期の論文は、ラムダ計算と、機械および高級言語 (ALGOL 60) との関係について議論している^[15]。ランディンは、1964年^{[注釈 4]}に、 SECD マシンと呼ばれる抽象的な機械を使って機械的に式を評価する方法を論じ、1965年^{[注釈 5]}に、ラムダ計算で ALGOL 60 の非自明なサブセットを形式化した^[15]。1966年^{[注釈 6]}にランディンが発表した ISWIM（If You See What I Mean の略）という言語（群）は、間違いなく、これらの研究の成果であり、構文や意味論において多くの重要なアイデアを含んでいた^[15]。 ISWIM は、ランディン本人によれば、「 LISP を、その名前にも表れたリストへのこだわり、手作業のメモリ割り当て、ハードウェアに依存した教育方法、重い括弧、伝統への妥協、から解放しようとする試みとして見ることができる」^[15]。関数型言語の歴史において ISWIM は次のような貢献を果たした^[16]。

構文についての革新^[15]
- 演算子を前置記法で記述するのをやめて中置記法を導入した^[15]。
- let 節と where 節を導入して、さらに、関数を順序なく同時に定義でき、相互再帰も可能なようにした^[15]。
- 宣言などを記述する構文に、インデントに基づいたオフサイドルールを使用した^[15]。
意味論についての革新^[16]
- 非常に小さいが表現力があるコア言語を使って、構文的に豊かな言語を定義するという戦略を導入した^[15]。
- 等式推論 (equational reasoning) を重視した^[15]。
- 関数によるプログラムを実行するための単純な抽象機械としての SECD マシンを導入した^[16]。

ランディンは「それをどうやって行うか」ではなく「それの望ましい結果とは何か」を表現することに重点を置いており、そして、 ISWIM の宣言的なプログラミング・スタイルは命令的なプログラミング・スタイルよりも優れているというランディンの主張は、今日まで関数型プログラミングの賛同者たちから支持されてきた^[17]。その一方で、関数型言語への関心が高まるまでは、さらに10年を要した^[17]。その理由の一つは、 ISWIM ライクな言語の実用的な実装がなかったことであり、実のところ、この状況は1980年代になるまで変わらなかった^[17]。

ケネス・アイバーソンが1962年^{[注釈 7]}に発表した APL は、純粋な関数型プログラミング言語ではないが、その関数型的な部分を取り出したサブセットがラムダ式に頼らずに関数型プログラミングを実現する方法の一例であるという点で、関数型プログラミング言語の歴史を考察する際に言及する価値はある^[17]。実際に、アイバーソンが APL を設計した動機は、配列のための代数的なプログラミング言語を開発したいというものであり、アイバーソンのオリジナル版は基本的に関数型的な記法を用いていた^[17]。その後の APL では、いくつかの命令型的な機能が追加されている^[17]。

脚注

[脚注の使い方]

出典

^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l 本間, 類地 & 逢坂 2017, p. 3
^ ^a ^b ^c ^d ^e 本間, 類地 & 逢坂 2017, p. 2
^ ^a ^b ^c ^d ^e ^f 本間, 類地 & 逢坂 2017, p. 4
^ ^a ^b ^c ^d 本間, 類地 & 逢坂 2017, p. 5
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j 本間, 類地 & 逢坂 2017, p. 6
^ 本間, 類地 & 逢坂 2017, p. 23
^ 本間, 類地 & 逢坂 2017, p. 31
^ 本間, 類地 & 逢坂 2017, p. 32
^ ^a ^b ^c ^d Lipovača 2012, p. 22
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l 本間, 類地 & 逢坂 2017, p. 22
^ ^a ^b ^c ^d ^e 本間, 類地 & 逢坂 2017, pp. 22–23
^ ^a ^b ^c Hudak 1989, p. 363
^ Hudak 1989, p. 367
^ Hudak 1989, pp. 367–368
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l Hudak 1989, p. 371
^ ^a ^b ^c Hudak 1989, pp. 371–372
^ ^a ^b ^c ^d ^e ^f 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, https://jstor.org/stable/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