- Projects

Re: XRM 33: Add constant propagation for builtins.
by Akim Demaille 05 Jun '06

05 Jun '06

>>> "SIGOURE" == SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> writes: > https://svn.lrde.epita.fr/svn/xrm/trunk > Index: ChangeLog > from SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> > Add constant propagation for builtins. > Some C code was needed to implement easily and efficiently some > operations on reals. > The --pp-prism|-P option of xrm-front was removed and replaced by --add-pos> -P. The reason for this is that xrm-front takes PRISM code > as input and was producing PRISM AST as output, which is a bit > inconsistent. So the default is now to produce PRISM source code. > addPosInfo is now only invoked with --add-pos|-P because it is very > inefficient and introduces a big memory/time penalty. On big inputs it > will even get killed by the system. > * src/lib/xrm/Makefile.am: Remove useless include. > * src/lib/Makefile.am: Ditto. > * src/lib/prism/Makefile.am: Ditto. > * src/syn/Makefile.am: Ditto. > * src/lib/native: New. > * src/lib/native/floor.c: New. > * src/lib/native/libstr-reals.h: New. > * src/lib/native/Makefile.am: New. > * src/lib/native/ceil.c: New. > * src/lib/native/power.c: New. > * src/str/xrm-front.str: Change the -P option to be --add-pos. > * src/str/Makefile.am: Use libstr-reals. > * src/str/prism-desugar.str: Add builtins desugarisation. > * src/str/reals.str: Add more new strategies using libstr-reals. > * src/syn/prism/PRISM-MetaVars.sdf: Update the meta-var `a*'. > * src/Makefile.am: Build the `lib' subdir before `str'. > * tests/test-pp-prism.sh.in: Save the reason of the failing tests. > * tests/test-xrm-front.sh.in: Ditto. > * tests/test-parse-xrm.sh.in: Ditto. > * tests/test-parse-prism.sh.in: Ditto. > * tests/test-pp-xrm.sh.in: Ditto. > * tests/xrm/desugar_builtins.pm: New. > * configure.ac: Add src/lib/native/Makefile's generation. > * bootstrap (svn:executable): Mark as executable. C'est cool tout ça ! On dirait que tu t'interdis les fonctions shell, c'est une erreur. En particulier on dirait que tes scripts test-* pourraient être factorisés.

2 2

XRM 48: Use libstratego-gpp for direct pretty printing.
by SIGOURE Benoit 02 Jun '06

02 Jun '06

https://svn.lrde.epita.fr/svn/xrm/trunk Index: ChangeLog from SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> 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. * src/tools/Makefile.am: Add includes flags for direct pretty printing. * src/tools/pp-xrm.str: Use libstratego-gpp. * src/tools/pp-prism.str: Ditto. * src/lib/xrm/pp/xrm-to-abox.str: Move pp-xrm-to-abox... * src/lib/xrm/pp/pp-xrm-to-box.str: ...here. * src/lib/prism/pp/prism-to-abox.str: Move pp-prism-to-abox... * src/lib/prism/pp/pp-prism-to-box.str: ...here. * src/str/xrm-to-prism.str: Add a notice message. * tests/xrm/array-decl-with-meta-and-non-meta-and-exp.xpm: New test. * configure.ac: Use stratego-gpp. configure.ac | 4 + src/lib/prism/pp/pp-prism-to-box.str | 37 +++++++++++++ src/lib/prism/pp/prism-to-abox.str | 34 ------------ src/lib/xrm/pp/pp-xrm-to-box.str | 44 ++++++++++++++++ src/lib/xrm/pp/xrm-to-abox.str | 41 -------------- src/str/xrm-to-prism.str | 1 src/tools/Makefile.am | 13 ++++ src/tools/pp-prism.str | 18 +++--- src/tools/pp-xrm.str | 18 +++--- tests/xrm/array-decl-with-meta-and-non-meta-and-exp.xpm | 5 + 10 files changed, 121 insertions(+), 94 deletions(-) Index: src/tools/Makefile.am --- src/tools/Makefile.am (revision 47) +++ src/tools/Makefile.am (working copy) @@ -5,7 +5,7 @@ ## Mail <sigoure.benoit(a)lrde.epita.fr> ## ## Started on Mon May 8 21:16:56 2006 SIGOURE Benoit -## Last update Thu May 25 17:28:02 2006 SIGOURE Benoit +## Last update Fri Jun 2 17:57:09 2006 SIGOURE Benoit ## include $(top_srcdir)/config/Transformers.mk @@ -21,11 +21,20 @@ CLEANFILES = $(wildcard *.c) $(wildcard *.dep) SCFLAGS = --main main-$* -STRINCLUDES = -I $(srcdir) -I $(XTC)/share/xtc +STRINCLUDES = -I $(srcdir) -I $(XTC)/share/xtc \ + -I $(GPP)/share/sdf/gpp \ + $(STRATEGO_GPP_STRCFLAGS) \ + -I $(top_srcdir)/src/lib/prism/pp \ + -I $(top_srcdir)/src/lib/xrm/pp \ + -I $(top_builddir)/src/lib/prism/pp \ + -I $(top_builddir)/src/lib/xrm/pp \ + -I $(top_builddir)/src/sig LDADD += $(SSL_LIBS) parse_prism_SOURCES = parse-prism.c pp_prism_SOURCES= pp-prism.c +pp_prism_LDADD = $(STRATEGO_GPP_LIBS) parse_xrm_SOURCES = parse-xrm.c pp_xrm_SOURCES= pp-xrm.c +pp_xrm_LDADD = $(STRATEGO_GPP_LIBS) Index: src/tools/pp-xrm.str --- src/tools/pp-xrm.str (revision 47) +++ src/tools/pp-xrm.str (working copy) @@ -2,27 +2,27 @@ module pp-xrm imports - libxtclib // FIXME: import libstratego-xtc for strc 0.17 + libstratego-lib tool-doc + libstratego-gpp + pp-xrm-to-box strategies main-pp-xrm = - // xtc-io-wrap(extra-opts, usage, about, deps, s) - xtc-io-wrap( + // io-stream-wrap(extra-opts, usage, about, s) + io-stream-wrap( fail , pp-xrm-usage , pp-xrm-about - , !["xrm-to-abox", "abox2text"] , pp-xrm ) pp-xrm = - xtc-transform(get-2abox, pass-verbose) - ; xtc-abox2text - - get-2abox = - <get-config> "2abox" <+ !"xrm-to-abox" + ?(<read-from-stream>, out-file) + ; pp-xrm-to-abox + ; box2text-stream(|80, out-file) + // FIXME: a final \n is missing /** * Documentation Index: src/tools/pp-prism.str --- src/tools/pp-prism.str (revision 47) +++ src/tools/pp-prism.str (working copy) @@ -2,27 +2,27 @@ module pp-prism imports - libxtclib // FIXME: import libstratego-xtc for strc 0.17 + libstratego-lib tool-doc + libstratego-gpp + pp-prism-to-box strategies main-pp-prism = - // xtc-io-wrap(extra-opts, usage, about, deps, s) - xtc-io-wrap( + // io-stream-wrap(extra-opts, usage, about, s) + io-stream-wrap( fail , pp-prism-usage , pp-prism-about - , !["prism-to-abox", "abox2text"] , pp-prism ) pp-prism = - xtc-transform(get-2abox, pass-verbose) - ; xtc-abox2text - - get-2abox = - <get-config> "2abox" <+ !"prism-to-abox" + ?(<read-from-stream>, out-file) + ; pp-prism-to-abox + ; box2text-stream(|80, out-file) + // FIXME: a final \n is missing /** * Documentation Index: src/lib/xrm/pp/pp-xrm-to-box.str --- src/lib/xrm/pp/pp-xrm-to-box.str (revision 0) +++ src/lib/xrm/pp/pp-xrm-to-box.str (revision 0) @@ -0,0 +1,44 @@ +module pp-xrm-to-box +imports + Box + XRM // signature + PRISM // signature of the base language (see README) + prism-command + prism-constant + prism-declaration + prism-expression + prism-formula + prism-global + prism-init + prism-module + prism-modulesfile + prism-modulesfiletype + prism-reward + prism-systemcomposition + prism-update + xrm-parenthesize + xrm-expression + xrm-module + xrm-meta-for + xrm-meta-if + xrm-arrays + +strategies + + pp-xrm-to-abox = + pp-xrm-to-abox(prism-to-box) // we keep prism-to-box as rule name + // because we simply extend it + + pp-xrm-to-abox(pprules) = + // strategy from xrm-parenthesize.str generated by sdf2parenthesize + parenthesize-XRM + ; topdown(try(very-special-conflict) + ; repeat(pprules)) + +rules + + very-special-conflict: + Minus(Minus(e)) -> Minus(Parenthetical(Minus(e))) + + very-special-conflict: + Plus(Plus(e)) -> Plus(Parenthetical(Plus(e))) Index: src/lib/xrm/pp/xrm-to-abox.str --- src/lib/xrm/pp/xrm-to-abox.str (revision 47) +++ src/lib/xrm/pp/xrm-to-abox.str (working copy) @@ -2,28 +2,7 @@ imports libxtclib // FIXME: import libstratego-xtc for strc 0.17 tool-doc - Box - XRM // signature - PRISM // signature of the base language (see README) - prism-command - prism-constant - prism-declaration - prism-expression - prism-formula - prism-global - prism-init - prism-module - prism-modulesfile - prism-modulesfiletype - prism-reward - prism-systemcomposition - prism-update - xrm-parenthesize - xrm-expression - xrm-module - xrm-meta-for - xrm-meta-if - xrm-arrays + pp-xrm-to-box strategies @@ -48,24 +27,6 @@ write-to-text // write text output end -strategies - pp-xrm-to-abox = - pp-xrm-to-abox(prism-to-box) // we keep prism-to-box as rule name - // because we simply extend it - - pp-xrm-to-abox(pprules) = - // strategy from xrm-parenthesize.str generated by sdf2parenthesize - parenthesize-XRM - ; topdown(try(very-special-conflict)) - ; topdown(try(repeat(pprules))) - -rules - very-special-conflict: - Minus(Minus(e)) -> Minus(Parenthetical(Minus(e))) - - very-special-conflict: - Plus(Plus(e)) -> Plus(Parenthetical(Plus(e))) - /** * Documentation */ Index: src/lib/prism/pp/pp-prism-to-box.str --- src/lib/prism/pp/pp-prism-to-box.str (revision 0) +++ src/lib/prism/pp/pp-prism-to-box.str (revision 0) @@ -0,0 +1,37 @@ +module pp-prism-to-box +imports + Box + PRISM // signature + prism-command + prism-constant + prism-declaration + prism-expression + prism-formula + prism-global + prism-init + prism-module + prism-modulesfile + prism-modulesfiletype + prism-reward + prism-systemcomposition + prism-update + prism-parenthesize + +strategies + + pp-prism-to-abox = + pp-prism-to-abox(prism-to-box) + + pp-prism-to-abox(pprules) = + // strategy from prism-parenthesize.str generated by sdf2parenthesize + parenthesize-PRISM + ; topdown(try(very-special-conflict) + ; repeat(pprules)) + +rules + + very-special-conflict: + Minus(Minus(e)) -> Minus(Parenthetical(Minus(e))) + + very-special-conflict: + Plus(Plus(e)) -> Plus(Parenthetical(Plus(e))) Index: src/lib/prism/pp/prism-to-abox.str --- src/lib/prism/pp/prism-to-abox.str (revision 47) +++ src/lib/prism/pp/prism-to-abox.str (working copy) @@ -2,22 +2,7 @@ imports libxtclib // FIXME: import libstratego-xtc for strc 0.17 tool-doc - Box - PRISM // signature - prism-command - prism-constant - prism-declaration - prism-expression - prism-formula - prism-global - prism-init - prism-module - prism-modulesfile - prism-modulesfiletype - prism-reward - prism-systemcomposition - prism-update - prism-parenthesize + pp-prism-to-box strategies @@ -42,23 +27,6 @@ write-to-text // write text output end -strategies - pp-prism-to-abox = - pp-prism-to-abox(prism-to-box) - - pp-prism-to-abox(pprules) = - // strategy from prism-parenthesize.str generated by sdf2parenthesize - parenthesize-PRISM - ; topdown(try(very-special-conflict)) - ; topdown(try(repeat(pprules))) - -rules - very-special-conflict: - Minus(Minus(e)) -> Minus(Parenthetical(Minus(e))) - - very-special-conflict: - Plus(Plus(e)) -> Plus(Parenthetical(Plus(e))) - /** * Documentation */ Index: src/str/xrm-to-prism.str --- src/str/xrm-to-prism.str (revision 47) +++ src/str/xrm-to-prism.str (working copy) @@ -91,6 +91,7 @@ /* paste them at the end of the file */ ; ModulesFile(id, <conc>(<id>, rand-gen-modules)) + ; notice-msg(|"xrm-to-prism: added modules for random numbers") /* remove array accesses: x[i] -> x_i */ // FIXME: can we make this more efficient than a complete bottomup? Index: tests/xrm/array-decl-with-meta-and-non-meta-and-exp.xpm --- tests/xrm/array-decl-with-meta-and-non-meta-and-exp.xpm (revision 0) +++ tests/xrm/array-decl-with-meta-and-non-meta-and-exp.xpm (revision 0) @@ -0,0 +1,5 @@ +for i from 0 to 4 do + for j in 0, 1 do + const int N[i+2+j][3] = 0; + end +end Index: configure.ac --- configure.ac (revision 47) +++ configure.ac (working copy) @@ -5,7 +5,7 @@ ## Mail <sigoure.benoit(a)lrde.epita.fr> ## ## Started on Thu Apr 27 15:55:56 2006 SIGOURE Benoit -## Last update Thu May 25 18:56:02 2006 SIGOURE Benoit +## Last update Fri Jun 2 17:52:40 2006 SIGOURE Benoit ## ## --------------- ## @@ -59,6 +59,8 @@ # define PACKAGE_NAME_TERM, PACKAGE_VERSION_TERM and PACKAGE_BUGREPORT_TERM # theses are #defined so that PACKAGE_* are accessible as ATerms XT_TERM_DEFINE +# use STRATEGO_GPP +XT_CHECK_PACKAGE([STRATEGO_GPP],[stratego-gpp]) ## -------------------- ## ## Output configuration ##

