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;
}