『Write Great Code: Volume I: Understanding the Machine』を読んだ

『Write Great Code: Volume I: Understanding the Machine』を読んだ。副題に注目。予想していた以上にマシンの話だった。

自分たちが書くあらゆるプログラムは、それが現実界で動いている以上、必ず物理的な実体を持つコンピュータの上で動いている。こう動いてほしいと願って書いたコードがどんな風に解釈され、表現され、実行されるかということを、この本ではごくごくマシンの側から描いてくれる。C言語が一種の高級言語という範疇に収められているところから、その立ち位置を想像されたし。

今自分が書き、走らせているプログラムは様々な抽象の上に構築されているのだけれど、それらのあらゆる抽象化を取り去って、数値や文字列といった、プログラムが扱うデータはどんな風にメモリ上に配置されるのか。CPU への命令はどんな風にビット列として表されるのか、それを CPU はどんな風に処理するのか。メモリやディスクへの IO はどんな風に行われ、どんな風に高速化が試みられているのか。一台のマシンの中ではどんな機器が協調して働いているのか。などなど、もちろん知らなくてもプログラムを動かすことはできるが、知っていれば効率のよいコードを書けるだろう知識を広く扱っている。

プログラミングに欠かせないプロセスとして抽象化された概念が、実のところどのように現実的・物理的に実現されるか、垣間見ることができたのはとてもおもしろかった。特に CPU の働き、キャッシュの仕組みを見ると、ものすごく複雑な仕組みの上で自分のプログラムが動いていることを知って、感謝の念が湧いてくる。マシンの歓声を聞くことも、もしかしたらできるのかもしれないという気がしてくる。

この本では、こういったマシンの働きを知ることがグレートなコードを書くことにつながると言っている。実際のところ、現在のかなり抽象度の高い環境でこの知識たちが直接活用できるとは思えないけれど、例えば OS の働きを知るのにこういった土台のことを知っていることは重要だろう。出版年が古く（2004 年）、扱われるトピックも具体的な名前は古いところが時おり見られるが、本質的な部分はまだまだ通用するはず。

最近日本語訳も Kindle化 されたらしいです。洋書はこのボリュームで 2000 円しなくて安い。

Write Great Code: Volume I: Understanding the Machine: 1

Write Great Code〈Vol.1〉ハードウェアを知り、ソフトウェアを書く

この本の次によむならこの本でもよく挙げられているパタヘネか Linux カーネル（再読）かネットワーク低レイヤの本かな（どんな本がいいのか知らない）。

コンピュータの構成と設計 第4版 上 (Computer Organization and Design: The Hardware/Software Interface, Fourth Edition)

Linuxカーネル2.6解読室

ブラウザで動くラムダ計算器を作った（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