Comp 210 Lab 2: Data Definitions

Index: Simple data definitions, Donkey, Scheme style


Simple Data Definitions

In class we saw the data definition for a list of numbers:

A list of numbers is

It is good practice always to write your data definitions. This will be expected to do this on most Comp210 homeworks. In Scheme, the data definitions are not part of your program, but it is good practice to include them as comments in your code, e.g.,

; A LoN (list of numbers) is one of
;   1) null
;   2) (cons f r), where f is a number, r is a LoN
In some programming languages, some form of data definitions are part of the program and used by the computer. Regardless of programming language, it will be important to clearly remember your data definition when writing your program.

Our five steps are

  1. Make a data definition
  2. Make a program template, including
    1. Perform a case analysis
    2. Extract the available data
    3. Identify natural recursion
  3. Describe each function to be defined and provide examples of what they should do
  4. Write these functions, using the template
  5. Test these functions, using the examples
For the beginning of this class, we will be very pedantic about following these steps. As these ideas become second nature, we can relax them.

Try some other examples:


Donkey

Like DrScheme, Donkey is a programming environment for Scheme. While DrScheme is generally better, Donkey has one important feature that DrScheme lacks: it allows you to see how your program is evaluated. This lab shows you how to use that feature.

To run Donkey, either

(This assumes you have run register comp210. If not, you can enter /home/comp210/bin/donkey.)

As an example, type (if (= 1 2) (+ 1 2) (+ 1 3)) in the main window.

  1. Press the Return key, or equivalently select the Eval button. This evaluates the expression to 4, just like DrScheme.
  2. Put the cursor back on that expression by clicking in its box. This time select the Step button. Donkey highlights the first subexpression to evaluate, and up in the Next Reduction Rule textbox it displays the applicable rule for that subexpression. Selecting the Step button again evaluates that subexpression and goes on to the next subexpression to evaluate. Eventually, you evaluate the whole expression.

    When stepping, you also have other options, e.g., selecting the Unstep button goes backwards one step in the evaluation.

  3. Put the cursor back on the expression again. This time select the Step All button. This completely evaluates the expression, like the Eval button, but it builds up the extra information so that you can now Unstep, and then Step/Unstep like we just saw.

One main option you'll want in Donkey are to Load files (in the File menu). We assume you'll usually use DrScheme for writing your programs. Select Help from the Help menu to explain other options.

Try stepping through some examples. In particular, try a simple use of recursion:

(define length
   (lambda (l)
       (cond
           ((null? l) 0)
           (else      (+ 1 (length (cdr l)))))))
(length (cons 1 (cons 4 (cons 8 (cons 2)))))

Since stepping through larger programs can be very tedious, you can indicate what kinds of subexpressions are "important" to show during stepping. In the Stop-at menu, currently All is selected, i.e., stepping stops at all subexpressions. If you select "if/cond/case", stepping will only stop and conditionals, but not at function applications. When stepping through recursive functions, you sometimes want to select only "apply" in the Stop-at menu, i.e., only indicate when it's applying a user-defined function and skip over the conditionals and primitive functions. Try the same example again and observe the difference.


Scheme style

Like any language, there are conventions for writing Scheme that help make it more readable. In this and the previous lab, we've discussed some conventions on providing supplementary information in comments. In class, we briefly discussed conventions for choosing between cond and if. Here, we will discuss layout and indenting conventions. Also of note, programmers vary widely in naming conventions, e.g., whether to name a list of numbers as l, lon, AListOfNumbers, nums, or something else.

The basic goals of spacing and indentation in Scheme include

DrScheme will help you with the first two issues: selecting the Check Syntax button will highlight keywords, and DrScheme automatically aligns a line nicely when you use the Return key. The following are examples of good style.