On this page:
Discrepancies
Summary of Recipe Steps
1 Data Design
1.1 Data Definitions
1.2 Data Invariants
1.3 Interpretation
1.4 Data Examples
1.5 Templates
1.5.1 Template for Compound Data
1.5.2 Template for Itemization Data
1.5.3 Template for Mixed Data
1.5.4 Template For Recursive Data
1.5.5 Template Summary
1.6 Data Design Summary
2 Function Specification
2.1 Signature
2.2 Purpose Statement
2.3 Argument Invariants
2.4 Function Examples
2.5 Design Strategy
2.5.1 Function Composition
2.5.2 Data Decomposition
2.5.3 Generative Recursion
2.6 Function Specification Summary
3 Function Implementation
4 Testing
How to Test
Equivalence Partitioning
Errors Reveal More Test Partitions
5 Program Review
5.1 Requirements
5.2 Names
5.3 Prose
5.4 Data Definitions
5.5 Strategy
5.6 Abstraction
5.7 Other
6 Performance and Optimization, in Quotes
7 Extensions
7.1 Abstraction
7.1.1 Abstracting Code
7.1.2 Abstracting Data Definitions
7.1.3 Abstracting Function Specifications
7.2 Local
7.2.1 Local Functions
7.2.2 Local Constants
7.3 Accumulators
7.4 Generative Recursion
7.5 Termination Argument
7.5.1 Termination Argument:   Termination
7.5.2 Termination Argument:   Non-termination
7.6 Backtracking
7.7 Effects Statement
8 Object-Oriented Design
8.1 Testing Objects
8.2 Testing Mutable Objects

The Program Design Recipe

Last updated: Fri, 24 Apr 2015 16:27:38 -0400

The textbook introduces the notion of a design recipe as a step-by-step process for turning a problem statement and an empty code buffer into a program that solves the problem.

This page extends and further formalizes The Program Design Recipe, as it pertains to CS5010. You must apply this recipe when writing any programs for this course. Bookmark this page and refer to it often.

Discrepancies

When other course materials, like the textbook, conflict with this guide, defer to this guide. We try to sync all the course materials but some differences may still remain.

We will try to point out any discrepancies. For example:
Don’t hesitate to let us know if we missed any discrepancies.

Summary of Recipe Steps

These are the steps of The Program Design Recipe.

  1. Data Design

  2. Function Specification

  3. Function Implementation

  4. Testing

  5. Program Review

To write a function, apply these steps in order.

A program is a group of functions so to write a program, repeat these steps for every function you write.

Each step is explained in more detail below.

1 Data Design

All programs must process and compute with facts from the real world. We call these facts information. For example,
  • one program may process road and location information to compute driving directions;

  • another may process player input information to compute the current state of a game;

  • and yet another may process information about files on a disk to create a user interface.

To do this processing, however, programs must first encode information from the real world as data representations in the computer. The Data Design step determines these data representations.

This is the most critical step of the design recipe. It dictates all subsequent steps.

1.1 Data Definitions

To create a data represention for a piece of information, we write data definitions.

A data definition names a set of values and is created via a comment that begins:

; A <data-definition-name> is ...

Racket is case-sensitive so data definition names are as well.

This creates a data definition named <data-definition-name>. This name may then be referenced in other (or even the same) data definitions. The defined name may also be referenced in a function’s signature (see the Signature section).

See the Data Design section of the Style Guide for conventions to follow when writing data definitions.

To complete the data definition, we describe the set of values represented by <data-definition-name>. Specifically, the ellipses (...) above may be replaced with:

1.2 Data Invariants

Occasionally, the Data Definition rules presented thus far cannot express the precise set of values that we want our program to use. In this situation, we add data invariants to further restrict the set of values represented by the data definition.

The word WHERE may be useful to introduce such invariants, and the invariant itself is expressed in English prose.

Color, restricted to those accepted by 2htdp/image

; A Color is a String
; WHERE: for each Color c, (image-color? c) = true

World example

; A World is a (make-world ListOf<Ball> NonNegInt)
; WHERE: (length balls) == count
(define-struct world (balls count))
1.3 Interpretation

As mentioned, a data definition represents information, i.e., real-world facts. We describe what this information is via an interpretation.

It may be helpful to label an interpretation with INTERPRETATION or INTERP. unless it is very short.

TrafficGuide

; A TrafficGuide is one of:
; - (make-circle ...)
; - (make-octagon ...)
; INTERP: the circle is one possible traffic light,
;  and the octagon is a stop sign

Author name, made more precise

; An Author is a string, representing an author's last name.

Coordinate

; A Coordinate is a Real.
; INTERP:
;  Represents either an x or y pixel coordinate on a Universe (big-bang)
;  canvas, where (0,0) is in the upper-left corner, and right and down are
;  the positive directions.

If the data definition name does not directly name the units, the interpretation must include this information.

Make a judgement based on the specific program whether to use the unit name directly, or whether to use a more general data definition name.

Temperature

; A Temperature is a Real, in degrees Celsius.

Speed

; A Speed is an Integer, in m/s.

1.4 Data Examples

Data examples are an important part of Data Design. Concrete examples can often illustrate a data definition more clearly than English prose, particularly if the data definition is complex, e.g., an itemization data consisting of various mutually recursive compound data.

For example, the Xexpr definition from the last bullet in the Data Definitions section may be difficult to understand when viewed in isolation. However, some concrete HTML examples more clearly explains each part of the data definition to anyone who has some web programming experience.

X-expression examples

