C211 Lab 6: Using Let!9 October 2003 |
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.
Recall the non tail-recursive definition of factorial:
(define !
(lambda (n)
(if (zero? n)
1
(* n (! (- n 1))))))
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:
Notice, you get the output as well as the time.(time (! 100))
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
You can use (time (lots-o-fact 300 500)) to 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")))
This time, use (time (lots-o-fact 300 500 (! 500)))
to see that it 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:
But, we're doing the same thing twice, let's make it less redundant by remembering (! 4).> (* (! 4) (! 4)) 576
>((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 (! fact-rand):
(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))))
If you use (time (lots-o-fact 300 500)) you can see
that 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 factorial value.
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)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:
do helper stuff with fact-val.
let 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.(let ([a1 b1] [a2 b2] ...) body1 body2 ...)And it is the same as:((lambda (a1 a2 ...) body1 body2 ...) b1 b2 ...)
So, before I wrote (* (! 4) (! 4)) as:
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?((lambda (four!) (* four! four!)) (! 4))With a let, you can write it as:(let ([four! (! 4)]) (* four! four!))
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"))))
You can test this one just like the previous one.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.
It's time for your weekly chores!
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 that random will give back the same number again!
> (three-random) (6 6 3)
(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) '()))))))
Extend three-random such that it returns a list with four elements:
> (three-random 20) ((17 16 10) 43 2720 17)
(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) '())))))))
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
version of three-random:
((var1 var2 ... varN) <sum> <product> <max>)
Like I said, this is much harder, here are some hints:
Example test cases:
4 random numbers:> (n-random 4) ((37 89 44 7) 177 1014244 89)10 random numbers:> (n-random 10) ((82 94 45 41 3 76 56 98 24 90) 609 38436229452902400 98)zero random numbers:> (n-random 0) (() 0 1 0)
(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 '()))))))))