リーダーマクロと行カバレッジとステップ実行を作った

Gauche

これはKPF#x09のネタとして作成して発表したものです。台風の影響で勉強会は延期になってしまいましたが、これ以上公開を先延ばししたくないので予定通り公開します。
リポジトリはこちら。github上にあります。
今回はGaucheにリーダーマクロ、行カバレッジ計測、ステップ実行の三つを実装しました。
それぞれ説明しているためかなり長くなっています。
目次代わりにそれぞれの章へのジャンプを作っておくので、気になるところだけ見ていってください。


はじめに

今回使っているGaucheのバージョンは0.9.4です。
他のバージョンで動作する保障はありません。
また、リーダーマクロについての説明の関係上COMMON LISPのリーダーマクロについて触れていたり、その知識を前提として説明している部分があります。ですが、COMMON LISPのリーダーマクロ自体の解説は行っていません。ごめんなさい。


今回三つの機能を実装していますが、すべてGaucheレベルのスクリプトで実装しています。
ただし、行カバレッジやステップ実行のスクリプトを実行するためには、一箇所だけGauche本体のソースを修正しなければなりません。(※追記あり。現在はこのパッチを当てる必要はありません。)

この修正ではload関数から呼ばれるread関数を上書きできるようにしています。
Gaucheレベルでreadに対してset!したとしてもload関数内からは呼ばれないため、このような修正が必要になります。
上記のdiffはgit diff --no-prefixで出力したものなので、Gaucheのルートディレクトリで以下のようにパッチを当てることが出来ます。

diff -p0 < patch

ちなみにですが、diffを適用させた後に再コンパイルする必要があります。

※追記 2014年8月13日時点のGauche開発レベルの最新版では上記のパッチを当てる必要はありません。パッチの様なその場しのぎではない方法でちゃんと上書きしたread関数が呼ばれるようになりました。


Gaucheにリーダーマクロを導入する

リーダーマクロはCOMMON LISPにある機能です。
通常のマクロはevalされる前(ほとんどの場合はコンパイルタイム)に評価されますが
リーダーマクロはさらにその前、read時に評価されます。
GaucheはSchemeの実装ですからリーダーマクロは存在しません。
といっても通常のマクロは存在するわけで、リーダーマクロもあっていいだろうということで実装してみました。
github上のリポジトリではsrc/ya/以下のファイルがリーダーマクロを実装するために必要なファイルです。


さて、リーダーマクロをGaucheに導入する方法を考えます。
リーダーマクロはread関数の動作と密接に結びついているのですが
GaucheのreadはC言語で実装されているのでカスタマイズする余地がありません。
なので今回はread関数そのものを再実装しています。


実装したread関数の特徴
  • 構文は全てリーダーマクロで実装
    • ' (クオート)も" (文字列) ( (リスト)も#u8( (各ユニフォームVector)など全てリーダマクロとして定義。
  • トライ木を使ってリーダマクロ のテーブルを表現している
    • 一文字ずつトライ木から検索できるように、標準ライブラリのトライ木モジュールを拡張しています。
  • Gaucheの標準ライブラリは全て読込み可能
    • 対応していない構文はsrfi-38の共有データ参照読込みだけです。
  • Gauche本体のread関数より5倍くらい遅い


こんな感じでリーダーマクロをベースとしたread関数を実装しました。
では本題のリーダーマクロの説明に入ります。


実装したリーダーマクロの仕様
  • COMMON LISP風のterminatingとnon-terminatingのマクロを持つ
  • 独自のリーダーマクロタイプ、right-terminatingを持つ
  • COMMON LISP風の文字種類操作ができる

    (whitespace, constituent, illegalと独自のskipという種類を指定できる)
  • ディスパッチマクロは存在しない
  • マクロ名の長さに制限が無い


COMMON LISPのリーダーマクロをベースにしつつ
かなり大胆に独自仕様を取り入れています。
一番大きな点はディスパッチマクロが無い代わりに、そもそもマクロ名の長さに制限が無いことでしょう。
なので、文字単位にマクロを紐付けるという考え方ではなく
文字列に対してリーダーマクロを紐付けるという考え方になります。


