3.3 Modelu â Data Newidiadwy

Ymdriniodd Pennod 2 â data cyfansawdd fel modd o adeiladu gwrthrychau cyfrifiadurol sydd â sawl rhan, er mwyn modelu gwrthrychau yn y byd go iawn sydd â sawl agwedd. Yn y bennod honno cyflwynasom ddisgyblaeth haniaethu data, yn ôl yr hon y pennir strwythurau data yn nhermau adeiladwyr, sy'n creu gwrthrychau data, a detholwyr, sy'n cyrchu rhannau gwrthrychau data cyfansawdd. Ond bellach gwyddom fod agwedd arall ar ddata nad ymdriniodd pennod 2 â hi. Mae'r awydd i fodelu systemau sy'n cynnwys gwrthrychau â chyflwr sy'n newid yn ein harwain at yr angen i addasu gwrthrychau data cyfansawdd, yn ogystal â'u hadeiladu a dethol ohonynt. Er mwyn modelu gwrthrychau cyfansawdd â chyflwr sy'n newid, byddwn yn dylunio haniaethau data i gynnwys, yn ogystal â detholwyr ac adeiladwyr, weithrediadau o'r enw newidwyr, sy'n addasu gwrthrychau data. Er enghraifft, mae modelu system fancio yn gofyn inni newid balansau cyfrifon. Felly, gallai strwythur data ar gyfer cynrychioli cyfrifon banc ganiatáu gweithrediad

(set-balance! ⟨account⟩ ⟨new-value⟩)

sy'n newid balans y cyfrif penodedig i'r gwerth newydd penodedig. Gelwir gwrthrychau data y diffinnir newidwyr ar eu cyfer yn wrthrychau data newidiadwy.

Cyflwynodd Pennod 2 barau fel “glud” at ddefnydd cyffredinol i gyfuno data cyfansawdd. Dechreuwn yr adran hon drwy ddiffinio newidwyr sylfaenol ar gyfer parau, fel y gall parau wasanaethu'n flociau adeiladu ar gyfer creu gwrthrychau data newidiadwy. Mae'r newidwyr hyn yn cynyddu gallu cynrychioli parau yn fawr, gan ein galluogi i adeiladu strwythurau data heblaw'r dilyniannau a'r coed y gweithiasom â hwy yn 2.2. Cyflwynwn hefyd rai enghreifftiau o efelychiadau lle modelir systemau cymhleth yn gasgliadau o wrthrychau â chyflwr lleol.

3.3.1Strwythur Rhestrau Newidiadwy

Gellir defnyddio'r gweithrediadau sylfaenol ar barau—cons, car, ac cdr—i adeiladu strwythur rhestrau ac i ddethol rhannau ohono, ond ni allant addasu strwythur rhestrau. Mae'r un peth yn wir am y gweithrediadau rhestrau a ddefnyddiasom hyd yma, megis append ac list, gan y gellir diffinio'r rhain yn nhermau cons, car, ac cdr. I addasu strwythurau rhestrau mae arnom angen gweithrediadau newydd.

Y newidwyr cyntefig ar gyfer parau yw set-car! ac set-cdr!. Mae Set-car! yn cymryd dau arg, y mae'n rhaid i'r cyntaf fod yn bâr. Mae'n addasu'r pâr hwn drwy roi pwyntydd at ail arg set-car! yn lle'r pwyntydd car.¹⁴⁴

Yn enghraifft, tybiwch fod x wedi'i rwymo i'r rhestr ((a b) c d) ac y i'r rhestr (e f) fel y dangosir yn Ffigur 3.12. Mae gwerthuso'r mynegiad (set-car! x y) yn addasu'r pâr y mae x wedi'i rwymo iddo, gan roi gwerth y yn lle ei car. Dangosir canlyniad y gweithrediad yn Ffigur 3.13. Mae'r strwythur x wedi'i addasu a byddai bellach yn cael ei argraffu fel ((e f) c d). Mae'r parau sy'n cynrychioli'r rhestr (a b), a ddynodwyd gan y pwyntydd a ddisodlwyd, bellach wedi'u datgysylltu oddi wrth y strwythur gwreiddiol.¹⁴⁵

Cymharwch Ffigur 3.13 â Ffigur 3.14, sy'n dangos canlyniad gweithredu (define z (cons y (cdr x))) ag x ac y wedi'u rhwymo i restrau gwreiddiol Ffigur 3.12. Mae'r newidyn z bellach wedi'i rwymo i bâr newydd a grëwyd gan y gweithrediad cons; nid yw'r rhestr y mae x wedi'i rwymo iddi wedi newid.

Mae'r gweithrediad set-cdr! yn debyg i set-car!. Yr unig wahaniaeth yw mai pwyntydd cdr y pâr, yn hytrach na'r pwyntydd car, sy'n cael ei ddisodli. Dangosir effaith gweithredu (set-cdr! x y) ar restrau Ffigur 3.12 yn Ffigur 3.15. Yma mae pwyntydd cdr x wedi'i ddisodli gan y pwyntydd at (e f). Hefyd, mae'r rhestr (c d), a arferai fod yn cdr x, bellach wedi'i datgysylltu oddi wrth y strwythur.

Mae Cons yn adeiladu strwythur rhestrau newydd drwy greu parau newydd, tra bod set-car! ac set-cdr! yn addasu parau sy'n bodoli eisoes. Yn wir, gallem weithredu cons yn nhermau'r ddau newidiwr, ynghyd â gweithdrefn get-new-pair, sy'n dychwelyd pâr newydd nad yw'n rhan o unrhyw strwythur rhestrau sy'n bodoli eisoes. Cawn y pâr newydd, gosodwn ei bwyntyddion car ac cdr at y gwrthrychau penodedig, a dychwelwn y pâr newydd yn ganlyniad cons.¹⁴⁶

(define (cons x y)
  (let ((new (get-new-pair)))
    (set-car! new x)
    (set-cdr! new y)
    new))

Ymarfer 3.12: Cyflwynwyd y weithdrefn ganlynol ar gyfer atodi rhestrau yn 2.2.1:

(define (append x y)
  (if (null? x)
      y
      (cons (car x) (append (cdr x) y))))

Mae Append yn ffurfio rhestr newydd drwy gymhwyso cons yn olynol i osod elfennau x ar flaen y. Mae'r weithdrefn append! yn debyg i append, ond newidiwr yw hi yn hytrach nag adeiladydd. Mae'n atodi'r rhestrau drwy eu cysylltu â'i gilydd, gan addasu pâr olaf x fel bod ei cdr bellach yn y. (Gwall yw galw append! ag x gwag.)

(define (append! x y)
  (set-cdr! (last-pair x) y)
  x)

Yma mae last-pair yn weithdrefn sy'n dychwelyd y pâr olaf yn ei harg:

(define (last-pair x)
  (if (null? (cdr x))
      x
      (last-pair (cdr x))))

Ystyriwch y rhyngweithiad

(define x (list 'a 'b))
(define y (list 'c 'd))
(define z (append x y))

z
(a b c d)

(cdr x)
⟨response⟩

(define w (append! x y))

w
(a b c d)

(cdr x)
⟨response⟩

Beth yw'r gwerthoedd ⟨response⟩ sydd ar goll? Tynnwch ddiagramau blychau a phwyntyddion i esbonio eich ateb.

Ymarfer 3.13: Ystyriwch y weithdrefn make-cycle ganlynol, sy'n defnyddio'r weithdrefn last-pair a ddiffiniwyd yn Ymarfer 3.12:

(define (make-cycle x)
  (set-cdr! (last-pair x) x)
  x)

Tynnwch ddiagram blychau a phwyntyddion sy'n dangos y strwythur z a grëir gan

