;; Sid Stamm
;; C211 lab number 6: Let
;; 10-9-2003

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Let
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; You've learned how to create complex procedures and how
;; to loop (recursively).  Now it's time to do a little
;; abstraction in a different way.

;; When you run a program that computes a value then uses
;; the result many times, you don't want to recompute the
;; result each time it is used.  Currently, that's all you
;; know how to do.  

;; This lab will show you how to bind local variables in
;; a somewhat intuitive manner.  First, I'll show you where
;; it came from.


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Internal Lambda's
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; recall the non tail-recursive definition of factorial:
(define !
  (lambda (n)
    (if (zero? n)
        1
        (* n (! (- n 1))))))

(define !
  (lambda (n)
    (if (zero? n)
	'()
	(cons n (! (sub1 n))))))

(define !
  (lambda (n)
    (fact n '())))

(define fact
  (lambda (n acc)
    (if (zero? n)
	acc
	(fact (sub1 n) (cons n acc)))))

;; Using this method, if we want 20000!, it's going to take
;; a very long time!  So the goal is to just compute it once.

;; Here's an analysis tool: time
;; You can time some procedure's execution by executing it
;; inside the time procedure:
(time (! 100))

;; Notice, you get the output as well as the time.

;; SO, let's define a method that uses the same computed
;; factorial value many times.

;; I've used an internal define to create a helper function
;; (the reason will be obvious later) and I've marked it off
;; with lines.

(define lots-o-fact
  (lambda (num-times fact-rand)
    ;----------------------------------------
    (define help (lambda (x)
                   (if (zero? x)
                       '()
                       (cons (! fact-rand) (help (- x 1))))))
    ;----------------------------------------
    (help num-times)
    (display "done"))) ;this supresses the output

(time (lots-o-fact 300 500)) ;see how long it takes?


;; Now, I can eliminate the recurrance of (! fact-rand) by
;; calculating it once, then passing it in.

(define lots-o-fact
  (lambda (num-times fact-rand fact-val)
    ;----------------------------------------
    (define help (lambda (x)
                   (if (zero? x)
                       '()
                       (cons fact-val (help (- x 1))))))
    ;----------------------------------------
    (help num-times)
    (display "done")))

(time (lots-o-fact 300 500 (! 500))) ;takes less time!


;; But this is terrible, since we don't want whoever calls
;; this procedure to need to compute factorial, that should
;; be part of our procedure.  So, let's try something new.

;; What is ((lambda (v) (+ x v)) 4)?
;; That's just the same as saying (+ x 4), right?  We build
;; an environment when we call the anonymous procedure.  It
;; puts v with value 4 into the environment, then (+ x v)
;; knows that v=4.  

;; So if we want to remember something, we can wrap a lambda
;; expression around where we need to have that memory!

;; For example, say we want to square a factorial value:

(* (! 4) (! 4))
;576

;; But, we're doing the same thing twice, let's make it less
;; redundant by *remembering* (! 4).

((lambda (four!) 
         (* four! four!)) 
 (! 4))
;576

;; Notice, we've only used the ! procedure ONCE.  This is a
;; better technique to use when writing code in scheme.

;; Now I can rewrite lots-o-fact so that it has a memory that
;; remembers (! v):

(define lots-o-fact
  (lambda (num-times fact-rand)
    (
     ;==================================================
     (lambda (fact-val)
       ;----------------------------------------
       (define help (lambda (x)
                      (if (zero? x)
                          '()
                          (cons fact-val (help (- x 1))))))
       ;----------------------------------------
       (help num-times)
       (display "done"))
     ;==================================================
     (! fact-rand))))

(time (lots-o-fact 300 500)) ;it still works!

;; I've sectioned off the helper definition once again with
;; single lines, and notice how both it and the call to help
;; are within our "memory" lambda's (anonymous procedure's) 
;; body.

;; I've further sectioned off the memory lambda so we can see
;; that it is defined, then immediately applied to (! fact-rand).
;; Think of the stuff between double-lines as a procedure like
;; add1.  When you call add1, you apply it to a number, so we
;; could call (add1 (! fact-rand)) to add 1 to our calculated
;; value.

;; So really all we're doing inside the lots-o-fact body is 
;; creating a procedure (that keeps a memory in it's formals)
;; then calling it.  That's it.

;; This is ugly though.  Terribly ugly.  We calculate (! fact-rand)
;; before we do the stuff with it, but it is at the bottom of
;; our expression!  HORRIBLE!  Think about how you would do
;; this on paper.  You'd probably write something like:

; let fact-val = (! fact-rand)
; do helper stuff with fact-val.

;; That's not the order it is in scheme, so what happens? We
;; have a new expression called a let-expression.  Here's what
;; a let expression looks like:

; (let ([a1 b1] [a2 b2] ...)
;      body1
;      body2
;      ...)

;; IS THE SAME AS:

; ((lambda (a1 a2 ...)
;    body1
;    body2
;    ...)
;  b1 b2 ...)

;; It contains a list that has variable (a's) and value (b's) 
;; pairs.  In this case, [] and () are the same thing.  The
;; [] are used to make it slightly more readable.
;; Following the list of pairs is a bunch of bodies.  Like in
;; a lambda or begin expression, they all get evaluated, but
;; the let expression always evaluates to the value returned
;; by the last body.

;; So, before I wrote (* (! 4) (! 4)) as:

((lambda (four!) 
         (* four! four!)) 
 (! 4))

;; With a let, you can write it as:
(let ([four! (! 4)])
  (* four! four!))

;; Yes, it's that simple.  It binds the value of (! 4) to
;; four!, then in the body it squares that value.  Now we can
;; declare our "memory" *before* we use it!  This is far more
;; intuitive, no?

;; So, let's convert our nasty lots-o-fact into something
;; that uses a let expression.

(define lots-o-fact
  (lambda (num-times fact-rand)
    ;==================================================
    (let ([fact-val (! fact-rand)])
      ;----------------------------------------
      (define help (lambda (x)
                     (if (zero? x)
                         '()
                         (cons fact-val (help (- x 1))))))
      ;----------------------------------------
      (help num-times)
      (display "done"))
    ;==================================================
    ))

(time (lots-o-fact 300 500)) ;it still works! Faster too!

;; OH!  That is MUCH easier to read.  So we let fact-val be
;; the value of (! fact-rand), then do some stuff. Once again,
;; I have the let expression surrounded by double-lines (like
;; the memory-lambda was) so you can see where the memory is.
;; Now, we have a decently easy-to-read procedure that makes
;; an environment for us to remember things without forcing
;; us to use lambda.

;; Things to remember with let:
;; You cannot write recursive procedures inside the list of
;; pairs, since the pairs are evaluated in a random order.
;; You can define other procedures though:

(define square
  (lambda (n)
    (let ([sq-help (lambda (x) (* x x))])
      (sq-help n))))

;; That works. I wrote excessive code here, but it gets the
;; job done.


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; EXERCISES!
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; It's time for your weekly chores!

;; EXERCISE 1
;;------------
;; Define the procedure three-random that generates three 
;; random numbers between 1 and 100, then returns a list that 
;; contains their sum, product, and maximum (use the max 
;; built-in procedure). It takes NO parameters!  Also, you 
;; have to use let because once they're generated, you cannot
;; assume (random) will give back the same number again!

;; Ex: the numbers generated are 2 1 3
; > (three-random)
; (6 6 3)

;; Solution:
(define three-random
  (lambda ()
    (let ([x (random 100)]
          [y (random 100)]
          [z (random 100)])
      (cons (+ x y z)
            (cons (* x y z)
                  (cons (max x y z) '()))))))

;; EXERCISE 2
;; ------------
;; Extend three-random such that it returns a list with
;; four elements:
;; - a list containing the random numbers
;; - their sum 
;; - their product
;; - their maximum
;; Also, give three-random one parameter that is the maximum
;; size for the random numbers.  (Use this when generating
;; the numbers).

;; Ex:
; > (three-random 20)
; ((17 16 10) 43 2720 17)

;; Solution
(define three-random
  (lambda (max-num)
    (let ([x (random max-num)]
          [y (random max-num)]
          [z (random max-num)])
      (cons (list x y z)
            (cons (+ x y z)
                  (cons (* x y z)
                        (cons (max x y z) '())))))))

;; EXERCISE 3
;;------------
;; This one is much harder.  Make a new procedure called
;; n-random that takes one parameter: num-vars.  It should
;; generate num-vars random numbers less than 100 and then 
;; return a list with the same structure as the last 
;; three-random:
;; ((var1 var2 ... varN) <sum> <product> <max>)

;; Like I said, this is much harder, here are some hints:
;; - Use let, but you will probably only bind one "memory" 
;;    variable.
;; - You will probably want to remember a list.
;; - You may want one or more helpers.
;; - You will have to use 2 memories (let expressions) because
;;   the order of binding for the pairs in a let expression
;;   is random!  So if I do (let ([a 1] [b a]) b) I may get
;;   an error!  I have to do (let ([a 1]) (let ([b a]) b))
;;   instead.

;; Example test cases:
; > (n-random 4)
; ((37 89 44 7) 177 1014244 89)
; > (n-random 10)
; ((82 94 45 41 3 76 56 98 24 90) 609 38436229452902400 98)
; > (n-random 0)
; (() 0 1 0)

 
;; Solution:
(define n-random
  (lambda (num-vars)

    (define make-vars
      (lambda (n acc)   ;start this accumulator as '()
        (if (zero? n)
            acc
            (make-vars (sub1 n) (cons (random 100) acc)))))
    (define max-list
      (lambda (ls acc)  ;start this accumulator as 0
        (if (null? ls)
            acc
            (max-list (cdr ls) (max (car ls) acc)))))
    (define sum-list
      (lambda (ls acc)  ;start this accumulator as 0
        (if (null? ls)
            acc
            (sum-list (cdr ls) (+ (car ls) acc)))))
    (define prod-list
      (lambda (ls acc)  ;start this accumulator as 1
        (if (null? ls)
            acc
            (prod-list (cdr ls) (* (car ls) acc)))))

    ;; now onto the real program! (ENOUGH HELPERS!)
    (let ([vars (make-vars num-vars '())])
      ;; have to nest lets, because I don't know what order the
      ;; vars are evaluated in!
      (let ([v-sum (sum-list vars 0)]
            [v-prod (prod-list vars 1)]
            [v-max (max-list vars 0)])
        ;; make the returned list.
        (cons vars
              (cons v-sum
                    (cons v-prod
                          (cons v-max '()))))))))