Interactive Calculator

Purpose

To give you practice specifying tree computations:

Due dates

You must submit your solution via electronic mail by 9:00am on Tuesday, September 27. Your submission must be an attachment that is a zip file named ``firstName.lastName.zip''. (If you are submitting as a group, the file should be named by the person actually submitting it.) To ensure proper credit, please be certain that every one of the specification files contains the names of all of the members of the group. Place these names in C-style comments at the head of all Eli specification files except FunnelWeb files. Place them in the first block of text in a FunnelWeb file.

This assignment is worth 20 points.

Background

An arbitrary tree structure can be defined by a set of LIDO rules. Each rule defines a concrete class that represents a tree node. The left-hand side of that rule names an abstract class from which the concrete class inherits. The right-hand side of the rule defines the children of the tree node, stating the abstract class from which each child must inherit. Thus the following rule defines a concrete class Plus that inherits from an abstract class called Exp. Objects of class Plus have two children, each of which must be an object of a class inheriting from Exp:
RULE Plus: Exp ::= Exp '+' Exp END;
An object can have an arbitrary number of children. For example, here is a rule defining a concrete class whose name is uninteresting. It inherits from the abstract class Stmts, and has an arbitrary number of children. Each child must be a concrete class that inherits from Stmt, Iteration, or Block:
RULE: Stmts LISTOF Stmt | Iteration | Block END;

You have already seen how Eli can generate Java or C++ declarations for a set of tree node classes, and for an abstract visitor class, from files containing LIDO rules. You have implemented computations over trees defined in LIDO rules by writing concrete visitor classes that inherit from the generated abstract visitor class.

In order to write a concrete visitor class, you first have to decide upon the task that visitor must accomplish. Usually this means associating some interesting values with nodes, and postulating some relationship among those values. For example, if the task of the visitor is to evaluate the expression represented by a tree then each node represents a sub-expression and the value of that sub-expression could be associated with the node representing it. Clearly you can then postulate a relationship among those values in the case of the Plus node defined above: The value at the node is the sum of the values at its children.

The task of a concrete visitor is to establish the interesting values at each node, guaranteeing that the postulated relationships hold. It may also involve some side effect, such as printing out some of the interesting values. You have decided upon the task when you have decided upon the interesting values, the postulated relationships, and the side effects. Your work is finished at this point if you can capture your decisions in a LIDO file; Eli can use this information to generate the concrete visitor classes as well as the tree node classes and the abstract visitor class.

In the remainder of this section we shall present a general strategy for capturing decisions about tree computations, explain the role of entities with state independent of their position, and discuss the implicit dependence that these entities introduce.

Capturing decisions about tree computations

Here is a general strategy for capturing the specification of a tree computation in LIDO:
  1. Introduce attributes to represent the interesting values (e.g. an attribute named Value, of type int, to represent the value of an expression).
  2. Associate those attributes with either LIDO symbols (representing abstract classes) or LIDO rules (representing concrete classes) according to the meanings of the values they represent. You will find that most attributes are naturally associated with symbols (e.g. the Value attribute would be associated with the Expr symbol rather than the Plus rule because Value represents an interesting value for any expression).
  3. Consider each symbol associated with an attribute, and select a computation strategy to determine the value of that attribute according to the postulated relationships by using the following table:

    Computation patternStrategy
    Each lower context of the symbol requires a different computation of the information. Design an appropriate computation for each rule having the symbol on the left-hand side.
    Each upper context of the symbol requires a different computation of the information. Design an appropriate computation for each rule having the symbol on the right-hand side.
    The information can be computed independently of the particular context, using attributes of the symbol itself or remote-access attributes. Design an appropriate lower-context symbol computation.
    The information can be computed almost independently of the particular context, using attributes of the symbol itself or remote-access attributes. There are a few exceptions where a lower context of the symbol requires a different computation. Design an appropriate lower-context symbol computation and override it in the exceptional contexts.
    The information can be computed almost independently of the particular context, using attributes of the symbol itself or remote-access attributes. There are a few exceptions where an upper context of the symbol requires a different computation. Design an appropriate upper-context symbol computation and override it in the exceptional contexts.

    For example, the postulated relationships among the expression values in the Plus rule state that the value at the node is the sum of the values of the children. That requires a computation in the lower context of the node (i.e. the context of the node and its children). Moreover, the computation will be different for each rule (Plus, Minus, etc.) because different rules embody different operations. Thus this case fits row one's pattern, and we should design an appropriate computation for each rule having Expr on the left-hand side:

    RULE Plus:  Exp ::= Exp '+' Exp
    COMPUTE Exp[1].Value=ADD(Exp[2].Value,Exp[3].Value);
    END;
    
    RULE Minus: Exp ::= Exp '-' Exp
    COMPUTE Exp[1].Value=SUB(Exp[2].Value,Exp[3].Value);
    END;
    
    ...
    
  4. Consider each rule associated with an attribute, and design an appropriate computation for the attribute.

