Comp 210 Lab 3: define-struct

Index: define-struct, Kingdom example

How would you represent a "pair" in Scheme? An "association", from homework, was just a special kind of pair, for example. So far, we would have represented it as a two-element list. Well, that seems kind of strange:

• A two-element list contains a empty as an end-marker, which we don't need because we know we'll have exactly two elements.
• Accessing the second element is more difficult than the first, i.e., compare (first (rest pair)) vs. (first pair), respectively.

First, congratulations you have graduated to DrScheme's "intermediate" language level! What we will be introducing isn't allowed in the beginner level. In DrScheme, select Configure Language Level from the Language Level menu. Choose Intermediate from the resulting menu. Restart DrScheme.

OK, back to pairs. What are the important things about pairs? Most importantly, they contain exactly two elements. Also, it would be nice to have helper functions like Scheme provides for numbers, lists, etc.:

• constructors, like cons, and
• predicates, like cons?,
• selectors, like first and rest

Scheme gives us a way to define all of that at once: (define-struct pair (first second)). This defines several functions:

• make-pair, which takes two arguments and returns a "pair" of those arguments (constructor),
• pair?, which takes one argument and returns whether that it a "pair" (predicate), and
• pair-first and pair-second, which each take one argument, a "pair", and returns the appropriate element of it (selector).

But what is the "pair"? Well, all we care about is that it has two elements in it and that we can make them, test them, and look inside them. Do we care what they really are inside the computer? You'll notice that the result of (make-pair 1 2) does not print as (cons 1 (cons 2 empty)). In fact, Scheme considers the two to be distinct values.

Would it matter if we had typed (define-struct pair (second first)), instead?

Defining structures in Donkey

Alas, whereas DrScheme uses define-struct, Donkey uses something slightly different.

• In DrScheme: (define-struct foo (a b)).
• In Donkey: (define-structure (foo a b)).

Consider the following data definition, which describes the structure of a medieval kingdom:

• regent is (make-regent general aide)
  where general is a knight, and aide is a serf.
• knight is one of
  • (make-private salary)
  • (make-officer fellow squire servant salary)
  where fellow is a knight, squire and servant are serfs, and salary is a number (of potatoes to be paid).
• serf is one of
  • (make-simpleton potatoes)
  • (make-idiot)
  where potatoes is a number (of potatoes raised).

Do the following, answering the questions. When you're done, you can look at the answers.

• Is there any recursion in this?
• Write the appropriate uses of define-struct. How many uses do we need?
• List the functions that these uses of define-struct make. How many constructors, predicates, and selectors are there?
• Make some example data.
• Create all the program templates for functions of one input on these data types. How many templates do we need?
• Write a function that counts the number of potatoes grown in a kingdom. (simpletons generate potatoes, idiots are too stupid to raise potatoes. knights and regents are too important to farm themselves.) The function should take a regent as its argument and return a number. Including helper functions, how many functions should you write?
• Create test data for any "potato functions". To be thorough, how many pieces of test data do we need?

A hint of mutual recursion

You haven't seen this in lecture yet, but here's something to think about.

Let's add to our data definition:

• serf is one of
  • ...
  • ...
  • (make-spy potatoes rebel)
    where potatoes is a number (of potatoes stolen), and rebel is a regent (whom the spy really works for

How would we change our potato-counting program? (Spies steal potatoes.)

Write a function that checks if a kingdom has any spys working against it. The function should take a regent as its argument and return a boolean.

• Q: Do we need to write templates for this function?
• A: No, each function doesn't require a template, just each input data type, and we've already written templates for these datatypes.

• Q: How many functions should you write in total for this?
• A: 3, like before. To write a function has-spies-regent?, we need helper functions has-spies-knight? and is-spy-serf?.

Create test data for this function.

• Q: How many pieces of test data do we need?
• A: Assume we test each function separately since we know that is easier than testing just the main function. We need at least three different serfs, one of each kind. We need at least two knights, one of each kind. For completeness, we need nine (a private plus eight officers, each combination of his fellow possibly having a spy and his squire and servant possibly being spies). We need at least one regent, of the only kind. For completeness, we need four (each combination of his general possibly having a spy and his aide possibly being a spy). This would test all the cases of any reasonable implementation.