Effiziente Virtuelle Maschinen für funktionale Programmiersprachen

EffizienteVirtuelle Maschinenfür funktionale ProgrammiersprachenXavier Leroy, The ZINC experiment:an economical implementation of the ML language. Technical report 117, INRIA, 1990

Überblick

Motivation Eigenschaften funktionaler

Sprahen N-ary / Unary / curried

functions Die abstrakte Maschine Naive Auswertung Analyse der Auswertung Echte Mehrfachapplikation

Probleme Analyse der Auswertung

Darstellung von Funktionen

Das Instruction Set Die Übersetzungsfunktion Operationale Semantik Unterversorgung Überversorgung Optimierungen Darstellung von Werten Das reale Instruction Set Benchmarks

Motivation

Wie können Programme in funktionalen Sprachen effizient und plattformunabhängig ausgeführt werden ?

native Code Compiler hohe Ausführungsgeschwindigkeit Programmdarstellung ist plattformabhängig Compiler müssen für jede Ziel-Plattform neu entwickelt werden

Virtuelle Maschine VM selbst ist plattformabhängig, aber leicht portierbar Bytecode ist plattformunabhängig Overhead der VM kann minimiert werden

Eigenschaften funktionaler Sprachen

Abstraktion Curried functions: val f = fn a => fn b => a+b Unary functions: val f = fn (a,b) => a+b N-ary functions ?

Applikation mit Unterversorgung von Argumenten mit Überversorgung von Argumenten

Schleifen werde durch rekursive Funktionen dargestellt.

N-ary functions

n-ary functions sind Funktionen mit mehr als einem Argument.Bei der Ausführung werden diese zurückübersetzt in einfachere Funktionen. Es gibt dazu zwei Möglichkeiten fun f (a b) = a+b

als unary functions mit Argumenten-Tupelfun f (a,b) = a+b

oder als curried functions val f = fn a => fn b => a+b

Vergleich von Unary / curried functions

Nachteil bei Argumenten-Tupel: Allokation des Argumenten-Tupel auf dem Heap bei jedem Aufruf

Vorteil von curried functions: Curried functions sind bei partieller Anwendung verwendbar: val add = fn a => fn b => a+b map (add 5) [1,2,3]

Partielle Applikation ist bei Argumenten-Tupel nicht möglich.=> Curried functions sollten effizient implementiert werden!=> N-ary functions als curried functions übersetzbar.

Überblick

Motivation Eigenschaften funktionaler

Sprahen N-ary / Unary / curried

functions Die abstrakte Maschine Naive Auswertung Analyse der Auswertung Echte Mehrfachapplikation

Probleme Analyse der Auswertung

Darstellung von Funktionen

Das Instruction Set Die Übersetzungsfunktion Operationale Semantik Unterversorgung Überversorgung Optimierungen Darstellung von Werten Das reale Instruction Set Benchmarks

Die abstrakte Maschine

Die abstrakte Maschine besteht aus folgenden Komponenten: Der Akkumulator enthält Zwischenergebnisse Der Code-Zeiger zeigt auf die nächste auszuführende Instruktion. Die Umgebung verwaltet alle aktuellen Bezeichnerbindungen. Auf dem Stack werden Aufrufparameter, Ergebnis-Werte und

Closures von unterbrochenen Auswertungen abgelegt.

Die Semantik der Maschine wird bestimmt durch: Das Instruction Set der Maschine. Die Operationale Semantik bestimmt wie diese Instruktionen in

Abhängigkeit vom aktuellen Inhalt von Umgebung und Stack ausgewertet werden.

Naive Auswertung

Bei der naiven Auswertung wird jeweils ein Parameter angewandt.

M N1 N2 ==> (M N1) N2

Über- und Unterversorgung betrachten wir später!

Auswertungsbeispiel

(fn a => fn b => a + x) 3 x

Um die erste Applikation auszuführen, wird der Folgeausdruck als Closure auf den Stack gelegt.

StackUmgebung

x: 7

Akkumulator

Auswertungsbeispiel

(fn a => fn b => a + x) 3

Der Parameter wird in den Akkumulator geladen.

Stack

Closure A

Umgebung

x: 7

Closure A

Code

X

Umgebung

x: 7

Akkumulator

Auswertungsbeispiel

(fn a => fn b => a + x)

… und auf den Stack gelegt.

Stack

Closure A

Umgebung

x: 7

Closure A

Code

X

Umgebung

x: 7

Akkumulator

3

Auswertungsbeispiel

fn a => fn b => a + x

Die Abstraktion wird ausgeführt, indem das Argument von Stack genommen wird und als „a“ in die Umgebung eingefügt.

Stack

3

Closure A

Umgebung

x: 7

Closure A

Code

X

Umgebung

x: 7

Akkumulator

Auswertungsbeispiel

fn b => a + x

Bei einer weiteren Abstraktion ist die Auswertung zunächst abgebrochen. Das Zwischenergebnis wird in einer Closure in den Akkumulator gepackt.

Stack

Closure A

Umgebung

x: 7

a: 3

Closure A

Code

X

Umgebung

x: 7

Akkumulator

Auswertungsbeispiel

Die neue Closure ersetzt die unterbrochene Auswertung auf dem Stack.Diese wird fortgesetzt.

Stack

Closure A

Closure A

Code

X

Umgebung

x: 7

Closure B

Code

fn b => a + x

Umgebung

x: 7

a: 3

Akkumulator

Closure B

Auswertungsbeispiel

x

Das nächste Argument wird in den Akkumulator geladen.

Stack

Closure B

Umgebung

x: 7

Closure B

Code

fn b => a + x

Umgebung

x: 7

a: 3

Akkumulator

Auswertungsbeispiel

… und auf den Stack gelegt. Die unterbrochene Auswertung wird fortgesetzt.

Stack

Closure B

Umgebung

x: 7

Closure B

Code

fn b => a + x

Umgebung

x: 7

a: 3

Akkumulator

7

Auswertungsbeispiel

fn b => a + x

Die Abstraktion wird ausgeführt, indem das Argument von Stack genommen wird und als „b“ in die Umgebung eingefügt.

Stack

7

Umgebung

x: 7

a: 3

Akkumulator

Auswertungsbeispiel

a + x

„a“ wird aus der Umgebung in den Akkumulator geladen.

StackUmgebung

x: 7

a: 3

b: 7

Akkumulator

Auswertungsbeispiel

+ x

… und auf den Stack gelegt.

StackUmgebung

x: 7

a: 3

b: 7

Akkumulator

3

Auswertungsbeispiel

+ x

„x“ wird aus der Umgebung in den Akkumulator geladen.

Stack

3

Umgebung

x: 7

a: 3

b: 7

Akkumulator

Auswertungsbeispiel

+

Der oberste Wert auf dem Stack wird zum Akkumulator addiert.

Stack

3

Umgebung

x: 7

a: 3

b: 7

Akkumulator

7

Auswertungsbeispiel

Der Wert im Akkumulator ist das Ergebnis.

StackUmgebung

x: 7

a: 3

b: 7

Akkumulator

10

Analyse der Auswertung

Die Auswertung von Mehrfach-Applikationen erfolgt schrittweise:

Bei Left-To-Right Evaluation: ((((M) (N1)) (N2)) (N3))

Reihenfole: M, N1, (M N1)=a, N2, (a N2)=b, N3, (b N3)

Bei der Auswertung jeder Applikation [außer der letzten] entsteht eine Closure für das bisher erzeugte Zwischenergebnis.n-Argumente => n-1 Closures.

Probleme dieser Auswertung

Es werden für k Argumente mindestens k - 1 Closures verwendet.

Closures werden auf dem Heap angelegt. Allokationen sind zeitintensiv Die Closures werden [teilweise] nur einmal verwendet. Der Speicherbedarf steigt. Die Garbage Collection wird häufiger verwendet.

Wie kann man diese Closures meiden ?

Überblick

Motivation Eigenschaften funktionaler

Sprahen N-ary / Unary / curried

functions Die abstrakte Maschine Naive Auswertung Analyse der Auswertung Echte Mehrfachapplikation

Probleme Analyse der Auswertung

Darstellung von Funktionen

Das Instruction Set Die Übersetzungsfunktion Operationale Semantik Unterversorgung Überversorgung Optimierungen Darstellung von Werten Das reale Instruction Set Benchmarks

„Echte“ Mehrfachapplikation - Vorteile

Alle Argumente könnten vor der Applikation auf den Stack gelegt werden. Die Auswertung muss nicht nach jeder Teilapplikation unterbrochen werden.

Die Reihenfolge bei 3-fach-Applikation M N1 N2 N3 ist: bei Einzelapplikationen: M, N1, (M N1)=a, N2, (a N2)=b, N3, (b

N3)

bei Mehrfachapplikation: M, N1, N2, N3, (M N1 N2 N3)

Die Applikation aller Argumente erzeugt keine unnötigen Closures.

Probleme der Mehrfachapplikation

Mehrere Einzelapplikationen sollten die gleiche Auswertungsreihenfolge haben wie eine Mehrfachapplikation.[Gilt nicht für „Zwischenergebnisse“ !]

Problem: Left-To-Right Evaluation Order M N1 N2 => M, N1, N2, (M N1 N2) (M N1) N2 => [M, N1, (M N1)=a], N2, (a N2)

Lösung: Right-To-Left Evaluation Order M N1 N2 => N2, N1, (M N1 N2) (M N1) N2 => N2, [N1, (M N1)=a], (a N2)

Beispiel für Inkonsistenz

exception Abs exception Right val f = fn x => (raise Abs; fn y => y)

Problem: Left-To-Right Evaluation Order f 1 (raise Right) => raise Right ( f 1 ) (raise Right) => raise Abs

Lösung: Right-To-Left Evaluation Order f 1 (raise Right) => raise Right ( f 1 ) (raise Right) => raise Right

Auswertungsbeispiel

(fn a => fn b => a + x) 3 x

Zuerst wird das rechte Argument in den Akkumulator geladen.

StackUmgebung

x: 7

Akkumulator

Auswertungsbeispiel

(fn a => fn b => a + x) 3

… und auf den Stack gelegt.

StackUmgebung

x: 7

Akkumulator

7

Auswertungsbeispiel

(fn a => fn b => a + x) 3

Dann wird das nächste Argument in den Akkumulator geladen.

Stack

7

Umgebung

x: 7

Akkumulator

Auswertungsbeispiel

fn a => fn b => a + x

… und auf den Stack gelegt.

Stack

7

Umgebung

x: 7

Akkumulator

3

Auswertungsbeispiel

fn a => fn b => a + x

Die Abstraktion wird ausgeführt, indem das Argument von Stack genommen wird und als „a“ in die Umgebung eingefügt.

Stack

3

7

Umgebung

x: 7

Akkumulator

Auswertungsbeispiel

fn b => a + x

Die Abstraktion wird ausgeführt, indem das Argument von Stack genommen wird und als „b“ in die Umgebung eingefügt.

Stack

7

Umgebung

x: 7

a: 3

Akkumulator

Auswertungsbeispiel

a + x

„a“ wird aus der Umgebung in den Akkumulator geladen.

StackUmgebung

x: 7

a: 3

b: 7

Akkumulator

Auswertungsbeispiel

+ x

… und auf den Stack gelegt.

StackUmgebung

x: 7

a: 3

b: 7

Akkumulator

3

Auswertungsbeispiel

+ x

„x“ wird aus der Umgebung in den Akkumulator geladen.

Stack

3

Umgebung

x: 7

a: 3

b: 7

Akkumulator

Auswertungsbeispiel

+

Der oberste Wert auf dem Stack wird zum Akkumulator addiert.

Stack

3

Umgebung

x: 7

a: 3

b: 7

Akkumulator

7

Auswertungsbeispiel

Der Wert im Akkumulator ist das Ergebnis.

StackUmgebung

x: 7

a: 3

b: 7

Akkumulator

10

Analyse der Auswertung

Bei dieser Auswertung wurden KEINE Closures erzeugt.

Überblick

Motivation Eigenschaften funktionaler

Sprahen N-ary / Unary / curried

functions Die abstrakte Maschine Naive Auswertung Analyse der Auswertung Echte Mehrfachapplikation

Probleme Analyse der Auswertung

Darstellung von Funktionen

Das Instruction Set Die Übersetzungsfunktion Operationale Semantik Unterversorgung Überversorgung Optimierungen Darstellung von Werten Das reale Instruction Set Benchmarks

Darstellung von Funktionen

Funktionen werden durch λ-Abstraktionen mit de-Bruijn-Darstellung ersetzt: val f = fn a => fn b => a + b val f = λ . λ . <1> + <0>

val f = fn a => fn b => fn x => a + b val f = λ . λ . λ . <2> + <1>

Die Bezeichner von neu gebundenen Abstraktionen entfallen.Außerdem reduzieren sich Umgebungen von Funktionen Bezeichner -> Wert auf einfachere Werte-Listen.

Darstellung von Funktionen

Funktionen werden als Werte in Form von Closures dargestellt. Eine Closure besteht aus einer Umgebung und einer Code-

Pointer.

Beispiel (ML-Notation):

val f = fn a => fn b => fn c => a + b

f : {}, o

val g = f 5 3

g : {a:5, b:3}, o

Darstellung von Funktionen

Funktionen werden als Werte in Form von Closures dargestellt. Eine Closure besteht aus einer Umgebung und einer Code-

Pointer.

Beispiel (de-Bruijn-Notation):

val f = λ . λ . λ . <2> + <1>

f : [], o

val g = f 5 3

g : [3, 5], o

Das Instruction Set

Access(n) - liest das n. Element aus der Umgebung in den Akkumulator.

Reduce(c) - führt c aus und legt den Wert des Akkumulators auf den Stack.

Return - Beendet ein Auswertung eines Ausdrucks Grab - nimmt das oberste Element [das nächste Argument]

vom Stack und fügt sie als neues erstes Element in die Umgebung ein.

ConstInt(i) - legt die Integer-Konstante i in den Akkumulator. AddInt - Addiert das oberste Element des Stacks zum

Akkumulator.

Die Übersetzungsfunktion [ ]

[ M N ] --> Reduce( [ N ]; Return ); [ M ] [ <n> ] --> Access(n) [ λ . N ] --> Grab; [ N ] [ i ] --> ConstInt(i) [ N1 + N2 ] --> Reduce( [ N2 ]; Return );

[ N1 ]; AddInt

Jedes Programm endet mit Return.

Übersetzungsbeispiel

( fn a => fn b => a + b ) ( ( fn x => x ) 1 ) 2

( λ . λ . <1> + <0> ) ( ( λ . <0> ) 1 ) 2

[ ( λ . λ . <1> + <0> ) ( ( λ . <0> ) 1 ) 2 ]; Return

Übersetzungsbeispiel

( fn a => fn b => a + b ) ( ( fn x => x ) 1 ) 2

( λ . λ . <1> + <0> ) ( ( λ . <0> ) 1 ) 2

Reduce( [ 2 ]; Return );[ ( λ . λ . <1> + <0> ) ( ( λ . <0> ) 1 ) ]; Return

Übersetzungsbeispiel

( fn a => fn b => a + b ) ( ( fn x => x ) 1 ) 2

( λ . λ . <1> + <0> ) ( ( λ . <0> ) 1 ) 2

Reduce( ConstInt(2); Return );[ ( λ . λ . <1> + <0> ) ( ( λ . <0> ) 1 ) ]; Return

Übersetzungsbeispiel

( fn a => fn b => a + b ) ( ( fn x => x ) 1 ) 2

( λ . λ . <1> + <0> ) ( ( λ . <0> ) 1 ) 2

Reduce( ConstInt(2); Return );Reduce( [ ( λ . <0> ) 1 ]; Return );[ λ . λ . <1> + <0> ]; Return

Übersetzungsbeispiel

( fn a => fn b => a + b ) ( ( fn x => x ) 1 ) 2

( λ . λ . <1> + <0> ) ( ( λ . <0> ) 1 ) 2

Reduce( ConstInt(2); Return );Reduce( Reduce( [ 1 ]; Return ); [ λ . <0> ]; Return );[ λ . λ . <1> + <0> ]; Return

Übersetzungsbeispiel

( fn a => fn b => a + b ) ( ( fn x => x ) 1 ) 2

( λ . λ . <1> + <0> ) ( ( λ . <0> ) 1 ) 2

Reduce( ConstInt(2); Return );Reduce( Reduce( ConstInt(1); Return ); [ λ . <0> ]; Return );[ λ . λ . <1> + <0> ]; Return

Übersetzungsbeispiel

( fn a => fn b => a + b ) ( ( fn x => x ) 1 ) 2

( λ . λ . <1> + <0> ) ( ( λ . <0> ) 1 ) 2

Reduce( ConstInt(2); Return );Reduce( Reduce( ConstInt(1); Return ); Grab; [ <0> ]; Return );[ λ . λ . <1> + <0> ]; Return

Übersetzungsbeispiel

( fn a => fn b => a + b ) ( ( fn x => x ) 1 ) 2

( λ . λ . <1> + <0> ) ( ( λ . <0> ) 1 ) 2

Reduce( ConstInt(2); Return );Reduce( Reduce( ConstInt(1); Return ); Grab; Access(0); Return );[ λ . λ . <1> + <0> ]; Return

Übersetzungsbeispiel

( fn a => fn b => a + b ) ( ( fn x => x ) 1 ) 2

( λ . λ . <1> + <0> ) ( ( λ . <0> ) 1 ) 2

Reduce( ConstInt(2); Return );Reduce( Reduce( ConstInt(1); Return ); Grab; Access(0); Return );Grab; [ λ . <1> + <0> ]; Return

Übersetzungsbeispiel

( fn a => fn b => a + b ) ( ( fn x => x ) 1 ) 2

( λ . λ . <1> + <0> ) ( ( λ . <0> ) 1 ) 2

Reduce( ConstInt(2); Return );Reduce( Reduce( ConstInt(1); Return ); Grab; Access(0); Return );Grab; Grab; [ <1> + <0> ]; Return

Übersetzungsbeispiel

( fn a => fn b => a + b ) ( ( fn x => x ) 1 ) 2

( λ . λ . <1> + <0> ) ( ( λ . <0> ) 1 ) 2

Reduce( ConstInt(2); Return );Reduce( Reduce( ConstInt(1); Return ); Grab; Access(0); Return );Grab; Grab; Reduce( [ <0> ]; Return ); [ <1> ]; AddInt; Return

Übersetzungsbeispiel

( fn a => fn b => a + b ) ( ( fn x => x ) 1 ) 2

( λ . λ . <1> + <0> ) ( ( λ . <0> ) 1 ) 2

Reduce( ConstInt(2); Return );Reduce( Reduce( ConstInt(1); Return ); Grab; Access(0); Return ); Grab; Grab; Reduce( Access(0); Return ); [ <1> ]; AddInt; Return

Übersetzungsbeispiel

( fn a => fn b => a + b ) ( ( fn x => x ) 1 ) 2

( λ . λ . <1> + <0> ) ( ( λ . <0> ) 1 ) 2

Reduce( ConstInt(2); Return );Reduce( Reduce( ConstInt(1); Return ); Grab; Access(0); Return ); Grab; Grab; Reduce( Access(0); Return ); Access(1); AddInt; Return

Das Instruction Set

Access(n) - liest das n. Element aus der Umgebung in den Akkumulator.

Reduce(c) - führt c aus und legt den Wert des Akkumulators auf den Stack.

Return - Beendet ein Auswertung eines Ausdrucks Grab - nimmt das oberste Element [das nächste Argument]

vom Stack und fügt sie als neues erstes Element in die Umgebung ein.

ConstInt(i) - legt die Integer-Konstante i in den Akkumulator. AddInt - Addiert das oberste Element des Stacks zum

Akkumulator.

Operationale Semantik

Code Akku Env. Stack Code Akku Env Stack

Access(k); c a [v0..vn] s c vk [v0..vn] s

Reduce(c‘); c

a e s c‘ a e <c,e> :: s

Return a e <c0, e0> :: s c0 a e0 a :: s

Return (c0, e0) e v :: s c0 (c0, e0) e0 v :: s

Grab; c a e v :: s c a v :: e s

Grab; c a e <c0, e0> :: s c0 a e0 (Grab; c, e) :: s

ConstInt(i); c a e s c i e s

AddInt; c a e v :: s c a + v e s

SubInt; c a e v :: s c a – v e s

Verbleibende Closures

Closures können nur von Grab und Reduce erzeugt werden.

Grab erzeugt eine Closure genau dann, wenn keine weiteren Argumente vorhanden sind. (Normale Closure)=> Das Ergebnis ist eine Abstraktion, die Closure ist notwendig.

Reduce erzeugt Closures, um die Auswertung zu unterbrechen, bis ein Argument reduziert ist. (Markierte Closure)Diese Closures können nicht in die Umgebung eingefügt werden.=> Sie können auf dem Stack alloziiert werden.=> Sie belasten den Heap / die Garbage Collection nicht.

Wie funktioniert Unter- / Überversorgung ?

Überblick

Motivation Eigenschaften funktionaler

Sprahen N-ary / Unary / curried

functions Die abstrakte Maschine Naive Auswertung Analyse der Auswertung Echte Mehrfachapplikation

Probleme Analyse der Auswertung

Darstellung von Funktionen

Das Instruction Set Die Übersetzungsfunktion Operationale Semantik Unterversorgung Überversorgung Optimierungen Darstellung von Werten Das reale Instruction Set Benchmarks

Unterversorgung

Unterversorgung bedeutet, dass eine Curried-Function weniger Argumente bekommt, als sie bekommen könnte.

( fn a => fn b => 1 ) 2

( λ . λ . 1 ) 2

Reduce( ConstInt(2); Return ); Grab; Grab; Access(1); Return

Unterversorgung

Reduce( ConstInt(2); Return ); Grab; Grab; Access(1); Return

StackUmgebung

Akkumulator

Unterversorgung

ConstInt(2); Return

Stack

<Closure A>

Umgebung

Akkumulator

Closure A

Code

Grab; ... Return

Umgebung

Unterversorgung

Return

Stack

<Closure A>

Umgebung

Akkumulator

2

Closure A

Code

Grab; ... Return

Umgebung

Unterversorgung

Grab; Grab; Access(1); Return

Stack

2

Umgebung

Akkumulator

Unterversorgung

Grab; Access(1); Return

StackUmgebung

2

Akkumulator

Operationale Semantik

Code Akku Env. Stack Code Akku Env Stack

Access(k); c a [v0..vn] s c vk [v0..vn] s

Reduce(c‘); c

a e s c‘ a e <c,e> :: s

Return a e <c0, e0> :: s c0 a e0 a :: s

Return (c0, e0) e v :: s c0 (c0, e0) e0 v :: s

Grab; c a e v :: s c a v :: e s

Grab; c a e <c0, e0> :: s c0 a e0 (Grab; c, e) :: s

ConstInt(i); c a e s c i e s

AddInt; c a e v :: s c a + v e s

SubInt; c a e v :: s c a – v e s

Unterversorgung

Stack

(Closure B)

Umgebung

Akkumulator

Closure B

Code

Grab; Access(1); Return

Umgebung

2

Überblick

Motivation Eigenschaften funktionaler

Sprahen N-ary / Unary / curried

functions Die abstrakte Maschine Naive Auswertung Analyse der Auswertung Echte Mehrfachapplikation

Probleme Analyse der Auswertung

Darstellung von Funktionen

Das Instruction Set Die Übersetzungsfunktion Operationale Semantik Unterversorgung Überversorgung Optimierungen Darstellung von Werten Das reale Instruction Set Benchmarks

Überversorgung

Überversorgung bedeutet, dass eine Curried-Function mehr Argumente bekommt, als zu erwarten wäre.Daher muss das Ergebnis der Anwendung der erwarteten Argumente eine Abstraktion sein. (Typ-Korrektheit)

( fn a => a ) ( fn b => 1 ) 2

( λ . <0> ) ( λ . 1 ) 2

Reduce( ConstInt(2); Return );Reduce( Grab; ConstInt(1); Return );Grab; Access(0); Return

Überversorgung

Reduce( ConstInt(2); Return );Reduce( Grab; ConstInt(1); Return );Grab; Access(0); Return

StackUmgebung

Akkumulator

Überversorgung

ConstInt(2); Return

Stack

<Closure A>

Umgebung

Akkumulator

Closure A

Code

Reduce ...; Return

Umgebung

Überversorgung

Return

Stack

<Closure A>

Umgebung

Akkumulator

2

Closure A

Code

Reduce ... Return

Umgebung

Überversorgung

Reduce( Grab; ConstInt(1); Return );Grab; Access(0); Return

Stack

2

Umgebung

Akkumulator

Überversorgung

Grab; ConstInt(1); Return

Stack

<Closure B>

2

Umgebung

Akkumulator

Closure B

Code

Grab; ...; Return

Umgebung

Operationale Semantik

Code Akku Env. Stack Code Akku Env Stack

Access(k); c a [v0..vn] s c vk [v0..vn] s

Reduce(c‘); c

a e s c‘ a e <c,e> :: s

Return a e <c0, e0> :: s c0 a e0 a :: s

Return (c0, e0) e v :: s c0 (c0, e0) e0 v :: s

Grab; c a e v :: s c a v :: e s

Grab; c a e <c0, e0> :: s c0 a e0 (Grab; c, e) :: s

ConstInt(i); c a e s c i e s

AddInt; c a e v :: s c a + v e s

SubInt; c a e v :: s c a – v e s

Überversorgung

Grab; Access(0); Return

Stack

(Closure C)

2

Umgebung

Akkumulator

Closure C

Code

Grab; ...; Return

Umgebung

Überversorgung

Access(0); Return

Stack

2

Umgebung

(Closure C)

Akkumulator

Closure C

Code

Grab; ...; Return

Umgebung

Überversorgung

Return

Stack

2

Umgebung

(Closure C)

Akkumulator

(Closure C)

Closure C

Code

Grab; ...; Return

Umgebung

Operationale Semantik

Code Akku Env. Stack Code Akku Env Stack

Access(k); c a [v0..vn] s c vk [v0..vn] s

Reduce(c‘); c

a e s c‘ a e <c,e> :: s

Return a e <c0, e0> :: s c0 a e0 a :: s

Return (c0, e0) e v :: s c0 (c0, e0) e0 v :: s

Grab; c a e v :: s c a v :: e s

Grab; c a e <c0, e0> :: s c0 a e0 (Grab; c, e) :: s

ConstInt(i); c a e s c i e s

AddInt; c a e v :: s c a + v e s

SubInt; c a e v :: s c a – v e s

Überversorgung

Grab; ConstInt(1); Return

Stack

2

Umgebung

Akkumulator

Überversorgung

ConstInt(1); Return

StackUmgebung

2

Akkumulator

Überversorgung

Return

StackUmgebung

2

Akkumulator

1

Überversorgung

Stack

1

Umgebung

Akkumulator

Weitere Optimierungen

Durch einen Cache (in Registern der Virtuellen Maschine) wird der Zugriff auf die aktuellsten Elemente der Umgebung beschleunigt.

Es gibt spezialisierte Instruktionen für häufige Operationen.(z.B.: Let, Konstante Konstruktoren, Endrekursion …)

Durch eine globale Variablenliste wird die Umgebung stark verkleinert.

Trennung von Argumenten-Stack und Return-Stack

Überblick

Motivation Eigenschaften funktionaler

Sprahen N-ary / Unary / curried

functions Die abstrakte Maschine Naive Auswertung Analyse der Auswertung Echte Mehrfachapplikation

Probleme Analyse der Auswertung

Darstellung von Funktionen

Das Instruction Set Die Übersetzungsfunktion Operationale Semantik Unterversorgung Überversorgung Optimierungen Darstellung von Werten Das reale Instruction Set Benchmarks

Darstellung von Werten

Alle Werte sind 32-bit Worte.

unboxed, also direkt, werden folgende Typen abgelegt: 31-bit vorzeichenbehaftete Integer werden als 32-bit Integer

mit gesetztem Bit 0 dargestellt. Zeiger in den Heap (oder in den Code auf Konstanten) werden

direkt abgelegt. (Ihre Binärdarstellung endet auf 00.)

Alle anderen Datentypen werden im Heap angelegt und es wird nur der Zeiger auf diesen Speicherblock abgelegt. „boxed“

31-bit Integer

..........1

32-bit Pointer

.........00

? Real .........10

Heap-Aufbau

Der Speicher besteht aus 32-bit Worten, die in Blöcke aufgeteilt werden. Jeder Block hat einen Header, mit einer Beschreibung seines Inhalts, seiner Größe und 2 Bits für die Garbage Collection.

Die Garbage Collection kann selbständig zwischen unstrukturierten Daten und Listen von Werten unterscheiden.

Es gibt im Code keine Zeiger in den Heap. Es gibt in der globalen Variablenliste Zeiger in den Heap.

Speicherblöcke im Heap

Im ersten Word eines Blocks steht: n – die Größe des Blocks (22 bit) GC – Daten für den Garbage Collector (2 bit) tag – Typinformation (8 bit)

Das Tag-Feld bestimmt die Interpretation des Inhalts tag=255: Unstrukturierte Blöcke tag=254: Closure tag<254: Konkreter Datentyp

n GC tag

field1

.

.

.

fieldn

Unstrukturierte Blöcke

Unstrukturierte Blöcke enthalten keine Werte. tag = 255

Beispiel: Strings

Strings werden nullterminiert abgelegt Sie werden aufgefüllt, so dass Länge = 4 * Block-Größe – letztes Byte.

Beispiel: var x = „Abstract_Maschine“

5 GC 255

Abst

ract

_Mas

chin

e\0\0\3

Closure

Closures sind stukturierte Blöcke,d.h. sie enthalten Werte.

tag = 254

Der Datenblock besteht aus dem Codezeigerund der zugehörigen Umgebung

Im Beispiel: k Elemente in der Umgebung

k+1 GC 254

<codepointer>

value1

value2

…

valuek

Konkrete Datentypen

Instanzen sind strukturierte Blöcke,d.h. sie enthalten Werte.

tag < 254

Beispiel:datatype t = I of int * int | S of string

Varianten werden beginnend mit 0 durchnummeriert.Die Variantennummer wird als tag verwendet.

2 GC 0

value1

value2

1 GC 1

pointer1

Konkrete Datentypen (2)

Sind mehr als 254 Varianten vorhanden,so muss eine alternative Darstellungverwendet werden.

Die Variantennummer wird als Integerim ersten Daten-Feld abgelegt.

Beispiel:datatype t = C0 of int | ... | C254 of int * int

2 GC 0

0

value1

3 GC 0

254

value1

value2

Beispiel

datatype t = A of int | B of int * t * string * (int->int)

val x = B(3, A 2, „test“, (fn a => fn b => a+b) 3)

4 GC

1

3

o

o

o

2 GC

255

test

\0\0\0\4

1 GC

0

2

2 GC

254

o

3

Vorteile der Blockdarstellung

Der Garbage Collector kann erkennen, ob es sich um reine Daten oder eine Liste von Werten handelt, die Zeiger enthalten können.

Zur Erinnerung:Zeiger können von Integern an den beiden abschließenden 00 unterschieden werden.

Überblick

Motivation Eigenschaften funktionaler

Sprahen N-ary / Unary / curried

functions Die abstrakte Maschine Naive Auswertung Analyse der Auswertung Echte Mehrfachapplikation

Probleme Analyse der Auswertung

Darstellung von Funktionen

Das Instruction Set Die Übersetzungsfunktion Operationale Semantik Unterversorgung Überversorgung Optimierungen Darstellung von Werten Das reale Instruction Set Benchmarks

Das reale Instruction Set

Constants and literals Function handling Environment handling Building and destructing blocks Integers Floating-point numbers Strings Predicates Branches and conditional branches Miscellaneous

Constants and literals

Constbyte(int8), Constshort(int16), Constlog(int32)Lädt eine Konstante.

Atom(tag), Atom0, …, Atom9Lädt einen Pointer auf einen konstanten Block mit Tag tag.

GetGlobal(int16), SetGlobal(int16)Lädt eine globale Variable oder speichert diese.

Function handling

Push, PushmarkLegt den Akkumulator bzw. eine Markierung auf den Stack

Apply, AppTermFührt die Closure im Akkumulator aus. (Normal / endrekursiv)

ReturnBeendet die Auswertung eines Ausdrucks

GrabFügt ein Argument vom Stack in die Umgebung ein.

Cur(ofs)Erstellt eine Closure für Codepointer ofs im Akkumulator

Integers and floating-point numbers

SuccInt, PredInt, NegInt, AddInt, SubInt, MulInt, DivInt, ModInt, AndInt, OrInt, XorInt, ShiftLeftInt, ShiftRightIntBerechnet die jeweilige Operation mit dem Akkumulator und ggf. dem obersten Element des Stacks.

FloatOfInt, IntOfFloatKonvertiert Integer in Fließkommazahlen oder umgekehrt.

Floatop(AddFloat), Floatop(SubFloat), Floatop(MulFloat), Floatop(DivFloat)Berechnet die jeweiligen Operationen

Branches and conditional branches

Branchifeqtag(tag, ofs), Branchifneqtag(tag, ofs)Springt relativ um ofs, falls der Akkumulator auf Tag tag zeigt.

Switch(ofs0, ..., ofsk)Springt relativ um ofstag falls der Akkumulator auf Tag tag zeigt.

BranchifEq(ofs)Springt relativ um ofs, falls der Akkumulator und der oberste Element des Stacks pointer-gleich sind.

BranchifEqual(ofs)Springt relativ um ofs, falls der Akkumulator und der oberste Element des Stacks struktuell gleich sind.

… viele weitere

Benchmarks

fun fib n = if n<2 then 1 else fib(n-1) + fib(n-2)

fun tak x y z = if x>y then tak (tak (x-1) y z) (tak (y-1) z x) (tak (z-1) x y) else z

fun sum [] = 0 | sum (a::ar) = a + sum arfun interval n = if n = 0 then nil else n :: interval(n-1)

fun double f x = f (f x)val quad = double doubleval oct = quad quad

fun succ n = n+1

fib 26tak 18 12 6sum (interval 10000)double oct (fn x => x+1) 1map (quad quad succ) (intervall 1000)

Benchmarks (2)

Quellen

Xavier Leroy, The ZINC experiment:an economical implementation of the ML language. Technical report 117, INRIA, 1990