Digital PDFs

XX-ED707-B3

2000

4 pages

Original

0.3MB

view download

OCR Version

0.3MB

view download

Document:	An Efficient ALGOL-60 System for the PDP/8
Order Number:	XX-ED707-B3
Revision:	0
Pages:	4
Original Filename:	RogAlgol.pdf

OCR Text

AN EFFICIENT ALGOL-60 SYSTEM FOR THE PDP8
Roger H.

Abbott

A.R.C. Unit of Muscle Mechanisms & Insect Physiology
Department of Zoology, University of Oxford
South Parks Road, Oxford 0X1 3PS, U.K.

ABSTRACT

A one-pass compiler translates nearly full Algol-60 into an

intermediate language, whose instructions and variable addresses

The run-time system loads the intermediate
are 6 bits long.
language into core memory, and performs the operations

specified by its 6L instructions.

Execution speed is limited

and is nearly as fast as proIt is about 6 times faster
grams written in machine code.

by floating point arithmetic,

than 0S8/8 Fortran on a machine with EAE, although compiled

programs occupy only one-third of the space.

Minimum hard-

The system can run under
ware 1s an 8K PDP8 with teletype.
A 12K machine can use Field 2 for array
Monitor or 0S/8.
storage.

INTRODUCTION

The purpose of a compiler is to provide an inter-

face between a program written in a symbolic

language and the equivalent binary patterns on which
the hardware of the machine can operate.

This

applied equally to machine code and the so-called
high level languages.

There are three fairly

distinct ways to set about this

sufficient for running Algol.

symbolic language into binary or a high level language into symbolic machine code or binary.
The
machine can then run the compiler output as it
stands.

(b) The compiler may translate a high level language
into a code which is not machine code,

but whose
instructions perform the functions which are needed
in the high level language concerned.
A run-time
program then examines these codes, and executes the
tasks they specify by means of subroutines.
We
could include in this class compilers whose output,
although machine code, consists mainly of subroutine

calls.
This latter method is not very efficient,
because it takes more instruction bits to specify a
hardware subroutine jump and the address of the subroutine than it does to have a code number specifying which out of a list of subroutines should be
executed.

(¢) The high level language can be stored in the
machine as it stands, with no compilation.
A run
time program interprets it, in a manner similar to
().
This method has the dual advantage that the
program 1s easily modified,

Basic interpreters.

and the

system can be

Focal works in this way,

as do

The disadvantage of the method

is that programs run relatively slowly.

execution speed of a well-designed system,

because

it must be done by software, so method (b) should
A 6 bit
not be noticeably slower than method (a).

instruction allows 64 different codes, which 1s quite

task.

(a) A compiler can be written to translate the

made conversational.

mediate code (b), because operations which could be
In
performed by subroutine are done by open code.
the PDP8, floating point arithmetic will limit the

It is not

really a competitor tomethods (a) and (b), which are
used when speed and economy of memory are more

important than user interaction with the running of
the program.

Since the execution of a high level language requires operations more complex than are provided by

the machine instructions of most computers (and
certainly the PDP8!), a program translated by method

(a) will be longer than one translated into an inter-

It also suffices as

an address length, since 64 variables in any proced-

are adequate. Two 6
ure plus 64 in the main program
bit instructions can be packed into a single PDP8

word.
Therefore, method (b) using 6 bit instructions is the best one for the PDP8.

DEC do not offer such a system, the nearest being 4K

It was
Fortran which interprets 12 bit codes.
decided to write an Algol compiler because this is
a much more convenient and powerful language than

Fortran, and because the PDPB lacked an Algol-60
compiler.
Design Objectives

As well as being efficient, a high level language
system should be convenient to operate.
In practice,
on a small machine, this means that the translation
should involve the minimum number of passes, with
The
the compiler output being as short as possible.
run-time system should also be short, and be designed
in such a way that the Algol program can use

any

It should
peripheral devices that the machine has.
not be geared to any particular operating system,

such as 0S/8 or Monitor, but should be capable of

running under

any such system.

THE OBJECT CODE

It was therefore decided that the Algol should be
translated in a single pass into a form which could
be loaded directly into memory.
Because of the
desirability of being able to include machine code
statements in the Algol program, the compiler output should be compatible with PAL, so that compiler

