kmizuの日記

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

Macro PEG with 後方参照で、「変数宣言がない場合エラー」を構文解析時にチェックする

ほぼタイトルの通りです。先日導入した、Macro PEG + 後方参照の拡張を利用することで、変数宣言のテーブルのようなものを構文解析時に作り出すことができるようになったので、それを利用することで、変数宣言をみるたびごとに、table | varibleのようにして、ORで定義した変数名を追加していきます。

gist.github.com

規則Statementsの定義がポイントです。

def Statements(table: P[Any]): P[Any] = VAL ~ Identifier.evalCC{i => EQ ~ Expression(table) ~ SEMI_COLON ~ refer(Statements(table | i)).? } / Expression(table) ~ SEMI_COLON ~ refer(Statements(table)).?
val s = 1;

のような変数宣言を見つけたら、sリテラルとしてテーブルに追加して続きを読むという作業を行っています。そして、式の中で、tableにある変数が出現した場合のみ、識別子として許可するということを、and-predicateを用いて行います:

def Primary(table: P[Any]): P[Any] =  table.and ~ Identifier | IntegerLiteral | (OPEN ~ refer(Expression(table)) ~ CLOSE)

ここではあえてしていませんが、変数のundefといった文があった場合も、not-predicateを用いて同様に記述することができます。

Macro PEGに後方参照を追加すると、扱える文法の範囲がかなり拡大します。

Scalaのメソッドや関数に関するQ&A

Scala勉強会第170回 in 本郷

rpscala.doorkeeper.jp

は、サブテーマ「Scalaの言語仕様」であったため、久々に熱弁をふるったところ、特に、メソッドや関数の仕様や区別に関して疑問に思った方が多かったらしく、質問も多かったので、Q&A形式でまとめておきます。

Q: (x1, xN) => body 形式と、{ case pat1 => body1; ... case patN => bodyN }形式の違いは何でしょうか?

A: 前者は必ずFunctionN[S1,...,SN,R]型を持つのに対して、後者は期待型(expected type)によって型が異なります:

1: FunctionN[S1,...,SN,R]: この場合、

(x1:S1,...,xN:SN) => (x1,...,xN) match {
  case pat1 => body1
  case ...
  case patN => bodyN
}

と同じ意味になります。通常の無名関数構文+本体で直後にパターンマッチングを行うわけです。

2: PartialFunction[S, R]: この場合、

new scala.PartialFunction[S, R] {
  def apply(x: S): TT = x match {
    case pat1 => body1; ... case patN => bodyN
  }
  def isDefinedAt(x: S): Boolean = {
    case pat1 => true  .. case patN => true
    case _ => false
  }
}

と同じ意味になります。期待型がPartialFucntion[S, R]の場合、パターンにマッチするかだけをチェックすることができる、isDefinedAt()メソッドが自動的に定義されるのがポイントです。Scalaのコレクションクラスのメソッドcollectはこれを利用して実装されています。

scala> List(1, 2, 3, 4).collect{ case x if x > 2 => x * 2}
res0: List[Int] = List(6, 8)

collectcaseにマッチする要素だけを取り出して、かつ、関数本体を適用した要素からなる値を返します。いわば、filter + mapのような動作を行うわけですが、caseにマッチするかだけをチェックできるため、このような挙動が可能になるのです。

3: FunctionN[S1,...,SN,R]に対してSAM-convertibleである:この場合、

(x1:S1,...,xN:SN) => (x1,...,xN) match {
  case pat1 => body1
  case ...
  case patN => bodyN
}

と同じ意味になります。これは、Scala 2.12で正式に導入される(Scala 2.11でも実験的なオプションを使えば利用可能な)Single Abstract Methodだけを持つインタフェースへの変換を念頭に置いたものだと思われます(これは、昨日説明していて言語仕様を参照するなかで初めて気が付きました。先行して、仕様を記述しておいたのでしょうか?)。

Q: タプルを引数にとる関数と複数の引数をとる関数の違いは何でしょうか?

A: 前者はFunction1[(S1,...,SN),R]型を持つのに対して、後者はFunctionN[S1,...,SN,R]型を持ちます。特に、JVMレベルでは、前者は型消去の後は全て同一の型になるのに対して、後者は引数の数に応じて異なる型を持ちます。

この区別は、JVM上では、複数の引数を取る関数を別に扱った方が効率的な実現が可能になるからです。効率を無視すれば、全てFunction1型で表現するような実装も可能だったと思われます。ただし、その場合、2引数以上の全てのメソッド呼び出しのたびに、タプルの生成、タプルからの値を取り出す余分なコードの実行が必要になります。この辺は、JVM上で実現する上での妥協の産物といえます。

なお、MLやOCamlなどの言語では、この区別が存在せず、タプルを引数に取る関数しか存在しませんが、だいたいの処理系では、タプル引数の関数を効率的に実行できるようになっているはずです。

