5.3 Dyrannu Storfa a Chasglu Sbwriel

Yn adran 5.4, byddwn yn dangos sut i weithredu gwerthusydd Scheme fel peiriant cofrestri. Er mwyn symleiddio'r drafodaeth, byddwn yn tybio y gellir rhoi cof â strwythur rhestrau i'n peiriannau cofrestri, lle mae'r gweithrediadau sylfaenol ar gyfer trin data â strwythur rhestrau yn gyntefig. Mae tybio bod cof o'r fath yn bodoli yn haniaeth ddefnyddiol wrth ganolbwyntio ar fecanweithiau rheoli mewn dehonglydd Scheme, ond nid yw hyn yn adlewyrchu golwg realistig ar wir weithrediadau data cyntefig cyfrifiaduron cyfoes. I gael darlun mwy cyflawn o sut mae system Lisp yn gweithredu, rhaid inni ymchwilio i sut y gellir cynrychioli strwythur rhestrau mewn ffordd sy'n gydnaws â chof cyfrifiadurol confensiynol.

Mae dau beth i'w hystyried wrth weithredu strwythur rhestrau. Mater cynrychioli yn unig yw'r cyntaf: sut i gynrychioli strwythur “blychau a phwyntyddion” parau Lisp, gan ddefnyddio dim ond galluoedd storio a chyfeirio cof cyfrifiadurol nodweddiadol. Mae'r ail fater yn ymwneud â rheoli cof wrth i gyfrifiad fynd rhagddo. Mae gweithrediad system Lisp yn dibynnu'n hollbwysig ar y gallu i greu gwrthrychau data newydd yn barhaus. Mae'r rhain yn cynnwys gwrthrychau a grëir yn benodol gan y gweithdrefnau Lisp sy'n cael eu dehongli, yn ogystal â strwythurau a grëir gan y dehonglydd ei hun, megis amgylcheddau a rhestrau argiau. Er na fyddai creu gwrthrychau data newydd yn gyson yn peri problem ar gyfrifiadur â swm anfeidrol o gof y gellir ei gyrchu'n gyflym drwy gyfeiriadau, dim ond mewn meintiau meidraidd y mae cof cyfrifiadurol ar gael (yn anffodus iawn). Felly mae systemau Lisp yn darparu cyfleuster dyrannu storfa'n awtomatig i gynnal y rhith o gof anfeidrol. Pan nad oes angen gwrthrych data mwyach, ailgylchir y cof a ddyrannwyd iddo'n awtomatig a'i ddefnyddio i adeiladu gwrthrychau data newydd. Ceir amrywiol dechnegau ar gyfer darparu dyrannu storfa awtomatig o'r fath. Gelwir y dull a drafodwn yn yr adran hon yn gasglu sbwriel.

5.3.1Cof fel Fectorau

Gellir meddwl am gof cyfrifiadurol confensiynol fel arae o gilfachau, pob un yn gallu cynnwys darn o wybodaeth. Mae gan bob cilfach enw unigryw, a elwir yn gyfeiriad neu'n leoliad iddi. Mae systemau cof nodweddiadol yn darparu dau weithrediad cyntefig: un sy'n nôl y data a storir mewn lleoliad penodedig ac un sy'n aseinio data newydd i leoliad penodedig. Gellir cynyddu cyfeiriadau cof i gefnogi mynediad dilyniannol at ryw set o'r cilfachau. Yn fwy cyffredinol, mae llawer o weithrediadau data pwysig yn gofyn bod cyfeiriadau cof yn cael eu trin fel data, y gellir eu storio mewn lleoliadau cof a'u trin yng nghofrestri'r peiriant. Mae cynrychioli strwythur rhestrau yn un cymhwysiad o rifyddeg cyfeiriadau o'r fath.

