SICP · Yr ail argraffiad · Scheme

2.4 Cynrychioliadau Lluosog ar gyfer Data Haniaethol

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

Rydym wedi cyflwyno haniaethu data, methodoleg ar gyfer strwythuro systemau fel y gellir pennu llawer o raglen yn annibynnol ar y dewisiadau ynghylch gweithredu’r gwrthrychau data y mae’r rhaglen yn eu trin. Er enghraifft, gwelsom yn 2.1.1 sut i wahanu’r dasg o ddylunio rhaglen sy’n defnyddio rhifau cymarebol oddi wrth y dasg o weithredu rhifau cymarebol yn nhermau mecanweithiau cyntefig yr iaith gyfrifiadurol ar gyfer adeiladu data cyfansawdd. Y syniad allweddol oedd codi rhwystr haniaethu—yn yr achos hwn, y detholwyr a’r adeiladyddion ar gyfer rhifau cymarebol (make-rat, numer, denom)—sy’n ynysu’r ffordd y defnyddir rhifau cymarebol oddi wrth eu cynrychioliad sylfaenol yn nhermau strwythur rhestrau. Mae rhwystr haniaethu tebyg yn ynysu manylion y gweithdrefnau sy’n cyflawni rhifyddeg gymarebol (add-rat, sub-rat, mul-rat, ac div-rat) oddi wrth y gweithdrefnau “lefel uwch” sy’n defnyddio rhifau cymarebol. Mae gan y rhaglen sy’n deillio o hyn y strwythur a ddangosir yn Ffigur 2.1.

Mae’r rhwystrau haniaethu data hyn yn arfau pwerus ar gyfer rheoli cymhlethdod. Drwy ynysu cynrychioliadau sylfaenol gwrthrychau data, gallwn rannu’r dasg o ddylunio rhaglen fawr yn dasgau llai y gellir eu cyflawni ar wahân. Ond nid yw’r math hwn o haniaethu data’n ddigon pwerus eto, oherwydd efallai na fydd bob amser yn gwneud synnwyr sôn am “y cynrychioliad sylfaenol” ar gyfer gwrthrych data.

Yn un peth, gallai fod mwy nag un cynrychioliad defnyddiol ar gyfer gwrthrych data, ac efallai yr hoffem ddylunio systemau sy’n gallu ymdrin â chynrychioliadau lluosog. I gymryd enghraifft syml, gellir cynrychioli rhifau cymhlyg mewn dwy ffordd sydd bron yn gyfwerth: ar ffurf betryalog (rhannau real a dychmygol) ac ar ffurf begynol (maint ac ongl). Weithiau mae’r ffurf betryalog yn fwy priodol ac weithiau mae’r ffurf begynol yn fwy priodol. Yn wir, mae’n gwbl gredadwy dychmygu system lle cynrychiolir rhifau cymhlyg yn y ddwy ffordd, a lle mae’r gweithdrefnau ar gyfer trin rhifau cymhlyg yn gweithio gyda’r naill gynrychioliad neu’r llall.

Yn bwysicach, mae systemau rhaglennu’n aml yn cael eu dylunio gan lawer o bobl sy’n gweithio dros gyfnodau hir, yn ddarostyngedig i ofynion sy’n newid dros amser. Mewn amgylchedd o’r fath, nid yw’n bosibl i bawb gytuno ymlaen llaw ar ddewisiadau cynrychioli data. Felly, yn ogystal â’r rhwystrau haniaethu data sy’n ynysu cynrychioliad oddi wrth ddefnydd, mae angen rhwystrau haniaethu sy’n ynysu dewisiadau dylunio gwahanol oddi wrth ei gilydd ac yn caniatáu i ddewisiadau gwahanol gydfodoli mewn un rhaglen. Ymhellach, gan fod rhaglenni mawr yn aml yn cael eu creu drwy gyfuno modiwlau sydd eisoes yn bodoli ac a ddyluniwyd ar wahân, mae angen confensiynau sy’n caniatáu i raglenwyr gynnwys modiwlau mewn systemau mwy drwy ychwanegu, hynny yw, heb orfod ailddylunio nac ailweithredu’r modiwlau hyn.

Yn yr adran hon, byddwn yn dysgu sut i ymdopi â data a all gael ei gynrychioli mewn gwahanol ffyrdd gan wahanol rannau o raglen. Mae hyn yn gofyn am adeiladu gweithdrefnau generig—gweithdrefnau sy’n gallu gweithredu ar ddata a all gael ei gynrychioli mewn mwy nag un ffordd. Ein prif dechneg ar gyfer adeiladu gweithdrefnau generig fydd gweithio yn nhermau gwrthrychau data sydd â thagiau math, hynny yw, gwrthrychau data sy’n cynnwys gwybodaeth benodol am sut y dylid eu prosesu. Byddwn hefyd yn trafod rhaglennu a gyfarwyddir gan ddata, strategaeth weithredu bwerus a chyfleus ar gyfer cydosod systemau drwy ychwanegu gweithrediadau generig.

Dechreuwn â’r enghraifft syml o rifau cymhlyg. Gwelwn sut mae tagiau math a dull a gyfarwyddir gan ddata yn ein galluogi i ddylunio cynrychioliadau petryalog a phegynol ar wahân ar gyfer rhifau cymhlyg, gan gynnal y syniad o wrthrych data haniaethol “rhif cymhlyg.” Cyflawnwn hyn drwy ddiffinio gweithdrefnau rhifyddol ar gyfer rhifau cymhlyg (add-complex, sub-complex, mul-complex, ac div-complex) yn nhermau detholwyr generig sy’n cyrchu rhannau o rif cymhlyg yn annibynnol ar sut y cynrychiolir y rhif. Mae’r system rhifau cymhlyg sy’n deillio o hyn, fel y’i dangosir yn Ffigur 2.19, yn cynnwys dau fath gwahanol o rwystrau haniaethu. Mae’r rhwystrau haniaethu “llorweddol” yn chwarae’r un rôl â’r rhai yn Ffigur 2.1. Maent yn ynysu gweithrediadau “lefel uwch” oddi wrth gynrychioliadau “lefel is.” Yn ogystal, mae rhwystr “fertigol” sy’n rhoi’r gallu inni ddylunio a gosod cynrychioliadau amgen ar wahân.

