Personal Blogs

In Algorithms 11 binding methods to an instance of a class getting dynamic dispatch was demonstrated: calling a method against an instance at a reference calls the method belonging to that object. Algorithms 12 showed class inheritance: inheritance of method names together with the functionality of those methods.

Together these two attributes provide subtype polymorphism: the ability to view an instance of a subclass as an instance of its super-class. Subtype polymorphism is enforced in statically typed languages where calling a method unknown to the nominal class of a reference (or by-value variable) gets a compile-time error. Python provides more or less total flexibility, a variable can be viewed as any type, but compliance with the framework supplied by static typing can provide a basis that is known to work.

The utility of class inheritance for building new classes from existing classes with added or specialised functionality is obvious: it saves work and reduces code size together with associated complexity. Copy and paste could be used to get a new type but using inheritance the total amount of code is reduced. In Algorithms 12 a Stack was turned into an extendable structure, a List, simply by replacing __init__() and push() with new methods and introducing a helper method _check_capacity().

Overriding and overloading methods

Replacing an inherited method is known as overriding the method. To maintain polymorphism the parameter types and return type of the new method must be the same as those of the overridden method or steps taken to ensure the new method still works when presented with the same type of arguments as the method being replaced. Stack.__init__() for example, was designed to accept an integer, the maximum size of a stack, so List's __init__() should also work when passed an integer as well as an Iterable. (Iterable is the base class of List and Python's list, so a new List can be constructed from either of these types). 

A function's name, parameters and return type comprise its signature. Many statically typed languages allow use of functions with the same name but different signatures, known as overloaded functions or methods. From the compiler's viewpoint these are separate functions. This can cause problems in some languages when pre-compiled libraries are used because the overloaded function names exposed by the library have been changed by the compiler, a process known as name mangling.

Many languages allow functions to be called without their return being assigned to a variable. In this case the expected return type will be unknown to the compiler so the signature used for overloading excludes the return type. When overloading is available execution efficiency will suffer if the type of a parameter is chosen to be that of a mutual ancestor with runtime type checking used to determine the actual type rather than writing separate overloaded methods for the different types.

Pythons dispatch mechanism uses the method name to determine which method to call. Parameter types do not feature in this selection excluding overloading. Any method with the same name in a subclass effectively overrides the superclass method but complete flexibility as to the type of parameters passed to a function can replace overloading. Runtime type checking or named default parameters are used to determine how parameters of different types are processed. Named defaults are considered to be more 'Pythonic' but are less transparent in use.

Encapsulation

Coding abstract data types without OOP in languages such as UCSD Pascal, Ada83 and Delphi there can be complete separation of operations appearing in the interface from the workings hidden in the implementation. Anything declared in the implementation, perhaps located in a separate file is private and hidden in entirety from client code.

Interface / implementation separation has become known as information hiding, a term originating from the design strategy proposed by David Parnas (Parnas 1972). In OOP such separation is provided by encapsulation but the facilities available to achieve it vary from one language to another. In general encapsulation means grouping the methods that operate on data with the data rather than passing data objects with no inherent functionality to a hierarchy of possibly shared subroutines.

OOP languages tend to declare all fields and methods in an interface file or section hiding only method implementations or feature no physical separation of code the entire class appearing in a single file. A typical C++ program for example will define a class in a .hpp header file and put method implementations in a separate .cpp file.

In C++ any class that is not defined as abstract can be instantiated by value simply by declaring a variable of the class. In this case the compiler needs access to the total size of fields so sufficient space can be allocated to accommodate the instance. When all instances are by reference as in Java etc. this is not a requirement. All references have the same size in memory and the actual allocation is done at runtime by object creation. Even so, Java and many other languages still feature all-in-one-place class definitions.

To overcome implementation exposure two strategies have been adopted: inheritance from a pure abstract class or interface type without any fields featuring only method definitions and secondly, key words defining levels of exposure for the members of a class (its methods and fields), generally private, protected and public.

With inheritance from an abstract class descendant instances can be assigned to a reference of the abstract type and viewed as such. The descendant supports the interface defined by the superclass. Languages that do not provide multiple inheritance generally define an interface type and a class can support multiple interfaces. The actual implementation can be ignored by client code and can be made reasonably inaccessible through the reference providing interface / implementation separation. This comes at the cost of pre-definition of the abstract type and perhaps an additional execution overhead resulting from multiple inheritance.

Beyond the separation of the interface as a set of public methods, other levels of exposure only relate to re-use of functionality through inheritance. Fields and methods defined as private are hidden from client code and in subclasses. Those defined as protected are inaccessible to client code but are visible in a subclass implementation.

Making fields and methods private imposes restrictions on the options available when writing a subclass. For example, a base class Person might have a private field date_of_birth. If modification to this birthdate after instantiation is a requirement a public method set_birthdate() is needed. A subclass, Employee say, must either use the inherited setter method or override it perhaps to ensure that no person below a certain age can be employed. An overridden setter cannot access the private field but calls the inherited setter to modify the birth date. This minimum age requirement is then imposed on all subclasses of Employee, not so if date_of_birth had been give protected exposure.

Sounds logical but such a lack of flexibility can cause problems when the only access a descendant of employee can have to the age field is through the inherited setter.  Suppose at a later time a new class Trainee is required with a lower age limit. Due to the imposed limit no Trainee can be an Employee and cannot inherit or take advantage of any functionality already written in relation to employees. Reducing the limit for Employee will likely break existing age verification.

Another consideration may be the additional overhead of methods that call other methods, not good when execution efficiency is in any way critical. To overcome these problems Java provides a fourth level of exposure known as 'package-private', the default when no other is specified. All Java classes exist in a package, a grouping of class files. Package-private members of are visible in the implementation of all other classes in the same package but inaccessible to classes located in other packages.

Package-private exposure finds widespread use in supplied Java class libraries and many other languages provide an equivalent. Using it as an alternative to protected exposure is all very well if it is possible to extend a package, not a possibility for these Java libraries. Consequently minor modifications to the functionality of a HashMap say, with a requirement for equivalent execution efficiency means starting almost from scratch. The only useful library definition is the Map interface.

