Tachyon-list Août 2011

tachyon-list@iro.umontreal.ca

6 participants
12 discussions

Benchmark suggestions
by Erick Lavoie 25 Aoû '11

25 Aoû '11

Avocado: Live programming environment for Javascript http://avocadojs.com/ Lively Kernel http://lively-kernel.org/ Erick

1 0

The C Paradox
by chevalma＠iro.umontreal.ca 24 Aoû '11

24 Aoû '11

http://dis.4chan.org/read/prog/1312655446/4

2 1

Meeting Thursday
by Marc Feeley 22 Aoû '11

22 Aoû '11

Can we meet on Thursday this week? I may have a hard time making the meeting if it is Wednesday. Marc

5 4

Photon Code
by Erick Lavoie 20 Aoû '11

20 Aoû '11

The latest source code for the photon compiler can be found on the Photon repo on github under the branch 'ometa-compiler'. The version on the repo is not buildable because the d8-tachyon-exts.cc must be accomodated and I still need to discuss this with Maxime. Anyway, the source code for the object model in C is 'bootstrap/photon.c'. The ometa compiler is 'ometa/photon-compiler.txt'. The supporting photon library is 'photon-lib.js'. Erick

1 0

Photon Bootstrap and Relative frequency of each AST node types for Photon compiler
by Erick Lavoie 18 Aoû '11

18 Aoû '11

