Reeks 8 : Compilatie

Deze oefeningenreeks behandelt de compiler uit hoofdstuk 5.5 van Structure and Interpretation of Computer Programs. De code die je nodig hebt om deze oefeningen te maken vind je in dit zip-bestand: "compiler.zip". Een overzicht van de inhoud vind je in "overzicht.pdf".

1 Praktisch

Download het bestand compiler.zip van de oefeningenwebsite. Je kan de compiler starten door het bestand load-eceval-compiler.scm te evalueren. Deze laadt de compiler, de registermachinesimulator, de nodige functies voor lexicale analyse uit de meta-circulaire evaluator en ook enkele handige hulpfuncties die hieronder staan uitgelegd.

• Compileren van Scheme code en de registermachine instructies bezichtigen:

  > (pp (compile        '(define (fac n)           (if (= n 0)               1               (* n (fac (- n 1)))))        'val        'next))

  (assign val (op make-compiled-procedure) (label entry1) (reg env))     (goto (label after-lambda2)) entry1     (assign env (op compiled-procedure-env) (reg proc))     (assign env (op extend-environment) (const (n)) (reg argl) (reg env))     (save continue)     (save env)     (assign proc (op lookup-variable-value) (const =) (reg env))     (assign val (const 0))     (assign argl (op list) (reg val))     (assign val (op lookup-variable-value) (const n) (reg env))     (assign argl (op cons) (reg val) (reg argl))     (test (op primitive-procedure?) (reg proc))     (branch (label primitive-branch6)) compiled-branch7     (assign continue (label after-call8))     (assign val (op compiled-procedure-entry) (reg proc))     (goto (reg val)) primitive-branch6     (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) after-call8     (restore env)     (restore continue)     (test (op false?) (reg val))     (branch (label false-branch4)) true-branch3     (assign val (const 1))     (goto (reg continue)) false-branch4     (assign proc (op lookup-variable-value) (const *) (reg env))     (save continue)     (save proc)     (save env)     (assign proc (op lookup-variable-value) (const fac) (reg env))     (save proc)     (assign proc (op lookup-variable-value) (const -) (reg env))     (assign val (const 1))     (assign argl (op list) (reg val))     (assign val (op lookup-variable-value) (const n) (reg env))     (assign argl (op cons) (reg val) (reg argl))     (test (op primitive-procedure?) (reg proc))     (branch (label primitive-branch9)) compiled-branch10     (assign continue (label after-call11))     (assign val (op compiled-procedure-entry) (reg proc))     (goto (reg val)) primitive-branch9     (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) after-call11     (assign argl (op list) (reg val))     (restore proc)     (test (op primitive-procedure?) (reg proc))     (branch (label primitive-branch12)) compiled-branch13     (assign continue (label after-call14))     (assign val (op compiled-procedure-entry) (reg proc))     (goto (reg val)) primitive-branch12     (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) after-call14     (assign argl (op list) (reg val))     (restore env)     (assign val (op lookup-variable-value) (const n) (reg env))     (assign argl (op cons) (reg val) (reg argl))     (restore proc)     (restore continue)     (test (op primitive-procedure?) (reg proc))     (branch (label primitive-branch15)) compiled-branch16     (assign val (op compiled-procedure-entry) (reg proc))     (goto (reg val)) primitive-branch15     (assign val (op apply-primitive-procedure) (reg proc) (reg argl))     (goto (reg continue)) after-call17 after-if5 after-lambda2     (perform (op define-variable!) (const fac) (reg val) (reg env))     (assign val (const ok)) ------------------------

• Compileren van Scheme code en de registermachinecode uitvoeren in simulator:

  (compile-and-go '(define (fac n)

  (if (= n 0) 1

  (* n (fac (- n 1))))))

2 Decompilatie

Decompilatie is het process waarbij je, beginnend van een stuk gecompileerde code, probeert te reconstrueren wat de originele code was die aan compile werd meegegeven. Neem bijvoorbeeld het volgende stuk output van de compiler.

(assign proc (op lookup-variable-value) (const +) (reg env))

(assign val (const 2))

(assign argl (op list) (reg val))

(assign val (const 1))

(assign argl (op cons) (reg val) (reg argl))

(test (op primitive-procedure?) (reg proc))

(branch (label primitive-branch1))

compiled-branch2

(assign continue (label after-call3))

(assign val (op compiled-procedure-entry) (reg proc))

(goto (reg val))

primitive-branch1

(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

after-call3

Je ziet dat de waarde van + wordt opgezocht en het resultaat in het proc register gestoken. Dan worden 2 en 1 in het argl register gestoken. Achteraf splitst de code aan de hand van een branch statement. Dit hangt af van de waarde van +: is het een primitive of een compiled procedure? Dit zal pas geweten worden bij het uitvoeren van de code, daarom dat beide opties voorkomen in de gecompileerde code. Je ziet dat het hier gaat om een oproep van (+ 1 2).

Je kan ook terugvinden wat de target van de compile oproep was. Voor target, bedenk waar het resultaat van de oproep (+ 1 2) geschreven zal worden. Van de compiled procedure weet je dat diens resultaat in het val register zal gestoken worden. Bij de primitive zie je dat het resultaat van apply-primitive-procedure eveneens in val belandt.

In het geval van de linkage tenslotte, moet je bedenken wat er gebeurt nadat het stuk gecompileerde code is uitgevoerd. In dit voorbeeld moet je dus wederom kijken wat er op het einde van de procedure gebeurt. In het geval van een gecompileerde procedure, weet je dat die na uitvoering springt naar de waarde van het continue register. Die wordt hier op after-call3 gezet. In het geval van de primitive procedure, zie je dat er na het uitvoeren gewoon wordt verdergegaan. In beide gevallen belandt de uitvoering bij het volgende label na het uitvoeren van de procedure. Met andere woorden, de linkage was 'next.

De volledige compile oproep zag er zo uit:

> (pp (compile         '(+ 1 2)         'val         'next))

(assign proc (op lookup-variable-value) (const +) (reg env))     (assign val (const 2))     (assign argl (op list) (reg val))     (assign val (const 1))     (assign argl (op cons) (reg val) (reg argl))     (test (op primitive-procedure?) (reg proc))     (branch (label primitive-branch18)) compiled-branch19     (assign continue (label after-call20))     (assign val (op compiled-procedure-entry) (reg proc))     (goto (reg val)) primitive-branch18     (assign val (op apply-primitive-procedure) (reg proc) (reg argl)) after-call20 ------------------------

Decompileer nu zelf de volgende outputs en reconstrueer de verschillende exp, target en linkage die aan compile werden meegegeven. Indien je iets niet herkent, probeer dan zelf wat input aan compile te geven en te analyseren wat eruit komt. Om de oefeningen wat interessanter te maken, zijn de labels onherkenbaar gemaakt.

2.1 Oefening a

(assign val (const 100))

(perform (op define-variable!) (const oef-a) (reg val) (reg env))

(assign resultaat (const ok))

(assign resultaat (op lookup-variable-value) (const oef-a) (reg env))

2.2 Oefening b

(save continue)

(assign proc (op lookup-variable-value) (const =) (reg env))

(save proc)

(assign proc (op lookup-variable-value) (const +) (reg env))

(assign val (const 2))

(assign argl (op list) (reg val))

(assign val (const 1))

(assign argl (op cons) (reg val) (reg argl))

(test (op primitive-procedure?) (reg proc))

(branch (label label2))

label1

(assign continue (label label3))

(assign val (op compiled-procedure-entry) (reg proc))

(goto (reg val))

label2

(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

label3

(assign argl (op list) (reg val))

(assign val (const 10))

(assign argl (op cons) (reg val) (reg argl))

(restore proc)

(test (op primitive-procedure?) (reg proc))

(branch (label label5))

label4

(assign continue (label label6))

(assign val (op compiled-procedure-entry) (reg proc))

(goto (reg val))

label5

(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

label6

(restore continue)

(test (op false?) (reg val))

(branch (label label8))

label7

(assign een-getal (const 100))

(goto (reg continue))

label8

(assign een-getal (const 200))

(goto (reg continue))

label9

2.3 Oefening c

(assign val (const 20))

(perform (op define-variable!) (const x) (reg val) (reg env))

(assign z (const ok))

(assign proc (op lookup-variable-value) (const >) (reg env))

(assign val (const 10))

(assign argl (op list) (reg val))

(assign val (op lookup-variable-value) (const x) (reg env))

(assign argl (op cons) (reg val) (reg argl))

(test (op primitive-procedure?) (reg proc))

(branch (label label-1))

label-2

(assign continue (label label-3))

(assign val (op compiled-procedure-entry) (reg proc))

(goto (reg val))

label-1

(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

label-3

(test (op false?) (reg val))

(branch (label label-4))

label-5

(assign z (const 5))

(goto (label label-6))

label-4

(assign z (const 15))

(goto (label label-6))

label-7

2.4 Oefening d

(assign val (op make-compiled-procedure) (label label1) (reg env))

(goto (label label17))

label1

(assign env (op compiled-procedure-env) (reg proc))

(assign env (op extend-environment) (const (n)) (reg argl) (reg env))

(save continue)

(save env)

(assign proc (op lookup-variable-value) (const <) (reg env))

(assign val (const 2))

(assign argl (op list) (reg val))

(assign val (op lookup-variable-value) (const n) (reg env))

(assign argl (op cons) (reg val) (reg argl))

(test (op primitive-procedure?) (reg proc))

(branch (label label3))

label2

(assign continue (label label4))

(assign val (op compiled-procedure-entry) (reg proc))

(goto (reg val))

label3

(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

label4

(restore env)

(restore continue)

(test (op false?) (reg val))

(branch (label label6))

label5

(assign val (const 1))

(goto (reg continue))

label6

(assign proc (op lookup-variable-value) (const *) (reg env))

(save continue)

(save proc)

(save env)

(assign proc (op lookup-variable-value) (const f) (reg env))

(save proc)

(assign proc (op lookup-variable-value) (const -) (reg env))

(assign val (const 1))

(assign argl (op list) (reg val))

(assign val (op lookup-variable-value) (const n) (reg env))

(assign argl (op cons) (reg val) (reg argl))

(test (op primitive-procedure?) (reg proc))

(branch (label label8))

label7

(assign continue (label label9))

(assign val (op compiled-procedure-entry) (reg proc))

(goto (reg val))

label8

(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

label9

(assign argl (op list) (reg val))

(restore proc)

(test (op primitive-procedure?) (reg proc))

(branch (label label11))

label10

(assign continue (label label12))

(assign val (op compiled-procedure-entry) (reg proc))

(goto (reg val))

label11

(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

label12

(assign argl (op list) (reg val))

(restore env)

(assign val (op lookup-variable-value) (const n) (reg env))

(assign argl (op cons) (reg val) (reg argl))

(restore proc)

(restore continue)

(test (op primitive-procedure?) (reg proc))

(branch (label label14))

label13

(assign val (op compiled-procedure-entry) (reg proc))

(goto (reg val))

label14

(assign val (op apply-primitive-procedure) (reg proc) (reg argl))

(goto (reg continue))

label15

label16

label17

(perform (op define-variable!) (const f) (reg val) (reg env))

(assign s (const ok))

(assign proc (op lookup-variable-value) (const f) (reg env))

(assign val (const 11))

(assign argl (op list) (reg val))

(test (op primitive-procedure?) (reg proc))

(branch (label label20))

label18

(assign continue (label label19))

(assign val (op compiled-procedure-entry) (reg proc))

(goto (reg val))

label19

(assign s (reg val))

(goto (label label21))

label20

(assign s (op apply-primitive-procedure) (reg proc) (reg argl))

label21

3 Oefening: Dynamische scope

Dit was een examenvraag in de eerste zit van 2018-2019.

De versie van de compiler die we in de les hebben gezien, zorgt ervoor dat de gecompileerde code lexicale scope gebruikt. Beschrijf welke aanpassingen je aan de compiler moet maken opdat dynamische scope gebruikt zou worden.

Hint die niet op het examen stond:

(compile-and-go

'(begin

(define n 100)

(define (f)

n)

(define (h)

(define n 200)

(f))

(h)))

Bij de lexicale geeft dit 100 als resultaat. Bij de dynamische geeft dit 200 als resultaat.

4 Oefening: Een efficiëntere compiler

Bekijk hoe momenteel primitieve functies zoals (+ a 5) gecompileerd worden naar registermachine-instructies. De gegenereerde registermachinecode kan efficiënter gemaakt worden. Dit wil zeggen: kortere code genereren die hetzelfde gedrag implementeert. In deze oefening gaan we deze efficiëntieverhoging realiseren voor de primitieven +, -, * en = door gebruik te maken van extra registers. M.a.w. we laten de ruimtecomplexiteit stijgen ten voordele van de tijdscomplexiteit. De bedoeling is om bij de primitieven +, -, * en = eerst alle subexpressies (dit zijn de argumenten) te compileren. Elk argument dient daarbij zijn resultaat weg te schrijven in de extra registers val0, val1, val2, etc. Merk op dat we vroeger slechts beschikten over één register om resultaten in weg te schrijven, namelijk val.

Onderneem daarvoor volgende stappen.

4.1 open-coded?

Implementeer een predikaat open-coded? dat applicaties met de primitieve procedures +, -, * en = onderschept. Breid de dispatching in de procedure compile uit.

4.2 spread-args

procedure (spread-args arg-exps call-code) → instruction-sequence?

arg-exps : list-of-scheme-args

call-code : instruction-sequence?

Hier een voorbeeldwerking van spread-args.

> (pp (spread-args '(1 2 3) (empty-instruction-sequence)))

(assign val0 (const 1))

(assign val1 (const 2))

(assign val2 (const 3))

> (pp (spread-args '(1 2 3)

(make-instruction-sequence

'(continue)

'()

'((goto (reg continue))))))

(assign val0 (const 1))

(assign val1 (const 2))

(assign val2 (const 3))

(goto (reg continue))

Enkele extra tips:

• Je gaat herhaaldelijk preserving oproepen. Een recursieve aanpak is hier het makkelijkst.

• Indien je niet meteen weet welke registers mee te geven aan preserving, gebruik dan gewoon even '(). Je kan dan een ietwat werkende functie krijgen.

• Je zal spread-args pas uitvoerig kunnen testen wanneer ook compile-open-coded geschreven is.

4.3 compile-open-coded

Schrijf nu de codegenerator compile-open-coded die applicaties met primitieven +, -, * en = efficiënt compileert door gebruik te maken van extra registers val0, val1, val2, etc. Maak daarbij gebruik van de procedure spread-args die je zopas geïmplementeerd hebt.

procedure (compile-open-coded exp target linkage) → instruction-sequence?

exp : scheme-expressie

target : register

linkage : next/return/label

4.4 Uitbreiding registermachinesimulator

Om je uitbreiding gemakkelijk te testen, kan je compile-and-go gebruiken. Breng hiertoe de nodige aanpassingen aan de configuratie van de registermachinesimulator (registers, operaties, ...).

4.5 Randgevallen

Deze randgevallen zullen je meer inzicht geven in wat je misschien nog aan moet passen aan jouw code. Probeer de ene werkende te krijgen voor naar de volgende te gaan.

(compile '(+ 1 (+ 2 3) 4) 'val 'next)

(compile-and-go

'(begin

(define (f x)

x)

(define (g y)

(define a 10)

(+ 1 (f y) a))

(g 2)))

; Resultaat moet 13 zijn.

(compile-and-go

'(begin

(define (f x)

(+ x 1))

(define (g y)

(define a 10)

(+ 1 (f y) a))

(g 2)))

; Resultaat moet 14 zijn.

; Geen zorgen indien je deze niet opgelost krijgt.

5 Theorie

Deze sectie is toegevoegd om snel wat theorie te vermelden indien de oefeningen de theorie hebben ingehaald.

5.1 De top-levelprocedure compile

procedure (compile exp target linkage) → instruction-sequence?

exp : scheme-expressie

target : register

linkage : next/return/label

De top-level compile procedure zet een (hoog-niveau) Scheme-expressie exp om in een sequentie van (laag-niveau) registermachine-instructies. De compile procedure voert een lexicale analyse uit van exp om zo de juiste “code generator” te kiezen zoals compile-self-evaluating, compile-variable, compile-application, etc. De compile procedure heeft 3 argumenten:

• exp : Dit is de te compileren expressie.

• target : Geeft het register aan waar de gecompileerde code de waarde van de expressie moet retourneren. Hieronder volgt een eenvoudig voorbeeld met een self-evaluating expressie, nl. het getal 5.

  > (statements (compile 5 'val 'next))

  ((assign val (const 5)))

• linkage : Geeft aan hoe de gecompileerde code moet verdergezet worden. We onderscheiden hierbij 3 mogelijke gevallen:

  • next : Ga verder met de volgende instructie. (Zie voorbeeld bij uitleg van target.)

  • return : Keer terug naar “vanwaar je kwam”. Per conventie is dit adres steeds opgeslagen in het continue register.

    > (statements (compile 5 'val 'return))

    ((assign val (const 5)) (goto (reg continue)))

  • Ga naar een specifiek label.

    > (statements (compile 5 'val 'my-label))

    ((assign val (const 5)) (goto (label my-label)))

5.2 Instructiesequentie-ADT

Speciale aandacht gaat uit naar het samenstellen van sequenties van registermachine-instructies: <seq1> + <seq2> = <seq>. Dit is geen eenvoudige zaak omdat de mogelijkheid bestaat dat <seq1> registers overschrijft die nodig zijn in <seq2>. Deze kwestie wordt als volgt aangepakt:

procedure (make-instruction-sequence   needs             modifies             statements)   →   instruction-sequence?

needs : register-list

modifies : register-list

statements : register-machine-instructies

procedure (preserving regs seq1 seq2) → instruction-sequence?

regs : register-list

seq1 : instruction-sequence?

seq2 : instruction-sequence?

5.3 Quasiquote

Quasiquoten is een manier om makkelijker symbolen en variabelen door mekaar heen te gebruiken wanneer je lijsten aan het maken bent. Je bent het gebruik hiervan normaal gezien reeds in Structuur van Computerprogramma’s 1 tegengekomen. Desondanks geven we hier nog kort een overzicht en enkele voorbeelden.

• ' : Quote

• ` : Quasiquote

• , : Unquote

• ,@ : Unquote splicing

5.4 Codegeneratoren

De procedure end-with-linkage voegt op basis van de parameter linkage (next, return of label) de nodige linkage-code toe op het einde van de gecompileerde instruction sequence.

De procedure make-instruction-sequence construeert een instruction sequence ADT. Deze instruction sequence kent een lege needs-lijst en 1 modifies-register target. Daarna volgt een geraamte van registermachinecode waarbij enkel nog target en exp ingevuld moeten worden.