Subscribed unsubscribe Subscribe Subscribe

枕を欹てて聴く

香炉峰の雪は簾を撥げて看る

Re-Implement ECMA262 5th Engine@Firefox Developers Conference 2010

JavaScript ECMAScript

f:id:Constellation:20101120234255p:image

LTで話してきました. Constなんとか Constellation です. Firefox Developers Conference, 素晴らしい方々とお会いできて大変楽しかったです. ありがとうございました.

Re-Implement ECMA262 5th Engine - Constellation Scorpius

これが当日のLTの資料です. 言い訳タイムとしては, 4分になったので, 技術的なこと含めてある程度話すには衝撃的な早口と冗長なslideの吹っ飛ばししかないなと決意したというのが結論です. 結果非常に分かりづらい形になってしまって申し訳ないです.
資料なのですが, もともと5分でしゃべるためにかなり端折っていて, しかもさらに端折ったので, 例えばECMAScript strict modeの違反のexampleが6例中の1例しか紹介出来ていなかったりします. なので, このblog記事で本当は喋りたかったこと, その他もろもろ追記しようと思います.
資料の方にも, 6例ほどECMAScriptの面白い仕様のquizのような(Engineも騙される系の)ものがあるので是非楽しんでもらえれば.

iv / lv5の話

本題は自分が夏くらいから書き始めたJavaScript Interpreter iv / lv5の話です.

iv / lv5

現状, かなりbuggyなのでまだまだなのですが, 一応Expression / Statementやprototypeの継承の仕組みなどやnew, Writable / Enumerable / Configurable, strict mode supportなどある程度めどが付いている程度には出来上がっています. 問題は, String / Number / Objectなどにある大量のbuiltinのメソッドを時間をかけてゆっくり追加していくという話ですが, それもまあ時間をかけてゆっくりやって行くつもりです.

