関数型プログラミング
関数型プログラミングとは?
チュートリアルも、かなり進んできたが、まだ関数型プログラミングにつ
いて深く考えたことがない。これまでに教えた機能をあまさず使うことを考えれば — 豊富なデータ型、
パターンマッチング、型推論、入れ子関数 —
これはもう、"超C言語"みたいに思えてくる。これらはたしかにクールな機能で、あなたのコードを、わかりやすく、読みやすく、それでいてバグは少なく、
してくれる。しかし、それらは実は、関数型プログラミングとは、ほとんど関係がない。私の主張としては、関数型言語がすばらしい理由は、関数型プログラミ
ングだからではない。それよりも、私たちがCライクの言語に長年、足をとられていたからということと、その間にプログラミングの最先端が目に見えて動いたからだ、というのが大きいと思う。私たちは、struct { int type; union { ... }
を何度書いたことだろう。その一方で、MLとHaskellプログラマは、安全なヴァリアントと、データ型へのパターンマッチングを手にしていた。私たちが、すべてのmalloc
をfree
することに神経をすりへらす、その一方で、彼らは、ガーベジコレクタつきの言語で、80年代から続いた手のコードより高い性能を、叩き出していた。
さあ、そろそろ、関数型プログラミングがどんなものかを、話してもよいころだろう。
そのものズバリじゃないかもしれないが、基本的な定義はこうだ:関数型言語では、関数は第一級の身分をもつ。
百聞は一見にしかず。例を見てみよう。
# let double x = x * 2 in
List.map double [ 1; 2; 3 ];;
- : int list = [2; 4; 6]
この例は、まず定義をやっている。入れ子関数のdouble
は、引数x
をとり、x * 2
を返す。それからmap
はdouble
を、与えられたリスト([1; 2; 3]
)の各要素に呼び、結果をだす:
数をそれぞれ2倍したリストである。
map
は高階関数という。高階関数は、関数を引数にとる関数というのをちょっと言いかえただけだ。
簡単じゃないか。もしC/C++のたしなみがあるなら、これは関数ポインタを渡しているようにみえる。Javaには、憎いあンちくしょう、匿名クラ
スというものがある。これは、クロージャを焼き直して、遅く長たらしくしたようなものだ。Perlを知っているなら、もうPerlのクロージャやmap
関数をご存じで、使っていることと思う。話しているのはまさにそれのことだ。実はPerlは結構いい関数型言語である。
クロージャは関数で、定義されたときの"環境"ともいうべきものを保持している。特に、クロージャは、定義の時点で有効だった変数を、参照できる。うえの関数を一般化して、整数のリストをとれるように、また、各々の要素を掛け算するのに、任意の値n
でできるようにしよう。
# let multiply n list =
let f x =
n * x in
List.map f list;;
val multiply : int -> int list -> int list = <fun>
よって:
# multiply 2 [1; 2; 3];;
- : int list = [2; 4; 6]
# multiply 5 [1; 2; 3];;
- : int list = [5; 10; 15]
大切なので注意してほしいのは、multiply
関数に入れ子関数f
があることだ。これがクロージャだ。
f
がどのようにn
の値を使っているかみてほしい。引数として明示的にf
に渡されているわけではない。
かわりにf
はそれを環境から拾っている。 - これはmultiply
関数への引数であり、よって、この関数内で有効である。
筋はあっているようだが、ちょっと、map
を呼んでいるところをよくみてほしい: List.map f list
map
はList
モジュールで定義されていて、今のコードからはるか彼方にある。いいかえれば、ここでf
をモジュールに渡しているが、それが定義されたのは、"昔々、はるかなる銀河の果てで"なのだ。ここまでで分かるのは、f
を他のモジュールに渡したり、あるいは、f
への参照をどこかに保存しておいてあとで呼びだしたり、そんなコードを書けるということだ。なんというか、クロージャは、f
があとでいつでも親の環境やn
にアクセスできるように、してくれるのだ。
これは、lablgtkからの実例だ。これは実際はクラスのメソッドだ(まだクラスとオブジェクトについて触れていないが、いまは単に関数の定義と思ってくれればよい)
class html_skel obj = object (self)
...
...
method save_to_channel chan =
let receiver_fn content =
output_string chan content;
true in
save obj receiver_fn
...
end
まずはじめに見てほしいのは、save
関数がメソッドの終わりに呼ばれていて、その2番めの引数が関数(receiver_fn
)であることだ。それは繰り返してreceiver_fn
を呼びだす。その際、保存したいウィジェットからのテキストを伴う。
では、receiver_fn
の定義を見よう。この関数はまさにクロージャだ。それで、環境から、chan
への参照を引いている。
関数の部分適用とカリー化
plus関数を定義しよう。2つの整数をたすだけだ。
# let plus a b =
a + b;;
val plus : int -> int -> int = <fun>
教室の後ろのほうで居眠りをしている連中から、こんな質問がでた。
plus
ってなんですか?plus 2 3
ってなんですか?plus 2
ってなんですか?
質問1は簡単だ。plus
は関数で、2つの引数を整数でとり、整数を返す。型を書くとこうだ:
plus : int -> int -> int
質問2はもっと簡単だ。plus 2 3
は数、整数5
だ。値と型はこうだ:
5 : int
しかし、質問3はどうだろう? plus 2
は間違いか、バグじゃないか?
実は、なんと、そうじゃない。OCamlのトップレベルに打ち込むと、こう言われる:
# plus 2;;
- : int -> int = <fun>
エラーではない。plus 2
は実は関数だと言っているのだ。これは、int
をひとつとり、int
をひとつ返す。これはどんな関数だろう?
まずは、この不思議な関数に名前(f
)をつけてから、実験してみよう。いくつか整数をいれてみる:
# let f = plus 2;;
val f : int -> int = <fun>
# f 10;;
- : int = 12
# f 15;;
- : int = 17
# f 99;;
- : int = 101
工学者がよくやる、例による証明というやつだが、まあいいだろう。ここから、plus 2
は何かに2をたす関数だとわかる。
もともとの定義に戻って、最初の引数(a
)を2で"埋めて"みよう。すると:
let plus 2 b = (* これはOCamlのコードになってないよ! *)
2 + b
なぜplus 2
が何かに2をたす関数なのか、なんとなくわかってもらえるだろう。
これらの式の型を見てもらえば、変な -> 矢印記法を関数の型に使う意味がわかると思う。
plus : int -> int -> int
plus 2 : int -> int
plus 2 3 : int
この過程をカリー化(もしかしてアンカリー化だっ たっけ?どっちがどっちだかよく知らないんだ)という。Haskell Curry にちなんで名付けられた。彼は、lambda計算に関する重要な研究をした。OCamlの背景にある数学的なところは、いまはできるだけ避けようと思う。 それについてはじめると、かなり退屈で、役に立たないチュートリアルになってしまうので、これ以上はこの件に踏み込まないことにする。もっとカリー化につ いて知りたければ、Googleで検索をかけてみてほしい。
先ほどの、double
とmultiply
関数を思い出そう。multiply
はこう定義されていた:
# let multiply n list =
let f x =
n * x in
List.map f list;;
val multiply : int -> int list -> int list = <fun>
なら、double
やtriple
関数を定義するのも、こうすれば、非常に簡単だ:
# let double = multiply 2;;
val double : int list -> int list = <fun>
# let triple = multiply 3;;
val triple : int list -> int list = <fun>
本当にこれで関数である。よって:
# double [1; 2; 3];;
- : int list = [2; 4; 6]
# triple [1; 2; 3];;
- : int list = [3; 6; 9]
部分適用を直接つかう(間にf
関数をはさまずに)こともできる。こうする:
# let multiply n = List.map (( * ) n);;
val multiply : int -> int list -> int list = <fun>
# let double = multiply 2;;
val double : int list -> int list = <fun>
# let triple = multiply 3;;
val triple : int list -> int list = <fun>
# double [1; 2; 3];;
- : int list = [2; 4; 6]
# triple [1; 2; 3];;
- : int list = [3; 6; 9]
上の例では、(( * ) n)
は、( * )
(倍)関数の部分適用になっている。ただし、スペースをいれてやらないと、OCamlが(*
をコメントのはじまりと勘違いしてしまうので注意。
中置演算子をカッコではさむと、関数をつくれる。これまでのplus
関数は、こう定義しても同じである:
# let plus = ( + );;
val plus : int -> int -> int = <fun>
# plus 2 3;;
- : int = 5
カリー化でもっと遊んでみる:
# List.map (plus 2) [1; 2; 3];;
- : int list = [3; 4; 5]
# let list_of_functions = List.map plus [1; 2; 3];;
val list_of_functions : (int -> int) list = [<fun>; <fun>; <fun>]
関数型プログラミングは何に向いているか?
関数型プログラミングは、ほかのプログラミングのテクニックと同じで、便利な道具のひとつであり、自分の懐
にしまっておいて、問題の種類に応じて使うものだ。コールバックにはおあつらえむきで、使い道はいろいろと、GUIから、イベント駆動のループまで、考え
られる。汎用アルゴリズムを表現するのにも非常によい。List.map
は、まさに汎用アルゴリズムで、どの型のリストにでも、関数を適用していける。同様にして、ツリーのための汎用な関数を定義したりもできる。ある種の数値的問題も、関数型プログラミングなら、もっと手早く解けることだろう。(例えば、数学の、関数の微分の数値計算)
純粋関数型プログラミングとは
関数が純粋であるというのは、副作用がないということである。副作用とは、関数が、内部で、なんらかの状態を隠しもつことをいう。strlen
はCの純粋な関数のよい見本だ。strlen
を同じ文字列に呼べば、いつも同じ長さが返ってくる。strlen
の出力(長さ)は、入力(文字列)だけで決まり、他には何も依存しない。Cの多くの関数は、不幸にも、純粋ではない。例えばmalloc
は、同じ数字に呼んでも、同じポインタを返してくれるわけではない。malloc
は、知ってのとおり、膨大な量の内部状態を、隠しもっている(ヒープに確保されたオブジェクト、確保の方法、OSからページをもらう、など)。
OCamlのようなML由来の言語は"ほぼ純粋"である。副作用を、参照や配列の形で使えるけども、大抵は、書いたコードは純粋関数型に落ち着くこ とが多い。言語が、この考え方をすすめるように、できているからだ。Haskellもまた、関数型言語で、純粋関数型だ。OCamlは、より実用的といえ る。純粋でない関数もときには便利だからだ。
純粋関数型にはさまざまな理論的利点がある。利点のひとつは、もし関数が純粋なら、同じ引数で何回も呼んだとき、コンパイラは、実際には関数を一度呼ぶだけでいいことだ。Cでの良い例は:
for (i = 0; i < strlen (s); ++i)
{
// Do something which doesn't affect s.
}
普通にコンパイルしたら、このループはO(n^2^)
である。なぜなら、strlen(s)
は毎回呼ばれ、strlen
には、s
の全体に渡る繰り返しがあるからだ。もしコンパイラが賢くて、strlen
は純粋関数であり、かつ、s
がループで更新されていないことを見つけてくれれば、strlen
の余分な呼出しを省いて、ループをO(n)にしてくれるだろう。コンパイラはこれを本当にやるだろうか?strlen
の場合はyesだが、その他の場合は、多分だめだ。
小さくて純粋な関数を書くことを念頭におくようにすると、再利用可能なコードをボトムアップに重ねていけるようになる。テストは、小さな関数ごとに わけてやっていく。最近流行しているのは、注意深くプログラムを計画してから、トップダウンでやっていく方法だが、著者の見解では、これだとしばしば、プ ロジェクトは失敗するはめになるようだ。
正格 vs 遅延
C由来、ML由来の言語は、正格だ。HaskellとMirandaは、非正格な、あるいは遅延な、言語だ。OCamlはデフォルトでは正格だが、遅延スタイルのプログラミングも、必要におうじてできるようになっている。
正格言語では、関数への引数はつねにはじめに評価される。それから、結果が関数に渡される。たとえば、正格言語では、この呼出しはつねに、0除算エラーになる:
# let give_me_a_three _ = 3;;
val give_me_a_three : 'a -> int = <fun>
# give_me_a_three (1/0);;
Exception: Division_by_zero.
日頃使っている言語では、そう動くのが当たり前で、これ以外の動きなんて考えられないだろう。
遅延な言語では、ちょっとおかしなことが起きる。関数への引数は、関数が実際にそれを使うときだけ、評価される。give_me_a_three
関数は、引数を捨てて、常に3を返すとしよう。なんと、遅延の言語では、さっきの呼出しは、失敗しない。give_me_a_three
ははじめの引数をみないからだ。はじめの引数は評価されないので、0除算は起きない。
遅延の言語は、もっと変なことができる。無限に続くリストを定義できるのだ。そうかといって、実際にリストがどこまで続くかを試すなんてのは、やめたほうがよい。(そのかわりに、最初の10コの要素を取り出すなんてのを、やるとよい。)
OCamlは正格な言語である。しかしLazy
モジュールで、遅延の式を書ける。これが例である。はじめに、1/0
を遅延の式で作ってみる:
# let lazy_expr = lazy (1/0);;
val lazy_expr : int lazy_t = <lazy>
この遅延の式の型が、int lazy_t
になるのに注意。
give_me_a_three
は
'a
(型はなんでもいい)をとるので、遅延の式を関数に渡してやることができる。
# give_me_a_three lazy_expr;;
- : int = 3
遅延の式を評価するには、Lazy.force
関数を使わねばならない。
# Lazy.force lazy_expr;;
Exception: Division_by_zero.
Boxed vs. unboxed 型
関数型言語の話をしているとき、よく聞く用語に、"boxed"がある。私はこの用語をはじめに聞いたとき にはかなりとまどったが、よくよく知れば、"boxed"と"unboxed"の区別というのは、きわめて簡単で、もし、CやC++,Javaを以前に 使ったことがあれば、たちどころにわかる。(Perlでは、すべてboxedだ。)
考え方として、boxedオブジェクトというのは、Cでいえばmalloc
で(あるいはC++のnew
でも同じ)ヒープに確保されたオブジェクトと思えばよい。そして、ポインタで参照される。このCのプログラムの例を見てみよう:
#include <stdio.h>
void
printit (int *ptr)
{
printf ("the number is %d\n", *ptr);
}
void
main ()
{
int a = 3;
int *p = &a;
printit (p);
}
変数a
は、スタックに確保され、明らかに、unboxedだ。
関数printit
は、boxedの整数をとり、それをプリントする。
下のダイアグラムは、unboxedの整数の配列(上) 対 boxedのそれ(下)を示している。
誰が見たって、unboxedの整数の配列のほうが、boxedの整数の配列なんかより、よっぽど速い。その上、unboxedオブジェクトの配列だと、確保が一気にできるので、ガーベジコレクションが単純になり、やはり速い。
CやC++なら、上の2つの型の配列のどちらでも、構築するのに支障はないはずだ。Javaでは、2つの型があり、int
は、unboxedで、Integer
はboxedだ。これだとやっぱり、効率は悪い。OCamlでは、基本の型はすべて、unboxedだ。