"untying knuth's knots: how to restructure spaghetti code?" Code Answer

i sketched an algorithm for op earlier at https:///a/36661381/120163

found a better paper that discusses how to generate structured code while preserving the original control flow graph exactly:

w.d maurer, "generalized structured programs and loop trees", science of computer programming, 2007

i followed that procedure (on paper, hope i did it right, looks ok at 2:40 am). his basic trick is to find strongly connected regions (cycles in the code); these will become loops; he then breaks that cycle by deleting an edge; this eventually becomes a loop backlink (restored when he is complete). the process is repeated until no more cycles can be found; what is left is essentially a structured program with identified loops. it is tricky to do this right; you really need an automated procedure. your bit of code, although small, is still pretty nasty :-}

i cheated in one place. maurer insists that forward gotos are ok, even into the middle of loop. if you buy that, then you can preserve the cfg exactly. if not, you have to handle the case where a loop has two or more entry points; your algorithm has such a loop. i solved the problem by coding the loop, and coding a loop-tail-end-fragment equivalent that acts like the first iteration of jump-into-the-middle, which is followed by the loop itself.

my notation is a little funny: most languages don't have "block{...}" constructs. [the one i code in (see bio) does]. think of this as being an "execute one iteration" loop :-} i assume that blocks/loops have loop exits and loop continues. if you dont have these, you can simulate them with sufficient quantity of just block{ ... } and exit_block@n.

edit after accepted: in the light of day, i didn't do it right, i left out the of the while loop@3. i've patched that; the need for the block construct now goes away because i can exit the while loop@3 to achieve the same affect. actually, the code reads a little better.

i left your numeric labels in, even where they aren't needed, for easier reference.

//algorithm x;
1:
initialize();
2:
while (true) {
   enter_level(k);
   3: 
   while (true) {
      set(a[k],q);
      if (test() == ok) {
         if (k != n) exit_while@3;
         visit();
         decrease(k); // replicate logic at 6 to avoid jumping into middle of 5 loop
         if (k==0) return;
         set(p,u_k);
      }
      5:
      while (true) {
         increasev2(a[k]);
         if (q != 0) continue_while@3;
         6:
         decrease(k);
         if (k==0) return;
         set(p,u_k);
      } // while(true)@5
  } // while(true)@3
  4:
  increase(k);
} // while(true)@2

unlike most other answers i've seen so far, this runs at the same speed as the original (no extra flags or flag checks).

@hatchet's answer is interesting; a) it is equally fast, b) he chose to handle the two entry loop by the same technique, but he chose the "other entry" as the loop top. he did something similar with the "enter_level(k)" operation at label 2.

it is interesting that all this structuring doesn't seem to help readability of this code one bit. makes one wonder about the whole point of "structured programs". maybe well-designed spaghetti isn't so bad :-}