Notes

Outline

High Level Languages Assembly language programming Too time consuming and error prone Target dependent, not portable High level languages Target independent More convenient way to express algorithms Examples: COBOL, FORTRAN Better control mechanisms than assembler: loops, if-then-else  etc., array and matrix manipulation More readable, people could write billions of lines of code! Limited support for data structures Structures or records  C, Pascal More support for data structures, user defined types, but do not  fully enforce type checking Explicit support for pointers in both languages C  uses symbol * to indicate a variable holds a pointer int * variable Pascal introduces a symbol ^ for pointers variable : ^integer variable is a pointer to another variable of type integer

High Level Languages (cont.) High level languages (cont.) C vs. Pascal In Pascal the pointer is bound to its type, in C its not enforced! Parameters by value and reference Pascal supports parameters by reference and value using a keyword routine (var a : integer; b integer) a := b; variables are referenced in same way to call routine(A,B) C requires addressing modes for variables instead routine (int * a,  int b) (*a) = b; to call routine(&in_a,in_b) Addressing symbols let you do more fancy things in C but they are error prone With these higher level languages and more experience with software the notions of information hiding developed for defining software components When choosing software components, maximize cohesion and minimize coupling! Led to the notion of an abstract data type

Data Type Data type = data structure + operations on the data Stack examples: Data structure, could be an array or linked list Operations: init, push, pop For example #define STACK_SIZE 100 typedef structure { int stack_pointer; int stack[STACK_SIZE]; } int_stack_type; int_stack_type a; ; define a variable of                                              ; type stack void init_stack(int_stack_type * a){ (*a).stack_pointer = 0; } int push(int_stack_type * a, int value){ (*a).stack[((*a).stack_pointer)++] = value; if ((*a).stack_pointer > STACK_SIZE) return (0); else return(1); }

Typical Data Types Stacks Init, Push, Pop Lists Init, Add, Remove, Head, Tail Queues (could be based on priorities) Init, Add, Remove Sets Init, Add, Remove, Union, Intersection Trees of various kinds Init, Add, Remove We can use these in our programs without knowing how the data is represented A list could be implemented using a stack, a stack could be implemented using a list and so on…. The interface to the data type’s operations is all we need

Algebraic Specification Specifying abstract types in terms of relationships between type operations Popular descriptive specification style used to define a system as a heterogeneous algebra (a collection of different sets on which several operations are defined) Specification is quite close to the notion of abstract data types module that exports a type along with the operations that must be invoked to access and manipulate objects of that type hides the representation of the type and the algorithms used in the operations

Specification Structure Introduction Introduces the type name and imported specifications Informal description Describes the type operations Signature Defines the syntax of the type operations Axioms Defines axioms which characterize the behaviour of the type

Specification Operations Constructor operations. Operations which create entities of the type being specified Inspection operations. Operations which evaluate entities of the type being specified To specify behaviour, define the inspector operations for each constructor operation

Operations on a List ADT Constructor operations which evaluate to type List Create, Cons and Tail Inspection operations which take type list as a parameter and return some other type Head and Length. Tail can be defined using the simpler constructors Create and Cons. No need to define Head and Length with Tail.

List Specification Introduction Type List Imports Integer Informal description: Defines a list where elements are added at the end and removed from the front. The operations are Create, which brings an empty list into existence, Cons, which creates a new list with an added member, Length, which evaluates the list size, Head, which evaluates the front element of the list, and Tail, which creates a list by removing the head from its input list. Signature Create -> List Cons(List, Elem) -> List Tail(List) -> List Head(List) -> Elem Length(List) -> Integer Axioms Head(Create) = Undefined Head(Cons(L,v)) = if L = Create then v else Head(L) Length(Create) = 0 Length(Cons(L,v)) = Length(L) + 1 Tail(Create) = Create Tail(Cons(L,v)) = if L = Create then Create else Cons(Tail(L),v)

Recursion in Specifications Operations are often specified recursively Tail (Cons (L, v)) = if L = Create then Create else Cons (Tail (L), v) Cons ([5, 7], 9) = [5, 7, 9] Tail ([5, 7, 9])  = Tail (Cons ( [5, 7], 9))  = Cons (Tail ([5, 7]), 9) = Cons (Tail (Cons ([5], 7)), 9) = Cons (Cons (Tail ([5]), 7), 9) = Cons (Cons (Tail (Cons ([], 5)), 7), 9) = Cons (Cons (Create, 7), 9) = Cons ([7], 9) = [7, 9]

