関数型プログラミング

関数型言語（英: functional language）は、関数型プログラミングのスタイルまたはパラダイムを扱うプログラミング言語の総称である。関数型プログラミングは関数の適用と合成から組み立てられる宣言型プログラミングの一種であり、関数は引数の適用から先行式の評価を後続式の適用に繋げて終端評価に到る式のツリーとして定義される。関数は引数ないし返値として渡せる第一級関数として扱われる。

関数型プログラミングは数理論理学と圏論を主にした数学分野をルーツにし、関数形式体系のラムダ計算とコンビネータ論理を幹にして構築され、LISP言語が実装面の先例になっている。関数の数学的な純粋性を追求した純粋関数型言語も存在する。純粋関数型パラダイムでは参照透過性が最重視されモナドなどの特別な型システムが導入されている。また並行計算パラダイムでは純粋関数が重視されている。マルチパラダイム言語での導入例では、単に有用な構文スタイルとして扱われている事が多い。高階関数と第一級関数、クロージャまたは無名関数、関数合成と部分適用、ポイントフリーまたはパイプライン、イテレーションまたはリスト処理、型推論、パラメータ多相とアドホック多相、パターンマッチング、イミュータブル定義などが関数型プログラミングのスタイル要素として挙げられる。

特徴

ここでは関数型プログラミング本来の構文スタイルを元にして説明する。式を基本文にする関数型に対して、ステートメントを基本文にする手続き型やオブジェクト指向などの命令型プログラミング言語では必要に応じて構文スタイルを変えて実装されている。代表的なのは「式の引数への適用」に対する「引数を関数に渡す」である。ただし双方ともアセンブリコード上では同様に符号化される。代数的データ型も構造体や連結リストで置き換えられているのが通例である。

式と関数

• 関数型プログラムの基本文は式（expression）である。式は第一級要素として扱われる。
• 式は、値（value）と演算子（operator）と関数（function）で構成される。式内の代数部分が確定される前の式は抽象値と同義であり、確定後の式は実値と同義になる。ここでの代数とは式内の各束縛変数と、同じく式内の各関数の引数の双方を指す。実値の導出過程は評価（evaluation）と呼ばれる。
• 式評価値の後続への反映は変数への代入ではなく、束縛変数で定数化するのが本来の在り方である。
• 引数値または先行式の評価値をデフォルトで後続式の適用値と見なして値の記述を省略する構文が多用される。これはパイプラインまたはポイントフリーと呼ばれる。
• 関数も値と同一視される。関数は引数（parameter）と式を結び付けるユニットである。式の代数部分に引数値が順次束縛され、式ツリーの終端式が評価値になる。
• 関数は、式の引数への適用（application）と解釈される。その対義概念として反適用（unapplication）の仕組みも存在する。これは式の引数への適用を差し戻して元の引数を抽出する。
• 関数は、式を第1引数に適用したもの→第2引数に適用したもの→第x引数に適用したもの→評価値、という形をとる。関数の型は各引数値から評価値までの型の連鎖として表現され、これはカインド（kind）とも呼ばれる。上述のように引数を1個ずつ適用する形態はカリー化と呼ばれる。
• 2個以上の引数を同時適用する非カリー化の関数も用いられる。無名関数がしばしばそれになる。この場合は部分適用やポイントフリーが制限される。
• カリー化は関数の断片化と連結を可能にする。前者は部分適用と呼ばれ、例えば式を第1引数に適用しただけのものを後続の式で使い回せる。後者は関数合成と呼ばれ、評価値と第1引数が同じ型の関数をつなげたものを後続の式で使い回せる。
• 関数は名前付きと名前無しの二通りある。後者はラムダ抽象を模した構文で式中に直接定義される。これはクロージャまたは無名関数と呼ばれる。
• 関数の引数値を関数にする事も可能であり、また関数の評価値を関数にする事も可能である。他の関数を引数値または評価値として扱える関数は高階関数と呼ばれる。他の関数から引数値または評価値として扱われる関数は第一級関数と呼ばれる。
• 言語によるが、演算子はデフォルトの式内容を持ち、引数が1～2個に限定された関数と同義である。演算子の式内容は任意に再定義できる。部分適用された演算子はセクションと呼ばれる第一級関数になる。

代数的データ型

