# An axiomatic representation for on-line recognition of a two-dimensional programming language

Jacques Gros, Jean-Paul Maroy

► To cite this version:

Jacques Gros, Jean-Paul Maroy. An axiomatic representation for on-line recognition of a two-dimensional programming language. [Research Report] IRIA-RR-051, IRIA. 1974, pp.22. hal-04715987

HAL Id: hal-04715987

https://inria.hal.science/hal-04715987v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
IRIA
laboria

laboratoire de recherche
en informatique
et automatique

An axiomatic representation
for on-line recognition
of a two-dimensional
programming language

J.Gros,J.P.Maroy

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n° 51

Janvier 1974
# AN AXIOMATIC REPRESENTATION FOR ON-LINE RECOGNITION OF A TWO-DIMENSIONAL PROGRAMMING LANGUAGE

J. Gros, J.P. Maroy

## Résumé

Des relations topologiques et sémantiques entre les symboles d'entrée et la linéarisation automatique du langage.

Les terminaux interactifs bidimensionnels exigent des processus de reconnaissance évolués pour permettre un dialogue aussi naturel que possible. Le processus de reconnaissance travaille sur une représentation interne qui lui permet d'interpréter la signification des symboles d'entrée.

Cet article propose une nouvelle syntaxe pour un langage de programmation à deux dimensions qui facilite la programmation structurée. Il décrit la représentation axiomatique.

## Abstract

Conversational bidimensional inputs to computers need intelligent recognition processes to keep a "natural" external form for the user. The recognition process has to work on an abstract internal representation that allows it to infer the meaning of the input symbols.

This paper presents an application to a new syntax for a 2D programming language which facilitates structured programming. It describes an axiomatic representation of topological and semantic relations and the automatic linearization of the language.
# 1 - INTRODUCTION

Programming languages have evolved within the various constraints of computing machines. Their evolution has been characterised by an attempt to free the programmer from these constraints and offer him languages easier to use. Any new language is a compromise between code efficiency and ease of use. But if it is quite easy to define and test code efficiency it is more difficult to define what is actually meant by ease of use.

It appears now that a language should not only describe easily a sequence of actions necessary to solve a problem but should also help - or at least not hinder - the human solving process itself. The problem is then to study the methodology of programming and may be to propose drastic changes in programming languages for a score of reasons ranging from programm correctness to problem solving (Dijskra [1]).

One of the constraints which does not appear explicitly in these studies is the sequentiality of programming languages. It has only been discussed in researches on parallel processing, but researches have no -or little - influence yet on the form of programming languages. The real issue is more in the methodology of programming. In this last field proposals consist mainly in decomposition of programs into independent and meaningful units. This approach which can be felt as quite obvious has important consequences on the form of programming languages. The structures proposed now are quite simple : modular programming, action clusters, stepwise refinement (Naur [2], Wirth [3]). They all have a common point : they question the mere sequentiality of programming languages and propose two dimensional structures, mainly hierarchical structures.

More simply, we can observe the written marks of the work of programmers or usual corrections on programm listings. Without being real flowcharts they consist in small sequences of instructions often enclosed in boxes. These sequences, or clusters, are linked together by arrows indicating insertion in a sequence or control (subroutine like). The level of description may vary from one cluster to the other.
Typically enough, variable initialisations and arithmetic formulas are
not detailed although they often imply complicated sequences of code
and several loops.

The study presented here tries to give an answer to the problem
of transforming a two-dimensional symbolic language into usual
sequential programming language. It consists in two main parts : the
proposition of a new 2D "natural" syntax and a pattern recognition
process of analysis of this language.

## 2 - THE TWO DIMENSIONAL LANGUAGE

A few previous attempts have been made to study 2D languages
(ACM SIGPLAN - Symposium on two dimensional man-machine Communication,
University of California, Los Alamos, 1972 [4]). But their development
has been limited by their restrictions on the symbolisms they studied
(chemical formulas, mathematical expressions) which are seldom meaning-
ful by themselves and because they used very constraining geometrical
representations.

The first generalisation we make is to consider that all the signs
of the 2D language are of the same nature : symbolic signs that take
their meaning from their relative positions. With that definition there
is no difference in the processing of a summation sign in a mathematical
expression and a reserved word in a programming language.

Then the recognition process will work on a topological and temporal
representation of the language, the time relationships being given by
the sequence of the input primitives. This representation will then be
transformed into a semantic representation which will be translated
into the sequential language.

### 2.1. The 2D symbols

The signs introduced by the 2D language are the usual signs of the
programming language into which it will be translated plus a few new
signs which are mainly arithmetic signs :

