3.1 Aseiniad a Chyflwr Lleol

Fel arfer, ystyriwn fod y byd yn cynnwys gwrthrychau annibynnol, a bod gan bob un gyflwr sy'n newid dros amser. Dywedir bod gan wrthrych “gyflwr” os yw ei hanes yn dylanwadu ar ei ymddygiad. Er enghraifft, mae gan gyfrif banc gyflwr am fod yr ateb i'r cwestiwn “A gaf godi $100?” yn dibynnu ar hanes trafodion adneuo a chodi arian. Gallwn nodweddu cyflwr gwrthrych drwy un neu ragor o newidynnau cyflwr, sydd rhyngddynt yn cadw digon o wybodaeth am ei hanes i bennu ymddygiad presennol y gwrthrych. Mewn system fancio syml, gallem nodweddu cyflwr cyfrif drwy ei falans presennol yn hytrach na chofio holl hanes trafodion y cyfrif.

Mewn system sy'n cynnwys llawer o wrthrychau, anaml y mae'r gwrthrychau'n gwbl annibynnol. Gall pob un ddylanwadu ar gyflwr y lleill drwy ryngweithiadau, sy'n cyplysu newidynnau cyflwr un gwrthrych â rhai gwrthrychau eraill. Yn wir, mae'r syniad bod system yn cynnwys gwrthrychau ar wahân fwyaf defnyddiol pan ellir grwpio newidynnau cyflwr y system yn is-systemau â chyplysiad agos oddi mewn iddynt a chyplysiad llac yn unig ag is-systemau eraill.

Gall y ffordd hon o edrych ar system ddarparu fframwaith pwerus ar gyfer trefnu modelau cyfrifiadurol ohoni. Er mwyn i fodel o'r fath fod yn fodiwlaidd, dylid ei ddadelfennu'n wrthrychau cyfrifiadurol sy'n modelu'r gwrthrychau gwirioneddol yn y system. Rhaid i bob gwrthrych cyfrifiadurol gael ei newidynnau cyflwr lleol ei hun sy'n disgrifio cyflwr y gwrthrych gwirioneddol. Gan fod cyflyrau gwrthrychau yn y system sy'n cael ei modelu'n newid dros amser, rhaid i newidynnau cyflwr y gwrthrychau cyfrifiadurol cyfatebol newid hefyd. Os dewiswn fodelu llif amser yn y system drwy'r amser a aeth heibio yn y cyfrifiadur, yna rhaid inni gael ffordd o adeiladu gwrthrychau cyfrifiadurol y mae eu hymddygiad yn newid wrth i'n rhaglenni redeg. Yn benodol, os dymunwn fodelu newidynnau cyflwr drwy enwau symbolaidd cyffredin yn yr iaith raglennu, rhaid i'r iaith ddarparu gweithredydd aseinio er mwyn inni allu newid y gwerth sy'n gysylltiedig ag enw.

3.1.1Newidynnau Cyflwr Lleol

I ddangos yr hyn a olygwn wrth wrthrych cyfrifiadurol â chyflwr sy'n amrywio dros amser, gadewch inni fodelu'r sefyllfa o godi arian o gyfrif banc. Gwnawn hyn gan ddefnyddio gweithdrefn withdraw, sy'n cymryd amount i'w godi yn arg. Os oes digon o arian yn y cyfrif i ganiatáu'r codiad, dylai withdraw ddychwelyd y balans sy'n weddill ar ôl codi'r arian. Fel arall, dylai withdraw ddychwelyd y neges Dim digon o arian. Er enghraifft, os dechreuwn â $100 yn y cyfrif, dylem gael y dilyniant canlynol o ymatebion gan ddefnyddio withdraw:

(withdraw 25)
75

(withdraw 25)
50

(withdraw 60)
"Insufficient funds"

(withdraw 15)
35

Sylwch fod y mynegiad (withdraw 25), o'i werthuso ddwywaith, yn rhoi gwerthoedd gwahanol. Mae hwn yn fath newydd o ymddygiad i weithdrefn. Hyd yma, gellid ystyried ein holl weithdrefnau yn fanylebau ar gyfer cyfrifo ffwythiannau mathemategol. Roedd galwad i weithdrefn yn cyfrifo gwerth y ffwythiant o'i gymhwyso i'r argiau a roddwyd, ac roedd dwy alwad i'r un weithdrefn â'r un argiau bob amser yn rhoi'r un canlyniad.¹²⁹

I weithredu withdraw, gallwn ddefnyddio newidyn balance i ddynodi balans yr arian yn y cyfrif a diffinio withdraw yn weithdrefn sy'n cyrchu balance. Mae'r weithdrefn withdraw yn gwirio a yw balance o leiaf mor fawr â'r amount y gofynnwyd amdano. Os felly, mae withdraw yn lleihau balance gan amount ac yn dychwelyd gwerth newydd balance. Fel arall, mae withdraw yn dychwelyd y neges Dim digon o arian. Dyma ddiffiniadau balance ac withdraw:

(define balance 100)

(define (withdraw amount)
  (if (>= balance amount)
      (begin (set! balance (- balance amount))
             balance)
      "Insufficient funds"))

Lleihëir balance drwy'r mynegiad

(set! balance (- balance amount))

Mae hwn yn defnyddio'r ffurf arbennig set!, sydd â'r gystrawen

(set! ⟨name⟩ ⟨new-value⟩)

