3.5 Ffrydiau

Rydym wedi ennill dealltwriaeth dda o aseiniad fel offeryn modelu, yn ogystal â gwerthfawrogiad o'r problemau cymhleth y mae aseiniad yn eu codi. Mae'n bryd gofyn a allem fod wedi mynd ati mewn ffordd wahanol, er mwyn osgoi rhai o'r problemau hyn. Yn yr adran hon, archwiliwn ddull amgen o fodelu cyflwr, yn seiliedig ar strwythurau data a elwir yn ffrydiau. Fel y gwelwn, gall ffrydiau leihau rhywfaint o gymhlethdod modelu cyflwr.

Gadewch inni gamu'n ôl ac adolygu tarddiad y cymhlethdod hwn. Wrth geisio modelu ffenomenau'r byd go iawn, gwnaethom rai penderfyniadau a oedd yn ymddangos yn rhesymol: Modelasom wrthrychau'r byd go iawn â chyflwr lleol drwy wrthrychau cyfrifiadurol â newidynnau lleol. Uniaethasom amrywiad dros amser yn y byd go iawn ag amrywiad dros amser yn y cyfrifiadur. Gweithredasom amrywiad dros amser cyflyrau'r gwrthrychau model yn y cyfrifiadur drwy aseiniadau i newidynnau lleol y gwrthrychau model.

A oes dull arall? A allwn osgoi uniaethu amser yn y cyfrifiadur ag amser yn y byd a fodelir? A oes rhaid inni wneud i'r model newid dros amser er mwyn modelu ffenomenau mewn byd sy'n newid? Meddyliwch am y mater yn nhermau ffwythiannau mathemategol. Gallwn ddisgrifio ymddygiad maint $x$ sy'n amrywio dros amser yn ffwythiant amser $x(t)$. Os canolbwyntiwn ar $x$ amrantiad wrth amrantiad, meddyliwn amdano'n faint sy'n newid. Eto os canolbwyntiwn ar holl hanes amser y gwerthoedd, nid ydym yn pwysleisio newid—nid yw'r ffwythiant ei hun yn newid.¹⁸⁰

Os mesurir amser mewn camau arwahanol, yna gallwn fodelu ffwythiant amser yn ddilyniant (a all fod yn anfeidrol). Yn yr adran hon, gwelwn sut i fodelu newid yn nhermau dilyniannau sy'n cynrychioli hanesion amser y systemau a fodelir. I gyflawni hyn, cyflwynwn strwythurau data newydd o'r enw ffrydiau. O safbwynt haniaethol, dim ond dilyniant yw ffrwd. Fodd bynnag, canfyddwn nad yw gweithredu ffrydiau'n uniongyrchol fel rhestrau (fel yn 2.2.1) yn datgelu grym prosesu ffrydiau'n llawn. Yn ddewis amgen, cyflwynwn dechneg gwerthuso gohiriedig, sy'n ein galluogi i gynrychioli dilyniannau mawr iawn (hyd yn oed rhai anfeidrol) yn ffrydiau.

Mae prosesu ffrydiau yn caniatáu inni fodelu systemau sydd â chyflwr heb ddefnyddio aseiniad na data newidiadwy byth. Mae gan hyn oblygiadau pwysig, yn ddamcaniaethol ac yn ymarferol, am y gallwn adeiladu modelau sy'n osgoi'r anfanteision sy'n gynhenid wrth gyflwyno aseiniad. Ar y llaw arall, mae'r fframwaith ffrydiau yn codi anawsterau ei hun, ac mae'r cwestiwn pa dechneg fodelu sy'n arwain at systemau mwy modiwlaidd a haws eu cynnal yn dal heb ei ateb.

3.5.1Rhestrau Gohiriedig yw Ffrydiau

Fel y gwelsom yn 2.2.3, gall dilyniannau wasanaethu'n rhyngwynebau safonol ar gyfer cyfuno modiwlau rhaglenni. Lluniasom haniaethau pwerus ar gyfer trin dilyniannau, megis map, filter, ac accumulate, sy'n mynegi amrywiaeth eang o weithrediadau mewn ffordd gryno a chain.

Yn anffodus, os cynrychiolwn ddilyniannau'n rhestrau, telir am y ceinder hwn drwy aneffeithlonrwydd difrifol o ran yr amser a'r gofod sydd eu hangen ar ein cyfrifiadau. Pan gynrychiolwn driniaethau ar ddilyniannau yn drawsffurfiadau o restrau, rhaid i'n rhaglenni adeiladu a chopïo strwythurau data (a all fod yn enfawr) ar bob cam o broses.

I weld pam mae hyn yn wir, gadewch inni gymharu dwy raglen ar gyfer cyfrifo swm yr holl rifau cysefin mewn cyfwng. Ysgrifennir y rhaglen gyntaf mewn arddull iteru safonol:¹⁸¹

(define (sum-primes a b)
  (define (iter count accum)
    (cond ((> count b) accum)
          ((prime? count)
           (iter (+ count 1)
                 (+ count accum)))
          (else (iter (+ count 1) accum))))
  (iter a 0))

Mae'r ail raglen yn cyflawni'r un cyfrifiad gan ddefnyddio gweithrediadau dilyniant 2.2.3:

(define (sum-primes a b)
  (accumulate 
   +
   0
   (filter prime? (enumerate-interval a b))))

Wrth gyflawni'r cyfrifiad, dim ond y swm sy'n cronni y mae angen i'r rhaglen gyntaf ei storio. Mewn cyferbyniad, ni all yr hidlydd yn yr ail raglen wneud unrhyw brofi nes bod enumerate-interval wedi adeiladu rhestr gyflawn o'r rhifau yn y cyfwng. Mae'r hidlydd yn cynhyrchu rhestr arall, a basir yn ei thro i accumulate cyn ei chywasgu i ffurfio swm. Nid oes angen storfa ganolradd mor fawr ar y rhaglen gyntaf, y gallwn feddwl amdani fel un sy'n rhifo'r cyfwng yn raddol, gan ychwanegu pob rhif cysefin at y swm wrth iddo gael ei gynhyrchu.

Daw aneffeithlonrwydd defnyddio rhestrau'n boenus o amlwg os defnyddiwn y paradeim dilyniannau i gyfrifo'r ail rif cysefin yn y cyfwng o 10,000 i 1,000,000 drwy werthuso'r mynegiad

(car (cdr 
      (filter 
       prime?
       (enumerate-interval 10000 1000000))))

Mae'r mynegiad hwn yn canfod yr ail rif cysefin, ond mae'r gorbenion cyfrifiadurol yn warthus. Adeiladwn restr o bron i filiwn o gyfanrifau, hidlwn y rhestr hon drwy brofi a yw pob elfen yn gysefin, ac yna anwybyddwn bron y cyfan o'r canlyniad. Mewn arddull raglennu fwy traddodiadol, byddem yn cydblethu'r rhifo a'r hidlo, ac yn stopio ar ôl cyrraedd yr ail rif cysefin.

Syniad clyfar yw ffrydiau sy'n caniatáu defnyddio triniaethau dilyniant heb fynd i gostau trin dilyniannau'n rhestrau. Gyda ffrydiau gallwn gael y gorau o ddau fyd: Gallwn lunio rhaglenni'n gain fel triniaethau dilyniant, gan gyflawni effeithlonrwydd cyfrifiannu graddol ar yr un pryd. Y syniad sylfaenol yw trefnu adeiladu ffrwd yn rhannol yn unig, a phasio'r adeiladwaith rhannol i'r rhaglen sy'n defnyddio'r ffrwd. Os yw'r defnyddiwr hwnnw'n ceisio cyrchu rhan o'r ffrwd nad yw wedi'i hadeiladu eto, bydd y ffrwd yn adeiladu'n awtomatig ddigon yn rhagor ohoni'i hun i gynhyrchu'r rhan sydd ei hangen, gan gynnal y rhith bod y ffrwd gyfan yn bodoli. Mewn geiriau eraill, er y byddwn yn ysgrifennu rhaglenni fel pe baem yn prosesu dilyniannau cyflawn, dyluniwn ein gweithrediad o ffrydiau i gydblethu adeiladu'r ffrwd â'i defnyddio'n awtomatig ac yn dryloyw.

Ar yr wyneb, dim ond rhestrau yw ffrydiau, ag enwau gwahanol i'r gweithdrefnau sy'n eu trin. Ceir adeiladydd, cons-stream, a dau ddetholwr, stream-car ac stream-cdr, sy'n bodloni'r cyfyngiadau

(stream-car (cons-stream x y)) = x
(stream-cdr (cons-stream x y)) = y

Ceir gwrthrych y gellir ei wahaniaethu, the-empty-stream, na all fod yn ganlyniad unrhyw weithrediad cons-stream, ac y gellir ei adnabod â'r traethiad stream-null?.¹⁸² Felly gallwn greu a defnyddio ffrydiau, yn union fel y gallwn greu a defnyddio rhestrau, i gynrychioli data cyfun wedi'i drefnu'n ddilyniant. Yn benodol, gallwn adeiladu fersiynau ffrydiau o weithrediadau rhestrau Pennod 2, megis list-ref, map, ac for-each:¹⁸³

(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(define (stream-map proc s)
  (if (stream-null? s)
      the-empty-stream
      (cons-stream 
       (proc (stream-car s))
       (stream-map proc (stream-cdr s)))))

(define (stream-for-each proc s)
  (if (stream-null? s)
      'done
      (begin 
        (proc (stream-car s))
        (stream-for-each proc 
                         (stream-cdr s)))))

Mae Stream-for-each yn ddefnyddiol ar gyfer gweld ffrydiau:

(define (display-stream s)
  (stream-for-each display-line s))

(define (display-line x)
  (newline)
  (display x))

I wneud i'r gweithrediad o ffrydiau gydblethu adeiladu ffrwd â'i defnyddio'n awtomatig ac yn dryloyw, byddwn yn trefnu bod cdr ffrwd yn cael ei werthuso pan gaiff ei gyrchu gan y weithdrefn stream-cdr yn hytrach na phan adeiledir y ffrwd gan cons-stream. Mae'r dewis gweithredu hwn yn atgoffa rhywun o'n trafodaeth ar rifau cymarebol yn 2.1.2, lle gwelsom y gallwn ddewis gweithredu rhifau cymarebol fel bod gostwng y rhifiadur a'r enwadur i'w termau isaf yn digwydd naill ai adeg adeiladu neu adeg dethol. Mae'r ddau weithrediad o rifau cymarebol yn cynhyrchu'r un haniaeth data, ond mae'r dewis yn effeithio ar effeithlonrwydd. Mae perthynas debyg rhwng ffrydiau a rhestrau cyffredin. Fel haniaeth data, mae ffrydiau'r un fath â rhestrau. Y gwahaniaeth yw'r amser y gwerthusir yr elfennau. Gyda rhestrau cyffredin, gwerthusir yr car a'r cdr ill dau adeg adeiladu. Gyda ffrydiau, gwerthusir yr cdr adeg dethol.

Bydd ein gweithrediad o ffrydiau yn seiliedig ar ffurf arbennig o'r enw delay. Nid yw gwerthuso (delay ⟨exp⟩) yn gwerthuso'r mynegiad ⟨exp⟩, ond yn hytrach yn dychwelyd yr hyn a elwir yn wrthrych gohiriedig, y gallwn feddwl amdano'n “addewid” i werthuso ⟨exp⟩ ar ryw adeg yn y dyfodol. Yn gydymaith i delay, ceir gweithdrefn o'r enw force sy'n cymryd gwrthrych gohiriedig yn arg ac yn cyflawni'r gwerthuso—gan orfodi delay, i bob pwrpas, i gyflawni ei addewid. Gwelwn isod sut y gellir gweithredu delay ac force, ond yn gyntaf gadewch inni ddefnyddio'r rhain i adeiladu ffrydiau.

Ffurf arbennig yw Cons-stream a ddiffinnir fel bod

(cons-stream ⟨a⟩ ⟨b⟩)

yn gyfwerth â

(cons ⟨a⟩ (delay ⟨b⟩))

Ystyr hyn yw y byddwn yn adeiladu ffrydiau gan ddefnyddio parau. Fodd bynnag, yn hytrach na rhoi gwerth gweddill y ffrwd yn cdr y pâr, rhown yno addewid i gyfrifo'r gweddill os gofynnir amdano byth. Bellach gellir diffinio Stream-car ac stream-cdr yn weithdrefnau:

(define (stream-car stream) 
  (car stream))

(define (stream-cdr stream) 
  (force (cdr stream)))

Mae Stream-car yn dethol car y pâr; mae stream-cdr yn dethol cdr y pâr ac yn gwerthuso'r mynegiad gohiriedig a geir yno i gael gweddill y ffrwd.¹⁸⁴

Y gweithrediad o ffrydiau ar waith

I weld sut mae'r gweithrediad hwn yn ymddwyn, gadewch inni ddadansoddi'r cyfrifiad rhifau cysefin “gwarthus” a welsom uchod, wedi'i ail-lunio yn nhermau ffrydiau:

(stream-car 
 (stream-cdr
  (stream-filter 
   prime? (stream-enumerate-interval 
           10000 1000000))))

Gwelwn ei fod yn gweithio'n effeithlon yn wir.

Dechreuwn drwy alw stream-enumerate-interval â'r argiau 10,000 ac 1,000,000. Stream-enumerate-interval yw'r fersiwn ffrydiau o enumerate-interval (2.2.3):

(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1)
                                  high))))

