5.4 Y Gwerthusydd Rheolaeth Eglur

Yn 5.1 gwelsom sut i drawsffurfio rhaglenni Scheme syml yn ddisgrifiadau o beiriannau cofrestri. Nawr byddwn yn cyflawni'r trawsffurfiad hwn ar raglen fwy cymhleth, sef gwerthusydd metagylchol 4.1.1–4.1.4, sy'n dangos sut y gellir disgrifio ymddygiad dehonglydd Scheme yn nhermau'r gweithdrefnau eval ac apply. Mae'r gwerthusydd rheolaeth eglur a ddatblygwn yn yr adran hon yn dangos sut y gellir disgrifio'r mecanweithiau sylfaenol ar gyfer galw gweithdrefnau a throsglwyddo argiau, a ddefnyddir yn y broses werthuso, yn nhermau gweithrediadau ar gofrestri a phentyrrau. Yn ogystal, gall y gwerthusydd rheolaeth eglur wasanaethu fel gweithrediad o ddehonglydd Scheme, wedi'i ysgrifennu mewn iaith sy'n debyg iawn i iaith beiriant frodorol cyfrifiaduron confensiynol. Gellir gweithredu'r gwerthusydd drwy efelychydd peiriannau cofrestri 5.2. Fel arall, gellir ei ddefnyddio fel man cychwyn ar gyfer adeiladu gweithrediad iaith beiriant o werthusydd Scheme, neu hyd yn oed beiriant pwrpasol ar gyfer gwerthuso mynegiadau Scheme. Mae Ffigur 5.16 yn dangos gweithrediad caledwedd o'r fath: sglodyn silicon sy'n gweithredu fel gwerthusydd ar gyfer Scheme. Dechreuodd dylunwyr y sglodyn â manylebau llwybr data a rheolydd peiriant cofrestri tebyg i'r gwerthusydd a ddisgrifir yn yr adran hon, a defnyddio rhaglenni awtomeiddio dylunio i adeiladu cynllun y gylched integredig.³⁰⁴

Cofrestri a gweithrediadau

Wrth ddylunio'r gwerthusydd rheolaeth eglur, rhaid inni bennu'r gweithrediadau sydd i'w defnyddio yn ein peiriant cofrestri. Disgrifiasom y gwerthusydd metagylchol yn nhermau cystrawen haniaethol, gan ddefnyddio gweithdrefnau megis quoted? ac make-procedure. Wrth weithredu'r peiriant cofrestri, gallem ehangu'r gweithdrefnau hyn yn ddilyniannau o weithrediadau cof elfennol ar strwythur rhestrau, a gweithredu'r gweithrediadau hyn ar ein peiriant cofrestri. Fodd bynnag, byddai hyn yn gwneud ein gwerthusydd yn hir iawn, gan guddio'r strwythur sylfaenol â manylion. I wneud y cyflwyniad yn glir, byddwn yn cynnwys yn weithrediadau cyntefig y peiriant cofrestri y gweithdrefnau cystrawen a roddwyd yn 4.1.2 a'r gweithdrefnau ar gyfer cynrychioli amgylcheddau a data eraill adeg rhedeg a roddwyd yn adrannau 4.1.3 a 4.1.4. Er mwyn pennu'n llwyr werthusydd y gellid ei raglennu mewn iaith beiriant lefel isel neu ei weithredu mewn caledwedd, byddem yn rhoi gweithrediadau mwy elfennol yn lle'r rhain, gan ddefnyddio'r gweithrediad strwythur rhestrau a ddisgrifiasom yn 5.3.

