関数型プログラミング

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

関数型プログラミングは数理論理学と代数系をルーツにし、ラムダ計算とコンビネータ論理を幹にして構築され、LISP言語が実装面の先駆になっている。応用面では圏論がパラダイムモデルにされている。関数の数学的な純粋性を追求した純粋関数型言語も存在する。純粋関数型パラダイムでは参照透過性が最重視されモナドなどの特別な型システムが導入されている。また並行計算パラダイムでは純粋関数が重視されている。マルチパラダイム言語での導入例では単に有用な構文スタイルとして扱われている事が多い。

高階関数と第一級関数、クロージャまたは無名関数、関数合成と部分適用、ポイントフリーまたはパイプライン、イテレータとジェネレータ、代数的データ型、型推論、パラメトリック多相とアドホック多相、パターンマッチング、束縛変数とイミュータブルなどが関数型プログラミングのスタイル要素として挙げられる。

特徴

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

式と関数

• 関数型プログラムの基本文は式（expression）である。
• 式は、値（value）と演算子（operator）と関数（function）で構成される。式内の代数部分が確定される前の式は抽象値と同義であり、確定後の式は実値と同義になる。ここでの代数とは式内の各束縛変数と、同じく式内の各関数の引数の双方を指す。実値の導出過程は評価（evaluation）と呼ばれる。
• 式は値と同一視されるので、上述の式と値は相互再帰の関係にある。式内の値は他の式の評価値である事があり、その式内にもまた他の値があるといった具合である。これは高階論理と呼ばれる。
• 式評価値の後続への反映は変数への代入ではなく、束縛変数で定数化するのが標準である。
• 後続式の自由変数を省略し、引数または先行式評価値を自動適用する構文がしばしば用いられる。これはポイントフリーまたはパイプラインと呼ばれる。
• 関数も値と同一視される。関数は式に引数（parameter）を結び付けるものである。式の代数部分に引数値が順次束縛され、式ツリーの終端式が評価値になる。
• 関数は、式の引数への適用（application）と解釈される。その対義概念として反適用（unapply）の仕組みも存在する。これは式の引数への適用を差し戻して元の引数を抽出する。
• 関数は、式を第1引数に適用したもの→第2引数に適用したもの→第x引数に適用したもの→評価値、という形をとる。引数を1個ずつ適用する形態はカリー化と呼ばれる。関数の型は「A→B→C→D」のように各引数値から評価値までの型の連鎖として表現される。
• 2個以上の引数を同時適用する非カリー化の関数も用いられる。無名関数がしばしばそれになる。この場合は部分適用やポイントフリーが制限される。
• 関数は名前付きと名前無しの二通りある。後者はラムダ抽象を模した構文で式中に直接定義される。これはクロージャまたは無名関数と呼ばれる。
• 高階論理は関数にも当然適用される。引数値または評価値として扱うことができる関数は第一級関数と呼ばれる。その第一級関数を扱える関数は高階関数と呼ばれる。
• 関数式の引数適用を任意の段階で保留して残り引数の適用を待つ第一級関数を生成できる。これは部分適用と呼ばれる。
• 片方の評価値と片方の第1引数が同じ型の両関数を合わせて双方の写像をつなげた第一級関数を生成できる。これは関数合成と呼ばれる。
• 演算子はデフォルトの式内容を持ち、引数が1～2個に限定された関数と同義である。部分適用された演算子はセクションと呼ばれる第一級関数になる。演算子は言語毎の制約内で任意の再定義および各型にフックした追加定義ができる。これはアドホック多相と呼ばれる。

代数的データ型

