読者です 読者をやめる 読者になる 読者になる

kmizuの日記

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

Kotlin Internal勉強会を開催しました

connpass.com

数ヶ月前からKotlinをちょくちょく触っていて、「もっと深いところを知りたいな」と思ったので開催することにしたのがこの勉強会です。さすがにInternalとついていたせいか、それほど参加者は多くなかったですが、かえって質問しやすい空気になっていたのではないかと思います。

以下、各発表について。

元々は、KotlinのSmart Castをチェックしているコードを読んで、「これでわかる!」と行きたかったのですが、結構難しかったので断念。代わりに、以前作ったスライドにちょこっと追加したものでお茶をにごしました。第二回があればSmart Castの謎を究明したいところですね。

やんくさんの発表。ディレクトリ別におおまかにどのようなコードが格納されているか、という解説でした。ソースコード探検の際にはとても役に立ちそうでした。

RyotaMurohoshiさんの発表。KotlinからJavaのメソッドを呼び出す時に、!がついた謎の型名があるけど、あれって何なの?というお話。自分も見たことがありつつ、あれって一体どういう意味なのだろうと思っていたので、謎が解決して良かったです。あれってPlatform Typeと呼ぶのが正式名称なのですね…

  • Kotlinのlexerを読む

Kotlinのlexerを以前読んでいて気づきがあったので、その場で雑に読みつつ、解説をするという発表。@omochimetaruさんがその場その場で適切なツッコミを入れてくださったおかげで自分の雑な理解をしていた部分に気がつくことができて良かったです。

Klassicの宣伝。型推論とは単に変数の型が省略できる程度じゃないんじゃよー、というのが伝えたかっただけです。

懇親会は少人数ですが、LLVM、Rust、Kotlin、Swiftと色々な話が飛び交い、大変楽しかったです。

RyotaMurohoshiさんに是非第二回を!と言われたので、またKotlinについて何か疑問が浮かんだら検討したいところです。参加者の皆様、ありがとうございました。

さて、次の週はRust基礎勉強会があるので、こちらの準備も始めなければいけない。忙しない…。

Klassic開発日誌(2016/11/20): Hindley-Milner型推論はじめました

以前、

kmizu.hatenablog.com

という記事を書いたことがあったのですが、このときはまだ多相型を実装しておらず、Dynamicという謎の型でごまかしていましたが、その辺の制限をとっぱらいましたという話です。

型推論というと、最近はやりの言語はだいたい型推論を持っているとか言われそうだけど、それは誤解なのです(といいつつ、自分も長いものには巻かれろ的な感じで、そういう意味で型推論という言葉を使うことがよくありますが…)。おそらく、そういう方の思い浮かべる型推論というのは、

val x = expression //x: typeOf(expression)として推論される

というようなexpressionの型を単にそのままxの型として付与するというようなものだと思います。

このようなものはより一般には(たぶん)局所型推論(local type inference)と呼ばれ、型推論のごく限定的なパターンでしかありません。

型推論アルゴリズムとしておそらく最も著名で、その後色々なアルゴリズムの基盤になったものに、Hindley-Milnerの型推論アルゴリズムがあります。これは、先程のように単方向なものでなく、双方向に推論が行われます。

たとえば、現在(2016/11/20)、Klassicのプログラムで階乗は次のように書けます。

def fact(x) = {
  if(x < 2) 1 else n * fact(n - 1)
}

このfact関数の型は、引数の型も返り値の型もいっさい書いていないにも関わらず、Int => Intと推論されます。これは、Hindley-Milnerの型推論アルゴリズムを使うと、そういう感じの推論がされるようになります。

Hindley-Milnerの型推論の原理については、ぐぐれば色々情報が出て来ると思いますが、Standard ML, OCaml, HaskellとかはいずれもHindley-Milner(の拡張)なので、同様のプログラムを型注釈いっさいなしで書くことができます。

