SICP · Yr ail argraffiad · Scheme

2.5 Systemau â Gweithrediadau Generig

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

Yn yr adran flaenorol, gwelsom sut i ddylunio systemau lle gellir cynrychioli gwrthrychau data mewn mwy nag un ffordd. Y syniad allweddol yw cysylltu’r cod sy’n pennu’r gweithrediadau ar ddata â’r sawl cynrychioliad drwy weithdrefnau rhyngwyneb generig. Yn awr gwelwn sut i ddefnyddio’r un syniad hwn nid yn unig i ddiffinio gweithrediadau sy’n generig dros wahanol gynrychioliadau ond hefyd i ddiffinio gweithrediadau sy’n generig dros wahanol fathau o argiau. Rydym eisoes wedi gweld sawl pecyn gwahanol o weithrediadau rhifyddol: y rhifyddeg gyntefig (+, -, *, /) sydd wedi’i chynnwys yn ein hiaith, rhifyddeg rhifau cymarebol (add-rat, sub-rat, mul-rat, div-rat) 2.1.1, a’r rhifyddeg rhifau cymhlyg a weithredasom yn 2.4.3. Yn awr defnyddiwn dechnegau a gyfarwyddir gan ddata i adeiladu pecyn o weithrediadau rhifyddol sy’n cynnwys yr holl becynnau rhifyddeg yr ydym eisoes wedi’u hadeiladu.

Mae Ffigur 2.23 yn dangos strwythur y system y byddwn yn ei hadeiladu. Sylwch ar y rhwystrau haniaethu. O safbwynt rhywun sy’n defnyddio “rhifau,” mae un weithdrefn add sy’n gweithredu ar ba rifau bynnag a ddarperir. Mae Add yn rhan o ryngwyneb generig sy’n caniatáu i raglenni sy’n defnyddio rhifau gyrchu’r pecynnau rhifyddeg gyffredin, rhifyddeg gymarebol a rhifyddeg gymhlyg ar wahân mewn ffordd unffurf. Gellir cyrchu unrhyw becyn rhifyddeg unigol (megis y pecyn cymhlyg) ei hun drwy weithdrefnau generig (megis add-complex) sy’n cyfuno pecynnau a ddyluniwyd ar gyfer cynrychioliadau gwahanol (megis petryalog a phegynol). Ymhellach, gellir estyn strwythur y system drwy ychwanegu, fel y gellir dylunio’r pecynnau rhifyddeg unigol ar wahân a’u cyfuno i gynhyrchu system rhifyddeg generig.

Ffigur 2.23: System rhifyddeg generig.

2.5.1Gweithrediadau Rhifyddol Generig

Mae’r dasg o ddylunio gweithrediadau rhifyddol generig yn gyfatebol i’r dasg o ddylunio’r gweithrediadau generig ar rifau cymhlyg. Hoffem, er enghraifft, gael gweithdrefn adio generig add sy’n ymddwyn fel yr adio cyntefig cyffredin + ar rifau cyffredin, fel add-rat ar rifau cymarebol, ac fel add-complex ar rifau cymhlyg. Gallwn weithredu add, a’r gweithrediadau rhifyddol generig eraill, drwy ddilyn yr un strategaeth ag a ddefnyddiasom yn 2.4.3 i weithredu’r detholwyr generig ar gyfer rhifau cymhlyg. Byddwn yn atodi tag math at bob math o rif ac yn peri i’r weithdrefn generig ddethol pecyn priodol yn ôl math data ei hargiau.

Diffinnir y gweithdrefnau rhifyddol generig fel a ganlyn:

