![]() |
|
cond
, struct
sIn class, we've reviewed the design recipe and introduced Booleans and conditionals. Further, we've just barely introduced other kinds of data, symbols and structures. We'll review those here, and see how they influence the design recipe.
Note: There are more exercises here than will be covered during lab. We encourage you to try them on your own.
Index:
Built-in data: Booleans, symbols,
Data with cases (cond
),
Data with fields (define-struct
),
The revised design recipe,
Further exercises
First, let's quickly recall the design recipe (so far). We'll fill in some new steps during this lab, so we'll start with some funny numbering.
We've seen that DrScheme has
17
,
-42.89
,
3/17
,
etc.
true
, false
'central-daylight-time
,
'galatea2.2
,
'mary
,
etc.
|
Sample solution |
We've already seen examples in class of a particular pattern:
when our input data neatly falls into one of several cases,
use cond
("conditional").
We'd like to keep track of who the fastest runner is for the Rice track team. Of course, who is fastest depends entirely on what distance you're interested in. Let's assume we're interested in all distances, not just those used in track meets. Marianne is the team's best sprinter, consistently the best for the standard 100m and 200m distances, and generally for anything under 300m. Becca is the outstanding middle-distance runner for the standard 400m and 800m distances, but also from 300m to just under 1000m. Suzy is best for the long distances, from 1000m to just under 10000m. Finally, marathon specialist Yvonne outlasts everyone for races 10000m and up.
Let's write a function
|
Note that one of the first things you had to decide, was how to represent the distance (clearly a number is appropriate), and how to represent the runner (a bit of thought reveals that symbols works fine). As a group, discuss any ambiguities, issues, thoughts. Sample solution.
We could have shortened the sample solution by eliminating
the first part of the |
A biologist has the following model for lion population in the savannah: If the population is less than 800, then next year the population will grow by 10% (food is plentiful). If the population is more than 800 but less than 1100, the next year's population will grow by 2% (food is available, but scarce). If the population is 1100 or more, then disease is likely, and the next year's population will be down 30%. (COMP210 doesn't claim this is a reasonable model, especially given this function's discontinuity at 800!) With your partner, write a function which, given this year's lion-population, returns next year's lion-population (according to this model). Following the design recipe, of course! (Halfway through, the TAs will stop you to discuss any issues.) |
Sample solution. |
Is there anything in common about these examples? Really, we find there are often several categories of input. For example, we could write
; A lion-pop is one of: ; - an integer in [0,800) ; - an integer in [800,1100) ; - an integer in [1100,+inf.0)(Note the "half-open inteveral" notation, standard for mathematicians: the square-bracket means include the number in the interval, and the round-bracket means exclude the number from the interval. These are not meant to be scheme-parentheses. We'll use "+inf.0" to mean positive-infinity for now (note that we exclude infinity from being a
lion-pop
.)
|
Answers:
|
We might realize that our output should be an integer. How should we obtain an integer: round? truncate? You'd have to go back and ask the biologist! We won't worry about this issue for this problem, but again you're free to look at the manual in Help Desk, if you're curious about what rounding functions are provided by DrScheme. |
In summary, this "x, y, or z"
structure is a very common way to define data,
and you see that the code reflects this way of thinking
about the data:
There is one cond
branch
for each branch of data.
You've just re-watched the PowerPuff Girl movie yet again,
and you decide you want to write a program involving Townsville's heroes.
Before we even start to write any code at all,
our first question is: how will we represent any individual
PowerPuff girl (ppg
), in our program?
We decide that the aspects we want our program to represent
will be their name, color, ferocity-level (a number)
and whether or not they're conflict-avoidant.
(Note that we think about this before writing any code!)
Well, let's think about what types of data we could use.
Numbers? Naw; I don't think of them as girls number 1,2,3, so my program should not encode them as integers.
Booleans? Right out: (If nothing else, it's impossible by a counting argument: you can't represent three heroes with only two possible values!)
Symbols?
That's certainly possible, to have
'Blossom
,
'Bubbles
,
'Buttercup
.
It would mean we'd hand-craft functions such as
;; ppg->ferocity: symbol -> number ;; Given one of {'blossom,'buttercup,'bubbles}, ;; return their ferocity index, a number. ;; (define (ppg->ferocity a-name) ...)Similarly, you'd have functions to map from a name to a color, etc.
What drawback does this approach have? Upon reflection, it doesn't really capture how think about our heroes: Bubbles is one person, which captures many different attributes.
By not reflecting our thinking, it turns out this approach is also hard to maintain: If later a new series, "The PowerPuff Girls Kids", introduces the new hero "Burbles", you'd have to encode the new info by changing several functions in several different places. Bugs are introduced if you forget any of those places. Keep in mind that in large programs, these functions might be spread over multiple files and maintained by different programmers. Very easy to miss a bug!
Structures! We saw in class, we can make a new type of data, composed out of several smaller data. This reflects how we think about them; it also means that making a new hero will be done all at once, rather than changing a bunch of functions.
(define-struct ppg (name color ferocity ca?)) ; ; A PowerPuff Girl ("ppg") is: ; (make-ppg symbol symbol number Boolean) ; where name is the ppg's name, ; color is their color ; (presumably one of {'green,'blue,'red}, but perhaps different ; if new ppgs are ever created) ; ferocity is their ferocity index, a number. ; and ca? is whether or not they're conflict-avoidant.
This is a bit strange:
we're expanding the language by introducing
a new data type.
In addition to numbers, Booleans, and symbols, DrScheme now knows
about ppg
s!
We have not yet created any instances of this type --
that is, we haven't yet defined Blossom, etc.
Fortunately, the comments above,
which explained the meaning of the different fields
(or attributes),
also shows us how to create particular instances of ppg
s:
(make-ppg 'Buttercup 'green 90 false)
Go ahead and create the value for Blossom (red, ferocity 70, and not conflict-avoidant) and Bubbles (blue, ferocity 77, and conflict-avoidant, though The Professor notes she is actually much more empathic, suggesting that would be a better name for the data definition.) |
The result of make-ppg
is a particular structure.
Think of it as a chest of drawers (the fields), with
drawers labeled
name
,
ferocity
,
etc.
Within each drawer is the value of that field
('Buttercup
, 90
, etc).
Note that make-ppg
is a function which was
created automatically, after DrScheme evaluated your
define-struct
.
make-ppg
is called a constructor.
What is the contract for make-ppg ?
Discuss.
|
In addition to the constructor make-ppg
, DrScheme
automatically creates a few other functions
upon seeing your (define-struct ppg (name ...))
.
It creates four selectors (or accessors),
one for each of the specified fields. Two are
ppg-name : ppg -> symbol
ppg-ca? : ppg -> Boolean
define-struct
.)
What are the other two selectors for |
A mathematician notes that the selectors are the inverse-function
of the constructor.
In arithmetic there is an axiom that
"For any value of x,
x + 0 = x".
In Scheme they'd note the axiom
"For any symbols (symbol=? (ppg-color (make-ppg a b c d)) b) |
"Do I always have to type in
(make-ppg 'Buttercup 'green 90 false)
(make-ppg ...)
ppg
s are much more intricate things than numbers,
so representing them takes more keystrokes.)
Compare an ancient Roman taking this class,
bemoaning "Do i really have to type in four characters, '2000',
every time i want to call a function on the number MM?"
There is difference between a number, and its representation
(Arabic, Roman, etc.).
The representation of ppg
s is admittedly cumbersome.
(But we'll see later how to attach a name to any value -- be
it a number like 3.1415926535897932384626433,
or -- exactly analagously -- a ppg
like
(make-ppg 'Buttercup 'green 90 false)
Note how much we've accomplished, and we haven't yet even thought about what functions to write!. Fortunately, once we have a clear data definition, writing the functions is often the easy part.
Using the design recipe, develop a function
Challenge version:
If you've done this, make it a bit more complicated:
Actually, good negotiators are those who are either conflict-avoidant,
or have ferocity bigger than 20 and less than 80.
You may either use |
Sample solution. |
With your partner, develop a function |
Sample solution. |
What was involved in the preceding examples? We realized that when approaching a problem, the first thing we do, is decide how our program will represent data, in the problem we're modeling. Moreover, we've seen two common situations:
The data is of the form "x, y, or z".
Any particular function dealing with that data
will use a cond
, with one branch for
each type of data.
The data is of the form "x, y, and z". We use structures to encapsulate these three data into one conceptual datum. Any particular function dealing with that data will use the structure's selectors.
We'll close by updating our design recipe. (Note to labbies: Students haven't seen all these steps in class.)
cond
-- one branch per case of data.
(Note: You can write all the cond
questions first,
to distinguish the data, and come back later to worry
about the answer for a particular function.)
What is step 3? We'll talk about that in lecture: it will just be a case of saying that defining your data alone gives you enough information to write the skeleton of any function which processes that data! (viz. take the header, and include steps 6a or 6b). This is handy because you can write the skeleton just once, and then copy/paste it for every later function involving that data. |
Programming is not tinker & pray. (I.e., copying a similar-looking program from a book, then repeatedly making small changes, running some tests, and hoping it will work, and tinkering some more. That approach leaves people wandering, and only stops by hoping that passing some test cases mean it works on all other inputs too.) There is Process in creating a program: the form of your data guides the shape of your program; the design recipe elucidates this.
|
Sample solutions. |
©2003 Stephen Wong