Effiziente
Virtuelle Maschinen
für funktionale Programmiersprachen
Xavier Leroy, The ZINC experiment:
an economical implementation of the ML language.
Technical report 117, INRIA, 1990
Überblick


Motivation
Eigenschaften funktionaler
Sprahen





Die abstrakte Maschine
Naive Auswertung
Analyse der Auswertung
Echte Mehrfachapplikation


N-ary / Unary / curried
functions
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-Tupel
fun 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





Die abstrakte Maschine
Naive Auswertung
Analyse der Auswertung
Echte Mehrfachapplikation


N-ary / Unary / curried
functions
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
Akkumulator

(fn a => fn b => a + x) 3 x

Um die erste Applikation auszuführen, wird der Folgeausdruck als Closure
auf den Stack gelegt.
Umgebung
x: 7
Stack
Auswertungsbeispiel
Akkumulator

(fn a => fn b => a + x) 3

Der Parameter wird in den Akkumulator geladen.
Closure A
Umgebung
Code
x: 7
Stack
X
Umgebung
x: 7
Closure A
Auswertungsbeispiel
Akkumulator

(fn a => fn b => a + x)

… und auf den Stack gelegt.
3
Closure A
Umgebung
Code
x: 7
Stack
X
Umgebung
x: 7
Closure A
Auswertungsbeispiel
Akkumulator

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.
Closure A
Umgebung
Code
x: 7
Stack
X
Umgebung
x: 7
3
Closure A
Auswertungsbeispiel
Akkumulator

fn b => a + x

Bei einer weiteren Abstraktion ist die Auswertung zunächst abgebrochen.
Das Zwischenergebnis wird in einer Closure in den Akkumulator gepackt.
Closure A
Umgebung
Code
x: 7
X
a: 3
Stack
Umgebung
x: 7
Closure A
Auswertungsbeispiel
Akkumulator
Closure B

Die neue Closure ersetzt die unterbrochene Auswertung auf dem Stack.
Diese wird fortgesetzt.
Closure B
Closure A
Code
Code
fn b => a + x
X
Umgebung
Umgebung
x: 7
x: 7
Stack
a: 3
Closure A
Auswertungsbeispiel
Akkumulator

x

Das nächste Argument wird in den Akkumulator geladen.
Closure B
Umgebung
Code
x: 7
Stack
fn b => a + x
Umgebung
x: 7
a: 3
Closure B
Auswertungsbeispiel
Akkumulator
7

… und auf den Stack gelegt.
Die unterbrochene Auswertung wird fortgesetzt.
Closure B
Umgebung
Code
x: 7
Stack
fn b => a + x
Umgebung
x: 7
a: 3
Closure B
Auswertungsbeispiel
Akkumulator

fn b => a + x

Die Abstraktion wird ausgeführt, indem das Argument von Stack genommen
wird und als „b“ in die Umgebung eingefügt.
Umgebung
Stack
x: 7
a: 3
7
Auswertungsbeispiel
Akkumulator

a + x

„a“ wird aus der Umgebung in den Akkumulator geladen.
Umgebung
x: 7
a: 3
b: 7
Stack
Auswertungsbeispiel
Akkumulator

+ x

… und auf den Stack gelegt.
3
Umgebung
x: 7
a: 3
b: 7
Stack
Auswertungsbeispiel
Akkumulator

+ x

„x“ wird aus der Umgebung in den Akkumulator geladen.
Umgebung
Stack
x: 7
a: 3
b: 7
3
Auswertungsbeispiel
Akkumulator
7

+

Der oberste Wert auf dem Stack wird zum Akkumulator addiert.
Umgebung
Stack
x: 7
a: 3
b: 7
3
Auswertungsbeispiel
Akkumulator
10

Der Wert im Akkumulator ist das Ergebnis.
Umgebung
x: 7
a: 3
b: 7
Stack
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





Die abstrakte Maschine
Naive Auswertung
Analyse der Auswertung
Echte Mehrfachapplikation


N-ary / Unary / curried
functions
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
Akkumulator

(fn a => fn b => a + x) 3 x

Zuerst wird das rechte Argument in den Akkumulator geladen.
Umgebung
x: 7
Stack
Auswertungsbeispiel
Akkumulator