Coding descendants there is really very little to be gained from these restrictions and making the implementation completely inaccessible is not possible in Python. Protected and private categorization is available by a naming convention rather than error generation and more reliance is placed on organization and coding by thinking. Similar measures are available for structuring the code to provide modularity.

Python information hiding

The smallest increment of Python functionality is a class. Classes can contain nested classes but putting a class in a nested location has no particular significance other than an indication of associated usage. For an inner instance to have knowledge of an enclosing object it must be given a reference to it:

class Outer(object):
    class Nested:
        def __init__(self, outer):
            self._outer = outer
            ...

    def __init__(self):
        self._inner = Outer.Nested(self)
        ...

Python provides no direct equivalent of private and protected exposure but a convention that variable and helper method names starting with an underscore are protected and should not be accessed directly by client code is useful. A leading double underscore supplies some equivalence to private members but this provision is not required in most cases.

Constants exposed by a module can be put in all upper case to indicate their status but to get a constant that is immutable as far as possible it must be made a member of a class accessible through a property. This option is shown in the download package1.module2 but going to these lengths is not what Python is about, I think.

Python, Delphi, C# and some dialects of C++, provide so called properties, a construct that replaces public getter and setter methods generally to control or exclude modification of the value of private or protected fields by client code. The property is seen as a virtual field so we can write x = aproperty and when write modification has been programmed aproperty = x, both without function-call brackets or arguments.

Because all members are accessed by name in Python its properties can supply validation of submitted values in a subclass even if the base class provides direct access. A property with the name of the base class field replaces it. A number of different syntax and variations are available but typical usage might be:

class Base:
    def __init__(self, value):
        self.value = value     # value is a fully accessible field
    def halve(self):
        self.value /= 2

class Subclass(Base):
    def _get_value(self):
        return self.value
    def _set_value(self, value):
        if value >= 0 and value < 100:
             self.value = value

    val = property(_get_value, _set_value)

instance = Subclass(99)
print(instance.val)
instance.halve()
print(instance.val)

In the Subclass the property value replaces the base class field and all inherited methods now address the field _value through the setter and getter functions. The base class field value does not exist in the subclass so there is no wasted allocation.

In Subclass the field name _value could have been given a double underscore indicating private status. Doing this invokes name-mangling and __value becomes an alias for the mangled name in the implementation. The mangled name, which always follows the pattern _Base__value or generically _Classname__membername, is visible in subclasses and client code as well as the current implementation. Such members are not truly private, simply less accessible to erroneous use.

Double underscore method names can be used to get the same effect as the static instance methods available in C++ etc.  When a dynamically dispatched method is overridden this directs all calls to the new method, very likely an unwanted side effect when the method is a helper used by multiple other inherited methods. Replacing a static method in a subclass, same name, same signature, this does not occur and any calls in inherited methods still go to the superclass method.

The two alternatives are contrasted by mod_list.py and  mod_list_static.py in the download. An overridden _check_capacity() method and a 'static' equivalent __check_capacity()are shown as respective alternatives. The replaced method is used in a subclass by insert_at() but not push(), which must continue to use the inherited version.

Python modules and packages

A Python file or 'module' with a .py extension can contain constants, variables, functions and class definitions. In larger programs modules supply the next increment of modularity above classes. Lest we forget which module is being used, within a module its canonical name is available through the global variable __name__.  However, when a module is run as a program __name__ is set to '__main__' getting the option of excluding minor test code from module initialization by enclosing it in an if statement. Variability of __name__  is demonstrated in package1.module1 together with the options for importing modules contained in a package as shown below.

The same naming conventions using underscores to indicate modules that are only for use by modules in the same package can be employed but a prepended double underscore does not result in name-mangling.

Packages allow modules to be grouped according to the type of functionality they expose or the usage they have within an application. They can be nested to any depth: package1.sub_package.subsub_package.subsub_module. When importing a module no account is taken of the location of the importing module in the package hierarchy and the full canonical path must be used.

If package1 contains two modules module1 and module2, to import a function module2.where() to module1 there are three options:

import package1.module2                           # import option 1
from package1 import module2                     # import option 2 (recommended)
from package1.module2 import where as where2     # import option 3

def where():
    return __name__

def elsewhere():
    result = package1.module2.where()   # using import option 1
    result = module2.where()            # using import option 2
    result = where2()                   # using import option 3
    return result

if __name__ == '__main__':
    print(where())
    print(elsewhere())

To create a new package in PyCharm, in the project tree right-click on the project name or the package under which the new package is to be created and select new > Python Package. PyCharm creates a module __init__ within the new package. The purpose of this module is to code any package initialization not done by constituent modules. When __init__ does not declare an __all__ list of module names, any modules imported to it from the current package or elsewhere are made visible in any module using the statement:

from package import *

When the alternative, declaring a list of modules in __init__ to be imported by import *  is used, __all__ = ['module1', 'module2'] for example, this list can contain only modules in the immediate package. Also its presence excludes access to the modules in __init__'s import statements as described above.

Note that circular imports are not allowed. If module1 imports module2 then module2 cannot import  module1. It may be possible to circumvent this rule by importing individual items, as in import option 3 above and module2's equivalent of module1's elsewhere() in the download, but be aware of possible problems: type checking failing to recognize an imported class for example.

Summary

Interface / implementation separation isolates client code from changes to an implementation. It can also provide levels of abstraction, used to mitigate the complexity inherent to large software systems. A user interface for example, can hide its implementation and the various subsystems that support it. Similarly each subsystem can hide its own implementation from code in the user interface. This layering of functionality can continue down through as many levels as may be required following the design strategy of information hiding.

OOP languages provide a level of interface, implementation separation through encapsulation. Subtype polymorphism used with abstract or interface classes can strengthen encapsulation. If sufficient pre-planning is put in place, provision of read-only interfaces for example, object integrity can be ensured.

Python relies less on enforced encapsulation than on code written with the precepts of information hiding in mind. Python's call-by-name has two effects here: any class supplies a conceptual interface that can be supported by any other class supplying the same function names and exposed functionality; direct access to fields in a base class can be overridden using properties.

