2019年10月6日
[ 前の資料 | 講義ホームページ・トップ | 次の資料 ]
2019年度用に改訂予定
\(\sum_{i=n}^m x_i\) という記法は(実)数列 \(\{x_i\}\) の第\(n\)項から第\(m\)項までの和を表す.この \(\sum\) をひとつの演算子だと捉えようとすると,これは自然数 \(n\), \(m\) と数列 \(\{x_i\}\) に作用する演算子,もしくは,関数と考えることができる.数列を自然数 \(i\) から実数への関数と考えれば,\(\sum\) は関数を引数とする関数である.プログラミングにおいて,「関数を引数とする関数」が実現できたり,関数を変数に格納することができたりと,関数が(整数や文字列などの通常の)データと同様に1扱えることを指して「関数が 第一級の値(first-class value) である」といったりする.
また,概念的には「『関数を引数とする関数』を引数とする関数」などが考えられるが,この「複雑さ」に特に制限が設けられていない時,プログラミング言語が 高階関数(higher-order function) をサポートしている,高階プログラミングができる,などという.
この「階(order)」とは,関数の「複雑さ」を示す度合いで,
関数が第一級の値であることは「データの操作」の受け渡しが許されている,ということとも考えられる.これはオブジェクトのような「データとその操作をいっしょにしたもの」が受け渡しできるオブジェクト指向言語では,ある意味当たり前にできていることである.そのため,明示的に関数の概念が現れないオブジェクト指向言語でも,実質的には高階関数が利用できると考えられる.
OCaml も含め,一般に関数型言語は高階関数が書きやすく設計されている.
最初の例である \(\sum\) を考えてみる.(ただし,煩雑にならないよう,最初の項は第0項で固定とする.) 関数 sigma
は,整数上の関数 f
と,自然数 n
を引数として,f(n) + f(n-1) + ... + f(0)
を計算する.以下が sigma
の定義である.
f
は,n
と同様に,特に特別な記法もなくふつうにパラメータとして書けばよい.関数本体では,f 0
のように,他の let
で定義された関数と同様に使われている.sigma
の型は例によって型推論機能が答えてくれる.
val sigma : (int -> int) * int -> int = <fun>
第1引数が int -> int
型の値,すなわち,整数から整数への関数であることが示されている.->
は *
よりも結合が弱いので ()
が必要となる.(この括弧がなかった時の読み方・意味は後でふれることにする.)
この関数を呼ぶには,引数に定義済の関数の名前を与えてやればよい.
関数が第一級の値であるような言語のうち多くでは,名前をつけずに関数を表す記法が用意されている.このような名前のない関数を 匿名関数(anonymous function) と呼ぶ.OCaml では匿名関数は fun〈パラメータ〉-> 〈式〉
という形で表す.以下が,上の a
b
の定義を匿名関数を使って書いたものである.
fun n -> n*n
で「n
を受け取って n * n
を返す関数」を意味する.
fun
はできるだけ伸びるので,しばしば括弧が必要となる.上の例で括弧を省略すると ->
の後が n * n , 20
ということになって,n * n
と 20
の組を返す関数になってしまう.(組のことはほとんど説明していない.あしからず.)
この記法を使うと,cube
を以下のように定義することもできる.
実は,let f x = ...
という記法は let f = fun x -> ...
の略記なのである.
これまで複数の引数をとる関数は let f(x,y) = ...
のように,複数の引数を組にしてとるように書いてきた.実は,高階関数,特に,関数を返す関数を使うと,複数引数関数を,1引数関数の組み合わせで表現することができる.このテクニックを カリー化(Currying) (カリーは人名),またそうして表現された関数を カリー化関数(Curried function) と呼ぶ.
例を見てみよう,以下の greeting
は,性別 gen
と名前を表す文字列 name
を受け取って,挨拶文(敬称が性別で違う)を返す簡単な関数である.
type gender = Male | Female
let greeting(gen, name) =
match gen with
Male -> "Hello, Mr. " ^ name
| Female -> "Hello, Ms. " ^ name
let g1 = greeting(Male, "Poirot")
let g2 = greeting(Female, "Marple")
カリー化のアイデアは2引数関数を,「最初の引数を受け取って,『第2の引数を受け取って結果を返す関数』を返す関数」として表現する,ということである.一般に,\(n\)引数関数なら「最初の引数を受け取って『残りの引数を受け取って結果を返す \(n-1\)引数関数』を返す関数」と表現される.以下はカリー化された greeting
である.
let curried_greeting gen = fun name ->
match gen with
Male -> "Hello, Mr. " ^ name
| Female -> "Hello, Ms. " ^ name
この関数の型は以下のようになる:
この型は gender -> (string -> string)
と同じ(->
は右結合)で,gender
を受け取ると,string -> string
を返す関数であることが型から読み取れる.
カリー化された関数を呼ぶ時は,まず,性別を与えると,(名前を受け取って挨拶分を返す)関数が返ってくるので,それを呼ぶ,という手順になる.
let greeting_for_men = curried_greeting Male
let greeting_for_women = curried_greeting Female
let g1 = greeting_for_men "Poirot"
let g2 = greeting_for_women "Marple"
curried_greeting x
は,関数 fun name -> ...
を返すわけだが,この時 gen
が,渡した x
に固定されたような関数が返ってきている,ということに注目してもらいたい.だからこそ,次の引数である文字列が渡された時に,最初の引数によって異なる挙動を示している.
一般に,(匿名)関数本体では,パラメータ以外の変数が現れるわけだが,その値は,fun
が評価された時(fun
に実行が到達した時)に固定される.関数が呼び出された時には,その以前に固定された値を使って,本体の計算が行われる.それゆえ,一般に関数を(コンパイラなどの言語処理系のレベルで)表現するためには,関数のコード(fun
以下の情報)に加え,パラメータ以外の(固定された)変数の値を記録しておく必要がある.それらをまとめたものを 関数閉包(function closure) と呼ぶ.これは言語処理系レベルで第一級関数を実現するための技法である.
curried_greeting
や g1
, g2
の別定義cube
の別定義でみたように,定義のための =
の直後の fun x ->
は =
の左側に移せるので,curried_greeting
も fun
キーワードを使わずに以下のように定義することができる.
let curried_greeting gen name =
match gen with
Male -> "Hello, Mr. " ^ name
| Female -> "Hello, Ms. " ^ name
また,呼び出す際にも,最初の引数を渡したものに,いちいち名前をつけずに,以下のように呼び出すこともできる.
しかも,g2
のように左側の括弧は省略できる(関数適用は左結合)ので,こう書くと,()
を使わずに2引数関数が書けているように見えるだろう.
カリー化された複数引数関数は,全ての引数を一度に与えて呼び出すことが多いが,greeting_for_men
のように,最初の方の一部の引数だけを与えて,引数の一部の値を固定した関数を作ることもしばしばある.このような一部の引数だけを渡すことを 部分適用(partial application) という.後の方の引数を固定するのはOCamlでは少し面倒なので,カリー化を行う際には,固定されやすい引数を最初にもってくることが多い.
いつもの(整数を格納した)2分木を考える.
type tree =
Lf
| Br of {
left: tree;
value: int;
right: tree;
}
let t1 = Br {left = Lf; value = 10; right = Lf}
let t2 = Br {left = Lf; value = 25; right = Lf}
let t3 = Br {left = t1; value = 15; right = t2}
let t4 = Br {left = Lf; value = 60; right = Lf}
let t5 = Br {left = Lf; value = 48; right = t4}
let t6 = Br {left = t3; value = 30; right = t5}
データ構造に典型的ないくつかの高階関数を見ていこう.
map
は,データ構造に格納された各データ(この2分木の場合は branch の整数)に関数(パラメータ) f
を適用して得られるような別の2分木を返す操作である.
let rec treemap f t =
match t with
Lf -> Lf
| Br {left=l; value=v; right=r} ->
Br {left = treemap f l;
value = f v;
right = treemap f r}
(* Let's double the values in t6 keeping its shape *)
let t7 = treemap (fun n -> n * 2) t6
fold
は畳み込みとも呼ばれる.データ構造の各コンストラクタ \(C_i\) (\(n_i\) 引数)を \(n_i\) 関数 \(f_i\) に置き換えて「解釈」し,値を得る関数である.(0引数コンストラクタには定数を割り当てる.)
(* Replace Lf with e and Br with f *)
let rec treefold e f t =
match t with
Lf -> e
| Br {left=l; value=v; right=r} ->
f (treefold e f l)
v
(treefold e f r)
(* Interpret Lf as 0 and Br as addition *)
let s6 = treefold 0 (fun l v r -> l + v + r) t6
let s7 = treefold 0 (fun l v r -> l + v + r) t7
(* Conversion to a string can be written in terms of fold *)
let str6 = treefold "leaf" (fun l v r -> "branch(" ^ l ^ ", " ^ (string_of_int v) ^ ", " ^ r ^ ")") t6
let str7 = treefold "leaf" (fun l v r -> "branch(" ^ l ^ ", " ^ (string_of_int v) ^ ", " ^ r ^ ")") t7
メソッドを関数と考えると,オブジェクトは複数のメソッドに名前をつけたレコードと考えることができる.特に,メソッドをひとつだけ持つオブジェクトを考えれば,第一級関数を表現することができる.
まず,関数の型毎に(メソッドがひとつだけの)インターフェースを用意する.インターフェースの名前は引数・返値の型を表す名前にしておく.メソッドの名前はなんでもよいが,ここでは Java のライブラリにある Function
という(ジェネリック)インターフェースにあわせ apply
とする.(Function
などのライブラリのインターフェースについては,後述する.)
そして,そのこのインターフェースを implements
したクラスを作ることで関数を表現する.整数を2倍する関数であれば,以下のようになる.インスタンス変数は特に必要ない.
public class Dbl implements IntToInt {
// no instance variables
public Dbl() {
// nothing to initialize
}
public int apply(int n) { return n * 2; }
}
例えば,この「関数」を作って,呼び出すには以下のようにすることになる.
さて,この手法を使って,2分木の map
や fold
をプログラムしてみよう.
今までの話を総合すれば特筆すべきことはない.まず,Tree
インターフェースには map
の宣言を追加する.引数が上で定義した整数上の関数を表すインターフェースになる.
そして,Leaf
と Branch
の各クラスに,処理を追加する.Branch
では関数オブジェクト f
を呼び出して新しい木に格納する整数を計算する.
// Branch クラスに追加
public Tree map(IntToInt f) {
Tree newLeft = left.map(f);
Tree newRight = right.map(f);
int newVal = f.apply(v);
return new Branch(newLeft, newVal, newRight);
}
以下が,この map
を使った例となる.
// Main クラスより
Tree t1 = new Branch(new Leaf(), 10, new Leaf());
Tree t2 = new Branch(new Leaf(), 25, new Leaf());
Tree t3 = new Branch(t1, 15, t2);
Tree t4 = new Branch(new Leaf(), 60, new Leaf());
Tree t5 = new Branch(new Leaf(), 48, t4);
Tree t6 = new Branch(t3, 30, t5);
System.out.println(t6);
Tree t7 = t6.map(new Dbl());
System.out.println(t7);
Br
を置き換える3引数関数のためにインターフェースを新しく用意する必要があるが,その他は特筆すべきところはない.インターフェース ThreeIntsToInt
が3つの整数から整数への関数を表すインターフェース,Sum3
が与えられた3整数の和を返す関数オブジェクトのクラス Sum3
である.
public class Sum3 implements ThreeIntsToInt {
// no instance variables
public Sum3() {
// nothing to initialize
}
public int apply(int n, int m, int p) { return n + m + p; }
}
// Branch クラスに追加
public int fold(int e, ThreeIntsToInt f) {
int l = left.fold(e, f);
int r = right.fold(e, f);
return f.apply(l, v, r);
}
その1の実装では,leaf と branch のために別の引数を用意したが,これらをひとつのオブジェクトにまとめることも可能である.実装その2として,
を持つオブジェクトを受け取る形で書いてみよう.このオブジェクトは,木の場合分け処理を表現していることから,インターフェース名を CaseForTree
としている.
public interface Tree {
...
int fold(int e, ThreeIntsToInt f);
int fold(CaseForTree c); // Overloading!
}
public class SumTree implements CaseForTree {
// no instance variables
public SumTree() {
// nothing to initialize
}
public int caseLeaf() { return 0; }
public int caseBranch(int n, int m, int p) { return n + m + p; }
}
// Branch クラスに追加
public int fold(CaseForTree c) {
int l = left.fold(c);
int r = right.fold(c);
return c.caseBranch(l, v, r);
}
CaseForTree
に並べたメソッドの名前を caseLeaf
,caseBranch
としたところから気付くかもしれないが,この fold
の実装は,ビジターパターンによく似ている.だいたい,fold
メソッドが accept
に対応していると考えられるが,よく見てみると以下のような違いがある.
caseBranch
メソッドは,訪れた Branch
オブジェクトのインスタンス変数の値を引数として,どの部分木に再帰呼出しを行うかも caseBranch
メソッド内で決定しているfold
では,再帰呼出しは fold
メソッドの中で先に行ってしまい,その再帰呼出しの結果を caseBranch
メソッドに渡している.fold
の場合は再帰呼出しの方法が固定されているので,このような定義になる(のが自然である).さて,ここまで関数を表現するためにいちいちクラスを書いてきたが,これらの実装の問題点は,
のがかなり煩雑である,という点である.ひとつめの問題は,ジェネリクスを用いることである程度解決する.例えば,ライブラリ java.util.function
にある2 Function<T,R>
というジェネリックインターフェースには R apply(T x);
というメソッドが宣言されている.よって,上の IntToInt
のようなインターフェースは Function<Integer, Integer>
と書けばよい.(int
を Integer
に変える必要はある.) 3 また,ふたつめの問題は,現在の Java では「ラムダ式」で解決することができる.「ラムダ式」は OCaml の fun
記法とほぼ同じアイデアで匿名関数を表すための記法である.4
Java でのラムダ式の一番基本的な記法は,
という形を取る.これで\(n\)引数を受け取って〈文の並び〉を実行する匿名関数として使うことができる.return
された値が返り値となる.例えば,上のSum3
は,クラスを書かずとも,ラムダ式を使って以下のようにして作ることができる.
ラムダ式において返り値の型は宣言しない(できない).ラムダ式はメソッドをひとつしか持たないインターフェースが期待される文脈でしか使うことができない.ここで「文脈」といっているのは,ThreeIntsToInt
型の f
に代入しようとしている,というプログラム上の文脈のことである.f
の型から,この関数は apply
メソッドの実装であると解釈してもらえるわけである.
上の記法以外にも,以下の表のような様々な短縮形が用意されている.
記法 | 備考 |
---|---|
(T1 x1,...,Tn xn) -> { ... } |
\(n\)引数で,... の文(の列)を実行する.return された値が返る |
(x1,...,xn) -> { ... } |
パラメータの型宣言は省略できる |
x -> { ... } |
1引数の場合,括弧すら省略できる |
(T1 x1,...,Tn xn) -> 〈式〉 |
中括弧の中が単一の return 〈式〉; の場合,〈式〉だけでよい |
(x1,...,xn) -> 〈式〉 |
型宣言の省略 |
x -> 〈式〉 |
(ふつうは)文脈側にあるインターフェースから型が決まるので,パラメータの型宣言は特にしなくても型推論が行われる.(ちなみに,型宣言のないパラメータと型宣言のあるパラメータを混ぜることはできない.(n, int m, p) -> ...
のようなものはエラーになる.5)
上の map
や fold
(その1) を使う例をラムダ式(の省略形)を使って書き直すと以下のようになる.
ThreeIntsToInt f = (n, m, p) -> n + m + p;
System.out.println(t6.fold(0, f));
Tree t8 = t6.map(n -> n * 2);
System.out.println(t7);
System.out.println(t7.fold(0, f));
Java のラムダ式は,結局のところオブジェクトである.よって,ラムダ式を呼び出す特殊な構文はなく,呼び出すためには必ずメソッド呼び出しを経由する必要がある.つまり,クラスを定義せずにオブジェクトを作る特殊な記法,程度に理解しておくべきである.コンパイルした結果を見ると,実はラムダ式に対応するクラスが自動で生成されている.また,(本講義ではこれ以上深くはふれないが)ラムダ式の使用に関するいくつかの規則も,ラムダ式がクラス定義+new
の略記であることを知っておくて理解しやすいだろう.
2018年版ではC言語を後回しにしているので,ひとまず,以下は説明しない.
C言語には OCaml のような一般的な高階関数を扱う機能はない.そもそも(GCCの独自拡張を除くと)関数の中で関数を定義できないので,カリー化関数を表現したかったら,自分で関数閉包を作ったり,関数閉包を呼び出す仕組みを作ることになる.また,匿名関数のための仕組みはない.それでも,上で紹介したような高階関数を使ったプログラミングが「ある程度」可能であることを紹介する.
関数ポインタは,概念としては関数を指すためのポインタで,*
を使って関数を参照して呼び出すことができる.まず,\(\sum\) の例を見てみよう.
int sigma(int (*f)(int), int n) {
if (n < 1) {
return (*f)(0);
} else {
return (*f)(n) + sigma(f, n - 1);
}
}
int square(int n) {
return n * n;
}
int cube(int n) {
return n * n * n;
}
int main(void) {
printf("1^2 + ... + 20^2 = %d\n", sigma(square, 20));
printf("1^3 + ... + 20^3 = %d\n", sigma(cube, 20));
return 0;
}
C言語の関数ポインタまわりでややこしいのは変数の型宣言の構文である.後置された (int)
が整数を1つ引数に取る関数であること,f
の前の *
が f
がポインタであることを示している.
main
関数にあるように,関数へのポインタを他の関数に渡す時には関数名だけを書けば,&
をつけなくても暗黙のうちにポインタとして扱われる.また,呼び出しの際にはポインタの参照 *f
をしているが,これも括弧が必要である.この括弧がないと,「関数 f
を呼んだ結果(f(n)
)であるところのポインタが指す先を *
参照する」という意味になってしまう.(C言語では関数呼び出しも後置演算子扱いで,後置演算子は常に前置演算子よりも優先される.)
(参考: http://www.unixwiz.net/techtips/reading-cdecl.html など,解説記事多数あり.)
C言語の型宣言は,識別子の前後にいろいろくっついて型を表すこともあり,読み方がややこしい.
f
なら "f
is ..." と読み始める()
(や []
) を優先して読むf
が何かがわかる.記法 | 読み方 | 備考 |
---|---|---|
(...) (後置) |
a function returning | 括弧内は引数の型をカンマで並べる |
[...] (後置) |
an array of | ... には配列の要素数を書いてもよい |
* (前置) |
a pointer to |
例えば int (*f)(int)
は f
is a pointer to a function (taking an int
) returning int
と読むことができる.*f
のまわりの括弧がないと,f
is a function returning a pointer to int
となって,違う意味になってしまう.
また,関数は「関数へのポインタ」を返すことはできるが「関数そのもの」を返すことはできないため,OCaml での f: T1 -> T2 -> T3
のような(T1
型の引数を受け取ったら,「T2
型の引数を受け取りT3
型の値を返す関数」を返す)関数を定義したい場合は,「T1
型の引数(仮にx
としよう)を受け取ったら『T2
を受け取りT3
を返す関数』へのポインタを返す関数」として定義す.この場合,f
の定義は T3 (*f(T1 x))(T2) { ...}
のように書く.(上の読み方との対応を取ってみよ.)
関数の受け渡しは必ずポインタでされることから,いくつかそれを利用した表記揺れが存在する.
f
の宣言につけた *
は省略して,と書いてもよい.が,これは関数パラメータに限られ,{}
内の局所変数の場合は省略できないので,この講義では常に *
をつける.
関数ポインタを使った呼び出し (*f)(n)
も,*
を省略して f(n)
と書いてよい.f
がポインタであることを意識・明示するために,この講義では常に *
をつける.
関数のポインタを取得する際に &
をつけて (sigma(&cube,20)
のように書いて)もよい.上の点とは一貫していないようにも思えるが,この講義では &
はつけない.配列(これも関数と同様受け渡しできるのはポインタだけである)の場合,配列名が先頭要素へのポインタに自動変換されるのと揃えている.
記法さえ飲み込めば map
や fold
を書くのは難しくない.
struct tree *map(int (*f)(int), struct tree *t) {
if (t->tag == LEAF) {
return newleaf();
} else /* t->tag == BRANCH */ {
struct branch *b = &t->dat.br;
struct tree *newleft = map(f, b->left);
struct tree *newright = map(f, b->right);
int newvalue = (*f)(b->value);
return newbranch(newleft, newvalue, newright);
}
}
int fold(int e, int (*f)(int, int, int), struct tree *t) {
if (t->tag == LEAF) {
return e;
} else /* t->tag == BRANCH */ {
struct branch *b = &t->dat.br;
int l = fold(e, f, b->left);
int r = fold(e, f, b->right);
return f(l, b->value, r);
}
}
int add3(int a, int b, int c) {
return a + b + c;
}
int dbl(int a) {
return a * 2;
}
int main(void) {
// Construct a tree
struct tree *t1 = newbranch(newleaf(), 10, newleaf());
struct tree *t2 = newbranch(newleaf(), 25, newleaf());
struct tree *t3 = newbranch(t1, 15, t2);
struct tree *t4 = newbranch(newleaf(), 60, newleaf());
struct tree *t5 = newbranch(newleaf(), 48, t4);
struct tree *t6 = newbranch(t3, 30, t5);
print_tree(t6); printf("\n");
int s6 = fold(0, add3, t6);
printf("the sum of integers in t6 is %d\n", s6);
struct tree *t7 = map(dbl, t6);
print_tree(t7); printf("\n");
int s7 = fold(0, add3, t7);
printf("the sum of integers in t7 is %d\n", s7);
return 0;
}
[ 前の資料 | 講義ホームページ・トップ | 次の資料 ]
「同様に」の意味は厳密ではないが,通常,変数に格納したり,他の関数・手続・メソッドに受け渡しできる,実行時に生成できたりすることを指す.↩
使うには `import java.util.function.*;' を各ファイル冒頭に置くこと↩
他に2引数関数のための BiFunction<T,U,R>
というインターフェース(T
と U
が引数の型を表す)もあるが,3引数以上の場合は用意されていないようだ.↩
「ラムダ」というのはギリシャ文字の \(\lambda\) のことである.ラムダ計算(\(\lambda\)-calculus) という計算のモデルの理論で,\(x\) を引数とし(\(x\) を含む)〈式〉を計算して返す関数を \(\lambda x.〈式〉\) という形式で表すことに由来している.例えば,「1を足す関数」は \(\lambda x. x + 1\) と書く.プログラミング言語によっては lambda
が匿名関数のキーワードになっている場合もある.(Lisp など)↩
Java言語仕様Java SE8版 15.27節↩
Copyright 五十嵐 淳, 2016, 2017, 2018, 2019