Q: _の使い方がよくわからないので、教えてください。

A: パターンマッチのパターンを除けば、式中のおおざっぱに言って、次の二通りにわかれます。

1:

val abs = Math.abs _

のように、メソッド に対して、空白を一つ以上あけて_を付けるケース。この場合、メソッド型(ユーザが書き下すことができない)から関数型への変換を指示する構文になります。たとえば、Math.absメソッド型は

(Int)Int

というものになりますが、これはファーストクラスの型ではなく、そのままでは値を引数として渡したり、変数がそれに束縛されたり、返り値として返したりすることができません。Math.abs _とすると、

(Int) => Int

型になります。この型はファーストクラスの型であり、その値を引数として渡したり、変数がそれに束縛されたり、返り値として返したりすることが自由にできます。

2:

List.map(_ + 1)

のように、突然_が出現する場合。これは、プレースホルダ構文と呼ばれ、構文解析時に特別な処理が行われます。詳しくは、私の過去のブログエントリ

kmizu.hatenablog.com

をご覧ください。この構文のめんどくささがよくわかります。

Q: メソッドと関数の違いがよくわかりません。

A: メソッドはファーストクラスの値ではありませんが、関数はファーストクラスの値です。

この呼び方は、厳密に言うとScala Language Specificationの呼び方と異なるのですが、こう考えた方がわかりやすいです。より厳密にいえば、メソッドメソッド型(ファーストクラスの型ではない)を持ち、関数は関数型(ファーストクラスの型)を持ちます。メソッド型は_構文で、対応する関数型に変換することができます(eta-expansion)。

構文的な区別としては、defで定義されたものは全てメソッドであり、それ以外が関数であると考えて間違いありません。

また、メソッドジェネリック(多相的)になれますが、関数は多相的になることができません。

trait PolymorphicFunction {
  def apply[T, U](arg: T): U
}

このPolymorphicFunctionapplyジェネリックメソッドですが、関数の型で同じことを表現することはできません(関数型の実際の表現はFunctionN[N1,...,NN,R]であり、関数の型が決まると型引数が全て決まってしまうため)。

なお、

List(1, 2, 3).foreach(println)

のように、一見「メソッドを値として渡している」ように見える箇所がありますが、これは、実際には

List(1, 2, 3).foreach(println _)

とほぼ同じで、メソッドの型を関数の型に変換せよと指示しているのであり、メソッドをそのまま渡しているのとは異なります。

とりあえず、こんな感じです。だだっと書いたので、何か見落としなどあるかもしれません。その際はご指摘よろしくお願いします。

新しい言語を覚えるために私がした事(Kotlinの場合)

先日の、Scala勉強会第170回 in 本郷 : サブテーマ「Scalaの言語仕様」

rpscala.doorkeeper.jp

Scalaの言語仕様について解説していたときの反応をみて、どうも、自分のプログラミング言語の把握の仕方はあまり一般的ではないのではということを考えました。どう違うかというと一言では説明できないのですが、世間的には、プログラミング言語については、よりフィーリング的になんとなく理解している部分理解していない部分がぼやーっとしているのに対して、自分の場合、理解している部分とそうでない部分の境界がくっきりしているような感じです。

それはともかくとして、このエントリでは、自分が最近新しく触った言語であるKotlinについて、どのようにして理解を進めたかを書いてみたいと思います。

公式ドキュメントを読む

定番といえば定番ですが、公式ドキュメントが一番正確に言語について書いてあるものです。Kotlinの公式リファレンスは以下から見ることができます。

kotlinlang.org

