Comp 210 Lab 3: Donkey, Style

Index: Donkey, How to print homeworks, Scheme style, Scheme Syntax

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

• enter donkey in an xterm window, or
• select Donkey from the Comp 210 menu.

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.

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.

The other 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 (list 1 4 8 2))

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.

Students have asked how best to print their homeworks, including testing, for grading. We suggest the following:

• Your homework will generally consist of several separate problems or groups of problems. Each separate group should be placed in a separate file.
• Place any data definitions and program templates in comments at the top of the appropriate file.
• When testing a program that is in the definition window of DrScheme, you will be using the interaction window of DrScheme. Copy your tests and their results and paste them into the bottom of the definition window. Comment out these tests and results (e.g., highlight the text and select Comment Out under the Scheme menu).
• Save and print the file with the extra information in comments.

Like any language, there are conventions for writing Scheme that help make it more readable. In this lab and the previous one, 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

• making keywords stand out,
• aligning related subexpressions, and
• keeping blocks of code reasonably-sized -- not too horizontal or too vertical.

(define afunction
   (lambda (x)
      body))

(if (= 3 x)
    (f 5)
    (+ 7 y))

(cond
   ((null? l) 0)
   (else      (+ 1 (foo (cdr l)))))

When subexpressions are long, or so deeply nested that you're regularly using 60+ columns of characters, you may have to break lines more frequently, e.g.,

(cond
   ((null? l)
    0)
   (else
    (+ 1 (foo (cdr l)))))

(myfunction (+ 3 (* 5 x) y)
            (- 3 (f 9 z)))

Note that using too many lines obscures structure:

(define
   afunction
   (lambda
      (l)
      (cond
         ((null? l)
          0)
         (else
          (+ 1
             (afunction
                (cdr l)))))))

Let's go over Scheme's syntax again, with emphasis on the common problem of "where do parentheses go?".

Expressions can be constants, e.g.,

• numbers: 1, 1.3, ...
• booleans: #t, #f
• symbols: 'foo, ...
• lists: null (We haven't shown you how to write other lists as constants.)

Expressions can be function applications:

• (expr expr1 expr2 ... exprn), where each piece is itself an expression, and expr needs to evaluate to a function, e.g., + or something with defined with a lambda.

Expressions can be special forms. Special forms are not function applications. In many languages, most expressions are special forms and thus are not "special". In Scheme, these are considered the exceptions to the general case of the function call. So far we've seen the following:

• definitions: (define name expr), where expr is an expression whose value is associated with name. (Definitions should only be at the "top-level", i.e., not as part of another expression.)
• functions: (lambda (name1 ... namen) expr) that creates a function of n arguments, that evaluates expr when called
• conditionals:
  • (if expr expr1 expr2), where expr should evaluate to a boolean
  • (cond (expr1a expr1b) ... (exprna exprnb)), where the first expression of each pair should evaluate to a boolean, and exprna may be the special keyword else.
  • (or expr1 ... exprn) and (and expr1 ... exprn) -- You may have thought or and and were primitive functions, but they aren't because they don't necessarily evaluate all of their subexpressions.

Looking at the above, parentheses can mean one of three things (given this subset of Scheme):

• call the function indicated after the left-paren -- a function application expression
• this is a special form -- one of the special forms, as indicated by a keyword define, lambda, ...
• this is part of a special form -- e.g., the grouping of parameter names in a lambda, or the pairing of expressions in a cond