P-Code-Maschine - p-code machine

In der Computerprogrammierung ist eine P-Code-Maschine ( tragbare Code-Maschine ) eine virtuelle Maschine, die entworfen ist, um P-Code (die Assemblersprache oder der Maschinencode einer hypothetischen Zentraleinheit (CPU)) auszuführen . Dieser Begriff wird sowohl generisch auf all diese Maschinen (wie die Java Virtual Machine (JVM) und vorkompilierten MATLAB- Code) als auch auf spezifische Implementierungen angewendet , von denen die bekannteste die p-Maschine des Pascal-P- Systems ist, insbesondere die UCSD Pascal Implementierung, unter deren Entwickler, die p in p-Code wurde auf mittlere ausgelegt Pseudo als häufiger tragbare , so pseudo-Code Anweisungen für einen pseudo-Maschine bedeutet.

Obwohl das Konzept erstmals um 1966 implementiert wurde (als O-Code für die Basic Combined Programming Language ( BCPL ) und P-Code für die Sprache Euler ), tauchte der Begriff P-Code erstmals in den frühen 1970er Jahren auf. Zwei frühe Compiler, die p-Code erzeugten, waren der Pascal-P-Compiler 1973 von Kesav V. Nori, Urs Ammann, Kathleen Jensen, Hans-Heinrich Nägeli und Christian Jacobi und der Pascal-S- Compiler 1975 von Niklaus Wirth .

Programme, die p-Code übersetzt wurden entweder werden interpretiert durch ein Software - Programm, das das Verhalten der hypothetischen CPU emuliert, oder übersetzt in den Maschinencode der CPU , auf dem das Programm laufen soll und dann ausgeführt. Wenn ein ausreichendes kommerzielles Interesse besteht, kann eine Hardwareimplementierung der CPU-Spezifikation erstellt werden (zB die Pascal MicroEngine oder eine Version eines Java-Prozessors ).

Vorteile und Schwächen der Implementierung von P-Code

Im Vergleich zur direkten Übersetzung in nativen Maschinencode bietet ein zweistufiger Ansatz mit Übersetzung in P-Code und Ausführung durch Interpretieren oder Just-in-Time-Kompilierung (JIT) mehrere Vorteile.

  • Es ist viel einfacher, einen kleinen P-Code-Interpreter für eine neue Maschine zu schreiben, als einen Compiler zu modifizieren, um nativen Code für dieselbe Maschine zu generieren.
  • Das Generieren von Maschinencode ist einer der komplizierteren Teile beim Schreiben eines Compilers. Im Vergleich dazu ist die Generierung von p-Code viel einfacher, da bei der Generierung des Bytecodes kein maschinenabhängiges Verhalten berücksichtigt werden muss . Dies macht es nützlich, um einen Compiler schnell zum Laufen zu bringen.
  • Da p-Code auf einer idealen virtuellen Maschine basiert, ist ein p-Code-Programm oft viel kleiner als das gleiche Programm, das in Maschinencode übersetzt wird.
  • Wenn der p-Code interpretiert wird, kann der Interpreter zusätzliche Laufzeitprüfungen anwenden , die mit nativem Code schwer zu implementieren sind.

Einer der wesentlichen Nachteile von P-Code ist die Ausführungsgeschwindigkeit, die manchmal durch JIT-Kompilierung behoben werden kann. P-Code ist oft auch einfacher zu rekonstruieren als nativer Code.

In den frühen 1980er Jahren, mindestens zwei Betriebssysteme erreicht Maschinenunabhängigkeit durch den umfassenden Einsatz von p-Code. Das Business Operating System (BOS) war ein plattformübergreifendes Betriebssystem, das ausschließlich für die Ausführung von P-Code-Programmen entwickelt wurde. Das UCSD p-System , das an der University of California, San Diego, entwickelt wurde, war ein selbstkompilierendes und selbsthostendes Betriebssystem auf der Grundlage von p-Code, der für die Generierung durch die Pascal- Sprache optimiert wurde .

In den 1990er Jahren wurde die Übersetzung in P-Code zu einer beliebten Strategie für Implementierungen von Sprachen wie Python , Microsoft P-Code in Visual Basic und Java-Bytecode in Java .

Die Sprache Go verwendet eine generische, portable Assembly als eine Form von P-Code, die von Ken Thompson als Erweiterung der Arbeit an Plan 9 von Bell Labs implementiert wurde . Im Gegensatz zu Common Language Runtime (CLR)-Bytecode oder JVM-Bytecode gibt es keine stabile Spezifikation, und die Go-Build-Tools geben kein Bytecode-Format aus, das zu einem späteren Zeitpunkt verwendet werden soll. Der Go-Assembler verwendet die generische Assemblersprache als Zwischendarstellung , und ausführbare Go-Dateien sind maschinenspezifische statisch verknüpfte Binärdateien.

UCSD p-Maschine

Die Architektur

