In this course, we teach an approach to program design based on design recipes. These recipes were originally based on those found in How To Design Programs, 2nd Edition, but have been expanded in this course. Each recipe is applicable to certain problems, and following the recipes systematizes the process of designing solutions to those problems.

The three core recipes are used most frequently. The templating recipes are used for the template phase of every data definition and function. Abstraction recipes are used to reduce redundancy in code.

There is also a checklist to help you remember the recipe steps.

How To Design Functions (HtDF)

The How to Design Functions (HtDF) recipe is a design method that enables systematic design of functions. We will use this recipe throughout the term, although we will enhance it as we go to solve more complex problems.

Signature, purpose and stub.

The entire function design starts with an @htdf tag. This indicates the name of the function, and the fact that what follows the tag is a function design based on the HtDF recipe.

Write the function signature, a one-line purpose statement and a function stub.

A signature has the type of each argument, separated by spaces, followed by ->, followed by the type of result. So a function that consumes an image and produces a number would have the signature Image -> Number. The signature is written as metadata using the @signature tag.

Note that the stub is a syntactically complete function definition that produces a value of the right type. If the type is Number it is common to use 0, if the type is String it is common to use a "" and so on. The value will not, in general, match the purpose statement. In the example below the stub produces 0, which is a Number, but only matches the purpose when double happens to be called with 0.

(@htdf double)
(@signature Number -> Number)
;; produces n times 2

(define (double n)  0)  ; this is the stub

The purpose of the stub is to serve as a kind of scaffolding to make it possible to run the examples even before the function design is complete. With the stub in place check-expects that call the function can run. Most of them will fail of course, but the fact that they can run at all allows you to ensure that they are at least well-formed: parentheses are balanced, function calls have the proper number of arguments, function and constant names are correct and so on. This is very important, the sooner you find a mistake -- even a simple one -- the easier it is to fix.

Define examples, wrap each one in check-expect.

Write at least one example of a call to the function and the expected result the call should produce.

You will often need more examples, to help you better understand the function or to properly test the function. (If once your function works and you run the program some of the code is highlighted in black it means you definitely do not have enough examples.) If you are unsure how to start writing examples use the combination of the function signature and the data definition(s) to help you generate examples. The example data constants from the data definition may be useful, but it does not necessarily cover all the important cases for a particular function.

The first role of an example is to help you understand what the function is supposed to do. If there are boundary conditions be sure to include an example of them. If there are different behaviours the function should have, include an example of each. Since they are examples first, you could write them in this form:

;; (double 0) should produce 0
;; (double 1) should produce 2
;; (double 2) should produce 4

When you write examples it is sometimes helpful to write not just the expected result, but also to elaborate how it is computed. For example, you might write the following instead of the above:

;; (double 0) should produce (* 0 2)
;; (double 1) should produce (* 1 2)
;; (double 2) should produce (* 2 2)

While the above form satisfies our need for examples, BSL gives us a better way to write them, by enclosing them in check-expect. This will allow BSL to check them automatically when the function is complete. (In technical terms it will turn the examples into unit tests.)

(@htdf double)
(@signature Number -> Number)
;; produces n times 2
(check-expect (double 0) (* 0 2))
(check-expect (double 1) (* 1 2))
(check-expect (double 3) (* 3 2))

(define (double n)  0)  ; this is the stub

The existence of the stub will allow you to run the tests. Most (or even all) of the tests will fail since the stub is returning the same value every time. But you will at least be able to check that the parentheses are balanced, that you have not misspelled function names etc.

Template and inventory

The template is the basic structure of the function. Before writing the actual template we write a @template-origin tag that tells us what strategy we plan to use to come up with the template - the basic function structure. In module 1 the template is simple, but as the course goes on they become more and more complex.

In modules 2 - 6, once the How to Design Data Definitions (HtDD) recipe in introduced, templates are produced by following the rules in the Data Driven Templates recipe. You should write a @template-origin tag giving the origin of the template, copy the template from the data definition to the function design, and rename it. Then make another copy, wrap the first one in a @template tag, and then set to work on the second one - once completed this will be your final function definition. Note that the template is copied from the data definition for the consumed type, not the produced type. Beyond module 6 templates are often produced by blending two or more basic templates.

For primitive data like numbers, strings and images the body of the template is simply (... x) where x is the name of the parameter to the function.

Once the template is done the stub should be commented out.

(@htdf double)
(@signature Number -> Number)
;; produces n times 2
(check-expect (double 0) (* 0 2))
(check-expect (double 1) (* 1 2))
(check-expect (double 3) (* 3 2))

;(define (double n) 0) ;this is the stub

(@template-origin Number)

(@template   
 (define (double n)    ;this a copy of the template for reference
  (... n)))
  
(define (double n)     ;this is the start of the final function definition
  (... n))

It can also be useful to add constant values which are extremely likely to be useful to the template body at this point. For example, the template for a function that renders the state of a world program might have an MTS constant added to its body. This causes the template to include an inventory of useful constants.

Code the function body

Now complete the function body by filling in the definition.

Note that:

• the signature tells you the type of the parameter(s) and the type of the data the function body must produce
• the purpose describes what the function body must produce in English
• the examples provide several concrete examples of what the function body must produce
• the template tells you the basic function structure - the raw material you have to work with

You should use all of the above to help you code the function body. In some cases further rewriting of examples might make it more clear how you computed certain values, and that may make it easier to code the function.

(@htdf double)
(@signature Number -> Number)
;; produces n times 2
(check-expect (double 0) (* 0 2))
(check-expect (double 1) (* 1 2))
(check-expect (double 3) (* 3 2))

