CPSC 203 HtDP Reference

This reference document is adapted from an old version of the CPSC 103 reference. It has been updated to use some modern notation, and to add some data types that we will encounter in CPSC 203.

For CPSC 203, these recipes and templates are meant as guidance only. You are not required to follow them in your code.

That said, the templates and particularly the recipes are an excellent way to structure your design and implementation of programs.

You can also use them to try to understand existing programs. When you encounter a program that you need to modify, your first step is definitely not to start editing the code. Instead:

Think about what data type(s) the program is manipulating. In particular, look for the compound and arbitrary-sized data types; furthermore, you are likely to encounter not just NamedTuple and list, but also classes, dictionaries, dataframes, and graphs. If the data types are not documented (either in an existing library or the code itself), write yourself some HtDD-like notes so you can better understand them.
Look for code patterns which resemble common templates. For example, when working through a list or dict, does the code directly access only certain elements by index / key (treating the data like a compound) or does the code iterate over all elements (treating the data like arbitrary-sized)?
Does the code introduce new templates / patterns that you haven’t seen before? If so, try to write down an abstract version of the pattern(s) so you can better understand them.
As you introduce your modifications:
- Make sure any new data types are documented (either in existing libraries or in the code itself). Just because the original programmer was lazy does not mean you should be too.
- Try to set things up so that you either stay entirely within the existing template / pattern, or introduce a separate template / pattern (likely in a new function or class). Doing a mixture of both will make it harder to judge the correctness of your modification, and harder for subsequent maintainers (including future you) to understand the implementation.
- If you need a mixture of both inside and outside the template / pattern, do them one at a time, test them, and be sure to document your design in the code / comments.

How to Design Functions Recipe

Write the stub, including the signature, purpose, and typecheck annotation.
Write examples.
Write or copy the template.
Code the function body.
Test and debug until correct.

How to Design Data Recipe

Identify the inherent structure of the information.

Write a data type definition with type comments where Python’s types are not specific enough.
Write an interpretation comment that describes the correspondence between information and data.
Write one or more examples of the data.
Write a template for a one-argument function operating on data of this type.

Data Definition Selection Guide

When the form of the information to be represented…	Use this data definition…
cannot be separated into meaningful pieces (is “atomic”)	Simple Atomic Data
is numbers within a certain range	Interval
consists of a fixed number of distinct items	Enumeration
is information in one of the other forms except for one special case	Optional
consists of two or more types of information that naturally belong together	Compound
is of arbitrary (unknown) size	Arbitrary-Sized

Basic Data Types

Simple Atomic Data

Simple atomic types are immutable.
This data type includes Python’s built-in types int, bool, str, float, complex.
- The number of bits required to store values of these types will in general depend on the hardware on which the program is running.
- For some types, such as str and int, the number of bits depends on the value being stored.
You would also use this pattern for more specialized (part of a Python library) but still simple data types (they represent a single piece of information). For example, the Numpy library for numerical computing (typically imported with the statement import numpy as np) includes data types which store a specific number of bits:
- Integers np.int8, np.int16, np.int32 and np.int64. These data types are stored with 8, 16, 32 and 64 bits respectively. An int with \(k\) bits can store any integer in the range \([ -2^{k-1}, +2^{k-1}-1 ]\).
- Unsigned integers np.uint8, np.uint16, np.uint32 and np.uint64. A uint with \(k\) bits can store any integer in the range \([ 0, +2^k-1 ]\).
- Floating point np.float16, np.float32 and np.float64. For more information on how floating point numbers are stored (and hence the range of values that they can represent), see Floating Point arithmetic.
- Complex floating point numbers np.complex64 and np.complex128.
- Boolean np.bool_, which is stored in 8 bits.
When you are working with a single piece of atomic data, you should not worry about the amount of storage that is used. It is only when you are working with large (arbitrary-sized) collections of data (for example, very large lists of integers) that you might want to use a data type that uses a fixed and restricted number of bits.

Definition

XXX = type

Template

return ...(x)

Interval

This data type is intended to be used for numerical atomic data which lies within a pre-specified range of values.
There are ways of enforcing the range, but like the type notation system in Python we generally just document the range in the code but do not explicitly enforce it.

Definition

XXX = int  # in range ...

Template

return ...(x)

Enumeration

Definition

from enum import Enum

XXX = Enum('XXX', ['A', 'B'])

Template

if x == XXX.A:
    return ...
elif x == XXX.B:
    return ...

Optional

Definition

new approach using modern union notation:

XXX = type | None

old approach from typing module:

from typing import Optional
XXX = Optional[type]

Template

if x is None:
    return ...
else:
    return ...(x)

Compound Data Types

Used when you have several data values which should be managed together.

NamedTuple

NamedTuples are immutable (they are a fancy version of a tuple).

Definition

Approach using class syntax (also allows default field values):

from typing import NamedTuple
class XXX(NamedTuple):
    a: type
    b: type

Approach using NamedTuple function:

from typing import NamedTuple

XXX = NamedTuple('XXX', [('a', type), ('b', type)])

Template

return ...(x.a, x.b)

DataClass

Dataclasses are mutable. If you want an immutable dataclass, use @dataclass(frozen = true) in the decorator before the class statement
Dataclasses can contain both data (“attributes” or “member data”) and functions (“methods” or “member functions”).

Definition

from dataclasses import dataclass

@dataclass
class XXX:
    a: type
    b: type

    def f(self, ...) -> ...:
        return ...(self.a, self.b, ...)

Template

return ...(x.a, x.b, x.f(...))

List and Dictionary

Sometimes you wish to extract individual elements of a list or dict using hardcoded indexes rather than treating those data structures as arbitrarily sized.
The definition of the data type is the same as for the arbitrary-sized case (see below) but the template is different (in other words, we use the data in a different manner).

List Template

return ...(x[0], x[1], x[2], ...)

Dictionary Template

return ...(x['a'], x['b'], x['c'], ...)

Arbitrary-Sized Data Types

Used when you have an amount of data which is not known in advance.

List

Lists are mutable.
Lists may contain elements of any type, but we encourage you to use lists containing a single type.
The elements of a list maintain their order.
Lists may contain multiple copies of a single item.
Elements of a list named x are indexed with the integer interval [0, len(x)].

Definition

Note: this data type name starts with a lower case l, and no need to import from typing module.

XXX = list[type]

Template

# description of the accumulator
acc = ...  # type: ...
for x in lox:
    acc = ...(x, acc)
return ...(acc)

Tuple

The tuple data type is basically an immutable list.

Definition

XXX = tuple[type]

Template

# description of the accumulator
acc = ...  # type: ...
for x in lox:
    acc = ...(x, acc)
return ...(acc)

Dictionary

TBA

Set

TBA