1 0

XRM 47: Fix array declarations.
by SIGOURE Benoit 02 Jun '06

02 Jun '06

https://svn.lrde.epita.fr/svn/xrm/trunk Index: ChangeLog from SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> Fix array declarations. * src/str/array-decl-desugar.str: Take the annotation "Generated" into account.. * src/str/xrm-to-prism.str: Call eval-meta-code before array-decl-desugar. * src/str/prism-desugar.str: Keep annotations when possible. * src/str/eval-meta-code.str: Mark generated code with the annotation "Generated". * src/str/signatures.str: New. * src/str/builtin-rand.str: Move signature to signatures.str. * src/str/collect-static-const-decl.str: Ditto. * src/str/desugar-array-access.str: Improve desugar-range (thanks to mefyl for his range-to-list). * tests/xrm/array-decl-with-meta-and-non-meta.xpm: New. * tests/prism/simple-label.pm: `label' is a reserved keyword in PRISM that's why this test was failing. * TODO: Bring up to date. TODO | 45 +++++------------------- src/str/array-decl-desugar.str | 22 ++++++++++- src/str/builtin-rand.str | 5 -- src/str/collect-static-const-decl.str | 8 ---- src/str/desugar-array-access.str | 27 ++++++++------ src/str/eval-meta-code.str | 15 ++++++-- src/str/prism-desugar.str | 26 ++++++------- src/str/signatures.str | 24 ++++++++++++ src/str/xrm-to-prism.str | 12 ++++-- tests/prism/simple-label.pm | 2 - tests/xrm/array-decl-with-meta-and-non-meta.xpm | 3 + 11 files changed, 108 insertions(+), 81 deletions(-) Index: src/str/array-decl-desugar.str --- src/str/array-decl-desugar.str (revision 46) +++ src/str/array-decl-desugar.str (working copy) @@ -13,10 +13,28 @@ /** ** Desugar dimensions in array declarations in explicit ranges. - ** eg: x[4] is desugared to x[0..3] + ** eg: x[1,2][4] is desugared to x[1,2][0..3] */ desugar-array-access-for-decl = - ArrayAccess(try(desugar-array-access-for-decl), prism-desugar;try(add-range)) + ArrayAccess(try(desugar-array-access-for-decl), try(try-add-range)) + + /** + ** Try to add a range if one of the dimensions is a simple Int + */ + try-add-range = + if ?[single-elem] then // we might need to add a range (x[4] -> x[0..3]) + /* in the current term (including subterms), we're collecting all the + * annotations that match Generated(_) which means that the dimensions + * has been generated by eval-meta-code and must no be transformed into + * a range */ + where(collect-all({a*:?_{a*};<fetch(?Generated(_))> a*}) => genlist) + ; prism-desugar + ; if !genlist => [] then // the dimension wasn't generated: + add-range // we can (try to) expand it in a range + end + else // no need to add a range, simply desugar the array access + prism-desugar + end rules Index: src/str/xrm-to-prism.str --- src/str/xrm-to-prism.str (revision 46) +++ src/str/xrm-to-prism.str (working copy) @@ -62,6 +62,14 @@ ; check-meta-vars ; notice-msg(|"xrm-to-prism: meta-vars checked") + /* unroll meta loops, eval meta if */ + ; eval-meta-code + ; notice-msg(|"xrm-to-prism: eval-meta-code done") + /*; notice-msg(|"debug: pretty printing current AST in ATerms to debug.aterm") + ; where(write-to => FILE(tmp-file) + ; <xtc-command(!"pp-aterm")> ["-i", tmp-file, "-o", "debug.aterm"] + )*/ + /* Desugar array declarations * eg: x[4][5] is transformed into two nested meta for loops * We can't do this in xrm-to-prism-desugar because the innermost @@ -73,10 +81,6 @@ ; topdown(try(array-decl-desugar)) ; notice-msg(|"xrm-to-prism: array declarations desugared") - /* unroll meta loops, eval meta if */ - ; eval-meta-code - ; notice-msg(|"xrm-to-prism: eval-meta-code done") - /* flatten nested lists */ ; ModulesFile(id, flatten-list) ; ModulesFile(id, map(try(Module(id, flatten-list)))) Index: src/str/prism-desugar.str --- src/str/prism-desugar.str (revision 46) +++ src/str/prism-desugar.str (working copy) @@ -52,11 +52,11 @@ rules - IntToDouble: Int(i) -> Double(i) + IntToDouble: Int(i){a*} -> Double(i){a*} /** Transforms a round (or almost round) Double into an Int. */ SimplifyDoubles: - Double(d) -> Int(i) // eg: Double("41.9999999999999") -> Int("42") + Double(d){a*} -> Int(i){a*} // eg: Double("41.9999999999999") -> Int("42") where !d // "41.9999999999999" ; string-to-real // 4.199999999999990e+01 ; real-to-string(|6) // "42.000000" @@ -67,7 +67,7 @@ /** Round real numbers up to 6 digits and remove trailing zeros */ TruncateDouble: - Double(d) -> Double(d') + Double(d){a*} -> Double(d'){a*} where <rtrim-chars(?'0')> (<real-to-string(|6)> (<string-to-real> d)) => d' rules @@ -138,16 +138,16 @@ rules DesugarUnaryOps: - Plus(Int(i)) -> Int(i) + Plus(Int(i){a*}) -> Int(i){a*} DesugarUnaryOps: - Plus(Double(i)) -> Double(i) + Plus(Double(i){a*}) -> Double(i){a*} DesugarUnaryOps: - Minus(Int(i)) -> Int(j) where <mulS>(i, "-1") => j + Minus(Int(i){a*}) -> Int(j){a*} where <mulS>(i, "-1") => j DesugarUnaryOps: - Minus(Double(i)) -> Double(j) where <mulS>(i, "-1") => j + Minus(Double(i){a*}) -> Double(j){a*} where <mulS>(i, "-1") => j /* ** ## ==================== ## @@ -313,15 +313,15 @@ EvalMin: |[ func(min, a*) ]| -> |[ r ]| - where !a*;debug - ; map(\ Double(d) -> d \);debug - ; minRL => r;debug + where !a* + ; map(\ Double(d) -> d \) + ; minRL => r EvalMax: |[ func(max, a*) ]| -> |[ r ]| - where !a*;debug - ; map(\ Double(d) -> d \);debug - ; maxRL => r;debug + where !a* + ; map(\ Double(d) -> d \) + ; maxRL => r EvalFloor: |[ func(floor, d) ]| -> |[ r ]| where <floor>(d) => r Index: src/str/eval-meta-code.str --- src/str/eval-meta-code.str (revision 46) +++ src/str/eval-meta-code.str (working copy) @@ -3,6 +3,13 @@ ** XRM modules can contain meta for loops as well as meta if statements ** which have to evaluated and transformed in PRISM source code. ** +** The code generated is annotated with the Generated("s") annotation where +** s is the name of the strategy which generated the code (can be useful for +** debugging). +** We annotate generated code because the rest of the pipeline might need to +** know what has been generated and what comes from the user to take +** different actions depending on that (eg: in array-decl-desugar.str). +** ** NOTE: This is a tricky part so debugging stuff have been kept and ** commented out instead of being deleted. Hopefully this will make ** debugging easier. This might also make the code easier to understand. @@ -13,7 +20,9 @@ ** mv .tmp eval-meta-code.str */ module eval-meta-code -imports ice +imports + ice + signatures strategies @@ -108,7 +117,7 @@ ///*DEBUG*/; printf(|" i = ", i) ///*DEBUG*/; say(!" <<< gen-meta-for -- propagating meta-var's value <<< ") ; !body - ; topdown(try(?meta-var; !Int(i))) + ; topdown(try(?meta-var; !Int(i){Generated("gen-meta-for")})) ///*DEBUG*/; debug ///*DEBUG*/; say(!" ~~~ gen-meta-for: now recursing") ; eval-meta-code => generated-code @@ -144,7 +153,7 @@ ///*DEBUG*/; printf(|" exp-to-replace = ", exp-to-replace) ///*DEBUG*/; say(!" <<< gen-meta-forin -- propagating meta-var's value <<< ") ; !body - ; topdown(try(?meta-var; !exp-to-replace)) + ; topdown(try(?meta-var; !exp-to-replace{Generated("gen-meta-forin")})) ///*DEBUG*/; debug ///*DEBUG*/; say(!" ~~~ gen-meta-forin: now recursing") ; eval-meta-code => generated-code Index: src/str/signatures.str --- src/str/signatures.str (revision 0) +++ src/str/signatures.str (revision 0) @@ -0,0 +1,24 @@ +module signatures + +/** +** used in collect-static-const-decl.str +** `Type' is used to annotate the static const collected. +** This might be useful in the future. +*/ +signature constructors + Type : String -> Type + +/** +** used in builtin-rand.str +** node to replace in templates +*/ +signature constructors + FIXME : FIXME + +/** +** used in eval-meta-code.str +** annotation to indicate generated code which must not go through further +** expansions. +*/ +signature constructors + Generated : String -> Generated Index: src/str/builtin-rand.str --- src/str/builtin-rand.str (revision 46) +++ src/str/builtin-rand.str (working copy) @@ -12,6 +12,7 @@ ** which the same probability [1/(x-y+1)] */ module builtin-rand +imports signatures rules @@ -85,7 +86,3 @@ " arguments must be statically evaluable"]) ; debug ; <xtc-exit> 4 - -/* node to replace in templates */ -signature constructors - FIXME : FIXME Index: src/str/collect-static-const-decl.str --- src/str/collect-static-const-decl.str (revision 46) +++ src/str/collect-static-const-decl.str (working copy) @@ -4,13 +4,7 @@ ** (see prism-desugar) */ module collect-static-const-decl - -/** -** `Type' is used to annotate the static const collected. -** This might be useful in the future. -*/ -signature constructors - Type : String -> Type +imports signatures strategies Index: src/str/desugar-array-access.str --- src/str/desugar-array-access.str (revision 46) +++ src/str/desugar-array-access.str (working copy) @@ -121,24 +121,27 @@ ; if <ltS>(to, from) then invalid-range-in-array-access end - ; ![to] // start with the highest value - ; rec x( - {h,t: // restrict h and t to this scope - ?[h|t] - ; if not(<eq>(h, from)) then - ![<subtS>(h, "1") | <id>] - ; x - end - } - ) + ; <range-to-list> (<string-to-int> from, <string-to-int> to) + ; map(int-to-string) + +rules + + range-to-list: + (a, a) -> [a] + + range-to-list: + (a, b) -> [a | <range-to-list>(<addi>(a, 1), b)] + where <lt>(a, b) + +strategies non-const-range-in-array-access = - err-msg(|"error: non constant term used in a range in an array access:") + err-msg(|"non constant term used in a range in an array access:") ; debug ; <xtc-exit> 2 invalid-range-in-array-access = - err-msg(|"error: invalid range in an array access [x..y] where x>y:") + err-msg(|"invalid range in an array access [x..y] where x>y:") ; debug ; <xtc-exit> 2 Index: tests/xrm/array-decl-with-meta-and-non-meta.xpm --- tests/xrm/array-decl-with-meta-and-non-meta.xpm (revision 0) +++ tests/xrm/array-decl-with-meta-and-non-meta.xpm (revision 0) @@ -0,0 +1,3 @@ +for i from 0 to 4 do + const int N[i][3] = 0; +end Index: tests/prism/simple-label.pm --- tests/prism/simple-label.pm (revision 46) +++ tests/prism/simple-label.pm (working copy) @@ -2,5 +2,5 @@ module dummy x: [0..1] init 1; - [label] x=2 -> x'=3; + [mylabel] x=2 -> x'=3; endmodule Index: TODO --- TODO (revision 46) +++ TODO (working copy) @@ -17,6 +17,7 @@ * Add more tests. Add tests which actually do check that the generated code is correct (which is not done ATM). + Factorize current tests with shell functions. * How are handled mutually recursive static constant variables in PRISM? eg: const int x = y; @@ -29,8 +30,6 @@ 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 ## ## ---------- ## @@ -44,10 +43,6 @@ o RewardStruct // ditto o SystemComp // b0rken anyway - * Add a sanity check before check-meta-vars to collect all statically - declared variables (globals, formulas, local declarations etc.) and ensure - (in check-meta-vars) that their identifiers are unique. - * 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. @@ -70,7 +65,7 @@ * Add non-static array accesses (as suggested by Micha). For instance: module test x[4] : [0..5]; - i : [0..2]; + i : [0..3]; [] x[0..i]=0 -> ... // i can't be guessed at compile time endmodule @@ -83,7 +78,7 @@ x_3 : [0..5]; i : [0..3]; - [] x_0=0 & ((i<1 | x_1=0) & (i<2 | x_2=0) & (i<3 | x_3=0)) -> ... + [] ((i<0 | x_0=0) & (i<1 | x_1=0) & (i<2 | x_2=0) & (i<3 | x_3=0)) -> ... endmodule /!\ This (might) require that we add another pass to collect the generated @@ -99,39 +94,12 @@ * 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 - * It is currently impossible to declare something partially with meta-vars. - eg: for i from 0 to 3 do - const int N[i][5] = 0; - end - This is because array declarations are desugared down to simple - declarations before the meta-code has been evaluated in the pipeline. - On the other hand, if we evaluate the meta-code before desugaring array - declarations, we will end up with N_i_5 for all `i' and not with - N_i_0 ... N_i_5. Moreover, this will most likely fail because we have - generated something like: const int N[0][5] = 0; - const int N[1][5] = 0; - ... - const int N[2][5] = 0; - but how can we know that we should interpret this as: - const int N[0][0..5] = 0; - const int N[1][0..5] = 0; - ... - that is: the meta-var which has been expanded must no go further - expansions (eg: const int N[0..1][0..5] = 0;) We will also get an error - about declaring an array with a size of 0 element. - - Idea to work around the problem: tag the expanded meta-vars with an - annotation on the AST and handle the special case when desugaring array - declarations. - ## -------------- ## ## Desugarisation ## ## -------------- ## @@ -246,3 +214,10 @@ * Disallow associativity for the "=" and "!=" operators: won't fix (see src/syn/prism/README) + + * Labels seems to be b0rken in parse-prism. + => no it's just that "label" is a reserved keyword. + + * Add a sanity check before check-meta-vars to collect all statically + declared variables (globals, formulas, local declarations etc.) and ensure + (in check-meta-vars) that their identifiers are unique.

