## Design Recipes in PostFix

Michael Rohs, October 21, 2018

The following design recipes and some of the given code examples are inspired by Matthias Felleisen et al.: How to Design Programs, Second Edition, Joe Politz: Design Recipes for Pyret Functions, and Gregor Kiczales: Introduction to Systematic Program Design.

### 1` `Introduction

#### 1.1` `From Problem Statement to Solution

The aim of the design recipes presented below is to help you to get from a textual problem statement to a well-organized and reliable solution. The design recipes are strongly inspired by How to Design Programs, Second Edition. The recipes presented below are available for different forms of data – from simple atomic data, like integer numbers, to arbitrary-length lists. The examples may seem simple and you may be tempted to solve them without following each of the steps presented below. We still urge you to follow these steps to learn and automate them and to be prepared to solve more complicated programming problems later on. Each step produces a well-defined intermediate product and makes it less likely that you stare at a blank screen, not knowing how to start the solution. The main steps in the design recipes are:

Problem statement

Data definition

Purpose statement and function stub

Examples

Implementation

Test and revision

In the problem statement step the programmer analyzes the problem, extracts its essence and represents it as a textual description. The problem statement may already be given, but even then you need to analyze it to extract useful information.

The data definition step is about choosing the data types that your program uses to represent the real-world information from the problem statement. Example data types are integer numbers, text, and Boolean values (true, false). The data definition expresses how you wish to represent real-world information as data in the program. An example is real-world temperatures measured in degrees Celsius are represented as numbers in the program. Conversely, the data definition may state how to interpret data items found in the program. For example, the interpretation of the number is degrees Celsius. The following figure illustrates the mediating role of the data definition. (Note that these notions of data and information differ from others, e.g., in information theory.)

The purpose statement describes the effect of the program on the input data. We here focus on the program as an algorithm or function that takes some kind of input data and produces some kind of result data. An example purpose statement would be: “Takes a temperature value in degrees Celsius and returns the corresponding value in degrees Fahrenheit.” A closely related step is to come up with a descriptive name for the algorithm, as well as the names and types of the parameters (input) and the type of the result (output). In the PostFix programming language this requires writing a function stub in a specific way. An example stub for a function that converts degrees Celsius to degrees Fahrenheit would be:

celsius-to-fahrenheit: (celsius :Int -> :Int) {

0

} fun

The function name (celsius-to-fahrenheit) is used to call this function, i.e., to apply it to a specific value. The parameter named celsius is an integer number. The result type is an integer number as well. This function maps an integer number to another integer number:

:Int -> :Int

The next step is to come up with examples of what you expect the algorithm (here: function) to do on a couple of inputs of your choice. For example, you may know that if you call celsius-to-fahrenheit with 0 °C, you expect a result of 32 °F (the conversion formula is °F = °C * 9 / 5 + 32):

Given: 0, expect: 32

Given: 10, expect: 50

Given -5, expect: 23

Given: 100, expect: 212

Coming up with these examples is trivial in this case, as the formula is known and can directly be written as one line in PostFix, but in general it very much helps to mentally prepare the subsequent implementation. The examples will also serve as test cases later on. The examples should be chosen in such a way that they cover typical cases and boundary cases. More on this later.

With the function header and several examples the implementation step is greatly simplified. The implementation defines how to compute the result from the parameters. Depending on the complexity of the data type it might be helpful to first write down a template of the implementation. For simple data types and problems, the implementation can often be directly written down. For the above example the formula can directly be translated to a sequence of words in PostFix.

celsius-to-fahrenheit: (celsius :Int -> :Int) {

celsius 9 * 5 i/ 32 +

} fun

The test and revision step involves checking whether the implementation produces the expected results. It also involves revising the function to correct or improve it. One (naive) option is to call the function on the examples, let the program produce the function results on the console, and then manually check them:

0 celsius-to-fahrenheit # expect: 32

10 celsius-to-fahrenheit # expect: 50

-5 celsius-to-fahrenheit # expect: 23

100 celsius-to-fahrenheit # expect: 212

The manual solution is problematic, because the programmer has to remember to check – after each change of the function – whether the results still correspond to the expected values. For the above implementation the results correspond to the expected values. The order in reversed, because the last result is on the top of the stack:

212

23

50

32

actual expected test=

0 celsius-to-fahrenheit 32 test=

celsius-to-fahrenheit.pf, line 11: Check passed.

celsius-to-fahrenheit.pf, line 11: Actual value 99 differs from expected value 32.

The last and final sub-step is to revise the function. If the function fails a test case, the need for a revision is obvious. But even if the function is correct, there might be an opportunity to implement it more clearly or to give it a more descriptive name.

The test cases should always remain in the implementation file and not be deleted after the implementation. That way, later changes can still be checked against the test cases. In fact, the test cases should go in their own function, named by appending -test to the function name, e.g., celsius-to-fahrenheit-test:

