竹内関数（tarai関数）

通常、C言語で組むと

tarai1.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

と長い時間をかけて出力されます。

遅延評価版では、

tarai2.c

#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言語で組むと

tak1.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

とちょっと長い時間をかけて出力されます。

遅延評価版では、

tak2.c

#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関数(メモ化)

しかし、次のように変更を加えると、

tak2.c

#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関数）(メモ化)

ちなみに、竹内関数をメモ化で処理した場合は、

tarai2.c

#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言語でも遅延評価ができるよと実証するために作ったものなので）

正直、いろいろ頑張ってＣ言語で遅延評価を実装してみましたが、言語レベルで遅延評価が実装されている言語以外では、メモ化のみを使用すればよいと思います。