ともあれ、これでようやく多相型が動き始めたので多相型がないと書きづらい標準関数とかも整備し始めています。headとかtailとかconsとかその他色々。

Kotlinのコレクションに対してstreamメソッドが呼び出せない

Java 8でjava.util.Collectionに追加されたメソッドとして、Streamを返すstream()メソッドがあります。これ、java.util.Collectionに追加されたメソッドなのだから、当然Kotlinでも呼び出せて良いはずですが、実はできません。

>>> val x = listOf(1, 2, 3, 4, 5)
>>> x.stream()
error: unresolved reference: stream
x.stream()
  ^

Scalaでは何の問題もなくできます(なお、SAM Type変換を行っているので、Scala 2.12以降でのコードです)。

scala> import scala.collection.JavaConverters._
import scala.collection.JavaConverters._

scala> val x = List(1, 2, 3, 4, 5).asJava
x: java.util.List[Int] = [1, 2, 3, 4, 5]

scala> x.stream()
res0: java.util.stream.Stream[Int] = java.util.stream.ReferencePipeline$Head@3739f3c9

scala> x.stream().filter{e => e % 2 == 0}
res1: java.util.stream.Stream[Int] = java.util.stream.ReferencePipeline$2@59371066

さて、何故、このような差が生まれてしまったのでしょうか。KotlinではJavaのコレクション・フレームワークを、実装上は再利用しつつ、型としては違う振る舞いを与えているからです。そのため、無理やりjava.util.Collectionにキャストしてやると、stream()メソッドが呼び出せるというめんどくさい挙動になっています。

>>> val x = listOf(1, 2, 3, 4, 5)
>>> (x as java.util.Collection<Int>).stream()
java.util.stream.ReferencePipeline$Head@15d0c81b
>>> (x as java.util.Collection<Int>).stream().filter{it % 2 == 0}
java.util.stream.ReferencePipeline$2@587c290d

よーするにKotlinのコレクションはJavaのコレクションだといいながら、型としてはJavaのコレクションだと思って扱うと上手くいかないという悲しい例です。 JavaとinteroperableじゃないKotlinの悲しい一面です。

ところで、

kotlinlang.org

をみると、

Kotlin supports Java 8 streams, which provide similar functionality

と書いてありますが、こういうのをみると、どこがやねん(何故か関西弁っぽい)とツッコミたくなります。

Kotlin用不変コレクションライブラリ kollection 0.4リリース

しばらく触っていなかったのですが、ふと思い立って、データ構造を追加してみました。

具体的には、

の二つを追加しました。実装はほとんど、Scala版のRedBlackTreeのポーティングですが、is乱発しなければいけなくて、結構めんどかったです。

GitHub - kmizu/kollection: Immutable Collection Libraries and Additional Utilities for Kotlin

Kotlinのnullable typeはzero overheadではありません

タイトルの通りなんですが、JetBrainsさんが公式で

Zero-overhead null-safety

とか書いているおかげで信じている人もいるかもしれません。ですが、それは正しくありません。

試しに、次のコードをコンパイルしてみましょう。

fun double(x: Int?): Int = x?.let{ it * it } ?: 0 

クラスファイル BoxingKt.class が生成されるので、javapしてみましょう。

Compiled from "Boxing.kt"
public final class BoxingKt {
  public static final int foo(java.lang.Integer);
    Code:
       0: aload_0
       1: dup
       2: ifnull        21
       5: astore_1
       6: nop
       7: aload_1
       8: checkcast     #9                  // class java/lang/Number
      11: invokevirtual #13                 // Method java/lang/Number.intValue:()I
      14: istore_2
      15: iload_2
      16: iload_2
      17: imul
      18: goto          23
      21: pop
      22: iconst_0
      23: ireturn
}

まず、引数の型がjava.lang.Integerになっています。これは、引数を渡す時にBoxingのコストが発生することを意味します。また、その値を使って計算する場合、Unboxingのコストが発生します。

