Reeks 6 : Registermachines

Deze oefeningenreeks behandelt het beschrijven van computationele processen aan de hand van registermachineprogrammaʼs (hoofdstuk 5.1 van Structure and Interpretation of Computer Programs).

Registermachines manipuleren een beperkt aantal geheugenplaatsen of registers. Alhoewel de resulterende procesbeschrijvingen op traditionele machinetaal voor een microprocessor lijken, hebben we in de hoorcolleges in weze telkens een op maat gemaakte microprocessor ontworpen. Het bestand "icp_5_regsim.scm" bevat deze registermachinesimulator. We hebben ook een "grafische registermachinesimulator" voor jullie ontwikkeld.

De registermachine waarvoor wij deze les programma’s zullen schrijven heeft vier registers '(cont v1 v2 res) en ondersteunt volgende operatoren: + * - = < >.

Indien je geen gebruik maakt van Dodona, dan kan het handig zijn om de volgende (assemble-and-run p) functie te gebruiken. Hier is p een list van instructies (en labels). Wanneer het programma stopt, wordt de inhoud van het res register weergegeven.

(define (assemble-and-run p)

(define m (make-machine

'(cont v1 v2 res)

ops

p))

(start m)

(display "\nFinal Result:\n")

(display (get-register-contents m 'res)))

Het volgende stukje code kan je op weg helpen. Het toont de implementatie en oproep van een procedure die altijd 3 terug geeft.

Scheme code:

(define (return-3 a b)

3)

(return-3 15 4)

Equivalente registermachine:

> (assemble-and-run '(start                       (assign v1 (const 15))                       (assign v2 (const 4))                       (assign cont (label stop))                       (goto (label start-return-3))                          start-return-3                       (assign res (const 3))                       (goto (reg cont))                          stop))

Final Result: 3

Voor het vertalen van Scheme-procedures naar registermachineprogramma’s gebruiken we enkele conventies die jullie goed van pas zullen komen.

• De argumenten voor het oproepen van een programma zetten we altijd klaar in de registers v1 en v2.

• Het label waar het programma na het uitvoeren van haar taken naar toe moet springen zetten we klaar in het continuatieregister cont.

• Het resultaat van de oproep moet het programma in het resultaatregister res klaarzetten.

• Als een programma de stack gebruikt moet het deze altijd achterlaten in de toestand van vóór de oproep.

1 Delen

> (assemble-and-run '(start                      (assign v1 (const 15))                      (assign v2 (const 4))                      (assign cont (label stop))                      (goto (label divide-start))                         divide-start                      (assign res (const 0))                      divide-loop                      (test (op <) (reg v1) (reg v2))                      (branch (label divide-end))                      (assign res (op +) (reg res) (const 1))                      (assign v1 (op -) (reg v1) (reg v2))                      (goto (label divide-loop))                         divide-end                      (goto (reg cont))                         stop))

Final Result: 3

2 Machtsverheffing

> (assemble-and-run '(start                      (assign v1 (const 2))                      (assign v2 (const 5))                      (assign cont (label stop))                      (goto (label expt-start))                         expt-start                      (assign res (const 1))                      expt-loop                      (test (op =) (reg v2) (const 0))                      (branch (label expt-end))                      (assign res (op *) (reg res) (reg v1))                      (assign v2 (op -) (reg v2) (const 1))                      (goto (label expt-loop))                      expt-end                      (goto (reg cont))                         stop))

Final Result: 32

3 Machtsverheffing (recursief)

> (assemble-and-run '(start                      (assign v1 (const 2))                      (assign v2 (const 5))                      (assign cont (label stop))                      (goto (label expt-start))                         expt-start                      (test (op =) (reg v2) (const 0))                      (branch (label expt-end))                      (save cont)                      (assign cont (label expt-continue))                      (assign v2 (op -) (reg v2) (const 1))                      (goto (label expt-start))                      expt-continue                      (restore cont)                      (assign res (op *) (reg res) (reg v1))                      (goto (reg cont))                      expt-end                      (assign res (const 1))                      (goto (reg cont))                      stop))

Final Result: 32

4 Fibonacci

Maak in deze oefening geen gebruik van het v2 register.

Herinner welke waarden de fibonacci functie kan aannemen:

> (assemble-and-run    '(start     (assign v1 (const 6))     (assign cont (label stop))     (goto (label fib-start))        fib-start     (test (op <) (reg v1) (const 2))     (branch (label fib-end))        fib-min-1     (save cont)     (save v1)     (assign v1 (op -) (reg v1) (const 1))     (assign cont (label fib-min-2))     (goto (label fib-start))        fib-min-2     (restore v1)     (save res)     (assign v1 (op -) (reg v1) (const 2))     (assign cont (label fib-plus))     (goto (label fib-start))        fib-plus     (restore v1)     (assign res (op +) (reg v1) (reg res))     (restore cont)     (goto (reg cont))        fib-end     (assign res (reg v1))     (goto (reg cont))        stop))

Final Result: 8

5 Gelukkige getallen

Deze oefening was een examenvraag in de tweede zit van het academiejaar 2018-2019.

Morgen, 27 augustus, is de 239ste dag van het jaar 2019. Hopelijk zijn jullie dan allemaal geslaagd voor dit vak. Een gevoel van gelukzaligheid zal zich meester van jullie maken. Dat is geen toeval, want 239 is een gelukkig getal.

Testen of een getal een gelukkig getal is, doe je door de individuele cijfers te kwadrateren en op te tellen. In het geval van 239 geeft dit 2² + 3² + 9² = 94. Dit proces blijf je herhalen. Indien je uiteindelijk bij 1 uitkomt, dan was het originele getal een gelukkig getal. Voor 239 krijg je dus: 239 → 94 → 97 → 130 → 10 → 1. Indien dit proces niet tot een 1 leidt, dan komt het in een loop terecht waar het niet meer uitgeraakt.

Beschouw de volgende Scheme code die #t teruggeeft indien het gegeven getal een gelukkig getal is. Indien het geen gelukkig getal is, blijft de code lopen.

(define (is-gelukkig n)

(if (= n 1)

#t

(is-gelukkig (kwadrateer-cijfers n))))

(define (kwadrateer-cijfers n)

(define (kwadrateer-cijfers-loop x y)

(if (< x 10)

(+ y (* x x))

(kwadrateer-cijfers-loop (verwijder-laatste-cijfer x)

(+ y

(* (laatste-cijfer x)

(laatste-cijfer x))))))

(kwadrateer-cijfers-loop n 0))

Je wordt gevraagd de twee gegeven Scheme functies om te zetten naar twee subroutines in een registermachine. De registermachine waarop jouw code uitgevoerd zal worden, ondersteunt +, *, =, <, laatste-cijfer, en verwijder-laatste-cijfer als primitieve operaties. Die twee laatste doen wat hun naam aanduidt. De registermachine beschikt over drie registers: v1, res, en cont. De subroutines worden verwacht de richtlijnen uit de WPOs te volgen i.v.m. het gebruik van labels en het gebruik van deze registers.

Bespreek ten slotte kort (maximum drie zinnen) hoe jouw registermachine zich gedraagt indien het gegeven getal geen gelukkig getal is. Zoals eerder vermeld zal dit tot een loop leiden. Blijft deze loop oneindig lang duren? Zal de registermachine crashen door een tekort aan geheugen? Waarom wel of waarom niet?

Om volledig te zijn, hier kan je dus niet assemble-and-run gebruiken. Gebruik in plaats daarvan de volgende machine.

6 Fietsvakantie

Deze oefening was een examenvraag in de eerste zit van het academiejaar 2020-2021.

Voor komende zomer zou je graag een fietsvakantie plannen. Daarvoor zou je de algemene hellingsgraad van de tocht willen kennen. De hellingsgraad is de hoogte gedeeld door de lengte, neergeschreven in procent. Ga je bijvoorbeeld 52 meter omhoog over 1000 meter, dan is de hellingsgraad 52 / 1000 = 0.052 = 5.2%.

Je zoekt en vindt enkele gegevens online, maar helaas zijn deze opgedeeld in "segmenten" van een beklimming. De gegevens van de Lukmanierpas in de Zwitserse Alpen zien er bijvoorbeeld als volgt uit:

(define hoogtes ( 228   52   72   43   64   53   67   72  194))

(define lengtes (3000 1000 3000 1000 1000 1000 1000 2000 2800))

Ter verduidelijking stelt volgende afbeelding het eerste en het voorlaatste segment voor:

Om de hellingsgraad van de hele klim uit te rekenen, moet je de hoogtes optellen en dit getal delen door de som van alle lengtes:

(define som_hoogtes (+ 228 52 72 43 64 53 67 72 194))

; 845

(define som_lengtes (+ 3000 1000 3000 1000 1000 1000 1000 2000 2800))

; 15800

(define hellingsgraad_lukmanierpas (/ 845 15800))

; = 5.35%

Jou wordt nu gevraagd om de hellingsgraad en som functies om te zetten naar twee subroutines in registermachinecode. Het iteratieve of recursieve karakter van de functies moet natuurlijk behouden worden. De registermachine waarop jouw subroutine wordt uitgevoerd, ondersteunt null?, car, cdr, +, *, en / als operaties. De registermachine beschikt over vier registers: cont, v1, v2 en res. Alle subroutines in deze registermachine volgen hetzelfde “contract”: input wordt verwacht in v1 en v2, output belandt in res en de inhoud van cont wordt gebruikt om uit de subroutine te springen wanneer deze klaar is. We verwachten hetzelfde van jouw code. Samengevat, jouw code moet hieronder ingevoegd kunnen worden en het gepaste resultaat in res achterlaten:

(let ((helling-machine

(make-machine

'(cont v1 v2 res)

`((null? ,null?) (car ,car) (cdr ,cdr) (+ ,+) (* ,*) (/ ,/))

'(start

(assign v1 (const ( 228   52   72   43   64   53   67   72  194)))

(assign v2 (const (3000 1000 3000 1000 1000 1000 1000 2000 2800)))

(assign cont (label stop))

(goto (label hellingsgraad))

; <jouw code hier>

stop))))

(start helling-machine)

(display (get-register-contents helling-machine 'res)))

(let ((helling-machine

(make-machine

'(cont v1 v2 res)

`((null? ,null?) (car ,car) (cdr ,cdr) (+ ,+) (* ,*) (/ ,/))

'(start

(assign v1 (const ( 228   52   72   43   64   53   67   72  194)))

(assign v2 (const (3000 1000 3000 1000 1000 1000 1000 2000 2800)))

(assign cont (label stop))

(goto (label hellingsgraad))

hellingsgraad

hellingsgraad-bereken-hoogte

(save cont)

(save v2)

(assign cont (label hellingsgraad-bereken-lengte))

(goto (label som-rec))

hellingsgraad-bereken-lengte

(restore v1)

(save res)

(assign cont (label hellingsgraad-deel-uitkomsten))

(goto (label som-rec))

hellingsgraad-deel-uitkomsten

(restore v1)

(assign res (op /) (reg v1) (reg res))

(assign res (op *) (reg res) (const 100))

(restore cont)

(goto (reg cont))

som-rec

(test (op null?) (reg v1))

(branch (label som-base))

(assign v2 (op car) (reg v1))

(save cont)

(save v2)

(assign v1 (op cdr) (reg v1))

(assign cont (label som-na-rec))

(goto (label som-rec))

som-na-rec

(restore v1)

(assign res (op +) (reg res) (reg v1))

(restore cont)

(goto (reg cont))

som-base

(assign res (const 0.0))

(goto (reg cont))

stop))))

(start helling-machine)

(display (get-register-contents helling-machine 'res)))

7 Oude oefeningen

Deze oefeningen maken geen deel meer uit van de WPOs. Indien je je verveelt, mag je ze natuurlijk ook maken.

7.1 Factorial

Enkele voorbeelden:

> (assemble-and-run '(start                      (assign v1 (const 5))                      (assign cont (label stop))                      (goto (label factorial-start))                         factorial-start                      (assign res (const 1))                      (assign v2 (const 1))                      factorial-loop                      (test (op <) (reg v1) (reg v2))                      (branch (label factorial-end))                      (assign res (op *) (reg v2) (reg res))                      (assign v2 (op +) (reg v2) (const 1))                      (goto (label factorial-loop))                      factorial-end                      (goto (reg cont))                         stop))

Final Result: 120

7.2 Programma’s combineren

7.2.1 Display One

7.2.2 Display Zero

7.2.3 Divide

7.2.4 Modulo

7.2.5 Combineer

Ontwerp nu een registermachine die het getal in register v1 in binaire vorm op het scherm toont. Maak hierbij gebruik van (de) stukjes registermachine die je net maakte, en laat je inspireren door de volgende procedure:

(define (display-binary n)

(if (= n 0)

(display-zero)

(if (= n 1)

(display-one)

(begin

(display-binary (divide n 2))

(if (= (modulo n 2) 0)

(display-zero)

(display-one))))))

> (assemble-and-run '(start                      (assign v1 (const 14))                      (assign cont (label stop))                      (goto (label display-binary-start))                         display-one-start                      (perform (op display) (const 1))                      (goto (reg cont))                         display-zero-start                      (perform (op display) (const 0))                      (goto (reg cont))                         divide-start                      (assign res (const 0))                      divide-loop                      (test (op <) (reg v1) (reg v2))                      (branch (label divide-end))                      (assign res (op +) (reg res) (const 1))                      (assign v1 (op -) (reg v1) (reg v2))                      (goto (label divide-loop))                      divide-end                      (goto (reg cont))                         modulo-start                      (test (op <) (reg v1) (reg v2))                      (branch (label modulo-end))                      (assign v1 (op -) (reg v1) (reg v2))                      (goto (label modulo-start))                      modulo-end                      (assign res (reg v1))                      (goto (reg cont))                         display-binary-start                      (test (op =) (reg v1) (const 0))                      (branch (label display-zero-start))                      (test (op =) (reg v1) (const 1))                      (branch (label display-one-start))                      (save cont)                      (save v1)                      (assign cont (label display-rec))                      (assign v2 (const 2))                      (goto (label divide-start))                      display-rec                      (assign cont (label compute-modulo))                      (assign v1 (reg res))                      (goto (label display-binary-start))                      compute-modulo                      (restore v1)                      (assign v2 (const 2))                      (assign cont (label display-modulo))                      (goto (label modulo-start))                      display-modulo                      (restore cont)                      (test (op =) (reg res) (const 0))                      (branch (label display-zero-start))                      (goto (label display-one-start))                         stop))

1110 Final Result: 0