GCCにはclosureがある!

実は以外と知られていないが、gccでは無名関数は使えなくとも、closureは使える。最近では無名関数をサポートしている言語が人気ということもあり、また無名関数の多くがclosureとしても用いられているため、無名関数の別名としてclosureという呼び方をすることもあるが(私もときどきやる)。この二つは本来は別物である。JavaScriptで書くと、

var outer      = 1;
var closure    = function(x){ return outer++ };
var nonclosure = function(x){ return x + 1 };

ということになる。外の変数を束縛しているか否かが、closureかどうかを分ける違いだ。名前があるかどうかは本来関係ないのだ。

それでは、gccにおけるclosureはどんな姿をしているか?見れば一目瞭然であろう。

#include <stdlib.h>
#include <stdio.h>

static long long count = 0;

int ltak(int (*fx)(void), int (*fy)(void),int (*fz)(void)){
    count++;
    if (fx() <= fy()){
        return fy();
    }else{
        int dx(void){ return fx() - 1; };
        int dy(void){ return fy() - 1; };
        int dz(void){ return fz() - 1; };
        int fxx(void){ return ltak(dx, fy, fz); };
        int fyy(void){ return ltak(dy, fz, fx); };
        int fzz(void){ return ltak(dz, fz, fy); };
        return ltak(fxx, fyy, fzz);
    }
}

int tak(int x, int y, int z){
    int fx(void){ return x; };
    int fy(void){ return y; };
    int fz(void){ return z; };
    return ltak(fx, fy, fz);
}

int main(int argc, char **argv){
    int x = argc > 1 ? atoi(argv[1]) : 10;
    int y = argc > 2 ? atoi(argv[2]) :  5;
    int z = argc > 3 ? atoi(argv[3]) :  0;
    int v = tak(x, y, z);
    printf("tak(%d, %d, %d) = %d; tak() called %qd times.\n", 
           x, y, z, v, count);
    return 0;
}

上記のコード、-W -Wallでコンパイルしても一切文句は出ない。環境によっては-fnested-functionsが必要かも知れない。Mac OS Xではそうだった。

上記のコードを実行してみると、確かに遅延化による効果が見られる。しかし、Judyでメモ化した時ほどではない。

tak(1000, 500, 0) = 1000; tak() called 1998001 times.
       20.16 real        20.07 user         0.00 sys
       768  maximum resident set size
         4  average shared memory size
         4  average unshared data size
       384  average unshared stack size
       136  page reclaims
         0  page faults
         0  swaps
         0  block input operations
         0  block output operations
         0  messages sent
         0  messages received
         0  signals received
         3  voluntary context switches
      1346  involuntary context switches

このnested functionはgccの機能拡張の中でも私が一番好きなものの一つなのだが、残念ながらCの標準ではない。また、セキュリティ上の問題にもなりうる。詳しくはBinary HacksのHack #33を参照のこと。

Cの標準機能のみでたらいを後回ししてみる

GCCの機能拡張を使わない限り、Cでは遅延評価は無理なのだろうか?ありがたいことに、Cには関数ポインターというものがある。これを何らかの形で保存しておき、後でそれを実行することは出来ないだろうか?

それをやったのが、以下のコードである。

#include <stdlib.h>
#include <stdio.h>

static long long count = 0;

typedef struct promise{
    int (*f)(struct promise *,struct promise *,struct promise *);
    union{
        int v;
        struct a {
            struct promise *x, *y, *z;
        } a;
    } v;
} promise;

promise *delay1(int v){
    promise *d = (promise *)malloc(sizeof(promise));
    d->f       = NULL;
    d->v.v     = v;
    return d;
}

promise *delay4(int (*f)(promise *,promise *,promise *), 
                promise *x, promise *y, promise *z){
    promise *d = (promise *)malloc(sizeof(promise));
    d->f       = f;
    d->v.a.x   = x;
    d->v.a.y   = y;
    d->v.a.z   = z;
    return d;
}

int force(promise *d){
    return d->f ? d->f(d->v.a.x, d->v.a.y, d->v.a.z) : d->v.v;
}

int ltak(promise *dx, promise *dy, promise *dz){
    count++;
    if (force(dx) <= force(dy)){
        return force(dy);
    }else{
        return ltak(
            delay4(ltak, delay1(force(dx)-1), dy, dz),
            delay4(ltak, delay1(force(dy)-1), dz, dx),
            delay4(ltak, delay1(force(dz)-1), dx, dy)
            );
    }
}

int tak(int x, int y, int z){
    return ltak(delay1(x), delay1(y), delay1(z));
}

int main(int argc, char **argv){
    int x = argc > 1 ? atoi(argv[1]) : 10;
    int y = argc > 2 ? atoi(argv[2]) :  5;
    int z = argc > 3 ? atoi(argv[3]) :  0;
    int v = tak(x, y, z);
    printf("tak(%d, %d, %d) = %d; tak() called %qd times.\n", 
           x, y, z, v, count);
    return 0;
}

要は遅延評価に必要な「材料」を構造体の中に忍ばせておき(delay)、その構造体を「評価する」関数(force)で値を取り出すというわけだ。

速度もなかなかのものである。

tak(1000, 500, 0) = 1000; tak() called 1998001 times.
        0.44 real         0.39 user         0.04 sys
     47336  maximum resident set size
         4  average shared memory size
     23706  average unshared data size
       128  average unshared stack size
     11997  page reclaims
         0  page faults
         0  swaps
         0  block input operations
         0  block output operations
         0  messages sent
         0  messages received
         0  signals received
         1  voluntary context switches
        57  involuntary context switches

ただし見ての通り、メモリーを食う上に、遅延評価用に確保した構造体をいつ解放していいのかが難しい。上ではmalloc()したのにfree()せず、メモリー解放はプログラム終了時にやるという、実用上はトンデモプログラムに仕上がっているが、スタック上に確保した領域ではうまく行かない(やってみればわかる)。

また、見ての通りここにおける遅延評価用の構造体は、たらい回し専用である。これを一般化するのはtrivialとはとても言えない。C++だとテンプレートがあるのでもう少し楽そうだが、他のLLほどカジュアルには行かなそうだということは確かなようだ。

とはいえ、遅延評価がすっぴんのCでも可能だというのは何かの時に役にたつ--かもしれない。

Dan the Lazy Evaluator