output and copied machine code could be compiled

In the PDP8, it is

together into absolute binary.

The

essential that page boundaries be irrelevant, which
means that all label addresses must be 12 bits.

(Variable addresses are 6 bits, as already mention-

ed).

which represents two

code

are

that

code whose

and 83 for

the

which is

false.

Colons

the arrow.

whether S1 was

PAL,

lower part of Fig.

In the

After the arrow,
1

shows

;

a label
are

locally declared integers,

through the

checks

recursive

clause

The most often quoted advantage of Algol over Fort-

Next it checks

ran is

else (212).

can be called recursively

which is

symbol

two

firstly

because factorial is most naturally and efficiently

1nteger

then,

its

jump.

outputs
value

terminated by

full Algol-60,

statement:

original

itself.

intention was

if Boolean then S1 else S2;
concluding another condit-

This

system to

check

run time,

This

space

statement brackets

can be declared after any begin.,

and

needed

begin..

procedures

Evidently,

Janguage which is defined recursively requires a
recursively written compiler.
Algol provides recursion, and as it is an Algol compiler which we wish
construct,

the

compiler

the

obvious

thing to do 1s

the

Firstly,
the

system,

s52;

*TAEN'

to write

in the

Li:

leaving more

space

and

routines

for

run-time programs

identifier

*IF*'

organised,

533

on.

The

*TAEI'

LLECILD)

STATEMEIT;

LDEC(L2)

BS#212

for.

Some

Algol

since variables

one

systems,

they are

in which

In the PDP8 system

modern ones

included,

the big difficulties

All

state

of writing
The method

that is necessary is

by their position in the memory

of Bottom in Fig.

When a procedure

This

contains

the

Another pointer marks

entered,

the base

pointer is

set

ta the previous value of the next free space pointer,
s0 that the new procedure has
all

of Algol

the next free space at the end of the variables.

STATEMEITS

L2:=JMPIEV; LDEC(LD)S

Section

the way the data

created

but in reality 1t is easy.

shown in Fig.

address

CONDITIONAL

Fig.

are

In addition recursion must be allowed

text-books,

refer to variables

"ENL®

'END*

entering

main feature which

variable allocation within a procedure is handled by

FALSE LI;

LI1,LE&;

for doing

and cease to exist when the block

that this

La:

operating

tables.

and

Ly JUMP IF FALSE L 13
513 aJUMP LE5

'IF® BS5=366 'TiEl" TAINIC33)s

VELSE''BEGIN® ABS:

compiler

contain routines

relative to a base pointer.

*BEGIJ''IVTEGER®

the

subroutines

the compller.

EY-H

for dealing with them,

evaluating Boolean expressions,

declared,

VELSE'*1F' ©S5=366 °*TAEY''COMMEIT' 366 1S 'IF's

Ll:=IFCLAUSE;

a great deal

arithmetic,

52;4\

Li:

compiler

consists mainly of procedure

compiler,

not have

JUMP IF

of procedure parameters

which saves

compiler

because

necessary in a full

distinguishes Algol from Fortran is

SiJ

'IF* B 'THEN" S1
'ELSE* 523 535

THE RUN-TIME SYSTEM

COMPILED

compiler in

omitted in the

they are declared is left.
'IF*

the

impossible
it

types

check

system does

All

in Algol.

ALGOL

compile S2

calls (the example in Fig. 1 consists entirely of
procedure calls).
Secondly, real quantities are not

if Boolean then S1 else if B then S3 else Shs

and variables

to write

proved to be

writing Algol

ional:

it must compile

using a full compiler to compile

space problems.

the

but if it was,

and secondly because

that the language 1s
For example, in the condition

example,

label

and finally declare I12.
The

further

the

The compiler then

to see whether S1 was

the label L1,

defined recursively.

If it was not, all it has to do is

the main advantage of Algol is

...end may be nested,

are held

that they remain

a jump to a new label (L2), declare L1,

this recur-

declare

doubly unfortunate,

S2 may be any statement,

com-

called

labels

example.

evaluated without recursion,

The

statements.

with the evaluation of factorial belng used as an
is

label.

