期末考査から考える無名再帰

多摩科技ACを作っておきながら、一つも記事を書かないというのもどうかと思ったので書きます。

期末考査の問題

我が校の「科学技術科」課程では、生徒はET・BT・IT・NTの四領域いずれかに所属して学習や研究活動を進めていきます。

さて皆さん、期末考査の成績はどうでしたか？
先日実施された「3年IT概論」問12では以下のような内容が出題されました。

入力された自然数(n)までの階乗を求めるプログラムを記述しなさい。（10点×1=10点）

ここで用いるプログラミング言語はC++です。しかし授業ではC言語の範囲で指導を受けていたので、多くの方はCで回答を作成したかと思います。

first.cpp

#include <stdio.h>

int main(void){
    unsigned int n;
    unsigned int ans = 1;

    scanf("%u", &n);

    for(; n > 0; n--)
            ans *= n;

    printf("n! = %u\n", ans);

    return 0;
}

実際の問題にあった出力の形式とかscanfの安全性とかの話は省略すれば、だいたいこんな感じでしょう。
当然ながらこのソースコードだってコンパイルすればちゃんと動きます。今回はg++くんに来てもらいました。

$ g++ first.cpp -o first
$ ./first
5
n! = 120

とまあ、こんな具合に。

関数に分離する

もしあなたが同じコード中で何度も階乗を求めたいとすれば、同じ内容を何度もコピペするのはあまり賢いやり方とは言えません。この部分を独立した処理として抜き出して、必要な時に呼び出せるようにすれば効率的でしょう。

#include <stdio.h>

unsigned int factorial(unsigned int n){
    unsigned int ans = 1;

    for(; n > 0; n--)
        ans *= n;

    return ans;
}

int main(void){
    unsigned int n;

    scanf("%u", &n);

    printf("n! = %u\n", factorial(n));

    return 0;
}

ここでfactorialは「自然数nを受け取ってその階乗を求める」関数で、こうしておけば後は好きな時にfactorial(2)とかfactorial(a)とかするだけでその階乗を得られます。

再帰を使う

先程の例では階乗の計算をfor文による繰り返し処理で実現していますが、これを別の形で表現することはできないでしょうか？自然数における$n$の階乗は$n!=n(n-1)(n-2)(n-3)......3 \cdot 2 \cdot 1$と定義されていますが、これは以下のようにも書き換えることができます。

n! = n(n-1)!

あるいは階乗を求める関数を$f(n)$として、

f(n)=\begin{cases}
    n f(n-1) & (n > 0) \\
    1 & (n = 0)
  \end{cases}

これを元にfactorialを書き直してみましょう。

factorial.cpp

unsigned int factorial(unsigned int n){
    if(n > 0){
        return n*f(n - 1);
    }else{
        return 1;
    }
}

もしくはもっと簡潔に

unsigned int factorial(unsigned int n){
    if(n > 0)
        return n*f(n - 1);
    return 1;
}

とか、三項演算子を使って

unsigned int factorial(unsigned int n){
    return n > 0 ? n*f(n - 1) : 1;
}

と書いてもいいですが、どちらにしても先程の定義をそのまま実装した形になっています。
もちろんfactorialはその内部で自身を呼び出しているため、それ以前に前方宣言をしている必要があります。
このように、サブルーチン（特に関数）内で自分自身を呼び出す構造のことを再帰呼び出しと言います。

フィボナッチ数列

別の例を考えましょう。フィボナッチ数列は以下の漸化式によって定義されています。

F_0=0\\
F_1=1\\
F_{n}=F_{n-1}+F_{n-2}\ (n \ge 2)

これより、自然数nを受け取ってフィボナッチ数列の第$n$項を返す関数fibonacciは以下の通りです。

fibonacci.cpp