celsius-to-fahrenheit-test: {

0 celsius-to-fahrenheit 32 test=

10 celsius-to-fahrenheit 50 test=

-5 celsius-to-fahrenheit 23 test=

100 celsius-to-fahrenheit 212 test=

test-stats # print test statistics

} fun

celsius-to-fahrenheit-test

The # is a comment to human readers of the source code and does not have any effect in the program. The result of calling the test function is:

celsius-to-fahrenheit.pf, line 11: Check passed.

celsius-to-fahrenheit.pf, line 12: Check passed.

celsius-to-fahrenheit.pf, line 13: Check passed.

celsius-to-fahrenheit.pf, line 14: Check passed.

All 4 tests passed!

#### 1.2` `PostFix Language and Development Environment

PostFix is available as a Web-based development environment. A tutorial on the PostFix language is available as well.

#### 1.3` `Structure

The rest of this script is organized along increasingly complex kinds of data. In each week of the lecture we will cover a few design recipes and apply them to the respective kinds of data. Elements of the PostFix programming language will be introduced as necessary. By the end of the lecture you should have a good set of strategies to to solve simple programming problems and use a systematic approach to programming.

Learning to program – similar to learning a sport or a musical instrument – requires time and practice. Don’t let initial problems frustrate you. Learning to program is an excellent way to sharpen your analytical skills. Analyzing a problem, exploring solution possibilities, and evaluating a solution are skills that are necessary in many domains, not only in computer programming.

The general recipe presented above is adapted to different kinds of data. This script covers these specific recipes:

Recipe for Atomic Data

Recipe for Enumerations

Recipe for Intervals

Recipe for Itemizations

Recipe for Compound Data (Product Types)

Recipe for Variant Data (Sum Types)

### 2` `Recipe for Atomic Data

Atomic data is data that cannot be broken down further. Examples are integer and floating point numbers, Boolean values, and strings. It could be argued that text strings are not atomic as they can be further subdivided into characters. Yet we treat strings as atomic here.

wages.pf serves as the example for atomic data.

#### 2.1` `Steps

##### 2.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?

#<

Design a function that computes weekly wages with overtime from the number of hours worked. The hourly rate is 10 €/hour. Regular working time is 40 hours/week. Overtime is paid 150% of the normal rate of pay.

>#

##### 2.1.2` `Data definition

Write how the real-world information (also called domain information) should be represented in the program. Conversely, write how to interpret the data (e.g., a number) as real-world information (e.g., degrees Celsius). You may describe the interpretation in a comment.

# :Int represents hours worked

# :Int represents wage in cents

##### 2.1.3` `Function name

hours-to-wages:

##### 2.1.4` `Parameter list

hours-to-wages: (hours :Int -> :Int)

##### 2.1.5` `Function stub

hours-to-wages: (hours :Int -> :Int) {

0

} fun

##### 2.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.

# Computes the wage in cents given the number of hours worked.

##### 2.1.7` `Examples and expected results

Write down examples with expected results in the test function. Define any constants that the function needs. Check that the code is parsed without errors. (Some tests will fail for the stub.)

Examples:

For 0 hours worked, expect 0 cents.

For 20 hours worked, expect 20 * 1000 cents.

For 39 hours worked, expect 39 * 1000 cents.

For 40 hours worked, expect 40 * 1000 cents.

For 41 hours worked, expect 40 * 1000 + 1 * 1500 cents.

For 45 hours worked, expect 40 * 1000 + 5 * 1500 cents.

Corresponding test cases in test function:

hours-to-wages-test: {

0 hours-to-wages 0 test=

20 hours-to-wages 20 1000 * test=

39 hours-to-wages 39 1000 * test=

40 hours-to-wages 40 1000 * test=

41 hours-to-wages 40 1000 * 1 1500 * + test=

45 hours-to-wages 40 1000 * 5 1500 * + test=

test-stats

} fun

hours-to-wages-test

The test= function takes two arguments: The actual result and the expected result. Each check will report the line number on which it appears. This helps to locate failed tests in the source code.

Running the above tests on the stub produces:

wages.pf, line 6: Check passed.

wages.pf, line 7: Actual value 0 differs from expected value 20000.

wages.pf, line 8: Actual value 0 differs from expected value 39000.

wages.pf, line 9: Actual value 0 differs from expected value 40000.

wages.pf, line 10: Actual value 0 differs from expected value 41500.

wages.pf, line 11: Actual value 0 differs from expected value 47500.

5 of 6 tests failed.

##### 2.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.

The implementation of the hours-to-wages function does not need helper functions. However, it needs an if-operator to decide whether the working time includes overtime.

# Computes the wage in cents given the number of hours worked.

hours-to-wages: (hours :Int -> :Int) {

hours 40 <= {

hours 1000 *

} {

40 1000 * hours 40 - 1500 * +

} if

} fun

##### 2.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.

Running the tests on the implemented function produces:

wages.pf, line 14: Check passed.

wages.pf, line 15: Check passed.

wages.pf, line 16: Check passed.

wages.pf, line 17: Check passed.

wages.pf, line 18: Check passed.

wages.pf, line 19: Check passed.

All 6 tests passed!

##### 2.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 complete source file wages.pf now looks like this:

#<

Design a function that computes weekly wages with overtime

from the number of hours worked. The hourly rate is 10 €/hour.

Regular working time is 40 hours/week. Overtime is paid 150%

of the normal rate of pay.

>#

# Computes the wage in cents given the number of hours worked.

hours-to-wages: (hours :Int -> :Int) {

hours 40 <= {

hours 1000 *

} {

40 1000 * hours 40 - 1500 * +

} if

} fun

hours-to-wages-test: {

0 hours-to-wages 0 test=

20 hours-to-wages 20 1000 * test=

39 hours-to-wages 39 1000 * test=

40 hours-to-wages 40 1000 * test=

41 hours-to-wages 40 1000 * 1 1500 * + test=

45 hours-to-wages 40 1000 * 5 1500 * + test=

test-stats

} fun

hours-to-wages-test

#### 2.2` `Generalizing the Function

The example function as written above contains some concrete bits of information, such as the work hours per week, the regular hourly rate, and the hourly rate for overtime. The weekly work hours are repeated multiple times, which contradicts the “Don’t Repeat Yourself” (DRY) principle. Such information should be represented as constants or as parameters to the function. What is represented as a constant and what is represented as a parameter depends on the needs of the application domain.

One possibility is to extract all information as constants:

40 WEEKLY_HOURS! # regular work hours per week

1000 HOURLY_RATE_REGULAR! # in cents

1500 HOURLY_RATE_OVERTIME! # in cents

hours-to-wages: (hours :Int -> :Int) {

hours WEEKLY_HOURS <= {

hours HOURLY_RATE_REGULAR *

} {

WEEKLY_HOURS HOURLY_RATE_REGULAR *

hours WEEKLY_HOURS - HOURLY_RATE_OVERTIME * +

} if

} fun

Another possibility is to include all information as parameters:

hours-to-wages: (

weekly-hours :Int,

hourly-rate-regular :Int,

hourly-rate-overtime :Int,

hours-worked :Int

-> :Int)

{

hours-worked weekly-hours <= {

hours-worked hourly-rate-regular *

} {

weekly-hours hourly-rate-regular *

hours-worked weekly-hours - hourly-rate-overtime * +

} if

} fun

This makes the function more flexible, but also more difficult to use, because many arguments have to be provided. Typically only the hourly rate and hours worked change frequently (from worker to worker and for different weeks, respectively).

#### 2.3` `Exercises

Design a function has-overtime that computes whether or not the given number of work hours contains overtime.

Modify hours-to-wages such that the program outputs an error if hours is negative. The operator "message" err pushes an error object on the stack and stops execution.

### 3` `Evaluating Functions Without Side-Effects

A function is like a cloze (a text with _____ gaps). To complete a cloze you fill in the right words. To call a function you fill in parameters of the right type. When the function

hours-to-wages: (hours :Int -> :Int) {

hours 40 <= {

hours 10 *

} {

40 10 * hours 40 - 15 * +

} if

} fun

is called, the parameter hours is replaced by an actual integer number and then the body of the function is evaluated to an integer number. For example, the step by step evaluation of 45 hours-to-wages looks like this:

45 hours-to-wages

Substitute the call with the function body, in which the parameter hours has been replaced with the argument value (45).

=> 45 40 <= {

45 10 *

} {

40 10 * 45 40 - 15 * +

} if

Evaluate the condition (45 40 <=) of the if-operator (to false).

=> false {

45 10 *

} {

40 10 * 45 40 - 15 * +

} if

Because the condition is false, replace the evaluated if-operator with its else-part.

=> 40 10 * 45 40 - 15 * +

Evaluate left multiplication operator.

=> 400 45 40 - 15 * +

Evaluate minus operator.

=> 400 5 15 * +

Evaluate right multiplication operator.

=> 400 75 +

Evaluate plus operator.

=> 475

For this particular function, the evaluation can be understood in analogy to simplifying an algebraic expression. Unfortunately, this is not always the case. Some functions have so-called side-effects, e.g., because they produce some output in addition to returning a value.

### 4` `Recipe for Enumerations

An enumeration type can represent one of a fixed number of distinct values. Examples of information of this type include gender (male, female), music genres (pop, rock, classic, jazz, etc.), continents (Europe, Asia, Africa, etc.), and traffic light colors (red, green, yellow). Each individual enumerated value is a distinct value and does not carry any additional data. In PostFix, such types can be represented as symbols. Symbols are names that may or may not be linked to a value.

traffic-light.pf serves as the example for enumerations.

#### 4.1` `Steps

##### 4.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?

