Presentation of the Z language

 

Overview
Structure of a Z algorithm
Definition of an action
Definition of a function
An example of a Z algorithm
Objects
Expressions
Instructions
Operations on abstract machines
High level Operations
Standard fonctions
 

 

Overview                                                                                                           

 

> A Z algorithm is a set of modules. The first one is the main module and the others are either actions (ACTION) or functions (FUNCTION).

> The Z language accepts recursion.

> Static objects are declared in the main module.

> The communication between modules is made via parameters and static variables.

> The language allows:

- Any type of parameters : scalars, structures, linked lists , queues, stacks, arrays, trees and also complex types.

- The dynamic allocation of arrays and structures

- The global assignment of any type

> Four standard types ( scalars) are allowed  : INTEGER, BOOLEAN, CHAR, STRING .

> Some usual functions exist :  MOD, MAX, MIN, RANDOMNUMBER, RANDOMSTRING,...

> The langage is the set of abstract algorithms written by using abstract machines.

> So, we considere abstract machines on structures, arrays of any dimension, queues, stacks, binary and m-ary search trees, linked lists and bidrectional linlked lists.

> We also consider an abstract machine on the files allowing their use and the construction of simple structures of files as well as the most complex structures.

> The language allows compound types such as STACK OF QUEUE OF LISTS OF ....of which the last one quoted is of scalar type or simple structure.

> The language has high-level operations to build lists, trees, queues, etc. from a set of values ( expressions ) or structures.

> the language offers two very useful functions to randomly generate strings (ALEACHAINE) and integers (ALEANUMBER).

> The language allows reading and  writing scalars, n-dimensional arrays of scalars and simple or complex structures.

Structure of a Z algorithm                                                                                        


    LET
        { Local and statitc objects }
        { announcement of the modules}
    BEGIN
        { Instructions }
    END
    Module 1
    ....
    Module n

Each module can be either a function or an action.

Definition of an action                                                             

    ACTION Name (P1, P2, ..., Pn)
            { Local objects and parameters }
    BEGIN
        { Instructions }
    END

Calling an action is made by the operation CALL followed by the name of the action and its parameters.

Parameters are not protected by the action.

Definition of a function                                                     

    FUNCTION Name (P1, P2, ...,Pn) : Type
            { Local objects and parameters }
    BEGIN
        { Instructions }
    END

Type can be any.

Functions are used in expressions.

Parameters are not protected by the function.

Example of a Z-algorithm                                           

LET
L1, L2 : LISTS;
Rech, Tous : FUNCTION(BOOLEAN);
BEGIN
CREATE_LIST(L1, [2, 5, 9, 8, 3, 6 ]);
CREATE_LIST(L2, [12, 5, 19, 8, 3, 6, 2,9]);
WRITE( Tous(L1, L2) )
END

FUNCTION Rech ( L, Val ) : BOOLEAN
LET
L : LIST; Val : INTEGER;
BEGIN
IF L = NULL : Rech := FALSE
ELSE
IF CELL_VALUE(L) = Val :
Rech := TRUE
ELSE
Rech := Rech(NEXT(L), Val )
ENDIF
ENDIF
END
FUNCTION Tous ( L1, L2 ) : BOOLEAN
LET
L1, L2 : LISTS;
BEGIN
IF L1 = NULL : Tous := TRUE
ELSE
IF NOT Rech(L2, CELL_VALUE(L1) )
Tous := FALSE
ELSE
Tous := Tous(NEXT(L1), L2)
ENDIF
ENDIF
END


Objects
    
                                                                

Objects can be scalars : INTEGER, BOOLEAN, CHAR, STRING.

Objects can be abstract machines : structures, arrays of any dimension, queues, stacks, binary and m-ary search trees, linked lists and bidrectional linlked lists.

 

Examples :

L1 , L2 : LISTS ;
A : STRUCTURE ( STRING , INTEGER ) ;
V1 : ARRAY ( 10 , 60 ) OF ( CHAR , INTEGER ) ;
Y : LIST OF STACKS OF ARRAY ( 10 ) ;
F1 : FILE OF ( STRING , ARRAY ( 5 ) OF INTEGERS ) BUFFER Var1 , Var2 ;

The default type is INTEGER.

 

Structures :

A structure can be simple, i.e., only consisting of scalar or complex and in this case it can contain scalars and/or one-dimensional arrays of scalars.

A structure definition specifies a set of types. Each type can be a scalar or a one-dimensional array of scalars.
 

Files :

A file definition consists of 3 parts:

** The first part (FILE) specifies the nature of the elements in the file.

a file record can be :

- a scalar, i.e of a simple type ( INTEGER, BOOLEAN, CHAR, STRING ),

