CS61A Week 1 Summary TA: Evan Temporary Office Hours: M 9:10-11:10am at the (h50) lab. 1. Parenthesis ALWAYS mean something * mostly: "do something" (call a procedure) So don't do things like (+ (1) (2)) ;; BAD! What's the error? "Bad function: 1" 2. You can QUOTE things 'asdf => asdf '(1 2 3) => (1 2 3) '(+ 2 3) => (+ 2 3) and by the way, 'asdf is shorthand for (quote asdf) Quoting can be confusing in some cases... For instance, if '(+ 2 3) => (+ 2 3) then how do we get 5 from it? You might be tempted to try ( '(+ 2 3) ), and nope, it doesn't work! Answer? You can't (yet). 3. What does the parenthesis REALLY mean? First, remember the terminology: * EXPRESSION - what i type into STk (an evaluator) * VALUE - what STk spits back out * EVALUATION - the act of cranking out a VALUE from an EXPRESSION +--------------------------------------------------------------------------------+ | EXTREMELY IMPORTANT! | +--------------------------------------------------------------------------------+ | The USUAL RULE for parenthesis: | | 1. EVALUATE every SUB-EXPRESSION (what's grouped inside the parenthesis) | | 2. CALL the PROCEDURE (value from first sub-expression) | | on the ARGUMENTS (values from the other sub-expressions) | +--------------------------------------------------------------------------------+ Example: EXPRESSION: (+ (+ 2 3) 5) SUB-EXPRESSIONS: +, (+ 2 3), 5 1. + => #[the plus procedure] (+ 2 3) => 5 5 => 5 2. CALL #[the plus procedure] on 5 and 5: 10 * But there are things called SPECIAL FORMS that break this rule! For instance... (if (= 2 2) 'yes 'no) evaluates (= 2 2) and EITHER 'yes OR 'no BUT NOT BOTH! (define x (+ 2 3)) evaluates (+ 2 3) but NOT the subexpression x (define (square x) (* x x)) does not evaluate the subexpressions (square x) or (* x x) (cond ( (= x 0) 1 ) ( (= x 1) 2 ) ( (= x 2) 0 ) ( else -1 ) ) ^ ^ `------------' these parenthesis are merely for GROUPING and remember that cond may not evaluate everything. also, the "else" is not evaluated. It's just a placeholder. Other special forms: and, or, let 4. By the way.. what is TRUE and what is FALSE? #f is false. Anything else is true! (if 1 'yes 'no) => 'yes ;; 1 => 1 (if (= 0 1) 'yes 'no) => 'no ;; (= 0 1) => #f 5. What is this "okay" I see sometimes? okay appears as a default value (remember, every expression in Scheme evaluates to something). For instance, okay appears after - loading a file - evaluating conditionals (if/cond) that lack an else clause (which you should NEVER do until weeks later...) 6. Programming with Recursion. THIS IS CRITICAL FOR SURVIVING THE COURSE! Here's an attempt at a gentle introduction to how to think about recursion. I'm going to try to brainwash you with the following: - The sum of the numbers in () is 0 - The sum of the numbers in (1 2 3) is 1 plus the sum of the numbers in (2 3) - The sum of the numbers in (1 2 3) is also 3 plus the sum of the numbers in (1 2) - (sum S) <--> (+ (first S) (sum (bf S))) if S is not empty - (define (sum S) (if (empty? S) 0 (+ (first S) (sum (bf S))))) - What is a sentence? A sentence is either empty () or it's a word joined with another sentence. - Definition of factorial: 0! = 1. n! = n * (n-1)! Here's the trick to recursion. Suppose you are trying to figure out how to (remove-dupls S) where S is a sentence. Just pretend for a moment that remove-dupls already works, but only for sentences that are SHORTER than S. The question is, can you use this to your advantage? This turns out to be a BIG HELP. Take a look: I want to take (remove-dupls '(1 2 1 1 3 1)). Playing the pretend game, I can find (remove-dupls '(1 2 1 1 3)) => (1 2 3) or (remove-dupls '(1 1 1 3 1)) => (1 3), or (remove-dupls '(1 2 1 1 3)) => (1 2 3) ... I can call remove-dupls on any sentence consisting of all but one word of the sentence! In particular, let's just consider the butfirst. Then we just need to figure out what to do with the first word. The question is, should we include it or not? This is easy. We include it only if it is not a duplicate of something else in the sentence. In other words, we can use the member? predicate to test if the first word is in the butfirst of the original sentence! Here's what we have so far then: (define (remove-dupls S) (if (member? (first S) (bf S)) (remove-dupls (bf S)) ;; do not include first word (se (first S) (remove-dupls (bf S))))) ;; include the first word Unfortunately, this won't work. But the good news is, the hard part is done! Just look: we have here a procedure that calls itself on a smaller part of the sentence. That will in turn call the procedure on yet another smaller part, and so on. When do we stop? This is called the BASE CASE, and in this case, the simplest sentence is the empty sentence. So let's add this case in. (define (remove-dupls S) (cond ((empty? S) '()) ;; nothing to do if sentence is empty ((member? (first S) (bf S)) (remove-dupls (bf S))) (else (se (first S) (remove-dupls (bf S)))))) This is the final answer. The trick described above is very GENERAL. The hard part is figuring out how to play the pretend game. That part is also known as the RECURSIVE CASE. You will often hear us say the phrase "TRUST YOUR RECURSION". This is what we mean. Pretend the procedure (almost) works! A final word about BASE CASES: In general, you may have more than one BASE CASE. It depends on what the RECURSIVE CASE does. For instance, if it looks at the first AND second word of the sentence, then we need two base cases, one for the empty sentence, and one for a sentence with a single word in it (see the ordered? question on hw1). Still stuck? Try specific cases and look for a PATTERN!