TU Wien:Abstrakte Maschinen VO (Krall)/Zusammenfassung

Bis jetzt hab ich nur mal eine Übersicht des Stoffes zusammengetragen (bitte ergänzen falls etwas fehlt). Mit Inhalten/Links werde ich es erst füllen wenn ich anfange zu lernen (hab am 06.07.2007 den Test also ca. ab einer Woche vorher). Wer jetzt schon dran arbeiten will der soll!

Abstrakte Maschinen

Reale Architekturen (RISC Vs. CISC)

Grundsätzlich wird zwischen CISC- und RISC-Architekturen unterschieden.

Unterschiede zwischen CISC und RISC

CISC steht für "Complex Instruction Set Computer", RISC für "Reduced Instruction Set Computer". CISC-Architekturen unterstützen kompliziertere Befehle, die höhere Konstrukte aus Programmiersprachen abbilden, während RISC-Architekturen auf "Grundinstruktionen" nach dem load/store-Prinzip ausgelegt sind. Dabei lädt man zuerst mit einem Befehl etwas aus dem Speicher in ein Register, bearbeitet den Wert im Register und schreibt ihn mit einem anderen Befehl zurück. Alle Instruktionen haben eine fixe Länge; man kann maximal einen Speicherzugriff pro Befehl ausführen. In der Regel haben RISC-Architekturen auch mehr Register als CISC, um das load/store-Prinzip besser verwenden zu können.

• CISC: Motorola 68000, Intel x86
• RISC: Alpha, ARM, MIPS, PowerPC

Funktionsaufruf

Bei CISC-Architekturen ist ein Funktionsaufruf meistens aufwändiger, da man die Parameter und die Return-Adresse am Stack lagert, was auch mehrerer Speicherzugriffen entspricht. Bei RISC-Architekturen verwendet man dafür Register, wodurch ein RISC-Funktionsaufruf viel schneller wird.

Optimierungen

Pipelining

Pipelining ermöglicht eine schnellere Ausführung von Befehlen; da man bei der Ausführung einer Instruktion mehrere Teilschritte zu erledigen hat, ist es effizienter gleich mit einem gewissen Teil einer neuen Instruktion zu beginnen, wenn dieser Teil für die alte Instruktion erledigt wurde. Konkret hat man z.B. bei der RISC-Architektur fünf (allgemeine) Schritte:

• Instruction Fetch
• Instruction Decode
• Execute
• Memory Access (Load)
• Register Write Back

Sobald z.B. "Instruction Fetch" für ein Befehl erledigt wurde, kann man schon mit dem nächsten beginnen; so können Instruktionen bis zu fünf mal schneller ausgeführt werden, wenn sie in die Instruction Pipeline gequeued werden.

Superskalar

Superskalare Architekturen verwenden eine Erweiterung von Pipelining, die einen zusätzlichen Dispatch-Schritt zwischen Decode und Execute enthält. Dabei werden mehrere Instruktionen gleichzeitig durch die Fetch und Decode-Schritte geschickt; diese werden vom Dispatcher an mehrere execution units geschickt, welche die Befehle dann parallel abarbeiten.

Abhängigkeiten müssen vorher festgestellt werden, da sonst keine parallele Abarbeitung möglich ist.

Out-Of-Order Execution und Very Long Instruction Word

Wenn Befehle nicht mehr in ihrer ursprünglichen Reihenfolge abgearbeitet werden, spricht man von out-of-order execution (im Gegensatz zu in-order execution). Um bei out-of-order execution die Kosten des Uberprüfens von Abhängigkeiten zwischen Befehlen in der Hardware zu minimieren, kann man diesen Schritt zu compile-time ausführen und der CPU Very Long Instruction Words (VLIW) schicken; so ein VLIW enthält einen Set von parallel abarbeitbaren Instruktionen.

Eine erweiterte superskalare Pipeline funktioniert also folgendermaßen:

• Fetch: Mehrere Instruktionen werden gefetcht, d.h. von einer gegebenen Adresse geholt.
• Decode: Die Instruktionen werden analysiert, um die gebrauchten Ressourcen / die execution unit zu ermitteln.
• Dispatch: Die Instruktionen werden zu den entsprechenden execution units geschickt. Hier kann man von einer reservation station Gebrauch machen; diese erlaubt es, eine Instruktion noch bevor die notwendigen Ressourcen verfügbar sind zu dispatchen und sie erst der execution unit zu schicken, wenn alles vorbereitet ist. Die reservation stations kümmern sich also auch um die Abhängigkeiten der Ressourcen. Aus Einfachheitsgründen wird das Dispatchen in-order gemacht.
• Execute: Die Instruktionen werden out-of-order ausgeführt.
• Completion: Hier werden die fertigen Instruktionen nochmal in-order gebracht.
• Write back: Die Ergebnisse der Instruktionen werden in den Registern zurückgeschrieben. Mittels bypass kann man Completion und Write back in einem Zyklus erledigen.