この問題は、プリミティブな型をnullableにしたときに発生します。ジェネリクスでプリミティブ型相当を引数にしたときにBoxingが発生するのと理屈は同じです。

必ずしもこの点が問題にはならないとは思いますが、一般にKotlinのnullable typeがzero overheadというのはだと言って良いでしょう。

Klassic開発日誌(2016/10/08):型チェックはじめました

冷やし中華はじめました、みたいなこと書いてみたかっただけです。はい。

これまでKlassicでは、メインのインタプリタは(あとで静的型をつけることを意識しつつ)動的型言語でしたが、少しずつ静的型を加えていっています。現在のところ、まだ多相型を扱えないという制限はあるものの、

val x = 1 // xはInt
x = 2 // 再代入不可

mutable y = 1 // xはInt
y = 2 // 再代入可能

val list = new ArrayList
list.add(1)
list.add(2)
list.add(2)
println(list) // リストリテラル。[1, 2, 3] 

println([1 2 3]) // [1 2 3]
println([
  1
  2
  3
]) // [1 2 3]

val map = #["key": "value"]// マップリテラル。
println(map)

などのコードが動きます。多相型が必要なところは現在Dynamicという型を導入することでごまかしています。階乗を計算するコードは、

def fact(n) = if(n < 2) 1 else (n * fact(n - 1))
println(fact(4))

のように書けますが、今のところ引数の型宣言を省略するとDynamicになるというなんとも微妙な仕様になっています。

また、substring関数の型は(Int, Int) => Dynamicのようになっています。この辺はJavaとのinteroperabilityを考えつつ慎重に設計したいところです。ただ、Klassicの開発目的の一つとして、サブタイピングの適切な制限というのがあって、その辺は、Javaとのinteroperabilityを考えると使い勝手が下がるので難しいところです(もちろん多数の先行研究があるのは承知の上ですが、とりあえずしばらくはテキトーに実装してみて、つまづいたら先行研究を参照しようかと思います)。

JSONのようでそうでないデータフォーマットNSON 0.0.1リリース

きっかけは、昨夜の思いつきでした。

JSONでも以前から、末尾のカンマを許すようにしてほしいとかそういう要望があったと記憶していましたが、そもそもカンマを要らなくすれば解決では?というのが動機です。

NSONは次のような特徴を持っています。

  1. オブジェクトの属性を区切るカンマが必要ない
  2. 配列の要素を区切るカンマが必要ない
  3. 属性のキーとして、文字列リテラルの他に通常の識別子が使える
  4. JSONの完全上位互換である

まず最初の点についてですが、たとえば、

{ "x": 1 "y": 2}

のような記述ができるということです。また、改行で要素を区切って

{ "x" : 1
  "y" : 2 }

のように書くこともできます。

その次の点ですが、これは最初の点と同じようなものです。

{ "like": ["Scala" "Nemerle" "Scheme"] }

このように、配列の要素をカンマで区切る必要がありません。

3番目の点ですが、これは、JavaScriptでは許されていたものの、JSONでは許されなくなった点の一つであり、たとえば、

{ x: 1 y: 2}

のような記述が許されます。

最後の点ですが、これはそのままです。JSONで正しいデータはNSONでも正しいデータです。たとえば、

{ "x": 1, "y": 1}

は正しいJSONのデータであり、かつ、正しいNSONのデータです。

詳しくは、以下のURLを参照してください。

GitHub - kmizu/nson: NSON: an object notation that is not a JSON but alike JSON.

NSONは構文上の実験であり、今後メンテナンスしていくかは正直微妙です。これを拡張していくことで何か書きやすいデータフォーマットが生まれる可能性もあるので、思いついたら何か手を加えていくかもしれません。

ちなみに、思いついてからNSONのパーザを書いて、ある程度動作するようになるまで3時間くらいでした(自作のKlassic言語のパーザがある程度流用できたので、ちょっとズルいかもしれません)。こと構文解析においてはさすがだな自分と自画自賛しておきます。