1.3 Llunio Haniaethau â Gweithdrefnau Trefn Uwch

Rydym wedi gweld mai haniaethau sy'n disgrifio gweithrediadau cyfansawdd ar rifau yn annibynnol ar y rhifau penodol yw gweithdrefnau, i bob pwrpas. Er enghraifft, pan fyddwn yn

(define (cube x) (* x x x))

nid ydym yn sôn am giwb rhif penodol, ond yn hytrach am ddull o gael ciwb unrhyw rif. Wrth gwrs, gallem ymdopi heb ddiffinio'r weithdrefn hon byth, drwy ysgrifennu mynegiadau megis

(* 3 3 3)
(* x x x)
(* y y y)

bob amser, a heb grybwyll cube yn benodol byth. Byddai hyn yn ein rhoi dan anfantais ddifrifol, gan ein gorfodi i weithio bob amser ar lefel y gweithrediadau penodol sy'n digwydd bod yn gyntefig yn yr iaith (lluosi, yn yr achos hwn) yn hytrach nag yn nhermau gweithrediadau lefel uwch. Byddai ein rhaglenni'n gallu cyfrifiannu ciwbiau, ond ni fyddai gan ein hiaith y gallu i fynegi'r cysyniad o giwbio. Un o'r pethau y dylem eu mynnu gan iaith raglennu bwerus yw'r gallu i adeiladu haniaethau drwy roi enwau i batrymau cyffredin ac yna gweithio'n uniongyrchol yn nhermau'r haniaethau. Mae gweithdrefnau'n darparu'r gallu hwn. Dyma pam mae pob iaith raglennu heblaw'r rhai mwyaf cyntefig yn cynnwys mecanweithiau ar gyfer diffinio gweithdrefnau.

Eto, hyd yn oed mewn prosesu rhifol, bydd ein gallu i greu haniaethau'n gyfyngedig iawn os cawn ein cyfyngu i weithdrefnau y mae'n rhaid i'w paramedrau fod yn rhifau. Yn aml, defnyddir yr un patrwm rhaglennu gyda nifer o weithdrefnau gwahanol. I fynegi patrymau o'r fath fel cysyniadau, bydd angen inni adeiladu gweithdrefnau sy'n gallu derbyn gweithdrefnau yn argiau neu ddychwelyd gweithdrefnau yn werthoedd. Gelwir gweithdrefnau sy'n trin gweithdrefnau yn weithdrefnau trefn uwch. Mae'r adran hon yn dangos sut y gall gweithdrefnau trefn uwch fod yn fecanweithiau haniaethu pwerus, gan gynyddu grym mynegiannol ein hiaith yn aruthrol.

1.3.1Gweithdrefnau fel Argiau

Ystyriwch y tair gweithdrefn ganlynol. Mae'r gyntaf yn cyfrifiannu swm y cyfanrifau o a hyd at ac yn cynnwys b:

(define (sum-integers a b)
  (if (> a b) 
      0 
      (+ a (sum-integers (+ a 1) b))))

Mae'r ail yn cyfrifiannu swm ciwbiau'r cyfanrifau yn yr amrediad penodol:

(define (sum-cubes a b)
  (if (> a b) 
      0 
      (+ (cube a) 
         (sum-cubes (+ a 1) b))))

Mae'r drydedd yn cyfrifiannu swm dilyniant o dermau yn y gyfres $$\frac{1}{1\cdot <!--\; \cdot \; -->3}+\frac{1}{5\cdot <!--\; \cdot \; -->7}+\frac{1}{9\cdot <!--\; \cdot \; -->11}+\dots <!--\; \dots \; -->,$$ sy'n cydgyfeirio at $\mathrm{\pi <!--\; \pi \; -->}/8$ (yn araf iawn):⁴⁹

(define (pi-sum a b)
  (if (> a b)
      0
      (+ (/ 1.0 (* a (+ a 2))) 
         (pi-sum (+ a 4) b))))

Mae'n amlwg fod y tair gweithdrefn hyn yn rhannu patrwm sylfaenol cyffredin. Maent yr un fath gan mwyaf, ac yn wahanol yn unig o ran enw'r weithdrefn, y ffwythiant o a a ddefnyddir i gyfrifiannu'r term sydd i'w adio, a'r ffwythiant sy'n darparu gwerth nesaf a. Gallem gynhyrchu pob un o'r gweithdrefnau drwy lenwi bylchau yn yr un templed:

(define (⟨name⟩ a b)
  (if (> a b)
      0
      (+ (⟨term⟩ a) 
         (⟨name⟩ (⟨next⟩ a) b))))

Mae presenoldeb patrwm cyffredin o'r fath yn dystiolaeth gref fod haniaeth ddefnyddiol yn aros i gael ei dwyn i'r wyneb. Yn wir, adnabu mathemategwyr ers talwm haniaeth symio cyfres a dyfeisiasant “nodiant sigma,” er enghraifft $$\underset{n=a}{\overset{b}{\sum <!--\; \sum \; -->}}f(n)=f(a)+\cdots <!--\; \cdots \; -->+f(b),$$ i fynegi'r cysyniad hwn. Grym nodiant sigma yw ei fod yn caniatáu i fathemategwyr ymdrin â'r cysyniad o symio ei hun, yn hytrach na dim ond symiau penodol—er enghraifft, llunio canlyniadau cyffredinol am symiau sy'n annibynnol ar y gyfres benodol sy'n cael ei symio.

Yn yr un modd, fel dylunwyr rhaglenni, hoffem i'n hiaith fod yn ddigon pwerus i'n galluogi i ysgrifennu gweithdrefn sy'n mynegi'r cysyniad o symio ei hun, yn hytrach na dim ond gweithdrefnau sy'n cyfrifiannu symiau penodol. Gallwn wneud hynny'n rhwydd yn ein hiaith weithdrefnol drwy gymryd y templed cyffredin a ddangoswyd uchod a thrawsffurfio'r “bylchau” yn baramedrau ffurfiol:

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

Sylwch fod sum yn cymryd y terfynau isaf ac uchaf a a b ynghyd â'r gweithdrefnau term a next yn argiau. Gallwn ddefnyddio sum yn union fel unrhyw weithdrefn arall. Er enghraifft, gallwn ei defnyddio (ynghyd â gweithdrefn inc sy'n cynyddu ei harg 1) i ddiffinio sum-cubes:

(define (inc n) (+ n 1))

(define (sum-cubes a b)
  (sum cube a inc b))

Gan ddefnyddio hyn, gallwn gyfrifiannu swm ciwbiau'r cyfanrifau o 1 i 10:

(sum-cubes 1 10)
3025

Gyda chymorth gweithdrefn unfathiant i gyfrifiannu'r term, gallwn ddiffinio sum-integers yn nhermau sum:

(define (identity x) x)

(define (sum-integers a b)
  (sum identity a inc b))

Yna gallwn adio'r cyfanrifau o 1 i 10:

(sum-integers 1 10)
55

Gallwn hefyd ddiffinio pi-sum yn yr un modd:⁵⁰

(define (pi-sum a b)
  (define (pi-term x)
    (/ 1.0 (* x (+ x 2))))
  (define (pi-next x)
    (+ x 4))
  (sum pi-term a pi-next b))

Gan ddefnyddio'r gweithdrefnau hyn, gallwn gyfrifiannu brasamcan o $\mathrm{\pi <!--\; \pi \; -->}$:

(* 8 (pi-sum 1 1000))
3.139592655589783

Unwaith y bydd gennym sum, gallwn ei defnyddio fel bloc adeiladu wrth lunio cysyniadau pellach. Er enghraifft, gellir brasamcanu integryn pendant ffwythiant $f$ rhwng y terfynau $a$ ac $b$ yn rhifiadol drwy ddefnyddio'r fformiwla $${\int <!--\; \int \; -->}_a^{b}f=[f(a+\frac{dx}{2})+f(a+dx+\frac{dx}{2})+f(a+2dx+\frac{dx}{2})+\dots <!--\; \dots \; -->]dx$$ ar gyfer gwerthoedd bach o $dx$. Gallwn fynegi hyn yn uniongyrchol fel gweithdrefn:

(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b) 
     dx))

(integral cube 0 1 0.01)
.24998750000000042

(integral cube 0 1 0.001)
.249999875000001

(Gwerth union integryn cube rhwng 0 ac 1 yw 1/4.)

Ymarfer 1.29: Mae Rheol Simpson yn ddull integru rhifiadol mwy cywir na'r dull a ddangoswyd uchod. Gan ddefnyddio Rheol Simpson, brasamcanir integryn ffwythiant $f$ rhwng $a$ ac $b$ fel $$\frac{h}{3}(y_0+4y_1+2y_2+4y_3+2y_4+\cdots <!--\; \cdots \; -->+2y_{n-<!--\; -\; -->2}+4y_{n-<!--\; -\; -->1}+y_n),$$ lle mae $h=(b-<!--\; -\; -->a)/n$, ar gyfer rhyw eilrif $n$, ac $y_k=f(a+kh)$. (Mae cynyddu $n$ yn cynyddu cywirdeb y brasamcan.) Diffiniwch weithdrefn sy'n cymryd $f$, $a$, $b$, ac $n$ yn argiau ac yn dychwelyd gwerth yr integryn, wedi'i gyfrifiannu drwy Reol Simpson. Defnyddiwch eich gweithdrefn i integru cube rhwng 0 ac 1 (gydag $n=100$ ac $n=1000$), a chymharwch y canlyniadau â rhai'r weithdrefn integral a ddangoswyd uchod.

Ymarfer 1.30: Mae'r weithdrefn sum uchod yn cynhyrchu dychweliad llinol. Gellir ailysgrifennu'r weithdrefn fel bod y swm yn cael ei gyflawni drwy iteru. Dangoswch sut i wneud hyn drwy lenwi'r mynegiadau coll yn y diffiniad canlynol:

(define (sum term a next b)
  (define (iter a result)
    (if ⟨??⟩
        ⟨??⟩
        (iter ⟨??⟩ ⟨??⟩)))
  (iter ⟨??⟩ ⟨??⟩))

Ymarfer 1.31:

1. Y weithdrefn sum yw'r symlaf yn unig o nifer enfawr o haniaethau tebyg y gellir eu mynegi fel gweithdrefnau trefn uwch.⁵¹ Ysgrifennwch weithdrefn gyfatebol o'r enw product sy'n dychwelyd lluoswm gwerthoedd ffwythiant ar bwyntiau dros amrediad penodol. Dangoswch sut i ddiffinio factorial yn nhermau product. Defnyddiwch product hefyd i gyfrifiannu brasamcanion o $\mathrm{\pi <!--\; \pi \; -->}$ drwy'r fformiwla⁵² $$\frac{\mathrm{\pi <!--\; \pi \; -->}}{4}=\frac{2\cdot <!--\; \cdot \; -->4\cdot <!--\; \cdot \; -->4\cdot <!--\; \cdot \; -->6\cdot <!--\; \cdot \; -->6\cdot <!--\; \cdot \; -->8\cdot <!--\; \cdot \; -->\cdots <!--\; \cdots \; -->}{3\cdot <!--\; \cdot \; -->3\cdot <!--\; \cdot \; -->5\cdot <!--\; \cdot \; -->5\cdot <!--\; \cdot \; -->7\cdot <!--\; \cdot \; -->7\cdot <!--\; \cdot \; -->\cdots <!--\; \cdots \; -->}.$$
2. Os yw eich gweithdrefn product yn cynhyrchu proses ddychweliadol, ysgrifennwch un sy'n cynhyrchu proses iteru. Os yw'n cynhyrchu proses iteru, ysgrifennwch un sy'n cynhyrchu proses ddychweliadol.

Ymarfer 1.32:

1. Dangoswch fod sum ac product (Ymarfer 1.31) ill dau yn achosion arbennig o syniad mwy cyffredinol fyth o'r enw accumulate sy'n cyfuno casgliad o dermau, gan ddefnyddio rhyw ffwythiant cronni cyffredinol:

   (accumulate 
    combiner null-value term a next b)

   Mae Accumulate yn cymryd yr un manylebau termau ac amrediad ag sum ac product yn argiau, ynghyd â gweithdrefn combiner (â dau arg) sy'n pennu sut y dylid cyfuno'r term cyfredol â chroniad y termau blaenorol, ac null-value sy'n pennu pa werth sylfaenol i'w ddefnyddio pan na fydd termau ar ôl. Ysgrifennwch accumulate a dangoswch sut y gellir diffinio sum ac product ill dau fel galwadau syml i accumulate.

2. Os yw eich gweithdrefn accumulate yn cynhyrchu proses ddychweliadol, ysgrifennwch un sy'n cynhyrchu proses iteru. Os yw'n cynhyrchu proses iteru, ysgrifennwch un sy'n cynhyrchu proses ddychweliadol.

Ymarfer 1.33: Gallwch gael fersiwn fwy cyffredinol fyth o accumulate (Ymarfer 1.32) drwy gyflwyno'r syniad o hidlydd ar y termau sydd i'w cyfuno. Hynny yw, cyfuno dim ond y termau hynny sy'n deillio o werthoedd yn yr amrediad sy'n bodloni amod penodol. Mae'r haniaeth filtered-accumulate sy'n deillio o hyn yn cymryd yr un argiau ag accumulate, ynghyd â thraethiad ychwanegol ag un arg sy'n pennu'r hidlydd. Ysgrifennwch filtered-accumulate fel gweithdrefn. Dangoswch sut i fynegi'r canlynol gan ddefnyddio filtered-accumulate:

1. swm sgwariau'r rhifau cysefin yn y cyfwng $a$ i $b$ (gan dybio bod gennych draethiad prime? wedi'i ysgrifennu eisoes)
2. lluoswm yr holl gyfanrifau positif sy'n llai nag $n$ ac sy'n gyd-gysefin ag $n$ (h.y., pob cyfanrif positif $i<n$ fel bod $\text{GCD}(i,n)=1$).

1.3.2Adeiladu Gweithdrefnau drwy Ddefnyddio Lambda

Wrth ddefnyddio sum fel yn 1.3.1, mae'n ymddangos yn drwsgl iawn gorfod diffinio gweithdrefnau dibwys megis pi-term ac pi-next dim ond er mwyn eu defnyddio yn argiau i'n gweithdrefn trefn uwch. Yn hytrach na diffinio pi-next ac pi-term, byddai'n fwy cyfleus cael ffordd o bennu'n uniongyrchol “y weithdrefn sy'n dychwelyd ei mewnbwn wedi'i gynyddu 4” a “y weithdrefn sy'n dychwelyd cilydd lluoswm ei mewnbwn a'i mewnbwn ynghyd â 2.” Gallwn wneud hyn drwy gyflwyno'r ffurf arbennig lambda, sy'n creu gweithdrefnau. Gan ddefnyddio lambda gallwn ddisgrifio'r hyn a ddymunwn fel

(lambda (x) (+ x 4))

a

(lambda (x) (/ 1.0 (* x (+ x 2))))

Yna gellir mynegi ein gweithdrefn pi-sum heb ddiffinio unrhyw weithdrefnau ategol fel

(define (pi-sum a b)
  (sum (lambda (x) (/ 1.0 (* x (+ x 2))))
       a
       (lambda (x) (+ x 4))
       b))

Gan ddefnyddio lambda eto, gallwn ysgrifennu'r weithdrefn integral heb orfod diffinio'r weithdrefn ategol add-dx:

(define (integral f a b dx)
  (* (sum f (+ a (/ dx 2.0))
            (lambda (x) (+ x dx))
            b)
     dx))

Yn gyffredinol, defnyddir lambda i greu gweithdrefnau yn yr un modd ag define, heblaw na phennir enw ar gyfer y weithdrefn:

(lambda (⟨formal-parameters⟩) ⟨body⟩)

Mae'r weithdrefn sy'n deillio o hyn yn weithdrefn lawn cymaint ag un a grëir drwy ddefnyddio define. Yr unig wahaniaeth yw nad yw wedi'i chysylltu ag unrhyw enw yn yr amgylchedd. Yn wir, mae

(define (plus4 x) (+ x 4))

yn gyfwerth â

(define plus4 (lambda (x) (+ x 4)))

Gallwn ddarllen mynegiad lambda fel a ganlyn:

(lambda                     (x)     (+   x     4))

y weithdrefn ag arg x sy’n adio x a 4

Fel unrhyw fynegiad sydd â gweithdrefn yn werth iddo, gellir defnyddio mynegiad lambda fel y gweithredydd mewn cyfuniad megis

((lambda (x y z) (+ x y (square z))) 1 2 3)
12

neu, yn fwy cyffredinol, mewn unrhyw gyd-destun lle byddem fel arfer yn defnyddio enw gweithdrefn.⁵³

Defnyddio let i greu newidynnau lleol

Defnydd arall o lambda yw creu newidynnau lleol. Yn aml mae angen newidynnau lleol yn ein gweithdrefnau heblaw'r rhai a rwymwyd fel paramedrau ffurfiol. Er enghraifft, tybiwch ein bod am gyfrifiannu'r ffwythiant $$f(x,y)=x(1+xy{)}^2+y(1-<!--\; -\; -->y)+(1+xy)(1-<!--\; -\; -->y),$$ y gallem hefyd ei fynegi fel $$\begin{array}{rcl}a& =& 1+xy,\\ \phantom{(x,y)}b& =& 1-<!--\; -\; -->y,\\ f(x,y)& =& x{a}^2+yb+ab.\end{array}$$ Wrth ysgrifennu gweithdrefn i gyfrifiannu $f$, hoffem gynnwys yn newidynnau lleol nid yn unig $x$ ac $y$ ond hefyd enwau meintiau canolradd megis $a$ ac $b$. Un ffordd o gyflawni hyn yw defnyddio gweithdrefn ategol i rwymo'r newidynnau lleol:

(define (f x y)
  (define (f-helper a b)
    (+ (* x (square a))
       (* y b)
       (* a b)))
  (f-helper (+ 1 (* x y)) 
            (- 1 y)))

Wrth gwrs, gallem ddefnyddio mynegiad lambda i bennu gweithdrefn ddienw ar gyfer rhwymo ein newidynnau lleol. Yna mae corff f yn dod yn un alwad i'r weithdrefn honno:

(define (f x y)
  ((lambda (a b)
     (+ (* x (square a)) 
        (* y b) 
        (* a b)))
   (+ 1 (* x y))
   (- 1 y)))

Mae'r gystrawen hon mor ddefnyddiol fel bod ffurf arbennig o'r enw let i wneud ei defnyddio'n fwy cyfleus. Gan ddefnyddio let, gellid ysgrifennu'r weithdrefn f fel

(define (f x y)
  (let ((a (+ 1 (* x y)))
        (b (- 1 y)))
    (+ (* x (square a))
       (* y b)
       (* a b))))

Ffurf gyffredinol mynegiad let yw

(let ((⟨var₁⟩ ⟨exp₁⟩)
      (⟨var₂⟩ ⟨exp₂⟩)
      …
      (⟨varₙ⟩ ⟨expₙ⟩))
  ⟨body⟩)

y gellir meddwl amdani fel pe bai'n dweud

let ⟨var₁⟩ â’r gwerth ⟨exp₁⟩ ac
    ⟨var₂⟩ â’r gwerth ⟨exp₂⟩ ac
…
    ⟨varₙ⟩ â’r gwerth ⟨expₙ⟩
  yn ⟨body⟩

Rhan gyntaf y mynegiad let yw rhestr o barau enw–mynegiad. Wrth werthuso'r let, cysylltir pob enw â gwerth y mynegiad cyfatebol. Gwerthusir corff y let gyda'r enwau hyn wedi'u rhwymo fel newidynnau lleol. Mae hyn yn digwydd drwy ddehongli'r mynegiad let fel cystrawen amgen ar gyfer

((lambda (⟨var₁⟩ … ⟨varₙ⟩)
   ⟨body⟩)
 ⟨exp₁⟩
 …
 ⟨expₙ⟩)

Nid oes angen unrhyw fecanwaith newydd yn y dehonglydd er mwyn darparu newidynnau lleol. Yn syml, siwgr cystrawennol ar gyfer y cymhwysiad lambda sylfaenol yw mynegiad let.

Gallwn weld o'r cywerthedd hwn mai corff y let yw cwmpas newidyn a bennir gan fynegiad let. Mae hyn yn awgrymu:

• Mae Let yn caniatáu rhwymo newidynnau mor lleol â phosibl i'r man lle cânt eu defnyddio. Er enghraifft, os mai 5 yw gwerth x, gwerth y mynegiad

  (+ (let ((x 3))
       (+ x (* x 10)))
     x)

  yw 38. Yma, 3 yw'r x yng nghorff y let, felly gwerth y mynegiad let yw 33. Ar y llaw arall, mae'r x sy'n ail arg i'r + mwyaf allanol yn dal yn 5.

• Cyfrifiannir gwerthoedd y newidynnau y tu allan i'r let. Mae hyn o bwys pan fydd y mynegiadau sy'n darparu gwerthoedd y newidynnau lleol yn dibynnu ar newidynnau sydd â'r un enwau â'r newidynnau lleol eu hunain. Er enghraifft, os mai 2 yw gwerth x, bydd gan y mynegiad

  (let ((x 3)
        (y (+ x 2)))
    (* x y))

  y gwerth 12 oherwydd, y tu mewn i gorff y let, bydd x yn 3 ac y yn 4 (sef yr x allanol ynghyd â 2).

Weithiau gallwn ddefnyddio diffiniadau mewnol i gael yr un effaith â let. Er enghraifft, gallem fod wedi diffinio'r weithdrefn f uchod fel

(define (f x y)
  (define a 
    (+ 1 (* x y)))
  (define b (- 1 y))
  (+ (* x (square a))
     (* y b)
     (* a b)))

Fodd bynnag, mae'n well gennym ddefnyddio let mewn sefyllfaoedd fel hyn, a defnyddio define mewnol ar gyfer gweithdrefnau mewnol yn unig.⁵⁴

Ymarfer 1.34: Tybiwch ein bod yn diffinio'r weithdrefn

(define (f g) (g 2))

Yna mae gennym

(f square)
4

(f (lambda (z) (* z (+ z 1))))
6

Beth sy'n digwydd os gofynnwn (yn wrthnysig) i'r dehonglydd werthuso'r cyfuniad (f f)? Eglurwch.

1.3.3Gweithdrefnau fel Dulliau Cyffredinol

Cyflwynasom weithdrefnau cyfansawdd yn 1.1.4 fel mecanwaith ar gyfer haniaethu patrymau gweithrediadau rhifol er mwyn eu gwneud yn annibynnol ar y rhifau penodol dan sylw. Gyda gweithdrefnau trefn uwch, megis gweithdrefn integral 1.3.1, dechreuasom weld math mwy pwerus o haniaethu: defnyddio gweithdrefnau i fynegi dulliau cyfrifiannu cyffredinol, yn annibynnol ar y ffwythiannau penodol dan sylw. Yn yr adran hon trafodwn ddwy enghraifft fwy cymhleth—dulliau cyffredinol ar gyfer canfod seroau a phwyntiau sefydlog ffwythiannau—a dangoswn sut y gellir mynegi'r dulliau hyn yn uniongyrchol fel gweithdrefnau.

Canfod gwreiddiau hafaliadau drwy'r dull hanner cyfwng

Mae'r dull hanner cyfwng yn dechneg syml ond pwerus ar gyfer canfod gwreiddiau hafaliad $f(x)=0$, lle mae $f$ yn ffwythiant di-dor. Y syniad yw, os rhoddir inni bwyntiau $a$ ac $b$ fel bod $f(a)<0<f(b)$, yna bod yn rhaid i $f$ fod ag o leiaf un sero rhwng $a$ ac $b$. I leoli sero, gosodwch $x$ yn gyfartaledd $a$ ac $b$, a chyfrifiannwch $f(x)$. Os yw $f(x)>0$, yna rhaid i $f$ fod â sero rhwng $a$ ac $x$. Os yw $f(x)<0$, yna rhaid i $f$ fod â sero rhwng $x$ ac $b$. Drwy barhau fel hyn, gallwn adnabod cyfyngau llai a llai y mae'n rhaid i $f$ fod â sero ynddynt. Pan gyrhaeddwn bwynt lle mae'r cyfwng yn ddigon bach, mae'r broses yn stopio. Gan fod cyfwng yr ansicrwydd yn cael ei haneru ar bob cam o'r broses, mae nifer y camau sydd eu hangen yn tyfu fel $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->(L/T))$, lle mai $L$ yw hyd y cyfwng gwreiddiol ac $T$ yw'r goddefiant gwall (hynny yw, maint y cyfwng y byddwn yn ei ystyried yn “ddigon bach”). Dyma weithdrefn sy'n gweithredu'r strategaeth hon:

(define (search f neg-point pos-point)
  (let ((midpoint 
         (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond 
           ((positive? test-value)
            (search f neg-point midpoint))
           ((negative? test-value)
            (search f midpoint pos-point))
           (else midpoint))))))

Tybiwn ein bod yn cael y ffwythiant $f$ ar y dechrau ynghyd â phwyntiau lle mae ei werthoedd yn negatif ac yn bositif. Cyfrifiannwn ganolbwynt y ddau bwynt a roddwyd yn gyntaf. Yna gwiriwn a yw'r cyfwng a roddwyd yn ddigon bach, ac os ydyw, dychwelwn y canolbwynt fel ein hateb. Fel arall, cyfrifiannwn werth $f$ yn y canolbwynt fel gwerth prawf. Os yw'r gwerth prawf yn bositif, parhawn â'r broses gyda chyfwng newydd sy'n rhedeg o'r pwynt negatif gwreiddiol i'r canolbwynt. Os yw'r gwerth prawf yn negatif, parhawn â'r cyfwng o'r canolbwynt i'r pwynt positif. Yn olaf, mae'n bosibl mai 0 yw'r gwerth prawf; yn yr achos hwnnw, y canolbwynt ei hun yw'r gwreiddyn yr ydym yn chwilio amdano.

I brofi a yw'r pwyntiau terfyn yn “ddigon agos,” gallwn ddefnyddio gweithdrefn debyg i'r un a ddefnyddiwyd yn 1.1.7 ar gyfer cyfrifiannu gwreiddiau sgwâr:⁵⁵

(define (close-enough? x y) 
  (< (abs (- x y)) 0.001))

Mae Search yn lletchwith i'w defnyddio'n uniongyrchol, oherwydd gallwn roi iddi ar ddamwain bwyntiau lle nad oes gan werthoedd $f$ yr arwydd gofynnol; yn yr achos hwnnw cawn ateb anghywir. Yn hytrach, byddwn yn defnyddio search drwy'r weithdrefn ganlynol, sy'n gwirio pa un o'r pwyntiau terfyn sydd â gwerth ffwythiant negatif a pha un sydd â gwerth positif, ac yn galw'r weithdrefn search yn unol â hynny. Os oes gan y ffwythiant yr un arwydd ar y ddau bwynt a roddwyd, ni ellir defnyddio'r dull hanner cyfwng, ac yn yr achos hwnnw mae'r weithdrefn yn rhoi signal gwall.⁵⁶

(define (half-interval-method f a b)
  (let ((a-value (f a))
        (b-value (f b)))
    (cond ((and (negative? a-value) 
                (positive? b-value))
           (search f a b))
          ((and (negative? b-value) 
                (positive? a-value))
           (search f b a))
          (else
           (error "Values are not of 
                   opposite sign" a b)))))

Mae'r enghraifft ganlynol yn defnyddio'r dull hanner cyfwng i frasamcanu $\mathrm{\pi <!--\; \pi \; -->}$ fel gwreiddyn $\sin <!--\; \; -->x=0$ rhwng 2 a 4:

(half-interval-method sin 2.0 4.0)
3.14111328125

Dyma enghraifft arall, sy'n defnyddio'r dull hanner cyfwng i chwilio am wreiddyn yr hafaliad $x^3-<!--\; -\; -->2x-<!--\; -\; -->3=0$ rhwng 1 a 2:

(half-interval-method 
 (lambda (x) (- (* x x x) (* 2 x) 3))
 1.0
 2.0)
1.89306640625

Canfod pwyntiau sefydlog ffwythiannau

Gelwir rhif $x$ yn bwynt sefydlog ffwythiant $f$ os yw $x$ yn bodloni'r hafaliad $f(x)=x$. Ar gyfer rhai ffwythiannau $f$, gallwn leoli pwynt sefydlog drwy ddechrau â dyfaliad cychwynnol a chymhwyso $f$ dro ar ôl tro, $$f(x),f(f(x)),f(f(f(x))),\dots <!--\; \dots \; -->,$$ nes nad yw'r gwerth yn newid rhyw lawer. Gan ddefnyddio'r syniad hwn, gallwn ddyfeisio gweithdrefn fixed-point sy'n cymryd ffwythiant a dyfaliad cychwynnol yn fewnbynnau ac yn cynhyrchu brasamcan o bwynt sefydlog y ffwythiant. Cymhwyswn y ffwythiant dro ar ôl tro nes canfod dau werth olynol y mae eu gwahaniaeth yn llai na rhyw oddefiant penodedig:

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) 
       tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

Er enghraifft, gallwn ddefnyddio'r dull hwn i frasamcanu pwynt sefydlog y ffwythiant cosin, gan ddechrau ag 1 fel brasamcan cychwynnol:⁵⁷

(fixed-point cos 1.0)
.7390822985224023

Yn yr un modd, gallwn ganfod datrysiad i'r hafaliad $y=\sin <!--\; \; -->y+\cos <!--\; \; -->y$:

(fixed-point (lambda (y) (+ (sin y) (cos y)))
             1.0)
1.2587315962971173

Mae'r broses pwynt sefydlog yn ein hatgoffa o'r broses a ddefnyddiasom i ganfod gwreiddiau sgwâr yn 1.1.7. Mae'r ddwy'n seiliedig ar y syniad o wella dyfaliad dro ar ôl tro nes bod y canlyniad yn bodloni rhyw faen prawf. Yn wir, gallwn lunio'r cyfrifiad gwreiddyn sgwâr yn rhwydd fel chwiliad am bwynt sefydlog. Mae cyfrifiannu gwreiddyn sgwâr rhyw rif $x$ yn gofyn am ganfod $y$ fel bod $y^2=x$. Drwy roi'r hafaliad hwn yn y ffurf gyfwerth $y=x/y$, sylweddolwn ein bod yn chwilio am bwynt sefydlog y ffwythiant⁵⁸ $y\mapsto <!--\; \mapsto \; -->x/y$, ac felly gallwn geisio cyfrifiannu gwreiddiau sgwâr fel

(define (sqrt x)
  (fixed-point (lambda (y) (/ x y))
               1.0))

Yn anffodus, nid yw'r chwiliad hwn am bwynt sefydlog yn cydgyfeirio. Ystyriwch ddyfaliad cychwynnol $y_1$. Y dyfaliad nesaf yw $y_2=x/y_1$ a'r dyfaliad wedyn yw $y_3=x/y_2=x/(x/y_1)=y_1$. Mae hyn yn arwain at ddolen anfeidraidd lle mae'r ddau ddyfaliad $y_1$ ac $y_2$ yn ailadrodd dro ar ôl tro, gan osgiliadu o amgylch yr ateb.

Un ffordd o reoli osgiliadau o'r fath yw atal y dyfaliadau rhag newid cymaint. Gan fod yr ateb bob amser rhwng ein dyfaliad $y$ ac $x/y$, gallwn wneud dyfaliad newydd nad yw mor bell o $y$ ag $x/y$ drwy gymryd cyfartaledd $y$ ac $x/y$, fel mai $\frac{1}{2}(y+x/y)$ yn lle $x/y$ yw'r dyfaliad nesaf ar ôl $y$. Y broses o wneud dilyniant o ddyfaliadau o'r fath yn syml yw'r broses o chwilio am bwynt sefydlog $y\mapsto <!--\; \mapsto \; -->\frac{1}{2}(y+x/y)$:

(define (sqrt x)
  (fixed-point 
   (lambda (y) (average y (/ x y)))
   1.0))

(Sylwch fod $y=\frac{1}{2}(y+x/y)$ yn drawsffurfiad syml o'r hafaliad $y=x/y;$; i'w ddeillio, ychwanegwch $y$ at ddwy ochr yr hafaliad a rhannwch â 2.)

Gyda'r addasiad hwn, mae'r weithdrefn gwreiddyn sgwâr yn gweithio. Yn wir, os dadblethwn y diffiniadau, gallwn weld bod y dilyniant o frasamcanion o'r gwreiddyn sgwâr a gynhyrchir yma yn union yr un fath â'r un a gynhyrchwyd gan ein gweithdrefn gwreiddyn sgwâr wreiddiol yn 1.1.7. Yn aml, mae'r dull hwn o gyfartaleddu brasamcanion olynol o ddatrysiad, sef techneg a alwn yn ddampio drwy gyfartaleddu, yn helpu chwiliadau am bwyntiau sefydlog i gydgyfeirio.

Ymarfer 1.35: Dangoswch fod y gymhareb aur $\mathrm{\phi <!--\; \phi \; -->}$ (1.2.2) yn bwynt sefydlog y trawsffurfiad $x\mapsto <!--\; \mapsto \; -->1+1/x$, a defnyddiwch y ffaith hon i gyfrifiannu $\mathrm{\phi <!--\; \phi \; -->}$ drwy'r weithdrefn fixed-point.

Ymarfer 1.36: Addaswch fixed-point fel ei bod yn argraffu'r dilyniant o frasamcanion y mae'n eu cynhyrchu, gan ddefnyddio'r gweithdrefnau cyntefig newline ac display a ddangosir yn Ymarfer 1.22. Yna canfyddwch ddatrysiad i $x^x=1000$ drwy ganfod pwynt sefydlog $x\mapsto <!--\; \mapsto \; -->\log <!--\; \; -->(1000)/\log <!--\; \; -->(x)$. (Defnyddiwch weithdrefn gyntefig log Scheme, sy'n cyfrifiannu logarithmau naturiol.) Cymharwch nifer y camau y mae hyn yn eu cymryd gyda dampio drwy gyfartaleddu a hebddo. (Sylwch na allwch ddechrau fixed-point â dyfaliad o 1, gan y byddai hyn yn achosi rhannu â $\log <!--\; \; -->(1)=0$.)

Ymarfer 1.37:

1. Mynegiad o'r ffurf $$f=\frac{N_1}{D_1+\frac{N_2}{D_2+\frac{N_3}{D_3+\dots <!--\; \dots \; -->}}}.$$ yw ffracsiwn parhaus anfeidraidd. Er enghraifft, gellir dangos bod yr ehangiad ffracsiwn parhaus anfeidraidd lle mae'r $N_i$ a'r $D_i$ i gyd yn hafal i 1 yn cynhyrchu $1/\mathrm{\phi <!--\; \phi \; -->}$, lle mai $\mathrm{\phi <!--\; \phi \; -->}$ yw'r gymhareb aur (a ddisgrifir yn 1.2.2). Un ffordd o frasamcanu ffracsiwn parhaus anfeidraidd yw tocio'r ehangiad ar ôl nifer penodol o dermau. Mae gan docio o'r fath—sef ffracsiwn parhaus meidraidd ffracsiwn parhaus meidraidd o k term—y ffurf $$\frac{N_1}{D_1+\frac{N_2}{\ddots <!--\; \ddots \; -->+\frac{N_k}{D_k}}}.$$ Tybiwch fod n ac d yn weithdrefnau ag un arg (mynegai'r term $i$) sy'n dychwelyd $N_i$ ac $D_i$ termau'r ffracsiwn parhaus. Diffiniwch weithdrefn cont-frac fel bod gwerthuso (cont-frac n d k) yn cyfrifiannu gwerth y ffracsiwn parhaus meidraidd o $k$ term. Gwiriwch eich gweithdrefn drwy frasamcanu $1/\mathrm{\phi <!--\; \phi \; -->}$ gan ddefnyddio

   (cont-frac (lambda (i) 1.0)
              (lambda (i) 1.0)
              k)

   ar gyfer gwerthoedd olynol k. Pa mor fawr y mae'n rhaid gwneud k er mwyn cael brasamcan sy'n gywir i 4 lle degol?

2. Os yw eich gweithdrefn cont-frac yn cynhyrchu proses ddychweliadol, ysgrifennwch un sy'n cynhyrchu proses iteru. Os yw'n cynhyrchu proses iteru, ysgrifennwch un sy'n cynhyrchu proses ddychweliadol.

Ymarfer 1.38: Ym 1737, cyhoeddodd y mathemategydd Swisaidd Leonhard Euler draethawd De Fractionibus Continuis, a oedd yn cynnwys ehangiad ffracsiwn parhaus ar gyfer $e-<!--\; -\; -->2$, lle mai $e$ yw bôn y logarithmau naturiol. Yn y ffracsiwn hwn, mae'r $N_i$ i gyd yn 1, a'r $D_i$ yn olynol yn 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, …. Ysgrifennwch raglen sy'n defnyddio eich gweithdrefn cont-frac o Ymarfer 1.37 i frasamcanu $e$, yn seiliedig ar ehangiad Euler.

Ymarfer 1.39: Cyhoeddwyd cynrychiolaeth ffracsiwn parhaus o'r ffwythiant tangiad ym 1770 gan y mathemategydd Almaenig J.H. Lambert: $$\tan <!--\; \; -->x=\frac{x}{1-<!--\; -\; -->\frac{x^2}{3-<!--\; -\; -->\frac{x^2}{5-<!--\; -\; -->\dots <!--\; \dots \; -->}}},$$ lle mae $x$ mewn radianau. Diffiniwch weithdrefn (tan-cf x k) sy'n cyfrifiannu brasamcan o'r ffwythiant tangiad yn seiliedig ar fformiwla Lambert. Mae k yn pennu nifer y termau i'w cyfrifiannu, fel yn Ymarfer 1.37.

1.3.4Gweithdrefnau fel Gwerthoedd a Ddychwelir

Mae'r enghreifftiau uchod yn dangos sut mae'r gallu i drosglwyddo gweithdrefnau yn argiau yn gwella grym mynegiannol ein hiaith raglennu yn sylweddol. Gallwn gael mwy fyth o rym mynegiannol drwy greu gweithdrefnau y mae'r gwerthoedd a ddychwelant eu hunain yn weithdrefnau.

Gallwn ddangos y syniad hwn drwy edrych eto ar yr enghraifft pwynt sefydlog a ddisgrifiwyd ar ddiwedd 1.3.3. Lluniasom fersiwn newydd o'r weithdrefn gwreiddyn sgwâr fel chwiliad am bwynt sefydlog, gan ddechrau â'r sylw fod $\sqrt{x}$ yn bwynt sefydlog y ffwythiant $y\mapsto <!--\; \mapsto \; -->x/y$. Yna defnyddiasom ddampio drwy gyfartaleddu i beri i'r brasamcanion gydgyfeirio. Mae dampio drwy gyfartaleddu yn dechneg gyffredinol ddefnyddiol ynddi ei hun. Sef, o gael ffwythiant $f$, ystyriwn y ffwythiant y mae ei werth ar $x$ yn hafal i gyfartaledd $x$ ac $f(x)$.

Gallwn fynegi'r syniad o ddampio drwy gyfartaleddu drwy'r weithdrefn ganlynol:

(define (average-damp f)
  (lambda (x) 
    (average x (f x))))

Gweithdrefn yw Average-damp sy'n cymryd gweithdrefn f yn arg ac yn dychwelyd gweithdrefn yn werth (a gynhyrchir gan y lambda) sydd, o'i chymhwyso i rif x, yn cynhyrchu cyfartaledd x ac (f x). Er enghraifft, mae cymhwyso average-damp i'r weithdrefn square yn cynhyrchu gweithdrefn y mae ei gwerth ar ryw rif $x$ yn gyfartaledd $x$ ac $x^2$. Mae cymhwyso'r weithdrefn hon i 10 yn dychwelyd cyfartaledd 10 a 100, sef 55:⁵⁹

((average-damp square) 10)
55

Gan ddefnyddio average-damp, gallwn ail-lunio'r weithdrefn gwreiddyn sgwâr fel a ganlyn:

(define (sqrt x)
  (fixed-point 
   (average-damp 
    (lambda (y) (/ x y)))
   1.0))

Sylwch sut mae'r ffurf hon yn gwneud y tri syniad yn y dull yn eglur: chwilio am bwynt sefydlog, dampio drwy gyfartaleddu, a'r ffwythiant $y\mapsto <!--\; \mapsto \; -->x/y$. Mae'n addysgiadol cymharu'r ffurf hon ar y dull gwreiddyn sgwâr â'r fersiwn wreiddiol a roddwyd yn 1.1.7. Cofiwch fod y gweithdrefnau hyn yn mynegi'r un broses, a sylwch gymaint cliriach y daw'r syniad pan fynegwn y broses yn nhermau'r haniaethau hyn. Yn gyffredinol, mae llawer o ffyrdd o lunio proses fel gweithdrefn. Mae rhaglenwyr profiadol yn gwybod sut i ddewis ffurfiau gweithdrefnol sy'n arbennig o glir, a lle amlygir elfennau defnyddiol o'r broses fel endidau ar wahân y gellir eu hailddefnyddio mewn cymwysiadau eraill. Fel enghraifft syml o ailddefnyddio, sylwch fod gwreiddyn ciwb $x$ yn bwynt sefydlog y ffwythiant $y\mapsto <!--\; \mapsto \; -->x/y^2$, felly gallwn gyffredinoli ein gweithdrefn gwreiddyn sgwâr ar unwaith i un sy'n echdynnu gwreiddiau ciwb:⁶⁰

(define (cube-root x)
  (fixed-point 
   (average-damp 
    (lambda (y) 
      (/ x (square y))))
   1.0))

Dull Newton

Pan gyflwynasom y weithdrefn gwreiddyn sgwâr gyntaf, yn 1.1.7, soniasom mai achos arbennig o ddull Newton oedd hon. Os yw $x\mapsto <!--\; \mapsto \; -->g(x)$ yn ffwythiant differadwy, yna mae datrysiad yr hafaliad $g(x)=0$ yn bwynt sefydlog y ffwythiant $x\mapsto <!--\; \mapsto \; -->f(x)$ lle mae $$f(x)=x-<!--\; -\; -->\frac{g(x)}{Dg(x)}$$ ac mae $Dg(x)$ yn ddeilliad $g$ wedi'i werthuso ar $x$. Dull Newton yw defnyddio'r dull pwynt sefydlog a welsom uchod i frasamcanu datrysiad yr hafaliad drwy ganfod pwynt sefydlog y ffwythiant $f$.⁶¹

Ar gyfer llawer o ffwythiannau $g$ a dyfaliadau cychwynnol digon da ar gyfer $x$, mae dull Newton yn cydgyfeirio'n gyflym iawn at ddatrysiad $g(x)=0$.⁶²

Er mwyn gweithredu dull Newton fel gweithdrefn, rhaid inni fynegi'r syniad o ddeilliad yn gyntaf. Sylwch fod “deilliad,” fel dampio drwy gyfartaleddu, yn rhywbeth sy'n trawsffurfio ffwythiant yn ffwythiant arall. Er enghraifft, deilliad y ffwythiant $x\mapsto <!--\; \mapsto \; -->x^3$ yw'r ffwythiant $x\mapsto <!--\; \mapsto \; -->3x^2$. Yn gyffredinol, os yw $g$ yn ffwythiant ac os yw $dx$ yn rhif bach, yna deilliad $Dg$ ffwythiant $g$ yw'r ffwythiant y rhoddir ei werth ar unrhyw rif $x$ (yn y terfan wrth i $dx$ fynd yn fach) gan $$Dg(x)=\frac{g(x+dx)-<!--\; -\; -->g(x)}{dx}.$$ Felly, gallwn fynegi'r syniad o ddeilliad (gan gymryd mai, dyweder, 0.00001 yw $dx$) fel y weithdrefn

(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))

ynghyd â'r diffiniad

(define dx 0.00001)

Fel average-damp, mae deriv yn weithdrefn sy'n cymryd gweithdrefn yn arg ac yn dychwelyd gweithdrefn yn werth. Er enghraifft, i frasamcanu deilliad $x\mapsto <!--\; \mapsto \; -->x^3$ ar 5 (y mae ei werth union yn 75), gallwn werthuso

(define (cube x) (* x x x))

((deriv cube) 5)
75.00014999664018

Gyda chymorth deriv, gallwn fynegi dull Newton fel proses pwynt sefydlog:

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) 
            ((deriv g) x)))))

(define (newtons-method g guess)
  (fixed-point (newton-transform g) 
               guess))

Mae'r weithdrefn newton-transform yn mynegi'r fformiwla ar ddechrau'r adran hon, a diffinnir newtons-method yn rhwydd yn nhermau hyn. Mae'n cymryd gweithdrefn sy'n cyfrifiannu'r ffwythiant yr ydym am ganfod sero iddo, ynghyd â dyfaliad cychwynnol, yn argiau. Er enghraifft, i ganfod gwreiddyn sgwâr $x$, gallwn ddefnyddio dull Newton i ganfod sero'r ffwythiant $y\mapsto <!--\; \mapsto \; -->y^2-<!--\; -\; -->x$ gan ddechrau â dyfaliad cychwynnol o 1.⁶³

Mae hyn yn darparu ffurf arall eto ar y weithdrefn gwreiddyn sgwâr:

(define (sqrt x)
  (newtons-method 
   (lambda (y) 
     (- (square y) x)) 
   1.0))

Haniaethau a gweithdrefnau dosbarth cyntaf

Rydym wedi gweld dwy ffordd o fynegi'r cyfrifiad gwreiddyn sgwâr fel enghraifft o ddull mwy cyffredinol, unwaith fel chwiliad am bwynt sefydlog ac unwaith drwy ddefnyddio dull Newton. Gan fod dull Newton ei hun wedi'i fynegi fel proses pwynt sefydlog, mewn gwirionedd gwelsom ddwy ffordd o gyfrifiannu gwreiddiau sgwâr fel pwyntiau sefydlog. Mae pob dull yn dechrau â ffwythiant ac yn canfod pwynt sefydlog rhyw drawsffurfiad o'r ffwythiant. Gallwn fynegi'r syniad cyffredinol hwn ei hun fel gweithdrefn:

(define (fixed-point-of-transform 
         g transform guess)
  (fixed-point (transform g) guess))

Mae'r weithdrefn gyffredinol iawn hon yn cymryd gweithdrefn g sy'n cyfrifiannu rhyw ffwythiant, gweithdrefn sy'n trawsffurfio g, a dyfaliad cychwynnol yn argiau. Y canlyniad a ddychwelir yw pwynt sefydlog y ffwythiant wedi'i drawsffurfio.

Gan ddefnyddio'r haniaeth hon, gallwn ail-lunio'r cyfrifiad gwreiddyn sgwâr cyntaf yn yr adran hon (lle chwiliwn am bwynt sefydlog y fersiwn o $y\mapsto <!--\; \mapsto \; -->x/y$ wedi'i dampio drwy gyfartaleddu) fel enghraifft o'r dull cyffredinol hwn:

(define (sqrt x)
  (fixed-point-of-transform 
   (lambda (y) (/ x y))
   average-damp
   1.0))

Yn yr un modd, gallwn fynegi'r ail gyfrifiad gwreiddyn sgwâr yn yr adran hon (enghraifft o ddull Newton sy'n canfod pwynt sefydlog trawsffurfiad Newton o $y\mapsto <!--\; \mapsto \; -->y^2-<!--\; -\; -->x$) fel

(define (sqrt x)
  (fixed-point-of-transform 
   (lambda (y) (- (square y) x))
   newton-transform
   1.0))

Dechreuasom adran 1.3 â'r sylw fod gweithdrefnau cyfansawdd yn fecanwaith haniaethu hanfodol, oherwydd eu bod yn caniatáu inni fynegi dulliau cyfrifiannu cyffredinol fel elfennau penodol yn ein hiaith raglennu. Nawr rydym wedi gweld sut mae gweithdrefnau trefn uwch yn caniatáu inni drin y dulliau cyffredinol hyn i greu haniaethau pellach.

Fel rhaglenwyr, dylem fod yn effro i gyfleoedd i adnabod yr haniaethau sylfaenol yn ein rhaglenni ac adeiladu arnynt a'u cyffredinoli i greu haniaethau mwy pwerus. Nid yw hyn yn golygu y dylid bob amser ysgrifennu rhaglenni yn y ffordd fwyaf haniaethol bosibl; mae rhaglenwyr arbenigol yn gwybod sut i ddewis y lefel haniaethu sy'n briodol i'w tasg. Ond mae'n bwysig gallu meddwl yn nhermau'r haniaethau hyn, er mwyn bod yn barod i'w cymhwyso mewn cyd-destunau newydd. Arwyddocâd gweithdrefnau trefn uwch yw eu bod yn ein galluogi i gynrychioli'r haniaethau hyn yn benodol fel elfennau yn ein hiaith raglennu, fel y gellir eu trin yn union fel elfennau cyfrifiadurol eraill.

Yn gyffredinol, mae ieithoedd rhaglennu yn gosod cyfyngiadau ar y ffyrdd y gellir trin elfennau cyfrifiadurol. Dywedir bod gan yr elfennau sydd â'r lleiaf o gyfyngiadau statws dosbarth cyntaf. Dyma rai o “hawliau a breintiau” elfennau dosbarth cyntaf:⁶⁴

• Gellir eu henwi drwy newidynnau.
• Gellir eu trosglwyddo yn argiau i weithdrefnau.
• Gellir eu dychwelyd fel canlyniadau gweithdrefnau.
• Gellir eu cynnwys mewn strwythurau data.⁶⁵

Mae Lisp, yn wahanol i ieithoedd rhaglennu cyffredin eraill, yn rhoi statws dosbarth cyntaf llawn i weithdrefnau. Mae hyn yn creu heriau o ran gweithredu effeithlon, ond mae'r cynnydd mewn grym mynegiannol yn enfawr.⁶⁶

