RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

ARCHIVES

A structure oriented
program editor :
a first step towards
computer assisted programming

V.Donzeau-Gouge, G.Huet,
Bernard
G.Kahn, B.Lang, JJ.Lévy.

Rapport de Recherche n° 114.

Avril 1975
A STRUCTURE-ORIENTED PROGRAM EDITOR:
A FIRST STEP TOWARDS COMPUTER ASSISTED PROGRAMMING

V. Donzeau-Gouge, G. Huet, G. Kahn, B. Lang, JJ. Lévy

Abstract

This paper describes a text-editor specialized in editing program texts. The design of the editor makes it a first step in a more ambitious project, the building of a better programming environment.

Résumé

Cet article décrit un éditeur de texte spécialisé dans l'édition des textes de programmes. Par sa conception, cet éditeur n'est en fait que la première étape d'un projet plus ambitieux : construire un environnement de programmation mieux adapté aux besoins du programmeur. •
A STRUCTURE-ORIENTED PROGRAM EDITOR :

A FIRST STEP TOWARDS COMPUTER ASSISTED PROGRAMMING.

V. Donzeau-Gouge G. Huet G. Kahn$^{(+)}$ B. Lang J.J. Lévy

IRIA-LABORIA

Domaine de Voluceau
78150 ROCQUENCOURT
FRANCE.

This paper describes a text-editor specialized in editing program texts. The design of the editor makes it a first step in a more ambitious project, the building of a better programming environment.

## INTRODUCTION

The research described in this paper is carried out as the first step in the direction of building a programming environment. Tradition equates the improvement of programming with the building of new and more powerful translators. To provide a programming environment means to integrate within a single conceptual framework and within a single programming system various activities of the programmer, such as : building, documenting, modifying a program text, executing and debugging (symbolically) the program, evaluating and improving the program performances, storing, retrieving and deducing facts about programs. While usually most of these tasks are performed manually, a good deal of them can benefit from the assistance of the computer. Actually the computer should be thought of as permanently looking over the shoulder of the programmer to check the logical consistency of his requests, facilitating his many clerical tasks and giving him a hand here and there on less trivial matters.

The first and foremost technical issue in carrying out this research is to understand how one can provide the system with the ability to manipulate conveniently its basic objects, programs. How this should be done may now be ascertained with a good degree of confidence -a non negligible result of the last ten years of research in Theory of Computation.

The possibilities and shortcomings of any method of program manipulation are immediately brought to light in the building of a *program editor* -a text editor aware of its handling highly struc-tured texts (programs) rather than strings of characters. In a program editor, manipulations of the program text are performed under direct control of the programmer. Their effects can be immediately displayed. Building such an editor involves many of the design decisions needed for the construction of the derived programming

environment and allows rapid checking of their satisfactory implementation. Hence it seems to be a rather logical and well-defined first step for a fairly broad range of research.

## DESIGN OF THE PROGRAM EDITOR

All time-sharing systems provide their users with the possibility of building and modifying files, an activity called text editing. A good survey of the features of available text editors is given by Van Dam [10]. The possibilities (and performances) of each text editor depend very heavily on the data structures used to represent files. Roughly speaking, most text editors conceive of the edited text as a list of lines, each line being in turn thought of as a list of characters. No difference is made between editing a program, editing numerical data or editing a business letter. Exceptions to this philosophy are the Interlisp Editor [9] and Emily [2]. The editor we describe in this paper is a direct spiritual descendent of theirs, even though it bears significant differences with both of them. The salient common point is that concrete programs are manipulated as if they were abstract objects, their *abstract representation*. In turn this representation is coded within the machine as a data structure, the *internal representation*. Operations on the internal representation are performed that give the feeling to the user that he is actually manipulating the abstract representation of the program.

### 1. *Abstract representation of programs.*

The abstract objects representing programs are labeled trees, usually called operator-operand trees. The *nodes* of the trees, the *operators* are of two kinds :

- *operators of fixed arity*, with a given number of descendants (E.g. `':=」`, `'if-then-else'`, etc...)

<footnote>(+) Compagnie Internationale des Services en Informatique, 35 bd Brune Paris France.</footnote>
A STRUCTURE-ORIENTED PROGRAM EDITOR:

