P-code machine

In computer programming, a p-code machine or pseudo-code machine is a specification of a CPU whose instructions are expected to be executed in software rather than in hardware (ie, interpreted). This term is applied both generically to all such specifications, although many specifications create their own name (e.g., Java uses byte-code), and to particular specifications (the most famous being UCSD Pascal p-code).

Although the concept was first implemented as O-code for BCPL, circa 1966, the term p-code first appeared on the scene in the early 1970s. Two early implementations of compilers generating p-code were the Pascal-P compiler in 1973, by Nori, Ammann, Jensen, Hageli, and Jacobi, and the Pascal-S compiler in 1975, by Niklaus Wirth.

Programs that have been translated to p-code are executed (interpreted) by a software program that emulates the behavior of the cpu specification. If there is sufficient commercial interest a hardware implementation of the specification may be built (e.g., the Pascal MicroEngine).

Why p-code?

* For porting purposes. It is much easier to write a small (compared to the size of the compiler) p-code interpreter for a new machine, as opposed to changing a compiler to generate native code for the same machine.

* For quickly getting a compiler up and running. Generating machine code is one of the more complicated parts of writing a compiler. By comparison, generating p-code is much easier.

* Size constraints. Since p-code is based on an ideal virtual machine, many times the resulting p-code is much smaller than the same program translated to machine code.

* For debugging purposes. Since p-code is interpreted, the interpreter can apply many additional runtime checks that are harder to implement with native code.

