This outline is also available in PDF.
Held: Monday, January 29, 2007
Today we consider the basics of structured programming and the reasons
it supplanted goto-ridden programming.
- Thursday at noon: Summer research opportunities.
- Questions on HW2?
- Friday's reading is the same as Wednesday's, so no readings distributed today.
- Dijkstra's Famous Letter.
- Permutation with Repetitions.
Some of these notes come from Dijkstra's
What Led to (EWD1308). Available at
- Late 1960's; about a decade after the first major high-level
- Why did languages include go to statements?
- Part of the underlying Von Neumann architecture.
- At least initially, seemed like the obvious control structure.
(Non-recursive procedure call also available.)
- If control was based on go to statements, why were these languages
closer to the problem?
- Programmers didn't have to lay out memory for values and variables.
- Programmers didn't have to decompose formulae into individual
- Programmers didn't have to worry about temporaries in such
- Mnemonics for many key operations.
- Programmers didn't have to worry about data representation.
- But people were seeing problems writing larger programs
- As the previous reading tells us, many proto-software-engineers wanted
- A large community also wanted to be able to formally verify programs.
- The result: New control structures
- Conditionals of various forms (including case)
- Recursive functions
- Key idea of most of these control structures (usuaully implicit;
eventually explicit): One entry point, one exit point.
- Dijkstra, a few years earlier, had been working on parallel programming.
- Dijkstra, in some sense, was serving as (unasigned) spokesperson for
a much larger group.
- The original title of the article was
A Case Against Go to
- Structure of argument?
- What does he mean by
a (mixed) sequence of textual and/or dynamic
- What does he mean by
- Why would one care about indices or coordinates?
- What does he mean by the
number of people in the room exmaple?
- Possible counter arguments?
- What is the purpose of this algorithm?
- What distinguishes it from other algorithms for computing permutations?
- Are there other goals of the algorithm?
- Does it meet those goals?
- What are the arguments, the local variables, the
- What general purposes do they seem to serve?
- What's going on at L2?
- Why isn't the sequence of L4 and L5 represented as a loop?
L4: if a[i] = p then go to L2;
if a[i] < p then r := i;
L5: i := i-1;
go to L4;
- You will continue to explore these questions in HW2.