NORMA (Раздаточные материалы)

NORMA

Language Description

September 14, 1998

Version 2.0

Keldysh Institute of Applied Mathematics

Russia Academy of Sciences

Contents

Introduction 41. Technical background 4

2. Aims 4

3. The goals of NORMA usage 5

Norma language specification 7

1. Application domain and main characteristics 7

2. Syntax notation 7

3. Principal language elements 8

3.1. Lexical rules 8

3.1.1. Principal symbols 8

3.1.2. Commentaries 9

3.1.3. Tokens 9

3.1.4. Identificators 9

3.1.5. Key words 10

3.1.6. Constants 10

3.1.7. Signs of operations 11

3.1.8. Delimiters 11

3.2. Names 12

3.3. Basic data types 12

3.4. Expressions 13

3.4.1. Arithmetical expressions 13

3.4.2. Conditional expressions 14

4. Program structure 15

5. NORMA constructions 17

5.1. Declarations 17

5.1.1. Declarations of domains 18

5.1.1.1. Declaration of unconditional domain 19

5.1.1.2. Declaration of conditional domain 22

5.1.2. Declaration of domains’ indexes 23

5.1.3. Declaration of variables 24

5.1.4. Declaration of domain parameters 25

5.1.5. Declaration of input and output 25

5.1.6. Declaration of external names 29

5.1.7. Declaration of distribution indexes 29

5.2. Operators in NORMA 30

5.2.1. Scalar operator 30

5.2.2. ASSUME operator 31

5.2.3. Function calls in Norma 32

5.2.3.1. Standard arithmetical functions 33

5.2.3.2. Reduction functions 33

5.2.3.3. User’s external functions 36

5.2.4. Part call 37

5.2.5. Interface with FORTRAN programs 38

5.2.6. Setting of sequential computing mode 39

5.3. Iteration 39

Appendix 1. Representation of initial program 43

Appendix 2. Syntax rules 44

Bibliography 55

Introduction

NORMA is a declarative language aimed at computation tasks’ specifications. Translator of the language has besides traditional functions of semantic and syntax analysis a function of output program synthesis during the translation. In other words the mode and the order of computations depended on target computer language and architecture are arranged.

The principal ideas of automated program design based on task’s specification were formulated by I.B. Zadykhailo [1] even in 1963. Their further development gave birth to NORMA language [2-4]. Some examples of NORMA practical usage are described in [5].

Authors consider the approach used in Norma design and realisation useful for creation of new generation languages. The development of parallel computers enhances the value of this method.

1. Technical background

The idea of the NORMA language was produced by applied mathematicians from KIAM (Keldysh Institute of Applied mathematics) RAS (Russian Academy of Science). It was an attempt of automated program design based on the jobs (application of numerical methods to physical problems solution) prepared for further programming.

It was 1960 when the first works on this theme appeared in our institute.The method of writing jobs in this work was called “parameter record”. Later on such methods had the name “non-procedure specifications” and afterwards they were called “declarative specifications”. The languages used these methods are of specification type where the rules of data computations must be defined but the order of computations may be arbitrary (e.g. in parallel or sequential mode) according to the rules.

Many researches on programming theory and practical results proved the correctness of the chosen path. Some corroborating aspects are given below.

2. Aims

Practical value of application software design methods depends on the degree of:

1) automation of design process,

2) portability and reliability of the output program,

3) convenience for the specialist in particular application domain.

The problems of providing all these items has been solving for the whole period of computer usage but there have been no universal and perfect methods for their solution yet. It can be explained by complicity of these problem and very fast development of the programming as a branch of science (new application domains and new hardware appear very quickly).

Progress in computer technology and architecture provides ample computational potentialities. But taking into consideration 1)-3) requirements their perfect practical application has many difficulties. Thus when multiprocessor computers appeared the question of new application software design was raised.

Probably application programmer wants to know as little as possible about the architecture of a particular computer but to use its resources as much as possible. He’d like to have convenient tools for test and debugging but no problems with programs’ portability. To work using generic methods and terms is also very important for application programmer. He needn’t know questions which are alien to him [compiler’s peculiarities, programming languages, system library organization and the questions of its effective usage, etc.].

The NORMA language and the approach to application program design is an attempt to take into consideration 1)-3) requirements. The authors of this approach realize the difficulties of the fundamental task solution and the fact that universal and perfect way to this solution couldn’t be found immediately. Though we can point out some goals of these approach even now.

