\chapter{A BRIEF INTRODUCTION TO ELAN-0}

Elan-0 is a small subset of Elan, which is intended for learning
systematic Top-Down programming. The best way to get acquainted
with  Elan and to appreciate the programming style it aims to
support is to start with the Elan-0 subset.

This chapter of the manual is intended for readers who already have
some experience in programming in an algorithmic language.
Notice that a careful distinction is made between
remarks which pertain to Elan as a whole and remarks confined
to the Elan-0 subset. In chapter 4 the syntax of the full language
(with the exception of packets) can be found, which is available
in the Elan Programming Environment.

\section{Some concepts of programming languages}

The following terminology and concepts are applicable to any
programming language, but in particular to Elan, since they lie
at the heart of its design. Readers not interested in philosophy
may skip this section.

\subsection{Entities}

A program is a text, viz. the formulation of some algorithm,
expressed in a programming language. This text obeys the syntax
of the programming language, and according to that syntax consists
of a nested collection of constructs. Among these constructs,
three general classes can be distinguished: {\em algorithms},
{\em objects} and {\em types}, which have the distinction that
they can be denoted by names. The program text consists of such
{\em entities}, glued together by control structures, data structures
and further composition mechanisms such as expressions and functional
application.

\subsection{Elementary and composed entities}

An entity which is denoted by a name we will term {\em elementary};
the others are {\em composed}. It may very well be that a composed
entity at one place of the program obtains a name, by means of
a {\em declaration}, and at other places of the program is denoted
by that name. Such a declaration serves as an abstraction mechanism.
Besides a shortening of the program, this naming of entities
allows the introduction of various {\em levels of abstraction}.

\subsection{Abstract and concrete entities}

Some elementary entities belong to the language and are available
without further effort by the programmer, with their specific
semantics. These we will term {\em concrete}. Others we will
term {\em abstract}: they are constructed by the programmer and
abstracted by means of a declaration. We might define programming
along these lines as the construction
of abstract algorithms.

\subsection{Composition mechanisms}

In the design of an algorithm a programmer should not try to
express it in all detail at once. Instead, the programmer should
split it into major parts which can be refined in a stepwise
fashion down to the elementary entities belonging to the programming
language. Algorithms are thus composed of other algorithms which
in their turn are either composed or elementary.

Particular composition mechanisms for the algorithms on the one
hand, and the objects and types on the other hand, are termed
{\em control structures} and {\em data structures}, respectively.

\subsection{Where does Elan fit in this taxonomy?}

Traditionally, composition mechanisms have been seen as the
central mechanisms in systematic (``structured'') programming.
Elan has rather conventional control structures and relatively
simple data structures. In contrast, in Elan the abstraction mechanisms
are seen as the central issue in any programming methodology
and consequently highly developed.

The Elan Programming Environment further stresses this view
by making the definition of abstract algorithms (refinements)
the basis for the development and manipulation of programs. It
considers a program as a collection of refinements, rather than
one text.

\section{The notation of algorithms}

\subsection{Names of algorithms}

Names are either the names of concrete algorithms, which means
that they are predefined in the Elan Interpreter, or they are
introduced by the programmer by the definition of abstract algorithms
using refinements. Here we explain their formation rules.

Names for abstract algorithms can be freely invented. Such a
name has the form of an {\em identifier}, consisting of a leading
(lower case) letter, followed by letters, digits, and possibly
embedded spaces. The latter serve to enhance the readability
of programs. In contrast to full Elan, such spaces in Elan-0
are considered significant and are part of the name. Some examples:

\begin{elan}
        find upper limit
        word occurs on this page
\end{elan}

\noindent
Names shall be chosen such that they express concisely {\em what}
is done by an algorithm, not
spelling out in detail {\em how} it is performed. Inventing suitable
names is a non-trivial task and needs experience which can be
gained only by the study of good examples, exercises, and by
the contemplation of programming problems.

\subsection{Control structures}

The first step towards a precise description of algorithms is
the use of a collection of stylistic patterns for connecting
together the algorithmic steps performed in the execution of
programs. These patterns are called {\em control structures}.
Elan-0 knows the following:

\begin{itemize}
\item sequence;
\item repetition;
\item choice.
\end{itemize}

\noindent
The forms available in Elan are also available in most other
programming languages. Elan uses a notation with keywords written
in upper case. They will be introduced by way of examples in
the next subchapters.

\subsubsection{Sequence}

The sequential execution of the steps of an algorithm is denoted
by placing a semicolon between them.

\begin{elan}
        read the current page ;
        turn page over ;
        read the current page
