5.1 Dylunio Peiriannau Cofrestri

I ddylunio peiriant cofrestri, rhaid inni ddylunio ei lwybrau data (cofrestri a gweithrediadau) a'r rheolydd sy'n trefnu'r gweithrediadau hyn yn ddilyniant. I ddangos sut i ddylunio peiriant cofrestri syml, gadewch inni archwilio Algorithm Euclid, a ddefnyddir i gyfrifiannu rhannwr cyffredin mwyaf (GCD) dau gyfanrif. Fel y gwelsom yn 1.2.5, gellir cyflawni Algorithm Euclid drwy broses iteru, fel y pennir gan y weithdrefn ganlynol:

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

Rhaid i beiriant sy'n cyflawni'r algorithm hwn gadw cofnod o ddau rif, $a$ ac $b$, felly gadewch inni dybio bod y rhifau hyn wedi'u storio mewn dwy gofrestr o'r enwau hynny. Y gweithrediadau sylfaenol sydd eu hangen yw profi a yw cynnwys cofrestr b yn sero a chyfrifiannu gweddill cynnwys cofrestr a wedi'i rannu â chynnwys cofrestr b. Mae'r gweithrediad gweddill yn broses gymhleth, ond tybiwch am y tro fod gennym ddyfais gyntefig sy'n cyfrifiannu gweddillion. Ar bob cylch o'r algorithm GCD, rhaid rhoi cynnwys cofrestr b yn lle cynnwys cofrestr a, a rhaid rhoi gweddill hen gynnwys a wedi'i rannu â hen gynnwys b yn lle cynnwys b. Byddai'n gyfleus pe gellid gwneud yr amnewidiadau hyn ar yr un pryd, ond yn ein model o beiriannau cofrestri byddwn yn tybio mai dim ond i un gofrestr y gellir aseinio gwerth newydd ar bob cam. I gyflawni'r amnewidiadau, bydd ein peiriant yn defnyddio trydedd gofrestr “dros dro,” a alwn yn t. (Yn gyntaf rhoddir y gweddill yn t, yna rhoddir cynnwys b yn a, ac yn olaf rhoddir y gweddill sydd wedi'i storio yn t yn b.)

