花見しに大阪へ行ってきます。 往復に高速バスを使って安くあげようと思ったのに切符が取れなかったので、 ヤケになってのぞみを使うことにしました。一度乗ってみたかったんだ。
たらいまわし関数と Haskell の話の続きです。 3/23 の原先生のツッコミより。
> 非正格ってnon-strictの訳ですよね。 > この「non〜」っていう用語が不思議な気がします。 > 非正格ならこのような最適化を必ずするのでか？ > それともこれは最適化ではなく、非正格なら自動的に > そういう計算の仕方をしてしまうのでしょうか。
必ずするわけじゃないと思います。 ぼくも勉強中なんであんまり深いことは言えませんが、 山下さんの受け売りで説明してみます。
Ruby で次のような式を計算すると、
f(g(1), g(2))
まず引数の g(1) と g(2) を計算して、それを f に渡します。 しかし Haskell では式のどこから計算されるかが決まっていません。 つまり f を展開してしまったあとに g(1) や g(2) を計算できます。
結果として次のようなことが起こります。Ruby で以下のような関数を書くと、 g(1) か g(2) どちらかの計算時間が必ず無駄になります。
def my_if( cond, t, f )
if cond
t
else
f
end
end
p my_if(true, g(1), g(2))
しかし Haskell だと先に my_if を展開してしまうことができるため、 g(1) と g(2) のどちらかは無駄になることがあらかじめわかるんです。 だからまず cond だけ計算してみて、 その後で t か f のどちらかだけを求めるということができます。 つまり g(1) か g(2) のどちらかはそもそも計算されずに終わります。 たらいまわし関数の計算が速いのはこのようなことが各所で起こるからです。
具体的に見てみると、
tarai :: Int -> Int -> Int -> Int
tarai x y z
| x <= y = y
| otherwise = tarai (tarai (x-1) y z)
(tarai (y-1) z x)
(tarai (z-1) x y)
三行目は「x <= y の場合は y」と記述しているんですが、 この場合 z は関係がありません。つまりそもそも計算しなくてよいわけです。 だから Haskell で計算するとかなり計算量が減って速くなるという仕組みです。
ところが John McCarthy が間違ったバージョン (竹内関数) では
tak :: Int -> Int -> Int -> Int
tak x y z
| x <= y = z
| otherwise = tak (tak (x-1) y z)
(tak (y-1) z x)
(tak (z-1) x y)
となっていて、x <= y のときは z を返すことになってます。 だからどの場合でも z の計算は省略できません。 結果として non-strict だろうが strict だろうが同じ計算量になるわけです。
Copyright (c) 2002-2007 青木峰郎 / Minero Aoki. All rights reserved.
先日のSICPではどうも。
TAKyとTAKzがあるんですね。知らんかったです。Mathematica計算の楽しみ（ヴァルディ）に実行時間の話があるけど、当方難しくて理解不能。原始帰納的関数ではないけど計算可能なのか？
Hugsでやってみたら tak 12 6 0 の結果は１だった。SMLでやると１２になる。なぜ？？？
すみませ〜ん。tarai(TAKy)とTak(TAKz)を取り違えてました。
非正格も正格も同じ計算結果、しかしHaskellの方がダントツに速い。
なるほどねぇ。さすが言語レベルで遅延評価をサポートしてると違いますね。
class Tarai
include Comparable
def initialize(x, y, z)
@x, @y, @z = x, y, z
@t = 0
end
def tarai_inspect(level = 3)
return "?" if (level -= 1) < 0
s = "Tarai(" <<
[@x, @y, @z].map {|x| Tarai === x ? x.tarai_inspect(level) : x}.join(", ") <<
")"
s << ("%#d" % @t) unless @t.zero?
s
end
def +(val)
@t += val
end
def -(val)
@t -= val
end
def <=>(val)
to_int() <=> val.to_int
end
def coerce(val)
case val
when Integer
[val, to_int()]
else
super
end
end
def to_int
@t += if !@x
0
elsif @x <= @y
@y
else
Tarai.new(Tarai.new(@x-1, @y, @z),
Tarai.new(@y-1, @z, @x),
Tarai.new(@z-1, @x, @y)).to_i
end
@x = nil
@t
end
alias to_i to_int
def to_s
to_i.to_s
end
end
if $0 == __FILE__
a = 12, 6, 0
ARGV.each_with_index {|v, i| a[i] = v.to_i}
t = Tarai.new(*a)
puts "#{t.inspect} = #{t}"
end
あ、なるほど。最適化じゃなくて、引数に対する遅延評価なんですね。
こうすると Ruby でもそれっぽくなるかな。
class Integer
def call; self; end
end
class Proc
def -(x); proc{call - x.call}; end
end
def tarai( x, y, z )
if x.call <= y.call
then y.call
else
tarai(proc{tarai(x-1, y, z)},
proc{tarai(y-1, z, x)},
proc{tarai(z-1, x, y)})
end
end
puts tarai(12, 6, 0)