関数型プログラミング概論

本記事では、関数型プログラミング(FP, functional programming)の諸概念を駆け足で見ていきます。特定のプログラミング言語は想定しませんが、参考例を示すためにClojure, Haskell, Javaを使います。あまり実践的な話題には触れません。具体的な言語の学習を始める前のウォーミングアップになれば幸いです。

関数型と命令型

「関数型」というからには、関数型でないプログラミングスタイルもあるわけで、その代表が「命令型」です。主流は命令型なので、自分が慣れ親しんだスタイルが何型か知らないとしたら、それは命令型の可能性が高いです。命令型プログラミング(IP, imperative programming)と比べると、FPには以下のような特徴があります。

式の評価

式を評価するというのは、式の答えを計算することです。中学校の数学のテストを思い出してみて下さい。だいたい、二次方程式や応用問題のような面倒な問題の前に、以下のような問題があったと思います。

1. 次の式を計算せよ。
1) 9+2
2) x=3として、3x+2
3) f(x)=3x+2として、f(3)+f(2)
4) g(x,y)=3x+yとして、g(3,2)

上記の9+23x+2f(3)+f(2)g(3,2)が、それぞれ式(expression)です。特にf(3)g(3,2)のような式は関数適用を意味し、例えばf(3)は「3へ関数fを適用(apply)する」と表現します。また、これらの式の答えを計算することを、評価(evaluate)する、と表現します。

FPでは演算子も関数とみなします。例えば+は、2つの数値を引数に取り、それらの和を返す関数です。数学なら9+2と書きますが、関数適用として書けば+(9,2)となります。よって突き詰めれば、式は、値と関数適用で構成されていると言えます。式を評価するというのは、すなわち、関数適用の結果を求めることに他なりません。

現実的には、式の評価だけを使ってプログラム(ゲームやテキストエディタなど)を作ることはできません。しかしIPとFPとでは、スタンス(意識)が大きく異なるのです。

関数がファーストクラス

FPでは関数が、数値や真偽値、文字列などと同様に「値」として、式の一部になることができます。よって関数へ別の関数を適用したり、関数適用の結果として別の関数を返したりすることが可能です。これは関数がファーストクラスであることを意味します。

5) f(x)=x(3)、g(x)=x+1として、f(g)
6) f(x)=3x、g(x)=x+2、h(x,y)=y∘xとして、h(f,g)

問5)の答えは4で、問6)の答えは引数を3倍して2を足す関数です。ただしは、2つの関数を合成する演算子とします。

関数を値として使えるので、複数の関数を柔軟に組み合わせて式を組み立てることができるようになります。

高階関数

高階関数とは、関数を引数に取る関数、または関数を戻り値として返す関数のことです。前節の問5)〜6)は高階関数の一例ですが、問3)〜4)に比べると少し難解と感じなかったでしょうか。引数や戻り値が数値の場合は計算も簡単です。もし数値ではなく、真偽値や文字列だったとしても大して難しくはないでしょう。しかし引数や戻り値が関数となると、ちょっと次元(というかレベル? 抽象度?)が違う感じがします。この感覚が「高階(higher order)」と呼ばれる由縁です。

高階関数の実例として良く挙がるのが、map, filter, reduceといった関数です。例えば「1から10の間にある偶数それぞれに1を足した数の合計を求めよ」という問題文があった場合、IPならforループやif文などを使ってプログラムを組み立てるでしょう。例としてJavaのコードを示します。

int sum = 0;
for ( int i = 1; i <= 10; i++ ) {
    if ( i % 2 != 0 ) continue;
    sum += i + 1;
}
return sum;

FPの場合、map, filter, reduceを使います。Clojureで書くと以下のようになります。

(->> (range 1 11)
     (filter even?)
     (map inc)
     (reduce +))

文法の説明は省略しますが、1〜10の数値からなるリストを作り、偶数を抽出し、インクリメントして、合算する、という流れになっています。3つの関数filter, map, reduceそれぞれが、even?, inc, +という関数を引数に取って、以下のような計算を行います。

Haskellなら以下のようになります。関数名がClojureとは異なります(foldl1reduceに相当)が、流れは同じです。

foldl1 (+) $ map (+1) $ filter even [1..10]

IPのコードに比べると、FPのコードは、より抽象的で元々の問題文に近いのが分かると思います。また関数を組み合わせて式を構築することにより、sumiのようなローカル変数を使わずに済んでいます。

純粋な関数

純粋(pure)な関数とは、以下の2つの条件を満たす関数のことです。

参照透過(referentially transparent)な関数とは、同じ値に適用すれば結果も毎回同じ値になるような関数のことです。つまり参照透過な関数の適用結果は、引数の値のみによって決まります。裏に隠した小細工が無いという点で、透過という表現がマッチしています。引数以外の情報(例えばグローバル変数やインスタンス変数の値など)によって結果が左右されるような関数やメソッドは参照透過ではありません。

