June 2006 - Projects

XRM 50: Fix static_rand.
by SIGOURE Benoit 08 Jun '06

08 Jun '06

https://svn.lrde.epita.fr/svn/xrm/trunk Index: ChangeLog from SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> Fix static_rand. * src/str/xrm-to-prism.str: Evaluate static_rand calls at the end of the transformation pipeline (that is, after meta-code evaluation). * src/str/prism-desugar.str: Evaluate static_rand in prism-desugar. * src/str/builtin-rand.str: Introduce EvalStaticRand. * TODO: Add something to do. TODO | 3 +++ src/str/builtin-rand.str | 2 +- src/str/prism-desugar.str | 2 ++ src/str/xrm-to-prism.str | 2 +- 4 files changed, 7 insertions(+), 2 deletions(-) Index: src/str/xrm-to-prism.str --- src/str/xrm-to-prism.str (revision 49) +++ src/str/xrm-to-prism.str (working copy) @@ -78,7 +78,7 @@ * This must come AFTER collect-static-const-decl since we might need * to expand an arrays which rely on static const variables. */ - ; topdown(try(array-decl-desugar)) + ; topdown(try(array-decl-desugar); try(EvalStaticRand)) ; notice-msg(|"xrm-to-prism: array declarations desugared") /* flatten nested lists */ Index: src/str/prism-desugar.str --- src/str/prism-desugar.str (revision 49) +++ src/str/prism-desugar.str (working copy) @@ -2,6 +2,7 @@ imports PRISM reals + builtin-rand strategies @@ -25,6 +26,7 @@ <+ EvalLt <+ EvalLtEq <+ EvalGt <+ EvalGtEq <+ EvalEq <+ EvalNotEq <+ EvalAnd <+ EvalOr <+ EvalMin <+ EvalMax <+ EvalFloor <+ EvalCeil <+ EvalPow <+ EvalMod + <+ (EvalStaticRand; IntToDouble) ) ; topdown(try(SimplifyDoubles <+ TruncateDouble)) Index: src/str/builtin-rand.str --- src/str/builtin-rand.str (revision 49) +++ src/str/builtin-rand.str (working copy) @@ -66,7 +66,7 @@ /* save this module in a DR for later retrieval */ ; rules(RandGenModules:+ _ -> rand-gen-module) - EvalRand: + EvalStaticRand: StaticRand(args) -> Int(rand-val) where check-rand-args(|"static_rand", args) => (from, to) ; rand(|<string-to-int> from, <string-to-int> to) Index: TODO --- TODO (revision 49) +++ TODO (working copy) @@ -30,6 +30,9 @@ 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. + * Rewrite src/lib/native/rand.c in Stratego. (This has been written in C + because I failed to make it work properly in Stratego :|) + ## ---------- ## ## Extensions ## ## ---------- ##

1 0

XRM 49: Add the static_rand builtin.
by SIGOURE Benoit 08 Jun '06

08 Jun '06

