kmizuの日記

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

自作パーザコンビネータライブラリを集めたリポジトリ mlcombinators を公開しました

私がプログラミング言語を学ぶときには、パーザコンビネータライブラリを作る、ということはScala福岡2019の講演とかでも他のところでもよく言っていることなのですが、せっかくなので、これまで私が作ってきたミニパーザコンビネータライブラリ集をひとつのリポジトリにまとめて公開することにしてみました。もちろん、これだけでは到底実用に耐えないことは言うまでもないです。

github.com

なお、mlはプログラミング言語のMLとはあまり関係なくて、multi-languagesくらいの意味です。それはともかく、このリポジトリには、私がそれらのプログラミング言語を学びたての頃(一部例外あり)にどのようにしてパーザコンビネータライブラリを組み立てたのか試行錯誤の跡が残っており、ひょっとしたらどなたかの参考になるかもしれません。

実は、これ以外にもC#とかCとかもっと色々なものについてパーザコンビネータライブラリを作った気がするのですが、その辺はGitHub以前(?)だったせいか、残っていないようです。

ではでは。

(追記)その言語のプロからみると、ここがいけてないとか色々言いたいことはあると思いますが、その辺はIssue立てるなりPull Requestしていただけたらベストエフォートで対応します。

実践Scala入門(共著)が発売されます

https://www.amazon.co.jp/dp/4297101416

企画自体は2015年くらいから始まっていたんですが、紆余曲折あって、約3年経ってしまいました。ともあれ、ようやく出版までこぎつけられてほっと一息です。 実際には多少遅れる可能性がありますが、10月27日から技術評論社さんから発売予定なので、この機会にScalaを勉強してみたい方は、是非予約していただければと思います。 さて、書いてる間の紆余曲折書いても意味がないので、このエントリでは、この書籍のウリを簡単に書きたいと思います。

現状の日本語のScala書籍は、大半が新しいバージョンのScalaに追随できてなくて、新しくScalaに入門する人に勧められるいい書籍が ほとんどないという問題意識がありました。いわゆるコップ本はScala書籍の中でもかなり売れていることもあってか、2.12対応の第三版まで出版されているものの、 重厚長大であるために敬遠する人が多いという課題があります。というわけで、もうちょっと「コンパクトなコップ本」があるといいなということで、それが今回の 実践Scala入門のコンセプトになっています。

「コンパクトなコップ本」というのが何を指しているのかですが、コップ本の中で特に重要だと私たち(共著者)が考えたものをピックアップして、もうちょっと 手軽に読めるものを作ろうといったところです。ページ数もコップ本に比べてだいぶ少なめなので、コップ本に挫折した人にも比較的気軽に手に取ってもらえる とうれしいと思っています。ちなみに、Scalaのバージョンは2.12.7対応です。

もう一つのウリは、入門本でありながら、単に言語の解説に終始するのではなく、sbtの使い方やテストの書き方、コレクションライブラリの使い方など、ある程度 実践寄りの内容も盛り込んだところです。この書籍だけで実践のための知識が十分に身につくとは、もちろんいいがたいですが、「おわりに」で今後のための参考文献 も示してあるので、リストアップした参考文献を元によりステップアップしていってもらえればと思います。

ただ、実践寄りの内容「も」あるとはいえ、あくまで入門書であるので、Scalaでプロダクションコードを書くためのノウハウががっつり詰まった本を期待されると ミスマッチが発生するかもしれません。

ちなみに、目次はこんな感じです。

  • はじめに
  • 第1章「Scalaひとめぐり」
  • 第2章「Scalaの基礎」
  • 第3章「Option/Either/Tryによるエラー処理」
  • 第4章「コレクション」
  • 第5章「並行プログラミング」
  • 第6章「Scalaプロジェクトのビルド」
  • 第7章「ユニットテスト
  • 第8章「知っておきたい応用的な構文」
  • 第9章「よりよいコーディングを目指して」
  • おわりに

なお、実践Scala入門はScala入門書ではあっても、プログラミング入門書ではない(最低1つのプログラミング言語を習得していることを前提とする)のでその点は注意していただければと思います。

