;;;;;;;;;;;;;;;;;;;;;;;PROBLEM 1;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; SICP 3.3

(define (make-account balance password)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (define (dispatch pwd request)
    (if (eq? pwd password)
	(cond ((eq? request 'withdraw) withdraw)
	      ((eq? request 'deposit) deposit)
	      ((eq? request 'balance) balance)
	      (else (error "Unknown request -- MAKE-ACCOUNT"
			   m)))
	(error "Incorrect password")))
  dispatch)

;; SICP 3.4

(define (make-account balance password)
  (let ((guesses 0))
    (define (withdraw amount)
      (if (>= balance amount)
	  (begin (set! balance (- balance amount))
		 balance)
	  "Insufficient funds"))
    (define (deposit amount)
      (set! balance (+ balance amount))
      balance)
    (define (dispatch pwd request)
      (if (eq? pwd password)
	  (cond ((eq? request 'withdraw) withdraw)
		((eq? request 'deposit) deposit)
		((eq? request 'balance) balance)
		(else (error "Unknown request -- MAKE-ACCOUNT"
			     m)))
	  (if (< guesses 7)
	      (begin (set! guesses (+ guesses 1))
		     (error "Incorrect password"))
	      (begin (call-the-cops)
		     (error "You're in big trouble, man.")))))
    dispatch))

;; When we do something like (define acc (make-account 100 'secret)),
;; we create E1, a frame that binds the variables "balance" and
;; "password" to 100 and 'secret.  Then we create E2 inside E1,
;; bind the variable "guesses" to 0, and we RETURN dispatch inside
;; E2.  Then we bind "acc" to dispatch.
;;
;; Now "acc" (and no other object!) will have access to guesses.
;; This is how local variables are implemented in Scheme.  Pretty cool
;; stuff.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;PROBLEM 2;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; First, in G, we bind "num" to 1.  Next, we want to bind "foo" to something,
;; but we have to evaluate whatever that is first.
;;
;; Remember the rules for evaulation:
;;    a) Evaluate the procedure, evaluate the arguments.
;;    b) Make a new frame wherever the procedure lives, and bind variables to arguments.
;;    c) Run body, and return anything in the new frame.
;;    d) Jump back out to the frame that called the procedure.
;;
;; By the way, none of this will make sense if you're just reading it.  Get out
;; a piece of paper and do it with me!
;;
;; We're trying to evaluate the procedure call:

(let ((fn (lambda (x) (set! num x))))
   (lambda (num)
       (fn num)
        num))

;; Which, when desugared, turns into:

((lambda (fn) (lambda (num) (fn num) num)) (lambda (x) (set! num x)))

;; For our sanity, lets refer to the first lambda (with parameter fn) as L1,
;; the second lambda (with param num) as L2, and the third lambda (with
;; param x) as L3.

;; So we do step a) first:
;;    --Evaluate the procedure, so it creates L1, a lambda
;;      bubble in G with P: fn and B: (lambda (num) (fn num) num).
;;
;;    --Evaluate the arguments, so it creates L3, a lambda bubble in G
;;      with P: x and B: (set! num x).

;; Then we do step b), so we create a new frame E1 where L1 lives (which is in G.)
;; and we set fn to the lambda bubble for L2.

;; Now we do step c), and run the body of L1.  We create L2, a lambda bubble in E1
;; with P: num and B: (fn num) num.

;; Phew! We just finished evaluating that giant expression, and now we can set "foo"
;; to the lambda bubble in E1.

;; Now we call (foo 50), so we have to follow our steps again:

;; Step a), we evaluate foo, it's a lambda bubble in E1.  We evaluate 50, and it's
;; self evaluating.

;; Step b), we call foo, so we create a new frame wherever foo lives.  It lives in E1,
;; so we create a new frame E2 inside of E1.  In there, we bind the variable "num" to
;; 50.

;; Step c), we run the body of foo.  It tells us to first do (fn num).  To do that,
;; we have to follow our steps again:

;;         Step a), we evaluate fn, it's a lambda bubble in G.  We evaluate num, and it's 50.
;;         Step b), we create a new frame E3 wherever fn lives (it lives in G), and we bind the
;;                  variable "x" to 50.
;;         Step c), we run the body of fn.  It tells us to do (set! num x).  Remember set! is
;;                  a special form, so we first evaluate x (it's 50), and we go hunting for
;;                  the variable "num".  It's not in our current frame, so we look out.  We
;;                  find it in the global frame, so we change that "num" to 50.
;;
;;                  Note that we don't change the num inside E2!!!  When we're in E3, we can't
;;                  "see" anything in E2!  We have to be E2 or contained in E2 if we want to access
;;                  the variables in E2.
;;
;;         Step d), Anyway, we're done with this step c, so we can jump back to the frame
;;                  that called this procedure...
;;
;; We're not done yet!  We still need to return num.  We return 50.  Now we're done.

;; So after the mess you created on your paper, you should have something like this:

;; GLOBAL ENV contains:
;;    -- num set to 50.
;;    -- foo pointing to L2.
;;    -- L1, which has params: fn and body: L2.
;;    -- L3, which has params: x and body: (set! num x).
;;    -- E1.
;;    -- E3.
;;
;; E1 contains:
;;    -- fn pointing to L3.
;;    -- L2, which has params: num and body: (fn num) num.
;;    -- E2.
;;
;; E2 contains:
;;    -- num pointing to 50.
;;
;; E3 contains:
;;    -- x pointing to 50.
;;
;; Okay, now we're done.  Doing environmental diagrams really just is bookkeeping.  Remember the
;; rules, and remember your current frame.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;PROBLEM 3;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; Okay, you're going to need all 8.5x11 square inches for this guy.  I got a headache trying
;; to write it out step by step, so come to my office hours if you want to see this done in action.
;; (if you couldn't tell, I'm Charles.)

;; PART A:

;; GLOBAL contains:
;;    -- L1, with parameter: total-student and body: L2.
;;    -- make-student, which points to L2.
;;    -- jo, which points to L4 in E3.
;;    -- mi, which points to L4 in E6.
;;    -- E1.
;;
;; E1 contains:
;;    -- total-sudents, which points to 0.
;;    -- L2, with parameter: name and body: let ((age 12)) blah blah.
;;    -- E2.
;;    -- E5.
;;
;; By the way, containment is transitive.  So when I say E1 contains E2, I also mean E1 contains
;; everything that E2 contains.
;;
;; E2 contains:
;;    -- name, which points to 'john-fitzgerald.
;;    -- L3, which has parameter: age and body: ((define .........) .... dispatch).
;;    -- E3.
;;
;; E3 contains:
;;    -- age, which points to 12.
;;    -- L4 (this is JO's dispatch!), which has parameter: m and body: (cond .......).
;;    -- L5, which has parameter: new-name, and body: (set! name new-name).
;;    -- E4.
;;
;; E4 contains:
;;    -- new-name, which is bound to 'john-fitzgerald.
;;
;; E5 contains:
;;    -- name, which points to 'michaelangelo.
;;    -- L3, which has parameter: age and body: ((define ....) ... dispatch).
;;    -- E6.
;;
;; E6 contains:
;;    -- age, which points to 12.
;;    -- L4 (this is MIKE's dispatch), which has parameter: m and body: (cond ...).

;; PART B:
;; a) make-student is bound to L2, which takes in a name as an argument.
;; b) Calling make-student returns a dispatch.
;; c) The object is the dispatch, since it has access to class variables (total-nums),
;;    instance variables (name and age), and has methods (change-name, etc.)
;; d) Total-students is a class variable, since every instance has access to it.
;; e) Name is an instatiation variable, because it's given as an argument to the instantiation.
;; f) Age is a instance variable, because the initial value is the same for every object
;;    in the class.

