▼Design Recipes in Post  Fix
►1 Introduction
On this page:
1.1 From Problem Statement to Solution
1.2 Post  Fix Language and Development Environment
1.3 Structure
8.2
    ← prev  up  next → 

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 design recipes 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 internalize 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:

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 are real-world temperatures measured in degrees Celsius that 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 a number may be 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 an 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):

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 ortermimprove 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:

termcdisp{ 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

Instead of manually checking whether the actual results match the expected results, a better option is to automatically check the examples. To this end, a check function is called with the actual result and the expected result. The test function to test for exact equality is

actual expected test=

The actual parameter is replaced by a function call on the value to test. For example, if function celsius-to-fahrenheit is given 0, we expect 32 as the result. The check becomes:

0 celsius-to-fahrenheit 32 test=

If actual is equal to expected, then the console output is:

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

If actual is not equal to expected (and the function erroneously produces, for example, 99 as its result), then the output is:

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 PostFix 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:

    ← prev  up  next →