kmizuの日記

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

Kotlinのsmart castの限界

Kotlinには所謂smart castと呼ばれる(公式ドキュメントがそう称している)機能があります。

たとえば以下のように、ifの条件式でnullチェックをすることにより、その中ではnot-nullableな型として扱うことができます。

gist.github.com

ただし、一般的に、あるnullableな型がある地点において、「not-nullableである」かどうかを完全かつ健全に判定する方法はおそらく決定不能(コンピュータのプログラムで判定できない問題)です。そのため、Kotlinは実際にはもっと保守的な方法、つまり、完全かつ健全な判定はできないが、not-nullableと判定できた場合にはかならずnot-nullableになっている、ようなアルゴリズムを採用しています。

このため、smart castは自明にある程度の制限があります。たとえば、あるString?な型について、not nullかつnot emptyであることを判定するメソッドnotNullAndNotEmptyがあったとします。このメソッドを使った次のコード

gist.github.com

は意図通りにはたらいてくれません。これは、Kotlinが呼び出し先のメソッドの制御フローまで追跡できないための制限です。現実的に、呼び出し先のメソッドの制御フローまで追跡していたらコンパイル時間が膨大になってしまいますし、この制限自体は妥当だと思います。ただ、smart castといっても、このような制限が存在するといったことは(Kotlinにおける良いメソッドの設計のためにも)理解しておいた方が良いと思います。

Macro PEG 0.0.8 リリース

github.com

今回のリリースでは、いわゆる後方参照と呼ばれる拡張をパーザコンビネータに導入してみました。

Introduce backreference as `evalCC` method. · kmizu/macro_peg@91154c8 · GitHub

このコミットです。

使い方は

gist.github.com

こんな感じです。サンプルは、XMLのような開きタグと閉じタグ名が一致しているような言語です。後方参照の典型的な使用例ですね。

evalCCメソッドStringを引数にとる関数オブジェクトを渡す形になります。evalCCのレシーバが成功すれば、関数オブジェクトが、マッチした文字列を引数として呼び出され、そうでない場合失敗します。

さて、後方参照ことevalCCメソッドを思いつきで導入してみましたが、これは実際のところ結構「危うい」拡張だと思います。Macro PEGだけで既に結構強力になっているのにこれ以上能力を強化するとうっかりするとチューリング完全…はすぐにはいかないと思いますが、あまり無節操な拡張をしているとそのうちそうなる可能性も捨て切れず…。

なんでチューリング完全になってはいけないのかというと、Macro PEGを解析する問題が、結局、一般のプログラミング言語によるプログラムを解析するのと似たような問題になってしまうためです。よりパワフルな形式言語は取り扱いにくく、よりパワフルでない形式言語は取り扱いやすい的な。

Kotlinによるパーザコンビネータライブラリ kotbinator 0.1 公開しました

実はリリースしてから、Kotlinのパーザコンビネータライブラリがあることに気づいたのですが、まあ、どうせexperimentalだし、自分ならではの独自路線歩みたいし、気にしないでいくことにしました。

最低限の使い方は、

github.com

に書いておきましたので、気がむいたら使ってみてフィードバックくださると嬉しいです。今のところ、文字列からのパーズにしか対応してないですし、構文解析エラーのメッセージはひどいものですが、ゆくゆくは改善していきたいと思っています。

Kotlinのブロックからなる関数定義でreturnを書かなくて良いようにする

Kotlinでは、一つの式からなる関数は

fun add(x: Int, y: Int): Int = x + y

のように明示的なreturnを必要としません。次のように複数の式からなる関数定義ではreturnが必須となります。

fun printAndAdd(x: Int, y: Int): Int {
  val k = x + y
  println(k)
  return k //必須
}

この制限の理由について、Kotlinのリファレンスでは

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).

と書いているのですが(強調は筆者による)、変な話です。何故かというと、ラムダ式複数の式を持てるのに、ちゃんと型を推論できているからです。

一方、Kotlinにはinlineという修飾子を関数につけることができて、これは、inline指定された関数を呼び出すときに、インライン展開させるように指示するものです。たとえば、

inline add(x: Int, y: Int): Int = x + y
println(add(1, 2))

とした場合、これは

println(1 + 2)

と同じコードとなることが期待できます。これを利用して、ブロックからなる関数定義でも、明示的にreturnを書かなくてよいようにする小技を思いついたのでご紹介します。方法は簡単で、

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

という関数を定義して、