Mae ein peiriant cofrestri gwerthusydd Scheme yn cynnwys pentwr a saith cofrestr: exp, env, val, continue, proc, argl, ac unev. Defnyddir Exp i ddal y mynegiad sydd i'w werthuso, ac mae env yn cynnwys yr amgylchedd lle mae'r gwerthuso i'w gyflawni. Ar ddiwedd gwerthusiad, mae val yn cynnwys y gwerth a gafwyd drwy werthuso'r mynegiad yn yr amgylchedd dynodedig. Defnyddir y gofrestr continue i weithredu dychweliad, fel yr eglurwyd yn 5.1.4. (Mae angen i'r gwerthusydd ei alw ei hun yn ddychweliadol, gan fod gwerthuso mynegiad yn gofyn am werthuso ei isfynegiadau.) Defnyddir y cofrestri proc, argl, ac unev wrth werthuso cyfuniadau.

Ni fyddwn yn darparu diagram llwybr data i ddangos sut mae cofrestri a gweithrediadau'r gwerthusydd wedi'u cysylltu, nac yn rhoi'r rhestr gyflawn o weithrediadau peiriant. Mae'r rhain ymhlyg yn rheolydd y gwerthusydd, a gyflwynir yn fanwl.

5.4.1Craidd y Gwerthusydd Rheolaeth Eglur

Elfen ganolog y gwerthusydd yw'r dilyniant o gyfarwyddiadau sy'n dechrau yn eval-dispatch. Mae hyn yn cyfateb i weithdrefn eval y gwerthusydd metagylchol a ddisgrifiwyd yn 4.1.1. Pan fydd y rheolydd yn dechrau yn eval-dispatch, mae'n gwerthuso'r mynegiad a bennir gan exp yn yr amgylchedd a bennir gan env. Pan fydd y gwerthuso wedi'i gwblhau, bydd y rheolydd yn mynd at y pwynt mynediad sydd wedi'i storio yn continue, a bydd y gofrestr val yn dal gwerth y mynegiad. Fel gyda'r eval metagylchol, mae strwythur eval-dispatch yn ddadansoddiad fesul achos o fath cystrawennol y mynegiad sydd i'w werthuso.³⁰⁵

eval-dispatch
  (test (op self-evaluating?) (reg exp))
  (branch (label ev-self-eval))
  (test (op variable?) (reg exp))
  (branch (label ev-variable))
  (test (op quoted?) (reg exp))
  (branch (label ev-quoted))
  (test (op assignment?) (reg exp))
  (branch (label ev-assignment))
  (test (op definition?) (reg exp))
  (branch (label ev-definition))
  (test (op if?) (reg exp))
  (branch (label ev-if))
  (test (op lambda?) (reg exp))
  (branch (label ev-lambda))
  (test (op begin?) (reg exp))
  (branch (label ev-begin))
  (test (op application?) (reg exp))
  (branch (label ev-application))
  (goto (label unknown-expression-type))

Gwerthuso mynegiadau syml

Nid oes gan rifau a llinynnau (sy'n hunanwerthusol), newidynnau, dyfyniadau, a mynegiadau lambda isfynegiadau i'w gwerthuso. Ar gyfer y rhain, mae'r gwerthusydd yn rhoi'r gwerth cywir yn y gofrestr val ac yn parhau i weithredu yn y pwynt mynediad a bennir gan continue. Gwerthusir mynegiadau syml gan y cod rheolydd canlynol:

ev-self-eval
  (assign val (reg exp))
  (goto (reg continue))
ev-variable
  (assign val
          (op lookup-variable-value)
          (reg exp)
          (reg env))
  (goto (reg continue))
ev-quoted
  (assign val
          (op text-of-quotation)
          (reg exp))
  (goto (reg continue))
ev-lambda
  (assign unev
          (op lambda-parameters)
          (reg exp))
  (assign exp 
          (op lambda-body)
          (reg exp))
  (assign val 
          (op make-procedure)
          (reg unev)
          (reg exp)
          (reg env))
  (goto (reg continue))

Sylwch sut mae ev-lambda yn defnyddio'r cofrestri unev ac exp i ddal paramedrau a chorff y mynegiad lambda fel y gellir eu trosglwyddo i'r gweithrediad make-procedure, ynghyd â'r amgylchedd yn env.

Gwerthuso cymwysiadau gweithdrefn

Pennir cymhwysiad gweithdrefn gan gyfuniad sy'n cynnwys gweithredydd ac operandau. Mae'r gweithredydd yn isfynegiad y mae ei werth yn weithdrefn, ac mae'r operandau yn isfynegiadau y mae eu gwerthoedd yn argiau y dylid cymhwyso'r weithdrefn iddynt. Mae'r eval metagylchol yn ymdrin â chymwysiadau drwy ei alw ei hun yn ddychweliadol i werthuso pob elfen o'r cyfuniad, ac yna'n trosglwyddo'r canlyniadau i apply, sy'n cyflawni'r cymhwysiad gweithdrefn ei hun. Mae'r gwerthusydd rheolaeth eglur yn gwneud yr un peth; gweithredir y galwadau dychweliadol hyn gan gyfarwyddiadau goto, ynghyd â defnyddio'r pentwr i gadw cofrestri a adferir ar ôl i'r alwad ddychweliadol ddychwelyd. Cyn pob galwad, byddwn yn ofalus i adnabod pa gofrestri y mae'n rhaid eu cadw (oherwydd y bydd angen eu gwerthoedd yn ddiweddarach).³⁰⁶

Dechreuwn werthuso cymhwysiad drwy werthuso'r gweithredydd i gynhyrchu gweithdrefn, a gymhwysir yn ddiweddarach i'r operandau wedi'u gwerthuso. I werthuso'r gweithredydd, symudwn ef i'r gofrestr exp ac awn at eval-dispatch. Mae'r amgylchedd yn y gofrestr env eisoes yr un cywir ar gyfer gwerthuso'r gweithredydd. Fodd bynnag, cadwn env oherwydd y bydd ei angen yn ddiweddarach i werthuso'r operandau. Rydym hefyd yn echdynnu'r operandau i unev ac yn cadw hwn ar y pentwr. Gosodwn continue fel y bydd eval-dispatch yn ailddechrau yn ev-appl-did-operator ar ôl gwerthuso'r gweithredydd. Yn gyntaf, fodd bynnag, cadwn hen werth continue, sy'n dweud wrth y rheolydd ble i barhau ar ôl y cymhwysiad.

ev-application
  (save continue)
  (save env)
  (assign unev (op operands) (reg exp))
  (save unev)
  (assign exp (op operator) (reg exp))
  (assign
   continue (label ev-appl-did-operator))
  (goto (label eval-dispatch))

Wrth ddychwelyd o werthuso isfynegiad y gweithredydd, awn ymlaen i werthuso operandau'r cyfuniad ac i gronni'r argiau a geir mewn rhestr, a gedwir yn argl. Yn gyntaf, adferwn yr operandau heb eu gwerthuso a'r amgylchedd. Cychwynnwn argl yn rhestr wag. Yna aseiniwn i'r gofrestr proc y weithdrefn a gynhyrchwyd drwy werthuso'r gweithredydd. Os nad oes operandau, awn yn uniongyrchol at apply-dispatch. Fel arall, cadwn proc ar y pentwr a dechreuwn y ddolen gwerthuso argiau:³⁰⁷

ev-appl-did-operator
  (restore unev)             ; the operands
  (restore env)
  (assign argl (op empty-arglist))
  (assign proc (reg val))    ; the operator
  (test (op no-operands?) (reg unev))
  (branch (label apply-dispatch))
  (save proc)

Mae pob cylch o'r ddolen gwerthuso argiau yn gwerthuso operand o'r rhestr yn unev ac yn cronni'r canlyniad i argl. I werthuso operand, rhoddwn ef yn y gofrestr exp ac awn at eval-dispatch, ar ôl gosod continue fel y bydd y gweithredu'n ailddechrau gyda'r cam cronni argiau. Ond yn gyntaf cadwn yr argiau a gronnwyd hyd yma (a gedwir yn argl), yr amgylchedd (a gedwir yn env), a'r operandau sy'n weddill i'w gwerthuso (a gedwir yn unev). Gwneir achos arbennig o werthuso'r operand olaf, yr ymdrinnir ag ef yn ev-appl-last-arg.

ev-appl-operand-loop
  (save argl)
  (assign exp
          (op first-operand)
          (reg unev))
  (test (op last-operand?) (reg unev))
  (branch (label ev-appl-last-arg))
  (save env)
  (save unev)
  (assign continue 
          (label ev-appl-accumulate-arg))
  (goto (label eval-dispatch))

Pan fydd operand wedi'i werthuso, cronnir y gwerth i'r rhestr a gedwir yn argl. Yna tynnir yr operand o'r rhestr o operandau heb eu gwerthuso yn unev, a pharheir i werthuso'r argiau.

ev-appl-accumulate-arg
  (restore unev)
  (restore env)
  (restore argl)
  (assign argl 
          (op adjoin-arg)
          (reg val)
          (reg argl))
  (assign unev
          (op rest-operands)
          (reg unev))
  (goto (label ev-appl-operand-loop))

Ymdrinnir â gwerthuso'r arg olaf yn wahanol. Nid oes angen cadw'r amgylchedd na'r rhestr o operandau heb eu gwerthuso cyn mynd at eval-dispatch, gan na fydd eu hangen ar ôl gwerthuso'r operand olaf. Felly, dychwelwn o'r gwerthuso at bwynt mynediad arbennig ev-appl-accum-last-arg, sy'n adfer y rhestr argiau, yn cronni'r arg newydd, yn adfer y weithdrefn a gadwyd, ac yn mynd i gyflawni'r cymhwysiad.³⁰⁸

ev-appl-last-arg
  (assign continue 
          (label ev-appl-accum-last-arg))
  (goto (label eval-dispatch))
ev-appl-accum-last-arg
  (restore argl)
  (assign argl 
          (op adjoin-arg)
          (reg val)
          (reg argl))
  (restore proc)
  (goto (label apply-dispatch))

Mae manylion y ddolen gwerthuso argiau yn pennu'r drefn y mae'r dehonglydd yn gwerthuso operandau cyfuniad ynddi (e.e., o'r chwith i'r dde neu o'r dde i'r chwith—gweler Ymarfer 3.8). Nid y gwerthusydd metagylchol sy'n pennu'r drefn hon, gan ei fod yn etifeddu ei strwythur rheoli o'r Scheme sylfaenol y gweithredir ef ynddo.³⁰⁹ Oherwydd bod y detholwr first-operand (a ddefnyddir yn ev-appl-operand-loop i echdynnu operandau olynol o unev) wedi'i weithredu fel car a'r detholwr rest-operands wedi'i weithredu fel cdr, bydd y gwerthusydd rheolaeth eglur yn gwerthuso operandau cyfuniad yn y drefn o'r chwith i'r dde.

Cymhwyso gweithdrefn

Mae'r pwynt mynediad apply-dispatch yn cyfateb i weithdrefn apply y gwerthusydd metagylchol. Erbyn inni gyrraedd apply-dispatch, mae'r gofrestr proc yn cynnwys y weithdrefn i'w chymhwyso ac mae argl yn cynnwys y rhestr o argiau wedi'u gwerthuso y mae'n rhaid ei chymhwyso iddynt. Mae gwerth continue a gadwyd (a drosglwyddwyd yn wreiddiol i eval-dispatch ac a gadwyd yn ev-application), sy'n dweud ble i ddychwelyd gyda chanlyniad y cymhwysiad gweithdrefn, ar y pentwr. Pan fydd y cymhwysiad wedi'i gwblhau, mae'r rheolydd yn trosglwyddo at y pwynt mynediad a bennir gan yr continue a gadwyd, gyda chanlyniad y cymhwysiad yn val. Fel gyda'r apply metagylchol, mae dau achos i'w hystyried. Mae'r weithdrefn i'w chymhwyso naill ai'n gyntefig neu'n weithdrefn gyfansawdd.

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

Tybiwn fod pob gweithdrefn gyntefig wedi'i gweithredu i gael ei hargiau o argl a rhoi ei chanlyniad yn val. I bennu sut mae'r peiriant yn ymdrin â gweithdrefnau cyntefig, byddai'n rhaid darparu dilyniant o gyfarwyddiadau rheolydd i weithredu pob un a threfnu i primitive-apply ddethol y cyfarwyddiadau ar gyfer y weithdrefn gyntefig a adnabyddir gan gynnwys proc. Gan fod gennym ddiddordeb yn strwythur y broses werthuso yn hytrach nag ym manylion y gweithdrefnau cyntefig, byddwn yn hytrach yn defnyddio gweithrediad apply-primitive-procedure sy'n cymhwyso'r weithdrefn yn proc i'r argiau yn argl. Er mwyn efelychu'r gwerthusydd ag efelychydd 5.2, defnyddiwn y weithdrefn apply-primitive-procedure, sy'n galw ar y system Scheme sylfaenol i gyflawni'r cymhwysiad, yn union fel y gwnaethom ar gyfer y gwerthusydd metagylchol yn 4.1.4. Ar ôl cyfrifiannu gwerth y cymhwysiad cyntefig, adferwn continue ac awn at y pwynt mynediad dynodedig.

primitive-apply
  (assign val (op apply-primitive-procedure)
              (reg proc)
              (reg argl))
  (restore continue)
  (goto (reg continue))

I gymhwyso gweithdrefn gyfansawdd, awn ymlaen yn union fel gyda'r gwerthusydd metagylchol. Adeiladwn ffrâm sy'n rhwymo paramedrau'r weithdrefn i'r argiau, defnyddiwn y ffrâm hon i ymestyn yr amgylchedd a gludir gan y weithdrefn, a gwerthuswn yn yr amgylchedd estynedig hwn y dilyniant o fynegiadau sy'n ffurfio corff y weithdrefn. Mae Ev-sequence, a ddisgrifir isod yn 5.4.2, yn ymdrin â gwerthuso'r dilyniant.

compound-apply
  (assign unev 
          (op procedure-parameters)
          (reg proc))
  (assign env
          (op procedure-environment)
          (reg proc))
  (assign env
          (op extend-environment)
          (reg unev)
          (reg argl)
          (reg env))
  (assign unev
          (op procedure-body)
          (reg proc))
  (goto (label ev-sequence))

Compound-apply yw'r unig fan yn y dehonglydd lle aseinir gwerth newydd i'r gofrestr env erioed. Yn union fel yn y gwerthusydd metagylchol, adeiladir yr amgylchedd newydd o'r amgylchedd a gludir gan y weithdrefn, ynghyd â'r rhestr argiau a'r rhestr gyfatebol o newidynnau i'w rhwymo.

5.4.2Gwerthuso Dilyniannau a Dychweliad Cynffon

Mae'r rhan o'r gwerthusydd rheolaeth eglur yn ev-sequence yn cyfateb i weithdrefn eval-sequence y gwerthusydd metagylchol. Mae'n ymdrin â dilyniannau o fynegiadau mewn cyrff gweithdrefnau neu mewn mynegiadau begin penodol.

Gwerthusir mynegiadau begin penodol drwy roi'r dilyniant o fynegiadau sydd i'w gwerthuso yn unev, cadw continue ar y pentwr, a neidio at ev-sequence.

ev-begin
  (assign unev
          (op begin-actions)
          (reg exp))
  (save continue)
  (goto (label ev-sequence))

Ymdrinnir â'r dilyniannau ymhlyg mewn cyrff gweithdrefnau drwy neidio at ev-sequence o compound-apply, ac ar y pwynt hwnnw mae continue eisoes ar y pentwr, wedi'i gadw yn ev-application.

Mae'r pwyntiau mynediad yn ev-sequence ac ev-sequence-continue yn ffurfio dolen sy'n gwerthuso pob mynegiad mewn dilyniant yn ei dro. Cedwir y rhestr o fynegiadau heb eu gwerthuso yn unev. Cyn gwerthuso pob mynegiad, gwiriwn a oes mynegiadau ychwanegol i'w gwerthuso yn y dilyniant. Os oes, cadwn weddill y mynegiadau heb eu gwerthuso (a gedwir yn unev) a'r amgylchedd lle mae'n rhaid eu gwerthuso (a gedwir yn env), a galwn eval-dispatch i werthuso'r mynegiad. Adferir y ddwy gofrestr a gadwyd wrth ddychwelyd o'r gwerthusiad hwn, yn ev-sequence-continue.

Ymdrinnir â mynegiad olaf y dilyniant yn wahanol, yn y pwynt mynediad ev-sequence-last-exp. Gan nad oes rhagor o fynegiadau i'w gwerthuso ar ôl hwn, nid oes angen cadw unev nac env cyn mynd at eval-dispatch. Gwerth y dilyniant cyfan yw gwerth y mynegiad olaf, felly ar ôl gwerthuso'r mynegiad olaf nid oes dim ar ôl i'w wneud heblaw parhau yn y pwynt mynediad a gedwir ar y pentwr ar hyn o bryd (a gadwyd gan ev-application neu ev-begin.) Yn hytrach na gosod continue i drefnu i eval-dispatch ddychwelyd yma ac yna adfer continue o'r pentwr a pharhau yn y pwynt mynediad hwnnw, adferwn continue o'r pentwr cyn mynd at eval-dispatch, fel y bydd eval-dispatch yn parhau yn y pwynt mynediad hwnnw ar ôl gwerthuso'r mynegiad.

ev-sequence
  (assign exp (op first-exp) (reg unev))
  (test (op last-exp?) (reg unev))
  (branch (label ev-sequence-last-exp))
  (save unev)
  (save env)
  (assign continue
          (label ev-sequence-continue))
  (goto (label eval-dispatch))
ev-sequence-continue
  (restore env)
  (restore unev)
  (assign unev
          (op rest-exps)
          (reg unev))
  (goto (label ev-sequence))
ev-sequence-last-exp
  (restore continue)
  (goto (label eval-dispatch))

Dychweliad cynffon

Ym Mhennod 1 dywedasom fod y broses a ddisgrifir gan weithdrefn megis

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)))

