This a preliminary document, meant as an introduction for the programmer to the concepts used in the framework. It discribes the paradigm, of the model, view, and icon components, and gives an overview of the modules involved. It is not (yet) a detailed description of the module interfaces. For the moment please refer to the example programs ExprBessel.Mod (a special expression extension) and ExprSubstituter.Mod (a evaluator command). Please feel free to discuss any particular question with me via e_mail.
The Model Component
The purpose of a framework for mathematical expressions is to represent expressions and make them accessible to client software like mathematical operators or evaluators. A service of this kind could be offered by an abstract data type. The structure of expressions is recursive - an expression may refer to an arbitrary number of subexpressions. Thus, expressions are represented as directed graphs: Each node represents an expression and the outgoing edges refer to the subexpressions.
The framework must allow for extension with new types of expressions. On the other hand, an expression of a new type might occur as a subexpression of any other expression. Thus, the abstract data type must be generic. It is realized as an abstract class. This class needs to define all the features that are common to all expressions. Every concrete expression will be an extension of it.
The main feature to be defined in the abstract class is the abstraction of the subexpression graph structure. We use immutable lists for that purpose. Every expression object is accompanied by a (possibly empty) list of references to other expressions. This list is accessible by clients, even without knowledge of the exact type of a node. This is important to allow for commands to operate on subexpressions of particular types, even if these subexpressions occur within an expression whose type is unknown.
Expression objects are immutable. This has the advantage that multiple references to the same expression can be implemented without copying or special bookkeeping. Further, expressions can be stored in a DAG (directed acyclic graph) rather than in a tree. But, if a subexpression within an expression is being changed (i.e. replaced), the entire expression has to be rebuilt to incorporate the change. Thus, a copy is generated, but only of the objects that actually change. For all other objects, references are included (see figure 1). This type of operation is anchored in the abstract class with the definition of a clone method.
Figure 1: The DAG representing
(white objects) and additional nodes resulting when changing sin to tan (grey objects).
As a consequence of this model the primitive for expression manipulation is the replacement of a subexpression. This has the advantage to assert the formal consistency of any expression at any time. For instance, for every fraction it is asserted that a numerator and a denominator exist.
Further features are defined by methods serving to compare expressions for equality, and for generation of a normalized form.
The View Component
When expressions are made visible in a two_dimensional form, the types of the individual expressions have a strong influence on the exact presentation. In contrast to the text model, where at least the overall structure is always a sequence of objects (characters), even the placement of the subexpressions of an expression depends on the concrete kind of expression. From this follows that it is impossible to design a generic view component completely independent of the concrete expression classes. As a consequence, a second abstract class has been introduced, extending the model class discussed above. The only extension is the ability to visualize.
The process of drawing an expression on a two_dimensional plane could be implemented by a recursive two phase protocol. In a first phase, for each node in the DAG the size of each subexpression needs to be determined, then the subexpressions can be positioned, and from this the size of the entire expression can be computed. In a second phase, the expressions can be drawn themselves.
For efficiency reasons, the information about subexpressions computed during the first phase has to be stored for re_use during the second phase. Re_computation on demand would result in an algorithm exponential - rather than linear - in the number of nodes.
Whereas the model component represents expressions and subexpressions as a DAG, for visualization a tree structure is more appropriate. The reason is mainly that the same expression might be represented differently, e.g. in different size. As a simple example, consider the expression
where the two instances of the symbol x are printed in different size, though they might be represented by a single node of the expression DAG. Further, the visualization component has been designed to handle even very large expressions as are frequently generated by computer algebra tools. Therefore, from a certain depth of structural hierarchy on subexpressions are visualized by three dots only. Again, this may cause the same subexpression occuring twice in an expression graph to be displayed differently.
To be able to deal with these requirements - for the model a DAG structure is preferred, while the viewing component needs a tree structure - an intermediate structure is introduced. It consists of a tree of boxes. In each box object the size of an expression and the position within its environmental expression is stored. For box objects a draw method is defined which can be used to actually display the respective expression. Drawing an expression thus means to call its method for production of the intermediate structure, i.e. a tree of boxes, and then calling the draw methods of these boxes.
The intermediate tree structure has a further application: It can be used to identify a point on the two_dimensional drawing plane with an expression. This is achieved by traversing the tree structure until the smallest box containing the point in question is reached. This is used to implement the selection mechanism for subexpressions in a generic way.
Figure 2 gives an overview over the classes involved in the kernel of the expression framework.
Figure 2: Classes of the expression framework's kernel (white: abstract classes; grey: concrete classes)
The Icon Component
The icon component establishes the link between the expression framework introduced so far, and the text framework. From the text framework's view, the icon component is simply an extension which can exist in parallel with other extensions and can cooperate with all kinds of tools designed for the text model (e.g. specialized editors or AsciiCoder).
From the perspective of the expression framework it is a specialized concrete view component. As such, it could be replaced e.g. by a separate individual expression editor, without affecting the rest of the framework. In fact, several such components could exist in parallel. As a concrete view component, the icon component implements concrete graphic ports, and the subselection feature. (See figure 3.)
Figure 3: The individual components and their tasks
As an implementation detail, it should be noted that the converter between text and internally represented expressions, i.e. the expression parser, is implemented in a separate module. This makes the icon component independent from the concrete syntax and semantics of the expression language in use. Also, the expression classes necessary to represent objects read by the parser need not to be known by the icon component. This leads to a clean separation between the general editing issues implemented in the framework and the expression class library. To abstract from text converters, the icon component defines an abstract class Converter. Figure 4 presents the complete set of classes involved in the resulting nested framework. Figure 5 shows the modules involved.
Figure 4: Classes of the Nested Framework (white: abstract classes; grey: concrete classes)
To allow clients of the framework to abstract from the representation of a parameter expression (text, single icon, mixture of both, or subselection) module ExprViews also implements a special mechanism to retrieve the least recent selected expression and to update it in place after some operation. The following simple version of the collapse command serves as an example for the usage of the selection objects:
PROCEDURE Collapse*;
VAR sel: ExprViews.Selection;
BEGIN
sel := ExprViews.LatestSelection(); (* get least recent selection (no matter whether text or subselection *)
IF (sel # NIL) & ~sel.promise THEN (* selection exists and selected expression might be changed *)
ExprStd.DoSubstitutions(sel.exp); (* do all registered standard substitutions *)
sel.notify(sel, sel) (* update selection to new value *)
END
END Collapse;
For a more detailed discussion of the concept of icons within text in general you may want to take a look at:
W. Weck: Putting Icons into (Con_) Text,
Proceedings of the Thirteenth International Conference on Technology of Object_Oriented Languages and Systems,
TOOLS EUROPE '94, Versailles, France, Prentice Hall, 1994.
(.txt)