Personal Blogs

The exit behaviour problem found with the 'Greeting' program in Algorithms 1 was down to incorrect ordering of statements inside the while loop. To solve this problem start again and do a proper job this time.

Step 1: Write a general description of what we want the algorithm to do and how it might do it; call this an 'initial insight' if you so wish:

Output a general greeting statement. Read in a user's name and if the input is not an empty string output a more specific greeting that includes the name. Keep on doing these last two actions until an empty string is input.

Step 2: An algorithm is a list of precise instructions for solving a problem. All instructions must be unambiguous. By definition anything written in an entirely formal language like a programming language is unambiguous but this does not mean such a listing will match what is required or make it easy to see what went wrong when it doesn't.

Some intermediate form written more in the language of the problem than that of the implementation is often useful but the variety of styles for writing such algorithmic statements are numerous. Currently a pseudocode, formal English, style seems to be becoming more general than numbered lines with gotos so following this trend:

    Output a general greeting

    loop
        Request a name and read it in
        if name is an empty string
            break                    # break means exit the enclosing loop
        Output a greeting that includes name
    # the end of the loop

    Output a goodbye message

Step 3: implement the code. Start PyCharm, the Greeting project is open or if you have closed it to start another select it from File >  Reopen Project. Select hello.py in the project tree and do Ctrl + C (copy). Select Greeting in the project tree and do Ctrl + V (paste) naming the new Python file, 'hello2.py' say. Edit code in the new file to be as follows:

print("Hello, g'day, its great to see you")

while True:
    name = input('Please input your name >')
    if name == '':
        break
    print('Hello', name + '. Welcome to algorithms and data structures in Python.\n')

print('\nBye')

Run hello2.py by right click on the new file in the edit window or on the project tree. Everything works as might be expected.

Python does not have a loop or a repeat..until. To locate a loop condition anywhere than at the apparent start use while True (loop forever) with break to get a conditional exit from the loop. In print('Hello', name + '. Welcome to algorithms and data structures in Python.\n') the string concatenation operator + is used to join name to the string literal and get the full-stop in the right place; \n includes a new line character in output.

A loop invariant

There is a property of loops called the loop invariant that guarantees correct working when chosen to relate to the task the loop performs (actually it only guarantees partial correctness because it does not ensure the loop will ever terminate, but that is something else). We already know that the loop in hello2.py works as required but a check that it complies with an invariant property may be instructive particularly in view of the perhaps unusual location of the loop condition.

The invariant must hold - be true, before and after each repetition of the loop (aka. an iteration). Basically this means that it must hold before the test allowing loop entry or re-entry and hold after this test whether or not the test returns true. The invariant for a loop summing a list of numbers, for example, states that the total of those already summed and those still to be summed is constant and equal to the eventual summation: the required result towards which the loop progresses.

Python does not allow assignments or other operations in conditions so it is unlikely that a simple loop-entry test will result in an invariant failure after the test when the invariant holds before it. However, as we will see later, side effects from calling a method of an object could result in a fail so the before and after requirement is worth keeping in mind.

So, what is the loop invariant for hello2.py? A possible requirement is that the variable name should hold a string with length greater than or equal to zero. This is far too weak: all strings have a length greater than or equal to zero.

A good invariant is that name must hold a string read anew from user input on each iteration. We could say that the required result embodied in the total of the invariant and the exit condition, the result the loop must progress towards, is that the user becomes more and more bored with inputting names and eventually presses return without entering one. The Algorithms 1 Greeting did not comply with this invariant helping me to write flawed code in hello.py.

In 'hello2.py' the invariant holds before and after if name == '':. and the location of the loop test is perfectly sound. The test marks the loop entry and re-entry point where the invariant must hold, while is just the point on the loop that execution jumps back to after each iteration. Any reasonable compiler will remove the while check that True is true and jump execution back to the input statement.

When the initial assignment to name takes place the loop has not been entered despite the fact the assignment appears after the while. To locate the test with while and maintain the loop invariant, name must be initialized with a user input before the loop:

name = input('Please input your name >')

while name != '':
     print('Hello', name + '. Welcome to algorithms and data structures in Python.\n')
     name = input('Please input your name > ')

There is nothing wrong with this version, in fact it looks somewhat neater than the original but that is down to Python syntax rather than any problem with the original code. Whether it is easier to read, having greater clarity, is a matter of opinion and possibly depends on what one is accustomed to. If the initial insight indicates a loop-exit located other than with the while why not put it there, maybe?

In this offering we have looked at three aids to developing correct algorithms: initial insight, pseudocode and loop invariants. I hinted that initial insight should include a specification of what the algorithm must do or achieve. This requirement ensures that we write the right algorithm, one that solves the problem we want it to. Pseudocode and loop invariants help us write the algorithm right. (Adages adapted from validation and verification of software systems as in Boehm 1979).

Reference

    Boehm, B. W. (1979) 'Guidelines for Verifying and Validating Software Requirements
    and Design Specifications', TRW Redondo Beach, CA, USA [Online]. 
    Available at http://csse.usc.edu/csse/TECHRPTS/1979/usccse79-501/usccse79-501.pdf
    (Accessed 22 June 2015)

[Algorithms 2: An invariant Greeting(c) Martin Humby 2015]