Import statements within the __init__ module can be used to create virtual groupings exposing modules and/or classes from other packages. This facility suggests the option of creating multiple groupings by type of functionality and by usage within an application, for example.

Reference

Parnas, D. L. (1972) 'On the Criteria To Be Used in Decomposing Systems into Modules', Communications of the ACM, vol 15 no. 12 [Online]. Available at https://www.cs.umd.edu/class/spring2003/cmsc838p/Design/criteria.pdf (Accessed 22 September 2015)

[Algorithms 14: Subtype polymorphism and encapsulation (c) Martin Humby 2015]

Because they are stored in a single contiguous block of memory arrays are not extendable. Memory is allocated to an exact fit, nothing more. This characteristic was reflected by the maximum size of a Stack. Now the requirement is for a List type. As we are coding the List ourselves we can give it any functionality we like including unlimited increase in size and the ability to add items not just at the end but to insert an item anywhere along a List's length.

Similarly, the requirements for List can dictate that when an item is removed at any index the list will close up to fill the gap. Additionally, List can be given a method to add a guard value at the end of the list for use when the List is searched .

Ignoring these new requirements List has several characteristics in common with Stack and one way to make a start on coding List is to copy Stack's code, paste it into a new file or the same file and rename Stack to List. OOP provides an alternative that brings some advantages: inheritance. Using inheritance all that needs to be done to get Stacks fields and functionality into List is to include Stack in the class declaration:

from my_OOP_stack import stack as Stack
class List(Stack):
    pass

Readers will note I have imported stack as Stack. The Python convention for class names is to use CamelCase but when it started out stack was not a class as such, simply the next best thing to a record. A short breakdown of Python naming conventions can be found here. The keyword pass allows a class or function to be defined with an empty body.

If you would like to follow the incremental development of List, open the List Investigations project from the download in PyCharm. Create a new file list.py and copy the above code into it. There is a copy of my_OOP_stack_test.py in the project with the import statement changed to: from list import List as stack. Without any doubt the test code in this file views a List as a stack. Run the test script and the output is identical to that got in Algorithms 11 when it was run with a genuine stack.

This is not surprising. Currently List has no functionality or fields other than those it has inherited from stack. Even so, it demonstrates three facts: List has inherited stack's interface - if it hadn't calling stack's methods would get an error. Similarly it has inherited stack functionality - if it hadn't output would differ or an error would result (despite the test script being far from comprehensive please take my word for it). Together these two points comprise what is sometimes known as class inheritance (as opposed to pure interface inheritance, to be dealt with in a later article).

The third fact is that List can be viewed as a stack.  List is a subclass, a subtype, a child class or a descendant of stack.  Stack is a superclass, parent or ancestor of List. The ability to view a subclass as a superclass is known as subtype polymorphism.

In some languages a view may become a reality. C++ features class instances by reference and by value. When a by-value instance is assigned to a variable of the same class all its fields are copied getting a new instance. If it is assigned to a superclass variable any additional fields it has are truncated off getting an instance of the superclass.

In languages that use static typing, assigning a reference to a subclass to a variable declared to be a reference a superclass is allowed. In Python assigning to a reference viewed as a superclass has the same effect.

Assignment super to subclass is not allowed under static typing: the subclass may have declared additional methods that do not exist in the superclass and in turn these methods may access fields that the superclass does not possess. In Python you can do what you like but errors are likely if this rule is violated.

Redefining push( )

Because push() adds items to Stack's array it has the capability of causing an overflow. The answer is simple: when the array is full allocate a bigger one and copy the items from the old array to the new one. 'But doesn't that take a long time to do?' you may wonder.

Well yes, doing this for a medium to large array coded to show how it works in Python is quite slow. Python features list slicing getting an equivalent to C's memcpy() but currently that will not be used. When coded in C or Delphi Pascal or assembly language for example, copying is much faster. Over time CPUs have been optimized to do various tasks and copying blocks of memory is one of them.

Another point, we are not copying actual items only references to them, considerably smaller than a record with even a few fields. Faced with a really big sequence other techniques would have to be considered. Adding a new array linked to the old one is one possibility but for small to medium arrays copying is fine and most likely more efficient.

Copying arrays

The copy_left() function is simple. It is passed the source array, the destination array, the source index and the destination index together with the number of items to be copied. Starting at the lowest index in both arrays it iterates over the given section of the source copying items to the destination. If both the source and destination array are the same the element at the destination index is overwritten deleting that element.

copy_right() duplicates the element at a source index in the same array after moving other elements right to make room. The original element can be overwritten with an insertion. To avoid overwriting elements copying must start on the right and work leftwards. Coding it is slightly trickier, mostly because of the non-intuitive syntax of the range() generator particularly when counting down.

A generator comprises a special code construct, generally within a function. Each call gets the next value in a sequence of values.  The function call can be put in a for loop to obtain successive values one per iteration. Writing generators will be detailed at a later time.

Counting up with range() we get range(start_value, last_value + 1, increment). When there is a single argument, range(n)for example,  n is the number of integers generated including zero. A start_value is optional, default zero, but required if there are other arguments in addition to n.  The increment defaults to 1 when not included.

Counting down with range(), this time we get range(start_value, last_value - 1, increment) with start_value greater than or equal to last_value. The increment is of course negative.

The code for my copy_right() is:

def copy_right(source, s_index, dest, d_index, length):
    sx = s_index + length - 1
    dx = d_index + length - 1
    for sx in range(sx, s_index - 1, -1):
        dest[dx] = source[sx]
        dx -= 1  # decrement destination index by 1

This function is in 'array_types.py' in the download with a small test script. Readers following incremental development are invited to code a similar copy_left() function in array_types, otherwise the code is in 'array_types.py' in the 'solutions' package.

To complete the redefinition of push() an instance variable capacity or some such will be needed to hold the current size of the array. The revised version of __init__ shown below calls the superclass __init__ to set the array's initial size. Another option can be included to provide Python style typecasting of any sequence to the List type.

Type casts