fun printAndAdd(x: Int, y: Int): Int = block {
  val k = x + y
  println(k)
  k //return不要
}

のように、=に続けて、定義したblock関数を呼び出すだけです。実に簡単です。さて、こうした場合の実行性能ですが、一つ定義するごとに、getstatic命令とその直後にpop命令が余分に追加されていました。両方とも命令の実行コストは非常に軽いことが予測されますし、無意味な命令としてJVMJITコンパイラが除去してくれる可能性もあります。いずれにせよ、通常気にする必要のあるオーバーヘッドは発生しません。

現在、そういう制御フローに関する小物関数を集めたライブラリを作ろうかななどと考えています(考えるだけでやるとは言っていない)。

プロジェクトのバイナリ互換性をうっかり壊してしまわないように、最初に気を付けるべきこと(主にScala)

先日、MiMaの紹介のために、

kmizu.hatenablog.com

を書きましたが、それの続編みたいな何か。基本的なことだと思うのですが、色々なScalaプロジェクトがバイナリ非互換な変更の元になる行為を意図せず行っている気がするので、啓蒙のために書いてみることにしました(意図している場合も多々あると思います)。主にScalaについて書いていますが、他のJVM系言語でも当てはまる場合は結構あると思います。

なお、自分の手元で、どのようにするとバイナリ非互換が起きるかを試すためのリポジトリとして、

GitHub - kmizu/how_to_use_mima: A repository to explain how to use MiMa

を用意してみました。このプロジェクトのmasterブランチをcloneして、用意されているソースコードに何かの変更を加えて

> sbt mimaReportBinaryIssues

をたたくことでバイナリ非互換な変更についてより深く知ることができるようになってるので、興味があれば試してみてください。

公開メンバの型は明記する

返り値の型推論、便利ですよね。使いたくなるのはわかります。しかし、推論される型はメンバ本体の式の型に依存して変わります。つまり、メンバ本体をいじると、意図せず返り値の型が変わってしまう可能性があります。

privateなメソッドは子クラスを含む外部から参照されないので良いのですが、protected以上のアクセス権を持つメンバの型を型推論におまかせにしてしまうのはやめましょう。

how_to_use_mima/ReturnTypeInferenceInPublishedMethod.scala at b85e77a6524780d25fb949887d8f7368a379f10b · kmizu/how_to_use_mima · GitHub

たとえば、上のような変更をすると、MiMaは

[error]  * method makeBuffer()scala.collection.mutable.ArrayBuffer in class com.github.kmizu.how_to_use_mima.ReturnTypeInferenceInPublishedMethod has a different result type in current version, where it is scala.collection.mutable.Buffer rather than scala.collection.mutable.ArrayBuffer
method makeBuffer()scala.collection.mutable.ArrayBuffer

という報告をしてくれます。このように、型推論に頼っていた部分で、より一般的な型を明示するようにしたくなることがありますが、それはバイナリ互換性を壊すことになります。scalacのソースコードでも、しばしばpublicなメソッドの返り値型を型推論にたよっていることがあったりするので、にほんと気を付けましょう。

また、メソッド本体全体が無名クラスのインスタンス生成になっているようなケースも気を付けましょう。無名クラスは、その継承元のクラスとは実際には別の型になっているので、単に

def foo = new Foo {
  ...
}

def foo: Foo = new Foo {
  ...
}

に変えただけでもNGです。なお、このアドバイスは、同様にメンバに対する型推論が効くKotlinのような言語でも当てはまります。

公開される型名/メソッドの名前は事前によく考える

当たり前の話ですが、いったんバイナリを公開した後に、その名前を変えてしまうと、そのバイナリの型名やメソッド名に依存しているライブラリが、依存ライブラリのバージョンを上げたときに壊れます。

といっても、現実的には事前に完璧な名前付けをするのは難しいので、新しい名前のものが古い名前のものを参照するようにして、古い名前のものをdeprecatedにして移行を促してから、あとのバージョンで削除するといった方法をとるべきでしょう。

how_to_use_mima/BadMethod.scala at b85e77a6524780d25fb949887d8f7368a379f10b · kmizu/how_to_use_mima · GitHub

[error]  * method badNamedMethod()scala.runtime.Nothing# in class com.github.kmizu.how_to_use_mima.BadMethod does not have a correspondent in current version

implicitな値やメソッドの名前をうっかり変更しない

