Abelson & Sussman, Section 1.1 (pages 1–31)
People who’ve taken CS 3: Don’t use the CS 3 higher-order procedures such as every in these problems; use recursion.
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.
Original “if” is implemented in a way that it will only evaluate “else-clause”, when the predicate is falsy. “new-if” is a procedure and because our version of Scheme is using applicable order of execution, it’s going to first evaluate the arguments. So it’s going to evaluate predicate, then-clause and else-clause ahead of time. This leads to an infinite loop, because within else-clause we’ve got a recursive call to “sqrt-iter”.
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)(load "_simply.scm")
(load "square.scm")
(define (squares list)
(if (is-empty? list) list
(sentence (square (first list)) (squares (butfirst list)))))
(define (is-empty? list)
(= (count list) 0))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)(load "_simply.scm")
(define (switch input)
(if (is-empty? input) input
(cond ((or (equal? (first input) 'me) (equal? (first input) 'I)) (se 'you (switch (bf input))))
;;; "You" at the beginning of a sentence, replace with "I"
((equal? (first input) 'You) (se 'I (switch (bf input))))
;;; "you" in the middle of a sentence, replace with "me"
((equal? (first input) 'you) (se 'me (switch (bf input))))
;;; Other word, don't change the first word, and switch the rest
(else (se (first input) (switch (bf input))))
)
)
)
(define (is-empty? list)
(= (count list) 0)
)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.
(define (ordered? numbers)
(define length (count numbers))
(cond
((= length 0) #t)
((= length 1) #t)
((or (= (item 1 numbers) (item 2 numbers)) (< (item 1 numbers) (item 2 numbers))) (ordered? (bf numbers)))
(else #f)
)
)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)(define (ends-e sentence)
(define (is-last-letter-e? word)
(equal? (last word) 'e)
)
(if (is-empty? sentence)
sentence
(if (is-last-letter-e? (first sentence))
(se (first sentence) (ends-e (bf sentence)))
(ends-e (bf sentence))
)
)
)
(define (is-empty? list)
(= (count list) 0)
)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?
If the following example will throw an error about unbound variable, it means that or is not a special
form. If it is a special form, it will return true and won’t evaluate the second expression with a bug.
(or (= 0 0) (= x 5))Benefits of or as a special form:
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.