マクロ種類
今回の実装で重要になるのがterminatingとnon-terminating、さらに独自仕様のright-terminatingの動作の違いです。
(以下、それぞれをterm、non-term、right-termと書きます)
  • term
    • termに指定したマクロ文字列はシンボルの途中に存在しても認識されます。
    たとえば、'　(クオート)や"　(文字列の始まり)や(　(リストの始まり)などがtermマクロです。

    a'bc

    という区切り文字を含まない文字列でも、aというシンボル、(quote bc)というリストの二つとしてreadされます。


  • non-term

    • non-termマクロの場合は読み取ったシンボルと完全一致した時だけ認識します。

    これは通常の関数やマクロの呼び出しと同じような考え方です。

    読み取ったシンボルに対応するリーダマクロが存在すれば、それが実行されます。

    #tや#fをnon-termマクロとして定義しています。


  • right-term

    • right-termマクロは、termとnon-termの中間の性質を持ちます。

    マクロ文字列は読み取ったシンボルの開始から一致する必要がありますが、シンボルの途中でもリーダマクロ文字列が完成した段階で、認識されます。

    right-termマクロは、本来はディスパッチマクロとして定義されていたリーダーマクロのために導入しました。

    そのため、Vectorのための#(　などほとんどのディスパッチマクロはright-termとして定義しています。


それぞれのマクロ種類で動作がどのように違うのか具体例を示して説明します。
abcというリーダーマクロが定義された環境でreadしたとして、どのような結果になるかコメントで示します。
コメントの先頭が○ならabcリーダマクロの認識可能、×なら認識不可能です。

  • termの場合

    • abc   ;○
abcd  ;○ abcリーダマクロが返した値とシンボルdの二つとして読み込まれます
zabcd ;○ zシンボル、abcリーダマクロが返した値、シンボルdの三つとして読み込まれます

  • non-termの場合

    • abc   ;○
abcd  ;× abcと完全に一致した時だけ、non-termリーダマクロは認識されます
zabcd ;× 同上

  • right-termの場合

    • abc   ;○
abcd  ;○ abcリーダマクロが返した値とシンボルdの二つとして読み込まれます
zabcd ;× right-termマクロはシンボルがabcから開始している必要があるため、この場合は認識されません。


一致するマクロの探索
termとright-termは、シンボルの途中でも部分一致するマクロが見つかれば認識されます。
なので異なるリーダーマクロが同じプレフィックスを持つ場合、複数のマクロが一致することがあります。
今回の実装では、最長一致するマクロを認識するようにしています。
たとえば、abとabcというtermマクロが定義された環境で以下の文字列をreadすると、

zabcd

zabcdはabとabcのどちらも含んでいますが、この場合はより長い文字列のabcが採用されます。
結果、シンボルz、abcリーダマクロが返した値、シンボルdの三つとしてreadされます。


文字種類操作
COMMON LISPに習い、読み込んだ文字をどのように扱うかを指定することが出来ます。
whitespace, constituent, illegalはCOMMON LISPにもあり、同じ意味を持ちます。
skipは独自の種類で、単にその文字を飛ばし、readを継続します。whitespaceと違い区切り文字にはなりません。


今回の実装では、COMMON LISPにあるsingle escapeとmulti escapeがありません。
これはディスパッチマクロが無いことと関連しています。
Gaucheでは#| はブロックコメントの始まりという意味を持つのですが、この構文を認識するためにはmulti escape文字の| をconstituentとして扱う必要がありました。
single escape文字のバックスラッシュも同じ理由でconstituentにする必要があります。
別の文字をsingle escapeやmulti escape文字にすることも考えました。
ですが、single escapeとmulti escapeの動作はGaucheにとってあまり重要ではないのかな？と考え、実装をしないという判断をしています。


リーダーマクロを使ったサンプルプログラム
リーダーマクロを使ったサンプルとして、Whitespace言語をリーダーマクロベースで実装してみました。
プロジェクト内のsrc/whitespace.scmがそのソースコードです。
まず、文字種類の操作を利用して本来区切り文字になるスペースとタブと改行(LF)を構成文字として読込み、それ以外の文字を無視するように設定しています。
次に、Whitespace言語の命令(IMP)とコマンドの組をリーダーマクロ文字列にして、リーダマクロ内では単に対応するGaucheの式を返しています。
ただし、Whitespace言語のgoto命令は後方にあるラベルにもジャンプできるため、単純に各命令をreadでS式に変換してevalするだけ、というわけにはいきませんでした。
その点だけ良い方法が思いつかず、不本意な実装になっています。


実際に動かすには、Whitespace言語のExamplesページにある各サンプルをダウンロードして、
ya-readのルートディレクトリに移動して、以下のようにコマンドを実行してください。

$ gosh -I src/ src/whitespace.scm hworld.ws

すると、「Hello, world of spaces!」と表示されると思います。


行カバレッジ計測

リーダーマクロを導入する過程で、read関数そのものを作成しました。
このread関数にフックを仕込めるようにすれば、さまざまなタイミングでより柔軟な式への操作を行えるようになります。
その応用の一つとして、評価される式の全てを

(begin
  (line 1 "test.scm")
  any-expression)