yn broses iteru. Er bod y weithdrefn yn ddychweliadol o ran cystrawen (wedi'i diffinio yn nhermau ei hun), nid yw'n angenrheidiol o safbwynt rhesymeg i werthusydd gadw gwybodaeth wrth symud o un alwad i sqrt-iter i'r nesaf.³¹⁰ Gelwir gwerthusydd sy'n gallu gweithredu gweithdrefn megis sqrt-iter heb ofyn am fwy a mwy o le storio wrth i'r weithdrefn barhau i'w galw ei hun yn werthusydd dychweliadol yn y gynffon. Nid yw gweithrediad metagylchol y gwerthusydd ym Mhennod 4 yn pennu a yw'r gwerthusydd yn ddychweliadol yn y gynffon, oherwydd bod y gwerthusydd hwnnw'n etifeddu ei fecanwaith cadw cyflwr o'r Scheme sylfaenol. Gyda'r gwerthusydd rheolaeth eglur, fodd bynnag, gallwn olrhain y broses werthuso i weld pryd mae galwadau gweithdrefn yn achosi croniad net o wybodaeth ar y pentwr.

Mae ein gwerthusydd yn ddychweliadol yn y gynffon, oherwydd er mwyn gwerthuso mynegiad olaf dilyniant trosglwyddwn yn uniongyrchol at eval-dispatch heb gadw unrhyw wybodaeth ar y pentwr. Felly, ni fydd gwerthuso mynegiad olaf dilyniant—hyd yn oed os yw'n alwad gweithdrefn (fel yn sqrt-iter, lle mae'r mynegiad if, sef y mynegiad olaf yng nghorff y weithdrefn, yn lleihau i alwad i sqrt-iter)—yn achosi i unrhyw wybodaeth gronni ar y pentwr.³¹¹

