Chapter 5  Tom

5.1  Notations

5.1.1  Lexical conventions

5.1.2  Names

5.2  Tom constructs

public class HelloWorld {
  %include { string.tom }

  public final static void main(String[] args) {
    String who = "World";
    %match(who) {
      "World" -> { System.out.println("Hello " + who); }
      _       -> { System.out.println("Don't panic"); }
    }
  }
}

5.2.1  Tom program

• MatchConstruct is translated into a list of instructions. This construct may appear anywhere a list of instructions is valid in the host language.
  
  
• StrategyConstruct is translated into a class definition. Since it is translated into a class, this construct is valid only for Java.
  
  
• RuleConstruct is translated into a function definition. This construct may appear anywhere a function declaration is valid in the host language.
  
  
• BackQuoteTerm is translated into a function call.
  
  
• IncludeConstruct is replaced by the content of the file referenced by the construct. Tom looks for include files in: ./packageName/, $TOM_HOME/share/jtom/ and <path>, where <path> is specified by option: --import <path>. If the file contains some Tom constructs, they are expanded.
  
  
• GomConstruct allows to define a Gom grammar. This construct is replaced by the content of the generated mapping. See the Chapter 6 for more details.
  
  
• TypeTerm, as well as Operator, OperatorList, and OperatorArray are replaced by some functions definitions.

5.2.2  Match construct

%match(s) {
  f(a(),g(y)) -> { /* code that uses y */ }
  f(x,g(b())) -> { /* code that uses x */ }
  f(x,y)      -> { /* code that uses x and y */ }
}

• a list of subjects,
  
  
• a list of PatternAction: this is a list of pairs (pattern,action), where an action is a set of host language instructions which is executed each time a pattern matches the subjects.

• given a list of sbject (they corresponds to objects only composed of constructors, called ground terms), the execution control is transferred to the first PatternAction whose patterns match the list of ground terms.
  
  
  Note: since version 2.4, a subject is no longer restricted to a host language variable. Term term built upon variables, constructors and function can be use. Note also that the sort is now optional.
  
  
  
• given such a PatternAction, the list of variables is instantiated and the associated semantic action is executed. The instantiated variable are bound in the underlying host-language, and thus can be used in the action part.
  
  
• if the execution control is transferred outside the %match instruction (by a goto, break or return for example), the matching process is finished. Otherwise, the execution control is transferred to the next PatternAction whose patterns match the list of ground terms.
  
  
• when there is no more PatternAction whose patterns match the list of subjects, the %match instruction is finished, and the execution control is transferred to the next instruction.

• given a PatternAction whose patterns match the list of ground terms, the list of variables is instantiated and the associated semantic action is executed.
  
  
• if the execution control is not transferred outside the %match instruction, in addition to the previous explanations, if the considered matching theory may return several matches, for each match, the free variables are instantiated and the associated semantic action is executed. This means that a same action may be executed several times, but in a different context: i.e. the variable have different instantiations.
  
  
• when all matches have been computed (there is at most one match in the syntactic theory), the execution control is transferred to the next PatternAction whose patterns match the list of ground terms.
• as before, when there is no more PatternAction whose patterns match the list of subject, the %match instruction is finished, and the execution control is transferred to the next instruction.

5.2.3  Tom pattern

• standard notation: a pattern can be defined using a classical prefix term notation. To make a distinction between variables and constants, the latter have to be written with explicit parentheses, like x(). In this case, the corresponding Tom operator (%op x()) should have been declared. When omitting parentheses, like x, this denotes a variable.
  
  
• unnamed variable: the _ notation denotes an anonymous variable. It can be used everywhere a variable name can be used. It is useful when the instance of the variable does not need to be used. Similarly, the _* notation can be used to denote an anonymous list-variable. This last notation can improve the efficiency of list-matching because the instances of anonymous list-variables do not need to be built.
  
  
• annoted variable: the @ operator allows to give a variable name to a subterm. In f(x@g(_)) for example, x is a variable that will be instantiated by the instance of the subterm g(_). The variable x can then be used as any other variable.
  
  
• implicit notation: as explained below, the %op operator forces to give name to arguments. Assuming that the operator f has two arguments, named arg1 and arg2, then we can write the pattern f[arg1=a()] which is equivalent to f(a(),_). This notation can be interesting when using constructors with many subterms.
  
  
• unnamed list operator: it is often the case that given a list-sort, only one list-operator is defined. It this case, when there is no ambiguity, the name of the operator can be omitted. Considering the conc list-operator for example (see %oplist and %oparray below), to improve the readability, the pattern conc(_*,x,_*) can be written (_*,x,_*). This feature is particularly useful in the XML notation introduced in the following.
  
  
• symbol disjunction notation: to factorize the definition of pattern which have common subterms, it is possible to describe a family of patterns using a disjunction of symbols. The pattern (f∣g)(a(),b()) corresponds to the disjunction f(a(),b()) or g(a(),b()). To be allowed in a disjunction (in standard notation), the constructors should have the same signature (arity, domain and codomain).
  
  In practice, it is usually better to use the disjunction notation with the implicit notation Tom offers: ((f∣g)[arg1=a()]). In that case, the signatures of symbols do not have to be identical: only involved slots have to be common (same names and types). Thus, the pattern (f∣g)[arg1=a()] is correct, even if g has more slots than f: it only has to have the slot arg1, with the same sort.
  
  
  Note: the disjunction of symbol can also be used in Xml notation: <(A∣B)>...</(A∣B)>.