• 値（value）は代数的データ型（algebraic data type）として表現される。これは直積、非交和、再帰の構造を持ち、単体値を兼ねたあらゆる値集合の汎用表現になる。代数的データによって単体値と値集合を同等に扱うスタイルが関数型プログラミングの代表的利点であるリスト処理（イテレーション）に繋がっている。
• 代数的データ型は、atom（プリミティブ）nil（無）cons（内包値＋リンク）の要素で実装される。atomは数値、論理値、文字、文字列を指す。consの内包値はatomまたは次のcons（=入れ子の代数的データ）を指し、consのリンクは次のconsまたはnil（=終端）を指す。代数的データはconsの再帰で構成されてゼロ個から複数以上の値を内包する事になる。この再帰ツリー構造はS式と呼ばれる。
• 値は型（type）によって分類される。
• 全ての値が同じ型の代数的データはlistと呼ばれ、異なる場合はtupleと呼ばれる。listは用法的に線形リストと同義であり、tupleは用法によっては構造体の近似物になる。後者は前述の直積である。
• 型選択している代数的データはvariantsなどと呼ばれ、共用体ないし列挙型の類似物になる。これは前述の非交和である。
• 前述の再帰は代数的データの入れ子構造を表現できる。その入れ子はパラメータ多相で総称型にできる。
• 値の型宣言と型指定は積極的に省略される。省略された型を自動的に導き出す機能は型推論と呼ばれる。型推論とパラメータ多相はよく併用される。

再帰と評価戦略とパターンマッチング

• 反復構造は変数代入したカウンタを増減するループ文ではなく、カウンタを束縛変数として扱う関数の再帰で表現するのが本来の在り方である。
• 選択構造では関数の引数値によるパターンマッチングが多用される。

参照透過性

純粋関数型言語は、参照透過性の遵守をプログラムの枠組みにしている。参照透過性の意味自体はシンプルであり、関数は同じ引数値に対して必ず同じ評価値を恒久的に導出し、その評価過程においてプログラムの認知内における一切の情報資源に作用を及ぼさない、というものである。プログラムが認知する範囲内のいずれかの情報資源が変化するのと同時にいずれかの関数の評価過程も変化してしまう現象が副作用と呼ばれる。

歴史

初の関数型プログラミング言語とされる「LISP」は、1950年代にマサチューセッツ工科大学のジョン・マッカーシーによって開発された。数々の後発言語の手本にされたマルチパラダイム言語であるLISPは同時に、ラムダ計算を元にして再帰可能にデザインされたfunctionを始めとする数々の関数型プログラミング的な特徴を備えていた。ラムダ計算は1930年代にアロンゾ・チャーチによって発明された計算模型であり、1937年にチューリング完全である事が示されて、チューリングマシンと等価な計算形式体系である事が証明されている。この経緯からラムダ計算は後に関数型プログラミングの基底理論に位置付けられた。同じく1930年代にラムダ計算と並ぶ計算模型のコンビネータ論理を考案し、カリー化の語源にもなったハスケル・カリーがいる。LISPは多くの派生言語を生んでいるが、その中でも「Scheme」「Clojure」「Dylan」「Julia」は関数型プログラミングとしての特徴をより強調した言語になっている。

現代的な関数型プログラミング言語の祖としてはアイディアが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#などが登場した。

代表的な関数型言語

言語	純粋さ	型付け
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言語は関数型言語」という一部の書籍に見られる記述は明確に誤りである。また、OCamlやHaskellなどでは、「自明な値(例えば())を返す」と、値を返さない（Voidなど）は違うものであり、後者は停止しないか例外を出す(そのため結果がない)ようなプログラムを表す。

なお、「関数型言語である」と「関数型プログラミングをする」は同値ではなく、関数型には分類されない言語で関数型プログラミングをすることや、関数型プログラミングを基本とする言語の上で他のパラダイムを実現する例もある。データフロープログラミング言語も関数型言語と共通した特徴を部分的に持つ。

その他の関数的性質を持つ言語

• APL
• XSLT

関数型プログラミングの例

関数型プログラミングは「計算とは何か」という数学の理論を基礎にしており、関数型プログラミングがもつ計算モデルは関数モデルである。たとえば、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のようにループ構文をサポートせず、従来の手続き型プログラミングが難しいケースもある。

逆に手続き型言語を使って関数型プログラミングを行なうことも可能であるが、末尾再帰呼び出しの最適化がサポートされるかどうかはコンパイラ次第である。

外部リンク

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