2016年度「プログラミング言語」配布資料 (11)

五十嵐 淳 (京都大学大学院情報学研究科 通信情報システム専攻)

2017年1月24日

[ 前の資料 | 講義ホームページ・トップ | 次の資料 ]

高階関数

\(\sum_{i=n}^m x_i\) という記法は(実)数列 \(\{x_i\}\) の第\(n\)項から第\(m\)項までの和を表す．この \(\sum\) をひとつの演算子だと捉えようとすると，これは自然数 \(n\), \(m\) と数列 \(\{x_i\}\) に作用する演算子，もしくは，関数と考えることができる．数列は自然数 \(i\) から実数への関数であるので，\(\sum\) は関数を引数とする関数である．プログラミングにおいて，このような「関数を引数とする関数」を実現したり，関数を変数に格納したり，関数が(整数や文字列などの通常の)データと同様に1扱えることを指して「関数が 第一級の値(first-class value) である」といったりする．

また，概念的には「『関数を引数とする関数』を引数とする関数」などが考えられるが，この「複雑さ」に特に制限が設けられていない時，プログラミング言語が 高階関数(higher-order function) をサポートしている，高階プログラミングができる，などという．

この「階」とは，関数の「複雑さ」を示す度合いで，

  • 一階の関数 (first-order functions) … 整数，文字列などの基本的データ，基本的データのみで構成されるレコードなどを引数とする関数
  • 二階の関数 (second-order functions) … 一階の関数を引数とする関数(\(\sum\)など)
  • \(n\)階の関数 (\(n\)-th-order functions) … \(n-1\)階の関数を引数とする関数
    と定義される．

関数が第一級の値であることは「データの操作」の受け渡しが許されている，ということとも考えられる．これはオブジェクトのような「データとその操作をいっしょにしたもの」が受け渡しできるオブジェクト指向言語では，ある意味当たり前にできていることである．そのため，明示的に関数の概念が現れないオブジェクト指向言語でも，実質的には高階関数が利用できると考えられる．

高階関数 in OCaml

OCaml も含め，一般に関数型言語は高階関数が書きやすく設計されている．

関数を引数とする関数

最初の例である \(\sum\) を考えてみる．(ただし，煩雑にならないよう，最初の項は第0項で固定とする．)
関数 sigma は，整数上の関数 f と，自然数 n を引数として，f(n) + f(n-1) + ... + f(0) を計算する．以下が sigma の定義である．

1
2
3

let rec sigma(f, n) =
  if n < 1 then f 0
  else f n + sigma(f, n-1)

f は，n と同様に，特に特別な記法もなくふつうにパラメータとして書けばよい．関数本体では，f 0 のように，他の let で定義された関数と同様に使われている．sigma の型は例によって型推論機能が答えてくれる．

val sigma : (int -> int) * int -> int = <fun>

第1引数が int -> int 型の値，すなわち，整数から整数への関数であることが示されている．-> は * よりも結合が弱いので () が必要となる．(この括弧がなかった時の読み方・意味は後でふれることにする．)

この関数を呼ぶには，引数に定義済の関数の名前を与えてやればよい．

1
2
3
4
5

let square n = n * n
let cube n = n * n * n

let a = sigma(square, 20)
let b = sigma(cube, 20)

匿名関数

関数が第一級の値であるような言語のうち多くでは，名前をつけずに関数を表す記法が用意されている．このような名前のない関数を 匿名関数(anonymous function) と呼ぶ．OCaml では匿名関数は fun〈パラメータ〉-> 〈式〉 という形で表す．以下が，上の a b の定義を匿名関数を使って書いたものである．

1
2
3

(* anonymous functions *)
let c = sigma ((fun n -> n*n), 20)
let d = sigma ((fun n -> n*n*n), 20)

fun n -> n*n で「n を受け取って n * n を返す関数」を意味する．

fun はできるだけ伸びるので，しばしば括弧が必要となる．上の例で括弧を省略すると -> の後が n * n , 20 ということになって，n * n と 20 の組を返す関数になってしまう．(組のことはほとんど説明していない．あしからず．)

この記法を使うと，cube を以下のように定義することもできる．

let cube = fun n -> n * n * n