Pe na baem yn meddwl manteisio ar y ffaith nad oedd angen cadw gwybodaeth yn yr achos hwn, gallem fod wedi gweithredu eval-sequence drwy drin pob mynegiad mewn dilyniant yn yr un modd—cadw'r cofrestri, gwerthuso'r mynegiad, dychwelyd i adfer y cofrestri, ac ailadrodd hyn nes bod yr holl fynegiadau wedi'u gwerthuso:³¹²

ev-sequence
  (test (op no-more-exps?) (reg unev))
  (branch (label ev-sequence-end))
  (assign exp (op first-exp) (reg unev))
  (save unev)
  (save env)
  (assign continue
          (label ev-sequence-continue))
  (goto (label eval-dispatch))
ev-sequence-continue
  (restore env)
  (restore unev)
  (assign unev (op rest-exps) (reg unev))
  (goto (label ev-sequence))
ev-sequence-end
  (restore continue)
  (goto (reg continue))

Gall hyn ymddangos yn newid bach i'n cod blaenorol ar gyfer gwerthuso dilyniant: yr unig wahaniaeth yw ein bod yn mynd drwy'r cylch cadw ac adfer ar gyfer mynegiad olaf dilyniant yn ogystal â'r lleill. Bydd y dehonglydd yn dal i roi'r un gwerth ar gyfer unrhyw fynegiad. Ond mae'r newid hwn yn angheuol i'r gweithrediad dychweliadol yn y gynffon, oherwydd rhaid inni bellach ddychwelyd ar ôl gwerthuso mynegiad olaf dilyniant er mwyn dadwneud y cadw cofrestri (diwerth). Bydd y gwerthoedd ychwanegol hyn a gedwir yn cronni yn ystod nyth o alwadau gweithdrefn. O ganlyniad, bydd prosesau megis sqrt-iter yn gofyn am ofod sy'n gyfrannol â nifer yr iteriadau yn hytrach na gofod cyson. Gall y gwahaniaeth hwn fod yn sylweddol. Er enghraifft, gyda dychweliad cynffon, gellir mynegi dolen anfeidraidd gan ddefnyddio'r mecanwaith galw gweithdrefn yn unig:

(define (count n)
  (newline)
  (display n)
  (count (+ n 1)))

Heb ddychweliad cynffon, byddai gweithdrefn o'r fath yn rhedeg allan o ofod pentwr yn y pen draw, a byddai mynegi iteriad gwirioneddol yn gofyn am ryw fecanwaith rheoli heblaw galw gweithdrefn.

5.4.3Mynegiadau Amodol, Aseiniadau, a Diffiniadau

Fel gyda'r gwerthusydd metagylchol, ymdrinnir â ffurfiau arbennig drwy werthuso darnau o'r mynegiad yn ddetholus. Ar gyfer mynegiad if, rhaid gwerthuso'r traethiad a phenderfynu, ar sail gwerth y traethiad, a ddylid gwerthuso'r mynegiad canlynol neu'r mynegiad amgen.

Cyn gwerthuso'r traethiad, cadwn y mynegiad if ei hun fel y gallwn echdynnu'r mynegiad canlynol neu'r mynegiad amgen yn ddiweddarach. Cadwn hefyd yr amgylchedd, y bydd ei angen yn ddiweddarach i werthuso'r mynegiad canlynol neu'r mynegiad amgen, a chadwn continue, y bydd ei angen yn ddiweddarach i ddychwelyd at werthuso'r mynegiad sy'n aros am werth yr if.

ev-if
  (save exp)   ; save expression for later
  (save env)
  (save continue)
  (assign continue (label ev-if-decide))
  (assign exp (op if-predicate) (reg exp))
  ; evaluate the predicate:
  (goto (label eval-dispatch))  

Pan ddychwelwn o werthuso'r traethiad, profwn a oedd yn wir neu'n anwir ac, yn dibynnu ar y canlyniad, rhoddwn naill ai'r mynegiad canlynol neu'r mynegiad amgen yn exp cyn mynd at eval-dispatch. Sylwch fod adfer env ac continue yma yn paratoi eval-dispatch i gael yr amgylchedd cywir ac i barhau yn y man cywir i dderbyn gwerth y mynegiad if.

ev-if-decide
  (restore continue)
  (restore env)
  (restore exp)
  (test (op true?) (reg val))
  (branch (label ev-if-consequent))
ev-if-alternative
  (assign exp (op if-alternative) (reg exp))
  (goto (label eval-dispatch))
ev-if-consequent
  (assign exp (op if-consequent) (reg exp))
  (goto (label eval-dispatch))