In languages with static typing, compiled to native code, a typecast often means 'view the object at this variable not as the type of the variable but as some other type.' Generally there is a restriction that both types should have the same footprint in memory and perhaps a few more, but when an object is by reference all references have the same size.

(native code is machine code executed directly by the Central Processing Unit (CPU) and native to the target platform for an application. A platform is the environment an application runs in supplied by the combination of the CPU, the operating system and sometimes a Graphical User Interface (GUI))

In Python what may appear to be a typecast is in fact a call to a constructor. __init__ is called and initializes the new object based on the object passed in. For List we might have  a_list = List('abcd'). Adding code that includes this option to List.__init__ gets:

from array_types import copy_left, copy_right
from collections.abc import Iterable

DEFAULT_CAPACITY = 2    # use a low value   testing

class List(Stack):
    def __init__(self, data):
        if isinstance(data, Iterable) and len(data) > 0:
            data_len = len(data)
            self.capacity = data_len * 3 // 2
            super().__init__(self.capacity)
            copy_left(data, 0, self.array, 0, data_len)
            self.SP = data_len
        else:
            if data == None or data < DEFAULT_CAPACITY:
                self.capacity = DEFAULT_CAPACITY
           else:
                self.capacity = data
            super().__init__(self.capacity)   
        self.max_size = sys.maxsize    # set inherited max_size to a very large number

Iterable is the common ancestor of all classes that can be iterated over in a for loop. It is the base class for these types. As yet List is not iterable so an instance cannot be 'cast' to a List to get a new copy. The guard element, for use in a linear search of the List, will be discussed in a later article.

The method that checks whether overflow of the array is imminent will be shared by Put() and an insert_at(index) method. It can be coded as a method _check_capacity():

def _check_capacity(self):
    if self.SP < self.capacity - 1: # leave a spare element for a guard
        return
    self.capacity = self.capacity * 3 // 2
    new_array = array_(self.capacity)
    copy_left(self.array, 0, new_array, 0, self.SP)
    self.array = new_array

The new array and the existing are separate so either of the copy functions could be used: use the simpler copy_left(). The method name starts with an underscore to indicate that it is a helper method belonging to List and not for public use by client code. I will endeavour to keep to this rule.  push(item) calls the method which will make space for the addition when required:

def push(self, item):
    self._check_capacity()
    super().push(item)

Here super().push(item) calls Stack's push to do the addition. If I was coding this for real, the original push is trivial and I probably would put its code inline rather than calling it but here the full possibilities of inheritance are used.

The methods insert_at(index) and delete_at(index) are left for interested readers to code with the proviso that the methods are included in the 'solutions' package version. Inherited pop() requires no modification unless we want to copy a reduced number of items to a smaller array, perhaps later, so the final task is to write a method to insert the guard value.

Adding a guard

From the provision in check_capacity() there will always be sufficient room to accommodate a guard at the end of the array. A guard is not a permanent addition so, unlike insertions and deletions, adjusting the inherited stack pointer self.SP is not required:

    self.array[self.SP] = item

Summary

In this section we have seen how an array can be made extensible by copying and visited two more OOP basics : class inheritance and polymorphism.

Two different requirements for copying elements left or right within the same array were identified. The single memcpy() function or its equivalent seen in many languages computes which of the alternatives to use when source and destination overlap. An array_cpy() function is provided in the solutions package. 

[Algorithms 12: Basic OOP - a List type (c) Martin Humby 2015]

Functions hide their workings in an implementation. Data types can be constructed with the same idea in mind. Functions implementing operations on a structure supply an interface for use by client code: other functions that use the structure, that is. Variables used to build the structure and any helper functions provide a separate implementation. For a structure developed using non-OOP techniques, in Ada83 for example, complete separation of the interface and implementation is possible by putting the code in separate files.

OOP languages tend to rely less on physical separation using key words such as public to define parts of the interface with private and protected indicating elements of the implementation. OOP has reinvented separation of interface and implementation by calling it encapsulation: a class exposes public methods and encapsulates the rest.

There are two main advantages to this approach: implementation details can be ignored when using the data type and different implementations of a structure can be substituted without affecting the operations seen in the interface by client code. Additionally, in some compiled languages a unit or package containing the implementation can be modified and compiled separately without the requirement to recompile client code. Only when the interface has changed is a rebuild required.

Perhaps a particular implementation works efficiently for a small number of stored items but does not scale well to a large number. Another implementation can accommodate a vast number of items but carries an overhead that makes it less efficient than an alternative when used with only a few. If one type can be substituted for the other without affecting client code, changes to the software will be minimized when it becomes apparent that a particular implementation is not up to the job. Time, cost, and a great deal of frustration and unproductive effort will be saved.

Viewed in this way a data structure is seen as an abstract data type (ADT). An ADT is defined by the operations that can be carried out on it, the pre and post conditions of those operations and the invariant condition of the ADT. Like the definition of a relation discussed in Algorithms 3, a particular implementation does not figure in an ADT definition. The basic operations on a stack of data items, for example, are to push an item onto the top of the stack and to pop an item off of it. Its invariant can be defined as its size always being greater than or equal to zero and less than or equal to a maximum size if one is specified.

Pre and postconditions

Some functions will only produce the required result if certain conditions pertain when the function is called. For stand alone functions that do not result in side effects on persistent data, such conditions can only relate to restrictions placed on the input set. For operations on a data structure the current state of the structure may also need to be taken into account. These prerequisites for calling a function are its preconditions.

After the function exits another set of conditions will apply. A statement of these postconditions is needed to check that a particular implementation of the function works according to requirements. For example, the pre and postconditions of a typical math square-root function defined in the style of VDM are:

SQRT(x:real)y:real
pre x >=0
post y*y = x and y >= 0

The input must be zero or positive; the output when multiplied by itself must equal the input and be greater than or equal to zero because sqrt() always returns the positive square root. Alternatively the relationship between pre and post conditions can be represented as a Hoare triple  where  and  are predicates and  is a program that terminates when it is run.

The Vienna Development Method (VDM) founded on Hoare Logic supplied a basis for the realization of these concepts in software design but various less formal specification languages are now available. OCL for example, an adjunct to the Unified Modelling Language (UML), allows the use of formal English to define conditions and invariants.

