言語実装パターンを読んだ

言語実装パターン ―コンパイラ技術によるテキスト処理から言語実装まで

「言語実装」と聞くとコンパイラの本かと思いますが、本書は「言語アプリケーション」を実装するための本です。言語アプリケーションには設定ファイルの読み取り、データの読み取り、コード生成、コード変換器、インタプリタなど、入力ファイルを処理・解析したり、変換したりするアプリケーションが含まれます。

このようなアプリケーションはだいたい同じような構成になり、以下のような要素を組み合わせて実装することになりますが、各要素の実装パターンが数種類紹介されていて、メリット・デメリットを考慮して適切なものを選択できるようになっています。

• 構文解析
• 中間表現の木構造
• 木走査と書き換え
• 記号表（変数テーブル）
• 型チェック
• インタプリタ
• コード変換
• コード生成

（私が知らないだけの可能性は高いですが）このような知見がまとまった書籍は他にないような気がします。言語の変換を行う際に、実装の指針となりとても役立ちました。

ANTLR 4の学習

言語アプリケーションの実装において、すべてを手で実装するのは現実的ではなく、特に構文解析にはパーサージェネレーター（あるいはパーサーコンビネーター）を使うのが一般的です。本書では著者のTerence Parrさんが開発しているパーサージェネレーターのANTLRを使います。

原著が2009年に執筆された本書ではANTLR 3が使われていますが、現在一般的なのは2013年に公開されたANTLR 4です。ANTLR 4はフルスクラッチで書き直され、考え方が大きく変わっています。木構造を生成する文法が削除されるなど、文法定義も互換性がありません。

このため、ANTLR 4で書籍内のサンプルコードを動かすことはできません。おとなしくANTLR 3で動かせばいいのですが、せっかくだし最新のバージョンを使いたかったのでANTLR 4の勉強もはじめました。

この本はANTLR自体を解説した本ではありません。ANTLR 4のリファレンスはGitHubで公開されていますし、文法定義の説明もWebに多くありますが、生成されたパーサーの使い方に関する情報があまり見当たらないように思いました。

ANTLR 4の学習には、（英語ですが）同じくTerence Parrさんが書かれたThe Definitive ANTLR 4 Referenceを読むのがオススメです。タイトルにReferenceとありますが、リファレンスは一部だけで、ANTLR 4の使い方が丁寧に解説されています。

The Definitive ANTLR 4 Reference by Terence Parr | The Pragmatic Bookshelf

以降では、主に参考にした箇所についてコメントします。

中間表現の木構造のパターン

4章「中間形式木の構築」に登場するパターンは、中身は簡単なことなのに難しい名前がついていてわかりにくく感じたので、5章「木の走査と書換え」に登場するパターンとの関連性と合わせて図示してみました。

ちなみにANTLR 3では文法定義にアクションとして抽象構文木を生成するコードを書いたり、木文法で訪問器を生成したりしていたようですが、ANTLR 4が生成するパーサーでは構文解析木が自動的に構築されるように変更されました。外部訪問器の基底クラスも生成されるので、抽象構文木は必要なら外部訪問器を使って自分で生成します。

この方が文法定義がスッキリして分かりやすいコードになるので、良い変更だと思います。

ちなみにパターン15「木パターン照合器」についても、ANTLR 3にあった木書換えの文法はなくなったので、ANTLR 4では代わりに ParseTreePatternを使うようです*1。

記号表のパターン

6章「プログラム記号の記録と識別」と7章「データ集合体のための記号表管理」に登場する記号表は以下のライブラリとして利用でき、助けられました。

github.com

コード変換のパターン

11章「コンピュータ言語の変換」に登場するパターン29「構文主導変換器」とパターン30「規則方式変換器」の違いがちょっとわかりづらかったです。構文ベースで変換するのが前者で、規則ベースで変換するのが後者ということだと思います。しかし、パターン30の例は変換規則DSLとしてANTLRの文法定義を使い、アクションでprint文を使って出力するというもので、これはパターン29でもあるのではないかと感じました。

パターン31「目的構成体ごとに固有の生成器クラス」と12章「テンプレートを使ったDSL生成」との関連もよくわからなかったです。パターン31の最後に「toString()の中で文字列を生成する代わりにテンプレートを使うこともできます。しかしながら、その場合は、特性の生成器クラスはやめてテンプレートだけを使うようにしたほうが良いでしょう。」という説明がありますが、12章はパターン31をより高度にしたものという理解で良いのでしょうか。12章をパターン32として、11章のパターンと比較する説明があると良かったと思います。

