Home Tutorial Comparison Top

Algorithms in *AIDA: Explanation by Comparisons

*AIDA language constructs and expressions essentially differ from constructs and expressions of conventional programming languages. Based on space-time paradigm, they represent some temporal activities (fronts of computation) on multi-dimensional space data structures. However, for cases of one node structures (substructures) temporal activities are reduced to flow-of-control constructs similar to ones of existing languages. In this chapter, to explain the *AIDA language some comparisons of its constructs with constructs of conventional languages are provided.

  1. Declarations of variables and constants
  2. Flow-of-control: if and if-else constructs
  3. Repetition of actions: while and for constructs
  4. Flow-of-control: break, switch, and nested if-else contruct
  5. Functions, procedures and components

Declarations of variables and constants

Algorithms are partially ordered operations on problem (application) attributes represented by variables and constants which should be declared in some ways. Among such declarations, fundamental data types including integer, character, float, double and others are employed. Scalar variables of these types can be integrated into compound data types of arrays, lists, stacks, and other objects. In addition, user-defined types through aggregating data elements, possibly of different types, can also be declared and defined. Some languages, directly or indirectly, allow attaching units of measure to application variables.

In *AIDA there is a special focus on presenting algorithms as a partially ordered activity in space structures (of our 3-D world) and on some visualization of this activity. So, to declare application variables, first it is necessary to declare space structures where processes of simulation will be performed. 1-D, 2-D, and 3-D grids or other space configurations including sets of moving particles and various graphs (diagrams) can be selected by putting corresponding generic a-pictures on the left side of a header row in Main view of *AIDA program. Then to all nodes (particles) of a space structure a fundamental type variable is attached. In this way, a compound variable with elements associated to each node of the structure is declared.

In fact, the attachment can be done not to all nodes (and/or edges) of the structure, but only to its natural sub-structures (for example, the main diagonal or the first row can be such sub-structures of a 2-D structure). This means that in different substructures different data types can be attached. On the other hand, the same structure (substructure) can have many variables associated to it.

*AIDA program usually represents a model of some real world phenomenon, so requests from the editor of *AIDA environment to declare units of measure for the application variables (for example, representing temperature, pressure, etc.) are considered as natural hints to be taken into account.

Hereafter, three examples related to variable declarations are presented. In the first example, a 2-D structure of M × N size (named st1) is declared with double float A and B, and integer I attached to all nodes of the structure. In addition, one-node structure (named st2) of so called observer with double float e is also defined.

The observer structure is used to imitate some "observation" of activity in a system of space structures from a "meta-system" or just to organize some centralized computation. In Example 2.1. a special annotation to variable A declaration is mentioned. This annotation is automatically generated and demonstrated on demand after the application programmer has attached temperature in K (Kelvin) to variables A and B.

In Example 1.2 (Fig.2.2), the second row provides some declaration of a mask. This type of declaration allows introducing more complicated space structures with a simple way of their understanding (see an example below, as well as the next subsection for if and if-else constructs).

Flow-of-control: if and if-else constructs

In conventional languages the general forms of the if and if-else constructs look like the following:

if (expr)
    statements
if (expr)
    statements-A
else
    statements-B

For the first construct, if expr is true, then the statements are performed; otherwise they are skipped. For the second construct, if expr is true, then the statements-A are performed and statements-B are skipped; if expr is false, then the statements-B are performed and statements-A are skipped.

In *AIDA, to define such types of flow-of-control, there are two icons applying on the level of algorithmic frames/scenes (where a space data structure is considered as a whole) and a set of icons used on the level of formulas (operations specified in different nodes of space data structure). In addition, there is an open set of mask icons (please, see sub-section 3.3) to skip operations in some nodes of the data space structures.

The first set of the flow-of-control icons includes the following generic a-pictures:

 

and

 

The rhombus micro-icon is used to define a conditional expression and the square micro-icon is used to define a body of computation on some space data structures. An example of a complete form of these constructs is shown below.

Within the body of computation, one algorithmic scene is shown. It is related to operations on nodes of a traversal scheme in a 2-D structure. The red circle says that reading or writing operations are available in nodes where the traversal front is currently active. The body is started at step 2 (at CyberFrame 2 of Dynamics details view), if nstep < tstop.

The second set of the flow-of-control a-pictures includes the following:

        ....   

