To illustratively explain what we can do with the help of Kimwitu++ we call upon an example. Let us imagine we want to write a computer game. Neat example. Respectable programmers as we are we calculate the overall costs of the new project in advance. It will take us, say, 30 days, on each we need to have a pizza at 7 € and 3 beer at 2 € each, but luckily meanwhile our grandma supports us with 100 €. We get the expression and type it in postfix notation into our RPN-calculator. You know, one of the antiquated devices knowing nothing about precedence nor parentheses and expecting input in Reverse Polish Notation, where operands precede their operator.

So we type 30 8 3 2 * + * 100 -. Er, we cannot. I remember. The calculator gave up the ghost last week. But don't despair. We quickly program a new one.

What exactly should the new calculator be able to do? Anyhow, it better would accept also variables. Why? Just imagine a drastic shortage of pizza and beer what would urge us to setup a new expression again. We better use a flexible one which can be seen in example Example 1.1, “Sample Expression”, in which x is the price of a beer and we know the price of a pizza always to be 4 times a beer.

Example 1.1. Sample Expression

(and resulting input in RPN: 30 4 x * 3 x * + * 100 -)

We now list the requirements on the calculator in proper order.

We assume the existence of a code component (a scanner) providing us with syntactical tokens like operators, numbers and identifiers (variables). We then need a description of correct input, a grammar. Our example demands a valid arithmetical term only to consist of numbers, identifiers, and the four arithmetical operators. A formal notation as used by the parser generator Yacc (see the section called “Yacc/Bison”) would look like in example Example 1.2, “Yacc Grammar for Sample”.

  aritherm:     simpleterm
	      | aritherm aritherm '+'
	      | aritherm aritherm '-'
	      | aritherm aritherm '*'
	      | aritherm aritherm '/';
	      
  simpleterm:   NUMBER
	      | IDENT;
      

Such a grammar is made up of rules, each having two sides separated by a colon. These rules describe how the left-hand side called nonterminal can be composed of syntactical tokens called terminals, which are typed in upper case letters or as single quoted characters. Different alternatives are separated by bar. The right-hand side may also contain nonterminals which there can be regarded to be an application of their respective composition rule.

The first rule of this grammar defines an aritherm to be a simpleterm or a composition of two aritherms and an operator sign. These aritherms in turn may be composed according to the aritherm rule. The second rule describes what an aritherm looks like, if it is a simpleterm.

A common way to hold an input term internally is to keep it as a syntax tree, that is a hierarchical structure of nodes (upside down tree). A nonterminal can be regarded as a node type and every alternative of the assigned right-hand side as one kind of that type. Every actual node thus is a kind of a node type with a specific number of child nodes, which depends on the kind. For example '+' is a kind of aritherm and it has 2 child nodes, while NUMBER is a kind of simpleterm and it has none. Figure Figure 1.1, “Syntax tree representing sample term” shows a syntax tree for our sample input term. Since every node is a term itself such a tree is more generally called a term tree.

Figure 1.1. Syntax tree representing sample term

To summarise the task identified: we want to build a tree from the term which has been typed in, walk over the tree nodes, and perform appropriate actions like calculating, simplifying or printing some results.

In a programming language a node type is usually represented as a structured data type, that is, as a class in object oriented languages and as a sort of record in others. A kind, then, may be a class variant or a subclass, and a variant record respectively. The code fragment in example Example 1.3, “Node Types as Classes with C++” illustrates a possible implementation in C++ (the kind as a subclass). The classes left out are to define similar.

  class Aritherm			{ /* ... */ };
  class Simpleterm : Aritherm           { /* ... */ };
	
  class Plus	      : public Aritherm
  {
    public :
      Plus( Aritherm *a, Aritherm *b ) : t1 ( a ), t2 ( b )
      { /* ... */ };
    private:
      Aritherm *t1, *t2;
  };

  class Number	      : public Simpleterm
  {
    public :
      Number( int a ) : n ( a )
      { /* ... */ };
    private:
      int n;
  };
      

From these classes we can instantiate C++ objects to represent our sample tree. We can navigate through it by accessing the child nodes of nodes. Not really yet, if you look closely at it. The child nodes are private members and thus they can not be accessed. We have to make them public or to add methods for their access. But what about the next step, simplifying parts of the tree? The subtree could be transformed to, right, , by putting x outside the parentheses, as illustrated in figure Figure 1.2, “Simplification of a samples subtree”. For C++ this may look like listed in example Example 1.4, “Term Substitution with C++”.

Figure 1.2. Simplification of a samples subtree

	
  if( dynamic_cast<Sum> ( A ) !=0 &&
      dynamic_cast<Mul> ( dynamic_cast<Sum>( A ) -> t1 ) !=0 &&
      dynamic_cast<Mul> ( dynamic_cast<Sum>( A ) -> t2 ) !=0 &&
      dynamic_cast<Mul> ( dynamic_cast<Sum>( A ) -> t1 ) -> t2 == 
      dynamic_cast<Mul> ( dynamic_cast<Sum>( A ) -> t2 ) -> t2 )
  {

     A = new Mul ( new Sum (
      dynamic_cast<Mul> ( dynamic_cast<Sum>( A ) -> t1 ) -> t1,
      dynamic_cast<Mul> ( dynamic_cast<Sum>( A ) -> t2 ) -> t1 ),
      dynamic_cast<Mul> ( dynamic_cast<Sum>( A ) -> t1 ) -> t2 );
  };
	
      

