[Projects] XRM 42: Extend meta for loops + fix the XRM rand builtin.

https://svn.lrde.epita.fr/svn/xrm/trunk Index: ChangeLog from SIGOURE Benoit &lt;sigoure.benoit(a)lrde.epita.fr&gt; Extend meta for loops + fix the XRM rand builtin. Revision 42 \o/ The fields `from', `to' and `step' of meta for loops can now contain any expression as long as it's statically evaluable down to a simple Int. The first pass of xrm-to-prism now desugar Plus(Int(i)) to Int(i) and Minus(Int(i)) to Int(-i). This plus the previous change allows for loops to use negative numbers (eg: for i from -4 to -1 do ... end) * src/lib/xrm/pp/xrm-to-abox.str: Update a comment. * src/lib/prism/pp/prism-to-abox.str: Ditto. * src/str/xrm-to-prism.str: Move the rand builtin in another file. Handle unary operators to ease transformations. * src/str/builtin-rand.str: New. * src/str/builtin-rand.meta: New. * src/str/eval-meta-code.str: Extend for loops (as said above). * src/syn/xrm/XRM-MetaFor.sdf: Ditto. * src/str/xrm-front.str: Update the help message. * src/syn/prism/PRISM-Expression.sdf: Update a comment. * TODO: More things to do... TODO | 19 +++++++-- src/lib/prism/pp/prism-to-abox.str | 2 - src/lib/xrm/pp/xrm-to-abox.str | 2 - src/str/builtin-rand.meta | 1 src/str/builtin-rand.str | 74 +++++++++++++++++++++++++++++++++++++ src/str/eval-meta-code.str | 34 +++++++++++++---- src/str/xrm-front.str | 4 +- src/str/xrm-to-prism.str | 68 ++++++++++------------------------ src/syn/prism/PRISM-Expression.sdf | 9 ++-- src/syn/xrm/XRM-MetaFor.sdf | 16 +++++--- 10 files changed, 155 insertions(+), 74 deletions(-) Index: src/lib/xrm/pp/xrm-to-abox.str --- src/lib/xrm/pp/xrm-to-abox.str (revision 41) +++ src/lib/xrm/pp/xrm-to-abox.str (working copy) @@ -54,7 +54,7 @@ // because we simply extend it pp-xrm-to-abox(pprules) = - // strategy generated in prism-parenthesize.str by sdf2parenthesize + // strategy from xrm-parenthesize.str generated by sdf2parenthesize parenthesize-XRM ; topdown(try(very-special-conflict)) ; topdown(try(repeat(pprules))) Index: src/lib/prism/pp/prism-to-abox.str --- src/lib/prism/pp/prism-to-abox.str (revision 41) +++ src/lib/prism/pp/prism-to-abox.str (working copy) @@ -47,7 +47,7 @@ pp-prism-to-abox(prism-to-box) pp-prism-to-abox(pprules) = - // strategy generated in prism-parenthesize.str by sdf2parenthesize + // strategy from prism-parenthesize.str generated by sdf2parenthesize parenthesize-PRISM ; topdown(try(very-special-conflict)) ; topdown(try(repeat(pprules))) Index: src/str/xrm-to-prism.str --- src/str/xrm-to-prism.str (revision 41) +++ src/str/xrm-to-prism.str (working copy) @@ -17,6 +17,9 @@ ** - ExpandFormulas: created by the strategy collect-formulas and used by ** prism-desugar for constant propagation. Maps an identifier with an ** expression. +** - RandGenModules: each call to the XRM builtin rand generates a module +** which is stored in this DR. Just before xrm-to-prism finishes, we +** paste these modules at the end of the source code. */ module xrm-to-prism imports @@ -26,13 +29,15 @@ check-meta-vars eval-meta-code array-decl-desugar + builtin-rand strategies xrm-to-prism = /* remove XRM sugar, normalize some nodes */ innermost( - DesugarRightShift <+ DesugarLeftShift + DesugarUnaryOps // keep this first + <+ DesugarRightShift <+ DesugarLeftShift <+ DesugarImplicitForStep <+ DesugarImplicitElse <+ DesugarRand <+ EvalRand ) @@ -62,20 +67,32 @@ ; ModulesFile(id, flatten-list) ; ModulesFile(id, map(try(Module(id, flatten-list)))) - /* get the list of generated modules that generates random numbers */ + /* get the modules that generates random numbers (XRM rand builtin) */ ; where(bagof-RandGenModules; reverse => rand-gen-modules) - /* add the modules that generates random numbers in the ModulesFile */ + /* paste them at the end of the file */ ; ModulesFile(id, <conc>(<id>, rand-gen-modules)) /* remove array accesses: x[i] -> x_i */ - ; topdown(try(remove-array-accesses)) + ; bottomup(try(remove-array-accesses)) /* re-order modules so that all declarations appear before commands */ ; ModulesFile(id, map(try(reorder-module-contents))) rules + DesugarUnaryOps: + Plus(Int(i)) -> Int(i) + + DesugarUnaryOps: + Plus(Double(i)) -> Double(i) + + DesugarUnaryOps: + Minus(Int(i)) -> Int(j) where <mulS>(i, "-1") => j + + DesugarUnaryOps: + Minus(Double(i)) -> Double(j) where <mulS>(i, "-1") => j + DesugarRightShift: |[ e1 >> e2 ]| -> |[ e1 / func(pow, 2, e2) ]| @@ -92,51 +109,8 @@ //|[ if e then s* end ]| -> |[ if e then s* else end ]| MetaIf(e, m*) -> MetaIf(e, m*, []) - /** rand(x) -> rand(0, x) */ - DesugarRand: - Rand([arg]) -> Rand([Int("0"), arg]) - - EvalRand: - Rand(args) -> Identifier(rand-var) - where ?current-term - ; if not( !args => [from, to] ) then - err-msg(|<concat-strings>["invalid call to XRM builtin: rand", - " takes either one or two arguments"]) - ; !current-term; debug; <xtc-exit> 4 - end - ; <prism-desugar> from => from' - ; <prism-desugar> to => to' - ; if not( !from' => Int(ifrom); !to' => Int(ito) ) then - err-msg(|<concat-strings>["invalid call to XRM builtin: rand's", - " arguments must be statically evaluable"]) - ; !current-term; debug; <xtc-exit> 4 - end - ; <debug> ifrom - ; <debug> ito - ; <newname> "__rand" => rand-var - ; !ProbUpdate( Div(Int("1"), Int( <subtS>(ito, ifrom) )) - , UpdateList([UpdateElement(IdentifierPrime(rand-var), FIXME())])) - ; {| RandUpdateList: - for-loop(gen-rand-update-list | ifrom, ito, "1", []) - ; bagof-RandUpdateList - |} - ; reverse - ; !ProbUpdateList(<id>) => u - ; !|[ module ~id:rand-var - ~id:rand-var : [~int:ifrom..~int:ito]; - [] true -> u; - endmodule ]| => rand-gen-module - ; rules(RandGenModules:+ _ -> rand-gen-module) - -strategies - - gen-rand-update-list(|i, data) = - topdown(try(\ FIXME() -> Int(i) \)) => rand-update - ; rules(RandUpdateList:+ _ -> rand-update) - signature constructors Type : String -> Type - FIXME : FIXME strategies Index: src/str/eval-meta-code.str --- src/str/eval-meta-code.str (revision 41) +++ src/str/eval-meta-code.str (working copy) @@ -9,7 +9,7 @@ ** Sorry if it makes the source a bit overloaded with comments. ** ** If you want to enable debugging simply use: -** sed 's@///\*@/*@g' < eval-meta-code.str > .tmp +** sed 's@/\*@/*@g' < eval-meta-code.str > .tmp ** mv .tmp eval-meta-code.str */ module eval-meta-code @@ -48,15 +48,26 @@ strategies unroll-meta-loops = - ?MetaFor(meta-var, Int(from), Int(to), Int(step), body) - ; where(check-loop-validity(|meta-var, from, to)) + ?MetaFor(meta-var, from, to, step, body) + /* reduce the fields from to and step down to simple integers */ + ; where( <prism-desugar> from => from' + ; <prism-desugar> to => to' + ; <prism-desugar> step => step' + ) + /* check whether the loop is valid */ + ; where(check-loop-validity(|meta-var, from', to', step')) + /* bind the integers of the fields from to and step */ + ; where(!from' => Int(ifrom) + ; !to' => Int(ito) + ; !step' => Int(istep) + ) ; {| MetaCode: ///*DEBUG*/say(!" @@@ unroll-meta-loops: starting:") ///*DEBUG*/; printf(|" meta-var = ", meta-var) - ///*DEBUG*/; printf(|" from = ", from) - ///*DEBUG*/; printf(|" to = ", to); + ///*DEBUG*/; printf(|" from = ", ifrom) + ///*DEBUG*/; printf(|" to = ", ito); where(<check-meta-var-unicity> meta-var) - ; for-loop(gen-meta-code | from, to, step, []) + ; for-loop(gen-meta-code | ifrom, ito, istep, []) ///*DEBUG*/; say(!" ~~~ unroll-meta-loops: before bagof-MetaModule") ///*DEBUG*/; debug ; bagof-MetaCode @@ -65,8 +76,15 @@ ///*DEBUG*/; debug |} - check-loop-validity(|meta-var, from, to) = - if <gtS>(from, to) then + check-loop-validity(|meta-var, from, to, step) = + if not(!from => Int(_); !to => Int(_); !step => Int(_)) then + err-msg(|<concat-strings>["invalid meta for loop: the value of the ", + "fields `from', `to' and `step' must be ", + "statically evaluable down to a ", + "simple integer"]) + ; <xtc-exit> 2 + end + ; if <gtS>(from, to) then !meta-var => Identifier(idf) ; err-msg(|<concat-strings>["bad `for' loop on the meta-var ", idf, " starts at ", from, Index: src/str/builtin-rand.str --- src/str/builtin-rand.str (revision 0) +++ src/str/builtin-rand.str (revision 0) @@ -0,0 +1,74 @@ +/** +** This sub-module handles the XRM builtin rand. +** rand(x) generates a random value (at runtime) between 0 and x (inclusive) +** rand(x) is first desugared to rand(0, x). +** rand(x, y) generates a random value between x and y (inclusive). +** +** Here is how it works with rand(y, x) +** 1. Check that rand is called with the correct number of arguments. +** 2. Apply prism-desugar to those arguments in order to reduce them down +** to simple integers [Int(..)] +** 3. Generate a module with a single command which have a list of updates +** which the same probability [1/(x-y+1)] +*/ +module builtin-rand + +rules + + /** rand(x) -> rand(0, x) */ + DesugarRand: + Rand([arg]) -> Rand([Int("0"), arg]) + + EvalRand: + Rand(args) -> Identifier(rand-var) + where ?current-term // save the current term for error messages + /* check that rand is called with exactly two arguments */ + ; if not( !args => [from, to] ) then + err-msg(|<concat-strings>["invalid call to XRM builtin: rand", + " takes either one or two arguments"]) + ; !current-term; debug; <xtc-exit> 4 + end + /* desugar (constant propagation) to make both arguments simple Int */ + ; <prism-desugar> from => from' + ; <prism-desugar> to => to' + /* check that both arguments are simple Int */ + ; if not( !from' => Int(ifrom); !to' => Int(ito) ) then + err-msg(|<concat-strings>["invalid call to XRM builtin: rand's", + " arguments must be statically evaluable"]) + ; !current-term; debug; <xtc-exit> 4 + end + ; if <gtS>(ifrom, ito) then + err-msg(|<concat-strings>["invalid call to XRM builtin: ", + "rand(x,y) where x > y"]) + ; !current-term; debug; <xtc-exit> 4 + end + /* generate a name for the random variable */ + ; <newname> "__rand" => rand-var + /* template: 1/(ito-ifrom+1):(rand-var'=FIXME) */ + ; !ProbUpdate( Div(Int("1"), Int( <addS>(<subtS>(ito, ifrom), "1") )) + , UpdateList([UpdateElement(IdentifierPrime(rand-var), FIXME())])) + /* generate the updates by replacing the FIXME */ + ; {| RandUpdateList: + for-loop(gen-rand-update-list | ifrom, ito, "1", []) + ; bagof-RandUpdateList + |} + ; reverse // bagof gives us the list in reverse order + /* put our update list in the correct AST node */ + ; !ProbUpdateList(<id>) => u + /* inject that node in a module */ + ; !|[ module ~id:rand-var + ~id:rand-var : [~int:ifrom..~int:ito]; + [] true -> u; + endmodule ]| => rand-gen-module + /* save this module in a DR for later retrieval */ + ; rules(RandGenModules:+ _ -> rand-gen-module) + +strategies + + gen-rand-update-list(|i, data) = + topdown(try(\ FIXME() -> Int(i) \)) => rand-update + ; rules(RandUpdateList:+ _ -> rand-update) + +/* node to replace in templates */ +signature constructors + FIXME : FIXME Index: src/str/xrm-front.str --- src/str/xrm-front.str (revision 41) +++ src/str/xrm-front.str (working copy) @@ -133,8 +133,8 @@ <tool-doc> [ Usage("xrm-front [OPTIONS]") , Summary("Transforms an eXtended Reactive Module source file in a - PRISM-equivalent abstract syntax tree (default) or source - code. (see option -P)") + PRISM-equivalent source code (default) or abstract syntax + tree. (see option -A)") , OptionUsage() , AutoReportBugs() ] Index: src/str/builtin-rand.meta --- src/str/builtin-rand.meta (revision 0) +++ src/str/builtin-rand.meta (revision 0) @@ -0,0 +1 @@ +Meta([Syntax("StrategoXRM")]) Index: src/syn/xrm/XRM-MetaFor.sdf --- src/syn/xrm/XRM-MetaFor.sdf (revision 41) +++ src/syn/xrm/XRM-MetaFor.sdf (working copy) @@ -7,27 +7,31 @@ %% EBNF Grammar: Meta For Loops %% (* Meta For loops at the top level *) %% ModulesFileSection ::= - %% "for" Identifier "from" Int "to" Int ["step" Int] "do" + %% "for" Identifier "from" Expression "to" Expression + %% ["step" Expression] "do" %% {ModulesFileSection} "end" %% %% (* Meta For loops inside modules *) %% DeclarationOrCommand ::= - %% "for" Identifier "from" Int "to" Int ["step" Int] "do" + %% "for" Identifier "from" Expression "to" Expression + %% ["step" Expression] "do" %% {DeclarationOrCommand} "end" context-free syntax %% This MetaFor can be found only at top-level %% So we can see it as a ModulesFileSection - "for" Identifier "from" Int "to" Int "do" ModulesFileSection* "end" + "for" Identifier "from" Expression "to" Expression "do" + ModulesFileSection* "end" -> ModulesFileSection {cons("MetaFor")} - "for" Identifier "from" Int "to" Int "step" Int "do" + "for" Identifier "from" Expression "to" Expression "step" Expression "do" ModulesFileSection* "end" -> ModulesFileSection {cons("MetaFor")} %% This MetaFor can be found only inside Modules %% So we can see it as a DeclarationOrCommand - "for" Identifier "from" Int "to" Int "do" DeclarationOrCommand* "end" + "for" Identifier "from" Expression "to" Expression "do" + DeclarationOrCommand* "end" -> DeclarationOrCommand {cons("MetaFor")} - "for" Identifier "from" Int "to" Int "step" Int "do" + "for" Identifier "from" Expression "to" Expression "step" Expression "do" DeclarationOrCommand* "end" -> DeclarationOrCommand {cons("MetaFor")} Index: src/syn/prism/PRISM-Expression.sdf --- src/syn/prism/PRISM-Expression.sdf (revision 41) +++ src/syn/prism/PRISM-Expression.sdf (working copy) @@ -27,8 +27,8 @@ %% | Expression ">=" Expression %% | Expression ">" Expression %% (* Notations for describing ranges in tests *) - %% | Expression "=" (Single | Range) {Single | Range} - %% | Expression "!=" (Single | Range) {Single | Range} + %% | Expression "=" Range {"," Range} + %% | Expression "!=" Range {"," Range} %% | "!" Expression %% | Expression "&" Expression %% | Expression "|" Expression @@ -46,9 +46,8 @@ %% | "func" "(" "floor" "," Expression {"," Expression} ")" %% | "func" "(" "ceil" "," Expression {"," Expression} ")" %% - %% Single ::= Expression - %% - %% Range ::= Expression ".." Expression + %% Range ::= Expression + %% | Expression ".." Expression %% EBNF Grammar: Expressions as in PRISM's parser %% Expression ::= ExpressionITE Index: TODO --- TODO (revision 41) +++ TODO (working copy) @@ -31,6 +31,8 @@ static const int N = -1; will issue an error such as "undeclared meta variable N" whereas the real problem is that array[N] couldn't be expanded. + * Labels seems to be b0rken in parse-prism. + ## ---------- ## ## Extensions ## ## ---------- ## @@ -48,10 +50,6 @@ declared variables (globals, formulas, local declarations etc.) and ensure (in check-meta-vars) that their identifiers are unique. - * Add a "rand" builtin. Eg: - rand(50) -> random value between 0 and 50 (included) - rand(42, 50) -> random value between 42 and 50 (included) - * Add a sanity check after xrm-front has finished to generate everything in order to ensure that each module/var decl has a unique name. @@ -103,6 +101,14 @@ * Add parameterized formulas. (Pretty much like macro-functions in C) + * Check why for i from -1 to -4 is not caught as an error. + + * Add scopes for meta variables + eg: for i ... do + for i ... // `i' shadows its previous definition + end + end + ## -------------- ## ## Desugarisation ## ## -------------- ## @@ -137,6 +143,7 @@ - 2: error with meta-vars (eg: undefined meta-var, redefined meta-var) - 3: arithmetic error when evaluating code (eg: division/modulo by 0) - 4: invalid call to a builtin (eg rand(1,2,3)) + - 5: invalid array access (eg: subscript is not a positive integer) - 42: internal compiler error - 51: not yet implemented @@ -196,3 +203,7 @@ * Desugarise ranges (?) x = 1..5,7,10..13 ==> (x>=1 & x<=5) | (x=7) | (x>=10 & x<=13) + + * Add a "rand" builtin. Eg: + rand(50) -> random value between 0 and 50 (included) + rand(42, 50) -> random value between 42 and 50 (included)