CIS LECTURE 19

Abstract Data Types, (chapter 10)

• Fortran-built in data types with a set of operators
• Type checking
• Atomic in nature, (ints, reals, chars)
• Pascal-user defined data types, (name only, no operations)
• Information hiding®encapsulation, (some)
• User writes subprograms for operations and passes variables as parameters
• procedure push(var s:stack, x.item)
• push (s, x) //pushes item x onto stack s

Ada package

· C++ lies between Ada packages and Smalltalk objects

Smalltalk objects:

· Also Java, Eiffel, Fortran 9x, CommonLisp, Cobol, Pascal

Ada "open" type of objects:

· Similar to .h files in C++

· Only one type of class is active at a time

· Not very secure, class is easily accessible

Ada "unique" type:

• Moves declaration of class down in code from the public to the private section
• Only one class is active at a time
• More secure, class is not accessible

Ada "generic" type:

• Almost like a "template", except not as much copying and compilation
• Type element is private
• Allows several instantiations

E.g.

• package integer queue.is
• new queue(element is integer)

Guttag/Liskov-M.I.T.

• Algebraic notation for language independent specification of abstract data types

Specification:

1) Syntactic specification

2) Semantic specification

3) Restriction specification

5 language primitives:

· Functional composition

· Quality relation

· Constants

· "true and false"

· infinite set of free variables

1) Syntactic specification:

new stack()®stack

push(stack, item)®stack

pop(stack)®stack

top(stack)®item

isNew(stack)®boolean

2) Semantic specification:

declare s:stack

i:item

pop(push(s, i))®s

top(push(s, i))®I

isNew(new stack()) = true

isNew(push(s, i)) = false

3) Restriction specification

pop(newStack()) = error

top(newStack()) = error

Specifications for queues:

1) Syntactic specification

structure queue

newQ®queue

addQ(queue, item)®item

delQ(queue)®queue

front(queue)®item

isNew(queue)®boolean

2) Semantic specification

declare q : queue

i : item

delQ(addQ(q, i)) =

if is newQ then

newQ

else

addQ(delQ(q), i)

isNewQ(addQ(q, i)) = false

isNewQ(newQ()) = true

frontQ(addQ(q, i)) =

if isNewQ(q) then

i

else

FrontQ(q)

3) Restriction specification

delQ(newQ()) = error

frontQ(newQ()) = error