That seems quite complicated and it is even more so! Not only have we to cast for every child node access, to avoid memory leaks we had to free memory of unused nodes as old A and its child nodes. Furthermore the equality check between t1 and t2 will merely compare pointer values, instead of checking whether the subtrees are structurally equal. Thus we additionally need to overload the equality operators. What a lot of trouble for such a simple example!

Kimwitu++'s name is formed after Swahili while the ‘++’ reminds on C++.

Thus the name indicates affiliation to trees and to C++. You guessed it before, didn't you? More strictly spoken Kimwitu++ is a tool which allows to describe in an easy way how to manipulate and to evaluate a given term tree. From these descriptions C++ code is generated and compiled to a program which processes terms. That is why Kimwitu++ itself is called a term processor.

The code for building a tree, we have to write ourselves, or we let preferably other tools generate it. We use Yacc to call term creation routines which are generated from a Kimwitu++ abstract grammar. This we have to specify first. It is similar to the Yacc grammar, but its right-hand side alternatives are operators applied to nonterminals. An abstract grammar for our sample can be seen in example Example 1.5, “Abstract Grammar for Sample”. The nonterminals integer and casestring are predefined in Kimwitu++.

  aritherm:	SimpleTerm  ( simpleterm )
	      | Plus	    ( aritherm aritherm )
	      | Minus	    ( aritherm aritherm )
	      | Mul	    ( aritherm aritherm )
	      | Div	    ( aritherm aritherm );

  simpleterm:   Number	    ( integer )
	      | Ident	    ( casestring );
      

Next we have to complete the Yacc grammar by adding semantic actions in braces to every alternative. These recursively create a term tree which has its root element assigned to the variable root_term. Example Example 1.6, “Completed Yacc Grammar for Sample” shows this grammar, in which $$ denotes the term under construction and $1 and $2 its first and its second subterm (child node).

  aritherm:    simpleterm
		{ root_term = $$ = SimpleTerm( $1 ); }
	      | aritherm aritherm '+'
		{ root_term = $$ = Plus( $1, $2 ); }
	      | aritherm aritherm '-'
		{ root_term = $$ = Minus( $1, $2 ); }
	      | aritherm aritherm '*'
		{ root_term = $$ = Mul( $1, $2 ); }
	      | aritherm aritherm '/'
		{ root_term = $$ = Div( $1, $2 ); };

  simpleterm:   NUMBER
		{ $$ = Number( $1 ); }
	      | IDENT
		{ $$ = Ident( $1 ); };
      

That is it for building a tree. Everything else is left to the automatic code generation. Modifying or evaluating the tree needs its own rules (see chapter Chapter 4, Modifying and Evaluating Term Trees).

The language Kimwitu++ is an extension of C++ for handling of term trees. It allows the definition of term types, creation of terms, and provides mechanisms for transforming and traversing trees as well as saving and restoring them. Besides creating it in static code a tree can dynamically be obtained by interfacing with compiler generator C++ code (as from Yacc/Bison). The Kimwitu++ processor generates C++ code from the contents of Kimwitu++ input (.k-files). Compilation of that code yields the term processing program.

How are phyla defined? Example Example 1.5, “Abstract Grammar for Sample” shows that each phylum is defined as an enumeration of its kinds, each being an operator applied to a number of phyla, maybe zero. So the operator SimpleTerm takes one simpleterm phylum, Plus takes two aritherm phyla. There are several predefined phyla, of which integer and casestring already have been mentioned. The latter denotes a case sensitive character string. If a phylum is defined more than once, all occurrences contribute to the first one. For each phylum, a C++ class is generated.

We may want to define a phylum as a list of phyla. Imagine we wanted not only to type one expression into our calculator but several ones at once, separated in input by, say, a semicolon. The main phylum, representing whole the input, would be a list of aritherms. This is a right-recursive definition of a list which may be a nil (empty) list. The name of the list phylum prefixed by Nil and Cons make up common names for the two list operators. The other way to define a list phylum is to use the built-in list operator. This not only looks more simple but causes the generation of additional list functions. Example Example 2.1, “Recursive and built-in List Definition” shows both definitions.

  arithermlist:	    Nilarithermlist ( )
		  | Consarithermlist( aritherm arithermlist );

  arithermlist: list aritherm;
      

Each phylum definition can contain declarations of attributes of phylum or arbitrary C++ types. They follow the operator enumeration as a block enclosed in braces. What purpose do they serve? With them, we can attach additional information to nodes, which otherwise could only unfavourably be represented in the tree. In our example, we may take advantage of attributes by saving intermediate results to support the calculation. Therefore we extend the definition of aritherm from example Example 1.5, “Abstract Grammar for Sample” to example Example 2.2, “Phylum Definition with Attributes”.

  aritherm:     SimpleTerm    ( simpleterm )
	      | Plus	      ( aritherm aritherm )
	      | Minus	      ( aritherm aritherm )
	      | Mul	      ( aritherm aritherm )
	      | Div	      ( aritherm aritherm )
	      { int result	  = 0;
                bool evaluated    = false;
                bool computable   = true;
	      };
      

Attribute result should hold the intermediate result of an aritherm, if it already has been evaluated (evaluated==true) and found computable during the evaluation (computable==true), that is the subterms contain no variables. The attributes can be initialized at the declaration or inside an additional braces block which may follow the declarations and can contain arbitrary C++ code. Example Example 2.3, “Alternative Attributes Initialization” shows an alternative to the initialization from example Example 2.2, “Phylum Definition with Attributes”.

              { int result;
                bool evaluated;
                bool computable;
                { $0->result      = 0;
                  $0->evaluated   = false;
                  $0->computable  = true; }
              };
      