まとめ

わかりにくいと書いたところもありますが、私の読み込みが足りないだけとも言えます。全体的に見れば最初に書いたように実装の指針となる良書でした。もし叶うならば、ANTLR 4で書き直されたバージョンを読んでみたいです。

*1:まだ試してないので試したい。

可視化のお供に「PythonユーザのためのJupyter［実践］入門」

PythonユーザのためのJupyter［実践］入門を頂きました。ありがとうございます。そして出版おめでとうございます。

PythonユーザのためのJupyter[実践]入門

まず明らかにしておくと、私は日常的にデータ分析を行っているわけではなく、主にWebプログラミングのためにPythonを使っています。 PyData界隈でJupyter Notebookが広く使われていることは存じていますが、個人的には通常のインタラクティブシェルのほうが手に馴染むので好んで使っています。 このため、本書のメインターゲットではないような気がしますが、その視点からレビューします。

全体の構成

目次を見るとわかりますが、半分以上のページ（4章*1から7章）がMatplotlibとBokehを使った可視化の解説に割かれています。 これらの章はフルカラー印刷で、豊富なグラフの作成例をパラパラとめくって確認できます。

表題のJupyterについても基本的な導入・使い方に加え、設定のカスタマイズやクラウド環境での利用などの解説があり、なんとなく使っていたものをしっかりと手に馴染む道具へと昇華させられると思います。

というわけで、以下のような方にオススメです。

• MatplotlibやBokehを使って可視化する必要があり、リファレンスを手元に置いておきたい方
• Jupyter Notebookの使い方をしっかりと理解したい方

以下、印象的だった章に触れます。

第1章 Jupyter Notebookを導入しよう

WindowsとmacOSにおけるAnacondaを利用したJupyter Notebookの導入方法が丁寧に解説されています。 condaコマンドを利用した仮想環境の扱い方や、Matplotlibでハマりがちな日本語フォントのインストールについても解説があるので安心です。

conda環境という言葉が説明なく出てくるのがちょっと気になりましたが、仮想環境と同じものという認識でよいのでしょうか。

第2章 Jupyter Notebookの操作を学ぼう

Jupyter Notebookの操作やメニュー、マジックコマンドなどについて一通りの解説があります。 なんとなくJupyter Notebookを起動して使っているだけではイマイチわかりづらい、セルの実行状態やモード、.ipynbファイルの仕組みや自動保存などについて丁寧に説明されています。

Jupyter Notebookを使っていると、キーボードショートカットを使いこなさないと思い通りに編集できないと感じます。 ヘルプからショートカット一覧を参照できるものの、数が多いので、本書ではよく使うものに絞って解説されているのがありがたかったです。

最後にJupyter Notebookの共有方法という話があります。 仮想環境にインストールしたライブラリを前提とした.ipynbファイルを共有して、同じ環境・実行結果を再現するにはどうするのだろうというところが若干気になりました。 .ipynbファイル内にはrequirements.txtに相当する内容は含まれてなさそうですし、コメントに書くのでしょうか。 それとも一般的には実行済みの結果さえ共有できれば気にならないものなのでしょうか。

第4章 Matplotlibでグラフを描画しよう

Matplotlibによるさまざまなグラフの作成方法が解説されています。 実際に意味のあるデータをサンプルとして使用しており、このような分析をするときにはこのグラフが適しているといった説明があるので、わかりやすいです。

第5章の最後に解説がありますが、Matplotlibには手続き型のインターフェイスとオブジェクト指向のインターフェイスの2種類が用意されています。 サンプルコードを書く人によって使うインターフェイスが異なり、混乱を招くことがあります。 本書ではPythonらしいオブジェクト指向のインターフェイスが推奨されていて、こだわりを感じます。

第6章 Bokehでグラフを描画しよう

Bokehはブラウザ上での表示を前提とした可視化ライブラリです。Jupyter Notebookと相性がよく、後発である分Matplotlibよりも洗練されています。

最初にBokehでは高・中・低と3つのレベルのインターフェイスがあるという解説があります。 Matplotlibの章と同様にさまざまなグラフの作成例が収められており、それぞれのグラフについてまず高レベルのインターフェイスで簡単に作成できることを確認した後、中レベルのインターフェイスで細かなカスタマイズを行うという構成になっています。 このため、自分が作成したいグラフのカスタマイズ度合いによって、どのインターフェイスを選択すべきかわかりやすいです。

第9章 クラウド上でJupyter Notebookを使おう