のように囲むことで、式が評価された時に同時にline関数を実行することが出来ます。
line関数内で式が実行されたことを記録するようにして、最後に統計を出せばカバレッジ計測機能の完成です。


評価される式はどこか？
「評価される式」と簡単に書きましたが、さて、その式の区別が簡単に付くでしょうか？
たとえば以下の式では、どこが構文的な意味を持つ式で、どこが実行時に評価される式でしょう。

(let ([a (+ 1 2)]
      [b 3])
  (* a b))

(if-let1 a (memq a l)
  (print "true")
  (print "false"))

(and-let* ([num (string->number str)]
           [(exact? num)]
           [(integer? num)])
  (print num))

Gaucheのプログラムに慣れている人であれば、一目でわかるかもしれません。
ですがそれ以前に、Gaucheはdefine-syntaxやdefine-macroによって、ユーザが自由に構文を定義できます。
さらに、letが上書きされている場合など、環境によって結果が変わります。
構文は無限に存在して、環境により結果も変わる。そんな状況では事前に構文に対するパース処理はかけません。
そんなわけで、無限の構文を有限にするため、以下の様な流れで処理を行います。


評価される式を特定する流れ
青字はGaucheの機能を利用
赤字は自前実装
  1. ソース
    2. テキストが次の処理に渡ります。
  2. read
    3. S式が次の処理に渡ります。
  3. Gaucheコンパイラ Pass1
    4. iform(Gaucheコンパイラで使用する内部表現)が次の処理に渡ります。
    マクロ、拡張構文はコンパイラによって全て展開されます。
  4. 逆コンパイル
    5. S式が次の処理に渡ります。
    この時に、評価される式への操作が出来ます。
  5. Gaucheコンパイラ
    6. コンパイル済みのコードが次の処理に渡ります。
  6. eval
無限の構文を有限の構文に変換するため、処理の三番目でGaucheコンパイラのPass1だけ実行します。
Pass1では全てのマクロと拡張構文が展開され、iformと呼ばれる構造に変換されます。
iformはタグで区別され、そのタグは現状25個しかありません。言いかえると、25個しか構文が存在しないプログラムに変換されるわけです。
25個しかないのであれば一つ一つの解析をすることができるので、タグ別の処理を書いてiformの中から評価される式を抽出しています。
このいったんコンパイラのPass1を通すというアイデアは、koguroさんのglitを参考にしました。


抽出する作業と、次にまたコンパイラを通さないといけないためiformからS式に戻すという作業を四番目で行っています。
この逆コンパイルはGaucheの内部処理にべったりと依存してしまっているので、バージョンが変わると動かなくなるでしょう。
しょーがないです。