Precise Interrups und Rename Buffers

Bei out-of-order Ausführung kann es schwierig sein, Interrupts zwischen zwei Befehlen zu setzen (precise interrupts), weil die Reihenfolge der Ausführung nicht unbedingt mit der ursprünglichen übereinstimmen muss. Dies kann man z.B. mit einem reorder buffer erreichen, welches sich die Reihenfolge und den Ausführungszustand der Instruktionen merkt. Um Datenkonsistenz zu bewahren, können die Ergebnisse von Befehlen zuerst out-of-order in sogenannte Rename Buffers gespeichert werden, welche dann im Write-Back-Schritt in-order in die echten Zielregistern kopiert werden; das ist das Prinzip von Register Renaming. Zu berücksichtigen sind die Rename Buffers auch beim Decoden / Dispatchen, da sie eine zusätzliche Ressourcenquelle sind.

Branch Prediction

Da man mit einem Branch die Befehle von einer anderen Stelle fetchen muss, könnte es notwendig sein, das Ergebnis eines Branches abzuwarten um mit dem Fetchen der Instruktionen für die Pipeline fortzufahren. Daher probiert man das Ziel von Branches zu "erraten", man verwendet also branch prediction. Dies kann mithilfe einer branch history table geschehen, welche eine Tabelle mit mehreren Branch-Instruktionen und deren wahrscheinlichen Ausgang (taken / not taken) verwaltet. Dabei wird nach dem Auswerten einer Branch-Instruktion die Tabelle dementsprechend aktualisiert.

Eine Möglichkeit um die Zieladressen von Branches schneller zu bekommen ist eine branch target address cache zu verwenden. Diese enthält bekannte Ziel-Adressen für Branch-Instruktionen, die mit großer Wahrscheinlichkeit genommen (taken) werden. Er wirkt wie ein eigener Return-Stack, der Rücksprungadressen ähnlich dem normalen Stack verwaltet.

2-bit prediction: Da bei Schleifen immer zwei Vorhersagefehler auftreten (beim ersten und letzten Durchlauf), verwendet man 2 Bits um alle vier möglichen Zustände abbilden zu können. Bei 0 und 1 wird nicht gesprungen, bei 2 und 3 schon. Damit kann die Erfolgsquote von 60% auf 80% gesteigert werden. 60% erreicht man, indem man als einfache Heuristik immer die letzte Sprungadresse verwendet.

Caches

Eine letzte Optimierung betrifft den Speicherzugriff allgemein: Sehr kleiner statischer Speicher (quasi in der Taktrate des Prozessors); Speicher kann hierarchisch in mehreren Levels von Cache unterteilt werden, die zunehmend langsamer, aber auch größer (weil billiger) werden. Dabei holt man aus einem höheren Cache-Level (oder aus dem Speicher) die gewünschten Speicherblöcke um sie zu verwenden; da man meistens längere Operationen auf einem ausgewählten Speicherbereich ausführt (Lokalitätsprinzip) ist Cache in der Regel auch sinnvoll.

Ähnlich können Instruktionen in einem read-only Instruction-Cache gespeichert werden, um darauf schneller zugreifen zu können (z.B. bei Schleifen). Diese können auch bereits im Vorhinein dekodiert worden sein (pre-decoded instruction cache) um die Geschwindigkeit noch weiter zu erhöhen.

Threaded Code

• Arten von Threaded Code; welche Vorteile hat welche Art?
• Warum indirekt? Maschinenunabhängig da kein Maschinencode sondern nur Bytecode erzeugt wird
• Was ist besser? AW: Kommt drauf an. Worauf kommts an?

Länge eines jmp, branch prediction, Ladebefehl, ...

CISC: direct threaded ist schneller als subroutine threaded

RISC: subroutine threaded kann schneller sein

Eine gute Erklärung von Threaded Code ist hier zu finden: http://www.complang.tuwien.ac.at/forth/threaded-code.html

Subroutine Threading

Der Objektcode besteht aus Jumps zu nativen Code. Kann auf RISC schneller als andere Codearten sein.

Geschwindigkeit ist von Branch Prediction abhängig, denn die Anzahl der Unterprogrammaufrufe (Return-Adressen auf Stack bei CISC und in Registern bei RISC) bestimmt die Geschwindigkeit.