$\Sigma, \Pi, \mathcal{S}$
The syntax presented by Anderson is based upon PL/1 as the corresponding sequential language.

Another proposition by Nassi and Schneiderman [6] is based upon structured programming. At first sight the scope is quite different. The 2D symbolism is not meant to be directly fed into the machine but to help programmers to write well structured programs. In their proposition Nassi and Schneiderman define blocks of instructions which they enclose into boxes. Iteration loops are represented by nesting the boxes one into the other and conditional statements are couples of adjacent boxes with a special triangular header (fig 3). There is of course no provision for go to statements. In our opinion it seems quite difficult to write a large program with this symbolism for the simple reason that the boxes will not fit on a single page, that you have to know the length of a sequence when you draw the boxes and that some provision for the linking of those boxes seem necessary.

All these propositions seem adequate to edit a program already written. But we would like in our proposition, to be able to write directly a program on a tablet without having a first draft of it on a paper. So we have to dismiss all partition of the plane which imply knowing in advance how many instructions an iteration or a conditional sequence will contain. All the segmentations into blocks are given by breaking vertical sequences, by braces drawn indifferently before or after the instructions they enclose, by goto arrows pointing anywhere in the sheet on which the programmer is working.

In the description of the syntax we give below we introduce a box which is a sign of the metalanguage, and which of course will not appear in the program. It indicates a spatial configuration which is described in the syntax.

## 2.4. Conditional assignment statements

The usual assignment statement holds here. The arithmetic expression on the right side of the assignment obeys the arithmetic 2D syntax mentioned earlier or the arithmetic syntax of the corresponding linear language.

`<variable> = <arithmetic expression>`
In the more general statement, one out of several arithmetic expressions can be selected according to the actual value of some boolean expression. The syntax can be described by :

