C言語では通常、遅延評価できませんが、関数ポインタやマクロを使用することで無理やりですが遅延評価が可能になります。
遅延評価により高速化可能な計算に竹内関数（tarai関数）があります。
竹内関数（tarai関数）
通常、C言語で組むと
#include <stdio.h>
#include <stdlib.h>
int count = 0;
int tarai(int x, int y, int z) {
printf("count = %d, tarai(%d, %d %d)\n", count, x, y, z);
count++;
if (x <= y) {
return y;
}
return tarai(
tarai(x - 1, y, z),
tarai(y - 1, z, x),
tarai(z - 1, x, y));
}
int main() {
int ans = tarai(10, 5, 0);
printf("ans = %d\n", ans);
printf("count = %d\n", count);
return 0;
}
となり、それを実行すると、
ans = 10
count = 343073
と長い時間をかけて出力されます。
遅延評価版では、
#include <stdio.h>
#include "lazy.h"
int count = 0;
LZ_FN3(tarai, x, y, z) {
count++;
if (calc(lz_le(x, y))) {
return y;
}
return tarai(
tarai(lz_sub(x, lzn(1)), y, z),
tarai(lz_sub(y, lzn(1)), z, x),
tarai(lz_sub(z, lzn(1)), x, y));
}
int main() {
int ans = calc(tarai(lzn(10), lzn(5), lzn(0)));
printf("ans = %d\n", ans);
printf("count = %d\n", count);
return 0;
}
となり、実行すると、
ans = 10
count = 76
となります。
ここで、 lazy.h や lazy.c はここにあります。
tarai関数を呼ぶ回数が、 343073回 から 76回 へと大幅に減っていることがわかります。
遅延評価版ではLazy型で計算式の形を保持します。
Lazy a = lzn(10);は10という整数をLazy型に変換するものです。
Lazy b = lz_sub(lzn(10),lzn(7)); は (10 - 7)という計算式を計算せず計算式のまま変数bに格納します。
calc(b)とcalc関数にLazy型の計算式を与えたときにはじめて計算を行い、答えである3を得ます。
tak関数
竹内関数の変種として、tak関数があります。
これはyを返していたところをzを返すものです。
通常、C言語で組むと
#include <stdio.h>
#include <stdlib.h>
int count = 0;
int tarai(int x, int y, int z) {
printf("count = %d, tarai(%d, %d %d)\n", count, x, y, z);
count++;
if (x <= y) {
return z;
}
return tarai(
tarai(x - 1, y, z),
tarai(y - 1, z, x),
tarai(z - 1, x, y));
}
int main() {
int ans = tarai(10, 5, 0);
printf("ans = %d\n", ans);
printf("count = %d\n", count);
return 0;
}
となり、それを実行すると、
ans = 5
count = 10345
とちょっと長い時間をかけて出力されます。
遅延評価版では、
#include <stdio.h>
#include "lazy.h"
int count = 0;
LZ_FN3(tak, x, y, z) {
count++;
if (calc(lz_le(x, y))) {
return z;
}
return tak(
tak(lz_sub(x, lzn(1)), y, z),
tak(lz_sub(y, lzn(1)), z, x),
tak(lz_sub(z, lzn(1)), x, y));
}
int main() {
int ans = calc(tak(lzn(10), lzn(5), lzn(0)));
printf("ans = %d\n", ans);
printf("count = %d\n", count);
return 0;
}
となり、実行すると、
ans = 5
count = 10345
となります。
tak関数を呼ぶ回数が、どちらも 10345回 であり遅延評価によって減っていません。
実はtak関数は遅延評価によって計算を短縮することができません。
tak関数(メモ化)
しかし、次のように変更を加えると、
#include <stdio.h>
#include "lazy.h"
int count = 0;
LZ_FN3(tak, x, y, z) {
count++;
if (calc(lz_le(x, y))) {
return z;
}
return tak(
tak(lz_sub(x, lzn(1)), y, z),
tak(lz_sub(y, lzn(1)), z, x),
tak(lz_sub(z, lzn(1)), x, y));
}
int main() {
+ no_lazy();
+ // no_memorize();
int ans = calc(tak(lzn(10), lzn(5), lzn(0)));
printf("ans = %d\n", ans);
printf("count = %d\n", count);
return 0;
}
実行結果は
ans = 5
count = 198
となり、
tak関数を呼ぶ回数が、 10345回 から 198回 へと大幅に減っていることがわかります。
変更を加えることで、遅延評価を不使用にして通常のC言語のように正格評価にし、
実はデフォルトで有効になっていたメモ化を利用してtak関数を呼ぶ回数を減らしたものです。
内部的に一度計算した結果をハッシュにして記録（メモ化）していて、同じ計算が発生した時にはその記録を呼び出すことで、計算を短縮しています。
本当は遅延評価＋メモ化のダブルの効果で計算回数を減らしたかったのですが、遅延評価を使用しているとメモ化がうまく働かず、メモ化を使用すると遅延評価がうまく働きませんでした。
竹内関数（tarai関数）(メモ化)
ちなみに、竹内関数をメモ化で処理した場合は、
#include <stdio.h>
#include "lazy.h"
int count = 0;
LZ_FN3(tarai, x, y, z) {
count++;
if (calc(lz_le(x, y))) {
return y;
}
return tarai(
tarai(lz_sub(x, lzn(1)), y, z),
tarai(lz_sub(y, lzn(1)), z, x),
tarai(lz_sub(z, lzn(1)), x, y));
}
int main() {
+ no_lazy();
+ // no_memorize();
int ans = calc(tarai(lzn(10), lzn(5), lzn(0)));
printf("ans = %d\n", ans);
printf("count = %d\n", count);
return 0;
}
実行結果は
ans = 10
count = 157
となり、
tarai関数を呼ぶ回数が、 遅延評価76回 と メモ化157回 と遅延評価のほうが少ないことがわかります。
まとめ
遅延評価をするうえで、内部的には関数ポインタを使ってクロージャのようなものを動的に作成（malloc）しているため、動作時間的にデメリットとなります。
また、lazy.c はmallocしたものを一切freeしていないため全く、実用的ではありません。（あくまでC言語でも遅延評価ができるよと実証するために作ったものなので）
正直、いろいろ頑張ってＣ言語で遅延評価を実装してみましたが、言語レベルで遅延評価が実装されている言語以外では、メモ化のみを使用すればよいと思います。