1.  Organization

      Most of px is written in the 11/780"" VAX 11/780 assembly language, using the UNIX® assembler as. Portions of px are also written in the UNIX systems programming language C. Px consists of a main procedure that reads in the interpreter code, a main interpreter loop that transfers successively to various code segments implementing the abstract machine operations, built-in procedures and functions, and several routines that support the implementation of the Pascal input-output environment.

      The interpreter runs at a fraction of the speed of equivalent compiled C code, with this fraction varying from 1/5 to 1/15. The interpreter occupies 18.5K bytes of instruction space, shared among all processes executing Pascal, and has 4.6K bytes of data space (constants, error messages, etc.) a copy of which is allocated to each executing process.

1.1.  Format of the object file

      Px normally interprets the code left in an object file by a run of the Pascal translator pi. The file where the translator puts the object originally, and the most commonly interpreted file, is called obj. In order that all persons using px share a common text image, this executable file is a small process that coordinates with the interpreter to start execution. The interpreter code is placed at the end of a special ``header'' file and the size of the initialized data area of this header file is expanded to include this code, so that during execution it is located at an easily determined address in its data space. When executed, the object process creates a pipe, creates another process by doing a fork, and arranges that the resulting parent process becomes an instance of px. The child process then writes the interpreter code through the pipe that it has to the interpreter process parent. When this process is complete, the child exits.

      The real advantage of this approach is that it does not require modifications to the shell, and that the resultant objects are ``true objects'' not requiring special treatment. A simpler mechanism would be to determine the name of the file that was executed and pass this to the interpreter. However it is not possible to determine this name in all cases.***
*** For instance, if the pxref program is placed in the directory `/usr/bin' then when the user types ``pxref program.p'' the first argument to the program, nominally the programs name, is ``pxref.'' While it would be possible to search in the standard place, i.e. the current directory, and the system directories `/bin' and `/usr/bin' for a corresponding object file, this would be expensive and not guaranteed to succeed. Several shells exist that allow other directories to be searched for commands, and there is, in general, no way to determine what these directories are.

1.2.  General features of object code

      Pascal object code is relocatable as all addressing references for control transfers within the code are relative. The code consists of instructions interspersed with inline data. All instructions have a length that is an even number of bytes. No variables are kept in the object code area.

      The first byte of a Pascal interpreter instruction contains an operation code. This allows a total of 256 major operation codes, and 232 of these are in use in the current px. The second byte of each interpreter instruction is called the ``sub-operation code'', or more commonly the sub-opcode. It contains a small integer that may, for example, be used as a block-structure level for the associated operation. If the instruction can take a longword constant, this constant is often packed into the sub-opcode if it fits into 8 bits and is not zero. A sub-opcode value of zero specifies that the constant would not fit and therefore follows in the next word. This is a space optimization, the value of zero for flagging the longer case being convenient because it is easy to test.

      Other instruction formats are used. The branching instructions take an offset in the following word, operators that load constants onto the stack take arbitrarily long inline constant values, and many operations deal exclusively with data on the interpreter stack, requiring no inline data.

1.3.  Stack structure of the interpreter

      The interpreter emulates a stack-structured Pascal machine. The ``load'' instructions put values onto the stack, where all arithmetic operations take place. The ``store'' instructions take values off the stack and place them in an address that is also contained on the stack. The only way to move data or to compute in the machine is with the stack.

      To make the interpreter operations more powerful and to thereby increase the interpreter speed, the arithmetic operations in the interpreter are ``typed''. That is, length conversion of arithmetic values occurs when they are used in an operation. This eliminates interpreter cycles for length conversion and the associated overhead. For example, when adding an integer that fits in one byte to one that requires four bytes to store, no ``conversion'' operators are required. The one byte integer is loaded onto the stack, followed by the four byte integer, and then an adding operator is used that has, implicit in its definition, the sizes of the arguments.

1.4.  Data types in the interpreter

      The interpreter deals with several different fundamental data types. In the memory of the machine, 1, 2, and 4 byte integers are supported, with only 2 and 4 byte integers being present on the stack. The interpreter always converts to 4 byte integers when there is a possibility of overflowing the shorter formats. This corresponds to the Pascal language definition of overflow in arithmetic operations that requires that the result be correct if all partial values lie within the bounds of the base integer type: 4 byte integer values.

      Character constants are treated similarly to 1 byte integers for most purposes, as are Boolean values. All enumerated types are treated as integer values of an appropriate length, usually 1 byte. The interpreter also has real numbers, occupying 8 bytes of storage, and sets and strings of varying length. The appropriate operations are included for each data type, such as set union and intersection and an operation to write a string.

      No special packed data formats are supported by the interpreter. The smallest unit of storage occupied by any variable is one byte. The built-ins pack and unpack thus degenerate to simple memory to memory transfers with no special processing.

1.5.  Runtime environment

      The interpreter runtime environment uses a stack data area and a heap data area, that are kept at opposite ends of memory and grow towards each other. All global variables and variables local to procedures and functions are kept in the stack area. Dynamically allocated variables and buffers for input/output are allocated in the heap.

      The addressing of block structured variables is done by using a fixed display that contains the address of its stack frame for each statically active block.**
** Here ``block'' is being used to mean any procedure, function or the main program. This display is referenced by instructions that load and store variables and maintained by the operations for block entry and exit, and for non-local goto statements.

1.6.  Dp, lc, loop

      Three ``global'' variables in the interpreter, in addition to the ``display'', are the dp, lc, and the loop. The dp is a pointer to the display entry for the current block; the lc is the abstract machine location counter; and the loop is a register that holds the address of the main interpreter loop so that returning to the loop to fetch the next instruction is a fast operation.

