;; Answers for Exam 2

;; ***DISTRIBUTION OF SCORES***
;; Range    Scores
;; 21-30:   28
;; 31-40:   34 39
;; 41-50:   46 50
;; 51-60:   55 56
;; 61-70:   64 65 65 65 66 68     
;; 71-80:   74 76 77           
;; 81-90:   83 89 90
;; 91-100:  97
;;
;; Average: 64.35      Median: 65.5

(define displayln
  (lambda xs
    (letrec 
	((prn (lambda (ys)
		(if (null? ys)
		    (newline)
		    (begin (display (car ys))
			   (display " ")
			   (prn (cdr ys)))))))
      (prn xs))))

;; Question 1 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(displayln "\n===Question 1===\n")

(define a 7) 
(define b 11) 
(define c 13) 

(define lst '((1 2) ((a) (b) c) (3)) )

(define p
  (let ((a 0) (b 2) (c b))
    (let ((a b))
      (list a b c))))
      
(define quandary (lambda z (list z)))

(displayln "Q1a: (cadr lst)             ~~> " (cadr lst))
(displayln "Q1b: (cons a 'lst)          ~~> " (cons a 'lst))
(displayln "Q1c: (map cdr lst)          ~~> " (map cdr lst))
(displayln "Q1d: (quandary 4 5 6)       ~~> " (quandary 4 5 6))
(displayln "Q1e: p                      ~~> " p)
(displayln "Q1f: (apply cdr '((a b c))) ~~> " (apply cdr '((a b c))))

;; Question 2 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(displayln "\n===Question 2===\n")
(displayln "See the source")


;; a) abstract syntax 
;;    See Pages 51--53 in EOPL or 
;;    http://en.wikipedia.org/wiki/Abstract_syntax
;;    Ex: Our interpreters represent 12 by: (num-val 12)

;; b) closure = a procedure's abstract syntax + its defining env.
;;    Ex: the procedures built by make-accumulator in Problem 5
;;    include a private variable x in their defining env.

;; c) higher-order procedure 
;;    A procedure that takes a procedural value as a parameter or
;;    produces it as a value.
;;    Ex: map or (lambda (f g) (lambda (x) (f (g x))))

;; d) hole in a scope 
;;    Within the scope of a variable, x, there can be another
;;    declaration of x, and within the scope of the 2nd declaration
;;    of x, the binding of first version of x is hidden.
;;    Ex: (let ((x 100)) (+ x (let ((x 1)) (+ x 3))))
;;               ^                   ^     =======
;;               1st                2nd    hole in the 1st x's scope

;; e) lexical address 
;;    The lexical address of a variable occurrence is the 
;;    number of contours you cross in order to get to the 
;;    variable's declaration.  (EOPL convention has you count from 0.)
;;    Ex: (let ((x 10)) 
;;          (let ((i 1)) 
;;            (let ((z 99))
;;               (+ x y z))))
;;  lex addrs:      2 1 0