\end{elan}

\noindent
These are the names of three abstract algorithms to be executed
one after the other. The semicolon is a {\em separator} between
them (not a terminator), and can be read as ``and then''.

We call such a sequence a {\em paragraph}, and its constituents
{\em units}. The example paragraph above contains 3 such units
and its execution consists of the execution, in that order, of
the three units. In this way the {\em effect} of the paragraph
is the composition of the effects of its units. The {\em value}
of a paragraph (if any) is the value of its last unit.

\subsubsection{Repetition}

Repetition can be expressed in a number of ways. An important
paradigm of repetition is the while-loop, e.g.

\begin{elan}
        WHILE
          the word does not occur on this page
        REP
          look at the following page
        ENDREP
\end{elan}

\noindent
The {\em condition} between {\tt WHILE} and {\tt REP} is a unit
which, upon evaluation, yields a truth value (true or false).

The paragraph between the keywords {\tt REP} and {\tt ENDREP}
is executed only if the condition yields true. After the execution
of the paragraph (the ``loop-body'') the condition is evaluated
again, and accordingly the loop-body may be executed repeatedly.
The execution ends as soon as the condition upon evaluation yields
false. For those who prefer more readable keywords, {\tt REP}
may be also written as {\tt REPEAT}, and {\tt ENDREP} as {\tt ENDREPEAT}.

\pagebreak
\begin{elan}
        WHILE
          the sun is shining
        REP
          have a drink ;
          sing another song
        ENDREP
\end{elan}

\noindent
In this kind of repetition a test of applicability is performed
before each cycle (``pre-checked-loop''). If in this example
it is rainy, the loop-body is never executed, and you have to
stay sober.

For cases where there is always something to be done first, and
checked for repetition afterwards (``post-checked-loop'') Elan
has the following complementary repetitive construct:

\begin{elan}
        REP
          drink a glass of tea with rum ;
          sing a christmas carol
        UNTIL
          it stops snowing
        ENDREP
\end{elan}

\noindent
In this case the condition which stands between {\tt UNTIL} and
{\tt ENDREP} is executed after each execution of the first paragraph,
the repetition continues if the condition yields false and stops
if the condition yields true.

For cases where the number of repetitions is known in advance,
Elan offers a ``counting-loop'', also called for-loop.

\begin{elan}
        FOR i FROM min UPTO max
        REP
          tally i th entry
        ENDREP
\end{elan}

\noindent
The units {\tt min} and {\tt max} yielding integers are evaluated
once at the beginning of the for-loop. The controlled integer variable
{\tt i} gets the value of {\tt min}. As long as {\tt i} is less
or equal to {\tt max}, the loop-body between {\tt REP} and {\tt
ENDREP} is executed, followed by an increment of the ``loop-variable''
{\tt i} by one. Within the loop-body {\tt i} may be used, but
not assigned to. Its value is undefined after the execution of
the for-loop.

In case you want to count not upwards, but downwards from a larger
value to a smaller one, there is a variant of the counting-loop:

\begin{elan}
        FOR nr FROM stock DOWNTO minimum
        REP
          sell one
        ENDREP
\end{elan}
 
\noindent
In this variant, {\tt nr} is counted down from {\tt stock} to
{\tt minimum}. If {\tt stock} was already below {\tt minimum},
then the loop-body is not executed.

In case the value of the from-part is one and the controlled
variable is of no interest, the for- and from-parts may be left
out, leading to the shorter form

\pagebreak
\begin{elan}
        UPTO 20
        REP
          hit him over the head ;
          pick him up
        ENDREP
\end{elan}

\noindent
A later section will demonstrate the use of the counting-loop
in processing rows of data elements.

\subsubsection{Choice}

Choosing between two alternatives depending on a condition is
written in Elan as:

\begin{elan}
        IF condition
        THEN
          part for condition true
        ELSE
          part for condition false
        FI
\end{elan}

\noindent
If the condition evaluates to true, then the paragraph
between {\tt THEN} and {\tt ELSE} (the ``then-part'') is executed,
and the rest up to the {\tt FI} skipped. In the contrary case,
the then-part is skipped, and the paragraph between {\tt ELSE}
and {\tt FI} is executed (the ``else-part'').
The keyword {\tt FI} may also be spelled as {\tt ENDIF}.

This primary form of choice has two variations for common needs.
If there is nothing to do in the else-part, then the choice can
be simplified by leaving out the else-part:

\begin{elan}
        IF it looks like rain
        THEN
          take the umbrella with you
        FI
\end{elan}

