OPTL Syntax

# Meta-Programming in OPTL

An OPTL source program is a C++ program enhanced with a number of syntactic constructs to make the task of the optimizer specification more tractable. The main data structure used by these language constructs is `Expr`, defined in basic.h. It is a tree-like data structure which is used for representing both algebraic forms and execution plans. For example, the C++ expression

    function(variable("join"),
             Cons(variable("R"),
                  Cons(variable("S"),
                       Cons(function(variable("eq"),
                                     Cons(variable("A"),Cons(variable("B"),Nil))),
                            Nil))))

constructs the algebraic term `join(R,S,eq(A,B))`, where `Cons` and `Nil` are the list constructors (e.g., `Cons(1,Cons(2,Cons(3,Nil)))` constructs the list `[1,2,3]` of type `list<int>`). To make the task of writing these tree constructions less tedious, OPTL extends C++ with the syntactic form `#< >`. For example, `#<join(R,S,eq(A,B))>` is equivalent to the above C++ expression. That is, the text within the brackets `#< >` is used by OPTL to generate C++ code, which creates the tree-like form (of type `Expr`) that represents this text. Values of type `Expr` can be included into the form generated by the `#< >` brackets by "escaping" them with a backquote character (```). The operand of the escape operator (the backquote operator) is expected to be an expression of type `Expr` that provides the value to "fill in" the hole in the bracketed text at that point. For example, in

      Expr x = #<join(a,b,p)>;
      Expr y = #<select(`x,q)>;
      Expr z = #<project(`y,A)>;

`y` is set to `#<select(join(a,b,p),q)>` and `z` to `#<project(select(join(a,b,p),q),A)>`. The BNF of the bracketed syntax is the following:

    bracketed ::= "#<" expr ">"
    expr      ::=   name                                 the representation of a name
                  | integer                              the repr. of an integer
                  | real                                 the repr. of a real
                  | string                               the repr. of a string
                  | "`" name                             escaping to the value of name
                  | "`(" code ")"                        escaping to the value of code
                  | expr "(" arg { "," arg } ")"         the repr. of a function
                  | expr "(" ")"                         function with no arguments
                  | "`" name "[" expr "]"                variable substitution (explained later)
    arg       ::=   expr                                 the repr. of an expression
                  | "..." name                           escaping to a list of values bound to name
                  | "..." "(" code ")"                   escaping to a list of values returned by code

where the curly brackets `{ }` in BNF indicate zero or more repetitions of the symbol sequence inside the curly brackets, and `code` is any C++ code. The `#< `(code) >` embeds the value returned by the C++ code `code` of type `Expr` to the term representation inside the brackets. For example, `#<`f(6,g("ab",`(k(1))),`y)>` is equivalent to the following C++ code:

    function(f,Cons(function(variable("g"),Cons(string("ab"),Cons(k(1),Nil))),
             Cons(y,Nil)))

If `f=#<h>`, `y=#<m(1,"a")>`, and `k(1)` returns the value `#<8>`, then the above term is equivalent to `#<h(6,g("ab",8),m(1,"a"))>`. The three dots (`...`) construct is used to indicate a list arguments in a function call. Since the arguments of a function call form a value of type `list<Expr>`, the type of `name` in `...name` is also `list<Expr>`. For example, in

      list<Expr>* r = Cons(#<join(a,b,p)>,Cons(#<select(c,q)>,Nil));
      Expr z = #<project(...r)>;

`z` will be bound to `#<project(join(a,b,p),select(c,q))>`.

OPTL provides a case statement syntax with patterns. Patterns match the `Expr` representations with similar shape. Escape operators applied to variables inside these patterns represent variable patterns, which "bind" to corresponding subterms upon a successful match. This capability makes it particularly easy to write functions that perform source-to-source transformations. A function that simplifies arithmetic expressions can be expressed easily as:

      Expr simplify ( Expr e ) {
        #case e
        |  plus(`x,0) => return x;
        |  times(`x,1) => return x;
        |  times(`x,0) => return #<0>;
        |  _ => return e;
        #end;
      };

where the `_` pattern matches any value. For example, `simplify(#<times(z,1)>)` returns `#<z>`, since `times(z,1)` matches the second case pattern. The BNF for the case statement is:

    case    ::= "#case" code { "|" pattern [ guard ] "=>" code } "#end"
    pattern ::=   name
                | integer
                | real
                | string
                | "_"                                          match everything
                | "`" name                                     pattern variable
                | pattern "(" arg { "," arg } ")"              the repr. of a function
                | pattern "(" ")"                              function with no arguments
                | "`" name "[" pattern "]"                     second-order pattern matching
    guard   ::=   ":" code                                     an optional condition
    arg     ::=   pattern                                      the repr. of an expression
                | "..." name                                   match the rest of the arguments

where the `[ ]` brackets indicate an optional sequence of symbols. For example, the pattern ``f(...r)` matches any function call: when it is matched with `#<join(a,b,c)>`, it binds `f` to `#<join>` and `r` to the list `Cons(#<a>,Cons(#<b>,Cons(#<c>,Nil)))`. For example, the following function adds the terms `#<8>` and `#<9>` as the first parameters to any function `e`:

      Expr add_arg ( Expr e ) {
        #case e
        |  `f(...r) => return #<`f(8,9,...r)>;
        |  `x => return x;
        #end;
      };

As another example of a case statement in OPTL, consider the following function, which switches the inputs of a binary join found as a parameter to a function `e`:

      Expr switch_join_args ( Expr e ) {
        #case e
        |  `f(...r,join(`x,`y),...s) => return #<`f(...r,join(`y,`x),...s)>;
        |  `x => return x;
        #end;
      };

The most powerful construct in OPTL is second-order pattern matching, denoted by the special syntax ``f[pattern]`. When ``f[pattern]` is matched against an `Expr`, `e`, it traverses the entire tree representation of `e` (in root-left-right order) until it finds a tree node that matches the `pattern`; when it finds one, say node `n`, it replaces this node with a fresh variable (i.e. a variable that has not been used before), say `v`, binding the pattern variables in `pattern`. Then it continues traversing the rest of the tree, replacing every node equal to `n` with `v`. At the end, if the matching succeeds, it binds `f` to the term `bind(v,u)`, where `u` is `e` in which all nodes equal to `n` have been replaced by `v`. That way, second-order pattern matching can be used for factorizing common subexpressions. Similarly, a term construction ``f[x]` expects `f` to be of the form `bind(v,u)`. It replaces all occurrences of `v` in `u` with the `Expr` `x`. For example, the OPTL program

      Expr n = new_variable();
      #case e
      |  `f[join(`x,`y)] => return #<let(`n,join(`x,`y),`f[`n])>;
      #end;

extracts the first term that matches a join from the term `e` and it pulls the term out in a let-binding (`n` is a user-defined fresh variable).

Next page: Optimizer Specification in OPTL