POP 2 Reference Manual

User Manual:

Open the PDF directly: View PDF PDF.
Page Count: 42

DownloadPOP-2-Reference-Manual
Open PDF In BrowserView PDF
POP-2
REFERENCE
MANUAL

BY

R. M. BURSTALL
AND

R. J. POPPLESTONE
DEPARTMENT OF MACHINE INTELLIGENCE AND PERCEPTION
UNIVERSITY OF EDINBURGH

CONTENTS

PAGE

1 INTRODUCTION
1.1 Aims
1.2 Main features
1.3 Examples
1.4 Notation for syntactic description
1.5 Notation for functions

209
209
210
212
213

2 ITEMS
2.1 Simple and compound items
2.2 Integers
2.3 Reals
2.4 Truth values
2.5 Undefined
2.6 Terminator

214
215
215
216
216
216

3 VARIABLES
3.1 Identifiers
3.2 Declaration and initialisation
3.3 Cancellation

216
217
219

4 FUNCTIONS
4.1 Definition of functions
4.2 Application of functions
4.3 Nonlocal variables
4.4 Partial application
4.5 Doublets
4.6 Arithmetic operations

219
220
221
221
223
224

5 EXPRESSIONS AND STATEMENTS
5.1 Expressions
5.2 Precedence
5.3 Statements and imperatives
5.4 Labels and goto statements

224
226
226
227

207

CONTENTS
PAGE

228
229

5.5 Assignment
5.6 Comments
6 CONDITIONALS
6.1 Conditional expressions
6.2 Conjunctions and disjunctions

229
230

7 DATA STRUCTURES
7.1 Functions of data structures
7.2 Records
7.3 Strips
7.4 Garbage collection

231
233
234
235

8 STANDARD STRUCTURES
8.1 References
8.2 Pairs
8.3 Lists
8.4 Full strips and character strips
8.5 Arrays
8.6 Words
8.7 Functions

236
236
236
239
239
240
241

9 INPUT AND OUTPUT
9.1 Input
9.2 Output

242
243

10 MACHINE CODE

244

11 MODES OF EVALUATION
11.1 Immediate,evaluation
11.2 Macros
11.3 Evaluation of program text

244
244
245
245

Acknowledgments

208

1.

INTRODUCTION

1.1. Aims
The following are the main design objectives for the POP-2 language:
(i) The language should allow convenient manipulation of a variety of
data structures and give powerful facilities for defining new functions over
them.
(ii) The language should be suitable for taking advantage of on-line use
at a console, i.e. it should allow immediate execution of statements and
should have a sufficiently simple syntax to avoid frequent typing errors.
(iii) A compiler and operating system should be easy to write and should
not occupy much storage.
(iv) The elementary features of the language ,should be easy to learn and
use.
(v) The language should be sufficiently self-consistent and economical in
structure to allow it to incorporate new facilities when extensions are desired.
In attaining these objectives certain other desirable features of programming languages had to be relegated to secondary importance:
(vi) Fast arithmetical facilities on integer and real numbers.
(vii) Fast subscripting of arrays.
(viii) A wide variety of elegant syntactic forms.
Naturally whether (iii) or (vi) and (vii) are attained is to a considerable
extent a matter of implementation.

