関数型プログラミング

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

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

概要

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

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

def square(n):
  return n ** 2

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

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

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

参照透過性

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

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

入出力

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

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

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

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

手法

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

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

言語

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

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

関数型プログラミング言語

名前	型付け	純粋性	評価戦略	理論的背景
Clean	静的型付け	純粋	遅延評価
Clojure	動的型付け	非純粋	正格評価
Erlang	動的型付け	非純粋	正格評価
F#	静的型付け	非純粋	正格評価
Haskell	静的型付け	純粋	遅延評価	型付きラムダ計算
Idris	静的型付け	純粋	正格評価	型付きラムダ計算
Lazy K	型なし	純粋	遅延評価	コンビネータ論理
LISP	動的型付け	非純粋	方言による	型無しラムダ計算
Miranda	静的型付け	純粋	遅延評価
ML (プログラミング言語)	静的型付け	非純粋	先行評価
SML	静的型付け	非純粋	正格評価
OCaml	静的型付け	非純粋	正格評価
Scala	静的型付け	非純粋	正格評価
Scheme	動的型付け	非純粋	正格評価
Unlambda	型なし	非純粋	正格評価	コンビネータ論理

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

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

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

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

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

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

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

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

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

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

• 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)

ただし再帰呼び出しはスタックオーバーフローの危険性やオーバーヘッドを伴うため、注意深く使用しなければならない。通例、関数型言語では、末尾再帰呼び出し (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 年と 1941 年に発表したラムダ計算の研究ほど基本的で重要な影響を与えたものはない。ラムダ計算は、それが考え出された当時はプログラムを実行するようなコンピュータが存在しなかったためにプログラミング言語として見なされなかったにも関わらず、今では最初の関数型言語とされている。 1989 年現在の関数型言語は、その殆どがラムダ計算に装飾を加えたものとして見なせる。

1950 年代

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

1960 年代

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

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

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

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

概要 (old)

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

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

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

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

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

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

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

歴史 (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と題した受賞記念講演で関数型プログラミングの重要性を訴えた。講演では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#などが登場した。

参考文献

• 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
• 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

外部リンク

• なぜ関数プログラミングは重要か
• The Functional Programming Language XSLT - A proof through examples

関連項目

• 参照透過性
• カリー化