-
Notifications
You must be signed in to change notification settings - Fork 1
/
4.2-Normal-Order.rkt
105 lines (76 loc) · 3.15 KB
/
4.2-Normal-Order.rkt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
;; *Exercise 4.25:* Suppose that (in ordinary applicative-order
;; Scheme) we define `unless' as shown above and then define
;; `factorial' in terms of `unless' as
;; (define (factorial n)
;; (unless (= n 1)
;; (* n (factorial (- n 1)))
;; 1))
;; What happens if we attempt to evaluate `(factorial 5)'? Will our
;; definitions work in a normal-order language?
;; Yes, it should, because it will stop when n = 1
;; *Exercise 4.26:* Ben Bitdiddle and Alyssa P. Hacker disagree over
;; the importance of lazy evaluation for implementing things such as
;; `unless'. Ben points out that it's possible to implement `unless'
;; in applicative order as a special form. Alyssa counters that, if
;; one did that, `unless' would be merely syntax, not a procedure
;; that could be used in conjunction with higher-order procedures.
;; Fill in the details on both sides of the argument. Show how to
;; implement `unless' as a derived expression (like `cond' or `let'),
;; and give an example of a situation where it might be useful to
;; have `unless' available as a procedure, rather than as a special
;; form.
;; If we make unless a special form, we cannot use it with list comprehensions,
;; or pass it in to other functions, or return it from functions. It no longer
;; would be "first class".
;; We could make it like cond or let by wrapping functions in lambdas.
(define (unless1 cond left right)
(if cond
(right)
(left)))
(unless1 true (lambda () 1) (lambda () 2))
;; *Exercise 4.27:* Suppose we type in the following definitions to
;; the lazy evaluator:
;; (define count 0)
;; (define (id x)
;; (set! count (+ count 1))
;; x)
;; Give the missing values in the following sequence of interactions,
;; and explain your answers.(5)
;; (define w (id (id 10)))
;; ;;; L-Eval input:
;; count
;; ;;; L-Eval value:
;; 0
;; ;;; L-Eval input:
;; w
;; ;;; L-Eval value:
;; 10
;; ;;; L-Eval input:
;; count
;; ;;; L-Eval value:
;; 2
;; The define will not have been evaluated yet, so until we try to
;; lookup the value of w, the counter will not have been incremented.
;; *Exercise 4.28:* `Eval' uses `actual-value' rather than `eval' to
;; evaluate the operator before passing it to `apply', in order to
;; force the value of the operator. Give an example that
;; demonstrates the need for this forcing.
;; (define (g x) (+ x 1))
;; (define (f g x) (g x))
;; (f g 10)
;; *Exercise 4.29:* Exhibit a program that you would expect to run
;; much more slowly without memoization than with memoization. Also,
;; consider the following interaction, where the `id' procedure is
;; defined as in *Note Exercise 4-27:: and `count' starts at 0:
;; (define (square x)
;; (* x x))
;; ;;; L-Eval input:
;; (square (id 10))
;; ;;; L-Eval value:
;; 100
;; ;;; L-Eval input:
;; count
;; ;;; L-Eval value:
;; (if memoizing? 1 2)
;; Give the responses both when the evaluator memoizes and when it
;; does not.