2.2 Data Hierarchaidd a’r Briodwedd Cau

Fel y gwelsom, mae parau’n darparu “glud” cyntefig y gallwn ei ddefnyddio i adeiladu gwrthrychau data cyfansawdd. Mae Ffigur 2.2 yn dangos ffordd safonol o ddelweddu pâr—yn yr achos hwn, y pâr a ffurfiwyd gan (cons 1 2). Yn y cynrychioliad hwn, a elwir yn nodiant blychau a phwyntyddion, dangosir pob gwrthrych fel pwyntydd at flwch. Mae’r blwch ar gyfer gwrthrych cyntefig yn cynnwys cynrychioliad o’r gwrthrych. Er enghraifft, mae’r blwch ar gyfer rhif yn cynnwys rhifolyn. Mae’r blwch ar gyfer pâr mewn gwirionedd yn flwch dwbl: mae’r rhan chwith yn cynnwys (pwyntydd at) car y pâr, a’r rhan dde yn cynnwys yr cdr.

Rydym eisoes wedi gweld y gellir defnyddio cons i gyfuno parau yn ogystal â rhifau. (Defnyddiasoch y ffaith hon, neu dylech fod wedi gwneud hynny, wrth wneud Ymarfer 2.2 ac Ymarfer 2.3.) O ganlyniad, mae parau’n darparu bloc adeiladu cyffredinol y gallwn adeiladu pob math o strwythurau data ohono. Mae Ffigur 2.3 yn dangos dwy ffordd o ddefnyddio parau i gyfuno’r rhifau 1, 2, 3, a 4.

Y gallu i greu parau y mae eu helfennau’n barau yw hanfod pwysigrwydd strwythur rhestr fel offeryn cynrychioli. Cyfeiriwn at y gallu hwn fel priodwedd cau cons. Yn gyffredinol, mae gweithrediad ar gyfer cyfuno gwrthrychau data yn bodloni’r briodwedd cau os gellir cyfuno canlyniadau cyfuno pethau â’r gweithrediad hwnnw eu hunain drwy ddefnyddio’r un gweithrediad.⁷² Y briodwedd cau yw’r allwedd i rym mewn unrhyw fodd o gyfuno, oherwydd mae’n caniatáu inni greu strwythurau hierarchaidd—strwythurau sy’n cynnwys rhannau, sydd eu hunain yn cynnwys rhannau, ac yn y blaen.

O ddechrau Pennod 1, rydym wedi gwneud defnydd hanfodol o’r briodwedd cau wrth ymdrin â gweithdrefnau, oherwydd mae pob rhaglen heblaw’r rhai symlaf oll yn dibynnu ar y ffaith y gall elfennau cyfuniad eu hunain fod yn gyfuniadau. Yn yr adran hon, awn i’r afael â chanlyniadau’r briodwedd cau ar gyfer data cyfansawdd. Disgrifiwn rai technegau confensiynol ar gyfer defnyddio parau i gynrychioli dilyniannau a choed, a dangoswn iaith graffeg sy’n darlunio’r briodwedd cau mewn ffordd fywiog.⁷³

2.2.1Cynrychioli Dilyniannau

Un o’r strwythurau defnyddiol y gallwn eu hadeiladu â pharau yw dilyniant—casgliad trefnedig o wrthrychau data. Wrth gwrs, mae llawer o ffyrdd o gynrychioli dilyniannau yn nhermau parau. Dangosir un cynrychioliad arbennig o syml yn Ffigur 2.4, lle cynrychiolir y dilyniant 1, 2, 3, 4 fel cadwyn o barau. Yr car ym mhob pâr yw’r eitem gyfatebol yn y gadwyn, ac cdr y pâr yw’r pâr nesaf yn y gadwyn. Mae cdr y pâr olaf yn dynodi diwedd y dilyniant drwy bwyntio at werth neilltuol nad yw’n bâr, a gynrychiolir mewn diagramau blychau a phwyntyddion fel llinell groeslinol ac mewn rhaglenni fel gwerth y newidyn nil. Adeiladir y dilyniant cyfan drwy weithrediadau cons nythol:

(cons 1
      (cons 2
            (cons 3
                  (cons 4 nil))))

Gelwir dilyniant o barau o’r fath, a ffurfir gan alwadau cons nythol, yn rhestr, ac mae Scheme yn darparu gweithdrefn gyntefig o’r enw list i helpu i adeiladu rhestrau.⁷⁴ Gellid cynhyrchu’r dilyniant uchod drwy (list 1 2 3 4). Yn gyffredinol, mae

(list ⟨a₁⟩ ⟨a₂⟩ … ⟨aₙ⟩)

yn gyfwerth â

(cons ⟨a₁⟩
      (cons ⟨a₂⟩
            (cons …
                  (cons ⟨aₙ⟩
                        nil)…)))

Yn ôl y confensiwn, mae systemau Lisp yn argraffu rhestrau drwy argraffu’r dilyniant o elfennau, wedi’i amgáu mewn cromfachau crwn. Felly, argreffir y gwrthrych data yn Ffigur 2.4 fel (1 2 3 4):

(define one-through-four (list 1 2 3 4))

one-through-four
(1 2 3 4)

Byddwch yn ofalus i beidio â chymysgu’r mynegiad (list 1 2 3 4) â’r rhestr (1 2 3 4), sef y canlyniad a geir pan werthusir y mynegiad. Bydd ceisio gwerthuso’r mynegiad (1 2 3 4) yn arwyddo gwall pan fydd y dehonglydd yn ceisio cymhwyso’r weithdrefn 1 i’r argiau 2, 3, 4.

Gallwn ystyried car yn dethol yr eitem gyntaf yn y rhestr, ac cdr yn dethol yr isrestr sy’n cynnwys pob eitem heblaw’r gyntaf. Gellir defnyddio cymwysiadau nythol o car ac cdr i echdynnu’r ail, y drydedd, a’r eitemau dilynol yn y rhestr.⁷⁵ Mae’r adeiladydd cons yn creu rhestr fel yr un wreiddiol, ond ag eitem ychwanegol ar y dechrau.

(car one-through-four)
1

(cdr one-through-four)
(2 3 4)

(car (cdr one-through-four))
2

(cons 10 one-through-four)
(10 1 2 3 4)

(cons 5 one-through-four)
(5 1 2 3 4)

Gellir ystyried gwerth nil, a ddefnyddir i derfynu’r gadwyn o barau, yn ddilyniant heb elfennau, y rhestr wag. Mae’r gair nil yn dalfyriad o’r gair Lladin nihil, sy’n golygu “dim.”⁷⁶

Gweithrediadau rhestr

Gyda’r defnydd o barau i gynrychioli dilyniannau o elfennau fel rhestrau, ceir technegau rhaglennu confensiynol ar gyfer trin rhestrau drwy gymhwyso “cdr” yn olynol i fynd i lawr y rhestrau. Er enghraifft, mae’r weithdrefn list-ref yn cymryd rhestr a rhif $n$ fel argiau ac yn dychwelyd eitem $n^{\text{fed}}$ y rhestr. Yr arfer yw rhifo elfennau’r rhestr gan ddechrau gyda 0. Dyma’r dull o gyfrifo list-ref:

• Ar gyfer $n=0$, dylai list-ref ddychwelyd car y rhestr.
• Fel arall, dylai list-ref ddychwelyd eitem rhif $(n-<!--\; -\; -->1)$ o cdr y rhestr.

(define (list-ref items n)
  (if (= n 0)
      (car items)
      (list-ref (cdr items) 
                (- n 1))))

(define squares 
  (list 1 4 9 16 25))

(list-ref squares 3)
16

Yn aml cymhwyswn cdr i fynd i lawr y rhestr gyfan. I gynorthwyo hyn, mae Scheme yn cynnwys traethiad cyntefig null?, sy’n profi a yw ei arg yn rhestr wag. Mae’r weithdrefn length, sy’n dychwelyd nifer yr eitemau mewn rhestr, yn dangos y patrwm defnydd nodweddiadol hwn:

(define (length items)
  (if (null? items)
      0
      (+ 1 (length (cdr items)))))

(define odds
  (list 1 3 5 7))

(length odds)
4

Mae’r weithdrefn length yn gweithredu cynllun dychweliadol syml. Y cam lleihau yw:

• Mae length unrhyw restr yn 1 ynghyd ag length cdr y rhestr.

Cymhwysir hyn yn olynol nes inni gyrraedd yr achos sylfaenol:

• Mae length y rhestr wag yn 0.

Gallem hefyd gyfrifo length mewn arddull iteru:

(define (length items)
  (define (length-iter a count)
    (if (null? a)
        count
        (length-iter (cdr a) 
                     (+ 1 count))))
  (length-iter items 0))

Techneg raglennu gonfensiynol arall yw adeiladu rhestr ateb â “cons” wrth gymhwyso cdr i fynd i lawr rhestr, fel yn y weithdrefn append, sy’n cymryd dwy restr fel argiau ac yn cyfuno eu helfennau i wneud rhestr newydd:

(append squares odds)
(1 4 9 16 25 1 3 5 7)

(append odds squares)
(1 3 5 7 1 4 9 16 25)

Gweithredir Append hefyd drwy ddefnyddio cynllun dychweliadol. I gymhwyso append i’r rhestrau list1 ac list2, gwnewch y canlynol:

• Os mai list1 yw’r rhestr wag, yna’r canlyniad yw list2 yn unig.
• Fel arall, cymhwyswch append i cdr list1 ac i list2, a defnyddiwch cons i osod car list1 ar flaen y canlyniad:

(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) 
            (append (cdr list1) 
                    list2))))

Ymarfer 2.17: Diffiniwch weithdrefn last-pair sy’n dychwelyd y rhestr sy’n cynnwys elfen olaf rhestr benodol (nad yw’n wag) yn unig:

(last-pair (list 23 72 149 34))
(34)

Ymarfer 2.18: Diffiniwch weithdrefn reverse sy’n cymryd rhestr fel arg ac yn dychwelyd rhestr o’r un elfennau yn y drefn wrthdro:

(reverse (list 1 4 9 16 25))
(25 16 9 4 1)

Ymarfer 2.19: Ystyriwch y rhaglen cyfrif newid yn 1.2.2. Byddai’n braf gallu newid yn hawdd yr arian cyfred a ddefnyddir gan y rhaglen, fel y gallem gyfrifo nifer y ffyrdd o newid punt Brydeinig, er enghraifft. Fel y mae’r rhaglen wedi’i hysgrifennu, mae’r wybodaeth am yr arian cyfred wedi’i dosbarthu’n rhannol i’r weithdrefn first-denomination ac yn rhannol i’r weithdrefn count-change (sy’n gwybod bod pum math o ddarn arian yn UDA). Byddai’n well gallu darparu rhestr o ddarnau arian i’w defnyddio i roi newid.