Aseiniadau a diffiniadau

Ymdrinnir ag aseiniadau gan ev-assignment, a gyrhaeddir o eval-dispatch gyda'r mynegiad aseiniad yn exp. Mae'r cod yn ev-assignment yn gwerthuso rhan werth y mynegiad yn gyntaf ac yna'n gosod y gwerth newydd yn yr amgylchedd. Tybir bod Set-variable-value! ar gael fel gweithrediad peiriant.

ev-assignment
  (assign unev 
          (op assignment-variable)
          (reg exp))
  (save unev)   ; save variable for later
  (assign exp
          (op assignment-value)
          (reg exp))
  (save env)
  (save continue)
  (assign continue
          (label ev-assignment-1))
  ; evaluate the assignment value:
  (goto (label eval-dispatch))  
ev-assignment-1
  (restore continue)
  (restore env)
  (restore unev)
  (perform (op set-variable-value!)
           (reg unev)
           (reg val)
           (reg env))
  (assign val
          (const ok))
  (goto (reg continue))

Ymdrinnir â diffiniadau mewn ffordd debyg:

ev-definition
  (assign unev 
          (op definition-variable)
          (reg exp))
  (save unev)   ; save variable for later
  (assign exp 
          (op definition-value)
          (reg exp))
  (save env)
  (save continue)
  (assign continue (label ev-definition-1))
  ; evaluate the definition value:
  (goto (label eval-dispatch))  
ev-definition-1
  (restore continue)
  (restore env)
  (restore unev)
  (perform (op define-variable!)
           (reg unev)
           (reg val)
           (reg env))
  (assign val (const ok))
  (goto (reg continue))

Ymarfer 5.23: Ymestynnwch y gwerthusydd i ymdrin â mynegiadau deilliedig megis cond, let, ac ati (4.1.2). Cewch “dwyllo” a thybio bod y trawsffurfwyr cystrawen megis cond->if ar gael fel gweithrediadau peiriant.³¹³

Ymarfer 5.24: Gweithredwch cond fel ffurf arbennig sylfaenol newydd heb ei lleihau i if. Bydd yn rhaid adeiladu dolen sy'n profi traethiadau cymalau cond olynol nes canfod un sy'n wir, ac yna defnyddio ev-sequence i werthuso gweithredoedd y cymal.

Ymarfer 5.25: Addaswch y gwerthusydd fel ei fod yn defnyddio gwerthuso yn y drefn arferol, yn seiliedig ar werthusydd diog 4.2.

5.4.4Rhedeg y Gwerthusydd

Gyda gweithrediad y gwerthusydd rheolaeth eglur, deuwn at ddiwedd datblygiad a ddechreuodd ym Mhennod 1, lle rydym wedi archwilio modelau mwy a mwy manwl o'r broses werthuso. Dechreuasom â'r model amnewid cymharol anffurfiol, ac yna'i ymestyn ym Mhennod 3 i'r model amgylchedd, a'n galluogodd i ymdrin â chyflwr a newid. Yng ngwerthusydd metagylchol Pennod 4, defnyddiasom Scheme ei hun fel iaith i wneud strwythur yr amgylchedd a adeiladir wrth werthuso mynegiad yn fwy eglur. Nawr, gyda pheiriannau cofrestri, rydym wedi edrych yn fanwl ar fecanweithiau'r gwerthusydd ar gyfer rheoli storfa, trosglwyddo argiau, a rheolaeth. Ar bob lefel newydd o ddisgrifio, bu'n rhaid inni godi materion a datrys amwyseddau nad oeddent yn amlwg yn y driniaeth flaenorol, lai manwl, o werthuso. I ddeall ymddygiad y gwerthusydd rheolaeth eglur, gallwn ei efelychu a monitro ei berfformiad.

Byddwn yn gosod dolen yrru yn ein peiriant gwerthusydd. Mae hon yn cyflawni rôl gweithdrefn driver-loop 4.1.4. Bydd y gwerthusydd yn argraffu anogwr, yn darllen mynegiad, yn gwerthuso'r mynegiad drwy fynd at eval-dispatch, ac yn argraffu'r canlyniad dro ar ôl tro. Mae'r cyfarwyddiadau canlynol yn ffurfio dechrau dilyniant rheolydd y gwerthusydd rheolaeth eglur:³¹⁴

read-eval-print-loop
  (perform (op initialize-stack))
  (perform (op prompt-for-input)
           (const ";;; EC-Eval input:"))
  (assign exp (op read))
  (assign env (op get-global-environment))
  (assign continue (label print-result))
  (goto (label eval-dispatch))
print-result
  (perform (op announce-output)
           (const ";;; EC-Eval value:"))
  (perform (op user-print) (reg val))
  (goto (label read-eval-print-loop))

Pan ddeuwn ar draws gwall mewn gweithdrefn (megis y “gwall math gweithdrefn anhysbys” a ddangosir yn apply-dispatch), argraffwn neges gwall a dychwelwn at y ddolen yrru.³¹⁵

unknown-expression-type
  (assign 
   val
   (const unknown-expression-type-error))
  (goto (label signal-error))
unknown-procedure-type
  ; clean up stack (from apply-dispatch):
  (restore continue)    
  (assign 
   val
   (const unknown-procedure-type-error))
  (goto (label signal-error))
signal-error
  (perform (op user-print) (reg val))
  (goto (label read-eval-print-loop))

At ddibenion yr efelychiad, cychwynnwn y pentwr bob tro drwy'r ddolen yrru, gan nad yw efallai'n wag ar ôl i wall (megis newidyn heb ei ddiffinio) dorri ar draws gwerthusiad.³¹⁶

Os cyfunwn yr holl ddarnau cod a gyflwynwyd yn 5.4.1–5.4.4, gallwn greu model peiriant gwerthusydd y gallwn ei redeg drwy efelychydd peiriannau cofrestri 5.2.

(define eceval
  (make-machine
   '(exp env val proc argl continue unev)
   eceval-operations
   '(read-eval-print-loop
     ⟨entire machine controller 
      as given above⟩)))

Rhaid diffinio gweithdrefnau Scheme i efelychu'r gweithrediadau a ddefnyddir yn rhai cyntefig gan y gwerthusydd. Dyma'r un gweithdrefnau a ddefnyddiasom ar gyfer y gwerthusydd metagylchol yn 4.1, ynghyd â'r ychydig rai ychwanegol a ddiffiniwyd mewn troednodiadau drwy gydol 5.4.

(define eceval-operations
  (list (list 'self-evaluating? 
              self-evaluating)
        ⟨complete list of operations 
         for eceval machine⟩))

Yn olaf, gallwn gychwyn yr amgylchedd byd-eang a rhedeg y gwerthusydd:

(define the-global-environment
  (setup-environment))

(start eceval)

;;; EC-Eval input:
(define (append x y)
  (if (null? x)
      y
      (cons (car x) (append (cdr x) y))))

;;; EC-Eval value:
ok

;;; EC-Eval input:
(append '(a b c) '(d e f))

;;; EC-Eval value:
(a b c d e f)

Wrth gwrs, bydd gwerthuso mynegiadau fel hyn yn cymryd llawer mwy o amser na phe baem wedi'u teipio'n uniongyrchol i Scheme, oherwydd y lefelau lluosog o efelychu dan sylw. Gwerthusir ein mynegiadau gan beiriant y gwerthusydd rheolaeth eglur, sy'n cael ei efelychu gan raglen Scheme, sydd ei hun yn cael ei gwerthuso gan y dehonglydd Scheme.

Monitro perfformiad y gwerthusydd

Gall efelychu fod yn arf pwerus i arwain gweithredu gwerthuswyr. Mae efelychiadau'n ei gwneud yn hawdd nid yn unig archwilio amrywiadau ar ddyluniad y peiriant cofrestri ond hefyd fonitro perfformiad y gwerthusydd wedi'i efelychu. Er enghraifft, un ffactor pwysig mewn perfformiad yw pa mor effeithlon y mae'r gwerthusydd yn defnyddio'r pentwr. Gallwn weld nifer y gweithrediadau pentwr sydd eu hangen i werthuso amrywiol fynegiadau drwy ddiffinio peiriant cofrestri'r gwerthusydd gyda'r fersiwn o'r efelychydd sy'n casglu ystadegau am ddefnydd y pentwr (5.2.4), ac ychwanegu cyfarwyddyd ym mhwynt mynediad print-result y gwerthusydd i argraffu'r ystadegau:

print-result
  ; added instruction:
  (perform (op print-stack-statistics))
  (perform (op announce-output)
           (const ";;; EC-Eval value:"))
  … ; same as before

Bellach mae rhyngweithiadau â'r gwerthusydd yn edrych fel hyn:

;;; EC-Eval input:
(define (factorial n)
  (if (= n 1) 1 (* (factorial (- n 1)) n)))
(total-pushes = 3, maximum-depth = 3)

;;; EC-Eval value:
ok

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

;;; EC-Eval value:
120

Sylwch fod dolen yrru'r gwerthusydd yn ailgychwyn y pentwr ar ddechrau pob rhyngweithiad, fel y bydd yr ystadegau a argreffir yn cyfeirio at y gweithrediadau pentwr a ddefnyddiwyd i werthuso'r mynegiad blaenorol yn unig.

Ymarfer 5.26: Defnyddiwch y pentwr wedi'i fonitro i archwilio priodwedd dychweliad cynffon y gwerthusydd (5.4.2). Dechreuwch y gwerthusydd a diffiniwch y weithdrefn iteru factorial o 1.2.1:

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

Rhedwch y weithdrefn gyda rhai gwerthoedd bach o $n$. Cofnodwch ddyfnder mwyaf y pentwr a nifer y gwthiadau sydd eu hangen i gyfrifiannu $n!$ ar gyfer pob un o'r gwerthoedd hyn.

1. Byddwch yn canfod bod y dyfnder mwyaf sydd ei angen i werthuso $n!$ yn annibynnol ar $n$. Beth yw'r dyfnder hwnnw?
2. Pennwch o'ch data fformiwla yn nhermau $n$ ar gyfer cyfanswm nifer y gweithrediadau gwthio a ddefnyddir wrth werthuso $n!$ ar gyfer unrhyw $n\ge <!--\; \ge \; -->1$. Sylwch fod nifer y gweithrediadau a ddefnyddir yn ffwythiant llinol o $n$ ac felly'n cael ei bennu gan ddau gysonyn.

Ymarfer 5.27: Er mwyn cymharu ag Ymarfer 5.26, archwiliwch ymddygiad y weithdrefn ganlynol ar gyfer cyfrifiannu ffactorialau'n ddychweliadol:

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

Drwy redeg y weithdrefn hon gyda'r pentwr wedi'i fonitro, pennwch, fel ffwythiant o $n$, ddyfnder mwyaf y pentwr a chyfanswm nifer y gwthiadau a ddefnyddir wrth werthuso $n!$ ar gyfer $n\ge <!--\; \ge \; -->1$. (Unwaith eto, bydd y ffwythiannau hyn yn llinol.) Crynhowch eich arbrofion drwy lenwi'r tabl canlynol â'r mynegiadau priodol yn nhermau $n$: $$\begin{array}{lll}& \text{Dyfnder}& \text{Nifer y}\\ & \text{mwyaf}& \text{gwthiadau}\\ \text{Ffactorial}& & \\ \text{dychweliadol}& & \\ \text{Ffactorial}& & \\ \text{drwy iteru}& & \end{array}$$ Mae'r dyfnder mwyaf yn fesur o faint y gofod a ddefnyddir gan y gwerthusydd i gyflawni'r cyfrifiad, ac mae nifer y gwthiadau'n cydberthyn yn dda â'r amser sydd ei angen.

