2 Chapter 2. Building Abstractions with Data🔗

2.1 Hierarchical Data and the Closure Property🔗

2.1.1 Example: A Picture Language🔗

2.1.1.1 Exercise 2.44🔗

Define the procedure up-split used by corner-split. It is similar to right-split, except that it switches the roles of below and beside.

Solution:

#lang racket/base

(provide square-limit)

(require (only-in "ch2-ex50.rkt" flip-horiz flip-vert)

(only-in "ch2-ex51.rkt" beside below))

(define (right-split painter n)

(if (= n 0)

painter

(let ([smaller (right-split painter (- n 1))])

(beside painter (below smaller smaller)))))

(define (up-split painter n)

(if (= n 0)

painter

(let ([smaller (up-split painter (- n 1))])

(below painter (beside smaller smaller)))))

(define (corner-split painter n)

(if (= n 0)

painter

(let* ([up (up-split painter (- n 1))]

[right (right-split painter (- n 1))]

[top-left (beside up up)]

[bottom-right (below right right)]

[corner (corner-split painter (- n 1))])

(beside (below painter top-left)

(below bottom-right corner)))))

(define (square-limit painter n)

(let* ([quarter (corner-split painter n)]

[half (beside (flip-horiz quarter) quarter)])

(below (flip-vert half) half)))

2.1.1.2 Exercise 2.45🔗

right-split and up-split can be expressed as instances of a general splitting operation. Define a procedure split with the property that evaluating

(define right-split (split beside below))

(define up-split (split below beside))

produces procedures right-split and up-split with the same behaviors as the ones already defined.

Solution:

#lang racket/base

(provide right-split

up-split)

(require (only-in "ch2-ex51.rkt" beside below))

(define (split a1 a2)

(lambda (painter n)

(if (= n 0)

painter

(let ([smaller ((split a1 a2) painter (- n 1))])

(a1 painter (a2 smaller smaller))))))

(define right-split (split beside below))

(define up-split (split below beside))

2.1.1.3 Exercise 2.46🔗

Implement a data abstraction for vectors by giving a constructor make-vect and corresponding selectors xcor-vect and ycor-vect. In terms of your selectors and constructor, implement procedures add-vect, sub-vect, and scale-vect that perform the operations vector addition, vector subtraction, and multiplying a vector by a scalar

Solution:

#lang racket/base

(provide make-vect

xcor-vect

ycor-vect

add-vect

sub-vect

scale-vect)

(define (make-vect x y) (list x y))

(define xcor-vect car)

(define ycor-vect cadr)

(define (add-vect v1 v2)

(make-vect (+ (xcor-vect v1) (xcor-vect v2))

(+ (ycor-vect v1) (ycor-vect v2))))

(define (sub-vect v1 v2)

(make-vect (- (xcor-vect v1) (xcor-vect v2))

(- (ycor-vect v1) (ycor-vect v2))))

(define (scale-vect s v)

(make-vect (* s (xcor-vect v))

(* s (ycor-vect v))))

(module+ test

(require akari-sicp/lib/testing)

(define v1 (make-vect 1 2))

(define v2 (make-vect 3 4))

(run-tests

(describe "vector operations"

(it.equal? "should add vectors correctly" (add-vect v1 v2) (make-vect 4 6))

(it.equal? "should subtract vectors correctly" (sub-vect v2 v1) (make-vect 2 2))

(it.equal? "should scale vectors correctly" (scale-vect 2 v2) (make-vect 6 8)))))

2.1.1.4 Exercise 2.47🔗

Here are two possible constructors for frames:

For each constructor supply the appropriate selectors to produce an implementation for frames.

Solution:

#lang racket/base

(provide make-frame

origin-frame

edge1-frame

edge2-frame

frame-coord-map)

(require (only-in"ch2-ex46.rkt"

make-vect

xcor-vect

ycor-vect

add-vect

scale-vect))

(define (make-frame origin edge1 edge2)

(list origin edge1 edge2))

