CS 37
Clab 15: State and assignment
We have built abstractions with procedures that led to both
recursive and iterative processes. We have worked
with flat lists and deep lists. We have treated procedures
as first-class objects. We know primitive expressions, means
of combination, and means of abstraction. We also have a
model (applicative-order-evaluation with the substitution model)
for understanding procedure application.
We also have built abstractions with data. We have used dotted
pairs, lists, trees, deep-lists. We learned how to create
compound data objects that were quite complex but manageable
with appropriate abstraction barriers. We learned how to use
enumerate, filter, map, and accumulate to treat data as
signals flowing through stages of a process. We learned how
to build generic procedures both through data-directed programming
(using tags and dispatching on type) and message passing.
This weekend would be a good time to start reviewing chapters
1 and 2 to make sure you agree with the above paragraphs.
We are now going to leave the nice world of the substitution model.
I'll say a word or two about state and then we'll look at some of the
section 3.1.1 code together.
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-20.html#%_sec_3.1
Except for the table handling functions get and put that we
used in our number package, everything we did up until now
was done in "pure" lisp or "pure" scheme. This is the land
where once you create something, it does not change. You may
create a new thing with the same name as an old thing. But
that does not change the old thing.
Put the following in a drscheme definitions window and press run.
<![CDATA[
(define animals '(cat dog pig))
(define some (cdr animals))
(define copanim animals)
]]>
Then in the interactions window, do
<![CDATA[
> animals
> some
> copanim
> (define animals '(1 2 3))
> animals
> some
> copanim
]]>
You should see clear evidence that although, you changed what
the variable animals references, you did NOT violate the
structure of the what animals originally referenced. This means
that the substition model is valid and that two evaluations of
the same procedure on the same arguments will always give the
same result. This is the world of ordinary mathematics and
ordinary techniques of mathematical proof apply. That is
nice, but not always adequate to allow us to do all that
we want to do in computing.
Suppose we want a procedure to set up a simple bank account with
an initial balance and a withdrawal function.
<![CDATA[
(define (make-withdraw balance)
(lambda (amount)
(if (>= balance amount)
(- balance amount)
"Insufficient funds")))
]]>
This may apppear to do what we want. Try:
<![CDATA[
> (define angela (make-withdraw 100))
> (define pierre (make-withdraw 50))
> (angela 60)
40
> (pierre 60)
"Insufficient funds"
> (pierre 50)
0
>
]]>
But now try
<![CDATA[
> (pierre 40)
10
> (pierre 40)
10
]]>
This is not what we want for a bank account. If Pierre's
account was down to zero and we try to withdraw 40, we
want the insufficient funds message. We must give up
unchanging structures and introduce mutation. We do
this first using set! pronounced set-bang.
<![CDATA[
(define (make-withdraw balance)
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds")))
]]>
Put this in a drscheme window and try.
<![CDATA[
> (define amy (make-withdraw 70))
> (define matt (make-withdraw 40))
> matt
#<procedure>
> amy
#<procedure>
> (amy 50)
20
> (matt 50)
"Insufficient funds"
> (matt 25)
15
> (amy 0)
20
> (matt 0)
15
> (matt 10)
5
> (amy -100)
120
]]>
You can see that these accounts are procedures with local 'state'.
Matt's account is different from Amy's and each account keeps track
of its own balance. We change state by using the assignment operator:
"set!". Check out set! and begin in the r5rs manual.
It is a bit wierd to have to make deposits by
entering a negative amount and using 0 to find balance is also strange.
So let's improve these a bit.
<![CDATA[
(define (make-account balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(define (dispatch m)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
((eq? m 'balance) balance)
(else (error "Unknown request -- MAKE-ACCOUNT"
m))))
dispatch)
]]>
Now try:
<![CDATA[
> (define alex (make-account 400))
> (define mal (make-account 125))
> alex
#<procedure:dispatch>
> (alex 'balance)
400
> ((alex 'withdraw) 20)
380
> (alex 'balance)
380
> (mal 'balance)
125
>
> ((mal 'deposit) 230)
355
>
]]>
Again, an account is a procedure with local state. Each procedure keeps
its own private local state that does not interfere with any other accounts
local state.
Enough talk. It's time for
you to work and me to change from "sage on the stage" to
"guide on the side".
So now you code up solutions to ex 3.1 and 3.2 on page 224-5.
Show me your solution to 3.2
After you have finished those, code up a solution to ex 3.8 on
page 236. How can you test your answer? That is, how can you
be sure your f function does its job? Once you are sure that
your f function works, in what order does it appear that drscheme
evaluates the arguments to + ?
Ask any questions you may have.
<![CDATA[
]]>
<![CDATA[
]]>