Entities with state

Information can be associated with particular entities, rather than with the appearances of those entities in the tree. The variable A is an example of an entity that may appear at many points in the tree representing an expression. That variable has a state, which is its associated value. The value is associated with the variable itself, not with any specific tree context in which that variable might appear. This description is characteristic of the Flyweight design pattern, in which the information is stored in a shared object that can be used in multiple contexts simultaneously.

Eli implements the Flyweight design pattern by a definition table key, a ``handle'' that provides access to an arbitrary number of properties of arbitrary types. Thus a variable is represented by a definition table key, and the variable's value is stored as a property of that key. Every tree node representing a variable has an attribute named Key, of type DefTableKey; the Key attributes of nodes representing instances of the same variable have the same value. This definition table key can be used to access a Value property, so that it is possible to obtain the value of a variable at any node representing that variable.

Computations like the example at the end of the last sub-section represent explicit dependence because of the way they are written: Exp[1] depends explicitly on Exp[2] and Exp[3]. The fact that an entity with state can be referenced at many places in the tree means that there may be implicit dependences among the computations in the tree. For example, suppose that our expressions included assignment. In that case, a variable's state (its value) would be updated by some computations and used by others. This implicit dependence determines the order in which certain computations must take place, and therefore it must somehow be made explicit.

Here is a general process for designing computations involving property values:

  1. Determine the type of value to encode the information, and introduce a property of that type.
  2. Determine the contexts in which the property is set.
  3. Determine the contexts in which the property is queried.
  4. Determine the dependence relation between (2) and (3), and make it explicit. There are two common cases:

Step (1) might require a new declaration in a property definition language specification. Computations involving the the property value might require that additional access functions be defined. Steps (2) and (3) serve to place the property access operations in the tree, while step (4) determines what computations are needed to express the implicit dependence.

Dependence is made explicit in the case of all (2) before any (3) by using remote dependence to make an attribute of a common parent of all (2) and (3) depend on the computations that set the property's value. All computations using the property's value are then made dependent on that attribute of the common parent, again using remote dependence. The attribute of the common parent is often VOID, but this is not required.

Dependence is made explicit in the case of textual order dependence by using a chain. Again, the chain is often VOID.

Task

You work for a company that makes microwave ovens. They are developing a new line, with a more powerful microprocessor to handle interaction with the user. Marketing has decided that it is important to move away from numbered recipes, using the capability of the new microprocessor to give recipes names. The user can select the name of the appropriate recipe via a touch screen.

Your group is developing the ``named menu'' facility. After some discussion, it becomes clear that this may be a nontrivial project. For example, consider the simple case of roasting a chicken. If the user simply selects a ``chicken'' menu item, you don't have enough information because you don't know how much the chicken weighs. Thus your solution has to be able to input arbitrary information in association with menu selection. Each menu item will have to have an associated program that prompts the user, accepts input, and calculates the time to run the oven.

Moreover, being experienced in the ways of the marketing department, you realize that it's only a small step to having the user create menus. Clearly the user isn't going to be able to write programs to implement their recipes! Why not get ahead of marketing for once, and make your job easier also? You therefore decide that you will store each recipe as a string consisting of a sequence of simple expressions. Such a representation will take less space than the program to implement the recipe, it will be easier for you to create recipes (writing expressions is easier than writing programs), and you'll be in a fine position when marketing finally thinks of user recipes.