ac felly'r canlyniad a ddychwelir gan stream-enumerate-interval, a ffurfir gan cons-stream, yw¹⁸⁵

(cons 10000
      (delay 
        (stream-enumerate-interval 
         10001 
         1000000)))

Hynny yw, mae stream-enumerate-interval yn dychwelyd ffrwd a gynrychiolir yn bâr y mae ei car yn 10,000 a'i cdr yn addewid i rifo mwy o'r cyfwng os gofynnir am hynny. Hidlir y ffrwd hon bellach i gael rhifau cysefin, gan ddefnyddio'r fersiwn ffrydiau o'r weithdrefn filter (2.2.3):

(define (stream-filter pred stream)
  (cond ((stream-null? stream) 
         the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream 
          (stream-car stream)
          (stream-filter 
           pred
           (stream-cdr stream))))
        (else (stream-filter 
               pred 
               (stream-cdr stream)))))

Mae Stream-filter yn profi stream-car y ffrwd (car y pâr, sef 10,000). Gan nad yw hwn yn gysefin, mae stream-filter yn archwilio stream-cdr ei ffrwd fewnbwn. Mae'r alwad i stream-cdr yn gorfodi gwerthuso'r stream-enumerate-interval gohiriedig, sydd bellach yn dychwelyd

(cons 10001
      (delay 
        (stream-enumerate-interval 
         10002 
         1000000)))

Mae Stream-filter bellach yn edrych ar stream-car y ffrwd hon, 10,001, yn gweld nad yw hwn yn gysefin chwaith, yn gorfodi stream-cdr arall, ac yn y blaen, nes bod stream-enumerate-interval yn rhoi'r rhif cysefin 10,007, ac yna mae stream-filter, yn ôl ei ddiffiniad, yn dychwelyd

(cons-stream 
 (stream-car stream)
 (stream-filter pred (stream-cdr stream)))

sef, yn yr achos hwn,

(cons 10007
      (delay
        (stream-filter
         prime?
         (cons 10008
               (delay
                 (stream-enumerate-interval 
                  10009 1000000))))))

Pasir y canlyniad hwn bellach i stream-cdr yn ein mynegiad gwreiddiol. Mae hyn yn gorfodi'r stream-filter gohiriedig, sydd yn ei dro'n parhau i orfodi'r stream-enumerate-interval gohiriedig nes iddo ganfod y rhif cysefin nesaf, sef 10,009. Yn olaf, y canlyniad a basir i stream-car yn ein mynegiad gwreiddiol yw

(cons 10009
      (delay
        (stream-filter
         prime?
         (cons 10010
               (delay
                 (stream-enumerate-interval 
                  10011 1000000))))))

Mae Stream-car yn dychwelyd 10,009, ac mae'r cyfrifiad wedi'i gwblhau. Dim ond cynifer o gyfanrifau ag oedd eu hangen i ganfod yr ail rif cysefin a brofwyd am fod yn gysefin, a dim ond cyn belled ag oedd ei angen i fwydo'r hidlydd rhifau cysefin y rhifwyd y cyfwng.

Yn gyffredinol, gallwn feddwl am werthuso gohiriedig fel rhaglennu “a yrrir gan alw,” lle gweithredir pob cam ym mhroses y ffrwd yn ddigon yn unig i fodloni'r cam nesaf. Yr hyn yr ydym wedi'i wneud yw datgysylltu gwir drefn digwyddiadau yn y cyfrifiad oddi wrth strwythur ymddangosiadol ein gweithdrefnau. Ysgrifennwn weithdrefnau fel pe bai'r ffrydiau'n bodoli “i gyd ar unwaith” pan, mewn gwirionedd, cyflawnir y cyfrifiad yn raddol, fel mewn arddulliau rhaglennu traddodiadol.

Gweithredu delay ac force

Er y gall delay ac force ymddangos yn weithrediadau dirgel, mae eu gweithredu yn eithaf syml mewn gwirionedd. Rhaid i Delay becynnu mynegiad fel y gellir ei werthuso'n ddiweddarach pan fo galw amdano, a gallwn gyflawni hyn yn syml drwy drin y mynegiad fel corff gweithdrefn. Gall Delay fod yn ffurf arbennig fel bod

(delay ⟨exp⟩)

yn siwgr cystrawennol ar gyfer

(lambda () ⟨exp⟩)

Dim ond galw'r weithdrefn (heb argiau) a gynhyrchir gan delay a wna Force, felly gallwn weithredu force fel gweithdrefn:

(define (force delayed-object)
  (delayed-object))

Mae'r gweithrediad hwn yn ddigon i delay ac force weithio fel yr addawyd, ond mae optimeiddiad pwysig y gallwn ei gynnwys. Mewn llawer o gymwysiadau, byddwn yn gorfodi'r un gwrthrych gohiriedig lawer gwaith yn y pen draw. Gall hyn arwain at aneffeithlonrwydd difrifol mewn rhaglenni dychweliadol sy'n cynnwys ffrydiau. (Gweler Ymarfer 3.57.) Yr ateb yw adeiladu gwrthrychau gohiriedig fel eu bod, y tro cyntaf y'u gorfodir, yn storio'r gwerth a gyfrifir. Bydd gorfodi wedyn yn dychwelyd y gwerth a storiwyd yn unig, heb ailadrodd y cyfrifiad. Mewn geiriau eraill, gweithredwn delay fel gweithdrefn at ddiben arbennig sy'n cofio canlyniadau, yn debyg i'r un a ddisgrifir yn Ymarfer 3.27. Un ffordd o gyflawni hyn yw defnyddio'r weithdrefn ganlynol, sy'n cymryd gweithdrefn (heb argiau) yn arg ac yn dychwelyd fersiwn o'r weithdrefn sy'n cofio canlyniadau. Y tro cyntaf y rhedir y weithdrefn sy'n cofio canlyniadau, mae'n cadw'r canlyniad a gyfrifwyd. Wrth werthuso wedi hynny, dim ond dychwelyd y canlyniad a wna.

(define (memo-proc proc)
  (let ((already-run? false) (result false))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? true)
                 result)
          result))))

Yna diffinnir Delay fel bod (delay ⟨exp⟩) yn gyfwerth â

(memo-proc (lambda () ⟨exp⟩))

ac mae force fel y'i diffiniwyd o'r blaen.¹⁸⁶

Ymarfer 3.50: Cwblhewch y diffiniad canlynol, sy'n cyffredinoli stream-map i ganiatáu gweithdrefnau sy'n cymryd sawl arg, yn gyfatebol i map yn 2.2.1, Troednodyn 78.

(define (stream-map proc . argstreams)
  (if (⟨??⟩ (car argstreams))
      the-empty-stream
      (⟨??⟩
       (apply proc (map ⟨??⟩ argstreams))
       (apply stream-map
              (cons proc 
                    (map ⟨??⟩ 
                         argstreams))))))

Ymarfer 3.51: Er mwyn edrych yn agosach ar werthuso gohiriedig, defnyddiwn y weithdrefn ganlynol, sydd yn syml yn dychwelyd ei harg ar ôl ei argraffu:

(define (show x)
  (display-line x)
  x)

Beth mae'r dehonglydd yn ei argraffu mewn ymateb i werthuso pob mynegiad yn y dilyniant canlynol?¹⁸⁷

(define x 
  (stream-map 
   show 
   (stream-enumerate-interval 0 10)))

(stream-ref x 5)
(stream-ref x 7)

Ymarfer 3.52: Ystyriwch y dilyniant o fynegiadau

(define sum 0)

(define (accum x)
  (set! sum (+ x sum))
  sum)

(define seq 
  (stream-map 
   accum 
   (stream-enumerate-interval 1 20)))

(define y (stream-filter even? seq))

(define z 
  (stream-filter 
   (lambda (x) 
     (= (remainder x 5) 0)) seq))

(stream-ref y 7)
(display-stream z)

Beth yw gwerth sum ar ôl gwerthuso pob un o'r mynegiadau uchod? Beth yw'r ymateb argraffedig i werthuso'r mynegiadau stream-ref ac display-stream? A fyddai'r ymatebion hyn yn wahanol pe baem wedi gweithredu (delay ⟨exp⟩) yn syml fel (lambda () ⟨exp⟩) heb ddefnyddio'r optimeiddiad a ddarperir gan memo-proc? Esboniwch.

3.5.2Ffrydiau Anfeidrol

Rydym wedi gweld sut i gynnal y rhith o drin ffrydiau'n endidau cyflawn er ein bod, mewn gwirionedd, yn cyfrifo dim ond cymaint o'r ffrwd ag y mae angen inni ei gyrchu. Gallwn ddefnyddio'r dechneg hon i gynrychioli dilyniannau'n effeithlon fel ffrydiau, hyd yn oed os yw'r dilyniannau'n hir iawn. Yn fwy trawiadol fyth, gallwn ddefnyddio ffrydiau i gynrychioli dilyniannau sy'n anfeidrol hir. Er enghraifft, ystyriwch y diffiniad canlynol o ffrwd y cyfanrifau positif:

(define (integers-starting-from n)
  (cons-stream 
   n (integers-starting-from (+ n 1))))
(define integers (integers-starting-from 1))

Mae hyn yn gwneud synnwyr am y bydd integers yn bâr y mae ei car yn 1 a'i cdr yn addewid i gynhyrchu'r cyfanrifau sy'n dechrau â 2. Ffrwd anfeidrol hir yw hon, ond mewn unrhyw amser penodol dim ond rhan feidraidd ohoni y gallwn ei harchwilio. Felly, ni fydd ein rhaglenni byth yn gwybod nad yw'r ffrwd anfeidrol gyfan yno.

Gan ddefnyddio integers gallwn ddiffinio ffrydiau anfeidrol eraill, megis ffrwd y cyfanrifau nad ydynt yn rhanadwy â 7:

(define (divisible? x y) (= (remainder x y) 0))
(define no-sevens
  (stream-filter (lambda (x) 
                   (not (divisible? x 7)))
                 integers))

Yna gallwn ganfod cyfanrifau nad ydynt yn rhanadwy â 7 drwy gyrchu elfennau'r ffrwd hon yn unig:

(stream-ref no-sevens 100)
117

Yn gyfatebol i integers, gallwn ddiffinio ffrwd anfeidrol rhifau Fibonacci:

(define (fibgen a b)
  (cons-stream a (fibgen b (+ a b))))
(define fibs (fibgen 0 1))

Mae Fibs yn bâr y mae ei car yn 0 a'i cdr yn addewid i werthuso (fibgen 1 1). Pan werthuswn yr (fibgen 1 1) gohiriedig hwn, bydd yn cynhyrchu pâr y mae ei car yn 1 a'i cdr yn addewid i werthuso (fibgen 1 2), ac yn y blaen.

I weld ffrwd anfeidrol fwy cyffrous, gallwn gyffredinoli'r enghraifft no-sevens i adeiladu ffrwd anfeidrol rhifau cysefin, gan ddefnyddio dull a elwir yn ridyll Eratosthenes.¹⁸⁸ Dechreuwn â'r cyfanrifau sy'n dechrau â 2, sef y rhif cysefin cyntaf. I gael gweddill y rhifau cysefin, dechreuwn drwy hidlo lluosrifau 2 allan o weddill y cyfanrifau. Mae hyn yn gadael ffrwd sy'n dechrau â 3, sef y rhif cysefin nesaf. Nawr hidlwn luosrifau 3 allan o weddill y ffrwd hon. Mae hyn yn gadael ffrwd sy'n dechrau â 5, sef y rhif cysefin nesaf, ac yn y blaen. Mewn geiriau eraill, adeiladwn y rhifau cysefin drwy broses ridyllu, a ddisgrifir fel a ganlyn: I ridyllu ffrwd S, ffurfiwch ffrwd y mae ei helfen gyntaf yn elfen gyntaf S ac y ceir ei gweddill drwy hidlo holl luosrifau elfen gyntaf S allan o weddill S a ridyllu'r canlyniad. Mae'n hawdd disgrifio'r broses hon yn nhermau gweithrediadau ffrydiau:

(define (sieve stream)
  (cons-stream
   (stream-car stream)
   (sieve (stream-filter
           (lambda (x)
             (not (divisible? 
                   x (stream-car stream))))
           (stream-cdr stream)))))

(define primes 
  (sieve (integers-starting-from 2)))

Nawr, i ganfod rhif cysefin penodol, nid oes angen inni ond gofyn amdano:

(stream-ref primes 50)
233

Mae'n ddiddorol ystyried y system prosesu signalau a sefydlir gan sieve, a ddangosir yn y “diagram Henderson” yn Ffigur 3.31.¹⁸⁹ Mae'r ffrwd fewnbwn yn bwydo i mewn i flwch sy'n dadwneud cons sy'n gwahanu elfen gyntaf y ffrwd oddi wrth ei gweddill. Defnyddir yr elfen gyntaf i adeiladu hidlydd rhanadwyedd, y pasir y gweddill drwyddo, a bwydir allbwn yr hidlydd i flwch ridyll arall. Yna cymhwysir cons i osod yr elfen gyntaf wreiddiol ar flaen allbwn y ridyll mewnol i ffurfio'r ffrwd allbwn. Felly, nid yn unig y mae'r ffrwd yn anfeidrol, ond mae'r prosesydd signalau hefyd yn anfeidrol, am fod y ridyll yn cynnwys ridyll oddi mewn iddo.

Diffinio ffrydiau'n ymhlyg

Diffiniwyd y ffrydiau integers ac fibs uchod drwy bennu gweithdrefnau “cynhyrchu” sy'n cyfrifo elfennau'r ffrwd yn benodol fesul un. Ffordd arall o bennu ffrydiau yw manteisio ar werthuso gohiriedig i ddiffinio ffrydiau'n ymhlyg. Er enghraifft, mae'r mynegiad canlynol yn diffinio'r ffrwd ones yn ffrwd anfeidrol o unau:

(define ones (cons-stream 1 ones))

Mae hyn yn gweithio'n debyg iawn i ddiffiniad gweithdrefn ddychweliadol: Mae ones yn bâr y mae ei car yn 1 a'i cdr yn addewid i werthuso ones. Mae gwerthuso'r cdr yn rhoi 1 inni eto ac addewid i werthuso ones, ac yn y blaen.

Gallwn wneud pethau mwy diddorol drwy drin ffrydiau â gweithrediadau megis add-streams, sy'n cynhyrchu swm dwy ffrwd a roddwyd, elfen wrth elfen:¹⁹⁰

(define (add-streams s1 s2) 
  (stream-map + s1 s2))

Nawr gallwn ddiffinio'r cyfanrifau fel a ganlyn:

(define integers 
  (cons-stream 1 (add-streams ones integers)))

Mae hyn yn diffinio integers yn ffrwd y mae ei helfen gyntaf yn 1 a'i gweddill yn swm ones ac integers. Felly, ail elfen integers yw 1 ac elfen gyntaf integers, sef 2; trydedd elfen integers yw 1 ac ail elfen integers, sef 3; ac yn y blaen. Mae'r diffiniad hwn yn gweithio am fod digon o'r ffrwd integers wedi'i gynhyrchu ar unrhyw bwynt i allu ei fwydo'n ôl i'r diffiniad er mwyn cynhyrchu'r cyfanrif nesaf.

Gallwn ddiffinio rhifau Fibonacci yn yr un arddull:

(define fibs 
  (cons-stream 
   0 (cons-stream
      1 (add-streams 
         (stream-cdr fibs) fibs))))

Mae'r diffiniad hwn yn dweud bod fibs yn ffrwd sy'n dechrau â 0 ac 1, fel y gellir cynhyrchu gweddill y ffrwd drwy adio fibs ato'i hun wedi'i symud un lle:

    1 1 2 3 5  8 13 21 … = (stream-cdr fibs)
    0 1 1 2 3  5  8 13 … = fibs
0 1 1 2 3 5 8 13 21 34 … = fibs

Mae Scale-stream yn weithdrefn ddefnyddiol arall wrth lunio diffiniadau ffrydiau o'r fath. Mae hon yn lluosi pob eitem mewn ffrwd â chysonyn a roddwyd:

(define (scale-stream stream factor)
  (stream-map
   (lambda (x) (* x factor))
   stream))

Er enghraifft, mae

(define double 
  (cons-stream 1 (scale-stream double 2)))

yn cynhyrchu ffrwd pwerau 2: 1, 2, 4, 8, 16, 32, ….

Gellir rhoi diffiniad amgen o ffrwd y rhifau cysefin drwy ddechrau â'r cyfanrifau a'u hidlo drwy brofi a ydynt yn gysefin. Bydd angen y rhif cysefin cyntaf, 2, arnom i ddechrau:

(define primes
  (cons-stream
   2 (stream-filter 
      prime? (integers-starting-from 3))))

Nid yw'r diffiniad hwn mor syml ag y mae'n ymddangos, am y byddwn yn profi a yw rhif $n$ yn gysefin drwy wirio a yw $n$ yn rhanadwy â rhif cysefin (nid ag unrhyw gyfanrif yn unig) sy'n llai nag neu'n hafal i $\sqrt{n}$:

(define (prime? n)
  (define (iter ps)
    (cond ((> (square (stream-car ps)) n) true)
          ((divisible? n (stream-car ps)) false)
          (else (iter (stream-cdr ps)))))
  (iter primes))

Diffiniad dychweliadol yw hwn, gan y diffinnir primes yn nhermau'r traethiad prime?, sydd ei hun yn defnyddio'r ffrwd primes. Y rheswm pam mae'r weithdrefn hon yn gweithio yw bod digon o'r ffrwd primes wedi'i gynhyrchu ar unrhyw bwynt i brofi a yw'r rhifau y mae angen inni eu gwirio nesaf yn gysefin. Hynny yw, ar gyfer pob $n$ y profwn a yw'n gysefin, naill ai nid yw $n$ yn gysefin (ac yna mae rhif cysefin eisoes wedi'i gynhyrchu sy'n ei rannu) neu mae $n$ yn gysefin (ac yna mae rhif cysefin eisoes wedi'i gynhyrchu—h.y., rhif cysefin llai nag $n$—sy'n fwy nag $\sqrt{n}$).¹⁹¹

Ymarfer 3.53: Heb redeg y rhaglen, disgrifiwch elfennau'r ffrwd a ddiffinnir gan

(define s (cons-stream 1 (add-streams s s)))

Ymarfer 3.54: Diffiniwch weithdrefn mul-streams, yn gyfatebol i add-streams, sy'n cynhyrchu lluoswm ei dwy ffrwd fewnbwn elfen wrth elfen. Defnyddiwch hon ynghyd â ffrwd yr integers i gwblhau'r diffiniad canlynol o'r ffrwd y mae ei helfen rhif $n^{\text{fed}}$ (gan gyfrif o 0) yn ffactorial $n+1$:

(define factorials 
  (cons-stream 1 (mul-streams ⟨??⟩ ⟨??⟩)))

Ymarfer 3.55: Diffiniwch weithdrefn partial-sums sy'n cymryd ffrwd $S$ yn arg ac yn dychwelyd y ffrwd y mae ei helfennau'n $S_0$, $S_0+S_1$, $S_0+S_1+S_2,\dots <!--\; \dots \; -->$. Er enghraifft, dylai (partial-sums integers) fod yn ffrwd 1, 3, 6, 10, 15, ….

Ymarfer 3.56: Problem enwog, a godwyd gyntaf gan R. Hamming, yw rhifo, mewn trefn esgynnol heb ailadrodd, yr holl gyfanrifau positif nad oes ganddynt ffactorau cysefin heblaw 2, 3, neu 5. Un ffordd amlwg o wneud hyn yw profi pob cyfanrif yn ei dro i weld a oes ganddo unrhyw ffactorau heblaw 2, 3, a 5. Ond mae hyn yn aneffeithlon iawn, gan fod llai a llai o'r cyfanrifau'n bodloni'r gofyniad wrth iddynt fynd yn fwy. Yn ddewis amgen, gadewch inni alw'r ffrwd rifau sydd ei hangen yn S a sylwi ar y ffeithiau canlynol amdani.

• Mae S yn dechrau ag 1.
• Mae elfennau (scale-stream S 2) hefyd yn elfennau S.
• Mae'r un peth yn wir am (scale-stream S 3) ac (scale-stream S 5).
• Dyma holl elfennau S.

Nawr y cyfan sydd angen inni ei wneud yw cyfuno elfennau o'r ffynonellau hyn. Ar gyfer hyn diffiniwn weithdrefn merge sy'n cyfuno dwy ffrwd wedi'u trefnu yn un ffrwd ganlyniad wedi'i threfnu, gan ddileu ailadroddiadau:

(define (merge s1 s2)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (let ((s1car (stream-car s1))
               (s2car (stream-car s2)))
           (cond ((< s1car s2car)
                  (cons-stream 
                   s1car 
                   (merge (stream-cdr s1) 
                          s2)))
                 ((> s1car s2car)
                  (cons-stream 
                   s2car 
                   (merge s1 
                          (stream-cdr s2))))
                 (else
                  (cons-stream 
                   s1car
                   (merge 
                    (stream-cdr s1)
                    (stream-cdr s2)))))))))

Yna gellir adeiladu'r ffrwd sydd ei hangen ag merge, fel a ganlyn:

(define S (cons-stream 1 (merge ⟨??⟩ ⟨??⟩)))

Llenwch y mynegiadau coll yn y mannau sydd wedi'u nodi ag ⟨??⟩ uchod.

Ymarfer 3.57: Faint o adiadau a gyflawnir pan gyfrifwn rif Fibonacci rhif $n^{\text{fed}}$ gan ddefnyddio'r diffiniad o fibs sy'n seiliedig ar y weithdrefn add-streams? Dangoswch y byddai nifer yr adiadau yn fwy o ffactor esbonyddol pe baem wedi gweithredu (delay ⟨exp⟩) yn syml fel (lambda () ⟨exp⟩), heb ddefnyddio'r optimeiddiad a ddarperir gan y weithdrefn memo-proc a ddisgrifir yn 3.5.1.¹⁹²

Ymarfer 3.58: Rhowch ddehongliad o'r ffrwd a gyfrifir gan y weithdrefn ganlynol:

(define (expand num den radix)
  (cons-stream
   (quotient (* num radix) den)
   (expand (remainder (* num radix) den) 
           den 
           radix)))

(Gweithrediad cyntefig yw Quotient sy'n dychwelyd cyniferydd cyfanrifol dau gyfanrif.) Beth yw'r elfennau olynol a gynhyrchir gan (expand 1 7 10)? Beth a gynhyrchir gan (expand 3 8 10)?

Ymarfer 3.59: Yn 2.5.3 gwelsom sut i weithredu system rhifyddeg polynomialau sy'n cynrychioli polynomialau'n rhestrau o dermau. Mewn ffordd debyg, gallwn weithio â chyfresi pŵer, megis $$\begin{array}{rcl}{e}^x& =& 1+x+\frac{1}{2}{x}^2+\frac{1}{3\cdot <!--\; \cdot \; -->2}{x}^3+\frac{1}{4\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->2}{x}^4+\dots <!--\; \dots \; -->,\\ \cos <!--\; \; -->x& =& 1-<!--\; -\; -->\frac{1}{2}{x}^2+\frac{1}{4\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->2}{x}^4-<!--\; -\; -->\dots <!--\; \dots \; -->,\\ \sin <!--\; \; -->x& =& x-<!--\; -\; -->\frac{1}{3\cdot <!--\; \cdot \; -->2}{x}^3+\frac{1}{5\cdot <!--\; \cdot \; -->4\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->2}{x}^5-<!--\; -\; -->\dots <!--\; \dots \; -->\end{array}$$ wedi'u cynrychioli'n ffrydiau anfeidrol. Byddwn yn cynrychioli'r gyfres $a_0+a_{1}x+a_2{x}^2+a_3{x}^3+\dots <!--\; \dots \; -->$ yn ffrwd y mae ei helfennau yn gyfernodau $a_0$, $a_1$, $a_2$, $a_3$, ….

1. Integryn y gyfres $a_0+a_{1}x+a_2{x}^2+a_3{x}^3+\dots <!--\; \dots \; -->$ yw'r gyfres $$c+a_{0}x+\frac{1}{2}{a}_1{x}^2+\frac{1}{3}{a}_2{x}^3+\frac{1}{4}{a}_3{x}^4+\dots <!--\; \dots \; -->,$$ lle mae $c$ yn unrhyw gysonyn. Diffiniwch weithdrefn integrate-series sy'n cymryd yn fewnbwn ffrwd $a_0$, $a_1$, $a_2$, … sy'n cynrychioli cyfres pŵer, ac yn dychwelyd y ffrwd $a_0$, $\frac{1}{2}{a}_1$, $\frac{1}{3}{a}_2$, … o gyfernodau y termau nad ydynt yn gyson integryn y gyfres. (Gan nad oes gan y canlyniad derm cyson, nid yw'n cynrychioli cyfres pŵer; pan ddefnyddiwn integrate-series, byddwn yn defnyddio cons i osod y cysonyn priodol ar y blaen.)
2. Mae'r ffwythiant $x\mapsto <!--\; \mapsto \; -->e^x$ yn ddeilliad iddo'i hun. Mae hyn yn awgrymu bod $e^x$ ac integryn $e^x$ yr un gyfres, ac eithrio'r term cyson, sef $e^0=1$. Yn unol â hynny, gallwn gynhyrchu'r gyfres ar gyfer $e^x$ fel

   (define exp-series
     (cons-stream 
      1 (integrate-series exp-series)))

   Dangoswch sut i gynhyrchu'r cyfresi ar gyfer sin a chosin, gan ddechrau o'r ffeithiau mai cosin yw deilliad sin ac mai negatif sin yw deilliad cosin:

   (define cosine-series 
     (cons-stream 1 ⟨??⟩))
   
   (define sine-series
     (cons-stream 0 ⟨??⟩))

Ymarfer 3.60: Gyda chyfresi pŵer wedi'u cynrychioli'n ffrydiau o gyfernodau fel yn Ymarfer 3.59, gweithredir adio cyfresi gan add-streams. Cwblhewch ddiffiniad y weithdrefn ganlynol ar gyfer lluosi cyfresi:

(define (mul-series s1 s2)
  (cons-stream ⟨??⟩ (add-streams ⟨??⟩ ⟨??⟩)))

Gallwch brofi eich gweithdrefn drwy ddilysu bod ${\sin }^2<!--\; \; -->x+{\cos }^2<!--\; \; -->x=1,$ gan ddefnyddio'r cyfresi o Ymarfer 3.59.

Ymarfer 3.61: Boed $S$ yn gyfres pŵer (Ymarfer 3.59) y mae ei therm cyson yn 1. Tybiwch ein bod am ganfod y gyfres pŵer $1/S$, hynny yw, y gyfres $X$ fel bod $SX=1$. Ysgrifennwch $S=1+S_R$ lle mai $S_R$ yw'r rhan o $S$ ar ôl y term cyson. Yna gallwn ddatrys am $X$ fel a ganlyn: $$\begin{array}{rcl}S\cdot <!--\; \cdot \; -->X& =& 1,\\ (1+S_R)\cdot <!--\; \cdot \; -->X& =& 1,\\ X+S_R\cdot <!--\; \cdot \; -->X& =& 1,\\ X& =& 1-<!--\; -\; -->S_R\cdot <!--\; \cdot \; -->X.\end{array}$$ Mewn geiriau eraill, $X$ yw'r gyfres pŵer y mae ei therm cyson yn 1 a'i thermau trefn uwch yn cael eu rhoi gan negatif $S_R$ wedi'i luosi ag $X$. Defnyddiwch y syniad hwn i ysgrifennu gweithdrefn invert-unit-series sy'n cyfrifo $1/S$ ar gyfer cyfres pŵer $S$ â therm cyson 1. Bydd angen ichi ddefnyddio mul-series o Ymarfer 3.60.

Ymarfer 3.62: Defnyddiwch ganlyniadau Ymarfer 3.60 ac Ymarfer 3.61 i ddiffinio gweithdrefn div-series sy'n rhannu dwy gyfres pŵer. Dylai Div-series weithio ar gyfer unrhyw ddwy gyfres, ar yr amod bod cyfres yr enwadur yn dechrau â therm cyson nad yw'n sero. (Os oes gan yr enwadur derm cyson sero, dylai div-series arwyddo gwall.) Dangoswch sut i ddefnyddio div-series ynghyd â chanlyniad Ymarfer 3.59 i gynhyrchu'r gyfres pŵer ar gyfer tangiad.

3.5.3Manteisio ar y Paradeim Ffrydiau

Gall ffrydiau â gwerthuso gohiriedig fod yn offeryn modelu pwerus, gan ddarparu llawer o fanteision cyflwr lleol ac aseiniad. Ar ben hynny, maent yn osgoi rhai o'r dryswch damcaniaethol sy'n cyd-fynd â chyflwyno aseiniad i iaith raglennu.

Gall y dull ffrydiau daflu goleuni ar bethau am ei fod yn caniatáu inni adeiladu systemau â ffiniau modiwlau gwahanol i systemau a drefnir o amgylch aseiniad i newidynnau cyflwr. Er enghraifft, gallwn ganolbwyntio ar gyfres amser gyfan (neu signal), yn hytrach na gwerthoedd y newidynnau cyflwr ar eiliadau unigol. Mae hyn yn ei gwneud yn gyfleus cyfuno a chymharu cydrannau cyflwr o wahanol eiliadau.

Llunio iteriadau fel prosesau ffrydiau

Yn adran 1.2.1, cyflwynasom brosesau iteru, sy'n mynd rhagddynt drwy ddiweddaru newidynnau cyflwr. Gwyddom bellach y gallwn gynrychioli cyflwr yn ffrwd “ddiamser” o werthoedd yn hytrach nag yn set o newidynnau i'w diweddaru. Gadewch inni fabwysiadu'r safbwynt hwn wrth ailystyried y weithdrefn gwreiddyn sgwâr o 1.1.7. Cofiwch mai'r syniad yw cynhyrchu dilyniant o ddyfaliadau gwell a gwell ar gyfer gwreiddyn sgwâr $x$ drwy gymhwyso dro ar ôl tro'r weithdrefn sy'n gwella dyfaliadau:

(define (sqrt-improve guess x)
  (average guess (/ x guess)))

Yn ein gweithdrefn sqrt wreiddiol, gwnaethom y dyfaliadau hyn yn werthoedd olynol newidyn cyflwr. Yn lle hynny gallwn gynhyrchu ffrwd anfeidrol y dyfaliadau, gan ddechrau â dyfaliad cychwynnol o 1:¹⁹³

(define (sqrt-stream x)
  (define guesses
    (cons-stream 
     1.0 (stream-map
          (lambda (guess)
            (sqrt-improve guess x))
          guesses)))
  guesses)

(display-stream (sqrt-stream 2))
1.
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
…

Gallwn gynhyrchu mwy a mwy o dermau'r ffrwd i gael dyfaliadau gwell a gwell. Os dymunwn, gallwn ysgrifennu gweithdrefn sy'n parhau i gynhyrchu termau nes bod yr ateb yn ddigon da. (Gweler Ymarfer 3.64.)

Iteriad arall y gallwn ei drin yn yr un ffordd yw cynhyrchu brasamcan i $\mathrm{\pi <!--\; \pi \; -->}$, yn seiliedig ar y gyfres eiledol a welsom yn 1.3.1: $$\frac{\mathrm{\pi <!--\; \pi \; -->}}{4}=1-<!--\; -\; -->\frac{1}{3}+\frac{1}{5}-<!--\; -\; -->\frac{1}{7}+\dots <!--\; \dots \; -->.$$ Yn gyntaf cynhyrchwn ffrwd adendau'r gyfres (cilyddion y cyfanrifau od, ag arwyddion eiledol). Yna cymerwn ffrwd symiau mwy a mwy o dermau (gan ddefnyddio gweithdrefn partial-sums Ymarfer 3.55) a graddiwn y canlyniad â 4:

(define (pi-summands n)
  (cons-stream 
   (/ 1.0 n)
   (stream-map - (pi-summands (+ n 2)))))

(define pi-stream
  (scale-stream 
   (partial-sums (pi-summands 1)) 4))

(display-stream pi-stream)
4.
2.666666666666667
3.466666666666667
2.8952380952380956
3.3396825396825403
2.9760461760461765
3.2837384837384844
3.017071817071818
…

Mae hyn yn rhoi ffrwd o frasamcanion gwell a gwell i $\mathrm{\pi <!--\; \pi \; -->}$ inni, er bod y brasamcanion yn cydgyfeirio braidd yn araf. Mae wyth term o'r dilyniant yn gosod gwerth $\mathrm{\pi <!--\; \pi \; -->}$ rhwng 3.284 a 3.017.

Hyd yma, nid yw ein defnydd o'r dull ffrwd cyflyrau yn wahanol iawn i ddiweddaru newidynnau cyflwr. Ond mae ffrydiau'n rhoi cyfle inni wneud rhai triciau diddorol. Er enghraifft, gallwn drawsffurfio ffrwd â chyflymydd dilyniant sy'n trosi dilyniant o frasamcanion yn ddilyniant newydd sy'n cydgyfeirio at yr un gwerth â'r gwreiddiol, ond yn gyflymach.

Mae un cyflymydd o'r fath, a ddyfeisiwyd gan y mathemategydd Swisaidd o'r ddeunawfed ganrif, Leonhard Euler, yn gweithio'n dda â dilyniannau sy'n symiau rhannol cyfresi eiledol (cyfresi o dermau ag arwyddion eiledol). Yn nhechneg Euler, os mai $S_n$ yw term rhif $n^{\text{fed}}$ y dilyniant symiau gwreiddiol, yna mae gan y dilyniant wedi'i gyflymu dermau $$S_{n+1}-<!--\; -\; -->\frac{(S_{n+1}-<!--\; -\; -->S_n{)}^2}{S_{n-<!--\; -\; -->1}-<!--\; -\; -->2S_n+S_{n+1}}.$$ Felly, os cynrychiolir y dilyniant gwreiddiol yn ffrwd o werthoedd, rhoddir y dilyniant wedi'i drawsffurfio gan

(define (euler-transform s)
  (let ((s0 (stream-ref s 0))     ; Sₙ₋₁
        (s1 (stream-ref s 1))     ; Sₙ
        (s2 (stream-ref s 2)))    ; Sₙ₊₁
    (cons-stream 
     (- s2 (/ (square (- s2 s1))
              (+ s0 (* -2 s1) s2)))
     (euler-transform (stream-cdr s)))))

Gallwn ddangos cyflymu Euler â'n dilyniant o frasamcanion i $\mathrm{\pi <!--\; \pi \; -->}$:

(display-stream 
 (euler-transform pi-stream))
3.166666666666667
3.1333333333333337
3.1452380952380956
3.13968253968254
3.1427128427128435
3.1408813408813416
3.142071817071818
3.1412548236077655
…

Yn well byth, gallwn gyflymu'r dilyniant wedi'i gyflymu, a chyflymu hwnnw'n ddychweliadol, ac yn y blaen. Hynny yw, crëwn ffrwd o ffrydiau (strwythur y byddwn yn ei alw'n dabl haenog) lle mae pob ffrwd yn drawsffurfiad o'r un flaenorol:

(define (make-tableau transform s)
  (cons-stream 
   s
   (make-tableau
    transform
    (transform s))))

Mae gan y tabl haenog y ffurf $$\begin{array}{cccccc}{s}_{00}& s_{01}& s_{02}& s_{03}& s_{04}& \dots <!--\; \dots \; -->\\ & s_{10}& s_{11}& s_{12}& s_{13}& \dots <!--\; \dots \; -->\\ & & s_{20}& s_{21}& s_{22}& \dots <!--\; \dots \; -->\\ & & & \dots <!--\; \dots \; -->& & \end{array}$$ Yn olaf, ffurfiwn ddilyniant drwy gymryd y term cyntaf ym mhob rhes o'r tabl haenog:

(define (accelerated-sequence transform s)
  (stream-map stream-car
              (make-tableau transform s)))

Gallwn ddangos y math hwn o “uwchgyflymu” ar y dilyniant $\mathrm{\pi <!--\; \pi \; -->}$:

(display-stream 
 (accelerated-sequence euler-transform
                       pi-stream))
4.
3.166666666666667
3.142105263157895
3.141599357319005
3.1415927140337785
3.1415926539752927
3.1415926535911765
3.141592653589778
…

Mae'r canlyniad yn drawiadol. Mae cymryd wyth term o'r dilyniant yn rhoi gwerth cywir $\mathrm{\pi <!--\; \pi \; -->}$ i 14 lle degol. Pe baem wedi defnyddio'r dilyniant $\mathrm{\pi <!--\; \pi \; -->}$ gwreiddiol yn unig, byddai angen inni gyfrifo tua ${10}^{13}$ o dermau (h.y., ehangu'r gyfres yn ddigon pell fel bod y termau unigol yn llai nag ${10}^{-<!--\; -\; -->13}$) i gael cymaint â hynny o gywirdeb!

Gallem fod wedi gweithredu'r technegau cyflymu hyn heb ddefnyddio ffrydiau. Ond mae'r ffurfiad ffrydiau yn arbennig o gain a chyfleus am fod y dilyniant cyflyrau cyfan ar gael inni fel strwythur data y gellir ei drin â set unffurf o weithrediadau.

Ymarfer 3.63: Mae Louis Reasoner yn gofyn pam na ysgrifennwyd y weithdrefn sqrt-stream yn y ffordd fwy uniongyrchol ganlynol, heb y newidyn lleol guesses:

(define (sqrt-stream x)
  (cons-stream 
   1.0
   (stream-map (lambda (guess)
                 (sqrt-improve guess x))
               (sqrt-stream x))))

Mae Alyssa P. Hacker yn ateb bod y fersiwn hon o'r weithdrefn yn sylweddol lai effeithlon am ei bod yn cyflawni cyfrifiannu diangen. Esboniwch ateb Alyssa. A fyddai'r ddwy fersiwn yn dal i fod yn wahanol o ran effeithlonrwydd pe bai ein gweithrediad o delay yn defnyddio (lambda () ⟨exp⟩) yn unig heb ddefnyddio'r optimeiddiad a ddarperir gan memo-proc (3.5.1)?

Ymarfer 3.64: Ysgrifennwch weithdrefn stream-limit sy'n cymryd ffrwd a rhif (y goddefiant) yn argiau. Dylai archwilio'r ffrwd nes dod o hyd i ddwy elfen olynol y mae gwerth absoliwt eu gwahaniaeth yn llai na'r goddefiant, a dychwelyd yr ail o'r ddwy elfen. Gan ddefnyddio hyn, gallem gyfrifo gwreiddiau sgwâr hyd at oddefiant penodedig drwy

(define (sqrt x tolerance)
  (stream-limit (sqrt-stream x) tolerance))

Ymarfer 3.65: Defnyddiwch y gyfres $$\ln <!--\; \; -->2=1-<!--\; -\; -->\frac{1}{2}+\frac{1}{3}-<!--\; -\; -->\frac{1}{4}+\dots <!--\; \dots \; -->$$ i gyfrifo tri dilyniant o frasamcanion i logarithm naturiol 2, yn yr un ffordd ag y gwnaethom uchod ar gyfer $\mathrm{\pi <!--\; \pi \; -->}$. Pa mor gyflym mae'r dilyniannau hyn yn cydgyfeirio?

Ffrydiau anfeidrol o barau

Yn 2.2.3, gwelsom sut mae'r paradeim dilyniannau yn trin dolenni nythol traddodiadol fel prosesau wedi'u diffinio ar ddilyniannau o barau. Os cyffredinolwn y dechneg hon i ffrydiau anfeidrol, yna gallwn ysgrifennu rhaglenni nad yw'n hawdd eu cynrychioli'n ddolenni, am fod rhaid i'r “dolennu” amrywio dros set anfeidrol.

Er enghraifft, tybiwch ein bod am gyffredinoli gweithdrefn prime-sum-pairs 2.2.3 i gynhyrchu ffrwd parau'r holl gyfanrifau $(i,j)$ ag $i\le <!--\; \le \; -->j$ fel bod $i+j$ yn gysefin. Os mai int-pairs yw dilyniant holl barau'r cyfanrifau $(i,j)$ ag $i\le <!--\; \le \; -->j$, yna'r ffrwd sydd ei hangen arnom yw, yn syml,¹⁹⁴

(stream-filter 
 (lambda (pair)
   (prime? (+ (car pair) (cadr pair))))
 int-pairs)

Ein problem, felly, yw cynhyrchu'r ffrwd int-pairs. Yn fwy cyffredinol, tybiwch fod gennym ddwy ffrwd $S=(S_i)$ ac $T=(T_j)$, a dychmygwch yr arae betryal anfeidrol $$\begin{array}{cccc}(S_0,T_0)& (S_0,T_1)& (S_0,T_2)& \dots <!--\; \dots \; -->\\ (S_1,T_0)& (S_1,T_1)& (S_1,T_2)& \dots <!--\; \dots \; -->\\ (S_2,T_0)& (S_2,T_1)& (S_2,T_2)& \dots <!--\; \dots \; -->\\ \dots <!--\; \dots \; -->& & & \end{array}$$ Dymunwn gynhyrchu ffrwd sy'n cynnwys yr holl barau yn yr arae sydd ar y groeslin neu uwch ei phen, h.y., y parau $$\begin{array}{cccc}(S_0,T_0)& (S_0,T_1)& (S_0,T_2)& \dots <!--\; \dots \; -->\\ & (S_1,T_1)& (S_1,T_2)& \dots <!--\; \dots \; -->\\ & & (S_2,T_2)& \dots <!--\; \dots \; -->\\ & & & \dots <!--\; \dots \; -->\end{array}$$ (Os cymerwn $S$ ac $T$ ill dau yn ffrwd y cyfanrifau, yna hon fydd y ffrwd int-pairs a ddymunwn.)

Galwch y ffrwd gyffredinol o barau yn (pairs S T), ac ystyriwch ei bod yn cynnwys tair rhan: y pâr $(S_0,T_0)$, gweddill y parau yn y rhes gyntaf, a'r parau sy'n weddill:¹⁹⁵ $$\begin{array}{cccc}(S_0,T_0)& (S_0,T_1)& (S_0,T_2)& \dots <!--\; \dots \; -->\\ & (S_1,T_1)& (S_1,T_2)& \dots <!--\; \dots \; -->\\ & & (S_2,T_2)& \dots <!--\; \dots \; -->\\ & & & \dots <!--\; \dots \; -->\end{array}$$ Sylwch mai'r trydydd darn yn y dadelfeniad hwn (parau nad ydynt yn y rhes gyntaf) yw (yn ddychweliadol) y parau a ffurfir o (stream-cdr S) ac (stream-cdr T). Sylwch hefyd mai'r ail ddarn (gweddill y rhes gyntaf) yw

(stream-map (lambda (x) 
              (list (stream-car s) x))
            (stream-cdr t))

Felly gallwn ffurfio ein ffrwd o barau fel a ganlyn:

(define (pairs s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (⟨combine-in-some-way⟩
    (stream-map (lambda (x) 
                  (list (stream-car s) x))
                (stream-cdr t))
    (pairs (stream-cdr s)
           (stream-cdr t)))))

Er mwyn cwblhau'r weithdrefn, rhaid inni ddewis rhyw ffordd o gyfuno'r ddwy ffrwd fewnol. Un syniad yw defnyddio'r fersiwn ffrydiau o'r weithdrefn append o 2.2.1:

(define (stream-append s1 s2)
  (if (stream-null? s1)
      s2
      (cons-stream 
       (stream-car s1)
       (stream-append (stream-cdr s1) s2))))

Fodd bynnag, mae hyn yn anaddas ar gyfer ffrydiau anfeidrol, am ei fod yn cymryd yr holl elfennau o'r ffrwd gyntaf cyn cynnwys yr ail ffrwd. Yn benodol, os ceisiwn gynhyrchu holl barau'r cyfanrifau positif gan ddefnyddio

(pairs integers integers)

bydd ein ffrwd ganlyniadau'n ceisio rhedeg yn gyntaf drwy'r holl barau lle mae'r cyfanrif cyntaf yn hafal i 1, ac felly ni fydd byth yn cynhyrchu parau ag unrhyw werth arall i'r cyfanrif cyntaf.

I drin ffrydiau anfeidrol, mae angen inni ddyfeisio trefn gyfuno sy'n sicrhau y cyrhaeddir pob elfen yn y pen draw os gadawn i'n rhaglen redeg yn ddigon hir. Ffordd gain o gyflawni hyn yw drwy'r weithdrefn interleave ganlynol:¹⁹⁶

(define (interleave s1 s2)
  (if (stream-null? s1)
      s2
      (cons-stream 
       (stream-car s1)
       (interleave s2 (stream-cdr s1)))))

Gan fod interleave yn cymryd elfennau bob yn ail o'r ddwy ffrwd, bydd pob elfen o'r ail ffrwd yn cyrraedd y ffrwd wedi'i chydblethu yn y pen draw, hyd yn oed os yw'r ffrwd gyntaf yn anfeidrol.

Felly gallwn gynhyrchu'r ffrwd o barau sydd ei hangen fel

(define (pairs s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (interleave
    (stream-map (lambda (x) 
                  (list (stream-car s) x))
                (stream-cdr t))
    (pairs (stream-cdr s) (stream-cdr t)))))

Ymarfer 3.66: Archwiliwch y ffrwd (pairs integers integers). A allwch wneud unrhyw sylwadau cyffredinol am y drefn y gosodir y parau yn y ffrwd ynddi? Er enghraifft, tua faint o barau sy'n dod cyn y pâr (1, 100)? y pâr (99, 100)? y pâr (100, 100)? (Os gallwch wneud datganiadau mathemategol manwl gywir yma, gorau oll. Ond mae croeso ichi roi atebion mwy ansoddol os byddwch yn mynd yn sownd.)

Ymarfer 3.67: Addaswch y weithdrefn pairs fel y bydd (pairs integers integers) yn cynhyrchu ffrwd holl barau'r cyfanrifau $(i,j)$ (heb yr amod $i\le <!--\; \le \; -->j$). Awgrym: Bydd angen ichi gymysgu ffrwd ychwanegol i mewn.

Ymarfer 3.68: Mae Louis Reasoner yn meddwl bod adeiladu ffrwd o barau o dair rhan yn ddiangen o gymhleth. Yn lle gwahanu'r pâr $(S_0,T_0)$ oddi wrth weddill y parau yn y rhes gyntaf, mae'n cynnig gweithio â'r rhes gyntaf gyfan, fel a ganlyn:

(define (pairs s t)
  (interleave
   (stream-map
    (lambda (x) 
      (list (stream-car s) x))
    t)
   (pairs (stream-cdr s)
          (stream-cdr t))))

A yw hyn yn gweithio? Ystyriwch beth sy'n digwydd os gwerthuswn (pairs integers integers) gan ddefnyddio diffiniad Louis o pairs.

Ymarfer 3.69: Ysgrifennwch weithdrefn triples sy'n cymryd tair ffrwd anfeidrol, $S$, $T$, ac $U$, ac yn cynhyrchu ffrwd y tripledi $(S_i,T_j,U_k)$ fel bod $i\le <!--\; \le \; -->j\le <!--\; \le \; -->k$. Defnyddiwch triples i gynhyrchu ffrwd yr holl dripledi Pythagoraidd o gyfanrifau positif, h.y., y tripledi $(i,j,k)$ fel bod $i\le <!--\; \le \; -->j$ ac $i^2+j^2=k^2$.

Ymarfer 3.70: Byddai'n braf gallu cynhyrchu ffrydiau lle mae'r parau'n ymddangos mewn rhyw drefn ddefnyddiol, yn hytrach na'r drefn sy'n deillio o broses gydblethu ad hoc. Gallwn ddefnyddio techneg debyg i weithdrefn merge Ymarfer 3.56, os diffiniwn ffordd o ddweud bod un pâr o gyfanrifau yn “llai nag” un arall. Un ffordd o wneud hyn yw diffinio “ffwythiant pwysoli” $W(i,j)$ a phennu bod $(i_1,j_1)$ yn llai nag $(i_2,j_2)$ os yw $W(i_1,j_1)<W(i_2,j_2)$. Ysgrifennwch weithdrefn merge-weighted sy'n debyg i merge, ac eithrio bod merge-weighted yn cymryd arg ychwanegol weight, sef gweithdrefn sy'n cyfrifo pwysau pâr ac a ddefnyddir i bennu'r drefn y dylai elfennau ymddangos yn y ffrwd gyfun a geir ynddi.¹⁹⁷ Gan ddefnyddio hyn, cyffredinolwch pairs i weithdrefn weighted-pairs sy'n cymryd dwy ffrwd, ynghyd â gweithdrefn sy'n cyfrifo ffwythiant pwysoli, ac yn cynhyrchu ffrwd y parau, wedi'u trefnu yn ôl pwysau. Defnyddiwch eich gweithdrefn i gynhyrchu

1. ffrwd holl barau'r cyfanrifau positif $(i,j)$ ag $i\le <!--\; \le \; -->j$ wedi'u trefnu yn ôl y swm $i+j$,
2. ffrwd holl barau'r cyfanrifau positif $(i,j)$ ag $i\le <!--\; \le \; -->j$, lle nad yw $i$ nac $j$ yn rhanadwy â 2, 3, na 5, a lle trefnir y parau yn ôl y swm $2i+3j+5ij$.

Ymarfer 3.71: Weithiau gelwir rhifau y gellir eu mynegi'n swm dau giwb mewn mwy nag un ffordd yn rhifau Ramanujan, er anrhydedd i'r mathemategydd Srinivasa Ramanujan.¹⁹⁸ Mae ffrydiau o barau wedi'u trefnu'n darparu ateb cain i'r broblem o gyfrifo'r rhifau hyn. I ganfod rhif y gellir ei ysgrifennu'n swm dau giwb mewn dwy ffordd wahanol, nid oes angen inni ond cynhyrchu ffrwd parau'r cyfanrifau $(i,j)$ wedi'u pwysoli yn ôl y swm $i^3+j^3$ (gweler Ymarfer 3.70), ac yna chwilio'r ffrwd am ddau bâr olynol â'r un pwysau. Ysgrifennwch weithdrefn i gynhyrchu rhifau Ramanujan. Y rhif cyntaf o'r fath yw 1,729. Beth yw'r pump nesaf?

Ymarfer 3.72: Mewn ffordd debyg i Ymarfer 3.71, cynhyrchwch ffrwd o'r holl rifau y gellir eu hysgrifennu'n swm dau sgwâr mewn tair ffordd wahanol (gan ddangos sut y gellir eu hysgrifennu felly).

Ffrydiau fel signalau

Dechreuasom ein trafodaeth ar ffrydiau drwy eu disgrifio'n gyfatebiaethau cyfrifiadurol i'r “signalau” mewn systemau prosesu signalau. Yn wir, gallwn ddefnyddio ffrydiau i fodelu systemau prosesu signalau mewn ffordd uniongyrchol iawn, gan gynrychioli gwerthoedd signal ar gyfyngau amser olynol yn elfennau olynol ffrwd. Er enghraifft, gallwn weithredu integrydd neu symiwr sydd, ar gyfer ffrwd fewnbwn $x=(x_i)$, gwerth cychwynnol $C$, a chynyddiad bach $dt$, yn cronni'r swm $$S_i=C+\underset{j=1}{\overset{i}{\sum <!--\; \sum \; -->}}{x}_{j}dt$$ ac yn dychwelyd ffrwd y gwerthoedd $S=(S_i)$. Mae'r weithdrefn integral ganlynol yn atgoffa rhywun o'r diffiniad “arddull ymhlyg” o ffrwd y cyfanrifau (3.5.2):

(define (integral integrand initial-value dt)
  (define int
    (cons-stream 
     initial-value
     (add-streams (scale-stream integrand dt)
                  int)))
  int)

Mae Ffigur 3.32 yn ddarlun o system prosesu signalau sy'n cyfateb i'r weithdrefn integral. Graddir y ffrwd fewnbwn ag $dt$ a'i phasio drwy adydd, y pasir ei allbwn yn ôl drwy'r un adydd. Adlewyrchir yr hunangyfeirio yn niffiniad int yn y ffigur gan y ddolen adborth sy'n cysylltu allbwn yr adydd ag un o'r mewnbynnau.

Ymarfer 3.73: Gallwn fodelu cylchedau trydanol gan ddefnyddio ffrydiau i gynrychioli gwerthoedd ceryntau neu folteddau ar ddilyniant o adegau. Er enghraifft, tybiwch fod gennym gylched RC sy'n cynnwys gwrthydd â gwrthiant $R$ a chynhwysydd â chynhwysiant $C$ mewn cyfres. Pennir ymateb foltedd $v$ y gylched i gerrynt a gyflenwir $i$ gan y fformiwla yn Ffigur 3.33, y dangosir ei strwythur gan y diagram llif signalau cysylltiedig.

Ysgrifennwch weithdrefn RC sy'n modelu'r gylched hon. Dylai RC gymryd gwerthoedd $R$, $C$, ac $dt$ yn fewnbynnau a dylai ddychwelyd gweithdrefn sy'n cymryd yn fewnbynnau ffrwd sy'n cynrychioli'r cerrynt $i$ a gwerth cychwynnol i foltedd y cynhwysydd $v_0$, ac yn cynhyrchu ffrwd y folteddau $v$ yn allbwn. Er enghraifft, dylech allu defnyddio RC i fodelu cylched RC ag $R$ = 5 ohm, $C$ = 1 farad, a cham amser o 0.5 eiliad drwy werthuso (define RC1 (RC 5 1 0.5)). Mae hyn yn diffinio RC1 yn weithdrefn sy'n cymryd ffrwd sy'n cynrychioli dilyniant amser y ceryntau a foltedd cychwynnol y cynhwysydd, ac yn cynhyrchu ffrwd allbwn y folteddau.

Ymarfer 3.74: Mae Alyssa P. Hacker yn dylunio system i brosesu signalau sy'n dod o synwyryddion ffisegol. Un nodwedd bwysig y mae am ei chynhyrchu yw signal sy'n disgrifio croesiadau sero y signal mewnbwn. Hynny yw, dylai'r signal a geir fod yn $+1$ pryd bynnag y mae'r signal mewnbwn yn newid o negatif i bositif, yn $-<!--\; -\; -->1$ pryd bynnag y mae'r signal mewnbwn yn newid o bositif i negatif, ac yn $0$ fel arall. (Tybiwch fod arwydd mewnbwn $0$ yn bositif.) Er enghraifft, gallai signal mewnbwn nodweddiadol a'i signal croesi sero cysylltiedig fod fel a ganlyn

… 1 2 1.5 1 0.5 -0.1 -2 -3 -2 -0.5 0.2 3 4 …
… 0 0  0  0  0   -1   0  0  0   0   1  0 0 …

Yn system Alyssa, cynrychiolir signal y synhwyrydd yn ffrwd sense-data a'r ffrwd zero-crossings yw'r ffrwd gyfatebol o groesiadau sero. Yn gyntaf mae Alyssa yn ysgrifennu gweithdrefn sign-change-detector sy'n cymryd dau werth yn argiau ac yn cymharu arwyddion y gwerthoedd i gynhyrchu $0$, $1$, neu $-<!--\; -\; -->1$ priodol. Yna mae'n adeiladu ei ffrwd croesi sero fel a ganlyn:

(define (make-zero-crossings
         input-stream last-value)
  (cons-stream
   (sign-change-detector 
    (stream-car input-stream) 
    last-value)
   (make-zero-crossings 
    (stream-cdr input-stream)
    (stream-car input-stream))))

(define zero-crossings 
  (make-zero-crossings sense-data 0))

Mae pennaeth Alyssa, Eva Lu Ator, yn cerdded heibio ac yn awgrymu bod y rhaglen hon fwy neu lai'n gyfwerth â'r un ganlynol, sy'n defnyddio'r fersiwn gyffredinoledig o stream-map o Ymarfer 3.50:

(define zero-crossings
  (stream-map sign-change-detector 
              sense-data 
              ⟨expression⟩))

Cwblhewch y rhaglen drwy ddarparu'r ⟨expression⟩ a nodir.

Ymarfer 3.75: Yn anffodus, nid yw canfodydd croesiadau sero Alyssa yn Ymarfer 3.74 yn ddigonol, am fod y signal swnllyd o'r synhwyrydd yn arwain at groesiadau sero ffug. Mae Lem E. Tweakit, arbenigwr caledwedd, yn awgrymu bod Alyssa yn llyfnhau'r signal i hidlo'r sŵn allan cyn tynnu'r croesiadau sero. Mae Alyssa yn dilyn ei gyngor ac yn penderfynu tynnu'r croesiadau sero o'r signal a adeiledir drwy gyfartaleddu pob gwerth yn y data synhwyro â'r gwerth blaenorol. Mae'n esbonio'r broblem i'w chynorthwyydd, Louis Reasoner, sy'n ceisio gweithredu'r syniad, gan addasu rhaglen Alyssa fel a ganlyn:

(define (make-zero-crossings 
         input-stream last-value)
  (let ((avpt 
         (/ (+ (stream-car input-stream) 
               last-value) 
            2)))
    (cons-stream 
     (sign-change-detector avpt last-value)
     (make-zero-crossings 
      (stream-cdr input-stream) avpt))))

Nid yw hyn yn gweithredu cynllun Alyssa yn gywir. Canfyddwch y byg y mae Louis wedi'i gyflwyno a chywirwch ef heb newid strwythur y rhaglen. (Awgrym: Bydd angen ichi gynyddu nifer yr argiau i make-zero-crossings.)

Ymarfer 3.76: Mae gan Eva Lu Ator feirniadaeth o ddull Louis yn Ymarfer 3.75. Nid yw'r rhaglen a ysgrifennodd yn fodiwlaidd, am ei bod yn cymysgu'r gweithrediad llyfnhau â thynnu'r croesiadau sero. Er enghraifft, ni ddylai fod angen newid y canfodydd os yw Alyssa yn canfod ffordd well o gyflyru ei signal mewnbwn. Helpwch Louis drwy ysgrifennu gweithdrefn smooth sy'n cymryd ffrwd yn fewnbwn ac yn cynhyrchu ffrwd lle mae pob elfen yn gyfartaledd dwy elfen olynol o'r ffrwd fewnbwn. Yna defnyddiwch smooth yn gydran i weithredu'r canfodydd croesiadau sero mewn arddull fwy modiwlaidd.

3.5.4Ffrydiau a Gwerthuso Gohiriedig

Mae'r weithdrefn integral ar ddiwedd yr adran flaenorol yn dangos sut y gallwn ddefnyddio ffrydiau i fodelu systemau prosesu signalau sy'n cynnwys dolenni adborth. Modelir dolen adborth yr adydd a ddangosir yn Ffigur 3.32 gan y ffaith bod ffrwd fewnol int y weithdrefn integral wedi'i diffinio yn nhermau ei hun:

(define int
  (cons-stream 
   initial-value
   (add-streams 
    (scale-stream integrand dt) int)))

Mae gallu'r dehonglydd i ymdrin â diffiniad ymhlyg o'r fath yn dibynnu ar yr delay sydd wedi'i gynnwys yn cons-stream. Heb yr delay hwn, ni allai'r dehonglydd adeiladu int cyn gwerthuso'r ddau arg i cons-stream, a byddai hynny'n gofyn bod int eisoes wedi'i ddiffinio. Yn gyffredinol, mae delay yn hanfodol i ddefnyddio ffrydiau i fodelu systemau prosesu signalau sy'n cynnwys dolenni. Heb delay, byddai'n rhaid llunio ein modelau fel bod mewnbynnau unrhyw gydran prosesu signalau yn cael eu gwerthuso'n llawn cyn y gellid cynhyrchu'r allbwn. Byddai hyn yn gwahardd dolenni.

Yn anffodus, gall modelau ffrydiau o systemau â dolenni ofyn am ddefnyddiau o delay y tu hwnt i'r delay “cudd” a ddarperir gan cons-stream. Er enghraifft, mae Ffigur 3.34 yn dangos system prosesu signalau ar gyfer datrys yr hafaliad differol $dy/dt=f(y)$ lle mae $f$ yn ffwythiant a roddwyd. Mae'r ffigur yn dangos cydran fapio, sy'n cymhwyso $f$ i'w signal mewnbwn, wedi'i chysylltu mewn dolen adborth ag integrydd mewn ffordd debyg iawn i gylchedau'r cyfrifiaduron analog a ddefnyddir mewn gwirionedd i ddatrys hafaliadau o'r fath.

Gan dybio ein bod yn cael gwerth cychwynnol $y_0$ ar gyfer $y$, gallem geisio modelu'r system hon gan ddefnyddio'r weithdrefn

(define (solve f y0 dt)
  (define y (integral dy y0 dt))
  (define dy (stream-map f y))
  y)

Nid yw'r weithdrefn hon yn gweithio, am fod yr alwad i integral yn llinell gyntaf solve yn gofyn bod y mewnbwn dy wedi'i ddiffinio, ac nid yw hynny'n digwydd tan ail linell solve.

Ar y llaw arall, mae bwriad ein diffiniad yn gwneud synnwyr, am y gallwn, mewn egwyddor, ddechrau cynhyrchu'r ffrwd y heb wybod dy. Yn wir, mae gan integral a llawer o weithrediadau ffrydiau eraill briodweddau tebyg i rai cons-stream, yn yr ystyr y gallwn gynhyrchu rhan o'r ateb o gael gwybodaeth rannol yn unig am yr argiau. Ar gyfer integral, elfen gyntaf y ffrwd allbwn yw'r initial-value penodedig. Felly, gallwn gynhyrchu elfen gyntaf y ffrwd allbwn heb werthuso'r integrand dy. Unwaith y gwyddom elfen gyntaf y, gall yr stream-map yn ail linell solve ddechrau gweithio i gynhyrchu elfen gyntaf dy, a fydd yn cynhyrchu elfen nesaf y, ac yn y blaen.

I fanteisio ar y syniad hwn, byddwn yn ailddiffinio integral i ddisgwyl i ffrwd yr integrand fod yn arg gohiriedig. Bydd Integral yn defnyddio force i orfodi gwerthuso'r integrand dim ond pan fydd ei angen i gynhyrchu mwy nag elfen gyntaf y ffrwd allbwn:

(define (integral
         delayed-integrand initial-value dt)
  (define int
    (cons-stream 
     initial-value
     (let ((integrand 
            (force delayed-integrand)))
       (add-streams 
        (scale-stream integrand dt)
        int))))
  int)

Nawr gallwn weithredu ein gweithdrefn solve drwy ohirio gwerthuso dy yn niffiniad y:¹⁹⁹

(define (solve f y0 dt)
  (define y (integral (delay dy) y0 dt))
  (define dy (stream-map f y))
  y)

Yn gyffredinol, rhaid i bob galwr integral bellach ddefnyddio delay i ohirio arg yr integrand. Gallwn ddangos bod y weithdrefn solve yn gweithio drwy frasamcanu $e\approx <!--\; \approx \; -->2.718$ drwy gyfrifo'r gwerth yn $y=1$ o ddatrysiad yr hafaliad differol $dy/dt=y$ â'r amod cychwynnol $y(0)=1$:

(stream-ref 
 (solve (lambda (y) y) 1 0.001) 1000)
2.716924

Ymarfer 3.77: Roedd y weithdrefn integral a ddefnyddiwyd uchod yn gyfatebol i'r diffiniad “ymhlyg” o ffrwd anfeidrol y cyfanrifau yn 3.5.2. Fel arall, gallwn roi diffiniad o integral sy'n debycach i integers-starting-from (hefyd yn 3.5.2):

(define (integral
         integrand initial-value dt)
  (cons-stream 
   initial-value
   (if (stream-null? integrand)
       the-empty-stream
       (integral 
        (stream-cdr integrand)
        (+ (* dt (stream-car integrand))
           initial-value)
        dt))))

Pan ddefnyddir hi mewn systemau â dolenni, mae gan y weithdrefn hon yr un broblem â'n fersiwn wreiddiol o integral. Addaswch y weithdrefn fel ei bod yn disgwyl yr integrand yn arg gohiriedig ac felly y gellir ei defnyddio yn y weithdrefn solve a ddangosir uchod.

Ymarfer 3.78: Ystyriwch y broblem o ddylunio system prosesu signalau i astudio'r hafaliad differol llinol homogenaidd ail drefn $$\frac{d^{2}y}{d{t}^2}-<!--\; -\; -->a\frac{dy}{dt}-<!--\; -\; -->by=0.$$ Cynhyrchir y ffrwd allbwn, sy'n modelu $y$, gan rwydwaith sy'n cynnwys dolen. Y rheswm yw bod gwerth $d^{2}y/d{t}^2$ yn dibynnu ar werthoedd $y$ ac $dy/dt$, a phennir y ddau hyn drwy integru $d^{2}y/d{t}^2$. Dangosir y diagram yr hoffem ei amgodio yn Ffigur 3.35. Ysgrifennwch weithdrefn solve-2nd sy'n cymryd yn argiau'r cysonion $a$, $b$, ac $dt$ a'r gwerthoedd cychwynnol $y_0$ ac $d{y}_0$ ar gyfer $y$ ac $dy/dt$, ac yn cynhyrchu ffrwd gwerthoedd olynol $y$.

Ymarfer 3.79: Cyffredinolwch weithdrefn solve-2nd Ymarfer 3.78 fel y gellir ei defnyddio i ddatrys hafaliadau differol ail drefn cyffredinol $d^{2}y/d{t}^2=f(dy/dt,y)$.

