明日(6/11(土))に、こういう勉強会があるのですが、
きょんさんから、出演依頼があったのと、これからあちこちでなんか発表したいなーという気分があったので発表することにしました。
タイトルは「私のプログラミング言語の学び方」です。ざっくり言うと、既存の、プログラミング言語の学び方に違和感があるので、その辺を言語化してみた、というような話です。だいたい、プログラミング言語の学び方というと
という、どうも両極端アプローチがやたら目につく気がするんですが、そういうのって、１言語習得辺りの効率が悪いと思うので、もっと統一的な理解をするのがよいのでは、というやや強まった発表（の予定）です。
らへんの話をもうちょいふくらました感じというか。
というわけで、明日はよろしくおねがいします。
タイトルは、斜め読み論文紹介ですが、
↑の辺の企画の亜種だと思ってください。気が向いたらときどき書いていこうと思います。第一回は、From APIs to Languages: Generalising Method Namesです*1。
唐突ですが、Smalltalkという言語があります。オブジェクト指向を発明したとかいう言語ですが（テキトーな言い方だ…）ここでは全く関係がないのでおいておきます。Smalltalkの系列の言語は、メソッド名の構成に関してやや特殊なところがあります。それは、メソッド名をいくつかの断片に分けて記述するところです。
たとえば、辞書に値を突っ込むには、次のようにします：
kmizu := Dictionary new. kmizu at:'Age' put:'32'. kmizu at:'Sex' put:'Male'. kmizu at:'Name' put:'Kota Mizushima'
ここで、at:とput:で合わせて一つのメソッド名を構成しているのが、Smalltalk系列（Objective-Cも含む）のメソッドの特異なところです。これは、いわゆる名前付き引数とも違っていて、通常、メソッドの断片の順序は変更できません（もし最近のSmalltallkだとできるとかあれば教えてください）。
ここまでが準備です。さて、このように、メソッドをメソッド名の断片に分けられるのなら、その断片について
といった規則を使って、断片同士くっつけられるはず！、というのがこの論文のポイントです。メソッド名の断片を基本単位とした、正規表現のようなものが書けるようになった、という感じでしょうか。このような機構を指して、著者らは「Generalized Method Names」と呼んでいます。以下は、論文中に出てくるサンプルコードです。
method use(x) +addRatio(y1, y2) ?multiplyBy(z) {
var value := x
for (y1) and (y2) do { a, b −>
value := value + a / b
}
for (z) do { v −>
return value * v
}
return value
}
use(0) addRatio(1, 2) addRatio(2, 4)
multiplyBy(6) // −> 6
use(1) addRatio(2, 3)
multiplyBy(2) // −> 3 1/3
useで初期値を設定して、addRatioで有理数を足しこんで、multiplyByで掛ける、という具合です。ポイントは、addRatioにはprefixとして+が付いており、useに続いて、addRatioを1回以上繰り返して呼び出せること、それに続いて、multiplyByを0回または1回呼び出せることです。
このGeneralized Method Namesを使うことで、
といったものをすべて統一的な機構で扱えるのです（というのが著者らの主張です）。
さらに、これらの、メソッドの断片について、部分型（Subtype）関係が定義されているのが面白いところです。たとえば、
a() *(b() | c()) <: a() *b() *c()
というサブタイプ関係が成り立つそうです。結構ややこしいので詳細は論文を読んでもらうことにします（というか、自分もサブタイプ関係のところはちゃんと読んでいない）。
ともあれ、メソッド名の断片を基本単位としてなんかするというのは、結構昔から聞いたことがあるテーマではありますが、結構綺麗に一般化できるのだなーというのが素直な感想です。
あと、ちょっと面白いのは、メソッド断片に対するマッチングはgreedyに行われるので、たとえば、
method a(x) *b(y) b(z) { ... }
のような、決してマッチすることのない（二つ目のb(y)で全部`bの出現を食べてしまうため）メソッド定義もできちゃうところですね。
テストDSLの例みると、
method scenario(desc)
?(Given(context) *And(contexts))
When(event)
Then(expr) ShouldBe(val)
*(And(exprs) ShouldBe(vals)) {...}
method feature(name)
?background(initialisation)
+(scenario(desc)
?(Given(context) *And(contexts))
When(event)
Then(expr) ShouldBe(val)
*(And(exprs) ShouldBe(vals)))
のような、超メソッド解決がややこしそうな例がありますが、これはまあ柔軟性の代償というところでしょうか。というわけで、なんとなく数日前に読んだ論文を紹介してみました。他の方々もなんかおもしろんぶんがあれば紹介してもらえると嬉しいかもです。
*1:Proceedings of the 11th Symposium on Dynamic Languages 2015。自分はそれほど詳しいわけではないですが、動的型付き言語関係の国際会議のようです
Scalaには中置パターン（infix pattern）と呼ばれる機能があります。これは単純にいうと、
case class ~[A, B](a: A, b: B)
のようにして定義したケースクラスに対して*1、
scala> val ab = new ~(1, "FOO") ab: ~[Int,String] = ~(1,FOO) scala> val a ~ b = ab a: Int = 1 b: String = FOO
このようにパターン名を中置（infix）にして書くことができる機能です。この機能、一見使い道が少なそうですが、実は皆さん、日頃からよく使われています。
まず、
list match {
case x::y::xs =>
...
}
のように、リストを::を使ったパターンマッチで分解することはよくあると思いますが、これは、::という中置パターンがあればこそできる書き方です。これができないと、
list match {
case ::(x, ::(y, xs)) =>
}
のように、いちいちネストした形式でパターンを書く必要があり、これは書きやすくも読みやすくもありません。
"(" ~ expression ~ ")" ^^ { case _ ~ e ~ _ => ... }
のようにして、マッチした式の値のうち一部だけを取り出しますが、これも~を中置パターンとして使えているからこそです。これがないと、
"(" ~ expression ~ ")" ^^ { case ~(~(_, e), _) => ... }
のようにネストした形でパターンを記述する必要があり、とてもuglyです。~でつながれる要素数がさらに増えるともはや書き下すことが難しくすらなります。
というわけで、中置パターンは便利です、という話でした。
*1:実際には、unapplyが定義されていればいいわけですが、説明の簡略化のためその辺はばっさり略
昨日、Amazon Prime Nowの存在を知り、送料を余計に支払えば1時間以内、無料枠でも2時間以内に注文した品を届けてくれるサービスであることを知った（該当エリアに住んでいることが条件。また、専用のPrime Nowアプリで注文する必要がある）。注文できる品物は、Amazon.co.jpで買えるものからすると限定されているが、この素早さは魅力的だ。というわけで、早速使ってみた。送料を余計に支払って1時間以内に届けてくれるやつで。
とにかく、1時間以内にきっちりと配達してくれた。凄いサービスだ。
タイトルの通りです。JavaScriptに関しては多少は知っていますが、知識が全然アップデートされていないので、この機会に再入門してみることにしました。以下はpackage.jsonなんかBabel関連で試行錯誤したので、結構変な構成になっているかも。
{ "name": "es_copmbinator", "version": "0.0.1", "description": "A ES2015 Parser Combinator Library", "main": "index.js", "scripts": { "test": "ava -v" }, "repository": { "type": "git", "url": "git+https://github.com/kmizu/es_copmbinator.git" }, "keywords": [ "parser" ], "author": "Kota Mizushima", "license": "MIT", "bugs": { "url": "https://github.com/kmizu/es_copmbinator/issues" }, "homepage": "https://github.com/kmizu/es_copmbinator#readme", "devDependencies": { "ava": "^0.15.1", "babel-preset-es2015": "^6.9.0", "babelify": "^7.3.0" } }
以下、遭遇した問題やES2015の機能について。
無名関数の簡略記法（というだけではないが）。本体が式である場合、returnが省略できるらしい。というか、ブロックは式ではないというのが正しいか。なんとも中途半端な仕様だが、これまでのJavaScriptの仕様と一貫性を保つためには仕方ないのか。
const add = (x, y) =>(x, y) const printAdd = (x, y) => { util.log(x); util.log(y); return x + y; // return必須 };
割と普通にクラスを定義できる。暗黙のsuper();呼び出しがないことを知らなかった。もうちょっとわかりやすいエラーメッセージを出してほしい。ただ、メソッドの定義が、メソッド名(引数...) { ... }だけで書けるのは便利。
class ParseResult { constructor(next) { this.next = next; } } class ParseSuccess extends ParseResult { constructor(value, next) { super(next); this.value = value; } isSuccess() { return true; } } class ParseFailure extends ParseResult { constructor(next) { super(next); } isSuccess() { return false; } }
共にブロックスコープ。letは変更可能。constは変更不能。とりあえず、ほとんどconstしか使わなかった。
以下のようなことをしたかった
const combinator = new ParserCombinator; const or = combinator.or; or(new StringParser("FOO"), new StringParser("BAR"));
だが、thisがないと怒られてしまう。これはまあ、それまでのJavaScriptの仕様を考えると納得できるが、構文的にはthisが束縛されていて欲しいので残念。
const true = 1;
とすると怒られるのに、
class Hoge { true() { } } const hoge = new Hoge(); hoge.true();
は怒られない。
に、実際に、「予約語は識別子のみに適用されます。（以下略）」
a.import
a["import"]
a = { import: "test" }
とあって、そういう仕様であることがわかる。
いやまあ、結局、これまでのJavaScriptを考えると仕方無いのだろうけど、
class OrParser extends Parser { constructor(lhs, rhs) { super(); this.lhs = lhs; this.rhs = rhs; } parse(input) { const r1 = this.lhs.parse(input); if(r1.isSuccess()) { return r1; }else{ return this.rhs.parse(input); } } }
は
class OrParser extends Parser { constructor(lhs, rhs) { super(); this.lhs = lhs; this.rhs = rhs; } parse(input) { const r1 = lhs.parse(input); if(r1.isSuccess()) { return r1; }else{ return rhs.parse(input); } } }
と書きたかった。
全体的に、ES2015の言語自体で、今のところそれほどハマったとは感じなかったというか、どっちかというと周辺環境の整備でハマった。
てな感じで生まれたのがこちら。
以前に、このエントリで、新しい言語を覚えるためにはまずパーザコンビネータライブラリを作成すると書いていたが、まさにそのまんまというか。パーザコンビネータは、言語機能を多少は使えないと作れない類のものなので、やはり"Hello, World!"の代わりとして適しているとますます確信する次第です。
ところで、テスト中に書いた、四則演算式のパーザなのですが、もっと冗長になるかと思いきや、
const E = () => A(); const A = () => c.f(() => M()).chainl( ( c.s("+").map((op) => (lhs, rhs) => lhs + rhs) ).or( c.s("-").map((op) => (lhs, rhs) => lhs - rhs) ) ); const M = () => c.f(() => P()).chainl( ( c.s("*").map((op) => (lhs, rhs) => lhs * rhs)).or( c.s("/").map((op) => (lhs, rhs) => lhs / rhs) ) ); const P = () => (c.s("(").cat(c.f(() => E())).cat(c.s(")"))).map((values) => { return values[0][1]; }).or(c.f(() => N())); const N = () => c.r("[0-9]+").map((n) => parseInt(n));
これだけで書けてしまったのが結構意外でした（ちゃんと数値の計算もしてるサンプル）。これは、アロー関数の本体が、式の場合はreturnを省略できるのと、chainlがやはり強力なコンビネータであって、これを実装すると、パーザを実装するのが格段に楽になるということかなと思います。ただ、規則に相当するものが全て関数でラップされている通り、遅延評価されるフィールドとか書けないので、若干不格好です。まあ仕方ない。
とまあこんな感じですが、ES2015は初心者もいいところだし、それ以前のJavaScriptもあまり得意ではないので、ツッコミどころがあるかもしれませんが、そこはツッコんでいただけるとありがたいです。
についての補足的なエントリです。scala-nativeのサンプルプログラムsmallpt.scalaは
__stderrpを使っていますが、Linux系には存在しないので、リンク時にこけてしまいます。
これを修正するには、smallpt.scalaとstdlib.scalaの__stderrpと__stdoutpをそれぞれ、stderrとstdoutに書き換えてやる必要があります。現状、条件コンパイルのような仕組みはサポートされていないのでこれをクロスプラットフォームで動作させる方法がたぶんないのがちと困ったものです（作者本人が作ったIssueには入っているので、そのうち解決されるだろうとは思いますが）。実は手元でunameを使ってOSによって分岐するコードを書いてみようとしたのですが、構造体のメモリレイアウトが微妙に違うのか、unameは呼び出せるものの、返り値に謎の値が入っているという事態になりました（なにか勘違いしているかも）。
Scala Nativeなのかscala-nativeなのか迷ったのですが、今後はリポジトリ名のscala-nativeに統一しようかと思います。さて、タイトルについてですが、そのまんまです。
サンプルコードは以下：
通常のJVM上でのScalaでは、末尾呼び出しが自分自身で（自己末尾再帰）、かつ、その関数（メソッド）がオーバーライドされない場合に限り、末尾呼び出しを除去することができましたが、scala-nativeはそれに限らず、一般の末尾呼び出しも除去（ジャンプに置き換えることができる）という話です。
上記サンプルコードでは、単純にやるとおよそ100000000個分スタックを積む必要がありますが、そのまま関数呼び出しとして実装するとスタックオーバーフローします。事実、最適化オプションを付けないclang（3.7）では同等のコードを実行しようとするとsegmentation faultを起こしました（-O1以上の最適化オプションを付けるとちゃんと実行できました）。
JVM上でのScalaでは末尾呼び出しの除去をやろうと思うと、非常に高いコストを払って自前でトランポリン形式にするくらいしか選択肢がなかったですが、scala-nativeではJVMという制約がないので、その辺の最適化もできるようになった、ということです。
追記： LLVMでは言語非依存の最適化として末尾呼び出しの除去が行えるらしいのでscala-nativeはその機能をそのまま使っているのかもしれませんね。
