GNU Guile (Scheme) Reference
Kip Landergren
Contents
Language
null?
pair?
#t
#f
#nil
Resources
FAQ
What does “Wrong type to apply” mean?
Check whether you an extra set of parentheses causing the evaluation of the result of a procedure.
sicp-guile
README.md
# sicp-guile
Work associated with [Structure and Interpretation of Computer Programs](https://mitpress.mit.edu/9780262510875/structure-and-interpretation-of-computer-programs/) using [Guile](https://www.gnu.org/software/guile/).
HTML5/EPUB3 version of SICP available via [sarabander/sicp](https://github.com/sarabander/sicp).
chapter-1.scm
;;; solutions to exercises from SICP Chapter 1
;;; 1.1
10 ; => 10
(+ 5 3 4) ; => 12
(- 9 1) ; => 8
(/ 6 2) ; => 3
(+ (* 2 4) (- 4 6)) ; => 6
(define a 3) ; => unspecified
(define b (+ a 1)) ; => unspecified
(+ a b (* a b)) ; => 19
(= a b) ; => #f
(if (and (> b a) (< b (* a b)))
b
a) ; => 4
(cond ((= a 4) 6)
((= b 4) (+ 6 7 a))
(else 25)) ; => 16
(+ 2 (if (> b a) b a)) ; => 6
(* (cond ((> a b) a)
((< a b) b)
(else -1))
(+ a 1)) ; => 16
;;; 1.2
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7))) ; -37/150
;;; 1.3
(define (square x) (* x x))
(define (sum-of-squares x y)
(+ (square x) (square y)))
(sum-of-squares 3 4) ; => 25
(define (sum-of-squares-of-largest x y z)
(cond ((and (< z x) (< z y)) (sum-of-squares x y))
((and (< y x) (< y z)) (sum-of-squares x z))
(else (sum-of-squares y z))))
(sum-of-squares-of-largest 1 2 2) ; => 8
(sum-of-squares-of-largest 1 2 3) ; => 13
(sum-of-squares-of-largest 4 2 3) ; => 25
;;; 1.4
;;; the following will:
;;; * check if b is greater than 0
;;; * if true an addition operator will be returned, resulting in (+ a b)
;;; * else a subtraction operator will be returned, resulting in (- a b)
;;; * the net result of which is that a is always added to the absolute value of b
(define (a-plus-abs-b a b)
((if (> b 0) + -) a b))
;;; 1.5
(define (p) (p))
(define (test x y)
(if (= x 0) 0 y))
;;; (test 0 (p)) ; I run forever
;;; applicative order ("evaluate arguments, then reduce"):
;; (test 0 (p)) ; evaluate subexpressions!
;; (test 0 (p)) ; `test` is looked up in the environment
;; (test 0 (p)) ; `0` evaluates to the number 0
;; (test 0 (p)) ; `(p)` is an expression needing evaluation
;; (p) ; `p` is looked up in the environment and substituted
;; ((p)) ; ad infinitum. there is no completion.
;;; normal order ("fully expand, then apply"):
;; (test 0 (p)) ; `test` is looked up in the environment
;; (if (= 0 0) 0 (p)) ; the body of `test` is substituted
;; (= 0 0) ; the predicate of the `if` statement is evaluated to true
;; 0 ; 0 is returned. `(p)` is never evaluated
;;; 1.6
;;; If `new-if` is used the procedure will not complete. The interpreter,
;;; implemented using applicative order, will evaluate the arguments for their
;;; values before applying `new-if`. the `else-clause` of `new-if` calls
;;; `square-biter`. The examples work because they do not contain recursive
;;; calls.
;;; 1.7
;;; note: I am prefixing with 1.7- to avoid collision with any existing
;;; procedures
(define (1.7-square x) (* x x))
(define (1.7-sqrt-iter guess x)
(if (1.7-good-enough? guess x)
guess
(1.7-sqrt-iter (1.7-improve guess x) x)))
(define (1.7-improve guess x)
(1.7-average guess (/ x guess)))
(define (1.7-average x y)
(/ (+ x y) 2))
(define (1.7-good-enough? guess x)
(< (abs (- (1.7-square guess) x)) 0.001))
(define (1.7-sqrt x)
(1.7-sqrt-iter 1.0 x))
;;; re: The good-enough? test used in computing square roots will not be very
;;; effective for finding the square roots of very small numbers.
;;; Answer: `good-enough?` uses a tolerance of 0.001, which defines the lower
;;; bound of how small our potential square root could be. Anything less than
;;; 0.001 will result in `good-enough?` returning true for a value we know to
;;; be incorrect.
(1.7-sqrt 0.0001) ; 0.03230844833048122
;;; re: Also, in real computers, arithmetic operations are almost always
;;; performed with limited precision. This makes our test inadequate for very
;;; large numbers.
;;; Answer: I take limited precision to mean that a number is represented by a
;;; fixed number of digits, possibly with one digit n representing 10^n. This
;;; means that `good-enough?` may never be supplied with an argument that can
;;; represent the value to the thousandths place (0.001), meaning that the
;;; iteration will continue indefinitely.
;; (1.7-sqrt 10000000000000) ; I run forever
;;; re: An alternative strategy for implementing good-enough? is to watch how
;;; guess changes from one iteration to the next and to stop when the change is
;;; a very small fraction of the guess. Design a square-root procedure that
;;; uses this kind of end test. Does this work better for small and large
;;; numbers?
(define (1.7-improved-sqrt-iter guess guess-prev x)
(if (1.7-improved-good-enough? guess guess-prev)
guess
(1.7-improved-sqrt-iter (1.7-improve guess x) guess x)))
(define (1.7-improved-good-enough? guess guess-prev)
(< (abs (- guess guess-prev)) 0.001))
(define (1.7-improved-sqrt x)
(1.7-improved-sqrt-iter 1.0 x x))
(1.7-improved-sqrt 4)
;;; better!
(1.7-improved-sqrt 0.0001) ; 0.010000714038711746
;;; still an issue with very large numbers giving wrong answer because the
;;; precision is not sufficient to represent the potential root *and* the
;;; decimal place necessary for the comparison
(1.7-improved-sqrt 10000000000000) ; 3162277.6601683795
;;; 1.8
(define (1.8-square x) (* x x))
(define (1.8-cube x) (* x x x))
(define (1.8-cube-root-iter guess x)
(if (1.8-cube-good-enough? guess x)
guess
(1.8-cube-root-iter (1.8-cube-improve guess x) x)))
(define (1.8-cube-improve y x)
(/ (+ (/ x (1.8-square y)) (* 2 y)) 3))
(define (1.8-cube-good-enough? guess x)
(< (abs (- (1.8-cube guess) x)) 0.001))
(define (1.8-cube-root x)
(1.8-cube-root-iter 1.0 x))
(1.8-cube-root 27)
;;; 1.9
;; (define (+ a b)
;; (if (= a 0)
;; b
;; (inc (+ (dec a) b))))
;;; this is a recursive process. the amount of information required to keep
;;; track (e.g. the `inc` calls) scales with the size of `n`. its process
;;; illustration is:
;; (+ 4 5)
;; (inc (+ (dec 4) 5))
;; (inc (+ 3 5))
;; (inc (inc (+ (dec 3) 5)))
;; (inc (inc (+ 2 5)))
;; (inc (inc (inc (+ (dec 2) 5))))
;; (inc (inc (inc (+ 1 5))))
;; (inc (inc (inc (inc (+ (dec 1) 5)))))
;; (inc (inc (inc (inc (+ 0 5)))))
;; (inc (inc (inc (inc 5))))
;; (inc (inc (inc 6)))
;; (inc (inc 7))
;; (inc 8)
;; 9
;; (define (+ a b)
;; (if (= a 0)
;; b
;; (+ (dec a) (inc b))))
;;; this is an iterative process. the amount of information required to
;;; represent its state is fixed. its process illustration is:
;; (+ 4 5)
;; (+ (dec 4) (inc 5))
;; (+ 3 6)
;; (+ (dec 3) (inc 6))
;; (+ 2 7)
;; (+ (dec 2) (inc 7))
;; (+ 1 8)
;; (+ (dec 1) (inc 8))
;; (+ 0 9)
;; 9
;;; 1.10
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
(A 1 10) ; 1024
(A 2 4) ; 65536
(A 3 3) ; 65536
(define (f n) (A 0 n))
(f 0) ; 0
(f 1) ; 2
(f 2) ; 4
(f 3) ; 6
(f 4) ; 8
;;; f(n) = 2n
(define (g n) (A 1 n))
(g 0) ; 0
(g 1) ; 2
(g 2) ; 4
(g 3) ; 8
(g 4) ; 16
;;; g(0) = 0 for n = 0
;;; g(n) = 2^n for 0 < n
(define (h n) (A 2 n))
(h 0) ; 0 0
(h 1) ; 2 2^1 2
(h 2) ; 4 2^2 4
(h 3) ; 16 2^4 16
(h 4) ; 65536 2^16
;;; note: I could not figure out the mathematical function for `h`. I looked at
;;; answers here: https://sicp-solutions.net/post/sicp-solution-exercise-1-10/
;;; h(0) = 0
;;; h(n) = 2^h(n-1)
(define (k n) (* 5 n n))
;;; k(n) = 5n^2
;;; 1.11
(define (1.11/f-rec n)
(cond ((< n 3) n)
(else (+ (1.11/f-rec (- n 1))
(* 2 (1.11/f-rec (- n 2)))
(* 3 (1.11/f-rec (- n 3)))))))
(1.11/f-rec 1) ; 1
(1.11/f-rec 2) ; 2
(1.11/f-rec 3) ; 4
(1.11/f-rec 4) ; 11
(1.11/f-rec 5) ; 25
(1.11/f-rec 6) ; 59
;;; n can always be calculated if you know the n-1, n-2, and n-3 values. So we
;;; make the state comprised of them, plus the iteration number we are
;;; "calculating up" from, and the n value we wish to calculate.
(define (1.11/f-iter-helper n1 n2 n3 iter n)
(if (= iter n)
(+ n1 (* 2 n2) (* 3 n3))
(1.11/f-iter-helper (+ n1 (* 2 n2) (* 3 n3)) n1 n2 (+ iter 1) n))
)
(define (1.11/f-iter n)
(cond ((< n 3) n)
(else (1.11/f-iter-helper 2 1 0 3 n))))
(1.11/f-iter 1) ; 1
(1.11/f-iter 2) ; 2
(1.11/f-iter 3) ; 4
(1.11/f-iter 4) ; 11
(1.11/f-iter 5) ; 25
(1.11/f-iter 6) ; 59
;;; 1.12
(define (pascal-calc i j)
(cond ((= j 0) 1)
((= i j) 1)
((< i j) 0) ; assume returning 0 is OK for invalid coordinate
(else (+ (pascal-calc (- i 1) (- j 1)) (pascal-calc (- i 1) j)))))
(pascal-calc 0 0) ; 1
(pascal-calc 0 1) ; 0 invalid coordinate test
(pascal-calc 1 0) ; 1
(pascal-calc 1 1) ; 1
(pascal-calc 2 0) ; 1
(pascal-calc 2 1) ; 2
(pascal-calc 2 2) ; 1
(pascal-calc 3 0) ; 1
(pascal-calc 3 1) ; 3
(pascal-calc 3 2) ; 3
(pascal-calc 3 3) ; 1
(pascal-calc 4 0) ; 1
(pascal-calc 4 1) ; 4
(pascal-calc 4 2) ; 6
(pascal-calc 4 3) ; 4
(pascal-calc 4 4) ; 1
;;; 1.13
;;; skipped
;;; 1.14
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0)
(= kinds-of-coins 0))
0)
(else
(+ (cc amount (- kinds-of-coins 1))
(cc (- amount (first-denomination
kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))
;;; (count-change 11) time complexity grows as the square of n splitting twice
;;; for every amount over 5, the cube of n splitting three times for every
;;; amount over 10, ^4 splitting 4 times for amounts over 25 and ^5 times for
;;; amounts over 50. its space requirements grow linearly with n.
;;; 1.15
(define (cube x) (* x x x))
(define (p x) (display x) (newline) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0)))))
(sine 12.15)
;;; 1. `p` is applied 5 times
;;; 2a. growth of time: logarithmic. `angle` is divided by 3.0 each invocation,
;;; so the number of operations is log_3(a / 0.1)
;;; 2b. growth of space: also logarithmic, for the same reasons.
;;; 1.16
;;; key here is to realize that we want to reduce n to 0 as quickly as
;;; possible. the provided identities hint to us that we can halve n by
;;; squaring b. our invariant, ab^n, is preserved.
;;; implementation note: I found that starting to write the implementation of
;;; fast-exp-iter, even when I did not know the solution, helped arrive at the
;;; answer.
(define (fast-exp-iter b n a)
(define (square x) (* x x))
(cond ((= n 0) a)
((even? n) (fast-exp-iter (square b) (/ n 2) a))
(else (fast-exp-iter b (- n 1) (* a b)))))
(define (fast-exp b n)
(fast-exp-iter b n 1))
(fast-exp 4 4)
;;; 1.17
;;; same approach here as 1.16: recognize that there is invariant in: (xy +
;;; a). and in this case the transformation is xy = (x/2)(2y)
(define (fast-mult-iter x y a)
(define (double x) (* x 2))
(define (halve x) (/ x 2))
(cond ((= y 0) a)
((even? y) (fast-mult-iter (double x) (halve y) a))
(else (fast-mult-iter x (- y 1) (+ a x)))))
(define (fast-mult x y)
(fast-mult-iter x y 0))
(fast-mult 20 5)
;;; 1.18
;;; see answer to 1.17, it is iterative
;;; 1.19
;;; a ← bq + aq + ap
;;; b ← bp + aq
;;; Show that if we apply such a transformation T_pq twice, the effect is the
;;; same as using a single transformation T_p'q' of the same form. compute p'
;;; and q' in terms of p and q.
;;; a_1 = b_0 * q + a_0 * q + a_0 * p
;;; b_1 = b_0 * p + a_0 * q
;;; plug in:
;;; a_2 = (b_0 * p + a_0 * q) * q + (b_0 * q + a_0 * q + a_0 * p) * q + (b_0 * q + a_0 * q + a_0 * p) * p
;;; b_2 = (b_0 * p + a_0 * q) * p + (b_0 * q + a_0 * q + a_0 * p) * q
;;; combine:
;;; a_2 = b_0 * p * q + a_0 * q * q + b_0 * q * q + a_0 * q * q + a_0 * p * q + b_0 * q * p + a_0 * q * p + a_0 * p * p
;;; b_2 = b_0 * p * p + a_0 * q * p + b_0 * q * q + a_0 * q * q + a_0 * p * q
;;; group:
;;; a_2 = a_0 * q * q + a_0 * q * q + a_0 * p * q + b_0 * p * q + b_0 * q * q + b_0 * q * p + a_0 * q * p + a_0 * p * p
;;; b_2 = a_0 * q * p + a_0 * q * q + a_0 * p * q + b_0 * p * p + b_0 * q * q
;;; reduce:
;;; a_2 = b_0 (2pq + 2q^2) + a_0 (2q^2 + 2pq + p^2)
;;; b_2 = b_0 (p^2 + q^2) + a_0 (2pq + q^2)
;;; so looking at b_2 and the original transformations we can see that p' is
;;; (p^2 + q^2) and q` is (2pq + q^2). plugging into a_2 verifies this.
(define (fib n)
(fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
(cond ((= count 0)
b)
((even? count)
(fib-iter a
b
(+ (* p p) (* q q))
(+ (* 2 p q) (* q q))
(/ count 2)))
(else
(fib-iter (+ (* b q)
(* a q)
(* a p))
(+ (* b p)
(* a q))
p
q
(- count 1)))))
(fib 10) ; 55
;;; 1.20
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
;;; normal order
(gcd 206 40)
(if (= 40 0) 206 (gcd 40 (remainder 206 40))) ;false
(gcd 40 (remainder 206 40))
(if (= (remainder 206 40) 0) 40 (gcd (remainder 206 40) (remainder 40 (remainder 206 40)))) ; 1 remainder eval
(if (= 6 0) 40 (gcd (remainder 206 40) (remainder 40 (remainder 206 40)))) ; false
(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))
(if (= (remainder 40 (remainder 206 40)) 0) (...)) ;2 remainder eval
(if (= 4 0) (...)) ;false
;;; etc etc. remainder is applied some number greater than 3 times
;;; applicative order
(gcd 206 40)
(gcd 40 (remainder 206 40)) ; remainder applied
(gcd 40 6)
(gcd 6 (remainder 40 6)) ; remainder applied
(gcd 6 4)
(gcd 4 (remainder 6 4)) ; remainder applied
(gcd 4 2)
(gcd 2 (remainder 4 2)) ; remainder applied
(gcd 2 0)
;;; remainder is applied 4 times
;;; 1.21
(define (divides? a b)
(= (remainder b a) 0))
(define (square x) (* x x))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n)
n)
((divides? test-divisor n)
test-divisor)
(else (find-divisor
n
(+ test-divisor 1)))))
(define (smallest-divisor n)
(find-divisor n 2))
(smallest-divisor 199) ; 199
(smallest-divisor 1999) ; 1999
(smallest-divisor 19999) ; 7
;;; 1.22
(define (prime? n)
(if (< n 2)
#f
(= n (smallest-divisor n))))
(define (timed-prime-test n)
(newline)
(display n)
(start-prime-test n (current-time)))
;;; modified to explicitly return a boolean
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime (- (current-time)
start-time))
#f))
;;; modified to explicitly return a boolean
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time)
#t)
;;; Using this procedure, write a procedure search-for-primes that checks the
;;; primality of consecutive odd integers in a specified range.
(define (search-for-primes lower-bound upper-bound max-count)
(define (driver n count)
(cond ((= count max-count) count)
((< upper-bound n) count)
((even? n) (driver (+ n 1) count))
((timed-prime-test n) (driver (+ n 2) (+ count 1)))
(else (driver (+ n 2) count))))
(driver lower-bound 0))
;;; `current-time` is not granular enough to determine timing differences
(search-for-primes 1000 10000 3)
(search-for-primes 10000 100000 3)
(search-for-primes 100000 1000000 3)
;;; 1.23
;;; punted implementation. if our problem goes from sqrt(n) to sqrt(n/2) a ~2x
;;; speedup is expected but because it is a constant factor the order of growth
;;; is still sqrt(n) for large numbers.
;;; 1.24
;;; punted
;;; 1.25
;;; punted
;;; 1.26
;;; reasoning: the arguments to the explicit multiply square are evaluated
;;; twice rather than just once.
;;; 1.27
;;; punted
;;; 1.28
;;; punted
;;; 1.29
(define (identity x) x)
(define (inc n) (+ n 1))
(define (cube x) (* x x x))
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
(define (sum-integers a b)
(sum identity a inc b))
(define (simpsons-integral f a b n)
(define h (/ (- b a) n))
(define (y k) (f (+ a (* k h))))
(define (term k)
(* (cond ((= k 0) 1)
((= k n) 1)
((even? k) 2)
(else 4))
(y k)))
(* (/ h 3) (sum term 0 inc n)))
(simpsons-integral cube 0.0 1.0 100) ; 0.24999999999999992
(simpsons-integral cube 0.0 1.0 1000) ; 0.2500000000000003
;;; 1.30
(define (sum term a next b)
(define (iter a result)
(if (< b a)
result
(iter (next a) (+ (term a) result))))
(iter a 0))
;;; testing
(define (sum-integers a b)
(sum identity a inc b))
(sum-integers 0 10) ; 55
;;; 1.31
(define (product-rec term a next b)
(if (< b a)
1
(* (term a)
(product-rec term (next a) next b))))
(define (product-iter term a next b)
(define (iter a acc)
(if (< b a)
acc
(iter (next a) (* acc (term a)))))
(iter a 1))
(define (factorial n product)
(product identity 1 inc n))
(factorial 6 product-rec) ; 720
(factorial 6 product-iter) ; 720
(define (pi-approx n)
(define (term k)
(cond ((odd? k) (/ (+ k 1) (+ k 2)))
(else (/ (+ k 2) (+ k 1)))))
(* 4 (product-iter term 1.0 inc n)))
(pi-approx 10) ; 3.2751010413348065
(pi-approx 100) ; 3.1570301764551654
(pi-approx 1000) ; 3.1431607055322552
(pi-approx 10000) ; 3.1417497057380084
;;; 1.32
;;; part 1 - recursive
(define (accumulate-rec combiner null-value term a next b)
(if (< b a)
null-value
(combiner (term a) (accumulate-rec combiner null-value term (next a) next b))))
;;; part 2 - iterative
(define (accumulate-iter combiner null-value term a next b)
(define (iter i result)
(if (< b i)
result
(iter (next i) (combiner result (term i)))))
(iter a null-value))
(define (accumulate combiner null-value term a next b)
(accumulate-iter combiner null-value term a next b))
;;; product
(define (product-acc term a next b)
(accumulate * 1 term a next b))
;;; sum
(define (sum-acc term a next b)
(accumulate + 0 term a next b))
;;; testing
(define (factorial-acc n)
(product-acc identity 1 inc n))
(factorial-acc 6) ; 720
(define (sum-integers-acc a b)
(sum-acc identity a inc b))
(sum-integers-acc 0 10) ; 55
;;; 1.33
(define (filtered-accumulate combiner null-value term a next b predicate)
(define (iter i result)
(if (< b i)
result
(iter (next i)
(if (predicate i)
(combiner result (term i))
result))))
(iter a null-value))
;;; part 1
(define (sum-of-squares-of-primes a b)
(filtered-accumulate + 0 square a inc b prime?))
;;; part 2
(define (product-relatively-prime a b)
(define (relatively-prime i) (= 1 (gcd i b)))
(filtered-accumulate * 1 identity a inc b relatively-prime))
;;; testing
(sum-of-squares-of-primes 1 6) ; 38
(product-relatively-prime 1 10) ; 189
;;; 1.34
(define (f g) (g 2))
(f f)
;;; evaluation is:
;;; (f f)
;;; (f 2)
;;; (2 2) ; error
;;; 1.35 punted
;;; 1.36 punted
;;; 1.37 punted
;;; 1.38 punted
;;; 1.39 punted
;;; 1.40 punted
;;; 1.41 punted
;;; 1.42 punted
;;; 1.43 punted
;;; 1.44 punted
;;; 1.45 punted
;;; 1.46 punted
chapter-2.scm
;;; solutions to exercises from SICP Chapter 2
;;; 2.1
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
;;; the idea here is to create new local variables n-prime and d-prime which
;;; are adjusted such that n-prime represents the sign of the resulting
;;; rational and d-prime is always positive.
(define (make-rat n d)
(let ((n-prime (cond ((and (< n 0) (< d 0)) (- 0 n)) ; numer neg, denom neg, rat pos
((and (< n 0) (< 0 d)) n) ; numer neg, denom pos, rat neg
((and (< 0 n) (< d 0)) (- 0 n)) ; numer pos, denom neg, rat neg
(else n)))
(d-prime (cond ((< d 0) (- 0 d)) ;always make denom positive
(else d)))
(g (gcd n d)))
(cons (/ n-prime g)
(/ d-prime g))))
(make-rat 9 12) ; (3 . 4)
(make-rat -9 12) ; (-3 . 4)
(make-rat 9 -12) ; (-3 . 4)
(make-rat -9 -12) ; (3 . 4)
;;; 2.2
(define (make-point x y) (cons x y))
(define (x-point p) (car p))
(define (y-point p) (cdr p))
(define (make-segment p1 p2) (cons p1 p2))
(define (start-segment s) (car s))
(define (end-segment s) (cdr s))
(define (print-point p)
(newline)
(display "(")
(display (x-point p))
(display ",")
(display (y-point p))
(display ")")
(newline))
(define (average-point p1 p2)
(define (average x1 x2) (/ (+ x1 x2) 2.0))
(make-point (average (x-point p1) (x-point p2))
(average (y-point p1) (y-point p2))))
(define (midpoint-segment s)
(average-point (start-segment s) (end-segment s)))
(define (print-midpoint x1 y1 x2 y2)
(print-point (midpoint-segment (make-segment (make-point x1 y1) (make-point x2 y2)))))
;;; 2.3
;;; our abstraction barriers are at rect-length and rect-width
(define (rect-area r)
(* (rect-length r) (rect-width r)))
(define (rect-perimeter r)
(+ (* 2 (rect-length r) ) (* 2 (rect-width r) )))
;;; implementation 1, using a point, length, and width
(define (make-rect p l w) (cons p (cons l w)))
(define (rect-length r) (car (cdr r)))
(define (rect-width r) (cdr (cdr r)))
(define rect-a (make-rect (make-point 1 1) 2 4))
(rect-area rect-a) ; 8
(rect-perimeter rect-a) ; 12
;;; implementation 2, using opposite corner points
(define (make-rect p1 p2) (cons p1 p2))
(define (rect-length r) (abs (- (x-point (cdr r)) (x-point (car r)))))
(define (rect-width r) (abs (- (y-point (cdr r)) (y-point (car r)))))
(define rect-a (make-rect (make-point 0 0) (make-point 2 4)))
(rect-area rect-a) ; 8
(rect-perimeter rect-a) ; 12
;;; 2.4
(define (cons x y)
(lambda (m) (m x y)))
(define (car z)
(z (lambda (p q) p)))
(define (cdr z)
(z (lambda (p q) q)))
(car (cons 1 2)) ; 1
(cdr (cons 1 2)) ; 2
;;; verification
(cdr (cons 1 2)) ; eval (cons 1 2)
(cdr (lambda (m) (m 1 2))) ; substitute cons
((lambda (m) (m 1 2)) (lambda (p q) q)) ; sub cdr
((lambda (p q) q) 1 2) ; eval: invoke (m 1 2) with (lambda (p q) q) as m
(lambda (1 2) 2) ; eval: invoke (lambda (p q) q) with 1 and 2
2 ; eval: return 2
;;; 2.5 punted
;;; 2.6
(define zero (lambda (fz) (lambda (xz) xz)))
(define (add-1 n)
(lambda (fa) (lambda (xa) (fa ((n fa) xa)))))
(define one (add-1 zero))
(define one (lambda (fa) (lambda (xa) (fa ((zero fa) xa))))) ; sub body of add-1
(define one (lambda (fa) (lambda (xa) (fa ((lambda (xz) xz) xa))))) ; sub body of zero
(define one (lambda (fa) (lambda (xa) (fa xa)))) ; eval
(define two (add-1 one))
(define two (lambda (fa) (lambda (xa) (fa ((one fa) xa))))) ; sub body add-1
(define two (lambda (fa) (lambda (xa) (fa (((lambda (fa) (lambda (xa) (fa xa))) fa) xa))))) ; sub body one
(define two (lambda (fa) (lambda (xa) (fa ((lambda (xa) (fa xa)) xa))))) ; eval
(define two (lambda (fa) (lambda (xa) (fa (fa xa))))) ; eval
;;; 2.7
(define (lower-bound i) (car i))
(define (upper-bound i) (cdr i))
;;; 2.8
;;; rationale: imagine we have the interval (0.5, 0.8) and (0.6, 0.7). the
;;; lowest bound the subtraction could be is the lowest value of x minus the
;;; highest value of y. the highest bound it could be is the upper bound of x
;;; minus the lowest value of y
(define (sub-interval x y)
(make-interval (- (lower-bound x)
(upper-bound y))
(- (upper-bound x)
(lower-bound y))))
;;; 2.9 punted
;;; 2.10 punted
;;; 2.11 punted
;;; 2.12 punted
;;; 2.13 punted
;;; 2.14 punted
;;; 2.15 punted
;;; 2.16 punted
;;; 2.17
(define (last-pair l)
(if (null? (cdr l))
(car l)
(last-pair (cdr l))))
(last-pair (list 23 72 149 34)) ; 34
;;; 2.18
;;; notes: I initially wrote this in a way that constructed lists with inverted
;;; cons usage, like (cons (cons (cons 4 3) 2) 1). the key for me was to write
;;; out the cases I wanted to work and how I wanted the cons structure to be
;;; framed. (see below). from there I wrote reverse-helper naively and came up
;;; with the implementation below
(define (reverse original-list)
(define (reverse-helper remaining-list reversed-list)
(if (null? (cdr remaining-list))
(cons (car remaining-list) reversed-list)
(reverse-helper (cdr remaining-list) (cons (car remaining-list) reversed-list))))
(reverse-helper original-list #nil))
(reverse (list 1)) ; (1)
;; (cons 1 #nil)
(reverse (list 1 2)) ; (2 1)
;; (cons 2 1)
(reverse (list 1 2 3)) ; (3 2 1)
;; (cons 3 (cons 2 1))
(reverse (list 1 2 3 4)) ; (4 3 2 1)
;; (cons 4 (cons 3 (cons 2 1)))
;;; 2.21
(define (square x) (* x x))
(define (square-list items)
(if (null? items)
#nil
(cons (square (car items)) (square-list (cdr items)))))
(square-list (list 1 2 3)) ; (1 4 9)
(define (square-list items)
(map (lambda (x) (* x x)) items))
(square-list (list 1 2 3)) ; (1 4 9)
;;; 2.22
;;; re: reverse order first attempt
;;; for (list 1 2 3) `iter` forms the chain:
;;; (iter (list 2 3) (cons 1 nil))
;;; (iter (list 3) (cons 4 (cons 1 nil)))
;;; (iter nil (cons 9 (cons 4 (cons 1 nil))))
;;; re: reverse order second attempt
;;; for (list 1 2 3) `iter` forms the chain:
;;; (iter (list 2 3) (cons nil 1))
;;; (iter (list 3) (cons (cons nil 1) 4))
;;; (iter nil (cons (cons (cons nil 1) 4) 9))
;;; this form does not satisfy the condition for a list that (car l) is the
;;; first item or that (cdr l) is the remainder
;;; 2.23
(define (my-for-each proc items)
(if (null? items)
#t
(and (proc (car items)) (my-for-each proc (cdr items)))))
(my-for-each (lambda (x) (and (display x) (newline))) (list 1 2 3))
;;; 2.24 punted
;;; 2.25
(car (cdr (car (cdr (cdr (list 1 3 (list 5 7) 9))))))
(car (car (list (list 7))))
(cadadr (cadadr (cadadr (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))))
;;; 2.26
;; (append x y)
;; $14 = (1 2 3 4 5 6)
;; (cons x y)
;; $15 = ((1 2 3) 4 5 6)
;; (list x y)
;; $16 = ((1 2 3) (4 5 6))
;;; 2.27
(define (deep-reverse original-list)
(define (reverse-helper remaining-list reversed-list)
(cond ((null? remaining-list) reversed-list)
((pair? (car remaining-list)) (reverse-helper (cdr remaining-list) (cons (deep-reverse (car remaining-list)) reversed-list)))
(else (reverse-helper (cdr remaining-list) (cons (car remaining-list) reversed-list)))))
(reverse-helper original-list #nil))
(define x
(list (list 1 2) (list 3 4)))
;;; 2.28
(define (fringe tree)
(cond ((null? tree) #nil)
((not (pair? tree)) (list tree))
(else (append (fringe (car tree))
(fringe (cdr tree))))))
(define x
(list (list 1 2) (list 3 4)))
(fringe x) ; (1 2 3 4)
(fringe (list x x)) ; (1 2 3 4 1 2 3 4)
;;; 2.29 punted
;;; 2.30 punted
;;; 2.31 punted
;;; 2.32 punted
;;; 2.33
(define (my-accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(my-accumulate op
initial
(cdr sequence)))))
(define (my-map p sequence)
(my-accumulate (lambda (next acc) (cons (p next) acc))
#nil sequence))
(my-map (lambda (x) (* x x)) (list 1 2 3 4)) ; (1 4 9 16)
(define (my-append seq1 seq2)
(my-accumulate cons seq2 seq1))
(my-append (list 1 2) (list 3 4)) ; (1 2 3 4)
(define (my-length sequence)
(my-accumulate (lambda (next acc) (+ 1 acc)) 0 sequence))
(my-length (list 1 2 3 4)) ; 4
;;; 2.34 punted
;;; 2.35
(define (count-leaves t)
(my-accumulate + 0 (map (lambda (n) (if (pair? n) (count-leaves n) 1)) t)))
(count-leaves (list 1 (list 2 3) (list 4))) ; 4
;;; 2.36
(define (my-accumulate-n op init seqs)
(if (null? (car seqs))
#nil
(cons (my-accumulate op init (my-map car seqs))
(my-accumulate-n op init (my-map cdr seqs)))))
(define s (list (list 1 2 3) (list 4 5 6) (list 7 8 9) (list 10 11 12)))
(my-accumulate-n + 0 s) ; (22 26 30)
;;; 2.37 punted
;;; 2.38
(define fold-right my-accumulate)
(define (fold-left op initial sequence)
(define (iter result rest)
(if (null? rest)
result
(iter (op result (car rest))
(cdr rest))))
(iter initial sequence))
(fold-right / 1 (list 1 2 3)) ; 3/2
(fold-left / 1 (list 1 2 3)) ; 1/6
(fold-right list #nil (list 1 2 3)) ; (1 (2 (3 #nil)))
(fold-left list #nil (list 1 2 3)) ; (((#nil 1) 2) 3)
;;; `op` must be associative for both `fold-right` and `fold-left` to return
;;; the same results. e.g. * or +
(fold-right + 1 (list 1 2 3)) ; 7
(fold-left + 1 (list 1 2 3)) ; 7
(fold-right * 1 (list 1 2 3)) ; 6
(fold-left * 1 (list 1 2 3)) ; 6
;;; 2.39
(define (reverse-right sequence)
(fold-right
(lambda (next acc) (append acc (list next))) #nil sequence))
(define (reverse-left sequence)
(fold-left
(lambda (next acc) (append (list acc) next)) #nil sequence))
(reverse-right (list 1 2 3 4)) ; (4 3 2 1)
(reverse-left (list 1 2 3 4)) ; (4 3 2 1)
;;; 2.40
(define (enumerate-interval low high)
(if (> low high)
#nil
(cons low
(enumerate-interval
(+ low 1)
high))))
(define (unique-pairs n)
(flatmap (lambda (i)
(map (lambda (j) (list i j))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))
(unique-pairs 3) ; ((2 1) (3 1) (3 2))
(define (divides? a b)
(= (remainder b a) 0))
(define (square x) (* x x))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n)
n)
((divides? test-divisor n)
test-divisor)
(else (find-divisor
n
(+ test-divisor 1)))))
(define (smallest-divisor n)
(find-divisor n 2))
(define (prime? n)
(if (< n 2)
#f
(= n (smallest-divisor n))))
(define (prime-sum? pair)
(prime? (+ (car pair) (cadr pair))))
(define (make-pair-sum pair)
(list (car pair)
(cadr pair)
(+ (car pair) (cadr pair))))
(define (prime-sum-pairs n)
(map make-pair-sum
(filter prime-sum? (unique-pairs n))))
(prime-sum-pairs 6) ; ((2 1 3) (3 2 5) (4 1 5) (4 3 7) (5 2 7) (6 1 7) (6 5 11))
;;; 2.41
;;; Write a procedure to find all ordered triples of distinct positive integers
;;; i, j, and k less than or equal to a given integer n that sum to a given
;;; integer s.
(define (unique-triples n)
(flatmap (lambda (i)
(flatmap (lambda (j)
(map (lambda (k) (list i j k))
(enumerate-interval 1 (- j 1))))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))
(unique-triples 3) ; ((3 2 1))
(unique-triples 4) ; ((3 2 1) (4 2 1) (4 3 1) (4 3 2))
(define (sum-ordered-triples n s)
(define (sums-to t) (= s (+ (car t) (cadr t) (caddr t))))
(filter sums-to (unique-triples n)))
(sum-ordered-triples 7 7) ; ((4 2 1))
(sum-ordered-triples 10 20) ; ((8 7 5) (9 6 5) (9 7 4) (9 8 3) (10 6 4) (10 7 3) (10 8 2) (10 9 1))
;;; 2.42 punted
;;; 2.43 punted
;;; 2.44 punted
;;; 2.45 punted
;;; 2.46 punted
;;; 2.47 punted
;;; 2.48 punted
;;; 2.49 punted
;;; 2.50 punted
;;; 2.51 punted
;;; 2.52 punted
;;; 2.53
(define a 1)
(define b 2)
(define c 3)
(list 'a 'b 'c) ; (a b c)
(list (list 'george)) ; ((george))
(cdr '((x1 x2) (y1 y2))) ; ((y1 y2))
(cadr '((x1 x2) (y1 y2))) ; (y1 y2)
(pair? (car '(a short list))) ; #f
(memq 'red '((red shoes) (blue socks))) ; #f
(memq 'red '(red shoes blue socks)) ; (red shoes blue socks)
;;; 2.54 punted
;;; 2.55 punted
;;; 2.56 punted
;;; 2.57 punted
;;; 2.58 punted
;;; 2.59 punted
;;; 2.60 punted
;;; 2.61 punted
;;; 2.62 punted
;;; 2.63 punted
;;; 2.64 punted
;;; 2.65 punted
;;; 2.66 punted
;;; 2.67 punted
;;; 2.68 punted
;;; 2.69 punted
;;; 2.70 punted
;;; 2.71 punted
;;; 2.72 punted
;;; 2.73 punted
;;; 2.74 punted
;;; 2.75 punted
;;; 2.76 punted
;;; 2.77 punted
;;; 2.78 punted
;;; 2.79 punted
;;; 2.80 punted
;;; 2.81 punted
;;; 2.82 punted
;;; 2.83 punted
;;; 2.84 punted
;;; 2.85 punted
;;; 2.86 punted
;;; 2.87 punted
;;; 2.88 punted
;;; 2.89 punted
;;; 2.90 punted
;;; 2.91 punted
;;; 2.92 punted
;;; 2.93 punted
;;; 2.94 punted
;;; 2.95 punted
;;; 2.96 punted
;;; 2.97 punted
understanding-flatmap.scm
;;; understanding flatmap
(define (my-accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(my-accumulate op
initial
(cdr sequence)))))
(define (enumerate-interval low high)
(if (> low high)
#nil
(cons low
(enumerate-interval
(+ low 1)
high))))
(enumerate-interval 1 3) ; (1 2 3)
;;; I'm having trouble understanding the difference in intention / operation
;;; between the following invocation, which is `flatmap`:
(my-accumulate
append
#nil
(map (lambda (i)
(map (lambda (j)
(list i j))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 3))) ; ((2 1) (3 1) (3 2))
;;; and just the map-based operation:
(map (lambda (i)
(map (lambda (j)
(list i j))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 3)) ; (() ((2 1)) ((3 1) (3 2)))
;;; what are we conceptually trying to do by accumulating with append?
;;; I think of the result `(() ((2 1)) ((3 1) (3 2)))` as being the list of
;;; lists for each `i`: 1 makes the empty list (), 2 makes the list containing
;;; one sublist ((2 1)) and 3 makes the list containing two sublists ((3 1) (3
;;; 2)).
;;; when we use my-accumulate, we are appending the members of each of these
;;; lists together.
;;; `map` is for A -> B mapping
;;; `flatmap` is for A -> (list B) concatenation
(define (flatmap proc seq)
(my-accumulate append #nil (map proc seq)))
;;; the following do not work:
(flatmap + (list 1 2 3))
(flatmap (lambda (x) (* x x)) (list 1 2 3))
;;; the following works:
(flatmap (lambda (x) (enumerate-interval x 3)) (list 1 2 3)) ; (1 2 3 2 3 3)
Terminology
- abstraction
- 1.
The separation of the use from the implementation.
Related:
- applicative-order evaluation
- 1.
Evaluate the arguments, then apply.
Related:
- atom
- 1.
- binding
- 1.
The association of a variable to a procedure.
Related:
- block structure
- 1.
The nesting of definitions within a procedure.
Related:
- bound variable
- 1.
A variable local to a procedure.
Related:
- capturing
- 1.
The binding of an expression (typically a variable) to a procedure.
- case analysis
- 1.
Taking different actions based on conditions.
Related:
- clause
- 1.
An expression following a cond
Related:
- closed under
- 1.
A set of elements is said to be closed under an operation if applying the operation to elements in the set produces an element that is again an element of the set.
Related:
- closure
- 1.
An implementation technique for representing procedures with free variables.
Related:
- combination
- 1.
An expression, comprised of other expressions, in a list, contained within parentheses.
Related:
- consequent
- 1.
The resulting value of the conditional expression whose predicate evaluates to true
Related:
- data
- 1.
The "stuff" we want to manipulate!
Related:
- data abstraction
- 1.
A methodology for structuring systems in such a way that much of a program can be specified independent of the choices involved in implementing the data objects that the program manipulates.
Related:
- derived expression
- 1.
- environment
- 1.
The memory within which a computation executes.
Related:
- expression
- 1.
A construct that returns a value.
Related:
- free variable
- 1.
A variable that is not bound.
Related:
- global environment
- 1.
- integration of algebraic equations
- 1.
- interpreter
- 1.
A machine that carries out procedures described in the Lisp language.
- Lisp
- 1.
LISt Processing.
- lexical scoping
- 1.
Free variables in a procedure are taken to refer to bindings made by enclosing procedure definitions.
Related:
- list
- 1.
- normal-order evaluation
- 1.
Fully expand, then reduce.
Related:
- operands
- 1.
The remaining elements within a combination.
Related:
- operator
- 1.
The leftmost element within a combination.
Related:
- order
- 1.
The position of an element within a sequence; does not imply sorted.
- predicate
- 1.
A procedure or expression that evaluates to true or false.
Related:
- prefix notation
- 1.
The convention of placing the operator to the left of the operands.
Related:
- primitive expression
- 1.
The simplest entities a language is concerned with; numerals, built-in operators, and other names.
Related:
- procedure
- 1.
Descriptions of the instructions for manipulating data; evaluated as expressions.
Related:
- process
- 1.
The execution of procedures within a computing environment.
Related:
- REPL (Read Eval Print Loop)
- 1.
- recursion
- 1.
The act of a procedure calling itself.
- referential transparency
- 1.
- robustness
- 1.
The likelihood that small changes in a specification will require correspondingly small changes in the program.
- scope
- 1.
The expressions for which a variable is bound; typically the body of a procedure.
Related:
- special form
- 1.
Exceptions to the general evaluation rule, like define
- substitution model
- 1.
- symbol
- 1.
- symbolic differentiation
- 1.
- tree accumulation
- 1.
Percolating values upward.