AST in JSON format

[kevin curtis]

In May there was some discussion on the possibility of a standardized
format for the ECMAScript AST in JSON/JsonML.

The V8 engine has an option (in bleeding_edge) where the internal AST
tree can be output to JsonML for debugging purposes:
./shell_g --print_json_ast <file.js>

This is V8's internal AST type, which necessarily includes some
implementation-specific artifacts. That said, the V8 AST is very
nearly straight out of the ECMA 262 spec, so it's pretty generic.
(Note: it's an initial version e.g doesn't recur into switch statement
cases). It could be useful as an input as to what a standard JSON AST
should look like. (Which, i guess, ECMAScript engines could support as
an new, additional format to any existing AST serialization formats).

Here's an example - with some V8 artefact's removed for clarity. Note:
the script gets wrapped in a FunctionLiteral and VariableProxy ==
Identifier.

--- source ---

x = 1;
if (x > 0) {
        y = x + 2;
        print(y);
}


--- AST JsonML ---

["FunctionLiteral",
  {"name":""},
  ["ExpressionStatement",
    ["Assignment",
      {"op":"ASSIGN"},
      ["VariableProxy",
        {"name":"x"}
      ],
      ["Literal",
        {"handle":1}
      ]
    ]
  ],
  ["IfStatement",
    ["CompareOperation",
      {"op":"GT"},
      ["VariableProxy",
        {"name":"x"}
      ],
      ["Literal",
        {"handle":0}
      ]
    ],
    ["Block",
      ["ExpressionStatement",
        ["Assignment",
          {"op":"ASSIGN"},
          ["VariableProxy",
            {"name":"y"}
          ],
          ["BinaryOperation",
            {"op":"ADD"},
            ["VariableProxy",
              {"name":"x"}
            ],
            ["Literal",
              {"handle":2}
            ]
          ]
        ]
      ],
      ["ExpressionStatement",
        ["Call",
          ["VariableProxy",
            {"name":"print"}
          ],
          ["VariableProxy",
            {"name":"y"}
          ]
        ]
      ]
    ],
    ["EmptyStatement"]
  ]
]

3
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[David-Sarah Hopwood-2]

Kevin Curtis wrote:

> In May there was some discussion on the possibility of a standardized
> format for the ECMAScript AST in JSON/JsonML.
>
> The V8 engine has an option (in bleeding_edge) where the internal AST
> tree can be output to JsonML for debugging purposes:
> ./shell_g --print_json_ast <file.js>
>
> This is V8's internal AST type, which necessarily includes some
> implementation-specific artifacts. That said, the V8 AST is very
> nearly straight out of the ECMA 262 spec, so it's pretty generic.
> (Note: it's an initial version e.g doesn't recur into switch statement
> cases). It could be useful as an input as to what a standard JSON AST
> should look like. (Which, i guess, ECMAScript engines could support as
> an new, additional format to any existing AST serialization formats).

The Jacaranda parser (not released yet) also produces a JsonML AST.
Below is the same example for comparison, also with Jacaranda-specific
artefacts removed.

> Here's an example - with some V8 artefact's removed for clarity. Note:
> the script gets wrapped in a FunctionLiteral and VariableProxy ==
> Identifier.
>
> --- source ---
>
> x = 1;
> if (x > 0) {
>         y = x + 2;
>         print(y);
> }

