P-code for PL/0 machine

This page describes the assembler language assumed for the PL/0 p-code machine emulated by another page on this site.

The PL/0 virtual machine was originally specified by Nicklaus Wirth in his book Algorithms + Data Structures = Programs; it's used as the target machine for a PL/0 compiler.

Just as PL/0 is simpler than full Pascal, so also the virtual machine used by the PL/0 compiler is simpler than the p-code machines used by various Pascal compilers (e.g. Pascal-P from ETH Z├╝rich and UCSD Pascal's P-System). Students learning about p-code and virtual machines may find the PL/0 p-code easier to grasp than the p-code systems used by full Pascal compilers.

General

The machine has four registers and two storage areas. The two storage areas are:

stack
a stack used as a datastore for mutable data. Variables, information on function invocations, and temporary data are all placed on the stack. All values are integers.
code area
an immutable array of instructions; all instructions have the same format

The registers are:

P
program counter: points to an instruction in the program area
T
stack-top register: points to the current top of the stack
B
base address: points to the base address in the stack for the current invocation of a given procedure
I
instruction register: contains the currently executing instruction

Integer is the only datatype.

There is no input or output; a useful convention is for programs to leave their results in a pre-arranged location on the stack.

Instruction format

Each instruction consists of an op code and two arguments, which Wirth's source code refers to as l (short for level, and good luck to you if you are displaying things in a font that makes lower-case L and digit 1 look similar) and a (which might be argument or address). The op-code mnemonics used here (lit, opr, lod, sto, cal, int, jmp, and jpc) are drawn from the declaration of the fct type in Wirth's interpreter for the virtual machine. (Alas, I don't know what fct might be short for.)

The examples here will also allow a comment which begins with // and runs to the end of the line.

E.g.

STO 1 4 // stores the value in the 
        // fourth storage cell one level up

In some cases, one or both arguments are ignored.

In an assembler intended for practical use, symbolic references to locations would be possible. Wirth's p-code, however, is only a target language for the compiler, so symbolic references are not needed, and I haven't yet added them in this emulator.

Movement to and from memory and stack

Load

LOD level offset

Load (i.e. push onto the stack) the value of the cell identified by level and offset. A level value of 0 means the variable is in the currently executing procedure; 1 means it's in the immediately enclosing region of the program. 2 means it's the region outside that (in PL/0 as in Pascal procedures can nest indefinitely). The offset distinguishes among the variables declared at that level.

E.g.

LOD 0 0

Store

STO level offset

Store the value currently at the top of the stack to the memory cell identified by level and offset, popping the value off the stack in the process.

E.g.

STO 0 0

Literals

LIT 0 arg

Push the literal value arg onto the stack.

E.g.

LIT 0 20

Flow of control

Jump

JMP 0 address

Jump to the instruction at address.

E.g.

JMP 0 28 // go to instruction 28

Conditional jump

JPC 0 address

Pop the current value from the top of the stack. If it's 0 (false), jump to the instruction at address. Otherwise, continue with the current location of the program counter.

E.g.

JPC 0 29

Call subroutine

CAL level address

Call the subroutine at location address, which is level nesting levels different from the nesting level of the currently executing code. This instruction pushes a stack frame (or block mark) onto the stack, storing

  • the base address for variables, level blocks down on the stack (so that variables in outer blocks can be referred to and modified)
  • the current base address (so that it can be restored when the subroutine returns)
  • the current program counter (so that it can be restored when the subroutine returns)

E.g.

CAL 2 56 // goes up two levels in the block hierarchy,
         // calls subroutine at instruction 56 
	

Return

OPR 0 0

Return from a subroutine. This instruction uses the stack frame (or block mark) from the current invocation of the subroutine to clear the stack of all data local to the current subroutine, restore the base register, and restore the program counter. Like all operations which require no arguments, it uses the op code OPR, with a second argument (here zero) indicating which of the zero-argument operations to perform.

E.g.

OPR 0 0 // return

Tests / conditions

All of these tests operate on the value(s) at the top of the stack and require no other arguments. They are all represented by the op code OPR with a first argument of zero and a second argument indicating which test to perform.

The tests remove one (for the unary test odd?) or two (for the binary tests) items from the stack and then place a 1 or a 0 on the stack to indicate that the condition tested for is true or false.

Odd?

OPR 0 6

Test the value at the top of the stack to see if it's odd or not.

Equal?

OPR 0 8

Test the two values at the top of the stack to see if they are equal or not.

Not equal?

OPR 0 9

Test the two values at the top of the stack to see if they are unequal or not.

Less than?

OPR 0 10

Test the two values x and y at the top of the stack to see if x is less than y or not.

Here, y is the value on the top of the stack, and x is below it on the stack. Example:

LIT 10
LIT 11
OPR 0 10

This code will leave a 1 on the stack, because 10 is less than 11.

Greater than or equal to?

OPR 0 11

Test the two values x and y at the top of the stack to see if x is greater than or equal to y, or not.

Example:

LIT 10
LIT 11
OPR 0 11

This code will leave a 0 on the stack, because 10 is not greater than or equal to 11.

Greater than?

OPR 0 12

Test the two values x and y at the top of the stack to see if x is greater than y or not.

Here, y is the value on the top of the stack, and x is below it on the stack. Example:

LIT 11
LIT 10
OPR 0 12

This code will leave a 1 on the stack, because 11 is greater than 10.

Less than or equal to?

OPR 0 13

Test the two values x and y at the top of the stack to see if x is less than or equal to y, or not.

Example:

LIT 11
LIT 10
OPR 0 13

This code will leave a 0 on the stack, because 11 is not less than or equal to 10.

Arithmetic operations

All of these tests operate on the value(s) at the top of the stack and require no other arguments. They are all represented by the op code OPR with a first argument of zero and a second argument indicating which test to perform.

The operations remove one (for the unary operation, negation) or two (for the binary operations) items from the stack and then place the result of the operation on the stack.

Negate

OPR 0 1

Negate the value on the top of the stack (i.e. multiply by -1).

Add

OPR 0 2

Add the two values at the top of the stack and replace them with their sum.

Subtract

OPR 0 3

Subtract the value at the top of the stack from the value below it; replace the diminuend and the subtrahend with their difference.

Multiply

OPR 0 4

Multiply the two values at the top of the stack and replace them with their product.

Divide

OPR 0 5

Perform integer division on the two values at the top of the stack. The value on top of the stack becomes the divisor, the value below it the dividend. Replace the two values with their integer quotient.

Notes

No provision is made for arithmetic overflow or underflow. Students may find it a useful exercise to think about how provisions might be made for such conditions.

Similarly, no provision is made for passing parameters to subroutines or returning values from them. (In Pascal terms: PL/0 supports no functions, only procedures, and only zero-parameter procedures at that.) It is a useful exercise to think about what changes to the machine language might be required to support parameters and return values.

Links

Wirth's PL/0 compiler (apparently from Algorithms + Data Structures = Programs [1975]).

Wikipedia article on PL/0.

Wikipedia article on P-code machine (includes the source code for Wirth's interpret function, but not much explanation of PL/0 or the p-code developed for it).

Last updated 3 December 2011; typos corrected 16 February 2013