That C++ code is executed when a term of that phylum has been created. It can be referred to as $0 and its attributes can be accessed via the operator ->.

Patterns are a means to select specific terms which can be associated with a desired action. Example Example 3.1, “Patterns” shows some patterns and explains what terms they match. Patterns are used in special statements and in rewrite and unparse rules (see the section called “Special Statements” and Chapter 4, Modifying and Evaluating Term Trees respectively).

  Plus( *, * )
  // matches a term Plus with two subterms

  c=Plus( a, b )
  // matches a term Plus with two subterms, which are assigned to
  // the variables a and b, while the term itself is assigned to c

  Plus( a, a )
  // similar to the previous case, but matches only if the two subterms
  // are structurally equal; variable a gets assigned the first subterm

  Plus( Mul( a, b ), * )
  // matches a term Plus with two subterms, whereof the first one
  // is a Mul term with the subterms assigned to the variables a and b

  Plus( a, b ), Minus( a, b )
  // matches if the term in question is either a Plus or a Minus; the
  // two subterms then are assigned to the variables a and b
      

Kimwitu++ provides two statements as extensions to C++ which make it more comfortable to deal with terms. These are the with-statement and the foreach-statement. They can be used in functions and in the C++ parts of unparse rules (see the section called “Traversing”).

The with-statement can be considered as a switch-statement for a phylum. It contains an enumeration of patterns which must describe kinds of the specified phylum. From these, the one is chosen which matches a given term best. Then the C++ code is executed, which was assigned to that pattern.

Example Example 3.2, “with-statement” takes a term of the phylum aritherm and calculates the attribute result, if the term is a sum or a difference, by adding or subtracting the results of the subterms. The keyword default serves as a special pattern in with, which matches when none of the others does.

In the first case, the two subterms are assigned to the variables a and b, which can be used in the C++ part. The term itself is assigned to variable c which thus refers to the same term as the variable at. Variable at is visible throughout the entire with body and it can be accessed in all C++ parts. It may get a new term assigned as it is done in the second case whithin which the variable at refers to the first subterm.

  aritherm at;
  ...
  with ( at ) {
    c = Plus ( a, b )	:  { c -> result = a -> result + b -> result; }
    Minus ( at, b )	:  { c -> result = at -> result - b -> result; }
    default		:  { }
  }
      

The second special construct is the foreach-statement, which iterates over a term of a list phylum and performs the specified actions for every list element. Example Example 3.3, “foreach-statement” determines the greatest result from the terms in the list a.

  int max = 0;
  foreach( a; arithermlist A ){
    if( a -> result > max ) max = a -> result;
  }
	

Rewriting denotes the process of stepping through the tree, seeking the terms that match a pattern and substituting them by the appropriate substitution term. Rewrite rules consist of two parts, where the left-hand side is a pattern (as described in the section called “Patterns”) and the right-hand side is a substitution term enclosed by angle brackets. A term must always be substituted by a simpler one, that is by one that is nearer to the desired form of result. Otherwise the substitution process may never stop.

Let us try simplifying according to figure Figure 1.2, “Simplification of a samples subtree” to demonstrate the usage of rewrite rules. What would the rules look like in Kimwitu++ to achieve a simplification of that kind? Example Example 4.1, “Term Substitution using Kimwitu++” shows a solution using rewriting. It is quite short in comparison with example Example 1.4, “Term Substitution with C++”, isn't it?

  Mul( Plus( a, b ), Plus( c, b ) ) -> <: Plus( Mul( a, c ), b )> ;
	

An equivalent part would cover the case that b takes the first position in both subterms. The meaning of the colon will be explained in the section called “Views”.

Originally unparsing was meant to be a reverse parse, used to give a formatted output of the tree built. In general it should better be recognized as a way to traverse the tree. Unparse rules have a structure similar to that of rewrite rules. The left-hand side consists of a pattern, the right-hand side of a list of unparse items enclosed by square brackets. Some more common unparse items are strings, pattern variables, attributes, and blocks of arbitrary C++ code enclosed in braces.

Unparsing starts by calling the unparse-method of a term, usually the root term, and when a rule matches a term the specified items are ‘printed’. Only string items are really delivered to the current printer. This printer has to be defined by the user, and it usually writes to the standard output or into a file. Variable items and attribute items are further unparsed, code fragments are executed. If no pattern matches then the default rule is used, which exists for every phylum operator and which simply unparses the subterms.

We could do quite a lot of different things with the information saved in the tree. It just depends on the rules we use. For example we choose to print the input term in infix notation, because it is better readable to humans.

  Plus( a, b ) -> [infix: "(" a "+" b ")" ];
      

For every Plus term this rule prints an opening parenthesis, unparses the first subterm, prints a plus sign, unparses the second subterm, and then prints the closing parenthesis. The other operators are handled by similar rules.

We also may want to eventually compute the result of expressions. This can be achieved with rules like this.

  c = Plus( a, b ) -> [: a b { c -> result = a -> result + b -> result; } ];
      

Here the subterms are unparsed and then an attribute of the term gets assigned the sum of the subterm results. This will work only if these do not contain Idents. The meaning of the colon will be explained in the section called “Views”.

The C++ code is enclosed by braces, but can itself contain braces in matching pairs. If a single brace is needed, as when mixing code and variable items, it has to be escaped with the dollar sign. Example Example 4.2, “Escaped Braces in Unparse Rule” shows an application. If the function yields true the first branch is taken, and b is unparsed before a.

  Plus( a, b ) -> [ : { if( smaller_than( a, b ) ) } ${
			  b "+" a $}
		      { else } ${
			  a "+" b $} ];
      

