Comp 210 Lab 2: Design Recipe

Index: Design Recipe, Donkey, Law of Scheme Scheme style

Design Recipe

In class we started to write some simple functions using a "design recipe". Our examples here will be temperature conversion. This recipe says

Write the contract, and place it in the code using comments. The contract describes the meaning of the function's inputs and output. Be sure to pick a mnemonic name for the function.

     ;; k2c converts degrees kelvin to the equivalent degrees celsius
     ;; k2c : number -> number

     ;; c2f converts degrees celsius to the equivalent degrees fahrenheit
     ;; c2f : number -> number

     ;; k2f converts degrees kelvin to the equivalent degrees fahrenheit
     ;; k2f : number -> number

Make some examples of what the function should do. Picking a sufficient number of good examples is an important skill to learn. Your examples should test any conditionals or special cases of your function.

Expression	Value
`(k2c 0)`	`-273`
`(k2c 1000)`	`727`
`(c2f -40`	`-40`
`(c2f 0)`	`32`
`(c2f 100)`	`212`
`(k2f 273)`	`32`
`(k2f 373)`	`212`

Write the function header. Pick mnemonic names for the function parameter(s).

     (define k2c (lambda (k) ...))
     (define c2f (lambda (c) ...))
     (define k2f (lambda (k) ...))

Write the function body. We'll have lots more to say about this for more complicated functions and data. Be sure to reuse code when applicable!
```
     (define k2c (lambda (k) (- k 273)))
     (define c2f (lambda (c) (+ (* 9/5 c) 32)))
     (define k2f (lambda (k) (c2f (k2c k))))
     
```
If your function is complicated, simplify it using helper functions! Be sure to follow the design recipe for each helper function as well.
Test your function. Verify that it works for your examples. Include these tests in comments after the function.

For the curious...

Does the order of defining these functions matter? Try different orders and find out.

Advanced

The above contracts aren't as specific as desired. Should the functions convert meaningless temperatures, i.e., those less than absolute zero (i.e., zero degrees kelvin)?

Change the above so that the functions don't convert such temperates.

Specify the behavior in the contracts.
Make examples of this intended behavior.
The headers shouldn't change.
Change the function body.
Test your changes.

Donkey

Like DrScheme, Donkey is a programming environment for Scheme. While DrScheme is generally better, Donkey has one important feature that DrScheme currently 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.

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

Press the Return key, or equivalently select the Eval button. This evaluates the expression to 4, just like DrScheme.
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. In the Next Reduction Rule textbox it displays the applicable rule for that subexpression. See the Law of Scheme for a description of these rules. 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.
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, including those using functions like the above temperate conversions.

In the above example, when are the pieces of an if evaluated? What about the pieces in a cond?
Try calling a user-defined function (e.g., k2c). When is the body of the lambda evaluated?

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 at 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 examples again and observe the difference.

Law of Scheme

Donkey follows a set of rules, the Law of Scheme, that define how Scheme programs behave. For each kind of expression, these rules describe how to obtain a value. Some of these have been informally described in class, but we list them. (We'll see more rules later.)

Kind of expression	Examples	How to evaluate
Value	`1`, `#t`, `(lambda (n) (* 2 n))`	You have the value already.
Placeholder	`pi`, `+`	Get its `define`d value.
Function application	`(+ (* 9 4) pi)`, `(k2c 200)`	Evaluate the subexpressions (exp₀ exp₁ ... exp_n) to get values (val₀ val₁ ... val_n). If val₀ is primitive, e.g., `+`, do the appropriate built-in computation, resulting in the desired value. If val₀ is user-defined (i.e., a `lambda`), rewrite the `lambda`'s body, replacing the definition parameters with the values. Evaluate the rewritten body.
Special form	`(define classname 'comp210)`, `(if this that theother)`	If this is a `define` expression, evaluate the expression in the third position. Remember that the placeholder in the second position has this value. If this is a `if` expression, ... ...

define is one of several "special forms" that we've seen so far. They are "special" because they aren't like function application, which is considered the normal way to evaluate multi-part expressions.

How do we determine whether a multi-part expression is a function application or a special form? Well, each special form starts with a keyword, e.g., define, so if there's no keyword, it must be a function application.

Aside from some additional special forms, this is all there is to understand about Scheme. The absolute bulletproof definition of Scheme, defining all primitive functions, is about 60 pages long. Compare that to a standard C, C++, or Java reference book!

Now go back to Donkey and pay attention to the rules it displays as you try some examples.

Advanced

What are the rules for other special forms, such as if, and, or, and cond? Why are they special, i.e., how and why are they different from function application?

Advanced

Note that for a function application we evaluate exp₀ too! That means we can have complicated expressions in the function position (although that's disallowed in DrScheme's beginner level). That is going to be part of the key to Scheme's power.

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. What is most important is that you pick a single convention and be very consistent.

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.

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

```
     (define afunction
        (lambda (x)
           body))
     
```
The define and lambda keywords are each on separate lines to point out that you are doing two separate things:
1. making a definition and
2. creating a function with one argument.
(For very simple functions like c2f, this isn't necessary.)
```
     (if (= 3 x)
         (f 5)
         (+ 7 y))
     
```
The "then" and "else" branches are on separate lines and aligned so that you can easily see them. The same idea holds for larger conditionals:
```
     (cond
        [(empty? l) 0]
        [else       (+ 1 (foo (rest l)))])
     
```
Note the use of square brackets in cond. (Also note that I like to also align the result expressions in a cond, assuming the test expressions are reasonably short; but this is not a common style.)

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
        [(empty? l)
         0]
        [else
         (+ 1 (foo (rest l)))])

or in function calls,

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

Note that using too many lines obscures structure:
```
     (define
        afunction
        (lambda
           (l)
           (cond
              [(empty? l)
               0]
              [else
               (+ 1
                  (afunction
                     (rest l)))])))
     
```
It also makes you scroll vertically more. Unfortunately, sometimes you are forced into this if you want to be able to print your code on fixed-width paper and you have really big complicated functions. Within DrScheme your code can be arbitrarily wide.