13 TERMS
In the past the majority of programming languages were based on the initial idea of what the primary task of a computer is: numerical computations. However, some languages such as Lisp and Prolog showed that the computer also could be used for symbolic computations. Symbolic computations are used to manipulate symbolic information in a systematic way.
Symbolic information is playing an important role in several area's. Algebraic formulas, logic relations, and natural language phrases are all examples of symbolic expressions which can be processed.
In Elisa symbolic expressions are represented by terms. In this chapter we will study the concept of terms.
We start with the question what terms are and how they are represented in the computer. The following sections are related to the composition and the decomposition of terms. Some examples are given of the manipulation of symbolic expressions.
Let us assume that we want to write a program to manipulate algebraic expressions. One of the first things we need to know is how algebraic expressions are represented in the computer. In general, symbolic expressions are represented in Elisa as terms. Terms are the basic building blocks of symbolic expressions. Take the following example:
2 * x + a * f( -b, c, d * e)
In this example, 2, x, a, b, c, d, and e are terms, as well as 2 * x, -b, d * e, f( -b, c, d * e), and a * f( -b, c, d * e). The total expression is also a term.
More generally, a term may be one of the following elements:
* a value, such as 2, 4.5, 'a'
* a symbol, such as a, b, x, y
* a prefix operation term, such as -2, -b
* an infix operation term, such as a + b, 2 * x
* a function term, such as f( -b, c, d * e)
Terms representing values or symbols are called simple terms. Prefix operation terms, infix operations terms, and function terms are called compound terms. Simple terms do not contain other terms, compound terms are comprised of other terms.
A compound term consists of a functor and a number of arguments. For example, the compound term f( -b, c, d * e) consists of the functor f, and the arguments -b, c, and d * e. The arguments are again terms. The number of arguments of a compound term is called its arity. In our example, f(-b, c, d * e) has the arity of 3.
Terms of prefix and infix operations are also compound terms. The functor of an operation term is the operation symbol. For example, the functor of -b is the - symbol, the functor of 2 * x is the * symbol. The relationship with function terms may be more clear if we write 2 * x in a functional notation:
* ( 2, x)
Mark that this is not a legal Elisa expression!
The arity of a prefix operation term is always 1. An infix operation term has the arity of 2. The arity of a simple term is always zero.
As we saw, the notation for expressing terms is very general. Therefore, terms are not limited to algebraic expressions, but they can also be used to describe many other things. Some examples are:
- Formulas: a * b - c, H2O + CO2 + Na
- Relationships: likes (Mary, Bach), speaks (Peter, Spanish)
- Properties: male(Peter), female(Susan), human(Socrates).
- Structures: date (13, June, 1993), name ("John","Smith").
- Sentences: loves (man (John), woman (Kate)).
In the following some typical examples will be worked out.
Terms can be represented as trees. Trees are often drawn upside down; we will follow that convention. The example:
2 * x + a * f(-b,c,d * e)
may be represented as a tree (see Figure 13-1).
|
+
/ \
/ \
* *
/ \ / \
2 x a f
/ | \
- c *
| / \
b d e
Figure 13-1: A tree of terms
Trees are made of sub-trees. Trees and sub-trees are representing terms. A (sub-)tree consists of nodes and branches. Nodes are representing the functors of terms. Branches, representing arguments, are pointing to other nodes. The arity of a term determines the number of branches originating from that node. The initial node of a tree is called the root node.
A leaf node is a node without branches. A term represented by a leaf node is a simple term. Examples are: 2, x, a, b, c, d, f. All other nodes are representing compound terms.
As another example how trees can be used to represent terms we use the expression:
loves (man (John), woman (Kate))
which can be represented as a tree (see Figure 13-2).
| loves / \ man woman | | John Kate
Figure 13-2: A tree representation of terms
Exercises:
- 13.1 Represent the following symbolic expression as a tree:
father (uncle (John), mother (father (Peter)))
- 13.2 Represent the following symbolic expression as a tree:
parallel (road1, series (parallel (road2, road3), road4))
A tree is a perfect means to visualize the relationships between the different terms in a symbolic expression.
Terms are represented in the computer as data structures. There are specific data structures to represent integer values, real values, character values, boolean values, prefix operations, infix operations, and function calls. All these data structures are belonging to a collective data type term which is a predefined type in the language.
Terms can be created by using special language constructs in a program, as will be described in this section.
Let us start with a simple example of how terms can be created in a program. Suppose we want to use relationships such as "John likes Mary" and "Peter likes Ann". However, before we are able to do that, we first have to define the meaning of the likes relationship. That can be done in the following way:
likes (Person, Person) => term;
This so-called term-signature has the same format as the signature of a definition, with one exception, the => symbol. The => symbol, pronounced as 'is a', indicates that there are no definition rules associated with this signature and that a 'call' of this signature will result in the creation of a corresponding term.
If we assume that John and Mary are already known as names of Persons, we may now ask the system to evaluate the following expression:
likes (John, Mary)?
The system will assume that this is a call of a function definition. It tries to find the corresponding definition. However, it discovers that the corresponding signature indicates that there are no definition rules defined to transform the input values into output values. Therefore the system will make a compound function term representing the call:
likes (John, Mary)
The returned term is equivalent to the following tree (see Figure 13-3).
| likes / \ John Mary
Figure 13-3: A tree representation of likes (John, Mary).
The likes relation has an arity of 2. We can also define compound terms with other arities, such as:
mother (Person) => Person;father (Person) => Person;
Based on these term-signatures we may now ask the system to evaluate compound expressions such as:
likes (father (Ann), mother (Peter))?
Because all corresponding signatures are term-signatures the system will create the analogous terms:
likes (father (Ann), mother (Peter))
The resulting term may be interpreted as "the father of Ann likes the mother of Peter". It is equivalent to the following tree (see Figure 13-4).
| likes / \ father mother | | Ann Peter
Figure 13-4: A tree representation of likes (father (Ann), mother (Peter))
In the preceding examples, we assumed that John, Mary, Peter, and Ann were names of persons which could be used as terms. We may specify that in the following way:
type Person = term;
John => Person;
Mary => Person;
Peter => Person;
Ann => Person;
Because of the frequent occurrences of these kinds of term-signatures there is a short-hand notation for term names as illustrated by the following example:
John, Mary, Peter, Ann => Person;
With the preceding elements we are now able to show a complete session:
type Person = term; John, Mary, Peter, Ann => Person;mother (Person) => Person; father (Person) => Person;likes (Person, Person) => term;likes (father (Ann), mother (Peter))?
As we saw, the system will return with the compound term:
likes (father (Ann), mother (Peter))
In the previous examples we used the predefined term type or equivalent types for arguments and parameters. However, that is not always adequate. Sometimes we want to use different types as in the following example:
Date (Day = integer, Month = text, Year = integer) => term;
This term-signature can be used to record dates in the following way:
Date (19, "May", 1995)?
The system will return with the following compound term:
Date (19, "May", 1995)
This result can be represented by the following tree (see Figure 13-5).
| Date / | \ / | \ 20 "May" 1995
Figure 13-5: A tree representation of a Date
The arguments of a compound term, such as 20, "May", 1995, are also represented as terms. As a general rule, argument values of a term-signature call are represented by corresponding terms.
Term-signatures can also be used to specify terms which are representing prefix operations, infix operations, and functions. Examples are:
+ term => term; - term => term;term + term => term; integer + term => term; term * term => term; integer * term => term;f (term, term, term) => term;
If we assume that:
a, b, c, d, e, x => term;
then the evaluation of the following expression:
2 * x + a * f ( -b, c, d * e)
will create a tree of terms as represented by Figure 13-1.
There are a number of rules associated with term-signatures:
1. The parameters of a term-signature may be of any type - including the term type itself.
2. Because a term-signature always represents a single term, its result specification can only specify single term types. Other types and other quantifiers are not allowed.
3. The selection of term-signatures is the same as used for definitions: the function-name or operation-symbol, the argument types, and the number of arguments are used to select the proper definition or term-signature.
4. The evaluation of a function or operation call which refers to a term-signature, may result in the creation of a number of terms representing the arguments before a compound term representing the call is created. See, for example, Figure 13-1 and Figure 13-4.
5. Arguments are evaluated before they are used in a compound term. For example:
Date ( 3 * 9 - 7, "May", 1950 + 45)?
will deliver the same compound term as represented by Figure 13-5.
Exercises:
- 13.3 Make a program which creates a tree of terms representing:
father (uncle (John), mother (father (Peter)))
Compare the result with the tree of Exercise 13.1.
- 13.4 Make a program which creates a tree of terms representing:
parallel (road1, series (parallel (road2, road3), road4))
Compare the result with the tree of Exercise 13.2.
There is also another, more explicit way to create a term. If we want to convert a value of a given type into a term type we can use the term type, or its equivalent, in a so-called type conversion expression:
term: expression
For example, term:15 converts the integer value 15 into the term value 15.
In the preceding section we discussed how terms are composed. In this section we will study how terms can be decomposed. The decomposition of terms is based on pattern matching.
Pattern matching is used to select specific terms from a set of terms and to retrieve the arguments from those selected terms. It makes use of patterns which are characterizing the terms to be selected.
Let us give a simple example. In the previous section we assumed that John likes Mary and Peter likes Ann and we discussed how to create terms of such relations. We may expect that there are many more of those like-relations. To find out who likes who, we may write a definition in the following way:
f (term) -> optional (list (term));
f (likes ( X, Y)) = { X, Y};
The input of the function f is a term. If the term is a likes term, the arguments of the term, called X and Y, are returned in a list. We call likes (X, Y) a pattern.
In Section 3.4, "Definition Rules", it has been explained that parameters may not only be names, but also literals, and named values. In this section we learn that a parameter may also be a pattern.
We will use the term parameter-expression to denote all the possibilities at a given parameter position. Thus, a parameter expression is one of the followings:
* a parameter name
* a literal
* an expression (preceded by a prefix = sign)
* a pattern
A pattern describes a number of possible terms. That means that patterns may only be used for term parameters, or for parameter types which are declared to be equivalent to the term type.
A pattern consists of a given functor and a list of pattern expressions. A pattern-expression has the same syntax as a parameter expression. Consequently, a pattern expression may be a name, denoting a pattern variable, a literal, denoting a specific value, an expression value (preceded by a = sign), or another pattern.
The number of pattern expressions in a pattern specifies the arity of the pattern. For example, the pattern likes (X, Y) has the arity of 2. It describes all terms with the functor likes and the arity of 2.
Pattern variables are represented by simple names. For example, in the pattern likes (X, Y) are X and Y both pattern variables. In case of a successful match a pattern variable contains the value of the corresponding argument.
Suppose we have a list of men and women, such as:
People = { man(John), woman(Mary), woman(Ann), man(Peter) };
This is a list of terms. Let us now assume that we want to select all the names of the women in the list. We will use the following definition:
Female (term) -> optional (term); Female (woman (X)) = X;
This definition has as input a term. There is only one definition rule given. It has one parameter-expression which is a pattern. In this example, woman(X) is the pattern. Its functor is woman, its arity is one, and the pattern expression is the pattern variable X.
If the functor of an input term is woman and its arity is one, then we are talking about a successful match. In that case the value of the argument will be assigned to the pattern variable X. The right hand side of the definition rule may now use the value of X. In this case, the value of X is simply returned to the caller.
If, in our example, the functor of an input term is man (or any other functor unlike woman) then there is no successful match of the input term against the pattern. In that case the definition does not apply. So, no value can be returned. That is the reason we used the optional quantifier in the result specification. In general, if in a definition, not all input terms may be matched, the optional or multi quantifier should be specified.
Our example definition can now be used in the following way:
Female (items (People))?
The system returns with the stream:
Mary Ann
Pattern constants are literals or named values. Named values are prefixed by a = sign. A pattern constant specifies that the corresponding argument must have the same value for a successful match.
The following example illustrates the use of pattern constants. Suppose we have list of mothers, as in:
Mothers = { mother (Ann, Mary),
mother (Kate, Alice),
mother (Ann, Susan),
mother (Ann, John) };
In this list of terms is Ann the mother of Mary, and so on.
We would like to know all the sons and daughters of Ann. We will use the following definition:
Children (term) -> optional (term); Children (mother (= Ann, X)) = X;
The pattern in this definition, mother (=Ann, X), has two pattern expressions. The first is a constant, the second a variable. The constant specifies that for a successful match the first argument of the input term must be the symbol Ann. If that is the case then the second argument of that term will be assigned to the variable X. All other actions are similar to the actions of the previous definition of Female.
This definition can now be used in the following way:
Children (items (Mothers) )?
The system will return the stream:
Mary Susan John
However, the problem with this version of Children is that it is restricted to the sons and daughters of Ann. We may generalize Children in the following way:
Children (Mother = term, Relation = term) -> optional (term); Children (X, mother( X, Y)) = Y;
This definition has two input terms, one for the name of the mother and the other for the mother relationship. The pattern used for the second parameter has a pattern variable which name is the same as used for the first parameter. This means that the two values must be equal. In general, equal names of variables in parameter expressions require equal argument values for a successful match.
This definition can now be used in the following way:
Children (Ann, items (Mothers))?
The system will return the same set of answers as with the previous questions:
Mary Susan John
Patterns may contain other patterns. A pattern-expression in a pattern may be another pattern, which means that for a successful match the corresponding argument must be in accordance with this nested pattern.
Suppose we have list of mothers, together with their sons and daughters as indicated:
mothers = { mother (Ann, female (Mary) ),
mother (Kate, female (Alice) ),
mother (Ann, female (Susan) ),
mother (Ann, male (John) ) };
This is a list of terms where Ann is the mother of a female person called Mary, and so on. We now like to know all the daughters of a mother. We will use the following definition:
Daughter (Mother = term, Relation = term) -> optional (term); Daughter (X, mother (X, female (Y)) ) = Y;
The pattern mother (X, female (Y)) is a nested pattern.
This definition can now be used in the following way:
Daughter (Ann, items (mothers))?
The system will return the stream:
Mary Susan
13.4.4 Patterns of Prefix and Infix Operations
Patterns of prefix and infix operations can also be used to match corresponding terms. Suppose we have the following list of expressions:
Expr = { a + b, + c - d, e * f + g, 2 * k + 5 * q };
We want to select only the infix + operations to form corresponding plus terms. We use the following definitions:
sum (term, term) => term;plus (term) -> optional (term); plus (X + Y ) = sum (X, Y);
The pattern in the plus definition is X + Y.
This definition can now be used in the following way:
plus (items (Expr))?
The system will return the stream:
sum (a, b) sum (e * f, g) sum (2 * k, 5 * q)
Exercise:
- 13.5 Make a definition which transforms X + X into 2 * X.
13.4.5 Patterns of Special Operations
Patterns of operations used in special operations can also be used to match corresponding terms. Suppose we have the following list of conditionals:
Cond = { if a then b * c, if d < e then p else q , f + g when r < s };
Let us assume that we want to form a list of the expressions in a conditional. Because conditionals are not unary or binary operations we will use a built-in function, called phrase, to indicate that its argument should be treated as a term which can be used for pattern matching. We illustrate its use in the following definitions:
Conditional (term) -> optional (list (term));
Conditional ( phrase(if X then Y) ) = { X, Y };
Conditional ( phrase(if X then Y else Z) ) = { X, Y, Z };
Conditional ( phrase(X when Y) ) = { Y, X };
This definition can now be used in the following way:
Conditional (items (Cond))?
The system will return the stream:
{ a, b * c }
{ d < e, p, q }
{ r < s, f + g }
13.4.6 Relations between Patterns
Relations between patterns are used to describe certain combinations of arguments. Suppose we want to describe relations between persons. Let us assume that we like to formulate the biblical father relations as described in Genesis 4:
type Person = term; type relation = term;Adam, Abel, Cain, Enoch, Irad => Person;father (Person, Person) => relation;FatherList = { father (Adam, Abel), father (Adam, Cain), father (Cain, Enoch), father (Enoch, Irad) };
At the first two lines the notion of Person and relation are introduced. The persons involved are given at the third line. The fourth line gives a signature of the father relation and the actual relations are collected in the FatherList as terms. In this example, we use the convention that father (Adam, Abel) means Adam is-the-father-of Abel.
Let us assume that we want to obtain only the names of the sons of Adam. We will therefore introduce the following definition:
AdamSons (relation) -> optional (Person); AdamSons (father (=Adam, X)) = X;
This definition will test if the first term of a father relation is the name of Adam; if so, the second term, being the name of the son will be returned. After the query:
AdamSons (items (FatherList))?
the following answers will be returned:
Abel Cain
The problem with this solution is that it is restricted to the sons of Adam. It is the same problem as we discussed with the daughters of Ann. We would prefer a more general solution where we could ask types of questions like: Give me the names of all the sons of a given father. We will split that question into two parts. The first part is: Give me for a given person and a given relation the name of the son if the person and the father in the relation matches. The second part is: Give me for a given person all the names of the sons in the FatherList:
son (Person, relation) -> optional (Person); son (P, father (P, X)) = X;sons (Person) -> multi (Person); sons (P) = son (P, items (FatherList));
If we are now asking for the sons of Adam with:
sons (Adam)?
we will also obtain:
Abel Cain
However, with these definitions we can also ask for the sons of Abel, Cain, and so on.
Suppose we want to ask questions about more complicated relationships, such as: Who was the grandfather of Enoch? To answer that type of questions we have to define what a grandfather is and what the relationship between a father and a grandfather is. Therefore we will define for relations a binary and operation which can be applied to any pair of relations:
grandfather (Person, Person) => relation;relation & relation -> optional (relation); father (X, Y) & father (Y, Z) = grandfather (X, Z);
The definition rule at the last line states: if X is the father of Y and Y is the father of Z then X is the grandfather of Z. Note, that the binary operation & we used earlier for boolean values can also be used for other types, provided its meaning is defined, as is done here.
Now we are able to generate a list of grandfathers, based on our FatherList:
GrandfatherList = { items (FatherList) & items (FatherList) };
In this definition each father relation in the FatherList is compared with all other father relations to see if the grandfather relation holds. If we now ask for all the items of the GrandfatherList with:
items (GrandfatherList)?
the following answers are given:
grandfather (Adam, Enoch) grandfather (Cain, Irad)
13.4.7 Patterns for Type Matching
Because simple terms may represent values of different types, such as integer values, real values, and so on, it is sometimes necessary to match for arguments of certain types. Such a type match has the following form:
type-expression : pattern-variable
The type-expression specifies the required type of the corresponding argument. With a successful match the argument will be assigned to the pattern variable. The pattern variable will be of the type specified by the type-expression.
To illustrate type matching we assume that we have the following list of term values:
Values = { term:23, 3.4, 45, -23, ... };
Suppose we want to quadruple all the values in the list. We will use the following definition:
quadruple (term) -> optional (term); quadruple (integer: I) = term: (4 * I); quadruple (real: R) = term: (4.0 * R);
This definition has two definition rules. The first rule tests if the term represents an integer value. If that is the case the integer value will be multiplied by 4. The resulting value will be converted to a term and returned. The second rule does the same for real values.
Another example of type matching is demonstrated in the following example. Suppose we have the following list of terms which may be interpreted as 'instructions':
Instructions = { square (12),
double (23.5),
triple (34),
square (3.4), ...};
We may now define the interpretation of these instructions in the following way:
Interpret (term) -> optional (real); Interpret (double (integer: I)) = real (I + I); Interpret (triple (integer: I)) = real (3 * I); Interpret (square (integer: I)) = real (I * I); Interpret (double (real: R)) = R + R; Interpret (triple (real: R)) = 3.0 * R; Interpret (square (real: R)) = R * R;
In contrast to the previous example, all the results will be real numbers instead of terms. We may now use our simple interpreter in the following way:
Interpret (items (Instructions))?
The system will respond with the stream:
144.0 47.0 102.0 11.56
Although, until now, the terms used in our examples are very simple, in practical situations terms can be quite complex. Because a lot of symbolic information can be stored in term trees there is often a need to analyze and decompose the terms in a tree and to manipulate the corresponding sub-trees in an easy way.
There are two features in the language which are very helpful in this way: that are pattern matching and recursion.
Recursion is a natural tool for dealing with tree structures, because we can often reduce operations on trees to operations on their sub-trees, which reduce in turn to operations on the sub-trees of the sub-trees, and so on, until we reach the leaves of the tree. So, recursion gives us the possibility of climbing trees up and down in a natural way.
Pattern matching combined with recursion provides us with a powerful combination for defining operations on term trees.
To illustrate operations on term trees we will use two examples: one based on symbolic differentiation of algebraic formulas, the other designated for the simplification of those formulas.
Before we are going to discuss that in detail we will first introduce algebraic formulas as examples of symbolic expressions. As we saw earlier symbolic expressions are based on terms. Therefore we are defining a component for Formulas ( see Figure 13-6).
component Formulas; type formula = term; + formula => formula; - formula => formula; formula + formula => formula; formula + integer => formula; integer + formula => formula; formula - formula => formula; formula - integer => formula; integer - formula => formula; formula * formula => formula; formula * integer => formula; integer * formula => formula; formula / formula => formula; formula / integer => formula; integer / formula => formula; formula ** formula => formula; formula ** integer => formula; integer ** formula => formula; abs (formula) => formula; sqrt (formula) => formula; sin (formula) => formula; cos (formula) => formula; ln (formula) => formula; exp (formula) => formula; begin<< empty implementation section >>end component Formulas;
Figure 13-6: A component for algebraic formulas
The component introduces in the interface-section the type formula, and the term-signatures of the usual infix and prefix operations and some functions. The implementation-section of the component is empty. All operations used in formulas are represented by corresponding terms.We are now able to use formulas in our applications. Let us use the following example:
a, b, c, x => formula;
y = a * x ** 2 + b * x + c;
The execution of the definition of y results in the symbolic expression a * x ** 2 + b * x + c, which is assigned to y. The expression is evaluated according to the operator precedence rules as ((a * (x ** 2)) + (b * x)) + c and each sub-expression is represented by a term. The whole expression is represented by a tree of terms which has the following form (see Figure 13-7).
x 2
\ /
a ** b x
\ / \/
* *
\ /
\ /
+ c
\ /
\ /
+
|
Figure 13-7: Tree of formula a * x ** 2 + b * x + c
Notice that we have not used the convention of drawing trees upside down. A more natural view may help to visualize tree climbing as discussed in the following.
13.5.1 Example: Symbolic Differentiation
In mathematics, symbolic differentiation is a procedure that converts an algebraic expression into another algebraic expression which is called the derivative. This procedure can be written in Elisa as a definition which has as input an algebraic expression and a variable, and as output the derivative of the expression with respect to the variable. The definition makes heavily use of pattern matching and recursion. Figure 13-8 shows a component which is dedicated to symbolic differentiation.
component Differentiation; diff (formula, formula) -> formula; begin diff (x, x) = formula: 1; diff (u + v, x) = diff (u, x) + diff (v, x); diff (u - v, x) = diff (u, x) - diff (v, x); diff (u * v, x) = diff (u, x) * v + u * diff (v, x); diff (u / v, x) = diff (u, x) / v - u * diff (v, x) / v ** 2; diff (y ** integer:n, x) = n * y ** ( n - 1) * diff (y, x); diff (sin (y), x) = cos (y) * diff (y, x); diff (cos (y), x) = -sin (y) * diff (y, x); diff (ln (y), x) = 1 / y * diff (y, x); diff (others, x) = formula: 0; end component Differentiation;
Figure 13-8: Symbolic Differentiation Component
Notice that there is only one signature for the differentiation operation but that there are many definition rules: for each possible operation or function symbol in the formula a rule has been given. So each rule represents a particular case. If the differentiation operation is applied to a formula, then the patterns in the parameter-expressions of the first rule will be compared with the input formulas. If they match then the expression of the right-hand side of the rule will be evaluated. If they do not match, the patterns of the next rule will be taken for comparison. This process will continue until the patterns of a rule are matching or until the last rule of the definition has been met. In our example, the last rule represents the most general case. It will always be applied if no preceding ones do.
Suppose we want to differentiate y as given by the previous example. Then we start with the following situation:
diff (y, x)
Substitution of the value of y gives us:
diff (a * x ** 2 + b * x + c, x)
Now we start with tree climbing! We always start at the root node. Because the most right + operator is the root node at the bottom of the tree it will be used first for matching. We see that the second definition rule is matching with the + operator and we may now apply the right-hand part of the second definition rule which results into:
diff (a * x ** 2 + b * x, x) + diff (c, x)
By proceeding from left to right the left sub-expression can be further evaluated by applying again the second definition rule:
( diff (a * x ** 2, x) + diff (b * x, x) ) + diff (c, x)
So, we have climbed the tree of Figure 13-7 to the second + node.
The most left sub-expression can be further evaluated by applying the fourth definition rule dedicated to u * v patterns.
( (diff (a, x) * (x ** 2) + a * diff (x ** 2, x)) + diff (b * x, x)) + diff (c, x)
We have now climbed to the most left * node.
The most left sub-expression is further evaluated. Because there is no specific rule for a only the last and most general rule applies:
(((formula: 0) * (x ** 2) + a * diff (x ** 2, x)) + diff (b * x, x)) + diff (c, x)
We have reached the left-most (sub-) top! It took us a number of recursions before we reached leaf a.
Now we are climbing down. We are reaching the most left * node again and try to perform the multiplication. Because both operands are known and both are of the formula type, this is an irreducible sub-expression which will result in the term 0 * (x ** 2) and this is the first result of our differentiation exercise. The following steps are similar to the steps we discussed so far. It involves further tree climbing up and down.
Exercise:
- 13.6 Complete this differentiation process till the final answer has been found.
The final result of this exercise is:
0 * x ** 2 + a * (2 * x ** 1 * 1) + (0 * x + b * 1) + 0
As you see, all unnecessary parentheses have been removed. The remaining parentheses are reflecting the structure of the resulting tree.
As a final remark: The differentiation definition may be considered as a description of a procedure to derive from a symbolic expression another symbolic expression. But equally, it may also be seen as a procedure which transform a tree into another tree.
Exercises:
13.7 Draw the tree corresponding to the result of the differentiation exercise. Are there common parts of the input and the output trees?
13.8 Are the symbolic expressions (X * Y) * Z, X * (Y * Z), and X * Y * Z all equal? Hint: Draw the corresponding trees.
13.9 Write a definition which determines if two symbolic expressions are equal. Assume that these symbolic expressions only contains the infix operators +, -, *, and /.
13.5.2 Example: Symbolic Simplification
The result of the differentiation exercise might not be according to your expectations. You probably would have expected a much simpler formula as a result. And that is because of the simplifications we are making if we do the exercise ourselves. To bring our result in a simplified form we could have extended our differentiation definition with simplification features. But, because simplification is also required in many other situations we have separated simplification in a dedicated component as defined in Figure 13-9.
component Simplification; simplify (formula) -> formula; begin simplify (x + y) = reduce ( simplify (x) + simplify (y) ); simplify (x - y) = reduce ( simplify (x) - simplify (y) ); simplify (x * y) = reduce ( simplify (x) * simplify (y) ); simplify (x / y) = reduce ( simplify (x) / simplify (y) ); simplify (x ** y)= reduce ( simplify (x) ** simplify (y) ); simplify (x) = reduce (x);reduce (formula) -> formula; reduce ( 0 + x) = simplify (x); reduce ( x + 0) = simplify (x); reduce ( integer: x + integer: y) = formula: (x + y); reduce ( x - 0) = simplify (x); reduce ( 0 - x) = simplify (- x); reduce ( integer: x - integer: y) = formula: (x - y); reduce ( 0 * x) = formula: 0; reduce ( x * 0) = formula: 0; reduce ( 1 * x) = simplify (x); reduce ( x * 1) = simplify (x); reduce ( integer: x * integer: y) = formula: (x * y); reduce ( x / 1) = simplify (x); reduce ( 0 / x) = formula: 0; reduce ( integer: x / integer: y) = formula: (x / y); reduce ( x ** 1) = simplify (x); reduce ( x ** 0) = formula: 1; reduce ( integer: x ** integer: y) = formula: (x ** y); reduce (x) = x; end component Simplification;
Figure 13-9: Algebraic Simplification Component
The simplification procedure consists of two mutual recursive definitions, both based on pattern matching. This is because the simplification procedure creates many intermediate sub-trees which may be simplified further.
With this component it is possible to simplify algebraic expressions to some degree. This component will eliminate all redundant terms based on 0 and 1 and will lead to considerable size reduction. For example, simplification of the result of our previous differentiation example:
simplify (0 * x ** 2 + a * (2 * x ** 1 * 1) + (0 * x + b * 1) + 0)
will result in:
a * (2 * x) + b
which is considerably shorter.
Exercise:
13.10 Use tree climbing to verify the result.
13.11 Modify the simplification procedure such that a * (2 * x) is rewritten as 2 * a * x.
13.12 Modify the simplification procedure such that a + a is rewritten as 2 * a.
In the preceding examples we discussed how pattern matching and recursion can be used to construct quite complex procedures for symbol manipulations. We used tree climbing as an aid in visualizing the operations.
In previous sections we introduced symbols as symbolic representations of names or identifiers. Because symbols are often used in symbolic expressions there is sometimes a need to compare symbols. For example, it is customary to write in an algebraic expression b * a as a * b. If we want to achieve this by means of a simplification procedure we will need to compare the textual representations of symbols.
As a consequence, the following operations are defined on symbols which are all belonging to the predefined type symbol:
type symbol;
symbol == symbol -> boolean;
symbol <> symbol -> boolean;
symbol < symbol -> boolean;
symbol <= symbol -> boolean;
symbol > symbol -> boolean;
symbol >= symbol -> boolean;
text (symbol) -> text;
symbol (text) -> symbol;
The binary operations ==, <>, <, <=, >, >= are defined for symbol operands. They are used for comparison and they represent the familiar operations of equal to, not equal to, less than, less than or equal to, greater than, and greater than or equal to. The result is a boolean value. Comparing two symbol strings works in the same way as defined for text strings. For example, the result of the expression a < b where a and b are both symbols, will be true.
In addition to the comparison operations there are two other operations related to text conversion.
One is a conversion operation which converts a symbol into text. For example, evaluation of the expression text(a) will result in the text string "a".
The other operation does the opposite: it converts a text string into a symbol. For example, symbol("X") will result in the symbol X.
Symbolic names of type symbol may be introduced by name-signatures. For example:
H2O, CO2, H2SO4, HCl => symbol;
may be used as symbols of chemical components.
Symbolic names of any type are considered to be symbols which may be used in patterns of parameter expressions. For example, if we want to rearrange an algebraic formula in such a way that Y + X will become X + Y, we may do that in the following way:
use Formulas; X, Y, Z => formula;symbol + symbol => term;rearrange (term) -> term; rearrange ( symbol: u + symbol: v) = if u < v then u + v else v + u; rearrange ( others) = others;
We may now use this in the following dialogue:
rearrange (X + Y)? X + Yrearrange (Y + X)? X + Yrearrange (Y - X)? Y - X
13.7 Inspecting Compound Terms
There are three built-in definitions for inspecting compound terms and one definition for setting an argument. The signatures of these definitions are:
functor (term) -> symbol; arity (term) -> integer; argument (term, integer) -> term; set_argument (term, integer, term) -> nothing;
The functor function returns the functor of the input term. The input term must be a compound term. For example, functor (woman(Mary)) will be the symbol woman.
The arity function returns the arity of the input term. If the term is a simple term the arity is zero, otherwise it is the number of arguments of the term. Therefore, the arity function can be used to test if a term is a simple term or a compound term.
The argument (T, I) function returns the I th argument of the input term T. The value of I must be positive and may not exceed the arity of the term T. For example,
argument (loves (man (John), woman (Kate) ), 2 )
will return woman (Kate).
The set_argument (T, I, U) function assigns U to the I th argument of the input term T. The value of I must be positive and may not exceed the arity of the term T. For example,
set_argument (loves (man (John), woman (Kate)), 2, woman (Alice))
will change the first input term into:
loves (man (John), woman (Alice))
We will give another example of how these functions can be used. Suppose we want to design a procedure which will return all the leaves of a term tree, without knowing the structure and contents of the tree. This will be done by the following recursive definition:
Leaves (Tree = term) -> multi (term);
Leaves (Tree) = if arity (Tree) == 0 then Tree << is Leaf >>
else Leaves (argument (Tree, 1 .. arity(Tree) ) );
This definition is a recursive procedure which returns a stream of terms, being the leaves of the input tree.
The definition rule starts with testing if the arity of the input term is zero. If that is true the input term is a simple term which is returned. Otherwise, the Leaves procedure is recursively called for each argument of the input term.
- Terms are used to represent symbolic information. A term is a value, a symbol, a prefix operation term, an infix operation term, or a function term. Terms representing values or symbols are called simple terms. Prefix operation terms, infix operations terms, and function terms are called compound terms.
- Terms may be represented as trees. A (sub-)tree consists of nodes and branches. Nodes are representing the functors of terms. Branches, representing arguments, are pointing to other nodes. The arity of a term determines the number of branches originating from that node. A leaf node is a node without branches.
- Pattern matching is used to select specific terms from a set of terms. It makes use of patterns which are characterizing the terms to be selected. Patterns are part of parameter expressions. A parameter expression is one of the followings: a parameter name, a literal, an expression (preceded by a prefix = sign), or a pattern. A pattern may be a name, denoting a pattern variable, a literal, denoting a specific value, a named value, or another pattern. Patterns may be nested: they may contain other patterns.
- A successful match between an argument and a corresponding parameter-expression depends on the current value of the argument and on the structure of the parameter-expression:
- If the parameter-expression is a literal the corresponding argument should represent the same value.
- If the parameter-expression is a single name which has not occurred already in a parameter-expression of the same definition rule then any value of the argument will match.
- If the parameter-expression is a single name which has already occurred in a parameter-expression of the same definition rule then the current entity of the argument should be equal to the entity of the argument of the previous parameter.
- If the parameter-expression is an expression preceded by an unary = sign then that expression will be evaluated and the resulting entity - which must be a single entity - should be equal to the entity of the argument. Note: Because the = sign is used here as a unary operator which has the highest priority, parentheses should be used if operators with lower priorities are part of the expression.
- If the parameter-expression is a type-expression, followed by a colon, followed by a name then the corresponding argument should be of the type denoted by the type-expression.
- If the parameter-expression is an expression, representing a pattern, then the corresponding argument should represent a term. The match is successful if the term has the same pattern as the parameter-expression, according to the rules given above.
 |
Part 1: Language Description | Chapter 13: Terms |