-varadic operators, with an arbitrary number of descendants (E.g. : '...' , '....',')

corresponding to associative binary operators.

In the case of Pascal, we tried to follow simple principles :

The abstract syntax matches closely the intuitive idea of the languages structure. The formal description in Appendix 3 is a reference.

The leaves of trees are primitive energies called G. Kahoot & users manually atoms. (eg. I, J etc...)

A special atom, Λ, is used to denote the empty tree.

A set of rules, the abstract syntax, described by LABORIA, mark (except very rarely).

the well-formed trees. As an example, an abstract tree of Pascal is used with different meanings in syntax for PASCAL is shown in Appendix 3. 78150 ROCQUEN (Pascal) is used with different contexts, it corresponds to distinct operators in the abstract syntax.

Valid programs are texts written according to concrete syntax. From a well-formed tree, valid program may be obtained by a tree-to-string transformation called unparsing.

A certain degree of freedom is left in choosing a particular abstract syntax. For example, consider the following portion of PASCAL: program P, the research described in this paper is carried out. At the first step the direction of building programming environment. Tradition equates the improvement of programming with the building of new, and more powerful translators. To provide a WRITE(amt) environment means to integrate with a single conceptual framework and within a single programming system various The chosen abstract representation of P is the tree, below, modifying a program text, executing and debugging (symbolically) the program, evaluating and improving program performances, storing, retrieving and deducing facts about programs. While usually most of these tasks are performed manually, a good deal of them can benefit from the assistance of the computer. Actually the computer should be thought of as permanently looking over the shoulder of the programmer to check the logical consistency of his request, facilitating his many clerical tasks and giving him a hand, here and there on less trivial matters.

The first and foremost technical issue in carrying out this research is to WRITE how... one can provide the system with the ability to manipulate conveniently its basic objects, programs. How this should be done may now be ascertained with a good degree of confidence -a non negligible result of the last ten years of research in Theory of Computation.

<caption>Fig. 1.</caption>

The possibilities and shortcomings of any method of program manipulation are immediately brought to light in the building of a program editor -a text editor aware of its handling highly struc- The text editor, with but 20 nodes, are of fixed arity. The second one, of if-then-else stands for if-then-else statements and the second one (apply) stands for apply if and only if. Note that if this then help modify it has been decided here to use a single operator. For both the else and if-then-else. This choice may seem unreasonable but arbitrary. But it will make some program modifications easier. This example tends to show that caution should be exercised in the design of the abstract syntax.

- No operator of fixed arity has more than three sons.

- When unparsing, all nodes leave a concrete

mark (except very rarely). We do not elaborate further on the well-structured tree, below, modifying a program text, executing and debugging (symbolically) the program, evaluating and improving program performances, storing, retrieving and deducing facts about programs. While usually most of these tasks are performed manually, a good deal of them can benefit from the assistance of the computer. Actually the computer should be thought of as permanently looking over the shoulder of the programmer to check the logical consistency of his request, facilitating his many clerical tasks and giving him a hand, here and there on less trivial matters.

All 2 structural addresses provide their users with the possibility of building and modifying a notation that is to be devised not to designate subcomponents of a given program. The expressions identifying such trees will be called structural addresses. Letters u, text, red, state, and state mean, respectively, up, left, right, and down. If refers to the position of a program P, then & refers to the first second the condition A = u2+* of ands, e.g. the second one, the else - e.g. the third part. character is this subtrees. Now e refers to the else-else part, EU2 and EU3 are synonymous. e.g. EU2 is the second statement, p is that of the true part. Finally, the symbol allows editorialism. Even much as possible we use denotations that appear if the program containing a subcendent of theirs, even though it bears significant differences with both of them. The salient common point is that concrete programs are manipulated as if they were abstract objects, their abstract representation. In turn this representation is coded within the machine and the syntax and meaning of the notation are the same. Operations on the internal representation are performed by the user of the editor. It is able to use these structural addresses as such. A certain amount of syntactic sugaring will be provided as a means for it to become apparent. For example, if I denotes a subtree with top node if-then-else, I1, condition will mean but if it starts with a repeat node, U, condition will mean U2. The abstract objects representing programs are labeled trees, usually called operator-operand trees. Construction of the abstract representation of two kinds :

In sharp contrast with Hansen, or Hoffman [4] we wish to show fixed and flexible handling programs because we can build 'under if-then-else' where we must accept any file of characters as input and construct the corresponding abstract representation. Almost any parsing

<figure><img src="image_1.png" /></figure>
technique for the input language may be adapted to generate the abstract representation rather than code, and indeed it is an easier task. Two features of the constructor need to be emphasized :

### 3.1. Absence of type checking.

Obviously the constructor shall not make much sense of a vastly incorrect program. It is desirable however to try and build as much abstract representation as possible. One way to achieve this is not to require variables to be declared. Since declarations might be missing, no type checking can be performed. The constructor cannot rely on type information to analyze the input text. A separate process will later on check programs for validity of declarations, consistency of types and observance of scope rules. Aside from allowing to build a manipulable data structure for many more input texts, this approach has several advantages :

- Assume presence of declarations and well-typedness were to be ascertained at all times in the abstract representation. Minor modifications of a program such as removal of a declaration might have remote consequences, a well-known phenomenon in so-called "incremental compiling".

- Scope rules, type coercions, rules for the use of identifiers, etc... differ widely from one language to another. Suppose one wants to rebuild the program editor around a different language. To have syntax analysis and strict obedience to these name-rules as distinct computations rather than as coroutines will be useful.

- When building a program text for example in a topdown fashion, one often wishes to leave identifiers in place of program parts to be specified later. Usually the programmer is prevented from this rather natural practice by (an avalanche of) error messages from the compiler.

- The process that performs type-checking, declarations updating etc.. may be made more convenient than usual, for example in providing cross reference tables or displaying a different concrete representation of the program where declaration and use of names is emphasized.

- Finally the constructor will be more efficient.

### 3.2. Analysing subparts of a text.

The constructor is not only used for building the representation of an entire program. It is invoked whenever the user types in text to modify his file. However this calling of the constructor is goal-directed : the commands for insertion or replacement look up in the abstract representation and discover what syntactic category is to be expected.

### 4. Search by content.

When editing programs, a request such as : 'find all occurrences of identifier A in the procedure

P' is intuitively useful. Standard text editors provide a pattern matching facility that enables to find all occurrences of character 'A'. A general tree-matching routine will be available to the editor's users. Most associative searches however are expected to be very simple-merely looking for occurrences of a node of the abstract representation. Furthermore experience with other text-editors indicates that using a fast terminal drastically reduces the number such requests : most of them are performed by the human eye.

### 5. Terminal.

We use the editor with a video-display (+). The display's physical characteristics have an influence on the overall design of the editor :

i) **Speed**. The transfer rate between the computer and the terminal is 2400 bds. Hence filling out the whole screen is not an exceeding-ly slow operation ; scanning a file is fast as well.