Google Cloud Platform (GCP) とMicrosoft Azure上でJupyter Notebookを利用できるサービスの紹介です。 これらのサービスを使えばローカルで環境を構築する手間すら不要です。特にGCP上で使えるCloud Datalabでは、BigQueryなどのGCP上のサービスと連携できて便利そうです。

Appendix

付録と言いながらも、Jupyter Notebook上でインタラクティブな入力を可能にするipywidgetsや、Jupyter Notebookを発表用のスライドに変換する方法など、興味深いコンテンツが収められています。

最後に

本書の「はじめに」には以下の記述があります。

Jupyter Notebookは人気のツールであり、インターネット上には既に可視化に関する多くのドキュメントやサンプルコードが存在します。しかし私たちはJupyter Notebookを日々利用しながら「Jupyter Notebookの活用とデータ可視化における実践例や知見が集まった場所が少ない」と考えていました。

まさにこの課題を解決する内容になっており、同じような課題を感じている方にはピッタリの書籍と言えます。 これからJupyter Notebookを使った可視化を始める方にとっても、必要な知識を短時間で効率よく学べる一冊です。 興味があれば、ぜひお手にとってみてください。

PythonユーザのためのJupyter[実践]入門

*1:正確には3-10節

ElementTreeやlxmlで名前空間を含むXMLの要素を取得する

PythonでElementTreeやlxmlを使って名前空間つきのXMLから要素を取得しようとしても、思い通りに取得できないことがあります。これはよくあるハマりどころですが、あまりまとまった情報がないのでまとめておきます。

Python 3.6.0で検証しました。

目次:

解決したい問題

まず前提としてXMLの名前空間について確認した後、解決したい問題について述べます。

前提知識: XMLの名前空間

1つのXML文書に複数の語彙を混ぜた場合、タグ名などが衝突してしまう可能性があるので、それらの意味を明確にするのが名前空間です。

XMLの名前空間はURI（ここではhttp://www.w3.org/2005/Atom）で表され、XML文書内では名前空間に属する要素や属性を接頭辞（ここではatom:）をつけて表します。

<atom:feed xmlns:atom="http://www.w3.org/2005/Atom">
...
  <atom:title>orangain flavor</atom:title>
...
</atom:feed>

xmlns属性でデフォルト名前空間として指定した名前空間は接頭辞が不要になるので、以下のようにも書けます。

<feed xmlns="http://www.w3.org/2005/Atom">
...
  <title>orangain flavor</title>
...
</feed>

当ブログのAtomのソースもこのような形になっています。

参考: XML名前空間の簡単な説明

問題: 名前空間を含むXMLから意図した要素を取得できない

さて、このようなXML文書のtitle要素を取得しようとして、以下のように書いても要素が取得できません。

from urllib.request import urlopen
from xml.etree import ElementTree

f = urlopen('http://orangain.hatenablog.com/feed')
xml = f.read()
root = ElementTree.fromstring(xml)

title = root.find('./title')  # title要素を取得するつもりがNoneとなる
print(title)  # None

以降では、この問題への対応方法を見ていきます。（RSSやAtomなどのフィードに限って言えば、feedparserのようなライブラリを使えば生のXMLを意識する必要はありませんが、ここでは名前空間を持つXMLの一例としてAtomを取り上げます。）

対応方法

基本的な対応方針としては以下の2つを行います。

1. XPathに名前空間の接頭辞を含める
2. find()などのメソッドに{名前空間の接頭辞: URI}形式のdict（本記事では名前空間マッピングと呼ぶ）を渡す

注意点は、デフォルト名前空間であっても必ず適当な接頭辞をつけなくてはいけないということです。「名前空間なし」と「デフォルト名前空間」は完全に別のものと認識されます。

ElementTree（標準ライブラリ）の場合

ElementTreeのfind()やfindall()では以下のようになります。

from urllib.request import urlopen
from xml.etree import ElementTree

f = urlopen('http://orangain.hatenablog.com/feed')
xml = f.read()
root = ElementTree.fromstring(xml)

title = root.find('./atom:title', {'atom': 'http://www.w3.org/2005/Atom'})  # 第2引数に名前空間のマッピングを指定
print(title)  # <Element '{http://www.w3.org/2005/Atom}title' at 0x108e545e8>

ちなみに以下のようにXPath内に直接名前空間のURIを書くこともできます。これはElementTreeのAPIで使用できる特殊な書式であり、有効なXPathではないため、後述するlxmlのxpath()では使用できません。（そもそもElementTreeではXPathのサブセットのみ使用できます。）

