Edison – a Multiprocessor Language

Edison – a Multiprocessor Language

Edison – a Multiprocessor Language

by Per Brinch Hansen
Computer Science Department, University of Southern California,
Los Angeles, California 900007, USA


SUMMARY

This paper defines a programming language called Edison. The language
is suitable for teaching the principles of concurrent programming
and for designing reliable real-time programs for multiprocessor systems.
Edison is block structured and includes modules, concurrent statements,
and when statements.

KEY WORDS: Edison Programming language Multiprocessing Modules
Concurrent statements When statements


CONTENTS

  1. LANGUAGE OVERVIEW
  2. SYMBOLS AND SENTENCES
    1. Syntactic rules
    2. Characters
    3. Basic symbols
    4. Separators
    5. Character strings

  3. PROGRAMS AND EXECUTION
  4. NAMED ENTITIES

    1. Standard names
    2. Declarations
    3. Blocks, scopes, and contexts
    4. Modules

  5. VALUES, OPERATIONS, AND TYPES

    1. Type declarations

  6. CONSTANTS

    1. Constant declarations

  7. ELEMENTARY TYPES

    1. Type integer
    2. Arithmetic operators
    3. Type boolean
    4. Boolean operators
    5. Type character
    6. Enumeration types
    7. Elementary constructors
    8. Elementary relations

  8. RANGES
  9. RECORD TYPES

    1. Record constructors
    2. Record relations

  10. ARRAY TYPES

    1. Array constructors
    2. Array relations

  11. SET TYPES

    1. Set constructors
    2. Set relations
    3. Set operators

  12. CONSTRUCTORS
  13. VARIABLES

    1. Variable declarations
    2. Variable operands
    3. Field variables
    4. Indexed variables
    5. Retyped variables

  14. EXPRESSIONS

    1. Retyped factors

  15. STATEMENTS

    1. Skip statements
    2. Assignment statements
    3. Procedure calls
    4. If statements
    5. While statements
    6. When statements
    7. Concurrent statements

  16. PROCEDURES

    1. Complete procedures
    2. Parameters
    3. Functions
    4. Split procedures
    5. Library procedures

  17. PROGRAMS
  18. SYNTAX SUMMARY
  19. ACKNOWLEDGMENT
  20. INDEX

1. LANGUAGE OVERVIEW

This paper defines the programming language Edison. The language
is suitable both for teaching the principles of concurrent programming
and for designing reliable real-time programs for a multiprocessor
system.

The overriding concern in the design of Edison was to achieve
simplicity in the design of medium-sized programs of 1000-2000 lines
of text. This aim led to the selection of a small number of abstract
concepts for modular programming. In particular, the issues of
modularity, concurrency, and synchronization were
separated into distinct language features.

An Edison program describes operations on named entities called
constants, variables, and procedures. The constants and variables
have data values of fixed types. The types determine the possible
values of these entities and restrict the operations that can
be performed on them.

The data types integer, boolean, and character are standard types.
Other types are introduced by enumerating their values
or by describing how the values are composed from other values.
The composition methods for new types are the well-known arrays,
records, and sets. Every type has a name, and two operands are
of the same type only if their types are denoted by the same
name and have the same scope.

The computation of new data values from existing
values is described by expressions in which the operands
are constants, variables, and function calls, while the operators
are the conventional arithmetic, boolean, set, and relational
operators. The computation of composite values in terms of other values
is described by expression lists called constructors.

Statements describe operations such as the assignment of
values to variables and the execution of procedures. The if,
while and when statements describe a choice
among substatements to be executed depending on the truth values of
expressions. The concurrent statement denotes simultaneous
execution of several substatements as concurrent processes.
Process synchronization is controlled by when
statements. The execution of a when statement delays
a process until an expression is true and then performs
an operation on the common variables shared by the processes.
Concurrent processes can only execute when statements one
at a time.

The named entities and statements of a program are grouped into
blocks of two kinds, called procedures and modules. Blocks can
be combined to form other blocks in a nested fashion.

A procedure is a group of named entities and statements that
describe an operation on operands of fixed types. The operands
(known as parameters) may vary from one execution of
the procedure to another.
Each parameter is either a variable or another procedure.
The named entities introduced by a procedure are local
to the procedure and cannot be used outside it. Each execution
of the procedure creates a fresh instance of its parameters
and local variables. These entities disappear again
when the execution of the procedure terminates.

A module is a group of named entities that fall into
two categories: (1) local entities that can only be used within
the module, and (2) exported entities that can be used both
within the module and within the immediately-surrounding block.
The module entities exist as long as the entities of the
immediately-surrounding block. A module serves
to ensure that its local entities are only operated upon
by well-defined procedures which are exported from
the module to the immediately-surrounding block. To ensure
that the local variables are initialized before they are used,
a module includes a statement part that is executed when the module
entities are created.


2. SYMBOLS AND SENTENCES


The programming language Edison is a formal notation
in which programs can be written. The programs are texts
composed of symbol sequences known as sentences.

The language is described in terms of syntactic forms.
A syntactic form is a named class of symbols or sentences with
common properties. The definition of a syntactic form
consists of syntactic rules that define how sentences of the form
are composed and semantic rules that define the meaning of these sentences.

2.1. Syntactic rules

A syntactic rule described in a variant of the Backus-Naur notation
has the form

    S: E

where S stands for the name of the syntactic form while E stands for
a syntax expression that defines the corresponding class of sentences.
The name S consists of a capital letter possibly followed by small letters
and spaces.

Example of a syntactic rule:

    Parameter group:
      ['var'] Variable group # Procedure heading

A syntactic expression has the form

    T1 # T2 # ... # Tn

where T1, T2,…, Tn stand for terms that define classes of sentences.
A sentence of this form is composed by writing a sentence belonging to anyone of
the classes.

Example of a syntax expression:

    ['var'] Variable group # Procedure heading

A syntax term has the form

    F1 F2... Fn

where F1, F2,…, Fn stand for the syntax factors that define classes
of sentences. A sentence of the form is composed by writing a sentence of each
class in the order shown.

Example of a syntax term:

    ['var'] Variable group

A syntax factor has one of the four forms:

  1.     [E]*
    

    This form is an abbreviation for the syntax expression Empty # E # E E # E E E…
    where the name Empty denotes the empty sentence while E denotes a syntax
    expression. A sentence of this form is composed by writing either nothing
    or a finite sequence of sentences of the class E.

    Examples of a syntax factor:

        [Letter # Digit # '_']*
    
  2.     [E]
    

    This form is an abbreviation for the syntax expression Empty # E.
    A sentence of this form is composed by writing either nothing or
    a sentence of the class E.

    Example of a syntax factor:

        ['var']
    
  3.     N
    

    where N denotes the name of a syntactic form. A sentence of this
    form is composed according to the syntactic rule named N.

    Example of a syntax factor:

        Variable group
    
  4.     'C1 C2... Cn'
    

    where C1, C2,…, Cn denote characters. A symbol of this form
    is composed of the characters written in the order shown. In particular,
    the syntax factors ‘#’, ‘:’, ‘[‘, ‘]’, ‘*’, and ”’ denote
    the characters #, :, [, ], *, and ‘ used as program symbols.

    Example of a syntax factor:

        'var'
    

2.2. Characters

    Character:
     Graphic character # New line character
    Graphic Character:
     Letter # Digit # Special character # Space
    Letter:
     'a' # 'b' # 'c' # 'd' # 'e' # 'f' # 'g' # 'h' # 'i' #
     'j' # 'k' # 'l' # 'm' # 'n' # 'o' # 'p' # 'q' # 'r' #
     's' # 't' # 'u' # 'v' # 'w' # 'x' # 'y' # 'z'
    Digit:
     '0' # '1' # '2' # '3' # '4' # '5' # '6' # '7' # '8' # '9'
    Special character:
     '"' # ''' # '(' # ')' # '*' # '+' # ',' # '-' # '.' #
     ':' # ';' # '<' # '=' # '>' # '[' # ']' # '_'

Characters are used to form basic symbols
(see Section 2.3).
A graphic character is represented by a graphic picture
or the deliberate omission thereof (a space). A new line
character marks the end of each line of text.

The character set may be extended with more letters and special
characters. In particular, the letters may be extended with capital
letters. The meaning of capital letters is explained in sections
2.3 and
4.


2.3. Basic symbols

    Basic symbol:
     Special symbol # Word symbol # Name # Numeral #
     Graphic symbol
    Special symbol:
     '+' # '-' # '*' # '=' # '<>' # '<' # '<=' # '>' # '>=' #
     ':=' # '(' # ')' # '[' # ']' # '.' # ',' # ':' # ';'
    Word symbol:
     'also' # 'and' # 'array' # 'begin' # 'cobegin' #
     'const' # 'div' # 'do' # 'else' # 'end' # 'enum' #
     'if' # 'in' # 'lib' # 'mod' # 'module' # 'not' #
     'or' # 'post' # 'pre' # 'proc' # 'record' # 'set' #
     'skip' # 'val' # 'var' # 'when' # 'while' #

The basic symbols are either special symbols, word symbols,
names
(see Section 4),
numerals
(see Section 7.1),
or graphic symbols
(see Section 7.5).

The special symbols and the word symbols have fixed meanings
which will be defined later.

Any capital letter used in a word symbol is considered equivalent
to the corresponding small letter. In this report the word
symbols are printed in boldface type.

2.4. Separators

    Separator:
     Space # New line character # '"' Comment '"'
    Comment:
     [Character]*

The character ” cannot occur within a comment.

Any basic symbol preceded by one or more separators stands
for the basic symbol itself. Two adjacent word symbols or names must be
separated by at least one separator.

Example:

    "This is a comment"

2.5. Character strings

    Character list:
     ''' Graphic character '''
      [',' ''' Graphic character ''']*
    Character string:
     ''' Graphic character [Graphic character]* '''

A character list denotes a sequence of graphic characters.
Character lists are used in constructors
(see Section 12).

A character string is an abbreviation for a character list that
contains the same sequence of graphic characters.

Example of character lists:

    '.'
    'E', 'd', 'i', 's', 'o', 'n'

Examples of character strings:

    '.'
    'Edison'

3. PROGRAMS AND EXECUTION


A program is a description of one or more related data processes,
each process taking place in a number of separate steps. In each step
a well-defined action (an operation) is performed on a set
of entities (the operands).

The act of following a program text and performing the operations
described by it is called the execution of a program (and its operations).
A person or device that executes a program (or part of it) is called
a processor.

The operands of a program generally denote data values that
either remain fixed (constants) or change during the execution (variables).

The operations are generally rules for deriving new data values (results)
from previous data values given by operands. Operations may also use data
values to determine the order in which subsequent operations are to
be executed.

The execution of an operation will have one of three outcomes:

  1. Termination: after a finite time the processor completes the operation.
  2. Failure: after a finite time the processor detects that the operation
    is meaningless and cannot continue the execution of the program.

  3. Cycling: the processor executes the same cycle of operations
    endlessly.

The execution of certain operations may be influenced by properties
that are not fully described in this report since they vary from
processor to processor. Such properties are said to be system dependent.

A program may prescribe a sequence of operations to be carried out
strictly one at a time. Such a sequence is known as a process.
A program may also allow several processes to take place simultaneously.
They are know as concurrent processes.


4. NAMED ENTITIES

    Name:
     Letter [Letter # Digit # '_']*

Any capital letter used in a name is considered equivalent to
the corresponding small letter. The word symbols cannot be used
as names. Apart from that names may be chosen freely.

A name denotes an entity used in a program. The entity is
either a constant
(see Section 6),
a data type
(see Section 5),
a record field
(see Section 9),
a variable
(see Section 13),
or a procedure
(see Section 16).

Examples:

    char
    s
    table
    matrix1
    rc4000a
    end_of_file

4.1. Standard names

    Standard name:
     'bool' # 'char' # 'false' # 'int' # 'true'

The standard names denote the standard types bool, char, int,
and the truth values false, true
(see Section 7).
These names can be used throughout a program without being declared.

4.2. Declarations

    Declaration:
     Constant declaration list # Type declaration #
     Variable declaration list # Procedure declaration #
     Module declaration

A declaration introduces names to denote program entities
and describes some of their properties. The entities are either
constants
(see Section 6.1),
types
(see Section 5.1),
variables
(see Section 13.1),
procedures
(see Section 16),
or modules
(see Section 4.4).

The use of a name within a program to denote an entity must be
preceded by a declaration which introduces the name and describes
the entity it stands for (unless the name is a standard name).
A declaration of an entity is generally valid within
one block only
(see Section 4.3).
Outside this block the same name
can be declared and used with other meanings.

4.3. Blocks, scopes, and contexts

A block is a piece of program text consisting of (1) declarations
of named entities, and (2) statements which define operations on
these entities. The only possible kinds of
blocks are procedures
(see Section 16),
modules
(see Section 4.4),
and programs
(see Section 17).

Generally a block Q can be a part of another block P in which case
P is said to contain Q. The block Q is then called an inner block
of P, while P is called a surrounding block of Q. In general
a program will consist of a hierarchy of nested blocks.

The innermost block in which a declaration of a named entity appears
is called the origin of that declaration.

The scope of a named entity x is that part of the program text in
which the name x may be used to denote the entity. A named entity
is said to be known within its scope.

The scope generally extends from the declaration of the entity to
the end of its origin, with the following additional rules:

  1. If the origin is a module M then the scope may be extended to
    the end of the immediately-surrounding block B. The entity is
    then said to be exported from M to B
    (see Section 4.4).

  2. If the same name is declared with another meaning in an inner
    block of the origin then the scope does not include the inner block.

A given name can only be declared with one meaning in the same block.
And a name cannot be exported to a surrounding block in which the same
name is declared with another meaning.

The meaning of a name used at some point in a block is determined
by the following rules:

  1. Local entity: if the use of the name is preceded by a declaration
    in the same block of an entity of that name then the use of the name
    denotes the entity.

  2. Exported entity: if the use of the name is preceded by a module
    in the same block from which a declared entity of that name is exported
    to the block then the use of the name denotes the entity.

  3. Global entity: if neither of the above apply then the name has the
    same meaning it has in the immediately-surrounding block at the point
    where the given block begins.

When several processes are executed concurrently or when
a single process calls one or more procedures recursively,
several instances of a named entity may exist simultaneously.
At any given moment, however, a process can only operate
on a single instance of every entity that is know to the process
at the moment.

When a process executes a statement it operates on known
entities selected from a set of entities the current context
of the process. The context consists of (1) an instance of every
entity declared in the procedures surrounding the statement,
and (2) an instance of every entity declared in the modules
contained in these procedures.

When a process refers to a known entity an instance of that entity
is located in the current context of the process in accordance
with the scope rules.

Throughout this report the phrase ‘the current context’
refers to the current context of the process that performs a given
operation.

The dynamic changes of contexts are further explained in Sections
4.4,
15.3,
15.7
and
17.

4.4. Modules

A module is a block that introduces two kinds of named entities
known as local and exported entities. The module also describes
an initial operation on these entities.

The local entities can only be used within the module. The exported
entities can be used both within the module and within the block
that immediately surrounds the module.

A module is either contained in a procedure or in another module.
When a procedure body is executed an operation known as module
initialisation is performed on all modules declared within the
procedure body.

The initialisation of a module M take place in three steps:

  1. The local and exported entities declared in M are created
    and added to the current context.

  2. The modules declared in M are initialised one at a time in the
    order written.

  3. The initial operation of M is performed.

When the execution of the procedure terminates the entities
of the module (and those of its inner modules) disappear again.

    Module declaration:
     'module' [Local declaration # Exported declaration]*
       Statement part
    Local declaration:
     Declaration
    Exported declaration:
     '*' Declaration
    Statement part:
     'begin' Statement list 'end'

A module declaration describes a module by means of declarations
of local and exported entities and by a statement part which
describes the initial operation by means of a statement list
(see Section 15).

An export symbol * in front of a module declaration has no effect.
Exported entities are discussed further in Sections
6.1,
7.6,
9,
10,
11,
13.1
and
16.

Example:

    module
      const max = 10
      array stack[1 : max] (int)
      var lifo : stack; size : int
    
      *proc push(x : int)
      begin size := size+1; lifo[size] := x end
    
      *proc pop(var x : int)
      begin x := lifo[size]; size := size - 1 end
    
      *proc empty : bool
      begin val empty := (size = 0) end
    
    begin size := 0 end

5. VALUES, OPERATIONS, AND TYPES


Data are physical phenomena chosen by convention to
represent facts or ideas. The same fact or idea can be represented
by a variety of different data. The common notion of data representing
the same fact or idea will be called a value.

Data values are grouped into classes called types. A type is
a named set of values. Each value is of one and only one type.

The operands that yield data values during execution are constants
(see Section 6),
variables
(see Section 13),
and expressions
(see Section 14).

Any value yielded by an operand during execution will be of one and
only one type. The operand type can be determined from the program
text without executing it.

Standard operations on values are denoted by symbols called operators.
New operations are described in terms of previously defined operations
by means of procedures
(see Section 16).

Every operation applies to operands of fixed types and delivers
results of fixed types.

The types integers, boolean, and character are standard types — types
that are available without being declared. All other types must be introduced
by means of type declarations.

5.1. Type declarations

    Type declaration:
     Enumeration type declaration # Record type declaration #
     Array type declaration # Set type declaration

A type declaration describes a new type which is either an enumeration
type
(see Section 7.6),
record type
(see Section 9),
array type
(see Section 10),
or set type
(see Section 11).


6. CONSTANTS


A constant is a fixed value of a fixed type.

    Constant symbol:
     Numeral # Truth symbol # Character symbol #
     Enumeration symbol # Constant symbol

A constant symbol denotes a constant and is either a numeral
(see Section 7.1),
a truth symbol
(see Section 7.3),
an enumeration symbol
(see Section 7.6),
or a constant synonym
(see Section 6.1).

6.1. Constant declarations

    Constant declaration list:
     'const' Constant declaration
      [';' Constant declaration]*
    Constant declaration:
     Constant synonym '=' Constant symbol
    Constant symbol:
     Name

Every constant declaration introduces a name, called a constant synonym,
to denote a constant. A constant declaration cannot be of the form
x = x where x is the synonym.

The scope rules
(see Section 4.3)
apply to declared constants. A constant
c declared in a module is exported to the immediately-surrounding
block by exporting the constant declaration list that introduces c
(see Section 4.4).

Example:

    const namelength = 12; on = true; last = '.';
     nl = char(10); lf = nl

7. ELEMENTARY TYPES


An elementary type consists of a finite set of successive
values, called elementary values.

The values of any elementary type can be mapped onto a finite set
of successive integer values (and vice versa). The integer value
that corresponds to an elementary value x is called
the ordinal value of x and is denoted int(x).

The elementary types comprise the standard types integer,
boolean, and character as well as the enumeration types introduced
by type declarations.

7.1. Type integer

The standard type integer is an elementary type denoted
by the standard name int. The integer values are a finite
set of successive whole numbers including both positive and negative
values. The range of integers is system-dependent. For any
integer value x we have int(x) = x.

    Numeral:
     Digit [Digit]*

A numeral is a conventional decimal notation for a non-negative
integer value. Negative integer values must be denoted by
expressions
(see Section 14).

Examples:

    0
    1351

7.2. Arithmetic operands

The arithmetic operators apply to operands of type
integer and yield a result of type integer. When applied
to two operands of type integer the operators +, -,
*, div, mod denote addition, subtraction,
multiplication, division, and modulo, respectively.
The results of
x div y
and
x mod y
are the truncated quotient of x divided by y
and the remainder of x div y. They satisfy
the relation
x = (x div y) * y + x mod y.

When applied to a single operand of type integer + and –
are conventional sign operators.

An arithmetic operation terminates if the result is within
the range of integers; otherwise, it fails.

7.3. Type boolean

The standard type boolean is an elementary type denoted by
the standard name bool.

    Truth symbol:
     'false' # 'true'

The truth symbols are standard names that denote the boolean
values. The boolean values have the ordinal values int(false) = 0
and int(true) = 1.

7.4. Boolean operators

The boolean operators not, and, or
denote negation, disjunction, and conjunction, respectively.
They apply to one or two operands of type boolean and yield
a result of type boolean according to the following rules:

    not false = true          not true = false
    x and false = false       x and true = x
    x or false = x            x or true = true

where x denotes an arbitrary boolean value. A boolean
operation always terminates.

7.5. Type character

The standard type character is an elementary type denoted by the
standard name char. The set of characters and their
ordinal values are system dependent
(see Section 2.2).

    Character symbol:
     Graphic symbol # Control symbol
    Graphic symbol:
     ''' Graphic character '''
    Control symbol:
     'char' '(' Numeral ')'

A character symbol denotes a value of type character. A graphic
symbol 'c' denotes the graphic character c.
A control symbol char(n) denotes the character with the
ordinal value n.

Examples:

    'a'
    '0'
    ';'
    char(10)

7.6. Enumeration types

    Enumeration type declaration:
     'enum' Type name '(' Enumeration symbol list ')'
    Enumeration symbol list:
     Enumeration symbol [',' Enumeration symbol]*
    Type name:
     Name
    Enumeration symbol:
     Name

An enumeration type declaration introduces a name, called a type name,
to denote an elementary type and introduces a list of names, called
enumeration symbols, to denote the successive values of the type.

The values of an enumeration type enum T(c0,c1,…,cn)
have the ordinal values
int(c0) = 0,
int(c1) = 1, …,
int(cn) = n.

The scope rules
(see Section 4.3)
apply to an enumeration type and its values. An enumeration type declared
in a module can be exported together with its values to the
immediately-surrounding block
(see Section 4.4).

Example:

     enum task(flow, scan, log)
     enum filekind(empty, scratch, ascii, code)

7.7. Elementary constructors

    Elementary constructor:
     Type name '(' Expression ')'

An elementary constructor denotes a mapping of the values
of one elementary type onto the values of a (usually different)
elementary type. The type name must denote an
elementary type and the expression must be of an elementary type.

The elementary constructor int(x) denotes the ordinal
value of an elementary value x of type T.
If y is the ordinal value of x,
that is int(x) = y, then T(y) = x.
For a value y of any elementary type we have T(y) =
T(int(y))
.

Examples:

    int(slot)
    bool(1 - x)
    char(x + int('0'))
    task(x)

7.8. Elementary relations

The relational operators =, <>, <, <=, >, >=
denote the relations equal, not equal, less, not greater,
greater, and not less. These operators apply to two operands
of the same elementary type and yield a result of type boolean.

These operators have their conventional meaning for operands
of type integer: they yield the value true if the operand values
satisfy the relations, and the value false
if they do not. If x and y are values
of another elementary type then x = y has
the same value as int(x) = int(y), and similarly
for the other relations.

These operations always terminate.


8. RANGES


A range is a finite set of successive elementary values of the same
type from a lower bound x to an upper bound y both included (where x <= y).
The type of the values is know as the range type.

    Range symbol:
     Lower bound ':' Upper bound
    Lower bound:
     Constant symbol
    Upper bound:
     Constant symbol

A range symbol denotes a range. The bounds are denoted by constant
symbols which must be of the same elementary type (the range type).

Ranges are used to define the possible index values of array types
(see Section 10).

Examples:

    1 : namelength
    false : true
    'a' : 'b'
    flow : log

9. RECORD TYPES


A record type consists of a finite set of values, called
record values. Each record value consists of a finite sequence of
other values known as fields. Each field is of some known
type. The set of record values consists of all the possible
sequences of the possible field values.

    Record type declaration:
     'record' Type name '(' Field list ')'
    Field list:
     Field group [';' Field group]*
    Field group:
     Field name [',' Field name]* ':' Field type
    Field name:
     Name
    Field type:
     Type name

A record type declaration introduces a type name to denote a record
type. The field list introduces names, called field names, to denote
the fields. A group of fields have the known type given by another type
name, called the field type.

A record type declaration cannot use its own type name as a field type.
The scope rules
(see Section 4.3)
apply to a record type and its fields.
A record type declared within a module can be exported to the
immediately-surrounding block
(see Section 4.4),
but the corresponding field names
remain local to the module and cannot be exported from it.

Examples:

      record semaphore(count : int)
      record time(hour, minute, second : int)
      record attributes(kind : filekind; address : int; protected : bool)
      record entry(id : name; attr : attributes)

9.1. Record constructors

    Record constructor:
     Type name '(' Expression list ')'
    Expression list:
     Expression [',' Expression]*

A record constructor denotes a record value of the type given by
the type name. The expression list must contain one expression for each
field of the record type. The order in which the expressions are listed
in the record constructor and the order in which the field names are listed
in the record type declaration define a one-to-one correspondence
between the expressions and the fields. The expressions must be of the same
types as the corresponding fields.

The result of executing a record constructor is a record value in
which the fields are the values obtained by evaluating the corresponding
expressions in the order written. The execution terminates if the
evaluation of the expressions terminates.

Examples:

    semaphore(0)
    time(x, y+5, 0)
    attributes(code, x, true)
    entry(name('edit'), attributes(code, x, true))

9.2. Record relations

The relational operators = and <> apply to operands of the same record
type and yield a result of type boolean. Two record values x and y
of the same type are equal (denoted x = y) if all the corresponding
fields of the values are equal. The relation x <> y has the same
value as not (x = y).

These operations always terminate.


10. ARRAY TYPES


An array type consists of a finite set of values, called
array values. Each array value consists of a finite sequence of other
values known as elements. The elements are of the same known type. The set
of array values consists of all the possible sequences of the possible
element values.

The elements are distinguished by their position in the array value.
The positions are denoted by the successive values in a range known as
the index range. The position of an element is called its index value.

An array type with n elements of type character is called a
string of length n.

    Array type declaration:
     'array' Type name '[' Index range ']'
      '(' Element type ')'
    Index range:
     Range symbol
    Element type:
     Type name

An array type declaration introduces a name to denote an
array type. The index range is given by a range symbol
(see Section 8).
The known type of the elements is given by another type name, called
the element type.

An array type declaration cannot use its own type name as the
element type. The scope rules
(see Section 4.3)
apply to an array type. An array type declared within a module can be exported
to the immediately-surrounding block
(see Section 4.4).

Examples:

    array name [1 : namelength] (char)
    array poll [false : true] (int)
    array timetable ['a' : 'b'] (time)
    array namelist [flow : log] (name)

10.1. Array constructors

    Array constructor:
     Type name '(' Expression list ')'

An array constructor denotes an array value of the type given by
the type name. The expression list
(see Section 9.1)
must contain one
expression for each element of the array value (unless the array type
is a string type). The order in which the expressions are listed
in the array constructor and the order in which the array elements
are arranged by the index values define a one to one correspondence
between the expressions and the elements. The expressions must be of the
element type given by the array type declaration.

An array constructor for a string type of length n
must contain m expressions of type character (where
1 <= m <= n). This is an abbreviation for an array value consisting
of the character values given by the m expressions followed
by n - m spaces.

The result of executing an array constructor is an array value in
which the elements are the values obtained by evaluating the corresponding
expressions in the order written. The execution terminates if the evaluation
of the expressions terminates.

Examples:

    name('do',nl,c)
    poll(x+1, y)
    timetable(time(12,30,0), time(x,y+5,0))
    namelist(name('flow'), name('scan'), name('log))

10.2. Array relations

The relational operators = and <> apply to operands of the same array
type and yield a result of type boolean. Two array values x and y of the
same type are equal (denoted x = y) if all the corresponding
elements of the values are equal. The relation x <> y has
the same value as not (x = y).

These operations always terminate.


11. SET TYPES


A set type consists of a finite set of values, called set values.
Each set value consists of a finite (possibly empty) set
of other values. These other values are known as
the members of the set value. The members are of the same known
elementary type, called the base type.

A member must have an ordinal number in the range 0 : setlimit
where the upper bound is a system-dependent integer called the set
limit
(see Sections 7, 8).

The range of possible members is called the base range of the set type.
The set of set values consists of all the possible subsets (including
the empty one) that can be formed from the values in the base range.

    Set type declaration:
     'set' Type name '(' Base type ')'
    Base type:
     Type name

A set type declaration introduces a type name to denote a set type.
The known base type is given by another type name and must be
elementary.

The scope rules
(see Section 4.3)
apply to a set type. A set type
declared within a module can be exported to the immediately-surrounding
block
(see Section 4.4).

Examples:

    set intset(int)
    set boolset(bool)
    set charset(char)
    set taskset(task)

11.1. Set constructors

    Set constructor:
     Type name ['(' Expression list ')']

A set constructor denotes a set value of the type given by the type name.
The expression list (if any) consists of one or more expressions
of the base type given by the set type declaration
(see Section 9.1).

The result of executing a set constructor is a set value in which
the members are the values obtained by evaluating the expressions in
the order written. The evaluation fails if any of the expression
values are outside the base range.

A set constructor without an expression list denotes the
empty set, which has no members.

Examples:

    intset
    boolset(x = y)
    charset('0123456789')
    taskset(scan, log)

11.2. Set relations

The relational operation in applies to operands v and x
where x denotes a set value of type T while v denotes an elementary
value of the base type. The relation v in x is
true if the value v is a member of the set x. The evaluation
of the relation fails if the value of v is outside the base range.
The empty set T has no members, that is (v in T) = false
for all values v in the base range.

The relational operators = and <> apply to operands x and y
of the same set type. The relation x = y is true if (v in x)
= (v in y) for all values v in the base range. The relation
x <> y has the same values as not (x = y). These operations
always terminate.

11.3. Set operators

The set operators +, -, * denote union, difference, and intersection,
respectively. These apply to operands x and y of the same set type
and yield a result of that type.

For any value v in the base range of the set type:

    v in (x+y)    means   (v in x) or (v in y)
    v in (x-y)    means   (v in x) and not (v in y)
    v in (x*y)    means   (v in x) and (v in y)

The operations always terminate.


12. CONSTRUCTORS

    Constructor:
     Elementary constructor # Record constructor #
     Array constructor # Set constructor

A constructor denotes a mapping of one or more values of fixed
types onto a value of a (usually different) type. It is either
an elementary constructor
(see Section 7.7),
a record constructor
(see Section 9.1),
an array constructor
(see Section 10.1),
or a set constructor
(see Section 11.1).


13. VARIABLES


A variable is a named entity that may assume any of the values of
a known type. The value of a variable may be used in expressions
(see Section 14)
to compute other values and may be changed by means of
assignments
(see Section 15.2).

A variable of a record or array type consists of a group of other
variables known as subvariables. A variable of an elementary type or a set
type has no subvariables. A variable that is not a subvariable
of any other variable is called a whole variable.

13.1. Variable declarations

    Variable declaration list:
     'var' Variable group [';' Variable group]*
    Variable group:
     Variable name [',' Variable name]* ':' Type name
    Variable name:
     Name

Every variable group in a variable declaration list introduces
one or more names, called variable names, to denote whole variables of the known
type given by the type name.

Other whole variables known as parameters and function variables are
introduced by procedures
(see Section 16).

The scope rules
(see Section 4.3)
apply to every whole variable.
A whole variable v declared in a module is exported to the
immediately-surrounding block by exporting the variable
declaration list that introduces v
(see Section 4.4).

Example:

    var x, y, size : int; full, free : bool; c, slot : char;
     job : task; s : semaphore; file : entry;
     answers : poll; schedule : timetable; tasks : namelist;
     months : intset; digits : charset;

13.2. Variable operands

    Variable symbol:
     Whole variable symbol # Subvariable symbol #
     Retyped variable symbol
    Whole variable symbol:
     Variable name # Function variable symbol
    Subvariable symbol:
     Field variable symbol # Indexed variable symbol

A variable symbol denotes a whole variable, a subvariable, or
a retyped variable
(see Section 13.5)
used as an operand.

A whole variable is denoted by a known variable name or by
a function variable symbol
(see Section 16.3).

A subvariable is denoted by a field variable symbol
(see Section 13.3)
or an indexed variable symbol
(see Section 13.4).

The evaluation of a variable symbol involves locating the corresponding
variable in the current context. This is called variable selection.
The selection of a whole variable always terminates. The selection
of a subvariable is described later.

If a variable symbol occurs within an expression
(see Section 14)
the corresponding variable is first selected and then a copy
of its value is obtained. This is called variable retrieval.
The retrieval terminates if the selection does.

Examples of whole variable symbols:

    x
    s
    file
    answers
    schedule
    tasks
    val empty

13.3. Field variables

A variable of a record type is called a record variable. It
contains a subvariable for each field of the record value. The
subvariables are known as field variables. Their types are the
corresponding field types given by the record type declaration.

    Field variable symbol:
     Record variable symbol '.' Field name
    Record variable symbol:
     Variable symbol

A field variable symbol v.f consists of a record variable symbol
v followed by a field name f.

A field variable is selected in two steps:

  1. The record variable is selected.
  2. The field value given by the field name is selected within
    the record variable.

The selection of the field variable terminates if the selected
of the record variable does.

If v denotes a record variable of type T then the relation

v = T(v.f1, v.f2, …, v.fm)

is true, where v.f1, v.f2, …, v.fm denotes the values of the field
variables of v.

Examples:

    s.count
    schedule.second
    file.attr.kind

13.4. Indexed variables

A variable of an array type is called an array variable. It contains
a subvariable for each element of the array value. The subvariables
are known as indexed variables. Their type is the element type
given in the array type declaration.

    Indexed variable symbol:
     Array variable symbol '[' Index expression ']'
    Array variable symbol:
     Variable symbol
    Index expression:
     Expression

An indexed variable symbol v[e] consists of an array variable symbol
v followed by an index expression e.
The index expression is an expression of the
same type as the index range given in the array type declaration.

An indexed variable is selected in three steps:

  1. The array variable is selected.

  2. The index expression is evaluated to obtain an index value.

  3. The indexed variable corresponding to the index value is
    selected within the array variable.

The selection of an indexed variable terminates if the selection
of the array variable terminates and if the evaluation of the index
expression yields an index value within the index range. The
selection fails if the index value is outside the index range.

If v denotes an array variable of type T then the relation

v = T(v[e1], v[e2], …, v[em])

is true where v[e1], v[e2], …, v[em] denote the values
of the indexed variables of v.

Examples:

    answers[false]
    schedule
    tasks[job][x+1]
    file.id[12]

13.5. Retyped variables

In most computers data values are held as binary numerals known as
stored values. The following describes a system depended operation
that only applies to computers in which stored values of the same
type occupy the same amount of storage.

If the stored values of two types occupy the same amount of
storage the types are said to be of the same length.

An operation known as retyping maps the values of one type
onto another type of the same length in such a way that the
corresponding values of the two types have the same stored values.

If x denotes a variable of type T1 then x : T2 denotes the
same variable considered to be of another type T2 of the
same length. The variable x : T2 is called a retyped variable.

A selection of possible subvariables of x : T2 proceeds as if
x was of type T2.

A retrieval of x : T2 yields a value of type T2 with the same
stored value as the value of x.

An assignment
(see Section 15.2)
to x : T2 of a value y of type
T2 assigns a value to x with the same stored value as the value of y.

    Retyped variable symbol:
     Variable symbol ':' Type name

A retyped variable is denoted by a variable symbol followed by a known
type name.

Example:
schedule : attributes


14. EXPRESSIONS

    Expression:
     Simple expression
      [Relational operator Simple expression]
    Relational operator:
     '=' # '<>' # '<' # '<=' # '>' # '>=' # 'in'
    Simple expression:
     [Sign operator] Term #
     Simple expression Adding operator Term
    Sign operator:
     '+' # '-'
    Adding operator:
     '+' # '-' # 'or'
    Term:
     [Term Multiplying operator] Factor
    Multiplying operator:
     '*' # 'div' # 'mod' # 'and'
    Factor:
     Simple operand # '(' Expression ')' #
     'not' Factor # Retyped factor
    Simple operand:
     Constant symbol # Constructor #
     Variable symbol # Procedure call

An expression denotes a rule for computing a value of a fixed
type known as the expression type. An expression consists of operands
denoting values and operators denoting operations on the values. Parentheses
may be used to prescribe the order in which the operators are to be applied
to the operands. The execution of an expression is known as its evaluation.

An operator denotes a standard operation on the values of one or two
operands. The same operator may stand for several different operations depending
on the operand types. The execution of an operator yields a single
value as described in Sections
7.2,
7.4,
7.8,
9.2,
10.2,
11.2
and
11.3.

Each operator restricts the operands to which it may be applied
to belong to certain types only. The syntactic rules for expressions, which
describe no restrictions arising from types, include many forms that are
invalid.

The value of an expression is found either as the value of
a simple expression or by applying a relational operator
to the values of two simple expressions.

The value of a simple expression is found either as the value of a term,
or by applying a sign operator to the value of a term, or by applying
an adding operator to the values of another simple expression and a term.

The value of a term is found either as the value of a factor,
or by applying a multiplying operator to the values of another term and a
factor.

The value of a factor is found either as the value of a simple operand,
or another expression, or by applying a not operator to the value of
another factor, or by evaluating a retyped factor
(see Section 14.1).

The value of a simple operand is found either as the value of a constant
(see Section 6),
a constructor
(see Section 12),
a variable
(see Section 13.2),
or a procedure call
(see Section 15.3).

Examples of simple operands:

    false
    attributes(code, x, true)
    schedule.second
    gcd(189, 215)

Examples of factors:

    ... all the examples above ...
    (1 <= x)
    not full
    s : int

Examples of terms:

    ... all the examples above ...
    5 * x div y
    (1 <= x) and (x <= namelength)

Examples of simple expressions:

    ... all the examples above ...
    -10
    x + y - 1

Examples of expressions:

    ... all the examples above ...
    1 <= x
    c in digits

14.1. Retyped expressions

If x denotes a value of type T1 then x : T2 denotes a value of type T2
with the same stored value as the value of x. The types T1 and T2
must be of the same length
(see Section 13.5).
The operand x : T2 is called a retyped factor. Its value is system dependent.

    Retyped factor:
     Factor ':' Type name

A retyped factor consists of a factor followed by a known type name.

Example:

    s : int

15. STATEMENTS

    Statement:
     Skip statement # Assignment statement #
     Procedure call # If statement #
     While statement # When statement #
     Concurrent statement
    Statement list:
     Statement [';' Statement]*

A statement denotes one or more operations and determines (at least
partially) the order in which these operations are to be executed.
A statement is either a skip statement
(see Section 15.1),
an assignment statement
(see Section 15.2),
a procedure call
(see Section 15.3),
an if statement
(see Section 15.4),
a while statement
(see Section 15.5),
a when statement
(see Section 15.6),
or a concurrent statement
(see Section 15.7).

A statement list denotes execution of a sequence of statements.

The statements of a statement list are executed one at a time
in the order written.

Examples of statement lists:

    full := false
    send(x); read(x)

15.1. Skip statements

    Skip statement:
     'skip'

The word symbol skip denotes the empty operation. The
execution of a skip has no effect and always terminates.

15.2. Assignment statements

    Assignment statement:
     Variable symbol ':=' Expression

An assignment statement denotes assignment of a value given by
an expression to a variable. The variable and the expression must be
of the same type.

An assignment statement is executed in three steps:

  1. The variable is selected.

  2. The expression is evaluated to obtain a value.

  3. The value is assigned to the variable.

An assignment to a subvariable of a whole variable assigns
a value to the subvariable without changing the values of the remaining
subvariables.

If v denotes a record variable of the type

      record T (f1 : T1; f2 : T2; ...; fm : Tm)

then

       v.f1 := e1    means    v := T(e1, v.f2, ..., v.fm)
       v.f2 := e2    means    v := T(v.f1, e2, ..., v.fm)
			  ...
       v.fm := em    means    v := T(v.f1, v.f2, ..., em)

where f1, f2, …, fm are the field names of the record type T
while e1, e2, …, em are expressions of the field type T1, T2, …, Tm.

Similarly, if v denotes an array of the type

      array T [i1 : im] (Te)

then

      v[i1] := e1    means    v := T(e1, v[i2], ..., v[im])
      v[i2] := e2    means    v := T(v[i1], e2, ..., v[im])
			      ...
      v[im] := em    means    v := T(v[i1], v[i2], ..., em)

where i1, i2, …, im are the index values of the array type T while
e1, e2, …, em are expressions of the element type Te.

Examples:

    x := x + 1
    c := char(x + int('0'))
    full := false
    job := log
    val empty := (size = 0)
    file := entry(name('edit'), attributes(code, x, true))
    s.count := s.count + 1
    schedule := time(12, 30, 0)

15.3. Procedure calls

    Procedure call:
     Procedure name ['(' Argument list ')']
    Argument list:
     Argument [',' Argument]*
    Argument:
     Value argument # Variable argument # Procedure argument
    Value argument:
     Expression
    Variable argument:
     Variable symbol
    Procedure argument:
     Procedure name

A procedure call denotes execution of a known procedure given by
the procedure name
(see Section 16).

The argument list denotes operands that may be operated upon by the
procedure. The argument list must contain one argument for each parameter
of the procedure. The order in which the arguments are written in the
procedure call and the order in which the parameters are listed in the procedure
declaration define a one to one correspondence between the arguments
and the parameters.

Each argument is either a value argument, a variable argument, or
a procedure argument.

A value argument must correspond to a value parameter and must be
an expression of the same type as the corresponding parameter.

A variable argument must correspond to a variable parameter and must be
a variable symbol of the same type as the corresponding parameter.

A procedure argument must correspond to a procedure parameter
and must be the name of a procedure with the same heading as the
corresponding parameter (apart from the choice of procedure and
parameter names).

The execution of a procedure call takes place in six steps:

  1. The parameters of the procedure called are created one at
    a time in the order listed:

    A value parameter is created as a fresh variable which is
    assigned the value obtained by evaluating the corresponding value argument.

    A variable parameter is created by selecting the corresponding
    variable argument.

    A procedure parameter is created by selecting the corresponding
    procedure argument and selecting a context associated with the
    argument (as described below).

  2. A new current context is formed from a context associated
    with the procedure called extended with the parameters.

    The procedure body is then executed as described in steps (3)-(5):

  3. The auxiliary entries declared in the procedure body are created
    and added to the current context. The initial values of the auxiliary
    variables are undefined.

  4. The local modules of the procedure are initialised one at a time
    in the order written. This extends the current context further as
    described in Section 4.4. The current context is then also
    attached as an attribute to all procedures declared in the
    body (and to all procedures declared in the local modules
    of the body).

  5. The statement part of the procedure body is executed.

  6. The old context, used prior to the call is re-established
    as the current context.

During the execution of the procedure body every operation
on a variable parameter stands for the same operation performed on
the corresponding variable argument,
and every call of a procedure parameter stands
for the same call of the corresponding procedure argument in the context
associated with the argument. These parameters are said to be bound
to the corresponding arguments during the execution of the
procedure body.

When a procedure call is used as a statement it must refer to a
general procedure
(see Section 16.1).

When a procedure call is used as an operand in an expression
it must refer to a function
(see Section 16.3).
The execution of a function computes a value of a fixed type given by
the procedure declaration.

Examples:

    init
    receive(x)
    gcd(189, 215)

15.4. If statements

    If statement:
     'if' Conditional statement list 'end'
    Conditional statement list:
     Conditional statement ['else' Conditional statement]*
    Conditional statement:
     Boolean expression 'do' Statement list
    Boolean expression:
     Expression

An if statement denotes a single execution of a conditional
statement list.

A conditional statement list denotes execution of one
of several conditional statements (or none of them). Each conditional
statement consists of an expression of type boolean and a statement list.

The execution of an if statement consists of executing the conditional
statement list once.

The execution of a conditional statement list consists of first
evaluating the boolean expressions one at a time in the order written
until one yielding the value true is found or until all have
been found the yield the value false. If the value obtained
from an expression is true then the statement list that follows
the expression is executed; otherwise, none of the statement
lists are executed. In the latter case, the statement lists are
said to be skipped.

Examples:

    if x mod y <> 0 do send(x) end

    if job = flow do flow_analysis
    else job = scan do alarm_scanning
    else job = log do data_logging
    else true do error end

15.5. While statements

    While statement:
     'while' Conditional statement list 'end'

A while statement denotes one or more executions of a
conditional statement list
(see Section 15.4).

The execution of a while statement consists of executing the conditional
statement list repeatedly until all the statement lists are skipped.

If statement lists continue to be executed forever then the execution cycles.

Examples:

    while x <> last do send(x); read(x) end

    while x > y do x := x - y
    else x < y do y := y - x end

15.6. When statements

    When statement:
      'when' Synchronized statement 'end'
    Synchronized statement:
     Conditional statement list

A when statement consists of a conditional statement list
known as a synchronized statement. This is a mechanism which can be
used to give concurrent processes exclusive access to
common variables when their values satisfy certain conditions.

A process executes a when statement in two phases:

  1. Synchronization phase: the process is delayed until no other process
    is executing the critical phase of a when statement.

  2. Critical phase: the synchronized statement is executed as
    described in Section
    15.4.
    If the statement lists are skipped
    the process returns to the synchronizing phase;
    otherwise the execution of the when statement is terminated.

Each synchronizing phase of a process lasts a finite time only
provided that the critical phase of all other concurrent processes
terminate.

Concurrent processes are further discussed in Section
15.7.

Examples:

    when true do s.count := s.count + 1 end

    when s.count > 0 do s.count := s.count - 1 end

    when free do x := 1; free := false
    else x > 0 do x := x + 1 end

15.7. Concurrent statements

    Concurrent statement:
     'cobegin' Process statement list 'end'
    Process statement list:
     Process statement ['also' Process statement]*
    Process statement:
     Process constant 'do' Statement list
    Process constant:
     Constant symbol

A concurrent statement denotes execution of a process statement list.
The process statement list consists of process statements to be
executed simultaneously. Each process statement describes a process by
means of a constant symbol (the process constant) and a statement
list. The type and meaning of process constants are system dependent.
They may, for example, be used to specify the amount of storage
required by a process or the processor that must perform the process.

The execution of a concurrent statement consists of executing the
process statements simultaneously. The relative ordering of operations
performed by different processes is unspecified. The execution of such
operations may generally overlap in time (unless they are described by
when statements). The execution of a concurrent statement terminates
when all the concurrent processes terminate.

When a process reaches a concurrent statement the current context
of that process becomes the initial context of each of the concurrent
processes.

The variable instances in the initial context of the processes are called
common variables because they can be operated upon by all the
processes. The common variables enable processes to exchange
values during their execution.

When a process calls one or more procedures its its initial
context is extended with variable instances that are inaccessible
to the other processes. They are called the private variables of the
process.

Two common variables are said to be disjoint if they are different
variable instances or if none of them is a subvariable of the other;
otherwise, they are called intersecting variables.

If each of several concurrent processes only operates on
private variables and disjoint, common variables then the effect
of executing a concurrent statement is the same as the effect
of executing the process statements one at a time in any order.

But, if concurrent processes operate on intersecting, common
variables then the effect of executing a concurrent statement is generally
unpredictable since nothing is known about the order in which the processes
operate on these variables. However, by restricting the operations on
intersecting, common variables to well-defined disciplines
under the control of modules
(see Section 4.4),
procedures
(see Section 16),
and when statements
(see Section 15.6)
it is possible to formulate concurrent statements that make predictable
use of such variables. The theories used to reason about concurrent
statements, when statements, and common variables are beyond
the scope of this report.

When concurrent processes terminate, the execution of
all procedures called by these processes has also ended. Consequently,
the private variables of the processes have disappeared leaving
only the common variables in the context. The execution of the
program now continues as a single process in the current context
of common variables.

The meaning of variable retrieval
(see Section 13.2)
and assignment
(see Section 15.2)
defined earlier is valid only if these operations
are performed one at a time on a given variable. Concurrent processes
can ensure that this assumption is satisfied by performing all
operations on intersecting, common variables within when statements.
The assumption is always satisfied for operations on private variables
since each of these variables can be used only by a single process
which performs all its operations (including those on variables) one
at a time.

If any of the concurrent processes reaches a concurrent
statement the execution fails.

Examples:

    cobegin 1 do print end

    cobegin 1 do producer
    also 2 do consumer end

    cobegin 1 do node(b[0], b[1])
    also 2 do node(b[1], b[2])
    also 3 do node(b[2], b[0])
    also 4 do send(b[0], 9999) end

16. PROCEDURES

    Procedure declaration:
     Complete procedure declaration # Split procedure part #
      Library procedure declaration

A procedure declaration describes a named procedure. It is either
a complete procedure
(see Section 16.1),
a split procedure
(see Section 16.4),
or a library procedure
(see Section 16.5).

A procedure declared in a module can be exported to the
immediately-surrounding block
(see Section 4.4).

16.1. Complete procedures

    Complete procedure declaration:
     Procedure heading Procedure body
    Procedure heading:
     'proc' Procedure name ['(' Parameter list ')']
       [':' Function type]
    Procedure name:
     Name
    Function type:
     Type name
    Procedure body:
     [Declaration]* Statement part

A complete procedure declaration defines a procedure completely.
The procedure heading introduces a name, called a procedure name, to denote
the procedure and describes the parameters by a parameter list
(see Section 16.2).
If the heading includes a known type name, called the function
type, the the procedure is a function
(see Section 16.3);
otherwise, it is a general procedure.

The procedure body consists of declarations
(see Section 4.2)
which describe auxiliary entities used by the procedure and a statement
part
(see Section 4.4)
which describes a sequence of operations on the
parameters and auxiliary entities.

A procedure acts as a block
(see Section 4.3).
The parameters and
auxiliary entities are local to the procedure and can only be used
within the procedure body. The procedure name is local to the
immediately-surrounding block.

The execution of the procedure body is invoked by executing a procedure
call
(see Section 15.3).

A procedure may call itself recursively.

Examples:

    proc init begin full := false end

    proc consumer
    var y : char
    begin receive(y);
      while y <> last do
        write(y); receive(y)
      end;
      write(y); write(nl)
    end

    proc wait(var s : semaphore)
    begin when s.count > 0 do s.count := s.count - 1 end end

    proc push(c : int)
    begin size := size + 1; lifo[size] := c end

    proc gcd(x, y: int): int
    begin
      while x > y do x := x - y
      else x < y do y := y - x end;
      val gcd := x
    end

16.2. Parameters

    Parameter list:
     Parameter group [';' Parameter group]*
    Parameter group:
     Value parameter group # Variable parameter group #
     Procedure parameter
    Value parameter group:
     Variable group
    Variable parameter group:
     'var' Variable group
    Procedure parameter:
     Procedure heading

A parameter list describes one or more group of parameters.

A value parameter group introduces a group of local variables
known as value parameters. Each value parameter is assigned the
value of an argument before the procedure body is executed.

A variable parameter group introduces a group of local variables known
as variable parameters. Each variable parameter denotes a variable
argument which is selected before the procedure body is executed.

A procedure parameter introduces a procedure heading to denote
a procedure argument and its associated context which are selected before
the procedure body is executed.

Examples:

    x, y : int
    var s : semaphore
    id : name; proc lookup(x : name; var y : attributes)

16.3. Functions

A function is a procedure that describes the computation of a single
value of a fixed type (the function type). A function call can be used as
an operand in an expression. The procedure body of a function assigns the value
of the function to a local variable, called the function variable. The last
value assigned to this variable during the execution of the procedure
body becomes the value of the procedure call that invoked
the execution.

    Function variable symbol:
      'val' Procedure name

A function variable is denoted by the procedure name of the given
function. The function variable is only known in the body of the function.

Examples of a function variable symbol:

    val gcd

16.4. Split procedures

In a procedure that contains mutually recursive procedures some procedure
calls must precede the corresponding procedure bodies in the program text.
A procedure that is called in this way must have its declaration split into
two parts: a predeclaration that precedes these calls and a postdeclaration
that follows them.

    Split procedure part:
     Procedure predeclaration # Procedure postdeclaration
    Procedure predeclaration:
     'pre' Procedure heading
    Procedure postdeclaration:
     'post' Complete procedure declaration

A procedure predeclaration is a procedure heading that describes how
to call a split procedure. The procedure name introduced by the procedure
heading can be used in the program text that extends from the predeclaration
to the end of the block in which the predeclaration appears.

A procedure postdeclaration is a complete procedure declaration that
describes how to call and execute a split procedure. The pre- and post declarations
must appear in the same block in that order but may be separated by other
declarations in the same block. The procedure headings of the pre- and
post declarations must be identical.

A split procedure declared in a module is exported to the
immediately-surrounding block
(see Section 4.4)
by exporting the corresponding predeclaration.

Example:

    pre proc variable_symbol(succ : symbols)
    ... other declarations ...
    post proc variable_symbol(succ : symbols)
    begin ... end

16.5. Library procedures

A program library is a group of procedures that can be called
by a program without being included in the program. The library
procedures, which have the form of separate programs
(see Section 17),
cannot use global variables or global procedures
(see Section 4.3).

A program may call a library procedure if the program contains a declaration
of the procedure heading and a description of where the procedure body
is located in the library.

    Library procedure declaration:
     'lib' Procedure heading '[' Library key ']'
    Library key:
     Expression

A library procedure declaration describes a library procedure by
means of a procedure heading and a library key. The library key
is an expression that indicates the location of
the procedure body in the library. The type of the expression is system
dependent.

When the library procedure is called the library key is
evaluated and used to locate the procedure body in the library.
The execution of the body then proceeds as described earlier
(see Section 15.3).

The procedure heading used in the program and the procedure heading used
in the library to describe the procedure must be the same.

Example:

    lib proc edit(source, dest : name) [name('edit')]

17. PROGRAMS

    Program:
     [Constant declaration list # Type declaration]*
      Complete procedure declaration

A program consists of a declaration of constants, types, and a single,
complete procedure
(see Sections 6.1,
5.1,
and
16.1).

A program acts as a block
(see Section 4.3).
The declared entities
can be used throughout the program.

The execution of the program consists of executing a call
of the procedure in a system dependent context. Initially, the program
is executed as a single process in the given context.

Example:

      "This program defines two processes connected by a buffer module.
      A producer process reads a sequence of characters terminated by
      a period and sends them through the buffer to a consumer process
      that receives the characters and writes them. The procedures for
      reading and writing characters are system dependent parameters
      of the program."
    
    const last = '.'; nl = char(10)
    
    proc copier(proc read(var c : char); proc write(c : char))
    
      module
        var slot : char; full : bool
    
      * proc send(c : char)
        begin when not full do slot := c; full := true end end
    
      * proc receive(var c : char)
        begin when full do c := slot; full := false end end
    
      begin full := false end
    
      proc producer
      var x : char
      begin read(x);
        while x <> last do
          send(x); read(x)
        end;
        send(x)
      end
    
      proc consumer
      var y : char
      begin receive(y);
        while y <> last do
          write(y); receive(y)
        end;
        write(y); write(nl)
      end
    
    begin
      cobegin 1 do producer
      also 2 do consumer end
    end

18. SYNTAX SUMMARY


The following is a list of the syntactic forms of the language.
Trivial syntactic forms have been omitted. Some forms have been
eliminated by replacing all references to their names with the
corresponding syntax expressions. Other forms that were defined
recursively earlier have been replaced by equivalent ones that are
defined iteratively. Separators and character strings, which are
alternative representations of other syntactic forms, are defined
elsewhere
(see Sections 2.4
and
2.5).

Name:

Letter [Letter # Digit # ‘_’]*

Numeral:

Digit [Digit]*

Character symbol:

”’ Graphic character ”’ # ‘char’ ‘(‘ Numeral ‘)’

Constant symbol:

Constant name # Numeral # Character symbol

Constant declaration:

Constant name ‘=’ Constant symbol

Constant declaration list:

‘const’ Constant declaration
[‘;’ Constant declaration]*

Enumeration symbol list:

Constant name [‘,’ Constant name]*

Enumeration type declaration:

‘enum’ Type name ‘(‘ Enumeration symbol list ‘)’

Field group:

Field name [‘,’ Field name]* ‘:’ Type name

Field list:

Field group [‘;’ Field group]*

Record type declaration:

‘record’ Type name ‘(‘ Field list ‘)’

Range symbol:

Constant symbol ‘:’ Constant symbol

Array type declaration:

‘array’ Type name ‘[‘ Range symbol ‘]’ ‘(‘ Type name ‘)’

Set type declaration:

‘set’ Type name ‘(‘ Type name ‘)’

Type declaration:

Enumeration type declaration # Record type declaration #
Array type declaration # Set type declaration

Variable group:

Variable name [‘,’ Variable name]* ‘:’ Type name

Variable declaration list:

‘var’ Variable group [‘;’ Variable group]*

Parameter group:

[‘var’] Variable group # Procedure heading

Parameter list:

Parameter group [‘;’ Parameter group]*

Procedure heading:

‘proc’ Procedure name [‘(‘ Parameter list ‘)’]
[‘:’ Type name]

Complete procedure declaration:

Procedure heading [Declaration]* Statement part

Procedure declaration:

‘pre’ Procedure heading #
[‘post’] Complete procedure declaration #
‘lib’ Procedure heading ‘[‘ Expression ‘]’

Module declaration:

‘module’ [Declaration # Exported declaration]*
Statement part

Declaration:

Constant declaration list # Type declaration #
Variable declaration list # Procedure declaration #
Module declaration

Exported declaration:

‘*’ Declaration

Variable symbol:

Variable name # ‘val’ Procedure name #
Variable symbol ‘.’ Field name #
Variable symbol ‘[‘ Expression ‘]’ #
Variable symbol ‘:’ Type name

Expression list:

Expression [‘,’ Expression]*

Constructor:

Type name [‘(‘ Expression list ‘)’]

Factor:

Constant symbol # Constructor # Variable symbol #
Procedure call # ‘(‘ Expression ‘)’ #
‘not’ Factor # Factor ‘:’ Type name

Multiplying operator:

‘*’ # ‘div’ # ‘mod’ # ‘and’

Term:

Factor [Multiplying operator Factor]*

Adding operator:

‘+’ # ‘-‘ # ‘or’

Simple expression:

[‘+’ # ‘-‘] Term [Adding operator Term]*

Relational operator:

‘=’ # ‘<>’ # ‘<‘ # ‘<=’ # ‘>’ # ‘>=’ # ‘in’

Expression:

Simple expression
[Relational operator Simple expression]

Argument:

Expression # Variable symbol # Procedure name

Argument list:

Argument [‘,’ Argument]*

Procedure call:

Procedure name [‘(‘ Argument list ‘)’]

Conditional statement:

Expression ‘do’ Statement list

Conditional statement list:

Conditional statement [‘else’ Conditional statement]*

Process statement:

Constant symbol ‘do’ Statement list

Process statement list:

Process statement [‘also’ Process statement]*

Statement:

‘skip’ # Variable symbol ‘:=’ Expression #
Procedure call #
‘if’ Conditional statement list ‘end’ #
‘while’ Conditional statement list ‘end’ #
‘when’ Conditional statement list ‘end’ #
‘cobegin’ Process statement list ‘end’

Statement list:

Statement [‘;’ Statement]*

Statement part:

‘begin’ Statement list ‘end’

Program:

[Constant declaration list # Type declaration]*
Complete procedure declaration



ACKNOWLEDGMENT

The programming language Edison was developed for a multiprocessor system built by Mostek Corporation. This language report was first
written in January 1979 and was then revised in July 1979, January 1980, and September 1980. In writing (and rewriting) this report I have benefitted greatly from the constructive criticism of Peter Naur. I have also received helpful suggestions from Jon Fellows, David Gries, and Habib Maghami.