The Design Recipe🔗

Last updated: Wed, 6 Nov 2024 11:48:27 -0500

A central concept in this course is a Design Recipe.

A Design Recipe is a systematic way to write readable and correct high-level code (no matter what programming language you’re using).

The Textbook describe some steps of the recipes, but this page summarizes the official recipe we use in this course.

There are two main recipes: one for Data Design and one for Function Design.

1 Data Design Recipe🔗

The first step of any programming task is to determine what kind of data the program operates on.

Examples of data are numbers, strings, or some combination of values like coordinates.

Since a program’s purpose is to accomplish a real-world task, this data must be a represention, i.e., a data representation, of some real-world concept.

More specifically, a data representation consists of one or more data definitions.

1.1 Data Definitions🔗

A data definition consists of the following parts:

1. a name,

2. a description of the set of all possible values of this data,

3. an interpretation that explains what real-world concepts are represented by this data definition,

4. A predicate is a function that returns a Boolean value.

   See below for various refinements to predicate requirements for different kinds of data definitions, e.g., enumerations and itemizations from lecture 5.

   a single-argument predicate function that returns true for members of this data definition (if needed, define additional predicates for each enumeration or itemization).

5. Templates introduced in lecture 5.

   For some kinds of data, a template sketches what the code for a function that processes this kind of data looks like.

   In this course, we use a four-dot ellipsis (....) as template placeholders, to be filled in later, for unknown parts of the function.

   The template will use the predicates defined in the previous step (with define/contract or cond).

   See Kinds of Data Definitions for more details.

1.2 Kinds of Data Definitions🔗

• basic data values, e.g., integers, strings.

  Occasionally, we can directly use "built-in" data definitions, e.g., Number or String.

  The "built-in" data definitions are the ones with built-in predicates, e.g., number? or string?.

  The function template for built-in data is straightforward. It consists of just a function header and a (partial) contract to validate the input.

  Example:

  ;; int-fn : Integer -> ....

  (define/contract (int-fn x)

  (-> integer? ....)

  ....)

  Functions that process basic data typically compute with straightforward arithmetic. Thus the template, uses a .... as a placeholder, to be filled in later.

  An important piece of information that is missing from built-in templates, however, is the interpretation.

  Thus, it is often better to define new data definition, even for data that are basic values.

  Examples:

  ;; A TempC is an Integer

  ;; Interp: Represents a temperature in degrees Celsius.

  (define (tempc? x) (exact-integer? x))

  ;; tempc-fn : TempC -> ....

  (define/contract (tempc-fn x)

  (-> tempc? ....)

  ....)

  ;; A TempF is a Real

  ;; Interp: Represents a temperature in degrees Fahrenheit.

  (define (tempf? x) (real? x))

  ;; tempf-fn : Tempf -> ....

  (define/contract (tempf-fn x)

  (-> tempf? ....)

  ....)

  ;; A TempK is a non-negative Integer

  ;; Interp: Represents a temperature in degrees Kelvin.

  (define (tempk? x) (exact-nonnegative-integer? x))

  ;; tempk-fn : Tempk -> ....

  (define/contract (tempk-fn x)

  (-> tempk? ....)

  ....)

• intervals: data from a range of values, e.g., [0,100]

• enumeration: data that is one of a list of possible values.

  Enumerations introduced in lecture 5.

  Example:

  ;; A TrafficLight is one of:

  (define RED-LIGHT "RED")

  (define GREEN-LIGHT "GREEN")

  (define YELLOW-LIGHT "YELLOW")

  ;; Interpretation: Represents possible colors of a traffic light

  Predicates for this kind of data should define smaller predicates for each of the values, when needed.

  (define (red-light? x) (string=? x RED-LIGHT))

  (define (green-light? x) (string=? x GREEN-LIGHT))

  (define (yellow-light? x) (string=? x YELLOW-LIGHT))

  ;; traffic-light? : Any -> Boolean

  ;; Returns TRUE if x is a TrafficLight

  (define (traffic-light? x)

  (or (red-light? x)

  (green-light? x)

  (yellow-light? x)))

  A template for this kind of data should have a cond, with one clause for each of the enumerates.

  ;; TEMPLATE for a function that processes TrafficLight data

  ;; trafficlight-fn: TrafficLight -> ???

  (define (trafficlight-fn light)

  (cond

  [(red-light? light) ....]

  [(green-light? light) ....]

  [(yellow-light? light) ....]))

