ブラウザで動くラムダ計算器を作った（Scala で）

最近 Types and Programming Languages を読んでいて、はじめは我慢していたものの、やはりラムダ式の簡約をコンピュータで確認したい気持ちが高まってきたので、ブラウザで動くものを書いてみた。この本には OCaml による実装の章がときどき挟まれるので、演習の一環ともいえる。

Lambda Calculator

"(λx.λy.x y)(λz.z)" といったラムダ式を入力して送信すると（λ は \ で代用可能）、解析された項が出力される。その後1ステップずつ簡約して、項が評価されていく過程を眺められる。評価戦略は TAPL にしたがって call-by-value と call-by-name を提供してるつもりです。毎回どのサブ項が評価されたのかがハイライトされるので、実用的。

同じ項を何度も入力するのが辛いので文字列マクロを導入してあり、"$omega" などと書くと展開した上で解析される。グローバル変数のような概念がないので、文字列置換です。いくつかのよく使う（？）式を定義しておいた。

パーマリンクもあるので、ラムダ式を SNS で共有することもできる。

http://motemen.github.io/lambda-calculator/untyped.html?s=call-by-value#$omega

実装は JavaScript……ではなく主に Scala で行い、Scala.js で JS に変換した。ハマると解決できなそうなので動かなかったら諦めようと思っていたんだけど、普通に動いてしまったので感動です。とはいえいくつか工夫しなくてはならなかった点があるのでここに記す。

Scala.js で parser-combinators を使う

id:xuwei さんのアドバイスにしたがって、bintray にアップロードされているものを使うよう変更できました。あざーす！

Scala.js には Scala のパーザコンビネータは含まれていない（JS にコンパイルできない）が、2.11 になって切り出されたもののフォークが存在するので、これを利用する。（参考）

今のところ公開された場所に登録はされていないらしいので、依存プロジェクトとして sbt のビルド定義に含んでやる。この時、サブプロジェクトの plugins.sbt は読み込まれないのでルートプロジェクトのプラグインとして指定する必要がある。コアプロジェクトをこれに依存させる。（build.sbt）

JS として切り出すプロジェクトを分ける

はじめ Scala で実装してテストも Scala で書いてたんだけど、このプロジェクトをそのまま Scala.js のプロジェクトとすると sbt test の挙動も変わってしまった。これは意図的なもので 、Scala がコンパイルするものと Scala.js がコンパイルするものとの間に互換性がないためらしい（JVM のバイトコードを　JS に変換してるわけではないってことかな）。なので JS 側へのインターフェースだけ別プロジェクトに切り出し、コア部分に依存させるということにする。

ちなみに Scala.js でクライアントサイドの JS を全て書くこともできるんだけど、そこまでの意欲はないのでコア部分のインターフェースを書いたら、あとは生の JS でやることにした。

結果、こんな感じの構成になった。