関数適用の本質(いわば本作用)は、引数の値に基づいて評価結果を返すことです。それ以外の作用を副作用(side effect)と呼びます。例えばグローバル変数の値を変更したり、画面に何かを表示したり、音を鳴らしたりするのは副作用です。そういった作用を持つ関数は純粋ではありません。

まとめると、純粋な関数は引数に応じて結果を返すことに徹しています。

pure function

一方、純粋でない関数は、返す結果が状態に依存したり、状態を変更したりします。

impure function

ここで言う「状態」は単なる変数などではなく、関数の外部にある、変わりうる情報すべてを指しています。例えば、ユーザのキー入力、ファイルIO、DBアクセス、socket通信、画面表示などは、すべて状態への依存や状態の変更とみなします。FPの世界では、依存や変更をまとめて「入出力(IO)」と表現することが多いです。状態やIOを見つけたら、純粋性喪失のサインです。

同様に、引数を取らない関数や、何も返さない関数も、純粋ではない証拠と言えるでしょう。純粋な関数が引数を取らないとすると、もはやそれは関数ではなく定数です。また関数が何も返さないとしたら、副作用以外に目的は無いはずです。

純粋さの利点

純粋な関数は、以下の点で不純(impure)な関数より優れています。

純粋な関数をテストしたければ、適切な引数に適用してみて、結果を期待値と比較するだけでOKです。一方、不純な関数のテストは、事前準備(グローバル変数に特定の値を格納しておくなど)が必要だったり、確認作業が複雑(出力されたファイル内容のチェックなど)だったりします。

またコードを解析するときも、使われているのが参照透過な関数ばかりなら、引数のみに集中してコードの流れを追うことができます。「このときはグローバル変数の値がこう変わってるはずだから……」といった具合に引数以外の情報(つまり状態)をケアする必要がありません。

実際には、純粋な関数のみを使って実用的なプログラムを作るのは無理でしょう。しかし、なるべく純粋な関数を使い、不純な関数を一箇所にまとめようとするのがFPスタイルです。このとき、不純な関数の中で純粋な関数を使うのは構いませんが、純粋な関数の中で不純な関数を使うことはできません(使うと不純になるので)。

fp program

部分適用

関数の引数の数をアリティ(arity)と呼び、関数をアリティより少なめの引数に適用することを部分適用(partial application)と呼びます。部分適用を評価すると、残りの引数を取って元の関数の本来の計算を実施する関数が返ります。アリティ3の関数を例に挙げます。

2. f(x,y,z)=x+y-zとして、以下の式を計算せよ。
1) f(5,4,3)
2) f(5,4)
3) (f(5,4))(3)

1)の答えはもちろん6ですが、2)は引数が足りないので部分適用です。つまり2)は関数を返します。それは、残りの引数zを取って5+4-zを返すような関数です。よって3)の答えはやはり6になります。

