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