(define origin-frame car)

(define edge1-frame cadr)

(define edge2-frame caddr)

(define (frame-coord-map frame)

(lambda (v)

(add-vect

(origin-frame frame)

(add-vect (scale-vect (xcor-vect v) (edge1-frame frame))

(scale-vect (ycor-vect v) (edge2-frame frame))))))

(define (make-frame* origin edge1 edge2)

(cons origin (cons edge1 edge2)))

(define origin-frame* car)

(define edge1-frame* cadr)

(define edge2-frame* cddr)

(module+ test

(require akari-sicp/lib/testing)

(define origin (make-vect 0 0))

(define unit-x (make-vect 1 0))

(define unit-y (make-vect 0 1))

(define origin2 (make-vect 2 3))

(define edge1 (make-vect 4 2))

(define edge2 (make-vect 1 5))

;; Tests for the first implementation (using list)

(define list-impl-tests

(describe "list implementation of frame"

(it "creates a frame and accesses components"

(let ([frame (make-frame origin unit-x unit-y)])

(expect

[(origin-frame frame) => origin]

[(edge1-frame frame) => unit-x]

[(edge2-frame frame) => unit-y])))

(it "works with arbitrary vectors"

(let ([frame (make-frame origin2 edge1 edge2)])

(expect

[(origin-frame frame) => origin2]

[(edge1-frame frame) => edge1]

[(edge2-frame frame) => edge2])))

(it "uses frame-coord-map correctly"

(let* ([frame (make-frame origin2 edge1 edge2)]

[mapper (frame-coord-map frame)])

(expect

[(mapper (make-vect 0 0)) => origin2]

[(mapper (make-vect 1 0)) => (add-vect origin2 edge1)]

[(mapper (make-vect 0 1)) => (add-vect origin2 edge2)]

[(mapper (make-vect 1 1)) => (add-vect origin2 (add-vect edge1 edge2))])))))

;; Tests for the second implementation (using cons)

(define cons-impl-tests

(describe "cons implementation of frame"

(it "creates a frame and accesses components"

(let ([frame (make-frame* origin unit-x unit-y)])

(expect

[(origin-frame* frame) => origin]

[(edge1-frame* frame) => unit-x]

[(edge2-frame* frame) => unit-y])))

(it "works with arbitrary vectors"

(let ([frame (make-frame* origin2 edge1 edge2)])

(expect

[(origin-frame* frame) => origin2]

[(edge1-frame* frame) => edge1]

[(edge2-frame* frame) => edge2])))))

(define all-tests

(describe "frame implementations (exercise 2.47)"

list-impl-tests

cons-impl-tests))

(run-tests all-tests))

2.1.1.5 Exercise 2.48🔗

A directed line segment in the plane can be represented as a pair of vectors—the vector running from the origin to the start-point of the segment, and the vector running from the origin to the end-point of the segment.

Use your vector representation from Exercise 2.46 to define a representation for segments with a constructor make-segment and selectors start-segment and end-segment.

Solution:

#lang racket/base

(provide make-segment

start-segment

end-segment)

(define (make-segment start end)

(list start end))

(define start-segment car)

(define end-segment cadr)

(module+ test

(require akari-sicp/lib/testing)

(require (only-in "ch2-ex46.rkt" make-vect))

(define v1 (make-vect 1 2))

(define v2 (make-vect 3 4))

(define v3 (make-vect 5 6))

(define v4 (make-vect 7 8))

(define seg1 (make-segment v1 v2))

(define seg2 (make-segment v3 v4))

(define segment-tests

(describe "segment implementation (exercise 2.48)"

(it "creates a segment and accesses components"

(expect

[(start-segment seg1) => v1]

[(end-segment seg1) => v2]))

(it "works with different vectors"

(expect

[(start-segment seg2) => v3]

[(end-segment seg2) => v4]))))

(run-tests segment-tests))

2.1.1.6 Exercise 2.49🔗

Use segments->painter to define the following primitive painters:

1. The painter that draws the outline of the designated frame.

2. The painter that draws an “X” by connecting opposite corners of the frame.

3. The painter that draws a diamond shape by connecting the midpoints of the sides of the frame.

4. The wave painter.

Solution:

#lang racket/base

(provide outline

x

diamond

wave)

(require akari-sicp/lib/picture)

(define outline

(segments->painter

(list (make-segment (make-vect 0 0) (make-vect 1 0))

(make-segment (make-vect 1 0) (make-vect 1 1))

(make-segment (make-vect 1 1) (make-vect 0 1))

(make-segment (make-vect 0 1) (make-vect 0 0)))))

(define x

(segments->painter

(list (make-segment (make-vect 0 0) (make-vect 1 1))

(make-segment (make-vect 1 0) (make-vect 0 1)))))

(define diamond

(segments->painter

(list (make-segment (make-vect 0.5 0) (make-vect 1 0.5))

(make-segment (make-vect 1 0.5) (make-vect 0.5 1))

(make-segment (make-vect 0.5 1) (make-vect 0 0.5))

(make-segment (make-vect 0 0.5) (make-vect 0.5 0)))))

; https://stackoverflow.com/questions/13592352/

(define wave

(segments->painter

(list

(make-segment (make-vect 0.20 0.00) (make-vect 0.35 0.50))

(make-segment (make-vect 0.35 0.50) (make-vect 0.30 0.60))

(make-segment (make-vect 0.30 0.60) (make-vect 0.15 0.45))

(make-segment (make-vect 0.15 0.45) (make-vect 0.00 0.60))

(make-segment (make-vect 0.00 0.80) (make-vect 0.15 0.65))

(make-segment (make-vect 0.15 0.65) (make-vect 0.30 0.70))

(make-segment (make-vect 0.30 0.70) (make-vect 0.40 0.70))

(make-segment (make-vect 0.40 0.70) (make-vect 0.35 0.85))

(make-segment (make-vect 0.35 0.85) (make-vect 0.40 1.00))

(make-segment (make-vect 0.60 1.00) (make-vect 0.65 0.85))

(make-segment (make-vect 0.65 0.85) (make-vect 0.60 0.70))

(make-segment (make-vect 0.60 0.70) (make-vect 0.75 0.70))

(make-segment (make-vect 0.75 0.70) (make-vect 1.00 0.40))

(make-segment (make-vect 1.00 0.20) (make-vect 0.60 0.48))

(make-segment (make-vect 0.60 0.48) (make-vect 0.80 0.00))

(make-segment (make-vect 0.40 0.00) (make-vect 0.50 0.30))

(make-segment (make-vect 0.50 0.30) (make-vect 0.60 0.00)))))

2.1.1.7 Exercise 2.50🔗

Define the transformation flip-horiz, which flips painters horizontally, and transformations that rotate painters counterclockwise by 180 degrees and 270 degrees.

Solution:

#lang racket/base

(provide transform-painter

flip-vert

flip-horiz

squash-inwards

shrink-to-upper-right

rotate90

rotate180

rotate270)

(require akari-sicp/lib/picture)

(define (transform-painter painter origin corner1 corner2)

(lambda (frame)

(let* ([m (frame-coord-map frame)]

[new-origin (m origin)])

(painter

(make-frame new-origin

(sub-vect (m corner1) new-origin)

(sub-vect (m corner2) new-origin))))))

(define (flip-vert painter)

(transform-painter painter

(make-vect 0.0 1.0)

(make-vect 1.0 1.0)

(make-vect 0.0 0.0)))

(define (flip-horiz painter)

(transform-painter painter

(make-vect 1.0 0.0)

(make-vect 0.0 0.0)

(make-vect 1.0 1.0)))

(define (rotate90 painter)

(transform-painter painter

(make-vect 1.0 0.0)

(make-vect 1.0 1.0)

(make-vect 0.0 0.0)))