\noindent
In case the weather is fine you do nothing ({\tt ELSE do nothing}
was omitted).
For decision cascades like

\begin{elan}
        IF condition 1
        THEN
          action 1
        ELSE
          IF condition 2
          THEN
            action 2
          ELSE
            IF
              ...
            FI
          FI
        FI
\end{elan}

\noindent
Elan offers another variant of the choice construction:

\begin{elan}
        IF condition 1
        THEN
          action 1
        ELIF condition 2
        THEN
          action 2
        ELIF
          ...
        ELSE
          action for all conditions above failing
        FI
\end{elan}

\noindent
Also in this case, an empty else-part may be omitted.

\subsubsection{Control structures yielding a value}

The execution of a paragraph or a choice can also {\em yield}
a value, namely that of the last unit executed. The paragraph

\begin{elan}
        compute sum of integers 1 to 10 ;
        that sum + 1
\end{elan}

\noindent
suggests that first the integers 1, 2, ... 10 are summed up,
resulting in a value of 55, and then the value 56 is yielded
by that paragraph. If the last unit of a paragraph yields a value,
then the paragraph as a whole yields that value.

In case of a choice, the value yielded is that of the paragraph
in the then-part or in the else-part, depending on the condition.
These values must have the same type. As an example, the unit

\begin{elan}
        IF a < b THEN a ELSE b FI
\end{elan}

\noindent
yields the smaller of the two integer values {\tt a} and {\tt b}.
Repetitions cannot yield a value.

\subsection{Refinement}

The most striking construct of Elan is the {\em refinement},
a simple mechanism for defining abstract algorithms which forms
the basis for the {\em Top-Down} programming style, which can be summarized:

\begin{quote}
   ``A program is developed by first giving a rough but potentially
   correct formulation composed of abstract entities. Thereupon
   each of these abstract entities is similarly defined, in terms
   of other abstract and concrete entities, until at last all
   necessary abstract entities have a suitable definition.''
\end{quote}

\noindent
A refinement gives a name to a paragraph, and looks like

\begin{elan}
        name: paragraph.
\end{elan}

\noindent
Executing the name of a refinement means executing its constituent
paragraph (its {\em body}). The value of the refinement is the
value of its body.

In distinction to procedures (which could also in principle be
used as refinements) refinements may appear in any order, and
may in particular appear after any invocation of the refinement.
Refinements can not have parameters, in order to keep the ``visual
overhead'' in their definition and application to a minimum.
A refinement does not form a separate scope of naming. Therefore
it is possible to put a declaration in one refinement and use
it in another. For these reasons, refinements are better suited
than procedures for capturing the ``fleeting abstractions'' in
programming.

In Elan-0, a program consists of one or more refinements, where
the first refinement is the {\em root} of the program. Such programs
correspond to procedure-bodies in full Elan.

\subsection{Leave-statement}

Elan has a special mechanism for terminating the execution of
a particular refinement, which looks like

\begin{elan}
        LEAVE refinement name
\end{elan}

\noindent
This mechanism can in particular be used to terminate repetitions
from the inside.

Although it looks much like the infamous goto-statement, the
leave-statement is very different: It does not allow arbitrary
continuation of program execution at some other part of the program
with all its known dangers, but completes the execution of an
algorithm. For this reason, you may name in a leave-statement
only a refinement of whose execution the execution of the leave-statement
is part.
It is even possible to leave a refinement with a value, by

\begin{elan}
        LEAVE refinement name WITH expression
\end{elan}

\noindent
This causes the refinement with that name to be left, yielding
the value of the expression.

\section{The notation of objects}

Algorithms to be executed on a computer do not work on thin
air, but need objects to operate on. In this chapter we describe
what kinds of objects are available in Elan-0, and what are the
basic algorithms to handle them.
Objects occur in programs in two forms:

\begin{itemize}
\item Elementary objects are variables and constants which come
into life by the execution of {\em declarations};
\item Composed objects are the {\em expressions}. Expressions
are a convenient notation for the computation of values. A
particular kind of expression are {\em denotations}, a way of
writing down values in the program text.
\end{itemize}

\subsection{Declaring objects}

In Elan all elementary objects must be declared. This declaration
may occur at any place in the program, provided there is only
one such place, and in executing the program the declaration
of an object precedes all its applications. Thus there is no
necessity to collect all declarations at the head of the program
but declarations can appear at the place where they are first
needed. A declaration may even occur within the body of a loop.

A declaration is a unit which introduces an elementary object
with four attributes:

