程序代写代做代考 compiler data structure concurrency html chain ada Haskell Systems, Networks & Concurrency 2019

Systems, Networks & Concurrency 2019
Language refresher / introduction course Uwe R. Zimmer – The Australian National University

Language refresher / introduction course
[Ada 2012 Language Reference Manual]
[Chapel 1.13 Language Specification Version 0.981]
see course pages or
References for this chapter
see course pages or http://www.ada-auth.org/standards/ada12.html
http://chapel.cray.com/docs/latest/_downloads/chapelLanguageSpec.pdf
released on 7. April 2016
© 2019 Uwe R. Zimmer, The Australian National University page 20 of 757 (“Language refresher / introduction course” up to page 159)

Language refresher / introduction course
Languages explicitly supporting concurrency: e.g. Ada
Ada is an ISO standardized (ISO/IEC 8652:201x(E)) ‘general purpose’ language with focus on “program reliability and maintenance, programming as a human activity, and efficiency”.
It provides core language primitives for:
• Strong typing, contracts, separate compilation (specification and implementation),
abstract data types, generics, object-orientation.
• Concurrency, message passing, synchronization, monitors, rpcs, timeouts, scheduling, priority ceiling locks, hardware mappings, fully typed network communication.
• Strong run-time environments (incl. stand-alone execution). … as well as standardized language-annexes for:
• Additional real-time features, distributed programming, system-level programming, numeric, informations systems, safety and security issues.
© 2019 Uwe R. Zimmer, The Australian National University page 21 of 757 (“Language refresher / introduction course” up to page 159)

Language refresher / introduction course
… refreshing for some, x’th-language introduction for others:
• Specification and implementation (body) parts, basic types
• Exceptions
• Information hiding in specifications (‘private’)
• Contracts
• Generic programming (polymorphism)
• Tasking
• Monitors and synchronisation (‘protected’, ‘entries’, ‘selects’, ‘accepts’)
• Abstract types and dispatching
Not mentioned here: general object orientation, dynamic memory management, foreign language interfaces, marshalling, basics of imperative programming, …
Ada
A crash course
© 2019 Uwe R. Zimmer, The Australian National University page 22 of 757 (“Language refresher / introduction course” up to page 159)

Ring lists
Forms of implementation:
Enqueue
Dequeue
Dequeue
Enqueue
© 2019 Uwe R. Zimmer, The Australian National University
page 23 of 757 (chapter 2: “Language refresher / introduction course” up to page 159)
Language refresher / introduction course
Dequeue
Enqueue
Data structure example
Queues
In
Out

Almost impossible for real-time systems.
Best suited for real-time systems.
Potentially suited for real-time sys- tems if distributed storage is required and memory can be pre-allocated.
Forms of implementation:
Enqueue
Dequeue
Dequeue
Enqueue
© 2019 Uwe R. Zimmer, The Australian National University
page 24 of 757 (chapter 2: “Language refresher / introduction course” up to page 159)
Language refresher / introduction course
Dequeue
Enqueue
Data structure example
Queues
In
Out

… introducing:
Language refresher / introduction course
• Specification and implementation (body) parts • Constants
• Some basic types (integer specifics)
• Some type attributes
• Parameter specification
Ada
Basics
© 2019 Uwe R. Zimmer, The Australian National University page 25 of 757 (“Language refresher / introduction course” up to page 159)

Language refresher / introduction course
package Queue_Pack_Simple is
QueueSize : constant Positive := 10;
type Element type Marker type List
is new Positive range 1_000..40_000; is mod QueueSize;
is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First; Is_Empty : Boolean := True; Elements : List;
A simple queue specification
end record;
procedure Enqueue (Item: Element; Queue: in out Queue_Type);
procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean; end Queue_Pack_Simple;
© 2019 Uwe R. Zimmer, The Australian National University page 26 of 757 (“Language refresher / introduction course” up to page 159)

Specifications define an interface to provided types and operations.
Syntactically enclosed in a package block.
Language refresher / introduction course
package Queue_Pack_Simple is
QueueSize : constant Positive := 10;
type Element type Marker type List
is new Positive range 1_000..40_000; is mod QueueSize;
is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First; Is_Empty : Boolean := True; Elements : List;
A simple queue specification
end record;
procedure Enqueue (Item: Element; Queue: in out Queue_Type);
procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean; end Queue_Pack_Simple;
© 2019 Uwe R. Zimmer, The Australian National University page 27 of 757 (“Language refresher / introduction course” up to page 159)

Variables should be initialized. Constants must be initialized.
Assignments are denoted by the “:=” symbol.
… leaving the “=” symbol for comparisons.
Language refresher / introduction course
package Queue_Pack_Simple is
QueueSize : constant Positive := 10;
type Element type Marker type List
is new Positive range 1_000..40_000; is mod QueueSize;
is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First; Is_Empty : Boolean := True; Elements : List;
A simple queue specification
end record;
procedure Enqueue (Item: Element; Queue: in out Queue_Type);
procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean; end Queue_Pack_Simple;
© 2019 Uwe R. Zimmer, The Australian National University page 28 of 757 (“Language refresher / introduction course” up to page 159)

Default initializations can be selected to be:
as is (random memory content), initialized to invalids, e.g. 999
or valid, predicable values, e.g. 1_000
Language refresher / introduction course
package Queue_Pack_Simple is
QueueSize : constant Positive := 10;
type Element type Marker type List
is new Positive range 1_000..40_000; is mod QueueSize;
is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First; Is_Empty : Boolean := True; Elements : List;
A simple queue specification
end record;
procedure Enqueue (Item: Element; Queue: in out Queue_Type);
procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean; end Queue_Pack_Simple;
© 2019 Uwe R. Zimmer, The Australian National University page 29 of 757 (“Language refresher / introduction course” up to page 159)

Numerical types can be specified by:
range, modulo,
number of digits ( floating point) or delta increment ( fixed point).
Always be as specific as the language allows.
… and don’t repeat yourself!
Language refresher / introduction course
package Queue_Pack_Simple is
QueueSize : constant Positive := 10;
type Element type Marker type List
is new Positive range 1_000..40_000; is mod QueueSize;
is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First; Is_Empty : Boolean := True; Elements : List;
A simple queue specification
end record;
procedure Enqueue (Item: Element; Queue: in out Queue_Type);
procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean; end Queue_Pack_Simple;
© 2019 Uwe R. Zimmer, The Australian National University page 30 of 757 (“Language refresher / introduction course” up to page 159)

All types come with a long list of built-in attributes.
Let the compiler fill in what you already (implicitly) specified!
Language refresher / introduction course
package Queue_Pack_Simple is
QueueSize : constant Positive := 10;
type Element type Marker type List
is new Positive range 1_000..40_000; is mod QueueSize;
is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First; Is_Empty : Boolean := True; Elements : List;
A simple queue specification
end record;
procedure Enqueue (Item: Element; Queue: in out Queue_Type);
procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean; end Queue_Pack_Simple;
© 2019 Uwe R. Zimmer, The Australian National University page 31 of 757 (“Language refresher / introduction course” up to page 159)

Parameters can be passed as ‘in’ (default), ‘out’
or ‘in out’.
Language refresher / introduction course
package Queue_Pack_Simple is
QueueSize : constant Positive := 10;
type Element type Marker type List
is new Positive range 1_000..40_000; is mod QueueSize;
is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First; Is_Empty : Boolean := True; Elements : List;
A simple queue specification
end record;
procedure Enqueue (Item: Element; Queue: in out Queue_Type);
procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean; end Queue_Pack_Simple;
© 2019 Uwe R. Zimmer, The Australian National University page 32 of 757 (“Language refresher / introduction course” up to page 159)

All specifications are used in
Code optimizations (optional), Compile time checks (mandatory) Run-time checks (suppressible).
Language refresher / introduction course
package Queue_Pack_Simple is
QueueSize : constant Positive := 10;
type Element type Marker type List
is new Positive range 1_000..40_000; is mod QueueSize;
is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First; Is_Empty : Boolean := True; Elements : List;
A simple queue specification
end record;
procedure Enqueue (Item: Element; Queue: in out Queue_Type);
procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean; end Queue_Pack_Simple;
© 2019 Uwe R. Zimmer, The Australian National University page 33 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
Language refresher / introduction course
package Queue_Pack_Simple is
QueueSize : constant Positive := 10;
type Element type Marker type List
is new Positive range 1_000..40_000; is mod QueueSize;
is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First; Is_Empty : Boolean := True; Elements : List;
A simple queue specification
end record;
procedure Enqueue (Item: Element; Queue: in out Queue_Type);
procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean; end Queue_Pack_Simple;
© 2019 Uwe R. Zimmer, The Australian National University page 34 of 757 (“Language refresher / introduction course” up to page 159)

Language refresher / introduction course
package body Queue_Pack_Simple is
A simple queue implementation
procedure Enqueue (Item: Element; Queue: in out Queue_Type) is
begin
Queue.Elements (Queue.Free) := Item;
Queue.Free := Queue.Free + 1;
Queue.Is_Empty := False;
end Enqueue;
procedure Dequeue (Item: out Element; Queue: in out Queue_Type) is
begin
Item := Queue.Elements (Queue.Top);
Queue.Top := Queue.Top + 1;
Queue.Is_Empty := Queue.Top = Queue.Free;
end Dequeue;
function Is_Empty (Queue : Queue_Type) return Boolean is
(Queue.Is_Empty);
function Is_Full (Queue : Queue_Type) return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free);
end Queue_Pack_Simple;
© 2019 Uwe R. Zimmer, The Australian National University page 35 of 757 (“Language refresher / introduction course” up to page 159)

Implementations are defined in a separate file.
Syntactically enclosed in a package body block.
Language refresher / introduction course
package body Queue_Pack_Simple is
A simple queue implementation
procedure Enqueue (Item: Element; Queue: in out Queue_Type) is
begin
Queue.Elements (Queue.Free) := Item;
Queue.Free := Queue.Free + 1;
Queue.Is_Empty := False;
end Enqueue;
procedure Dequeue (Item: out Element; Queue: in out Queue_Type) is
begin
Item := Queue.Elements (Queue.Top);
Queue.Top := Queue.Top + 1;
Queue.Is_Empty := Queue.Top = Queue.Free;
end Dequeue;
function Is_Empty (Queue : Queue_Type) return Boolean is
(Queue.Is_Empty);
function Is_Full (Queue : Queue_Type) return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free);
end Queue_Pack_Simple;
© 2019 Uwe R. Zimmer, The Australian National University page 36 of 757 (“Language refresher / introduction course” up to page 159)

Modulo type, hence no index checks required.
Language refresher / introduction course
package body Queue_Pack_Simple is
A simple queue implementation
procedure Enqueue (Item: Element; Queue: in out Queue_Type) is
begin
Queue.Elements (Queue.Free) := Item;
Queue.Free := Queue.Free + 1;
Queue.Is_Empty := False;
end Enqueue;
procedure Dequeue (Item: out Element; Queue: in out Queue_Type) is
begin
Item := Queue.Elements (Queue.Top);
Queue.Top := Queue.Top + 1;
Queue.Is_Empty := Queue.Top = Queue.Free;
end Dequeue;
function Is_Empty (Queue : Queue_Type) return Boolean is
(Queue.Is_Empty);
function Is_Full (Queue : Queue_Type) return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free);
end Queue_Pack_Simple;
© 2019 Uwe R. Zimmer, The Australian National University page 37 of 757 (“Language refresher / introduction course” up to page 159)

Boolean expressions
Language refresher / introduction course
package body Queue_Pack_Simple is
A simple queue implementation
procedure Enqueue (Item: Element; Queue: in out Queue_Type) is
begin
Queue.Elements (Queue.Free) := Item;
Queue.Free := Queue.Free + 1;
Queue.Is_Empty := False;
end Enqueue;
procedure Dequeue (Item: out Element; Queue: in out Queue_Type) is
begin
Item := Queue.Elements (Queue.Top);
Queue.Top := Queue.Top + 1;
Queue.Is_Empty := Queue.Top = Queue.Free;
end Dequeue;
function Is_Empty (Queue : Queue_Type) return Boolean is
(Queue.Is_Empty);
function Is_Full (Queue : Queue_Type) return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free);
end Queue_Pack_Simple;
© 2019 Uwe R. Zimmer, The Australian National University page 38 of 757 (“Language refresher / introduction course” up to page 159)

Side-effect free,
single expression functions
can be expressed with- out begin-end blocks.
Language refresher / introduction course
package body Queue_Pack_Simple is
A simple queue implementation
procedure Enqueue (Item: Element; Queue: in out Queue_Type) is
begin
Queue.Elements (Queue.Free) := Item;
Queue.Free := Queue.Free + 1;
Queue.Is_Empty := False;
end Enqueue;
procedure Dequeue (Item: out Element; Queue: in out Queue_Type) is
begin
Item := Queue.Elements (Queue.Top);
Queue.Top := Queue.Top + 1;
Queue.Is_Empty := Queue.Top = Queue.Free;
end Dequeue;
function Is_Empty (Queue : Queue_Type) return Boolean is
(Queue.Is_Empty);
function Is_Full (Queue : Queue_Type) return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free);
end Queue_Pack_Simple;
© 2019 Uwe R. Zimmer, The Australian National University page 39 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
Language refresher / introduction course
package body Queue_Pack_Simple is
A simple queue implementation
procedure Enqueue (Item: Element; Queue: in out Queue_Type) is
begin
Queue.Elements (Queue.Free) := Item;
Queue.Free := Queue.Free + 1;
Queue.Is_Empty := False;
end Enqueue;
procedure Dequeue (Item: out Element; Queue: in out Queue_Type) is
begin
Item := Queue.Elements (Queue.Top);
Queue.Top := Queue.Top + 1;
Queue.Is_Empty := Queue.Top = Queue.Free;
end Dequeue;
function Is_Empty (Queue : Queue_Type) return Boolean is
(Queue.Is_Empty);
function Is_Full (Queue : Queue_Type) return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free);
end Queue_Pack_Simple;
© 2019 Uwe R. Zimmer, The Australian National University page 40 of 757 (“Language refresher / introduction course” up to page 159)

