PLP: Lecture 21
Structured vs Unstructured flow
- unstructured control flow uses
goto
statement. Used in Fortran, causes spaghetti code - structured flow use only sequencing, selection, and iteration
Structured flow aims to avoid non-local branching. This occurs when you branch to label outside current subroutine. Requires unwinding the stack (deallocate stack frames, restore registers, etc.).
Continuations
Abstraction that captures a context where execution might continue. This is a generalization of non-local gotos that unwind the stack. Are first-class values in some languages, such as Scheme. Will return to this later.
Sequencing
Central to imperative programming. Generally implemented as a delimited list of statements wherever a statement is expected, e.g., between begin
and end
keywords. Not really present in functional languages.
Selection
Generally if-then-else
statement. Although condition is Boolean expression, need not store the value in a register- instead can generate jump code to do comparison and then branch.
Rather than testing each case sequentially, the case
statement may compute the address of the jump target. Can use:
- Jump table - T[expr] gives address to jump for that value of expression. Need an entry for every possible value.
- Sequential testing if # of values is small
- Hash table works well if possible range of
case
statement is large - Binary search
- Multiple lookup strategies
Iteration
Need iteration or recursion in order to be Turing complete!
Enumeration controlled loops: know ahead of time number of iterations to loop for b/c looping over a set.
Iterators - separate the way to enumerate objects from the loop control. Java has Iterator. Java also converts for-each
loop to an Iterator.
Logically controlled loops: execute until some condition is true.
Parallel loops
Computing sequential loops in parallel. OpenMP is a set of compiler directives (C, C++, FORTRAN) for parallelism. Iterations will be divided up between the available processors.
double Res[1000];
#pragma omp parallel for
for(int i = 0; i < 10000; ++i) {
Res[i] *= 2;
}