ii) **Size**. Unfortunately the screen is very small in comparison with what the human eye can comfortably span : 80 characters wide, 24 lines high. In general, the last three lines are used for diagnostics and commands so that the window through which one looks at the text is only 21 lines high.

<figure><img src="image_2.png" /><figcaption>Fig 2. Screen layout. When unparsing special care is required not to waste screen space.</figcaption></figure>

iii) **Character set**. Upper and lower case are available and made use of (reserved words are displayed in lower case).

iv) **Gadgets**. Any character on the screen can be displayed in one of four states : dim, blinking, inverted or normal. If it is used with parsimony, this facility is extremely useful to attract the user's attention or to focus it. In the way it is implemented, it is actually difficult to handle : markers in the display buffer delineate the portions of text which are to be displayed in a special manner. Unfortunately these markers take up a position on the screen, which makes it difficult to turn on or off a section of the screen without moving it around a little. These little markers are the source of many headaches for the unparser (or rather the unparser designer !).

v) **A small modification**. Obviously the idea of having a "window" over a portion of text should be retained, provided it can be rendered

<footnote>(+) Tektronix 4023.</footnote>
compatible with the syntax oriented structure of
the editor. But there is no reason why this window
should be able to go down and not up on the text.
Most terminals will not permit insertion or
deletion of lines to be initiated from the compu-
ter. A slight modification in our terminal's
hardware gives them this crucial facility.

## 6. Unparser

There are not **one** but **many** ways to visualize a
given abstract representation onto a physical
display. An editor should comprise several
**un parsers** which take abstract representation
onto concrete text. We describe one of them in
detail, possibly one whose usefulness is most
obvious : it builds back the source text (or an
approximation of it).

At any instant, the user is looking at the
abstract representation through a window, i.e.
is interested in a subtree V that is displayed
entirely on the screen, whenever possible.

<figure><img src="image_3.png" /><figcaption>Fig. 3. Current expression.</figcaption></figure>

The current expression, K is a (not necessarily
proper) subtree of V. Its parsing is shown in
inverted mode so that it stands bright on the
screen. All addressing is relative to K unless
otherwise explicitly stated. V plays the part of
the astronomer's sighting telescope that helps
focusing on what is really under scrutiny, here
K.

