commit 7b651346810e7ff013aba39a29c4a2170899f2ca
parent 7119ca02436b98b2c6bc3e11ac73ec1c1a68a8b9
Author: Yuval Langer <yuval.langer@gmail.com>
Date: Tue, 21 Nov 2023 21:22:52 +0200
Add two rewrites.
Diffstat:
4 files changed, 161 insertions(+), 140 deletions(-)
diff --git a/sicp/solutions/chapter-1/exercise-10.scm b/sicp/solutions/chapter-1/exercise-10.scm
@@ -1,108 +1,24 @@
-
-#!
-
-*Exercise 1.10:* The following procedure computes a mathematical
-function called Ackermann's function.
-
-(define (A x y)
- (cond ((= y 0) 0)
- ((= x 0) (* 2 y))
- ((= y 1) 2)
- (else (A (- x 1)
- (A x (- y 1))))))
-
-What are the values of the following expressions?
-
-(A 1 10)
-
-(A 2 4)
-
-(A 3 3)
-
-Consider the following procedures, where `A' is the procedure
-defined above:
-
-(define (f n) (A 0 n))
-
-(define (g n) (A 1 n))
-
-(define (h n) (A 2 n))
-
-(define (k n) (* 5 n n))
-
-Give concise mathematical definitions for the functions computed
-by the procedures `f', `g', and `h' for positive integer values of
-n. For example, `(k n)' computes 5n^2.
-
-
-(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)
-(cond ((= 10 0) 0)
- ((= 1 0) (* 2 10))
- ((= 10 1) 2)
- (else (A (- 1 1)
- (A 1 (- 10 1)))))
-(A (- 1 1)
- (A 1 (- 10 1)))
-(A 0 (A 1 9))
-(A 0 (A 0 (A 1 8)))
-(A 0 (A 0 (A 0 (A 1 7))))
-(A 0 (A 0 (A 0 (A 0 (A 1 6)))))
-(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
-(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
-(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
-(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))
-(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
-(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
-(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 2)))))))))
-(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
-(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
-(A 0 (A 0 (A 0 (A 0 (A 0 32)))))
-(A 0 (A 0 (A 0 (A 0 64))))
-(A 0 (A 0 (A 0 128)))
-(A 0 (A 0 256))
-(A 0 512)
-1024
-
-(define (A x y)
- (cond ((= y 0) 0)
- ((= x 0) (* 2 y))
- ((= y 1) 2)
- (else (A (- x 1)
- (A x (- y 1))))))
-
-
-(A 2 4)
-(cond ((= 4 0) 0)
- ((= 2 0) (* 2 4))
- ((= 4 1) 2)
- (else (A (- 2 1)
- (A 2 (- 4 1)))))
-(A 1
- (A 1 (A 2 (- 3 1))))
-
-(A 1
- (A 1 (A 2 (- 3 1))))
-(A 1
- (A 1 (A 2 (- 3 1))))
-
-
-!#
-
-(define (A x y)
- (cond ((= y 0) 0)
- ((= x 0) (* 2 y))
- ((= y 1) 2)
- (else (A (- x 1)
- (A x (- y 1))))))
-
-(test-begin "1.10")
-'(test-equal 1024 (A 1 10))
-'(test-equal 1024 (A 2 4))
-(test-end "1.10")
+(define-library (sicp solutions chapter-1 exercise-10)
+ (import (scheme base))
+ (export A
+ f
+ g
+ h
+ k)
+
+ (begin
+ (define (A x y)
+ ;; SICP lied to us! This is not the Ackermann functinon!
+ (cond ((= y 0) 0)
+ ((= x 0) (* 2 y))
+ ((= y 1) 2)
+ (else (A (- x 1)
+ (A x (- y 1))))))
+
+ (define (f n) (A 0 n))
+
+ (define (g n) (A 1 n))
+
+ (define (h n) (A 2 n))
+
+ (define (k n) (* 5 n n))))
diff --git a/sicp/solutions/chapter-1/exercise-11.scm b/sicp/solutions/chapter-1/exercise-11.scm
@@ -1,36 +1,34 @@
+(define-library (sicp solutions chapter-1 exercise-11)
+ (import (scheme base))
+ (export f-recursive
+ f-iterative)
-#!
+ #!
-*Exercise 1.11:* A function f is defined by the rule that f(n) = n
-if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n>= 3.
-Write a procedure that computes f by means of a recursive process.
-Write a procedure that computes f by means of an iterative
-process.
+ *Exercise 1.11:* A function f is defined by the rule that f(n) = n
+ if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n>= 3.
+ Write a procedure that computes f by means of a recursive process.
+ Write a procedure that computes f by means of an iterative
+ process.
-!#
+ !#
+ (begin
+ (define (f-recursive n)
+ (cond
+ ((< n 3) n)
+ (else (+ (f-recursive (- n 1))
+ (* 2 (f-recursive (- n 2)))
+ (* 3 (f-recursive (- n 3)))))))
-(define (f-recursive n)
- (cond
- ((< n 3) n)
- (else (+ (f-recursive (1- n))
- (* 2 (f-recursive (- n 2)))
- (* 3 (f-recursive (- n 3)))))))
-
-(define (f-iterative n)
- (define (f i n a b c)
- (cond
- ((= i n) a)
- (else (f (1+ i)
- n
- b
- c
- (+ c
- (* 2 b)
- (* 3 a))))))
- (f 0 n 0 1 2))
-
-(test-begin "1.11")
-(test-equal
- (map f-recursive '(0 1 2 3 4 5 6 7))
- (map f-iterative '(0 1 2 3 4 5 6 7)))
-(test-end "1.11")
+ (define (f-iterative n)
+ (define (f i n a b c)
+ (cond
+ ((= i n) a)
+ (else (f (+ i 1)
+ n
+ b
+ c
+ (+ c
+ (* 2 b)
+ (* 3 a))))))
+ (f 0 n 0 1 2))))
diff --git a/sicp/tests/chapter-1/exercise-10.scm b/sicp/tests/chapter-1/exercise-10.scm
@@ -0,0 +1,96 @@
+(define-library (sicp tests chapter-1 exercise-10)
+ (import (scheme base)
+ (scheme eval)
+ (srfi :1)
+ (srfi :64)
+ (sicp solutions chapter-1 exercise-10))
+
+;;; XXX: No solution.
+
+ (begin
+
+
+ (test-begin "chapter-1-exercise-10")
+
+ (for-each
+ (lambda (test-expr)
+ (test-equal
+ (A 1 10)
+ (eval test-expr
+ (environment '(scheme base)
+ '(sicp solutions chapter-1 exercise-10)))))
+ '((A 1 10)
+ (cond ((= 10 0) 0)
+ ((= 1 0) (* 2 10))
+ ((= 10 1) 2)
+ (else (A (- 1 1)
+ (A 1 (- 10 1)))))
+ (A (- 1 1)
+ (A 1 (- 10 1)))
+ (A 0 (A 1 9))
+ (A 0 (A 0 (A 1 8)))
+ (A 0 (A 0 (A 0 (A 1 7))))
+ (A 0 (A 0 (A 0 (A 0 (A 1 6)))))
+ (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
+ (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
+ (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
+ (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))
+ (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
+ (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
+ (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 2)))))))))
+ (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
+ (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
+ (A 0 (A 0 (A 0 (A 0 (A 0 32)))))
+ (A 0 (A 0 (A 0 (A 0 64))))
+ (A 0 (A 0 (A 0 128)))
+ (A 0 (A 0 256))
+ (A 0 512)
+ 1024))
+
+
+ (A 2 4)
+
+ (A 3 3)
+
+
+
+ (A 2 4)
+ (cond ((= 4 0) 0)
+ ((= 2 0) (* 2 4))
+ ((= 4 1) 2)
+ (else (A (- 2 1)
+ (A 2 (- 4 1)))))
+ (A 1
+ (A 1 (A 2 (- 3 1))))
+
+ (A 1
+ (A 1 (A 2 (- 3 1))))
+ (A 1
+ (A 1 (A 2 (- 3 1))))
+
+
+ (do ((i 0 (+ i 1)))
+ ((> i 10))
+ (test-equal
+ (* 2 i)
+ (f i)))
+
+ (do ((i 0 (+ i 1)))
+ ((> i 10))
+ (test-equal
+ (expt 2 i)
+ (g i)))
+
+ (do ((i 0 (+ i 1)))
+ ((> i 5))
+ (test-equal
+ (do ((m i (- m 1))
+ (s (expt 1 2) (expt 2 s)))
+ ((= m 0) s))
+ (h i)))
+
+ '(test-equal 1024 (A 1 10))
+ '(test-equal 1024 (A 2 4))
+
+ (test-end "chapter-1-exercise-10")
+ ))
diff --git a/sicp/tests/chapter-1/exercise-11.scm b/sicp/tests/chapter-1/exercise-11.scm
@@ -0,0 +1,11 @@
+(define-library (sicp tests chapter-1 exercise-11)
+ (import (scheme base)
+ (srfi :64)
+ (sicp solutions chapter-1 exercise-11))
+
+ (begin
+ (test-begin "chapter-1-exercise-11")
+ (test-equal
+ (map f-recursive '(0 1 2 3 4 5 6 7))
+ (map f-iterative '(0 1 2 3 4 5 6 7)))
+ (test-end "chapter-1-exercise-11")))
