kmizuの日記

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

Scala関西Summit 2017に参加してきました！

実は今年が初参加なのですが、応募した発表、「プレースホルダ構文完全解説」が選考を通過したので、大阪まで行ってきました。

前日に、会社まで泊まりのための着替えなどを持っていき、会社が終わったら直行で新幹線で東京へ。@kawachi さんたちが手配してくださった、airbnbの宿に泊まりました。着いたのが22時過ぎで、集合写真

に載れなかったのがちょっぴり残念でした。

会場は、天満駅近くの天満研修センターというところで、なんと今年は４トラック同時進行！

私は全体的に疲れ気味で、控室で休んでいた時間が結構あったため、全部は聴けていないのですが、いくつか印象に残った点について。

  • エスカレーターで右に立つ

イベントとは関係ないのですが、新大阪駅から宿泊施設に向かっているとき、いつもの習慣で左側に立っていると、皆右側に立っていて、あれ…？と思いました。

  • エフ・コードの技術顧問就任について

会場でお会いした方にこの件について、色々たずねられました。おめでとうございます、と言っていただけることが多かったですが、自分としては、これから自分がエフ・コードさんに価値を提供していくことができるか、考えていかなければなあと思うところです。

  • null消しゴム

エフ・コードさんのブースで配布されていたやつで、

こういうものです。事前に、がくぞさん、麻植さんらと話し合ったときに、何がインパクトがあるかということで、この案が最終的に採用されたのですが、無事、当日に間に合ったので良かったです。インパクトもあったようです。

最初からいきなり関数型プログラミングばりばりでいくのではなく、初心者がもっととっつきやすいように、（害のない範囲で）手続き型プログラミングも認めていこうよ、という話だと理解しました。特に、メソッドローカルに閉じている限り、var/whileやミュータブルコレクションを使って構わないという主張には、私も賛成するところです。最近のScala界隈は、too functionalな面があると感じていて、自分も、こういう取り組みをしていけたらと思わせられる良い発表でした。

フィボナッチサービスという例題を使って、jvisualvmでボトルネックを発見する方法を解説した発表です。jvisualvmについては既に使ったことがあり、新しみはあまりなかったのですが、発表のわかりやすさという点で学ぶべきところが多かったです。

scalafmtを使ったことは（ほぼ）なかったので、そのアグレッシヴさ、というか、設定項目の多さに仰天しました。高橋さんとしては、どっちも十分使えるので好みで良いということでしたが、個人的には、sbtでコンパイル時に自動フォーマットできるscalariformの方が好みかなというところです。また、Scala Style Guideについて

  • 標準化されていない
  • スタイルが未定義な部分がある
  • 矛盾した部分がある

という指摘があり、なるほどと思いました。scalariformは手書きのパーザを使っているらしいという情報を得たので、ちょっとパーザみてみようかと思いました（構文解析屋としての興味）。

なお、私は、最初に書いたように「プレースホルダ構文完全解説」という発表を行いました。発表を聴きに来てくださった方はだいたい30～40名くら居たのですが、正直、うまく説明できたのかあまり自信がありません。元々、テーマ的にマニアックである上に、理解するにはコンパイラやパーザの知識が必要になる、という点でかなり聴く人を選ぶものだったので、全員に伝わるように発表するのが難しかったのかもしれません。一部の方には面白かったと言っていただけたのは嬉しかったです。

新幹線であらかじめ帰りの指定席を予約していたこともあり、懇親会には参加せずに離脱。後ほどTwitterを眺めてみると懇親会の楽しそうな様子が伝わってきて、ちょっぴり後悔しました。

主催者の、Scala関西ユーザーグループの方々、楽しい一日でした。ありがとうございました！来年は、もうちょっと万人受けするネタを考えようと思っています…

プレースホルダ構文と文字列補間を組み合わせた時の挙動についての考察

Scala

久しぶりの日記の更新です。今回のテーマは、Scalaにおける、Placeholder syntax for anonymous function（以後、プレースホルダ構文）とString Interpolation（文字列補間）を組み合わせた時にどのような挙動であるべきか、また、現状の挙動が妥当かについて考察する記事です。

きっかけは、本日のきの子さんのツイートでした。

文法上はできるはずだけど、どういうケースなのだろう、と疑問に思ったのですが、吉田さんのツイート

のリンク先をみて、補間文字列の中に現れるプレースホルダが、その外側と結びつかないことが問題ということのようでした。

ただ、リンク先では

It can probably be made to work; pull requests welcome.

と軽く言っちゃってますが、これ、プレースホルダ構文について以前詳細に調べたことのある身としては、なんか許しちゃ駄目なケースではないかと瞬間的に思いました。ただ、文字列補間の詳細な仕様を参照したことがなく、自信があったわけではないので、両方の仕様を突き合わせたり、サンプルの入力を考えた時に、プレースホルダが補間文字列の外側と結びついて大丈夫なのか考えてみることにしました。

まず、プレースホルダ構文についてですが、Scala Language Specificationの6.23.5に仕様が規定されています。ただ、これが意味するところは結構ややこしいので、自分が以前書いた解説記事をベースに話を勧めます（当該記事も、仕様書を元に説明したものなので、改めて解説する手間をはしょっただけです）。

文字列補間については、SIP-11 - String Interpolationに仕様が定義されているので、これを元にして考察します。

解説記事にも書いているのですが、プレースホルダ構文は構文解析時に作用する要素であるという点が非常に特異な代物で、文法定義上のカテゴリという概念を参照して定義されています。一方、文字列補間も構文解析時に主に処理が行われるもので、両者を組み合わせた場合のことをテキトーに考えると、おかしな結果になることは割とすぐに想像がつきます。

