Cで継続渡し(末尾最適化バージョン)
Cで継続渡しを書いてから、もう少しがんばれば末尾最適化もできそうだということに気付いて、やってみたらなんとかできた。しかも、絶対にアセンブラが必要だろうと思っていたんだけど結果的にはアセンブラに頼らずにCの範囲内で実現することができた。さすが高級アセンブラ。
- fib2.c
#include <stdio.h>
#include <stdlib.h>
#include "obj.h"
int main(int argc, char *argv[])
{
// 汎用レジスタのつもり
void *r1;
void *r2;
closure_t c = newClosure(0);
c->func = (func_t) &&fib_cps_0;
for (int i = 1; i < 10; i++) {
addRef((object_t) c);
// printf("Fibonacci(%d) = %d\n", i, fib_cps(i, c));
r1 = (void*) i;
r2 = (void*) c;
goto fib_cps;
fib_cps_0: // int fib_cps_0(int n, closure_t k)
{
int n = (int) r1;
closure_t k = (closure_t) r2;
release((object_t) k);
printf("Fibonacci(%d) = %d\n", i, n);
}
}
release((object_t) c);
return EXIT_SUCCESS;
fib_cps: // int fib_cps(int n, closure_t k)
{
int n = (int) r1;
closure_t k = (closure_t) r2;
if ((n == 1) || (n == 2)) {
r1 = (void*) 1;
r2 = (void*) k;
goto *(k->func);
// return (int) k->func(1, k);
} else {
closure_t c = newClosure(2);
c->func = &&fib_cps_1;
c->vars[0] = (void*) k;
c->vars[1] = (void*) n;
r1 = (void*) (n - 1);
r2 = (void*) c;
goto fib_cps;
// return fib_cps(n - 1, c);
}
}
fib_cps_1: // int fib_cps_1(int v1, closure_t k1)
{
int v1 = (int) r1;
closure_t k1 = (closure_t) r2;
int n = (int) k1->vars[1];
closure_t c = newClosure(3);
c->func = &&fib_cps_2;
c->vars[0] = k1->vars[0];
c->vars[1] = (void*) v1;
c->vars[2] = (void*) n;
release((object_t) k1);
r1 = (void*) (n - 2);
r2 = (void*) c;
goto fib_cps;
// return (int) fib_cps(n - 2, c);
}
fib_cps_2: // int fib_cps_2(int v2, closure_t k2)
{
int v2 = (int) r1;
closure_t k2 = (closure_t) r2;
int v1 = (int) k2->vars[1];
closure_t k = k2->vars[0];
release((object_t) k2);
r1 = (void*) (v1 + v2);
r2 = (void*) k;
goto *(k->func);
// return (int) k->func(v1 + v2, k);
}
}最初ラベルのアドレスを得る方法とかポインタ変数の指すアドレスにgotoする方法が分からなくて困った（それぞれ&&label, goto *varなどと書けばいい）。
このコードは全く実用的ではないけど、末尾呼び出しをジャンプに変換すると本当に関数呼び出しが消えるという実証にはなっていると思う。こういうことをコンパイラがやってくれると、プログラマは効率の心配をせずになんでも再帰呼び出しにしてしまうことができる。
以下は28日のfib.h, fib.cの一部を別ファイルとしたもの（内容はほとんど同じですが微妙に修正してあります）
- obj.h
#ifndef __OBJ_H__
#define __OBJ_H__
typedef void* (*func_t)();
typedef void (*proc_t)();
typedef struct object {
int ref_count;
size_t size;
proc_t destructor;
} *object_t;
void addRef(object_t obj);
void release(object_t obj);
object_t newObject(size_t size, proc_t destructor);
void deleteObject(object_t obj);
typedef struct closure {
// inherited from object_t
int ref_count;
size_t size;
proc_t destructor;
// own data
func_t func;
int var_num;
void *vars[0];
} *closure_t;
closure_t newClosure(int var_num);
#endif /* __OBJ_H__ */
- obj.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "obj.h"
void addRef(object_t obj)
{
obj->ref_count++;
}
void release(object_t obj)
{
obj->ref_count--;
if (obj->ref_count <= 0) {
if (obj->destructor)
obj->destructor(obj);
deleteObject(obj);
}
}
object_t newObject(size_t size, proc_t destructor)
{
assert(size >= sizeof(struct object));
object_t obj = malloc(size);
#ifdef DEBUG
fprintf(stderr, "malloc: %p\n", obj);
#endif
obj->ref_count = 0;
obj->size = size;
obj->destructor = destructor;
addRef(obj);
return obj;
}
void deleteObject(object_t obj)
{
#ifdef DEBUG
size_t size = obj->size;
char *p = (char*) obj;
// filled by `de ad be ef' ... pattern
for (int i = 0; i < size / 4; i++) {
*p++ = '\xde'; *p++ = '\xad';
*p++ = '\xbe'; *p++ = '\xef';
}
switch (size % 4) {
case 3: p[2] = '\xbe';
case 2: p[1] = '\xad';
case 1: p[0] = '\xde';
}
#endif /* DEBUG */
free(obj);
#ifdef DEBUG
fprintf(stderr, "free: %p\n", obj);
#endif
}
closure_t newClosure(int var_num)
{
assert(var_num >= 0);
size_t size = sizeof(struct closure) + sizeof(void*) * var_num;
closure_t c = (closure_t) newObject(size, NULL);
c->var_num = var_num;
return c;
}
→修正版
人間コンパイラコンパイラとLispのマクロ
C++を使っていると、関数型言語の人には、「そこまで(Boost.Lambdaみたいなことまで)して関数型に近づける努力をするくらいならC++をやめて関数型言語使えばいいじゃん」 と言われることがありますが、それは全然違うよ、と思うのです。
まさに自分はそういうことをよく言う派の人間なのですが、後の方で書かれている「Powerfulな言語の人間コンパイラコンパイラとなる」というのは、それはそれでよく分かります（例えば次のエントリなんかもその一つ）。そして、その場合Lisp系の言語ではマクロという非常に強力な機能があって、これが自分がSchemeを使っている大きな理由の一つになっています。
Schemeの（というかLispの）マクロは、その表現力と言語本体との親和性の高さが他の言語とは一線を画していて、相当変なこと（例えば元の文法を根本的に変えてしまったり）でも、割と自然に書くことができます。極端に言うと、通常の関数を定義する気安さで新しい文法を一つ作れるようなものです（Schemeのマクロ定義はそのものずばりdefine-syntaxという名前になっています）。使ったことのない人には理解しにくいかもしれませんが、もし仮にLispにマクロがなかったとしたら、それはユーザが関数を定義できないC言語みたいなものだと言えば、おそらく使いにくくてしょうがないということが分かってもらえるでしょう。だからこそSchemeのマクロが楽しいわけです。