jsr ... Jump Sub-Routine

Direct Threading

Der Objektcode besteht aus (nativen) Adressen zu nativen Codestücken anstatt aus Jumps und ist somit maschinenabhängig. Ist auf CISC das schnellste.

Indirect Threading

Eine weitere Indirektion in Relation zu Direct Threading. Adressen sind nicht mehr nativ, Code ist plattformunabhängiger und kleiner.

Token Threading

Der Objektcode besteht aus Tokens, die über eine Tabelle zu den nativen Codestücken zugeordnet werden. Plattformunabhängig und am kleinsten. Indizes zu einer Adresstabelle werden gespeichert.
Kann mit Direct Therading/Indirect Threading beliebig kombiniert werden.

Programmiersprache ZIP

Z80 (8-Bit Prozessor) Interpretative Processor

• Indirect Threaded Code
• Ähnlich zu Postscript und Forth
• Integer Arithmetik
• Stackmaschine, die für den Programmierer zu sehen ist
• Dictionary Format
• Systemparameter stehen in Variablen, Ausnahme: IR (Instruction Register)
• Stackbefehle: drop, dup, swap, over

Verwendung:
Startupcode von PC-Einschubkarten, BIOS (z.B. von Apple und Sun)

Pascal P4

Komplette beschreibung: https://web.archive.org/web/20180730222225/https://homepages.cwi.nl/~steven/pascal/book/pascalimplementation.html

• vollständig getypte Stackmaschine (benötigte Datentypen stehen immer im Befehlsnamen)
• static link/dynamic link
• Compiler:
  • recursive descent parser
  • ausprogrammierte lexikalische Analyse
  • single pass
• Typecheck: bei Vergleichen von nicht finiten Datenstrukturen trotzdem finite Ausführungszeit
• Unterschied zwischen Pascal Maschine und JVM
  • beides Stackmaschinen, ähnlich getypt (bis auf Stackumordnung bei Java)
  • P4: AR spezifiziert, Typen ungenau spezifiziert
  • JVM: AR frei, Typen genau auf Bitgröße spezifiziert

Maschinenregister

• PC: Program Counter (Instruction Counter/Pointer)
• SP: Stack Pointer
• MP: Mark Stack Pointer (Frame Pointer, im Stackframe: dynamic link)
• EP: Extreme Pointer, max. an Stack den die aktuelle Funktion brauchen wird
• NP: New Pointer (bis wo hin der Heap verwendet wurde)

Speicherlayout

	Konstanten
NP →	Heap ↓
SP →	↑ Stack

Unterprogrammaufruf

1. Mark Stack (MST): Speichert static link, dynamic link (MP) und EP auf den Stack
2. Call User Procedure (CUP): anpassen von SP für die Parameter, sichern und setzen von PC
3. Enter Block (ENT): anpassen von EP
4. Return (RET): laden von MP, EP und PC

Activation Record (Stackframe)

	...
EP →	local stack
SP →	locals
	parameters
	return address
	old EP
	dynamic link (old MP)
	static link
MP →	function value
	...

Java Virtual Machine

• Stackorientiert
• getypt, aber mit ein paar ungetypten Befehlen (dup etc.)
• Register (32 bit)
  • pc - enthält die Adresse des nächsten bytecodes
  • vars - zeigt auf eine menge von lokalen Variablen
    • variablen sind 32 bit breit
    • long und double verbrauchen zwei variablen, werden aber nur mit der ersten addressiert
  • optop - Operanden Stack
  • frame - execution environment structure
• JIT-Compiler
• Wie funktionieren die wichtigsten Bytecodes?
  • method-call - 4 Möglichkeiten
    • invokevirtual - Dispatch nach Runtime Typ, Standard-Methode
    • invokenonvirtual - Dispatch nach Compiletime Typ, zB wenn "super", oder der Name einer Superklasse als Qualifier verwendet wird
    • invokestatic - für Klassenmethoden
    • invokeinterface - Interfacemethoden
    • vor dem Aufruf muss am Stack eine Referenz zu einem Objekt (außer für static) liegen, danach folgen die Argumente
    • nach dem Byte für die Instruktion folgen zwei Bytes als Index in den Constant Pool für den Methodennamen
  • branching
    • ifeq, ifnull, iflt, ..
    • auf das Byte der Instruktion folgen zwei Bytes, die einen Offset darstellen. Wenn die Bedingung zutrifft, so wird die Ausführung an diesem Offset fortgesetzt.