Ymarfer 3.80: Mae cylched RLC cyfresol yn cynnwys gwrthydd, cynhwysydd, ac anwythydd wedi'u cysylltu mewn cyfres, fel y dangosir yn Ffigur 3.36. Os mai $R$, $L$, ac $C$ yw'r gwrthiant, yr anwythiant, a'r cynhwysiant, yna disgrifir y perthnasoedd rhwng foltedd $(v)$ a cherrynt $(i)$ ar gyfer y tair cydran gan yr hafaliadau $$\begin{array}{rcl}{v}_R& =& i_{R}R,\\ v_L& =& L\frac{d{i}_L}{dt},\\ i_C& =& C\frac{d{v}_C}{dt},\end{array}$$ ac mae cysylltiadau'r gylched yn pennu'r perthnasoedd $$\begin{array}{rcl}{i}_R& =& i_L=-<!--\; -\; -->i_C,\\ v_C& =& v_L+v_R.\end{array}$$ Mae cyfuno'r hafaliadau hyn yn dangos bod cyflwr y gylched (wedi'i grynhoi gan $v_C$, y foltedd ar draws y cynhwysydd, ac $i_L$, y cerrynt yn yr anwythydd) yn cael ei ddisgrifio gan y pâr o hafaliadau differol $$\begin{array}{rcl}\frac{d{v}_C}{dt}& =& -<!--\; -\; -->\frac{i_L}{C},\\ \frac{d{i}_L}{dt}& =& \frac{1}{L}{v}_C-<!--\; -\; -->\frac{R}{L}{i}_L.\end{array}$$ Dangosir y diagram llif signalau sy'n cynrychioli'r system hon o hafaliadau differol yn Ffigur 3.37.

Ysgrifennwch weithdrefn RLC sy'n cymryd yn argiau baramedrau $R$, $L$, ac $C$ y gylched a'r cynyddiad amser $dt$. Mewn ffordd debyg i weithdrefn RC Ymarfer 3.73, dylai RLC gynhyrchu gweithdrefn sy'n cymryd gwerthoedd cychwynnol y newidynnau cyflwr, $v_{C_0}$ ac $i_{L_0}$, ac yn cynhyrchu pâr (gan ddefnyddio cons) o'r ffrydiau cyflyrau $v_C$ ac $i_L$. Gan ddefnyddio RLC, cynhyrchwch y pâr o ffrydiau sy'n modelu ymddygiad cylched RLC cyfresol ag $R$ = 1 ohm, $C$ = 0.2 farad, $L$ = 1 henry, $dt$ = 0.1 eiliad, a gwerthoedd cychwynnol $i_{L_0}$ = 0 amp ac $v_{C_0}$ = 10 folt.

Gwerthuso yn y drefn arferol

Mae'r enghreifftiau yn yr adran hon yn dangos sut mae defnyddio delay ac force yn benodol yn darparu hyblygrwydd mawr mewn rhaglennu, ond mae'r un enghreifftiau hefyd yn dangos sut y gall hyn wneud ein rhaglenni'n fwy cymhleth. Mae ein gweithdrefn integral newydd, er enghraifft, yn rhoi'r gallu inni fodelu systemau â dolenni, ond rhaid inni bellach gofio y dylid galw integral ag integrand gohiriedig, a rhaid i bob gweithdrefn sy'n defnyddio integral fod yn ymwybodol o hyn. I bob pwrpas, rydym wedi creu dau ddosbarth o weithdrefnau: gweithdrefnau cyffredin a gweithdrefnau sy'n cymryd argiau gohiriedig. Yn gyffredinol, mae creu dosbarthiadau ar wahân o weithdrefnau yn ein gorfodi i greu dosbarthiadau ar wahân o weithdrefnau trefn uwch hefyd.²⁰⁰

Un ffordd o osgoi'r angen am ddau ddosbarth gwahanol o weithdrefnau yw gwneud i bob gweithdrefn gymryd argiau gohiriedig. Gallem fabwysiadu model gwerthuso lle gohirir holl argiau gweithdrefnau'n awtomatig, a lle gorfodir argiau dim ond pan fydd eu hangen mewn gwirionedd (er enghraifft, pan fydd gweithrediad cyntefig yn gofyn amdanynt). Byddai hyn yn trawsnewid ein hiaith i ddefnyddio gwerthuso yn y drefn arferol, a ddisgrifiasom gyntaf pan gyflwynasom y model amnewid ar gyfer gwerthuso yn 1.1.5. Mae trosi i werthuso yn y drefn arferol yn darparu ffordd unffurf a chain o symleiddio defnyddio gwerthuso gohiriedig, a byddai hon yn strategaeth naturiol i'w mabwysiadu pe baem yn ymwneud â phrosesu ffrydiau yn unig. Yn 4.2, ar ôl inni astudio'r gwerthusydd, gwelwn sut i drawsnewid ein hiaith yn union fel hyn. Yn anffodus, mae cynnwys gohirio mewn galwadau gweithdrefnau yn creu llanast yn ein gallu i ddylunio rhaglenni sy'n dibynnu ar drefn digwyddiadau, megis rhaglenni sy'n defnyddio aseiniad, yn newid data, neu'n cyflawni mewnbwn neu allbwn. Gall hyd yn oed yr un delay yn cons-stream achosi dryswch mawr, fel y dangosir gan Ymarfer 3.51 ac Ymarfer 3.52. Hyd y gŵyr neb, nid yw newidiadwyedd a gwerthuso gohiriedig yn cymysgu'n dda mewn ieithoedd rhaglennu, ac mae dyfeisio ffyrdd o ymdrin â'r ddau hyn ar unwaith yn faes ymchwil gweithredol.

3.5.5Modiwlaredd Rhaglenni Ffwythiannol a Modiwlaredd Gwrthrychau

Fel y gwelsom yn 3.1.2, un o brif fanteision cyflwyno aseiniad yw y gallwn gynyddu modiwlaredd ein systemau drwy amgáu, neu “guddio,” rhannau o gyflwr system fawr mewn newidynnau lleol. Gall modelau ffrydiau ddarparu modiwlaredd cyfatebol heb ddefnyddio aseiniad. I ddangos hyn, gallwn ailweithredu amcangyfrif Monte Carlo o $\mathrm{\pi <!--\; \pi \; -->}$, a archwiliasom yn 3.1.2, o safbwynt prosesu ffrydiau.

Y mater modiwlaredd allweddol oedd ein bod am guddio cyflwr mewnol generadur rhifau ar hap rhag rhaglenni a ddefnyddiai rifau ar hap. Dechreuasom â gweithdrefn rand-update, yr oedd ei gwerthoedd olynol yn darparu ein cyflenwad o rifau ar hap, a defnyddiasom hon i gynhyrchu generadur rhifau ar hap:

(define rand
  (let ((x random-init))
    (lambda ()
      (set! x (rand-update x))
      x)))

Yn y ffurfiad ffrydiau nid oes generadur rhifau ar hap fel y cyfryw, dim ond ffrwd o rifau ar hap a gynhyrchir gan alwadau olynol i rand-update:

(define random-numbers
  (cons-stream random-init
               (stream-map rand-update 
                           random-numbers)))

Defnyddiwn hyn i adeiladu ffrwd canlyniadau arbrawf Cesàro a gyflawnir ar barau olynol yn y ffrwd random-numbers:

(define cesaro-stream
  (map-successive-pairs
   (lambda (r1 r2) (= (gcd r1 r2) 1))
   random-numbers))

(define (map-successive-pairs f s)
  (cons-stream
   (f (stream-car s) 
      (stream-car (stream-cdr s)))
   (map-successive-pairs 
    f (stream-cdr (stream-cdr s)))))

Bwydir yr cesaro-stream bellach i weithdrefn monte-carlo, sy'n cynhyrchu ffrwd o amcangyfrifon tebygolrwyddau. Yna trosir y canlyniadau'n ffrwd o amcangyfrifon o $\mathrm{\pi <!--\; \pi \; -->}$. Nid oes angen paramedr sy'n nodi faint o dreialon i'w cynnal ar y fersiwn hon o'r rhaglen. Ceir amcangyfrifon gwell o $\mathrm{\pi <!--\; \pi \; -->}$ (o gynnal mwy o arbrofion) drwy edrych ymhellach i mewn i'r ffrwd pi:

(define (monte-carlo experiment-stream 
                     passed 
                     failed)
  (define (next passed failed)
    (cons-stream
     (/ passed (+ passed failed))
     (monte-carlo
      (stream-cdr experiment-stream) 
      passed 
      failed)))
  (if (stream-car experiment-stream)
      (next (+ passed 1) failed)
      (next passed (+ failed 1))))

(define pi
  (stream-map
   (lambda (p) (sqrt (/ 6 p)))
   (monte-carlo cesaro-stream 0 0)))

Mae cryn fodiwlaredd yn y dull hwn, am y gallwn o hyd lunio gweithdrefn monte-carlo gyffredinol a all ymdrin ag unrhyw arbrofion. Eto nid oes aseiniad na chyflwr lleol.

Ymarfer 3.81: Trafododd Ymarfer 3.6 gyffredinoli'r generadur rhifau ar hap i ganiatáu ailosod y dilyniant rhifau ar hap er mwyn cynhyrchu dilyniannau ailadroddadwy o rifau “ar hap.” Cynhyrchwch ffurfiad ffrydiau o'r un generadur hwn sy'n gweithredu ar ffrwd fewnbwn o geisiadau i generate rif ar hap newydd neu i reset y dilyniant i werth penodedig, ac sy'n cynhyrchu'r ffrwd o rifau ar hap a ddymunir. Peidiwch â defnyddio aseiniad yn eich datrysiad.

Ymarfer 3.82: Gwnewch Ymarfer 3.5 ar integru Monte Carlo eto yn nhermau ffrydiau. Ni fydd gan y fersiwn ffrydiau o estimate-integral arg sy'n dweud faint o dreialon i'w cynnal. Yn lle hynny, bydd yn cynhyrchu ffrwd o amcangyfrifon yn seiliedig ar fwy a mwy o dreialon.

Golwg rhaglennu ffwythiannol ar amser

Gadewch inni nawr ddychwelyd at y materion ynghylch gwrthrychau a chyflwr a godwyd ar ddechrau'r bennod hon a'u harchwilio mewn goleuni newydd. Cyflwynasom aseiniad a gwrthrychau newidiadwy i ddarparu mecanwaith ar gyfer adeiladu rhaglenni'n fodiwlaidd sy'n modelu systemau â chyflwr. Adeiladasom wrthrychau cyfrifiadurol â newidynnau cyflwr lleol a defnyddiasom aseiniad i addasu'r newidynnau hyn. Modelasom ymddygiad amserol gwrthrychau yn y byd drwy ymddygiad amserol y gwrthrychau cyfrifiadurol cyfatebol.

Nawr rydym wedi gweld bod ffrydiau'n darparu ffordd amgen o fodelu gwrthrychau â chyflwr lleol. Gallwn fodelu maint sy'n newid, megis cyflwr lleol rhyw wrthrych, gan ddefnyddio ffrwd sy'n cynrychioli hanes amser y cyflyrau olynol. Yn ei hanfod, cynrychiolwn amser yn benodol, gan ddefnyddio ffrydiau, fel ein bod yn datgysylltu amser yn ein byd efelychiedig oddi wrth y dilyniant o ddigwyddiadau sy'n digwydd yn ystod gwerthuso. Yn wir, oherwydd presenoldeb delay, efallai nad oes fawr o berthynas rhwng amser efelychiedig yn y model a threfn digwyddiadau yn ystod y gwerthuso.

Er mwyn cymharu'r ddau ddull hyn o fodelu, gadewch inni ailystyried gweithredu “prosesydd codi arian” sy'n monitro balans cyfrif banc. Yn 3.1.3 gweithredasom fersiwn symlach o brosesydd o'r fath:

(define (make-simplified-withdraw balance)
  (lambda (amount)
    (set! balance (- balance amount))
    balance))

Mae galwadau i make-simplified-withdraw yn cynhyrchu gwrthrychau cyfrifiadurol, pob un â newidyn cyflwr lleol balance sy'n cael ei leihau gan alwadau olynol i'r gwrthrych. Mae'r gwrthrych yn cymryd amount yn arg ac yn dychwelyd y balans newydd. Gallwn ddychmygu defnyddiwr cyfrif banc yn teipio dilyniant o fewnbynnau i wrthrych o'r fath ac yn arsylwi'r dilyniant o werthoedd a ddychwelir ar sgrin.

Fel arall, gallwn fodelu prosesydd codi arian fel gweithdrefn sy'n cymryd balans a ffrwd o symiau i'w codi yn fewnbwn ac yn cynhyrchu ffrwd balansau olynol y cyfrif:

(define (stream-withdraw balance amount-stream)
  (cons-stream
   balance
   (stream-withdraw 
    (- balance (stream-car amount-stream))
    (stream-cdr amount-stream))))

Mae Stream-withdraw yn gweithredu ffwythiant mathemategol wedi'i ddiffinio'n dda y mae ei fewnbwn yn pennu ei allbwn yn llwyr. Tybiwch, fodd bynnag, mai'r mewnbwn amount-stream yw ffrwd y gwerthoedd olynol a deipir gan y defnyddiwr a bod y ffrwd balansau a geir yn cael ei harddangos. Yna, o safbwynt y defnyddiwr sy'n teipio gwerthoedd ac yn gwylio canlyniadau, mae gan y broses ffrydiau yr un ymddygiad â'r gwrthrych a grëir gan make-simplified-withdraw. Fodd bynnag, gyda'r fersiwn ffrydiau, nid oes aseiniad, dim newidyn cyflwr lleol, ac o ganlyniad dim un o'r anawsterau damcaniaethol a wynebasom yn 3.1.3. Eto mae gan y system gyflwr!

Mae hyn yn rhyfeddol. Er bod stream-withdraw yn gweithredu ffwythiant mathemategol wedi'i ddiffinio'n dda nad yw ei ymddygiad yn newid, canfyddiad y defnyddiwr yma yw ei fod yn rhyngweithio â system sydd â chyflwr sy'n newid. Un ffordd o ddatrys y paradocs hwn yw sylweddoli mai bodolaeth amserol y defnyddiwr sy'n gosod cyflwr ar y system. Pe gallai'r defnyddiwr gamu'n ôl o'r rhyngweithio a meddwl yn nhermau ffrydiau o falansau yn hytrach na thrafodion unigol, byddai'r system yn ymddangos heb gyflwr.²⁰¹

O safbwynt un rhan o broses gymhleth, mae'r rhannau eraill yn ymddangos fel pe baent yn newid gydag amser. Mae ganddynt gyflwr lleol cudd sy'n amrywio dros amser. Os dymunwn ysgrifennu rhaglenni sy'n modelu'r math hwn o ddadelfeniad naturiol yn ein byd (fel y'i gwelwn o'n safbwynt fel rhan o'r byd hwnnw) â strwythurau yn ein cyfrifiadur, gwnawn wrthrychau cyfrifiadurol nad ydynt yn ffwythiannol—rhaid iddynt newid gydag amser. Modelwn gyflwr â newidynnau cyflwr lleol, a modelwn newidiadau cyflwr ag aseiniadau i'r newidynnau hynny. Drwy wneud hyn, gwnawn i amser gweithredu cyfrifiad fodelu amser yn y byd yr ydym yn rhan ohono, ac felly cawn “wrthrychau” yn ein cyfrifiadur.

Mae modelu â gwrthrychau yn bwerus ac yn reddfol, yn bennaf am ei fod yn cyd-fynd â'r canfyddiad o ryngweithio â byd yr ydym yn rhan ohono. Fodd bynnag, fel y gwelsom dro ar ôl tro drwy gydol y bennod hon, mae'r modelau hyn yn codi problemau dyrys ynghylch cyfyngu ar drefn digwyddiadau a chydamseru sawl proses. Mae'r posibilrwydd o osgoi'r problemau hyn wedi ysgogi datblygiad ieithoedd rhaglennu ffwythiannol, nad ydynt yn cynnwys unrhyw ddarpariaeth ar gyfer aseiniad na data newidiadwy. Mewn iaith o'r fath, mae pob gweithdrefn yn gweithredu ffwythiant mathemategol o'i hargiau wedi'i ddiffinio'n dda, nad yw ei ymddygiad yn newid. Mae'r dull ffwythiannol yn hynod ddeniadol ar gyfer ymdrin â systemau cydamserol.²⁰²

Ar y llaw arall, os edrychwn yn fanwl, gallwn weld problemau sy'n ymwneud ag amser yn sleifio i mewn i fodelau ffwythiannol hefyd. Mae un maes arbennig o drafferthus yn codi pan ddymunwn ddylunio systemau rhyngweithiol, yn enwedig rhai sy'n modelu rhyngweithiadau rhwng endidau annibynnol. Er enghraifft, ystyriwch unwaith eto weithredu system fancio sy'n caniatáu cyfrifon banc ar y cyd. Mewn system gonfensiynol sy'n defnyddio aseiniad a gwrthrychau, byddem yn modelu'r ffaith bod Peter a Paul yn rhannu cyfrif drwy wneud i Peter a Paul ill dau anfon eu ceisiadau trafodion at yr un gwrthrych cyfrif banc, fel y gwelsom yn 3.1.3. O safbwynt ffrydiau, lle nad oes “gwrthrychau” fel y cyfryw, rydym eisoes wedi nodi y gellir modelu cyfrif banc yn broses sy'n gweithredu ar ffrwd o geisiadau trafodion i gynhyrchu ffrwd o ymatebion. Yn unol â hynny, gallem fodelu'r ffaith bod gan Peter a Paul gyfrif banc ar y cyd drwy gyfuno ffrwd ceisiadau trafodion Peter â ffrwd ceisiadau Paul a bwydo'r canlyniad i broses ffrwd y cyfrif banc, fel y dangosir yn Ffigur 3.38.

Y drafferth gyda'r ffurfiad hwn yw'r syniad o gyfuno. Ni fydd yn ddigon cyfuno'r ddwy ffrwd drwy gymryd un cais gan Peter ac un gan Paul bob yn ail. Tybiwch mai anaml iawn y mae Paul yn cyrchu'r cyfrif. Prin y gallem orfodi Peter i aros i Paul gyrchu'r cyfrif cyn y gallai gychwyn ail drafodyn. Sut bynnag y gweithredir cyfuno o'r fath, rhaid iddo gydblethu'r ddwy ffrwd trafodion mewn rhyw ffordd a gyfyngir gan “amser real” fel y'i canfyddir gan Peter a Paul, yn yr ystyr, os bydd Peter a Paul yn cwrdd, y gallant gytuno bod rhai trafodion wedi'u prosesu cyn y cyfarfod, a thrafodion eraill wedi'u prosesu ar ôl y cyfarfod.²⁰³ Dyma'n union yr un cyfyngiad ag y bu'n rhaid inni ymdrin ag ef yn 3.4.1, lle canfuom yr angen i gyflwyno cydamseru penodol i sicrhau trefn “gywir” ar ddigwyddiadau wrth brosesu gwrthrychau â chyflwr yn gydamserol. Felly, wrth geisio cefnogi'r arddull ffwythiannol, mae'r angen i gyfuno mewnbynnau o wahanol asiantau yn ailgyflwyno'r un problemau yr oedd yr arddull ffwythiannol i fod i'w dileu.

Dechreuasom y bennod hon â'r nod o adeiladu modelau cyfrifiadurol y mae eu strwythur yn cyfateb i'n canfyddiad o'r byd go iawn rydym yn ceisio ei fodelu. Gallwn fodelu'r byd yn gasgliad o wrthrychau ar wahân, wedi'u rhwymo i amser, sy'n rhyngweithio ac sydd â chyflwr, neu gallwn fodelu'r byd yn un cyfanwaith diamser heb gyflwr. Mae gan bob safbwynt fanteision grymus, ond nid yw'r naill safbwynt na'r llall ar ei ben ei hun yn gwbl foddhaol. Nid yw uniad mawr wedi ymddangos eto.²⁰⁴