kmizuの日記

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

Macro PEGとParser Combinatorの関係に関するメモ

特に他の人が読むことを想定して書いていないので、あしからず。Parser Combinatorに関しては、Scala風味の記述で。

  • 0階PEGは、相互再帰的なlazyな値(=> Parser[T])の集まり(式はPrimitiveと基本的なCombinatorで構成される)
    • Primitive
      • 文字列リテラル: "str": Parser[String]
      • 空文字列: "": Parser[String]
      • 非終端記号の参照
    • 基本的なCombinator
      • 順序付き選択(e1 / e2):(Parser[T], Parser[T]) => Parser[T]
      • 繰り返し: e * or e+: Parser[T] => Parser[List[T]]
      • And述語: & e: Parser[T] => Parser[Unit]
      • Not述語: ! e: Parser[T] => Parser[Unit]
      • 0回または1回の繰り返し:e ?: Parser[T] => Parser[Option[T]]
  • Macro PEGは、0階PEGに対応するParser Combinatorに加え、Parser[T] => Parser[U]型の関数の定義を許したもの
    • たぶん、真に文脈自由言語を含む(そして、文脈依存言語のそこそこの部分がカバー可能?)
      • 自然数の加減乗除、累乗等が計算可能
    • 順列言語みたいなのが非常に簡単に書ける
  • 後方参照(str:e1 e2)の拡張は、Parser Combinatorでは、evalWithContinuation: (Parser[String] => (Parser[String] => Parser[T])) のような関数として考えることができる
    • e1を評価した結果、「消費された」文字列にマッチするようなParser[String]を引数にとり別のParser[T]を返す
  • Higer Order Macro PEGは、
    • Parser[A1] => Parser[A2] => ... Parser[An] のような型の関数を許す
      • 無名関数も書けるように(ただし、現状のMacro PEGでは、無名関数を置ける場所に制限あり)
  • 動的スコープVS.静的スコープ
    • 動的スコープ
      • 文脈を持ちまわる手間がはぶける
      • Parser Combinatorに素直に対応が付かない
    • 静的スコープ
      • Parser Combinatorに素直に対応が付く
      • レキシカルクロージャが定義できるが…
  • 値呼び出しと名前呼び出し
    • 何も考えずに定義すれば、名前呼び出しになる
    • Macro PEGにおける値呼び出しってなんだ?
  • to be continued ...

あなたの知らないKotlinのsmart cast(known as Flow-Sensitive Type)

皆さん、Kotlin触っていますか?Kotlinかわいいですよね、Kotlin(どの口がそんなことを言うかって感じですが)。Kotlinにはsmart castという機能があり、安全なキャストができます、というのは不正確で、KotlinはFlow-Sensitive Typeと呼ばれる型システムを持っています。おおざっぱに言えば、制御フローによってある変数や式の型が変わる型システムの総称(だと思います。間違ってたらご指摘願います)Kotlinではそれをsmart cast(と公式ドキュメントには書いてある)と呼んでいるという話のようです。

公式ドキュメントにある例からいくつか引用します:

fun demo(x: Any) {
  if (x is String) {
    print(x.length) // x is automatically cast to String
  }
}
  if (x !is String) return
  print(x.length) // x is automatically cast to String
when (x) {
  is Int -> print(x + 1)
  is String -> print(x.length + 1)
  is IntArray -> print(x.sum())
}
  // x is automatically cast to string on the right-hand side of `||`
  if (x !is String || x.length == 0) return

  // x is automatically cast to string on the right-hand side of `&&`
  if (x is String && x.length > 0)
      print(x.length) // x is automatically cast to String

説明もなんからさらっとして、わかったような、わからないような…と思うかどうかは人それぞれだと思いますが、自分は少なくとも不思議に思いました。そこで、処理系のソースを読まずにいくつかのコードを書いて実験してみました。

まずは準備から。

interface D {
    fun d(): Unit
}

interface A : D{
    fun a(): Unit
}

interface B : D{
    fun b(): Unit
}

class C : A, B {
    override fun a() {
        println("A")
    }
    override fun b() {
        println("B")
    }
    override fun d() {
        println("C")
    }
}

inline fun random(): Boolean = (Math.random() * 2).toInt() == 1

例1:

fun demo1() {
    val x: Any = "FOO"
    if(random() && x is A) {
        x.a() //OK
    }
}