;; f) syntactic category 
;;    Either the nonterminal symbols of a grammar or
;;    the set of terms derivable from said nonterminal.
;;    Ex: In the grammar 
;;       <expression> ::= <identifier> 
;;                      | <number> 
;;                      | -(<expression>,<expression>
;;       the set of expressions = the terms produced by <expression>

;; Question 3 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(displayln "\n===Question 3===\n")

(define-datatype mobile mobile?
  (rod    (rw number?) (m1 mobile?) (m2 mobile?))
  (bauble (bw number?)))

(define m1 (bauble 12))
(define m2 (rod 1 (bauble 3) (bauble 10)))
(define m3 (rod 3 
		(rod 1 (bauble 7) (rod 1 (bauble 3) (bauble 3))) 
		(bauble 15)))

;; Question 3a
;; (heft m) returns the total weight of mobile m.
(define heft 
  (lambda (m)
    (cases mobile m
	   (rod (rw m1 m2)
		(+ rw (heft m1) (heft m2)))
	   (bauble (bw) 
		   bw))
    ))

(displayln "Q3a: (heft m1) ~~>" (heft m1))
(displayln "Q3a: (heft m2) ~~>" (heft m2))
(displayln "Q3a: (heft m3) ~~>" (heft m3))
(newline)

;; (balance? m) returns the total weight of mobile m, if m is balanced
;;              and returns #f if m is not balanced.
;; Recall (and e1 ... en) returns #f if any of the ei's is #f 
;;        and otherwise returns the value of en.
(define balanced?
  (lambda (m)
    (cases mobile m
	   (rod (rw m1 m2)
		(let ((w1 (balanced? m1))
		      (w2 (balanced? m2)))
		  (and w1 w2 (= w1 w2) (+ rw w1 w2))))
	   (bauble (bw) bw))))

(displayln "Q3b: (balanced? m1) ~~>" (balanced? m1))
(displayln "Q3b: (balanced? m2) ~~>" (balanced? m2))
(displayln "Q3b: (balanced? m3) ~~>" (balanced? m3))

;; Question 4 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(displayln "\n===Question 4===\n")

(displayln "Q4a: " 
           (let ((x 10) (c 100) (m 1000))
             (let ((p (lambda (x) (+ m x))))
               (let ((q (lambda (m) (+ c (p (+ m x))))))
                 (let ((x 20) (c 200))
                   (q 1))))))

(displayln "Q4b:   222")

;; Here is why. Remember, this is under dynamic scoping.
;; When we evaluate (q 1) the environment is:
;;    [c=200]
;;      [x=20]
;;        [q={formal: m, body: (+ x (p (+ m x)))}]
;;          [p={formal: x, body: (+ m x)}]
;;            [m=1000]
;;              [c=100]
;;                [x=10]
;; when we evaluate the body of q the environment is:
;;  [m=1]
;;    [c=200]
;;      [x=20]
;;        [q={formal: m, body: (+ x (p (+ m x)))}]
;;          [p={formal: x, body: (+ m x)}]
;;            [m=1000]
;;              [c=100]
;;                [x=10]
;;    So c=200, m=1, and x=20.
;;    So we call p with argument 21 = 20+1.
;; when we evaluate the body of p the environment is:
;; [x=21]
;;  [m=1]
;;    [c=200]
;;      [x=20]
;;        [q={formal: m, body: (+ x (p (+ m x)))}]
;;          [p={formal: x, body: (+ m x)}]
;;            [m=1000]
;;              [c=100]
;;                [x=10]
;;     so m=1, x=21, and +(m,x) returns 22

;; So when we finish up the evaluation of the body of q we have
;;    +(c,(p +(m,x))) = +(200,22) = 222



(displayln "Q4c: " 
           (let ((x 10) (c 100) (m 1000))
             (let ((p (lambda (x) (+ m x))))
               (let ((q (lambda (m) (+ c (p (+ m x))))))
                 (let ((x 20) (c 200))
                   (q (p 1)))))))

(displayln "Q4b:  2222")

;; Here is why. Remember, this is under dynamic scoping.
;; When we evaluate (q (p 1)) the environment is:
;;      [c=200]
;;        [x=20]
;;          [q={formal: m, body: (+ x (p (+ m x)))}]
;;            [p={formal: x, body: (+ m x)}]
;;              [m=1000]
;;                [c=100]
;;                  [x=10]
;; We do the (p 1) evaluation first. 
;; So when we evaluate the body of p the environment is:
;;   [x=1]
;;    [c=200]
;;      [x=20]
;;        [q={formal: m, body: (+ x (p (+ m x)))}]
;;          [p={formal: x, body: (+ m x)}]
;;            [m=1000]
;;              [c=100]
;;                [x=10]
;;    So +(m,x) = +(1000,1) = 1001
;; Now we have to apply q to 1001.
;; when we evaluate the body of q the environment is:
;;  [m=1001]
;;    [c=200]
;;      [x=20]
;;        [q={formal: m, body: (+ x (p (+ m x)))}]
;;          [p={formal: x, body: (+ m x)}]
;;            [m=1000]
;;              [c=100]
;;                [x=10]
;;    So c=200, m=1001, and x=20.
;;    So we call p with argument 1001+20 = 1021
;; when we evaluate the body of p the environment is:
;; [x=1021]
;;  [m=1001]
;;    [c=200]
;;      [x=20]
;;        [q={formal: m, body: (+ x (p (+ m x)))}]
;;          [p={formal: x, body: (+ m x)}]
;;            [m=1000]
;;              [c=100]
;;                [x=10]
;;     so m=1001, x=1021, and +(m,x) returns 1022

;; So when we finish up the evaluation of the body of q we have
;;    +(c,(p +(m,x))) = +(200,2022) = 2222

;; Question 5 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(displayln "\n===Question 5===\n")

(define make-accumulator 
  (lambda () 
    (let ((x 10)) 
      (lambda (y) 
        (set! x (+ x y)) 
        x)))) 

(define x 20) 
(define acc1 (make-accumulator)) 
;; acc1 has its own private variable x which shadows the x 
;;      declared in ``(define x 20)''
(define acc2 (make-accumulator)) 
;; acc1 has its own private variable x which shadows the x 
;;      declared in ``(define x 20)''
(define acc3 acc1) ;; so acc3 and acc1 name the same thing!

(displayln "Q5: (acc1 5)        ~~>" (acc1 5))
;; So acc1's private x is set to 10+5 = 15 and 15 is returned

(displayln "Q5: (acc2 7)        ~~>" (acc2 7))
;; So acc2's private x is set to 10+7 = 17 and 17 is returned

(displayln "Q5: (acc1 (acc2 4)) ~~>" (acc1 (acc2 4)))
;; So  1: acc2's private x is set to 17+4=21 and 21 is returned
;; and 2: acc1's private x is set to 15+21=36 and 36 is returned

(displayln "Q5: (acc3 1)        ~~>" (acc3 1))
;; Since acc3 and acc1 are names for the same thing.
;; (acc3 1) has the same effect as (acc1 1)
;; Hence acc1's private x is set to 37 and 37 is returned.

(displayln "Q5: x               ~~>" x)
;; Since acc1 and acc2 where working with different bindings of x
;; The global x has its value unchanged.

;; Question 6 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(displayln "\n===Question 6===\n")
(displayln "See the source")

;; Question 6a
;;   (sqr-exp (exp1)
;;      (let ((n (expval->num (value-of exp1))))
;;         (num-val (* n n)))

;; Question 6b
;;   (and-exp (exp1 exp2)
;;      (if (expval->bool (value-of exp1 env))
;;          (value-of exp2 env) ;; only evaluated when exp1 ~~> true
;;          (bool-val #f)))

;; Question 6c, version 1 --- recursive calls of value-of
;;   (for-exp (count proc exp1)
;;      (let ((n (expval->num (value-of count env))))
;;        (if (zero? n)
;;            (value-of exp1 env)
;;            (let ((newval   (value-of (call-exp proc exp1) env))
;;                  (newcount (numval (- n 1))))
;;              (value-of (for-exp newcount proc newval))))))

;; Question 6c, version 2 --- a recursion inside of value-of
;;   (for-exp (count proc exp1)
;;      (let ((m (expval->num (value-of count env)))
;;            (p (expval->proc (value-of proc env)))
;;            (v (value-of exp1 env)))
;;        (letrec ((step (lambda (n val)
;;                          (if (zero? n) 
;;                              val
;;                              (step (- n 1) (apply-proc p val))))))
;;          (step m v)))