These a-pictures are for defining the if, if-else and 4-nested if-else constructs on the level of node formulas; after such an a-picture, a rhombus micro-icon with a conditional expression and wave micro-icons with corresponding statements are allocated. In the case of the third a-picture, four conditional expressions and five statements should be involved.

Repetition of actions: while and for constructs

In conventional languages the general forms of while-do, do-while, and for loops look like the following:

while (expr)
    statements
do statements
    while (expr)
for (expr1; expr2; expr3)
    statements

For the while loop, first expr is evaluated. If it is true, then statements are performed and expr is evaluated again as at the beginning of the loop. The statements are executed until expr is false. For the do-while loop, first the statements are executed and then expr is evaluated.

In *AIDA there are two types of a-pictures to define the while loop computation: one is to directly represent this control-flow construct in a visual form, and another is to represent it indirectly through a traversal process within a space data structure. The meaning of the indirect representation is: while (traversal process in the structure) do (statement).

The first type a-pictures are presented below:

  

and

  

These a-pictures are for defining the while constructs; after such an a-picture, a rhombus micro-icon with a conditional expression and a square micro-icon with corresponding statements are allocated. A specially colored vertical bar is used to show a beginning-end of the statements.

Within the body of computation, three algorithmic scenes are shown. They are related to operations on the observer node and on nodes of traversal schemes in 2-D structure with different masks. The red circles say that reading or writing operations are available in nodes where the traversal front is currently active. Examples of the masks are presented below:

The deep blue areas of icons show where computation (in a corresponding 2-D structure) has to be executed and the white areas show where computation has to be skipped. For example, the left icon says that computation has to be performed only in a top-left node of 2-D structure, and the right icon says that computation has to be performed in all nodes of the structure except nodes of the white area (values of parameters specifying the white area are declared with variable declarations). In a similar way, we can recognize that one of two icons in the row center defines computation in internal nodes and the other - in boundary nodes.

Another example shows how masks can be used for initializing different values of a variable on internal and boundary nodes of a 2-D structure.

 
 

To present such computation in conventional languages, the if and if-else constructs should be involved to take into account necessary limitations.

An example of the indirect representation of the while construct and a corresponding traversal scheme on a 2-D structure are presented below:

The a-picture says that while the top-down row-by-row traversal process in the 2-D structure, do operations specified for blue and red color nodes.

In this approach, highlighted nodes of the traversal process are applied (instead of conventional index expressions) to define structure positions where variables should be modified or read.

For the for loop, first expr1 is evaluated. The expr1 value is used to start the loop. Then expr2, that is usually a logical expression controlling the repetition, is calculated. If it is true, then statements (the loop body) are executed and expr3 is calculated. After that all operations, except the calculation of expr1, are repeated. The repetition continues until expr2 is false.

In *AIDA to define the n time iteration of a loop body, there is an a-picture similar to the while construct where the rhombus micro-icon includes the symbol of n.

In this example, the 400 time iteration of the body defined behind the black square micro-icon is presented. It shows that there is no necessity to declare an iteration variable and provide expressions for checking and modifying it.

A variety of icons has been introduced in *AIDA to define nested for loops. The following example shows how an *AIDA a-picture represents a nested for loop of the conventional style. This example also shows that there is no necessity to declare index variables and provide expressions for checking and modifying them.

This a-picture represents a traversal scheme in 2-D structure:

By attaching a formula to this a-picture, we can specify computation that in a conventional language requires something like two nested loops for representing the flows of computation from left-to-right and from right-to-left.

In fact, a-pictures can represent repetitive constructs requiring much more complex implementations in conventional languages. For example,

This a-picture represents a traversal scheme (in a graph structure) explained by the following set of tile pictures:

In this traversal scheme (repetitive construct) four formulas should be defined. For the shortest path problem they can be represented by the following rows:

To define it in C++, rows like the following should be provided.

_s = source;
 D[_s] = 0;
_kernel = where_nmin(D, _candidate);
D[_fringe] = min( D[_fringe], D[_kernel] + GR[_kernel][_fringe] );

Flow-of-control: break, switch, and nested if-else contruct

In conventional languages a general form of break constructs looks like the following:

for (expr1; expr2; expr3)
    statements                                              
    if (expr)                                                     
        break                                                         
    other statements  

It is used to interrupt the flow of control in for and while constructs, and defines an exit from inner-most enclosing loop.