I fodelu cof cyfrifiadurol, defnyddiwn fath newydd o strwythur data o'r enw fector. Yn haniaethol, gwrthrych data cyfansawdd yw fector y gellir cyrchu ei elfennau unigol drwy fynegai cyfanrifol mewn amser sy'n annibynnol ar y mynegai.²⁹⁰ Er mwyn disgrifio gweithrediadau cof, defnyddiwn ddwy weithdrefn Scheme gyntefig ar gyfer trin fectorau:

• Mae (vector-ref ⟨vector⟩ ⟨n⟩) yn dychwelyd elfen rhif $n^{\text{fed}}$ y fector.
• Mae (vector-set! ⟨vector⟩ ⟨n⟩ ⟨value⟩) yn gosod elfen rhif $n^{\text{fed}}$ y fector i'r gwerth penodedig.

Er enghraifft, os yw v yn fector, yna mae (vector-ref v 5) yn cael y pumed cofnod yn y fector v ac mae (vector-set! v 5 7) yn newid gwerth pumed cofnod y fector v i 7.²⁹¹ Ar gyfer cof cyfrifiadurol, gellir gweithredu'r mynediad hwn drwy ddefnyddio rhifyddeg cyfeiriadau i gyfuno cyfeiriad sylfaen sy'n pennu lleoliad dechrau fector yn y cof â mynegai sy'n pennu gwrthbwyso elfen benodol o'r fector.

Cynrychioli data Lisp

Gallwn ddefnyddio fectorau i weithredu'r strwythurau pâr sylfaenol sydd eu hangen ar gof â strwythur rhestrau. Gadewch inni ddychmygu bod cof y cyfrifiadur wedi'i rannu'n ddau fector: the-cars ac the-cdrs. Byddwn yn cynrychioli strwythur rhestrau fel a ganlyn: Mynegai i mewn i'r ddau fector yw pwyntydd at bâr. car y pâr yw'r cofnod yn the-cars â'r mynegai penodedig, ac cdr y pâr yw'r cofnod yn the-cdrs â'r mynegai penodedig. Mae arnom hefyd angen cynrychioliad ar gyfer gwrthrychau heblaw parau (megis rhifau a symbolau) a ffordd o wahaniaethu rhwng un math o ddata a math arall. Ceir llawer o ddulliau o gyflawni hyn, ond maent i gyd yn dibynnu yn y pen draw ar ddefnyddio pwyntyddion â math, hynny yw, ar ymestyn y syniad o “bwyntydd” i gynnwys gwybodaeth am fath data.²⁹² Mae'r math data yn galluogi'r system i wahaniaethu rhwng pwyntydd at bâr (sy'n cynnwys y math data “pâr” a mynegai i mewn i'r fectorau cof) a phwyntyddion at fathau eraill o ddata (sy'n cynnwys rhyw fath data arall a beth bynnag a ddefnyddir i gynrychioli data o'r math hwnnw). Ystyrir bod dau wrthrych data yr un fath (eq?) os yw eu pwyntyddion yn unfath.²⁹³ Mae Ffigur 5.14 yn dangos defnyddio'r dull hwn i gynrychioli'r rhestr ((1 2) 3 4), y dangosir ei diagram blychau a phwyntyddion hefyd. Defnyddiwn ragddodiaid llythrennau i ddynodi gwybodaeth y math data. Felly, dynodir pwyntydd at y pâr â mynegai 5 gan p5, dynodir y rhestr wag gan y pwyntydd e0, a dynodir pwyntydd at y rhif 4 gan n4. Yn y diagram blychau a phwyntyddion, rydym wedi nodi yng nghornel chwith isaf pob pâr y mynegai fector sy'n pennu ble y storir car ac cdr y pâr. Gall y lleoliadau gwag yn the-cars ac the-cdrs gynnwys rhannau o strwythurau rhestrau eraill (nad ydynt o ddiddordeb yma).