#<

Design a function that returns the next color of a traffic light given the current color of the traffic light.

>#

##### 4.1.2` `Data definition

Write how the domain information should be represented in the program. Conversely, write how to interpret the data (e.g., a number) as real-world information (e.g., a traffic light state). Write the data definition as the list of required symbols.

# enumeration of TrafficLight states:

# :red, :red-yellow, :green, :yellow

The colon : at the beginning or end of the symbol is necessary. Without the colon, PostFix tries to lookup the name in the dictionary. With the colon, the symbol stands for itself.

##### 4.1.3` `Function name

traffic-light-next:

##### 4.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.

traffic-light-next: (traffic-light :Sym -> :Sym)

Remember, the purpose statement says that we need a function that returns the next color of the traffic light, given its current color.

##### 4.1.5` `Function stub

traffic-light-next: (color :Sym -> :Sym) {

:red

} fun

This function can already be called, but it gives us a traffic light that is constantly red – how frustrating.

##### 4.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.

# Produces the next color of a traffic light

# given the current color of the traffic light.

##### 4.1.7` `Examples and expected results

Write down examples with expected results in the test function. Define any constants that the function needs. Check that the code is parsed without errors. (Some tests will fail for the stub.)

Examples:

If the traffic light is :red, expect :red-yellow as the next state.

If the traffic light is :red-yellow, expect :green as the next state.

If the traffic light is :green, expect :yellow as the next state.

If the traffic light is :yellow, expect :red as the next state.

Corresponding test cases in test function:

traffic-light-next-test: {

:red traffic-light-next :red-yellow test=

:red-yellow traffic-light-next :green test=

:green traffic-light-next :yellow test=

:yellow traffic-light-next :red test=

test-stats

} fun

traffic-light-next-test

Running the above tests on the stub (which always returns :red) produces:

traffic-light.pf, line 14: Actual value :red differs from expected value :red-yellow.

traffic-light.pf, line 15: Actual value :red differs from expected value :green.

traffic-light.pf, line 16: Actual value :red differs from expected value :yellow.

traffic-light.pf, line 17: Check passed.

3 of 4 tests failed.

##### 4.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.

The implementation of the traffic-light-next function does not need helper functions:

# Produces the next color of a traffic light

# given the current color of the traffic light.

traffic-light-next: (color :Sym -> :Sym) {

color :red = {

:red-yellow

} {

color :red-yellow = {

:green

} {

color :green = {

:yellow

} {

:red

} if

} if

} if

} fun

##### 4.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.

Running the tests on the implemented function produces:

traffic-light.pf, line 37: Check passed.

traffic-light.pf, line 38: Check passed.

traffic-light.pf, line 39: Check passed.

traffic-light.pf, line 40: Check passed.

All 4 tests passed!

##### 4.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.

In the given situation, the cond operator is a good alternative to the nested if operators.

traffic-light-next: (color :Sym -> :Sym) {

{

{ color :red = } { :red-yellow }

{ color :red-yellow = } { :green }

{ color :green = } { :yellow }

{ color :yellow = } { :red }

} cond

} fun

This can further be simplified using the cond-fun operator. It is a conditional nested in a function definition operator.

traffic-light-next: (color :Sym -> :Sym) {

{ color :red = } { :red-yellow }

{ color :red-yellow = } { :green }

{ color :green = } { :yellow }

{ color :yellow = } { :red }

} cond-fun

The complete program now looks like this:

#<

Design a function that returns the next color of a traffic light

given the current color of the traffic light.

>#

# enumeration of traffic light states:

# :red :red-yellow :green :yellow

traffic-light-next: (color :Sym -> :Sym) {

{ color :red = } { :red-yellow }

{ color :red-yellow = } { :green }

{ color :green = } { :yellow }

{ color :yellow = } { :red }

} cond-fun

traffic-light-next-test: {

:red traffic-light-next :red-yellow test=

:red-yellow traffic-light-next :green test=

:green traffic-light-next :yellow test=

:yellow traffic-light-next :red test=

test-stats

} fun

traffic-light-next-test

Given this information, we can write a reusable template for functions that can handle traffic lights:

traffic-light-fn...: (color :Sym -> ...) {

{ color :red = } { ... }

{ color :red-yellow = } { ... }

{ color :green = } { ... }

{ color :yellow = } { ... }

} cond-fun

This template may be copied, pasted, and adapted for new functions that operate on this data type.

#### 4.2` `Exercises

Design a function continent-next that computes the next continent for a sailing ship. The route of the sailing ship is influenced by the wind direction. The next continent depends on the current continent and the wind direction (the direction from which the wind originates). Among others, the following relations hold: Europe –northwind–> Africa, Europe –westwind–> Asia, Asia –eastwind–> Europe. Complete these relations using a world map. To simplify the exercise assume that the Americas and Australia do not exist, and that if a ship reaches Antarctica it sinks. Assume that the only wind directions (directions from which the wind originates) are east, west, north, and south, and that they do not change during a single journey of a sailing ship from one continent to another. Use suitable enumerations.

