Cでカリー化関数を実現する

カリー化という言葉に耳慣れない方もいると思います。関数のカリー化というのは、 f(x,y)という関数があった時に、例えば、g(y) = f(100, y)となる関数gを動的に 生成することをいいます。(厳密には違いますが)

カリー化関数があれば、

int add(int x, int y) { return x + y; }

curry関数の実装

さて、一般にCでは動的に関数を生成することはできません。すなわち、プログラ ムで使うことのできる関数の数は、記述した関数の数より多くなることはありませ ん。そこで、Cでカリー化関数を実現するには、ちょっとトリッキーなことをしま す。何はともあれ、以下のプログラムを見てください。

/*
 * カリー化関数(intを返す関数へのポインタを返す)
 */
int (*curry(int (*func)(), int param))() {
#define CODE_SIZE 64
#define SAVE_ADDR 56
    char *code;
    extern char* memalign();

    code = memalign(4, CODE_SIZE);
    /* movl SAVE_ADDR,%ebx */
    code[0] = 0xbb;
    *(int *)(code + 1) = (int)code + SAVE_ADDR;
    /* movl %ebp, 0(%ebx)  */
    code[5] = 0x89; code[6] = 0x6b; code[7] = 0x00;
    /* popl 4(%ebx)        */
    code[8] = 0x8f; code[9] = 0x43; code[10] = 0x04;
    /* pushl param         */
    code[11] = 0x68;
    *(int *)(code + 12) = param;
    /* call   func         */
    code[16] = 0xe8;
    *(int *)(code + 17) = (int)func - ((int)code + 21);
    /* movl SAVE_ADDR,%ebx */
    code[21] = 0xbb;
    *(int *)(code + 22) = (int)code + SAVE_ADDR;
    /* pushl 4(%ebx)       */
    code[26] = 0xff; code[27] = 0x73; code[28] = 0x04;
    /* movl 0(%ebx), %ebp  */
    code[29] = 0x8b; code[30] = 0x6b; code[31] = 0x00;
    /* ret                 */
    code[32] = 0xc3;

    return ((int (*)())code);
}

curry関数が呼ばれると、動的にメモリを確保して、そこにマシン語(命令列)を直 接書き込んでいます。つまり、動的にプログラムを生成しているのです!!! そして、確保したメモリの先頭アドレスを関数ポインタとして返しています。この ようなことをしているので、当然移植性はなくなります。ちなみに、上のプログラ ムはi386 + Linuxでしか動きません。

1. 関数の戻り番地と上位フレームへのポインタを確保したメモリ領域に退避する。
2. 与えられたパラメータをスタックにプッシュする。
3. パラメータで指定された関数を呼び出す。
4. スタックフレームを元に戻して呼出し元にリターンする。

  (スタックフレームの構造)
   |                    |
   +====================+
   | upper frame(%ebp)  |<--+
   +--------------------+   |
   |                    |   |
   |      .......       |   |
   |                    |   |
   +--------------------+   |
   | arg2               |   |
   +--------------------+   |
   | arg1               |   |
   +--------------------+   |
   | return addr(%eip)  |   |
   +====================+   |
   | upper frame(%ebp)  |---+ <--- %ebp(現在のフレーム)
   +--------------------+
   | local var1         |
   +--------------------+
   | local var2         | <--- %esp(スタックトップ)
   +--------------------+

curry関数のテスト

せっかくですから、上で定義したcurry関数をテストしてみましょう。以下にテス トプログラムを示します。

/*
 * カリー化関数のテスト
 */
#include 
/*
 * a^n(ベキ乗)を計算
 */
int pow(int a, int n) {
    int i    = 0;
    int prod = 1;

    for (i = 0; i < n; i++) {
	prod *= a;
    }

    return prod;
}
/*
 * a * (b + c)を計算
 */
int addmul(int a, int b, int c) {
    return a * (b + c);
}
/*
 * メイン関数
 */
int main(void) {
    int (*square)();
    int (*cube)();

    square = curry(pow, 2);
    cube   = curry(pow, 3);

    printf("2^10    = %d\n", square(10));
    printf("3^4     = %d\n", cube(4));

    printf("2*(1+2) = %d\n", addmul(2,1,2));
    printf("4*(1+2) = %d\n", curry(addmul, 4)(1,2));
    printf("8*(1+2) = %d\n", curry(curry(addmul, 8),1)(2));

    return 0;
}

なんだか、Cのプログラムには見えませんがちゃんと動きます。実行してみると以 下のような結果が得られました。

$ ./a.out
2^10    = 1024
3^4     = 81
2*(1+2) = 6
4*(1+2) = 12
8*(1+2) = 24

以上、Cでカリー化関数を実現するという、およそ実用にもならないことを説明し てきましたが、まあ、このような考え方やプログラミングテクニックもあるという ことでご容赦下さい。

参考

• H君への手紙: curry