Some [http://www.swissdelphicenter.ch/en/niklauswirth.php articles] by Niklaus Wirth mention an m-code variant for Pascal successor Modula-2.

The Business Operating System (BOS) of the 1980s was a cross-platform operating system designed to exclusively run p-code based programs.

The UCSD p-System was a portable machine independent operating system based on p-code.

Architecture

The p-code is commonly executed on a stack machine, which means that most instructions take their operands from the stack, and place results back on the stack. So the "add" instruction replaces the two topmost elements of the stack with their sum. A few instructions take an immediate argument. Like Pascal, p-Code is strongly typed, supporting boolean (b), character (c), integer (i), real (r), set (s), and pointer (a) types natively.

Some simple instructions:

Insn. Stack Stack Description before after adi i1 i2 i1+i2 add two integers adr r1 r2 r1+r2 add two reals dvi i1 i2 i1/i2 integer division inn i1 s1 b1 set membership; b1 = whether i1 is a member of s1 ldci i1 i1 load integer constant mov a1 a2 move not b1 ~b1 boolean negation

Environment

Differing from other stack-based environments (such as Forth and Java Virtual Machine) the p-System has only one stack shared by procedure stack frames (providing return address, etc.) and the arguments to local instructions. Three of the machine's registers point into the stack (which grows upwards):

* SP points to the top of the stack (the stack pointer).
* MP marks the beginning of the active stack frame (the frame pointer).
* EP points to the highest stack location used in the current procedure.

Also present is a constant area, and, below that, the heap growing down towards the stack. The NP register points to the top (lowest used address) of the heap. When EP gets greater than NP, the machine's memory is exhausted.

The fifth register, PC, points at the current instruction in the code area.

Calling conventions

Stack frames look like this:

EP -> local stack SP -> ... locals ... parameters ... return address (previous PC) previous EP dynamic link (previous MP) static link (MP of surrounding procedure) MP -> function return value

The procedure calling sequence works as follows: The call is introduced with mst nwhere "n" specifies the difference in nesting levels (remember that Pascal supports nested procedures). This instruction will "mark" the stack, i.e. reserve the first five cells of the above stack frame, and initialise previous EP, dynamic, and static link. The caller then computes and pushes any parameters for the procedure, and then issues cup n, pto call a user procedure ("n" being the number of parameters, "p" the procedure's address). This will save the PC in the return address cell, and set the procedure's address as the new PC.

User procedures begin with the two instructions ent 1, i ent 2, jThe first sets SP to MP + "i", the second sets EP to SP + "j". So "i" essentially specifies the space reserved for locals (plus the number of parameters plus 5), and "j" gives the number of entries needed locally for the stack. Memory exhaustion is checked at this point.

Returning to the caller is accomplished via retCwith "C" giving the return type (i, r, c, b, a as above, and p for no return value). The return value has to be stored in the appropriate cell previously. On all types except p, returning will leave this value on the stack.

Instead of calling a user procedure (cup), standard procedure "q" can be called with csp qThese standard procedures are Pascal procedures like "readln()" ("csp rln"), "sin()" ("csp sin"), etc. Peculiarly "eof()" is a p-Code instruction instead.

Example machine

Niklaus Wirth specified a simple p-code machine in the 1976 book "Algorithms + Data Structures = Programs". The machine had 3 registers - a program counter, p, a base register b, and a top-of-stack register t. There were 8 instructions, with one (opr) having multiple forms.

This is the code for the machine:

procedure interpret; const stacksize = 500;

var p,b,t: integer; {program-, base-, topstack-registers} i: instruction; {instruction register} s: array [1..stacksize] of integer; {datastore}

function base(l: integer): integer; var b1: integer; begin b1 := b; {find base l levels down} while l > 0 do begin b1 := s [b1] ; l := l - 1 end; base := b1 end {base};

begin writeln(' start pl/0'); t := 0; b := 1; p := 0; s [1] := 0; s [2] := 0; s [3] := 0; repeat i := code [p] ; p := p + 1; with i do case f of lit: begin t := t + 1; s [t] := a end; opr: case a of {operator} 0: begin {return} t := b - 1; p := s [t + 3] ; b := s [t + 2] ; end; 1: s [t] := -s [t] ; 2: begin t := t - 1; s [t] := s [t] + s [t + 1] end; 3: begin t := t - 1; s [t] := s [t] - s [t + 1] end; 4: begin t := t - 1; s [t] := s [t] * s [t + 1] end; 5: begin t := t - 1; s [t] := s [t] div s [t + 1] end; 6: s [t] := ord(odd(s [t] )); 8: begin t := t - 1; s [t] := ord(s [t] = s [t + 1] ) end; 9: begin t := t - 1; s [t] := ord(s [t] <> s [t + 1] ) end; 10: begin t := t - 1; s [t] := ord(s [t] < s [t + 1] ) end; 11: begin t := t - 1; s [t] := ord(s [t] >= s [t + 1] ) end; 12: begin t := t - 1; s [t] := ord(s [t] > s [t + 1] ) end; 13: begin t := t - 1; s [t] := ord(s [t] <= s [t + 1] ) end; end; lod: begin t := t + 1; s [t] := s [base(l) + a] end; sto: begin s [base(l)+a] := s [t] ; writeln(s [t] ); t := t - 1 end; cal: begin {generate new block mark} s [t + 1] := base(l); s [t + 2] := b; s [t + 3] := p; b := t + 1; p := a end; int: t := t + a; jmp: p := a; jpc: begin if s [t] = 0 then p := a; t := t - 1 end end {with, case} until p = 0; writeln(' end pl/0');end {interpret};

This machine was used to run Wirth's PL/0, which was a Pascal subset compiler used to teach compiler development.

Further reading

* Steven Pemberton and Martin Daniels: [http://www.cwi.nl/~steven/pascal/book/ Pascal Implementation: The P4 Compiler and Interpreter] . ISBN 0-85312-358-6; ISBN 0-13-653031-1
* [http://homepages.cwi.nl/~steven/pascal/ Steven Pemberton's page on Pascal] has Pascal sources of the P4 compiler and interpreter, usage instructions, and [http://www.cwi.nl/ftp/pascal/pcom.code4.Z the p-code of the compiler] (generated by itself).
* [http://www.threedee.com/jcm/psystem/ The Jefferson Computer Museum's page on the UCSD p-System]
* [http://www.klebsch.de Open Source implementation]
* "Compiling with C# and Java", Pat Terry, 2005, ISBN 0-321-26360-X, 624
* "Algorithms + Data Structures = Programs", Niklaus Wirth, 1975, ISBN 0-13-022418-9
* "Compiler Construction", Niklaus Wirth, 1996, ISBN 0-201-40353-6
* "The Byte Book of Pascal", Blaise W. Liffick, Editor, 1979, ISBN 0-07-037823-1
* "PASCAL - The Language and its Implementation", Edited by D.W. Barron, 1981, ISBN 0-471-27835-1. Especially see the articles "Pascal-P Implementation Notes" and "Pascal-S: A Subset and its Implementation".

ee also

* Bytecode
* Pascal (programming language)
* Runtime
* compiler
* interpreter
* interpreted language
* PL/0
* UCSD p-System
* UCSD Pascal
* Joel McCormack
* Microsoft P-Code
* P-code is a kind of token threaded code