[Projects] XRM 43: Fix the XRM rand builtin for negative numbers.

https://svn.lrde.epita.fr/svn/xrm/trunk Index: ChangeLog from SIGOURE Benoit &lt;sigoure.benoit(a)lrde.epita.fr&gt; Fix the XRM rand builtin for negative numbers. rand(-1) was desugared to rand(0, -1) instead of rand(-1, 0) * src/str/xrm-to-prism.str: Move DesugarUnaryOps... * src/str/prism-desugar.str: Here. * src/str/builtin-rand.str (DesugarRand): Allow negative numbers. * src/str/desugar-array-accesses.str: Fix a flowed check which allowed negative array accesses when they came after a good array access. * src/syn/prism/README: New. * src/syn/prism/PRISM-Expression.sdf: Remove a FIXME. See the README. * tests/xrm/for-with-exps.xpm: New. * tests/xrm/negative-rand.xpm: New. * TODO: Bring up to date. TODO | 18 ++++++++- src/str/builtin-rand.str | 27 +++++++++++--- src/str/desugar-array-accesses.str | 2 - src/str/prism-desugar.str | 19 ++++++++++ src/str/xrm-to-prism.str | 15 -------- src/syn/prism/PRISM-Expression.sdf | 6 +-- src/syn/prism/README | 68 +++++++++++++++++++++++++++++++++++++ tests/xrm/for-with-exps.xpm | 9 ++++ tests/xrm/negative-rand.xpm | 4 ++ 9 files changed, 142 insertions(+), 26 deletions(-) Index: src/str/xrm-to-prism.str --- src/str/xrm-to-prism.str (revision 42) +++ src/str/xrm-to-prism.str (working copy) @@ -36,8 +36,7 @@ xrm-to-prism = /* remove XRM sugar, normalize some nodes */ innermost( - DesugarUnaryOps // keep this first - <+ DesugarRightShift <+ DesugarLeftShift + DesugarRightShift <+ DesugarLeftShift <+ DesugarImplicitForStep <+ DesugarImplicitElse <+ DesugarRand <+ EvalRand ) @@ -81,18 +80,6 @@ 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) ]| Index: src/str/prism-desugar.str --- src/str/prism-desugar.str (revision 42) +++ src/str/prism-desugar.str (working copy) @@ -19,6 +19,7 @@ prism-desugar-first-pass ; innermost( RemoveUnconditionnalUpdates + <+ DesugarUnaryOps // keep this before the following rules <+ AddZero <+ MulOne <+ MulZero <+ DivOne <+ catch-div-by-zero <+ EvalPlus <+ EvalMinus <+ EvalMul <+ EvalDiv <+ EvalLt <+ EvalLtEq <+ EvalGt <+ EvalGtEq <+ EvalEq <+ EvalNotEq @@ -131,6 +132,24 @@ |[ e / 1D ]| -> |[ e ]| /* +** Simplify the AST by removing unary operators where possible. +*/ + +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 + +/* ** ## ==================== ## ** ## Constant propagation ## ** ## ==================== ## Index: src/str/builtin-rand.str --- src/str/builtin-rand.str (revision 42) +++ src/str/builtin-rand.str (working copy) @@ -15,9 +15,22 @@ rules - /** rand(x) -> rand(0, x) */ + /** rand(x) -> rand(0, x) if x >= 0 + ** rand(x) -> rand(x, 0) if x < 0 */ DesugarRand: - Rand([arg]) -> Rand([Int("0"), arg]) + Rand([arg]) -> Rand([arg1, arg2]) + where ?current-term + ; <prism-desugar> arg => arg' + ; if not( !arg' => Int(iarg) ) then + <invalid-call-to-rand-non-int> current-term + end + ; if <ltS>(iarg, "0") then + !Int("0") => arg2 + ; !arg' => arg1 + else + !Int("0") => arg1 + ; !arg' => arg2 + end EvalRand: Rand(args) -> Identifier(rand-var) @@ -33,9 +46,7 @@ ; <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 + <invalid-call-to-rand-non-int> current-term end ; if <gtS>(ifrom, ito) then err-msg(|<concat-strings>["invalid call to XRM builtin: ", @@ -69,6 +80,12 @@ topdown(try(\ FIXME() -> Int(i) \)) => rand-update ; rules(RandUpdateList:+ _ -> rand-update) + invalid-call-to-rand-non-int = + err-msg(|<concat-strings>["invalid call to XRM builtin: rand's", + " arguments must be statically evaluable"]) + ; debug + ; <xtc-exit> 4 + /* node to replace in templates */ signature constructors FIXME : FIXME Index: src/str/desugar-array-accesses.str --- src/str/desugar-array-accesses.str (revision 42) +++ src/str/desugar-array-accesses.str (working copy) @@ -36,7 +36,7 @@ /* Now we have a list of strings such as: ["1", "2", ...] * Check that the list only contains positive integers as strings */ - ; try(map(string-to-int; neg; invalid-array-access)) + ; map(try(string-to-int; neg; invalid-array-access)) /* Insert underscores between each integer */ ; separate-by(|"_") Index: src/syn/prism/README --- src/syn/prism/README (revision 0) +++ src/syn/prism/README (revision 0) @@ -0,0 +1,68 @@ +About the "=" and "!=" operators +-------------------------------- + +We would like to make "=" and "!=" non-associative. Actually it's worse than +that since we would like to disallow expressions such as 1=2=3 at all, whether +they are parenthesized or not. + +One idea could be to make "=" and "!=" non-associative in a first time and +then reject invalid productions in a second time using SDF priorities. +(The following stuff have been explained by Martin Bravenboer) + +here are the two derivations that you want to reject: +----------------------------------------------------------------------------- +$ echo "0 = 1 = 2" | sglri -p PRISM.tbl | pp-aterm +amb( + [ Eq( + Eq(Int("0"), [Int("1")]) + , [Int("2")] + ) + , Eq( + Int("0") + , [Eq(Int("1"), [Int("2")])] + ) + ] +) +----------------------------------------------------------------------------- + +The first one *can* be rejected with the non-assoc attribute: + + Expr "=" {Range ","}+ -> Expr {cons("Eq"), non-assoc} + +----------------------------------------------------------------------------- +$ echo "0 = 1 = 2" | sglri -p PRISM.tbl | pp-aterm +Eq( + Int("0") +, [Eq(Int("1"), [Int("2")])] +) +----------------------------------------------------------------------------- + +The second one is more tricky, and indeed the associativity attribute +does not work for this derivation, since the right-hand side of the Eq +expression only indirectly produces an Eq. What we want to reject is +the following derivation: + +Expr "=" {Range ","}+ -> Expr + +where Range is produced by Expr -> Range +where Expr is produced by Expr "=" {Range ","}+ -> Expr + +We can reject this associated Eq by defining a priority that rejects Eq +expressions as ranges: + + context-free priorities + Expr -> Range + > Expr "=" {Range ","}+ -> Expr + +This seems to work but due to the transitivity of priorities, this also +rejects all expressions on the right-hand side of Eq that have lower +priority than the Eq itself. + +This is a real problem because (for instance) logical operators have a lower +priority than the "=" sign. Therefore, with the above priorities, it is +impossible to write 1=2&3 (for instance). + +Hence we chose to ignore the problem completely and leave the ambiguity. +parse-prism and parse-xrm invoke sglr with the -A option which tells sglr to +treat ambiguities as errors. This dirty workaround enables us to reject +invalid input such as 1=2=3. Index: src/syn/prism/PRISM-Expression.sdf --- src/syn/prism/PRISM-Expression.sdf (revision 42) +++ src/syn/prism/PRISM-Expression.sdf (working copy) @@ -136,11 +136,9 @@ Expression ">" Expression -> Expression {non-assoc,cons("Gt")} %% Notations for describing ranges in tests - %%Expression "=" Expression ({(Expression (".." Expression)?) ","}*)? - %% FIXME: disallow associativy for this construction: + %% NOTE: The two following rules should have a `non-assoc' keyword + %% which is omitted on purpose. See the README in this folder. Expression "=" {Range ","}+ -> Expression {cons("Eq")} - %%Expression "!=" Expression ({(Expression (".." Expression)?) ","}*)? - %% FIXME: disallow associativy for this construction: Expression "!=" {Range ","}+ -> Expression {cons("NotEq")} "!" Expression -> Expression {cons("Not")} Index: tests/xrm/for-with-exps.xpm --- tests/xrm/for-with-exps.xpm (revision 0) +++ tests/xrm/for-with-exps.xpm (revision 0) @@ -0,0 +1,9 @@ +for i from +42-21*+2 to +3 do // 0 to 3 + for j from -1 to i*2 do + if j >= 0 then + const int x[i][j] = i * 42 - j; + else + const int x[i][-1*j + i*2+1] = i * 42 - j; + end + end +end Index: tests/xrm/negative-rand.xpm --- tests/xrm/negative-rand.xpm (revision 0) +++ tests/xrm/negative-rand.xpm (revision 0) @@ -0,0 +1,4 @@ +module test + x : [-42..42]; + [] true -> x'=rand(-10); +endmodule Index: TODO --- TODO (revision 42) +++ TODO (working copy) @@ -13,8 +13,6 @@ * Add tests using "system ... endsystem" (it's properly not parsed atm) - * Disallow associativity for the "=" and "!=" operators. - * Write some sort of formal descriptions of the extensions offered. * Add more tests. Add tests which actually do check that the generated code @@ -134,6 +132,19 @@ [] x=3 -> ... // x=3 is impossible [] x=0 -> (x'=3) // x=3 is not in the definition range of x + ## ----- ## + ## Notes ## + ## ----- ## + + * PRISM's parser doesn't allow negative values in ranges for variables. + eg: x : [-42..42]; + + * PRISM's parser doesn't allow ranges for variables which start and end + with the same values. + eg: x : [42..42]; + // idea: could we fix this by transforming x in a const int? + // -> needs to ensure that x isn't updated anywhere. + ## ------------- ## ## Documentation ## ## ------------- ## @@ -207,3 +218,6 @@ * Add a "rand" builtin. Eg: rand(50) -> random value between 0 and 50 (included) rand(42, 50) -> random value between 42 and 50 (included) + + * Disallow associativity for the "=" and "!=" operators: won't fix (see + src/syn/prism/README)