;;;=================================================================
;;;                       Problem Set 1 Solutions;
;;;               CS 370 --- LISP: Language and Literature
;;;=================================================================


;;; PROBLEM 1-a

; expression                    ; simplifies to
; ----------------------------- ; --------------
234                             ; 234
(+ 2 3)                         ; 5
(/ 10 2)                        ; 5
(/ 10 3)                        ; 3
(1+ 10000)                      ; 10001
(1- 10000)                      ; 9999
(= 4 (* 2 2))                   ; $TRUE
(= 12 (* 3 (/ 12 3)))           ; $TRUE
(= 12 (* 3 (/ 13 3)))           ; $TRUE
(< 10 20)                       ; $TRUE
(set b 20)                      ; 20
(set a (1+ b))                  ; 21
(* a b)                         ; 420



;;; PROBLEM 1-b

(if (= [10] [(+ 5 5)])
    (+ 10 5)
    (- 10 5))                  ; simplifies to 15


(define CAREFUL-DIVISION
   (lambda [n1 n2]
      (if (= n2 0)
          "cannot do it"
          (/ n1 n2))))


; Though / causes an error when its second argument is 0, careful
; division does not.  The fifth line is never normalized in cases when
; n2 is 0.  This tells us that if does not normalize all of its
; arguments as most functions do.  In particular, it normalizes only
; those arguments whose normalization will be needed.  For this reason,
; IF must be implemented in 3-LISP as a so-called special form.


;;; PROBLEM 1-c

;;; The standard method:

(define ABSOLUTE-VALUE
   (lambda [n]
      (if (< n 0)
          (- 0 n)
          n)))


;;; A more arcane definition, using higher-order functions:

(define ABSOLUTE-VALUE
   (lambda [n]
      ((if (< n 0) - +)
       0 n)))


;;; PROBLEM 1-d

;;; The standard recursive factorial:

(define FACTORIAL
   (lambda [n]
      (if (= n 0)
          1
          (* n (factorial (- n 1))))))


;;; PROBLEM 1-e

;;; The standard recursive fibonacci function:

(define FIBONACCI
   (lambda [n]
      (if (<= n 2)
          1
          (+ (fibonacci (- n 1))
             (fibonacci (- n 2))))))


;;; PROBLEM 1-f

; Most people find that FIBONACCI corresponds most closely to their
; intuitive idea of what the fibonacci function is.  However, the more
; efficient algorithm FIB-2 seems closer to how people actually compute
; fibonacci numbers, since it does not require recomputing prior
; results.  


;;; PROBLEM 1-g

; FIBONACCI is considerably less efficient than FIB-2 in computing
; fibonacci numbers.  FIB-2 computes all fibonacci numbers up to n
; exactly once in computing (FIB-2 n), whereas FIBONACCI computes some
; intermediate results many times.  In particular,
;
;   (FIBONACCI n-1) is computed 1 time
;              n-2              2 times
;              n-3              3
;              n-4              5
;              n-5              8
;       etc.
; 
; 
; You may recognize this sequence of numbers.  It is just the fibonacci
; sequence!  Thus FIB-2 takes time proportional to n but FIBONACCI takes
; time proportional to the nth fibonacci number.


;;; PROBLEM 1-h

; Though FIB-3 is possibly notationally and visually more complex, it is
; simpler in the sense that the helper function does not require n to be
; repeatedly passed, and because the only locally needed helping
; function is defined only locally, not globally, as in the case of
; FIB-2. 


;;; PROBLEM 1-i

; FIB-4 would not work because the use of n inside of helper is not
; within the scope of the binding of n.  (Recall that scope in 3-LISP is
; determined lexically.)


;;; PROBLEM 1-j

(define SQUARE
   (lambda [x] (* x x)))

(define COMPOSE
   (lambda [f g]
      (lambda [n]
         (f (g n)))))


(define DOUBLE
   (lambda [n]
      (* 2 n)))

;;; Testing these functions:

((compose double square) 5)         ; normalizes to 50
((compose square double) 5)         ; normalizes to 100
((compose square square) 5)         ; normalizes to 625


(define TWICE
   (lambda [f]
      (compose f f)))

;;; Now testing TWICE:

((twice factorial) 3)              ; normalizes to 720
((twice 1+) 10)                    ; normalizes to 12


;;; PROBLEM 1-k

(define THRICE
   (lambda [f]
      (compose (twice f) f)))

;;; Testing this function:

((thrice (thrice 1+)) 0)                 ; normalizes to 9
(((thrice thrice) 1+) 0)                 ; normalizes to 27

((thrice (thrice (thrice 1+))) 0)        ; normalizes to 27        
(((thrice thrice) (thrice 1+)) 0)        ; normalizes to 81

; ((((thrice thrice) thrice) 1+) 0)

; The last of these is 3 to the 27th


;;; PROBLEM 1-l

; IF* is completely extensional, that is, it normalizes all of its
; arguments.  But normalizing the atom 'then' causes an error because
; the atom is unbound.  Replacing the atom then with the stringer "then"
; nor the handle 'then would solve this problem (since they normalize to
; themselves).  However, note that both the then and the else
; expressions get normalized by IF* before returning.  Thus in the case
; of FACTORIAL, both the 0 and the recursive expression would be
; normalized, leading to an infinite regress. Unfortunately, this
; problem with IF* cannot be solved (with our present knowledge of
; 3-LISP) because we have no way of defining functions that do not
; normalize all of their arguments.