title = root.find('./{http://www.w3.org/2005/Atom}title')  # 名前空間のURIをXPathに含める

lxml（サードパーティライブラリ）の場合

lxml 3.8.0で検証しました。

lxmlのxpath()では以下のようになります。なおnamespacesはキーワード引数でしか指定できません。

from urllib.request import urlopen
from lxml import etree

f = urlopen('http://orangain.hatenablog.com/feed')
xml = f.read()
root = etree.fromstring(xml)

title = root.xpath('./atom:title', namespaces={'atom': 'http://www.w3.org/2005/Atom'})[0]
print(title)  # <Element {http://www.w3.org/2005/Atom}title at 0x108ab8e08>

（lxmlにもElementTree互換のfind()などがあり、ElementTreeの場合と同様の書き方ができます。が、lxmlで敢えてXPathのサブセットしか使えないこれらのAPIを使うメリットは少ないでしょう。詳しくはあとで触れます。）

XPathにデフォルト名前空間を指定したい

さて、名前空間を指定すれば取得できるのはわかりましたが、XPathに名前空間を含めるのは正直面倒です。XMLではデフォルト名前空間によって簡潔に書けるようになっていますが、XPathでも同様にできないのでしょうか。

結論から言えばXPath 1.0ではできません。XPath 1.0の仕様として、名前空間を指定しない要素は常に「名前空間なし」の要素を意味し、デフォルト名前空間のようなものを指定することはできません。lxmlのFAQにもこの旨が書かれています。

XPath 2.0以降ではデフォルト名前空間を指定できるようになっているようですが、XPath 2.0以降は1.0から大きく変わってXQueryという仕様のサブセットになっています。世の中の実装も多くはXPath 1.0のままであり、lxmlで使われているlibxml2でもXPath 2.0をサポートする予定はないそうです。

参考: objective c - Does libxml2 support XPath 2.0 or not? - Stack Overflow

諦めてXPathに名前空間を含めましょう、ということなのですが、微妙な感じの対処法を2つ紹介しておきます。

実はlxmlのfind()やfindall()ではデフォルト名前空間を指定できる

実はlxmlのfind()やfindall()はElementTreeのそれから拡張されており、デフォルト名前空間を指定できます。名前空間マッピングでキーをNoneにすると、それがデフォルト名前空間として使用されます。

title = root.find('./title', {None: 'http://www.w3.org/2005/Atom'})

さらに、lxmlではroot.nsmapでドキュメントの名前空間マッピングを取得できるため、以下のように書けます。

title = root.find('./title', root.nsmap)

また、lxmlでは名前空間のURIにワイルドカードを指定できるので、以下のようにも書けます。

title = root.find('./{*}title')

これらの書き方だと名前空間のURIを意識しなくてよいので嬉しいですが、ElementTreeからの拡張についてドキュメント化されていないこと、lxmlでfind()を使うメリットが少ないことから、微妙な感じです。

よく使うであろうxpath()では、名前空間マッピングのキーをNoneにするとエラーになるので注意が必要です。

名前空間の宣言を消してしまう（雑）

非常に雑ですが、XMLの文字列から名前空間の宣言を消してしまうという方法もあります。以下のようにデフォルト名前空間の宣言を消せば、名前空間を気にせずに要素を取得できるというわけです。

from urllib.request import urlopen
from xml.etree import ElementTree
import re

f = urlopen('http://orangain.hatenablog.com/feed')
xml = f.read()
root = ElementTree.fromstring(re.sub(rb'xmlns=".*?"', b'', xml, count=1))

title = root.find('./title')
print(title)  # <Element 'title' at 0x108308598>

書き捨てのスクリプトであれば、これで十分な場合もあるでしょう。誤って意図しない箇所を置換してしまう可能性もあるので、自己責任でどうぞ。

デフォルト名前空間だけでなく、他の名前空間もある場合は、すべての名前空間を消す必要があります。正規表現では厳しくなってくるので、一度パースしてから書き換えるのが無難です。詳しくは以下のページを参考にしてください。

参考: Python ElementTree module: How to ignore the namespace of XML files to locate matching element when using the method “find”, “findall” - Stack Overflow

ちなみにこのページにも「XMLの文字列を正規表現で書き換えるなんてとんでもない！」というコメントがあります。

まとめ

名前空間を含むXMLに対してXPathを使用する際は、面倒ですが名前空間を1つ1つ指定しましょう。