checks that the next symbol 1s not another if (s1
may not be conditional), and if not it compiles S1.

THE COMPILER

This

a Boolean expression,

Jjump and returns

number of the conditional

the

same up to

or by else.

calls.

compiles

that the next

if it is

the

Because
the

procedure

and S1,

"Jump if false" is a

statement,

numbers

with

the Algol

the portion of the

intact

the code depends on

terminated by

label

conditional

that procedures

execute

and jump to

recursively in two places.
sion the

may not

for the

to examine the result

is part of procedure

the program area.

that

piler which deals with conditional

latter case, they are usually equated with a previously declared label.
It is a simple matter to
have the loader replace these symbolic labels by
their binary equivalents.
Floating point literals
are read into the floating point accumulator by the
same routine that reads floating point numbers when
the program is running.
The loader transfers them

equivalents,

signify the definition of

by the pseudo-op DECIMAL.,

or by their definition with an equals sign.

but

B stands

compiled programs

Labels are defined in one of the ways allowed by
either by their occurrence followed by a comma,

two

the Boolean expression B,

Jjob it is

Note that the

the

statment.

ambiguous.

translated

codes

Boolean expression,

followed again

left,

statement,

statements of the same names.

These consist of the

followed by the literal,

shown the

evaluates

followed by a decimal number.

simply copied from the Algol text,

on the

conditional

then and else removed.

pseudo-op FLTG,

Algol

the resulting statement is

right

separate 6 bit instructions.
(b) A label address, consisting of the letter L
(¢) Floating point literals.

shows,

conditional

another

the 1f,

(a) A signed decimal number,

may be
the

item:

of Fig.
of

because

This was achieved by having three types of

loadable

top part

possible forms

Compiler

to itself.

This

a section of memory

arrangement is known as

a stack.

will
Top
of B

nd arrgz

Procedure B
Called by A

|
|values

Link to A

