CSE 130 Lecture Notes, May 29, 2002

CSE130 LECTURE NOTES

May 29, 2002

ANNOUNCEMENTS

The midterm will be handed back today. If you don't get it now, you can get it in section on Friday.

We'll also do the TA evaluations today. CAPE will come for the instructor evaluation next Wednesday, June 5.

COMPOUND LITERALS: AGGREGATES

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 of x can 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.

FUNCTIONS ARE ABSTRACTIONS OF EXPRESSIONS

A pure function is like an expression. When it is called, it yields a result value.

More precisely, a function is an abstraction of an expression. All the user of the function needs to know is what value will be returned. Exactly how this value is computed is a detail that is private to the function.

Consider for example two alternative cosine functions:

function cosine (x: real): real;
begin
return sine(x + pi/2.0);
end;
function cosine (x: real): real;
begin
return integrate(sine,0,x,epsilon);
end;

Each function "encapsulates" a very different expression, but for the same argument, both always yield the same result.

PROCEDURES ARE ABSTRACTIONS ALSO

A procedure is an abstraction of a command. The user of a procedure only needs to know how it updates its parameters and global variables. It doesn't matter what the procedure does with local variables.

Just like for functions, procedures with different bodies and different algorithms can have exactly the same effect, i.e. they are the same from the user's abstract point of view.

ACTUAL AND FORMAL PARAMETERS

In all programming languages, functions and procedures can have one or more arguments. First we need some terminology:

"Parameter" and "argument" are synonymous.
When a function or procedure is called, the argument variables or values given to it are called actual arguments.
The parameters specified in the function or procedure signature are called formal parameters.