• Exceptions
  • enstehen bei Linkerfehler, Laufzeitfehlern (zB NullPointerException bei Zugriffen aud nicht initialisierte Objekte), asynchronen Events (zb Thread.stop) und falls throw benutzt wird
  • jede Methode hat eine Liste von Catch-Clauses, jede Clause beschreibt für welche Range von Instruktionen sie gilt, welchen Typ sie fängt und wo der Handlercode steht
  • Handling funktioniert nach den bekannten Regeln. Weil Java strukturiert ist (ie keine überschneidungen in {} Blöcken) können die catch-clauses immer sortiert werden, so dass eine lineare Suche reicht
  • falls keine clause matcht, wird die calling-Funktion wiederhergestellt und die Exception propagiert
• Laufzeit Daten werden am Heap allokiert, der Garbage collected ist. Manuelles allokieren ist nicht möglich, aber man kann den Garbagekollektor wählen.
• Limitierungen
  • pro Klasse max 65535 Einträge im constant pool
  • pro Methode max 65535 Einträge in der exception der line number und der local variable table.
  • max Anzahl an Funktionsargumenten ist 255
• CACAO: wie funktioniert's?
  • stackbasierte operationen müssen in registerbasierte umgewandelt werden
  • naive methode: jeden stack-slot in eigenes register ("temporäre variable") kopieren
  • besser: unnötige kopien vermeiden
  • CACAO-JIT (neu) verwendet 3 Passes
    • basic-blocks bestimmen und schneller decodierbare Repräsentation der VM Instruktionen erstellen
    • Stack analysieren und static stack daraus erstellen, Variablen Abhängigkeiten feststellen und Register Anforderungen berechnen
      • Static-Stack enthält die Typen aller von den Instruktionen verwendeten Werten, sowie ob sie Variablen, Parameter, etc sind
      • daraus lässt sich leicht bestimmen, welche Werte sich auf die gleichen Variablen beziehen - in diesen Fällen kann man load / store weglassen
    • Temporäre Register allokieren und Maschinencode generieren
      • keine teuren Registerallokationsalgorithmen notwendig - javac macht coloring von lokalen Variablen und weißt nicht überlappenden Variablen die selbe Nummer zu.
      • Lebenszeit von Stackvariablen implizit durch push und pop definiert
      • nur dup bereitet Probleme - Duplikate müssen markiert werden!
• Vergleich mit anderen Maschinen

• Pascal Vs. JVM:
  • JVM:
    • Unterprogrammaufruf nicht in der Spezifikation
    • Typen (Hardware unabhängig) auf die Bitgröße genau spezifiziert
  • Pascal:
    • Activation Record ist genau definiert
    • Größe der Typen ist nicht spezifiziert (implementationsabhängig)
• JVM Vs. .NET:
  • wesentlich: .NET hat neben managed Code auch unmanaged und unterstützt auch tail recursion elimination (für Funktionale Programmiersprachen).

Dalvik VM

• Registermaschine (65536 Register)
• nutzt RISC Architektur (mit vielen Registern) besser aus
• Tool "dx" konvertiert .class oder .jar nach .dex
• anderes Instruktionsset als die JVM; Instruktionen sind 2, 4 oder 6 Byte breit
• Register sind 32 Bit breit
• viele Instruktionen bzw. Instruktionsvarianten können nur die ersten 16 Register (als 4 Bits codiert) adressieren, manche die ersten 256 (als 8 Bits codiert)
  • Grund: viele Methoden brauchen nur wenige Register ⇒ kleinere Codierung genügt ⇒ kürzere Instruktionen ⇒ schnellere Abarbeitung
• Argumente werden via Register übergeben
• wenn eine Anwendung auf ein mobiles Gerät übertragen wird, können Instruktionen plattformabhängig verändert und umgeordnet werden ⇒ schnellere Ausführung

Stack VS Register Maschinen

• Stackmaschinen haben Variablen (= Operanden) implizit am Stack, dadurch (für ein bestimmtes Programm) mehr, aber kleinere Instruktionen
• Registermaschinen müssen Variablen (= Register) explizit adressieren, dadurch werden die Instruktionen größer, es sind für das selbe Programm aber weniger Instruktionen notwendig
• Eine stackmaschine braucht einen Instruction Pointer, einen Stack Pointer und einen Frame Pointer, während eine Registermaschine mit IP und FP auskommt. Auf Architekturen mit wenig General Purpose Registern hat so die Register-VM einen Vorteil
• Die Berechnung selbst braucht nur einen kleinen Teil der Rechenzeit, aber Dinge wie Common Subexpression Elimination oder Loop Invariant Elimination sind nur mit einer Register-VM moeglich
• Register-VMs koennen einige Optimierungen durchführen:
  • Copy-Propagation
  • Global Redundant Load Elimination
  • Loop Invariant Motion - loop invariants are moved out of loops
• Im Endeffekt scheint nicht viel Unterschied in der Geschwindigkeit zu bestehen. Registermaschinen sind ein wenig schneller (laut Paper 15% für JVM). Der Geschwindigkeitsunterschied hängt auch stark davon ab, welche Threading Methode verwendet wird - je besser das Threading, desto weniger Unterschied.
• Außerdem braucht eine Register-VM weniger Slots in einem Stackframe, lokale Variablen und Operanden gemeinsam in Registern gespeichert werden (bei einer Stack VM sind sie getrennt).
• Die meisten eliminierten Instruktionen (bei Stack -> Register) sind Moves, gefolgt von Constant Loads.
• Im JVM Beispiel ist der Registercode 26% groesser, obwohl er 44% weniger Instruktionen hat

Common Language Runtime

• Soll viele verschiedene Sprachen unterstützen
• Mehrere Threads gleichzeitig ausgeführt, 1 Thread = Liste von Activation Records. Activation Records normalerweise auf einem Stack, aber nicht notwendigerweise.
• Assembly
  • Menge von Dateien mit Common Intermediate Language Code + Metadata
  • entspricht einem JAR
  • enthält Definitionen von Reference Types (Klassen, Arrays, Interfaces, ..); Value Types (structs, enums); Nested Types
  • auch top-level methoden sind möglich
• Typsystem
  • zusätzlich zu User Defined Types gibt es die üblichen Primitives
  • außerdem getypte Reference
  • managed und unmanaged Pointer
  • unmanaged sind wie C Pointer, können nicht in managed Heap zeigen
  • im Gegensatz zu JVM können Typen unterschiedliche Größen haben (nicht wie bei JVM zwei Locations für long und double)
• Instruktionen enthalten weniger Typinformationen, meist nur fürs Ergebnis
• enthält Tailcall-Optimization durch eigenes Präfix "tail." vor einem Aufruf

Baummaschinen und Syntax gesteuerte Editoren

(sehr unvollständig)

• rekursiv oder Zeiger auf Vaterknoten

Baummaschinen

• es wird direkt der Baum (AST) interpretiert
• Baum auch mit gotos darstellbar
• Beispiele:
  • Mentor
  • Gandalf (ALOE)
  • Cornell Program Synthesizer (COPS)
  • Program System Generator (PSG)

PDF

Mentor, Cornel Program Synthisizer (mit gotos)

Program System Generator (PSG)

• erstellt aus einer formalen Sprachdefiniton (in LL(1) Grammatik) einen Editor, Interpreter und eine Standardbibliothek
• Editor erlaubt Bearbeitung in "Textmodus" und "Strukturmodus", verhindert syntaktische und semantische Fehler
• Programm wird intern als AST dargestellt
• im Strukturmodus werden Programme menügesteuert erstellt
• sprache wird in 3 Teilen definiert
  • Syntax - zuerst wird lexixalische Struktur definiert, aus der ein Scanner generiert wird. Dann folgt die abstrakte Syntax als Kern jeder Sprachdefinition. (wie sind Statements aufgebaut, etc). Anschließend folgt die konkrete Syntax (als LL(1) Grammatik) zur Erstellung eines Parsers.
  • Context conditions - für jedes unvollständige Fragment wird eine Menge von noch möglichen Attributen berechnet. (= context relation) Ist die Menge leer, liegt ein Fehler vor, enthält sie genau ein Element, dann ist die Kontextinformation eindeutig. Die Spezifikation erfolgt in 4 Schritten: Sichtbarkeitsregeln, Spezifikation der Daten-Attribut Grammatik (ie ordinal = integer, boolean, ..), Attribut-Format Definition (wie sollen Attribute angezeigt werden), und schlussendlich die basic-relations: wie Typen und Attribute übereinstimmen müssen (zb assignment von variablen nur mit gleichem typ)
  • Semantics - in Type-Free Lambda Calculus definiert als Zwischensprache. Interpretation = Reduktion auf Normalform
• Vorteile
  • Sprachdefinitionen relativ kurz (200 - 4000 zeilen)
  • Sprachdesigner kann sich auf die Sprache konzentrieren und nicht auf Implementierungsdetails
  • Sprachinkonsistenzen werden zur Compile-Zeit entdeckt
  • Sprachen können leicht verändert und getestet werden
