正規表現のようでそうでない文字列マッチングライブラリ PEGEX 0.3リリース

PEGEXを開発し始めたのが確か2010年の春頃でした。元々は、私の専門であるPEGに対してより正規表現ライクな記法をサポートしたものでした。それから6年、現在は既にPEGのセマンティクスはほとんど残っておらず、（おそらく）全ての文脈自由言語を扱えるような強力なマッチングツールに進化しました。

たとえば、PEGEXで、任意階層ネスト可能で、しかも開始タグと閉じタグが一致しているXMLのような文法、というのは次のようにして記述することができます。

#{E}$; 
E=<(?<tag>#{I})>#{E}*</\k<tag>>; 
I=[a-z]+;

実は、たとえば、Rubyの正規表現は既に古典的な意味での正規表現を超えており、再帰呼出しによってこのような文法を表現することができます。ただ、正規表現の記法に無理やり拡張を入れたため、正規表現を超えた部分についてはあまり可読性が良いとは言えません。PEGEXでは規則を;で分割することで、読みやすい形でパターンを記述することができます。より一般には、BNFで書かれているような仕様、たとえば、メールアドレスなどはPEGEXで比較的簡潔に記述できるでしょう。

PEGEXについて詳しくは、以下のページを参照してください：

github.com

今後は速度の向上や機能面で充実させていくことでより実用的にしていきたいと思っています。

次以降のバージョンで予定している機能のリスト： * POSIX文字クラス * アンカー文字列の強化 * パーズエラー時のメッセージを親切に * 引数付き規則のサポート

歯の健康を守ろう

この記事は、健康Advent Calendar 2016 12/13の記事です。

皆さん、歯、大丈夫ですか？自分は最近、右上の親知らずが虫歯にかかっていることが判明して抜歯する羽目になりました。ついでに、虫歯の治療も同時にしたせいで、一週間、左側の歯だけで飯を食わなければいけないことになりました。固いものはまず無理なので、これから１週間麺類とかスープとかやわらかいもの中心の食生活になりそうです。つらい。

なお、こういう歯の治療に行くと必ずといっていいほど、「歯磨きをちゃんとしてください」といったことを言われるのですが、歯医者が考える模範的な歯磨きは面倒過ぎてやってられません。かといって、ずっと放置していると今回の自分のように知らない間に大きな虫歯ができているということになります。

そういう事態を防ぐには、思うに、定期的に歯のメンテナンスに歯科に通うのがいいのではないかと思います（数ヶ月に１回くらい？）。歯石なども取り除いてくれますし、虫歯が深刻になる前にわかるというメリットもあります。

というわけで、皆さん、定期的に歯科に通いましょう。

Java (8)によるパーザコンビネータライブラリ JCombinator 0.0.1をリリースしました

Javaには既にJParsecというパーザコンビネータライブラリもあり、あえて新しいものを作る必要はないかもしれません。

ただ、JParsecはイマイチ気に入らなかったので、新しいパーザコンビネータライブラリを作ってみることにしました。とりあえず、基本的なコンビネータはそろっているので、デバッグの容易さとか考えなければこれで割と複雑なパーザを組むことも可能だと思います。

github.com

今後は、より色々なパーザを書きやすくするためのコンビネータの充実と、パーズエラー時のメッセージをわかりやすくすることに力を注いでいきたいところです。

例として、四則演算をできる式（括弧を含む）のパーザは次のようにして書くことができます。

import com.github.kmizu.jcombinator.datatype.Function2;

import static com.github.kmizu.jcombinator.Parser.*;
import static com.github.kmizu.jcombinator.Functions.*;

public class ArithmeticExpression {
    private Rule<Integer> expression() {
        return rule(() ->
            additive().cat(eof()).map(t -> t.extract((result, __) -> result))
        );
    }
    private Rule<Integer> additive() {
        return rule(() -> {
            final Parser<Function2<Integer, Integer, Integer>> Q = string("+").map(op -> (Integer lhs, Integer rhs) -> lhs + rhs);
            final Parser<Function2<Integer, Integer, Integer>> R = string("-").map(op -> (Integer lhs, Integer rhs) -> lhs - rhs);
            return multitive().chain(Q.or(R));
        });
    }
    private Rule<Integer> multitive() {
        return rule(() -> {
            final Parser<Function2<Integer, Integer, Integer>> Q = string("*").map(op -> (Integer lhs, Integer rhs) -> lhs * rhs);
            final Parser<Function2<Integer, Integer, Integer>> R = string("/").map(op -> (Integer lhs, Integer rhs) -> lhs / rhs);
            return primary().chain(Q.or(R));
        });
    }
    private final Rule<Integer> primary() {
        return rule(() ->
            number().or((string("(").cat(expression())).cat(string(")")).map(t -> t.item1().item2()))
        );
    }
    private final Rule<Integer> number() {
        return rule(() ->
            digit().many1().map(digits -> Integer.parseInt(join(digits, "")))
        );
    }

    public void testExpression() {
        Parser<Integer> arithmetic = expression();
        arithmetic.invoke("100").onSuccess(s -> {
            assert ((Integer)100) == s.value();
        });
        arithmetic.invoke("100+200").onSuccess(s -> {
            assert ((Integer)300) == s.value();
        });
        arithmetic.invoke("(1+2)*(3+4)").onSuccess(s -> {
            assert ((Integer)21) == s.value();
        });
        arithmetic.invoke("1+2*3+4").onSuccess(s -> {
            assert ((Integer)11) == s.value();
        });
    }
}

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

connpass.com

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

以下、各発表について。

• KotlinのSmart Castを探る: @kmizu

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

• Kotlinソースコード探訪 @yy_yank さん

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

• KotlinとJavaとnullのライトな話 @RyotaMurohoshi さん

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

• Kotlinのlexerを読む

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

• プログラミング言語Klassic

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リリース

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

具体的には、

• TreeMap: 赤黒木ベースのMap
• TreeSet: 赤黒木ベースのSet

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

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