Sコンビネータ

昨日ついでに書いたものを公開する。
まず、λ計算というのがあって、それは関数の拡張概念みたいなものだと思っておけば、まあよくて、コンビネータというのがあって、(S,K)の組を適当に組み合わせるだけで、それと(ほぼ)同等な力を持っているのですよ。

typedef void* f0;
typedef f0 (*f1) (void*);
typedef f1 (*f2) (void*);
typedef f2 (*f3) (void*);
typedef f3 (*f4) (void*);
typedef f4 (*f5) (void*);
typedef f5 (*f6) (void*);
typedef f6 (*f7) (void*);
typedef f7 (*f8) (void*);
typedef f8 (*f9) (void*);
typedef f9 (*f10) (void*);
#define combinator f10

combinator k(void* v)
{
    unsigned char *func = (char*)malloc(6);
    func[0]=0xB8;
    *(void**)(func+1)=(void*)v;
    func[5]=0xC3;
    return (combinator)func;
}
combinator s(void* v)
{
    unsigned char *func = (char*)malloc(109);

    func[0]=0x55;
    func[1]=0x8B;func[2]=0xEC;func[3]=0x53;func[4]=0x56;func[5]=0x57;
    func[6]=0x6A;func[7]=0x2D;
    func[8]=0xB8;*(void**)(func+9)=(void*)malloc;
    func[13]=0xFF;func[14]=0xD0;
    func[15]=0x83;func[16]=0xC4;func[17]=0x04;

    func[18]=0xBE;*(int**)(func+19)=(int*)(func+64);
    func[23]=0x8B;func[24]=0xF8;
    func[25]=0xB9;*(int*)(func+26)=(int)0x2D;
    func[30]=0xF3;func[31]=0xA4;

    func[32]=0x8B;func[33]=0x55;func[34]=0x08;
    func[35]=0x89;func[36]=0x50;func[37]=0x0B;
    func[38]=0x90;func[39]=0x90;
    func[40]=0x5F;func[41]=0x5E;func[42]=0x5B;func[43]=0x5D;func[44]=0xC3;

    func[64]=0x55;
    func[65]=0x8B;func[66]=0xEC;
    func[67]=0x53;
    func[68]=0x56;
    func[69]=0x57;
    func[70]=0x8B;func[71]=0x55;func[72]=0x08;
    func[73]=0x52;
    func[74]=0xB8;func[75]=0x00;func[76]=0x00;func[77]=0x00;func[78]=0x00;
    func[79]=0xFF;func[80]=0xD0;
    func[81]=0x83;func[82]=0xC4;func[83]=0x04;
    func[84]=0x50;
    func[85]=0x8B;func[86]=0x55;func[87]=0x08;
    func[88]=0x52;
    func[89]=0xB8;*(void**)(func+90)=v;
    func[94]=0xFF;func[95]=0xD0;
    func[96]=0x83;func[97]=0xC4;func[98]=0x04;
    func[99]=0xFF;func[100]=0xD0;
    func[101]=0x83;func[102]=0xC4;func[103]=0x04;
    func[104]=0x5F;
    func[105]=0x5E;
    func[106]=0x5B;
    func[107]=0x5D;
    func[108]=0xC3;
    return (combinator)func;
}

これを書く上で取ったバグ

• push ebp のところで push ebx としていたこと。
• rep movs のいじるスタックを勘違いしていたこと。誤った資料を見た。
• (char*)で足すところを(int*)で足していた。

ollydbg走らせて難なく見つけた。ん、esi の s って明らかに source だろ、とか、なんか ebx 二度押してる、とか、で。と、まあ、長さの割にはやっていること単純なのでそんなに難しくはないです。
Sを書いて「ハック」の称号は吹き飛んだ気がするけども。
func[38]=0x90;func[39]=0x90;にNOPが二つ入っているけれども深い意味はない。はじめ、勘違いで mov eax,edi が入っていたような。

#define K (k)
#define S (s)
#define B (S (K S) K)
#define I (S K K)
#define Y (S (K (S I I)) (S (S (K S) K) (K (S I I))))

として

int suc(int i)
{
	return ++i;
}
int main()
{
	printf("%d:%s\n", S K K (10), S K K ("hello world!"));
	printf("%d\n", (S B) ((S B) ((S B) (K I))) (suc) (0));
}

を実行すると、

10:hello world!
3

と出る。つまり、S K K はなにもしない関数を返している。また、

(S B) ((S B) ((S B) (K I)))

はチャーチ数(church numeral)で 3 をあらわす。 3(f,x) = f(f(f(x))) という関数。
Bは合成関数を作る演算。Iは恒等写像。Yは不動点を返す。
そして、恒等写像が combinator で s k k と書けること、SKKの名前の由来はこれです。

C++の関数オブジェクトで書けるから、そうして実行速度を競ってみると楽しいかも。あと、コードがあれだとさすがにx86の生みの親でも分からんだろうから解説をつけるか。