たらい回しについて説明

どうも、たらい回しがよくわからないと言われたので、どうなっているのか説明してみるテスト。

まず、遅延じゃない方向でしてみる

(defun tarai (x y z)
  (if (<= x y)
      y
      (tarai (tarai (1- x) y z)
             (tarai (1- y) z x)
             (tarai (1- z) x y))))

を tarai(3 2 1)で呼び出してみよう。
if式はながいから3項演算子で書くことにした。

正則評価でやってみ...無理無理!!

 tarai(3 2 1)
=: 3 <= 2 ? 2 : tarai( tarai( (3-1) 2 1) tarai( (2-1) 1 3) tarai( (1-1) 3 2))
=: tarai( tarai( (3-1) 2 1) tarai( (2-1) 1 3) tarai( (1-1) 3 2))
=: tarai( tarai( 2 2 1) tarai( (2-1) 1 3) tarai( (1-1) 3 2))
=: tarai( tarai( (2<=2) ? 2 tarai( tarai((2-1) 2 1) tarai((2-1) 1 2) tarai( (1-1) 2 2))) tarai( (2-1) 1 3) tarai( (1-1) 3 2))
=: tarai( 2 tarai( (2-1) 1 3) tarai( (1-1) 3 2))
=: tarai( 2 tarai( 1 1 3 ) tarai( (1-1) 3 2))
=: tarai( 2 (1 <= 1) ? 1 : tarai(tarai( (1-1) 1 3) tarai( (1-1) 3 1) tarai( (3-1) 1 1)) tarai( (1-1) 3 2))
=: tarai( 2 1 tarai( (1-1) 3 2))
=: tarai( 2 1 tarai( 0 3 2))
=: tarai( 2 1 (0 <= 3 ? 3 : tarai( tarai((0-1) 3 2) tarai((3-1) 2 0) tarai(2-1) 0 3)))
=: tarai( 2 1 tarai( tarai((0-1) 3 2) tarai((3-1) 2 0) tarai(2-1) 0 3))
=: tarai( 2 1 ( tarai( tarai(-1 3 2) tarai((3-1) 2 0) tarai(2-1) 0 3)))
=: tarai( 2 1 ( tarai( ( -1 <= 3 ? 3 tarai(tarai((-1-1) 3 2) tarai((3-1) 2 -1) tarai((2-1) 3 -1))) tarai((3-1) 2 0) tarai(2-1) 0 3)))
=: tarai( 2 1 tarai( 3 tarai((3-1) 2 0) tarai(2-1) 0 3))
=: tarai( 2 1 tarai( 3 tarai(2 2 0) tarai(2-1) 0 3))
=: tarai( 2 1 tarai( 3 (2 <= 2 ? 2 : tarai(tarai((2-1) 2 0) tarai((2-1) 0 2 tarai((0-1) 2 2))) tarai(2-1) 0 3))
=: tarai( 2 1 tarai( 3 2 tarai( (2-1) 0 3)))
=: tarai( 2 1 tarai( 3 2 tarai( 1 0 3)))
=: tarai( 2 1 tarai( 3 2 ( 1 <= 0 ? 0 :tarai(tarai( (1-1) 0 3) tarai( (0-1) 3 1 tarai((3-1) 1 0)))))
=: tarai( 2 1 tarai( 3 2 tarai(tarai( (1-1) 0 3) tarai( (0-1) 3 1 tarai((3-1) 1 0)))))
=: tarai( 2 1 tarai( 3 2 tarai(tarai( 0 0 3) tarai( (0-1) 3 1 tarai((3-1) 1 0)))))
=: tarai( 2 1 tarai( 3 2 tarai((0 <= 0 ? 0 :tarai(tarai((0-1) 0 3) tarai(0-1) 3 0 tarai((3-1) 0 0))) tarai( (0-1) 3 1 tarai((3-1) 1 0)))))
=: tarai( 2 1 tarai( 3 2 tarai( 0 tarai((0-1) 3 0) tarai((3-1) 0 0 ))))
=: tarai( 2 1 tarai( 3 2 tarai( 0 tarai(-1 3 0) tarai((3-1) 0 0 ))))
=: tarai( 2 1 tarai( 3 2 tarai( 0 (-1 <= 3 ? 3 :tarai(tarai((-1-1) 3 0) tarai((3-1) 0 -1) tarai((0-1) 3 -1 ))) tarai((3-1) 0 0 ))))
=: tarai( 2 1 tarai( 3 2 tarai( 0 3 tarai((3-1) 0 0 ))))
=: tarai( 2 1 tarai( 3 2 tarai( 0 3 tarai(2 0 0 ))))

やってられっかー。

恐ろしい。進んでいる気がしない。

じゃあ遅延で、

遅延評価だから、前にでてきたのを定義で置き換えて評価する。その際に前にでてきたのと同じ式は評価結果で置き換える。

 tarai(3 2 1)
=: 3 <= 2 ? 2 : tarai( tarai((3-1) 2 1) tarai((2-1) 1 3) tarai((1-1) 3 2))
=: tarai( tarai((3-1) 2 1) tarai((2-1) 1 3) tarai((1-1) 3 2))
=: tarai((3-1) 2 1) <= tarai((2-1) 1 3) ? tarai((2-1) 1 3) : tarai(tarai(tarai((3-1) 2 1)-1 tarai((2-1) 1 3) tarai((1-1) 3 2)) tarai(tarai((2-1) 1 3)-1 tarai((1-1) 3 2) tarai((3-1) 2 1)) tarai(tarai((1-1) 3 2)-1 tarai((3-1) 2 1) tarai((2-1) 1 3)))
=: ((3-1)<= 2 ? 2 : tarai(tarai(((3-1)-1) 2 1) tarai((2-1) 1 (3-1)) tarai((1-1) (3-1) 2)) <= tarai((2-1) 1 3) ? tarai((2-1) 1 3) : tarai(tarai(tarai((3-1) 2 1)-1 tarai((2-1) 1 3) tarai((1-1) 3 2)) tarai(tarai((2-1) 1 3)-1 tarai((1-1) 3 2) tarai((3-1) 2 1))tarai(tarai((1-1) 3 2)-1 tarai((3-1) 2 1) tarai((2-1) 1 3)))
=: (2<= 2 ? 2 : tarai(tarai((2-1) 2 1)tarai((2-1) 1 2)tarai((1-1) 2 2)) <= tarai((2-1) 1 3) ? tarai((2-1) 1 3) : tarai(tarai(tarai(2 2 1)-1 tarai((2-1) 1 3) tarai((1-1) 3 2))tarai(tarai((2-1) 1 3)-1 tarai((1-1) 3 2) tarai(2 2 1))tarai(tarai((1-1) 3 2)-1 tarai(2 2 1) tarai((2-1) 1 3)))
=: 2 <= tarai((2-1) 1 3) ? tarai((2-1) 1 3) : tarai(tarai(2-1 tarai((2-1) 1 3) tarai((1-1) 3 2))tarai(tarai((2-1) 1 3)-1 tarai((1-1) 3 2) 2) tarai(tarai((1-1) 3 2)-1 2 tarai((2-1) 1 3))) 
=: 2 <= ((2-1) <= 1 ? 1 :tarai(tarai(((2-1)-1) 1 3) tarai((1-1) 3 (2-1)) tarai((3-1) (2-1) 1)) ? tarai((2-1) 1 3) : tarai(tarai(2-1 tarai((2-1) 1 3) tarai((1-1) 3 2))tarai(tarai((2-1) 1 3)-1 tarai((1-1) 3 2) 2) tarai(tarai((1-1) 3 2)-1 2 tarai((2-1) 1 3)))
=: 2 <= 1 ? 1 : tarai(tarai(1 1 tarai((1-1) 3 2)) tarai(1-1 tarai((1-1) 3 2) 2)tarai(tarai((1-1) 3 2)-1 2 1))
=: tarai(tarai(1 1 tarai((1-1) 3 2)) tarai(1-1 tarai((1-1) 3 2) 2) tarai(tarai((1-1) 3 2)-1 2 1))
=: (tarai(1 1 tarai((1-1) 3 1)) <= tarai(1-1 tarai((1-1) 3 2) 2) ? tarai(1-1 tarai((1-1) 3 2) 2) ) : tarai(tarai(1 1 tarai((1-1) 3 1))-1 tarai(1-1 tarai((1-1) 3 2) 2) tarai(tarau((1-1) 3 2)-1 2 1) tarai(1-1 tarai((1-1) 3 2) 2)-1 tarai(tarau((1-1) 3 2)-1 2 1) tarai(1 1 tarai((1-1) 3 1)) tarai(tarau((1-1) 3 2)-1 2 1)-1 tarai(1 1 tarai((1-1) 3 1)) tarai(1-1 tarai((1-1) 3 2) 2))

もう無理...