Rydym eisiau ailysgrifennu’r weithdrefn cc fel bod ei hail arg yn rhestr o werthoedd y darnau arian i’w defnyddio, yn hytrach na chyfanrif sy’n pennu pa ddarnau arian i’w defnyddio. Gallem wedyn gael rhestrau a fyddai’n diffinio pob math o arian cyfred:

(define us-coins 
  (list 50 25 10 5 1))

(define uk-coins 
  (list 100 50 20 10 5 2 1 0.5))

Gallem wedyn alw cc fel a ganlyn:

(cc 100 us-coins)
292

Bydd gwneud hyn yn gofyn am rywfaint o newid i’r rhaglen cc. Bydd ganddi’r un ffurf o hyd, ond bydd yn cyrchu ei hail arg yn wahanol, fel a ganlyn:

(define (cc amount coin-values)
  (cond ((= amount 0) 
         1)
        ((or (< amount 0) 
             (no-more? coin-values)) 
         0)
        (else
         (+ (cc 
             amount
             (except-first-denomination 
              coin-values))
            (cc 
             (- amount
                (first-denomination 
                 coin-values))
             coin-values)))))

Diffiniwch y gweithdrefnau first-denomination, except-first-denomination ac no-more? yn nhermau gweithrediadau cyntefig ar strwythurau rhestr. A yw trefn y rhestr coin-values yn effeithio ar yr ateb a gynhyrchir gan cc? Pam, neu pam lai?

Ymarfer 2.20: Mae’r gweithdrefnau +, *, ac list yn cymryd nifer mympwyol o argiau. Un ffordd o ddiffinio gweithdrefnau o’r fath yw defnyddio define gyda nodiant cynffon ddotiog. Mewn diffiniad gweithdrefn, mae rhestr baramedrau sydd â dot cyn enw’r paramedr olaf yn dynodi, pan elwir y weithdrefn, y bydd gwerthoedd y paramedrau cychwynnol (os oes rhai) yn argiau cychwynnol, fel arfer, ond y bydd gwerth y paramedr olaf yn rhestr o unrhyw argiau sy’n weddill. Er enghraifft, o gael y diffiniad

(define (f x y . z) ⟨body⟩)

gellir galw’r weithdrefn f â dau arg neu fwy. Os gwerthuswn

(f 1 2 3 4 5 6)

yna yng nghorff f, bydd x yn 1, bydd y yn 2, a bydd z yn rhestr (3 4 5 6). O gael y diffiniad

(define (g . w) ⟨body⟩)

gellir galw’r weithdrefn g â sero neu fwy o argiau. Os gwerthuswn

(g 1 2 3 4 5 6)

yna yng nghorff g, bydd w yn rhestr (1 2 3 4 5 6).⁷⁷

Defnyddiwch y nodiant hwn i ysgrifennu gweithdrefn same-parity sy’n cymryd un cyfanrif neu fwy ac yn dychwelyd rhestr o’r holl argiau sydd â’r un paredd eilrif-odrif â’r arg cyntaf. Er enghraifft,

(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)

(same-parity 2 3 4 5 6 7)
(2 4 6)

Mapio dros restrau

Un gweithrediad hynod ddefnyddiol yw cymhwyso rhyw drawsffurfiad i bob elfen mewn rhestr a chynhyrchu’r rhestr o ganlyniadau. Er enghraifft, mae’r weithdrefn ganlynol yn graddio pob rhif mewn rhestr gan ffactor penodol:

(define (scale-list items factor)
  (if (null? items)
      nil
      (cons (* (car items) factor)
            (scale-list (cdr items) 
                        factor))))

(scale-list (list 1 2 3 4 5) 10)
(10 20 30 40 50)

Gallwn haniaethu’r syniad cyffredinol hwn a’i ddal fel patrwm cyffredin wedi’i fynegi fel gweithdrefn trefn uwch, yn union fel yn 1.3. Gelwir y weithdrefn trefn uwch yma yn map. Mae Map yn cymryd gweithdrefn un arg a rhestr fel argiau, ac yn dychwelyd rhestr o’r canlyniadau a gynhyrchir drwy gymhwyso’r weithdrefn i bob elfen yn y rhestr:⁷⁸

(define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))

(map abs (list -10 2.5 -11.6 17))
(10 2.5 11.6 17)

(map (lambda (x) (* x x)) (list 1 2 3 4))
(1 4 9 16)

Gallwn yn awr roi diffiniad newydd o scale-list yn nhermau map:

(define (scale-list items factor)
  (map (lambda (x) (* x factor))
       items))

Mae Map yn luniad pwysig, nid yn unig oherwydd ei fod yn dal patrwm cyffredin, ond oherwydd ei fod yn sefydlu lefel uwch o haniaethu wrth ymdrin â rhestrau. Yn y diffiniad gwreiddiol o scale-list, mae strwythur dychweliadol y rhaglen yn tynnu sylw at brosesu’r rhestr fesul elfen. Mae diffinio scale-list yn nhermau map yn cuddio’r lefel honno o fanylder ac yn pwysleisio bod graddio’n trawsffurfio rhestr o elfennau yn rhestr o ganlyniadau. Nid y gwahaniaeth rhwng y ddau ddiffiniad yw bod y cyfrifiadur yn cyflawni proses wahanol (nid yw), ond ein bod yn meddwl am y broses yn wahanol. I bob pwrpas, mae map yn helpu i sefydlu rhwystr haniaethu sy’n ynysu gweithrediad gweithdrefnau sy’n trawsffurfio rhestrau oddi wrth fanylion sut yr echdynnir ac y cyfunir elfennau’r rhestr. Fel y rhwystrau a ddangosir yn Ffigur 2.1, mae’r haniaeth hon yn rhoi’r hyblygrwydd inni newid manylion lefel isel gweithredu dilyniannau, gan gadw’r fframwaith cysyniadol o weithrediadau sy’n trawsffurfio dilyniannau yn ddilyniannau. Mae Adran 2.2.3 yn ymhelaethu ar y defnydd hwn o ddilyniannau fel fframwaith ar gyfer trefnu rhaglenni.

Ymarfer 2.21: Mae’r weithdrefn square-list yn cymryd rhestr o rifau fel arg ac yn dychwelyd rhestr o sgwariau’r rhifau hynny.

(square-list (list 1 2 3 4))
(1 4 9 16)

Dyma ddau ddiffiniad gwahanol o square-list. Cwblhewch y ddau drwy lenwi’r mynegiadau coll:

(define (square-list items)
  (if (null? items)
      nil
      (cons ⟨??⟩ ⟨??⟩)))

(define (square-list items)
  (map ⟨??⟩ ⟨??⟩))

Ymarfer 2.22: Mae Louis Reasoner yn ceisio ailysgrifennu’r weithdrefn square-list gyntaf yn Ymarfer 2.21 fel ei bod yn esblygu proses iteru:

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons (square (car things))
                    answer))))
  (iter items nil))

Yn anffodus, mae diffinio square-list fel hyn yn cynhyrchu’r rhestr ateb yn y drefn wrthdro i’r un a ddymunir. Pam?

Mae Louis wedyn yn ceisio trwsio ei nam drwy gyfnewid yr argiau i cons:

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons answer
                    (square 
                     (car things))))))
  (iter items nil))

Nid yw hyn yn gweithio ychwaith. Esboniwch.

Ymarfer 2.23: Mae’r weithdrefn for-each yn debyg i map. Mae’n cymryd gweithdrefn a rhestr o elfennau fel argiau. Fodd bynnag, yn hytrach na ffurfio rhestr o’r canlyniadau, mae for-each yn cymhwyso’r weithdrefn i bob un o’r elfennau yn ei thro, o’r chwith i’r dde. Ni ddefnyddir y gwerthoedd a ddychwelir drwy gymhwyso’r weithdrefn i’r elfennau o gwbl—defnyddir for-each gyda gweithdrefnau sy’n cyflawni gweithred, megis argraffu. Er enghraifft,

(for-each 
 (lambda (x) (newline) (display x))
 (list 57 321 88))

57
321
88

Gall y gwerth a ddychwelir gan yr alwad i for-each (nas dangosir uchod) fod yn rhywbeth mympwyol, megis gwir. Rhowch weithrediad o for-each.

2.2.2Strwythurau Hierarchaidd

Mae cynrychioli dilyniannau yn nhermau rhestrau yn cyffredinoli’n naturiol i gynrychioli dilyniannau y gall eu helfennau eu hunain fod yn ddilyniannau. Er enghraifft, gallwn ystyried y gwrthrych ((1 2) 3 4) a adeiladir gan

(cons (list 1 2) (list 3 4))

yn rhestr o dair eitem, y mae’r gyntaf ei hun yn rhestr, (1 2). Yn wir, awgrymir hyn gan y ffurf yr argreffir y canlyniad ynddi gan y dehonglydd. Mae Ffigur 2.5 yn dangos cynrychioliad y strwythur hwn yn nhermau parau.

Ffordd arall o feddwl am ddilyniannau y mae eu helfennau’n ddilyniannau yw fel coed. Elfennau’r dilyniant yw canghennau’r goeden, ac isgoed yw elfennau sydd eu hunain yn ddilyniannau. Mae Ffigur 2.6 yn dangos y strwythur yn Ffigur 2.5 wedi’i ystyried yn goeden.

Mae dychweliad yn offeryn naturiol ar gyfer ymdrin â strwythurau coed, gan y gallwn yn aml leihau gweithrediadau ar goed i weithrediadau ar eu canghennau, sydd yn eu tro yn lleihau i weithrediadau ar ganghennau’r canghennau, ac yn y blaen, nes inni gyrraedd dail y goeden. Fel enghraifft, cymharwch y weithdrefn length yn 2.2.1 â’r weithdrefn count-leaves, sy’n dychwelyd cyfanswm nifer dail coeden:

(define x (cons (list 1 2) (list 3 4)))

(length x)
3

(count-leaves x)
4

(list x x)
(((1 2) 3 4) ((1 2) 3 4))

(length (list x x))
2

(count-leaves (list x x))
8

I weithredu count-leaves, cofiwch y cynllun dychweliadol ar gyfer cyfrifo length:

• Mae Length rhestr x yn 1 ynghyd ag length cdr x.
• Mae Length y rhestr wag yn 0.

Mae Count-leaves yn debyg. Mae’r gwerth ar gyfer y rhestr wag yr un fath:

• Mae Count-leaves y rhestr wag yn 0.

Ond yn y cam lleihau, lle tynnwn car y rhestr oddi arni, rhaid inni ystyried y gall yr car ei hun fod yn goeden y mae angen cyfrif ei dail. Felly, y cam lleihau priodol yw

• Mae Count-leaves coeden x yn count-leaves car x ynghyd ag count-leaves cdr x.

Yn olaf, drwy gymryd car dro ar ôl tro cyrhaeddwn ddail go iawn, felly mae angen achos sylfaenol arall:

• Mae Count-leaves deilen yn 1.