;(define (double n) 0) ; this is the stub

(@template-origin Number)

(@template   
 (define (double n)    ;this a copy of the template for reference
  (... n)))

(define (double n)
  (* n 2))

Test and debug until correct

Run the program and make sure all the tests pass, if not debug until they do. Many of the problems you might have had will already have been fixed because of following the "run early, run often" approach. But if not, debug until everything works.

How To Design Data (HTDD)

Data definitions are a driving element in the design recipes.

A data definition establishes the represent/interpret relationship between information and data:

• Information in the program's domain is represented by data in the program.
• Data in the program can be interpreted as information in the program's domain.

A data definition must describe how to form (or make) data that satisfies the data definition and also how to tell whether a data value satisfies the data definition. It must also describe how to represent information in the program's domain as data and interpret a data value as information.

So, for example, one data definition might say that numbers are used to represent the Speed of a ball. Another data definition might say that numbers are used to represent the Height of an airplane. So given a number like 6, we need a data definition to tell us how to interpret it: is it a Speed, or a Height or something else entirely. Without a data definition, the 6 is just data – it could mean anything.

What is the Inherent Structure of the Information?

One of the most important points in the course is that:

• the structure of the information in the program's domain determines the kind of data definition used,
• which in turn determines the structure of the data-driven templates and helps determine the function examples (check-expects),
• and therefore the structure of much of the final program design.

The remainder of this page lists in detail different kinds of data definition that are used to represent information with different structures. The page also shows in detail how to design a data definition of each kind. This summary table provides a quick reference to which kind of data definition to use for different information structures.

Simple Atomic Data

Use simple atomic data when the information to be represented is itself atomic in form, such as the elapsed time since the start of the animation, the x coordinate of a car or the name of a cat.

(@htdd Time)
;; Time is Natural
;; interp. number of clock ticks since start of game

(define START-TIME 0)
(define OLD-TIME 1000)

(@dd-template-rules atomic-non-distinct) ;Natural

(define (fn-for-time t)
  (... t))

Forming the Template

As noted below the template, it is formed according to the Data Driven Templates recipe using the right hand column of the atomic non-distinct rule.

Guidance on Data Examples and Function Example/Tests

One or two data examples are usually sufficient for simple atomic data.

When creating example/tests for a specific function operating on simple atomic data at least two test cases will be required. Additional tests are required if there are multiple cases involved. If the function produces Boolean there needs to be at least a true and false test case. Also be on the lookout for cases where a number of some form is an interval in disguise, for example given a type comment like Countdown is Natural, in some functions 0 is likely to be a special case.

Intervals

A special case of the number types (Number, Integer, and Natural) arises when the information to be represented is numbers within a certain range. In an interval data definition describe the bounds of the interval as part of the interpretation. For example, integers in the range [0, 10]. In specifying the bounds use the notation that [ and ] mean that the end of the interval includes the end point; ( and ) mean that the end of the interval does not include the end point. So [0, 10] is 0 to 10 inclusive; [0, 10) 0 inclusive to 10 exclusive.

(@htdd Countdown)
;; Countdown is Integer
;; interp. the number of seconds remaining to liftoff, restricted to [0, 10]
(define C1 10)  ; start
(define C2 5)   ; middle
(define C3 0)   ; end

(@dd-template-rules atomic-non-distinct) ;Integer

(define (fn-for-countdown cd)
  (... cd))

Forming the Template

As noted below the template, it is formed according to the Data Driven Templates recipe using the right hand column of the atomic non-distinct rule.

Guidance on Data Examples and Function Example/Tests

For data examples provide sufficient examples to illustrate how the type represents information. The three data examples above are probably more than is needed in this case.

When writing tests for functions operating on intervals be sure to test closed boundaries as well as points off the boundary such as midpoints. As always, be sure to include enough tests to check all other points of variance in behaviour across the interval.

Enumerations

Use an enumeration when the information to be represented consists of a fixed number of distinct items, such as colors, letter grades, provinces etc. The data used to represent an enumeration could in principle be anything - strings, integers, images even. Some languages provide an explicit mechanism rather than allowing arbitrary data selection - we mirror that by always using strings for enumerations. In the case of enumerations it is sometimes redundant to provide an interpretation and nearly always redundant to provide examples.

(@htdd LightState)
;; LightState is one of:
;;  - "red"
;;  - "yellow"
;;  - "green"
;; interp. the color of a traffic light

;; <examples are redundant for enumerations>
 
(@dd-template-rules one-of           ;3 cases
                    atomic-distinct  ;"red"
                    atomic-distinct  ;"yellow"
                    atomic-distinct) ;"green"

(define (fn-for-light-state ls)
  (cond [(string=? ls "red") (...)]
        [(string=? ls "yellow") (...)]
        [(string=? ls "green") (...)]))

Forming the Template

As noted in the @dd-template-rules tag the template is formed according to the Data Driven Templates recipe as follows:

First, LightState is an enumeration with 3 cases, so the one of rule says to use a cond with 3 cases:

(@dd-template-rules one-of           ;3 cases
                    )
(define (fn-for-light-state ls)
  (cond [Q1 A1]
        [Q2 A2]
        [Q3 A3])) 

In the first subclass of the type comment, "red" is a distinct atomic value, so the cond question column of the atomic distinct rule says Q1 should be (string=? ls "red"). The cond answer column says A1 should be (...). So we have:

(@dd-template-rules one-of           ;3 cases
                    atomic-distinct  ;"red"
                    )
