commit f7b93a4391a94ec25333c0f9dee972b3a1c6e4ec
parent 730f1989c05b6c11ebc940bccddf1e7dc3e8c8f6
Author: Yuval Langer <yuval.langer@gmail.com>
Date: Sat, 15 Apr 2023 01:13:01 +0300
Add ASCII art and helpful comments about unspecified order of evaluation in procedure applications.
Diffstat:
2 files changed, 213 insertions(+), 0 deletions(-)
diff --git a/sicp/solutions/3_9.scm b/sicp/solutions/3_9.scm
@@ -0,0 +1,210 @@
+(define-library (sicp solutions 3_9)
+ (import (scheme base))
+
+ (begin
+ (define (recursive-factorial-global-environment)
+ (define (factorial n)
+ (if (= n 1)
+ 1
+ (* n (factorial (- n 1)))))
+
+;;; +--------------------+
+;;; | |
+;;; global -->| factorial: --+ |
+;;; env | | |
+;;; +--------------|-----+
+;;; +---+ ^
+;;; | |
+;;; V |
+;;; .---.---. |
+;;; | O | O-+---+
+;;; `-|-^---'
+;;; |
+;;; V
+;;; parameters: n
+;;; body: (if (= n 1)
+;;; 1
+;;; (* n (factorial (- n 1))))
+;;;
+;;; global env
+;;; |
+;;; V
+;;; +----+
+;;; | | E1 (factorial 6)
+;;; | | |
+;;; | | V
+;;; | | +------+
+;;; | | | n: 6 | (if (= n 1)
+;;; | | +------+ 1
+;;; | | | (* n (factorial (- n 1))))
+;;; | |<--+
+;;; | |
+;;; | | E2 (factorial 5)
+;;; | | |
+;;; | | V
+;;; | | +------+
+;;; | | | n: 5 | (if (= n 1)
+;;; | | +------+ 1
+;;; | | | (* n (factorial (- n 1))))
+;;; | |<--+
+;;; | |
+;;; | | E3 (factorial 4)
+;;; | | |
+;;; | | V
+;;; | | +------+
+;;; | | | n: 4 | (if (= n 1)
+;;; | | +------+ 1
+;;; | | | (* n (factorial (- n 1))))
+;;; | |<--+
+;;; | |
+;;; | | E4 (factorial 3)
+;;; | | |
+;;; | | V
+;;; | | +------+
+;;; | | | n: 3 | (if (= n 1)
+;;; | | +------+ 1
+;;; | | | (* n (factorial (- n 1))))
+;;; | |<--+
+;;; | |
+;;; | | E5 (factorial 2)
+;;; | | |
+;;; | | V
+;;; | | +------+
+;;; | | | n: 2 | (if (= n 1)
+;;; | | +------+ 1
+;;; | | | (* n (factorial (- n 1))))
+;;; | |<--+
+;;; | |
+;;; | | E6 (factorial 1)
+;;; | | |
+;;; | | V
+;;; | | +------+
+;;; | | | n: 1 | (if (= n 1)
+;;; | | +------+ 1
+;;; | | | (* n (factorial (- n 1))))
+;;; | |<--+
+;;; +----+
+ )
+
+ (define (iterative-factorial-global-environment)
+ (define (factorial n)
+ (fact-iter 1 1 n))
+
+ (define (fact-iter product
+ counter
+ max-count)
+ (if (> counter max-count)
+ product
+ (fact-iter (* counter product)
+ (+ counter 1)
+ max-count)))
+
+;;; +------------------------------+
+;;; | fact-iter: -------------+ |
+;;; global -->| | |
+;;; env | factorial: --+ | |<-+
+;;; +--------------|----------|----+ |
+;;; +---+ ^ | |
+;;; | | | |
+;;; V | V |
+;;; .---.---. | .---.---. |
+;;; | O | O-+---+ | O | O-+---+
+;;; `-|-^---' `-|-^---'
+;;; | |
+;;; V +--------+
+;;; parameters: n |
+;;; body: (fact-iter 1 1 n) +-> parameters: product, counter, max-count
+;;; body: (if (> counter max-count)
+;;; product
+;;; (fact-iter (* counter product)
+;;; global env (+ counter 1)
+;;; | max-count))
+;;; V
+;;; +----+
+;;; | | E1 (factorial 6)
+;;; | | |
+;;; | | V
+;;; | | +------+
+;;; | | | n: 6 | (fact-iter 1 1 n)
+;;; | | +------+
+;;; | | |
+;;; | |<--+
+;;; | |
+;;; | | E2 (fact-iter product counter max-count)
+;;; | | |
+;;; | | V
+;;; | | +--------------+
+;;; | | | product: 1 | (if (> counter max-count)
+;;; | | | counter: 1 | product
+;;; | | | max-count: 6 | (fact-iter (* counter product)
+;;; | | +--------------+ (+ counter 1)
+;;; | | | max-count))
+;;; | |<--+
+;;; | |
+;;; | | E3 (fact-iter product counter max-count)
+;;; | | |
+;;; | | V
+;;; | | +--------------+
+;;; | | | product: 1 | (if (> counter max-count)
+;;; | | | counter: 2 | product
+;;; | | | max-count: 6 | (fact-iter (* counter product)
+;;; | | +--------------+ (+ counter 1)
+;;; | | | max-count))
+;;; | |<--+
+;;; | |
+;;; | | E4 (fact-iter product counter max-count)
+;;; | | |
+;;; | | V
+;;; | | +--------------+
+;;; | | | product: 2 | (if (> counter max-count)
+;;; | | | counter: 3 | product
+;;; | | | max-count: 6 | (fact-iter (* counter product)
+;;; | | +--------------+ (+ counter 1)
+;;; | | | max-count))
+;;; | |<--+
+;;; | |
+;;; | | E5 (fact-iter product counter max-count)
+;;; | | |
+;;; | | V
+;;; | | +--------------+
+;;; | | | product: 6 | (if (> counter max-count)
+;;; | | | counter: 4 | product
+;;; | | | max-count: 6 | (fact-iter (* counter product)
+;;; | | +--------------+ (+ counter 1)
+;;; | | | max-count))
+;;; | |<--+
+;;; | |
+;;; | | E6 (fact-iter product counter max-count)
+;;; | | |
+;;; | | V
+;;; | | +--------------+
+;;; | | | product: 24 | (if (> counter max-count)
+;;; | | | counter: 5 | product
+;;; | | | max-count: 6 | (fact-iter (* counter product)
+;;; | | +--------------+ (+ counter 1)
+;;; | | | max-count))
+;;; | |<--+
+;;; | |
+;;; | | E7 (fact-iter product counter max-count)
+;;; | | |
+;;; | | V
+;;; | | +--------------+
+;;; | | | product: 120 | (if (> counter max-count)
+;;; | | | counter: 6 | product
+;;; | | | max-count: 6 | (fact-iter (* counter product)
+;;; | | +--------------+ (+ counter 1)
+;;; | | | max-count))
+;;; | |<--+
+;;; | |
+;;; | | E8 (fact-iter product counter max-count)
+;;; | | |
+;;; | | V
+;;; | | +--------------+
+;;; | | | product: 720 | (if (> counter max-count)
+;;; | | | counter: 7 | product
+;;; | | | max-count: 6 | (fact-iter (* counter product)
+;;; | | +--------------+ (+ counter 1)
+;;; | | | max-count))
+;;; | |<--+
+;;; +----+
+ )))
diff --git a/sicp/tests/3_8.scm b/sicp/tests/3_8.scm
@@ -9,5 +9,8 @@
(test-begin "3.8")
(test-equal
1 ; Turns out it starts with the right one.
+ ;; People of #scheme @ libera.chat say it is an implementation detail.
+ ;; The specification leaves the order of evaluation unspecified,
+ ;; and therefore one should avoid writing code that depends on it.
(+ (f 0) (f 1)))
(test-end "3.8")))