Pythonクローリング&スクレイピングでElementTreeを扱った箇所では、シンプルさを優先して名前空間のついたAtomの代わりに名前空間のないRSS 2.0からデータを取得しました。よくあるハマりどころなので、名前空間のついたXMLを扱う方法もどこかに書いておけばよかったなと思い、記事にしました。

scraping-book.com

参考

• lxmlでXMLパースしたらnamespaceではまった - YAMAGUCHI::weblog
• Pythonで名前空間付きのXMLを操作する(ElementTree) - Qiita
• RSS1.0を検索する際の名前空間の指定 - stogの日記
• lxmlでXMLをパースする - ふたこもり
• Issue 18304: ElementTree – provide a way to ignore namespace in tags and searches - Python tracker
• python - lxml etree xmlparser remove unwanted namespace - Stack Overflow

「プログラミングHaskell」を読んだ

ちょっと前の記事で宣言したように「プログラミングHaskell」を読んだ。

A5判で本文は185ページと読みやすい分量なのに、小さな関数を1つずつ作りながらしっかりと理解できて良かった。これもHaskellの記述の簡潔さのおかげと言えるだろう。若干説明が足りないところには、すかさず訳注が挿入されており、素晴らしかった。

プログラミングHaskell

それぞれの章の感想

一通り読んで練習問題もだいたいやった。それぞれの章について思ったところを残しておく。

1章〜6章

これらの章はPythonとLispの経験があったおかげで、あまり引っかかるところはなかった。1章に出てくるHaskellでのクイックソートのエレガントな実装によって引き込まれた。

3章での「1つ以上のクラス制約（例: Num a）を持つ型を多重定義型と呼ぶ」という定義は未だにしっくりこない。

4章で出てくるパターンマッチは便利。

7章 高階関数

畳み込みを行うfoldrやfoldlは苦手だったけど、練習問題などで使ったことで少し慣れてきた。

関数合成は便利。数学で出てきた時はf(g(x))と連続して適用することに比べたメリットがよくわからなかったが、Unixのパイプみたいに関数を順に適用していく書き方ができて便利さを実感した。

以下は86ページに掲載されているencode関数。文字列に含まれる文字を1文字ずつ数値にして、2進数に変換して、8bitになるよう揃えた後に結合する。

encode :: String -> [Bit]
encode = concat . map (make8 . int2bin . ord)

関数合成によって括弧が減るのも重要。

8章 関数型パーサー

本章のプログラムは動かないと書かれていてちょっと辛かった。

結果的には、原著者のサポートページからコードをダウンロードし、Parsing.hsからParser*1, parse, itemの定義だけ抜き出してきて、failureと(+++)をPで囲う形に置き換えたら動くようになった。

failure :: Parser a
failure = P (\inp -> [])

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = P (\inp -> case parse p inp of
                      [] -> parse q inp
                      [(v,out)] -> [(v,out)])

9章 対話プログラム

パーサーが「残りの文字列」という状態を変化させながらパースしていくのと同様に、対話プログラムはIOによって表示や入力などの世界の状態を変化させながら動作する。この意味でパーサーと対話プログラムには共通項があり、10章のモナドの話につながっていくという流れ。

エスケープシーケンスを出力することでコンソールの表示を制御するというのは、これまでほとんどやったことなかったので新鮮だった（積極的に使いたいものではない）。

10章 型とクラスの定義

新しい型を宣言するdataはシンプルに書ける割に強力で便利。

最終的にモナドが出てきた。Haskellと言えばモナドというイメージあるけど、あっさりとした説明だった。

今のところの雑な認識としては、モナドは副作用のあるアクションをdo記法で繋げて手続きっぽく書けるようにするためのクラス。モナドによって何かスゴイことができるようになるわけではなく、（手続き型言語では普通に行われている）副作用を扱うことが純粋関数型のHaskellでもできるようになるのがスゴイという理解。

11章 切符番号遊び

ずっとインタラクティブシェル（ghci）で動かしてきたが、総当りで解くにはちょっと性能が足りなかった。ghcでコンパイルする方法をググって実行ファイルを作った。

12章 遅延評価

遅延評価ってなんだか難しいけどいい感じにやってくれてるという雰囲気で使っていたが、式を簡約する時に外側から簡約していき、複数回評価しなくても良いよう同じ式にはポインタを張っておくことで実現できることを学んだ。ちなみに遅延評価のない普通の言語は内側から簡約していく。簡約の順番が得られる結果に影響しないのは、副作用のない純粋関数のみで構成されているおかげ。

無限リストを使ったエラトステネスのふるいの実装も美しかった。

13章 プログラムの論証

