% dbpl_system1.tex

\chapter{DBPL Language Report}
   
\label{Report}

\section{Syntax}

\label{Syntax}
   
   A language is an infinite set of sentences, namely the sentences
   well formed according to its syntax. In DBPL, these sentences are
   called {\em compilation units}. Each unit is a finite sequence of
   symbols from a finite {\em vocabulary}. The vocabulary of DBPL
   consists of identifiers, numbers, strings, operators, and
   delimiters. They are called lexical {\em symbols} and are composed
   of sequences of characters. (Note the distinction between symbols
   and characters.)
   
   To describe the syntax, an extended Backus-Naur Formalism called
   EBNF is used. Angular brackets [ ] denote optionality of the
   enclosed sentential form, and curly brackets \{ \} denote its
   repetition (possibly 0 times). Syntactic entities (non-terminal
   symbols) are denoted by English words expressing their intuitive
   meaning. Symbols of the language vocabulary (terminal symbols) are
   strings enclosed in quote marks or words written in capital
   letters, so-called  {\em reserved} words. Syntactic rules
   (productions) are designated by a \$ sign at the left margin of the 
   line. 
   
\section{Vocabulary and representation}
   
\label{vocabulary}
   The representation of symbols in terms of characters depends on the
   underlying character set. The ASCII set is used in this paper, and
   the following lexical rules must be observed. Blanks must not occur
   within symbols (except in strings). Blanks and line breaks are
   ignored unless they are essential to separate two consecutive
   symbols. 
   
   \begin{enumerate}
      \item {\em Identifiers} are sequences of letters and digits. The
            first character must be a letter.

\begin{syntax}
\$ ident = letter \{letter $|$ digit\}.
\end{syntax}

      Examples:
\begin{verbatim}
      x scan Modula ETH GetSymbol firstLetter
\end{verbatim}

      \item {\em Numbers} are (unsigned) integers or real numbers.
      Integers are sequences of digits. If the number is followed by
      the letter B, it is taken as an octal number; if it is followed
      by the letter H, it is taken as a hexadecimal number; if it is
      followed by the letter C, it denotes the character with the
      given (octal) ordinal number (and is of type CHAR, see 6.1).
      
      An integer i in the range 0 $<=$ i $<=$ MaxInt can be considered
      as either of type INTEGER or CARDINAL; if it is in the range
      MaxInt $<$ i $<=$ MaxCard, it is of type CARDINAL. For 16-bit
      computers: MaxInt = 32767, MaxCard = 65535. 
      
      A real number always contains a decimal point. Optionally it may
      also contain a decimal scale factor. The letter E is pronounced
      as  ``ten to the power of''. A real number is of type REAL.

\begin{syntax}
\$ number = integer $|$ real.\\
\$ integer = digit \{digit\} $|$ octalDigit \{octalDigit\} (``B'' $|$ ``C'') $|$\\
\$ \> digit \{hexDigit\} ``H''.\\
\$ real = digit \{digit\} ``.'' \{digit\} [ScaleFactor].\\
\$ ScaleFactor = ``E'' [``+'' $|$ ``-''] digit \{digit\}.\\
\$ hexDigit = digit $|$ ``A'' $|$ ``B'' $|$ ``C'' $|$ ``D'' $|$ ``E'' $|$ ``F''.\\
\$ digit = octalDigit $|$ ``8'' $|$ ``9''.\\
\$ octalDigit = ``0'' $|$ ``1'' $|$ ``2'' $|$ ``3'' $|$ ``4'' $|$ ``5'' $|$ ``6'' $|$ ``7''.\\
\end{syntax}

      Examples:
\begin{verbatim}
      1980  3764B  7BCH  33C  12.3  45.67E-8
\end{verbatim}

      \item {\em Strings} are sequences of characters enclosed in
      quote marks. Both double quotes and single quotes (apostrophes)
      may be used as quote marks. However, the opening and closing
      marks must be the same character, and this character cannot
      occur within the string. A string must not extend over the end
      of a line. 

\begin{syntax}
\$ string = ``\,'\,'' \{character\} ``\,'\,'' $|$ ``"'' \{character\} ``"''.
\end{syntax}
                                                                           
% 3rd Ed.
      A string consisting of n characters is of type (see \ref{arrayType}).
\begin{verbatim}
      ARRAY [0..n-1] OF CHAR   
\end{verbatim}

      Examples:
\begin{verbatim}
      "DBPL"  "Don't worry!"  'codeword "Barbarossa"'
\end{verbatim}
   
      \item {\em Operators and delimiters} are the special characters,
      character pairs, or reserved words listed below. These reserved
      words consist exclusively of capital letters and {\em must not} be
      used in the role of identifiers. The symbols \# and $<>$ are
% 3rd Ed.
      synonyms, and so are \&, AND, and \tilde, NOT. 

\bchanged
\begin{center}
\begin{tabular}{lllll}\tt
 \verb"+"   &  \verb"<"     &  ALL           &  EXPORT        &  QUALIFIED\\
 \verb"-"   &  \verb">"     &  AND           &  FOR           &  RECORD\\
 \verb"*"   &  \verb"<>"    &  ARRAY         &  FROM          &  RELATION\\
 \verb"/"   &  \verb"<="    &  BEGIN         &  IF            &  REPEAT\\
 \verb":="  &  \verb">="    &  BY            &  IMPLEMENTATION&  RETURN\\
 \verb"&"   &  \verb".."    &  CASE          &  IMPORT        &  SELECTOR\\
 \verb"."   &  \verb":"     &  CONST         &  IN            &  SET\\ 
 \verb","   &  \verb")"     &  CONSTRUCTOR   &  LOOP          &  SOME\\
 \verb";"   &  \verb"]"     &  DATABASE      &  MOD           &  THEN\\
 \verb"("   &  \verb"}"     &  DEFINITION    &  MODULE        &  TO\\  
 \verb"["   &  \verb"|"     &  DIV           &  NOT           &  TRANSACTION\\
 \verb"{"   &  \verb":+"    &  DO            &  OF            &  TYPE\\
 \verb"^"   &  \verb":-"    &  EACH          &  ON            &  UNTIL\\
 \verb"="   &  \verb":&"    &  ELSE          &  OR            &  USING\\
 \verb"#"   &               &  ELSIF         &  POINTER       &  VAR\\ 
% 3rd Ed. 
 \tilde     &               &  END           &  PROCEDURE     &  WHILE\\
            &               &  EXIT          &                &  WITH
\end{tabular}                              
\end{center}                   
\echanged

      \item {\em Comments} may be inserted between any two symbols in
      a program. They are arbitrary character sequences opened by the
      bracket $(*$ and closed by $*)$. Comments may be nested, and they do
      not affect the meaning of a program. 
   \end{enumerate}
   
\section{Declarations and scope rules}
    
\label{declarations}
   Every identifier occurring in a program must be introduced by a
   declaration, unless it is a standard identifier. The latter are
   considered to be predeclared, and they are valid in all parts of a
   program. For this reason they are called {\em pervasive}.
   Declarations also serve to specify certain permanent properties of
   an object, such as whether it is a constant, a type, a variable, a
   procedure, or a module. 
   
   The identifier is then used to refer to the associated object. This
   is possible in those parts of a program only which are within the
   so-called {\em scope} of the declaration. In general, the scope
   extends over the entire block (procedure or module declaration) to
   which the declaration belongs and to which the object is local. The
   scope rule is augmented by the following cases:
   
   \begin{enumerate}
      \item  If an identifier x defined by a declaration D1 is used in
      another declaration (not statement) D2, then D1 must textually
      precede D2. 
      
      \item A type T1 can be used in a declaration of a pointer type T
      (see \ref{pointerType}) which textually precedes the declaration of T1, if
      both T and T1 are declared in the same block. This is a
      relaxation of rule 1. 
      
      \item If an identifier defined in a module M1 is exported, the
      scope expands over the block which contains M1. If M1 is a
      compilation unit (see Ch. \ref{compilation}), it extends to all those units
      which import M1. 
                                                                       
      \item Field identifiers of a record declaration (see \ref{recordType}) are
      valid only in field designators and in with statements referring
      to a variable of that record type. 
\end{enumerate}

% 3rd Ed.      
An identifier may be {\em qualified}. In this case it is
prefixed by another identifier which designates the module (see
Ch. \ref{module}) in which the qualified identifier is defined. The prefix
and the identifier are separated by a period. Standard identifiers appear
below.

\begin{syntax}
\$ qualident = ident \{``.'' ident\}.
\end{syntax}

% 3rd Ed.                        
\bchanged
\begin{center}
\begin{tabular}{lr lr}
ABS       & (\ref{standardProc})      & LONGINT  & (\ref{basicType})\\     
BITSET    & (\ref{setType})           & LONGREAL & (\ref{basicType})\\     
BOOLEAN   & (\ref{basicType})         & LOWEST   & (\ref{standardProc})\\  
CAP       & (\ref{standardProc})      & MAX      & (\ref{standardProc})\\  
CARD      & (\ref{standardProc})      & MIN      & (\ref{standardProc})\\  
CARDINAL  & (\ref{basicType})         & NEXT     & (\ref{standardProc})\\  
CHAR      & (\ref{basicType})         & NIL      & (\ref{pointerType})\\   
CHR       & (\ref{standardProc})      & ODD      & (\ref{standardProc})\\  
DEC       & (\ref{standardProc})      & ORD      & (\ref{standardProc})\\  
EOR       & (\ref{standardProc})      & PRIOR    & (\ref{standardProc})\\  
EXCL      & (\ref{standardProc})      & PROC     & (\ref{procedureType})\\ 
FALSE     & (\ref{basicType})         & REAL     & (\ref{basicType})\\     
FLOAT     & (\ref{standardProc})      & RESTRICTED & (\ref{standardProc})\\
HALT      & (\ref{standardProc})      & THIS     & (\ref{standardProc})\\  
HIGH      & (\ref{standardProc})      & SIZE     & (\ref{standardProc})\\  
HIGHEST   & (\ref{standardProc})      & TRUE     & (\ref{basicType})\\     
INC       & (\ref{standardProc})      & TRUNC    & (\ref{standardProc})\\    
INCL      & (\ref{standardProc})      & VAL      & (\ref{standardProc})\\
INTEGER   & (\ref{basicType})         
\end{tabular}                 
\end{center}
\echanged
      
\section{Constant declarations}
      
\label{constant}
   A constant declaration associates an identifier with a constant
   value. 

\begin{syntax}
\$ ConstantDeclaration = ident ``='' ConstExpression.\\
% 3rd Ed.
\$ ConstExpression = expression.
\end{syntax}
% 3rd Ed.
   A constant expression is an expression, which can be evaluated by a mere
   textual scan without actually executing the program. Its operands are
   constants. (see Ch. \ref{expression}).

   Examples of constant declarations are
% 3rd Ed.   
\begin{verbatim}
       N     =  100
       limit =  2*N-1
       all   = {0..WordSize-1}
       bound = MAX(INTEGER) - N
\end{verbatim}
      
\section{Type declarations}
   
\label{type}
   A data type determines a set of values which variables of that type
   may assume, and it associates an identifier with the type. In the
   case of structured types, it also defines the structure of
   variables of this type. 
\bchanged
   There are four different structures, namely arrays, records, sets 
   and relations.
\echanged

\bchanged
\begin{syntax}
\$ TypeDeclaration = ident ``='' type.\\
\$ type = SimpleType $|$ ArrayType $|$ RecordType $|$ SetType $|$\\
\$   \>RelationType $|$ PointerType $|$ ProcedureType $|$ SelectorType $|$\\
\$   \>ConstructorType.\\
\$ SimpleType = qualident $|$ enumeration $|$ SubrangeType.
\end{syntax}
\echanged

   Examples:
\begin{verbatim}
      Color = (red,green,blue)
      Index = [1..80]
      Card = ARRAY Index OF CHAR
      Node = RECORD key: CARDINAL;
               left,right: TreePtr
             END
      Tint = SET OF Color
      TreePtr = POINTER TO Node
      Function = PROCEDURE(CARDINAL):CARDINAL
\end{verbatim}
\bchanged
\begin{verbatim}
      String = ARRAY Index OF CHAR
      Item = RECORD code: Color;
               itemname: String;
               price: INTEGER;
               connectedTo: RELATION OF String;
             END
      Items = RELATION itemname OF Item
      Connections = RELATION OF RECORD from,to: String END
      ItemsInRange = SELECTOR ON (Items) WITH (CARDINAL,CARDINAL)
\end{verbatim}
\echanged
   
\subsection{Basic types}
      
\label{basicType}
   The following basic types are predeclared and denoted by standard 
   identifiers:
% 3rd Ed.   
   \begin{enumerate}
      \item INTEGER comprises the integers between MIN(INTEGER) and
      MAX\-(IN\-TE\-GER).

      \item CARDINAL comprises the integers between 0 and MAX\-(CARDINAL).
      
      \item BOOLEAN comprises the truth values TRUE or FALSE.
      
      \item CHAR denotes the character set provided by the used computer
      system.

      \item REAL (and LONGREAL) denote finite sets of real numbers.
 
      \item LONGINT comprises the integers between MIN(LONGINT) and
      MAX\-(LONG\-INT).
   \end{enumerate}

\subsection{Enumerations}                           

   An enumeration is a list of identifiers that denote the values
   which constitute a data type. These identifiers are used as
   constants in the program. They, and no other values, belong to this
   type. The values are ordered, and the ordering relation is defined
   by their sequence in the enumeration. The ordinal number of the
   first value is 0. 

\begin{syntax}
\$ enumeration = ``('' IdentList ``)''.\\
\$ IdentList = ident \{``,'' ident\}.
\end{syntax}

   Examples of enumerations:
\begin{verbatim}
       (red,green,blue)
       (club,diamond,heart,spade)
       (Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday)
\end{verbatim}

\subsection{Subrange types}
   
   A type T may be defined as a subrange of another, basic or
   enumeration type T1 (except REAL) by specification of the least and
   the highest value in the subrange.
                          
% 3rd Ed.
\begin{syntax}
\$ SubrangeType = [ident] ``['' ConstExpression ``..'' ConstExpression ``]''.
\end{syntax}

   The first constant specifies the lower bound, and must not be
   greater than the upper bound. The type T1 of the bounds is called
   the {\em base type} of T, and all operators applicable to operands
   of type T1 are also applicable to operands of type T. However, a
   value to be assigned to a variable of a subrange type must lie
   within the specified interval. 
% 3rd Ed.
   The base type can be specified by an identifier preceding the bounds.
   If it is omitted, and the lower bound is a non-negative
   integer, the base type of the subrange is taken to be CARDINAL; if
   it is a negative integer, it is INTEGER. 
   
   A type T1 is said to be {\em compatible} with a type T0, if it is
   declared either as T1 = T0 or as a subrange of T0, or if T0 is a
   subrange of T1, or if T0 and T1 are both subranges of the same
   (base) type. 
   
   Examples of subrange types:
\begin{verbatim}
       [0..N-1]
       ["A".."Z"]
       [Monday..Friday]
\end{verbatim}
             
\subsection{Array types}

\label{arrayType}
   An array is a structure consisting of a fixed number of components
   which are all of the same type, called the {\em component type}.
   The elements of the array are designated by indices, values
   belonging to the {\em index type}. The latter must be an
   enumeration, a subrange type, or one of the basic types BOOLEAN or
   CHAR. 

\begin{syntax}
\$ ArrayType = ARRAY SimpleType \{``,'' SimpleType\} OF type.
\end{syntax}
                             
   A declaration of the form 
\begin{verbatim}
      ARRAY T1, T2, ..., Tn OF T
\end{verbatim}
   \noindent with n index types T1 ... Tn must be understood as an 
   abbreviation for the declaration
\begin{verbatim}
      ARRAY T1 OF
        ARRAY T2 OF
          ...
           ARRAY Tn OF T
\end{verbatim}

   Examples of array types:
\begin{verbatim}
      ARRAY [0..N-1] OF CARDINAL
      ARRAY [1..10],[1..20] OF [0..99]
      ARRAY [-10..+10] OF BOOLEAN
      ARRAY WeekDay OF Color
      ARRAY Color OF WeekDay
\end{verbatim}

\subsection{Record types}
   
\label{recordType}
   A record type is a structure consisting of a fixed number of
   components of possibly different types. The record type declaration
   specifies for each component, called {\em field}, its type and an
   identifier which denotes the field. The scope of these field
   identifiers is the record definition itself, and they are also
   accessible within field designators (see \ref{operand}) refering to
   components of record variables, and within with statements. 
   
   A record type may have several variant sections, in which case the
   first field of the section is called the {\em tag field}. Its value
   indicates which variant is assumed by the section. Individual
   variant structures are identified by {\em case labels}. These
   labels are constants of the type indicated by the tag field.

\begin{syntax}
\$ RecordType = RECORD FieldListSequence END.\\
\$ FieldListSequence = FieldList \{``;'' FieldList\}.\\
\$ FieldList = [IdentList ``:'' type $|$\\
% 3rd Ed.
\$   \>CASE [ident] ``:'' qualident OF variant \{``$|$'' variant\}\\
\$   \>[ELSE FieldListSequence] END].\\
% 3rd Ed.
\$ variant = [CaseLabelList ``:'' FieldListSequence].\\
\$ CaseLabelList = CaseLabels \{``,'' CaseLabels\}.\\
\$ CaseLabels = ConstExpression [``..'' ConstExpression].
\end{syntax}
                                          
   Examples of record types:              
\begin{verbatim}
      RECORD day: [1..31];
        month: [1..12];
        year:  [0..2000]
      END

      RECORD
        name,firstname: ARRAY [0..9] OF CHAR;
        age: [0..99];
        salary: REAL
      END

      RECORD x,y: T0;
        CASE tag0: Color OF
          red: a: Tr1; b: Tr2|
          green: c: Tg1; d: Tg2|
          blue: e: Tb1; f: Tb2
        END;
        z: T0;
        CASE tag1: BOOLEAN OF
          TRUE: u,v: INTEGER|
          FALSE: r,s: CARDINAL
        END
      END
\end{verbatim}
         
   The example above contains two variant sections. The variant of the
   first section is indicated by the value of the tag field tag0, the
   one of the second section by the tag field tag1. 

\subsection{Set types}
                                                    
\label{setType}
   A set type defined as SET OF T comprises all sets of values of its
   base type T. This must be a subrange of the integers between 0 and
   N--1, or a (subrange of an) enumeration type with at most N values,
   where N is a small constant determined by the implementation,
   usually the computer's wordsize or a small multiple thereof.

\begin{syntax}
\$ SetType = SET OF SimpleType.
\end{syntax}

   The standard type BITSET is defined as follows, where W is a
   constant defined by the implementation, usually the word size of
   the computer. 
\begin{verbatim}
       BITSET = SET OF [0..W-1]
\end{verbatim}
   
\subsection{Pointer types}
   
\label{pointerType}
   Variables of a pointer type P assume as values pointers to
   variables of another type T. The pointer type P is said to be
   {\em bound} to T.
% 3rd Ed.
   A pointer value is generated by a call to an allocation procedure in
   a storage management module.

\begin{syntax}
\$ PointerType = POINTER TO type.
\end{syntax}
                                      
   Besides such pointer values, a pointer variable may assume the
   value NIL, which can be thought as pointing to no variable at all.
   
\subsection{Procedure types}
   
\label{procedureType}
   Variables of a procedure type T may assume as their value a
   procedure P. The (types of the) formal parameters of P must be the
   same as those indicated in the formal type list of T. The same
   holds for the result type in the case of a function procedure.
   
   {\small Restriction: P must not be declared local to another
   procedure, and neither can it be a standard procedure.}

\begin{syntax}
\$ ProcedureType = PROCEDURE [FormalTypeList].\\
\$ FormalTypeList = ``('' [[VAR] FormalType \\
\$    \> \{``,'' [VAR] FormalType\}] ``)'' [``:'' qualident].
\end{syntax}
   
   The standard type PROC denotes a parameterless procedure:
\begin{verbatim}
       PROC = PROCEDURE
\end{verbatim}
         
\subsection{Relation types}

   \bchanged 
   A relation type declaration specifies a structure consisting
   of elements of the same type, called the relation element type. The
   number of elements, called the cardinality of the relation, is not
   fixed. A relation with zero elements is called empty. The relation type
   declaration specifies the element type as well as the relation key. 

   The relation key defines a list of components of the relation element
   type which uniquely determines a relation element. An empty key
   component list is a synonym for an exhaustive element component list;
   in this case, a relation is just a set of relation elements. A relation
   key can only be specified if the relation element type is an array or
   record structure. A key component is either specified by a qualified
   identifier designating a record field, or by a constant expression
   designating an array component. Key components must not be part of a
   variant in a variant record structure. The type of a key component must
   be a simple type or a string. 

\begin{syntax}
\$ RelationType = RELATION [RelationKey] OF type.\\
\$ RelationKey = KeyComponent \{``,'' KeyComponent\}.\\
\$ KeyComponent = KeyDesignator \{KeySubDesignator\}.\\
\$ KeyDesignator = ident $|$ ``['' ConstExpList ``]''.\\
\$ KeySubDesignator = ``.'' ident $|$ ``['' ConstExpList ``]''.\\
\$ ConstExpList = ConstExpression \{``,'' ConstExpression\}.
\end{syntax}

   Examples of relation types:
\begin{verbatim}
       Address =    RECORD
                      street: String;
                      city: String;
                    END;
       AddrClass =  (office, stock);
       Company =    RECORD
                      companyname: String;
                      address: ARRAY AddressClass OF
                                 Address;
                      phonenumber: CARDINAL;
                    END
       Companies =  RELATION companyname, address[office].city OF 
                      Company
       Deliveries = RELATION itemname OF
                      RECORD
                        itemname: String;
                        name, city: String;
                        quantity: CARDINAL;
                      END;
\end{verbatim}
\echanged

\subsection{Selector types}

\label{SelectorType}
\bchanged
     Variables of a selector type T may assume as their values a selector
     S. The types of the formal parameters and the result type of S
     must be the same as those indicated in the formal type list of T. 

     Two selector types are compatible, if their formal parameter types and
     result types agree, and if their access restrictions are compatible. 

     Access restrictions are used in selector declarations  and  in  the 
     intention list of a transaction (see Ch. \ref{procedure}). 
     They define the set  of operations  applicable to selected relation 
     variables and persistent variables.

     The access symbol = restricts the use of these variables to expressions, 
     to range relations of FOR EACH statements and as parameters in the 
     standard relation handling procedures (see Ch. \ref{standardProc}). 
     The access symbols :=, :+, :--, :\& enable the use of 
     a  selected  variable as the left side of the  corresponding  relation 
     update operations. Defining no access restriction is synonymous to
     the full set of access symbols.
     If a selected relation variable is to be passed as
     a variable parameter, all access rights have to be specified.

     Access restriction A is called  a {\em restriction} of access restriction
     B, if A is a subset of B. Two access restrictions A and B are compatible,
     if A and B are equal.

\begin{syntax}
\$ SelectorType = SELECTOR [ON ``(''qualident``)''] [WITH TypeList]\\
\$  \>AccessRestriction [``:'' qualident].\\
\$ TypeList = ``('' FormalType \{``,'' FormalType\} ``)''.\\
\$ AccessRestriction = [FOR ``('' AccessRight \{``,'' AccessRight ``)''\}].\\
\$ AccessRight = ``:='' $|$ ``:+'' $|$ ``:--'' $|$ ``:\&'' $|$ ``=''.
\end{syntax}                                                         

     Example of a selector type:
\begin{verbatim}                                        
      ReadOnlyItems = SELECTOR ON (Items) FOR (=)
\end{verbatim}               
\echanged

\subsection{Constructor types}

\label{ConstructorType}
\bchanged
     Variables of a constructor type T may assume as their values a constructor
     C. The types of the formal parameters and the result type of C
     must be the same as those indicated in the formal type list of T. 

     Two constructor types are compatible, if their formal pararameter 
     types and result types agree.

\begin{syntax}
\$ ConstructorType = CONSTRUCTOR [ON TypeList] [WITH TypeList]``:'' qualident.
\end{syntax}                                                         

     Example of a constructor type:
\begin{verbatim}                                        
      ConnectionRule = CONSTRUCTOR ON (Items): Connections
\end{verbatim}               
\echanged

\section{Variable declarations}
        
\label{variable}
   Variable declarations serve to introduce  variables and associate
   them with a unique identifier and a fixed data type and structure.
   Variables whose identifiers appear in the same list all obtain the
   same type. 

\begin{syntax}
\$ VariableDeclaration = IdentList ``:'' type.
\end{syntax}
    
   The data type determines the set of values that a variable may
   assume and the operators that are applicable; it also defines the
   structure of the variable.

   Examples of variable declarations (see examples in Ch. \ref{type}):
\begin{verbatim}
       i,j: CARDINAL
       k: INTEGER
       p,q: BOOLEAN
       s: BITSET
       F: Function
       a: ARRAY Index OF CARDINAL
       w: ARRAY [0..7] OF
            RECORD ch: CHAR;
              count: CARDINAL
            END
       t: TreePtr
\end{verbatim}
\bchanged
\begin{verbatim}
       thispart: Item
       parts: Items
       oldparts: Items
       suppliers: Companies
       orders: Deliveries
       InRange: ItemsInRange
       adjacent: ConnectionRule
\end{verbatim}
\echanged

\section{Expressions}

\label{expression}
   Expressions are constructs denoting rules of computation for
   obtaining values of variables and generating new values by the
   application of operators. Expressions consist of operands and
   operators. Parentheses may be used to express specific associations
   of operators and operands. 

\subsection{Access expressions}
\label{AccessExpression}                           
                                                              
\bchanged
   Access expressions denote rules for accessing relation
   variables. Access expressions can be named and parameterized. 
   A parameter substitution is used to build new access expressions
   which can be stored in variables of type selector and constructor.

\begin{syntax}
\$ AccessExpression = SelectiveAccessExpression $|$ ConstructiveAccessExpression.\\ 
\$ SelectiveAccessExpression = ElementDenotation ``:''expression.\\
\$ ConstructiveAccessExpression = expression $|$\\
\$ \>expression OF ElementDenotation \{``,'' ElementDenotation\} ``:'' expression.\\
\$ ElementDenotation = EACH ident IN range.\\
\$ range = expression $|$ designator.
\end{syntax}

   There are selective and constructive access expressions.

   A selective access expression has the form
\begin{verbatim}
      EACH v IN rg: se
\end{verbatim}  
   It denotes the selection rule that refers to exactly those elements v
   of the range rg, that make the selection expression se of type BOOLEAN 
   true. The (lexical) scope of an element variable is the selection 
   expression se.
                                
   A constructive access expression has the form
\begin{verbatim}
      e OF EACH v1 IN r1, EACH v2 IN r2, ..., EACH vn IN rn: se
\end{verbatim}         
   It denotes the construction rule that evaluates the expression e for
   exactly those combinations of the elements v1, v2,\ldots, vn of the
   ranges r1, r2,\ldots, rn that fulfill the selection expression se.
   The (lexical) scope of the element variables are the expressions
   e and se.
\echanged  


\subsection{Selectors}
   
\label{selector}
\bchanged
     Selectors denote selective access expressions where the range 
     relation is a designator. They are introduced by selector declarations
     and have a type (see \ref{SelectorType} and \ref{SelectorDeclaration}).

     Selectors are used in relations (see \ref{relations}), in for
     statements (see \ref{for}), in the intention list of transactions (see
     Ch. \ref{procedure}), and as designators (see \ref{designators}). 
                                                             
\begin{syntax}
\$ selector = designator [``('' [designator] ``)'' [ActualParameters]].
\end{syntax}
     
     Let S be a selector declared as:
\begin{verbatim}
      SELECTOR S ON (RPar: RType) WITH (ParList) FOR (AccList): RType;
      BEGIN EACH r IN RPar: p(r,ParList) END S
\end{verbatim}
     
     Such a parameterized selector can be used to define new selectors by
     a (partial) parameter substitution:
\begin{itemize}

\item
     The substitution of the ON-parameter of S by a designator R, S(R),
     denotes a non-ON-parameterized selector SR, that is bound to R as 
     its range relation. That selector is equivalent to the declaration
\begin{verbatim}
      SELECTOR SR WITH (ParList) FOR (AccList): RType;
      BEGIN EACH r IN R: p(r,ParList) END SR
\end{verbatim}
                                                                 
\item
     The relational ON-parameter of a selector can also be substituted by 
     a selected relation variable denoted by any type-compatible
     (non-parameterized) selector [SRP]. The resulting selector, S([SRP]), 
     has as its access restriction the intersection of the access 
     restrictions of S and SRP.
                           
\item
     Substitution of the WITH-parameter list of S by actual parameters,
     S()(ActList), denotes a selector equivalent to the declaration
\begin{verbatim}
      SELECTOR SP ON (RPar: RType) FOR (AccList): RType;
      BEGIN EACH r IN RPar: pp(r) END SP
\end{verbatim}                          
      \noindent where pp is the predicate p after substitution of each
      occurence of the formal parameters by the current values of the
      actual parameters.

\item
      ON- and WITH-parameters can be substituted simultaneously: 
      S(R)(ActList) is an unparameterized selector equivalent to
\begin{verbatim}
      SELECTOR SRP FOR (AccList): RType;
      BEGIN EACH r IN R: pp(r) END SRP
\end{verbatim}                        
\end{itemize}
             
      A selector with an ON-parameter of type RType but without a WITH-parameter
      can be applied to a relation variable of type RType: R[SP] denotes a {\em
      selected relation variable}. For the special case of a non-parameterized
      selector the application is denoted by [SRP]. The designators R[SP], [SRP],
      [SP(R)] and [SR(P)] are synonymous. They denote a subvariable of R, 
      which is defined by the access expression         
\begin{verbatim}
      EACH r IN R: pp(r)
\end{verbatim}                                               
      A selected relation variable can only be used in a context 
      defined by the access restrictions (AccList) of the selector type.

      The interpretation of a selected relation variable depends on
      its actual context:
\begin{itemize}
\item
      If [SRP] is used in an expression it is synonymous to the relation
      expression
\begin{verbatim}
      RType{EACH r IN R: pp(r)}
\end{verbatim}
\item
      The semantics of assignments to selected relation variables are
      defined in \ref{assignment}.
\item        
      The substitution of a variable parameter in a procedure call by 
      a selected relation variable implies repeated
      evaluation of the access expression in the procedure or transaction.
\end{itemize}
       
      Examples of selectors and selected relation variables
      (see examples in Ch. \ref{SelectorDeclaration} together with their
      types in Ch. \ref{type} and \ref{variable}):
\begin{verbatim}
       InRange()(0,N)                  SELECTOR ON (Items): Items      
       InRange(parts)                  SELECTOR WITH
                                         (CARDINAL, CARDINAL): Items
       InRange([RedItems(oldparts)])   SELECTOR WITH
                                         (CARDINAL, CARDINAL): Items 
       [RedItems(parts)]               Items
       orders[OfParts()("Printer")]    Deliveries
       [InRange(oldparts)(0,k)]        Items
\end{verbatim}
\echanged       


\subsection{Constructors}         

\bchanged
\label{constructor}                                              
    Constructors denote access expression lists.
    They are introduced by constructor declarations and have a type
    that is determined by the constructor heading (see \ref{ConstructorType}
    and \ref{ConstructorDeclaration}).

    The use of constructors is restricted to relations and the intention
    list of transactions.

\begin{syntax}
\$ constructor = designator [ActualParameters [ActualParameters]].
\end{syntax}                                                       
                          
    Constructors can be generated by substituting formal
    parameters of existing constructors. The rules for subtitution are
    the same as those for selectors with the exception, that a 
    constructor may have more than one ON-parameter.
\echanged                                              

\subsection{Operands}

\label{operand}
\bchanged             
     Operands are denoted by literal constants,  i.e.  numbers, strings and 
     sets (see Ch. \ref{constant}), designators, aggregates or relations.
\echanged

\subsubsection{Designators}

\label{designators}
\bchanged
     A  designator  consists of an identifier referring  to  the  constant, 
     variable, procedure, transaction, selector or constructor to be 
     designated, or a selector enclosed in square brackets denoting a
     selected relation variable (see \ref{selector}).

\begin{syntax}
\$ designator = (qualident $|$ ``['' selector ``]'') \{ ``.'' ident $|$ ``['' ExpList ``]'' $|$ ``$\uparrow$''\}.\\
\$ ExpList = expression \{``,'' expression\}.
\end{syntax}   
\echanged
                              
   This identifier may possibly be qualified by module identifiers
   (see Ch. \ref{declarations} and \ref{module}),      
   and it may be followed by component selectors, if the
   designated object is an element of a structure. If the structure is
   an array A, then the designator A[E] denotes that component of A
   whose index is the current value of the expression E. The index
   type of A must be {\em assignment compatible} with the type of E
   (see\ \ref{assignment}). A designator of the form 
\begin{quote}
        A[E1,E2,\ldots,En] stands for  A[E1][E2]\ldots[En].
\end{quote}

\bchanged
   If the structure is a relation R declared by
\begin{quote}
        R: RELATION k1, k2,\ldots, kn OF ElementType 
\end{quote}
   then the designator R[E1,\ldots,En]
   denotes that element of R whose key component values are the
   current values of the selection expressions E1 to En. A variable
   designated in this way is called a selected element variable. The
   types of the selection expressions must be assignment compatible
   with the types of the key components k1,\ldots,kn identified by the 
   relation type. The type of a selected element variable is
   defined by the relation element type with the additional constraint
   that the values of the key components are restricted to the values
   of the selection expressions. This implies that the values of the
   key components of a selected element variable cannot be altered.
   Note also, that R[E1,\ldots,En] denotes an object of type ElementType
   only if an element with key value E1,E2,\ldots,En exists in R. Thus
   selected element variables may cause conflicts with type definitions
   and other constraints (see \ref{assignment}).
\echanged

   If the structure is a record R, then the designator R.f denotes the
   field f of R. The designator P\XOC denotes the variable which is
   referenced by the pointer P.
   
   If the designated object is a variable, then the designator refers
   to the variable's current value. If the object is a function
   procedure, a designator without parameter list refers to that
   procedure. If it is followed by a (possibly empty) parameter list,
   the designator implies an activation of the procedure and stands
   for the value resulting from its execution, i.e. for the
   ``returned'' value. The (types of these) actual parameters must
   correspond to the formal parameters as specified in the
   procedure's declaration (see Ch. \ref{procedure}). 

   Examples of designators (see examples in Ch. \ref{variable}):
\begin{verbatim}
       k                                            (INTEGER)
       a[i]                                         (CARDINAL)
       w[3].ch                                      (CHAR)        
       t^.key                                       (CARDINAL)
       t^.left^.right                               (TreePtr)
\end{verbatim}
\bchanged
\begin{verbatim}
       parts["Printer"]                             (Item)
       suppliers["Brown & Co","Zurich"].phonenumber (CARDINAL)
\end{verbatim}
\echanged
                              
\subsubsection{Aggregate expressions}
                          
\bchanged
   An aggregate must be either of type RECORD or type ARRAY. The
   identifier preceding the left bracket of an aggregate specifies the
   type of the aggregate. If an element of a relation or a component
   of an aggregate is an aggregate the type identifier preceding the
   aggregate can be omitted. 

   If the aggregate is of type ARRAY, all components must be assignment
   compatible with the array element type and the number of components
   must be the same as the number of array elements: if A=ARRAY
   [i..j] OF T and A\{E0,...,En\} is an aggregate then n=j--i and the
   component Ek corresponds to the array element with the index [i+k].

   If the aggregate is of type RECORD the components and the record
   fields are associated in the sequence of their declaration. The
   component expressions must be assignment compatible with their
   corresponding record fields. Components associated
   with tag fields must be constant expressions (see Ch. 5). Records
   containing variants without tag fields cannot be built with an
   aggregate.  

\begin{syntax}           
\$ aggregate = [qualident] ``\{'' ExpList ``\}''.\\
\end{syntax}

   Examples of aggregates:
\begin{verbatim}
       Item{green,"Printer",999, {"Computer"}}      (Item)
       Node{25,t^.left,NIL}                         (Node)
\end{verbatim}
\echanged

\subsubsection{Relation expressions}
                 
\bchanged
\label{relations}                         
     RType\{\} denotes the empty relation of type RType.  
                                   
     Relation expressions denote sets of relation elements; relation
     elements can be given by
\begin{itemize}
\item
     selective or constructive access expressions as defined in
     \ref{AccessExpression},
\item
     unparameterized selectors denoting elements defined by 
     the selective access expressions of their bodies,
\item
     unparameterized constructors denoting the access expression list
     of their bodies.
\end{itemize}    

     Note, that constructive access expressions include the case that
     a relation element is given by an expression that evaluates a single
     value of the relation's element type.

     If several relation elements are specified, they all have to be of
     the same type, which is the relation element type.
                    
\begin{syntax}
\$ relation = qualident ``\{'' AccessExpressionList ``\}''.\\
\$ AccessExpressionList = [AccessExpression \{ ``,'' AccessExpression \}].
\end{syntax} 

   Examples of relations:
\begin{verbatim}
      Items{thispart}                               (Items)
      Items{EACH p IN parts:p.code = red}           (Items)
      Items{InRange(parts)(0,7)}                    (Items)
      Deliveries{EACH o IN orders: SOME p IN parts
                   (o.itemname = p.itemname)}       (Deliveries)
      Items{EACH p IN parts: p.code = thispart.code,
            thispart}                               (Items)
      Items{{p.code,p.itemname,100,p.connectedTo} OF
            EACH p IN oldparts: p.price<1000}       (Items)
      Connections{TransConn(parts)}                 (Connections)
\end{verbatim}
\echanged
                           
\subsection{Operators}
       
\label{operators}
   The syntax of expressions specifies operator precedences according
   to four classes of operators. The operators NOT, 
   \bchanged SOME and ALL \echanged have
   the highest precedence, followed by the so-called multiplying
   operators, then the so-called adding operators, and finally, with
   the lowest precedence, the relational operators. Sequences of
   operators of the same precedence are executed from left to right.

\bchanged
\begin{syntax}
% 3rd Ed.
\$ expression = SimpleExpression [RelOperator SimpleExpression] $|$\\
\$    \>constructor $|$ selector.\\
\$ RelOperator = ``='' $|$ ``\#'' $|$ ``$<>$'' $|$ ``$<$'' $|$ ``$<=$'' $|$ ``$>$'' $|$ ``$>=$'' $|$ IN.\\
\$ SimpleExpression = [``+'' $|$ ``--''] term \{AddOperator term\}.\\
\$ AddOperator = ``+'' $|$ ``--'' $|$ OR.\\
\$ term = factor \{MulOperator factor\}.\\
\$ MulOperator = ``$*$'' $|$ ``/'' $|$ DIV $|$ MOD $|$ AND $|$ ``\&''.\\
\$ factor = number $|$ string $|$ set $|$ designator [ActualParameters] $|$\\
\$   \>relation $|$ aggregate $|$ QuantifiedExpression $|$\\
\$   \>``('' expression ``)'' $|$ NOT factor.\\
\$ ActualParameters = ``('' [ExpList] ``)''.\\
\$ set = [qualident] ``\{'' [element \{``,'' element\}] ``\}''.\\
\$ element = expression [``..'' expression].\\
\$ QuantifiedExpression = (SOME $|$ ALL) ident IN expression predicate.\\
\$ predicate = ``('' expression ``)'' $|$ QuantifiedExpression.
\end{syntax}
\echanged
                                              
   The available operators are listed in the following tables. In
   some instances, several different operations are designated by the
   same operator symbol. In these cases, the actual operation is
   identified by the types of the operands.

\subsubsection{Arithmetic operators}
              
\begin{center}
\begin{tabular}{|l|l|}                       
\hline
symbol & operation\\
\hline
+      & addition\\
--    & subtraction\\
$*$    & multiplication\\
/      & real division\\
DIV    & integer division\\
MOD    & modulus\\
\hline
\end{tabular}
\end{center}

   These operators (except /) apply to operands of type INTEGER,
   CARDINAL, or subranges thereof. Both operands must be either of
   type CARDINAL or a subrange with base type CARDINAL, in which case
   the result is of type CARDINAL, or they must both be of type
   INTEGER or a subrange with base type INTEGER, in which case the
   result is of type INTEGER. 
   
   The operators +, --, and * also apply to operands of type REAL. In
   this case, both operands must be of type REAL, and the result is
   then also of type REAL. The division operator / applies to REAL
   operands only. When used as operators with a single operand only, --
   denotes sign inversion and + denotes the identity operation. Sign
   inversion applies to operands of type INTEGER or REAL. The
   operations DIV and MOD are defined by the following rules:
   \begin{quotation}
       x DIV y is equal to the truncated quotient of x/y

       x MOD y is equal to the remainder of the division x DIV
       y (for y $>$ 0)

       x = (x DIV y)*y+ (x MOD y)
   \end{quotation} 
   
\subsubsection{Logical operators}
   
   \begin{center}
   \begin{tabular}{|l|l|}
   \hline
   symbol & operation\\
   \hline
   OR     & logical disjunction\\
   AND    & logical conjunction\\
   NOT    & negation\\
   \hline
   \end{tabular}
   \end{center}

   These operators apply to BOOLEAN operands and yield a BOOLEAN
   result.

   \begin{center} 
   \begin{tabular}{lll}
       p OR q   & means & ``if p then TRUE, otherwise q''\\
       p AND q  & means & ``if p then q, otherwise FALSE''
   \end{tabular}
   \end{center}

\bchanged
   Quantifiers apply to operands of type RELATION and BOOLEAN and
   yield a BOO\-LEAN result. 

\begin{center}
\begin{tabular}{|l|l|}
\hline   
symbol & operation\\
\hline
SOME   & existential quantification\\
ALL    & universal quantification\\
\hline
\end{tabular}
\end{center}

     The  expression in a quantified expression must be of  type  RELATION. 
     The  expression  in  a predicate must  be  of  type  BOOLEAN.  Element 
     variables   in  quantified  expressions  are  called   bound   element 
     variables.  The  scope of a bound element variable is  the  subsequent 
     predicate,  its  type is the element type of the  subsequent  relation 
     expression.

     SOME r IN R (exp) is true,  if some element r in the relation R  makes 
     the expression exp true.  Analogously ALL r IN R (exp) is true, if all 
     elements r in R fulfill the selection expression exp.
\echanged
   
\subsubsection{Set operators}

\begin{center}
\begin{tabular}{|l|l|}
\hline
symbol & operation\\
\hline
+      & set union\\
--    & set difference\\
$*$    & set intersection\\
/      & symmetric set difference\\
\hline
\end{tabular}
\end{center}

   These operations apply to operands of any set type and yield a
   result of the same type.
\begin{verbatim}
      x IN (s1 + s2)    iff     (x IN s1) OR (x IN s2)
      x IN (s1 - s2)    iff     (x IN s1) AND NOT (x IN s2)
      x IN (s1 * s2)    iff     (x IN s1) AND (x IN s2)
      x IN (s1 / s2)    iff     (x IN s1) # (x IN s2)
\end{verbatim}
   
\subsubsection{Relational operators}

   Relational operators yield a BOOLEAN result. They apply to the
   basic types INTEGER, CARDINAL, BOOLEAN, CHAR, REAL, to
   enumerations, and to subrange types. 
   
\begin{center}
\begin{tabular}{|l|l|}
\hline   
symbol & relation\\
\hline
 =     & equal\\
\#    & unequal\\
$<$    & less\\
$<=$   & less or equal  (set inclusion)\\
$>$    & greater\\
$>=$   & greater or equal  (set inclusion)\\
 IN    & contained in  (membership)\\
\hline
\end{tabular}
\end{center}
   
   The relational operators = and \# also apply to sets and pointers.
   If applied to sets, $<=$ and $>=$ denote (improper) inclusion. 
\bchanged 
   The relational operators  =, \#, $<$, $<=$, $>$, $>=$ may also be used to
   compare arrays of type string (see Ch.\ \ref{vocabulary}), and then denote
   alphabetical ordering according to the underlying character set. A
   string of length n1 can be compared with a string variable of
   length n2 $>$ n1. In this case the string value is extended with a
   null character (0C) which will be the last character to be
   compared. 

   The relational operators =, \#, $<$, $<=$, $>$, $>=$ may also be used to
   compare values of relation type, and then denote relation equality
   or inclusion. The value of the expression 
\begin{verbatim}
      r1 <= r2
\end{verbatim}
\noindent where r1, r2 are relation expressions is equal to the value of the
   quantified expression 
\begin{verbatim}
      ALL v1 IN r1 SOME v2 IN r2 (v1.key = v2.key).
\end{verbatim}
\noindent where v1.key=v2.key stands for a conjunction of comparisons of the
   key attributes.

   The relational operator IN denotes set or relation membership. In
   an expression of the form x IN e, the expression e must be of type
   SET OF T, where T is (compatible with) the type of x, or the
   expression e must be of relation type and x of its element type. 
\echanged

   Examples of expressions (refer to examples in Ch. \ref{variable}): 
\begin{verbatim}
      1980                                   (CARDINAL)
      k DIV 3                                (INTEGER)
      NOT p OR q                             (BOOLEAN)
      (i+j) * (i-j)                          (CARDINAL)
      s - {8,9,13}                           (BITSET)
      a[i] + a[j]                            (CARDINAL)
      a[i+j] * a[i-j]                        (CARDINAL)
      (0< = k) & (k<100)                     (BOOLEAN)
      t^.key = 0                             (BOOLEAN)
      {13..15} <= s                          (BOOLEAN)
      i IN {0,5..8, 15}                      (BOOLEAN)
\end{verbatim}
\bchanged  
\begin{verbatim}
      SOME p IN parts (p.code = red)         (BOOLEAN)
      [RedParts] <=
      Items{EACH p IN parts: p.price < 100}  (BOOLEAN)
      thispart IN parts                      (BOOLEAN)
\end{verbatim}                                                     
\echanged
   