Gaucheのテストコードでカバレッジを計測してみる
せっかくなのでGauche本体のテストを実行してみて、標準ライブラリに対するテストカバレッジを出してみましょう。
その前にGaucheのテストコードには自前実装のreadで読み込むことが出来ない参照読込み(#0#や#0=など)が含まれているため、そこの部分だけコメントアウトする必要があります。

それ以外は読み込んで実行することができるのですが、自前のread関数で実装をサボっているところや、カバレッジ計測のために式をインジェクションしているため、テストが失敗することがあります。ですが今回は気にしない方針で行きましょう。
※実はio2.scmにも参照読込みを使用したコードが存在しますが、io2.scmは他にもちゃんと対応できていない構文がたくさんあるためテスト対象から外しています。Gaucheのread関数のコンパチを名乗るためには、このio2.scmをちゃんとread出来るようならないといけないですね。


それでは結果ですが、Gaucheのカバレッジは52%でした。
実際にプログラムから出力された各ファイルの明細をこちらからダウンロード出来るようにしています。ぜひ見ていってください。
フォルダ内のindex.htmlにサマリ、サマリ内の各ファイル名をクリックすると詳細を見ることが出来ます。


実際にGaucheのテストカバレッジを図るためには、ya-readディレクトリのルートで以下のように実行する必要があります。

gosh -I src/ -I /hoge/Gauche/test/ src/coverage.scm --basedir=/hoge/Gauche/src/ --tests=GaucheTests

注意点として、/hoge/Gauche/test/と/hoge/Gauche/src/の二つの部分は実際にGaucheのソースコードがあるパスに書き換えてください。
また、なぜかsystemのテストの動作が不安定です。完全に止まってしまいどうしようもない時はGaucheTestsファイル内のsystem行の先頭に;を入れてコメントアウトしてください。
テストには普通に実行するのと比べてかなり時間がかかります。辛抱強く待つと急にテストが終わるので、そうすると現在のディレクトリに.coverageというディレクトリが出来ていると思います。その中に上でダウンロードできる内容と同じ明細が作成されています。


ステップ実行

やっと三つ目。Gaucheスクリプトのステップ実行です。
ここまで来ると特に難しいことはやっていません。
カバレッジ計測の時と同じ要領で関数呼出を行う式を全て以下のように修正します

(begin
  (break ...)
  func-call-expression)

break関数は対象の式がブレイクポイントになっているかを確認し、ブレイクポイントであればプログラムの実行を一時中断させます。


すごいぞcall/cc
言語実装者やライブラリ実装者にとっては厄介でしかない（と、僕は思っている）、そしてユーザから見ても使いどころがわからない（と、僕は思っている）。
それがcall/cc。
ですが今回のように、プログラムの環境を保存しておいて大域脱出、その後もとの位置に復帰して実行を継続する。こういったことをしようと思ったときにはcall/ccがあってよかったと思います。
そんなわけで一時中断と復帰してからの継続にはcall/ccを使っています。おかげでかなり簡単に実装することが出来ました。


機能一覧
続いてこのスクリプトが行えることを説明したいと思います。
  • breakで実行を止めることができる
  • 停止中にstep, next, continueができる
  • 停止中の環境で式を評価できる(watch)
    • ただし手抜きをしているのでset!による破壊的代入後の値を参照できません。
  • ステップアウトはできない
  • バックトレースを出力できない
  • いろいろできない
    • 正直、時間がたらんかった。実装適当。テストも適当。
こんな感じです。
breakによる停止とstep等の順次実行はもちろんできます。ですが一度関数内にステップインしてしまったら最後。ステップアウトが出来ないため、順次実行していき関数から抜ける必要があります。
停止した位置のローカルフレームを保持しているため、watchができます。これはがんばった点ですが、プログラム内でset!された場合は上書きした値を参照できません。片手落ちですね。


最後にこのスクリプトを実行する方法を説明します。
ya-readディレクトリのルートで以下のコマンドを実行してください

gosh -I src/ src/debug.scm step.scm

最後のstep.scmはステップ実行の対象にしたいスクリプトです。
step.scmの内容は以下の様なものです。

好きなファイルを指定すればステップ実行ができると思います（本当に思うだけで、落ちる可能性も大いにあります)。
起動に少し時間がかかりますが、しばらくすると警告がいくつか出た後にgdb> というプロンプトが表示されコマンド入力が可能になります。
それではstep.scmを引数に渡した場合の、ステップ実行の操作例を紹介します。
ちなみに;以降はコマンドを説明するためのコメントです。実際には出力されません。

gdb> run
gdb> break 4      ;step.scmの4行目add関数内の(print "before"の出力前)で一時停止するように指定しています
gdb> exec (add 2) ;exec eでeを評価することが出来ます。今回はstep.scm内のadd関数にを評価します。
gdb> stop: /hoge/huga/ya-read/step.scm:4    ;step.scmの4行目で一時停止した、というメッセージが出力されます。
gdb> next    ;nextコマンドで、同一関数内の次の行へ移ります。
gdb> before  ;beforeはstep.scmのプログラムによって出力された内容です。
stop: /hoge/huga/ya-read/step.scm:5
gdb> next    ;nextの代わりにstepを実行するとstring-split関数にステップインできます。(先述のとおりステップアウトできないので覚悟してください)
gdb> (hoge huga)
stop: /hoge/huga/ya-read/step.scm:7
gdb> print (+ a b c)    ;7行目の実行時環境内で(+ a b c)を評価して、その結果を表示します。
gdb> 10      ;print (+ a b c)の結果が表示されます。
gdb> step    ;stepコマンドでmul関数内に入ります。
gdb> stop: /hoge/huga/ya-read/step.scm:11
gdb> step
gdb> 13
stop: /hoge/huga/ya-read/step.scm:8
gdb> next
gdb> after

書いた本人が言うのもあれですが、かなりごちゃっとしていてわかりにくい説明ですね。
ごめんなさい。


こんな中途半端なステップ実行機能ですが、
言語自体による特別なサポートがなくてもread時の式操作とcall/ccがあればここまでデキルんだぜ(どやぁ）
というのが書きたかっただけです。
なのでこれ以上進展させるつもりはありません。


おわりに

最初に書いたとおり、かなり内容が長くなってしまいました。
単にリーダーマクロを導入するだけの予定でしたが、好き勝手いじることができるread関数を手に入れてしまうと、なかなか夢が広がりますね。
単にプログラムを実行するだけでは足りない人はマクロを利用しますが、それでも足りない場合はリーダーマクロやread時フックです。
まぁ強力な分、実際に書いたプログラムとはかけ離れた形としてreadされてしまう可能性があるため、デバッグがさらにさらに複雑になってしまうんですけど。
そんなこともLISPならではということで、LISPerの皆さんなら楽しむことができますよね？