Gallwn ddangos y cofrestri a'r gweithrediadau sydd eu hangen ar y peiriant hwn drwy ddefnyddio'r diagram llwybr data a ddangosir yn Ffigur 5.1. Yn y diagram hwn, cynrychiolir y cofrestri (a, b, ac t) gan betryalau. Dangosir pob ffordd o aseinio gwerth i gofrestr gan saeth ag X y tu ôl i'r pen, yn pwyntio o ffynhonnell y data at y gofrestr. Gallwn feddwl am yr X fel botwm sydd, o'i wasgu, yn caniatáu i'r gwerth yn y ffynhonnell “lifo” i'r gofrestr ddynodedig. Y label wrth bob botwm yw'r enw y byddwn yn ei ddefnyddio i gyfeirio at y botwm. Mae'r enwau'n fympwyol, a gellir eu dewis i fod yn gymhorthion cof (er enghraifft, mae a<-b yn dynodi gwasgu'r botwm sy'n aseinio cynnwys cofrestr b i gofrestr a). Gall ffynhonnell data cofrestr fod yn gofrestr arall (fel yn yr aseiniad a<-b), yn ganlyniad gweithrediad (fel yn yr aseiniad t<-r), neu'n gysonyn (gwerth adeiledig na ellir ei newid, a gynrychiolir mewn diagram llwybr data gan driongl sy'n cynnwys y cysonyn).

Cynrychiolir gweithrediad sy'n cyfrifiannu gwerth o gysonion a chynnwys cofrestri mewn diagram llwybr data gan drapesiwm sy'n cynnwys enw'r gweithrediad. Er enghraifft, mae'r blwch sydd wedi'i farcio rem yn Ffigur 5.1 yn cynrychioli gweithrediad sy'n cyfrifiannu gweddill cynnwys y cofrestri a ac b y mae wedi'i gysylltu â hwy. Mae saethau (heb fotymau) yn pwyntio o'r cofrestri mewnbwn a'r cysonion at y blwch, ac mae saethau'n cysylltu gwerth allbwn y gweithrediad â chofrestri. Cynrychiolir prawf gan gylch sy'n cynnwys enw'r prawf. Er enghraifft, mae gan ein peiriant GCD weithrediad sy'n profi a yw cynnwys cofrestr b yn sero. Mae gan brawf hefyd saethau o'i gofrestri mewnbwn a'i gysonion, ond nid oes ganddo saethau allbwn; defnyddir ei werth gan y rheolydd yn hytrach na chan y llwybrau data. Yn gyffredinol, mae'r diagram llwybr data yn dangos y cofrestri a'r gweithrediadau sydd eu hangen ar y peiriant a sut y mae'n rhaid eu cysylltu. Os ystyriwn y saethau yn wifrau a'r botymau X yn switshis, mae'r diagram llwybr data yn debyg iawn i ddiagram gwifrau peiriant y gellid ei adeiladu o gydrannau trydanol.

Er mwyn i'r llwybrau data gyfrifiannu GCD mewn gwirionedd, rhaid gwasgu'r botymau yn y drefn gywir. Byddwn yn disgrifio'r dilyniant hwn yn nhermau diagram rheolydd, fel y dangosir yn Ffigur 5.2. Mae elfennau'r diagram rheolydd yn dangos sut y dylid gweithredu cydrannau'r llwybr data. Mae'r blychau petryalog yn y diagram rheolydd yn adnabod botymau llwybr data sydd i'w gwasgu, ac mae'r saethau'n disgrifio'r drefn o un cam i'r nesaf. Mae'r diemwnt yn y diagram yn cynrychioli penderfyniad. Dilynir un o'r ddwy saeth ddilyniant, yn dibynnu ar werth y prawf llwybr data a enwir yn y diemwnt. Gallwn ddehongli'r rheolydd drwy gyfatebiaeth ffisegol: meddyliwch am y diagram fel drysfa y mae marblen yn rholio ynddi. Pan fo'r farblen yn rholio i mewn i flwch, mae'n gwasgu'r botwm llwybr data a enwir gan y blwch. Pan fo'r farblen yn rholio i mewn i nod penderfynu (megis y prawf am b = 0), mae'n gadael y nod ar y llwybr a bennir gan ganlyniad y prawf a ddangosir. Gyda'i gilydd, mae'r llwybrau data a'r rheolydd yn disgrifio peiriant ar gyfer cyfrifiannu GCD yn llwyr. Dechreuwn y rheolydd (y farblen sy'n rholio) yn y man a farciwyd start, ar ôl rhoi rhifau mewn cofrestri a ac b. Pan fydd y rheolydd yn cyrraedd done, cawn werth y GCD yng nghofrestr a.

Ymarfer 5.1: Dyluniwch beiriant cofrestri i gyfrifiannu ffactorialau gan ddefnyddio'r algorithm iteru a bennir gan y weithdrefn ganlynol. Lluniwch ddiagramau llwybr data a rheolydd ar gyfer y peiriant hwn.

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

5.1.1Iaith ar gyfer Disgrifio Peiriannau Cofrestri

Mae diagramau llwybr data a rheolydd yn ddigonol ar gyfer cynrychioli peiriannau syml megis GCD, ond maent yn anhylaw ar gyfer disgrifio peiriannau mawr megis dehonglydd Lisp. Er mwyn gallu ymdrin â pheiriannau cymhleth, byddwn yn creu iaith sy'n cyflwyno, ar ffurf testun, yr holl wybodaeth a roddir gan y diagramau llwybr data a rheolydd. Dechreuwn â nodiant sy'n adlewyrchu'r diagramau'n uniongyrchol.

Diffiniwn lwybrau data peiriant drwy ddisgrifio'r cofrestri a'r gweithrediadau. I ddisgrifio cofrestr, rhoddwn enw iddi a phennwn y botymau sy'n rheoli aseinio iddi. Rhoddwn enw i bob un o'r botymau hyn a phennwn ffynhonnell y data sy'n mynd i mewn i'r gofrestr dan reolaeth y botwm. (Cofrestr, cysonyn, neu weithrediad yw'r ffynhonnell.) I ddisgrifio gweithrediad, rhoddwn enw iddo a phennwn ei fewnbynnau (cofrestri neu gysonion).

Diffiniwn reolydd peiriant fel dilyniant o gyfarwyddiadau ynghyd â labeli sy'n adnabod pwyntiau mynediad yn y dilyniant. Mae cyfarwyddyd yn un o'r canlynol:

• Enw botwm llwybr data i'w wasgu er mwyn aseinio gwerth i gofrestr. (Mae hyn yn cyfateb i flwch yn y diagram rheolydd.)
• Cyfarwyddyd test, sy'n cyflawni prawf penodol.
• Cangen amodol (cyfarwyddyd branch) i leoliad a ddangosir gan label rheolydd, yn seiliedig ar ganlyniad y prawf blaenorol. (Mae'r prawf a'r gangen gyda'i gilydd yn cyfateb i ddiemwnt yn y diagram rheolydd.) Os yw'r prawf yn anwir, dylai'r rheolydd barhau â'r cyfarwyddyd nesaf yn y dilyniant. Fel arall, dylai'r rheolydd barhau â'r cyfarwyddyd ar ôl y label.
• Cangen ddiamod (cyfarwyddyd goto) sy'n enwi label rheolydd lle dylid parhau i weithredu.

Mae'r peiriant yn dechrau ar ddechrau dilyniant cyfarwyddiadau'r rheolydd ac yn stopio pan fydd y gweithredu'n cyrraedd diwedd y dilyniant. Heblaw pan fydd cangen yn newid llif rheolaeth, gweithredir cyfarwyddiadau yn y drefn y'u rhestrir.

Mae Ffigur 5.3 yn dangos y peiriant GCD wedi'i ddisgrifio fel hyn. Nid yw'r enghraifft hon ond yn awgrymu cyffredinolrwydd y disgrifiadau hyn, gan fod y peiriant GCD yn achos syml iawn: dim ond un botwm sydd gan bob cofrestr, a dim ond unwaith y defnyddir pob botwm a phrawf yn y rheolydd.

Ffigur 5.3: $\downarrow <!--\; \downarrow \; -->$ Manyleb y peiriant GCD.

(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                ; label
   (test =)            ; test
   (branch 
    (label gcd-done))  ; conditional branch
   (t<-r)              ; button push
   (a<-b)              ; button push
   (b<-t)              ; button push
   (goto 
    (label test-b))    ; unconditional branch
 gcd-done)             ; label

Yn anffodus, mae'n anodd darllen disgrifiad o'r fath. Er mwyn deall cyfarwyddiadau'r rheolydd, rhaid inni gyfeirio'n ôl yn gyson at ddiffiniadau enwau'r botymau ac enwau'r gweithrediadau, ac i ddeall beth mae'r botymau'n ei wneud efallai y bydd angen cyfeirio at ddiffiniadau enwau'r gweithrediadau. Felly byddwn yn trawsffurfio ein nodiant i gyfuno'r wybodaeth o'r disgrifiadau llwybr data a rheolydd fel y gallwn ei gweld i gyd gyda'i gilydd.

I gael y ffurf hon ar ddisgrifiad, byddwn yn rhoi diffiniadau o ymddygiad y botymau a'r gweithrediadau yn lle eu henwau mympwyol. Hynny yw, yn hytrach na dweud (yn y rheolydd) “Gwasgwch fotwm t<-r” a dweud ar wahân (yn y llwybrau data) “Mae botwm t<-r yn aseinio gwerth y gweithrediad rem i gofrestr t” a “Mewnbynnau'r gweithrediad rem yw cynnwys cofrestri a ac b,” byddwn yn dweud (yn y rheolydd) “Gwasgwch y botwm sy'n aseinio i gofrestr t werth y gweithrediad rem ar gynnwys cofrestri a ac b.” Yn yr un modd, yn hytrach na dweud (yn y rheolydd) “Cyflawnwch y prawf =” a dweud ar wahân (yn y llwybrau data) “Mae'r prawf = yn gweithredu ar gynnwys cofrestr b a'r cysonyn 0,” byddwn yn dweud “Cyflawnwch y prawf = ar gynnwys cofrestr b a'r cysonyn 0.” Byddwn yn hepgor y disgrifiad llwybr data, gan adael dilyniant y rheolydd yn unig. Felly, disgrifir y peiriant GCD fel a ganlyn:

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

Mae'r ffurf hon ar ddisgrifiad yn haws ei darllen na'r math a ddangosir yn Ffigur 5.3, ond mae iddi anfanteision hefyd:

• Mae'n fwy geiriog ar gyfer peiriannau mawr, oherwydd bod disgrifiadau cyflawn o elfennau'r llwybr data yn cael eu hailadrodd pryd bynnag y crybwyllir yr elfennau yn nilyniant cyfarwyddiadau'r rheolydd. (Nid yw hyn yn broblem yn yr enghraifft GCD, oherwydd dim ond unwaith y defnyddir pob gweithrediad a botwm.) Ar ben hynny, mae ailadrodd y disgrifiadau llwybr data yn cuddio strwythur gwirioneddol llwybr data'r peiriant; nid yw'n amlwg mewn peiriant mawr faint o gofrestri, gweithrediadau, a botymau sydd, na sut y maent wedi'u cysylltu â'i gilydd.
• Gan fod cyfarwyddiadau'r rheolydd mewn diffiniad peiriant yn edrych fel mynegiadau Lisp, mae'n hawdd anghofio nad mynegiadau Lisp mympwyol ydynt. Dim ond gweithrediadau peiriant dilys y gallant eu nodi. Er enghraifft, dim ond ar gysonion a chynnwys cofrestri y gall gweithrediadau weithredu'n uniongyrchol, nid ar ganlyniadau gweithrediadau eraill.

Er gwaethaf yr anfanteision hyn, byddwn yn defnyddio'r iaith peiriannau cofrestri hon drwy gydol y bennod, oherwydd bydd gennym fwy o ddiddordeb mewn deall rheolyddion nag mewn deall elfennau a chysylltiadau llwybrau data. Dylem gofio, fodd bynnag, fod dylunio llwybrau data yn hanfodol wrth ddylunio peiriannau go iawn.

Ymarfer 5.2: Defnyddiwch yr iaith peiriannau cofrestri i ddisgrifio peiriant ffactorial iteru Ymarfer 5.1.

Gweithredoedd

Gadewch inni addasu'r peiriant GCD fel y gallwn deipio'r rhifau yr ydym am gael eu GCD a chael yr ateb wedi'i argraffu yn ein terfynell. Ni fyddwn yn trafod sut i wneud peiriant sy'n gallu darllen ac argraffu, ond byddwn yn tybio (fel y gwnawn wrth ddefnyddio read ac display yn Scheme) eu bod ar gael fel gweithrediadau cyntefig.²⁸⁶

Mae Read yn debyg i'r gweithrediadau yr ydym wedi'u defnyddio gan ei bod yn cynhyrchu gwerth y gellir ei storio mewn cofrestr. Ond nid yw read yn cymryd mewnbynnau o unrhyw gofrestri; mae ei gwerth yn dibynnu ar rywbeth sy'n digwydd y tu allan i'r rhannau o'r peiriant yr ydym yn eu dylunio. Byddwn yn caniatáu i weithrediadau ein peiriant ymddwyn fel hyn, ac felly byddwn yn darlunio ac yn nodi defnydd read yn union fel unrhyw weithrediad arall sy'n cyfrifiannu gwerth.

Ar y llaw arall, mae Print yn wahanol mewn ffordd sylfaenol i'r gweithrediadau yr ydym wedi'u defnyddio: nid yw'n cynhyrchu gwerth allbwn i'w storio mewn cofrestr. Er bod ganddi effaith, nid ar ran o'r peiriant yr ydym yn ei ddylunio y mae'r effaith honno. Byddwn yn cyfeirio at y math hwn o weithrediad fel gweithred. Byddwn yn cynrychioli gweithred mewn diagram llwybr data yn union fel gweithrediad sy'n cyfrifiannu gwerth—fel trapesiwm sy'n cynnwys enw'r weithred. Mae saethau'n pwyntio at flwch y weithred o unrhyw fewnbynnau (cofrestri neu gysonion). Rydym hefyd yn cysylltu botwm â'r weithred. Mae gwasgu'r botwm yn peri i'r weithred ddigwydd. I wneud i reolydd wasgu botwm gweithred, defnyddiwn fath newydd o gyfarwyddyd o'r enw perform. Felly, cynrychiolir y weithred o argraffu cynnwys cofrestr a mewn dilyniant rheolydd gan y cyfarwyddyd

(perform (op print) (reg a))

Mae Ffigur 5.4 yn dangos llwybrau data a rheolydd y peiriant GCD newydd. Yn hytrach na gwneud i'r peiriant stopio ar ôl argraffu'r ateb, rydym wedi gwneud iddo ddechrau eto, fel ei fod yn darllen pâr o rifau, yn cyfrifiannu eu GCD, ac yn argraffu'r canlyniad dro ar ôl tro. Mae'r strwythur hwn yn debyg i'r dolenni gyrru a ddefnyddiasom yn nehonglwyr Pennod 4.

5.1.2Haniaethu wrth Ddylunio Peiriannau

Byddwn yn aml yn diffinio peiriant i gynnwys gweithrediadau “cyntefig” sydd mewn gwirionedd yn gymhleth iawn. Er enghraifft, yn 5.4 a 5.5 byddwn yn trin gweithrediadau Scheme ar amgylcheddau fel rhai cyntefig. Mae haniaethu o'r fath yn werthfawr oherwydd ei fod yn caniatáu inni anwybyddu manylion rhannau o beiriant er mwyn canolbwyntio ar agweddau eraill ar y dyluniad. Fodd bynnag, nid yw'r ffaith ein bod wedi ysgubo llawer o gymhlethdod o dan y carped yn golygu bod dyluniad peiriant yn afrealistig. Gallwn bob amser roi gweithrediadau cyntefig symlach yn lle'r gweithrediadau “cyntefig” cymhleth.

Ystyriwch y peiriant GCD. Mae gan y peiriant gyfarwyddyd sy'n cyfrifiannu gweddill cynnwys cofrestri a ac b ac yn aseinio'r canlyniad i gofrestr t. Os ydym am adeiladu'r peiriant GCD heb ddefnyddio gweithrediad gweddill cyntefig, rhaid inni bennu sut i gyfrifiannu gweddillion yn nhermau gweithrediadau symlach, megis tynnu. Yn wir, gallwn ysgrifennu gweithdrefn Scheme sy'n canfod gweddillion fel hyn:

(define (remainder n d)
  (if (< n d) n (remainder (- n d) d)))

Felly gallwn roi gweithrediad tynnu a phrawf cymharu yn lle'r gweithrediad gweddill yn llwybrau data'r peiriant GCD. Mae Ffigur 5.5 yn dangos llwybrau data a rheolydd y peiriant wedi'i ymhelaethu. Rhoddir yn lle'r cyfarwyddyd

(assign t (op rem) (reg a) (reg b))

yn niffiniad rheolydd GCD ddilyniant o gyfarwyddiadau sy'n cynnwys dolen, fel y dangosir yn Ffigur 5.6.

Ffigur 5.6: $\downarrow <!--\; \downarrow \; -->$ Dilyniant cyfarwyddiadau'r rheolydd ar gyfer y peiriant GCD yn Ffigur 5.5.

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

Ymarfer 5.3: Dyluniwch beiriant i gyfrifiannu gwreiddiau sgwâr drwy ddull Newton, fel y disgrifir yn 1.1.7:

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))

Dechreuwch drwy dybio bod y gweithrediadau good-enough? ac improve ar gael fel gweithrediadau cyntefig. Yna dangoswch sut i'w hehangu yn nhermau gweithrediadau rhifyddol. Disgrifiwch bob fersiwn o ddyluniad y peiriant sqrt drwy lunio diagram llwybr data ac ysgrifennu diffiniad rheolydd yn yr iaith peiriannau cofrestri.

5.1.3Isreolweithiau

Wrth ddylunio peiriant i gyflawni cyfrifiad, byddai'n well gennym yn aml drefnu i wahanol rannau o'r cyfrifiad rannu cydrannau yn hytrach na dyblygu'r cydrannau. Ystyriwch beiriant sy'n cynnwys dau gyfrifiad GCD—un sy'n canfod GCD cynnwys cofrestri a ac b, ac un sy'n canfod GCD cynnwys cofrestri c ac d. Gallem ddechrau drwy dybio bod gennym weithrediad cyntefig gcd, ac yna ehangu'r ddau achos o gcd yn nhermau gweithrediadau mwy cyntefig. Mae Ffigur 5.7 yn dangos dim ond rhannau GCD llwybrau data'r peiriant sy'n deillio o hyn, heb ddangos sut y maent yn cysylltu â gweddill y peiriant. Mae'r ffigur hefyd yn dangos rhannau cyfatebol dilyniant rheolydd y peiriant.

Mae gan y peiriant hwn ddau flwch gweithrediad gweddill a dau flwch ar gyfer profi hafaledd. Os yw'r cydrannau a ddyblygir yn gymhleth, fel y blwch gweddill, ni fydd hyn yn ffordd ddarbodus o adeiladu'r peiriant. Gallwn osgoi dyblygu cydrannau'r llwybr data drwy ddefnyddio'r un cydrannau ar gyfer y ddau gyfrifiad GCD, ar yr amod na fydd gwneud hynny'n effeithio ar weddill cyfrifiad y peiriant mwy. Os nad oes angen y gwerthoedd yng nghofrestri a ac b erbyn i'r rheolydd gyrraedd gcd-2 (neu os gellir symud y gwerthoedd hyn i gofrestri eraill i'w cadw'n ddiogel), gallwn newid y peiriant fel ei fod yn defnyddio cofrestri a ac b, yn hytrach na chofrestri c ac d, wrth gyfrifiannu'r ail GCD yn ogystal â'r cyntaf. Os gwnawn hyn, cawn ddilyniant y rheolydd a ddangosir yn Ffigur 5.8.

Ffigur 5.8: $\downarrow <!--\; \downarrow \; -->$ Rhannau o ddilyniant y rheolydd ar gyfer peiriant sy'n defnyddio'r un cydrannau llwybr data ar gyfer dau gyfrifiad GCD gwahanol.

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

Rydym wedi dileu'r cydrannau llwybr data dyblyg (fel bod y llwybrau data eto fel yn Ffigur 5.1), ond mae gan y rheolydd bellach ddau ddilyniant GCD sy'n wahanol yn unig o ran labeli eu pwyntiau mynediad. Byddai'n well rhoi canghennau at un dilyniant yn lle'r ddau ddilyniant hyn—sef isreolwaith gcd—ac ar ei ddiwedd canghennu'n ôl i'r man cywir yn y prif ddilyniant cyfarwyddiadau. Gallwn gyflawni hyn fel a ganlyn: cyn canghennu at gcd, rhoddwn werth gwahaniaethol (megis 0 neu 1) mewn cofrestr arbennig, continue. Ar ddiwedd yr isreolwaith gcd, dychwelwn naill ai at after-gcd-1 neu at after-gcd-2, yn dibynnu ar werth y gofrestr continue. Mae Ffigur 5.9 yn dangos y rhan berthnasol o ddilyniant y rheolydd sy'n deillio o hyn, sy'n cynnwys dim ond un copi o'r cyfarwyddiadau gcd.

Ffigur 5.9: $\downarrow <!--\; \downarrow \; -->$ Defnyddio cofrestr continue i osgoi dilyniant rheolydd dyblyg Ffigur 5.8.

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 after-gcd-1))
 (goto (label after-gcd-2))
  …
;; Before branching to gcd from
;; the first place where it is needed,
;; we place 0 in the continue register
 (assign continue (const 0))
 (goto (label gcd))
after-gcd-1
  …
;; Before the second use of gcd, 
;; we place 1 in the continue register
 (assign continue (const 1))
 (goto (label gcd))
after-gcd-2

Mae hwn yn ddull rhesymol o ymdrin â phroblemau bach, ond byddai'n lletchwith pe bai llawer o achosion o gyfrifiadau GCD yn nilyniant y rheolydd. I benderfynu ble i barhau i weithredu ar ôl yr isreolwaith gcd, byddai angen profion yn y llwybrau data a chyfarwyddiadau canghennu yn y rheolydd ar gyfer pob man sy'n defnyddio gcd. Dull mwy pwerus o weithredu isreolweithiau yw gwneud i'r gofrestr continue ddal label y pwynt mynediad yn nilyniant y rheolydd lle dylid parhau i weithredu pan fydd yr isreolwaith wedi gorffen. Mae gweithredu'r strategaeth hon yn gofyn am fath newydd o gysylltiad rhwng llwybrau data a rheolydd peiriant cofrestri: rhaid cael ffordd o aseinio label yn nilyniant y rheolydd i gofrestr fel y gellir nôl y gwerth hwn o'r gofrestr a'i ddefnyddio i barhau i weithredu yn y pwynt mynediad dynodedig.

