この記事は言語実装 Advent Calendar 2018の18日目の記事です。昨日の記事はC(のサブセット)コンパイラを書く上でハマった点：配列編 - hsjoihs’s diaryでした。

最近、BiwaScheme公式サイトのREPLでread関数が使えるようになったので、その解説をします。(read)は標準入力からS式を同期的に読み込むのですが、JavaScriptでキー入力を処理しようとすると必ず非同期処理になるので、readのようなものを実装するには工夫が必要です。

本稿ではaltjs¹上に同期的なsleepやreadを実装する方法について解説します。

altjsとsleep

説明の都合上、readより先にsleepの話をします。

BiwaSchemeは、私が開発しているJavaScriptで書かれたScheme処理系です。(Schemeは、Lispの一種です。) BiwaSchemeにはsleepという組み込み関数があり、例えば https://www.biwascheme.org で

(begin (print "a") (sleep 1) (print "b"))

というプログラムを入力すると、「a」が表示されてから1秒後に「b」が表示されます。

何が問題か？

JavaScriptには同期的にsleepするAPIがなく、sleepに相当する動作を直接表現することができないため、上記を実現する方法は自明ではありません。しいていえばwhile(1)でビジーループする、というのが近いですが、この方法はsleepが終わるまでブラウザが操作不能になってしまうという副作用があります。

ではaltjsでsleepを実装したい場合はどうすれば良いのでしょうか？答えは、altjs処理系がコンパイラ方式なのかインタプリタ方式なのかによります。あ、BiwaSchemeのようにVM方式の処理系もありますが、これは中間言語を処理するインタプリタと考えられるので、今回は後者に含みます。

インタプリタでsleepを実装する

インタプリタ方式のaltjsの場合、JavaScriptのsetTimeoutを使うことで比較的簡単にsleepを実現できます。例えば

処理A
sleep 1
処理B

のようなプログラムがあるとしたら、処理Aを行ったあとに setTimeout(function(){ ...処理Bの実行... }, 1000); とすれば、「処理Aの1秒後に処理Bを行う」という挙動を実現できます。

(ここで本当に実装したい人者向けに一点だけ補足しておきます。sleepを構文やVM命令として用意する場合はわりと簡単にいけると思いますが、そうではなくライブラリ関数の一つとして実装したい場合は少し工夫が必要です。というのはライブラリ関数の中でsetTimeoutしようと思っても、「処理B」を知らないとsetTimeoutできないですよね。ので例えばライブラリ関数に「残りの処理」をJS functionで渡してやるとか、ライブラリ関数がsleepしたいときは何か特殊な値を返すことにして、本体側はそれを受け取ったらsetTimeoutを行う、などする必要があります。BiwaSchemeは後者の方式で、BiwaScheme.Pauseというのがインタプリタの実行を一時停止したいという気持ちを表す特殊な値です。)

コンパイラでsleepを実装する

コンパイラ方式のaltjsの場合も考え方は同じで、

処理A
sleep 1
処理B

のようなプログラムを、

処理Aのコンパイル結果;
setTimeout(function(){
  処理Bのコンパイル結果;
}, 1000);

のように変換してやれば、「処理Aの1秒後に処理Bを行う」という挙動を実現できます。

…が、変換元言語の仕様によってはこれが難しい場合もあるかもしれません。例えばRubyにはKernel#sleepというメソッドがありますが、プログラム中の「sleep」がKernel#sleepの呼び出しであることを確実かつ静的に判定する方法は存在しません。このような場合は何らかの規約を設けるなど妥協する必要があるでしょう。

一方、中間表現にCPSを使うコンパイラだった場合はわりと簡単に実装できるでしょう。

stdinからのreadの実装

さて、本記事の主題はread関数でした。Schemeの(read)は、標準入力からS式を一つ読み込みます。ブラウザ上のJavaScriptには標準入力という概念はありませんが、https://www.biwascheme.org/ みたいにブラウザ上にREPLを実装する場合は、デスクトップで動かす場合と同じようなことができると良いですよね。

がしかし、ここでsleepの時と同じような問題が発生します。以下のようなプログラムがあったとしましょう(架空の言語です)。何か処理Aがあって、標準入力から1行読んで、それを使って処理Bを行う、という流れを考えます。

処理A
s = stdin.gets()
処理B

ブラウザ上のJavaScriptではユーザの入力を「同期的に」取得するようなことはできないので、keydownイベントとかを使ってイベントドリブンにやることになります。となるとユーザの入力を受け取る関数は、

getStringFromUser()     // 文字列を返す

ではなく、

getStringFromUser(function(s){
  ...
})

のようにコールバックを受け取る形をしているはずです。となると上記のstdin.getsを使った処理は、

処理A
getStringFromUser(function(s){
  処理B
});

のような形に変換しなければなりません。

…が、この形はsetTimeoutでsleepを実装したときと全く同じですよね？ということで、sleepが実装できたなら、それを応用して「標準入力」からの同期的な読み込みも実装できるようになります。

実際にBiwaSchemeでそれを行っている箇所を貼っておきます。Scheme(R6RS)の言語仕様のために「Port(input port)」という概念を経由していますが、根本的な考え方は同じです。

• readの定義
• BiwaScheme.Port.CustomInput
• node.js上でのcurrent_inputの定義
• 公式サイトREPL用のcurrent_inputの定義[^1]

[^1]: こんな短く書けるのかっこいいなと思う。使っているjQuery Terminalが賢い。ちなみにBiwaSchemeサイトのREPLはjQuery Terminalの作者本人が作ってくれたものである。

まとめ

本稿ではaltjsでsleepやreadを実装する方法について解説しました。実際に処理系を作るには説明不足な気がしますが、わからないところがあればtwitterででも聞いてください。

実際のところaltjsにsleepや同期的readが必要なのかというと微妙な気がしますが(実際BiwaSchemeにそれらがあるのも「かっこいいから」というだけの理由)、サーバサイドのコードをまるごと移植する必要が生じた場合とかに役立つかもしれません。少なくとも実現が不可能ではない、ということだけ知っておいておいたら良いかと思います。

追記1 (12/20)

• Q. こういう変なことをせずにsleepやreadを実装する方法はないでしょうか？
• A. setTimeoutやkeydownイベントを扱う機能を提供して、非同期処理でやってもらうことにするのが良いと思います。

追記2 (12/20)

iris (ISLisp in Go)のソースを見てて思い出したんですが、もう一個補足しておくべきことがありました。

上記のような「JSだと非同期になるものを同期的っぽく書けるAPI」を導入したことにより、BiwaSchemeでSchemeプログラムを実行する際は

var result = interpreter.evaluate("(+ 1 2)");

ではなく、

interpreter.evaluate("(+ 1 2)", function(result){
   // ...
});

のようにコールバックを使う必要があります。(細かいことをいうと、evaluateの返り値は「値またはPause」で、SchemeプログラムがPauseを使わなかった場合は実行結果が返るので、この例の場合は前者の書き方でも動きますが、Pauseを使う場合にも対応させるには後者の書き方が必要です。Pauseを使う関数はsleep以外にもhttp-requestなどがあります。)