I helpu i ysgrifennu gweithdrefnau dychweliadol ar goed, mae Scheme yn darparu’r traethiad cyntefig pair?, sy’n profi a yw ei arg yn bâr. Dyma’r weithdrefn gyflawn:⁷⁹

(define (count-leaves x)
  (cond ((null? x) 0)
        ((not (pair? x)) 1)
        (else (+ (count-leaves (car x))
                 (count-leaves (cdr x))))))

Ymarfer 2.24: Tybiwch ein bod yn gwerthuso’r mynegiad (list 1 (list 2 (list 3 4))). Rhowch y canlyniad a argreffir gan y dehonglydd, y strwythur blychau a phwyntyddion cyfatebol, a’i ddehongliad fel coeden (fel yn Ffigur 2.6).

Ymarfer 2.25: Rhowch gyfuniadau o car ac cdr a fydd yn dewis 7 o bob un o’r rhestrau canlynol:

(1 3 (5 7) 9)
((7))
(1 (2 (3 (4 (5 (6 7))))))

Ymarfer 2.26: Tybiwch ein bod yn diffinio x ac y yn ddwy restr:

(define x (list 1 2 3))
(define y (list 4 5 6))

Pa ganlyniad a argreffir gan y dehonglydd wrth werthuso pob un o’r mynegiadau canlynol:

(append x y)
(cons x y)
(list x y)

Ymarfer 2.27: Addaswch eich gweithdrefn reverse o Ymarfer 2.18 i gynhyrchu gweithdrefn deep-reverse sy’n cymryd rhestr fel arg ac yn dychwelyd fel ei gwerth y rhestr â’i helfennau yn y drefn wrthdro, a phob isrestr hefyd wedi’i gwrthdroi ar bob lefel. Er enghraifft,

(define x 
  (list (list 1 2) (list 3 4)))

x
((1 2) (3 4))

(reverse x)
((3 4) (1 2))

(deep-reverse x)
((4 3) (2 1))

Ymarfer 2.28: Ysgrifennwch weithdrefn fringe sy’n cymryd coeden (wedi’i chynrychioli fel rhestr) fel arg ac yn dychwelyd rhestr y mae ei helfennau’n holl ddail y goeden wedi’u trefnu o’r chwith i’r dde. Er enghraifft,

(define x 
  (list (list 1 2) (list 3 4)))

(fringe x)
(1 2 3 4)

(fringe (list x x))
(1 2 3 4 1 2 3 4)

Ymarfer 2.29: Mae symudyn deuaidd (binary mobile) yn cynnwys dwy gangen, cangen chwith a changen dde. Mae pob cangen yn wialen o hyd penodol, ac oddi arni mae naill ai pwysau neu symudyn deuaidd arall yn hongian. Gallwn gynrychioli symudyn deuaidd drwy ddefnyddio data cyfansawdd, gan ei adeiladu o ddwy gangen (er enghraifft, drwy ddefnyddio list):

(define (make-mobile left right)
  (list left right))

Adeiladir cangen o length (y mae’n rhaid iddo fod yn rhif) ynghyd â structure, a all fod naill ai’n rhif (sy’n cynrychioli pwysau syml) neu’n symudyn arall:

(define (make-branch length structure)
  (list length structure))

1. Ysgrifennwch y detholwyr cyfatebol left-branch ac right-branch, sy’n dychwelyd canghennau symudyn, ac branch-length ac branch-structure, sy’n dychwelyd cydrannau cangen.
2. Gan ddefnyddio eich detholwyr, diffiniwch weithdrefn total-weight sy’n dychwelyd cyfanswm pwysau symudyn.
3. Dywedir bod symudyn mewn cydbwysedd os yw’r trorym a roddir gan ei gangen chwith uchaf yn hafal i’r un a roddir gan ei gangen dde uchaf (hynny yw, os yw hyd y wialen chwith wedi’i luosi â’r pwysau sy’n hongian oddi ar y wialen honno yn hafal i’r lluoswm cyfatebol ar yr ochr dde) ac os yw pob un o’r is-symudynnau sy’n hongian oddi ar ei ganghennau mewn cydbwysedd. Dyluniwch draethiad sy’n profi a yw symudyn deuaidd mewn cydbwysedd.
4. Tybiwch ein bod yn newid cynrychioliad symudynnau fel bod yr adeiladwyr yn

   (define (make-mobile left right)
     (cons left right))
   
   (define (make-branch length structure)
     (cons length structure))

   Faint sydd angen i chi newid eich rhaglenni i drosi i’r cynrychioliad newydd?

Mapio dros goed

Yn union fel y mae map yn haniaeth rymus ar gyfer ymdrin â dilyniannau, mae map ynghyd â dychweliad yn haniaeth rymus ar gyfer ymdrin â choed. Er enghraifft, mae’r weithdrefn scale-tree, sy’n cyfateb i scale-list yn 2.2.1, yn cymryd fel argiau ffactor rhifiadol a choeden y mae ei dail yn rhifau. Mae’n dychwelyd coeden o’r un siâp, lle mae pob rhif wedi’i luosi â’r ffactor. Mae’r cynllun dychweliadol ar gyfer scale-tree yn debyg i’r un ar gyfer count-leaves:

(define (scale-tree tree factor)
  (cond ((null? tree) nil)
        ((not (pair? tree)) 
         (* tree factor))
        (else
         (cons (scale-tree (car tree) 
                           factor)
               (scale-tree (cdr tree) 
                           factor)))))

(scale-tree (list 1 
                  (list 2 (list 3 4) 5) 
                  (list 6 7))
            10)

(10 (20 (30 40) 50) (60 70))

Ffordd arall o weithredu scale-tree yw ystyried y goeden yn ddilyniant o isgoed a defnyddio map. Mapiwn dros y dilyniant, gan raddio pob isgoeden yn ei thro, a dychwelyd y rhestr o ganlyniadau. Yn yr achos sylfaenol, lle mae’r goeden yn ddeilen, lluoswn â’r ffactor yn syml:

(define (scale-tree tree factor)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (scale-tree sub-tree factor)
             (* sub-tree factor)))
       tree))

Gellir gweithredu llawer o weithrediadau coed drwy gyfuniadau tebyg o weithrediadau dilyniant a dychweliad.

Ymarfer 2.30: Diffiniwch weithdrefn square-tree sy’n cyfateb i’r weithdrefn square-list yn Ymarfer 2.21. Hynny yw, dylai square-tree ymddwyn fel a ganlyn:

(square-tree
 (list 1
       (list 2 (list 3 4) 5)
       (list 6 7)))
(1 (4 (9 16) 25) (36 49))

Diffiniwch square-tree yn uniongyrchol (h.y., heb ddefnyddio unrhyw weithdrefnau trefn uwch) a hefyd drwy ddefnyddio map a dychweliad.

Ymarfer 2.31: Haniaethwch eich ateb i Ymarfer 2.30 i gynhyrchu gweithdrefn tree-map sydd â’r briodwedd y gellid diffinio square-tree fel

(define (square-tree tree) 
  (tree-map square tree))

Ymarfer 2.32: Gallwn gynrychioli set fel rhestr o elfennau gwahanol, a gallwn gynrychioli set holl is-setiau’r set fel rhestr o restrau. Er enghraifft, os mai (1 2 3) yw’r set, yna (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)) yw set yr holl is-setiau. Cwblhewch y diffiniad canlynol o weithdrefn sy’n cynhyrchu set is-setiau set, a rhowch esboniad clir o pam mae’n gweithio:

(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map ⟨??⟩ rest)))))

2.2.3Dilyniannau fel Rhyngwynebau Confensiynol

Wrth weithio â data cyfansawdd, pwysleisiwyd sut mae haniaethu data yn caniatáu inni ddylunio rhaglenni heb fynd yn sownd ym manylion cynrychioliadau data, a sut mae haniaethu’n cadw’r hyblygrwydd inni arbrofi â chynrychioliadau amgen. Yn yr adran hon, cyflwynwn egwyddor ddylunio rymus arall ar gyfer gweithio â strwythurau data—defnyddio rhyngwynebau confensiynol.

Yn 1.3 gwelsom sut y gall haniaethau rhaglen, wedi’u gweithredu fel gweithdrefnau trefn uwch, ddal patrymau cyffredin mewn rhaglenni sy’n ymdrin â data rhifiadol. Mae ein gallu i lunio gweithrediadau cyfatebol ar gyfer gweithio â data cyfansawdd yn dibynnu’n hanfodol ar yr arddull a ddefnyddiwn i drin ein strwythurau data. Ystyriwch, er enghraifft, y weithdrefn ganlynol, sy’n cyfateb i’r weithdrefn count-leaves yn 2.2.2, sy’n cymryd coeden fel arg ac yn cyfrifo swm sgwariau’r dail sy’n odrifau:

(define (sum-odd-squares tree)
  (cond ((null? tree) 0)
        ((not (pair? tree))
         (if (odd? tree) (square tree) 0))
        (else (+ (sum-odd-squares 
                  (car tree))
                 (sum-odd-squares 
                  (cdr tree))))))

Ar yr wyneb, mae’r weithdrefn hon yn wahanol iawn i’r un ganlynol, sy’n adeiladu rhestr o’r holl rifau Fibonacci eilrif $\text{Fib}(k)$, lle mae $k$ yn llai na neu’n hafal i gyfanrif penodol $n$:

(define (even-fibs n)
  (define (next k)
    (if (> k n)
        nil
        (let ((f (fib k)))
          (if (even? f)
              (cons f (next (+ k 1)))
              (next (+ k 1))))))
  (next 0))

Er bod y ddwy weithdrefn hyn yn wahanol iawn o ran strwythur, mae disgrifiad mwy haniaethol o’r ddau gyfrifiad yn datgelu llawer iawn o debygrwydd. Mae’r rhaglen gyntaf yn

• rhestru dail coeden;
• eu hidlo, gan ddethol yr odrifau;
• sgwario pob un o’r rhai a ddetholwyd; ac yn
• cronni’r canlyniadau drwy ddefnyddio +, gan ddechrau gyda 0.

Mae’r ail raglen yn

• rhestru’r cyfanrifau o 0 i $n$;
• cyfrifo’r rhif Fibonacci ar gyfer pob cyfanrif;
• eu hidlo, gan ddethol yr eilrifau; ac yn
• cronni’r canlyniadau drwy ddefnyddio cons, gan ddechrau gyda’r rhestr wag.

Byddai peiriannydd prosesu signalau yn ei chael yn naturiol gysyniadoli’r prosesau hyn yn nhermau signalau sy’n llifo drwy raeadr o gamau, pob un yn gweithredu rhan o gynllun y rhaglen, fel y dangosir yn Ffigur 2.7. Yn sum-odd-squares, dechreuwn â rhestrydd, sy’n cynhyrchu “signal” sy’n cynnwys dail coeden benodol. Pasir y signal hwn drwy hidlydd, sy’n dileu pob elfen heblaw’r odrifau. Pasir y signal canlyniadol yn ei dro drwy fapiad, sef “trawsddygiadur” sy’n cymhwyso’r weithdrefn square i bob elfen. Yna bwydir allbwn y mapiad i gronnwr, sy’n cyfuno’r elfennau drwy ddefnyddio +, gan ddechrau o 0 cychwynnol. Mae’r cynllun ar gyfer even-fibs yn gyfatebol.