(define (fn-for-light-state ls)
  (cond [(string=? ls "red") (...)]
        [Q2 A2]
        [Q3 A3])) 

Then "yellow" and "green" are also distinct atomic values, so the final tag and template are:

(@dd-template-rules one-of           ;3 cases
                    atomic-distinct  ;"red"
                    atomic-distinct  ;"yellow"
                    atomic-distinct) ;"green"

(define (fn-for-light-state ls) 
  (cond [(string=? ls "red") (...)]
        [(string=? ls "yellow") (...)]
        [(string=? ls "green") (...)]))

Do not use else as the last question in an enumeration unless you are using the large enumeration rule.

Note that the order of question/answer pairs in the cond must match the order of subclasses in the type comment. In addition, in any function where the template is used, the cond question/answer pairs must not be re-ordered and the cond questions must not be edited in any way. Except when using the large enumeration rule all cond question/answer pairs must be preserved.

Guidance on Data Examples and Function Example/Tests

Data examples are redundant for enumerations.

Functions operating on enumerations should have (at least) as many tests as there are cases in the enumeration.

Large Enumerations

Some enumerations contain a large number of elements. A canonical example is KeyEvent, which is provided as part of big-bang. KeyEvent includes all the letters of the alphabet as well as other keys you can press on the keyboard. It is not necessary to write out all the cases for such a data definition. Instead write one or two, as well as a comment saying what the others are, where they are defined etc.

Defer writing templates for such large enumerations until a template is needed for a specific function. At that point include the specific cases that particular function cares about. Be sure to include an else clause in the template to handle the other cases. As an example, some functions operating on KeyEvent may only care about the space key and ignore all other keys, the following would be an appropriate template for such functions.

(@template-origin KeyEvent)

(@template
 (define (fn-for-key-event kevt)
   (cond [(key=? " " kevt) (...)]
         [else
          (...)])))

The same is true of writing tests for functions operating on large enumerations. All the specially handled cases must be tested, in addition one more test is required to check the else clause.

Itemizations

An itemization describes data comprised of 2 or more subclasses, at least one of which is not a distinct item. (C.f. enumerations, where the subclasses are all distinct items.) In an itemization the template is similar to that for enumerations: a cond with one clause per subclass. In cases where the subclass of data has its own data definition the answer part of the cond clause includes a call to a helper template, in other cases it just includes the parameter.

(@htdd Bird)
;; Bird is one of:
;;  - false
;;  - Number
;; interp. false means no bird, number is x position of bird

(define B1 false)
(define B2 3) 

(@dd-template-rules one-of                ;2 cases
                    atomic-distinct       ;false
                    atomic-non-distinct)  ;Number


(define (fn-for-bird b)
  (cond [(false? b) (...)]
        [else (... b)]))

Forming the Template

As noted below the template, it is formed according to the Data Driven Templates recipe using the one-of rule, the atomic distinct rule and the atomic non-distinct rule in order.

Note that the order of question/answer pairs in the cond must match the order of subclasses in the type comment. In addition, in any function where the template is used, the cond question/answer pairs must not be re-ordered and the cond questions must not be edited in any way. Except when using the large enumeration rule all cond question/answer pairs must be preserved.

Guidance on Data Examples and Function Example/Tests

As always, itemizations should have enough data examples to clearly illustrate how the type represents information.

Functions operating on itemizations should have at least as many tests as there are cases in the itemizations. If there are intervals in the itemization, then there should be tests at all points of variance in the interval. In the case of adjoining intervals it is critical to test the boundaries.

The course no longer includes itemizations of intervals.

Compound data

Use compound when two or more values naturally belong together. The define-struct goes immediately after the @htdd tag, and before the type comment.

(@htdd Ball)
(define-struct ball (x y))
;; Ball is (make-ball Number Number)
;; interp. a ball at position x, y 

(define BALL-1 (make-ball 6 10))

(@dd-template-rules compound)  ;2 fields

(define (fn-for-ball b)
  (... (ball-x b)     ;Number
       (ball-y b)))   ;Number

The template above is formed according to the Data Driven Templates recipe using the compound rule. Then for each of the selectors, the result type of the selector (Number in the case of ball-x and ball-y) is used to decide whether the selector call itself should be wrapped in a call to another template function expression. In this case, where the result types are primitive, no additional wrapping occurs. C.f. cases below when the reference rule applies.

Guidance on Data Examples and Function Example/Tests

For compound data definitions it is often useful to have numerous examples, for example to illustrate special cases. For a snake in a snake game you might have an example where the snake is very short, very long, hitting the edge of a box, etc. These data examples can also be useful for writing function tests because they save space in each check-expect.

References to other data definitions