• Itemizations introduced in lecture 5.

  itemization (this data definition generalizes enumerations): data whose values are from a list of possible other data definitions, e.g., either a string or number. The template for this kind of data should also use a cond, with one clause for each of the items.

• Compound Data introduced in lecture 6.

  compound data: data that combines multiple values from other data definitions, e.g., structs

  Example:

  ;; A Posn is a:

  (struct posn [x y])

  ;; where:

  ;; x : Integer - x coordinate of circle center in big-bang animation

  ;; y : Integer - y coordinate of circle center

  Compound data predicates should only do a shallow check, e.g., the Ball example’s predicate would be posn?.

  For compound data, the Template should extract the pieces of the compound data, which will later be combined with arithmetic.

  ;; TEMPLATE for posn-fn: Posn -> ???

  (define (posn-fn p)

  .... (posn-x p) ....

  .... (posn-y p) ....)

• Recursive Data introduced in lecture 8.

  recursive data: a data definition that references itself.

  This kind of data is typically an itemization with at least a base case and a recursive case, where the second is a compound data, e.g., a list.

  Example:

  ;; A ListofInt is one of:

  ;; - empty

  ;; - (cons Int ListofInt)

  ;; Interp: a list of CS class numbers

  For recursive data, the predicate should again be a shallow check, e.g., list?.

  The Template should include a recursive function call (in addition the template pieces for other kinds of data definitions, e.g. itemization and compound data).

  ;; TEMPLATE for list-fn : ListOfInt -> ???

  (define (list-fn lst)

  (cond

  [(empty? lst) ....]

  [(cons? lst) .... (first lst) ....

  .... (list-fn (rest lst)) ....]))

• Data Definitions with invariants introduced in lecture 14.

  Data definitions may specify additional invariants.

  Example: Binary Search Tree

• Intertwined data introduced in lecture 16.

  intertwined data: a set of data definitions that reference each other. Their templates should also reference each other’s template (when needed).

  Example:

  ;; An Sexpr is one of:

  ;; - Atom

  ;; - ProgTree

  ;; Interp: Represents syntax of Racket programs

  (define (sexpr-fn s)

  (cond

  ;; order of clauses may be re-arranged to put easier tests first

  [(list? s) .... (ptree-fn s) ....]

  [else      .... (atom-fn s)  ....]))

  ;; An Atom is one of:

  ;; - Number

  ;; - String

  ;; - Symbol

  ;; Interp: Represents Racket programs that are basic values

  (define (atom-fn a)

  (cond

  [(number? a) ....]

  [(string? a) ....]

  [else ....]))

  ;; A ProgTree is one of:

  ;; - empty

  ;; - (cons Sexpr ProgTree)

  ;; Interp: Represents non-atomic Racket programs

  (define (ptree-fn t)

  (cond

  [(empty? t) ....]

  [else .... (sexpr-fn (first t)) ....

  .... (ptree-fn (rest t))  ....]))

2 Function Design Recipe🔗

The recipe for designing a function requires the following steps.

1. Name of the function

2. Signature

   The Signature specifies the number of arguments and the types of the inputs and outputs.

   It should use the Data Definitions defined using the Data Design Recipe. New Data Definitions should be defined at this point, if needed.

3. Function Description or Purpose Statement

   This briefly describes, in English prose, what the "purpose" of the function.

   More specificly, it should explain what the function computes, and how it uses the input arguments to do so, but not the details of how it computes it.

4. Examples

   Similar to the Test-Driven Development (TDD) philosophy, these must be written before any code. (Note, however, that we have a separate Tests step after the Code step.)

   One way to think about the difference between Examples and Tests is:

   • Examples help explain what a function does. They are what you would want to see in documentation and tend to be simpler.

   • Tests help verify that a function is correct. They may be more complicated and, as a result, less human-readable.

   The number of Examples needed depends on how complicated a function is. For simple functions, one example may suffice. Larger functions may require more.

   In this course, Examples should be expressed as rackunit test cases, e.g., check-equal? so they may later be used to test the code.

5. Template step added in lecture 5.

   Choose Template

   Specifically, choose one argument from the signature that this function will "process". The code for this function must use the template for that kind of data. If there are multiple arguments, then choose one only.

6. Code

   If all previous steps have been followed, then this step should be straightforward (if you find yourself struggling at this step, it often means you did not properly do the previous The Design Recipe steps).

   Specifically, this step involves filling in the template with (a combination of nested) arithmetic expressions (it should not contain any statements.)