Yn anffodus, nid yw’r ddau ddiffiniad gweithdrefn uchod yn dangos y strwythur llif signalau hwn. Er enghraifft, os archwiliwn y weithdrefn sum-odd-squares, gwelwn fod y rhestru’n cael ei weithredu’n rhannol gan y profion null? ac pair? ac yn rhannol gan strwythur dychweliadol coediog y weithdrefn. Yn yr un modd, ceir y cronni’n rhannol yn y profion ac yn rhannol yn yr adio a ddefnyddir yn y dychweliad. Yn gyffredinol, nid oes rhannau penodol o’r naill weithdrefn na’r llall sy’n cyfateb i’r elfennau yn y disgrifiad llif signalau. Mae ein dwy weithdrefn yn dadelfennu’r cyfrifiadau mewn ffordd wahanol, gan wasgaru’r rhestru dros y rhaglen a’i gymysgu â’r mapio, yr hidlo, a’r cronni. Pe gallem drefnu ein rhaglenni i wneud y strwythur llif signalau yn amlwg yn y gweithdrefnau a ysgrifennwn, byddai hyn yn cynyddu eglurder cysyniadol y cod canlyniadol.

Gweithrediadau Dilyniant

Yr allwedd i drefnu rhaglenni fel eu bod yn adlewyrchu’r strwythur llif signalau yn gliriach yw canolbwyntio ar y “signalau” sy’n llifo o un cam yn y broses i’r nesaf. Os cynrychiolwn y signalau hyn fel rhestrau, gallwn ddefnyddio gweithrediadau rhestr i weithredu’r prosesu ym mhob un o’r camau. Er enghraifft, gallwn weithredu camau mapio’r diagramau llif signalau drwy ddefnyddio’r weithdrefn map o 2.2.1:

(map square (list 1 2 3 4 5))
(1 4 9 16 25)

Cyflawnir hidlo dilyniant i ddethol dim ond yr elfennau hynny sy’n bodloni traethiad penodol drwy

(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate 
                       (cdr sequence))))
        (else  (filter predicate 
                       (cdr sequence)))))

Er enghraifft,

(filter odd? (list 1 2 3 4 5))
(1 3 5)

Gellir gweithredu cronni drwy

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op 
                      initial 
                      (cdr sequence)))))

(accumulate + 0 (list 1 2 3 4 5))
15
(accumulate * 1 (list 1 2 3 4 5))
120
(accumulate cons nil (list 1 2 3 4 5))
(1 2 3 4 5)

Y cyfan sy’n weddill i weithredu diagramau llif signalau yw rhestru’r dilyniant o elfennau i’w prosesu. Ar gyfer even-fibs, mae angen cynhyrchu’r dilyniant o gyfanrifau mewn ystod benodol, a gallwn wneud hynny fel a ganlyn:

(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low 
            (enumerate-interval 
             (+ low 1) 
             high))))

(enumerate-interval 2 7)
(2 3 4 5 6 7)

I restru dail coeden, gallwn ddefnyddio⁸⁰

(define (enumerate-tree tree)
  (cond ((null? tree) nil)
        ((not (pair? tree)) (list tree))
        (else (append 
               (enumerate-tree (car tree))
               (enumerate-tree (cdr tree))))))

(enumerate-tree (list 1 (list 2 (list 3 4)) 5))
(1 2 3 4 5)

Gallwn yn awr ail-lunio sum-odd-squares ac even-fibs fel yn y diagramau llif signalau. Ar gyfer sum-odd-squares, rhestrwn ddilyniant dail y goeden, hidlwn hwn i gadw’r odrifau yn y dilyniant yn unig, sgwariwn bob elfen, a symiwn y canlyniadau:

(define (sum-odd-squares tree)
  (accumulate 
   +
   0
   (map square
        (filter odd?
                (enumerate-tree tree)))))

Ar gyfer even-fibs, rhestrwn y cyfanrifau o 0 i $n$, cynhyrchwn y rhif Fibonacci ar gyfer pob un o’r cyfanrifau hyn, hidlwn y dilyniant canlyniadol i gadw’r elfennau eilrif yn unig, a chronnwn y canlyniadau mewn rhestr:

(define (even-fibs n)
  (accumulate 
   cons
   nil
   (filter even?
           (map fib
                (enumerate-interval 0 n)))))

Gwerth mynegi rhaglenni fel gweithrediadau dilyniant yw bod hyn yn ein helpu i greu dyluniadau rhaglen modiwlar, hynny yw, dyluniadau a adeiladir drwy gyfuno darnau sy’n gymharol annibynnol. Gallwn annog dylunio modiwlar drwy ddarparu llyfrgell o gydrannau safonol ynghyd â rhyngwyneb confensiynol ar gyfer cysylltu’r cydrannau mewn ffyrdd hyblyg.

Mae adeiladu modiwlar yn strategaeth rymus ar gyfer rheoli cymhlethdod mewn dylunio peirianyddol. Mewn cymwysiadau prosesu signalau go iawn, er enghraifft, mae dylunwyr yn adeiladu systemau’n rheolaidd drwy gysylltu mewn rhaeadr elfennau a ddewiswyd o deuluoedd safonedig o hidlyddion a thrawsddygiaduron. Yn yr un modd, mae gweithrediadau dilyniant yn darparu llyfrgell o elfennau rhaglen safonol y gallwn eu cyfuno mewn amryw ffyrdd. Er enghraifft, gallwn ailddefnyddio darnau o’r gweithdrefnau sum-odd-squares ac even-fibs mewn rhaglen sy’n adeiladu rhestr o sgwariau’r $n+1$ rhif Fibonacci cyntaf:

(define (list-fib-squares n)
  (accumulate 
   cons
   nil
   (map square
        (map fib
             (enumerate-interval 0 n)))))

(list-fib-squares 10)
(0 1 1 4 9 25 64 169 441 1156 3025)

Gallwn aildrefnu’r darnau a’u defnyddio i gyfrifo lluoswm sgwariau’r cyfanrifau od mewn dilyniant:

(define 
  (product-of-squares-of-odd-elements
   sequence)
  (accumulate 
   *
   1
   (map square (filter odd? sequence))))

(product-of-squares-of-odd-elements 
 (list 1 2 3 4 5))
225

Gallwn hefyd lunio cymwysiadau prosesu data confensiynol yn nhermau gweithrediadau dilyniant. Tybiwch fod gennym ddilyniant o gofnodion personél a’n bod eisiau canfod cyflog y rhaglennydd sy’n ennill fwyaf. Tybiwch fod gennym ddetholwr salary sy’n dychwelyd cyflog cofnod, a thraethiad programmer? sy’n profi a yw cofnod yn perthyn i raglennydd. Yna gallwn ysgrifennu

(define 
  (salary-of-highest-paid-programmer
   records)
  (accumulate 
   max
   0
   (map salary
        (filter programmer? records))))

Dim ond awgrym o’r ystod enfawr o weithrediadau y gellir eu mynegi fel gweithrediadau dilyniant a roddir gan yr enghreifftiau hyn.⁸¹

Mae dilyniannau, a weithredir yma fel rhestrau, yn gwasanaethu fel rhyngwyneb confensiynol sy’n caniatáu inni gyfuno modiwlau prosesu. Yn ogystal, pan gynrychiolwn strwythurau’n unffurf fel dilyniannau, rydym wedi lleoli’r dibyniaethau ar strwythurau data yn ein rhaglenni mewn nifer bach o weithrediadau dilyniant. Drwy newid y rhain, gallwn arbrofi â chynrychioliadau amgen o ddilyniannau, gan adael dyluniad cyffredinol ein rhaglenni yn gyfan. Defnyddiwn y gallu hwn yn 3.5, pan gyffredinolwn y patrwm prosesu dilyniannau i gynnwys dilyniannau anfeidrol.

Ymarfer 2.33: Llenwch y mynegiadau coll i gwblhau’r diffiniadau canlynol o rai gweithrediadau sylfaenol ar gyfer trin rhestrau fel gweithrediadau cronni:

(define (map p sequence)
  (accumulate (lambda (x y) ⟨??⟩) 
              nil sequence))

(define (append seq1 seq2)
  (accumulate cons ⟨??⟩ ⟨??⟩))

(define (length sequence)
  (accumulate ⟨??⟩ 0 sequence))

Ymarfer 2.34: Gellir ffurfio gwerthuso polynomial mewn $x$ ar werth penodol o $x$ fel proses gronni. Gwerthuswn y polynomial $$a_n{x}^n+a_{n-<!--\; -\; -->1}{x}^{n-<!--\; -\; -->1}+\cdots <!--\; \cdots \; -->+a_{1}x+a_0$$ drwy ddefnyddio algorithm adnabyddus o’r enw rheol Horner, sy’n strwythuro’r cyfrifiad fel $$(\dots <!--\; \dots \; -->(a_{n}x+a_{n-<!--\; -\; -->1})x+\cdots <!--\; \cdots \; -->+a_1)x+a_0.$$ Mewn geiriau eraill, dechreuwn ag $a_n$, lluoswn ag $x$, ychwanegwn $a_{n-<!--\; -\; -->1}$, lluoswn ag $x$, ac yn y blaen, nes cyrraedd $a_0$.⁸²

Llenwch y templed canlynol i gynhyrchu gweithdrefn sy’n gwerthuso polynomial drwy ddefnyddio rheol Horner. Tybiwch fod cyfernodau’r polynomial wedi’u trefnu mewn dilyniant, o $a_0$ hyd at $a_n$.

(define 
  (horner-eval x coefficient-sequence)
  (accumulate 
   (lambda (this-coeff higher-terms)
     ⟨??⟩)
   0
   coefficient-sequence))

Er enghraifft, i gyfrifo $1+3x+5x^3+x^5$ pan fo $x=2$ byddech yn gwerthuso

(horner-eval 2 (list 1 3 0 5 0 1))

Ymarfer 2.35: Ailddiffiniwch count-leaves o 2.2.2 fel proses gronni:

(define (count-leaves t)
  (accumulate ⟨??⟩ ⟨??⟩ (map ⟨??⟩ ⟨??⟩)))

Ymarfer 2.36: Mae’r weithdrefn accumulate-n yn debyg i accumulate, heblaw ei bod yn cymryd fel ei thrydydd arg ddilyniant o ddilyniannau, y tybir bod ganddynt oll yr un nifer o elfennau. Mae’n cymhwyso’r weithdrefn gronni ddynodedig i gyfuno holl elfennau cyntaf y dilyniannau, holl ail elfennau’r dilyniannau, ac yn y blaen, ac yn dychwelyd dilyniant o’r canlyniadau. Er enghraifft, os yw s yn ddilyniant sy’n cynnwys pedwar dilyniant, ((1 2 3) (4 5 6) (7 8 9) (10 11 12)), yna dylai gwerth (accumulate-n + 0 s) fod yn ddilyniant (22 26 30). Llenwch y mynegiadau coll yn y diffiniad canlynol o accumulate-n:

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      nil
      (cons (accumulate op init ⟨??⟩)
            (accumulate-n op init ⟨??⟩))))

Ymarfer 2.37: Tybiwch ein bod yn cynrychioli fectorau v = $(v_i)$ fel dilyniannau o rifau, a matricsau m = $(m_{ij})$ fel dilyniannau o fectorau (rhesi’r matrics). Er enghraifft, cynrychiolir y matrics $$\left(\begin{array}{cccc}1& 2& 3& 4\\ 4& 5& 6& 6\\ 6& 7& 8& 9\end{array}\right)$$ fel y dilyniant ((1 2 3 4) (4 5 6 6) (6 7 8 9)). Gyda’r cynrychioliad hwn, gallwn ddefnyddio gweithrediadau dilyniant i fynegi’n gryno y gweithrediadau matrics a fector sylfaenol. Dyma’r gweithrediadau hyn (a ddisgrifir mewn unrhyw lyfr ar algebra matricsau): $$\begin{array}{rl}\text{(dot-product v w)}& \text{yn dychwelyd y swm}{\mathrm{\Sigma <!--\; \Sigma \; -->}}_i{v}_i{w}_i;\\ \text{(matrix-*-vector m v)}& \text{yn dychwelyd y fector}\mathbf{t},\\ & \text{lle mae}{t}_i={\mathrm{\Sigma <!--\; \Sigma \; -->}}_j{m}_{ij}{v}_j;\\ \text{(matrix-*-matrix m n)}& \text{yn dychwelyd y matrics}\mathbf{p},\\ & \text{lle mae}{p}_{ij}={\mathrm{\Sigma <!--\; \Sigma \; -->}}_k{m}_{ik}{n}_{kj};\\ \text{(transpose m)}& \text{yn dychwelyd y matrics}\mathbf{n},\\ & \text{lle mae}{n}_{ij}=m_{ji}.\end{array}$$ Gallwn ddiffinio’r lluoswm dot fel⁸³

(define (dot-product v w)
  (accumulate + 0 (map * v w)))

Llenwch y mynegiadau coll yn y gweithdrefnau canlynol ar gyfer cyfrifo’r gweithrediadau matrics eraill. (Diffinnir y weithdrefn accumulate-n yn Ymarfer 2.36.)

(define (matrix-*-vector m v)
  (map ⟨??⟩ m))

(define (transpose mat)
  (accumulate-n ⟨??⟩ ⟨??⟩ mat))

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map ⟨??⟩ m)))

Ymarfer 2.38: Gelwir y weithdrefn accumulate hefyd yn fold-right, oherwydd ei bod yn cyfuno elfen gyntaf y dilyniant â chanlyniad cyfuno’r holl elfennau i’r dde. Mae hefyd fold-left, sy’n debyg i fold-right, heblaw ei bod yn cyfuno elfennau gan weithio i’r cyfeiriad arall:

(define (fold-left op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest))
              (cdr rest))))
  (iter initial sequence))

Beth yw gwerthoedd

(fold-right / 1 (list 1 2 3))
(fold-left  / 1 (list 1 2 3))
(fold-right list nil (list 1 2 3))
(fold-left  list nil (list 1 2 3))

Rhowch briodwedd y dylai op ei bodloni i warantu y bydd fold-right ac fold-left yn cynhyrchu’r un gwerthoedd ar gyfer unrhyw ddilyniant.

Ymarfer 2.39: Cwblhewch y diffiniadau canlynol o reverse (Ymarfer 2.18) yn nhermau fold-right ac fold-left o Ymarfer 2.38:

(define (reverse sequence)
  (fold-right 
   (lambda (x y) ⟨??⟩) nil sequence))

(define (reverse sequence)
  (fold-left 
   (lambda (x y) ⟨??⟩) nil sequence))

Mapiadau Nythol

Gallwn ehangu’r patrwm dilyniannau i gynnwys llawer o gyfrifiadau a fynegir yn gyffredin drwy ddefnyddio dolenni nythol.⁸⁴ Ystyriwch y broblem hon: O gael cyfanrif positif $n$, canfyddwch bob pâr trefnedig o gyfanrifau positif gwahanol $i$ ac $j$, lle $1\le <!--\; \le \; -->j<i\le <!--\; \le \; -->n$, fel bod $i+j$ yn gysefin. Er enghraifft, os yw $n$ yn 6, yna dyma’r parau: $$\begin{array}{cccccccc}i& 2& 3& 4& 4& 5& 6& 6\\ j& 1& 2& 1& 3& 2& 1& 5\\ i+j& 3& 5& 5& 7& 7& 7& 11\end{array}$$ Ffordd naturiol o drefnu’r cyfrifiad hwn yw cynhyrchu’r dilyniant o bob pâr trefnedig o gyfanrifau positif sy’n llai na neu’n hafal i $n$, hidlo i ddethol y parau hynny y mae eu swm yn gysefin, ac yna, ar gyfer pob pâr $(i,j)$ sy’n pasio drwy’r hidlydd, cynhyrchu’r tripled $(i,j,i+j)$.

Dyma ffordd o gynhyrchu’r dilyniant o barau: Ar gyfer pob cyfanrif $i\le <!--\; \le \; -->n$, rhestrwch y cyfanrifau $j<i$, ac ar gyfer pob $i$ ac $j$ o’r fath cynhyrchwch y pâr $(i,j)$. Yn nhermau gweithrediadau dilyniant, mapiwn ar hyd y dilyniant (enumerate-interval 1 n). Ar gyfer pob $i$ yn y dilyniant hwn, mapiwn ar hyd y dilyniant (enumerate-interval 1 (- i 1)). Ar gyfer pob $j$ yn y dilyniant olaf hwn, cynhyrchwn y pâr (list i j). Mae hyn yn rhoi dilyniant o barau inni ar gyfer pob $i$. Mae cyfuno’r holl ddilyniannau ar gyfer pob $i$ (drwy gronni ag append) yn cynhyrchu’r dilyniant gofynnol o barau:⁸⁵

(accumulate 
 append
 nil
 (map (lambda (i)
        (map (lambda (j) 
               (list i j))
             (enumerate-interval 1 (- i 1))))
      (enumerate-interval 1 n)))

Mae’r cyfuniad o fapio a chronni ag append mor gyffredin yn y math hwn o raglen fel y byddwn yn ei ynysu fel gweithdrefn ar wahân:

(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))

Nawr hidlwch y dilyniant hwn o barau i ganfod y rhai y mae eu swm yn gysefin. Gelwir y traethiad hidlo ar gyfer pob elfen yn y dilyniant; pâr yw ei arg a rhaid iddo echdynnu’r cyfanrifau o’r pâr. Felly, y traethiad i’w gymhwyso i bob elfen yn y dilyniant yw

(define (prime-sum? pair)
  (prime? (+ (car pair) (cadr pair))))

Yn olaf, cynhyrchwch y dilyniant o ganlyniadau drwy fapio dros y parau a hidlwyd gan ddefnyddio’r weithdrefn ganlynol, sy’n adeiladu tripled sy’n cynnwys dwy elfen y pâr ynghyd â’u swm:

(define (make-pair-sum pair)
  (list (car pair) 
        (cadr pair) 
        (+ (car pair) (cadr pair))))

Mae cyfuno’r holl gamau hyn yn rhoi’r weithdrefn gyflawn:

(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter 
        prime-sum?
        (flatmap
         (lambda (i)
           (map (lambda (j) 
                  (list i j))
                (enumerate-interval 
                 1 
                 (- i 1))))
         (enumerate-interval 1 n)))))

Mae mapiadau nythol hefyd yn ddefnyddiol ar gyfer dilyniannau heblaw’r rhai sy’n rhestru cyfyngau. Tybiwch ein bod yn dymuno cynhyrchu holl drynewidiadau set $S;$, hynny yw, yr holl ffyrdd o drefnu eitemau’r set. Er enghraifft, trynewidiadau $\{1,2,3\}$ yw $\{1,2,3\}$, $\{1,3,2\}$, $\{2,1,3\}$, $\{2,3,1\}$, $\{3,1,2\}$, ac $\{3,2,1\}$. Dyma gynllun ar gyfer cynhyrchu trynewidiadau $S$: Ar gyfer pob eitem $x$ yn $S$, cynhyrchwch yn ddychweliadol y dilyniant o drynewidiadau $S-<!--\; -\; -->x$,⁸⁶ ac ychwanegwch $x$ at flaen pob un. Mae hyn yn rhoi, ar gyfer pob $x$ yn $S$, y dilyniant o drynewidiadau $S$ sy’n dechrau ag $x$. Mae cyfuno’r dilyniannau hyn ar gyfer pob $x$ yn rhoi holl drynewidiadau $S$:⁸⁷

(define (permutations s)
  (if (null? s)   ; empty set?
      (list nil)  ; sequence containing empty set
      (flatmap (lambda (x)
                 (map (lambda (p) 
                        (cons x p))
                      (permutations 
                       (remove x s))))
               s)))

Sylwch sut mae’r strategaeth hon yn lleihau’r broblem o gynhyrchu trynewidiadau $S$ i’r broblem o gynhyrchu trynewidiadau setiau sydd â llai o elfennau nag $S$. Yn yr achos terfynol, gweithiwn ein ffordd i lawr at y rhestr wag, sy’n cynrychioli set heb elfennau. Ar gyfer hon, cynhyrchwn (list nil), sef dilyniant ag un eitem, sef y set heb elfennau. Mae’r weithdrefn remove a ddefnyddir yn permutations yn dychwelyd yr holl eitemau mewn dilyniant penodol heblaw am eitem benodol. Gellir mynegi hyn fel hidlydd syml:

(define (remove item sequence)
  (filter (lambda (x) (not (= x item)))
          sequence))

Ymarfer 2.40: Diffiniwch weithdrefn unique-pairs sydd, o gael cyfanrif $n$, yn cynhyrchu’r dilyniant o barau $(i,j)$ gyda $1\le <!--\; \le \; -->j<i\le <!--\; \le \; -->n$. Defnyddiwch unique-pairs i symleiddio’r diffiniad o prime-sum-pairs a roddwyd uchod.

Ymarfer 2.41: Ysgrifennwch weithdrefn i ganfod pob tripled trefnedig o gyfanrifau positif gwahanol $i$, $j$, ac $k$ sy’n llai na neu’n hafal i gyfanrif penodol $n$ ac y mae eu swm yn gyfanrif penodol $s$.

