<Macro Tutorial>

All macros in <bigwig> must be placed in packages (that is, files) and required by the service in order to be available for usage in the service program.

Basics

A very simple macro: Pi

---pi.wigmac---
syntax <floatconst> pi ::= {
  3.1415926
}

require "pi.wigmac"

service {
  session S() {
    float f;

    f = pi;
    ...;
  }
}

One of the simplest macros one could write, would be a macro that does not take any arguments as is the case for the macro pi in the example. When declared it will appear to the programmer as if the floatconst syntactic category had been extended with a production pi. This is different from a lexical macro in that the macro invocation of pi is only allowed in places where a floatconst would be. Also, the body of the macro is parsed and thus syntax checked to see if it complies with the declared return type (here floatconst) at definition time (not expansion time). This ensures that no parse errors are produced as a consequence of invoking the macro, regardless of invocation context.

A macro with an argument: Maybe

---maybe.wigmac---
syntax <stm> maybe <stm S> ::= {
  if(random(2)==1) <S>
}

require "maybe.wigmac"

service {
  session S() {
    html H = ...;

    maybe show H;
    ...;
  }
}

This example defines a new construct, maybe, that takes an argument, namely a statement and executes it with 50% probability. The argument taken (S) refer to a syntax tree (of kind statement) produced from parsing a statement and is in the body of the macro referred to as a normal identifier in angled brackets (<S>).

A macro definition with token separators: Plus

---plus.wigmac---
syntax <regexp> plus ( <regexp R> ) ::= {
  concat(<R>, star(<R>))
}

require "plus.wigmac"

service {
  session S() {
    format Digit = range('0', '9');
    format Number = plus(Digit);

    ...;
  }
}

In the <bigwig> grammar, one can see that there is something called star for Kleene's star on regular languages, signaling zero-or-more. However, there is nothing called "plus" for one-or-more. Such a construct could easily be defined by a macro. This is a nice example of a macro that uses token separators to enforce a particular syntax. The macro definition contains two tokens, namely the two parentheses. The compiler will thus automatically enforce that invocations of the macro plus contain the two parentheses in the sense that it would be a syntactic error to omit them. In this way the macro author can tailor the macros to have the desired look-and-feel.

Caution: this extreme flexibility could be abused to write macros that expected horrific syntax with, for instance, unbalanced parentheses of varying kinds. So the macro programmer should take some care when designing a macro's invocation syntax.

A macro with an identifier delimiter: Repeat-until

---repeat_until.wigmac---
syntax <stm> repeat <stm S> until ( <exp E> ) ; ::= {
  {
    <S>
    while (!<E>) <S>
  }
}

require "repeat_until.wigmac"

service {
  session S() {
    int x, y, z;

    ...;
    repeat {
      x = x * y;
      y--;
    } until (y==0);
    ...;
  }
}

This macro, repeat-until will take two arguments, S and E, delimited not only by tokens but also by an identifier "until". The repeat-until construct is transparent in the sense that it appears to the programmer as if it really was in the language.

Caution: The statement argument S is used twice in the body of the macro and because arguments are copied (for good reason), the repeat-until macro may cause an explosion in the size of the parse tree produced when the construct is nested. We shall see later how to define the repeat-until macro without potential parse tree explosion.

A macro in terms of another: Forever

---forever.wigmac---
syntax <stm> repeat <stm S> until ( <exp E> ) ; ::= {
  {
    <S>
    while (!<E>) <S>
  }
}

syntax <stm> forever <stm S> ::= {
  repeat <S> until (false);
}

require "forever.wigmac"

service {
  session S() {
    html H = ...;

    forever show H;
  }
}

A macro can easily be defined in terms of another as is the case in this example, where we have defined a new macro forever in terms of repeat-until. The repeat-until macro will only be expanded once, namely when the forever macro is defined (i.e. parsed).

2pass scope rules

---forever.wigmac---
syntax <stm> forever <stm S> ::= {
  repeat <S> until (false);
}

syntax <stm> repeat <stm S> until ( <exp E> ) ; ::= {
  {
    <S>
    while (!<E>) <S>
  }
}

require "forever.wigmac"

service {
  session S() {
    html H = ...;

    forever show H;
  }
}

<bigwig> macro definitions have two-pass scope rules, which means that a macro is available in a package even before its lexical point of definition. This service is semantically equivalent to the previous one.

Recursion not allowed!

---illegal.wigmac---
syntax <stm> Rec ::= {
  ...Rec...;
}