たとえば、GitHubのIssueに上がっている例では、

val f : Int => String = s"The there are ${_} apples in the bowl"

が

val f: Int => String = n => s"The there are $n apples in the bowl"

と解釈されて欲しい、という事が書いてあります。ぱっと見で、文字列リテラルっぽいものの型が関数の型になるという結果で、かなり直観的ではないのですが、さて、これは許されるべきなのでしょうか。まあ、想像だけで考えても仕方ないので、String Interpolationの方の仕様を見てみます。

関係する部分を抜粋すると、

A processed string literal of either of the forms

 id ”text0${ expr1 }text1 … ${ exprn }textn”
    id ”””text0${ expr1 }text1 … ${ exprn }textn”””

where each texti is a possibly empty string not containing dollar sign escapes, is equivalent to:

StringContext(”””text0”””, …, ”””textn”””).id(expr1, …, exprn)

と書かれています。これは、processed string literal（fとかsとかがプレフィックスについた文字列リテラルのこと。補間文字列リテラルと呼びます）が、StringContextオブジェクトのメソッド呼び出しに変換され、式の部分は引数として渡されるということを言っています。このような仕組みになっているのは、文字列補間をユーザ定義可能にするためなのですが、それはさておき、この説明を読む限り、補間文字列リテラルの型は、プレフィックスと同じ名前のメソッド呼び出しによって決定されるのであって、中にプレースホルダがあったら、 Int => String に型が変わるというのは、現状の文字列補間の仕様と衝突します。要求を通すなら、少なくとも、現状の仕様を、StringContext を使わない形に解釈され得るという風に更新する必要がありそうです。

じゃあ、文字列補間の仕様を更新することを前提にするなら、OKか。駄目とは言い切れないものの、結構微妙なところがあります。まず、補間文字列の構文カテゴリは SimpleExpr1 だと定められており、補間文字列中の ${...} は BlockExpr であると定められています。プレースホルダ構文の仕様としては、構文カテゴリ Expr が _ を含み得るという形で定義されており、かつ、SimpleExpr1 も BlockExpr も Expr に昇格可能なので、補間文字列中の式が外側の式と結びつくのは、構文カテゴリの点で言えば、既存の仕様と矛盾していないとは言えそうです。

ただ、矛盾していないからいいかというと…次の例を考えてみます。

List("A", "B", "C").map(s"alphabet = ${_}")

これが、

List("A", "B", "C").map(a => StringContext("alphabet = ", "").s(a))

と変換されて欲しいとします（し、実際の要求としても、こういうのがありそうです）。この場合、プレースホルダ構文が処理されて、その結果として、補間文字列の式が a => StringContext(...).s(a) になる、という解釈になるでしょう。

別の例として、

(List(1, 2), List(3, 4)).zipped.map(s"${_ + _}")

がどう変換されるべきかを考えてみます。プレースホルダ構文の仕様の方はいじらないなら、これは

(List(1, 2), List(3, 4)).zipped.map((x, y) => StringContext("", "").s(x + y))

に変換されるべきです…ほんとに？実は、ちょっとごまかしが入っていて、文字列補間による式変形と、プレースホルダ構文による式変形がなんとなくうまくはまったかのように書いていますが、十分に挙動を説明しきれていません。

正確に仕様を書こうとするなら、文字列補間による式変形の順番とプレースホルダ構文による式変形の順番を規定する必要があります。しかし、困ったことに、文字列補間は式の（構文カテゴリ上の）形を変えてしまうので、どちらを先に適用するかで最終結果が変わる可能性があります。

上記の例で言えば、文字列補間→プレースホルダ構文という順番で処理されると考えるのなら、

(List(1, 2), List(3, 4)).zipped.map(StringContext("", "").s(_ + _))

その後に

(List(1, 2), List(3, 4)).zipped.map(StringContext("", "").s((x, y) => x + y))

となります。逆の順番なら、

(List(1, 2), List(3, 4)).zipped.map((x, y) => s"${x + y}")

その後に

(List(1, 2), List(3, 4)).zipped.map((x, y) => StringContext("", "").s(x + y))

となります。このケースでは、後者、つまり、プレースホルダ構文→文字列補間、の順番に変形してくれた方が嬉しいでしょう。しかし、順番を考えないとうまく動くかどうか判断できないのは仕様としてはあんまりだと思うのです。

プレースホルダ構文が補間文字列リテラルの外に影響を与えない、という現状の仕様であれば、（おそらく）処理順序による影響は出ません。自分としては、構文上の仕様に（プレースホルダ構文だけでもめんどうなのに）これ以上ややこしいものを放り込んでほしくないので、これはちょっと…と思うところです。

長くなりましたが、結論としては、

  • 現状のプレースホルダ構文と文字列補間の仕様の整合性は取れている。要求に従うと現状の仕様に不整合が出る
    • 仕様変更が必要
  • プレースホルダ構文が補間文字列リテラルの外側に影響を与える仕様変更を行うには、両者の処理順序を明記する必要がある
    • 複雑であり、わかりにくい挙動
  • 結論としては、現状の仕様のままが妥当そう

といったところになります。

結構ややこしい問題で、自分の考察になんか穴がある可能性はあるので、もしあれば指摘していただければと思います。

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 )が引数に与えられたとき、それぞれが x と y というメンバがあると仮定して、PlayerとEnemyの間の距離を計算する、というものです。

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

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

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

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

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

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

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

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

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

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

構文解析ハンズオン - connpass

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

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

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

反省点については

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

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

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

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

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

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

Understanding Scala - connpass

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

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

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

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

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

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

タイトルだけだと、わかってる人にしかわからないので、背景を説明します。サンプルコードは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さんといった方々も登壇されるようです。