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