kmizuの日記

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

Klassic言語開発日誌 〜列多相(row polymorphism)〜

最近、Klassic言語をちょくちょく更新しているのですが、半月くらい前にオブジェクトに関係する型推論の仕組みを入れました。知っている人は知っていると思いますが、OCamlとかにあるアレです。たとえば、

def distance(p, e) = {
  // abs: Double => Double
  // double: Int => Double
  val dx = abs(double(p.x - e.x))
  val dy = abs(double(p.y - e.y))
  sqrt(dx * dx + dy * dy) // sqrt: Double => Double
}

こういうKlassicプログラムがあったとします。これは、 Player ( p )とEnemy ( e )が引数に与えられたとき、それぞれが xy というメンバがあると仮定して、PlayerとEnemyの間の距離を計算する、というものです。

この関数の型を推論させてみると、以下のように推論されます。

distance : (
  record{ x: Int; y: Int; ...},
  record{ x: Int; y: Int; ...},
) => Double

算術演算子を適用しようとした場合に、他にいい候補がないときにデフォルトで Int を対象として選択するのは、現状のイケてない点ではありますが(型クラスを入れるのがいいのだろうか…)、とりあえず意図通りに推論されています。

まだ、メソッドの型推論を真面目にやっていないので、来月中にはその辺をきちっと作り込みたいところですが、ようやくオブジェクト指向言語を名乗ってもいいような感じになってきました。

ところで、row polymorphismってなんで行多相じゃなくて列多相って訳が定訳(?)なのでしょうか。どなたかご存知の方が居れば情報をいただきたく。

「構文解析ハンズオン」を開催しました(2017/07/01)

今まで、あまり見たことがない(一般エンジニア向け)勉強会で、かつ、これを学ぶことは実用上とても意味があるテーマの一つに「構文解析」があります*1

たとえば、Webアプリケーションにおいて、ユーザの入力に大して何らかの構文的制約をつけてバリデーションをする機会は多いですが、正規表現による簡単なチェック(あるいは、滅茶苦茶複雑な正規表現を作って色々な入力のバリエーションに対応する)や、よくわからない緩いバリデーションで済まされることは多いように感じます(自分の開発経験というより、Webアプリケーションのフォームのバリデーションの仕方などを見ての感想です)。

正規表現によるバリデーションで十分なことも多いので、それをむやみに否定するものではありませんが、入力が(原理的に)正規表現でバリデーションできない場合や、可能だが正規表現が爆発するケースだと、正規表現が不適当なこともしばしばです。

個人的には(文脈自由な)構文解析ができる技能があれば、もっと精度の高いバリデーションができるのに、と思っていたこともあり、構文解析の基本を学ぶ勉強会を開催してみることにしたのでした。

構文解析ハンズオン - connpass

というわけで、昨日に開催したのが、↑の勉強会です。ハンズオン形式で、1桁整数の構文解析JSON構文解析を学ぶ、というものです。

大学における構文解析の授業では、手書き構文解析の方法として、LL(1)のようなものを再帰下降パーザで模倣することが非常に一般的ですが、昨日の勉強会では、時間的制約( 全部で6時間程度しかない)や、自分のPEG推しという趣味もあって、PEGベースの再帰下降パーザを学んでもらう構成にしました。

参加者層は本当に構文解析初学者が多いので、PEGという言葉をだすと混乱するだろうと思われたため、そういう言葉を出さずに、PEG的な発想をそのまま教えるというアプローチを取りました。結果としては、短い時間でJSONのような再帰的構造を持つ言語の構文解析までたどりついてもらうには、それなりに有効なアプローチだったと思います。

反省点については

  • 資料を準備する時間が十分でなかったため、当日、大量のアドリブを入れて説明をする必要があった
  • 自分の構文解析器をテストするように、用意したプログラムを修正してもらうというやり方は遠回り過ぎた
  • 参加者層に対する要求である「Javaが普通に書ける」が曖昧過ぎて、参加条件を満たさない方も参加してしまった
    • それらの方に対する苦情というより、それだとハンズオンで構文解析を学んでもらうことが難しいので、結果的に申し訳ないことになってしまったなという意図です
  • 資料の細かいミスが結構あった
  • , etc.

と色々あるのですが、構文解析の基本をおさえてもらうという目的はある程度達成できたかなと思っています。

