10. Language V1

The language V1 differs from V0 only in its semantic specification. In the chapter on V0, we saw how a parse tree for V0 can print itself. Let’s now show how a parse tree can evaluate itself.

As an example, the command plcc-rep on input add1(+(2, 3)) produces the following output:

6

The term evaluate can have many meanings (one of which is to produce a string representation of the input), but for our purposes, to evaluate an arithmetic expression such as add1(+(2, 3)) means to produce the integer value 6. In other words, the value of an arithmetic expression is its numeric value using usual rules for arithmetic.

(Remember that we are abstracting the notion of value to refer to an instance of the Val class. In this setting, a numeric value is an instance of the IntVal subclass of Val.)

If an expression involves an identifier, we need to determine the value bound to that identifier to evaluate the expression. For example, suppose the identifier x is bound to the integer value 10, then the expression sub1(x) would evaluate to 9.

The interpreter evaluates every expression in some environment. This environment determines how to obtain the values bound to the identifiers that occur in the expression.

Subclasses of the Exp class are the appropriate places to declare evaluation behavior, which we implement using a common method called eval. Three classes extend the Exp class: LitExp, VarExp, and PrimappExp. Recall that all of these classes appear as non-terminals of the grammar in the syntax section of the PLCC specification file. This means that the rules determine the types of nodes that will appear in a parse tree created from programs in our language, and therefore that, to evaluate a program, the parse tree must be traversed.

Because an environment is sometimes needed to do the evaluation, an environment must be passed to the eval method.

10.1 LitExp

We’ll start with LitExp. Below is the semantic specification that defines the behavior of a LitExp object. The eval method coexists with the __str__ behavior that we defined in V0.

LitExp
%%%
def eval(self, env):
    return IntVal(self.lit.lexeme)

def __str__(self):
    return self.lit.lexeme
%%%

Remember that a LitExp instance has a Token field named lit. When we apply the __str__ method to this field, we get the string of decimal digits that comes from the part of the program text we are parsing. The IntVal initializer converts this string into a real Python integer that becomes part of the IntVal instance. Obviously an environment bears no influence on the value of a numeric literal. The literal 10 evaluates to the integer value 10 no matter which environment, so the eval method for an instance of LitExp simply returns the appropriate IntVal object without consulting the environment passed to it. env is still passed to the method because the code traversing the tree does not know which subclass of Exp the node belongs to.

10.2 VarExp

Next we consider VarExp. Below is the semantic specification that defines the the eval method of a VarExp object.

VarExp
%%%
def eval(self, env):
    return env.applyEnv(self.symbol.lexeme)

def __str__(self):
    return self.symbol.lexeme
%%%

A VarExp object has a var attribute of type Token. Given an environment, the value bound to var is precisely the value returned by applyEnv, which in turn is the value of the expression.

The value of an expression consisting of an identifier is the value bound to that identifier in the environment in which the expression is evaluated, as determined by the application of applyEnv.

10.3 PrimappExp

Finally we consider PrimappExp. A PrimappExp object has two attributes: a Prim object named prim and a Rands object named rands. To evaluate such an expression, we need to apply the given primitive operation (the prim object) to the values of the expressions in the rands object.

10.3.1 Terminology: apply and primitive

We use the word apply in two related ways.

1. On a variable's name, to look up its value, as seen previously.
2. On a function: To apply a function is to call the function with the provided operands.

The word primitive is used because the functions defined in this language are built in. Their names are in the language syntax, and we are now hard-coding how they work into the semantics of the language. User-defined functions will be done very differently.

10.3.2 Rands

An object of type Rands has an attribute, named expList, whose type is a list of Exp. To perform the operation determined by the prim object, we need first to evaluate each of the expressions in expList. A utility method named evalRands in the Rands class does that work. Of course, this method needs to know what environment is being used to evaluate the expressions, so an Env object is a parameter to this method.

Rands
%%%
def evalRands(self, env):
    return [e.eval(env) for e in self.expList]

def __str__(self):
    return ",".join(str(e) for e in self.expList)
%%%

The evalRands method returns a list of Vals.

The expressions appearing in an application of a primitive can be called its operands, or its actual parameters; the values of these expressions are called its arguments.

Careful readers will have observed that the class name Rands is derived from the word operands, and that the name args in the evalRands method is derived from the word arguments.

10.3.3 Pulling it all together

We now have the pieces necessary to define the eval method in the PrimappExp class:

PrimappExp
%%%
def eval(self, env):
    args = self.rands.evalRands(env)
    return self.prim.apply(args)

def __str__(self):
    return f"{self.prim}({self.rands})"
%%%

In summary, to evaluate a primitive application expression (a PrimappExp), we evaluate the operands (a Rands object) in the given environment and pass the resulting argument list to the apply method of the primitive (a Prim) object, which returns the appropriate value.

10.4 Prim

We now define the behavior of the apply methods in the various Prim subclasses. By the time a Prim.apply receives its arguments, all operand expressions have already been evaluated, so the arguments contain only values. Therefore, the apply method's sole responsibility is the application of primitives to values.

Prim objects like AddPrim and Add1Prim have no "memory", that is, no attributes. However, we endow these objects with behavior, so that an AddPrim object knows how to add values passed in to it, an Add1Prim object knows how to increment values, and so forth.

Four of the Prim objects need two arguments (+, -, *, and /), and three of them need one argument (add1, sub1, and zerop). Since args is a list of Val arguments, we can grab the values from the list to evaluate the result. Below is the semantic specification for the AddPrim class.

AddPrim
%%%
def __str__(self):
    return "+"

def apply(self, args):
    if len(args) != 2:
        raise LanguageError("two arguments expected")
    i0 = args[0].intVal().val
    i1 = args[1].intVal().val
    return IntVal(i0 + i1)
%%%

The intVal method calls shown in this specification convert Val objects (such as args[0]) into IntVal objects, essentially like "downcasting". These objects, in turn, have int attributes named val. So both i0 and i1 are legitimate Python integers that can be added together to return the resulting IntVal object. The Val class also defines the intVal method: an attempt to apply the intVal method to a Val object that is not an IntVal throws an exception.

The definitions of apply for the classes SubPrim, MulPrim, and DivPrim (the latter two are added in V1) have obvious implementations, except that in DivPrim, the apply method throws an exception if it detects a division by zero.

For the Add1Prim class, the apply method expects only one value, which is passed as element zero of the args list.

Add1Prim
%%%
def __str__(self):
    return "add1"

def apply(self, args):
    if len(args) != 1:
        raise LanguageError("one argument expected")
    i0 = args[0].intVal().val
    return IntVal(i0 + 1)
%%%

Again, the definition of apply for the Sub1Prim class is entirely similar. Language V1 also has a seventh primitive named zerop. The definition of apply for the ZeropPrim class returns an IntVal of 1 (true) for a zero argument and an IntVal of 0 (false) for a nonzero argument.

10.5 Program

In our final implementation step, we will define the _run method of a Program object that returns the value of its expression.

Program
%%%
env = Env.initEnv()

def _run(self):
    return str(self.exp.eval(Program.env))
%%%

In V1 there is no way to "assign", or more accurately bind, a value to a variable. An empty environment would only allow for literal expressions with no variables, since every variable would be unbound. To test V1, we hard-code an initial environment initEnv specific to this language that has the following variable bindings (think Roman numerals!):

For V1, this environment can be obtained by a call to Env.initEnv. These bindings give us some variables to play with. We will dispense with them in a later language.

To test V1, run the plcc-rep command in the Python subdirectory and enter expressions at the prompt.