P-Code machine
Encyclopedia
In computer programming
Computer programming
Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...

, a p-code machine, or portable code machine is a virtual machine
Virtual machine
A virtual machine is a "completely isolated guest operating system installation within a normal host operating system". Modern virtual machines are implemented with either software emulation or hardware virtualization or both together.-VM Definitions:A virtual machine is a software...

 designed to execute p-code (the assembly language of a hypothetical CPU). This term is applied both generically to all such machines (such as the Java Virtual Machine
Java Virtual Machine
A Java virtual machine is a virtual machine capable of executing Java bytecode. It is the code execution component of the Java software platform. Sun Microsystems stated that there are over 4.5 billion JVM-enabled devices.-Overview:...

 and MATLAB
MATLAB
MATLAB is a numerical computing environment and fourth-generation programming language. Developed by MathWorks, MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages,...

 precompiled code), and to specific implementations, the most famous being the p-Machine of the Pascal-P system
Pascal (programming language)
Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...

, particularly in its UCSD Pascal
UCSD Pascal
UCSD Pascal was a Pascal programming language system that ran on the UCSD p-System, a portable, highly machine-independent operating system. UCSD Pascal was first released in 1978...

 incarnation.

Although the concept was first implemented circa 1966 (as O-code
O-code
O-code is an intermediate language emitted by the BCPL compiler. It is then compiled into the machine code for the computer which is intended to run the program. This method of compiling allowed the original BCPL compiler to be ported to new machines very easily and as a result it became...

 for BCPL
BCPL
BCPL is a procedural, imperative, and structured computer programming language designed by Martin Richards of the University of Cambridge in 1966.- Design :...

), the term p-code first appeared in the early 1970s. Two early compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...

s 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
Niklaus Wirth
Niklaus Emil Wirth is a Swiss computer scientist, best known for designing several programming languages, including Pascal, and for pioneering several classic topics in software engineering. In 1984 he won the Turing Award for developing a sequence of innovative computer languages.-Biography:Wirth...

.

Programs that have been translated to p-code are interpreted by a software program that emulates the behavior of the hypothetical CPU. If there is sufficient commercial interest, a hardware implementation of the CPU specification may be built (e.g., the Pascal MicroEngine
Pascal MicroEngine
The Pascal MicroEngine was a series of microcomputer products manufactured by Western Digital from 1979 through the mid 1980s, designed specifically to efficiently run the UCSD p-System...

 or a version of the Java processor
Java processor
A Java processor is the implementation of the Java Virtual Machine in hardware.In other words the bytecodes that make up the instruction set of the abstract machine become the instruction set of a concrete machine.- Implementations :...

).

Why p-code?

Compared to direct translation into native machine code, a two-stage approach involving translation into p-code and execution by an interpreter or just-in-time compiler
Just-in-time compilation
In computing, just-in-time compilation , also known as dynamic translation, is a method to improve the runtime performance of computer programs. Historically, computer programs had two modes of runtime operation, either interpreted or static compilation...

 offers several advantages.
Portability: It is much easier to write a small p-code interpreter for a new machine than it is to modify a compiler to generate native code for the same machine.
Simple implementation: Generating machine code is one of the more complicated parts of writing a compiler. By comparison, generating p-code is much easier. This makes it useful for getting a compiler up and running quickly.
Compact size: Since p-code is based on an ideal virtual machine, a p-code program is often much smaller than the same program translated to machine code.
Debugging: When the p-code is interpreted, the interpreter can apply additional runtime checks that are difficult to implement with native code.

In the early 1980s, at least two operating systems achieved machine independence
Cross-platform
In computing, cross-platform, or multi-platform, is an attribute conferred to computer software or computing methods and concepts that are implemented and inter-operate on multiple computer platforms...

 through
extensive use of p-code. The Business Operating System (BOS) was a cross-platform operating system designed to run p-code programs exclusively. The UCSD p-System, developed at The University of California, San Diego, was a self-compiling and self-hosted
Self-hosting
The term self-hosting was coined to refer to the use of a computer program as part of the toolchain or operating system that produces new versions of that same program—for example, a compiler that can compile its own source code. Self-hosting software is commonplace on personal computers and larger...

operating system based on p-code optimized for generation by the Pascal programming language.

In the 1990s, translation into p-code became a popular strategy for implementations of languages such as Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...

 and Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...

.

Why not p-code?

One of the significant disadvantages of p-code is execution speed, which can sometimes be remedied through the use of a JIT compiler.

Architecture