The whole process of rewriting and unparsing as well as parts of it can be executed under different views. Each rule contains a view list between the respective opening brace and the colon, and it is used only if the current view appears in the list. This allows to specify different rules for a pattern. If a term is visited twice under different views, different rules are applied. These rules can be merged into one by listing all right-hand sides after one left-hand side, separating them by a comma.

Example Example 4.3, “Views in Rewrite Rules” defines two rewrite views (simplify and canonify) and two rules, each of which will only be applied to a matching term if the current view is among the specified ones. The first rule replaces the quotient of the same two identifiers by the number 1, the second expresses the associativity of addition. Both change the tree.

  %rview simplify, canonify;

  Div( SimpleTerm( Ident( a ) ), SimpleTerm( Ident( a ) ) )
      -> < simplify: SimpleTerm( Number( mkinteger( 1 ) ) ) >;

  Plus( Plus( a, b ), c )
      -> < canonify: Plus( a, Plus( b, c ) ) >;
      

Example Example 4.4, “Views in Unparse Rules” defines two unparse views (infix and postfix) and two rules for the same pattern, the one of which is used which matches both the term and the current view. It is possible to force a variable item to be unparsed under a desired view by specifying it after the variable and an intermediate colon. Subterm b is further unparsed under the view check_zero instead of the view infix.

  %uview check_zero;

  Div( a, b ) -> [ infix : a "/" b : check_zero ];
	
      

  %uview infix, postfix;

  Plus( a, b ) -> [ infix   : a "+" b ],
		  [ postfix : a b "+" ];
      

A phylum definition consists of two sides. The left-hand side specifies the phylum name, the right-hand side, behind a colon, a set of alternative operators, which are separated by bars. An operator is followed by a matching pair of parentheses, which may enclose a list of phyla as arguments. A nullary operator has an empty list. Example Example 5.1, “Definition of a Phylum” presents a basic definition with operators of different arity. Before the semicolon closing the definition an attribute block may appear. The definition of a phylum follows the general form:

  phylum   := phylum_name ":" operator { "|" operator } [ attributes ] ";"
  operator := operator_name "(" [ phylum_name ] { " " phylum_name } ")"
      

For the names of phyla and operators, the same restrictions hold as for C++ identifiers. Multiple definitions of of a phylum with the same name are interpreted as additional alternative branches of the first definition.

There are some simple predefined phyla: integer, real, casestring, and nocasestring, representing integer values, real values, case sensitive strings, and case insensitive strings respectively. Terms of these are not created by calls of operators but of special generated functions: mkinteger(), mkreal(), mkcasestring() and mknocasestring().

The phylum abstract_phylum represents the direct base of all phyla. Adding properties, like attributes or methods, to it makes them available for all phyla. Other direct bases may be specified for a phylum by using the keyword %base. One of them has to be derived from abstract_phylum, not necessarily directly. Example Example 5.2, “Changing base of a phylum” makes phylum math_expression to be derived from a phylum expression and a user defined C++ class counter_class.

expression:
      Plus   ( expression expression )
    | Neg    ( expression )
    | Null   ( ) ;
      

  %base math_expression : expression, counter_class;

  %{ KC_TYPES_HEADER /* code redirection */
    class counter_class {
      ...
    };
  %}
      

A list phylum can be defined by using the basic form of phylum definitions in a (right-) recursive way. The nullary operator constructs a list which is empty, and the binary, a list which is concatenated of a single list element and a list. The other variant uses the predefined operator list after which is specified the phylum of the list elements. The latter notation is to prefer because it is concise and causes the generation of additional list functions. That includes two operators which are named according to the scheme which is used in the right-recursive definition (prefixes Nil and Const). Other names could be chosen as well but this may cause some confusion. With either variants, a term is created by calling one of the two operators. The two definitions in example Example 5.3, “Alternative Definitions of one List” yield the same list of elements of a phylum expression.

  expression_list:
      Nilexpression_list  ( )
    | Consexpression_list ( expression expression_list )
    ;

  expression_list: list expression;
      

A phylum definition may have an attribute part attached which is enclosed in braces. It contains declarations of attributes of phylum types or other C++ types and optionally their initial value assignment. After that arbitrary C++ code can follow again enclosed in braces. This is the general form of the attribute part:

  attributes := "{" {attr_type " " attr_name [ "=" init_value ] ";"} [ cpp_part ] "}"
  cpp_part   := "{" arbitrary_cpp_code "}"
      

In particular, the initialization of attributes can be done in the C++ part too; though technically then it is not initialization, but assignment. Attributes may also be defined outside the phylum definition according to the general form beneath.

  attributes := "%attr " attr_type phylum_name "::" attr_name ";"
  members := "%member " attr_type phylum_name "::" attr_name ";"
      

Only attributes of phylum types can be defined with %attr. This is because they are considered part of the enclosing phylum by Kimwitu++. When a term is written to a file using the CSGIO functions (see the section called “CSGIO Functions”), its attributes are saved and can thus be restored.

Using the keyword %member instead allows also C++ types to be used. The values of attributes defined in this way will get lost when their term is written to a file. Restoring a saved term will assign the initial values to all %member attributes.

The C++ code is executed after the term creation and the attribute initializations. Inside that code the newly created term can be referred to as $0. Attributes are accessed via the operator ->. Each predefined phylum has an attribute which holds its value, which is value for integer and real, and name for casestring and nocasestring. Example Example 5.4, “Alternative Definitions of one Attribute” shows three alternative ways to define and initialize one attribute (of C++ type).

  expression: Div ( expression expression )
    { bool is_valid = true; };

  expression: Div ( expression expression )
    { bool is_valid; 
      { $0 -> is_valid = true; } };

  expression: Div ( expression expression );
  %member bool expression::is_valid = true;
      

