ps1-1.3-lisp!1 (original) (raw)

;;;================================================================= ;;; 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.