In *AIDA to interrupt a repetitive construct based on a traversal scheme, a specially flashed (highlighted) operation has to be included for defining conditions of the interruption.

As for the switch and nested if-else constructs, they have the following general forms:

switch (val){
    case 1:
        statements-1;
        break;
    case 2:
        statements-2;
        break;
    case 3:
        statements-3;
        break;
    default:
        statements-d;
}
if (expr1)
    statements-1
else if (expr2)
    statements-2
else if (expr3)
    statements-3
...
else if (exprK)
    statements-K
else
    statements-d

The switch construct is based on integer variable val, which value defines the execution of corresponding case statements. The if-else construct is similar; it executes statements-N if exprN is true (all other statements are skipped). If all expressions are false, then only statements-d are performed.

In *AIDA to specify such type of the flow-of-control 1) on the level of algorithmic CyberFrames and CyberScenes, nesting the a-pictures of the first set (mentioned in sub-section 3.1) is applied; and 2) on the level of terminal formulas, many-nested if-else a-pictures of the second set (also above mentioned) and a switch a-picture (shown below) are used. The following examples illustrate *AIDA construct features.

The patterns of the constructs and supportive vertical bars simplify perception of the computation specified.

Functions, procedures and components

In conventional languages, a function is a named procedure executing pre-defined operations on one or more arguments (variables) and returning a calculated value as a result. There are standard functions that are embedded in the system environment and directly accessible on their names and declared functions that are defined by users and accessible from the program text or from special libraries. A procedure is similar to functions; it also obtains values of arguments, but returns results indirectly, through values of some or all arguments. A component (module) is an integrated entity combining data and associated operations. Though a library procedure can be an example of a component, the component concept is mainly related to reusability, independent development and robust composition of the integrated entities. In many cases, the components are "black boxes" with restrictive opportunities for adapting to new requirements. So, the object-oriented concept is involved to allow for inheriting some properties (data and operations) of existing types and adding new ones.

In *AIDA, the language a-characters, formulas and constructs, as well as its environment are well prepared to employ the best features of approaches above mentioned.

For example, in assignment statements, flexible style patterns are used to obtain compact formulas:

This pattern is considered as a symbol of expression where four sub-expressions should be attached. The green sub-expression defines a dot-product of A and V; the light-magenta sub-expression is just V; the yellow and light-brown sub-expressions define the average of V and sum V+1, respectively. Values of variables are taken from red contour-highlighted nodes.

In addition to standard functions of the following type,

there are new functions (procedures) demonstrated by examples below:

that define sorting operations, calculation of some differential operators, creating a "heap" and taking a value from the top of the "heap." Input/output operations are also supported by a-characters for whole operations and for their parts:

 
 

This example says that values of variable a associated with a 2-D structure are displayed on the computer monitor through a "value-to-color" function. The next example presents displaying values of u, v, and p on the monitor and recording values of p and (u, v) in some files:

 
 

A special form of integrated entities is related to algorithmic CyberScenes which can be reusable in many places of a CyberFilm. This form allows a variety of modifications for sizes of space data structures, traversal schemes on the structures, variables attached to the structure domains and their types and units of measure, as well as for operations involved on structure nodes. It is important to note that the modifications applied are controlled by the environment and visually examined by the users.

A CyberFilm as a composition of CyberScenes is also has a lot of opportunities for adapting to new requirements and algorithmic ideas. For including a function/procedure or a CyberFilm developed by the user, it should be saved in a library of the environment. After that, calls by name are available. The body developed in *AIDA is provided on user's demand as a special annotation.

 
 

To integrate existing components which are conventional "black boxes," there is an editable icon for declaring their names. In the above example, it presents a name of boundary_setting_1.

The standard form of invoking components can be used. However, a very important feature of the *AIDA is the component integration based on space structures and traversal schemes of activities within the structures. The space structures visually represent integrated entity shapes and the traversal schemes show partial orders of the component communication. To define the communication, send/receive operations with special triggering conditions are employed and visually demonstrated by token movements. In addition, operations on the sending data alignment for the space structure of receivers can be used. There is a library of the component integration types including master-workers, clients-server, communicating processes, and graph data-flow forms. In Main view of *AIDA program, special scene a-pictures are used to represent such forms. Names of components are involved to define operations (activities) within the scenes.

 
Information: Red text is used for presenting language super-characters and constructs which are still under the development and will be available later.