CS 131 LECTURE 1 OVERVIEW AND ADA DATA TYPE SYSTEM

Ada Language Concepts

Packages (Specification And Body)

Generic Subprograms And Packages

Variant and Tagged Record Types

Access Types And Dynamic Memory Allocation

Data Structures

Stacks (Last-In First-Out)

Queues (First-In First Out And Priority)

Keyed Tables

Linear Table

Binary Search Table

Hash Table

Binary Trees

Directed Graphs

Algorithms

Algorithm Performance

Searching (Linear And Binary Search)

Sorting

Computer Science As An Engineering Discipline

1. Software Systems Require Design, An Essential Characteristic Of Engineering Fields

2. Computer Systems Are Constructed, The Building Material Is The Programming Language

3. Simplicity Is An Important Design Criterion, Simple Programs Are More Reliable And Easier To Maintain

Software Engineering Goals

1. Correctness and Reliability

2. Readability and Writability

3. Maintainability and Reusability

4. Efficiency

Programming Languages And Software Engineering

1. Ada Is A Language Designed With Software Engineering Principles In Mind

2. Ada's Design Emphasizes Reliability Before Efficiency

3. Ada's Design Emphasizes Readability Before Writability

4. Using A Well Designed Language Can Reduce The Cost Of Software Development

Major Issue:

Software Engineering Principles Promote Simple Program Design

Structured Programming

Structured Programming Simplifies The Statement Level Control Structure Of Programs By Prohibiting Explicit Gotos

Procedural Abstraction

Procedural Abstraction Simplifies Programs By Limiting The Size Of Subprograms

Data Abstraction

Data Abstraction Simplifies Programs By Encapsulating Data Type Definitions Into Packages

Ada And Software Engineering

Ada Supports Structured Programming Because It Contains High Level Statements That Can Be Nested

Ada Supports Procedural Abstraction Because Ada Permits The Definition And Invocation Of Subprograms

Ada Supports Data Encapsulation Because Ada Permits Data Types And Objects To Be Defined Within Packages

Terminology:

Encapsulation: Enclosing A Data Type Definition With The Functions That Define Its Operations

Information Hiding: Concealing The Representation Of A Data Type And The Implement Of Its Operations

Loose Coupling: Building A System Of Software Components With Minimal Interdependencies

Software Reusability: Building General Software Components That Can Be Used In Other Systems

Terminology:

Genericity: Writing Type Independent General Purpose Code

Inheritance: Extending Data Type Definitions By Adding Data Components and Overriding or Adding Operations

Polymorphism: Dispatching An Operation Based On The Type Of Its Parameter

Important Point:

1. Ada 95 Supports Full Object-Oriented Programming, Ada 83 Does Not

Ada Language Defined Data Types

Scalar Data Types

Discrete Types

Integer Types

Enumeration Types

Boolean Type

Character Type

Real Types

Floating Point

Fixed Point

Composite Data Types

Array Types

Record Types

Access Types

User-Defined Data Structures

Stacks And Queues

Lists And Trees

Directed And Undirected Graphs

Important Point:

1. All User-Defined Data Structures Must Be Built From Language Supplied Data Types

Enumeration Type Declarations

Enumeration Type Declarations Create New Data Types Whose Literal Values Are Names, Identifiers

Enumeration Type Declaration Examples

TYPE Days IS (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday);

TYPE Rainbow_Colors IS (Red, Orange, Yellow, Green, Blue, Indigo, Violet);

Enumeration Type Declaration Syntax

enumeration_type_declaration ::=

TYPE identifier ( identifier_list  );

Terminology:

Overloading: The Use Of A Name Or An Operator For More Than One Purpose

Overloaded Enumeration Literals

Ada Permits Enumeration Literals To Be Overloaded, In Addition To Rainbow_Colors, The Following Type Could Be Defined

TYPE Primary_Colors IS (Red, Blue, Yellow);

The Names Red, Blue And Yellow Belong To Two Types

Syntax Rules:

integer_type_definition ::=

RANGE simple_expression  .. simple_expression

floating_point_type_definition ::=

DIGITS static_simple_expression  [range_constraint]

fixed_point_type_definition ::=

DELTA static_simple_expression range_constraint

Sample Type Definitions

TYPE Days_In_Month IS RANGE 1..31;