\begin{itemize}
\item a type;
\item a name;
\item a value, which may be undefined; and
\item an access right.
\end{itemize}

\noindent
A declaration makes the name of the object known throughout the
whole Elan program.

\subsubsection{Names}

The names of objects are identifiers, just like those for algorithms,
and may be chosen freely, as long as they differ from the names
of any other entities in the program.

\subsubsection{Types}

The type of an object serves two purposes:

\begin{itemize}
\item It expresses what operations can be applied to the objects
in question. In a way, it controls that apples cannot be added
to oranges;
\item It determines the internal representation of values in
the computer's memory.
\end{itemize}

\noindent
There are four basic types in Elan, denoted in program texts
by the keywords:

\begin{itemize}
\item {\tt INT   }\\
      integral numbers in the range -2147483647 to 2147483647;
\item {\tt REAL  }\\
      real numbers in a precision of  14 decimals;
\item {\tt BOOL  }\\
      truth values, true and false; and
\item {\tt TEXT  }\\
      sequences of characters.
\end{itemize}

\noindent
Furthermore, objects of any type can be composed into one dimensional
rows. These composed types are discussed in the subchapter on
rows.

\subsubsection{Values}

Since values of the various types are kept within the memory
of the computer, little can be said about them. Knowledge of
their internal representation is not at all necessary to understand
their relevant properties. It should be noted that the Elan programming
environment detects and reports the manipulation of undefined
values, e.g. an attempt to use the value of an uninitialized
variable.

\subsubsection{Access attributes}

The access attribute of an object is either {\tt VAR} or {\tt CONST}
and the objects are correspondingly classed as variables
and constants. The value of a variable can be changed by an assignment,
whereas the value of a constant cannot.

\subsection{Declarations}

A variable declaration may give an initial value to a variable,

\begin{elan}
        INT VAR middle :: ( 1 + max ) DIV 2
\end{elan}

\noindent
otherwise its initial value is undefined, as in

\begin{elan}
        VAR x
\end{elan}

\noindent
Two or more variable declarations can be combined into one unit

\begin{elan}
        VAR left pointer :: 1 ,
            right pointer :: max ,
            middle pointer
\end{elan}

\noindent
A constant declaration must give an initial value to a constant

\begin{elan}
        INT CONST small :: 4711 ;
        TEXT CONST capital :: "monaco"
\end{elan}

\noindent
Each execution of a declaration causes a new elaboration of the
initialization. In this way a constant may have a different value
after each declaration executed. The term ``constant'' is therefore
somewhat misleading: its value is not changeable by an assignment,
therefore it is constant over part or all of the program.

\subsection{Denotations}

Values of basic type can be written down (denoted) in a program
text by denotations:

\begin{itemize}
\item {\tt INT}\\
                Natural numbers can be written as a sequence of digits, e.g.
                {\tt 3}, {\tt 198}, {\tt 10000}
                are all three valid {\tt INT} denotations.

                Negative numbers can be written as expressions consisting of a
                monadic minus operator and an {\tt INT} denotation, e.g.
                {\tt -57}, as you might have suspected.
\item {\tt REAL}\\
                Elan admits the conventional fixed point and floating point
                representation for (approximations) of real numbers,
                like {\tt 3.1415269}, {\tt 1.3e-8}.
\item {\tt BOOL}\\
                There are only two values for truth values, which are denoted
                by the constants {\tt TRUE} and {\tt FALSE} respectively.
                People allergic to capital letters may use the concrete
                standard constants {\tt true} and {\tt false} instead.
\item {\tt TEXT}\\
                Text denotations consist of sequences of characters
                enclosed in quotation marks, e.g. {\tt "Hello world!"}\\
                All printable characters of your computer are allowed
                within text denotations. If a quote character is to appear
                in a text denotation, then it has te be doubled, e.g.
                {\tt "He said ""Don't!"""}
                The empty text consisting of no characters is denoted by
                {\tt ""}.
\end{itemize}

\subsection{Expressions}

An expression in Elan is composed in the conventional fashion
out of operands, monadic operators and dyadic operators with
brackets to indicate grouping.
An operand may in Elan-0 be the name of an object, a denotation,
a subscription, an invocation of a refinement or the call of
a standard procedure. The priority of operators, from high to
low, is as follows:

\begin{itemize}
\item the monadic operators {\tt +}, {\tt -}, {\tt NOT}, {\tt HEAD}, {\tt TAIL}, {\tt LENGTH}
\item {\tt *}, {\tt DIV}, {\tt MOD}
\item dyadic {\tt +}, {\tt -}
\item {\tt =}, {\tt <>}, {\tt >}, {\tt >=}, {\tt <}, {\tt <=}
\item {\tt AND}
\item {\tt OR}
\item {\tt SUB}
\item {\tt INCR}, {\tt DECR}, {\tt CAT}
\item the assignment operator {\tt :=}
\end{itemize}