Gallai pwyntydd at rif, megis n4, gynnwys math sy'n dynodi data rhifiadol ynghyd â chynrychioliad gwirioneddol y rhif 4.²⁹⁴ I ymdrin â rhifau sy'n rhy fawr i'w cynrychioli yn y swm sefydlog o ofod a ddyrannir i un pwyntydd, gallem ddefnyddio math data bignum ar wahân, y mae ei bwyntydd yn dynodi rhestr lle storir rhannau'r rhif.²⁹⁵

Gellid cynrychioli symbol yn bwyntydd â math sy'n dynodi dilyniant y nodau sy'n ffurfio cynrychioliad argraffedig y symbol. Adeiledir y dilyniant hwn gan ddarllenydd Lisp pan geir y llinyn nodau gyntaf yn y mewnbwn. Gan ein bod am i ddau achos o symbol gael eu hadnabod yn “yr un” symbol gan eq?, ac am i eq? fod yn brawf syml o hafaledd pwyntyddion, rhaid inni sicrhau, os yw'r darllenydd yn gweld yr un llinyn nodau ddwywaith, y bydd yn defnyddio'r un pwyntydd (at yr un dilyniant nodau) i gynrychioli'r ddau ymddangosiad. I gyflawni hyn, mae'r darllenydd yn cadw tabl, a elwir yn draddodiadol yn obarray, o'r holl symbolau y mae wedi'u gweld erioed. Pan fydd y darllenydd yn dod ar draws llinyn nodau ac ar fin adeiladu symbol, mae'n gwirio'r obarray i weld a yw wedi gweld yr un llinyn nodau o'r blaen. Os nad yw, mae'n defnyddio'r nodau i adeiladu symbol newydd (pwyntydd â math at ddilyniant nodau newydd) ac yn rhoi'r pwyntydd hwn yn yr obarray. Os yw'r darllenydd wedi gweld y llinyn o'r blaen, mae'n dychwelyd y pwyntydd symbol a storir yn yr obarray. Gelwir y broses hon o roi pwyntyddion unigryw yn lle llinynnau nodau yn mewnoli symbolau (interning).

Gweithredu'r gweithrediadau rhestrau cyntefig

O gael y cynllun cynrychioli uchod, gallwn ddisodli pob gweithrediad rhestrau “cyntefig” mewn peiriant cofrestri ag un neu ragor o weithrediadau fector cyntefig. Defnyddiwn ddwy gofrestr, the-cars ac the-cdrs, i adnabod y fectorau cof, a thybiwn fod vector-ref ac vector-set! ar gael yn weithrediadau cyntefig. Tybiwn hefyd fod gweithrediadau rhifiadol ar bwyntyddion (megis cynyddu pwyntydd, defnyddio pwyntydd pâr i fynegeio fector, neu adio dau rif) yn defnyddio rhan mynegai'r pwyntydd â math yn unig.

Er enghraifft, gallwn wneud i beiriant cofrestri gefnogi'r cyfarwyddiadau

(assign ⟨reg₁⟩ (op car) (reg ⟨reg₂⟩))
(assign ⟨reg₁⟩ (op cdr) (reg ⟨reg₂⟩))

os gweithredwn y rhain, yn y drefn honno, fel

(assign ⟨reg₁⟩ 
        (op vector-ref)
        (reg the-cars)
        (reg ⟨reg₂⟩))
(assign ⟨reg₁⟩
        (op vector-ref)
        (reg the-cdrs)
        (reg ⟨reg₂⟩))

Gweithredir y cyfarwyddiadau

(perform (op set-car!) (reg ⟨reg₁⟩) (reg ⟨reg₂⟩))
(perform (op set-cdr!) (reg ⟨reg₁⟩) (reg ⟨reg₂⟩))

fel

(perform (op vector-set!)
         (reg the-cars)
         (reg ⟨reg₁⟩)
         (reg ⟨reg₂⟩))
(perform (op vector-set!)
         (reg the-cdrs)
         (reg ⟨reg₁⟩)
         (reg ⟨reg₂⟩))