• 値は型（type）によって分類される。型は代数的データ型（algebraic data type）として実装される。ただしその実装スタイルはそれを意識させない位単純なものから複雑なものまで言語ごとに様々である。
• 代数的データ型は言わば「型の式」である。代数的データ型は自身の構成要素になる「型」を値と同義の代数として扱う。その代数はパラメトリック多相で総称化できる。
• 代数的データ型（=型の式）は、直積型（product type）非交和型（sum type）帰納型（inductive type）依存型（dependent type）ユニット型（unit type）などの構造を持つ。式的役割は直積型=×演算子、非交和型=＋演算子、帰納型=式再帰、依存型=型関数、ユニット型=NILと同義である。
• 直積+非交和+帰納+依存+ユニットの五構造で大半のデータストラクチャを表現できるが、その他にも指数型（exponential type）交差型（intersection type）など様々にあり、また依存型は用途によって詳細型（refinement type）選択型（option type）などに特化される事がある。
• 直積型は、(A, B) のようなタプルの構造を表わす。また標準的な構造体を表現する。
• 非交和型は、(A | B) のような修飾共用体または列挙型の構造を表わす。
• 帰納型は、ボックス化の構造を表わす。また帰納型は非交和型およびユニット型と併用されて、連結リスト、二分木、多分木の構造を表わす。
• 依存型は、もっぱら関数+環境値+対象値のセットで対象値は参照時に常時関数適用される。その写像は環境値によって変化する。依存型は他の型構造と併用されて動的配列、Maybe値などの構造を表わす。依存型の写像パターンはカインド（kind）と呼ばれる。
• ユニット型は、NIL、NULL、VOIDであり空集合の構造を表わす。
• 指数型は、”関数の型”の構造を表わす。”関数適用の評価値”は指数型と直積型の併用で表現される。
• 交差型は、トレイトや型クラスの構造を表わす。
• プリミティブ値はあくまで理論上ではあるが、数値は非交和型、論理値は非交和型、文字は非交和型、文字列は直積型と非交和型と依存型（可変長文字列時）の併用、複素数は直積型と非交和型の併用で実装されている事になる。
• 代数的データ型は単体値を兼ねたあらゆる多重集合の表現になり、それに対する関数適用は全単射と同義になる。これが関数型プログラミングの代表的利点であるリスト処理に繋がっている。
• 値が式評価の束縛と解釈されるケースではその型宣言はもっぱら省略される。型を自動的に導き出す機能は型推論と呼ばれる。型推論とパラメトリック多相はよく併用される。

再帰と評価戦略

• 反復構造は変数代入したカウンタを増減するループ文ではなく再帰で表現するのが好まれる。カウンタは再帰呼び出し時に、引数として与えて操作するか、イテレーションを用いる。
• 選択構造では関数の引数値によるパターンマッチングが多用される。真理値による単純な比較など、パターンマッチングでは大げさな場合はif文も用いられる。

参照透過性

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

歴史

1930年代に数学者アロンゾ・チャーチによって発明されたラムダ計算は、関数適用を土台にした計算形式体系であり、1937年にチューリング完全の性質が明らかにされてチューリングマシンと等価な計算模型である事が証明されている。この経緯からラムダ計算は関数型プログラミングの基盤に据えられた。ラムダ計算と同等の計算理論にコンビネータ論理があり、こちらは1920年代から1930年代にかけて数学者ハスケル・カリーらによって発明されている。チャーチはラムダ計算を拡張してその全タームに型を付与した型付けラムダ計算も考案しており、これは関数型プログラミングにおける型理論ないし型システムの源流になった。

1950年代

初の関数型プログラミング言語とされる「LISP」は、1958年にマサチューセッツ工科大学の計算機科学者ジョン・マッカーシーによって開発された。LISPの関数はラムダ計算の形式を元に定義され再帰可能に拡張されており、式（フォーム）の高階評価とそのマクロ化など複数の関数型的特徴を備えていた。LISPは数多くの”方言”を生み出しているが、その中でも「Scheme」「Dylan」「Racket」「Clojure」「Julia」は取り分け関数型の特徴を明確にした言語である。1956年に公開された「Information Processing Language」の方が先駆であるが、こちらはアセンブリベースの低水準言語なので前段階扱いである。IPLが備えていたニーモニックコードのリストをオペランドにできるジェネレータ機能はLISPに影響を与えたと言われる。高階オペランドの演算処理は高階関数と同じ働きをし、メモリ一括処理のストリング命令の効率を高めるなどした。