Haskellの関数は=で定義されているので、数式と同様に証明できるというのは面白かった。人間が手で証明するのは面倒なので、自動化したいというモチベーションもわかる。

全体的な感想と今後

関数型言語をちゃんと学ぶのは初めてで、いろいろと新しい気付きがあった。Pythonなどの関数型言語の影響を受けた言語をこれまで使ってきたことで、さほど苦しまずに学べたのはラッキーだった。

カリー化やモナドなどのキーワードを聞いても何が嬉しいのかわかっていなかったが、Haskellの世界を構成する上で必要なものだと実感できた。

しかし、Haskellが向く用途がまだよくわかっていない。Haskellのメリットは理解したが、他の言語で書くのと比べてどの程度良くなるのかは、実際にいくつかプログラムを書いてみないとわからないと思う。

そして実際に何か書いてみようと考えると、まだ学ぶべきことはいろいろある。そもそもmain関数の書き方とかモジュールの定義方法の説明とかなかった。例えばWebアプリケーション作るにはどうしたらいいんだろうとか、サードパーティライブラリの使い方とか。モナドについてももっと知りたい。

というわけで、次はとりあえず「関数プログラミング実践入門」を読んでみることにする。手元にあるのは改定される前の版の方だが。

[増補改訂]関数プログラミング実践入門 ──簡潔で、正しいコードを書くために (WEB+DB PRESS plus)

*1:Parserの3つのinstanceの宣言も含む

神戸Pythonの会でクローリングとスクレイピングについて話した

だいぶ日が経ってしまいましたが、神戸Pythonの会でクローリング・スクレイピングについて2回話してきました。

1回目はRequestsとBeautiful Soupを使った基本的なスクレイピングについて、2回目はHeadless Chromeを使ったスクレイピングについて話してきました。

資料は概要的なもので、これだけ読んでもあまり役立たないですが、以下のリンク先にあります。

• 1回目: Crawling and Scraping in Python
• 2回目: Crawling and Scraping using Headless Browser

演習問題もやりました。こちらのほうがメインです。

github.com

感想など

神戸Pythonの会は去年から始まったコミュニティで、しばしば参加させてもらってます。登壇者との距離が近くて質問しやすく、演習問題などでコードを書く時間を多く取っているのが好みです。

参加者の皆さんは研究や業務など、様々な目的でクローリング・スクレイピングに興味を持たれていました。終了後に感想を伺うとPythonのライブラリの便利さに驚いたといった声や、やりたかったことができそうという声があり、少しは役立ったかなと思います。

参加者の中にはPythonクローリング&スクレイピングを購入してくださった方も多く、とてもありがたかったです。2回目には書籍を読んでから私のTwitterアカウントを知り、Twitterでの告知を見て参加してくださった方も居て、なんとも感激でした。

ちなみにPythonクローリング&スクレイピングは先日また増刷され、半年余りで第4刷になりました。編集者さんからは「新人著者にしてはかなりのヒット」というお言葉をいただき、注目の集まる題材でタイミング良くオファーを頂いたことの幸運を噛みしめるとともに、お世話になった関係者・読者の皆様に改めて感謝しております。今後ともよろしくお願いします。

scraping-book.com

「スモールコンパイラの制作で学ぶプログラムのしくみ」を読んだ

最後まで実装したわけではないが、とりあえず関数呼び出しや四則演算を伴う鶴亀算のコードは動くようになり、あとは時間さえかければ機能を増やせるところまでできたので満足した。

結果として、知識としてなんとなく知っているレベルだったことに実感が伴うようになった。再帰的下向き構文解析とか、実行時のプログラムカウンターやスタックの動きとか。特に、関数呼び出しの時に引数をスタックに積んでから関数内のスコープから負のアドレスで参照するというのはなるほどだった。

スモールコンパイラ の制作で学ぶ プログラムのしくみ

例え話はわかりにくいがとっつきやすい

この本はずっと昔に買って、いつかやろうと思って本棚に寝ていた。記憶が曖昧だが、おそらく以下の記事を読んで一番とっつきやすそうなのを選んだのだと思う。勧められていた気がしたが、改めて読んだら「文章に難あり」と書いてあった。。

プログラミング名著100選 - やねうらお－ノーゲーム・ノーライフ http://d.hatena.ne.jp/yaneurao/20050912

この記事のコメントやAmazonのレビューにも書かれているけど、りんごの例え話が意味分からないというのが一番のツッコミどころである。

