6 Recipe for Itemizations

8.2

6 Recipe for Itemizations

Itemizations mix aspects of enumerations and intervals. Like enumerations they denote data which represents different alternatives, but at least one of the alternatives holds additional data. An example is information about the position of a train in a tunnel: Either there is no train in the tunnel (case 1) or there is a train at a cert–ain position in the tunnel (case 2). Case 2 has the train’s position as additional data.

Data definitions for itemizations typically use symbols to name each alternative as well as additional data for some of the cases (e.g., a number to represent position). The symbol and additional data are embedded in an array.

move-train.pf serves as the example for itemizations.

Further examples are rocket-launch.pf and rocket-launch-with-countdown.pf. These will be discussed in the lecture.

6.1 Steps

6.1.1 Problem statement

Write down the problem statement as a comment. The problem statement should answer these questions: What information needs to be represented? What should the function (to be implemented) do with the data? What cases need to be considered?

#<
A critical section of a railway track has a length of 10 km. Trains pass through the critical section in both directions. At most one train is allowed on this critical section at any one time. A control system is to be implemented that provides the position of a train in that section (if there is one) or an indication that there is no train in that section. Define a data definition for this information. Define a function that takes this data definition and advances the train's position by a given amount (in km). This may result in the train leaving the critical section.
>#

6.1.2 Data definition

Define how the domain information should be represented in the program or, vice versa, how to interpret the data (e.g., a number) as real-world information (e.g., a train position). Name each alternative as a symbol.

# enumeration of all possible alternatives
# :absent, :present

# the distance from the start of the critical section (in km)
no-train: (-> :Arr) { # constructor function
[:absent]
} fun

train-at: (position :Num -> :Arr) { # constructor function
[:present position]
} fun

A train can either be absent or present. If it is present, the position is given as a floating point number. Position 0.0 represents the start of the critical section, position 10.0 represents its end. The constructor functions simplify the creation of train values. There is one constructor function for each case: One for no train in the critical section (no-train) and one for the case of a train at a particular position in the critical section (train-at).

6.1.3 Function name

Conceive a descriptive function name. This should ideally be a short non-abbreviated name. You may revise the name and find a better name in the last step.

move-train:

6.1.4 Parameter list

Write down the function signature as a parameter list. The parameter names and types go left of the arrow (comma separated if you wish). The result type goes right of the arrow. The parameter names should ideally be descriptive, short, and non-abbreviated.

move-train: (train :Arr, amount :Num -> :Arr)

The function consumes two values (a train and an amount of movement). Positive amounts move the train towards the end of the critical section. Negative amounts move it towards the start. Note that this aspect is not captured in the data definition.

6.1.5 Function stub

Write down the function stub, returning an arbitrary value from the range of the function. Check that the code is parsed without error.

move-train: (train :Arr, amount :Num -> :Arr) {
no-train
} fun

6.1.6 Purpose statement

Write down a purpose statement (given as a comment). The purpose statement should describe what the function computes (not how it does that) and should mention the given inputs and produced result.

# Advances the train by the given amount. Consider the case
# that the train enters or leaves the critical section.

6.1.7 Examples and expected results

Write down examples with expected results in the test function. The test examples should cover corner cases (e.g., boundary values) and a typical case of each category (e.g. a value from the interior of an interval). Boolean functions should test positive and negative examples. You may already define constants for use in the implementation. Check that the code compiles. (Some tests will fail for the stub.)

The test examples handle several cases, such as the borders of the critical section, advancement in its interor, and entering and leaving the critical section.

Examples:

Advancing a train that is not in the critical section (no-train()) by 3.0 km results in a train that is still not in the critical section (no-train()).

Advancing a train that is at the start of the critical section (train-at(0.0)) by 0.0 km results in a train that is still at the start of the critical section (train-at(0.0)).

Advancing a train that is at position 1.0 km of the critical section (train-at(1.0)) by -1.0 km results in a train that is at the start of the critical section (train-at(0.0)).

etc.

Corresponding test cases in test function:

move-train-test: {
    1e-10 EPSILON!

    # absent trains, moving an absent train has no effect
    no-train 3.0 move-train, no-train, test=

    # borders
    0.0 train-at 0.0 move-train, 0.0 train-at, EPSILON, test~=
    10.0 train-at 0.0 move-train, 10.0 train-at, EPSILON, test~=
    1.0 train-at -1.0 move-train, 0.0 train-at, EPSILON, test~=
    9.0 train-at 1.0 move-train, 10.0 train-at, EPSILON, test~=

    # interior (both before and after advance)
    1.0 train-at 2.0 move-train, 3.0 train-at, EPSILON, test~=
    5.5 train-at 1.5 move-train, 7.0 train-at, EPSILON, test~=
    4.5 train-at -1.0 move-train, 3.5 train-at, EPSILON, test~=

    # leaving the section
    9.0 train-at 1.1 move-train, no-train, test=
    1.0 train-at -1.1 move-train, no-train, test=

    # entering the section
    -0.1 train-at 0.1 move-train, 0.0 train-at, EPSILON, test~=
    10.1 train-at -0.1 move-train, 10.0 train-at, EPSILON, test~=

    test-stats
} fun

move-train-test

6.1.8 Function body

Implement the function body. Put required helper functions on a "wish list." These will be implemented later.

How to identify the need for a helper function: A function should perform one well-defined task. A change in task or data type should be outsourced in a helper function. Moreover, a reusable subtask should be outsourced in a helper function (Don’t Repeat Yourself, DRY principle). It is often helpful to write a stub for the helper functions. This way you can already run the program.

# Advances the train by the given amount. Consider the case
# that the train enters or leaves the critical section.
move-train: (train :Arr, amount :Num -> :Arr) {
    { train .0 :absent = } {
        no-train
    }
    { train .0 :present = } {
        train .1 amount + new-pos!
        new-pos 0.0 <  new-pos 10.0 >  or {
            no-train
        } {
            new-pos train-at
        } if
    }
} cond-fun

The implementation handles the two cases of the train data. If a train is present, the new position is calculated. It is then checked whether the new position falls outside the critical section. If so, this corresponds to the absence of the train in the critical section. Otherwise a train representing presence at the new position is returned.

6.1.9 Testing

Check that the function body satisfies the tests. Correct the function body (and the tests). Look for opportunities to simplify the structure of the code. This typically requires multiple iterations. The function does not have side effects.

move-train.pf, line 48: Check passed.
move-train.pf, line 51: Check passed.
move-train.pf, line 52: Check passed.
move-train.pf, line 53: Check passed.
move-train.pf, line 54: Check passed.
move-train.pf, line 57: Check passed.
move-train.pf, line 58: Check passed.
move-train.pf, line 59: Check passed.
move-train.pf, line 62: Check passed.
move-train.pf, line 63: Check passed.
move-train.pf, line 66: Check passed.
move-train.pf, line 67: Check passed.
All 12 tests passed!

6.1.10 Review and revise

Review and revise the function name, the parameter names, and the purpose statement. Improve them if necessary. A design is not complete until it has a purpose statement and tests.

The above implementation should be improved. The start and end positions should be replaced by constants. Moreover, checking the case and accessing the train data should be abstracted into reusable helper functions. This allows changing the representation of the train data in the future without breaking functions that process train data.

0.0 START-POS!
10.0 END-POS!

absent?: (t) {
    t [:absent] =
} fun

present?: (t) {
   [{t arr?}
    {t length 2 =}
    {t .0 :present =}
    {t .1 num?}] and
} fun

position: (t :Arr) {
    t .1
} fun

# Advances the train by the given amount. Consider the case
# that the train enters or leaves the critical section.
move-train: (train :Arr, amount :Num -> :Arr) {
    { train absent? } {
        no-train
    }
    { train present? } {
        train position amount + new-pos!
        new-pos START-POS <  new-pos END-POS >  or {
            no-train
        } {
            new-pos train-at
        } if
    }
} cond-fun

If we are satisfied with the function, we can write a reusable template that can serve as a basis for future functions on this type.

fn-for-train: (train :Arr, amount :Num -> ...) {
    { train absent? } {
        ...
        train position ...
        no-train
        ... train-at
    }
    { train present? } {
        ...
        train position ...
        no-train
        ... train-at
    }
} cond-fun

6.2 Exercises

Write a function that takes two train values and tests whether they are in conflict with each other, i.e., whether they correspond to a state that is not allowed in the critical section.
Design a function that takes a train value and a percentage value p and checks whether the train is located in the first p% of the critical section.

← prev up next →

1	Introduction
2	Recipe for Atomic Data
3	Evaluating Functions Without Side-Effects
4	Recipe for Enumerations
5	Recipe for Intervals
6	Recipe for Itemizations
7	Recipe for Compound Data (Product Types)
8	Recipe for Variant Data (Sum Types)
9	Recipe for Self-Referential Data (Recursive Types)
10	Style