CS61A                 Summer 2011                 Homework 1

Topic: Functional programming

Reading: Abelson & Sussman, Section 1.1 (pages 1-31)

Topic:  Functional programming

Reading: Abelson & Sussman,  Section 1.1 (pages 1–31)

Note:  With  the obvious  exception  of this  first  week, you should  do each week’s reading before the Monday lecture.  So also start now on next week’s reading,  Abelson & Sussman, Section 1.3

Homework:

People who’ve  taken  CS  3:  Don’t  use the CS  3 higher-order procedures such as  every in these problems; use recursion.

1.   Write  a  procedure  squares that takes  a  sentence  of numbers  as  its  argument  and returns a sentence of the squares  of the numbers:

> (squares ’(2 3 4 5))

(4 9 16 25)

2. Write a procedure  switch that takes a sentence as its argument and returns a sentence in which every instance  of the words I or me is replaced  by you, while every instance  of you is replaced  by me except  at the beginning  of the sentence,  where it’s  replaced  by I. (Don’t worry about capitalization of letters.)  Example:

> (switch ’(You told me that I should wake you up)) (i told you that you should wake me up)

3.  Write  a predicate  ordered? that takes  a sentence  of numbers  as its  argument  and returns a true value if the numbers  are in ascending  order,  or a false value otherwise.

4. Write a procedure  ends-e that takes a sentence as its argument and returns a sentence containing 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.

5.  Most  versions  of Lisp provide  and and  or procedures  like the ones on page  19.   In principle  there is no reason why these can’t be ordinary  procedures,  but some versions of Lisp make them special forms.  Suppose,  for example,  we evaluate

(or (= x 0) (= y 0) (= z 0))

If or is an ordinary  procedure,  all three argument expressions  will be evaluated before or is invoked.  But if the variable  x has the value 0, we know that the entire expression  has to be true regardless  of the values of y and z. A Lisp interpreter in which or is a special form can evaluate the arguments one by one until either a true one is found or it runs out of arguments.

Your mission is to devise a test that will tell you whether Scheme’s and and or are special forms or ordinary  functions.  This is a somewhat tricky problem,  but it’ll get you thinking about 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 evaluate its arguments one at a time?  Can  you think of reasons  why it might be advantageous to treat or as an ordinary  function?

6. Do exercise 1.6, page 25. This is an essay question; you needn’t hand  in any computer printout, unless you think the grader can’t read your handwriting.  If you had trouble understanding  the square  root program  in the book, explain  instead  what will happen  if you use new-if instead of if in the pigl Pig Latin procedure.

Unix feature of the week: man

Emacs feature of the week: C-g, M-x apropos

There will be a “feature of the week” each week. These first features come first because they are the ones that you use to find out about the other ones: Each provides documentation of a Unix or Emacs feature.  This week, type man man as a shell command  to see the Unix manual  page on the man program.   Then,  in Emacs,  type M-x (that’s meta-X, or ESC X if you prefer) describe-function followed by the Return or Enter key, then apropos to see how the apropos command  works.  If you want to know about a command  by its keystroke form (such  as C-g) because  you don’t know its long name  (such  as keyboard-quit),  you can 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 life a lot easier if you learn about them.