VDM, OCL etc. are typified as being formal methods.Their representation as Design by Contract has resulted in further deformalization although this may not have been the intention of Bertrand Meyer who coined the metaphor to represent the relationship between client code and code supplying a service.

A Stack ADT

After reviewing various formal and semi-formal definitions on the www in relation to a stack (there are many), model based VDM looked too cryptic, algebraic based definitions likewise and OCL appeared to lack precision. Perhaps formal English is the answer. Of course I am no expert in any of these approaches so my judgement is open to doubt. The idea I found most appealing used a series of operations in { } brackets (Wikipedia 2015). Applying this idea to a stack ADT, a possible set of operations on a could be formulated as:

pre  true
post r = a new Stack instance
     r.max_size = max_size
     size(r) = 0
     is_empty(r) = True
     is_full(r) = False
invariant: size(r) >= 0

size(S: Stack): r: (0.. S.max_size)
pre  true
post r = j - k where {S = Stack(), j * push(S, i), k * pop(S), j >= k} 
     {the sum of valid pushes - pops since S was created}

is_empty(S: Stack): r: bool
pre  true
post r = (size(S) = 0)

is_full(S: Stack): r: bool
pre  true
post r = (size(S) = S.max_size)

top(S: Stack): r: Item
pre  not is_empty(s)
post r = i where {i = pop(S), S = push(S, i)}
    {defines i, S after i has been popped off and pushed back on again} 

push(S: Stack, i: Item): None
pre  not is_full(S) and n = size(S)
post top(S) = i and size(S) = n + 1

pop(S: Stack): r : Item
pre not is_empty(S) and i = top(S) and n = size(S)
post r = i and size(S) = n - 1

The precondition true specifies the operation is valid for any state of a stack: there are no preconditions. An ADT invariant specifies conditions that are True for any instance and remain True throughout its lifetime irrespective of the operations carried out on it.  It is therefore appropriate to place the invariant after the postconditions for initializing an instance.  

With these operations in place a visualization of a stack with push and pop waiting to execute is as below:

When the item on the left is pushed onto the stack and pop() is called that item will be the one on the top of the stack and will be removed. This characteristic makes a stack a Last-In-First-Out structure, a LIFO, as opposed to a queue which features First-In-First-Out, a FIFO.

A traditional implementation of a stack without using any OOP techniques is best done in a separate file called 'stack.py'. The first step is to define a record to hold persistent data for the stack instance. By persistent I mean data that persists from one access of the stack to another (for data to persist from one run of a program to another it needs to be placed in backing storage i.e. put in a file saved to disk or some other medium).

An array to hold items in pushed order is required. A stack pointer points to the next free location in the array. When the array has zero based indexing, size and the value of stack-pointer are the same: only a stack pointer is needed. Maximum size is the size of the array. Using Python's record equivalent as before gets:

from array_types import array_

class stack:
    def __init__(self, max_size):
        self.array = array_(max_size)
        self.SP = 0     # the stack pointer
        self.max_size = max_size

Now define the stack operations:

def push(stack, item):
    stack._array[stack.SP] = item
    stack.SP += 1

def pop(stack):
    stack.SP -= 1
    return stack.array[stack.SP]
# etc.

A complete set of operations is in 'stack.py' from the download project in Stacks.zip. Test scripts are also included. There are a couple points to note from the tests, in part resulting from the characteristics of the underlying list type used to implement array_.

When there is an attempt to push an item onto a full stack this overflow produces an exception. The exception is raised before SP is incremented making the push() operation valid as far as it goes. However, when an underflow occurs from popping an empty stack, the stack pointer is decremented to -1 before the invalid removal is attempted. There is no exception but this is neither here nor there: the stack is already corrupted and will no longer function correctly. The value of the stack pointer SP is also the size of the stack and the ADT invariant is broken.

For those with a belief that design by contract is the answer to all life's problems this may be of no consequence: calling pop() on an empty stack is in clear violation of pop's precondition. This is not my belief and these problems will be dealt with a later article.

The second point is that when items are popped off the stack the stack-pointer is decremented but items are not actually removed. They will remain in the array until an item is pushed into the space they occupy. For a limited number of small objects this is not a problem but for a large structure replacing references to objects with a reference to None in pop() might be required. A test file for 'stack.py' is in 'stack_test.py'

Testing the stack

In a test file possible syntax to use stack operations is:

from stack import *       # import all stack's identifiers by name

a_stack = stack(6)
print('stack size:', size(a_stack), '  stack array:', a_stack.array)
push(a_stack, '||')
p = pop(a_stack)

print(empty(a_stack))

This is not at all bad and you could begin to wonder what OOP is all about. A problem might come up though if a queue was also required and someone had been foolish enough to implement removing an item from the front of the queue as pop(). Then with

from stack import *
from queue import *

queue's pop() would hide stack's pop() and the wrong function would get called.

A way around this problem is to import all queue's identifiers individually giving any that clash with stack's an alias:

from queue import join, pop as leave, .....

This alternative is open to error when there are many identifiers. A way that avoids any possibility of error is to import only the file name and prefix functions with it:

import stack
import queue

a_stack = stack.stack(6)
print('stack size:', stack.size(a_stack), '  stack array:', a_stack.array)
stack.push(a_stack, '||')
p = stack.pop(a_stack)

This alternative is acceptable for a few calls but not when there are pages of code with many references to one or more stacks, I think. Perhaps it is time to see what OOP has on offer.

Summary

Here we have looked at the characteristics of Abstract Data Types in general and in relation to a stack ADT. The concepts of preconditions, postconditions and class invariants were introduced. Testing the stack identified overflow and undeflow problems. There was also a problem when multiple imports were used one hiding the identifiers used in the other. Algorithms 11 will address these problems.

Reference

Wikipedia (2015) Abstract Data Type [Online], 4 July 2015. Available at https://en.wikipedia.org/wiki/Abstract_data_type (Accessed 26 July 2015).  