begin
Enqueue (2000, Queue);
Dequeue (Item, Queue);
Dequeue (Item, Queue);
end Queue_Test_Simple;
© 2019 Uwe R. Zimmer, The Australian National University
page 41 of 757 (“Language refresher / introduction course” up to page 159)
Language refresher / introduction course
with Queue_Pack_Simple; use Queue_Pack_Simple; procedure Queue_Test_Simple is
Queue : Queue_Type;
Item : Element;
A simple queue test program

Importing items from other packages is done with with-clauses.
use-clauses allow to use names with qualifying them with the package name.
begin
Enqueue (2000, Queue);
Dequeue (Item, Queue);
Dequeue (Item, Queue);
end Queue_Test_Simple;
© 2019 Uwe R. Zimmer, The Australian National University
page 42 of 757 (“Language refresher / introduction course” up to page 159)
Language refresher / introduction course
with Queue_Pack_Simple; use Queue_Pack_Simple; procedure Queue_Test_Simple is
Queue : Queue_Type;
Item : Element;
A simple queue test program

A top level procedure is read as the code which needs to be executed.
begin
Enqueue (2000, Queue);
Dequeue (Item, Queue);
Dequeue (Item, Queue);
end Queue_Test_Simple;
© 2019 Uwe R. Zimmer, The Australian National University
page 43 of 757 (“Language refresher / introduction course” up to page 159)
Language refresher / introduction course
with Queue_Pack_Simple; use Queue_Pack_Simple; procedure Queue_Test_Simple is
Queue : Queue_Type;
Item : Element;
A simple queue test program

Variables are declared Algol style: “Item is of type Element”.
begin
Enqueue (2000, Queue);
Dequeue (Item, Queue);
Dequeue (Item, Queue);
end Queue_Test_Simple;
© 2019 Uwe R. Zimmer, The Australian National University
page 44 of 757 (“Language refresher / introduction course” up to page 159)
Language refresher / introduction course
with Queue_Pack_Simple; use Queue_Pack_Simple; procedure Queue_Test_Simple is
Queue : Queue_Type;
Item : Element;
A simple queue test program

Will produce a result according to the chosen initialization:
Raises an “invalid data” exception if initialized to invalids.
… hmm, ok … so this was rubbish …
begin
Enqueue (2000, Queue);
Dequeue (Item, Queue);
Dequeue (Item, Queue);
end Queue_Test_Simple;
© 2019 Uwe R. Zimmer, The Australian National University
page 45 of 757 (“Language refresher / introduction course” up to page 159)
Language refresher / introduction course
with Queue_Pack_Simple; use Queue_Pack_Simple; procedure Queue_Test_Simple is
Queue : Queue_Type;
Item : Element;
A simple queue test program

… anything on this slide still not perfectly clear?
begin
Enqueue (2000, Queue);
Dequeue (Item, Queue);
Dequeue (Item, Queue);
end Queue_Test_Simple;
© 2019 Uwe R. Zimmer, The Australian National University
page 46 of 757 (“Language refresher / introduction course” up to page 159)
Language refresher / introduction course
with Queue_Pack_Simple; use Queue_Pack_Simple; procedure Queue_Test_Simple is
Queue : Queue_Type;
Item : Element;
A simple queue test program

… introducing:
Language refresher / introduction course
• Exception handling
• Enumeration types
• Type attributed operators
© 2019 Uwe R. Zimmer, The Australian National University
page 47 of 757 (“Language refresher / introduction course” up to page 159)
Ada
Exceptions

Language refresher / introduction course
A queue specification with proper exceptions
package Queue_Pack_Exceptions is QueueSize : constant Positive := 10;
type Element type Marker type List
is (Up, Down, Spin, Turn);
is mod QueueSize;
is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First; Is_Empty : Boolean := True; Elements : List;
end record;
procedure Enqueue (Item: Element; Queue: in out Queue_Type);
procedure Dequeue (Item: out Element; Queue: in out Queue_Type);
function Is_Empty (Queue : Queue_Type) return Boolean is (Queue.Is_Empty); function Is_Full (Queue : Queue_Type) return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free); Queue_overflow, Queue_underflow : exception;
end Queue_Pack_Exceptions;
© 2019 Uwe R. Zimmer, The Australian National University page 48 of 757 (“Language refresher / introduction course” up to page 159)

Enumeration types are first- class types and can be used e.g. as array indices.
The representation values can be controlled and do not need to be continuous (e.g. for purposes like interfacing with hardware).
Language refresher / introduction course
A queue specification with proper exceptions
package Queue_Pack_Exceptions is QueueSize : constant Positive := 10;
type Element type Marker type List
is (Up, Down, Spin, Turn);
is mod QueueSize;
is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First; Is_Empty : Boolean := True; Elements : List;
end record;
procedure Enqueue (Item: Element; Queue: in out Queue_Type);
procedure Dequeue (Item: out Element; Queue: in out Queue_Type);
function Is_Empty (Queue : Queue_Type) return Boolean is (Queue.Is_Empty); function Is_Full (Queue : Queue_Type) return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free); Queue_overflow, Queue_underflow : exception;
end Queue_Pack_Exceptions;
© 2019 Uwe R. Zimmer, The Australian National University page 49 of 757 (“Language refresher / introduction course” up to page 159)

Nothing else changes in the specifications.
Exceptions need to be declared.
Language refresher / introduction course
A queue specification with proper exceptions
package Queue_Pack_Exceptions is QueueSize : constant Positive := 10;
type Element type Marker type List
is (Up, Down, Spin, Turn);
is mod QueueSize;
is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First; Is_Empty : Boolean := True; Elements : List;
end record;
procedure Enqueue (Item: Element; Queue: in out Queue_Type);
procedure Dequeue (Item: out Element; Queue: in out Queue_Type);
function Is_Empty (Queue : Queue_Type) return Boolean is (Queue.Is_Empty); function Is_Full (Queue : Queue_Type) return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free); Queue_overflow, Queue_underflow : exception;
end Queue_Pack_Exceptions;
© 2019 Uwe R. Zimmer, The Australian National University page 50 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
Language refresher / introduction course
A queue specification with proper exceptions
package Queue_Pack_Exceptions is QueueSize : constant Positive := 10;
type Element type Marker type List
is (Up, Down, Spin, Turn);
is mod QueueSize;
is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First; Is_Empty : Boolean := True; Elements : List;
end record;
procedure Enqueue (Item: Element; Queue: in out Queue_Type);
procedure Dequeue (Item: out Element; Queue: in out Queue_Type);
function Is_Empty (Queue : Queue_Type) return Boolean is (Queue.Is_Empty); function Is_Full (Queue : Queue_Type) return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free); Queue_overflow, Queue_underflow : exception;
end Queue_Pack_Exceptions;
© 2019 Uwe R. Zimmer, The Australian National University page 51 of 757 (“Language refresher / introduction course” up to page 159)

A queue implementation with proper exceptions
package body Queue_Pack_Exceptions is
procedure Enqueue (Item : Element; Queue : in out Queue_Type) is
begin
if Is_Full (Queue) then
raise Queue_overflow; end if;
Queue.Elements (Queue.Free) := Item;
Queue.Free := Marker’Succ (Queue.Free);
Queue.Is_Empty := False;
end Enqueue;
procedure Dequeue (Item : out Element; Queue : in out Queue_Type) is
begin
if Is_Empty (Queue) then
raise Queue_underflow; end if;
Item := Queue.Elements (Queue.Top);
Queue.Top := Marker’Succ (Queue.Top);
Queue.Is_Empty := Queue.Top = Queue.Free;
end Dequeue;
end Queue_Pack_Exceptions;
© 2019 Uwe R. Zimmer, The Australian National University page 52 of 757 (“Language refresher / introduction course” up to page 159)

Raised exceptions break the control
flow and “propagate” to the closest “exception handler” in the call-chain.
A queue implementation with proper exceptions
package body Queue_Pack_Exceptions is
procedure Enqueue (Item : Element; Queue : in out Queue_Type) is
begin
if Is_Full (Queue) then
raise Queue_overflow; end if;
Queue.Elements (Queue.Free) := Item;
Queue.Free := Marker’Succ (Queue.Free);
Queue.Is_Empty := False;
end Enqueue;
procedure Dequeue (Item : out Element; Queue : in out Queue_Type) is
begin
if Is_Empty (Queue) then
raise Queue_underflow; end if;
Item := Queue.Elements (Queue.Top);
Queue.Top := Marker’Succ (Queue.Top);
Queue.Is_Empty := Queue.Top = Queue.Free;
end Dequeue;
end Queue_Pack_Exceptions;
© 2019 Uwe R. Zimmer, The Australian National University page 53 of 757 (“Language refresher / introduction course” up to page 159)

All Types come with a long list of built-in operators.
Syntactically expressed as attributes.
Type attributes often make code more generic: ‘Succ works for instance on enumeration types as well … “+ 1” does not.
A queue implementation with proper exceptions
package body Queue_Pack_Exceptions is
procedure Enqueue (Item : Element; Queue : in out Queue_Type) is
begin
if Is_Full (Queue) then
raise Queue_overflow; end if;
Queue.Elements (Queue.Free) := Item;
Queue.Free := Marker’Succ (Queue.Free);
Queue.Is_Empty := False;
end Enqueue;
procedure Dequeue (Item : out Element; Queue : in out Queue_Type) is
begin
if Is_Empty (Queue) then
raise Queue_underflow; end if;
Item := Queue.Elements (Queue.Top);
Queue.Top := Marker’Succ (Queue.Top);
Queue.Is_Empty := Queue.Top = Queue.Free;
end Dequeue;
end Queue_Pack_Exceptions;
© 2019 Uwe R. Zimmer, The Australian National University page 54 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
A queue implementation with proper exceptions
package body Queue_Pack_Exceptions is
procedure Enqueue (Item : Element; Queue : in out Queue_Type) is
begin
if Is_Full (Queue) then
raise Queue_overflow; end if;
Queue.Elements (Queue.Free) := Item;
Queue.Free := Marker’Succ (Queue.Free);
Queue.Is_Empty := False;
end Enqueue;
procedure Dequeue (Item : out Element; Queue : in out Queue_Type) is
begin
if Is_Empty (Queue) then
raise Queue_underflow; end if;
Item := Queue.Elements (Queue.Top);
Queue.Top := Marker’Succ (Queue.Top);
Queue.Is_Empty := Queue.Top = Queue.Free;
end Dequeue;
end Queue_Pack_Exceptions;
© 2019 Uwe R. Zimmer, The Australian National University page 55 of 757 (“Language refresher / introduction course” up to page 159)

begin
Language refresher / introduction course
A queue test program with proper exceptions with Queue_Pack_Exceptions; use Queue_Pack_Exceptions;
with Ada.Text_IO ; use Ada.Text_IO;
procedure Queue_Test_Exceptions is Queue : Queue_Type;
Item : Element;
Enqueue (Turn, Queue);
Dequeue (Item, Queue);
Dequeue (Item, Queue); — will produce a Queue_underflow exception
exception
when Queue_underflow => Put (“Queue underflow”); when Queue_overflow => Put (“Queue overflow”);
end Queue_Test_Exceptions;
© 2019 Uwe R. Zimmer, The Australian National University page 56 of 757 (“Language refresher / introduction course” up to page 159)

Control flow is continued after the exception handler in case of a handled exception.
An exception handler has a choice to handle, pass, or re-raise the same or a different exception.
Raised exceptions break the control
flow and “propagate” to the closest “exception handler” in the call-chain.
begin
Language refresher / introduction course
A queue test program with proper exceptions with Queue_Pack_Exceptions; use Queue_Pack_Exceptions;
with Ada.Text_IO ; use Ada.Text_IO;
procedure Queue_Test_Exceptions is Queue : Queue_Type;
Item : Element;
Enqueue (Turn, Queue);
Dequeue (Item, Queue);
Dequeue (Item, Queue); — will produce a Queue_underflow exception
exception
when Queue_underflow => Put (“Queue underflow”); when Queue_overflow => Put (“Queue overflow”);
end Queue_Test_Exceptions;
© 2019 Uwe R. Zimmer, The Australian National University page 57 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
begin
Language refresher / introduction course
A queue test program with proper exceptions with Queue_Pack_Exceptions; use Queue_Pack_Exceptions;
with Ada.Text_IO ; use Ada.Text_IO;
procedure Queue_Test_Exceptions is Queue : Queue_Type;
Item : Element;
Enqueue (Turn, Queue);
Dequeue (Item, Queue);
Dequeue (Item, Queue); — will produce a Queue_underflow exception
exception
when Queue_underflow => Put (“Queue underflow”); when Queue_overflow => Put (“Queue overflow”);
end Queue_Test_Exceptions;
© 2019 Uwe R. Zimmer, The Australian National University page 58 of 757 (“Language refresher / introduction course” up to page 159)

This package provides access to ‘internal’ structures which can lead to inconsistent access.
Language refresher / introduction course
A queue specification with proper exceptions
package Queue_Pack_Exceptions is QueueSize : constant Positive := 10;
type Element type Marker type List
is (Up, Down, Spin, Turn);
is mod QueueSize;
is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First; Is_Empty : Boolean := True; Elements : List;
end record;
procedure Enqueue (Item: Element; Queue: in out Queue_Type);
procedure Dequeue (Item: out Element; Queue: in out Queue_Type);
function Is_Empty (Queue : Queue_Type) return Boolean is (Queue.Is_Empty); function Is_Full (Queue : Queue_Type) return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free); Queue_overflow, Queue_underflow : exception;
end Queue_Pack_Exceptions;
© 2019 Uwe R. Zimmer, The Australian National University page 59 of 757 (“Language refresher / introduction course” up to page 159)

