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). ------------