そのあたりを踏まえた上で、購入を検討していただければ幸いです。

ScalaMatsuri 1日目の雑感

ScalaMatsuri Training Dayは、別チケットであることからもわかるように、ScalaMatsuriとは若干独立していました。というわけで、この日から本番でした。この日、私が一番楽しみにしていたのはMartin Thompsonさん(Javaで高パフォーマンスのメッセージングライブラリLMAX Disruptorの作者でもある)の発表でした。彼はScalaにはあまり縁がない人物ではありますが、Javaカリカリに性能をチューニングをする専門家であり、そのノウハウの一端でも聞ければという思いでした。

関数型プログラミングによるパフォーマンス」

寝坊したので間に合わないかと思いましたが、タクシーに乗って、なんとかMartinさんの発表には間に合うことができました。しょっぱなからHaswellのアーキテクチャ図を示して、低レベルな部分での動きを把握することの重要さを語っていたのが印象てきでした。また、関数型データ構造について、一般的には木構造が多いが、それはポインタをたぐる操作を多用するために、現代のCPUアーキテクチャでは遅くなりがちであるというのはなるほどと思いました。後半、CRDTというデータ構造を中心に説明が進んでいくのですが、私は恥ずかしながらCRDTについてほとんど知らなかったので、後半ついていけなくなったのが少々悔しかったです。まとめとしては、関数型データ構造を使うときでもハードウェアを意識すべきだ、ということでしょうか?

HaskellScala

これは私の発表ですが、HaskellScalaについて、言語戦争に陥らないように、それぞれの利点を比較しようという趣旨のものでした。聴衆の方にうまく伝わったか自信がないのですが、私は、最近のScalaコミュニティがHaskellから学ぶことはあっても、ML系言語からあまり学んでいないことにもったいなさを感じていて、ScalaでMLスタイルのモジュールがエミュレートできることを示すことで、MLから学ぶこともあるのだということを主張したかったのでした。なお、発表中は、Scala型推論は雑魚ですという言い方をしたのが結構うけたようですが、これ自体はまぎれもない事実です。しかし、型システムの表現力と型推論の強力さは一般的にトレードオフの関係にあるものであり、両立させるのが難しいので、どちらを取るかは好みの問題かもしれません。

なお、発表の後、元、筑波大学のM先生と鉢合わせした(M先生が非学術系のこういうイベントに参加されるとは思っていなかったので)のは印象深かったです。Scala型推論をディスったことについても、もうちょっとScala型推論を評価してもいいんじゃないかなあということを言われましたw(M先生は型システムの専門家です)。

Haskell + Scala ハイブリッド開発大作戦」

HaskellJVM用の実装Eta、というか、処理系としてはGHCをベースにしてクラスファイルを出力するもの、ととらえればいよいのでしょうか、についての発表でした。正直なところ、Etaの実装については興味深かったのですが、現在のJavaジェネリックスととても相性が悪そうなところが気になりました。また、ただでさえコンパイルが遅いScalaなのに、それにさらにコンパイルが遅いであろうEtaGHCベース)と組み合わせて大丈夫なのかとか、Javaとの連携がScalaほどうまく行かなそうなのが気になりました。用途としては、Java側のfacadeを用意して、それをHaskellを呼び出すようにするのが一番良いのでしょうか。

その他

昨日に引き続き、不眠気味で体力がかなりぎりぎりだったので、自分の発表といくつかの発表を聴いた他は休憩用のソファーで休んでいました。せっかくのMatsuriなのでもったいないとも思うのですが、体調の問題はどうしようもなく。

この日は、懇親会があったのですが、私はオプテピピック会場で色々な方とお話しました。中にはカンボジアからはるばる来られた方や、自分に関係のある方(詳細は伏せますが)との思いがけない出会いもあって楽しく過ごすことができました。

私は、体力的には懇親会が終わったあたりで限界が来ていたので、翌日のアンカンファレンスにも出られませんでいたし、楽しみ切れたかわからないのですが、とりあえず私の発表に穴を空けずに済んだことはほっとしています。

後日、公開されるであろう動画を見て、今回視聴できなかったお話を見てみようかと思います。