### 5` `Recipe for Intervals

When the domain information that needs to be represented in the program consists of one or more ranges of numbers, then the data definition is concerned with handling intervals. An example would be a taxation scheme in which there is no taxation for goods below 1000 €, moderate taxation between 1 k€ – 10 k€, and high taxation for goods above 10 k€. When dealing with intervals special care needs to be taken to treat the boundary cases correctly. In the example above, is a product of 1000 € still without taxation or does it fall in the next interval? Boundaries can be represented precisely in this way: [0, 1000), [1000, 10000), [10000, inf), where brackets [ and ] denote inclusive boundaries and parentheses ( and ) denote exclusive boundaries: 1000 does not belong to the interval [0, 1000), but 0 does.

Data definitions for intervals typically use symbols to name each interval as well as constants to define the boundaries of the intervals.

tax.pf serves as the example for intervals.t

#### 5.1` `Steps

##### 5.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 fictitious country has decided to introduce a three-stage sales tax. Cheap items below 1 k€ are not taxed. Goods of more than 10 k€ are taxed at 10%. Items in between are taxed at a rate of 5%. Give a data definition and define a function that computes the amount of tax for a given item price.

>#

##### 5.1.2` `Data definition

# enumeration of tax stages:

# :no-tax, :low-tax, :high-tax

# :Int represents Euro

1000 :LOW-TAX-BOUNDARY! # interpret.: price in Euro

10000 :HIGH-TAX-BOUNDARY! # interpret.: price in Euro

##### 5.1.3` `Function name

sales-tax:

##### 5.1.4` `Parameter list

sales-tax: (price :Int -> :Int)

##### 5.1.5` `Function stub

sales-tax: (price :Int -> :Int) {

0

} fun

##### 5.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.

# Returns the amount of tax for the given price.

##### 5.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 codeis parsed without errors. (Some tests will fail for the stub.)

Examples:

For a price of 0 € expect a sales tax of 0 €.

For a price of 537 € expect a sales tax of 0 €.

For a price of 1000 € expect a sales tax of 50 €.

For a price of 1282 € expect a sales tax of 64 €.

For a price of 10000 € expect a sales tax of 1000 €.

For a price of 12017 € expect a sales tax of 1202 €.

Corresponding test cases in test function:

sales-tax-test: {

0 sales-tax, 0, test=

537 sales-tax, 0, test=

1000 sales-tax, 1000 0.05 * round, test=

1282 sales-tax, 1282 0.05 * round, test=

10000 sales-tax, 10000 0.10 * round, test=

12017 sales-tax, 12017 0.10 * round, test=

} fun

sales-tax-test

The tax values are rounded and converted to integer numbers, which represent whole Euros.

Note that the test cases cover each of the boundary values of the intervals, and at least one value from the interior of each interval.

##### 5.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.

# Returns the amount of tax for the given price.

sales-tax: (price :Int -> :Int) { # :Int represents whole Euro

{ 0 price <= price 1000 < and } { # :no-tax interval

0

}

{ 1000 price <= price 10000 < and } { # :low-tax interval

price 0.05 * round

}

{ price 10000 >= } { # :high-tax interval

price 0.10 * round

}

{ true } { # error: if this line is reached then price < 0

"sales-tax, error: negative price" err

}

} cond-fun

The implementation reflects the structure of the data. As specified in the enumeration there are three cases: :no-tax, :low-tax, and :high-tax. These three cases correspond to three intervals: [0, 1000), [1000, 10000), and [1000, inf). For each interval there is a condition that matches one of the intervals. When formulating the conditions care has to be taken to handle the boundary values correctly. In addition, there is an error case for negative prices. Since Euro is represented as integer number, a negative number could be provided, which could lead to an error.

##### 5.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 given implementation satisfies all test examples:

tax.pf, line 36: Check passed.

tax.pf, line 37: Check passed.

tax.pf, line 38: Check passed.

tax.pf, line 39: Check passed.

tax.pf, line 40: Check passed.

tax.pf, line 41: Check passed.

All 6 tests passed!

##### 5.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.

0.05 LOW-TAX-RATE!

0.10 HIGH-TAX-RATE!

# Returns the amount of tax for the given price.

sales-tax: (price :Int -> :Int) { # :Int represents whole Euro

{ price 0 < } { # error

"sales-tax, error: negative price" err

}

{ price LOW-TAX-BOUNDARY < } {

0

}

{ price HIGH-TAX-BOUNDARY < } {

price LOW-TAX-RATE * round

}

{ true } {

price HIGH-TAX-RATE * round

}

} cond-fun