実は，let f x = ... という記法は let f = fun x -> ... の略記なのである．

カリー化による複数引数関数の表現

これまで複数の引数をとる関数は let f(x,y) = ... のように，複数の引数を組にしてとるように書いてきた．実は，高階関数，特に，関数を返す関数を使うと，複数引数関数を，1引数関数の組み合わせで表現することができる．このテクニックを カリー化(Currying) (カリーは人名)，またそうして表現された関数を カリー化関数(Curried function) と呼ぶ．

例を見てみよう，以下の greeting は，性別 gen と名前を表す文字列 name を受け取って，挨拶文(敬称が性別で違う)を返す簡単な関数である．

1
2
3
4
5
6
7
8
9

type gender = Male | Female

let greeting(gen, name) =
  match gen with
    Male -> "Hello, Mr. " ^ name
  | Female -> "Hello, Ms. " ^ name
  
let g1 = greeting(Male, "Igarashi")
let g2 = greeting(Female, "Koike")

カリー化のアイデアは2引数関数を，「最初の引数を受け取って，『第2の引数を受け取って結果を返す関数』を返す関数」として表現する，ということである．一般に，\(n\)引数関数なら「最初の引数を受け取って『残りの引数を受け取って結果を返す \(n-1\)引数関数』を返す関数」と表現される．以下はカリー化された greeting である．

1
2
3
4

let curried_greeting gen = fun name ->
  match gen with
    Male -> "Hello, Mr. " ^ name
  | Female -> "Hello, Ms. " ^ name

この関数の型は以下のようになる:

val : curried_greeting : gender -> string -> string = <fun>

この型は 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 "Igarashi"
let g2 = greeting_for_women "Koike"

curried_greeting x は，関数 fun name -> ... を返すわけだが，この時 gen が，渡した x に固定されたような関数が返ってきている，ということに注目してもらいたい．だからこそ，次の引数である文字列が渡された時に，最初の引数によって異なる挙動を示している．

一般に，(匿名)関数本体では，パラメータ以外の変数が現れるわけだが，その値は，fun が評価された時(fun に実行が到達した時)に固定される．関数が呼び出された時には，その以前に固定された値を使って，本体の計算が行われる．それゆえ，一般に関数を(コンパイラなどの言語処理系のレベルで)表現するためには，関数のコード(fun 以下の情報)に加え，パラメータ以外の(固定された)変数の値を記録しておく必要がある．それらをまとめたものを 関数閉包(function closure) と呼ぶ．これは言語処理系レベルで第一級関数を実現するための技法である．

  • curried_greeting や g1, g2 の別定義

cube の別定義でみたように，定義のための = の直後の fun x -> は = の左側に移せるので，curried_greeting も fun キーワードを使わずに以下のように定義することができる．

1
2
3
4

let curried_greeting gen name =
  match gen with
    Male -> "Hello, Mr. " ^ name
  | Female -> "Hello, Ms. " ^ name

また，呼び出す際にも，最初の引数を渡したものに，いちいち名前をつけずに，以下のように呼び出すこともできる．

let g1 = (curried_greeting Male) "Igarashi"
let g2 = curried_greeting Female "Koike"

しかも，g2 のように左側の括弧は省略できる(関数適用は左結合)ので，こう書くと，() を使わずに2引数関数が書けているように見えるだろう．

カリー化された複数引数関数は，全ての引数を一度に与えて呼び出すことが多いが，greeting_for_men のように，最初の方の一部の引数だけを与えて，引数の一部の値を固定した関数を作ることもしばしばある．このような一部の引数だけを渡すことを 部分適用(partial application) という．後の方の引数を固定するのは少し面倒なので，カリー化を行う際には，固定されやすい引数を最初にもってくることが多い．

2分木のための高階関数

いつもの(整数を格納した)2分木を考える．

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

map は，データ構造に格納された各データ(この2分木の場合は branch の整数)に関数(パラメータ) f を適用して得られるような別の2分木を返す操作である．

1
2
3
4
5
6
7
8
9
10

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

