TEACH POPSYS Steve Hardy Dec 1982
INCOMPLETE
HOW THE POP11 SYSTEM WORKS
==========================
Keywords
--------
Compiler, interpreter, LISP, machine code, syntax analysis, lexical
analysis, list cell, garbage collection.
This handout points out those areas of computer science necessary for an
understanding (even slight) of how the POP11 system works. More detailed
discussion of some of the topics presented here can be found in TEACH VM
and TEACH GC.
We can divide an understanding of how the POP11 system works into two
parts. Firstly, how is the translation from POP11 to a language the
machine can understand done, and secondly, how are the important
features of POP11. (In particular list structures,) implemented?
An important phase in the translation process is the formation of an
intermediate representation of the program that is called a 'parse
tree'. This parse tree is in many ways analagous to a LISP program and
so an understanding of LISP itself is useful. There is then a second
phase of translation from LISP to machine code. To completely understand
the second phase of translation, the reader must understand something of
machine code itself.
The two principal data structures of POP11 (and LISP) are "the word" and
"the list". We need to know how these can be represented on the VAX's
memory - this, of course, requires an understanding of the VAX's
memory.
A third important aspect of understanding POP11 is the operating system,
for it is via the operating system that POP11 programs communicate with the
'world'.
Translation Into LISP
----------------------
Translation of a high level language like POP11 into a LISP-like
language is usually called syntax analysis. This topic is described in
most books on compiling techniques and is usually dependent on an
understanding of "transformational grammars".
A related topic is 'lexical analysis', that is the conversion of
characters (e.g. 'C','A','T') into symbols, (e.g. "CAT").
LISP
----
No actual compiler would produce LISP as an intermediate representation
of a program. However, the parse trees produced will usually be very
like LISP and as LISP is well documented I will use it as a analogy for
a parse tree. There are many manuals on LISP itself.
Here is an example of a POP11 program:
define sum(list);
if list = []
then 0
else hd(list) + sum(tl(list))
endif
enddefine;
Here is the same program in LISP
(define (sum list)
(cond ((null list) 0)
(t (plus (hd list)
(sum (tl list))))))
Notice that in LISP, expressions are represented by lists. The HD of
such a list is the name of a procedure to be applied and the TL its
arguments. Notice, also, that the arguments of COND are 'condition -
consequent' pairs.
An important feature of LISP is that it can be "interpreted" by a LISP
interpreter. Therefore, it is useful if a reader understands something
of the way LISP is interpreted in a LISP system.
Code Generation
---------------
One of the disadvantages of interpreting code is that one usually
requires a complicated program, written in a simple language (usually
machine code) to do the interpreting. Furthermore, interpreting is
inevitably slower than direct execution by the machine itself. A
tremendous increase in efficiency can be achieved by translating LISP
into machine code. When carried out by a compiler, this process is
called "code generation".
Here is an example of a LISP expression;
(plus (hd list)
(sum (tl list)))
and here is its translation into a simple machine code:
push list
call hd
push list
call tl
call sum
call plus
Machine Code
------------
Machine code is a language, specific to each machine, which can be
understood by the hardware of the machine itself. That is, the
interpreter for machine code IS the machine. Perhaps surprisingly, most
modern computers have a very similar sort of language as their machine
code. Each instruction in a machine code program will usually perform
some very simple operation, for example:-
(1) Putting the value of a variable on to a stack.
(2) Putting a literal (e.g. a number) on to a stack.
(3) Taking the top item from the stack and putting it into a variable.
(4) Calling a sub-routine.
(5) Returning from a sub-routine.
(6) A jump instruction which breaks the normal sequential flow of
control.
(7) All programming languages require the ability to conditionally
execute code. One way of doing this is to have a "conditional jump
instruction". Unlike the jump instruction, this label will only be
"gone to" if some 'condition' is met (e.g. the top element of the
stack being TRUE).
Machine Memory
--------------
Most computers have a very simple memory structure. A large number of
numbered "words" - each word of the computer's memory can hold a number.
This contained number can be interpreted in any way we wish, for example
as an instruction to the hardware, as a character (e.g. A = 1, B = 2
etc.), as the address of another word in the machine's memory, "a
pointer" or, of course, as a number.
For a more detailed explanation of how we can represent POP11 objects
such as words and lists in this sort of memory, see the * WAL demo.
Garbage Collection
------------------
The computer only has a finite memory (in our case about 1 million words)
As the POP11 program is running it is creating various data structures
(e.g. lists, words, procedures, etc.). These data structures are
represented using some of the machine's memory. A problem arises - what
happens when the POP11 system has used all of the memory allocated to it
by the operating system? Now, many data structures are only temporary,
they are created, used for a while and then no longer wanted. (For
example, a procedure is re-defined, the data structure used to represent
the old definition is no longer wanted. POP11 contains a set of
procedures collectively called the "garbage collector" which attempts to
guess which of the data structures currently existing are no longer
wanted. These unwanted data structures are then made available for re-
use.
The Operating System
--------------------
There is a set of programs collectively called 'the operating system'
which exist to help programs make the best use possible of the computer.
They have two important rules:-
(1) The computer would be under-used if only one person could use
it at a time. When that one person was sat thinking, the machine
would be idle. To prevent this happening, the operating system
allows many people to use the machine on a "time sharing" basis.
First one user has her program running and then, whilst she is
thinking, another user's program can run. If more than one program
is runnable at any given moment, the operating system gives them
equal shares of the computer's time. The operating system also
protects users from one another (and indeed, protects itself from
them) if one user has an area that should not affect others. For
this reason, the operating system clearly defines what sort of
access each user can have to the machine (for example, how much of
the computer's memory they are allowed to use).
(2) Almost all programs want to communicate with the world in some
way, for example by reading input from the teletype or sending
output to the teletype or accessing the discs. These tasks are very
fiddly and moreover, it is essentially the same task, no matter
what program the user wants to run. For this reason, instructions
on how to work the individual devices are made part of the
operating system (thus preventing unnecessary duplication of code).
-----<Copyright University of Sussex 1987. All rights reserved.>-------Author: Steve Hardy Dec 1982