Domain knowledge might suggest to include a constant for the low-taxation category as well. There could be a revision of the taxation system, in which the first interval of [0, 1000) Euro becomes subject to a small taxation rate as well. Moreover, an additional interval for higher-priced items could be introduced, which would require adding a case. It is up to the programmer’s judgment to decide how far the generalization should go, because this can come at a cost. For example, introducing another constant for the first interval could increase the effort to read the code.

If we are satisfied with the function, we can write a reusable template, which can serve as a basis when implementing functions related to this taxation scheme in the future.

0.05 LOW-TAX-RATE!

0.10 HIGH-TAX-RATE!

fn-for-tax: (price :Int -> ...) { # :Int represents whole Euro

{ price 0 < } { # error

"sales-tax, error: negative price" err

}

{ price LOW-TAX-BOUNDARY < } {

...

}

{ price HIGH-TAX-BOUNDARY < } {

...

}

{ true } {

...

}

} cond-fun

This template can be adapted for new functions that operate on this data type.

#### 5.2` `Exercises

A taxation rate of 1.5% is introduced for items below 1000 €. Modify the sales-tax function to reflect this change.

A revision of the taxation system introduces a linearly increasing taxation rate for the middle interval (1 k€ – 10 k€). As before, the taxation rate is 5% at 1 k€ and 10% at 10 k€, but is linearly interpolated in between. Modify the sales-tax function to reflect this change.

### 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

#<

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

# 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

move-train:

##### 6.1.4` `Parameter list

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

##### 6.1.5` `Function stub

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

no-train

} fun

##### 6.1.6` `Purpose statement

# 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

# 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.

### 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

#<

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

# 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

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.

### 8` `Recipe for Variant Data (Sum Types)

Sometimes, data can take on one of different variants. An example are points that may be represented either in Euclidean coordinates (x, y) or in polar coordinates (theta, magnitude). In the latter case, magnitude specifies the distance from the origin of the coordinate system and theta specifies the direction with respect to the positive x-axis. So, (0°, 3) is equivalent to (3, 0) in Euclidean coordinates, (90°, 2) is equivalent to (0, 2), and (45°, sqrt(2)) is equivalent to (1, 1).

A data type that can represent one of different choices is called a variant, a (tagged) union, or a sum type. In PostFix, such types are represented as multiple arrays, one for each variant.

point-euclid-polar.pf serves as the example for variant data.

#### 8.1` `Steps

##### 8.1.1` `Problem statement

#<

Points on the 2D plane may be given either in Euclidean coordinates or in polar coordinates. Design a function that computes the distance of such a point to the origin of the coordinate system.

>#

##### 8.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.

# enumeration of point variants:

# :euclid, :polar

euclid: (x :Num, y :Num -> :Arr) { # constructor function

[euclid: x: x y: y]

} fun

euclid?: (e :Obj -> :Bool) { # detector function

[ { e arr? }

{ e length 5 = }

{ e 0 get :euclid = } ] and

} fun

euclid-x: (e :Arr -> :Num) { # accessor function

e .:x

} fun

euclid-y: (e :Arr -> :Num) { # accessor function

e .:y

} fun

polar: (theta :Num, magnitude :Num -> :Arr) { # constructor function

[polar: theta: theta magnitude: magnitude]

} fun

polar?: (p :Obj -> :Bool) { # detector function

[ { p arr? }

{ p length 5 = }

{ p 0 get :polar = } ] and

} fun

polar-theta: (p :Arr -> :Num) { # accessor function

p .:theta

} fun

polar-magnitude: (p :Arr -> :Num) { # accessor function

p .:magnitude

} fun

##### 8.1.3` `Function name

distance-to-origin:

##### 8.1.4` `Parameter list

distance-to-origin: (p :Arr -> :Num)

##### 8.1.5` `Function stub

distance-to-origin: (p :Arr -> :Num) {

0

} fun

##### 8.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.

##### 8.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.)

distance-to-origin-test: {

1e-10 EPSILON!

# test cases for polar variant

0 0 polar distance-to-origin, 0, EPSILON test~=

0 1 polar distance-to-origin, 1, EPSILON test~=

2.3 2 polar distance-to-origin, 2, EPSILON test~=

# test cases for Euclidean variant

0 -2 euclid distance-to-origin, 2, EPSILON test~=

2 0 euclid distance-to-origin, 2, EPSILON test~=

1 1 euclid distance-to-origin, 2 sqrt, EPSILON test~=

test-stats

} fun

distance-to-origin-test

It is important to generate test cases for each variant.

##### 8.1.8` `Function body

The implementation of the example function does not need helper functions.

# Computes the distance from the given point

# to the origin of the coordinate system.

distance-to-origin: (p :Arr -> :Num) {

{ p euclid? } {

p euclid-x p euclid-x *

p euclid-y p euclid-y * + sqrt

}

{ p polar? } {

p polar-magnitude

}

} cond-fun

The function takes different strategies to compute the distance of the point to the root, depending on whether the point is given in Euclidean or in polar coordinates. The detector functions are used to distinguish these cases.