1 0

XRM 46: Major changes: new way of handling arrays.
by SIGOURE Benoit 01 Jun '06

01 Jun '06

https://svn.lrde.epita.fr/svn/xrm/trunk Index: ChangeLog from SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> 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). * src/lib/xrm/pp/xrm-expression.str: Add boxing for future operators (not yet implemented) "?=" and "?!=". * src/syn/xrm/XRM-Expression.sdf: Ditto. * src/lib/xrm/pp/xrm-arrays.str: Change boxing of arrays according to the new grammar for arrays. * src/lib/prism/pp/prism-expression.str: Add `KW' boxes for keywords. * src/str/flatten-array-access.str: Adapt to the new arrays. * src/str/check-meta-vars.str: Take the static const and formulas into account to avoid name clashes. * src/str/array-decl-desugar.str: Brand new code from scratch. * src/str/xrm-to-prism.str: Improve the pipeline by reducing the traversals and performing sanity checks earlier on. Move collect-* stuff to... * src/str/collect-static-const-decl.str: ... here. * src/str/collect-static-const-decl.meta: New. * src/str/prism-desugar.str: Fix the expansion of static const values and formulas in constant propagation. * src/str/eval-meta-code.str: Remove unnecessary checks on meta-vars (already performed earlier in the pipeline). * src/str/xrm-front.str: Remove useless FIXME. * src/str/desugar-array-access.str: New. Hot stuff here. * src/syn/xrm/XRM-Arrays.sdf: New grammar for arrays in XRM. * src/syn/prism/PRISM-Expression.sdf: Remove a useless cons. * tests/xrm/exists-eq.xpm: New. * tests/xrm/for-loop-using-const-int.xpm: New. * tests/test-xrm-front.sh.in: Change a message echo'ed. * tests/test-parse-xrm.sh.in: Fix test counting. * tests/test-parse-prism.sh.in: Ditto. * TODO: A new problem arose :(. TODO | 25 ++ src/lib/prism/pp/prism-expression.str | 10 - src/lib/xrm/pp/xrm-arrays.str | 17 - src/lib/xrm/pp/xrm-expression.str | 12 + src/str/array-decl-desugar.str | 298 +++++++++++++++++++-------------- src/str/check-meta-vars.str | 18 + src/str/collect-static-const-decl.meta | 1 src/str/collect-static-const-decl.str | 77 ++++++++ src/str/desugar-array-access.str | 176 +++++++++++++++++++ src/str/eval-meta-code.str | 18 + src/str/flatten-array-access.str | 54 ++--- src/str/prism-desugar.str | 6 src/str/xrm-front.str | 1 src/str/xrm-to-prism.str | 55 ++---- src/syn/prism/PRISM-Expression.sdf | 2 src/syn/xrm/XRM-Arrays.sdf | 26 +- src/syn/xrm/XRM-Expression.sdf | 32 +++ tests/test-parse-prism.sh.in | 3 tests/test-parse-xrm.sh.in | 3 tests/test-xrm-front.sh.in | 2 tests/xrm/exists-eq.xpm | 12 + tests/xrm/for-loop-using-const-int.xpm | 8 22 files changed, 630 insertions(+), 226 deletions(-) Index: src/lib/xrm/pp/xrm-expression.str --- src/lib/xrm/pp/xrm-expression.str (revision 45) +++ src/lib/xrm/pp/xrm-expression.str (working copy) @@ -9,7 +9,15 @@ prism-to-box: LeftShift(lhs, rhs) -> H hs=1 [~lhs MATH["<<"] ~rhs] + prism-to-box: + ExistsEq(array-access, rhs) + -> H hs=1 [~array-access MATH["?="] ~rhs] + + prism-to-box: + ExistsNotEq(array-access, rhs) + -> H hs=1 [~array-access MATH["?!="] ~rhs] + prism-to-box: // NOTE: we use the old builtin-call style - Rand(args) // func(rand, ...) is just uggly. - -> box |[ H hs=0 [ "rand" "(" H hs=1 [ ~args-imploded ] ")" ] ]| + 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 Index: src/lib/xrm/pp/xrm-arrays.str --- src/lib/xrm/pp/xrm-arrays.str (revision 45) +++ src/lib/xrm/pp/xrm-arrays.str (working copy) @@ -2,14 +2,15 @@ rules - // Identifier ArraySubscript+ -> ArrayAccess + // Identifier "[" {Range ","}+ "]" -> ArrayAccess + // ArrayAccess "[" {Range ","}+ "]" -> ArrayAccess prism-to-box: - ArrayAccess(idf, subscripts) -> H hs=0 [ ~idf ~*subscripts-impl ] - where - <mapconcat(\ x -> [S("["), x, S("]")] \)> subscripts => subscripts-impl + ArrayAccess(idf, subscripts) + -> H hs=0 [ ~idf "[" ~subscripts-impl "]" ] + where <implode-list(|",")> subscripts => subscripts-impl - // Identifier ArraySubscript+ "'" -> ArrayAccessPrime + // ArrayAccess "[" {Range ","}+ "]" "'" -> ArrayAccessPrime prism-to-box: - ArrayAccessPrime(idf, subscripts) -> H hs=0 [ ~idf ~*subscripts-impl "'" ] - where - <mapconcat(\ x -> [S("["), x, S("]")] \)> subscripts => subscripts-impl + ArrayAccessPrime(idf, subscripts) + -> H hs=0 [ ~idf "[" ~subscripts-impl "]" "'" ] + where <implode-list(|",")> subscripts => subscripts-impl Index: src/lib/prism/pp/prism-expression.str --- src/lib/prism/pp/prism-expression.str (revision 45) +++ src/lib/prism/pp/prism-expression.str (working copy) @@ -72,31 +72,31 @@ prism-to-box: Min(args) - -> box |[ H hs=0 [ "func" "(" H hs=1 [ H hs=0["min" ","] + -> box |[ H hs=0 [ KW["func"] "(" H hs=1 [ H hs=0[KW["min"] ","] ~args-imploded ] ")" ] ]| where <implode-list(|",")> args => args-imploded prism-to-box: Max(args) - -> box |[ H hs=0 [ "func" "(" H hs=1 [ H hs=0["max" ","] + -> box |[ H hs=0 [ KW["func"] "(" H hs=1 [ H hs=0[KW["max"] ","] ~args-imploded ] ")" ] ]| where <implode-list(|",")> args => args-imploded prism-to-box: Floor(args) - -> box |[ H hs=0 [ "func" "(" H hs=1 [ H hs=0["floor" ","] + -> box |[ H hs=0 [ KW["func"] "(" H hs=1 [ H hs=0[KW["floor"] ","] ~args-imploded ] ")" ] ]| where <implode-list(|",")> args => args-imploded prism-to-box: Ceil(args) - -> box |[ H hs=0 [ "func" "(" H hs=1 [ H hs=0["ceil" ","] + -> box |[ H hs=0 [ KW["func"] "(" H hs=1 [ H hs=0[KW["ceil"] ","] ~args-imploded ] ")" ] ]| where <implode-list(|",")> args => args-imploded prism-to-box: Call(idf, args) - -> box |[ H hs=0 [ "func" "(" H hs=1 [ H hs=0[~idf ","] + -> box |[ H hs=0 [ KW["func"] "(" H hs=1 [ H hs=0[~idf ","] ~args-imploded ] ")" ] ]| where <implode-list(|",")> args => args-imploded Index: src/str/flatten-array-access.str --- src/str/flatten-array-access.str (revision 45) +++ src/str/flatten-array-access.str (working copy) @@ -6,43 +6,40 @@ ** Transform an array access into an identifier (eg: x[i] -> x_i) */ flatten-array-access: - ArrayAccess(Identifier(idf), access-list) -> Identifier(idf') - where flatten-access-list(|idf, access-list) => idf' + ArrayAccess(Identifier(idf), [subscript]) -> Identifier(idf') + where flatten-access-list(|idf, subscript) => idf' flatten-array-access: - ArrayAccessPrime(Identifier(idf), access-list) -> IdentifierPrime(idf') - where flatten-access-list(|idf, access-list) => idf' + ArrayAccessPrime(Identifier(idf), [subscript]) -> IdentifierPrime(idf') + where flatten-access-list(|idf, subscript) => idf' strategies /** ** @internal - ** Transform an access list (in array accesses) into a flat variable name - ** eg: flatten-access-list(|"x", [Int("1"), Int("2")]) -> "x_1_2" - ** NOTE: The access list can contain expressions as long as it possible to - ** evaluate them down to a constant positive Int() value. + ** Transform simple array access into a flat variable name. + ** eg: flatten-array-access(|"x", Int("1")) -> "x_1" + ** NOTE: The subscript can contain expressions as long as it possible to + ** evaluate it down to a constant positive Int() value. ** ** @param idf String - ** @param access-list List of Int() + ** @param subscript Expression */ - flatten-access-list(|idf, access-list) = - /* eval meta expressions in the access-list + flatten-access-list(|idf, subscript) = + /* eval expressions in the subscript * eg: Plus(Int("1"), Int("2")) -> Int("3") */ - <prism-desugar> access-list + <prism-desugar> subscript - /* Now the access must only contain a list of Int: [Int("1"), Int("2"), ..] + /* Now the access must only contain a simple Int(..) * So we can remove the Int() constructor. */ - ; map(\ Int(i) -> i \ <+ invalid-array-access) + ; (\ Int(i) -> i \ <+ invalid-array-access) - /* Now we have a list of strings such as: ["1", "2", ...] - * Check that the list only contains positive integers as strings */ - ; map(try(string-to-int; neg; invalid-array-access)) + /* Now we have an int in a string such as: "1" + * Check that the subscript is not negative */ + ; try(string-to-int; neg; invalid-array-access) - /* Insert underscores between each integer */ - ; separate-by(|"_") - - /* Produce the final identifier: eg: idf_1_2 */ - ; <concat-strings> [idf, "_" | <id>] + /* Produce the final identifier: eg: idf_1 */ + ; <concat-strings> [idf, "_" | [<id>]] /** ** @internal @@ -50,17 +47,16 @@ */ invalid-array-access = if ?Identifier(i) then - ice(|"invalid-array-access", <concat-strings>["internal compiler error: ", - "undeclared meta-variable: ", i, - " (should have been detected earlier!)"]) + err-msg(|<concat-strings>["undeclared meta-variable: ", i]) else if (is-int; neg) then - err-msg(|"error: negative array subscript detected:") + err-msg(|"negative array subscript detected:") ; debug - ; <xtc-exit> 2 else - err-msg(|"error: non constant term in array access:") + err-msg(|"invalid array access:") ; debug - ; <xtc-exit> 2 + ; err-msg(|<concat-strings>["array subscripts must be evaluable ", + "down to constant positive integers."]) end end + ; <xtc-exit> 5 Index: src/str/check-meta-vars.str --- src/str/check-meta-vars.str (revision 45) +++ src/str/check-meta-vars.str (working copy) @@ -53,10 +53,16 @@ check-meta-var-unicity ; ?meta-var ; rules(MetaVars: meta-var) + ; rules(UnscopedMetaVarList: meta-var) check-meta-var-declared = ?Identifier(idf) - ; if not(<MetaVars> Identifier(idf)) then + ; if not(<MetaVars> Identifier(idf) + /* static consts can be seen as a meta-vars here. */ + + <ExpandStaticConsts> Identifier(idf) + /* formulas too, as long as they are statically evaluable. */ + + (<ExpandFormulas> Identifier(idf) + ; check-all-identifers-are-meta-vars)) then err-msg(|<concat-strings>["undeclared meta-var: ", idf]) ; <xtc-exit> 2 end @@ -67,3 +73,13 @@ err-msg(|<concat-strings>["meta-var already defined: ", idf]) ; <xtc-exit> 2 end + ; if <ExpandStaticConsts> Identifier(idf) then + err-msg(|<concat-strings>["cannot redefine `", idf, "': already ", + "defined as a constant value"]) + ; <xtc-exit> 2 + end + ; if <ExpandFormulas> Identifier(idf) then + err-msg(|<concat-strings>["cannot redefine `", idf, "': already ", + "defined as a formula"]) + ; <xtc-exit> 2 + end Index: src/str/array-decl-desugar.str --- src/str/array-decl-desugar.str (revision 45) +++ src/str/array-decl-desugar.str (working copy) @@ -1,141 +1,199 @@ /** -** This sub-module is used to desugar multi-dimension array declarations. -** Each dimension will by handled by a meta for loop unrolled later. -** So if we have a N-dimensions array declaration, it will be rewritten as -** N nested for loops. +** This sub-module is used to desugar array declarations into simple +** declarations. ** -** eg: x[4][3] : [1..2]; -** for meta_i_0 from 0 to 4 do -** for meta_i_1 from 0 to 3 do -** x[meta_i_0][meta_i_1] : [1..2]; -** end -** end -** Since this will unrolled and flattened later in by the submodule evaluating -** meta-code we will end up having all the x_i_j variables declared. -** -** NOTE: Each dimension is handled separately and recursion is not handled by -** array-decl-desugar. The rule must be called in a topdown(try(..)) in order -** to naturally traverse generated code and thus, handle all dimensions. +** eg: x[4][6,7] : [1..2]; +** is desugared to x[0..3][6,7] : [1..2]; +** and then to the declaration of x_0_6, x_0_7, x_1_6, x_1_7, x_2_6, etc. */ module array-decl-desugar +imports desugar-array-access strategies /** - ** 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(_) - ** - ** eg: x[4][3] : bool; - ** => BoolDecNoInit(Identifier("x"), - ** ArrayAccess( [Identifier("meta_i_0"), Int(3)] )) - ** will needs to be transformed as: - ** BoolDecNoInit(Identifier("x"), - ** ArrayAccess( [Identifier("meta_i_0"), - ** Identifier("meta_i_1")] )) - ** @type List(dims) -> List(meta-var, current-dim, List(all-dims-patched)) + ** Desugar dimensions in array declarations in explicit ranges. + ** eg: x[4] is desugared to x[0..3] */ - update-dimensions(|dims) = - <newname> "__meta_i" => x - - /* Ensure that the list of dimensions is desugared */ - ; <prism-desugar> dims => dims' - - /* find the first element in the list which matches ?Int(_) - * eg: [Identifier("..."), Int("1"), Int("2")] will be transformed in - * ([Identifier("...")], Int("1"), [Int("2")]) */ - ; <split-fetch-keep(?Int(_))> dims' - => (dims-done, Int(current-dim), dims-todo) - - /* array[N] has N elements ranging from 0 to N-1 */ - ; <subtS>(current-dim, "1") => current-dim' - - /* replace the dimension we're working on by the meta-var */ - ; <concat> [dims-done, [Identifier(x)], dims-todo] - - /* return the result in a tuple */ - ; !(x, Int(current-dim'), <id>) + desugar-array-access-for-decl = + ArrayAccess(try(desugar-array-access-for-decl), prism-desugar;try(add-range)) rules -// FIXME: Try to figure out why concrete syntax fails to work here - - array-decl-desugar: - IntDecNoInit(ArrayAccess(idf, dims), low, up) - //-> |[ for x from 0 to ~dim step 1 do x[i] : [~low..~up]; end ]| - -> MetaFor(Identifier(x), Int("0"), current-dim', Int("1"), - [ IntDecNoInit(ArrayAccess(idf, dims'), low, up) ]) - where update-dimensions(|dims) => (x, current-dim', dims') - - array-decl-desugar: - IntDec(ArrayAccess(idf, dims), low, up, value) - //-> |[ for x from 0 to ~dim step 1 do - // x[i] : [~low..~up] init ~value; - // end ]| - -> MetaFor(Identifier(x), Int("0"), current-dim', Int("1"), - [ IntDec(ArrayAccess(idf, dims'), low, up, value) ]) - where update-dimensions(|dims) => (x, current-dim', dims') - - - - array-decl-desugar: - BoolDecNoInit(ArrayAccess(idf, dims)) - //-> |[ for x from 0 to ~dim step 1 do x[i] : bool; end ]| - -> MetaFor(Identifier(x), Int("0"), current-dim', Int("1"), - [ BoolDecNoInit(ArrayAccess(idf, dims')) ]) - where update-dimensions(|dims) => (x, current-dim', dims') - - array-decl-desugar: - BoolDec(ArrayAccess(idf, dims), value) - //-> |[ for x from 0 to ~dim step 1 do x[i] : bool init ~value; end ]| - -> MetaFor(Identifier(x), Int("0"), current-dim', Int("1"), - [ BoolDec(ArrayAccess(idf, dims'), value) ]) - where update-dimensions(|dims) => (x, current-dim', dims') - - - - array-decl-desugar: - ConstInt(ArrayAccess(idf, dims), value) - //-> |[ for x from 0 to ~dim step 1 do const int x[i] = ~value; end ]| - -> MetaFor(Identifier(x), Int("0"), current-dim', Int("1"), - [ ConstInt(ArrayAccess(idf, dims'), value) ]) - where update-dimensions(|dims) => (x, current-dim', dims') - - array-decl-desugar: - ConstIntNoInit(ArrayAccess(idf, dims)) - //-> |[ for x from 0 to ~dim step 1 do const int x[i]; end ]| - -> MetaFor(Identifier(x), Int("0"), current-dim', Int("1"), - [ ConstIntNoInit(ArrayAccess(idf, dims')) ]) - where update-dimensions(|dims) => (x, current-dim', dims') + /** @internal Rewrite simple dimensions with ranges (x[4] -> x[0..3]). */ + add-range: + [Int(i)] -> [Range(Int("0"), Int(j))] + where if <eq>(i, "0") then + err-msg(|"array declared with a size of 0 element") + ; debug + ; <xtc-exit> 2 + else + if <ltS>(i, "0") then + err-msg(|"array declared with a negative number of elements") + ; debug + ; <xtc-exit> 2 + end + end + ; <subtS>(i, "1") => j +rules +// FIXME: Try to figure out why concrete syntax fails to work here. +// FIXME: Try to put some code in common in order to shorten the rules. - array-decl-desugar: - ConstDouble(ArrayAccess(idf, dims), value) - //-> |[ for x from 0 to ~dim step 1 do const double x[i] = ~value; end ]| - -> MetaFor(Identifier(x), Int("0"), current-dim', Int("1"), - [ ConstDouble(ArrayAccess(idf, dims'), value) ]) - where update-dimensions(|dims) => (x, current-dim', dims') +/* +** ## ============ ## +** ## Local arrays ## +** ## ============ ## +*/ + // int without init array-decl-desugar: - ConstDoubleNoInit(ArrayAccess(idf, dims)) - //-> |[ for x from 0 to ~dim step 1 do const double x[i]; end ]| - -> MetaFor(Identifier(x), Int("0"), current-dim', Int("1"), - [ ConstDoubleNoInit(ArrayAccess(idf, dims')) ]) - where update-dimensions(|dims) => (x, current-dim', dims') + IntDecNoInit(aa@ArrayAccess(aa_idf, _), low, up) + -> int-decl-no-init-list + where <fetch-idf> aa_idf => idf + ; <desugar-array-access-for-decl> aa + ; desugar-array-access + ; desugared-array-access-list-to-identifier-list(|idf) + ; map({var-name: + ?var-name + ; !IntDecNoInit(Identifier(var-name), low, up) + }) + ; ?int-decl-no-init-list + + // int with init + array-decl-desugar: + IntDec(aa@ArrayAccess(aa_idf, _), low, up, value) + -> int-decl-list + where <fetch-idf> aa_idf => idf + ; <desugar-array-access-for-decl> aa + ; desugar-array-access + ; desugared-array-access-list-to-identifier-list(|idf) + ; map({var-name: + ?var-name + ; !IntDec(Identifier(var-name), low, up, value) + }) + ; ?int-decl-list - array-decl-desugar: - ConstBool(ArrayAccess(idf, dims), value) - //-> |[ for x from 0 to ~dim step 1 do const bool x[i] = ~value; end ]| - -> MetaFor(Identifier(x), Int("0"), current-dim', Int("1"), - [ ConstBool(ArrayAccess(idf, dims'), value) ]) - where update-dimensions(|dims) => (x, current-dim', dims') + // bool without init + array-decl-desugar: + BoolDecNoInit(aa@ArrayAccess(aa_idf, _)) + -> bool-decl-no-init-list + where <fetch-idf> aa_idf => idf + ; <desugar-array-access-for-decl> aa + ; desugar-array-access + ; desugared-array-access-list-to-identifier-list(|idf) + ; map({var-name: + ?var-name + ; !BoolDecNoInit(Identifier(var-name)) + }) + ; ?bool-decl-no-init-list + + // bool with init + array-decl-desugar: + BoolDec(aa@ArrayAccess(aa_idf, _), value) + -> bool-decl-list + where <fetch-idf> aa_idf => idf + ; <desugar-array-access-for-decl> aa + ; desugar-array-access + ; desugared-array-access-list-to-identifier-list(|idf) + ; map({var-name: + ?var-name + ; !BoolDec(Identifier(var-name), value) + }) + ; ?bool-decl-list + +/* +** ## =================== ## +** ## Static const arrays ## +** ## =================== ## +*/ + // const int with init array-decl-desugar: - ConstBoolNoInit(ArrayAccess(idf, dims)) - //-> |[ for x from 0 to ~dim step 1 do const bool x[i]; end ]| - -> MetaFor(Identifier(x), Int("0"), current-dim', Int("1"), - [ ConstBoolNoInit(ArrayAccess(idf, dims')) ]) - where update-dimensions(|dims) => (x, current-dim', dims') + ConstInt(aa@ArrayAccess(aa_idf, _), value) + -> const-int-decl-list + where <fetch-idf> aa_idf => idf + ; <desugar-array-access-for-decl> aa + ; desugar-array-access + ; desugared-array-access-list-to-identifier-list(|idf) + ; map({var-name: + ?var-name + ; !ConstInt(Identifier(var-name), value) + }) + ; ?const-int-decl-list + + // const int without init + array-decl-desugar: + ConstIntNoInit(aa@ArrayAccess(aa_idf, _)) + -> const-int-decl-no-init-list + where <fetch-idf> aa_idf => idf + ; <desugar-array-access-for-decl> aa + ; desugar-array-access + ; desugared-array-access-list-to-identifier-list(|idf) + ; map({var-name: + ?var-name + ; !ConstIntNoInit(Identifier(var-name)) + }) + ; ?const-int-decl-no-init-list + + + + // const double with init + array-decl-desugar: + ConstDouble(aa@ArrayAccess(aa_idf, _), value) + -> const-double-decl-list + where <fetch-idf> aa_idf => idf + ; <desugar-array-access-for-decl> aa + ; desugar-array-access + ; desugared-array-access-list-to-identifier-list(|idf) + ; map({var-name: + ?var-name + ; !ConstDouble(Identifier(var-name), value) + }) + ; ?const-double-decl-list + + // const double without init + array-decl-desugar: + ConstDoubleNoInit(aa@ArrayAccess(aa_idf, _)) + -> const-double-decl-no-init-list + where <fetch-idf> aa_idf => idf + ; <desugar-array-access-for-decl> aa + ; desugar-array-access + ; desugared-array-access-list-to-identifier-list(|idf) + ; map({var-name: + ?var-name + ; !ConstDoubleNoInit(Identifier(var-name)) + }) + ; ?const-double-decl-no-init-list + + + + // const bool with init + array-decl-desugar: + ConstBool(aa@ArrayAccess(aa_idf, _), value) + -> const-bool-decl-list + where <fetch-idf> aa_idf => idf + ; <desugar-array-access-for-decl> aa + ; desugar-array-access + ; desugared-array-access-list-to-identifier-list(|idf) + ; map({var-name: + ?var-name + ; !ConstBool(Identifier(var-name), value) + }) + ; ?const-bool-decl-list + + // const bool without init + array-decl-desugar: + ConstBoolNoInit(aa@ArrayAccess(aa_idf, _)) + -> const-bool-decl-no-init-list + where <fetch-idf> aa_idf => idf + ; <desugar-array-access-for-decl> aa + ; desugar-array-access + ; desugared-array-access-list-to-identifier-list(|idf) + ; map({var-name: + ?var-name + ; !ConstBoolNoInit(Identifier(var-name)) + }) + ; ?const-bool-decl-no-init-list Index: src/str/xrm-to-prism.str --- src/str/xrm-to-prism.str (revision 45) +++ src/str/xrm-to-prism.str (working copy) @@ -20,10 +20,15 @@ ** - 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. +** - MetaVars: (scoped) temporary used by check-meta-vars to store the list +** of meta-vars declared in the current scope. +** - UnscopedMetaVarList: Same as MetaVars but unscoped. Used as a *dirty* +** workaround to allow declarations using meta-vars. */ module xrm-to-prism imports XRM + collect-static-const-decl prism-desugar flatten-array-access check-meta-vars @@ -39,14 +44,24 @@ DesugarRightShift <+ DesugarLeftShift <+ DesugarImplicitForStep <+ DesugarImplicitElse <+ DesugarRand <+ EvalRand + /*FIXME: to be implemented. + <+ DesugarArrayEq <+ DesugarArrayNotEq + <+ DesugarArrayExistsEq <+ DesugarArrayExistsNotEq*/ ) ; notice-msg(|"xrm-to-prism: XRM sugar removed") /* Collect static const variables * Two goals: expand them if needed, look for variable name conflicts. */ - ; topdown(try(collect-static-const-decl); try(collect-formulas)) + ; ModulesFile(id, map(try(collect-static-const-decl); try(collect-formulas))) ; notice-msg(|"xrm-to-prism: static const and formulas collected") + /* Check that meta vars are always defined in the current scope when used + * and that they are not redefined twice in the same scope. This must come + * AFTER collect-static-const-decl/collect-formulas since it needs some of + * the information gathered by them (in DR's). */ + ; check-meta-vars + ; notice-msg(|"xrm-to-prism: meta-vars checked") + /* Desugar array declarations * eg: x[4][5] is transformed into two nested meta for loops * We can't do this in xrm-to-prism-desugar because the innermost @@ -58,11 +73,6 @@ ; topdown(try(array-decl-desugar)) ; notice-msg(|"xrm-to-prism: array declarations desugared") - /* Check that meta vars are always defined in the current scope when used - * and that they are not redefined twice in the same scope */ - ; check-meta-vars - ; notice-msg(|"xrm-to-prism: meta-vars checked") - /* unroll meta loops, eval meta if */ ; eval-meta-code ; notice-msg(|"xrm-to-prism: eval-meta-code done") @@ -105,32 +115,19 @@ //|[ if e then s* end ]| -> |[ if e then s* else end ]| MetaIf(e, m*) -> MetaIf(e, m*, []) -signature constructors - Type : String -> Type - -strategies + /* FIXME: to be implemented. + DesugarArrayEq: + Eq(aa@ArrayAccess(_, _), rhs) -> Eq(rhs, rhs) - collect-static-const-decl = - ?ConstInt(idf, value) - ; where(!value{Type("int")} => v) - ; rules(ExpandStaticConsts: idf -> v) - - collect-static-const-decl = - ?ConstDouble(idf, value) - ; where(!value{Type("double")} => v) - ; rules(ExpandStaticConsts: idf -> v) - - collect-static-const-decl = - ?ConstBool(idf, value) - ; where(!value{Type("bool")} => v) - ; rules(ExpandStaticConsts: idf -> v) + DesugarArrayNotEq: + NotEq(aa@ArrayAccess(_, _), rhs) -> NotEq(rhs, rhs) -rules + DesugarArrayExistsEq: + ExistsEq(aa@ArrayAccess(_, _), rhs) -> Eq(rhs, rhs) - collect-formulas = - //?|[ formula x = e; ]| - ?FormulaDef(x, e) - ; rules(ExpandFormulas: x -> e) + DesugarArrayExistsNotEq: + ExistsNotEq(aa@ArrayAccess(_, _), rhs) -> NotEq(rhs, rhs) + */ strategies Index: src/str/collect-static-const-decl.meta --- src/str/collect-static-const-decl.meta (revision 0) +++ src/str/collect-static-const-decl.meta (revision 0) @@ -0,0 +1 @@ +Meta([Syntax("StrategoXRM")]) Index: src/str/prism-desugar.str --- src/str/prism-desugar.str (revision 45) +++ src/str/prism-desugar.str (working copy) @@ -46,9 +46,9 @@ <+ ConstBool(id, prism-desugar) <+ FormulaDef(id, prism-desugar) <+ ?Int(_); IntToDouble - <+ all(try(ExpandStaticConsts) - ; try(ExpandFormulas) - ; prism-desugar-first-pass) + <+ ExpandStaticConsts + <+ ExpandFormulas + <+ all(prism-desugar-first-pass) rules Index: src/str/eval-meta-code.str --- src/str/eval-meta-code.str (revision 45) +++ src/str/eval-meta-code.str (working copy) @@ -67,8 +67,7 @@ ///*DEBUG*/; printf(|" meta-var = ", meta-var) ///*DEBUG*/; printf(|" from = ", ifrom) ///*DEBUG*/; printf(|" to = ", ito); - where(<check-meta-var-unicity> meta-var) // FIXME: is this still needed? - ; for-loop(gen-meta-for | ifrom, ito, istep, []) + for-loop(gen-meta-for | ifrom, ito, istep, []) ///*DEBUG*/; say(!" ~~~ unroll-meta-for: before bagof-MetaModule") ///*DEBUG*/; debug ; bagof-MetaCode @@ -78,16 +77,20 @@ |} 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 ", + !meta-var => Identifier(idf) + ; if not(!from => Int(_); !to => Int(_); !step => Int(_)) then + err-msg(|<concat-strings>["invalid meta-for loop on the meta-var `", + idf, "': the value of the ", "fields `from', `to' and `step' must be ", "statically evaluable down to a ", "simple integer"]) + ; <debug> from + ; <debug> to + ; <debug> step ; <xtc-exit> 2 end ; if <gtS>(from, to) then - !meta-var => Identifier(idf) - ; err-msg(|<concat-strings>["bad `for' loop on the meta-var ", + err-msg(|<concat-strings>["bad `for' loop on the meta-var ", idf, " starts at ", from, " which is less than ", to]) ; <xtc-exit> 2 @@ -122,8 +125,7 @@ ///*DEBUG*/say(!" @@@ unroll-meta-forin: starting:") ///*DEBUG*/; printf(|" meta-var = ", meta-var) ///*DEBUG*/; printf(|" exp-list = ", exp-list); - where(<check-meta-var-unicity> meta-var) // FIXME: is this still needed? - ; <map(gen-meta-forin(|meta-var, body))> exp-list + <map(gen-meta-forin(|meta-var, body))> exp-list ///*DEBUG*/; say(!" ~~~ unroll-meta-forin: before bagof-MetaModule") ///*DEBUG*/; debug ; bagof-MetaCode Index: src/str/xrm-front.str --- src/str/xrm-front.str (revision 45) +++ src/str/xrm-front.str (working copy) @@ -46,7 +46,6 @@ prism-desugar ; dbg(|"prism-desugar finished") end - ; id // FIXME: add more transformations here /** list of available options for xrm-front */ xrm-front-options = Index: src/str/collect-static-const-decl.str --- src/str/collect-static-const-decl.str (revision 0) +++ src/str/collect-static-const-decl.str (revision 0) @@ -0,0 +1,77 @@ +/** +** This sub-module is used to collect static constants and formulas +** declarations so they can be used in constant propagation. +** (see prism-desugar) +*/ +module collect-static-const-decl + +/** +** `Type' is used to annotate the static const collected. +** This might be useful in the future. +*/ +signature constructors + Type : String -> Type + +strategies + + collect-static-const-decl = + ?ConstInt(idf, value) + ; where(!value{Type("int")} => v) + ; if <ExpandStaticConsts> idf then + cannot-redefine-static-const(|idf) + end + ; if <ExpandFormulas> idf then + cannot-redefine-formula(|idf) + end + ; rules(ExpandStaticConsts: idf -> v) + + collect-static-const-decl = + ?ConstDouble(idf, value) + ; where(!value{Type("double")} => v) + ; if <ExpandStaticConsts> idf then + cannot-redefine-static-const(|idf) + end + ; if <ExpandFormulas> idf then + cannot-redefine-formula(|idf) + end + ; rules(ExpandStaticConsts: idf -> v) + + collect-static-const-decl = + ?ConstBool(idf, value) + ; where(!value{Type("bool")} => v) + ; if <ExpandStaticConsts> idf then + cannot-redefine-static-const(|idf) + end + ; if <ExpandFormulas> idf then + cannot-redefine-formula(|idf) + end + ; rules(ExpandStaticConsts: idf -> v) + +rules + + collect-formulas = + //?|[ formula x = e; ]| + ?FormulaDef(x, e) + ; if <ExpandStaticConsts> x then + cannot-redefine-static-const(|x) + end + ; if <ExpandFormulas> x then + cannot-redefine-formula(|x) + end + ; rules(ExpandFormulas: x -> e) + +strategies + + cannot-redefine-static-const(|idf) = + !idf => Identifier(idf') + ; err-msg(|<concat-strings>["Cannot redefine `", idf', "': already defined", + " as a static const variable."]) + ; <debug> (<ExpandStaticConsts> idf) + ; <xtc-exit> 2 + + cannot-redefine-formula(|idf) = + !idf => Identifier(idf') + ; err-msg(|<concat-strings>["Cannot redefine `", idf', "': already defined", + " as a formula."]) + ; <debug> (<ExpandFormulas> idf) + ; <xtc-exit> 2 Index: src/str/desugar-array-access.str --- src/str/desugar-array-access.str (revision 0) +++ src/str/desugar-array-access.str (revision 0) @@ -0,0 +1,176 @@ +/** +** This sub-module provides several strategies used to handle arrays in XRM +** and desugar them down to simple variables for PRISM. +** +** Support is provided for any kind of array (including multi-demensional ones) +** The main strategies are: +** - desugar-array-access: provided with the root of an ArrayAccess as +** current term, this strategy will return the list of all the possibles +** array accesses generated by the sugared ArrayAccess in the current +** term. +** - desugared-array-access-list-to-identifier-list: applied to the result +** of desugar-array-access, this enables to easily get a list of +** identifiers involved in complex array accesses. +** - fetch-idf: finds which identifier is pertains to the current +** ArrayAccess. This is useful because the identifier one which the +** real ArrayAccess is done can be "hidden" in nested ArrayAccesses. +*/ +module desugar-array-access + +strategies + + /** Yield the list of all possible array accesses generated by a sugared + ** array access. (See the comments of desugar-subscripts and + ** list-all-array-accesses) + */ + desugar-array-access = + desugar-subscripts + ; list-all-array-accesses + +strategies + + /** Collects all subscripts in array accesses and desugar ranges. + ** eg: x[1][2] -> [[1], [2]] + ** x[1..3][2,4] -> [[1,2,3], [2,4]] + ** NOTE: we have a 2D list. The first level of lists represents the + ** dimension, the second level, the subscripts accessed for that + ** dimension. + ** NOTE: If the subscripts contain at least one meta-var, we completely + ** discard this array-access (by failing) and let the eval-meta-code + ** part take care of it. This is a *dirty* hack to allow declarations + ** using meta-vars. This implies that it's impossible to declare + ** something only partially using meta-vars. :| + */ + desugar-subscripts = + collect-all(?ArrayAccess(_, <id>), conc) // collect gives us the list... + ; reverse // ... with deepest array accesses first (we want the opposite) + ; prism-desugar + ; if has-meta-vars then fail end // see the 2nd NOTE above. + ; map( // traverse the list of dimensions + map( // traverse the subscripts for a given dimension + if ?Int(_) then + (\ Int(i) -> i \ // get rid of Int() constructor + ; where(string-to-int; not(neg))) // ensure that i>=0 + <+ invalid-array-access // if anything above failed, report it + else + if ?Range(_, _) then + desugar-range + else // we are neither on an Int nor on a Range => invalid + invalid-array-access + end + end + ) // end inner map + ; flatten-list // because Ranges create nested lists + ) // end outer map + + has-meta-vars = + oncetd(?Identifier(_); UnscopedMetaVarList) + +strategies + + /** Create the Cartesian product of all possible array subscripts. + ** eg: [[1,2,3], [2,4]] -> [[1,2], [1,4], [2,2], [2,4], [3,2], [3,4]] + ** [[1,2],[3,4],[5,6]] -> [[1,3,5], [1,3,6], [1,4,5], [1,4,6], + ** [2,3,5], [2,3,6], [2,4,5], [2,4,6]] + ** Here we use the black magic of the rule below (cartesian-product). + */ + list-all-array-accesses = + /* remember: 1st-level of the list = dimensions => this if matches array + * accesses in 1D arrays, where a Cartesian product is not needed. + */ + if ?[single-list] then + /* since we're not doing a Cartesian product, we must separate each + * element in its own sub list so that x[1,2] yields [["1"], ["2"]] and + * not [["1", "2"]] which means x[1][2] (not obvious, I admit) */ + <map(\ x -> [x] \)> single-list + else + /* Use Cartesian product to generate the list of all the possible + * accesses. */ + foldr(![], ?(<id>,[]) <+ cartesian-product) + end + +rules + + /** Perform a cartesian-product between two lists. + ** FIXME: this is just NOT human readable. + ** + ** OK so here xs is a list of elements (eg: [1,2]) and ys too (eg: [3,4]). + ** First foldr executes the \ x -> ... \ for each element x in xs. This + ** combines each element of x with ys. Dammit, this part is a bit tricky: + ** If the current term is a list (with one or more elements) it will match + ** ?[_|_] so what we do is add x at the beginning of the list. + ** Else we create a new list with two elements, x and the current term. + ** => This way we end with [x,ys] + ** + ** Then all the resulting tuples are of the form ([x1, ys], [x2, ys]) + ** concatenated together by conc, which indeed, is a Cartesian product. + */ + cartesian-product: (xs,ys) + -> <foldr(![] + , conc + , \ x -> <map( (?[_|_];![x|<id>]) <+ ![x|[<id>]])> ys \ + )> xs + +strategies + + /** Desugar a Range(Int(low), Int(high)) in a list [low,...,high]. + ** eg: Range(Int(1), Int(5)) -> [1,2,3,4,5] + */ + desugar-range = + (?Range(Int(from),Int(to)) <+ non-const-range-in-array-access) + ; if <ltS>(to, from) then + invalid-range-in-array-access + end + ; ![to] // start with the highest value + ; rec x( + {h,t: // restrict h and t to this scope + ?[h|t] + ; if not(<eq>(h, from)) then + ![<subtS>(h, "1") | <id>] + ; x + end + } + ) + + non-const-range-in-array-access = + err-msg(|"error: non constant term used in a range in an array access:") + ; debug + ; <xtc-exit> 2 + + invalid-range-in-array-access = + err-msg(|"error: invalid range in an array access [x..y] where x>y:") + ; debug + ; <xtc-exit> 2 + +strategies + + /** Given an identifier and a desugared array access list (as provided by + ** desugar-array-access), produce a single list of identifiers. + ** The desugared array access list must be passed as current term. + ** + ** eg: idf="i" + ** current term=[["1","2"], ["1","3"]] + ** yields => ["i_1_2", "i_1_3"] + ** + ** this is usefull to translate i[1][2,3] in i_1_2 and i_1_3 (using + ** desugar-array-access) + */ + desugared-array-access-list-to-identifier-list(|idf) = + map(![idf|<id>] + ; separate-by(|"_") + ; concat-strings + ) + +rules + + /** Used to find the identifier in an ArrayAccess. + ** x[1] => ArrayAccess(Identifier(x), [1]) + ** x[1][2] => ArrayAccess(ArrayAccess(Identifier(x), [1]), [2]) + ** We dig into the first child of ArrayAccess looking for an Identifier as + ** long as we haven't got it. + ** + ** We return the identifier itself (without the Identifier(_) constructor). + */ + fetch-idf = + (?Identifier(i); !i) + <+ (?ArrayAccess(aa_idf, _); <fetch-idf> aa_idf) Index: src/syn/xrm/XRM-Arrays.sdf --- src/syn/xrm/XRM-Arrays.sdf (revision 45) +++ src/syn/xrm/XRM-Arrays.sdf (working copy) @@ -2,25 +2,25 @@ imports PRISM-to-XRM exports + %% FIXME: we can probably make this look nicer. %% EBNF Grammar: Arrays - %% ArrayAccess ::= Identifier ArraySubscript {ArraySubscript} + %% ArrayAccess ::= + %% Identifier "[" Range {"," Range} "]" + %% | ArrayAccess "[" Range {"," Range} "]" %% - %% ArraySubscript ::= "[" Identifier "]" - %% - %% ArrayAccessPrime ::= Identifier ArraySubscript+ "'" + %% ArrayAccessPrime ::= + %% Identifier "[" Range {"," Range} "]" "'" + %% | ArrayAccess "[" Range {"," Range} "]" "'" - sorts ArrayAccess ArraySubscript + sorts ArrayAccess context-free syntax - Identifier ArraySubscript+ -> ArrayAccess {cons("ArrayAccess")} - "[" Expression "]" -> ArraySubscript {bracket} - - %% Note: why use bracket here? - %% This is a work around. In SDF, if a production contains literals, - %% a constructor is required. With brackets, we specify that literals - %% are allowed there, however this does not create a node in the AST. + Identifier "[" {Range ","}+ "]" -> ArrayAccess {cons("ArrayAccess")} + ArrayAccess "[" {Range ","}+ "]" -> ArrayAccess {cons("ArrayAccess")} sorts ArrayAccessPrime context-free syntax - Identifier ArraySubscript+ "'" + ArrayAccess "[" {Range ","}+ "]" "'" + -> ArrayAccessPrime {cons("ArrayAccessPrime")} + Identifier "[" {Range ","}+ "]" "'" -> ArrayAccessPrime {cons("ArrayAccessPrime")} Index: src/syn/xrm/XRM-Expression.sdf --- src/syn/xrm/XRM-Expression.sdf (revision 45) +++ src/syn/xrm/XRM-Expression.sdf (working copy) @@ -8,6 +8,8 @@ %% ArrayAccess %% | Expression "<<" Expression %% | Expression ">>" Expression + %% | ArrayAccess "?=" Range {"," Range} + %% | ArrayAccess "?!=" Range {"," Range} %% %% ExpressionFunc ::= %% (* older builtin functions for backwards compat. *) @@ -20,19 +22,43 @@ Expression ">>" Expression -> Expression {left,cons("RightShift")} Expression "<<" Expression -> Expression {left,cons("LeftShift")} + %% NOTE: The two following rules should have a `non-assoc' keyword + %% which is omitted on purpose. See the README in ../prism + ArrayAccess "?=" {Range ","}+ -> Expression {cons("ExistsEq")} + ArrayAccess "?!=" {Range ","}+ -> Expression {cons("ExistsNotEq")} + "rand" "(" {Expression ","}+ ")" -> Expression {cons("Rand")} "func" "(" "rand" "," {Expression ","}+ ")" -> Expression {cons("Rand")} + %% 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 + %% grammar (../prism/PRISM-Expression.sdf) and the latter means that + %% these priorities are inserted in the right place in the "priority chain". context-free priorities - { + { %% inherited "+" Expression -> Expression "-" Expression -> Expression } - > {left: + > {left: %% new Expression ">>" Expression -> Expression Expression "<<" Expression -> Expression } - > {left: + > {left: %% inherited Expression "*" Expression -> Expression Expression "/" Expression -> Expression } + > {left: %% inherited + Expression "+" Expression -> Expression + Expression "-" Expression -> Expression + } + > {non-assoc: %% new + ArrayAccess "?=" {Range ","}+ -> Expression + ArrayAccess "?!=" {Range ","}+ -> Expression + } + > {non-assoc: %% inherited + Expression ".." Expression -> Range + } + > { %% inherited + Expression -> Range + } Index: src/syn/prism/PRISM-Expression.sdf --- src/syn/prism/PRISM-Expression.sdf (revision 45) +++ src/syn/prism/PRISM-Expression.sdf (working copy) @@ -210,7 +210,7 @@ %% As we can see, it doesn't make sense to allow a range 1..0 to be a LHS %% or a RHS for a logical operation. > {non-assoc: - Expression ".." Expression -> Range {cons("Range")} + Expression ".." Expression -> Range } > { Expression -> Range Index: tests/xrm/exists-eq.xpm --- tests/xrm/exists-eq.xpm (revision 0) +++ tests/xrm/exists-eq.xpm (revision 0) @@ -0,0 +1,12 @@ +formula N = 4; + +module test + x[N] : [0..42]; + y[4][4] : [0..42] init 0; + + [] x[3]?=0 -> true; + [] y[3][2]?=0 -> true; + [] y[1..3][2]?=0 -> true; + [] y[1..3][1,2]?=0 -> true; + [] y[1,0..3][2]?=0 -> true; +endmodule Index: tests/xrm/for-loop-using-const-int.xpm --- tests/xrm/for-loop-using-const-int.xpm (revision 0) +++ tests/xrm/for-loop-using-const-int.xpm (revision 0) @@ -0,0 +1,8 @@ +const int N=3; + +for i from 0 to N do + module dummy[i] + x[i] : [0..i]; + [] true -> true; + endmodule +end Index: tests/test-xrm-front.sh.in --- tests/test-xrm-front.sh.in (revision 45) +++ tests/test-xrm-front.sh.in (working copy) @@ -28,7 +28,7 @@ echo ">>> Starting the test for $basefile" test_cnt=$((test_cnt + 1)) - echo @ECHO_N@ " Converting $basefile into standard PRISM ... " + echo @ECHO_N@ " Converting $basefile into standard PRISM AST... " "@top_builddir@/src/str/xrm-front" -A \ -i "$file" -o "$outdir/$bfile.pm.aterm" if [ $? -ne 0 ]; then Index: tests/test-parse-xrm.sh.in --- tests/test-parse-xrm.sh.in (revision 45) +++ tests/test-parse-xrm.sh.in (working copy) @@ -17,13 +17,14 @@ echo @ECHO_N@ " Parsing `basename $file` ... " "@top_builddir@/src/tools/parse-xrm" -i "$file" -o /dev/null rv=$? + test_cnt=$((test_cnt + 1)) if [ $? -eq 0 ]; then echo 'OK, no ambiguities found' test_pass=$((test_pass + 1)) else echo " * $file: FAILED (bad return value: $rv)" >> failed_tests.$$ + continue fi - test_cnt=$((test_cnt + 1)) done echo "$0: $test_pass/$test_cnt tests passed" echo "`date` $0: $test_pass/$test_cnt tests passed" >> test_summary Index: tests/test-parse-prism.sh.in --- tests/test-parse-prism.sh.in (revision 45) +++ tests/test-parse-prism.sh.in (working copy) @@ -17,13 +17,14 @@ echo @ECHO_N@ " Parsing `basename $file` ... " "@top_builddir@/src/tools/parse-prism" -i "$file" -o /dev/null rv=$? + test_cnt=$((test_cnt + 1)) if [ $rv -eq 0 ]; then echo 'OK, no ambiguities found' test_pass=$((test_pass + 1)) else echo " * $file: FAILED (bad return value: $rv)" >> failed_tests.$$ + continue fi - test_cnt=$((test_cnt + 1)) done echo "$0: $test_pass/$test_cnt tests passed" echo "`date` $0: $test_pass/$test_cnt tests passed" >> test_summary Index: TODO --- TODO (revision 45) +++ TODO (working copy) @@ -107,6 +107,31 @@ end end + * It is currently impossible to declare something partially with meta-vars. + eg: for i from 0 to 3 do + const int N[i][5] = 0; + end + This is because array declarations are desugared down to simple + declarations before the meta-code has been evaluated in the pipeline. + On the other hand, if we evaluate the meta-code before desugaring array + declarations, we will end up with N_i_5 for all `i' and not with + N_i_0 ... N_i_5. Moreover, this will most likely fail because we have + generated something like: const int N[0][5] = 0; + const int N[1][5] = 0; + ... + const int N[2][5] = 0; + but how can we know that we should interpret this as: + const int N[0][0..5] = 0; + const int N[1][0..5] = 0; + ... + that is: the meta-var which has been expanded must no go further + expansions (eg: const int N[0..1][0..5] = 0;) We will also get an error + about declaring an array with a size of 0 element. + + Idea to work around the problem: tag the expanded meta-vars with an + annotation on the AST and handle the special case when desugaring array + declarations. + ## -------------- ## ## Desugarisation ## ## -------------- ##

