The Edison System, 1982, is comprised of both an operating system and programming environment. The system language, also named Edison, is simple yet powerful. The Edison language is comprised of only a few basic commands and structures. However, these basic fundamentals have been carefully chosen to establish the necessary foundation to produce powerful and extensive applications. The Edison System possesses adequate development facilities, yet is contained in a very small quantity of code. Per Brinch Hansen’s final development system for a PDP-11 contains approximately 10,000 lines of program text. This text includes the operating system, the compiler, the editor, the diskette formatting program, necessary assembly code, and other utility programs. This establishes a powerful yet small environment for the development of concurrent programs.
Available here complete! In parts, partially scanned like introduction and Edison Programs, partially as separate articles in PDF or HTMl format.
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.
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 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 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.
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.
The character ” cannot occur within a comment.
- 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:
- The record variable is selected.
- 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[c].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:
- The array variable is selected.
- The index expression is evaluated to obtain an index value.
-
- 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[c]
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:
'=' # '&lt;&gt;' # '&lt;' # '&lt;=' # '&gt;' # '&gt;=' # '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 &lt;= x)
not full
s : int
Examples of terms:
... all the examples above ...
5 * x div y
(1 &lt;= x) and (x &lt;= namelength)
Examples of simple expressions:
... all the examples above ...
-10
x + y - 1
Examples of expressions:
... all the examples above ...
1 &lt;= 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:
- The variable is selected.
- The expression is evaluated to obtain a value.
-
- 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[c] := 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:
- 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).
- 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):
- 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.
-
- 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).
-
- The statement part of the procedure body is executed.
-
- 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 &lt;&gt; 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 &lt;&gt; last do send(x); read(x) end
while x &gt; y do x := x - y
else x &lt; 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:
- Synchronization phase: the process is delayed until no other process
is executing the critical phase of a when statement.
- 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 &gt; 0 do s.count := s.count - 1 end
when free do x := 1; free := false
else x &gt; 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 &lt;&gt; last do
write(y); receive(y)
end;
write(y); write(nl)
end
proc wait(var s : semaphore)
begin when s.count &gt; 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 &gt; y do x := x - y
else x &lt; 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 &lt;&gt; last do
send(x); read(x)
end;
send(x)
end
proc consumer
var y : char
begin receive(y);
while y &lt;&gt; 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.
Pascal-S is a subset of Pascal selected for introductory programming courses. The implementation is especially designed to provide comprehensive and transparant error diagnostics and economical service for small jobs.
