How to Code: Simple Data

Course notes for "How to Code: Simple Data" on edX.

Introduction

What makes it difficult to write programs?

  1. A poorly formed problem: What do we want our program to do?
  2. The program is too big to solve all at once: How do we break down a problem?

Systematic program design is the path from poorly-formed problem to well-structured solution.

Beginning Student Language

How to Design Functions (HtDF) Recipe

The HtDF recipe systematizes the design of a function. (Note: The recipe is going to make hard functions easier to design and easy functions a little harder to design.)

To design a single function:

  1. Signature, purpose, and stub
  2. Define examples, wrap each in check-expect
  3. Template and inventory
  4. Code the function body
  5. Test and debug until correct

The signature declares the type of data a function consumes and produces. Always use the most specific type.

The purpose is a one line description of what the function produces in terms of what it consumes.

The stub is a function definition that has the correct function name, has the correct number of parameters, and produces a dummy result of the correct type.

Examples help us understand what the function must do. Multiple examples illustrate behavior. Wrapping in check-expect means they will also serve as unit tests for the completed function.

The template is the outline of the function.

Use the previous recipe steps to code the function body.

How to Design Data (HtDD) Recipe

When we design data, we make decisions about all of the functions that operate on that data.

Data definitions explain how information is represented as data. We represent information in the problem domain using data in the program.

The first step of the recipe is to identify the inherent structure of the information.

  • Simple atomic data
  • Interval
  • Enumeration
  • Itemization
  • Compound data
  • References to other defined type
  • self-referential or mutually referential

Once that is done, a data definition consists of four or five elements:

  1. A possible structure definition
  2. A type comment that defines a new type name and describes how to form data of that type
  3. An interpretation that describes the correspondence between information and data
  4. One or more examples of the data
  5. A template for a 1 argument function operating on data of this type

How to Design Worlds (HtDW) Recipe

Compound Data

Self-Reference

Reference

Naturals

Helpers

Binary Search Trees