Like many other p-code machines, the UCSD p-Machine is a stack machine
Stack machine
A stack machine may be* A real or emulated computer that evaluates each sub-expression of a program statement via a pushdown data stack and uses a reverse Polish notation instruction set....

, which means that most instructions take their operands from the stack, and place results back on the stack. Thus, the "add" instruction replaces the two topmost elements of the stack with their sum. A few instructions take an immediate argument. Like Pascal, the 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

Unlike other stack-based environments (such as Forth and the Java Virtual Machine
Java Virtual Machine
A Java virtual machine is a virtual machine capable of executing Java bytecode. It is the code execution component of the Java software platform. Sun Microsystems stated that there are over 4.5 billion JVM-enabled devices.-Overview:...

) the p-System has only one stack shared by procedure stack frames (providing return address
Return address
In postal mail, a return address is an explicit inclusion of the address of the person sending the message. It provides the recipient with a means to determine how to respond to the sender of the message if needed....

, etc.) and the arguments to local instructions. Three of the machine's registers
Processor register
In computer architecture, a processor register is a small amount of storage available as part of a CPU or other digital processor. Such registers are addressed by mechanisms other than main memory and can be accessed more quickly...

 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 n
where 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, p
to 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, j
The 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
retC
with 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 q
These 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
Algorithms + Data Structures = Programs
Algorithms + Data Structures = Programsis a 1976 book written by Niklaus Wirth covering some of the fundamental topics of computer programming, particularly that algorithms and data structures are inherently related...

. The machine had 3 registers - a program counter
Program counter
The program counter , commonly called the instruction pointer in Intel x86 microprocessors, and sometimes called the instruction address register, or just part of the instruction sequencer in some computers, is a processor register that indicates where the computer is in its instruction sequence...

 p, a base register b, and a top-of-stack register
Stack (data structure)
In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...

 t. There were 8 instructions, with one (opr) having multiple forms.

This is the code for the machine, written in Pascal:


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
PL/0
At least two programming languages are known as PL/0. One is a subset of IBM's general-purpose programming language PL/I.The other PL/0, covered here, is similar to but much simpler than the general-purpose programming language Pascal, intended as an educational programming language. It serves as...

, which was a Pascal subset compiler used to teach compiler development.

See also

  • Run-time system
    Run-time system
    A run-time system is a software component designed to support the execution of computer programs written in some computer language...

  • Compiler
    Compiler
    A compiler is a computer program that transforms source code written in a programming language into another computer language...

  • Interpreter
  • Interpreted language
    Interpreted language
    Interpreted language is a programming language in which programs are 'indirectly' executed by an interpreter program. This can be contrasted with a compiled language which is converted into machine code and then 'directly' executed by the host CPU...

  • Joel McCormack
    Joel McCormack
    Joel McCormack is the designer of the NCR Corporation version of the p-code machine which is a kind of Stack machine popular in the 1970s as the preferred way to implement new computing architectures and languages such as Pascal and BCPL...

  • Microsoft P-Code
    Microsoft P-Code
    Microsoft's P-Code, short for packed code, is an intermediate language that provides an alternate binary format to native code for any compiled binary . Its primary goal is to produce smaller files. P-Code binaries require an additional runtime library to execute...

  • Token threaded code
  • UCSD Pascal
    UCSD Pascal
    UCSD Pascal was a Pascal programming language system that ran on the UCSD p-System, a portable, highly machine-independent operating system. UCSD Pascal was first released in 1978...


Further reading

  • Steven Pemberton
    Steven Pemberton
    Steven Pemberton is one of the developers of the ABC programming language and of the Views system.He is chair of the W3C XHTML2 and XForms Working Groups and also member of RDFa Taskforce....

     and Martin Daniels: Pascal Implementation: The P4 Compiler and Interpreter. ISBN 0-85312-358-6; ISBN 0-13-653031-1
  • Steven Pemberton's page on Pascal has Pascal sources of the P4 compiler and interpreter, usage instructions, and the p-code of the compiler (generated by itself).
  • The Jefferson Computer Museum's page on the UCSD p-System
  • Open Source implementation, including packaging and pre-compiled binaries; a friendly fork of the Klebsch implementation
  • Compiling with C# and Java, Pat Terry, 2005, ISBN 0-321-26360-X, 624
  • Algorithms + Data Structures = Programs
    Algorithms + Data Structures = Programs
    Algorithms + Data Structures = Programsis a 1976 book written by Niklaus Wirth covering some of the fundamental topics of computer programming, particularly that algorithms and data structures are inherently related...

    , 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.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK