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

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

(pp (compile '(if (= 10 (+ 1 2))

100

200)

'een-getal

'return))

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

(pp (compile '(begin

(define x 20)

(if (> x 10)

5

15))

'z

'label-6))

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

(pp (compile '(begin

(define (f n)

(if (< n 2)

1

(* n (f (- n 1)))))

(f 11))

's

'next))

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.

Zie de slides bij de metacirculaire evaluator voor meer details over dynamische scope.

Één aanpassing is essentieel, in compile-lambda-body.

(define (compile-lambda-body exp proc-entry)

(let ((formals (lambda-parameters exp)))

(append-instruction-sequences

(make-instruction-sequence '(env proc argl) '(env)

`(,proc-entry

; Verwijder deze assignment

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

(assign env

(op extend-environment)

(const ,formals) (reg argl) (reg env))))

(compile-sequence (lambda-body exp) 'val 'return))))

Verder zijn er extra’s om de code op te kuisen. De volgende wordt expliciet vermeld bij de metacirculaire evaluator, dus wordt die hier ook in acht genomen.

(define (compile-lambda exp target linkage)

(let ((proc-entry (make-label 'entry))

(after-lambda (make-label 'after-lambda)))

(let ((lambda-linkage

(if (eq? linkage 'next) after-lambda linkage)))

(append-instruction-sequences

(tack-on-instruction-sequence

(end-with-linkage lambda-linkage

; Deze instructiesequentie hoeft env niet meer in needs te hebben

; (make-instruction-sequence '(env) (list target)

(make-instruction-sequence '() (list target)

`((assign ,target

(op make-compiled-procedure)

(label ,proc-entry)

; Het definitie env moet niet meer opgeslagen worden

; (reg env)))))

(const '*no-environment*)))))

(compile-lambda-body exp proc-entry))

after-lambda))))

Je zou verder ook de make-compiled-procedure uit de EC-eval simulator op kunnen kuisen door de env parameter volledig te verwijderen. Deze aanpassing moet dan natuurlijk eveneens in compile-lambda gebruikt worden.

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.

(define (open-coded? exp)

(and (application? exp)

(member (operator exp) '(+ - * =))))

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.

(define (spread-args arg-exps call-code)

(let* ((targets  (make-arg-targets 0 (length arg-exps)))

(arg-codes (map (lambda (exp target)

(compile exp target 'next))

arg-exps

targets)))

(let loop ((arg-codes arg-codes)

(targets targets)

(to-preserve '(env)))

(if (null? arg-codes)

call-code

(preserving to-preserve

(car arg-codes)

(loop (cdr arg-codes)

(cdr targets)

(cons (car targets)

to-preserve)))))))

Sommigen proberen dit iteratief te doen. Dit is niet fout, maar je maakt het jezelf wel moeilijker.

De reden hiervoor is dat je preserving langs vanachter wilt beginnen. Indien er drie argumenten zijn, dan wil je immers eerst het derde argument combineren met call-code. Dan wil je het tweede argument ervoor plakken. Tenslotte het eerste argument voor dat alles. Je wilt dit op die manier doen, omdat je specifiek voor het i-de gecompileerde argument en verder ervoor wilt zorgen dat de i-1 en eerdere registers gepreserved worden. Dit is moeilijk als je iteratief begint op te bouwen langs vanvoor. Als je dit iteratief wilt doen, moet je dan dus eerst de lijsten om gaan draaien zodat je iteratief langs vanachter kunt opbouwen.

Een iteratieve oplossing wordt hier getoond louter voor educatieve redenen, de recursieve oplossing is aangeraden.

(define (spread-args arg-exps call-code)

(let* ((targets (make-arg-targets 0 (length arg-exps)))

(arg-codes (map (lambda (arg target)

(compile arg target 'next))

arg-exps

targets)))

(let iter

((to-preserve (cdr (reverse (cons 'env targets))))

(arg-codes (reverse arg-codes))

(res call-code))

(if (null? arg-codes)

res

(iter (cdr to-preserve)

(cdr arg-codes)

(preserving to-preserve

(car arg-codes)

res))))))

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

(define (compile-open-coded exp target linkage)

(let* ((op (operator exp))

(arg-exps (operands exp))

(arg-count  (length arg-exps))

(targets (make-arg-targets 0 arg-count))

(target-regs (map (lambda (target) `(reg ,target))

targets)))

(end-with-linkage

linkage

(spread-args arg-exps

(make-instruction-sequence

targets

(list target)

`((assign ,target (op ,op) ,@target-regs)))))))

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, ...).

(define eceval-operations

(list (list 'read read)

...

(list '+ +)

(list '- -)

(list '* *)

(list '= =)

...))

(define eceval

(make-machine

'(exp env val proc argl continue unev

val0 val1 val2 val3 val4 val5 val6 val7 val8 val9

compapp)

...))

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)

Indien je niet de juiste registers aan preserving meegaf, dan staan er hier ofwel te weinig, ofwel te veel save en restore oproepen.

(compile-and-go

'(begin

(define (f x)

x)

(define (g y)

(define a 10)

(+ 1 (f y) a))

(g 2)))

; Resultaat moet 13 zijn.

Indien je env niet aan preserving meegaf bij spread-args, dan zal dit een error geven en zeggen dat a niet gekend is. Dit gebeurt omdat de oproep van f het env register overschrijft met de omgeving waarin f gedefinieerd was. Daarin bestaat a natuurlijk niet!

(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.

Waarschijnlijk krijg je hier 15 terug. Dat klopt natuurlijk niet, 1 + (2 + 1) + 10 moet toch 14 zijn? Om te zien waar het hier mis loopt, kan je naar de output van compile kijken. Daar zul je het volgende zien

(assign val0 (const 1))

(save env)

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

Er wordt dus naar de f gegaan zonder dat val0 op de stack gezet wordt. We geven val0 nochtans mee aan preserving, waarom verschijnt er geen save/restore?

Immers, in de body van f zien we

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

(assign val1 (const 1))

(assign val (op +) (reg val0) (reg val1))

De reden dat dit misloopt is te vinden in compile-proc-appl, het stukje code waar het applyen van een compiled procedure behandeld wordt. Daar zie je dat de instruction-sequences die aangemaakt worden allen all-regs gebruiken als modifies. Ze zeggen dus reeds dat alles aanpast kan worden, waarom pikt preserving dit niet op? Daarvoor moet je eens ietsje lager gaan kijken naar de definitie van all-regs. Die wist natuurlijk niet dat wij registers toe hadden gevoegd. Onze val0, val1, ... verschenen dus nooit in de modifies van procedure applicaties! Om dit te corrigeren, kan je dus gewoon deze definitie aanpassen.

(define all-regs '(env proc val argl continue val0 val1 val2 val3))

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?