diff options
| -rw-r--r-- | compiler/patterns.nim | 2 | ||||
| -rwxr-xr-x | compiler/semtempl.nim | 2 | ||||
| -rwxr-xr-x | contributors.txt | 1 | ||||
| -rwxr-xr-x | doc/docs.txt | 4 | ||||
| -rwxr-xr-x | doc/manual.txt | 4 | ||||
| -rw-r--r-- | doc/trmacros.txt | 288 | ||||
| -rwxr-xr-x | doc/tut2.txt | 12 | ||||
| -rw-r--r-- | tests/patterns/tmatrix.nim | 7 | ||||
| -rw-r--r-- | tests/patterns/tor.nim | 11 | ||||
| -rw-r--r-- | tests/patterns/tstar.nim | 2 | ||||
| -rwxr-xr-x | todo.txt | 2 | ||||
| -rwxr-xr-x | web/index.txt | 11 | ||||
| -rwxr-xr-x | web/news.txt | 2 | ||||
| -rwxr-xr-x | web/nimrod.ini | 2 |
14 files changed, 332 insertions, 18 deletions
diff --git a/compiler/patterns.nim b/compiler/patterns.nim index d8c7e26d9..af259c916 100644 --- a/compiler/patterns.nim +++ b/compiler/patterns.nim @@ -146,7 +146,7 @@ proc matches(c: PPatternContext, p, n: PNode): bool = case opr of "|": result = matchChoice(c, p, n) of "*": result = matchNested(c, p, n, rpn=false) - of "*|": result = matchNested(c, p, n, rpn=true) + of "**": result = matchNested(c, p, n, rpn=true) of "~": result = not matches(c, p.sons[1], n) else: InternalError(p.info, "invalid pattern") # template {add(a, `&` * b)}(a: string{noalias}, b: varargs[string]) = diff --git a/compiler/semtempl.nim b/compiler/semtempl.nim index ef935e346..8e36aac20 100755 --- a/compiler/semtempl.nim +++ b/compiler/semtempl.nim @@ -491,7 +491,7 @@ proc semPatternBody(c: var TemplCtx, n: PNode): PNode = # we interpret `*` and `|` only as pattern operators if they occur in # infix notation, so that '`*`(a, b)' can be used for verbatim matching: let opr = n.sons[0] - if opr.ident.s == "*" or opr.ident.s == "*|": + if opr.ident.s == "*" or opr.ident.s == "**": result = newNodeI(nkPattern, n.info, n.len) result.sons[0] = opr result.sons[1] = semPatternBody(c, n.sons[1]) diff --git a/contributors.txt b/contributors.txt index 23fcd14e0..e9909c677 100755 --- a/contributors.txt +++ b/contributors.txt @@ -2,6 +2,7 @@ Comex Eric Doughty-Papassideris Simon Hafner Keita Haga +Grzegorz Adam Hankiewicz Philippe Lhoste Zahary Karadjov Mario Ray Mahardhika diff --git a/doc/docs.txt b/doc/docs.txt index 42294ea1c..14bdd64b2 100755 --- a/doc/docs.txt +++ b/doc/docs.txt @@ -30,6 +30,10 @@ The documentation consists of several documents: | The Nimrod compiler supports source code filters as a simple yet powerful builtin templating system. +- | `Term rewriting macros <trmacros.html>`_ + | Term rewriting macros enhance the compilation process with user defined + optimizations. + - | `Internal documentation <intern.html>`_ | The internal documentation describes how the compiler is implemented. Read this if you want to hack the compiler. diff --git a/doc/manual.txt b/doc/manual.txt index c8d40c476..042163de9 100755 --- a/doc/manual.txt +++ b/doc/manual.txt @@ -3662,7 +3662,9 @@ warnings on|off Turns the warning messages of the compiler hints on|off Turns the hint messages of the compiler on or off. optimization none|speed|size Optimize the code for speed or size, or - disable optimization. + disable optimization. +patterns on|off Turns the term rewriting templates/macros + on or off. callconv cdecl|... Specifies the default calling convention for all procedures (and procedure types) that follow. diff --git a/doc/trmacros.txt b/doc/trmacros.txt new file mode 100644 index 000000000..bb6591827 --- /dev/null +++ b/doc/trmacros.txt @@ -0,0 +1,288 @@ +========================================================= + Term rewriting macros for Nimrod +========================================================= + +:Author: Andreas Rumpf + +Term rewriting macros are macros or templates that have not only a *name* but +also a *pattern* that is searched for after the semantic checking phase of +the compiler: This means they provide an easy way to enhance the compilation +pipeline with user defined optimizations: + +.. code-block:: nimrod + template optMul{`*`(a, 2)}(a: int): int = a+a + + let x = 3 + echo x * 2 + +The compiler now rewrites ``x * 2`` as ``x + x``. The code inside the +curlies is the pattern to match against. The operators ``*``, ``**``, + ``|``, ``~`` have a special meaning in patterns if they are written in infix +notation, so to match verbatim against ``*`` the ordinary function call syntax +needs to be used. + + +Unfortunately optimizations are hard to get right and even the tiny example +is **wrong**: + +.. code-block:: nimrod + template optMul{`*`(a, 2)}(a: int): int = a+a + + proc f(): int = + echo "side effect!" + result = 55 + + echo f() * 2 + +We cannot duplicate 'a' if it denotes an expression that has a side effect! +Fortunately Nimrod supports side effect analysis: + +.. code-block:: nimrod + template optMul{`*`(a, 2)}(a: int{noSideEffect}): int = a+a + + proc f(): int = + echo "side effect!" + result = 55 + + echo f() * 2 # and still optimized ;-) + +The reason is that the compiler does not consider 'echo' to have side effects +for debugging convenience (this is comparable to Haskell's ``UnsafeIO`` monad). +So lets try it with a "real" side effect: + +.. code-block:: nimrod + template optMul{`*`(a, 2)}(a: int{noSideEffect}): int = a+a + + proc f(): int = + writeln stdout, "side effect!" + result = 55 + + echo f() * 2 # not optimized ;-) + +So what about ``2 * a``? We should tell the compiler ``*`` is commutative. We +cannot really do that however as the following code only swaps arguments +blindly: + +.. code-block:: nimrod + template mulIsCommutative{`*`(a, b)}(a, b: int): int = b*a + +What optimizers really need to do is a *canonicalization*: + +.. code-block:: nimrod + template canonMul{`*`(a, b)}(a: int{lit}, b: int): int = b*a + +The ``int{lit}`` parameter pattern matches against an expression of +type ``int``, but only if it's a literal. + + + +Parameter constraints +===================== + +The parameter constraint expression can use the operators ``|`` (or), +``&`` (and) and ``~`` (not) and the following predicates: + +=================== ===================================================== +Predicate Meaning +=================== ===================================================== +``atom`` The matching node has no children. +``lit`` The matching node is a literal like "abc", 12. +``sym`` The matching node must be a symbol (a bound + identifier). +``ident`` The matching node must be an identifier (an unbound + identifier). +``call`` The matching AST must be a call/apply expression. +``lvalue`` The matching AST must be an lvalue. +``sideeffect`` The matching AST must have a side effect. +``nosideeffect`` The matching AST must have no side effect. +``param`` A symbol which is a parameter. +``genericparam`` A symbol which is a generic parameter. +``module`` A symbol which is a module. +``type`` A symbol which is a type. +``var`` A symbol which is a variable. +``let`` A symbol which is a ``let`` variable. +``const`` A symbol which is a constant. +``result`` The special ``result`` variable. +``proc`` A symbol which is a proc. +``method`` A symbol which is a method. +``iterator`` A symbol which is an iterator. +``converter`` A symbol which is a converter. +``macro`` A symbol which is a macro. +``template`` A symbol which is a template. +``field`` A symbol which is a field in a tuple or an object. +``enumfield`` A symbol which is a field in an enumeration. +``forvar`` A for loop variable. +``label`` A label (used in ``block`` statements). +``nk*`` The matching AST must have the specified kind. + (Example: ``nkIfStmt`` denotes an ``if`` statement.) +``alias`` States that the marked parameter needs to alias + with *some* other parameter. +``noalias`` States that *every* other parameter must not alias + with the marked parameter. +=================== ===================================================== + +The ``alias`` and ``noalias`` predicates refer not only to the matching AST, +but also to every other bound parameter; syntactially they need to occur after +the ordinary AST predicates: + +.. code-block:: nimrod + template ex{a = b + c}(a: int{noalias}, b, c: int) = + # this transformation is only valid if 'b' and 'c' do not alias 'a': + a = b + inc a, b + + +Pattern operators +================= + +The operators ``*``, ``**``, ``|``, ``~`` have a special meaning in patterns +if they are written in infix notation. + + +The ``|`` operator +------------------ + +The ``|`` operator if used as infix operator creates an ordered choice: + +.. code-block:: nimrod + template t{0|1}(): expr = 3 + let a = 1 + # outputs 3: + echo a + +The matching is performed after the compiler performed some optimizations like +constant folding, so the following does not work: + +.. code-block:: nimrod + template t{0|1}(): expr = 3 + # outputs 1: + echo 1 + +The reason is that the compiler already transformed the 1 into "1" for +the ``echo`` statement. However, a term rewriting macro should not change the +semantics anyway. In fact they can be deactived with the ``--patterns:off`` +command line option or temporarily with the ``patterns`` pragma. + + +The ``{}`` operator +------------------- + +A pattern expression can be bound to a pattern parameter via the ``expr{param}`` +notation: + +.. code-block:: nimrod + template t{(0|1|2){x}}(x: expr): expr = x+1 + let a = 1 + # outputs 2: + echo a + + +The ``~`` operator +------------------ + +The ``~`` operator is the **not** operator in patterns: + +.. code-block:: nimrod + template t{x = (~x){y} and (~x){z}}(x, y, z: bool): stmt = + x = y + if x: x = z + + var + a = false + b = true + c = false + a = b and c + echo a + + +The ``*`` operator +------------------ + +The ``*`` operator can *flatten* a nested binary expression like ``a & b & c`` +to ``&(a, b, c)``: + +.. code-block:: nimrod + var + calls = 0 + + proc `&&`(s: varargs[string]): string = + result = s[0] + for i in 1..len(s)-1: result.add s[i] + inc calls + + template optConc{ `&&` * a }(a: string): expr = &&a + + let space = " " + echo "my" && (space & "awe" && "some " ) && "concat" + + # check that it's been optimized properly: + doAssert calls == 1 + + +The second operator of `*` must be a parameter; it is used to gather all the +arguments. The expression ``"my" && (space & "awe" && "some " ) && "concat"`` +is passed to ``optConc`` in ``a`` as a special list (of kind ``nkArgList``) +which is flattened into a call expression; thus the invocation of ``optConc`` +produces: + +.. code-block:: nimrod + `&&`("my", space & "awe", "some ", "concat") + + +The ``**`` operator +------------------- + +The ``**`` is much like the ``*`` operator, except that it gathers not only +all the arguments, but also the matched operators in reverse polish notation: + +.. code-block:: nimrod + import macros + + type + TMatrix = object + dummy: int + + proc `*`(a, b: TMatrix): TMatrix = nil + proc `+`(a, b: TMat): TMatrix = nil + proc `-`(a, b: TMatrix): TMatrix = nil + proc `$`(a: TMatrix): string = result = $a.dummy + proc mat21(): TMatrix = + result.dummy = 21 + + macro optM{ (`+`|`-`|`*`) ** a }(a: TMatrix): expr = + echo treeRepr(a) + result = newCall(bindSym"mat21") + + var x, y, z: TMatrix + + echo x + y * z - x + +This transforms passes expression ``x + y * z - x`` to the ``optM`` macro as +an ``nnkArgList`` node containing:: + + Arglist + Sym "x" + Sym "y" + Sym "z" + Sym "*" + Sym "+" + Sym "x" + Sym "-" + +(Which is the reverse polish notation of ``x + y * z - x``.) + + +Parameters +========== + +Parameters in a pattern are type checked in the matching process. If a +parameter is of the type ``varargs`` it is treated specially and it can match +0 or more arguments in the AST to be matched against: + +.. code-block:: nimrod + template optWrite{ + write(f, x) + ((write|writeln){w})(f, y) + }(x, y: varargs[expr], f: TFile, w: expr) = + w(f, x, y) + diff --git a/doc/tut2.txt b/doc/tut2.txt index 85a68c983..3882296be 100755 --- a/doc/tut2.txt +++ b/doc/tut2.txt @@ -286,7 +286,7 @@ Procedures always use static dispatch. For dynamic dispatch replace the .. code-block:: nimrod type - TExpr = object ## abstract base class for an expression + TExpr = object of TObject ## abstract base class for an expression TLiteral = object of TExpr x: int TPlusExpr = object of TExpr @@ -323,7 +323,7 @@ dispatching: .. code-block:: nimrod type - TThing = object + TThing = object of TObject TUnit = object of TThing x: int @@ -702,3 +702,11 @@ regular expressions: return tkOperator else: return tkUnknown + + +Term rewriting macros +--------------------- + +Term rewriting macros can be used to enhance the compilation process +with user defined optimizations; see this `document <trmacros.html>`_ for +further information. diff --git a/tests/patterns/tmatrix.nim b/tests/patterns/tmatrix.nim index 1d411ad25..c825a7792 100644 --- a/tests/patterns/tmatrix.nim +++ b/tests/patterns/tmatrix.nim @@ -12,11 +12,12 @@ proc `*`(a, b: TMat): TMat = nil proc `+`(a, b: TMat): TMat = nil proc `-`(a, b: TMat): TMat = nil proc `$`(a: TMat): string = result = $a.dummy -proc mat32(): TMat = +proc mat21(): TMat = result.dummy = 21 -macro optOps{ (`+`|`-`|`*`) *| a }(a: TMat): expr = - result = newCall(bindSym"mat32") +macro optOps{ (`+`|`-`|`*`) ** a }(a: TMat): expr = + echo treeRepr(a) + result = newCall(bindSym"mat21") #macro optPlus{ `+` * a }(a: varargs[TMat]): expr = # result = newIntLitNode(21) diff --git a/tests/patterns/tor.nim b/tests/patterns/tor.nim index 304e1c692..92ef96925 100644 --- a/tests/patterns/tor.nim +++ b/tests/patterns/tor.nim @@ -7,3 +7,14 @@ template testOr{ (arithOps{f})(a, b) }(a, b, f: expr): expr = f(a+1, b) let xx = 10 echo 10*xx + +template t{x = (~x){y} and (~x){z}}(x, y, z: bool): stmt = + x = y + if x: x = z + +var + a = true + b = true + c = false +a = b and a +echo a diff --git a/tests/patterns/tstar.nim b/tests/patterns/tstar.nim index ac3373214..8443268f4 100644 --- a/tests/patterns/tstar.nim +++ b/tests/patterns/tstar.nim @@ -10,7 +10,7 @@ proc `&&`(s: varargs[string]): string = for i in 1..len(s)-1: result.add s[i] inc calls -template optConc{ `&&` * a }(a: varargs[string]): expr = &&a +template optConc{ `&&` * a }(a: string): expr = &&a let space = " " echo "my" && (space & "awe" && "some " ) && "concat" diff --git a/todo.txt b/todo.txt index e5efa1f87..269338c63 100755 --- a/todo.txt +++ b/todo.txt @@ -2,7 +2,7 @@ version 0.9.0 ============= - make 'm: stmt' use overloading resolution -- document pattern matching +- fix the 'nil' bug in the AST - make 'bind' default for templates and introduce 'mixin' diff --git a/web/index.txt b/web/index.txt index def04048e..494e6a8f7 100755 --- a/web/index.txt +++ b/web/index.txt @@ -97,22 +97,19 @@ Nimrod plays nice with others libcurl, mySQL and SQLite are included in the standard distribution. * A C to Nimrod conversion utility: New bindings to C libraries are easily generated by ``c2nim``. -* A Pascal to Nimrod conversion utility: A large subset of Object Pascal - can be translated to Nimrod automatically! Roadmap to 1.0 ============== -Version 0.9.0 - * closures - Version 0.9.x - * recursive iterators/coroutines + * first class iterators * 2-phase type system for better interaction between macros, templates and overloading - * term rewriting macros * the syntactic distinction between statements and expressions will be removed + * the binding rules for generics and templates will change + * exception tracking + * the effect system will be extended * the need for forward declarations may be removed diff --git a/web/news.txt b/web/news.txt index a9d3336a7..2c9fd2715 100755 --- a/web/news.txt +++ b/web/news.txt @@ -162,6 +162,8 @@ Language Additions in templates. - Comments can be continued with a backslash continuation character so that comment pieces don't have to align on the same column. +- Enums can be annotated with ``pure`` so that their field names do not pollute + the current scope. 2012-02-09 Version 0.8.14 released diff --git a/web/nimrod.ini b/web/nimrod.ini index e8160146b..d81ec097c 100755 --- a/web/nimrod.ini +++ b/web/nimrod.ini @@ -21,7 +21,7 @@ FAQ: question file: ticker [Documentation] -doc: "endb;intern;apis;lib;manual;tut1;tut2;nimrodc;overview;filters" +doc: "endb;intern;apis;lib;manual;tut1;tut2;nimrodc;overview;filters;trmacros" doc: "tools;c2nim;niminst;nimgrep" pdf: "manual;lib;tut1;tut2;nimrodc;c2nim;niminst;gc" srcdoc: "core/macros;pure/marshal;core/typeinfo;core/unsigned" |