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

Expr x = # ; Expr y = #

bracketed ::= "#<" expr ">" expr ::= namewhere the curly bracketsthe representation of a name| integerthe repr. of an integer| stringthe repr. of a string| "`" nameescaping to the value of| "`(" code ")"nameescaping to the value of| expr "(" arg { "," arg } ")"codethe repr. of a function| expr "(" ")"function with no arguments| "`" name "[" expr "]"variable substitution (explained later)arg ::= exprthe repr. of an expression| "..." nameescaping to a list of values bound to| "..." "(" code ")"nameescaping to a list of values returned bycode

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

list * r = Cons(# ,Cons(#

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:

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

case ::= "#case" code { "|" pattern [ guard ] "=>" code } "#end" pattern ::= name | integer | string | "_"where thematch everything| "`" namepattern variable| pattern "(" arg { "," arg } ")"the repr. of a function| pattern "(" ")"function with no arguments| "`" name "[" pattern "]"second-order pattern matchingguard ::= ":" codean optional conditionarg ::= patternthe repr. of an expression| "..." namematch the rest of the arguments

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

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

Next page: Optimizer Specification in OPTL

Last modified: 2/19/97 by Leonidas Fegaras