(define H1-XEXPR '(h1 "Heading"))
(define IMG-XEXPR '(img ((src "cat.gif"))))
(define BODY-XEXPR (list 'body H1-XEXPR IMG-XEXPR "some more text"))
(define HTML-XEXPR (list 'html BODY-XEXPR))

In addition, data examples often come in handy and eliminate code duplication when defining tests or Function Examples, so don’t ignore this step.

1.5 Templates

A data definition describes and names a set of values. A program then computes with those values via functions. To bridge the gap between data definitions and function implementations, we write templates.

We use the shape of the data to guide the shape of our code.

A template lays out the pieces or choices of compound data or itemization data, respectively.

In a template, use a placeholder function name that indicates the kind of data. Note however, that this is not a good function name, so when writing actual functions, you should change it to something better for your particular program.

1.5.1 Template for Compound Data

A template for compound data lays out the subpieces of that data.

A template for compound data helps programmers take inventory, so they know what they have to work with while implementing a function.

Note, however, that it’s not necessary for a function to use all the data pieces assembled by the template.

In addition, if any of the subpieces are still compound or itemization data, include a call to that kind of data’s template function.

1.5.2 Template for Itemization Data

A template for itemization data uses a cond to distinguish between the possible choices. The distinguishing expression processes the input and returns either true or false.

TrafficLightColor template

; TEMPLATE:
; trafficlightcolor-fn: TrafficLightColor -> ???
(define (trafficlightcolor-fn tl)
  (cond
    [(string=? tl "red") ...]
    [(string=? tl "yellow") ...]
    [(string=? tl "green") ...]))

Creating separate global constants and predicate functions that distinguish between the choices often makes code clearer (and easier to revise later):

TrafficLightColor template, with distinguishing predicates

(define RED "red")
...
(define (red? c) (string=? c RED))
...
; trafficlightcolor-fn : TrafficLightColor -> ???
(define (trafficlightcolor-fn tl)
  (cond
    [(red? tl) ...]
    [(yellow? tl) ...]
    [(green? tl) ...]))

Note that define-struct automatically defines predicates that can identify an instance of that struct.

The order of the cond clauses should match the data defintion, and ideally the simplest-to-distinguish choice should come first.

1.5.3 Template for Mixed Data

A mixed data template has a cond that distinguishes between the choices. Then, in each clause, extract the pieces of the appropriate compound data.

TrafficGuide Template

; trafficguide-fn : TrafficGuide -> ???
(define (trafficguide-fn sh)
  (cond
    [(circle? sh) (... (circle-radius sh) ...
                       (trafficlightcolor-fn (circle-color sh)) ...)]
    [(octagon? sh) (... (octagon-side sh) ...)]))

If any of the pieces are still compound or itemization data, then the template includes a call to that data’s template function. This way, we are reminded that a function should only perform one distinct task.

1.5.4 Template For Recursive Data

When the data definition has a self-reference, then there should be a self-reference in the template, i.e., a recursive call to the template function.

List of Ints Template

; A ListOfInt is one of:
; - empty
; - (cons Integer ListOfInt)
 
; TEMPLATE:
; loi-fn : ListOfInt -> ???
(define (loi-fn loi)
  (cond
    [(empty? lst) ...]
    [else (... (first lst)
               (loi-fn (rest lst)))]))

Again, if any of the resulting subpieces are still compound data or itemization data, then the template should call the appropriate function to process that kind of data.

List of Attributes Template

; A ListOfAttr is one of:
; - empty
; - (cons Attribute ListOfAttr)
 
; loa-fn : ListOfAttr -> ???
(define (loa-fn attrs)
  (cond
    [(empty? attrs) ...]
    [else (... (attribute-fn (first attrs)) ...
               (loa-fn (rest attrs)))]))
1.5.5 Template Summary

Here are separate summaries for how to write a proper templates for compound data and itemization data, respectively:

1.6 Data Design Summary

In summary, here are the (possible) outputs of the Data Design step.

The Data Design step defines all the data representations your program needs. The remaining steps describe how to implement a function that processes one of these kinds of data. Repeat all the remaining steps for each function required in your program.

2 Function Specification

A major goal of this course is to create readable programs. This famous quote comes from the Preface of the textbook SICP. In the words of Hal Abelson, programs must be written for people to read, and only incidentally for machines to execute

Unfortunately, code is inherently unreadable because:

The Function Specification step of The Program Design Recipe addresses this discrepancy. Each component of a Function Specification conveys a function’s behavior in a different manner, but always:

In summary, a Function Specification enables a reader to understand a program without looking at the implementation.

2.1 Signature

A function’s signature specifies what kind of data the function consumes and produces.

Nearly all programming languages support some form of signature specification. Some languages require annotating a function with statically checked types (e.g., Java, C++, OCaml). Other languages make use of runtime contracts.

Since different type and contract systems have varying degrees of expressiveness, to avoid this technical complexity, and to remain language agnostic, in this course we write a function’s signature as a comment. The signature begins with the function’s name, followed by a colon, followed by the kinds of input data, followed by an arrow, and finally ending with the kind of output data.

MouseEvent handler signature

; mouse-handler : World MouseEvent Coordinate Coordinate -> World
(define (mouse-handler w mev x y) ...)

A signature uses the Data Definitions defined in the Data Design step. If you reach this step and realize that your function requires an undefined data definition, go back to the Data Design step.

Note: In this course, we assume that a function will only receive input values that are allowed by its signature (and argument invariants). Thus, it’s not necessary to check for invalid inputs and throw errors.

2.2 Purpose Statement

A purpose statement is a high-level description, in English prose, of how a function computes its output from its inputs. A purpose statement should refer to a function’s parameters by name.

MouseEvent handler purpose statement

; mouse-handler : World MouseEvent Coordinate Coordinate -> World
; Computes the next World state based on the current World w,
; and a MouseEvent mev at coordinate (x,y).
(define (mouse-handler w mev x y) ...)
2.3 Argument Invariants

As with Data Invariants, we use argument invariants when necessary to further restrict the kinds of data that a function can consume and produce.

An argument invariant accompanies a function’s purpose statement and typically specifies a relation between a function’s arguments.

See also the note in the Signature section about error checking.

Radiuses invariant

; ring-area : Inches Inches -> Inches^2
; Computes the area of the ring formed by concentric circles with
; radiuses r1 and r2.
; WHERE: r1 < r2
(define (ring-area r1 r2) ...)

Length invariant

; balls-tick : ListOf<Ball> Natural -> ListOf<Ball>
; WHERE: (length bs) == numballs
(define (balls-tick bs numballs) ...)

Lengths invariant

; list-sum : ListOf<Natural> ListOf<Natural> -> ListOf<Natural>
; WHERE: (length lst1) == (length lst2)
; For each pair of corresponding numbers in lst1 and lst2, add them
; and return the results in a new list.
(define (list-sum lst1 lst2) ...)
2.4 Function Examples

As with Data Definitions and Data Examples, a good, concrete example can illustrate a function’s behavior more precisely than English prose. Thus, examples should accompany every function definition.

Note that examples differ from Testing. Examples should be illustrative, while tests are more comprehensive. See the Testing section for more information about testing.

A good use of function examples is to precisely describe any edge cases.

However, there’s no reason not to include any function examples in the program’s test suite. In this class, we use the begin-for-test form and Rackunit to define tests, so examples should be written using this framework as well. Don’t forget to label every test case with a string description.

list-sum examples

; list-sum : ListOf<Natural> ListOf<Natural> -> ListOf<Natural>
; WHERE: (length lst1) == (length lst2)
; For each pair of corresponding numbers in lst1 and lst2, add them
; and return the results in a new list.
(begin-for-test
  (check-equal? (list-sum empty empty)
                empty
                "empty lists")
  (check-equal? (list-sum (list 1 2 3) (list 4 5 6))
                (list 5 7 9)
                "non-empty list"))
(define (list-sum lst1 lst2) ...)
2.5 Design Strategy

In general, each step in The Program Design Recipe provides more detail than the steps before it.

A design strategy begins to explain a function’s implementation.

In this course, there are three design strategies, described below.

Every function you write should declare its strategy in a comment, prefixed by STRATEGY:.

2.5.1 Function Composition

A function employing the function composition strategy does not inspect subcomponents of its data. Instead, it merely passes the data on to be processed by other functions, and then combines the result of these function calls.

Functions that process scalar data (i.e., non-compound and non-itemization data) like numbers and strings must employ the function composition strategy.

Note: Function composition is equivalent to the textbook’s notion of arithmetic.

However, function composition is frequently an appropriate strategy for processing compound or itemization data as well, particularly when you separate the function’s behavior into multiple, distinct tasks.

2.5.2 Data Decomposition

The data decomposition strategy extends function composition.

Specifically, a function that decomposes compound data first extracts and processes the subpieces of its input, utilizing the template for that kind of data to do so, and then combines those subresults using function composition.

A function that decomposes itemization data first distinguishes the possible choices via cond, utilizing that data’s template to do so, and then uses function composition in the right-hand side of each cond clause.

Since a function should only perform one distinct task, data decomposing functions should only decompose one kind of data.

A data decomposition function should be labled with both the kind of data it’s decomposing, and the variable representing that data.

data decomposition strategy

; trafficguide-fn : Trafficguide -> ???
; STRATEGY: data decomposition on tg : TrafficGuide
(define (trafficguide-fn tg) ...)
2.5.3 Generative Recursion

Generative recursion generalizes the data decomposition strategy.

For the first half of the course, we will only use Function Composition and Data Decomposition.

See Generative Recursion for more details about generative recursion.

2.6 Function Specification Summary

In summary, here are the components of the Function Specification step:

See the Function Specification section of the style guide for additional guidelines on how write a good function specification.

3 Function Implementation

An overarching theme of this course is creating readable code. Unfortunately, code by definition is for computers to run and so is inherently not very pleasant for humans to read.

To address this, we avoid looking at code as much as possible. Thus, the first several of the The Program Design Recipe attempts to explain a function’s behavior without looking at code.

To have functioning programs, however, we must eventually implement code. But we can follow some guidelines to ensure the code is well-organized and as clear as possible.

As a first step, function’s implementation must match all the specification from the Function Specification step:
  • It must consume the kind of inputs and produce the output declared in the signature.

  • It must satisfy the purpose statement.

  • It must satisfy any argument invariants.

  • It must produce the expected results of any examples.

  • It must follow the declared strategy.

Regarding the last point, a function composition function cannot decompose any of its inputs. A data decomposition function must use the template of the declared kind of data and may only decompose (i.e., use the accessors of) that kind of data.

The following tutorial presents more guidelines for implementing functions: How to Implement Functions

4 Testing

While Function Examples should be illustrative, to confirm that a program behaves as intended, all programs should have a more comprehensive test suite.

In this class we use the begin-for-test form from "extras.rkt", in conjunction with the Rackunit testing framework, to define tests for our programs.

NOTE: Racket’s Beginner Languages have their own testing forms (e.g., check-expect, etc) that are separate from Rackunit . Do not use the Beginner Language testing forms in this course. Ask if you are confused about this.

Each Rackunit function (like check-equal? or check-true) accepts an optional string as the last argument. You should always supply a string describing the test for this argument.

We also make use of DrRacket’s code coverage tool to check that all parts of a program are at least somewhat tested. At a minimum, all programs should have 100% code coverage.

UPDATE : For Beginning Student and other beginner languages, the code coverage tool is enabled by default. When you run your program, untested code is highlighted in black. For full Racket (later in the semester), enable code coverage through the DrRacket "Choose Language" menu at the bottom-left: Choose Language -> The Racket Language -> Show Details -> Dynamic Properties -> Syntactic test suite coverage

How to Test
Equivalence Partitioning

Employ equivalence partitioning when testing your code. In other words, for a given function, think about how to divide its possible inputs into equivalent groups, and then write at least one test per group. During code walks, it’s very likely that we will ask what partitions you came up with for a particular function.

For example, say we want to write tests for the following function that computes the distance between two points:

(Notice the acceptable double decomposition here.)

dist

; dist : Posn Posn -> NonNegReal
; Returns the Euclidean distance between pt1 and pt2.
; STRATEGY: data decomposition on pt1, pt2 : Posn
(define (dist pt1 pt2)
  (sqrt (+ (sqr (- (posn-x pt1) (posn-x pt2)))
           (sqr (- (posn-y pt1) (posn-y pt2))))))

The following two tests are probably redundant, since they fall into the same partition. Note the use of check-equal?’s third arugment to label the partitions.
(define PT1 (make-posn 1 2))
(define PT2 (make-posn 4 6))
(define PT3 (make-posn 2 4))
(define PT4 (make-posn 7 16))
(begin-for-test
  (check-equal? (dist PT1 PT2) 5 "positive differences")
  (check-equal? (dist PT3 PT4) 13 "positive differences"))

A better second test might be:
(define PT5 (make-posn -3 -8))
(check-equal? (dist PT5 PT3) 13 "negative differences")

Another good test would be:

(check-true (zero? (dist PT5 PT5)) "same point")

A "partition" can involve more than one call to the function:

(check-equal? (dist PT1 PT3) (dist PT3 PT1) "order doesn't matter")

In other words, you can test "properties" of the function. Note, however, that this last test would catch some errors (e.g., a missing sqr) but not others (e.g., a missing sqrt).

Errors Reveal More Test Partitions

It’s not always obvious how many different partitions need to be tested. Sometimes, new partitions are only revealed after making a mistake.

As a second example, imagine we want to implement the function inside-circle?

wrong version of inside-circle?

; inside-circle? : Posn Pixels Posn -> Boolean
; Returns true if pt lies inside the circle represented by center and radius.
; STRATEGY: data decomposition on center, pt : Posn
(define (inside-circle?.bad center radius pt)
  (and (< (abs (- (posn-x pt) (posn-x center)))
          radius)
       (< (abs (- (posn-y pt) (posn-y center)))
          radius)))

(The .bad prefix is just a flag for the reader. We will continue to use inside-circle? as the function name.)

This first version is wrong, but let’s see if testing can reveal the mistake.

On first glance, one might think that we only need two test partitions: a point inside the circle and a point outside the circle.

(define ORIGIN (make-posn 0 0))
(define PT50 (make-posn 5 0))
(define PT30 (make-posn 3 0))
(begin-for-tests
  (check-false (inside-circle? ORIGIN 4 PT50) "outside")
  (check-true (inside-circle? ORIGIN 4 PT30) "inside"))

However, our incorrect implementation passes both the tests.

A better test suite might additionally include the edge case where pt is on the circle’s border (which is not considered "inside" the circle).

(define PT40 (make-posn 4 0))
(check-false (inside-circle? ORIGIN 4 PT40) "on the border")

However, the incorrect implementation passes this test as well.

The first version of inside-circle? is wrong because it only computes if pt is inside the bounding box of the circle represented by center and radius. Thus, to reveal the error, we need a test where pt is outside the circle but inside the bounding box

(define PT33 (make-posn 3 3))
(check-false (inside-circle? ORIGIN 4 PT33) "outside, but inside bounding box")

Our incorrect first version of inside-circle? does not pass this test.

Here is a correct implementation of inside-circle?, which uses our dist function.

correct version of inside-circle?

; inside-circle? : Posn Pixels Posn -> Boolean
; Returns true if pt lies inside the circle represented by center and radius.
; STRATEGY: function composition
(define (inside-circle? center radius pt)
  (< (dist center pt) radius))

This correct version passes all of our tests.

The lesson here is that it’s not always initially obvious how many partitions are needed. A test suite should include tests for any mistakes you made while coding (make note of any such tests, since you’ll probably be asked about them during code walks). A particularly thorough test suite may want to consider mistakes that may be made as well. Of course, no test suite can completely capture all possible inputs but considering possible mistakes and testing for them is the kind of reasoning we expect from good students.

A note on code coverage: Any single test would produce 100% coverage, according to DrRacket’s code coverage tool, for these functions. However, as demonstrated, one test is clearly an insufficient test suite. This is why we say that 100% test coverage is a minimum requirement.

5 Program Review

A program is like an essay. The first version is a draft, and drafts demand editing. – How to Design Programs, second edition

The above quote from the textbook is a nice way of saying that the first version of anything is terrible and must be improved. Thus if you submit the first version of your homework assignment, expect to receive a comparably terrible grade.

Programming must be an iterative process. The last but crucial step of the design recipe requires looking back and improving the code you wrote.

You will be asked questions about your refactoring and improvements during your code walks. It may be a good idea to keep a journal as you complete each homework assignment, to better help you remember the rationale for your decisions.

5.1 Requirements

In this step, you should check that your program meets all requirements, which may have changed since the last time you checked. This is extremely common in practice and in this course as well.

Or you may realize that some requirements are actually unclear or ambiguous. This is also extremely common in practice. If you think a requirement is unclear, you should ask your client (or in this course, the course staff) questions until things are clear. This is yet another reason why it’s important to start early on each assignment.

5.2 Names

Names are vital if one wishes to write clear code. This includes functions, variables, and data definition names.

During the review step, review your names to make sure they are as clear and accurate as possible.

5.3 Prose

The design recipe requires you to write a lot of prose, for purpose statements, interpretations, comments, etc.

Like any piece of writing, you should be constantly updating these parts of your program so that they are as clear, precise, and accurate as possible.

5.4 Data Definitions

Review data definitions and explore possible improvements. In particular, some data definition variations may make certain functions easier to implement and make other functions more complicated. You should constantly be thinking about such tradeoffs and be prepared to discuss them during your code walks.

5.5 Strategy

Read this tutorial illustrates some guidelines for choosing between the different design stratgies: How to Implement Functions.

5.6 Abstraction

Always be on the lookout for repeated code. This will be addressed in more detail when we study lists.

5.7 Other

Some other tasks that you may want to do during program review are:
  • code cleanup; remove extraneous code,

  • collapsing cond branches, when dealing with data like MouseEvents or KeyEvents.

Less important in this course, but important in practice, this is the step where you would review and profile the performance of your program, and explore optimizations.

6 Performance and Optimization, in Quotes

This course does not focus on performance. We favor clean readable code over "optimized" solutions that are often a little too clever and difficult to understand. In general, you will not be penalized for performance except in extreme cases or where explicitly mentioned.

To summarize how you should view performance and optimization, we defer to those with more experience and expertise than us (as quoted in [EffectiveJava]):

7 Extensions

7.1 Abstraction

This subsection supplements Part III of the textbook and describes one example of creating abstractions for common pieces of code. In some sense, the process of abstraction works backwards through the steps of the design recipe.

We start with the following code.

; A Name is a String with no spaces, representing a capitalized first Name.
(define STEVE "Steve")
(define DAN "Dan")
(define RAHUL "Rahul")
 
; A ListOfName (LoN) is one of:
; - empty
; - (cons Name LoN)
; Represents a sequence of first names.
(define STEVE-DAN-RAHUL (cons STEVE (cons DAN (cons RAHUL empty))))
 
; TEMPLATE
; names-fn : ListOfName -> ???
(define (names-fn names)
  (cond
    [(empty? names) ...]
    [else
     (... (first names) ... (names-fn (rest names)) ...)]))
 
; A ListofImage (LoI) is one of:
; - empty
; - (cons Image LoI)
; Represents a sequence of 2htdp/image images.
 
(define RED-CIRCLE (circle 5 "solid" "red"))
(define BLUE-SQUARE (square 10 "outline" "blue"))
(define BLACK-CIRCLE (circle 12 "solid" "black"))
(define CIRCLE-SQUARE-CIRCLE (list RED-CIRCLE BLUE-SQUARE BLACK-CIRCLE))
 
; TEMPLATE
; images-fn : ListOfImage -> ???
(define (images-fn imgs)
  (cond
    [(empty? imgs) ...]
    [else
     (... (first imgs) ... (images-fn (rest imgs)) ...)]))
 
(define THE-FIRST "TheFirst")
 
; names-join : ListOfName -> Name
; Appends a list of Names together and adds the suffix "TheFirst"
; Strategy: data decomposition on names : ListOfString
(define (names-join names)
  (cond
    [(empty? names) THE-FIRST]
    [else
     (string-append
      (first names)
      (names-join (rest names)))]))
 
(begin-for-test
  (check-equal? (names-join empty) THE-FIRST)
  (check-equal? (names-join STEVE-DAN-RAHUL) (string-append STEVE DAN RAHUL THE-FIRST)))
 
 
; images-join : ListOfImage -> Image
; Appends a list of images together side-by-side.
; Strategy: data decomposition on imgs : ListOfImage
(define (images-join imgs)
    (cond
      [(empty? imgs) empty-image]
      [else
       (beside
        (first imgs)
        (images-join (rest imgs)))]))
 
(begin-for-test
  (check-equal? (images-join empty) empty-image)
  (check-equal? (images-join CIRCLE-SQUARE-CIRCLE)
                (beside RED-CIRCLE BLUE-SQUARE BLACK-CIRCLE)))

There are many commonalities between the two functions so we identify it as a candidate for abstraction.

7.1.1 Abstracting Code

First we pull out the common pieces of code:
; join : ???
; Strategy: data decomposition on lst : ???
(define (join combine-fn mt lst)
  (cond
    [(empty? lst) mt]
    [else
     (combine-fn (first lst) (join combine-fn mt (rest lst)))]))
 
; ???
(define (names-join names)
  (join string-append THE-FIRST names))
; ???
(define (images-join imgs)
  (join beside empty-image imgs))

But now we want our function specifications to reflect the abstraction so let’s look at the data definitions in question.

7.1.2 Abstracting Data Definitions

If we abstract the common parts of ListOfName and ListOfImage, we get:

; A ListOf<X> is one of:
; - empty
; - (cons X ListOf<X>)
; Represents a sequence of X elements.
 
; list-fn : ListOf<X> -> ???
(define (list-fn lst)
  (cond
    [(empty? lst) ...]
    [else (... (first lst) ... (list-fn (rest lst)) ...)]))
 
; A ListOfName is a ListOf<Name>
; A ListOfImage is a ListOf<Image>

Here ListOf<X> declares a name of a data definition ListOf, as well as a parameter named X, in the same way that (define (f x) ...) declares f as the name of a function and its parameter x.

(Note that our syntax for a parameterized data definition deviates from the textbook.)

To use this parameterized data definition, we have to give it another data definition name. Here we’ve re-defined ListOfName and ListOfImage to use ListOf<X>. In fact, it’s no longer necessary to explicitly define ListOfName and ListOfImage and instead, ListOf<Name> and ListOf<Image> may be used directly in signatures and other data definitions.

Many other programming languages utilize parameterized data definitions, such as Java’s generics and C++ templates.

7.1.3 Abstracting Function Specifications

Now we may add function specifications to our abstracted functions.

; join : (X Y -> Y) Y ListOf<X> -> Y
; Iteratively applies combine-fn to an element of lst and an intermediate
; accumulated value, where mt is the initial accumulator.
; STRATEGY: data decomposition on lst : ListOf<X>
(define (join combine-fn mt lst)
  (cond
    [(empty? lst) mt]
    [else
     (combine-fn (first lst) (join combine-fn mt (rest lst)))]))
 
; names-join : ListOf<Name> -> Name
; STRATEGY: function composition
(define (names-join names)
  (join string-append THE-FIRST names))
; images-join : ListOf<Image> -> Image
; STRATEGY: function composition
(define (images-join imgs)
  (join beside empty-image imgs))

In the signature of join, the undefined X and Y are implicitly declared as parameters, in the same was that the X in ListOf<X> is a parameter. The X and Y are implicitly filled in on a call to join, with the concrete data definition name of join’s arguments. For example, when join is called in names-join, both the X and Y in join’s signature are implicitly replaced with Name.

Quiz: What is another name for the join function?

7.2 Local

The Intermediate Student language introduces local. Here are some guidelines for when to use local.

7.2.1 Local Functions

In general, functions should not be defined using local.

Functions should represent one precise task that makes sense regardless of context (i.e., the function should make sense regardless of who calls it).

Using local also makes testing and debugging of functions more difficult.

Thus most functions should be defined at the top-level. In general, you should avoid writing local functions.

However, here are some instances where local functions may make your code clearer:
  1. To specialize (i.e., partially apply) multi-argument functions, for example as an argument to another function like map, filter, foldr, etc.

  2. Related to item 1, use local to leverage scope to cut down on the number of arguments passed around. Of course, you should only do this when it does not make your code more difficult to understand, but this can technique can often cut down on extraneous code.

    Here is an example, from exercise 245 in the textbook:
    ; A Name is a String that is capitalized and consists of only letters.
     
    ; prefix-of? : Name ListOf<Name> -> Boolean
    ; Returns true if nam is a prefix of any element of nams.
    ; Strategy: function composition
    (define (prefix-of? nam nams)
      (local
        ((define nam-length (string-length nam))
     
         ; prefix-of-nam? : Name -> Boolean
         ; Returns true if nam is a prefix of n.
         ; Strategy: function composition
         (define (prefix-of-nam? n)
           (and (<= nam-length (string-length n))
                (string=? nam (substring n 0 nam-length)))))
        (ormap prefix-of-nam? nams)))

  3. To group functions that together process mutually referential data definitions. See part IV of the textbook, specifically exercise 263 and chapter 22.5.

    When you have functions like this that operate as a group, the templates should be grouped as well.

  4. When writing accumulator functions.

Functions defined via local must be accompanied by all the Function Specification requirements. You may occasionally omit examples, since local functions are typically small and are difficult to test. However, add informal examples when it helps explain the behavior of your function.

7.2.2 Local Constants

Define local constants when it would eliminate duplicate expressions and clean up your code.

In other words, the primary benefit of introducing local constants is readability, not performance.

Thus if the resulting code is not more concise and readable, do not introduce local constants.

In the prefix-of? example above, the only benefit of defining nam-length is to make the code more precise.

This means that local constants need especially good variable names. If a reader has to repeatedly refer back to the local definition, then the local definition has made your code worse.

7.3 Accumulators

This short section explains how to use accumulators in this course. (It supplements the guide in Chapter 37.2.)

Accumulators capture additional context information, typically in recursive functions.

Here is a concrete example. It’s the same invert example from the textbook.

; invert : ListOf<X> -> ListOf<X>
; Reverses the given list.
; Strategy: function composition
(define (invert lst0)
  (local (; ListOf<X> ListOf<X> -> ListOf<X>
          ; Reverses lst onto rev-so-far.
          ; WHERE: rev-so-far is the elements of lst0 reversed so far,
          ; and lst is the elements of lst0 to be reversed.
          ; Strategy: data decomposition on lst : ListOf<X>
          (define (invert/a lst rev-so-far)
            (cond
              [(empty? lst) rev-so-far]
              [else (invert/a (rest lst) (cons (first lst) rev-so-far))])))
    (invert/a lst0 '())))
7.4 Generative Recursion

Generative recursion generalizes the data decomposition strategy.

Generative recursive functions roughly try to break a problem into (a) smaller version(s) of the problem on each recursive call. A generative recursive function has this rough form:

; genrec-fn : Problem -> Solution
; Purpose statement ...
; Strategy: Generative Recursion
; TERMINATION ARGUMENT:
; 1) declares that the function always terminates and explains why,
;    i.e., in what way the smaller problems are smaller
; 2) declares that the function may not terminate and gives examplse
(define (genrec-fn problem)
  (cond
    [(trivial? problem) ...]
    ...
    [else
     (combine
      (genrec-fn (create-smaller-problem problem)) ...)]))

NOTE: Though it resembles a template, this is not a template in the same sense as you are used to at this point in the course, because this code is not following the shape of any data definition. This is merely a code skeleton intended to provide some guidance in writing generative recursive functions. In other words, you do not need to include this outline your other Data Design deliverables.

The recursion stops when the function encounters a trivially-solvable problem. Otherwise, the function recursively calls itself on smaller versions of the problem, and then combines the results.

A function utilizing generative recursion must additionally present a termination argument. A termination argument is considered part of the Function Specification step.

7.5 Termination Argument

A termination argument either:
  • declares that the function always terminates and explains how by demonstrating that each recursive call operates on a smaller problem than the function’s inputs.

  • declares that the function may not terminate and gives example inputs that result in non-terminatation.

7.5.1 Termination Argument: Termination

For the first case of terminating generative recursive functions, the meaning of "smaller" in the termination argument differs depending on each specific function.

For data decomposition, the smaller refers to the number of subpieces of data. That is why data-decomposing functions do not need termination arguments, because we know they always terminate.

Though a termination argument can take any form, including English prose, the most clear and concise way to state a termination argument is via a halting measure. A halting measure is a piece of code that:
  • evaluates to a natural number,

  • cannot be less than zero,

  • and always decreases on every recursive call

Hence the halting measure demonstrates that the recursion eventually stops.

For example, the halting measure in quick-sort is the length of the list because the pivot is always excluded from the recursive calls:

; ListOf<Number> -> ListOf<Number>
; Sorts the given list of numbers in ascending order.
; Strategy: generative recursion
; Halting Measure: (length alon) always decreases
(define (quick-sort alon) ...)

NOTE: A termination argument does not explain when a function terminates. For example, "the function terminates when the list lst is empty" is not a valid termination argument.

A termination argument explains how and why a function terminates. A valid termination argument could be "the list lst gets smaller on every recursive call", or simply "HALTING MEASURE: (length lst)".

Ask on Piazza if you still don’t understand the difference between stating when a function terminates, versus how and why it terminates.

7.5.2 Termination Argument: Non-termination

Use the second termination argument alternative when a generative recursive function may loop forever. In this case, the termination argument should clearly state which function inputs cause non-termination. This is vital information for someone trying to read and understand the program. See the bundle in example in Chapter 29 for a concrete example.

7.6 Backtracking

A backtracking function is a kind of generative recursive function.

Thus, a backtracking function has the general shape of a typical generative recursive function, with a few differences:

; backtrack-fn : Problem -> Maybe<Solution>
; Purpose statement ...
; Strategy: Generative Recursion
; TERMINATION ARGUMENT: explain either
; 1) why the function terminates, i.e., in what way the smaller problems are smaller
; 2) when the function does not terminate
(define (backtrack-fn problem)
  (cond
    [(trivial-or-fail? problem) ...]
    ...
    [else
     (local ((define result/#f (backtrack-fn (create-smaller-problem problem))))
       (if (false? result/#f)
           (backtrack-fn (next-smaller-problem problem)) ; backtrack
           result/#f))]))
7.7 Effects Statement

8 Object-Oriented Design

See Interfaces, objects, and dispatching document for object-oriented design guidelines.

8.1 Testing Objects

Prior to using objects, we didnt have to worry much about how to test our programs. The check-equal? and other testing functions handled comparisons, including deep comparisons of compound (student langage) define-struct and list values, automatically.

However, a tradeoff cost that comes with the additional encapsulation introduced by classes and interfaces is that we no longer have immediate access to the data inside every object, so comparing objects via check-equal? or equal? is insufficient.

> (define Ball.v0%
    (class* object% ()
      (init-field x  ; x-axis Coordinate
                  y  ; y-axis Coordinate
                  r) ; radius, in Pixels
      (super-new)))
> (define ball1 (new Ball.v0% [x 1][y 2][r 10]))
> (define ball2 (new Ball.v0% [x 1][y 2][r 10]))
> (equal? ball1 ball2)

#f

(Note that of course equal? still returns true when comparing an object to itself.)
> (equal? ball1 ball1)

#t

Hence testing object-oriented programs requires a different approach.

We can only test observable parts of an object, i.e., values that are publically accessable through an interface and define/public.

> (define Ball.v1<%>
    (interface ()
      ; testing:get-x : -> Coordinate
      ; Returns the x coordinate of the ball.
      testing:get-x
      ; testing:get-y : -> Coordinate
      ; Returns the y coordinate of the ball.
      testing:get-y))
> (define Ball.v1%
   (class* object% (Ball.v1<%>)
     (init-field x  ; x-axis Coordinate
                 y  ; y-axis Coordinate
                 r) ; radius, in Pixels
     ; testing:get-x : -> Coordinate
     (define/public (testing:get-x) x)
     ; testing:get-y : -> Coordinate
     (define/public (testing:get-y) y)
     (super-new)))
> (define ball1 (new Ball.v1% [x 10][y 20][r 100]))
> (define ball2 (new Ball.v1% [x 10][y 20][r 100]))
> (equal? ball1 ball2)

#f

> (= (send ball1 testing:get-x) (send ball2 testing:get-x))

#t

> (= (send ball1 testing:get-y) (send ball2 testing:get-y))

#t

Note the testing: prefix for methods that are added to an interface for testing purposes only. See the OOP Style guide for other object-oriented style rules.

Note: Add testing: methods only as a last resort. You should prefer to test objects through their available public interface. In this demonstration example, there are no public methods so we add two accessor methods for testing.

A second option is to write your own comparison function.

; ball=? : Ball.v1<%> Ball.v1<%> -> Boolean
; Compares two ball objects for equality.
> (define (ball=? b1 b2)
    (and (= (send b1 testing:get-x) (send b2 testing:get-x))
         (= (send b1 testing:get-y) (send b2 testing:get-y))))
> (ball=? ball1 ball2)

#t

Note that now you must decide which parts of a ball should be included for the purposes of computing equality. Here we’ve decided to exclude the radius field. (A better name for this comparison function would be ball-location=?.)

A third option is to add a comparison method.

> (define Ball.v2<%>
    (interface ()
      ; testing:get-x : -> Coordinate
      ; Returns the x coordinate of the ball.
      testing:get-x
      ; testing:get-y : -> Coordinate
      ; Returns the y coordinate of the ball.
      testing:get-y
      ; ball=? : Ball.v2<%> -> Boolean
      ; Returns true if the given ball is equivalent to this one.
      ball=?))
> (define Ball.v2%
   (class* object% (Ball.v2<%>)
     (init-field x  ; x-axis Coordinate
                 y) ; y-axis Coordinate
     ; testing:get-x : -> Coordinate
     (define/public (testing:get-x) x)
     ; testing:get-y : -> Coordinate
     (define/public (testing:get-y) y)
     ; ball=? : Ball.v2<%> -> Boolean
     (define/public (ball=? b)
       (and (= x (send b testing:get-x))
            (= y (send b testing:get-y))))
     (super-new)))
> (define ball1 (new Ball.v2% [x 10][y 20]))
> (define ball2 (new Ball.v2% [x 10][y 20]))
> (equal? ball1 ball2)

#f

> (send ball1 ball=? ball2)

#t

> (send ball2 ball=? ball1)

#t

UPDATE 2015-04-09: Another option is to have your classes implement the equal<%> interface, which requires three methods: equal-to?, equal-hash-code-of, equal-secondary-hash-code-of.

Thanks to Ankit for pointing out this option.

The equal-to? method is invoked when comparing two objects of the same class using equal?. The other two methods are used for hashing, for example if an object is added to a hash table.

Implementing the equal<%> interface is similar you how you might implement object equality in other OO languages like Java. Similar to these other languages, you must implement all three methods such that if two objects are equivalent according to equal?, then they must return the same hash codes.

Like the other testing options, you should only implement equal<%> if you cannot fully test the functionality of your program through already-accessible interface methods.

> (define Ball.v3<%>
    (interface ()
      ; testing:get-x : -> Coordinate
      ; Returns the x coordinate of the ball.
      testing:get-x
      ; testing:get-y : -> Coordinate
      ; Returns the y coordinate of the ball.
      testing:get-y))
> (define Ball.v3%
   (class* object% (Ball.v3<%> equal<%>)
     (init-field x  ; x-axis Coordinate
                 y) ; y-axis Coordinate
     ; testing:get-x : -> Coordinate
     (define/public (testing:get-x) x)
     ; testing:get-y : -> Coordinate
     (define/public (testing:get-y) y)
  
     ; required equal<%> methods -
     ; use the recur parameter on nested objects; not needed here
     (define/public (equal-to? b recur)
       (and (= x (send b testing:get-x))
            (= y (send b testing:get-y))))
     (define/public (equal-hash-code-of recur)
       (equal-hash-code (list x y)))
     (define/public (equal-secondary-hash-code-of recur)
       (equal-secondary-hash-code (list x y)))
    (super-new)))
> (define ball1 (new Ball.v3% [x 10][y 20]))
> (define ball2 (new Ball.v3% [x 10][y 20]))
> (equal? ball1 ball2)

#t

Regardless of which option you choose, the overarching lesson is that with objects, we must now put more thought into our testing strategy.

Note: Regarding define-structs in the student languages (e.g., Beginning Student) versus full Racket (i.e., #lang racket), define-structs in full Racket are opaque just like objects.

; using #lang racket
> (define-struct opaque-ball (x y))
> (equal? (make-opaque-ball 1 2) (make-opaque-ball 1 2))

#f

To define structs in full Racket that behave like student language structs, add a #:transparent tag to your define-struct definition.

; using #lang racket
> (define-struct ball (x y) #:transparent)
> (equal? (make-ball 1 2) (make-ball 1 2))

#t

Note: While reading the Racket documentation, you may stumble upon the (inspect false) form that "opens" objects in the same way that #:transparent opens structs. To practice good object-oriented programming, do not use this form.

Finally here is some additional material on testing objects.

Note: These slides are from a previous semester. We provide them because learning is often aided by looking at different presentations of the same material. However, previous iterations of the course had a different structure and different style requirements. Read these slides for their ideas only. When there are discrepancies, follow the rules of our current course.
  • CS5010f14: Testing Simple Objects [pptx] [pdf]

  • CS5010f14: Observables vs Fields [pptx] [pdf]

8.2 Testing Mutable Objects

Testing mutable objects is more involved than testing immutable objects because more effort is required to get the object into the proper state. Also, if you re-use objects between different tests, you must now pay attention to the order in which your tests appear. Testing frameworks for mutable objects in other languages must explicitly account for these setup and teardown phases.

With mutable objects, you can’t simply chain together constructor and method calls. You must first create the object, giving it a name, and then sequentially send a series of method calls. However, be careful when reusing this object in subsequent tests since it’s no longer in its initial state. This complication is yet another reason why programs should strive to use as little mutation as possible.

> (define Ball<%>
    (interface ()
      ; tick! : -> Void
      ; EFFECT: Moves this ball horizontally to the right by 3 pixels
      ; and changes it color every 5th tick.
      tick!
  
      ; get-color : -> Color
      ; Returns the color of this ball.
      get-color
  
      ; get-x : -> Coordinate
      ; Returns the x coordinate of this ball.
      get-x))
; Represents a horizontally moving ball that changes between red and green
; on every 5th tick.
> (define Ball%
    (class* object% (Ball<%>)
      (super-new)
      (init-field x) ; Coordinate
  
      (field [X-VEL 3] ; Pixels/tick
             [COLOR-CHANGE-FREQ 4]
             [color "green"]  ; Color
             [color-countdown ; Natural between [0,5), Represents ticks until color change
              COLOR-CHANGE-FREQ])
  
      ; toggle-color! : -> Void
      ; EFFECT: toggles the color of this ball between red and green.
      (define (switch-color!)
        (set! color-countdown COLOR-CHANGE-FREQ)
        (if (string=? color "green")
            (set! color "red")
            (set! color "green")))
  
      ; tick! : -> Void
      (define/public (tick!)
        (set! x (+ x X-VEL))
        (if (zero? color-countdown)
            (switch-color!)
            (set! color-countdown (sub1 color-countdown))))
  
      ; get-color : -> Color
      (define/public (get-color) color)
      ; get-x : -> Coordinate
      (define/public (get-x) x)))
> (define b (new Ball% [x 10]))
> (check-equal? (send b get-x) 10 "initial x coordinate")
> (check-equal? (send b get-color) "green" "initial color")
> (send b tick!)
> (check-equal? (send b get-x) 13 "x coordinate after 1 tick")
> (check-equal? (send b get-color) "red" "oops")

--------------------

FAILURE

actual:     "green"

expected:   "red"

name:       check-equal?

location:   (eval 40 0 40 1)

expression: (check-equal? (send b get-color) "red")

message:    "oops"

Check failure

--------------------

> (check-equal? (send b get-color) "green" "color doesnt change after 1 tick")
> (send b tick!)
> (send b tick!)
> (send b tick!)
> (check-equal? (send b get-x) 22 "x coord after 4 ticks")
> (check-equal? (send b get-color) "green" "right before color change")
> (send b tick!)
> (check-equal? (send b get-color) "red" "color changed on 5th tick")
> (send b tick!)
> (send b tick!)
> (send b tick!)
> (send b tick!)
> (check-equal? (send b get-color) "green"
                "color changed back to green --- oops it didnt")

--------------------

FAILURE

actual:     "red"

expected:   "green"

name:       check-equal?

location:   (eval 53 0 53 1)

expression: (check-equal? (send b get-color) "green")

message:    "color changed back to green --- oops it didnt"

Check failure

--------------------

> (send b tick!)
> (check-equal? (send b get-color) "green" "color changed back to green")

NOTE: begin-for-test does not allow internal defines, so use local or let to create your initial testing objects.

(begin-for-test
  (let ([b (new Ball% [x 10])])
    (send b tick!)
    (check-equal? (send b get-x) 13)
    ...))

Here are some additional slides on testing mutable objects.

Note: These slides are from a previous semester. We provide them because learning is often aided by looking at different presentations of the same material. However, previous iterations of the course had a different structure and different style requirements. Read these slides for their ideas only. When there are discrepancies, follow the rules of our current course.
  • CS5010f14: Testing Mutable Objects [pptx] [pdf]