Primitive Constructors It is sometimes necessary to introduce additional constructors to simplify the specification The other constructors can then be defined using these more primitive constructors In the binary tree specification, a primitive constructor Build is added

Operations on a Binary Tree

Binary Tree Specification Introduction Type Binary_tree Imports Boolean Informal description: Defines a binary tree where the data is of generic type Elem. See previous transparency for interface operation descriptions. Build is an additional primitive constructor operation which is introduced to simplify the specification. It builds a tree given the value of anode and the left and right sub-trees. Signature Create -> Binary_tree Add(Binary_tree, Elem) -> Binary_tree Left(Binary_tree) -> Binary_tree Data(Binary_tree) -> Elem Right(Binary_tree) -> Binary_tree Is_empty(Binary_tree) -> Boolean Contains(Binary_tree, Elem) -> Boolean Build(Binary_tree, Elm, Binary_tree) -> Binary_tree

Binary Tree Specification (cont.) Axioms Add(Create, E) = Build(Create, E, Create) Add(B, E) =   if E < Data(B) then Add(Left(B),E)           else Add(Right(B),E) Left(Create) = Create Right(Create) = Create Data(Create) = Undefined Left(Build(L,D,R)) = L Right(Build(L,D,R)) = R Data(Build(L,D,R) = D Is_empty(Create) = true Is_empty(Build(L,D,R)) = false Contains(Create,E) = false Contains(Build(L,D,R),E) = if E = D then true               else if E < D then Contains(L,E)    else Contains(R,E)

Specification Enrichment Starting with a reusable specification building block, new operations are added to create a more complex type Enrichment can be continued to any number of  levels. It is comparable to inheritance (will be discussed later) Not the same as importing a specification Importing makes a specification available for use Enrichment creates a specification for a new type The names of the generic parameters of the base type are inherited when a type is enriched

Operations on New_list

New_list Specification Introduction Type New_list enrich List Imports Integer, Boolean Informal description: Defines an extended form of list which inherits the operations and properties of the simpler specification of List and which adds new operations (Add and Member) to these. See previous transparency for a description of these operations. Signature Add (New_list, Elem) -> New_list Member(New_list, Elem) -> Boolean Axioms Tail(Add(L, v)) = L Member(Create, v) = false Member(Add(L, v), v1) = ((v == v1) or Member(L, v1)) Member(Cons(L, v), v1) = ((v == v1) or Member(L, v1)) Head(Add(L, v)) = v Length(Add(L, v)) = Length(L) + 1

Multi-value Operations Some operations affect more than one entity. Logically, a function returns more than one value Stack pop operation returns both the value popped from the stack AND the modified stack May be modeled algebraically using multiple operations (TOP and RETRACT for a stack) but a more intuitive approach is to define operations which return a tuple rather than a single value

Queue Operations

Queue Specification Introduction Type Queue enrich List Imports Integer Informal description: This specification defines a queue which is a first-in, first-out data structure. It can therefore be specified as a List where the insert operation adds a member to the end of the queue. See the previous transparency for a description of the operations Signature Get(Queue) -> (Elem, Queue) Axioms Get(Create) = (Undefined, Create) Get(Cons(Q,v)) = (Head(Cons(Q,v)), Tail(Cons(Q,v)))

Key points Algebraic specification involves specifying operations on an abstract data type or object in terms of their inter-relationships An algebraic specification has a signature part defining syntax and an axioms part defining semantics Formal specifications should have an associated informal description to make them more readable Algebraic specifications may be defined by defining the semantics of each inspection operation for each constructor operation Specification should be developed incrementally from simpler specification building blocks

High Level Languages (cont.) Ada Ada specified by committee supported by U.S. DoD Strong type checking, must explicitly type cast between variables of different types For ex: cannot assign a ptr to char to a ptr to an int Tedious but really makes sure that you meant to assign one type to another No aliasing permitted! Why? Avoid many of the problems associated with maintaining C code, many coding errors are avoided when strong typing is enforced Ada has the notion of packages Data and operations Some data and operations can be made private: they can only be referenced within the package (no longer rely on the benevolence of programmers!) Provides better support for abstract data types Ada also has generics Templates that are a cross between packages and macros Can write a generic for a stack_type, then instantiate instances of the packages for any user specified type For ex: int, real, colours, customer_type,.... Saves you from writing, debugging, and maintaining identical code for different types

Object-Orientation Take the notion of a data type a step further than Ada by providing support for inheritance (will be discussed later) Class = data + operations on the data Can have many instances of objects of the class For ex: C++ Can have a class with data only class Employee {public: char name[NAME_LENGTH]; char sin[SIN_LENGTH]; short age; float salary; }; To use: Employee An_Employee; // defines an object named An_Employee , it is an instance of the class Employee An_Employee.salary  references the attribute salary of this instance of the class

Objects with Data and Functions We can augment the class to include operations and hide the data structures class Employee { public: .....    get_name(char * name); set_name(char * name);    void display(); private: char name[NAME_LENGTH]; char sin[SIN_LENGTH]; short age; float salary; }; This gives us solid support for data types and is often referred to as encapsulation Saves us a lot of grief if we change the insides of an object, as long as the interface stays the same users of the object will not be affected To reference an operation: An_employee.get_name(&name)

Stack Example in C++ class int_stack { // class name public:   int_stack() = {my_stack = NULL};// default constructor   void push(int a);   int pop();   void init(); private:   int_list my_stack; }; If  list is another class, then its default constructor could initialize my_stack to NULL so that int_stack would not have to We define the implementation of the methods as follows void int_stack::push(int a){ // regular C++ code } We no longer need to pass an explicit reference to the stack since we access using the stack variable: int_stack My_stack; My_stack.push(2);

Template Example in C++ With C++ we access the reference to the stack directly from its variable We can also parameterize classes (like Ada generics) so that their specification can be used to support many types For example: template <class T> class stack { // class name public:   int_stack() = {my_stack = NULL}; // default constructor   void push(T a);   T pop();   void init(); private:   list<T> my_stack;  // my stack relies on a template for list }; To instantiate an instance of a stack of integers: stack<int> My_int_stack; stack<double> My_double_stack;

Building up Classes Composition Build up objects from other objects directly class calculator {public: .... panel calculator_panel; // panel is another class keypad calculator_keypad; // keypad is another class .....} To use: My_calculator.calculator_panel.reset(); Languages that support encapsulation alone but not inheritance are often called object-based With Inheritance a language is called object-oriented Inheritance allows the derivation of a similar or related object (derived object) from another object (base object) Only specify things that are added to the base class class Manager_Employee: public Employee {public: set_management_level(...) private: management_level_type management_level; ....}

Inheritance and Overloading Single inheritance Inherit from a single base class Multiple inheritance Inherit from many base classes class calculator: public panel, public keypad {public: .... } To use: My_calculator.reset(); My_calculator.display(); What if both keypad and panel have a reset method? Compile time error! What if base objects have instances of the same private data? Notion of virtual members and functions

Overloading Overloading Assignment of multiple duties to functions and operators For ex: “+” may mean Addition of two integers, addition of two doubles, addition of an integer with a double, or adding an element onto a list, or whatever we define it as Compiler needs enough information to decide which it is! The signature must be distinct Signature = number and types of parameters The following all have distinct signatures int power(int a, int n); int power(int  a, unsigned n); double power (int a, int n); double power(float a, int n); double power(generator_type gen); unsigned int a,b, c;  =>  c = power(a,b) = ?

Polymorphism Polymorphism To operate on multiple classes in an identical manner Car, truck, boat, airplane may all have the same operations Open fuel bay Close fuel bay Tank is full Tank is low The operation fill_tank may work with all of them Code that operates on many classes using their commonly defined methods is polymorphic Common methods: inherited from common ancestor

Polymorphism class vehicle { public:    virtual void fill_tank(); // allows us to override fill_tank later    …... } class car: public vehicle { public:   void fill_tank();    …... } class boat: public vehicle { public:   void fill_tank();   …... } void do_something(vehicle v) { …. v.fill_tank(); …. } <--- generate code to call which operation? car porsche; do_something (porsche); <--- use car FILL_TANK! boat qe2; do_something(qe2); <--- use boat FILL_TANK!

Summary Assembly Target dependent, virtually no type information Initial high-level languages Target independence Some supports for useful types Data structures User defined types Data types Data structure + operations Object based Encapsulation of data and operations Generics Object oriented Inheritance Polymorphism