1960年代

1964年に計算機科学者ケネス・アイバーソンが開発した「APL」は、数多く定義された関数象形記号を多次元配列データに適用する機能を中心にした言語であり、取り分けスプレッドシート処理に対する効率性が見出されて、1960年代以降の商業分野と産業分野に積極導入された。APLは関数型ではなく配列プログラミング型に位置付けられてるが、配列を始めとするデータ集合に対する関数適用の有用性を特に証明した言語になった。そのデータ集合処理の可能性に注目した「J」「K」「Q」といった派生言語が後年に登場している。続く1966年に発表された「ISWIM」は関数型を有用な構文スタイルとして扱うマルチパラダイム言語の原点とされ、ALGOLを参考にした構造化プログラミングに高階関数とwhereスコープが加えられていた。60年代の関数型プログラミングの歴史はもっぱらLISPの発展を中心にしていたが、ISWIMは後年の「ML」「Scheme」のモデルにされている。

1970年代

相互自動定理証明に向けて始められた「Logic for computable functions」プロジェクトの中で1973年に導入された「ML」は、代数的データ型とパラメトリック多相などを備えたマルチパラダイム関数型言語であり、計算機科学者ロビン・ミルナーによって開発された。また1975年にMIT人工知能研究所の計算機科学者ガイ・スティールとジェイ・サスマンが設計してAIリサーチ用に導入された「Scheme」もMLに劣らぬ言語仕様を備えており、関数用レキシカルスコープが採用されて構造化が図られていた。更に再帰構造にも着目したスティールとサスマンは後年のラムダペーパーの中で末尾再帰最適化の必要性を訴えている。MLとScheme双方の登場は関数型プログラミングのマイルストーンになった。また同年代に関数の数学的純粋性を重視した「SASL」とクリーネの再帰定理の実装を主な目的にした「NPL」とその後継「Hope」も発表されている。

1977年、バッカス・ナウア記法とFORTRAN開発の功績でこの年のチューリング賞を受けた計算機科学者ジョン・バッカスは「Can Programming Be Liberated From the von Neumann Style? -A Functional Style and Its Algebra of Programs-」と題した記念講演の中で関数型プログラミングの重要性を訴えた。同時に自ら考案した関数型ならぬ関数水準（function-level programming）言語「FP」を紹介している。バッカスはFPのパラダイムをヒエラルキー手法と定義し、それはプログラム代数を用いるコンバイン・フォーム（LISPのform）で実装されると提唱した。ノイマン型からの脱却を題目に掲げているバッカスの理論は、後年のCPUに導入される並列パイプライン処理に通じる構想であった。しかしFPが示す自由変数を極力排した関数水準プログラミングはさほど支持を得られなかった。

1980年代

数学者マルティン＝レーフが1972年から提唱していた直感的型理論は、関数型プログラミングの世界に型理論の依存型の重要性を認識させて型システムの拡張に貢献した。1978年にML設計者のミルナーが発表した型推論アルゴリズムが1982年に証明されると、Hindley–Milner型体系と定義されて型システムは更に成熟した。1983年にMLの標準化を目的にした「Standard ML」が発表され、続く1985年にMLの派生言語「Caml」が公開された。同じく1985年にSASLの後継として発表された「Miranda」は、遅延評価に着目しながら関数の数学的純粋性を追求した言語であり、関数型プログラミング研究用オープンスタンダードのコンセンサスで1987年から策定が開始されたHaskellのモデルになりその進捗を大きく後押しした。それと前後してMirandaは1987年公開の純粋関数型言語「Clean」にも大きな影響を与えている。Cleanは後発のHaskellをも叩き台にして改良を続けた。1986年公開の「Erlang」はLISP、Prolog、Smalltalkといったパイオニア言語をモチーフにデザインされ、並行プログラミング指向の面で特に注目を集めている言語である。