(fn a => fn b => a + x) 3

… und auf den Stack gelegt.
7
Umgebung
x: 7
Stack
Auswertungsbeispiel
Akkumulator

(fn a => fn b => a + x) 3

Dann wird das nächste Argument in den Akkumulator geladen.
Umgebung
Stack
x: 7
7
Auswertungsbeispiel
Akkumulator

fn a => fn b => a + x

… und auf den Stack gelegt.
3
Umgebung
Stack
x: 7
7
Auswertungsbeispiel
Akkumulator

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.
Umgebung
Stack
x: 7
3
7
Auswertungsbeispiel
Akkumulator

fn b => a + x

Die Abstraktion wird ausgeführt, indem das Argument von Stack genommen
wird und als „b“ in die Umgebung eingefügt.
Umgebung
Stack
x: 7
a: 3
7
Auswertungsbeispiel
Akkumulator

a + x

„a“ wird aus der Umgebung in den Akkumulator geladen.
Umgebung
x: 7
a: 3
b: 7
Stack
Auswertungsbeispiel
Akkumulator

+ x

… und auf den Stack gelegt.
3
Umgebung
x: 7
a: 3
b: 7
Stack
Auswertungsbeispiel
Akkumulator

+ x

„x“ wird aus der Umgebung in den Akkumulator geladen.
Umgebung
Stack
x: 7
a: 3
b: 7
3
Auswertungsbeispiel
Akkumulator
7

+

Der oberste Wert auf dem Stack wird zum Akkumulator addiert.
Umgebung
Stack
x: 7
a: 3
b: 7
3
Auswertungsbeispiel
Akkumulator
10

Der Wert im Akkumulator ist das Ergebnis.
Umgebung
x: 7
a: 3
b: 7
Stack
Analyse der Auswertung

Bei dieser Auswertung wurden KEINE Closures erzeugt.
Überblick


Motivation
Eigenschaften funktionaler
Sprahen





Die abstrakte Maschine
Naive Auswertung
Analyse der Auswertung
Echte Mehrfachapplikation


N-ary / Unary / curried
functions
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 [ ]

[
[
[
[
[

Jedes Programm endet mit Return.




M N ]
<n> ]
λ . N ]
i ]
N1 + N2 ]
-->
-->
-->
-->
-->
Reduce( [ N ]; Return ); [ M ]
Access(n)
Grab; [ N ]
ConstInt(i)
Reduce( [ N2 ]; Return );
[ N1 ]; AddInt
Ü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





Die abstrakte Maschine
Naive Auswertung
Analyse der Auswertung
Echte Mehrfachapplikation


N-ary / Unary / curried
functions
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
Akkumulator

Reduce( ConstInt(2); Return );
Grab; Grab; Access(1); Return
Umgebung
Stack
Unterversorgung
Akkumulator

ConstInt(2); Return
Closure A
Umgebung
Stack
Code
Grab; ... Return
Umgebung
<Closure A>
Unterversorgung
Akkumulator

2
Return
Closure A
Umgebung
Stack
Code
Grab; ... Return
Umgebung
<Closure A>
Unterversorgung
Akkumulator

Grab; Grab; Access(1); Return
Umgebung
Stack
2
Unterversorgung
Akkumulator

Grab; Access(1); Return
Umgebung
2
Stack
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
Akkumulator
Closure B
Umgebung
Stack
Code
Grab; Access(1); Return
Umgebung
2
(Closure B)
Überblick


Motivation
Eigenschaften funktionaler
Sprahen





Die abstrakte Maschine
Naive Auswertung
Analyse der Auswertung
Echte Mehrfachapplikation


N-ary / Unary / curried
functions
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
Akkumulator

Reduce( ConstInt(2); Return );
Reduce( Grab; ConstInt(1); Return );
Grab; Access(0); Return
Umgebung
Stack
Überversorgung
Akkumulator

ConstInt(2); Return
Closure A
Umgebung
Stack
Code
Reduce ...; Return
Umgebung
<Closure A>
Überversorgung
Akkumulator

2
Return
Closure A
Umgebung
Stack
Code
Reduce ... Return
Umgebung
<Closure A>
Überversorgung
Akkumulator

