BT

最新技術を追い求めるデベロッパのための情報コミュニティ

寄稿

Topics

地域を選ぶ

InfoQ ホームページ アーティクル コールバック不要:Javascript に逐次プログラミングを取り戻す StratifiedJS

コールバック不要:Javascript に逐次プログラミングを取り戻す StratifiedJS

ブックマーク

原文(投稿日:2010/12/19)へのリンク

Javascript は基本的にシングルスレッドであって,並列スレッドの概念を持っていません。実行時ブロックを伴う処理には非同期 (asynchronous) プログラミングが必須ですが,Javascript でのプログラミングには通常,大量のコールバック生成と処理の転送を伴います。これは開発者に対して,シーケンシャルなコードを継続渡し形式 (continuation passing style) に変換するための労力を強いることになります。

この問題に対するソリューションのひとつが,OSCON 2010 の Emerging Language Camp で紹介された StratifiedJS です。この言語の本質は,いくつかのキーワードとシーケンシャルなコードで記述可能な並列構造を追加した Javascript です。しかも現在のブラウザが持つ,ごく普通の Javascript エンジン上で動作するのです。

どうすればそんなことが可能なのでしょうか? InfoQ は Onilabs の CTO である Alexander Fritze 氏にその方法を聞きました。Onilabs はブラウザベースの StratifiedJS 実装であり,MIT ライセンスで無償公開されている Apollo をサポートしています。

InfoQ: StratifiedJS とは何でしょうか?

SJS は JS 言語の構造的コンカレントプログラミング (structured concurrent programming) 拡張です。並列的なコードパスを自然に扱うための構成要素 ( waitfor/and,waitfor/or,waitfor()/resume,hold,spawn,using ) をいくつか追加するとともに,ベースである JS 言語の構成要素 (シーケンス,ループ,条件文,例外など) を意味的に拡張しています。

ベース言語のセマンティクスには手を加えていません。従って JS プログラムを SJS でコンパイルしても期待どおりに動作します ( SJS のキーワードを変数名として使用しない,という不可避な制限はありますが ) 。

JS プログラマは SJS を使うことで,非同期処理コードを逐次実行的なスタイルで記述することができます。コールバックの迷路に混乱させられることなく,コントロールフローを自身のソースコードに直接書き下せるのです。

