CSC151 2007S, Class 05: Basics of Programming Language Design

Admin:
* Remember: If there are multiple readings, 
  then send a response for each one.
* Summer research talk tomorrow at noon.  Brown bag it.
* Questions on HW2 in the last ten-fifteen minutes of class.
* For Friday, pick one example for Hoare that involves code, 
  and explain what he is trying to indicate with that code.
  * Syntax of FORTRAN  DO 17 I = 1 10
  * Comparison of bad switch to elegant case statement
  * Assignment in Algol: x := y; vs. x := y+1;
  * Matrix multiplication
* Sam rants about 
  * People who use OCR
  * Students who can't parse bibliographic entries.
* Grammar check: 
  * Shibboleth of independent compilation,
  * Prolixity of Cobol - unneccessarily long or complex
* So, how many languages with a C-like syntax can we identify?
  Actionscript (Flash), AWK, C, C++, C#, Cshell, Java, Javascript, Perl, PHP (?)
  * Maybe: Ruby
* Warning!  Sam derailed by mail server upgrade and dead Church.
* Interesting summary of current usage: 
  http://www.cs.berkeley.edu/~flab/languages.html

Overview:
* Permutation with repetitions.
* Choosing a language.
* Key design criteria.
* Notes from the readings.

/PwR: The Interface/

perm(A, n, last)
  A is an array, ordered from greatest to least in the first call
    (when last is also true), otherwise not necessarily ordered,
    but unchanged from return value of previous call.
  n is an integer
  last is a boolean
Goal:
  Generate permutations of A.  Each call generates a new perm.
  n is number of elements  [FIXED]
  last should be set to true on first call.  last is set to
    false upon return if a new permutation has been generated.
    last is set to true upon return if no new perm has been
    generated.
Preconditions and postconditions:
  Implicit: n > 0
  Implicit: If last is false upon return, A is a *new* permutation
    of the original array.
  Implicit: By the time last is set to true upon return, every
    unique permutation has been generated.
  Stated: Permutations are generated in reverse lexicographic
    order.  [Not in Sam's or Stone's re-implementation]

What is the "with repetitions"? - When a number is repeated, we
  don't get all the permutations of the repeated number.

There is only one permutation of 5,5,5 vs. six of 3,2,1 vs three of 5,5,1

How would I implement this, or something similar?
* Recursively: Put each element in the last spot, and then permute
  first n-1 elements.
* Issue: requires a stack.
  * Generating one-at-a-time requires storing the stack.
  * This algorithm seems to do it without storing the stack (unless
    b provides a rep. of the stack)

Perm with Reps discussed on the whiteboard