;;;;;; #1
;a
;STk> (if 'false 'true 'false)
;true

;b
;STk> (- '1 '2 '3)
;-4

;c
;STk> (- '(1 2 3))
;error, because - cannot take a sentence as an argument

;d
;STk> (first (bf (first (bf '(living la vida loca)))))
;a

;e
;STk> +
;#[closure arglist=args 13c738]
;procedure

;f
;STk> (define rocks 'rocks)
;rocks
;STk> rocks
;rocks

;g
;STk> (rocks)
;error, because rocks is a varible, not a procedure, not valid in () by itself

;h
;STk> (define (papers) 'papers)
;papers
;STk> papers
;procedure

;i
;STk> (papers)
;papers

;j
;STk> (define (scissors) (scissors))
;scissors
;STk> scissors
;procedure

;k
;STk> (scissors)
;runs forver, infinite loop

;l
;STk> (lambda (x y) (+ 5 (x y y))) + 5)
;error, (lambda (x y) (+ 5 (x y y))) defines a perfect procedure, but + 5) causes problem

;m
;STk> (let ((a 1)
;	   (b a)
;	   (c b))
;       (+ a b c))
;error, unbound variale a when declare b and c, cannot use a new local variable to declare another on in the same let

;n
;STk> (define x (random 2))
;x
;STk> (define (y) (random 2))
;y
;STk> x
;0
;may return 1, but once x defind, only one value(0 or 1) can be obtained, no matter how many times we exam x
;because after we defind x, x holds the value forever unless we redefind it

;o
;STk> (x)
;error, x is not a procedure, cannot be in a () by itself

;p
;STk> y
;procedure

;q
;STk> (y)
;0
;may return 1 as well


;;;;;; #2
(define (sort arg)
       (if (empty? arg) '()
	   (insert (first arg) (sort (bf arg)))))

(define (insert a arg)
       (cond ((empty? arg) (se a arg))
	     ((> a (first arg)) (se (first arg) (insert a (bf arg))))
	     (else (se a arg))))

;STk> (sort '())
;()
;STk> (sort '(1 2 3))
;(1 2 3)
;STk> (sort '(4 5 6 7 1 3 3 2 0 0))
;(0 0 1 2 3 3 4 5 6 7)
;STk> (sort '(3 3 3 2 1))
;(1 2 3 3 3)
;STk> (sort '(0 0 -1 -3 8 2))
;(-3 -1 0 0 2 8)


;;;;;; #3
(define (mystery) 1)
(define (double1 a) (+ a a))
(define (double2 a) (+ (a) (a)))
(define (bar y z)
  (define (bar-helper1 x) 
    (if (= x 0)
	0
	(+ (bar-helper1 (- x 1))
	   (y))))
  (define (bar-helper2)
    (bar-helper1 z))
  bar-helper2)

;STk> (trace mystery)
;STk> (double1 (double2 (bar mystery 4)))
;.. -> mystery .. <- mystery returns 1
;.. -> mystery .. <- mystery returns 1
;.. -> mystery .. <- mystery returns 1
;.. -> mystery .. <- mystery returns 1
;.. -> mystery .. <- mystery returns 1
;.. -> mystery .. <- mystery returns 1
;.. -> mystery .. <- mystery returns 1
;.. -> mystery .. <- mystery returns 1
;16

;Applicative order: 8 times
;Normal order: 16 times


;;;;;; #4
;b, c and e can be done in linear time
;a can't becuase sorting can be done in log(n) growth, such as quick sort
;d can't because it can be done in constant time.
;such as (if (> (nth 2 arg) (first arg)))


;;;;;; #5
;;;;;; recursive version
(define (foooo arg)
  
(define (process wd)
  (if (or (empty? wd) (empty? (bf wd))) wd
      (let ((a (first wd)) (b (first (bf wd))))
	 (if (equal? a b) (word a a a a (process (bf (bf wd))))
	     (word a (process (bf wd)))))))

  (if (empty? arg) '()
      (se (process (first arg)) (foooo (bf arg)))))

;;;;;; iterative version
(define (foooo2 arg)

(define (iter arg result)
  (if (empty? arg) result
      (iter (bf arg) (se result (process (first arg))))))
(define (process wd)
  (p_iter (bf wd) (first wd)))
(define (p_iter arg res)
  (cond ((empty? arg) res)
	(else (let ((a (last res)) (b (first arg)))
		(cond ((and (equal? a b) (empty? (bf arg))) (p_iter (bf arg) (word res b b b)))
		      ((equal? a b) (p_iter (bf (bf arg)) (word res b b b (first (bf arg)))))
		      (else (p_iter (bf arg) (word res b))))))))

  (if (empty? arg) '()
      (iter (bf arg) (se (process (first arg))))))
;STk> (foooo '())
;()
;STk> (foooo '(abb))
;(abbbb)
;STk> (foooo2 '())
;()
;STk> (foooo2 '(abbc))
;(abbbbc)
;
;STk> (foooo '(i saw the mondey eat a bannana at the zoo))
;(i saw the mondey eat a bannnnana at the zoooo)
;STk> (foooo (foooo '(i saw the mondey eat a bannana at the zoo)))
;(i saw the mondey eat a bannnnnnnnana at the zoooooooo)
;STk> (foooo2 '(i saw the mondey eat a bannana at the zoo))
;(i saw the mondey eat a bannnnana at the zoooo)
;STk> (foooo2 (foooo2 '(i saw the mondey eat a bannana at the zoo)))
;(i saw the mondey eat a bannnnnnnnana at the zoooooooo)


;;;;;; #6
(define (dist arg1 arg2)
  (let ((a (square (- (first arg1) (first arg2))))
	(b (square (- (first (bf arg1)) (first (bf arg2)))))
	(c (square (- (last arg1) (last arg2)))))
    (sqrt (+ a b c))))

(define (square x) (* x x))
(define (fixed-point f guess)
  (if (good? f guess) guess
      (fixed-point f (improve f guess))))
(define (good? f guess)
  (< (abs (- (f guess) guess)) 0.00001))
(define (improve f guess)
  (/ (+ guess (f guess)) 2))
(define (sqrt x)
  (fixed-point (lambda (y) (/ x y)) 1.0))

;STk> (dist '(1 2 3) '(1 2 3))
;7.62939453125e-06
;STk> (dist '(1 2 3) '(0 0 0))
;3.74165756905871
;STk> (dist '(0 10 5) '(4 10 2))
;5.00000000005372