A programmer often does not want to see all the
details of his program, but is interested only
in its general structure. An integer $n$ called
the holophrasting depth is attached to V to
specify the level of detail required. Roughly
speaking, when the unparser meets a node at level
from the top of it displays a special symbol, an
holophrast$^{(+)}$ (...for a varyadic node, # other-
wise).

Actually expressions at level $n$ are not abbre-
viated, only control structures. Fig. 4 shows
the result of unparsing and holophrasting $Π$ of
fig.1. This abbreviation strategy is most
likely to evolve as experience with the editor
accumulates.

(+)

Terminology suggested by Hansen [2].

if # then # n = 1

if A = B+2*C then
begin
...
end
n = 2

if A = B+2*C then
begin
#;#;
end
n = 3

if A = B+2*C then
begin
I:=I+1;
J:=0;
WRITE(A,B,C)
end
n = 4

**Nota** : Expressions are not abbreviated.

<caption>Fig. 4. Holophrasting.</caption>

The unparser attempts to position source tokens
on the screen in a manner that will be systematic
and enhance legibility of the program. Difficul-
ties arise from the brevity of lines and small
number of lines available. These constraints are
actually in conflict. An efficient solution has
to be found, for the user should not be scared
away from changing his window on the program. Any
node of the abstract representation may be tagged
by a prefix or a postfix comment. Comments are
not displayed, but available on request. (Note
that the constructor has to decide what node a
comment refers to. Although occasional misunderstandings may occur, results seem reasonable.).

A special feature is provided for a rolling
effect. When V is a subtree starting with a list
node, it may be the case that the list is too
long to fit on the screen. In this case, while V
remains constant, a command allows to let appear
or disappear one (or more) list elements at the
top of the screen so as to make room for other
list elements. In this detoured way, rolling
doesn't appear anymore to be at odds with the
remainder of the editor's design.

## 7. Commands

Appendix 2 lists the commands available at this
point on the editor, with their intended meaning.
Since nothing particularly striking can be said
about them we shall not elaborate on the command
language. Suffice it to say that logical consistency
imposes for the commands to be first pared so as to build an abstract representation for
them, stored away and then interpreted. Further
advantages of this approach are fairly clear :

- possibility of editing the command file with the same structured editor.

- checking of the validity of commands before starting their execution.

- later possibility of compiling commands.

The ideal would be of course that commands be actually written in the same language as the one being edited (a feasible solution in POP2 and INTERLISP). But this cannot be expected to be possible with all languages one wishes to build editors for.

## 8. Evaluators

Programs computing on the abstract representation of programs are called *evaluators*. One of them is the standard unparser described in section 6. Development of other evaluators is foreseen as the logical sequel of our research effort. We outline the functions of some of the evaluators whose development is considered, in or order to highlight the broad range of applications of our approach.

1. Other unparsers. As it was pointed out earlier, one may wish other pictorial representations of the program text. For example one may wish to emphasize declarations and use of names and underplay everything else. Of course, declarations and types have to be checked. Suggestions as to where to put these declarations etc.. will be provided by the evaluator.

2. A special program is considered to deal with *comments*. Comments may be attached to any node of the abstract representation, added, updated etc. For the moment no particular structure has been assigned to comments, but the interest of more formalized and more structured comments is clear.

3. In particular, a special evaluator will request documentation and produce as a result structured comments. Typical question the documenter might ask in the manner of H. Mills [7] "what is the meaning of the parameters of this procedure ?". And then it will proceed in listing one by one the parameters with their type, requesting an answer for each one. Smarter questions such as : "why does this *while* loop terminate" may be judiciously asked if a *symbolic interpreter* is available.

4. An interpreter is another special kind of evaluator, which will make use of tables built by the type-checker.

5. A compiler starting from the abstract representation can also be thought of as a code-producing evaluator.

6. Optimization à la Darlington [1] i.e. by program schemata transforms requires using an abstract representation as input. To be able of visualizing what optimizations have actually

taken place will be of great advantage.

Further extensions are also considered in the areas of debugging, program proving and executing partially written programs.

## NOTES ON IMPLEMENTATION.

The initial version of the editor has been programmed in PASCAL, with PASCAL being the object language as well. The structure of the problem allows for a very logical decomposition of the programming task.