<table><tr><td> Conditional assignment statement </td><td> ::= </td></tr><tr><td> &lt; variable &gt; = { assignments </td><td> </td></tr><tr><td> assignments </td><td> ::= </td></tr><tr><td> </td><td> &lt; assignment &gt; </td></tr><tr><td> </td><td> assignments </td></tr><tr><td> &lt; assignment &gt; </td><td> ::= </td></tr><tr><td> </td><td> &lt; arithmetic expression &gt; [ &lt; boolean expression &gt; ] </td></tr></table>

The conditional assignment statement allows multiple assignments which can be quite tedious with a usual language :

$$R = \begin{cases} 0 & [q = 0] \\ m+1 & [q < n] \\ m+1-n & \end{cases}$$

which gives in ALGOL - 60

``` ALGOL
if q=0 then R:=0
else if q < n then R := m+1
else R := m+1-n;
```

We can mention here the introduction of the left brace and the brackets as well as the box meta-sign which indicates the implicit UNDER relationship.
## 2.5. Iteration statements

The syntax of the iteration statement introduces the left brace and the iteration sets :

<figure><img src="image_2.png" /></figure>

fig. 4 describes with that syntax an algorithm for inverting a matrix in its own space by Gaussian elimination.

## 2.6. Conditional statements

<figure><img src="image_3.png" /></figure>

The otherwise statement can be omitted as shown in fig. 5 With this definition of the syntax the left brace has always a conditional meaning and the right brace an iteration meaning.

<footnote>note : due to an error in page count
page number 8 does not exist</footnote>
Finally we just mention the drawing of arrows from one point of the program to another. It clearly has the meaning of a goto statement but can be used to edit the program i.e. insert sequences of program into an already written text or link together separatly written parts of the program.

## 3 - ANALYSIS

The bidimensional syntax adopted tries to look as natural as possible but there lacks in its description an important factor which cannot be included in the syntax : the latitude in positioning the different units on the tablet. It is in the preprocessing of the data and in the representation used for the analysis that we have to allow this freedom of position.

A second important point depends on the input mode which can take two forms : a keyboard language or a tablet language [7] . The keyboard language is entered through an editing program which gives 2D formatting possibilities on an alphanumeric Cathode Ray Tube. The tablet language is entered directly through a graphic tablet. It needs of course a handwritten character recognition program. In both cases the input sequence is known and meaningful. It can be used to relax position requirements.

This information on the sequence of input signs is common to all real time devices and widely used. But it can be pointed out that it can also be memorized on off-line devices. If experiences show that the sequential information is useful for recognition, then it is quite easy to devise off-line recording graphic tablets or local conversationnal 2D editing programs on small computers to gather that form of data instead of digitizing already written documents.

In current 2D languages there is a syntactical analysis phase using relative positions of elementary features. Anderson [8] for example, in decoding mathematical expressions, encloses each sign into a rectangle and then computes the position of a pseudo center for this rectangle.
Then, relative positions of elementary features are given by the
relative positions of their centers. The position requirements are
quite strong even with the correction offered by the definition of the
pseudo center. The exponentiation has to be written carefully and the
form :

$$a^{b+c} = f$$

will not be recognized for example.

Here, in order to give some flexibility we use a preprocessing which
gives us topological relations which are already quite permissive, and
the analysis itself then adds some more freedom by semantic analysis.

We will first describe the topological and semantic relations used
in the analysis and then the axiomatic representation used by the recognition or linearization process.

### 3.1. The topological relations

The elementary features used at this first level are the syntactical
signs presented earlier. They include the vocabulary of the linear programming language we want to obtain plus the signs of the 2D language syntax.

The input consists in a triple of a character, a topological relation
between that character and the preceding one, and some data to be memorized.

$$I = \{ki, r_{i-1}, i, d(ki)\}$$

This data $d(ki)$ depends on the input character but consists at least
in the x and y coordinates of the character ki or some function of those
coordinates.

The topological relation consists in the combination of two terms.
One is given by a y-comparison : OVER, HOR, UNDER. The other by a x-comparison : RIGHT, VERT, LEFT. These topological relations are not memorized.
They are used to build the structure representing the program. They are transformed into semantical relations as they appear. This transformation will be studied in the next paragraph.
But one of these relations has a special status, an implicit semantic : the HOR * RIGHT relation. If the 2D syntax keeps some external similarity with the linear language it is supposed to extend, and if some instructions have the same form they dont need to be translated. Then instead of keeping each character as a syntactical feature the whole string of characters can be considered as a syntactical feature itself. In the syntax proposed all the current affectations obey that rule except the very simple transformations of subscripts into indices enclosed in parenthesis.

## 3.2. Semantic relations

The main semantic relation is the SUIT (follows) relation. It corresponds to the implicit sequence between statements of a usual language. It is mainly created whenever two successive units are linked by an UNDER * VERT topological relation.

This relation builds sequences of instructions and clearly enough the problem is to define various sequences and their organization into a program.

The sequence is broken each time the relation SUIT does not apply i.e. when

$$ \eta_{i-1,i} \neq \text{VERT} * \text{UNDER} $$

Then instead of a SUIT relation we create a ALORS (then) or FAIRE (do) or any other relation breaking the sequentiality.

On a conditional statement a ALORS relation is created between the IF statement being the last element of the sequence and the next statement that begins a new sequence. Then the next statements are linked by SUIT relations (fig. 6). This new sequence is added to the list of open sequences. The only elements that can be accessed during the processing are elements of sequences which appear in the list of open sequences. This list displays the nesting of the blocks of the program.

Any breaking of the sequence can close the open sequence. The next instruction written in the example of fig 6 can be an iteration instruction and its brace.
The brace itself is neutral i.e. it is only used as a data associated
with the iteration instruction and it yields the first and the last
instruction within the iteration loop. Let's suppose the first three
instructions of the IF sequence lie within the loop. Then the three
instructions are disconnected from their sequence and connected by à
FAIRE (do) and FIN (end) relation to the iteration instruction. This last
instruction now represents the whole sequence and takes all its links
with others instructions (fig. 7). The sequence is only accessible by
the iteration instruction and is taken from the list of open sequences.
The loop is now a closed semantic unit.

The brace of a IF relation or of a loop can be drawn either before
or after the writing of the corresponding instructions. When drawn before
or after the sequence itself it defines the beginning and the end of a
sequence. When drawn just after the last element of the sequence it is
redundant and acts just as a verification.

When a sequence is closed it is only accessible by its header which
may not itself be accessible if it is in another closed sequence. But since
corrections in already closed sequences are not unfrequent it is necessary
to have an updating mode. In that mode we need not only the syntactical
relations but also the topological relations. If those last relations are
not kept in memory we have to re-create them from the data d(ki) associated
to input ki. That data reflects at least the x,y position of the element.
This geometrical data and the semantic relationships place us in a simu-
lated real time environment by threading the graph of the relationships
from the beginning. The topological structure is thus recreated.

In fig. 8, 9 and 10 are given a program, the graphic representation
of its semantic graph and its linearisation. This last operation is quite
straightforward once the graph has been constructed.

### 3.3. The axiomatic description

The two representations described previously - topological and seman-
tical - are implemented in a relational data structure which allows dynamic
creation, retrieval and deletion of information. The basic element of this
structure is the triple of three items. But it can also work on doubles,
sets and strings [9].
The use of this associative language to represent temporal and topological relations and their transformation into semantic relations leads us to adopt a formalism we call axiomatic in the sense that it works on predicates (the relations of the first representation) that it transforms into other predicates (the relations of the second representation) by applying transformation rules or axioms which can be stated as a sets of predicates to be replaced [10].

Other models can be proposed for the resolution process. The figures shown earlier suggest a graph-theoretical representation. Then the problem would be of the identification of known subgraphs in the structure and their inter relations. These representations are used quite explicitly by WINSTON [11] and by PFALTZ [12] in the study of web grammars. But as we would like to work in real time and since our input sequence is quite meaningful, the axiomatic representation allows us some form of local treatment and does not need important scanning of the structure.

The input consists of a primitive feature, a topological relationship and some data.

$$I = \{ ki, i-1, i, d(ki) \}$$

With the preprocessing mentioned earlier ki is a meaningful semantic unit. The analysis of the input string of fig. 6 creates the subsequent relationships :

`<k₂, SUIT, k₁>` , `<k₃, SUIT, k₂>`

`<k₄, ALORS, k₃>`

`<k₅, SUIT, k₄>` , `<k₆, SUIT, k₅>` , `<k₇, SUIT, k₆>`

Then the new sequence is broken (fig. 7) by the drawing of the brace and an iteration instruction. The brace is a part of the iteration instruction and can be drawn before or after this instruction. It associates to it two y-values that give FIRST and LAST instructions in the field of the iteration loop. Here FIRST is k₄ and LAST is k₆. This determination is made by scanning the list of open sequences and comparing y-values of the brace with y-values from the d(ki) stored. In that sense the representation is not purely axiomatic and some times recall geometric data. The axiomatic description takes only into account the data most often used for the treatment.
The treatment of the loop consists in disconnecting all relations coming on FIRST and leaving LAST and connecting them to the iteration instruction, and then in connecting FIRST and LAST also to the iteration instruction by FAIRE (do) and FIN (end) relations. This is done by the following set of actions :

loop ($k_8$) $\Rightarrow$
Add <FIRST, FAIRE, $k_8$>
Add < $k_8$ , FIN , LAST >

for X and Y such that <FIRST, X , Y>
delete <FIRST, X , Y>
Add < $k_8$ , X , Y> ;

for X and Y such that < X , Y , LAST >
delete < X , Y , LAST >
Add < X , Y , $k_8$ > ;

In the present case the graph of fig. 7 will be produced and it will
be represented by the two sets of predicates :

α : < k₂ , SUIT, k₁> , < k₃ , SUIT, k₂ > , < k₈ , ALORS, k₃> , < k₇ , SUIT, k₈>

β : < k₄ , FAIRE, k₈> , < k₅ , SUIT, k₄ > , < k₆ , SUIT, k₅> , < k₈ , FIN, k₆>

The sequence β is inside a semantical unit. It can only be accessed
through its header k<sub>8</sub> which belongs to the active list α. Various lists
like α,β can be opened during the analysis. They reflect the block struc-
ture of the language.

After that operation the linearization is quite straightforward
The structure is scanned, beginning with the first instruction and then
translated term after term. The linearization in fact can be done step
by step each time a sequence is closed. But it has to be done in the
systematic way when in updating mode.
4 - CONCLUSION

We have described here a new proposition for a 2D syntax for a pro-
gramming language. We think that the problem is important for the develop-
ment of more intelligent input means for computers. It is important on two
levels. First to help computing languages to adopt a structure more appro-
priate to problem solving. Second to improve the recognition process which
is not "intelligent" enough, yet.

This recognition process is based on the idea that meaning can be
assigned to 2D input by using both syntax and semantics and that one
of the greatest difficulties is to find a good representation of the
problem. The structural representation proposed here and its processing
are general enough to be adapted to any sort of symbolic 2D graphic lan-
guages such as flowcharts, mathematical expressions or chemical structures.

ACKNOLEDGEMENT

We would like to thank the Professor J.C. Simon for his encouragement
and many useful conversations and criticisms.
REFERENCES

[1] Edsger W. DIJKSTRA - The Humble Programmer. CACM vol 15 n°10 (1972)

[2] Peter NAUR - Programming by actions clusters. BIT 9 (1969)

[3] Niklaus WIRTH - Program Development by Stepwise Refinement. CACM vol 14 n° 4 (1971)

[4] Symposium on Two-Dimensional Man - Machine Communication - University of California - Los Alamos Scientific Laboratory. SIGPLAN notices vol 7 n° 10 (1972)

[5] Robert H. ANDERSON - Programming on a Tablet : A proposal for a New Notation. in [4] (1972).

[6] I. NASSI and B. SCHNEIDERMAN - Flowchart Techniques for structured Programming. SIGPLAN Notices August (1973)

[7] Mark B. WELLS - A Review of Two-Dimensional Programming Languages. in [4] (1972)

[8] Robert H. ANDERSON - Syntax-Directed Recognition of Hand-Printed Two-Dimensional Mathematics. Ph D Thesis Harvard University (1968)

[9] Pierre BOULLIER, Pierre JANCENE - LAMBDA : Langage pour la Manipulation d'une Base de Données Associative - Rapport Laboria n° 25 (1973)

[10] Laurent SIKLOSSY and J. DREUSSI - An Efficient Robot Planner Which Generates its own Procedures - Proceedings of the 3rd Int. Joint Conference on Artificial Intelligence - Stanford (1973).

[11] Patrick H. WINSTON - Learning Structural Descriptions from Examples. Ph D thesis MIT Artificial Intelligence Laboratory (1970)

[12] John L. PFALTZ - Web Grammars and Picture Description - Computer Graphics and Image Processing n° 1 (1972)
<figure><img src="image_4.png" /><figcaption>fig.1 An 2D Arithmetic expression</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>fig.2 Anderson : tablet notation for
a 2D programming language</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>fig.3 Nassi and Schneiderman : Proposition for
a 2D notation for structured programming</figcaption></figure>
$$
\begin{array}{l}
D = A_{kk} \\
A_{kk} = 1 \\
A_{kj} = \frac{A_{kj}}{D} \quad \{ j \to 1, \dots, n \} \\
D = A_{ik} \\
A_{ik} = 0 \\
A_{ij} = A_{ij} - D \cdot A_{kj} \quad \{ j \to 1, \dots, n \}
\end{array}
\quad
\left\{
\begin{array}{l}
k \to 1, \dots, n \\
\\
i \to 1, \dots, k-1, k+1, \dots, n
\end{array}
\right.
$$

<caption>Fig. 4 - Matrix Inversion by Gaussian Elimination</caption>

$$
\begin{array}{ll}
\text{IF } A=0 & \left\{ \begin{array}{l} R = -\frac{C}{B} \\ \text{OUTPUT } R \end{array} \right. \\[1.5em]
\text{OTHERWISE} & \left\{ \begin{array}{l} D = B^2 - 4.A.C \\ \text{IF } D \neq 0 \quad \left\{ \begin{array}{l} R = -\frac{B}{2.A} \\ \text{OUTPUT } R \end{array} \right. \\ \text{OTHERWISE} \quad \left\{ \begin{array}{l} \text{IF } D > 0 \quad \begin{array}{l} R_1 = \frac{-B + \sqrt{D}}{2.A} \\ R_2 = \frac{-B - \sqrt{D}}{2.A} \end{array} \\ \text{OUTPUT } R_1, R_2 \end{array} \right. \end{array}
\end{array}
$$

<caption>Fig. 5 - Solution of $Ax^2 + Bx + C = 0$</caption>
<figure><img src="image_7.png" /><figcaption>Fig. 6 - Conditional block</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 7 - Iteration block</figcaption></figure>
<figure><img src="image_9.png" /><figcaption>Fig. 8 - Input script</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 9 - Final Semantic Structure</figcaption></figure>
'DEBUT'
'POUR' k → 1, ..., n-1 'FAIRE'
'DEBUT'
m=k+1 ;
'SI' A(k,k) = O 'ALORS'
'DEBUT'
'POUR' j → k, ..., n 'FAIRE'
'DEBUT'
R=A(k,j) ;
A(k,j) = A(m,j) ;
A(m,j) = R ;
'FIN'
R=B(k) ;
B(k) = B(m) ;
B(m) = R ;
'FIN'
'POUR' i → k+1, ..., n 'FAIRE'
'DEBUT'
R=A(i,k)/A(k,k) ;
'POUR' ℓ → k+1, ..., n 'FAIRE'
'DEBUT'
A(i,ℓ)=A(i,ℓ)-R.A(k,ℓ) ;
'FIN'
B(i)=B(i)-R.B(k) ;
'FIN'
'FIN'
X=B(n)/A(n,n) ;
'FIN'

<caption>Fig. 10 - Final string generated : The linear programming language is an ALGOL like language</caption>