CS 61A Week 1Topic: Functional programmingReading: Abelson & Sussman, Section 1.1 (pages 1–31)Note: With the obvious exception of this first week, you should do each week’s readingbefore the Monday lecture. So also start now on next week’s reading, Ab elson & Sussman,Section 1.3Homework:People who’ve taken CS 3: Don’t use the CS 3 higher-order procedures suchas every in these problems; use recursion.1. Do exercise 1.6, page 25. This is an essay question; you needn’t hand in any computerprintout, unless you think the grader can’t read your handwriting. If you had troubleunderstanding the square root program in the book, explain instead what will happ en ifyou use new-if instead of if in the pigl Pig Latin procedure.2. Write a procedure squares that takes a sentence of numbers as its arg ument andreturns a sentence of the squares of the numbers:> (squares ’(2 3 4 5))(4 9 16 25)3. Write a procedure switch that takes a sentence as i ts argument and returns a sent encein which every instance of the words I or me is replaced by you, while every instance ofyou is replaced by me except at the beginning of the sentence, where it’s replaced by I.(Don’t worry about capital ization of letters.) Example:> (switch ’(You told me that I should wake you up))(i told you that you should wake me up)4. Write a predicate ordered? that takes a sentence of numbers as its argument andreturns a true value if the numbers are in ascending order, or a false value otherwise.5. Write a procedure ends-e that takes a sentence as i ts argument and returns a sent encecontaining only those words of the argument whose last letter is E:> (ends-e ’(please put the salami above the blue elephant))(please the above the blue)Continued on next page.3Week 1 continued...6. Most versions of Lisp provide and and or procedures like the ones on page 19. Inprinciple there is no reason why these can’t be ordinary procedures, but some versions ofLisp make them special forms. Suppose, for example, we eval uate(or (= x 0) (= y 0) (= z 0))If or is an ordinary procedure, all three argument expressions will be evaluated before oris invoked. But if the variable x has the value 0, we know that the entire expression hasto be true regardless of the values o f y and z. A Lisp interpreter in which or is a specialform can evaluate the arguments one by one until either a true one is found or it runs outof arguments.Your mission is to devi se a test that will tell you whether Scheme’s and and or are specialforms or ordinary functions. This is a somewhat tricky problem, but it’ ll get you thinkingabout the evaluation process more deeply than you otherwise might .Why might it be advantageous for an interpreter to treat or as a special form and evaluateits arguments one at a ti me? Can you think of reasons why it might be advantageous totreat or as an ordinary function?Unix feature of the week: manEmacs feature of the week: C-g, M-x aproposThere will be a “feature of the week” each week. These first features come first because theyare the ones that you use to find out about the other ones: E ach provides documentationof a Unix or Emacs feature. This week, type man man as a shell command to see the Unixmanual page on the man program. Then, in Emacs, type M-x (that’s meta-X, or ESC X ifyou prefer) describe-function followed by the Return or Enter key, then apropos to seehow the apropos command works. If you want to know about a command by its keystrokeform (such as C-g) because you don’t know its long name (such as keyboard-quit), youcan say M-x describe-key then C-g.You aren’t going to be tested on these system features, but it’ll make the rest of your lifea lot easier if you learn about them.4CS 61A Week 2Topic: Higher-order proceduresReading: Abelson & Sussman, Section 1.3Note that we are skipping 1.2; we’ll get to it later. Because of this, never mind for nowthe stuff about iterative versus recursive processes in 1.3 and in the exercises from thatsection.Don’t panic if you have trouble with the half-interval example on pp. 67–68; you can justskip it. Try to read and understand everything else.Homework:1. Abelson & Sussman, exercises 1.31(a), 1.32(a), 1.33, 1.40, 1.41, 1.43, 1.46(Pay attention to footnote 51; yo u’ll need to know the ideas in these exercises later in thesemester.)2. Last week you wrote procedures squares, that squared each number in its argumentsent ence, and saw pigl-sent, that pigled each word in its argument sentence. Generalizethis pattern to create a higher-order procedure called every that applies an arbitraryprocedure, given as an argument, to each word of an argument sentence. T his procedureis used as follows:> (every square ’(1 2 3 4))(1 4 9 16)> (every first ’(nowhere man))(n m)3. Our Scheme library provides versions of the every function from the last exercise andthe keep function shown in lecture. Get familiar with these by trying examples such asthe following:(every (lambda (letter) (word letter letter)) ’purple)(every (lambda (number) (if (even? number) (word number number) number))’(781 5 76 909 24))(keep even? ’(781 5 76 909 24))(keep (lambda (letter) (member? letter ’aeiou)) ’bookkeeper)(keep (lambda (letter) (member? letter ’aeiou)) ’syzygy)(keep (lambda (letter) (member? letter ’aeiou)) ’(purple syzygy))(keep (lambda (wd) (member? ’e wd)) ’(purple syzygy))Continued on next page.5Week 2 continued...Extra for experts:In principle, we could build a version of Scheme with no primitives except lambda. Every-thing else can be defined in terms of lambda, although it’s not done that way in practicebecause i t would be so pai nful. But we can get a sense of the flavor of such a language byeliminating one feature at a t ime from Scheme to see how to work around i t.In this problem we explore a Scheme without define. We can give t hings names by usingargument binding, as let does, so instead o f(define (sumsq a b)(define (square x) (* x x))(+ (square a) (square b)))(sumsq 3 4)we can say((lambda (a b)((lambda (square)(+ (square a) (square b)))(lambda (x) (* x x))))3 4)This works fine as long as we don’t want to use recursive procedures. But we can’t replace(define (fact n)(if (= n 0)1(* n (fact (- n 1)))))(fact 5)by((lambda (n)(if ...))5)because what do we do about the invocat ion of fact inside the body?Your task is to find a way to express the fact procedure in a Scheme without any way todefine global names.Unix feature of the week: pine,
View Full Document
Unlocking...