SICP · Yr ail argraffiad · Scheme

5.5 Crynhoi

Harold Abelson a Gerald Jay Sussman gyda Julie Sussman · Cyfieithiad Cymraeg

Mae gwerthusydd rheolaeth eglur 5.4 yn beiriant cofrestri y mae ei reolydd yn dehongli rhaglenni Scheme. Yn yr adran hon gwelwn sut i redeg rhaglenni Scheme ar beiriant cofrestri nad yw ei reolydd yn ddehonglydd Scheme.

Mae peiriant y gwerthusydd rheolaeth eglur yn gyffredinol—gall gyflawni unrhyw broses gyfrifiadurol y gellir ei disgrifio yn Scheme. Mae rheolydd y gwerthusydd yn trefnu’r defnydd o’i lwybrau data i gyflawni’r cyfrifiad a ddymunir. Felly, mae llwybrau data’r gwerthusydd yn gyffredinol: Maent yn ddigonol i gyflawni unrhyw gyfrifiad a ddymunwn, o gael rheolydd priodol.³¹⁸

Mae cyfrifiaduron masnachol at ddibenion cyffredinol yn beiriannau cofrestri wedi’u trefnu o amgylch casgliad o gofrestri a gweithrediadau sy’n ffurfio set gyffredinol effeithlon a chyfleus o lwybrau data. Dehonglydd ar gyfer iaith peiriant cofrestri fel yr un yr ydym wedi bod yn ei defnyddio yw rheolydd peiriant at ddibenion cyffredinol. Gelwir yr iaith hon yn iaith frodorol y peiriant, neu’n iaith beiriant yn syml. Mae rhaglenni a ysgrifennir mewn iaith beiriant yn ddilyniannau o gyfarwyddiadau sy’n defnyddio llwybrau data’r peiriant. Er enghraifft, gellir meddwl am ddilyniant cyfarwyddiadau’r gwerthusydd rheolaeth eglur fel rhaglen iaith beiriant ar gyfer cyfrifiadur at ddibenion cyffredinol yn hytrach nag fel rheolydd peiriant dehongli arbenigol.

Mae dwy strategaeth gyffredin ar gyfer pontio’r bwlch rhwng ieithoedd lefel uwch ac ieithoedd peiriannau cofrestri. Mae’r gwerthusydd rheolaeth eglur yn dangos strategaeth dehongli. Mae dehonglydd a ysgrifennir yn iaith frodorol peiriant yn ffurfweddu’r peiriant i weithredu rhaglenni a ysgrifennwyd mewn iaith (a elwir yn iaith ffynhonnell) a all fod yn wahanol i iaith frodorol y peiriant sy’n cyflawni’r gwerthuso. Gweithredir gweithdrefnau cyntefig yr iaith ffynhonnell fel llyfrgell o is-reolweithiau a ysgrifennwyd yn iaith frodorol y peiriant penodol. Cynrychiolir rhaglen sydd i’w dehongli (a elwir yn rhaglen ffynhonnell) fel strwythur data. Mae’r dehonglydd yn croesi’r strwythur data hwn, gan ddadansoddi’r rhaglen ffynhonnell. Wrth wneud hynny, mae’n efelychu ymddygiad bwriadedig y rhaglen ffynhonnell drwy alw is-reolweithiau cyntefig priodol o’r llyfrgell.

Yn yr adran hon, archwiliwn y strategaeth amgen o grynhoi. Mae crynhoydd ar gyfer iaith ffynhonnell a pheiriant penodol yn trosi rhaglen ffynhonnell yn rhaglen gyfwerth (a elwir yn rhaglen wrthrych) a ysgrifennwyd yn iaith frodorol y peiriant. Mae’r crynhoydd a weithredwn yn yr adran hon yn trosi rhaglenni a ysgrifennwyd yn Scheme yn ddilyniannau o gyfarwyddiadau i’w gweithredu gan ddefnyddio llwybrau data peiriant y gwerthusydd rheolaeth eglur.³¹⁹

O gymharu â dehongli, gall crynhoi gynyddu effeithlonrwydd gweithredu rhaglenni’n fawr, fel yr esboniwn isod yn y trosolwg o’r crynhoydd. Ar y llaw arall, mae dehonglydd yn darparu amgylchedd mwy pwerus ar gyfer datblygu a dadfygio rhaglenni’n rhyngweithiol, oherwydd bod y rhaglen ffynhonnell sy’n cael ei gweithredu ar gael adeg rhedeg i’w harchwilio a’i haddasu. Yn ogystal, oherwydd bod y llyfrgell gyfan o weithdrefnau cyntefig yn bresennol, gellir adeiladu rhaglenni newydd a’u hychwanegu at y system yn ystod dadfygio.

O ystyried manteision cyflenwol crynhoi a dehongli, mae amgylcheddau datblygu rhaglenni modern yn dilyn strategaeth gymysg. Fel arfer trefnir dehonglwyr Lisp fel y gall gweithdrefnau wedi’u dehongli a gweithdrefnau wedi’u crynhoi alw ei gilydd. Mae hyn yn galluogi rhaglennydd i grynhoi’r rhannau hynny o raglen y tybir eu bod wedi’u dadfygio, gan felly ennill mantais effeithlonrwydd crynhoi, a chadw’r modd gweithredu drwy ddehongli ar gyfer y rhannau hynny o’r rhaglen sy’n dal i newid drwy ddatblygu a dadfygio rhyngweithiol. Yn 5.5.7, ar ôl inni weithredu’r crynhoydd, dangoswn sut i’w gysylltu â’n dehonglydd i gynhyrchu system ddatblygu integredig o ddehonglydd a chrynhoydd.

Trosolwg o’r crynhoydd

Mae ein crynhoydd yn debyg iawn i’n dehonglydd, o ran ei strwythur ac o ran y swyddogaeth y mae’n ei chyflawni. Yn unol â hynny, bydd y mecanweithiau a ddefnyddir gan y crynhoydd i ddadansoddi mynegiadau’n debyg i’r rhai a ddefnyddir gan y dehonglydd. Ymhellach, er mwyn ei gwneud yn hawdd cysylltu cod wedi’i grynhoi a chod wedi’i ddehongli, dyluniwn y crynhoydd i gynhyrchu cod sy’n dilyn yr un confensiynau o ran defnyddio cofrestri â’r dehonglydd: Cedwir yr amgylchedd yn y gofrestr env, cronnir rhestrau argiau yn argl, bydd gweithdrefn sydd i’w chymhwyso yn proc, bydd gweithdrefnau’n dychwelyd eu hatebion yn val, a chedwir y lleoliad y dylai gweithdrefn ddychwelyd iddo yn continue. Yn gyffredinol, mae’r crynhoydd yn trosi rhaglen ffynhonnell yn rhaglen wrthrych sy’n cyflawni, yn ei hanfod, yr un gweithrediadau cofrestri ag y byddai’r dehonglydd yn eu cyflawni wrth werthuso’r un rhaglen ffynhonnell.

Mae’r disgrifiad hwn yn awgrymu strategaeth ar gyfer gweithredu crynhoydd elfennol: Croeswn y mynegiad yn yr un ffordd â’r dehonglydd. Pan ddown ar draws cyfarwyddyd cofrestr y byddai’r dehonglydd yn ei gyflawni wrth werthuso’r mynegiad, ni weithredwn y cyfarwyddyd ond yn hytrach ei gronni mewn dilyniant. Y dilyniant cyfarwyddiadau sy’n deillio o hyn fydd y cod gwrthrych. Sylwch ar fantais effeithlonrwydd crynhoi dros ddehongli. Bob tro y mae’r dehonglydd yn gwerthuso mynegiad—er enghraifft, (f 84 96)—mae’n gwneud y gwaith o ddosbarthu’r mynegiad (gan ddarganfod mai cymhwysiad gweithdrefn yw hwn) a phrofi am ddiwedd rhestr yr operandau (gan ddarganfod bod dau operand). Gyda chrynhoydd, dim ond unwaith y dadansoddir y mynegiad, pan gynhyrchir y dilyniant cyfarwyddiadau adeg crynhoi. Mae’r cod gwrthrych a gynhyrchir gan y crynhoydd yn cynnwys dim ond y cyfarwyddiadau sy’n gwerthuso’r gweithredydd a’r ddau operand, yn cydosod y rhestr argiau, ac yn cymhwyso’r weithdrefn (yn proc) i’r argiau (yn argl).

Dyma’r un math o optimeiddio ag a weithredasom yng ngwerthusydd dadansoddi 4.1.7. Ond mae cyfleoedd pellach i gynyddu effeithlonrwydd mewn cod wedi’i grynhoi. Wrth i’r dehonglydd redeg, mae’n dilyn proses y mae rhaid iddi fod yn gymwys i unrhyw fynegiad yn yr iaith. Mewn cyferbyniad, bwriedir i ddarn penodol o god wedi’i grynhoi weithredu rhyw fynegiad penodol. Gall hyn wneud gwahaniaeth mawr, er enghraifft wrth ddefnyddio’r pentwr i gadw cofrestri. Pan fydd y dehonglydd yn gwerthuso mynegiad, rhaid iddo fod yn barod ar gyfer unrhyw bosibilrwydd. Cyn gwerthuso is-fynegiad, mae’r dehonglydd yn cadw’r holl gofrestri y bydd eu hangen yn ddiweddarach, oherwydd y gallai’r is-fynegiad ofyn am werthuso mympwyol. Ar y llaw arall, gall crynhoydd fanteisio ar strwythur y mynegiad penodol y mae’n ei brosesu i gynhyrchu cod sy’n osgoi gweithrediadau pentwr diangen.

Fel enghraifft, ystyriwch y cyfuniad (f 84 96). Cyn i’r dehonglydd werthuso gweithredydd y cyfuniad, mae’n paratoi ar gyfer y gwerthuso hwn drwy gadw’r cofrestri sy’n cynnwys yr operandau a’r amgylchedd, y bydd angen eu gwerthoedd yn ddiweddarach. Yna mae’r dehonglydd yn gwerthuso’r gweithredydd i gael y canlyniad yn val, yn adfer y cofrestri a gadwyd, ac yn olaf yn symud y canlyniad o val i proc. Fodd bynnag, yn y mynegiad penodol yr ydym yn ymdrin ag ef, y gweithredydd yw’r symbol f, a gyflawnir ei werthuso gan y gweithrediad peiriant lookup-variable-value, nad yw’n newid unrhyw gofrestri. Bydd y crynhoydd a weithredwn yn yr adran hon yn manteisio ar y ffaith hon ac yn cynhyrchu cod sy’n gwerthuso’r gweithredydd gan ddefnyddio’r cyfarwyddyd

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

Mae’r cod hwn nid yn unig yn osgoi’r cadw a’r adfer diangen ond hefyd yn aseinio gwerth y chwilio’n uniongyrchol i proc, tra byddai’r dehonglydd yn cael y canlyniad yn val ac yna’n ei symud i proc.

Gall crynhoydd hefyd optimeiddio cyrchu’r amgylchedd. Ar ôl dadansoddi’r cod, gall y crynhoydd wybod mewn llawer o achosion ym mha ffrâm y bydd newidyn penodol wedi’i leoli a chyrchu’r ffrâm honno’n uniongyrchol, yn hytrach na chyflawni’r chwiliad lookup-variable-value. Byddwn yn trafod sut i weithredu cyrchu newidynnau o’r fath yn 5.5.6. Tan hynny, fodd bynnag, canolbwyntiwn ar y math o optimeiddio cofrestri a phentwr a ddisgrifiwyd uchod. Gall crynhoydd gyflawni llawer o optimeiddiadau eraill, megis mewnlinio cod gweithrediadau cyntefig yn lle defnyddio mecanwaith apply cyffredinol (gweler Ymarfer 5.38); ond ni fyddwn yn pwysleisio’r rhain yma. Ein prif nod yn yr adran hon yw dangos y broses grynhoi mewn cyd-destun wedi’i symleiddio (ond sy’n dal yn ddiddorol).

5.5.1Strwythur y Crynhoydd

Yn 4.1.7 addasasom ein dehonglydd metagylchol gwreiddiol i wahanu dadansoddi oddi wrth weithredu. Dadansoddasom bob mynegiad i gynhyrchu gweithdrefn weithredu a oedd yn cymryd amgylchedd yn arg ac yn cyflawni’r gweithrediadau gofynnol. Yn ein crynhoydd, byddwn yn gwneud yr un dadansoddiad yn ei hanfod. Yn lle cynhyrchu gweithdrefnau gweithredu, fodd bynnag, byddwn yn cynhyrchu dilyniannau o gyfarwyddiadau i’w rhedeg gan ein peiriant cofrestri.

Y weithdrefn compile sy’n cyflawni’r dethol ar y lefel uchaf yn y crynhoydd. Mae’n cyfateb i weithdrefn eval 4.1.1, gweithdrefn analyze 4.1.7, a phwynt mynediad eval-dispatch y gwerthusydd rheolaeth eglur yn 5.4.1. Mae’r crynhoydd, fel y dehonglwyr, yn defnyddio’r gweithdrefnau cystrawen mynegiadau a ddiffiniwyd yn 4.1.2.³²⁰ Mae Compile yn dadansoddi achosion yn ôl math cystrawennol y mynegiad sydd i’w grynhoi. Ar gyfer pob math o fynegiad, mae’n dethol cynhyrchydd cod arbenigol:

(define (compile exp target linkage)
  (cond ((self-evaluating? exp)
         (compile-self-evaluating 
          exp target linkage))
        ((quoted? exp) 
         (compile-quoted exp target linkage))
        ((variable? exp)
         (compile-variable 
          exp target linkage))
        ((assignment? exp)
         (compile-assignment
          exp target linkage))
        ((definition? exp)
         (compile-definition
          exp target linkage))
        ((if? exp)
         (compile-if exp target linkage))
        ((lambda? exp)
         (compile-lambda exp target linkage))
        ((begin? exp)
         (compile-sequence 
          (begin-actions exp) target linkage))
        ((cond? exp) 
         (compile 
          (cond->if exp) target linkage))
        ((application? exp)
         (compile-application 
          exp target linkage))
        (else
         (error "Unknown expression type: 
                 COMPILE" 
                exp))))

Targedau a chysylltiadau

Mae Compile a’r cynhyrchwyr cod y mae’n eu galw yn cymryd dau arg yn ogystal â’r mynegiad i’w grynhoi. Mae targed, sy’n pennu’r gofrestr y dylai’r cod wedi’i grynhoi ddychwelyd gwerth y mynegiad ynddi. Mae hefyd ddisgrifydd cysylltu, sy’n disgrifio sut y dylai’r cod sy’n deillio o grynhoi’r mynegiad fynd yn ei flaen pan fydd wedi gorffen gweithredu. Gall y disgrifydd cysylltu ofyn i’r cod wneud un o’r tri pheth canlynol:

parhau at y cyfarwyddyd nesaf yn y dilyniant (pennir hyn gan y disgrifydd cysylltu next),
dychwelyd o’r weithdrefn sy’n cael ei chrynhoi (pennir hyn gan y disgrifydd cysylltu return), neu
neidio at bwynt mynediad ag enw (pennir hyn drwy ddefnyddio’r label dynodedig yn ddisgrifydd cysylltu).

Er enghraifft, dylai crynhoi’r mynegiad 5 (sy’n gwerthuso iddo’i hun) â’r gofrestr val yn darged ac next yn gysylltiad gynhyrchu’r cyfarwyddyd

(assign val (const 5))

Dylai crynhoi’r un mynegiad â chysylltiad return gynhyrchu’r cyfarwyddiadau

(assign val (const 5))
(goto (reg continue))