https://svn.lrde.epita.fr/svn/xrm/trunk Index: ChangeLog from SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> Add the static_rand builtin. NOTE: Some C was needed to implement rand(from, to) because for some reason I didn't succeed in writing something equivalent in Stratego. For some reason, the numbers I generated were all too small. * src/tools/pp-xrm.str: Remove a FIXME. * src/tools/pp-prism.str: Ditto. * src/lib/xrm/pp/xrm-expression.str: Add boxing for static_rand. * src/lib/native/rand.c: New. * src/lib/native/Makefile.am: Add rand.c. * src/str/prism-desugar.str (prism-desugar-first-pass): Re-order calls and correct a minor bug. * src/str/builtin-rand.str: Handle static_rand. * src/str/xrm-front.str: Set a random seed before the main transformation pipeline starts. * src/syn/xrm/XRM-Expression.sdf: Add static_rand. lib/native/Makefile.am | 5 +- lib/native/rand.c | 27 +++++++++++ lib/xrm/pp/xrm-expression.str | 5 ++ str/builtin-rand.str | 101 ++++++++++++++++++++++++++++++------------ str/prism-desugar.str | 8 +-- str/xrm-front.str | 1 syn/xrm/XRM-Expression.sdf | 9 +++ tools/pp-prism.str | 2 tools/pp-xrm.str | 2 9 files changed, 124 insertions(+), 36 deletions(-) Index: src/tools/pp-xrm.str --- src/tools/pp-xrm.str (revision 48) +++ src/tools/pp-xrm.str (working copy) @@ -22,7 +22,7 @@ ?(<read-from-stream>, out-file) ; pp-xrm-to-abox ; box2text-stream(|80, out-file) - // FIXME: a final \n is missing + ; <fputs> ("\n", out-file) /** * Documentation Index: src/tools/pp-prism.str --- src/tools/pp-prism.str (revision 48) +++ src/tools/pp-prism.str (working copy) @@ -22,7 +22,7 @@ ?(<read-from-stream>, out-file) ; pp-prism-to-abox ; box2text-stream(|80, out-file) - // FIXME: a final \n is missing + ; <fputs> ("\n", out-file) /** * Documentation Index: src/lib/xrm/pp/xrm-expression.str --- src/lib/xrm/pp/xrm-expression.str (revision 48) +++ src/lib/xrm/pp/xrm-expression.str (working copy) @@ -21,3 +21,8 @@ Rand(args) // because func(rand, ...) is just uggly. -> box |[ H hs=0 [ KW["rand"] "(" H hs=1 [ ~args-imploded ] ")" ] ]| where <implode-list(|",")> args => args-imploded + + prism-to-box: + StaticRand(args) + -> box |[ H hs=0 [ KW["static_rand"] "(" H hs=1 [~args-imploded] ")" ] ]| + where <implode-list(|",")> args => args-imploded Index: src/lib/native/rand.c --- src/lib/native/rand.c (revision 0) +++ src/lib/native/rand.c (revision 0) @@ -0,0 +1,27 @@ +/* +** rand.c for str-reals in /home/tsuna/work/xrm/trunk/src/lib/native +** +** Made by SIGOURE Benoit +** Mail <sigoure.benoit(a)lrde.epita.fr> +** +** Started on Tue Jun 6 15:13:53 2006 SIGOURE Benoit +** Last update Tue Jun 6 15:23:57 2006 SIGOURE Benoit +*/ + +#include <stdlib.h> +#include "libstr-reals.h" + +ATerm STR_REALS_rand(ATerm from, ATerm to) +{ + int ifrom; + int ito; + int r; + + if((ATgetType(from) != AT_REAL && ATgetType(from) != AT_INT) || + (ATgetType(to) != AT_REAL && ATgetType(to) != AT_INT)) + return NULL; + NUMERIC_ATERM_TO_REAL(ifrom, from); + NUMERIC_ATERM_TO_REAL(ito, to); + r = ifrom + (unsigned)((float)(ito - ifrom + 1) * rand() / (RAND_MAX + 1.)); + return (ATerm) ATmakeInt(r); +} Index: src/lib/native/Makefile.am --- src/lib/native/Makefile.am (revision 48) +++ src/lib/native/Makefile.am (working copy) @@ -5,7 +5,7 @@ ## Mail <sigoure.benoit(a)lrde.epita.fr> ## ## Started on Wed May 10 19:27:12 2006 SIGOURE Benoit -## Last update Thu May 25 20:19:00 2006 SIGOURE Benoit +## Last update Tue Jun 6 15:13:38 2006 SIGOURE Benoit ## include $(top_srcdir)/config/toplevel.mk @@ -16,7 +16,8 @@ libstr_reals_la_SOURCES = $(include_HEADERS) \ ceil.c \ floor.c \ - power.c + power.c \ + rand.c # FIXME: Detect in configure whether -lm needs to be used. libstr_reals_la_LIBADD = $(SSL_LIBS) -lm Index: src/str/prism-desugar.str --- src/str/prism-desugar.str (revision 48) +++ src/str/prism-desugar.str (working copy) @@ -41,13 +41,13 @@ ** formulas and ExpandFormulas. */ prism-desugar-first-pass = - ConstInt(id, prism-desugar) + ?Int(_); IntToDouble + <+ ExpandStaticConsts; prism-desugar-first-pass // we must desugar the + <+ ExpandFormulas; prism-desugar-first-pass // expansed code. + <+ ConstInt(id, prism-desugar) <+ ConstDouble(id, prism-desugar) <+ ConstBool(id, prism-desugar) <+ FormulaDef(id, prism-desugar) - <+ ?Int(_); IntToDouble - <+ ExpandStaticConsts - <+ ExpandFormulas <+ all(prism-desugar-first-pass) rules Index: src/str/builtin-rand.str --- src/str/builtin-rand.str (revision 48) +++ src/str/builtin-rand.str (working copy) @@ -20,48 +20,39 @@ ** rand(x) -> rand(x, 0) if x < 0 */ DesugarRand: Rand([arg]) -> Rand([arg1, arg2]) - where ?current-term + where desugar-rand(|arg) => (arg1, arg2) + + DesugarRand: + StaticRand([arg]) -> StaticRand([arg1, arg2]) + where desugar-rand(|arg) => (arg1, arg2) + +strategies + + desugar-rand(|arg) = + ?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 + !(arg', Int("0")) else - !Int("0") => arg1 - ; !arg' => arg2 + !(Int("0"), arg') end +rules + 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 - <invalid-call-to-rand-non-int> current-term - 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 + where check-rand-args(|"rand", args) => (from, to) /* 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") )) + /* template: 1/(to-from+1):(rand-var'=FIXME) */ + ; !ProbUpdate( Div(Int("1"), Int( <addS>(<subtS>(to, from), "1") )) , UpdateList([UpdateElement(IdentifierPrime(rand-var), FIXME())])) /* generate the updates by replacing the FIXME */ ; {| RandUpdateList: - for-loop(gen-rand-update-list | ifrom, ito, "1", []) + for-loop(gen-rand-update-list | from, to, "1", []) ; bagof-RandUpdateList |} ; reverse // bagof gives us the list in reverse order @@ -69,12 +60,52 @@ ; !ProbUpdateList(<id>) => u /* inject that node in a module */ ; !|[ module ~id:rand-var - ~id:rand-var : [~int:ifrom..~int:ito]; + ~id:rand-var : [~int:from..~int:to]; [] true -> u; endmodule ]| => rand-gen-module /* save this module in a DR for later retrieval */ ; rules(RandGenModules:+ _ -> rand-gen-module) + EvalRand: + StaticRand(args) -> Int(rand-val) + where check-rand-args(|"static_rand", args) => (from, to) + ; rand(|<string-to-int> from, <string-to-int> to) + ; int-to-string => rand-val + +strategies + + /** + ** Ensure that the arguments passed to rand or static_rand builtin are + ** correct: + ** - It must have exactly two arguments. + ** - Both arguments must be statically evaluable as Int(_). + ** - The first argument must be lesser than or equal to the second. + ** @param builtin-name: String used in error messages + ** @param args: arguments of the builtin call + ** @return (to, from) where to and from are integers. + */ + check-rand-args(|builtin-name, args) = + ?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: ", + builtin-name, " 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 + <invalid-call-to-rand-non-int> current-term + end + ; if <gtS>(ifrom, ito) then + err-msg(|<concat-strings>["invalid call to XRM builtin: ", + builtin-name, "(x,y) where x > y"]) + ; !current-term; debug; <xtc-exit> 4 + end + ; !(ifrom, ito) + strategies gen-rand-update-list(|i, data) = @@ -86,3 +117,17 @@ " arguments must be statically evaluable"]) ; debug ; <xtc-exit> 4 + +strategies + + /** + ** Returns a random integer between `from' and `to' (included). + ** @param from Integer + ** @param to Integer + ** @return Integer + ** @warning You must call <set-random-seed> seed before calling this + ** strategy, otherwise every run will generate the same sequence of + ** random numbers. + */ + rand(|from, to) = + prim("STR_REALS_rand", from, to) Index: src/str/xrm-front.str --- src/str/xrm-front.str (revision 48) +++ src/str/xrm-front.str (working copy) @@ -40,6 +40,7 @@ /** pipeline of transformations performed by xrm-front */ xrm-front-pipeline = notice-msg(|"transformation pipeline starting") + ; where(<set-random-seed> (<time>)) ; xrm-to-prism ; dbg(|"xrm-to-prism finished") ; if must-desugar then Index: src/syn/xrm/XRM-Expression.sdf --- src/syn/xrm/XRM-Expression.sdf (revision 48) +++ src/syn/xrm/XRM-Expression.sdf (working copy) @@ -14,8 +14,10 @@ %% ExpressionFunc ::= %% (* older builtin functions for backwards compat. *) %% "rand" "(" Expression {"," Expression} ")" + %% | "static_rand" "(" Expression {"," Expression} ")" %% (* builtin functions calls using the "func" notation *) %% | "func" "(" "rand" "," Expression {"," Expression} ")" + %% | "func" "(" "static_rand" "," Expression {"," Expression} ")" context-free syntax ArrayAccess -> Expression @@ -27,9 +29,16 @@ ArrayAccess "?=" {Range ","}+ -> Expression {cons("ExistsEq")} ArrayAccess "?!=" {Range ","}+ -> Expression {cons("ExistsNotEq")} + %% rand builtin "rand" "(" {Expression ","}+ ")" -> Expression {cons("Rand")} "func" "(" "rand" "," {Expression ","}+ ")" -> Expression {cons("Rand")} + %% static rand builtin + "static_rand" "(" {Expression ","}+ ")" + -> Expression {cons("StaticRand")} + "func" "(" "static_rand" "," {Expression ","}+ ")" + -> Expression {cons("StaticRand")} + %% NOTE: remember: priorities are transitive in SDF. %% The following priorities are marked either with "inherited" or "new". %% The former means that these priorities are inherited from the base

