Abstract machines
Arrays Definition :
A N dimensional array can be seen as an application of the set I= [1,
Max1]X [1, Max2].....X[1, MaxN] to a set of values. An array is thus a set of
pairs (index1, a), (index2, b), ....., (indexN, e) whose first elements are
called the indices and belong to the set I. A simple machine on arrays consists
in acting only on one element, i.e. to consult or modify it. Moreover, arrays
can be static or dynamic. Operations : ELEMENT ( T [i, j, ...]
) : Access to element T[i, j, ...] of array T. ASS_ELEMENT
( T [i, j, ...], Val ) : Assign value Val to element T[i, j, ...]. ALLOC_ARRAY (T) :
Array allocation. The array address is in T.
FREE_ARRAY(T) : Free the array of address T.
Linked
linear lists Definition :
A linked linear list is a set of chains that are dynamically allocated
(i.e. during the execution of a program) and linked together. A chain generally
contains two fields: information and an address. It is the user who creates the
list, who modifies it by adding or deleting chains, who browses it in order to
perform a given treatment. A machine on linked linear lists thus consists in
offering to the user operations for the dynamic allocation of chains, operations
to fill a chain (information and chaining) and operations to consult the
contents of a chain. The machine acts only at the level of a chain. Opérations :
ALLOCATE ( P ) : Create a chain and return its address in P.
FREE ( P ) : Free the node of address P.
NEXT ( P ) : Access to the 'Address' field of the node
referenced by P.
VALUE ( P ) : Access to the 'Value' field of the node
referenced by P. ASS_ADR ( P, Q ) :
Assign to the 'Address' field of the node referenced by P, the address Q.
ASS_VAL( P, Val ) : Assign to the 'Value' field of the node referenced
by P, the value Val.
Bilateral linear linked lists Definition :
A bilateral list is a linked linear list that can be traversed in both
directions. A machine on bilateral lists is defined in the same way as the one
defined on linked linear lists, except that a link instead of containing only
one address, it contains two. Consequently, we replace the ASS_ADR function by
ASS_L_ADR and AFF_R_ADR for example and add the function PREVIOUS. Operations :
ALLOCATE ( P ) :
Create a chain and return its address in P.
FREE ( P ) :
Free the node of address P.
NEXT ( P ) :
Access to the 'Right address' field of the node referenced by P.
PREVIOUS ( P ) : Access to the
'Left address' field of the node referenced by P. VALUE( P ) :
Access to the 'Value' field of the node referenced by P. ASS_VAL( P, Val ) :
Assign to the 'Value' field of the node referenced by P, the value
Val. ASS_R_ADR ( P, Q ) :
Assign to the 'Right address' field of the node referenced by P, the
address Q.
AFF_L_ADR ( P, Q ) :
Assign to the 'Left address' field of the node referenced by P, the
address Q.
Queues
Definition :
A queue obeys the 'FIFO' principle: First In First Out. It is a
collection of elements such that any new element is inserted at the end and any
removal of element is done at the beginning. A machine on the queues is thus
endowed with its two fundamental operations to which one adds some operations of
lesser importance making it possible to initialize or test the state of a queue
at any time (empty or full queue). The machine acts on the whole collection
Operations :
CREATEQUEUE ( F ) : Create an empty queue.
EMPTY_QUEUE ( F) : Test if queue F is empty. ENQUEUE ( F, Val ) : Enqueue (add
to tail) value
Val to queue F. DEQUEUE
( F, Val ) : Dequeue ( Remove from the file head )
a value from queue F et put it in Val.
Stacks
Definition :
A stack obeys the 'LIFO' principle: Last In First Out. It is a
collection of elements such that any new element is inserted at the beginning
and any removal of element is done at the beginning. A stack machine is thus
endowed with these two fundamental operations to which we add some operations
allowing to initialize or to test the state of a stack at any time (empty or
full stack). The machine acts on the whole collection. Opérations :
CREATESTACK ( P ) : Create an empty stack.
EMPTY_STACK ( P ) : Test if stack P is empty.
PUSH ( P, Val ) : Push (add to the top) value Val to stack P.
POP ( P, Val ) : Pop( Remove from the top) a value from stack P
and put it in Val.
Binary search trees Definition :
A binary search tree represents a set of data with an order relation.
All data in the left sub-tree of any node with the information x are less than
x, all data in the right sub-tree of any node with the information x are greater
than x. Since it is a dynamic data structure (composed of a set of nodes forming
a graph in which any node has at most one predecessor and at most two successors)
a machine consists of providing operations to make the dynamic allocation,
operations to fill a node and operations to consult a node. Intuitively, a node
is composed of 3 fields: information and two address fields providing the left
and right child. The machine acts only at the node level. Operations :
ALLOCATE_NODE ( Val ) : Create a node value Val and return the address of
the node. The others fields are to NIL.
FREE_NODE ( P ) : Free the node of address P.
LC ( P ) : Access to field left child of node referenced by P.
RC ( P ) :
Access to field right child
of node referenced by P. PARENT ( P ) :
Access to field parent
of node referenced by P.
NODE_VALUE ( P ) :
Access to field value
of node referenced by P. ASS_LC ( P, Q ) : Assign
the address Q to the field left child
of node referenced by P.
ASS_RC ( P, Q ) :
Assign the address Q to the field rightchild
of node referenced by P. ASS_PARENT
( P, Q ) :
Assign the address Q to the field parent of node referenced by
P. ASS_NODE_VAL(
P, Val ) :
Assign the value Val to the field value
of node referenced by P.
M-ary search trees Definition :
An m-ary search tree allows to represent a data set with an order
relation. It is a generalization of the binary search tree. Instead of having
one information and two address fields, we have p addresses and (p-1)
information in which case the m-ary search tree is said to have order p.
Intuitively, a node has the following form: (a1, v1, a2, v2, ......, vp-1, ap).
All the data in the sub-tree of root a1 are less than v1, all the data in the
sub-tree of root a2 are greater than v1 and less than v2, etc. A machine
consists of providing operations to make the dynamic allocation, operations to
fill a node and operations to consult a node. The machine acts only at the node
level.
Operations :
ALLOCATE_NODE ( Val ) :
Create a node value Val and return the address of the node. The
others fields are to NIL.
FREE_NODE ( P ) :
Free the node of address P.
CHILD ( P, I ) : Access to the i-th child
of node referenced by P. PARENT
( P ) : Access to field parent
of node referenced by P.
NODE_VALUE_MST ( P, I ) : Access to the i-th value
of node referenced by P. ASS_CHILD ( P, I, Q ) : Assign
the address Q to the i-th child
of node referenced by P. ASS_PARENT ( P, Q ) : Assign
the address Q to the field parent
of node referenced by P.
ASS_NODE_VAL_MST( P, I, Val ) : Assign the value Val to i-th value
of node referenced by P, la valeur Val. DEGREE(P) : Number
of values stocked inside
the node referenced by P. ASS_DEGREE(P, n) : Assign
the value n to the field degree of node referenced by P.
Structures
Definition :
A structure is a set of heterogeneous elements. An element of a
structure can be a scalar or a one-dimensional array of scalars. A simple
machine on structures is to get the i-th field or to assign a value in its i-th
field. Structures can be static or dynamic. In the latter case, two operations
are added to the abstract machine, allowing their allocation and release.
STRUCT(S, i) : access to the i-th field of structure S. ASS_STRUCT(S, i, Val) : Assign value Val to the i-th field of structure S. ALLOC_STRUCT(S) : allocation of a structure. The structure address is in S. FREE_STRUCT(S) : Free the structure of address S. |
Files
Definition :
A file is a set of structures, usually stored on the disk. The
structures can be items (user level) or blocks (designer level). The file
contains a particular structure (header) necessary for the design of file
structures. An abstract machine on files is to provide operations to do sequential access and direct access. Operations
F is the logical file, Fp is the physical file.
OPEN (F, Fp,
Mode) : open the logique file F and associate it to the physical file
specifying whether the file is new ('N') or old ('A').
CLOSE(F) : Close file F.
READSEQ (F, V) : Read in buffer V the record (or block) that is
in current position.
WRITESEQ (F, V) : Write the record (or block) V to the current
position.
READDIR (F, V, n) : Read into V the n-th record (or block) of file
F.
WRITEDIR (F, V, n) : Write record (or block ) V to n-th position.
ADD (F, V) : Add record (or block) V at the end of file F.
ENDFILE (F) : Predicate equal to true if the end of file F is
reached, false otherwise. ALLOC_BLOCK(F)
: Position of a block in which we can write.
HEADER (F, i) : Get the i-th feature of file F. ASS_HEADER(F,
i, v) : Assign V as the i-th feature of file F.