Yn yr achos cyntaf, bydd y gweithredu’n parhau â’r cyfarwyddyd nesaf yn y dilyniant. Yn yr ail achos, byddwn yn dychwelyd o alwad gweithdrefn. Yn y ddau achos, rhoddir gwerth y mynegiad yn y gofrestr darged val.

Dilyniannau cyfarwyddiadau a defnyddio’r pentwr

Mae pob cynhyrchydd cod yn dychwelyd dilyniant cyfarwyddiadau sy’n cynnwys y cod gwrthrych y mae wedi’i gynhyrchu ar gyfer y mynegiad. Cyflawnir cynhyrchu cod ar gyfer mynegiad cyfansawdd drwy gyfuno allbwn cynhyrchwyr cod symlach ar gyfer y mynegiadau cydrannol, yn union fel y cyflawnir gwerthuso mynegiad cyfansawdd drwy werthuso’r mynegiadau cydrannol.

Y dull symlaf o gyfuno dilyniannau cyfarwyddiadau yw gweithdrefn o’r enw append-instruction-sequences. Mae’n cymryd yn argiau unrhyw nifer o ddilyniannau cyfarwyddiadau sydd i’w gweithredu yn eu trefn; mae’n eu hatodi at ei gilydd ac yn dychwelyd y dilyniant cyfun. Hynny yw, os yw $⟨ s e q_{1} ⟩$ ac $⟨ s e q_{2} ⟩$ yn ddilyniannau o gyfarwyddiadau, yna mae gwerthuso

(append-instruction-sequences ⟨seq₁⟩ ⟨seq₂⟩)

yn cynhyrchu’r dilyniant

⟨seq₁⟩
⟨seq₂⟩

Pryd bynnag y gallai fod angen cadw cofrestri, mae cynhyrchwyr cod y crynhoydd yn defnyddio preserving, sy’n ddull mwy cynnil o gyfuno dilyniannau cyfarwyddiadau. Mae Preserving yn cymryd tri arg: set o gofrestri a dau ddilyniant cyfarwyddiadau sydd i’w gweithredu yn eu trefn. Mae’n atodi’r dilyniannau at ei gilydd fel bod cynnwys pob cofrestr yn y set yn cael ei gadw drwy gydol gweithredu’r dilyniant cyntaf, os oes angen hyn ar gyfer gweithredu’r ail ddilyniant. Hynny yw, os yw’r dilyniant cyntaf yn addasu’r gofrestr ac mae ar yr ail ddilyniant angen cynnwys gwreiddiol y gofrestr mewn gwirionedd, yna mae preserving yn rhoi save ac restore ar gyfer y gofrestr o amgylch y dilyniant cyntaf cyn atodi’r dilyniannau. Fel arall, mae preserving yn dychwelyd y dilyniannau cyfarwyddiadau wedi’u hatodi yn unig. Felly, er enghraifft, mae (preserving (list ⟨reg₁⟩ ⟨reg₂⟩) ⟨seg₁⟩ ⟨seg₂⟩) yn cynhyrchu un o’r pedwar dilyniant cyfarwyddiadau canlynol, yn dibynnu ar sut mae $⟨ s e q_{1} ⟩$ ac $⟨ s e q_{2} ⟩$ yn defnyddio $⟨ r e g_{1} ⟩$ ac $⟨ r e g_{2} ⟩$ : $\begin{array}{llll} ⟨ s e q_{1} ⟩ & (save & (save & (save ⟨ r e g_{2} ⟩) \\ ⟨ s e q_{2} ⟩ & ⟨ r e g_{1} ⟩) & ⟨ r e g_{2} ⟩) & (save ⟨ r e g_{1} ⟩) \\ ⟨ s e q_{1} ⟩ & ⟨ s e q_{1} ⟩ & ⟨ s e q_{1} ⟩ \\ (restore & (restore & (restore ⟨ r e g_{1} ⟩) \\ ⟨ r e g_{1} ⟩) & ⟨ r e g_{2} ⟩) & (restore ⟨ r e g_{2} ⟩) \\ ⟨ s e q_{2} ⟩ & ⟨ s e q_{2} ⟩ & ⟨ s e q_{2} ⟩ \end{array}$

Drwy ddefnyddio preserving i gyfuno dilyniannau cyfarwyddiadau, mae’r crynhoydd yn osgoi gweithrediadau pentwr diangen. Mae hyn hefyd yn ynysu’r manylion ynghylch a ddylid cynhyrchu cyfarwyddiadau save ac restore o fewn y weithdrefn preserving, gan eu gwahanu oddi wrth y materion sy’n codi wrth ysgrifennu pob un o’r cynhyrchwyr cod unigol. Yn wir, nid yw’r cynhyrchwyr cod yn cynhyrchu unrhyw gyfarwyddiadau save nac restore yn benodol.

Mewn egwyddor, gallem gynrychioli dilyniant cyfarwyddiadau fel rhestr o gyfarwyddiadau yn unig. Yna gallai Append-instruction-sequences gyfuno dilyniannau cyfarwyddiadau drwy gyflawni append arferol ar restrau. Fodd bynnag, byddai preserving wedyn yn weithrediad cymhleth, oherwydd y byddai rhaid iddo ddadansoddi pob dilyniant cyfarwyddiadau i benderfynu sut mae’r dilyniant yn defnyddio ei gofrestri. Byddai Preserving yn aneffeithlon yn ogystal â bod yn gymhleth, oherwydd y byddai rhaid iddo ddadansoddi pob un o’i argiau dilyniant cyfarwyddiadau, er y gallai’r dilyniannau hyn eu hunain fod wedi’u hadeiladu drwy alwadau i preserving, ac os felly byddai eu rhannau eisoes wedi’u dadansoddi. I osgoi dadansoddi ailadroddus o’r fath, byddwn yn cysylltu rhywfaint o wybodaeth am ddefnydd cofrestri â phob dilyniant cyfarwyddiadau. Pan adeiladwn ddilyniant cyfarwyddiadau sylfaenol, darparwn y wybodaeth hon yn benodol, a bydd y gweithdrefnau sy’n cyfuno dilyniannau cyfarwyddiadau’n deillio gwybodaeth am ddefnydd cofrestri’r dilyniant cyfun o’r wybodaeth sy’n gysylltiedig â’r dilyniannau cydrannol.

Bydd dilyniant cyfarwyddiadau’n cynnwys tri darn o wybodaeth:

y set o gofrestri y mae rhaid eu cychwyn cyn gweithredu’r cyfarwyddiadau yn y dilyniant (dywedir mai’r rhain yw’r cofrestri sydd eu hangen ar y dilyniant),
y set o gofrestri y mae eu gwerthoedd yn cael eu haddasu gan y cyfarwyddiadau yn y dilyniant, a
y cyfarwyddiadau eu hunain (a elwir hefyd yn ddatganiadau) yn y dilyniant.

Byddwn yn cynrychioli dilyniant cyfarwyddiadau fel rhestr o’i dair rhan. Felly, yr adeiladydd ar gyfer dilyniannau cyfarwyddiadau yw

(define (make-instruction-sequence 
         needs modifies statements)
  (list needs modifies statements))

Er enghraifft, mae’r dilyniant dau gyfarwyddyd sy’n chwilio am werth y newidyn x yn yr amgylchedd presennol, yn aseinio’r canlyniad i val, ac yna’n dychwelyd, yn gofyn bod cofrestri env ac continue wedi’u cychwyn, ac yn addasu cofrestr val. Felly byddai’r dilyniant hwn yn cael ei adeiladu fel

(make-instruction-sequence
 '(env continue)
 '(val)
 '((assign val
           (op lookup-variable-value)
           (const x)
           (reg env))
   (goto (reg continue))))

Weithiau mae angen adeiladu dilyniant cyfarwyddiadau heb ddatganiadau:

(define (empty-instruction-sequence)
  (make-instruction-sequence '() '() '()))

Dangosir y gweithdrefnau ar gyfer cyfuno dilyniannau cyfarwyddiadau yn 5.5.4.

Ymarfer 5.31: Wrth werthuso cymhwysiad gweithdrefn, mae’r gwerthusydd rheolaeth eglur bob amser yn cadw ac yn adfer y gofrestr env o amgylch gwerthuso’r gweithredydd, yn cadw ac yn adfer env o amgylch gwerthuso pob operand (heblaw’r un olaf), yn cadw ac yn adfer argl o amgylch gwerthuso pob operand, ac yn cadw ac yn adfer proc o amgylch gwerthuso dilyniant yr operandau. Ar gyfer pob un o’r cyfuniadau canlynol, dywedwch pa rai o’r gweithrediadau save ac restore hyn sy’n ddiangen ac felly y gallai mecanwaith preserving y crynhoydd eu dileu:
(f 'x 'y)
((f) 'x 'y)
(f (g 'x) y)
(f (g 'x) 'y)

Ymarfer 5.32: Gan ddefnyddio’r mecanwaith preserving, bydd y crynhoydd yn osgoi cadw ac adfer env o amgylch gwerthuso gweithredydd cyfuniad yn yr achos lle mae’r gweithredydd yn symbol. Gallem hefyd gynnwys optimeiddiadau o’r fath yn y gwerthusydd. Yn wir, mae gwerthusydd rheolaeth eglur 5.4 eisoes yn cyflawni optimeiddiad tebyg, drwy drin cyfuniadau heb operandau fel achos arbennig.

Ymestynnwch y gwerthusydd rheolaeth eglur i adnabod cyfuniadau y mae eu gweithredydd yn symbol fel dosbarth ar wahân o fynegiadau, ac i fanteisio ar y ffaith hon wrth werthuso mynegiadau o’r fath.
Mae Alyssa P. Hacker yn awgrymu y gallem, drwy ymestyn y gwerthusydd i adnabod mwy a mwy o achosion arbennig, gynnwys holl optimeiddiadau’r crynhoydd, ac y byddai hyn yn dileu mantais crynhoi’n llwyr. Beth yw eich barn am y syniad hwn?

5.5.2Crynhoi Mynegiadau

Yn yr adran hon a’r nesaf gweithredwn y cynhyrchwyr cod y mae’r weithdrefn compile yn eu dethol.

Crynhoi cod cysylltu

Yn gyffredinol, bydd allbwn pob cynhyrchydd cod yn gorffen â chyfarwyddiadau—a gynhyrchir gan y weithdrefn compile-linkage—sy’n gweithredu’r cysylltiad gofynnol. Os mai return yw’r cysylltiad, yna rhaid cynhyrchu’r cyfarwyddyd (goto (reg continue)). Mae ar hwn angen y gofrestr continue ac nid yw’n addasu unrhyw gofrestri. Os mai next yw’r cysylltiad, yna nid oes angen cynnwys unrhyw gyfarwyddiadau ychwanegol. Fel arall, label yw’r cysylltiad, a chynhyrchwn goto i’r label hwnnw, cyfarwyddyd nad yw’n gofyn am unrhyw gofrestri nac yn eu haddasu.³²¹

(define (compile-linkage linkage)
  (cond ((eq? linkage 'return)
         (make-instruction-sequence 
          '(continue)
          '()
          '((goto (reg continue)))))
        ((eq? linkage 'next)
         (empty-instruction-sequence))
        (else
         (make-instruction-sequence '() '()
          `((goto (label ,linkage)))))))

Atodir y cod cysylltu at ddilyniant cyfarwyddiadau drwy ddefnyddio preserving ar y gofrestr continue, gan y bydd cysylltiad return yn gofyn am y gofrestr continue: Os yw’r dilyniant cyfarwyddiadau a roddwyd yn addasu continue a bod ar y cod cysylltu ei hangen, cedwir ac adferir continue.

(define (end-with-linkage 
         linkage instruction-sequence)
  (preserving '(continue)
   instruction-sequence
   (compile-linkage linkage)))

Crynhoi mynegiadau syml

Mae’r cynhyrchwyr cod ar gyfer mynegiadau sy’n gwerthuso iddynt eu hunain, dyfyniadau a newidynnau yn adeiladu dilyniannau cyfarwyddiadau sy’n aseinio’r gwerth gofynnol i’r gofrestr darged ac yna’n mynd yn eu blaen fel y pennir gan y disgrifydd cysylltu.

(define (compile-self-evaluating 
         exp target linkage)
  (end-with-linkage
   linkage (make-instruction-sequence 
            '()
            (list target)
            `((assign ,target (const ,exp))))))

(define (compile-quoted exp target linkage)
  (end-with-linkage
   linkage
   (make-instruction-sequence
    '()
    (list target)
    `((assign 
       ,target
       (const ,(text-of-quotation exp)))))))

(define (compile-variable
         exp target linkage)
  (end-with-linkage 
   linkage
   (make-instruction-sequence 
    '(env)
    (list target)
    `((assign ,target
              (op lookup-variable-value)
              (const ,exp)
              (reg env))))))

Mae’r holl gyfarwyddiadau aseiniad hyn yn addasu’r gofrestr darged, ac mae ar yr un sy’n chwilio am newidyn angen y gofrestr env.

Trinnir aseiniadau a diffiniadau yn debyg iawn i’r ffordd y’u trinnir yn y dehonglydd. Cynhyrchwn yn ddychweliadol god sy’n cyfrifo’r gwerth sydd i’w aseinio i’r newidyn, ac atodwn ato ddilyniant dau gyfarwyddyd sydd yn wir yn gosod neu’n diffinio’r newidyn ac yn aseinio gwerth y mynegiad cyfan (y symbol ok) i’r gofrestr darged. Mae gan y crynhoi dychweliadol darged val a chysylltiad next fel y bydd y cod yn rhoi ei ganlyniad yn val ac yn parhau â’r cod a atodir ar ei ôl. Gwneir yr atodi gan gadw env, oherwydd bod angen yr amgylchedd i osod neu ddiffinio’r newidyn, a gallai’r cod ar gyfer gwerth y newidyn fod yn ganlyniad crynhoi mynegiad cymhleth a allai addasu’r cofrestri mewn ffyrdd mympwyol.

(define (compile-assignment 
         exp target linkage)
  (let ((var (assignment-variable exp))
        (get-value-code
         (compile (assignment-value exp) 
                  'val
                  'next)))
    (end-with-linkage 
     linkage
     (preserving 
      '(env)
      get-value-code
      (make-instruction-sequence
       '(env val)
       (list target)
       `((perform (op set-variable-value!)
                  (const ,var)
                  (reg val)
                  (reg env))
         (assign ,target (const ok))))))))

(define (compile-definition 
         exp target linkage)
  (let ((var (definition-variable exp))
        (get-value-code
         (compile (definition-value exp)
                  'val
                  'next)))
    (end-with-linkage
     linkage
     (preserving 
      '(env)
      get-value-code
      (make-instruction-sequence
       '(env val)
       (list target)
       `((perform (op define-variable!)
                  (const ,var)
                  (reg val)
                  (reg env))
         (assign ,target (const ok))))))))

Mae ar y dilyniant dau gyfarwyddyd a atodir angen env ac val ac mae’n addasu’r targed. Sylwch, er ein bod yn cadw env ar gyfer y dilyniant hwn, nad ydym yn cadw val, oherwydd bod get-value-code wedi’i ddylunio i roi ei ganlyniad yn benodol yn val i’r dilyniant hwn ei ddefnyddio. (Yn wir, pe baem yn cadw val, byddai gennym fyg, oherwydd y byddai hyn yn peri i gynnwys blaenorol val gael ei adfer yn syth ar ôl rhedeg get-value-code.)

Crynhoi mynegiadau amodol

Mae gan y cod ar gyfer mynegiad if a grynhoir â tharged a chysylltiad penodol y ffurf

⟨compilation of predicate, 
 target val, linkage next⟩
 (test (op false?) (reg val))
 (branch (label false-branch))
true-branch
 ⟨compilation of consequent with given 
  target and given linkage or after-if⟩
false-branch
 ⟨compilation of alternative 
  with given target and linkage⟩
after-if

I gynhyrchu’r cod hwn, crynhown y traethiad, y mynegiad canlyniadol a’r mynegiad amgen, a chyfuno’r cod sy’n deillio o hynny â chyfarwyddiadau i brofi canlyniad y traethiad ac â labeli newydd i nodi’r canghennau gwir ac anwir a diwedd y mynegiad amodol.³²² Yn y trefniant cod hwn, rhaid inni ganghennu o amgylch y gangen wir os yw’r prawf yn anwir. Yr unig gymhlethdod bach yw sut y dylid trin cysylltiad y gangen wir. Os mai return neu label yw cysylltiad y mynegiad amodol, yna bydd y canghennau gwir ac anwir ill dwy’n defnyddio’r un cysylltiad hwn. Os mai next yw’r cysylltiad, mae’r gangen wir yn gorffen â naid o amgylch cod y gangen anwir at y label ar ddiwedd y mynegiad amodol.

(define (compile-if exp target linkage)
  (let ((t-branch (make-label 'true-branch))
        (f-branch (make-label 'false-branch))
        (after-if (make-label 'after-if)))
    (let ((consequent-linkage
           (if (eq? linkage 'next) 
               after-if
               linkage)))
      (let ((p-code 
             (compile (if-predicate exp)
                      'val
                      'next))
            (c-code
             (compile (if-consequent exp) 
                      target 
                      consequent-linkage))
            (a-code
             (compile (if-alternative exp)
                      target
                      linkage)))
        (preserving 
         '(env continue)
         p-code
         (append-instruction-sequences
          (make-instruction-sequence 
           '(val) 
           '()
           `((test (op false?) (reg val))
             (branch (label ,f-branch))))
          (parallel-instruction-sequences
           (append-instruction-sequences 
            t-branch c-code)
           (append-instruction-sequences
            f-branch a-code))
          after-if))))))

Cedwir Env o amgylch cod y traethiad oherwydd y gallai fod ei angen ar y canghennau gwir ac anwir, a chedwir continue oherwydd y gallai fod ei angen ar y cod cysylltu yn y canghennau hynny. Atodir cod y canghennau gwir ac anwir (nad ydynt yn cael eu gweithredu yn eu trefn) gan ddefnyddio cyfunydd arbennig parallel-instruction-sequences a ddisgrifir yn 5.5.4.

Sylwch fod cond yn fynegiad deilliedig, felly’r cyfan sydd angen i’r crynhoydd ei wneud i’w drin yw cymhwyso’r trawsffurfiwr cond->if (o 4.1.2) a chrynhoi’r mynegiad if sy’n deillio o hyn.

Crynhoi dilyniannau

Mae crynhoi dilyniannau (o gyrff gweithdrefnau neu fynegiadau begin penodol) yn dilyn yr un patrwm â’u gwerthuso. Crynhöir pob mynegiad o’r dilyniant—y mynegiad olaf â’r cysylltiad a bennwyd ar gyfer y dilyniant, a’r mynegiadau eraill â chysylltiad next (i weithredu gweddill y dilyniant). Atodir dilyniannau cyfarwyddiadau’r mynegiadau unigol at ei gilydd i ffurfio un dilyniant cyfarwyddiadau, fel y cedwir env (sydd ei angen ar gyfer gweddill y dilyniant) ac continue (a all fod ei angen ar gyfer y cysylltiad ar ddiwedd y dilyniant).

(define (compile-sequence seq target linkage)
  (if (last-exp? seq)
      (compile (first-exp seq) target linkage)
      (preserving '(env continue)
       (compile (first-exp seq) target 'next)
       (compile-sequence (rest-exps seq)
                         target
                         linkage))))

Crynhoi mynegiadau `lambda`

Mae mynegiadau Lambda yn adeiladu gweithdrefnau. Rhaid i’r cod gwrthrych ar gyfer mynegiad lambda fod ar y ffurf

⟨construct procedure object 
 and assign it to target register⟩
⟨linkage⟩

Pan grynhown y mynegiad lambda, cynhyrchwn y cod ar gyfer corff y weithdrefn hefyd. Er na weithredir y corff adeg adeiladu’r weithdrefn, mae’n gyfleus ei fewnosod yn y cod gwrthrych yn syth ar ôl y cod ar gyfer lambda. Os yw cysylltiad y mynegiad lambda yn label neu’n return, mae hyn yn iawn. Ond os mai next yw’r cysylltiad, bydd angen hepgor y cod ar gyfer corff y weithdrefn drwy ddefnyddio cysylltiad sy’n neidio at label a fewnosodir ar ôl y corff. Felly mae gan y cod gwrthrych y ffurf

⟨construct procedure object 
 and assign it to target register⟩
 ⟨code for given linkage⟩ or 
  (goto (label after-lambda))
 ⟨compilation of procedure body⟩
after-lambda

Mae Compile-lambda yn cynhyrchu’r cod ar gyfer adeiladu’r gwrthrych gweithdrefn ac yna’r cod ar gyfer corff y weithdrefn. Adeiledir y gwrthrych gweithdrefn adeg rhedeg drwy gyfuno’r amgylchedd presennol (yr amgylchedd ym mhwynt y diffiniad) â’r pwynt mynediad i gorff y weithdrefn wedi’i grynhoi (label newydd).³²³

(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
         (make-instruction-sequence 
          '(env)
          (list target)
          `((assign 
             ,target
             (op make-compiled-procedure)
             (label ,proc-entry)
             (reg env)))))
        (compile-lambda-body exp proc-entry))
       after-lambda))))

Mae Compile-lambda yn defnyddio’r cyfunydd arbennig tack-on-instruction-sequence yn hytrach nag append-instruction-sequences (5.5.4) i atodi corff y weithdrefn at god y mynegiad lambda, oherwydd nad yw’r corff yn rhan o’r dilyniant cyfarwyddiadau a weithredir pan eir i mewn i’r dilyniant cyfun; yn hytrach, mae yn y dilyniant dim ond am fod hwnnw’n lle cyfleus i’w roi.

Mae Compile-lambda-body yn adeiladu’r cod ar gyfer corff y weithdrefn. Mae’r cod hwn yn dechrau â label ar gyfer y pwynt mynediad. Nesaf daw cyfarwyddiadau a fydd yn peri i’r amgylchedd gwerthuso adeg rhedeg newid i’r amgylchedd cywir ar gyfer gwerthuso corff y weithdrefn—sef amgylchedd diffiniad y weithdrefn, wedi’i ymestyn i gynnwys rhwymiadau’r paramedrau ffurfiol i’r argiau y gelwir y weithdrefn â hwy. Ar ôl hyn daw’r cod ar gyfer y dilyniant mynegiadau sy’n ffurfio corff y weithdrefn. Crynhöir y dilyniant â chysylltiad return a tharged val fel y bydd yn gorffen drwy ddychwelyd o’r weithdrefn â chanlyniad y weithdrefn yn val.

(define (compile-lambda-body exp proc-entry)
  (let ((formals (lambda-parameters exp)))
    (append-instruction-sequences
     (make-instruction-sequence 
      '(env proc argl)
      '(env)
      `(,proc-entry
        (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))))

5.5.3Crynhoi Cyfuniadau

Hanfod y broses grynhoi yw crynhoi cymwysiadau gweithdrefnau. Mae gan y cod ar gyfer cyfuniad a grynhoir â tharged a chysylltiad penodol y ffurf

⟨compilation of operator, 
 target proc, linkage next⟩
⟨evaluate operands and construct 
 argument list in argl⟩
⟨compilation of procedure call 
 with given target and linkage⟩

Efallai y bydd rhaid cadw ac adfer y cofrestri env, proc, ac argl yn ystod gwerthuso’r gweithredydd a’r operandau. Sylwch mai dyma’r unig le yn y crynhoydd lle pennir targed heblaw val.

Cynhyrchir y cod gofynnol gan compile-application. Mae hwn yn crynhoi’r gweithredydd yn ddychweliadol, i gynhyrchu cod sy’n rhoi’r weithdrefn sydd i’w chymhwyso yn proc, ac yn crynhoi’r operandau, i gynhyrchu cod sy’n gwerthuso operandau unigol y cymhwysiad. Cyfunir dilyniannau cyfarwyddiadau’r operandau (gan construct-arglist) â chod sy’n adeiladu’r rhestr argiau yn argl, a chyfunir y cod rhestr argiau sy’n deillio o hyn â chod y weithdrefn a’r cod sy’n cyflawni’r alwad gweithdrefn (a gynhyrchir gan compile-procedure-call). Wrth atodi’r dilyniannau cod, rhaid cadw’r gofrestr env o amgylch gwerthuso’r gweithredydd (gan y gallai gwerthuso’r gweithredydd addasu env, y bydd ei hangen i werthuso’r operandau), a rhaid cadw’r gofrestr proc o amgylch adeiladu’r rhestr argiau (gan y gallai gwerthuso’r operandau addasu proc, y bydd ei hangen ar gyfer cymhwyso’r weithdrefn ei hun). Rhaid cadw Continue hefyd drwy gydol y broses, gan fod ei hangen ar gyfer y cysylltiad yn yr alwad gweithdrefn.

(define (compile-application 
         exp target linkage)
  (let ((proc-code 
         (compile (operator exp) 'proc 'next))
        (operand-codes
         (map (lambda (operand)
                (compile operand 'val 'next))
              (operands exp))))
    (preserving 
     '(env continue)
     proc-code
     (preserving 
      '(proc continue)
      (construct-arglist operand-codes)
      (compile-procedure-call 
       target
       linkage)))))

Bydd y cod ar gyfer adeiladu’r rhestr argiau yn gwerthuso pob operand i val ac yna’n defnyddio cons i atodi’r gwerth hwnnw at y rhestr argiau sy’n cael ei chronni yn argl. Gan ein bod yn defnyddio cons i atodi’r argiau at argl yn eu trefn, rhaid inni ddechrau â’r arg olaf a gorffen â’r cyntaf, fel y bydd yr argiau’n ymddangos mewn trefn o’r cyntaf i’r olaf yn y rhestr sy’n deillio o hyn. Yn hytrach na gwastraffu cyfarwyddyd drwy gychwyn argl â’r rhestr wag i baratoi ar gyfer y dilyniant gwerthusiadau hwn, parwn i’r dilyniant cod cyntaf adeiladu’r argl cychwynnol. Felly, dyma ffurf gyffredinol adeiladu’r rhestr argiau:

⟨compilation of last operand, targeted to val⟩
(assign argl (op list) (reg val))
⟨compilation of next operand, targeted to val⟩
(assign argl (op cons) (reg val) (reg argl))
…
⟨compilation of first operand, targeted to val⟩
(assign argl (op cons) (reg val) (reg argl))

Rhaid cadw Argl o amgylch gwerthuso pob operand heblaw’r cyntaf (fel na chollir yr argiau a gronnwyd hyd yma), a rhaid cadw env o amgylch gwerthuso pob operand heblaw’r olaf (i’w ddefnyddio wrth werthuso operandau dilynol).

Mae crynhoi’r cod argiau hwn ychydig yn ddyrys, oherwydd y driniaeth arbennig o’r operand cyntaf sydd i’w werthuso a’r angen i gadw argl ac env mewn lleoedd gwahanol. Mae’r weithdrefn construct-arglist yn cymryd yn argiau y cod sy’n gwerthuso’r operandau unigol. Os nad oes operandau o gwbl, mae’n allyrru’r cyfarwyddyd

(assign argl (const ()))

Fel arall, mae construct-arglist yn creu cod sy’n cychwyn argl â’r arg olaf, ac yn atodi cod sy’n gwerthuso gweddill yr argiau ac yn eu hatodi at argl yn olynol. Er mwyn prosesu’r argiau o’r olaf i’r cyntaf, rhaid gwrthdroi rhestr dilyniannau cod yr operandau o’r drefn a ddarperir gan compile-application.

(define (construct-arglist operand-codes)
  (let ((operand-codes 
         (reverse operand-codes)))
    (if (null? operand-codes)
        (make-instruction-sequence 
         '() 
         '(argl)
         '((assign argl (const ()))))
        (let ((code-to-get-last-arg
               (append-instruction-sequences
                (car operand-codes)
                (make-instruction-sequence 
                 '(val)
                 '(argl)
                 '((assign argl
                           (op list)
                           (reg val)))))))
          (if (null? (cdr operand-codes))
              code-to-get-last-arg
              (preserving 
               '(env)
               code-to-get-last-arg
               (code-to-get-rest-args
                (cdr operand-codes))))))))

(define (code-to-get-rest-args operand-codes)
  (let ((code-for-next-arg
         (preserving 
          '(argl)
          (car operand-codes)
          (make-instruction-sequence 
           '(val argl)
           '(argl)
           '((assign argl
                     (op cons)
                     (reg val)
                     (reg argl)))))))
    (if (null? (cdr operand-codes))
        code-for-next-arg
        (preserving 
         '(env)
         code-for-next-arg
         (code-to-get-rest-args 
          (cdr operand-codes))))))

Cymhwyso gweithdrefnau

Ar ôl gwerthuso elfennau cyfuniad, rhaid i’r cod wedi’i grynhoi gymhwyso’r weithdrefn yn proc i’r argiau yn argl. Mae’r cod yn cyflawni, yn ei hanfod, yr un dethol gweithdrefn â’r weithdrefn apply yng ngwerthusydd metagylchol 4.1.1 neu’r pwynt mynediad apply-dispatch yng ngwerthusydd rheolaeth eglur 5.4.1. Mae’n gwirio a yw’r weithdrefn sydd i’w chymhwyso yn weithdrefn gyntefig neu’n weithdrefn wedi’i chrynhoi. Ar gyfer gweithdrefn gyntefig, mae’n defnyddio apply-primitive-procedure; gwelwn yn fuan sut mae’n trin gweithdrefnau wedi’u crynhoi. Mae gan y cod cymhwyso gweithdrefn y ffurf ganlynol:

(test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch))
compiled-branch
 ⟨code to apply compiled procedure 
  with given target and appropriate linkage⟩
primitive-branch
 (assign ⟨target⟩
         (op apply-primitive-procedure)
         (reg proc)
         (reg argl))
 ⟨linkage⟩
after-call

Sylwch fod rhaid i’r gangen ar gyfer gweithdrefn wedi’i chrynhoi hepgor y gangen gyntefig. Felly, os mai next oedd cysylltiad yr alwad gweithdrefn wreiddiol, rhaid i’r gangen gyfansawdd ddefnyddio cysylltiad sy’n neidio at label a fewnosodir ar ôl y gangen gyntefig. (Mae hyn yn debyg i’r cysylltiad a ddefnyddir ar gyfer y gangen wir yn compile-if.)

(define (compile-procedure-call
         target linkage)
  (let ((primitive-branch 
         (make-label 'primitive-branch))
        (compiled-branch 
         (make-label 'compiled-branch))
        (after-call
         (make-label 'after-call)))
    (let ((compiled-linkage
           (if (eq? linkage 'next)
               after-call
               linkage)))
      (append-instruction-sequences
       (make-instruction-sequence 
        '(proc)
        '()
        `((test 
           (op primitive-procedure?)
           (reg proc))
          (branch 
           (label ,primitive-branch))))
       (parallel-instruction-sequences
        (append-instruction-sequences
         compiled-branch
         (compile-proc-appl 
          target
          compiled-linkage))
        (append-instruction-sequences
         primitive-branch
         (end-with-linkage
          linkage
          (make-instruction-sequence
           '(proc argl)
           (list target)
           `((assign 
              ,target
              (op apply-primitive-procedure)
              (reg proc)
              (reg argl)))))))
       after-call))))

Atodir y canghennau cyntefig a chyfansawdd, fel y canghennau gwir ac anwir yn compile-if, gan ddefnyddio parallel-instruction-sequences yn hytrach na’r append-instruction-sequences arferol, oherwydd na chânt eu gweithredu yn eu trefn.

Cymhwyso gweithdrefnau wedi’u crynhoi

Y cod sy’n trin cymhwyso gweithdrefnau yw rhan fwyaf cynnil y crynhoydd, er bod y dilyniannau cyfarwyddiadau y mae’n eu cynhyrchu’n fyr iawn. Mae gan weithdrefn wedi’i chrynhoi (fel y’i hadeiledir gan compile-lambda) bwynt mynediad, sef label sy’n dynodi lle mae cod y weithdrefn yn dechrau. Mae’r cod yn y pwynt mynediad hwn yn cyfrifo canlyniad yn val ac yn dychwelyd drwy weithredu’r cyfarwyddyd (goto (reg continue)). Felly, gallem ddisgwyl i’r cod ar gyfer cymhwyso gweithdrefn wedi’i chrynhoi (a gynhyrchir gan compile-proc-appl) â tharged a chysylltiad penodol edrych fel hyn os yw’r cysylltiad yn label

(assign continue 
        (label proc-return))
 (assign val
         (op compiled-procedure-entry)
         (reg proc))
 (goto (reg val))
proc-return
 (assign ⟨target⟩ 
         (reg val))   ; included if target is not val
 (goto (label ⟨linkage⟩))   ; linkage code

neu fel hyn os mai return yw’r cysylltiad.

(save continue)
 (assign continue 
         (label proc-return))
 (assign val 
         (op compiled-procedure-entry)
         (reg proc))
 (goto (reg val))
proc-return
 (assign ⟨target⟩
         (reg val))   ; included if target is not val
 (restore continue)
 (goto (reg continue))   ; linkage code

Mae’r cod hwn yn gosod continue fel y bydd y weithdrefn yn dychwelyd at label proc-return ac yn neidio at bwynt mynediad y weithdrefn. Mae’r cod yn proc-return yn trosglwyddo canlyniad y weithdrefn o val i’r gofrestr darged (os oes angen) ac yna’n neidio at y lleoliad a bennir gan y cysylltiad. (Mae’r cysylltiad bob amser yn return neu’n label, oherwydd bod compile-procedure-call yn disodli cysylltiad next ar gyfer y gangen gweithdrefn gyfansawdd â label after-call.)

Yn wir, os nad val yw’r targed, dyna’n union y cod y bydd ein crynhoydd yn ei gynhyrchu.³²⁴ Fel arfer, fodd bynnag, val yw’r targed (yr unig adeg y mae’r crynhoydd yn pennu cofrestr wahanol yw wrth dargedu gwerthuso gweithredydd i proc), felly rhoddir canlyniad y weithdrefn yn uniongyrchol yn y gofrestr darged ac nid oes angen dychwelyd i leoliad arbennig sy’n ei gopïo. Yn lle hynny, symleiddiwn y cod drwy osod continue fel y bydd y weithdrefn yn “dychwelyd” yn uniongyrchol i’r lle a bennir gan gysylltiad y galwr:

⟨set up continue for linkage⟩
(assign val 
        (op compiled-procedure-entry)
        (reg proc))
(goto (reg val))

Os yw’r cysylltiad yn label, gosodwn continue fel y bydd y weithdrefn yn dychwelyd at y label hwnnw. (Hynny yw, mae’r (goto (reg continue)) y mae’r weithdrefn yn gorffen ag ef yn dod yn gyfwerth â’r (goto (label ⟨linkage⟩)) yn proc-return uchod.)

(assign continue 
        (label ⟨linkage⟩))
(assign val
        (op compiled-procedure-entry)
        (reg proc))
(goto (reg val))

Os mai return yw’r cysylltiad, nid oes angen gosod continue o gwbl: Mae eisoes yn dal y lleoliad a ddymunir. (Hynny yw, mae’r (goto (reg continue)) y mae’r weithdrefn yn gorffen ag ef yn mynd yn uniongyrchol i’r lle y byddai’r (goto (reg continue)) yn proc-return wedi mynd iddo.)

(assign val
        (op compiled-procedure-entry)
        (reg proc))
(goto (reg val))

Gyda’r gweithrediad hwn o’r cysylltiad return, mae’r crynhoydd yn cynhyrchu cod â dychweliad cynffon. Mae galw gweithdrefn fel y cam olaf yng nghorff gweithdrefn yn trosglwyddo’n uniongyrchol, heb gadw unrhyw wybodaeth ar y pentwr.

Tybiwch yn lle hynny ein bod wedi trin achos galwad gweithdrefn â chysylltiad return a tharged val fel y dangoswyd uchod ar gyfer targed heblaw val. Byddai hyn yn dinistrio dychweliad cynffon. Byddai ein system yn dal i roi’r un gwerth ar gyfer unrhyw fynegiad. Ond bob tro y galwem weithdrefn, byddem yn cadw continue ac yn dychwelyd ar ôl yr alwad i ddadwneud y cadw (diwerth). Byddai’r gweithrediadau cadw ychwanegol hyn yn cronni yn ystod nyth o alwadau gweithdrefn.³²⁵

Mae Compile-proc-appl yn cynhyrchu’r cod cymhwyso gweithdrefn uchod drwy ystyried pedwar achos, yn dibynnu ar a yw targed yr alwad yn val ac a yw’r cysylltiad yn return. Sylwch y datgenir bod y dilyniannau cyfarwyddiadau’n addasu’r holl gofrestri, gan y gall gweithredu corff y weithdrefn newid y cofrestri mewn ffyrdd mympwyol.³²⁶ Sylwch hefyd y datgenir bod angen continue ar y dilyniant cod ar gyfer yr achos â tharged val a chysylltiad return: Er na ddefnyddir continue yn benodol yn y dilyniant dau gyfarwyddyd, rhaid inni sicrhau y bydd gan continue y gwerth cywir pan awn i mewn i’r weithdrefn wedi’i chrynhoi.

(define (compile-proc-appl target linkage)
  (cond ((and (eq? target 'val)
              (not (eq? linkage 'return)))
         (make-instruction-sequence 
          '(proc)
          all-regs
          `((assign continue (label ,linkage))
            (assign 
             val 
             (op compiled-procedure-entry)
             (reg proc))
            (goto (reg val)))))
        ((and (not (eq? target 'val))
              (not (eq? linkage 'return)))
         (let ((proc-return 
                (make-label 'proc-return)))
           (make-instruction-sequence 
            '(proc)
            all-regs
            `((assign continue 
                      (label ,proc-return))
              (assign 
               val 
               (op compiled-procedure-entry)
               (reg proc))
              (goto (reg val))
              ,proc-return
              (assign ,target (reg val))
              (goto (label ,linkage))))))
        ((and (eq? target 'val)
              (eq? linkage 'return))
         (make-instruction-sequence 
          '(proc continue) 
          all-regs
          '((assign 
             val 
             (op compiled-procedure-entry)
             (reg proc))
            (goto (reg val)))))
        ((and (not (eq? target 'val))
              (eq? linkage 'return))
         (error "return linkage, 
                 target not val: COMPILE"
                target))))

5.5.4Cyfuno Dilyniannau Cyfarwyddiadau

Mae’r adran hon yn disgrifio’r manylion ynghylch sut y cynrychiolir ac y cyfunir dilyniannau cyfarwyddiadau. Cofiwch o 5.5.1 fod dilyniant cyfarwyddiadau wedi’i gynrychioli fel rhestr o’r cofrestri sydd eu hangen, y cofrestri a addasir, a’r cyfarwyddiadau eu hunain. Byddwn hefyd yn ystyried label (symbol) yn achos dirywiedig o ddilyniant cyfarwyddiadau, nad oes arno angen unrhyw gofrestri ac nad yw’n eu haddasu. Felly, i bennu’r cofrestri sydd eu hangen ar ddilyniannau cyfarwyddiadau a’r rhai y maent yn eu haddasu, defnyddiwn y detholwyr

(define (registers-needed s)
  (if (symbol? s) '() (car s)))
(define (registers-modified s)
  (if (symbol? s) '() (cadr s)))
(define (statements s)
  (if (symbol? s) (list s) (caddr s)))

ac i benderfynu a oes angen cofrestr benodol ar ddilyniant penodol neu a yw’n ei haddasu, defnyddiwn y traethiadau

(define (needs-register? seq reg)
  (memq reg (registers-needed seq)))
(define (modifies-register? seq reg)
  (memq reg (registers-modified seq)))

Yn nhermau’r traethiadau a’r detholwyr hyn, gallwn weithredu’r amrywiol gyfunwyr dilyniannau cyfarwyddiadau a ddefnyddir drwy’r crynhoydd.

Y cyfunydd sylfaenol yw append-instruction-sequences. Mae hwn yn cymryd yn argiau nifer mympwyol o ddilyniannau cyfarwyddiadau sydd i’w gweithredu yn eu trefn ac yn dychwelyd dilyniant cyfarwyddiadau y mae ei ddatganiadau’n ddatganiadau’r holl ddilyniannau wedi’u hatodi at ei gilydd. Y pwynt cynnil yw pennu’r cofrestri sydd eu hangen ar y dilyniant canlyniadol a’r rhai y mae’n eu haddasu. Mae’n addasu’r cofrestri hynny a addasir gan unrhyw un o’r dilyniannau; mae arno angen y cofrestri hynny y mae rhaid eu cychwyn cyn y gellir rhedeg y dilyniant cyntaf (y cofrestri sydd eu hangen ar y dilyniant cyntaf), ynghyd â’r cofrestri hynny sydd eu hangen ar unrhyw un o’r dilyniannau eraill nad ydynt wedi’u cychwyn (eu haddasu) gan ddilyniannau sy’n ei ragflaenu.

Atodir y dilyniannau fesul dau gan append-2-sequences. Mae hwn yn cymryd dau ddilyniant cyfarwyddiadau seq1 ac seq2 ac yn dychwelyd y dilyniant cyfarwyddiadau y mae ei ddatganiadau’n ddatganiadau seq1 ac yna ddatganiadau seq2, y mae ei gofrestri wedi’u haddasu’n gofrestri a addasir gan naill ai seq1 neu seq2, ac y mae ei gofrestri sydd eu hangen yn gofrestri sydd eu hangen ar seq1 ynghyd â’r cofrestri hynny sydd eu hangen ar seq2 nad ydynt yn cael eu haddasu gan seq1. (Yn nhermau gweithrediadau ar setiau, y set newydd o gofrestri sydd eu hangen yw uniad y set o gofrestri sydd eu hangen ar seq1 â gwahaniaeth setiau’r cofrestri sydd eu hangen ar seq2 a’r cofrestri a addasir gan seq1.) Felly, gweithredir append-instruction-sequences fel a ganlyn:

(define (append-instruction-sequences . seqs)
  (define (append-2-sequences seq1 seq2)
    (make-instruction-sequence
     (list-union 
      (registers-needed seq1)
      (list-difference 
       (registers-needed seq2)
       (registers-modified seq1)))
     (list-union
      (registers-modified seq1)
      (registers-modified seq2))
     (append (statements seq1)
             (statements seq2))))
  (define (append-seq-list seqs)
    (if (null? seqs)
        (empty-instruction-sequence)
        (append-2-sequences 
         (car seqs)
         (append-seq-list (cdr seqs)))))
  (append-seq-list seqs))

Mae’r weithdrefn hon yn defnyddio rhai gweithrediadau syml ar gyfer trin setiau a gynrychiolir fel rhestrau, yn debyg i’r cynrychioliad setiau (heb drefn) a ddisgrifiwyd yn 2.3.3:

(define (list-union s1 s2)
  (cond ((null? s1) s2)
        ((memq (car s1) s2)
         (list-union (cdr s1) s2))
        (else
         (cons (car s1)
               (list-union (cdr s1) s2)))))

(define (list-difference s1 s2)
  (cond ((null? s1) '())
        ((memq (car s1) s2)
         (list-difference (cdr s1) s2))
        (else 
         (cons (car s1)
               (list-difference (cdr s1)
                                s2)))))

Mae Preserving, yr ail brif gyfunydd dilyniannau cyfarwyddiadau, yn cymryd rhestr o gofrestri regs a dau ddilyniant cyfarwyddiadau seq1 ac seq2 sydd i’w gweithredu yn eu trefn. Mae’n dychwelyd dilyniant cyfarwyddiadau y mae ei ddatganiadau’n ddatganiadau seq1 ac yna ddatganiadau seq2, gyda chyfarwyddiadau save ac restore priodol o amgylch seq1 i ddiogelu’r cofrestri yn regs a addasir gan seq1 ond sydd eu hangen ar seq2. I gyflawni hyn, mae preserving yn gyntaf yn creu dilyniant sydd â’r cyfarwyddiadau save gofynnol, yna ddatganiadau seq1, yna’r cyfarwyddiadau restore gofynnol. Mae ar y dilyniant hwn angen y cofrestri sy’n cael eu cadw a’u hadfer yn ogystal â’r cofrestri sydd eu hangen ar seq1, ac mae’n addasu’r cofrestri a addasir gan seq1 heblaw am y rhai sy’n cael eu cadw a’u hadfer. Yna atodir y dilyniant estynedig hwn ac seq2 at ei gilydd yn y ffordd arferol. Mae’r weithdrefn ganlynol yn gweithredu’r strategaeth hon yn ddychweliadol, gan gerdded i lawr y rhestr o gofrestri sydd i’w cadw:³²⁷

(define (preserving regs seq1 seq2)
  (if (null? regs)
      (append-instruction-sequences seq1 seq2)
      (let ((first-reg (car regs)))
        (if (and 
             (needs-register? seq2 first-reg)
             (modifies-register? seq1 
                                 first-reg))
            (preserving 
             (cdr regs)
             (make-instruction-sequence
              (list-union 
               (list first-reg)
               (registers-needed seq1))
              (list-difference
               (registers-modified seq1)
               (list first-reg))
              (append `((save ,first-reg))
                      (statements seq1)
                      `((restore ,first-reg))))
             seq2)
            (preserving 
             (cdr regs)
             seq1
             seq2)))))

Defnyddir cyfunydd dilyniannau arall, tack-on-instruction-sequence, gan compile-lambda i atodi corff gweithdrefn at ddilyniant arall. Gan nad yw corff y weithdrefn “yn y llinell” i’w weithredu fel rhan o’r dilyniant cyfun, nid yw ei ddefnydd o gofrestri’n effeithio ar ddefnydd cofrestri’r dilyniant y mae wedi’i ymgorffori ynddo. Felly anwybyddwn setiau’r cofrestri sydd eu hangen ar gorff y weithdrefn a’r rhai y mae’n eu haddasu pan atodwn ef at y dilyniant arall.

(define (tack-on-instruction-sequence 
         seq body-seq)
  (make-instruction-sequence
   (registers-needed seq)
   (registers-modified seq)
   (append (statements seq)
           (statements body-seq))))

Mae Compile-if ac compile-procedure-call yn defnyddio cyfunydd arbennig o’r enw parallel-instruction-sequences i atodi at ei gilydd y ddwy gangen amgen sy’n dilyn prawf. Ni chaiff y ddwy gangen byth eu gweithredu yn eu trefn; ar gyfer unrhyw werthusiad penodol o’r prawf, eir i mewn i’r naill gangen neu’r llall. Oherwydd hyn, mae’r cofrestri sydd eu hangen ar yr ail gangen yn dal i fod eu hangen ar y dilyniant cyfun, hyd yn oed os yw’r gangen gyntaf yn eu haddasu.

(define (parallel-instruction-sequences 
         seq1 seq2)
  (make-instruction-sequence
   (list-union (registers-needed seq1)
               (registers-needed seq2))
   (list-union (registers-modified seq1)
               (registers-modified seq2))
   (append (statements seq1)
           (statements seq2))))

5.5.5Enghraifft o God Wedi’i Grynhoi

Gan ein bod bellach wedi gweld holl elfennau’r crynhoydd, gadewch inni archwilio enghraifft o god wedi’i grynhoi i weld sut mae pethau’n cyd-fynd. Byddwn yn crynhoi diffiniad gweithdrefn factorial ddychweliadol drwy alw compile:

(compile
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n)))
 'val
 'next)

Rydym wedi pennu y dylid rhoi gwerth y mynegiad define yn y gofrestr val. Nid oes ots gennym beth mae’r cod wedi’i grynhoi’n ei wneud ar ôl gweithredu’r define, felly mae ein dewis o next yn ddisgrifydd cysylltu’n fympwyol.

Mae Compile yn penderfynu mai diffiniad yw’r mynegiad, felly mae’n galw compile-definition i grynhoi cod i gyfrifo’r gwerth sydd i’w aseinio (wedi’i dargedu at val), yna god i osod y diffiniad, yna god i roi gwerth y define (sef y symbol ok) yn y gofrestr darged, ac yn olaf y cod cysylltu. Cedwir Env o amgylch cyfrifo’r gwerth, oherwydd bod ei angen er mwyn gosod y diffiniad. Gan mai next yw’r cysylltiad, nid oes cod cysylltu yn yr achos hwn. Felly, sgerbwd y cod wedi’i grynhoi yw

⟨save env if modified by code to compute value⟩
  ⟨compilation of definition value, 
   target val, linkage next⟩
  ⟨restore env if saved above⟩
  (perform (op define-variable!)
           (const factorial)
           (reg val)
           (reg env))
  (assign val (const ok))

Y mynegiad sydd i’w grynhoi i gynhyrchu’r gwerth ar gyfer y newidyn factorial yw mynegiad lambda y mae ei werth yn weithdrefn sy’n cyfrifo ffactorialau. Mae Compile yn trin hyn drwy alw compile-lambda, sy’n crynhoi corff y weithdrefn, yn ei labelu’n bwynt mynediad newydd, ac yn cynhyrchu’r cyfarwyddyd a fydd yn cyfuno corff y weithdrefn yn y pwynt mynediad newydd â’r amgylchedd adeg rhedeg ac yn aseinio’r canlyniad i val. Yna mae’r dilyniant yn hepgor cod y weithdrefn wedi’i grynhoi, a fewnosodir yn y fan hon. Mae cod y weithdrefn ei hun yn dechrau drwy ymestyn amgylchedd diffiniad y weithdrefn â ffrâm sy’n rhwymo’r paramedr ffurfiol n i arg y weithdrefn. Yna daw corff y weithdrefn ei hun. Gan nad yw’r cod hwn ar gyfer gwerth y newidyn yn addasu’r gofrestr env, ni chynhyrchir yr save ac restore dewisol a ddangoswyd uchod. (Ni weithredir cod y weithdrefn yn entry2 ar y pwynt hwn, felly mae ei ddefnydd o env yn amherthnasol.) Felly, daw sgerbwd y cod wedi’i grynhoi yn

  (assign val (op make-compiled-procedure)
              (label entry2)
              (reg env))
  (goto (label after-lambda1))
entry2
  (assign env (op compiled-procedure-env)
              (reg proc))
  (assign env (op extend-environment)
              (const (n))
              (reg argl)
              (reg env))
  ⟨compilation of procedure body⟩
after-lambda1
  (perform (op define-variable!)
           (const factorial)
           (reg val) (reg env))
  (assign val (const ok))

Crynhöir corff gweithdrefn bob amser (gan compile-lambda-body) fel dilyniant â tharged val a chysylltiad return. Mae’r dilyniant yn yr achos hwn yn cynnwys un mynegiad if:

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

Mae Compile-if yn cynhyrchu cod sy’n cyfrifo’r traethiad yn gyntaf (wedi’i dargedu at val), yna’n gwirio’r canlyniad ac yn canghennu o amgylch y gangen wir os yw’r traethiad yn anwir. Cedwir Env ac continue o amgylch cod y traethiad, gan y gallai fod eu hangen ar gyfer gweddill y mynegiad if. Gan mai’r mynegiad if yw’r mynegiad olaf (a’r unig fynegiad) yn y dilyniant sy’n ffurfio corff y weithdrefn, ei darged yw val a’i gysylltiad yw return, felly crynhöir y canghennau gwir ac anwir ill dwy â tharged val a chysylltiad return. (Hynny yw, gwerth y mynegiad amodol, sef y gwerth a gyfrifir gan y naill neu’r llall o’i ganghennau, yw gwerth y weithdrefn.)

⟨save continue, env if modified by 
 predicate and needed by branches⟩
  ⟨compilation of predicate, 
   target val, linkage next⟩
  ⟨restore continue, env if saved above⟩
  (test (op false?) (reg val))
  (branch (label false-branch4))
true-branch5
  ⟨compilation of true branch, 
   target val, linkage return⟩
false-branch4
  ⟨compilation of false branch, 
   target val, linkage return⟩
after-if3

Galwad gweithdrefn yw’r traethiad (= n 1). Mae hwn yn chwilio am y gweithredydd (y symbol =) ac yn rhoi’r gwerth hwn yn proc. Yna mae’n cydosod yr argiau 1 a gwerth n yn argl. Yna mae’n profi a yw proc yn cynnwys gweithdrefn gyntefig neu gyfansawdd, ac yn dethol cangen gyntefig neu gangen gyfansawdd yn unol â hynny. Mae’r ddwy gangen yn ailddechrau yn y label after-call. Nid yw’r gofynion i gadw cofrestri o amgylch gwerthuso’r gweithredydd a’r operandau’n arwain at gadw unrhyw gofrestri, oherwydd nad yw’r gwerthusiadau hynny yn yr achos hwn yn addasu’r cofrestri dan sylw.

  (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-branch17))
compiled-branch16
  (assign continue (label after-call15))
  (assign val (op compiled-procedure-entry)
              (reg proc))
  (goto (reg val))
primitive-branch17
  (assign val (op apply-primitive-procedure)
              (reg proc)
              (reg argl))
after-call15

Crynhöir y gangen wir, sef y cysonyn 1 (â tharged val a chysylltiad return), yn

(assign val (const 1))
(goto (reg continue))

Mae’r cod ar gyfer y gangen anwir yn alwad gweithdrefn arall, lle mae’r weithdrefn yn werth y symbol *, a’r argiau’n n a chanlyniad galwad gweithdrefn arall (galwad i factorial). Mae pob un o’r galwadau hyn yn gosod proc ac argl a’i changhennau cyntefig a chyfansawdd ei hun. Mae Ffigur 5.17 yn dangos y crynhoi cyflawn o ddiffiniad y weithdrefn factorial. Sylwch fod yr save ac restore posibl ar continue ac env o amgylch y traethiad, a ddangoswyd uchod, yn cael eu cynhyrchu mewn gwirionedd, oherwydd bod y cofrestri hyn yn cael eu haddasu gan yr alwad gweithdrefn yn y traethiad ac yn angenrheidiol ar gyfer yr alwad gweithdrefn a’r cysylltiad return yn y canghennau.

Ffigur 5.17: $↓$ Crynhoi diffiniad y weithdrefn factorial.

;; construct the procedure and skip over code
;; for the procedure body
  (assign val
          (op make-compiled-procedure) 
          (label entry2) 
          (reg env))
  (goto (label after-lambda1))
entry2     ; calls to factorial will enter here
  (assign env 
          (op compiled-procedure-env)
          (reg proc))
  (assign env
          (op extend-environment) 
          (const (n)) 
          (reg argl) 
          (reg env))
;; begin actual procedure body
  (save continue)
  (save env)
;; compute (= n 1)
  (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-branch17))
compiled-branch16
  (assign continue (label after-call15))
  (assign val
          (op compiled-procedure-entry)
          (reg proc))
  (goto (reg val))
primitive-branch17
  (assign val 
          (op apply-primitive-procedure) 
          (reg proc) 
          (reg argl))
after-call15   ; val now contains result of (= n 1)
  (restore env)
  (restore continue)
  (test (op false?) (reg val))
  (branch (label false-branch4))
true-branch5  ; return 1
  (assign val (const 1))
  (goto (reg continue))

false-branch4
;; compute and return (* (factorial (- n 1)) n)
  (assign proc 
          (op lookup-variable-value) 
          (const *) 
          (reg env))
  (save continue)
  (save proc)   ; save * procedure
  (assign val 
          (op lookup-variable-value) 
          (const n) 
          (reg env))
  (assign argl (op list) (reg val))
  (save argl)   ; save partial argument list for *
;; compute (factorial (- n 1)), 
;; which is the other argument for *
  (assign proc
          (op lookup-variable-value) 
          (const factorial) 
          (reg env))
  (save proc)  ; save factorial procedure
;; compute (- n 1), which is the argument for factorial
  (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-branch8))
compiled-branch7
  (assign continue (label after-call6))
  (assign val
          (op compiled-procedure-entry)
          (reg proc))
  (goto (reg val))
primitive-branch8
  (assign val 
          (op apply-primitive-procedure) 
          (reg proc) 
          (reg argl))

after-call6   ; val now contains result of (- n 1)
  (assign argl (op list) (reg val))
  (restore proc) ; restore factorial
;; apply factorial
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch11))
compiled-branch10
  (assign continue (label after-call9))
  (assign val
          (op compiled-procedure-entry)
          (reg proc))
  (goto (reg val))
primitive-branch11
  (assign val 
          (op apply-primitive-procedure) 
          (reg proc) 
          (reg argl))
after-call9      ; val now contains result 
                 ; of (factorial (- n 1))
  (restore argl) ; restore partial argument list for *
  (assign argl (op cons) (reg val) (reg argl))
  (restore proc) ; restore *
  (restore continue)
;; apply * and return its value
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-branch14))
compiled-branch13
;; note that a compound procedure here
;; is called tail-recursively
  (assign val
          (op compiled-procedure-entry)
          (reg proc))
  (goto (reg val))
primitive-branch14
  (assign val 
          (op apply-primitive-procedure) 
          (reg proc) 
          (reg argl))
  (goto (reg continue))
after-call12
after-if3
after-lambda1
;; assign the procedure to the variable factorial
  (perform (op define-variable!) 
           (const factorial) 
           (reg val) 
           (reg env))
  (assign val (const ok))

Ymarfer 5.33: Ystyriwch y diffiniad canlynol o weithdrefn ffactorial, sydd ychydig yn wahanol i’r un a roddwyd uchod:
(define (factorial-alt n)
  (if (= n 1)
      1
      (* n (factorial-alt (- n 1)))))
Crynhowch y weithdrefn hon a chymharu’r cod sy’n deillio ohoni â’r cod a gynhyrchwyd ar gyfer factorial. Esboniwch unrhyw wahaniaethau a ganfyddwch. A yw’r naill raglen yn gweithredu’n fwy effeithlon na’r llall?

Ymarfer 5.34: Crynhowch y weithdrefn ffactorial iteru
(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))
Anodwch y cod sy’n deillio o hyn, gan ddangos y gwahaniaeth hanfodol rhwng y cod ar gyfer fersiynau iteru a dychweliadol factorial sy’n peri i un broses gronni gofod pentwr ac i’r llall redeg mewn gofod pentwr cyson.

Ymarfer 5.35: Pa fynegiad a grynhowyd i gynhyrchu’r cod a ddangosir yn Ffigur 5.18?

Ffigur 5.18: $↓$ Enghraifft o allbwn crynhoydd. Gweler Ymarfer 5.35.

(assign val (op make-compiled-procedure) 
            (label entry16) 
            (reg env))
  (goto (label after-lambda15))
entry16
  (assign env (op compiled-procedure-env)
              (reg proc))
  (assign env (op extend-environment) 
              (const (x)) 
              (reg argl) 
              (reg env))
  (assign proc (op lookup-variable-value) 
               (const +) 
               (reg env))
  (save continue) (save proc) (save env)
  (assign proc (op lookup-variable-value) 
               (const g) 
               (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 (op lookup-variable-value)
              (const x) 
              (reg env))
  (assign argl (op cons)
               (reg val)
               (reg argl))
  (test (op primitive-procedure?)
        (reg proc))
  (branch (label primitive-branch19))
compiled-branch18
  (assign continue (label after-call17))
  (assign val
          (op compiled-procedure-entry)
          (reg proc))
  (goto (reg val))
primitive-branch19
  (assign val
          (op apply-primitive-procedure)
          (reg proc) 
          (reg argl))
after-call17
  (assign argl (op list) (reg val))
  (restore proc)
  (test (op primitive-procedure?)
        (reg proc))
  (branch (label primitive-branch22))
compiled-branch21
  (assign continue (label after-call20))
  (assign val
          (op compiled-procedure-entry)
          (reg proc))
  (goto (reg val))
primitive-branch22
  (assign val 
          (op apply-primitive-procedure) 
          (reg proc) 
          (reg argl))
after-call20
  (assign argl (op list) (reg val))
  (restore env)
  (assign val
          (op lookup-variable-value) 
          (const x) 
          (reg env))
  (assign argl
          (op cons)
          (reg val)
          (reg argl))
  (restore proc)
  (restore continue)
  (test (op primitive-procedure?)
        (reg proc))
  (branch (label primitive-branch25))
compiled-branch24
  (assign val (op compiled-procedure-entry)
              (reg proc))
  (goto (reg val))
primitive-branch25
  (assign val 
          (op apply-primitive-procedure)
          (reg proc) 
          (reg argl))
  (goto (reg continue))
after-call23
after-lambda15
  (perform (op define-variable!) 
           (const f) 
           (reg val) 
           (reg env))
  (assign val (const ok))

Ymarfer 5.36: Pa drefn werthuso y mae ein crynhoydd yn ei chynhyrchu ar gyfer operandau cyfuniad? A yw o’r chwith i’r dde, o’r dde i’r chwith, neu mewn rhyw drefn arall? Ymhle yn y crynhoydd y pennir y drefn hon? Addaswch y crynhoydd fel ei fod yn cynhyrchu rhyw drefn werthuso arall. (Gweler y drafodaeth o drefn werthuso ar gyfer y gwerthusydd rheolaeth eglur yn 5.4.1.) Sut mae newid trefn gwerthuso operandau’n effeithio ar effeithlonrwydd y cod sy’n adeiladu’r rhestr argiau?

Ymarfer 5.37: Un ffordd o ddeall mecanwaith preserving y crynhoydd ar gyfer optimeiddio defnydd o’r pentwr yw gweld pa weithrediadau ychwanegol a gynhyrchid pe na baem yn defnyddio’r syniad hwn. Addaswch preserving fel ei fod bob amser yn cynhyrchu’r gweithrediadau save ac restore. Crynhowch rai mynegiadau syml a nodwch y gweithrediadau pentwr diangen a gynhyrchir. Cymharwch y cod â’r cod a gynhyrchir gyda’r mecanwaith preserving yn gyfan.

Ymarfer 5.38: Mae ein crynhoydd yn glyfar am osgoi gweithrediadau pentwr diangen, ond nid yw’n glyfar o gwbl wrth grynhoi galwadau i weithdrefnau cyntefig yr iaith yn nhermau’r gweithrediadau cyntefig a ddarperir gan y peiriant. Er enghraifft, ystyriwch faint o god a grynhoir i gyfrifo (+ a 1): Mae’r cod yn gosod rhestr argiau yn argl, yn rhoi’r weithdrefn adio gyntefig (y mae’n ei chanfod drwy chwilio am y symbol + yn yr amgylchedd) yn proc, ac yn profi a yw’r weithdrefn yn gyntefig neu’n gyfansawdd. Mae’r crynhoydd bob amser yn cynhyrchu cod i gyflawni’r prawf, yn ogystal â chod ar gyfer canghennau cyntefig a chyfansawdd (dim ond un ohonynt a weithredir). Nid ydym wedi dangos y rhan o’r rheolydd sy’n gweithredu’r gweithdrefnau cyntefig, ond tybiwn fod y cyfarwyddiadau hyn yn defnyddio gweithrediadau rhifyddol cyntefig yn llwybrau data’r peiriant. Ystyriwch faint yn llai o god a gynhyrchid pe gallai’r crynhoydd fewnlinio cod gweithdrefnau cyntefig—hynny yw, pe gallai gynhyrchu cod i ddefnyddio’r gweithrediadau peiriant cyntefig hyn yn uniongyrchol. Gellid crynhoi’r mynegiad (+ a 1) yn rhywbeth mor syml ag³²⁸
(assign val (op lookup-variable-value) 
            (const a) 
            (reg env))
(assign val (op +)
            (reg val)
            (const 1))
Yn yr ymarfer hwn, byddwn yn ymestyn ein crynhoydd i gefnogi mewnlinio cod gweithdrefnau cyntefig dethol. Cynhyrchir cod at ddiben arbennig ar gyfer galwadau i’r gweithdrefnau cyntefig hyn yn lle’r cod cymhwyso gweithdrefn cyffredinol. Er mwyn cefnogi hyn, ychwanegwn gofrestri argiau arbennig arg1 ac arg2 at ein peiriant. Bydd gweithrediadau rhifyddol cyntefig y peiriant yn cymryd eu mewnbynnau o arg1 ac arg2. Gellir rhoi’r canlyniadau yn val, arg1, neu arg2.

Rhaid i’r crynhoydd allu adnabod cymhwysiad gweithdrefn gyntefig y mewnlinir ei chod yn y rhaglen ffynhonnell. Byddwn yn ymestyn y dethol gweithdrefn yn y weithdrefn compile i adnabod enwau’r gweithdrefnau cyntefig hyn yn ogystal â’r geiriau neilltuedig (y ffurfiau arbennig) y mae’n eu hadnabod ar hyn o bryd.³²⁹ Ar gyfer pob ffurf arbennig mae gan ein crynhoydd gynhyrchydd cod. Yn yr ymarfer hwn byddwn yn adeiladu teulu o gynhyrchwyr cod ar gyfer y gweithdrefnau cyntefig y mewnlinir eu cod.

Yn wahanol i’r ffurfiau arbennig, mae angen gwerthuso operandau pob un o’r gweithdrefnau cyntefig y mewnlinir eu cod. Ysgrifennwch gynhyrchydd cod spread-arguments i’w ddefnyddio gan yr holl gynhyrchwyr cod mewnlinio. Dylai Spread-arguments gymryd rhestr operandau a chrynhoi’r operandau a roddwyd gan eu targedu at gofrestri argiau olynol. Sylwch y gall operand gynnwys galwad i weithdrefn gyntefig y mewnlinir ei chod, felly bydd rhaid cadw cofrestri argiau yn ystod gwerthuso operandau.
Ar gyfer pob un o’r gweithdrefnau cyntefig =, *, -, ac +, ysgrifennwch gynhyrchydd cod sy’n cymryd cyfuniad â’r gweithredydd hwnnw, ynghyd â tharged a disgrifydd cysylltu, ac yn cynhyrchu cod i ddosbarthu’r argiau i’r cofrestri ac yna gyflawni’r gweithrediad wedi’i dargedu at y targed penodol â’r cysylltiad penodol. Dim ond mynegiadau â dau operand sydd angen eu trin. Parwch i compile ddethol y cynhyrchwyr cod hyn.
Rhowch gynnig ar eich crynhoydd newydd ar yr enghraifft factorial. Cymharwch y cod sy’n deillio o hyn â’r canlyniad a gynhyrchir heb fewnlinio cod.
Ymestynnwch eich cynhyrchwyr cod ar gyfer + ac * fel y gallant drin mynegiadau â niferoedd mympwyol o operandau. Bydd rhaid crynhoi mynegiad â mwy na dau operand yn ddilyniant o weithrediadau, pob un â dau fewnbwn yn unig.

5.5.6Cyfeirio Geiriadurol

Un o’r optimeiddiadau mwyaf cyffredin a gyflawnir gan grynhowyr yw optimeiddio chwilio am newidynnau. Mae ein crynhoydd, fel yr ydym wedi’i weithredu hyd yma, yn cynhyrchu cod sy’n defnyddio gweithrediad lookup-variable-value y peiriant gwerthuso. Mae hwn yn chwilio am newidyn drwy ei gymharu â phob newidyn sydd wedi’i rwymo ar hyn o bryd, gan weithio fesul ffrâm tuag allan drwy’r amgylchedd adeg rhedeg. Gall y chwilio hwn fod yn gostus os yw’r fframiau wedi’u nythu’n ddwfn neu os oes llawer o newidynnau. Er enghraifft, ystyriwch y broblem o chwilio am werth x wrth werthuso’r mynegiad (* x y z) mewn cymhwysiad o’r weithdrefn a ddychwelir gan

(let ((x 3) (y 4))
  (lambda (a b c d e)
    (let ((y (* a b x))
          (z (+ c d x)))
      (* x y z))))

Gan mai siwgr cystrawennol ar gyfer cyfuniad lambda yn unig yw mynegiad let, mae’r mynegiad hwn yn gyfwerth â

((lambda (x y)
   (lambda (a b c d e)
     ((lambda (y z) (* x y z))
      (* a b x)
      (+ c d x))))
 3
 4)

Bob tro y mae lookup-variable-value yn chwilio am x, rhaid iddo benderfynu nad yw’r symbol x yn eq? ag y neu z (yn y ffrâm gyntaf), nac ag a, b, c, d, neu e (yn yr ail ffrâm). Tybiwn, am y tro, nad yw ein rhaglenni’n defnyddio define—mai dim ond ag lambda y rhwymir newidynnau. Gan fod gan ein hiaith gwmpas geiriadurol, bydd gan yr amgylchedd adeg rhedeg ar gyfer unrhyw fynegiad strwythur sy’n dilyn strwythur geiriadurol y rhaglen y mae’r mynegiad yn ymddangos ynddi.³³⁰ Felly gall y crynhoydd wybod, wrth ddadansoddi’r mynegiad uchod, y ceir y newidyn x yn (* x y z) ddwy ffrâm allan o’r ffrâm bresennol bob tro y cymhwysir y weithdrefn, ac mai hwn fydd y newidyn cyntaf yn y ffrâm honno.

Gallwn fanteisio ar y ffaith hon drwy ddyfeisio math newydd o weithrediad chwilio am newidyn, lexical-address-lookup, sy’n cymryd yn argiau amgylchedd a chyfeiriad geiriadurol sy’n cynnwys dau rif: rhif ffrâm, sy’n pennu faint o fframiau i’w hepgor, a rhif dadleoliad, sy’n pennu faint o newidynnau i’w hepgor yn y ffrâm honno. Bydd Lexical-address-lookup yn cynhyrchu gwerth y newidyn sydd wedi’i storio yn y cyfeiriad geiriadurol hwnnw mewn perthynas â’r amgylchedd presennol. Os ychwanegwn y gweithrediad lexical-address-lookup at ein peiriant, gallwn beri i’r crynhoydd gynhyrchu cod sy’n cyfeirio at newidynnau drwy’r gweithrediad hwn, yn hytrach nag lookup-variable-value. Yn yr un modd, gall ein cod wedi’i grynhoi ddefnyddio gweithrediad newydd lexical-address-set! yn lle set-variable-value!.

Er mwyn cynhyrchu cod o’r fath, rhaid i’r crynhoydd allu pennu cyfeiriad geiriadurol newidyn y mae ar fin crynhoi cyfeiriad ato. Mae cyfeiriad geiriadurol newidyn mewn rhaglen yn dibynnu ar ble yn y cod yr ydym. Er enghraifft, yn y rhaglen ganlynol, cyfeiriad x yn y mynegiad ⟨e1⟩ yw (2, 0)—dwy ffrâm yn ôl a’r newidyn cyntaf yn y ffrâm. Ar y pwynt hwnnw mae y yn y cyfeiriad (0, 0) ac c yn y cyfeiriad (1, 2). Yn y mynegiad ⟨e2⟩, mae x yn (1, 0), y yn (1, 1), ac c yn (0, 2).

((lambda (x y)
   (lambda (a b c d e)
     ((lambda (y z) ⟨e1⟩)
      ⟨e2⟩
      (+ c d x))))
 3
 4)

Un ffordd i’r crynhoydd gynhyrchu cod sy’n defnyddio cyfeirio geiriadurol yw cynnal strwythur data o’r enw amgylchedd amser crynhoi. Mae hwn yn cadw golwg ar ba newidynnau fydd ym mha safleoedd ym mha fframiau yn yr amgylchedd adeg rhedeg pan weithredir gweithrediad penodol i gyrchu newidyn. Mae’r amgylchedd amser crynhoi yn rhestr o fframiau, pob un yn cynnwys rhestr o newidynnau. (Wrth gwrs, ni fydd gwerthoedd wedi’u rhwymo i’r newidynnau, gan na chyfrifir gwerthoedd adeg crynhoi.) Daw’r amgylchedd amser crynhoi yn arg ychwanegol i compile ac fe’i trosglwyddir ymlaen i bob cynhyrchydd cod. Mae’r alwad lefel uchaf i compile yn defnyddio amgylchedd amser crynhoi gwag. Pan grynhoir corff lambda, mae compile-lambda-body yn ymestyn yr amgylchedd amser crynhoi â ffrâm sy’n cynnwys paramedrau’r weithdrefn, fel y crynhoir y dilyniant sy’n ffurfio’r corff â’r amgylchedd estynedig hwnnw. Ar bob pwynt yn y crynhoi, mae compile-variable ac compile-assignment yn defnyddio’r amgylchedd amser crynhoi er mwyn cynhyrchu’r cyfeiriadau geiriadurol priodol.

Mae Ymarfer 5.39 hyd Ymarfer 5.43 yn disgrifio sut i gwblhau’r braslun hwn o’r strategaeth cyfeirio geiriadurol er mwyn cynnwys chwilio geiriadurol yn y crynhoydd. Mae Ymarfer 5.44 yn disgrifio defnydd arall o’r amgylchedd amser crynhoi.

Ymarfer 5.39: Ysgrifennwch weithdrefn lexical-address-lookup sy’n gweithredu’r gweithrediad chwilio newydd. Dylai gymryd dau arg—cyfeiriad geiriadurol ac amgylchedd adeg rhedeg—a dychwelyd gwerth y newidyn sydd wedi’i storio yn y cyfeiriad geiriadurol penodedig. Dylai Lexical-address-lookup nodi gwall os mai’r symbol *unassigned* yw gwerth y newidyn.³³¹ Ysgrifennwch hefyd weithdrefn lexical-address-set! sy’n gweithredu’r gweithrediad sy’n newid gwerth y newidyn mewn cyfeiriad geiriadurol penodedig.

Ymarfer 5.40: Addaswch y crynhoydd i gynnal yr amgylchedd amser crynhoi fel y disgrifiwyd uchod. Hynny yw, ychwanegwch arg amgylchedd amser crynhoi at compile a’r amrywiol gynhyrchwyr cod, a’i ymestyn yn compile-lambda-body.

Ymarfer 5.41: Ysgrifennwch weithdrefn find-variable sy’n cymryd newidyn ac amgylchedd amser crynhoi yn argiau ac yn dychwelyd cyfeiriad geiriadurol y newidyn mewn perthynas â’r amgylchedd hwnnw. Er enghraifft, yn y darn o raglen a ddangosir uchod, yr amgylchedd amser crynhoi wrth grynhoi’r mynegiad ⟨e1⟩ yw ((y z) (a b c d e) (x y)). Dylai Find-variable gynhyrchu
(find-variable 
 'c '((y z) (a b c d e) (x y)))
(1 2)

(find-variable 
 'x '((y z) (a b c d e) (x y)))
(2 0)

(find-variable 
 'w '((y z) (a b c d e) (x y)))
not-found

Ymarfer 5.42: Gan ddefnyddio find-variable o Ymarfer 5.41, ailysgrifennwch compile-variable ac compile-assignment i allbynnu cyfarwyddiadau cyfeiriadau geiriadurol. Mewn achosion lle mae find-variable yn dychwelyd not-found (hynny yw, lle nad yw’r newidyn yn yr amgylchedd amser crynhoi), dylech beri i’r cynhyrchwyr cod ddefnyddio gweithrediadau’r gwerthusydd, fel o’r blaen, i chwilio am y rhwymiad. (Yr unig le y gall newidyn nas ceir adeg crynhoi fod ynddo yw’r amgylchedd byd-eang, sy’n rhan o’r amgylchedd adeg rhedeg ond nad yw’n rhan o’r amgylchedd amser crynhoi.³³² Felly, os dymunwch, gallwch beri i weithrediadau’r gwerthusydd edrych yn uniongyrchol yn yr amgylchedd byd-eang, y gellir ei gael drwy’r gweithrediad (op get-global-environment), yn lle peri iddynt chwilio’r amgylchedd adeg rhedeg cyfan a geir yn env.) Profwch y crynhoydd wedi’i addasu ar ychydig o achosion syml, megis y cyfuniad lambda nythog ar ddechrau’r adran hon.

Ymarfer 5.43: Dadleuasom yn 4.1.6 na ddylid ystyried diffiniadau mewnol ar gyfer strwythur blociau yn ffurfiau define “go iawn.” Yn hytrach, dylid dehongli corff gweithdrefn fel pe bai’r newidynnau mewnol sy’n cael eu diffinio wedi’u gosod yn newidynnau lambda cyffredin wedi’u cychwyn â’u gwerthoedd cywir gan ddefnyddio set!. Dangosodd 4.1.6 ac Ymarfer 4.16 sut i addasu’r dehonglydd metagylchol i gyflawni hyn drwy sganio’r diffiniadau mewnol allan. Addaswch y crynhoydd i gyflawni’r un trawsffurfiad cyn iddo grynhoi corff gweithdrefn.

Ymarfer 5.44: Yn yr adran hon rydym wedi canolbwyntio ar ddefnyddio’r amgylchedd amser crynhoi i gynhyrchu cyfeiriadau geiriadurol. Ond mae defnyddiau eraill i amgylcheddau amser crynhoi. Er enghraifft, yn Ymarfer 5.38 cynyddasom effeithlonrwydd cod wedi’i grynhoi drwy fewnlinio cod gweithdrefnau cyntefig. Roedd ein gweithrediad yn trin enwau gweithdrefnau y mewnlinir eu cod fel geiriau neilltuedig. Pe bai rhaglen yn ailrwymo enw o’r fath, byddai’r mecanwaith a ddisgrifiwyd yn Ymarfer 5.38 yn dal i fewnlinio ei god fel gweithdrefn gyntefig, gan anwybyddu’r rhwymiad newydd. Er enghraifft, ystyriwch y weithdrefn
(lambda (+ * a b x y)
  (+ (* a x) (* b y)))
sy’n cyfrifo cyfuniad llinol o x ac y. Gallem ei galw â’r argiau +matrix, *matrix, a phedwar matrics, ond byddai’r crynhoydd mewnlinio cod yn dal i fewnlinio’r + a’r * yn (+ (* a x) (* b y)) fel + ac * cyntefig. Addaswch y crynhoydd mewnlinio cod i ymgynghori â’r amgylchedd amser crynhoi er mwyn crynhoi’r cod cywir ar gyfer mynegiadau sy’n cynnwys enwau gweithdrefnau cyntefig. (Bydd y cod yn gweithio’n gywir cyn belled nad yw’r rhaglen yn defnyddio define nac set! ar yr enwau hyn.)

5.5.7Cysylltu Cod Wedi’i Grynhoi â’r Gwerthusydd

Nid ydym eto wedi esbonio sut i lwytho cod wedi’i grynhoi i’r peiriant gwerthuso na sut i’w redeg. Tybiwn fod peiriant y gwerthusydd rheolaeth eglur wedi’i ddiffinio fel yn 5.4.4, gyda’r gweithrediadau ychwanegol a bennwyd yn Troednodyn 323. Byddwn yn gweithredu gweithdrefn compile-and-go sy’n crynhoi mynegiad Scheme, yn llwytho’r cod gwrthrych sy’n deillio o hynny i’r peiriant gwerthuso, ac yn peri i’r peiriant redeg y cod yn amgylchedd byd-eang y gwerthusydd, argraffu’r canlyniad, a mynd i mewn i ddolen yrru’r gwerthusydd. Byddwn hefyd yn addasu’r gwerthusydd fel y gall mynegiadau wedi’u dehongli alw gweithdrefnau wedi’u crynhoi yn ogystal â rhai wedi’u dehongli. Yna gallwn roi gweithdrefn wedi’i chrynhoi yn y peiriant a defnyddio’r gwerthusydd i’w galw:

(compile-and-go
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n))))

;;; EC-Eval value:
ok

;;; EC-Eval input:
(factorial 5)

;;; EC-Eval value:
120

I alluogi’r gwerthusydd i drin gweithdrefnau wedi’u crynhoi (er enghraifft, i werthuso’r alwad i factorial uchod), mae angen newid y cod yn apply-dispatch (5.4.1) fel ei fod yn adnabod gweithdrefnau wedi’u crynhoi (yn wahanol i weithdrefnau cyfansawdd neu gyntefig) ac yn trosglwyddo rheolaeth yn uniongyrchol i bwynt mynediad y cod wedi’i grynhoi:³³³

apply-dispatch
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-apply))
  (test (op compound-procedure?) (reg proc))
  (branch (label compound-apply))
  (test (op compiled-procedure?) (reg proc))
  (branch (label compiled-apply))
  (goto (label unknown-procedure-type))

compiled-apply
  (restore continue)
  (assign val
          (op compiled-procedure-entry)
          (reg proc))
  (goto (reg val))

Sylwch ar adfer continue yn compiled-apply. Cofiwch fod y gwerthusydd wedi’i drefnu fel y byddai’r parhad ar frig y pentwr yn apply-dispatch. Ar y llaw arall, mae pwynt mynediad y cod wedi’i grynhoi yn disgwyl i’r parhad fod yn continue, felly rhaid adfer continue cyn gweithredu’r cod wedi’i grynhoi.

I’n galluogi i redeg rhywfaint o god wedi’i grynhoi pan ddechreuwn y peiriant gwerthuso, ychwanegwn gyfarwyddyd branch ar ddechrau’r peiriant gwerthuso, sy’n peri i’r peiriant fynd i bwynt mynediad newydd os yw’r gofrestr flag wedi’i gosod.³³⁴

;; branches if flag is set:
(branch (label external-entry)) 
read-eval-print-loop
  (perform (op initialize-stack))
  …

Mae External-entry yn tybio bod y peiriant yn cael ei gychwyn gydag val yn cynnwys lleoliad dilyniant cyfarwyddiadau sy’n rhoi canlyniad yn val ac yn gorffen ag (goto (reg continue)). Mae dechrau yn y pwynt mynediad hwn yn neidio i’r lleoliad a ddynodir gan val, ond yn gyntaf yn aseinio continue fel y bydd y gweithredu’n dychwelyd i print-result, sy’n argraffu’r gwerth yn val ac yna’n mynd i ddechrau dolen darllen-gwerthuso-argraffu’r gwerthusydd.³³⁵

external-entry
  (perform (op initialize-stack))
  (assign env (op get-global-environment))
  (assign continue (label print-result))
  (goto (reg val))

Yn awr gallwn ddefnyddio’r weithdrefn ganlynol i grynhoi diffiniad gweithdrefn, gweithredu’r cod wedi’i grynhoi, a rhedeg y ddolen darllen-gwerthuso-argraffu fel y gallwn roi cynnig ar y weithdrefn. Gan ein bod am i’r cod wedi’i grynhoi ddychwelyd i’r lleoliad yn continue â’i ganlyniad yn val, crynhown y mynegiad â tharged val a chysylltiad return. Er mwyn trawsffurfio’r cod gwrthrych a gynhyrchir gan y crynhoydd yn gyfarwyddiadau gweithredadwy ar gyfer peiriant cofrestri’r gwerthusydd, defnyddiwn y weithdrefn assemble o’r efelychydd peiriant cofrestri (5.2.2). Yna cychwynnwn y gofrestr val i bwyntio at y rhestr gyfarwyddiadau, gosodwn yr flag fel y bydd y gwerthusydd yn mynd i external-entry, a chychwynnwn y gwerthusydd.

(define (compile-and-go expression)
  (let ((instructions
         (assemble 
          (statements
           (compile 
            expression 'val 'return))
          eceval)))
    (set! the-global-environment
          (setup-environment))
    (set-register-contents! 
     eceval 'val instructions)
    (set-register-contents! 
     eceval 'flag true)
    (start eceval)))

Os ydym wedi sefydlu monitro’r pentwr, fel ar ddiwedd 5.4.4, gallwn archwilio defnydd cod wedi’i grynhoi o’r pentwr:

(compile-and-go
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n))))
(total-pushes = 0, maximum-depth = 0)

;;; EC-Eval value:
ok

;;; EC-Eval input:
(factorial 5)
(total-pushes = 31, maximum-depth = 14)

;;; EC-Eval value:
120

Cymharwch yr enghraifft hon â gwerthuso (factorial 5) gan ddefnyddio’r fersiwn wedi’i dehongli o’r un weithdrefn, a ddangosir ar ddiwedd 5.4.4. Roedd ar y fersiwn wedi’i dehongli angen 144 o wthiadau ac uchafswm dyfnder pentwr o 28. Mae hyn yn dangos yr optimeiddio sy’n deillio o’n strategaeth grynhoi.

Dehongli a chrynhoi

Gyda’r rhaglenni yn yr adran hon, gallwn bellach arbrofi â strategaethau gweithredu amgen dehongli a chrynhoi.³³⁶ Mae dehonglydd yn codi’r peiriant i lefel rhaglen y defnyddiwr; mae crynhoydd yn gostwng rhaglen y defnyddiwr i lefel yr iaith beiriant. Gallwn ystyried iaith Scheme (neu unrhyw iaith raglennu) yn deulu cydlynol o haniaethau wedi’u codi ar yr iaith beiriant. Mae dehonglwyr yn dda ar gyfer datblygu a dadfygio rhaglenni’n rhyngweithiol oherwydd bod camau gweithredu’r rhaglen wedi’u trefnu yn nhermau’r haniaethau hyn, ac felly’n fwy dealladwy i’r rhaglennydd. Gall cod wedi’i grynhoi weithredu’n gyflymach, oherwydd bod camau gweithredu’r rhaglen wedi’u trefnu yn nhermau’r iaith beiriant, ac mae’r crynhoydd yn rhydd i wneud optimeiddiadau sy’n croesi’r haniaethau lefel uwch.³³⁷

Mae dewisiadau dehongli a chrynhoi hefyd yn arwain at strategaethau gwahanol ar gyfer trosglwyddo ieithoedd i gyfrifiaduron newydd. Tybiwch ein bod am weithredu Lisp ar gyfer peiriant newydd. Un strategaeth yw dechrau â gwerthusydd rheolaeth eglur 5.4 a throsi ei gyfarwyddiadau’n gyfarwyddiadau ar gyfer y peiriant newydd. Strategaeth wahanol yw dechrau â’r crynhoydd a newid y cynhyrchwyr cod fel eu bod yn cynhyrchu cod ar gyfer y peiriant newydd. Mae’r ail strategaeth yn caniatáu inni redeg unrhyw raglen Lisp ar y peiriant newydd drwy ei chrynhoi’n gyntaf â’r crynhoydd sy’n rhedeg ar ein system Lisp wreiddiol, a’i chysylltu â fersiwn wedi’i chrynhoi o’r llyfrgell amser rhedeg.³³⁸ Yn well fyth, gallwn grynhoi’r crynhoydd ei hun, a’i redeg ar y peiriant newydd i grynhoi rhaglenni Lisp eraill.³³⁹ Neu gallwn grynhoi un o ddehonglwyr 4.1 i gynhyrchu dehonglydd sy’n rhedeg ar y peiriant newydd.

Ymarfer 5.45: Drwy gymharu’r gweithrediadau pentwr a ddefnyddir gan god wedi’i grynhoi â’r gweithrediadau pentwr a ddefnyddir gan y gwerthusydd ar gyfer yr un cyfrifiad, gallwn bennu i ba raddau y mae’r crynhoydd yn optimeiddio defnydd o’r pentwr, o ran cyflymder (lleihau cyfanswm nifer y gweithrediadau pentwr) ac o ran gofod (lleihau uchafswm dyfnder y pentwr). Mae cymharu’r defnydd optimaidd hwn o’r pentwr â pherfformiad peiriant at ddiben arbennig ar gyfer yr un cyfrifiad yn rhoi rhyw arwydd o ansawdd y crynhoydd.

Gofynnodd Ymarfer 5.27 ichi bennu, fel ffwythiant o $n$ , nifer y gwthiadau ac uchafswm dyfnder y pentwr sydd eu hangen ar y gwerthusydd i gyfrifo $n!$ gan ddefnyddio’r weithdrefn ffactorial ddychweliadol a roddwyd uchod. Gofynnodd Ymarfer 5.14 ichi wneud yr un mesuriadau ar gyfer y peiriant ffactorial at ddiben arbennig a ddangosir yn Ffigur 5.11. Yn awr cyflawnwch yr un dadansoddiad gan ddefnyddio’r weithdrefn factorial wedi’i chrynhoi.
Cymerwch gymhareb nifer y gwthiadau yn y fersiwn wedi’i chrynhoi i nifer y gwthiadau yn y fersiwn wedi’i dehongli, a gwnewch yr un peth ar gyfer uchafswm dyfnder y pentwr. Gan fod nifer y gweithrediadau a dyfnder y pentwr a ddefnyddir i gyfrifo $n!$ yn llinol mewn $n$ , dylai’r cymarebau hyn ddynesu at gysonion wrth i $n$ fynd yn fawr. Beth yw’r cysonion hyn? Yn yr un modd, canfyddwch gymarebau defnydd y peiriant at ddiben arbennig o’r pentwr i ddefnydd y fersiwn wedi’i dehongli.

Cymharwch y cymarebau ar gyfer cod at ddiben arbennig yn erbyn cod wedi’i ddehongli â’r cymarebau ar gyfer cod wedi’i grynhoi yn erbyn cod wedi’i ddehongli. Dylech ganfod bod y peiriant at ddiben arbennig yn gwneud yn llawer gwell na’r cod wedi’i grynhoi, gan y dylai cod y rheolydd a luniwyd â llaw at y diben fod yn llawer gwell na’r hyn a gynhyrchir gan ein crynhoydd elfennol at ddibenion cyffredinol.
A allwch awgrymu gwelliannau i’r crynhoydd a fyddai’n ei helpu i gynhyrchu cod y byddai ei berfformiad yn nes at berfformiad y fersiwn a luniwyd â llaw?

Ymarfer 5.46: Cyflawnwch ddadansoddiad fel yr un yn Ymarfer 5.45 i bennu effeithiolrwydd crynhoi’r weithdrefn Fibonacci â dychweliad coeden
(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))
o gymharu ag effeithiolrwydd defnyddio’r peiriant Fibonacci at ddiben arbennig yn Ffigur 5.12. (Am fesuriad o berfformiad y fersiwn wedi’i dehongli, gweler Ymarfer 5.29.) Ar gyfer Fibonacci, nid yw’r adnodd amser a ddefnyddir yn llinol mewn $n;$ , felly ni fydd cymarebau’r gweithrediadau pentwr yn dynesu at werth terfyn sy’n annibynnol ar $n$ .

Ymarfer 5.47: Disgrifiodd yr adran hon sut i addasu’r gwerthusydd rheolaeth eglur fel y gall cod wedi’i ddehongli alw gweithdrefnau wedi’u crynhoi. Dangoswch sut i addasu’r crynhoydd fel y gall gweithdrefnau wedi’u crynhoi alw nid yn unig weithdrefnau cyntefig a gweithdrefnau wedi’u crynhoi, ond gweithdrefnau wedi’u dehongli hefyd. Mae hyn yn gofyn am addasu compile-procedure-call i drin achos gweithdrefnau cyfansawdd (wedi’u dehongli). Gwnewch yn siŵr eich bod yn trin yr un holl gyfuniadau o target ac linkage ag yn compile-proc-appl. I gyflawni cymhwyso’r weithdrefn ei hun, mae angen i’r cod neidio i bwynt mynediad compound-apply y gwerthusydd. Ni ellir cyfeirio’n uniongyrchol at y label hwn mewn cod gwrthrych (gan fod y cydosodydd yn gofyn bod pob label y cyfeirir ato gan y cod y mae’n ei gydosod wedi’i ddiffinio yno), felly ychwanegwn gofrestr o’r enw compapp at y peiriant gwerthuso i ddal y pwynt mynediad hwn, ac ychwanegwn gyfarwyddyd i’w chychwyn:
  (assign compapp (label compound-apply))
  ;; branches if flag is set:
  (branch (label external-entry))
read-eval-print-loop …
I brofi eich cod, dechreuwch drwy ddiffinio gweithdrefn f sy’n galw gweithdrefn g. Defnyddiwch compile-and-go i grynhoi diffiniad f a chychwyn y gwerthusydd. Yn awr, gan deipio wrth y gwerthusydd, diffiniwch g a cheisiwch alw f.

Ymarfer 5.48: Mae’r rhyngwyneb compile-and-go a weithredwyd yn yr adran hon yn lletchwith, gan mai dim ond unwaith y gellir galw’r crynhoydd (pan gychwynnir y peiriant gwerthuso). Ymestynnwch y rhyngwyneb crynhoydd-dehonglydd drwy ddarparu gweithdrefn gyntefig compile-and-run y gellir ei galw o’r tu mewn i’r gwerthusydd rheolaeth eglur fel a ganlyn:
;;; EC-Eval input:
(compile-and-run
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n))))

;;; EC-Eval value:
ok

;;; EC-Eval input:
(factorial 5)

;;; EC-Eval value:
120

Ymarfer 5.49: Fel dewis amgen i ddefnyddio dolen darllen-gwerthuso-argraffu’r gwerthusydd rheolaeth eglur, dyluniwch beiriant cofrestri sy’n cyflawni dolen darllen-crynhoi-gweithredu-argraffu. Hynny yw, dylai’r peiriant redeg dolen sy’n darllen mynegiad, yn ei grynhoi, yn cydosod ac yn gweithredu’r cod sy’n deillio ohono, ac yn argraffu’r canlyniad. Mae hyn yn hawdd ei redeg yn ein trefniant efelychu, gan y gallwn drefnu i alw’r gweithdrefnau compile ac assemble yn “weithrediadau peiriant cofrestri.”

Ymarfer 5.50: Defnyddiwch y crynhoydd i grynhoi gwerthusydd metagylchol 4.1 a rhedeg y rhaglen hon gan ddefnyddio’r efelychydd peiriant cofrestri. (I grynhoi mwy nag un diffiniad ar y tro, gallwch becynnu’r diffiniadau mewn begin.) Bydd y dehonglydd sy’n deillio o hyn yn rhedeg yn araf iawn oherwydd y lefelau lluosog o ddehongli, ond mae cael yr holl fanylion i weithio’n ymarfer addysgiadol.

Ymarfer 5.51: Datblygwch weithrediad elfennol o Scheme yn C (neu ryw iaith lefel isel arall o’ch dewis) drwy drosi gwerthusydd rheolaeth eglur 5.4 i C. Er mwyn rhedeg y cod hwn, bydd angen hefyd ddarparu rheolweithiau dyrannu storfa priodol a chymorth arall adeg rhedeg.

Ymarfer 5.52: Fel cyferbyniad i Ymarfer 5.51, addaswch y crynhoydd fel ei fod yn crynhoi gweithdrefnau Scheme yn ddilyniannau o gyfarwyddiadau C. Crynhowch werthusydd metagylchol 4.1 i gynhyrchu dehonglydd Scheme wedi’i ysgrifennu yn C.

Troednodiadau

³¹⁸ Datganiad damcaniaethol yw hwn. Nid ydym yn honni bod llwybrau data’r gwerthusydd yn set arbennig o gyfleus nac effeithlon o lwybrau data ar gyfer cyfrifiadur at ddibenion cyffredinol. Er enghraifft, nid ydynt yn dda iawn ar gyfer gweithredu cyfrifiadau pwynt arnawf â pherfformiad uchel na chyfrifiadau sy’n trin fectorau didau’n ddwys.

³¹⁹ Mewn gwirionedd, gall y peiriant sy’n rhedeg cod wedi’i grynhoi fod yn symlach na’r peiriant dehongli, oherwydd na fyddwn yn defnyddio’r cofrestri exp ac unev. Defnyddiodd y dehonglydd y rhain i ddal darnau o fynegiadau heb eu gwerthuso. Gyda’r crynhoydd, fodd bynnag, mae’r mynegiadau hyn yn cael eu hymgorffori yn y cod wedi’i grynhoi y bydd y peiriant cofrestri yn ei redeg. Am yr un rheswm, nid oes angen y gweithrediadau peiriant sy’n ymdrin â chystrawen mynegiadau. Ond bydd cod wedi’i grynhoi’n defnyddio ychydig o weithrediadau peiriant ychwanegol (i gynrychioli gwrthrychau gweithdrefnau wedi’u crynhoi) nad oeddent yn ymddangos ym mheiriant y gwerthusydd rheolaeth eglur.

³²⁰ Sylwch, fodd bynnag, mai rhaglen Scheme yw ein crynhoydd, a’r gweithdrefnau cystrawen y mae’n eu defnyddio i drin mynegiadau yw’r gweithdrefnau Scheme eu hunain a ddefnyddir gyda’r gwerthusydd metagylchol. Ar gyfer y gwerthusydd rheolaeth eglur, mewn cyferbyniad, tybiasom fod gweithrediadau cystrawen cyfwerth ar gael fel gweithrediadau ar gyfer y peiriant cofrestri. (Wrth gwrs, pan efelychasom y peiriant cofrestri yn Scheme, defnyddiasom y gweithdrefnau Scheme eu hunain yn ein hefelychiad o’r peiriant cofrestri.)

³²¹ Mae’r weithdrefn hon yn defnyddio nodwedd Lisp o’r enw dyfynnod ôl (neu ffugddyfynnu) sy’n hwylus ar gyfer adeiladu rhestrau. Mae rhoi symbol dyfynnod ôl o flaen rhestr yn debyg iawn i’w dyfynnu, heblaw bod unrhyw beth yn y rhestr a nodir â choma yn cael ei werthuso.

Er enghraifft, os mai’r symbol branch25 yw gwerth linkage, yna mae’r mynegiad

`((goto (label ,linkage)))

yn gwerthuso i’r rhestr

((goto (label branch25)))

Yn yr un modd, os mai’r rhestr (a b c) yw gwerth x, yna mae

`(1 2 ,(car x))

yn gwerthuso i’r rhestr

(1 2 a)

³²² Ni allwn ddefnyddio’r labeli true-branch, false-branch, ac after-if yn unig fel y dangoswyd uchod, oherwydd y gallai fod mwy nag un if yn y rhaglen. Mae’r crynhoydd yn defnyddio’r weithdrefn make-label i gynhyrchu labeli. Mae Make-label yn cymryd symbol yn arg ac yn dychwelyd symbol newydd sy’n dechrau â’r symbol a roddwyd. Er enghraifft, byddai galwadau olynol i (make-label 'a) yn dychwelyd a1, a2, ac ati. Gellir gweithredu Make-label yn debyg i gynhyrchu enwau newidynnau unigryw yn yr iaith ymholi, fel a ganlyn:

(define label-counter 0)

(define (new-label-number)
  (set! label-counter (+ 1 label-counter))
  label-counter)

(define (make-label name)
  (string->symbol
   (string-append 
    (symbol->string name)
    (number->string (new-label-number)))))

³²³ Mae angen gweithrediadau peiriant i weithredu strwythur data ar gyfer cynrychioli gweithdrefnau wedi’u crynhoi, sy’n gyfatebol i’r strwythur ar gyfer gweithdrefnau cyfansawdd a ddisgrifiwyd yn 4.1.3:

(define (make-compiled-procedure entry env)
  (list 'compiled-procedure entry env))
(define (compiled-procedure? proc)
  (tagged-list? proc 'compiled-procedure))
(define (compiled-procedure-entry c-proc) 
  (cadr c-proc))
(define (compiled-procedure-env c-proc)
  (caddr c-proc))

³²⁴ Mewn gwirionedd, nodwn wall pan nad val yw’r targed ac mai return yw’r cysylltiad, gan mai’r unig le y gofynnwn am gysylltiadau return yw wrth grynhoi gweithdrefnau, a’n confensiwn yw bod gweithdrefnau’n dychwelyd eu gwerthoedd yn val.

³²⁵ Gallai peri i grynhoydd gynhyrchu cod â dychweliad cynffon ymddangos yn syniad syml. Ond nid yw’r rhan fwyaf o grynhowyr ar gyfer ieithoedd cyffredin, gan gynnwys C a Pascal, yn gwneud hyn, ac felly ni all yr ieithoedd hyn gynrychioli prosesau iteru drwy alwadau gweithdrefn yn unig. Yr anhawster â dychweliad cynffon yn yr ieithoedd hyn yw bod eu gweithrediadau’n defnyddio’r pentwr i storio argiau gweithdrefnau a newidynnau lleol yn ogystal â chyfeiriadau dychwelyd. Mae’r gweithrediadau Scheme a ddisgrifir yn y llyfr hwn yn storio argiau a newidynnau mewn cof sydd i’w adfer drwy gasglu sbwriel. Y rheswm dros ddefnyddio’r pentwr ar gyfer newidynnau ac argiau yw ei fod yn osgoi’r angen am gasglu sbwriel mewn ieithoedd na fyddai arnynt ei angen fel arall, a chredir yn gyffredinol ei fod yn fwy effeithlon. Gall crynhowyr Lisp soffistigedig, mewn gwirionedd, ddefnyddio’r pentwr ar gyfer argiau heb ddinistrio dychweliad cynffon. (Gweler Hanson 1990 am ddisgrifiad.) Ceir hefyd rywfaint o ddadl ynghylch a yw dyrannu ar y pentwr mewn gwirionedd yn fwy effeithlon na chasglu sbwriel yn y lle cyntaf, ond ymddengys fod y manylion yn dibynnu ar bwyntiau cynnil o bensaernïaeth gyfrifiadurol. (Gweler Appel 1987 ac Miller and Rozas 1994 am safbwyntiau gwrthwynebol ar y mater hwn.)

³²⁶ Mae’r newidyn all-regs wedi’i rwymo i restr enwau’r holl gofrestri:

(define all-regs '(env proc val argl continue))

³²⁷ Sylwch fod preserving yn galw append â thri arg. Er bod y diffiniad o append a ddangosir yn y llyfr hwn yn derbyn dau arg yn unig, mae Scheme fel safon yn darparu gweithdrefn append sy’n cymryd nifer mympwyol o argiau.

³²⁸ Rydym wedi defnyddio’r un symbol + yma i ddynodi’r weithdrefn yn yr iaith ffynhonnell a’r gweithrediad peiriant. Yn gyffredinol, ni fydd cyfatebiaeth un-i-un rhwng gweithdrefnau cyntefig yr iaith ffynhonnell a gweithrediadau cyntefig y peiriant.

³²⁹ Yn gyffredinol, mae gwneud y gweithdrefnau cyntefig yn eiriau neilltuedig yn syniad gwael, gan na all defnyddiwr wedyn ailrwymo’r enwau hyn i weithdrefnau gwahanol. Ymhellach, os ychwanegwn eiriau neilltuedig at grynhoydd sy’n cael ei ddefnyddio, bydd rhaglenni presennol sy’n diffinio gweithdrefnau â’r enwau hyn yn rhoi’r gorau i weithio. Gweler Ymarfer 5.44 am syniadau ynghylch sut i osgoi’r broblem hon.

³³⁰ Nid yw hyn yn wir os caniateir diffiniadau mewnol, oni bai ein bod yn eu sganio allan. Gweler Ymarfer 5.43.

³³¹ Dyma’r addasiad i chwilio am newidynnau sydd ei angen os gweithredwn y dull sganio i ddileu diffiniadau mewnol (Ymarfer 5.43). Bydd angen dileu’r diffiniadau hyn er mwyn i gyfeirio geiriadurol weithio.

³³² Ni ellir defnyddio cyfeiriadau geiriadurol i gyrchu newidynnau yn yr amgylchedd byd-eang, oherwydd y gellir diffinio ac ailddiffinio’r enwau hyn yn rhyngweithiol ar unrhyw adeg. Gyda’r diffiniadau mewnol wedi’u sganio allan, fel yn Ymarfer 5.43, yr unig ddiffiniadau y mae’r crynhoydd yn eu gweld yw’r rhai ar y lefel uchaf, sy’n gweithredu ar yr amgylchedd byd-eang. Nid yw crynhoi diffiniad yn peri i’r enw a ddiffiniwyd gael ei roi yn yr amgylchedd amser crynhoi.

³³³ Wrth gwrs, mae gweithdrefnau wedi’u crynhoi yn ogystal â gweithdrefnau wedi’u dehongli yn gyfansawdd (nid yn gyntefig). Er mwyn bod yn gydnaws â’r derminoleg a ddefnyddir yn y gwerthusydd rheolaeth eglur, yn yr adran hon defnyddiwn “cyfansawdd” i olygu wedi’i ddehongli (yn hytrach na wedi’i grynhoi).

³³⁴ Gan fod y peiriant gwerthuso bellach yn dechrau ag branch, rhaid inni bob amser gychwyn y gofrestr flag cyn cychwyn y peiriant gwerthuso. I gychwyn y peiriant yn ei ddolen darllen-gwerthuso-argraffu arferol, gallem ddefnyddio

(define (start-eceval)
  (set! the-global-environment
        (setup-environment))
  (set-register-contents! eceval 'flag false)
  (start eceval))

³³⁵ Gan fod gweithdrefn wedi’i chrynhoi’n wrthrych y gall y system geisio ei argraffu, addaswn hefyd weithrediad argraffu’r system user-print (o 4.1.4) fel na fydd yn ceisio argraffu cydrannau gweithdrefn wedi’i chrynhoi:

(define (user-print object)
  (cond ((compound-procedure? object)
         (display 
          (list 'compound-procedure
                (procedure-parameters object)
                (procedure-body object)
                '<procedure-env>)))
        ((compiled-procedure? object)
         (display '<compiled-procedure>))
        (else (display object))))

³³⁶ Gallwn wneud yn well fyth drwy ymestyn y crynhoydd i ganiatáu i god wedi’i grynhoi alw gweithdrefnau wedi’u dehongli. Gweler Ymarfer 5.47.

³³⁷ Yn annibynnol ar y strategaeth weithredu, mae cost ychwanegol sylweddol os mynnwn fod gwallau a geir wrth weithredu rhaglen defnyddiwr yn cael eu canfod a’u nodi, yn hytrach na’u gadael i ladd y system neu gynhyrchu atebion anghywir. Er enghraifft, gellir canfod cyfeiriad y tu allan i derfynau arae drwy wirio dilysrwydd y cyfeiriad cyn ei gyflawni. Fodd bynnag, gall cost ychwanegol gwirio fod sawl gwaith cost cyfeirio at yr arae ei hun, a dylai rhaglennydd bwyso cyflymder yn erbyn diogelwch wrth benderfynu a yw prawf o’r fath yn ddymunol. Dylai crynhoydd da allu cynhyrchu cod â phrofion o’r fath, dylai osgoi profion diangen, a dylai ganiatáu i raglenwyr reoli maint a math y gwirio gwallau yn y cod wedi’i grynhoi.

Prin fod crynhowyr ar gyfer ieithoedd poblogaidd, megis C a C++, yn rhoi unrhyw weithrediadau gwirio gwallau mewn cod sy’n rhedeg, er mwyn gwneud i bethau redeg mor gyflym â phosibl. O ganlyniad, cyfrifoldeb y rhaglenwyr yw darparu gwirio gwallau’n benodol. Yn anffodus, mae pobl yn aml yn esgeuluso gwneud hyn, hyd yn oed mewn cymwysiadau critigol lle nad yw cyflymder yn gyfyngiad. Mae eu rhaglenni’n byw bywydau cyflym a pheryglus. Er enghraifft, manteisiodd y “Worm” drwg-enwog a barlysodd y Rhyngrwyd yn 1988 ar fethiant system weithredu UNIX(tm) i wirio a oedd y byffer mewnbwn wedi gorlifo yn y daemon finger. (Gweler Spafford 1989.)

³³⁸ Wrth gwrs, gyda strategaeth dehongli neu strategaeth crynhoi, rhaid inni hefyd weithredu ar gyfer y peiriant newydd ddyrannu storfa, mewnbwn ac allbwn, a’r holl weithrediadau amrywiol a gymerasom yn rhai “cyntefig” yn ein trafodaeth o’r gwerthusydd a’r crynhoydd. Un strategaeth ar gyfer lleihau’r gwaith yma yw ysgrifennu cynifer o’r gweithrediadau hyn â phosibl yn Lisp ac yna eu crynhoi ar gyfer y peiriant newydd. Yn y pen draw, mae popeth yn lleihau i gnewyllyn bach (megis casglu sbwriel a’r mecanwaith ar gyfer cymhwyso gweithrediadau cyntefig y peiriant ei hun) a godir â llaw ar gyfer y peiriant newydd.

³³⁹ Mae’r strategaeth hon yn arwain at brofion difyr o gywirdeb y crynhoydd, megis gwirio a yw canlyniad crynhoi rhaglen ar y peiriant newydd, gan ddefnyddio’r crynhoydd wedi’i grynhoi, yn union yr un fath â chanlyniad crynhoi’r rhaglen ar y system Lisp wreiddiol. Mae olrhain ffynhonnell gwahaniaethau’n hwyl ond yn aml yn rhwystredig, oherwydd bod y canlyniadau’n hynod sensitif i fanylion bychain iawn.