目標としては, LTでも触れたとおり, 完全にECMA262 5thの仕様に沿ったReference実装を目指しています. 互換性とかそういったものは許容しない方針で, また, FunctionStatementなど一応対応していますが, それが将来的に仕様に反するという結論に達すれば即座に切り捨てるというように, 非常に仕様に正確につくることを目的としています. ES5 compatible table ECMAScript 5 compatibility table (Prototype.jsのcommitterのkangaxさん(といったほうがはやいかも)でJSCやBesen, SpiderMonkeyの最新版(trunk)はStrict Mode対応のtestを全てpassしていますが, 実際には様々なヌケがあります. また, 数値変換のparseFloat/parseInt/ToNumberなどにも仕様と異なる部位があるなど様々な微妙に異なる部分が存在します. これを丁寧に仕様に沿って実装しようというのがiv / lv5の趣旨です. 速度はそれほど気にしてはいません.

iv / lv5の特徴としては,

  1. Interpreter方式でASTに静的型付けを行ったものをVisitorでInterpretし(なので分岐は定数時間, まあvirtual methodたどると遅い説が濃厚ですが, 見た目にもすっきり), Contextを渡してそのなかで評価を行うという形式
  2. ほぼSingletonがなく, ある程度はじめから複数Contextを建てる事ができるようにという設計方針
  3. 最近流行のNaN Boxingを行っており, JSValという型安全なUnionをValueとして扱っているのですが大きさは統一でdoubleと同サイズ, これはJSC / JeagerMonkeyと同じです. 一応Endianと64bitのため4通り書いてあり, C++のお家芸のtemplateでcompile時に判断

あと目標としては,

  1. GCは現在はBoehmGCを使っていますが, 将来的には自分で書きたい
  2. Interpreter方式ですが, VM式のも書きたい
  3. ICUの依存を切りたい

などがあります.

ECMA262 5thの仕様の話

あとはECMA262 5thの仕様の話です.

まずは仕様書の罠の話. 仕様書は非常に正確で(ちょっとおかしいなと思ったらErrata見てください), 大変頼もしいのですが, 実はいくつかの暗黙の了解が必要なポイントがあります.
例えば, PropertyDescriptorのAttribute, writable: true, configurable: trueなどと設定しますね. さて, この時設定しなかった値はどのように評価されるのでしょうか? section 8.12.9などをみるとその値に応じて例えばstep 7ではConfigurable field of current is false thenとなっていますが, どうなのでしょうか.
自動でfalseで埋められると思った場合は残念ながらはずれです. 実はこの値はtrue / false / absentの3値を取る実質triboolであり, 例えば, この8.12.9のstep 7の場合はfalseのcheckなので, absentの場合は入ってはいけないifのbranchなのです. それを如実に示す8.12.9のstep 7のbを見てください. Enumerableについてpresent(absentでない)であるか確認が入っていますね. このように実はC++などで作る場合はboolでは実現できず, 3値取るようにする必要があります. 自分はConfigurable / Enumerable / Writable / AccessorDescriptor / DataDescriptorなどなどの状態をひとつのintのbit flagで管理しています.
これ, なんでこうなるかというと, 例えば

var obj = {};
Object.defineProperty(obj, 'i', {
  writable: true,
  configurable: false,
  enumerable: false,
  value: "NG"
});
obj.i = "OK";

こうしたときにiのconfigurableとenumerableがtrueの値だと, configurableの値が変更されるのでTypeErrorが発生するわけですね. このときすでに登録されている値に対する場合は, absentはその対象のattrの値をそのまま取る, つまり出来る限り波風立てない形に収まります. なのでtrue / false以外にabsentといういわば「先に場所とってた人がいなかったらなんか埋めるけど, 先に場所とってた人がいたらその人が決めた値におまかせ」みたいな状態がぜひとも必要になってくるという事情があります. なので, absentは非常に重要なfactorなのです.


次は冗長な実装の話. Argumentsなどあからさまです. とりあえず, 読んでみてください...
どうですか? ParameterMap, 超無駄, というかわざわざそのためだけにObjectをもうひとつ持つのはオーバーだと思いませんでしたか?
そのため, 一般的には配列を作り(なぜなら, ParameterMapに定義される値はすべてstep11のindxであり, 0からarguments.length-1までの数値であることが確定しているから), bitでflagをたてておき, そのbitでcheckします. accessで数値indexできたときのみこの内部配列の中身を確認してtrueかどうかをcheckするのですね. これなら非常に低コストです. ただ, これをJSCはnew bool[num]ってやっているのですが, 個人的には new uint32_t[num / 32 + (num % 32 ? 1 : 0)]とかやってbit flagでやったほうがmemory cost低いと思いました. boolのサイズ普通に大きいので...


また, 最後にひとつ大きな変更点は, early errorです. section 16, The Annotated ES5 spec has moved でES5で新たに付け加えられたErrorsの項目には, early error, つまりparse時にエラーとすべき項目が載っていて,

Any syntax error.

という衝撃の言葉が書いてあります. これはつまり, もしもあなたがeval / Function Constructor(この2つは認められている, 仕様参考)以外からSyntaxErrorがruntimeに実行されるのを見たら, それは即座にES5仕様違反だという判断をしても良いということです. このearly errorは非常にアレなので, まだ全然実装されていません. 主要Engineの中ではSpiderMonkeyが一番進んでいると思います. ちなみにiv / lv5は非常にstrict modeとearly errorに力を入れているので, すでにSyntaxErrorは全てparse時にreport, runtimeにだすということはないです.

復帰可能SyntaxErrorの話

例えば,

function test() {

でSyntaxErrorになったとき, 内容は, ほしいtokenが来なかったというerror(Expected tokenが来なかった)というerrorで, 実際にはEOS(End Of String)が来ているわけですね. このようにEOSによってExpected tokenが外れたことによるSyntaxErrorは, 逆に言えば, まだtokenが続けば, SyntaxValidになり得るという特徴を持っています. つまり, 上の例だと }がくれば,

function test() {
}

でSyntaxValidですね. このようにまだSyntaxValidに復帰可能なSyntaxErrorを自分では復帰可能SyntaxErrorと定義しています. 例えば以下のものは復帰不可能なSyntaxErrorです.

var var

IdentifierがくるところにvarですのでExpected tokenが来なかったというのはあっていますが, そのtokenがEOSでなくvarですね.

復帰可能なSyntaxErrorはまだtokenを与えればSyntaxValidになり得るという特徴を持つため, Interactive ShellでEnterを押されたときに, わざと待って, もう少しtokenをもらうことで再解釈できます. これつまり, V8とかの場合, functionとかを,

> (function test() { print("OK"); return void 0; })();

なーんて一行で書かないとSyntaxErrorになっていたのが, iv / lv5のinteractive shellだと,

> (function test() {
|   print("OK"9;
|   return void 0;
| })();

と書いて大丈夫になるというわけです. IRBとかIPythonとかそうなっていますね. それを実装したわけです. これは今年の夏頃, Eval ContextとかInteractive JS Shellとかもろもろ - 枕を欹てて聴く にて研究した内容に, strict modeでのSyntaxErrorなど例外を加えてより正確に実装したもので, C++でparseが走るため全く時間がかからず, なんのストレスもなく複数行のprogramをinteractive shellで書くことができます. これがsmartなinteractive shellと言っていた内容です. LTにて実際に改行を含んでも問題なく評価を待ってくれるのをiv / lv5がちゃんとinterpreterとして動作するというdemoと同時に見せました. 伝わりづらかったら申し訳ないです.

とりあえず

夏からInterpreterをこっそりと書いていたので, いろいろ話したいネタがまだまだたくさんあったりします. early errorの実際の実装の話, typeofの話, あと, JSEngineのなかでなぜboolはC++のboolじゃなくてJSTrue/JSFalseとかそんな値を使っているのかという話(これはC++の話) というようなのはあるのですが, それはおいおい.

補足

で, lv5, 由来は超電磁砲打ちたいという, とある願望です. 科学的(科学サイド)な感じがしますね!! またlv6にしなかった理由としては, lv6はSYSTEMと同義でも語られ「神ならぬ身にて天上の意思に辿り着く者(SYSTEM)」とかなっちゃっておこがましいので, lv6 shiftはしないことにしました. ちなみにGoogle日本語入力だとレールガンで超電磁砲って変換してくれますね! すごい!!
あとミルキィホームズ素晴らしいです. コーデリアさん...