Comp 210 Lab 3: Data Definitions

Index: Simple data definitions,

In class we described a multi-step process for writing programs, based upon a data definition. Our example data definition was for a list of symbols:

A list_of_symbols is

• empty (the empty list), or
• (cons symbol list_of_symbols),

Let's try another example that you'll need for your homework, natural numbers, i.e., a non-negative integer.

For now, we are rather pedantic about our multi-step programming process to ensure that you learn good programming skills. With practice, it becomes habit for you to think about all the necessary steps. Our process is

1. Make your data definition(s).

   A natural_number is

   • 0 (zero), or
   • (add1 natural_number).

2. Make sample elements of your data. This should include at least one of each case of the data definition(s).

   For natural numbers, we have

   • 0
   • (add1 0), which Scheme writes as 1
   • (add1 (add1 0)), which Scheme writes as 2

3. Make a program template for each data definition. In each template,

   1. perform a case analysis -- a function case for each data definition case,
   2. extract the available data, and
   3. identify natural recursion -- the function may be recursive whenever the data is recursive.
   In other words, this means looking at the shape of your input data and writing all of the potentially useful information about your function based only on this shape. A template does not include information about the meaning of the function, i.e., what it computes.

   Do this for functions on natural numbers. You should use the following two functions:

   • zero? returns whether a number is zero or not.
   • sub1 extracts the natural number stored in a natural number, i.e., it subtracts one.

4. Give the contract and description for each function.

   Do this step and the following ones for the following sample functions:

   • sum_0_to_n, which returns the sum of all natural numbers from zero to the input n.
   • power_of_2, which returns two to the given exponent. (Do not use the built-in exponentiation function when writing this.)
   • list_of_ones, which, given a number n, returns a list containing n copies of the number 1. (Hmm... this is just unary notation for numbers. Isn't this similar to natural numbers?)
   • list_upto_n, which, given a number n, returns a list containing the natural numbers zero up to n in reverse order, i.e., (list_upto_n 1) = (cons 1 (cons 0 empty)).
   • Whatever else you like.

5. Provide examples of what these functions should do. Presumably, this should use the sample data already listed. Remember that your examples should illustrate what should happen for each interesting case of each function.

6. Write your program by filling in the templates.

7. Test these functions, using the examples.

Try some other example kinds of data:

• How would you define a list that can contain both symbols and numbers?

  Hint: as one option, you can either think of an empty list, or building a list with a symbol, or building a list with a number; as another option, you can think of an empty list, or building a list with a symbol or a number. Do you see the difference? There's nothing too mysterious -- they are equivalent, of course.

• Sometimes you want to have a program that allows all lists, and for some reason check if a list has even length, for example. Other times you want to allow only even length lists.

  How would you define even (0, 2, 4, etc.) length lists of numbers?

• How would you define a non-empty list of symbols? By this we mean that an empty list should not meet your data definition. Also, this means that your template does not need to test for the empty list. But, you will still need a base case for your data -- what will it be?

For the curious...

In the future, we'll talk about templates and functions using multiple "interesting" inputs (i.e., multiple inputs that we need to recur on). But can you generalize some of the above functions and write the following:

• power, which returns the exponentiation of one argument to the other argument.
• list_of_xs, which, given a number n, returns a list containing n copies of the the other argument.

• sum_i_to_n, which returns the sum of all natural numbers from an input i up to the other input n. Assume 0<=i<=n.