kmizuの日記

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

プログラミング言語作成ハンズオンを開催しました

connpass.com

今回開催したこのイベントは、私が学習用に作成したプログラミング言語nub

github.com

の文法や機能拡張を通じて、プログラミング言語処理系の作成の基礎について学ぶというものでした。

自分がこのイベントを開催したねらいは主に二つあって、

というものでした。準備には十分時間をかけたかったので、昨年秋から募集を始め、また、チューターとなってくれる 方も同時に募集しました。結果として、応募人数は十分過ぎる程、チューターも4名（うち2名は遠方（静岡と名古屋から！））来てくれる ことになりました。

チューターのno_maddoさん、yontaさん、long_long_floatさん、tetsuromさんの協力があったのは、特に、自分一人では質問に対応するのに 限界がある以上、大変助かりました。

反省点

さて、イベントを開催してみての手応えですが、興味を持ってがんがん手を動かしてくださった方も居た一方で、どう拡張すればいいかわからず 途方にくれていた方も居たように思います。後者のような人が出た原因の一つは、私が作成した学習用言語nubの仕様が学習用途としてはあまりにも リッチ過ぎたということがあったようです。この点は、nomaddoさんからも事前に指摘をもらっていたのですが、nubは

  • 変数宣言
  • 四則演算式
  • 比較演算式
  • if式
  • while式
  • 関数のユーザ定義・呼び出し

などを備えており、そこからさらに拡張しようと思うと、ややジャンプが必要であったのでした。私は当初この問題については軽く考えていた、というより、 プログラミング言語処理系初学者の気持ちがよくわかっていませんでした。結果として、どう拡張すればいいかわからない参加者がある程度出てしまう結果 になったようです。

実は、最初の機能追加提案としては、文字列型のサポートを考えていたのですが、no_maddoさんらの指摘もあったため、軌道修正しました。そして、二項演算子を追加する 提案を、ライブコーディングを交えて行ったところ、ある程度は効果があったようです。このような指摘がなければ、イベントとしては独りよがりなものになっていたかもしれません。 大変ありがたいことです。実際、文字列型のサポートに関してはイベント期間中に出来た参加者もいたものの、どうやっていいのかよくわからない方も居たようです。

nubの当日の仕様としては、現在のものから四則演算の一部を削り、さらにwhile式や関数のユーザ定義を削るくらいでちょうど良かっただろうというのが終わってみての実感です。

気づいた点

今回のイベントの目的の一つは、プログラミング言語処理系初学者がどこでつまづくのかを知ることでしたが、これに関してはある程度知見が得られたと思います。いくつかわかった点がありますが、特に

  1. ベタとメタの混同（という言い方が正しいかは微妙だけど）
  2. （具象）文法定義は難しい
  3. 再帰的な解釈（文法やインタープリタにおける）は難しい

が印象的でした。

最初の点ですが、たとえば、ある構文木のノードが変数名を保持する変数iを持っていたとして（この名前は良くないのですが、それはそれとして）、この変数iと nubの実際のプログラムで使われる変数であるiとの混同をしている方が居ました（当たり前のことですが、それが悪いとかいう意味ではなく、そういう混乱があるのだという単なる感想です）

二点目。今回、文法定義にはANTLR V4を使いました。これは、現存するパーザジェネレータの中で最も使い勝手や能力（扱える文法の範囲の広さという意味で）が高いものだったからですが、それでも苦戦していた人は多かったようです。この点を踏まえて、懇親会では、具象構文を使わずに抽象構文木を組み立てて解釈するだけにすればという話も出ました。一理あるとは思いますが、個人的な趣味としては、また、今後の可能性としても、具象構文を自在に操る能力はあって損はないとも思います。

三点目。これはそもそも再帰自体が難しいということに通じるのですが、プログラミング言語処理系の世界では、ごく当然のような顔をしてあちこちに再帰があらわれます。これはおそらく、苦労して再帰を扱っている人にとってはかなりしんどいのではと思いました。

また、これは最初から面倒になることがわかっていたのですが、代数的データ型およびパターンマッチングがない言語でプログラミング言語処理系作成を教えると、回り道があちこちできるので大変よろしくないことです。これはまあ、言語人口の多さを考えてJavaを選んだときからわかっていたことなのですが、早く主流の言語に代数的データ型とパターンマッチングが入って欲しいものです。

おわりに

何はともあれ、イベントは無事終了し、自分はいくつかの知見を得られました。参加者も全員とはいかないとは思いますが、プログラミング言語処理系を学習するきっかけになった方がいると思っています。チューター陣の方々にはお手数をおかけしましたが、おかげさまで質問に対して手が回らないという事態にはならずに済みました。また次回、このようなイベントがあるかはわかりませんが、もしやるとしたら、今回の範囲を踏まえて、もっと初歩から一歩一歩丁寧にやる形のものにしたいと思います。

ではでは、おやすみなさいませ。

正規表現のようでそうでない文字列マッチングライブラリ 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をチェックしているコードを読んで、「これでわかる！」と行きたかったのですが、結構難しかったので断念。代わりに、以前作ったスライドにちょこっと追加したものでお茶をにごしました。第二回があれば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

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