Abstract machines

 

Arrays

Linked lists

Bilateral linked lists

Files  

Stacks

Binary search trees

M-ary search trees

Structures

Files

 

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.

 

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.

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.

 

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.

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.

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.

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.

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.
 

Operations

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.

 

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.