IMPERATIVE PROGRAMMING

Programming in the von Neumann architecture

"The computer has brought about a paradigm shift" (Gregory Chaitin).

---

The von Neumann Architecture
Concept

The von Neumann model basically consists of considering the machine as a sequence of memory cells in which the data and the program itself are stored. This model is inspired by the universal Turing machine [Turing, 1936].

In the early days of computing, programming a computer consisted of constructing a sequence of instructions in machine code. These instructions manipulated data contained in registers and memory cells, which were accessed by addresses. Since then, although languages have evolved, the "principles" of programming have remained the same:

• Memory cells are "assigned" values (data).
• The program dynamically changes the values of those memory cells.
• The program does not change during execution.

This machine model underlies even third-generation languages, which provide high-level abstraction machine access. These languages have two features, which carry over from the conception of first-generation languages:

1. They are imperative.
2. They are statement-oriented.

Since the beginning of computers, the von Neumann model has had a decisive influence. On the one hand, it has been the great driving force of computer development. On the other hand, it has conditioned the structure of programming languages, exerting a limiting influence, imposing a restricted conception of the nature of computation, based on implementational references, on the existence of a certain machine model.


Imperative languages

The imperative paradigm is statement or instruction-oriented, with structures for controlling the execution flow of a program. When the language also has a mechanism for constructing procedures and functions, it is also called Procedural Paradigm or Procedural. Examples of procedural languages are Pascal and C.

Classical imperative languages are based on three ideas:

1. Variables.
   Memory consists of a set of cells. Cells can be assigned symbolic names to store, update and retrieve information. A variable is an abstraction of the memory cell concept and has the attributes of:
   
   
   • Address (memory cell position).
     
     
   • Content (stored data).
     
     
   • Type (indicates the type of values that can be stored, the storage format, as well as, indirectly, the operations that can be performed to create, access and modify such values).
   
   
2. Assignment.
   Any calculated value must be stored in a given cell. This is done by an assignment statement, which is the abstraction of modifying the contents of a memory cell.
   
   A strange and unnatural form of allocation that is often used is, for example:
   
   
   x = x + 1
   
   To the left of the "=" sign we refer to the address of the variable x. To the right we refer to the content of x. This is not consistent, since consistency consists of maintaining semantics in a context-independent manner.
   
   Hehner [1978] observed that the classical assignment operator of the von Neumann model is intended backwards: that is, it is more logical to say "assign a name to an object" than "assign the value (object) to a memory location, i.e. indirectly to a name.
   
   
3. Repetition.
   A concept that applies exclusively to a sequence of statements for iterative execution.

Structured Programming
Generic Control Structures

The so-called "Structured Programming" [Dijkstra, 1976] allows to specify in a clear and orderly way the control of the execution flow of a program. It does not contemplate the "go to" statement [Dijkstra, 1968] for two reasons:

1. Because it is a low-level, implementing mechanism. In fact, the only two mechanisms for controlling the execution flow of a processor are sequencing and jumping.
   
   
2. Because it makes programs difficult to read and understand.

Structured Programming is based on only three generic control structures:

1. Sequence.
   This is the simplest mechanism. It is used to indicate that the program units (statements or blocks of statements) a₁ ... a_n will be executed in sequence, one after the other.
   
   
2. Exclusive selection.
   It is the selection of only one unit among a certain number of alternative program units. Given the units a₁ ... a_n, the unit a_i is selected (1 ≤ i ≤ n).
   
   
3. Iteration.
   It is the successive repetition (a certain number of times) of a program unit a. The number of times to be evaluated is set by a control variable or a condition.

By means of these three control structures it is possible to express the execution flow of any program [Böhm, 1966].

These three control structures have promoted a conceptual standardization of the flow control specification, due to their ease of understanding and application. In fact it is a humanization of the flow control specification [Dijkstra, 1965], along with a reduction of complexity.

Although there is general consensus on the use of these three structures, modern programming languages distort the "natural" semantics of Structured Programming, moving away from the desired formal standardization. This is due to the existence of different, even redundant, control structures.

In spite of the remarkable progress that this programming technique represented, two important limitations remain:

1. Programming languages offer only fixed and predetermined control structures. It is not possible to define control structures "tailored" to the needs.
   
   
2. Control structures are not generic. They can only be applied to source code. They cannot be applied to data.

Exclusive selection

The most common and well-known form of selection is by means of the IF-THEN-ELSE mechanism, which is fully supported and accepted by all imperative languages:

IF condition THEN
    a₁
ELSE
    a₂
END IF

The condition (true or false) is the result of the evaluation of a logical expression. And two blocks are distinguished: the IF block (associated with the true condition) and the ELSE block (associated with the false condition).

