CでSKIコンビネータしてみる

みょん · 投稿記事 by **みょん** » 12年前

Cの函数ポインタというものを、名前は聞いたことあったけど今まで実際使ったことなかったので使ってみることにしました。
折角なので函数ポインタでコンビネータっぽいものを実装してみようかと思います。
今回実装するのはLazy Kなどでも採用されているSKIコンビネータと呼ばれるものです。

コンビネータについて：
翻訳:コンビネータ論理チュートリアル
Lazy K(wikipedia)

要は函数S,K,Iを実装するだけです(コンビネータの妥当性はコンパイルエラーでキャッチできるはずなので割愛します)
函数Iは恒等写像ですから来た変数をそのまま返します(I(x){return x;})
Kは2つの引数を取り前だけを返します(K(x,y){return x;})
Sは少し複雑で、引数xyzが来たらxにyと(x z)を適用させます(S(x,y,z){return x(y,(x,z))})

ここで言う引数とは、函数(というかラムダ式)を含んでいます
これをそのままCで実装してみます

CODE:

#include 
 
void* I(void* x){
    return x;
}
 
void* K(void* x, void* y){
    return x;
}
 
void* S(void* (*x)(void*, void*), void* (*y)(void*), void* z){
    return (*x)(z, (*y)(z));
}
 
void dummy(void){}
void out(int a){ printf("here!:%d",a); }
 
int main(void)
{
    // SKK = I
    void (*f)(int) = S(K,K,out);
    (*f)(10);
    return 0;
}

最後の部分では、SKKがIと等しいことを用いて、SKKに函数outを作用させるとoutが返ってくることを表しています
実行結果は

here!:10

が出力され、確かにout函数が実行されていることが分かります

以上、函数ポインタを用いたSKIコンビネータの実装でした〜☆
(どうせならチャーチ数も実装して、自然数の足し算とか出来るようにさせれば、例えばですが函数fを2回作用させる、みたいな処理も出来るようになって素敵なのでやってみようかと思っています)

		7月 2025
日	月	火	水	木	金	土
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31