(define z (make-cycle (list 'a 'b 'c)))

Beth sy'n digwydd os ceisiwn gyfrifo (last-pair z)?

Ymarfer 3.14: Mae'r weithdrefn ganlynol yn eithaf defnyddiol, er ei bod yn aneglur:

(define (mystery x)
  (define (loop x y)
    (if (null? x)
        y
        (let ((temp (cdr x)))
          (set-cdr! x y)
          (loop temp x))))
  (loop x '()))

Mae Loop yn defnyddio'r newidyn “dros dro” temp i ddal hen werth cdr x, gan fod set-cdr! ar y llinell nesaf yn dinistrio'r cdr. Esboniwch beth mae mystery yn ei wneud yn gyffredinol. Tybiwch y diffinnir v gan (define v (list 'a 'b 'c 'd)). Tynnwch y diagram blychau a phwyntyddion sy'n cynrychioli'r rhestr y mae v wedi'i rwymo iddi. Tybiwch ein bod nawr yn gwerthuso (define w (mystery v)). Tynnwch ddiagramau blychau a phwyntyddion sy'n dangos y strwythurau v ac w ar ôl gwerthuso'r mynegiad hwn. Beth fyddai'n cael ei argraffu yn werthoedd v ac w?

Rhannu a hunaniaeth

Soniasom yn 3.1.3 am y materion damcaniaethol ynghylch “bod yr un fath” a “newid” a godir gan gyflwyno aseiniad. Mae'r materion hyn yn codi'n ymarferol pan rennir parau unigol rhwng gwahanol wrthrychau data. Er enghraifft, ystyriwch y strwythur a ffurfir gan

(define x (list 'a 'b))
(define z1 (cons x x))

Fel y dangosir yn Ffigur 3.16, mae z1 yn bâr y mae ei car a'i cdr ill dau yn pwyntio at yr un pâr x. Mae'r ffaith bod car ac cdr z1 yn rhannu x fel hyn yn ganlyniad i'r ffordd syml y gweithredir cons. Yn gyffredinol, bydd defnyddio cons i adeiladu rhestrau'n arwain at strwythur o barau wedi'u cydgysylltu, lle rhennir llawer o barau unigol gan lawer o wahanol strwythurau.

Mewn cyferbyniad â Ffigur 3.16, mae Ffigur 3.17 yn dangos y strwythur a grëir gan

(define z2 
  (cons (list 'a 'b) (list 'a 'b)))

Yn y strwythur hwn, mae'r parau yn y ddwy restr (a b) ar wahân, er bod y symbolau eu hunain yn cael eu rhannu.¹⁴⁷

O'u hystyried yn rhestrau, mae z1 ac z2 ill dau yn cynrychioli “yr un” rhestr, ((a b) a b). Yn gyffredinol, ni ellir canfod rhannu o gwbl os gweithredwn ar restrau gan ddefnyddio cons, car, ac cdr yn unig. Fodd bynnag, os caniatawn newidwyr ar strwythur rhestrau, daw rhannu'n arwyddocaol. Yn enghraifft o'r gwahaniaeth y gall rhannu ei wneud, ystyriwch y weithdrefn ganlynol, sy'n addasu car y strwythur y'i cymhwysir iddo:

(define (set-to-wow! x)
  (set-car! (car x) 'wow)
  x)

Er bod z1 ac z2 yn “yr un” strwythur, mae cymhwyso set-to-wow! iddynt yn rhoi canlyniadau gwahanol. Gydag z1, mae newid yr car hefyd yn newid yr cdr, am fod yr car a'r cdr yn z1 yr un pâr. Gydag z2, mae'r car a'r cdr ar wahân, felly dim ond yr car y mae set-to-wow! yn ei addasu:

z1
((a b) a b)

(set-to-wow! z1)
((wow b) wow b)

z2
((a b) a b)

(set-to-wow! z2)
((wow b) a b)

Un ffordd o ganfod rhannu mewn strwythurau rhestrau yw defnyddio'r traethiad eq?, a gyflwynasom yn 2.3.1 fel ffordd o brofi a yw dau symbol yn hafal. Yn fwy cyffredinol, mae (eq? x y) yn profi ai'r un gwrthrych yw x ac y (hynny yw, a yw x ac y yn hafal fel pwyntyddion). Felly, gydag z1 ac z2 fel y'u diffiniwyd yn Ffigur 3.16 a Ffigur 3.17, mae (eq? (car z1) (cdr z1)) yn wir ac mae (eq? (car z2) (cdr z2)) yn anwir.

Fel y gwelir yn yr adrannau canlynol, gallwn ddefnyddio rhannu i ehangu'n fawr yr amrywiaeth o strwythurau data y gellir eu cynrychioli gan barau. Ar y llaw arall, gall rhannu hefyd fod yn beryglus, gan y bydd addasiadau i strwythurau hefyd yn effeithio ar strwythurau eraill sy'n digwydd rhannu'r rhannau a addaswyd. Dylid defnyddio'r gweithrediadau newid set-car! ac set-cdr! yn ofalus; oni bai bod gennym ddealltwriaeth dda o sut y rhennir ein gwrthrychau data, gall eu newid gael canlyniadau annisgwyl.¹⁴⁸

Ymarfer 3.15: Tynnwch ddiagramau blychau a phwyntyddion i esbonio effaith set-to-wow! ar y strwythurau z1 ac z2 uchod.

Ymarfer 3.16: Mae Ben Bitdiddle yn penderfynu ysgrifennu gweithdrefn i gyfrif nifer y parau mewn unrhyw strwythur rhestrau. “Mae'n hawdd,” meddai wrth resymu. “Nifer y parau mewn unrhyw strwythur yw'r nifer yn yr car a'r nifer yn yr cdr ac un arall i gyfrif y pâr presennol.” Felly mae Ben yn ysgrifennu'r weithdrefn ganlynol:

(define (count-pairs x)
  (if (not (pair? x))
      0
      (+ (count-pairs (car x))
         (count-pairs (cdr x))
         1)))

Dangoswch nad yw'r weithdrefn hon yn gywir. Yn benodol, tynnwch ddiagramau blychau a phwyntyddion sy'n cynrychioli strwythurau rhestrau sy'n cynnwys yn union dri phâr, y byddai gweithdrefn Ben ar eu cyfer yn dychwelyd 3; yn dychwelyd 4; yn dychwelyd 7; neu byth yn dychwelyd o gwbl.

Ymarfer 3.17: Dyfeisiwch fersiwn gywir o weithdrefn count-pairs Ymarfer 3.16 sy'n dychwelyd nifer y parau ar wahân mewn unrhyw strwythur. (Awgrym: Tramwywch y strwythur, gan gadw strwythur data ategol a ddefnyddir i gadw golwg ar ba barau sydd eisoes wedi'u cyfrif.)

Ymarfer 3.18: Ysgrifennwch weithdrefn sy'n archwilio rhestr ac yn pennu a yw'n cynnwys cylch, hynny yw, a fyddai rhaglen a geisiai ddod o hyd i ddiwedd y rhestr drwy gymryd cdr yn olynol yn mynd i ddolen ddiddiwedd. Adeiladwyd rhestrau o'r fath yn Ymarfer 3.13.

Ymarfer 3.19: Gwnewch Ymarfer 3.18 eto gan ddefnyddio algorithm sy'n cymryd swm cyson o ofod yn unig. (Mae angen syniad clyfar iawn i wneud hyn.)

Nid yw newid gwrthrych ond yn aseiniad

Pan gyflwynasom ddata cyfansawdd, nodasom yn 2.1.3 y gellir cynrychioli parau yn gyfan gwbl yn nhermau gweithdrefnau:

(define (cons x y)
  (define (dispatch m)
    (cond ((eq? m 'car) x)
          ((eq? m 'cdr) y)
          (else (error "Undefined 
                 operation: CONS" m))))
  dispatch)

(define (car z) (z 'car))
(define (cdr z) (z 'cdr))

Mae'r un sylw'n wir am ddata newidiadwy. Gallwn weithredu gwrthrychau data newidiadwy fel gweithdrefnau gan ddefnyddio aseiniad a chyflwr lleol. Er enghraifft, gallwn ymestyn y gweithrediad uchod o barau i drin set-car! ac set-cdr! mewn ffordd gyfatebol i'r ffordd y gweithredasom gyfrifon banc gan ddefnyddio make-account yn 3.1.1:

(define (cons x y)
  (define (set-x! v) (set! x v))
  (define (set-y! v) (set! y v))
  (define (dispatch m)
    (cond ((eq? m 'car) x)
          ((eq? m 'cdr) y)
          ((eq? m 'set-car!) set-x!)
          ((eq? m 'set-cdr!) set-y!)
          (else (error "Undefined 
                 operation: CONS" m))))
  dispatch)

(define (car z) (z 'car))
(define (cdr z) (z 'cdr))

(define (set-car! z new-value)
  ((z 'set-car!) new-value)
  z)

(define (set-cdr! z new-value)
  ((z 'set-cdr!) new-value)
  z)

Aseiniad yw'r cyfan sydd ei angen, yn ddamcaniaethol, i esbonio ymddygiad data newidiadwy. Cyn gynted ag y caniatawn set! yn ein hiaith, codwn yr holl faterion sy'n ymwneud nid yn unig ag aseiniad, ond â data newidiadwy'n gyffredinol.¹⁴⁹

Ymarfer 3.20: Tynnwch ddiagramau amgylchedd i ddangos gwerthuso'r dilyniant o fynegiadau

(define x (cons 1 2))
(define z (cons x x))

(set-car! (cdr z) 17)

(car x)
17

gan ddefnyddio'r gweithrediad gweithdrefnol o barau a roddir uchod. (Cymharwch Ymarfer 3.11.)

3.3.2Cynrychioli Ciwiau

Mae'r newidwyr set-car! ac set-cdr! yn ein galluogi i ddefnyddio parau i adeiladu strwythurau data na ellir eu hadeiladu ag cons, car, ac cdr yn unig. Mae'r adran hon yn dangos sut i ddefnyddio parau i gynrychioli strwythur data a elwir yn giw. Bydd Adran 3.3.3 yn dangos sut i gynrychioli strwythurau data a elwir yn dablau.

Dilyniant yw ciw lle mewnosodir eitemau mewn un pen (a elwir yn gefn y ciw) a'u dileu o'r pen arall (y blaen). Mae Ffigur 3.18 yn dangos ciw sy'n wag i ddechrau, y mewnosodir yr eitemau a ac b ynddo. Yna tynnir a, mewnosodir c ac d, a thynnir b. Gan fod eitemau bob amser yn cael eu tynnu yn y drefn y'u mewnosodir, gelwir ciw weithiau yn glustog FIFO (cyntaf i mewn, cyntaf allan).

Yn nhermau haniaethu data, gallwn ystyried ciw wedi'i ddiffinio gan y set ganlynol o weithrediadau:

• adeiladydd: mae (make-queue) yn dychwelyd ciw gwag (ciw heb unrhyw eitemau).
• dau ddetholwr:

  (empty-queue? ⟨queue⟩)

  yn profi a yw'r ciw yn wag.

  (front-queue ⟨queue⟩)

  yn dychwelyd y gwrthrych ar flaen y ciw, gan arwyddo gwall os yw'r ciw yn wag; nid yw'n addasu'r ciw.

• dau newidiwr:

  (insert-queue! ⟨queue⟩ ⟨item⟩)

  yn mewnosod yr eitem yng nghefn y ciw ac yn dychwelyd y ciw wedi'i addasu yn werth iddo.

  (delete-queue! ⟨queue⟩)

  yn tynnu'r eitem ar flaen y ciw ac yn dychwelyd y ciw wedi'i addasu yn werth iddo, gan arwyddo gwall os yw'r ciw yn wag cyn dileu.

Gan fod ciw yn ddilyniant o eitemau, gallem yn sicr ei gynrychioli'n rhestr gyffredin; blaen y ciw fyddai car y rhestr, byddai mewnosod eitem yn y ciw yn gyfystyr ag atodi elfen newydd ar ddiwedd y rhestr, a byddai dileu eitem o'r ciw yn ddim ond cymryd cdr y rhestr. Fodd bynnag, mae'r cynrychioliad hwn yn aneffeithlon, am fod rhaid inni, er mwyn mewnosod eitem, sganio'r rhestr hyd nes cyrraedd y diwedd. Gan mai'r unig ddull sydd gennym o sganio rhestr yw drwy weithrediadau cdr olynol, mae'r sganio hwn yn gofyn am $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ o gamau ar gyfer rhestr o $n$ o eitemau. Mae addasiad syml i'r cynrychioliad rhestr yn goresgyn yr anfantais hon drwy ganiatáu gweithredu gweithrediadau'r ciw fel bod angen $\mathrm{\Theta <!--\; \Theta \; -->}(1)$ o gamau arnynt; hynny yw, fel bod nifer y camau sydd eu hangen yn annibynnol ar hyd y ciw.

Mae'r anhawster gyda'r cynrychioliad rhestr yn deillio o'r angen i sganio i ddod o hyd i ddiwedd y rhestr. Y rheswm dros yr angen i sganio yw, er bod y ffordd safonol o gynrychioli rhestr yn gadwyn o barau yn rhoi pwyntydd at ddechrau'r rhestr inni'n rhwydd, nad yw'n rhoi pwyntydd hawdd ei gyrchu at y diwedd. Yr addasiad sy'n osgoi'r anfantais yw cynrychioli'r ciw yn rhestr, ynghyd â phwyntydd ychwanegol sy'n dynodi'r pâr olaf yn y rhestr. Felly, pan awn ati i fewnosod eitem, gallwn gyfeirio at bwyntydd y cefn ac osgoi sganio'r rhestr.

Cynrychiolir ciw, felly, yn bâr o bwyntyddion, front-ptr ac rear-ptr, sy'n dynodi, yn y drefn honno, y pâr cyntaf a'r pâr olaf mewn rhestr gyffredin. Gan ein bod am i'r ciw fod yn wrthrych y gellir ei adnabod, gallwn ddefnyddio cons i gyfuno'r ddau bwyntydd. Felly, y ciw ei hun fydd cons y ddau bwyntydd. Mae Ffigur 3.19 yn dangos y cynrychioliad hwn.

I ddiffinio gweithrediadau'r ciw defnyddiwn y gweithdrefnau canlynol, sy'n ein galluogi i ddethol ac addasu pwyntyddion blaen a chefn ciw:

(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item) 
  (set-car! queue item))
(define (set-rear-ptr! queue item) 
  (set-cdr! queue item))

Nawr gallwn weithredu gweithrediadau'r ciw eu hunain. Byddwn yn ystyried ciw yn wag os mai'r rhestr wag yw ei bwyntydd blaen:

(define (empty-queue? queue) 
  (null? (front-ptr queue)))

Mae'r adeiladydd make-queue yn dychwelyd, fel ciw sy'n wag i ddechrau, bâr y mae ei car a'i cdr ill dau yn rhestr wag:

(define (make-queue) (cons '() '()))

I ddethol yr eitem ar flaen y ciw, dychwelwn car y pâr a ddynodir gan bwyntydd y blaen:

(define (front-queue queue)
  (if (empty-queue? queue)
      (error "FRONT called with an 
              empty queue" queue)
      (car (front-ptr queue))))

I fewnosod eitem mewn ciw, dilynwn y dull y dangosir ei ganlyniad yn Ffigur 3.20. Yn gyntaf crëwn bâr newydd y mae ei car yn eitem i'w mewnosod a'i cdr yn rhestr wag. Os oedd y ciw yn wag i ddechrau, gosodwn bwyntyddion blaen a chefn y ciw at y pâr newydd hwn. Fel arall, addaswn y pâr olaf yn y ciw i bwyntio at y pâr newydd, a gosodwn bwyntydd y cefn at y pâr newydd hefyd.

(define (insert-queue! queue item)
  (let ((new-pair (cons item '())))
    (cond ((empty-queue? queue)
           (set-front-ptr! queue new-pair)
           (set-rear-ptr! queue new-pair)
           queue)
          (else (set-cdr! (rear-ptr queue) 
                          new-pair)
                (set-rear-ptr! queue new-pair)
                queue))))

I ddileu'r eitem ar flaen y ciw, dim ond addasu pwyntydd y blaen a wnawn, fel ei fod bellach yn pwyntio at yr ail eitem yn y ciw, y gellir dod o hyd iddi drwy ddilyn pwyntydd cdr yr eitem gyntaf (gweler Ffigur 3.21):¹⁵⁰

(define (delete-queue! queue)
  (cond ((empty-queue? queue)
         (error "DELETE! called with 
                 an empty queue" queue))
        (else (set-front-ptr! 
               queue 
               (cdr (front-ptr queue)))
              queue)))

Ymarfer 3.21: Mae Ben Bitdiddle yn penderfynu profi'r gweithrediad o giw a ddisgrifir uchod. Mae'n teipio'r gweithdrefnau i mewn i'r dehonglydd Lisp ac yn mynd ati i roi cynnig arnynt:

(define q1 (make-queue))

(insert-queue! q1 'a)
((a) a)

(insert-queue! q1 'b)
((a b) b)

(delete-queue! q1)
((b) b)

(delete-queue! q1)
(() b)

“Mae'r cyfan yn anghywir!” meddai wrth gwyno. “Mae ymateb y dehonglydd yn dangos bod yr eitem olaf yn cael ei mewnosod yn y ciw ddwywaith. A phan ddileaf y ddwy eitem, mae'r ail b yno o hyd, felly nid yw'r ciw yn wag, er ei fod i fod felly.” Mae Eva Lu Ator yn awgrymu bod Ben wedi camddeall yr hyn sy'n digwydd. “Nid yw'r eitemau'n mynd i mewn i'r ciw ddwywaith,” eglura. “Y cwbl yw nad yw argraffydd safonol Lisp yn gwybod sut i ddehongli cynrychioliad y ciw. Os wyt ti am weld y ciw yn cael ei argraffu'n gywir, bydd rhaid iti ddiffinio dy weithdrefn argraffu dy hun ar gyfer ciwiau.” Esboniwch beth mae Eva Lu yn sôn amdano. Yn benodol, dangoswch pam mae enghreifftiau Ben yn cynhyrchu'r canlyniadau argraffedig a welir. Diffiniwch weithdrefn print-queue sy'n cymryd ciw yn fewnbwn ac yn argraffu'r dilyniant o eitemau yn y ciw.

Ymarfer 3.22: Yn lle cynrychioli ciw yn bâr o bwyntyddion, gallwn adeiladu ciw fel gweithdrefn â chyflwr lleol. Bydd y cyflwr lleol yn cynnwys pwyntyddion at ddechrau a diwedd rhestr gyffredin. Felly, bydd gan y weithdrefn make-queue y ffurf

(define (make-queue)
  (let ((front-ptr … )
        (rear-ptr … ))
    ⟨definitions of internal procedures⟩
    (define (dispatch m) …)
    dispatch))

Cwblhewch ddiffiniad make-queue a darparwch god ar gyfer gweithrediadau'r ciw gan ddefnyddio'r cynrychioliad hwn.

Ymarfer 3.23: Mae ciw dau ben (“deque”) yn ddilyniant lle gellir mewnosod a dileu eitemau naill ai ar y blaen neu yn y cefn. Y gweithrediadau ar giwiau dau ben yw'r adeiladydd make-deque, y traethiad empty-deque?, y detholwyr front-deque ac rear-deque, a'r newidwyr front-insert-deque!, rear-insert-deque!, front-delete-deque!, rear-delete-deque!. Dangoswch sut i gynrychioli ciwiau dau ben gan ddefnyddio parau, a rhowch god sy'n gweithredu'r gweithrediadau hyn.¹⁵¹ Dylid cyflawni pob gweithrediad mewn $\mathrm{\Theta <!--\; \Theta \; -->}(1)$ o gamau.

3.3.3Cynrychioli Tablau

Pan astudiasom amrywiol ffyrdd o gynrychioli setiau ym Mhennod 2, soniasom yn 2.3.3 am y dasg o gadw tabl o gofnodion wedi'u mynegeio gan allweddi adnabod. Wrth weithredu rhaglennu a gyfarwyddir gan ddata yn 2.4.3, gwnaethom ddefnydd helaeth o dablau dau ddimensiwn, lle storir ac adferir gwybodaeth gan ddefnyddio dwy allwedd. Yma gwelwn sut i adeiladu tablau fel strwythurau rhestrau newidiadwy.

Yn gyntaf ystyriwn dabl un dimensiwn, lle storir pob gwerth o dan un allwedd. Gweithredwn y tabl fel rhestr o gofnodion, pob un wedi'i weithredu'n bâr sy'n cynnwys allwedd a'r gwerth cysylltiedig. Gludir y cofnodion ynghyd i ffurfio rhestr gan barau y mae eu car yn pwyntio at gofnodion olynol. Gelwir y parau gludo hyn yn asgwrn cefn y tabl. Er mwyn cael man y gallwn ei newid pan ychwanegwn gofnod newydd at y tabl, adeiladwn y tabl yn rhestr â phennyn. Mae gan restr â phennyn bâr asgwrn cefn arbennig ar y dechrau, sy'n dal “cofnod” ffug—yn yr achos hwn, y symbol *table* a ddewiswyd yn fympwyol. Mae Ffigur 3.22 yn dangos y diagram blychau a phwyntyddion ar gyfer y tabl

a:  1
b:  2
c:  3

I dynnu gwybodaeth o dabl defnyddiwn y weithdrefn lookup, sy'n cymryd allwedd yn arg ac yn dychwelyd y gwerth cysylltiedig (neu anwir os nad oes gwerth wedi'i storio o dan yr allwedd honno). Diffinnir Lookup yn nhermau'r gweithrediad assoc, sy'n disgwyl allwedd a rhestr o gofnodion yn argiau. Sylwch nad yw assoc byth yn gweld y cofnod ffug. Mae Assoc yn dychwelyd y cofnod y mae'r allwedd a roddwyd yn car iddo.¹⁵² Yna mae Lookup yn gwirio nad yw'r cofnod a ddychwelwyd gan assoc yn anwir, ac yn dychwelyd gwerth (yr cdr) y cofnod.

(define (lookup key table)
  (let ((record (assoc key (cdr table))))
    (if record
        (cdr record)
        false)))

(define (assoc key records)
  (cond ((null? records) false)
        ((equal? key (caar records)) 
         (car records))
        (else (assoc key (cdr records)))))

I fewnosod gwerth mewn tabl o dan allwedd benodedig, defnyddiwn assoc yn gyntaf i weld a oes cofnod â'r allwedd hon eisoes yn y tabl. Os nad oes, ffurfiwn gofnod newydd drwy gyfuno'r allwedd â'r gwerth gan ddefnyddio cons, a mewnosodwn hwn ar ben rhestr cofnodion y tabl, ar ôl y cofnod ffug. Os oes cofnod â'r allwedd hon eisoes, gosodwn cdr y cofnod hwn i'r gwerth newydd penodedig. Mae pennyn y tabl yn rhoi man sefydlog inni ei addasu er mwyn mewnosod y cofnod newydd.¹⁵³

(define (insert! key value table)
  (let ((record (assoc key (cdr table))))
    (if record
        (set-cdr! record value)
        (set-cdr! table
                  (cons (cons key value) 
                        (cdr table)))))
  'ok)

I adeiladu tabl newydd, dim ond creu rhestr sy'n cynnwys y symbol *table* a wnawn:

(define (make-table)
  (list '*table*))

Tablau dau ddimensiwn

Mewn tabl dau ddimensiwn, mynegeir pob gwerth gan ddwy allwedd. Gallwn adeiladu tabl o'r fath fel tabl un dimensiwn lle mae pob allwedd yn adnabod is-dabl. Mae Ffigur 3.23 yn dangos y diagram blychau a phwyntyddion ar gyfer y tabl

math:  +: 43    letters:  a: 97
       -: 45              b: 98
       *: 42

sydd â dau is-dabl. (Nid oes angen symbol pennyn arbennig ar yr is-dablau, gan fod yr allwedd sy'n adnabod yr is-dabl yn cyflawni'r diben hwn.)

Wrth chwilio am eitem, defnyddiwn yr allwedd gyntaf i adnabod yr is-dabl cywir. Yna defnyddiwn yr ail allwedd i adnabod y cofnod o fewn yr is-dabl.

(define (lookup key-1 key-2 table)
  (let ((subtable (assoc key-1 (cdr table))))
    (if subtable
        (let ((record 
               (assoc key-2 (cdr subtable))))
          (if record (cdr record) false))
        false)))

I fewnosod eitem newydd o dan bâr o allweddi, defnyddiwn assoc i weld a oes is-dabl wedi'i storio o dan yr allwedd gyntaf. Os nad oes, adeiladwn is-dabl newydd sy'n cynnwys yr un cofnod (key-2, value) a'i fewnosod yn y tabl o dan yr allwedd gyntaf. Os oes is-dabl eisoes yn bodoli ar gyfer yr allwedd gyntaf, mewnosodwn y cofnod newydd yn yr is-dabl hwn, gan ddefnyddio'r dull mewnosod ar gyfer tablau un dimensiwn a ddisgrifir uchod:

(define (insert! key-1 key-2 value table)
  (let ((subtable (assoc key-1 (cdr table))))
    (if subtable
        (let ((record 
               (assoc key-2 (cdr subtable))))
          (if record
              (set-cdr! record value)
              (set-cdr! 
               subtable
               (cons (cons key-2 value)
                     (cdr subtable)))))
        (set-cdr! 
         table
         (cons (list key-1 (cons key-2 value))
               (cdr table)))))
  'ok)

Creu tablau lleol

Mae'r gweithrediadau lookup ac insert! a ddiffiniwyd uchod yn cymryd y tabl yn arg. Mae hyn yn ein galluogi i ddefnyddio rhaglenni sy'n cyrchu mwy nag un tabl. Ffordd arall o ymdrin â sawl tabl yw cael gweithdrefnau lookup ac insert! ar wahân ar gyfer pob tabl. Gallwn wneud hyn drwy gynrychioli tabl yn weithdrefnol, fel gwrthrych sy'n cadw tabl mewnol yn rhan o'i gyflwr lleol. Pan anfonir neges briodol ato, mae'r “gwrthrych tabl” hwn yn darparu'r weithdrefn i weithredu ar y tabl mewnol. Dyma generadur ar gyfer tablau dau ddimensiwn a gynrychiolir fel hyn:

(define (make-table)
  (let ((local-table (list '*table*)))
    (define (lookup key-1 key-2)
      (let ((subtable 
             (assoc key-1 (cdr local-table))))
        (if subtable
            (let ((record 
                   (assoc key-2 
                          (cdr subtable))))
              (if record (cdr record) false))
            false)))
    (define (insert! key-1 key-2 value)
      (let ((subtable 
             (assoc key-1 (cdr local-table))))
        (if subtable
            (let ((record 
                   (assoc key-2 
                          (cdr subtable))))
              (if record
                  (set-cdr! record value)
                  (set-cdr! 
                   subtable
                   (cons (cons key-2 value)
                         (cdr subtable)))))
            (set-cdr! 
             local-table
             (cons (list key-1
                         (cons key-2 value))
                   (cdr local-table)))))
      'ok)
    (define (dispatch m)
      (cond ((eq? m 'lookup-proc) lookup)
            ((eq? m 'insert-proc!) insert!)
            (else (error "Unknown operation: 
                          TABLE" m))))
    dispatch))

Gan ddefnyddio make-table, gallem weithredu'r gweithrediadau get ac put a ddefnyddiwyd yn 2.4.3 ar gyfer rhaglennu a gyfarwyddir gan ddata, fel a ganlyn:

(define operation-table (make-table))
(define get (operation-table 'lookup-proc))
(define put (operation-table 'insert-proc!))

Mae Get yn cymryd dwy allwedd yn argiau, ac mae put yn cymryd dwy allwedd a gwerth yn argiau. Mae'r ddau weithrediad yn cyrchu'r un tabl lleol, sydd wedi'i amgáu o fewn y gwrthrych a grëir gan yr alwad i make-table.

Ymarfer 3.24: Yn y gweithrediadau o dablau uchod, profir a yw'r allweddi'n hafal gan ddefnyddio equal? (a elwir gan assoc). Nid hwn yw'r prawf priodol bob amser. Er enghraifft, gallem gael tabl ag allweddi rhifiadol lle nad oes arnom angen cyfatebiaeth union i'r rhif rydym yn chwilio amdano, ond dim ond rhif sydd o fewn rhyw oddefiant iddo. Dyluniwch adeiladydd tabl make-table sy'n cymryd gweithdrefn same-key? yn arg i'w defnyddio i brofi “hafaledd” allweddi. Dylai Make-table ddychwelyd gweithdrefn dispatch y gellir ei defnyddio i gyrchu gweithdrefnau lookup ac insert! priodol ar gyfer tabl lleol.

Ymarfer 3.25: Gan gyffredinoli tablau un a dau ddimensiwn, dangoswch sut i weithredu tabl lle storir gwerthoedd o dan nifer mympwyol o allweddi, a lle gellir storio gwahanol werthoedd o dan wahanol niferoedd o allweddi. Dylai'r gweithdrefnau lookup ac insert! gymryd yn fewnbwn restr o allweddi a ddefnyddir i gyrchu'r tabl.

Ymarfer 3.26: I chwilio tabl fel y'i gweithredir uchod, mae angen sganio drwy'r rhestr o gofnodion. Yn ei hanfod, dyma gynrychioliad rhestr heb drefn 2.3.3. Ar gyfer tablau mawr, gall fod yn fwy effeithlon strwythuro'r tabl mewn ffordd wahanol. Disgrifiwch weithrediad o dabl lle trefnir y cofnodion (allwedd, gwerth) gan ddefnyddio coeden ddeuaidd, gan dybio y gellir rhoi allweddi mewn rhyw drefn (e.e., yn rhifiadol neu'n nhrefn yr wyddor). (Cymharwch Ymarfer 2.66 ym Mhennod 2.)

Ymarfer 3.27: Mae cofio canlyniadau (memoization, a elwir hefyd yn dablu) yn dechneg sy'n galluogi gweithdrefn i gofnodi, mewn tabl lleol, werthoedd a gyfrifwyd o'r blaen. Gall y dechneg hon wneud gwahaniaeth enfawr i berfformiad rhaglen. Mae gweithdrefn sy'n cofio canlyniadau yn cadw tabl lle storir gwerthoedd galwadau blaenorol, gan ddefnyddio'r argiau a gynhyrchodd y gwerthoedd yn allweddi. Pan ofynnir i'r weithdrefn sy'n cofio canlyniadau gyfrifo gwerth, mae'n gwirio'r tabl yn gyntaf i weld a yw'r gwerth yno eisoes ac, os ydyw, dim ond dychwelyd y gwerth hwnnw a wna. Fel arall, mae'n cyfrifo'r gwerth newydd yn y ffordd arferol ac yn ei storio yn y tabl. Yn enghraifft o gofio canlyniadau, cofiwch o 1.2.2 y broses esbonyddol ar gyfer cyfrifo rhifau Fibonacci:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

Y fersiwn sy'n cofio canlyniadau o'r un weithdrefn yw

(define memo-fib
  (memoize 
   (lambda (n)
     (cond ((= n 0) 0)
           ((= n 1) 1)
           (else 
            (+ (memo-fib (- n 1))
               (memo-fib (- n 2))))))))

lle diffinnir y gweithdrefn cofio canlyniadau fel

(define (memoize f)
  (let ((table (make-table)))
    (lambda (x)
      (let ((previously-computed-result 
             (lookup x table)))
        (or previously-computed-result
            (let ((result (f x)))
              (insert! x result table)
              result))))))

Tynnwch ddiagram amgylchedd i ddadansoddi cyfrifo (memo-fib 3). Esboniwch pam mae memo-fib yn cyfrifo rhif Fibonacci rhif $n^{\text{fed}}$ mewn nifer o gamau sy'n gyfrannol ag $n$. A fyddai'r cynllun yn dal i weithio pe baem wedi diffinio memo-fib yn (memoize fib) yn unig?

3.3.4Efelychydd Cylchedau Digidol

Mae dylunio systemau digidol cymhleth, megis cyfrifiaduron, yn weithgaredd peirianyddol pwysig. Adeiledir systemau digidol drwy gydgysylltu elfennau syml. Er bod ymddygiad yr elfennau unigol hyn yn syml, gall rhwydweithiau ohonynt ymddwyn mewn ffyrdd cymhleth iawn. Mae efelychu dyluniadau cylched arfaethedig ar gyfrifiadur yn offeryn pwysig a ddefnyddir gan beirianwyr systemau digidol. Yn yr adran hon dyluniwn system ar gyfer cyflawni efelychiadau rhesymeg ddigidol. Mae'r system hon yn nodweddu math o raglen a elwir yn efelychiad a yrrir gan ddigwyddiadau, lle mae gweithredoedd (“digwyddiadau”) yn sbarduno digwyddiadau pellach sy'n digwydd yn ddiweddarach, ac sydd yn eu tro'n sbarduno rhagor o ddigwyddiadau, ac yn y blaen.

Bydd ein model cyfrifiadurol o gylched yn cynnwys gwrthrychau sy'n cyfateb i'r cydrannau elfennol y mae'r gylched wedi'i hadeiladu ohonynt. Ceir gwifrau, sy'n cludo signalau digidol. Ar unrhyw adeg, dim ond un o ddau werth posibl, 0 ac 1, y gall signal digidol ei gael. Ceir hefyd amrywiol fathau o flychau ffwythiant digidol, sy'n cysylltu gwifrau sy'n cludo signalau mewnbwn â gwifrau allbwn eraill. Mae blychau o'r fath yn cynhyrchu signalau allbwn a gyfrifir o'u signalau mewnbwn. Oedir y signal allbwn am amser sy'n dibynnu ar fath y blwch ffwythiant. Er enghraifft, mae gwrthdröydd yn flwch ffwythiant cyntefig sy'n gwrthdroi ei fewnbwn. Os yw signal mewnbwn gwrthdröydd yn newid i 0, yna un oedi gwrthdröydd yn ddiweddarach bydd y gwrthdröydd yn newid ei signal allbwn i 1. Os yw signal mewnbwn gwrthdröydd yn newid i 1, yna un oedi gwrthdröydd yn ddiweddarach bydd y gwrthdröydd yn newid ei signal allbwn i 0. Tynnwn wrthdröydd yn symbolaidd fel yn Ffigur 3.24. Mae adwy AC, a ddangosir hefyd yn ffigur 3.24, yn flwch ffwythiant cyntefig â dau fewnbwn ac un allbwn. Mae'n gyrru ei signal allbwn i werth sy'n AC rhesymegol y mewnbynnau. Hynny yw, os daw ei ddau signal mewnbwn yn 1, yna un cyfnod oedi adwy AC yn ddiweddarach bydd yr adwy AC yn gorfodi ei signal allbwn i fod yn 1; fel arall bydd yr allbwn yn 0. Mae adwy NEU yn flwch ffwythiant cyntefig tebyg â dau fewnbwn sy'n gyrru ei signal allbwn i werth sy'n NEU rhesymegol y mewnbynnau. Hynny yw, bydd yr allbwn yn dod yn 1 os yw o leiaf un o'r signalau mewnbwn yn 1; fel arall bydd yr allbwn yn dod yn 0.

Gallwn gysylltu ffwythiannau cyntefig â'i gilydd i adeiladu ffwythiannau mwy cymhleth. I gyflawni hyn, gwifrwn allbynnau rhai blychau ffwythiant i fewnbynnau blychau ffwythiant eraill. Er enghraifft, mae'r gylched hanner-adydd a ddangosir yn Ffigur 3.25 yn cynnwys adwy NEU, dwy adwy AC, a gwrthdröydd. Mae'n cymryd dau signal mewnbwn, A a B, ac mae ganddi ddau signal allbwn, S a C. Bydd S yn dod yn 1 pryd bynnag y mae yn union un o A a B yn 1, a bydd C yn dod yn 1 pryd bynnag y mae A a B ill dau yn 1. Gwelwn o'r ffigur, oherwydd yr oedi dan sylw, y gall yr allbynnau gael eu cynhyrchu ar adegau gwahanol. Mae llawer o anawsterau dylunio cylchedau digidol yn deillio o'r ffaith hon.

Byddwn nawr yn adeiladu rhaglen ar gyfer modelu'r cylchedau rhesymeg ddigidol y dymunwn eu hastudio. Bydd y rhaglen yn adeiladu gwrthrychau cyfrifiadurol sy'n modelu'r gwifrau, a fydd yn “dal” y signalau. Modelir blychau ffwythiant gan weithdrefnau sy'n gorfodi'r perthnasoedd cywir rhwng y signalau.

Un elfen sylfaenol o'n hefelychiad fydd gweithdrefn make-wire, sy'n adeiladu gwifrau. Er enghraifft, gallwn adeiladu chwe gwifren fel a ganlyn:

(define a (make-wire))
(define b (make-wire))
(define c (make-wire))
(define d (make-wire))
(define e (make-wire))
(define s (make-wire))

Atodwn flwch ffwythiant at set o wifrau drwy alw gweithdrefn sy'n adeiladu'r math hwnnw o flwch. Argiau'r weithdrefn adeiladu yw'r gwifrau sydd i'w hatodi at y blwch. Er enghraifft, o wybod y gallwn adeiladu adwyon AC, adwyon NEU, a gwrthdroyddion, gallwn wifro'r hanner-adydd a ddangosir yn Ffigur 3.25 ynghyd:

(or-gate a b d)
ok

(and-gate a b c)
ok

(inverter c e)
ok

(and-gate d e s)
ok

Yn well byth, gallwn roi enw penodol i'r gweithrediad hwn drwy ddiffinio gweithdrefn half-adder sy'n adeiladu'r gylched hon, o gael y pedair gwifren allanol i'w hatodi at yr hanner-adydd:

(define (half-adder a b s c)
  (let ((d (make-wire)) (e (make-wire)))
    (or-gate a b d)
    (and-gate a b c)
    (inverter c e)
    (and-gate d e s)
    'ok))

Mantais gwneud y diffiniad hwn yw y gallwn ddefnyddio half-adder ei hun yn floc adeiladu wrth greu cylchedau mwy cymhleth. Mae Ffigur 3.26, er enghraifft, yn dangos adydd llawn sy'n cynnwys dau hanner-adydd ac adwy NEU.¹⁵⁴ Gallwn adeiladu adydd llawn fel a ganlyn:

(define (full-adder a b c-in sum c-out)
  (let ((c1 (make-wire)) 
        (c2 (make-wire))
        (s  (make-wire)))
    (half-adder b c-in s c1)
    (half-adder a s sum c2)
    (or-gate c1 c2 c-out)
    'ok))

Ar ôl diffinio full-adder yn weithdrefn, gallwn bellach ei ddefnyddio'n floc adeiladu i greu cylchedau mwy cymhleth fyth. (Er enghraifft, gweler Ymarfer 3.30.)

Yn ei hanfod, mae ein hefelychydd yn rhoi'r offer inni adeiladu iaith cylchedau. Os mabwysiadwn y safbwynt cyffredinol ar ieithoedd a ddefnyddiasom wrth astudio Lisp yn 1.1, gallwn ddweud bod y blychau ffwythiant cyntefig yn ffurfio elfennau cyntefig yr iaith, bod gwifro blychau ynghyd yn darparu modd o gyfuno, a bod pennu patrymau gwifro fel gweithdrefnau yn darparu modd o haniaethu.

Blychau ffwythiant cyntefig

Mae'r blychau ffwythiant cyntefig yn gweithredu'r “grymoedd” y mae newid yn y signal ar un wifren yn dylanwadu drwyddynt ar y signalau ar wifrau eraill. I adeiladu blychau ffwythiant, defnyddiwn y gweithrediadau canlynol ar wifrau:

• (get-signal ⟨wire⟩)

  yn dychwelyd gwerth presennol y signal ar y wifren.

• (set-signal! ⟨wire⟩ ⟨new value⟩)

  yn newid gwerth y signal ar y wifren i'r gwerth newydd.

• (add-action! ⟨wire⟩ ⟨procedure of no arguments⟩)

  yn nodi y dylid rhedeg y weithdrefn benodedig pryd bynnag y mae'r signal ar y wifren yn newid ei werth. Gweithdrefnau o'r fath yw'r modd y cyfathrebir newidiadau yng ngwerth signal y wifren i wifrau eraill.

Yn ogystal, defnyddiwn weithdrefn after-delay sy'n cymryd cyfnod oedi a gweithdrefn i'w rhedeg, ac sy'n gweithredu'r weithdrefn a roddwyd ar ôl yr oedi a roddwyd.

Gan ddefnyddio'r gweithdrefnau hyn, gallwn ddiffinio'r ffwythiannau rhesymeg ddigidol cyntefig. I gysylltu mewnbwn ag allbwn drwy wrthdröydd, defnyddiwn add-action! i gysylltu â'r wifren fewnbwn weithdrefn a redir pryd bynnag y mae'r signal ar y wifren fewnbwn yn newid ei werth. Mae'r weithdrefn yn cyfrifo logical-not y signal mewnbwn, ac yna, ar ôl un inverter-delay, yn gosod y signal allbwn i'r gwerth newydd hwn:

(define (inverter input output)
  (define (invert-input)
    (let ((new-value 
           (logical-not (get-signal input))))
      (after-delay 
       inverter-delay
       (lambda ()
         (set-signal! output new-value)))))
  (add-action! input invert-input)
  'ok)

(define (logical-not s)
  (cond ((= s 0) 1)
        ((= s 1) 0)
        (else (error "Invalid signal" s))))

Mae adwy AC ychydig yn fwy cymhleth. Rhaid rhedeg y weithdrefn weithredu os yw'r naill neu'r llall o fewnbynnau'r adwy yn newid. Mae'n cyfrifo logical-and (gan ddefnyddio gweithdrefn debyg i logical-not) gwerthoedd y signalau ar y gwifrau mewnbwn, ac yn trefnu i newid i'r gwerth newydd ddigwydd ar y wifren allbwn ar ôl un and-gate-delay.

(define (and-gate a1 a2 output)
  (define (and-action-procedure)
    (let ((new-value
           (logical-and (get-signal a1) 
                        (get-signal a2))))
      (after-delay 
       and-gate-delay
       (lambda ()
         (set-signal! output new-value)))))
  (add-action! a1 and-action-procedure)
  (add-action! a2 and-action-procedure)
  'ok)

Ymarfer 3.28: Diffiniwch adwy NEU yn flwch ffwythiant cyntefig. Dylai eich adeiladydd or-gate fod yn debyg i and-gate.

Ymarfer 3.29: Ffordd arall o adeiladu adwy NEU yw fel dyfais rhesymeg ddigidol gyfansawdd, wedi'i hadeiladu o adwyon AC a gwrthdroyddion. Diffiniwch weithdrefn or-gate sy'n cyflawni hyn. Beth yw amser oedi'r adwy NEU yn nhermau and-gate-delay ac inverter-delay?

Ymarfer 3.30: Mae Ffigur 3.27 yn dangos adydd cario tonnog (ripple-carry adder) a ffurfir drwy gysylltu $n$ o adyddion llawn yn gadwyn. Dyma'r ffurf symlaf ar adydd paralel ar gyfer adio dau rif deuaidd $n$ did. Y mewnbynnau $A_1$, $A_2$, $A_3$, …, $A_n$ ac $B_1$, $B_2$, $B_3$, …, $B_n$ yw'r ddau rif deuaidd sydd i'w hadio (mae pob $A_k$ ac $B_k$ yn 0 neu'n 1). Mae'r gylched yn cynhyrchu $S_1$, $S_2$, $S_3$, …, $S_n$, sef $n$ did y swm, ac $C$, sef y cario o'r adio. Ysgrifennwch weithdrefn ripple-carry-adder sy'n cynhyrchu'r gylched hon. Dylai'r weithdrefn gymryd yn argiau dair rhestr o $n$ o wifrau yr un—yr $A_k$, yr $B_k$, a'r $S_k$—ac hefyd wifren arall $C$. Prif anfantais yr adydd cario tonnog yw'r angen i aros i'r signalau cario ymledu. Beth yw'r oedi sydd ei angen i gael yr allbwn cyflawn o adydd cario tonnog $n$ did, wedi'i fynegi yn nhermau'r oedi ar gyfer adwyon AC, adwyon NEU, a gwrthdroyddion?

Cynrychioli gwifrau

Bydd gwifren yn ein hefelychiad yn wrthrych cyfrifiadurol â dau newidyn cyflwr lleol: signal-value (a gymerir yn 0 i ddechrau) a chasgliad o action-procedures i'w rhedeg pan fydd y signal yn newid ei werth. Gweithredwn y wifren, mewn arddull trosglwyddo negeseuon, fel casgliad o weithdrefnau lleol ynghyd â gweithdrefn dispatch sy'n dethol y gweithrediad lleol priodol, yn union fel y gwnaethom gyda'r gwrthrych cyfrif banc syml yn 3.1.1:

(define (make-wire)
  (let ((signal-value 0) 
        (action-procedures '()))
    (define (set-my-signal! new-value)
      (if (not (= signal-value new-value))
          (begin (set! signal-value new-value)
                 (call-each 
                  action-procedures))
          'done))
    (define (accept-action-procedure! proc)
      (set! action-procedures 
            (cons proc action-procedures))
      (proc))
    (define (dispatch m)
      (cond ((eq? m 'get-signal) 
             signal-value)
            ((eq? m 'set-signal!) 
             set-my-signal!)
            ((eq? m 'add-action!) 
             accept-action-procedure!)
            (else (error "Unknown operation: 
                          WIRE" m))))
    dispatch))

Mae'r weithdrefn leol set-my-signal! yn profi a yw gwerth newydd y signal yn newid y signal ar y wifren. Os felly, mae'n rhedeg pob un o'r gweithdrefnau gweithredu, gan ddefnyddio'r weithdrefn call-each ganlynol, sy'n galw pob un o'r eitemau mewn rhestr o weithdrefnau heb argiau:

(define (call-each procedures)
  (if (null? procedures)
      'done
      (begin ((car procedures))
             (call-each (cdr procedures)))))

Mae'r weithdrefn leol accept-action-procedure! yn ychwanegu'r weithdrefn a roddwyd at y rhestr o weithdrefnau i'w rhedeg, ac yna'n rhedeg y weithdrefn newydd unwaith. (Gweler Ymarfer 3.31.)

Gyda'r weithdrefn leol dispatch wedi'i sefydlu fel y nodwyd, gallwn ddarparu'r gweithdrefnau canlynol i gyrchu'r gweithrediadau lleol ar wifrau:¹⁵⁵

(define (get-signal wire)
  (wire 'get-signal))
(define (set-signal! wire new-value)
  ((wire 'set-signal!) new-value))
(define (add-action! wire action-procedure)
  ((wire 'add-action!) action-procedure))

Mae gwifrau, sydd â signalau sy'n amrywio dros amser ac y gellir eu hatodi at ddyfeisiau'n raddol, yn nodweddiadol o wrthrychau newidiadwy. Rydym wedi'u modelu fel gweithdrefnau â newidynnau cyflwr lleol a addasir drwy aseiniad. Pan grëir gwifren newydd, dyrennir set newydd o newidynnau cyflwr (gan y mynegiad let yn make-wire) ac adeiledir a dychwelir gweithdrefn dispatch newydd, gan ddal yr amgylchedd â'r newidynnau cyflwr newydd.

Rhennir y gwifrau rhwng yr amrywiol ddyfeisiau sydd wedi'u cysylltu â hwy. Felly, bydd newid a wneir drwy ryngweithio ag un ddyfais yn effeithio ar yr holl ddyfeisiau eraill sydd wedi'u hatodi at y wifren. Mae'r wifren yn cyfathrebu'r newid i'w chymdogion drwy alw'r gweithdrefnau gweithredu a roddwyd iddi pan sefydlwyd y cysylltiadau.

Yr agenda

Yr unig beth sydd ei angen i gwblhau'r efelychydd yw after-delay. Y syniad yma yw ein bod yn cadw strwythur data, a elwir yn agenda, sy'n cynnwys amserlen o bethau i'w gwneud. Diffinnir y gweithrediadau canlynol ar gyfer agendâu:

• Mae (make-agenda) yn dychwelyd agenda wag newydd.
• Mae (empty-agenda? ⟨agenda⟩) yn wir os yw'r agenda benodedig yn wag.
• Mae (first-agenda-item ⟨agenda⟩) yn dychwelyd yr eitem gyntaf ar yr agenda.
• Mae (remove-first-agenda-item! ⟨agenda⟩) yn addasu'r agenda drwy dynnu'r eitem gyntaf.
• Mae (add-to-agenda! ⟨time⟩ ⟨action⟩ ⟨agenda⟩) yn addasu'r agenda drwy ychwanegu'r weithdrefn weithredu a roddwyd i'w rhedeg ar yr adeg benodedig.
• Mae (current-time ⟨agenda⟩) yn dychwelyd amser presennol yr efelychiad.

Dynodir yr agenda benodol a ddefnyddiwn gan the-agenda. Mae'r weithdrefn after-delay yn ychwanegu elfennau newydd at the-agenda:

(define (after-delay delay action)
  (add-to-agenda! 
   (+ delay (current-time the-agenda))
   action
   the-agenda))

Gyrrir yr efelychiad gan y weithdrefn propagate, sy'n gweithredu ar the-agenda, gan weithredu pob gweithdrefn ar yr agenda yn ei threfn. Yn gyffredinol, wrth i'r efelychiad redeg, ychwanegir eitemau newydd at yr agenda, a bydd propagate yn parhau â'r efelychiad cyn belled â bod eitemau ar yr agenda:

(define (propagate)
  (if (empty-agenda? the-agenda)
      'done
      (let ((first-item 
             (first-agenda-item the-agenda)))
        (first-item)
        (remove-first-agenda-item! the-agenda)
        (propagate))))

Efelychiad enghreifftiol

Mae'r weithdrefn ganlynol, sy'n gosod “chwiliedydd” ar wifren, yn dangos yr efelychydd ar waith. Mae'r chwiliedydd yn dweud wrth y wifren y dylai, pryd bynnag y mae ei signal yn newid ei werth, argraffu gwerth newydd y signal, ynghyd â'r amser presennol ac enw sy'n adnabod y wifren:

(define (probe name wire)
  (add-action! 
   wire
   (lambda ()
     (newline)
     (display name)
     (display " ")
     (display (current-time the-agenda))
     (display "  New-value = ")
     (display (get-signal wire)))))

Dechreuwn drwy gychwyn yr agenda a phennu cyfnodau oedi ar gyfer y blychau ffwythiant cyntefig:

(define the-agenda (make-agenda))
(define inverter-delay 2)
(define and-gate-delay 3)
(define or-gate-delay 5)

Nawr diffiniwn bedair gwifren, gan osod chwiliedyddion ar ddwy ohonynt:

(define input-1 (make-wire))
(define input-2 (make-wire))
(define sum (make-wire))
(define carry (make-wire))

(probe 'sum sum)
sum 0  New-value = 0

(probe 'carry carry)
carry 0  New-value = 0

Nesaf cysylltwn y gwifrau mewn cylched hanner-adydd (fel yn Ffigur 3.25), gosodwn y signal ar input-1 i 1, a rhedwn yr efelychiad:

(half-adder input-1 input-2 sum carry)
ok

(set-signal! input-1 1)
done

(propagate)
sum 8  New-value = 1
done

Mae'r signal sum yn newid i 1 ar amser 8. Rydym bellach wyth uned amser o ddechrau'r efelychiad. Ar y pwynt hwn, gallwn osod y signal ar input-2 i 1 a gadael i'r gwerthoedd ymledu:

(set-signal! input-2 1)
done

(propagate)
carry 11  New-value = 1
sum 16  New-value = 0
done

Mae'r carry yn newid i 1 ar amser 11 ac mae'r sum yn newid i 0 ar amser 16.

Ymarfer 3.31: Mae'r weithdrefn fewnol accept-action-procedure! a ddiffinnir yn make-wire yn nodi y rhedir gweithdrefn weithredu newydd ar unwaith pan ychwanegir hi at wifren. Esboniwch pam mae angen y cychwyn hwn. Yn benodol, olrheiniwch enghraifft yr hanner-adydd yn y paragraffau uchod a dywedwch sut y byddai ymateb y system yn wahanol pe baem wedi diffinio accept-action-procedure! fel

(define (accept-action-procedure! proc)
  (set! action-procedures 
        (cons proc action-procedures)))

Gweithredu'r agenda

Yn olaf, rhown fanylion strwythur data'r agenda, sy'n dal y gweithdrefnau sydd wedi'u hamserlennu i'w gweithredu yn y dyfodol.

Mae'r agenda'n cynnwys segmentau amser. Mae pob segment amser yn bâr sy'n cynnwys rhif (yr amser) a chiw (gweler Ymarfer 3.32) sy'n dal y gweithdrefnau sydd wedi'u hamserlennu i redeg yn ystod y segment amser hwnnw.

(define (make-time-segment time queue)
  (cons time queue))
(define (segment-time s) (car s))
(define (segment-queue s) (cdr s))

Byddwn yn gweithredu ar giwiau'r segmentau amser gan ddefnyddio'r gweithrediadau ciw a ddisgrifir yn 3.3.2.

Mae'r agenda ei hun yn dabl un dimensiwn o segmentau amser. Mae'n wahanol i'r tablau a ddisgrifir yn 3.3.3 yn yr ystyr y bydd y segmentau wedi'u didoli yn nhrefn amser cynyddol. Yn ogystal, storiwn yr amser presennol (h.y., amser y weithred olaf a broseswyd) ar ben yr agenda. Nid oes segmentau amser mewn agenda sydd newydd ei hadeiladu, ac mae ganddi amser presennol o 0:¹⁵⁶

(define (make-agenda) (list 0))
(define (current-time agenda) (car agenda))
(define (set-current-time! agenda time)
  (set-car! agenda time))
(define (segments agenda) (cdr agenda))
(define (set-segments! agenda segments)
  (set-cdr! agenda segments))
(define (first-segment agenda) 
  (car (segments agenda)))
(define (rest-segments agenda) 
  (cdr (segments agenda)))

Mae agenda'n wag os nad oes ganddi segmentau amser:

(define (empty-agenda? agenda)
  (null? (segments agenda)))

I ychwanegu gweithred at agenda, gwiriwn yn gyntaf a yw'r agenda'n wag. Os ydyw, crëwn segment amser ar gyfer y weithred a gosodwn hwn yn yr agenda. Fel arall, sganiwn yr agenda, gan archwilio amser pob segment. Os canfyddwn segment ar gyfer ein hamser penodedig, ychwanegwn y weithred at y ciw cysylltiedig. Os cyrhaeddwn amser sy'n ddiweddarach na'r un a bennwyd inni, mewnosodwn segment amser newydd yn yr agenda yn union o'i flaen. Os cyrhaeddwn ddiwedd yr agenda, rhaid inni greu segment amser newydd ar y diwedd.

(define (add-to-agenda! time action agenda)
  (define (belongs-before? segments)
    (or (null? segments)
        (< time 
           (segment-time (car segments)))))
  (define (make-new-time-segment time action)
    (let ((q (make-queue)))
      (insert-queue! q action)
      (make-time-segment time q)))
  (define (add-to-segments! segments)
    (if (= (segment-time (car segments)) time)
        (insert-queue! 
         (segment-queue (car segments))
         action)
        (let ((rest (cdr segments)))
          (if (belongs-before? rest)
              (set-cdr!
               segments
               (cons (make-new-time-segment 
                      time 
                      action)
                     (cdr segments)))
              (add-to-segments! rest)))))
  (let ((segments (segments agenda)))
    (if (belongs-before? segments)
        (set-segments!
         agenda
         (cons (make-new-time-segment 
                time 
                action)
               segments))
        (add-to-segments! segments))))

Mae'r weithdrefn sy'n tynnu'r eitem gyntaf o'r agenda yn dileu'r eitem ar flaen y ciw yn y segment amser cyntaf. Os yw'r dileu hwn yn gwneud y segment amser yn wag, tynnwn ef o'r rhestr o segmentau:¹⁵⁷

(define (remove-first-agenda-item! agenda)
  (let ((q (segment-queue 
            (first-segment agenda))))
    (delete-queue! q)
    (if (empty-queue? q)
        (set-segments! 
         agenda 
         (rest-segments agenda)))))

Ceir eitem gyntaf yr agenda ar ben y ciw yn y segment amser cyntaf. Pryd bynnag y tynnwn eitem allan, diweddarwn yr amser presennol hefyd:¹⁵⁸

(define (first-agenda-item agenda)
  (if (empty-agenda? agenda)
      (error "Agenda is empty: 
              FIRST-AGENDA-ITEM")
      (let ((first-seg 
             (first-segment agenda)))
        (set-current-time! 
         agenda 
         (segment-time first-seg))
        (front-queue 
         (segment-queue first-seg)))))

Ymarfer 3.32: Cedwir y gweithdrefnau sydd i'w rhedeg yn ystod pob segment amser o'r agenda mewn ciw. Felly, gelwir gweithdrefnau pob segment yn y drefn y'u hychwanegwyd at yr agenda (cyntaf i mewn, cyntaf allan). Esboniwch pam y mae'n rhaid defnyddio'r drefn hon. Yn benodol, olrheiniwch ymddygiad adwy AC y mae ei mewnbynnau'n newid o 0, 1 i 1, 0 yn yr un segment, a dywedwch sut y byddai'r ymddygiad yn wahanol pe baem yn storio gweithdrefnau segment mewn rhestr gyffredin, gan ychwanegu a thynnu gweithdrefnau ar y blaen yn unig (olaf i mewn, cyntaf allan).

3.3.5Lledaenu Cyfyngiadau

Yn draddodiadol, trefnir rhaglenni cyfrifiadurol yn gyfrifiadau uncyfeiriadol, sy'n cyflawni gweithrediadau ar argiau a bennwyd ymlaen llaw i gynhyrchu'r allbynnau a ddymunir. Ar y llaw arall, rydym yn aml yn modelu systemau yn nhermau perthnasoedd rhwng meintiau. Er enghraifft, gallai model mathemategol o strwythur mecanyddol gynnwys y wybodaeth bod gwyriad $d$ gwialen fetel yn gysylltiedig â'r grym $F$ ar y wialen, hyd $L$ y wialen, arwynebedd y trawstoriad $A$, a'r modwlws elastig $E$ drwy'r hafaliad $$dAE=FL.$$ Nid yw hafaliad o'r fath yn uncyfeiriadol. O gael unrhyw bedwar o'r meintiau, gallwn ei ddefnyddio i gyfrifo'r pumed. Eto i gyd, byddai trosi'r hafaliad yn iaith gyfrifiadurol draddodiadol yn ein gorfodi i ddewis un o'r meintiau i'w gyfrifo yn nhermau'r pedwar arall. Felly, ni ellid defnyddio gweithdrefn ar gyfer cyfrifo'r arwynebedd $A$ i gyfrifo'r gwyriad $d$, er bod cyfrifiadau $A$ ac $d$ yn deillio o'r un hafaliad.¹⁵⁹

Yn yr adran hon, amlinellwn ddyluniad iaith sy'n ein galluogi i weithio yn nhermau'r perthnasoedd eu hunain. Elfennau cyntefig yr iaith yw cyfyngiadau cyntefig, sy'n datgan bod rhai perthnasoedd yn bodoli rhwng meintiau. Er enghraifft, mae (adder a b c) yn nodi bod rhaid i'r meintiau $a$, $b$, ac $c$ fod yn gysylltiedig drwy'r hafaliad $a+b=c$, mae (multiplier x y z) yn mynegi'r cyfyngiad $xy=z$, ac mae (constant 3.14 x) yn dweud bod rhaid i werth $x$ fod yn 3.14.

Mae ein hiaith yn darparu modd o gyfuno cyfyngiadau cyntefig er mwyn mynegi perthnasoedd mwy cymhleth. Cyfunwn gyfyngiadau drwy adeiladu rhwydweithiau cyfyngiadau, lle cysylltir cyfyngiadau gan gysylltyddion. Gwrthrych yw cysylltydd sy'n “dal” gwerth a all gymryd rhan mewn un neu ragor o gyfyngiadau. Er enghraifft, gwyddom mai'r berthynas rhwng tymereddau Fahrenheit a Celsius yw $$9C=5(F-<!--\; -\; -->32).$$ Gellir ystyried cyfyngiad o'r fath yn rhwydwaith sy'n cynnwys cyfyngiadau adydd, lluosydd, a chysonyn cyntefig (Ffigur 3.28). Yn y ffigur, gwelwn ar y chwith flwch lluosydd â thair terfynell, wedi'u labelu $m1$, $m2$, ac $p$. Mae'r rhain yn cysylltu'r lluosydd â gweddill y rhwydwaith fel a ganlyn: Mae'r derfynell $m1$ wedi'i chysylltu â chysylltydd $C$, a fydd yn dal tymheredd Celsius. Mae'r derfynell $m2$ wedi'i chysylltu â chysylltydd $w$, sydd hefyd wedi'i gysylltu â blwch cysonyn sy'n dal 9. Mae'r derfynell $p$, y mae'r blwch lluosydd yn ei chyfyngu i fod yn lluoswm $m1$ ac $m2$, wedi'i chysylltu â therfynell $p$ blwch lluosydd arall, y mae ei $m2$ wedi'i gysylltu â chysonyn 5 a'i $m1$ wedi'i gysylltu ag un o dermau swm.

Mae cyfrifiannu gan rwydwaith o'r fath yn mynd rhagddo fel a ganlyn: Pan roddir gwerth i gysylltydd (gan y defnyddiwr neu gan flwch cyfyngiad y mae wedi'i gysylltu ag ef), mae'n deffro ei holl gyfyngiadau cysylltiedig (ac eithrio'r cyfyngiad sydd newydd ei ddeffro) i roi gwybod iddynt fod ganddo werth. Yna mae pob blwch cyfyngiad a ddeffrowyd yn holi ei gysylltyddion i weld a oes digon o wybodaeth i bennu gwerth i gysylltydd. Os oes, mae'r blwch yn gosod y cysylltydd hwnnw, sydd wedyn yn deffro ei holl gyfyngiadau cysylltiedig, ac yn y blaen. Er enghraifft, wrth drosi rhwng Celsius a Fahrenheit, gosodir $w$, $x$, ac $y$ ar unwaith gan y blychau cysonyn i 9, 5, a 32, yn y drefn honno. Mae'r cysylltyddion yn deffro'r lluosyddion a'r adydd, sy'n pennu nad oes digon o wybodaeth i fynd yn eu blaen. Os yw'r defnyddiwr (neu ryw ran arall o'r rhwydwaith) yn gosod $C$ i werth (dyweder 25), deffroir y lluosydd pellaf i'r chwith, a bydd yn gosod $u$ i $25\cdot <!--\; \cdot \; -->9=225$. Yna mae $u$ yn deffro'r ail luosydd, sy'n gosod $v$ i 45, ac mae $v$ yn deffro'r adydd, sy'n gosod $F$ i 77.

Defnyddio'r system gyfyngiadau

I ddefnyddio'r system gyfyngiadau i gyflawni'r cyfrifiad tymheredd a amlinellir uchod, crëwn yn gyntaf ddau gysylltydd, C ac F, drwy alw'r adeiladydd make-connector, a chysylltwn C ac F mewn rhwydwaith priodol:

(define C (make-connector))
(define F (make-connector))
(celsius-fahrenheit-converter C F)
ok

Diffinnir y weithdrefn sy'n creu'r rhwydwaith fel a ganlyn:

(define (celsius-fahrenheit-converter c f)
  (let ((u (make-connector))
        (v (make-connector))
        (w (make-connector))
        (x (make-connector))
        (y (make-connector)))
    (multiplier c w u)
    (multiplier v x u)
    (adder v y f)
    (constant 9 w)
    (constant 5 x)
    (constant 32 y)
    'ok))

Mae'r weithdrefn hon yn creu'r cysylltyddion mewnol u, v, w, x, ac y, ac yn eu cysylltu fel y dangosir yn Ffigur 3.28 gan ddefnyddio'r adeiladwyr cyfyngiadau cyntefig adder, multiplier, ac constant. Yn union fel gydag efelychydd cylchedau digidol 3.3.4, mae mynegi'r cyfuniadau hyn o elfennau cyntefig yn nhermau gweithdrefnau yn rhoi modd i'n hiaith haniaethu gwrthrychau cyfansawdd yn awtomatig.

I wylio'r rhwydwaith ar waith, gallwn osod chwiliedyddion ar y cysylltyddion C ac F, gan ddefnyddio gweithdrefn probe sy'n debyg i'r un a ddefnyddiasom i fonitro gwifrau yn 3.3.4. Bydd gosod chwiliedydd ar gysylltydd yn peri i neges gael ei hargraffu pryd bynnag y rhoddir gwerth i'r cysylltydd:

(probe "Celsius temp" C)
(probe "Fahrenheit temp" F)

Nesaf gosodwn werth C i 25. (Mae'r trydydd arg i set-value! yn dweud wrth C fod y cyfarwyddyd hwn yn dod oddi wrth yr user.)

(set-value! C 25 'user)
Probe: Celsius temp = 25
Probe: Fahrenheit temp = 77
done

Mae'r chwiliedydd ar C yn deffro ac yn adrodd y gwerth. Mae C hefyd yn lledaenu ei werth drwy'r rhwydwaith fel y disgrifiwyd uchod. Mae hyn yn gosod F i 77, a chaiff hynny ei adrodd gan y chwiliedydd ar F.

Nawr gallwn geisio gosod F i werth newydd, dyweder 212:

(set-value! F 212 'user)
Error! Contradiction (77 212)

Mae'r cysylltydd yn cwyno ei fod wedi canfod gwrthddywediad: Ei werth yw 77, ac mae rhywun yn ceisio ei osod i 212. Os ydym wir am ailddefnyddio'r rhwydwaith â gwerthoedd newydd, gallwn ddweud wrth C am anghofio ei hen werth:

(forget-value! C 'user)
Probe: Celsius temp = ?
Probe: Fahrenheit temp = ?
done

Mae C yn canfod bod yr user, a osododd ei werth yn wreiddiol, bellach yn tynnu'r gwerth hwnnw'n ôl, felly mae C yn cytuno i golli ei werth, fel y dangosir gan y chwiliedydd, ac yn hysbysu gweddill y rhwydwaith o'r ffaith hon. Yn y pen draw mae'r wybodaeth hon yn ymledu i F, sydd bellach yn canfod nad oes ganddo reswm dros barhau i gredu mai 77 yw ei werth ei hun. Felly, mae F hefyd yn ildio ei werth, fel y dangosir gan y chwiliedydd.

Nawr nad oes gan F werth, gallwn ei osod i 212:

(set-value! F 212 'user)
Probe: Fahrenheit temp = 212
Probe: Celsius temp = 100
done

Mae'r gwerth newydd hwn, o'i ledaenu drwy'r rhwydwaith, yn gorfodi C i gael gwerth 100, a chofnodir hyn gan y chwiliedydd ar C. Sylwch fod yr union un rhwydwaith yn cael ei ddefnyddio i gyfrifo C o gael F ac i gyfrifo F o gael C. Y ffaith hon nad oes gan gyfrifiannu gyfeiriad penodol yw nodwedd arbennig systemau sy'n seiliedig ar gyfyngiadau.

Gweithredu'r system gyfyngiadau

Gweithredir y system gyfyngiadau drwy wrthrychau gweithdrefnol â chyflwr lleol, mewn ffordd debyg iawn i efelychydd cylchedau digidol 3.3.4. Er bod gwrthrychau cyntefig y system gyfyngiadau ychydig yn fwy cymhleth, mae'r system gyffredinol yn symlach, gan nad oes angen poeni am agendâu nac oedi rhesymeg.

Dyma'r gweithrediadau sylfaenol ar gysylltyddion:

• Mae (has-value? ⟨connector⟩) yn dweud a oes gan y cysylltydd werth.
• Mae (get-value ⟨connector⟩) yn dychwelyd gwerth presennol y cysylltydd.
• Mae (set-value! ⟨connector⟩ ⟨new-value⟩ ⟨informant⟩) yn dynodi bod yr hysbysydd yn gofyn i'r cysylltydd osod ei werth i'r gwerth newydd.
• Mae (forget-value! ⟨connector⟩ ⟨retractor⟩) yn dweud wrth y cysylltydd fod y sawl sy'n tynnu'n ôl yn gofyn iddo anghofio ei werth.
• Mae (connect ⟨connector⟩ ⟨new-constraint⟩) yn dweud wrth y cysylltydd am gymryd rhan yn y cyfyngiad newydd.

Mae'r cysylltyddion yn cyfathrebu â'r cyfyngiadau drwy'r gweithdrefnau inform-about-value, sy'n dweud wrth y cyfyngiad a roddwyd fod gan y cysylltydd werth, ac inform-about-no-value, sy'n dweud wrth y cyfyngiad fod y cysylltydd wedi colli ei werth.

Mae Adder yn adeiladu cyfyngiad adydd rhwng cysylltyddion adendau a1 ac a2 a chysylltydd sum. Gweithredir adydd fel gweithdrefn â chyflwr lleol (y weithdrefn me isod):

(define (adder a1 a2 sum)
  (define (process-new-value)
    (cond ((and (has-value? a1) 
                (has-value? a2))
           (set-value! sum
                       (+ (get-value a1) 
                          (get-value a2))
                       me))
          ((and (has-value? a1) 
                (has-value? sum))
           (set-value! a2
                       (- (get-value sum) 
                          (get-value a1))
                       me))
          ((and (has-value? a2) 
                (has-value? sum))
           (set-value! a1
                       (- (get-value sum) 
                          (get-value a2))
                       me))))
  (define (process-forget-value)
    (forget-value! sum me)
    (forget-value! a1 me)
    (forget-value! a2 me)
    (process-new-value))
  (define (me request)
    (cond ((eq? request 'I-have-a-value)
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else (error "Unknown request: 
                        ADDER" request))))
  (connect a1 me)
  (connect a2 me)
  (connect sum me)
  me)

Mae Adder yn cysylltu'r adydd newydd â'r cysylltyddion penodedig ac yn ei ddychwelyd yn werth iddo. Mae'r weithdrefn me, sy'n cynrychioli'r adydd, yn dethol ymhlith y gweithdrefnau lleol. Defnyddir y “rhyngwynebau cystrawen” canlynol (gweler Troednodyn 155 yn 3.3.4) ar y cyd â'r detholwr hwn:

(define (inform-about-value constraint)
  (constraint 'I-have-a-value))
(define (inform-about-no-value constraint)
  (constraint 'I-lost-my-value))

Gelwir gweithdrefn leol yr adydd, process-new-value, pan hysbysir yr adydd fod gan un o'i gysylltyddion werth. Yn gyntaf mae'r adydd yn gwirio a oes gan a1 ac a2 ill dau werthoedd. Os oes, mae'n dweud wrth sum am osod ei werth i swm y ddau adend. Yr arg informant i set-value! yw me, sef gwrthrych yr adydd ei hun. Os nad oes gan a1 ac a2 ill dau werthoedd, yna mae'r adydd yn gwirio a oes gan a1 ac sum werthoedd efallai. Os oes, mae'n gosod a2 i wahaniaeth y ddau hyn. Yn olaf, os oes gan a2 ac sum werthoedd, mae hyn yn rhoi digon o wybodaeth i'r adydd osod a1. Os dywedir wrth yr adydd fod un o'i gysylltyddion wedi colli gwerth, mae'n gofyn i'w holl gysylltyddion golli eu gwerthoedd bellach. (Dim ond y gwerthoedd a osodwyd gan yr adydd hwn a gollir mewn gwirionedd.) Yna mae'n rhedeg process-new-value. Y rheswm dros y cam olaf hwn yw y gall un neu ragor o gysylltyddion ddal i gael gwerth (hynny yw, gallai cysylltydd fod wedi cael gwerth na chafodd ei osod yn wreiddiol gan yr adydd), ac efallai fod angen lledaenu'r gwerthoedd hyn yn ôl drwy'r adydd.

Mae lluosydd yn debyg iawn i adydd. Bydd yn gosod ei product i 0 os yw'r naill ffactor neu'r llall yn 0, hyd yn oed os nad yw'r ffactor arall yn hysbys.

(define (multiplier m1 m2 product)
  (define (process-new-value)
    (cond ((or (and (has-value? m1) 
                    (= (get-value m1) 0))
               (and (has-value? m2) 
                    (= (get-value m2) 0)))
           (set-value! product 0 me))
          ((and (has-value? m1) 
                (has-value? m2))
           (set-value! product
                       (* (get-value m1) 
                          (get-value m2))
                       me))
          ((and (has-value? product) 
                (has-value? m1))
           (set-value! m2
                       (/ (get-value product) 
                          (get-value m1))
                       me))
          ((and (has-value? product) 
                (has-value? m2))
           (set-value! m1
                       (/ (get-value product) 
                          (get-value m2))
                       me))))
  (define (process-forget-value)
    (forget-value! product me)
    (forget-value! m1 me)
    (forget-value! m2 me)
    (process-new-value))
  (define (me request)
    (cond ((eq? request 'I-have-a-value)
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else
           (error "Unknown request: 
                   MULTIPLIER" 
                  request))))
  (connect m1 me)
  (connect m2 me)
  (connect product me)
  me)

Dim ond gosod gwerth y cysylltydd penodedig a wna adeiladydd constant. Bydd unrhyw neges I-have-a-value neu I-lost-my-value a anfonir at y blwch cysonyn yn cynhyrchu gwall.

(define (constant value connector)
  (define (me request)
    (error "Unknown request: CONSTANT" 
           request))
  (connect connector me)
  (set-value! connector value me)
  me)

Yn olaf, mae chwiliedydd yn argraffu neges am osod neu ddad-osod y cysylltydd penodedig:

(define (probe name connector)
  (define (print-probe value)
    (newline) (display "Probe: ")
    (display name) (display " = ")
    (display value))
  (define (process-new-value)
    (print-probe (get-value connector)))
  (define (process-forget-value)
    (print-probe "?"))
  (define (me request)
    (cond ((eq? request 'I-have-a-value)
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else (error "Unknown request: 
                        PROBE" request))))
  (connect connector me)
  me)

Cynrychioli cysylltyddion

Cynrychiolir cysylltydd yn wrthrych gweithdrefnol â newidynnau cyflwr lleol value, gwerth presennol y cysylltydd; informant, y gwrthrych a osododd werth y cysylltydd; ac constraints, rhestr o'r cyfyngiadau y mae'r cysylltydd yn cymryd rhan ynddynt.

(define (make-connector)
  (let ((value false) 
        (informant false) 
        (constraints '()))
    (define (set-my-value newval setter)
      (cond ((not (has-value? me))
             (set! value newval)
             (set! informant setter)
             (for-each-except 
              setter
              inform-about-value
              constraints))
            ((not (= value newval))
             (error "Contradiction" 
                    (list value newval)))
            (else 'ignored)))
    (define (forget-my-value retractor)
      (if (eq? retractor informant)
          (begin (set! informant false)
                 (for-each-except 
                  retractor
                  inform-about-no-value
                  constraints))
          'ignored))
    (define (connect new-constraint)
      (if (not (memq new-constraint 
                     constraints))
          (set! constraints
                (cons new-constraint 
                      constraints)))
      (if (has-value? me)
          (inform-about-value new-constraint))
      'done)
    (define (me request)
      (cond ((eq? request 'has-value?)
             (if informant true false))
            ((eq? request 'value) value)
            ((eq? request 'set-value!) 
             set-my-value)
            ((eq? request 'forget) 
             forget-my-value)
            ((eq? request 'connect) connect)
            (else (error "Unknown operation: 
                          CONNECTOR"
                         request))))
    me))

Gelwir gweithdrefn leol y cysylltydd, set-my-value, pan geir cais i osod gwerth y cysylltydd. Os nad oes gan y cysylltydd werth ar hyn o bryd, bydd yn gosod ei werth ac yn cofio fel informant y cyfyngiad a ofynnodd am osod y gwerth.¹⁶⁰ Yna bydd y cysylltydd yn hysbysu'r holl gyfyngiadau y mae'n cymryd rhan ynddynt ac eithrio'r cyfyngiad a ofynnodd am osod y gwerth. Cyflawnir hyn gan ddefnyddio'r iterwr canlynol, sy'n cymhwyso gweithdrefn benodedig i'r holl eitemau mewn rhestr ac eithrio un a roddwyd:

(define (for-each-except exception 
                         procedure 
                         list)
  (define (loop items)
    (cond ((null? items) 'done)
          ((eq? (car items) exception) 
           (loop (cdr items)))
          (else (procedure (car items))
                (loop (cdr items)))))
  (loop list))

Os gofynnir i gysylltydd anghofio ei werth, mae'n rhedeg y weithdrefn leol forget-my-value, sy'n gwirio'n gyntaf fod y cais yn dod o'r un gwrthrych a osododd y gwerth yn wreiddiol. Os ydyw, mae'r cysylltydd yn hysbysu ei gyfyngiadau cysylltiedig fod y gwerth wedi'i golli.

Mae'r weithdrefn leol connect yn ychwanegu'r cyfyngiad newydd penodedig at y rhestr o gyfyngiadau os nad yw eisoes yn y rhestr honno. Yna, os oes gan y cysylltydd werth, mae'n hysbysu'r cyfyngiad newydd o'r ffaith hon.

Mae gweithdrefn me y cysylltydd yn dethol ymhlith y gweithdrefnau mewnol eraill ac hefyd yn cynrychioli'r cysylltydd yn wrthrych. Mae'r gweithdrefnau canlynol yn darparu rhyngwyneb cystrawen ar gyfer y detholwr:

(define (has-value? connector)
  (connector 'has-value?))
(define (get-value connector)
  (connector 'value))
(define (set-value! connector 
                    new-value 
                    informant)
  ((connector 'set-value!) 
   new-value 
   informant))
(define (forget-value! connector retractor)
  ((connector 'forget) retractor))
(define (connect connector new-constraint)
  ((connector 'connect) new-constraint))

Ymarfer 3.33: Gan ddefnyddio cyfyngiadau lluosydd, adydd, a chysonyn cyntefig, diffiniwch weithdrefn averager sy'n cymryd tri chysylltydd a, b, ac c yn fewnbynnau ac yn sefydlu'r cyfyngiad mai cyfartaledd gwerthoedd a ac b yw gwerth c.

Ymarfer 3.34: Mae Louis Reasoner am adeiladu sgwariwr, dyfais gyfyngiad â dwy derfynell fel y bydd gwerth y cysylltydd b ar yr ail derfynell bob amser yn sgwâr y gwerth a ar y derfynell gyntaf. Mae'n cynnig y ddyfais syml ganlynol wedi'i gwneud o luosydd:

(define (squarer a b) (multiplier a a b))

Mae diffyg difrifol yn y syniad hwn. Esboniwch.

Ymarfer 3.35: Mae Ben Bitdiddle yn dweud wrth Louis mai un ffordd o osgoi'r drafferth yn Ymarfer 3.34 yw diffinio sgwariwr yn gyfyngiad cyntefig newydd. Llenwch y rhannau coll yn amlinelliad Ben o weithdrefn i weithredu cyfyngiad o'r fath:

(define (squarer a b)
  (define (process-new-value)
    (if (has-value? b)
        (if (< (get-value b) 0)
            (error "square less than 0: 
                    SQUARER" 
                   (get-value b))
            ⟨alternative1⟩)
        ⟨alternative2⟩))
  (define (process-forget-value) ⟨body1⟩)
  (define (me request) ⟨body2⟩)
  ⟨rest of definition⟩
  me)

Ymarfer 3.36: Tybiwch ein bod yn gwerthuso'r dilyniant canlynol o fynegiadau yn yr amgylchedd byd-eang:

(define a (make-connector))
(define b (make-connector))
(set-value! a 10 'user)

Ar ryw adeg wrth werthuso set-value!, gwerthusir y mynegiad canlynol o weithdrefn leol y cysylltydd:

(for-each-except 
  setter inform-about-value constraints)

Tynnwch ddiagram amgylchedd sy'n dangos yr amgylchedd y gwerthusir y mynegiad uchod ynddo.

Ymarfer 3.37: Mae'r weithdrefn celsius-fahrenheit-converter yn feichus o'i chymharu ag arddull ddiffinio sy'n canolbwyntio'n fwy ar fynegiadau, megis

(define (celsius-fahrenheit-converter x)
  (c+ (c* (c/ (cv 9) (cv 5))
          x)
      (cv 32)))

(define C (make-connector))
(define F (celsius-fahrenheit-converter C))

Yma c+, c*, ac ati yw'r fersiynau “cyfyngiad” o'r gweithrediadau rhifyddol. Er enghraifft, mae c+ yn cymryd dau gysylltydd yn argiau ac yn dychwelyd cysylltydd sy'n gysylltiedig â'r rhain drwy gyfyngiad adydd:

(define (c+ x y)
  (let ((z (make-connector)))
    (adder x y z)
    z))

Diffiniwch weithdrefnau cyfatebol c-, c*, c/, ac cv (gwerth cyson) sy'n ein galluogi i ddiffinio cyfyngiadau cyfansawdd fel yn enghraifft y trawsnewidydd uchod.¹⁶¹

(v-sum a b temp1)
(v-sum c d temp2)
(v-prod temp1 temp2 answer)

(define answer 
  (v-prod (v-sum a b) (v-sum c d)))