5.2.4  Tom anti-pattern

5.2.5  Rule construct

• an equality condition (t₁ == t₂) is a pair of ground terms that belong to the same type. The condition is satisfied when the normal forms of the two terms (t₁ and t₂) are equal modulo the equals predicate defined in the definition of the type associated to t₁ and t₂.
• a matching condition (p := t) is a pair of terms where p may contain free variables. The condition is satisfied if the pattern p can be matched against the normal form of t. In this case, the free variables of p are instantiated and can be used in other conditions or the right-hand side of the rule.

5.2.6  Backquote construct

• `Name: to denote a Tom variable
• `Name`*': to denote a Tom list-variable
• `Name( ... ): to build a prefix term
• `( ... ): to build an expression
• `xml( ... ): to build an Xml term

5.2.7  Meta-quote construct

String hello = %[
  public class Hello {
    public static void main(String[] args) {
      System.out.println("Hello\n\tWorld !");
    }
  }
]%

String version = "v12";
String hello2=%[
  public class Hello {
    public static void main(String[] args) {
      System.out.println("Hello\n\tWorld   @version@");
    }
  }
]%;

5.3  Tom signature constructs

5.3.1  Sort definition constructs

• the implement construct describes how the new type is implemented. The host language part written between braces ('{' and '}') is never parsed. It is used by the compiler to declare some functions and variables.
  
  
• the visitor_fwd represents a Java class. In order to use strategies, sorts must define a Java class. This class must extend VisitorFwd and must implement the interface VisitableVisitor. The goal of the VisitorFwd is to provide a base class for building strategies. Thus, it has to provide typed visitors for each defined sort, and implement its visit method to call the typed visit_sort functions depending on the dynamic type of the subject. More information about visitor_fwd can be found in 7.7.
• the equals(t1,t2) construct corresponds to a predicate (parametrized by two term variables). This predicate should return true if the terms are “equal”. The true value should correspond to the builtin true value of the considered host language. This last optional predicate is used to compare builtin values and to compile non-linear left-hand sides.

 %typeterm TomPerson {
   implement { Person }
   equals(t1,t2) { t1.equals(t2) }
 }

5.3.2  Constructor definition constructs

%op TomPerson person(name:String, age:int)

• The is_fsym(t) { predicate(t) } construct is used to check if a term t is rooted by the considered symbol. The true value should correspond to the builtin true value of the considered host language (true in Java or Caml, and something different from 0 in C for example).
  
  
• The make(t1,...,tn) construct is parametrized by several variables (i.e. that should correspond to the arity of the symbol). A call to this make function should return a term rooted by the considered symbol, where each subterm correspond to the terms given in arguments to the function. When defining a constant (i.e. an operator without argument, make can be defined without brace: make { ... }).
  
  
• The get_slot(slotName,t) construct has to be defined for all slots of the signature. The implementation of these constructs should be such that the corresponding subterm is returned.

%op TomPerson person(name:String, age:int) {
  is_fsym(t)  { t instanceof Person }
  make(t1,t2) { new Person(t1,t2) }
  get_slot(name,t) { t.name } // assuming that 'name' is public
  get_slot(age,t)  { t.age  } // assuming that 'age' is public
}

• the make_empty() construct should return an empty list.
  
  
• the make_insert(e,l) construct corresponds to a function parametrized by a list variable and a term variable. This function should return a new list l' where the element e has been inserted at the head of the list l (i.e. equals(get_head(l'),e) and equals(get_tail(l'),l) should be true).
  
  
• the get_head(l) function is parametrized by a list variable and should return the first element of the considered list.
  
  
• the get_tail(l) function is parametrized by a list variable and should return the tail of the considered list.
  
  
• the is_empty(l) constructs corresponds to a predicate parametrized by a list variable. This predicate should return true if the considered list contains no element.

• the make_empty(n) construct should return a list of size n.
  
  
• the make_append(e,l) construct corresponds to a function parametrized by a list variable and a term variable.
  
  Warning: This function should return a list l' such that the element e is at the n-th position.
  
  
• the get_element(l,n) construct is parametrized by a list variable and an integer. This should correspond to a function that return the n-th element of the considered list l.
  
  
• the get_size(l) constructs corresponds to a function that returns the size of the considered list. By convention, an empty list contains 0 element.

  %typeterm Object {
    implement     { Object        }
    equals(l1,l2) { l1.equals(l2) }
  }
  %typeterm TomList {
    implement     { ArrayList    }
    equals(l1,l2) { l1.equals(l2) }
  }

  %oparray TomList conc( Object* ) {
    is_fsym(t)       { t instanceof ArrayList }
    make_empty(n)    { new ArrayList(n)       }
    make_append(e,l) { myAdd(e,(ArrayList)l)   }
    get_element(l,n) { (Object)l.get(n)        }
    get_size(l)      { l.size()                }
  }

  private static ArrayList myAdd(Object e,ArrayList l) {
    l.add(e);
    return l;
  }

5.3.3  Predefined sorts and operators

5.4  XML pattern