7 Recipe for Compound Data (Product Types)
Compound data types aggregate potentially different kinds of data into a whole. PostFix uses arrays to represent values that consist of multiple components. The components in turn can be atomic or structured. As an example we use a 2-dimensional point with x- and y-coordinates as components. Compound data types are also called product types, because they form the Cartesian product of their components.
point.pf serves as the example for compound data.
7.1 Steps
7.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?
#<
Objects are located somewhere on a 2D plane. Design a function that computes the distance of the center of an object to the origin of the coordinate system.
>#
7.1.2 Data definition
Write how the domain information should be represented in the program, or, vice versa, write how to interpret the data (e.g., a pair of numbers) as real-world information (e.g., a point in 2D space). Write a data definition as an array with symbols as attribute names. Write a constructor for creating and initializing values of this kind.
# a 2D point has x- and y-coordinates, which are numbers
point: (x :Num, y :Num -> :Arr) { # constructor function
[x: x y: y]
} fun
The constructor function simplifies the creation of point values.
7.1.3 Function name
distance-to-origin:
7.1.4 Parameter list
distance-to-origin: (p :Arr -> :Num)
7.1.5 Function stub
distance-to-origin: (p :Arr -> :Num) {
0
} fun
7.1.6 Purpose statement
Write down a purpose statement (given as a comment).
# Computes the distance from the given point
# to the origin of the coordinate system.
7.1.7 Examples and expected results
Write down examples with expected results in the test method. Define any constants that the function needs. Check that the code is parsed correctly. (Some tests will fail for the stub.)
Examples:
For point (0,0) expect a distance to origin of 0.
For point (1,0) expect a distance to origin of 1.
For point (-1,0) expect a distance to origin of 1.
For point (3,4) expect a distance to origin of 5.
etc.
Corresponding test cases in test function:
distance-to-origin-test: {
1e-10 EPSILON!
0 0 point distance-to-origin, 0 EPSILON test~=
1 0 point distance-to-origin, 1 EPSILON test~=
-1 0 point distance-to-origin, 1 EPSILON test~=
3 4 point distance-to-origin, 5 EPSILON test~=
3 -4 point distance-to-origin, 5 EPSILON test~=
test-stats
} fun
distance-to-origin-test
The test function shows multiple aspects. First, the constructor function point creates point values. Second, because floating-point values are not exact, the test function test~= checks whether the function result is sufficiently close to the expected result. EPSILON is small positive constant close to zero. It specifies the allowed tolerance.
7.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.
# Computes the distance from the given point
# to the origin of the coordinate system.
distance-to-origin: (p :Arr -> :Num) {
p .:x p .:x * p .:y p .:y * + sqrt
} fun
The function inspects the components of the array to compute the result value. The dot operator (.) is used to access a component value (e.g., :x) of the compound value (p). The dot operator is an abbreviation: p .:x is equivalent to p :x get. It returns the value following the symbol.
7.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.
point.pf, line 28: Check passed.
point.pf, line 29: Check passed.
point.pf, line 30: Check passed.
point.pf, line 31: Check passed.
point.pf, line 32: Check passed.
All 5 tests passed!
7.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 purpose statement should describe what the function computes (not how it does the computation) and should mention the given inputs and produced result. The test examples should cover corner cases and a typical case.
The above implementation should be improved. Accessing the point components should be abstracted into reusable helper functions. This allows changing the representation of points in the future without breaking functions that use points.
point-x: (p :Arr -> :Num) {
p .:x
} fun
point-y: (p :Arr -> :Num) {
p .:y
} fun
# Computes the distance from the given point
# to the origin of the coordinate system.
distance-to-origin: (p :Arr -> :Num) {
p point-x p point-x * p point-y p point-y * + sqrt
} fun
For example, we may decide to change the representation of points to not use symbols as tags anymore, but just the actual data, so as to save memory. This saves memory, because an array that represents points now just consists of two rather than four components.
# a 2D point has x- and y-coordinates, which are numbers
point: (x :Num, y :Num -> :Arr) { # constructor function
[x y]
} fun
point-x: (p :Arr -> :Num) { # accessor function
p .0
} fun
point-y: (p :Arr -> :Num) { # accessor function
p .1
} fun
# Computes the distance from the given point
# to the origin of the coordinate system.
distance-to-origin: (p :Arr -> :Num) {
p point-x p point-x * p point-y p point-y * + sqrt
} fun
As you can see, the representation of a point has changed, but the distance-to-origin function, which uses points, has not been modified. This illustrates the power of abstraction.
7.2 Data Definitions for Compound Data
You do not have to write constructor and accessor functions yourself. The datadef operator automatically creates them as well as a type test function and a type symbol. Thus, with datadef it is possible to define new types. The type names can be used in parameter lists to precisely denote the type, whereas above we just used the type :Arr.
# a 2D point has x- and y-coordinates, which are numbers
Point: (x :Num, y :Num) datadef
# Computes the distance from the given point
# to the origin of the coordinate system.
distance-to-origin: (p :Point -> :Num) {
p point-x p point-x * p point-y p point-y * + sqrt
} fun
Point: (x :Num, y :Num) datadef
point: ( x :Num y :Num -> :Point ) {
[ :datadef :Point x y ]
} fun
point?: ( p :Obj -> :Bool ) {
[ { p arr? }
{ p length 2 >= }
{ p 0 get :datadef = }
{ p 1 get :Point = } ] and
} fun
point-x: ( p :Point -> :Num ) {
p 2 get
} fun
point-y: ( p :Point -> :Num ) {
p 3 get
} fun
7.3 Exercises
Design a function distance-points that computes the distance between two points.
Design a function circles-overlap that tests whether two circles overlap. Define a suitable data definition for circles.
Design a function and a data definition for points that are represented in polar coordinates. Search online for the definition of polar coordinates.