以上、短い感想でしたが、読んでくださった方ありがとうございました。

ScalaMatsuri 2018 Training Dayの雑感

今は金曜の夜(土曜日の朝とも言う)で、眠れないので、せっかくなので感想でも書いてみるかーってな具合に書いてみることにしました。

さて、ご存じの方も多いかもしれませんが、2016に実質運営を譲って、2017には名目上も座長の権限を譲ったため、今年は私は 特に運営に関して大きな働きをしていません(というのも控えめな言い方で、ほとんど何もしてない気がする)。

というわけで、今回は、一参加者としてのイベントの所感を書いてみようかと思います。

Training Day

今年からの試みであるTraining Day、Scalaにあまりなじみのない人にも参加してもらえるようにと、別チケットが用意されましたが、無事、完売に近いようになったようです。

Scalaに関する神話と真実」

私の発表は、「Scalaに関する神話と真実」というタイトルで、Scalaになじみのない人の、Scalaに関する誤解を解こうというのが主眼でした。Scala福岡に来られていた方はご存知かもしれませんが、そのときの発表をベースに、細かいところを調整したものになります。いくつか質問があったのですが、印象に残っていたのは、「Scalaに移行しているのですが、nullなどを使われてなかなかうまく行かないが、どうすればいいのか」というものでした。そのときの答えとしては、私は「nullダメ絶対」ということで、nullを使うコードはレビューではじくという方針を提案したのですが、質問者の方は、レビュー体制が整っていないので、これから頑張ってみます、という回答でした。正直なところ、コードを(初期に一人でがりがりと書くときはともかく)レビューがないというのはあまり想定していなかったので、意外でした。他にもそういう現場は結構あるのでしょうか。Scalaに限らずコードレビューを行える体制がないと色々しんどいので、少人数だとしても、なんとかコードレビューができる体制を作るのが重要ではないかと思いました。

その他

実は不眠気味で、体力をかなり消耗していたので、自分の発表で手一杯で、あまり他の方のセッションを見に行く余裕がなかったのですが、まあScalaになじみのない人向けのセッションだからいいかと開き直っていました。Training Dayではスピーカーディナーがあったのですが、体力的に余裕がなかったために行けなかったので残念でした。とにかく、自分の発表に穴を空けなかっただけでもほっとしました。

Hello, Dart (2) - パーザコンビネータ

いつだったか、新しい言語を学ぶときのHello, Worldはパーザコンビネータを書くことにしてる、といった事を言った覚えがあります。実際、これまで学んできたたいていの言語でミニパーザコンビネータライブラリを書いてきました。というわけで、Dartでもパーザコンビネータライブラリを書いてみました。

もう何度も何度も書いてきたコードのため、考えるのは、その言語での標準的なデータ構造と関数に落とし込む方法だけです。というわけで、次のような感じになりました。クラスの定義方法とかコンストラクタの扱い、無名関数の文法、文字列の取り扱い、など基本的なことを一度に学べるので、パーザコンビネータという題材はやはり良いなと思います(自画自賛)。

感想:

  • 色々な面でかなりJavaプログラマフレンドリ。
    • 適当にJavaっぽい文法で書くとそれなりにパーズしてくれる可能性が高い。
  • 関数/メソッドの本体が式であるときに使える、 => 記法は便利。というか、これがないと不便。
  • 多相オペレータを定義できないのはちょっと不便。
    • Parser<Pair<T, U>> operator &<U>(Parser<U> that) みたいなのを書きたいが、これはDartでは許されないようだ。
  • Javaと違って、プリミティブ型を意識せずに済むのは楽。
  • コンストラクタの略記法が中途半端。フィールドへの代入コードを手動で書くよりは楽だが…
  • 関数の型の文法が、Cっぽい微妙さ。 Ret funArg(Arg1 arg1, ...) のように書くのだが、これだと関数を返す関数の型が綺麗に書けない…
    • typedef すればいいのだけど。
  • Javaでメソッドの型パラメタの宣言の位置がヘンテコだった問題は解決されている。

全体的に、Dartは、今の時代の言語としては平凡な感じがぬぐえませんが、その分、変な癖がないとも言えそうです。また、JavaプログラマDartを学ぶのはかなり簡単であるという 感想を持ちました。

