ADT Signature Specifications

What Is a Signature Specification?

A signature specification formally describes an ADT by listing all its operators (operations), along with:
- The name of each operator
- The argument types (inputs)
- The result type (output)

This is analogous to a function declaration: it tells you what you can do with the ADT without saying how it is done.

KEY TAKEAWAY: A signature is a formal contract — it specifies precisely what operations exist and what types they consume and produce.

General Notation

The standard notation used in VCE Algorithmics is:

operatorName : ArgumentType1 × ArgumentType2 × ... → ResultType

× denotes a Cartesian product (multiple arguments)
→ separates argument types from result type
Special types: Boolean, Integer, Element, ADTName

Example: Stack ADT Signature

A stack operates on the LIFO (Last In, First Out) principle.

Operator	Signature	Description
`empty`	`→ Stack`	Create a new empty stack
`push`	`Stack × Element → Stack`	Add element to top
`pop`	`Stack → Stack`	Remove top element
`top`	`Stack → Element`	Return top element (without removing)
`isEmpty`	`Stack → Boolean`	True if stack has no elements

Example: Queue ADT Signature

Operator	Signature	Description
`empty`	`→ Queue`	Create an empty queue
`enqueue`	`Queue × Element → Queue`	Add element to rear
`dequeue`	`Queue → Queue`	Remove element from front
`front`	`Queue → Element`	Return front element
`isEmpty`	`Queue → Boolean`	True if queue is empty

Example: Dictionary ADT Signature

Operator	Signature	Description
`empty`	`→ Dictionary`	Create empty dictionary
`insert`	`Dictionary × Key × Value → Dictionary`	Add key-value pair
`lookup`	`Dictionary × Key → Value`	Retrieve value for key
`delete`	`Dictionary × Key → Dictionary`	Remove key-value pair
`hasKey`	`Dictionary × Key → Boolean`	Check if key exists

Reading a Signature

Consider: push : Stack × Element → Stack

Operator name: push
Arguments: takes a Stack AND an Element
Result: returns a new Stack (with the element on top)

This tells us push is a function that, given an existing stack and some element, produces a new stack.

EXAM TIP: In VCAA exams, you may be asked to write or complete a signature specification. Ensure argument and result types are precise — use the exact type names and × notation.

Common Mistakes

Forgetting that constructors (like empty) have no arguments: → Stack, not Stack → Stack
Confusing pop (returns the modified stack) with top (returns the element)
Using informal descriptions instead of typed signatures

COMMON MISTAKE: Do not write pop : Stack → Element. In many VCE specifications, pop returns the modified stack, and top returns the element. Check which convention your course uses.

Why Signatures Matter

Signatures enable:
1. Formal verification — algorithms can be proven correct using only the signature
2. Implementation independence — any data structure satisfying the signature is valid
3. Communication — precise, unambiguous description shared by all programmers

ADT Signature Specifications

Table of Contents

About these notes

Join StudyPulse