S-algol Reference Manual Ron Morrison
University of St. Andrews, North Haugh, Fife, Scotland. KY16 9SS
CS/79/1
1 Contents Chapter 1.
Preface
2.
Syntax Specification
3.
Types and Type Rules 3.1 Universe of Discourse 3.2 Type Rules
4.
Literals 4.1 Integer Literals 4.2 Real Literals 4.3 Boolean Literals 4.4 String Literals 4.5 Pixel Literals 4.6 File Literal 4.7 pntr Literal
5.
Primitive Expressions and Operators 5.1 Boolean Expressions 5.2 Comparison Operators 5.3 Arithmetic Expressions 5.4 Arithmetic Precedence Rules 5.5 String Expressions 5.6 Picture Expressions 5.7 Pixel Expressions 5.8 Precedence Table 5.9 Other Expressions
6.
Declarations 6.1 Identifiers 6.2 Variables, Constants and Declaration of Data Objects 6.3 Sequences 6.4 Brackets 6.5 Scope Rules
7.
Clauses 7.1 Assignment Clause 7.2 if Clause 7.3 case Clause 7.4 repeat ... while ... do ... Clause 7.5 for Clause 7.6 abort Clause
8.
Procedures 8.1 Declarations and Calls 8.2 Forward Declarations
2 9.
Aggregates 9.1 Vectors 9.1.1 Creation of Vectors 9.1.2 upb and lwb 9.1.3 Indexing 9.1.4 Equality and Equivalence 9.2 Structures 9.2.1 Creation of Structures 9.2.2 Equality and Equivalence 9.2.3 Indexing 9.3 Images 9.3.1 Creation of Images 9.3.2 Indexing 9.3.3 Depth Selection 9.3.4 Equality and Equivalence
10. Input and Output 10.1 Input 10.2 Output 10.3 i.w, s.w and r.w 10.4 End of File 11. Standard Procedures and Identifiers 11.1 Standard Procedures 11.2 Standard Identifiers 11.3 S-algol Prelude 12. References
Appendices I II III
S-algol Syntax S-algol Type Rules Program Layout
3 1.
Preface
Programming language design is probably the most emotive subject in Computational Science today. Nearly everyone uses a programming language and most people have something to say about their design. S-algol is presented as a member of a family of languages in the algol tradition that are constrained by a design methodology. This design methodology is based on the belief that most programming languages are too big and intellectually unmanageable. In addition it is believed that these problems arise in part from the languages being too restrictive. The number of rules to define a language increases when a general rule has additional rules attached to constrain its use in certain cases. Ironically these additional rules usually make the language less powerful. Power through simplicity, simplicity through generality is the guiding tenet. The design methodology is based on three semantic principles which can be attributed to Strachey [9] and Landin [5] and later developed by Tennent [10] and Morrison [7]. These are
(a)
The principle of data type completeness
(b)
The principle of abstraction
(c)
The principle of correspondence
The principle of data type completeness states that the rules for using data types must be complete with no gaps. This does not mean that all operators in the language need be defined on all data types but rather that general rules have no exceptions. Examples of lack of completeness can be seen in Pascal [12], for example, where only some data types are allowed as members of sets. The Principle of Data Type Completeness is bound to lead to simpler languages since it avoids the complexity of special cases. Abstraction is a process of extracting the general structure to allow the inessential details to be ignored. It is a facility well known to mathematicians and programmers since it is usually the only tool they have to handle complexity. The principle of abstraction when applied to language design is invoked by identifying the semantically meaningful syntactic categories in the language and allowing abstractions over them. The most familiar form of abstraction is the function which is an abstraction over expressions. Finally, the principle of correspondence states that the rules for introducing and using names should be the same everywhere in a program. In particular there should be a one to one correspondence between introducing names in declarations and introducing names as parameters. Armed with the above rules the language may be designed as follows Data Types Decide which data types, both simple and compound, are required by the language and define the operations on these data types. The flavour of the language will be determined by the data objects it can manipulate. The principle of data type completeness is invoked to ensure that all data objects have the same civil rights. Ignoring the principle means introducing rules to handle exceptions thus making the language more complex. For example, if arrays are allowed then arrays of arrays should be allowed as should expressions and functions with array results.
4 The Store Introduce the store, if any, and the manner in which it may be used. First of all the relationship between the store and the data types should be defined. This includes the implementation of pointers, data locations and protection on these locations. For example, constants may be regarded as storage locations which may not be updated [4]. The introduction of the store forces consideration of the language control structures. The designer can take his pick and is well advised to read the excellent paper by Ledgard and Marcotty [6] on the subject. Abstraction Tennent [10] has suggested that the method of applying the principle of abstraction is to identify the semantically meaningful syntactic categories and invent abstractions for each. This he does for Pascal and proposes some extensions to complete the abstractions. However, he points out that it is not always an easy matter to identify these categories in the first place. Examples of abstractions are functions which are abstractions over expressions and procedures which are abstractions over statements. An important point about abstractions is that they may be parameterised. Declaration and Parameters Invent the declarations and the parametric objects together. There must be a one to one correspondence between the two. This does not mean that they necessarily have the same syntax but that for every type of declaration there is an equivalent parametric type. Parameter passing modes are also included in this correspondence. For example, the declarative equivalent of call by value is an initialising declaration. If functions, record classes etc can be declared then they can be passed as parameters even though they are not defined as data objects in the language. Finally, if the language has a facility to define new data types and give them a name then the type can be passed as a parameter. Input and Output The I/O models for most high level languages tend to reflect the environment in which they were designed. Some attempts have been made to design and implement comprehensive I/O systems. Unfortunately where it has not been tied to particular hardware it has never been very successful. Nowhere else in the design of a programming language does the hardware intervene as much as it does in the I/O system. When a new I/O device becomes available the language must be able to make use of it. Of course, this situation is hopeless and perhaps the wisest approach to I/O is to allow the implementor to deal with it for a particular environment, as the Algol 60 designers proposed. Iterate Re-evaluate the language and correct or justify any idiosyncrasies in the design. Hopefully the design process will converge. Concrete Syntax The final stage of language design is to propose a concrete syntax. Ideally different groups of workers could have a different syntax. However, there are many users who do not wish to design their own syntax and so the language must provide at least one possibility. It seems very obvious to say that the syntax should be simple and easy to learn. That may be so but there is no doubt that some of the success of the language depends on the cosmetics. Also, a carefully chosen syntax can ease the problem of compilation.
5
How often the rules can be broken is for the designer's own conscience. However, every time the rules are broken the language becomes more complex. The rules were introduced to help design simpler and more intellectually manageable languages and should only be ignored with great care. S-algol is the first of the family of algols to be produced under this design methodology. It reflects my own personal preference for data objects and syntax. It also ignores the principle of abstraction with regard to sequencers and declarations. However there are no exceptions to the principle of correspondence or the principle of data type completeness in the language. I see this as the strength of the language. A number of people must be thanked for their help with the S-algol project. Firstly, Jack Cole whose enthusiasm and encouragement were responsible for the development of the system. Peter Bailey must be thanked for his help in testing the initial system on the PDP11 and in proof reading the original manual, as well as his enormous willingness to help when difficulties arose. Pete also wrote the VAX interpreter with Paul Maritz and the S-algol code generators. Paul Maritz implemented S-algol on the Zilog Z80 and pointed out a discrepancy in the application of the principle of correspondence to the language. Paul must also be blamed for the old binder for separately compiled modules. Fred Brown implemented a fast version of the Outline graphics for the Z80. Mike Livesey must be thanked for our discussions of the semantic principles on which the language is based and David Turner, now in Canterbury, with whom I started on language design deserves a special mention for his contribution [11]. Tony Davie, Michael Weatherill, Hamish Gunn and Ian Sommerville also may useful comments during the early design and implementation of S-algol. Tony also made numerous comments for improving this reference manual. In 1983, S-algol was used as a basis for PS-algol as part of the research in the PISA project. Al Dearle wrote versions of the interpreter in C and altered the compiler to generate new object code. It is on these versions that Dave Munro tailored the system to fit into the Macintosh environment. For this he rewrote the compiler in C, adapted the interpreter and surrounded it all with a Mac environment. To the language he added the raster graphics facilities of PS-algol [8] built by Al & Fred [2]. In parallel with this Dave made an equivalent system available on the SUN workstations. Al, Ray Carrick and Tony Davie have now written an introductory text based on S-algol. I hope you enjoy reading it and using the system. Ron Morrison 18-9-88
6 2.
Syntax Specification
It is important that a programming language can be formally defined since it gives implementors a standard to work on. There are two levels of definition, syntactic and semantic. A formal semantic description, a denotational semantics, of S-algol is given by Adamson [1]. Here we will deal with the formal syntactic rules giving an informal semantic description of the syntactic categories. That is, we will define the set of all syntactically legal S-algol programs remembering that the meaning of any one of these programs is defined by the semantics. To define the syntax of a language we need another notation which we will call a meta language and in this case we choose a variation of Backus-Naur form. The syntax of S-algol is specified by a set of rules or productions as they are normally called. Each production specifies the manner in which a particular syntactic category (e.g. a clause) can be formed. The syntactic category name is enclosed in the meta symbols '<' and '>' thus distinguishing it from names or reserved words in the language. These syntactic categories can be mixed in productions with terminal symbols which are actual symbols of the language itself. Thus, by following the productions until we have only terminal symbols, we can derive legal programs. We can also use the productions in a compiler to check that a program is legal and a very efficient method of doing this, called Recursive Descent is described by Davie & Morrison [3]. Other meta symbols include '|' which allows a choice in a production. The square brackets '[' and ']' are also used in pairs to denote an object is optional. When used with a '*' we have a zero or many times repetition. You should not confuse the meta symbols '|','<', '>', '*', and '[', ']' with the actual symbols in S-algol and we will be careful to keep the two concepts completely separate in our description. In the syntactic description of S-algol these symbols are defined by the following non-terminal symbols:
::=
|
::=
<
::=
>
<star>
::=
*
::=
[
::=
]
As you may expect with any reasonable programming language, the productions for S-algol are recursive which means that there are an infinite number of legal S-algol programs. However the syntax of S-algol can be described in about 60 productions. We will break ourselves in gently with an example.
::=
[]
::=
[]*
::=
+|-
::=
1|2|3|4|5|6|7|8|9|0
The above syntax indicates that an integer can be formed as an optional + or - followed by one or many digits. The full context-free syntax of S-algol is given in Appendix I.
7 3.
Types and Type Rules
The S-algol type system is based on the notion of types as sets of objects from the value space. These sets may be built in, like integer, or they may be formed by using one of the built in type constructors, like structure. The constructors obey the Principle of Data Type Completeness. That is, where a type may be used in a constructor, any type is legal without exception. This has two benefits. Firstly it allows a very rich type system to be described using a small number of defining rules since all the rules are very general without exception to them. This reduces the complexity of the defining rules. The second benefit is that the type constructors are as powerful as they can be since there is no way to restrict their domain. This increases the power of the language. 3.1
Universe of Discourse
There is an infinite number of data types in S-algol defined recursively by the following rules. 1.
The scalar data types are integer, real, boolean, string, picture, pixel and file.
2.
#pixel is the type of an image made up of pixels arranged as a rectangular matrix.
3.
For any data type T, *T is the data type of a vector with elements of type T.
4.
The data type pntr comprises a structure with any number of fields, and any data type in each field.
In addition to the above data types there is a number of other objects in S-algol to which it is convenient to give a type in order that the compiler may check their use for consistency.
5.
The type of a procedure with parameters T1,...,Tn and result type Tm is (T1,...,Tn > Tm).
6.
Clauses which yield no value are of type void.
7.
The class of a structure with fields of type T1,...,Tn is of type (T1 ,...,Tn )-structure and its fields are of type Ti-field.
The universe of discourse of the language is defined by the closure of rules 1 and 2 under the recursive application of rules 3 and 4.
8 3.2
Type Rules
The type rules form a second set of rules to be used in conjunction with the context free syntax to define well formed programs. The generic types that are required for the formal definition of S-algol can be described by the following: type arith
is
type or dere d is
arith | strin g string
type wr itea ble
is
type liter al
wr itea ble b le | pixe l | p n tr | f ile
is
in t | rea l
or dere d | bo ol
type im ag e
is
type no nv oid is
litera l | p ic | ima ge | ve ctor
type ve ctor
*no nvo *non vo id | *cn on vo id
type typ e
is
is
#p ixe l | #c p ix el
no nnv void oid | v oid
For example, in the above, the generic arith can be either an in t or a real, real representing the types integer and real in the language. In the type rules, the language types and generic types are written in shadow font to distinguish them from the reserved words. To check that a syntactic category is correctly typed the context free syntax is used in conjunction with a type rule. For example, the type rules for the two-armed if clause is t : ty pe , if : bool type boo l then : t else : t => t This rule may be interpreted as follows. t is given as a type from the table above. That is, it can be any type including void. Following the comma, the type rule states that the reserved word if may be followed by a clause which must be of type boolean. This is indicated by : bool. bool The then and else alternatives must have clause of type t, t whichever type it is. That is, both alternatives must have the same type. The resultant type, indicated by => , of this production is also t , the same as the alternatives. The type rules will be used throughout this manual, in conjunction with the context-free syntax rules to describe the language. A complete set of type rules for S-algol is given in Appendix II.
9 4.
Literals
Literals are one of the basic building blocks of a program and allow values to be introduced. A literal is defined by
4.1
<exp6>
::=
::=
| | | <string_literal> | | |
Integer Literals
These values of type int are defined by
::=
[]
::=
[]*
::=
+|-
=>
int
An integer literal is one or more digits possibly preceeded by a sign. e.g. 1
4.2
0
-1256
8797
Real Literals
These are of type real and are defined by
::=
.[][e< integer_literal >]
= > real
Thus, there are a number of ways of writing a real literal. For example 1.2 1.
3.1e2 5.e5 3.4e-2 3.4e+4
3.1e-2 means 3.1 times 10 to the power -2 (i.e. 0.031) 4.3
Boolean Literals
There are only two literals of type bool. They are the symbols true and false. They may be used with obvious meaning when a boolean literal is required.
4.4
::=
true | false
=>
bo ol
String Literals
A string literal is a sequence of characters in the character set (ASCII) enclosed by double quotes. The syntax is
10 <string_literal> ::= <special_character> <special_follow>
<double_quote>[]*<double_quote> ::= any ascii character except ' or " | <special_character> ::= <single_quote><special_follow> ::= n | p | o | t | b | <single_quote> | <double_quote>
<string_literal> =>
str ing
The empty string is denoted by "". Examples of string literals are "This is a string literal" "I am a string" The programmer may wish to have a double quote itself inside a string literal. This requires using a single quote as an escape character and so if a single or double quote is required inside a string literal it must be preceded by a single quote. For example "a'"" has a value a" and "a''" has a value a' There are a number of other special characters which may be used inside string literals. They are 'n 'p 'o 't 'b
newline newpage carriage return horizontal tab backspace
These characters are normally used in strings to represent special ASCII characters. 4.5
Pixel Literals
A pixel literal specifies the values in the planes of the pixel. It is defined by
::=
on[&] | off[&]
=>
pixe l
For example on 4.6
off & on & off
File Literal
There is only one file literal. It is used to denote an inactive file.
4.7
::=
nullfile
nullfile
=>
file
pntr Literal
There is only one pntr literal. It is used to denote an empty structure.
::=
nil
11 nil
=>
pntr
12 5.
Primitive Expressions and Operators
The order of execution of an S-algol program is strictly from left to right and top to bottom. This rule becomes important in understanding side-effects in the store. 5.1
Boolean Expressions
Objects of type bool in S-algol can have the value true or false. There are only two boolean literals, true and false and three operators. There is one unary operator, ~, and two binary operators, and and or. They are defined by the truth table below. a
b
~a
a or b
a and b
true false true false
false true true false
false true false true
true true true false
false false true false
The precedence of the operators is important and is defined in descending order as ~ and or Thus ~a or b and c is equivalent to ( ~a ) or ( b and c ) This is reflected in the syntax rules which are <expression> ::= <exp1> ::= <exp2> ::= <expression> <expression> [~]<expression>
<exp1>[or<exp1>]* <exp2>[and<exp2>]* [~]<exp3> : bo ol or <expression> : b ool = > b ool bool oo l : bo ol and <expression> : b oo l = > boo l bool : bo ol => bo bool b o ol
The evaluation of a boolean expression in S-algol is non-strict. That is, in the left to right evaluation of the expression, as soon as the result is found, no more computation is performed on the expression. For example true or <expression> gives the value true without evaluating <expression> and false and <expression> gives the value false without evaluating <expression>.
13 5.2
Comparison Operators
Expressions of type boolean can also be formed by some other binary operators. For example, a = b is either true or false and is therefore boolean in nature. The operators are called the comparison operators and are < less than ≤ less than or equal to (written <=) > greater than ≥ greater than or equal to (written >=) = equal to ≠ not equal to (written ~=) is a pntr has the given class isnt a pntr does not have the given class The syntactic rules for these are <exp2>
::= ::=
[~]<exp3>[<exp3>] <eq_op> | |
t : no nvoid, n onvo id <expression> : t <eq_op> <expression> : t = > b ool w here <eq_op> ::= = | ≠ t : orde o rde red ,<expression> : t <expression> : t = > b ool w here ::= < | ≤ | > | ≥ <expression> : pn tr = > bo o l pntr w here ::= is | isnt Note that the operators <, ≤, > and ≥ are defined on integers, reals and strings whereas = and ≠ are defined on all S-algol data types. Their interpretation for these data types is given with each data type as it is introduced below. The operators is and isnt are for testing a structure class. 5.3
Arithmetic Expressions
Arithmetic may be performed on data objects of type integer and real. The syntax of arithmetic expressions is <exp3> <exp4> <exp5> <mult_op>
::= ::= ::= ::= ::=
<exp4>[<exp4>]* <exp5>[<mult_op><exp5>]* []<exp6> +|<star> | / | div | rem
t : arith, arith <expression> : t <expression> : t = > t t : arith, arith <expression> : t = > t <expression> : in t <expression> : in t => int ::= <star> | div | rem
w here
<expression> : rea l <expression> : re al => rea l ::= <star> | /
w here
14 The operators mean + * / div rem
addition subtraction multiplication real division integer division throwing away the remainder remainder after integer division
In both div and rem the result is negative only if exactly one of the operands is negative. Some examples of arithmetic expressions are a+b
3+2
1.2 + 0.5
-2 + a / 2.0
The language provides automatic coercion from integer to real where necessary. 5.4
Arithmetic Precedence Rules
The order of evaluation of an expression in S-algol is from left to right and based on the precedence table * +
/ -
div
rem
That is, the operations *, /, div, rem are always evaluated before the binary versions of + and -. However, if the operators are of the same precedence then the expression is evaluated left to right. For example 6 div 4 rem 2
gives the value 1
Brackets may be used to override the precedence of the operator or to clarify an expression. <exp6>
::=
()
t : no nvoid,( : t) n onvo id t => t For example 3*(2-1) 5.5
yields 3 not 5
String Expressions
There is only one string operator ++ defined on strings. It concatenates the two operand strings to form a new string. For example "abc" ++ "def" results in the string "abcdef" The syntax rule is <exp4>
::=
<exp5>[++<exp5>]*
15 <expression> : str ing in g ++ <expression> : strin g => string strin g A new string may be formed by selecting a substring of an existing string. For example, if s is the string "abcdef" then s( 3 | 2 ) is the string "cd". That is, a new string is formed by selecting two elements from s starting at element 3. The syntax rule is <exp6> ::=
<expression>[()]
<expression> : str ing( : int : in t) in g t = > str ing For the purposes of substring selection the first character in a string is numbered 1. The selection values are the start position and the length respectively. The characters in a string are ordered according to the ASCII character code. Thus "a" < "z" To compare two strings, the characters are compared in pairs, one from each string, from left to right. Two strings are considered equal only if they have the same characters in the same order and are of the same length. Otherwise they are not equal. The null string is less than any other string. Thus the less-than relation can be resolved by taking the characters pair by pair in the two strings until one is found to be less than the other. This is the lexicographic order commonly used in dictionaries. The other relations can be resolved by using '=' and '<'. 5.6
Picture Expressions
The picture drawing facilities of S-algol allow the user to produce line drawings in two dimensions. The system provides an infinite two dimensional real space. Altering the relationship between different parts of the picture is performed by mathematical transformations which means that pictures are usually built up of a number of sub-pictures. The syntax of picture expressions is <exp4>
::= ::=
<exp5>[<exp5>]* ^|&
<expression> : pic <expression> : p ic = > pic ::= shiftby, | scaleby, | rotateby | colourin | textfrom,to, | , shift scale rotate colour text
: : : : :
pic by : r eal, : rea l => pic eal pic by : r eal, : rea l => pic eal pic by : r eal = > pic pic in : pixe l => p ic str ing from : rea l, : r eal l to : r eal, : rea l => pic eal : rea l, : r eal = > pic l In a line drawing system the simplest picture is a point. For example, the expression
16 [ 0.1,2.0 ] defines the point 0.1,2.0. Points in pictures are implicitly ordered. A binary operation on pictures operates between the last point of the first picture and the first point of the second. The resulting picture has as its first point, the first point of the first picture, and as its last, the last point of the second. There are two infix picture operators. They are '^', which joins one picture to another by a straight line from the last point of the first picture to the first point of the second, and '&' which includes one picture in another. The other transformations and operations on pictures are
5.7
shift
The new picture consists of the points obtained by adding the x and y shift values and the x and y co-ordinates of the points in the old picture. The ordering of the points is preserved.
scale
The new picture consists of the points obtained by multiplying the x and y scale values with the x and y co-ordinates of the points in the old picture, respectively. The ordering of the points is preserved.
rotate
The new picture consists of the points obtained by rotating the x and y coordinates of the points in the old picture about the origin by the angle indicated in degrees. The ordering of the points is preserved.
colour
The new picture is the old one in a new colour.
text
Form a picture consisting of the text string. The two co-ordinates represent the start and end points of the string which will be scaled to fit.
Pixel Expressions
Pixels may be concatenated to produce another pixel of a greater depth using the operator '&'. <exp4>
::=
<exp5>[&<exp5>]*
<expression> : pixe l &<expression> : p ix el = > pixel pix el A pixel has depth representing the number of planes in the pixel. The planes are numbered from 0 and new pixels can be formed from subpixels of others. The syntax is <exp6>
::=
<expression>[()]
<expression> : pixe l ( : int : int ) => pixe l For example let b = on & off & off & on b (1 | 2 ) is the pixel off & off This last expression is interpreted as the pixel formed by starting at plane 1 in 'b' and selecting 2 planes.
17 5.8
Precedence Table
The full precedence table for S-algol is now / * + ~ = ≠ and or 5.9
div ++
rem
^
&
<
≤
>
≥
is
isnt
Other Expressions
All the S-algol operators have now been described but we have not exhausted all the ways of writing down expressions. There are vector expressions, pntr expressions, vector and structure indexing expressions, if and case expressions as well as block expressions and the fact that literals, identifiers and procedure calls on their own constitute expressions. All of these are dealt with elsewhere in this manual.
18 6.
Declarations
Declarations are of four kinds defined by the following syntax: <declaration> ::=
| <structure_decl> | <proc_decl> |
<declaration> = > void Procedure, forward and structure declarations are dealt with in later chapters. 6.1
Identifiers
In S-algol an identifier may be given to a data object, a procedure parameter, a structure field and a structure class. An identifier may be formed by the syntactic rule
::=
| <standard_id>
::=
[]
::=
[] | [] | .[]
That is, an identifier consists of a letter followed by any number of dots, letters or digits. For example x1
ron
look.for.record1
Ron
Note that case is significant in identifiers. The standard identifiers are those predefined for the user. They are given in section 11.2. 6.2
Variables, Constants and Declaration of Data Objects
Before an identifier can be used in S-algol it must be declared. The action of declaring a data object associates an identifier with a location of a certain type which can hold values that the identifier may take. In S-algol the programmer may specify whether the value is constant or variable. A constant may be manipulated in exactly the same manner as a variable except that it may not be updated. When introducing an identifier the programmer must indicate the identifier, the type of the data object, whether it is variable or constant and its initial value. Variables are declared by
::=
let
let : non v oid = > vo id For example let a := 1 introduces an integer variable with initial value 1. Notice that the compiler deduces the type. A constant is declared by let = For example
19 let discrim = b * b - 4.0 * a * c introduces a real constant with the calculated value. The compiler will detect and flag as an error any attempt to assign to a constant. 6.3
Sequences
A sequence of clauses is made up of any mixture, in any order, of declarations and clauses. The type of the sequence is the type of the last clause or declaration. If there is more than one clause in a sequence then all but the last must be of type void. <program>
::=
<sequence>?
<sequence>
::=
<declaration>[;<sequence>] | [;<sequence>]
<sequence> : vo id = > v oid t : ty pe, <declaration> : void ;<sequence> : t = > t type t : ty pe, : void ;<sequence> : t = > t type 6.4
Brackets
Brackets are used to make a sequence of clauses and declarations into a single clause. <exp6>
::=
begin[<sequence>]end | {[<sequence>]}
begin end => v oid { } = > void v oid t : ty pe, begin[<sequence> : t ]end = > t type t : ty pe, {[<sequence> : t ]} => t type The {} method is there to allow a clause to be written clearly on one line. For example let i := 2 for j = 1 to 5 do { i := i * i ; write i } However, if the clause is longer than one line the first alternative should be used for greater clarity. Nonvoid blocks are sometimes called block expressions. 6.5
Scope Rules
Any identifier that is declared has its scope limited to the following sequence. This means that the scope of an identifier starts immediately after the declaration and continues up to the next unmatched } or end. If the same identifier is declared in an inner sequence, then while the inner identifier is in scope the outer one is not.
20 7.
Clauses
The expression is a special type of clause which allows the operators in the language to be used to produce data objects. There are other clauses in S-algol which allow the data objects to be manipulated and some which are there to control the flow of the program. 7.1
Assignment Clause
The assignment clause has the following syntax. ::=
:=
t : no nvoid, n onvo id : t := : t = > void For example discriminant := b * b - 4.0 * a * c gives 'discriminant' the value of the expression on the right. Of course, the identifier must have been declared as a variable and not a constant. The clause alters the value denoted by the identifier. 7.2
if Clause
There are two forms of the if clause defined by ::=
ifdo | ifthenelse
if : bool do : v oid = > v oid t : type , if : bool then : t else : t => t In the single pronged version, if the condition after the if is true then the clause after the do is executed. For example if a < b do a := 3 The second version allows a choice between two actions to be made. If the first clause is true the second clause is executed, otherwise the third clause is executed. Notice that the second and third clauses are of the same type and the result is of that type. For example if x = 0 then y := 1 else x := y - 1 let temp = if a < b then 1 else 5 7.3
case Clause
The case clause is a generalisation of the if clause which allows the selection of one item from a number of possible ones. The syntax is ::=
caseofdefault : ::= :;[]
t : ty pe ; t1 : non void, type void case : t1 of default : : t => t w here ::= : : t ; [] w here ::= : t1 [,]
21 An example of the use of the case clause is case next.car.colour of 1,4 : "green" 2 : "blue" default : "any" The value 'next.car.colour' is compared in strict order, i.e left to right, top to bottom, with the expressions on the left hand side of the colon. When a match is found the clause on the right hand side is executed. Control is then transferred to the next clause after the case clause. If no match is found then the default clause is executed. The above case clause has result type string. 7.4
repeat ... while ... do Clause
There are three forms of this clause which allow loops to be set up with the test at the start, the end or the middle of the loop. The three forms are encapsulated in the two productions. ::=
repeatwhile[do] | whiledo
repeat : vo id while : b ool [do : v oid ] => vo id while : bo ol do : vo id => v o id In each of the three forms the loop is executed until the boolean clause is false. The while do version is used to perform a loop zero or many times whereas the repeat while is used for one or many times. 7.5
for Clause
The for clause is included in the language as a bit of syntactic sugar where it is known in advance how many times the loop will be executed. It is defined by ::=
for=to[by]do
for = : int to : in t [by : in t ]do : v oid = > v oid The clauses are the initial value, the limit, the increment and the clause to be repeated respectively. The first three are of type int and are calculated only once at the start. If the increment is 1 then the by clause may be omitted. The identifier or control constant is declared at the start of the void clause taking on the values defined by initial value, increment and limit. The scope of 'i' is the void clause. An example of the for clause is let factorial := 1 ; let n = 8 for i = 1 to n do factorial := factorial * i With a positive increment, the for loop terminates when the control constant is initialised to a value greater than the limit. With a negative increment, the for loop terminates when the control constant is initialised to a value less than the limit.
22 7.6
abort Clause
The reserved word abort simply stops the program when used. ::=
abort
abort
=>
void
23 8.
Procedures
8.1
Declarations and Calls
Procedures in S-algol constitute the abstractions over expressions, if they return a value, and clauses of type void if they do not. In accordance with the principle of correspondence, any method of introducing an identifier in a declaration has an equivalent form as a parameter. Thus, in declarations of data objects, giving an identifier an initial value is equivalent to assigning the actual parameter value to the formal parameter. Since this is the only type of declaration for data objects in the language, it is also the only parameter passing mode and is commonly known as call by value. Like declarations, the formal parameters representing data objects must have an identifier, a type and an indication of whether they are variable or constant. A procedure which returns a value must also specify its return type. The scope of the formal parameters is from their declaration to the end of the procedure clause. Procedures are defined with the following syntax. <proc_decl>
::=
procedure[([<parameter_list>] [<arrow>])] ;
<parameter_list>
::=
<parameter>[;<parameter_list>]
<parameter>
::=
| <structure_decl> | <proc_type>
<proc_type>
::=
([][<arrow>])
::=
[, | <proc_type>[,] | <s_decl>[,]
<s_decl>
::=
structure([,]*)
::=
[c]
::=
int | real | bool | string | pixel | pic | pntr | file | <star> | #pixel | #cpixel
Thus we may declare the integer identity procedure, which we will call 'int.id' by procedure int.id( int n -> int ) ; n The syntax of the procedure call is <exp6>
::=
::=
[([])]
There must be a one-to-one correspondence between the actual and formal parameters and their types. Thus to call the integer identity procedure given above we could use int.id (42)
24 which will evaluate to the integer 42. The type of 'int.id' is written (int -> int). To complete the Principle of Correspondence for procedures, the parameters may be made constant. Variable parameters may be assigned to but since they are local variables this only has local effect. Constant parameters may not be assigned to. All parameters are passed by value. For example, the parameter in 'int.id' is not assigned to and is more appropriately a constant. Therefore the declaration should be procedure int.id( cint n -> int ) ; n Note that the constancy of the parameter is not part of the type, a notion that is important when deciding type equivalence.
8.2
forward Declarations
In S-algol all names must be declared before they can be used and a identifier comes into scope immediately after its declaration. This is awkward when recursive procedure definitions are involved. Therefore in the case of the procedure, the identifier comes into scope after the parameter list has been specified allowing procedures to call themselves. A forward declaration is required for mutually recursive procedures. Its syntax is
::=
forward<proc_type>
This is merely an aid to the compiler. However, there is one rule with forward declarations that has nothing to do with the one pass nature of the compiler but with the decision to allow clauses and declarations to be freely mixed. To avoid the possibility of an uninitialised identifier being used by jumping over a declaration, a forward declaration and the actual declaration may only be separated by structure class declarations and other procedure declarations. In other words its use is restricted to mutual recursion situations.
25 9.
Aggregates
S-algol allows the programmer to group together data objects into larger aggregate objects which may then be treated as single objects. There are three such object types in S-algol : vectors, structures and images. If the constituent objects are of the same type a vector is used and a structure for non-homogeneous collections. Images are collections of pixels. Vectors, structures and images have the full civil rights as any other data object in S-algol. All aggregate data objects in S-algol have pointer semantics. That is, when a aggregate data object is created, a pointer to the locations that make up the object is also created. The object is always referred to by the pointer which may be passed around by assignment and tested for equality. The location containing the pointer and the constituent parts of the aggregate data object may be independently constant or variable. <exp6>
::=
::=
9.1
| | <subimage_constr> |
Vectors
9.1.1 Creation of Vectors A vector provides a method of grouping together objects of the same type. Since S-algol does not allow undefined values all the initial values of the elements must be specified. The syntax is
::=
::=
vectorof | @of :: [,]
t : non void, nonv oid, vectorof : t = > *t t : non void, nonv oid, @ : int of