Ymarfer 2.42: Mae “pos yr wyth brenhines” yn gofyn sut i osod wyth brenhines ar fwrdd gwyddbwyll fel nad yw unrhyw frenhines dan fygythiad gan unrhyw un arall (h.y., nid oes dwy frenhines yn yr un rhes, colofn, na chroeslin). Dangosir un datrysiad posibl yn Ffigur 2.8. Un ffordd o ddatrys y pos yw gweithio ar draws y bwrdd, gan osod brenhines ym mhob colofn. Ar ôl inni osod $k-<!--\; -\; -->1$ brenhines, rhaid gosod brenhines $k^{\text{fed}}$ mewn safle lle nad yw’n bygwth unrhyw un o’r breninesau sydd eisoes ar y bwrdd. Gallwn lunio’r dull hwn yn ddychweliadol: Tybiwch ein bod eisoes wedi cynhyrchu’r dilyniant o’r holl ffyrdd posibl o osod $k-<!--\; -\; -->1$ brenhines yn $k-<!--\; -\; -->1$ colofn gyntaf y bwrdd. Ar gyfer pob un o’r ffyrdd hyn, cynhyrchwch set estynedig o safleoedd drwy osod brenhines ym mhob rhes o golofn $k^{\text{fed}}$. Nawr hidlwch y rhain, gan gadw’r safleoedd hynny yn unig lle mae’r frenhines yng ngholofn $k^{\text{fed}}$ yn ddiogel mewn perthynas â’r breninesau eraill. Mae hyn yn cynhyrchu’r dilyniant o’r holl ffyrdd o osod $k$ brenhines yn $k$ colofn gyntaf y bwrdd. Drwy barhau â’r broses hon, cynhyrchwn nid un datrysiad yn unig, ond holl ddatrysiadau’r pos.

Gweithredwn y datrysiad hwn fel gweithdrefn queens, sy’n dychwelyd dilyniant o’r holl ddatrysiadau i’r broblem o osod $n$ brenhines ar fwrdd gwyddbwyll $n\times <!--\; \times \; -->n$. Mae gan Queens weithdrefn fewnol queen-cols sy’n dychwelyd y dilyniant o’r holl ffyrdd o osod breninesau yn $k$ colofn gyntaf y bwrdd.

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) 
           (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position 
                    new-row 
                    k 
                    rest-of-queens))
                 (enumerate-interval 
                  1 
                  board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

Yn y weithdrefn hon mae rest-of-queens yn ffordd o osod $k-<!--\; -\; -->1$ brenhines yn y $k-<!--\; -\; -->1$ colofn gyntaf, ac mae new-row yn rhes arfaethedig ar gyfer gosod brenhines colofn $k^{\text{fed}}$. Cwblhewch y rhaglen drwy weithredu’r cynrychioliad ar gyfer setiau o safleoedd ar y bwrdd, gan gynnwys y weithdrefn adjoin-position, sy’n ychwanegu safle rhes-colofn newydd at set o safleoedd, ac empty-board, sy’n cynrychioli set wag o safleoedd. Rhaid i chi hefyd ysgrifennu’r weithdrefn safe?, sy’n penderfynu, ar gyfer set o safleoedd, a yw’r frenhines yng ngholofn $k^{\text{fed}}$ yn ddiogel mewn perthynas â’r lleill. (Sylwch nad oes angen ond gwirio a yw’r frenhines newydd yn ddiogel—mae diogelwch y breninesau eraill mewn perthynas â’i gilydd eisoes wedi’i warantu.)

Ymarfer 2.43: Mae Louis Reasoner yn cael amser ofnadwy wrth wneud Ymarfer 2.42. Mae ei weithdrefn queens i’w gweld yn gweithio, ond mae’n rhedeg yn eithriadol o araf. (Nid yw Louis byth yn llwyddo i aros yn ddigon hir iddi ddatrys hyd yn oed yr achos $6\times <!--\; \times \; -->6$.) Pan ofynna Louis i Eva Lu Ator am help, mae hi’n tynnu sylw at y ffaith ei fod wedi cyfnewid trefn y mapiadau nythol yn yr flatmap, gan ei ysgrifennu fel

(flatmap
 (lambda (new-row)
   (map (lambda (rest-of-queens)
          (adjoin-position 
           new-row k rest-of-queens))
        (queen-cols (- k 1))))
 (enumerate-interval 1 board-size))

Esboniwch pam mae’r cyfnewid hwn yn gwneud i’r rhaglen redeg yn araf. Amcangyfrifwch pa mor hir y bydd rhaglen Louis yn ei gymryd i ddatrys pos yr wyth brenhines, gan dybio bod y rhaglen yn Ymarfer 2.42 yn datrys y pos mewn amser $T$.

2.2.4Enghraifft: Iaith Darluniau

Mae’r adran hon yn cyflwyno iaith syml ar gyfer llunio darluniau sy’n dangos grym haniaethu data a’r briodwedd cau, ac sydd hefyd yn defnyddio gweithdrefnau trefn uwch mewn ffordd hanfodol. Dyluniwyd yr iaith i’w gwneud yn hawdd arbrofi â phatrymau megis y rhai yn Ffigur 2.9, sy’n cynnwys elfennau ailadroddus a symudir ac a raddir.⁸⁸ Yn yr iaith hon, cynrychiolir y gwrthrychau data a gyfunir fel gweithdrefnau yn hytrach nag fel strwythur rhestr. Yn union fel yr oedd cons, sy’n bodloni’r briodwedd cau, yn caniatáu inni adeiladu strwythur rhestr o gymhlethdod mympwyol yn hawdd, mae’r gweithrediadau yn yr iaith hon, sydd hefyd yn bodloni’r briodwedd cau, yn caniatáu inni adeiladu patrymau o gymhlethdod mympwyol yn hawdd.

Yr iaith darluniau

Pan ddechreuasom astudio rhaglennu yn 1.1, pwysleisiasom bwysigrwydd disgrifio iaith drwy ganolbwyntio ar ei helfennau cyntefig, ei moddion cyfuno, a’i moddion haniaethu. Dilynwn y fframwaith hwnnw yma.

Rhan o geinder yr iaith darluniau hon yw mai dim ond un math o elfen sydd, a elwir yn beintiwr. Mae peintiwr yn llunio delwedd a symudir ac a raddir i ffitio o fewn ffrâm benodedig ar ffurf paralelogram. Er enghraifft, mae peintiwr cyntefig y byddwn yn ei alw’n wave sy’n gwneud llun llinell bras, fel y dangosir yn Ffigur 2.10. Mae gwir siâp y llun yn dibynnu ar y ffrâm—cynhyrchir y pedair delwedd yn ffigur 2.10 gan yr un peintiwr wave, ond mewn perthynas â phedair ffrâm wahanol. Gall peintwyr fod yn fwy cywrain na hyn: Mae’r peintiwr cyntefig o’r enw rogers yn peintio darlun o sylfaenydd MIT, William Barton Rogers, fel y dangosir yn Ffigur 2.11.⁸⁹ Llunnir y pedair delwedd yn ffigur 2.11 mewn perthynas â’r un pedair ffrâm â’r delweddau wave yn ffigur 2.10.

I gyfuno delweddau, defnyddiwn amrywiol weithrediadau sy’n adeiladu peintwyr newydd o beintwyr penodol. Er enghraifft, mae’r gweithrediad beside yn cymryd dau beintiwr ac yn cynhyrchu peintiwr cyfansawdd newydd sy’n llunio delwedd y peintiwr cyntaf yn hanner chwith y ffrâm a delwedd yr ail beintiwr yn hanner dde’r ffrâm. Yn yr un modd, mae below yn cymryd dau beintiwr ac yn cynhyrchu peintiwr cyfansawdd sy’n llunio delwedd y peintiwr cyntaf islaw delwedd yr ail beintiwr. Mae rhai gweithrediadau’n trawsffurfio un peintiwr i gynhyrchu peintiwr newydd. Er enghraifft, mae flip-vert yn cymryd peintiwr ac yn cynhyrchu peintiwr sy’n llunio ei ddelwedd wyneb i waered, ac mae flip-horiz yn cynhyrchu peintiwr sy’n llunio delwedd y peintiwr gwreiddiol gyda’r chwith a’r dde wedi’u gwrthdroi.

Mae Ffigur 2.12 yn dangos llun peintiwr o’r enw wave4 a adeiladir mewn dau gam gan ddechrau ag wave:

(define wave2 (beside wave (flip-vert wave)))
(define wave4 (below wave2 wave2))

Wrth adeiladu delwedd gymhleth fel hyn rydym yn defnyddio’r ffaith bod peintwyr yn gaeedig o dan foddion cyfuno’r iaith. Mae beside neu below dau beintiwr ei hun yn beintiwr; felly, gallwn ei ddefnyddio fel elfen wrth wneud peintwyr mwy cymhleth. Fel wrth adeiladu strwythur rhestr drwy ddefnyddio cons, mae priodwedd cau ein data o dan y moddion cyfuno yn hanfodol i’r gallu i greu strwythurau cymhleth gan ddefnyddio ychydig o weithrediadau yn unig.

Unwaith y gallwn gyfuno peintwyr, hoffem allu haniaethu patrymau nodweddiadol o gyfuno peintwyr. Byddwn yn gweithredu gweithrediadau’r peintwyr fel gweithdrefnau Scheme. Mae hyn yn golygu nad oes angen mecanwaith haniaethu arbennig arnom yn yr iaith darluniau: Gan mai gweithdrefnau Scheme cyffredin yw’r moddion cyfuno, mae gennym yn awtomatig y gallu i wneud unrhyw beth â gweithrediadau peintwyr y gallwn ei wneud â gweithdrefnau. Er enghraifft, gallwn haniaethu’r patrwm yn wave4 fel

(define (flipped-pairs painter)
  (let ((painter2 
         (beside painter 
                 (flip-vert painter))))
    (below painter2 painter2)))

a diffinio wave4 fel enghraifft o’r patrwm hwn:

(define wave4 (flipped-pairs wave))

Gallwn hefyd ddiffinio gweithrediadau dychweliadol. Dyma un sy’n gwneud i beintwyr ymrannu a changhennu i’r dde fel y dangosir yn Ffigur 2.13 a Ffigur 2.14:

(define (right-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (right-split painter 
                                  (- n 1))))
        (beside painter 
                (below smaller smaller)))))

Gallwn gynhyrchu patrymau cytbwys drwy ganghennu i fyny yn ogystal ag i’r dde (gweler Ymarfer 2.44, Ffigur 2.13 a Ffigur 2.14):

(define (corner-split painter n)
  (if (= n 0)
      painter
      (let ((up (up-split painter (- n 1)))
            (right (right-split painter 
                                (- n 1))))
        (let ((top-left (beside up up))
              (bottom-right (below right 
                                   right))
              (corner (corner-split painter 
                                    (- n 1))))
          (beside (below painter top-left)
                  (below bottom-right 
                         corner))))))

Drwy osod pedwar copi o corner-split yn briodol, cawn batrwm o’r enw square-limit, y dangosir ei gymhwysiad i wave ac rogers yn Ffigur 2.9:

(define (square-limit painter n)
  (let ((quarter (corner-split painter n)))
    (let ((half (beside (flip-horiz quarter) 
                        quarter)))
      (below (flip-vert half) half))))

Ymarfer 2.44: Diffiniwch y weithdrefn up-split a ddefnyddir gan corner-split. Mae’n debyg i right-split, heblaw ei bod yn cyfnewid rolau below ac beside.

Gweithrediadau trefn uwch

Yn ogystal â haniaethu patrymau o gyfuno peintwyr, gallwn weithio ar lefel uwch, gan haniaethu patrymau o gyfuno gweithrediadau peintwyr. Hynny yw, gallwn ystyried gweithrediadau’r peintwyr yn elfennau i’w trin, a gallwn ysgrifennu moddion cyfuno ar gyfer yr elfennau hyn—gweithdrefnau sy’n cymryd gweithrediadau peintwyr fel argiau ac yn creu gweithrediadau peintwyr newydd.

Er enghraifft, mae flipped-pairs ac square-limit ill dau yn trefnu pedwar copi o ddelwedd peintiwr mewn patrwm sgwâr; dim ond yn y ffordd y maent yn cyfeirio’r copïau y maent yn gwahaniaethu. Un ffordd o haniaethu’r patrwm hwn o gyfuno peintwyr yw drwy’r weithdrefn ganlynol, sy’n cymryd pedwar gweithrediad peintiwr un arg ac yn cynhyrchu gweithrediad peintiwr sy’n trawsffurfio peintiwr penodol â’r pedwar gweithrediad hynny ac yn trefnu’r canlyniadau mewn sgwâr. Tl, tr, bl, ac br yw’r trawsffurfiadau i’w cymhwyso i’r copi chwith uchaf, y copi dde uchaf, y copi chwith isaf, a’r copi dde isaf, yn y drefn honno.

(define (square-of-four tl tr bl br)
  (lambda (painter)
    (let ((top (beside (tl painter) 
                       (tr painter)))
          (bottom (beside (bl painter) 
                          (br painter))))
      (below bottom top))))

Yna gellir diffinio flipped-pairs yn nhermau square-of-four fel a ganlyn:⁹⁰

(define (flipped-pairs painter)
  (let ((combine4 
         (square-of-four identity 
                         flip-vert
                         identity 
                         flip-vert)))
    (combine4 painter)))

a gellir mynegi square-limit fel⁹¹

(define (square-limit painter n)
  (let ((combine4 
         (square-of-four flip-horiz 
                         identity
                         rotate180 
                         flip-vert)))
    (combine4 (corner-split painter n))))

Ymarfer 2.45: Gellir mynegi Right-split ac up-split fel enghreifftiau o weithrediad rhannu cyffredinol. Diffiniwch weithdrefn split sydd â’r briodwedd bod gwerthuso

(define right-split (split beside below))
(define up-split (split below beside))

yn cynhyrchu gweithdrefnau right-split ac up-split sydd â’r un ymddygiad â’r rhai a ddiffiniwyd eisoes.

Fframiau

Cyn y gallwn ddangos sut i weithredu peintwyr a’u moddion cyfuno, rhaid inni ystyried fframiau yn gyntaf. Gellir disgrifio ffrâm gan dri fector—fector tarddbwynt a dau fector ymyl. Mae’r fector tarddbwynt yn pennu dadleoliad tarddbwynt y ffrâm o ryw darddbwynt absoliwt yn y plân, ac mae’r fectorau ymyl yn pennu dadleoliadau corneli’r ffrâm o’i tharddbwynt. Os yw’r ymylon yn berpendicwlar, bydd y ffrâm yn betryalog. Fel arall, bydd y ffrâm yn baralelogram mwy cyffredinol.

Mae Ffigur 2.15 yn dangos ffrâm a’i fectorau cysylltiedig. Yn unol â haniaethu data, nid oes angen inni fod yn benodol eto ynghylch sut y cynrychiolir fframiau, heblaw dweud bod adeiladydd make-frame, sy’n cymryd tri fector ac yn cynhyrchu ffrâm, a thri detholwr cyfatebol origin-frame, edge1-frame, ac edge2-frame (gweler Ymarfer 2.47).

Byddwn yn defnyddio cyfesurynnau yn y sgwâr uned $(0\le <!--\; \le \; -->x,y\le <!--\; \le \; -->1)$ i bennu delweddau. Gyda phob ffrâm, cysylltwn fapiad cyfesurynnau’r ffrâm, a ddefnyddir i symud a graddio delweddau i ffitio’r ffrâm. Mae’r mapiad yn trawsffurfio’r sgwâr uned yn ffrâm drwy fapio’r fector $\mathbf{v}=(x,y)$ i’r swm fectorau $$\text{Origin(Frame)}+x\cdot <!--\; \cdot \; -->{\text{Edge}}_1\text{(Frame)}+y\cdot <!--\; \cdot \; -->{\text{Edge}}_2\text{(Frame)}.$$ Er enghraifft, mapir (0, 0) i darddbwynt y ffrâm, (1, 1) i’r fertig sydd gyferbyn â’r tarddbwynt ar y groeslin, a (0.5, 0.5) i ganol y ffrâm. Gallwn greu mapiad cyfesurynnau ffrâm â’r weithdrefn ganlynol:⁹²

(define (frame-coord-map frame)
  (lambda (v)
    (add-vect
     (origin-frame frame)
     (add-vect 
      (scale-vect (xcor-vect v)
                  (edge1-frame frame))
      (scale-vect (ycor-vect v)
                  (edge2-frame frame))))))

Sylwch fod cymhwyso frame-coord-map i ffrâm yn dychwelyd gweithdrefn sydd, o gael fector, yn dychwelyd fector. Os yw’r fector arg yn y sgwâr uned, bydd y fector canlyniadol yn y ffrâm. Er enghraifft, mae

((frame-coord-map a-frame) (make-vect 0 0))

yn dychwelyd yr un fector â

(origin-frame a-frame)

Ymarfer 2.46: Gellir cynrychioli fector dau ddimensiwn $\mathbf{v}$ sy’n mynd o’r tarddbwynt at bwynt fel pâr sy’n cynnwys cyfesuryn $x$ a chyfesuryn $y$. Gweithredwch haniaeth data ar gyfer fectorau drwy roi adeiladydd make-vect a detholwyr cyfatebol xcor-vect ac ycor-vect. Yn nhermau eich detholwyr a’ch adeiladydd, gweithredwch weithdrefnau add-vect, sub-vect, ac scale-vect sy’n cyflawni’r gweithrediadau adio fectorau, tynnu fectorau, a lluosi fector â sgalar: $$\begin{array}{rcl}(x_1,y_1)+(x_2,y_2)& =& (x_1+x_2,y_1+y_2),\\ (x_1,y_1)-<!--\; -\; -->(x_2,y_2)& =& (x_1-<!--\; -\; -->x_2,y_1-<!--\; -\; -->y_2),\\ s\cdot <!--\; \cdot \; -->(x,y)& =& (sx,sy).\end{array}$$

Ymarfer 2.47: Dyma ddau adeiladydd posibl ar gyfer fframiau:

(define (make-frame origin edge1 edge2)
  (list origin edge1 edge2))

(define (make-frame origin edge1 edge2)
  (cons origin (cons edge1 edge2)))

Ar gyfer pob adeiladydd, darparwch y detholwyr priodol i gynhyrchu gweithrediad ar gyfer fframiau.

Peintwyr

Cynrychiolir peintiwr fel gweithdrefn sydd, o gael ffrâm fel arg, yn llunio delwedd benodol wedi’i symud a’i graddio i ffitio’r ffrâm. Hynny yw, os yw p yn beintiwr ac f yn ffrâm, yna cynhyrchwn ddelwedd p yn f drwy alw p ag f fel arg.

Mae manylion gweithredu peintwyr cyntefig yn dibynnu ar nodweddion penodol y system graffeg a’r math o ddelwedd i’w llunio. Er enghraifft, tybiwch fod gennym weithdrefn draw-line sy’n llunio llinell ar y sgrin rhwng dau bwynt penodedig. Yna gallwn greu peintwyr ar gyfer lluniadau llinell, megis y peintiwr wave yn Ffigur 2.10, o restrau o segmentau llinell fel a ganlyn:⁹³

(define (segments->painter segment-list)
  (lambda (frame)
    (for-each
     (lambda (segment)
       (draw-line
        ((frame-coord-map frame) 
         (start-segment segment))
        ((frame-coord-map frame) 
         (end-segment segment))))
     segment-list)))

Rhoddir y segmentau drwy ddefnyddio cyfesurynnau mewn perthynas â’r sgwâr uned. Ar gyfer pob segment yn y rhestr, mae’r peintiwr yn trawsffurfio pwyntiau terfyn y segment â mapiad cyfesurynnau’r ffrâm ac yn llunio llinell rhwng y pwyntiau a drawsffurfiwyd.

Mae cynrychioli peintwyr fel gweithdrefnau yn codi rhwystr haniaethu grymus yn yr iaith darluniau. Gallwn greu a chymysgu pob math o beintwyr cyntefig, wedi’u seilio ar amrywiaeth o alluoedd graffeg. Nid yw manylion eu gweithrediad yn bwysig. Gall unrhyw weithdrefn wasanaethu fel peintiwr, ar yr amod ei bod yn cymryd ffrâm fel arg ac yn llunio rhywbeth wedi’i raddio i ffitio’r ffrâm.⁹⁴

Ymarfer 2.48: Gellir cynrychioli segment llinell cyfeiriedig yn y plân fel pâr o fectorau—y fector sy’n mynd o’r tarddbwynt at bwynt dechrau’r segment, a’r fector sy’n mynd o’r tarddbwynt at bwynt gorffen y segment. Defnyddiwch eich cynrychioliad fectorau o Ymarfer 2.46 i ddiffinio cynrychioliad ar gyfer segmentau ag adeiladydd make-segment a detholwyr start-segment ac end-segment.

Ymarfer 2.49: Defnyddiwch segments->painter i ddiffinio’r peintwyr cyntefig canlynol:

1. Y peintiwr sy’n llunio amlinell y ffrâm benodedig.
2. Y peintiwr sy’n llunio “X” drwy gysylltu corneli cyferbyn y ffrâm.
3. Y peintiwr sy’n llunio siâp diemwnt drwy gysylltu canolbwyntiau ochrau’r ffrâm.
4. Y peintiwr wave.

Trawsffurfio a chyfuno peintwyr

Mae gweithrediad ar beintwyr (megis flip-vert neu beside) yn gweithio drwy greu peintiwr sy’n galw’r peintwyr gwreiddiol mewn perthynas â fframiau a ddeillir o’r ffrâm arg. Felly, er enghraifft, nid oes rhaid i flip-vert wybod sut mae peintiwr yn gweithio er mwyn ei droi wyneb i waered—dim ond gwybod sut i droi ffrâm wyneb i waered sydd ei angen: Mae’r peintiwr a drowyd yn defnyddio’r peintiwr gwreiddiol, ond yn y ffrâm wrthdro.