Cyflawnir Cons drwy ddyrannu mynegai nas defnyddiwyd a storio'r argiau i cons yn the-cars ac the-cdrs yn y safle fector a fynegeir felly. Tybiwn fod cofrestr arbennig, free, sydd bob amser yn dal pwyntydd pâr sy'n cynnwys y mynegai nesaf sydd ar gael, ac y gallwn gynyddu rhan mynegai'r pwyntydd hwnnw i ganfod y lleoliad rhydd nesaf.²⁹⁶ Er enghraifft, gweithredir y cyfarwyddyd

(assign ⟨reg₁⟩
        (op cons)
        (reg ⟨reg₂⟩)
        (reg ⟨reg₃⟩))

fel y dilyniant canlynol o weithrediadau fector:²⁹⁷

(perform (op vector-set!)
         (reg the-cars)
         (reg free)
         (reg ⟨reg₂⟩))
(perform (op vector-set!)
         (reg the-cdrs)
         (reg free)
         (reg ⟨reg₃⟩))
(assign ⟨reg₁⟩ (reg free))
(assign free (op +) (reg free) (const 1))

Mae'r gweithrediad eq?

(op eq?) (reg ⟨reg₁⟩) (reg ⟨reg₂⟩)

yn profi hafaledd yr holl feysydd yn y cofrestri yn unig, a dim ond y maes math y mae angen i draethiadau megis pair?, null?, symbol?, ac number? ei wirio.

Gweithredu pentyrrau

Er bod ein peiriannau cofrestri yn defnyddio pentyrrau, nid oes angen inni wneud dim byd arbennig yma, gan y gellir modelu pentyrrau yn nhermau rhestrau. Gall y pentwr fod yn rhestr o'r gwerthoedd a gadwyd, gyda chofrestr arbennig the-stack yn pwyntio ati. Felly, gellir gweithredu (save ⟨reg⟩) fel

(assign the-stack 
        (op cons)
        (reg ⟨reg⟩)
        (reg the-stack))

Yn yr un modd, gellir gweithredu (restore ⟨reg⟩) fel

(assign ⟨reg⟩ (op car) (reg the-stack))
(assign the-stack (op cdr) (reg the-stack))

a gellir gweithredu (perform (op initialize-stack)) fel

(assign the-stack (const ()))

Gellir ehangu'r gweithrediadau hyn ymhellach yn nhermau'r gweithrediadau fector a roddwyd uchod. Mewn pensaernïaeth gyfrifiadurol gonfensiynol, fodd bynnag, mae fel arfer yn fanteisiol dyrannu'r pentwr yn fector ar wahân. Yna gellir cyflawni gwthio ar y pentwr a thynnu oddi arno drwy gynyddu neu leihau mynegai i mewn i'r fector hwnnw.

Ymarfer 5.20: Tynnwch gynrychioliad blychau a phwyntyddion a chynrychioliad fectorau cof (fel yn Ffigur 5.14) o'r strwythur rhestrau a gynhyrchir gan

(define x (cons 1 2))
(define y (list x x))

gyda'r pwyntydd free yn p1 i ddechrau. Beth yw gwerth terfynol free? Pa bwyntyddion sy'n cynrychioli gwerthoedd x ac y?

Ymarfer 5.21: Gweithredwch beiriannau cofrestri ar gyfer y gweithdrefnau canlynol. Tybiwch fod y gweithrediadau cof â strwythur rhestrau ar gael yn weithrediadau cyntefig y peiriant.

1. count-leaves dychweliadol:

   (define (count-leaves tree)
     (cond ((null? tree) 0)
           ((not (pair? tree)) 1)
           (else 
            (+ (count-leaves (car tree))
               (count-leaves (cdr tree))))))

2. count-leaves dychweliadol â rhifydd penodol:

   (define (count-leaves tree)
     (define (count-iter tree n)
       (cond ((null? tree) n)
             ((not (pair? tree)) (+ n 1))
             (else 
              (count-iter 
               (cdr tree)
               (count-iter (car tree) 
                           n)))))
     (count-iter tree 0))

