type hue = set of colour
Some languages have bags (multisets - sets that permit repeated values)
or power sets.
{red, yellow}
{n: 1 n 100 and n mod 2 == 0}
type pigment = colour * real
or
struct pigment {colour paint; float intensity;} pigment
(red, .50)
let (paint, intensity) = pigment_instance in ... end
or pigment_instance.paint
paint of pigment_instance
int a[] = {1, 2, 3, 4, 5};
some languages allow e.g. {6=>3, 7..15=>4, others=>--1}
a [j] = a [i];
"hello"
) or bit strings (0xF0AD
).
[1, 2, 3] "ABC" 1::[2, 3]
RDTs can also be used to build trees, but general graphs can only be represented by e.g. one list of nodes and another list of links between nodes.
Constructors: some languages allow pointers to any named variables
and/or functions e.g. a = &i
, some only allow them to anonymous data
items e.g. a = malloc(...)
and usually also disallow pointer
arithmetic.
There are two main rationalisations for restricting pointers to anonymous
data items:
extent (sometimes known as dynamic scope) describes the lifetime of a
variable. We often want to call a function to create a data structure that
uses pointers, and if the lifetime of the objects pointed at is the same as
that of the function they were created in, this will not be of any use.
However, it is not clear that this means that pointing to data items with a
short lifetime should be prohibited. Nor do all languages that disallow
pointers to named items cope with the problem that an anonymous item can be
explicitly killed (e.g. by free
) without all relevant pointers being
reset. Some languages use various tricks, such as garbage collection,
to help solve this problem.
aliasing is the concept of an object, such as a data item, having more
than one name. This makes life more difficult both for humans and compilers
trying to understand a program. If a pointer can be used to access a named
data item, then the data item has an alias. A similar problem occurs with
parameters. However, even if we prohibit pointers to named data items, we
can still have more than one pointer to the same anonymous data item, which
is still aliasing.
Operations: dereferencing
some languages insist on an explicit dereference operation e.g. *a = 1
,
whereas some automatically dereference pointers e.g. a = 1
. The
latter is nifty but dangerous e.g. if a
and b
are both
pointers to integers, a = b
changes the value of a
, but
a = b + 1
changes the value of whatever a
points at and leaves
a
itself unchanged.
There is a related problem with accesses to var- or ref-parameters.
There is also something related going on in assignments e.g. a = b
-
we treat a
and b
rather differently, in that b
could be
anything that can be evaluated, such as a function call or a constant, but
a
has to be a variable and we do not use its value but instead its
location. There are some languages where we can even write
e.g. (a ? b : c) = d
and the left-hand expression is manipulating the
locations of b
and c
, not their values, and then automatically
dereferencing the location to store the value of the right-hand side in it
- such a language often treats all variables as if they were references to
values, and pointer variables as references to references to values, and so
on (e.g. Algol 68).
Other operations: tests for equality, inequality, nul pointer
Pointer arithmetic is dangerous, but some languages allow it (strongly typed
languages usually do not). It is often useful, for example, to obtain
pointers to components of a data structure, given a pointer to the whole
structure e.g. when stepping through the elements of an array. Pointer
arithmetic and automatic dereferencing cannot both be allowed in a
programming language, unless we can avoid overloading the arithmetic
operators - the caveat above hints that even pointer assignment should not
be mixed with automatic dereferencing.
C function to insert an item into an ordered list
using pointers to anonymous (malloc) variables
($CS2111/e*/insert/*
):
typedef struct node {int item; struct node* next;} node; node *insert_1 (int new_item, node *list) { node *temp, *prev, *new= (node*) malloc(sizeof(node)); new->item= new_item; if (!list || new_item<=list->item) { new->next= list; return new; } temp= list; prev=NULL; while (temp && temp->item<=new_item) { prev= temp; temp= temp->next; } new->next= temp; prev->next= new; return list; }C function to insert an item into an ordered list using pointers to named variables (
$CS2111/e*/insert/*
):
node *insert_2 (int new_item, node *list) { node **temp, *new= (node*) malloc(sizeof(node)); new->item= new_item; temp= &list; /* <------------------------ pointer to named variable */ while (*temp && (*temp)->item<=new_item) temp= &((*temp)->next); new->next= *temp; *temp= new; return list; }