It is possible to supplement the classes which will be generated from phylum definitions with additional methods. These are defined as usual but have as qualifier the name of either a phylum or of an operator. Such a method is known for all terms of the phylum or only for those constructed by the specified operator. Predefined phyla can get additional methods too.

  bool aritherm::equals( aritherm a ) {...}

  int Number::get_int( ) {...}

  nocasestring casestring::convert_to_nocase( ) {...}
      

It may appear desirable to initialize attributes of a phylum with non-default values immediately at term creation. This can be realized by using the Kimwitu++ keyword %ctor to define own constructors which will replace the default ones. Additional constructors are possible for phyla as well as for operators, but not for predefined phyla.

If these constructors are defined to have arguments then of some points are to take note. First, when used with operators the arguments will be added to those in the operator definition. Second, since the default constructors are replaced but relied on by some internal mechanism, the user has to define new ones or alternatively just provide default values for all new arguments. The latter may cause performance loss in the case of many or non-simple arguments.

The keyword %dtor allows own destructor definitions for freeing memory of attributes or something similar. It is applicable to phyla and operators but not to predefined phyla.

  %ctor simpleterm( int i ) {...}
  %ctor simpleterm( ) {...}

  %ctor Minus( bool neg = true ) {...}
  // Minus now has 3 arguments, but the third is optional
  
  %dtor virtual term( ) {...}
      

For every phylum a C++ class is generated, with one create-method for every operator. A term is created by calling the appropriate method, which returns a pointer to the object representing the term. As a default for every such object a new cell is allocated in memory. But the user may influence the memory management for optimization purposes. At phylum definition time the phylum can be declared to use a special storage class. There is one predefined storage class: uniq. It is allowed to specify !uniq what is the same as specifying nothing and results in usage of the default storage. Subphyla of a phylum with storage class can not use the default storage, but must be defined with a storage class too. The completed general form of a phylum definition is the following one.

  phylum := phylum_name [ "{" storage_class "}" ] ":" operator 
	    { "|" operator } [ attributes ] ";"
      

  aritherm    {!uniq} : Plus	( aritherm aritherm );

  simpleterm  {uniq}  : Number	( integer );
      

The first phylum in example Example 5.7, “Phylum with Storage Class” declares explicitly to use the default storage. All other phyla defined until now got that implicitly. Memory of such terms can be freed individually, terms of the second phylum can not. They are kept under uniq storage. What does this mean? Each storage class has a hashtable assigned. All terms of phyla with that class are stored there. If a term is to be created the create routine does conditionally allocate new storage. It checks first whether there is already stored an object created with the same arguments. If found true, the routine will return a pointer to that object in memory. Such every term is created only once. All predefined phyla, such as integer, are declared uniq. So the example has the effect that if two simpleterms are created from the same int value they will both point to the same memory cell.

It is possible to define additional storage classes, which each get their own table. Tables also can be explicitly created and assigned to storage classes, as well as cleared or freed (see the section called “Hashtable Functions”). Example Example 5.8, “Storage Class Definition and Application” declares two additional storage classes and defines two phyla using them.

  %storageclass table1 table2;

  intermediate {table1}: Div	( aritherm aritherm );

  final	       {table2}: Ident  ( casestring );
      

Patterns make it easier to select terms and subterms and to distinguish cases. They appear in rules for rewriting and unparsing and in with- and foreach-statements. Here there are explained common features while the slight differences will be mentioned in the appropriate place.

The term ‘pattern’ can be defined through induction. Each of the following is a pattern in the context of Kimwitu++:

Additionally some restrictions hold regarding the use of patterns. The patterns of item 1 are not allowed as the outermost pattern, while these of item 4 are allowed only as the outermost pattern. The assignment of an asterisk to a variable can be abbreviated by stating only the variable.

If more than one pattern matches a term, the most specific pattern is chosen. If there is no most specific one, the first of the matches is chosen. The matched term can be accessed as $0, its first subterm as $1, the second as $2 etc. (not in rewrite rules). Table Table 6.1, “Pattern groups increasingly specific” lists pattern examples, which are in each group equally specific. Kimwitu++ is not yet able to decide between more complex patterns (maybe partly overlapping each other) which to be most specific, but chooses the first found.

Kimwitu++ provides two control structures which help dealing with terms: the with-statement and the foreach-statement. They appear in different variants, fitting slightly different purposes.

  simpleterm a;
  ...
  with( a ){
    Ident( * )	    : { $0 -> computable = false; }
    c=Number( a )   : { c -> computable = true; c -> result = a -> value; }
    default	    : { // never reached, because simpleterm has only
			// the above two kinds
		      }
  }
	  
	

  bool is_arithmetic_term( aritherm $a ) {
    Plus, Minus, Mul, Div:    { return true; }
    default:	              { return false; }
  }
	  
	

  int count = 0;
  foreach( a; arithermlist A ) {
    if( is_arithmetic_term( a ) ) count++;
  }
	  
	

  int num_plus = 0;
  int num_minus = 0;
  foreach( $a; arithermlist A ) {
    Plus:   { num_plus++; }
    Minus:  { num_minus++; }
  }
	  
	

  int num_plus = 0;
  foreach( Plus( *, * ); arithermlist A ) {
    num_plus++;
  }
	  
	

  simpleterm a, b;
  ...
  with ( a, b ) {
    Number & Number:              { std::cout << "numbers"       <<  std::endl; }
    Ident & Ident:                { std::cout << "identifiers"   <<  std::endl; }
    Number & (Number, Ident):     { std::cout << "first num"	 <<  std::endl; }
    default:                      { std::cout << "first ident"   <<  std::endl; }
  }
	  
	

  foreach( $a & $b; arithermlist A, arithermlist B ) {
    default: { /* do nothing */ }
  }
  // at least one list ran out of elements
  afterforeach( $a & $b ) {
    Consarithermlist & Nilarithermlist: { return true; 
				    /* A has elements, B doesn't */ }
    default: { return false; }
  }
	  
	