I adlewyrchu'r gallu hwn, byddwn yn ymestyn cyfarwyddyd assign yr iaith peiriannau cofrestri i ganiatáu aseinio label o ddilyniant y rheolydd yn werth i gofrestr (fel math arbennig o gysonyn). Byddwn hefyd yn ymestyn y cyfarwyddyd goto i ganiatáu parhau i weithredu yn y pwynt mynediad a ddisgrifir gan gynnwys cofrestr, yn hytrach na dim ond mewn pwynt mynediad a ddisgrifir gan label cyson. Gan ddefnyddio'r cystrawennau newydd hyn, gallwn derfynu'r isreolwaith gcd â changen at y lleoliad sydd wedi'i storio yn y gofrestr continue. Mae hyn yn arwain at ddilyniant y rheolydd a ddangosir yn Ffigur 5.10.

Ffigur 5.10: $\downarrow <!--\; \downarrow \; -->$ Mae aseinio labeli i'r gofrestr continue yn symleiddio ac yn cyffredinoli'r strategaeth a ddangosir yn Ffigur 5.9.

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))
  …
;; Before calling gcd, 
;; we assign to continue the label
;; to which gcd should return.
 (assign continue (label after-gcd-1))
 (goto (label gcd))
after-gcd-1
  …
;; Here is the second call to gcd,
;; with a different continuation.
 (assign continue (label after-gcd-2))
 (goto (label gcd))
