![[PukiWiki]](image/hojwiki.png "[PukiWiki]")
次のような短縮は，ある程度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) a(s)
というコードがあったとします．実行部分はXrばかりなので，ちょっと変数を変換すれば「a(X):XXXX」の形で書けるはずです．
さっと間違わずにできますか？？上記のコードを正しく変換すると，次のようになります：
b(Y):YYYYb(YYllY) b(sr)
合計3B縮みました．こういう変数変換を理解しておくと役に立つこともあると思うので説明しておきましょう．
再帰の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]
特に細部の説明は不要ですよね？いくつか演習としてみるので書き変えてみてください． 全部実行を「XXXX」の形にしてみましょう．
a(X):XrXrXrXra(XXX) a(s)
a(X):XrXrXrXra(XXl) a(s)
a(X):XlXlXlXla(XXl) a(s)
a(X):XlXlXlXla(srslXss) a(ll)
答えは一番下にでも．
「変数変換」に該当するかは微妙ですが，「方向転換をどこに入れるか」で
短縮出来る例をいくつか紹介しましょう．まず覚えておいた方が良いのは次のようなパターンです：
a(X):l **** ra(**) a(**)
Xの変化規則など全く関係なく，「l****r」となっている時点でこれは1Bの損をしています． 再帰の1段階目，2段階目，…という境目の部分を考えると
[l*****r][l******r][l******r][l******r]…
となっていて毎回「rl」が挟まるのがいかにも無駄な感じですよね．実際には
a(X):****a(**) la(**)
と最初にlを避けておくことで1Bの短縮ができます．逆に
a(X):****a(**) la(**)
を
a(X):l****ra(**) a(**)
と書き直すことで短縮につながることもあります．例えば
a(X):l****la(**) la(**)
とかなっていると1B縮みますね．
もうちょっと複雑な例を扱ってみましょう．例えば次のコードを見てください． なるべく短く書くとどうなるでしょうか？
a(X):rXXXXa(XlX) ra(sr)
答えに至るまでの考え方と共に丁寧に説明してみることにします．
まず，このコードの経路は「長さ1，長さ2，長さ4，……」という正方形を描くものです．
長さが2倍ずつになっているので，「a(X):****a(XX), a(s)」と書けるのを，4倍することを見越して
方向転換を組み込んだ形で変数を置いています．これで十分上手に書けているようですが，
損をしている部分があるのです．
「このまま見ても縮まないけど…」というときは，一旦
「変数を方向転換を含まない形に戻して」考えるとよいです．この場合，
a(X):rXrXrXrXra(XX) ra(s)
と戻すことが出来ます．さらに最初のrを中に入れると
a(X):rrXrXrXrXrla(XX) a(s)
つまり
a(X):rrXrXrXrXa(XX) a(s)
となりますね．すると，Xrは3度，rXは4度現れており，「Xrを新しい変数と思う」という変換よりも
「rXを新しい変数と思う」という変換で短縮をする方が賢いということが分かると思います．
あとはY=rXとおいて変数変換して
b(Y):rYYYYa(YlY) b(rs)
と書き直すことで最初のコードよりも1Bの短縮に成功しました！
ある程度慣れてくるとこの手の書き換えは割と感覚的に出来るようになります．
でも複雑な状況になってくると間違えやすくなってきたり，最適化した自信がなくなることも多いです．
ちゃんと原理を理解しているとどんな場面でもかなり自信を持って最適化できるのではないでしょうか？
さて，途中に挙げた問題の解答を載せておきます：
b(Y):YYYYb(YlYlY) b(sr)
b(Y):YYYYb(YlYl) b(sr)
b(Y):YYYYb(YrYl) b(sl)
b(Y):YYYYb(lsrsYllssll) b(r)
4つめのは辛うじて得をした感じですが，「育てる向きと反対向きに繰り返す」ような感じになって いるので上手なコードには見えないですねぇ…．あまり上手く書けないときは経路取りをやり直した方がいいかも． こういう変数変換のが理解できてくると，
みたいな現象も説明することが出来そうですね．