abstract class ParseResult<T> {
  String next;
  ParseResult(this.next) {}

  T get value;
  bool get successful;
}

class Pair<T1, T2> {
  T1 item1;
  T2 item2;
  Pair(this.item1, this.item2);

  String toString() {
    return '(${item1}, ${item2})';
  }
}

class ParseSuccess<T> extends ParseResult<T> {
  T value;
  ParseSuccess(this.value, String next) : super(next);
  @override bool get successful => true;
  @override String toString() => 'ParseSuccess(${value}, ${next})';
}

class ParseFailure<T> extends ParseResult<T> {
  T value = null;
  ParseFailure(String next) : super(next);
  @override bool get successful => false;
  @override String toString() => 'ParseFailure(${next})';
}

typedef ParseResult<T> ParserFunction<T>(String input);

typedef U BiFunction<T1, T2, U>(T1 t1, T2 t2);

class Parser<T> {
  ParserFunction<T> fun;
  Parser(this.fun);
  ParseResult<T> call(String input) => fun(input);

  Parser<T> operator |(Parser<T> that) => parserOf(
    (input) {
      var r1 = this.fun(input);
      if(r1.successful) {
        return r1;
      } else {
        return that.fun(input);
      }
    }
  );

  Parser<Pair<T, U>> then<U>(Parser<U> that) => parserOf(
    (input) {
      var r1 = this.fun(input);
      if(r1.successful) {
        var r2 = that.fun(r1.next);
        return r2.successful ? 
          new ParseSuccess<Pair<T, U>>(new Pair<T, U>(r1.value, r2.value), r2.next) :
          new ParseFailure<Pair<T, U>>(r1.next);
      } else {
        return new ParseFailure<Pair<T, U>>(input);
      }
    }
  );

  Parser<U> map<U>(U f(T result)) => parserOf(
    (input) {
      var r = this.fun(input);
      if(r.successful) {
        return new ParseSuccess<U>(f(r.value), r.next);
      } else {
        return new ParseFailure<U>(r.next);
      }
    }
  );

  Parser<T> chain(Parser<BiFunction<T, T, T> > q) =>
    this.then(q.then(this).many()).map((t) {
      var init = t.item1;
      var list = t.item2;
      return list.fold(init, (a, fb) {
        var f = fb.item1;
        var b = fb.item2;
        return f(a, b);
      });
    });

  Parser<List<T>> many() => parserOf(
    (input) {
      var rest = input;
      List<T> values = [];
      while(true) {
        var r = this.fun(rest);
        if(!r.successful) return new ParseSuccess(values, rest);
        values.add(r.value);
        rest = r.next;
      }
    }
  );

  Parser<List<T>> many1() => this.then(this.many()).map((t) {
    List<T> result = [];
    result.add(t.item1);
    result.addAll(t.item2);
    return result;
  });
}

Parser<String> range(String from, String to) => parserOf((input) {
  var f = from.codeUnitAt(0);
  var t = to.codeUnitAt(0);
  if(input.length < 1) {
    return new ParseFailure<String>(input);
  } else {
    var c = input.codeUnitAt(0);
    if(f <= c && c <= t) {
      return new ParseSuccess<String>(input[0], input.substring(1));
    } else {
      return new ParseFailure<String>(input);
    }
  }
});

Parser<T> rule<T>(Parser<T> body()) => parserOf((input) =>
  body()(input)
);

Parser<T> parserOf<T>(ParserFunction<T> fun) => new Parser<T>(fun);

Parser<String> s(String literal) => parserOf((input) =>
  input.startsWith(literal) ? 
    new ParseSuccess<String>(literal, input.substring(literal.length)) : 
    new ParseFailure<String>(input)
);

使う側はこんな感じです。

import 'dart:core';
import 'parser_combinator.dart';

Parser<int> expression() => rule(
  () => additive()
);

Parser<int> additive() => rule(
  () {
    Parser<BiFunction<int, int, int>> Q = s('+').map((op) => (int lhs, int rhs) => lhs + rhs);
    Parser<BiFunction<int, int, int>> R = s('-').map((op) => (int lhs, int rhs) => lhs - rhs);
    return multitive().chain(Q | R);
  }
);