まあでも例え話は適当に読み飛ばして、コードと虎の巻の部分をちゃんと読み込めばなんとかなる。Javaで書いてるのにC言語的なコードになっているのは辛いが、いい感じにEnumとかMapとかListとかで置き換えればこれも許容範囲。全体的にとっつきやすさがあって良かった。

本を書いたことがある身としては、10年以上経っても問題なく読める本というのはすごいなぁという印象である（携帯電話のiアプリはなくなってしまったが、些細な問題である）。

仕様に対する説明があると嬉しい

さて、上に挙げたツッコミどころを我慢できる場合、次に気になるのは題材として作る言語・コンパイラ・VMの仕様がなぜこうなっているかという解説が足りていないところである。限られたスペース・難易度で説明する都合上、仕様を簡略化するのは当然なのだが、実際のプロダクトとの比較があると良かった。

例えば、int型の変数宣言vIとint型の関数の戻り値Iが別のキーワードになっている言語は使いづらいと思うけど、なんでこうしたのかとか。まあ関数宣言と変数宣言を最初のトークンで区別できるようにしないとLL(1)にならないからなのだけど、じゃあ同じキーワードを使えるようにするためにはこうする必要がありますとか。

他にもワンパスでコードから直接VMの命令に変換してるけど、一旦構文木を作ったほうがコードの見通しが良くなるのではとか。

よく知らないけどVMの命令セットはこんなものなのだろうか。ディスプレイの退避と回復がditとdikなの、イケてないのだが。一般的なものと比較してどうだとかの解説があると良かった。

扱えるデータ型としては整数のみから始まり、3章で文字列型を使えるように拡張するのだけど、文字列型専用のスタックを別に用意するという実装方法になっていた。これだと拡張性がないので一般的な実装方法を知りたかった。ヒープにオブジェクトを確保してポインタをスタックに詰む感じなのかな。

今後

こんな感じでいろいろとツッコミどころがあるゆえに、もっと詳しく勉強したくなる本だった。 とりあえず発展的に学習できそうな以下の3冊を注文してみた。

コンパイラ (新コンピュータサイエンス講座)

ふつうのコンパイラをつくろう

言語実装パターン ―コンパイラ技術によるテキスト処理から言語実装まで

しかし、この方面は頑張って勉強・実装しても結局既存の言語を内部DSLとして使ったほうが便利なことがほとんどなので、あまり時間をかけたくないという思いも常に抱えている。その辺の合理的な判断を一時の熱中で抑えてどこまで進めるかが勝負なのかもしれない。

言語を改良する方向性だけでなく、Haskellみたいな関数型言語を使うとパーサーが書きやすいという方向性で勉強するのもいいかもしれない。とりあえず注文した本が届くまで、これまた積まれているHaskell本をやってみる。

プログラミングHaskell

将棋の定跡を勉強するためのアプリ「Kifu Notebook」を作った

最近3月のライオンを見て、子供の頃以来の将棋を始めるなどした。

最近は将棋も改めて勉強してる。直接のきっかけは3月のライオンを見たことだけど、大人になってからボードゲームをやると子供の頃とは違うように見えることに気づいたというのもある

— かと (@orangain) 2017年3月7日

適当なアプリをダウンロードしてコンピューターと対戦すると、ちょっと悪い手を指すだけで付け込まれて負けてしまう。序盤の定跡というものの理解が足りていない。相手の指す手に合わせて最適な手を指し続けなければならないので、1つの戦法だけ知っていても意味がない。

図書館で将棋の本を借りてきたり、勉強のためのアプリを購入するなどしてみた。解説されている個別の戦法は理解できるものの、考えられるすべての指し手（ここでは指し手空間*1と呼ぶことにする）における、その戦法の位置づけが把握できない。もちろん指し手空間は膨大なのだが、それをある程度限定するのが序盤の定跡という考え方のはずだ。

というわけで、指し手空間を樹形図のような形で可視化したかった。世の中の人はどうやって勉強しているのだろう。よくわからないので、とりあえず自分で樹形図的にメモを取れるアプリを作ってみた。それがKifu Notebookである。Pythonの人には自明かと思うがJupyter Notebookにインスパイアされている*2。

使い方

GitHubのReleasesから自分のOS用のバイナリをダウンロードしてきて、以下のように起動する。引数にはメモを保存するJKFファイルのパスを指定する。最初はサンプルファイルをダウンロードするとわかりやすいと思う。存在しないファイルのパスを指定したらまっさらな局面から始まり、Saveしたときにファイルが作成される。

kifu-notebook joseki.jkf