1 0

Re: XRM 47: Fix array declarations.
by Akim Demaille 08 Jun '06

08 Jun '06

>>> "SIGOURE" == SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> writes: > DesugarUnaryOps: > - Plus(Int(i)) -> Int(i) > + Plus(Int(i){a*}) -> Int(i){a*} If you don't write this, you loose the annotations?

2 2

Re: XRM 48: Use libstratego-gpp for direct pretty printing.
by Akim Demaille 08 Jun '06

08 Jun '06

>>> "SIGOURE" == SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> writes: > Use libstratego-gpp for direct pretty printing. > This is a brand new way of pretty-printing. It relies on a very > recent version of libstratego-gpp and thus requires a very recent > installation of Stratego/XT 0.17M1. > Instead of calling prism-to-abox and Abox-2-text (which implies > creating several temporary files under /tmp) pp-{prism,xrm} do the > pretty-printing themselves and then use libstratego-gpp to transform > the boxed AST into text. This is much more efficient. The point is only speed?

2 1

test
by SIGOURE Benoit 08 Jun '06

08 Jun '06

test -- SIGOURE Benoit aka Tsuna _____ /EPITA\ Promo 2008, LRDE

1 0

Re: XRM 46: Major changes: new way of handling arrays.
by Akim Demaille 07 Jun '06