Reduce( Grab; ConstInt(1); Return );
Grab; Access(0); Return
Umgebung
Stack
2
Überversorgung
Akkumulator

Grab; ConstInt(1); Return
Closure B
Umgebung
Stack
Code
Grab; ...; Return
Umgebung
<Closure B>
2
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
Akkumulator

Grab; Access(0); Return
Closure C
Umgebung
Stack
Code
Grab; ...; Return
Umgebung
(Closure C)
2
Überversorgung
Akkumulator

Access(0); Return
Closure C
Umgebung
Code
(Closure C)
Stack
Grab; ...; Return
Umgebung
2
Überversorgung
Akkumulator

(Closure C)
Return
Closure C
Umgebung
Code
(Closure C)
Stack
Grab; ...; Return
Umgebung
2
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
Akkumulator

Grab; ConstInt(1); Return
Umgebung
Stack
2
Überversorgung
Akkumulator

ConstInt(1); Return
Umgebung
2
Stack
Überversorgung
Akkumulator

1
Return
Umgebung
2
Stack
Überversorgung
Akkumulator
Umgebung
Stack
1
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





Die abstrakte Maschine
Naive Auswertung
Analyse der Auswertung
Echte Mehrfachapplikation


N-ary / Unary / curried
functions
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
31-bit Integer
..........1
32-bit Pointer
.........00
? Real
.........10

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“
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)
n
GC tag
field1
.
.
.
fieldn




Das Tag-Feld bestimmt die Interpretation des Inhalts
tag=255: Unstrukturierte Blöcke
tag=254: Closure
tag<254: Konkreter Datentyp
Unstrukturierte Blöcke

Unstrukturierte Blöcke enthalten keine Werte.
tag = 255

Beispiel: Strings

5
GC
Abst
ract
_Mas

Strings werden nullterminiert abgelegt
Sie werden aufgefüllt, so dass
Länge = 4 * Block-Größe – letztes Byte.

Beispiel: var x = „Abstract_Maschine“


chin
e\0\0\3
255
Closure


Closures sind stukturierte Blöcke,
d.h. sie enthalten Werte.
tag = 254
k+1
GC
<codepointer>
value1


254
Der Datenblock besteht aus dem Codezeiger
und der zugehörigen Umgebung
value2
Im Beispiel: k Elemente in der Umgebung
valuek
…
Konkrete Datentypen


Instanzen sind strukturierte Blöcke,
d.h. sie enthalten Werte.
tag < 254
2
GC
0
value1
value2


Beispiel:
datatype t = I of int * int
| S of string
1
Varianten werden beginnend mit 0 durchnummeriert.
Die Variantennummer wird als tag verwendet.
GC
pointer1
1
Konkrete Datentypen (2)

Sind mehr als 254 Varianten vorhanden,
so muss eine alternative Darstellung
verwendet werden.
2
GC
0
0
value1


Die Variantennummer wird als Integer
im ersten Daten-Feld abgelegt.
Beispiel:
datatype t = C0 of int
| ...
| C254 of int * int
3
GC
254
value1
value2
0
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)
1
GC
0
2
4
GC
3
1
2
GC
255
2
GC
o
test
o
o
\0\0\0\4
3
o
254
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





Die abstrakte Maschine
Naive Auswertung
Analyse der Auswertung
Echte Mehrfachapplikation


N-ary / Unary / curried
functions
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, …, Atom9
Lä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, Pushmark
Legt den Akkumulator bzw. eine Markierung auf den Stack

Apply, AppTerm
Führt die Closure im Akkumulator aus. (Normal / endrekursiv)

Return
Beendet die Auswertung eines Ausdrucks

Grab
Fü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, ShiftRightInt
Berechnet die jeweilige Operation mit dem Akkumulator und ggf.
dem obersten Element des Stacks.

FloatOfInt, IntOfFloat
Konvertiert 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 ar
fun interval n = if n = 0 then nil else n :: interval(n-1)

fun double f x = f (f x)
val quad = double double
val oct = quad quad

fun succ n = n+1

fib 26
tak 18 12 6
sum (interval 10000)
double oct (fn x => x+1) 1
map (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

Folien