The process of rewriting transforms a term tree. The left-hand side of each rewrite rule is a pattern specifying which term to substitute. The right-hand side denotes the term to substitute by, which has to be of the same phylum as the original one. This is done by calls of operators and term returning functions. Variables from the left-hand side may be used. Example Example 6.8, “Rewriting” simplifies terms by replacing every sum of numbers by its evaluated result. A helper function is necessary since it is not possible directly to use C++ operators in a rewrite rule (except method calls, see the section called “Restrictions on C++ in Kimwitu++”).

  Plus( SimpleTerm( Number( a ) ), SimpleTerm( Number( b ) ) ) ->
    <: SimpleTerm( Number( plus( a, b ) ) ) >;
    
  %{ KC_REWRITE /* code redirection */
  integer plus( integer a, integer b ){
      return mkinteger( a -> value + b -> value );
    }
  %}
      

To allow rewriting to end, each rule has to replace the term in question by one which is really simpler, reduced, or closer to a normal form. Since rewriting searches depth first, the subterms are usually already the result of a transformation. Calling the rewrite method of the root term starts the transforming process for the tree. Choosing an arbitrary term instead rewrites the subtree beneath.

The process of unparsing traverses a term tree and executes the instructions for every term matching a pattern as specified in the unparse rules. The left-hand side of a rule denotes a term pattern, the right-hand side a list of unparse items which are evaluated for matching terms. The various items allowed are listed below and appear all in example Example 6.9, “Unparse Items”, which is completely nonsensically.

  Mul( a, b ) ->  [:  "zero"
		      a
		      b->result
		      { if (a->value == 0) } ${
			  a:infix
			$}
		      %uviewvar prefix p1;
		      a:p1
		];
      

For every operator, there is a default pattern which matches if no other pattern does. Its associated rule unparses all subterms. The unparse-method generated for every phylum can also be called explicitly. It has 3 arguments: the term to be unparsed, a printer and an unparse view. The names kc_printer and kc_current_view respectively refer to the printer and the view which are currently in use.

  void printer( const char* the_string, uview the_view ) { ... };
	

  %{ HEADER /* redirection since no class definitions allowed in .k */
  class example_printer : public printer_functor_class {
    public:
      void operator( ) ( const char* the_string, uview the_view ) { ... };
  }
  %}
	

  %language CPP, JAVA;

  ClassDefinition( name, base_name, class_body ) ->
    [:	<JAVA>: "public " "class " name
	<JAVA>: " extends " <CPP>: " : "
	base_name " {\n" class_body "}"
	<CPP>: ";"
	"\n"
    ];
	  
	

Rewriting and unparsing of each term is done under a certain view. The view serves as a means to further differentiate between rules when choosing one to apply. To be a match a rule must have the current view to appear in its view list, which is the left part of the right-hand side between the bracket and the colon. If no rule matches the rules with empty list are considered. Below is shown the general form of rules with views.

  rewrite_rule   := pattern "->"  "<" rview_list ":" {operator|function}  ">;"
  unparse_rule   := pattern "->"  "[" uview_list ":" unparse_items          "];"
      

Views are declared by enumerating them after the keyword %rview and %uview for rewriting and unparsing respectively, separated by a space or a comma. These declarations enable Kimwitu++ to check for view consistency, although it is possible to leave them out entirely. But that should be avoided, because then even simple misspellings in a view list cause the implicit introduction of new views. One view is predefined for rewriting and unparsing respectively, base_rview and base_uview, which is implicitly included in the empty view list.

The view can be changed for a term by calling its rewrite/unparse-method with a new view argument. In unparse rules there the same can also be achieved by appending a colon and a new view name to a variable unparse item. Thus a whole subtree can be rewritten/unparsed under a different view, or even multiple times under changing views. Changing views allows to interlock several tasks on a certain subtree.

  %rview demo1 ;

  Plus( a, SimpleTerm( Number( 0 ) ) ) -> <: a -> rewrite( demo1 ) >;

  %uview demo2 ;

  Plus( a, b ) -> [: a:demo2 { b->unparse( kc_printer, demo2 ); } ];
  // both subterms of Plus are further unparsed under view demo2;
      

Every view introduced by the user actually causes the generation of a view class and one view variable of the same name. Since the user cannot distinguish them, the generalizing term ‘view’ is used. For unparse views that may matter since the user can define his own unparse view classes. These are declared by enclosing the view name in parentheses. The user has to provide a class view_class derived from a generated class view_baseclass. In particular, that class may contain member variables to hold information persistent over several rules. The base class provides an equality operator (==) deciding whether two view variables are of the same class and a name-method returning the name of the view.