部分適用は関数のアリティを減らしたいときに便利です。例えば高階関数のmapはアリティ1の関数を引数に取るので上記の関数fには適用できません(fのアリティは3)。しかしf(5,4)のように、3つの引数のうちxとyをそれぞれ5と4に固定すれば、mapに使える関数が手に入るわけです。g(z)=5+4-zという別の関数を定義しても良いですが、それだと「2つを足して3つ目を引く」というロジックがfgに重複するのでDRY(don't repeat yourself)の原則に反します。

ラムダ(無名関数)

部分適用の説明のところで「引数zを取って5+4-zを返すような関数」という表現を使いました。これを文章ではなく、式でも書けると便利です。そこで数学では、λz.5+4-zのように表記します。λ.の間にあるのが引数です。これをClojureで書くなら(fn [z] (- (+ 5 4) z))となり、Haskellなら\z -> 5 + 4 - zです。そして、このように表記した関数をラムダ(lambda)と呼びます。関数名を持たないので無名関数(anonymous function)とも呼ばれます。

関数の定義は、それを使用する箇所とは離れた場所にあるのが普通ですが、ラムダなら使うその場で定義するので、コードを読みやすくできる可能性があります。

カリー化

部分適用の考え方を極限まで拡張すると、どんなアリティの関数も、実はアリティ1の関数の組み合わせで構成できることが分かります。これをカリー化(currying)と呼びます。例えば前述のf(x,y,z)=x+y-zをカリー化した関数cfは、cf(x)=λy.(λz.x+y-z)です。f(5,4,3)と同じことをcfを使って行うには、まずcfを5に適用してλy.(λz.5+y-z)を得ます。次にこのラムダを4に適用してλz.5+4-zを得ます。最後にこれを3へ適用すれば解答の6を得ることができます。

学問の世界では、複雑な問題(アリティが2以上とか)を単純な問題(アリティが1)に置き換えられることが大きな意味を持つ場合もあるようですが、プログラミングにおいてカリー化のメリットを感じることは少ないかもしれません。

不変な変数

多くのIP用言語は、変数を変更不可にするためのキーワードを提供しています。Javaならfinal、C++ならconstといった具合です。一方FPでは、変数はデフォルトで変更不可(immutable)です。一旦変数を初期化したら、もうそれを変更することはありません。変更を許さないことは、状態の排除、すなわち関数の純粋性につながります。

とは言え、もちろん変数を初期化するときは「代入」のような操作が必要です。FPではそれを「定義」と考えます。f(x)=x+1y=3は、fyを定義しているわけです。あるいは、値(λx.x+1や3)に名前(fy)を付けたと解釈しても良いでしょう。

変数を変更できないことが大きな制約に感じるかもしれませんが、実はそれほどでもありません。鍵は関数の引数にあります。f(x)を異なる値へ適用するたびにxの値は変わります。これを利用すれば、多くのIP的な変数を使わずに済みます。既にmapreduceのサンプルコードを通して、変数を使わずにループや積算が可能なことを示しました。

不思議な関数

純粋性の判断が微妙な、2つの関数を紹介します。

クロージャ

例えばλx.x+yのように、ラムダの中に引数以外の変数がある場合、これを自由変数(free variable)と呼びます。自由変数の値はラムダの外側のコードによって決まります。一見、参照透過性が破られている気がしますが、そうとも限りません。

例えばこのラムダを別のラムダの中で、λy.(λx.x+y)のように使ってみましょう。外側のラムダ内が変数yのスコープになります。よって、この外側のラムダを5へ適用したときに返るλx.x+yでは、yの値は5です。同じく10へ適用したときに返るλx.x+yではyが10です。つまり、どちらも参照透過なラムダです。自由変数が(外側のラムダの)スコープにより閉じられることから、このようなラムダのことをクロージャ(closure)と呼びます。

メモ化

参照透過な関数の結果は引数によってのみ決まるので、もし引数と結果との対応表を事前に持っておくことができれば、本来の計算を行うことなく結果を返すことができます。また関数が副作用を持たないなら、本来の計算を行おうと行うまいと、外側のコードにとっては無関係です。メモ化(memoize)は、これらのことを利用して関数適用をスピードアップさせる技法です。

メモ化の仕組みは以下の通りです。

メモ化した関数が依然として純粋と言えるかどうかに関しては議論の余地があります。メモ化に用いた対応表はまさしく状態の一種と言えそうです。しかし、もしこの対応表が関数内部からしかアクセスできないのなら、少なくとも見かけ上は参照透過ですし、対応表を変更することが副作用に相当するのかどうかはグレイゾーンでしょう(外側から観測できない作用を副作用と呼べるか? という話し)。

遅延評価

FPの言語には、遅延評価(lazy evaluation)と呼ばれる評価戦略を採用するものがあります。評価戦略とは、複数の項からなる式を評価するときの評価順序のことです。例えばf(3+1)+f(2-1)を評価するとき、一般的な評価戦略では、関数fを適用する前に3+12-1を評価します。しかし、例えばHaskellのような、遅延評価を採用する言語では、結果を出すために必要になるギリギリまで評価を先送りにします。例を挙げましょう。

print $ map (div 8) [-2..4]
[-4,-8,*** Exception: divide by zero

(div 8)では、関数divを8へ部分適用することにより、何かを8で割る関数を得ています。それを、-2から4までの整数からなるリストへmapしました。すると、リストの3番目の要素(つまり0)のところで、0除算エラーが発生してしまいます。

では次に、take関数を使って、mapの結果から先頭の2要素だけを取り出してみましょう。

print $ take 2 $ map (div 8) [-2..4]
[-4,-8]

今度はうまくいきました。これは以下のように説明できます。

これが遅延評価です。結果的にdiv 8 0を評価する必要がなかったのでエラーは起きませんでした。

遅延評価のメリットは、あまり効率を気にすることなく巨大なデータ(例えば無限に続くリストとか)を扱えることです。何重にもネストする関数適用の間で大きなデータを受け渡しするときでも、最終的に必要なデータだけがメモリにロードされ計算されます。遅延評価が使えない環境では、あらかじめ必要なサイズだけを切り出したりする必要があるでしょう。しかし、必要なサイズがいつでも事前に計算できるとは限りません。そして事前に計算できない場合、コードはトリッキーになりがちです(例えばUTF-8のテキストファイルから最初の1文だけを取り出したいときなど)。

まとめ

IPのプログラムが「CPUに対する命令を列挙した指示書」であるのに対し、FPのプログラムは「解答を得るための式の(つまり関数適用の)連なり」です。よってIPのコードは「実行」するのに対し、FPのコードは「評価」します。そしてFPの関数は、「呼び出す」ものではなく、戻り値を得るために「適用」するものと考えます。

FPでは、「純粋な」複数の関数をつなげることで大きな式を組み立てます。関数をつなげるためには高階関数や再帰を使います(再帰はFP独特の技法ではないので本稿では割愛しました)。不純な関数や可変な変数の使用は最小限にとどめます。部分適用、ラムダ、クロージャといった補助的なテクニックが式の表現力を高めてくれます。また遅延評価は、巨大なデータの扱いを楽にしてくれます。