comp210 lectures, 98-spring, ian barland 98.Jan.21 (lect #4) How to Design Programs (which handle lists) Book: chapt 1-4. Today: chapt 7. Recall the solarSysWeight program: (solarSysWeight 220 'mars) = 24.2 How to write it? (We already have planetWeight). Answer: (define solarSysWeight (lambda (ew pn) (planetWeight ew (planetMass pn)))) Okay, we haven't written planetMass yet, but we trust that we could, and it works. (It's a big cond.) Note this minor leap of faith. Okay, on to the main part of lecture. We will write a program dealing with lists of symbols. Example: contains-mary 1. Recall defn of List-Of-Symbols: a. , or b. 3. Program template (follows from data defn) a. case analysis b. data extraction c. natural recursion 2. Description & Examples contract (signature), examples, header (formal params) 4. Fill in the template 5. Test cases (This is in Figure 8 and Figure 2.) Another example: add list-of-numbers Expressions are: 1. values (numbers, bools, symbols, lambda expressions, lists) 2. placeholders 3. function application (exp0 exp1 exp2 ... expn) 4. Special forms: define, lambda, if, cond ---- ... ---- insert, sort (as an example of top-down design) ---- 98.feb.02 more-interesting data defns, continued. We assume (define-struct posn (x y)) Shapes: A Shape is - make-circ ... - make-rect ... - make-line ... Template. Write area. Q: how would you write a function like overlap?, which takes in two Shapes? ---- 98.feb.04 Data Def'ns with two recursions: - family tree picture - family tree data defn - family tree template - functions: size, is-descendent-of Note: these two functions *include* the person as their own ancestor Use overheads, overlapped to emphasize template re-use ---- 98.feb.06 We've seen how family-tree functions are easy, if you follow template. It suggests for you, that the answer for a person is combined from the answers for mother, father (and self). [put up overhead of descended-from-Betty?] Now, another question: (hint: template will guide you!) ;; path-to-Betty : FamTree --> list-of-symbols ;; Returns null if there is no path to 'betty ;; Otherwise returns a list of {'mothers 'fathers} and then ending in 'betty ;; Example: if x is somebody whose maternal grandmother is 'betty, then maybe ;; (path-to-betty x) = (list 'mothers 'mothers 'betty) ;; (define path-to-Betty (lambda (a-ftree) (cond [ (symbol? a-ftree) null ] [ (child? a-ftree) (cond [(eq? 'betty (child-name a-ftree)) (list 'betty) ] [(cons? (path-to-Betty (child-mother a-ftree))) (cons 'mother (path-to-Betty (child-mother a-ftree)))] [(cons? (path-to-Betty (child-mother a-ftree))) (cons 'mother (path-to-Betty (child-mother a-ftree)))] [else null]) ]))) That was chpt 16. Here is chpt 18 (called 17 in handout). Okay, let's look at trees going in the other direction: (define-struct parent (kids eyes birth)) where kids is a list-of-children is - null - (cons p loc) where p is parent, loc is list-of-children [picture] ---- Announce: test on ... Together, we write size, for parents: Now, write ancestor-of-adam. (What would the analog of path-to-betty be?) Arguments of multiple complex types: Shape - interesect (the template only). Two lists: interleave. Two natNums: >, only using recursion, if, zero?, positive?. append, nth-car, nth-cdr ---- [Test will be a week from friday/weekend] accumulator: index-of [bad example -- accum not needed if you accept the same sub-comp 2x] [A better example?:] ;; bounced-a-check?: lon --> bool ;; given a list of bank transaction and an initial bank balance, ;; tell whether a check might bounce. ;; (A positive transaction means a deposit.) ;; (define bounced-a-check (lambda (transactions) (if (null? transactions) (negative? bal) (bounced-a-check (+ bal (first transcation)) (rest transaction))))) ; Why doesn't this work? This only looks a the final balance. ; Add (or (negative? bal) ...) ; (But then this doesn't seem tail-esque.... add a clause ; that if balance > 100000, then doesn't count as bounced???) OR ;; lucky-streak?s ;; Take a list of {'head,'tails}, and return a list ;; of booleans, which tells at each step have you seen more heads ;; than tails ;; ;; lucky-helper: list-of-head/tails x number --> list-of-bool ;; tosses is a list of head/tails; head-count is how many heads prev. seen ;; (define lucky-helper (lambda (tosses head-count) (if (null? tosses) null (cons (> (if (eq? (car tosses) 'hd) (add1 headcount) (sub1 headcount)) 0) (lucky-helper (rest tosses) (if (eq? (car tosses) 'hd) (add1 headcount) (sub1 headcount))))))) This repetition can be used to motivate local. (But not a *good* motivator?) product [they write] reverse: to think about -- how (reverse (list 'a 'b 'c)) hand-evals Note that in a hand-eval, you could type it literally into drScheme, and it'd evaluate as a bunch of lines and "=". If you notice a change in any of the values, that's your mistake. ---- 98.feb.13 quickly do hand-eval of revrse: note the *tail recursion* Something similar to index-of: ; replace-w-index: sym,los -> los ; replace every occurrence with sym with its index. ; (define replace-w-index-helper (lambda (sym los position) (if (null? los) null (cons (if (eq? sym (first los)) position sym) (replace-w-index-helper sym (rest los) (add1 position)))))) Use transparency: (define path-to-betty (lambda (a-ftree) (cond [(eq? 'unknown a-ftree) null] [(eq? 'betty (child-name a-ftree)) (list 'betty)] [(cons? (path-to-betty (child-mother a-ftree))) (cons 'mothers (path-to-betty (child-mother a-ftree)))] [ ...same with father... ] [else null]))) Note the repetition (let's consider just the maternal side): we check the mother's side twice. But each of these two checks looks at the grandmother twice: so that's four times. But each of those four checks of grandma checks great-grandma twice: that's eight times. my nth-mother is checked 2^n times! This is perhaps the most important/useful use of local. Of course, can avoid repetition with local: ... Syntax of local: (local [(define ph1 exp1)...(define phn expn)] body) Semantics of local (Law of Scheme): ...top-level definitions.. (local [defs] body) becomes: ...top-level definitions.. ...defs... body Pragmatics of local: (1) To avoid re-computation! (2) can avoid re-mentioning the static argument. (3) give names to individual parts of a computation. (4) want to hide the name of helper functions. ;; An accumulator version: ;; (define index-of#3 (local [(define helper (lambda (sym los index-so-far) (cond [(null? los) #f] [(eq? sym (car los)) (add1 index-so-far)] [else (helper sym (cdr los) (add1 index-so-far))])))] (lambda (a-sym a-los) (helper a-sym a-los 0)))) ---- feb.18 (wed.) We saw using local to hid the name of index-of-helper. Note that we could also use local to name (add1 index-so-far), avoiding re-computation. Is this extremely helpful? Not particularly. Two reasons -- its a quick function, and only called once per branch. But still might make things clearer: Pragmatic#3: give names to individual parts of functions But notice how the arg "sym" to helper never changes; it might as well be top-level defined. Can we modify so that we don't repeatedly pass it along? ;; An accumulator version: ;; (define index-of#4 (lambda (a-sym a-los) (local [(define helper (lambda (sym los index-so-far) (cond [(null? los) #f] [(eq? sym (car los)) (add1 index-so-far)] [else (helper sym (cdr los) (add1 index-so-far))])))] (helper a-sym a-los 0)))) Pragmatic#4: factor out unchanging arguments. Note that we could have call the argument sym instead of a-sym. When multiple placeholders with same name, ... Each placeholder has a binding occurence (where it gets a value), and a scope (where it knows that value). Scope of a lambda-argument: the function body. Scope of top-level define: everywhere. Scope of local define: the local body (achieved by re-naming). Scopes have holes in them! (define z 17) (local [(define z 118) (define confusion (lambda (y z) (+ y z)))] (confusion z 5)))) Now wrap the above local in a lambda(z); evaluate it at 9. ---- feb.20 generative recursion: hi-lo ---- feb.23 generative recursion: paths in a graph (DFS) picture of graph; directed graph; edge; node (houston, chicago, la, slc, dc, nyc) (define-struct city (name nbhrs)) (define big-apple ('nyc (list 'dc 'chicago))) ... (define all-cities (list big-apple ...)) ; You must yourself write a function which, given a city-name, ; can look up the city. (define (path-from src dest) (if (eq? (city-name src) (city-name dest)) null (local [(define subpath (path-from-any (city-nbhrs src) dest))] (if (cons? subpath) (cons src subpath) #f)))) (define (path-from-any src-name-list dest) ... But what about cycles?! Add an accumulator: visited [ There are two optimizations here. First, when you recur, Second note that any searching done by recursive calls is forgotten. If we could "mark" visited cities, that'd be fine. Short of that, we could have the functions return not only the answer, but a list of failed-cities searched. ] ---- feb.25 Announcments: test back next time; how many copies of notes? Here's an equivalent version of mergesort (top-down): (define (mergesort lon) (if (length-zero-or-one? lon) lon (merge (mergesort (first-half lon)) (mergesort (first-half lon))))) "Divide and conquer" To think about: why is this equivalent to the hw version? (Btw, this version is generative-recursive.) (define (qsort nums) (cond [(null? nums) null] [else (append (qsort (collect-lessers (first nums) nums) (collect-equals (first nums) nums) (qsort (collect-greaters (first nums) nums))))])) This calls three functions -- collect-{>,=,<} which each traverse the list. Exercise: write partition, which takes a list and a number, and returns a lsit-of-three-lists. How would you call that function only once, instead of three times? [If I write this on the board, then the above qsort could have used local in the first place.] (collect ; Could write a function ; ;;partition: lon,n -> list-of-three-lists-of-nums ; (define (partition nums threshold) ; (local [(define (help nums a b c) ; (if (null? nums) ; (list a b c) ; (cond [(> (first nums) threshold) ; (help (rest nums) a b (cons (first nums) c))] ; [(= (first nums) threshold) ; (help (rest nums) a (cons (first nums) b) c)] ; [(< (first nums) threshold) ; (help (rest nums) (cons (first nums) a) b c)])))] ; (help nums null null null))) Nagging question: what is different about mergesort, qsort is different, that you'd expect would be the same? The base-case condition: null? vs length-zero-or-one? Why is this? (The pitfalls of generative recursion) Okay, you-third of the class write collect-lessers, you-third write collect-equals, ... What do these look like? ... [include a small error, to fix later, *after* copy/pasting] To write these, you'd copy-and-paste, leaving you with three copies of the code to maintain. What if you find an error? What if you find a better way (say, you want to make ti tail-recursive)? Moral: Don't copy code! How could we avoid this? We could have written many different functions collect-greaterthan-eight, collect-greatherthan-nineteen, ... but of course we didn't; we passed in the desired number as an argument. When we applied the function, the box for "num" was replaced with the desired argument. Same thing here: we'll just pass in <, =, or > as an arguemnt, which will fill in the box when the function is applied. (define (collect-according-to compare reference) 0 ---- 98.mar.09 Functions are people too: coin-toss: list-of-{'head,'tail} --> num (define (coin-toss tosses) (cond [(null? tosses) 0] [else (if (head? (first tosses)) (add1 (coin-toss (rest tosses))) (sub1 (coin-toss (rest tosses))))])) We could re-write: ...(+ (coin-toss (rest tosses)) (if (head? (first tosses)) +1 -1)) But even more like the spirit of original ...((if (head? (first tosses)) add1 sub1) (coin-toss (rest tosses))) Now, reconsider what we did to combine collect-greater, collect-less, collect-even: We looked at three copies of code, circled the common part, and made it an arg. Recall collect-evens. Can we reduce the replication of code? (define (collect lyst keep?) (cond [(null? lyst) null] [(keep? (first lyst)) (cons (first lyst) (collect (rest lyst) keep?))] [else (collect (rest lyst) keep?)])) Now in merge-sort we have: (append (collect lon (lambda (n) (< n (first lon)))) ... Exercise: you have written less-than?. Now write greater-than?, equal-to?. child-older-than?, ... Aha, find the common part, and abstract! Exercise: Write less-than-5?. Write less-than-9?. Write (less-than? n) What are the contracts? Example: (define less9? (make-lesser 9)) (less9? 3) = ...(to be continued) ---- This is called *currying* <. < wants two arguments, but we only have one at the moment. So package one argument into the lambda-suitcase, and wait for the other one to get plugged in. Contract. Finally, make-predicate: (define make-predicate (lambda (comparer? reference) (lambda (n) (comparer? n reference))) (define (lesser-than n) (make-predicate < n)) We could also write: (define (child (child-year a) (child-year b))) We are *currying* <: ---- mar.11 higher-order (passing fns, map, curry) Consider sort-ascending, sort-descending; (show overhead with code, difference boxed.) And sort-alphabetically, sort-cities,... We now have n different versions. Hey, i want to use mergesort! Would have to go back and change numerous versions. (cut-and-paste n times means maintain n times the code.) Write a version sort-with: ... Hey, what is the contract of this function? (alpha,alpha-->bool),list-of-alpha --> list-of-alpha (where alpha is a "type variable" -- can stand for any type. A metaplaceholder.) Or even more generally, write make-sorter: (alpha,alpha-->bool) --> (list-of-alpha --> list-of-alpha) Hw: miss&cann Lab: ,miss&cann feb.27 template-fns (collect) mar.09 mar.11 mar.13 vectors, build-vector mar.16 set-struct! Aside: When to use lists vs structs: - when you have an unknown # of items - when you want to take an existing one and tack on another item When to count from zero instead of 1: - when counting continuous quantities: distance after t seconds; height of a building - from 1 with discrete quantities: # of people in room, # of floors in a building Note that there is sometimes conflict: european ground floor=0. This is great in that floor-k is 10k feet above ground; however a building with k floors is 10(k+1) ft tall. Chapter 0 of a book -- only if it contains background material. (What if there is background stat + background econ?) Okay okay, the main topic: CHANGING THE WORLD We had an assignment with bouncing balls; we moved a ball by creating a new ball which coincidentally was related to a previous one. This doesn't reflect how we real-world think about the problem... The language provides a remedy: (define-struct posn (x y)) (define profPlace (make-posn 3 5)) (set-posn-x profPlace 17) profPlace = (make-posn 17 5) This is very different from anything before! The rule of set-posn-x! is to evaluate each argument (first), then set the field appropriately. It does not return a value (or rather, it returns the useless value (void)). Note that the important thing about calling set-posn-x! is not the return value, but the *side-effect* of calling the function. So how can we write move-ball!: ball --> 'moved-it (define-struct ball (place velocity color name owner size ...)) Remember that the old way would be to take in a ball, and return a new one which had copies of most of the fields w/ a few changes. (define (move-ball! b) ... (set-posn-x! (ball-place b) (+ (posn-x (ball-place b)) (posn-x (ball-velocity b))) ;; uh-oh, how to change the y component? ;; and return a symbol Notice we need to call set-posn-x!, and also return a value. Use "begin", which takes in a list of expressions, evaluates each, and returns the value of the final expression. (This is pointless unless the non-last expressions engender side-effects.) Exercise: Write move-lob!: list-of-balls --> 'wahoo Hint: follow the template! (define (move-lob! lob) (cond [(null? lob) 'wahoo] [else (begin (move-ball! (frist lob)) (move-lob! (rest lob)))])) ---- mar.18 semantics of set--! If Elizabeth Windsor dyes her hair, what happens to the queen of england? She has purple hair too! (define-struct person (name hair-color birth-year eye-color hair-color height weight ...)) (define liz (make-person 'elizabeth 'brown 1926 ...)) (define queen-of-england liz) (set-person-hair-color liz 'purple) (person-hair-color queen-of-england) = 'purple How does this work? As it stands, the rules don't explain it: (set-person-haircolor liz 'purple) = (set-person-haircolor (make-person ...) 'purple) and how do we know that this make-person is the same liz, or just somebody with the same name? (we want to be able to model both) Here is the truth: Whenever you call make-person (or make- or vector or cons), what gets returned is not a box with those entries, but actually a *reference* to a box with those entries. A reference is a new type of value. We'll indicate references with hats: (define liz^ (make-person 'elizabeth 'brown 1926 ...)) (define liz liz^) Now, when we evaluate (define queen-of-england liz), here's what happens: (define queen-of-england liz) = (define queen-of-england liz^) ;; stop here; liz^ is a reference. (define liz^ (make-person 'elizabeth 'brown 1926 ...)) (define liz liz^) (set-person-haircolor! liz 'purple) = (set-person-haircolor! liz^ 'purple) = (void) ;; but we re-write the make-person associated with liz^ This seems like a bit of superficial syntactic wordplay, but it makes a huge difference. What if we'd said: (define liz (make-person ...)) (define queen-of-england (make-person ...)) (set-person-haircolor liz 'purple) Note that references are created whenever you make a structure, even if you don't associate a placeholder with it. Now, to make the difference clear or to confuse it hopelessly: "define" associates a placeholder with a value. You can modify such an association with "set!". (This is very different!) (define x 17) (set! x 23) ;; semantics: all further references to x use the value 23 Example: (define l 'common) ;; evaluate r.h. value; any knowledge of "x" is gone. (define q l) (set! l 'purple) q Compare with the previous example where q was queen-of-england, l was liz [finished 4min early!] ---- Comp210 lecture notes mar.20 circular structures, depth-first search with marking We now can answer some previous questions: When we had the family tree, and said (define gabi (make-child 'gabi 'unknown 'unknown)) (define chantelle (make-child 'chantelle gabi ...)) (define pierre (make-child 'chantelle gabi ...)) Are chantelle's mother and pierre's mother equal intensionally? extensionally? A hand-eval says they are intensionally equal, and we have indeed followed the guideline of one call to make-child for each actual human we model. What is an experiment you can do to confirm or deny? Also, recall the airline path-planning we did: (define-struct city (name nbhrs)) (define big-apple ('nyc (list 'dc 'chicago))) ... (define all-cities (list big-apple ...)) ; You must yourself write a function which, given a city-name, ; can look up the city: HERE, given "collect": ;; lookup: symbol --> city ;; Lookup targetname in all-cities ;; (The code presumes it occurs exactly once.) (define (lookup targetname) (first (collect all-cities (lambda (x) (eq? (city-name x) targetname))))) What if we had wanted to have nbhrs be a list of cities, rather than a list of names-of-cities? (I mean, that is more natural: the nbhrs are cities.) Before last week, we couldn't have done this, in cases of cycles: suppose houston was connected to chicago and also vice-versa. Then we have to make-city for chicagto before we can make-city houston (since make-city houston needs chicago as part of its nbhrs), and similarly we need to make-city houston before we can make-city chicago. How can we do this now, that we know about mutating structures? (define theWindyCity (make-city 'chicago null)) (define ricesTown (make-city 'houston (list chicago))) (set-city-nbhrs theWindyCity (list ricesTown)) What if we want to have a sightseeing flight from chicago to itself? (set-city-nbhrs theWindyCity (cons theWindyCity (city-nbhrs theWindyCity))) What does drScheme print? Try it! (Other Schemes, and older versions of drScheme, went into an infinite loop.) What about handling loops in the path-from problem? Before, we added an accumulator "cities-seen". ;; path-from: city, city --> union(list-of-city, #f) (define (path-from src dest already-seen) (cond [(eq? (city-name src) (city-name dest)) (list src)] [(contains? src already-seen) #f] [else (local [(define subpath (path-from-any (city-nbhrs src) dest (cons src already-seen)))] (if (cons? subpath) (cons src subpath) #f)))) (define (path-from-any src-name-list dest already-seen) (cond [(null? src-name-list) #f] [else (local [(define aWay (path-from (lookup-city (first src-name-list)) dest already-seen))] (if (cons? apath) aWay (path-from-any (rest src-name-list) dest already-seen)))])) This contained a tragic amount of repeated computation: you'd calculate (path-from houston slc (...)), and conclude there was no path to slc via nyc. This recursive call would return #f, and you'd forget that there was no path from nyc to slc, and might later try that again. Such repeated-tries might yield results for other problems, but clearly not here. What can we do? ;; path-from: city, city --> union(list-of-city, #f) ;; Return either any path src to dest, or #f if none. ;; (define (path-from src dest) (cond [(eq? (city-name src) (city-name dest)) (list src)] [(city-visted? src) #f] [else (begin (set-city-visted?! #t) (local [(define subpath (path-from-any (city-nbhrs src) dest))] (if (cons? subpath) (cons src subpath) #f)))) ;; path-from-any: list-of-city, city --> union(list-of-city, #f) ;; Return either: any path from any city in src-list to dest, or #f if none. ;; (define (path-from-any src-list dest) (cond [(null? src-name-list) #f] [else (local [(define aWay (path-from (first src-name-list) dest already-seen))] (if (cons? apath) aWay (path-from-any (rest src-name-list) dest already-seen)))])) mar.20 circular structures, dfs with marking mar.25 loops + vectors; tail-recur mar.27 finish loops; 10min of JAM intro I: architecture, memory, cmds lab: emacs, while/fori=, Jam intro hw: jail cells, passwd obj, use jam simulator mar.23 set! for history and global state Uses of set! (1) keep history btwn function calls (2) keep state btwn function calls Examples: (1) history between calls: Consider the J-mart inventory. (define ir (name price color num)) (define (same-item ir1 ir2) (eq? (ir-name ir1) (ir-name ir2))) We can write a function (stock new-item): (define (stock new-item) (set! inventory-list (cons new-item inventory-list))) Or even better, we can : ;; stock: ir --> (void) ;; (define (stock new-item) (local [(define others (collect (lambda (ir) (same-item ir new-item)) inventory-list)) (define other (if (cons? others) (first others) 'no-other-record))] (if (ir? other) (set-ir-num others (+ (ir-num other) (ir-num new-item))) (set! inventory-list (cons new-item inventory-list))))) (2) (state) A random-number generator: (define seed 0) ;; return a pseudo-random int in [0,100) (define (rand) (begin (set! seed (next-num seed)) seed)) (define (next-num n) (remainder (+ 17 (* n 41)) 100)) 17, 14, 91, 48, 85, ... (NB if i change 41 to 43, i get 17,48,81,0,17,...) Of course, the limit 100 could be made more flexible: (define max-rand 100) How could we make it so ? mar.30 JAM II: opcodes; loops Recall from the end of two lectures ago, The JAM machine has a CPU, memory (a giant vector), and registers R0-R9 general purpose, special register PC. The four-stage step of JAM machine: Repeatedly (1) fetch the value mem[PC] (2) increment PC (3) decode the value as an instruction (4) execute the instruction. Okay, now we'll talk about some of the exact instructions. Refer to the reference sheet. There are a few general classes of instructions: - arithmetic (only works on registers) - memory (move between memory and registers) - control (modify PC) Let's take an example. Suppose in Scheme we have variables a,b, and we wanted the equivalent of (set! a (- a b)) ;; a <-- a - b (Alternate notation) For the JAM assembly version, we'll suppose that a is stored in memory location 456, and b in location 789. Hmmm, the only subtraction command is "Rx <-- Ry - Rz". This means that we need to move a and b from memory into registers. ;; R0 <-- mem[456]. A two-step process: (ldi 1 456) ; R1 <-- 456 (ld 0 1) ; R0 <-- mem[R1] ;; R5 <-- mem[789]. The same two-step. (ldi 6 789) (ld 5 6) ;; Now we can subtract! Put answer in R2. (sub 2 5 0) ; R2 <-- R5 - R0. ;; We did "a-b" (answer in R2), so now "a <-- R2", ;; i.e. "mem[456] <-- R2". Looking at the store command "st", ;; we need to have the value 456 sitting in a register. Is that so? ;; Fortuitously, yes. (st 2 1) ; mem[R1] <-- R2. (halt) So this is the program. Now we need to put it into memory, so that the JAM machines' 4-step program can get to it. We have seven instructions; we'll place those in, say, mem[4], mem[5], ..., mem[10]. But it turns out, memory can only hold numbers! We must refer to the sheet for the encoding. Consider "(ldi 1 456)". Reading of the sheet, we see that this is encoded as "+00045619"; store this value into mem[4] using the machine inspector. Similarly, "ld 0 1" is encoded as "??1?1060", eg 101060. Question: What is "(sub 2 5 0)" encoded as? Note how you have to use the insepector to load these numbers (instructions) into mem locations 4..10. Then, you must set the PC to 4, and execute. ---- apr.01 Scheme to Jam to C lab: Jam, C intro hw: Jam loops, simple C, C loops An Overhead slide, with the program from last time: ;;; (set! a (- a b)) ;;; a <-- a - b (Alternate notation) ;; We presume a is stored in memory location 456, and b in location 789. locat'n: Value ; Decoded ; Comment. mem[ 4]: 45619 ; (ldi 1 456) ; R1 <-- 456 Two-step for R0<--mem[456]: mem[ 5]: 101060 ; (ld 0 1) ; R0 <-- mem[R1] mem[ 6]: 78969 ; (ldi 6 789) ; R6 <-- 789 Two-step for R5<--mem[789]: mem[ 7]: 106560 ; (ld 5 6) ; R5 <-- mem[R6] mem[ 8]: 05220 ; (sub 2 5 0) ; R2 <-- R5 - R0. Subtract; put answer in R2. mem[ 9]: 101270 ; (st 2 1) ; mem[R1] <-- R2. R1 is still a's location. mem[10]: 321000 ; (halt) Note with ld, st: in "(ld 2 1)", R2 is the register which gets the value; R1 is the register which contains the *address* of the value. The actual values are "machine code". THe decoded instructions are "assembly code". It's tedious writing in machine code; much nicer to write in assembly, and then have a program to translate it. That's it first worked: somebody wrote an assembler, in machine code! Thereafter, you write in assembly, and give your english-like program text to the assembler, which translates it. (Actually, they probably wrote it in assembler, and then hand-evaluated to assemble their assembler into machine code.) We'll do a similar thing in lab: You'll write in C, and then an "compiler" will translate your C code to assembly code, which will then be assembled into machine code. (In drScheme, every time you hit "execute", this compiling happens.) We will see C soon, and in lab how to do the compiling (i.e. how to click the execute button.) C is "high-level assembly": it allows for variable names, for-loops, function calls. Here is an example which involves a loop. We want to store the values 0...49 in locations 100...149. (define vec (make-vector 50)) (define (fill i) (if (< i (vector-length vec)) (begin (vector-set! vec i i) (fill (add1 i))) (void))) In JAM-assembly: - Approach 1: have veci iterate 100,101,102,...149, and access mem[vec]. - Approach 2: set vec = 100; have i iterate 0,1,2,3,...,49, and store into mem[vec + i] We'll take approach 2; it parallels the Scheme (and C) approach. ;; We'll use memory locations 100 through 150 to store "vec". ;; First think about what placeholders we need. ;R0 i <-- 0 ;R1 len <-- 50 ;R2 vec <-- 100 ;R3 vec + i ;R4 uno <-- 1 ;R5 diff: ?? (ldi 0 0) (ldi 1 50) (ldi 2 100) (ldi 4 1) loop: (sub 5 1 0) ... ; is i < len ? (add 3 2 0) ; R3 <-- vec + i (st 0 3) (add 0 0 4) ; i <-- i + 1 (jmpi loop) done: (halt) Now go back and fill in the skipped line: blez 5 done Eleven instructions. Put them in memory 90..100. It works, but only because of luck! What if we set vec[i] to be i+1970? Lesson: be very careful! (Some machines have two memories -- prog & data) ---- apr.03 Exercise on your own: get rid of computing vec+i, and instead use the stx instruction. (stx 0 2 0) ;; mem[R2+R0] <-- R0 Cf Scheme and C: C has the contracts built-in.

Scheme, natural Recursion

(define size 50) (define nums (build-vector size (lambda (i) 17.3))) ;; max: int --> float ;; Given N, find the largest entry in nums[0]..nums[N]. ;; The natural recursion version. ;; (define (max N) (if (zero? N) (vector-ref nums 0) (local [(define max-of-rest (max (sub1 N))) (define nth (vector-ref nums N))] (if (> max-of-rest nth) max-of-rest nth)))) (max (sub1 size))

C, natural Recursion 

// max, the natural-recursion version.
//
#include 
const int size = 50;
double nums[size];

// max: Return the largest entry in nums[0]..nums[N].
//
double max( int N ) {
  if (N==0)
    return nums[0];
  else {
    int maxOfRest = max( N-1 );
    int nth = nums[N];
    if ( maxOfRest > nth )
      return maxOfRest;
    else
      return nth;
    }
  }

int main() {
  cout << max( size-1 );
  return 0;
  }

// Note: you must call a function "fill-up-nums()" to
// initialize the array.

Scheme, accumulator version 

(define size 50)
(define nums (make-vector 50 17))
(define (max N max-so-far)
  (if (>= N size)
      max-so-far
      (if (> nums[N] max-so-far)
          (max (add1 N) nums[N])
          (max (add1 N) max-so-far))))
(max 1 nums[0])

C, accumulator version 

#include 
const int size = 50;
int nums[size];

int max( int N, int maxSoFar ) {
  if (N >= size)
    return maxSoFar;
  else if (nums[N] > maxSoFar)
    return max( N+1, nums[N] );
  else
    return max( N+1, maxSoFar );
  }

int main() {
  cout << max( 1, nums[0] );
  return 0;
  }
Variables: - (define x 3) int x; // declare x = 3; // assign // OR int x = 3; // initialize Compare with the tail-recursion of Scheme: The tail-recursion changes the argument each time through. The assembly version assigns to i each time through. Tail-recursion can be implemented as a loop + (re)assign parameters! Exercise: Modify this, so that you compute the sum of ---- (define vec (make-vector 50)) (fori= 0 (lambda (i) (< i (vector-length vec))) add1 (lambda (i) (vector-set! vec i i))) ---- const int size = 50; int vec[] = new int[size]; int i; for ( i = 0; i < size; i = i + 1 ) { vec[i] = i; } ; Using the fori= construct: ;(fori= 0 ; (index-checker vec) ; add1 ; (lambda (i) (vector-set! vec i i))) apr.03 advanced Jam: stack apr.06 implementing Jam apr.08 exam2 review hw e.c.: lab: optional: arithmetic hw: assign project apr.13 (catchup) apr.15 multi-dim arrays scheme, C lab: C apr.17 object-oriented I apr.20 object-oriented II lab: timing apr.22 halting prob apr.24 summary Labs: arithmetic imprecision; timing qsort, msort, isort; optional topics: eval, program-as-data, shcme-in-scheme max: scheme-accum C-accum scheme-for C-for Jam-for The Scheme-accumulator version of max

Scheme, accumulator version 

;; max: int, double --> double
;; Return the largest value out of vec[i]...vec[size-1],max-so-far.
;; N.B. It is an error if vec does not have at least one element.
;;
(define (max i max-so-far)
  (if (>= i size)
      max-so-far
      (if (< max-so-far (vector-ref vec i))
          (max (add1 i) (vector-ref vec i))
          (max (add1 i) max-so-far))))

(max 1 (vector-ref vec 0))

C, accumulator version 

#include 
const int size = 50;
int nums[size];

int max( int N, int maxSoFar ) {
  if (N >= size)
    return maxSoFar;
  else if (nums[N] > maxSoFar)
    return max( N+1, nums[N] );
  else
    return max( N+1, maxSoFar );
  }

int main() {
  cout << max( 1, nums[0] );
  return 0;
  }

C, for-loop version 

//   max-for.cc
//   Compile this with "g++ -Wall max-for.cc".

#include 


const int size = 50;
double vec[size];


// max
// The "for" version in C.
//
double max( int i, double maxSoFar ) {
  if (i >= size) {
    return maxSoFar;
    }
  else if (maxSoFar < vec[i]) {
    return max( i+1, vec[i] );
    }
  else {
    return max( i+1, maxSoFar );
    }
    // N.B. In this case, the curly-bracces were optional,
    // since each if/else body had only one statement.
  }

int main() {
  cout << max( 1, vec[0] );
  return 0;
  }
;; max: . --> double ;; The Scheme fori= version. ;; Return the largest value out of vec[0]...vec[size-1] ;; N.B. It is an error if vec does not have at least one element. ;; (define (max) (local [(define max-so-far (vector-ref vec 0))] (begin (fori= 1 ; start (lambda (i) (>= i size)) ; stop? add1 ; next (lambda (i) ; body! (if (< max-so-far (vector-ref vec i)) (set! max-so-far (vector-ref vec i)) (void)))) max-so-far ; This is the 2nd stmt in the begin. ))) // The C-for version of max. // N.B. It is an error if vec does not have at least one element. // double max() { double maxSoFar = vec[0]; int i; for ( i = 1; i < size; i = i + 1 ) { if (maxSoFar < vec[i]) { maxSoFar = vec[i]; } } return maxSoFar; } ---- apr.08: tail-recursion to loops in JAM. JAM: vec <-- 100 i uno <-- 1 diff msf <-- ldx vec 0 i <-- 1 diff <-- size - i blez diff end ldx veci vec i diff <-- veci - msf blez diff endfor msf <-- veci endFor: i <-- i + 1 bri startFor end Notice now, how tail-recurion, in JAM, becomes "change the arguments (stored in registers), and do a jump". This is quick and easy. To think about: How would you translate function-call to JAM? Imagine I had a subroutine that location 5000, which took the sqrt of R0, and put the answer in R1 (trashing the other registers). How would you call it? What would happen at end of that routine? Would this work for recursive functions? -------- arrays: vectors were 1-dim (rowhouses); arrays are 2-dim (hotels). Example: - spatial dimensions: a map, where map[r][c] has the terrain-type of cell at row r, column c. Pixels. - time: is jail-cell i open at time t? jail[i][t] (suppose you want to remember for all time) - abstract: vector of scores in the class. array of scores in all classes (score[i][c] is score of student #i in class #c) array of scores in all classes in all semesters: score[i][c][s] ...of all schools... Conventionally, each dimension indexed 0...-1. Syntax in C: const int maxRows = 10, maxCols = 10; // useful constants double arr[maxRows][maxCols]; // A declaration: create the array in memory! ... // Fill arr with "0.0", except along main diag put "1.0" int r, c; for ( r = 0; r < maxRows; r = r + 1 ) { for ( c = 0; c < maxCols; c = c + 1 ) { if (r==c) arr[r][c] = 1.0; else arr[r][c] = 0.0; } } Note the nested loop: i is 0; j goes 0...maxCols. Then i is 1; j goes 0...maxRows. Syntax in Scheme: (array-ref arr r c), (array-set! arr r c val), (make-array r c init-val), (build-array r c init-fn) (array-num-rows arr), (array-num-cols arr) What would init-fn be for the identity matrix? Actually, these aren't built-in. How would you write them? A vector of vectors. ---- alluded to: %%% (define (for-vector vec body!) %%% (fori= 0 (lambda (i) (>= i (vector-length vec))) add1 body!)) (define (for-simple a b body!) (fori= a (lambda (i) (>= i b) add1 body!))) apr.15 (tax) (define map (make-array 10 10 'plains)) (define (erode world) (for-simple 0 (array-rows world) (lambda (r) (for-simple 0 (array-cols world) (lambda (c) (floodland r c)))))) (erode map) flood-land, which looks around a cell in matrix (count neighbors) In C, how would you write this? No symbols, ...but enumerated types. A Land is: - 'plains, 'forest, ... enum Land { plains, forest, mountains, swamp, island }; //... if ((map[2][3] == plains) && nextToIsland(2,3)) map[2][3] = swamp; . . . . typedef Land[2][3] World; In C, Structures: enum Color { white, green, red, black, blue }; ---- apr.17 (fri) struct InventoryRec { float cost; int numInStock; Color color; }; void printInventoryRec( InventoryRecord* ir ) { cout << "Cost is " << ir->cost << endl; } void discount( InventoryRec* ir, float p ) { ir->cost = ir->cost * p; } int main() { InventoryRec* itm = new InventoryRec; itm->cost = 9.3; itm->color = blue; cout << "It costs " << itm->cost << endl; printInventoryRecord( itm ); return 0; } Recursive structures: Cons cells. - - - - #include // for NULL #include struct Cons { int first; Cons* rest; }; Cons* makeCons( int car, Cons* cdr ) { Cons* c = new Cons; c->first = car; c->rest = cdr; return c; } void printList( Cons* c ) { if (c == NULL) cout << endl; else { cout << c->first << " "; printList( c->rest ); } } int main() { Cons* nums1, *nums2; nums1 = new Cons; nums1->first = 17; nums1->rest = NULL; nums2 = makeCons( 15, makeCons( 16, nums1 ) ); printList( nums2 ); } - - - - NOTE: our recursive idea that A List is - null, or - makeCons( kar, kdr ) is not part of the language! In fact, if a "null list" had been a structure (maybe all lists keep track of their own length), we'd have trouble distinguishing makeNulls from makeConss. What is going on here? A Cons* is a reference (signpost); a Cons is the real structure. (In Scheme you couldn't make this distinction; in C you can, and you must be careful not to confuse them.) Notice how discount actually changed the structure referred to; compare this with a function taking an int. Let's write sum: Don't forget templates! int sum( Cons* l ) { if (l == NULL) return 0; else return l->car + sum( l->cdr ); } You're not allowed to forget about program templates! ---- C structures: Under the hood or, The truth about splats and dots Recall how we use structures in C to get Scheme behavior: ...(example from prev. lecture) "ir->price" is shorthand for "(*ir).price" What does "*" mean? (a) In declarations: "InvRec *x" means that *x is an InvRec, and x is a pointer-to-InvRec (b) In executable statements: "x" refers to the (value of the) pointer, "*x" refers to the (value of the) int. Pictures of memory, when you make a struct: creating invRec, calling discount, makeInvRec. Note that in calling "z = 0.9; discount( ir, z )", any changes to "ir" do seem to be reflected, but changes to z aren't. Why? Because in JAM, when we call a function, the parameters are copied. This is "call-by-value". C lets you do smething Scheme didn't: declare a structure, instead of a reference-to-structure. (This complicates things; I suggest you only use pointers-to-structs.) invRec ir2; ir2->price = 99.99; float z = 0.9; discount2( ir2, z ); cout << ir2->price; // prints 99.99 Note that Scheme, and original C, has only call-by-value. Because we can pass references by value, sometimes we effect changes. This is a faux pass-by-reference; you can imagine a language where changes to parameters are *really* modifying the calling-variable (e.g., in discount2, modifying the second arg would change z.) But we can also fake this, using references. Some books call this pass-by-ref, but it's not really (just having pass-by-ref can't explain circular references, item in multiple lists, etc). Uses of pass-by-ref: when you want to return multiple values w/o struct. ---- apr.22 (wed.) Vectors in C: - vectors are represented as a poitner to the first element. const int sz = 5; int main() { int data[sz]; data[2] = 17; } Draw memory diagrams of what happens in this. Note that data[2] is translated to *(data+2). While the latter is still valid C, DO NOT USE IT! What about passing arrays? void print( int vec[] ) { for (int i = 0; i < sz; i++) cout << vec[i]; cout << endl; } Draw memory diagrams of what happens when main calls print(data). What if we were to assign to vec[2]? Notice that it changes, just like when structure-references are passed, even though we didn't use the "*" syntax at all. (an inconsistenC) What about returning arrays? Try: // WRONG int[] makeAndFillVec() { int retVec[sz]; for (int i=0; i < sz; i++) retVec[i] = 2*i; return retVec; } int main() { int data[]; data = makeAndFillVec(); print( data ); } Well, first a syntax problem: "int x[]" isn't a valid declaration; change them to "int* x" :-( But there is a much more serious problem: Draw memory diagrams. When we leave makeAndFillVec, local memory goes away, can get re-used. (Ex: data1 = makeAndFillVec(); data1[2]=17; data2 = makeAndFillVec(); You can see that data1[2] is no longer 17! data1 and data2 *happen* to poitn to same location.) Solution: In makeAndFillVec, don't declare the array as a local variable (never return address of a local variable). Instead, int* retVec; retVec = new int[sz]; This way retVec (the poitner) is a local var, but the actual array is long-lived, on the heap. Talk about exam. ---- 98.apr.25 (last day) Where have we been? Scheme - define, lambda, if, zero?, 0, add1 computation as an extension of algebra struct recursion -- mirror your input generative recursion accumulator recursion, loops side-effects: set-struct-field!, set!, print, read Assembly Jam, C Which is more powerful -- Scheme or JAM? In 1930's, people trying to formalize "computation" lambda calculus -- Church 1936 Turing Machine -- Turing 1936 recursive functions -- Go:del, Kleene 1936 deduction systems -- Post 1943 register machines (JAM) -- 1946 Church-Turing thesis: all notions of "computability" are the same! Can we compute anything we like? No: Comp212, comp482, comp450 comp314, comp421 (OS), comp430 (db) comp440 (ai) Comp311,Comp412 comp320, elec326 comp481 [ see matthias's last lecture; halting problem. ] (why "car" and "cdr"?) Why C is unsafe - lets you walk off end of array - can cast pointers - pointer arithmetic lets you access memory directly !! - too easy to erroneously return pointers to freed memory.