今まで色々な言語を触ってきましたが、その中でもKotlinのリファレンスはよく書かれている方だと思います。ですが、ここではそういうことは割とどうでもよくて、とにかくサンプルコードをざっと眺めて、自分の脳内におおざっぱに文法定義のようなものを構築します。この時点ではBNFほどくっきりとした形ではないですが、

  • (クラス|オブジェクト)は任意個のメンバー定義からなっている
  • メンバーの型名は省略可能
  • メソッドが単一式からなる場合、`='に続けて本体を記述する(注:便宜上メソッドと呼んでいます)
  • メソッド複数の式を含むブロックからなる場合、'='ではなく、直後に{ ... }を続ける

といった事実を積み上げて、全体としてどのような文法になっているかを推測していきます。文法について疑問が湧いたときは、「こうだろう」というおおまかな仮説を立てて、それが正しいかを検証します。言語のリファレンスは文法について網羅的に解説していませんから、コンパイラに聞くのが手っ取り早いです。そこで、コーナーケースを含む入力をコンパイラに食わせてパーズエラーになるかどうか等を調べます。

パーザコンビネータライブラリを作成

一見ネタっぽいですが、これは結構馬鹿にできない効果があると思います。Hello, World!から学べることは極めて限られていますが、パーザコンビネータライブラリを作ると

  • ジェネリックスを含む型システム
  • 文字列の基本操作
  • 関数の取り扱い(関数を第一級オブジェクトとして扱う場合も含む)
  • クラスやオブジェクトの取り扱い
  • etc

など様々なことを一度に学べます。

公式ドキュメントの疑問点を突き詰める

これは、公式ドキュメントの説明が不足していると感じた場合によく行う方法です。たとえば、Kotlinでは、smart castがあるよというのを謳い文句にしてますが、どのくらいsmartなのかについて説明がありません。

val s: String? = ...
if(s != null) {
    println(s.length)
}

といったサンプルを見せられても、じゃあ、たとえば

if(false || s != null) {
    println(s.length)
}

はOKなのかとか、

if(!!!!!!(s != null)) {
    println(s.length)
}

はOKなのかとか、色々疑問が湧いてきます。ここで重要なのは、完璧なスマートキャストといったものは基本的に不可能なので、型システムにおいて一般的な、「安全側に倒す」(=not-nullableと判定された場合は必ずnot-nullableだが、全てのnot-nullableを検知できるわけではない)手法を取っているに違いないという推測を働かせることです。そして、「どの程度の近似精度なのか」を確かめるために、色々なプログラムを食わせてみます。

kmizu.hatenablog.com

はそういった事を調べる過程でわかったことを書き留めたものです。

また、Kotlinの公式ドキュメントによれば、ブロックからなる関数定義は、必ずreturnを書かなければいけなくて、その根拠として

Kotlin does not infer return types for functions with block bodies because such functions may have complex control flow in the body, and the return type will be non-obvious to the reader (and sometimes even for the compiler).

というのが書かれていますが、ラムダ式複数の式を持てるのにreturnを書かなくて良いことを考えると、このドキュメントの記述はおかしいです。これを立証するために、次のようなblock関数を定義し、実際に、複数の式からなる関数定義においてreturnを不要にできることを確認しました。

inline fun <T> block(body: () -> T): T {
    return body()
}

この辺で意識していたのは、公式ドキュメントのサンプルコードは信用するが、説明については話半分くらいに思っておくという態度です。言語仕様書であれば正確を期していることが期待できますが、言語の公式ドキュメントは、魅力的な機能を新規ユーザに対してアピールする場でもあり、しばしば正確さは犠牲になります。

さらにサンプルプログラムを書く

この時点で、言語の構文や型システムについてある程度把握できていましたが、より深く理解したいので、さらにいくつかのサンプルコードを書いて実験してみました。できるだけ、言語のシステムのコーナーケースを付くようないやらしいサンプルコードを考え、それを通してさらに理解を深めます。

ソースを読む

だいたいの言語処理系のソースにはBNFによる文法定義がついてくるので、なんだかよくわからない構文が登場したときはそれを読めばだいたい解決できます。それでもわからない場合、実際に字句解析器や構文解析器のソースまで読みます。今回の場合、字句解析器のソースは読んだものの、構文解析器は面倒そうだったのであえて読みませんでしたが、その気になれば読めると思います。

型チェッカはフロー解析を行う都合上、通常の静的型付き言語よりややこしそうだなと思ったので、今のところソースは読んでいません。正直、Kotlinのフロー非依存の部分の型システムは大体わかったと思うのですが、フロー依存の部分についてはちゃんと理解していません。ですが、「フロー非依存の部分については理解できた」「フロー依存の部分については未理解の部分が多い」といった形で、理解していることとそうでないことの間に境界線を引いておきさえすれば良い話です。

まとめ

だらだらと書いてきましたが、

  • コンパイラ作者の気持ちになって言語仕様を推測する
  • 文法の全体像を思い描きながら、随時修正する
  • 理解していることと理解していないことの間に適切な境界線を引く

辺りが自分にとっての重要なポイントなのではないかと思いました。特に、最後の点は個人的に一番重要な点です。理解していないことの範囲が適切にわかっていれば(あるいは理解していない範囲をくくり出せれば)、プログラミング言語の全体像についてわかっていないことを恐れる必要はないためです。

なお、当たり前ですが、Kotlinについてよく理解したからといって、それでKotlinで実用的なプログラムを書けるようになるわけではありません。

Macro PEG 0.0.9 リリース

今回のおもな変更点は、

です。一点目は、まだそんなバグが残ってたのか…と自分に呆れるばかりです。二点目は、evalCCの型をより一般的なものに変更したというものです。これは、

での@phenanさんのアドバイスを受けての変更です。そろそろ、Macro PEGも拡張はこれくらいにして、もっとパーザコンビネータとしての実用度を上げていく方向にいこうかなと思っています(Macro PEGインタプリタ自体もパーザコンビネータの拡張に追随させないといかんですが)。