Some data definitions contain references to other data definitions you have defined (non-primitive data definitions). One common case is for a compound data definition to comprise other named data definitions. (Or, once lists are introduced, for a list to contain elements that are described by another data definition. In these cases the template of the first data definition should contain calls to the second data definition's template function wherever the second data appears. For example:

---assume Ball is as defined above---
(@htdd Game)
(define-struct game (ball score))
;; Game is (make-game Ball Number) 
;; interp. the current state of a game, with the ball and score

(define GAME-1 (make-game (make-ball 1 5) 2))

(@dd-template-rules compound       ;2 fields
                    ref)           ;(game-ball g) is Ball

(define (fn-for-game g)
  (... (fn-for-ball (game-ball g))
       (game-score g)))            ;Number

In this case the template is formed according to the Data Driven Templates recipe by first using the compound rule. Then, since the result type of (game-ball g) is Ball, the reference rule is used to wrap the selector so that it becomes (fn-for-ball (game-ball g)). The call to game-score is not wrapped because it produces a primitive type.

Guidance on Data Examples and Function Example/Tests

For data definitions involving references to non-primitive types the data examples can sometimes become quite long. In these cases it can be helpful to define well-named constants for data examples for the referred to type and then use those constants in the referring from type. For example:

...in the data definition for Drop...
(define DTOP (make-drop 10 0))            ;top of screen
(define DMID (make-drop 20 (/ HEIGHT 2))) ;middle of screen
(define DBOT (make-drop 30 HEIGHT))       ;at bottom edge
(define DOUT (make-drop 40 (+ HEIGHT 1))) ;past bottom edge

...in the data definition for ListOfDrop...
(define LOD1 empty)
(define LOD-ALL-ON             (cons DTOP (cons DMID )))
(define LOD-ONE-ABOUT-TO-LEAVE (cons DTOP (cons DMID (cons DBOT empty))))
(define LOD-ONE-OUT-ALREADY    (cons DTOP (cons DMID (cons DBOT (cons DOUT empty)))))

In the case of references to non-primitive types the function operating on the referring type (i.e. ListOfDrop) will end up with a call to a helper that operates on the referred to type (i.e. Drop). Tests on the helper function should fully test that function, tests on the calling function may assume the helper function works properly.

Self-referential or mutually referential

When the information in the program's domain is of arbitrary size, a well-formed self-referential (or mutually referential) data definition is needed.

In order to be well-formed, a self-referential data definition must:

• (i) have at least one case without self reference (the base case(s))
• (ii) have at least one case with self reference

The template contains a base case corresponding to the non-self-referential clause(s) as well as one or more natural recursions corresponding to each of the self-referential clauses.

(@htdd ListOfString)
;; ListOfString is one of:
;;  - empty
;;  - (cons String ListOfString)
;; interp. a list of strings

(define LOS-1 empty)
(define LOS-2 (cons "a" empty))
(define LOS-3 (cons "b" (cons "c" empty)))

(@dd-template-rules one-of            ;2 cases
                    atomic-distinct   ;empty
                    compound          ;(cons String ListOfString)
                    self-ref)         ;(rest los) is ListOfString

(define (fn-for-los los)
  (cond [(empty? los) (...)]                   ;BASE CASE
        [else (... (first los)                 ;String
                   (fn-for-los (rest los)))])) ;NATURAL RECURSION
;;             /
;;            /
;;       COMBINATION

In some cases a type comment can have both self-reference and reference to another type.

(@htdd Dot)
(define-struct dot (x y))
;; Dot is (make-dot Integer Integer)
;; interp. A dot on the screen, w/ x and y coordinates in pixels.
(define D1 (make-dot 10 30))

(@dd-template-rules compound)  ;2 fields

(define (fn-for-dot d)
  (... (dot-x d)   ;Integer
       (dot-y d))) ;Integer

(@htdd ListOfDot)
;; ListOfDot is one of:
;;  - empty
;;  - (cons Dot ListOfDot)
;; interp. a list of Dot
(define LOD1 empty)
(define LOD2 (cons (make-dot 10 20) (cons (make-dot 3 6) empty)))

(@dd-template-rules one-of               ;2 cases
                    atomic-distinct      ;empty
                    compound             ;(cons Dot ListOfDot)
                    ref                  ;(first lod) is Dot 
                    self-ref)            ;(rest lod) is ListOfDot

(define (fn-for-lod lod)
  (cond [(empty? lod) (...)]
        [else
         (... (fn-for-dot (first lod))
              (fn-for-lod (rest lod)))]))

Guidance on Data Examples and Function Example/Tests

When writing data and function examples for self-referential data definitions always put the base case first. It's usually trivial for data examples, but many function tests don't work properly if the base case isn't working properly, so testing that first can help avoid being confused by a failure in a non base case test. Also be sure to have a test for a list (or other structure) that is at least 2 long. If the function has conditional behaviour be sure that all branches of the behaviour are tested at an element that is not the last in the list.

How To Design Worlds (HtDW)

The How to Design Worlds process provides guidance for designing interactive world programs using big-bang. While some elements of the process are tailored to big-bang, the process can also be adapted to the design of other interactive programs. The wish-list technique can be used in any multi-function program.

Phase 1: Domain Analysis

Do a domain analysis by hand-drawing three or more pictures of what the world program will look like at different stages when it is running.

Use this picture to identify constant information such as the height and width of screen, color of the background, the background image itself, the length of a firework's fuse, the image for a moving cat and so on.

Also identify changing information such as the position of a firework, the color of a light, the number in countdown etc.

Identify which big-bang options the program needs.

(There are several more options to big-bang. Look in the DrRacket help desk under big-bang for a complete list.)

Phase 2: Building the actual program

Structure the actual program in four parts:

1. Requires followed by one line summary of program's behavior
2. Constants
3. Data definitions
4. Functions

The program should begin with whatever require declarations are required. For a program using big-bang this is usually a require for 2htdp/universe to get big-bang itself and a require for 2htdp/image to get useful image primitives. This is followed by a short summary of the program's behavior (ideally 1 line).

The next section of the file should define constants. These will typically come directly from the domain analysis.

This is followed by data definitions. The data definitions describe how the world state - the changing information identified during the analysis - will be represented as data in the program. Simple world programs may have just a single data definition. More complex world programs have a number of data definitions.

The functions section should begin with the main function which uses big-bang with the appropriate options identified during the analysis. After that put the more important functions first followed by the less important helpers. Keep groups of closely related functions together.

Template for a World Program

A useful template for a world program, including a template for the main function and wish list entries for tick-handler and to-draw handler is as follows. To use this template replace WS with the appropriate type for your changing world state. You may want to give the handler functions more descriptive names and you should definitely give them all a more descriptive purpose.

(require spd/tags)
(require 2htdp/image)
(require 2htdp/universe)

;; My world program  (make this more specific)

(@htdw WS) ;(give WS a better name)

;; =================
;; Constants:


;; =================
;; Data definitions:

(@htdd WS)
;; WS is ... 



;; =================
;; Functions:

(@htdf main)
(@signature WS -> WS)
;; start the world with ...
;; 

(@template-origin htdw-main)

(define (main ws)
  (big-bang ws           ; WS
    (on-tick   tock)     ; WS -> WS
    (to-draw   render)   ; WS -> Image
    (on-mouse  ...)      ; WS Integer Integer MouseEvent -> WS
    (on-key    ...)))    ; WS KeyEvent -> WS


(@htdf tock)
(@signature WS -> WS)
;; produce the next ...
;; !!!
(define (tock ws) ws)

(@htdf render)
(@signature WS -> Image)
;; render ... 
;; !!!
(define (render ws) empty-image)

Depending on which other big-bang options you are using you would also end up with wish list entries for those handlers. So, at an early stage a world program might look like this:

(require 2htdp/universe)
(require 2htdp/image)

;; A cat that walks across the screen.

(@htdw Cat)

;; Constants:

(define WIDTH  200)
(define HEIGHT 200)

(define CAT-IMG (circle 10 "solid" "red")) ; a not very attractive cat

(define MTS (empty-scene WIDTH HEIGHT))


;; Data definitions:

(@htdd Cat)
;; Cat is Number
;; interp. x coordinate of cat (in screen coordinates)
(define C1 1)
(define C2 30)

(@dd-template-rules atomic-non-distinct)
  
(define (fn-for-cat c)
  (... c))


;; Functions:

(@htdf main)
(@signature Cat -> Cat)
;; start the world with initial state c, for example: (main 0)

(@template-origin htdw-main)

(define (main c)
  (big-bang c                         ; Cat
            (on-tick   tock)          ; Cat -> Cat
            (to-draw   render)))      ; Cat -> Image

(@htdf tock)
(@signature Cat -> Cat)
;; Produce cat at next position
;!!!
(define (tock c) 1)  ;stub

(@htdf render)
(@signature Cat -> Image)
;; produce image with CAT-IMG placed on MTS at proper x, y position
; !!!
(define (render c) MTS)

Note that we are maintaining a wish listof functions that need to be designed. The way to maintain the wish list is to just write a signature, purpose and stub for each wished-for function, also label the wish list entrywith !!! or some other marker that is easy to search for. That will help you find your unfilled wishes later.

Forming wish list entries this way is enough for main (or other functions that call a wished for function) to be defined without error. But of course main (and other such functions) will not run properly until the wished for functions are actually completely designed.

As you design the program remember to run early and run often. The sooner you can run the program after writing anything the sooner you can find any small mistakes that might be in it. Fixing the small mistakes earlier makes it easier to find any harder mistakes later.

Key and Mouse Handlers

The on-key and on-mouse handler function templates are handled specially. The on-key function is templated according to its second argument, a KeyEvent, using the large enumeration rule. The on-mouse function is templated according to its MouseEvent argument, also using the large enumeration rule. So, for example, for a key handler function that has a special behaviour when the space key is pressed but does nothing for any other key event the following would be the template:

(@template-origin KeyEvent)

(@template   
 (define (handle-key ws ke)
   (cond [(key=? ke " ") (... ws)]
         [else 
          (... ws)])))

Similarly the template for a mouse handler function that has special behavior for mouse clicks but ignores all other mouse events would be:

(@template-origin MouseEvent)

(@template
 (define (handle-mouse ws x y me)
   (cond [(mouse=? me "button-down") (... ws x y)]
         [else
          (... ws x y)])))

For more information on the KeyEvent and MouseEvent large enumerations see the DrRacket help desk.

Data Driven Templates

Templates are the core structure that we know a function must have, independent of the details of its definition. In many cases the template for a function is determined by the type of data the function consumes. We refer to these as data driven templates. The recipe below can be used to produce a data driven template for any type comment.

For a given type TypeName the data driven template is:

(define (fn-for-type-name x)
  <body>)

Where x is an appropriately chosen parameter name (often the initials of the type name) and the body is determined according to the table below. To use the table, start with the type of the parameter, i.e. TypeName, and select the row of the table that matches that type. The first row matches only primitive types, the later rows match parts of type comments.

(Note that when designing functions that consume additional atomic parameters, the name of that parameter gets added right after every ... in the template. Templates for functions with additional complex parameters are covered in Functions on 2 One-Of Data.)

Producing the Template for an Example One Of Type

In many cases more than one of the above rules will apply to a single template. Consider this type comment:

;; Clock is one of:
;; - Natural
;; - false

and the step-by-step construction of the template for a function operating on Clock.

(@dd-template-rules one-of       ;2 cases
                    )

(define (fn-for-clock c)
  (cond [Q A]
        [Q A]))

(@dd-template-rules one-of               ;2 cases
                    atomic-non-distinct  ;Natural
                    )

(define (fn-for-clock c)
  (cond [(number? c) (... c)]
        [Q A]))

(@dd-template-rules one-of               ;2 cases
                    atomic-non-distinct  ;Natural
                    atomic-distinct)     ;false

(define (fn-for-clock c)
  (cond [(number? c) (... c)]
        [else
          (...)]))

Templates for Mutually Referential Types

The previous example doesn't cover the mutual-reference rule, which says that in the case of mutually-referential data definitions, when you template one function in the mutual-reference cycle you should immediately template all the functions in the mutual-reference cycle. So, for example, given:

(define-struct person (name subs))
;; Person is (make-person String ListOfPerson)

;; ListOfPerson is one of:
;;  - empty
;;  - (cons Person ListOfPerson)

Then if you need a template for a function operating on a Person (or a function operating on a ListOfPerson) you should immediately write a template for both functions, resulting in something like this:

(define (fn-for-person p)
  (... (person-name p)
       (fn-for-lop (person-subs p))))      ;mutual recursion from mutual-reference

(define (fn-for-lop lop)
  (cond [(empty? lop) ...]
        [else
         (... (fn-for-person (first lop))  ;mutual recursion from mutual-reference
              (fn-for-lop (rest lop)))]))  ;natural recursion from self-reference

(Note that producing that template will also involve using the atomic-distinct, atomic, one-of and compound rules.)

As with self-reference, its a good idea to draw a mutual-reference line on the data definition and ensure you have corresponding mutual recursion lines in your templates.

Testing

The principles above can also be used to understand how many tests a data definition implies. Simply put, the set of tests/examples should cover all cases, call all helper functions, involve all selectors, and avoid duplicated values.

Additional Design Rules for Helpers

During coding three additional guidelines suggest situations under which a helper function should be added:

1. Use a separate function for each difference between quantities in a problem.
2. If a subtask requires operating on arbitrary sized data a helper function must be used.
3. If a subtask involves special domain knowledge a helper function should be used.
4. In addition always keep the "one task per function" goal in mind. If part of a function you are designing seems to be a well-defined subtask put that into a helper function.

Functions On 2 One-Of Data

This page outlines the variations in the normal HtDF recipe when designing a function that consumes 2 data that have a one-of in their type comments. Examples of functions for which this applies include functions with the following signatures:

1. ListOfString ListOfString -> Boolean
2. ListOfString ListOfString -> ListOfString
3. ListOfString BinaryTree -> Boolean
4. ListOfNatural FamilyTree -> ListOfString

For the purpose of this explanation, assume that the goal is to design a function that consumes two ListOfString and produces true if the strings in the first list are equal to the corresponding strings in the second list. If that is true and the second list is longer than the first the function should produce true; if the second list is shorter it always produces false.

The first three steps of the recipe - signature, purpose and stub - are unchanged.

(@signature ListOfString ListOfString -> Boolean)
;; produce true if lsta is a prefix of lstb

(define (prefix=? lsta lstb) false)

But at this point the next step is to form a cross-product of type comments table as follows. The row labels of the table are the cases of the one-of type comment for one argument (perhaps the first), and the column labels are the cases of the one-of type comment for the other argument. 

;; CROSS PRODUCT OF TYPE COMMENTS TABLE
;;
;;                                     lstb
;;                           empty           (cons String LOS)                
;;                                         
;; l   empty                               
;; s
;; t   (cons String LOS)                   
;; a                                       

In this case, where both arguments have 2 cases in their one-of type comments, the cross-product formed has 4 cells (2 * 2 = 4). The next step of the process is to use the cross product table to help form at least as many tests as there are cells. The upper left cell describes a scenario where both lsta and lstb are empty. The lower left cell is where lsta is non-empty but lstb is empty and so on. The lower right cell is where both lists are non-empty, and this case requires more than one test. So we end up with: 

(check-expect (prefix=? empty empty) true)
(check-expect (prefix=? empty (list "a" "b")) true)
(check-expect (prefix=? (list "a") empty) false)

(check-expect (prefix=? (list "a") (list "b")) false)
(check-expect (prefix=? (list "a") (list "a")) true)
(check-expect (prefix=? (list "a" "b") (list "a" "x")) false)
(check-expect (prefix=? (list "a" "b") (list "a" "b")) true)

;; CROSS PRODUCT OF TYPE COMMENTS TABLE
;;
;;                                     lstb
;;                           empty           (cons String LOS)                
;;                                          
;; l   empty                   true           true
;; s                         
;; t   (cons String LOS)       false          (and (string=? (first lsta) (first lstb))
;; a                                               (prefix=? (rest lsta) (rest lstb)))

;; CROSS PRODUCT OF TYPE COMMENTS TABLE
;;
;;                                     lstb
;;                           empty           (cons String LOS)                
;;                                         
;; l   empty                           true
;; s                         
;; t   (cons String LOS)       false          (and (string=? (first lsta) (first lstb))
;; a                                               (prefix=? (rest lsta) (rest lstb)))

              (... (first lsta)
                   (first lstb)
                   (prefix=? (rest lsta) ...)
                   (prefix=? ... (rest lstb)))

(@template-origin 2-one-of)

;; no @template for 2-one-of    

(define (prefix=? lsta lstb)
  (cond [(empty? lsta) true]
        [(empty? lstb) false]
        [else
         (and (string=? (first lsta) (first lstb))
              (prefix=? (rest lsta)
                        (rest lstb)))]))

Function Composition

Use function composition when a function must perform two or more distinct and complete operations on the consumed data. For example:

• A function that must sort and layout a list of images. First it must sort the complete list and then lay it out. It cannot sort and layout each image one at a time.
• A function that must advance a list of raindrops and then remove the ones that have left the screen. First it must advance all the drops and then remove the ones that have advanced too far. (With difficulty this could be done in a single pass through the list of drops, but it is much more cumbersome to do that way.)

When using function composition the normal template for the function is discarded, and the body of the function has two or more function compositions. So in the case of arrange-images the function design would look like this:

(@signature ListOfImage -> Image)
;; arrange images left to right in increasing order of size
(check-expect (arrange-images (list I1 I3 I2))
              (beside I1 I2 I3 empty-image))

(@template-origin fn-composition)

(@template   
 (define (arrange-images loi)
   (layout-images (sort-images ...))))
  
(define (arrange-images loi)
  (layout-images (sort-images loi)))

Which we read as saying "first sort the images, and then layout the sorted list". At the point this is written wish list entries would be created for layout-images and sort-images unless those functions already existed.

Tests for a function that uses function composition should be selected to ensure that the function is calling all the appropriate functions and composing them properly. For example, assuming that images I1, I2 and I3 are in increasing order of size, then this test alone would not be adequate:

(check-expect (arrange-images (list I1 I2 I3))
              (beside I1 I2 I3 empty-image))

Because a faulty implementation of arrange-images that just calls layout-images would pass. Instead a test like the original one above is needed, to ensure that both sort-images and layout-images are called. But note that the tests for arrange-images do not themselves need to fully test both composed functions. They only need to test the composition. That is why arrange-images does not absolutely have to have a base case test. (Although it wouldn't hurt it to have one.)

Failure Handling

The template for failure handling comprises 3 elements:

  
(@template-origin X try-catch)

(@template 
 (define (fn-for-x x)
   (if (not (false? (fn-that-might-fail <args>))) ;does this function call fail?
       (fn-that-might-fail <args>)                ;if not, produce it
       <some alternative result>)))               ;if so, produce something else

(@template   
 (define (fn-for-x x)
   (local [(define try (fn-that-might-fail <args>))]
     (if (not (false? try))
         try
         <some alternative result>))))

(@template-origin X)

(@template 
 (define (fn-for-x x)
   (if (have-we-found-result? x)  ;success?
       (produce-result x)         ;produce correct value
       (fn-for-lox (x-subs x))))) ;search in the subs of this node

(@template-origin try-catch ListOfX)

(@template 
 (define (fn-for-lox lox)
   (cond [(empty? lox) false]
         [else
           (if (not (false? (fn-for-x (first lox))))  ;is first child successful?
               (fn-for-x (first lox))                 ;if so produce that
               (fn-for-lox (rest lox)))])))           ;or try rest of children

(@template-origin encapsulated X ListOfX try-catch)

(@template   
 (define (backtracking-fn x)
   (local [(define (fn-for-x x)
             (if (have-we-found-result? x)
                 (produce-result x)       
                 (fn-for-lox (x-subs x))))

           (define (fn-for-lox lox)
             (cond [(empty? lox) false]
                   [else
                    (local [(define try (fn-for-x (first lox)))]
                      (if (not (false? try))                    
                          try                                   
                          (fn-for-lox (rest lox))))]))]

     (fn-for-x x))))

(define (genrec-fn d)
  (cond [(trivial? d) (trivial-answer d)]
        [else
         (... d 
              (genrec-fn (next-problem d)))]))

(@signature (listof X) -> (listof X))
;; produce list formed by keeping the 1st, 3rd, 5th and so on elements of lox
(check-expect (skip1 (list "a" "b" "c" "d")) (list "a" "c"))
(check-expect (skip1 (list 0 1 2 3 4)) (list 0 2 4))

(define (skip1 lox) empty) ;stub

(@template-origin (listof X) accumulator)

(define (skip1 lox)
  (cond [(empty? lox) (...)]
        [else
         (... (first lox)
              (skip1 (rest lox)))]))

(@template (listof X) accumulator)

(define (skip1 lox0)
  (local [(define (skip1 lox)
            (cond [(empty? lox) (...)]
                  [else
                   (... (first lox)
                        (skip1 (rest lox)))]))]
    
    (skip1 lox0)))

(@template (listof X) accumulator)

(define (skip1 lox0)
  (local [(define (skip1 lox acc)
            (cond [(empty? lox) (... acc)]
                  [else
                   (... acc
                        (first lox)
                        (skip1 (rest lox)
                               (... acc (first lox))))]))]
    
    (skip1 lox0 ...)))

(skip1 (list 0 1 2 3 4) 1)       the 0 is the 1st element of lox0 (using 1 based indexing)
(skip1 (list   1 2 3 4) 2)       the 1 is the 2nd element
(skip1 (list     2 3 4) 3)       the 2 is the 3rd 
(skip1 (list       3 4) 4)       the 3 is the 4th
(skip1 (list         4) 5)       the 4 is the 5th
(skip1 (list          ) 6)

(@template-origin (listof X) accumulator)

(@template
 (define (skip2 lox0)
   ;; acc is ...; ...
   (local [(define (skip2 lox acc)
            (cond [(empty? lox) (... acc)]
                  [else
                   (... acc
                        (first lox)
                        (skip2 (rest lox)
                               (... acc (first lox))))]))]
    
    (skip2 lox0 ...))))

(define (skip2 lox0)
  ;; acc is Natural; how many elements of lox to keep before next skip
  ;; (skip2 (list 0 1 2 3 4) 1)
  ;; (skip2 (list   1 2 3 4) 0)
  ;; (skip2 (list     2 3 4) 1)
  ;; (skip2 (list       3 4) 0)
  ;; (skip2 (list         4) 1)
  ;; (skip2 (list          ) 
  (local [(define (skip2 lox acc)
            (cond [(empty? lox) (... acc)]
                  [else
                   (... acc
                        (first lox)
                        (skip2 (rest lox)
                               (... acc (first lox))))]))]
    
    (skip2 lox0 ...)))

(@template-origin (listof X) accumulator)

(@template
 (define (skip2 lox0)
   ;; acc is ...; ...
   (local [(define (skip2 lox acc)
            (cond [(empty? lox) (... acc)]
                  [else
                   (... acc
                        (first lox)
                        (skip2 (rest lox)
                               (... acc (first lox))))]))]
    
    (skip2 lox0 ...))))

(define (skip1 lox0)
  ;; acc is Natural; 1 based index of (first lox) in lox0
  ;; (skip1 (list 0 1 2 3 4) 1)    ;0 should be kept
  ;; (skip1 (list   1 2 3 4) 2)    ;1 should be skipped
  ;; (skip1 (list     2 3 4) 3)    ;0 should be kept
  ;; (skip1 (list       3 4) 4)    ;1 should be skipped
  ;; (skip1 (list         4) 5)    ;0 should be kept
  ;; (skip1 (list          ) 6)
  (local [(define (skip1 lox acc)
            (cond [(empty? lox) empty]
                  [else
                   (if (even? acc)
                       (skip1 (rest lox) (add1 acc))
                       (cons (first lox)
                             (skip1 (rest lox) (add1 acc))))]))]
    
    (skip1 lox0 1)))

(@signature Board -> Board or false)
;; produce a solution for bd; or false if bd is unsolvable
;; CONSTRAINT: bd is valid

(check-expect (solve BD4) BD4s)
(check-expect (solve BD5) BD5s)
(check-expect (solve BD7) false)







(define (solve bd) false) ;stub

(define (solve bd)
  (local [(define (solve--bd bd)
            (... (solve--lobd (bd-subs bd))))
          (define (solve--lobd lobd)
            (cond [(empty? lobd) (...)]
                  [else
                   (... (solve--bd (first lobd))
                        (solve--lobd (rest lobd)))]))]    

    (solve--bd bd)))

(define (genrec-fn d)
  (if (trivial? d)
      (trivial-answer d)
      (... d 
           (genrec-fn (next-problem d)))))

(define (solve bd)
  (local [(define (solve--bd bd)
            (if (solved? bd)
                bd
                (solve--lobd (next-boards bd))))

          (define (solve--lobd lobd)
            (cond [(empty? lobd) (...)]
                  [else
                   (... (solve--bd (first lobd))
                        (solve--lobd (rest lobd)))]))]    

    (solve--bd bd)))

(define (backtracking-fn x)
  (local [(define (fn-for-x x)
            (... (fn-for-lox (x-subs x))))          

          (define (fn-for-lox lox)
            (cond [(empty? lox) false]
                  [else
                   (local [(define try (fn-for-x (first lox)))] ;try first child
                     (if (not (false? try))                     ;successful?
                         try                                    ;if so produce that
                         (fn-for-lox (rest lox))))]))]          ;or try rest of children

    (fn-for-x x)))

(define (solve bd)
  (local [(define (solve--bd bd)
            (if (solved? bd)
                bd
                (solve--lobd (next-boards bd))))          

          (define (solve--lobd lobd)
            (cond [(empty? lobd) false]
                  [else
                   (local [(define try (solve--bd (first lobd)))]
                        (if (not (false? try))
                            try
                            (solve--lobd (rest lobd))))]))]    

    (solve--bd bd)))

(define (solve bd)
  (local [(define (solve--bd bd)
            (if (solved? bd)
                bd
                (solve--lobd (next-boards bd))))          

          (define (solve--lobd lobd)
            (cond [(empty? lobd) false]
                  [else
                   (local [(define try (solve--bd (first lobd)))]
                        (if (not (false? try))
                            try
                            (solve--lobd (rest lobd))))]))]    

    (solve--bd bd)))

;; ListOfX is one of:
;; - empty
;; - (cons X ListOfX)

(define (fn-for-lox lox)
  (cond [(empty? lox) (...)]
        [else
         (... (first lox)
              (fn-for-lox (rest lox)))]))

(define (fold fn b lox)
  (cond [(empty? lox) b]
        [else
         (fn (first lox)
             (fold fn b (rest lox)))]))

(check-expect (fold cons empty (list 1 2 3)) (list 1 2 3)) ;copy the list
(check-expect (local [(define (c1 x rnr) (add1 rnr))]      ;count elements of list
                (fold c1 0 (list 1 2 3)))
              3)
(check-expect (fold + 0 (list 1 2 3)) 6)                   ;add elements of list

(check-expect (fold string-append "" (list "a" "bc" "def"));a different kind of adding
              "abcdef")


(check-expect (local [(define (total-area i a)             ;even more different adding
                        (+ (* (image-width i)
                              (image-height i))
                           a))]
                (fold total-area 0 (list (rectangle 20 40 "solid" "red")
                                         (right-triangle 10 20 "solid" "red")
                                         (circle 20 "solid" "red"))))
              (+ (* 20 40) (* 10 20) (* 40 40)))

;; the abstract fold function for (listof X)

(X ??? -> ???) ??? (listof X) -> ???

Image Number -> Number

(X Y -> Y) Y (listof X) -> Y

(@htdf only-positive)
(@signature (listof Number) -> (listof Number))
;; produce only positive? elements of lon

;; tests elided

(@template-origin use-abstract-fn)

(@template 
 (define (only-positive lon)
   (filter ... lon)))

(define (only-positive lon)
          ;(Number -> Boolean)
  (filter ...                   lon))