;; Answers for Exam 1 in CIS 352, Spring 2008
;;
;; DISTRIBUTION OF SCORES
;;  range:   scores
;; 31- 40:   36  39
;; 41- 50:   43
;; 51- 60:   54  54  60
;; 61- 70;   63  65  66  67
;; 71- 80:   78  79
;; 81- 90:   84  86  86  90
;; 91-100:   95  98 100
;;
;; Average = 70.68   Median = 78
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; (displayln x1 x2 ... xn) 
;;   prints x1 ... xn separated by spaces and then prints a newline.

(define displayln
  (lambda lst
    (if (null? lst)
	(newline)
	(begin (display (car lst)) 
	       (display " ") 
	       (apply displayln (cdr lst))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Question 1 (20 points).
;; Suppose we have the following definitions:

(define x '(a b c))
(define y '(11 23 17))
(define z 4)
  
(define moe '(f g h i))
(define larry  (cons y z))
(define curly (append moe '((1 2) 3) ))

(define t
  (let ((y 6) (z 10) (w z))
    (let ((x (+ z w)) (y x))
      y)))

(define mystery 
  (lambda w (cdr w)))

;; Give the value of each of the following expressions:
(displayln "---Question 1---")
(displayln "Question 1a: "  (cadr moe))
(displayln "Question 1b: "  (cons '() moe))
(displayln "Question 1c: "  larry)
(displayln "Question 1d: "  'curly)
(displayln "Question 1e: "  (list x y))
(displayln "Question 1f: "  (map (lambda (z) (cons  z  'z)) x))
(displayln "Question 1g: "  t)
(displayln "Question 1h: "  (mystery  '(z)  y  '(c d e)))
(displayln "Question 1i: "  (eq? x '(a b c)))
(displayln "Question 1j: "  (apply cdr '((1 2))))
(displayln)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Question 2 (15 points).
;; (a) (4 points)  Given an example of a higher-order procedure that is
;;   built into Scheme, and briefly explain what makes it higher-order.
;;;; AN ANSWER: map because its first argument is a procedure.

;; (b) Fill in the indicated space below with a lambda-calculus 
;;   expression that creates a hole-in-the-scope of the u declared
;;   on line 1.
;;   (lambda (u)                  ;; line 1
;;           ((u x) (lambda (z)   ;; line 2
;;                                ;; <== FILL IN 
;;           )))                  ;;line 4
;;;; AN ANSWER: (lambda (u) (z u)) would do just fine.

;; (c) Draw the internal list structure that corresponds to the 
;;   following Scheme value:  ( 99 (e (g)) () (3 . x) )    

;;;; AN ANSWER:
;;;;
;;      +---+---+      +---+---+      +---+---+      +---+---+      
;;      |86 | ########>| # | ########>| / | ########>| # | / |
;;      +---+---+      +-#-+---+      +---+---+      +-#-+---+      
;;                       #                             #
;;                       #                             V
;;                       #                           +---+---+
;;                       #                           | 3 | x |
;;                       #                           +---+---+
;;                       V
;;                     +---+---+      +---+---+      
;;                     | e | ########>| # | / |
;;                     +---+---+      +-#-+---+      
;;                                      #
;;                                      V
;;                                    +---+---+      
;;                                    | g | / |
;;                                    +---+---+      


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Question 3 (12 points).
;;Consider the following expression:
;;   ((lambda (k w)               ;; line 1
;;      ((w t)                    ;; line 2
;;       (lambda (y t w)          ;; line 3
;;         ((y u)                 ;; line 4
;;          (lambda (t) (x k)))   ;; line 5
;;          )                     ;; line 6
;;       ))                       ;; line 7
;;    k)                          ;; line 8 

;; (a) (3 points) 
;;   What variables occur free in this expression?
;;;; Answer: t (line 2), u (line 4) and k (line 8).

;; (b) (3 points) 
;;   What variables occur bound in this expression?
;;;; Answer:  w (line 2), y (line 4), and k (line 5)


;; (c) (3 points) 
;;   What is the lexical address of the k on line 5?
;;;; Answer: (2,0)

;; (d) (3 points) 
;;   Which variable references (if any) have lexical address (0,1)
;;   in the expression?  
;;;; Answer: w on line 2

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Question 4 (9 points).
;; Write a Scheme procedure swap which, given a two-argument 
;; procedure fun, returns a new procedure that has the same
;; behavior as fun, except that it takes its two arguments 
;; in reverse order.  For example:
;;
;;    > (define swapped-cons (swap cons))
;;    > (swapped-cons 6 8)
;;    (8 . 6)
;;    > ((swap (lambda (x y) (list x y))) 3 10)
;;    (10 3)
;;;; An answer:
(define swap
  (lambda (fun)
    (lambda (x y) 
      (fun y x))))

(displayln "---Question 4---")
(define swapped-cons (swap cons))
(displayln "(swapped-cons 6 8) \n   =" (swapped-cons 6 8))
(displayln "((swap (lambda (x y) (list x y))) 3 10) \n   ="
           ((swap (lambda (x y) (list x y))) 3 10))
(displayln)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Question 5 (14 points).
;; Write a Scheme procedure average that takes an unbounded 
;; number of arguments and returns the average of these 
;; arguments. By convention, the average of an empty list is 
;; 0. For example: 
;;
;; > (average 1 2 3 4) ; (1 + 2 + 3 + 4)/4 = 2.5 
;; 2.5 
;; > (average 2 4 6) ; (2 + 4 + 6)/3 = 4 
;; 4 
;; > (average) 
;; 0 
;;;; An answer:
(define average 
  (lambda x
    (if (null? x)
        0
        (/ (apply + x) (length x)))))
  
(displayln "---Question 5---")
(displayln "(average 1 2 3 4)  \n   =" (average 1 2 3 4))
(displayln "(average 2 4 6) \n   =" (average 2 4 6))
(displayln "(average)  \n   =" (average))
(displayln)

(define sum-of-squares-too
  (lambda ns
    (apply + (map (lambda (x) (* x x)) ns))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Question 6 (14 points).
;; Write a Scheme procedure merge which, given to lists of 
;; numbers, lst1 and lst2, that are in smallest-to-largest order, 
;; returns the merger of these two lists in to a list of 
;; smallest-to-largest order. For example: 
;;   > (merge ’(1 2 5) ’(3 4 6)) 
;;   (1 2 3 4 5 6) 
;;   > (merge ’(1 2) ’(1 2 3)) 
;;   (1 1 2 2 3) 
;;   > (merge ’(0 30 50) ’(10)) 
;;   (0 10 30 50) 
;;;; An answer:
(define merge 
  (lambda (lst1 lst2)
    (cond
      ((null? lst1) lst2)
      ((null? lst2) lst1)
      ((< (car lst1) (car lst2))
       (cons (car lst1) (merge (cdr lst1) lst2)))
      (else
       (cons (car lst2) (merge lst1 (cdr lst2)))))))

(displayln "---Question 6---")
(displayln "(merge '(1 2 5) '(3 4 6))\n   = " (merge '(1 2 5) '(3 4 6)))
(displayln "(merge '(1 2) '(1 2 3))\n   = "   (merge '(1 2) '(1 2 3)))
(displayln "(merge '(0 30 50) '(10))\n   = "  (merge '(0 30 50) '(10)))
(displayln)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Question 7 (16 points).
;; An n-expression is just like an s-expression, except with numbers 
;; in place of symbols. The BNF for n-expressions is given by: 
;;    <n-exp>  ::= <number> | <n-list> 
;;    <n-list> ::= () | (<n-exp> . <n-list>) 
;;  Write a Scheme procedure sum which, given an n-expression, 
;; returns the sum of all the numbers in the n-expression. If 
;; there are no numbers in the n-expression (e.g., ()), then the 
;; procedure should return 0. For example: 
;;   > (sum 4) 
;;   4 
;;   > (sum '( () (()) ) ) 
;;   0 
;;   > (sum '(2 -4 10)) 
;;   8 
;;   > (sum '((-1 (2) 5) () ((3 4)))) 
;;   13 
;;;; An answer:
(define sum
  (lambda (nexp)
    (if (number? nexp)
        nexp
        (sum-nlst nexp))))

(define sum-nlst
  (lambda (nlst)
    (if (null? nlst)
        0
        (+ (sum (car nlst)) (sum-nlst (cdr nlst))))))

(displayln "---Question 7---")
(displayln "(sum 4) \n   =" (sum 4))
(displayln "(sum '( () (()) ) ) \n   =" (sum '( () (()) ) ))
(displayln "(sum '(2 -4 10)) \n   =" (sum '(2 -4 10)))
(displayln "(sum '((-1 (2) 5) () ((3 4)))) \n   ="
           (sum '((-1 (2) 5) () ((3 4)))) )

(define sum-too
  (lambda (nexp)
    (if (number? nexp)
        nexp
        (apply + (map sum-too nexp)))))

(define sum-also
  (define (nexp)
    (cond ((null? nexp) 0)
          ((number? nexp) nexp)
          (else (+ (sum-also (car nexp))
                   (sum-also (cdr nexp)))))))