1 0

XRM 45: Add messages for the --verbose notice level.
by SIGOURE Benoit 31 May '06

31 May '06

https://svn.lrde.epita.fr/svn/xrm/trunk Index: ChangeLog from SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> Add messages for the --verbose notice level. Because someone has been reporting poor performances when using xrm-front on large files, this will help to track the execution of the pipeline by using --verbose notice. Hopefully we'll quickly see where is the bottleneck (in term of execution time). desugar-array-access has been renamed to flatten-array-access because the name wasn't really appropriate and also because this name will be used for a new strategy in future extensions. * src/str/desugar-array-accesses.str: Rename as... * src/str/flatten-array-access.str: ...this. * src/str/xrm-to-prism.str: Update accordingly. * src/str/xrm-front.str: Add calls to notice-msg. flatten-array-access.str | 6 +++--- xrm-front.str | 8 +++++--- xrm-to-prism.str | 15 ++++++++++++--- 3 files changed, 20 insertions(+), 9 deletions(-) Index: src/str/flatten-array-access.str --- src/str/flatten-array-access.str (revision 44) +++ src/str/flatten-array-access.str (working copy) @@ -1,15 +1,15 @@ -module desugar-array-accesses +module flatten-array-access rules /** ** Transform an array access into an identifier (eg: x[i] -> x_i) */ - remove-array-accesses: + flatten-array-access: ArrayAccess(Identifier(idf), access-list) -> Identifier(idf') where flatten-access-list(|idf, access-list) => idf' - remove-array-accesses: + flatten-array-access: ArrayAccessPrime(Identifier(idf), access-list) -> IdentifierPrime(idf') where flatten-access-list(|idf, access-list) => idf' Index: src/str/xrm-to-prism.str --- src/str/xrm-to-prism.str (revision 44) +++ src/str/xrm-to-prism.str (working copy) @@ -25,7 +25,7 @@ imports XRM prism-desugar - desugar-array-accesses + flatten-array-access check-meta-vars eval-meta-code array-decl-desugar @@ -40,10 +40,12 @@ <+ DesugarImplicitForStep <+ DesugarImplicitElse <+ DesugarRand <+ EvalRand ) + ; notice-msg(|"xrm-to-prism: XRM sugar removed") /* Collect static const variables * Two goals: expand them if needed, look for variable name conflicts. */ ; topdown(try(collect-static-const-decl); try(collect-formulas)) + ; notice-msg(|"xrm-to-prism: static const and formulas collected") /* Desugar array declarations * eg: x[4][5] is transformed into two nested meta for loops @@ -53,18 +55,22 @@ * This must come AFTER collect-static-const-decl since we might need * to expand an arrays which rely on static const variables. */ - ; array-decl-desugar + ; topdown(try(array-decl-desugar)) + ; notice-msg(|"xrm-to-prism: array declarations desugared") /* Check that meta vars are always defined in the current scope when used * and that they are not redefined twice in the same scope */ ; check-meta-vars + ; notice-msg(|"xrm-to-prism: meta-vars checked") /* unroll meta loops, eval meta if */ ; eval-meta-code + ; notice-msg(|"xrm-to-prism: eval-meta-code done") /* flatten nested lists */ ; ModulesFile(id, flatten-list) ; ModulesFile(id, map(try(Module(id, flatten-list)))) + ; notice-msg(|"xrm-to-prism: flatten-list done") /* get the modules that generates random numbers (XRM rand builtin) */ ; where(bagof-RandGenModules; reverse => rand-gen-modules) @@ -73,10 +79,13 @@ ; ModulesFile(id, <conc>(<id>, rand-gen-modules)) /* remove array accesses: x[i] -> x_i */ - ; bottomup(try(remove-array-accesses)) + // FIXME: can we make this more efficient than a complete bottomup? + ; bottomup(try(flatten-array-access)) + ; notice-msg(|"xrm-to-prism: flatten-array-access done") /* re-order modules so that all declarations appear before commands */ ; ModulesFile(id, map(try(reorder-module-contents))) + ; notice-msg(|"xrm-to-prism: reorder-module-contents done") rules Index: src/str/xrm-front.str --- src/str/xrm-front.str (revision 44) +++ src/str/xrm-front.str (working copy) @@ -29,15 +29,17 @@ write-to // output binary ATerms else if must-pp-aterm then // output pp-ATerms - write-to; xtc-transform(!"pp-aterm", pass-verbose) + notice-msg(|"pretty printing ATerms") + ; write-to; xtc-transform(!"pp-aterm", pass-verbose) else // output PRISM source - write-to; xtc-transform(!"pp-prism", pass-verbose) + notice-msg(|"pretty printing PRISM code") + ; write-to; xtc-transform(!"pp-prism", pass-verbose) end end /** pipeline of transformations performed by xrm-front */ xrm-front-pipeline = - dbg(|"xrm-front-pipeline starting") + notice-msg(|"transformation pipeline starting") ; xrm-to-prism ; dbg(|"xrm-to-prism finished") ; if must-desugar then