["SEQ", {},
  ["EXPRSTMT", {},
    ["=", {},
      ["REF", {"name":"x"}],
      ["NUMBER", {"MV":1}]]],
  ["if", {},
    [">", {},
      ["REF", {"name":"x"}],
      ["NUMBER", {"MV":0}]],
    ["{", {},
      ["SEQ", {},
        ["EXPRSTMT", {},
          ["=", {},
            ["REF", {"name":"y"}],
            ["+", {},
              ["REF", {"name":"x"}],
              ["NUMBER", {"MV":2}]]],
        ["EXPRSTMT", {},
          ["(", {},
            ["REF", {"name":"print"}],
            ["ARGS", {},
              ["REF", {"name":"y"}]]]]]]]]

> --- AST JsonML ---
>
> ["FunctionLiteral",
>   {"name":""},
>   ["ExpressionStatement",
>     ["Assignment",
>       {"op":"ASSIGN"},
>       ["VariableProxy",
>         {"name":"x"}
>       ],
>       ["Literal",
>         {"handle":1}
>       ]
>     ]
>   ],
>   ["IfStatement",
>     ["CompareOperation",
>       {"op":"GT"},
>       ["VariableProxy",
>         {"name":"x"}
>       ],
>       ["Literal",
>         {"handle":0}
>       ]
>     ],
>     ["Block",
>       ["ExpressionStatement",
>         ["Assignment",
>           {"op":"ASSIGN"},
>           ["VariableProxy",
>             {"name":"y"}
>           ],
>           ["BinaryOperation",
>             {"op":"ADD"},
>             ["VariableProxy",
>               {"name":"x"}
>             ],
>             ["Literal",
>               {"handle":2}
>             ]
>           ]
>         ]
>       ],
>       ["ExpressionStatement",
>         ["Call",
>           ["VariableProxy",
>             {"name":"print"}
>           ],
>           ["VariableProxy",
>             {"name":"y"}
>           ]
>         ]
>       ]
>     ],
>     ["EmptyStatement"]
>   ]
> ]
>
> 3

--
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com

_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[kevin curtis]

DSH - very interesting.

Is the idea eventually (for say ES6) to have something like like the
Python ast module, where the AST (in JsonML format) can be executed?
Or just js source to source roundtripping. e.g js -> JsonML AST -> js

I'm working on an experiment utilizing the V8 engine - using the JSON
object as a (temporary) namespace:

var source = "var x = 3; if (x > 2) print('hello world');";

var astStr = JSON.AST.parse(source); // returns the AST in a JsonML string

JSON.AST.execute(astStr);

> hello world
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[kevin curtis]

A patch is available for the V8 engine which enables:

JSON.AST.parse(|js source code|) -> |AST JsonML String|

At:
http://code.google.com/p/ecmascript-ast/


On Sat, Oct 17, 2009 at 2:47 PM, Kevin Curtis <kevinc1846@...> wrote:

> DSH - very interesting.
>
> Is the idea eventually (for say ES6) to have something like like the
> Python ast module, where the AST (in JsonML format) can be executed?
> Or just js source to source roundtripping. e.g js -> JsonML AST -> js
>
> I'm working on an experiment utilizing the V8 engine - using the JSON
> object as a (temporary) namespace:
>
> var source = "var x = 3; if (x > 2) print('hello world');";
>
> var astStr = JSON.AST.parse(source); // returns the AST in a JsonML string
>
> JSON.AST.execute(astStr);
>
>> hello world
>

_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[kevin curtis]

I have tweaked the JsonML AST format (shorter element names and
operator tokens not names eg ">=" instead of "GTE") and added an
evaluate() function which can execute the JsonML string. Example:

> more example.js
var source = "x = 2; if (x > 1) print(x + 3);";

print("--- js source ---");
print(source);
print("");

print("--- ast ---");
var ast = JSON.AST.parse(source);
print(ast);
print("");

print("--- evaluate(ast) ---");
JSON.AST.evaluate(ast);


> ./shell_g example.js
--- js source ---
x = 2; if (x > 1) print(x + 3);

--- ast ---
["Program",
  ["ExprStmt",
    ["Assign",
      {"op":"="},
      ["Id",
        {"name":"x"}
      ],
      ["Literal",
        {"handle":2}
      ]
    ]
  ],
  ["If",
    ["CompareOp",
      {"op":">"},
      ["Id",
        {"name":"x"}
      ],
      ["Literal",
        {"handle":1}
      ]
    ],
    ["ExprStmt",
      ["Call",
        ["Id",
          {"name":"print"}
        ],
        ["BinOp",
          {"op":"+"},
          ["Id",
            {"name":"x"}
          ],
          ["Literal",
            {"handle":3}
          ]
        ]
      ]
    ],
    ["EmptyStmt"]
  ]
]

--- evaluate(ast) ---
5
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[kevin curtis]

The previous example was pretty printed. A production version would
offer a minified  alternative without newlines and indentation. e.g:

["Program",["ExprStmt",["Assign",{"op":"="},["Id",{"name":"x"}], ...

Perhaps there could be in addition an alternative compact format where
the element strings are replaced with integers:

[44,[20,[21,{"op":"="},[25,{"name":"x"}], ...

And the attribute name string with an integer or maybe the first letter:

[44,[20,[21,{1:"="},[25,{3:"x"}], ...
[44,[20,[21,{"o":"="},[25,{n:"x"}], ...

It's compact and as the integers match the underlying enum no hash
lookup for the element/attribute string names is required. Kind of a
half way house between the AST and bytecode. e.g:

var ast = JSON.AST.parse(source, true); // true for compact mode
var result = JSON.AST.evaluate(ast); // No special mode required

The evaluate() function would simply test if the element value was a
string or integer and hash lookup or atoi.
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[kevin curtis]

Re the idea of standardizing a serialization format in JsonML of the
ECMAScript AST based on the ECMAScript grammar.

The ecmascript-ast project's JSON.AST.parse() function now serializes
all of the grammar/AST to JsonML (I think). JSON.AST.evaluate() is
rudimentary (example.js and ast-test/if.js and while.js work!) The
code to build JSON.AST on V8 is at:
http://code.google.com/p/ecmascript-ast/

JSON.AST - like the JSON object - could initially be implemented in
pure javascript. (evaluate() could parse JsonML and generate JS which
could then be eval'ed). Then engines could determine whether to do
native implementations. A native JSON.AST.parse() outputting JsonML
should be relatively straighforward. JSON.AST.evaluate() is more
tricky - 2 alternatives. Parse and execute the JsonML directly. Or
parse the JsonML to JS - and then the JS can be eval'ed. (A JsonML to
JS function is probably desirable in any case).

Here's an example of parsing JS source to JsonML AST:

>./ast.sh ast-test/while.js
--- js source ---
x = 1;
while (x < 5) { print(x); x = x + 1; };

--- ast ---
["Program",
  ["ExprStmt",
    ["Assign",
      {"op":"="},
      ["Id",
        {"name":"x"}
      ],
      ["Literal",
        {"handle":1}
      ]
    ]
  ],
  ["While",
    ["CompareOp",
      {"op":"<"},
      ["Id",
        {"name":"x"}
      ],
      ["Literal",
        {"handle":5}
      ]
    ],
    ["Block",
      ["ExprStmt",
        ["Call",
          ["Id",
            {"name":"print"}
          ],
          ["Id",
            {"name":"x"}
          ]
        ]
      ],
      ["ExprStmt",
        ["Assign",
          {"op":"="},
          ["Id",
            {"name":"x"}
          ],
          ["BinOp",
            {"op":"+"},
            ["Id",
              {"name":"x"}
            ],
            ["Literal",
              {"handle":1}
            ]
          ]
        ]
      ]
    ]
  ]
]

--- evaluate(ast) ---
1
2
3
4
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[Mark S. Miller-2]

On Sun, Dec 6, 2009 at 4:19 AM, Kevin Curtis <kevinc1846@...> wrote:
> Re the idea of standardizing a serialization format in JsonML of the
> ECMAScript AST based on the ECMAScript grammar.
>
> The ecmascript-ast project's JSON.AST.parse() function now serializes
> all of the grammar/AST to JsonML (I think). JSON.AST.evaluate() is
> rudimentary (example.js and ast-test/if.js and while.js work!) The
> code to build JSON.AST on V8 is at:
> http://code.google.com/p/ecmascript-ast/

I am eager to see such a proposal. However, on your pages, I could not
find any documentation, other than small examples, showing what your
proposed encoding of JS ASTs in JSON is. Are you writing a draft spec?

> JSON.AST - like the JSON object - could initially be implemented in
> pure javascript. (evaluate() could parse JsonML and generate JS which
> could then be eval'ed). Then engines could determine whether to do
> native implementations. A native JSON.AST.parse() outputting JsonML
> should be relatively straighforward. JSON.AST.evaluate() is more
> tricky - 2 alternatives. Parse and execute the JsonML directly. Or
> parse the JsonML to JS - and then the JS can be eval'ed. (A JsonML to
> JS function is probably desirable in any case).
>
> Here's an example of parsing JS source to JsonML AST:
>
>>./ast.sh ast-test/while.js
> --- js source ---
> x = 1;
> while (x < 5) { print(x); x = x + 1; };
>
> --- ast ---
> ["Program",
>  ["ExprStmt",
>    ["Assign",
>      {"op":"="},
>      ["Id",
>        {"name":"x"}
>      ],
>      ["Literal",
>        {"handle":1}
>      ]
>    ]
>  ],
>  ["While",
>    ["CompareOp",
>      {"op":"<"},
>      ["Id",
>        {"name":"x"}
>      ],
>      ["Literal",
>        {"handle":5}
>      ]
>    ],
>    ["Block",
>      ["ExprStmt",
>        ["Call",
>          ["Id",
>            {"name":"print"}
>          ],
>          ["Id",
>            {"name":"x"}
>          ]
>        ]
>      ],
>      ["ExprStmt",
>        ["Assign",
>          {"op":"="},
>          ["Id",
>            {"name":"x"}
>          ],
>          ["BinOp",
>            {"op":"+"},
>            ["Id",
>              {"name":"x"}
>            ],
>            ["Literal",
>              {"handle":1}
>            ]
>          ]
>        ]
>      ]
>    ]
>  ]
> ]
>
> --- evaluate(ast) ---
> 1
> 2
> 3
> 4
> _______________________________________________
> es-discuss mailing list
> es-discuss@...
> https://mail.mozilla.org/listinfo/es-discuss
>

--
    Cheers,
    --MarkM
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[kevin curtis]

No spec as yet - more a speculative prototype.

The patch creates a subdir 'ast-test' in the V8 dir which contain a
range of JS source examples covering the ECMAScript grammar. These
examples (and any other JS scripts) can be parsed to JsonML using the
ast-parse.sh shell script (which calls JSON.AST.Parse()):
./ast-parse.sh ast-test/forin.js

The project is an attempt to use the (already pretty generic) JsonML
output feature offered by the V8 deug shell as a starting point for a
generic standarized JSON AST format. Thus, output from from an
unpatched V8 debug shell can also give a good feel of what the JsonML
looks like. (Note: this output is incomplete - it prints only the node
name for some AST constructs):
./shell_g file.js --print-json-ast

It would be useful to get a feel whether the general idea is a starter
- or non-starter. Maybe it merits a wiki straw man entry.

> more ast-test/forin.js
x = [4,5,6];
for (i in x) print(x[i]);
> ./ast-parse.sh ast-test/forin.js
["Program",
  ["ExprStmt",
    ["Assign",
      {"op":"="},
      ["Id",
        {"name":"x"}
      ],
      ["ArrayLiteral",
        ["Literal",
          {"handle":4}
        ],
        ["Literal",
          {"handle":5}
        ],
        ["Literal",
          {"handle":6}
        ]
      ]
    ]
  ],
  ["ForIn",
    ["Id",
      {"name":"i"}
    ],
    ["Id",
      {"name":"x"}
    ],
    ["ExprStmt",
      ["Call",
        ["Id",
          {"name":"print"}
        ],
        ["Property",
          {"type":"NORMAL"},
          ["Id",
            {"name":"x"}
          ],
          ["Id",
            {"name":"i"}
          ]
        ]
      ]
    ]
  ]
]


> I am eager to see such a proposal. However, on your pages, I could not
> find any documentation, other than small examples, showing what your
> proposed encoding of JS ASTs in JSON is. Are you writing a draft spec?
>
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[Oliver Hunt-2]

On Dec 7, 2009, at 3:52 AM, Kevin Curtis wrote:

> No spec as yet - more a speculative prototype.
>
> The patch creates a subdir 'ast-test' in the V8 dir which contain a
> range of JS source examples covering the ECMAScript grammar. These
> examples (and any other JS scripts) can be parsed to JsonML using the
> ast-parse.sh shell script (which calls JSON.AST.Parse()):
> ./ast-parse.sh ast-test/forin.js
>
> The project is an attempt to use the (already pretty generic) JsonML
> output feature offered by the V8 deug shell as a starting point for a
> generic standarized JSON AST format. Thus, output from from an
> unpatched V8 debug shell can also give a good feel of what the JsonML
> looks like. (Note: this output is incomplete - it prints only the node
> name for some AST constructs):
> ./shell_g file.js --print-json-ast
>
> It would be useful to get a feel whether the general idea is a starter
> - or non-starter. Maybe it merits a wiki straw man entry.

Maybe i've missed an email or something, but what is the purpose of this spec?  What is it trying to let developers do?

--Oliver

_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[kevin curtis]

This covers the origin of the idea and some of it's uses:
https://mail.mozilla.org/pipermail/es-discuss/2009-May/009234.html

I'm interested in JsonML AST as a DSL target.

Hacking the YACC file in jsc to parse the ES5 grammar as expressed in
JsonML could yield an (executable) spec of sorts.


On Mon, Dec 7, 2009 at 11:58 AM, Oliver Hunt <oliver@...> wrote:
> Maybe i've missed an email or something, but what is the purpose of this spec?  What is it trying to let developers do?
>
> --Oliver
>
>
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[Maciej Stachowiak]

On Dec 7, 2009, at 7:22 AM, Kevin Curtis wrote:

> This covers the origin of the idea and some of it's uses:
> https://mail.mozilla.org/pipermail/es-discuss/2009-May/009234.html
>
> I'm interested in JsonML AST as a DSL target.
>
> Hacking the YACC file in jsc to parse the ES5 grammar as expressed in
> JsonML could yield an (executable) spec of sorts.

I can see how modifying the AST client-side prior to execution could  
be useful, to implement macro-like processing. But I don't see the use  
case for serializing an AST in JSON-like format, or sending it over  
the wire that way. It seems like it would be larger (and therefore  
slower to transmit), and likely no faster to parse, as compared to  
JavaScript source code. So shouldn't the serialization format just be  
JS source code?

Regards,
Maciej

_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[kevin curtis]

True. JS as the ultimate delivery mechanism is most likely. With JSON
serialization comes for free i guess.

Though i propose an 'compact format' - which is definitely 'speculative':

Perhaps there could an alternative compact format where the element
strings are replaced with integers:

[44,[20,[21,{"op":"="},[25,{"name":"x"}], ...

And the attribute name string with an integer or maybe the first letter:
[44,[20,[21,{1:"="},[25,{3:"x"}], ...
[44,[20,[21,{"o":"="},[25,{n:"x"}], ...

It's compact and as the integers match the underlying enum no hash
lookup for the element/attribute string names is required. Kind of a
half way house between the AST and bytecode.

var ast = JSON.AST.parse(source, true); // true for compact mode
var result = JSON.AST.evaluate(ast); // No special mode required
The evaluate function would simply test if the element value was a
string or integer and hash lookup or atoi.

On Mon, Dec 7, 2009 at 3:45 PM, Maciej Stachowiak <mjs@...> wrote:

>
> On Dec 7, 2009, at 7:22 AM, Kevin Curtis wrote:
>
>> This covers the origin of the idea and some of it's uses:
>> https://mail.mozilla.org/pipermail/es-discuss/2009-May/009234.html
>>
>> I'm interested in JsonML AST as a DSL target.
>>
>> Hacking the YACC file in jsc to parse the ES5 grammar as expressed in
>> JsonML could yield an (executable) spec of sorts.
>
> I can see how modifying the AST client-side prior to execution could be
> useful, to implement macro-like processing. But I don't see the use case for
> serializing an AST in JSON-like format, or sending it over the wire that
> way. It seems like it would be larger (and therefore slower to transmit),
> and likely no faster to parse, as compared to JavaScript source code. So
> shouldn't the serialization format just be JS source code?
>
> Regards,
> Maciej
>
>

_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[Maciej Stachowiak]

I could see a potential use case for a format that was more compact  
and/or faster to parse down to an executable form than JS source.  
However, for size the fair comparison should probably be to JS source  
that has been run through a source-to-source minimizer/compressor, and  
with both run through gzip. I seriously doubt any text-based AST  
format will do better under these conditions.

I also note that your compact form no longer seems very useful for  
direct manipulation of the AST, so presumably the use case would be  
different.

If we really want to minimize size for delivery and parsing speed,  
then probably some sort binary format with built-in compression would  
be most useful, though there would be risk presented in properly  
validating such a format.

Actually, this is potentially a factor for any natively supported AST  
format. If execution is direct rather than via transoformation to JS  
source, the implementation would have to verify that the AST is one  
that could be created by parsing JS source.

Regards,
Maciej

On Dec 7, 2009, at 8:13 AM, Kevin Curtis wrote:

> True. JS as the ultimate delivery mechanism is most likely. With JSON
> serialization comes for free i guess.
>
> Though i propose an 'compact format' - which is definitely  
> 'speculative':
>
> Perhaps there could an alternative compact format where the element
> strings are replaced with integers:
>
> [44,[20,[21,{"op":"="},[25,{"name":"x"}], ...
>
> And the attribute name string with an integer or maybe the first  
> letter:
> [44,[20,[21,{1:"="},[25,{3:"x"}], ...
> [44,[20,[21,{"o":"="},[25,{n:"x"}], ...
>
> It's compact and as the integers match the underlying enum no hash
> lookup for the element/attribute string names is required. Kind of a
> half way house between the AST and bytecode.
>
> var ast = JSON.AST.parse(source, true); // true for compact mode
> var result = JSON.AST.evaluate(ast); // No special mode required
> The evaluate function would simply test if the element value was a
> string or integer and hash lookup or atoi.
>
> On Mon, Dec 7, 2009 at 3:45 PM, Maciej Stachowiak <mjs@...>  
> wrote:
>>
>> On Dec 7, 2009, at 7:22 AM, Kevin Curtis wrote:
>>
>>> This covers the origin of the idea and some of it's uses:
>>> https://mail.mozilla.org/pipermail/es-discuss/2009-May/009234.html
>>>
>>> I'm interested in JsonML AST as a DSL target.
>>>
>>> Hacking the YACC file in jsc to parse the ES5 grammar as expressed  
>>> in
>>> JsonML could yield an (executable) spec of sorts.
>>
>> I can see how modifying the AST client-side prior to execution  
>> could be
>> useful, to implement macro-like processing. But I don't see the use  
>> case for
>> serializing an AST in JSON-like format, or sending it over the wire  
>> that
>> way. It seems like it would be larger (and therefore slower to  
>> transmit),
>> and likely no faster to parse, as compared to JavaScript source  
>> code. So
>> shouldn't the serialization format just be JS source code?
>>
>> Regards,
>> Maciej
>>
>>

_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[kevin curtis]

On Mon, Dec 7, 2009 at 4:56 PM, Maciej Stachowiak <mjs@...> wrote:
>
> I could see a potential use case for a format that was more compact and/or
> faster to parse down to an executable form than JS source. However, for size
> the fair comparison should probably be to JS source that has been run
> through a source-to-source minimizer/compressor, and with both run through
> gzip. I seriously doubt any text-based AST format will do better under these
> conditions.

V8 has the implementation idea of symbols - frequently used strings -
such as 'valueOf, String, Number' etc. In ES5 'Object.defineProperty'
etc is going to be used quite frequently. It would be possible to to
turn these common Call strings into integers in JsonML. If the Call Id
is an integer than it is considered a direct call to one of ES5's
non-monkeypatched 'special forms'. Given the amount of object
hardening factories that i imagine will be written this could be a
win.
["Call", ["Property", ["Id", {name:"Object"}, ["Id", "defineProperty"]]
[33,[55,{4:12}...

Maybe that would be more compact. Though it's stretching!

> If we really want to minimize size for delivery and parsing speed, then
> probably some sort binary format with built-in compression would be most
> useful, though there would be risk presented in properly validating such a
> format.

Maybe the ByteVector proposal offers possibilities in this area! (With
a module system could this be namespaced within a native builtin
module? Then Data could be a name possibility. Though having
ByteVector as top-level and immediately accessible is sweet).

Overall, there seems to be a tension between those who wish to treat
the ECMAScript as a semantic runtime with serverside compilers
generating compact, optimized JS and those who want to add sugar to
the language so that the it could compete with - say Python - for user
friendliness as a general purpose PL. I prefer to reduce the language
and then add any necessary core semantics for safety, speed and
simplicity. Then let DSL's compete for the best sugar - C syntax or
otherwise.

> Actually, this is potentially a factor for any natively supported AST
> format. If execution is direct rather than via transoformation to JS source,
> the implementation would have to verify that the AST is one that could be
> created by parsing JS source.

Though in some ways a JsonML format - or whatever - offers freedom
from JS backward compatibility issues. Want a new keyword:
["Import", ...

Regards.
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[Brendan Eich-3]

On Dec 7, 2009, at 8:56 AM, Maciej Stachowiak wrote:

> Actually, this is potentially a factor for any natively supported  
> AST format. If execution is direct rather than via transoformation  
> to JS source, the implementation would have to verify that the AST  
> is one that could be created by parsing JS source.

This reminds me of SafeTSA:

http://portal.acm.org/citation.cfm?id=378825
http://portal.acm.org/citation.cfm?doid=1377492.1377496

and more specifically of work by Christian Stork and Michael Franz, see:

http://www.ics.uci.edu/~cstork/

The idea as I first heard it from Chris and Michael was to  
arithmetically code ASTs such that no ill-formed tree could be  
encoded. You could take a JPEG of the Mona Lisa, run it through the  
decoder, and if it succeeded, get a (almost-certainly) nonsensical yet  
syntactically well-formed AST. The encoding is fairly efficient, not  
as good as optimized Huffman coding but close.

This work was motivated by the sometimes bad (O(n^4)) complexity in  
the Java bytecode verifier (or at least in early versions of it).

My view is that there will never be a standardized bytecode (politics  
look insuperable to me), and more: that there should not be. Besides  
the conflicts among target VM technical details, and ignoring latent  
IPR issues, I believe view-source capability is essential. Even  
minification lets one pretty-print (http://jsbeautifier.org/) and  
learn or diagnose.

JS is still used in edit-shift-reload, crawl-walk-run development  
style and part of this culture involves sharing. Of course no one  
could mandate binary syntax to the exclusion of source, but a binary  
syntax that did not allow pretty-printing would shove us all down the  
slippery slope toward the opaque, closed-box world of Java applets,  
Flash SWFs (modulo Flash+Flex's server-fetched view-source  
capabilities), etc.

Compression at the transport (session, whatever, the model is climbing  
the traditional layering) is a separate issue.

/be
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[Maciej Stachowiak]

On Dec 7, 2009, at 10:11 AM, Brendan Eich wrote:

> On Dec 7, 2009, at 8:56 AM, Maciej Stachowiak wrote:
>
>> Actually, this is potentially a factor for any natively supported  
>> AST format. If execution is direct rather than via transoformation  
>> to JS source, the implementation would have to verify that the AST  
>> is one that could be created by parsing JS source.
>
> This reminds me of SafeTSA:
>
> http://portal.acm.org/citation.cfm?id=378825
> http://portal.acm.org/citation.cfm?doid=1377492.1377496
>
> and more specifically of work by Christian Stork and Michael Franz,  
> see:
>
> http://www.ics.uci.edu/~cstork/
>
> The idea as I first heard it from Chris and Michael was to  
> arithmetically code ASTs such that no ill-formed tree could be  
> encoded. You could take a JPEG of the Mona Lisa, run it through the  
> decoder, and if it succeeded, get a (almost-certainly) nonsensical  
> yet syntactically well-formed AST. The encoding is fairly efficient,  
> not as good as optimized Huffman coding but close.
>
> This work was motivated by the sometimes bad (O(n^4)) complexity in  
> the Java bytecode verifier (or at least in early versions of it).
>
> My view is that there will never be a standardized bytecode  
> (politics look insuperable to me), and more: that there should not  
> be. Besides the conflicts among target VM technical details, and  
> ignoring latent IPR issues, I believe view-source capability is  
> essential. Even minification lets one pretty-print (http://jsbeautifier.org/ 
> ) and learn or diagnose.
>
> JS is still used in edit-shift-reload, crawl-walk-run development  
> style and part of this culture involves sharing. Of course no one  
> could mandate binary syntax to the exclusion of source, but a binary  
> syntax that did not allow pretty-printing would shove us all down  
> the slippery slope toward the opaque, closed-box world of Java  
> applets, Flash SWFs (modulo Flash+Flex's server-fetched view-source  
> capabilities), etc.
>
> Compression at the transport (session, whatever, the model is  
> climbing the traditional layering) is a separate issue.

Given the above, do you think there is a valid case to be made for a  
serialization format other than JavaScript source itself? It seems  
like anything binary is likely to have the same downsides as bytecode,  
and anything text-based enough to be truly readable and view-source  
compatible would be rather inefficient as a wire format (I would  
consider a JSON encoding with mysterious integers all over to be not  
truly view-source compatible). Thus I would propose that we should not  
define an alternate serialization at all.

(This is as considered separately from the possibility of  
programatically manipulating a parsed AST - the use cases for that are  
clear. Though there may still be verification issues depending on the  
nature of the manipulation API. It seems like the possibilities are  
either specialized objects that enforce validity on every individual  
manipulation, or something that accepts JSON-like objects and verifies  
validity after the fact, or something that accepts JSON-like objects  
and verifies validity by converting to JavaScript source code and then  
parsing it).

Regards,
Maciej

_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[Mark Miller-2]

On Mon, Dec 7, 2009 at 7:45 AM, Maciej Stachowiak <mjs@...> wrote:

>
> On Dec 7, 2009, at 7:22 AM, Kevin Curtis wrote:
>
>> This covers the origin of the idea and some of it's uses:
>> https://mail.mozilla.org/pipermail/es-discuss/2009-May/009234.html
>>
>> I'm interested in JsonML AST as a DSL target.
>>
>> Hacking the YACC file in jsc to parse the ES5 grammar as expressed in
>> JsonML could yield an (executable) spec of sorts.
>
> I can see how modifying the AST client-side prior to execution could be
> useful, to implement macro-like processing. But I don't see the use case for
> serializing an AST in JSON-like format, or sending it over the wire that
> way. It seems like it would be larger (and therefore slower to transmit),
> and likely no faster to parse, as compared to JavaScript source code. So
> shouldn't the serialization format just be JS source code?

+1.

While potentially useful, I have no interest in these ASTs as a
serialization format nor in a compact AST encoding. I am interested in
having a standard JsonML AST encoding of parsed ES5, and eventually an
efficient and standard browser-side parser that emits these ASTs. Many
forms of JS meta-programming that currently occur only on the server
(e.g., Caja, FBJS, MSWebSandbox, Jacaranda) or have to download a full
JS parser to the client per frame (ADsafe, JSLint, Narcissus,
Narrative JS) could instead become lighter weight client side
programs.


--
Text by me above is hereby placed in the public domain

    Cheers,
    --MarkM
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[David-Sarah Hopwood-2]

Mark Miller wrote:

> On Mon, Dec 7, 2009 at 7:45 AM, Maciej Stachowiak <mjs@...> wrote:
>
>> I can see how modifying the AST client-side prior to execution could be
>> useful, to implement macro-like processing. But I don't see the use case for
>> serializing an AST in JSON-like format, or sending it over the wire that
>> way. It seems like it would be larger (and therefore slower to transmit),
>> and likely no faster to parse, as compared to JavaScript source code. So
>> shouldn't the serialization format just be JS source code?
>
> +1.
>
> While potentially useful, I have no interest in these ASTs as a
> serialization format nor in a compact AST encoding. I am interested in
> having a standard JsonML AST encoding of parsed ES5, and eventually an
> efficient and standard browser-side parser that emits these ASTs. Many
> forms of JS meta-programming that currently occur only on the server
> (e.g., Caja, FBJS, MSWebSandbox, Jacaranda) or have to download a full
> JS parser to the client per frame (ADsafe, JSLint, Narcissus,
> Narrative JS) could instead become lighter weight client side
> programs.

+1.

Note that:
 - although the size of the JSON serialization of the AST is not
   critical for this kind of usage, the size of the in-memory
   representation definitely is.

 - encoding node type strings as integers, as suggested earlier in the
   thread, does not help with this memory usage.

 - any Lempel-Ziv-based compression algorithm will do much better than
   replacing type strings with integers, in the few situations where
   it is useful to serialize the AST and to minimize the size of the
   serialization.

 - JsonML is a reasonable basis for an AST format even when
   "serialization for free" is of fairly low importance. In particular,
   it is useful that it only uses structures that are common across
   programming languages (for instance, the prototype Jacaranda verifier
   uses it even though it is written in Java). Also, programmers of
   AST-processing applications will see this serialization when
   debugging, and it is likely to appear in test cases for such
   applications and for parsers/emitters.

--
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com



_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[ihab.awad]

On Mon, Dec 7, 2009 at 3:10 PM, David-Sarah Hopwood
<david-sarah@...> wrote:
> ... programmers of AST-processing applications will see this
> serialization when debugging, and it is likely to appear in test
> cases for such applications and for parsers/emitters.

Also: would a JsonML representation be *quicker* to execute than the
original human readable JS source? If so, it could be useful as a wire
format for the code of mobile objects.

Furthermore, this format could be a good target for *generated* code.

On the other hand, this discussion slowly creeps into asking whether
(say) collaborative IDEs and could benefit from such a common
representation. For that use case, it would be necessary to support
comments, which would grow the problem space considerably....

Ihab

--
Ihab A.B. Awad, Palo Alto, CA
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss