%format latex
%%%%%%%%%%%%
%%
%%  Artikel fuer die Tagung SCAN-93 in Wien
%%
%%%%%%%%%%%%

\documentstyle[12pt,a4]{article}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Seitenformat definieren                                              %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\setlength{\unitlength}{1mm}
\setlength{\textwidth}{160mm}
%\setlength{\textheight}{250mm}
\setlength{\oddsidemargin}{0mm}
\setlength{\evensidemargin}{0mm}
%\addtolength{\topmargin}{5mm} 
\parindent0cm
\setlength{\parskip}{3pt plus 1pt minus 1pt}
\frenchspacing
\sloppy
%\pagestyle{myfootings}
%\markright{\kurstitel}

%\renewcommand{\baselinestretch}{1.2}

%%%%%%%%%%%%
%%
%%  Titelblatt
%%
%%%%%%%%%%%%

\newcommand{\mytitle}[1]
{
    \bf
    \begin{center}
       \Large
       PASCAL-XSC \\*[0.5ex]
       \medskip
       A Report on Basic Concepts and \\*[0.5ex]
       Current Development of the Language \\
       \bigskip \medskip
       \normalsize
       Peter Januschke \\*[0.5ex]
       \medskip
       Institute of Applied Mathematics, University of Karlsruhe \\*[0.5ex]
       Kaiserstrasse 12, D--76128 Karlsruhe, Federal Republic of Germany \\*[0.5ex]
       Internet: ae24@rz.uni-karlsruhe.de \\*[0.5ex]
       \bigskip \medskip
       December 6, 1993
    \end{center}
    \normalsize
}

%%%%%%%%%%%%
%%
%%  Weitere eigene Kommandos
%%
%%%%%%%%%%%%

\newenvironment{folie}[1]%
{
  \begin{center}
    #1
    \rule{140mm}{1mm}
  \end{center}
  \hbox{}
  \vfill
}%
{ \vfill
  \hbox{}
  \newpage
}

