The Boehm-Jacopini Theorem
and
Structured Programming

1. Only 3(*) rules of grammar are needed to combine any set of basic instructions into more complex ones:
   1. Sequence: Do this; then do that
   2. Selection (or choice): IF such-&-such is true,
                                          THEN do this
                                          ELSE do that

   3. Repetition (or looping): WHILE such-&-such is true
                                              DO this

   4. (optional; depends on the programming language)
      HALT

   5. (even more optional, but very useful)
      Procedure definition: Define new complex actions by name

   ---

   (*) Or maybe 4. (Or maybe 5.) (Or maybe 6! -- see below!)

   ---

2. Using flowcharts, the 3 rules of grammar (which are sometimes also called "control structures") can be illustrated like this:
   • (Note: It's too hard to draw flowcharts for a webpage, but hopefully what I show below will give you the flavor of it. If anyone wants to volunteer to give me some neat flowcharts I can include in this webpage, please let me know :-)

   ---

   1. Sequence (first do this; then do that): S1 ; S2

      |
      |
      V
      
      S1
      
      |
      |
      V
      
      S2
      
      |
      |
      V

      ---

   2. Selection (or Choice)

          (IF some statement Q is true,
              THEN do this
              ELSE do that)

          IF Q
              THEN S1
              ELSE S2
       

                      |
                      |
                      V
      (else if false)          (if true)
      --------------- Q? ---------------
      |                                |
      |                                |
      V                                V
      
      S2                               S1 
      
      |                                |
      |                                |
      V                                V

      ---

   3. Repetition (or Looping)

          (WHILE some statement Q is true, DO this)

          WHILE Q DO
              S

      |
      |
      |<---------------
      |               |
      |               |
      v  while true   |
      Q?------------> S
      |
      | when false
      |
      v
      

      These, together with naming, are the 4 basic features of Karel the Robot that we'll learn.

Recursion

1. 4 Lectures on Recursion by Robert C. Holte (for a course in Data Structures at the University of Ottawa).
   • Lectures 2 and 3 are especially relevant for CSE 111

2. Recursion, from the Wikipedia.
   • I don't normally trust the Wikipedia, but this article is pretty good.

3. Recursion, from the Free Dictionary.
   • Another source not to be trusted in general, but OK in this case.

4. Primitive recursive function, from the Free Dictionary
   • Much more technical than the previous websites.

1. Boehm, Corrado, & Jacopini, Giuseppe (1966), "Flow Diagrams, Turing Machines, and Languages with only Two Formation Rules", Communications of the ACM 9(5): 366-371.
   Abstract: This paper contains a proof that every program with gotos can be transformed into a semantically equivalent program without goto. A transformation algorithm is given.
   • For a simplified proof sketch, see:
     Riley, David D., "Boehm-Jacopini Theorem" [PowerPoint]

   • A useful discussion, which suggested many of the items listed here, was on both the comp.theory and sci.math newsgroups in 2000:
     "Status of Bohm-Jacopini Theorem"

2. Cooper, David C. (1967), "Böhm and Jacopini's Reduction of Flow Charts" (Letter to the Editor), Communications of the ACM 10(8) (August): 463,473.

3. * Dijkstra, Edsger W. (1968), "Go To Statement Considered Harmful" (Letter to the Editor), Communications of the ACM 11(3) (March): 147-148.

4. Ashcroft, Edward A.; & Manna, Zohar (1971), "The Translation of "go to" Programs to "while" Programs" Report CS-TR-71-188 (Stanford, CA: Stanford University Department of Computer Science).
   • Abstract: In this paper we show that every flowchart program can be written without go to statements by using while statements. The main idea is to introduce new variables to preserve the values of certain variables at particular points in the program; or alternatively, to introduce special boolean variables to keep information about the course of the computation. The "while" programs produced yield the same final results as the original flowchart program but need not perform computations in exactly the same way. However, the new programs do preserve the "topology" of the original flowchart program, and are of the same order of efficiency. We also show that this cannot be done in general without adding variables.

5. *?? Peterson, W.W.; Kasami, T.; & Tokura, N. (1973), "On the Capabilities of While, Repeat, and Exit Statements", Communications of the ACM 16(8) (August): 503-512.

6. *? Wirth, Niklaus (1974), "On the Composition of Well-Structured Programs", ACM Computing Surveys 6(4) (December): 247-259.
   • A good discussion of stepwise refinement.

7. * Knuth, Donald E. (1974), "Structured Programming with go to Statements", ACM Computing Surveys 6(4) (December): 261-301.
   • PDF
   • A wonderful (and wonderfully written) paper; should be required reading for all computer science or computer engineering students!

8. DeMillo, Richard A.; Eisenstat, Stanley; & Lipton, Richard J. (1980), "Space-Time Trade-Offs in Structured Programming: An Improved Combinatorial Embedding Theorem", Journal of the ACM 27(1) (January): 123-127.

9. * Harel, David (1980), "On Folk Theorems", Communications of the ACM 23(7) (July): 379-389.
   • A discussion of the history of the Boehm-Jacopini Theorem: What did they really prove, and who really proved it first?

10. *? Mills, Harlan D.; Basili, Victor R.; Gannon, John D.; & Hamlet, Richard G. (1989), "Mathematical Principles for a First Course in Software Engineering", IEEE Transactions on Software Engineering 15(5) (May): 550-559.

11. * Hayes, Brian (2003), "The Post-OOP Paradigm", American Scientist 91(2) (March-April): 106-110. [PDF] [html]
    • Abstract: Every generation has to reinvent the practice of computer programming. In the 1950s the key innovations were programming languages such as Fortran and Lisp. The 1960s and '70s saw a crusade to root out "spaghetti code" and replace it with "structured programming." Since the 1980s software development has been dominated by a methodology known as object-oriented programming, or OOP. Now there are signs that OOP may be running out of oomph, and discontented programmers are once again casting about for the next big idea. It's time to look at what might await us in the post-OOP era (apart from an unfortunate acronym).