… introducing:
Language refresher / introduction course
• Private declarations
needed to compile specifications,
yet not accessible for a user of the package.
• Private types assignments and comparisons are allowed
• Limited private types entity cannot be assigned or compared
Ada
Information hiding
© 2019 Uwe R. Zimmer, The Australian National University page 60 of 757 (“Language refresher / introduction course” up to page 159)

Language refresher / introduction course
A queue specification with proper information hiding
package Queue_Pack_Private is QueueSize : constant Integer := 10;
type Element is new Positive range 1..1000; type Queue_Type is limited private;
procedure Enqueue (Item: Element; Queue: in out Queue_Type); procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean;
Queueoverflow, Queueunderflow : exception;
private
type Marker is mod QueueSize;
type List is array (Marker) of Element; type Queue_Type is record
Top, Free : Marker := Marker’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Private;
© 2019 Uwe R. Zimmer, The Australian National University
page 61 of 757 (“Language refresher / introduction course” up to page 159)

The private section is only here so that the specifications can be separately compiled.
private splits the specification into a public and a private section.
Language refresher / introduction course
A queue specification with proper information hiding
package Queue_Pack_Private is QueueSize : constant Integer := 10;
type Element is new Positive range 1..1000; type Queue_Type is limited private;
procedure Enqueue (Item: Element; Queue: in out Queue_Type); procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean;
Queueoverflow, Queueunderflow : exception;
private
type Marker is mod QueueSize;
type List is array (Marker) of Element; type Queue_Type is record
Top, Free : Marker := Marker’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Private;
© 2019 Uwe R. Zimmer, The Australian National University
page 62 of 757 (“Language refresher / introduction course” up to page 159)

Queue_Type can now be used out- side this package without any way to access its internal structure.
limited disables assignments and comparisons for this type.
A user of this package would now e.g. not be able to make a copy of a Queue_Type value.
Language refresher / introduction course
A queue specification with proper information hiding
package Queue_Pack_Private is QueueSize : constant Integer := 10;
type Element is new Positive range 1..1000; type Queue_Type is limited private;
procedure Enqueue (Item: Element; Queue: in out Queue_Type); procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean;
Queueoverflow, Queueunderflow : exception;
private
type Marker is mod QueueSize;
type List is array (Marker) of Element; type Queue_Type is record
Top, Free : Marker := Marker’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Private;
© 2019 Uwe R. Zimmer, The Australian National University
page 63 of 757 (“Language refresher / introduction course” up to page 159)

Queue_Type can now be used out- side this package without any way to access its internal structure.
Alternatively ‘=’ and ‘:=’ operations can be replaced with type-specific versions (overloaded) or default operations can be allowed.
Language refresher / introduction course
A queue specification with proper information hiding
package Queue_Pack_Private is QueueSize : constant Integer := 10;
type Element is new Positive range 1..1000; type Queue_Type is limited private;
procedure Enqueue (Item: Element; Queue: in out Queue_Type); procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean;
Queueoverflow, Queueunderflow : exception;
private
type Marker is mod QueueSize;
type List is array (Marker) of Element; type Queue_Type is record
Top, Free : Marker := Marker’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Private;
© 2019 Uwe R. Zimmer, The Australian National University
page 64 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
Language refresher / introduction course
A queue specification with proper information hiding
package Queue_Pack_Private is QueueSize : constant Integer := 10;
type Element is new Positive range 1..1000; type Queue_Type is limited private;
procedure Enqueue (Item: Element; Queue: in out Queue_Type); procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean;
Queueoverflow, Queueunderflow : exception;
private
type Marker is mod QueueSize;
type List is array (Marker) of Element; type Queue_Type is record
Top, Free : Marker := Marker’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Private;
© 2019 Uwe R. Zimmer, The Australian National University
page 65 of 757 (“Language refresher / introduction course” up to page 159)

A queue implementation with proper information hiding package body Queue_Pack_Private is
procedure Enqueue (Item: Element; Queue: in out Queue_Type) is begin
if Is_Full (Queue) then raise Queueoverflow;
end if;
Queue.Elements Queue.Free Queue.Is_Empty
(Queue.Free) := Item;
:= Marker’Pred (Queue.Free);
end Enqueue; procedure Dequeue
:= False;
(Item: out Element; Queue: in out Queue_Type) is
begin
if Is_Empty (Queue) then raise Queueunderflow; end if;
Item := Queue.Elements (Queue.Top); Queue.Top := Marker’Pred (Queue.Top); Queue.Is_Empty := Queue.Top = Queue.Free;
end Dequeue;
function Is_Empty (Queue : Queue_Type) return Boolean is (Queue.Is_Empty); function Is_Full (Queue : Queue_Type) return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free);
end Queue_Pack_Private;
© 2019 Uwe R. Zimmer, The Australian National University page 66 of 757 (“Language refresher / introduction course” up to page 159)

… besides the implementation of the two functions which has been moved to the implementation section.
A queue implementation with proper information hiding package body Queue_Pack_Private is
procedure Enqueue (Item: Element; Queue: in out Queue_Type) is begin
begin
if Is_Full (Queue) then raise Queueoverflow;
end if;
Queue.Elements Queue.Free Queue.Is_Empty
(Queue.Free) := Item;
:= Marker’Pred (Queue.Free);
end Enqueue; procedure Dequeue
:= False;
(Item: out Element; Queue: in out Queue_Type) is if Is_Empty (Queue) then raise Queueunderflow; end if;
Item
Queue.Top Queue.Is_Empty
:= Queue.Elements (Queue.Top); := Marker’Pred (Queue.Top);
:= Queue.Top = Queue.Free;
end Dequeue;
(Queue : Queue_Type) return Boolean is (Queue.Is_Empty); function Is_Full (Queue : Queue_Type) return Boolean is
function Is_Empty
(not Queue.Is_Empty and then Queue.Top = Queue.Free);
end Queue_Pack_Private;
© 2019 Uwe R. Zimmer, The Australian National University page 67 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
A queue implementation with proper information hiding package body Queue_Pack_Private is
procedure Enqueue (Item: Element; Queue: in out Queue_Type) is begin
if Is_Full (Queue) then raise Queueoverflow;
end if;
Queue.Elements Queue.Free Queue.Is_Empty
(Queue.Free) := Item;
:= Marker’Pred (Queue.Free);
end Enqueue; procedure Dequeue
:= False;
(Item: out Element; Queue: in out Queue_Type) is
begin
if Is_Empty (Queue) then raise Queueunderflow; end if;
Item := Queue.Elements (Queue.Top); Queue.Top := Marker’Pred (Queue.Top); Queue.Is_Empty := Queue.Top = Queue.Free;
end Dequeue;
function Is_Empty (Queue : Queue_Type) return Boolean is (Queue.Is_Empty); function Is_Full (Queue : Queue_Type) return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free);
end Queue_Pack_Private;
© 2019 Uwe R. Zimmer, The Australian National University page 68 of 757 (“Language refresher / introduction course” up to page 159)

begin
Language refresher / introduction course
A queue test program with proper information hiding with Queue_Pack_Private; use Queue_Pack_Private;
with Ada.Text_IO ; use Ada.Text_IO; procedure Queue_Test_Private is
Queue, Queue_Copy : Queue_Type;
Item : Element;
Queue_Copy := Queue;
— compiler-error: “left hand of assignment must not be limited type”
Enqueue (Item => 1, Queue => Queue);
Dequeue (Item, Queue);
Dequeue (Item, Queue); — would produce a “Queue underflow”
exception
when Queueunderflow => Put (“Queue underflow”); when Queueoverflow => Put (“Queue overflow”);
end Queue_Test_Private;
© 2019 Uwe R. Zimmer, The Australian National University page 69 of 757 (“Language refresher / introduction course” up to page 159)

Illegal operation on a limited type.
begin
Language refresher / introduction course
A queue test program with proper information hiding with Queue_Pack_Private; use Queue_Pack_Private;
with Ada.Text_IO ; use Ada.Text_IO; procedure Queue_Test_Private is
Queue, Queue_Copy : Queue_Type;
Item : Element;
Queue_Copy := Queue;
— compiler-error: “left hand of assignment must not be limited type”
Enqueue (Item => 1, Queue => Queue);
Dequeue (Item, Queue);
Dequeue (Item, Queue); — would produce a “Queue underflow”
exception
when Queueunderflow => Put (“Queue underflow”); when Queueoverflow => Put (“Queue overflow”);
end Queue_Test_Private;
© 2019 Uwe R. Zimmer, The Australian National University page 70 of 757 (“Language refresher / introduction course” up to page 159)

Parameters can be named or passed by order of definition.
(Named parameters do not need to follow the definition order.)
begin
Language refresher / introduction course
A queue test program with proper information hiding with Queue_Pack_Private; use Queue_Pack_Private;
with Ada.Text_IO ; use Ada.Text_IO; procedure Queue_Test_Private is
Queue, Queue_Copy : Queue_Type;
Item : Element;
Queue_Copy := Queue;
— compiler-error: “left hand of assignment must not be limited type”
Enqueue (Item => 1, Queue => Queue);
Dequeue (Item, Queue);
Dequeue (Item, Queue); — would produce a “Queue underflow”
exception
when Queueunderflow => Put (“Queue underflow”); when Queueoverflow => Put (“Queue overflow”);
end Queue_Test_Private;
© 2019 Uwe R. Zimmer, The Australian National University page 71 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
begin
Language refresher / introduction course
A queue test program with proper information hiding with Queue_Pack_Private; use Queue_Pack_Private;
with Ada.Text_IO ; use Ada.Text_IO; procedure Queue_Test_Private is
Queue, Queue_Copy : Queue_Type;
Item : Element;
Queue_Copy := Queue;
— compiler-error: “left hand of assignment must not be limited type”
Enqueue (Item => 1, Queue => Queue);
Dequeue (Item, Queue);
Dequeue (Item, Queue); — would produce a “Queue underflow”
exception
when Queueunderflow => Put (“Queue underflow”); when Queueoverflow => Put (“Queue overflow”);
end Queue_Test_Private;
© 2019 Uwe R. Zimmer, The Australian National University page 72 of 757 (“Language refresher / introduction course” up to page 159)

… introducing:
Language refresher / introduction course
• Pre- and Post-Conditions on methods • Invariants on types
• For all, For any predicates
© 2019 Uwe R. Zimmer, The Australian National University
page 73 of 757 (“Language refresher / introduction course” up to page 159)
Ada
Contracts

Language refresher / introduction course
A contracting queue specification
package Queue_Pack_Contract is
Queue_Size : constant Positive := 10;
type Element is new Positive range 1 .. 1000; type Queue_Type is private;
procedure Enqueue (Item : Element; Q : in out Queue_Type) with Pre => not Is_Full (Q),
Post => not Is_Empty (Q) and then Length (Q) = Length (Q’Old) + 1
and then Lookahead (Q, Length (Q)) = Item and then (for all ix in 1 .. Length (Q’Old)
procedure Dequeue (Item : out Element; Q : in out Queue_Type) with Pre => not Is_Empty (Q),
Post => not Is_Full (Q) and then Length (Q) = Length (Q’Old) – 1
=> Lookahead (Q, ix) = Lookahead (Q’Old, ix));
and then (for all ix in 1 .. Length (Q)
=> Lookahead (Q, ix) = Lookahead (Q’Old, ix + 1));
function Is_Empty (Q : Queue_Type) return Boolean; function Is_Full (Q : Queue_Type) return Boolean; function Length (Q : Queue_Type) return Natural;
function Lookahead (Q : Queue_Type; Depth : Positive) return Element;
© 2019 Uwe R. Zimmer, The Australian National University page 74 of 757 (“Language refresher / introduction course” up to page 159)

Pre- and Post-predicates are checked before and after each execution resp.
6 and7quantifiers are expressed as “for all” and “for some” expressions resp.
Original (Pre) values can still be referred to.
Language refresher / introduction course
A contracting queue specification
package Queue_Pack_Contract is
Queue_Size : constant Positive := 10;
type Element is new Positive range 1 .. 1000; type Queue_Type is private;
procedure Enqueue (Item : Element; Q : in out Queue_Type) with Pre => not Is_Full (Q),
Post => not Is_Empty (Q) and then Length (Q) = Length (Q’Old) + 1
and then Lookahead (Q, Length (Q)) = Item and then (for all ix in 1 .. Length (Q’Old)
procedure Dequeue (Item : out Element; Q : in out Queue_Type) with Pre => not Is_Empty (Q),
Post => not Is_Full (Q) and then Length (Q) = Length (Q’Old) – 1
=> Lookahead (Q, ix) = Lookahead (Q’Old, ix));
and then (for all ix in 1 .. Length (Q)
=> Lookahead (Q, ix) = Lookahead (Q’Old, ix + 1));
function Is_Empty (Q : Queue_Type) return Boolean; function Is_Full (Q : Queue_Type) return Boolean; function Length (Q : Queue_Type) return Natural;
function Lookahead (Q : Queue_Type; Depth : Positive) return Element;
© 2019 Uwe R. Zimmer, The Australian National University page 75 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
Language refresher / introduction course
A contracting queue specification
package Queue_Pack_Contract is
Queue_Size : constant Positive := 10;
type Element is new Positive range 1 .. 1000; type Queue_Type is private;
procedure Enqueue (Item : Element; Q : in out Queue_Type) with Pre => not Is_Full (Q),
Post => not Is_Empty (Q) and then Length (Q) = Length (Q’Old) + 1
and then Lookahead (Q, Length (Q)) = Item and then (for all ix in 1 .. Length (Q’Old)
procedure Dequeue (Item : out Element; Q : in out Queue_Type) with Pre => not Is_Empty (Q),
Post => not Is_Full (Q) and then Length (Q) = Length (Q’Old) – 1
=> Lookahead (Q, ix) = Lookahead (Q’Old, ix));
and then (for all ix in 1 .. Length (Q)
=> Lookahead (Q, ix) = Lookahead (Q’Old, ix + 1));
function Is_Empty (Q : Queue_Type) return Boolean; function Is_Full (Q : Queue_Type) return Boolean; function Length (Q : Queue_Type) return Natural;
function Lookahead (Q : Queue_Type; Depth : Positive) return Element;
© 2019 Uwe R. Zimmer, The Australian National University page 76 of 757 (“Language refresher / introduction course” up to page 159)