興味深かった(一部の方の)反応として、わかったか自信がないけど、心を無にすれば書けたという趣旨の発言が見られたことです。BNFからPEGベース手書きパーザへの(ほぼ)機械的な変換方法を提示するというやり方だったからだと思うのですが、PEGベースのパーザの単純さ、理解の容易さがそれに貢献したのではないかなと思います。

構文解析をテーマにした勉強会については、当分はしないと思いますが、その他の、「(情報系の)学部だと普通にならうけど、自習がやや難しい」系のテーマについて、積極的に教える機会を作っていきたいなと思っています。

*1:自然言語構文解析を主に指します

技術イベント「Understanding Scala」を開催しました(6/10)

Understanding Scala - connpass

昨日、表題の技術イベントを自分主催で行いました。なんでこんなイベントをやろうと思ったかというと「皆、Scalaを難しくめんどくさい方法で学んでるのでは?」という疑問が自分の中であって、その原因として、サンプルプログラムの集合を通して、ボトムアップになんとなくイメージで 全体像を作りあげてるのではという思いがありました。

そのようなアプローチに対して懐疑的な自分としては、このイベントでは(厳密にはやってませんが)どちらかというとトップダウン的アプローチでプログラミング言語について理解してもらおうと思い(もちろん、例は大切なので必要に応じて詳細に下りるのは忘れませんでしたが)、5つの発表の全てを全部自分でやりました。さすがに、5時間程度しゃべりっぱなしというのは疲れましたが、おかげさまで(?)、色々な疑問が解決したとか、メソッドと関数の違いがわかったとか、狙い通りの成果を持ち帰っていただけた方も多いようで、報われた気持ちになりました。

なお、発表資料は以下にあります:

後ろ2つの発表については、Scala特有の事項が多く出てきますが、最初の3つの発表は、学んだことを他の言語を学ぶ際にも多少は応用できるように内容を考えていたように思います。

自分としては、構文、型システム(がある場合)、意味論に分けて考えるのは、他のプログラミング言語を学ぶのに役立つと思うので、そういうアプローチでプログラミング言語を理解しようとする人がもっと増えてくれるといいなと思っています。

高階多相か高カインド多相、どちらが適切な用語かを考える

タイトルだけだと、わかってる人にしかわからないので、背景を説明します。サンプルコードはScalaですが、同じ機能はHaskellにもあります(あとは、C++のテンプレートテンプレート引数もこれに該当します。もうちょっとマイナーな言語だと他にいくつもありますが、プロダクション環境での事例がある程度ある言語だとこの三つくらいになると思います)。

今回考えたいのは、ある型システムに関して色々な用語が入り乱れているので、どれが適切なのかを検討したいということです。まず、次のようなScalaプログラムの断片を考えます。

trait Functor[F[_]] {
 def fmap[A, B](f: F[A])(g: A => B): F[B]
}

ここで、Functor[F[_]]で、パラメタとして渡せるものは、通常の型ではなく、型コンストラクタです。型コンストラクタというのは、何か引数を受け取って型を返すもので、具体的な例でいうと、List,Option,Vector,ArrayList,などなど、型パラメタを実際に与える前の何かを指します。型コンストラクタを与えたものとして、Functor[List],Functor[Option],Functor[Vector]などを、実際の型として考えることができます。

このようなものは、それ自体は型ではないので、単純なパラメタ多相(あるいはジェネリクス)では扱うことができません。そのため、パラメタ多相を拡張する必要がありますが、このようなパラメタ多相の拡張を何と呼ぶかについて、いくつかの用語があり、外野からみるとそれらが同じものなのか別のものなのか区別がつきにくいので、どの用語が最も適切かについて検討を加えてみようというのがこの記事の趣旨です。

まず、結論からいうと、使われている数の多さ、用語の歴史、概念をよく説明していることから、高階多相が適切だろうというのが自分の考えです。以下で、その根拠について説明していきます。