;; PART C:
(define-class (make-student name)
  (class-vars (total-students 0))
  (instance-vars (age 12))
  (method (change-name new-name) (set! name new-name))
  (method (greet) 'hello!))

;; PART D:

(define make-student
  (let ((total-students 0))
  
    (lambda (name)
      (let ((age 12))
        
        (define (change-name new-name)
           (set! name new-name))
  		
        (define (dispatch m)
           (cond ((eq? m 'name) name)
                ((eq? m 'change-name) change-name)  
                ((eq? m 'age) age)
                ((eq? m 'total-students) total-students)
                ((eq? m 'greet) 'hello)
                (else ``UNKNOW MESSAGE'')))
        (set! total-student (+ total-student 1))
        dispatch))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;PROBLEM 4;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; SICP 3.13

;; z should look like a circular list with three cons cells.  The first cons cell has car
;; 'a and cdr pointing to the second cons cell.  The second cons cell has car 'b and cdr
;; pointing to the third cons cell.  The third cons cell has car 'c and cdr pointing to the
;; first cons cell.

;; Computing (last-pair z) will result in an infinite loop, because last-pair chases down cdrs.

;; SICP 3.14

;; mystery returns the reverse of the list.  The important part is the (loop x y) procedure.
;; y stores the progress of the reversal.  Basically, loop moves the first cons cell of x to
;; y at every iteration.  Here's a sample trace, with (define x '(1 2 3 4)):
;;
;; 1st iteration: (loop x '()), which is really (loop '(1 2 3 4) '())
;;
;;                We set temp1 = '(2 3 4) and set-cdr! x to '().
;;
;; 2nd iteration: (loop temp1 x), which is really (loop '(2 3 4) '(1))
;;
;;                We set temp2 = '(3 4) and set-cdr! temp1 to '(1).
;;
;; 3rd iteration: (loop temp2 temp1), which is really (loop '(3 4) '(2 1))
;;
;;                We set temp3 = '(4) and set-cdr! temp2 to '(2 1).
;;
;; 4th iteration: (loop temp3 temp2), which is really (loop '(4) '(3 2 1))
;;
;;                We set temp4 = '() and set-cdr! temp3 to '(3 2 1).
;;
;; And finally, we return temp3, which is '(4 3 2 1).  Phew!

;; SICP 3.16

;; Returning 3: (define x (list 1 2 3)),
;;              (count-pairs x).
;;
;; Returning 4: (define x (list 1 2 3)),
;;              (set-car! x (cdr (cdr x))),
;;              (count-pairs x).
;;
;; Returning 7: (define x (list 1 2 3))
;;              (set-car! x (cdr x))
;;              (set-car! (cdr x) (cdr (cdr x)))
;;              (count-pairs x)
;;
;; Returning nothing: (define x (list 1 2 3)),
;;                    (set-car! x x)
;;                    (count-pairs x)

;; SICP 3.17

;; We keep a list of pairs we have seen before.  Note we can't use equal?
;; to help us, because it check equality of content, not equality of pointers.
;; We use memq.

(define (count-pairs x seenbefore)
  (cond ((not (pair? x)) 0)
	((memq? x seenbefore) (+ (count-pairs (car x) seenbefore)
				 (count-pairs (cdr x) seenbefore)))
	(else (+ (count-pairs (car x) (cons x seenbefore))
		 (count-pairs (cdr x) (cons x seenbefore))
		 1))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;PROBLEM 6;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; SICP 3.21

;; Queue is an abstract data type.  We don't know how it is actually implemented,
;; but the thing is, we don't really care.  Stk sees just a pair created with cons,
;; so it prints its car and cdr.  How can we make Ben satisfied?  Let's follow some
;; rules, and only use queue specific procedures:

(define (print-queue Q)
  (if (empty-queue? Q)
      '()
      (let ((temp (front-queue Q)))
	(delete-queue! Q)
	(cons temp (print-queue Q)))))

;; But this comes at the price of destroying Q!  Let's try again...

(define (print-queue Q)
  (car Q))

;; But this is implementation specific, and violates data abstraction!
;; If we didn't know anything about how queues were implemented, we couldn't
;; do car on Q because we can't assume Q is a cons pair.

;;;;;;;;;;;;;;;;;;;;;;;;;;;PROBLEM 7;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; We're given a list of FLAT lists.  Recursively speaking, (easy-flatten! (cdr ls))
;; RETURNS a flat list containing the atoms in (cdr ls).
;;
;; Hence, we append! (car ls) to (easy-flatten! (cdr ls)) to get our flattened list.
;; We use begin to notify Scheme that there is more than one line in our else clause.
;;
;; Also, the way begin works is it does each statement one by one, and returns the
;; value of the final statement.

(define (easy-flatten! ls)
  (if (null? ls)
      '()
      (append! (car ls) (easy-flatten! (cdr ls)))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;PROBLEM 8;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; If (car ls) is a list, we append it to the flattened cdr.
;; Otherwise, we just flatten the cdr and return the list.

  
(define (flatten! ls)
  (cond ((atom? ls) ls)
	((list? (car ls)) (append! (flatten! (car ls))
				   (flatten! (cdr ls))))
	(else (set-cdr! ls (flatten! (cdr ls)))
	      ls)))