;  David Golombek
;  Problem Set #4
===============================================================================
;  Lab Exercise 1

(define (save-this-step? n body) #t)

(smeval
 '((define (rec-fact n)
    (if (<= n 0)
	1
	(* n (rec-fact (dec n)))))
 (rec-fact 4)))

;==(0)==>
((define rec-fact (lambda (n) (if (<= n 0) 1 (* n (rec-fact (dec n))))))
 (rec-fact 4))

;==(1)==>
((define rec-fact (lambda (n) (if (<= n 0) 1 (* n (rec-fact (dec n))))))
 ((lambda (n) (if (<= n 0) 1 (* n (rec-fact (dec n))))) 4))
...
;==(39)==>
((define rec-fact (lambda (n) (if (<= n 0) 1 (* n (rec-fact (dec n))))))
 (define n#0 4)
 (define n#1 3)
 (define n#2 2)
 (define n#3 1)
 (define n#4 0)
 (* 4 (* 3 2)))

;==(40)==>
(* 4 6)

;==(41)==>
24
---------------------------------
(smeval
 '((define (iter-fact n)
     (define (iter n result)
       (if (<= n 0)
	   result
	   (iter (- n 1) (* n result))))
     (iter n 1))
   (iter-fact 4)))

;==(0)==>
((define
  iter-fact
  (lambda
   (n)
   (define
    iter
    (lambda (n result) (if (<= n 0) result (iter (- n 1) (* n result)))))
   (iter n 1)))
 (iter-fact 4))
...
;==(49)==>
((define
  iter#1
  (lambda (n result) (if (<= n 0) result (iter#1 (- n 1) (* n result)))))
 (define n#9 1)
 (define result#3 24)
 (define n#10 0)
 (define result#4 24)
 24)

;==(50)==>
24

===============================================================================
; Lab Exercise 2A:

(define (save-this-step? step-number body)
  (simple? (expression-of-body body)))

(define (simple? body)
  (define (check-all-operands operand-list)
    (if (null? operand-list)
	#t
	(and (simple? (car operand-list))
	     (check-all-operands (cdr operand-list)))))
  (or (variable? body)
      (self-evaluating? body)
      (and (combination? body)
	   (simple? (operator-of body))
	   (check-all-operands (operands-of body)))))

----------------
(smeval 
  '((define fact 
      (lambda (n) 
        (if (= n 0)
            1
            (* n (fact (- n 1))))))
    (fact 4)))


;==(0)==>
((define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1)))))) (fact 4))

;==(5)==>
((define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1)))))) (define n#120 4)
                                                                (* n#120 (fact (- n#120 1))))
...
;==(39)==>
((define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1)))))) (define n#120 4)
                                                                (define n#121 3)
                                                                (define n#122 2)
                                                                (define n#123 1)
                                                                (define n#124 0)
                                                                (* 4 (* 3 2)))

;==(40)==>
(* 4 6)

;==(41)==>
24

===============================================================================
Lab Exercise 2B:
(define (print-stepped-message step-number body)
  (begin (newline)
         (newline)
         (display ";==(")
         (display step-number)
         (display ")==>")
	 (pp (expression-of-body body))))

---------
(smeval 
  '((define fact 
      (lambda (n) 
        (if (= n 0)
            1
            (* n (fact (- n 1))))))
    (fact 4)))

;==(0)==>
(fact 4)

;==(5)==>
(* n#78 (fact (- n#78 1)))
...
;==(41)==>
24

;==(42)==>
24
Syntactic Value was returned
;Value: 24

=================================
(smeval 
 '((define (iter-fact n)
   (define (iter n result)
     (if (<= n 0)
	 result
	 (iter (- n 1) (* n result))))
   (iter n 1))
 (iter-fact 4)))

;==(0)==>
(iter-fact 4)

;==(2)==>
(iter#11 n#83 1)

;==(3)==>
(iter#11 4 1)
...
;==(48)==>
result#14

;==(49)==>
24

=====================================
(smeval
 '((define (rec-fib n)
     (if (< n 2)
	 n
	 (+ (rec-fib (- n 1))
	    (rec-fib (- n 2)))))
   (rec-fib 4)))

;==(0)==>
(rec-fib 4)

;==(5)==>
(+ (rec-fib (- n#89 1)) (rec-fib (- n#89 2)))

;==(6)==>
(+ (rec-fib (- 4 1)) (rec-fib (- n#89 2)))
...
;==(69)==>
(+ 2 1)

;==(70)==>
3

=========================================
(smeval
 '((define (iter-fib n)
     (define (iter count a b)
       (if (= count 0)
	   b
	   (iter (- count 1) (+ a b) a)))
     (iter n 1 0))
   (iter-fib 4)))

;==(0)==>
(iter-fib 4)

;==(2)==>
(iter#9 n#77 1 0)
...
;==(53)==>
3

===============================================================================
Lab Exercise 2C:

(define (simple? body)
  (define (check-all-operands operand-list)
    (if (null? operand-list)
	#t
	(and (simple? (car operand-list))
	     (not (variable? (car operand-list)))
	     (check-all-operands (cdr operand-list)))))
  (or (variable? body)
      (self-evaluating? body)
      (and (combination? body)
	   (simple? (operator-of body))
	   (check-all-operands (operands-of body)))))

==========================
(smeval 
  '((define fact 
      (lambda (n) 
        (if (= n 0)
            1
            (* n (fact (- n 1))))))
    (fact 4)))

;==(0)==>
(fact 4)

;==(7)==>
(* 4 (fact (- 4 1)))
...
;==(40)==>
(* 4 6)

;==(41)==>
24

==============================
(smeval
 '((define (rec-fact n)
    (if (<= n 0)
	1
	(* n (rec-fact (dec n)))))
 (rec-fact 4)))

;==(0)==>
(rec-fact 4)

;==(7)==>
(* 4 (rec-fact (dec 4)))
...
;==(40)==>
(* 4 6)

;==(41)==>
24

==============================
(smeval 
 '((define (iter-fact n)
   (define (iter n result)
     (if (<= n 0)
	 result
	 (iter (- n 1) (* n result))))
   (iter n 1))
 (iter-fact 4)))