##### 8.1.9` `Testing

point-euclid-polar.pf, line 78: Check passed.

point-euclid-polar.pf, line 79: Check passed.

point-euclid-polar.pf, line 80: Check passed.

point-euclid-polar.pf, line 83: Check passed.

point-euclid-polar.pf, line 84: Check passed.

point-euclid-polar.pf, line 85: Check passed.

All 6 tests passed!

##### 8.1.10` `Review and revise

Given the implementation, we can write a reusable template for functions that handle points:

fn-for-points: (p :Arr -> ...) {

{ p euclid? } {

p euclid-x ...

p euclid-y ...

}

{ p polar? } {

p polar-magnitude ...

p polar-theta ...

}

} cond-fun

#### 8.2` `Data Definitions for Variant Data

You do not have to write constructor, detector, and accessor functions yourself. The datadef operator automatically creates them as well as type symbols for each variant and the overall type itself. 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.

Point: {

Euclid: (x :Num, y :Num)

Polar: (theta :Num, magnitude :Num)

} datadef

# Computes the distance from the given point

# to the origin of the coordinate system.

distance-to-origin: (p :Point -> :Num) {

{ p euclid? } {

p euclid-x p euclid-x *

p euclid-y p euclid-y * + sqrt

}

{ p polar? } {

p polar-magnitude

}

} cond-fun

Point: {

Euclid: (x :Num, y :Num)

Polar: (theta :Num, magnitude :Num)

} datadef

point?: ( p :Obj -> :Bool ) {

[ { p euclid? } { p polar? } ] or

} fun

euclid: ( x :Num y :Num -> :Euclid ) {

[ :datadef :Euclid x y ]

} fun

euclid?: ( p :Obj -> :Bool ) {

[ { p arr? }

{ p length 2 >= }

{ p 0 get :datadef = }

{ p 1 get :Euclid = } ] and

} fun

euclid-x: ( p :Euclid -> :Num ) {

p 2 get

} fun

euclid-y: ( p :Euclid -> :Num ) {

p 3 get

} fun

polar: ( theta :Num magnitude :Num -> :Polar ) {

[ :datadef :Polar theta magnitude ]

} fun

polar?: ( p :Obj -> :Bool ) {

[ { p arr? }

{ p length 2 >= }

{ p 0 get :datadef = }

{ p 1 get :Polar = } ] and

} fun

polar-theta: ( p :Polar -> :Num ) {

p 2 get

} fun

polar-magnitude: ( p :Polar -> :Num ) {

p 3 get

} fun

#### 8.3` `Exercises

Write a data definition for a type that can represent one of miles or kilometers. Use this data definition to represent distances. Design a function convert-distance that converts a distance to the other unit.

Write a data definition for a type Shape that can represent one of a rectangle, a circle, or an equilateral triangle. Write a function that computes the area of a shape.

### 9` `Recipe for Self-Referential Data (Recursive Types)

Some information has a recursive (self-referential) structure. For example, a natural number is either zero or the successor of a predecessor, which is also a natural number. An ancestor is a parent or the ancestor of a parent. A descendant is a child or the descendant of a child.

Such information can be represented by an instance of a self-referential data type: The type to be defined is mentioned in its definition. Recursive types are a special case of variant types: At least one variant is self-referential and at least one variant is not self-referential. As we shall see, self-referential data can represent information of arbitrary size.

Examples include lists and trees. A list is either empty (variant 1, not self-referential) or a value followed by a shorter list (variant 2, self-referential). A binary tree is either empty (variant 1, not self-referential) or a node with a left binary tree, a value, and a right binary tree (variant 2, two self-references).

PostFix uses arrays to represent self-referential data. The datadef operator allows to describe recursive data types. The operator also generates the necessary constructors, detectors (variant tests), and accessors.

list-sum.pf serves as the example for self-referential data.

#### 9.1` `Steps

##### 9.1.1` `Problem statement

#<

Computes the sum of the values of a list of integer numbers.

>#

##### 9.1.2` `Data definition

Write how the domain information should be represented in the program, or, vice versa, write how to interpret the data as real-world information.

Determine and name the variants. Determine the self-references. At least one variant must not be self-referential (base case) and at least one variant has to be self-referential (recursive case). For a list of numbers there are two variants. The variant that is not self-referential, which we call Null, is the empty list. (The name empty is already taken in PostFix.) The self-referential variant, which we call Cons, is an integer number followed by a list. Cons stands for construct, as it constructs a longer list by prepending a number to a shorter list. Determine the data types that occur in the different variants.

Null: no additional data in this variant, base case

Cons: two data items in this variant: value is an integer number, rest is a self-reference to the List type

Write the data definition:

List: {

Null: () # empty list

Cons: (value :Int, rest :List) # value, followed by list

} datadef

