2.1 Cyflwyniad i Haniaethu Data

Yn 1.1.8, nodasom y gellid ystyried gweithdrefn a ddefnyddir fel elfen wrth greu gweithdrefn fwy cymhleth nid yn unig yn gasgliad o weithrediadau penodol ond hefyd yn haniaeth weithdrefnol. Hynny yw, gellid cuddio manylion sut y gweithredwyd y weithdrefn, a gellid disodli’r weithdrefn benodol ei hun gan unrhyw weithdrefn arall â’r un ymddygiad cyffredinol. Mewn geiriau eraill, gallem greu haniaeth a fyddai’n gwahanu’r ffordd y defnyddid y weithdrefn oddi wrth fanylion sut y gweithredid y weithdrefn yn nhermau gweithdrefnau mwy cyntefig. Gelwir y syniad cyfatebol ar gyfer data cyfansawdd yn haniaethu data. Methodoleg yw haniaethu data sy’n ein galluogi i ynysu sut y defnyddir gwrthrych data cyfansawdd oddi wrth fanylion sut y’i hadeiladir o wrthrychau data mwy cyntefig.

Syniad sylfaenol haniaethu data yw strwythuro’r rhaglenni sydd i ddefnyddio gwrthrychau data cyfansawdd fel eu bod yn gweithredu ar “ddata haniaethol.” Hynny yw, dylai ein rhaglenni ddefnyddio data mewn ffordd nad yw’n gwneud unrhyw dybiaethau am y data nad ydynt yn gwbl angenrheidiol i gyflawni’r dasg dan sylw. Ar yr un pryd, diffinnir cynrychioliad data “diriaethol” yn annibynnol ar y rhaglenni sy’n defnyddio’r data. Y rhyngwyneb rhwng y ddwy ran hyn o’n system fydd set o weithdrefnau, o’r enw detholwyr ac adeiladwyr, sy’n gweithredu’r data haniaethol yn nhermau’r cynrychioliad diriaethol. I ddangos y dechneg hon, byddwn yn ystyried sut i ddylunio set o weithdrefnau ar gyfer trin rhifau cymarebol.

2.1.1Enghraifft: Gweithrediadau Rhifyddol ar gyfer Rhifau Cymarebol

Tybiwch ein bod eisiau cyflawni rhifyddeg â rhifau cymarebol. Rydym eisiau gallu eu hadio, eu tynnu, eu lluosi, a’u rhannu, a phrofi a yw dau rif cymarebol yn hafal.

Dechreuwn drwy dybio bod gennym eisoes ffordd o adeiladu rhif cymarebol o rifiadur ac enwadur. Tybiwn hefyd fod gennym, o gael rhif cymarebol, ffordd o echdynnu (neu ddethol) ei rifiadur a’i enwadur. Tybiwn ymhellach fod yr adeiladydd a’r detholwyr ar gael fel gweithdrefnau:

• Mae (make-rat ⟨n⟩ ⟨d⟩) yn dychwelyd y rhif cymarebol y mae ei rifiadur yn gyfanrif ⟨n⟩ a’i enwadur yn gyfanrif ⟨d⟩.
• Mae (numer ⟨x⟩) yn dychwelyd rhifiadur y rhif cymarebol ⟨x⟩.
• Mae (denom ⟨x⟩) yn dychwelyd enwadur y rhif cymarebol ⟨x⟩.

Rydym yma’n defnyddio strategaeth rymus ar gyfer syntheseiddio: meddwl dymunol. Nid ydym eto wedi dweud sut y cynrychiolir rhif cymarebol, na sut y dylid gweithredu’r gweithdrefnau numer, denom, ac make-rat. Er hynny, pe bai’r tair gweithdrefn hyn gennym, gallem wedyn adio, tynnu, lluosi, rhannu, a phrofi hafaledd drwy ddefnyddio’r perthnasoedd canlynol: $$\begin{array}{rcl}\frac{n_1}{d_1}+\frac{n_2}{d_2}& =& \frac{n_1{d}_2+n_2{d}_1}{d_1{d}_2},\\ \frac{n_1}{d_1}-<!--\; -\; -->\frac{n_2}{d_2}& =& \frac{n_1{d}_2-<!--\; -\; -->n_2{d}_1}{d_1{d}_2},\\ \frac{n_1}{d_1}\times <!--\; \times \; -->\frac{n_2}{d_2}& =& \frac{n_1{n}_2}{d_1{d}_2},\\ \frac{n_1/d_1}{n_2/d_2}& =& \frac{n_1{d}_2}{d_1{n}_2},\\ \frac{n_1}{d_1}& =& \frac{n_2}{d_2}\mathrm{i}\mathrm{f}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{n}\mathrm{l}\mathrm{y}\mathrm{i}\mathrm{f}{n}_1{d}_2=n_2{d}_1.\end{array}$$ Gallwn fynegi’r rheolau hyn fel gweithdrefnau:

(define (add-rat x y)
  (make-rat (+ (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

(define (sub-rat x y)
  (make-rat (- (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

(define (mul-rat x y)
  (make-rat (* (numer x) (numer y))
            (* (denom x) (denom y))))

(define (div-rat x y)
  (make-rat (* (numer x) (denom y))
            (* (denom x) (numer y))))

(define (equal-rat? x y)
  (= (* (numer x) (denom y))
     (* (numer y) (denom x))))

Bellach mae gennym y gweithrediadau ar rifau cymarebol wedi’u diffinio yn nhermau’r gweithdrefnau dethol ac adeiladu numer, denom, ac make-rat. Ond nid ydym eto wedi diffinio’r rhain. Yr hyn sydd ei angen yw rhyw ffordd o ludo ynghyd rifiadur ac enwadur i ffurfio rhif cymarebol.

Parau

Er mwyn ein galluogi i weithredu lefel ddiriaethol ein haniaethu data, mae ein hiaith yn darparu strwythur cyfansawdd o’r enw pâr, y gellir ei adeiladu â’r weithdrefn gyntefig cons. Mae’r weithdrefn hon yn cymryd dau arg ac yn dychwelyd gwrthrych data cyfansawdd sy’n cynnwys y ddau arg fel rhannau. O gael pâr, gallwn echdynnu’r rhannau drwy ddefnyddio’r gweithdrefnau cyntefig car ac cdr.⁶⁸ Felly, gallwn ddefnyddio cons, car, ac cdr fel a ganlyn:

(define x (cons 1 2))

(car x)
1

(cdr x)
2

Sylwch fod pâr yn wrthrych data y gellir rhoi enw iddo a’i drin, yn union fel gwrthrych data cyntefig. At hynny, gellir defnyddio cons i ffurfio parau y mae eu helfennau’n barau, ac yn y blaen:

(define x (cons 1 2))
(define y (cons 3 4))
(define z (cons x y))

(car (car z))
1

(car (cdr z))
3

Yn 2.2 gwelwn sut mae’r gallu hwn i gyfuno parau yn golygu y gellir defnyddio parau fel blociau adeiladu cyffredinol i greu pob math o strwythurau data cymhleth. Yr un cyntefigyn data cyfansawdd pâr, a weithredir gan y gweithdrefnau cons, car, ac cdr, yw’r unig lud sydd ei angen arnom. Gelwir gwrthrychau data a adeiladir o barau yn ddata â strwythur rhestr.

Cynrychioli rhifau cymarebol

Mae parau’n cynnig ffordd naturiol o gwblhau’r system rhifau cymarebol. Yn syml, cynrychiolwch rif cymarebol fel pâr o ddau gyfanrif: rhifiadur ac enwadur. Yna mae’n hawdd gweithredu make-rat, numer, ac denom fel a ganlyn:⁶⁹

(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))

Hefyd, er mwyn dangos canlyniadau ein cyfrifiadau, gallwn argraffu rhifau cymarebol drwy argraffu’r rhifiadur, slaes, a’r enwadur:⁷⁰

(define (print-rat x)
  (newline)
  (display (numer x))
  (display "/")
  (display (denom x)))

Gallwn yn awr roi cynnig ar ein gweithdrefnau rhifau cymarebol:

(define one-half (make-rat 1 2))
(print-rat one-half)
1/2

(define one-third (make-rat 1 3))
(print-rat
 (add-rat one-half one-third))
5/6

(print-rat
 (mul-rat one-half one-third))
1/6

(print-rat
 (add-rat one-third one-third))
6/9

Fel y dengys yr enghraifft olaf, nid yw ein gweithrediad rhifau cymarebol yn lleihau rhifau cymarebol i’w termau isaf. Gallwn unioni hyn drwy newid make-rat. Os oes gennym weithdrefn gcd fel yr un yn 1.2.5 sy’n cynhyrchu rhannydd cyffredin mwyaf dau gyfanrif, gallwn ddefnyddio gcd i leihau’r rhifiadur a’r enwadur i’w termau isaf cyn adeiladu’r pâr:

(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g) 
          (/ d g))))

Bellach mae gennym

(print-rat 
 (add-rat one-third one-third))
2/3

fel y dymunwyd. Cyflawnwyd yr addasiad hwn drwy newid yr adeiladydd make-rat heb newid unrhyw un o’r gweithdrefnau (megis add-rat ac mul-rat) sy’n gweithredu’r gweithrediadau eu hunain.

Ymarfer 2.1: Diffiniwch fersiwn well o make-rat sy’n trin argiau positif a negatif. Dylai Make-rat normaleiddio’r arwydd fel bod y rhifiadur a’r enwadur ill dau’n bositif os yw’r rhif cymarebol yn bositif, a dim ond y rhifiadur sy’n negatif os yw’r rhif cymarebol yn negatif.

2.1.2Rhwystrau Haniaethu

Cyn parhau â rhagor o enghreifftiau o ddata cyfansawdd a haniaethu data, gadewch inni ystyried rhai o’r materion a godwyd gan yr enghraifft rhifau cymarebol. Diffiniasom y gweithrediadau rhifau cymarebol yn nhermau adeiladydd make-rat a detholwyr numer ac denom. Yn gyffredinol, y syniad sy’n sail i haniaethu data yw adnabod, ar gyfer pob math o wrthrych data, set sylfaenol o weithrediadau y mynegir pob triniaeth o wrthrychau data o’r math hwnnw yn eu termau, ac yna defnyddio’r gweithrediadau hynny’n unig i drin y data.

Gallwn ddychmygu strwythur y system rhifau cymarebol fel y’i dangosir yn Ffigur 2.1. Mae’r llinellau llorweddol yn cynrychioli rhwystrau haniaethu sy’n ynysu gwahanol “lefelau” y system. Ar bob lefel, mae’r rhwystr yn gwahanu’r rhaglenni (uwchlaw) sy’n defnyddio’r haniaeth data oddi wrth y rhaglenni (islaw) sy’n gweithredu’r haniaeth data. Mae rhaglenni sy’n defnyddio rhifau cymarebol yn eu trin yn nhermau’r gweithdrefnau a gyflenwir “at ddefnydd cyhoeddus” gan y pecyn rhifau cymarebol yn unig: add-rat, sub-rat, mul-rat, div-rat, ac equal-rat?. Gweithredir y rhain, yn eu tro, yn nhermau’r adeiladydd a’r detholwyr make-rat, numer, ac denom yn unig, a weithredir eu hunain yn nhermau parau. Mae manylion sut y gweithredir parau yn amherthnasol i weddill y pecyn rhifau cymarebol cyn belled ag y gellir trin parau drwy ddefnyddio cons, car, ac cdr. I bob pwrpas, y gweithdrefnau ar bob lefel yw’r rhyngwynebau sy’n diffinio’r rhwystrau haniaethu ac yn cysylltu’r gwahanol lefelau.

Mae gan y syniad syml hwn lawer o fanteision. Un fantais yw ei fod yn gwneud rhaglenni’n llawer haws eu cynnal a’u haddasu. Gellir cynrychioli unrhyw strwythur data cymhleth mewn amryw ffyrdd â’r strwythurau data cyntefig a ddarperir gan iaith raglennu. Wrth gwrs, mae’r dewis o gynrychioliad yn dylanwadu ar y rhaglenni sy’n gweithredu arno; felly, pe bai’r cynrychioliad yn cael ei newid rywbryd yn ddiweddarach, efallai y byddai’n rhaid addasu pob rhaglen o’r fath yn unol â hynny. Gallai’r dasg hon gymryd llawer o amser a bod yn ddrud yn achos rhaglenni mawr, oni bai fod y ddibyniaeth ar y cynrychioliad wedi’i chyfyngu drwy ddyluniad i ychydig iawn o fodiwlau rhaglen.

Er enghraifft, ffordd arall o fynd i’r afael â’r broblem o leihau rhifau cymarebol i’w termau isaf yw cyflawni’r lleihau bob tro y cyrchwn rannau rhif cymarebol, yn hytrach na phan adeiladwn ef. Mae hyn yn arwain at weithdrefnau adeiladu a dethol gwahanol:

(define (make-rat n d)
  (cons n d))

(define (numer x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (car x) g)))

(define (denom x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (cdr x) g)))

Mae’r gwahaniaeth rhwng y gweithrediad hwn a’r un blaenorol yn gorwedd yn yr adeg y cyfrifwn yr gcd. Os ydym, yn ein defnydd arferol o rifau cymarebol, yn cyrchu rhifiaduron ac enwaduron yr un rhifau cymarebol lawer gwaith, byddai’n well cyfrifo’r gcd pan adeiladir y rhifau cymarebol. Os nad felly, efallai y byddai’n well aros tan yr adeg cyrchu i gyfrifo’r gcd. Beth bynnag, pan newidiwn o un cynrychioliad i’r llall, nid oes rhaid addasu’r gweithdrefnau add-rat, sub-rat, ac yn y blaen o gwbl.

Mae cyfyngu’r ddibyniaeth ar y cynrychioliad i ychydig o weithdrefnau rhyngwyneb yn ein helpu i ddylunio rhaglenni yn ogystal â’u haddasu, oherwydd mae’n caniatáu inni gadw’r hyblygrwydd i ystyried gweithrediadau amgen. I barhau â’n henghraifft syml, tybiwch ein bod yn dylunio pecyn rhifau cymarebol ac na allwn benderfynu ar y dechrau a ddylem gyflawni’r gcd wrth adeiladu neu wrth ddethol. Mae methodoleg haniaethu data yn rhoi ffordd inni ohirio’r penderfyniad hwnnw heb golli’r gallu i wneud cynnydd ar weddill y system.

Ymarfer 2.2: Ystyriwch y broblem o gynrychioli segmentau llinell mewn plân. Cynrychiolir pob segment fel pâr o bwyntiau: pwynt dechrau a phwynt gorffen. Diffiniwch adeiladydd make-segment a detholwyr start-segment ac end-segment sy’n diffinio cynrychioliad segmentau yn nhermau pwyntiau. Ymhellach, gellir cynrychioli pwynt fel pâr o rifau: y cyfesuryn $x$ a’r cyfesuryn $y$. Yn unol â hynny, pennwch adeiladydd make-point a detholwyr x-point ac y-point sy’n diffinio’r cynrychioliad hwn. Yn olaf, gan ddefnyddio eich detholwyr a’ch adeiladwyr, diffiniwch weithdrefn midpoint-segment sy’n cymryd segment llinell fel arg ac yn dychwelyd ei ganolbwynt (y pwynt y mae ei gyfesurynnau’n gyfartaledd cyfesurynnau’r pwyntiau terfyn). I roi cynnig ar eich gweithdrefnau, bydd angen ffordd arnoch o argraffu pwyntiau:

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

Ymarfer 2.3: Gweithredwch gynrychioliad ar gyfer petryalau mewn plân. (Awgrym: Efallai yr hoffech ddefnyddio Ymarfer 2.2.) Yn nhermau eich adeiladwyr a’ch detholwyr, crëwch weithdrefnau sy’n cyfrifo perimedr ac arwynebedd petryal penodol. Nawr gweithredwch gynrychioliad gwahanol ar gyfer petryalau. A allwch ddylunio eich system â rhwystrau haniaethu addas, fel y bydd yr un gweithdrefnau perimedr ac arwynebedd yn gweithio gyda’r naill gynrychioliad neu’r llall?

2.1.3Beth a Olygir gan Ddata?

Dechreuasom weithredu rhifau cymarebol yn 2.1.1 drwy weithredu’r gweithrediadau rhifau cymarebol add-rat, sub-rat, ac yn y blaen yn nhermau tair gweithdrefn amhenodol: make-rat, numer, ac denom. Ar y pwynt hwnnw, gallem ystyried y gweithrediadau yn rhai wedi’u diffinio yn nhermau gwrthrychau data—rhifiaduron, enwaduron, a rhifau cymarebol—yr oedd eu hymddygiad wedi’i bennu gan y tair gweithdrefn olaf.

Ond beth yn union a olygir gan ddata? Nid yw’n ddigon dweud “beth bynnag a weithredir gan y detholwyr a’r adeiladwyr a roddwyd.” Yn amlwg, ni all pob set fympwyol o dair gweithdrefn wasanaethu fel sail briodol ar gyfer gweithredu rhifau cymarebol. Rhaid inni warantu, os adeiladwn rif cymarebol x o bâr o gyfanrifau n ac d, y dylai echdynnu numer ac denom o x a’u rhannu roi’r un canlyniad â rhannu n ag d. Mewn geiriau eraill, rhaid i make-rat, numer, ac denom fodloni’r amod bod, ar gyfer unrhyw gyfanrif n ac unrhyw gyfanrif ansero d, os mai (make-rat n d) yw x, yna $$\frac{\text{(numer x)}}{\text{(denom x)}}=\frac{\text{n}}{\text{d}}.$$ Mewn gwirionedd, dyma’r unig amod y mae’n rhaid i make-rat, numer, ac denom ei fodloni er mwyn ffurfio sail addas ar gyfer cynrychioliad rhifau cymarebol. Yn gyffredinol, gallwn ystyried data yn rhai wedi’u diffinio gan ryw gasgliad o ddetholwyr ac adeiladwyr, ynghyd ag amodau penodedig y mae’n rhaid i’r gweithdrefnau hyn eu bodloni er mwyn bod yn gynrychioliad dilys.⁷¹

Gall y safbwynt hwn wasanaethu i ddiffinio nid yn unig gwrthrychau data “lefel uchel,” megis rhifau cymarebol, ond gwrthrychau lefel is hefyd. Ystyriwch y syniad o bâr, a ddefnyddiasom i ddiffinio ein rhifau cymarebol. Ni ddywedasom erioed beth oedd pâr mewn gwirionedd, dim ond bod yr iaith yn darparu gweithdrefnau cons, car, ac cdr i weithredu ar barau. Ond yr unig beth sydd angen inni ei wybod am y tri gweithrediad hyn yw, os gludwn ddau wrthrych ynghyd drwy ddefnyddio cons, y gallwn adfer y gwrthrychau drwy ddefnyddio car ac cdr. Hynny yw, mae’r gweithrediadau’n bodloni’r amod, ar gyfer unrhyw wrthrychau x ac y, os mai (cons x y) yw z, yna x yw (car z) ac y yw (cdr z). Yn wir, soniasom fod y tair gweithdrefn hyn wedi’u cynnwys fel gweithdrefnau cyntefig yn ein hiaith. Fodd bynnag, gellir defnyddio unrhyw driawd o weithdrefnau sy’n bodloni’r amod uchod fel sail ar gyfer gweithredu parau. Dangosir y pwynt hwn yn drawiadol gan y ffaith y gallem weithredu cons, car, ac cdr heb ddefnyddio unrhyw strwythurau data o gwbl, ond gan ddefnyddio gweithdrefnau’n unig. Dyma’r diffiniadau:

(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
          ((= m 1) y)
          (else 
           (error "Argument not 0 or 1:
                   CONS" m))))
  dispatch)

(define (car z) (z 0))
(define (cdr z) (z 1))

Nid yw’r defnydd hwn o weithdrefnau yn cyfateb i ddim byd tebyg i’n syniad greddfol o beth y dylai data fod. Serch hynny, y cyfan sydd angen inni ei wneud i ddangos bod hon yn ffordd ddilys o gynrychioli parau yw gwirio bod y gweithdrefnau hyn yn bodloni’r amod a roddwyd uchod.

Y pwynt cynnil i sylwi arno yw mai gweithdrefn yw’r gwerth a ddychwelir gan (cons x y)—sef y weithdrefn dispatch a ddiffiniwyd yn fewnol, sy’n cymryd un arg ac yn dychwelyd naill ai x neu y yn dibynnu ar a yw’r arg yn 0 neu’n 1. Yn gyfatebol, diffinnir (car z) i gymhwyso z i 0. Felly, os mai z yw’r weithdrefn a ffurfiwyd gan (cons x y), yna bydd cymhwyso z i 0 yn rhoi x. Felly, dangoswyd bod (car (cons x y)) yn rhoi x, fel y dymunwyd. Yn yr un modd, mae (cdr (cons x y)) yn cymhwyso’r weithdrefn a ddychwelir gan (cons x y) i 1, ac mae hon yn dychwelyd y. Felly, mae’r gweithrediad gweithdrefnol hwn o barau yn weithrediad dilys, ac os cyrchwn barau drwy ddefnyddio cons, car, ac cdr yn unig, ni allwn wahaniaethu rhwng y gweithrediad hwn ac un sy’n defnyddio strwythurau data “go iawn.”

Pwrpas dangos cynrychioliad gweithdrefnol parau yw nid bod ein hiaith yn gweithio fel hyn (mae Scheme, a systemau Lisp yn gyffredinol, yn gweithredu parau’n uniongyrchol er mwyn effeithlonrwydd), ond y gallai weithio fel hyn. Er bod y cynrychioliad gweithdrefnol yn aneglur, mae’n ffordd gwbl ddigonol o gynrychioli parau, gan ei fod yn bodloni’r unig amodau y mae angen i barau eu bodloni. Mae’r enghraifft hon hefyd yn dangos bod y gallu i drin gweithdrefnau fel gwrthrychau yn darparu’r gallu i gynrychioli data cyfansawdd yn awtomatig. Efallai fod hyn yn ymddangos yn odrwydd ar hyn o bryd, ond bydd cynrychioliadau gweithdrefnol o ddata yn chwarae rôl ganolog yn ein casgliad o dechnegau rhaglennu. Gelwir yr arddull raglennu hon yn aml yn drosglwyddo negeseuon, a byddwn yn ei defnyddio fel offeryn sylfaenol ym Mhennod 3 pan awn i’r afael â materion modelu ac efelychu.

Ymarfer 2.4: Dyma gynrychioliad gweithdrefnol amgen o barau. Ar gyfer y cynrychioliad hwn, gwiriwch fod (car (cons x y)) yn rhoi x ar gyfer unrhyw wrthrychau x ac y.

(define (cons x y) 
  (lambda (m) (m x y)))

(define (car z) 
  (z (lambda (p q) p)))

Beth yw’r diffiniad cyfatebol o cdr? (Awgrym: I wirio bod hyn yn gweithio, defnyddiwch fodel amnewid 1.1.5.)

Ymarfer 2.5: Dangoswch y gallwn gynrychioli parau o gyfanrifau annegyddol drwy ddefnyddio rhifau a gweithrediadau rhifyddol yn unig os cynrychiolwn y pâr $a$ ac $b$ fel y cyfanrif sy’n lluoswm $2^a{3}^b$. Rhowch y diffiniadau cyfatebol o’r gweithdrefnau cons, car, ac cdr.

Ymarfer 2.6: Rhag ofn nad oedd cynrychioli parau fel gweithdrefnau yn ddigon i beri penbleth, ystyriwch y gallwn, mewn iaith sy’n gallu trin gweithdrefnau, wneud heb rifau (o leiaf o ran cyfanrifau annegyddol) drwy weithredu 0 a’r gweithrediad o adio 1 fel

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

Gelwir y cynrychioliad hwn yn rifolion Church, ar ôl ei ddyfeisiwr, Alonzo Church, y rhesymegydd a ddyfeisiodd y calcwlws λ.

Diffiniwch one ac two yn uniongyrchol (nid yn nhermau zero ac add-1). (Awgrym: Defnyddiwch amnewid i werthuso (add-1 zero)). Rhowch ddiffiniad uniongyrchol o’r weithdrefn adio + (nid yn nhermau cymhwyso add-1 dro ar ôl tro).

2.1.4Ymarfer Estynedig: Rhifyddeg Cyfyngau

Mae Alyssa P. Hacker yn dylunio system i helpu pobl i ddatrys problemau peirianneg. Un nodwedd y mae hi eisiau ei darparu yn ei system yw’r gallu i drin meintiau anfanwl (megis paramedrau mesuredig dyfeisiau ffisegol) â thrachywiredd hysbys, fel y bydd y canlyniadau’n rhifau â thrachywiredd hysbys pan wneir cyfrifiadau â meintiau brasamcanol o’r fath.

Bydd peirianwyr trydanol yn defnyddio system Alyssa i gyfrifo meintiau trydanol. Weithiau mae angen iddynt gyfrifo gwerth gwrthiant cyfwerth paralel $R_p$ dau wrthydd $R_1$ ac $R_2$ drwy ddefnyddio’r fformiwla $$R_p=\frac{1}{1/R_1+1/R_2}.$$ Fel arfer dim ond o fewn rhyw oddefiant a warentir gan wneuthurwr y gwrthydd y mae gwerthoedd gwrthiant yn hysbys. Er enghraifft, os prynwch wrthydd wedi’i labelu “6.8 ohm â goddefiant 10%,” dim ond bod gwrthiant y gwrthydd rhwng 6.8 $-<!--\; -\; -->$ 0.68 = 6.12 a 6.8 + 0.68 = 7.48 ohm y gallwch fod yn sicr ohono. Felly, os oes gennych wrthydd 6.8-ohm 10% yn baralel â gwrthydd 4.7-ohm 5%, gall gwrthiant y cyfuniad amrywio o tua 2.58 ohm (os yw’r ddau wrthydd ar y terfynau isaf) i tua 2.97 ohm (os yw’r ddau wrthydd ar y terfynau uchaf).

Syniad Alyssa yw gweithredu “rhifyddeg cyfyngau” fel set o weithrediadau rhifyddol ar gyfer cyfuno “cyfyngau” (gwrthrychau sy’n cynrychioli ystod gwerthoedd posibl maint anfanwl). Mae canlyniad adio, tynnu, lluosi, neu rannu dau gyfwng ei hun yn gyfwng, sy’n cynrychioli ystod y canlyniad.

Mae Alyssa yn rhagdybio bod gwrthrych haniaethol o’r enw “cyfwng” yn bodoli sydd â dau bwynt terfyn: terfyn isaf a therfyn uchaf. Mae hi hefyd yn tybio y gall, o gael pwyntiau terfyn cyfwng, adeiladu’r cyfwng drwy ddefnyddio’r adeiladydd data make-interval. Yn gyntaf mae Alyssa yn ysgrifennu gweithdrefn ar gyfer adio dau gyfwng. Mae hi’n rhesymu mai swm y ddau derfyn isaf yw gwerth lleiaf posibl y swm, a swm y ddau derfyn uchaf yw ei werth mwyaf posibl:

(define (add-interval x y)
  (make-interval (+ (lower-bound x) 
                    (lower-bound y))
                 (+ (upper-bound x) 
                    (upper-bound y))))

Mae Alyssa hefyd yn cyfrifo lluoswm dau gyfwng drwy ganfod y lleiafswm a’r mwyafswm o luosymiau’r terfynau a’u defnyddio fel terfynau’r cyfwng canlyniadol. (Mae Min ac max yn weithdrefnau cyntefig sy’n canfod lleiafswm neu fwyafswm unrhyw nifer o argiau.)

(define (mul-interval x y)
  (let ((p1 (* (lower-bound x) 
               (lower-bound y)))
        (p2 (* (lower-bound x) 
               (upper-bound y)))
        (p3 (* (upper-bound x) 
               (lower-bound y)))
        (p4 (* (upper-bound x) 
               (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))

I rannu dau gyfwng, mae Alyssa yn lluosi’r cyntaf â chilydd yr ail. Sylwch mai cilydd y terfyn uchaf a chilydd y terfyn isaf, yn y drefn honno, yw terfynau’r cyfwng cilyddol.

(define (div-interval x y)
  (mul-interval x 
                (make-interval 
                 (/ 1.0 (upper-bound y)) 
                 (/ 1.0 (lower-bound y)))))

Ymarfer 2.7: Mae rhaglen Alyssa yn anghyflawn oherwydd nad yw wedi pennu gweithrediad yr haniaeth cyfwng. Dyma ddiffiniad o adeiladydd y cyfwng:

(define (make-interval a b) (cons a b))

Diffiniwch ddetholwyr upper-bound ac lower-bound i gwblhau’r gweithrediad.

Ymarfer 2.8: Gan ddefnyddio rhesymu tebyg i un Alyssa, disgrifiwch sut y gellir cyfrifo gwahaniaeth dau gyfwng. Diffiniwch weithdrefn dynnu gyfatebol, o’r enw sub-interval.

Ymarfer 2.9: Mae lled cyfwng yn hanner y gwahaniaeth rhwng ei derfynau uchaf ac isaf. Mae’r lled yn fesur o ansicrwydd y rhif a bennir gan y cyfwng. Ar gyfer rhai gweithrediadau rhifyddol, mae lled canlyniad cyfuno dau gyfwng yn ffwythiant o ledau’r cyfyngau arg yn unig, ond ar gyfer eraill nid yw lled y cyfuniad yn ffwythiant o ledau’r cyfyngau arg. Dangoswch fod lled swm (neu wahaniaeth) dau gyfwng yn ffwythiant o ledau’r cyfyngau sy’n cael eu hadio (neu eu tynnu) yn unig. Rhowch enghreifftiau i ddangos nad yw hyn yn wir ar gyfer lluosi na rhannu.

Ymarfer 2.10: Mae Ben Bitdiddle, rhaglennydd systemau medrus, yn edrych dros ysgwydd Alyssa ac yn dweud nad yw’n glir beth mae’n ei olygu i rannu â chyfwng sy’n rhychwantu sero. Addaswch god Alyssa i wirio am yr amod hwn ac i roi arwydd o wall os yw’n digwydd.

Ymarfer 2.11: Wrth fynd heibio, mae Ben hefyd yn gwneud sylw enigmatig: “Drwy brofi arwyddion pwyntiau terfyn y cyfyngau, mae’n bosibl rhannu mul-interval yn naw achos, a dim ond un ohonynt sydd angen mwy na dau luosiad.” Ailysgrifennwch y weithdrefn hon gan ddefnyddio awgrym Ben.

Ar ôl dadfygio ei rhaglen, mae Alyssa yn ei dangos i ddarpar ddefnyddiwr, sy’n cwyno bod ei rhaglen yn datrys y broblem anghywir. Mae ef eisiau rhaglen a all ymdrin â rhifau a gynrychiolir fel gwerth canol a goddefiant adiol; er enghraifft, mae eisiau gweithio â chyfyngau megis 3.5 $\pm <!--\; \pm \; -->$ 0.15 yn hytrach na [3.35, 3.65]. Mae Alyssa yn dychwelyd at ei desg ac yn unioni’r broblem hon drwy ddarparu adeiladydd amgen a detholwyr amgen:

(define (make-center-width c w)
  (make-interval (- c w) (+ c w)))

(define (center i)
  (/ (+ (lower-bound i) 
        (upper-bound i)) 
     2))

(define (width i)
  (/ (- (upper-bound i) 
        (lower-bound i)) 
     2))

Yn anffodus, peirianwyr yw’r rhan fwyaf o ddefnyddwyr Alyssa. Fel arfer mae sefyllfaoedd peirianneg go iawn yn cynnwys mesuriadau ag ansicrwydd bach yn unig, wedi’i fesur fel cymhareb lled y cyfwng i ganolbwynt y cyfwng. Mae peirianwyr fel arfer yn pennu goddefiannau canrannol ar baramedrau dyfeisiau, fel yn y manylebau gwrthyddion a roddwyd yn gynharach.

Ymarfer 2.12: Diffiniwch adeiladydd make-center-percent sy’n cymryd canol a goddefiant canrannol ac yn cynhyrchu’r cyfwng dymunol. Rhaid i chi hefyd ddiffinio detholwr percent sy’n cynhyrchu’r goddefiant canrannol ar gyfer cyfwng penodol. Mae’r detholwr center yr un fath â’r un a ddangosir uchod.

Ymarfer 2.13: Dangoswch, o dan y dybiaeth o oddefiannau canrannol bach, fod fformiwla syml ar gyfer goddefiant canrannol brasamcanol lluoswm dau gyfwng yn nhermau goddefiannau’r ffactorau. Gallwch symleiddio’r broblem drwy dybio bod pob rhif yn bositif.

Ar ôl cryn waith, mae Alyssa P. Hacker yn cyflwyno ei system orffenedig. Sawl blwyddyn yn ddiweddarach, ar ôl iddi anghofio amdani’n llwyr, mae’n cael galwad wyllt gan ddefnyddiwr cynddeiriog, Lem E. Tweakit. Mae’n ymddangos bod Lem wedi sylwi y gellir ysgrifennu’r fformiwla ar gyfer gwrthyddion paralel mewn dwy ffordd sy’n gyfwerth yn algebraidd: $$\frac{R_1{R}_2}{R_1+R_2}$$ ac $$\frac{1}{1/R_1+1/R_2}.$$ Mae wedi ysgrifennu’r ddwy raglen ganlynol, pob un yn cyfrifo’r fformiwla gwrthyddion paralel yn wahanol:

(define (par1 r1 r2)
  (div-interval 
   (mul-interval r1 r2)
   (add-interval r1 r2)))

(define (par2 r1 r2)
  (let ((one (make-interval 1 1)))
    (div-interval 
     one
     (add-interval 
      (div-interval one r1) 
      (div-interval one r2)))))

Mae Lem yn cwyno bod rhaglen Alyssa yn rhoi atebion gwahanol ar gyfer y ddwy ffordd o gyfrifo. Mae hon yn gŵyn ddifrifol.

Ymarfer 2.14: Dangoswch fod Lem yn iawn. Ymchwiliwch i ymddygiad y system ar amrywiaeth o fynegiadau rhifyddol. Crëwch rai cyfyngau $A$ ac $B$, a’u defnyddio i gyfrifo’r mynegiadau $A/A$ ac $A/B$. Cewch y ddealltwriaeth fwyaf drwy ddefnyddio cyfyngau y mae eu lled yn ganran fach o’r gwerth canol. Archwiliwch ganlyniadau’r cyfrifiad ar ffurf canol-canran (gweler Ymarfer 2.12).

Ymarfer 2.15: Mae Eva Lu Ator, defnyddiwr arall, hefyd wedi sylwi ar y cyfyngau gwahanol a gyfrifir gan fynegiadau gwahanol ond cyfwerth yn algebraidd. Mae hi’n dweud y bydd fformiwla ar gyfer cyfrifo â chyfyngau gan ddefnyddio system Alyssa yn cynhyrchu terfynau gwall tynnach os gellir ei hysgrifennu ar ffurf lle nad yw unrhyw newidyn sy’n cynrychioli rhif ansicr yn cael ei ailadrodd. Felly, meddai, mae par2 yn rhaglen “well” ar gyfer gwrthiannau paralel nag par1. A yw hi’n iawn? Pam?

Ymarfer 2.16: Esboniwch, yn gyffredinol, pam y gall mynegiadau algebraidd cyfwerth arwain at atebion gwahanol. A allwch ddyfeisio pecyn rhifyddeg cyfyngau nad oes ganddo’r diffyg hwn, neu a yw’r dasg hon yn amhosibl? (Rhybudd: Mae’r broblem hon yn anodd iawn.)

(define make-rat cons)
(define numer car)
(define denom cdr)