fold は畳み込みとも呼ばれる．データ構造の各コンストラクタ \(C_i\) (\(n_i\) 引数)を \(n_i\) 関数 \(f_i\) に置き換えて「解釈」し，値を得る関数である．(0引数コンストラクタには定数を割り当てる．)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(* 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

オブジェクトを使った高階関数プログラミング in Java

オブジェクト≒関数のレコード

メソッドを関数と考えると，オブジェクトは複数のメソッドに名前をつけたレコードと考えることができる．特に，メソッドをひとつだけ持つオブジェクトを考えれば，第一級関数を表現することができる．

まず，関数の型毎に(メソッドがひとつだけの)インターフェースを用意する．インターフェースの名前は引数・返値の型を表す名前にしておく．メソッドの名前はなんでもよいが，ここでは Java のライブラリにある Function という(ジェネリック)インターフェースにあわせ apply とする．(Function などのライブラリのインターフェースについては，後述する．)

1
2
3

public interface IntToInt {
    int apply(int x);
}

そして，そのこのインターフェースを implements したクラスを作ることで関数を表現する．整数を2倍する関数であれば，以下のようになる．インスタンス変数は特に必要ない．

1
2
3
4
5
6
7
8
9

public class Dbl implements IntToInt {
    // no instance variables

    public Dbl() {
        // nothing to initialize
    }

    public int apply(int n) { return n * 2; }
}

例えば，この「関数」を作って，呼び出すには以下のようにすることになる．

1
2

IntToInt f = new Dbl();
int x = f.apply(3);   // x = 6

さて，この手法を使って，2分木の map や fold をプログラムしてみよう．

map

今までの話を総合すれば特筆すべきことはない．まず，Tree インターフェースには map の宣言を追加する．引数が上で定義した整数上の関数を表すインターフェースになる．

1
2
3
4

public interface Tree {
    Tree map(IntToInt f);
    ...
}

そして，Leaf と Branch の各クラスに，処理を追加する．Branch では関数オブジェクト f を呼び出して新しい木に格納する整数を計算する．

1
2
3
4

    // Leaf クラスに追加
    public Tree map(IntToInt f) {
        return new Leaf();
    }
1
2
3
4
5
6
7

    // 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 を使った例となる．

1
2
3
4
5
6
7
8
9
10
11
12

        // 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);

fold その1

Br を置き換える3引数関数のためにインターフェースを新しく用意する必要があるが，その他は特筆すべきところはない．インターフェース ThreeIntsToInt が整数3つから整数への関数を表すインターフェース，Sum3 が与えられた3整数の和を返す関数オブジェクトのクラス Sum3 である．

1
2
3
4

public interface Tree {
    ...
    int fold(int e, ThreeIntsToInt f);
}
1
2
3

public interface ThreeIntsToInt {
    int apply(int l, int v, int r);
}
1
2
3
4
5
6
7
8
9

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; }
}
1
2
3
4

    // Leaf クラスに追加
    public int fold(int e, ThreeIntsToInt f) {
        return e;
    }
1
2
3
4
5
6

    // 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);
    }
    System.out.println(t6.fold(0, new Sum3()));
       // displays the sum of 10, 25, ..., and 30.

fold その2

その1の実装では，leaf と branch のために別の引数を用意したが，これらをひとつのオブジェクトにまとめることも可能である．実装その2として，

  • 葉の時に呼び出すメソッド
  • 枝の時に呼び出すメソッド
    を持つオブジェクトを受け取る形で書いてみよう．このオブジェクトは，木の場合分け処理を表現していることから，インターフェース名を CaseForTree としている．
1
2
3
4
5

public interface Tree {
    ...
    int fold(int e, ThreeIntsToInt f);
    int fold(CaseForTree c);  // Overloading!
}
1
2
3
4

public interface CaseForTree {
    int caseLeaf();
    int caseBranch(int l, int v, int r);
}
1
2
3
4
5
6
7
8
9
10

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; }
}
1
2
3
4

    // Leaf クラスに追加
    public int fold(CaseForTree c) {
        return c.caseLeaf();
    }
1
2
3
4
5
6

    // Branch クラスに追加
    public int fold(CaseForTree c) {
        int l = left.fold(c);
        int r = right.fold(c);
        return c.caseBranch(l, v, r);
    }
1
2

        CaseForTree c = new SumTree();
        System.out.println(t6.fold(c));