順当な結果ですね。random()trueを返そうが返すまいが、ifの本体が評価されるときには、必ずx is Atrueになるわけですから。まあ、実際のところ、random()は読む人を撹乱するためだけに使っています。

例2:

fun demo2() {
    val x: Any = "FOO"
    if(!(random() || !(x is A))) {
        x.a() //OK
    }
}

より式を複雑にしてみましたが、これもOKです。これは、いうなれば、

if(!random() && !!(x is A)) {
  x.a()
}

としているのと同じわけですが、!!(x is A) = x is Aなので、やっぱりifの本体が評価されるときには、x is Aが成り立っているわけです。ちゃんと論理式を計算しているところがミソです。

例3

fun demo3() {
    val x: Any = "FOO"
    if(false || x is A) {
        x.a() //NG
    }
}

これは意味的にはx is Aと同じになりますが、truefalseといったリテラルは特別扱いの対象ではないようです。

例4

fun demo4() {
    val x: Any = "FOO"
    if(x is A && !(x is A)) {
        x.a() //OK
    }
}

x is A && !(x is A) というのは決してtrueに評価されませんが、もし仮に全体がtrueに評価されるならば、そのときは必ずx is Aが成り立つのでOKということでしょう。ちなみに、順番をひっくり返した次の式でもOKです

例5

fun demo5() {
    val x: Any = "FOO"
    if(!(x is A) && x is A) {
        x.a()
    }
}

これは妥当ですね。次行ってみましょう。

例6

fun demo6() {
    val x: Any = "FOO"
    if(x is A && x is B) {
        x.a() //OK
        x.b() //OK
        x.d() //OK
    }
}

型Aかつ型Bという条件が成り立ったときにどうなるかということですが、両方のメソッドを呼び出すことができています。内部的にはintersection typeのようなものを持っているのではないかと推測されます。

例7

fun demo7() {
    val x: Any = "FOO"
    if(x is A || x is B) {
        x.d() //NG
    }
}

残念ながらこれはNGでした。least upper boundのようなものが計算されることを意図したのですが、union typeとして表現されているのでしょうか。

さて、demo6と同じ意味になる次の式はどうでしょうか。

例8

fun demo8() {
    val x: Any = "FOO"
    if(!(!(x is A) || !(x is B))) {
        x.a() //OK
        x.b() //OK
        x.d() //OK
    }
}

ちゃんとOKになります。賢いですね。次はnullable typeを混ぜてみます。

例9

fun demo9() {
    val x: Any? = null
    if(x is A? && x is B) {
        x.a() //OK
        x.b() //OK
        x.d() //OK
    }
}

次はどうなるでしょう。

例10

fun demo10() {
    val x: Any? = null
    if(x is A? && x is B?) {
        x.a() //NG
        x?.a() //OK
        x?.b() //OK
        x?.d() //OK
    }
}

?.でnullをはずしてやればOKです。内部的には、 (A & B)?という扱いになっているのでしょうか。ややこしいですね。

まとめ

  • KotlinはFlow-Sensitive Typeと一般的(?)に呼ばれる型システムを持っている。
  • 型推論をする上で、is&&||! が特別扱いされている
  • (推測)型のintersectionやunionを内部的に持っている
  • どうやら、nullableとnon-nullableのintersectionも扱える模様
  • シンプルなケース以外でKotlinの型推論の結果を推測するのは自明ではない。というか複雑。
  • 基本的にこの辺の挙動はundocumented(ある程度推測は可能だが)

Macro PEG 0.0.6 リリース

もはやDaily Releaseになってきたので、Daily Buildをスナップショットで提供だけでいいんじゃないかとかそういう気がしてきましたが、まあ練習と思ってしばらく継続していく予定です。

しかし、そろそろsbt-release使ってリリース自動化すべきときですね。

今回のリリースの変更点はだいたいこの辺↓:

Macro PEGのパーザはscala-parser-combinators使って作成しているのですが、構文解析エラーに関してはあまり賢くないので、文法作成者がある程度手動で、「ここはバックトラックしないで一気にエラーにしてね」と手動で教えてあげる必要があります。その辺やるのが commitメソッドだったり、!~演算子だったりします。この辺使い込んでる人あまり居ないんじゃないかという気がします。fastparseもCut演算子もってて、この辺はPEGベースのパーザ(コンビネータ)は持っておくべき機構なのかもしれないですね。なお、自分が提案したCut in PEGは、Lexical Cut とでも呼ぶべきもので、commitやfastparseのCutと違って、大域的脱出ではなく、ローカルな脱出のみを提供します(でないと、PEGの意味論にうまくマッチしない)。Li HaoyiさんはfastparseへのCut導入にあたってCut in PEG参照してくださったようですが、この辺は大域脱出的カットの方が実用的だと判断されたのか、意味論が誤解されたのかどっちだろう。

