IBM
Contents Index Previous Next



Algorithms in SDL


A former problem in SDL is the lack of support for writing algorithms. For pure calculations, not involving communication, the graphical form for SDL tends to become ordinary flow charts, which is usually not a good way to describe advanced algorithms. Such, often large, parts of an SDL diagram also hide other, from the SDL point-of-view, more important parts of the diagram, namely the state machine and the communication aspects.

The algorithmic extensions described here addresses these problems by introducing the possibility to write algorithms in textual form within a Task symbol, and also to define procedures and operators in textual form in text symbols. There are two major advantages with this approach, compared to ordinary SDL:

In addition, the algorithmic extensions make it possible to now define procedures and operators in textual form in text symbols in SDL/GR.

These algorithmic extensions to SDL have been approved by ITU Study Group 10 to be incorporated into the official Master List of Changes that will affect the next ITU recommendation for SDL. There are a few minor differences in the support for SDL algorithms in the SDL Suite compared with the ITU definition - these are noted in the descriptions below.

The constructs that are part of the extensions are:

Compound Statement

The basic concept in the algorithmic extensions is the compound statement. A compound statement starts with a `{', which is followed by a sequence of variable declarations and a sequence of statements, and it then ends with a `}'.

A compound statement may be used in three places:

Note:

According to the ITU language definition the body of a procedure or operator is allowed to be a statement. In the SDL Suite, however, a compound statement is required. This means that if the body consists of only one statement, the enclosing "{ }" are required anyhow.

Note also that the enclosing "{ }" should not be included in a Task symbol in the SDL Editor. These braces will be added when the SDL system is converted to SDL/PR for analysis.

Example 39

Contents in Task symbol in SDL/GR:

a := b+1;
if (a>7) b := b+1;

Corresponding code in SDL/PR:

task {
  a := b+1;
  if (a>7) b := b+1;
};

Example 40

A procedure in a text symbol in SDL/GR, or in SDL/PR:

procedure p fpar i integer returns integer
{
  if (i>0)
    i := i+1;
  else
    i := i-1;
  return i;
}

Local Variables

Within a compound statement it is allowed to define a number of local variables. These variables will be created when the compound statement is entered and will be destroyed when the compound statement is left. The semantics of a compound statement is very much like a procedure without parameters, which is defined and called at the place of the compound statement.

A variable declaration within a compound statement looks that same as ordinary variable declarations, except that "exported" and "revealed" are not allowed. Example:

dcl
  a, b integer := 0,
  c    boolean;

Statements

A statement within a compound statement my be of any of the following types:

Note that each statement (and each variable declaration statement) ends with a `;'. The following statement types use the same syntax as in ordinary SDL/PR:

output, create, set, reset, export, return, call, assignment

Example 41 : Ordinary SDL/PR statements

output s1(7) to sender;
output s2(true, v1) via sr1;
create p2(11);
set(now+5, t);
reset(t);
export(v1);
return a+3;
call prd1(a, 10);
a := a+1;

Note:

According to the ITU language definition the keyword call in a procedure call is optional. In the SDL Suite it is, however, required.

If Statements

The structure of an if statement is:

if ( <Boolean expr> )
  <Statement>
else
  <Statement>

where the else part is optional. The Boolean expression is first calculated. If it has the value true, the first statement is executed, otherwise the else statement, if present, is executed.

Example 42

if (a>0)
  a := a+1;

if (a=0) {
  a := 100;
  b := b+1;
} else {
  a := a+1;
  b := 0;
}

If there are several possible if statements for an else path (the "dangling else" problem), the innermost if is always selected.

Example 43

if (a>0)
  if (b>0)
    a := a+1;
  else
    a := a-1;

means:

if (a>0) {
  if (b>0)
    a := a+1;
  else
    a := a-1;
}

Decision Statements

A decision statement has much in common with the ordinary decisions found in SDL, i.e. it is a multi-branch statement. The major differences between decision statements and ordinary statements is that all paths in a decision statement ends at the enddecision.

Example 44

decision (a) {
(1:10) : {call p(a); a := a-5;}
(<=0)  : a := a+5;
else   : a := a-5;
} 

The decision question and the decision answers follows the same syntax and semantics as in ordinary decisions. Following an answer there should be a statement, which might be a compound statement.

Loop Statements

A loop statement is used to repeat the execution of a statement (or usually a compound statement), a number of times. The loop is controlled by a loop variable, which either can be locally defined in the loop or defined somewhere outside of the loop.

The loop control part contains three fields:

Example 45

for (a := 1, a<10, a+1)
  sum := sum+a;

should be interpreted as (in C-like syntax):

a = 1;
while (a<10) {
  sum = sum+a;
  a = a+1;
}

Note the difference between SDL and C when it comes to the variable update. In C this is a statement, in SDL it is an expression to be assigned to the variable mentioned in the loop variable indicator.

In the loop variable indicator, either a new variable can be defined or a previously defined variable can be used. Example:

for (a := 1, ...
for (dcl a integer := 1, ...

Other possibilities in loop statements:

Label Statements

A label statement is just a label followed by a statement. These labels are only of interest if the statement following the label is a loop statement. The label name can be used in break statements (see below) to break out of a loop statement. Example:

L:
for (i:=0, i<10, i+1)
  sum := sum+a(i);

Note:

There are no "join" or "goto" statements allowed in the algorithmic extensions to SDL.

Jump Statements

Jump statements, i.e. break and continue, are used to change the execution flow within a loop.

A continue statement, which only may occur within a loop, is defined as: "skip the remaining part of the loop body and continue with updating the loop variable to its next value."

Example 46

for (a:=1, a<10, a+1) {
  if (sum > limit) continue;
  sum := sum+arr(a);
}

should be interpreted as (in C like syntax):

a = 1;
while (a<10) {
  if (sum > limit) goto cont;
  sum = sum + arr[a];
cont :
  a = a+1;
}

A break statement can be used to stop the execution of the loop and directly goto the statement after the loop.

Example 47

ok := false;
for (a:=1, a<10, a+1) {
  sum := sum+arr(a);
  if (sum > limit) break;
}
then
  ok := true;

should be interpreted as (in C like syntax):

ok = false;
a = 1;
while (a<10) {
  sum = sum + arr[a];
  if (sum > limit) goto brk;
  a = a+1;
}
ok = true;
brk:

A break statement breaks out of the innermost loop statement. By using labeled loop statements breaks out of outer loops can be achieved.

Example 48

L: for (x:=1, x<10, x+1) { 
     a := 0;
     for (y:=1, y<10, y+1) {
       a := a+y;
       if (call test(x,y)) break L;
     }
   }

The break statement in the inner loop breaks out from both loops as it mentions the label for the outer loop.

Empty Statements

It is allowed to have an empty statement, represented by just writing nothing. This is sometimes useful, for example as loop statement:

for (i:=1, Arr(i)/=0 and i<Limit, i+1) ;
  /* This loop sets i to the index of the first zero
     element in the Array Arr. */

Grammar for the Algorithmic Extensions

Meta grammar:

`dcl', `)', `;'	 are examples of terminal symbols.

<Stmt>, <Name>	 are examples of non-terminal symbols.

::=	 means defined as.

$	 means used for empty.

*	 means 0 or more occurencies.

+	 means 1 or more occurencies.

|	 means or.



Start of Grammar

<CompoundStmt> ::= 
   `{' <VarDefStmt>* <Stmt>* `}'

<VarDefStmt>   ::=
   `dcl'     <Name> (`,' <Name>)* <Sort> (`:=' <Expr> | $)
       ( `,' <Name> (`,' <Name>)* <Sort> (`:=' <Expr> | $) )*
   `;'

<Stmt>         ::=
   <CompoundStmt>      |
   <Outputx> `;'       |
   <CreateRequest> `;' |
   <Setx> `;'          |
   <Resetx> `;'        |
   <Export> `;'        |
   <Return> `;'        |
   <ProcedureCall> `;' |
   <IfStmt>            |
   <LabelStmt>         |
   <AssignmentStatement> `;' |
   <DeciStmt>          |
   <LoopStmt>          |
   <JumpStmt> `;'      |
   <EmptyStmt> `;'
 
<IfStmt>       ::=
   `if' `(' <Expr> `)' <Stmt> (`else' <Stmt> | $)