Language refresher / introduction course
A contracting queue specification (cont.) type Marker is mod Queue_Size;
private
type List is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First;
Is_Empty : Boolean := True;
Elements : List; — will be initialized to invalids
end record with Type_Invariant
=> (not Queue_Type.Is_Empty or else Queue_Type.Top = Queue_Type.Free)
and then (for all ix in 1 .. Length (Queue_Type)
=> Lookahead (Queue_Type, ix)’Valid);
function Is_Empty (Q : Queue_Type) return Boolean is (Q.Is_Empty); function Is_Full (Q : Queue_Type) return Boolean is
(not Q.Is_Empty and then Q.Top = Q.Free); function Length (Q : Queue_Type) return Natural is
(if Is_Full (Q) then Queue_Size else Natural (Q.Free – Q.Top)); function Lookahead (Q : Queue_Type; Depth : Positive) return Element is
(Q.Elements (Q.Top + Marker (Depth – 1)));
end Queue_Pack_Contract;
© 2019 Uwe R. Zimmer, The Australian National University page 77 of 757 (“Language refresher / introduction course” up to page 159)

Type-Invariants are checked on return from any operation defined in the public part.
Language refresher / introduction course
A contracting queue specification (cont.) type Marker is mod Queue_Size;
private
type List is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First;
Is_Empty : Boolean := True;
Elements : List; — will be initialized to invalids
end record with Type_Invariant
=> (not Queue_Type.Is_Empty or else Queue_Type.Top = Queue_Type.Free)
and then (for all ix in 1 .. Length (Queue_Type)
=> Lookahead (Queue_Type, ix)’Valid);
function Is_Empty (Q : Queue_Type) return Boolean is (Q.Is_Empty); function Is_Full (Q : Queue_Type) return Boolean is
(not Q.Is_Empty and then Q.Top = Q.Free); function Length (Q : Queue_Type) return Natural is
(if Is_Full (Q) then Queue_Size else Natural (Q.Free – Q.Top)); function Lookahead (Q : Queue_Type; Depth : Positive) return Element is
(Q.Elements (Q.Top + Marker (Depth – 1)));
end Queue_Pack_Contract;
© 2019 Uwe R. Zimmer, The Australian National University page 78 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
Language refresher / introduction course
A contracting queue specification (cont.) type Marker is mod Queue_Size;
private
type List is array (Marker) of Element;
type Queue_Type is record
Top, Free : Marker := Marker’First;
Is_Empty : Boolean := True;
Elements : List; — will be initialized to invalids
end record with Type_Invariant
=> (not Queue_Type.Is_Empty or else Queue_Type.Top = Queue_Type.Free)
and then (for all ix in 1 .. Length (Queue_Type)
=> Lookahead (Queue_Type, ix)’Valid);
function Is_Empty (Q : Queue_Type) return Boolean is (Q.Is_Empty); function Is_Full (Q : Queue_Type) return Boolean is
(not Q.Is_Empty and then Q.Top = Q.Free); function Length (Q : Queue_Type) return Natural is
(if Is_Full (Q) then Queue_Size else Natural (Q.Free – Q.Top)); function Lookahead (Q : Queue_Type; Depth : Positive) return Element is
(Q.Elements (Q.Top + Marker (Depth – 1)));
end Queue_Pack_Contract;
© 2019 Uwe R. Zimmer, The Australian National University page 79 of 757 (“Language refresher / introduction course” up to page 159)

No checks in the implementation part, as all required conditions have been guaranteed via the specifications.
Language refresher / introduction course
A contracting queue implementation package body Queue_Pack_Contract is
procedure Enqueue (Item : Element; Q : in out Queue_Type) is
begin
Q.Elements (Q.Free) := Item; Q.Free := Q.Free + 1; Q.Is_Empty := False;
end Enqueue;
procedure Dequeue (Item : out Element; Q : in out Queue_Type) is
begin
Item := Q.Elements (Q.Top); Q.Top := Q.Top + 1; Q.Is_Empty := Q.Top = Q.Free;
end Dequeue;
end Queue_Pack_Contract;
© 2019 Uwe R. Zimmer, The Australian National University
page 80 of 757 (“Language refresher / introduction course” up to page 159)

begin
Language refresher / introduction course
A contracting queue test program
with Ada.Text_IO; use Ada.Text_IO;
with Exceptions; use Exceptions;
with Queue_Pack_Contract; use Queue_Pack_Contract; with System.Assertions; use System.Assertions;
procedure Queue_Test_Contract is Queue : Queue_Type;
Item : Element;
Enqueue (Item => 1, Q => Queue);
Enqueue (Item => 2, Q => Queue);
Dequeue (Item, Queue); Put (Element’Image (Item));
Dequeue (Item, Queue); Put (Element’Image (Item));
Dequeue (Item, Queue); — will produce an Assert_Failure
Put (Element’Image (Item));
Put (“Queue is empty on exit: “); Put (Boolean’Image (Is_Empty (Queue)));
exception
when Exception_Id : Assert_Failure => Show_Exception (Exception_Id);
end Queue_Test_Contract;
© 2019 Uwe R. Zimmer, The Australian National University page 81 of 757 (“Language refresher / introduction course” up to page 159)

Violated Pre-condition will raise an assert failure exception.
begin
Language refresher / introduction course
A contracting queue test program
with Ada.Text_IO; use Ada.Text_IO;
with Exceptions; use Exceptions;
with Queue_Pack_Contract; use Queue_Pack_Contract; with System.Assertions; use System.Assertions;
procedure Queue_Test_Contract is Queue : Queue_Type;
Item : Element;
Enqueue (Item => 1, Q => Queue);
Enqueue (Item => 2, Q => Queue);
Dequeue (Item, Queue); Put (Element’Image (Item));
Dequeue (Item, Queue); Put (Element’Image (Item));
Dequeue (Item, Queue); — will produce an Assert_Failure
Put (Element’Image (Item));
Put (“Queue is empty on exit: “); Put (Boolean’Image (Is_Empty (Queue)));
exception
when Exception_Id : Assert_Failure => Show_Exception (Exception_Id);
end Queue_Test_Contract;
© 2019 Uwe R. Zimmer, The Australian National University page 82 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
begin
Language refresher / introduction course
A contracting queue test program
with Ada.Text_IO; use Ada.Text_IO;
with Exceptions; use Exceptions;
with Queue_Pack_Contract; use Queue_Pack_Contract; with System.Assertions; use System.Assertions;
procedure Queue_Test_Contract is Queue : Queue_Type;
Item : Element;
Enqueue (Item => 1, Q => Queue);
Enqueue (Item => 2, Q => Queue);
Dequeue (Item, Queue); Put (Element’Image (Item));
Dequeue (Item, Queue); Put (Element’Image (Item));
Dequeue (Item, Queue); — will produce an Assert_Failure
Put (Element’Image (Item));
Put (“Queue is empty on exit: “); Put (Boolean’Image (Is_Empty (Queue)));
exception
when Exception_Id : Assert_Failure => Show_Exception (Exception_Id);
end Queue_Test_Contract;
© 2019 Uwe R. Zimmer, The Australian National University page 83 of 757 (“Language refresher / introduction course” up to page 159)

Exceptions are commonly preferred to handle rare, yet valid situations.
Contracts are commonly used to test program correctness with respect to its specifications.
Those contracts can be used to fully specify operations and types. Specifications should be complete, consistent and canonical, while using as little implementation details as possible.
package Queue_Pack_Contract is (…)
(…)
type Queue_Type is record
A contracted queue specification
procedure Enqueue (Item : Element; Q : in out Queue_Type) with
Pre => not Is_Full (Q), — could also be “=> True” according to specifications Post => not Is_Empty (Q) and then Length (Q) = Length (Q’Old) + 1
and then Lookahead (Q, Length (Q)) = Item and then (for all ix in 1 .. Length (Q’Old)
Top, Free : Marker := Marker’First;
Is_Empty : Boolean := True;
Elements : List;
=> Lookahead (Q, ix) = Lookahead (Q’Old, ix));
procedure Dequeue (Item : out Element; Q : in out Queue_Type) with
Pre => not Is_Empty (Q), — could also be “=> True” according to specifications Post => not Is_Full (Q) and then Length (Q) = Length (Q’Old) – 1
and then (for all ix in 1 .. Length (Q)
=> Lookahead (Q, ix) = Lookahead (Q’Old, ix + 1));
end record with Type_Invariant =>
(not Queue_Type.Is_Empty or else Queue_Type.Top = Queue_Type.Free) and then (for all ix in 1 .. Length (Queue_Type)
(…)
© 2019 Uwe R. Zimmer, The Australian National University page 84 of 757 (chapter 2: “Language refresher / introduction course” up to page 159)
=> Lookahead (Queue_Type, ix)’Valid);

Language refresher / introduction course
… introducing:
• Specification of generic packages
• Instantiation of generic packages
Ada
Generic (polymorphic) packages
© 2019 Uwe R. Zimmer, The Australian National University page 85 of 757 (“Language refresher / introduction course” up to page 159)

generic
Language refresher / introduction course
A generic queue specification type Element is private;
package Queue_Pack_Generic is QueueSize: constant Integer := 10; type Queue_Type is limited private;
procedure Enqueue (Item: Element; Queue: in out Queue_Type); procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean; Queueoverflow, Queueunderflow : exception;
private
type Marker is mod QueueSize;
type List is array (Marker) of Element; type Queue_Type is record
Top, Free : Marker := Marker’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 86 of 757 (“Language refresher / introduction course” up to page 159)

The type of Element now becomes a parameter of a generic package.
No restrictions (private) have been set for the type of Element.
Haskell syntax:
enqueue :: a -> Queue a -> Queue a
generic
Language refresher / introduction course
A generic queue specification type Element is private;
package Queue_Pack_Generic is QueueSize: constant Integer := 10; type Queue_Type is limited private;
procedure Enqueue (Item: Element; Queue: in out Queue_Type); procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean; Queueoverflow, Queueunderflow : exception;
private
type Marker is mod QueueSize;
type List is array (Marker) of Element; type Queue_Type is record
Top, Free : Marker := Marker’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 87 of 757 (“Language refresher / introduction course” up to page 159)

Generic aspects can include:
• Typecategories
• Incompletetypes
• Constants
• Procedures and functions
• Otherpackages
• Objects (interfaces)
Default values can be provided (making those parameters optional)
generic
Language refresher / introduction course
A generic queue specification type Element is private;
package Queue_Pack_Generic is QueueSize: constant Integer := 10; type Queue_Type is limited private;
procedure Enqueue (Item: Element; Queue: in out Queue_Type); procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean; Queueoverflow, Queueunderflow : exception;
private
type Marker is mod QueueSize;
type List is array (Marker) of Element; type Queue_Type is record
Top, Free : Marker := Marker’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 88 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
generic
Language refresher / introduction course
A generic queue specification type Element is private;
package Queue_Pack_Generic is QueueSize: constant Integer := 10; type Queue_Type is limited private;
procedure Enqueue (Item: Element; Queue: in out Queue_Type); procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean; Queueoverflow, Queueunderflow : exception;
private
type Marker is mod QueueSize;
type List is array (Marker) of Element; type Queue_Type is record
Top, Free : Marker := Marker’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 89 of 757 (“Language refresher / introduction course” up to page 159)

A generic queue implementation package body Queue_Pack_Generic is
procedure Enqueue (Item: Element; Queue: in out Queue_Type) is begin
if Is_Full (Queue) then raise Queueoverflow;
end if;
Queue.Elements Queue.Free Queue.Is_Empty
(Queue.Free) := Item;
:= Marker’Pred (Queue.Free);
end Enqueue; procedure Dequeue
:= False;
(Item: out Element; Queue: in out Queue_Type) is
begin
if Is_Empty (Queue) then raise Queueunderflow; end if;
Item := Queue.Elements (Queue.Top); Queue.Top := Marker’Pred (Queue.Top); Queue.Is_Empty := Queue.Top = Queue.Free;
end Dequeue;
function Is_Empty (Queue : Queue_Type) return Boolean is (Queue.Is_Empty); function Is_Full (Queue : Queue_Type) return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free); end Queue_Pack_Generic;
© 2019 Uwe R. Zimmer, The Australian National University page 90 of 757 (“Language refresher / introduction course” up to page 159)

begin
Language refresher / introduction course
A generic queue test program
with Queue_Pack_Generic; — cannot apply ‘use’ clause here with Ada.Text_IO ; use Ada.Text_IO;
procedure Queue_Test_Generic is
package Queue_Pack_Positive is
new Queue_Pack_Generic (Element => Positive);
use Queue_Pack_Positive; — ‘use’ clause can be applied to instantiated package Queue : Queue_Type;
Item : Positive;
Enqueue (Item => 1, Queue => Queue);
Dequeue (Item, Queue);
Dequeue (Item, Queue); — will produce a “Queue underflow”
exception
when Queueunderflow => Put (“Queue underflow”); when Queueoverflow => Put (“Queue overflow”);
end Queue_Test_Generic;
© 2019 Uwe R. Zimmer, The Australian National University page 91 of 757 (“Language refresher / introduction course” up to page 159)

