再帰の打ち切り

打ち切りによるパーツ構成

数値を用いた構文において必ず利用されるのは, 0以下の数値関数は消滅するという性質です.
これを再帰関数に応用すると, 再帰関数を打ち切ることができます.

a(X,T):XXXXa(sX,T-1)
a(r,10)

再帰関数

a(X):XXXXa(sX)
a(r)

が10回で打ち切られていることが分かると思います.

再帰的に構成できるパーツ複数の場所で使いたいときに便利な考え方ですね.
さらに引数を様々に変化させることで, 同じような再帰で書けるものを同時に定義できます.
つまり, 例えば上述の関数でも,

a(,6)

とすれば, 正面にたくさん進むパーツが得られますし,

a(rr,10)

とすれば, 長さ9の棒を正面に立てることができます.
場合によっては, 再帰関数を多変数化して幅を持たせる余分な引数を持たせる

a(X,Y,T):XXXXa(sYX,Y,T-1)

なんていうのも有効なときもあります.

a(r,,10)a(l,rsl,5)

などと育てる初項や育てる規則をある程度自在にコントロールできますね.

このように色んなパーツを兼ねた良い関数を定義するのは重要な問題意識だと思います.
ただし汎用性を持たせるために関数を膨らませすぎると, かえってバイト数がかさむので, さじ加減が難しいですね.

数値関数の右側

次に再帰関数の右側を利用することを考えます. 通常の再帰関数では,
バグを楽しむ以外の目的では, 基本的に実行されない部分ですね.

a(X,T):XXXXa(sX,T-1)srsl
a(r,10)

この例を調べると分かると思いますが, 数値関数の右側は,
数値が0になり再帰が行われなくなった途端に溜まっていた分が吐き出される仕組みです.
ここに方向転換や移動を混ぜることにより, より効率的にパーツを作れることがあります.

打ち切りによる繰り返し

「数値が0になった途端に右側が実行される」仕組みを利用して,
「再帰を打ち切って繰り返す」ことが可能になります.

a(X,T):lXlXsa(sX,T-1)a(l,9)
a(l,9)

a(l,9)が実行されて打ち切られた後再びa(l,9)が呼び出されることが分かるでしょう.
すると, 再びa(l,9)が実行されたあとでa(l,9)が呼び出されますね. したがってa(l,9)の無限ループに突入します.

a(X,T):lXlXsa(sX,T-1)sssra(l,9)
a(l,9)

などと, パーツ間に移動を挟むこともできます.

a(X,T):lXlXsa(sX,T-1)a(l,9)
a(l,5)

というように, 繰り返しの初項を特殊なものにすることもできますね.
12B構文?との複合も可能そうです.

a(X,T):lXlXsa(sX,T-3)a(l,T+10)
a(l,1)

また, 無限に繰り返したいだけが目的の場合は,

a(X,T):lXlXa(sX,T-1)a(l,9)
a(,1)

のように初項は何でも良かったりします.

不規則な打ち切り

再帰関数がある程度のところで止まるのは, 正の数から負の数への切り替わりにより,
突然再帰関数が呼び出されなくなることが原因でした. 基本的に数値が0以下か否かにより現象が変わるというわけです.

今度は, 負の数から正の数への切り替わりを利用してみましょう.

a(X,T):Xa(r,T-6)Xa(sX,T+1)
a(r,1)

a(r,T-6)の部分が最初の方は負で実行されず, 単なる再帰関数となっていますが,
T=7となった瞬間, 正の数が現れa(r,1)が実行されます.
しかも, 「XX」の間の, 再帰の中途半端な場所で打ち切りに成功しています.

このような打ち切りでは,

実行される→ある瞬間に実行されない

ではなく

実行されない→ある瞬間に実行される

という仕組みで実装する必要があるため, 負の数から正の数への切り替わりを利用することになります.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-02-03 (日) 14:05:05 (2082d)