"Strong typing¤¤"
is the strict enforcement of type rules
"Weak typing¤¤"
is the strict enforcement of type rules but with well-defined exceptions¤
or an explicit type-violation mechanism
Languages may even have "no typing¤"
(for example, assemblers)
Note: The definition of these terms is hard to pin down... the terms are used by different authors in slightly different ways. For instance, ask yourself, "Is C a strongly-typed or weakly-typed language? Why? What do the authors of your programming books say?"
The point to take away from this discussion is that various languages enforce different rules about what may be done with objects and variables of specific types. In some cases these rules may be sufficiently weak to allow the introduction (by the programmer) of errors that will not be reported by the compiler.
Now suppose I define an ADT which represents an automatically ordered list
What functions (behaviours¤)
does it have in common with the list ADT?
What additional functions does it have?
Type Inheritance
We can define the ordered list ADT in terms of the list ADT
OrderedListis aListplus
ordering behaviour
We can represent that relationship as a UML (Unified Modelling Language) diagram:
Inheritance Hierarchies
(Trees)
The "List <- OrderedList" hierarchy¤
is the smallest possible example of inheritance.
Inheritance hierarchies between classes¤
can be much more elaborate trees:
Reminder:
Heap - an ordered tree data-structure in which the values of the children of a node are always less than the value of their parents (i.e. the root of any sub-tree has a greater value than each of its children).
BST (Binary Search Tree) - an ordered tree data-structure in which the values of the left children of a node are less than or equal to the value of their parent and the values of the node's right children are greater than or equal to the value of their parent.
BTree (Balanced? Bayer? Tree) - an ordered tree data-structure in which nodes maintain a number of children within a specified range and in which all leaf nodes are of the same depth.
Things can be classified (abstracted) in many different ways, simultaneously
Hence it is possible for a particular class¤
to inherit from two or more parent classes¤¤
simultaneously:
Inheritance Graphs
In the larger scheme of things, multiple inheritance¤
produces inheritance graphs (rather than trees):
Such graphs must be acyclic. Why?
Inheritance is Transitive
The additional properties conferred by inheritance as passed on to classes¤
which subsequently inherit
Hence we could simplify the previous inheritance graph:
Rather than have each of the Heap, BST and BTree inherit from Ordered, separately, Tree inherits from Ordered and the properties of Ordered can then be passed on to Heap, BST and BTree.
![[Diagram showing a class labelled "List" above a class labelled "OrderedList", with an arrow pointing from "OrderList" to "List"]](inherit1.GIF)
![[Diagram showing the class Container with subclasses List, Tree, and Set. List has subclasses OrderedList and DoublyLinkedList. Tree has classes BST, BTree, AVLTree.]](inherit2.GIF)
![[Diagram showing classes labelled "List" and "Ordered" above a box labelled "OrderedList", with arrows pointing from "OrderList" to both "List" and "Ordered"]](multiple1.GIF)
![[Diagram showing the classes Container, List, Tree, Set, OrderedList, DoublyLinkedList, BST, BTree, and AVLTree (as before). Now, however, classes OrderedList, BST, BTree, and AVLTree also inherit from class Ordered.]](multiple2.GIF)
![[Diagram showing the classes Container, List, Tree, Set, OrderedList, DoublyLinkedList, BST, BTree, and AVLTree (as before). Now, however, classes OrderedList and Tree inherit from class Ordered.]](multiple3.GIF)