これはややScala特有な話になりますが、ソースコードレベルでimplicitなメソッドを直接使わなかったとしても、バイナリレベルではそれらが使われる可能性があります。ソースコードレベルでは見えない隠れた依存性というべきものができるので、気を付けましょう。

how_to_use_mima/RenamingImplicitIsDanger.scala at b85e77a6524780d25fb949887d8f7368a379f10b · kmizu/how_to_use_mima · GitHub

[error]  * method IntToString(Int)java.lang.String in class com.github.kmizu.how_to_use_mima.RenamingImplicitIsDanger does not have a correspondent in current version

implicitとついていても、それらは通常の名前で参照することができるので、名前変更をしたときと同じエラーになります。

non-final(デフォルト)で良いかよく考える

non-finalなメンバはユーザにとって自由に拡張できるので、利点もありますが(Template Methodパターン等)、いったんnon-finalなメンバとして公開してしまうと、あとからfinalにするとバイナリ互換性を壊すことになります。また、ユーザにとっても、あるメソッドがfinalであることは、挙動を推測するヒントになります。

Kotlinはクラスもメソッドもデフォルトでfinalで、オーバーライド可能なものにはopenキーワードを付ける必要がありますが、これは意図しない挙動を防ぐためにも、意図しないバイナリ非互換を導入しないためにも良い言語設計だと思います(openを明示するということは、その危険性についてもわかった上で選択したということになるので)

how_to_use_mima/NonFinal.scala at b85e77a6524780d25fb949887d8f7368a379f10b · kmizu/how_to_use_mima · GitHub

[error]  * method nonFinalMethod()scala.runtime.Nothing# in class com.github.kmizu.how_to_use_mima.NonFinal is declared final in current version

他にもあるのですが、眠くなってきたので、今回はここまで。参考になれば幸いです。

MiMa(Migration Manager)でScalaプロジェクトのバイナリ互換性をチェックする

MiMaは主にScalaライブラリ(Scala本体を含む)のバイナリ非互換な変更をチェックしてくれるライブラリです(おそらくバイトコードレベルの検査なので、Javaプロジェクトでもチェックできると思うのですが試していない)。

元々の経緯としては、Scala 2.9以降、マイナーバージョンアップでのバイナリ下位互換性は保証するよー、という話があり(それ以前は全く保証がなかった)、そのことを保証するために開発されたツールで、それがオープンソース化されたのがMiMaとなります。

詳しい経緯については

を参照してください。

さて、MiMaは単体で動作するコマンドラインツールとしてと、sbtプラグインとしてと両方が提供されています。しかし、Scalaでライブラリ作ってる人はまあ大抵sbt使ってると思いますので、そっちについて軽く説明します。詳しくはMiMaのWikiをどうぞ。

とここまで前置きです。導入は非常に簡単で、project/plugins.sbtに以下の一行の記述を加え(バージョンは適宜その時点での最新のものに置き換えてください。2016/03/16時点では、0.1.9が最新版となっています)

addSbtPlugin("com.typesafe" % "sbt-mima-plugin" % "0.1.9")

互換性を検査する基点となるartifactを以下のようにbuild.sbtに追加するだけです。

mimaPreviousArtifacts := Set("com.github.kmizu" % "macro_peg_2.11" % "0.0.7")

現在、Macro PEGの最新リリース(Maven Centralに同期されているもの)は0.0.7なのでこのようになっていますが、もちろん、スナップショットリリースなどを指定することもできます。

さて、このようにした上で、コマンドラインから

> sbt mimaReportBinaryIssues 

と叩きます。何も問題がなければ、

[info] macro_peg: found 0 potential binary incompatibilities while checking again

のように表示されます。まあ、これで終わっては意味がないので、バイナリ互換性を壊す変更を入れてみましょう。と、その前に、バイナリ互換性についておおざっぱに考えてみます。たとえば、hoge 0.0.1では、class Hogeが次のように定義されていたとします。全く無意味なライブラリですが、例のためです。

class Hoge {
  def hoge(): Unit = {
    println("hoge")
  }
}

hoge 0.0.1のユーザは、class Hogeを継承して、class HogeHoge extends Hogeとしてhogeメソッドをオーバーライドしても良いですし、(new Hoge).hoge()と呼び出してもかまいません。さて、hoge 0.0.2では、メソッドhogehoge(): Unitを追加し、その中ではhoge()を2回呼び出したいとします。hoge()メソッドが一回だけhogeを出力するのを保証したいので、hoge()メソッドfinalにしましょう。