Parser<int> multitive() => rule(
  () {
    Parser<BiFunction<int, int, int>> Q = s('*').map((op) => (int lhs, int rhs) => lhs * rhs);
    Parser<BiFunction<int, int, int>> R = s('/').map((op) => (int lhs, int rhs) => lhs ~/ rhs);
    return primary().chain(Q | R);
  }
);

Parser<int> primary() => rule(
  () => number() | (s('(').then(expression()).then(s(')'))).map((t) => t.item1.item2)
);

Parser<int> number() => rule(
  () => range('0', '9').many1().map((digits) => int.parse(digits.join()))
);

void main() {
  var e = expression();
  print(e('1+2*(3/4)'));
  print(e('(1+2)*3/4'));
  print(e('10+20*30'));
}
$ dart parser_usage.dart
ParseSuccess(1, )
ParseSuccess(2, )
ParseSuccess(610, )

Hello, Dart (1) - フィボナッチ数列

Flutterを触ってみたくなったので、ついでにDartの勉強も始めることにした。手始めに、フィボナッチ数列を求める Stream を作って、そっから最初の10要素を取り出して表示するというプログラム。

import 'dart:async';
import 'dart:core';

main() async {
  var fibs = await fib().take(10).toList();
  print(fibs);
}

Stream<BigInt> fib() async* {
  var a = new BigInt.from(0);
  var b = new BigInt.from(1);                                                   
  while(true) {
    yield a;
    var c = a + b;
    a = b;
    b = c;
  }
}
$ dart fibs.dart
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Stream#toList() は非同期に処理が完了する Future<List<T>> を返すのだけど、 await で結果を待って List<T> に変換することができるようだ。

ScalaMatsuri 2018 Training Dayで「Scalaに関する神話と真実」という発表をします

このブログを更新するのも、ちょっと久しぶりですね。今回は宣伝というか、表題の件についてちょっと書こうと思います。

ここ数年、ScalaMatsuriはかなりの規模で開催されています。例年は2日間だったのを、3日間に拡張して、最初の1日を 「Training Day」として、主に、Scala初学者やScalaを普段触っていない人向けのプログラムにすることになりました(プログラムはこちらです)。

さて、このTraining Day、結城清太郎さんによる「Scalaハンズオン」、山本裕介さんによる「IntelliJ ハンズオン」などなど、ハンズオン形式のものや入門的な発表が多数あります。Scalaって最近どうなのよという初学者の方や、昔Scalaを触っていたけど最近は触っていないといった人に楽しんでいただけるイベントになると思います。Training Dayのチケットはこちらからお願いします*1。これが1点目。

もう一つは、Training Dayでの自分の発表に関することです。「Scalaに関する神話と真実」と題していますが、要はScalaに関しては色々神話とか誤解(もちろん、真実もありますが)が多数あるので、それを解きほぐすことで、Scalaに対する心理的障壁を下げるのが狙いです。似た発表として、Scala福岡の私の発表「Scalaにまつわる誤解を解く」を思い出された方もいるかもしれません。Scala福岡では比較的概要的な話が多かったですが、ScalaMatsuriでの発表では、より細部に踏み込んだ話をしようかと考えています(時間制約上どこまでできるかわかりませんが)。Scala福岡での発表を聴いた方にもそうでない方にも気づきがあるような発表にしたいのでよろしくお願いします。

例えば:

  • コンパイル時間の問題を緩和するには、実際どうすればいいのか?
  • implicit parameterの利用が適切なとき、不適切なときとはどんなときか?
  • バージョンによる細かな違い

といった点にも触れられればと思います。

というわけで、皆さん、Training Dayのチケットを買って当日お会いしましょう。なお、私は、本編の2日目で「Haskell対Scala」をすることが決まっているので、そちらの方もよろしくお願いします。Haskeller対Scalaistのバトルにならないよう、仲良くできるような発表をしたいと思っています(^^;

*1:Training Dayのチケット*は本編(2日目以降)とは別売りですので注意してください