Thursday, April 15, 2010

DeadEnds Interpreter, Expression Values

The most common operation that occurs when the DeadEnds Interpreter is running a program is expression evaluation. Within the context of the interpreter an expression is a semantic entity, an object of a sub-class of TWInterpExpression, created when a DeadEnds program was parsed. Expressions are evaluated by their evaluate: methods that are passed a symbol table (an object of class TWInterpSymbolTable) that holds the values the variables at the time of the call.

Here are the forms that a value can take.

As a TWInterpExpression
A TWInterpExpression object is the semantic representation of a bit of programming language syntax, part of the internal form of a parsed module. These expressions are recursive. For example, the expression found in a DeadEnds program:

i*alpha + b*21

is represented as a tree of seven TWInterpExpressions, three for the variables, one for the integer constant, two for the multiplication operators, and one for the plus operator. It is better to think of this structure as the potential for computing a value, rather than as the value itself. The process of evaluation, implemented by the evaluate: methods, is to convert these trees of semantic objects in a single real value. The evaluate: method for an integer constant expression (an object of type TWInterpIntegerConstant, a subclass of TWInterpExpression), returns the integer constant as an R-Value (see below). The evaluate: method for a variable (an object of type TWInterpVariable, also a subclass of TWInterpExpression) looks up the variable name in the sequence of symbol tables that are currently active and returns the variable's value as an R-Value. The evaluate: method for a binary expression (an object of type TWInterpBinaryExpression, also a subclass of TWInterpExpression) recursively calls the evaluate: methods on its left and right sub-expressions to get two R-Values, combines those values using the mathematical operator, and returns the overall result as a new R-Value.

As final, evaluated, values. These values are Booleans, Unicode characters, integers, floating point numbers, Unicode strings, lists, sets, tables, nodes and records. These are the types that a DeadEnds programmer thinks in. The DeadEnds Interpreter allows the user to write programs and think in terms of values of these types.

Behind the scenes the DeadEnds Interpreter must represent these values in a consistent form. There are four of these forms:

Primitive values
Values at this level are the lowest form possible. For example an integer is a 32 or 64 bit word on the computer. A list is an NSArray from the Foundation framework.

Boxed Values
Values at the next level up are Objective-C objects that represent the primitive values. Boxing is the term used to mean creating an object type for a primitive type in order to allow values of the primitive type to have all the benefits of objecthood. In the case of the DeadEnds Interpreter, of the Boolean, Character, Integer, and Float type are all boxed as NSNumber objects from the Cocoa Foundation. The String type is represented at the primitive level as an NSString object, which is an object, so have the same value at the both the primitive and boxed levels. The List, Set, and Table values at this level are the same as at the primitive level, objects of the Foundation classes NSArray, NSSet and NSDictionary. The Primitive and Boxed values of Node and Record objects are TWGedcomNode and TWGedcomRecord objects, which are classes defined in the TWGedcom Objective-C library.

An R-Value is nothing more than a Boxed Value and a type code to indicate what kind of value is boxed. The values returned by all evaluate: methods are R-Values.

L-Values are references to R-Values, and that's all that they are. A DeadEnds symbol table (an object of class TWInterpSymbolTable) contains a table (NSMutableDictionary) that maps variable names (NSStrings) to L-Values (objects of class TWInterpLValue). That L-Value refers to the R-Value that holds the boxed value of the variable. Consider the following code from a DeadEnds Program

Integer i = 0;
i = i + 1;

After the first line, the declaration of i, is interpreted there will be a new mapping added to the current symbol table. The variable name i maps to a newly created L-Value that refers to a newly created R-Value that contains a boxed NSNumber object that contains the Integer 0. When the assignment expression (the assignment expression is a top level binary expression whose left expression is the variable i and whose right expression is the binary expression i + 1. To evaluate an assignment expression first the right hand side is evaluated into an R-Value. In this case that R-Value is computed by looking up the R-Value of the variable i in the symbol table and adding 1 to it, so in this case a new value of 1. That value is boxed into an NSNumber and put in a new R-Value. Now the actual assignment occurs. Here the evaluator looks up the variable in the symbol table, this time interested in its L-Value and the R-Value that the L-Value refers to. The boxed value of the R-Value computed from the right hand side is used to replace the boxed value of the R-Value to the L-Value refers to. This has the desired effect of changing the value of the variable i. The next time an expression includes this variable, the variable's L-Value refers to an R-Value that contains a boxed NSNumber object with a primitive value of 1. It's not as complicated as this description probable makes it seem.

No comments:

Post a Comment