This preview shows page 1-2-3-4-5-6-7-50-51-52-53-54-55-56-101-102-103-104-105-106-107 out of 107 pages.
CS 61A Lecture Notes Week 1Topic: Functional programmingReading: Abelson & Sussman, Section 1.1 (pages 1–31)Welcome to CS 61 A, the world’s best computer science course, because we use the world’s best CS book asthe textbook. The only thing wrong with this course is that all the rest of the CS cour ses for the rest ofyour life will seem a little disappointing (and repetitive).Course overview comes next lecture; now we’re going to jump right in so you can get started exploring onyour own in the lab.In 61A we program in Scheme, which is an interactive language. That means that instead of writing a greatbig program and then cranking it through all at once, you can type in a single expression and find out itsvalue. For example:3 self-evaluating(+ 2 3) function notation(sqrt 16) names don’t have to be punctuation(+ (* 3 4) 5) composition of functions+ functions are things in themselves’+ quoting’hello can quote any word’(+ 2 3) can quote any expression’(good morning) even non-expression sentences(first 274) functions don’t have to be arithmetic(butfirst 274) (abbreviation bf)(first ’hello) works for non-numbers(first hello) reminder about quoting(first (bf ’hello)) composition of no n-numeric functions(+ (first 23) (last 45)) combining numeric and non-numeric(define pi 3.14159) spe c ial formpi value of a symbol’pi contrast with quoted symbol(+ pi 7) symbols work in larger expressions(* pi pi)(define (square x)(* x x)) defining a function(square 5) invoking the function(square (+ 2 3)) composition with defined functionsTerminology: the formal parameter is the name of the ar gument (x); the actual argument expression is theexpression used in the invocation ((+ 2 3)); the actual argument value is the value of the argument in theinvocation (5). The argument’s name comes from the function’s definition; the argument’s value comes fromthe invocation.267Examples:(define (plural wd)(word wd ’s))This simple plural works for lots of words (book, computer, elephant) but not for words that end in y (fly,spy). So we improve it:;;;;; In file cs61a/lectures/1.1/plural.scm(define (plural wd)(if (equal? (last wd) ’y)(word (bl wd) ’ies)(word wd ’s)))If is a special form that only e valuates one of the alternatives.Pig Latin: Move initial consonants to the end of the word and append “ay”; SCHEME becomes EMESCHAY.;;;;; In file cs61a/lectures/1.1/pigl.scm(define (pigl wd)(if (pl-done? wd)(word wd ’ay)(pigl (word (bf wd) (first wd)))))(define (pl-done? wd)(vowel? (first wd)))(define (vowel? letter)(member? letter ’(a e i o u)))Pigl introduces recursion—a function that invokes itself. Mo re about how this works next week.Another example: Remember how to play Buzz? You go around the circle counting, but if your number isdivisible by 7 or has a digit 7 you have to say “buzz” instead:;;;;; In file cs61a/lectures/1.1/buzz.scm(define (buzz n)(cond ((equal? (remainder n 7) 0) ’buzz)((member? 7 n) ’buzz)(else n)))This introduces the cond special form for multi-way choices.Cond is the big exception to the rule about the meaning of parentheses; the clauses are n’t invo c ations.268Course overview:Computer science isn’t about computers (that’s electrical engineering) and it isn’t primarily a science (weinvent things more than we discover them).CS is partly a form of engineering (co nce rned with building reliable, efficient mechanisms, but in softwareinstead of metal) and partly an art form (using prog ramming as a medium for creative expr ession).Programming is really easy, as long as you’re solving small problems. Any k id in junior high school canwrite programs in BASIC, and not just exercises, either; kids do quite interesting and useful things withcomputers. But BASIC doe sn’t scale up; once the problem is so complicated that you c an’t keep it all inyour head at once, you need help, in the form of more powerful way s of thinking abo ut programming. (But inthis course we mostly use small examples, becaus e we’d never get finished otherwise, so you have to imaginehow you think each technique would work out in a larger case.)We deal with three big programming styles/approaches/paradigms:• Functional programming (2 months)• Object-oriented programming (1 month)• Client-server programming (1 wee k)• Logic programming (1 week)The big idea of the course is abstraction: inventing languages that let us talk more nearly in a problem’s ownterms and less in terms of the computer’s mechanisms or capabilities. There is a hierarchy of abstraction:Application programsHigh-level language (Scheme)Low-level language (C)Machine languageArchitecture (registers, memory, arithmetic unit, etc)circuit elements (gates)transistorssolid-state physicsquantum mechanicsIn 61C we look at lower levels; all are important but we want to start at the highest level to get you thinkingright.Style of work: Cooperative lear ning. No grading curve, so no need to compete. Homework is to learnfrom; only tests are to test you. Don’t cheat; ask for help instead. (This is the first CS course; if you’retempted to cheat now, how are you planning to get through the harder ones?)Functions.• A function can have any number of arguments, including zero, but must have exactly one return value.(Suppose you want two? You combine them into one, e.g., in a sentence.) It’s not a function unless youalways get the same answer fo r the same arguments.• Why does that matter? If each little computation is independent of the past history of the overallcomputation, then we can reorder the little computations. In particular, this helps cope with parallelprocessors.• The function definition provides a formal parameter (a name), and the function invocation provides anactual argument (a va lue). These fit together like piece s of a jigsaw puzzle. Don’t write a “function” thatonly works for one particular argument value!269• Instead of a sequence of events, we have composition of functions, like f (g(x)) in high school algebra. Wecan represent this visually with function machines and plumbing diagrams.Recursion:;;;;; In file cs61a/lectures/1.1/argue.scm> (argue ’(i like spinach))(i hate spinach)> (argue ’(broccoli is awful))(broccoli is great)(define (argue s)(if (empty? s)’()(se (opposite (first s))(argue (bf s)))))(define (opposite w)(cond ((equal? w ’like) ’hate)((equal? w ’hate) ’like)((equal? w ’wonderful) ’terrible)((equal? w ’terrible)
View Full Document