ブラウザーで以下のような画面が開く。

主な使い方は次のとおりである。

• 盤面でドラッグ&ドロップして（ルール通りに）駒を動かすと指し手が画面下部の樹形図に追加される。
• 樹形図の指し手をクリックするとその局面に移動できる。
• 既に次の指し手がある局面で別の手を指すと、分岐として記録される。
• 樹形図の指し手にホバーした時に表示されるボタンで、指し手を左右に移動したり、削除したりできる。
• 右のコメント欄にその指し手のコメントを書ける。コメントがある指し手には*がつき、ホバーするとツールチップでコメントが表示される。
• bad:で始まるコメントがある指し手はそれ以降薄い色になる。指し手はいけない手を記録するのに役立つ。
• 右上のSaveボタンをクリックすると、コマンド起動時の引数に指定したJKFファイルに現在の状態を保存できる。
• Auto Saveにチェックを付けておけば、変更する度に自動的に保存される。

実装

ソースコードはorangain/kifu-notebookに置いてある。

Kifu for JS

将棋盤はKifu for JSのものを使用している。Reactのコンポーネント自体はライブラリとしてエクスポートされていなかったので、とりあえずforkしたものを使用している。

Kifu for JSはReactで作成されており、コンポーネント単位でいい感じに再利用できたので非常に助かった。

JSON棋譜フォーマット (JKF)

メモを記録するファイル形式としてJSON棋譜フォーマット (JKF) を使用している。Kifu for JSと同じくna2hiroさんのライブラリである。こうやって1人で界隈の必要なものを作っているのはカッコよくて憧れる。

JKFはKifu for JSにおける標準形式？であり、指し手の分岐やコメントなどの必要な要素が満たされており、JSONで使いやすかったので使わせてもらった。ただ、JKFはメインの棋譜があってそこに分岐を付け足す形なので、分岐を平等に扱うKifu Notebookで求められるデータ構造とは若干異なっていた。このため内部的には別の木構造を使っており、入出力の際にJKFと相互変換している。

shogi-piece-images

Kifu for JSでは将棋の駒画像として将棋アプリ用クリエイティブコモンズ画像が使われているが、PNG形式で解像度が低いのでRetinaディスプレイではちょっと気になった。錦旗一字駒はベクター形式も公開されているが、あまり好みじゃなかった。

そこでWikimedia Commonsに公開されていたHari Seldonさんによる駒のSVG画像を改変（枠の除去、背景色・影の追加など）して使用した。shogi-piece-imagesとして、CC BY-SA 3.0 Unportedで公開している。

React

Web UIにはReactを使っている。これまで使ったことなかったけど、Kifu for JSで使われていたので触ってみた。最初はKifu for JSを直接書き換える形で作っていたが、差分が大きくなってきた頃にcreate-react-appを使って1から作り直した。

最初はLocal Stateを使っていたが、複数のコンポーネントで状態を共有したほうが綺麗になる気がしたのでReduxを使うことにした。Presentational ComponentとContainer Componentを分けるという考え方は、propsとstateが混ざっていて気持ち悪かったので納得感があった。React/Redux界隈から漏れ聞こえてくるMiddlewareが重要だなという問題意識までは追いついたが、特に解決できているわけではない。

Go

コマンドはGo言語で書いた。みんなのGo言語に書かれていたgo-assets-builderを使ってビルドしたReactアプリを含めただけのコマンドにしている。

なんとなくブラウザで動かしたかったのでコマンドにしたけど、ユーザー層を考えるとElectronアプリとかのほうが使いやすかったかもしれない。この辺は検討の余地がある。

まとめ

Kifu Notebookという将棋の定跡を勉強するためのアプリを作った。将棋の指し手を樹形図のように可視化してメモできる。

Reactでの開発が面白くて将棋の勉強は放ったらかしになっている。早めにKifu Notebookを使って勉強を始めないと将棋への熱が冷めてしまう。

もしご存知の方がいれば、iPhoneで以下の条件をなるべく満たすオススメの将棋アプリを教えてもらえるとありがたい。

• 有償で構わないので広告がない
• 1人でコンピューターと対戦できる
• 待ったができる
• 相手のコンピューターの強さを調整できる
• （可能なら）相手のコンピューターの戦法を指定できる（例えばコンピューターを先手にして居飛車で戦ってほしいなど）

*1:コンピューター将棋における探索空間と同じ意味で使っているが、探索という言葉はしっくりこない。適切な言葉があれば知りたい。

*2:参考: https://twitter.com/orangain/status/839398377410326528