1.2. Main features
The following main features are provided. Roughly analogous features of
some other programming languages are mentioned in brackets as a guide:
(i) Variables (cf. ALGOL but no types#at compile time).
(ii) Constants (cf. ALGOL numeric and string constants, LISP atoms and list
constants).
209

PROBLEM-ORIENTED LANGUAGES

(iii) Expressions and statements (cf. ALGOL).
(iv) Assignment (cf. ALGOL, also CPL left-hand functions).
(v) Conditionals, jumps and labels (cf. ALGOL but restrictions on jumps
and labels).
(vi) Functions (cf. ALGOL procedures but no call by name, cf. CPL and
'swim for full manipulation of functions).
(vii) Arrays (cf. ALGOL; cf. CPL for full manipulation of arrays).
(viii) Records (cf. COBOL, PL/l, Wirth-Hoare ALGOL records, CPL nodes).
(ix) Words (cf. LISP atoms).
(x) Lists (cf. LISP, IPL-V).
(xi) Macros.
(xii) Use of compiler during running (cf. LISP, TRAC, FORMULA ALGOL).
(Xiii) Immediate execution (cf. JOSS, TRAC).
Notes:
LISP 1.5
See Barron, D. W.,etal. 1964. The main features of CPL, Computer
J., 6, 134-43.
CPL reference manual. Edited C. Strachey (privately circulated).
Wirth-Hoare ALGOL: See Wirth, N., and Hoare, C. A. R. 1966. A contribution to the development of Algol, Communs Assn Comput. Mach.,
9, 413-32.
mc:See Mooers, C. N. 1966. TRAC, a procedure describing language
for the reactive typewriter, Communs Assn Comput. Mach., 9, 215-24.
iswm: See Landin, P. J. 1966. The next 700 programming languages,
Communs Assn Comput. Mach., 9, 157-166.
LISP:

CPL:

1.3. Examples
The following is an example of pop-2 program text. The sign (not to be
confused with that used in section 1.5 'Notation for functions') prints out
some results on a newline prefixed with two asterisks. These results are
included in the text below, as they would appear if the program were run
on-line at a console.
comment arithmetic;
12.0+ 2.5*(1.5 -I- 2.5).
**22.0
vars a b sum;
2*2—+a; 3*a—*b; a*a+b*b—osum;sum
**160
function sumsq x y;
x*x+y*y
end;
sumsq(a, b)+1
**161
210

BURSTALL AND POPPLESTONE

function fact n; vars p;
1-0p;
loop: if n=0 then p else n*p-op; n
end;
fact(fact(3))
** 720

goto loop close

comment arrays;
vars a if;
10-31; 20-tj;
newarray([%1, i, 1,j%], sumsq)-4a;
a(2,
** 13
10-■a(2, 3); a(2,
** 10
function arraysum al a2 m n;
newarray ([%1, m, 1, n%], lambda if; al(i,j)+a2(i,j) end)
end;
arrays= (a, a, 10, 20)-oa; a(2,
** 20
comment lists;
vars u;
1-41; 2--tj;
[%i, i+j, "dog", "cat" %]-'u;
** [1 3 dog cat]
cons("pig", u)** [pig 1 3 dog cat]
function appencla y;
if null(y) then[% x Y.] else cons(hd(y), append(x, tl(y))) close
end;
append(4,[% 1, 1+1, 3%])=
** [1 2 3 4]
comment records;
vars consper destperforename surname male pl p2;
recordfns("person", 500,[0 0 1])-.male-'surname-'forename
-0destper-■ consper;
comper("jane", "Jones",false)-opl; consper("sam", "smith", true)-y2;
surname(p1)
**,/ones
datalist(p1)=.
** [Jane Jones 0]
routine marry x y;
if male(x) and not(male(y)) then surname(x)--Psurname(y) close
211

PROBLEM-ORIENTED LANGUAGES

end;

marry(p2, pl); datalist(p1)
** [jane smith 0]

1.4. Notation for syntactic description
We use the

BNF (Backus-Naur

Form)notation as used in the ALGOL report:

= indicates a syntax definition;
< > are used to enclose the name of a syntax class;
I denotes disjunction (union of syntax classes).
Concatenation denotes concatenation of any elements of two syntax
classes.
We also use a convenient extension of this notation due to R. A. Brooker:
* means that a class may occur n times, n> 1;
? means that a class may occur n times, n=0 or 1;
*7 means that a class may occur n times, n 0,
e.g. the definitions

::=  I 
::= 
::=  I 
may be replaced by

::= 
::= 
The characters <, > and * are used in the pop-2 reference language but no
confusion should arise.
When we wish to give examples of a syntax class we use the symbol
'e.g.::=',for example.:
e.g.::=  I    
The character set of the pop-2 reference language is as follows.
::=alblcIdlelI1011j1kIllmInlolplqirlsItluIvIwIxlyiz
::=0I11213141516171819

::= +I-14,111$18d=1l:ILIT
::=,1;
::=.
::=10
::=(1)I[1]
::= %
="
::= /I\
212

BURSTALL AND POPPLESTONE

Letters may be written in lower case, upper case or heavy type without any
change of meaning. It will be conventional however to use heavy type letters
for syntax words, i.e. those identifiers such as function, then, end and cancel
which have a special meaning for the pop-2 compiler and which characterise
certain syntactic forms.
Spaces,tabulate and new lines terminte dentifiers,integers,reals and words
but otherwise they are ignored.
A distinction is made between the reference language used in this document
and a number of possible hardware languages used by particular computer
implementations of Pop-2. Each character in the reference language should
be represented by a distinct character or sequence of characters in the hardware language. A particular letter, whether upper case, lower case, heavy
type or not is regarded as the same character in the reference language.
The symbols and used in this paper should be read as a typographical
abbreviation for the pairs of characters —> (minus greater than) and
= > (equals greater than) respectively.

1.5. Notation for functions
It is convenient to have a notation to specify the domain and range of functions. We will consider functions having several arguments (or possibly
none)and producing several results(or possibly none),the notion offunctions
with more than one result being an extension of normal mathematical usage
(see section 4.2 'Application of functions'). We introduce a special symbol
which is not to be confused with any identifier in the pop-2 language.
Suppose dl, d2, ,dm and r 1, r2, ,rn are all sets of items. Then
dl, d2, ,
r2, ,rn is the set of all functions whose domain is
dl, d2, ,dm and range r 1,r2, • ,rn,i.e. with arguments which are m-tuples
in dl x d2 x x din and with results which are n-tuples in r 1 x r2 x rn. We
express the fact that a functionf is a member of this set of functions by
fe dl, d2, ,dm rl, r2, ,rn
Some examples will make this clear.
add E integer, integer integer
divreni E integer, integer integer, integer
where divrem is 'divide with remainder', e.g. divrem (7, 3)=2, 1 and divrem
(14, 4)=3, 2
roundup e real
prime e integer

integer
truthvalue

If the function has no results we use an empty pair of parentheses, thus:
printout e integer
The arguments or results#20
may themselves be functions
differentiate e (real

real)

(real real)
213

PROBLEM-ORIENTED LANGUAGES

Where we wish to discuss a number offunctions all having the same domain
and range it is convenient to abbreviate thus:

f, g,

h all e

for

f
and
ge

and

he
Some functions do not have a fixed number of arguments and some do
not have a fixed number of results (see section 4.2'Application of functions').
In such cases we may write for example
i.e integer

real, integer, ... ,integer

for the domain or range, meaning that a real and a variable number ofintegers
are the results.

2.

ITEMS

2.1. Simple and compound items
The objects on which one can operate are called Items. They are divided into
two distinct classes: Compound items, which are represented by addresses and
Simple items which are directly represented by bitstrings which do not contain addresses (these bit strings are normally of fixed length for a given implementation, being a single machine word). The address representing a compound item points to a bit string whose length may vary from item to item.
This bit string may contain other items. The areas of store immediately
pointed to by two different compound items do not overlap.
The following standard function recognises compound items:
iscompnd e item

truthvalue

Two kinds of simple item are distinguished: integers and reals. The
following standard functions recognise them:
isinteger, isreal all e item

truth value

The standard function = (an operation of precedence 7)is used to represent
equality of items. For integers and reals it has the usual meaning. Its
meaning for compound items is given in section 7.1 'Functions of data
structures'.
= e item, item

truthvalue
214

BURSTALL AND POPPLESTONE

2.2. Integers
Integers are simple items. They may be positive, negative or zero. The size
of the largest and smallest integers allowed depends on the implementation.
The#following functions on integers are standard:
intadd, intsub, intmult, all E integer, integer integer
// e integer, integer integer, integer
intplus, intminus all e integer integer.
intsign E integer integer
intgr, mile, intgreq, intleeq all E integer, integer truthvalue
intadd, intsub, intmult and intdiv are the usual add, subtract and multiply.
// is divide with remainder and produces a quotient and a remainder (if al/b
is (q, r), then q*b+ r =a and 0.4 r::=ll
::= 8:
::= 2:binary#2digit*>
::=
::=011121314151617
::= 011
Example:
e.g.::= 8:77712:1011016559
Integers may also be treated as bit-strings (the length depending on the
implementation) and the following functions are standard:
logand, logor, logshift all e integer, integer integer
lognot e integer integer
logand and logor are the usual bit by bit 'and' and 'inclusive or'; logs/ft
causes the first integer to be shifted left by the number of places given in the
second, unless the second integer is negative when shifting to the right takes
place (all new bits to fill up the end are zero in each case).

2.3. Reals
Reals are simple items. They may be positive, negative or zero. The size of
the largest and smallest reals allowed and the precision depends on the implementation. The following functions on reals are standard:
realadd, realsub, realmult, realdiv all e real, real real
realplus, realminus all e real real
realsign e real integer
realgr, realle, realgreq, realleeq all e real, real truth value
215

PROBLEM-ORIENTED LANGUAGES

These are the usual add, subtract, multiply and divide on reals. realplus
carries a real into itself and realminus complements a real. realsign produces
—1,0 or +1 according to the sign of the real. The remaining four functions
are the relations 'greater than', 'less than', 'greater than or equal to' and
'less than or equal to'.
There are also operations to convert a real to the nearest integer and to
convert an integer to real:
intofe real integer
realofe integer real
The syntax of reals is as follows:
::=. 
::=10+110—  I io
Example:
e.g.::=.511.9911.510-6

2.4. Truth values
The two items True which is the integer 1 and False which is the integer 0 are
called Truthvalues.
•
•
On entry#to the pop-2 system the standard variable true is set to 1 and the
standard variable false is set to 0. The following standard functions on
truthvalues are provided:
hooland, boolor all e truthvalue, truthvalue truthvalue
not e truthvalue truthvalue
These are the usual functions'and','inclusive or' and 'not' of propositiona
calculus.

2.5. Undefined
The standard variable undef has the word "under as its value on entry to
the pop-2 system (see section 8.6 Words'). The programmer may use it as
the result of a function which fails to produce its normal result.

2.6. Terminator
The standard variable termin has the word "termini' as its value on entry to the
,pop-2 system (see section 8.6 Words'). It may be used as the first argument
of a variadic function (see section 4.2 'Application of functions') or to mark
the end of an input file (see section 9.1 'Input').

3.

VARIABLES

3.1. Identifiers
An item may be the Value of a Variable (a variable is not itself an item).
An Identifier is associated with the variable and this identifier is used to
216

BURSTALL AND POPPLESTONE

refer to it in a pop-2 program. A number of distinct variables may have
the same identifier, but only one of them is Currently associated with it at a
particular time in the evaluation process.
An identifier may be restricted to a certain range of values and it may be
given special syntactic properties by being given a precedence (see section 5.2
'Precedence').
The syntax of identifiers is:
::=  I 
::=  I 
Example:
gdentifier>e.g. ::=x I y99 I alpha I u2a I +++ 11+ I 0 I * $ $ *
Syntax words such as then, end, and : have special meanings and may
not be used as identifiers. Only the first 8 characters are significant.

3.2. Declaration and initialisation
A variable is either Global, Local or Formal. A Declaration is used to
introduce an identifier and associate it with a global or local variable. A
Local Declaration, introducing a local variable, is a declaration which occurs
in a function body. A Global Declaration, introducing a global variable, is
one which does not.
An Initialisation is used to introduce an identifier and associate it with a
formal variable and give the variable an initial value. It is achieved by
including the identifier in the formal parameter list of a function (see section
4.1 'Definition of functions').
A declaration or initialisation may also specify that the identifier is restricted to take only functions as values. This is not necessary but may make the
implementation more efficient. A declaration or initialisation may also
specify that the identifier is an Operation, i.e. it is restricted to take functions
as its values and is given a precedence. This restriction is associated with
the unique name(see below)produced by the declaration or the initialisation.
The syntax of declarations is:
::=vars 
::=  I 
::= I ()
::= function I operation 
Example:
e.g.::=vars x y I vars x y function(fg)operation 7 ==
A declaration or initialisation has a Scope, which is a piece of pop-2 text.
An identifier may not be used to represent a variable outside the scope of a
declaration or initialisation of the identifier.
217

PROBLEM-ORIENTED LANGUAGES

The scope of a global declaration starts at the declaration and continues
until the identifier is cancelled.
The scope of a local declaration starts at the declaration and continues to
the end of the innermost function body enclosing it.
The scope of an initialisation is the body of the function in which it occurs.
Each declaration or initialisation gives rise to a unique mark and this
mark is associated with all occurrences of any identifier introduced by the
declaration or initialisation within the scope of the declaration or initialisation. An identifier together with its unique mark is called a Unique name.
Thus an identifier which occurs in more than one declaration or initialisation corresponds to more than one unique name.
The generation of fresh unique names for identifiers can be suppressed by
using the standard routines:
nonunique, unique all e 0
If nonunique is applied, all declarations or initialisations of a given identifier
until unique is applied will give rise to the same unique name. This may save
storage space and can be used when no confusion is liable to occur.
To sum up:
A new identifier is introduced by introducing a fresh sequence of
characters.
A new unique name is introduced by#each declaration or initialisation
(unless nonunique has been applied).
A new variable is introduced by each dynamic activation of a declaration
or initialisation.
A variable has an Extent which is a sequence of evaluations of expressions
and statements.
The extent of a global variable starts from its declaration and continues
indefinitely.
The extent of a local or formal variable starts on entry#to the body of the
function in which it is declared or initialised and continues until exit from the
body. During this extent the extent of any other variable with the same
unique name is temporarily interrupted. This is called a Hole in the Extent
of the other variable. Its value is not altered but it cannot be accessed or
changed by assignment. Thus there is only one variable Currently Associated
with a particular unique name during any evaluation. Other variables
associated with the unique name are in abeyance.
• More than one global declaration of the same identifier is not permitted
unless a cancellation of it intervenes in the text.
Similarly a declaration of a local variable is not permitted if there is already
a declaration of a local or initialisation of a formal with the same identifier
for the same function body.
A Standard Variable is a global variable which already has a value on entry
to the pop-2 system. A Standard Function (or Routine) is one which is the
value of a standard variable. Certain standard variables are Protected, i.e.
no assignment may be made to them.
218

BURSTALL AND POPPLESTONE

3.3. Cancellation
A cancellation terminates the scope of any declaration of an identifier and
removes the effect of any restrictions placed upon the identifier. The
cancellation must occur textually between the old declaration and any new
declaration. It may not occur in a function body.
The syntax of cancellations is:
::= cancel 

4.

FUNCTIONS

4.1. Definition of functions
A Function is a compound item. Definition and application of functions are
treated in this section and the next. Certain properties of a function regarded
as a data structure are treated in section 8.7 'Functions'.
A function consists of a Formal Parameter List which is a list of identifiers
offormal variables, possibly an output local list which is a list of the identifiers
of output local variables (see section 4.2 'Application of functions') and a
Body which is an imperative sequence (see section 5.3 'Statements and
imperatives').
A function which produces no results (see section 4.2 'Application of
functions') is called a Routine.
Functions may be referred to in the program by using a function constant,
called a Lambda Expression, or they may be standard functions provided by
the pop-2 system, or they may be created by partial application or by application of a standard function which produces a function as a result.
The syntactic representation of a function constant is:
(formal parameter list element>::= I 
'(formal parameter list>::=
::= I 

::=
::=
::=1ambda;
 end
Example:
e.g.::= lambda x y; cons(x, cons(a, y)) end
I lambda x; n1(1); print(x) end
We very often wish to declare a variable and then assign a function to it.
The syntactic form of this will be as follows:
vars ;
;  end —■ 
219

PROBLEM-ORIENTED LANGUAGES

This is so common that a special syntactic form is introduced which is
equivalent to it:
::= function I routine
(Junction definition>::=;
 end
The word routine is a synonym for function. It may be used for a function
with no results.
If the identifier has been previously declared at this level no new declaration
is implied and the function definition is equivalent simply to an assignment
of a lambda expression. The identifier may be an operation identifier.
Example:
(function definition>e.g.::=function max x y; if x > y then x else y close
end
I routine enter u v; cons(conspair(u, v), dict)—•
dict end
I function order x y u v;
if x > y then x --• u; y --■ v
else y u; x —■ v close
end

4.2. Application of functions
An n-Tuple is an ordered sequence of n items (n >0). An item is identical
with the 1-tuple whose sole member is that item. An n-tuple and an m-tuple
may be Concatenated to produce an (n+m)-tuple.
A function of n arguments (i.e. with n formal parameters, excluding frozen
formals; see section 4.4 'Partial application'), may be Applied to an n-tuple,
whose members are called the ActualParameters of the function. Application
of a function to its actual parameters produces an m-tuple, whose members
are said to be the Results of the function. A function producing no results
(i.e. an 0-tuple) is called a routine (see section 4.1 'Definition of functions').
A function which does not take a fixed number of arguments is called
Variadic. A function which does not produce a fixed number of results is
called Variresult.
The application of a function to its actual parameters consists of the following sequence of events:
Entry: a new variable corresponding to each formal parameter is initialised
to the corresponding actual parameter value, or if it is a frozen formal to the
corresponding value in the frozen value list. A new variable corresponding to
each local variable declaration in the function body but not in any interior
function body is then created. The variables previously associated with the
identifiers of formal or local variables can no-longer be referred to but their
values are undisturbed.
Running: the function body is evaluated with the variables created on entry.
220

BURSTALL AND POPPLESTONE

Exit. Any items which have been placed on the stack (see section 5.3 'Statements and imperatives') and were not there at entry are concatenated with
the values of any Output Local Variables to form the results of the function.
The variables created on entry are terminated and the variable associated
with each identifier reverts to what it was on entry. There is no change in the
values of variables which were previously associated with the formal or local
variable identifiers and have now been reinstated. The values of formal and
frozen variables are lost. The frozen formals will be reinitialised from the
frozen value list on the next entry to the function normally with the same
values as last time; the frozen value list can be changed by usingfrozval(see
section 8.7 'Functions').

4.3. Nonlocal variables
Variables which occur in a function body and are not locals (i.e. declared in the
body)or formals(i.e.elements of the formal parameter list) are called Nonlocal
to the function. They may be globals or locals of some outer function body
which textually encloses it. Care must be taken not to apply a function with
nonlocals in a hole in the extent of some of its nonlocals (see section 3.2
'Declaration and initialisation') or outside their extent. Mention of the
identifier of such a nonlocal would refer to a quite different variable currently
associated with that unique name. The difficulty can arise for recursive
functions. Analogous trouble may arise if nonunique is used.
To avoid such difficulties a frozen formal may be used instead of the nonlocal, provided that it is not desired to assign a new value to the nonlocal as
a result of the call. The frozen formal can be initialised by partial application
to the value that the non-local would have taken. (Note that the frozen
formals can be used in this way to give the equivalent of CPL fixed functions,
see CPL Reference Manual privately circulated by C. Strachey, Programming
Research Unit, Oxford University.) In cases where assignment to the nonlocal is desired a frozen formal can be used and initialised to take a reference
(see section 8.1 'References') as value. The component of this reference can
then be assigned to, and so long as the reference is made the value of some
other exterior variable the value is accessible outside the function body.

4.4. Partial application
In section 4.2'Application offunctions' we explained the method of applying
a function to its arguments. There is a process somewhat analogous to
application called Partial Application. By this means some of the formal
parameters of a function may be made into Frozen Formals, producing a new
function with fewer arguments. The frozen formals are always initialised to
a fixed value when the function is applied and do not require any corresponding actual parameters (see however section 8.7 'Functions' for means of
altering this fixed value). In other words the actual parameters corresponding
221

PROBLEM-ORIENTED LANGUAGES

to the frozen formals are supplied once and for all on partial application.
The values of the frozen formals are called the Frozen Value List.
For example by partially applying the two argument function 'multiply'
to 2 we get a one argument function to double a number, and by partially
applying it to 3 we get a function to#triple a number. These two functions
can coexist, and in general one function can be used to generate any number
of others by partial application.
More formally we say that a functionf of m arguments may be partially
applied to an n-tuple of actual parameters with n m. We assume for the
moment thatf has no frozen formals. The partial application produces a
new function f' with m-n ordinary formals corresponding to the first m-n
formals off, and n frozen formals corresponding to the last n formals off.
The functionf
'has a frozen value list consisting of the n items supplied as
actual parameters of the partial application.
Iff itself has some frozen formals already, say k of them, thenf'will have
n +k frozen formals and n +k corresponding items in its frozen value list.
The standard function partapply takes a function as its first argument and
a list as its#second argument,and partially applies the function to the elements
of the list.
partapply efunction, list

function

Note that partial application constructs a new function with a particular
frozen value list, it does not alter the original function in any way. A function
which has been produced as the result of partial application is called a Closure
Function. The frozen values of a closure function can be selected or updated
(see section 8.7 `Functions').
If a doublet(see section 4.5 'Doublets') is partially applied to one or more
items it produces a new doublet. The selector of the new doublet is obtained
by partially applying the selector of the original doublet to the given items.
The update routine of the new doublet is obtained by partially applying the
update routine of the original doublet to the given items.
A special syntactic form is also available for partial application. It is
similar to#that for ordinary application (see section 5.1 'Expressions').
 =(%I%)
(partial application>::=(% %)
I (%  %)
The value of the variable currently associated with the identifier is partially
applied to the concatenation of the expressions in the expression list. Thus
for example:
vars c; cons(%[is a number]%)—c;
c(1)
**[us a number]
c(2)
** [2 is a number]
222

BURSTALL AND POPPLESTONE

functionfx y z; .. etc. end;
f(% yl, zl %)—*fl;f1(xl)

4.5. Doublets
When dealing with data structures,functions called selectors are defined which
may be applied to a structure to produce its components (see section 7.1
'Functions of data structures'). To each selector there corresponds#an update
routine which alters the value of the component in the structure to a given
new value.
Any function may have an update routine associated#with it. This#will
normally only be done for selector functions. The function is then called a
Doublet. When a function is created using a lambda expression its associated
update routine is not defined. An update routine may be associated with it
by using the doublet updater, (see section 8.7 'Functions').
When a variable whose value is a doublet is used as the operator of a
compound expression the selector function of the doublet is applied. But
when such a variable is used as the operator of a quasi compound expression
(i.e. as part of a destination of an assignment) the update routine is applied.
It is convenient to extend our notation for functions (see section 1.5
to express concisely
'Notation for functions') using the new symbol `.=
the domain and range of the selector and update routines of a doublet.
Thus iff is a doublet we write
fe dl,

,dk=

r

meaning thatf has a selector s
s e dl

,dk

r

and an update routine u
u e r, dl,

,dk

()

Example:
The standard function hd used in list processing (see section 8.3 'Lists') is
a doublet.
vars 1; [1 2 3 41-4; hd(I)
** 1
5—+hd(1); 1
** [5 2 3 4]
hd(1)
** 5
function second I; hd(t1(1)) end;
lambda x I; x—+hd(t1(1)) end-4updater(second);
second(1)
** 2
6—■ second(1); 1
** [5 6 3 4]
223

PROBLEM-ORIENTED LANGUAGES

4.6. Arithmetic operations
In sections 2.2'Integers' and 2.3 'Reals' a number of standard functions were
introduced for performing arithmetic on integers and reals.
We say that an item is a Number if it is either a real or an integer. Arithmetic on numbers is performed by the following standard operations:
Explanation
Operation Precedence
7
less than
<
greater than
7
>
=<
7
less than or equal
7
greater than or equal
>=
add
5
+
5
subtract
—
4
*
multiply
4
divide
/
exponent
3
1

Result
truthvalue
truthvalue
truthvalue
truthvalue
real or integer
real or integer
real or integer
real
real

These are defined in terms of intadd, realadd, etc. and isreal, isint and
realof. +, — and * produce an integer result if both arguments are integer
otherwise a real result.

5.

EXPRESSIONS AND STATEMENTS

5.1. Expressions
An Expression is either a simple expression, a compound expression, a
conditional expression or an imperative expression (see section 5.3 'Statements and imperatives').
A Simple expression is either an identifier or a Constant, a constant being
an integer, a real or a structure constant. If the simple expression is an identifier then its value is the value of the variable currently associated with that
identifier. If it is a constant then its value is the item denoted by the constant.
A Structure Constant is either a lambda expression which is dealt with in
section 4.1 'Definition of functions' and in section 8.7 'Functions', a word
constant, a string constant or a list constant, all of which are dealt with in
section 8 'Standard structures'.
• A Compound expression has an'Operator which is an expression and some
Operands which are an expression list. The value of a compound expression
is found by evaluating the operands and evaluating the operator, whose value
should be a function (see section 4.5'Doublets' for the case where the operator is a doublet). The sequence in which these evaluations are carried out is
not defined. The function obtained from the operator is then applied to the
n-tuple obtained by evaluating the operands. The case where the number of
arguments required by the function is not equal to the number of items
obtained by evaluating the operands is dealt with in section 5.3 'Statements
224

BURSTALL AND POPPLESTONE

and imperatives'. The results of this application are the value of the expression. Thus the value of the expression is an n-tuple, with n=0 if the function
is a routine.
Evaluation of conditional expressions is described in section 6.1 'Conditional expressions', and that of imperative expressions in section 5.3 'Statements and imperatives'.
An expression list is evaluated by evaluating the expressions of which it
consists and concatenating the results. The order in which the evaluations
are made is not defined. The order in which the results of evaluating the
expressions are concatenated is the order in which the expressions occur.
The syntax of expressions is given below. There are a number of syntactic
forms for compound expressions. A further explanation of the syntax is
given in section 5.2 'Precedence'.
::= I nonop 
::= I  I ::= I  I  I'::= I 
::=
::=  ()
Kexpression ?Xoperation>
'
::= I 
I 
::= . 
::=
::= ,  I 
 I 
I  I 
()
Examples:
e.g.::=x I nonop+ I 3 I lambda x; x+ 1 end I [3 5 9]
e.g.::= + I *** I adjoin
e.g.::=f(x+ 1, y) I a*(b+ c) I x.hd
If(%x %)1E/ x+ 1, x+2 %i
e.g.::= a I g(h(x +1)) I if x=0 then y else z close
(x+1—•x; y+ 1 —■y; x*y)
(x, y+ 1, z-1)
The various syntactic forms of compound expressions denote the operator
and operands in the following way:
(i)   • . This is equivalent to:
nonop  (, ) which is a special case
of(i) above.
(iii) . . This is equivalent
to:
 () which is a special case of
(i) above.
(iv) . This is equivalent to (i) above with a special
identifier for the operand. The exact rules are given in section 4.4 'Partial
Application' and section 8.3 'Lists'.
Note that there is no syntactic provision above for compound expressions
whose operator is an expression other than an identifier.

5.2. Precedence
If a compound expression or quasi compound expression is of the form
  
the operator is the operation. In this case ambiguity might arise in the analysis of expressions such as
    
which could be analysed with association to the left or to the right. This
ambiguity is resolved by the notion of precedence. A precedence is a positive
integer between 1 and 7 associated with an operation identifier. It is set by a
declaration and can only be changed by cancellation. The operator of a
sequence of expressions containing one or more operations is the operation
of highest precedence or if there is more than one operation of highest
precedence the rightmost of these.
It must be made clear that the difference between an operation and any
other identifier which is restricted to having function values is purely a
syntactic one.
It may be desired to use an operation in a context other than as the operator
of a compound expression. If so it must be prefixed with the word nonop
in which case it is treated syntactically like any other identifier. The use of
nonop overrules the precedence of the identifier but does not remove
restriction of its values to functions. This facility enables operations to
appear as operands and enables assignment to operations.
Example:
> has precedence 7, + and — have precedence 5 and * has precedence 4.
5 — x+2*y> 1+2 is the same as ((5 —x)+(2*y))>(1+2).

5.3. Statements and imperatives
A statement is either an assignment, a goto statement, a machine code
instruction or an expression list. It may be labelled.
226

BURSTALL AND POPPLESTONE

An imperative is either a declaration or a statement.
The syntax is:
::= I 
I  I 
I 
::= I 
::=;  I

Example:
e.g.::=loop:x-1—■x; f(x)—oy; if x>O then goto
loop;
I x+1—q; y; u—oy;—+z;
The evaluation of an Imperative Sequence consists of evaluating the statements in the sequence in which they occur, except when a goto statement
oceurs and the sequence continues at the point indicated by the goto statement.
An Imperative Expression may be formed from an imperative sequence.
The syntax is:
(imperative expression>::=()
The Stack is an ordered sequence of items. The last item to be added to
this sequence is said to be on Top of the Stack. Items can be added to the
top of the stack or removed from the top of the stack. On entry to the
Pop-2 system the stack is empty. When a statement is evaluated any results
produced are added to the top of the stack. The results of an imperative
sequence are the items left on the stack when the sequence has been evaluated.
Evaluation of a statement which is a compound expression may affect the
stack as follows. If the number of arguments required by the function
obtained by evaluating the operator is not the same as the number of items
produced by evaluating the operands, these items are loaded on to the stack
in sequence. The function then takes its arguments off the stack, the last
argument being the one which was on the top of the stack. Thus suppose that
the function requires m arguments and the operands yield n items. If m>n the
first m—n arguments are taken off the stack. If m::=
Source Exif Data: 
File Type                       : PDF
File Type Extension             : pdf
MIME Type                       : application/pdf
PDF Version                     : 1.6
Linearized                      : Yes
Create Date                     : 2013:02:24 16:33:35-08:00
Creator                         : OmniPage CSDK 18
Modify Date                     : 2013:02:24 16:34:00-08:00
Has XFA                         : No
XMP Toolkit                     : Adobe XMP Core 4.2.1-c043 52.372728, 2009/01/18-15:56:37
Metadata Date                   : 2013:02:24 16:34-08:00
Creator Tool                    : OmniPage CSDK 18
Format                          : application/pdf
Document ID                     : uuid:0eb12b89-4a8b-1940-93cc-34ac5debcb05
Instance ID                     : uuid:f9eca50c-d464-f94b-aef7-d384e58c5808
Producer                        : OmniPageCSDK18
Page Count                      : 42
EXIF Metadata provided by EXIF.tools

Navigation menu