3. The goals of NORMA usage

High level of automation of the application design process.

Initial equations are formalized only to make input from keyboard easy. It is important that the issue of the formulae isn’t changed. Thus the programming phase is skipped and further design of the program is carried out automatically

Reliability and portability of the programs.

If the method of the task solution is right and the formulae are written correctly an output program will be also correct ( because the process of programming is automatic).

We have to underline that the strict specification of the task solution process on the application domain level is very important. This level is the most reliable because it deals only with the scheme of the computations and doesn’t depend on the optimizations which can be realized during programming phase. It is evident that if we propose the language for the strict specification of the task solution process in the terms of application domain automatically designed program based on this specification will have the degree of reliability corresponding to the one of the translator and the translator’s optimization level.

NORMA used only the terms of application domain associated with the grid-based mathematical physics tasks solutions. Simplicity and reliability of the programs are provided by eliminating of the programming phase and required only the knowledge of application domain terms and their correct usage.

Synthesising translator from NORMA allows for computer architecture peculiarities. It provides portability of the application programs.

Method of parallel program design.

Generic mathematical formulae usage in NORMA has great possibilities for problem optimization in all cases including realization on parallel systems.

The specification of the task solution keeps its natural parallelism. This specification doesn’t contain any adaptation constraints to computer architecture, programming language peculiarities or other requirements. It is “clear” specification of task solution which restricts only computation order according to the computation scheme content (informatic dependencies between variables).There is no term “memory” for storing different values in different periods of time. It simplifies natural parallelism revealing algorithms design and creation of the target program.

In the cases where computation order is important (e.g. it affects the precision of computations, rate of convergence, etc.) supplementary notions may be used (they are interpreted in a special way).

Norma language specification

1. Application domain and main characteristics

The NORMA language is a specialized language applied to numerical - based specification of the mathematical physics problems solutions. First it was directed towards solving mathematical physics‘ problems by means of grid difference method solutions. But later practice shows us that NORMA application domain could be more extensive.

Originally NORMA could be deciphered as: Non-procedure Specification of the Difference Algorithm Models. Nowadays we decode this abbreviation as NORMAl level of computer - mathematician communication. Mathematician’s formulae are input almost directly into the computer system.

NORMA requires no information about computation order and ways of computation process organization. The order of the sentences may be arbitrary ( informatic connections are revealed during the translation).

Value can be assigned to any variable in NORMA only once. This feature characterizes the level of the NORMA language. There is no such terms as “memory”, side effect, assignment statement, control operators in NORMA.

These characteristics and some other constraints (first on the form of index statements and ways of index domain specifications) substantiate solvability of output program synthesis problem [2,3]. Generic solution of this problem has substantial mathematical difficulties (the task may be NP-complete or undecidable). On the other hand researches on NORMA applications and design show that the constraints are acceptable practically [5].

2. Syntax notation

Extended Backus-Naur form is used in the given syntax notation.

{A}*, {A}⁺, {A_{1, . . . ,} A _n }_, [A] symbols mean

where A - any language object ,

- empty,

- alternative choose,

... etc.

Syntax notions are written in italics, but words and symbols of common usage are printed in a usual way. As a rule, alternative constructions are arranged in columns (each construction on a separate line).

Sometimes half-underlined syntax constructions are used, e.g. name-set. Syntactically this name is identical to symbol name but underlined part of the construction has additional semantic information.

Symbol list-element substitutes non-empty list of elements enumerated by comma:

list-element :

element { , element }*

The definition of the element is given in every particular case.

Usually syntactical rules are given first; commentaries, semantic explanations, examples, etc. follow.

3. Principal language elements

3.1. Lexical rules

Symbols are a base for all the constructions, they are original language elements. The number of principal symbols is fixed and used for the design of any language constructions. The number of supplementary symbols isn’t fixed and settled by the type of computer equipment. They are used for symbolic constants formation and data representation for medium.

3.1.1. Principal symbols

principal-symbol :

letter

digit

special-symbol

letter :

{ A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z }

{ a,b,c,d,e,f,g,h,i,j k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}

digit :

{ 0,1,2,3,4,5,6,7,8,9 }

special-symbol :

special-symbol-not-apostrophe

apostrophe

special-symbol-not-apostrophe :

{ space ,=,>,>,+,-,*,/,(,),[,],!,?,,,.,#}