unsigned int fibonacci(unsigned int n){
    if(n == 0)
        return 0;
    else if(n == 1)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

このように、関数には再帰呼び出しを使うことで簡潔に記述することが可能なものがあります。

第一級関数と無名関数

次に第一級オブジェクトと第一級関数、そして無名関数なる存在について論じていきます。

第一級オブジェクトの要件

Wikipediaによれば、ある対象が概ね以下のような要件を満たす時にそれが「第一級オブジェクト」であるとされます。

・無名のリテラルとして表現可能である。
・変数に格納可能である。
・データ構造に格納可能である。
・それ自体が独自に存在できる（名前とは独立している）。
・他のものとの等値性の比較が可能である。
・プロシージャや関数のパラメータとして渡すことができる。
・プロシージャや関数の戻り値として返すことができる。
・実行時に構築可能である。
・表示可能である。
・読み込むことができる。
・分散したプロセス間で転送することができる。
・実行中のプロセスの外に保存することができる。
出典：Wikipedia『第一級オブジェクト』

特に、無名のリテラルとして表現可能であるという点は非常に重要な要素です。
リテラル*(literal)*は「文字通り」という意味の英語で、コンピュータプログラミングにおいてはソースコード内に直接記述される値を指します。

リテラルの例：

• 数値（整数、実数、複素数など）
• 文字
• 文字列
• 真偽値
• 配列
• 構造体
• クラス
• 関数

ここで注意したいのは、例えば以下のようなソースコードがあったとき、

var = "hoge"

ここでいうリテラルとは変数varではなく、値"hoge"のことだということです。

無名関数

リテラルの例として関数も挙がっていますが、そのような関数を特に関数リテラルと呼びます。
しかしここまでのソースコードに登場した関数たちはどれもリテラルではありません。無名でも何でもありませんから。

もしこれが文字列リテラルならば

"Hello World!"

関数リテラルはこういったものだろうと思いませんか？

(double x){
    if(x >= 0)
        return x;
    else
        return -x;
}

これは与えられた小数の絶対値を返す関数ですが、関数リテラルとして無名のまま独立に記述されています。この関数に生まれもって付けられた名前というのはなく、ただそういう「値」として存在するのです。名前がないので、関数リテラルは無名関数とも呼ばれます（厳密には別物かも）。
これが変数に格納できたり配列を作れたり、あるいは別の関数の引数として渡したり返値として受け取ったりすることができれば、その関数は第一級オブジェクトと言えるでしょう。そのような関数が第一級関数であり、多くの場合無名関数は第一級関数です。
階乗もこの無名関数で記述できればなんだか便利そうですね。

C++の無名関数

C/C++には以前まで無名関数が存在していませんでした。プログラマはC++で関数をオブジェクト的に使いたいときには関数ポインタをいじくり回す他なかったのです。
しかし2011年に標準化されたISO/IEC 14882:2011、通称C++11より以下のようなラムダ式（ラムダ関数）が追加されました。
以下は先に挙げた階乗をラムダ式で表記した形です。

[](unsigned int n){
    unsigned int ans = 1;
    for(; n > 0; n--)
        ans *= n;
    return ans;
}

最早factorialという名前すら必要ありませんが、これを名前付けられた変数に代入することも可能です。
3やtrue、"hoge"と同じ、ただの値なのですから。

auto factorial = [](unsigned int n){
    unsigned int ans = 1;
    for(; n > 0; n--)
        ans *= n;
    return ans;
};

ラムダ式は自動的に定義される一意な型のオブジェクトでありプログラマが知ることはできません。変数に代入する際には上の例文のように型推論キーワードautoを使うか、クラスstd::functionの変数を使う必要があります。
そういえば、関数の頭に[]という何やらわからない記号がついています。これはラムダ導入子といい、ラムダ式がクロージャ的に使われる際に変数のキャプチャについて指定するものです。とりあえず無視して「頭に[]をつければいいんだな」と思ってもらえれば十分です。

ここでのfactorialは右辺の関数を代入された変数に過ぎません。よってこのように値を代入して使うだけでなく

std::cout << "n! = " << factorial(n) << std::endl;

別の関数に渡すことすら可能です。

hogeFunc(factorial, x); //関数と値を受け取ってなんかする関数

ラムダ計算

急に「ラムダ式」という単語が出てきましたが、これは計算理論におけるラムダ計算という計算模型が由来です。詳しい説明はリンク先のWikipediaに譲りますが、簡単に言えば以下のような$x$の関数$f(x)$があったとすれば

f(x)=x+3

それを以下のように表記する方法のことです

\lambda x. x+3

ここでもやはり関数には名前というものがありません。どうしても紐づける必要があるなら

f = \lambda x. x+3

とすることもできます。
ならばこの関数に$x=3$を代入（こうした動作を適用といいます）したいときにはどうすればいいでしょうか？普通なら$f(3)$と表記するでしょうが、ラムダ式にはそういった方法は通用しません。
実際のところ、ラムダ式では

(\lambda x.x+3)\ 3

といった具合に関数の右側に書くことで適用を示します。当然その結果は$6$です。
ここで$x$という変数の名前は重要ではありません。同じ変数が同じ文字で表現されていさえすれば区別がつくので、

\lambda x.x+3 = \lambda y.y+3 = \lambda い.い+3

これら各辺は同様の関数を指すでしょう。
さて、ここで関数に適用されるものは数値とは限りません。

高階関数

突然ですが、もしも先程の関数へ$\lambda x.x^2-3$を適用するとどうなるでしょうか？

(\lambda x.x+3)(\lambda x.x^2-3)=\lambda x.x^2

関数に関数を適用することで新たな関数を得ることが出来ました。
ここで上記の左辺にある二つの関数の変数について、$\lambda x.x+3$の$x$と$\lambda x.x^2-3$の$x$は、偶然名前が同じだけの全くの別物であるということに留意してください。
このように関数を受け取ったり、あるいは関数を返すような関数を高階関数と呼びます。

当然ながら、受け取った関数に関数内で関数を適用することだって問題ありません。
少しだけ複雑な例を出します。

F = \lambda f. f (\lambda x.x+3)

$F$は「受け取った引数の関数$f$へ関数$\lambda x.x+3$を適用する」関数です。だから、例えば$F$に$\lambda y.\sqrt y$を適用したならば、

F (\lambda x.\sqrt x) = (\lambda y. \sqrt y)(\lambda x.x+3)= \lambda x. \sqrt {x+3}

を得ることになります。

##カリー化

次に考えるのは、二つの引数$a$と$b$の和$a+b$を返すような関数です。
数学の一般的な記法に則るならば、これは二変数関数

f(a,b)=a+b

というように書きます。
しかし、実はラムダ計算において関数はたった一つの引数しか持つことが出来ません。ラムダ計算では$a+b$なんていう簡単な関数も表現できないのでしょうか？
結論から言えば、その問題は下のような関数によって解決できます。

\lambda a.(\lambda b. a+b)

$a=4, b=9$が適用されるものとして一つずつその過程をトレースしていきましょう。

(\lambda a.(\lambda b. a+b))\ 4 = \lambda b.4+b

まず、一番外側の関数に対して$a=4$を適用することで右辺のような関数を得ます。
そして次に......

(\lambda b. 4+b)\ 9=4+9=13

$b=9$を適用することで、最終的な結果$4+9=13$を計算することが出来ました。
これを一行で書き表すならば

((\lambda a.(\lambda b. a+b))\ 4)\ 9 =(\lambda a.(\lambda b. a+b))\ 4\ 9= 13

となります。やっていることは本質的には先程の高階関数の例と同じです。
このように一変数関数を入れ子構造にすることで多変数関数のようにすることをカリー化といいます。

ちなみに、例示した関数$\lambda a.(\lambda b. a+b)$はよく

\lambda ab.a+b

のように省略して表記されるので注意しましょう。

Haskellを使ってみよう

しかしC++の文法というのは、関数で色々遊ぶにはあまりにも窮屈すぎます。もっと楽に「それっぽく」書くことが出来る言語はないのでしょうか。
そこで選択したいのがHaskellです。どんな言語かって？とりあえずHello Worldでも読んでみましょうか。

hello.hs

main = putStrLn "Hello, World!"

Haskellもエントリーポイントはmain関数です。

Haskellで階乗

Haskellにはfor文というものが存在しません。
しかしご安心を、そんなもの無くたってもっと綺麗なfactorialが書けますから。

factorial 0 = 1
factorial n | n > 0 = n * factorial(n - 1)

簡潔......！
1行目では引数が0の時の、2行目では引数が0より大きい時のfactorialを再帰によって記述しています。まさしく先述した階乗の定義通りですね。

しかしこの関数factorialは無名関数ではありません。factorialという名前ありきなのがその証拠でしょう。
そうなれば早速Haskellでも階乗を無名関数で書いてみたいと思うのが人情ですが、先述の通りHaskellにはfor文が（細かい部分を置いておけば）存在しません。繰り返し処理は全て再帰によって実現するというのがHaskellの設計思想です。
すると重大な問題に気が付きます。無名関数は自分自身の名前を持たないために、自分の名前を使って再帰呼び出しをすることが出来ないのです。これは困った。

Haskellでラムダ式

難しいことは置いておいて、まずはHaskellのラムダ式記法をご紹介します。

例1：$\lambda x. x+3$

\x -> x +3

例2：$\lambda ab.a+b$

\a -> \b -> a + b

C++に比べれば雲泥の差ですね。

ここで、もし例2をfという名前の関数にするならば

f a b = a + b
f a = \b -> a + b
f = \a -> \b -> a + b

は全て等価の表現です。

無名再帰

無名関数が自分自身を呼び出す＝再帰呼び出しをすることを無名再帰と呼びます。
しかし先述の通り、無名関数は名前がないので一般的な（名前が付いた）関数のようには簡単に再帰呼び出しができません。
それを可能にするために必要な関数が「不動点コンビネータ」です。

不動点コンビネータと再帰

ここで不動点コンビネータなる高階関数$\mathrm{fix}$を以下のように定義します。

任意の関数fに対して、f(\mathrm{fix}(f))=\mathrm{fix}(f)が成り立つ\\
\Leftrightarrow 任意の関数fに対するx=\mathrm{fix}(f)について、f(x)=x

つまり$\mathrm{fix}$とは、どんな関数$f$に対しても$f(x)=x$の解を返してくれるような関数を指します。
ちなみに$\mathrm{fix}$は不動点コンビネータ(fixed point combinator)の頭文字です。

ここで、不動点コンビネータについて一般に以下のことが知られています。

ある再帰関数をf(x)とする。これはf(x)=U(f,x)という関数Uで表される。\\
更にUがV:f \rightarrow U(f, x)なる関数Vで定義されるとき、\\
f(x)=\mathrm{fix}(V)

これは大変興味深く、同時にとても有用な性質です。
証明はこちらにありますが、結構面白いので自力で導出してみてもよいでしょう。

ここに非常に重要なポイントがあります。
それは再帰関数$f$を得ることができるにもかかわらず、そのために$f$自身を必要としないということです。
さて、私たちは無名再帰によって階乗を求める関数を作り出したいのでした。ここでいう$f$がfactorialであるとすれば、それに対応する$V$さえ実装できればよいということになります。

What is V?

そもそも$f$は次のような関数でしたね。

f(n)=\begin{cases}
    n f(n-1) & (n > 0) \\
    1 & (n = 0)
  \end{cases}

然るに$U$は次のような内容であるべきです。

U(f,n)=\begin{cases}
    n f(n-1) & (n > 0) \\
    1 & (n = 0)
  \end{cases}

$V$とは$f$を受けて$U(f,n)$を返す関数でした。ということは......

V(f)=\begin{cases}
    n f(n-1) & (n > 0) \\
    1 & (n = 0)
  \end{cases}

結局のところ、その外見は変わっていません。

ラムダ式に書き直す

しかし実際にはこれを無名関数の形で実装する必要がありますから、このままでは式とプログラムの対応関係がパッとしないままです。ラムダ式に書き直してみましょう。

f = \lambda n. \begin{cases}
    n f(n-1) & (n > 0) \\
    1 & (n = 0)
  \end{cases}

U= \lambda f. \lambda n. \begin{cases}
    n f(n-1) & (n > 0) \\
    1 & (n = 0)
  \end{cases}

\begin{eqnarray}
V &=& \lambda f. \begin{cases}
        \lambda n. n \cdot f(n-1) & (n > 0) \\
        \lambda n. 1 & (n = 0)
      \end{cases}\\
&=& \lambda f. \lambda n. \begin{cases}
        n \cdot f(n-1) & (n > 0) \\
        1 & (n = 0)
      \end{cases}\\
&=& \lambda fn. \begin{cases}
        n \cdot f(n-1) & (n > 0) \\
        1 & (n = 0)
      \end{cases}
\end{eqnarray}

無事に$V$をラムダ式の形で表現できました。あとは手を動かしてキーボードを打つだけです。

実装する

不動点コンビネータfixは定義より以下の形で記述できます。

fix = \f -> f(fix f)

さて、あとはVをそのまま書けば......

fix (\f -> \n -> if n > 0 then n*f(n - 1) else 1)

これこそが「階乗」を求める無名関数です！！

動かそう！

どきどきの実行タイム

anonymous.hs

fix = \f -> f(fix f)
factorial = fix (\f -> \n -> if n > 0 then n*f(n - 1) else 1)

main = do
    print (factorial 5)
    print (factorial 10) 

$ ghc anonymous.hs -o anonymous
[1 of 1] Compiling Main             ( anonymous.hs, anonymous.o )
Linking anonymous ...
$ ./anonymous
120
3628800

動いた！
電卓を叩いて$5!$と$10!$を検算......ちゃんと計算できてるみたいです。

まとめ

期末考査の問題からスタートして（こじつけ）、最終的には無事に階乗を無名再帰で求めることができました。
Haskellに触ったのは初めてだったけど気持ちよくてクセになりそうです。