07 Jun '06

>>> "SIGOURE" == SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> writes: > Major changes: new way of handling arrays. > The whole way of handling arrays in XRM has been changed. The former > way of doing it was somewhat simplistic and quickly reached its > limit. We used to have: x[1][2] represented as ArrayAccess(x, [1, 2]), > we now have: ArrayAccess(ArrayAccess(x, [1]), [2]) which means that > the expression is parenthesized as (x[1])[2]. Pretty much like in > Java/C/C++... So far it did not make sense to have this approach > since one cannot access the intermediate dimensions anyway (eg: if x > is a 2D array, say: x[3][3], it doesn't make sense, in XRM, to access > x[2] for instance). > We are moving to an approach which is more Java/C-like because we > want to be able to write things such as: x[1..3,5,7..9][1,3,5][2..6] > which is suddenly more complex than what we used to support before. > This revision provides several new features among this new way of > writing array accesses: > It is now possible to declare an array using ranges, eg: > x[1..3,7][2..4] will declare a 2D array defined only for certain > ranges (it's somewhat like sparse arrays) > It will soon be possible to write equality tests such as: > x[1..3][2,3]=0 to check whether x[1][2]=0 & x[1][3]=0 & x[2][2]=0 > etc. > Other new operators added in the grammar (but not yet implemented): > x[1..3][2,3]?=0 is there at least one of the elements > that's equal to 0? x[1..3][2,3]?!=0 same but at least one not equal. > Array declarations have been optimized since the declarations are now > directly generated instead of creating a meta-for loop that will be > later unrolled to generate them. This also introduces a problem (see > the TODO). Nice and well documented: congrats!

