hopeg_fopeg.md

部分適用の無いHOPEG(高階PEG)の表現力はFOPEG(一階PEG)と同じ?

1. 規則の数は有限である。
2. 規則の各パラメタについて、それが規則を受け取るのかどうかは決定可能。 例: Foo(f, x) = f(x); Bar(g, x) = Foo(g, x)ならfとgはルールでないといけない。
3. よって、全てのルールを展開すればルールを受け取るパラメタを消せる。 例:

     Foo(f, x) = 'd' f(f, x);
     Bar(f, x) = 'c' / 'a' Foo(f, 'a' x) Foo(f, 'b' x);
     ↓
     Foo(f, x) = 'd' f(f, x);
     Bar$Foo(x) = 'c' / Foo(Foo, 'a' x) Foo(Foo, 'b' x);
     Bar$Bar(x) = 'c' / Foo(Bar, 'a' x) Foo(Bar, 'b' x);
     Bar(f, x) = 'c' / Foo(f, 'a' x) Foo(f, 'b' x);
     ↓
     Foo$Foo(x) = 'd' Foo(Foo, x);
     Foo$Bar(x) = 'd' Bar(Bar, x);
     Foo(f, x) = 'd' f(f, x);
     Bar$Foo(x) = 'c' / Foo(Foo, 'a' x) Foo(Foo, 'b' x);
     Bar$Bar(x) = 'c' / Foo(Bar, 'a' x) Foo(Bar, 'b' x);
     Bar(f, x) = 'c' / Foo(f, 'a' x) Foo(f, 'b' x);
     ↓
     Foo$Foo(x) = 'd' Foo$Foo(x);
     Foo$Bar(x) = 'd' Bar$Bar(x);
     Foo(f, x) = 'd' f(f, x);
     Bar$Foo(x) = 'c' / Foo$Foo('a' x) Foo$Foo('b' x);
     Bar$Bar(x) = 'c' / Foo$Bar('a' x) Foo$Bar('b' x);
     Bar(f, x) = 'c' / Foo(f, 'a' x) Foo(f, 'b' x);
     ↓
     Foo$Foo(x) = 'd' Foo$Foo(x);
     Foo$Bar(x) = 'd' Bar$Bar(x);
     Bar$Foo(x) = 'c' / Foo$Foo('a' x) Foo$Foo('b' x);
     Bar$Bar(x) = 'c' / Foo$Bar('a' x) Foo$Bar('b' x);
     
   

消すための手続き:

1. パラメータの型を推論する。型は、「(高階でない)式」「規則[型1, 型2, ... 型n]」のいずれかである。
2. 規則の参照関係をDAGとみなして、強連結成分に分けて、トポロジカルソートして、末端の方から処理する。(このステップ必要ない?)
3. 規則を受け取るパラメータについて、型が適合する規則で特殊化した規則を作る。ただし右辺に現れるのは特殊化する前の規則である。例: 「Foo$Bar(x) = 'd' Bar(Bar, x);」において、右辺のBarは特殊化する前のBarとする。
4. 全ての規則の全てのパラメータを特殊化し終わったら、右辺を特殊化したもので置き換える。例: 「Foo$Bar(x) = 'd' Bar(Bar, x);」を「Foo$Bar(x) = 'd' Bar$Bar(x);」にする。
5. 特殊化する前の規則を削除する。