How to code: simple data

Note: The code below uses Racket programming language.

How to design functions

Function recipe

  1. Write signature, purpose and stub
  2. Write examples
  3. Write template and inventory
  4. Code the function body
  5. Test and debug

Signature, purpose, and stub

The signature is a one-line statement which specifies the types of arguments that the function inputs and outputs.

;; Number -> Number

The purpose explains what problem the function solves.

;; produces n times 2

The stub is a syntactically complete dummy function that produces value of the right type. It is used to run examples before the function is complete to reveal syntactic errors.

(define (double n) 0)

Examples

Examples help us to understand what the function is supposed to do. Examples should explore all the paths in the function and test boundary values. We can run examples after stub definition to check for syntactic errors in the code.

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

DrRacket can check examples automatically by applying check-expect function.

(check-expect (double 0) (* 0 2))
(check-expect (double 1) (* 1 2))
(check-expect (double 3) (* 3 2))

Template and inventory

Template and inventory are used to understand what the function has to work with. Inventory may be constant values that the function should use in computation. Once the template is done it should be commented out together with the stub.

(define (double n)
  (... n))

Function body

Now we are ready to complete the function body by filling in the template. Use the previous steps as a scaffolding to define the function body.

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

Test and debug

Run the program, test it, and debug until it produces the correct result. So far our code looks like this.

;; 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) ;stub

;(define (double n)    ;template
;  (... n))

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

Data definition

In a program we use data to represent information of a real-world problem. For example, we use integer values 0 and 1 to represent traffic lights red and yellow. Data definition helps us establish the relationship between information and data.

Data definition recipe

  1. Define data structure for compound data
  2. Define a new type name and show how to form data of this type
  3. Write interpretation note that establishes the correspondence of data to information that it represents
  4. Give one or more examples of the data
  5. Provide a template for one argument function to show how to operate on data of this type

The structure of information determines the kind of data definition to use which affects how we construct the templates. There are several types of data definition:

  • Simple atomic
  • Interval
  • Enumeration
  • Itemization
  • Compound
  • Composed
  • Self-referential

Simple atomic

Simple atomic data definition is used for only one thing, for example time from the start of the program, x-coordinate or name of a cat. At least one test case is required. The data could be distinct (fixed constant) or non-distinct (variable).

;; Time is Integer
;; interp. number of clock ticks since start of game

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

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

;; Template rules used:
;; Atomic non-distinct: Integer

For a given type TypeName the function template

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

will have the following body:

Atomic non-distinct Type check Body
Integer (integer? tn) (... tn)
String (string? tn) (... tn)
Boolean (boolean? tn) (... tn)
Image (image? tn) (... tn)
Atomic distinct Type check Body
"red" (string=? tn "red") (...)
false (false? tn) (...)
empty (empty? tn) (...)

Interval

Interval data definition is used for information that could be represented as a number within a range, for example Integer[0,10] is the range of integers from 0 to 10 inclusive. Test cases should include closed boundaries and midpoints.

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

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

;; Template rules used:
;; Atomic non-distinct: Integer[0, 10]

For a given type TypeName the function template

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

will have the following body:

Atomic non-distinct Type check Body
Integer[0, 10] (and (>= tn 0) (<= tn 10)) (... tn)

Enumeration

Enumeration data definition is used when the information could be represented in a fixed number of distinct items, such as colors or letter grades. Distinct means that data has a fixed number of values which do not vary. We normally use strings with this data type. It is not necessary to write interpretation note or examples. However, functions operating on enumerations should have at least as many tests as there are cases in the enumeration, unless the set is very large, in which case only a few tests are provided.

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

;; <examples are redundant for enumerations>

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

;; Template rules used:
;; One of: 3 cases
;;  - atomic distinct: "red"
;;  - atomic distinct: "yellow"
;;  - atomic distinct: "green"

For a given type TypeName the function template

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

will have the following body:

One of Type check Body
Enumeration (cond [Q A]) According to atomic type

Itemization

The itemization data definition is used when data has at least two subclasses, one of which is not a distinct item (contrary to enumeration). Functions operating on itemization should have at least as many tests as there are cases in the itemization. Relevant type tests should be done beforehand. It is possible to use else for the last type instead of checking the type.

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

(define B1 false)
(define B2 3) 

#;
(define (fn-for-bird b)
  (cond [(false? b) (...)]
        [(number? b) (... b)]))

;; Template rules used:
;; One of: 2 cases
;;  - atomic distinct: false
;;  - atomic non-distinct: Number

For a given type TypeName the function template

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

will have the following body:

One of Type check Body
Itemization (cond [Q A]) According to atomic type

Compound

Compound data definition is used when at least two values belong to each other and form a group. It is useful to have numerous examples to illustrate special cases.

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

(define B1 (make-ball 6 10))

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

;; Template rules used:
;; Compound: 2 fields
;; - atomic non-distinct: (ball-x b) is Number
;; - atomic non-distinct: (ball-x b) is Number

For a given type TypeName the function template

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

will have the following body:

Compound Type check Body
Ball (ball? b) (... ball-x b) (ball-y b))
Player (player? p) (... player-fn p) (player-ln p))

Composed

Composed data definition is used when data contains a reference to another data definitions. This is contrary to self-referencial data which has a reference to itself.

---assume Ball is as defined above---

(define-struct game (ball score))
;; Game is (make-game Ball Number) 

;; interp. the current ball and score of the game

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

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