1990年代

1990年にこれも関数型プログラミングのマイルストーン的な純粋関数型言語「Haskell」が初リリースされた。1992年にアップル社による動的型付けデザインの関数型言語「Dylan」が登場した。1993年にオブジェクト指向のクラスを模した抽象データ型を扱う関数型言語「R」が発表された。1995年にLISPのマクロ機能を大幅に強化したコンポーネント指向により各分野に合わせたドメイン固有言語として振る舞える「Racket」が登場した。1996年にはML系列のCamlに当時流行していたオブジェクト指向を導入した「OCaml」が公開された。90年代の関数型プログラミングの歴史では、関数の数学的純粋さを追求する参照透過性指向と、オブジェクト指向との連携ないしその観点下の抽象データ型の導入が比較的目立っていた。日本ではStandard MLに独自の拡張を施した「SML#」が発表されている。研究用または教育用を目的にした関数型言語も続々と発表されておりコンビネータ論理に立ち返った「Unlambda」や、論理型プログラミングを組み合わせた「Wolfram」「Mercury」などが挙げられる。論理型の導入は項置き換えのロジックを応用した強力なパターンマッチングを表現した。

2000年代

2000年代になると関数型プログラミングへの注目度は更に高まり、マルチパラダイムに応用された関数型言語が様々に登場した。2003年のJava仮想マシン動作「Scala」、2005年のマイクロソフト製「F#」、2007年のLISP方言「Clojure」など数々のポピュラー言語が生み出されている。また直感的型理論とカリー=ハワード同型対応のロジックをベースにした証明アシスタント（Proof assistant）によるプログラム正当性の数学的証明を指向した関数型言語が支持され、2004年に「Epigram」2007年に「Agda」および純粋関数型「Idris」が発表されている。関数型構文の有用性がより広く認識されるに従い、オブジェクト指向言語やスクリプト言語にも積極的に導入されるようになった。産業分野からも注目されるようになり、CSG幾何フレームワーク上で動くCADへの導入も始められた。しかし関数型コンセプトに馴染まないオペレーターが定数化規則による値の再代入制限に困惑して設計作業に支障をきたすなどの弊害も明らかになっている。

代表的な関数型言語

LISP　（1958年）

非純粋、動的型付け

ISWIM　（1966年）←　LISP、ALGOL

非純粋、静的型付け

ML　（1973年）←　ISWIM

非純粋、静的型付け

Scheme　（1975年）←　LISP、ISWIM

非純粋、動的型付け

FP　（1977年）

純粋、型なし

Standard ML　（1983年）←　ML、Hope、PASCAL

非純粋、静的型付け

Miranda　（1985年）←　ML、SASL、Hope

純粋、静的型付け

Erlang　（1986年）←　LISP、Prolog、Smalltalk

非純粋、動的型付け

Clean　（1987年）←　Miranda

純粋、静的型付け

Haskell　（1990年）←　ML、Scheme、Miranda、Clean、FP、Hope

純粋、静的型付け

Dylan　（1993年）←　Scheme、CLOS、ALGOL

非純粋、動的型付け

R　（1993年）←　Scheme、CLOS

非純粋、動的型付け

Racket　（1995年）←　Scheme、Eiffel

非純粋、動的型付け

OCaml　（1996年）←　Caml、Standard ML、Modula-3

非純粋、静的型付け

Scala　（2003年）←　Scheme、Haskell、OCaml、Erlang、Smalltalk、Java

非純粋、静的型付け

F#　（2005年）←　Haskell、OCaml、Erlang、Scala、Python、C♯

非純粋、静的型付け

Clojure　（2007年）←　Scheme、Haskell、OCaml、Erlang、Java

非純粋、動的型付け

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

関数型プログラミングは「計算とは何か」という数学の理論を基礎にしており、関数型プログラミングがもつ計算モデルは関数モデルである。たとえば、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