CS61A Summer 2011 Homework 2
Topic: Higher-order procedures
Reading: Abelson & Sussman, Section 1.3
Note that we are skipping 1.2; we’ll get to it later. Because of this, never mind for now the stuff about iterative versus recursive processes in 1.3 and in the exercises from that section.
Don’t panic if you have trouble with the half-interval example on pp. 67–68; you can just skip it. Try to read and understand everything else.
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; you’ll need to know the ideas in these exercises later in the semester.)
2. Last week you wrote procedures squares, that squared each number in its argument sentence, and saw pigl-sent, that pigled each word in its argument sentence. Generalize this pattern to create a higher-order procedure called every that applies an arbitrary procedure, given as an argument, to each word of an argument sentence. This procedure is used as follows:
> (every square ’(1 2 3 4))
(1 4 9 16)
> (every first ’(nowhere man))
3. Our Scheme library provides versions of the every function from the last exercise and the keep function shown in lecture. Get familiar with these by trying examples such as the 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.
EXTRA FOR EXPERTS
In principle, we could build a version of Scheme with no primitives except lambda. Everything else can be defined in terms of lambda, although it’s not done that way in practice because it would be so painful. But we can get a sense of the flavor of such a language by eliminating one feature at a time from Scheme to see how to work around it.
In this problem we explore a Scheme without define. We can give things names by using argument binding, as let does, so instead of
(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))))
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)
(* n (fact (- n 1)))))
((lambda (n) (if ...))
because what do we do about the invocation of fact inside the body?
Your task is to find a way to express the fact procedure in a Scheme without any way to define global names.
Unix feature of the week: pine, mail, firefox
Emacs feature of the week: M-x info, C-x u (undo)