DOC PREVIEW
Berkeley COMPSCI 61A - Lecture Notes

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.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 107 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Berkeley COMPSCI 61A - Lecture Notes

Documents in this Course
Lecture 1

Lecture 1

68 pages

Midterm

Midterm

5 pages

Midterm

Midterm

6 pages

Lecture 35

Lecture 35

250 pages

Lecture 14

Lecture 14

125 pages

Lecture 2

Lecture 2

159 pages

Lecture 6

Lecture 6

113 pages

Lecture 3

Lecture 3

162 pages

Homework

Homework

25 pages

Lecture 13

Lecture 13

117 pages

Lecture 29

Lecture 29

104 pages

Lecture 11

Lecture 11

173 pages

Lecture 7

Lecture 7

104 pages

Midterm

Midterm

6 pages

Midterm

Midterm

6 pages

Lecture 8

Lecture 8

108 pages

Lab 4

Lab 4

4 pages

Lecture 7

Lecture 7

52 pages

Lecture 20

Lecture 20

129 pages

Lecture 15

Lecture 15

132 pages

Lecture 9

Lecture 9

95 pages

Lecture 30

Lecture 30

108 pages

Lecture 17

Lecture 17

106 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?