When the user selects the name of a recipe on the touch screen, the corresponding string will be fed to a program that reads it, builds a tree, queries the user for the necessary data, and evaluates the expression sequence. The result becomes the time input of the oven. Of course you recognize immediately that this program can be generated by Eli, and therefore you don't have to actually write it!

You and your colleagues decide that the tree structure should be defined as follows:

RULE Recipe:   Source LISTOF Action      END;

RULE Store:    Action ::= Name '=' Exp   END;
RULE Print:    Action ::= Name           END;

RULE Fetch:    Exp    ::= Name           END;
RULE Constant: Exp    ::= Number         END;
RULE Plus:     Exp    ::= Exp '+' Exp    END;
RULE Minus:    Exp    ::= Exp '-' Exp    END;
RULE Negate:   Exp    ::=     '-' Exp    END;
RULE Star:     Exp    ::= Exp '*' Exp    END;
RULE Slash:    Exp    ::= Exp '/' Exp    END;

RULE Variable: Name   ::= Identifier     END;

You also decide that the form of an integer should be that same as it is in C. That's easy to remember, and easy to specify to Eli by using a canned description.

Identifiers are more interesting. You decide that they should be able to carry units with them, so that when the user is queried for a value they will know what units are expected. Here are some examples of legal identifiers:

Weight(lb)	Temperature(F)	Doneness(1-3)	scratch
Since parentheses are used for the units, you decide not to use them for grouping. That means you may need temporary variables like scratch to override operator precedence. For example, suppose that you need to assign the value of (a+1)*b to result. Because parentheses can't be used for grouping, you would need to write a sequence of two actions:
scratch = a+1
result = scratch*b
Presumably such temporary variables don't need units.

You were tasked with the specification of the basic symbol formats and the tree computation; your colleagues have specified the tree builder, the identification of variables, and the actual process of getting input from the user. Click here for the file Calci.fw, which contains all of those specifications. You should not alter file Calci.fw unless you find a bug! Instead, simply put the name Calci.fw in your specs file along with the names of your specification files. As the semester goes on, you will learn about everything in Calci.fw. You can ask Eli to format Calci.fw as a PDF file for easy reading:

-> Calci.fw :fwTex :pdf > Calci.pdf

Your tree computations should establish an integer value for every expression, according to the normal rules of integer arithmetic. Assume that every value is in bounds and that no divisor will ever be zero.

Number is the integer value represented by a Constant node.

The result of evaluating a Fetch expression must be the current value of the variable. From specifications in file Calci.fw, Eli creates a function that you can use to obtain the value. Here is its interface:

int ObtainValue(DefTableKey key, int sym)
/* Obtain the value of a variable, possibly by asking the user
 *   On entry-
 *     key=definition table key of the variable
 *     sym=string table index of the variable name
 *   On exit-
 *     ObtainValue=value of the variable
 ***/
Computations generated by Eli from specifications in file Calci.fw set the attribute Name.Key to the definition table key of the variable and the attribute Name.Sym to the string table index of the variable's name. You should use those attributes as arguments to ObtainValue.

A Store action must set the value of the variable to the result of evaluating the expression. From specifications in file Calci.fw, Eli creates a function that you can use to set the value. Here is its interface:

void ResetValue(DefTableKey key, int val)
/* Reset the current value of a variable
 *   On entry-
 *     key=definition table key of the variable
 *     val=value to which the variable should be set
 *   On exit-
 *     The variable's current value is val
 ***/

A Print action outputs the value of the expression to the oven. Use printf with the format string "%d\n" to output the value of the variable at every Print node.

Your specification must guarantee that all actions are carried out in the order in which they appear in the input text. Note that this requirement results in an implicit dependence among the actions, and that dependence must be made explicit as discussed above.

After you create a file containing input text (assume that it is named input), you can test your processor in two ways:

  1. Independently of Eli:
    1. Copy your executable file from the cache
      -> Calc.specs :exe > myprog
      
    2. Run that executable with your text:
      % myprog input
      
      The program will request input if it has variables whose values are unknown.

  2. By requesting Eli to run the executable file:
    . +cmd=(Calc.specs :exe) (input) :run
    
    This Eli request can be explained as follows: Parentheses around a product indicate that Eli should use the complete path name of the file representing that product.

Click here for further information about the form of an Eli request.


Instructor
Revision 1.7 (2005/09/22 20:14:53)