[Algorithms 10: Abstract data types - Stack     (c) Martin Humby 2015]

Arrays and records supply primitive data structures that can be used to construct other more complex types. As they stand these basic structures form part of several algorithms and make a good place to start.

An array is a monolithic sequence of elements usually all of the same type. Ordering of elements is sequential so they can be addressed by one or more indices that identify a particular element. It makes sense to to refer to the arrangement of elements as being in a line even when the line has a number of disjunctions to produce rectangular or other shapes. Always there are first and last elements and, for inner elements, next and previous elements. These properties make arrays one of a group known as linear data structures.

The elements of a record, generally referred to as its fields or members, may or may not be of the same type and are addressed through identifiers, typically a name. The arrangement of fields in a record can be seen as forming a tree with identifiers holding an offset from its base. This is a somewhat unusual view but illustrates the fact that records are not linear as such.

Arrays

Consider an array that has been initialized so that all its elements contain an integer value of zero as shown below. The indices to elements have been included for convenience and the array has been assigned to an identifier an_array making it accessible:

In many languages creating this array would mean that all its zeros were contained in a single contiguous block of memory with all bytes set to zero. Python does provide this kind of array with its array type initialized to hold integers but I want an array capable of holding any type including records and supplying the option of multiple dimensions. Arrays with these capabilities can be got from array_types.py in the Arrays.zip attachment.

Initializing one of these arrays with integers the result is as shown below:

The array comprises a contiguous block of references all pointing to the one and only int(0) object supplied by Python. This difference is of no great importance because integers and their like are immutable. One integer zero is as good as any other or indeed the same one.

Arrays are accessed by indexing into the array. To get the 10th element of a one dimensional array, also called a vector we write:

element_10 = an_array[9]

The variable element_10 now holds a reference to the same data as the tenth element of an_array, which may or may not be mutable. With the single proviso that modifying a mutable element can have external effects, an array can be viewed as holding its elements directly or holding references to those elements. The same is true of any variable.

Arrays may have one, two or more dimensions and boundaries that are not rectangular. Elements can form a triangle or a spiral arrangement for example:

In all cases there must be a unique mapping between the one or more indices and the elements of the array. A spiral type could map by [layer, element-in-layer]. Gaps in the elements mapped in the underlying array may be of no concern. The fact that index zero in a vector is not used is preferable to subtracting 1 from all indices when they are used with the array. Mapping the years 2000 to 2015 to array elements simply requires subtracting 2000 from submitted indices but the series 2000, 2005, 2010, .... indicates using a bit more arithmetic.

The array type in arrays.py is called array_ to distinguish it from Python's type. To create an instance of a 3 x 3 x 3 cubic array the syntax is

array_3D = array_(3, 3, 3, numbered=True) # number each element sequentially
array_3D[0, 0, 0] = 'first'
array_3D[2, 2, 2] = 'last'
print(array_3D[0, 0, 0], array_3D[2, 2, 2], '\n\n', array_3D) 

This syntax is typical of languages that provide multi dimensional monolithic arrays, Pascal for example. It is not the norm in Python because it does not provide these types out of the box. But no worries, the syntax for accessing elements of arrays with one dimension is identical in both cases. Python lists and arrays will be discussed at a later time.

To get the software into your equivalent of C:\Users\Martin\PycharmProjects\ALGORITHMS\Arrays and records follow a similar procedure to that given for Truth Tables in Algorithms 5:

Array visualization

Perhaps you might care to experiment by instantiating some larger arrays and printing them. Maybe assign a marker string to an element and see where it occurs in the printout. A few examples are in array_types.pi. To limit the number of different instances printed at any one time PyCharm provides a useful facility for inserting or removing # from lines of code so they are executed or not: highlight all or part of each line and press Ctrl +  /.

 [0, 1, 2, 
  3, 4, 5, 
  6, 7, 8, 

  9, 10, 11,
  12, #, 14, 
  15, 16, 17, 
 
  18, 19, 20, 
  21, 22, 23, 
  24, 25, 26]

