"アプリケーションのビルド"をSDKとして抽象化できるのか問題

nmosh

追記: Racket 7は--embed-dllsで完全にstandaloneな.exeを生成できるようになった https://blog.racket-lang.org/2018/07/racket-v7-0.html
実は意外に多くのScheme処理系が単体アプリケーションのビルドを機能としてサポートしている。
Gaucheは最新リリースの0.9.6でbuild-standaloneユーティリティ( http://practical-scheme.net/gauche/man/gauche-refe/Building-standalone-executables.html#Building-standalone-executables )を提供し、スクリプトとライブラリを文字列の形で取り込んだexecutableを作ることができる。ツールは(まだ実験的な)precomp( https://github.com/shirok/Gauche/blob/master/doc/HOWTO-precompile.txt )を活用しない。build-standaloneはSchemeソースコードをC文字列に変換し、簡単なmainスタブとともにコンパイルすることでアプリケーションをビルドする。コンパイラはgauche-config --ccのものがそのまま使用される。
ChezSchemeはmake-boot-file手続きでbootファイルを作り、それとバンドルされているstatic library形式の処理系を組み合わせて単体アプリに仕立てることができる。解説( http://cisco.github.io/ChezScheme/csug9.4/use.html#./use:h8 )は商用版の名残りでpetit chez schemeを使っているが、同じことはコンパイラ入りの完全版でも可能なはず。これと言ったフロントエンドの類いは用意されていない、つまり、ユーザは自分でCコードを書く必要がある。
Guileは元々Extension languageとして作られたので当然ライブラリ(libguile)を提供し、ドキュメントも存在する場合はC APIとScheme APIを常に併記している。が、逆、つまりSchemeで書かれたアプリケーションを配布するためにアーカイブする仕組みは備えていない。一応バイトコードコンパイラを直接呼ぶことはできる( https://www.gnu.org/software/guile/manual/html_node/Compilation.html )が、バイトコードを直接ロードする良い方法は無い。...じゃぁ相当量のコードがGuileで実装されているLilypondのようなアプリケーションはどうしてんのかというと、システムにインストールされているlibguileに直接依存する形を取っている。
RacketはたぶんScheme処理系では最も考察が進んでいて、パッケージングツールであるracoがライブラリを含め単体実行ファイルを生成するraco distribute( https://docs.racket-lang.org/raco/exe-dist.html )を持っている。実際の実行ファイルを生成するraco exeコマンド( https://docs.racket-lang.org/raco/exe.html )はテンプレートになる.exeやmacOSアプリケーションのアイコンの差し替えまでサポートしている(UNIXでは単にテンプレートとなるexecutableのコピーになる)。更に、静的ライブラリも同時に提供し、アプリケーションへの組込みも可能になっている( https://docs.racket-lang.org/inside/embedding.html )。

最小公約数としての静的ライブラリ提供

というわけで、Gauche、ChezScheme、Racketは静的ライブラリとして処理系を配布しており、バイトコード化した(または、C文字列化した)プログラムを起動するための簡便なインターフェースを持っていると言える。なので、yuniのSDKとして何か提供するとするならば、

  1. 各処理系向けの簡単なmain()関数
  2. 各処理系でのバイトコードコンパイラやライブラリパッケージャを呼ぶCMakeモジュール

端的に言うとChezSchemeの方式が基準になる。GacuheはCコードの生成、Racketはカスタマイズされた.exeの生成までサービスしているが、アプリケーションに追加の静的リンクライブラリをリンクしたいケース等を考えると、C側のmain()の準備とアプリケーションのリンクは自前でやってしまった方が融通が効くような気がしている。
... 処理系を静的リンクライブラリで配るのか動的リンクライブラリで配るのかはちょっと悩ましい問題で、どちらもpros/consが有る。WindowsやmacOSのように、実行ファイルがPIC(位置独立コード)であることが前提のプラットフォームであれば、静的リンクライブラリで配ってしまって利用者に委ねる方式も取れなくはないが。。特にWindowsの場合、処理系をビルドするのに使用したC言語ランタイムがMinGWなのかMSなのかという問題まであるため、動的リンクライブラリのメリットもそれなりに有ると言える。
yuniが他と比べて特殊なのは、yuniを使うアプリは殆どがネイティブコードを含んでいるという事実で、どうしてもアプリケーションのビルドには追加のビルドツールの存在を想定することになる。このため、ネイティブコード側の処理をScheme処理系に任せたいモチベーションがあまり無い。
Guileのような処理系や、Gambit、ChickenのようなSchemeコンパイラでも同じような方針で単体executableの生成は実装できる。ただGuileのような方式、つまりシステムに処理系をインストールしなければならない方式では、アプリケーションを単体で配布することができない - が、そもそもGuileはWindowsでよく動作しないのであまり大きな問題では無いはず。

hashtablesとserializeライブラリ

nmosh

久々にyuniに新しいライブラリを足すことにした。どちらも他所でライブラリにしていたけどyuni本体に有った方が何かと便利なんじゃないかということで移動。

hashtables

yuniは基本的に"R7RS smallにあるものはR7RS、そうでなくてR6RSにあるものはR6RS"という方針で選択している。というわけでhashtablesはR6RSベース。
また、R6RSのものを更にサブセットしている:

  • ハッシュ関数は無し。
  • インスペクションは無し。つまり、ハッシュ関数やequality手続きを既存のハッシュテーブルから取り出すことはできない。
  • キーの型限定hashtablesを提供する。integer / string / symbol の3種。

この限定はScheme処理系を既存のインタプリタ言語で実装するケースを想定していて、integerやstringに関しては、それぞれのホスト言語ネイティブのハッシュテーブルを活用できる可能性があることから。
hashtableかhash-tableかは微妙なポイントで、SRFI-125ではhash-tableを推しているが( https://srfi.schemers.org/srfi-125/srfi-125.html )、yuniではプリミティブオブジェクトは1単語原則でhashtableにした。(e.g. byte-vectorでなくbytevector)
実はオブジェクトのハッシュは言語上に言語を載せる場合には良く実装できない可能性があり、可能な限り型付きのハッシュテーブルを想定した方が移植性は高くなる。ハッシュ関数は普通に使えても良いかもしれないが、移植性の問題と、eq/eqvに関しては再現性の問題がある(eq? の成立するオブジェクトに異なるハッシュ値を振る可能性がある)ため実はあんまり役に立たない。R6RSのRationaleでは:

The make-eq-hashtable and make-eqv-hashtable constructors are designed to hide their hash function. This allows implementations to use the machine address of an object as its hash value, rehashing parts of the table as necessary if a garbage collector moves objects to different addresses.

serialize

serializeライブラリは要するにFASLだが、"バイナリ形式のwrite/read"という位置付けとなる。API名は良いものが全く浮ばない。。いっそのこと fasl-read とか fasl-write にしてしまった方が良いかもしれない。。
オブジェクトのシリアライズ機能は処理系によってマチマチで、GambitやChezScheme等のようにちゃんとFASLとして使用できるものもあれば、そもそもシリアライズ機能自体を提供していない処理系もある。
最低でも、全てのread-write invariantなオブジェクトは正常にシリアライズできるという要求で良いと考えているが、問題は"writeできないがシリアライズはできた方が良いもの"をどうするかという問題だろう。
chibi-scheme、chicken、Gauche、Guile、Sagittarius などにはシリアライズの直接的なサポートはない。これらでは自前のWriter/Readerで対応することになる。

... 今見てみるとyuniのターゲット処理系でネイティブのFASLを持つ処理系って3つしか無いのか。。
これらのネイティブサポートは、一般にread/write invariantであるものの他に、ハッシュテーブルやrecordの入出力も可能となっている。ただし、yuniではハッシュテーブルの入出力は上記のinteger/symbol/stringの3種に限定しようとしている。固有のハッシュ関数やequality手続きを持ったハッシュテーブルを入出力するためには、これらの手続きもシリアライズする必要があるが、クロージャのシリアライズは処理系のサポートが無いと困難なため。
ネィティブサポートの無い処理系の扱いは悩みどころだが、とりあえずScheme側の実装でどの程度のパフォーマンスになるかを見たいところ。おそらく殆どのケースで、テキスト形式のread/writeには勝てないのではないだろうか。
...じゃぁシリアライズなんて要らないじゃんということになりそうだが、

  1. read/writeだとyuniのプログラムでは頻出するbytevectorのI/Oに使えない
  2. 大きなデータセットを繰り返し処理するようなケースで必要になる - 今のユースケースだとFASL形式で100MiB 〜 500MiB程度のデータを処理しているのでテキスト形式に落してしまうとI/Oオーバヘッドが大きくなってしまう。(Twitterに挙げたgccのログデータセットは、インデックス処理後でも500MiBを超えるくらい https://twitter.com/okuoku/status/1018833935797645312 )
  3. スレッド非サポートの処理系では、並列処理時に結果を受け取る際に使用する。

というあたりで、個人的にはyuniのような位置付けのライブラリにはどうしても必要なんじゃないかと考えている。

BiwaSchemeで同期I/Oもしたい

nmosh

ゲームの細かいデータハンドリングはSchemeで書いているので、Webアプリ側でも同じロジックを使いたい。というわけでBiwaSchemeにyuniを適当に移植した。で、適当に移植してみると、やっぱり普通のScheme処理系としても使えた方が便利...というわけでbytevectorや同期ファイルI/Oのような欠けている機能もyuniで使っているものは一通り実装した。
BiwaSchemeへのupstreamも意識して機能は基本的にJavaScript側に実装している。
非常に悩ましいのはJavaScriptは文字列がimmutableなため、R7RSで標準となっているmutable-stringsが実装できない点。専用の文字列ハンドルを導入して無理矢理実現するか、そもそも健全なプログラムはmutable-stringsを使うことは無いので実装しないかが悩みどころ。個人的にもmutable-stringsは殆ど使わない。
bytevectorはUint8Arrayで実装した( https://github.com/okuoku/biwasyuni/blob/5e93dc14f9901e0e20b90c56f4e037526f29b1d8/biwasyuni.js#L309 )。同期I/Oはどうせnode.jsでしか使わないのでBufferで良いような気もするが。。yuniではbytevectorのreadは必須でない(R6RSとR7RSで構文が違うので移植性が無い)ため、reader側はサポートを入れていない。
バイナリポートはget_bytes_at(bytevector指定箇所への読み取り)とget_bytes_all(内容全部の読み取り)を拡張している(https://github.com/okuoku/biwasyuni/blob/5e93dc14f9901e0e20b90c56f4e037526f29b1d8/biwasyuni.js#L137 )。openだけはyuniの側でScheme実装としている( https://github.com/okuoku/yuni/blob/7726eb4a0126c9585806160321f9e629e2a1ce2b/lib-runtime/biwascheme/prelib.scm#L12 )。これはbrowserfsがnode.jsと同じようなfsインターフェースをIndexedDBのようなブラウザ上のストレージに対して提供しているため、(current-port等と同じような感じで、)current-fsをオーバーライド可能にした方が良いかなという気がしていることに因る。
いくつかのBiwaScheme標準手続きはoverrideしている。例えばR6RSからR7RSで拡張されたstring-copy等の手続きはr6:string-copyにリネームしてyuniの標準ライブラリ側でR7RS版を実装した。また、yuniではloadは常にPauseを返し最終結果でresumeを呼ぶように修正している。

biwas.define_libfunc("load", 1, 1, function(ar){
    // Override: (load fn)
    // NB: Override load because we may return a Pause on load'ed code.
    // FIXME: Parhaps it's same for scheme-eval...
    var pth = ar[0];
    var src = fs.readFileSync(pth, "utf8"); // FIXME: Make this async.
    return new biwas.Pause(function(pause){
        var interp2 = new biwas.Interpreter(interp, this.on_error);
        interp2.evaluate(src, pause.resume);
    });
});

標準のloadは手続きがPauseを返すことを想定していないため、loadしたスクリプトがPauseを返すと異常な挙動になってしまう。このようにすることで、browserfs等を使ってブラウザ上でもファイルのload等をローカルストレージから実施できるように拡張できる可能性がある。PauseオブジェクトはBiwaSchemeの便利な機能で、継続をwrapしたJavaScriptオブジェクトとしてPauseオブジェクトを生成でき、手続きから返すことでVMの実行を一時中断できる。これによりJavaScript界ではよくある、コールバック駆動の非同期処理を同期処理のように記述することができる。

Isomorphic プログラム環境として実は有望なのではないか

yuniにとって、BiwaSchemeはs7に続く2つめのGeneric runtime処理系となっている。というわけで、yuniのランタイムをロードした状態であれば、擬似的なSyntax-rules( http://d.hatena.ne.jp/mjt/20180521/p1 )やyuniのR6RS-liteライブラリ機構を使えるので、BiwaSchemeと他のScheme処理系で同じように動作するプログラムを容易に組むことができる。(まだFFIが無いので現状実用的でもないが)
Scheme環境の他所に無い特徴として、Gambitのような実用的かつ静的な最適化コンパイラの存在がある。ランタイムサイズを極限まで絞った環境と同じコードがJavaScriptやJavaでも動作するので、今までに無いIsomorphicアプリケーションが考えられるかもしれない。

各種オーディオエンジンの調査

audio teslawire

ゲームで使うオーディオエンジンのポータビリティを高めるために、WebAudioのCバインディングを考えて、その移植レイヤを各種オーディオエンジンに対して実装するのが良いような気がしている。
...というよりは、固定機能で実現されることが多いOpenALのオーディオエフェクトと、BiquadFilterとかIIRFilterのようなフィルタプリミティブだけを提供するWebAudioではどうやってもセマンティクスが合わないので、どちらに合わせるかというのが単に問題になる。Emscriptenのように、WebAudioをOpenALでwrapし、OpenALを移植層として使う方が簡単かもしれないが、如何せんOpenAL自体があまりメジャー実装に恵まれていない。。
特に近年のVRの流行でオーディオエンジンもリバーブのbakeや、シーンのジオメトリ表現によるオーディオポータルの生成といった専用ゲームエンジンにあるような機能を提供しつつあり、これらを良く抽象化するAPIデザインはなかなか難しい。

LabSound

LabSoundはChromiumのWebAudio実装を抜き出してC++ライブラリにしたもので、機能性としてはWebAudioのものとほぼ同一になっている。グラフの構築はAudioContextを使用して行うためどちらかと言うと用法はOpenALに近い。拡張機能としてPureDataとリンクするためのPdNode等が追加されている。
ライセンスはBSD2で、当初はこれをwrapしてOpenAL実装にできないか検討していた。

Google Resonance Audio

GoogleのResonance AudioはWebやAndroidを含めた各種環境向けの空間オーディオSDKで、Ambisonicsを中心に据えたデザインになっている。OpenALではBlueRippleの実装が同様のデザインを持ち、OpenAL Softも近いAmbisonics合成パスを最近実装している。
リバーブに関してはVRでは一般的になったshoeboxモデル(直方体の部屋を仮定し、部屋のサイズと壁材質に合わせたリバーブを設定するモデル)を採用している。またオープンソースのライブラリでは多分初めてリバーブのbakeに対応しており( https://developers.google.com/resonance-audio/develop/unity/developer-guide )、Unityのゲームシーンにprobeを配置することでAPIのパラメタ設定を行わせることができる。残響パラメタは一般的なRT60を採用。
公開APIにはなっていないものの、各種フィルタやグラフAPIが有り、WebAudio同様のフィルタを備えている。

Windows Sonic

Windows Sonicは最近のWindows 10やXboxで使用できる空間オーディオAPIで、Dolby Atmosのトランスポートをサポートする等外部/ハードウェアレンダラをサポートしているのが特徴。ただしXboxでハードウェアレンダリングした場合16オブジェクトに制約され、ソフトウェアレンダリングの場合のAPI制約も128オブジェクト(含bedチャンネル)となっている。
8.1.4.4のようなチャンネルフォーマットをサポートする一方、Ambisonicsをサポートしていない。Barcoはチャンネルベースオーディオを推すホワイトペーパーを以前出していて( http://d.hatena.ne.jp/mjt/20140504/p1 )Dolby Atmosと対決姿勢を見せていた一方、Dolbyに支持されたこのAPIがAmbisonicsをサポートしていないのはちょっと気になる傾向と言える。
Ambisonicsの非サポートに見られるように、Windows SonicのAPIセット自体はAtmosのようなレンダリングシステムとのインターフェースに特化していて、フィルタやリバーブ等の機能性を持たない。何を組み合わせるべきなのかは調査中。

Steam Audio

Steam Audio はValveに買収されたImpulsonicのオーディオSDKを無償化したもので環境のbakeやTrueAudioによる畳み込みオフロード等の高機能を誇る。特に無償のミドルウェアで直接的にTrueAudioをサポートしているのは珍しい気がする。Ambisonicの再生やHRTFレンダリングもサポートしているものの、フィルタやオシレータのような機能性は無く、どちらかというとOpenALに近い機能性と言える。
また、つい昨日リリースされたbeta14で、IntelのEmbreeレイトレーサ( http://embree.github.io/ )を使用したオーディオシミュレーションに対応している( https://steamcommunity.com/games/596420/announcements/detail/1674659226616741624 文中のphononはSteam Audioにおけるオーディオエンジンの名称)。
サイトはgithub.ioに有るもののオーディオエンジン部分のソースコードは公開されていない。バイナリはAndroid/Linux/OSX/Windows向けに提供。

Oculus Audio

ココで最初にとりあげた( http://d.hatena.ne.jp/mjt/20150308/p1 )際はネイティブAPIは公開されていなかったが、現在はC APIも公開されている。Ambisonicsの再生に対応しており、機能性は比較的普通。
同時発音数等をモニタするプロファイラ( https://developer.oculus.com/documentation/audiosdk/latest/concepts/audio-profiler-using/ )を提供している。Wwiseの統合ミドルウェアでは比較的よく見られる機能だが、単体のspatializerで提供されるのは比較的珍しい。

BiwaSchemeでWebアプリを書きたい

nmosh

BiwaSchemeでyuniのライブラリシステムを導入する目処が立ったので、BiwaSchemeを使ってWebアプリのロジック部分を書けないか検討することにした。
BiwaSchemeには組込みのjqueryサポートが存在するが、今回は(個人的によく使っているので)mithril.jsベースのSPAを前提として考えることにする。

組込み

今回はビルドシステムとしてParcelを使うことにした。設定ファイルの類はほぼ不要(yarnで適当に依存を足すだけ)、エントリポイントのHTMLは至極シンプルで、

<!doctype html>
<head lang="en">
    <link rel="stylesheet" href="index.scss">
</head>
<body>
    <script src="index.js"></script>
</body>

だけになる。index.jsがJavaScript側のエントリポイントになり、ここでBiwaScheme等をロードしている。

var m = require('./node_modules/mithril');
var biwas = require('./node_modules/biwascheme');
var bfs = require('./node_modules/browserfs');
var root = document.body;

m.render(root, "Hello."); // debug

Parcelのようなビルドシステムはコード内のrequire記述をパースし、依存関係を自動的に抽出する。

load相当処理の実装

Parcelで普通にビルドするとNode.js用のloadやdisplay実装が使われてしまうため、mithril.jsのXHR wrapperを使って適当にload相当の処理を実装する。

var errhook = function(e) { console.error(e); }
var biwa = new biwas.Interpreter(errhook);

m.request({
    method: "GET",
    url: "/check.scm",
    deserialize: function(v){return v;},
}).then(function(str){
    biwa.evaluate(str, function(res){m.render(root, res);});
});

ここでは、Schemeプログラム check.scm を / から読んでいる。Parcelのデフォルトでは dist ディレクトリがルートになるので、dist/check.scmにプログラムを置く必要がある。

js-invoke/async

BiwaSchemeは組込みでNode.jsのファイルシステムやjqueryのバインディングが付属してくるが、今回は他のアプリに合わせてBrowserfsやMithril.jsを採用するためそれらのバインディングを用意する必要がある。
基本的にはBiwaSchemeのドキュメントにあるようにJavaScript側でバインディングを書くことを想定しているように見えるが、コードの取り回しを考えるとJS側のコードを減らしScheme側の比重を高めたい。というわけで、コールバックを取る非同期APIのためのプリミティブとして js-invoke/async を用意してみた。
js-invoke/asyncは コールバックは引数の最後 を想定していて、非同期APIの呼び出し中はSchemeプログラムの実行をPauseし、コールバックが呼ばれるとSchemeコードの実行を再開する。js-invoke/asyncの返値はコールバックの引数そのものとなる。

// (js-invoke/async js-obj "method" args ...)
biwas.define_libfunc("js-invoke/async", 2, null, function(ar){
    var js_obj = ar.shift();
    var func_name = ar.shift(); // FIXME: Require underscorejs for isString??
    return new biwas.Pause(function(pause){
        var cb = function(){return pause.resume(arguments);};
        ar.push(cb);
        js_obj[func_name].apply(js_obj, ar);
    });
});

js-invoke/asyncを使ったSchemeコードは:

(define (object->string obj)
  (let ((p (open-output-string)))
   (write obj p)
   (get-output-string p)))
(define the-result 0)
(define x (js-closure (lambda (arg cb) (cb (+ arg 1))))) ;; myfuncの実体、引数1つとコールバックを受けとり1加算してcbに渡す 
(define theWindow (js-eval "window"))
(js-set! theWindow "myfunc" x)                           ;; 適当にwindow.myfunc() を登録
(set! the-result (js-invoke/async theWindow "myfunc" 2)) ;; myfuncの呼び出し (myfunc 2 cb)、cbはScheme側を実行再開
(set! the-result (object->string (car (js-array->list the-result))))
the-result ;; 先のload相当処理で、返値がWebブラウザ上に表示される

このコードをdist/check.scmに配置すると、結果として"#(3)"が表示される(3 = 2 + 1)。(ベクタになっているのは、JavaScript側のコールバックが多値を返すケースを想定しているため。コールバックの引数が2つ以上であれば、その分長いベクタが返ることになる。)

... これで任意のJavaScript非同期APIを同期手続きのように呼び出せるが、そもそもJavaScript(〜ES5)には末尾再帰最適化が無いので、どこかで継続を打ち切るように書かないとスタックが伸びつづけてヤバい気はする。これはBiwaScheme側の実装をチェックしてみる必要が有りそう。

未解決問題

BiwaSchemeはNodeとブラウザの両方で load のようなAPIをサポートしているが、yarn経由で適当にビルドした場合BiwaScheme側のpackage.jsonに従ってNodeの方が使われているようだ。今回はmithril.jsを組込む都合、jqueryバインディングは不要だし何らかの形でコンフィギュレーションを切れると良い気がするが。。たぶんコレに関してはnpm的に直接的な解法はなくて、biwascheme-coreパッケージと同-node、-browserパッケージを用意して分割するしか無いと思う。
js-invoke/asyncのインターフェースは悩みどころで、もうちょっと抽象化したSchemeフレンドリなAPIの方が好ましいかもしれない。
まだyuniのビルドシステムとParcelを繋ぐ良い方法を思いついていない。たぶんParcelのプラグインとして書くのが良いと思うが、ParcelのCLIから使うためにはnpmパッケージとしてpublishしないとダメなんではなかろうか。。

Scheme雑記

nmosh

なんか今週schemeトピック多くない？

今週のyuni/yunibase

処理系ブリッジフレームワークであるところのyuniではs7( https://ccrma.stanford.edu/software/snd/snd/s7.html )をサポートしてみた。yuniffi等もそのうち入れる予定。
yuniでサポートしている処理系は特に理由が無い限りyunibaseにも収録することにしているのでs7も収録したけど、急にMUSL libcでビルドできなくなり( https://github.com/okuoku/yunibase/issues/62 )この息の長い処理系がアクティブに開発されていることを示した。s7というかその上位プロジェクトのsndはコミットログがすごい https://github.com/spurious/snd-mirror/commits/master 。
yuniはR7RS処理系を基本に置いていて、R6RS処理系は互換層を挟んで対応している。その互換層の一部がR6RSのパッケージマネージャであるAkkuに収録された https://gitlab.com/akkuscm/akku-r7rs 。AkkuはR6RS処理系向けのパッケージマネージャだが、R7RSライブラリの取り込みをサポートするつもりのようだ。
yuniではs7の次はBiwaSchemeのサポートを目指しているけどBiwaSchemeのdefine-macroはレキシカルスコープされないのでlet-syntaxがサポートできず、どうしたもんか考え中。(既にBiwaSchemeにはsyntax-caseの開発ブランチが有るので、あんまりBiwaScheme側を改造する方向でのサポートはやりたくない。) まだライブラリのimportが動作していないが、yuniのテストで見つかった問題を直してPRした( https://github.com/biwascheme/biwascheme/pull/120 )。

唐突にSTklosがリリースされる

先週突然STklosがリリースされた。

STklosはGaucheのCLOS風オブジェクトシステムの始祖に相当する処理系で、名前が示唆する通りGUI開発の考察が有り、独自のパッケージシステムScmPkgを持つ。
...yuniは一応FFIがありアクティブに開発されているScheme処理系はみんなサポートするつもりなので隙を見てサポートしたい。。

唐突にmit-schemeのFFIが1.0になる

突然mit-schemeのFFIが1.0になった http://git.savannah.gnu.org/cgit/mit-scheme.git/commit/?id=c851b8c5100ad7a2b54c753728609fe7be5019ea 。
MIT/GNU Schemeは、それこそザ・Scheme処理系で、最近はbytevectorが実装され http://d.hatena.ne.jp/mjt/20170227/p1 、過去にあったFFIでバッファを表現できなかった問題 http://d.hatena.ne.jp/mjt/20160913/p1 などが解消している。
忙しくて開発を追い切れていないが、あとはsyntax-rulesがR7RS仕様になればyuniとしてはネイティブサポートと言っても良い状況ではないかと思う。(今はAlexpanderを使って事前にexpandしたプログラムを実行させる方式での対応としている。このような処理系はMIT-SchemeとGambitだけで、Gambitは今のs7サポート同様libraryをマクロとして定義する方式に代える予定。)
他にもChicken-r7rsがChicken 5向けのコミットをpushする等、歴史のある処理系の動きが目立った週になった気がする。

CMakeをSchemeにする -- S式のtokenize

nmosh

意外な伏兵。。
CMakeはそれなりに高速なスクリプティング機能が有るため、やる気になればそれなりに実用的なScheme処理系にできるんじゃないかという気がしている。が、適当にやったらやっぱり遅かったのである程度は真面目にやる必要がありそうだ。

適当な実装

S式をtokenizeするには、適当な状態遷移マシンを用意して1文字づつ処理すればできる。 ...できるんだけど超遅い。以下、yuniの簡易テストコード https://github.com/okuoku/yuni/blob/cce309e917efbb7e0787e5bed7dd040996f9e452/_sanity.sps を読むのに掛かった時間で比較する。
素朴な実装はこういう感じになる: https://gist.github.com/okuoku/6a1a4ea859735cdc19779db3314bb63d

string(SUBSTRING "${${ctx}_buf}" ${${ctx}_cur} 1 __input)
...
if(("${__input}" STREQUAL " ")
           OR ("${__input}" STREQUAL "\r")
           OR ("${__input}" STREQUAL "\n")
           OR ("${__input}" STREQUAL "\t")
           OR ("${__input}" STREQUAL "\"")
           OR ("${__input}" STREQUAL ";")
           OR ("${__input}" STREQUAL "(")
           OR ("${__input}" STREQUAL ")")

つまり、単に1文字をSUBSTRINGによって取り出し、それを文字列比較で比較していけば良い。(CMakeのSUBSTRINGはSchemeと違って第二引数として長さを取る。)
が、これが超遅い。

oku@stripe ~/repos/dryscheme-cmake
$ time cmake -P check.cmake > /dev/null

real    0m7.699s
user    0m7.671s
sys     0m0.015s

意外なことに、ORの部分を正規表現に置き換えると速度が向上する。

oku@stripe ~/repos/dryscheme-cmake
$ time cmake -P check.cmake > /dev/null

real    0m5.849s
user    0m5.718s
sys     0m0.031s

つまり、正規表現の破棄/生成コストよりも、ORの連鎖を処理するコストの方が高いと言える。高速なCMakeスクリプトを書きたければ行数を減らすしかない。

tokenを正規表現で引く実装

正規表現のコストが文字列比較並に安いのならば、正規表現を使った方が良いに決まっているので、正規表現でtokenを引く実装が考えられる: https://gist.github.com/okuoku/2beb787118d0cff574bdc817d4c547ac

        elseif("${${ctx}_buf}" MATCHES "^(\\(|\\)|\\[\\]|'|`|#vu8|#u8|,@|,|#f|#t|#\;|#\\\\[a-z]+)(.*)")

CMakeはifコマンドに正規表現マッチ機能が有り、サブマッチを変数にバインドして直接アクセスできる。これを使用することで、tokenの抽出を行うことができ、tokenizer自体もまずまずコンパクトに書くことができる。速度の方もそれなりに改善して、

oku@stripe ~/repos/dryscheme-cmake
$ time cmake -P check.cmake > /dev/null

real    0m1.802s
user    0m1.781s
sys     0m0.015s

半分以下のコストで処理できるようになった。
...が、高々11KiB程度のコードを読むのに2秒掛かるのはちょっと。。

REGEXP MATCHALLで一気にトークンに分割する方法

たぶん文字列をちょっとづつ読むというのが構造的に重い(文字列の確保と解放を繰り返すことになる)。というわけで、処理を2パスに分割し、tokenはstring(REGEXP MATCHALL)を使用して一気にCMakeのリストに変換できるように考える。
REGEXP MATCHALLをコードに適用する前に、以下の変換を行う:

  1. ソース中のセミコロンをescapeする。CMakeのリストは単に文字列をセミコロンで区切ったものであるため、リストの内容にセミコロンを含めたいときは適当に処理する必要がある。個人的には、printableでない適当な文字に置き換える方法をよく採用している(手抜き)。
  2. 文字列中のdouble quoteを事前にエスケープする。
  3. SRFI-30 ネスト化コメント( https://srfi.schemers.org/srfi-30/srfi-30.html )を削除する。CMakeの正規表現にはlazy matchが無いため、ネストされたコメントにマッチさせることはできない(はず)。
  4. 通常のセミコロン行コメントを削除する。

このうち、後段のdouble quoteのエスケープ置き換えと、ネスト化コメントの削除は単一パスで実行できる。また、セミコロンやダブルクォートの変換が入ってしまうので文字定数は事前に処理する必要がある。
この前処理を実施することでトークンは単一の正規表現で表現でき、stringコマンドのREGEXP MATCHALLによってリストに変換することができる: https://gist.github.com/okuoku/7fd831c53b9bf7e970fad5bbb4301985

function(yuni_sexp_tokenize out str)
    yuni_sexp_tokenize_preprocess(prep fil)
    string(REGEX MATCHALL 
        "\"[^\"]*\"|#vu8|#u8|#t|#f|#\\[a-z]*|#\\.|#|,@|,|[()`']|[^ \r\n\t()`']+|[ \r\n\t]+"
        lis
        "${prep}")
    set(${out} "${lis}" PARENT_SCOPE)
endfunction()

これは上2つの1トークンづつマッチしていく手法よりも圧倒的に速い。

oku@stripe ~/repos/dryscheme-cmake
$ time cmake -P check.cmake >/dev/null

real    0m0.121s
user    0m0.093s
sys     0m0.015s

100ms程度ならまぁ許容できる速度だと思う。ただし、この方法だとトークンの行番号とか桁位置が取れないという問題がある。

次の一手

次はヒープとGCの実現を考える。
CMakeはシェルスクリプトやawk、tclと同様に全ての変数は文字列となっていて型が存在しない。このため、変数は型アノテーションを行う必要がある。また、CMakeのリストは単にセミコロンで区切られた文字列でしかないため、リストやベクタの表現にも直接使うことはできない(セミコロンを含んだ文字列を保持すると、そこでリストが分割されてしまう)。
その辺のScheme処理系と同様に、CMakeは一度internした変数シンボルを解放する手段は存在しないため、GCによって領域を回収するには変数をfunctionなりなんなりでスコープする必要がある。