Interpretatie van Computerprogramma’s I
Theo D’Hondt
Vrije Universiteit Brussel Faculteit van de Wetenschappen Vakgroep Informatica
Deel 2a: Ontwerp van registermachines Interpretatie van Computerprogramma's I Theo D'Hondt
Ontwerp van register machines
p.
1
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Register Machines registers
data paths
operaties
=
controller sekwentie Ontwerp van register machines
p.
2
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Voorbeeld het algoritme van Euclides voor de grootste gemene deler van twee natuurlijke getallen
registers
(define (gcd a b) (if (= b 0) a (gcd (b (remainder a b))))
sekwentie operaties Ontwerp van register machines
p.
3
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Data-path diagram a<-b a
=
b
b<-t
rem t<-r
t
Ontwerp van register machines
0
p.
4
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Betekenis t
register
rem
operatie
=
predicaat
Ontwerp van register machines
t<-r
toekenning
sekwentie
0
constante
p.
5
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Controller diagram start ja =
stop
nee t<-r
a<-b
b<-t Ontwerp van register machines
p.
6
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Gebruik van een specificatietaal (data-paths (registers ((name a) (buttons ((name a<-b) (source (register b))))) ((name b) (buttons ((name b<-t) (source (register t))))) ((name t) (buttons ((name t<-r) (source (operation rem)))))) (operations ((name rem) (inputs (register a) (register b))) ((name =) (inputs (register b) (constant 0))))) (controller test-b (test =) (branch (label gcd-done)) (t<-r) (a<-b) (b<-t) (goto (label test-b)) gcd-done) Ontwerp van register machines
; ; ; ; ; ; ; ;
label test conditional branch button-push button-push button-push unconditional branch label p.
7
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Formele beschrijving van een machine (controller
) GCD (controller test-b (test (op =) (reg b) (const 0)) (branch (label gcd-done)) (assign t (op rem) (reg a) (reg b)) (assign a (reg b)) (assign b (reg t)) (goto (label test-b)) gcd-done)
Ontwerp van register machines
p.
8
Interpretatie van Computerprogramma’s I
Theo D’Hondt
GCD-machine die leest en schrijft read a<-rd
b<-rd a<-b
a
b
=
P
print
rem
b<-t
t<-r
t Ontwerp van register machines
0 p.
9
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Specificatie GCD
(controller gcd-loop (assign a (op read)) (assign b (op read)) test-b (test (op =) (reg b) (const 0)) (branch (label gcd-done)) (assign t (op rem) (reg a) (reg b)) (assign a (reg b)) (assign b (reg t)) (goto (label test-b)) gcd-done (perform (op print) (reg a)) (goto (label gcd-loop)))
Ontwerp van register machines
p. 10
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Uitgewerkte GCD-machine
(define (remainder n d) (if (n < d) n (remainder (- n d) d)))
Ontwerp van register machines
p. 11
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Uitgewerkte GCD-machine: data-paths a<-b a
b
t<-a
b<-t t
t<-d
=
<
rem
0
Ontwerp van register machines
p. 12
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Uitgewerkte GCD-machine: controller start ja =
stop
t<-a
nee t<-a
nee
<
ja a<-b
b<-t Ontwerp van register machines
p. 13
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Uitgewerkte GCD-machine: specificatie (controller test-b (test (op =) (reg b) (const 0)) (branch (label gcd-done)) (assign t (reg a)) rem-loop (test (op <) (reg t) (reg b)) (branch (label rem-done)) (assign t (op -) (reg t) (reg b)) (goto (label rem-loop)) rem-done (assign a (reg b)) (assign b (reg t)) (goto (label test-b)) gcd-done)
Ontwerp van register machines
GCD
p. 14
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Subroutines: het 2 x gcd voorbeeld a<-b a
=
b
c<-d c b<-t
rem t<-r
d<-s
rem t
0
s<-r
s Ontwerp van register machines
=
d
0 p. 15
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Volledig ontdubbelde specificaties (controller ... gcd-1 (test (op =) (reg b) (const 0)) (branch (label after-gcd-1)) (assign t (op rem) (reg a) (reg b)) (assign a (reg b)) (assign b (reg t)) (goto (label gcd-1)) after-gcd-1 ... gcd-2 (test (op =) (reg d) (const 0)) (branch (label after-gcd-2)) (assign s (op rem) (reg c) (reg d)) (assign c (reg d)) (assign d (reg s)) (goto (label gcd-1)) after-gcd-2 ... ) Ontwerp van register machines
p. 16
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Gemeenschappelijke data-paths (controller ... gcd-1 (test (op =) (reg b) (const 0)) (branch (label after-gcd-1)) (assign t (op rem) (reg a) (reg b)) (assign a (reg b)) (assign b (reg t)) (goto (label gcd-1)) after-gcd-1 ... gcd-2 (test (op =) (reg b) (const 0)) (branch (label after-gcd-2)) (assign t (op rem) (reg a) (reg b)) (assign a (reg b)) (assign b (reg t)) (goto (label gcd-2)) after-gcd-2 ... ) Ontwerp van register machines
p. 17
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Gemeenschappelijke controller gcd (test (op =) (reg b) (const 0)) (branch (label gcd-done)) (assign t (op rem) (reg a) (reg b)) (assign a (reg b)) (assign b (reg t)) (goto (label gcd)) gcd-done (test (op =) (reg continue) (const 0)) (branch (label gcd-1-done)) (goto (label gcd-2-done)) ... gcd-1 (assign continue 0) (goto gcd) gcd-1-done ... gcd-2 (assign continue 1) (goto gcd) gcd-2-done ...) Ontwerp van register machines
p. 18
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Labels als waarde gcd (test (op =) (reg b) (const 0)) (branch (label gcd-done)) (assign t (op rem) (reg a) (reg b)) (assign a (reg b)) (assign b (reg t)) (goto (label gcd)) gcd-done (goto (reg continue)) ... gcd-1 (assign continue gcd-1-done) (goto gcd) gcd-1-done ... gcd-2 (assign continue gcd-2-done) (goto gcd) gcd-2-done ...)
Ontwerp van register machines
p. 19
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Recursieve processen
(define (fac n) (if (= n 1) 1 (* (fac (- n 1)) n)))
Ontwerp van register machines
p. 20
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Recursie via een stapel = stack
1 rn sn val
n
controller
*
sc rc continue stack after-fact
Ontwerp van register machines
fact-done p. 21
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Recursie via een stapel (controller factorial-machine (assign continue (label fact-done)) fact-loop (test (op =) (reg n) (const 1)) (branch (label base-case)) (save continue) (save n) (assign n (op -) (reg n) (const 1)) (assign continue (label after-fact)) (goto (label fact-loop)) after-fact (restore n) (restore continue) (assign val (op *) (reg n) (reg val)) (goto (reg continue)) base-case (assign val (const 1)) (goto (reg continue)) return to caller fact-done) Ontwerp van register machines
p. 22
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Complexe recursieve processen
(define (fib n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))
Ontwerp van register machines
p. 23
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Het Fibonacci controle-programma (controller (assign continue (label fib-done)) fib-loop (test (op <) (reg n) (const 2)) (branch (label immediate-answer)) (save continue) (assign continue (label afterfib-n-1)) (save n) (assign n (op -) (reg n) (const 1)) (goto (label fib-loop)) afterfib-n-1 (restore n) (restore continue) (assign n (op -) (reg n) (const 2)) (save continue) (assign continue (label afterfib-n-2)) (save val) (goto (label fib-loop))
Ontwerp van register machines
p. 24
Interpretatie van Computerprogramma’s I
Theo D’Hondt
Het Fibonacci controle-programma afterfib-n-2 (assign n (reg val)) (restore val) (restore continue) (assign val (op +) (reg val) (reg n)) (goto (reg continue)) immediate-answer (assign val (reg n)) (goto (reg continue)) fib-done)
Ontwerp van register machines
p. 25