The editor is made of several "logical devices". Roughly speaking, a logical device (') has characteristics similar to a physical one : input ports, dials (variables which other devices are only allowed to read), functional keys (procedures that may be called by any user of the device) A desirable feature of physical devices, bells to warn the user that some malfunctions has occurred, is impossible to implement in PASCAL (return to a trap analysis procedure in the *calling* device when a trap occurs in the *called* device). PASCAL is not very well suited to this style of programming which requires for example the ability to beat the ALGOL scope rule by *hiding more names*. We give below a list of *some* of these logical devices :

1. **Pseudo-display.** Simulates a high level display; with commands such as : FLASH, HOME, TAB, UNTAB, NUMBER (write a number at the end of line) etc...

[3 instances of this device, with identical appearance, exist depending on the concrete terminal in use : display, line printer, teletype].

2. **Abstract representation constructor.** Input : text, output : data structure. Commands : any node category.

3. **Command constructor** : similar to 2 with different input language.

4. **Command interpreter**

5. **Abstract representation store.** The data structure which concretely implements the abstract representation is encapsulated within a logical device with forces all reading and updating to be performed through standard procedures.

6. **Table driven evaluators**

As an example, we show what logical devices are successively needed to interpret the following command :

3 I "J:=J+1" *carriage return*

This command requests the insertion of an instruction between the 3rd and 4th element of the current expression, presumably itself a list of instructions.

<footnote>(+)

Logical devices are simple versions of Hoare's monitors [3].</footnote>
The pseudo-display inputs this command after receiving the control signal *carriage return* and passes it on to the command constructor. The abstract version of the command is built and stored. Then, the command interpreter looks up in the abstract representation store to see what should be inserted at the requested address. With the reply that this place can hold an instruction, the constructor is called to build the abstract representation of J:=J+1. Upon receiving the constructor's answer, the store is requested to perform the insertion, the standard unparser reflects on the display the modification of the store if necessary. The command is then rolled down one line by the pseudo-display and reading of the next command is initiated.

## CONCLUSION

Implementation of the editor is still in progress at this time. Its practicality cannot yet be assessed conclusively. To the authors of this paper however, the work described above appears ever more clearly as a mandatory initial step towards a remote goal: the building on sound foundations of an integrated system endowed with understanding of the programmer's activity [11],[12].

## REFERENCES

[1] Darlington, J. "A semantic approach to Automatic program improvement", Ph.D. Thesis, University of Edinburgh, 1972.

[2] Hansen, W.J. "Creation of hierarchic text with a computer display" Ph.D. Thesis, Stanford University, 1971.

[3] Hoare, C.A.R. "Monitors: an operating system structuring concept" Comm. ACM, vol 17, n°10, Oct. 1974.

[4] Hoffman, H.J. "Programming by selection" in International Computing Symposium 1973, North-Holland 1974.

[5] Landin "Correspondance between Algol 60 and Church's lambda-notation" Part I, Comm. ACM vol 8, n°2, 1965.

[6] Lucas P., Walk K. "On the formal description of PL/7" Annual Review in Automatic Programming, vol 6, Part III, 1969. Pergamon Press. N.Y.

[7] Mills, H. "Syntax-directed documentation for PL 360" Comm. ACM, vol 13, n°4, April 1970.

[8] McCarthy, J. "Towards a mathematical science of computation" in Information Processing 1962 North Holland, Amsterdam, 1963.

[9] Teitelman, W. et al. INTERLISP Manual, Xerox Corporation, Palo Alto Research Center, 1974.

[10] Van Dam, A. and Rice, D.E. "On line text editing: a survey" Computing Surveys, vol 3, n°3, September 1971.

[11] Wegbreit, B. "The ECL programming system" Proceedings of FJCC, Nov. 1971, Afips Press, N.J.

[12] Winograd, T. "Breaking the complexity Barrier again" Sigplan Notices, vol 10, n°1, January 1975.

# APPENDIX 1

## Addressing mechanism

1. Variables are used as pointers in the program text.

1.1. Predefined pointers : K, V, @DUMP

1.2. User defined pointers : @<identifier>

2. Structural addresses are defined using a pointer as <base>

<structural address>::=<base> list-of<modifier>'s
<modifier>::=<direct modifier>
| <search modifier>

<direct modifier>::=U<number>
| L<number>
| R<number>
| S<number>

/*up*/
/*left*/
/*right*/
/*son*/

<search modifier>::=F<pattern>
| FF<pattern>

/*find in this
  subtree*/
/*find in a
  larger context*/

A <pattern> contains metavariables which may be
instantiated

<pattern>::= '<schema>' /*immediate pattern*/
| & /*enter pattern from
      terminal*/
| <base> /*pattern already stored*/

A <schema> is an abstract representation schema. Details on <schema> are not given here. The abbreviations for addresses are not given here either for lack of space.

# APPENDIX 2

Basic commands of the editor (sketchy description).

## 1. Manipulation of pointers.

1.1. <base> : <structural address>

Meaning. The right-hand side address is evaluated, and the left-hand side points from now on to this address.

## Special cases :

a) <base> is K--The current expression is changed. The new current expression on the screen is shown in inverted mode. If K moves out of the subtree designated by V, a diagnostic appears on the diagnostic line.