今までスルーしてました。サンプルコードいじってて、スルーされると困るのでチェックを追加しました。とにかく自分でMacro PEGをいじって不具合洗い出したりしていこう。

あと、トップページ@cocoa_ruto君からもらった興味深いMacro PEGの例を追加しておきました。自然数の引き算や累乗をMacro PEGでできるという話です。

Macro PEG 0.0.5リリースしました。

HOPEGからMacro PEGに改名しても、バージョン番号はそのまま上がっていますが、タグがぶつかるのが嫌だったので…。

Release releases/0.0.5 · kmizu/macro_peg · GitHub

主な変更は

S = [a-zA-Z_][a-zA-Z0-9_]*;

こういう、識別子を表す規則みたいなのが簡単に書けるようになりました。文字クラスは結局、/で文字をつなげれば等価な表現ができるので本質的ではないのですが、利便性のために追加することにしました。

辺りです。サンプルの文法を作っていくと、追加していきたい機能や不備がどんどん出てくるので、凄いハイペースでのリリースになっています。その代わり、当分は0.0.Xのままにしていこうかと思います。

Macro PEGで「一度現れたら再出現しない修飾子」+「相互排他的な修飾子」を表現してみる

gist.github.com

とりあえずMacro PEGのコード。

「排他的な修飾子」とは何のことかというと、たとえば、public, private, protectedのように、「一度どれかが出現したら他のものは出現しない修飾子」のことです。最近のプログラミング言語の文法では、このような排他的な修飾子はよく見るパターンだと思いますが、これもMacro PEGでサクっと書くことができます。

話は簡単で、前回の記事のMacro PEGに

kmizu.hatenablog.com

引数Scopeを追加して、「排他的な修飾子」の前に、(&Scope)でassertionを書くだけというもの。この例のように、引数として渡された式にand-predicateやnot-predicateを追加することで様々なものを表現することができます。

Higer Order PEG(HOPEG)をMacro PEGに改名しました

タイトルの通りです。githubのプロジェクト名称、パッケージ名なども既に変更済みです。

github.com

元々、Higer Order PEGおよびFirst Order PEGは、Macro Grammarと呼ばれる、文脈自由文法を拡張して、非終端記号が引数を取れるようにしたものにインスパイアされたものなのでした。そういうこともあって、ネーミングに関しては悩んでいたのですが、やはりインスパイア元に敬意を表して、Macro PEGとすることにしました。ちゃんちゃん。

というわけで、以後は、Macro PEGでよろしくお願いします(略称MPEG)。

Higer Order PEGで「一度現れたら再出現しない修飾子」を表現してみる

gist.github.com

とりあえずHOPEGのコードを貼り付けます。表題のような言語をHOPEGで表現する方法ですが、「一度見た修飾子の集合」をどこかに取っておく必要があります。それがModifersの引数AlreadyLookedです。一度どれかの修飾子を読むたびに、AlreadyLooked | "public"のようにして、一度「読んだ」修飾子を/で渡すわけです。

さて、「一度現れたら再出現しない修飾子」は0階のPEGで表現できないのでしょうか。と言われれば、「文法の規模を考慮しなければ」出来る、という回答になります。おおざっぱに言えば、

S = "public" "static" "final"
  / "public" "final" "static"
  / "static" "final" "public"
  / "static" "public" "final"
  / "final" "public" "static"
  / "final" "static" "public"
  / "public" "static"
  / "public" "final"
  / "static" "public"
  / "static" "final"
  / "final" "public"
  / "final" "static"
  / "public"
  / "static"
  / "final"

これで、同じ言語が表現できます。と、ここまで書いて気づいたのですが、

は厳密には間違いで、修飾子の数nに対して、通常のPEGでは、

nPn * nP(n-1)... * nP1

に比例する規模の文法になる、が正しいですね。

ともあれ、First Order PEGになることによって、表現力が向上することも、同じ言語をより簡潔に表現できることも自明ですが、同じ言語を表現するときの、簡潔さ、に関してこのようなオーダーレベルでの違いが出てくるのは面白いですね。