Yma mae ⟨name⟩ yn symbol ac mae ⟨new-value⟩ yn unrhyw fynegiad. Mae Set! yn newid ⟨name⟩ fel mai ei werth yw'r canlyniad a geir drwy werthuso ⟨new-value⟩. Yn yr achos dan sylw, rydym yn newid balance fel mai ei werth newydd fydd canlyniad tynnu amount o werth blaenorol balance.¹³⁰

Mae Withdraw hefyd yn defnyddio'r ffurf arbennig begin i beri i ddau fynegiad gael eu gwerthuso pan fo'r prawf if yn wir: yn gyntaf lleihau balance ac yna dychwelyd gwerth balance. Yn gyffredinol, mae gwerthuso'r mynegiad

(begin ⟨exp₁⟩ ⟨exp₂⟩ … ⟨expₖ⟩)

yn peri i'r mynegiadau o $⟨ex{p}_1⟩$ hyd at $⟨ex{p}_k⟩$ gael eu gwerthuso yn eu trefn ac i werth y mynegiad olaf $⟨ex{p}_k⟩$ gael ei ddychwelyd yn werth y ffurf begin gyfan.¹³¹

Er bod withdraw yn gweithio fel y dymunir, mae'r newidyn balance yn achosi problem. Fel y nodwyd uchod, enw wedi'i ddiffinio yn yr amgylchedd byd-eang yw balance, ac mae ar gael yn rhwydd i unrhyw weithdrefn ei archwilio neu ei newid. Byddai'n llawer gwell pe gallem rywsut wneud balance yn fewnol i withdraw, fel mai withdraw fyddai'r unig weithdrefn a allai gyrchu balance yn uniongyrchol, ac mai dim ond yn anuniongyrchol (drwy alwadau i withdraw) y gallai unrhyw weithdrefn arall gyrchu balance. Byddai hyn yn modelu'n fwy cywir y syniad bod balance yn newidyn cyflwr lleol a ddefnyddir gan withdraw i gadw golwg ar gyflwr y cyfrif.

Gallwn wneud balance yn fewnol i withdraw drwy ailysgrifennu'r diffiniad fel a ganlyn:

(define new-withdraw
  (let ((balance 100))
    (lambda (amount)
      (if (>= balance amount)
          (begin (set! balance 
                       (- balance amount))
                 balance)
          "Insufficient funds"))))

Yr hyn yr ydym wedi'i wneud yma yw defnyddio let i sefydlu amgylchedd â newidyn lleol balance, wedi'i rwymo i'r gwerth cychwynnol 100. O fewn yr amgylchedd lleol hwn, defnyddiwn lambda i greu gweithdrefn sy'n cymryd amount yn arg ac sy'n ymddwyn fel ein gweithdrefn withdraw flaenorol. Y weithdrefn hon—a ddychwelir yn ganlyniad gwerthuso'r mynegiad let—yw new-withdraw, sy'n ymddwyn yn union fel withdraw ond nad yw ei newidyn balance ar gael i unrhyw weithdrefn arall.¹³²

Cyfuno set! â newidynnau lleol yw'r dechneg raglennu gyffredinol y byddwn yn ei defnyddio i adeiladu gwrthrychau cyfrifiadurol â chyflwr lleol. Yn anffodus, mae defnyddio'r dechneg hon yn codi problem ddifrifol: Pan gyflwynasom weithdrefnau gyntaf, cyflwynasom hefyd y model amnewid o werthuso (1.1.5) i ddehongli ystyr cymhwyso gweithdrefn. Dywedasom y dylid dehongli cymhwyso gweithdrefn fel gwerthuso corff y weithdrefn gyda gwerthoedd y paramedrau ffurfiol yn eu lle. Y drafferth yw, cyn gynted ag y cyflwynwn aseiniad i'n hiaith, nid yw amnewid bellach yn fodel digonol o gymhwyso gweithdrefn. (Cawn weld pam yn 3.1.3.) O ganlyniad, yn dechnegol nid oes gennym ar hyn o bryd ffordd o ddeall pam mae'r weithdrefn new-withdraw yn ymddwyn fel yr honnir uchod. Er mwyn deall gweithdrefn fel new-withdraw mewn gwirionedd, bydd angen inni ddatblygu model newydd o gymhwyso gweithdrefn. Yn 3.2 byddwn yn cyflwyno model o'r fath, ynghyd ag esboniad o set! a newidynnau lleol. Yn gyntaf, fodd bynnag, archwiliwn rai amrywiadau ar y thema a sefydlwyd gan new-withdraw.

Mae'r weithdrefn ganlynol, make-withdraw, yn creu “prosesyddion codi arian.” Mae'r paramedr ffurfiol balance yn make-withdraw yn nodi swm cychwynnol yr arian yn y cyfrif.¹³³

(define (make-withdraw balance)
  (lambda (amount)
    (if (>= balance amount)
        (begin (set! balance 
                     (- balance amount))
               balance)
        "Insufficient funds")))

Gellir defnyddio Make-withdraw fel a ganlyn i greu dau wrthrych W1 ac W2:

(define W1 (make-withdraw 100))
(define W2 (make-withdraw 100))

(W1 50)
50

(W2 70)
30

(W2 40)
"Insufficient funds"

(W1 40)
10

Sylwch fod W1 ac W2 yn wrthrychau cwbl annibynnol, a bod gan bob un ei newidyn cyflwr lleol balance ei hun. Nid yw codi arian o'r naill yn effeithio ar y llall.

