This is the archived website of SI 413 from the Fall 2012 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.
This lab is due at 0900 next Tuesday, September 18. It should
contain a single Scheme file lab3.scm, as well as a subfolder
called tests with your tests, like the last lab. See the
submit page and lab 2 page
for details on how the auto-testing and submission work.
MODIFICATION: You only have to complete one out of exercises 2 and 3. (If you do both, it will count as a bonus.) Exercise 7 (set intersection) and 10 (tail recursion for sets) are also bonus problems, which you are not required to complete.
Lots of Scheme functions like +, max,
and even <, take a variable number of arguments.
For example:
> (+ 1 2) 3 > (+ 1 2 3) 6 > (+ 3) 3 > (+) 0 > (> 3 2 1) #t > (> 3 1 2) #f
How can we write our own functions to behave this way? Well, there are two ways. First, if in a lambda-expression, you put a variable name in place of the entire parameter list, your function gets as its argument that variable only, and it will be a list of all the actual arguments. Since a list can have any length, your function can take any number of arguments!
> (define avg (lambda vals (/ (apply + vals) (length vals)))) > (avg 95 80 86) 87 > (avg 13) 13 > (avg 85.0 62 77 84 78 92 90 58) 78.25
Some functions take a variable number of arguments, but
must have at least some fixed number. For example, the
-
function must have at least one argument, as must max.
In fact, the interpreter enforces this ... go ahead and
try calling (max).
Our avg should be defined
this way, since calling it with no arguments would give a
divide-by-zero error.
We can get a variable number of
arguments another way that lets us specify that at least
some arguments must be present. In the parameter list for
the lambda-expression (or function defined in our usual
way, without lambdas), specify the variables that must be
there in the usual way, then put a . followed by
just one more
variable name. The name following the period will be a
list of all the optional arguments, while those variables
before the . are mandatory.
> (define (avg x . vals)(/ (+ x (apply + vals))(+ 1 (length vals))))> (avg 1.0 5 7) 4.333333333333333 > (avg 1 5) 3 > (avg 1) 1 > (avg) ;This one will give an error!
min-sin that takes one or more
numbers as arguments and returns the one with the smallest sine, as
returned by the built-in sin function.(min-sin 1.1 2.3 4.5 6.7)should return
4.5 since
sin(4.5), which is about -0.98, is smaller than all the other sines.
cadr and
cddadr? You may be dismayed to discover that these stop
after 4 d's and a's, so for example caadaar is not
a built-in function in Scheme.make-cXr
that takes any number of 'a and 'd symbols
as arguments, and returns another function to do that series
of cars and cdrs.> ((make-cXr 'a 'd 'd) '(1 2 3 4 5)) 3 > (define caaaaaadr (make-cXr 'a 'a 'a 'a 'a 'a 'd)) > (caaaaaadr '((1 2) ((((((3)))))))) (3)
group whose first argument
is an integer k that takes its remaining arguments and
"groups" them such that each consecutive k arguments
becomes a group. The function returns a list of groups
... where each group is itself a list.
Careful: This is a bit tricky!
> (group 2 'a 1 'b 2 'c 3) ((a 1) (b 2) (c 3)) > (group 3 'a 1 'b 2 'c 3) ((a 1 b) (2 c 3)) > (group 4 'a 1 'b 2 'c 3) ((a 1 b 2) (c 3)) > (group 5) ()
The C++ view of object-oriented programming is "I've got this data, wouldn't it be nice to package it together with functions?" The Scheme view is "I've got functions, wouldn't it be nice to package them together with data?" Either way, you get to the same place. Closures, of course, is how you package data together with a function. Let's see how that might give you an "object". In particular, let's make an object that models a bank account, where you can make deposits and withdrawals.
First of all notice that a closure is a single function, so
that the C++/Java model of an object with lots of member
functions is not quite what we'll have. Instead, we will
view ourselves as interacting with objects by sending
messages. Thus, the function that is our
object is a message-processing function. So instead of
calling a member function withdraw, we will
send the 'withdraw message. And instead of
calling a member function deposit, we will
send the 'deposit message. So the function
that is our closure will take two arguments: the message,
which will be 'deposit or
'withdraw, and the data associated with the
message, which will simply be the amount.
(define bankAcct (let ((bal 0)) (lambda (message data) (cond [(symbol=? message 'deposit) (set! bal (+ bal data)) bal] [(symbol=? message 'withdraw) (set! bal (- bal data)) bal]))))
This creates a new closure named bankAcct, which
has as its only persistent data bal. Since
bankAcct is a closure, it is a function. When
you call it, it expects two arguments - message
and data. Here's how you might use this object:
> (bankAcct 'deposit 10.50) 10.5 > (bankAcct 'withdraw 6.75) 3.75
Now, one serious limitation to this scheme is that we only
have one bank account object. What if we want to model an
entire bank, with thousands of accounts? We certainly don't
want to copy and past the code (let ((bal 0) ...)
thousands of times. Instead, let's write a function
make-account that returns a new bank account
object.
(define (make-account) (let ((bal 0)) (lambda (message data) (cond [(symbol=? message 'deposit) (set! bal (+ bal data)) bal] [(symbol=? message 'withdraw) (set! bal (- bal data)) bal]))))
Now we can use make-account to make as many
bank account objects as we want.
> (define myacct (make-account)) > (define youracct (make-account)) > (myacct 'deposit 25.50) 25.5 > (myacct 'withdraw 14.23) 11.27 > (youracct 'deposit 20.00) 20.0
So where do we go from here? Well, it'd be nice to add a
'balance message that would simply get the
balance for you ... of course that would cause problems
since there wouldn't be any data parameter for
that message. Thus, we'd need to rewrite this thing using
one of the variable argument constructs. Of course some
functions for signalling that the account should accrue one
month's interest would be good too ... what about setting
interest rates ...
make-stack that creates
"stack objects". Your stack should allow the following messages:
'size: Returns the number of
elements in the stack.'pop: Removes the top element of the
stack and returns it. (You can assume that the size of the stack
is at least 1 before this method is called.)'push x1 x2 ...: Takes any number of
additional objects and puts them on the stack.
Note: normally "push" puts a single new object on
the top of the stack. Your stack will allow an arbitrary
number of arguments, and the effect will be to add them as
if they had been pushed individually from right to left.Here's an example:
> (define S1 (make-stack)) > (S1 'size) 0 > (S1 'push 3 'a 2.1) > (S1 'pop) 3 > (S1 'push 'x) > (S1 'pop) x > (S1 'pop) a > (S1 'size) 1
I recommend using a list as the internal data structure, with
the car of the list being the top of the stack.
make-set function which returns an "object"
function which just supports basic getting and setting of the underlying
storage. You will need this for the later functions, and for debugging
while you write them.
'get: Returns the underlying list that stores the set.'set! L: Sets the underlying list storage to L.
(You don't have to check that L is sorted and doesn't
contain any duplicates.) The return should be void.'size: Returns the number of distinct elements in the
set.make-set to support two more messages. You
will probably want to write helper functions for these.
'insert! x1 x2 ...:
Takes any number of numbers x1, x2, etc., and
inserts each of them into the set, if they're not already there.
The numbers x1... are not necessarily in sorted order,
but they must be stored in sorted order within the set!
The return should be void.
'contains? x: Returns true or false depending on whether
the set has the number x in it. (This one only takes
a single argument.)
> (define S1 (make-set)) > (S1 'get) () > (S1 'size) 0 > (S1 'contains? 10) #f > (S1 'insert! 10) > (S1 'contains? 10) #t > (S1 'insert! 15 3) > (S1 'get) (3 10 15) > (S1 'contains? 11) #f > (S1 'contains? 15) #t > (S1 'set! (list 14)) > (S1 'size) 1 > (S1 'contains? 15) #f > (define S2 (make-set)) > (S2 'contains? 14) #f
make-set to support one more message.
'intersect S returns a new set that contains
all the elements that are in both this set and in S.
You will definitely have to use the 'get and 'set
messages, and write a helper function or two!
> (define S1 (make-set)) > (S1 'insert! 5 2 53 9 10) > (define S2 (make-set)) > (S2 'insert! 6 7 2 10 11 83 5) > (define S3 (S1 'intersect S2)) > (S3 'size) 3 > (S3 'contains? 6) #f > (S3 'contains? 10) #t
union, set-difference, and
subset?.
In class we looked at the way recursion gets implemented, and why Java or C++ programmers sometimes want to avoid it. It has to do with the stack space required for all the recursive calls.
For example, here is the range function from
Lab 2:
; Returns a list containing integers a, a+1, ..., b. (define (range a b) (if (> a b) null (cons a (range (+ a 1) b))))
If we followed the execution of something like
(range 10 20), we would see that it goes all the
way down to (range 21 20) before doing anything,
and then all those function calls are "popped" off the stack
one at a time as each cons is performed to get
the answer.
Well what if we wrote range like this
instead:
(define (range-helper a b accum) (if (> a b) accum (range-helper a (- b 1) (cons b accum)))) (define (range a b) (range-helper a b '()))
Yes, this is a little more verbose, but it's going to use a lot
less memory. The reason is that range-helper is
tail-recursive, meaning that all the recursive calls
to range-helper don't have to be saved on the stack
at once.
The idea behind this function is that accum
carries around the information that would normally have to be
saved in the function call stack.
Definition: A function is tail recursive if its output expression in every recursive case is only the recursive call.
In Scheme, this means that the recursive call is
outermost in every returned expression. By "outermost", I mean
it's the last thing in a let or lambda body,
or the second or third thing in a if statement, or the last
thing in a cond clause, etc. If you want to be fancy about it,
you say that the recursive call in these cases is in tail position.
In C/C++/Java, a tail-recursive function can be identified
by looking at the return statement(s) for the
recursive case(s): if the recursive call itself is the
outermost expression in the return, the function
is tail-recursive. The fundamental idea is that the result
returned by the recursive call is the answer; nothing else
needs to be done with it. In that case, there's no reason to
pop records off the stack of recursive calls, and if you're
never going to pop them off, they needn't be pushed in the
first place.
The original range function above
is not tail recursive because the output expression in the recursive
case is (cons a (range (+ a 1) b)), which while
it contains a recursive call is not just a
recursive call. In contrast, the recursive case of
range-helper
has output expression
(range-helper a (- b 1) (cons b accum)), which
is just a recursive call.
As we noted above, with tail recursive functions we could actually forget about the stack and only ever remember what would ordinarily be the top record of the stack. Thus, tail recursive functions can be optimized to take less memory - and usually to run faster as well. Scheme interpreters are required to make this optimization whenever functions are defined tail-recursively.
;TAIL RECURSIVE in comments
so I know which one.
OPTIONAL: do all three!
'insert! or
'intersect from exercises 6 and 7 to make the function
tail recursive.
Indicate ;TAIL RECURSIVE in comments
so I know which one.
OPTIONAL: do all of your set functions!