不動点演算子 in C DouKaku?

不動点演算子

不動点演算子とは、関数を引数に取り、その関数の不動点を返すような関数です。つまり、不動点演算子である関数gが関数fを引数に取るとき、 f(g(f)) = g(f) となります。

お題は不動点演算子を実装することです。（Yコンビネータを実装しても結構ですが、それ以外でも、コンビネータになっていなくてもOKとします）

Posted feedbacks - C

let rec fix f = f (fix f)型の不動点演算子をCで実現してみました。
stdcall呼び出しの関数(引数は右から左にスタックにプッシュ、スタックの後始末は呼び出された側で実施)を渡すと、不動点(実体は遅延評価のためのThunk)を作って返します。

任意個の引数の関数に対応しています。
また、Visual C++/GCCの両方で使用可能です。

#include <stdio.h>
#include <string.h>

#ifdef __GNUC__
#ifndef __stdcall
#define __stdcall __attribute__((stdcall))
#endif
#endif

#define SET(p,a) *(void**)(p+a)

void* __stdcall fix(void *f)
{
    char *thunk = strdup("hack!\xba....\xff\xd2ZPR\xb8....\xff\xe0");
    SET(thunk,  1) = f;
    SET(thunk,  6) = fix;
    SET(thunk, 16) = f;
    return thunk;
}

typedef int (__stdcall *FUNC2)(int, int);

int __stdcall gcd_maker(FUNC2 f, int a, int b)
{
    return a % b == 0 ? b : f(b, a % b);
}

int main(int argc, char**argv)
{
    FUNC2 gcd = (FUNC2)fix(gcd_maker);

    printf("gcd(2520,3840) = %d\n",             gcd(2520,       3840));
    printf("gcd(1836311903,1134903170) = %d\n", gcd(1836311903, 1134903170));

    return 0;
}

DouKaku?

不動点演算子

Posted feedbacks - C

Index

Feed

Other

Link

Pathtraq