OverviewThe Big PictureSchemeFunctionsWords and ConditionalsRecursionCourse OverviewINTRODUCTIONS, OVERVIEW, SCHEME 1GEORGE [email protected] of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyJune 21, 20101 OverviewMy name is George Wang, and we’ve got a great staff of TA’s, Readers, and LA’s to help all of you thissemester. Please take a minute to say ’hi’ to me and them in Lab later today :). Before I go over coursecontent and administrivia, I’d like to jump straight into the course.2 The Big PictureComputer Science is an interesting name for the field, since really, it is neither about computers nor is it ascience. If you want to study the construction and design of computers, you want to be studying electricalengineering. And excepting more theoretical elements, computer science is much more of of an abstractengineering discipline. Abstract, in the sense that in most fields you have to be concerned with the physi-cal limitations of the world. In Computer Science, we can deal with problems devoid of the constraints ofreality. This is something I think is really great.We’re not teaching you Scheme, since as I said, you’ll know Scheme by tomorrow. We’re teaching Com-puter Science. This is analogous to teaching Literature through Shakespeare or Milton, or whatever. Andthe central idea to this course and CS and much of engineering is Abstraction.Consider this. Maybe, but hopefully not, you drive a car to school. To speed up, you press the gas pedal.To slow down, you hit the brakes. To turn you use the steering wheel. But what’s amazing is that once youlearn these things, they’re the same whether you’re driving a hybrid or a truck. What the brakes are doingis utterly different. What the gas pedal is doing is mindblowingly complicated. But the point is, that youdon’t care. That is the power of abstraction. All you need to know is that gas pedal = speed. You don’tthink about the fuel injectors injecting gas and air engine, or each individual molecule forming in containedexplosions driving pistons which give the car your motion. You don’t think about all of that, because if youdid, you wouldn’t be able to actually do anything. You would be so focused on thinking about the detailsthat you miss the big picture.1But the abstraction are not limited to one single layer. What you should think about is the idea of layers ofabstraction. The engineers who build the engine don’t have to consider in detail the synthesis and analysisof the carbon chains that forms the gas. The chemists that study that don’t have to deal with the subatomicparticles that in turn compose those. Thus, these layers of abstraction keep you sane as you are trying totackle these topics.3 SchemeIn this class, we’ve settled on teaching CS through the medium of a language called Scheme. Students haveoften asked why we use Scheme and not something more powerful and cooler like Python, or Java, or C, orwhatever is popular in the day. One big reason is simple: by the end of today you will know virtually allthe rules of Scheme. However, knowing rules and understanding rules are fundamentally different, muchlike knowing the rules of chess and understanding the implications of these rules are very very different.Scheme is a interactive language. That means that instead of writing a great big program and then crankingit through all at once, you can type in a single expression and find out its value. 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) quote non-expression sentences(first 274) functions dont have to be arithmetic(butfirst 274) (abbreviated bf)(first ’hello) works for non-numbers(first hello) reminder about quoting(first (bf ’hello)) composition of non-numeric functions(+ (first 23) (last 45)) combining numeric and nonnumeric(define pi 3.14159265) special formpi value of a symbol’pi contrast with quoted(+ pi 7) symbols work in expressions(*pi pi)4 FunctionsNow, let’s talk about functions. You’ve heard of these from grade school. Functions here are essentially thesame thing. First, let’s look at how to do them in Scheme:2(define (square x) defining a function(*x x))(square 5) invoking the function(square (+ 2 3)) composition with defined functionsHere’s a few things to note:• Procedures have something called formal parameters and a body. In the case above, the parameter isx, and the body is (*x x). There is also a difference between functions and procedures. Take forexample:f (x) = 3x + 6g (x) = 3 (x + 2)f and g are the same function, but they are different procedures. In other words, procedures is a set ofinstructions to compute a function. Most of the time, these won’t matter, but occasionally, they will,and I’ll try to be careful when I can.• A function can have any number of arguments, including none. However, they must have exactlyone return value. It’s not a function unless you always get the same answer for the same arguments.• If each little computation is independent of the past history, then we can reorder the computation. Inparticular, this is great for parallelism where we may have many processors dividing up the work insuch a way as to be both efficient and correct.• It is not about a sequence of events! We don’t do programming like:(do-thing-1)(do-thing-2)(do-thing-3)• Instead, we do composition of functions. Imagine things like f (g (x)), like in high school. We canrepresent this visually as well.5 Words and ConditionalsLet’s try to write a procedure that returns the plural of a word:(define (plural wd)(word wd ’s))Word is a procedure that builds a word given its arguments. This example works for a lot of simple words,such as word, work, book, elephant, but not for words that end in y. Thus, we will include it by introducinga conditional, if.(define (plural wd)(if (equal? (last wd) ’y)(word (bl wd) ’ies)(word wd ’s)))If is a special form that only evaluates one of the two alternatives. Equal? is a procedure that given twoarguments, tests if they are equal.Finally, let’s examine one more special form, cond.3(define (buzz n)(cond ((equal? (remainder n 7) 0) ’buzz)((member? 7 n) ’buzz)(else n)))This is an example of what we call syntactic sugar. The two
View Full Document
Unlocking...