. [Scala, depends modules/scala-parser-combinators]
|-- js [Scala.js, depends root]
|-- modules
    `-- scala-parser-combinators

gulp でビルドしたい

sbt が律速（重い）なのでビルドは sbt に一元化したくなるけれど、とにかく重いしこの前段階でもう飽き飽きしたので、gulp から sbt を呼ぶようにした。まあ必要なのはほぼ sbt ~fastOptJS だけなので spawn するだけ。Scala.js はコンパイル時、生成先のファイルにどんどん追記して完成させるらしいのだけど、これが gulp.watch と相性悪い。内部ではファイルシステムのイベントに対して debounce と呼んでる遅延処理がデフォルト 500ms かかっているんだけど、どちらかというと throttle と呼ぶべき代物で（underscore のネーミングを拝借すると）、困るのは、最後の書きこみが行われたあとにイベントが発生しないことがある。そこでコールバックのほうで 1s ほど _.debounce してやることにした。

そのほか

本体の話全然書いてないけどライブラリ使ったらパーザもだいぶ楽できた。愚直に書いたら無限に再帰しだして、久しぶりに左再帰とかいう言葉を思い出した。項を簡約するときに木のどの位置が簡約されたのか示すあたりのコードがあんまり綺麗ではない。

結局のところ評価して得られたこの値って何なの、というのがどうしても分からないことがあるので、ラムダ式を JS の関数に評価する API も作ってある。チャーチ数の確認とかにご利用ください。

> λ('λs.λz.s (s z)')
function (s) { return (function (z) { return s(s(z)) }) }
> λ('λs.λz.s (s z)')(function (x) { return x+1 })(0)
2

最後に書くようなことではないけど、実装が合ってるのかどうかイマイチ自信がない。業界で標準的なテストケース集とかあったら教えてほしいです。プルリク待ってます。

型システム入門 −プログラミング言語と型の理論−

Scalaスケーラブルプログラミング第2版

minimatch（node.js で path match するライブラリ）のチートシートを作った

minimatch っていうのは Grunt や gulp.js その他あちこちで（npm もらしい）使われてるグロブマッチライブラリです。最近よく gulp を使ってるんだけど、毎回 gulp.src() の書き方で迷ってしまう。調べた結果 minimatch に行き当たったんだけど各種 glob 実装のドキュメント読んで把握しろ、という感じでよく分からなかったので早見表を作った次第です。

https://github.com/motemen/minimatch-cheat-sheet

確認用にテストを書いていて、そのテストケースからドキュメントを生成してるので間違いはないはずです。説明が間違ってる、この例も乗せた方が見やすいだろ、とかあればプルリクください。

折角なので日本語版を書いておきますね。

基本

• * はパスセパレータを含まない任意の文字列にマッチ
• ** はパスセパレータを含む任意の文字列にマッチ
• ? はパスセパレータでない任意の1文字にマッチ

パターン	マッチする	マッチしない
xxx.*	xxx.yyy, xxx.y.z	abcxxx.yyy, xxx.y/z
xxx/*/yyy	xxx/abc/yyy	xxx/yyy, xxx/abc/def/yyy, xxx/.abc/yyy
xxx/**/yyy	xxx/abc/yyy, xxx/yyy, xxx/abc/def/yyy	xxx/.abc/yyy
xxx/**yyy	xxx/yyy	xxx/abc/yyy, xxx/abc/def/yyy, xxx/.abc/yyy
x?y	xAy	xy, xABy, x/y

ブレース

• {foo,bar} は "foo" と "bar" に展開
• {1..3} は "1", "2", "3" に展開

パターン	マッチする	マッチしない
{foo,bar}	foo, bar	baz
{x,y/*}/z	x/z, y/a/z	y/z
foo{1..3}	foo1, foo2, foo3	foo, foo0

否定

• ! で始まるパターンは真偽を逆転させる

パターン	マッチする	マッチしない
!abc	a, xyz	abc

コメント

• # で始まるパターンはコメントとみなされて何にもマッチしない
• \# とすることでエスケープできる

パターン	マッチする	マッチしない
#abc		abc, #abc
\#abc	#abc	abc

extglob

• +(pattern) は pattern の1回以上の繰り返し (/(pattern)+/)
• *(pattern) は pattern の0回以上の繰り返し (/(pattern)*/)
• ?(pattern) は pattern の0回または1回の出現 (/(pattern)?/)
• @(pattern) は pattern そのもの (/(pattern)/)
• !(pattern) は pattern にマッチしないというパターン (/(?!pattern)/)
• カッコ内のパターンは | で連結可能 (/(foo|bar)/)

パターン	マッチする	マッチしない
a+(xy)	axy, axyxy	a
a*(xy)	a, axy, axyxy
a@(xy)	axy	a, axyxy
a!(xy)	ax	axy, axyz
a+(x|y*z)	axx, ayzxyzxx, axyAAAz	axy, a

デザイン4+1の基本ルール: 『The Non-Designers Design Book』を読んだ

なんかで Kindle の洋書が安かったときに何となく買っていた『The Non-Designers Design Book』を読み終えた。素人のための……というよりは新人デザイナーのための本のようなのだけど、エンジニアの自分が読んでも面白かったので書いとく。日本語版もある。

4つのルール

曰わく、デザインには基本的な4つのルールがある。それぞれの頭文字を取ると "CRAP" ……となるのだけれど、これは上品な単語ではないのでそう示唆されるだけではっきりとは書かれない。ともかく、各々に対応する原則は以下のとおり。

• Contrast（コントラスト）
• Repetition（反復）
• Alignment（整列）
• Proximity（近接）

これらにどういう意味があり、どう活用すべきであるか。本で紹介される順に書いていく。

Proximity

意味的に関連する要素どうしを近くに置いてグルーピングする。逆に直接関係のない要素どうしは離して配置する。そうすることで、ページ内の情報を組織化できる。

Alignment

ページ上の要素どうしを視覚的に関連づける。たとえ二つの要素が離れていても、同じように整列されていればそれらは関連しているように感じられる。安易に中央揃えしない！　右でも左でも、一方に要素を揃えることでより強く関連づけられる。組織化と統一が目的。

Repetition

色やフォントなどの視覚的な要素を繰り返し、一貫性を持たせる。これは1ページ内のことに限らなくて、例えば数ページに渡る文書でも、見出しや罫線といった部分の体裁を同じに整える。ここでは統一と視覚的に関心を持たせることが目的。

Contrast

2つの要素の違いを際立たせる。要素どうしがなんか違うという状況では単に間違えてるだけに見えてしまう。ここで違いというのは色とかフォントとか文字サイズだけじゃなくて、横長の罫線に対して縦長のカラムを置くとか、そういうことでもいいらしい。目的はページに関心を持たせること。

至上のルール

以上4つの法則に加えて、何度も何度も繰り返されるいちばん基本的なルールは、"Don't be a wimp"。怖気付くな！　コントラストを作るなら中途半端じゃなく思いっきりやる、空白を怖がらない。等々。ホントに何十回と言われるのでよっぽど大事なことなんだろう。

タイプについて

それからタイプ（書体？）についての話も面白かった。CSS だけからなるこれまでの経験で、フォントの違いには serif、sans-serif と等幅とあと装飾的なの、くらいしか区別できていなかったけれど、本当はもっといろいろある。特にこれまで serif だと認識していた中にも Oldstyle, Modern, Slab serif なんてカテゴリがあるんだそうだ。この章を読み始めたときはそんなの気にするのアルファベットを日常的に使ってる人間だけで日本語ユーザの自分には関係ないだろう、と斜に構えていたのだけど、読んでみて、実際に試してみると、確かに……と思えてしまったので面白かった。これらの違いを理解して、うまくコントラストを作ってやることが大事。

まとめ

4つのルールなどといっても、聞いてみればそりゃそうだろうという気もするかもしれない（自分はちょっとした）。けど本当に大事なのは、こういったルールに名前をつけて、自覚的になることだ。自分がデザインしたページに違和感があるときに、その原因は何なのか名前を上げることができるようになることが重要である。そうすれば、何となく今ひとつに感じてしまうデザインを確実によりよくできるはずだ。……とまあ実際に実現可能かどうかは別として、これまでは結局センスの産物なんだろうと思っていたデザインを、新たな視点で見られるようになったと思う。

Kindle 版の場合はカラーで（タブレットやスマートフォンで）読むのがオススメ。

The Non-Designer's Design Book (3rd Edition) (Non Designer's Design Book)

ノンデザイナーズ・デザインブック [フルカラー新装増補版]

4つの原則の日本語訳はこのスライドを参考にした。とても分かりやすいし、本の内容がかなり補強されると思う。