Ymarfer 5.22: Cyflwynodd Ymarfer 3.12 yn 3.3.1 weithdrefn append sy'n atodi dwy restr i ffurfio rhestr newydd a gweithdrefn append! sy'n cysylltu dwy restr â'i gilydd. Dyluniwch beiriant cofrestri i weithredu pob un o'r gweithdrefnau hyn. Tybiwch fod y gweithrediadau cof â strwythur rhestrau ar gael yn weithrediadau cyntefig.

5.3.2Cynnal y Rhith o Gof Anfeidrol

Mae'r dull cynrychioli a amlinellir yn 5.3.1 yn datrys y broblem o weithredu strwythur rhestrau, ar yr amod bod gennym swm anfeidrol o gof. Gyda chyfrifiadur go iawn, byddwn yn rhedeg allan o ofod rhydd i adeiladu parau newydd ynddo yn y pen draw.²⁹⁸ Fodd bynnag, dim ond i ddal canlyniadau canolradd y defnyddir y rhan fwyaf o'r parau a gynhyrchir mewn cyfrifiad nodweddiadol. Ar ôl cyrchu'r canlyniadau hyn, nid oes angen y parau mwyach— sbwriel ydynt. Er enghraifft, mae'r cyfrifiad

(accumulate 
 + 
 0
 (filter odd? (enumerate-interval 0 n)))

yn adeiladu dwy restr: y rhifiad a chanlyniad hidlo'r rhifiad. Pan fydd y cronni wedi'i gwblhau, nid oes angen y rhestrau hyn mwyach, a gellir adennill y cof a ddyrannwyd. Os gallwn drefnu casglu'r holl sbwriel o bryd i'w gilydd, ac os yw hyn yn ailgylchu cof tua'r un gyfradd ag y byddwn yn adeiladu parau newydd, byddwn wedi cadw'r rhith bod swm anfeidrol o gof.

Er mwyn ailgylchu parau, rhaid inni gael ffordd o bennu pa barau a ddyrannwyd nad oes eu hangen (yn yr ystyr na all eu cynnwys ddylanwadu mwyach ar ddyfodol y cyfrifiad). Gelwir y dull y byddwn yn ei archwilio i gyflawni hyn yn gasglu sbwriel. Mae casglu sbwriel yn seiliedig ar y sylw mai'r unig wrthrychau a all effeithio ar ddyfodol y cyfrifiad, ar unrhyw adeg wrth ddehongli Lisp, yw'r rhai y gellir eu cyrraedd drwy ryw ddilyniant o weithrediadau car ac cdr gan ddechrau o'r pwyntyddion sydd yng nghofrestri'r peiriant ar hyn o bryd.²⁹⁹ Gellir ailgylchu unrhyw gell gof nad yw'n hygyrch fel hyn.

