6.001 Structure and Interpretation of Computer Programs
Recitation #6
Wednesday, September 29, 2004
Review
- higher-order procedures, e.g., map
Practice
1. Here is an abstraction for a vector, which represents a
point (x,y) in the plane.
- (make-vect x y) constructs a vector
- (get-x v) accesses a vector's x coordinate
- (get-y v) accesses a vector's y coordinate
(a) Write down the contract for the vector abstraction.
(get-x (make-vect x y)) => x
(get-y (make-vect x y)) => y
(b) Implement the abstraction when a vector is represented by a pair.
(define (make-vect x y) (cons x y))
(define (get-x v) (car v))
(define (get-y v) (cdr v))
or, equivalently:
(define make-vect cons)
(define get-x car)
(define get-y cdr)
(c) Implement the abstraction when a vector is represented by a list.
(define (make-vect x y) (list x y))
(define (get-x v) (car v))
(define (get-y v) (car (cdr v)))
or, equivalently:
(define make-vect list)
(define get-x car)
(define get-y cadr)
(d) Implement the abstraction when a vector is represented by a
procedure.
Here's one way to do it:
(define (make-vect x y)
(lambda (coord)
(if (= coord 0) x y)))
(define (get-x v) (v 0))
(define (get-y v) (v 1))
Here's another, where a vector is not
just a procedure, but is actually a higher-order procedure:
(define (make-vect x y)
(lambda (selector)
(selector x y)))
(define (get-x v)
(v (lambda (x y) x)))
(define (get-y v)
(v (lambda (x y) y)))
2. Using the vector abstraction, write the following operations on
vectors.
(a) (+vect v1 v2) adds two vectors v1 and v2
using vector addition
(define (+vect v1 v2)
(make-vect (+ (get-x v1) (get-x v2))
(+ (get-y v1) (get-y v2))))
Notice no uses of car, cdr, or cons!
The vector abstraction doesn't tell us how vectors are implemented; all we
can count on is the contract, which only lets us use make-vect, get-x, and get-y.
(b) (-vect v1 v2) subtracts v2 from v1
(define (-vect v1 v2)
(make-vect (- (get-x v1) (get-x v2))
(- (get-y v1) (get-y v2))))
(c) (scale-vect v k) multiplies vector v by the
(scalar) factor k
(define (scale-vect v k)
(make-vect (* (get-x v1) k)
(* (get-y v1) k)))
(d) (mag v) computes the
length of a vector.
(define (mag v)
(sqrt (+ (square (get-x v)) (square (get-y v)))))
(e) (=vect? v1 v2) returns true if v1 is the same
point as v2
(define (=vect? v1 v2)
(and (= (get-x v1) (get-x v2))
(= (get-y v1) (get-y v2))))
3. Define another abstraction, curve, to represent a sequence
of line segments whose start and end points are vectors.
- (make-curve v) constructs an empty curve, i.e. having no
line segments and start point v.
- (extend-curve v c) constructs a curve by inserting a new
point v at the start of another curve c.
- (start-point c) returns a curve's start point.
- (rest-of-curve c) removes a curve's first line segment
and returns the rest of it.
- (empty-curve? c) returns true if a curve has no
line segments.
(a) Write down the contract for the curve abstraction.
For all vectors v and curves c,
(start-point (make-curve v)) => v
(start-point (extend-curve v c)) => v
(rest-of-curve (extend-curve v c)) => c
(empty-curve? (make-curve v)) => #t
(empty-curve? (extend-curve v c)) => #f
(b) Implement the abstraction when a curve is represented as a list of
points.
(define (make-curve v) (list v))
(define (extend-curve v c) (cons v c))
(define (start-point c) (car c))
(define (rest-of-curve c) (cdr c))
(define (empty-curve? c) (null? (cdr c)))
(c) Implement the abstraction when a curve is represented by a
procedure.
Here's one solution:
(define (make-curve v)
(lambda (selector)
(selector v nil)))
(define (extend-curve v c)
(lambda (selector)
(selector v c)))
(define (start-point c)
(c (lambda (start rest) start)))
(define (rest-of-curve c)
(c (lambda (start rest) rest)))
(define (empty-curve? c)
(null? (c (lambda (start rest) rest))))
4. Using the curve abstraction and vector operations, define the
following operations on curves:
(a) (scale c k) scales every point in a curve by a scalar
value k.
(define (scale c k)
(if (empty-curve? c)
(make-curve (scale-vect (start-point c) k))
(extend-curve (scale-vect (start-point c) k))
(scale-vect (rest-of-curve c) k))))
(b) (translate c v) translates every point in a curve by
vector v.
(define (translate c v)
(if (empty-curve? c)
(make-curve (+vect (start-point c) v))
(extend-curve (+vect (start-point c) v))
(translate (rest-of-curve c) v))))
Why didn't we just use map here?
(c) (perimeter c) computes
the sum of the lengths of the line segments in a curve.
(define (perimeter c)
(if (empty-curve? c)
0
(let ((p1 (start-point c))
(p2 (start-point (rest-of-curve c))))
(+ (mag (-vect p1 p2))
(perimeter (rest-of-curve c))))))
(d) (closed? c) tests whether the curve's start point is the
same as its end point.
Here are two solutions. Interestingly, both solutions define
helper functions, like many of the iterative processes we've looked
at. Which of these closed?
procedures is iterative, and which is recursive?
(define (closed? c)
(define (end-point c)
(if (empty-curve? c)
(start-point c)
(end-point (rest-of-curve c))))
(=vect? (start-point c) (end-point c)))
(define (closed? c)
(define (ends-with? c v)
(if (empty-curve? c)
(=vect? (start-point c) v)
(ends-width? (rest-of-curve v))))
(ends-with? c (start-point c)))