CSC302 2011S, Class 28: Goto Considered Harmful

Overview:
* Context.
* Dijkstra's Famous Letter.
* Permutation with Repetitions.

Admin:
* Missing, Unexcused: AC, DG
* Missing, Excused: AH, AT, DV
* Are there questions on the exam?
  * For the writing part, what languages should we restrict our
    suggestions to?  10 languages: 7L7W + Scheme,C,Java
  * Is there a dropbox yet?  Yes.
* Reading for Wednesday: Stuff on the Call Stack
  * Wikipedia on Call Stack
  * Encyclopedia of CS on Activation Records
* Psychologist hiring
* EC for either of Tuesday's Town-Hall Meetings on the Forum [academic]
* EC for Thursday's Convocation on Intellectual Property [academic]
* EC for Thursday's CS Extra [academic]
* EC for Friday's CS Table [academic]
* EC for Fresh Flutes on Thursday [peer]

Today's readings: Two papers having to do with the goto statement.
* Context: Late 1960's
  * High level languages had existed for about ten years
  * People were just figuring things out
    * Dijkstra cites: if statement, record, conditional statement
  * Challenges:
    * Efficient compiled code and efficient programmer time
    * Writing good code: Maintenance, debugging
    * How do we know that our programs are correct?
  * Just thinking about things like: "How do we implement recursion?"

Dijkstra's paper
* Audience
  * First friends
  * Then Academic and professional computing community - Published in 
    Communication of ACM
* Claim
  * There are alternatives to goto
  * Goto invites you to make a mess of your code
  * Programs should be written without goto because goto-ridden programs
    are impossible (or at least very difficult) to analyze
* Evidence
  * Proof by citation that you *can* do without gotos
  * Statement that it's harder to trace where the program was and will be
    if you have gotos
  * Proof by example: "Consider the problem of counting the number of
    people in a room ..."
* Opinion

To prove a program correct, we need to know all the ways in which you
can reach a particular point of the control flow.
* By "point in the program", we mean two things
  * Where it is in the static text
  * Where it is in the dynamic execution

E.g.,
  read (x);
  x := max (x, 0);
L1:
  x := 1 + x;
  // x must be positive - safe to take square root, safe to declare an
  // array with that size, ...

* If this is all there is to our program, we can guarantee that
  x is positive at the point I said it was.
* If the program can have gotos, there is *nothing* we can guarantee
  about x.
  x := -3;
  goto L1;

while (TEST)
{
  ...
}
// I know that !TEST

while (x < 0)
{
}
// I know that X is non-negative

* Can you explain the "count the number of people in the room example"?
* Program goal: Let N be the number of people in the room
  N := 0;
  // N is the number of people in the room
  while (!done)
    {
      // N is the number of people in the room
      if (someone_just_entered())
        {
          // N is one less than the number of people in the room
          N := N+1;
          // N is the number of people in the room
        }
      // N is the number of people in the room
    }
  // N is the number of people in the room
* Note: "Goto Statement Considered Harmful" appears in Yourden's "Classics
  of Software Engineering"

"If Goto makes things messy, why did it take so long to eliminate?"
* Change of goals: From fast code that gets the job done to provable code
* Opponents were not outspoken enough
  * Opponents were obnoxious
* People still thinking in terms of the underlying machine, and few
  architectures provide a while loop as a machine-code instruction
  * While loops are still rare

Permutation with repetitions
* perm (a, n, last)
  n is an integer
  a is an array of integers
  last is a boolean
  all are mutable
* What is the purpose of the code?
  "to give all the permutations of an array in reverse lexicographic order"
  "to give you the *next* permutation in a sequence of permutations of 
   some starting array, with the permutations given in reverse lexicographic
   order"
* What are the parameters?
  n is an integer - the size of the array
  a is an array of integers
  last is a boolean - a return value that tells you whether or not we've
  computed all of the permutations
* What are the preconditions?
  * The elements of a have to be in descending order on *the first call*
  * last should be true on the first call
* What are the postconditions?
  * The permutation returned is new unless last is true
  * If the permutation returned is new, last is false

Implementation?  How would you implement this procedure?
* With lots of gotos

Sam's permutation algorithm:
 * Swap first element with each of the other N-1 elements
 * Recurse on the N-1 elements