Mae gweithrediadau peintwyr wedi’u seilio ar y weithdrefn transform-painter, sy’n cymryd peintiwr a gwybodaeth am sut i drawsffurfio ffrâm fel argiau ac yn cynhyrchu peintiwr newydd. Pan elwir y peintiwr a drawsffurfiwyd ar ffrâm, mae’n trawsffurfio’r ffrâm ac yn galw’r peintiwr gwreiddiol ar y ffrâm a drawsffurfiwyd. Pwyntiau (wedi’u cynrychioli fel fectorau) yw’r argiau i transform-painter, ac maent yn pennu corneli’r ffrâm newydd: Pan gânt eu mapio i’r ffrâm, mae’r pwynt cyntaf yn pennu tarddbwynt y ffrâm newydd ac mae’r ddau arall yn pennu pennau ei fectorau ymyl. Felly, mae argiau o fewn y sgwâr uned yn pennu ffrâm sydd o fewn y ffrâm wreiddiol.

(define (transform-painter 
         painter origin corner1 corner2)
  (lambda (frame)
    (let ((m (frame-coord-map frame)))
      (let ((new-origin (m origin)))
        (painter (make-frame new-origin
                  (sub-vect (m corner1) 
                            new-origin)
                  (sub-vect (m corner2)
                            new-origin)))))))

Dyma sut i droi delweddau peintwyr wyneb i waered yn fertigol:

(define (flip-vert painter)
  (transform-painter 
   painter
   (make-vect 0.0 1.0)   ; new origin
   (make-vect 1.0 1.0)   ; new end of edge1
   (make-vect 0.0 0.0))) ; new end of edge2

Drwy ddefnyddio transform-painter, gallwn ddiffinio trawsffurfiadau newydd yn hawdd. Er enghraifft, gallwn ddiffinio peintiwr sy’n crebachu ei ddelwedd i chwarter dde uchaf y ffrâm a roddir iddo:

(define (shrink-to-upper-right painter)
  (transform-painter painter
                     (make-vect 0.5 0.5)
                     (make-vect 1.0 0.5)
                     (make-vect 0.5 1.0)))

Mae trawsffurfiadau eraill yn cylchdroi delweddau 90 gradd yn wrthglocwedd⁹⁵

(define (rotate90 painter)
  (transform-painter painter
                     (make-vect 1.0 0.0)
                     (make-vect 1.0 1.0)
                     (make-vect 0.0 0.0)))

neu’n gwasgu delweddau tuag at ganol y ffrâm:⁹⁶

(define (squash-inwards painter)
  (transform-painter painter
                     (make-vect 0.0 0.0)
                     (make-vect 0.65 0.35)
                     (make-vect 0.35 0.65)))

Trawsffurfio fframiau hefyd yw’r allwedd i ddiffinio moddion cyfuno dau beintiwr neu fwy. Mae’r weithdrefn beside, er enghraifft, yn cymryd dau beintiwr, yn eu trawsffurfio i beintio yn haneri chwith a dde ffrâm arg, yn y drefn honno, ac yn cynhyrchu peintiwr cyfansawdd newydd. Pan roddir ffrâm i’r peintiwr cyfansawdd, mae’n galw’r peintiwr trawsffurfiedig cyntaf i beintio yn hanner chwith y ffrâm ac yn galw’r ail beintiwr trawsffurfiedig i beintio yn hanner dde’r ffrâm:

(define (beside painter1 painter2)
  (let ((split-point (make-vect 0.5 0.0)))
    (let ((paint-left  (transform-painter 
                        painter1
                        (make-vect 0.0 0.0)
                        split-point
                        (make-vect 0.0 1.0)))
          (paint-right (transform-painter
                        painter2
                        split-point
                        (make-vect 1.0 0.0)
                        (make-vect 0.5 1.0))))
      (lambda (frame)
        (paint-left frame)
        (paint-right frame)))))

Sylwch sut mae haniaeth data’r peintwyr, ac yn benodol gynrychioli peintwyr fel gweithdrefnau, yn gwneud beside yn hawdd ei gweithredu. Nid oes angen i’r weithdrefn beside wybod dim am fanylion y peintwyr cyfansoddol heblaw y bydd pob peintiwr yn llunio rhywbeth yn ei ffrâm benodedig.

Ymarfer 2.50: Diffiniwch y trawsffurfiad flip-horiz, sy’n gwrthdroi peintwyr yn llorweddol, a thrawsffurfiadau sy’n cylchdroi peintwyr 180 gradd a 270 gradd yn wrthglocwedd.

Ymarfer 2.51: Diffiniwch y gweithrediad below ar gyfer peintwyr. Mae Below yn cymryd dau beintiwr fel argiau. O gael ffrâm, mae’r peintiwr canlyniadol yn llunio â’r peintiwr cyntaf yng ngwaelod y ffrâm ac â’r ail beintiwr yn y brig. Diffiniwch below mewn dwy ffordd wahanol—yn gyntaf drwy ysgrifennu gweithdrefn sy’n cyfateb i’r weithdrefn beside a roddwyd uchod, ac eto yn nhermau beside a gweithrediadau cylchdroi addas (o Ymarfer 2.50).

Lefelau iaith ar gyfer dylunio cadarn

Mae’r iaith darluniau yn rhoi ar waith rai o’r syniadau allweddol a gyflwynasom am haniaethu â gweithdrefnau a data. Gweithredir yr haniaethau data sylfaenol, y peintwyr, drwy ddefnyddio cynrychioliadau gweithdrefnol, sy’n galluogi’r iaith i drin gwahanol alluoedd lluniadu sylfaenol mewn ffordd unffurf. Mae’r moddion cyfuno yn bodloni’r briodwedd cau, sy’n caniatáu inni adeiladu dyluniadau cymhleth yn hawdd. Yn olaf, mae’r holl offer ar gyfer haniaethu gweithdrefnau ar gael inni ar gyfer haniaethu moddion cyfuno peintwyr.

Rydym hefyd wedi cael cipolwg ar syniad hanfodol arall am ieithoedd a dylunio rhaglenni. Dyma’r dull o ddylunio haenedig, sef y syniad y dylid strwythuro system gymhleth fel dilyniant o lefelau a ddisgrifir drwy ddefnyddio dilyniant o ieithoedd. Adeiladir pob lefel drwy gyfuno rhannau a ystyrir yn gyntefig ar y lefel honno, a defnyddir y rhannau a adeiladir ar bob lefel fel elfennau cyntefig ar y lefel nesaf. Mae gan yr iaith a ddefnyddir ar bob lefel o ddyluniad haenedig elfennau cyntefig, moddion cyfuno, a moddion haniaethu sy’n briodol i’r lefel honno o fanylder.

Mae dylunio haenedig yn treiddio drwy beirianneg systemau cymhleth. Er enghraifft, mewn peirianneg gyfrifiadurol, cyfunir gwrthyddion a thransistorau (a’u disgrifio drwy ddefnyddio iaith cylchedau analog) i gynhyrchu rhannau megis adwyon AC ac adwyon NEU, sy’n ffurfio elfennau cyntefig iaith ar gyfer dylunio cylchedau digidol.⁹⁷ Cyfunir y rhannau hyn i adeiladu prosesyddion, strwythurau bysiau, a systemau cof, a gyfunir yn eu tro i ffurfio cyfrifiaduron, drwy ddefnyddio ieithoedd sy’n briodol i bensaernïaeth gyfrifiadurol. Cyfunir cyfrifiaduron i ffurfio systemau dosbarthedig, drwy ddefnyddio ieithoedd sy’n briodol i ddisgrifio rhyng-gysylltiadau rhwydweithiau, ac yn y blaen.

Fel enghraifft fach o haenu, mae ein hiaith darluniau yn defnyddio elfennau cyntefig (peintwyr cyntefig) a grëir drwy ddefnyddio iaith sy’n pennu pwyntiau a llinellau i ddarparu’r rhestrau o segmentau llinell ar gyfer segments->painter, neu’r manylion cysgodi ar gyfer peintiwr fel rogers. Canolbwyntiodd y rhan fwyaf o’n disgrifiad o’r iaith darluniau ar gyfuno’r elfennau cyntefig hyn, drwy ddefnyddio cyfunwyr geometrig megis beside ac below. Buom hefyd yn gweithio ar lefel uwch, gan ystyried beside ac below yn elfennau cyntefig i’w trin mewn iaith y mae ei gweithrediadau, megis square-of-four, yn dal patrymau cyffredin o gyfuno cyfunwyr geometrig.

Mae dylunio haenedig yn helpu i wneud rhaglenni’n gadarn, hynny yw, mae’n ei gwneud yn debygol y bydd newidiadau bach mewn manyleb yn gofyn am newidiadau cyfatebol fach yn y rhaglen. Er enghraifft, tybiwch ein bod eisiau newid y ddelwedd sy’n seiliedig ar wave a ddangosir yn Ffigur 2.9. Gallem weithio ar y lefel isaf i newid golwg fanwl yr elfen wave; gallem weithio ar y lefel ganol i newid y ffordd y mae corner-split yn ailadrodd yr wave; gallem weithio ar y lefel uchaf i newid sut mae square-limit yn trefnu pedwar copi’r gornel. Yn gyffredinol, mae pob lefel o ddyluniad haenedig yn darparu geirfa wahanol ar gyfer mynegi nodweddion y system, a math gwahanol o allu i’w newid.

Ymarfer 2.52: Gwnewch newidiadau i derfyn sgwâr wave a ddangosir yn Ffigur 2.9 drwy weithio ar bob un o’r lefelau a ddisgrifiwyd uchod. Yn benodol:

1. Ychwanegwch rai segmentau at beintiwr cyntefig wave Ymarfer 2.49 (i ychwanegu gwên, er enghraifft).
2. Newidiwch y patrwm a adeiladir gan corner-split (er enghraifft, drwy ddefnyddio dim ond un copi o’r delweddau up-split ac right-split yn lle dau).
3. Addaswch y fersiwn o square-limit sy’n defnyddio square-of-four er mwyn cydosod y corneli mewn patrwm gwahanol. (Er enghraifft, gallech wneud i’r Mr. Rogers mawr edrych allan o bob cornel o’r sgwâr.)

(cadr ⟨arg⟩) = (car (cdr ⟨arg⟩))

(define f (lambda (x y . z) ⟨body⟩))
(define g (lambda w ⟨body⟩))

(map + 
     (list 1 2 3) 
     (list 40 50 60) 
     (list 700 800 900))
(741 852 963)

(map (lambda (x y) (+ x (* 2 y)))
     (list 1 2 3)
     (list 4 5 6))
(9 12 15)

(define flipped-pairs
  (square-of-four 
   identity flip-vert identity flip-vert))