after-gcd-2

Gallai peiriant â mwy nag un isreolwaith ddefnyddio sawl cofrestr parhad (e.e., gcd-continue, factorial-continue), neu gallem wneud i'r holl isreolweithiau rannu un gofrestr continue. Mae rhannu'n fwy darbodus, ond rhaid bod yn ofalus os oes gennym isreolwaith (sub1) sy'n galw isreolwaith arall (sub2). Oni bai fod sub1 yn cadw cynnwys continue mewn rhyw gofrestr arall cyn gosod continue ar gyfer yr alwad i sub2, ni fydd sub1 yn gwybod ble i fynd pan fydd wedi gorffen. Mae'r mecanwaith a ddatblygir yn yr adran nesaf i ymdrin â dychweliad hefyd yn darparu ateb gwell i'r broblem hon o alwadau isreolwaith nythol.

5.1.4Defnyddio Pentwr i Weithredu Dychweliad

Gyda'r syniadau a ddangoswyd hyd yma, gallwn weithredu unrhyw broses iteru drwy bennu peiriant cofrestri sydd â chofrestr sy'n cyfateb i bob newidyn cyflwr yn y broses. Mae'r peiriant yn gweithredu dolen reolydd dro ar ôl tro, gan newid cynnwys y cofrestri, nes bod rhyw amod terfynu wedi'i fodloni. Ar bob pwynt yn nilyniant y rheolydd, pennir cyflwr y peiriant (sy'n cynrychioli cyflwr y broses iteru) yn llwyr gan gynnwys y cofrestri (gwerthoedd y newidynnau cyflwr).

Fodd bynnag, mae gweithredu prosesau dychweliadol yn gofyn am fecanwaith ychwanegol. Ystyriwch y dull dychweliadol canlynol ar gyfer cyfrifiannu ffactorialau, a archwiliasom gyntaf yn 1.2.1:

(define (factorial n)
  (if (= n 1) 
      1
      (* (factorial (- n 1)) n)))

Fel y gwelwn o'r weithdrefn, mae cyfrifiannu $n!$ yn gofyn am gyfrifiannu $(n-<!--\; -\; -->1)!$. Yn yr un modd, roedd yn rhaid i'n peiriant GCD, a fodelwyd ar y weithdrefn

(define (gcd a b)
  (if (= b 0) 
      a
      (gcd b (remainder a b))))

gyfrifiannu GCD arall. Ond mae gwahaniaeth pwysig rhwng y weithdrefn gcd, sy'n lleihau'r cyfrifiad gwreiddiol i gyfrifiad GCD newydd, ac factorial, sy'n gofyn am gyfrifiannu ffactorial arall fel isbroblem. Yn GCD, ateb y cyfrifiad GCD newydd yw ateb y broblem wreiddiol. I gyfrifiannu'r GCD nesaf, rhoddwn yr argiau newydd yng nghofrestri mewnbwn y peiriant GCD ac ailddefnyddiwn lwybrau data'r peiriant drwy weithredu'r un dilyniant rheolydd. Pan fydd y peiriant wedi gorffen datrys y broblem GCD olaf, mae wedi cwblhau'r cyfrifiad cyfan.

Yn achos ffactorial (neu unrhyw broses ddychweliadol), nid ateb y broblem wreiddiol yw ateb yr isbroblem ffactorial newydd. Rhaid lluosi'r gwerth a geir ar gyfer $(n-<!--\; -\; -->1)!$ ag $n$ i gael yr ateb terfynol. Os ceisiwn efelychu dyluniad GCD, a datrys yr isbroblem ffactorial drwy leihau'r gofrestr n ac ailredeg y peiriant ffactorial, ni fydd hen werth n ar gael inni bellach i luosi'r canlyniad ag ef. Felly mae angen ail beiriant ffactorial arnom i weithio ar yr isbroblem. Mae gan yr ail gyfrifiad ffactorial hwn ei hun isbroblem ffactorial, sy'n gofyn am drydydd peiriant ffactorial, ac ati. Gan fod pob peiriant ffactorial yn cynnwys peiriant ffactorial arall ynddo, mae'r peiriant cyfan yn cynnwys nyth anfeidraidd o beiriannau tebyg ac felly ni ellir ei adeiladu o nifer sefydlog, meidraidd o rannau.

Serch hynny, gallwn weithredu'r broses ffactorial fel peiriant cofrestri os gallwn drefnu i ddefnyddio'r un cydrannau ar gyfer pob achos nythol o'r peiriant. Yn benodol, dylai'r peiriant sy'n cyfrifiannu $n!$ ddefnyddio'r un cydrannau i weithio ar yr isbroblem o gyfrifiannu $(n-<!--\; -\; -->1)!$, ar yr isbroblem ar gyfer $(n-<!--\; -\; -->2)!$, ac ati. Mae hyn yn gredadwy oherwydd, er bod y broses ffactorial yn mynnu bod angen nifer diderfyn o gopïau o'r un peiriant i gyflawni cyfrifiad, dim ond un o'r copïau hyn sydd angen bod yn weithredol ar unrhyw adeg benodol. Pan fydd y peiriant yn dod ar draws isbroblem ddychweliadol, gall atal y gwaith ar y brif broblem dros dro, ailddefnyddio'r un rhannau ffisegol i weithio ar yr isbroblem, ac yna parhau â'r cyfrifiad a ataliwyd.

Yn yr isbroblem, bydd cynnwys y cofrestri yn wahanol i'r hyn oedd ynddynt yn y brif broblem. (Yn yr achos hwn, lleiheir y gofrestr n.) Er mwyn gallu parhau â'r cyfrifiad a ataliwyd dros dro, rhaid i'r peiriant gadw cynnwys unrhyw gofrestri y bydd eu hangen ar ôl datrys yr isbroblem, fel y gellir eu hadfer i barhau â'r cyfrifiad. Yn achos ffactorial, byddwn yn cadw hen werth n, i'w adfer pan fyddwn wedi gorffen cyfrifiannu ffactorial y gofrestr n wedi'i lleihau.²⁸⁷

Gan nad oes terfyn a priori ar ddyfnder galwadau dychweliadol nythol, efallai y bydd angen inni gadw nifer mympwyol o werthoedd cofrestri. Rhaid adfer y gwerthoedd hyn yn y drefn wrthdro i'r drefn y'u cadwyd, oherwydd mewn nyth o ddychweliadau, yr isbroblem olaf yr eir iddi yw'r gyntaf i'w gorffen. Mae hyn yn mynnu defnyddio pentwr, neu strwythur data “olaf i mewn, cyntaf allan,” i gadw gwerthoedd cofrestri. Gallwn ymestyn yr iaith peiriannau cofrestri i gynnwys pentwr drwy ychwanegu dau fath o gyfarwyddyd: rhoddir gwerthoedd ar y pentwr drwy gyfarwyddyd save, ac fe'u hadferir o'r pentwr drwy gyfarwyddyd restore. Ar ôl cadw dilyniant o werthoedd ar y pentwr drwy save, bydd dilyniant o gyfarwyddiadau restore yn adalw'r gwerthoedd hyn yn y drefn wrthdro.²⁸⁸

Gyda chymorth y pentwr, gallwn ailddefnyddio un copi o lwybrau data'r peiriant ffactorial ar gyfer pob isbroblem ffactorial. Mae mater dylunio tebyg yn codi wrth ailddefnyddio dilyniant y rheolydd sy'n gweithredu'r llwybrau data. I ailgyflawni'r cyfrifiad ffactorial, ni all y rheolydd ddolennu'n ôl i'r dechrau yn syml, fel gyda phroses iteru, oherwydd ar ôl datrys yr isbroblem $(n-<!--\; -\; -->1)!$ rhaid i'r peiriant o hyd luosi'r canlyniad ag $n$. Rhaid i'r rheolydd atal ei gyfrifiad o $n!$ dros dro, datrys yr isbroblem $(n-<!--\; -\; -->1)!$, ac yna parhau â'i gyfrifiad o $n!$. Mae'r safbwynt hwn ar y cyfrifiad ffactorial yn awgrymu defnyddio'r mecanwaith isreolwaith a ddisgrifiwyd yn 5.1.3, lle mae'r rheolydd yn defnyddio cofrestr continue i drosglwyddo i'r rhan o'r dilyniant sy'n datrys isbroblem ac yna barhau o'r man lle gadawodd y brif broblem. Felly gallwn wneud isreolwaith ffactorial sy'n dychwelyd at y pwynt mynediad sydd wedi'i storio yn y gofrestr continue. O amgylch pob galwad isreolwaith, cadwn ac adferwn continue yn union fel y gofrestr n, gan y bydd pob “lefel” o'r cyfrifiad ffactorial yn defnyddio'r un gofrestr continue. Hynny yw, rhaid i'r isreolwaith ffactorial roi gwerth newydd yn continue pan fydd yn ei alw ei hun ar gyfer isbroblem, ond bydd angen yr hen werth arno i ddychwelyd at y man a'i galwodd i ddatrys isbroblem.

Mae Ffigur 5.11 yn dangos llwybrau data a rheolydd peiriant sy'n gweithredu'r weithdrefn ddychweliadol factorial. Mae gan y peiriant bentwr a thair cofrestr, o'r enwau n, val, ac continue. I symleiddio'r diagram llwybr data, nid ydym wedi enwi'r botymau aseinio cofrestri, dim ond y botymau gweithredu pentwr (sc ac sn i gadw cofrestri, rc ac rn i adfer cofrestri). I weithredu'r peiriant, rhoddwn y rhif yr ydym am gyfrifiannu ei ffactorial yng nghofrestr n a dechreuwn y peiriant. Pan fydd y peiriant yn cyrraedd fact-done, bydd y cyfrifiad wedi gorffen a bydd yr ateb yn y gofrestr val. Yn nilyniant y rheolydd, cedwir n ac continue cyn pob galwad ddychweliadol ac fe'u hadferir wrth ddychwelyd o'r alwad. Cyflawnir dychwelyd o alwad drwy ganghennu at y lleoliad sydd wedi'i storio yn continue. Cychwynnir Continue pan fydd y peiriant yn dechrau fel y bydd y dychweliad olaf yn mynd at fact-done. Ni chedwir y gofrestr val, sy'n dal canlyniad y cyfrifiad ffactorial, cyn yr alwad ddychweliadol, oherwydd nad yw hen gynnwys val yn ddefnyddiol ar ôl i'r isreolwaith ddychwelyd. Dim ond y gwerth newydd, sef y gwerth a gynhyrchir gan yr isgyfrifiad, sydd ei angen.

Er bod y cyfrifiad ffactorial yn gofyn am beiriant anfeidraidd mewn egwyddor, mae'r peiriant yn Ffigur 5.11 yn feidraidd mewn gwirionedd heblaw am y pentwr, sydd o bosibl yn ddiderfyn. Fodd bynnag, bydd unrhyw weithrediad ffisegol penodol o bentwr o faint meidraidd, a bydd hyn yn cyfyngu ar ddyfnder y galwadau dychweliadol y gall y peiriant ymdrin â hwy. Mae'r gweithrediad hwn o ffactorial yn dangos y strategaeth gyffredinol ar gyfer gwireddu algorithmau dychweliadol fel peiriannau cofrestri cyffredin wedi'u hategu gan bentyrrau. Pan ddeuir ar draws isbroblem ddychweliadol, cadwn ar y pentwr y cofrestri y bydd angen eu gwerthoedd cyfredol ar ôl datrys yr isbroblem, datryswn yr isbroblem ddychweliadol, ac yna adferwn y cofrestri a gadwyd a pharhawn i weithredu ar y brif broblem. Rhaid cadw'r gofrestr continue bob amser. Mae p'un a oes cofrestri eraill y mae angen eu cadw yn dibynnu ar y peiriant penodol, gan nad oes angen gwerthoedd gwreiddiol cofrestri a addasir wrth ddatrys yr isbroblem ar bob cyfrifiad dychweliadol (gweler Ymarfer 5.4).

Dychweliad dwbl

Gadewch inni archwilio proses ddychweliadol fwy cymhleth, sef cyfrifiad dychweliadol coeden rhifau Fibonacci, a gyflwynasom yn 1.2.2:

(define (fib n)
  (if (< n 2) 
      n 
      (+ (fib (- n 1)) (fib (- n 2)))))

Yn union fel gyda ffactorial, gallwn weithredu'r cyfrifiad Fibonacci dychweliadol fel peiriant cofrestri â chofrestri n, val, ac continue. Mae'r peiriant yn fwy cymhleth na'r un ar gyfer ffactorial, oherwydd bod dau fan yn nilyniant y rheolydd lle mae angen cyflawni galwadau dychweliadol—unwaith i gyfrifiannu $\text{Fib}(n-<!--\; -\; -->1)$ ac unwaith i gyfrifiannu $\text{Fib}(n-<!--\; -\; -->2)$. I baratoi ar gyfer pob un o'r galwadau hyn, cadwn y cofrestri y bydd angen eu gwerthoedd yn ddiweddarach, gosodwn y gofrestr n i'r rhif y mae angen inni gyfrifiannu ei Fib yn ddychweliadol ($n-<!--\; -\; -->1$ neu $n-<!--\; -\; -->2$), ac aseiniwn i continue y pwynt mynediad yn y prif ddilyniant y dylid dychwelyd ato (afterfib-n-1 neu afterfib-n-2, yn eu trefn). Yna awn at fib-loop. Pan ddychwelwn o'r alwad ddychweliadol, mae'r ateb yn val. Mae Ffigur 5.12 yn dangos dilyniant y rheolydd ar gyfer y peiriant hwn.

Ffigur 5.12: $\downarrow <!--\; \downarrow \; -->$ Rheolydd ar gyfer peiriant i gyfrifiannu rhifau Fibonacci.

(controller
   (assign continue (label fib-done))
 fib-loop
   (test (op <) (reg n) (const 2))
   (branch (label immediate-answer))
   ;; set up to compute Fib(n − 1)
   (save continue)
   (assign continue (label afterfib-n-1))
   (save n)           ; save old value of n
   (assign n 
           (op -)
           (reg n)
           (const 1)) ; clobber n to n-1
   (goto 
    (label fib-loop)) ; perform recursive call
 afterfib-n-1 ; upon return, val contains Fib(n − 1)
   (restore n)
   (restore continue)
   ;; set up to compute Fib(n − 2)
   (assign n (op -) (reg n) (const 2))
   (save continue)
   (assign continue (label afterfib-n-2))
   (save val)         ; save Fib(n − 1)
   (goto (label fib-loop))
 afterfib-n-2 ; upon return, val contains Fib(n − 2)
   (assign n 
           (reg val)) ; n now contains Fib(n − 2)
   (restore val)      ; val now contains Fib(n − 1)
   (restore continue)
   (assign val        ; Fib(n − 1) + Fib(n − 2)
           (op +) 
           (reg val)
           (reg n))
   (goto              ; return to caller,
    (reg continue))   ; answer is in val
 immediate-answer
   (assign val 
           (reg n))   ; base case: Fib(n) = n
   (goto (reg continue))
 fib-done)

Ymarfer 5.4: Pennwch beiriannau cofrestri sy'n gweithredu pob un o'r gweithdrefnau canlynol. Ar gyfer pob peiriant, ysgrifennwch ddilyniant cyfarwyddiadau rheolydd a lluniwch ddiagram sy'n dangos y llwybrau data.

1. Esbonyddu dychweliadol:

   (define (expt b n)
     (if (= n 0)
         1
         (* b (expt b (- n 1)))))

2. Esbonyddu drwy iteru:

   (define (expt b n)
     (define (expt-iter counter product)
       (if (= counter 0)
           product
           (expt-iter (- counter 1)
                      (* b product))))
     (expt-iter n 1))

Ymarfer 5.5: Efelychwch y peiriannau ffactorial a Fibonacci â llaw, gan ddefnyddio rhyw fewnbwn nad yw'n ddibwys (sy'n gofyn am gyflawni o leiaf un alwad ddychweliadol). Dangoswch gynnwys y pentwr ar bob pwynt arwyddocaol yn y gweithredu.