さて，ここまで関数を表現するためにいちいちクラスを書いてきたが，これらの実装の問題点は，

  • 関数の引数型・返値型毎にインターフェースを用意する
  • 関数毎に別のクラスを用意する
    のがかなり煩雑である，という点である．ひとつめの問題は，ジェネリクスを用いることである程度解決する．例えば，ライブラリ java.util.function にある2 Function<T,R> というジェネリックインターフェースには R apply(T x); というメソッドが宣言されている．よって，上の IntToInt のようなインターフェースは Function<Integer, Integer> と書けばよい．(int は Integer に変える必要はある．) 3 また，ふたつめの問題は，現在の Java では「ラムダ式」で解決することができる．「ラムダ式」は OCaml の fun 記法とほぼ同じアイデアで匿名関数を表すための記法である．4

関数インターフェースとラムダ式

Java でのラムダ式の記法は以下の通りである．

記法 備考
x -> 〈式〉 1引数で〈式〉の値を返す
(x1,...,xn) -> 〈式〉 \(n\)引数で〈式〉の値を返す
x -> { ... } 1引数で，... の文(の列)を実行する．return された値が返る
(x1,...,xn) -> { ... } \(n\)引数で，... の文(の列)を実行する．return された値が返る

ラムダ式は1メソッドインターフェースが期待される文脈で使うことができる．例えば，上の Sum3 は，クラスを書かずとも，以下のようにして作ることができる．

ThreeIntsToInt f = (n, m, p) -> n + m + p;

左辺の状況から，この関数は apply の実装であると解釈してもらえるわけである．また，(ふつうは)文脈のインターフェースから型が決まるので，パラメータの型宣言はしなくても型推論が行われる．

上の map fold(その1) を使う例を書き直すと以下のようになる．

1
2
3
4
5
6

        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の略記であることを知っておくて理解しやすいだろう．

関数ポインタを使ったプログラミング in 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言語では関数呼び出しも後置演算子扱いで，後置演算子は常に前置演算子よりも優先される．)

型宣言の読み方

C言語の型宣言は，識別子の前後にいろいろくっついて型を表すこともあり，読み方がややこしい．

  1. 識別子から読み始める．f なら "f is ..." と読み始める
  2. 各記号の読み方は以下の表の通り．
  3. (括弧がない限り)後置の () (や []) を優先して読む
  4. 最後に左の型を読むと 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 の宣言につけた * は省略して，
int sigma(int f(int), int n) { ... }

と書いてもよい．が，これは関数パラメータに限られ，{} 内の局所変数の場合は省略できないので，この講義では常に * をつける．

  • 関数ポインタを使った呼び出し (*f)(n) も，* を省略して f(n) と書いてよい．f がポインタであるを意識・明示するために，この講義では常に * をつける．

  • 関数のポインタを取得する際に & をつけて (sigma(&cube,20) のように書いて)もよい．上の点とは一貫していないようにも思えるが，この講義では & はつけない．配列(これも関数と同様受け渡しできるのはポインタだけである)の場合，配列名が先頭要素へのポインタに自動変換されるのと揃えている．

2分木のmapとfold

記法さえ飲み込めば map fold を書くのには難しいことはない．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

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;
}

[ 前の資料 | 講義ホームページ・トップ | 次の資料 ]

  1. 「同様に」の意味は厳密ではないが，通常，変数に格納したり，他の関数・手続・メソッドに受け渡しできる，実行時に生成できたりすることを指す．↩

  2. 使うには `import java.util.function.*;' を各ファイル冒頭に置くこと↩

  3. 他に2引数関数のための BiFunction<T,U,R> というインターフェース(T と U が引数の型を表す)もあるが，3引数以上の場合は用意されていないようだ．↩

  4. 「ラムダ」というのはギリシャ文字の \(\lambda\) のことである．ラムダ計算(\(\lambda\)-calculus) という計算のモデルの理論で，\(x\) を引数とし(\(x\) を含む)〈式〉を計算して返す関数を \(\lambda x.〈式〉\) という形式で表すことに由来している．プログラミング言語によっては lambda が匿名関数のキーワードになっている場合もある．(Lisp など)↩

Copyright 五十嵐 淳, 2016, 2017