Ymarfer 1.40: Diffiniwch weithdrefn cubic y gellir ei defnyddio ynghyd â'r weithdrefn newtons-method mewn mynegiadau o'r ffurf

(newtons-method (cubic a b c) 1)

i frasamcanu seroau'r ciwbig $x^3+a{x}^2+bx+c$.

Ymarfer 1.41: Diffiniwch weithdrefn double sy'n cymryd gweithdrefn ag un arg yn arg ac yn dychwelyd gweithdrefn sy'n cymhwyso'r weithdrefn wreiddiol ddwywaith. Er enghraifft, os yw inc yn weithdrefn sy'n ychwanegu 1 at ei harg, yna dylai (double inc) fod yn weithdrefn sy'n ychwanegu 2. Pa werth a ddychwelir gan

(((double (double double)) inc) 5)

Ymarfer 1.42: Gadewch i $f$ ac $g$ fod yn ddau ffwythiant ag un arg. Diffinnir y cyfansoddiad $f$ ar ôl $g$ fel y ffwythiant $x\mapsto <!--\; \mapsto \; -->f(g(x))$. Diffiniwch weithdrefn compose sy'n gweithredu cyfansoddi. Er enghraifft, os yw inc yn weithdrefn sy'n ychwanegu 1 at ei harg,

((compose square inc) 6)
49

Ymarfer 1.43: Os yw $f$ yn ffwythiant rhifol ac os yw $n$ yn gyfanrif positif, yna gallwn ffurfio cymhwysiad ailadroddus $n^{\text{fed}}$ o $f$, a ddiffinnir fel y ffwythiant y mae ei werth ar $x$ yn $f(f(\dots <!--\; \dots \; -->(f(x))\dots <!--\; \dots \; -->))$. Er enghraifft, os mai $f$ yw'r ffwythiant $x\mapsto <!--\; \mapsto \; -->x+1$, yna cymhwysiad ailadroddus $n^{\text{fed}}$ o $f$ yw'r ffwythiant $x\mapsto <!--\; \mapsto \; -->x+n$. Os mai $f$ yw'r gweithrediad o sgwario rhif, yna cymhwysiad ailadroddus $n^{\text{fed}}$ o $f$ yw'r ffwythiant sy'n codi ei arg i'r pŵer $2^n\text{-fed}$. Ysgrifennwch weithdrefn sy'n cymryd gweithdrefn sy'n cyfrifiannu $f$ a chyfanrif positif $n$ yn fewnbynnau, ac yn dychwelyd y weithdrefn sy'n cyfrifiannu cymhwysiad ailadroddus $n^{\text{fed}}$ o $f$. Dylai fod modd defnyddio eich gweithdrefn fel a ganlyn:

((repeated square 2) 5)
625

Awgrym: efallai y bydd defnyddio compose o Ymarfer 1.42 yn gyfleus.

Ymarfer 1.44: Mae'r syniad o lyfnhau ffwythiant yn gysyniad pwysig mewn prosesu signalau. Os yw $f$ yn ffwythiant ac os yw $dx$ yn rhyw rif bach, yna'r fersiwn lyfn o $f$ yw'r ffwythiant y mae ei werth mewn pwynt $x$ yn gyfartaledd $f(x-<!--\; -\; -->dx)$, $f(x)$, ac $f(x+dx)$. Ysgrifennwch weithdrefn smooth sy'n cymryd gweithdrefn sy'n cyfrifiannu $f$ yn fewnbwn ac yn dychwelyd gweithdrefn sy'n cyfrifiannu $f$ wedi'i lyfnhau. Weithiau mae'n werthfawr llyfnhau ffwythiant dro ar ôl tro (hynny yw, llyfnhau'r ffwythiant sydd wedi'i lyfnhau, ac ati) i gael y ffwythiant wedi'i lyfnhau n gwaith. Dangoswch sut i gynhyrchu'r ffwythiant wedi'i lyfnhau n gwaith o unrhyw ffwythiant penodol gan ddefnyddio smooth ac repeated o Ymarfer 1.43.

Ymarfer 1.45: Gwelasom yn 1.3.3 nad yw ceisio cyfrifiannu gwreiddiau sgwâr drwy ganfod pwynt sefydlog $y\mapsto <!--\; \mapsto \; -->x/y$ yn ddiniwed yn cydgyfeirio, ac y gellir unioni hyn drwy ddampio drwy gyfartaleddu. Mae'r un dull yn gweithio i ganfod gwreiddiau ciwb fel pwyntiau sefydlog $y\mapsto <!--\; \mapsto \; -->x/y^2$ wedi'i dampio drwy gyfartaleddu. Yn anffodus, nid yw'r broses yn gweithio ar gyfer gwreiddiau pedwerydd—nid yw un dampiad drwy gyfartaleddu yn ddigon i beri i chwiliad am bwynt sefydlog $y\mapsto <!--\; \mapsto \; -->x/y^3$ gydgyfeirio. Ar y llaw arall, os dampiwn drwy gyfartaleddu ddwywaith (h.y., defnyddio dampiad cyfartaleddu dampiad cyfartaleddu $y\mapsto <!--\; \mapsto \; -->x/y^3$), mae'r chwiliad am bwynt sefydlog yn cydgyfeirio. Gwnewch rai arbrofion i bennu faint o ddampiadau drwy gyfartaleddu sydd eu hangen i gyfrifiannu gwreiddiau $n^{\text{fed}}$ fel chwiliad am bwynt sefydlog sy'n seiliedig ar ddampio $y\mapsto <!--\; \mapsto \; -->x/y^{n-<!--\; -\; -->1}$ drwy gyfartaleddu dro ar ôl tro. Defnyddiwch hyn i weithredu gweithdrefn syml ar gyfer cyfrifiannu gwreiddiau $n^{\text{fed}}$ gan ddefnyddio fixed-point, average-damp, a gweithdrefn repeated Ymarfer 1.43. Tybiwch fod unrhyw weithrediadau rhifyddol sydd eu hangen arnoch ar gael fel gweithrediadau cyntefig.

Ymarfer 1.46: Mae nifer o'r dulliau rhifiadol a ddisgrifir yn y bennod hon yn enghreifftiau o strategaeth gyfrifiadurol hynod gyffredinol a elwir yn welliant drwy iteru. Mae gwelliant drwy iteru yn dweud ein bod, i gyfrifiannu rhywbeth, yn dechrau â dyfaliad cychwynnol o'r ateb, yn profi a yw'r dyfaliad yn ddigon da, ac fel arall yn gwella'r dyfaliad ac yn parhau â'r broses gan ddefnyddio'r dyfaliad gwell yn ddyfaliad newydd. Ysgrifennwch weithdrefn iterative-improve sy'n cymryd dwy weithdrefn yn argiau: dull o ddweud a yw dyfaliad yn ddigon da a dull o wella dyfaliad. Dylai Iterative-improve ddychwelyd yn werth weithdrefn sy'n cymryd dyfaliad yn arg ac yn parhau i wella'r dyfaliad nes ei fod yn ddigon da. Ailysgrifennwch weithdrefn sqrt 1.1.7 a gweithdrefn fixed-point 1.3.3 yn nhermau iterative-improve.