Ymarfer 5.28: Addaswch ddiffiniad y gwerthusydd drwy newid eval-sequence fel y disgrifir yn 5.4.2 fel nad yw'r gwerthusydd bellach yn ddychweliadol yn y gynffon. Ailredwch eich arbrofion o Ymarfer 5.26 ac Ymarfer 5.27 i ddangos bod y ddwy fersiwn o'r weithdrefn factorial bellach yn gofyn am ofod sy'n tyfu'n llinol gyda'u mewnbwn.

Ymarfer 5.29: Monitrwch y gweithrediadau pentwr yn y cyfrifiad Fibonacci dychweliadol coeden:

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

1. Rhowch fformiwla yn nhermau $n$ ar gyfer dyfnder mwyaf y pentwr sydd ei angen i gyfrifiannu $\text{Fib}(n)$ ar gyfer $n\ge <!--\; \ge \; -->2$. Awgrym: yn 1.2.2 dadleuasom fod y gofod a ddefnyddir gan y broses hon yn tyfu'n llinol ag $n$.
2. Rhowch fformiwla ar gyfer cyfanswm nifer y gwthiadau a ddefnyddir i gyfrifiannu $\text{Fib}(n)$ ar gyfer $n\ge <!--\; \ge \; -->2$. Dylech ganfod bod nifer y gwthiadau (sy'n cydberthyn yn dda â'r amser a ddefnyddir) yn tyfu'n esbonyddol ag $n$. Awgrym: gadewch i $S(n)$ fod yn nifer y gwthiadau a ddefnyddir wrth gyfrifiannu $\text{Fib}(n)$. Dylech allu dadlau bod fformiwla sy'n mynegi $S(n)$ yn nhermau $S(n-<!--\; -\; -->1)$, $S(n-<!--\; -\; -->2)$, a rhyw gysonyn “gorbenion” sefydlog $k$ sy'n annibynnol ar $n$. Rhowch y fformiwla, a dywedwch beth yw $k$. Yna dangoswch y gellir mynegi $S(n)$ fel $a\cdot <!--\; \cdot \; -->\text{Fib}(n+1)+b$, a rhowch werthoedd $a$ ac $b$.

Ymarfer 5.30: Ar hyn o bryd, dim ond dau fath o wall y mae ein gwerthusydd yn eu dal ac yn rhoi signal amdanynt—mathau anhysbys o fynegiadau a mathau anhysbys o weithdrefnau. Bydd gwallau eraill yn mynd â ni allan o ddolen darllen-gwerthuso-argraffu'r gwerthusydd. Pan redwn y gwerthusydd drwy'r efelychydd peiriannau cofrestri, caiff y gwallau hyn eu dal gan y system Scheme sylfaenol. Mae hyn yn cyfateb i'r cyfrifiadur yn chwalu pan fydd rhaglen defnyddiwr yn gwneud gwall.³¹⁷ Mae gwneud i system wallau go iawn weithio yn brosiect mawr, ond mae deall yr hyn sydd ynghlwm wrth hyn yn werth yr ymdrech.

1. Gellid dal gwallau sy'n digwydd yn y broses werthuso, megis ymgais i gyrchu newidyn heb ei rwymo, drwy newid y gweithrediad chwilio i wneud iddo ddychwelyd cod cyflwr penodol na all fod yn werth posibl unrhyw newidyn defnyddiwr. Gall y gwerthusydd brofi am y cod cyflwr hwn ac yna wneud yr hyn sydd ei angen i fynd at signal-error. Canfyddwch bob man yn y gwerthusydd lle mae angen newid o'r fath a'i gywiro. Mae hyn yn llawer o waith.
2. Llawer gwaeth yw'r broblem o ymdrin â gwallau y rhoddir signal amdanynt drwy gymhwyso gweithdrefnau cyntefig, megis ymgais i rannu â sero neu ymgais i echdynnu car symbol. Mewn system o ansawdd uchel a ysgrifennwyd yn broffesiynol, gwirir diogelwch pob cymhwysiad cyntefig fel rhan o'r weithdrefn gyntefig. Er enghraifft, gallai pob galwad i car wirio'n gyntaf fod yr arg yn bâr. Os nad yw'r arg yn bâr, byddai'r cymhwysiad yn dychwelyd cod cyflwr penodol i'r gwerthusydd, a fyddai wedyn yn adrodd am y methiant. Gallem drefnu hyn yn ein hefelychydd peiriannau cofrestri drwy wneud i bob gweithdrefn gyntefig wirio a ellir ei chymhwyso a dychwelyd cod cyflwr penodol priodol ar fethiant. Yna gall y cod primitive-apply yn y gwerthusydd wirio am y cod cyflwr a mynd at signal-error os oes angen. Adeiladwch y strwythur hwn a gwnewch iddo weithio. Mae hwn yn brosiect sylweddol.

(define (empty-arglist) '())
(define (adjoin-arg arg arglist)
  (append arglist (list arg)))

(define (last-operand? ops) (null? (cdr ops)))

(define (no-more-exps? seq) (null? seq))

(define the-global-environment
  (setup-environment))

(define (get-global-environment)
  the-global-environment)