• Nachteile
  • Sprachsyntax muss LL(1) kompatibel sein
  • kein Überladen von Funktionen
  • langsam

Syntax gesteuerte Editoren

• Was sind Syntax gesteuerte Editoren?

Prolog

Elemente werden durch Struktur mit Value und Tag für den Typ repräsentiert (weil dynamische Sprache). Variablen beinhalten eine Referenz, freie Variablen zeigen dabei auf sich selbst (nützlich für erste Zuweisung).

• Aufbau des Speichers:
  • Code Area, für intermediate code of clauses
  • Environment Stack (≈ Stack), für stack frames und choice points
  • Trail: Bei der Unifikation werden i.A. ungebundene Variablen gebunden. Schlägt der Ast fehl, müssen diese wieder zurückgesetzt werden. Der Trail Stack merkt sich diese Variablen, um sie beim Backtracking poppen und zurücksetzen zu können.
  • Copy Stack (≈ Heap), für structures und unbound variables
• Und- (Aufrufe) & Oder- (durch backtracking) Baum
• stack frame
  • variables
  • caller & stack frame of caller (auch continuation genannt)
• choice point
  • wird verwendet, falls mehrere alternativen zur unification bestehen
  • stackframe, das zusätzlich einen zeiger auf die nächste alternative, auf die Spitze des trails, auf den vorigen Choice Point und auf die Spitze des copy stacks enthält
  • falls unification fehlschlägt, werden zeiger wiederhergestellt und nächste alternative versucht
• structures
  • structure sharing: annahme großteil der Struktur ist constant, daher in 2 Teile geteilt. konstanter teil "skeleton", in der code area aufbewahrt und variabler teil "environment" am global stack. daher zwei pointer pro structure notwendig - auf modernen maschinen langsam
  • structure copying: ?
• vorwärts rekursiv
• last call optimierung
  • bei WAM: variablen des callers werden in Register kopiert, dann wird das neue Stackframe am Platz des alten erstellt
  • bei VAM: zuerst wird das neue Stack frame erstellt (nicht über dem alten); caller und callee werden unified. Dann, wenn der Aufruf deterministisch ist (keine Alternativen, dh keine choice points) wird das stack frame des callee über das des callers kopiert
• tail rekursion elemination! (⇒ Rekursionen werden quasi zu Schleifen)
• clause indexing
  • Optimierung - weniger Clauses müssen probiert werden
  • First Argument indexing: nur clauses die mit dem goal in ersten Argument unifien werden ausgewählt.
  • WAM speichert die indexing information in Instruktionen, VAM in speziellen Datenstrukturen (balanced binary tree)
• Argumentregister
• Garbage Collector ist notwendig
• Variablenklassifikationen:
  • Normal
  • Temporär: Variablen, die nur in einer Subgoal vorkommen, muss man nicht am Stack Frame speichern (der für alle Goals gültig ist). Sie werden in bestimmten fixen Bereichen platziert.
  • Void (weg-optimiert): Variablen, die nur einmal in einer Klausel vorkommen, kann man immer einfach zuweisen, brauchen also nicht repräsentiert werden.
• Warren's Abstract Machine (ähl. RISC)
  • Unifikation in 2 Teile: Argumente über Register übergeben (falls genügend Register vorhanden, sonst Stack), dann Argumentregister mit dem Kopf des aufgerufenen Goals unifizieren. Dadurch braucht man nur mehr einen Instruktion Pointer, wenn man keine Argumente über den Stack übergeben muss. Das vereinfacht auch Last-call Optimierungen und temporäre Variablen (siehe Seite 6 des Papers rechts unten).
  • welche Pointer gibts, etc.?
• Vienna Abstract Machine (vam_afterfinal.pdf von Andreas Krall und Ulrich Neumerkel)
  • unification in einem Schritt
  • V2P
    • als intermediate Code Interpreter in C oder Assembly geeignet
    • 2 Instruktionpointer: Goal Instruktion Pointer zeigt auf die Instruktionen des aufrufenden Goals, der Head Instruktion Pointer auf die Instruktionen des Heads der aufgerufenen clause
    • durch zwei Pointer mehr Optimierungen möglich
  • V1P
    • für Compilieren geeignet
    • zusätzliche Optimierungen: instruction elimination, extended clause indexing, fast last-call optimization, loop optimization
• Abstrakte Interpretation
  • globale Data Flow Analysis
  • Programm wird über abstrakter Domäne ausgeführt
  • Rekursion wird durch Bestimmung von Fixpunkten aufgelöst
  • vollständigkeit durch wiederholte Interpretation bis sich nichts mehr ändert