;==(0)==>
(iter-fact 4)

;==(3)==>
(iter#7 4 1)

;==(12)==>
(iter#7 3 (* 4 1))
...
;==(49)==>
24

==============================
(smeval
 '((define (iter-fib n)
     (define (iter count a b)
       (if (= count 0)
	   b
	   (iter (- count 1) (+ a b) a)))
     (iter n 1 0))
   (iter-fib 4)))

;==(0)==>
(iter-fib 4)

;==(3)==>
(iter#5 4 1 0)
...
;==(53)==>
3

============================
(smeval
 '((define (rec-fib n)
     (if (< n 2)
	 n
	 (+ (rec-fib (- n 1))
	    (rec-fib (- n 2)))))
   (rec-fib 4)))

;==(0)==>
(rec-fib 4)
....
;==(68)==>
(+ 2 (+ 1 0))

;==(69)==>
(+ 2 1)

;==(70)==>
3

===============================================================================
;Exercise 3A:

(define let*? (tagged-pair? 'let*))
(define bindings-of-let* cadr)
(define first-binding car)
(define remainding-bindings cdr)
(define body-of-let* caddr)
(define (make-let binding body)
  (list 'let binding body))

(define (turn-into-lets bindings inner-body)
  (if (null? bindings)
      inner-body
      (make-let (list (first-binding bindings))
		(turn-into-lets (remainding-bindings bindings) inner-body))))

(define (desugar body)
  (cond ((cond? body)
         (let ((clauses (clauses-of-cond body)))
           (if (null? clauses)
               submodel-useless-value
               (let ((first-clause (car clauses)))
                 (desugar
                  (if (else-clause? first-clause)
                      (expression-of-clause first-clause)
                      (make-if
                       (test-of-clause first-clause)
                       (expression-of-clause first-clause)
                       (make-cond (cdr clauses)))))))))
        ((let? body)
         (desugar
          (let ((bindings (bindings-of-let body)))
            (make-combination
             (make-lambda
              (map variable-of-binding bindings)
              (body-of-let body))
             (map init-of-binding bindings)))))
	((let*? body)
	  (let ((inner-body (body-of-let* body))
		(bindings (bindings-of-let* body)))
	    (desugar
	     (turn-into-lets bindings inner-body))))
	((or (self-evaluating? body)
             (symbol-expression? body)
             (variable? body)
             (submodel-null? body))
         body)
        ((lambda-expression? body)
         (make-lambda
          (formals-of-lambda body)
          (desugar (body-of-lambda body))))
        ((combination? body)
         (make-combination
          (desugar (operator-of body))
          (map desugar (operands-of body))))
        ((if? body)
         (make-if
          (desugar (test-of-if body))
          (desugar (consequent-of body))
          (desugar (alternative-of body))))
        (else
         (let ((defs (defines-of-body body)))
           (make-body
            (map make-define
                 (map variable-of-define defs)
                 (map desugar (map expression-of-define defs)))
            (desugar (expression-of-body body)))))))

===============================================================================
Lab Exercise 3B:

(pp (desugar '(let* ((x 1) (y x)) y)))

((lambda (x) ((lambda (y) y) x)) 1)
...

(pp (desugar let*-test1))

((define
  put-in-standard-position
  (lambda
   (curve)
   ((lambda
     (start-point)
     ((lambda
       (curve-started-at-origin)
       ((lambda
         (new-end-point)
         ((lambda
           (theta)
           ((lambda
             (curve-ended-at-x-axis)
             ((lambda
               (end-point-on-x-axis)
               ((scale (/ 1 end-point-on-x-axis)) curve-ended-at-x-axis))
              (x-of (curve-ended-at-x-axis 1))))
            ((rotate-around-origin (- theta)) curve-started-at-origin)))
          (atan (y-of new-end-point) (x-of new-end-point))))
        (curve-started-at-origin 1)))
      ((translate (- (x-of start-point)) (- (y-of start-point))) curve)))
    (curve 0))))
 (put-in-standard-position (compose unit-circle double)))
;No value

...
	
(pp (desugar let*-test2))

((lambda
  (a)
  ((lambda
    (b)
    ((lambda (b) (not ((lambda (c) (equal? c b)) (cdr (b)))))
     ((lambda
       ()
       (define
        y
        (lambda () ((lambda (a) ((lambda (b) (cons b y)) (inc a))) (inc a))))
       y))))
   (inc a)))
 (+ 2 3))
;No value