b) <base> is V--The view is changed on the display screen. The value of the holophrasting depth appears on the far right of the diagnostic line, together with the symbol# or... depending on the head node of the tree designated by V.

1.2. <base>#<number>--Assigns a value to the holophrasting depth of the tree designated by <base>.
1.3. W<`number>`--Rolls the view provided V designates a list.

1.4. Pointers are actually stacks. The three following instructions permit to memorize pointers :

`<base>PD` /*pushdown*/

`<base>PU` /*pushup*/

`<base>PT` /*transpose*/

## 2. Manipulation of abstract representation

2.1. `<base>` = `<pattern>`

Meaning: `create` an abstract representation for the pattern and have the `<base>` designate it.

2.2. `<structural address>` C `<pattern>`

Meaning: To change the subtree at `<structural address>`. The `<pattern>` should not contain metadata, and its head node should be in the proper node category.

2.3. `<structural address>` D [<`structural address`>]

Meaning: If only one `<structural address>` occurs, then :

1) if the address on the left designate the son of a fixed-arity node, replace by `Λ`; Update `@DUMP`.

2) if it designates a list element, `remove` from list and update `@DUMP`.

If two addresses are specified, both must point to list elements in the same list, the first one occurring first. The interval they denote is deleted, `@DUMP` is updated.

2.4. `<structural address>` X `<structural address>`.

Meaning: `Exchange` the designated subtrees (with copy). Their headnodes have to be of course in the proper node category.

2.5. `<base>` Z `<structural address>`

Meaning. To `build` a sublist `<base>` designates a list member, the structural address on the right must designate a further member of the same list. Then `<base>` is updated to designate the indicated sublist.

2.6. `<structural address>` I `<pattern>`

Meaning: insert `<pattern>` after the (list-element at) `<structural address>.<pattern>` must contain no metadata and its head node must be in the proper category.

Nota: J may be used to insert `before` the structural address.

2.7. `<structural address>` II `<base>`

Meaning: same as 2.6. except `<base>` designates a list of the same type which must be merged there.

Nota: JJ may be used to mean `before`.

3. Control. All of the above are `<commands>`. Several commands can be typed on the same line separated by semi-colons to form a command group.

3.1. `<command group>` `<number>`

Do the `<command group>`, `<number>` times. Symbol `*` may be used to mean as much as possible.