I thought about the required work for bootstrapping Photon with OMeta and decided to find the operations needed in the compiler. I did a static analysis to find them and their frequency in the source code. For those interested, the OMeta code is given at the end. I apply the analysis to the following files needed for the bootstrap (I still need to make sure I do not need the other stdlib files). To give an idea of the size of each file, I list the number of lines beside it: 135 utility/debug.js 938 utility/num.js 505 utility/misc.js 141 utility/iterators.js 270 utility/arrays.js 624 stdlib/array.js 1146 stdlib/string.js 160 stdlib/function.js 194 stdlib/object.js 1302 backend/asm.js 3352 backend/x86/asm.js 180 ometa-js/lib.js 513 ometa-js/ometa-base.js 46 ometa-js/parser.js 136 ometa-js/photon-compiler.js 405 photon-lib.js 58 photon-test.js 10105 total I get the following frequencies. I put an 'X' beside supported operations, '/' beside partially supported operations and ' ' beside not supported operations: get: 9728 / -> need to add support for scope chain lookup string: 9194 X getp: 7179 call: 3693 X this: 3072 X var: 2545 X binop: 1863 '===': 409 X '+': 379 X '<': 204 X '-': 169 X '&&': 126 / -> need to fix semantic to only evaluate second operand when the first is true '>=': 94 '||': 93 / -> ... when the first is false '!==': 69 X '>': 52 '!=': 43 -> I am surprised to see those, I'll need to further investigate where they come from '&': 41 '<<': 32 '>>': 29 '<=': 26 '==': 21 -> idem '*': 20 / -> need to add type test '/': 18 'instanceof': 14 '%': 10 '^': 9 '|': 5 set: 1669 / -> need to add support for assignment in a parent closure/global object or a regular object number: 1548 X return: 1529 X func: 1419 / -> need to add support for closures begin: 1236 X if: 501 X arr: 261 case: 219 binding: 211 X unop: 173 '-': 64 / -> need to add type test and overflow check '!': 60 'typeof': 46 'delete': 3 postop: 148 '++': 119 '--': 29 for: 119 condExpr: 112 X throw: 98 -> need to add support for exceptions preop: 89 '++': 77 '--': 12 switch: 79 break: 73 default: 72 new: 53 json: 52 mset: 48 '+': 39 '-': 5 '>>': 2 '*': 2 while: 44 X forIn: 12 try: 12 -> need to add support for exceptions doWhile: 9 continue: 7 No support for a GC will be done at this time and the bootstrap will be done in memory. I plan to do the following in order: 1. Add support for binop, unop, preop, postop, mset(partial), arr, for, switch/case/default, json, doWhile, continue, break (except operations requiring Constructors) -> Should be enough to compile C-like code 2. Rewrite the semantic of the object model in extended JS (< 600l of C code) 3. Add support for extension of objects and arrays 4. Add support for the global object 5. Add support for closures and scope chain 6. Add support for exceptions 7. Add support for constructors 8. Add inline cache invalidation mecanism 9. Add reuse of maps 10.Add support for variadic functions and arguments object 11.Port stdlib tachyon-specific operations to photon 12.Try bootstrap, fix bugs, add missing support, rinse, repeat (13.) Optimize get/set property and variable on the scope chain (14.) Optimize string internalization with a dictionary (15.) Optimize lookup of properties on a map with a dictionary (16.) Optimize construction of objects Help would be appreciated, especially on steps 4-11. Those can mostly be done in parallel once 1-3 have been done. I'll be glad to explain the current system to interested people. Erick PS: Here is ASTFrequency Ometa analysis: ometa ASTFrequency <: PhotonASTTraversal { trans = [:t apply(t):ans] -> {self.nodes[t] = (self.nodes[t] === undefined) ? 1 : self.nodes[t] + 1; self;}, binop :op trans:x trans:y -> {if (self.ops.binop[op] === undefined) self.ops.binop[op] = 0; self.ops.binop[op] += 1;}, preop :op trans:x -> {if (self.ops.preop[op] === undefined) self.ops.preop[op] = 0; self.ops.preop[op] += 1;}, unop :op trans:x -> {if (self.ops.unop[op] === undefined) self.ops.unop[op] = 0; self.ops.unop[op] += 1;}, mset trans:lhs :op trans:rhs -> {if (self.ops.mset[op] === undefined) self.ops.mset[op] = 0; self.ops.mset[op] += 1;}, postop :op trans:x -> {if (self.ops.postop[op] === undefined) self.ops.postop[op] = 0; self.ops.postop[op] += 1;} }; ASTFrequency.initialize = function () { this.nodes = {}; this.ops = { binop:{}, preop:{}, mset:{}, unop:{}, postop:{} }; this.freqs = function () { function sorta(a, b) { return b[1] - a[1]; } var total = 0; for (var n in this.nodes) { total += this.nodes[n]; } var numbers = []; for (var n in this.nodes) { numbers.push([n, this.nodes[n]]); } numbers.sort(sorta); for (var i = 0; i < numbers.length; ++i) { print(numbers[i][0] + ": " + numbers[i][1]); var n = numbers[i][0]; if (this.ops[n] !== undefined) { var op_numbers = []; for (var op in this.ops[n]) { op_numbers.push([op, this.ops[n][op]]); } op_numbers.sort(sorta); for (var j = 0; j < op_numbers.length; ++j) { print(" '" + op_numbers[j][0] + "': " + op_numbers[j][1]); } } } }; }; PPS: Here is the base grammar to traverse the AST: ometa PhotonASTTraversal { trans = [:t apply(t):ans], curlyTrans = [#begin curlyTrans:r] | [#begin trans*:rs] | trans:r, this end, break end, continue end, number :n, string :s, arr trans*:xs, unop :op trans:x, getp trans:fd trans:x, get :x, set trans:lhs trans:rhs, mset trans:lhs :op trans:rhs, binop :op trans:x trans:y, preop :op trans:x, postop :op trans:x, return trans:x, with trans:x curlyTrans:s, if trans:cond curlyTrans:t curlyTrans:e, condExpr trans:cond trans:t trans:e, while trans:cond curlyTrans:body, doWhile curlyTrans:body trans:cond, for trans:init trans:cond trans:upd curlyTrans:body, forIn trans:x trans:arr curlyTrans:body, begin trans:x end, begin trans*:xs, func :args :scope curlyTrans:body, call trans:fn trans*:args, send :msg trans:recv trans*:args, new :cls trans*:args, var :name trans:val, throw trans:x, try curlyTrans:x :name curlyTrans:c curlyTrans:f, json trans*:props, binding :name trans:val, switch trans:x trans*:cases, case trans:x trans:y, default trans:y, global_return trans:x, ref :s, gets trans:fd trans:x, mreturn trans:x trans:y }

1 0

Extensible Compiler generation
by Erick Lavoie 15 Aoû '11

15 Aoû '11

The CoSy system might be an interesting inspiration. http://www.ace.nl/compiler/papers.html Erick

1 0

No meeting this afternoon
by Bruno Dufour 10 Aoû '11

10 Aoû '11

Just to confirm, there will be no DLT meeting this afternoon. Bruno

1 0

Fib working
by Erick Lavoie 10 Aoû '11

10 Aoû '11

Fibonacci worked yesterday. I'll be demoing to interested people today. Just come to the lab! Erick

3 2

Re: [Ref#2011080310000021] cr�ation du
by Marc Feeley 10 Aoû '11

10 Aoû '11

Voici ce que l'équipe de support me dit à propos de la création de l'usager "dlt". Je vais proposer le nom "dl-team" ou "dl-group" s'il n'y a pas d'objection. Marc On 2011-08-04, at 10:43 AM, Gestion des requêtes wrote: > Bonjour, > > Le nom d'usager proposé est trop court; qu'est-ce que tu dirais de > « dylate » ou « dynlant » ou « dynalan » avec ou sans "t" final ? > > Un nom d'usager fait entre 5 et 8 caractères. > > Le formulaire à remplir est disponible à : > http://support.iro.umontreal.ca/lib/exe/fetch.php?media=compte:formulaire_c… > > > Bernard > > Marc Feeley <feeley(a)iro.umontreal.ca> écrit: > >> Bonjour. J'aimerais créer le compte "dlt" qui sera associé à notre nouveau >> projet de compilateur pour créer un wiki qui permettra de publiciser le >> projet. DLT = "Dynamic Languages Team". >> >> Marc > > -- > Bernard Derval > Soutien technique DIRO >

2 5

Parser extension
by Marc Feeley 03 Aoû '11

03 Aoû '11

To evaluate how hard it is to extend the current parser, I did the following experiment. I extended the JavaScript grammar to support 2 new forms of statements with the following syntax: atomic { ... } future <Expr> ; These could be used for example for the atomic execution of a block, and for the parallel evaluation of an expression in a newly created thread. A "git diff" is attached below. It took me about 30 minutes to implement the parser extensions. To implement these extensions we need 2 new tokens "atomic" and "future". Which require adding a %token line in Grammar.y , and two lines in the file "keywords.scm" (which is used to create a perfect hash table of the keywords). Two lines are added to Grammar.y to specify the new productions rules. The file parser.js has to be modified to add the function Statement_18 and Statement_19 which implement the actions of the new production rules, which create AST nodes specific to those cases (18 and 19 because these production rules are the 18th and 19th in the category "Statement"). Finally, for smooth integration with the AST passes of the compiler, the AST walker for statements has to be extended for these new AST node types (file ast-passes.js). A few more lines would be required in the pretty printer (pp.js). That makes about 30 to 40 lines of simple code to implement each extension. This is very little when compared to the hundreds of lines of complex code to implement the analysis, optimization, code generation and runtime support for these forms. It would be really nice if we could simplify the implementation of the complex stuff! Marc diff --git a/source/parser/Grammar.y b/source/parser/Grammar.y index f7c3c10..7718157 100644 --- a/source/parser/Grammar.y +++ b/source/parser/Grammar.y @@ -243,6 +243,7 @@ static inline void setExceptionLocation(ThrowableExpressionData* node, unsigned %token SWITCH WITH RESERVED %token THROW TRY CATCH FINALLY %token DEBUGGER +%token ATOMIC FUTURE /********* extensions *********/ /* give an if without an else higher precedence than an else to resolve the ambiguity */ %nonassoc IF_WITHOUT_ELSE @@ -859,6 +860,8 @@ Statement: | ThrowStatement | TryStatement | DebuggerStatement + | ATOMIC Block /********* extensions *********/ + | FUTURE Expr ';' /********* extensions *********/ ; Block: diff --git a/source/parser/ast-passes.js b/source/parser/ast-passes.js index bd92a39..0dfb36e 100644 --- a/source/parser/ast-passes.js +++ b/source/parser/ast-passes.js @@ -213,7 +213,17 @@ function ast_walk_statement(ast, ctx) { return ast; } - else + else if (ast instanceof AtomicStatement) /********* extensions *********/ + { + ast.statement = ctx.walk_statement(ast.statement); + return ast; + } + else if (ast instanceof FutureStatement) /********* extensions *********/ + { + ast.expr = ctx.walk_expr(ast.expr); + return ast; + } + else { //pp(ast); error("unknown ast in walk_statement"); diff --git a/source/parser/keywords.scm b/source/parser/keywords.scm index 8721b2e..5fba892 100644 --- a/source/parser/keywords.scm +++ b/source/parser/keywords.scm @@ -80,6 +80,8 @@ "void" "while" "with" +"atomic" ;; ********* extensions ********* +"future" ;; ********* extensions ********* ;; FutureReservedWord "class" diff --git a/source/parser/parser.js b/source/parser/parser.js index 193223d..c5fc0e0 100644 --- a/source/parser/parser.js +++ b/source/parser/parser.js @@ -1984,6 +1984,30 @@ function Statement_17(p, DebuggerStatement) return DebuggerStatement; } +function AtomicStatement(loc, statement) +{ + this.loc = loc; + this.statement = statement; +} + +function Statement_18(p, ATOMIC, Block) /********* extensions *********/ +{ + return new AtomicStatement(ATOMIC.loc.join(Block.loc), + Block); +} + +function FutureStatement(loc, expr) +{ + this.loc = loc; + this.expr = expr; +} + +function Statement_19(p, FUTURE, Expr, SEMICOLON) /********* extensions *********/ +{ + return new FutureStatement(FUTURE.loc.join(SEMICOLON.loc), + Expr); +} + function Block_1(p, LBRACE, RBRACE) { return new BlockStatement(LBRACE.loc.join(RBRACE.loc),

1 0

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

Tachyon-list Août 2011