Compilerbau/Kapitel 4: Zwischensprachen

Aus Halloserv Wiki

Zwischensprachen werden benutzt, um die Ergebnisse des Frontend (lexikalische, syntaktische und semantische Analyse) mit dem Backend (Codeerzeugung- und Optimierung) zu verbinden. Sie werden eingesetzt, weil man hierdurch die Anzahl der zu schreibenden Programme deutlich verringern kann: Hat man m Quell- und n Zielsprachen, so benötigt man mit Zwischensprache lediglich m + n Programme zur Uebersetzung. Wir suchen hierfür eine interne Repräsentation eines Programmes, für die diese Kriterien erfüllt sind:

einfach zu analysieren
einfach zu transformieren
einfache Codeerzeugung (Elemente der Repräsentation sollen wenigen Maschinenbefehlen entsprechen)
eindeutig festgelegte Bedeutung

Die Vorlesung überspringt hier eine Kapitel aus dem ursprünglichen Skript, den Lambda-Kalkül. Es entsteht dadurch ein bisschen Verwirrung, was den Inhalt angeht, aber im Grunde bezweckt dieses Kapitel die Vereinfachung des Quellcodes nach den oben beschriebenen Kriterien. Zu diesem Zweck entwerfen wir eine Reihe von Interpretern: zuerst einen naiven Interpreter, der dann zu einem Interpreter mit continuation-passing style (CPS) ausgebaut wird, um daraufhin Lambda-Lifting (basierend auf dem Lambda-Kalkül) und weitere Verfahren zu benutzen, die uns schrittweise dem Maschinencode näherbringen.

Inhaltsverzeichnis

1 Naiver Interpreter
2 Continuation-Passing Style
- 2.1 Exceptions
3 Closures
4 Lambda-Lifting
- 4.1 Algorithmus
5 Der Weg zum Maschinencode

Naiver Interpreter

Wir beginnen mit einer Struktur zur Buchführung über die Bezeichner, environment und zugehörigen Operationen. Dies werden als Funktionen festgelegt, damit wir die Struktur in Zukunft optimieren können, ohne den restlichen Code ändern zu müssen:

<div style="padding-left:4px;" id="Code: environment">Code: environment

type expr =
    Int of int
  | Builtin of ident * expr list
  | If of expr * expr * expr
  | Ident of ident
  | Let of ident * expr * expr
  | Function of ident * ident list * expr
  | Apply of expr * expr list
  | Raise of expr
  | Try of expr * ident * expr
  | Var of ident * expr * expr
  | Assign of ident * expr

(* environment manipulation - the environment is a list of identifier-value pairs. *)
type 'value env =
  (string * 'value) list
let extend env x v =
  ((x,v)::env)
let rec extends env xs vs =
  match (xs, vs) with
      (x::xs, v::vs) -> extends (extend env x v) xs vs
    | ([], []) -> env
let lookup =
  List.assoc

</div>

Als nächstes folgt der naive Interpreter eval selbst:

Code: naiver Interpreter

(* begin with a few definitions for values and exceptions *)

type value =
    VInt of int
  | VFun of (value list -> value)
  | VRef of value ref
  | VUnit of unit

let exInt (VInt i) = i
let exFun (VFun f) = f
let exRef (VRef r) = r
let exUnit (VUnit u) = u

exception VException of value

(* eval : Syntax.t −> value env −> value *)
let rec eval e env =
  match e with
      Int (i) -> VInt (i)
    | Builtin (f, es) -> (
        match (f, evals es env) with
            ("+", [v1; v2]) -> VInt (exInt v1 + exInt v2))
    | If (e1, e2, e3) -> 
        if exInt (eval e1 env) != 0
        then eval e2 env
        else eval e3 env
    | Ident (x) -> lookup x env
    | Let (x, e1, e2) -> eval e2 (extend env x (eval e1 env))
    | Function (x0, xs, e) -> VFun (function vs -> eval e (extends env xs vs))
    | Apply (e0, es) -> (exFun (eval e0 env)) (evals es env)
    | Raise (e) -> raise (VException (eval e env))
    | Try (e0, x, e1) -> (
        try eval e0 env with
          VException v -> eval e1 (extend env x v))
    | Var (x, e1, e2) -> eval e2 (extend env x (VRef (ref (eval e1 env))))
    | Assign (x, e) -> VUnit ((exRef (lookup x env)) := eval e env)

and evals es env =
  match es with
      [] -> []
    | e :: es -> eval e env :: evals es env

Continuation-Passing Style

Wie man im naiven Interpreter bei Apply(e1, e2) sehen kann, ist die Reihenfolge der Auswertung von Argumenten nicht festgelegt, gegebenenfalls wird e2 gar gar nicht ausgeführt. Das nennt man auch das Sequenzierungsproblem. Damit die Auswertung der Argumente sichergestellt wird, übergeben wir nun nur noch Werte als Parameter. Erreicht wird das durch Transformation des Programms in den Continuation-Passing Style (CPS). Ein Ausdruck in einem CPS Programm liefert kein Ergebnis, sondern übergibt das Ergebnis an eine Continuation, das heisst eine Funktion, die den Kontext des Ausdrucks (den Rest des Programms) repräsentiert.

Als Illustration mag dieser Vergleich der Fakultätsfunktion in "direktem Stil" und CPS dienen:

Beispiel: Fakultät

(* direct style *)
let rec fac n = 
  if n = 0 then 1 else n * fac (n - 1)

(* CPS, unter der Annahme, dass
     =' (x, y) c
     *' (x, y) c
     -' (x, y) c
   die CPS Versionen von =, *, - sind. *)
let rec fac' n c =
  ='(n, 0) (function b ->
    if b then 
      c 1
    else -'(n, 1) (function n' ->
      fac' n' (function r' ->
        *'(n, r') (function r -> c r))))

