次のような短縮は,ある程度Herbertをプレイした方なら(?)馴染み深いと思います:
a(X):XrXra(sX)今回は,このような感じの短縮について整理しましょう.
a()
↓
b(Y):YYb(sY)
b(r)
上記のパターンは比較的簡単ですね.「a(X):****a(pX)」という成長をさせている場合,
初項としてa(q)と与えておくと,Xの部分が「ppppppq」というように,
繰り返しの後にqがついたものを表すようになります.
同じように,「a(X):****a(Xp)」という成長をさせると,
初項としてa(q)と与えておくと,Xの部分が「qpppppp」というように,
繰り返しの手前にqがついたものになるというわけです.
もう少し複雑な書き変えをしてみましょう.例えば
a(X):XrXrXrXra(XrXlX)というコードがあったとします.実行部分はXrばかりなので,ちょっと
a(s)
上記のコードを正しく変換すると,次のようになります:
b(Y):YYYYb(YYllY)合計3B縮みました.こういう変数変換を理解しておくと役に立つこともあると思うので説明しておきましょう.
b(sr)
再帰のn段階目のXやYをX[n],Y[n]などと表すことにします.「Y[n]=X[n]r」という変換をすればいいわけです.
次のような式変形は数列の漸化式などで習ったことがあるかもしれません.
Y[1]=X[1]r=sr,特に細部の説明は不要ですよね?いくつか演習としてみるので書き変えてみてください.
Y[n+1]=X[n+1]r=X[n]rX[n]lX[n]r=(Y[n]l)r(Y[n]l)l(Y[n]l)r=Y[n]lrY[n]llY[n]lr=Y[n]Y[n]llY[n]
「変数変換」に該当するかは微妙ですが,「方向転換をどこに入れるか」短縮出来る例をいくつか紹介しましょう.
まず覚えておいた方が良いのは次のようなパターンです:
a(X):l **** ra(**), a(**)Xの変化規則など全く関係なく,「l****r」となっている時点でこれは1Bの損をしています.
[l*****r][l******r][l******r][l******r]…となっていて毎回「rl」が挟まるのがいかにも無駄な感じですよね.実際には
a(X):****a(**), l a(**)と最初にlを避けておくことで1Bの短縮ができます.
逆に
a(X):****a(**), la(**)を
a(X):l****ra(**), a(**)と書き直すことで短縮につながることもあります.例えば
a(X):l****la(**), la(**)とかなっていると1B縮みますね.
もうちょっと複雑な例を扱ってみましょう.例えば次のコードを見てください. なるべく短く書くとどうなるでしょうか?
a(X):rXXXXa(XlX)答えに至るまでの考え方と共に丁寧に説明してみることにします.
ra(sr)
「このまま見ても縮まないけど…」というときは,一旦
「変数を方向転換を含まない形に戻して」考えるとよいです.この場合,
a(X):rXrXrXrXra(XX)と戻すことが出来ます.さらに最初のrを中に入れると
ra(s)
a(X):rrXrXrXrXrla(XX)つまり
a(s)
a(X):rrXrXrXrXa(XX)となりますね.すると,Xrは3度,rXは4度現れており,「Xrを新しい変数と思う」という変換よりも
a(s)
b(Y):rYYYYa(YlY)と書き直すことで最初のコードよりも1Bの短縮に成功しました!
b(rs)
ある程度慣れてくるとこの手の書き換えは割と感覚的に出来るようになります.
でも複雑な状況になってくると間違えやすくなってきたり,最適化した自信がなくなることも多いです.
ちゃんと原理を理解しているとどんな場面でもかなり自信を持って最適化できるのではないでしょうか?
こういう変数変換のが理解できてくると,