アットウィキロゴ
ranha-icfp @ ウィキ
アットウィキロゴ
ranha-icfp @ ウィキ
ページ一覧

pseudo code解説

ちなみに、このPDFで書かれてる疑似コードはBNF(っぽい)

疑似コード解説

Fig2 DNAデータ型

BASE ::= I | C | F | P
DNA  ::= Base* (Baseの繰り返し)
RNA  ::= DNA*  (DNAの繰り返し、DNAと同じ)


DNA = array<BASE>
RNA = array<DNA>
という事

Fig3 シーケンス型

X* X型の要素から成り立つシーケンス
ε  空っぽのシーケンス
x <| xs 要素x + シーケンスxsで結合する
xs |> x シーケンスxs + 要素xで結合する
xs <> ys シーケンスxs + シーケンスys
xs[m..n] xsの部分シーケンスで index m 〜 index (n-1)
xs[m..] xsの部分シーケンスで　index mから最後まで(index len-1)
xs[n] xsのindex n(xs[n..(n+1)]とも書ける)。不正なindexの場合はε
len xs シーケンスxsの長さ

Fig5 DNAの実行

global dna : DNA <- ε(グローバル変数dnaを空に初期化)
global rna : RNA <- ε(グローバル変数rnaを空に初期化)
proc execute () =
 dna <- read(入力を読み込む　遠藤DNAの事か)
 repeat
   let p <- pattern () (patternを呼び出し返値を得る)
   let t <- template() (templateを呼び出し返値を得る)
   matchreplace(p,t) (2つの返値を引数としてmatchreplaceを呼び出す)
 end repeat



proc finish () =
 write rna (rnaを書き出す)
 exit      ("プログラム"を終了させる)

Fig6 パターン

Pattern ::= PItem* (Pattern is array<PItem>)
PItem   ::= Base (I | C | F | P　一つ)
          | !N   ( skip(N) )
          | ?DNA ( search(DNA) )
          | (    (groupのopen)
          | )    (groupのend)

Fig7 Pattern評価

function pattern () : Pattern =
 let p  : Pattern <- ε;(Pattern型のローカル変数pを空に初期化)
 let lvl: N       <- 0;(現在のグループ数を表す自然数lvlを0で初期化)
 repeat
   case dna starts with
     'C'         => dna <- dna[1 . . ]; p <- p |> I
     'F'         => dna <- dna[1 . . ]; p <- p |> C
     'P'         => dna <- dna[1 . . ]; p <- p |> F
     'IC'        => dna <- dna[2 . . ]; p <- p |> P
     'IP'        => dna <- dna[2 . . ]; let n <- nat (); p <- p |> !n
     'IF'        => dna <- dna[3 . . ]; let s <-consts (); p <- p |> ?s
     'IIP'       => dna <- dna[3 . . ]; lvl <- lvl + 1; p <- p |> (
     'IIC'|'IIF' => dna <- dna[3 . . ]
                    if lvl = 0
                    then return p
                    else lvl <- lvl -1; p <- p |> )
                    end if
     'III'       => rna <- rna |> dna[3..10];dna <- dna[10..]
      anything else => finish ()
   end case
 end repeat

'III'の部分からも分かるが、rnaに対してdnaは要素(operator |> と <|)
なので RNA is array<DNA>

Fig9 DNAデコーディングの為の補助関数

function nat () : N = (返値は自然数)
 case dna starts with
   'P'      => dna <- dna[1..]; return 0
   'I'|'F'  => dna <- dna[1..]; let n <- nat (); return 2*n
   'C'      => dna <- dna[1..]; let n <- nat (); return 2*n + 1
   nothing (i.e., is empty) ) => finish ()
 end case


function consts () : DNA = (返値はDNA)
 case dna starts with
   'C'  => dna <- dna[1..]; let s <- consts (); return I <| s
   'F'  => dna <- dna[1..]; let s <- consts (); return C <| s
   'P'  => dna <- dna[1..]; let s <- consts (); return F <| s
   'IC' => dna <- dna[2..]; let s <- consts (); return P <| s
   anything else => return ε
 end case

Fig10 テンプレート

Template ::= TItem*
Template is array<TItem>


TItem ::= Base(塩基)
        | N^N(保護レベルlのreference numberはn^lと書かれる Nは自然数を表す)
        | |N|(reference nの長さをエンコードする要素で|n|と書かれる)

Fig11　テンプレート評価

function template () : Template = (返値はTemplate)
 let t : Template <- ε;
 repeat
   case dna starts with
     'C'           => dna <- dna[1..]; t <- t |> I
     'F'           => dna <- dna[1..]; t <- t |> C
     'P'           => dna <- dna[1..]; t <- t |> F
     'IC'          => dna <- dna[2..]; t <- t |> P
     'IF'|'IP'     => dna <- dna[2..]; let l <- nat (); let n <- nat (); t <- t |> n^l
     'IIC'|'IIF'   => dna <- dna[3..]; return t
     'IIP'         => dna <- dna[3..]; let n <- nat (); t <- t |> |n| 
     'III'         => rna <- rna |> dna[3..10]; dna <- dna[10..]
     anything else => finish ()
   end case
 end repeat

Fig12　パターンマッチング

Environment ::= DNA* (Environment is array<DNA>)


proc matchreplace (pat : Pattern, t : Template) = (引数はPattern型とTemplate型)
 let i : N  <- 0
 let e : Environment <- ε
 let c : N* <- ε (c is array<N>)
 foreach p in pat(foreach文は分かる?　分からなかったらRuby,Python,C#あたりとセットでググる)
   case p is of the form
     b => if dna[i] = b
          then i <- i + 1
          else return
          end if
    !n => i <- i + n
          if i > len(dna) then return end if
    ?s => if there is a smallest (n : N) such that n >= i and s is a postfix of dna[i..n]
          (index i以降で最初に文字列sが出てくる場所を探し、文字列sの最後の文字のindex+1をnとする。失敗する可能性もある)
          then i <- n
          else return
          end if
     ( => c <- i <| c
     ) => e <- e |> dna[c[0]..i]; c<-c[1..]
   end case
 end foreach
 dna <- dna[i..]
 replace(t,e)
 return

Fig13　置換

proc replace (tpl:Template, e:Environment) = (引数の型はTemplate型とEnvironment型)
 let r : DNA <-　ε
 foreach t in tpl
   case t is of the form
     b   => r <- r |> b
     n^l => r <- r <> protect(l,e[n])
     |n| => r <- r <> asnat(len(e[n]))
   end case
 end foreach
 dna <- r <> dna
 return

Fig14 保護

function protect (l : N, d : DNA) : DNA = (引数の型はN,DNA　返値の型はDNA)
 if l = 0
 then return d
 else return protect(l−1,quote(d))
 end if


function quote (d : DNA) : DNA = (引数の型はDNA,返値の型はDNA)
 case d starts with
   I => return C <| quote(d[1..])
   C => return F <| quote(d[1..])
   F => return P <| quote(d[1..])
   P => return 'IC' <> quote(d[1..])
   anything else => return ε
 end case

Fig15　自然数エンコード

function asnat (n : N) : DNA =
 case n is
   0 => return 'P'
   positive even => return I <| asnat(floor(n/2))
   positive odd  => return C <| asnat(fllor(n/2))
 end case

floor関数は、与えられた数を超えない最大の整数の事。
普通のプログラミング言語では 整数/整数 の演算は切り捨てられるので
単に割れば良いだけかもしれない。

ただ、 n>>1　にはするべき。
「pseudo code解説」をウィキ内検索
最終更新：2008年05月16日 12:11