1 0

Re: XRM 28: Simplify XRM's grammar.
by Akim Demaille 31 May '06

31 May '06

>>> "SIGOURE" == SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> writes: > Simplify XRM's grammar. > The constructors for meta for loops and meta ifs had each two > different names depending whether they were found at top-level or > inside modules. This turned out to be a bad idea because it was > completely unecessary and made transformations harder (because > multiple different cases had to be addressed where a single one could > be enough). > From now on we also stop saying "static" for loops or "static" if > because "meta" seems more appropriate to qualify them and it sounds > better (buzzword inside! :P) Good. > + // -> MetaFor > prism-to-box: > - OuterStaticFor(idf, for-from, for-to, mfs-list) > + MetaFor(idf, for-from, for-to, mfs-list) Pourquoi ne pas reposer sur GPP ?

2 1

XRM 44: Add shell-like meta-for loops.
by SIGOURE Benoit 30 May '06

30 May '06

https://svn.lrde.epita.fr/svn/xrm/trunk Index: ChangeLog from SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> Add shell-like meta-for loops. It is now possible to write meta-for loops a la shell: for i in x, y, z do const int i = 42; end yields => const int x = 42; const int y = 42; const int z = 42; It's a bit ugly but I'm going to need something similar for the next extension. So I thought it would be "nice" to make this "feature" not only some internal hack used to achieve transformations and let the user play with it if he/she feels so. * src/lib/xrm/pp/xrm-meta-for.str: Add boxing for meta-for-in loops. * src/str/check-meta-vars.str: Add checks for meta-for-in loops. * src/str/xrm-to-prism.str: change the way array-decl-desugar is called. * src/str/eval-meta-code.str: Eval (unroll) "meta for in" loops. * src/syn/xrm/XRM-MetaFor.sdf: Add "meta for in" loops. * tests/xrm/for-in.xpm: New. * tests/test-xrm-front.sh.in: Remove useless check. src/lib/xrm/pp/xrm-meta-for.str | 27 ++++++++++++--- src/str/check-meta-vars.str | 9 +++++ src/str/eval-meta-code.str | 70 ++++++++++++++++++++++++++++++---------- src/str/xrm-to-prism.str | 4 +- src/syn/xrm/XRM-MetaFor.sdf | 12 ++++-- tests/test-xrm-front.sh.in | 8 ---- tests/xrm/for-in.xpm | 3 + 7 files changed, 97 insertions(+), 36 deletions(-) Index: src/lib/xrm/pp/xrm-meta-for.str --- src/lib/xrm/pp/xrm-meta-for.str (revision 43) +++ src/lib/xrm/pp/xrm-meta-for.str (working copy) @@ -2,10 +2,10 @@ rules - // "for" Identifier "from" Int "to" Int "do" ModulesFileSection* "end" - // -> MetaFor - // "for" Identifier "from" Int "to" Int "do" DeclarationOrCommand* "end" - // -> MetaFor + // "for" Identifier "from" Expression "to" Expression "do" + // ModulesFileSection* "end" -> MetaFor + // "for" Identifier "from" Expression "to" Expression "do" + // DeclarationOrCommand* "end" -> MetaFor prism-to-box: MetaFor(idf, for-from, for-to, mfs-list) -> box |[ V[ V is=2 [ @@ -16,9 +16,9 @@ ] KW["end"] // in the outermost V box ] ]| - // "for" Identifier "from" Int "to" Int "step" Int "do" + // "for" Identifier "from" Expression "to" Expression "step" Expression "do" // ModulesFileSection* "end" -> MetaFor - // "for" Identifier "from" Int "to" Int "step" Int "do" + // "for" Identifier "from" Expression "to" Expression "step" Expression "do" // DeclarationOrCommand* "end" -> MetaFor prism-to-box: MetaFor(idf, for-from, for-to, for-step, mfs-list) @@ -30,3 +30,18 @@ ~*mfs-list // in the innermost V box ] KW["end"] // in the outermost V box ] ]| + + // "for" Identifier "in" {Expression ","} "do" ModulesFileSection* "end" + // -> MetaForIn + // "for" Identifier "in" {Expression ","} "do" DeclarationOrCommand* "end" + // -> MetaForIn + prism-to-box: + MetaForIn(idf, in-list, mfs-list) + -> box |[ V[ V is=2 [ + H hs=1 [ KW["for"] ~idf + KW["in"] ~*in-list' + KW["do"] ] + ~*mfs-list // in the innermost V box + ] KW["end"] // in the outermost V box + ] ]| + where <separate-by(!S(","))> in-list => in-list' Index: src/str/check-meta-vars.str --- src/str/check-meta-vars.str (revision 43) +++ src/str/check-meta-vars.str (working copy) @@ -13,6 +13,7 @@ check-meta-vars = check-meta-for + <+ check-meta-forin <+ check-meta-if <+ ArrayAccess(id, check-all-identifers-are-meta-vars) <+ ArrayAccessPrime(id, check-all-identifers-are-meta-vars) @@ -28,6 +29,14 @@ ; <check-meta-vars> body |}) + check-meta-forin = + ?MetaForIn(new-meta-var, exp-list, body) + ; where({| MetaVars: + <add-meta-var> new-meta-var + ; <check-meta-vars> exp-list + ; <check-meta-vars> body + |}) + check-meta-if = ?MetaIf(condition, then-part, else-part) ; where( Index: src/str/xrm-to-prism.str --- src/str/xrm-to-prism.str (revision 43) +++ src/str/xrm-to-prism.str (working copy) @@ -51,9 +51,9 @@ * traversal is bottomup and won't recurse into generated code. * * This must come AFTER collect-static-const-decl since we might need - * to expand an array which relies on static const variables. + * to expand an arrays which rely on static const variables. */ - ; topdown(try(array-decl-desugar)) + ; array-decl-desugar /* Check that meta vars are always defined in the current scope when used * and that they are not redefined twice in the same scope */ Index: src/str/eval-meta-code.str --- src/str/eval-meta-code.str (revision 43) +++ src/str/eval-meta-code.str (working copy) @@ -19,7 +19,8 @@ eval-meta-code = eval-meta-if - <+ unroll-meta-loops + <+ unroll-meta-for + <+ unroll-meta-forin <+ all(eval-meta-code) strategies @@ -47,7 +48,7 @@ strategies - unroll-meta-loops = + unroll-meta-for = ?MetaFor(meta-var, from, to, step, body) /* reduce the fields from to and step down to simple integers */ ; where( <prism-desugar> from => from' @@ -62,17 +63,17 @@ ; !step' => Int(istep) ) ; {| MetaCode: - ///*DEBUG*/say(!" @@@ unroll-meta-loops: starting:") + ///*DEBUG*/say(!" @@@ unroll-meta-for: starting:") ///*DEBUG*/; printf(|" meta-var = ", meta-var) ///*DEBUG*/; printf(|" from = ", ifrom) ///*DEBUG*/; printf(|" to = ", ito); - where(<check-meta-var-unicity> meta-var) - ; for-loop(gen-meta-code | ifrom, ito, istep, []) - ///*DEBUG*/; say(!" ~~~ unroll-meta-loops: before bagof-MetaModule") + where(<check-meta-var-unicity> meta-var) // FIXME: is this still needed? + ; for-loop(gen-meta-for | ifrom, ito, istep, []) + ///*DEBUG*/; say(!" ~~~ unroll-meta-for: before bagof-MetaModule") ///*DEBUG*/; debug ; bagof-MetaCode ; reverse - ///*DEBUG*/; say(!" ~~~ unroll-meta-loops: after bagof-MetaModule") + ///*DEBUG*/; say(!" ~~~ unroll-meta-for: after bagof-MetaModule") ///*DEBUG*/; debug |} @@ -94,24 +95,61 @@ strategies - gen-meta-code(|i, data) = - ///*DEBUG*/say(!" ### gen-meta-code starting"); debug; - (?MetaFor(meta-var, _, _, _, body) <+ fatal-err-msg(|"ICE!")) - ///*DEBUG*/; say(!" >>> gen-meta-code -- start -- current term >>>") + gen-meta-for(|i, data) = + ///*DEBUG*/say(!" ### gen-meta-for starting"); debug; + ?MetaFor(meta-var, _, _, _, body) + ///*DEBUG*/; say(!" >>> gen-meta-for -- start -- current term >>>") ///*DEBUG*/; debug - ///*DEBUG*/; say(!" >>> gen-meta-code -- start -- iterator >>>") + ///*DEBUG*/; say(!" >>> gen-meta-for -- start -- iterator >>>") ///*DEBUG*/; printf(|" meta-var = ", meta-var) ///*DEBUG*/; printf(|" i = ", i) - ///*DEBUG*/; say(!" <<< gen-meta-code -- propagating meta-var's value <<< ") + ///*DEBUG*/; say(!" <<< gen-meta-for -- propagating meta-var's value <<< ") ; !body ; topdown(try(?meta-var; !Int(i))) ///*DEBUG*/; debug - ///*DEBUG*/; say(!" ~~~ gen-meta-code: now recursing") + ///*DEBUG*/; say(!" ~~~ gen-meta-for: now recursing") ; eval-meta-code => generated-code ; rules(MetaCode:+ _ -> generated-code) - ///*DEBUG*/; say(!" ~~~ gen-meta-code: recursion finished, final result:") + ///*DEBUG*/; say(!" ~~~ gen-meta-for: recursion finished, final result:") ///*DEBUG*/; debug - ///*DEBUG*/; say(!" <<<<<<<<<<<<<<<<< gen-meta-code <<<<<<<<<<<<<<<<< ") + ///*DEBUG*/; say(!" <<<<<<<<<<<<<<<<< gen-meta-for <<<<<<<<<<<<<<<<< ") + +strategies + + unroll-meta-forin = + ?MetaForIn(meta-var, exp-list, body) + ; {| MetaCode: + ///*DEBUG*/say(!" @@@ unroll-meta-forin: starting:") + ///*DEBUG*/; printf(|" meta-var = ", meta-var) + ///*DEBUG*/; printf(|" exp-list = ", exp-list); + where(<check-meta-var-unicity> meta-var) // FIXME: is this still needed? + ; <map(gen-meta-forin(|meta-var, body))> exp-list + ///*DEBUG*/; say(!" ~~~ unroll-meta-forin: before bagof-MetaModule") + ///*DEBUG*/; debug + ; bagof-MetaCode + ; reverse + ///*DEBUG*/; say(!" ~~~ unroll-meta-forin: after bagof-MetaModule") + ///*DEBUG*/; debug + |} + + gen-meta-forin(|meta-var, body) = + ///*DEBUG*/say(!" ### gen-meta-forin starting"); debug; + ?exp-to-replace + ///*DEBUG*/; say(!" >>> gen-meta-forin -- start -- current term >>>") + ///*DEBUG*/; debug + ///*DEBUG*/; say(!" >>> gen-meta-forin -- start -- iterator >>>") + ///*DEBUG*/; printf(|" meta-var = ", meta-var) + ///*DEBUG*/; printf(|" exp-to-replace = ", exp-to-replace) + ///*DEBUG*/; say(!" <<< gen-meta-forin -- propagating meta-var's value <<< ") + ; !body + ; topdown(try(?meta-var; !exp-to-replace)) + ///*DEBUG*/; debug + ///*DEBUG*/; say(!" ~~~ gen-meta-forin: now recursing") + ; eval-meta-code => generated-code + ; rules(MetaCode:+ _ -> generated-code) + ///*DEBUG*/; say(!" ~~~ gen-meta-forin: recursion finished, final result:") + ///*DEBUG*/; debug + ///*DEBUG*/; say(!" <<<<<<<<<<<<<<<<< gen-meta-forin <<<<<<<<<<<<<<<<< ") strategies ///*DEBUG*/printf(|str, term) = where(<fprintnl> (stderr, [str, term])) Index: src/syn/xrm/XRM-MetaFor.sdf --- src/syn/xrm/XRM-MetaFor.sdf (revision 43) +++ src/syn/xrm/XRM-MetaFor.sdf (working copy) @@ -21,17 +21,21 @@ %% This MetaFor can be found only at top-level %% So we can see it as a ModulesFileSection "for" Identifier "from" Expression "to" Expression "do" - ModulesFileSection* "end" - -> ModulesFileSection {cons("MetaFor")} + ModulesFileSection* "end" -> ModulesFileSection {cons("MetaFor")} "for" Identifier "from" Expression "to" Expression "step" Expression "do" ModulesFileSection* "end" -> ModulesFileSection {cons("MetaFor")} + "for" Identifier "in" {Expression ","}+ "do" + ModulesFileSection* "end" -> ModulesFileSection {cons("MetaForIn")} + %% This MetaFor can be found only inside Modules %% So we can see it as a DeclarationOrCommand "for" Identifier "from" Expression "to" Expression "do" - DeclarationOrCommand* "end" - -> DeclarationOrCommand {cons("MetaFor")} + DeclarationOrCommand* "end" -> DeclarationOrCommand {cons("MetaFor")} "for" Identifier "from" Expression "to" Expression "step" Expression "do" DeclarationOrCommand* "end" -> DeclarationOrCommand {cons("MetaFor")} + + "for" Identifier "in" {Expression ","}+ "do" + ModulesFileSection* "end" -> DeclarationOrCommand {cons("MetaForIn")} Index: tests/xrm/for-in.xpm --- tests/xrm/for-in.xpm (revision 0) +++ tests/xrm/for-in.xpm (revision 0) @@ -0,0 +1,3 @@ +for i in x,y,z do + const int i = 0; +end Index: tests/test-xrm-front.sh.in --- tests/test-xrm-front.sh.in (revision 43) +++ tests/test-xrm-front.sh.in (working copy) @@ -58,14 +58,6 @@ fi echo 'OK, no ambiguities found' - diff -q "$outdir/$bfile.pm.aterm" "$outdir/$bfile.pm2.aterm" - - if [ $? -ne 0 ]; then - echo 'FAILED: the two parses did NOT produce the same AST:' - echo " * $file: both parses did NOT produce the same AST" >> failed_tests.$$ - diff -u "$outdir/$bfile.pm.aterm.pp" "$outdir/$bfile.pm2.aterm.pp" - fi - echo "<<< Test for $basefile PASSED" test_pass=$((test_pass + 1)) done