Note that the Cons variant could also be defined as Cons: (front :List, value :Int), in which case the value would be appended at the end of the existing list and not prepended in front of the existing list as in the data definition above.

##### 9.1.3` `Example Values for Data Definition

Create at least one example value per variant in the data definition. Create examples that use the self-referential variant(s) more than once, i.e., create examples of different lengths. These value examples are later used in the functional examples and expected results.

null # variant 1

10 null cons # variant 2 and then variant 1

10 20 null cons cons # variants 2, then variant 2, then variant 1

10 20 30 null cons cons cons # variants 2, 2, 2, and finally 1

##### 9.1.4` `Function name

list-sum:

##### 9.1.5` `Parameter list

list-sum: (a :List -> :Int)

##### 9.1.6` `Function stub

list-sum: (a :List -> :Int) {

0

} fun

##### 9.1.7` `Purpose statement

Briefly describes what the function does. Do not try to explain how. The purpose statement should ideally be a single sentence. However, multiple sentences may be necessary.

# Computes the sum of the values of the list.

##### 9.1.8` `Examples and expected results

Write down several examples with expected results in the test function. Write at least one example per variant in the data definition. Use the example values created above. Check that the code is parsed correctly. (Some tests will fail for the stub.)

list-sum-test: {

null list-sum 0 test=

10 null cons list-sum 10 test=

10 20 null cons cons list-sum 30 test=

10 20 30 null cons cons cons list-sum 60 test=

test-stats

} fun

list-sum-test

##### 9.1.9` `Template

Translate the data definition into a function template. Use the cond or cond-fun operators with suitable condition-action pairs. Write one condition per variant using the detector function for the respective variant. In the corresponding actions add the accessor functions. If the variant is self-referential, add one recursive call per self-reference.

The translation of the data definition of the list of integer numbers into a function template is:

list-sum: (a :List -> :Int) {

{ a null? } { ... }

{ a cons? } {

... a cons-value ...

... a cons-rest list-sum ...

}

} cond-fun

##### 9.1.10` `Function body

Combine the expressions in the template to obtain the expected results according to the test examples. Start with filling the non-recursive cases. For each such case there should be an example with an expected result. If not, add such examples to the test function. For the self-referential cases things are a bit more difficult. Use the recursive call as if the function had already been implemented and did what the purpose statement says. A meaningful purpose statement is thus especially important for recursive functions. The assumption that the recursive call works correctly (on the rest of the list without the first value) is the induction hypothesis. This assumption has also been termed the "leap of faith". Using the call in the implementation (and combining it with the first value) is the induction step. For the non-recursive base case we know that the function returns the right result. Do not try to mentally descend into the recursion as this typically does not work out.

# Computes the sum of the values of the list.

list-sum: (a :List -> :Int) {

{ a null? } { 0 }

{ a cons? } {

a cons-value

a cons-rest list-sum +

}

} cond-fun

The function uses the result of the recursive call (which is correct according to the induction hypothesis) and combines the result by adding it to the first value of the list (induction step).

##### 9.1.11` `Testing

list-sum.pf, line 16: Check passed.

list-sum.pf, line 17: Check passed.

list-sum.pf, line 18: Check passed.

list-sum.pf, line 19: Check passed.

All 4 tests passed!

##### 9.1.12` `Review and revise

#### 9.2` `Exercises

Write a data definition for a list of female ancestors. Each value is the name, year of birth, and year of death. Write a function that computes the average age of a list of ancestors.

Write a data definition for a binary tree of parents. Each value is the name of the father and the name of the mother. Write a function that computes the most frequent name.

### 10` `Style

Style and naming conventions can be a controversial issue. The primary goal of establishing naming conventions is to make code easier to read. Source code is typically more often read than written. Programs should be written as clearly and consistently as possible. Consistent use of naming conventions and consistent layout of source code is a sign of high-quality work. A few recommendations follow.

#### 10.1` `Naming Conventions

Use short, common, and non-abbreviated names.

Use abbreviations sparingly.

Use very short variable names only as local variables, and if their meaning is clear from the context.

Use i, j, k as loop indices.

Do not make the type name part of the variable name, e.g., center rather than center-point.

Use plural for collections of items, e.g., names rather than name-array.

Use lower-case function, variable, and file names.

Use dash as a word separator, e.g., hours-to-wages. Note that this is a PostFix convention. C often uses underscores (e.g., hours_to_wages) and Java often uses camel case (e.g., hoursToWages).

Use CAPITALIZED-WITH-DASHES for constants.

Use CamelCase with an upper-case first letter for custom-defined type names, e.g., TrackingOrder.

Avoid l as a variable name and O as a type name as they are easily confused with 1 and 0, respectively.

#### 10.2` `Coding Style

Properly indent code. This is extremely important for readability.

Consistently indent code. Do not mix tab characters and spaces. The typical tab width is 4 spaces. Using spaces avoids problems with different editor settings.

Use empty lines to visually structure blocks of code.