• VAM_AI
  • basiert auf V2P
  • Data Flow Information direkt im intermediate Code gespeichert
  • in der V1P verwendet
  • verschiedne Aufrufe der selben clause werden separat behandelt, um exaktere Typ-Informationen zu bekommen (clause wird dupliziert, anschließend Union der Typen)

SECD

• speicher besteht aus getaggten Zellen für s-expressions, entweder Integer oder cons cell
• programme werden als listen gespeichert. braucht mehr speicher, dafür keine neue datenstruktur notwendig und code = data
• Beschreibe S, E, C und D - die Register für die 4 Hauptdatenstrukturen
  • S = evaluation stack, für builtins (+, -, car, cons, etc). Gepoppte Werte werden nie überschrieben, die aktuelle zeigt dann einfach auf die Zelle vor dem gepoppten Wert.
  • E = environment, für Argumentwerte. Genauso persistent wie der Stack.
  • C = control list, entspricht program counter in einem normalen Computer. Zeigt auf car der aktuellen Instruktion.
  • D = dump, zum speichern des Funktions-states wenn ein neuer Aufruf beginnt - es werden die Werte von S, E und C gespeichert.
  • zusätzlich F, zeigt auf die nächste freie Speicherzelle
• Dump: entspricht Return Address Stack bei ZIP; bei If-Then-Else verwendet um danach weiter zu machen
• if-then-else
  • special form
  • instruktionen: ... condition SEL (true part JOIN) (false part JOIN) ...
  • SEL speichert einen zeiger auf die instruktion nach der zweiten subliste (also nach dem false zeug) auf den dump, poppt das oberste Element vom S stack (das ja von der condition draufgelegt wurde) und entscheidet aufgrund dieses Wertes welche subliste ausgeführt wird. anschließend ersetzt es C mit dem entsprechenden Listenkopf
  • JOIN poppt den dump und setzt C auf den vorher gespeicherten Wert zurück
• nicht-rekursive funktionen
  • LDF (load function) gefolgt von einer subliste die den programmcode enthält, der von RTN abgeschlossen wird
  • wenn LDF ausgeführt wird, baut es in einer neuen Listenzelle ein Closure aus einem Zeiger auf den Funktionscode und dem aktuellen E register. Dann wird die closure auf den S stack gepusht.
  • die funktion wird nicht sofort ausgeführt! erst eine AP (apply) instruktion holt die closure vom stack. (darunter liegt eine liste mit argumentwerten)
  • wenn AP ausgeführt wird, werden S, E und C auf den dump gepusht
  • anschließend wird S auf nil gesetzt (leere Stack für aufruf), C auf den beginn des funktionscodes und E auf den cons von cdr der closure (war E zur zeit, als die closure erstellt wurde) und den alten S stack
  • RTN nimmt den obersten Wert von S als rückgabewert, dann werden die S, E, C werte vom dump wiederhergestellt
  • einziger unterschied zu vor dem aufruf: das oberste elemente von S ist jetzt der rückgabewert
• rekursive funktionen
  • es wird eine DUM instruktion ganz vorne an die enviromnent angehängt, welche später durch einen rekursiven zeiger ersetzt wird
  • statt AP wird jetzt RAP (recursive apply) verwendet
  • sonst sieht alles wie bei normalen funktionen aus
  • die ausführung von RAP ist wie AP, außer das DUM durch einen zeiger auf die liste von closures ersetzt wird. dadurch entsteht die gewünschte schleife
• das funarg problem
  • wenn die definiton einer nested function auf variablen von ihren eltern zugreift, die bei der ausführung nicht mehr vorhanden sind
  • lösung: closures
  • funktioniert, weil stacks nie überschrieben oder gelöscht werden

Lambda-Kalkül

• • $\alpha$-Konversion: "renaming"
  • $\beta$-Konversion: funktionsanwendung
  • $\eta$-Konversion: λ x . f x == f
• church-rosser theorem I: wenn A durch verschiedene Reduktionen auf B und C reduziert werden kann, so gibt es immer ein D, auf das sowohl B und C reduziert werden können.
• => durch reduktionen können keine nicht-äquivalente ausdrücke entstehen
• church-rosser theorem II: wenn A nach B reduziert, und B in normal order ist (keine $\beta$ oder $\eta$ Konv möglich), dann gelangen wir von A nach B indem wir immer die linkeste Reduktion ausführen.
• Evaluationsreihenfolgen (normal, applicative)
  • normal order - zuerst werden Funktionen angewendet (immer die linkesten), dann erst werden die Parameter reduziert,
  • applicative order - parameter werden reduziert, bevor Funktionen angewendet werden. Manchmal effizienter (parameter werden nicht mehrfach evaluiert), kann aber zu Endlosschleifen führen