Ceir llawer o ffyrdd o gasglu sbwriel. Gelwir y dull y byddwn yn ei archwilio yma yn atal a chopïo. Y syniad sylfaenol yw rhannu'r cof yn ddau hanner: “cof gweithio” a “chof rhydd.” Pan fydd cons yn adeiladu parau, mae'n eu dyrannu yn y cof gweithio. Pan fo'r cof gweithio'n llawn, casglwn sbwriel drwy leoli'r holl barau defnyddiol yn y cof gweithio a'u copïo i leoliadau olynol yn y cof rhydd. (Lleolir y parau defnyddiol drwy olrhain yr holl bwyntyddion car ac cdr, gan ddechrau â chofrestri'r peiriant.) Gan nad ydym yn copïo'r sbwriel, mae'n debyg y bydd cof rhydd ychwanegol y gallwn ei ddefnyddio i ddyrannu parau newydd. Yn ogystal, nid oes angen dim yn y cof gweithio, gan fod yr holl barau defnyddiol ynddo wedi'u copïo. Felly, os cyfnewidiwn rolau'r cof gweithio a'r cof rhydd, gallwn barhau i brosesu; dyrennir parau newydd yn y cof gweithio newydd (sef yr hen gof rhydd). Pan fydd hwn yn llawn, gallwn gopïo'r parau defnyddiol i'r cof rhydd newydd (sef yr hen gof gweithio).³⁰⁰

Gweithredu casglwr sbwriel atal a chopïo

Defnyddiwn ein hiaith peiriant cofrestri nawr i ddisgrifio'r algorithm atal a chopïo'n fanylach. Byddwn yn tybio bod cofrestr o'r enw root sy'n cynnwys pwyntydd at strwythur sy'n pwyntio yn y pen draw at yr holl ddata hygyrch. Gellir trefnu hyn drwy storio cynnwys holl gofrestri'r peiriant mewn rhestr a ddyrannwyd ymlaen llaw y mae root yn pwyntio ati, yn union cyn dechrau casglu sbwriel.³⁰¹ Tybiwn hefyd fod cof rhydd ar gael, yn ogystal â'r cof gweithio presennol, y gallwn gopïo'r data defnyddiol iddo. Mae'r cof gweithio presennol yn cynnwys fectorau y mae eu cyfeiriadau sylfaen mewn cofrestri o'r enw the-cars ac the-cdrs, ac mae'r cof rhydd mewn cofrestri o'r enw new-cars ac new-cdrs.

Sbardunir casglu sbwriel pan ddefnyddiwn yr holl gelloedd rhydd yn y cof gweithio presennol, hynny yw, pan fydd gweithrediad cons yn ceisio cynyddu'r pwyntydd free y tu hwnt i ddiwedd y fector cof. Pan fydd y broses casglu sbwriel wedi'i chwblhau, bydd y pwyntydd root yn pwyntio i'r cof newydd, bydd yr holl wrthrychau y gellir eu cyrchu o'r root wedi'u symud i'r cof newydd, a bydd y pwyntydd free yn dynodi'r man nesaf yn y cof newydd lle gellir dyrannu pâr newydd. Yn ogystal, bydd rolau'r cof gweithio a'r cof newydd wedi'u cyfnewid—adeiledir parau newydd yn y cof newydd, gan ddechrau yn y man a ddynodir gan free, a bydd yr hen gof gweithio ar gael yn gof newydd ar gyfer y casglu sbwriel nesaf. Mae Ffigur 5.15 yn dangos trefniant y cof yn union cyn ac yn union ar ôl casglu sbwriel.

Rheolir cyflwr y broses casglu sbwriel drwy gadw dau bwyntydd: free ac scan. Cychwynnir y rhain i bwyntio at ddechrau'r cof newydd. Mae'r algorithm yn dechrau drwy adleoli'r pâr y mae root yn pwyntio ato i ddechrau'r cof newydd. Copïir y pâr, addasir y pwyntydd root i bwyntio at y lleoliad newydd, a chynyddir y pwyntydd free. Yn ogystal, marcir hen leoliad y pâr i ddangos bod ei gynnwys wedi'i symud. Gwneir y marcio hwn fel a ganlyn: Yn y safle car, rhown dag arbennig sy'n dynodi mai gwrthrych sydd eisoes wedi'i symud yw hwn. (Yn draddodiadol gelwir gwrthrych o'r fath yn galon doredig.)³⁰² Yn y safle cdr rhown gyfeiriad ailgyfeirio sy'n pwyntio at y lleoliad y symudwyd y gwrthrych iddo.

