関数型プログラミング

(Redirected from ja/functional_programming)

関数型プログラミングとは?

チュートリアルも、かなり進んできたが、まだ関数型プログラミングについて深く考えたことがない。これまでに教えた機能をあまさず使うことを考えれば - 豊富なデータ型、パターンマッチング、型推論、入れ子関数 - これはもう、"超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
  ;;

よって:

# 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

まずはじめに見てほしいのは、save関数がメソッドの終わりに呼ばれていて、その2番めの引数が関数(receiver_fn)であることだ。それは繰り返してreceiver_fnを呼びだす。その際、保存したいウィジェットからのテキストを伴う。

では、receiver_fnの定義を見よう。この関数はまさにクロージャだ。それで、環境から、chanへの参照を引いている。

関数の部分適用とカリー化

plus関数を定義しよう。2つの整数をたすだけだ。

let plus a b =
  a + b
  ;;

教室の後ろのほうで居眠りをしている連中から、こんな質問がでた。

  1. plusってなんですか?
  2. plus 2 3ってなんですか?
  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
  ;;

なら、doubleやtriple関数を定義するのも、こうすれば、非常に簡単だ:

let double = multiply 2;;
let triple = multiply 3;;

本当にこれで関数である。よって:

# 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(n2) である。なぜなら、strlen(s)は毎回呼ばれ、strlenには、sの全体に渡る繰り返しがあるからだ。もしコンパイラが賢くて、strlenは純粋関数であり、かつ、sがループで更新されていないことを見つけてくれれば、strlenの余分な呼出しを省いて、ループをO(n)にしてくれるだろう。コンパイラはこれを本当にやるだろうか?strlenの場合はyesだが、その他の場合は、多分だめだ。

小さくて純粋な関数を書くことを念頭におくようにすると、再利用可能なコードをボトムアップに重ねていけるようになる。テストは、小さな関数ごとにわけてやっていく。最近流行しているのは、注意深くプログラムを計画してから、トップダウンでやっていく方法だが、著者の見解では、これだとしばしば、プロジェクトは失敗するはめになるようだ。

正格 vs 遅延

C由来、ML由来の言語は、正格だ。HaskellとMirandaは、非正格な、あるいは遅延な、言語だ。OCamlはデフォルトでは正格だが、遅延スタイルのプログラミングも、必要におうじてできるようになっている。

正格言語では、関数への引数はつねにはじめに評価される。それから、結果が関数に渡される。たとえば、正格言語では、この呼出しはつねに、0除算エラーになる:

give_me_a_three (1/0);;

日頃使っている言語では、そう動くのが当たり前で、これ以外の動きなんて考えられないだろう。

遅延な言語では、ちょっとおかしなことが起きる。関数への引数は、関数が実際にそれを使うときだけ、評価される。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のそれ(下)を示している。

boxedarray.png

誰が見たって、unboxedの整数の配列のほうが、boxedの整数の配列なんかより、よっぽど速い。その上、unboxedオブジェクトの配列だと、確保が一気にできるので、ガーベジコレクションが単純になり、やはり速い。

CやC++なら、上の2つの型の配列のどちらでも、構築するのに支障はないはずだ。Javaでは、2つの型があり、intは、unboxedで、Integerはboxedだ。これだとやっぱり、効率は悪い。OCamlでは、基本の型はすべて、unboxedだ。