;; Midterm solution --Amr ;; 1 (define prodprimes (lambda (n k) (if (= n 1) (k 1) (if (prime? n) (prodprimes (sub1 n) (lambda (v) (k (* n v)))) (prodprimes (sub1 n) k))))) (define prodprimes (lambda (n k) (if (= n 1) (k 1) (prime? n (lambda (v) (if v (prodprimes (sub1 n) (lambda (v) (k (* n v)))) (prodprimes (sub1 n) k))))))) ;; 2 [while (condition body) (letrec ([loop (lambda () (if (true? (eval condition env)) (begin (eval body env) (loop)) 0))]) (loop))] ;; 3 (define A (lambda (m n k) (if (zero? m) (k (add1 n)) (if (zero? n) (A (sub1 m) 1 k) (A m (sub1 n) (lambda (v) (A (sub1 m) v k))))))) ;; 4 fun = arg = 2 env = init-env ++ { countdown --> } [recproc (formal body) (make-dynproc formal body)] ;; 5 Possible conditions on SOME-OPERATION: - commutative and associative. - SOME-OPERATION(0,x) = 0 - no side effects Multiplication and addition are ok. Substraction and division are not. ;; 6 (scar (scons M N)) = (car (cons M (lambda (_) N))) by definition of scar, scons = M by axiom on regular pairs (cdr (scons M N)) = ((cdr (cons M (lambda (_) N))) 42) by definition of scdr, scons = ((lambda (_) N) 42) by axiom on regular pairs = N by beta-reduction [scons (head tail) (cons (eval head env) (make-closure _ tail env))] [scar (stream) (car (eval stream env))] [scdr (stream) (apply-proc (cdr (eval stream env)) 17)] ;; 7 (define search (lambda (lookfor tree) (go lookfor tree (lambda (path) path) (lambda () '())))) (define go (lambda (lookfor tree success failure) (variant-case tree [leaf () (failure)] [node (id contents left right) (if (eq? lookfor contents) (success (list id)) (go lookfor left (lambda (path) (success (cons (cons id 'L) path))) (lambda () (go lookfor right (lambda (path) (success (cons (cons id 'R) path))) failure))))]))) ;; 8 (define eval (lambda (exp outerk) (letrec ([loop (lambda (exp innerk) (variant-case exp [num (n) (innerk n)] [add (e1 e2) (loop e1 (lambda (v1) (loop e2 (lambda (v2) (innerk (+ v1 v2))))))] [div (e1 e2) (loop e1 (lambda (v1) (loop e2 (lambda (v2) (if (zero? v2) (outerk "infinity") (innerk (/ v1 v2)))))))]))]) (loop exp outerk)))) ;; Extra credit Transformation 1: Correct Transformation 2: Correct Transformation 3: Incorrect