;; Template rules used:
;; Composed: 2 fields
;; - compound: (make-ball Number Number)
;; - atomic non-distinct: (game-score g) is Number
;; Reference: ball field is Ball

For a given type TypeName the function template

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

will have the following body:

Composed Type check Body
Game (game? g) (... (fn-for-ball (game-ball g)) (game-score g))

Self-referential

Self-referential data definition is used when information is of arbitrary size, for example a list of items. The definition should have at least one base case and at least one case with recursion. When writing data and function examples always put the base case first because many functions don't work properly for the base case, such as an empty list. Additionally, there should be a test for a list with at least two elements. Natural recursion means there is a call to the function itself. This is contrary to the composed data which has a reference call to another data definition. We also call the list compound data because it consists of data that belongs together.

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

(define LOS1 empty)
(define LOS2 (cons "a" empty))
(define LOS3 (cons "b" (cons "c" empty)))

#;
(define (fn-for-los los)
  (cond [(empty? los) (...)]                   ;base case
        [else (... (first los)                 ;String
                   (fn-for-los (rest los)))])) ;natural recursion

;; Template rules used:
;; One of: 2 cases
;;  - atomic distinct: empty
;;  - compound: (cons String ListOfString)
;; Self-reference: (rest los) is ListOfString

For a given type TypeName the function template

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

will have the following body:

Self-reference Type check Body
ListOfString (cond [(empty? los) (...)]) [else (... (first los) (fn-for-los (rest los)))]

Mutually-referential

Mutual reference happens when one function refers to another helper function in its code. In the following example a helper function (fn-for-school (first los)) is referred from the function (fn-for-los los). Mutual recursion means there is a call to another helper function. When we code a function definition after the data definition, we might want to use a wish-list function for the call to (fn-for-school (first los)). We say that mutual recursion call is composed data because it refers to another data definition, contrary to self-referential data definition, elements of which do not refer to another data definition.

(define-struct school (name tuition))
;; School is (make-school String Natural)
;; interp. name is the school's name, tuition is student's tuition in USD

(define S1 (make-school "School 1" 27797))
(define S2 (make-school "School 2" 23300))
(define S3 (make-school "School 3" 28500))

(define (fn-for-school s)
  (... (school-name s)        ;String
       (school-tuition s)))   ;Natural

;; Template rules used:
;; Compound: 2 fields
;; - atomic non-distinct: (school-name s) is String
;; - atomic non-distinct: (school-tuition s) is Natural

;; ListOfSchool is one of:
;; - empty
;; - (cons School ListOfSchool)
;; interp. a list of schools
(define LOS1 empty)
(define LOS2 (cons S1 (cons S2 (cons S3 empty))))

(define (fn-for-los los)
  (cond [(empty? los) (...)]
        [else
         (... (fn-for-school (first los))  ;mutual recursion
              (fn-for-los (rest los)))]))  ;natural recursion

;; Template rules used:
;; One of: 2 cases
;; - atomic distinct: empty
;; - compound: (cons School ListOfSchool)
;; Composed: (first los) is School
;; Self-reference: (rest los) is ListOfSchool

For a given type TypeName the function template

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

will have the following body:

Reference Type check Body
ListOfSchool (cond [(empty? los) (...)]) [else (... (fn-for-school (first los)) (fn-for-los (rest los)))]

How to design worlds

The following procedure gives a recipe on how to design interactive programs. It is important to design a program that is easy to change. Having constants and clear traceability between code and analysis makes the code easy to change.

  1. Domain analysis
    1. Sketch program scenarios
    2. Identify constant information
    3. Identify changing information
    4. Identify module and options
  2. Build the actual program
    1. Add necessary modules
    2. Define constants
    3. Write data definitions
    4. Define functions: main and wish list
    5. Work through the wish list

A wish list is a to-do list of functions that should be done later. Each wish list function consists of a signature, purpose and stub together with !!! as a reminder that this is a wish list function definition.

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

;; My world program  (make this more specific)

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

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

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

;; WorldState -> WorldState
;; start the world with ...
(define (main ws)
  (big-bang ws
            (on-tick   next-ws)      ;WorldState -> WorldState
            (to-draw   render-ws)    ;WorldState -> Image
            (stop-when stop-ws)      ;WorldState -> Boolean
            (on-mouse  handle-mouse) ;WorldState Number Number MouseEvent -> WorldState
            (on-key    handle-key))) ;WorldState KeyEvent -> WorldState

;; WorldState -> WorldState
;; produce the next ...
;; !!!
(define (next ws) ...)

;; WorldState -> Image
;; render ...
;; !!!
(define (render ws) ...)

;; WorldState Number Number MouseEvent -> WorldState
;; Handle mouse event ...
;; !!!
(define (mouse-handle ws x y me)
  (cond [(mouse=? me "button-up") (... ws)]
        [else (... ws)]))

;; WorldState KeyEvent -> WorldState
;; Handle key event ...
;; !!!
(define (key-handle ws ke)
  (cond [(key=? ke " ") (... ws)]
        [else (... ws)]))

Function composition

We use function composition when we need to perform two or more different operations on the data. The standard template is not used for function composition. Instad, we introduce two or more helper functions to operate on the data and put them into the wish list, for example:

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

(define (arrange-images loi)
  (layout-images (sort-images loi)))

The tests for helper functions should appropriately test their respected function, while the tests for the composition of functions should the composition of the functions (it doesn't have to test again all the cases of the helper functions).

Reference: How to Code: Simple Data