Instantiate generic package
begin
Language refresher / introduction course
A generic queue test program
with Queue_Pack_Generic; — cannot apply ‘use’ clause here with Ada.Text_IO ; use Ada.Text_IO;
procedure Queue_Test_Generic is
package Queue_Pack_Positive is
new Queue_Pack_Generic (Element => Positive);
use Queue_Pack_Positive; — ‘use’ clause can be applied to instantiated package Queue : Queue_Type;
Item : Positive;
Enqueue (Item => 1, Queue => Queue);
Dequeue (Item, Queue);
Dequeue (Item, Queue); — will produce a “Queue underflow”
exception
when Queueunderflow => Put (“Queue underflow”); when Queueoverflow => Put (“Queue overflow”);
end Queue_Test_Generic;
© 2019 Uwe R. Zimmer, The Australian National University page 92 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
begin
Language refresher / introduction course
A generic queue test program
with Queue_Pack_Generic; — cannot apply ‘use’ clause here with Ada.Text_IO ; use Ada.Text_IO;
procedure Queue_Test_Generic is
package Queue_Pack_Positive is
new Queue_Pack_Generic (Element => Positive);
use Queue_Pack_Positive; — ‘use’ clause can be applied to instantiated package Queue : Queue_Type;
Item : Positive;
Enqueue (Item => 1, Queue => Queue);
Dequeue (Item, Queue);
Dequeue (Item, Queue); — will produce a “Queue underflow”
exception
when Queueunderflow => Put (“Queue underflow”); when Queueoverflow => Put (“Queue overflow”);
end Queue_Test_Generic;
© 2019 Uwe R. Zimmer, The Australian National University page 93 of 757 (“Language refresher / introduction course” up to page 159)

None of the packages so far can be used in a concurrent environment.
generic
Language refresher / introduction course
A generic queue specification type Element is private;
package Queue_Pack_Generic is QueueSize: constant Integer := 10; type Queue_Type is limited private;
procedure Enqueue (Item: Element; Queue: in out Queue_Type); procedure Dequeue (Item: out Element; Queue: in out Queue_Type); function Is_Empty (Queue : Queue_Type) return Boolean;
function Is_Full (Queue : Queue_Type) return Boolean; Queueoverflow, Queueunderflow : exception;
private
type Marker is mod QueueSize;
type List is array (Marker) of Element; type Queue_Type is record
Top, Free : Marker := Marker’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 94 of 757 (“Language refresher / introduction course” up to page 159)

… introducing:
Language refresher / introduction course
• Protected objects
• Entry guards
• Side-effecting (mutually exclusive) entry and procedure calls • Side-effect-free (concurrent) function calls
Ada
Access routines for concurrent systems
© 2019 Uwe R. Zimmer, The Australian National University page 95 of 757 (“Language refresher / introduction course” up to page 159)

A generic protected queue specification type Element is private;
generic
type Index is mod <>; — Modulo defines size of the queue. package Queue_Pack_Protected_Generic is
type Queue_Type is limited private;
protected type Protected_Queue is entry Enqueue (Item : Element); entry Dequeue (Item : out Element); procedure Empty_Queue;
function Is_Empty return Boolean; function Is_Full return Boolean;
private
Queue : Queue_Type; end Protected_Queue;
private
type List is array (Index) of Element; type Queue_Type is record
Top, Free : Index := Index’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Protected_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 96 of 757 (“Language refresher / introduction course” up to page 159)

Generic components of the package:
Element can be anything while the Index need to be a modulo type.
A generic protected queue specification type Element is private;
generic
type Index is mod <>; — Modulo defines size of the queue. package Queue_Pack_Protected_Generic is
type Queue_Type is limited private;
protected type Protected_Queue is entry Enqueue (Item : Element); entry Dequeue (Item : out Element); procedure Empty_Queue;
function Is_Empty return Boolean; function Is_Full return Boolean;
private
Queue : Queue_Type; end Protected_Queue;
private
type List is array (Index) of Element; type Queue_Type is record
Top, Free : Index := Index’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Protected_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 97 of 757 (“Language refresher / introduction course” up to page 159)

Queue is protected for safe concurrent access.
Three categories of a access routines are distinguished by the keywords:
entry, procedure, function
A generic protected queue specification type Element is private;
generic
type Index is mod <>; — Modulo defines size of the queue. package Queue_Pack_Protected_Generic is
type Queue_Type is limited private;
protected type Protected_Queue is entry Enqueue (Item : Element); entry Dequeue (Item : out Element); procedure Empty_Queue;
function Is_Empty return Boolean; function Is_Full return Boolean;
private
Queue : Queue_Type; end Protected_Queue;
private
type List is array (Index) of Element; type Queue_Type is record
Top, Free : Index := Index’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Protected_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 98 of 757 (“Language refresher / introduction course” up to page 159)

Procedures are mutually exclusive to all other access routines.
Rationale:
Procedures can modify the protected data.
Hence they need a guarantee for exclusive access.
A generic protected queue specification type Element is private;
generic
type Index is mod <>; — Modulo defines size of the queue. package Queue_Pack_Protected_Generic is
type Queue_Type is limited private;
protected type Protected_Queue is entry Enqueue (Item : Element); entry Dequeue (Item : out Element); procedure Empty_Queue;
function Is_Empty return Boolean; function Is_Full return Boolean;
private
Queue : Queue_Type; end Protected_Queue;
private
type List is array (Index) of Element; type Queue_Type is record
Top, Free : Index := Index’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Protected_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 99 of 757 (“Language refresher / introduction course” up to page 159)

Functions are mutually exclusive to procedures and entries, yet concurrent to other functions.
Rationale:
The compiler enforces those functions to be side-effect-free with respect to the protected data.
Hence concurrent access can be granted among functions without risk.
A generic protected queue specification type Element is private;
generic
type Index is mod <>; — Modulo defines size of the queue. package Queue_Pack_Protected_Generic is
type Queue_Type is limited private;
protected type Protected_Queue is entry Enqueue (Item : Element); entry Dequeue (Item : out Element); procedure Empty_Queue;
function Is_Empty return Boolean; function Is_Full return Boolean;
private
Queue : Queue_Type; end Protected_Queue;
private
type List is array (Index) of Element; type Queue_Type is record
Top, Free : Index := Index’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Protected_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 100 of 757 (“Language refresher / introduction course” up to page 159)

Entries are mutually exclusive to all other access routines and also provide one guard per entry which need to evaluate to True before entry is granted.
The guard expressions are defined in the implementation part.
Rationale:
Entries can be blocking even if the protected object itself is unlocked.
Hence a separate task waiting queue is provided per entry.
A generic protected queue specification type Element is private;
generic
type Index is mod <>; — Modulo defines size of the queue. package Queue_Pack_Protected_Generic is
type Queue_Type is limited private;
protected type Protected_Queue is entry Enqueue (Item : Element); entry Dequeue (Item : out Element); procedure Empty_Queue;
function Is_Empty return Boolean; function Is_Full return Boolean;
private
Queue : Queue_Type; end Protected_Queue;
private
type List is array (Index) of Element; type Queue_Type is record
Top, Free : Index := Index’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Protected_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 101 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
A generic protected queue specification type Element is private;
generic
type Index is mod <>; — Modulo defines size of the queue. package Queue_Pack_Protected_Generic is
type Queue_Type is limited private;
protected type Protected_Queue is entry Enqueue (Item : Element); entry Dequeue (Item : out Element); procedure Empty_Queue;
function Is_Empty return Boolean; function Is_Full return Boolean;
private
Queue : Queue_Type; end Protected_Queue;
private
type List is array (Index) of Element; type Queue_Type is record
Top, Free : Index := Index’First;
Is_Empty : Boolean := True;
Elements : List;
end record;
end Queue_Pack_Protected_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 102 of 757 (“Language refresher / introduction course” up to page 159)

A generic protected queue implementation
package body Queue_Pack_Protected_Generic is protected body Protected_Queue is
entry Enqueue (Item : Element) when not Is_Full is begin
Queue.Elements (Queue.Free) := Item; Queue.Free := Index’Succ (Queue.Free);
Queue.Is_Empty := False; end Enqueue;
entry Dequeue (Item : out Element) when not Is_Empty is begin
Item := Queue.Elements (Queue.Top); Queue.Top := Index’Succ (Queue.Top);
Queue.Is_Empty := Queue.Top = Queue.Free; end Dequeue;
procedure Empty_Queue is begin
Queue.Top := Index’First; Queue.Free := Index’First; Queue.Is_Empty := True; end Empty_Queue;
function Is_Empty return Boolean is (Queue.Is_Empty); function Is_Full return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free); end Protected_Queue;
end Queue_Pack_Protected_Generic;
© 2019 Uwe R. Zimmer, The Australian National University page 103 of 757 (“Language refresher / introduction course” up to page 159)

Guard expressions
follow after when in the implementation of entries.
Tasks are automatically blocked or released depending on the state of the guard.
Guard expressions are re-evaluated on exiting an entry or procedure
(no point to re-check them at any other time).
Exactly one waiting task on one entry is released.
A generic protected queue implementation
package body Queue_Pack_Protected_Generic is protected body Protected_Queue is
entry Enqueue (Item : Element) when not Is_Full is begin
Queue.Elements (Queue.Free) := Item; Queue.Free := Index’Succ (Queue.Free);
Queue.Is_Empty := False; end Enqueue;
entry Dequeue (Item : out Element) when not Is_Empty is begin
Item := Queue.Elements (Queue.Top); Queue.Top := Index’Succ (Queue.Top);
Queue.Is_Empty := Queue.Top = Queue.Free; end Dequeue;
procedure Empty_Queue is begin
Queue.Top := Index’First; Queue.Free := Index’First; Queue.Is_Empty := True; end Empty_Queue;
function Is_Empty return Boolean is (Queue.Is_Empty); function Is_Full return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free); end Protected_Queue;
end Queue_Pack_Protected_Generic;
© 2019 Uwe R. Zimmer, The Australian National University page 104 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
A generic protected queue implementation
package body Queue_Pack_Protected_Generic is protected body Protected_Queue is
entry Enqueue (Item : Element) when not Is_Full is begin
Queue.Elements (Queue.Free) := Item; Queue.Free := Index’Succ (Queue.Free);
Queue.Is_Empty := False; end Enqueue;
entry Dequeue (Item : out Element) when not Is_Empty is begin
Item := Queue.Elements (Queue.Top); Queue.Top := Index’Succ (Queue.Top);
Queue.Is_Empty := Queue.Top = Queue.Free; end Dequeue;
procedure Empty_Queue is begin
Queue.Top := Index’First; Queue.Free := Index’First; Queue.Is_Empty := True; end Empty_Queue;
function Is_Empty return Boolean is (Queue.Is_Empty); function Is_Full return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free); end Protected_Queue;
end Queue_Pack_Protected_Generic;
© 2019 Uwe R. Zimmer, The Australian National University page 105 of 757 (“Language refresher / introduction course” up to page 159)

begin
A generic protected queue test program
with Ada.Task_Identification; use Ada.Task_Identification; with Ada.Text_IO; use Ada.Text_IO;
with Queue_Pack_Protected_Generic;
procedure Queue_Test_Protected_Generic is
type Queue_Size is mod 3;
package Queue_Pack_Protected_Character is
new Queue_Pack_Protected_Generic (Element => Character, Index => Queue_Size);
use Queue_Pack_Protected_Character; Queue : Protected_Queue;
type Task_Index is range 1 .. 3; task type Producer;
task type Consumer;
Producers : array (Task_Index) of Producer;
Consumers : array (Task_Index) of Consumer; (…)
null;
end Queue_Test_Protected_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 106 of 757 (“Language refresher / introduction course” up to page 159)

If more than one instance of a specific task is to be run then a task type (as opposed to a concrete task) is declared.
begin
A generic protected queue test program
with Ada.Task_Identification; use Ada.Task_Identification; with Ada.Text_IO; use Ada.Text_IO;
with Queue_Pack_Protected_Generic;
procedure Queue_Test_Protected_Generic is
type Queue_Size is mod 3;
package Queue_Pack_Protected_Character is
new Queue_Pack_Protected_Generic (Element => Character, Index => Queue_Size);
use Queue_Pack_Protected_Character; Queue : Protected_Queue;
type Task_Index is range 1 .. 3; task type Producer;
task type Consumer;
Producers : array (Task_Index) of Producer;
Consumers : array (Task_Index) of Consumer; (…)
null;
end Queue_Test_Protected_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 107 of 757 (“Language refresher / introduction course” up to page 159)

Multiple instances of a task can be instantiated e.g. by declaring an array of this task type.
Tasks are started right when such an array is created.
begin
A generic protected queue test program
with Ada.Task_Identification; use Ada.Task_Identification; with Ada.Text_IO; use Ada.Text_IO;
with Queue_Pack_Protected_Generic;
procedure Queue_Test_Protected_Generic is
type Queue_Size is mod 3;
package Queue_Pack_Protected_Character is
new Queue_Pack_Protected_Generic (Element => Character, Index => Queue_Size);
use Queue_Pack_Protected_Character; Queue : Protected_Queue;
type Task_Index is range 1 .. 3; task type Producer;
task type Consumer;
Producers : array (Task_Index) of Producer;
Consumers : array (Task_Index) of Consumer; (…)
null;
end Queue_Test_Protected_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 108 of 757 (“Language refresher / introduction course” up to page 159)

These declarations spawned off all the production code.
Often there are no statements for the “main task” (here explicitly stated by a null statement).
This task is prevented from terminating though until all tasks inside its scope terminated.
begin
A generic protected queue test program
with Ada.Task_Identification; use Ada.Task_Identification; with Ada.Text_IO; use Ada.Text_IO;
with Queue_Pack_Protected_Generic;
procedure Queue_Test_Protected_Generic is
type Queue_Size is mod 3;
package Queue_Pack_Protected_Character is
new Queue_Pack_Protected_Generic (Element => Character, Index => Queue_Size);
use Queue_Pack_Protected_Character; Queue : Protected_Queue;
type Task_Index is range 1 .. 3; task type Producer;
task type Consumer;
Producers : array (Task_Index) of Producer;
Consumers : array (Task_Index) of Consumer; (…)
null;
end Queue_Test_Protected_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 109 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
begin
A generic protected queue test program
with Ada.Task_Identification; use Ada.Task_Identification; with Ada.Text_IO; use Ada.Text_IO;
with Queue_Pack_Protected_Generic;
procedure Queue_Test_Protected_Generic is
type Queue_Size is mod 3;
package Queue_Pack_Protected_Character is
new Queue_Pack_Protected_Generic (Element => Character, Index => Queue_Size);
use Queue_Pack_Protected_Character; Queue : Protected_Queue;
type Task_Index is range 1 .. 3; task type Producer;
task type Consumer;
Producers : array (Task_Index) of Producer;
Consumers : array (Task_Index) of Consumer; (…)
null;
end Queue_Test_Protected_Generic;
© 2019 Uwe R. Zimmer, The Australian National University
page 110 of 757 (“Language refresher / introduction course” up to page 159)

