CSE 130 Lecture Notes, May 15, 2002

CSE130 LECTURE NOTES

May 15, 2002

ADMINISTRATION

Reminder: The midterm will be next Monday in class (Center Hall room 119). I will be out of town starting Friday, so my office hours on May 20 and 22 are canceled. The TAs will be answering questions in their office hours and on Discus. Prof. Gary Cottrell will give the lecture on May 22.

The policy for what you can use during the exams is as follows: You may bring and use your own personal hand-written notes, and a printed copy of the published lecture and section notes. You may not use any books or any other materials.

THE DIFFICULTY OF REQUIREMENTS ANALYSIS

I sense that there is some frustration about the vagueness of the description of the current project. There are deeper issues to understand and reflect upon here.

(1) Figuring out exactly what the problem to be solved is, is called requirements analysis. This is intrinsically difficult. For complicated tasks, there are always many, many details to be specified. It is difficult to write down a specification that is unambiguous, comprehensive, and an order of magnitude smaller than an actual implementation.

(2) You should think about what your real job is, i.e. what would really make the client happy. If the client hasn't given details in the initial task description, perhaps s/he does not want to. Your job is not to force the client to do something s/he does not want to. Instead, try to understand the wider context, and what the customer really wants. Here, there are at least three different perspectives:

As a class exercise, the real objective here is to understand and compare different PLs.
As a simulation of an artificial universe, the objective may be to create a universe that is fun for a player, with the exact details arbitrary.
As a simulation of a real universe, the objective may be to reproduce reality. In this case questions should be answered experimentally, not by querying the client.

(3) Interviewing clients to determine the detailed specification for a programming task is always a frustrating effort for both the interviewers and the interviewees. In any large project, you have to make assumptions in order to make progress. You should try to ensure that assumptions are easy to change. This means that assumptions should be documented and encapsulated.

ESCAPE COMMANDS: EXCEPTIONS

Let's think about the design of escape commands. In general a condition that makes an escape necessary is called an "exception". When an exception is triggered, and control escapes from inside a command, usually some recovery commands should be executed. Here are some desirable features of exception handling:

(0) The single entry, single exit property should be preserved: that control can only flow into the command at one point, and can only flow out at one point.

(1) It should be possible to raise exceptions and recover from them for any command, not just loops. There can be reasons to abort any command.

(2) When an exception is handled, it should be possible to execute some recovery commands as an alternative to the regular command which gave rise to the failure. For example if an exception is raised while reading an input value, it should be possible to recover by assigning a default value.

(3) It should be possible to provide exception handlers for many different types of exception.

(4) Providing exception handlers should be optional. If a handler is not provided, the exception should cause an escape from the enclosing block.

(5) Programmer-defined exceptions like "negative age" should be allowed in addition to system-defined exceptions like "division by zero".

EXCEPTIONS IN ADA

We saw above five PL design criteria for exception-handling. The Ada language has a successful exception mechanism that meets all these requirements, as do ML and Java. The mechanisms are very similar, so we'll just look at the Ada syntax.

In general exception handlers occur at the end of blocks:

begin
    C;
exception
    when e₁ => C₁;
    when e₂ => C₂;
    ...
end;

If the exception e_i is raised while executing the command C, then C is abandoned and C_i is executed instead.

If a recovery command is not provided for an exception, then the exception is propagated to the next enclosing block. For example:

begin
    begin
        C;
    exception
        when e1 => C1;
    end;
exception
    when e1 => C1';
    when e2 => C2;
    ...
end;

In the code above, C1' will never be executed, but C2 may be.

A REALISTIC EXAMPLE OF EXCEPTION-HANDLING

Here is an example of an Ada procedure where three exceptions may be raised, and how those exceptions are handled. Note that negative_rainfall is a user-defined and user-raised exception, and that end_error is handled non-locally.

procedure main is
    type
        month is (jan, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec);
        rainfall: array (month) of float;
    negative_rainfall: exception;
    procedure input_data is
    begin
        for amonth in month
            loop
                begin
                    get(rainfall(amonth));
                    if rainfall(amonth) < 0.0 then raise negative_rainfall
                exception
                    when data_error => rainfall(amonth) := 0.0;
                    when negative_rainfall => rainfall(amonth) := 0.0;
                end;
            end loop;
    end;
begin
    ...
exception
    when end_error => put("Insufficient data");
    when others => put("Unknown catastrophic error");
end

THE "EIFFEL" WAY TO USE EXCEPTIONS

It is bad programming style to use exceptions in place of regular testing for alternative cases, e.g. for end-of-file, or for leap years in software that processes dates.

The language Eiffel enforces a rule of good programming style, that the only ways to leave an exception-handler are

(1) to execute the failed operation again, or

(2) to propagate the exception.

With re-execution (called retry), after raising e1 and executing C1, C would be executed again. With propagation (called reraise), after raising e1 and executing C1, C1' would then be executed.

The use of exceptions in the Ada example above does not meet the Eiffel criteria.

In general, there are two main opinions on programming style in the presence of errors. The first attitude is that code should be written defensively, and as many errors as possible should be handled, even if they cannot be fixed completely. The second attitude is that errors should be revealed as quickly as possible, so that they can be fixed properly.

For example, according to the first attitude, one should write
for (i = 0; i <= 10; i++) { ... }

According to the second attitude one should write
for (i = 0; i != 10; i++) { ... }

Suppose that the code inside the loop erroneously modifies i to have a value greater than 10. The first approach will hide this error, while the second will reveal it to the user, by causing an infinite loop.

NEW TOPIC: STATIC VERSUS DYNAMIC TYPE-CHECKING

Definition: Type-checking is the process of checking that for each operation, the types of its operands are appropriate, i.e. that the operation is legal for these types.

Static type-checking means type-checking done by the compiler, before executing the program.

Dynamic type-checking means type-checking done while executing the program. The compiler must generate extra code to do this checking.

The descriptor strong type-checking is sometimes used to mean static type-checking. Alternatively, it is used to mean complete type-checking, i.e. guaranteeing that any mismatch is caught between the signature of an operation and the types of its actual arguments.

WHY COMPILE-TIME TYPE-CHECKING IS VALUABLE

(1) If the compiler can know for sure the types of operands, then it can generate code for the right implementation of (e.g.) addition with no space overhead of generating code for alternative operations, and with no run-time overhead of testing and choosing one of the implementations.

(2) The compiler can use complex type-checking algorithms just once, with no run-time speed penalty.

(3) Errors can be reported at compile-time instead of run-time.
(3)(a) Experts on software engineering and management say that the later an error is caught, the more it costs to fix the error.
(3)(b) Some run-time type conflicts may not be caught at all during testing, because they only happen for un-tested input values.

This last reason (3) is the most important.

WHY RUN-TIME TYPE-CHECKING IS VALUABLE

(1) Human input is often of unpredictable type. Languages with run-time typing can deal with this more easily.

(2) At run-time, type-checking can know the actual values of variables, not just their initial value or declared type.

In practice all languages combine run-time and compile-time type-checking. Verifying that index variables are within range can often only be done at run-time.

Question to think about: when can it be done at compile-time?

(3) Less verbosity. Example: the awk language.