本記事は言語実装 Advent Calendar 2016の最終日の記事です。話題が多岐に渡っていて楽しいアドベントカレンダーでしたね。前日はEgisonのリーマン幾何学用記法の話でした。

BiwaSchemeは筆者が作っているJavaScriptによるScheme実装です。先月の話ですが、list-sortという関数を修正し、比較に使うScheme関数を受け取れるように改善しました。BiwaSchemeは中間言語方式(VM方式)かつライブラリを全てJSで実装するという方針になっているため、実装に少し工夫が必要でした。本稿ではそのことについて解説します。

中間言語方式

JavaScriptでScheme処理系を実装する場合、いくつかの方針が考えられます。

1. インタプリタ方式 (S式を一つずつ読み、評価する)
2. コンパイラ方式 (プログラム全体を等価なJavaScriptに変換する
3. 中間言語方式 (プログラムを中間言語に変換し、それを実行するもの(=VM)を用意する)

BiwaSchemeは3.の中間言語方式で実装されています。現代では2.のコンパイラ方式でも十分な速度が出ると思いますが、開発を始めた2008年当時はJavaScriptの処理性能が今ほど良くなかったため、VM方式のほうが性能的メリットがありました。あとは参考にした論文(3imp)がそうなっていたからという理由もあります。

例えば(+ 1 2)というSchemeプログラムは、以下のような中間言語(IL, Intermediate Language)にコンパイルされます。

[frame
   [constant 2
   [argument
   [constant 1
   [argument
   [constant 2
   [argument
   [refer-global "+"
   [apply]]]]]]]]
[halt]]

どのようなILが生成されるかはbiwascheme.orgからオンラインで確認できます。各命令の説明はここです。

ライブラリ関数の呼び出し

上記のようなIL列をループでぐるぐる回して、各命令を順番に実行していくというのがVMの基本的な動作です。しかし場合によっては、命令の実行中に生のJavaScript関数を実行することもあります。

例えばBiwaSchemeではライブラリ関数(上記で言えば、+)は全てJavaScriptで実装しているので、(+ 1 2)というプログラムを実行する場合、足し算を行うところだけJavaScriptの関数が走ります。

JS側からSchemeのコードを実行したい場合

上図はVMループから生のJavaScript関数を呼び出す例でしたが、場合によってはライブラリ関数からさらにScheme関数を実行したいことがあります。例えば(map f '(1 2 3))ようにしてリストをmapする場合、ライブラリ関数mapの中からSchemeの関数fを呼ぶことになります。

さてこれをどのように実装したら良いでしょうか？例えばfを実行するためにVMループをもう一つ起動するのはどうでしょうか。この方法は単純ですが、長いリストをmapするとVMループがどんどん増えていってしまうという問題があります。

BiwaSchemeではこのような場合、ライブラリ関数から特殊な値(BiwaScheme.Callのインスタンス)を返します。Callオブジェクトはライブラリ関数からVMループに向けて「このScheme関数をこの引数で呼んでほしい」という依頼を示すもので、以下のものが入っています。

• proc: 呼び出したいScheme関数
• args: 呼び出し時の引数
• after: 呼び出し後に実行するJavaScript関数

after関数は、Scheme関数の呼び出し後に何らかの処理が必要な場合に使います。例えばmapの場合は全ての要素を処理するまで繰り返しScheme関数を呼び出す必要があるので、Callを返す→afterが呼ばれる→Callを返す→…という感じでループしていくことになります(下図)。

CPS(継続渡し形式)

CPSという言葉を使えば、ここまでの話は要するに「BiwaSchemeのmapはCPS形式で実装されている」と言えます。CPS(Continuation Passing Style, 継続渡し形式)は「残りの計算」を関数として持ち回る形式です。mapの場合はCallオブジェクトのafterによって残りの計算を渡しています。

list-sort

mapの他にもvector-map, for-each, findなど、たくさんのライブラリ関数がCallオブジェクトを使って実装されています。ところが、R6RSのライブラリ関数の中にCallオブジェクトでは実装しづらいものがありました。それがlist-sort(およびvector-sort, vector-sort!)です。

list-sortはリストと比較関数を受け取り、安定ソートした結果を返します。これをCallオブジェクトで実装するには、何らかのソートアルゴリズムをCPSで実装する必要があります。mapの場合は要素を順番にScheme関数に渡すだけなので簡単ですが、ソートとなるとソート途中の状態を保持したまま適切にCallオブジェクトを呼び出す必要があります。

これを解決する方法として、頑張るという方法があります。ソートのアルゴリズムには有名なものがいくつかありますが、クイックソートは最悪計算量が良くない、ヒープソートは安定ソートでないという特徴があるので今回はマージソートを選択しました。マージソートは再帰的なアルゴリズムなのでCPSにするのは大変ですが、頑張ることによって実装ができます。できたものが以下です。

• https://github.com/biwascheme/biwascheme/blob/6c602b0d5fe0916c00d3f1b07f87d23e00c7a8b8/src/library/r6rs_lib.js#L1682-L1801

mergeSortがソートを行う関数で、mergeSort_およびmerge_は補助関数です。list-sort等はこのmergeSortを使って定義されています。

最初からCPSでソートを書くのは大変なので、まずは普通に再帰で書いたものを用意し、それをCPSに直すのが良いと思います。再帰の場合はホスト言語(BiwaSchemeの場合、JavaScript処理系)が関数の呼び出し履歴を管理してくれますが、CPSに直す際は処理系が持っていた状態を自分でハンドリングする必要があります。上記のコードではstackという変数がそれで、stack.pushが再帰の呼び出し、stack.popが再帰呼び出しからのreturnに対応しています。

おわりに

本稿ではlist-sortのためにCPSでマージソートを書いたという話をしました。話としてはそれだけなんですが、そこまでのコンテキストを補完すると長くなりますね。

ちなみにLisp処理系を実装する場合、ライブラリ関数もLispで書いてしまうという戦略も考えられます (というかそうする人の方が多いかも？)。この場合はlist-sortもLispで書くので今回のような苦労はないと思います。最低限必要な部分だけをホスト言語で書いて、ライブラリ等はその上に乗せるわけですね。BiwaSchemeの場合はそれをやるとランタイムがすごく大きくなるので避けていますが。