竹内関数と遅延評価

竹内関数ってご存知でしょうか?
ベンチマークテストに使われる関数なんだそうですが、シンプルな外見に似合わず、計算に無茶苦茶時間がかかる関数だそうです。
Schemeでの定義は以下の通りです。

(define (tak x y z)
  (if (<= x y)
      y
      (tak (tak (- x 1) y z)
    (tak (- y 1) z x)
    (tak (- z 1) x y))))

環境にもよるんですが、あまり大きな実引数を与えると計算がなかなか終わりません。PLT Scheme依存のtime手続きで時間を計ってみます。なお、CPUはCore2DuoのT7500の2.2GHz、メモリは2GBです。

> (time (tak 10 5 0))
cpu time: 20 real time: 21 gc time: 0
10
> (time (tak 12 6 0))
cpu time: 388 real time: 388 gc time: 0
12
> (time (tak 18 12 6))
cpu time: 376 real time: 379 gc time: 0
18
> 

まあ、実際各自マシンで試してみてください。「意外と計算に時間がかかる」と思うでしょう。

ところで、風の噂で聞くには、この竹内関数、Haskellと言うプログラミング言語ではちょっぱやで計算終了しちゃうそうです。へえへえへえ。どうやら、Haskellの伝家の宝刀、遅延評価は竹内関数の天敵らしい。

遅延評価、と言えばSchemeも遅延評価を備えています。しかし今まで使い勝手が良く分からなかったんでマトモに触った事がありませんでした。
曰く、

評価しなければならない値が存在するとき、実際の計算を値が必要になるまで行わないことをいう。

………。
な～んか、日常生活的な感覚から言うとあまりに当たり前のような気もしますがねえ……。あまりにも当たり前の事が出来ないのが前提なら、コンピュータってメンド臭えな。マジな話、実感としてはそんな感じですよ。プログラミング言語の世界って日常生活的には当たり前の事を大げさに言ってる、ってたまに感じます。

脱線しますが、例えば、

彼女になりそうな女性が存在するとき、彼女が必要になるまで口説かない。

とか言われると当たり前でしょ(笑)?彼女がいるのに別の女性を口説いたりしたらそれは人非人と後ろ指さされる世の中です(笑)。僕がプライベートでどう言う行動を取ろうが関係なく、まあ、そうですよね(笑)。プログラミング言語で「遅延評価」とか言ってますが、人間の行動なんて多かれ少なかれ遅延評価、です。別に特別な話じゃない。
実際問題、コンピュータの世界では人間の「常識」がいまだ通用しない世界なんですね。前にも書きましたが、プログラミング言語に於ける「抽象性」と言うのは、人間の常識に近づいてる事だ、と言うのはこう言う事なんです。竹内関数がコンピュータでクソみたいに計算に時間がかかるのは、女と見れば見境なしに手を出してるロクデナシみたいな事をプログラミング言語が行っているから、です。そう言う評価形式を先行評価と呼ぶらしい。そして竹内関数はそう言う女ったらしに鉄槌を下す。
いずれにせよ、我々の世界では、遅延評価が当たり前で先行評価が「異常」です。しかし、プログラミング言語の世界では、まだまだ「我々の行動原理で言う異常」が当たり前ならしい。そしてプログラマはその世界にどっぷりと浸かってなれざるを得ない。

そんな中でHaskellとSchemeは「ちょっとだけ」僕等の常識に近いトコにいるんですよね。Haskellは遅延評価がデフォですが、Schemeではちょっと工夫しないとならない。いずれにせよ、早いトコ、もっと人間側の常識に従っているプログラミング言語が普及して欲しいものです。

さて、Schemeでのその「工夫」ですけど。マクロを使って次のようなifの亜種を作ります。名づけてlif(lazy-ifの意)です。

(define-syntax lif
  (syntax-rules ()
    ((_ _cond _then _else)
     (force (if (delay _cond)
  (delay _then)
  (delay _else))))))

ここでdelayはS式の評価を遅延させるための特殊形式です(出来たものをプロミスと呼びます)。そしてforceはプロミスを強制評価する為の手続きです。
このforceとdelayを同じマクロ内に書いても意味が無い、と思われるかもしれませんが、さにあらず。特殊形式ifは述語判定が行われないと第二引数ないしは第三引数が評価されません。しかしながら条件節自体がプロミスなので、評価ははじまりません。故にifが形作るS式は全体として評価が遅延されている。
また、マクロ自体もマクロ展開が行われないと評価が開始されません。そしてdelayのせいでどう言う展開形に落ち着くのか、はこのlifはまだ知らないのです。従って、forceも発動しようがないのです。
このマクロlifを使えば、ltak(lazy-takeuchi)手続きは次のようにオリジナルのtak手続きと殆ど同様に定義可能です。

(define (ltak x y z)
  (lif (<= x y)
       y
       (tak (tak (- x 1) y z)
     (tak (- y 1) z x)
     (tak (- z 1) x y))))

実際、インタプリタで計測してみましょう。恐ろしい程の竹内関数のベンチマークを叩き出します。

> (time (ltak 10 5 0))
cpu time: 0 real time: 0 gc time: 0
5
> (time (ltak 12 6 0))
cpu time: 0 real time: 0 gc time: 0
6
> (time (ltak 18 12 6))
cpu time: 0 real time: 0 gc time: 0
12
> 

全く計算時間がかかってない事が分かるでしょう。すげえ、ブラボー！！！Viva!遅延評価(笑)！！！
それどころか、マトモな竹内関数だったらいつ計算が終わるか分からない次のような大きな引数を与えても難なくltakは結果を返してくれます。

> (time (ltak 100 50 0))
cpu time: 0 real time: 0 gc time: 0
50
> 

すっごいですね～～。一瞬で答えを返してくれます。これも「値が必要になるまで評価しない」遅延評価版の竹内関数ならでは、の仕事です。オリジナルはよっぽど無駄な計算をしてるんでしょうね。こちらは不必要な計算は全く行わないので、迅速に計算結果が返ってくるのです。

面白いですね、遅延評価。また何かあったら使ってみたいな、と思います。