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