Ffigur 2.19: Rhwystrau haniaethu data yn y system rhifau cymhlyg.

Yn 2.5 byddwn yn dangos sut i ddefnyddio tagiau math a dull a gyfarwyddir gan ddata i ddatblygu pecyn rhifyddeg generig. Mae hwn yn darparu gweithdrefnau (add, mul, ac ati) y gellir eu defnyddio i drin pob math o “rifau” ac y gellir eu hymestyn yn hawdd pan fydd angen math newydd o rif. Yn 2.5.3, byddwn yn dangos sut i ddefnyddio rhifyddeg generig mewn system sy’n cyflawni algebra symbolaidd.

2.4.1Cynrychioliadau ar gyfer Rhifau Cymhlyg

Byddwn yn datblygu system sy’n cyflawni gweithrediadau rhifyddol ar rifau cymhlyg fel enghraifft syml ond afrealistig o raglen sy’n defnyddio gweithrediadau generig. Dechreuwn drwy drafod dau gynrychioliad credadwy ar gyfer rhifau cymhlyg fel parau trefnedig: ffurf betryalog (rhan real a rhan ddychmygol) a ffurf begynol (maint ac ongl).¹⁰⁹ Bydd Adran 2.4.2 yn dangos sut y gellir peri i’r ddau gynrychioliad gydfodoli mewn un system drwy ddefnyddio tagiau math a gweithrediadau generig.

Fel rhifau cymarebol, cynrychiolir rhifau cymhlyg yn naturiol fel parau trefnedig. Gellir meddwl am y set o rifau cymhlyg fel gofod dau ddimensiwn â dwy echelin orthogonal, yr echelin “real” a’r echelin “ddychmygol.” (Gweler Ffigur 2.20.) O’r safbwynt hwn, gellir meddwl am y rhif cymhlyg $z = x + i y$ (lle mae $i^{2} = −1$ ) fel y pwynt yn y plân sydd â chyfesuryn real $x$ a chyfesuryn dychmygol $y$ . Mae adio rhifau cymhlyg yn y cynrychioliad hwn yn lleihau i adio cyfesurynnau: $\begin{array}{rcl} Real-part (z_{1} + z_{2}) & = & Real-part (z_{1}) + \\ Real-part (z_{2}), \\ Imaginary-part (z_{1} + z_{2}) & = & Imaginary-part (z_{1}) + \\ Imaginary-part (z_{2}) . \end{array}$

Ffigur 2.20: Rhifau cymhlyg fel pwyntiau yn y plân.

Wrth luosi rhifau cymhlyg, mae’n fwy naturiol meddwl yn nhermau cynrychioli rhif cymhlyg ar ffurf begynol, fel maint ac ongl ( $r$ ac $A$ yn Ffigur 2.20). Lluoswm dau rif cymhlyg yw’r fector a geir drwy ymestyn un rhif cymhlyg yn ôl hyd y llall ac yna ei gylchdroi drwy ongl y llall: $\begin{array}{rcl} Magnitude (z_{1} \cdot z_{2}) & = & Magnitude (z_{1}) \cdot Magnitude (z_{2}), \\ Angle (z_{1} \cdot z_{2}) & = & Angle (z_{1}) + Angle (z_{2}) . \end{array}$

Felly, mae dau gynrychioliad gwahanol ar gyfer rhifau cymhlyg, sy’n briodol ar gyfer gwahanol weithrediadau. Eto i gyd, o safbwynt rhywun sy’n ysgrifennu rhaglen sy’n defnyddio rhifau cymhlyg, mae egwyddor haniaethu data’n awgrymu y dylai’r holl weithrediadau ar gyfer trin rhifau cymhlyg fod ar gael pa gynrychioliad bynnag a ddefnyddir gan y cyfrifiadur. Er enghraifft, mae’n aml yn ddefnyddiol gallu canfod maint rhif cymhlyg a bennir gan gyfesurynnau petryalog. Yn yr un modd, mae’n aml yn ddefnyddiol gallu pennu rhan real rhif cymhlyg a bennir gan gyfesurynnau pegynol.

I ddylunio system o’r fath, gallwn ddilyn yr un strategaeth haniaethu data ag a ddilynasom wrth ddylunio’r pecyn rhifau cymarebol yn 2.1.1. Tybiwch fod y gweithrediadau ar rifau cymhlyg wedi’u gweithredu yn nhermau pedwar detholwr: real-part, imag-part, magnitude, ac angle. Tybiwch hefyd fod gennym ddwy weithdrefn ar gyfer adeiladu rhifau cymhlyg: mae make-from-real-imag yn dychwelyd rhif cymhlyg â rhannau real a dychmygol penodedig, ac mae make-from-mag-ang yn dychwelyd rhif cymhlyg â maint ac ongl penodedig. Mae gan y gweithdrefnau hyn y briodwedd, ar gyfer unrhyw rif cymhlyg z, fod

(make-from-real-imag (real-part z) 
                     (imag-part z))

(make-from-mag-ang (magnitude z) 
                   (angle z))

ill dau’n cynhyrchu rhifau cymhlyg sy’n hafal i z.

Gan ddefnyddio’r adeiladyddion a’r detholwyr hyn, gallwn weithredu rhifyddeg ar rifau cymhlyg gan ddefnyddio’r “data haniaethol” a bennir gan yr adeiladyddion a’r detholwyr, yn union fel y gwnaethom ar gyfer rhifau cymarebol yn 2.1.1. Fel y dangosir yn y fformiwlâu uchod, gallwn adio a thynnu rhifau cymhlyg yn nhermau rhannau real a dychmygol, a lluosi a rhannu rhifau cymhlyg yn nhermau meintiau ac onglau:

(define (add-complex z1 z2)
  (make-from-real-imag 
   (+ (real-part z1) (real-part z2))
   (+ (imag-part z1) (imag-part z2))))

(define (sub-complex z1 z2)
  (make-from-real-imag 
   (- (real-part z1) (real-part z2))
   (- (imag-part z1) (imag-part z2))))

(define (mul-complex z1 z2)
  (make-from-mag-ang 
   (* (magnitude z1) (magnitude z2))
   (+ (angle z1) (angle z2))))