1.7.  The stack frame structure

      Each active block has a stack frame consisting of three parts: a block mark, local variables, and temporary storage for partially evaluated expressions. The stack in the interpreter grows from the high addresses in memory to the low addresses, so that those parts of the stack frame that are ``on the top'' of the stack have the most negative offsets from the display entry for the block. The major parts of the stack frame are represented in Figure 1.1.


center; c l l l _ l | l | | cw(18) | aw(28) | _ | l | c | a. Base of stack frame Block mark Positive offsets

<- Display entry points here

Local variables

_ Negative offsets Temporary expression space

| _ | l c l.

Top of stack frame

Figure 1.1 - Structure of stack frame

Note that the local variables of each block have negative offsets from the corresponding display entry, the ``first'' local variable having offset `-2'.

1.8.  The block mark

      The block mark contains the saved information necessary to restore the environment when the current block exits. It consists of two parts. The first and top-most part is saved by the CALL instruction in the interpreter. This information is not present for the main program as it is never ``called''. The second part of the block mark is created by the BEG begin block operator that also allocates and clears the local variable storage. The format of these blocks is represented in Figure 1.2.




center; l l | cw(22n) | aw(20n). _ Created by CALL Saved lino

Saved lc

Saved dp

_ Created by BEG Saved dp contents

Pointer to current entry line and section name

Current file name and buffer

Top of stack reference

| _ | l.

Figure 1.2 - Block mark structure

      The data saved by the CALL operator includes the line number lino of the point of call, that is printed if the program execution ends abnormally; the location counter lc giving the return address; and the current display entry address dp at the time of call.

      The BEG begin operator saves the previous display contents at the level of this block, so that the display can be restored on block exit. A pointer to the beginning line number and the name of this block is also saved. This information is stored in the interpreter object code in-line after the BEG operator. It is used in printing a post-mortem backtrace. The saved file name and buffer reference are necessary because of the input/output structure (this is discussed in detail in sections 3.3 and 3.4). The top of stack reference gives the value the stack pointer should have when there are no expression temporaries on the stack. It is used for a consistency check in the LINO line number operators in the interpreter, that occurs before each statement executed. This helps to catch bugs in the interpreter, that often manifest themselves by leaving the stack non-empty between statements.

      Note that there is no explicit static link here. Thus to set up the display correctly after a non-local goto statement one must ``unwind'' through all the block marks on the stack to rebuild the display.

1.9.  Arguments and return values

      A function returns its value into a space reserved by the calling block. Arguments to a function are placed on top of this return area. For both procedure and function calls, arguments are placed at the end of the expression evaluation area of the caller. When a function completes, expression evaluation can continue after popping the arguments to the function off the stack, exactly as if the function value had been ``loaded''. The arguments to a procedure are also popped off the stack by the caller after its execution ends.

      As a simple example consider the following stack structure for a call to a function f, of the form ``f(a)''.

center, allbox; lw(20). T{

Space for

value returned
from f
T} T{ Value of a
T} T{

Block Mark

T}

Figure 1.3 - Stack structure on function call `f(a)'

      If we suppose that f returns a real and that a is an integer, the calling sequence for this function would be:




lp-2w(8) l. PUSH -8 RV4:l a CALL:l f POP 4

      Here we use the operator PUSH to clear space for the return value, load a on the stack with a ``right value'' operator, call the function, pop off the argument a, and can then complete evaluation of the containing expression. The operations used here will be explained in section 2.

      If the function f were given by


 10 function f(i: integer): real;
 11 begin
 12     f := i
 13 end;
then
f
would have code sequence:





lp-2w(8) l. BEG:2 0 11 "f" LV:l 40 RV4:l 32 AS48 END

      Here the BEG operator takes 9 bytes of inline data. The first byte specifies the length of the function name. The second longword specifies the amount of local variable storage, here none. The succeeding two lines give the line number of the begin and the name of the block for error traceback. The BEG operator places a name pointer in the block mark. The body of the function first takes an address of the function result variable f using the address of operator LV a. The next operation in the interpretation of this function is the loading of the value of i. I is at the level of the function f, here symbolically l, and the first variable in the local variable area. The function completes by assigning the 4 byte integer on the stack to the 8 byte return location, hence the AS48 assignment operator, and then uses the END operator to exit the current block.

1.10.  The main interpreter loop

      The main interpreter loop is simply:


iloop:
	caseb	(lc)+,$0,$255
	<table of opcode interpreter addresses>

      The main opcode is extracted from the first byte of the instruction and used to index into the table of opcode interpreter addresses. Control is then transferred to the specified location. The sub-opcode may be used to index the display, as a small constant, or to specify one of several relational operators. In the cases where a constant is needed, but it is not small enough to fit in the byte sub-operator, a zero is placed there and the constant follows in the next word. Zero is easily tested for, as the instruction that fetches the sub-opcode sets the condition code flags. A construction like:


_OPER:
	cvtbl	(lc)+,r0
	bneq	L1
	cvtwl	(lc)+,r0
L1:	...
is all that is needed to effect this packing of data.
This technique saves space in the Pascal
obj
object code.

      The address of the instruction at iloop is always contained in the register variable loop. Thus a return to the main interpreter is simply:


	jmp	(loop)
that is both quick and occupies little space.

1.11.  Errors

      Errors during interpretation fall into three classes:


1) Interpreter detected errors.
2) Hardware detected errors.
3) External events.

      Interpreter detected errors include I/O errors and built-in function errors. These errors cause a subroutine call to an error routine with a single parameter indicating the cause of the error. Hardware errors such as range errors and overflows are fielded by a special routine that determines the opcode that caused the error. It then calls the error routine with an appropriate error parameter. External events include interrupts and system limits such as available memory. They generate a call to the error routine with an appropriate error code. The error routine processes the error condition, printing an appropriate error message and usually a backtrace from the point of the error.