CSE 111, Fall 2004

Great Idea III:

The Boehm-Jacopini Theorem
Structured Programming

(Click on the title above to do Google searches.)

Last Update: 22 November 2004

Note: NEW or UPDATED material is highlighted

Note to CSE 111 Students: The main usefulness of this webpage for you is the summary of this third Great Idea of Computer Science. Many of the references in the second half of the article might be too advanced for you to fully appreciate, but some of them (marked by an asterisk "*") might be interesting to read anyway.

Note to Other Readers: This page was created for the students in CSE 111, Great Ideas in Computer Science, so my statement of the Boehm-Jacopini Theorem is not phrased exactly the way that they phrased it. However, the references in the second half of the article, while not all directly related to the Theorem, are of some relevant interest to the general topic of structured programming.

Note to All Readers: All articles from publications of the ACM and most articles from the IEEE are available online under certain circumstances, one of which is using a ".buffalo.edu" computer. UB students: Log into Bison and access the journals from there.

  • III. Boehm & Jacopini's Insight.

    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)

      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

      2. Selection (or Choice)

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

            IF Q
                THEN S1
                ELSE S2

          (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

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

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

  • UPDATED Karel the Robot


    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.

  • Recommended Readings:

    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.

    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).

    Copyright © 2004 by William J. Rapaport (rapaport@cse.buffalo.edu)
    file: 111F04/greatidea3-2004-11-22.html