How to Design Functions (HtDF)

Design Recipes Overview

• Design recipes provide a systematic approach to program design, applicable to specific problem types.
• Core recipes include data-driven design, templating, and abstraction, with templating used in every data definition and function design.
• Part 1 of the course focuses on Core Recipes and Templating.
• A condensed version of the design recipes in Part 1 is available for reference.

How to Design Functions (HtDF)

• HtDF is a method for systematic function design, consisting of the following steps:
  • Signature, purpose, and stub
  • Define examples and wrap them in check-expect
  • Template and inventory
  • Code the function body
  • Test and debug until correct
• Each step builds upon the preceding ones, and the order can be adjusted except for writing the function definition first.
• Running the program frequently helps in identifying and fixing mistakes early.

Signature, Purpose, and Stub

• Write the function signature, a one-line purpose statement, and a function stub.
• A signature includes the type of each argument, followed by ->, and then the type of the result.
• A stub is a syntactically complete function definition that produces a value of the correct type.
• The stub allows running examples and checking for syntax errors before the function design is complete.

Define Examples

• Write at least one example of a function call and its expected result, with more examples needed for better understanding and testing.
• Examples help clarify the function's purpose and include boundary conditions and different behaviors.
• Enclose examples in check-expect for automatic testing in DrRacket.
• The examples can be run to check that parenthesis are balanced and that function names are not mispelled.

Template and Inventory

• A template provides a clear sense of what the function has to work with.
• Templates are produced by following rules on the Data Driven Templates web page.
• The template is copied from the data definition for the consumed type.
• The template for primitive data is (... x) where x is the name of the parameter to the function.
• Constant values that are likely to be useful can be added to the template body.

Code the Function Body

• Complete the function body by filling in the template, using the signature, purpose, examples, and template as guides.
• The signature indicates the types of parameters and the type of the data the function body must produce.
• The purpose describes what the function body must produce in English.
• The examples shows what the function body must produce.
• The template shows the raw material from which to work.

Test and Debug

• Run the program and ensure all tests pass, debugging until they do.
• Problems are fixed by following the "run early, run often" approach.

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.
• A data definition describes data formation, how to check if a data value satisfies the definition, how to represent information as data, and how to interpret data as information.
• The first step is to identify the inherent structure of the information.
• A data definition consists of a possible structure definition, a type comment, an interpretation, one or more examples, and a template.

Inherent Structure of Information

• The structure of information determines the type of data definition used, which influences the structure of templates and function examples.
• Different kinds of data definitions are used based on the form of information.

Simple Atomic Data

• Use simple atomic data when the information is atomic, like elapsed time or a name.

Intervals

• Use an interval when the information is numbers within a certain range.

Enumerations

• Use an enumeration for a fixed number of distinct items like colors or grades, typically using strings for the data.
• Data examples are often redundant.
• The template is formed according to the Data Driven Templates recipe.
• Functions should have as many tests as there are cases in the enumeration.
• For large enumerations, write one or two cases with a comment about the others.

Itemizations

• An itemization describes data with 2+ subclasses, where at least one is not a distinct item.
• The template is similar to enumerations: a cond with one clause per subclass.
• The answer part of the cond clause includes a call to a helper template if the subclass has its own data definition.
• There should be enough data examples to show how the type represents information.
• Functions should have as many tests as there are cases in the itemization.

Compound Data

• Use compound data when information consists of two or more items that naturally belong together.

References to Other Defined Types

• Use references to other defined types when a data type is naturally composed of different parts.

Self-Referential or Mutually Referential

• Use self or mutually referential data definitions when the size is arbitrary or unknown.

Data Driven Templates

• Data-driven templates are applied to functions that consume structured data.
• The template is based on the type comment/data definition of the input parameter.
• These templates represent structured data and guide the design of functions that process that data.

Atomic Non-Distinct

• Consists of atomic values that are not distinct in meaning.
• Applicable to data types like Number, String, Image, Boolean, and Posn.
• The template for this type is (... x), where x is the name of the parameter.

Atomic Distinct

• Consists of atomic values that are distinct in meaning and is always also an enumeration.
• Applicable to data types represented by a fixed set of distinct values, like color names or symbols.

One Of

• Combines different data types into a single structure, representing a choice between alternatives.
• Functions operating on "one-of" types are often designed using a cond expression.
• Each condition in cond checks for a specific case of the "one-of" type and processes the data accordingly.

List

• Represents an ordered collection of elements of the same type.
• Common in programs that need to handle multiple items, such as a list of numbers, strings, or custom data structures.
• Functions processing lists often use recursion to handle each element.

Two One-of Data

• This recipe applies when designing functions where two arguments have a one-of in their type comments.
• It involves creating a cross-product of type comments table to form tests and code the function body.
• The steps include signature, purpose, stub, forming the cross-product table, and simplifying the table to code the function body.

Function Composition

• This recipe is used when a function performs two or more distinct operations on the consumed data.
• Normal template is discarded, and the body has two or more function compositions.
• Tests should ensure the function calls all appropriate functions and composes them properly.

Backtracking Search

• The template includes functions for processing a node and its children.
• Includes a backtracking mechanism to try alternative paths and return the result if successful.

Generative Recursion

• The template consists of a base case and a recursive call with a modified input.
• trivial? checks for the base case, and next-problem generates the next problem to solve.

Accumulators

• Accumulators are used to preserve context, make the function tail-recursive, or maintain a work list.
• The basic recipe includes encapsulating the structural recursion template in an outer function and local. Type and examples are also useful.

Template Blending

• Template blending combines multiple templates that contribute to the structure of a function.
• Templates that can be used are: arbitrary-arity tree, generative recursion and backtracking search.

Abstraction From Examples

• Identify repetitive code fragments or functions.
• Arrange the functions to easily see them.
• Identify points of variance.
• Copy one function to make a new one, give it a general name, add parameters for each point of variance, and rename other parameters to be more abstract.

Abstraction From Type Comments

• Encapsulate mutually recursive functions in a single template with local.
• Replace each ... in the templates with a new parameter.
• Develop examples, abstract purpose, and signature from concrete examples.
• Generating a fold function for (listof X) as an example.

Using Abstract Functions

• The template for using a built-in abstract function includes specifying the input type and using the abstract function.