The ELSE block is optional. In this case the form is:

IF condition THEN
    a
END IF

Many programming languages support the CASE statement, which is a two-way generalization of IF-THEN-ELSE:

1. Any type of expression is usually supported, not just a logical expression.
   
   
2. The form is multi-path, i.e., there may be more than two alternatives.

The typical form is:

CASE expression
    valor1: a₁
    valor2: a₂
    ...
    valorn: a_n
ELSE
    a
END CASE

The ELSE block is also optional.

A more generic form would be to use n conditions:

CASE
    IF c₁ THEN a₁
    ...
    IF c_n THEN a_n
    ELSE a
END CASE

where the conditions are assumed to be mutually exclusive. If they are not, only the unit ai corresponding to the first condition ci that is met is executed.

Limitations and problems:

• It is not justified to use different control structures (IF-THEN-ELSE and CASE) for the same semantics, in this case selection of program units.
  
  
• It is not explicitly specified that what is being applied is an exclusive program unit selection mechanism. Only in some languages, such as PL/I, is the word SELECT explicitly specified:
  
  
  SELECT
      WHEN (c₁) a₁;
      ...
      WHEN (c_n) a_n;
      OTHERWISE a;
  END;
  
  
• The selection is type exclusive. It should be possible to select multiple program units (inclusive selection), as well as none or all.
  
  
• The IF-THEN-ELSE structure, from the point of view of form, has been criticized for its lack of symmetry. There is experimental evidence that fewer errors are made if the negative condition is re-specified. An alternative form could be the following:
  
  
  IF condition THEN
      a₁
  IF NOT condition THEN
      a₂
  END IF
  
  The second block could be called "IF NOT block", instead of ELSE block.
  
  With this form it is better emphasized that "IF block" or "IF NOT block" may not appear.
  
  
• The relationship between the logical expression and its value (V or F) is also not sufficiently highlighted. An alternative form would be:
  
  
  IF condition = V THEN
      a₁
  IF condition = F THEN
      a₂
  END IF
  
  in which the IF block and IF NOT block now appear even more homogeneously.

Iteration

Control structures for iteration (or loops) are traditionally of two categories:

1. Fixed number of iterations.
   The classical form is as follows:
   
   
   FOR v = v1 TO v2 STEP v3
       a
   END FOR
   
   The control variable v is of type integer and v1, v2 and v3 are integer expressions. STEP v3 is optional (by default, it assumes v3=1). The block a is called the "body" of the loop.
   
   
2. Variable number of iterations.
   Control is performed by evaluating a condition, which is specified at the beginning or end of the loop. The classical forms are:
   
   

   Condition up	Condition down
   WHILE condición     a END WHILE	REPEAT     a UNTIL condition

Limitations and issues:

• When you simply want to repeat a program unit a certain number of times, languages force the use of a variable, even if it is not used internally within that unit.
  
  
• Only one variable can be specified (since it is a control variable). It should be possible to specify several variables that take different values in each iteration. Only some languages provide the possibility of more than one variable.
  
  
• You can only specify a range of integer values (with optional increment). You should be able to specify any sequence of values, numeric or non-numeric.
  
  
• Variable number iterative control structures are usually designed so that the active loop can be exited (under evaluation). But there may be loops arranged in a hierarchical (nested) fashion. When this circumstance occurs, almost no language resolves in a completely satisfactory way to be able to leave any loop, the active one or another more external block. In addition, the loop exit usually occurs at the beginning or at the end. It should be possible to exit the loop at any point in the block.

Implementation in MENTAL
Classic IF-THEN-ELSE specification

The classic IF-THEN-ELSE form.

IF c THEN
    a1
ELSE
    a2
END IF

is specified by the full conditional form:

(a1 ← c →' a2) or
(a2 ←' c → a1)

In both cases, if the condition c is satisfied, a1 is evaluated. If it is not satisfied, a2 is evaluated. If there is no ELSE block, it is sufficient to specify (a1 ← c) or (c → a1). If c is satisfied, a1 is evaluated. Similarly, if only ELSE block (contrary condition) exists, (a2 ←' c) or (c →' a2) is specified.

Examples:

1. (a ← x>3 →' b) // if x>3, we get a. Otherwise, we have b
   
   
2. (a ← x>3) // if x>3, we have a.
   
   
3. (a ← (x>3 ∧ x<10) →' b) // If x>3 and x<10, we have a. Otherwise, we have b
   
   
4. (a ← (x>3 ∨ y>5) →' b) // If x>3 or y>5, we have a. Otherwise, we have b
   
   
5. (a ← (x=1 ∨ x=2 ∨ x=3) →' b) // If x is 1, 2 or 3, we have a. Otherwise, we have b

CASE specification

We will implement the following generic form:

CASE
    IF c1 THEN a1
    ...
    IF cn THEN an
END CASE

Specifies to evaluate ai if condition ci is met. The conditions c1, ... , cn can be exclusive or not.

In MENTAL can be specified in the following ways:

1. Sequential (inclusive selection).
   
   
   ((c1 → a1) (c2 → a2) ... (cn → an))
   
   All the ai corresponding to the conditions ci that are met are evaluated.
   
   
2. Hierarchical (exclusive selection).
   Nested full conditional expressions are used.
   
   
   • For two conditions:
     
     (a1 ← c1 →' (a2 ← c2 →' a3))
     
     
   • For three conditions:
     
     (a1 ← c1 →' (a2 ← c2 →' (a3 ← c3 →' a4))))
     
     
   • Etc.
   
   In this case, the conditions are evaluated in a descending hierarchical way, i.e., first c1 is evaluated; if it is not fulfilled, c2 is evaluated, and so on. In the end only one of the ai would be evaluated.
   
   For clarity, they can be specified on different lines and with relative offsets. For example, for three conditions:
   
   (a1 ← c1 →'
    (a2 ← c2 →'
        (a3 ← c3 →' a4)
   )
)
   
   The three-level hierarchical full conditional expression.
   
   
   (a1 ← c1 →' (a2 ← c2 →' (a3 ← c3 →' a4))))
   
   can be represented by
   
   
   (z1 (z2 (z2 (z3 a4)))
   
   being
   
   
   ⟨( zi = (ai ← ci →')↓ )⟩
   
   ie,
   
   
   (z1 (z2 (z2 (z3 a4)))/⟨( zi = (ai ← ci →')↓ )⟩
   
   In general, for n conditions,
   
   
   (⟨( (z1...zn a(n+1)))/á( zi = (ai ← ci →')↓ )⟩

Simple loop

To determine the structure associated with a loop, the best method is to start from the extensive (developed) form and successively compact it by identifying common expressions, to finally obtain a reduced expression, which is then generalized.

A simple example of structure would be the successive evaluation of the body a with the values 1, 3 and 5 of the variable x:

((((x = 1) a) ((x = 3) a) ((x = 5) a))
eq. ([((x = [1 3 5]) a)])

If we call (v = (1 3 5)↓) that is, the open sequence of values that runs through the variable x, we finally have the general expression:

([[(((x = [v])) a)]])

which we can express in parameterized form as follows:

⟨( loop(x v a) = ([(((x = v) a)]) )⟩

being;

x: Name of the control variable.
v: Sequence (open expression) of the values traversed by the variable x.
a: Loop body.

The classic simple loop

FOR v = v1 TO v2 STEP v3
    a
END FOR

would be specified as:

loop(v (v1 v1+v3 ... v2) a)


Bucles jerarquizados

These are nested or higher-order loops where for each variable value of a one-level loop, all the values of the rest of the variables corresponding to the lower levels are traversed. Let us now analyze the following forms:

Levels	Loop
1	FOR x1 = v1     a1 END FOR
2	FOR x2 = v2     a2     FOR x1 = v1         a1     END FOR END FOR
3	FOR x3 = v3     a3     FOR x2 = v2         a2         FOR x1 = v1            a1         END FOR     END FOR END FOR

Where x₁, x₂, x₃, ... are the control variables, and v₁, v₂, v₃, ... are the sequences (open expressions) of values corresponding to those variables.

The one-level loop is:

loop(x1 v1 v1 a1)

The two-level loop is:

loop(x2 v2 (a2 loop(x1 v1 a1) b2))

The three-level loop is:

loop(x3 v3 (a3 loop(x2 v2 (a2 loop(x1 v1 a1) b2)) b3)))

In general, for n levels, we have a hyperloop, i.e., a structure of nested loops with varying number of levels:

⟨( hyperloop(x v a n) = loop(x1 v1 a1) ← n=1 →'
(a(n) hiperbucle(x(n− 1) v(n−1) a(n−1)) b(n))) )⟩

Example:

( (x1 = u) (x2 = v) (x3 = w) )

( x = (x1 x2 x2 x3) )

( (v1 = 1...10) (v2 = (1 2 3)↓) (v3 = (1 3 ... 10) )

( v = (v1 v2 v2 v3) )

(a1 = (. . . .) // body loop 1

(a2 = (. . . .) // body loop 2

(a3 = (. . . .) // body loop 3

hyperloop(x v a 3)

Finite repetition loops

These are loops in which the body a is evaluated a certain number n of times (fixed or variable). Their associated structure is:

a★n

where n is the number of times to evaluate the a body. In this case, no loop control variable is needed.


Bucles condicionales

These are those that use a condition to end a loop:

1. Loop with the condition above (the condition is evaluated at the beginning of each loop). Its classical form is:
   
   
   WHILE c
       a
   END WHILE
   
   In MENTAL:
   
   
   (loop = (c → (a loop))
   
   It can also be specified using keywords:
   
   
   ⟨( (WHILE c a END WHILE) = (loop = (c → (<[b>a loop)) )⟩
   
   
2. Loop with condition below (the condition is evaluated at the end of each loop). Its classical form is:
   
   
   REPEAT
       a
   UNTIL c
   
   In MENTAL:
   
   
   ( loop = (a (c → loop)) )
   
   It can also be specified using keywords:
   
   
   ⟨( (REPEAT a UNTIL c) = ( loop = (a (c → loop)) ) )⟩
   
   Alternative ways of specifying conditional loops are:
   
   

   Loop	Code
   WHILE	(b = ((←' c → a) b)!
   	( (¡ ←' c → a)★ )!
   REPEAT	(b = ((a ← c →' )!
   	( a (c →' ¡)★ )!

Advantages of MENTAL for control structure specification

• The same semantic primitives are used to define control structures, which are very simple to use.
  
  
• Control structures can be applied to all types of expressions.
  
  
• All kinds of control structures can be defined: combining the basic control structures.
  
  
• Generic (parameterized) control structures can be defined. They have the advantage of being reusable.
  
  
• Control structures with a variable number of levels (hyperloops) and even higher order hyperloops can be defined.

Procedures

A procedure is a program unit that performs a certain task. In a procedure you can define parameters, which can be: input, output and input/output.

When invoking a procedure, if a parameter is an output or input/output parameter, the parameter name must be specified. This is analogous to traditional imperative languages, where a distinction is made between content (value) and address of a variable. In MENTAL, the equivalent of address is the name of a variable.

Examples:

1. Ascending sorting of a sequence of numbers by the bubble method.
   
   The first component of the sequence is compared with each of the remaining components, swapping the components if they are not in ascending order. The same is done with the second component with respect to the rest (from the third onwards). And so on until the penultimate component is reached, which is compared with the last one. In this case there is only one parameter (the sequence), which is input/output.
   
   ⟨( clasif(s) = ((n = s#) // sequence length

[(i = [1...(n−1)]) // traverse the elements

[(j = [(i+1)...n]]) // traverse following

(((s\i) > s\j) → ((u = s\i) //switch

(((s\i) = s\j) (((s\i) = u)))
]
]
)
)⟩

(s = (36 5 17 12)) // example sequence.

classif( s ) // name is used as parameter

s // ev. (5 12 17 36) (sorted sequence)
   
   
2. Same procedure as above, but with two parameters: one input (s) and one output (t).
   
   ⟨( clasif(s t) = ((n = s#) // length of the sequence

(t = s) // copy input sequence

[(i = [1...(n−1)]) // traverse elements

[(j = [(i+1)n]) // traverse following

((t\i) > t\j) → ((u = t\i) //exchange

(((t\i) = t\j)(((t\j) = u))))
]
]
)
)⟩

(s = (36 5 17 12)) // example sequence.

classif(s t)

s // ev. (36 5 17 17 12)) (original sequence)

t // ev. (5 12 17 36) (sorted sequence)

One could have also defined classif(s) as a function: with s as input parameter and as output of the function the sorted sequence.

---

Bibliography

• Böhm, C.; Jacopini, G. Flow diagrams, Turing Machines and languages with only two formation rules. CACM, Vol. 9, No. 5, pp. 366−371, May 1966.
  
  
• Dijkstra, Edsgar W. Programming Considered as a Human Activity. Proc. 1965 IFIP Congress, North Holland Pub. Co., 1965.
  
  
• Dijkstra, Edsgar W. Go To statement considered harmful. Comms. ACM, vol. 11, no. 3, pp. 147−148, 1968.
  
  
• Dijkstra, Edsgar W. Structured Programming. Software Engineering Concepts and Techniques. J. Buxton et al., eds. Van Nostrand Reinhold, 1976.
  
  
• Dijkstra, Edsgar W. A Discipline of Programming. Prentice−Hall, 1976.
  
  
• Hehner, E.C.R. On Removing the Machine from the Language. Acta Informática 10:9 (1978), 229−243, 1978.
  
  
• Turing, Alan M. On Computable Numbers, with an Application to the Entscheidungsproblem. Poceedings of the London Mathematical Society 2 (42): 230−265, 1936. Disponible online.