Chris Pollett>Old Classes>PIC 15, Fall 1999>Hw1>HW1 Solution
; Ex 1.2
; The expression in prefix form would be:
; (/
; (+ 5 (+ 4 (- 2 (- 3 (+ 6 (/ 4 5))))))
; (* 3 (* (- 6 2) (- 2 7)))
; )
; Ex 1.5
;
; The code we are considering is
;
; (define (p) (p))
;
; (define (test x y)
; (if (= x 0)
; 0
; y))
; )
;
; Basically, running (p) causes scheme to go into an infinite loop.
;
; Thus, if we type run (test 0 (p)) and we are evaluating under
; applicative order we will try to evaluate both arguments to
; test and when we try to evaluate (p) we will go into an
; infinite loop. On the other hand, when we evaluate
; (test 0 (p)) under normal order we will first replace test
; with its body where the argument 0 and (p) have been
; substituted in. We would then check (= 0 0) which is true
; and so output 0.
; Ex 1.14
;
; We are supposed to draw the tree of the count change procedure
; in making change for 11 cents. We will write out the cc
; procedure calls (since its hard to draw tree using text):
;
; 1. (cc 11 5)
; 2. (cc 11 4) (cc -39 5)
; 3. (cc 11 3) (cc -14 4) 0
; 3. (cc 11 2) (cc 1 2) 0
; 4. (cc 11 1) (cc 6 2) (cc 1 1) (cc -4 2)
; 5. (cc 11 0) (cc 10 1) (cc 6 1) (cc 1 2) (cc 1 0) (cc 0 1) 0
; 6. 0 (cc 10 0) (cc 9 1) (cc 6 0) (cc 5 1) (cc 1 1) (cc -4 2) 0 1
; 7. 0 (cc 9 0) (cc 8 1) 0 (cc 5 0) (cc 4 1) (cc 1 0) (cc 0 1) 0
; 8. 0 (cc 8 0) (cc 7 1) 0 (cc 4 0) (cc 3 1) 0 1
; 9. 0 (cc 7 0) (cc 6 1) 0 (cc 3 0) (cc 2 1)
; 10. 0 (cc 6 0) (cc 5 1) 0 (cc 2 0) (cc 1 1)
; 11. 0 (cc 5 0) (cc 4 1) 0 (cc 1 0) (cc 0 1)
; 12. 0 (cc 4 0) (cc 3 1) 0 1
; 13. 0 (cc 3 0) (cc 2 1)
; 14. 0 (cc 2 0) (cc 1 1)
; 15. 0 (cc 1 0) (cc 0 1)
; 16. 1
;As an example of how this would look in tree form the first 0 in
;line 8 is the daughter of the node (cc 9 0) in line 7 and the
;(cc 8 0) and (cc 7 1) in line 8 are the daughters of (cc 8 1) in line 7
;,etc... Now let's consider the order of growth of this process where
; we use the five coin types we had specified. The evaluation process
; is depth first, so the amount of space we will use grows as the length
; of the longest path through the evaluation tree. (There could be
; that many +'s waiting to be evaluated.) Since at each level
; we either decrease the amount we are making change for by 1 or the
; types of coins by 1 the length of the longest path is at most the
; amount+5. This path length will actually be achieved since one of our
; coin types is the penny.
; Thus we get \theta(amount) for the space used.
; On the other hand, we will get 2^{\theta(amount)} for the time used.
; To see this notice if every leaf of the tree on the amount+5th level
; we would have 1+2+4+8+16+ +2^{amount+k} nodes in our tree and this
; would be an upper bound on the time up to a constant factor.
; Multiplying this sum by (2 - 1) we see it actually equals
; 2^{amount+5+1} -1 < 2^{2 amount} for amount >6.
; To see that there is also a lower bound of the form 2^{K amount}
; we need to consider what is the shortest possible path in the tree.
; This corresponds to path where we repeated substract off half dollars
; which is of length [amount/50]. Thus the tree will have at least
; 2^{[amount/50]+1}-1 nodes and for amount > 1
; this is bigger than 2^{[amount/50]}.
;
; Ex 1.34
; We are asked to consider the function:
;
; (define (f g) (g 2))
;
; and answer what happens when we try to evaluate (f f).
;
; Substituting f for g in the body of f gives (f 2) as the first step
; in the evaluation. We would then substitute 2 for g in the body
; of f giving (2 2). But since 2 is not an operation it cannot
; be applied to 2 so we'd get an error to this effect.
;
; Ex 1.43
;
; (compose f g)
;
; Purpose:
; ========
; This functional returns the function which results from composing
; the functions f and g
;
; Known Bugs:
; ===========
; None
(define (compose f g)
(lambda (x)
(f (g x))
)
)
;
; (repeated f n)
;
; Purpose:
; ========
; If f is 1-ary this functional returns the function which results
; from f with itself n times
;
; Known Bugs:
; ===========
; None
(define (repeated f n)
(if (> n 0)
(compose f (repeated f (- n 1)))
(lambda (x) x)
)
)
;
; Examples
;
(define (square x) (* x x)) ;function which outputs x^2
(define (g x) ((repeated square 3) x)) ;function which outputs
; ((x^2)^2)^2)
; i.e., x^8