<DecisionStmt> ::=
   `decision' `(' <Expr> `)' `{'
   ( <Answer> <Stmt> )+
   ( `else'   <Stmt> | $)
   `}'
 
<Answer>       ::= same as answer in ordinary decisions
 
<LoopStmt>     ::=
   `for' `(' (<LoopClause> (`;' <LoopClause>)* | $) `)'
     <Stmt>
   (`then' <Stmt> | $)
 
<LoopClause>   ::=
   (<LoopVarInd> | $) `,' (<Expr> | $) `,' (<Expr> | $)
 
<LoopVarInd>   ::=
   `dcl' <Name> <Sort> `:=' <Expr> |
   <Identifier> (`:=' <Expr> | $)
 
<LabelStmt>    ::=
   <Label> <Stmt>
 
<JumpStmt>     ::=
   <Break> (<Name> / $) |
   <Continue>
 
<EmptyStmt>    ::=
   $

End of Grammar

Algorithms in SDL Simulator/SDL Explorer

The textual trace in the SDL Simulator and the SDL Explorer for the new algorithmic extensions will be according to the table below.

Statement Textual trace Comment

Compound



No trace

If

IF (true)

IF (false)


Decision

DECISION  Value: 7

Same trace as for ordinary decisions

Loop

LOOP variable b := 3

LOOP test TRUE

LOOP test FALSE

For loop variable assignments

For loop tests

Jump

CONTINUE

BREAK

BREAK LoopName


Empty



No trace

A compound statement without variables declarations is seen as just a sequence of statements, while a compound statement with variable declarations is seen as a procedure call of a procedure with no name, without parameters. However, no trace information is produced for this implicit procedure call or procedure return.

When it comes to variables, these are available in the simulator interface just in the same way as if compound statements where true procedures. That is, the commands Up and Down can be used to view variables in different scopes. Note that a variable defined in a loop variable indicator introduces a scope of its own.

There is one exception of this general treatment of variables in local scopes and that is procedures defined as a compound statement.

In this procedure:

procedure p
  fpar in/out a integer
{
  dcl b integer;
  ...
}

the parameter a and the variable b will be in the same scope, the procedure scope. For compound statements within the outermost procedure scope the general rules above apply.

Execution Performance in Applications

Cadvanced

All concepts in the algorithmic extensions have efficient C implementations, except variable declarations in local scopes (including in a loop variable indicator), as such compound statements will become SDL procedure calls.

Cmicro

All concepts in the algorithmic extensions have efficient C implementations. Compound statements containing variables are implemented using C block statements.


http://www.ibm.com/rational
Contents Index Previous Next