\section{Statements}

   Statements denote actions. There are elementary and structured
   statements. Elementary statements are not composed of any parts
   that are themselves statements. They are the assignment, the
   procedure call, and the return and exit statements. Structured
   statements are composed of parts that are themselves statements.
   These are used to express sequencing, and conditional, selective,
   and repetitive execution. 

\begin{syntax}
\$ statement = [assignment $|$ ProcedureCall $|$\\
\$   \>IfStatement $|$ CaseStatement $|$ WhileStatement $|$\\
\$   \>RepeatStatement $|$ LoopStatement $|$ ForStatement $|$\\
\$   \>WithStatement $|$ EXIT $|$ RETURN [expression]].
\end{syntax}

   A statement may also be empty, in which case it denotes no action.
   The empty statement is included in order to relax punctuation rules
   in statement sequences.

\subsection{Assignments}                                               

\label{assignment}
   The assignment serves to replace the current value of a variable by
   a new value indicated by an expression. The assignment operator is
   written as ``:='' and pronounced as ``becomes''.

\bchanged
\begin{syntax}
\$ assignment = designator UpdateOperator expression.\\
\$ UpdateOperator = ``:+'' $|$ ``:--'' $|$ ``:\&'' $|$ ``:=''.
\end{syntax}
\echanged

   The designator to the left of the assignment operator denotes a
   variable. After an assignment is executed, the variable has the
   value obtained by evaluating the expression. The old value is lost
   (overwritten). The type of the variable must be assignment
   compatible with the type of the expression. Operand types are said
   to be {\em assignment compatible}, if either they are compatible or
   both are INTEGER or CARDINAL or subranges with base types INTEGER
   or CARDINAL. 
   
   A string of length n1 can be assigned to a string variable of
   length n2$>$n1. In this case, the string value is extended with a
   null character (0C). 
% 3rd Ed.
   A string of length 1 is compatible with the type CHAR.

\bchanged
     A constructor of type T1 can be assigned to a constructor of type
     T2 iff their formal parameter types and result types agree.
     The same holds for selectors and selector variables with the additional
     constraint, that the access restrictions of T2 have to be a restriction
     of the access restrictions of T1.

     Assignments that update a relation variable rel of type RType by a
     relation expression rex, using one of the relation update
     operators, :+, :--, :\&, are equivalent to assignments using the
     assignment operator, :=, and a more complicated relation
     expression. 

   Relation insertion:
\begin{verbatim}
      rel:+ rex
\end{verbatim}
   \noindent is equivalent to
\begin{verbatim}
      rel:= RType{EACH r IN rel: TRUE,
                  EACH x IN rex: NOT SOME r IN rel (x.key=r.key)}.
\end{verbatim}

   Relation deletion:
\begin{verbatim}
      rel:- rex
\end{verbatim}
   \noindent is equivalent to

\begin{verbatim}
      rel:= RType{EACH r IN rel: NOT SOME x IN rex (r.key=x.key)}
\end{verbatim}

   Relation replacement:
\begin{verbatim}
      rel:& rex
\end{verbatim}
   \noindent is equivalent to
\begin{verbatim}
      rel:= RType{EACH r IN rel: NOT SOME x IN rex (r.key=x.key),
                  EACH x IN rex: SOME r IN rel (x.key=r.key)} 
\end{verbatim}
     
   The expressions x.key=y.key here stand for a conjunction of
   comparisons of the respective key attributes.
   
   The execution of an assignment to a selected relation variable 
   (see \ref{selector})
\begin{verbatim}
      R[SP]:= rex
\end{verbatim}         
   \noindent is intended to meet the following two constraints: The
   value of the selected relation variable after the assignment becomes
   equal to the relation expression, rex, while the value of the 
   non-selected rest of variable R remains unchanged. Note that, due
   to constraint violations, a selective assignment may not be executable.

   The assignment to a selected element variable (see \ref{designators})
   is a special case of selective relation assignment.

   The standard procedure RESTRICTED (see~\ref{standardProc}) allows to
   detect violations of a selector or a key constraint that occured 
   during relation insertion, deletion, replacement or assignment.
\echanged
                     
   Examples of assignments:
\begin{verbatim}
        i:= k
        p:= i = j
        j:= log2(i+j)    
        F:= log2
        s:= {2,3,5,7,11,13}
        a[i]:= (i+j) * (i-j)
        t^.key:= i
        w[i+1].ch:= "A"  
\end{verbatim}
\bchanged      
\begin{verbatim}
        adjacent:= DirConn
        parts := Items{EACH p IN oldparts: p.price>k}
        parts :- Items{EACH p IN parts: p.code=red}
        parts :& Items{thispart}
        parts[RedItems] := oldparts
        [InRange(oldparts)(0,k)] := Items{}
        oldparts := Items{} 
\end{verbatim}
\echanged
                                           
\subsection{Procedure calls }

\label{procedureCall}
   A procedure call serves to activate a procedure or transaction. The
   procedure call may contain a list of actual parameters which are
   substituted in place of their corresponding formal parameters
   defined in the procedure declaration (see Ch. \ref{procedure}). The
   correspondence is established by the positions of the parameters in
   the lists of actual and formal parameters respectively. There exist
   two kinds of parameters: {\em variable} and {\em value parameters}.
   
   In the case of variable parameters, the actual parameter must be a
   designator denoting a variable. If it designates a component of a
   structured variable, the selector is evaluated when the
   formal/actual parameter substitution takes place, i.e. before the
   execution of the procedure. If the parameter is a value parameter,
   the corresponding actual parameter must be an expression. This
   expression is evaluated prior to the procedure activation, and the
   resulting value is assigned to the formal parameter which now
   constitutes a local variable. The types of corresponding actual and
   formal parameters must be compatible in the case of variable
   parameters and assignment compatible in the case of value
   parameters. 

\begin{syntax}
\$ ProcedureCall = designator [ActualParameters].
\end{syntax}
   
   Examples of procedure calls:
\begin{verbatim}
      Read(i)  
      Write(j*2+1,6)
      INC(a[i])
\end{verbatim}
   
\subsection{Statement sequences}

   Statement sequences denote the sequence of actions specified by the
   component statements which are separated by semicolons. 

\begin{syntax}
\$ StatementSequence = statement \{``;'' statement\}.
\end{syntax}
                                                           
\subsection{If statements}

\begin{syntax}
\$ IfStatement = IF expression THEN StatementSequence\\
\$   \>\{ELSIF expression THEN StatementSequence\}\\
\$   \>[ELSE StatementSequence] END.
\end{syntax}

   The expressions following the symbols IF and ELSIF are of type
   BOOLEAN. They are evaluated in the sequence of their occurrence,
   until one yields the value TRUE. Then its associated statement
   sequence is executed. If an ELSE clause is present, its associated
   statement sequence is executed if and only if all Boolean
   expressions yielded the value FALSE. 
   
   Example:
\begin{verbatim}
      IF (ch>="A") & (ch<="Z") THEN ReadIdentifier
      ELSIF (ch>="0") & (ch<="9") THEN ReadNumber
      ELSIF ch = '"' THEN ReadString ('"')
      ELSIF ch = "'" THEN ReadString ("'")
      ELSE SpecialCharacter
      END
\end{verbatim}
   
\subsection{Case statements}

   Case statements specify the selection and execution of a statement
   sequence according to the value of an expression. First the case
   expression is evaluated, then the statement sequence is executed
   whose case label list contains the obtained value. The type of the
   case expression must be a basic type (except REAL), an enumeration
   type, or a subrange type, and all labels must be compatible with
   that type. Case labels are constants, and no value must occur more
   than once. If the value of the expression does not occur as a label
   of any case, the statement sequence following the symbol ELSE is
   selected.  

\begin{syntax}
\$ CaseStatement = CASE expression OF case \{``$|$'' case\}\\
\$   \>[ELSE StatementSequence] END.\\
% 3rd Ed.
\$ case = [CaseLabelList ``:'' StatementSequence].
\end{syntax}
              
   Example:
\begin{verbatim}
      CASE i OF
       0:p:= p OR q; x:= x+y|
       1:p:= p OR q; x:= x-y|
       2:p:= p AND q; x:= x*y
      END
\end{verbatim}
   
\subsection{While statements}
   
   While statements specify the repeated execution of a statement
   depending on the value of a Boolean expression. The expression is
   evaluated before each subsequent execution of the statement
   sequence. The repetition stops as soon as this evaluation yields
   the value FALSE. 

\begin{syntax}
\$ WhileStatement = WHILE expression DO StatementSequence END.
\end{syntax}
                    
   Examples:
\begin{verbatim}
      WHILE j>0 DO
        j:= j DIV 2; i:= i+1
      END
      WHILE i#j DO
        IF i>j THEN i:= i-j
        ELSE j:= j-i
        END
      END
      WHILE (t#NIL) & (t^.key#i) DO
        t:= t^.left
      END
\end{verbatim}
   
\subsection{Repeat statements}

   Repeat statements specify the repeated execution of a statement
   sequence depending on the value of a Boolean expression. The
   expression is evaluated after each execution of the statement
   sequence, and the repetition stops as soon as it yields the value
   TRUE. Hence, the statement sequence is executed at least once.

\begin{syntax}
\$ RepeatStatement = REPEAT StatementSequence UNTIL expression.
\end{syntax}
   
   Example:
\begin{verbatim}
      REPEAT 
        k:= i MOD j; i:= j; j:= k
      UNTIL j = 0
\end{verbatim}
   
\subsection{For statements}

\label{for}
   The for statement indicates that a statement sequence is to be
   repeatedly executed while a progression of values is assigned to a
   variable. This variable is called the {\em control variable}
   of the for statement. It cannot be a component of a structured
   variable, it cannot be imported, nor can it be a parameter. Its
   value should not be changed by the statement sequence. 

\bchanged
\begin{syntax}
\$ ForStatement = FOR ControlSection DO StatementSequence END.\\
\$ ControlSection = ident ``:='' expression TO expression [BY ConstExpression] $|$\\
\$ \>SelectiveAccessExpression $|$ ident ``:'' selector.
\end{syntax}
\echanged

   The for statement                                         
\begin{verbatim}
      FOR v := A TO B BY C DO SS END
\end{verbatim}
\noindent expresses repeated execution of the statement sequence SS with v 
   successively assuming the values A, A+C, A+2C, ..., A+nC, where
   A+nC is the last term not exceeding B. v is called the control
   variable, A the starting value, B the limit, and C the increment. A
   and B must be assignment compatible with v; C must be a constant of
   type INTEGER or CARDINAL. If no increment is specified, it is
   assumed to be 1. 

\bchanged
   If the control section is given by a selective access expression, 
   the element variable is called control element variable. 
   If a selector is used, its element variable is renamed by the
   identifier preceding the selector; the selector has to be unparameterized.
   The scope of a control element variable is the subsequent statement 
   sequence.

   The  control section is evaluated only once to determine all  elements 
   e1, e2,\ldots, en  in  the range relation that  fulfill the  
   selection expression. The iteration order of these elements is system 
   defined.

   The  control element variable obeys the same  rules  as  a  selected 
   relation element variable (see \ref{designators}). The value of the
   control element variable may be changed if the access restriction of the
   range relation variable contains the access right :\&.
                                             
   Examples:   
\begin{verbatim}
      FOR i := 1 TO 80 DO j:= j+a[i] END
      FOR i := 80 TO 2 BY -1 DO a[i] := a[i-1] END
      FOR EACH o IN orders:
        SOME p IN parts ((p.itemname=o.itemname) AND (p.code=red)) DO
          i := i + p.quantity;
      END;
      FOR EACH item: RedItems(parts) DO
        item.price:= item.price DIV 2;
      END
\end{verbatim}                   
\echanged
   
\subsection{Loop statements}
   
\label{loop}
   A loop statement specifies the repeated execution of a statement
   sequence. It is terminated by the execution of any exit statement
   within that sequence. 

\begin{syntax}
\$ LoopStatement = LOOP StatementSequence END.
\end{syntax}
   
   Example:
\begin{verbatim}
      LOOP
        IF t1^.key> x THEN t2:= t1^.left; p:= TRUE
        ELSE t2:= t1^.right; p:= FALSE
        END;
        IF t2 = NIL THEN
          EXIT
        END;
        t1:= t2
      END
\end{verbatim}

   While, repeat, and for statements can be expressed by loop
   statements containing a single exit statement. Their use is
   recommended as they characterize the most frequently occurring
   situations where termination depends either on a single condition
   at either the beginning or end of the repeated statement sequence,
   or on reaching the limit of an arithmetic progression. The loop
   statement is, however, necessary to express the continuous
   repetition of cyclic processes, where no termination is specified.
   It is also useful to express situations exemplified above. Exit
   statements are contextually, although not syntactically bound to
   the loop statement which contains them. 
   
\subsection{With statements}

   The with statement specifies a record variable and a statement
   sequence. In these statements the qualification of field
   identifiers may be omitted, if  they are to refer to the variable
   specified in the With clause. If the designator denotes a component
   of a structured variable, the selector is evaluated once (before
   the statement sequence). The with statement opens a new scope.

\begin{syntax}
\$ WithStatement = WITH designator DO StatementSequence END.
\end{syntax}

   Example:
\begin{verbatim}
      WITH t^ DO     
        key:= 0; left:= NIL; right:= NIL
      END
\end{verbatim}

\subsection{Return and exit statements}

   A return statement consists of the symbol RETURN, possibly followed
   by an expression. It indicates the termination of a procedure (or a
   module body), and the expression specifies the value returned as
   result of a function procedure. Its type must be assignment
   compatible with the result type specified in the procedure heading
   (see Ch. \ref{procedure}). 
   
   Function procedures require the presence of a return statement
   indicating the result value. There may be several, although only
   one will be executed. In proper procedures, a return statement is
   implied by the end of the procedure body. An explicit return
   statement therefore appears as an additional, probably exceptional
   termination point. 
   
   An exit statement consists of the symbol EXIT, and it specifies
   termination of the enclosing loop statement and continuation with
   the statement following that loop statement (see \ref{loop}). 

\section{Selector declarations}

\label{SelectorDeclaration}
\bchanged 
     Selector declarations introduce selectors.  They consist of a  heading 
     defining  the name and the type of the selector and a body  containing 
     a selective access expression with a designator as its range relation.
     Selectors are  used to define value-based constraints on relation
     variables or to restrict access rights on relations.
   
     If  the ON-parameter is omitted, the selector is bound  to the 
     global relation variable of the reference type, which is given by 
     the range relation in the selector body.  If the ON-parameter 
     is specified,  it has to be used as the range relation.
     The  WITH-parameters  have  to  be  value  parameters  and  can  be 
     substituted to derive new specialized selectors. 

     A selector is called unparameterized, if neither ON- nor 
     WITH-parameters are specified.   
     Access restrictions are explained in \ref{SelectorType} and are 
     part of the selector type.
     The  scope  rules  for  selector declarations  are  the  same  as  for 
     procedure declarations.
   
\begin{syntax}
\$ SelectorDeclaration = SelectorHeading ``;'' SelectorBlock ident.\\
\$ SelectorHeading = SELECTOR ident [OnParameter]\\
\$ \> [WITH ParameterList] AccessRestriction [``:'' qualident].\\
\$ SelectorBlock  = BEGIN EACH ident IN designator ``:'' expression END.\\
\$ OnParameter = ON ``('' ident ``:'' FormalType ``)''.\\
\$ ParameterList = ``('' FPSection \{``;'' FPSection\} ``)''.\\
\end{syntax}
   
     Examples of selector declarations:
\begin{verbatim}
      SELECTOR RedParts: Items;
      BEGIN EACH r IN parts: r.code=red END RedParts

      SELECTOR RedItems ON (rel: Items);
      BEGIN EACH r IN rel: r.code=red END RedItems

      SELECTOR ColoredItems ON(rel: Items) WITH (color: Color);
      BEGIN EACH r IN rel: r.code=color END ColoredItems
          
      SELECTOR OfParts ON (orders: Deliveries) WITH (s: String);
      BEGIN EACH o IN orders: o.itemname=s END OfParts    
\end{verbatim}
\echanged

\section{Constructor declarations}
                                              
\label{ConstructorDeclaration}
\bchanged               
     Constructor declarations introduce constructors. They consist of a heading 
     defining  the name and the type of the constructor and a body consisting
     of a list of access expressions. Constructors are
     used to intentionally define relations. 
     Constructor declarations can be recursive (with a fixed-point semantic).

     ON-parameters have to be of type relation. They can be substituted
     by (selected) relation variables or unparameterized constructors, i.e. 
     their substitution yields a new constructor
     with references to global or persistent relations. 
     The  WITH-parameters  have  to  be  value  parameters  and  can  be 
     substituted to  derive  new specialized constructors
     (see \ref{constructor}).

     If neither WITH- nor ON-parameters are defined, the constructor is
     called unparameterized. Unparameterized constructors can be evaluated
     through relation expressions (see \ref{relations}).

     The  scope  rules  for  constructor declarations  are  the  same  as  for 
     procedure declarations.
   
\begin{syntax}
\$ ConstructorDeclaration = ConstructorHeading ``;'' ConstructorBlock ident.\\
\$ ConstructorHeading = CONSTRUCTOR ident [ON ParameterList]\\
\$ \> [WITH ParameterList] ``:'' qualident.\\
\$ ConstructorBlock  = BEGIN AccessExpressionList END.
\end{syntax}
   
     Examples of constructors:
\begin{verbatim}          
      CONSTRUCTOR DirConn ON (P: Items): Connections;
      BEGIN
        {a.itemname, c} OF
          EACH a IN P, EACH c IN a.connectedTo: TRUE
      END DirConn
          
      CONSTRUCTOR TransConn ON (P: Items): Connections;
      BEGIN            
        DirConn(P),
        {a.from, b.to} OF
          EACH a IN {DirConn(P)}, 
            EACH b IN {TransConn(P)}: a.to = b.from
     END TransConn
\end{verbatim}
\echanged

\section{Procedure declarations}
          
\label{procedure}
   Procedure declarations consist of a {\em procedure heading}
   and a block which is said to be the {\em procedure body}. The
   heading specifies the procedure identifier and the {\em formal
   parameters}. The block contains declarations and statements. The
   procedure identifier is repeated at the end of the procedure
   declaration. 
   
\bchanged
   Procedures can be divided into two classes, namely {\em ordinary
   procedures} and {\em transaction procedures}. The latter are marked
   by the symbol TRANSACTION instead of PROCEDURE. 
\echanged
   
   There are two kinds of procedures, namely {\em proper procedures}
   and {\em function procedures}. The latter are activated by a
   function designator as a constituent of an expression, and yield a
   result that is an operand in the expression. Proper procedures are
   activated by a procedure call. The function procedure is
   distinguished in the declaration by indication of the type of its
   result following the parameter list. Its body must contain a RETURN
   statement which defines the result of the function procedure.
   
   All constants, variables, types, modules and procedures declared
   within the block that constitutes the procedure body are {\em
   local} to the procedure. The values of local variables, including
   those defined within a local module, are undefined upon entry to
   the procedure. Since procedures may be declared as local objects
   too, procedure declarations may be nested. Every object is said to
   be declared at a certain {\em level} of nesting. If it is declared 
   local to a procedure at level k, it has itself level k+1. Objects
   declared in the module that constitutes a compilation unit (see Ch.
   \ref{compilation}) are defined to be at level 0.
   
   In addition to its formal parameters and local objects, also the
   objects declared in the environment of the procedure are known and
   accessible in  the procedure (with the exception of those objects
   that have the same name as objects declared locally). 
   
   The use of the procedure identifier in a call within its
   declaration implies recursive  activation  of the procedure.

\bchanged
\begin{syntax}
\$ ProcedureDeclaration = ProcedureHeading ``;'' block ident.\\
\$ ProcedureHeading = (PROCEDURE $|$ TRANSACTION) ident [FormalParameters].\\
\$ block = \{declaration\} [USING IntentionList]\\
\$  \>[BEGIN StatementSequence] END.\\
\$ declaration = CONST \{ConstantDeclaration ``;''\} $|$\\
\$   \>TYPE \{TypeDeclaration ``;''\} $|$\\
\$   \>VAR \{VariableDeclaration ``;''\} $|$\\
\$   \>SelectorDeclaration ``;'' $|$ ConstructorDeclaration $|$ \\
\$   \>ProcedureDeclaration ``;'' $|$ ModuleDeclaration ``;''.  \\
\$ IntentionList = Intention \{ ``;'' Intention\}.\\
\$ Intention = expression \{``,'' expression\} AccessRestriction.
\end{syntax}
   
   Transaction procedures are the only means of interacting with the
   database. They consist of a sequence of operations on persistent
   variables and have to be  regarded as atomic with respect to their
   effects on the database. The  property of atomicity does not hold
   for variables other than persistent variables.

   Under some scheduling strategies transaction procedures are subject
   to automatic restarts. A restart does not reset the global
   variables and parameters used in the transaction procedures. In the case
   of nested or recursive calls of transaction procedures, the entire
   transaction is ``flattened'', i.e. inner calls are
   treaded as ordinary procedure calls.

   An intention list may be used to denote the set of persistent  variables 
   accessed  during execution of a transaction procedure.  The  intention 
   list  is  a  means  for  passing  additional  information  about   the 
   transaction's  behavior  to the compiler.  The compiler may  use  this 
   information for some optimization.                           

   Access to a persistent object is defined by its designator and (a 
   superset of) the needed access rights. 
   If a designator is denoted by a selector of type T,  the 
   access restriction in the intention list has to be a restriction of T.
   An unparameterized constructor C may be used to request read access to
   all (sub-)relations needed to evaluate C.
\echanged
   
   
\subsection{Formal parameters}
                                         
   Formal parameters are identifiers which denote actual parameters
   specified in the procedure call. The correspondence between formal
   and actual parameters  is established when the procedure is called.
   There are two kinds of parameters, namely {\em value} and {\em
   variable parameters}. The kind is indicated in the formal parameter
   list. Value parameters stand for local variables to which the
   result of the evaluation of the corresponding actual parameter is
   assigned as initial value. Variable parameters correspond to actual
   parameters that are variables, and they stand for these variables.
   Variable parameters are indicated by the symbol VAR, value
   parameters by the absence of the symbol VAR. 
   
   Formal parameters are local to the procedure, i.e. their scope is
   the program text which constitutes the procedure declaration.

\begin{syntax}
\$ FormalParameters = ``('' [FPSection \{``;'' FPSection\}] ``)'' [``:'' qualident].\\
\$ FPSection = [VAR] IdentList ``:'' FormalType.\\
\$ FormalType = [ARRAY OF] qualident.
\end{syntax}
   
   The type of each formal parameter is specified in the parameter
   list. In the case of variable parameters it must be compatible with
   its corresponding actual parameter (see \ref{procedureCall}), in the case of value
   parameters the formal type must be assignment compatible with the
   actual type (see \ref{assignment}). If the parameter is an array, the form
\begin{verbatim}
      ARRAY OF T
\end{verbatim}
\noindent may be used, where the specification of the actual index bounds is
   omitted. The parameter is then said to be an {\em open array
   parameter}. T must be the same as the element type of the actual
   array, and the index range is mapped onto the integers 0 to N--1,
   where N is the number of elements. The formal array can be accessed
   elementwise only, or it may occur as actual parameter whose formal
   parameter is without specified index bounds. A function procedure
   without parameters has an empty parameter list. It must be called
   by a function designator whose actual parameter list is empty too.
   
   {\small Restriction: If a formal parameter specifies a procedure
   type, then the corresponding actual parameter must be either a
   procedure declared at level 0 or a variable (or parameter) of that
   procedure type. It cannot be a standard procedure.}
   
   Examples of procedure declarations:
\begin{verbatim}
      PROCEDURE Read(VAR x: CARDINAL);
        VAR i: CARDINAL; ch: CHAR;
      BEGIN i:= 0;
        REPEAT ReadChar(ch)
        UNTIL (ch>= "0") & (ch<= "9");
        REPEAT i:= 10*i + (ORD(ch)-ORD("0"));
          ReadChar(ch)
        UNTIL (ch<"0") OR (ch>"9");
        x:= i
      END Read

      PROCEDURE Write(x,n: CARDINAL);
        VAR i: CARDINAL;
          buf: ARRAY[1..10] OF CARDINAL;
      BEGIN i:= 0;
        REPEAT INC(i); buf[i]:= x MOD 10; x:= x DIV 10
        UNTIL x = 0;
        WHILE n>i DO
          WriteChar(" "); DEC(n)
        END;
        REPEAT WriteChar(CHR(buf[i] + ORD("0")));
          DEC(i)
        UNTIL i = 0;
      END Write 
         
      PROCEDURE log2(x: CARDINAL): CARDINAL;
        VAR y: CARDINAL; (* assume x>0 *)
      BEGIN x: = x-1; y: = 0;
        WHILE x>0 DO
          x:= x DIV 2; y:= y+1
        END;
        RETURN y
      END log2
\end{verbatim}
\bchanged
\begin{verbatim}
      TRANSACTION AveragePrice (irel: Items): INTEGER;
        VAR sum: INTEGER;
      USING irel FOR (=);
      BEGIN
        sum := 0;
        FOR EACH item IN irel: TRUE DO sum := sum + item.price END;
        RETURN ORD(sum) DIV CARD(irel)
      END AveragePrice;

      TRANSACTION DropItem (s: String);
      USING orders[OfParts(s)] FOR (=);
        parts FOR (=, :-) ;
      BEGIN
        IF SOME p IN parts(p.itemname=s) AND       
           (orders[OfPart()(s)] = Deliveries{}) 
        THEN parts :- Items{parts[s]}
        END
      END DropItem;
\end{verbatim}
\echanged

\subsection{Standard procedures}

\label{standardProc}
   Standard procedures are predefined. Some are {\em generic}
   procedures that cannot be explicitly declared, i.e. they apply to
   classes of operand types or have several possible parameter list
   forms. Standard procedures are 

\bchanged
\begin{center}
\begin{tabular}{p{3cm}p{9cm}}
   ABS(x)      & absolute value; result type = argument type.\\
   CAP(ch)     & if ch is a lower case letter, the corresponding
                 capital letter; if ch is a capital letter, the same letter.\\
   CARD(rex)   &  rex is a relation expression of any  relation 
                  type  and the result is the actual number  of 
                  relation elements in rex;  the result type  is 
                  CARDINAL.\\
   CHR(x)      & the character with ordinal number x. CHR(x) =
                 VAL(CHAR,x) \\
   FLOAT(x)    & x of type CARDINAL represented as a value of
                 type REAL.\\
   HIGH(a)     & high index bound of array a.\\ 
   MAX(T)      & the maximum value of type T.\\
   MIN(T)      & the minimum value of type T. \\
   ODD(x)      & x MOD 2 \# 0.\\
   ORD(x)      & ordinal number (of type CARDINAL) of x in the set of
                 values defined by type T of x. T is any enumeration type, CHAR,
                 INTEGER, or CARDINAL. \\
   RESTRICTED() &  a value of type BOOLEAN that indicates whether
                   an update operation on a (selected) relation was not executed
                   due to a violation of a key or a selector constraint.\\ 
   
   SIZE(T)     & the number of storage units required by a variable of type
                 T, or the number of storage units required by the variable
                 T.\\ 
   TRUNC(x)    & real number x truncated to its integral part
                 (of type CARDINAL).\\ 
   VAL(T,x)    & the value with ordinal number x and with type T. T
                 is any enumeration type, CHAR, INTEGER, or CARDINAL.
                 VAL(T,ORD(x)) = x, if x of type T.\\ 
   DEC(x)      & x:= x--1\\
   DEC(x,n)    & x:= x--n\\
   EXCL(s,i)   & s:= s--\{i\} for sets, s:--\{i\} for relations\\
   HALT        & terminate program execution\\
   INC(x)      & x:= x+1\\
   INC(x,n)    & x:= x+n\\
   INCL(s,i)   & s:= s+\{i\} for sets, s:+\{i\} for relations
\end{tabular}
\end{center}
\echanged   

   The procedures INC and DEC also apply to operands x of enumeration
   types and of type CHAR. In these cases they replace x by its (n-th)
   successor or predecessor.
   
% 3rd Ed. (Abschnitt ueber NEW/DISPOSE geloescht)
                 
\bchanged
     The five relation handling procedures LOWEST, NEXT, THIS, HIGHEST
     and PRIOR select at most one element from the (selected)
     relation variable rel given as the first parameter. If the element
     exists it is assigned to the second parameter r which must be a
     variable of the element type of the first parameter, and EOR()
     becomes FALSE; if the element does not exist EOR() becomes TRUE 
     and r remains unchanged.
   
     The procedures provide an ordered access to the elements of the relation
     rel. This order is implied by the lexicographic order on the value sets
     of  the types  of  the key components. 
   
\begin{center}
\begin{tabular}{lp{8cm}}
     LOWEST(rel, r)    &  selects the first element in rel.\\
     HIGHEST(rel, r)   &  selects the last element in rel.\\
     PRIOR(rel, r)     &  selects the predecessor of r in rel.\\
     NEXT(rel, r)      &  selects the successor of r in rel.\\
     THIS(rel, r)      &  selects the element in rel, that has the same 
                          ordinal value as r.\\
     EOR               &  returns a value of type BOOLEAN that indicates whether
the last application of one of the above operations selected an element r IN
rel.
\end{tabular}
\end{center}
\echanged

\section{Modules}

\label{module}
   A module constitutes a collection of declarations and a sequence
   of statements. They are enclosed in the brackets MODULE and END.
   The module heading contains the module identifier, and possibly a
   number of {\em import lists} and an {\em export list}. The former
   specify all identifiers of objects that are declared outside but
   used within the module and therefore have to be imported. The
   export-list specifies all identifiers of objects  declared within
   the module and used outside. Hence, a module constitutes a wall
   around its local objects whose transparency is strictly under
   control of the programmer.
   
   Objects local to a module are said to be at the same scope level as
   the module. They can be considered as being local to the procedure
   enclosing the module but residing within a more restricted scope.

\begin{syntax}
\$ ModuleDeclaration = MODULE ident [priority] ``;'' \{import\} [export] block ident.\\
\$ priority = ``['' ConstExpression ``]''.\\
\$ export = EXPORT [QUALIFIED] IdentList ``;''.\\
\$ import = [FROM ident] IMPORT IdentList ``;''.
\end{syntax}
   
   The module identifier is repeated at the end of the declaration.
   
   The statement sequence that constitutes the {\em module body}
   is executed when the procedure to which the module is local is
   called. If several modules are declared, then these bodies are
   executed in the sequence in which the modules occur. These bodies
   serve to initialize local variables and must be considered as
   prefixes to the enclosing procedure's statement part. 
   
   If an identifier occurs in the import (export) list, then the
   denoted  object may be used inside (outside) the module as if the
   module brackets did not exist. If, however, the symbol EXPORT is
   followed by the symbol QUALIFIED, then the listed identifiers must
   be prefixed with the module's identifier when used outside the
   module. This case is called {\em qualified export}, and is used
   when modules are designed which are to be used in coexistence with
   other modules not known a priori. Qualified export serves to avoid
   clashes of identical identifiers exported from different modules
   (and presumably denoting different objects).
    
   A module may feature several import lists which may be prefixed
   with the symbol FROM and a module identifier. The FROM clause has
   the effect of unqualifying the imported identifiers. Hence they may
   be used within the module as if they had been exported in normal,
   i.e. non-qualified mode. 
   
   If a record type is exported, all its field identifiers are
   exported too. The same holds for the constant identifiers in the
   case of an enumeration  type.
% 3rd Ed. (Absatz geloescht)
         
   Examples of module declarations:
   
   The following module serves to scan a text and to copy it into an
   output character sequence. Input is obtained characterwise by a
   procedure inchr and delivered by a procedure outchr. The characters
   are given in the ASCII code; control characters are ignored, with
   the exception of LF (line feed) and FS (file separator). They are
   both translated into a blank and cause the  Boolean variables eoln
   (end of line) and eof (end of file) to be set  respectively. FS is
   assumed to be preceded by LF. 

\begin{verbatim}
      MODULE LineInput;
         IMPORT inchr, outchr;
         EXPORT read, NewLine, NewFile, eoln, eof, lno;
         CONST LF = 12C; CR = 15C; FS = 34C;

         VAR lno: CARDINAL;(* line number *)
           ch: CHAR; (* last character read *)
           eof, eoln: BOOLEAN;

         PROCEDURE NewFile;
         BEGIN
           IF NOT eof THEN
             REPEAT inchr(ch) UNTIL ch = FS;
           END;
           eof: = FALSE; eoln:= FALSE; lno:= 0
         END NewFile;

         PROCEDURE NewLine;
         BEGIN
           IF NOT eoln THEN
             REPEAT inchr(ch) UNTIL ch = LF;
             outchr(CR); outchr(LF)
           END;
           eoln: = FALSE; INC(lno)
         END NewLine;

         PROCEDURE read(VAR x: CHAR);
         BEGIN (* assume NOT eoln AND NOT eof *)
           LOOP inchr(ch); outchr(ch);
             IF ch>= " " THEN
               x:= ch; EXIT
             ELSIF ch = LF THEN
               x:= " "; eoln:= TRUE; EXIT
             ELSIF ch = FS THEN
               x:= " "; eoln:= TRUE; eof:= TRUE; EXIT
             END
           END
         END read;               
         
      BEGIN eof:= TRUE; eoln:= TRUE
      END LineInput.
\end{verbatim}
                                 
   The next example is a module which operates a disk track
   reservation table, and protects it from unauthorized access. A
   function procedure NewTrack yields the number of a free track which
   is becoming reserved. Tracks can be released by calling procedure
   ReturnTrack. 

\begin{verbatim}
      MODULE TrackReservation;
        EXPORT NewTrack, ReturnTrack;
        CONST ntr = 1024; (* no. of tracks *)
          w = 16;   (*word size*)
          m = ntr DIV w;

        VAR i: CARDINAL;
          free: ARRAY [0..m-1] OF BITSET;

        PROCEDURE NewTrack(): INTEGER;
        (* reserves a new track and yields its index as result,
           if a free track is found, and -1 otherwise *)
          VAR i,j: CARDINAL; found: BOOLEAN;
        BEGIN found:= FALSE; i:= m;
          REPEAT DEC(i); j:= w;
            REPEAT DEC(j);
              IF j IN free[i] THEN found:= TRUE END
            UNTIL found OR (j=0)
          UNTIL found OR (i=0);
          IF found THEN EXCL(free[i],j); RETURN i*w+j
          ELSE RETURN -1
          END
        END NewTrack;

        PROCEDURE ReturnTrack(k: CARDINAL);
        BEGIN (* assume 0<=k<ntr *)
          INCL(free[k DIV w], k MOD w)
        END ReturnTrack;

      BEGIN (* mark all tracks free *)
        FOR i:= 0 TO m-1 DO free[i]:= {0..w-1} END
      END TrackReservation.
\end{verbatim}
                                 
\section{System-dependent facilities}
                                 
\label{system}
   DBPL offers certain facilities that are necessary to program
   low-level operations referring directly to objects particular of a
   given computer  and/or implementation. These include for example
   facilities for accessing devices that are controlled by the
   computer, and facilities to break the data type compatibility rules
   otherwise imposed by the language definition. Such facilities are
   to be used with utmost care, and it is strongly  recommended to
   restrict their use to specific modules (called low-level  modules).
   Most of them appear in the form of data types and procedures
   imported from the standard module SYSTEM. A low-level module is
   therefore explicitly characterized by the identifier SYSTEM
   appearing in its import list. 

   {\small Note: Because the objects imported from SYSTEM obey special
   rules, this module must be known to the compiler. It is therefore
   called a pseudo-module and need not be supplied as a separate
   definition module (see Ch. \ref{compilation}). }
% 3rd Ed.

   The facilities exported from the module SYSTEM are specified by
   individual implementations. Normally, the types WORD and ADDRESS,
   and the procedures ADR, TSIZE, NEWPROCESS, TRANSFER are among
   them (see also Ch. \ref{processes}).
   
   The type WORD represents an individually accessible storage unit.
   No operation except assignment is defined on this type. However, if
   a formal parameter of a procedure is of type WORD, the
   corresponding actual parameter may be of any type that uses one
   storage word in the given implementation.
% 3rd Ed.
   If a formal parameter
   has the type ARRAY OF WORD, its corresponding actual parameter may
   be of any type; in particular it may be a record type to be
   interpreted as an array of words. 
   
   The type ADDRESS is defined as
\begin{verbatim}
      ADDRESS = POINTER TO WORD
\end{verbatim}
   
   It is compatible with all pointer types, and also with the type
   CARDINAL. Therefore, all operators for integer arithmetic apply to
   operands of this type. Hence, the type ADDRESS can be used to
   perform address computations and to export the results as pointers.
   The following example of a primitive  storage allocator
   demonstrates a typical usage of the type ADDRESS. 

\begin{verbatim}
      MODULE Storage;
        FROM SYSTEM IMPORT ADDRESS;
        EXPORT Allocate;

        VAR lastused: ADDRESS;

        PROCEDURE Allocate(VAR a: ADDRESS; n: CARDINAL);
        BEGIN a:= lastused; lastused:= lastused + n
        END Allocate;

      BEGIN lastused:= 0
      END Storage
\end{verbatim}
 
% 3rd Ed.
   The function ADR(x) denotes the storage address of the variable x
   and is of type ADDRESS. TSIZE(T) is the number of storage units
   assigned to any variable of type T. TSIZE is of an arithmetic type
   depending on the implementation.
   
   Examples:
\begin{verbatim}
      ADR(lastused)   TSIZE(Node)
\end{verbatim}

   Besides those exported from the pseudo-module SYSTEM, there are two
   other facilities whose characteristics are system-dependent. The
   first is the  possibility to use a type identifier T as a name
   denoting the {\em type transfer function} from the type of the
   operand to the type T. Evidently, such functions are data
   representation dependent, and they involve no explicit conversion
   instructions. 
   
% 3rd Ed.
   The second non-standard facility is used in variable declarations. 
   It allows to
   specify the absolute address of a variable and to override the
   allocation scheme of a compiler. This facility is intended for
   access to storage locations with  specific purpose and fixed
   address, such as e.g. device registers on computers with
   ``memory-mapped I/O''. This address is specified as a constant
   integer expression enclosed in brackets immediately following the
   identifier in the variable declaration. The choice of an
   appropriate data type is left to the programmer.

\section{Processes}

\label{processes}
   Being a Modula-2 extension, DBPL is designed primarily for
   implementation on a conventional single-processor computer. For
   multiprogramming it offers only some basic facilities which allow
   the specification of quasi-concurrent processes and of genuine
   concurrency for peripheral devices. The word {\em process} is here
   used with the meaning of {\em coroutine}. Coroutines are processes
   that are executed by a (single) processor one at a time. 
   
\subsection{Creating a process and transfer of control}

   A new process is created by a call to
% 3rd Ed.
\begin{verbatim}
      PROCEDURE NEWPROCESS(P: PROC; A: ADDRESS; n: CARDINAL; 
                           VAR p1: ADDRESS)
\end{verbatim}
\begin{tabbing}
        XX \= \kill
        P  \> denotes the procedure which constitutes the process,\\
        A  \> is the base address of the process' workspace, \\
        n  \> is the size of this workspace,\\
        p1 \> is the result parameter.
\end{tabbing}

   A new process with P as program and A as workspace of size n is
   assigned to p1. This process is allocated, but not activated. P
   must be a parameterless  procedure declared at level 0.
   
   A transfer of control between two processes is specified by a call
   to                                                  
% 3rd Ed.
\begin{verbatim}
      PROCEDURE TRANSFER(VAR p1, p2: ADDRESS)
\end{verbatim}                     

   This call suspends the current process, assigns it to p1, and
   resumes the process designated by p2. Evidently, p2 must have been
   assigned a process by an earlier call to either NEWPROCESS or
   TRANSFER. Both procedures must be imported.
% 3rd Ed.
   A program  terminates, when control reaches the end of a procedure 
   which is the body of a process. 

   {\small Note: assignment to p1 occurs after identification of the
   new process p2; hence, the actual parameters may be identical.}
   
\subsection{Device processes and interrupts}

\label{device}
   If a process contains an operation of a peripheral device, then the
   processor may be transferred to another process after the operation
   of the device has  been initiated, thereby leading to a concurrent
   execution of that other process with the {\em device process}. Usually,
   termination of the device's operation is signalled by an interrupt
   of the main processor. In terms of DBPL, an interrupt is a transfer
   operation. This interrupt transfer is (in Modula-2 implemented on
   the PDP-11) preprogrammed by and combined with the transfer after
   device initiation. This combination is expressed by a call to
\begin{verbatim}
      PROCEDURE IOTRANSFER(VAR p1, p2: ADDRESS; va: CARDINAL)
\end{verbatim}

   In analogy to TRANSFER, this call suspends the calling device
   process, assigns it to p1, resumes (transfers to) the suspended
   process p2, and in addition causes the interrupt transfer occurring
   upon device completion to assign the interrupted process to p2 and
   to resume the device process p1. va is the  interrupt vector
   address assigned to the device. The procedure IOTRANSFER must be
   imported from the module SYSTEM, and should be considered as PDP-11
   implementation-specific. 
   
   It is necessary that interrupts can be postponed (disabled) at
   certain times, e.g. when variables common to the cooperating
   processes are accessed, or when other, possibly time-critical
   operations have priority. Therefore, every module is given a
   certain priority level, and every device capable of interrupting is
   given a priority level. Execution of a program can be  interrupted,
   if and only if the interrupting device has a priority that is
   greater than the priority level of the module containing the
   statement  currently being executed. Whereas the device priority is
   defined by the hardware, the priority level of each module is
   specified by its heading. If an explicit specification is absent,
   the level in any procedure is that of the calling program.
   IOTRANSFER must be used within modules with a specified priority
   only.                                                        
   
\section{Compilation units}

\label{compilation}
   A text which is accepted by the compiler as a unit is called a
   {\em compilation unit}. There are three kinds of compilation units:
   main modules, definition modules, and implementation modules. A
   main module constitutes a main program and consists of a so-called
   {\em program module}. In particular, it has no export list.
   Imported objects are defined in other (separately compiled)
   program parts which themselves are subdivided into two units,
   called definition module and implementation module.
   
   The {\em definition module} specifies the names and properties of
   objects that are relevant to clients, i.e. other modules which
   import from it. The {\em implementation module} contains local
   objects and statements that need not be known to a client. In
   particular the definition module contains the export list,
   constant, type, and variable declarations, and specifications of 
% 3rd Ed.
   procedure, selector and constructor headings. The corresponding
   implementation module contains the complete procedure declarations,
   and possibly further declarations of objects not exported.
   Definition and implementation modules exist in pairs. Both  may
   contain import lists, and all objects declared in the definition
   module are available in the corresponding implementation module
   without explicit import.
   
\bchanged
     Compilation units  prefixed  with  the   symbol 
     DATABASE  are  called {\em database modules}.  Variables declared  within  a 
     database  module which reside at the same scope level as  the  modules 
     are called persistent variables.  Their lifetime is longer than that  of 
     any  program importing the database module.  The set of  all  persistent 
     variables  of  a  database module  constitutes  a  database.  Persistent
     variables  are shared objects,  i.e.  they can be accessed by  several 
     programs simultaneously. An access to a persistent variable must be part 
     of  a  transaction execution.  During the  transaction  execution  the 
     calling  program  is  guaranteed  to be the  only  one  accessing  the 
     respective  persistent  variables;  the values of these  variables  upon 
     entry to the transaction however cannot be deduced from the program.
   
\begin{syntax}
\$ CompilationUnit = [DATABASE] (DefinitionModule $|$ ImplementationModule $|$\\
\$   \> ProgramModule).
\$ DefinitionModule = DEFINITION MODULE ident ``;''\\
% 3rd Ed.
\$   \>\{import\} \{definition\} END ident ``.''.\\
\$ definition = CONST \{ConstantDeclaration ``;''\} $|$\\
\$   \>TYPE \{ident [``='' type] ``;''\} $|$\\
\$   \>VAR \{VariableDeclaration ``;''\} $|$\\                  
\$   \>SelectorHeading ``;'' $|$ ConstructorHeading ``;'' $|$\\
\$   \>ProcedureHeading ``;''.\\
\$ ImplementationModule = IMPLEMENATION MODULE ident [priority] ``;''\\ 
\$   \>\{import\} {declaration}\\
\$   \>[DATABASE DEFINITON StatementSequence]\\ 
\$   \>[DATABASE IMPLEMENTATION StatementSequence]\\ 
\$   \>[BEGIN StatementSequence] END ident ``.''.\\
\$ ProgramModule = MODULE ident [priority] ``;'' \{import\} {declaration}\\
\$   \>[DATABASE StatementSequence] [BEGIN StatementSequence] END ident ``.''. 
\end{syntax}  
\echanged

% 3rd Ed.
   The definition module evidently represents the interface between
   the implementation module on one side and its clients on the other side.
   The definition module contains those declarations which are relevant
   to the client modules, and presumably no other ones. Hence,
   the definition module acts as the implementation module's 
   (extended) export list, and all its declared objects are exported.
                           
% 3rd Ed.
   Definition modules imply the use of qualified export. Type
   definitions may consist of the full specification of the type (in
   this case its export is said to be transparent), or they may
   consist of the type identifier only. In this case the full
   specification must appear in the corresponding implementation
   module, and its export is said to be {\em opaque}. The type is
   known in the importing client modules by its name only, and all its
   properties are hidden. Therefore, procedures operating on operands
   of this type, and in particular operating on its components, must
   be defined in the same implementation module which hides the type's
   properties. Opaque export is restricted to pointers. Assignment
   and test for equality are applicable to all opaque types.

% 3rd Ed.
   As in local modules, the body of an implementation module acts as an
   initialisation facility for its local objects. Before its execution,
   the imported modules are initialized in the order in which they
   are listed. If circular references occur among modules, their order
   of initialization is not defined.

\bchanged                                      
   The body of a database module may contain initialization statements for
   each kind of compilation unit. This initialization is executed only
   once during database lifetime, namly before any access to the
   persistent variables has been made.
\echanged   