require "illegal.wigmac"

service {
  ...
}

Without a compile-time language for ``breaking the recursion'', recursion can only yield infinite program fragments. Therefore, macro recursion (and mutual recursion) is not permittet in <bigwig>. However, as we shall see later, <bigwig> supports metamorphic macros which enable recursive definitions that yield finite expansions.

Stacking packages

---repeat_until.wigmac---
syntax <stm> repeat <stm S> until ( <exp E> ) ; ::= {
  {
    <S>
    while (!<E>) <S>
  }
}
---forever.wigmac---
require "repeat_until.wigmac"

syntax <stm> forever <stm S> ::= {
  repeat <S> until (false);
}

require "forever.wigmac"

/* Only the `forever' macro is available here! */
service {
  session S() {
    html H = ...;

    forever show H;
  }
}

This service is again semantically equivalent to the two previous ones. Here, we have split the package into two packages, one for each macro. The forever package requires the repeat package in order to use it. Since the repeat package is required (as opposed to extended), it is local to the forever package and will not be exported beyond it (to the service). Thus, only the forever macro is available in the service.

Extend

---repeat_until.wigmac---
syntax <stm> repeat <stm S> until ( <exp E> ) ; ::= {
  {
    <S>
    while (!<E>) <S>
  }
}
---forever.wigmac---
extend "repeat_until.wigmac"

syntax <stm> forever <stm S> ::= {
  repeat <S> until (false);
}

require "forever.wigmac"

/* Both macros are available here! */
service {
  session S() {
    html H = ...;

    repeat show H; until (1==2);
  }
}

This service is slightly different than the previous one in that the forever package extends the repeat package. This means that both macros are exported from the forever package into the service.

Intermediate

Specificity (split: ``end'' vs. terminal)

---split.wigmac---
syntax <stm> si (<exp E>) <stm S1> ::= {
  if (<E>) <S1>
}

syntax <stm> si (<exp E>) <stm S1> sinon <stm S2> 
    ::= {
  if (<E>) <S1> else <S2>
}

require "split.wigmac"

service {
  session S() {
    int x,y;

    ...;
    si (f(x)>0) si (f(y)<0) x++; sinon y--;
    ...;
  }
}

In <bigwig> several macros may have the same name. However, macros with the same name must all have the same nonterminal return type. Also, their headers (invocation syntax design) are not allowed to be exactly the same which means that at some point the headers are said to split. In the example the two si macros have same headers up until after the statement argument (S1); after which the first macro ``ends'' and the second has a (terminal symbol) "sinon" identifier. Invocation parsing always selects the most specific definition for an invocation. In the example, the first "si" will commence macro parsing, the second "si" will commence another instance of macro parsing and will after the "x++;" statement be left with a choice of whether to take the first definition (stop) or the second (match the "sinon"). The macros are greedy, to the second definition will be taken; correctly solving the dangling-sinon problem.

In detail: There are three kinds of header elements; terminals, nonterminals, and ``end''. Invocation parsing is conducted in challenge rounds, header element after header element. Whenever a macro invocation is parsed, the current token on the input stream is matched against all (live) macro definitions to see if they are compatible. Those macro definitions that are not are immediately eliminated (set to non-live). Between the compatible macro definitions, the ones (there may be more than one) that are the most specific are kept, the others are eliminated. The following specificity relation is used:

terminal < nonterminal < ``end''

Specificity (split: terminal vs. nonterminal)

---split.wigmac---
syntax <stm> pay 1 dollar ; ::= {
  ...1...;
}

syntax <stm> pay <exp E> dollars ; ::= {
  ...<E>...;
}

require "split.wigmac"

service {
  session S() {
    ...;
    pay 1 dollar;  // 1st definition.
    pay 7 dollars; // 2nd definition.

    ...;
  }
}

This example again illustrates the specificity splitting. The "1" in the first macro invocation "pay 1 dollar;" matches both definitions, since "1" is in the set of first-tokens of expressions. However, due to the specificity relation, the terminal is favored over the nonterminal; meaning that the first definition is chosen.

Pretty printer directives

---split.wigmac---
syntax <stm> si (<exp E>) <stm S1> ::= {
  if (<E>) <S1>
}

syntax <stm> si (<exp E>) <stm S1> \n sinon <stm S2> 
    ::= {
  if (<E>) <S1> else <S2>
}

require "split.wigmac"