3.2. `? <command 1>`, `<command 2>.-

Do `<command 1>` if the previous command was a `SUCCESS`, else do `<command 2>`.

3.3. `! <command 1>`, `<command 2>`

Request validation from the user. Do `<command 1>` in the affirmative, `<command 2>` otherwise.

3.4. `$ +` /*Exit loop with `SUCCESS`*/

$ -$ /*Exit loop with `FAILURE`*/

Note. Multiple representation for numbers, standard abbreviations are not included. A macro definition facility is being devised and is not given here either.

# APPENDIX 3

## Abstract syntax of Pascal

1. Nullary nodes (generators)

IDENT /*identifier*/

INTCONS /*integer constant*/

REALCONS /*real constant*/

ALFACONS /*alfa constant*/

CHARCONS /*Character constant*/

NIL /*nil pointer*/

2. Node categories (phyla)

They are sets of nodes. Each node is identified with the *phylum* that contains him only.

param ={DECL, PROCPAR}

selector ={IDENT/,,const/,,FUNCPAR, VARPAR, CASERC, IDENT}

stat ={LABST, ASSIGN, PROCALL, BEGEND, IF, CASE, WHILE, REPEAT, FOR, WITH, GOTO, nil}

var ={IDENT, INDEX, DOT, UNREF}

const ={IDENT, ALFACONS, INTCONS, REALCONS, CHARCONS, NIL}

step ={UPSTEP, DWNSTEP}

factor ={BRACKETS, NOT, PARENS, FUNCALL}

const var

term ={MULT, DIV, INTDIV, MOD, AND, OR}

simplexp ={UPLUS, UMINUS, PLUS, MINUS, OR}

exp ={EQL, LSS, GTR, NEQ, LEQ, GEQ, IN}

simtype ={RANGE, SYMBT, IDENT}

type ={RECORD, SET, FILE, ARRAY, PACKED, REF, FIELD}

3. Varyadic nodes (associative operators)

They are lists of nodes of a given category separated by a given separator. Ex : exp/, denotes any node such as : which is unpar-

exp exp exp

sed as : #, #, #.

4. A procedure, function or program body is represented by a block, which is a node {LABEL, CONST, VAR, PROC, FUNCNT, BEGEND}/; Blocks are accessed and linked together through a *display data structure* whose detail is omitted.
<table>
  <thead>
    <tr>
      <th>Nodes</th>
      <th>Node cat. of son 1</th>
      <th>Node cat. of son 2</th>
      <th>Node cat. of son 3</th>
      <th>Unparsing</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>PROG</td>
      <td>IDENT</td>
      <td>IDENT/,</td>
      <td>-</td>
      <td>program # (...) If son 2 is empty,</td>
    </tr>
    <tr>
      <td>PROC</td>
      <td>IDENT</td>
      <td>param/;</td>
      <td>-</td>
      <td>procedure #(...) then the pair ()</td>
    </tr>
    <tr>
      <td>FUNCT</td>
      <td>IDENT</td>
      <td>param/;</td>
      <td>IDENT</td>
      <td>function #(...) : # is omitted</td>
    </tr>
    <tr>
      <td>LABEL</td>
      <td>INTCONS/,</td>
      <td>-</td>
      <td>-</td>
      <td>label ...</td>
    </tr>
    <tr>
      <td>CONST</td>
      <td>EQLC/;</td>
      <td>-</td>
      <td>-</td>
      <td>const ...</td>
    </tr>
    <tr>
      <td>TYPE</td>
      <td>EQLT/;</td>
      <td>-</td>
      <td>-</td>
      <td>type ...</td>
    </tr>
    <tr>
      <td>VAR</td>
      <td>DECL/;</td>
      <td>-</td>
      <td>-</td>
      <td>var ...</td>
    </tr>
    <tr>
      <td>DECL</td>
      <td>selector</td>
      <td>type</td>
      <td>-</td>
      <td>... : # or # : #</td>
    </tr>
    <tr>
      <td>PROCPAR</td>
      <td>IDENT/,</td>
      <td>-</td>
      <td>-</td>
      <td>procedure ...</td>
    </tr>
    <tr>
      <td>FUNCPAR</td>
      <td>IDENT/,</td>
      <td>-</td>
      <td>-</td>
      <td>function ...</td>
    </tr>
    <tr>
      <td>VARPAR</td>
      <td>IDENT/,</td>
      <td>-</td>
      <td>-</td>
      <td>var ...</td>
    </tr>
    <tr>
      <td>BEGEND</td>
      <td>stat/;</td>
      <td>-</td>
      <td>-</td>
      <td>begin ... end</td>
    </tr>
    <tr>
      <td>LABST</td>
      <td>INTCONS</td>
      <td>stat</td>
      <td>-</td>
      <td># : #</td>
    </tr>
    <tr>
      <td>ASSIGN</td>
      <td>var</td>
      <td>exp</td>
      <td>-</td>
      <td># := #</td>
    </tr>
    <tr>
      <td>PROCALL</td>
      <td>IDENT</td>
      <td>exp/,</td>
      <td>-</td>
      <td>...( ) or #</td>
    </tr>
    <tr>
      <td>IF</td>
      <td>exp</td>
      <td>stat</td>
      <td>stat</td>
      <td>if # then # else # if # then #</td>
    </tr>
    <tr>
      <td>CASEST</td>
      <td>exp</td>
      <td>COLON/;</td>
      <td>-</td>
      <td>case # of</td>
    </tr>
    <tr>
      <td>WHILE</td>
      <td>exp</td>
      <td>stat</td>
      <td>-</td>
      <td>while # do #</td>
    </tr>
    <tr>
      <td>REPEAT</td>
      <td>stat/;</td>
      <td>exp</td>
      <td>-</td>
      <td>repeat ... until #</td>
    </tr>
    <tr>
      <td>FOR</td>
      <td>IDENT</td>
      <td>step</td>
      <td>stat</td>
      <td>for # := # do #</td>
    </tr>
    <tr>
      <td>WITH</td>
      <td>var/,</td>
      <td>stat</td>
      <td>-</td>
      <td>with ... do #</td>
    </tr>
    <tr>
      <td>GOTO</td>
      <td>INTCONS</td>
      <td>-</td>
      <td>-</td>
      <td>goto #</td>
    </tr>
    <tr>
      <td>INDEX</td>
      <td>var</td>
      <td>exp/,</td>
      <td>-</td>
      <td>#[...]</td>
    </tr>
    <tr>
      <td>DOT</td>
      <td>var</td>
      <td>IDENT</td>
      <td>-</td>
      <td>.#</td>
    </tr>
    <tr>
      <td>UNREF</td>
      <td>var</td>
      <td>-</td>
      <td>-</td>
      <td>#↑</td>
    </tr>
    <tr>
      <td>BRACKETS</td>
      <td>exp/,</td>
      <td>-</td>
      <td>-</td>
      <td>[...]</td>
    </tr>
    <tr>
      <td>PARENS</td>
      <td>exp</td>
      <td>-</td>
      <td>-</td>
      <td>(#)</td>
    </tr>
    <tr>
      <td>FUNCALL</td>
      <td>IDENT</td>
      <td>exp/,</td>
      <td>-</td>
      <td>...( ) or #</td>
    </tr>
    <tr>
      <td>COLON</td>
      <td>const/,</td>
      <td>stat</td>
      <td>-</td>
      <td>... : #</td>
    </tr>
    <tr>
      <td>EQLC</td>
      <td>IDENT</td>
      <td>const</td>
      <td>-</td>
      <td># = #</td>
    </tr>
    <tr>
      <td>EQLT</td>
      <td>IDENT</td>
      <td>type</td>
      <td>-</td>
      <td># = #</td>
    </tr>
    <tr>
      <td>RECORD</td>
      <td>DECL/;</td>
      <td>-</td>
      <td>-</td>
      <td>record ... end</td>
    </tr>
    <tr>
      <td>SET</td>
      <td>simptype</td>
      <td>-</td>
      <td>-</td>
      <td>set of #</td>
    </tr>
    <tr>
      <td>FILE</td>
      <td>type</td>
      <td>-</td>
      <td>-</td>
      <td>file of #</td>
    </tr>
    <tr>
      <td>ARRAY</td>
      <td>simptype/,</td>
      <td>type</td>
      <td>-</td>
      <td>array [...] of #</td>
    </tr>
    <tr>
      <td>PACKED</td>
      <td>type</td>
      <td>-</td>
      <td>-</td>
      <td>packed #</td>
    </tr>
    <tr>
      <td>REF</td>
      <td>IDENT</td>
      <td>-</td>
      <td>-</td>
      <td>#↑</td>
    </tr>
    <tr>
      <td>RANGE</td>
      <td>const</td>
      <td>const</td>
      <td>-</td>
      <td># .. #</td>
    </tr>
    <tr>
      <td>SYMBT</td>
      <td>IDENT/,</td>
      <td>-</td>
      <td>-</td>
      <td>(...)</td>
    </tr>
    <tr>
      <td>CASERC</td>
      <td>DECL</td>
      <td>DECL/;</td>
      <td>-</td>
      <td>case # of ...</td>
    </tr>
    <tr>
      <td>FIELD</td>
      <td>DECL/;</td>
      <td>-</td>
      <td>-</td>
      <td>(...)</td>
    </tr>
    <tr>
      <td>NOT</td>
      <td>factor</td>
      <td>-</td>
      <td>-</td>
      <td>#↓</td>
    </tr>
    <tr>
      <td>UPLUS, UMINUS</td>
      <td>simplexp</td>
      <td>-</td>
      <td>-</td>
      <td>+# resp(-)</td>
    </tr>
    <tr>
      <td>PLUS, MINUS, OR</td>
      <td>term</td>
      <td>term</td>
      <td>-</td>
      <td># + # resp(-, v)</td>
    </tr>
    <tr>
      <td>MULT, DIV, MOD, AND, INTDIV</td>
      <td>factor</td>
      <td>factor</td>
      <td>-</td>
      <td># * # resp(/, mod, ^, div)</td>
    </tr>
    <tr>
      <td>EQL, LSS, GTR, IN, NEQ, LEQ, GEQ</td>
      <td>simplexp</td>
      <td>simplexp</td>
      <td>-</td>
      <td>#=# resp(<, >, #, ≤, ≥, in)</td>
    </tr>
    <tr>
      <td>UPSTEP, DWNSTEP</td>
      <td>exp</td>
      <td>exp</td>
      <td>-</td>
      <td># to # resp(downto)</td>
    </tr>
  </tbody>
</table>

5. Table of nodes with fixed arity greater than 0 (operators)