Any array from a printout arranged as shown above (but with the # put in quotes) can be assigned to an array with the same number of elements:

an_array.assign([0, 1, 2, .... # etc.

Lookup tables

Arrays provide the fastest possible access to data that can be arranged sequentially on some ordinal. Ordinals are subsets of the ordinal numbers {0, 1, 2, ...} but other values can be mapped to them. The set of characters can be mapped directly to the ordinals. Strings cannot because they do not have a fixed length. While they can be placed in alphabetical order there can be any number of strings over an interval from 'A' to 'B', say.

Values that can be mapped to ordinals must have a least term and each subsequent term must have a fixed relationship with the previous term or terms. Generally,  where  is some function. Where mappings are not unique, the case of 2000, 2005, 2010, ... for example, the consequences must be known and taken into account when a value is looked-up in the array. A lookup of 2003 could generate an error, return the value for 2000 or alternatively for 2005 or some interpolation could be applied.

The kind of data that can benefit from storage and lookup in an array are values that cannot be computed because they result from external factors and values from long and complex calculations that are used frequently. Distances between towns on a map or locations on a PCB layout, for example, can be stored in a two dimensional array so that the most economical rout covering a number of points can be found. Integers can be mapped to town names. During computations the fact that town 3 is 'Ayr' is unimportant. To provide human readable output another lookup-table index to name can be generated.

Because the distance A to B is the same as B to A, a square array gives more than 50% redundancy. For an additional overhead when looking up a distance a triangular array can be used. As for any multidimensional array a function that will map indices in the multidimensional space to an index in the underlying vector of values is needed.

In two dimensions the requirement is for the number of elements in preceding rows plus elements in the current row. Zero based indexing simplifies the calculation getting row_index * row_size + column_index for a rectangular array. In a triangular array the size of each row increases:   

def _compute_index(self, indices):  # indices is a tuple
    row = indices[0]
    column = indices[1]
    if column > row:
        row, column = column, row   # swap row with column
    row_total = (row-1)* row // 2
    return row_total + column

Referring to the distance map in the figure above PORTSMOUTH at index [0] has a row size of zero: a virtual row. Row sizes form an arithmetic series with sum number_of_terms * (first_term + last_term) / 2.  First term is zero but we want want the sum of preceding rows and because row [1] ABERDEEN maps to row zero in the underlying array subtract 1 from the row index to get number_of_terms. Because the multiplication is done first integer division // can be used to get an integer result.

Using arrays that are not rectilinear row sizes must conform to a sequence, not necessarily linear, but one that has a closed form - a formula giving the nth term, that can be summed.

Summary

Arrays provide a simple, efficient and easily applied data type accessed by indexing. The restriction they have relates to their fixed size but it is simple to write types based on an array that provide for addition and insertion of additional elements. How this is done will be revealed in Algorithms 12. Algorithms 10 looks at the records.

To write software that behaves how we want it to a line of reasoning we have devised is hard-coded into the system. In most cases Boolean logic suffices: a condition is true or false, there is no probably about it. Software that uses this kind of reasoning, and sometimes probabilistic reasoning as well, can be described as being rule based with logical expressions providing the rules.

Python supplies two expressions to evaluate the truth of a condition and take appropriate action: if<condition is true> and while <condition is true>. The other loop construct for <variable> in something is predominately unconditional: the only time such a loop will not be entered is when something is an empty set or sequence or an empty range of values. This is not the case in C etc. where a for loop is a while loop with optional extras.

Comparisons

The comparison operators provide basic generation of Boolean values. To investigate their usage the Python Console supplies a convenient environment. It works like a calculator with access to the full range of Python syntax and provides immediate evaluation of results: no print statements required. It can be run from a command window with C:\Python34\python.exe but it may be easier to start PyCharm and select the Python Console tab on the bottom bar. Simply type in comparisons at the >>> prompt and press return. My session went as follows:

Python 3.4.2 (v3.4.2:ab2c023a9432, Oct  6 2014, 22:15:05) [MSC v.1600 32 bit (Intel)] on win32
>>> 10 == 10    # equality 'equals'
True
>>> 10 != 10    # inequality 'not equal'
False
>>> 10 < 10     # strictly less than
False
>>> 10 <= 10    # less than or equal
True
>>> 100 > 42    # strictly greater than
True
>>> variable = 42 >= 42     # greater than or equal 
>>> variable                # display the value at the variable
True
>>> a = 30
>>> 0 < a < 42  # operators can be chained
True

Note how a Boolean value can be assigned to a variable and stored for future use.

Functions can provide an additional source of Boolean values:

def exclusive_in(x, numbers, y):
    return x in numbers and x is not y

numbers = {1, 16, 42, 101, 10249561} # a set
x = 10249561
y = 10249561
print(exclusive_in(x, numbers, y))
output: False as it should be

y = int(10249561.0)
print(exclusive_in(x, numbers, y))
output: True as it shouldn't be

Without going into any great detail the function simply accepts the values passed to it when it is called by writing exclusive_in(x, numbers, y) and returns the result it calculates. The in, not in operators are useful for checking set membership as above and for checking whether an object is present in a list and several other data structures.

The is and is not operators check whether the object at a variable is the same object as that at another variable. Their usage is quite specific and, as apparent from the output from the test code calling exclusive_in(), they should not be used as a substitute for == or !=. A correct return from the function would be:

    return x != y and x in numbers

A legitimate usage for is or is not checks the type of an object

    isint = type(obj) is int # int being the class of integer

The names of some commonly and not so commonly used built in types are: object, int(integer),bool(Boolean), float, complex, tuple, list, set, str (string) and dict (dictionary: a hash map).

In Python all types have a logical equivalent acceptable to if and while. Any object can be cast tobool(obj) but doing this is usually unnecessary. Integers and floats are counted False for a zero value, True otherwise. An empty set, sequence or dict presents False, True if it contains any elements.

Having obtained the conditions applying to a particular situation as above it may be necessary to introduce further reasoning by combining these values. Results can be combined using the logical operators, also called the Boolean operators.

The logical operators

The Python Boolean operators or, and, not accept the values True and False and all other types. The not operator reverses the truth of its operand always returning a Boolean. It accepts a single operand placed on its right making it a unary operator. The other binary operators return a type that depends on the type and order of their two operands but two Booleans always result in a Boolean.

Because all types have a logical equivalent the actual type of the return is generally not significant. The only reason this eminently useful Python attribute needs to be considered at this stage is because there is no Boolean exclusive-or operator. There is however a bitwise exclusive-or ^ used to combine the bit patterns of integers. So, can this operator be used as a substitute for a logical xor with impunity?

It seems that it can, with the proviso that when relying on the logical equivalence of types other than bool, or integers except 1 and 0, those types must be cast to bool(<object>) before they can be used. Also, the fact that ^ has a higher precedence than the comparison operators can lead to problems. For example, if

p = 0; q = 1; r = 1; s = 0 then
print(p < q ^ r < s)

does not give the same result as

print((p < q) ^ (r < s))

Tabulating the operators in ascending order of precedence:

A more extensive precedence table can be found in the Python documentation athttps://docs.python.org/3/reference/expressions.html#operator-precedence. 

Logical operator precedence works in a similar way to arithmetic operator precedence BODMAS but BEBNAO (brackets, exclusive-or, basis, not, and, or) is probably less helpful. The comparison operators and everything else, apart from if - else, while (and lambda expressions), have a higher precedence than the Boolean operators. This means that we can write

    v = a < b and b < c and d > c

without any brackets around the comparisons. If all the comparisons return True then True is assigned to the variable v. If any comparison returns False then False is assigned.

However, it is worth keeping in mind that 

    v = p or q and r or s

gets

    v = p or (q and r) or s

not

    v = (p or q) and (r or s)

The or operator means 'One, the other, or both.' This usage is universal throughout mathematics and computing but everyday usage tends more towards exclusive-or. 'We can go to the beach or we can go to the forest and bathe in the hot springs.' Clearly there will not be time to do both!

Truth tables

A way of illustrating the results got from Boolean operations is to prepare a truth table tabulating outputs for all possible inputs with say T - true,  F - false: 

| p | q | not p | p and q | p or q | p xor q | p => q | p -> q |
+---+---+-------+---------+--------+---------+--------+--------+
| T | T |   F   |    T    |   T    |    F    |   T    |   T    | 
| T | F |   F   |    F    |   T    |    T    |   F    |   F    | 
| F | T |   T   |    F    |   T    |    T    |   T    |   T    | 
| F | F |   T   |    F    |   F    |    F    |   T    |   T    | 

This table is of course computer generated to avoid any possibility of error and, for bigger tables, a level of boredom. The column titles use xor to represent exclusive-or and there are two implication columns => and ->. The xor column values are got using bitwise ^. Generating the => column uses not p or(p and q). The -> column uses a bitwise equivalent.

The truth table generator is included in the attached .zip. It can be used to generate a truth table for any number of logical expressions with any reasonable number of variables by following the instructions at the top of truth_tables.py. It works by generating a binary number 1111 when there are say 4 variables p, q, r, s and counting down to zero. A binary 1 represents T - True, 0 represents F - False. The script truth_tables.py uses several other techniques that have not been discussed yet but may be worth a look.

The reason that the values of p and q show T, T in the top row in the table and F, F at the bottom is because this appears to be the computer science convention. Engineers being a more practical breed start with 0, 0 at the top and end with 1, 1 when considering logic gates. Now there's a thought! If I reversed the logic of the function that converts a 1 to a 'T' and a 0 to an 'F' would the other-way-up table still be correct? 

This file also includes a table for the Boolean expressions used to demonstrate precedence above but as-is it outputs a table with only the values of p, q, r, and s shown. I invite you to copy and paste the blank table into Notepad or similar, perhaps print it out, and fill in the truth values. Then delete blank = True from the tt.print_table() call and check your answers against what the computer thinks. You can of course do the same with any other truth table, one from the listings or one you have initialized yourself.

To get the code into PyCharm extract the .zip to your equivalent of C:\Users\Martin\PycharmProjects\ALGORITHMS\. Then with PyCharm open do File > Open and navigate to the Logic folder. Highlight the folder (not any of the files it contains) and click [OK]. Select Open in a new window [OK]. Expand the project tree and double-click on truth_tables.py to open it. Run the file.

Summary

Here we have looked at how Boolean values are generated by code, combined using conjunction and disjunction and how logical expressions can be investigated using truth tables. Algorithms 6 will look deeper at the meaning of these logical operations and consider implication and its equivalence to if condition then do something...

[Algorithms 6: Logically speaking   (c) Martin Humby 2015]

Passing an indeterminate number of parameters

Python matches arguments in a call to parameters in the parameter list by position

def func_a(a, b, c):
    ...     
val = func_a(d, e, f)

Argument d is matched to a, argument e to b, etc.

Sometimes it is useful to be able to write a function that that accepts any number of arguments. print() is one such function. When this is so prefixing the last parameter in the positional list (perhaps the only parameter) with a * character indicates it is to accept a sequence of one or more arguments:

def func_b(a, b, *args):
    ...
val = func_b(d, e, f, g)

Here d and e are matched to a and b positionally but f and g are wrapped to form a tuple which is passed to args. Tuples can be created on the fly and unpack transparently:

tup = (a, b, c, d)      # this creates a tuple
tup = 1, 2, 3, 4        # brackets are optional
d, e, f, g = tup        # the tuple is unpacked

Transparent unpacking cannot be used in the function body when the number of arguments in the tuple is unknown: a mismatch generates an error. Arguments in the tuple are accessed by indexing into it, arg = args[index], or by iterating over it in a for loop

def func_b(a, b, *args):
    for arg in args:
        # do something with arg

Another way of providing a function with optional parameters is to use key-word arguments. This kind of argument is doubly useful because inclusion of a particular argument in any call is optional and the argument supplies a default value when not included:

def func_b(a, b, *args, h=None, i='', **kwargs):
    if h == None: print('h holds default', h)
    else: print(h)
    print(i, kwargs, sep = ', ')

val = func_b(a, b, c, d, i='custard', j=False, k=True)

output:
    h holds default None
    custard {'j': False, 'k': True}

The argument h is not included in the call so it is initialized with its default value None. Additionally, including the optional parameter**kwargs prefixed with two stars, allows zero or more additional keyword arguments to be passed to the function. These additional arguments are passed as a dict (dictionary)  and access to them is obtained by writing

j = kwargs['j']    # no stars here

for example. If j was not included in the call an error would result so for optional additional key-word arguments we need to write

if 'j' in kwargs:
    j = kwargs['j']
else: 
    j = 'j default'

Tuple function returns

With one notable exception interpretations of the requirement that a function must only return a single value has been a problem in computing from day one. LISP of course provides the exception. Languages that rely on var parameters or the like to sidestep the single return restriction create an environment where mistakes are all too likely. Such languages feature pass by value conjoined with pass by variable address conjoined with pass by reference.

This is fine in a low level language like C where all is explicit, less so in languages that have pretensions towards a level of abstraction. In any event allowing modification of non-locals at diverse points in a function is not conducive to data integrity when there is some obscure error in the logic or when an exception is thrown.

Python's answer is to supply a single return as a tuple of multiple values that can be unpacked transparently to a list of variables:

def swap(a, b):
    return b, a    # construct a tuple and return it

a, b = 1, 2
print(a, b)
a, b = swap(a, b)
print(a, b)

output:
1 2
2 1

If the number of variables in the list does not match the returned tuple an error occurs and thus return of a single item of known composition is maintained.

Transparent construction and unpacking of tuples allows multiple assignments, any to any. So, in reality, a swap function is not required to exchange the values at two variables. The construct

a, b = b, a

is all that is needed.

After all the millions of functions that have been written to modify data using side effects it seems unlikely that tuple returns will see much general usage in the near future but in this series I will use this return type whenever it is indicated.

Summary

In Algorithms 3 and 4 we have looked at the usage and structure of functions and the scope of entities within a program including local and other variables. Lazy evaluation and closures will be considered in Algorithms 5.

[Algorithms 4: Indeterminate arguments, complex returns    (c) Martin Humby 2015]

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]