Ymarfer 5.6: Mae Ben Bitdiddle yn sylwi bod gan ddilyniant rheolydd y peiriant Fibonacci un save ac un restore ychwanegol, y gellir eu tynnu i wneud peiriant cyflymach. Ble mae'r cyfarwyddiadau hyn?

5.1.5Crynodeb o'r Cyfarwyddiadau

Mae gan gyfarwyddyd rheolydd yn ein hiaith peiriannau cofrestri un o'r ffurfiau canlynol, lle mae pob $⟨inpu{t}_i⟩$ naill ai'n (reg ⟨register-name⟩) neu'n (const ⟨constant-value⟩). Cyflwynwyd y cyfarwyddiadau hyn yn 5.1.1:

(assign ⟨register-name⟩ (reg ⟨register-name⟩))
(assign ⟨register-name⟩ 
        (const ⟨constant-value⟩))
(assign ⟨register-name⟩ 
        (op ⟨operation-name⟩) 
        ⟨input₁⟩ … ⟨inputₙ⟩)
(perform (op ⟨operation-name⟩) 
         ⟨input₁⟩ 
         … 
         ⟨inputₙ⟩)
(test (op ⟨operation-name⟩) 
      ⟨input₁⟩ 
      … 
      ⟨inputₙ⟩)
(branch (label ⟨label-name⟩))
(goto (label ⟨label-name⟩))

Cyflwynwyd defnyddio cofrestri i ddal labeli yn 5.1.3:

(assign ⟨register-name⟩ (label ⟨label-name⟩))
(goto (reg ⟨register-name⟩))

Cyflwynwyd cyfarwyddiadau i ddefnyddio'r pentwr yn 5.1.4:

(save ⟨register-name⟩)
(restore ⟨register-name⟩)

Yr unig fath o ⟨constant-value⟩ a welsom hyd yma yw rhif, ond yn ddiweddarach byddwn yn defnyddio llinynnau, symbolau, a rhestrau. Er enghraifft,
(const "abc") yw'r llinyn "abc",
(const abc) yw'r symbol abc,
(const (a b c)) yw'r rhestr (a b c),
ac (const ()) yw'r rhestr wag.