Gallwn hefyd greu gwrthrychau sy'n trin adneuon yn ogystal â chodiadau arian, ac felly gallwn gynrychioli cyfrifon banc syml. Dyma weithdrefn sy'n dychwelyd “gwrthrych cyfrif banc” â balans cychwynnol penodedig:

(define (make-account balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance 
                     (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (define (dispatch m)
    (cond ((eq? m 'withdraw) withdraw)
          ((eq? m 'deposit) deposit)
          (else (error "Unknown request: 
                 MAKE-ACCOUNT" m))))
  dispatch)

Mae pob galwad i make-account yn sefydlu amgylchedd â newidyn cyflwr lleol balance. O fewn yr amgylchedd hwn, mae make-account yn diffinio gweithdrefnau deposit ac withdraw sy'n cyrchu balance, a gweithdrefn ychwanegol dispatch sy'n cymryd “neges” yn fewnbwn ac yn dychwelyd un o'r ddwy weithdrefn leol. Dychwelir y weithdrefn dispatch ei hun yn werth sy'n cynrychioli gwrthrych y cyfrif banc. Dyma'n union yr arddull raglennu trosglwyddo negeseuon a welsom yn 2.4.3, er ein bod yma'n ei defnyddio ar y cyd â'r gallu i newid newidynnau lleol.

Gellir defnyddio Make-account fel a ganlyn:

(define acc (make-account 100))

((acc 'withdraw) 50)
50

((acc 'withdraw) 60)
"Insufficient funds"

((acc 'deposit) 40)
90

((acc 'withdraw) 60)
30

Mae pob galwad i acc yn dychwelyd y weithdrefn deposit neu withdraw a ddiffiniwyd yn lleol, ac yna cymhwysir honno i'r amount penodedig. Fel yn achos make-withdraw, bydd galwad arall i make-account

(define acc2 (make-account 100))

yn cynhyrchu gwrthrych cyfrif cwbl ar wahân, sy'n cadw ei balance lleol ei hun.

Ymarfer 3.1: Gweithdrefn a elwir dro ar ôl tro ag un arg rhifiadol, ac sy'n cronni ei hargiau mewn swm, yw croniadur. Bob tro y'i gelwir, mae'n dychwelyd y swm sydd wedi cronni hyd hynny. Ysgrifennwch weithdrefn make-accumulator sy'n cynhyrchu croniaduron, pob un yn cadw swm annibynnol. Dylai'r mewnbwn i make-accumulator bennu gwerth cychwynnol y swm; er enghraifft

(define A (make-accumulator 5))

(A 10)
15

(A 10)
25

Ymarfer 3.2: Mewn cymwysiadau profi meddalwedd, mae'n ddefnyddiol gallu cyfrif sawl gwaith y gelwir gweithdrefn benodol yn ystod cyfrifiad. Ysgrifennwch weithdrefn make-monitored sy'n cymryd gweithdrefn, f, yn fewnbwn, a honno ei hun yn cymryd un mewnbwn. Y canlyniad a ddychwelir gan make-monitored yw trydedd weithdrefn, dyweder mf, sy'n cadw golwg ar sawl gwaith y'i galwyd drwy gadw rhifydd mewnol. Os mai'r symbol arbennig how-many-calls? yw'r mewnbwn i mf, yna mae mf yn dychwelyd gwerth y rhifydd. Os mai'r symbol arbennig reset-count yw'r mewnbwn, yna mae mf yn ailosod y rhifydd i sero. Ar gyfer unrhyw fewnbwn arall, mae mf yn dychwelyd canlyniad galw f ar y mewnbwn hwnnw ac yn cynyddu'r rhifydd. Er enghraifft, gallem wneud fersiwn wedi'i monitro o'r weithdrefn sqrt:

(define s (make-monitored sqrt))

(s 100)
10

(s 'how-many-calls?)
1

Ymarfer 3.3: Addaswch y weithdrefn make-account fel ei bod yn creu cyfrifon wedi'u diogelu gan gyfrinair. Hynny yw, dylai make-account gymryd symbol yn arg ychwanegol, fel yn

(define acc 
  (make-account 100 'secret-password))

Dim ond os daw cais gyda'r cyfrinair a ddefnyddiwyd i greu'r cyfrif y dylai'r gwrthrych cyfrif a geir ei brosesu, a dylai ddychwelyd cwyn fel arall:

((acc 'secret-password 'withdraw) 40)
60

((acc 'some-other-password 'deposit) 50)
"Incorrect password"

Ymarfer 3.4: Addaswch weithdrefn make-account Ymarfer 3.3 drwy ychwanegu newidyn cyflwr lleol arall fel ei bod, os ceisir cyrchu cyfrif fwy na saith gwaith yn olynol â chyfrinair anghywir, yn galw'r weithdrefn call-the-cops.

3.1.2Manteision Cyflwyno Aseiniad

Fel y gwelwn, mae cyflwyno aseiniad i'n hiaith raglennu yn ein harwain i ddryswch o faterion cysyniadol anodd. Serch hynny, mae ystyried systemau yn gasgliadau o wrthrychau â chyflwr lleol yn dechneg bwerus ar gyfer cadw dyluniad modiwlaidd. Yn enghraifft syml, ystyriwch ddylunio gweithdrefn rand sydd, bob tro y'i gelwir, yn dychwelyd cyfanrif a ddewisir ar hap.

Nid yw'n gwbl eglur beth a olygir wrth “a ddewisir ar hap.” Yr hyn yr ydym, yn ôl pob tebyg, ei eisiau yw i alwadau olynol i rand gynhyrchu dilyniant o rifau sydd â phriodweddau ystadegol dosraniad unffurf. Ni thrafodwn ddulliau o gynhyrchu dilyniannau addas yma. Yn hytrach, tybiwn fod gennym weithdrefn rand-update sydd â'r briodwedd ganlynol: os dechreuwn â rhif penodol $x_1$ a ffurfio

x₂ = (rand-update x₁)
x₃ = (rand-update x₂)

yna bydd gan y dilyniant gwerthoedd $x_1$, $x_2$, $x_3$, … y priodweddau ystadegol a ddymunir.¹³⁴

Gallwn weithredu rand fel gweithdrefn â newidyn cyflwr lleol x a gychwynnir i ryw werth sefydlog random-init. Mae pob galwad i rand yn cyfrifo rand-update o werth presennol x, yn dychwelyd hwn yn rhif ar hap, ac hefyd yn ei storio yn werth newydd x.

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

Wrth gwrs, gallem gynhyrchu'r un dilyniant o rifau ar hap heb ddefnyddio aseiniad, drwy alw rand-update yn uniongyrchol. Fodd bynnag, byddai hynny'n golygu y byddai'n rhaid i unrhyw ran o'n rhaglen a ddefnyddiai rifau ar hap gofio'n benodol werth presennol x i'w basio yn arg i rand-update. I sylweddoli pa mor drafferthus fyddai hyn, ystyriwch ddefnyddio rhifau ar hap i weithredu techneg o'r enw efelychiad Monte Carlo.

Mae dull Monte Carlo yn cynnwys dewis arbrofion sampl ar hap o set fawr ac yna gwneud didyniadau ar sail y tebygolrwyddau a amcangyfrifir drwy dablu canlyniadau'r arbrofion hynny. Er enghraifft, gallwn frasamcanu $\mathrm{\pi <!--\; \pi \; -->}$ gan ddefnyddio'r ffaith mai $6/{\mathrm{\pi <!--\; \pi \; -->}}^2$ yw'r tebygolrwydd na fydd gan ddau gyfanrif a ddewisir ar hap unrhyw ffactorau yn gyffredin; hynny yw, mai 1 fydd eu rhannydd cyffredin mwyaf.¹³⁵ I gael y brasamcan i $\mathrm{\pi <!--\; \pi \; -->}$, cynhaliwn nifer fawr o arbrofion. Ym mhob arbrawf dewiswn ddau gyfanrif ar hap a chynnal prawf i weld ai 1 yw eu GCD. Mae'r gyfran o weithiau y llwyddir yn y prawf yn rhoi ein hamcangyfrif o $6/{\mathrm{\pi <!--\; \pi \; -->}}^2$, ac o hwn cawn ein brasamcan i $\mathrm{\pi <!--\; \pi \; -->}$.

Wrth wraidd ein rhaglen mae gweithdrefn monte-carlo, sy'n cymryd yn argiau nifer y troeon i roi cynnig ar arbrawf, ynghyd â'r arbrawf ei hun, wedi'i gynrychioli'n weithdrefn heb argiau a fydd yn dychwelyd naill ai gwir neu anwir bob tro y'i rhedir. Mae Monte-carlo yn rhedeg yr arbrawf am y nifer penodedig o dreialon ac yn dychwelyd rhif sy'n nodi'r gyfran o'r treialon y canfuwyd bod yr arbrawf yn wir ynddynt.

(define (estimate-pi trials)
  (sqrt (/ 6 (monte-carlo trials 
                          cesaro-test))))
(define (cesaro-test)
   (= (gcd (rand) (rand)) 1))

(define (monte-carlo trials experiment)
  (define (iter trials-remaining trials-passed)
    (cond ((= trials-remaining 0)
           (/ trials-passed trials))
          ((experiment)
           (iter (- trials-remaining 1) 
                 (+ trials-passed 1)))
          (else
           (iter (- trials-remaining 1) 
                 trials-passed))))
  (iter trials 0))

Nawr gadewch inni roi cynnig ar yr un cyfrifiad gan ddefnyddio rand-update yn uniongyrchol yn hytrach na rand, sef y ffordd y byddai'n rhaid inni fynd ati pe na baem yn defnyddio aseiniad i fodelu cyflwr lleol:

(define (estimate-pi trials)
  (sqrt (/ 6 (random-gcd-test trials 
                              random-init))))

(define (random-gcd-test trials initial-x)
  (define (iter trials-remaining 
                trials-passed 
                x)
    (let ((x1 (rand-update x)))
      (let ((x2 (rand-update x1)))
        (cond ((= trials-remaining 0)
               (/ trials-passed trials))
              ((= (gcd x1 x2) 1)
               (iter (- trials-remaining 1)
                     (+ trials-passed 1)
                     x2))
              (else
               (iter (- trials-remaining 1)
                     trials-passed
                     x2))))))
  (iter trials 0 initial-x))

Er bod y rhaglen yn dal yn syml, mae'n amlygu rhai achosion trafferthus o dorri modiwlaredd. Yn ein fersiwn gyntaf o'r rhaglen, sy'n defnyddio rand, gallwn fynegi dull Monte Carlo yn uniongyrchol fel gweithdrefn gyffredinol monte-carlo sy'n cymryd unrhyw weithdrefn experiment yn arg. Yn ein hail fersiwn o'r rhaglen, heb gyflwr lleol i'r generadur rhifau ar hap, rhaid i random-gcd-test drin y rhifau ar hap x1 ac x2 yn benodol ac ailgylchu x2 drwy'r ddolen iteru yn fewnbwn newydd i rand-update. Mae'r driniaeth benodol hon o'r rhifau ar hap yn plethu strwythur cronni canlyniadau profion â'r ffaith bod ein harbrawf penodol ni'n defnyddio dau rif ar hap, tra gallai arbrofion Monte Carlo eraill ddefnyddio un rhif ar hap neu dri. Mae'n rhaid i hyd yn oed y weithdrefn lefel uchaf estimate-pi ymwneud â darparu rhif ar hap cychwynnol. Mae'r ffaith bod manylion mewnol y generadur rhifau ar hap yn gollwng allan i rannau eraill o'r rhaglen yn ei gwneud yn anodd inni ynysu syniad Monte Carlo fel y gellir ei gymhwyso i dasgau eraill. Yn fersiwn gyntaf y rhaglen, mae aseiniad yn amgáu cyflwr y generadur rhifau ar hap o fewn y weithdrefn rand, fel bod manylion cynhyrchu rhifau ar hap yn parhau'n annibynnol ar weddill y rhaglen.

Dyma'r ffenomen gyffredinol a ddangosir gan enghraifft Monte Carlo: 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 cyfrifiadurol y mae eu strwythur yn adlewyrchu'r dadelfeniad hwn, gwnawn wrthrychau cyfrifiadurol (megis cyfrifon banc a generaduron rhifau ar hap) y mae eu hymddygiad yn newid gydag amser. Modelwn gyflwr â newidynnau cyflwr lleol, a modelwn newidiadau cyflwr ag aseiniadau i'r newidynnau hynny.

Mae'n demtasiwn dod â'r drafodaeth hon i ben drwy ddweud ein bod, drwy gyflwyno aseiniad a'r dechneg o guddio cyflwr mewn newidynnau lleol, yn gallu strwythuro systemau'n fwy modiwlaidd na phe bai'n rhaid trin pob cyflwr yn benodol drwy basio paramedrau ychwanegol. Yn anffodus, fel y gwelwn, nid yw'r stori mor syml â hynny.

Ymarfer 3.5: Dull o amcangyfrif integrynnau pendant drwy efelychiad Monte Carlo yw integru Monte Carlo. Ystyriwch gyfrifo arwynebedd rhanbarth o ofod a ddisgrifir gan draethiad $P(x,y)$ sy'n wir ar gyfer pwyntiau $(x,y)$ yn y rhanbarth ac yn anwir ar gyfer pwyntiau y tu allan iddo. Er enghraifft, disgrifir y rhanbarth o fewn cylch â radiws 3 a'i ganol yn (5, 7) gan y traethiad sy'n profi a yw $(x-<!--\; -\; -->5{)}^2+(y-<!--\; -\; -->7{)}^2\le <!--\; \le \; -->3^2$. I amcangyfrif arwynebedd y rhanbarth a ddisgrifir gan draethiad o'r fath, dechreuwch drwy ddewis petryal sy'n cynnwys y rhanbarth. Er enghraifft, mae petryal â chorneli croeslinol gyferbyn yn (2, 4) ac (8, 10) yn cynnwys y cylch uchod. Yr integryn a ddymunir yw arwynebedd y rhan honno o'r petryal sydd yn y rhanbarth. Gallwn amcangyfrif yr integryn drwy ddewis, ar hap, bwyntiau $(x,y)$ sydd yn y petryal, a phrofi $P(x,y)$ ar gyfer pob pwynt i bennu a yw'r pwynt yn y rhanbarth. Os rhown gynnig ar hyn â llawer o bwyntiau, dylai cyfran y pwyntiau sy'n syrthio yn y rhanbarth roi amcangyfrif o'r gyfran o'r petryal sydd yn y rhanbarth. Felly, dylai lluosi'r gyfran hon ag arwynebedd y petryal cyfan roi amcangyfrif o'r integryn.

Gweithredwch integru Monte Carlo fel gweithdrefn estimate-integral sy'n cymryd yn argiau draethiad P, ffiniau uchaf ac isaf x1, x2, y1, ac y2 y petryal, a nifer y treialon i'w cynnal er mwyn cynhyrchu'r amcangyfrif. Dylai eich gweithdrefn ddefnyddio'r un weithdrefn monte-carlo a ddefnyddiwyd uchod i amcangyfrif $\mathrm{\pi <!--\; \pi \; -->}$. Defnyddiwch eich estimate-integral i gynhyrchu amcangyfrif o $\mathrm{\pi <!--\; \pi \; -->}$ drwy fesur arwynebedd cylch uned.

Bydd yn ddefnyddiol ichi gael gweithdrefn sy'n dychwelyd rhif a ddewisir ar hap o amrediad penodol. Mae'r weithdrefn random-in-range ganlynol yn gweithredu hyn yn nhermau'r weithdrefn random a ddefnyddiwyd yn 1.2.6, sy'n dychwelyd rhif annegyddol sy'n llai na'i mewnbwn.¹³⁶

(define (random-in-range low high)
  (let ((range (- high low)))
    (+ low (random range))))

Ymarfer 3.6: Mae'n ddefnyddiol gallu ailosod generadur rhifau ar hap i gynhyrchu dilyniant sy'n dechrau o werth penodol. Dyluniwch weithdrefn rand newydd a elwir ag arg sydd naill ai'n symbol generate neu'n symbol reset, ac sy'n ymddwyn fel a ganlyn: mae (rand 'generate) yn cynhyrchu rhif ar hap newydd; mae ((rand 'reset) ⟨new-value⟩) yn ailosod y newidyn cyflwr mewnol i'r ⟨new-value⟩ penodedig. Felly, drwy ailosod y cyflwr, gellir cynhyrchu dilyniannau y gellir eu hailadrodd. Mae'r rhain yn ddefnyddiol iawn wrth brofi a dadfygio rhaglenni sy'n defnyddio rhifau ar hap.

3.1.3Costau Cyflwyno Aseiniad

Fel y gwelsom, mae'r gweithrediad set! yn ein galluogi i fodelu gwrthrychau sydd â chyflwr lleol. Fodd bynnag, mae pris i'w dalu am y fantais hon. Ni ellir bellach ddehongli ein hiaith raglennu yn nhermau'r model amnewid o gymhwyso gweithdrefn a gyflwynasom yn 1.1.5. Ar ben hynny, ni all unrhyw fodel syml â phriodweddau mathemategol “braf” ddarparu fframwaith digonol ar gyfer ymdrin â gwrthrychau ac aseiniad mewn ieithoedd rhaglennu.

Cyn belled nad ydym yn defnyddio aseiniadau, bydd dau werthusiad o'r un weithdrefn â'r un argiau'n rhoi'r un canlyniad, fel y gellir ystyried gweithdrefnau yn cyfrifo ffwythiannau mathemategol. Felly, gelwir rhaglennu heb unrhyw ddefnydd o aseiniadau, fel y gwnaethom drwy gydol dwy bennod gyntaf y llyfr hwn, yn rhaglennu ffwythiannol.

I ddeall sut y mae aseiniad yn cymhlethu pethau, ystyriwch fersiwn symlach o weithdrefn make-withdraw 3.1.1 nad yw'n trafferthu gwirio am swm annigonol:

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

(define W (make-simplified-withdraw 25))

(W 20)
5

(W 10)
-5

Cymharwch y weithdrefn hon â'r weithdrefn make-decrementer ganlynol, nad yw'n defnyddio set!:

(define (make-decrementer balance)
  (lambda (amount)
    (- balance amount)))

Mae Make-decrementer yn dychwelyd gweithdrefn sy'n tynnu ei mewnbwn o swm penodedig balance, ond nid oes effaith gronnus dros alwadau olynol, fel sydd gyda make-simplified-withdraw:

(define D (make-decrementer 25))

(D 20)
5

(D 10)
15

Gallwn ddefnyddio'r model amnewid i esbonio sut mae make-decrementer yn gweithio. Er enghraifft, gadewch inni ddadansoddi gwerthusiad y mynegiad

((make-decrementer 25) 20)

Yn gyntaf symleiddiwn weithredydd y cyfuniad drwy roi 25 yn lle balance yng nghorff make-decrementer. Mae hyn yn lleihau'r mynegiad i

((lambda (amount) (- 25 amount)) 20)

Nawr cymhwyswn y gweithredydd drwy roi 20 yn lle amount yng nghorff y mynegiad lambda:

(- 25 20)

Yr ateb terfynol yw 5.

Sylwch, fodd bynnag, beth sy'n digwydd os ceisiwn wneud dadansoddiad amnewid tebyg ag make-simplified-withdraw:

((make-simplified-withdraw 25) 20)

Yn gyntaf symleiddiwn y gweithredydd drwy roi 25 yn lle balance yng nghorff make-simplified-withdraw. Mae hyn yn lleihau'r mynegiad i¹³⁷

((lambda (amount) 
   (set! balance (- 25 amount)) 25)
 20)

Nawr cymhwyswn y gweithredydd drwy roi 20 yn lle amount yng nghorff y mynegiad lambda:

(set! balance (- 25 20)) 25

Pe baem yn glynu wrth y model amnewid, byddai'n rhaid inni ddweud mai ystyr cymhwyso'r weithdrefn yw gosod balance i 5 yn gyntaf ac yna dychwelyd 25 yn werth y mynegiad. Mae hyn yn rhoi'r ateb anghywir. Er mwyn cael yr ateb cywir, byddai'n rhaid inni rywsut wahaniaethu rhwng ymddangosiad cyntaf balance (cyn effaith set!) ac ail ymddangosiad balance (ar ôl effaith set!), ac ni all y model amnewid wneud hyn.

Y drafferth yma yw bod amnewid yn seiliedig yn y pen draw ar y syniad mai enwau am werthoedd yw'r symbolau yn ein hiaith yn eu hanfod. Ond cyn gynted ag y cyflwynwn set! a'r syniad y gall gwerth newidyn newid, ni all newidyn fod yn enw yn unig bellach. Bellach mae newidyn rywsut yn cyfeirio at fan lle gellir storio gwerth, a gall y gwerth a storir yn y man hwn newid. Yn 3.2 cawn weld sut mae amgylcheddau'n cyflawni rôl y “man” hwn yn ein model cyfrifiadurol.

Bod yr un fath a newid

Mae'r mater sy'n dod i'r amlwg yma'n fwy dwys na methiant model cyfrifiannu penodol yn unig. Cyn gynted ag y cyflwynwn newid i'n modelau cyfrifiadurol, daw llawer o syniadau a oedd gynt yn syml yn broblemus. Ystyriwch y cysyniad o ddau beth yn bod “yr un fath.”

Tybiwch ein bod yn galw make-decrementer ddwywaith â'r un arg i greu dwy weithdrefn:

(define D1 (make-decrementer 25))
(define D2 (make-decrementer 25))

A yw D1 ac D2 yr un fath? Un ateb derbyniol yw ydynt, am fod gan D1 ac D2 yr un ymddygiad cyfrifiadurol—mae pob un yn weithdrefn sy'n tynnu ei mewnbwn o 25. Yn wir, gellid rhoi D1 yn lle D2 mewn unrhyw gyfrifiad heb newid y canlyniad.

Cymharwch hyn â galw make-simplified-withdraw ddwywaith:

(define W1 (make-simplified-withdraw 25))
(define W2 (make-simplified-withdraw 25))

A yw W1 ac W2 yr un fath? Yn sicr nid ydynt, am fod galwadau i W1 ac W2 yn cael effeithiau gwahanol, fel y dangosir gan y dilyniant rhyngweithiadau canlynol:

(W1 20)
5

(W1 20)
-15

(W2 20)
5

Er bod W1 ac W2 yn “hafal” yn yr ystyr bod y ddau'n cael eu creu drwy werthuso'r un mynegiad, (make-simplified-withdraw 25), nid yw'n wir y gellid rhoi W1 yn lle W2 mewn unrhyw fynegiad heb newid canlyniad gwerthuso'r mynegiad.

Dywedir bod iaith sy'n cefnogi'r cysyniad y “gellir amnewid pethau hafal am bethau hafal” mewn mynegiad heb newid gwerth y mynegiad yn gyfeiriadol dryloyw. Torrir tryloywder cyfeiriadol pan gynhwyswn set! yn ein hiaith gyfrifiadurol. Mae hyn yn ei gwneud yn anodd pennu pryd y gallwn symleiddio mynegiadau drwy roi mynegiadau cyfwerth yn eu lle. O ganlyniad, mae rhesymu am raglenni sy'n defnyddio aseiniad yn mynd yn llawer iawn anos.

Ar ôl inni ildio tryloywder cyfeiriadol, mae'n anodd mynegi'n ffurfiol beth yw ystyr dweud bod gwrthrychau cyfrifiadurol “yr un fath.” Yn wir, prin fod ystyr “yr un fath” yn y byd go iawn y mae ein rhaglenni'n ei fodelu yn eglur ynddo'i hun. Yn gyffredinol, dim ond drwy addasu un gwrthrych ac yna arsylwi a yw'r gwrthrych arall wedi newid yn yr un ffordd y gallwn bennu bod dau wrthrych sy'n ymddangos yn unfath yn wir “yr un un.” Ond sut y gallwn ddweud a yw gwrthrych wedi “newid” ac eithrio drwy arsylwi'r “un” gwrthrych ddwywaith a gweld a yw rhyw briodwedd iddo'n wahanol rhwng yr arsylwadau? Felly, ni allwn bennu “newid” heb ryw syniad a priori o “fod yr un fath,” ac ni allwn bennu bod pethau'r un fath heb arsylwi effeithiau newid.

Yn enghraifft o sut y mae'r mater hwn yn codi mewn rhaglennu, ystyriwch y sefyllfa lle mae gan Peter a Paul gyfrif banc â $100 ynddo. Mae gwahaniaeth sylweddol rhwng modelu hyn fel

(define peter-acc (make-account 100))
(define paul-acc (make-account 100))

a'i fodelu fel

(define peter-acc (make-account 100))
(define paul-acc peter-acc)

Yn y sefyllfa gyntaf, mae'r ddau gyfrif banc ar wahân. Ni fydd trafodion a wneir gan Peter yn effeithio ar gyfrif Paul, nac i'r gwrthwyneb. Yn yr ail sefyllfa, fodd bynnag, rydym wedi diffinio paul-acc yn yr un peth ag peter-acc. I bob pwrpas, mae gan Peter a Paul gyfrif banc ar y cyd bellach, ac os yw Peter yn codi arian o peter-acc bydd Paul yn gweld llai o arian yn paul-acc. Gall y ddwy sefyllfa debyg ond gwahanol hyn achosi dryswch wrth adeiladu modelau cyfrifiadurol. Gyda'r cyfrif a rennir, yn benodol, gall fod yn arbennig o ddryslyd bod un gwrthrych (y cyfrif banc) â dau enw gwahanol (peter-acc ac paul-acc); os ydym yn chwilio am yr holl fannau yn ein rhaglen lle gellir newid paul-acc, rhaid inni gofio edrych hefyd ar bethau sy'n newid peter-acc.¹³⁸

O ran y sylwadau uchod ar “fod yr un fath” a “newid,” sylwch pe gallai Peter a Paul archwilio eu balansau banc yn unig, a phe na allent gyflawni gweithrediadau a newidiai'r balans, na fyddai'r cwestiwn a yw'r ddau gyfrif ar wahân o unrhyw bwys ymarferol. Yn gyffredinol, cyn belled nad ydym byth yn newid gwrthrychau data, gallwn ystyried gwrthrych data cyfansawdd yn union gyfanrwydd ei rannau. Er enghraifft, pennir rhif cymarebol drwy roi ei rifiadur a'i enwadur. Ond nid yw'r safbwynt hwn yn ddilys mwyach ym mhresenoldeb newid, lle mae gan wrthrych data cyfansawdd “hunaniaeth” sy'n rhywbeth gwahanol i'r rhannau sy'n ei gyfansoddi. Mae cyfrif banc yn dal i fod “yr un” cyfrif banc hyd yn oed os newidiwn y balans drwy godi arian; i'r gwrthwyneb, gallem gael dau gyfrif banc gwahanol â'r un wybodaeth cyflwr. Nid canlyniad ein hiaith raglennu yw'r cymhlethdod hwn, ond canlyniad ein canfyddiad o gyfrif banc fel gwrthrych. Er enghraifft, nid ydym fel arfer yn ystyried rhif cymarebol yn wrthrych newidiadwy â hunaniaeth, fel y gallem newid y rhifiadur a dal i gael “yr un” rhif cymarebol.

Peryglon rhaglennu gorchmynnol

Mewn cyferbyniad â rhaglennu ffwythiannol, gelwir rhaglennu sy'n gwneud defnydd helaeth o aseiniad yn rhaglennu gorchmynnol. Yn ogystal â chodi cymhlethdodau ynghylch modelau cyfrifiadurol, mae rhaglenni a ysgrifennir mewn arddull orchmynnol yn agored i fygiau na allant ddigwydd mewn rhaglenni ffwythiannol. Er enghraifft, cofiwch y rhaglen ffactoraidd drwy iteru o 1.2.1:

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

Yn lle pasio argiau yn y ddolen iteru fewnol, gallem fabwysiadu arddull fwy gorchmynnol drwy ddefnyddio aseiniadau penodol i ddiweddaru gwerthoedd y newidynnau product ac counter:

(define (factorial n)
  (let ((product 1)
        (counter 1))
    (define (iter)
      (if (> counter n)
          product
          (begin (set! product (* counter 
                                  product))
                 (set! counter (+ counter 1))
                 (iter))))
    (iter)))

Nid yw hyn yn newid y canlyniadau a gynhyrchir gan y rhaglen, ond mae'n cyflwyno magl gynnil. Sut y penderfynwn ar drefn yr aseiniadau? Fel mae'n digwydd, mae'r rhaglen yn gywir fel y'i hysgrifennwyd. Ond byddai ysgrifennu'r aseiniadau yn y drefn wrthdro

(set! counter (+ counter 1))
(set! product (* counter product))

wedi cynhyrchu canlyniad gwahanol, anghywir. Yn gyffredinol, mae rhaglennu ag aseiniad yn ein gorfodi i ystyried trefn gymharol yr aseiniadau'n ofalus er mwyn sicrhau bod pob gosodiad yn defnyddio'r fersiwn gywir o'r newidynnau sydd wedi'u newid. Yn syml, nid yw'r mater hwn yn codi mewn rhaglenni ffwythiannol.¹³⁹

Mae cymhlethdod rhaglenni gorchmynnol yn gwaethygu ymhellach os ystyriwn gymwysiadau lle mae sawl proses yn gweithredu'n gydamserol. Dychwelwn at hyn yn 3.4. Yn gyntaf, fodd bynnag, byddwn yn mynd i'r afael â darparu model cyfrifiadurol ar gyfer mynegiadau sy'n cynnwys aseiniad, ac yn archwilio'r defnydd o wrthrychau â chyflwr lleol wrth ddylunio efelychiadau.

Ymarfer 3.7: Ystyriwch y gwrthrychau cyfrif banc a grëir gan make-account, gyda'r addasiad cyfrinair a ddisgrifir yn Ymarfer 3.3. Tybiwch fod ein system fancio'n gofyn am y gallu i wneud cyfrifon ar y cyd. Diffiniwch weithdrefn make-joint sy'n cyflawni hyn. Dylai Make-joint gymryd tri arg. Y cyntaf yw cyfrif wedi'i ddiogelu gan gyfrinair. Rhaid i'r ail arg gyfateb i'r cyfrinair a ddefnyddiwyd i ddiffinio'r cyfrif er mwyn i'r gweithrediad make-joint fynd yn ei flaen. Cyfrinair newydd yw'r trydydd arg. Dylai Make-joint greu ffordd ychwanegol o gyrchu'r cyfrif gwreiddiol gan ddefnyddio'r cyfrinair newydd. Er enghraifft, os yw peter-acc yn gyfrif banc â'r cyfrinair open-sesame, yna bydd

(define paul-acc
  (make-joint peter-acc 
              'open-sesame 
              'rosebud))

yn caniatáu gwneud trafodion ar peter-acc gan ddefnyddio'r enw paul-acc a'r cyfrinair rosebud. Efallai y byddwch am addasu eich ateb i Ymarfer 3.3 i gynnwys y nodwedd newydd hon.

Ymarfer 3.8: Pan ddiffiniasom y model gwerthuso yn 1.1.3, dywedasom mai'r cam cyntaf wrth werthuso mynegiad yw gwerthuso ei isfynegiadau. Ond ni nodasom erioed ym mha drefn y dylid gwerthuso'r isfynegiadau (e.e., o'r chwith i'r dde neu o'r dde i'r chwith). Pan gyflwynwn aseiniad, gall y drefn y gwerthusir argiau gweithdrefn ynddi wneud gwahaniaeth i'r canlyniad. Diffiniwch weithdrefn syml f fel y bydd gwerthuso

(+ (f 0) (f 1))

yn dychwelyd 0 os gwerthusir yr argiau i + o'r chwith i'r dde ond yn dychwelyd 1 os gwerthusir yr argiau o'r dde i'r chwith.