(define (div-complex z1 z2)
  (make-from-mag-ang 
   (/ (magnitude z1) (magnitude z2))
   (- (angle z1) (angle z2))))

I gwblhau’r pecyn rhifau cymhlyg, rhaid inni ddewis cynrychioliad a gweithredu’r adeiladyddion a’r detholwyr yn nhermau rhifau cyntefig a strwythur rhestrau cyntefig. Mae dwy ffordd amlwg o wneud hyn: Gallwn gynrychioli rhif cymhlyg ar “ffurf betryalog” fel pâr (rhan real, rhan ddychmygol) neu ar “ffurf begynol” fel pâr (maint, ongl). Pa un a ddewiswn?

Er mwyn gwneud y dewisiadau gwahanol yn bendant, dychmygwch fod dau raglennydd, Ben Bitdiddle ac Alyssa P. Hacker, yn dylunio cynrychioliadau ar gyfer y system rhifau cymhlyg yn annibynnol. Mae Ben yn dewis cynrychioli rhifau cymhlyg ar ffurf betryalog. Gyda’r dewis hwn, mae dethol rhannau real a dychmygol rhif cymhlyg yn syml, fel y mae adeiladu rhif cymhlyg â rhannau real a dychmygol penodol. I ganfod y maint a’r ongl, neu i adeiladu rhif cymhlyg â maint ac ongl penodol, mae’n defnyddio’r perthnasoedd trigonometrig

\begin{array}{rcl} x & = & r \cos A, \\ y & = & r \sin A, \\ r & = & \sqrt{x^{2} + y^{2},} \\ A & = & \arctan (y, x), \end{array}

sy’n cysylltu’r rhannau real a dychmygol $(x, y)$ â’r maint a’r ongl $(r, A)$ .¹¹⁰ Felly rhoddir cynrychioliad Ben gan y detholwyr a’r adeiladyddion canlynol:

(define (real-part z) (car z))
(define (imag-part z) (cdr z))

(define (magnitude z)
  (sqrt (+ (square (real-part z)) 
           (square (imag-part z)))))

(define (angle z)
  (atan (imag-part z) (real-part z)))

(define (make-from-real-imag x y) 
  (cons x y))

(define (make-from-mag-ang r a)
  (cons (* r (cos a)) (* r (sin a))))

Mae Alyssa, ar y llaw arall, yn dewis cynrychioli rhifau cymhlyg ar ffurf begynol. Iddi hi, mae dethol y maint a’r ongl yn syml, ond mae rhaid iddi ddefnyddio’r perthnasoedd trigonometrig i gael y rhannau real a dychmygol. Dyma gynrychioliad Alyssa:

(define (real-part z)
  (* (magnitude z) (cos (angle z))))

(define (imag-part z)
  (* (magnitude z) (sin (angle z))))

(define (magnitude z) (car z))
(define (angle z) (cdr z))

(define (make-from-real-imag x y)
  (cons (sqrt (+ (square x) (square y)))
        (atan y x)))

(define (make-from-mag-ang r a) 
  (cons r a))

Mae disgyblaeth haniaethu data’n sicrhau y bydd yr un gweithrediad o add-complex, sub-complex, mul-complex, ac div-complex yn gweithio gyda naill ai gynrychioliad Ben neu gynrychioliad Alyssa.

2.4.2Data â thagiau

Un ffordd o edrych ar haniaethu data yw fel cymhwysiad o’r “egwyddor o ymrwymo cyn lleied â phosibl.” Wrth weithredu’r system rhifau cymhlyg yn 2.4.1, gallwn ddefnyddio naill ai gynrychioliad petryalog Ben neu gynrychioliad pegynol Alyssa. Mae’r rhwystr haniaethu a ffurfir gan y detholwyr a’r adeiladyddion yn caniatáu inni ohirio’r dewis o gynrychioliad pendant ar gyfer ein gwrthrychau data tan yr eiliad olaf bosibl, ac felly gadw’r hyblygrwydd mwyaf wrth ddylunio ein system.

Gellir mynd â’r egwyddor o ymrwymo cyn lleied â phosibl hyd yn oed ymhellach. Os dymunwn, gallwn gadw amwysedd y cynrychioliad hyd yn oed ar ôl inni ddylunio’r detholwyr a’r adeiladyddion, a dewis defnyddio cynrychioliad Ben a chynrychioliad Alyssa. Os cynhwysir y ddau gynrychioliad mewn un system, fodd bynnag, bydd angen rhyw ffordd o wahaniaethu rhwng data ar ffurf begynol a data ar ffurf betryalog. Fel arall, pe gofynnid inni, er enghraifft, ganfod magnitude y pâr (3, 4), ni fyddem yn gwybod a ddylem ateb 5 (gan ddehongli’r rhif ar ffurf betryalog) neu 3 (gan ddehongli’r rhif ar ffurf begynol). Ffordd syml o wneud y gwahaniaeth hwn yw cynnwys tag math—y symbol rectangular neu polar—fel rhan o bob rhif cymhlyg. Yna, pan fydd angen inni drin rhif cymhlyg, gallwn ddefnyddio’r tag i benderfynu pa ddetholwr i’w gymhwyso.

Er mwyn trin data â thagiau, byddwn yn tybio bod gennym weithdrefnau type-tag ac contents sy’n echdynnu’r tag a’r cynnwys ei hun o wrthrych data (y cyfesurynnau pegynol neu betryalog, yn achos rhif cymhlyg). Byddwn hefyd yn rhagdybio gweithdrefn attach-tag sy’n cymryd tag a chynnwys ac yn cynhyrchu gwrthrych data â thag. Ffordd syml o weithredu hyn yw defnyddio strwythur rhestrau cyffredin:

(define (attach-tag type-tag contents)
  (cons type-tag contents))