私たちは SJS と非同期プログラムの関係を,構造化プログラミング ( http://en.wikipedia.org/wiki/Structured_programming で説明されている意味で ) と GOTO プログラムスタイルの関係と同じように捉えています。

JS と SJS の違いを説明するならば,例えばノーマルな JS では,サーバからの応答を待機する XMLHttpRequest や setTimeout( ) コールなどの非同期なタスクには,アクションの完了時に起動されるコールバック関数を渡す必要があります。あるタスクが完了するまで,現在のコールスタックを同期的に停止させておく方法はありません (ブラウザ UI 全体がブロックされてしまうため)。

これに対して SJS では,すべての非同期処理は ( waitfor()/resume 構成を使用することで ) 同期的なブロッキング処理に変換可能です。変換した同期タスクは次のような JS 構文で利用します。
if (detectLanguage(document) != “en”)
  document = translateDocument(document);
detectLanguage() と translateDocument() は共に,特定のサーバ ( Google の翻訳サービスなど ) に対する非同期クエリを内部的に実行する関数です。

さらに SJS では,モジュール構造的な手法で複数の並列処理を統合するためのキーワードが追加されています ( 私たちはこれを ‘階層 (strata)’ と呼んでいます – ゆえに ‘階層化された (stratified)’ javascript,なのです)。 例えば Google と Yahhoo に対して同時にクエリを発行して,先に受信した応答を返すような処理を次のように記述できます。
var result;
waitfor {
  result = performGoogleQuery(query);
}
or {
  result = performYahooQuery(query);
}
この例では,単に最初の結果が到着した時点でリターンするだけでなく,ペンディング状態になっている要求を (SJS の try/retract 構文によって) 自動的にクリーンアップする処理も実行されます。具体的には,例えば Google の処理が完了した時点で Yahoo 側がメガバイト単位のデータを送信中である場合,処理結果が不要であると判明した時点で Yahoo との接続をクローズします。


InfoQ: Apollo は StratifiedJS コードを Javascript に変換して実行するランタイムのひとつです。Apollo は数多くのブラウザの JS エンジンで動作しますが,StratifiedJS のランタイムは他にもあるのでしょうか?

そう,Apollo はブラウザベースの SJS ランタイムなのです。Apollo は3つのピースで構成された,小さな JS ファイルです。SJS をその場 (on the fly) で JS に変換するコードトランスレータ,生成されたコードで使用されるランタイム,ネットワークを越えた SJS コードモジュールの同期的ロードを実現するモジュールシステム,この3つです。

その他のランタイムとしては,Apollo を node.js に移植する作業に取り組んでいるところです – これに関しては,近日中に私たちのブログ (http://onilabs.com/blog) 上でご報告できると思います。

他の言語の階層化 (stratify) の試みも計画しています。少なくとも C++ と Go については,すでに実現方法の検討が始まっています。

InfoQ: hold や sleep といった StratifiedJS のブロッキングコールは,Apollo ではどのように実装されているのでしょう?

Apollo の基本は,コールスタック管理のテイクオーバーにあります。非同期タスク完了時の実行再開位置を ‘記憶’ できるように,コードを書き換えているのです。ごく基本的なレベルでは,Apollo はコードの継続渡し変換を行います ( http://en.wikipedia.org/wiki/Continuation-passing_style の例を参照してください )。ただし SJS には例外や ‘キャンセル時復帰管理フロー’ ( 先述の Yahoo/Google の例で,Google からの復帰が早い場合にペンディング状態の Yahoo 要求がキャンセルされるように ) などの処理が必要なため,現実の実装はもう少し複雑になっています。

InfoQ: Apollo は JS エンジンの特別な機能,例えば WebWorker などが必要ですか? setTimeout や setInterval は使用していますか? そうであれば,どのように使われているのでしょう?

Apollo は,すべての一般的な JS エンジン上で動作します ( ただしテスト未実施のブラウザが,バグによって例外になる可能性はあります )。setTimeout は hold( ) でのみ使用しています。これ以外,SJS に必要な並列性機構は何もありません ( 後述の WebWorkers その他に関する詳細説明も参照してください )。

InfoQ: ブロッキングを回避するために,特別な階層化バージョンの API は必要はないのでしょうか? 階層化の不可能な,すなわち必ずブロックされる処理はありませんか?

JS の API はすべて,SJS でも修正なしで使用可能です。ただし非同期 (コールバック関数を取る) API については多少ラップコードを書いておくと,SJS のアドバンテージをフルに活用するのに役立ちます。非ブロッキングなものをすべてブロック処理にしておくためです ( つまり SJS では,すべての非同期処理を明示的にブロック化しておく必要があるのです) 。setTmeout( ) を例にすれば,次のようなブロックを伴う関数 pause( ) が記述できます。
function pause(t) {
  waitfor () { setTimeout(resume, t); }
}
SJS 内では以下のように使用します。
console.log('foo');
pause(1000);
console.log('bar');
この例では最初に ‘foo’ が,1秒後に ‘bar’ が表示されます。

InfoQ: StratifiedJS が採用,あるいは実装しているコンセプトはどのようなものでしょう?

SJS は当初,学術的領域で言うオーケストレーション言語 (orchestration language) を JS に導入する,小さな試みとして始まりました。特にテキサス大学オースティン校の ‘Orc calculus’ には強い影響を受けています ( http://orc.csres.utexas.edu/research.shtml 参照 )。

現在の SJS は,Orc とはあまり似ていないものになっているかも知れません ( 表現力の点で見れば,SJS のいくつかの機能 – try/retract など – は,Orc では記述困難だと思います)。それでもこの2言語には,並列性結合子の構築による並列プログラム記述の構造的手法の実装という,共通のアイデアが存在するのです。

InfoQ: Apollo にはどのような制約がありますか?

頻繁に上がっている問題としては,主に3つあります。

処理速度:Apollo の第1印象として,実行時 (on the fly) コンパイルが非常に重い処理なのではないか,という意見を多く受けます。しかし実際は十分に早く,通常の SJS スクリプトであれば,コンパイル時間はモバイルブラウザ上でも無視できるレベルです。( 例えば http://code.onilabs.com/0.9.1/demo/flickrcities.html 上の SJS コード (~ 100 行) のパースに要する時間は,2.4GHz Core 2 Duo の旧型 MacBook 上の Chrome で 3ms,私の持っている Android Phone でも 30ms 程度です。)

互換性:ユーザが所有している大量の既存コードに関する懸念があります。例えば,jquery や prototype などのライブラリには数多くのユーザがいますが,これらを SJS と混合して使用した場合はどうか,という不安です。
結論から言うと,これは問題にはなりません。第1の理由は,ほとんどの JS コードが SJS コードとしても有効であって,セマンティクス的にも変わりないからです ( ちょうど C と C++ のような状況です – ほとんどの C プログラムは C++ コンパイラでコンパイル可能で,実行結果も期待どおりになります )。 第2は,Apollo の生成するコードは通常の JS と完全な相互運用性があって,自在に組み合わせることができるからです。SJS からは任意の JS 関数を呼び出すことができますし,その逆も可能です ( ここで注意すべきなのは,ブロッキング SJS 関数を JS から呼び出した場合,継続オブジェクト (continuation object) が返されることです。JS では処理のブロックはできません – そもそもそれが,SJS を開発した理由なのですから)。

デバッグ: ‘ノーマルな’ JS 用に作成されたステップ実行デバッガは,SJS ではあまり役に立ちません。ただし私自身は,これは大した問題ではないと思っています。通常のデバッガはもともと,非同期コードでは役に立たないものだからです ( スタックトレースを取得しても,イベントの論理的シーケンスを反映していないため)。そうではありますが,私たちは現在,SJS 用の特別なデバッガを開発中です。すべてのステップにおいて,正常なスタックトレースとペンディング状態の完全な非同期依存性ツリーが表示可能になる予定です。

InfoQ: StratifiedJS で有効と思われる JS の追加機能には,どのようなものがありますか?イテレータ,コルーチン,Webワーカ (WebWorker),継続 (Continuation) などはどうでしょう?

イテレータやコルーチン,継続といった協調的マルチタスク機構は有効かも知れませんが,現時点では,SJS のセマンティクス全体をそれらにマップする方法が確立できていません。

‘本当の’ 並列性を実現する手段としての Web ワーカやスレッドなどに関して言うならば,SJS のような処理系の実装にこれらが有効である,という誤解が非常に多いのです。この件について明確にしてみましょう ( 話題が多少外れますが,ご容赦ください )。

ソフトウェア開発者が一般的に扱う並列性には,2つのまったく異なった側面があります。しかもこれらは,混同されていることが多いのです。

第1として,プログラムに対して意識的に並列性を「導入」したい場合があります。例えば,1つの CPU コアでの実行には時間のかかり過ぎるアルゴリズムがある場合など,ロードを複数のコアに分散しようと思うでしょう。あるいは,いくつかのコンピュータに処理を振り分けようとするかも知れません (map-reduce アーキテクチャのように)。スレッドや Web ワーカ,XMLHttpRequest などはすべて,このような明示的な並列性を導入するための仕組みなのです。

第2に,プログラムに並列性を導入したならば,何らかの方法でそれを調整し統制する必要が生じます。ことばを変えるならば,並列性を,一貫性を持ったひとつのストーリにまで “縮退” させる必要があるのです。並列性導入時に用いた仕組みは,ここではあまり役には立ちません。

SJS はまさしく,この2つの違いを浮き彫りにするのです。SJS のオペレータには ( hold( ) を除けば ) システムに並列性を導入するものはひとつもありません。プログラムに存在する並列性の統制を目的とした,完全に決定論的な代数を形成しているのです。

残念なことにこの2つの事象は,これまでも明確に区別されて来ませんでした。並列性を統制する機構 ( ロック,条件変数,モニタなど ) が並列性機構 ( この場合はスレッド ) 自身の上に,直接的に構築されてきたのです。これがよい考えではないという点については,すでに合意が出来ていると考えて差し支えないでしょう。
例えば Simon Peyton Jones 氏は,この問題について次のように書いています ( Beautiful Code,A. Oram,G.Wilson 編,O’Reilly 2007,ISBN 0-321-18578-1 “Beautiful Concurrency” / 邦訳:ビューティフルコード,オライリー・ジャパン,ISBN 978-4-87311-363-0 “美しきかな,並列” )。
手短に言うと,今日の並列プログラミングにおける主流技術 – ロックと条件変数 – には,根本的な欠陥があるのです。 [...] ロックを基本としたプログラミングの根本的な欠点は,ロックと条件変数がモジュラプログラミングをサポートしていないことです。ここで言う “モジュラプログラミング” とは,小さなプログラムを結合させて大規模なプログラムを構築する,そのプロセスを指しています。ロックはこれを不可能にするのです。

さらに Edward A. Lee 氏は,スレッドに関する問題点を次のように整理しています ( “The problem with threads”, IEEE Computer, vol. 29, no. 5, pp 33-42, May 2006 )。 “スレッドは,逐次計算処理の最も基本的かつ有効な性質である理解性,予測性,決定性といったものを損なうのです。計算処理モデルとしてのスレッドは極めて非決定論的な存在であり,プログラマの労力はその非決定性を取り除く目的に浪費されてしまいます。 [...] 非決定性を取り除くのではなく,本質的に決定論的で構成可能なコンポーネントを用いて構築するべきです。非決定性は,不要な部分から削除するというより,必要な部分に明示的かつ慎重に導入すべきなのです。"

SJS のオペレータは,Lee 氏が言うところの “決定論的で構成可能なコンポーネント” の実例であると考えています。

InfoQ: Apollo は CommonJS をサポートしていますが,これが開発者に対して持つ意味は何でしょうか?

Apollo は,サーバサイド JS (node.js など) でデファクト標準となっている CommonJS モジュールシステム ( http://www.commonjs.org/specs/modules/1.0/ ) をサポートします。クライアントサイドにおいては,‘ノーマルな’ JS が本当の意味で,( CommonJS では必須である ) モジュールを非同期にロードする処理を実現できない点が問題になります – コールバックへの移行が常に必要なのです。Apollo は私の知る限り,CommonJS 形式のモジュールシステムをクライアントサイドで実現した,唯一の実装例です。

Apollo は MIT ライセンスの下,onilabs の Web サイト から入手可能だ。

この記事に星をつける

おすすめ度
スタイル

BT