CSE 130 Lecture Notes from Spring 1998

CSE130 LECTURE NOTES

December 6, 1999

ADMINISTRATION

Today I am distributing sample question answers for the midterm. Remember that the final exam is exactly one week from today!

Please complete the TA evaluation forms carefully.

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!

Consider the pseudo-Pascal summation function

function sum (lo,hi:int; macro k:int; macro f:real): real;
    var s: real := 0;
begin
    for k := lo to hi do s := s + f;
    return s;
end;

With call-by-macro the actual argument expressions for k and f will be evaluated again each time the formal parameter is used, so we can write for example sum(1,n,j,a[j]*b[j]) to compute the dot-product of two vectors a and b of length n.

THE IMPORTANCE OF CALL-BY-MACRO

All the other parameter-passing methods are basically similar: they work by initializing the formal parameters as local names in an environment used for executing the called block. They are all variants of "call-by-environment."

Practical programming languages use call-by-environment, but call-by-macro is theoretically important because

it is a common informal way to reason about invocation: simulating mentally step-by-step what the function body does with the actual arguments in place of the formal parameters
it is used in the lambda calculus, which is the mathematically most abstract programming language
it is formally simpler: it doesn't introduce these complex objects called "environments"
it does appear in practical languages under the guise of macros.

In Algol 60, call-by-macro is called call-by-name, but implemented using higher-order functions (i.e. using function arguments).

Consider the pseudo-Pascal summation function using call-by-macro from before. This can be implemented using call-by-value with function arguments:

function sum (lo,hi:int; ref k:int; f:void->real);
    var s: real := 0;
begin
    for k := lo to hi do s := s + f();
    return s
end;
function f(): real;
begin
    return a[j]*b[j];
end;

The lesson to learn here is that higher-order functions give the functionality of call-by-macro.

THREADS, TASKS, AND PROCESSES

These are different names for similar concepts. From a machine-level point of view, a process is one series of instructions being executed. From a high-level PL point of view, we will see that a process is similar to an object.

Processes have state: the values stored in the CPU registers, plus perhaps memory. Changing between processes is expensive because the state of one process has to be saved and the state of another has to be restored.

A "thread" is a lightweight process, i.e. one with only a small amount of state that needs to be saved and restored. Advantage: switching between lightweight processes is fast.

The definition used by many authors is that each process has its own address space, while threads share memory, i.e. share one address space.

TASKS IN ADA

In Ada, a task specification looks like an abstract type (ADT) specification. The outside world (i.e. any other task) interacts with a task by calling its "entries".

A task is like an object and an entry is like a method for an object. Entries can have "in" and "out" parameters.

task buffer is
entry give (x: in item);
entry take (x: out item);
end buffer;

A task body consists of code that can "accept" entry calls at certain times during execution. The code below can only accept a "take" immediately after accepting a "give":

task body buffer is
    it: item;
begin
    loop
        accept give (x: in item) do
            it := x;
        end give;
        accept take (x: out item) do
            x := it;
        end take;
    end loop;
end buffer;