(define (squash-inwards painter)

(transform-painter painter

(make-vect 0.0 0.0)

(make-vect 0.65 0.35)

(make-vect 0.35 0.65)))

(define (shrink-to-upper-right painter)

(transform-painter painter

(make-vect 0.5 0.5)

(make-vect 1.0 0.5)

(make-vect 0.5 1.0)))

(define (rotate180 painter)

(transform-painter painter

(make-vect 1.0 1.0)

(make-vect 0.0 1.0)

(make-vect 1.0 0.0)))

(define (rotate270 painter)

(transform-painter painter

(make-vect 0.0 1.0)

(make-vect 0.0 0.0)

(make-vect 1.0 1.0)))

2.1.1.8 Exercise 2.51🔗

Define the below operation for painters. below takes two painters as arguments. The resulting painter, given a frame, draws with the first painter in the bottom of the frame and with the second painter in the top. Define below in two different ways—first by writing a procedure that is analogous to the beside procedure given above, and again in terms of beside and suitable rotation operations.

Solution:

#lang racket/base

(provide beside

below

below*)

(require akari-sicp/lib/picture

(only-in "ch2-ex50.rkt" transform-painter rotate90 rotate270))

(define (beside painter1 painter2)

(let ([painter-left

(transform-painter painter1

(make-vect 0.0 0.0)

(make-vect 0.5 0.0)

(make-vect 0.0 1.0))]

[painter-right

(transform-painter painter2

(make-vect 0.5 0.0)

(make-vect 1.0 0.0)

(make-vect 0.5 1.0))])

(lambda (frame)

(painter-left frame)

(painter-right frame))))

;; implement the below function using transform-painter

(define (below painter1 painter2)

(let ([painter-bottom

(transform-painter painter1

(make-vect 0.0 0.0)

(make-vect 1.0 0.0)

(make-vect 0.0 0.5))]

[painter-top

(transform-painter painter2

(make-vect 0.0 0.5)

(make-vect 1.0 0.5)

(make-vect 0.0 1.0))])

(lambda (frame)

(painter-bottom frame)

(painter-top frame))))

;; implement the below* function using beside and suitable rotations

(define (below* painter-bottom painter-top)

(rotate90 (beside (rotate270 painter-bottom) (rotate270 painter-top))))

2.2 Systems with Generic Operations🔗

2.2.1 Generic Arithmetic Operations🔗

2.2.1.1 Exercise 2.77🔗

Louis Reasoner tries to evaluate the expression (magnitude z) where z is the object shown in Figure 2.24. To his surprise, instead of the answer 5 he gets an error message from apply-generic, saying there is no method for the operation magnitude on the types (complex). He shows this interaction to Alyssa P. Hacker, who says "The problem is that the complex-number selectors were never defined for complex numbers, just for polar and rectangular numbers. All you have to do to make this work is add the following to the complex package:"

(put 'real-part '(complex) real-part)

(put 'imag-part '(complex) imag-part)

(put 'magnitude '(complex) magnitude)

(put 'angle '(complex) angle)

Describe in detail why this works. As an example, trace through all the procedures called in evaluating the expression (magnitude z) where z is the object shown in Figure 2.24. In particular, how many times is apply-generic invoked? What procedure is dispatched to in each case?

#lang racket/base

(require akari-sicp/lib/numeric-tower)

(require racket/pretty)

(install-polar-package)

(install-rectangular-package)

(install-complex-package)

(define z (make-complex-from-real-imag 3 4))

(module+ test

(require akari-sicp/lib/testing

akari-sicp/lib/common)

(run-tests

(describe "exercise 2.77"

(it "should raise error"

(expect [(magnitude z) =!> #rx"no method for these types"]))

(it "should works"

(put 'real-part '(complex) real-part)

(put 'imag-part '(complex) imag-part)

(put 'magnitude '(complex) magnitude)

(put 'angle '(complex) angle)

(expect

[(magnitude z) ~> (sqrt (+ (square (real-part z))

(square (imag-part z))))])))))