Comp 210 Lab 6


xbuffy
======

When you log in, you will notice an "xbuffy" window which tells you
 * when you have new mail
 * when there are new messages on the Comp 210 newsgroup
You can also click on the notifications to start up Pine (reading your
mail) or Netscape (reading the newsgroup).  Please keep up-to-date with the
Comp 210 newsgroup, as valuable information is disseminated by way of it.


define-structure and constructors
=================================

We know that calling define-structure creates constructors, predicates, and
selectors.  For instance, suppose we have the data definition

  <two-list> :=   (empty)
		| (full name value others)
    where name is a symbol, value is a number, and others is a <two-list>

We would do

   (define-structure (two-list-empty))
   (define-structure (two-list-full name value others))

which would create functions

   make-two-list-empty, make-two-list-full
   two-list-empty?, two-list-full?
   two-list-full-name, two-list-full-value, two-list-full-others

Then we could write functions that operated on <two-list>s; for instance,
we could sum up all the values in a two-list.

Write two-list-sum as an exercise.

  (define two-list-sum
    (lambda (tl)
      (cond ((two-list-empty? tl)
	     0)
            ((two-list-full? tl)
	     (+ (two-list-full-value tl)
                (two-list-sum (two-list-full-others tl))))
            (else
	     (list "two-list-sum expects a two-list but was given" tl)))))

Now we can call two-list-sum:

  (define stooge-two-list
    (make-two-list-full
     'larry 7
     (make-two-list-full
      'curly 5
      (make-two-list-full
       'moe 10
       (make-two-list-empty)))))

  (two-list-sum stooge-two-list) => 22

Notice that if we call two-list-sum on something that isn't a two-list, we
get a helpful error report:

  (two-list-sum 100) => (list "two-list-sum expects a two-list but was given" 100)

Using the else clause in this way is very good programming style, because
it helps to guard against inevitable errors.

Unfortunately, we can make other sorts of errors when we create
<two-list-sum>s.  Suppose I did this:

  (define stooge-two-list-2
    (make-two-list-full
     'larry 7
     (make-two-list-full
      5 'curly
      (make-two-list-full
       'moe 10
       (make-two-list-empty)))))

(Notice that I have accidentally swapped 'curly and 5.)  This succeeds and
creates something that looks like a two-list, but isn't really one because
it doesn't satisfy the "where" clause of the data definition.

An hour later, I might decide to sum up stooge-list.

  (two-list-sum stooge-two-list-2) => "Error in +: curly is not a number"

I would rather have been told when I created stooge-two-list-2 that there
was a problem, rather than much later.  (I might have corrupted other data
structures in the meanwhile, also invisibly.)

In order to avoid this problem, which was endemic on the last homework, we
will issue a new convention that you must follow when converting data
definitions into define-structure forms.

define-structure defines a constructor (named make-struct, if the structure
is called struct).  You should define your own constructor named
create-struct which calls make-struct, and then you should never call
make-struct again.  Instead, always call create-struct.  Create-struct
simply checks its arguments, then calls make-struct.  For instance, we
would convert this data definition

  <two-list> :=   (empty)
		| (full name value others)
    where name is a symbol, value is a number, and others is a <two-list>

into the following Scheme code:

   (define-structure (two-list-empty))
   (define create-two-list-empty
     (lambda ()
       ;; no checks to do, since no arguments
       (make-two-list-empty)))

   (define-structure (two-list-full name value others))
   (define create-two-list-full
     (lambda (name value others)
       (cond ((not (symbol? name))
              (error 'create-two-list-full "arg 1 should be symbol, was ~s" name))
	     ((not (number? value))
              (error 'create-two-list-full "arg 2 should be number, was ~s" value))
	     ((not (two-list? others))
              (error 'create-two-list-full "arg 3 should be two-list, was ~s" others))
             (else
	      ;; Everything checks out; call make-two-list-full
	      (make-two-list-full name value others)))))

"But wait!", you say.  What is "two-list?".  We will need to define that too.
A thing is a two-list if it is either a two-list-empty or a two-list-full.

   (define two-list?
     (lambda (object)
       (or (two-list-empty? object) (two-list-full? object))))

So from now on, when you convert a type to define-structure forms, you
should
 * define a create-* function for each make-* function
 * never use the make-* function (except in the create-* function)
 * define a predicate for the entire type (using the predicates for each
   variety of the type)

Using our new definition, if we make an error during construction:

  (create-two-list-full
   7 'larry
   (create-two-list-full
    'curly 5
    (create-two-list-full
     'moe 10
     (create-two-list-empty))))

we are informed right away, and evaluation does not proceed -- just as if
we had tried to add a symbol to a number, or cons a symbol onto a number.

Use the "error" procedure as follows:
 * first argument is a symbol, the name of the current procedure
 * second argument is a string which contains zero or more instances of "~s"
 * remaining arguments: anything, but there should be one for each "~s"
     in the second argument

It is acceptable, easier to type, but slightly less informative, to put all
the tests together and have just one error message:

   (define create-two-list-full
     (lambda (name value others)
       (if (and (symbol? name) (number? value) (two-list? others))
	   ;; Arguments are fine; call make-two-list-full
	   (make-two-list-full name value others)
           ;; Some argument was wrong
	   (error 'create-two-list-full
		  "bad argument; expected symbol: ~s, number: ~s two-list: ~s"
                  name value others))))


type discipline
===============

It's incredibly important to get the types right.  That's why I always put
a comment at the top of each function I write which documents what types of
arguments it expects and what type of value it returns.  This also helps me
to understand my intention if I haven't chosen perfect function names.

Once you have decided what type of value a function returns, then make sure
that it always returns that kind of thing.  Check both the "then" and the
"else" parts of an if expression.  Check each arm of a cond expression.  If
you get the types right, then you are generally on the trck to getting the
entire function right.

If something is going wrong somewhere, you might want to consider checking
your arguments to make sure they are correct, and calling error if there is
a problem, so you can find out what is wrong right away.


practice with functions as values and currying
==============================================

For each of the following expressions, try to understand what happens, and
why.  Then "step" through each one (in order) in Donkey to see whether you
understood.  Ask a labby if you are confused.  This part of the lab is
intended to reinforce Wednesday's lecture.


(define curried-cons
  (lambda (x)
    (lambda (y)
      (cons x y))))

(curried-cons 'first (list 'second 'third))

((curried-cons 'first) (list 'second 'third))

(define cons-foo (curried-cons 'foo))

(cons-foo (list 'bar 'baz))

(define cons-x
  (lambda (y)
    (cons x y)))

(define cons-supply-x
  (lambda (x)
    cons-x))

((cons-supply-x 'first) (list 'the 'rest))

(define x 'last)

((cons-supply-x 'first) (list 'the 'rest))