Simple data definitions: cond, structs

In 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.

4. Function contract, purpose, header.
5. Function test cases.
6. Function body.
7. Function testing: Use your previously-written test cases.

We've seen that DrScheme has

• numbers: 17, -42.89, 3/17, etc.
• Booleans: true, false
• symbols: 'central-daylight-time, 'galatea2.2, 'mary, etc.

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").

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)

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.

Defining the data:

     (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 ppgs! We have not yet created any instances of this type -- that is, we haven't yet defined Blossom, etc.

Examples of the data

Fortunately, the comments above, which explained the meaning of the different fields (or attributes), also shows us how to create particular instances of ppgs:

     (make-ppg 'Buttercup 'green 90 false)

What's going on?

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.

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.
  (Note the convention of a trailing "?" indicating a Boolean function (or value). This falls out our happy choice of including "?" in our define-struct.)

     (symbol=? (ppg-color (make-ppg a b c d))
               b)
  

"Do I always have to type in (make-ppg 'Buttercup 'green 90 false) every time I want to refer to Buttercup? In a word, Yes. (Until next week.) The whole thing, (make-ppg ...), is just a value, in exactly the way 17.938 is just a particular value. (Though ppgs 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 ppgs 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).)

Functions using structures

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.

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.)

• 1. new Data definition: How, exactly, do you represent the problem in terms of Scheme data?
• 2. new Data examples.
• 4. Function contract, purpose, header.
• 5. Function test cases: Use your previously-written data examples.
• 6. Function body.
  1. new If your data has various cases, include a 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.)
  2. new If your data is a structure, your code will be using the various selectors for that structure. You can write these down before thinking about this particular function, like a good craftsperson inspecting what tools are available to complete the task with, before launching in blindly.
• 7. Function testing: Use your previously-written test cases.

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.

If you finish early...

©2003 Stephen Wong