Wie man sieht, sind alle Argumente Werte, die Reihenfolge der Auswertung ist festgelegt, Funktionsaufrufe werden zu Sprüngen und primitve Argumente können teilweise als Maschieneninstruktionen gelesen werden. Es gibt aber auch ein paar Nachtteile: Eine wirkliche Festlegung auf primitive Operatoren/Maschienenbefehle ist hier zu früh (weil es je nach Architektur unterschiedliche Spezialbefehle gibt, z.B. MULT/ADD bei der Power-Architektur). Auch müssen die Continuations unterschiedlich repräsentiert werden:

(function n' -> ...) Vorwärtsschalten des Program Counters (PC)
(function r' -> ...) ? (jedenfalls nicht Vorwärtsschalten des PC)

Für unsere Zwecke reicht deshalb eine schwächere Form, bei der alle Argumente primitiv auswertbar sind:

Beispiel: Fakultät 2

let rec fac'' n c =
  if n = 0 then 
    c 1
  else
    fac'' (n-1) (function r' -> c (n * r'))

Daraus folgend konstruieren wir jetzt einen naiven Interpreter mit CPS:

Code: CPS-Interpreter

(* as before we start with definitions - note the changed line for VFun *)
type value =
    VInt of int
  | VFun of (value list -> (value -> value) -> value)
  | VRef of value ref
  | VUnit of unit

let exInt (VInt i) = i
let exFun (VFun f) = f
let exRef (VRef r) = r
let exUnit (VUnit u) = u

exception VException of value

(* eval : Syntax.t −> value env −> (value −> value) −> value *)
let rec eval e env c =
  match e with
      Int (i) -> c (VInt (i))
    | Builtin (f, es) ->
        evals es env (function vs ->
          (match (f, vs) with
            ("+", [v1; v2]) -> c (VInt (exInt v1 + exInt v2))))
    | If (e1, e2, e3) ->
        eval e1 env (function v1 ->
          if exInt v1 != 0 then 
            eval e2 env c
          else 
            eval e3 env c)
    | Ident (x) -> c (lookup x env)
    | Let (x, e1, e2) ->
        eval e1 env (function v1 ->
          eval e2 (extend env x v1) c)
    | Function (x0, xs, e) ->
        c (VFun (function vs ->
          eval e (extends env xs vs)))
    | Apply (e0, es) ->
        eval e0 env (function v0 ->
          evals es env (function vs -> (exFun v0) vs c))
    | Raise (e) ->
        eval e env (function v -> raise (VException v))
    | Try (e0, x, e1) -> (*not correct*)
       (try eval e0 env c with
         VException v -> eval e1 (extend env x v) c)
    | Var (x, e1, e2) ->
        eval e1 env (function v1 ->
          eval e2 (extend env x (VRef (ref v1))) c)
    | Assign (x, e) ->
        eval e env (function v ->
          (exRef (lookup x env)) := v ; c (VUnit ()))

and evals es env c =
  match es with
      [] -> c []
    | e :: es ->
        eval e env (function v ->
          evals es env (function vs -> c (v :: vs)))

Wie man sieht, haben wir das Sequenzierungsproblem damit gelöst, allerdings mit dem Nachteil, für CPS sehr viele Funktionen definiert zu haben.

Exceptions

Im ursprünglichen Interpreter werden die Exceptions mit Hilfe der interpretierenden Sprache behandelt:

Code: naiver Interpreter Auszug

exception VException of value

let rec eval e env =
  match e with
      ...
    | Raise (e) -> raise (VException (eval e env))
    | Try (e0, x, e1) -> (
        try eval e0 env with
          VException v -> eval e1 (extend env x v))

Wie man am folgenden Beispiel sieht, kann man aus der ursprünglichen Version eine Transition nach CPS vornehmen, die keine Exceptions in der interpretierenden Sprache benötigt. Wir sehen uns dazu product, eine optimierte Version mit Exception und dann die CPS Version an:

<div style="padding-left:4px;" id="Beispiel: product">Beispiel: product

(* normal product *)
let rec product xs = 
  match xs with
      [] -> 1
    | x::xs' -> x * product xs'

(* optimized *)
let product xs = 
  let rec pr xs = 
    match xs with
        [] -> 1
      | x::xs' -> 
          if x = 0 then 
            raise Null
          else
            x * xs'
  in
  try pr with Null -> 0

(* CPS version *)
let product xs c = 
  let rec pr xs c'
    match xs with
        [] -> c' 1
      | x::xs' -> 
          if x = 0 then 
            c 0
          else 
            pr xs (function r -> c' (x * r))
  in
  pr xs c

</div>

Man beachte, dass CPS hier etwas waghalsig benutzt wird: Die Verwendung von c im then Teil sollte eigentlich nicht vorkommen, da nur die innerste Continuation zur Benutzung gedacht ist. Man kann deshalb eine weitere Version benutzen, die mit einer zusätzlichen Exception-Continuation die Exceptions systematisch behandelt:

Beispiel: Exception-Continuation

let product xs ex c = 
  let rec pr xs ex c = 
    match xs with
        [] -> c 1
      | x::xs' -> 
          if x = 0 then
            ex Null (* = raise *)
          else
            pr xs ex (function r -> c (x * r))
  in
  pr xs (function Null -> c 0) c
        (*      = try       *)

Closures

Während sich der letzte Abschnitt (auch) mit dem Umwandeln von Operationen in maschinennahe Instruktionen beschäftigt hat, geht es hier und im nächsten Abschnitt um die Behandlung der Funktionsaufrufe. Unser Ziel ist es, ein Programm so zu transformieren, dass es leicht in Maschinencode umgewandelt wird. Wenn wir uns noch einmal den naiven Interpreter ins Gedächtnis rufen, sehen wir, dass er zwar funktioniert, aber die Behandlung von Funktionen der interpretierenden Sprache überlässt:

Beispiel: naiver Interpreter Auszug

type value =
    VInt of int
  | VFun of (value list -> value)

let exInt (VInt i) = i
let exFun (VFun f) = f
...

let rec eval e env =
  match e with
      ...
    | Function (x0, xs, e) -> VFun (function vs -> eval e (extends env xs vs))
    | Apply (e0, es) -> (exFun (eval e0 env)) (evals es env)

Um die Funktionsbehandlung abstrahieren, führen wir deshalb Closures ein, die die Funktionsumsetzung übernehmen:

Code: Interpreter mit Closures

type ident = string

type value =
    VInt of int
  | VClosure of ident list * expr * value env

let rec eval e env =
  match e with
      ...
    | Function (x0, xs, e) -> VClosure(xs, e, env) 
    | Apply (e0, es) -> 
        let VClosure (xs', e', env') = eval e0 env in
        let vs = evals es env in
        eval e' (extends env' xs' vs)

Lambda-Lifting

Immer noch ist es unser Ziel, ein Programm so zu transformieren, dass es leicht in Maschinencode umgewandelt werden kann. Geschachtelte Funktionen sind diesem Ziel aber abträglich. Deshalb soll sich dieser Abschnitt mit der Aufhebung von Schachtelung beschäftigen: Wir wollen alle Funktionen zu top-level Funktionen machen. Das Verfahren hierzu nennt sich Lambda-Lifting. Wir beginnen mit einer Illustration des Problems und fahren mit Methoden zur Behebung fort.

Bemerkung: Lambda-Kalkül

Wie schon zu Beginn des Kapitels bemerkt, fehlt uns hier eigentlich der Lambda-Kalkül. Es reicht für uns hier zu wissen, dass z.B. die "addiere Zwei" Funktion f(x) = x + 2 im Lambda-Kalkül so ausgedrückt wird: λx. 2 + x, und die Anwendung f(3) so: (λx. 2 + x) 3.

Beispiel: top-level

let i = 5 in
letrec f = λx. f (i + i) in
f (i * i)

(* naive, errorenous top-level transformation: 
   obviously i would not be defined in the first line *)
letrec f = λx. f (i + i) in
let i = 5 in 
  f (i * i)

(* use i as parameter *)
letrec f = λi. λx. f i (i + i) in
let i = 5 in
  f i (i * i)

(* real transformation: first introduce variables that are free within the function *)
let i = 5 in
letrec f = λi. λx. f i (i + i) in
  f i (i * i)

Diese einfachen Umformungen reichen aber in der Regel nicht aus, um alle Probleme zu beseitigen, da Funktionen und ihre Parameter verschränkt sein können:

Beispiel: verschränkte Funktionen

let a = ... in
let b = ... in 
letrec f = λx. ... a ... g x
       g = λx. ... b ... f x
in 
f 42

(* transformed once by the previous mechanism this yields: *)
let a = ... in
let b = ... in 
letrec f = λa. λx. ... a ... g b x
       g = λb. λx. ... b ... f a x
in 
f a 42

(* as we can see, this is wrong: the functions have gotten their own free variables 
   as parameters, but at the same time new parameters are introduced for other 
   functions, creating new free variables within the first function. An additional 
   pass of the transformation yields a satisfying result: *)
let a = ... in
let b = ... in 
letrec f = λb. λa. λx. ... a ... g a b x
       g = λa. λb. λx. ... b ... f b a x
in 
f b a 42

Mit dem mehrfachen Transformieren, wie es im obigen Beispiel gezeigt wird, kann man also die Funktionen von freien Variablen befreien. Allerdings hat dieser naive, sukzessive Algorithmus kubische Laufzeit. Tatsächlich verwendet man deshalb folgenden Algorithmus:

Algorithmus

Vorbereitungsschritt:
- Benenne alle lokalen Definitionen so um, dass die Bezeichner programmweit eindeutig sind.
- Alle Ausdrucksfunktionen erhalten einen eindeutigen Namen: function x -> e wird zu letrec f = function x -> e in f.
Durchlaufe rekursiv das Programm mit Parameter $F$ , der Menge der bereits bekannten, definierten Funktionen (zu Beginn ist $F$ leer, beziehungsweise enthält alle vordefinierten Funktionen):

Ablauf: Lambda-Lifting

Angenommen das Programm hat dieses Format:

$\begin{array}{lrl} letrec & f_1 & = \lambda{x. e_1} \\ & & \vdots \\ & f_n & = \lambda{x. e_n} \\ in\ e \end{array}$

Dann sei $f v (λ x . e)$ die Menge der freien Variablen in $λ x . e$ und $\lbrace\overline{y}\rbrace = \bigcup_{1 \leqslant i \leqslant n} fv(\lambda{x}. e_i) \ F'$ die Menge der freien Variablen in den "top-most" Funktionen, wobei $F' = F \cup \lbrace f_1, \ldots, f_n \rbrace$ ( $\langle\overline{y}\rangle$ wird hier als Parametervektor benutzt). Dann wird das Programm folgendermassen umgeformt, wobei $$$ die normale Funktionsanwendung bezeichnet (für später markiert):

$\begin{array}{lrl} letrec & f_1 & = \lambda^$\langle\overline{y}\rangle. \lambda{x}. e_1[f_i \mapsto f_i$\langle\overline{y}\rangle]\\ & & \vdots \\ & f_n & = \lambda^$\langle\overline{y}\rangle. \lambda{x}. e_n[f_i \mapsto f_i$\langle\overline{y}\rangle]\\ in\ e [f_i \mapsto f_i$\langle\overline{y}\rangle] \end{array}$

Nach diesem Durchlauf verarbeitet man dann $e, e_1, \ldots, e_n$ rekursiv mit $F = F'$ . Ausserdem nimmt man vorher eine Aufspaltung der letrecs in stark verbundene Komponenten vor, da ansonsten zu viele Variablen in $\langle\overline{y}\rangle$ sind, was ineffizient ist.

Der Weg zum Maschinencode

In diesem Abschnitt beschäftigen wir uns mit der weiteren Umformung des Codes, so dass er besser in Maschinencode gewandelt werden kann. Dazu werden drei Zwischenschritte vorgenommen:

Alle Zwischenergebnisse werden benannt.
Die Reihenfolge wird explizit gemacht.
Der Kontrollfluss wird explizit gemacht.

Wir beginnen mit der Programmrepräsentation, Programme sind jetzt rekursive Programmschemata:

Definition: Programmschema

$\begin{array}{lcl} \langle\mbox{schema}\rangle & ::= & \langle\mbox{def}\rangle^* \langle\mbox{exp}'\rangle \\ \langle\mbox{def}\rangle & ::= & \langle\mbox{fname}\rangle = \lambda^$\langle\mbox{var}\rangle. \lambda\langle\mbox{var}\rangle. \langle\mbox{exp}'\rangle \\ \langle\mbox{exp}'\rangle & ::= & \langle\mbox{var}\rangle \\ & | & \langle\mbox{fname}\rangle$\langle\mbox{exp}'\rangle \\ & | & \langle\mbox{const}\rangle \\ & | & \langle\mbox{pure}\rangle \langle\mbox{exp}'\rangle \ldots \langle\mbox{exp}'\rangle \\ & | & \langle\mbox{oper}\rangle \langle\mbox{exp}'\rangle \ldots \langle\mbox{exp}'\rangle \\ & | & (\langle\mbox{exp}'\rangle \langle\mbox{exp}'\rangle) \\ & | & \left \langle \langle\mbox{exp}'\rangle \ldots \langle\mbox{exp}'\rangle \right \rangle \\ & | & let\ \langle\mbox{var}\rangle = \langle\mbox{exp}'\rangle\ in\ \langle\mbox{exp}'\rangle \\ & | & let\ \left \langle \langle\mbox{var}\rangle \ldots \langle\mbox{var}\rangle \right \rangle = \langle\mbox{exp}'\rangle\ in\ \langle\mbox{exp}'\rangle \\ & | & if\ \langle\mbox{exp}'\rangle\ then\ \langle\mbox{exp}'\rangle\ else\ \langle\mbox{exp}'\rangle \end{array}$

Man beachte, dass

die Deklaration von def Funktionen behandelt, die vom Lambda-Lifting kommen,
im let Guard Variablen gebunden und vor allem ihre Reihenfolge festgelegt wird
der Anfang des let Guard (let <var> = <exp'>) als Header bezeichnet wird
<pure> Operatoren ohne Seiteneffekte beschreibt (zum Beispiel arithmetische/logische Opertatoren)
<oper> zum Beispiel für Interrupts genutzt wird.

Verfahren: Entfernen der Vektoren vom Lambda-Lifting

Man entfernt die Vektoren vom Lambda-Lifting mit einer einfachen Umformung:

$\lambda^$\langle y_1,\ldots, y_m\rangle.\ \lambda{x}.\ e \Rightarrow \lambda^$z.\ \lambda x.\ let\ \langle y_1 \ldots y_m \rangle = z\ in\ e$

Notation: Schemata

In den folgenden Abschnitten gilt diese Notation: $x, x_i \in \langle \mbox{var}\rangle$ , $f \in \langle\mbox{fname}\rangle$ , $p \in \langle \mbox{pure} \rangle$ , $o \in \langle\mbox{oper}\rangle$ , $e, e' ,e_i \in \langle\mbox{exp}'\rangle$ , $c \in \langle\mbox{const}\rangle$ .

Wir kommen nun zum ersten Zwischenschritt, dem Benennen der Zwischenergebnisse:

Benennen der Zwischenergebnisse

Unser Ziel beim Benennen der Zwischenergebnisse ist es, allen Werten, die in Registern gespeichert werden müssen, einen Namen zu geben. Wir bedienen uns dabei einer Transformationsfunktion $\mathcal{W}$ :

Definition: $\mathcal{W}$

$\mathcal{W}^b[e] = \begin{cases}let\ x = e\ in\ x & b = true \\ e & b = false \end{cases}$

Der Wert $b$ wird hierbei aus Kontextinformationen gewonnen, die vier Werte annehmen können:

$v$ - Kontext verlangt Variable
$f$ - Kontext verlangt Funktion
$l$ - Kontext ist let-Header
$t$ - Kontext hat keine Anforderungen

Mit Hilfe dieser Funktion können wir nun gegebene Programmabschnitte transformieren:

Definition: Tranformation für explizite Zwischenschritte

$q \in \mbox{Kontextinformationen}$

$\begin{array}{ll} [v]^q & = v \\ {}[f $ e]^q & = \mathcal{W}^{q \neq f} [f $ [e]^v] \\ {}[c]^q & = \mathcal{W}^{q = v} [c] \\ {}[p\ e_1 \ldots e_m]^q & = \mathcal{W}^{q = v} [p\ [e_1]^t \ldots [e_m]^t] \\ {}[o\ e_1 \ldots e_m]^q & = \mathcal{W}^{q \neq l} [o\ [e_1]^v \ldots [e_m]^v] \\ {}[(e\ e')]^q & = \mathcal{W}^{q \neq l} [([e]^f\ [e']^v)] \\ {}[\langle e_1 \ldots e_m \rangle]^q & = \mathcal{W}^{q \neq l} [\langle [e_1]^v \ldots [e_m]^v\rangle] \\ {}[let\ x = e\ in\ e']^q & = let\ x = [e]^l\ in\ [e']^q \\ {}[let\ \langle x_1 \ldots x_m \rangle = e\ in\ e']^q & = let\ \langle x_1 \ldots x_m \rangle = [e]^l\ in\ [e']^q \\ {}[if\ e_1\ then\ e_2\ else\ e_3]^q & = \mathcal{W}^{q \neq l} [if\ [e_1]^v\ then\ [e_2]^v\ else\ [e_3]^v] \end{array}$

Um die Idee zu verdeutlichen, folgt ein Beispiel, in dem die Funktion power aus ihrer Originalfassung bis zu benannten Zwischenschritten umgeformt wird.

Beispiel: power

Originalprogramm:

$power\ x =$

$letrec\ g = \lambda{n}.\ if \ n = 0\ then\ 1\ else\ x * g (n-1)\ in$

$\ g$

Nach Lambda-Lifting:

$g = \lambda^$z.\ \lambda{n}.\ let\ \langle x \rangle = z\ in$

$if\ n = 0\ then\ 1\ else\ x * g$z (n-1)$

$power = \lambda^$z.\ \lambda{x}.\ g$\langle x \rangle$

power mit benannten Zwischenergebnissen:

$power = \lambda^$z.\ \lambda{x}.\ let\ x_1 = g$(let\ x_2 = \langle{x}\rangle\ in\ x_2)\ in\ x_1$

$g = \lambda^$w.\ \lambda{n}.\ let\ \langle x \rangle = z\ in$

$let\ x_2 =$

$if\ (let\ x_3 = (n=0)\ in\ x_3)\ then$

$let\ x_4 = 1\ in\ x_4$

$\,\!else$

$let\ x_5 = x * ($

$let\ x_6 = g$z (let\ x_7 = n-1\ in\ x_7)$

$in\ x_6)$

$in\ x_5$

$in\ x_2$

Explizite Reihenfolge

In dem Code, der aus dem Benennen der Zwischenergebnisse folgt, finden sich sehr viele verschachtelte let Blöcke. Um die Reihenfolge der Ausführung von Termen explizit zu machen, werden diese "nach oben gezogen", oder "geplättet". Das Verfahren nennt sich let flattening, es verwendet lokale Transformationsregeln, die so lange angewendet werden, bis alle Möglichkeiten der Anwendung erschöpft sind.

Wir betrachten dazu folgende Werte:

Definition: let flattening Werte

$\begin{array}{lcl} \langle\mbox{triv}\rangle & ::= & \langle \mbox{var} \rangle \\ & | & \langle \mbox{fname} \rangle $ \langle \mbox{var} \rangle \\ & | & \langle \mbox{const} \rangle \\ & | & \langle \mbox{pure} \rangle \langle \mbox{triv} \rangle \ldots \langle\mbox{triv} \rangle \end{array}$

Lasse $v$ über die Werte von $\langle \mbox{triv}\rangle$ laufen. Mit diesen Werten können wir nun die Transformationsregeln angeben:

Definition: let flattening Transformation

Alle hier angegebenen Regeln für $let\ x = e\ in \ldots$ können auch auf $let\ \langle x_1 \ldots x_m \rangle = e\ in \ldots$ angewandt werden. Wir können ausserdem davon ausgehen, dass nie freie Variablen überschrieben werden, da im vorherigen Schritt jede Variable einen eindeutigen Bezeichner erhalten hat.

$\begin{array}{ll} f $(let\ x = e\ in\ e') & \mapsto let\ x = e\ in\ f $ e' \\ p\ v_1 \ldots v_i\ (let\ x = e\ in\ e')\ e_1 \ldots e_k & \mapsto let\ x = e\ in\ p\ v_1 \ldots v_i\ e'\ e_1 \ldots e_k \\ o\ v_1 \ldots v_i\ (let\ x = e\ in\ e')\ e_1 \ldots e_k & \mapsto let\ x = e\ in\ o\ v_1 \ldots v_i\ e'\ e_1 \ldots e_k \\ \langle v_1 \ldots v_i\ (let\ x = e\ in\ e')\ e_1 \ldots e_k \rangle & \mapsto let\ x = e\ in\ \langle v_1 \ldots v_i\ e'\ e_1 \ldots e_k \rangle \\ (let\ x = e_1\ in\ e_2)\ e_3 & \mapsto let\ x = e_1\ in\ (e_1\ e_2) \\ v\ (let\ x = e\ in\ e') & \mapsto let\ x = e\ in\ (v\ e') \\ let\ x_1 = (let\ x_2 = e_1\ in\ e_2)\ in\ e_3 & \mapsto let\ x_2 = e_1\ in\ let\ x_1 = e_2\ in\ e_3 \\ if\ (let\ x = e_1\ in\ e_2)\ then\ e_3\ else\ e_4 & \mapsto let\ x = e_1\ in\ if\ e_2\ then\ e_3\ else\ e_4 \end{array}$

<div style="padding-left:4px;" id="Beispiel: power mit let flattening">Beispiel: power mit let flattening

$power = \lambda^$t.\ \lambda x.\ let\ x_2 = \langle x \rangle\ in$

$let\ x_1 = g$x_2\ in$

$\,\!x_1$

$g = \lambda^$z.\ \lambda n.\ let \langle x \rangle = z\ in$

$let\ x_3 = (n=0)\ in$

$let\ x_2 =$

$if\ x_3\ then$

$let\ x_4 = 1\ in\ x_4$

$\,\!else$

$let\ x_7 = n - 1\ in$

$let\ x_6 = (g$z)\ x_7\ in$

$let\ x_5 = x * x_6\ in$

$\,\!x_5$

$\,\!x_2$

</div>

Expliziter Kontrollfluss

In diesem letzten Zwischenschritt auf dem Weg zum Maschinencode wollen wir den Kontrollfluss explizit machen. Hier geht es um die Kontrolltransitionen, die am Ende von Funktionen ("return") und in Konditionsblöcken ("if-then-else") entstehen. Unser Ziel ist es, diese Kontrolltransitionen im Code explizit zu machen, und insbesondere zu zeigen, wohin wir springen, nachdem ein Block beendet wurde.

Wir beginnen dazu mit der Einführung einer neuen Programmbeschreibung, um die Unterscheidung von Ausdrücken in triviale und komplizierte (serious) zu ermöglichen.

Definition: Kontrollfluss Programmschema

$\begin{array}{lcl} \langle\mbox{triv}\rangle & ::= & \langle \mbox{var} \rangle \\ & | & \langle \mbox{fname} \rangle $ \langle \mbox{var} \rangle \\ & | & \langle \mbox{const} \rangle \\ & | & \langle \mbox{pure} \rangle \langle \mbox{triv} \rangle \ldots \langle\mbox{triv} \rangle \\ \\ \langle\mbox{hdr}\rangle & ::= & \langle \mbox{triv} \rangle \\ & | & \langle \mbox{oper} \rangle \langle \mbox{var}\rangle \ldots \langle\mbox{var} \rangle \\ & | & \langle \langle \mbox{var} \rangle \ldots \langle\mbox{var} \rangle \rangle \\ & | & (\langle \mbox{triv} \rangle \langle\mbox{var} \rangle) \\ \\ \langle\mbox{ser}\rangle & ::= & return\ \langle \mbox{var} \rangle \\ & | & let\ \langle \mbox{vars} \rangle = \langle \mbox{hdr}\rangle\ in\ \langle\mbox{ser} \rangle \\ & | & (\langle \mbox{triv} \rangle \langle\mbox{var} \rangle) \\ & | & if\ \langle \mbox{var} \rangle\ then\ \langle \mbox{ser}\rangle\ else\ \langle\mbox{ser} \rangle \\ & | & letcont\ k$\langle \mbox{vars} \rangle = \lambda\langle \mbox{var}\rangle.\ \langle\mbox{ser} \rangle\ in\ \langle\mbox{ser} \rangle \\ & | & yield\ k\ \langle \mbox{var} \rangle \end{array}$

$\langle\mbox{equation}\rangle ::= \langle \mbox{fname} \rangle = \lambda^$\langle \mbox{var} \rangle.\ \lambda \langle \mbox{var} \rangle.\ \langle \mbox{ser} \rangle$

$\langle\mbox{vars}\rangle ::= \langle \langle \mbox{var} \rangle^*\rangle$

Der Ausdruck $letcont\ k$\langle x_1 \ldots x_n\rangle = \lambda x.\ s_1\ in\ s_2$ dient dazu, eine Zieladresse für den Sprung aus einem Konditionalblock festzulegen. Die Funktion $k$ repräsentiert dieses Ziel und wird mit dem $y i e l d$ Ausdruck ausgeführt. Das Verhalten dieser Transformation (Definition weiter unten) lässt sich am besten an unserem power Beispiel betrachten:

Beispiel: expliziter Kontrollfluss für power

$power = \lambda^$t.\ \lambda x.\ let\ x_2 = \langle x \rangle\ in$

$let\ x_1 = g$x_2\ in$

$\,\!return\ x_1$

$g = \lambda^$z.\ \lambda n.\ let \langle x \rangle = z\ in$

$let\ x_3 = (n=0)\ in$

$letcont\ k$x = \lambda x_2.\ return\ x_2\ in$

$if\ x_3\ then$

$let\ x_4 = 1\ in\ yield\ k\ x_4$

$\,\!else$

$let\ x_7 = n - 1\ in$

$let\ x_6 = (g$z)\ x_7\ in$

$let\ x_5 = x * x_6\ in$

$\,\!yield\ k\ x_5$

Wie man hier sieht, ist $k$ nichts anderes als eine continuation, wie wir sie schon bei der Benutzung von von Continuation-Passing Style kennen gelernt haben. Um ein Programm in die oben dargestellte Form umzuwandeln, können wir die Funktion $\mathcal{R}_k[\cdot]$ benutzen. $k$ ist hier entweder 0, um eine top-level continuation anzuzeigen (also ein "return") oder eine von $l e t c o n t$ eingeführte continuation.

Definition: $\mathcal{R}_k[\cdot]$

$\begin{array}{ll} \mathcal{R}[f = \lambda^$z.\ \lambda x.\ e] & = f = \lambda^$z.\ \lambda x.\ \mathcal{R}_0[e] \\ \mathcal{R}_k[x] & = \begin{cases} return\ x & k = 0 \\ yield\ k\ x & \mbox{sonst} \end{cases} \\ \mathcal{R}_k[let\ x_1 =\ if\ x_2\ then\ e_1\ else\ e_2\ in\ e_3] & = letcont\ k'$\langle fv(e_3) \lbrace x \rbrace \rangle = \lambda x.\ \mathcal{R}_k[e]\ in\ if\ x_2\ then\ \mathcal{R}_{k'}[e_1]\ else\ \mathcal{R}_{k'}[e_2] \\ \mathcal{R}_k[let\ \langle x_1 \ldots x_n \rangle = e \ in\ e'] & = let\ \langle x_1 \ldots x_n \rangle = e \ in\ \mathcal{R}_k[e'] \end{array}$

Nachdem wir diese Definition erhalten haben, können wir noch einmal einen genaueren Blick auf das Beispiel von eben werfen: Man kann sich fragen, warum wir überhaupt die continuation $\lambda x_2.\ return\ x_2$ eingeführt haben. Die Ineffizienz, die daruch entsteht, dass wir erst aus dem Konditionalblock und dann aus der Funktion springen, lässt sich durch ein Ersetzen der $yield\ k\ s$ durch $r e t u r n s$ erreichen:

<div style="padding-left:4px;" id="Beispiel: power mit effizienterem Kontrollfluss">Beispiel: power mit effizienterem Kontrollfluss

$g = \lambda^$z.\ \lambda n.\ let \langle x \rangle = z\ in$

$let\ x_3 = (n=0)\ in$

$if\ x_3\ then$

$let\ x_4 = 1\ in\ return\ x_4$

$\,\!else$

$let\ x_7 = n - 1\ in$

$let\ x_6 = (g$z)\ x_7\ in$

$let\ x_5 = x * x_6\ in$

$\,\!return\ x_5$

</div>

Während sich Funktionen wie power mit bisherigen Methoden gut optimieren lassen, gibt es noch einige Dinge, die man verbessern kann. Folgende Funktion down zeigt ein Optimierungsproblem mit Endrekursion auf, selbst nachdem sie mit den bei power genutzten Methoden verbessert wurde:

<div style="padding-left:4px;" id="Beispiel: down">Beispiel: down

down n = if n=0 then 1 else down (n-1)

$down = \lambda^$z.\ \lambda n.$

$let\ x_1 = (n=0)\ in$

$if\ x_1\ then$

$let\ x_2 = 1\ in$

$return\ x_2$

$\,\!else$

$let\ x_3 = (n-1)\ in$

$let\ x_4 = down$z\ x_3\ in$

$return\ x_4$

</div>

Das Auffangen und sofortige Zurückgeben des Aufrufs von down ist nicht besonders effizient. Es ist aber mit gegebenen Mitteln möglich, die Funktion umzuformen, so dass sie korrekte Endrekursion benutzt (hierbei springt die aufgerufene Funktion nicht zum unmittelbaren Aufrufenden zurück, sondern zum letzten Aufrufenden ohne Endrekursion):

<div style="padding-left:4px;" id="Beispiel: down mit korrekter Endrekursion">Beispiel: down mit korrekter Endrekursion

$down = \lambda^$z.\ \lambda n.$

$let\ x_1 = (n=0)\ in$

$if\ x_1\ then$

$let\ x_2 = 1\ in$

$return\ x_2$

$\,\!else$

$let\ x_3 = (n-1)\ in$

$down$z\ x_3$

</div>

Implementation

Die in den vergangenen Abschnitten behandelten Zwischenschritte auf dem Weg zum Maschinencode können in einem einzigen Durchlauf implementiert werden (one pass transformation). Der entsprechende Algorithmus wird hier in Form von OCaml Code dargestellt.

Zu Beginn stellen wir die Typen vor, die von unseren Funktionen genutzt werden:

Code: One Pass Tranformation Typen

(* source calculus *)
type exp =
    Var of ident
  | Const of ident
  | Pure of ident * exp list
  | Oper of ident * exp list
  | Vector of exp list              (* <exp, ..., exp> *)
  | App of exp * exp
  | Let of ident list * exp * exp
  | If of exp * exp * exp
  | Close of exp * exp              (* f$z *)

type definition =
  ident * ident list * ident * exp  (* f = λ^$<exp,...exp>. λx. e *)

type scheme =
  definition list * exp


(* target calculus *)
type trivial =
    TVar of ident
  | TConst of ident
  | TPure of ident * trivial list
  | TClose of ident * ident

type header =
    HTriv of trivial
  | HOper of ident * ident list
  | HApp3 of ident * ident * ident
  | HVect of ident list

type serious =
    SReturn of ident
  | SApp3 of ident * ident * ident         (* tail call to function  f$z (y) *)
  | SLet of ident list * header * serious  (* SLet(...HApp3...) - ordinary call to function *)
  | SIf of ident * serious * serious
  | SLetCont of kident * ident list * ident * serious * serious
  | SYield of kident * ident

type xDefinition =
  ident * ident * ident * serious


(* identifiers, including functions to create fresh names which aren't yet in use *)
type ident =
    StrId of string
  | NumId of string * int

type kident =
  ident

let fresh_counter =
  ref 0

let fresh_int () =
  begin
    fresh_counter := !fresh_counter + 1;
    !fresh_counter
  end

let fresh prefix =
  NumId (prefix, fresh_int ())

let freshL ps =
  List.map fresh ps

type xScheme =
  xDefinition list * serious

Wir kommen nun zu dem Hauptteil der Transformation, der Funktion toSerious, die Ausdrücke vom Typ exp in komplizierte (serious) Ausdrücke übersetzt.

<div style="padding-left:4px;" id="Code: toSerious">Code: toSerious

(* toSerious : (string * string) list -> exp -> (ident −> serious) −> serious *)
(* subst is a variable renaming, e an expression to be transformed 
   and c a continuation *)

let rec toSerious subst e c =
  match e with
      Var i ->
        c (rename i subst)
    | Const p ->
        let fr = fresh "t" in
        SLet ([fr], HTriv (TConst p), c fr)
    | Pure (p, es) ->
        toTrivialL subst es
          (fun ts ->
            let fr = fresh "t" in
            SLet ([fr], HTriv (TPure (p, ts)), c fr))
    | Oper (o, es) ->
        let fr = fresh "t" in
        toSeriousL subst es
          (fun is ->
            SLet ([fr], HOper (o, is), c fr))
    | App (Close (e1, e2), e) ->
        toSerious subst e1
          (fun x1 ->
            toSerious subst e2
              (fun x2 ->
                toSerious subst e
                  (fun x3 ->
                    let fr = fresh "t" in
                    SLet ([fr], HApp3 (x1, x2, x3), c fr))))
    | App (f, e) ->
        toSerious subst f
          (fun ff ->
            toSerious subst e
              (fun ee ->
                 let [frf; frc; fr] = freshL ["t"; "t"; "t"] in
                 SLet ([frf; frc], HTriv (TVar ff),
                 SLet ([fr], HApp3 (frf, frc, ee), c fr))))
    | Let ([x], e1, e2) ->
        toSerious subst e1
         (fun xx ->
           toSerious ((x, xx) :: subst) e2 c)
    | Let (xs, e1, e2) ->
        toSerious subst e1
          (fun xx ->
            SLet (xs, HTriv (TVar (xx)), toSerious subst e2 c))
    | If (e1, e2, e3) ->
        toSerious subst e1
          (fun x1 ->
            let [kk; xx] = freshL ["k"; "t"] in
            let body = c xx in
            SLetCont
              (kk, remove xx (free_serious body), xx, body,
               SIf
                 (x1,
                   toSerious subst e2 (fun i ® SYield (kk, i)),
                   toSerious subst e3 (fun i ® SYield (kk, i)))))
    | Close (e1, e2) ->
        toSerious subst e1
          (fun x1 ->
             toSerious subst e2
               (fun x2 ->
                 let fr = fresh "t" in
                 SLet ([fr], HTriv (TClose (x1, x2)), c fr)))
    | Vector (es) ->
        toSeriousL subst es
          (fun xs ->
            let fr = fresh "t" in
            SLet ([fr], HVect( xs), c fr))

</div>

Wir brauchen noch die Funktion toTrivial - sie hat fast die gleiche Signatur wie toSerious, der einzige Unterschied ist das Argument der continuation, die einen trivialen Term anstelle eines Bezeichners erwartet. Die Funktion inspiziert alle Fälle, in denen sie einen trivialen Term konstruieren kann und gibt sonst an toSerious weiter.

<div style="padding-left:4px;" id="Code: toTrivial">Code: toTrivial

(* toTrivial : (string * string) list -> exp -> (trivial −> serious) −> serious *)
and toTrivial subst e c =
  match e with
      Var i ->
        c (TVar (rename i subst))
    | Const p ->
        c (TConst p)
    | Pure (p, es) ->
        toTrivialL subst es
          (fun ts ->
            c (TPure (p, ts)))
    | _ ->
        toSerious subst e
          (fun xx ->
            c (TVar xx))

</div>

Die Implementationen von toTrivialL und toSeriousL sind einfach und finden sich in Trafo.pdf. Des weiteren übernimmt der oben angegebene Algorithmus noch nicht die Auflösung der Endrekursion - dazu benötigen wir eine modifizierte Version der toSerious Funktion, die nur die top-level Funktionen bearbeitet und auf Seite 91/15 in Coco-Lambda-Trans.pdf besprochen wird.

Compilerbau/Kapitel 4: Zwischensprachen

Aus Halloserv Wiki

Inhaltsverzeichnis

Naiver Interpreter

Continuation-Passing Style

Exceptions

Closures

Lambda-Lifting

Algorithmus

Der Weg zum Maschinencode

Benennen der Zwischenergebnisse

Explizite Reihenfolge

Expliziter Kontrollfluss

Implementation

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Werkzeuge