kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

Higher Order PEG(HOPEG) がHiger Orderになりました

去年のエントリ

kmizu.hatenablog.com

でHigher Order PEG(HOPEG)の評価器を公開したと書いたのですが、その時点でのHOPEGは、まだ First Orderで、パラメタ付き規則自体は扱えても、規則そのものを引数として渡すことはできませんでした。で、最近、再びHOPEGについて考えていて、とりあえずHigher Orderにしてみようと一晩頑張ったらHigher Orderになりました。これによって、従来はできなかった

S = APPLY2(ALTER, "a", "b") !. ;
ALTER(x, y) = x / y ; 
APPLY2(F, x, y) = F(x, y) ; // aかbのどちらかにマッチする

みたいなのが書けるようになりました。ここでは、パラメタ付き規則APPLY2の第一引数自体がパラメタを取るようになっています。これによって当然表現能力は上がると思われるわけですが、どの程度のことが表現できるようになったかはよく考えていないので、いい例があれば教えてください…。

ところで、形式言語を作る(拡張)するというのは楽しいものですね。プログラミング言語の設計とはまた違った楽しさがあります。プログラミング言語の場合、本質的な表現能力は等価(チューリング完全)な上で、いかにして生産性を高くするかとか、安全性を高めるかとかいう目標を考えて設計するわけですが、形式言語を拡張したりする場合、そもそもその表現能力自体が変化するので、「どのように」表現能力が変化するのかに思いを巡らせるのが楽しいです。

とはいえ、自分もあくまでPEGという既存の形式言語を拡張しただけなので、そのうち、自分で一から形式言語(文法)を設計してみたいですね(?)

なお、ソースコード

github.com

にて公開中ですので、興味を持った型はスターを付けるなり、issueにドキュメント要望など書いてくださるとモチベーションが上がります。