1st array
(pasedeptRi |

Procedure A

Depthfarrays

Link to main

program

word-wise

part

Lower bound 3
Muttiplier 3

Bottom of A

Multiplier 2

Return address
|BottomB*|
Number of B

Lower bound|
No. subscripts,

Lower bound 2

Single array

machine

exit

can be

from the

address

the

pointers,

that

restored

its

called for.

thelr first parameter

a device number,
The

in the

this

area.

unique number which identifies
1s

under

refers

consideration.

state when

The return

The

first

jumped

levels,

declared.

against the
level

address

the

because

different,
numbers

at higher

procedure

this number

levels

exist

Jumps

the

label

checked

that

If it

removed until

the

the time

of the

Jump

Arrays

present

appear

and disappear within a

their

problem because
single

are held on a

separate

which arrays

are

of declaration.
level

are

stack,

ordinary variable
declared

which is
stack.

the

first

declaration depth,

and

the 12K overlay is
at the next free
stored
link

are

the

out

second

top and base

the

address
dope

are

where

array

pointers

in the

of an element,

vector is

given

set up at run

In the 8K system,

immediately above

the dope

vector, but in 12K Algol the last word of the
vector contains the address in field 2 where the
array begins.

The

operating system

using

an over-~

standard

used

Device

suppress

output

the

teletype

1s
as

the

systems

device,

an overlay to
operating

the

and

whose

routines

run-time

program,

catered

for.

systems

can be

used

for

time

system allows

just

that,

the

organisation

them to be

tape includes

tables

are

of machine

the run

used for activating

code.

SYSTEM

PERFORMANCE

Speed
The

speed

attainable

in a

ing point

arithmetic

program which uses

limited by

floating point software.
BxB has

been timed

the

speed

in a program written

and in Algol.

floatof

the

The statement A:=A+B-A/
in machine

In a machine which has

no EAE

Algol is only about 15% slower.
If an EAE is
available, Algol
1is about 80% slower, although it
is

nearly twice

EAE.

fast

re-write

machine

a machine without

this

arithmetic

and when this

fast

believed that

in needless

planned

these,
as

code

the

extra time
stack

run time

system

done

Algol

machine

spent

operations.
to

Time

Length

msec|words

with EAE.

122

|25

2
Y

NN
AzA+B-A/BxB

Azexp(sin(1-0)

[ ]

NAY

A=00

OS/8FORTRAN

g7
ALGOL

the

ALGOL+ EAE

loader,

the memory which

Fig.

avoid

should be nearly

EXECUTION TIME
& CODE LENGTH

which occupies with its

system

indication in input proc-

When

the information neces-

This

array elements

table,

In the

the

level.

Each array starts with a dope

all

a failure

can

Users

a third word points

time when the array is declared.
the

The array base pointer is

which contains

subscripts.

the

space in field 2,

along with

sary to work
the

the

in operation,

stored.

information.

vector,

table

embedded

Blocks

containing the

current

base

Arrays

are numbered by depth

pointer

elements

and

At the beginning of each array

two words,
the

they may

procedure

size is not known until run-time.

within the

but

in the

system.

procedures.

mainly

compiler.

special

which must
logical

Currently, Monitor and 0S/8 overlays are available.
Although the input/output procedures are normally

are

to any number by placing the

routine

O gives

various

code

into procedures which

in the memory at

are prohibited by the

identi-

the procedure

pointer.
are

the

in which

identifying number of

correspond.

numbers

and are used to address

lay to the run-time

any plece

a yet

such labels

active

procedure

At run time,

the

procedure

at every label

pointed at by the base

do not

in which case the pointers must be reset.

fication number

in the

to from procedures

The compiled program has

0-7.

can assign any device

also used at labels

declared in the Algol program,
can be

called at

variables
It

code in any

input/output machine code routine addresses.

written

the procedure.

needed when a procedure

higher level

range

device numbers,

Device

the

location in the procedure variable areacontains
This

code

could

device 2 the high-speed reader/punch combination.

procedure

also held

system

output

Within the new procedure's memory are stored the
of

the

loaded

the

any memory field.

cedures,

values

and

but

All the built-in input/output procedures have as

device

ROGALGOL 8K DATA STORAGE

output

INPUT/OUTPUT

Variables
Array base A

Fig.

compiler

relocatable,

Current procedure 22

Active data

the

easily be modified to load and run the

of
array

A "234 basq

Top ofA

Main

Elements

de|

Array

Currently,

into field O starting at location 200,

Dope vector

Called by main

be used for data storage when the program is

running.

Fig. 3 shows a more detailed comparison between

routines

In each case, the Algol

0S/8 Fortran and Algol.

values are represented as a fraction of the 03/8
Without EAE, Algol is about 3

Fortran values.

times as fast, and with EAE about 6 times as fast.

Storage requirements

3 also shows that the compiled Algol code is

only one-third of the length of compiled Fortran
However, the saving in space is greater, for
code.
two reasons.
Firstly there is a greater amount of

Fig. b

shows a memory map of an 8K machine, the cross-

hatched areas are ones occupied by the system,

and

77177

/
DATA

// 07777

(Systems device) |

|(Systems device)

PROGRAM

(+DATA)

DATA

)
0S/8 FORTRAN

ROGALGOL

MEMORY AVAILABLE TO USER
Fig,

The hatched areas are occuplied by system routines.
The

items

not available

in brackets

are optional.

to the programmer.

The Fortran

system 1s evidently much longer, although it has to
be admitted that this is partly due to the greater

facilities of the input/output handler.
The second reason is more subtle.
machine code,
short,

When using

we automatically think of writing a

program as a series of subroutines,
because this saves

which are often

space and makes the logic

of the program easier to follow.
Fortran is very
subroutines, because each one occupies at
least one page, and has to be compiled separately.
bad at
This

ran,

and although this may be

sometimes

quoted as

an advantage

of Fort-

true in general it is

certainly not true of the PDP8 implementation.
Algol

is efficient in this respect.

described here,

In the

system

the minimum length of a compiled

procedure is 3 words,

compared with Fortran's 128

words.

The Algol

compiler is

Fortran compiler.

The

about

the

same length as

good

starting reference

for

those wishing to

Annual Reviews in Automatic Programming.

of the arithmetic routines.

memory available for storing programs.

the linking loader

learn more about Algol Compilers is Vol.

Fortran is hardly speeded up at all by use of the
EAE, because its speed is not limited by the speed

Fig.

are about as long as

program needed by the Fortran system.

the

complete Algol run-time

3 of