service {
  session S() {
    int x,y;

    ...;
    si (f(x)>0) si (f(y)<0) x++; sinon y--;
    ...;
  }
}

The <bigwig> pretty printer is able to ``unparse'' the source code with or without expanding macros. When unparsing without macro expansion, the macro programmer is allowed to instruct the pretty printer how to pretty print a macro invocation. That is, when to insert newlines, whitespaces, even how to indent a macro invocation. The characters \n (newline), \+ (indent), and \- (unindent) are available for this. In the example, the "si-sinon" macro is instructed to print a newline character before the "sinon". Also, whitespaces are significant in the definition headers. Note that there are no spaces between the expression argument (E) and the parentheses. This means that the expression will be printed in parentheses without spaces.

Repeat-until: Alpha-conversion

---alpha.wigmac---
syntax <stm> repeat <stm S> until ( <exp E> ) ; ::= {
  {
    bool first = true; // first is alpha-converted!

    while (first || !<E>) {
      <S>
      first = false;
    }
  }
}

require "alpha.wigmac"

service {
  session S() {
    int x, y, z;

    ...;
    repeat {
      x = x * y;
      y--;
    } until (y==0);
    ...;
  }
}

As promised we define a repeat-until macro that does not cause parse tree explosion. We exploit runtime behaviour of <bigwig> (the host language) to give our macro the right semantics. We introduce a new bool variable first to remember (at runtime) whether or not we have executed the statement S. Note that as in C, the boolean-or operator "||" is lazy and since first is initially true, E never gets evaluated the ``first time around''. One could suspect that invocations of such a macro could yield identifier clashes if the statement contained a reference to an identifier first that was defined outside the invocation. However, with the <bigwig> macros this is not the case. Any non-argument identifier in a macro is automatically alpha-converted (renamed) to avoid accidental name-clashes. This hygienic property allows us to safely define macros such as the one above.

Alpha-conversion suppression: ` (operator)

---declare_i.wigmac---
syntax <decl> declare_i ; ::= {
  int `i = 42; // Caution! 
}

require "declare_i.wigmac"

service {
  session S() {
    declare_i;

    i = 87;
    ...;
  }
}

We have as a feature introduced an alpha-conversion suppression operator "`" (backping). So in this example, the code produced by the invocation of the macro declare_i declares an identifier named exactly i which is the one subsequently assigned 87.

Caution: This operator should be used with caution, as macros defined using it become highly context sensitive!

Advanced

This section of the macro tutorial will present the concept of metamorphisms. A metamorphism is a user defined (meta-grammar) nonterminal along with a rule specifying how the new (macro) syntax is morphed into host language (<bigwig>) syntax. As we shall see, metamorphisms can be used to define macros accepting almost arbitrary syntax with a varying number of arguments.

We will commence by gently introducing metamorphisms through a couple of toy examples after which we will look at some "real" examples.

Metamorphisms: Abbreviation

---si.wigmac---
metamorph <exp> until_part --> until (<exp Cond>) ::=
{
  <Cond>
}

syntax <stm> repeat <stm S> <until_part: exp E> ; ::=
{
  {
    <S>
    while (!<E>) <S>
  }
}

require "si.wigmac"

service {
  session S() {
    int x, y, z;

    ...;
    repeat {
      x = x * y;
      y--;
    } until (y==0);
    ...;
  }
}

A simple use of metamorphisms is to abbreviate definitions. In this toy example we have written the previous "repeat-until" macro, but where we have cut the definition in two parts by introducing a new nonterminal until_part. When a "repeat" macro invocation is being parsed and the parser comes to the metamorph argument...

<until_part: exp E>

...the parser will parse a (user defined) until_part which will yield an expression that will be called (E). Hereafter, parsing of the repeat macro is resumed, which will parse the terminal ";". This example is not very useful in the sense that it could easily have been defined as a (normal) macro, but it serves to illustrate metamorphisms.

Metamorphisms: Splitting

---si.wigmac---
metamorph <stm> opt_else --> ::= {
  /* empty */;
}

metamorph <stm> opt_else --> sinon <stm S> ::= {
  <S>
}

syntax <stm> si (<exp E>) <stm S1> 
    <opt_else: stm S2> ::= {
  if (<E>) <S1> else <S2>
}

require "si.wigmac"

service {
  session S() {
    int x,y;

    ...;
    si (f(x)>0) si (f(y)<0) x++; sinon y--;
    ...;
  }
}

The same splitting rules we saw for the (normal) macros also apply to metamorphisms. The specificity relation is extended in the following way:

terminal < nonterminal < metamorph < ``end''

Metamorphisms: Lists

---xlist.wigmac---
metamorph <stm> xlist --> ::= {
  /* empty */;
}

metamorph <stm> xlist --> X <xlist: stm S> ::= {
  <S>
}

syntax <stm> Xlist <xlist: stm S> ; ::= {
  <S>
}

require "xlist.wigmac"

service {
  session S() {
    Xlist X X X X;
  }
}

This example shows how lists can easily be defined with metamorphisms. The macro "Xlist" takes a metamorph argument xlist that can do one of two things; stop or parse an "X" followed by an ``xlist''. The result is that the macro will parse "Xlist" followed by an arbitrary number of "X"'es and transform this into the empty statement.

Metamorphisms: No Left Recursion!

---illegal.wigmac---
metamorph <stm> xlist --> ::= {
  /* empty */;
}

metamorph <stm> xlist --> <xlist: stm S> X ::= {
  <S>
}

syntax <stm> Xlist <xlist: stm S> ; ::= {
  <S>
}

require "illegal.wigmac"

service {
  session S() {
    Xlist X X X X;
  }
}

This is an example of an illegal service. Since the parser is a modified LL(1) top-down parser, left recursion would cause it to loop. Consequently, left recursion is intercepted and rejected by the parser. One should instead make the metamorphisms right recursive as in the previous example.

Metamorphisms: Productivity!

---illegal.wigmac---
metamorph <stm> xlist --> X <xlist: stm S> ::= {
  <S>
}

syntax <stm> Xlist <xlist: stm S> ; ::= {
  <S>
}

require "illegal.wigmac"

service {
  session S() {
    Xlist X X X X ...
  }
}

This is another example of an illegal macro. As a sanity check, the <bigwig> parser will check that all metamorphisms derive something (finite). The xlist nonterminal in this example cannot derive something finite and is thus rejected.

Metamorphisms: Palindrome

---palindrome.wigmac---
metamorph <stm> p --> C ::= {
  /* empty */;
}

metamorph <stm> p --> A <p: stm S> A ::= {
  <S>
}

metamorph <stm> p --> B <p: stm S> B ::= {
  <S>
}

syntax <stm> palindrome ( <p: stm S> ) ; ::= {
  <S>
}

require "palindrome.wigmac"

service {
  session S() {
    palindrome ( A B A C A B A );
  }
}

So far we have seen how metamorphisms could be used to parse list structures. This (toy) example shows how also tree structures can be parsed. The macro "palindrome" accepts palindromes over the alphabet {"A", "B"} with a "C" in the middle.

Metamorphisms: Enum

---enum.wigmac---
syntax <decl_list> enum { <id I> 
    <enum_list: decl_list EL> } ; ::= {
  int e;
  const int <I> = e++;
  <EL>
}

metamorph <decl_list> enum_list --> ::= {
}

metamorph <decl_list> enum_list --> , <id I> 
    <enum_list: decl_list EL> ::= {
  const int <I> = e++;
  <EL>
}

require "enum.wigmac"

service {
  session S() {
    int n;
    enum { ZERO, ONE, TWO, THREE };

    n = ONE+TWO*THREE;
  }
}

This real example shows how enums can easily be added to the <bigwig> language. The "enum" macro produces a list of declarations using an integer variable for e generating the enumeration values. This e will be alpha converted to the same fresh identifier in the macro and the two metamorphisms.

Metamorphisms: Switch

---Switch.wigmac---
syntax <stm> Switch { \+\n <swbody: stm S> \-\n } ::=
{
  {
    typeof(<E>) x = <E>;
    <S>
  }
}

metamorph <stm> swbody --> Case <exp E> : 
    <stm_list SL> Break ; <swbody: stm S> ::= {
  if (x==<E>) { <SL> } else <S>
}

metamorph <stm> swbody --> Case <exp E> :
    <stm_list SL> Break ; ::= {
  if (x==<E>) { <SL> } 
}

require "Switch.wigmac"

service {
  session S() {
    int x, y, dot_com, dot_org;
    string s;

    ...;
    Switch (s) {
      Case ".com":
        dot_com++;
        f(x);
        Break;
      Case ".org":
        dot_org++;
        g(y);
        Break;
    }
  }
}

This example shows how to make the "Switch" statement with a capital S (because <bigwig> already has a switch statement).

bigwig@brics.dk
Last updated: November 2, 2001