Ar ôl adleoli'r gwraidd, mae'r casglwr sbwriel yn mynd i mewn i'w gylch sylfaenol. Ar bob cam yn yr algorithm, mae'r pwyntydd scan (sy'n pwyntio at y gwraidd wedi'i adleoli i ddechrau) yn pwyntio at bâr sydd wedi'i symud i'r cof newydd ond y mae ei bwyntyddion car ac cdr yn dal i gyfeirio at wrthrychau yn yr hen gof. Adleolir pob un o'r gwrthrychau hyn, a chynyddir y pwyntydd scan. I adleoli gwrthrych (er enghraifft, y gwrthrych a ddynodir gan bwyntydd car y pâr rydym yn ei sganio), gwiriwn a yw'r gwrthrych wedi'i symud eisoes (fel y dynodir gan bresenoldeb tag calon doredig yn safle car y gwrthrych). Os nad yw'r gwrthrych wedi'i symud eisoes, copïwn ef i'r man a ddynodir gan free, diweddarwn free, sefydlwn galon doredig yn hen leoliad y gwrthrych, a diweddarwn y pwyntydd at y gwrthrych (yn yr enghraifft hon, pwyntydd car y pâr rydym yn ei sganio) i bwyntio at y lleoliad newydd. Os yw'r gwrthrych wedi'i symud eisoes, rhoddir ei gyfeiriad ailgyfeirio (a geir yn safle cdr y galon doredig) yn lle'r pwyntydd yn y pâr sy'n cael ei sganio. Yn y pen draw, bydd yr holl wrthrychau hygyrch wedi'u symud a'u sganio, ac ar y pwynt hwnnw bydd y pwyntydd scan yn dal y pwyntydd free a bydd y broses yn dod i ben.

Gallwn bennu'r algorithm atal a chopïo fel dilyniant o gyfarwyddiadau ar gyfer peiriant cofrestri. Cyflawnir y cam sylfaenol o adleoli gwrthrych gan isreolwaith o'r enw relocate-old-result-in-new. Mae'r isreolwaith hwn yn cael ei arg, pwyntydd at y gwrthrych sydd i'w adleoli, o gofrestr o'r enw old. Mae'n adleoli'r gwrthrych penodedig (gan gynyddu free yn y broses), yn rhoi pwyntydd at y gwrthrych wedi'i adleoli mewn cofrestr o'r enw new, ac yn dychwelyd drwy ganghennu i'r pwynt mynediad a storir yn y gofrestr relocate-continue. I ddechrau casglu sbwriel, galwn yr isreolwaith hwn i adleoli'r pwyntydd root, ar ôl cychwyn free ac scan. Pan gyflawnir adleoli root, gosodwn y pwyntydd newydd yn root newydd ac awn i mewn i brif ddolen y casglwr sbwriel.

begin-garbage-collection
  (assign free (const 0))
  (assign scan (const 0))
  (assign old (reg root))
  (assign relocate-continue 
          (label reassign-root))
  (goto (label relocate-old-result-in-new))
reassign-root
  (assign root (reg new))
  (goto (label gc-loop))

Ym mhrif ddolen y casglwr sbwriel rhaid inni bennu a oes rhagor o wrthrychau i'w sganio. Gwnawn hyn drwy brofi a yw'r pwyntydd scan yn cyd-daro â'r pwyntydd free. Os yw'r pwyntyddion yn hafal, yna mae'r holl wrthrychau hygyrch wedi'u hadleoli, a changhennwn i gc-flip, sy'n rhoi trefn ar bethau fel y gallwn barhau â'r cyfrifiad y torrwyd ar ei draws. Os oes parau i'w sganio o hyd, galwn yr isreolwaith adleoli i adleoli car y pâr nesaf (drwy roi'r pwyntydd car yn old). Gosodir y gofrestr relocate-continue fel y bydd yr isreolwaith yn dychwelyd i ddiweddaru'r pwyntydd car.

gc-loop
  (test (op =) (reg scan) (reg free))
  (branch (label gc-flip))
  (assign old 
          (op vector-ref)
          (reg new-cars)
          (reg scan))
  (assign relocate-continue 
          (label update-car))
  (goto (label relocate-old-result-in-new))

Yn update-car, addaswn bwyntydd car y pâr sy'n cael ei sganio, yna awn ymlaen i adleoli cdr y pâr. Dychwelwn i update-cdr pan gyflawnir yr adleoli hwnnw. Ar ôl adleoli a diweddaru'r cdr, rydym wedi gorffen sganio'r pâr hwnnw, felly parhawn â'r brif ddolen.

