by Per Brinch Hansen
Computer Science Department, University of Southern California, Los Angeles, California 900007, USA
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
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.
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.
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:
[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 # '_']*
[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']
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
'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'
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.
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.
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"
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'
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:
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.
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
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.
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.
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:
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:
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.
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:
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
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.
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).
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).
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
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.
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
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.
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.
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.
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)
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)
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)
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.
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
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)
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))
These operations always terminate.
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)
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))
These operations always terminate.
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)
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)
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.
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.
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).
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.
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;
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
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:
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
Examples:
s.count
schedule[c].second
file.attr.kind
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:
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
Examples:
answers[false]
schedule[c]
tasks[job][x+1]
file.id[12]
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[c] : attributes
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[c].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
Retyped factor:
Factor ':' Type name
A retyped factor consists of a factor followed by a known type name.
Example:
s : int
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)
Skip statement:
'skip'
The word symbol skip denotes the empty operation. The execution of a skip has no effect and always terminates.
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:
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[c] := time(12, 30, 0)
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:
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).
The procedure body is then executed as described in steps (3)-(5):
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)
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
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
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:
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
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
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).
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
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)
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
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
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')]
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
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.