3. DNA から RNA へ
右側の酵素に触れることにより、Fuun の DNA は変化しながら、RNA を作り出しはじめます。これを、「"DNA文字列"を実行する」と呼びます。泥臭いこと（化学的な意味で）は Arrow がよきにはからってくれるので、われわれはアルゴリズムの記述に専念することができます。以下は、Arrow によって与えられた（Fuun の DNA に関する）概要です。地球の変態諸氏の読みやすいように書き直してあります。
前述のとおり、DNA は図2で定義された塩基配列です。
塩基として I, C, F, P の4つが利用可能で、引用符によってDNA文字列であることを示します。例えば "ICFP" などです。結果として生成される RNA は、DNA 文字列のシーケンスです。
シーケンスは、DNA 文字列の実行にあたり重要な役割を担います。シーケンスは、ゼロかより多くの要素から成ります。シーケンスにおいての基本的な操作と、その記法を図3に示します。図3の操作はいずれも失敗せず、ゼロベースであることに注意してください。
サブシーケンス命令は、シーケンスの範囲外を指定したり、長さが 0 以下の範囲を指定したりすると、空のシーケンス ε を返します。範囲内を指定したとき、その部分をシーケンスとして返します。また、添字操作の例外としても ε を使います。図4は DNA 文字列に対して操作をするいくつかの例を示しています。
図5で与えられている DNA の実行の全体的な流れを見て見ましょう。このアルゴリズムは、21行目で宣言されているグローバルな DNA シーケンスに対して動作します。まず、初期 DNA が読み込まれます。初期 DNA は、コンテストの Web ページからダウンロードできる遠藤の DNA とあとに続く prefix（我々が求めることになっている）から成ります。
例外的な状態に至る（DNA 文字列が完全に消費される）まで、以下の3ステップが繰り返されます。
- DNA の接頭辞をパターンに変換(26行目)
- 残りの DNA の接頭辞をテンプレートに変換(27行目)
- 残りの DNA に対してパターンマッチを行い、テンプレートを使用して新しい DNA を生成
この手続きは、最終的な RNA 文字列を出力して、プログラムを終えます。そして、ビルドプログラムにその RNA 文字列を渡します。以降では、それぞれのステップを詳細に見ていきます。
3.1 パターンの解読
図6にパターンの構文を示します。パターンは一連のパターンアイテムからなり、パターンアイテムには次の5種類があります。
- 「I」, 「C」, 「F」, 「P」 からなる塩基アイテム（34行目）
- n 個の塩基をスキップするアイテム 「!n」 （35行目）
- DNA 配列 s を探すアイテム 「?s」 （36行目）
- グループを開閉する2つのアイテム 「(」 と 「)」 （37-38行目）
パターンの認識は関数 pattern によって実行されます。そして、それは図7に示されます。
関数 pattern はグローバル変数 dna を読み込み、その一部を消費します。そして、途中で局所変数 p にパターン（40行目）を保存します。現在のグループレベル（自然数）は、局所変数 lvl （41行目）に保存されます。変数を初期化した後はループに入ります。各々の繰り返しにおいて、我々は DNA の現在の prefix に従い分岐します。1つの分岐は、繰り返すたびに実行されます！
最初の4つのケースは、恒常的なアイテム（44-47行）を生成します。5回目の事例は、『スキップ』アイテム（第48行）を生成します。最初の『IP』を消費した後に、nat 関数は、dna から自然数 n を取得するために呼ばれます。nat 関数は、セクション3.2で記述されます。自然数 n は、『スキップ』アイテムのパラメータになります。
6回目の事例は『検索』アイテム（第49行）を生産します。このアイテムにはパラメータとして塩基シーケンスが渡されます。したがって、最初の『IF』とさらに1つの塩基を消費した後に、consts 関数（セクション3.2で記述される）は DNA 文字列化された塩基シーケンス s を検索するために呼ばれます。そして、それは consts 関数から発生するアイテムのパラメータになります。7回目の事例は『開いた』アイテム（第50行）を生産して、同時に lvl 変数を増加させます。
dnaの先頭が『IIC』または『IIF』（第51行）であるならば、8回目の事例に合致します。両方の場合とも、dna の先頭にある3つの塩基は削除されます。現在のlvlが0であるならば、パターン認識はこの点で終わります。そして、関数 pattern は p に代入されたパターンを返却します。lvl が正数であるならば、それはデクリメントされます。そして、『閉じる』アイテムが生産されます（第54行）。
（図7: パターン認識）
（図8: パターン認識の例）
dna の最初の3つの塩基が『III』であるならば、次の7つの塩基は RNA 命令を作って、出力シーケンス rna に加えられます。ここで、10個の塩基（3つの I と RNA 命令）が消費されます（第56行）。RNA 命令は DNA 変化プロセスの次の段階であり、チャプタ4で記述されています。
与えられた prefix のどれも合わないならば、DNA 解読の終わりも近いといえます。RNA を出力してプログラムを終了する関数 finish を呼ぶことによって、最後のケースは終了します（57行）。パターン認識の仕様では、与えられた prefix のどれも合わないか、認識プロセスが順調に進み、lvl が 0 と等しいときに繰り返しの始めに『IIC』または『IIF』と遭遇することによって、プログラムは終了します。pattern 関数によって返されるパターンの括弧は、常にバランスが保たれます。
図8は、pattern 関数の2つの例呼び出しを提示します。2番目のケースでは、次に記述される自然数エンコードを利用します。
（図10: テンプレート）
3.2 ヘルパー関数群
ここでは、パターン認識とテンプレートの間で利用される nat と consts について記述します。どちらも、図9にあるように非常に似通った構造をしています。
関数 nat は、大域変数 dna から自然数を解読します。次のPまでのすべてを読み込みます。基本的に、I と F は 0 として解釈されます。P が見つかる前にDNA文字列が終了すれば（＝ DNA 文字列に P が含まれていなければ）、RNA 文字列を出力して終了します。関数 consts は塩基配列（つまり DNA 文字列）を解読します。DNA 文字列のはじめが 'IC', C, F, P からはじまれば、それを取り除いて再帰的に関数 consts を呼び出します。どれにも該当しなければ終了します。
3.3 テンプレートの解読
DNA 文字列からテンプレートを解読するフェイズは、パターンを認識するフェイズとほとんど同様に行われます。テンプレートの構文は図10で説明されています。テンプレートは一連のテンプレートアイテムからなり、アイテムは次の3点を満たします。
- 塩基を表すアイテム（78行目）は「I」「C」「F」「P」に一致する
（図11. パターン認識）
- 保護レベル l 付きの参照番号 n のためのアイテム（79行目）は nl で表される
- 参照 n の長さをエンコードしたアイテム (80行目)は |n| で表される
テンプレートの解読は、図11にあるようにtemplate関数で実行されます。1つの局所変数（Template:t）しか存在しないので、この関数の構造は pattern 関数よりも少し単純です。テンプレートのグループは存在しないので、現在のグループレベルの経過を追う必要はありません。
変数 t の初期化の後、残りのテンプレート解読はループによって行われます。それぞれのループにおいて、dna の現在の内容が解析されます。prefix に従い、分岐のうちひとつが選ばれます。定数アイテムを表すケース（85-88行目）と RNA を生成するケース（92行目）とそれ以外のすべてに対応するケース（93行目）は、pattern 関数（セクション3.1を参照せよ）と全く同様になっています。
『IF』または『IP』prefix で、『参照』アイテムは発生します: prefix を消費した後に、2つの自然数 l と n が DNA 文字列からデコードされ、セクション3.2の nat 関数に渡されます。そして、アイテム nl が発生します（第89行）。prefix『IIC』または『IIF』は、テンプレートの端をマークします。これらの prefix は消費され、t の現在の内容が template 関数から返却されます（90行目）。
prefix『IIP』は、『長さ』アイテム |n| を生成します。ここで、n は3個の塩基が取り除かれたあとに解読される prefix の長さを表しています（91行目）。
3.4 パターンマッチング
関数 matchreplace は、図12に示されます。この関数は2つの引数として、DNA からデコードされた（そして削除される）パターン pat とテンプレート t を取ります。関数 matchreplace において、我々は pat と dna 文字列を読み込み、dna の内容と pat 中のパターンアイテムを照合しようとします。それぞれのパターンアイテムが適切に解析される間、我々は変数 i（98行目）にDNA文字列における現在の位置を保持します。
（図12. パターンマッチング）
マッチング処理を行っている間、我々は環境 e を作り上げます。環境は一連の DNA 文字列からなり、それぞれの文字列はグループ（「開く」アイテムと「閉じる」アイテムの間にあるすべて）にマッチした DNA の一部を表します。
局所変数を初期化したあと、それぞれの pat 中のパターンアイテム p は適切に考慮されます。塩基 b を表すパターンが DNA 文字列の現在の位置 i に存在するならば、塩基 b はマッチします。マッチすれば i はインクリメントされ、もしそうでなければ（あるいは位置 i が DNA 文字列の終端を越えていれば）、マッチは失敗し、我々は dna を更新することなく関数から抜けます。
「スキップ」アイテムがあれば、現在の位置はこのアイテムに従って調節されます（107行目）。もし新しい位置がDNA文字列の範囲を超えるのであれば、マッチは失敗します。
「検索」アイテムがあれば、我々は dna から文字列 s を検索し、最初に一致する部分を取り除きます。検索が成功し、n が 文字列 s の終端に続く最初の位置であるならば、我々は i を n に代入します（109-110行目）。もし、文字列 s が dna[i] に含まれないのであれば、マッチは失敗します。
「開く」アイテムがあれば、我々は現在の位置 i を開始位置 c に保存します（113行目）。
（図13. 置換）
「閉じる」アイテムがあれば、我々は対応する「開く」アイテムの位置を取得するために、変数 c を読み出します。その位置と現在の位置 i の間の範囲は、現在のグループにマッチするアイテムの部分を表します。そして、我々はこの範囲を環境 e に追加します。最後に、このグループが閉じられるので、c の最初のアイテムは取り外されます（114行目）。
もしパターンの終わりに達したならば、マッチは成功です。この場合、我々は dna（117行目）から現在の位置 i まですべてを取り除き、replace 関数を用いて、テンプレート t から生成された DNA 文字列とこれまでに集められた環境 e で置換します。
3.5 置換
それでは、図13を見ながら置換の操作について考えましょう。この操作は引数として、テンプレート tpl （以前 DNA 文字列からデコードしたもの）と環境 e （マッチング処理が成功した結果）の2つを受け取ります。この操作の間、我々はアイテムごとにテンプレートを読み込み（122行目）、少しずつ DNA の置換部分 r を作ります。そして、それは結局グローバルな DNA 文字列 dna の先頭に付加されます。
アイテム b のため、我々は適用な塩基 b を置換文字列に追加します。また、「参照」アイテム nl のために、我々は環境の n 番目の要素を調べます。もし n が e の長さよりも大きいのならば、この検索が ε で終わることに注意しましょう。我々は protect 関数を使うため、それが r に追加される前に、結果として生じる文字列を l 回引用します。
「長さ」アイテム |n| のために、我々もまた環境のn番目の要素を調べて、その長さを算出します。n が範囲外の場合は長さを算出するとεが返されるので、そのような n の値が与えられた場合は長さは 0 となるでしょう。そして、我々はその長さを表す自然数を asnat 関数を用いてエンコードし、置換文字列に追加します。
3.6 保護
関数 protect は、引数として レベル l と部分DNA文字列 d の2つを受け取ります。この関数は d を l 回 quote し、その結果として生じる文字列を返します。ここで、quote は、I を C で、C を F で、F を P で、そして P を 'IC' で置換する関数を表します。
（図14: 保護）
（図15: 自然数のエンコーディング）
（図16: 完全な繰り返しの例）
3.7 自然数のエンコーディング
asnat 関数は、ほとんど nat 関数の逆の動作をします。この関数は引数として数値 n を受け取り、数値をエンコードした結果として DNA 文字列を生成します。数値は最上位ビットを最後に置いたバイナリ表現でエンコードされ、0 は I、1 は C で置換されます。さらに、エンコードされた文字列は P で終端されます。
3.8 サンプル
実行に関する説明のまとめとして、図16にいくつかのサンプルを示します。これは、パターンのデコードやテンプレートのデコード、そして matchreplace 以降の処理の間に、dna 変数がどのように変わっていくかを表すものです。
最終更新：2008年05月17日 02:25
