CSE 130 Lecture Notes from Spring 1998

CSE130 LECTURE NOTES

December 1, 1999

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.

The binding occurrence of a formal parameter name is in the signature. Occurrences in the body of the function or procedure are applied.

Remember the rule of alpha-conversion: the meaning of a block is unchanged if a name that is bound locally in the block is changed everywhere inside the block.

In most languages alpha-conversion is a valid rule for formal parameters. This implies that the details which are hidden from the user of a function or procedure include the names of formal parameters.

So which actual arguments match which formals should not be specified by name. It is usually specified by position: the parameter type of a function is a tuple type.

In Ada arguments can be specified by name using the same notation as for record aggregates. For example a function call might be:

integrate(epsilon => 0.001, f => sine, a => 0.0, b => pi);

This allows actual arguments to be given out of order, and default values can be used for unspecified arguments: e.g. epsilon above could have been left out if the default value was satisfactory. Common Lisp also has named parameters.

SEMANTICS OF CALLING FUNCTIONS AND PROCEDURES

Informally, the semantics of calling a function or procedure is as follows:

evaluate the actual arguments
pass the actual arguments as values for the formal parameters
execute the block that is the function or procedure body
return any results back.

We need to clarify each of these four stages.

The point to notice here is that expressions are never passed as arguments in mainstream languages. They are always evaluated first, and the result values are passed.

Remember the discussion of evaluation order for expressions. An operation like + applied to two arguments, e.g. 2*x + 3*y is really a function-call plus(times(2,x),times(3,y)).

The most important rule of expression evaluation is that arguments are evaluated before the function applied to them is called, but if-then-elseis special. Languages differ in whether or not it is specified in what order multiple arguments are evaluated.

CALL BY VALUE

In the following procedure declaration f1 and f2 are formal parameter names and x is the name of a local variable.

procedure p(f1,f2:t);
var x: t;
begin
...
end;

Given the call "p(e1,e2)" where e1 evaluates to the value a1 and e2 evaluates to the value a2, the simplest semantics of parameter-passing says that the call is equivalent to executing the block

begin
    const f1 := a1;
    const f2 := a2;
    var x: t;
    ...
end;

This method of parameter-passing is called call-by-value. A variant allows f1 and f2 to be local variables as opposed to local constants.

CALL BY VALUE-RESULT

When an actual argument is an expression, it makes no sense to use it for returning a result value. However when an actual argument is a variable name, the final value of the formal parameter can be copied back into the actual argument variable. More formally, given

procedure p(inout f:t);
begin
...
end;

the call "p(x)" where x is the name of a variable is equivalent to

begin
    var f:t := a; // "a" denotes the current value of x
    ...
    x := f;
end;

Call by value-result is used in Ada.

CALL BY REFERENCE

When an actual argument is a variable name, it makes sense to pass the location denoted by the name to the called procedure. Then the formal parameter name acts as a local name for the global location.

This is the semantics of Pascal "var" parameter-passing. We can explain it more formally as follows. Given

procedure p(var f:t);
begin
...
end;

the call "p(x)" where x is the name of a variable is equivalent to

begin
const f: pointer to t := location(x);
...
end;

In some languages, for example C, call-by-reference is not available but in can be achieved by using call-by-value and passing the location of a variable instead of its value.

CALL BY MACRO

The idea in call-by-macro is that the actual argument is textually inserted into the called block. This contradicts the statement earlier that the first step in the semantics of function-calling is to evaluate all the argument expressions!