Expressions

Evaluation and Expressible Values

An expression is a phrase that produces a value when it is executed. Executing an expression is called evaluation. Evaluation of an expression may require additional information, which is provided by a data structure called a context:

value = eval(expression, context)

For example:

eval("x + 2", context) = 5

In this case the context might simply be a symbol table that contains the association x = 3.

The values produced by an expression are called expressible values or expressibles. Not all values are expressible. For example, in most languages numbers, characters, Booleans, and strings are expressible, while functions and types are not.

Types of Expressions

A typical programming language, L, provides four types of expressions:

Literals

The value of a literal expression is itself. Typical examples of literals are strings, numbers, characters, and Booleans.

Numbers

Numbers have two forms: exact and inexact:

Exact numbers include integers and rationals.

Integers can be expressed in decimal, octal, or hexadecimal notation. Here are some examples from the Scheme language:

42, 052, 0x2a, 3/5

While Scheme integers can have any number of digits, Java and C++ programmers must specify the size of their integers:

42l = 42 as a 32-bit integer

Inexact numbers include real and complex numbers:

A real number can be expressed in Scientific or floating point representation. Here are a few examples:

3e-2 3.14116 3.5+4.2i

Symbols

A symbol, also called a name or identifier, is bound to a name through a declaration. For example:

const double pi = 3.1416;

The binding, pi = 3.1416, is stored in a symbol table where it can be looked up later, when needed. This mechanism will be discussed in detail when declarations are covered.

In the Scheme language symbols may also be used as literals. We distinguish the symbolic and literal values of a symbol using Scheme's single quote operator. For example:

eval(pi) = 3.1416
eval('pi) = pi
eval(eval('pi)) = 3.1416

This is necessary because Scheme supports Symbol Processing, an important problem solving technique used by humans and intelligent programs.

Function Calls

Function calls come in three flavors:

Infix

An infix call is simply two expressions-- called operands-- separated by a binary operator:

Binary operators include the usual built in arithmetic and logical operators. Issues of precedence and associativity were discussed earlier.

Prefix

A prefix operator might have any number of operands, which might appear in a list following the operator:

<Prefix> ::= <PrefixOperator>(<Expression>*)

The number of required operands is called the arity of the operator.

Postfix

A postfix operator appears after the list of its operands:

In C/C++ the following expressions are considered postfix:

f(a, b, c)
a[i]
x++

Evaluation Models

There are two major families of algorithms used to evaluate function calls: substitution models and environment models.

Substitution Models

1. Replace each parameter in the body of a function by the corresponding operand.

2. Evaluate the resulting expression.

Environmental Models

Environmental models assume the availability of a data structure called the environment. Among other things, the environment contains symbol tables, perhaps organized as a stack or a tree. Every expression is evaluated relative to this structure. When symbols are encountered, the environment is searched for their corresponding values.

1. Evaluate the operands to create arguments.

2. Create a symbol table containing associations between the parameters of a function and the corresponding arguments

3. Temporarily extend the current environment with this symbol table.

4. Evaluate the body of the function relative to the extended environment.

5. Remove the temporary symbol table from th8e environment.

Special Forms

Certain expressions use custom evaluation algorithms that don't fit into any of our models. These are called special forms.

Short-Circuit Evaluation

Short circuit evaluation is this:

Evaluate operands from left to right until the answer is known, then stop evaluating.

Short circuit evaluation is used with Boolean conjunction and disjunction. For example, the value of:

(3 < 4) && true && (2 == 1 + 3) && (5 == 3/0)

is false. No "divide by zero" error occurs.

Short circuit evaluation is useful when two tests must be performed on a piece of data, and the second text only makes sense if the data passes the first test. For example:

if (x instanceof Number && ((Number)x).doubleValue() > 0) {
// do something with x
}

Conditional Evaluation

Conditional evaluation is this:

1. Evaluate operand 1.
2. If true, evaluate operand 2, ignore operand 3
3. If false, evaluate operand3, ignore operand 2

Conditional evaluation is present in the conditional expressions of C/C++/Java:

C?A:B

Make sure you understand the difference between this conditional expression and the conditional command:

if (C) A; else B;

Evaluation

We want expressions in our Simple language to know how to evaluate themselves (See the Command Processor Pattern described in Alpha). To guarantee this will be the case, we declare an abstract evaluation method in our Expression class:

abstract class Expression extends Phrase {
    public static boolean next(List tokens) { ... }
    public static Phrase parse(List tokens) throws ParseError {
         ...
    }
    abstract public Object eval(Context context);
    // etc.
}

The result of evaluating an expression is a value of some sort: a number, a Boolean, a String, etc. To cover all possibilities, we will identify the class of all possible Simple values with Java's Object class. Thus, the return value of eval() is Object.

Note that eval() expects a context as input. A context is roughly equivalent to the runtime environment of the virtual machine that evaluates Simple expressions. Eventually, the context will include memory, symbol tables, and I/O facilities. For now, we only assume that our context knows how to perform basic arithmetic and logic operations such as those performed by any ALU and can search a symbol table for the values of declared symbols:

class Context {
    //operator ::= + * - / and or not < = etc:
    public Object apply(String operator, Object arg1, Object arg2)
    throws EvalError {
         ???
    }
    // search symbol table for value of name:
    public Object get(String name) throws EvalError {
         ???
    }
    // etc.
}

Recall that our language, Simple, has three types of expressions:

We introduce three corresponding extensions of Expression. The value of a number is itself:

class Number extends Expression {
    private Number value;
    public Object eval(Context context) throws EvalError {
         return value;
    }
    // etc.
}

The value of a symbol is found by looking it up in the context's symbol table:

class Symbol extends Expression {
    private String name;
    public Object eval(Context context) throws EvalError {
         return context.get(name);
    }
    // etc.
}

Evaluating an operation is recursive. First, the operands are evaluated, producing objects (values) called arguments. Finally, the context applies the operator to the argumants:

class Operation extends Expression {
    private Expression operand1;
    private String operator;
    private Expression operand2;
    public Object eval(Context context) throws EvalError {
         Object arg1 = operand1.eval(context);
         Object arg2 = operand2.eval(context);
         return context.apply(operator, arg1, arg2);
    }
    // etc.
}

Evaluation 2

Value eval(Expression exp, Context context) {
    if (exp is a literal) return exp;
    if (exp is a symbol) return lookup(context, symbol);
    if (exp is a funCall) return evalFunCall(exp, context);
    if (exp is a specialForm) return evalSpecialForm(exp, context);
    throw new Exception();
}