- a one-dimensional array of scalars

- a structure that can contain  scalars or one-dimensional arrays of scalars.

** The second part defines the variables ( record or block ) used in the reading and writing operations.

** The third part describes the file features by specifying the type of each feature. This part is mainly used for the creation of user file structures and is used to store all the information useful for the exploitation of the file.
 

Expressions                                                                                                       

As in the programming languages.

Examples :

(B+C) / F , NOT Found, (X # 5) And NOT Found, F(x) <> 5

Instructions                                                                                        

V denotes a variable, E an expression and Idf a module  identifier.

[ ] denotes an optional part and { } a set.

Assignment  : V := E

Reading : READ(V1, V2, .....)

Variables can be scalars, structures or arrays of any dimension.

Writing : WRITE(E1, E2, .....)

Expressions can be scalars, structures or n-dimensional arrays.

Calling : CALL Idf [ ( E1, E2, ...) ]

Calling an user action is made by APPEL.

Conditional :

    IF E [ : ]
        { Instructions }
    [ ELSE
        { Instructions } ]
    ENDSI

Loop ( Form 1)

    WHILE E [ : ]
        { Instructions }
    ENDWHILE

Loop ( Form 2)

    FOR V := E1, E2 [,E3]
        { Instructions }
    ENDFOR                

E3, if present, designates the step.

 

Operations on abstract machines                                  

Linked liste : ALLOCATE_CELL , FREE , VALUE, NEXT, ASS_ADR, ASS_VAL

Bidirectional linked lists : ALLOCATE_CELL , FREE , VALUE, NEXT, PREVIOUS,  ASS_VAL, ASS_R_ADR, ASS_L_ADR

Stacks : CREATESTACK, PUSH, POP, EMPTY_STACK

Queues : CREATEQUEUE, ENQUEUE, DEQUEUE, EMPTY_QUEUE.

Binary search trees : ALLOCATE_NODE, LC, RC, PARENT, FREE_NODE, ASS_LC, ASS_RC, ASS_PARENT, NODE_VALUE, ASS_NODE_VAL.

Files : OPEN, CLOSE, READSEQ, READDIR, WRITESEQ, WRITEDIR, ADD, ENDFILE, HEADER, ASS_HEADER, ALLOC_BLOC.

M-ary search trees : CREATE_NODE, CHILD, FREE_NODE, ASS_CHILD, NODE_VALUE_MST, ASS_NODE_VAL_MST, DEGREE, ASS_DEGREE, PARENT, ASS_PARENT.

Arrays : ELEMENT, ASS_ELEMENT,

ALLOC_ARRAY, LIBER_ARRAY ( if dynamic array)

Structures : STRUCT, ASS_STRUCT,

ALLOC_STRUCT, LIBER_STRUCT ( if dynamic structure)

High level operations                                               

The Z language has high-level operations for filling or initializing a data structure from a set of values.

CREATE_ARB, CREATE_LISTE, CREATE_LISTEBI, CREATE_ARM, CREATE_PILE, CREATE_FILE, INIT_VECT (or INIT_ARRAY), INIT_STRUCT

Syntax :

CREATE_LIST ( L, [Exp1, Exp2, ....] )

CREATE_BILIST ( LB, [Exp1, Exp2, ....] )

CREATE_BST ( A, [Exp1, Exp2, ....] )

CREATE_MST ( M, [Exp1, Exp2, ....] )

CREATE_QUEUE ( F, [Exp1, Exp2, ....] )

CREATE_STACK ( P, [Exp1, Exp2, ....] )

INIT_STRUCT(S, [Exp1, Exp2, ....])

INIT_VECT ( T, [Exp1, Exp2, ....] )

Exp1, Exp2, .... are scalar expressions or structures.

Examples

CREATE-LIST (L, [12, 23, 67, I, I+J] )

creates the linked list L with values  with the values in square brackets in the order shown.

If L1 and L2 are 2 integer linked list and Ll a linked list of a linked list of integers, we can then write :

CREATE_LIST ( L1 , [ 2 , 4 , 67 , 778 ] ) ;

CREATE_LIST ( L2 , [ 12 , 14 , 167 , 1778 ] ) ;

CREATE_LIST ( Ll , [ L1 , L2 ] ) ;

Standard functions                                                                                

MOD (A, B)  : Give the remainder of the integer division of A by B.

MAX(A, B)  : Give the maximum between A and B.

MIN(A, B) : Give the minimum between A and B.

CHARACT(S, I) : give the i-th character of the string S.

RANDSTRING(N)  : generate an alphanumeric string of N characters.

RANDNUMBER (N) : Generate an integer between 0 and N.