CSE 130 Lecture Notes from Spring 1998

CSE130 LECTURE NOTES

November 29, 1999

ADMINISTRATION

Today we are returning the graded third projects. Overall, performance was excellent. The mean was 82 with a maximum of 98.
(If you submitted the project late, it may not have been graded yet.)

The CAPE representative will doing the course evaluation today.

EXPRESSIONS

Reminder: Traditional programming languages have three big categories of program fragments: definitions, expressions, and commands. For example x[2*j+1] := sqrt(u+v) is a command with two expressions embedded in it, namely 2*j+1 and sqrt(u+v).

Definitions:

An expression is a program fragment that gives a value when evaluated.
A value is a member of a type.
Evaluation is the process of computing the value denoted by an expression.

Expressions involve operators, literal constants (which are also called literals), and identifiers.

An identifier is a name that denotes a value which is obtained by "looking up" the declaration of the identifier. Typically identifiers can be either constants or variables. Parameter identifiers can be either also.

LITERALS AND AGGREGATES

A literal expression is one that directly denotes a value. Conceptually, there is only one, immediate, step of evaluation. Some examples of literals of various types are:

2.5E2
'!'
"prompt?"

Depending on the language, strings may or may not be legal literals, and may or may not be written differently from characters.

Question: how do you write down the complex number zero? Given the composite type declaration

type complex = record re, im: real end;

in Pascal you have to write the following:

var zero: complex;
...
zero.re := 0.0;
zero.im := 0.0;

An aggregate is a literal for composite types. In Ada you can write

zero: constant complex := (re => 0.0, im => 0.0)

The expression (re => 0.0, im => 0.0) is a literal of type complex, called an aggregate. Modern languages provide an aggregate notation for each composite type.

FUNCTION CALLS

A function-call expression is one that applies a function to one or more operands which are themselves expressions, for example sqrt(u+v).

Conceptually there are several steps of evaluation for function-call expressions:

first the argument expression(s) are evaluated,
then the resulting values are passed to the function
then the code of the function is executed.

These three steps are the same both for pure functions and for functions or procedures that have side-effects.

There is one rule of evaluation order for function-calls that is so fundamental, you may never have noticed it consciously: argument subexpressions must be evaluated before calling the function.

BUILT-IN OPERATORS ARE FUNCTIONS ALSO

Consider the arithmetic expression (2+3)*(4+5). As we've seen before, from a semantic point of view this is really a nested collection of function calls. Using a notation for abstract syntax, this expression is

times(plus(2,3),plus(4,5))

We saw before that the regular notation for operators where they appear between their arguments is called "infix". An operator that appears before its argument(s) is called "prefix". One that appears after is called "postfix".

Programming languages typically don't allow postfix operators because they make life difficult for the parser, but they occur in mathematics, e.g. for the factorial function, as in 29! using the factorial function.

The notation for abstract syntax used above standardizes all operators to be prefix. It is also possible to make all operators postfix. One variant of all-postfix notation is called "reverse Polish notation" or RPN for short.

EVALUATION ORDER FOR SUBEXPRESSIONS

Consider the expression (2+3+4*5)*6. In what order should subexpressions be evaluated? Clearly different orders give different results.

Writing this expression in standard prefix format forces some ambiguity on evaluation order to be resolved. There are two standard ambiguity-reduction rules:

some operators have precedence over others, e.g. * over + so 3+4*5 means 3+(4*5)
associativity is left-to-right so 2+3+4 means (2+3)+4

Thus the whole expression (2+3+4*5)*6 should be understood as times(plus(plus(2,3),times(4,5)),6)

Like standard prefix format, a parse tree representation is unambiguous. Operator precedence and ambiguity are lexical details that are important in concrete syntax but not in abstract syntax.

Sometimes some orders give an error and others don't: consider the expression

maxint + 1 - maxint

where maxint is the largest integer that can be represented.

EVALUATING ARGUMENTS OF FUNCTION-CALLS

In which order should the arguments of a function be evaluated?

The usual rule is left-to-right, so in plus(plus(2,3),times(4,5)) the inner addition is done before the multiplication.

Most modern programming languages carefully do not specify the order in which arguments are evaluated, because they want to allow the compiler to do optimizations:

constant folding means evaluating subexpressions at compile-time
common subexpression elimination means only evaluating a subexpression once, even if it is written several times

The most important reason not to specify the sequence in which multiple arguments are evaluated is to permit parallel evaluation.

CONDITIONAL EXPRESSIONS

Many languages allow "if-then-else" testing to be an operator that can be used in expressions. Notice that the "if-then-else" operator has three arguments. Written in function-call notation, the absolute value ofxcan be obtained as ifthenelse(x < 0, -x, x).

The rule that subexpressions must be evaluated before calling the function has one crucial exception: the "if-then-else" function. The first argument (the Boolean expression) should be evaluated first. Then, exactly one of the two other argument expressions should be evaluated.

Evaluating both the then and else expressions would be inefficient. Even worse, it could lead to an incorrect program, i.e. a non-terminating program. Consider the factorial function

function fact (n: integer): integer;
begin
return ifthenelse(n=0, 1, n*fact(n-1))
end;

If the third argument "n*fact(n-1)" is always evaluated, even when "n=0" is true, then calling this function will always give an infinite loop.

EXPRESSIONS AS FUNCTIONS

One aspect of functions being first-class objects is that they are values that can be the result of expressions. For example in a language that satisfies the "principle of type completeness" you can write (if flag then sin else cos)(u+v+w) to mean the same as if flag then sin(u+v+w) else cos(u+v+w)

In most traditional languages you can't write the first expression above.

If the function itself is an expression, then we need to know when it is evaluated: before or after the arguments?

Evaluating the function itself first is suggested by viewing (if flag then sin else cos)(u+v+w)as syntactic sugar for call(if flag then sin else cos,u+v+w)

One PL that has an explicit call operator is Lisp.