Wie viele andere p-Code-Maschinen ist die UCSD p-Machine eine Stack-Maschine , was bedeutet, dass die meisten Befehle ihre Operanden von einem Stack nehmen und die Ergebnisse wieder auf dem Stack ablegen . Somit addersetzt der Befehl die beiden obersten Elemente des Stapels durch ihre Summe. Ein paar Anweisungen erfordern ein sofortiges Argument. Wie Pascal ist der p-Code stark typisiert und unterstützt nativ die Datentypen Boolean (b), Zeichen (c), Integer (i), Real (r), Menge (s) und Zeiger (a) .

Einige einfache Anweisungen: 

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

Umfeld

Im Gegensatz zu anderen Stack-basierten Umgebungen (wie Forth und der Java Virtual Machine ), aber sehr ähnlich zu einer echten Ziel-CPU, hat das p-System nur einen Stack, der von Prozedur-Stack-Frames (mit Rückgabeadresse usw.) und den Argumenten geteilt wird lokale Anweisungen. Drei der Register der Maschine zeigen in den Stack (der nach oben wächst):

  • SP zeigt auf die Spitze des Stapels (der Stapelzeiger ).
  • MP markiert den Anfang des aktiven Stapelrahmens (den Markierungszeiger ).
  • EP zeigt auf den höchsten Stapelspeicherort, der in der aktuellen Prozedur verwendet wird (der Extremzeiger ).

Ebenfalls vorhanden ist eine konstante Fläche und darunter der zum Stapel hin nach unten wachsende Haufen . Das Register NP (der neue Zeiger ) zeigt auf die Spitze (niedrigste verwendete Adresse) des Heaps. Wenn EP größer als NP wird, ist der Speicher der Maschine erschöpft.

Das fünfte Register PC zeigt auf den aktuellen Befehl im Codebereich.

Aufrufkonventionen

Stapelrahmen sehen so aus: 

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

Die Prozeduraufrufsequenz funktioniert wie folgt: Der Aufruf wird eingeleitet mit 

 mst n

wo ngibt den Unterschied in den Verschachtelungsebenen an (denken Sie daran, dass Pascal verschachtelte Prozeduren unterstützt). Dieser Befehl markiert den Stapel, dh reserviert die ersten fünf Zellen des obigen Stapelrahmens und initialisiert den vorherigen EP, dynamischen und statischen Link. Der Aufrufer berechnet und überträgt dann alle Parameter für die Prozedur und gibt dann aus 

 cup n, p

um eine Benutzerprozedur aufzurufen ( nist die Anzahl der Parameter, pdie Adresse der Prozedur). Dadurch wird der PC in der Zelle für die Rücksendeadresse gespeichert und die Adresse der Prozedur als neuer PC festgelegt.

Benutzerverfahren beginnen mit den beiden Anweisungen 

 ent 1, i
 ent 2, j

Der erste setzt SP auf MP + i, der zweite setzt EP auf SP + j. Gibt also im iWesentlichen den für Locals reservierten Speicherplatz an (plus die Anzahl der Parameter plus 5) und jgibt die Anzahl der Einträge an, die lokal für den Stack benötigt werden. An dieser Stelle wird die Speichererschöpfung überprüft.

Die Rückkehr zum Anrufer erfolgt über 

 retC

mit CAngabe des Rückgabetyps (i, r, c, b, a wie oben und p für keinen Rückgabewert). Der Rückgabewert muss zuvor in der entsprechenden Zelle gespeichert werden. Bei allen Typen außer p wird dieser Wert bei der Rückgabe auf dem Stack bleiben.

Anstatt eine Benutzerprozedur (cup) aufzurufen, qkann die Standardprozedur mit aufgerufen werden 

 csp q

Diese Standardprozeduren sind Pascal-Prozeduren wie readln()( csp rln), sin()( csp sin), etc. Eigentümlicherweise eof()ist stattdessen eine p-Code-Anweisung.

Beispielmaschine

Niklaus Wirth spezifizierte 1976 in seinem Buch Algorithms + Data Structures = Programs eine einfache P-Code-Maschine . Die Maschine hatte 3 Register - einen Programmzähler p , ein Basisregister b und ein oberstes Register t . Es gab 8 Anweisungen:

  1. leuchtet 0, a  : Lastkonstante a
  2. opr 0, a  : Operation a ausführen (13 Operationen: RETURN, 5 mathematische Funktionen und 7 Vergleichsfunktionen)
  3. lod l , a  : Lastvariable l,a
  4. sto l , a  : Speichervariable l, a
  5. cal l , a  : Anrufverfahren eines auf der Ebene l
  6. int 0, a  : t-Register um a . erhöhen
  7. JMP 0, ein  : Sprung auf ein
  8. jpc 0, a  : Sprung bedingt zu a

Dies ist der Code für die Maschine, geschrieben in Pascal: 

const
	amax=2047;      {maximum address}
	levmax=3;       {maximum depth of block nesting}
	cxmax=200;      {size of code array}

type 
	fct=(lit,opr,lod,sto,cal,int,jmp,jpc);
	instruction=packed record 
		f:fct;
		l:0..levmax;
		a:0..amax;
	end;

var
	code: array [0..cxmax] of instruction;

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};

Diese Maschine wurde verwendet, um Wirths PL/0 auszuführen , einen Pascal-Subset-Compiler, der verwendet wird, um die Compiler-Entwicklung zu lehren.

Siehe auch

Verweise

Weiterlesen