Glossary

Glossary

abstract data type
We use the term abstract data type differently from the usual definition used in computer science research. Here, and abstract data type is a type with a well-defined interface and semantics.

Examples of abstract data types are: stack. queue, union-find set, priority queue, etc.

Some data types don't have well-defined interfaces, but are useful for implementing abstract data types. We call them implementation types.

buffer
An array of elements. When used to implement a container, usually dynamically resizeable. A buffer is not an abstract data type, but an implementation type.
container
An abstract data type whose sole purpose is to contain other objects. Different containers differ in the way the elements are accessed. Examples of containers are: set, stack, queue, double-ended queue, priority queue, dictionary, etc.
defect
Popularly known as a bug. A programming error that causes the program to fail, i.e. not accomplish its nominal task.

delegation
A technique that consists of using a more powerful abstract data type to implement a less powerful one, by using a subset of the operations on the more powerful data structure.
double-ended queue
A container holding a sequence of elements and allowing you to insert and delete elements both at the beginning and at the end of the sequence.
exception
1. An unusual situation that occurs as a result of the execution of parts of a program, such as attempting to open a file that does not exist, or attempting to allocate memory where non is available.

2. A mechanism in certain programming languages designed specifically to handle exceptional situations.

failure
A situation where a program is in a state that was not foreseen by the programmer. A program in such a state has a defect or is said to be defective.

A failure may or may not be detected by the program itself. If, undetected, the failure just causes the program to do the wrong thing.

generic pointer
A pointer of type void *. It is called generic because it can point to any object. This is useful for implementing containers.
header object
An object sometimes required in order to preserve uniform reference semantics.

implementation type
Implementation types are types that are not well-defined enough that they can be considered abstract data types.

Examples of implementation types are: list, doubly-linked list, circular list, binary tree, table.

list
Same as a linked list. Can be simply or doubly linked, but usually simply linked if not explicitly known to be doubly linked.

A linked list is not an abstract data type, but an implementation type. There is therefore no point in trying to write a module named list with a well-defined interface. Usually, a linked list will be defined like this:

	typedef struct cell *list;
	      
	struct cell
	{
	  void *element;
	  list next;
	};
nonlocal goto
A goto-instruction that jumps to a place outside the procedure in which it is located.

Nonlocal gotos can be used as a primitive mechanism for handling exceptions.

predicate
A function that that returns a boolean value. Usually, predicates are side-effect free, and are used to test the state of some kind of data structure.
queue
A container holding a sequence of elements and allowing you to insert elements at one end of the sequence and delete elements from the other end of the sequence.
scaffolding
Pieces of programs whose sole purpose is to aid in testing and debugging. Scaffolding is not part of the application itself. Scaffolding may take the form of stubs, or of test functions.
set
An unordered collection of items. Sets are very hard to implement efficiently in general. It is therefore common to find special versions of sets, such as ordered sets, sets that only support a subset of the usual set operations, etc.

side effect
An operation that changes the global state of the program. It is good practice to avoid side effects whenever practical, as it makes the program easier to maintain and to test.
stack
A container holding a sequence of elements and allowing you to insert elements at one end of the sequence and delete elements from the same end of the sequence.
stubs
Pieces of programs, usually functions or procedures, that provide the correct interface but not the correct implementation of some other piece of program, typically a function or an abstract data structure. A stub makes it possible to test certain aspects of a high-level function or abstract data type without having implemented all of the lower-level functions or abstract data types that it uses. Stubs are necessary when top-down programming is used.
test functions
Functions whose sole purpose is to be clients of other functions or abstract data types, in order to test the latter. Test functions are not part of the application, but exist only to test other parts of the application before the real clients are written. Test functions are necessary when bottom-up programming is used. However, sometimes an interactive programming environment such as Common Lisp or GDB can replace parts or all of the test functions necessary.