Spring 1996
If you did well on the last homework, you are likely to do well on the test. If there were parts of the homework you didn't understand, you are likely to have trouble on the test.
Today we will review for the test by getting more practice writing programs with recursive user-defined datatypes. Remember the four-step process for writing correct programs:
There are two basic types of data definition. One contains alternatives; for instance, a bug is either an insect (in which case we are interested in how many legs it has an which poisons it is resistant to) or a program error( in which case we are interested in which function it appears in).
<bug> := (insect legs poison-resistance)
| (program-error function)
where legs is a number, poison-resistance is a list of symbols,
and function is a symbol
The other type of data definition contains no alternatives. For instance,
all wigs are basically the same (earwigs excepted, since they are bus) and
have three identifying traits: color, length, and style.
<wig> := (color length style) where color and style are a symbols and length is a number
There are two different rules for turning the two types of data definitions
into calls to define-structuredefine-structure
(define-structure (bug-insect legs poison-resistance)) (define-structure (bug-program-error function))If there are no alternatives, we call
define-structure(define-structure (wig color length style))Do not try to use
(define-structure (wig-color length style)) ; wrong!This defines a new type named wig-color which has two components, length and style. That isn't what you want.
The rationale for the different rules for making define-structure
We can break building the program schema into the following four steps.
This part always contains a definelambda
(define schemaname
(lambda (arg1 arg2)
or
(define list-fn
(lambda (l)
It's a bit dangerous to use the final procedure name as the schema name,
because you may put bits of information that are specific to that procedure
in the schema. Schemas are supposed to contain only code that is
universally applicable; the schemas for two very different functions that
happen to take the same type of arguments will be identical. I often use
???type-fntype
If there are multiple possibilities for the particular kind of value, then
use a predicate (ifconddefine-structure
<gem> := (diamond color clarity carats cut)
| (ruby redness)
| (rhinestone tackiness glitter)
where color is a ... and clarity is a ... and glitter is a ... .
If your input is a gem, it might be a diamond, a ruby, or a rhinestone, so at this point your schema would look like this:
(define gem-fn
(lambda (g) ; g is a gem
(cond ((gem-diamond? g) ... )
((gem-ruby? g) ... )
((gem-rhinestone g) ... ))))
If there are multiple arguments, then you must consider every possible combination of values for those arguments. For instance, to set a gem in a ring made of either silver or gold, you would have to consider silver rings with each gem, and gold rings with each gem:
(define ring-gem-fn
(lambda (r g) ; r is a ring, g is a gem
(cond ((and (ring-silver? r) (gem-diamond? g)) ... )
((and (ring-silver? r) (gem-ruby? g)) ... )
((and (ring-silver? r) (gem-rhinestone g)) ... )
((and (ring-gold? r) (gem-diamond? g)) ... )
((and (ring-gold? r) (gem-ruby? g)) ... )
((and (ring-gold? r) (gem-rhinestone g)) ... ))))
You can think of the six alternatives as corresponding to the elements of
this matrix:
Make sure that you deal with each box of the matrix separately. (You might want to draw the matrix for yourself and check off each box as you include it in the schema.)
If there is only one possibility for what the input is, then you don't need any predicates at all. (When working with numbers, it is often helpful to think of them as either zero or non-zero, and do different things in the different cases.)
Now each ellipsis in the partially-completed schema is manipulating just
one type of data. For user-defined types, we don't want to treat the whole
thing as a single monolithic entity; we want to get at the pieces
individually. We use the selectors created by define-structure
(define gem-fn
(lambda (g) ; g is a gem
(cond ((gem-diamond? g)
... (gem-diamond-color g) ... (gem-diamond-clarity g)
... (gem-diamond-carats g) ... (gem-diamond-cut g) ... )
((gem-ruby? g)
... (gem-ruby-redness g) ... )
((gem-rhinestone g)
... (gem-rhinestone-tackiness g) ... (gem-rhinestone-glitter g) ... ))))
The selectors inserted in the previous step extract pieces from tuples (structures). We need to figure out what to do with these pieces. If they are atomic datatypes (such as numbers, booleans, symbols, etc.), then the function can manipulate them directly. If they are compound data types (they can be made up of more than one thing, or have alternatives), then we write helper functions for each such type.
In other words, only decompose the arguments to the function; don't decompose the parts of those arguments. Thus, the structure of each function closely mirrors the structure of the data definition(s) for the function's input(s).
Writing helper functions to process subparts permits automating the process, keeps functions small and easy to understand, and can help you avoid writing the same code twice (since it appears only once in the helper function, which you may call as often as need be).
Consider the following data definition, which describes the structure of a medieval kingdom:
<king> := (no-subjects)
| (subjects peer lord)
where peer is a duke and lord is a king.
<duke> := (weakling fighter farmer)
| (powerful colleague fortknight midknight)
where fighter, fortknight, and midknight are knights, farmer is a serf,
and colleague is a duke.
<knight> := (squire servant)
where squire and servant are serfs
<serf> := (potatoes)
where potatoes is a number
Write a function that counts the number of potatoes grown in a kingdom. (The function should take a king as its argument and return a number.)
Write a function that counts the total number of subjects of a king.