- 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.