思い立って先週から作っていた部分評価器がだいたい動いた。
fun ev(exp,env)
specialize exp;
{
if (nth(exp,0) == "lit") { nth(exp,1) }
else if (nth(exp,0) == "var") { lookup_assoc(env, nth(exp,1)) }
else if (nth(exp,0) == "lambda") { @ x { ev(nth(exp,2), bind_assoc(env, nth(exp,1), x)) } }
else if (nth(exp,0) == "call") { ev(nth(exp, 1), env)(ev(nth(exp,2), env)) }
else { raise() }
}
export fun foo(env) {
ev(ary3("call", ary2("var", "x"), ary2("var", "y")),env)
}
という入力プログラムを部分評価 (に加えていくつか簡約) すると foo の部分が
export fun foo(_78_env)
{
_79_tmp = lookup_assoc(_78_env, "x");
_80_tmp = lookup_assoc(_78_env, "y");
_81_tmp = _79_tmp(_80_tmp);
_81_tmp
}
にまで展開される。
もちろん定番の pow も動いて、
fun pow(x,y)
specialize y;
{
if (y == 0) { 1 }
else { x * pow(x, y-1) }
}
export fun cube(x) {
pow(x,3)
}
という cube が
export fun cube(_34_x)
{
_35_tmp = _34_x*_34_x;
_36_tmp = _34_x*_35_tmp;
_36_tmp
}
となる。
しかし考えてみると、この pow は定番ではあるが、引数に比例してコードが大きくなって剣呑である。
コードサイズを log くらいに落とすのは以下のようにすればよい。
fun pow(x,y)
specialize y;
{
if (y == 0) { 1 }
else if (y & 1 == 0) { pow(x*x, y >> 1) }
else { x * pow(x*x, y >> 1 ) }
}
export fun pow73(x) {
pow(x, 73)
}
とすれば
fun pow73(_89_x)
{
_90_tmp = _89_x*_89_x;
_91_tmp = _90_tmp*_90_tmp;
_92_tmp = _91_tmp*_91_tmp;
_93_tmp = _92_tmp*_92_tmp;
_94_tmp = _93_tmp*_93_tmp;
_95_tmp = _94_tmp*_94_tmp;
_96_tmp = _92_tmp*_95_tmp;
_97_tmp = _89_x*_96_tmp;
_97_tmp
}
となる。
「部分評価」も「部分計算」も検索すると違う意味のがかなり出てくるなぁ
実装していて思ったのだが、部分評価がインライン展開+定数伝播と違うのは生成された結果に再帰的な呼出し関係をつくり出せるかどうかなのではないか。
ev も pow もそういうケースではないのがなんだが...
再帰が残るケースの partial evaluation を試してみる
ちょっと人工的だが、3の倍数を検査してみよう
ここでは、3の倍数を人間が検査するやりかたを真似ている。人間がやるのは 10進数での各桁を足してそれが 3 の倍数かというやりかたであるが、ここでは 4進数で行う。(4 も 10 も 3 を法として 1 なので仕掛けは同じである。10進でやってもいいのだが、そうすると 10による割算が必要になる。4進ならビット演算で済む)
fun check3(n, d)
specialize d;
{
if (3 <= d) {
check3(n, d-3)
}
else {
if (n == 0) {
if ((d == 0) | (d == 3))
"yes"
else
"no"
}
else {
n2 = n >> 2;
d2 = n & 3;
if (d2 == 0) { check3(n2, d) }
else if (d2 == 1) { check3(n2, d+1) }
else if (d2 == 2) { check3(n2, d+2) }
else { check3(n2, d+3) }
}
}
}
export fun multiple_of_3(n)
{
check3(n, 0)
}
というのが、以下のように展開される (ちょっと単純化して、あと名前は適当に変えてある)
export fun multiple_of_3(n) {check3_0(n)}
fun check3_0(n)
{
if (n==0) "yes"
else {
n2 = n>>2;
d2 = n&3;
if (d2==0) check3_0(n2)
else if (d2==1) check3_1(n2)
else if (d2==2) check3_2(n2)
else check3_0(n2)
}
}
fun check3_1(n)
{
if (n==0) "no"
else {
n2 = n>>2;
d2 = n&3;
if (d2==0) check3_1(n2)
else if (d2==1) check3_2(n2)
else if (d2==2) check3_0(n2)
else check3_1(n2)
}
}
fun check3_2(n)
{
if (n==0) "no"
else {
n2 = n>>2;
d2 = n&3;
if (d2==0) check3_2(n2)
else if (d2==1) check3_0(n2)
else if (d2==2) check3_1(n2)
else check3_2(n2)
}
}
結果として、相互再帰を行う check3_0, check3_1, check3_2 が生成されているが、これはインライン展開+定数伝播では生成できない。
ところで、check3_0, check3_1, check3_2 は、実際のところオートマトンである。末尾呼出しを最適化すれば、そのまま動かしても問題ない。
そーか。C って末尾呼出しの最適化はできないんだな。
... いや、C の範囲内でできないのは常識。
気がついたのは、ポータブルでない方法 (つまりアセンブラ) を使っても無理な場合があるということ。
x86 の普通の calling convention では、呼出し側で引数をスタックに push した後に関数を call し、返ってきたら引数を pop する。
では、呼び出された関数が tail call するときに引数はどう渡せばいいか。
ret した時点でのスタックポインタは変えられない。変えると、返ったあとの呼出元で困る。
そうすると、tail call 時点でのスタックポインタも変えられない。
すると、引数を増やせないことになる。
MetaML で (任意の大きさの) オートマトンを生成できるか調べてみる。
うぅむ。状態に対応する関数を順々に生成していくとすると、最初に生成するときには未生成の状態を参照することはできないので、無理っぽい気がする?
Evolution of Partial Evaluators: Removing Inherited Limits, Torben Mogensen
を読む。とても面白い。
Ruby で試すなら、sysread, syswrite でいいと思うけど。
O_NONBLOCK をつけていいなら、read_nonblock, write_nonblock も使える。こいつらはバッファが空なら (O_NONBLOCK にしてから) read/write システムコールを 1回だけ発行して、結果を見せてくれる。
pipe の大きさが 65536byte とか一発でわかるし、
% uname -a
Linux nute 2.6.18-6-486 #1 Mon Aug 18 08:05:56 UTC 2008 i686 GNU/Linux
% ruby -rsocket -e '
r, w = IO.pipe
p w.write_nonblock("a" * 100000)
p w.write_nonblock("a" * 100000)
'
65536
-e:4:in `write_nonblock': Resource temporarily unavailable (Errno::EAGAIN)
from -e:4:in `<main>'
unix domain socket は 112896byte なのね、とか、
% ruby -rsocket -e '
s1, s2 = UNIXSocket.pair
p s1.write_nonblock("a"*1000000)
p s1.write_nonblock("a"*1000000)
'
112896
-e:4:in `write_nonblock': Resource temporarily unavailable (Errno::EAGAIN)
from -e:4:in `<main>'
tcp はなんか 2回書けちゃうとか、
% ruby -rsocket -e '
serv = TCPServer.new(1111)
s1 = TCPSocket.open("127.0.0.1", 1111)
s2 = serv.accept
p s1.write_nonblock("a"*1000000)
p s1.write_nonblock("a"*1000000)
p s1.write_nonblock("a"*1000000)
'
49152
98304
-e:7:in `write_nonblock': Resource temporarily unavailable (Errno::EAGAIN)
from -e:7:in `<main>'
1秒待つとさらにもう一回書けちゃうとか、
% ruby -rsocket -e '
serv = TCPServer.new(1111)
s1 = TCPSocket.open("127.0.0.1", 1111)
s2 = serv.accept
p s1.write_nonblock("a"*1000000)
p s1.write_nonblock("a"*1000000)
sleep 1
p s1.write_nonblock("a"*1000000)
sleep 1
p s1.write_nonblock("a"*1000000)
'
49152
98304
49152
-e:10:in `write_nonblock': Resource temporarily unavailable (Errno::EAGAIN)
from -e:10:in `<main>'
待ちかたを変えるともっと書けちゃうとか、
% ruby -rsocket -e '
serv = TCPServer.new(1111)
s1 = TCPSocket.open("127.0.0.1", 1111)
s2 = serv.accept
p s1.write_nonblock("a"*1000000)
sleep 1
p s1.write_nonblock("a"*1000000)
p s1.write_nonblock("a"*1000000)
sleep 1
p s1.write_nonblock("a"*1000000)
sleep 1
p s1.write_nonblock("a"*1000000)
'
49152
131072
16384
16384
-e:12:in `write_nonblock': Resource temporarily unavailable (Errno::EAGAIN)
from -e:12:in `<main>'
unix domain socket は 92byte 書くと select で writable でなくなるとか、
% ruby -rsocket -e '
s1, s2 = UNIXSocket.pair
n = 0
loop {
n += s1.write_nonblock("a")
p n
IO.select(nil, [s1])
}
'
1
2
...
91
92
いや、92byte じゃなくて 92回なのだろうか、とか、
% ruby -rsocket -e '
s1, s2 = UNIXSocket.pair
n = 0
loop {
n += s1.write_nonblock("aa")
p n
IO.select(nil, [s1])
}
'
2
4
...
182
184
unix domain socket は 112896byte 埋めつくした後 96767byte 読み出すと writable になるとか、
% ruby -rsocket -e '
112896.downto(0) {|n|
s1, s2 = UNIXSocket.pair
w = s1.write_nonblock("a"*1000000)
r = s2.read_nonblock(n).length
p [w,r]
IO.select(nil, [s1])
}
'
[112896, 112896]
[112896, 112895]
...
[112896, 96768]
[112896, 96767]
まぁ、結局よくわかんないのでてきとうにやってください。
個人的には、こんなのつきあってられん、という感じです。
Software Fault Interactions and Implications for Software Testing, D. Richard Kuhn, Dolores R. Wallace, Albert M. Gallo, IEEE Transactions on Software Engineering, June 2004 (Vol. 30, No. 6)
を読む。
いろんなソフトウェアで、多くのバグは少ない条件で発症させられる、という話である。
第2、第3著者は NASA のひとで、それが関係あるのかどうかはわからないが、宇宙開発での例がいくつかでてくる。Ariane 5 の例は少ない条件で発症するバグだったが、Mars Pathfinder の例は複雑な条件で発症するバグだったとか。
USS Yorktown というのも書いてあったが... これは宇宙開発じゃないな。ミサイル巡洋艦か。
黄金比というのは知っていたが、白銀比というのは知らなかった。
... いや、名前を知らなかっただけか?
[latest]