class Hoge {
  final def hoge(): Unit = {
    println("hoge")
  }
  def hogehoge(): Unit = {
    hoge()
    hoge()
  }
}

さて、こうするとhoge 0.0.1でHogeクラスを継承して、hoge()メソッドをオーバーライドしていたユーザがhoge 0.0.2にアップデートするとどうなるでしょうか。答えは、(早ければ)コンパイルエラーか(遅くとも)クラスのリンク時にエラーになる、です(若干正確ではありません)。これは、hoge 0.0.2のバイナリにおいて、Hogeのクラスファイルで、hoge()finalと指定されたことによります。このような変更をバイナリ非互換な変更と呼びましょう。他にも、hoge()メソッドを削除した場合とか、バイナリ非互換になる理由は色々あります。

そして、これは誤解されがちな点ですが、別にScalaがメジャーバージョンアップでバイナリ非互換になるからという理由だけで、Scalaライブラリがバージョンアップによってバイナリ非互換になる、というわけではないということです。

Javaのプロジェクトであっても、既存のメソッドを削除したり、既存のメソッドをfinalにしたりすれば同様の問題は起こります。ただし、ScalaライブラリはScalaのメジャーバージョンに依存しているので、Scalaのメジャーバージョンアップにともなって、Scalaライブラリもバイナリ非互換になるという点はScala特有の事情です(よく使われているScalaライブラリでは、この問題を解決するために、複数Scalaメジャーバージョン向けに同一ソースから複数種類のバイナリをクロスビルドしていることが多いです)。

前置きが長くなりましたが、実際にバイナリ非互換な変更を行って、MiMaにそれを検出させてみましょう。

github.com

意味の無い変更をコミットするのはさすがにむなしいので(別ブランチ作れという話はあるけど)、名前変更を行ってみました。pfunというよくわからない名前より、delayedParserの方が実態をよく表していると思います(ちなみに、classのval/varパラメータはby nameになることができません)。

変更によってmacro_pegコンパイルエラーになったりはしていません。ですが、pfunはcase classのパラメータである以上、この名前で外部にアクセスできるように公開しているということになります。この名前を変更するというのはまさにバイナリ非互換な変更です。そこでMiMaの出番です。上記のコミットに対して、

> sbt mimaReportBinaryIssues 

を走らせます。すると…

[error]  * method pfun()scala.Function0 in class com.github.kmizu.macro_peg.comb
 not have a correspondent in current version
[error]    filter with: ProblemFilters.exclude[DirectMissingMethodProblem]("com.
arsers#ReferenceParser.pfun")

現在のバージョンにはpfunというメソッドがないよーと文句を言ってきました。ここでは既にあったメソッドがなくなったという簡単な例でしたが、他にも、

といったバイナリ非互換の要因になる様々なものに対してチェックをしてくれます。ただ、意図してbreaking changeをしたい場合等、特定のエラーは無視したいというケースはあると思います。そのような場合、

github.com

に書かれているように、部分的にチェックを無効にすることができます。というわけで、MiMaの概要について紹介してみました。それでは快適なScalaライフを!(ひょっとしたらJavaライフも)

Macro PEG 0.0.7 リリース

今回から、sbt-releaseを使ってリリース作業を半自動化してみました。便利ですね、sbt-release。sbt-sonatypeと組み合わせれば、最初にリリース番号と、次のSNAPSHOTバージョン番号答えるだけで後は全自動。

それはともかく、今回のリリースでは、パーザコンビネータを実装してみました。

昨日のエントリでなんかメモ書きしていたのですが

kmizu.hatenablog.com

Macro PEGとParser Combinatorとの関係についてだいぶ理解が進んだので、とりあえず実装してみた感じです。

回文を表すMacro PEG Combinator(MacroPEGParsers)は次のようになります。

object Palindrome {
  lazy val S: MacroParser[Any] = P("") ~ !any
  def P(r: MacroParser[Any]): MacroParser[Any] = "a" ~ refer(P("a" ~ r)) / "b" ~ refer(P("b" ~ r)) / r
}

規則Pに該当するものが引数rを取っているのがポイントです。これはMacro PEGでは、

S = P("") !.; 
P(r) = "a" P("a" r) / "b" P("b" r) / r;

次のようになっています。ほぼ一対一対応しています。

MacroParsersでも評価戦略はcall-by-nameになっていますが(普通に実装するとそうなる)、call-by-value Macro PEGというのを無理くり考えることはできるものの、あまり意味がないのではと考えました。