1 0

XRM 43: Fix the XRM rand builtin for negative numbers.
by SIGOURE Benoit 30 May '06

30 May '06

https://svn.lrde.epita.fr/svn/xrm/trunk Index: ChangeLog from SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> 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)

1 0

Re: XRM 27: Add meta code evaluation [debug version].
by Akim Demaille 29 May '06

29 May '06

>>> "SIGOURE" == SIGOURE Benoit <sigoure.benoit(a)lrde.epita.fr> writes: > + add-meta-var = > + check-meta-var-unicity > + ; ?meta-var > + ; rules(MetaVars: meta-var) J'ai peut-être mal compris, mais je ne vois pas où tu vides les MetaVars qui sortent de la portée courante. Par ailleurs, est-ce vraiment ce que l'on veut ? Je ne vois pas de raison d'interdire des boucles for i dans des boucles for i.

2 3

Re: [Projects] Re: XRM 32: Fix the Makefiles.
by michael.cadilhac＠lrde.org 29 May '06

29 May '06

Akim Demaille <akim(a)lrde.epita.fr> writes: >>>> "Nicolas" == Nicolas Pouillard <nicolas.pouillard(a)gmail.com> writes: > > > On 5/29/06, Akim Demaille <akim(a)lrde.epita.fr> wrote: > >> >>> "Michaël" == Michaël Cadilhac <michael.cadilhac(a)lrde.org> writes: > >> > Please don't use such headers. SVN $Id$ is here for you. > >> > >> Et franchement, même ce dernier on n'en veut plus vraiment. > > > A bon ?? > > > Quelles en sont les raisons ? > > C'est quoi l'intérêt ? Aujourd'hui on a presque toujours une > connexion à l'Internet, ou à défaut des outils qui marchent plutôt > bien en off-line. Sans compter que maintenant on a un Id qui est > plutôt globale au projet que locale au fichier. Du coup, un svn info > ou genre fait très bien le métier. > > Je n'ai jamais vu un cas où ça avait servi d'avoir cet Id. Les fichiers de conf sur gentoo ont tous leur $Id$. Ça me permet, quand je reporte un bug dans un fichier de conf, de dire que c'est celui du 28 août 2005, modifié par Dave Wart. Tout le monde regarde alors le même fichier, mais je n'ai pas du tout la moindre idée d'où se trouve le repository SVN associé. Je ne vois pas en quoi c'est différent pour l'utilisateur, mettons, de Vaucanson, qui aura téléchargé un snapshot, ./configure && make && make install, supprime la tarball et le répertoire, et utilise la bibliothèque jusqu'à (hopefully) plantage. -- | Pour les 35-40 ans, l'humour Michaël `Micha' Cadilhac | | c'est une plus-value. cadilh_m - Epita 2007 - CSI | | -- Guillaume L. JID: micha(a)amessage.be | `-- - - - - --'

2 2