1 0

Re: XRM 43: Fix the XRM rand builtin for negative numbers.
by Akim Demaille 07 Jun '06

07 Jun '06

>>> "SIGOURE" == SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> writes: > +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. How about choosing the simplest path: a simple type-checking pass?

2 1

Re: XRM 38: Add support for ranges in constant propagation.
by Akim Demaille 07 Jun '06

07 Jun '06

>>> "SIGOURE" == SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> writes: > /!\ This commit has all the debugging messages left in the source of > prism-desugar because it seems to trigger a bug in the Stratego > compiler. Therefore we'll be able to use this revision to investigate > the bug. Roughly, what happens is that a strategy such as: > a;b;c;...; (X <+ Y <+ Z ...) > is inlined and transformed (in C) as something like: > ((a;b;c;...;X) <+ (a;b;c;...;Y) <+ (a;b;c;...;Z) <+ ...) > which is totally wrong if a;b;c;... has side effects (such as > defining dynamic rules) Wow... So, do you confirm? How much time did this bug cost you?

2 1

Re: XRM 37: Add formulas in constant propagation.
by Akim Demaille 07 Jun '06

07 Jun '06

>>> "SIGOURE" == SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> writes: > Index: tests/xrm/static-const-arrays-desugar.xpm > --- tests/xrm/static-const-arrays-desugar.xpm (revision 0) > +++ tests/xrm/static-const-arrays-desugar.xpm (revision 0) > @@ -0,0 +1,26 @@ > +const int N = 3; > +const int array[N] = 42; > + > +module test > + x[N] : [0..N] init array[N]; > + > + [] x[array[N]]=0 -> (x[array[N]]'=1); > +endmodule > + > +// The above code will generate the following code once > +// collect-static-const-decl and array-decl-desugar have runned. > +// The problem is that the loop "hides" static const variables which > +// are not caught by collect-static-const-decl. > + > +// const int N = 3; > +// > +// for __meta_i_0 from 0 to 2 step 1 do > +// const int array[__meta_i_0] = 42; > +// end > +// > +// module test > +// for __meta_i_2 from 0 to 2 step 1 do > +// x[__meta_i_2] : [0..N] init array[N]; > +// end > +// [] x[array[N]]=0 -> (x[array[N]]'=1); > +// endmodule Nice! Rather than using comments, you should check in the genuine expected output, and compare your output to it. You may want to add option to your binary to check intermediate desugaring.

2 1

Re: XRM 31: Add array declarations (sugar).
by Akim Demaille 07 Jun '06

07 Jun '06

>>> "SIGOURE" == SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> writes: > Add array declarations (sugar). > It is now possible to declare arrays such as: b[4][3] : bool; > Multi-dimensional arrays are correctly handled. This is really nice. I would like to emphasize, though, that, unless you plan to make "b[4]" actually mean something here, the user would rather write b[4, 3]. Again, that's only sugar. > + /** > + ** Patch the list of dimensions with the meta-var used in the meta for loop. > + ** Basically this strategy generates a new meta-var used as the iterator > + ** in the meta-for loop and updates the dimensions of the declared array. > + ** The dimension updated is the first one matching Int(_) A minor nit: Please don't forget the ending period for sentences. That's a frequent mistake. > +// FIXME: Try to figure out why concrete syntax fails to work here You bet! > xrm-to-prism = > /* remove XRM sugar, normalize some nodes */ > - topdown(try(xrm-to-prism-desugar)) > + innermost(xrm-to-prism-desugar) What made you change this? > Index: tests/xrm/globals.xpm > --- tests/xrm/globals.xpm (revision 0) > +++ tests/xrm/globals.xpm (revision 0) > @@ -0,0 +1,3 @@ > +for i from 0 to 4 do > + global x[i] : bool; > +end I don't really understand how works your test suite. Shouldn't you be also checking in the expected output?

2 1