update-car
  (perform (op vector-set!)
           (reg new-cars)
           (reg scan)
           (reg new))
  (assign  old 
           (op vector-ref)
           (reg new-cdrs)
           (reg scan))
  (assign  relocate-continue
           (label update-cdr))
  (goto (label relocate-old-result-in-new))
update-cdr
  (perform (op vector-set!)
           (reg new-cdrs)
           (reg scan)
           (reg new))
  (assign  scan (op +) (reg scan) (const 1))
  (goto (label gc-loop))

Mae'r isreolwaith relocate-old-result-in-new yn adleoli gwrthrychau fel a ganlyn: Os nad pâr yw'r gwrthrych sydd i'w adleoli (y mae old yn pwyntio ato), yna dychwelwn yr un pwyntydd at y gwrthrych heb ei newid (yn new). (Er enghraifft, gallem fod yn sganio pâr y mae ei car yn rhif 4. Os cynrychiolwn yr car gan n4, fel y disgrifir yn 5.3.1, yna rydym am i'r pwyntydd car “wedi'i adleoli” fod yn n4 o hyd.) Fel arall, rhaid inni gyflawni'r adleoli. Os yw safle car y pâr sydd i'w adleoli yn cynnwys tag calon doredig, yna mae'r pâr eisoes wedi'i symud mewn gwirionedd, felly adferwn y cyfeiriad ailgyfeirio (o safle cdr y galon doredig) a dychwelwn hwn yn new. Os yw'r pwyntydd yn old yn pwyntio at bâr nad yw wedi'i symud eto, yna symudwn y pâr i'r gell rydd gyntaf yn y cof newydd (y mae free yn pwyntio ati) a sefydlwn y galon doredig drwy storio tag calon doredig a chyfeiriad ailgyfeirio yn yr hen leoliad. Mae Relocate-old-result-in-new yn defnyddio cofrestr oldcr i ddal car neu cdr y gwrthrych y mae old yn pwyntio ato.³⁰³

relocate-old-result-in-new
  (test (op pointer-to-pair?) (reg old))
  (branch (label pair))
  (assign new (reg old))
  (goto (reg relocate-continue))
pair
  (assign  oldcr 
           (op vector-ref)
           (reg the-cars)
           (reg old))
  (test (op broken-heart?) (reg oldcr))
  (branch  (label already-moved))
  (assign  new (reg free)) ; new location for pair
  ;; Update free pointer.
  (assign free (op +) (reg free) (const 1))
  ;; Copy the car and cdr to new memory.
  (perform (op vector-set!)
           (reg new-cars)
           (reg new)
           (reg oldcr))
  (assign  oldcr 
           (op vector-ref)
           (reg the-cdrs)
           (reg old))
  (perform (op vector-set!)
           (reg new-cdrs)
           (reg new)
           (reg oldcr))
  ;; Construct the broken heart.
  (perform (op vector-set!)
           (reg the-cars)
           (reg old)
           (const broken-heart))
  (perform (op vector-set!)
           (reg the-cdrs)
           (reg old)
           (reg new))
  (goto (reg relocate-continue))
already-moved
  (assign  new
           (op vector-ref)
           (reg the-cdrs)
           (reg old))
  (goto (reg relocate-continue))

Ar ddiwedd y broses casglu sbwriel, cyfnewidiwn rôl yr hen gof a'r cof newydd drwy gyfnewid pwyntyddion: cyfnewid the-cars ag new-cars, ac the-cdrs ag new-cdrs. Yna byddwn yn barod i gasglu sbwriel eto y tro nesaf y bydd y cof yn rhedeg allan.

gc-flip
  (assign temp (reg the-cdrs))
  (assign the-cdrs (reg new-cdrs))
  (assign new-cdrs (reg temp))
  (assign temp (reg the-cars))
  (assign the-cars (reg new-cars))
  (assign new-cars (reg temp))