(define (add x y) (apply-generic 'add x y))
(define (sub x y) (apply-generic 'sub x y))
(define (mul x y) (apply-generic 'mul x y))
(define (div x y) (apply-generic 'div x y))

Dechreuwn drwy osod pecyn ar gyfer trin rhifau cyffredin, hynny yw, rhifau cyntefig ein hiaith. Byddwn yn rhoi’r tag scheme-number arnynt. Y gweithrediadau rhifyddol yn y pecyn hwn yw’r gweithdrefnau rhifyddol cyntefig (felly nid oes angen diffinio gweithdrefnau ychwanegol i drin y rhifau heb dagiau). Gan fod pob un o’r gweithrediadau hyn yn cymryd dau arg, cânt eu gosod yn y tabl â’r rhestr (scheme-number scheme-number) yn allwedd iddynt:

(define (install-scheme-number-package)
  (define (tag x)
    (attach-tag 'scheme-number x))
  (put 'add '(scheme-number scheme-number)
       (lambda (x y) (tag (+ x y))))
  (put 'sub '(scheme-number scheme-number)
       (lambda (x y) (tag (- x y))))
  (put 'mul '(scheme-number scheme-number)
       (lambda (x y) (tag (* x y))))
  (put 'div '(scheme-number scheme-number)
       (lambda (x y) (tag (/ x y))))
  (put 'make 'scheme-number
       (lambda (x) (tag x)))
  'done)

Bydd defnyddwyr y pecyn rhifau Scheme yn creu rhifau cyffredin (â thagiau) drwy’r weithdrefn:

(define (make-scheme-number n)
  ((get 'make 'scheme-number) n))

Gan fod fframwaith y system rhifyddeg generig bellach yn ei le, gallwn gynnwys mathau newydd o rifau’n hwylus. Dyma becyn sy’n cyflawni rhifyddeg gymarebol. Sylwch y gallwn, fel mantais o allu estyn drwy ychwanegu, ddefnyddio’r cod rhifau cymarebol o 2.1.1 heb ei addasu fel gweithdrefnau mewnol y pecyn:

(define (install-rational-package)
  ;; internal procedures
  (define (numer x) (car x))
  (define (denom x) (cdr x))
  (define (make-rat n d)
    (let ((g (gcd n d)))
      (cons (/ n g) (/ d g))))
  (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))))
  ;; interface to rest of the system
  (define (tag x) (attach-tag 'rational x))
  (put 'add '(rational rational)
       (lambda (x y) (tag (add-rat x y))))
  (put 'sub '(rational rational)
       (lambda (x y) (tag (sub-rat x y))))
  (put 'mul '(rational rational)
       (lambda (x y) (tag (mul-rat x y))))
  (put 'div '(rational rational)
       (lambda (x y) (tag (div-rat x y))))
  (put 'make 'rational
       (lambda (n d) (tag (make-rat n d))))
  'done)

(define (make-rational n d)
  ((get 'make 'rational) n d))

Gallwn osod pecyn tebyg i drin rhifau cymhlyg, gan ddefnyddio’r tag complex. Wrth greu’r pecyn, echdynnwn o’r tabl y gweithrediadau make-from-real-imag ac make-from-mag-ang a ddiffiniwyd gan y pecynnau petryalog a phegynol. Mae’r gallu i estyn drwy ychwanegu yn caniatáu inni ddefnyddio’r un gweithdrefnau add-complex, sub-complex, mul-complex, ac div-complex o 2.4.1 fel y gweithrediadau mewnol.

(define (install-complex-package)
  ;; imported procedures from rectangular 
  ;; and polar packages
  (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))
  ;; internal procedures
  (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))))
  ;; interface to rest of the system
  (define (tag z) (attach-tag 'complex z))
  (put 'add '(complex complex)
       (lambda (z1 z2) 
         (tag (add-complex z1 z2))))
  (put 'sub '(complex complex)
       (lambda (z1 z2) 
         (tag (sub-complex z1 z2))))
  (put 'mul '(complex complex)
       (lambda (z1 z2) 
         (tag (mul-complex z1 z2))))
  (put 'div '(complex complex)
       (lambda (z1 z2) 
         (tag (div-complex z1 z2))))
  (put 'make-from-real-imag 'complex
       (lambda (x y) 
         (tag (make-from-real-imag x y))))
  (put 'make-from-mag-ang 'complex
       (lambda (r a) 
         (tag (make-from-mag-ang r a))))
  'done)

Gall rhaglenni y tu allan i’r pecyn rhifau cymhlyg adeiladu rhifau cymhlyg naill ai o rannau real a dychmygol neu o feintiau ac onglau. Sylwch sut y caiff y gweithdrefnau sylfaenol, a ddiffiniwyd yn wreiddiol yn y pecynnau petryalog a phegynol, eu hallforio i’r pecyn cymhlyg, a’u hallforio oddi yno i’r byd y tu allan.

(define (make-complex-from-real-imag x y)
  ((get 'make-from-real-imag 'complex) x y))
(define (make-complex-from-mag-ang r a)
  ((get 'make-from-mag-ang 'complex) r a))

Yr hyn sydd gennym yma yw system dagiau â dwy lefel. Byddai rhif cymhlyg nodweddiadol, megis $3 + 4 i$ ar ffurf betryalog, yn cael ei gynrychioli fel y dangosir yn Ffigur 2.24. Defnyddir y tag allanol (complex) i gyfeirio’r rhif at y pecyn cymhlyg. Unwaith y mae o fewn y pecyn cymhlyg, defnyddir y tag nesaf (rectangular) i gyfeirio’r rhif at y pecyn petryalog. Mewn system fawr a chymhleth gallai fod llawer o lefelau, pob un wedi’i chysylltu â’r nesaf drwy weithrediadau generig. Wrth i wrthrych data gael ei drosglwyddo “i lawr,” tynnir y tag allanol a ddefnyddir i’w gyfeirio at y pecyn priodol (drwy gymhwyso contents), a daw’r lefel nesaf o dag (os oes un) yn weladwy i’w defnyddio ar gyfer dethol pellach.

Ffigur 2.24: Cynrychioli $3 + 4 i$ ar ffurf betryalog.

Yn y pecynnau uchod, defnyddiasom add-rat, add-complex, a’r gweithdrefnau rhifyddol eraill yn union fel y’u hysgrifennwyd yn wreiddiol. Unwaith y mae’r diffiniadau hyn yn fewnol i weithdrefnau gosod gwahanol, fodd bynnag, nid oes angen enwau arnynt sy’n wahanol i’w gilydd mwyach: gallem eu henwi’n add, sub, mul, ac div yn y ddau becyn.

Ymarfer 2.77: Mae Louis Reasoner yn ceisio gwerthuso’r mynegiad (magnitude z) lle mai z yw’r gwrthrych a ddangosir yn Ffigur 2.24. Er mawr syndod iddo, yn lle’r ateb 5 mae’n cael neges wall gan apply-generic, yn dweud nad oes dull ar gyfer y gweithrediad magnitude ar y mathau (complex). Mae’n dangos y rhyngweithiad hwn i Alyssa P. Hacker, sy’n dweud “Y broblem yw na ddiffiniwyd y detholwyr rhifau cymhlyg erioed ar gyfer rhifau complex, dim ond ar gyfer rhifau polar ac rectangular. Y cyfan sydd angen ei wneud i beri i hyn weithio yw ychwanegu’r canlynol at y pecyn complex:”
(put 'real-part '(complex) real-part)
(put 'imag-part '(complex) imag-part)
(put 'magnitude '(complex) magnitude)
(put 'angle '(complex) angle)
Disgrifiwch yn fanwl pam mae hyn yn gweithio. Fel enghraifft, olrheiniwch yr holl weithdrefnau a alwir wrth werthuso’r mynegiad (magnitude z) lle mai z yw’r gwrthrych a ddangosir yn Ffigur 2.24. Yn benodol, sawl gwaith y gelwir apply-generic? Pa weithdrefn a ddetholir ym mhob achos?

Ymarfer 2.78: Yn ei hanfod, nid yw’r gweithdrefnau mewnol yn y pecyn scheme-number yn ddim mwy na galwadau i’r gweithdrefnau cyntefig +, -, ac ati. Nid oedd modd defnyddio gweithdrefnau cyntefig yr iaith yn uniongyrchol oherwydd bod ein system tagiau math yn gofyn bod math wedi’i atodi at bob gwrthrych data. Mewn gwirionedd, fodd bynnag, mae gan bob gweithrediad Lisp system fathau y mae’n ei defnyddio’n fewnol. Mae traethiadau cyntefig megis symbol? ac number? yn penderfynu a oes gan wrthrychau data fathau penodol. Addaswch ddiffiniadau type-tag, contents, ac attach-tag o 2.4.2 fel bod ein system generig yn manteisio ar system fathau fewnol Scheme. Hynny yw, dylai’r system weithio fel o’r blaen heblaw y dylid cynrychioli rhifau cyffredin fel rhifau Scheme yn unig yn hytrach na pharau y mae eu car yn symbol scheme-number.

Ymarfer 2.79: Diffiniwch draethiad hafaledd generig equ? sy’n profi hafaledd dau rif, a’i osod yn y pecyn rhifyddeg generig. Dylai’r gweithrediad hwn weithio ar gyfer rhifau cyffredin, rhifau cymarebol a rhifau cymhlyg.

Ymarfer 2.80: Diffiniwch draethiad generig =zero? sy’n profi a yw ei arg yn sero, a’i osod yn y pecyn rhifyddeg generig. Dylai’r gweithrediad hwn weithio ar gyfer rhifau cyffredin, rhifau cymarebol a rhifau cymhlyg.

2.5.2Cyfuno Data o Fathau Gwahanol

Rydym wedi gweld sut i ddiffinio system rhifyddeg unedig sy’n cwmpasu rhifau cyffredin, rhifau cymhlyg, rhifau cymarebol ac unrhyw fath arall o rif y gallem benderfynu ei ddyfeisio, ond rydym wedi anwybyddu mater pwysig. Mae’r gweithrediadau yr ydym wedi’u diffinio hyd yma yn trin y mathau data gwahanol fel rhai cwbl annibynnol. Felly, mae pecynnau ar wahân ar gyfer adio, dyweder, dau rif cyffredin, neu ddau rif cymhlyg. Yr hyn nad ydym eto wedi’i ystyried yw’r ffaith ei bod yn ystyrlon diffinio gweithrediadau sy’n croesi ffiniau mathau, megis adio rhif cymhlyg at rif cyffredin. Rydym wedi ymdrechu’n fawr i gyflwyno rhwystrau rhwng rhannau o’n rhaglenni fel y gellir eu datblygu a’u deall ar wahân. Hoffem gyflwyno’r gweithrediadau rhwng mathau mewn rhyw ffordd wedi’i rheoli’n ofalus, fel y gallwn eu cynnal heb dorri ffiniau ein modiwlau’n ddifrifol.

Un ffordd o drin gweithrediadau rhwng mathau yw dylunio gweithdrefn wahanol ar gyfer pob cyfuniad posibl o fathau y mae’r gweithrediad yn ddilys ar ei gyfer. Er enghraifft, gallem ymestyn y pecyn rhifau cymhlyg fel ei fod yn darparu gweithdrefn ar gyfer adio rhifau cymhlyg at rifau cyffredin ac yn gosod hon yn y tabl gan ddefnyddio’r tag (complex scheme-number):¹¹⁵

(define (add-complex-to-schemenum z x)
  (make-from-real-imag (+ (real-part z) x)
                       (imag-part z)))

(put 'add 
     '(complex scheme-number)
     (lambda (z x) 
       (tag (add-complex-to-schemenum z x))))

Mae’r dechneg hon yn gweithio, ond mae’n feichus. Gyda system o’r fath, nid adeiladu pecyn gweithdrefnau’r math hwnnw’n unig yw cost cyflwyno math newydd, ond hefyd adeiladu a gosod y gweithdrefnau sy’n gweithredu’r gweithrediadau rhwng mathau. Gall hyn yn hawdd fod yn llawer mwy o god nag sydd ei angen i ddiffinio’r gweithrediadau ar y math ei hun. Mae’r dull hefyd yn tanseilio ein gallu i gyfuno pecynnau ar wahân drwy ychwanegu, neu o leiaf i gyfyngu ar faint y mae angen i weithredwyr y pecynnau unigol ystyried pecynnau eraill. Er enghraifft, yn yr enghraifft uchod, mae’n ymddangos yn rhesymol mai cyfrifoldeb y pecyn rhifau cymhlyg ddylai trin gweithrediadau cymysg ar rifau cymhlyg a rhifau cyffredin fod. Fodd bynnag, gallai cyfuno rhifau cymarebol a rhifau cymhlyg gael ei wneud gan y pecyn cymhlyg, gan y pecyn cymarebol, neu gan ryw drydydd pecyn sy’n defnyddio gweithrediadau a echdynnwyd o’r ddau becyn hyn. Gall llunio polisïau cydlynol ar rannu cyfrifoldeb rhwng pecynnau fod yn dasg lethol wrth ddylunio systemau â llawer o becynnau a llawer o weithrediadau rhwng mathau.

Trosi math

Yn y sefyllfa gyffredinol o weithrediadau cwbl anghysylltiedig yn gweithredu ar fathau cwbl anghysylltiedig, gweithredu gweithrediadau rhwng mathau’n benodol, er mor feichus y gall fod, yw’r gorau y gellir gobeithio amdano. Yn ffodus, gallwn fel arfer wneud yn well drwy fanteisio ar strwythur ychwanegol a all fod yn gudd yn ein system fathau. Yn aml nid yw’r mathau data gwahanol yn gwbl annibynnol, a gall fod ffyrdd o ystyried gwrthrychau o un math fel rhai o fath arall. Gelwir y broses hon yn drosi math. Er enghraifft, os gofynnir inni gyfuno rhif cyffredin â rhif cymhlyg yn rhifyddol, gallwn ystyried y rhif cyffredin fel rhif cymhlyg y mae ei ran ddychmygol yn sero. Mae hyn yn trawsffurfio’r broblem i’r broblem o gyfuno dau rif cymhlyg, y gall y pecyn rhifyddeg gymhlyg ei thrin yn y ffordd arferol.

Yn gyffredinol, gallwn weithredu’r syniad hwn drwy ddylunio gweithdrefnau trosi math sy’n trawsffurfio gwrthrych o un math yn wrthrych cyfwerth o fath arall. Dyma weithdrefn trosi math nodweddiadol, sy’n trawsffurfio rhif cyffredin penodol yn rhif cymhlyg â’r rhan real honno a rhan ddychmygol o sero:

(define (scheme-number->complex n)
  (make-complex-from-real-imag 
   (contents n) 0))

Gosodwn y gweithdrefnau trosi math hyn mewn tabl trosi math arbennig, wedi’i fynegeio o dan enwau’r ddau fath:

(put-coercion 'scheme-number 'complex 
              scheme-number->complex)

(Tybiwn fod gweithdrefnau put-coercion ac get-coercion ar gael ar gyfer trin y tabl hwn.) Yn gyffredinol, bydd rhai o’r lleoedd yn y tabl yn wag, oherwydd nad yw’n bosibl yn gyffredinol drosi gwrthrych data mympwyol o bob math i bob math arall. Er enghraifft, nid oes ffordd o drosi rhif cymhlyg mympwyol yn rhif cyffredin, felly ni fydd gweithdrefn gyffredinol complex->scheme-number wedi’i chynnwys yn y tabl.

Unwaith y mae’r tabl trosi math wedi’i sefydlu, gallwn drin trosi math mewn ffordd unffurf drwy addasu gweithdrefn apply-generic 2.4.3. Pan ofynnir inni gymhwyso gweithrediad, gwiriwn yn gyntaf a yw’r gweithrediad wedi’i ddiffinio ar gyfer mathau’r argiau, yn union fel o’r blaen. Os ydyw, detholwn y weithdrefn a geir yn y tabl gweithrediadau a mathau. Fel arall, ceisiwn drosi math. Er symlrwydd, ystyriwn dim ond yr achos lle mae dau arg.¹¹⁶ Gwiriwn y tabl trosi math i weld a ellir trosi gwrthrychau o’r math cyntaf i’r ail fath. Os gellir, troswn yr arg cyntaf a rhoi cynnig arall ar y gweithrediad. Os na ellir yn gyffredinol drosi gwrthrychau o’r math cyntaf i’r ail fath, ceisiwn drosi i’r cyfeiriad arall i weld a oes ffordd o drosi’r ail arg i fath yr arg cyntaf. Yn olaf, os nad oes ffordd hysbys o drosi’r naill fath i’r llall, rhown y gorau iddi. Dyma’r weithdrefn:

(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))
          (if (= (length args) 2)
              (let ((type1 (car type-tags))
                    (type2 (cadr type-tags))
                    (a1 (car args))
                    (a2 (cadr args)))
                (let ((t1->t2 
                       (get-coercion type1
                                     type2))
                      (t2->t1 
                       (get-coercion type2 
                                     type1)))
                  (cond (t1->t2
                         (apply-generic 
                          op (t1->t2 a1) a2))
                        (t2->t1
                         (apply-generic 
                          op a1 (t2->t1 a2)))
                        (else
                         (error 
                          "No method for 
                           these types"
                          (list 
                           op 
                           type-tags))))))
              (error 
               "No method for these types"
               (list op type-tags)))))))

Mae gan y cynllun trosi math hwn lawer o fanteision dros y dull o ddiffinio gweithrediadau rhwng mathau’n benodol, fel yr amlinellwyd uchod. Er bod angen inni o hyd ysgrifennu gweithdrefnau trosi math i gysylltu’r mathau (o bosibl $n^{2}$ o weithdrefnau ar gyfer system â $n$ o fathau), dim ond un weithdrefn sydd angen ei hysgrifennu ar gyfer pob pâr o fathau yn hytrach na gweithdrefn wahanol ar gyfer pob casgliad o fathau a phob gweithrediad generig.¹¹⁷ Yr hyn yr ydym yn dibynnu arno yma yw’r ffaith bod y trawsffurfiad priodol rhwng mathau’n dibynnu ar y mathau eu hunain yn unig, ac nid ar y gweithrediad sydd i’w gymhwyso.

Ar y llaw arall, gall fod cymwysiadau nad yw ein cynllun trosi math yn ddigon cyffredinol ar eu cyfer. Hyd yn oed pan na ellir trosi’r naill wrthrych sydd i’w gyfuno i fath y llall, gall fod yn bosibl o hyd gyflawni’r gweithrediad drwy drosi’r ddau wrthrych i drydydd math. Er mwyn ymdrin â chymhlethdod o’r fath a dal i gadw modiwlaredd ein rhaglenni, mae fel arfer yn angenrheidiol adeiladu systemau sy’n manteisio ar ragor eto o strwythur yn y perthnasoedd rhwng mathau, fel y trafodwn nesaf.

Hierarchaethau mathau

Roedd y cynllun trosi math a gyflwynwyd uchod yn dibynnu ar fodolaeth perthnasoedd naturiol rhwng parau o fathau. Yn aml mae strwythur mwy “byd-eang” yn y ffordd y mae’r mathau gwahanol yn cysylltu â’i gilydd. Er enghraifft, tybiwch ein bod yn adeiladu system rhifyddeg generig i drin cyfanrifau, rhifau cymarebol, rhifau real a rhifau cymhlyg. Mewn system o’r fath, mae’n gwbl naturiol ystyried cyfanrif yn fath arbennig o rif cymarebol, sydd yn ei dro’n fath arbennig o rif real, sydd yn ei dro’n fath arbennig o rif cymhlyg. Yr hyn sydd gennym mewn gwirionedd yw hierarchaeth mathau, fel y’i gelwir, lle mae cyfanrifau, er enghraifft, yn is-fath o rifau cymarebol (h.y., gellir cymhwyso unrhyw weithrediad y gellir ei gymhwyso i rif cymarebol yn awtomatig i gyfanrif). I’r gwrthwyneb, dywedwn fod rhifau cymarebol yn ffurfio uwch-fath o gyfanrifau. Mae’r hierarchaeth benodol sydd gennym yma o fath syml iawn, lle mae gan bob math un uwch-fath ar y mwyaf ac un is-fath ar y mwyaf. Dangosir strwythur o’r fath, a elwir yn dŵr, yn Ffigur 2.25.

Ffigur 2.25: Tŵr o fathau.

Os oes gennym strwythur tŵr, yna gallwn symleiddio’n fawr y broblem o ychwanegu math newydd at yr hierarchaeth, gan nad oes ond angen inni bennu sut mae’r math newydd wedi’i ymgorffori yn yr uwch-fath nesaf uwch ei ben a sut mae’n uwch-fath i’r math oddi tano. Er enghraifft, os ydym am adio cyfanrif at rif cymhlyg, nid oes angen diffinio gweithdrefn trosi math arbennig integer->complex yn benodol. Yn lle hynny, diffiniwn sut y gellir trawsffurfio cyfanrif yn rhif cymarebol, sut y trawsffurfir rhif cymarebol yn rhif real, a sut y trawsffurfir rhif real yn rhif cymhlyg. Yna caniatawn i’r system drawsffurfio’r cyfanrif yn rhif cymhlyg drwy’r camau hyn ac yna adio’r ddau rif cymhlyg.

Gallwn ailddylunio ein gweithdrefn apply-generic fel a ganlyn: Ar gyfer pob math, mae angen darparu gweithdrefn raise, sy’n “codi” gwrthrychau o’r math hwnnw un lefel yn y tŵr. Yna, pan fo angen i’r system weithredu ar wrthrychau o fathau gwahanol, gall godi’r mathau is yn olynol nes bod yr holl wrthrychau ar yr un lefel yn y tŵr. (Mae Ymarfer 2.83 ac Ymarfer 2.84 yn ymdrin â manylion gweithredu strategaeth o’r fath.)

Mantais arall tŵr yw y gallwn weithredu’n hawdd y syniad bod pob math yn “etifeddu” yr holl weithrediadau a ddiffiniwyd ar uwch-fath. Er enghraifft, os na ddarparwn weithdrefn arbennig ar gyfer canfod rhan real cyfanrif, dylem serch hynny ddisgwyl y bydd real-part wedi’i ddiffinio ar gyfer cyfanrifau oherwydd bod cyfanrifau’n is-fath o rifau cymhlyg. Mewn tŵr, gallwn drefnu i hyn ddigwydd mewn ffordd unffurf drwy addasu apply-generic. Os nad yw’r gweithrediad gofynnol wedi’i ddiffinio’n uniongyrchol ar gyfer math y gwrthrych a roddwyd, codwn y gwrthrych i’w uwch-fath a rhoi cynnig arall arni. Felly ymgripiwn i fyny’r tŵr, gan drawsffurfio ein harg wrth fynd, nes inni naill ai ganfod lefel lle gellir cyflawni’r gweithrediad a ddymunir neu gyrraedd y brig (ac os felly rhown y gorau iddi).

Mantais arall eto sydd gan dŵr dros hierarchaeth fwy cyffredinol yw ei fod yn rhoi ffordd syml inni “ostwng” gwrthrych data i’r cynrychioliad symlaf. Er enghraifft, os adio $2 + 3 i$ at $4 - 3 i$ a wnawn, byddai’n braf cael yr ateb fel y cyfanrif 6 yn hytrach nag fel y rhif cymhlyg $6 + 0 i$ . Mae Ymarfer 2.85 yn trafod ffordd o weithredu gweithrediad gostwng o’r fath. (Y tric yw bod angen ffordd gyffredinol o wahaniaethu rhwng y gwrthrychau y gellir eu gostwng, megis $6 + 0 i$ , a’r rhai na ellir eu gostwng, megis $6 + 2 i$ .)

Diffygion hierarchaethau

Os gellir trefnu’r mathau data yn ein system yn naturiol mewn tŵr, mae hyn yn symleiddio’n fawr y problemau o ymdrin â gweithrediadau generig ar fathau gwahanol, fel y gwelsom. Yn anffodus, nid felly y mae fel arfer. Mae Ffigur 2.26 yn dangos trefniant mwy cymhleth o fathau cymysg, hwn yn dangos perthnasoedd rhwng gwahanol fathau o ffigurau geometrig. Gwelwn y gall math, yn gyffredinol, gael mwy nag un is-fath. Mae trionglau a phedrochrau, er enghraifft, ill dau’n is-fathau o bolygonau. Yn ogystal, gall math gael mwy nag un uwch-fath. Er enghraifft, gellir ystyried triongl isosgeles ongl sgwâr naill ai’n driongl isosgeles neu’n driongl ongl sgwâr. Mae’r mater hwn o uwch-fathau lluosog yn arbennig o ddyrys, gan ei fod yn golygu nad oes un ffordd unigryw o “godi” math yn yr hierarchaeth. Gall canfod yr uwch-fath “cywir” lle dylid cymhwyso gweithrediad i wrthrych olygu bod gweithdrefn megis apply-generic yn gorfod chwilio cryn dipyn drwy’r rhwydwaith mathau cyfan. Gan fod gan fath is-fathau lluosog yn gyffredinol, ceir problem debyg wrth drosi gwerth “i lawr” hierarchaeth y mathau. Mae ymdrin â nifer fawr o fathau cydgysylltiedig gan ddal i gadw modiwlaredd wrth ddylunio systemau mawr yn anodd iawn, ac mae’n faes lle mae llawer o ymchwil gyfredol.¹¹⁸

Ffigur 2.26: Perthnasoedd rhwng mathau o ffigurau geometrig.

Ymarfer 2.81: Mae Louis Reasoner wedi sylwi y gall apply-generic geisio trosi’r argiau i fath ei gilydd hyd yn oed os ydynt eisoes o’r un math. Felly, mae’n rhesymu, mae angen rhoi gweithdrefnau yn y tabl trosi math i drosi argiau o bob math i’w math eu hunain. Er enghraifft, yn ogystal â’r trosiad scheme-number->complex a ddangoswyd uchod, byddai’n gwneud:
(define (scheme-number->scheme-number n) n)
(define (complex->complex z) z)

(put-coercion 'scheme-number 'scheme-number
              scheme-number->scheme-number)

(put-coercion 'complex 'complex 
              complex->complex)
Gyda gweithdrefnau trosi math Louis wedi’u gosod, beth sy’n digwydd os gelwir apply-generic â dau arg o fath scheme-number neu ddau arg o fath complex ar gyfer gweithrediad nad yw i’w gael yn y tabl ar gyfer y mathau hynny? Er enghraifft, tybiwch ein bod wedi diffinio gweithrediad generig ar gyfer codi i bŵer:
(define (exp x y) 
  (apply-generic 'exp x y))
ac wedi rhoi gweithdrefn ar gyfer codi i bŵer yn y pecyn rhifau Scheme ond nid mewn unrhyw becyn arall:
;; following added to Scheme-number package
(put 'exp 
     '(scheme-number scheme-number)
     (lambda (x y) 
       (tag (expt x y)))) 
       ; using primitive expt
Beth sy’n digwydd os galwn exp â dau rif cymhlyg yn argiau?
A yw Louis yn gywir bod rhaid gwneud rhywbeth ynghylch trosi math ag argiau o’r un math, ynteu a yw apply-generic yn gweithio’n gywir fel y mae?
Addaswch apply-generic fel nad yw’n ceisio trosi math os yw’r ddau arg o’r un math.

Ymarfer 2.82: Dangoswch sut i gyffredinoli apply-generic i drin trosi math yn achos cyffredinol argiau lluosog. Un strategaeth yw ceisio trosi’r holl argiau i fath yr arg cyntaf, yna i fath yr ail arg, ac ati. Rhowch enghraifft o sefyllfa lle nad yw’r strategaeth hon (ac yn yr un modd y fersiwn â dau arg a roddwyd uchod) yn ddigon cyffredinol. (Awgrym: Ystyriwch yr achos lle mae rhai gweithrediadau addas ar fathau cymysg yn bresennol yn y tabl na roddir cynnig arnynt.)

Ymarfer 2.83: Tybiwch eich bod yn dylunio system rhifyddeg generig ar gyfer ymdrin â’r tŵr o fathau a ddangosir yn Ffigur 2.25: cyfanrif, cymarebol, real, cymhlyg. Ar gyfer pob math (heblaw cymhlyg), dyluniwch weithdrefn sy’n codi gwrthrychau o’r math hwnnw un lefel yn y tŵr. Dangoswch sut i osod gweithrediad generig raise a fydd yn gweithio ar gyfer pob math (heblaw cymhlyg).

Ymarfer 2.84: Gan ddefnyddio gweithrediad raise Ymarfer 2.83, addaswch y weithdrefn apply-generic fel ei bod yn trosi ei hargiau i’r un math drwy’r dull o godi’n olynol, fel y trafodwyd yn yr adran hon. Bydd angen ichi ddyfeisio ffordd o brofi pa un o ddau fath sydd uwch yn y tŵr. Gwnewch hyn mewn ffordd sy’n “gydnaws” â gweddill y system ac na fydd yn arwain at broblemau wrth ychwanegu lefelau newydd at y tŵr.

Ymarfer 2.85: Soniodd yr adran hon am ddull o “symleiddio” gwrthrych data drwy ei ostwng mor bell â phosibl yn y tŵr o fathau. Dyluniwch weithdrefn drop sy’n cyflawni hyn ar gyfer y tŵr a ddisgrifiwyd yn Ymarfer 2.83. Yr allwedd yw penderfynu, mewn rhyw ffordd gyffredinol, a ellir gostwng gwrthrych. Er enghraifft, gellir gostwng y rhif cymhlyg $1.5 + 0 i$ cyn belled ag real, gellir gostwng y rhif cymhlyg $1 + 0 i$ cyn belled ag integer, ac ni ellir gostwng y rhif cymhlyg $2 + 3 i$ o gwbl. Dyma gynllun ar gyfer penderfynu a ellir gostwng gwrthrych: Dechreuwch drwy ddiffinio gweithrediad generig project sy’n “gwthio” gwrthrych i lawr y tŵr. Er enghraifft, byddai taflunio rhif cymhlyg yn cynnwys taflu’r rhan ddychmygol i ffwrdd. Yna gellir gostwng rhif os yw cymhwyso project iddo ac raise i’r canlyniad i’w godi’n ôl i’r math y dechreuasom ag ef yn rhoi rhywbeth sy’n hafal i’r hyn y dechreuasom ag ef. Dangoswch yn fanwl sut i weithredu’r syniad hwn, drwy ysgrifennu gweithdrefn drop sy’n gostwng gwrthrych mor bell â phosibl. Bydd angen ichi ddylunio’r amrywiol weithrediadau taflunio¹¹⁹ a gosod project yn weithrediad generig yn y system. Bydd angen hefyd ddefnyddio traethiad hafaledd generig, megis yr un a ddisgrifiwyd yn Ymarfer 2.79. Yn olaf, defnyddiwch drop i ailysgrifennu apply-generic o Ymarfer 2.84 fel ei fod yn “symleiddio” ei atebion.

Ymarfer 2.86: Tybiwch ein bod am drin rhifau cymhlyg y gall eu rhannau real, rhannau dychmygol, meintiau ac onglau fod naill ai’n rhifau cyffredin, yn rhifau cymarebol, neu’n rifau eraill y gallem ddymuno eu hychwanegu at y system. Disgrifiwch a gweithredwch y newidiadau i’r system sydd eu hangen i ganiatáu hyn. Bydd rhaid ichi ddiffinio gweithrediadau megis sine ac cosine sy’n generig dros rifau cyffredin a rhifau cymarebol.

2.5.3Enghraifft: Algebra Symbolaidd

Mae trin mynegiadau algebraidd symbolaidd yn broses gymhleth sy’n dangos llawer o’r problemau anoddaf sy’n codi wrth ddylunio systemau ar raddfa fawr. Yn gyffredinol, gellir ystyried mynegiad algebraidd yn strwythur hierarchaidd, yn goeden o weithredyddion wedi’u cymhwyso i operandau. Gallwn adeiladu mynegiadau algebraidd drwy ddechrau â set o wrthrychau cyntefig, megis cysonion a newidynnau, a’u cyfuno drwy weithredyddion algebraidd, megis adio a lluosi. Fel mewn ieithoedd eraill, ffurfiwn haniaethau sy’n ein galluogi i gyfeirio at wrthrychau cyfansawdd mewn termau syml. Mae haniaethau nodweddiadol mewn algebra symbolaidd yn cynnwys syniadau megis cyfuniad llinol, polynomial, ffwythiant cymarebol, neu ffwythiant trigonometrig. Gallwn ystyried y rhain yn “fathau” cyfansawdd, sy’n aml yn ddefnyddiol ar gyfer cyfarwyddo prosesu mynegiadau. Er enghraifft, gallem ddisgrifio’r mynegiad $x^{2} \sin (y^{2} + 1) + x \cos 2 y + \cos (y^{3} - 2 y^{2})$ fel polynomial mewn $x$ â chyfernodau sy’n ffwythiannau trigonometrig o bolynomialau mewn $y$ y mae eu cyfernodau’n gyfanrifau.

Ni fyddwn yn ceisio datblygu system gyflawn ar gyfer trin algebra yma. Mae systemau o’r fath yn rhaglenni hynod gymhleth, sy’n ymgorffori gwybodaeth algebraidd ddofn ac algorithmau cain. Yr hyn a wnawn yw edrych ar ran syml ond pwysig o drin algebra: rhifyddeg polynomialau. Byddwn yn dangos y mathau o benderfyniadau sy’n wynebu dylunydd system o’r fath, a sut i gymhwyso syniadau data haniaethol a gweithrediadau generig i helpu i drefnu’r ymdrech hon.

Rhifyddeg ar bolynomialau

Ein tasg gyntaf wrth ddylunio system ar gyfer cyflawni rhifyddeg ar bolynomialau yw penderfynu beth yn union yw polynomial. Fel arfer diffinnir polynomialau mewn perthynas â newidynnau penodol ( newidynnau ffurfiol y polynomial, neu indeterminates). Er symlrwydd, byddwn yn cyfyngu ein hunain i bolynomialau ag un newidyn ffurfiol yn unig ( polynomialau unnewidyn).¹²⁰ Diffiniwn bolynomial yn swm o dermau, pob un ohonynt naill ai’n gyfernod, yn bŵer o’r newidyn ffurfiol, neu’n lluoswm cyfernod a phŵer o’r newidyn ffurfiol. Diffinnir cyfernod yn fynegiad algebraidd nad yw’n dibynnu ar newidyn ffurfiol y polynomial. Er enghraifft, mae $5 x^{2} + 3 x + 7$ yn bolynomial syml mewn $x$ , ac mae $(y^{2} + 1) x^{3} + (2 y) x + 1$ yn bolynomial mewn $x$ y mae ei gyfernodau’n bolynomialau mewn $y$ .

Rydym eisoes yn osgoi rhai materion dyrys. A yw’r cyntaf o’r polynomialau hyn yr un fath â’r polynomial $5 y^{2} + 3 y + 7$ , ai peidio? Ateb rhesymol fyddai “ydyw, os ydym yn ystyried polynomial fel ffwythiant mathemategol yn unig, ond nac ydyw, os ydym yn ystyried polynomial yn ffurf gystrawennol.” Mae’r ail bolynomial yn gyfwerth yn algebraidd â pholynomial mewn $y$ y mae ei gyfernodau’n bolynomialau mewn $x$ . A ddylai ein system gydnabod hyn, ai peidio? Ymhellach, mae ffyrdd eraill o gynrychioli polynomial—er enghraifft, fel lluoswm ffactorau, neu (ar gyfer polynomial unnewidyn) fel y set o wreiddiau, neu fel rhestr o werthoedd y polynomial mewn set benodedig o bwyntiau.¹²¹ Gallwn osgoi’r cwestiynau hyn drwy benderfynu mai ffurf gystrawennol benodol fydd “polynomial” yn ein system trin algebra, ac nid ei ystyr fathemategol sylfaenol.

Yn awr rhaid inni ystyried sut i fynd ati i gyflawni rhifyddeg ar bolynomialau. Yn y system syml hon, dim ond adio a lluosi a ystyriwn. Ymhellach, byddwn yn mynnu bod gan ddau bolynomial sydd i’w cyfuno yr un newidyn ffurfiol.

Awn ati i ddylunio ein system drwy ddilyn disgyblaeth gyfarwydd haniaethu data. Cynrychiolwn bolynomialau gan ddefnyddio strwythur data o’r enw poly, sy’n cynnwys newidyn a chasgliad o dermau. Tybiwn fod gennym ddetholwyr variable ac term-list sy’n echdynnu’r rhannau hynny o poly ac adeiladydd make-poly sy’n cydosod poly o newidyn penodol a rhestr dermau. Symbol yn unig fydd newidyn, felly gallwn ddefnyddio gweithdrefn same-variable? 2.3.2 i gymharu newidynnau. Mae’r gweithdrefnau canlynol yn diffinio adio a lluosi gwrthrychau poly:

(define (add-poly p1 p2)
  (if (same-variable? (variable p1) 
                      (variable p2))
      (make-poly 
       (variable p1)
       (add-terms (term-list p1)
                  (term-list p2)))
      (error "Polys not in same var: 
              ADD-POLY"
             (list p1 p2))))

(define (mul-poly p1 p2)
  (if (same-variable? (variable p1) 
                      (variable p2))
      (make-poly 
       (variable p1)
       (mul-terms (term-list p1)
                  (term-list p2)))
      (error "Polys not in same var: 
              MUL-POLY"
             (list p1 p2))))

I gynnwys polynomialau yn ein system rhifyddeg generig, mae angen darparu tagiau math ar eu cyfer. Byddwn yn defnyddio’r tag polynomial, ac yn gosod gweithrediadau priodol ar bolynomialau â thagiau yn y tabl gweithrediadau. Byddwn yn ymgorffori ein holl god mewn gweithdrefn osod ar gyfer y pecyn polynomialau, yn debyg i’r rhai yn 2.5.1:

(define (install-polynomial-package)
  ;; internal procedures
  ;; representation of poly
  (define (make-poly variable term-list)
    (cons variable term-list))
  (define (variable p) (car p))
  (define (term-list p) (cdr p))
  ⟨procedures same-variable? 
   and variable? from section 2.3.2⟩

  ;; representation of terms and term lists
  ⟨procedures adjoin-term … coeff 
  from text below⟩

  (define (add-poly p1 p2) …)
  ⟨procedures used by add-poly⟩
  (define (mul-poly p1 p2) …)
  ⟨procedures used by mul-poly⟩

  ;; interface to rest of the system
  (define (tag p) (attach-tag 'polynomial p))
  (put 'add '(polynomial polynomial)
       (lambda (p1 p2) 
         (tag (add-poly p1 p2))))
  (put 'mul '(polynomial polynomial)
       (lambda (p1 p2) 
         (tag (mul-poly p1 p2))))
  (put 'make 'polynomial
       (lambda (var terms) 
         (tag (make-poly var terms))))
  'done)

Cyflawnir adio polynomialau fesul term. Rhaid cyfuno termau o’r un radd (h.y., â’r un pŵer o’r newidyn ffurfiol). Gwneir hyn drwy ffurfio term newydd o’r un radd y mae ei gyfernod yn swm cyfernodau’r termau sy’n cael eu hadio. Mae termau yn un polynomial sy’n cael ei adio nad oes termau o’r un radd ar eu cyfer yn y polynomial arall yn cael eu cronni’n syml i mewn i’r polynomial swm sy’n cael ei adeiladu.

Er mwyn trin rhestrau termau, tybiwn fod gennym adeiladydd the-empty-termlist sy’n dychwelyd rhestr dermau wag ac adeiladydd adjoin-term sy’n atodi term newydd at restr dermau. Tybiwn hefyd fod gennym draethiad empty-termlist? sy’n dweud a yw rhestr dermau benodol yn wag, detholwr first-term sy’n echdynnu’r term o’r radd uchaf o restr dermau, a detholwr rest-terms sy’n dychwelyd popeth heblaw’r term o’r radd uchaf. I drin termau, tybiwn fod gennym adeiladydd make-term sy’n adeiladu term â gradd a chyfernod penodol, a detholwyr order ac coeff sy’n dychwelyd gradd a chyfernod y term, yn y drefn honno. Mae’r gweithrediadau hyn yn ein galluogi i ystyried termau a rhestrau termau yn haniaethau data, y gallwn ymdrin â’u cynrychioliadau pendant ar wahân.

Dyma’r weithdrefn sy’n adeiladu’r rhestr dermau ar gyfer swm dau bolynomial:¹²²

(define (add-terms L1 L2)
  (cond ((empty-termlist? L1) L2)
        ((empty-termlist? L2) L1)
        (else
         (let ((t1 (first-term L1)) 
               (t2 (first-term L2)))
           (cond ((> (order t1) (order t2))
                  (adjoin-term
                   t1 
                   (add-terms (rest-terms L1) 
                              L2)))
                 ((< (order t1) (order t2))
                  (adjoin-term
                   t2 
                   (add-terms 
                    L1 
                    (rest-terms L2))))
                 (else
                  (adjoin-term
                   (make-term 
                    (order t1)
                    (add (coeff t1) 
                         (coeff t2)))
                   (add-terms 
                    (rest-terms L1)
                    (rest-terms L2)))))))))

Y pwynt pwysicaf i’w nodi yma yw ein bod wedi defnyddio’r weithdrefn adio generig add i adio cyfernodau’r termau sy’n cael eu cyfuno. Mae gan hyn ganlyniadau pwerus, fel y gwelwn isod.

Er mwyn lluosi dwy restr dermau, lluoswn bob term o’r rhestr gyntaf â holl dermau’r rhestr arall, gan ddefnyddio mul-term-by-all-terms dro ar ôl tro, sy’n lluosi term penodol â phob term mewn rhestr dermau benodol. Cronnir y rhestrau termau sy’n deillio o hyn (un ar gyfer pob term o’r rhestr gyntaf) yn swm. Mae lluosi dau derm yn ffurfio term y mae ei radd yn swm graddau’r ffactorau a’i gyfernod yn lluoswm cyfernodau’r ffactorau:

(define (mul-terms L1 L2)
  (if (empty-termlist? L1)
      (the-empty-termlist)
      (add-terms 
       (mul-term-by-all-terms 
        (first-term L1) L2)
       (mul-terms (rest-terms L1) L2))))

(define (mul-term-by-all-terms t1 L)
  (if (empty-termlist? L)
      (the-empty-termlist)
      (let ((t2 (first-term L)))
        (adjoin-term
         (make-term 
          (+ (order t1) (order t2))
          (mul (coeff t1) (coeff t2)))
         (mul-term-by-all-terms 
          t1 
          (rest-terms L))))))

Dyna’r cyfan sydd mewn gwirionedd i adio a lluosi polynomialau. Sylwch, gan ein bod yn gweithredu ar dermau drwy’r gweithdrefnau generig add ac mul, fod ein pecyn polynomialau’n gallu trin yn awtomatig unrhyw fath o gyfernod y mae’r pecyn rhifyddeg generig yn gwybod amdano. Os cynhwyswn fecanwaith trosi math megis un o’r rhai a drafodwyd yn 2.5.2, yna gallwn hefyd drin yn awtomatig weithrediadau ar bolynomialau â chyfernodau o fathau gwahanol, megis $[3 x^{2} + (2 + 3 i) x + 7] \cdot [x^{4} + \frac{2}{3} x^{2} + (5 + 3 i)] .$ Gan inni osod y gweithdrefnau adio a lluosi polynomialau add-poly ac mul-poly yn y system rhifyddeg generig fel y gweithrediadau add ac mul ar gyfer math polynomial, mae ein system hefyd yn gallu trin yn awtomatig weithrediadau polynomialau megis $[(y + 1) x^{2} + (y^{2} + 1) x + (y - 1)] \cdot [(y - 2) x + (y^{3} + 7)] .$ Y rheswm yw, pan fydd y system yn ceisio cyfuno cyfernodau, y bydd yn dethol gweithdrefn drwy add ac mul. Gan fod y cyfernodau eu hunain yn bolynomialau (mewn $y$ ), cânt eu cyfuno drwy add-poly ac mul-poly. Y canlyniad yw rhyw fath o “ddychweliad a gyfarwyddir gan ddata” lle bydd, er enghraifft, galwad i mul-poly yn arwain at alwadau dychweliadol i mul-poly er mwyn lluosi’r cyfernodau. Pe bai cyfernodau’r cyfernodau eu hunain yn bolynomialau (fel y gellid eu defnyddio i gynrychioli polynomialau mewn tri newidyn), byddai’r cyfarwyddo gan ddata’n sicrhau y byddai’r system yn mynd drwy lefel arall o alwadau dychweliadol, ac felly ymlaen drwy gynifer o lefelau ag y mae strwythur y data’n ei bennu.¹²³

Cynrychioli rhestrau termau

Yn olaf, rhaid inni wynebu’r dasg o weithredu cynrychioliad da ar gyfer rhestrau termau. Mewn gwirionedd, set o gyfernodau â gradd y term yn allwedd iddynt yw rhestr dermau. Felly, gellir cymhwyso unrhyw un o’r dulliau o gynrychioli setiau, fel y’u trafodwyd yn 2.3.3, i’r dasg hon. Ar y llaw arall, mae ein gweithdrefnau add-terms ac mul-terms bob amser yn cyrchu rhestrau termau’n ddilyniannol o’r radd uchaf i’r isaf. Felly, byddwn yn defnyddio rhyw fath o gynrychioliad â rhestr drefnedig.

Sut y dylem strwythuro’r rhestr sy’n cynrychioli rhestr dermau? Un ystyriaeth yw “dwysedd” y polynomialau y bwriadwn eu trin. Dywedir bod polynomial yn ddwys os oes ganddo gyfernodau ansero mewn termau o’r rhan fwyaf o raddau. Os oes ganddo lawer o dermau sero, dywedir ei fod yn denau. Er enghraifft, polynomial dwys yw $A : x^{5} + 2 x^{4} + 3 x^{2} - 2 x - 5$ , tra bo $B : x^{100} + 2 x^{2} + 1$ yn denau.

Y ffordd fwyaf effeithlon o gynrychioli rhestrau termau polynomialau dwys yw fel rhestrau o’r cyfernodau. Er enghraifft, byddai $A$ uchod yn cael ei gynrychioli’n dda fel (1 2 0 3 -2 -5). Gradd term yn y cynrychioliad hwn yw hyd yr is-restr sy’n dechrau â chyfernod y term hwnnw, wedi’i leihau gan 1.¹²⁴ Byddai hwn yn gynrychioliad ofnadwy ar gyfer polynomial tenau megis $B$ : Byddai rhestr anferth o seros gydag ambell derm ansero unig rhyngddynt. Cynrychioliad mwy rhesymol o restr dermau polynomial tenau yw rhestr o’r termau ansero, lle mae pob term yn rhestr sy’n cynnwys gradd y term a’r cyfernod ar gyfer y radd honno. Mewn cynllun o’r fath, cynrychiolir y polynomial $B$ yn effeithlon fel ((100 1) (2 2) (0 1)). Gan fod y rhan fwyaf o drin polynomialau’n digwydd ar bolynomialau tenau, defnyddiwn y dull hwn. Tybiwn fod rhestrau termau wedi’u cynrychioli fel rhestrau o dermau, wedi’u trefnu o’r term o’r radd uchaf i’r term o’r radd isaf. Unwaith y gwnaethom y penderfyniad hwn, mae gweithredu’r detholwyr a’r adeiladyddion ar gyfer termau a rhestrau termau’n syml:¹²⁵

(define (adjoin-term term term-list)
  (if (=zero? (coeff term))
      term-list
      (cons term term-list)))
(define (the-empty-termlist) '())
(define (first-term term-list) (car term-list))
(define (rest-terms term-list) (cdr term-list))
(define (empty-termlist? term-list) 
  (null? term-list))
(define (make-term order coeff) 
  (list order coeff))
(define (order term) (car term))
(define (coeff term) (cadr term))

lle mae =zero? fel y’i diffiniwyd yn Ymarfer 2.80. (Gweler hefyd Ymarfer 2.87 isod.)

Bydd defnyddwyr y pecyn polynomialau’n creu polynomialau (â thagiau) drwy’r weithdrefn:

(define (make-polynomial var terms)
  ((get 'make 'polynomial) var terms))

Ymarfer 2.87: Gosodwch =zero? ar gyfer polynomialau yn y pecyn rhifyddeg generig. Bydd hyn yn caniatáu i adjoin-term weithio ar gyfer polynomialau â chyfernodau sydd eu hunain yn bolynomialau.

Ymarfer 2.88: Ymestynnwch y system polynomialau i gynnwys tynnu polynomialau. (Awgrym: Efallai y bydd yn ddefnyddiol diffinio gweithrediad newid arwydd generig.)

Ymarfer 2.89: Diffiniwch weithdrefnau sy’n gweithredu’r cynrychioliad o restrau termau a ddisgrifiwyd uchod fel un priodol ar gyfer polynomialau dwys.

Ymarfer 2.90: Tybiwch ein bod am gael system polynomialau sy’n effeithlon ar gyfer polynomialau tenau a dwys. Un ffordd o wneud hyn yw caniatáu’r ddau fath o gynrychioliad rhestrau termau yn ein system. Mae’r sefyllfa’n gyfatebol i’r enghraifft o rifau cymhlyg yn 2.4, lle caniatawyd cynrychioliadau petryalog a phegynol. I wneud hyn rhaid inni wahaniaethu rhwng gwahanol fathau o restrau termau a gwneud y gweithrediadau ar restrau termau’n generig. Ailddyluniwch y system polynomialau i weithredu’r cyffredinoliad hwn. Mae hon yn ymdrech fawr, nid newid lleol.

Ymarfer 2.91: Gellir rhannu polynomial unnewidyn ag un arall i gynhyrchu cyniferydd polynomial a gweddill polynomial. Er enghraifft, $\frac{x^{5} - 1}{x^{2} - 1} = x^{3} + x, remainder x - 1.$ Gellir cyflawni rhannu drwy rannu hir. Hynny yw, rhannwch derm o’r radd uchaf y rhannyn â therm o’r radd uchaf y rhannydd. Y canlyniad yw term cyntaf y cyniferydd. Nesaf, lluoswch y canlyniad â’r rhannydd, tynnwch hwnnw o’r rhannyn, a chynhyrchwch weddill yr ateb drwy rannu’r gwahaniaeth â’r rhannydd yn ddychweliadol. Stopiwch pan fo gradd y rhannydd yn fwy na gradd y rhannyn a datgan mai’r rhannyn yw’r gweddill. Hefyd, os daw’r rhannyn byth yn sero, dychwelwch sero fel y cyniferydd a’r gweddill.

Gallwn ddylunio gweithdrefn div-poly ar fodel add-poly ac mul-poly. Mae’r weithdrefn yn gwirio a oes gan y ddau wrthrych poly yr un newidyn. Os oes, mae div-poly yn tynnu’r newidyn ac yn trosglwyddo’r broblem i div-terms, sy’n cyflawni’r gweithrediad rhannu ar restrau termau. Yn olaf, mae Div-poly yn ailatodi’r newidyn at y canlyniad a ddarperir gan div-terms. Mae’n gyfleus dylunio div-terms i gyfrifo cyniferydd a gweddill rhaniad. Gall Div-terms gymryd dwy restr dermau yn argiau a dychwelyd rhestr sy’n cynnwys rhestr dermau’r cyniferydd a rhestr dermau’r gweddill.

Cwblhewch y diffiniad canlynol o div-terms drwy lenwi’r mynegiadau coll. Defnyddiwch hwn i weithredu div-poly, sy’n cymryd dau wrthrych poly yn argiau ac yn dychwelyd rhestr o wrthrychau poly y cyniferydd a’r gweddill.
(define (div-terms L1 L2)
  (if (empty-termlist? L1)
      (list (the-empty-termlist) 
            (the-empty-termlist))
      (let ((t1 (first-term L1))
            (t2 (first-term L2)))
        (if (> (order t2) (order t1))
            (list (the-empty-termlist) L1)
            (let ((new-c (div (coeff t1) 
                              (coeff t2)))
                  (new-o (- (order t1) 
                            (order t2))))
              (let ((rest-of-result
                     ⟨compute rest of result 
                     recursively⟩ ))
                ⟨form complete result⟩ ))))))

Hierarchaethau mathau mewn algebra symbolaidd

Mae ein system polynomialau’n dangos sut y gall gwrthrychau o un math (polynomialau) mewn gwirionedd fod yn wrthrychau cymhleth sydd â gwrthrychau o lawer o fathau gwahanol yn rhannau iddynt. Nid yw hyn yn creu anhawster gwirioneddol wrth ddiffinio gweithrediadau generig. Dim ond gosod gweithrediadau generig priodol sydd ei angen i gyflawni’r trin angenrheidiol ar rannau’r mathau cyfansawdd. Yn wir, gwelsom fod polynomialau’n ffurfio rhyw fath o “haniaeth data ddychweliadol,” gan y gall rhannau o bolynomial fod yn bolynomialau eu hunain. Gall ein gweithrediadau generig a’n dull rhaglennu a gyfarwyddir gan ddata drin y cymhlethdod hwn heb lawer o drafferth.

Ar y llaw arall, system yw algebra polynomialau lle na ellir trefnu’r mathau data’n naturiol mewn tŵr. Er enghraifft, mae’n bosibl cael polynomialau mewn $x$ y mae eu cyfernodau’n bolynomialau mewn $y$ . Mae hefyd yn bosibl cael polynomialau mewn $y$ y mae eu cyfernodau’n bolynomialau mewn $x$ . Nid yw’r naill fath na’r llall “uwchben” y llall mewn unrhyw ffordd naturiol, ond yn aml mae angen adio elfennau o’r ddwy set. Mae sawl ffordd o wneud hyn. Un posibilrwydd yw trosi un polynomial i fath y llall drwy ehangu ac aildrefnu termau fel bod gan y ddau bolynomial yr un prif newidyn. Gellir gosod strwythur tebyg i dŵr ar hyn drwy drefnu’r newidynnau ac felly bob amser drosi unrhyw bolynomial i “ffurf ganonaidd” â’r newidyn sydd â’r flaenoriaeth uchaf yn flaenllaw a’r newidynnau â blaenoriaeth is wedi’u claddu yn y cyfernodau. Mae’r strategaeth hon yn gweithio’n weddol dda, heblaw y gall y trosiad ehangu polynomial yn ddiangen, gan ei wneud yn anodd ei ddarllen ac efallai’n llai effeithlon i weithio ag ef. Yn sicr nid yw strategaeth y tŵr yn naturiol ar gyfer y maes hwn nac unrhyw faes lle gall y defnyddiwr ddyfeisio mathau newydd yn ddeinamig gan ddefnyddio hen fathau mewn amrywiol ffurfiau cyfuno, megis ffwythiannau trigonometrig, cyfresi pŵer ac integrynnau.

Ni ddylai fod yn syndod bod rheoli trosi math yn broblem ddifrifol wrth ddylunio systemau trin algebra ar raddfa fawr. Mae llawer o gymhlethdod systemau o’r fath yn ymwneud â pherthnasoedd rhwng mathau amrywiol. Yn wir, mae’n deg dweud nad ydym eto’n deall trosi math yn llwyr. Mewn gwirionedd, nid ydym eto’n deall cysyniad math data yn llwyr. Serch hynny, mae’r hyn a wyddom yn rhoi inni egwyddorion pwerus ar gyfer strwythuro a modiwlaredd i gefnogi dylunio systemau mawr.

Ymarfer 2.92: Drwy osod trefn ar newidynnau, ymestynnwch y pecyn polynomialau fel bod adio a lluosi polynomialau’n gweithio ar gyfer polynomialau mewn newidynnau gwahanol. (Nid yw hyn yn hawdd!)

Ymarfer estynedig: Ffwythiannau cymarebol

Gallwn ymestyn ein system rhifyddeg generig i gynnwys ffwythiannau cymarebol. Mae’r rhain yn “ffracsiynau” y mae eu rhifiadur a’u henwadur yn bolynomialau, megis $\frac{x + 1}{x^{3} - 1} .$ Dylai’r system allu adio, tynnu, lluosi a rhannu ffwythiannau cymarebol, a chyflawni cyfrifiadau megis $\frac{x + 1}{x^{3} - 1} + \frac{x}{x^{2} - 1} = \frac{x^{3} + 2 x^{2} + 3 x + 1}{x^{4} + x^{3} - x - 1} .$ (Yma symleiddiwyd y swm drwy dynnu ffactorau cyffredin. Byddai “trawsluosi” arferol wedi cynhyrchu polynomial pedwaredd radd dros bolynomial pumed radd.)

Os addaswn ein pecyn rhifyddeg gymarebol fel ei fod yn defnyddio gweithrediadau generig, yna bydd yn gwneud yr hyn a ddymunwn, heblaw am y broblem o leihau ffracsiynau i’w ffurf symlaf.

Ymarfer 2.93: Addaswch y pecyn rhifyddeg gymarebol i ddefnyddio gweithrediadau generig, ond newidiwch make-rat fel nad yw’n ceisio lleihau ffracsiynau i’w ffurf symlaf. Profwch eich system drwy alw make-rational ar ddau bolynomial i gynhyrchu ffwythiant cymarebol:
(define p1 (make-polynomial 'x '((2 1) (0 1))))
(define p2 (make-polynomial 'x '((3 1) (0 1))))
(define rf (make-rational p2 p1))
Yn awr adiwch rf ato’i hun, gan ddefnyddio add. Byddwch yn sylwi nad yw’r weithdrefn adio hon yn lleihau ffracsiynau i’w ffurf symlaf.

Gallwn leihau ffracsiynau polynomial i’w ffurf symlaf gan ddefnyddio’r un syniad ag a ddefnyddiasom gyda chyfanrifau: addasu make-rat i rannu’r rhifiadur a’r enwadur â’u rhannydd cyffredin mwyaf. Mae’r syniad o “rannydd cyffredin mwyaf” yn gwneud synnwyr ar gyfer polynomialau. Yn wir, gallwn gyfrifo GCD dau bolynomial gan ddefnyddio, yn ei hanfod, yr un Algorithm Ewclid sy’n gweithio ar gyfer cyfanrifau.¹²⁶ Y fersiwn cyfanrifau yw

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

Gan ddefnyddio hwn, gallem wneud yr addasiad amlwg i ddiffinio gweithrediad GCD sy’n gweithio ar restrau termau:

(define (gcd-terms a b)
  (if (empty-termlist? b)
      a
      (gcd-terms b (remainder-terms a b))))

lle mae remainder-terms yn dewis cydran y gweddill o’r rhestr a ddychwelir gan y gweithrediad rhannu rhestrau termau div-terms a weithredwyd yn Ymarfer 2.91.

Ymarfer 2.94: Gan ddefnyddio div-terms, gweithredwch y weithdrefn remainder-terms a defnyddio hon i ddiffinio gcd-terms fel uchod. Yn awr ysgrifennwch weithdrefn gcd-poly sy’n cyfrifo GCD polynomial dau wrthrych poly. (Dylai’r weithdrefn nodi gwall os nad yw’r ddau wrthrych poly yn yr un newidyn.) Gosodwch yn y system weithrediad generig greatest-common-divisor sy’n lleihau i gcd-poly ar gyfer polynomialau ac i gcd arferol ar gyfer rhifau cyffredin. Fel prawf, rhowch gynnig ar
(define p1 
  (make-polynomial 
   'x '((4 1) (3 -1) (2 -2) (1 2))))

(define p2 
  (make-polynomial 
   'x '((3 1) (1 -1))))

(greatest-common-divisor p1 p2)
a gwiriwch eich canlyniad â llaw.

Ymarfer 2.95: Diffiniwch $P_{1}$ , $P_{2}$ , ac $P_{3}$ yn bolynomialau $\begin{aligned} P_{1} : & x^{2} - 2 x + 1, \\ P_{2} : & 11 x^{2} + 7, \\ P_{3} : & 13 x + 5. \end{aligned}$ Yn awr diffiniwch $Q_{1}$ yn lluoswm $P_{1}$ ac $P_{2}$ , ac $Q_{2}$ yn lluoswm $P_{1}$ ac $P_{3}$ , a defnyddiwch greatest-common-divisor (Ymarfer 2.94) i gyfrifo GCD $Q_{1}$ ac $Q_{2}$ . Sylwch nad yw’r ateb yr un fath ag $P_{1}$ . Mae’r enghraifft hon yn cyflwyno gweithrediadau nad ydynt ar gyfanrifau i’r cyfrifiad, gan achosi anawsterau i’r algorithm GCD.¹²⁷ I ddeall yr hyn sy’n digwydd, ceisiwch olrhain gcd-terms wrth gyfrifo’r GCD neu geisiwch gyflawni’r rhannu â llaw.

Gallwn ddatrys y broblem a ddangoswyd yn Ymarfer 2.95 os defnyddiwn yr addasiad canlynol i’r algorithm GCD (sydd mewn gwirionedd ond yn gweithio yn achos polynomialau â chyfernodau cyfanrif). Cyn cyflawni unrhyw rannu polynomialau yng nghyfrifiad y GCD, lluoswn y rhannyn â ffactor cyson sy’n gyfanrif, wedi’i ddewis i warantu na fydd unrhyw ffracsiynau’n codi yn ystod y broses rannu. Felly bydd ein hateb yn wahanol i’r GCD ei hun gan ffactor cyson sy’n gyfanrif, ond nid yw hyn o bwys wrth leihau ffwythiannau cymarebol i’w ffurf symlaf; defnyddir y GCD i rannu’r rhifiadur a’r enwadur, felly bydd y ffactor cyson sy’n gyfanrif yn canslo.

Yn fwy manwl, os yw $P$ ac $Q$ yn bolynomialau, gadewch i $O_{1}$ fod yn radd $P$ (h.y., gradd term mwyaf $P$ ) a gadewch i $O_{2}$ fod yn radd $Q$ . Gadewch i $c$ fod yn gyfernod blaen $Q$ . Yna gellir dangos, os lluoswn $P$ â’r ffactor cyfanrifioli $c^{1 + O_{1} - O_{2}}$ , y gellir rhannu’r polynomial sy’n deillio o hyn ag $Q$ drwy ddefnyddio’r algorithm div-terms heb gyflwyno unrhyw ffracsiynau. Weithiau gelwir y gweithrediad o luosi’r rhannyn â’r cysonyn hwn ac yna rannu yn ffugraniad $P$ ag $Q$ . Gelwir gweddill y rhaniad yn ffugweddill.

Ymarfer 2.96:

Gweithredwch y weithdrefn pseudoremainder-terms, sydd yn union fel remainder-terms heblaw ei bod yn lluosi’r rhannyn â’r ffactor cyfanrifioli a ddisgrifiwyd uchod cyn galw div-terms. Addaswch gcd-terms i ddefnyddio pseudoremainder-terms, a gwiriwch fod greatest-common-divisor bellach yn cynhyrchu ateb â chyfernodau cyfanrif ar yr enghraifft yn Ymarfer 2.95.
Bellach mae gan y GCD gyfernodau cyfanrif, ond maent yn fwy na rhai $P_{1}$ . Addaswch gcd-terms fel ei fod yn tynnu ffactorau cyffredin o gyfernodau’r ateb drwy rannu’r holl gyfernodau â’u rhannydd cyffredin mwyaf (sy’n gyfanrif).

Felly, dyma sut i leihau ffwythiant cymarebol i’w ffurf symlaf:

Cyfrifwch GCD y rhifiadur a’r enwadur, gan ddefnyddio’r fersiwn o gcd-terms o Ymarfer 2.96.
Pan gewch y GCD, lluoswch y rhifiadur a’r enwadur â’r un ffactor cyfanrifioli cyn rhannu’r ddau â’r GCD, fel na fydd rhannu â’r GCD yn cyflwyno unrhyw gyfernodau nad ydynt yn gyfanrifau. Fel ffactor gallwch ddefnyddio cyfernod blaen y GCD wedi’i godi i’r pŵer $1 + O_{1} - O_{2}$ , lle mae $O_{2}$ yn radd y GCD ac $O_{1}$ yn uchafswm graddau’r rhifiadur a’r enwadur. Bydd hyn yn sicrhau na fydd rhannu’r rhifiadur a’r enwadur â’r GCD yn cyflwyno unrhyw ffracsiynau.
Canlyniad y gweithrediad hwn fydd rhifiadur ac enwadur â chyfernodau cyfanrif. Bydd y cyfernodau fel arfer yn fawr iawn oherwydd yr holl ffactorau cyfanrifioli, felly’r cam olaf yw tynnu’r ffactorau diangen drwy gyfrifo rhannydd cyffredin mwyaf (sy’n gyfanrif) holl gyfernodau’r rhifiadur a’r enwadur a rhannu pob un â’r ffactor hwn.

Ymarfer 2.97:
Gweithredwch yr algorithm hwn fel gweithdrefn reduce-terms sy’n cymryd dwy restr dermau n ac d yn argiau ac yn dychwelyd rhestr nn, dd, sef n ac d wedi’u lleihau i’w ffurf symlaf drwy’r algorithm a roddwyd uchod. Ysgrifennwch hefyd weithdrefn reduce-poly, sy’n gyfatebol i add-poly, sy’n gwirio a oes gan y ddau wrthrych poly yr un newidyn. Os oes, mae reduce-poly yn tynnu’r newidyn ac yn trosglwyddo’r broblem i reduce-terms, yna’n ailatodi’r newidyn at y ddwy restr dermau a ddarperir gan reduce-terms.
Diffiniwch weithdrefn sy’n gyfatebol i reduce-terms sy’n gwneud yr hyn a wnaeth make-rat gwreiddiol ar gyfer cyfanrifau:
(define (reduce-integers n d)
  (let ((g (gcd n d)))
    (list (/ n g) (/ d g))))
a diffiniwch reduce yn weithrediad generig sy’n galw apply-generic i ddethol naill ai reduce-poly (ar gyfer argiau polynomial) neu reduce-integers (ar gyfer argiau scheme-number). Gallwch yn awr beri’n hawdd i’r pecyn rhifyddeg gymarebol leihau ffracsiynau i’w ffurf symlaf drwy beri i make-rat alw reduce cyn cyfuno’r rhifiadur a’r enwadur a roddwyd i ffurfio rhif cymarebol. Bellach mae’r system yn trin mynegiadau cymarebol mewn cyfanrifau neu bolynomialau. I brofi eich rhaglen, rhowch gynnig ar yr enghraifft ar ddechrau’r ymarfer estynedig hwn:
(define p1 
  (make-polynomial 'x '((1 1) (0 1))))
(define p2 
  (make-polynomial 'x '((3 1) (0 -1))))
(define p3 
  (make-polynomial 'x '((1 1))))
(define p4 
  (make-polynomial 'x '((2 1) (0 -1))))
(define rf1 (make-rational p1 p2))
(define rf2 (make-rational p3 p4))
(add rf1 rf2)
Gwelwch a gewch yr ateb cywir, wedi’i leihau’n gywir i’w ffurf symlaf.

Mae cyfrifo’r GCD wrth wraidd unrhyw system sy’n cyflawni gweithrediadau ar ffwythiannau cymarebol. Mae’r algorithm a ddefnyddiwyd uchod, er ei fod yn syml yn fathemategol, yn eithriadol o araf. Mae’r arafwch yn rhannol oherwydd y nifer fawr o weithrediadau rhannu ac yn rhannol oherwydd maint enfawr y cyfernodau canolradd a gynhyrchir gan y ffugraniadau. Un o’r meysydd gweithgar wrth ddatblygu systemau trin algebra yw dylunio algorithmau gwell ar gyfer cyfrifo GCDau polynomialau.¹²⁸

Troednodiadau

¹¹⁵ Rhaid inni hefyd ddarparu gweithdrefn sydd bron yn union yr un fath i drin y mathau (scheme-number complex).

¹¹⁶ Gweler Ymarfer 2.82 am gyffredinoliadau.

¹¹⁷ Os ydym yn glyfar, gallwn fel arfer ymdopi â llai nag $n^{2}$ o weithdrefnau trosi math. Er enghraifft, os gwyddom sut i drosi o fath 1 i fath 2 ac o fath 2 i fath 3, yna gallwn ddefnyddio’r wybodaeth hon i drosi o fath 1 i fath 3. Gall hyn leihau’n fawr nifer y gweithdrefnau trosi math y mae angen inni eu darparu’n benodol pan ychwanegwn fath newydd at y system. Os ydym yn barod i gynnwys y lefel angenrheidiol o soffistigeiddrwydd yn ein system, gallwn beri iddi chwilio’r “graff” o berthnasoedd rhwng mathau a chynhyrchu’n awtomatig y gweithdrefnau trosi math hynny y gellir eu casglu o’r rhai a ddarperir yn benodol.

¹¹⁸ Mae’r datganiad hwn, sydd hefyd yn ymddangos yn argraffiad cyntaf y llyfr hwn, yr un mor wir yn awr ag yr oedd pan ysgrifennom ef ddeuddeng mlynedd yn ôl. Mae datblygu fframwaith cyffredinol defnyddiol ar gyfer mynegi’r perthnasoedd rhwng gwahanol fathau o endidau (yr hyn y mae athronwyr yn ei alw’n “ontoleg”) yn ymddangos yn anodd i’r eithaf. Y prif wahaniaeth rhwng y dryswch a fodolai ddeng mlynedd yn ôl a’r dryswch sy’n bodoli yn awr yw bod amrywiaeth o ddamcaniaethau ontolegol annigonol bellach wedi’u hymgorffori mewn llu o ieithoedd rhaglennu sydd yr un mor annigonol. Er enghraifft, mae llawer o gymhlethdod ieithoedd rhaglennu gwrthrych-gyfeiriol—a’r gwahaniaethau cynnil a dryslyd rhwng ieithoedd gwrthrych-gyfeiriol cyfoes—yn canolbwyntio ar drin gweithrediadau generig ar fathau cydgysylltiedig. Mae ein trafodaeth ni o wrthrychau cyfrifiadurol ym Mhennod 3 yn osgoi’r materion hyn yn llwyr. Bydd darllenwyr sy’n gyfarwydd â rhaglennu gwrthrych-gyfeiriol yn sylwi bod gennym lawer i’w ddweud ym mhennod 3 am gyflwr lleol, ond nad ydym hyd yn oed yn sôn am “ddosbarthiadau” nac “etifeddu.” Yn wir, rydym yn amau na ellir mynd i’r afael â’r problemau hyn yn ddigonol drwy ddylunio ieithoedd cyfrifiadurol yn unig, heb dynnu hefyd ar waith ar gynrychioli gwybodaeth a rhesymu awtomataidd.

¹¹⁹ Gellir taflunio rhif real i gyfanrif gan ddefnyddio’r weithdrefn gyntefig round, sy’n dychwelyd y cyfanrif agosaf at ei harg.

¹²⁰ Ar y llaw arall, byddwn yn caniatáu polynomialau y mae eu cyfernodau eu hunain yn bolynomialau mewn newidynnau eraill. Bydd hyn yn rhoi inni, yn ei hanfod, yr un gallu cynrychioli â system amlnewidyn lawn, er ei fod yn arwain at broblemau trosi math, fel y trafodir isod.

¹²¹ Ar gyfer polynomialau unnewidyn, gall rhoi gwerth polynomial mewn set benodol o bwyntiau fod yn gynrychioliad arbennig o dda. Mae hyn yn gwneud rhifyddeg polynomialau’n hynod syml. I gael, er enghraifft, swm dau bolynomial a gynrychiolir fel hyn, dim ond adio gwerthoedd y polynomialau mewn pwyntiau cyfatebol sydd ei angen. I drawsffurfio’n ôl i gynrychioliad mwy cyfarwydd, gallwn ddefnyddio fformiwla rhyngosod Lagrange, sy’n dangos sut i adfer cyfernodau polynomial o radd $n$ o gael gwerthoedd y polynomial mewn $n + 1$ o bwyntiau.

¹²² Mae’r gweithrediad hwn yn debyg iawn i’r gweithrediad trefnedig union-set a ddatblygasom yn Ymarfer 2.62. Yn wir, os meddyliwn am dermau’r polynomial fel set wedi’i threfnu yn ôl pŵer yr newidyn ffurfiol, yna mae’r rhaglen sy’n cynhyrchu rhestr dermau swm bron yn union yr un fath ag union-set.

¹²³ I wneud i hyn weithio’n gwbl esmwyth, dylem hefyd ychwanegu at ein system rhifyddeg generig y gallu i drosi “rhif” yn bolynomial drwy ei ystyried yn bolynomial o radd sero y mae ei gyfernod yn rhif hwnnw. Mae hyn yn angenrheidiol os ydym am gyflawni gweithrediadau megis $[x^{2} + (y + 1) x + 5] + [x^{2} + 2 x + 1],$ sy’n gofyn am adio’r cyfernod $y + 1$ at y cyfernod 2.

¹²⁴ Yn yr enghreifftiau hyn o bolynomialau, tybiwn ein bod wedi gweithredu’r system rhifyddeg generig gan ddefnyddio’r mecanwaith mathau a awgrymwyd yn Ymarfer 2.78. Felly, cynrychiolir cyfernodau sy’n rhifau cyffredin fel y rhifau eu hunain yn hytrach na pharau y mae eu car yn symbol scheme-number.

¹²⁵ Er ein bod yn tybio bod rhestrau termau’n drefnedig, rydym wedi gweithredu adjoin-term i ddefnyddio cons yn unig i atodi’r term newydd at y rhestr dermau bresennol. Gallwn wneud hyn cyn belled ag y gwarantwn fod y gweithdrefnau (megis add-terms) sy’n defnyddio adjoin-term bob amser yn ei alw â therm o radd uwch nag unrhyw un sy’n ymddangos yn y rhestr. Pe na baem am roi gwarant o’r fath, gallem fod wedi gweithredu adjoin-term i fod yn debyg i’r adeiladydd adjoin-set ar gyfer cynrychioli setiau â rhestrau trefnedig (Ymarfer 2.61).

¹²⁶ Ffurfiolir y ffaith bod Algorithm Ewclid yn gweithio ar gyfer polynomialau mewn algebra drwy ddweud bod polynomialau’n ffurfio math o barth algebraidd o’r enw cylch Ewclidaidd. Mae cylch Ewclidaidd yn barth sy’n caniatáu adio, tynnu a lluosi cymudol, ynghyd â ffordd o neilltuo i bob elfen $x$ o’r cylch “fesur” $m (x)$ sy’n gyfanrif positif â’r priodweddau fod $m (x y) \geq m (x)$ ar gyfer unrhyw $x$ ac $y$ ansero a bod, o gael unrhyw $x$ ac $y$ , $q$ yn bodoli fel bod $y = q x + r$ a naill ai $r = 0$ neu $m (r) < m (x)$ . O safbwynt haniaethol, dyma sydd ei angen i brofi bod Algorithm Ewclid yn gweithio. Ar gyfer parth y cyfanrifau, mesur $m$ cyfanrif yw gwerth absoliwt y cyfanrif ei hun. Ar gyfer parth y polynomialau, mesur polynomial yw ei radd.

¹²⁷ Mewn gweithrediad megis MIT Scheme, mae hyn yn cynhyrchu polynomial sydd yn wir yn rhannydd i $Q_{1}$ ac $Q_{2}$ , ond â chyfernodau cymarebol. Mewn llawer o systemau Scheme eraill, lle gall rhannu cyfanrifau gynhyrchu rhifau degol â thrachywiredd cyfyngedig, gallwn fethu â chael rhannydd dilys.

¹²⁸ Darganfuwyd un dull hynod effeithlon a chain ar gyfer cyfrifo GCDau polynomialau gan Richard Zippel (1979). Algorithm tebygolrwydd yw’r dull, fel y prawf cyflym am gysefinrwydd a drafodasom ym Mhennod 1. Mae llyfr Zippel (Zippel 1993) yn disgrifio’r dull hwn, ynghyd â ffyrdd eraill o gyfrifo GCDau polynomialau.