Control Structures

 

Exceptions

Early computer hardware handled errors it detected in one of 4 ways:

    1. By setting a program-testable flag after any instruction which produced an arithmetic error (divide by zero, overflow); the flag would be reset after the next instruction.

    2. Same as (1), but the flag would only be reset when tested by a special conditional branch instruction;

    3. By generating an "interrupt" (called here a "trap").

    4. By generating an "error value" number, and continuing computation.

To detect an error in case (1), the program would have to include a branch to test the flag after every operation, and doing so would increase the code's complexity substantially. Case (2) allows a block of instructions to be executed, and tested jointly for acceptable execution. Case (3) allows the flexibility of both, together with the option of writing a common "error handling" routine, which could even determine where in the program the error occurred, and "recover" from it (e.g., by setting the result of an arithmetic underflow to zero, and resuming the computation after the error-producing instruction). Case (4) was introduced for floating-point computation, and is helpful in allowing data-parallel computation to proceed without introducing separate computation paths for each datum. "Exceptions" in high-level languages represent the "interrupt" option in those languages, with some limitations.

An exception is an object (data-containing record) produced when an error is detected by hardware, or "thrown" explicitly by the program. The record can contain all the information that would be needed to "resume" execution after the exception-producing operation. When an exception is thrown, control passes immediately to an exception handling routine selected by rules of the language. Usually, each block or subroutine has the option of establishing an exception-handler for itself; the exception handler invoked is selected by: A. The type of exception, and B. The handler associated with the most-recently invoked block. That is, blocks are terminated until one is reached which contains an exception-handler for the particular "exception" that was thrown. In some languages, the exception-handler has the option of ending with "resume <expression>", which returns to the point after the exception was thrown, and (if in the middle of an expression) uses <expression> as the operation's result. E.g. Java:

Any method that throws an exception must declare that fact;

A method that uses an exception-throwing method must either declare that IT throws the same exception, or provide a handler for it;

Handlers (the form is "catch <Exception name> {}") cannot "resume", and cannot find out where the exception they handle came from.

Handlers are very useful for quickly terminating a deep nest of procedures, say in a compiler that detects a syntax error, and wants to abandon part of the parsing, and start skipping input until it locates, say, a ";". However, the current designs have some problems -- handlers may not have access to variables within the block that invoked them. Logically, they provide "sneak" exits from loops and other constructs, which may cause loop behavior to be hard to understand.

Coroutines

Coroutines are subroutines, with neither the caller nor the callee being "in charge". Instead, they allow program-controlled interleaving of instructions generated by both. Suppose A calls B. Then B wants to allow A to perform some more computation. B can "resume A", which then runs until it "resumes B". Then A can execute until it needs data from B, which might produce part of that data, and resume A, to examine or compute with the part produced so far. Coroutines have been exploited in the past in compilers, where the "parser" asks the "lexer" to run until the lexer has to stop (say at end of line). The lexer then resumes the parser to process that line's data, and is itself resumed to continue reading input characters. The text also shows an example of a tree-comparison problem solved logically by coroutines. Their advantage is that the cooperative behavior allows the "high-level" program to terminate the computation early, before the companion routine "completes" its assigned task. I have also used them to simulate parallel computation, when I want to build my own control over the task scheduling process.

As an interesting exercise, the text shows how coroutines can be simulated in C, using C's "setjmp()" and "longjmp()" library procedures. These procedures are intended for use in setting exception-handler routines. However, they have the property that they create concrete realizations of a "stopped" task -- an instruction counter, along with a variable reference context is stored when a setjmp occurs, and is resumed when a longjmp to the saved item is performed. The longjmp(Buf, Return) causes the setjmp(Buf) to return (again), this time returning value Return, instead of the 0 setjmp(Buf) returns when it is called.

CLU Iterators

Iterators in CLU look like ordinary procedures. However, they produce a sequence of values, rather than just one. Each time an iterator executes a yield <value> statement, the iterator returns <value>. When it is called again, the iterator picks up its computation after the yield, so it can compute the next value to return. In CLU, when the iterator finishes, the controlling for loop in which it is being called also terminates.

Java also provides the functionality of iterators. A Collection object in Java can produce an iterator object IT, with methods next(), hasNext(), and remove(). Repeatedly calling next() until hasNext() returns false steps through the elements of the collection. This seems to provide the essential features of a CLU iterator. It also appears that no special internal mechanism is needed to implement Java Iterators -- each iterator maintains its own "state" in it private variables, and its methods can at any time test and modify that state.

Continuations

A "continuation" is a parameter (descriptor or pointer) which represents "the remainder of the computation to be performed". The language Io uses continuations, together with a goto which passes parameters, as the sole control structure. Some syntactic fudging let you think of such goto's as ordinary procedures:

declare writeTwice: -> N; Continuation;

Write N; Write N; Continuation

writeTwice 7;

Write 6;

terminate.

writeTwice is declared to accept N, and Continuation as parameters. The "call" on writeTwice performs a goto to its declaration, which, which after writing N twice, "calls" the Continuation. In fact, the actual parameter corresponding to Continuation is
"Write 6; terminate."

Continuations of a sort are also present in LISP, but are not popular in programming languages -- the text claims that the examples are hard to understand without carefully tracing the computation.

C Continuations

The "setjmp(Buf)" operation acts as a form of "continuation" in C. On call, it takes a snapshot of the current environment, and places it into data structure Buf. A subsequent "longjmp(Buf, ReturnValue)" causes the original "setjmp(Buf)" to return again. The first return from setjmp() returns 0, while subsequent returns via "longjmp()" return the ReturnValue instead. A mechanism like this allows the "concretization" of a "program in operation", allowing this conceptual object to be stored, copied, and "executed" under full program control. This forms the basis for the implementation of other control structures, like co-routines, in C.

General comments on control structures

    1. Exceptions have simplicity of expression, address a common problem, and are easy to understand and to implement. Thus they appear in Java, Ada, PL/I, and other languages.

    2. Coroutines add some functionality (they define a form of parallelism), but can be confusing. Coroutines are not easy to reason about, compared to functions., and they require that each object has its own stack, making implementations more complex. Although they allow "iterators" to be implemented, we have seen that objects allow exactly the same functionality.

    3. Continuations are powerful and elegant, but very confusing to use.