end loop;
A generic protected queue test program (cont.)
subtype Some_Characters is Character range ‘a’ .. ‘f’; task body Producer is
begin
for Ch in Some_Characters loop
Put_Line (“Task “ & Image (Current_Task) & “ finds the queue to be “ & (if Queue.Is_Empty then “EMPTY” else “not empty”) &
“ and “ &
(if Queue.Is_Full then “FULL” else “not full”) &
“ and prepares to add: “ & Character’Image (Ch) &
“ to the queue.”);
Queue.Enqueue (Ch); — task might be blocked here!
Put_Line (“<---- Task “ & Image (Current_Task) & “ terminates.”); end Producer; © 2019 Uwe R. Zimmer, The Australian National University page 111 of 757 (“Language refresher / introduction course” up to page 159) The executable code for a task is provided in its body. end loop; A generic protected queue test program (cont.) subtype Some_Characters is Character range ‘a’ .. ‘f’; task body Producer is begin for Ch in Some_Characters loop Put_Line (“Task “ & Image (Current_Task) & “ finds the queue to be “ & (if Queue.Is_Empty then “EMPTY” else “not empty”) & “ and “ & (if Queue.Is_Full then “FULL” else “not full”) & “ and prepares to add: “ & Character’Image (Ch) & “ to the queue.”); Queue.Enqueue (Ch); -- task might be blocked here! Put_Line (“<---- Task “ & Image (Current_Task) & “ terminates.”); end Producer; © 2019 Uwe R. Zimmer, The Australian National University page 112 of 757 (“Language refresher / introduction course” up to page 159) There are three of those tasks and they are all ‘hammering’ the queue at full CPU speed. end loop; A generic protected queue test program (cont.) subtype Some_Characters is Character range ‘a’ .. ‘f’; task body Producer is begin for Ch in Some_Characters loop Put_Line (“Task “ & Image (Current_Task) & “ finds the queue to be “ & (if Queue.Is_Empty then “EMPTY” else “not empty”) & “ and “ & (if Queue.Is_Full then “FULL” else “not full”) & “ and prepares to add: “ & Character’Image (Ch) & “ to the queue.”); Queue.Enqueue (Ch); -- task might be blocked here! Put_Line (“<---- Task “ & Image (Current_Task) & “ terminates.”); end Producer; © 2019 Uwe R. Zimmer, The Australian National University page 113 of 757 (“Language refresher / introduction course” up to page 159) Tasks automatically terminate once they reach their end declaration (and once all inner tasks are terminated). end loop; A generic protected queue test program (cont.) subtype Some_Characters is Character range ‘a’ .. ‘f’; task body Producer is begin for Ch in Some_Characters loop Put_Line (“Task “ & Image (Current_Task) & “ finds the queue to be “ & (if Queue.Is_Empty then “EMPTY” else “not empty”) & “ and “ & (if Queue.Is_Full then “FULL” else “not full”) & “ and prepares to add: “ & Character’Image (Ch) & “ to the queue.”); Queue.Enqueue (Ch); -- task might be blocked here! Put_Line (“<---- Task “ & Image (Current_Task) & “ terminates.”); end Producer; © 2019 Uwe R. Zimmer, The Australian National University page 114 of 757 (“Language refresher / introduction course” up to page 159) ... anything on this slide still not perfectly clear? end loop; A generic protected queue test program (cont.) subtype Some_Characters is Character range ‘a’ .. ‘f’; task body Producer is begin for Ch in Some_Characters loop Put_Line (“Task “ & Image (Current_Task) & “ finds the queue to be “ & (if Queue.Is_Empty then “EMPTY” else “not empty”) & “ and “ & (if Queue.Is_Full then “FULL” else “not full”) & “ and prepares to add: “ & Character’Image (Ch) & “ to the queue.”); Queue.Enqueue (Ch); -- task might be blocked here! Put_Line (“<---- Task “ & Image (Current_Task) & “ terminates.”); end Producer; © 2019 Uwe R. Zimmer, The Australian National University page 115 of 757 (“Language refresher / introduction course” up to page 159) A generic protected queue test program (cont.) task body Consumer is Item : Character; Counter : Natural := 0; begin loop Queue.Dequeue (Item); -- task might be blocked here! Counter := Natural’Succ (Counter); Put_Line (“Task “ & Image (Current_Task) & “ received: “ & Character’Image (Item) & “ and the queue appears to be “ & (if Queue.Is_Empty then “EMPTY” else “not empty”) & “ and “ & (if Queue.Is_Full then “FULL” else “not full”) & “ afterwards.”); exit when Item = Some_Characters’Last; end loop; Put_Line (“<---- Task “ & Image (Current_Task) & “ terminates and received“ & Natural’Image (Counter) & “ items.”); end Consumer; © 2019 Uwe R. Zimmer, The Australian National University page 116 of 757 (“Language refresher / introduction course” up to page 159) Another three tasks and are all ‘hammering’ the queue at this end and at full CPU speed. A generic protected queue test program (cont.) task body Consumer is Item : Character; Counter : Natural := 0; begin loop Queue.Dequeue (Item); -- task might be blocked here! Counter := Natural’Succ (Counter); Put_Line (“Task “ & Image (Current_Task) & “ received: “ & Character’Image (Item) & “ and the queue appears to be “ & (if Queue.Is_Empty then “EMPTY” else “not empty”) & “ and “ & (if Queue.Is_Full then “FULL” else “not full”) & “ afterwards.”); exit when Item = Some_Characters’Last; end loop; Put_Line (“<---- Task “ & Image (Current_Task) & “ terminates and received“ & Natural’Image (Counter) & “ items.”); end Consumer; © 2019 Uwe R. Zimmer, The Australian National University page 117 of 757 (“Language refresher / introduction course” up to page 159) ... anything on this slide still not perfectly clear? A generic protected queue test program (cont.) task body Consumer is Item : Character; Counter : Natural := 0; begin loop Queue.Dequeue (Item); -- task might be blocked here! Counter := Natural’Succ (Counter); Put_Line (“Task “ & Image (Current_Task) & “ received: “ & Character’Image (Item) & “ and the queue appears to be “ & (if Queue.Is_Empty then “EMPTY” else “not empty”) & “ and “ & (if Queue.Is_Full then “FULL” else “not full”) & “ afterwards.”); exit when Item = Some_Characters’Last; end loop; Put_Line (“<---- Task “ & Image (Current_Task) & “ terminates and received“ & Natural’Image (Counter) & “ items.”); end Consumer; © 2019 Uwe R. Zimmer, The Australian National University page 118 of 757 (“Language refresher / introduction course” up to page 159) What is going on here? A generic protected queue test program (output) Task producers(1) finds the queue to be EMPTY and not full and prepares to add: ‘a’ to the queue. Task producers(1) finds the queue to be not empty and not full and prepares to add: ‘b’ to the queue. Task producers(1) finds the queue to be not empty and not full and prepares to add: ‘c’ to the queue. Task producers(1) finds the queue to be not empty and FULL and prepares to add: ‘d’ to the queue. Task producers(2) finds the queue to be not empty and FULL and prepares to add: ‘a’ to the queue. Task producers(3) finds the queue to be not empty and FULL and prepares to add: ‘a’ to the queue. Task consumers(1) received: ‘a’ and the queue appears to be not empty and FULL afterwards. Task consumers(1) received: ‘b’ and the queue appears to be not empty and FULL afterwards. Task consumers(1) received: ‘c’ and the queue appears to be not empty and FULL afterwards. Task consumers(1) received: ‘d’ and the queue appears to be not empty and not full afterwards. Task consumers(1) received: ‘a’ and the queue appears to be not empty and not full afterwards. .. <---- Task producers(1) terminates. .. Task consumers(3) received: ‘b’ and the queue appears to be EMPTY and not full afterwards. <---- Task consumers(2) terminates and received 1 items. .. <---- Task producers(2) terminates. .. <---- Task producers(3) terminates. .. <---- Task consumers(1) terminates and received 12 items. <---- Task consumers(3) terminates and received 5 items. © 2019 Uwe R. Zimmer, The Australian National University page 119 of 757 (“Language refresher / introduction course” up to page 159) Does this make any sense? A generic protected queue test program (another output) Task producers(1) finds the queue to be EMPTY and not full and prepares to add: ‘a’ to the queue. Task producers(2) finds the queue to be EMPTY and not full and prepares to add: ‘a’ to the queue. Task producers(1) finds the queue to be not empty and not full and prepares to add: ‘b’ to the queue. Task consumers(1) received: ‘a’ and the queue appears to be EMPTY and not full afterwards. Task producers(3) finds the queue to be EMPTY and not full and prepares to add: ‘a’ to the queue. Task producers(1) finds the queue to be EMPTY and not full and prepares to add: ‘c’ to the queue. Task producers(2) finds the queue to be EMPTY and not full and prepares to add: ‘b’ to the queue. Task consumers(2) received: ‘a’ and the queue appears to be EMPTY and not full afterwards. Task consumers(3) received: ‘b’ and the queue appears to be EMPTY and not full afterwards. .. <---- Task producers(1) terminates. Task producers(2) finds the queue to be not empty and FULL and prepares to add: ‘f’ to the queue. Task consumers(2) received: ‘f’ and the queue appears to be not empty and not full afterwards. Task consumers(3) received: ‘e’ and the queue appears to be EMPTY and not full afterwards. Task producers(3) finds the queue to be not empty and not full and prepares to add: ‘f’ to the queue. Task consumers(1) received: ‘d’ and the queue appears to be not empty and not full afterwards. <---- Task producers(2) terminates. <---- Task consumers(2) terminates and received 5 items. Task consumers(3) received: ‘e’ and the queue appears to be not empty and not full afterwards. <---- Task producers(3) terminates. Task consumers(1) received: ‘f’ and the queue appears to be not empty and not full afterwards. Task consumers(3) received: ‘f’ and the queue appears to be EMPTY and not full afterwards. <---- Task consumers(1) terminates and received 6 items. <---- Task consumers(3) terminates and received 7 items. © 2019 Uwe R. Zimmer, The Australian National University page 120 of 757 (“Language refresher / introduction course” up to page 159) ... introducing: Language refresher / introduction course • Abstract tagged types & subroutines (Interfaces) • Concrete implementation of abstract types • Dynamic dispatching to different packages, tasks, protected types or partitions. • Synchronous message passing. Ada Abstract types & dispatching © 2019 Uwe R. Zimmer, The Australian National University page 121 of 757 (“Language refresher / introduction course” up to page 159) ... introducing: Language refresher / introduction course • Abstract tagged types & subroutines (Interfaces) • Concrete implementation of abstract types • Dynamic dispatching to different packages, tasks, protected types or partitions. • Synchronous message passing. Ada Abstract types & dispatching © 2019 Uwe R. Zimmer, The Australian National University page 122 of 757 (“Language refresher / introduction course” up to page 159) generic type Element is private; Language refresher / introduction course An abstract queue specification package Queue_Pack_Abstract is type Queue_Interface is synchronized interface; Element) is abstract; procedure Dequeue (Q : in out Queue_Interface; Item : out Element) is abstract; procedure Enqueue (Q : in out Queue_Interface; Item : end Queue_Pack_Abstract; © 2019 Uwe R. Zimmer, The Australian National University page 123 of 757 (“Language refresher / introduction course” up to page 159) Motivation: Different, derived implementations (potentially on different computers) can be passed around and referred to with the same common interface as defined here. generic type Element is private; Language refresher / introduction course An abstract queue specification package Queue_Pack_Abstract is type Queue_Interface is synchronized interface; Element) is abstract; procedure Dequeue (Q : in out Queue_Interface; Item : out Element) is abstract; procedure Enqueue (Q : in out Queue_Interface; Item : end Queue_Pack_Abstract; © 2019 Uwe R. Zimmer, The Australian National University page 124 of 757 (“Language refresher / introduction course” up to page 159) synchronized means that this interface can only be implemented by synchronized entities like protected objects (as seen above) or synchronous message passing. Abstract, empty type definition which serves to define interface templates. generic type Element is private; Language refresher / introduction course An abstract queue specification package Queue_Pack_Abstract is type Queue_Interface is synchronized interface; Element) is abstract; procedure Dequeue (Q : in out Queue_Interface; Item : out Element) is abstract; procedure Enqueue (Q : in out Queue_Interface; Item : end Queue_Pack_Abstract; © 2019 Uwe R. Zimmer, The Australian National University page 125 of 757 (“Language refresher / introduction course” up to page 159) Abstract methods need to be overridden with concrete methods when a new type is derived from it. generic type Element is private; Language refresher / introduction course An abstract queue specification package Queue_Pack_Abstract is type Queue_Interface is synchronized interface; Element) is abstract; procedure Dequeue (Q : in out Queue_Interface; Item : out Element) is abstract; procedure Enqueue (Q : in out Queue_Interface; Item : end Queue_Pack_Abstract; © 2019 Uwe R. Zimmer, The Australian National University page 126 of 757 (“Language refresher / introduction course” up to page 159) ... anything on this slide still not perfectly clear? generic type Element is private; Language refresher / introduction course An abstract queue specification package Queue_Pack_Abstract is type Queue_Interface is synchronized interface; Element) is abstract; procedure Dequeue (Q : in out Queue_Interface; Item : out Element) is abstract; procedure Enqueue (Q : in out Queue_Interface; Item : end Queue_Pack_Abstract; ... this does not require an implementation package (as all procedures are abstract) © 2019 Uwe R. Zimmer, The Australian National University page 127 of 757 (“Language refresher / introduction course” up to page 159) with Queue_Pack_Abstract; generic private Language refresher / introduction course A concrete queue specification with package Queue_Instance is new Queue_Pack_Abstract (<>); type Index is mod <>; — Modulo defines size of the queue.
package Queue_Pack_Concrete is
use Queue_Instance;
type Queue_Type is limited private;
protected type Protected_Queue is new Queue_Interface with overriding entry Enqueue (Item : Element); overriding entry Dequeue (Item : out Element);
not overriding procedure Empty_Queue;
not overriding function Is_Empty return Boolean;
not overriding function Is_Full return Boolean; private
Queue : Queue_Type; end Protected_Queue;
(…) — as all previous private queue declarations
end Queue_Pack_Concrete;
© 2019 Uwe R. Zimmer, The Australian National University page 128 of 757 (“Language refresher / introduction course” up to page 159)

A generic package which takes another generic package as a parameter.
with Queue_Pack_Abstract; generic
private
Language refresher / introduction course
function Is_Empty return Boolean;
function Is_Full return Boolean; private
Queue : Queue_Type; end Protected_Queue;
A concrete queue specification
with package Queue_Instance is new Queue_Pack_Abstract (<>); type Index is mod <>; — Modulo defines size of the queue.
package Queue_Pack_Concrete is
use Queue_Instance;
type Queue_Type is limited private;
protected type Protected_Queue is new Queue_Interface with overriding entry Enqueue (Item : Element); overriding entry Dequeue (Item : out Element); procedure Empty_Queue;
(…) — as all previous private queue declarations
end Queue_Pack_Concrete;
© 2019 Uwe R. Zimmer, The Australian National University page 129 of 757 (“Language refresher / introduction course” up to page 159)

A synchronous implementation of the abstract type Queue_Interface
All abstract methods are overridden with concrete implementations.
with Queue_Pack_Abstract; generic
private
Language refresher / introduction course
function Is_Empty return Boolean;
function Is_Full return Boolean; private
Queue : Queue_Type; end Protected_Queue;
A concrete queue specification
with package Queue_Instance is new Queue_Pack_Abstract (<>); type Index is mod <>; — Modulo defines size of the queue.
package Queue_Pack_Concrete is
use Queue_Instance;
type Queue_Type is limited private;
protected type Protected_Queue is new Queue_Interface with overriding entry Enqueue (Item : Element); overriding entry Dequeue (Item : out Element); procedure Empty_Queue;
(…) — as all previous private queue declarations
end Queue_Pack_Concrete;
© 2019 Uwe R. Zimmer, The Australian National University page 130 of 757 (“Language refresher / introduction course” up to page 159)

Other (not-overriding) methods can be added.
with Queue_Pack_Abstract; generic
private
Language refresher / introduction course
A concrete queue specification
with package Queue_Instance is new Queue_Pack_Abstract (<>); type Index is mod <>; — Modulo defines size of the queue.
package Queue_Pack_Concrete is
use Queue_Instance;
type Queue_Type is limited private;
protected type Protected_Queue is new Queue_Interface with overriding entry Enqueue (Item : Element); overriding entry Dequeue (Item : out Element);
not overriding procedure Empty_Queue;
not overriding function Is_Empty return Boolean;
not overriding function Is_Full return Boolean; private
Queue : Queue_Type; end Protected_Queue;
(…) — as all previous private queue declarations
end Queue_Pack_Concrete;
© 2019 Uwe R. Zimmer, The Australian National University page 131 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
with Queue_Pack_Abstract; generic
private
Language refresher / introduction course
function Is_Empty return Boolean;
function Is_Full return Boolean; private
Queue : Queue_Type; end Protected_Queue;
A concrete queue specification
with package Queue_Instance is new Queue_Pack_Abstract (<>); type Index is mod <>; — Modulo defines size of the queue.
package Queue_Pack_Concrete is
use Queue_Instance;
type Queue_Type is limited private;
protected type Protected_Queue is new Queue_Interface with overriding entry Enqueue (Item : Element); overriding entry Dequeue (Item : out Element); procedure Empty_Queue;
(…) — as all previous private queue declarations
end Queue_Pack_Concrete;
© 2019 Uwe R. Zimmer, The Australian National University page 132 of 757 (“Language refresher / introduction course” up to page 159)

package body Queue_Pack_Concrete is protected body Protected_Queue is
A concrete queue implementation
entry Enqueue (Item : Element) when not Is_Full is begin
Queue.Elements (Queue.Free) := Item; Queue.Free := Index’Succ (Queue.Free);
Queue.Is_Empty := False; end Enqueue;
entry Dequeue (Item : out Element) when not Is_Empty is begin
Item := Queue.Elements (Queue.Top); Queue.Top := Index’Succ (Queue.Top);
Queue.Is_Empty := Queue.Top = Queue.Free; end Dequeue;
procedure Empty_Queue is begin
Queue.Top := Index’First; Queue.Free := Index’First; Queue.Is_Empty := True; end Empty_Queue;
function Is_Empty return Boolean is (Queue.Is_Empty); function Is_Full return Boolean is
(not Queue.Is_Empty and then Queue.Top = Queue.Free); end Protected_Queue;
end Queue_Pack_Concrete;
© 2019 Uwe R. Zimmer, The Australian National University page 133 of 757 (“Language refresher / introduction course” up to page 159)

with Ada.Text_IO; use Ada.Text_IO; with Queue_Pack_Abstract;
with Queue_Pack_Concrete;
procedure Queue_Test_Dispatching is
(…)
package Queue_Pack_Abstract_Character is new Queue_Pack_Abstract (Character);
use Queue_Pack_Abstract_Character;
type Queue_Size is mod 3;
use Queue_Pack_Character;
A dispatching test program
package Queue_Pack_Character is
new Queue_Pack_Concrete (Queue_Pack_Abstract_Character, Queue_Size);
type Queue_Class is access all Queue_Interface’class;
task Queue_Holder; — could be on an individual partition / separate computer task Queue_User is — could be on an individual partition / separate computer
entry Send_Queue (Remote_Queue : Queue_Class); end Queue_User;
begin null;
end Queue_Test_Dispatching; © 2019 Uwe R. Zimmer, The Australian National University
page 134 of 757 (chapter 2: “Language refresher / introduction course” up to page 159)

Sequence of instantiations
with Ada.Text_IO; use Ada.Text_IO; with Queue_Pack_Abstract;
with Queue_Pack_Concrete;
procedure Queue_Test_Dispatching is
(…)
package Queue_Pack_Abstract_Character is new Queue_Pack_Abstract (Character);
use Queue_Pack_Abstract_Character;
type Queue_Size is mod 3;
use Queue_Pack_Character;
A dispatching test program
package Queue_Pack_Character is
new Queue_Pack_Concrete (Queue_Pack_Abstract_Character, Queue_Size);
type Queue_Class is access all Queue_Interface’class;
task Queue_Holder; — could be on an individual partition / separate computer task Queue_User is — could be on an individual partition / separate computer
entry Send_Queue (Remote_Queue : Queue_Class); end Queue_User;
begin null;
end Queue_Test_Dispatching; © 2019 Uwe R. Zimmer, The Australian National University
page 135 of 757 (chapter 2: “Language refresher / introduction course” up to page 159)

Type which can refer to any instance of Queue_Interface
with Ada.Text_IO; use Ada.Text_IO; with Queue_Pack_Abstract;
with Queue_Pack_Concrete;
procedure Queue_Test_Dispatching is
(…)
package Queue_Pack_Abstract_Character is new Queue_Pack_Abstract (Character);
use Queue_Pack_Abstract_Character;
type Queue_Size is mod 3;
use Queue_Pack_Character;
A dispatching test program
package Queue_Pack_Character is
new Queue_Pack_Concrete (Queue_Pack_Abstract_Character, Queue_Size);
type Queue_Class is access all Queue_Interface’class;
task Queue_Holder; — could be on an individual partition / separate computer task Queue_User is — could be on an individual partition / separate computer
entry Send_Queue (Remote_Queue : Queue_Class); end Queue_User;
begin null;
end Queue_Test_Dispatching; © 2019 Uwe R. Zimmer, The Australian National University
page 136 of 757 (chapter 2: “Language refresher / introduction course” up to page 159)

Declaring two concrete tasks.
(Queue_User has a synchronous message passing entry)
with Ada.Text_IO; use Ada.Text_IO; with Queue_Pack_Abstract;
with Queue_Pack_Concrete;
procedure Queue_Test_Dispatching is
(…)
package Queue_Pack_Abstract_Character is new Queue_Pack_Abstract (Character);
use Queue_Pack_Abstract_Character;
type Queue_Size is mod 3;
use Queue_Pack_Character;
A dispatching test program
package Queue_Pack_Character is
new Queue_Pack_Concrete (Queue_Pack_Abstract_Character, Queue_Size);
type Queue_Class is access all Queue_Interface’class;
task Queue_Holder; — could be on an individual partition / separate computer task Queue_User is — could be on an individual partition / separate computer
entry Send_Queue (Remote_Queue : Queue_Class); end Queue_User;
begin null;
end Queue_Test_Dispatching; © 2019 Uwe R. Zimmer, The Australian National University
page 137 of 757 (chapter 2: “Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
with Ada.Text_IO; use Ada.Text_IO; with Queue_Pack_Abstract;
with Queue_Pack_Concrete;
procedure Queue_Test_Dispatching is
(…)
package Queue_Pack_Abstract_Character is new Queue_Pack_Abstract (Character);
use Queue_Pack_Abstract_Character;
type Queue_Size is mod 3;
use Queue_Pack_Character;
A dispatching test program
package Queue_Pack_Character is
new Queue_Pack_Concrete (Queue_Pack_Abstract_Character, Queue_Size);
type Queue_Class is access all Queue_Interface’class;
task Queue_Holder; — could be on an individual partition / separate computer task Queue_User is — could be on an individual partition / separate computer
entry Send_Queue (Remote_Queue : Queue_Class); end Queue_User;
begin null;
end Queue_Test_Dispatching; © 2019 Uwe R. Zimmer, The Australian National University
page 138 of 757 (chapter 2: “Language refresher / introduction course” up to page 159)

A dispatching test program (cont.) task body Queue_Holder is
begin
Local_Queue : constant Queue_Class := new Protected_Queue; Item : Character;
Queue_User.Send_Queue (Local_Queue);
Local_Queue.all.Dequeue (Item);
Put_Line (“Local dequeue (Holder): “ & Character’Image (Item)); end Queue_Holder;
task body Queue_User is
Local_Queue : constant Queue_Class := new Protected_Queue;
Item : Character;
begin
accept Send_Queue (Remote_Queue : Queue_Class) do
Remote_Queue.all.Enqueue (‘r’); — potentially a remote procedure call! Local_Queue.all.Enqueue (‘l’);
end Send_Queue;
Local_Queue.all.Dequeue (Item);
Put_Line (“Local dequeue (User) : “ & Character’Image (Item)); end Queue_User;
© 2019 Uwe R. Zimmer, The Australian National University page 139 of 757 (“Language refresher / introduction course” up to page 159)

Declaring local queues in each task.
A dispatching test program (cont.) task body Queue_Holder is
begin
Local_Queue : constant Queue_Class := new Protected_Queue; Item : Character;
Queue_User.Send_Queue (Local_Queue);
Local_Queue.all.Dequeue (Item);
Put_Line (“Local dequeue (Holder): “ & Character’Image (Item)); end Queue_Holder;
task body Queue_User is
Local_Queue : constant Queue_Class := new Protected_Queue;
Item : Character;
begin
accept Send_Queue (Remote_Queue : Queue_Class) do
Remote_Queue.all.Enqueue (‘r’); — potentially a remote procedure call! Local_Queue.all.Enqueue (‘l’);
end Send_Queue;
Local_Queue.all.Dequeue (Item);
Put_Line (“Local dequeue (User) : “ & Character’Image (Item)); end Queue_User;
© 2019 Uwe R. Zimmer, The Australian National University page 140 of 757 (“Language refresher / introduction course” up to page 159)

Handing over the Holder’s queue via synchronous message passing.
A dispatching test program (cont.) task body Queue_Holder is
begin
Local_Queue : constant Queue_Class := new Protected_Queue; Item : Character;
Queue_User.Send_Queue (Local_Queue);
Local_Queue.all.Dequeue (Item);
Put_Line (“Local dequeue (Holder): “ & Character’Image (Item)); end Queue_Holder;
task body Queue_User is
Local_Queue : constant Queue_Class := new Protected_Queue;
Item : Character;
begin
accept Send_Queue (Remote_Queue : Queue_Class) do
Remote_Queue.all.Enqueue (‘r’); — potentially a remote procedure call! Local_Queue.all.Enqueue (‘l’);
end Send_Queue;
Local_Queue.all.Dequeue (Item);
Put_Line (“Local dequeue (User) : “ & Character’Image (Item)); end Queue_User;
© 2019 Uwe R. Zimmer, The Australian National University page 141 of 757 (“Language refresher / introduction course” up to page 159)

Adding to both queues
A dispatching test program (cont.) task body Queue_Holder is
begin
Local_Queue : constant Queue_Class := new Protected_Queue; Item : Character;
Queue_User.Send_Queue (Local_Queue);
Local_Queue.all.Dequeue (Item);
Put_Line (“Local dequeue (Holder): “ & Character’Image (Item)); end Queue_Holder;
task body Queue_User is
Local_Queue : constant Queue_Class := new Protected_Queue;
Item : Character;
begin
accept Send_Queue (Remote_Queue : Queue_Class) do
Remote_Queue.all.Enqueue (‘r’); — potentially a remote procedure call! Local_Queue.all.Enqueue (‘l’);
end Send_Queue;
Local_Queue.all.Dequeue (Item);
Put_Line (“Local dequeue (User) : “ & Character’Image (Item)); end Queue_User;
© 2019 Uwe R. Zimmer, The Australian National University page 142 of 757 (“Language refresher / introduction course” up to page 159)

Tasks could run on separate computers
These two calls can be very different in nature:
The first call is potentially tunneled through a network to another computer and thus uses a remote data structure.
The second call is always a local call and using a local data-structure.
A dispatching test program (cont.) task body Queue_Holder is
begin
Local_Queue : constant Queue_Class := new Protected_Queue; Item : Character;
Queue_User.Send_Queue (Local_Queue);
Local_Queue.all.Dequeue (Item);
Put_Line (“Local dequeue (Holder): “ & Character’Image (Item)); end Queue_Holder;
task body Queue_User is
Local_Queue : constant Queue_Class := new Protected_Queue;
Item : Character;
begin
accept Send_Queue (Remote_Queue : Queue_Class) do
Remote_Queue.all.Enqueue (‘r’); — potentially a remote procedure call! Local_Queue.all.Enqueue (‘l’);
end Send_Queue;
Local_Queue.all.Dequeue (Item);
Put_Line (“Local dequeue (User) : “ & Character’Image (Item)); end Queue_User;
© 2019 Uwe R. Zimmer, The Australian National University page 143 of 757 (“Language refresher / introduction course” up to page 159)

Reading out ‘r’
Reading out ‘l’
A dispatching test program (cont.) task body Queue_Holder is
begin
Local_Queue : constant Queue_Class := new Protected_Queue; Item : Character;
Queue_User.Send_Queue (Local_Queue);
Local_Queue.all.Dequeue (Item);
Put_Line (“Local dequeue (Holder): “ & Character’Image (Item)); end Queue_Holder;
task body Queue_User is
Local_Queue : constant Queue_Class := new Protected_Queue;
Item : Character;
begin
accept Send_Queue (Remote_Queue : Queue_Class) do
Remote_Queue.all.Enqueue (‘r’); — potentially a remote procedure call! Local_Queue.all.Enqueue (‘l’);
end Send_Queue;
Local_Queue.all.Dequeue (Item);
Put_Line (“Local dequeue (User) : “ & Character’Image (Item)); end Queue_User;
© 2019 Uwe R. Zimmer, The Australian National University page 144 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
A dispatching test program (cont.) task body Queue_Holder is
begin
Local_Queue : constant Queue_Class := new Protected_Queue; Item : Character;
Queue_User.Send_Queue (Local_Queue);
Local_Queue.all.Dequeue (Item);
Put_Line (“Local dequeue (Holder): “ & Character’Image (Item)); end Queue_Holder;
task body Queue_User is
Local_Queue : constant Queue_Class := new Protected_Queue;
Item : Character;
begin
accept Send_Queue (Remote_Queue : Queue_Class) do
Remote_Queue.all.Enqueue (‘r’); — potentially a remote procedure call! Local_Queue.all.Enqueue (‘l’);
end Send_Queue;
Local_Queue.all.Dequeue (Item);
Put_Line (“Local dequeue (User) : “ & Character’Image (Item)); end Queue_User;
© 2019 Uwe R. Zimmer, The Australian National University page 145 of 757 (“Language refresher / introduction course” up to page 159)

Boeing 787 cockpit (press release photo)
Language refresher / introduction course
Used in many large scale and/or high integrity projects
• Commonly used in aviation industry, high speed trains,
Ada
Ada language status
• Established language standard with free and professionally supported compilers available for all major OSs and platforms.
• Emphasis on maintainability, high-integrity and efficiency.
• Stand-alone runtime environments for embedded systems.
• High integrity, real-time profiles part of the standard e.g. Ravenscar profile.
metro-systems, space programs and military programs.
• … also increasingly on small platforms / micro-controllers.
© 2019 Uwe R. Zimmer, The Australian National University page 146 of 757 (“Language refresher / introduction course” up to page 159)
TGV, Renaud Chodkowski 2012

Language refresher / introduction course
• Dataparallelism:
Distributed data storage with fine grained control (“domains”). Concurrent map operations (forall).
Concurrent fold operations (scan, reduce).
• Taskparallelism:
concurrent loops and blocks (cobegin, coforall).
• Synchronization:
Task synchronization, synchronized variables, atomic sections.
Chapel
Currently under development at Cray.
(originally for the DARPA High Productivity Computing Systems initiative.)
Targeted at massively parallel computers Language primitives for …
© 2019 Uwe R. Zimmer, The Australian National University page 147 of 757 (chapter 2: “Language refresher / introduction course” up to page 159)

Language refresher / introduction course
config const n = 100, max_iterations = 50,
var Field : [Matrix_w_Borders] real, Next_Field : [Matrix] real;
A data-parallel stencil program
epsilon = 1.0E-5,
initial_border = 1.0;
const Matrix_w_Borders = {0 .. n + 1, 0 .. n + 1, 0 .. n + 1}, Matrix = Matrix_w_Borders [1 .. n, 1 .. n, 1 .. n], Single_Border = Matrix.exterior (1, 0, 0);
proc Stencil (M : [/* Matrix_w_Borders */] real, (i, j, k) : index (Matrix)) : real {
}
return (M [i – 1, j, k] + M [i + 1, j, k] + M [i, j – 1, k] + M [i, j + 1, k] + M [i, j, k + 1]
+ M [i, j, k – 1]) / 6;
© 2019 Uwe R. Zimmer, The Australian National University
page 148 of 757 (“Language refresher / introduction course” up to page 159)

Configuration constants can be set via command line options:
./Stencil –n=500
Language refresher / introduction course
config const n = 100, max_iterations = 50,
var Field : [Matrix_w_Borders] real, Next_Field : [Matrix] real;
A data-parallel stencil program
epsilon = 1.0E-5,
initial_border = 1.0;
const Matrix_w_Borders = {0 .. n + 1, 0 .. n + 1, 0 .. n + 1}, Matrix = Matrix_w_Borders [1 .. n, 1 .. n, 1 .. n], Single_Border = Matrix.exterior (1, 0, 0);
proc Stencil (M : [/* Matrix_w_Borders */] real, (i, j, k) : index (Matrix)) : real {
}
return (M [i – 1, j, k] + M [i + 1, j, k] + M [i, j – 1, k] + M [i, j + 1, k] + M [i, j, k + 1]
+ M [i, j, k – 1]) / 6;
© 2019 Uwe R. Zimmer, The Australian National University
page 149 of 757 (“Language refresher / introduction course” up to page 159)

Defining domains to be used for multi-dimensional array declarations and assignments.
Language refresher / introduction course
config const n = 100, max_iterations = 50,
var Field : [Matrix_w_Borders] real, Next_Field : [Matrix] real;
A data-parallel stencil program
epsilon = 1.0E-5,
initial_border = 1.0;
const Matrix_w_Borders = {0 .. n + 1, 0 .. n + 1, 0 .. n + 1}, Matrix = Matrix_w_Borders [1 .. n, 1 .. n, 1 .. n], Single_Border = Matrix.exterior (1, 0, 0);
proc Stencil (M : [/* Matrix_w_Borders */] real, (i, j, k) : index (Matrix)) : real {
}
return (M [i – 1, j, k] + M [i + 1, j, k] + M [i, j – 1, k] + M [i, j + 1, k] + M [i, j, k + 1]
+ M [i, j, k – 1]) / 6;
© 2019 Uwe R. Zimmer, The Australian National University
page 150 of 757 (“Language refresher / introduction course” up to page 159)

Declaring matrices of different, yet related dimensions.
Language refresher / introduction course
config const n = 100, max_iterations = 50,
var Field : [Matrix_w_Borders] real, Next_Field : [Matrix] real;
A data-parallel stencil program
epsilon = 1.0E-5,
initial_border = 1.0;
const Matrix_w_Borders = {0 .. n + 1, 0 .. n + 1, 0 .. n + 1}, Matrix = Matrix_w_Borders [1 .. n, 1 .. n, 1 .. n], Single_Border = Matrix.exterior (1, 0, 0);
proc Stencil (M : [/* Matrix_w_Borders */] real, (i, j, k) : index (Matrix)) : real {
}
return (M [i – 1, j, k] + M [i + 1, j, k] + M [i, j – 1, k] + M [i, j + 1, k] + M [i, j, k + 1]
+ M [i, j, k – 1]) / 6;
© 2019 Uwe R. Zimmer, The Australian National University
page 151 of 757 (“Language refresher / introduction course” up to page 159)

Function which calculates a “stencil” value at a spot inside a given matrix
Note the index type
Language refresher / introduction course
config const n = 100, max_iterations = 50,
var Field : [Matrix_w_Borders] real, Next_Field : [Matrix] real;
A data-parallel stencil program
epsilon = 1.0E-5,
initial_border = 1.0;
const Matrix_w_Borders = {0 .. n + 1, 0 .. n + 1, 0 .. n + 1}, Matrix = Matrix_w_Borders [1 .. n, 1 .. n, 1 .. n], Single_Border = Matrix.exterior (1, 0, 0);
proc Stencil (M : [/* Matrix_w_Borders */] real, (i, j, k) : index (Matrix)) : real {
}
return (M [i – 1, j, k] + M [i + 1, j, k] + M [i, j – 1, k] + M [i, j + 1, k] + M [i, j, k + 1]
+ M [i, j, k – 1]) / 6;
© 2019 Uwe R. Zimmer, The Australian National University
page 152 of 757 (“Language refresher / introduction course” up to page 159)

… anything on this slide still not perfectly clear?
Language refresher / introduction course
config const n = 100, max_iterations = 50,
var Field : [Matrix_w_Borders] real, Next_Field : [Matrix] real;
A data-parallel stencil program
epsilon = 1.0E-5,
initial_border = 1.0;
const Matrix_w_Borders = {0 .. n + 1, 0 .. n + 1, 0 .. n + 1}, Matrix = Matrix_w_Borders [1 .. n, 1 .. n, 1 .. n], Single_Border = Matrix.exterior (1, 0, 0);
proc Stencil (M : [/* Matrix_w_Borders */] real, (i, j, k) : index (Matrix)) : real {
}
return (M [i – 1, j, k] + M [i + 1, j, k] + M [i, j – 1, k] + M [i, j + 1, k] + M [i, j, k + 1]
+ M [i, j, k – 1]) / 6;
© 2019 Uwe R. Zimmer, The Australian National University
page 153 of 757 (“Language refresher / introduction course” up to page 159)

Language refresher / introduction course
Field [Single_Border] = initial_border; for l in 1 .. max_iterations {
A data-parallel stencil program (cont.)
forall Matrix_Indices in Matrix do
Next_Field (Matrix_Indices) = Stencil (Field, Matrix_Indices);
const delta = max reduce abs (Field [Matrix] – Next_Field);
Field [Matrix] = Next_Field;
if delta < epsilon then break; } © 2019 Uwe R. Zimmer, The Australian National University page 154 of 757 (“Language refresher / introduction course” up to page 159) Scalar to 2-d array-slice assignment (Technically a 3-d domain with two degenerate dimensions) 3-d array to 3-d array-slice assignment Language refresher / introduction course Field [Single_Border] = initial_border; for l in 1 .. max_iterations { A data-parallel stencil program (cont.) forall Matrix_Indices in Matrix do Next_Field (Matrix_Indices) = Stencil (Field, Matrix_Indices); const delta = max reduce abs (Field [Matrix] - Next_Field); Field [Matrix] = Next_Field; if delta < epsilon then break; } © 2019 Uwe R. Zimmer, The Australian National University page 155 of 757 (“Language refresher / introduction course” up to page 159) Data parallel application of the Stencil function to the whole 3-d matrix Language refresher / introduction course Field [Single_Border] = initial_border; for l in 1 .. max_iterations { A data-parallel stencil program (cont.) forall Matrix_Indices in Matrix do Next_Field (Matrix_Indices) = Stencil (Field, Matrix_Indices); const delta = max reduce abs (Field [Matrix] - Next_Field); Field [Matrix] = Next_Field; if delta < epsilon then break; } © 2019 Uwe R. Zimmer, The Australian National University page 156 of 757 (“Language refresher / introduction course” up to page 159) Data parallel (divide-and-conquer) application of the max function to the component-wise differences. “3-d data-parallel version” of (Haskell): foldr max minBound $ zipWith (-) field next_field Language refresher / introduction course Field [Single_Border] = initial_border; for l in 1 .. max_iterations { A data-parallel stencil program (cont.) forall Matrix_Indices in Matrix do Next_Field (Matrix_Indices) = Stencil (Field, Matrix_Indices); const delta = max reduce abs (Field [Matrix] - Next_Field); Field [Matrix] = Next_Field; if delta < epsilon then break; } © 2019 Uwe R. Zimmer, The Australian National University page 157 of 757 (“Language refresher / introduction course” up to page 159) ... anything on this slide still not perfectly clear? Language refresher / introduction course Field [Single_Border] = initial_border; for l in 1 .. max_iterations { A data-parallel stencil program (cont.) forall Matrix_Indices in Matrix do Next_Field (Matrix_Indices) = Stencil (Field, Matrix_Indices); const delta = max reduce abs (Field [Matrix] - Next_Field); Field [Matrix] = Next_Field; if delta < epsilon then break; } © 2019 Uwe R. Zimmer, The Australian National University page 158 of 757 (“Language refresher / introduction course” up to page 159) Language refresher / introduction course • Specification and implementation (body) parts, basic types • Exceptions & Contracts • Information hiding in specifications (‘private’) • Generic programming Summary Language refresher / introduction course • Tasking • Monitors and synchronisation (‘protected’, ‘entries’, ‘selects’, ‘accepts’) • Abstract types and dispatching • Data parallel operations © 2019 Uwe R. Zimmer, The Australian National University page 159 of 757 (“Language refresher / introduction course” up to page 159)