Computer Sciences Dept.

Program Inversions to Reorder Code

Raphael Finkel

Different languages provide control structures with different kinds of flexibility. For example, CLU iterators and SIMULA classes allow control to be suspended in the middle, to be resumed later. Other languages, like ALPHARD and PASCAL, do not have such a facility. A technique called inversion is presented in some generality. It brings statements inside loops to positions outside those loops. It often possible to invert code that employs one set of control structures to create code that does not make use of those features. Although inversion works when the termination test is not the first step of the loop, statements between the loop entry and the termination test cannot brought outside the loop. Two examples are given to demonstrate inversion: Two programs, in CLU and ALPHARD, that generate all binary trees on n nodes, and two SIMULA programs that generate all partitions the integer n.

Download this report (PDF)

Return to tech report index

Computer Science | UW Home