(define (type-tag datum)
  (if (pair? datum)
      (car datum)
      (error "Bad tagged datum: 
              TYPE-TAG" datum)))

(define (contents datum)
  (if (pair? datum)
      (cdr datum)
      (error "Bad tagged datum: 
              CONTENTS" datum)))

Gan ddefnyddio’r gweithdrefnau hyn, gallwn ddiffinio traethiadau rectangular? ac polar?, sy’n adnabod rhifau petryalog a phegynol, yn y drefn honno:

(define (rectangular? z)
  (eq? (type-tag z) 'rectangular))

(define (polar? z)
  (eq? (type-tag z) 'polar))

Gyda thagiau math, gall Ben ac Alyssa bellach addasu eu cod fel y gall eu dau gynrychioliad gwahanol gydfodoli yn yr un system. Bob tro y mae Ben yn adeiladu rhif cymhlyg, mae’n rhoi tag petryalog iddo. Bob tro y mae Alyssa’n adeiladu rhif cymhlyg, mae’n rhoi tag pegynol iddo. Yn ogystal, rhaid i Ben ac Alyssa sicrhau nad yw enwau eu gweithdrefnau’n gwrthdaro. Un ffordd o wneud hyn yw i Ben atodi’r ôl-ddodiad rectangular at enw pob un o’i weithdrefnau cynrychioli ac i Alyssa atodi polar at enwau ei rhai hi. Dyma gynrychioliad petryalog diwygiedig Ben o 2.4.1:

(define (real-part-rectangular z) (car z))
(define (imag-part-rectangular z) (cdr z))

(define (magnitude-rectangular z)
  (sqrt (+ (square (real-part-rectangular z))
           (square (imag-part-rectangular z)))))

(define (angle-rectangular z)
  (atan (imag-part-rectangular z)
        (real-part-rectangular z)))

(define (make-from-real-imag-rectangular x y)
  (attach-tag 'rectangular (cons x y)))

(define (make-from-mag-ang-rectangular r a)
  (attach-tag 
   'rectangular
   (cons (* r (cos a)) (* r (sin a)))))

a dyma gynrychioliad pegynol diwygiedig Alyssa:

(define (real-part-polar z)
  (* (magnitude-polar z) 
     (cos (angle-polar z))))

(define (imag-part-polar z)
  (* (magnitude-polar z) 
     (sin (angle-polar z))))

(define (magnitude-polar z) (car z))
(define (angle-polar z) (cdr z))

(define (make-from-real-imag-polar x y)
  (attach-tag 
   'polar
   (cons (sqrt (+ (square x) (square y)))
         (atan y x))))

(define (make-from-mag-ang-polar r a)
  (attach-tag 'polar (cons r a)))

Gweithredir pob detholwr generig fel gweithdrefn sy’n gwirio tag ei arg ac yn galw’r weithdrefn briodol ar gyfer trin data o’r math hwnnw. Er enghraifft, i gael rhan real rhif cymhlyg, mae real-part yn archwilio’r tag i benderfynu a ddylid defnyddio real-part-rectangular Ben neu real-part-polar Alyssa. Yn y naill achos a’r llall, defnyddiwn contents i echdynnu’r eitem ddata noeth, heb dag, a’i hanfon at y weithdrefn betryalog neu begynol yn ôl yr angen:

(define (real-part z)
  (cond ((rectangular? z)
         (real-part-rectangular (contents z)))
        ((polar? z)
         (real-part-polar (contents z)))
        (else (error "Unknown type: 
               REAL-PART" z))))

(define (imag-part z)
  (cond ((rectangular? z)
         (imag-part-rectangular (contents z)))
        ((polar? z)
         (imag-part-polar (contents z)))
        (else (error "Unknown type: 
               IMAG-PART" z))))

(define (magnitude z)
  (cond ((rectangular? z)
         (magnitude-rectangular (contents z)))
        ((polar? z)
         (magnitude-polar (contents z)))
        (else (error "Unknown type: 
               MAGNITUDE" z))))

(define (angle z)
  (cond ((rectangular? z)
         (angle-rectangular (contents z)))
        ((polar? z)
         (angle-polar (contents z)))
        (else (error "Unknown type: 
               ANGLE" z))))

I weithredu’r gweithrediadau rhifyddol ar rifau cymhlyg, gallwn ddefnyddio’r un gweithdrefnau add-complex, sub-complex, mul-complex, ac div-complex o 2.4.1, oherwydd bod y detholwyr y maent yn eu galw yn generig, ac felly’n gweithio gyda’r naill gynrychioliad neu’r llall. Er enghraifft, y weithdrefn add-complex o hyd yw

(define (add-complex z1 z2)
  (make-from-real-imag 
   (+ (real-part z1) (real-part z2))
   (+ (imag-part z1) (imag-part z2))))

Yn olaf, rhaid inni ddewis a ddylid adeiladu rhifau cymhlyg gan ddefnyddio cynrychioliad Ben neu gynrychioliad Alyssa. Un dewis rhesymol yw adeiladu rhifau petryalog pryd bynnag y mae gennym rannau real a dychmygol, ac adeiladu rhifau pegynol pryd bynnag y mae gennym feintiau ac onglau:

(define (make-from-real-imag x y)
  (make-from-real-imag-rectangular x y))

(define (make-from-mag-ang r a)
  (make-from-mag-ang-polar r a))

Mae gan y system rhifau cymhlyg sy’n deillio o hyn y strwythur a ddangosir yn Ffigur 2.21. Mae’r system wedi’i rhannu’n dair rhan gymharol annibynnol: y gweithrediadau rhifyddol ar rifau cymhlyg, gweithrediad pegynol Alyssa, a gweithrediad petryalog Ben. Gallai Ben ac Alyssa fod wedi ysgrifennu’r gweithrediadau pegynol a phetryalog wrth weithio ar wahân, a gall trydydd rhaglennydd sy’n gweithredu’r gweithdrefnau rhifyddeg gymhlyg yn nhermau’r rhyngwyneb adeiladyddion/detholwyr haniaethol ddefnyddio’r ddau hyn yn gynrychioliadau sylfaenol.

Ffigur 2.21: Strwythur y system rhifyddeg gymhlyg generig.

Gan fod pob gwrthrych data wedi’i dagio â’i fath, mae’r detholwyr yn gweithredu ar y data mewn ffordd generig. Hynny yw, diffinnir pob detholwr i ymddwyn mewn ffordd sy’n dibynnu ar y math penodol o ddata y cymhwysir ef iddo. Sylwch ar y mecanwaith cyffredinol ar gyfer cysylltu’r cynrychioliadau ar wahân: O fewn gweithrediad cynrychioliad penodol (er enghraifft, pecyn pegynol Alyssa), pâr heb fath yw rhif cymhlyg (maint, ongl). Pan fydd detholwr generig yn gweithredu ar rif o fath polar, mae’n tynnu’r tag ac yn trosglwyddo’r cynnwys i god Alyssa. I’r gwrthwyneb, pan fydd Alyssa’n adeiladu rhif at ddefnydd cyffredinol, mae’n ei dagio â math fel y gall y gweithdrefnau lefel uwch ei adnabod yn briodol. Gall y ddisgyblaeth hon o dynnu ac atodi tagiau wrth drosglwyddo gwrthrychau data o lefel i lefel fod yn strategaeth drefnu bwysig, fel y gwelwn yn 2.5.

2.4.3Rhaglennu a Gyfarwyddir gan Ddata ac Estyn drwy Ychwanegu

Gelwir y strategaeth gyffredinol o wirio math eitem ddata a galw gweithdrefn briodol yn dethol gweithdrefn yn ôl y math. Mae hon yn strategaeth bwerus ar gyfer sicrhau modiwlaredd wrth ddylunio systemau. Ar y llaw arall, mae dau wendid sylweddol i weithredu’r dethol fel yn 2.4.2. Un gwendid yw bod rhaid i’r gweithdrefnau rhyngwyneb generig (real-part, imag-part, magnitude, ac angle) wybod am yr holl gynrychioliadau gwahanol. Er enghraifft, tybiwch ein bod am gynnwys cynrychioliad newydd ar gyfer rhifau cymhlyg yn ein system rhifau cymhlyg. Byddai angen inni adnabod y cynrychioliad newydd hwn â math, ac yna ychwanegu cymal at bob un o’r gweithdrefnau rhyngwyneb generig i wirio am y math newydd a chymhwyso’r detholwr priodol ar gyfer y cynrychioliad hwnnw.

Gwendid arall yn y dechneg yw, er y gellir dylunio’r cynrychioliadau unigol ar wahân, fod rhaid inni warantu nad oes gan unrhyw ddwy weithdrefn yn y system gyfan yr un enw. Dyna pam roedd rhaid i Ben ac Alyssa newid enwau eu gweithdrefnau gwreiddiol o 2.4.1.

Y mater sydd wrth wraidd y ddau wendid hyn yw nad yw’r dechneg ar gyfer gweithredu rhyngwynebau generig yn caniatáu estyn drwy ychwanegu. Rhaid i’r sawl sy’n gweithredu’r gweithdrefnau dethol generig addasu’r gweithdrefnau hynny bob tro y gosodir cynrychioliad newydd, a rhaid i’r bobl sy’n cysylltu’r cynrychioliadau unigol addasu eu cod i osgoi gwrthdaro rhwng enwau. Ym mhob un o’r achosion hyn, mae’r newidiadau y mae rhaid eu gwneud i’r cod yn syml, ond rhaid eu gwneud serch hynny, ac mae hyn yn ffynhonnell anghyfleustra a gwallau. Nid yw hyn yn broblem fawr i’r system rhifau cymhlyg fel y mae, ond tybiwch fod cannoedd o gynrychioliadau gwahanol ar gyfer rhifau cymhlyg, yn hytrach na dau. A thybiwch fod llawer o ddetholwyr generig i’w cynnal yn y rhyngwyneb data haniaethol. Tybiwch, mewn gwirionedd, nad oedd yr un rhaglennydd yn gwybod yr holl weithdrefnau rhyngwyneb na’r holl gynrychioliadau. Mae’r broblem yn un wirioneddol a rhaid mynd i’r afael â hi mewn rhaglenni megis systemau rheoli cronfeydd data ar raddfa fawr.

Yr hyn sydd ei angen arnom yw ffordd o wneud dyluniad y system yn fwy modiwlaidd fyth. Darperir hyn gan y dechneg raglennu a elwir yn rhaglennu a gyfarwyddir gan ddata. I ddeall sut mae rhaglennu a gyfarwyddir gan ddata yn gweithio, dechreuwch drwy sylwi ein bod, pryd bynnag yr ymdriniwn â set o weithrediadau generig sy’n gyffredin i set o fathau gwahanol, mewn gwirionedd yn ymdrin â thabl dau ddimensiwn sy’n cynnwys y gweithrediadau posibl ar un echelin a’r mathau posibl ar yr echelin arall. Y cofnodion yn y tabl yw’r gweithdrefnau sy’n gweithredu pob gweithrediad ar gyfer pob math o arg a gyflwynir. Yn y system rhifau cymhlyg a ddatblygwyd yn yr adran flaenorol, roedd y cyfatebiaeth rhwng enw’r gweithrediad, y math data a’r weithdrefn ei hun wedi’i gwasgaru ymhlith y gwahanol gymalau amodol yn y gweithdrefnau rhyngwyneb generig. Ond gellid bod wedi trefnu’r un wybodaeth mewn tabl, fel y dangosir yn Ffigur 2.22.

Ffigur 2.22: Tabl gweithrediadau ar gyfer y system rhifau cymhlyg.

Rhaglennu a gyfarwyddir gan ddata yw’r dechneg o ddylunio rhaglenni i weithio’n uniongyrchol â thabl o’r fath. Yn flaenorol, gweithredasom y mecanwaith sy’n cysylltu’r cod rhifyddeg gymhlyg â’r ddau becyn cynrychioli fel set o weithdrefnau sydd bob un yn dethol gweithdrefn yn benodol yn ôl y math. Yma byddwn yn gweithredu’r rhyngwyneb fel un weithdrefn sy’n chwilio am gyfuniad enw’r gweithrediad a math yr arg yn y tabl i ganfod y weithdrefn gywir i’w chymhwyso, ac yna’n ei chymhwyso i gynnwys yr arg. Os gwnawn hyn, yna nid oes angen newid unrhyw weithdrefnau presennol i ychwanegu pecyn cynrychioli newydd at y system; dim ond ychwanegu cofnodion newydd at y tabl sydd ei angen.

I weithredu’r cynllun hwn, tybiwch fod gennym ddwy weithdrefn, put ac get, ar gyfer trin y tabl gweithrediadau a mathau:

Mae (put ⟨op⟩ ⟨type⟩ ⟨item⟩) yn gosod ⟨item⟩ yn y tabl, wedi’i fynegeio yn ôl ⟨op⟩ ac ⟨type⟩.
Mae (get ⟨op⟩ ⟨type⟩) yn chwilio am y cofnod ⟨op⟩, ⟨type⟩ yn y tabl ac yn dychwelyd yr eitem a geir yno. Os na cheir eitem, mae get yn dychwelyd anwir.

Am y tro, gallwn dybio bod put ac get wedi’u cynnwys yn ein hiaith. Ym Mhennod 3 (3.3.3) gwelwn sut i weithredu’r rhain a gweithrediadau eraill ar gyfer trin tablau.

Dyma sut y gellir defnyddio rhaglennu a gyfarwyddir gan ddata yn y system rhifau cymhlyg. Mae Ben, a ddatblygodd y cynrychioliad petryalog, yn gweithredu ei god yn union fel y gwnaeth yn wreiddiol. Mae’n diffinio casgliad o weithdrefnau, neu becyn, ac yn eu cysylltu â gweddill y system drwy ychwanegu cofnodion at y tabl sy’n dweud wrth y system sut i weithredu ar rifau petryalog. Cyflawnir hyn drwy alw’r weithdrefn ganlynol:

(define (install-rectangular-package)
  ;; internal procedures
  (define (real-part z) (car z))
  (define (imag-part z) (cdr z))
  (define (make-from-real-imag x y) 
    (cons x y))
  (define (magnitude z)
    (sqrt (+ (square (real-part z))
             (square (imag-part z)))))
  (define (angle z)
    (atan (imag-part z) (real-part z)))
  (define (make-from-mag-ang r a)
    (cons (* r (cos a)) (* r (sin a))))
  ;; interface to the rest of the system
  (define (tag x) 
    (attach-tag 'rectangular x))
  (put 'real-part '(rectangular) real-part)
  (put 'imag-part '(rectangular) imag-part)
  (put 'magnitude '(rectangular) magnitude)
  (put 'angle '(rectangular) angle)
  (put 'make-from-real-imag 'rectangular
       (lambda (x y) 
         (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'rectangular
       (lambda (r a) 
         (tag (make-from-mag-ang r a))))
  'done)

Sylwch mai’r gweithdrefnau mewnol yma yw’r un gweithdrefnau o 2.4.1 a ysgrifennodd Ben pan oedd yn gweithio ar ei ben ei hun. Nid oes angen unrhyw newidiadau i’w cysylltu â gweddill y system. Ymhellach, gan fod y diffiniadau hyn o weithdrefnau’n fewnol i’r weithdrefn osod, nid oes angen i Ben boeni am wrthdaro rhwng enwau a gweithdrefnau eraill y tu allan i’r pecyn petryalog. I gysylltu’r rhain â gweddill y system, mae Ben yn gosod ei weithdrefn real-part o dan enw gweithrediad real-part a math (rectangular), ac yn yr un modd ar gyfer y detholwyr eraill.¹¹¹ Mae’r rhyngwyneb hefyd yn diffinio’r adeiladyddion a ddefnyddir gan y system allanol.¹¹² Mae’r rhain yn union yr un fath ag adeiladyddion Ben a ddiffiniwyd yn fewnol, heblaw eu bod yn atodi’r tag.

Mae pecyn pegynol Alyssa yn gyfatebol:

(define (install-polar-package)
  ;; internal procedures
  (define (magnitude z) (car z))
  (define (angle z) (cdr z))
  (define (make-from-mag-ang r a) (cons r a))
  (define (real-part z)
    (* (magnitude z) (cos (angle z))))
  (define (imag-part z)
    (* (magnitude z) (sin (angle z))))
  (define (make-from-real-imag x y)
    (cons (sqrt (+ (square x) (square y)))
          (atan y x)))
  ;; interface to the rest of the system
  (define (tag x) (attach-tag 'polar x))
  (put 'real-part '(polar) real-part)
  (put 'imag-part '(polar) imag-part)
  (put 'magnitude '(polar) magnitude)
  (put 'angle '(polar) angle)
  (put 'make-from-real-imag 'polar
       (lambda (x y) 
         (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'polar
       (lambda (r a) 
         (tag (make-from-mag-ang r a))))
  'done)

Er bod Ben ac Alyssa ill dau’n dal i ddefnyddio eu gweithdrefnau gwreiddiol a ddiffiniwyd â’r un enwau â rhai ei gilydd (e.e., real-part), mae’r diffiniadau hyn bellach yn fewnol i weithdrefnau gwahanol (gweler 1.1.8), felly nid oes gwrthdaro rhwng enwau.

Mae’r detholwyr rhifyddeg gymhlyg yn cyrchu’r tabl drwy weithdrefn “weithredu” gyffredinol o’r enw apply-generic, sy’n cymhwyso gweithrediad generig i rai argiau. Mae Apply-generic yn edrych yn y tabl o dan enw’r gweithrediad a mathau’r argiau ac yn cymhwyso’r weithdrefn a geir os oes un yn bresennol:¹¹³

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (error
            "No method for these types: 
             APPLY-GENERIC"
            (list op type-tags))))))

Gan ddefnyddio apply-generic, gallwn ddiffinio ein detholwyr generig fel a ganlyn:

(define (real-part z) 
  (apply-generic 'real-part z))
(define (imag-part z) 
  (apply-generic 'imag-part z))
(define (magnitude z) 
  (apply-generic 'magnitude z))
(define (angle z) 
  (apply-generic 'angle z))

Sylwch nad yw’r rhain yn newid o gwbl os ychwanegir cynrychioliad newydd at y system.

Gallwn hefyd echdynnu o’r tabl yr adeiladyddion a ddefnyddir gan y rhaglenni y tu allan i’r pecynnau i wneud rhifau cymhlyg o rannau real a dychmygol ac o feintiau ac onglau. Fel yn 2.4.2, adeiladwn rifau petryalog pryd bynnag y mae gennym rannau real a dychmygol, a rhifau pegynol pryd bynnag y mae gennym feintiau ac onglau:

(define (make-from-real-imag x y)
  ((get 'make-from-real-imag 
        'rectangular) 
   x y))

(define (make-from-mag-ang r a)
  ((get 'make-from-mag-ang 
        'polar) 
   r a))

Ymarfer 2.73: Disgrifiodd 2.3.2 raglen sy’n cyflawni differu symbolaidd:
(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp) 
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product 
            (multiplier exp)
            (deriv (multiplicand exp) var))
           (make-product 
            (deriv (multiplier exp) var)
            (multiplicand exp))))
        ⟨more rules can be added here⟩
        (else (error "unknown expression type:
                      DERIV" exp))))
Gallwn ystyried bod y rhaglen hon yn dethol gweithdrefn yn ôl math y mynegiad sydd i’w ddifferu. Yn y sefyllfa hon, “tag math” yr eitem ddata yw symbol y gweithredydd algebraidd (megis +) a’r gweithrediad sy’n cael ei gyflawni yw deriv. Gallwn drawsffurfio’r rhaglen hon i ddefnyddio dull a gyfarwyddir gan ddata drwy ailysgrifennu’r weithdrefn ddeilliadau sylfaenol fel
(define (deriv exp var)
   (cond ((number? exp) 0)
         ((variable? exp) 
           (if (same-variable? exp var) 
               1 
               0))
         (else ((get 'deriv (operator exp)) 
                (operands exp) 
                var))))

(define (operator exp) (car exp))
(define (operands exp) (cdr exp))
Esboniwch yr hyn a wnaed uchod. Pam na allwn ymgorffori’r traethiadau number? ac variable? yn y dethol gweithdrefn a gyfarwyddir gan ddata?
Ysgrifennwch y gweithdrefnau ar gyfer deilliadau symiau a lluosymiau, a’r cod ategol sydd ei angen i’w gosod yn y tabl a ddefnyddir gan y rhaglen uchod.
Dewiswch unrhyw reol ddifferu ychwanegol a ddymunwch, megis yr un ar gyfer pwerau (Ymarfer 2.56), a’i gosod yn y system hon a gyfarwyddir gan ddata.
Yn y system drin algebraidd syml hon, math mynegiad yw’r gweithredydd algebraidd sy’n ei glymu ynghyd. Tybiwch, fodd bynnag, ein bod yn mynegeio’r gweithdrefnau i’r gwrthwyneb, fel bod y llinell dethol gweithdrefn yn deriv yn edrych fel
((get (operator exp) 'deriv) 
 (operands exp) var)
Pa newidiadau cyfatebol sydd eu hangen i’r system ddeilliadau?

Ymarfer 2.74: Cwmni conglomerad hynod ddatganoledig yw Insatiable Enterprises, Inc., sy’n cynnwys nifer fawr o adrannau annibynnol ledled y byd. Mae cyfleusterau cyfrifiadurol y cwmni newydd gael eu cysylltu â’i gilydd drwy gynllun clyfar ar gyfer rhyngwynebu rhwydweithiau sy’n gwneud i’r rhwydwaith cyfan ymddangos i unrhyw ddefnyddiwr fel un cyfrifiadur. Mae llywydd Insatiable, yn ei hymgais gyntaf i fanteisio ar allu’r rhwydwaith i echdynnu gwybodaeth weinyddol o ffeiliau’r adrannau, yn siomedig o ddarganfod, er bod holl ffeiliau’r adrannau wedi’u gweithredu fel strwythurau data yn Scheme, fod y strwythur data penodol a ddefnyddir yn amrywio o adran i adran. Gelwir cyfarfod o reolwyr yr adrannau ar frys i chwilio am strategaeth i integreiddio’r ffeiliau a fydd yn bodloni anghenion y pencadlys gan gadw ymreolaeth bresennol yr adrannau.

Dangoswch sut y gellir gweithredu strategaeth o’r fath drwy raglennu a gyfarwyddir gan ddata. Er enghraifft, tybiwch fod cofnodion personél pob adran yn cynnwys un ffeil, sy’n cynnwys set o gofnodion ag enwau’r cyflogeion yn allweddi iddynt. Mae strwythur y set yn amrywio o adran i adran. Ymhellach, mae cofnod pob cyflogai ei hun yn set (wedi’i strwythuro’n wahanol o adran i adran) sy’n cynnwys gwybodaeth dan allweddi sy’n ddynodwyr megis address ac salary. Yn benodol:

Gweithredwch weithdrefn get-record ar gyfer y pencadlys sy’n adalw cofnod cyflogai penodedig o ffeil bersonél benodedig. Dylai’r weithdrefn fod yn gymwys i ffeil unrhyw adran. Esboniwch sut y dylid strwythuro ffeiliau’r adrannau unigol. Yn benodol, pa wybodaeth am fathau y mae rhaid ei darparu?
Gweithredwch weithdrefn get-salary ar gyfer y pencadlys sy’n dychwelyd y wybodaeth am gyflog o gofnod cyflogai penodol o ffeil bersonél unrhyw adran. Sut y dylid strwythuro’r cofnod er mwyn gwneud i’r gweithrediad hwn weithio?
Gweithredwch weithdrefn find-employee-record ar gyfer y pencadlys. Dylai hon chwilio ffeiliau’r holl adrannau am gofnod cyflogai penodol a dychwelyd y cofnod. Tybiwch fod y weithdrefn hon yn cymryd enw cyflogai a rhestr o ffeiliau’r holl adrannau yn argiau.
Pan fydd Insatiable yn cymryd cwmni newydd drosodd, pa newidiadau y mae rhaid eu gwneud er mwyn cynnwys y wybodaeth bersonél newydd yn y system ganolog?

Trosglwyddo negeseuon

Syniad allweddol rhaglennu a gyfarwyddir gan ddata yw trin gweithrediadau generig mewn rhaglenni drwy ymdrin yn benodol â thablau gweithrediadau a mathau, megis y tabl yn Ffigur 2.22. Roedd yr arddull raglennu a ddefnyddiasom yn 2.4.2 yn trefnu’r dethol gweithdrefnau yn ôl math sydd ei angen drwy beri i bob gweithrediad ofalu am ei ddethol ei hun. Mewn gwirionedd, mae hyn yn rhannu’r tabl gweithrediadau a mathau yn rhesi, gyda phob gweithdrefn gweithrediad generig yn cynrychioli rhes o’r tabl.

Strategaeth weithredu amgen yw rhannu’r tabl yn golofnau ac, yn lle defnyddio “gweithrediadau deallus” sy’n dethol gweithdrefn yn ôl mathau data, gweithio gyda “gwrthrychau data deallus” sy’n dethol gweithdrefn yn ôl enwau gweithrediadau. Gallwn wneud hyn drwy drefnu pethau fel bod gwrthrych data, megis rhif petryalog, wedi’i gynrychioli fel gweithdrefn sy’n cymryd enw’r gweithrediad gofynnol yn fewnbwn ac yn cyflawni’r gweithrediad a ddynodir. O dan ddisgyblaeth o’r fath, gellid ysgrifennu make-from-real-imag fel

(define (make-from-real-imag x y)
  (define (dispatch op)
    (cond ((eq? op 'real-part) x)
          ((eq? op 'imag-part) y)
          ((eq? op 'magnitude)
           (sqrt (+ (square x) (square y))))
          ((eq? op 'angle) (atan y x))
          (else
           (error "Unknown op: 
            MAKE-FROM-REAL-IMAG" op))))
  dispatch)

Mae’r weithdrefn gyfatebol apply-generic, sy’n cymhwyso gweithrediad generig i arg, bellach yn bwydo enw’r gweithrediad i’r gwrthrych data ac yn gadael i’r gwrthrych wneud y gwaith:¹¹⁴

(define (apply-generic op arg) (arg op))

Sylwch mai gweithdrefn yw’r gwerth a ddychwelir gan make-from-real-imag—y weithdrefn fewnol dispatch. Dyma’r weithdrefn a alwir pan fydd apply-generic yn gofyn i weithrediad gael ei gyflawni.

Gelwir yr arddull raglennu hon yn drosglwyddo negeseuon. Daw’r enw o’r ddelwedd fod gwrthrych data yn endid sy’n derbyn enw’r gweithrediad y gofynnir amdano fel “neges.” Rydym eisoes wedi gweld enghraifft o drosglwyddo negeseuon yn 2.1.3, lle gwelsom sut y gellid diffinio cons, car, ac cdr heb wrthrychau data ond â gweithdrefnau yn unig. Yma gwelwn nad tric mathemategol yw trosglwyddo negeseuon, ond techneg ddefnyddiol ar gyfer trefnu systemau â gweithrediadau generig. Yng ngweddill y bennod hon byddwn yn parhau i ddefnyddio rhaglennu a gyfarwyddir gan ddata, yn hytrach na throsglwyddo negeseuon, i drafod gweithrediadau rhifyddol generig. Ym Mhennod 3 byddwn yn dychwelyd at drosglwyddo negeseuon, a gwelwn y gall fod yn arf pwerus ar gyfer strwythuro rhaglenni efelychu.

Ymarfer 2.75: Gweithredwch yr adeiladydd make-from-mag-ang gan ddefnyddio trosglwyddo negeseuon. Dylai’r weithdrefn hon fod yn gyfatebol i’r weithdrefn make-from-real-imag a roddwyd uchod.

Ymarfer 2.76: Wrth i system fawr â gweithrediadau generig esblygu, efallai y bydd angen mathau newydd o wrthrychau data neu weithrediadau newydd. Ar gyfer pob un o’r tair strategaeth—gweithrediadau generig â dethol gweithdrefn yn benodol, dull a gyfarwyddir gan ddata, a dull trosglwyddo negeseuon—disgrifiwch y newidiadau y mae rhaid eu gwneud i system er mwyn ychwanegu mathau newydd neu weithrediadau newydd. Pa drefniadaeth fyddai fwyaf priodol ar gyfer system lle mae rhaid ychwanegu mathau newydd yn aml? Pa un fyddai fwyaf priodol ar gyfer system lle mae rhaid ychwanegu gweithrediadau newydd yn aml?

Troednodiadau

¹⁰⁹ Mewn systemau cyfrifiadurol go iawn, mae ffurf betryalog yn well na ffurf begynol y rhan fwyaf o’r amser oherwydd gwallau talgrynnu wrth drosi rhwng ffurf betryalog a ffurf begynol. Dyna pam mae’r enghraifft o rifau cymhlyg yn afrealistig. Serch hynny, mae’n dangos yn glir sut i ddylunio system sy’n defnyddio gweithrediadau generig ac yn gyflwyniad da i’r systemau mwy sylweddol a ddatblygir yn ddiweddarach yn y bennod hon.

¹¹⁰ Diffinnir y ffwythiant arctangiad y cyfeirir ato yma, a gyfrifir gan weithdrefn atan Scheme, i gymryd dau arg $y$ ac $x$ ac i ddychwelyd yr ongl y mae ei thangiad yn $y / x$ . Mae arwyddion yr argiau’n pennu cwadrant yr ongl.

¹¹¹ Defnyddiwn y rhestr (rectangular) yn hytrach na’r symbol rectangular i ganiatáu ar gyfer y posibilrwydd o weithrediadau ag argiau lluosog nad ydynt i gyd o’r un math.

¹¹² Nid oes rhaid i’r math y gosodir yr adeiladyddion oddi tano fod yn rhestr oherwydd bod adeiladydd bob amser yn cael ei ddefnyddio i wneud gwrthrych o un math penodol.

¹¹³ Mae Apply-generic yn defnyddio’r nodiant cynffon ddotiog a ddisgrifiwyd yn Ymarfer 2.20, oherwydd y gall gweithrediadau generig gwahanol gymryd niferoedd gwahanol o argiau. Yn apply-generic, mae gan op arg cyntaf apply-generic yn werth iddo, ac mae gan args restr o’r argiau sy’n weddill yn werth iddo.

Mae Apply-generic hefyd yn defnyddio’r weithdrefn gyntefig apply, sy’n cymryd dau arg, gweithdrefn a rhestr. Mae Apply yn cymhwyso’r weithdrefn, gan ddefnyddio’r elfennau yn y rhestr yn argiau. Er enghraifft, mae

(apply + (list 1 2 3 4))

yn dychwelyd 10.

¹¹⁴ Un cyfyngiad ar y drefniadaeth hon yw ei bod yn caniatáu gweithdrefnau generig ag un arg yn unig.