\newenvironment{myverb}{}{}
\newcommand{\PX}{PASCAL--XSC}
\newcommand{\key}[1]{{\bf #1}}

%
% Syntax - Env.
% -------------

\newenvironment{syntax}
{\begin{flushleft}
\tabcolsep0em
\begin{tabular}{ccc}
\arrayrulewidth3pt
\tabcolsep0em
\vline&\makebox[2.29em]{}&\begin{minipage}{0.85\textwidth}
\setlength{\parindent}{3.5ex}
\tabcolsep6pt
\noindent}{\end{minipage}
              \end{tabular}
              \end{flushleft}}


%%%%%%%%%%%%
%%
%%  Jetzt geht's los
%%
%%%%%%%%%%%%

\begin{document}

\mytitle{29}

\begin{abstract}
The programming language \PX\ has been designed as a
powerful and easy to handle programming tool. It offers the
user a lot of facilities to implement sophisticated numerical
algorithms. \PX\ also is an ideal programming language
to teach students modern programming concepts.

\PX\ provides a large number of predefined data types
and operators for elements of the most commonly used spaces in
numerical analysis. All operators deliver a result of maximum
accuracy and the rounding mode of each operation may be
controlled by the user. Additionally, the scalar product of two
vectors can be computed accurately and the floating point
result of this operation can be obtained by applying only
one final rounding.

Further characteristics of \PX\ include dynamic arrays and strings,
functions with arbitrary result type, user defined operators
and overloading of assignment, operators, functions and procedures.
Moreover, \PX\ supports implementing libraries and splitting
large programs into smaller units by means of modules.

The concept of dynamic arrays has been significantly extended.
A user now is allowed to allocate a dynamic
array variable several times and with different size during the execution
of the subprogram which contains its declaration.
Moreover, dynamic arrays may now be declared as components of other
PASCAL structures such as records, static arrays, or pointers.
\end{abstract}

\newpage

\section{Introduction}
The implementation of numerical algorithms which compute reliable
results requires a precise definition of the underlying arithmetic.
Every operation should be of highest accuracy, i.e. it should be
defined by means of a semimorphism (see \cite{arith}). Furthermore,
a programming language should facilitate the direct use of
operations and the control of the computation\footnote{e.g. rounding modes}.
Additionally, data types and operations for elements of commonly
used sets in numerical algorithms should be available.

Since none of the commonly used programming languages meets
these conditions, the \PX\ system has been developed.
The first part of this article presents the main features of
\PX\ and the \PX\ development system. Due to the fact that
these were the subject of several talks and publications in the
past, I give a summary of features here rather than a detailed
description.

The second part of the article describes the extension
to the concept of dynamic arrays. Up to now, the size of a dynamic array\footnote{i.e. the
number of its elements} declared locally in a
subprogram could not be changed within the statement part of
that subprogram. Future releases of \PX\ will allow
this operation. The user will have the possibility of
allocation and deallocation of dynamic arrays within a program.
This article describes the new syntax and the semantics for
dynamic arrays. It should be regarded as a supplement to the
\PX\ Language Reference \cite{lang}. 

\section{The \PX\ System}
This section gives an overview about the components of the \PX\ system.
The first part summarizes the features of the language while
the second part is about the development system and its
availability.

\subsection{Language Features}
\PX\ ist an e\underline{X}tension of the programming language
PASCAL for \underline{S}cientific \underline{C}omputation. The
following list gives a summary of the language features. A more
detailed description can be found in \cite{prospekt} and, of course,
in \cite{lang}.

\begin{itemize}
   \item {\bf Standard PASCAL}

         With some minor exceptions, \PX\ complies with the ISO Standard
         for PASCAL \cite{iso}. Most of the few deviations arise from
         the fact that \PX\ compilers generate C programs from PASCAL
         sources and that particular PASCAL constructs can not be
         mapped to C efficiently. For example, a {\bf goto}
         statement may not leave the immediately surrounding block.
         See \cite{guide} for a complete description of the deviations.
   \item {\bf Operator Concept (User-defined Operators)}

         The possibility of defining operators for arbitrary data
         types allows the user to represent a mathematical formula
         in a \PX\ program by transcribing the mathematical notation.
         Thus the use of operators simplifies the development and
         increases the readability of programs.

         {\bf Example:}

         Compute the expression $z := u + v + w$, where $ u, v, w$ and
         $z$ are binary numbers\footnote{For simplification, we assume
         that no overflow will occur}.

         With the declarations
         \begin{verbatim}
  CONST max_digits = 32;
  TYPE  binary = ARRAY[ 1 .. max_digits ] OF 0 .. 1;
  VAR   u, v, w, z : binary;

  OPERATOR + ( a, b : binary ) addbb : binary;
  VAR i, c : INTEGER;
  BEGIN
    c := 0;
    FOR i := 1 TO max_digits DO
    BEGIN
      c := a[ i ] + b[ i ] + c;
      addbb[ i ] :=  c MOD 2;
      c := c DIV 2
    END
  END;
         \end{verbatim}
         we are able to write the following assignment statement:
         \begin{verbatim}
  z := u + v + w;
         \end{verbatim}
   \item {\bf Functions and Operators with Arbitrary Result Type}

         Standard PASCAL only allows functions with scalar data
         types\footnote{Integers, floating-point numbers, pointers etc.}
         as their result type. As the above example of an operator declaration
         shows, the result of a function or an operator in \PX\ 
         may also have a composite data type, such as a set, an array, or
         a record.
   \item {\bf Overloading of Subroutines}

         The operator \verb|+| for binary arithmetic\footnote{See the example
         above} can be invoked by using the same notation as for the
         PASCAL operator \verb|+| for addition of integer and floating-point
         numbers. This is possible because \PX\ allows overloading of
         operators as well as overloading of functions or procedures.
         Subroutines may be declared with the same subroutine name
         (or operator symbol) as existing or predefined subroutines.
         A \PX\ compiler distinguishes overloaded subroutines by the
         number and type of their parameters.
   \item {\bf Overloading of the Assignment Operator}

         Example:
         \begin{verbatim}
  TYPE COMPLEX = RECORD re, im : REAL END;
  VAR z : COMPLEX;

  OPERATOR := ( VAR a : COMPLEX; b : REAL );
  BEGIN
    a.re := b;
    a.im := 0
  END;

  {usage}

  z := 1.25;
         \end{verbatim}
   \item {\bf Overloading of READ and WRITE}

         The standard I/O procedures {\it READ} and {\it WRITE} may
         also be overloaded. The usual syntax can be used to call
         the user-defined I/O procedures.

         Example:
         \begin{verbatim}
  TYPE mytype = ... { user-defined data type }
  VAR  a, c : INTEGER;
       b    : mytype;
  PROCEDURE WRITE( VAR f : TEXT; x : mytype; width : INTEGER );
     { specify output of x to f here }

  {usage}

     WRITE( a, b : 10, c );
         \end{verbatim}
   \item {\bf Module Concept}

         Three new keywords \key{module}, \key{global}, and \key{use}
         have been added to the PASCAL language to permit the use
         of modules in \PX. \key{module} has to be used instead of
         \key{program} to declare a piece of program not to be
         directly executable but importable by another program or
         module. Within a module, entities that should be usable
         by programs or modules that import this module have to be
         marked with a preceding \key{global} at the point of their
         declararation.

         Example:
         \begin{verbatim}
  MODULE my_mod;

  GLOBAL TYPE my_type = ARRAY[ 1 .. 10 ] OF INTEGER;

  {further declarations}

  END.
         \end{verbatim}
         Modules can be imported by programs or other modules by
         using the \key{use} keyword followed by the name of a
         module or a list of module names. Any entitity that has
         been marked with the \key{global} keyword in an imported
         module is then usable within the importing program or
         module.

         Example:
         \begin{verbatim}
  PROGRAM my_prog;

  USE my_mod;

  VAR my_var : my_type;

   ...
         \end{verbatim}
   \item {\bf Dynamic Arrays}

         Dynamic Arrays allow the user to declare dynamic entities
         within subprograms. They are extensively described in
         section \ref{dynarr}.
   \item {\bf String Concept}

         A new data type {\it STRING} and some string handling subroutines
         have been added to the PASCAL language to facilitate text processing.
   \item {\bf Controlled Rounding}

         The rounding mode of any of the predefined arithmetic operators
         and the calculation of scalar products in \PX\ can be controlled
         by the user. When specifying the usual
         operator symbols $+, -, *,$ or $/$ in an expression
         the corresponding operation carries out
         rounding to the nearest floating-point number. If
         the operator symbol is followed by $<$, rounding towards
         $- \infty$ is used. If it is followed by $>$, rounding towards
         $+ \infty$ is used. Scalar product computations can be handled in a
         similar way while interval operations always compute the smallest
         enclosure of the mathematically correct result.
   \item {\bf Optimal Scalar Product}

         As I stated before, optimal matrix and vector arithmetic
         requires the calculation of the exact value of a scalar
         product. This operation is available in \PX\ by means of so-called
         sharp expressions (\#-expressions, see next point).
         
   \item {\bf Exact Evaluation of Expressions (\#-Expressions)}

         A new data type {\it DOTPRECISION} has been added to the PASCAL
         language. Variables of type {\it DOTPRECISION} can hold the exact
         value of a dot product. Due to the fact that a scalar product may
         be computed in an accumulative way {\it DOTPRECISION} variables
         are often called long accumulators. {\it DOTPRECISION} values are
         computed by sharp expressions. A sharp expression is always introduced
         by the symbol \# which is followed by an optional rounding mode symbol
         and an expression that can be computed as a scalar product, enclosed
         in brackets.

         Example:
         \begin{verbatim}
  #<( a * b - c * d )
         \end{verbatim}

   \item {\bf Additional arithmetic standard Types}

         Numerical algorithms are formulated not only for real numbers
         but also for complex numbers, intervals, complex intervals,
         and vectors and matrices over these sets. \PX\ provides standard
         data types for elements of each of these spaces.
   \item {\bf Highly accurate Arithmetic for all standard Types}
   \item {\bf Highly accurate standard Functions}
\end{itemize}

\subsection{The \PX\ system}

A main goal for the design of the \PX\ system was to create a highly
portable system (see \cite{port}). Therefore, the implementation of
the whole \PX\ package,
in particular of the compiler and the runtime library, was based on ANSI C
\cite{ansic}. The compiler translates PASCAL--XSC programs into C programs
which then are compiled to an executable program by an ANSI C compliant
compiler. The availability of such a compiler is the only requirement for
the installation of the \PX\ system on a given platform.

Besides, the arithmetic has been based on the IEEE 754 standard for 
floating-point arithmetic \cite{ieee}. Thus \PX\ programs produce the
same results on any platform, which means that
programs written in PASCAL--XSC are portable too. For
example, a program may be developed and tested on a small computer (PC) and
then run on a so-called supercomputer.

A \PX\ development system includes a configuration program, a manager
program that controls the compilation steps, a \PX\ to C compiler,
a listing generator and a runtime library.
Additionally precompiled arithmetic modules for basic types, as there are
intervals, complex numbers, and complex intervals, as well as modules for
vectors and matrices with components of any basic type (including real
numbers) belong to a complete system. Each module provides arithmetic and
relational operators as well as standard and transfer functions for one
of the standard data types of \PX.

\PX\ already has been ported to various platforms.
The latest release is PASCAL--XSC version 2.03, released in
October 1992. The following table gives a summary of the
available versions. It is an update of a table given in
\cite{prospekt}. \\
%    \renewcommand{\arraystretch}{1.2}
%    \bf
  \begin{center}
    \begin{tabular}{|c|c|c|c|}
       \hline
       Computer & Operating system & C compiler & Hardware support \\
       \hline
       IBM PC & DOS & Microsoft C 7.0 & yes \\
       IBM PC & DOS & Borland C++ 3.1 & yes \\
       IBM PC & DOS & Zortech C 3.0 & yes \\
       IBM PC & OS/2 2.0 & IBM C Set/2 & \\
       Atari ST & TOS( Gulam shell ) & Turbo C 2.0 & \\
       Sun SPARC station & Sun OS 4.1, Solaris & System & yes \\
       Micro VAX station & ULTRIX & System & \\
       DEC Station 3100 & ULTRIX & System & \\
       IBM PS/2 & AIX & System & \\
       IBM RS 6000 & AIX & System & \\
       HP 9000/300 series & HP UX & System & \\
       HP 9000/800 series & HP UX & System & \\
       HP 9000/700 series & HP UX & System & yes \\
       NeXT & UNIX & System & \\
       CONVEX & UNIX & System & \\
       VAX & VMS & System & \\
       Transputer T800 & HELIOS & System & \\
       Data General & ULTRIX & System & \\
       \hline
    \end{tabular} \\*[1.3ex]
    Table 1: Availability of the \PX\ system
  \end{center}
 %   \renewcommand{\arraystretch}{1}

\section{New features of Dynamic Arrays}  \label{dynarr}

This section describes the concept of dynamic arrays. First, a
summary of the present concept (see \cite{lang}) is given. After
that the new features are discussed.

For this article is intended to be a supplement to the Language
Reference \cite{lang}, I use the same notation than the latter
for describing the syntax of the new constructs. It is a simplified
Backus-Naur-Form which looks similar to usual program code. Syntax
descriptions are marked by a vertical black bar at the left margin.
The representation of the syntax consists of
\begin{itemize}
   \item basic symbols in their usual notation. Keywords are written
         in {\bf boldface} letters,
   \item syntax variables,
   \item predefined identifiers,
   \item repetition symbols\ \ldots\ , and
   \item comments enclosed in braces \{ \}.
\end{itemize}
Syntax variables are English nouns or composite nouns which are
used as abbreviations of other syntactical units. Predefined
identifiers are written in {\sl slanted} characters. The repetition
symbol\ \ldots\ denotes an arbitrary number of a part of the syntax,
i.e. the preceding group of language elements within the same line.
This group may occur zero or more times if no comment to the
contrary is given.

To generate PASCAL code by means of this syntax representation, we
have to read line after line from left to right and note the
basic symbols and the syntax variables in the appropriate number
of repetitions. Then we must successively replace the syntax variables
by their own definitions to eliminate them. This process ends when all
syntax variables are eliminated.

Example: Syntax description of an expression.
\begin{syntax}%
\begin{tabular}{lllll}
  MonadicOperator \\
                 & Operand & \{ not empty \}  &         &  \\
                 &         & DyadicOperator   & Operand & ...
\end{tabular}
\end{syntax}%


\subsection{Dynamic Arrays} \label{dyns}

The basic characteristic of this concept is the possibility of
using dynamic entities within subroutines. Locally declared
dynamic array variables are automatically allocated and deallocated
during the execution of the subroutine they belong to. Further,
it is possible to access subarrays.

The type declaration for a dynamic array is similar to the declaration
of a static array type. One only has to insert the keyword
\key{dynamic} and to replace the index ranges by asterisks.

\begin{samepage}
{\bf Example:} Type declaration for a real vector.
       \begin{verbatim}
  TYPE vector = DYNAMIC ARRAY[ * ] OF REAL;
       \end{verbatim}
\end{samepage}
The index ranges have to be declared for every dynamic array
variable individually in the variable declaration part belonging
to it.

{\bf Example:} Declaration of a real vector variable.
      \begin{verbatim}
  VAR v : vector[ 1 .. 10 ]; 
      \end{verbatim}

The main application of dynamic arrays is their use within subroutines.
Consider the following schematic example of the procedure \verb|do_something|:
%      \bf \parindent0em
      \begin{verbatim}
  PROCEDURE do_something( n : integer );               
  VAR local : vector[ 1 .. n ];                         
  BEGIN                                                
    { do something ... }                                  
  END;                                                    
      \end{verbatim}
Here, the procedure is declared with an integer parameter \verb|n|.
By means of this parameter the index bounds of the local variable
\verb|local| are specified. This means, that \verb|local| may hold
a different number of elements upon different calls of \verb|do_something|.
The disadvantage of this method is that it is not possible to
reallocate \verb|local| while the procedure is being executed.
In practice, however, it is desirable to be able to use a
structure\footnote{In our example this is a real vector}
with a different number of elements for different purposes within
a single subroutine. This could be realized by declaring several
dynamic array variables with different element numbers.
However, to minimize memory usage it should be possible to reuse
variables, i.e. to reallocate them, whenever this is appropriate.
This is the motivation for the extension to
the concept of dynamic arrays which is discussed later.

Access to the components of a dynamic array can be controlled
by means of the standard functions {\it lbound} and {\it ubound}
or their abbreviations {\it lb} and {\it ub}.

{\bf Example:}
        \begin{verbatim}
  OPERATOR + ( a, b : vector ) add : vector[ LB( a ) .. UB( a ) ];
  VAR i, h : INTEGER;
  BEGIN
    h := LB( b ) - LB( a );
    FOR i := LB( a ) TO UB( a ) DO add[ i ] := a[ i ] + b[ h + i ]
  END;
       \end{verbatim}
Please notice that the index bounds of \verb|a| are not only
used to access the elements of the arrays but also to specify the
index bounds of the operator's result. Further, to simplify the example,
we are assuming that both, \verb|a| and \verb|b|, have the same number
of elements\footnote{In practice this condition should be checked in the
statement part of the operator}.

{\bf Remark :}

The following text describes the features of reallocatable
dynamic arrays. I call these arrays {\it flexible arrays}
and use this term only temporarily to have the possibility of
clearly distinguishing the declaration syntax and semantics
of the new and the old concept. After having described the
declaration of flexible arrays, dynamic and flexible arrays
are no longer distinguished.

\subsection{Flexible arrays}

Future releases\footnote{The next release will be version 3.01}
of PASCAL--XSC will include the concept of {\it flexible} arrays.
We call an array a flexible array if it can be reallocated with
new index bounds and new size at any time during
its lifetime.

The realization of this concept led to the following basic ideas:
\begin{itemize}
   \item The syntax and semantics for declaring dynamic array
         types and dynamic array variables has to be extended.
   \item The use of flexible arrays according to the present
         rules for dynamic arrays shall not result in different
         behaviour of PASCAL--XSC programs.
   \item Standard procedures for memory allocation and deallocation
         for flexible arrays have to be provided.
   \item Assignment of a flexible array to another flexible
         array implicitely
         allocates the destination array, if it has not been
         allocated before.
   \item The semantics of type declarations has to be extended;
         flexible arrays may be used as components of other
         composite data types.
\end{itemize}

\subsubsection{Declaring a Flexible Array Type} \label{flextype}

The syntax for declaring flexible array types is as follows:

\begin{syntax}
   \key{dynamic} \key{array} [DimensionList] \key{of} Type
\end{syntax}

\begin{samepage}
A DimensionList is either a list\footnote{A list always consist of at
least one
element. If more than on element is to be specified then the elements
have to be separated by commas.} of asterisks (\verb|*|) or a
list of index types. An index type is specified by
either the type identifier of an integer subrange type or by
explicitely specifying the index bounds in the usual way:

\begin{syntax}
      IntegerExpression .. IntegerExpression
\end{syntax}
\end{samepage}

From this follows that there are two possibilities of declaring flexible
array types. The first possiblity simply is the adaption of the old
declaration rules, e.g. every dynamic array is also a flexible array.
                 \begin{verbatim}
  TYPE vector = DYNAMIC ARRAY[ * ] OF REAL;
                 \end{verbatim}
The second possibility is to provide default index ranges for flexible
array variables. In practice it oftenly occurs that a program uses
many array variables of the same array type with identical index
bounds and only a few variables of the same structure with
other index bounds. The extended rules for array declaration
allow for this situation.
                 \begin{verbatim}
  TYPE vec = DYNAMIC ARRAY[ 1 .. 10 ] OF REAL;
    { or }
  TYPE vec = vector[ 1 .. 10 ];                
                 \end{verbatim}
When declaring flexible array types with several index ranges it is not allowed to mix asterisks with default index ranges. Thus the semantics for using
flexible arrays is kept simple.

\subsubsection{Declaring Flexible Array Variables} \label{flexvar}

The syntax for a dynamic array variable declaration has been
extended according to the changes for type declarations in section
\ref{flextype}.

\begin{syntax}
   \key{var} IdentifierList : FlexTypeIdentifier [DimensionList];
\end{syntax}

As usual, variables may be declared without using a predefined or
user-defined array type:

\begin{syntax}
   \key{var} IdentifierList : FlexTypeIdentifier;
\end{syntax}

Here, FlexTypeIdentifier stands for the construction rule for flexible array
types given in \ref{flextype}. Again, these rules allow several possibilities
of declaring flexible array variables. For the type identifiers used
in this example, please refer to the examples in \ref{flextype}.
     \begin{itemize}
        \item Specifying index ranges:
                 \begin{verbatim}
  VAR v : vector[ 1 .. 10 ];                 
    { or }
  VAR v : DYNAMIC ARRAY[ 1 .. 10 ] OF REAL;    
                 \end{verbatim}
              Variables declared in this way are automatically allocated resp.
              deallocated upon entry resp. exit of the subprogram they
              belong to, i.e. they behave the same way as dynamic arrays do.
              Further, those variables may be reallocated during the execution
              of the subroutine they belong to.

        \item Omitting index ranges:
                 \begin{verbatim}
  VAR v : vector;                              
    { or }
  VAR v : DYNAMIC ARRAY[ * ] OF REAL;           
                 \end{verbatim}
              In this case \verb|v| has to be explicitely allocated by the
              user. Nevertheless, it will be automatically deallocated upon
              exit of the subroutine it belongs to. Of course, \verb|v| may
              be reallocated by the user.
        \item Using flexible arrays with default index ranges:
                 \begin{verbatim}
  VAR v : vec;                 
    { or }
  VAR v : vec[ 1 .. 20 ];    
                 \end{verbatim}

              In both cases automatic memory allocation and deallocation
              will be carried out, but the allocation process is different.
              When omitting the specification of the index bounds for \verb|v|
              the default index bounds of \verb|vec| are used, otherwise
              the specified index bounds replace the default bounds.
              Again, \verb|v| may be reallocated by the user in any case.
     \end{itemize}
The preceding and this section should have shown that the concept of flexible
arrays is an extension to that of dynamic arrays. It should have become
clear that programs that have been developed by exclusively using the
dynamic array features can be compiled with future compiler versions
without change. In the following descriptions of further language
extensions it is no longer necessary to distinguish between dynamic
and flexible arrays; these features apply to both. Consequently we will
only speak of dynamic arrays from now on.

\subsubsection{Memory Management Subroutines} \label{mem}

This section introduces a set of subroutines for handling dynamic
arrays, in particular for memory management. The first routine is
the procedure {\sl allocate} which allows the explicit allocation
of a dynamic array with the specified index bounds. It is called
in the form:
\begin{syntax}
   \begin{tabular}{llll}
      {\sl allocate} (DynamicArrayVariable & & & \\
      & , IndexRange ... & & \{not empty\}\\
      & & ); &
   \end{tabular}
\end{syntax}
Its first parameter is a dynamic array variable which is followed by
a list of index ranges. Index ranges are specified in the usual way
by specifying the index bounds:
\begin{syntax}
      IntegerExpression .. IntegerExpression
\end{syntax}
The number of index ranges specified must be the same as the number
of index ranges in the declaration of the dynamic array type belonging
to the dynamic array parameter. If the array variable passed to {\sl allocate}
is not allocated yet, it will be allocated with the specified
index bounds. If an array variable is already allocated, it first will
be deallocated. The latter allows the user to reallocate an array
with new index bounds and new size.

A further procedure provides the possibility of freeing memory occupied
by a dynamic array variable, i.e. a dynamic array may explicitely be
deallocated. It is called by:
\begin{syntax}
   {\sl free} ( DynamicArrayVariable );
\end{syntax}
{\sl free} has only a single parameter which must be a dynamic array
variable. After a call to {\sl free} the index bounds of the array
parameter are undefined as long as the array is not allocated
again. {\sl free} will have no
effect if an array is not allocated when it is passed as a parameter.

Access to an array which is not allocated may have undesirable
consequences such as a runtime error (see \ref{access}). Therefore,
\PX\ provides
a function for testing the accessibility of dynamic arrays. It is
called by
\begin{syntax}
   {\sl allocated} ( DynamicArrayVariable )
\end{syntax}
and delivers a boolean result. {\sl allocated} yields the value
{\sl true}, if the dynamic array variable which has to be passed
as the only parameter is allocated, and {\sl false} otherwise.

\subsubsection{First Examples}

\vfill

1. \verb|do_something|

\vfill

In \ref{dyns} I gave the procedure \verb|do_something| as an
example of how to use dynamic arrays within subroutines. It contained
a declaration of a local variable named \verb|local| the size
of which was specified by the integer parameter of the procedure.

Now let us assume that we want to double the size of \verb|local|
within the procedure. By means of the new standard subroutines
described in \ref{mem}, we may change \verb|do_something| as follows:
        \begin{verbatim}
  TYPE vector = DYNAMIC ARRAY[ * ] OF REAL;

  PROCEDURE do_something( n : INTEGER );
  VAR local : vector;
  BEGIN
    ALLOCATE( local, 1 .. n );
      { do something ... }
    FREE( local );               { might be omitted }
    ALLOCATE( local, 1 .. 2 * n );
      { do something else ... }
  END;
       \end{verbatim}

The first call to {\sl allocate} sets up the variable local
with indices ranging from 1 to \verb|n|. After some further
statements we deallocate \verb|local| by calling {\sl free}.
In this example this would not be necessary because the
following call to {\sl allocate} first would deallocate
\verb|local| automatically. However, if the program was in danger
to run out of memory and \verb|local| was not be used
in the remaining statements of the procedure, it would surely
be useful to deallocate the array here. Finally, the second
call to {\sl allocate} sets up \verb|local| once more, this time
with an index range from 1 to 2 \verb|n|.

\vfill

2. Input of a real vector from a textfile.

\vfill

\verb|n| real numbers shall be read from a textfile into an
array of real numbers. The input file first specifies the
dimension \verb|n| of the vector, and then its \verb|n| components.
Without the possibility of reallocation of dynamic arrays the
solution of this problem is very laborious. Having the new features
available the solution is very simple:

\newpage
        \begin{verbatim}
  PROCEDURE read( VAR f : TEXT; VAR v : vector );
  VAR i, n : INTEGER;
  BEGIN
    IF ALLOCATED( v ) THEN FREE( v );
    READ( f, n );
    ALLOCATE( v, 1 .. n );
    FOR i := LB( v ) TO UB( v ) DO READ( f, v[ i ] )
  END;
       \end{verbatim}

The \key{if} statement is rather a demonstration of the use of the
function {\sl allocated} than it is necessary. It causes \verb|v|
to be deallocated in any case. Next, the number \verb|n| of vector elements
in the textfile is read. Then this number is used to allocate \verb|v|
with the appropriate size. Finally, the \key{for} statement reads the
vector elements from the textfile.

\subsubsection{Access to and Assigment of Dynamic arrays} \label{access}

Compared to the present implementation (see \cite{lang}), the semantics of the assignment statement
        \begin{verbatim}
           A := B;
        \end{verbatim}
where A and B are assignment compatible dynamic arrays,
will not change with the following exceptions.

\begin{enumerate}
        \item A runtime error will be issued if \verb|B|
              is not allocated.
        \item If \verb|A| is not allocated, it
              will be allocated before assignment will be carried out.
              \verb|A| will have the same size
              and index bounds as \verb|B|.
\end{enumerate}
A runtime error is issued if a dynamic array which is not allocated
is accessed in an expression and if array indices are to be checked.
Otherwise, if array indices are not checked then the effect of accessing a
dynamic array which is not allocated is undefined\footnote{The checking
of array indices is controlled by compiler options, see \cite{guide}}.

\subsubsection{Dynamic arrays as components of other types}

Dynamic arrays may now be declared as components of other composite
data types as there are
     \begin{itemize}
        \item static arrays
        \item records
        \item pointers
     \end{itemize}

This is not a syntax extension but an extension to the semantics of
type declarations. The declaration of a dynamic array type as the
component type of a composite data type follows the rules for
dynamic array type declarations in \ref{flextype}. In particular,
default index ranges may be specified.

     Example:
        \begin{verbatim}
  TYPE rec = RECORD
               a, b : REAL;
               v    : DYNAMIC ARRAY[ * ] OF REAL
             END;                 
    { or }
  TYPE rec = RECORD
               a, b : REAL;
               v    : DYNAMIC ARRAY[ 1 .. 5 ] OF REAL
             END;    
        \end{verbatim}

     The rules for allocation and deallocation of dynamic components
     are the same as for dynamic array variables.     

Special care has to be taken when a program uses pointers to
dynamic arrays. Consider the following example:
        \begin{verbatim}
  TYPE dyn  = DYNAMIC ARRAY[ * ] OF INTEGER;
       dyn2 = DYNAMIC ARRAY[ 1 .. 10 ] OF INTEGER;

  VAR p1 = ^dyn;
      p2 = ^dyn2;

  BEGIN
    NEW( p2 );                  {automatic allocation of p2^}

    NEW( p1 );                  {allocation of a runtime descriptor only}
    ALLOCATE( p1^, 1 .. 10 );   {explicit allocation of p1^}
       {further statements}
  END
        \end{verbatim}
As you can see \verb|p2| points to a dynamic array with default
index range from 1 to 10. Therefore, the call to {\sl new}
automatically allocates the dynamic array \verb|p2| points to.
This is not the case for {\sl new} (\verb|p1|). Because \verb|p1|
points to a dynamic array which has no default index ranges
{\sl new} only creates a runtime descriptor for the array. The
array itself has to be explicitely allocated with a call
to {\sl allocate}.

\section{Conclusion}

Dynamic arrays allow for the need of flexiblity in data management
in programs. The concept presented here includes some basic features
that are sufficient for solving elementary problems that deal with
dynamic structures, in particular in connection with the possibility
of declaring dynamic arrays as components of composite data types.

Further extensions to this concepts may be possible. For example,
a resize operation could be defined that allows changing the size
of an array without deallocation of that structure. Moreover,
functions and operators could have dynamic arrays as their
results without a specification of the size of that results in
the declarations of that subroutines. If tests proved that such
a feature would be useful, it should be added to the language.

The extensions to \PX\ as described in this article are currently
being implemented and tested. They will be available with the next
release of the \PX\ system which hopefully will be issued in the
first quarter of 1994.

\begin{thebibliography}{99}
   \bibitem{port} Allend\"orfer, U.; Shiriaev, D.:
                  {\it \PX. A portable Development System.} Proceedings of the
                  13th World Congress on Computation and Applied Mathematics,
                  IMACS '91, Dublin, 1991.
   \bibitem{ansic} American National Standards Institute:
                   {\it American National Standard for Information Systems --
                    Programming Language C.} ANSI Standard X3.159-1989,
                    New York, 1989.
   \bibitem{ieee} American National Standards Institute/Institute of Electrical
                  and Electronics: {\it A Standard for Binary Floating-Point
                  Arithmetic.} ANSI/IEEE Standard 754-1985, New York, 1985.
   \bibitem{rts}  Cordes, D.: {\it Runtime System for a \PX\ Compiler.} In
                  \cite{kaucher}, pp. 151--160, 1991.
   \bibitem{prospekt} Ge\"org, S.; Hammer, R.; Neaga, M.; Ratz, D.;
                      Shiriaev, D.:
                      {\it \PX. A PASCAL Extension for Scientific Computation
                       and Numerical Data Processing.} Technical report,
                       Insitute of Applied Mathematics, University of
                       Karlsruhe, May 1993.
   \bibitem{tooleins} Hammer, R.; Hocks, M.; Kulisch, U.; Ratz, D.:
                      {\it Numerical Toolbox for Verified Computing I:
                       Basic Numerical Problems.} Springer-Verlag,
                       Berlin, Heidelberg, New York, 1993.
   \bibitem{acrith} IBM: {\it ACRITH--XSC: IBM High Accuracy Arithmetic ---
                         Extended Scientific Computation. Version 1, Release 1.}
                         IBM Deutschland GmbH, Department 3282,
                         Sch\"onaicher Strasse 220, D--71032 B\"oblingen,
                         3rd edition, 1986.
   \bibitem{iso}  Jensen, K.:, Wirth, N.: {\it PASCAL User Manual and Report.}
                  ISO Pascal Standard, 3rd ed., Springer, New York, 1985.
   \bibitem{kaucher} Kaucher, E.; Mayer, G.; Markov, S. M. (Eds.):
                     {\it Computer Arithmetic, Scientific Computation and
                      Mathematical Modelling.} Proceedings of SCAN--90.
                      IMACS Annals on Computing and Applied Mathematics,
                      Vol. 12 (1992), published Oct. 1991, J.C.Baltzer AG,
                      Basel, 1991.
   \bibitem{lang} Klatte, R.; Kulisch, U.; Neaga, M.; Ratz, D.; Ullrich, Ch.:
                  {\it PASCAL--XSC --- Language Reference with Examples.}
                  Springer-Verlag, Berlin/Heidelberg/New York, 1992
   \bibitem{cxsc} Klatte, R.; Kulisch, U.; Lawo, C.; Rauch, M.; Wiethoff, A.:
                  {\it C--XSC, A C++ Class Library for Extended Scientific
                   Computing.} Springer-Verlag, Berlin/Heidelberg, New York,
                  1993.
   \bibitem{toolzwei} Kr\"amer, W.; Kulisch, U.; Lohner, R.: {\it Numerical
                      Toolbox for Verified Computing II.} Springer-Verlag,
                      Berlin/Heidelberg/New York, to appear 1994.
   \bibitem{arith} Kulisch, U.; Miranker, W.L.:
                   {\it Computer Arithmetic in Theory and Practice.}
                   Academic Press, New York, 1981.
   \bibitem{guide} Numerik Software GmbH: {\it PASCAL-XSC: A PASCAL Extension
                   for Scientific Computation. User's Guide.}, Numerik
                   Software GmbH, P.O.Box 2232, D--76492 Baden-Baden, 1991.
\end{thebibliography}
\end{document}