• currying
  • funktion die mehrere parameter verlangt, wird durch kette von funktionen ersetzt, die je ein argument brauchen

Infos zur Prüfung

Die Prolog-Maschinen (Warren Abstract Machine und Vienna Abstract Machine) würde ich mir gut ansehen. Bei diesen wurde viel nachgefragt.

Prüfung 13.12.2010

Schriftliche Angabe

Entwirf einen Interpreter und einen Compiler in Pseudocode für folgende Sprache: (Zeit: 1,5h)

Func => FUNC Ident ( Idents ) Expr END
Expr =>
| Expr + Expr // Addition
| Expr = Expr // Vergleich
| Ident // Argumentabfrage
| Ident ( Exprs) // Funktionsaufruf
| IF Expr THEN Expr [ELSE Expr] END // Verzweigung (Else ist optional, 0 = false, alles andere true)

Ein Programm besteht aus einer beliebigen Menge von Funktionen (zumindest eine). Die erste Funktion darf keine Parameter haben und dient als Startpunkt. Es sind nur Ganzzahlen erlaubt, eine solche ist auch das Ergebnis der Berechnung. Idents und Exprs geben eine Auflistung von Identifiern und Expressions an, sie waren nicht näher definiert, wie auch Ident.

Ausarbeitung

quick&dirty implementierung in C: https://web.archive.org/web/20180730222239/https://gist.github.com/lewurm/1015002 --Lewurm 11:38, 24. Jan. 2012 (CET)

Mündliche Prüfung

dauerte ca. 30min, mit Smalltalk

• Was ist Threaded Code? Warum gibt es indirect threaded code? Was ist wo schneller (CISC bzw. RISC)?
• Was ist die Pascal P4 Maschine (Stackmaschine, 5 Register, ...)? Unterschiede zur Java VM?
• Was sind die Unterschiede zwischen WAM und VAM? Was sind void Variablen? Was sind temporäre Variablen und was ist ihr Vorteil bzgl. lokalen Variablen? Unterschied structure copying, structure sharing; warum ist structure copying schneller? Einzelheiten der VAM: Wozu Clause Indexing? Was ist VAM1P, VAM2P, VAMAI?
• Unterschiede Stackmaschinen, Registermaschinen; Vor- und Nachteile davon.

Die Prüfung war im Großen und Ganzen sehr angenehm. Zur schriftlichen Prüfung dürfen alle Unterlagen verwendet werden, bei der mündlichen keine. Zur Definition des Interpreters: Man sollte seine Zeit nicht mit Kleinigkeiten verschwenden, stattdessen einen kurzen Kommentar machen, das reicht. Wichtig ist, dass alles da ist, was einen Interpreter ausmacht. Falls man bei der mündlichen Prüfung etwas nicht sofort weiß, fragt Prof. Krall auch noch zusätzlich nach und gibt Tipps. PS: Im Skriptum ist echt viel Zeug drin, man muss ein wenig zwischen den Zeilen das Wesentliche herauslesen (ich nahm diese Zusammenfassung als Ausgangspunkt).
3 Tage wirklich intensiv gelernt, Note: sehr gut

Prüfung SS 11 (unvollständig)

• RISC/CISC, Piplining, Superskalare Architekturen, Out-Of-Order Execution, Reservation Station, Rename Buffer, Branch Prediction
• Threaded Code
• Pascal (w.o.)
• Registermaschinen: Vorteile, schneller bei Interpretation, bei Kompilierung ist es egal; dex-Format
• SECD: Stacks, wie funktioniert die Ausführung (insb. Funktionsaufrufe und if)
• Unterschiede WAM VAM (eher oberflächlich, es war aber auch nur mehr wenig Zeit)

Prüfung SS 12 (19. 06. 2012)

• RISC/CISC, Piplining, Superskalare Architekturen, Out-Of-Order Execution, Reservation Station, Rename Buffer, Branch Prediction
• Java-JIT
• WAM vs VAM

wer alles kann, was hier auf der Seite steht, sollte kein Problem haben ein sehr gut zu bekommen

Pruefung SS11 (17.02.2012)

• Computer Architekturen
• Threaded Code
• Pascal P4
• JavaVM
• Baummaschinen
• Registermaschinen, DalvikVM
• WAM
• VAM
• SECD