No global view variable of the same name is generated for a user defined unparse view class. Variables of such a view are instantiated inside of unparse rules by %uviewvar and may bear the same name as their class. They can be used like the implicitly created view variables, but additionally provide all features of their class. Example Example 6.11, “User defined Unparse View Class” shows the definition of an unparse view class and demonstrates its usage.

  %uview ( number_count ) ;

  %{ KC_UNPARSE /* code redirection to where it is needed */
  class number_count_class : public number_count_baseclass {
    public:
      number_count_class() : counter( 0 ) { };
      int counter;
  };
  %}

  c=Plus, c=Minus, c=Mul, c=Div, c=SimpleTerm  ->  [:
	%uviewvar number_count nc;    // instantiate view variable
	c:nc			      // and unparse c with it
	{ std::cout << "Numbers counted: " << nc.counter << std::endl; }
  ];
  Plus( a, b ), Minus( a, b ), Mul( a, b ), Div( a, b )
		    -> [ number_count: a b ];
  SimpleTerm( a )   -> [ number_count: a ];
  Number	    -> [ number_count: { kc_current_view.counter++; } ];
  Ident		    -> [ number_count: ];
      

View lists contain names of view classes, all other occurrences of views actually are view variables. The scope of an unparse view variable ends with its defining rule. Since its name is not known inside other rules there it can be accessed only by means of the name kc_current_view, which always refers to the view variable currently used.

There are many places in a .k-file where C++ code can be used. But for some of them, the Kimwitu++ processor allows only restricted use of C++ constructs. These places are listed in the following along with the restrictions they impose.

There is a way to get around the restrictions of the Kimwitu++ processor using macros. A macro is defined inside a code redirection, which the processor does not evaluate. Therefore it can be as complex as necessary, while the macro call inside the rewrite rule looks as simple as Kimwitu++ wishes. Example Example 6.8, “Rewriting” defines a function for addition, which can be avoided when using a macro as in example Example 6.12, “Macro Application in Rewriting”.

  Plus( SimpleTerm( Number( a ) ), SimpleTerm( Number( b ) ) ) ->
    <: SimpleTerm( Number( PLUS( a, b ) ) ) >;
    
  %{ KC_REWRITE /* code redirection */
  #define PLUS( a, b )	  mkinteger( ( a ) -> value + ( b ) -> value )
  %}
      

Some generated functions return terms of the phylum abstract_phylum which have to be cast to the actual phylum. The C++ cast operators may be used also for phylum conversion but Kimwitu++ provides phylum_cast, a cast operator for phyla, which is better to use.

The definition of phyla and operators result in generated C++ classes. But these should be of no further interest for the user since the phylum names can be used in C++ code as if being pointer types of these classes, the operators as if being C++ constructors. Every phylum has a const counterpart of the same name prefixed by c_, which is the only means to get a const phylum variable.

Just for the sake of completeness, be it mentioned that every phylum corresponds to a class impl_phylum and every operator to a subclass impl_phylum_operator. All the classes are derived from a common base class which can be referred to as abstract_phylum. By adding constructors, methods or attributes to it, all phyla will be changed in that way.

The interworking with Yacc/Bison requires a type YYSTYPE which will be generated by Kimwitu++ when the option yystype is specified (see the section called “Options”)

Kimwitu++ generates a number of functions which are available wherever C++ code is allowed in .k-files. The table Table 7.1, “Generated Functions” lists all these functions and the sections which contain a more detailed description.

Common Functions

Since abstract_phylum has an unparse-method defined and all phyla are derived from abstract_phylum all phyla have it. The same is true for some other methods.

copy

  abstract_phylum copy( bool copy_attributes ) const;

The method copies this term completely, including its subterms. Since the result is always abstract_phylum it has to be casted to the phylum of this term. If true is specified as argument, the attributes are copied too. But beware! Merely the addresses are copied if the attributes are phyla or C++ pointers, that is, the new term references the attributes of the old one.

eq

  bool eq( c_abstract_phylum c_p ) const;

The method returns true if this term is structurally equal to the argument, that is, both terms have equal subtrees.

fprint

  void fprint( FILE* file );
	

The method prints a textual presentation of this term to the specified file. This simple example produces the output underneath.

  simpleterm a_number = SimpleTerm( mkinteger( 23 ) );
  a_number -> print( );

  SimpleTerm(
    Number(
      23
    )
  )
	

fprintdot

  void fprintdot( FILE *f,			  
		  const char *root_label_prefix,
		  const char *edge_label_prefix,
		  const char *edge_attributes,	  
		  bool print_node_labels,
		  bool use_context_when_sharing_leaves,
		  bool print_prologue_and_epilogue
		 ) const;
	  

This function creates a representation of the term in a format understood by the program dot, which is part of the graphics package graphviz and draws directed acyclic graphs in various output formats like PostScript or GIF. The target of the operation is the file f, while the other arguments control the details of the graphs appearence.

root_label_prefix

Adds a label to the graph denoting the root term. The label has the name of the phylum of that term prefixed by this string argument.

edge_label_prefix

Every edge in the graph is labelled with a number. This string argument appears as the prefix of these labels.

edge_attributes

For dot, the edges can have attributes which specify additional features like font name or edge colour (see dot manual for attribute names and values). This string argument is a list of attribute/value pairs (attribute=value), separated by commas.

print_node_labels

If this argument is set to true, the names of the subterms phyla appear in the graph. Otherwise they are suppressed and only the term names (operator names) are printed.

use_context_when_sharing_leaves

Terms which are shared in the tree usually appear only once in the graph (terms of uniq phyla). In particular, terms of predefined phyla are shared if they are equal. They are always leaves since they have no subphyla. If this argument is set to true, the leaves appear shared in the graph only if they are subterms of shared (uniq) terms.

print_prologue_and_epilogue

This argument is usually set to true since a certain prologue and epilogue are necessary to frame the graph. This is set to false if multiple graphs are to be grouped into one figure. In that case the prologue function has to be called explicitly, then some fprintdot calls follow, and finally the epilogue call finishes the figure creation.