7. Tests

   Tests are written after the Code step and are in addition to the Examples.

   While we have already written the Examples as test cases, this step should add additional cases that are more complicated.

   They should follow basic software testing principles, e.g.,

   • maximum code coverage, and

   • sufficient testing of all the possible input values. One important aspect of this second point is coming up with corner cases.

   The number of Tests needed depends on how complicated a function is. For simple functions, two tests may suffice. More complicated functions may require more. For example, if the input is an itemization, then there should be at minimum one test for each of the itemizations.

   In this class, put Tests in a separate file.

8. Refactor

   Even after completing all the recipe steps, it’s rare for a program to be complete. At this point it’s common to refactor a program, if needed.

   We will talk about various possible refactorings this semester. One possibility is abstraction.

;; in a separate Tests file

(check-equal? (c2f 1) 33.8)

2.1 Accumulators🔗

Accumulators introduced in lecture 13.

Often, a function can process one argument, independently of previous function calls.

For example, we can use map to add one to every element of a list of numbers.

(map add1 (list 1 2 3)) ; => (list 2 3 4)

Sometimes, however, a function needs to remember additional information from other parts of the program, e.g., previous calls to the function.

In these cases, we need an accumulator.

Functions that use an accumulator must follow the accumulator template.

In particular, an accumulator must be specified with the following information

• name

• signature: specifies what kind of data the accumulator value is

• invariant: explains what the accumulator represents, in terms of a statement that must always be true

Summary of Accumulator Template

• Specify the accumulator (see above)

• In the original function, define an internal "helper" function that has the extra accumulator argument.

  If the signature is the same as the original function, then it does not need to be re-written.

  If the signature differs from the original function, then the new one should be specified.

• In the original function, call the "helper" function with an initial accumulator value.

Example

An example where an accumulator is needed is a max function that computes the maximum value in a list of numbers.

;; lst-max : NonEmptyList<Int> -> Int

;; Returns the largest value in a given non-empty list of ints

(define (lst-max lst0)

;; lst-max/a : List<Int> Int -> Int

;; max-so-far : Int

;; invariant: is the largest number in the list elements seen so far

;;  = (drop-right lst0 (length rst-lst))

(define (lst-max/a rst-lst max-so-far)

(cond

[(empty? rst-lst) max-so-far]

[else (lst-max/a (rest rst-lst)

(if (> (first rst-lst) max-so-far)

(first rst-lst)

max-so-far))]))

(lst-max/a (rest lst0) (first lst0)))

2.2 Multi-argument Templates🔗

Multi-argument templates introduced in lecture 18.

When a function has multiple argument, the design recipe usually calls for selecting one of the argument’s data definitions to use as the code template.

Sometimes, however, multiple arguments must be processed simultaneously. In these situations, the template for two data definitions must be combined.

Example

Here is a function (from our "CS450 Lang") that performs "addition" on either numbers or strings, in the same manner as JavaScript.

;; A Result is one of:

;; - Number

;; - String

(define (result? x) (or (number? x) (string? x)))

;; 450+: Result -> Result

;; Adds numbers or appends strings, following JS semantics.

(check-equal? (450+ 1 2) 3)

(check-equal? (450+ "1" "2") "12")

(check-equal? (450+ 1 "2") "12")

(define/contract (450+ x y)

(-> result? result?)

(cond

[(and (number? x) (number? y)) (+ x y)]

[else (string-append (res->str x) (res->str y))])) ; other cases combined

3 Iteration Recipe🔗

The Data Design Recipe and Function Design Recipe are not meant to be carried out only once. Instead, like all software development, the steps should be part of an iterative loop.

For example, while coming up with the signature of a function, you may realize that a new data definition is needed.

Or, writing a test may reveal a bug in a function’s code.

Thus, the recipe steps should be repeated as many times as needed in order to create a correct and readable program.

4 Abstraction Recipe🔗

Abstraction introduced in lecture 10 and lecture 11.

Abstraction is the process of creating a definition, e.g., a data definition or function, that contains a repeated pattern, with the goal of making the program easier to read and maintain by eliminating duplication.

Warning: Not all "repeated" code warrants creating an abstraction. In fact, creating a bad abstraction could be much more detrimental than simply leaving the duplicate code alone, so this step should be done with some caution.