CSE 1729 – Introduction to Principles of Programming November 15, 2016 Laboratory Assignment 11
Ob jectives
• Work with mutations • Work with objects
Activities
Editorial comment: the code you write in questions 1 will undoubtedly be less esthetically pleasing than the code you could write without destructive modification. Not that I am biased. -r.
1. Early in the course, we saw how to compute the factorial function using nondestructive func- tional programming. We’ve seen that a good way to do this is to define helper function which passes itself an accumulator at each recursive call. Using destructive assignment, we can use a helper function with no arguments that can update an accumulator in place rather than pass- ing it as an argument to itself. This helper function doesn’t even need to evaluate to anything useful, as the result ends up in the in-place accumulator.
What does this look like? Here is an example that takes this approach to sum the first n integers:
(define (sum-first-n n) (define sum 0) (define count 0) (define (helper)
(cond ((= count n) ’done)
(else
(set! count (+ count 1)) (set! sum (+ sum count)) (helper))))
(helper) sum)
Notably, when helper is finished, the result is in the variable sum.
(a) Write a new version of the factorial procedure (fact n) that works this way (that is, using a helper with no parameters that modifies an accumulated value). Make sure it works as intended by testing it on the numbers 1 through 5.
1
Solution:
(define (fact n) (define i 1)
(define prod 1) (define (helper)
(cond ((> i n) ’done) (else
(set! prod (* prod i)) (set! i (+ i 1)) (helper))))
(helper) prod)
(fact 1) (fact 2) (fact 3) (fact 4) (fact 5)
(b) We’ve also looked at procedures to compute “hailstone sequences.” Recall that a hailstone sequence is a sequence of numbers a1, a2, · · · such that
ai−1 if ai−1 is even ai= 2
3ai−1 + 1 otherwise
Write a procedure (hailstone n) that prints out all the numbers in the hailstone sequence starting from n using the approach above (that is, by using a helper function with no arguments, and a variable – initially the value hailstone was called with) – that helper changes). Your helper should include code to display the current number each time it is called. Note that calling (display x) will print out the value of the variable x, and calling (newline) will emit a line break.
Solution:
(define (hailstone n) (define (helper)
(display n)
(newline)
(cond ((= n 1) ’done)
((even? n)
(set! n (/ n 2)) (helper))
(else
(set! n (+ (* 3 n) 1)) (helper))))
(helper) n)
2
(hailstone 23)
2. Extend the bank account example in the slides with the following upgrade and new methods:
• withdraw – modify this method so it prints a message showing what the balance is and how much less than the request it is if the request is larger than the balance.
• accrue – add 1 year of simple interest to the balance. At first assume an interest rate of 1%
• setrate – change the interest rate to the given argument.
You may start with the following code which is (essentially) copied from the lecture slides:
(define (new-account initial-balance) (let ((balance initial-balance))
(define (deposit f)
(set! balance (+ balance f))
balance)
(define (withdraw f)
(cond ((> f balance) “Insufficient funds”) (else
(set! balance (- balance f))
balance ))) (define (bal-inq) balance)
(lambda (method)
(cond ((eq? method ’deposit) deposit)
((eq? method ’withdraw) withdraw)
((eq? method ’balance-inquire) bal-inq)))))
Solution:
(define (new-account initial-balance) (let ((balance initial-balance)
(interestrate 0.01)) (define (deposit f)
(set! balance
(+ balance f))
balance)
(define (withdraw f)
(cond ((< balance f)
(display "Withdrawal not allowed since balance is ") (display f)
3
(display " which is less than the request by ") (display (- f balance))
(newline))
(else
(set! balance (- balance f)) balance )))
(define (bal-inq) balance) (define (accrue)
(set! balance(+ balance
(* balance
interestrate )))
balance)
(define (setrate r) (set! interestrate r)) (lambda (method)
(cond ((eq? method ’deposit) deposit)
((eq? method ’withdraw) withdraw)
((eq? method ’balance-inquire) bal-inq) ((eq? method ’accrue) accrue)
((eq? method ’setrate) setrate)))))
3. Create two bank account objects and demonstrate that the balance and rate can be set and modified independently.
Solution:
(define acct1 (new-account 100))
(define acct2 (new-account 100))
((acct1 ’deposit) 50)
((acct1 ’balance-inquire)); should be different ((acct2 ’balance-inquire))
((acct1 ’withdraw) 50)
((acct1 ’balance-inquire)); should be same ((acct2 ’balance-inquire))
((acct2 ’setrate) 0.02)
((acct1 ’accrue)); should be different ((acct1 ’accrue))
4. Show how to implement Stacks as objects. You can base your implementation on a list, and you should provide the following methods:
• is-empty? – true if the stack is empty.
• push – adds an element to the top of the stack
4
• top – returns the top element of the stack without changing the stack
• pop – returns the top element of the stack, which is removed from the stack
Use the “standard” form for defining an object: when you make an object, it returns a function that can be used to access or modify parts of the object. See, for example, the bank account code given above – (define my-acct (new-account 100) sets my-acct to be a bank account with balance of 100, and ((my-acct ’deposit) 10) would add 10 to its balance. Use the code below as a starting point for Stack.
(define (make-stack)
(let ((state-variable initial-value))
(define (is-empty?) ...)
(define (push thing-to-push) ...)
(define (top) ...)
(define (pop) ...)
(lambda (meth-name)
(cond ((eq? meth-name ’is-empty)
is-empty ?)
((eq? meth-name ’push)
push)
((eq? meth-name ’top)
top)
((eq? meth-name ’pop)
pop )))))
Solution:
(define (make-stack) (define S ’())
(define (is-empty? x) (null? S)) (define (push x)
(set! S (cons x S))) (define (top)
(car S)) (define (pop)
(let ((ret-val (car S))) (set! S (cdr S)) ret-val ))
(lambda (meth-name)
(cond ((eq? meth-name ’is-empty)
is-empty ?)
5
((eq? meth-name ’push) push)
((eq? meth-name ’top) top)
((eq? meth-name ’pop) pop ))))
5. You have seen set!: there are other destructive operators that work on pairs: • (set-car! lst val) changes lst so that (car lst) refers to val
• (set-cdr! lst val) changes lst so that (cdr lst) refers to val
The interesting thing about these is that if you use them to change a list, the list changes, and
any variable refering to that list changes. Consider the following:
>(define a ’(1 2 3)) >a
(1 2 3)
>(set-car! a ’fish) >a
(fish 2 3)
>(set-cdr! (cdr a) ’(eat)) >a
(fish 2 eat)
The set-cdr! in the example illustrates that changing a part of a list destructively changes the whole list. Let’s try it and see what happens.
(a) Write a Scheme function called nconc! that does append destructively. Remember how append works:
On each recursive call for which x is not empty, we build a new list using cons. Here is an alternative:
1. Recursively cdr down list x until you reach the last element
2. Set the cdr of that last element to be y
Write the scheme function nconc! x y that implements the above alternative. It should
return a list that looks just like what you would get from append.
6
(define (append x y) (if (null? x)
y
(cons (car x)(append (cdr x) y))))
Solution:
(define (nconc! x y) (define (last-pair x) (if (null? (cdr x))
x
(last-pair (cdr x)))) (cond ((not (null? x))
(set-cdr! (last-pair x) y)
x)
(else y)))
(b) Demonstrate that append and nconc! behave differently. Try the following:
(define a ’(1 2 3)) (define b ’(4 5 6)) (append a b)
a
b
(nconc! a b) a
b
Solution:
> (define a ’(1 2 3)) > (define b ’(4 5 6)) > (append a b)
(1 2 3 4 5 6)
>a
(1 2 3)
>b
(4 5 6)
> (nconc! a b)
(1 2 3 4 5 6)
>a
(1 2 3 4 5 6)
>b
(4 5 6)
> (nconc! a a)
#0=(1 2 3 4 5 6 . #0#)
;The difference is that nconc! changes a — it tacks b onto the end. ;If I nconc! a onto a, I get a repeating list, because the last cons ;cell in a’s cdr pointer refers to the first cell in a.
7
How do you explain the differences? What do you think would happen if you evaluated (nconc! a a)? (Hint: try drawing some box-and-pointer diagrams.)
8