The following call of fprintdot writes a a presentation of the term t to a file exa. From that file dot creates a graph like that in figure Figure 7.1, “Dot Created Graph of an Example Term”.

  aterm t = Plus( SimpleTerm( Number( mkinteger( 7 ) ) ),
		  SimpleTerm( Number( mkinteger( 7 ) ) ) );
  t -> fprintdot(exa, "root_", "edge", "style=dashed", true, false, true);
	

Figure 7.1. Dot Created Graph of an Example Term

fprintdotprologue

  void fprintdotprologue ( FILE *f );
	  

This function writes the prologue to f, which is needed to set up graphviz. Usually, when the figure contains only one graph, this function will be called implicitly by fprintdot; call this function when you set print_prologue_and_epilogue to false in the function call above.

fprintdotepilogue

  void fprintdotepilogue ( FILE *f );
	  

This function writes the epilogue to f, which is needed to finish the graph for graphviz. Usually, when the figure contains only one graph, this function will be called implicitly by fprintdot; call this function when you set print_prologue_and_epilogue to false in the function call above.

op_name

  const char* op_name( ) const;
	

This function returns the name of the phylum operator which has been used to create this term.

phylum_name

  const char* phylum_name( ) const;
	

This function returns the name of the phylum of this term.

print

  void print( );
	

This function prints a textual presentation of this term to the standard output. It is similar to the output of fprint.

set_subphylum

  void set_subphylum( int n, abstract_phylum p, bool=false );
	

This function replaces the nth subterm of this term by term p, which must be of a phylum castable to the phylum of the appropriate subterm. Numbering starts with 0.

subphylum

  abstract_phylum subphylum( int n, bool=false ) const;
	  

This function returns the nth subterm of this term. Numbering starts with 0.

unparse

  void unparse( printer_functor pf, uview uv);
  void unparse( printer_function opf, uview uv );
	

This function starts unparsing for this term. It is recursively called for every subterm. Unparsing is processed under the specified unparse view, and the strings to output are delivered to the printer functor or function respectively.

rewrite

  <actual phylum> rewrite( rview rv );
	      
	  

This functions starts rewriting for this term. It returns a new term of the actual phylum. Usually it is called at the root term whereupon the entire tree is searched under the specified view.

  void CSGIOwrite( FILE *f ) const;
	      
	  

  template<typename P> void
  CSGIOread( FILE *f, P &p )
	      
	  

  casestring mkcasestring( const char *str );
  casestring mkcasestring( const char *str, unsigned int length );
	  

  integer mkinteger( const INTEGER i );
	  

  nocasestring mknocasestring( const char *str );
  nocasestring mknocasestring( const char *str, unsigned int length );
	  

  real mkreal( const REAL r );
	  

  void free( bool recursive=true );
	  

  void freelist( );
	  

  hashtable_t  ht_create_simple ( int size );
	  

  hashtable_t  ht_assign ( hashtable_t ht, storageclass_t sc,
    bool still_unique=false );
	  

  hashtable_t  ht_assigned ( storageclass_t sc );
	  

  void	ht_clear ( hashtable_t ht );
	  

  void	ht_delete ( hashtable_t ht );
	  

  <phylum list> append( <phylum> p );
	  

  friend <phylum list> concat( c_<phylum list> l1, c_<phylum list> l2 );
	  

  <phylum list> filter( bool (*fp) (<phylum>) );
	  

  bool is_nil( ) const;
	  

  <phylum list> last( ) const;
	  

  int length( ) const;
	  

  <phylum list> map( <phylum> (*fp) (<phylum>) );
	  

  <phylum list> merge( <phylum list> l, <phylum> (*fp) (<phylum>, <phylum>) );
	  

  <phylum> reduce( <phylum> p, <phylum> (*fp) (<phylum>, <phylum>) );
	  

  <phylum list> reverse( ) const;
	  

The generated code is spread over several files. The table Table 7.2, “Generated files” lists these files and a description of their contents. Every file defines a macro symbol which can be used in preprocessor instructions and in code redirections. These symbols are listed as well. From every Kimwitu++ file a C++ file and a header file are generated. The name file in the table refers to such files.

  // this be a file example.k

  %{
  // everything between the brace lines will be copied to example.cc
  %}

  %{ HEADER KC_UNPARSE /* beware of //-comments here */
  // everything between the brace lines will be copied to example.h and unpk.cc
  %}
	

Kimwitu++ recognizes a number of command line options which affect the process of parsing and code generation, some rather drastically. Table Table 8.1, “Command line options” presents, in alphabetical order, all available options and their explanation. In most environments, two forms are provided, short and GNU style long options.

Suppose you do not need CSGIO input/output, but want to interface with your favourite compiler compiler, you might use:

Some vital options can be specified directly in Kimwitu++ using the keyword %option. Such specified options take higher priority than command line options and thus override them. Table Table 8.2, “Built-in options” lists them in alphabetical order. They behave like their command line counterparts. A line like this could be specified in a Kimwitu++ file:

  %option yystype smart-pointer
      

Interfacing with a compiler generator is useful when a tree should be build from some kind of input. Kimwitu++ provides the yystype-option (see the section called “Options”) which causes the generation of a header file needed by Yacc to cooperate. For every token found, the desired Kimwitu++ operator is called to create a term. If lex/flex is used too, Yacc has to be run with the option which causes the generation of an other header file needed by lex/flex (–d for Bison). Appropriate files for the example can be found in appendix Appendix A, Complete code of RPN example. The makefile uses implicit rules for flex and Bison.