\subsection{Assignments}

The assignment is a unit of the form

\begin{elan}
        var := expr
\end{elan}

\noindent
where {\tt var} is a variable of some type and {\tt expr} an
expression of the same type.

The assignment serves to change the value of the variable. It
is executed by first executing the expression and then making
its value the new value of the variable. The value of all other
variables remains unchanged.
Thus the assignment

\begin{elan}
        x := x + 1
\end{elan}

\noindent
which can be read as ``x becomes x plus one'' does not mean that
in some curious way {\tt x} becomes equal to itself plus one,
but rather that first the sum of the present value of {\tt x}
and one is computed and then that value is made to be the new
value of {\tt x}.

\subsection{Composed objects: rows}

In Elan-0 the only composed objects are (one-dimensional) row-variables
and row-constants. A declaration for a row-variable looks like

\begin{literal}
        {\tt ROW 5 INT VAR weight}
        {\tt     |  |   |    |\_\_\_\_\_\_}name of the variable
        {\tt     |  |   |\_\_\_\_\_\_}access attribute
        {\tt     |  |\_\_\_\_\_\_}type of each element
        {\tt     |\_\_\_\_\_\_}number of elements
\end{literal}

\noindent
After this declaration, the row-variable {\tt weight} has 5 elements,
numbered from 1 to 5. Each element has an (as yet undefined)
value of the type {\tt INT}.

The subscription

\begin{elan}
        row [ i ]
\end{elan}

\noindent
denotes its {\tt i}-th element provided the value of the expression
{\tt i} (the {\em index}) is between one and the number of elements.
A subscription of a row-variable has the access attribute {\tt VAR},
so it can be assigned to, e.g.

\begin{elan}
        weight [ i ] := 144
\end{elan}

\noindent
After this assignment, the element whose index is equal to the
value of {\tt i}, which must be in the range {\tt 1} to {\tt 5},
is equal to {\tt 144}. Similarly, a row-constant can be declared like

\begin{elan}
        ROW 5 INT CONST first 5 primes ::[ 2, 3, 5, 7, 11 ]
\end{elan}

\noindent
The construct with the square brackets in this example is a {\em row-display},
which acts as a denotation for a row. As with other constant
declarations, the initialization (with a row-display or another
row) in a row-constant declaration is obligatory. A subscription
from a row-constant has the access attribute {\tt CONST}, so
it can not be assigned to.

Apart from the possibility of manipulating individual elements
of a row, it is also possible to deal with the row as a whole,
e.g. in the assignment

\begin{elan}
        weight := first 5 primes
\end{elan}

\noindent
In assignments and initializations, the number of elements in
the left and right hand side must match. The elements of a row
can in their turn be rows again, with a declaration like

\begin{elan}
        ROW 10 ROW 20 INT table
\end{elan}

\noindent
and a subscription like

\begin{elan}
        table [ i ][ j + 1 ]
\end{elan}

\noindent
provided, of course, that {\tt 1 <= i <= 10} and {\tt 1 <= j + 1 <= 20}.

\subsection{Synonym declarations}

In Elan the number of elements (``upper-bound'', ``cardinality'')
in a row declaration must be given by a denotation, that is,
it can not be dependent on the execution of the program. A row
therefore has a statically fixed number of elements. (This is
something of a nuisance but reflects the fact that rows in Elan
do not serve like arrays in other languages. They are intended
to be somewhat inflexible and primitive, and more convenient
data types should be built upon them. In a beginners environment,
their simplicity is an advantage).

Since this upper bound may have to appear in many places in a
program, a mechanism is available which allows the naming of
denotations. Such a {\em synonym declaration} looks like

\begin{elan}
        LET max = 5
\end{elan}

\noindent
which causes the identifier {\tt max} to stand for the denotation
{\tt 5} in suitable places.
The identifier {\tt max} can now be used as a denotation, e.g.:

\begin{elan}
        ROW max INT VAR weight ;
        FOR t FROM 1 UPTO max
        REP
          get ( weight [ t ] )
        ENDREP
\end{elan}

\noindent
In this example, the elements of the {\tt weight} are read successively
with the operation {\tt get}. As shown in this example, rows
and for-loops work together nicely; the use of synonyms assures
that the same range of index values is used.