TYPE Measurement IS DIGITS 10;

TYPE Constrained_Measurement IS DIGITS 10
  RANGE 0.0..100_000.0;

TYPE Dollars IS DELTA 0.01 RANGE
  0.00..1_000.00;

Important Points:

1. User-Defined Integer And Real Types Are Not Type Compatible With The Predefined Types Integer And Float

2. Floating Point Types Specify Uniform Precision, Fixed Point Types Specify Uniform Accuracy

3. Although Intended To Improve Program Portability, These Types Are Not Very Useful In Practice

Array Definition Syntax

array_definition ::=

 ARRAY (discrete_range) OF type

Constrained Array Type Declarations:

-- An Array For Hours Worked For A Week

TYPE Days_Of_Week IS (Mon, Tue, Wed, Thu, Fri, Sat, Sun);

TYPE Hours IS ARRAY(Days_Of_Week) OF Float;

-- An Array To Contain 10 Logical Values

TYPE Boolean_Array IS ARRAY(1..10) OF Boolean;

-- An Array Of Grade Frequencies

SUBTYPE Grades IS INTEGER RANGE 0..100;

TYPE Frequencies IS ARRAY(Grades) OF Natural;

Important Points:

1. Arrays Collect Together Data Elements Of The Same Type

2. The Type Of The Subscripts Must Be A Discrete Type, But The Components May Be Any Type

Syntax Rules:

record_type_definition ::=

RECORD
  component_list
END RECORD

component_list ::=

component_declaration  

{component_declaration} | NULL

component_declaration ::=

identifier_list: type_mark

 [constraint] [:= expression];

Record Type Declaration:

SUBTYPE Hours IS INTEGER RANGE 0..23;

SUBTYPE Minutes IS INTEGER RANGE 0..59;

TYPE Times IS RECORD Hour: Hours; Minute: Minutes; END RECORD;

Important Points:

1. Records Can Collect Together Data Elements Of Different Types

2. Variables Of Record Types With Initialized Components Are Initialized To Those Values

Terminology:

Aggregate: A Literal Constant Which Represents The Value Of A Complete Array Or Record

Array Object Declaration:

Worked: Hours;

Array Aggregates Assignments:

Worked := (4.0,4.0,8.0,8.0,8.0,0.0,0.0);

Worked := (4.0,4.0,8.0,8.0,8.0,OTHERS => 0.0);

Worked := (Sat|Sun => 0.0, Wed..Fri => 8.0, Mon..Tue => 4.0);

Record Object Declaration:

Time: Times;

Positional Aggregate:

Time := (6,45); -- Is Equivalent To
Time.Hour := 6;
Time.Minute := 45;

Named Aggregate:

Time := (Minute => 45, Hour => 6);

Subtype Concept

The Rationale For Using Subtype Declarations Is To Limit The Range Of Values And Detect Out Of Range Conditions If They Should Occur

Subtype Declaration Syntax

subtype_declaration ::=

SUBTYPE identifier IS type RANGE 
simple_expression  ..simple_expression  ;

Subtype Declaration Examples

SUBTYPE Days_In_Month IS Integer RANGE
  1..31;

SUBTYPE Weekdays IS Days_Of_Week RANGE Monday..Friday;

Range Checking Relational Operators

IN Determines Whether A Value Is In A Range

NOT IN Determines Whether A Value Is Not In A Range

Range Checking Expression Examples

3 IN 5..10 False

Wednesday IN Monday..Friday True

40 NOT IN 1..10 True

Major Issue:

1. Ada Uses Name Equivalence, Two Objects Are Of The Same Type If They Have The Same Type Name

Syntax Rule:

derived_type_definition ::=

NEW type [constraint]

Sample Type Definitions

TYPE Derived_Days_In_Month IS NEW
  Integer RANGE 1..31;

TYPE New_Float IS NEW Float;

TYPE Upper_Case_Letters IS NEW Character RANGE 'A'..'Z';

Important Points:

1. Derived Types Are Type Incompatible With Their Base Types

2. User-Defined Numeric Types Are Implicit Derived Types

3. Derived Types Inherit The Operations Of The Base Type, Inheritance Is Important In Object-Oriented Programming

4. Subtypes Only Restrict The Range Of Values, They Do Not Create A New Type Name