まず、このような多相性を表すことばとして、いくつかの用語があるので、それらをリストアップしてみます。

  • 高階多相(higher-order polymorphism)
  • 型コンストラクタ多相(type constructor polymorphism)
  • 高カインド多相(higher-kinded polymorphism)
  • 高カインドジェネリクス(higher kind(ed) generics
  • 高階ジェネリクス(higher order generics

ざっと調べただけでもこれだけ色々な用語が同じ概念を指す言葉として使われています。まず、自分は、型システム上の用語としてどれが適切かを考えたいので、特定の言語群に結びついたHogeHoge Genericsというのは避けたいところです。なので、HogeHoge Genericsは除外して考えます。

残る候補としては、

  • 高階多相(higher-order polymorphism)
  • 型コンストラクタ多相(type constructor polymorphism)
  • 高カインド多相(higher-kinded polymorphism)

になります。これらはどれも概念上はそれなりに妥当性がありそうですが、自分が知る限り、型コンストラクタ多相というのは、ScalaにおいてAdriaan Moors氏が導入した用語のようで、それ以前の用例は見つけることができませんでした(Google Scholarの検索結果においては)。それ以前からあったシステムに新たな用語を付ける必要もなかろうと思うので、型コンストラクタ多相も除外します。

あとは、高階多相か高カインド多相かということになりますが、まず、この二つの用語についてGoogle Scholarで検索した場合、前者(higher order polymorphism)は96件ヒットで、古い用例では1980年代からあるようです。また、型システムの教科書として定評のあるTypes And Programming Languages(日本語訳:型システム入門)では、高階多相(higher-order polymorphism)という用語が採用されており、これは伝統的な用語を踏まえたもののように思います。

後者については、higher-kind polymorphismが6件ヒットで、higher-kinded polymorphismが36件ヒット、また、両方とも2005年以前の用例がみつからない辺り、2005年以降のどこかの論文を参照した用語ではないかと思われます。

用語が使われてきた歴史や用例の多さ、著名な教科書に使われていることなどを考えて、高階多相という用語がもっともよさそうです。また、高階多相という用語は、型上の関数を考えたときに、型上の関数そのものを渡せるという意味で高階関数との類似性があり、名前としても妥当です。

無論、ある概念を他の用語で呼ぶべきでない、ということは一般に言えないですから、他の用語を使うことを積極的に止めるものではないですが、あえて統一するなら高階多相が一番妥当そうだという話です。

なお、私は型システムは専門ではないので、何かツッコミどころがある可能性はあるので、そういったことがあればコメントをいただければと思います。

Scala福岡2017で登壇してきます(2017/07/29(土))

Scala福岡主催のイベント、Scala福岡2017で登壇依頼をいただいたので、発表してきます。

詳しくは以下:

scala.connpass.com

今のところ、セッション参加枠がまだまだあるようなので、九州あるいは九州近辺在住で、Scalaについて興味のある方等、参加を検討してみてはいかがでしょうか。

私の発表は、「Scalaにまつわる誤解を解く」ですが、必ずしも誤解ではない話題についても扱う予定です。Scalaの導入を検討しているが、実際に導入するメリットがあるかわからないので躊躇している、という方に、結果として導入しないことになったとしても、判断の材料となることを色々話せればと思っています。また、Scala新人研修の結果わかったことなども話に含まれる予定です。この辺は、あまり知られていないので、参考になる部分も多いかもと思っています。

他には、@daiksyさん、@takezoenさんといった方々も登壇されるようです。

Klassic言語の現状のステータス

Klassic は自分が新たに去年くらいから開発し始めたプログラミング言語です。

まだ確固たる設計思想があるわけではなく、色々な構文や機能について試しに導入してみて、テストを書いて…みたいなのを繰り返してる 段階です。現状のKlassic言語の大雑把な特徴としては

  • ML多相に類似した型システム(ちゃんとした、というか、普通の型推論があります)
  • 静的スコープ(現在では当たり前過ぎますが)
  • 第一級関数(今では当たり前過ぎますが、組み込みの関数型があって、というあたりは、より、いわゆる「関数型言語」風味に寄せています
  • ヒアドキュメント
    • Rubyとかのあれですね。これは、ヒアドキュメントの構文をきちんと理解するための実験過程で入りました
  • スペースセンシティブなあれこれ
    • 色々なものをスペースセンシティブな、つまり、空白に意味を持たせてみると便利になるのではないか、という実験
    • スペースセンシティブかつ改行センシティブなリストリテラル
    • スペースセンシティブかつ改行センシティブなマップリテラル
    • スペースセンシティブかつ改行センシティブな集合リテラル
    • 改行センシティブな構文
  • cleanup式
  • Java FFI
    • これは、単純に色々な機能を実現しようとしたときに、あると便利なので暫定的に入っています

ML多相に類似した型システム

よーするに「普通の」型推論が行われるということです。「普通の」というのは単一化ベースの型推論で、(おそらく)型注釈 は書かずに全部推論できる(はず)という話です。

たとえば、

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

は、ちゃんとfact : Int => Intと推論してくれます。

mutable変数があるのに、多相性に制限つけてないので、mutable変数を考えると 健全でなくなるという大昔に解決された問題までそのまま残っています(笑)。これは、当然ながら型システムの性質として好ましく ないので、既存の解決法を流用するか、独自になんかそれっぽい解決法を適用してみる予定です

ヒアドキュメント

説明はあまりいらないと思いますが、

println(<<TAG1 + <<TAG2);
tag1
TAG1
tag2
TAG2

という感じのがちゃんとパーズされて動きます(一行に複数のヒアドキュメント開始が持てる(これはRubyもそうなので真似しています)点がポイントです)

第一級関数

map([])((x) => x + 1)

無名関数の文法はScalaの影響をかなり受けています。型クラスとかまだないので、x -> x + 1xの使われ方から、Int => Intとして推論されます。普通です。

スペースセンシティブかつ改行センシティブなリストリテラル

この辺の文法的な実験、というのが実は自分が一番やりたかったことです。

[1 2]

[1, 2]

と解釈されますし、

[[1 2]
 [3 4]
 [5 6]]

は、

[[1, 2],
 [3, 4],
 [5, 6]]

と解釈されます。要素を改行で区切るのは、trailing commaの利点も受けられるし、構文ノイズも入らないし、「思った通りにパーズされる」ので、割と良さげです。

スペースセンシティブかつ改行センシティブなマップリテラル

リストリテラルと同じような文法をマップリテラルにも入れてみました、というお話。

val points = [
  %["x":1 "y":1 "z":2
    "x":1 "y":1 "z":3]
]

%[で始まるのがマップリテラルで、キー・値ペアが空白でも改行でも区切ることができます。これもまあ、割と思った感じにパーズされます。集合リテラルの文法はリストリテラルとほとんど同じなので省略。

改行センシティブな構文

最近の言語には割とありがちですが、改行が色々なものの区切りになることができます。ただし、純粋に改行が来ると区切る、のだと困るケースもあるので、その辺はパーザが頑張ってます(この辺をどう頑張るかは言語によって異なると思いますが、Klassicでは割と単純な方法を採用しています)。

基本的なケースとして、

val x = 1
println(x)

このようなのはOKです。

val x = 1
+ 2
println(x)

このケースでは、1の後ろの改行で、行が終わるので宣言の終わりだと解釈するため、構文解析に失敗しますが

val x = 1 +
2
println(x)

のケースでは、1 +を読んだ段階で、これは行継続を意図してるっぽいと判断して、改行は意味がないものとして扱います。

cleanup式

色々な式について、その式が評価後に必ず実行されるコード(ただし、式の結果値は捨てられる)をくっつけることができます。

mutable i = 0
while(i < 10) {
  i = i + 1
} cleanup {
  println(i) // 10 is printed
}

後始末構文をもっと軽量にしてみたらこんな感じかなという割とどうでもいい実験です。

Java FFI

普通に、ScalaとかKotlinとかっぽい感じでJavaのメソッドが呼べます。

val newList = new java.util.ArrayList
foreach(a in [1, 2, 3, 4, 5]) {
  newList.add((a :> Int) * 2)
}
newList

ここで、:>は型キャスト式です。昔の時点で必要だったのでそのままコピペしてみたのですが、今のバージョンでは既に要らない気がします。

こんな感じで、今のところ、構文的な部分以外は何も特別ではないのですが、今後は言語機能上の実験も色々やっていきたいなと思うところです。今後の方向性として、structural type systemをまず入れる予定で、それに、open classを加えて、メソッド拡張を含めた場合にも型が推論されるような感じにするのがまずあります。

なお、構文はかなりScalaの影響を受けています(やっぱり今の自分にとって書きやすい構文の方に寄せたくなる)。

型クラスの真の力を見せる

昨日、

kmizu.hatenablog.com

という記事を書いたわけだが、その後、今日、型クラスに関する議論が一部で(?)盛り上がっているようだ。それは型クラスじゃなくても実現できるのでは、いや、やっぱりインタフェースのようなものと思っていいのでは、などなど。

今回の記事では、型クラスじゃないと実現が著しく困難であると思われる 使い方について書くことにする。

まず、前の記事では、Orderingの使い方を通して、型クラスの単純な使い方について説明したのであった。単純なオブジェクトの場合はそれでもいいが、より複雑なオブジェクトをOrderingを使ってソートしたい場合、前回の記事のようなやり方だけでは難しいことがある。

一例として、(A, B)というタプル型、つまり、A型の要素とB型の要素からなるペアを比較して、ソートしたいという要求を考える(実際には、標準ライブラリでタプル型の比較が提供されてしまっているので、新しい型MTuple[A, B]について考える)。このとき、タプル型同士を比較するOrderingを提供する段階では、ABも何が来るか全く不明なので、一見、そのままではOrderingを提供できないように見える。しかし、実は型クラスでは一般にそれができるのである、ということを示そう。

最初の、しかし、うまく動かないバージョンを以下に示す:

case class MTuple[A, B](_1: A, _2: B)
implicit def tupleOrdering[A, B]: Ordering[MTuple[A, B]] = new Ordering[MTuple(A, B)] {
  override def compare(x: MTuple[A, B], y: MTuple[A, B]): Int = {
    ???
  }
}

前の記事ではimplicit objectであったのが、implicit defになっているが、これはobjectジェネリックになれないため、仕方なく(?)そうなっているだけあり、本題とは関係ないので気にしないで欲しい。

???の部分を埋めて実装を完成させたいのだが、問題は、ABが何者であるかわからないため、比較を実装するのが無理である点だ。このcompareを実装するためには、Ordering[A]Ordering[B]の二つのインスタンスが必要で、しかも、今、私はオブジェクトを暗黙に渡して欲しいのだから、これらを明示的に与えるのは論外だ。では、どうすればいいのか?

回答を先に示す:

import scala.math.Ordering
case class MTuple[A, B](_1: A, _2: B)
implicit def tupleOrdering[A, B](implicit a: Ordering[A], b: Ordering[B]): Ordering[MTuple[A, B]] = new Ordering[MTuple[A, B]] {
  override def compare(x: MTuple[A, B], y: MTuple[A, B]): Int = {
    val MTuple(x1, x2) = x
    val MTuple(y1, y2) = y
    val r1 = a.compare(x1, y1)
    if(r1 < 0) {
      -1
    } else if(r1 > 0){
      1
    } else {
      b.compare(x2, y2)
    }
  }
}

利用例は以下のようになる:

List(MTuple(1, 2), MTuple(4, 3)).sorted  // => List(MTuple(1, 2), MTuple(4, 3))
List(MTuple(4, 3), MTuple(1, 2)).sorted // => List(MTuple(1, 2), MTuple(4, 3))
List(MTuple(new Object, new Object), MTuple(new Object, new Object)).sorted // => error: No implicit Ordering defined for MTuple[Object,Object].

最後の例は、MTupleの構成要素であるObjectに対して、Orderingが定義されていないので、したがって、MTuple[Object, Object]インスタンスも見つけられないということを意味している。

ある型クラスが別の型クラスに依存しているようなパターンといえる。このようなパターンは、単純なStrategyを明示的に渡すパターンではそのまま模倣しづらい(あえていうと、Strategyがネストしたオブジェクトを渡せば可能だがとても面倒だ)。

このような、型クラスが別の型クラスに依存するようなパターンは、おそらく、たとえば、open classのようなものでは実現が難しいし、通常のインタフェースでも実現が難しいであろう。

このとき、Ordering[MTuple[A, B]]の結果が、ユーザが実装をみないでも予想できるくらい十分にわかりやすいものになっているようにする必要がある点には注意されたい。

今回は、タプルの第一要素を先に比較して、それで順序が決まる場合はそれに従った順序に、それで決まらない場合(第一要素が同じである場合)、第二要素の比較を行うという形の辞書順比較なので、十分わかりやすいと言えるだろう。

上記の実装の意味については、また別の記事で解説したい。今回は、型クラスの本当のパワー(というとHaskellerの方に怒られそうではあるが、型クラス的なものでなくては実装が面倒なパターン)を見せるのが主な目的であるので。