4.3 Amrywiadau ar Scheme — Cyfrifiannu An-benderfyniaethol

Yn yr adran hon, estynnwn werthusydd Scheme i gynnal patrwm rhaglennu a elwir yn gyfrifiannu an-benderfyniaethol drwy adeiladu cyfleuster chwilio awtomatig i mewn i'r gwerthusydd. Mae hwn yn newid llawer dyfnach i'r iaith na chyflwyno gwerthuso diog yn 4.2.

Mae cyfrifiannu an-benderfyniaethol, fel prosesu ffrydiau, yn ddefnyddiol ar gyfer cymwysiadau “cynhyrchu a phrofi.” Ystyriwch y dasg o ddechrau â dwy restr o gyfanrifau positif a chanfod pâr o gyfanrifau—un o'r rhestr gyntaf ac un o'r ail restr—y mae eu swm yn gysefin. Gwelsom sut i ymdrin â hyn gyda gweithrediadau dilyniannau meidraidd yn 2.2.3 a gyda ffrydiau anfeidraidd yn 3.5.3. Ein dull oedd cynhyrchu dilyniant pob pâr posibl a hidlo'r rhain i ddethol y parau y mae eu swm yn gysefin. Nid yw p'un a gynhyrchwn y dilyniant cyfan o barau yn gyntaf fel ym Mhennod 2, neu a gydblethwn y cynhyrchu a'r hidlo fel ym Mhennod 3, yn newid y darlun hanfodol o sut y trefnir y cyfrifiad.

Mae'r dull an-benderfyniaethol yn creu darlun gwahanol. Dychmygwch yn syml ein bod yn dewis (mewn rhyw ffordd) rhif o'r rhestr gyntaf a rhif o'r ail restr, ac yn mynnu (drwy ryw fecanwaith) fod eu swm yn gysefin. Mynegir hyn gan y weithdrefn ganlynol:

(define (prime-sum-pair list1 list2)
  (let ((a (an-element-of list1))
        (b (an-element-of list2)))
    (require (prime? (+ a b)))
    (list a b)))

Gallai ymddangos mai dim ond ailddatgan y broblem y mae'r weithdrefn hon, yn hytrach na phennu ffordd o'i datrys. Serch hynny, mae hon yn rhaglen an-benderfyniaethol ddilys.²⁴⁶

Y syniad allweddol yma yw y gall mynegiadau mewn iaith an-benderfyniaethol gael mwy nag un gwerth posibl. Er enghraifft, gallai an-element-of ddychwelyd unrhyw elfen o'r rhestr a roddir. Bydd ein gwerthusydd rhaglenni an-benderfyniaethol yn gweithio drwy ddewis gwerth posibl yn awtomatig a chadw cofnod o'r dewis. Os na fodlonir gofyniad dilynol, bydd y gwerthusydd yn rhoi cynnig ar ddewis gwahanol, a bydd yn dal i roi cynnig ar ddewisiadau newydd nes bod y gwerthuso'n llwyddo, neu nes bod y dewisiadau'n darfod. Yn union fel y rhyddhaodd y gwerthusydd diog y rhaglennydd rhag manylion sut y gohirir ac y gorfodir gwerthoedd, bydd y gwerthusydd rhaglenni an-benderfyniaethol yn rhyddhau'r rhaglennydd rhag manylion sut y gwneir dewisiadau.

Mae'n addysgiadol cymharu'r gwahanol ddarluniau o amser a geir drwy werthuso an-benderfyniaethol a phrosesu ffrydiau. Mae prosesu ffrydiau'n defnyddio gwerthuso diog i wahanu'r amser pan gydosodir y ffrwd o atebion posibl oddi wrth yr amser pan gynhyrchir elfennau gwirioneddol y ffrwd. Mae'r gwerthusydd yn cynnal y rhith bod yr holl atebion posibl wedi'u gosod o'n blaenau mewn dilyniant diamser. Gyda gwerthuso an-benderfyniaethol, mae mynegiad yn cynrychioli archwilio set o fydoedd posibl, pob un wedi'i bennu gan set o ddewisiadau. Mae rhai o'r bydoedd posibl yn arwain at bennau caeedig, tra bo gan eraill werthoedd defnyddiol. Mae'r gwerthusydd rhaglenni an-benderfyniaethol yn cynnal y rhith bod amser yn canghennu, a bod gan ein rhaglenni hanesion gweithredu posibl gwahanol. Pan gyrhaeddwn ben caeedig, gallwn ailymweld â phwynt dewis blaenorol a bwrw ymlaen ar hyd cangen wahanol.

Gelwir y gwerthusydd rhaglenni an-benderfyniaethol a weithredir isod yn werthusydd amb oherwydd ei fod wedi'i seilio ar ffurf arbennig newydd o'r enw amb. Gallwn deipio'r diffiniad uchod o prime-sum-pair wrth ddolen yrru'r gwerthusydd amb (ynghyd â diffiniadau o prime?, an-element-of, ac require) a rhedeg y weithdrefn fel a ganlyn:

;;; Amb-Eval input:
(prime-sum-pair '(1 3 5 8) '(20 35 110))

;;; Starting a new problem
;;; Amb-Eval value:
(3 20)

Cafwyd y gwerth a ddychwelwyd ar ôl i'r gwerthusydd ddewis elfennau dro ar ôl tro o bob un o'r rhestrau, nes gwneud dewis llwyddiannus.

Mae Adran 4.3.1 yn cyflwyno amb ac yn egluro sut mae'n cynnal an-benderfyniaeth drwy fecanwaith chwilio awtomatig y gwerthusydd. Mae 4.3.2 yn cyflwyno enghreifftiau o raglenni an-benderfyniaethol, ac mae 4.3.3 yn rhoi manylion sut i weithredu'r gwerthusydd amb drwy addasu'r gwerthusydd Scheme arferol.

4.3.1Amb a Chwilio

I ymestyn Scheme i gynnal an-benderfyniaeth, cyflwynwn ffurf arbennig newydd o'r enw amb.²⁴⁷ Mae'r mynegiad

(amb ⟨e₁⟩ ⟨e₂⟩ … ⟨eₙ⟩)

yn dychwelyd gwerth un o'r $n$ mynegiad $⟨e_i⟩$ “yn amwys.” Er enghraifft, gall y mynegiad

(list (amb 1 2 3) (amb 'a 'b))

gael chwe gwerth posibl:

(1 a) (1 b) (2 a) (2 b) (3 a) (3 b)

Mae Amb gydag un dewis yn cynhyrchu gwerth arferol (sengl).

Mae Amb heb ddewisiadau—y mynegiad (amb)—yn fynegiad heb werthoedd derbyniol. O safbwynt gweithredu, gallwn feddwl am (amb) fel mynegiad sydd, wrth ei werthuso, yn achosi i'r cyfrifiad “fethu”: Mae'r cyfrifiad yn cael ei derfynu heb gynhyrchu gwerth. Gan ddefnyddio'r syniad hwn, gallwn fynegi'r gofyniad bod rhaid i fynegiad traethol penodol p fod yn wir fel a ganlyn:

(define (require p)
  (if (not p) (amb)))

Gyda amb ac require, gallwn weithredu'r weithdrefn an-element-of a ddefnyddiwyd uchod:

(define (an-element-of items)
  (require (not (null? items)))
  (amb (car items) 
       (an-element-of (cdr items))))

Mae An-element-of yn methu os yw'r rhestr yn wag. Fel arall, mae'n dychwelyd yn amwys naill ai elfen gyntaf y rhestr neu elfen a ddewisir o weddill y rhestr.

Gallwn hefyd fynegi ystodau anfeidraidd o ddewisiadau. Gall y weithdrefn ganlynol ddychwelyd unrhyw gyfanrif sy'n fwy na neu'n hafal i ryw $n$ penodol:

(define (an-integer-starting-from n)
  (amb n (an-integer-starting-from (+ n 1))))

Mae hyn yn debyg i'r weithdrefn ffrwd integers-starting-from a ddisgrifir yn 3.5.2, ond gydag un gwahaniaeth pwysig: Mae'r weithdrefn ffrwd yn dychwelyd gwrthrych sy'n cynrychioli dilyniant yr holl gyfanrifau gan ddechrau ag $n$, tra bo'r weithdrefn amb yn dychwelyd un cyfanrif.²⁴⁸

Yn haniaethol, gallwn ddychmygu bod gwerthuso mynegiad amb yn achosi i amser ymrannu'n ganghennau, lle mae'r cyfrifiad yn parhau ar bob cangen gydag un o werthoedd posibl y mynegiad. Dywedwn fod amb yn cynrychioli pwynt dewis an-benderfyniaethol. Pe bai gennym beiriant â nifer ddigonol o broseswyr y gellid eu dyrannu'n ddeinamig, gallem weithredu'r chwilio mewn ffordd syml. Byddai'r gweithredu'n mynd rhagddo fel mewn peiriant dilyniannol nes dod ar draws mynegiad amb. Ar y pwynt hwn, byddai rhagor o broseswyr yn cael eu dyrannu a'u cychwyn i barhau â'r holl weithrediadau paralel a awgrymir gan y dewis. Byddai pob prosesydd yn bwrw ymlaen yn ddilyniannol fel petai'r unig ddewis, nes iddo naill ai derfynu drwy ddod ar draws methiant, ymrannu ymhellach, neu orffen.²⁴⁹

Ar y llaw arall, os oes gennym beiriant sy'n gallu gweithredu dim ond un broses (neu ychydig o brosesau cydamserol), rhaid inni ystyried y dewisiadau amgen yn ddilyniannol. Gellid dychmygu addasu gwerthusydd i ddewis ar hap gangen i'w dilyn pryd bynnag y daw ar draws pwynt dewis. Fodd bynnag, gall dewis ar hap arwain yn hawdd at werthoedd sy'n methu. Gallem geisio rhedeg y gwerthusydd dro ar ôl tro, gan wneud dewisiadau ar hap a gobeithio canfod gwerth nad yw'n methu, ond mae'n well chwilio'n systematig drwy bob llwybr gweithredu posibl. Mae'r gwerthusydd amb y byddwn yn ei ddatblygu ac yn gweithio gydag ef yn yr adran hon yn gweithredu chwilio systematig fel a ganlyn: Pan ddaw'r gwerthusydd ar draws cymhwysiad o amb, mae'n dewis y dewis amgen cyntaf i ddechrau. Gall y dewis hwn ei hun arwain at ddewis pellach. Bydd y gwerthusydd bob amser yn dewis y dewis amgen cyntaf i ddechrau ym mhob pwynt dewis. Os yw dewis yn arwain at fethiant, mae'r gwerthusydd yn gwrthgilio yn awtomagig²⁵⁰ i'r pwynt dewis mwyaf diweddar ac yn rhoi cynnig ar y dewis amgen nesaf. Os bydd y dewisiadau amgen yn darfod mewn unrhyw bwynt dewis, bydd y gwerthusydd yn dychwelyd i'r pwynt dewis blaenorol ac yn ailddechrau oddi yno. Mae'r broses hon yn arwain at strategaeth chwilio a elwir yn chwilio dyfnder yn gyntaf neu wrthgilio cronolegol.²⁵¹

Y ddolen yrru

Mae gan ddolen yrru'r gwerthusydd amb rai priodweddau anarferol. Mae'n darllen mynegiad ac yn argraffu gwerth y gweithrediad cyntaf nad yw'n methu, fel yn yr enghraifft prime-sum-pair a ddangosir uchod. Os dymunwn weld gwerth y gweithrediad llwyddiannus nesaf, gallwn ofyn i'r dehonglydd wrthgilio a cheisio cynhyrchu ail weithrediad nad yw'n methu. Nodir hyn drwy deipio'r symbol try-again. Os rhoddir unrhyw fynegiad ac eithrio try-again, bydd y dehonglydd yn dechrau problem newydd, gan waredu'r dewisiadau amgen heb eu harchwilio yn y broblem flaenorol. Dyma enghraifft o ryngweithio:

;;; Amb-Eval input:
(prime-sum-pair '(1 3 5 8) '(20 35 110))

;;; Starting a new problem
;;; Amb-Eval value:
(3 20)

;;; Amb-Eval input:
try-again

;;; Amb-Eval value:
(3 110)

;;; Amb-Eval input:
try-again

;;; Amb-Eval value:
(8 35)

;;; Amb-Eval input:
try-again

;;; There are no more values of
(prime-sum-pair 
 (quote (1 3 5 8)) 
 (quote (20 35 110)))

;;; Amb-Eval input:
(prime-sum-pair '(19 27 30) '(11 36 58))

;;; Starting a new problem
;;; Amb-Eval value:
(30 11)

Ymarfer 4.35: Ysgrifennwch weithdrefn an-integer-between sy'n dychwelyd cyfanrif rhwng dau derfyn penodol. Gellir defnyddio hon i weithredu gweithdrefn sy'n canfod tripledi Pythagoras, h.y., tripledi o gyfanrifau $(i,j,k)$ rhwng y terfynau penodol fel bod $i\le <!--\; \le \; -->j$ ac $i^2+j^2=k^2$, fel a ganlyn:

(define (a-pythagorean-triple-between low high)
  (let ((i (an-integer-between low high)))
    (let ((j (an-integer-between i high)))
      (let ((k (an-integer-between j high)))
        (require (= (+ (* i i) (* j j)) 
                    (* k k)))
        (list i j k)))))

Ymarfer 4.36: Trafododd Ymarfer 3.69 sut i gynhyrchu ffrwd pob tripled Pythagoras, heb derfyn uchaf ar faint y cyfanrifau sydd i'w chwilio. Eglurwch pam nad yw rhoi an-integer-starting-from yn lle an-integer-between yn unig yn y weithdrefn yn Ymarfer 4.35 yn ffordd ddigonol o gynhyrchu tripledi Pythagoras mympwyol. Ysgrifennwch weithdrefn a fydd yn cyflawni hyn mewn gwirionedd. (Hynny yw, ysgrifennwch weithdrefn y byddai teipio try-again dro ar ôl tro ar ei chyfer, mewn egwyddor, yn cynhyrchu pob tripled Pythagoras yn y pen draw.)

Ymarfer 4.37: Mae Ben Bitdiddle yn honni bod y dull canlynol o gynhyrchu tripledi Pythagoras yn fwy effeithlon na'r un yn Ymarfer 4.35. A yw'n gywir? (Awgrym: Ystyriwch nifer y posibiliadau y mae'n rhaid eu harchwilio.)

(define (a-pythagorean-triple-between low high)
  (let ((i (an-integer-between low high))
        (hsq (* high high)))
    (let ((j (an-integer-between i high)))
      (let ((ksq (+ (* i i) (* j j))))
        (require (>= hsq ksq))
        (let ((k (sqrt ksq)))
          (require (integer? k))
          (list i j k))))))

4.3.2Enghreifftiau o Raglenni An-benderfyniaethol

Mae Adran 4.3.3 yn disgrifio gweithrediad y gwerthusydd amb. Yn gyntaf, fodd bynnag, rhown rai enghreifftiau o sut y gellir ei ddefnyddio. Mantais rhaglennu an-benderfyniaethol yw y gallwn guddio manylion sut y cyflawnir chwilio, gan fynegi ein rhaglenni felly ar lefel haniaethu uwch.

Posau Rhesymeg

Mae'r pos canlynol (o Dinesman 1968) yn nodweddiadol o ddosbarth mawr o bosau rhesymeg syml:

Mae Baker, Cooper, Fletcher, Miller, a Smith yn byw ar loriau gwahanol mewn bloc fflatiau sydd â dim ond pum llawr. Nid yw Baker yn byw ar y llawr uchaf. Nid yw Cooper yn byw ar y llawr isaf. Nid yw Fletcher yn byw ar y llawr uchaf nac ar y llawr isaf. Mae Miller yn byw ar lawr uwch na Cooper. Nid yw Smith yn byw ar lawr sy'n gyfagos i lawr Fletcher. Nid yw Fletcher yn byw ar lawr sy'n gyfagos i lawr Cooper. Ble mae pawb yn byw?

Gallwn bennu pwy sy'n byw ar bob llawr mewn ffordd syml drwy restru'r holl bosibiliadau a gosod y cyfyngiadau a roddir:²⁵²

(define (multiple-dwelling)
  (let ((baker (amb 1 2 3 4 5))
        (cooper (amb 1 2 3 4 5))
        (fletcher (amb 1 2 3 4 5))
        (miller (amb 1 2 3 4 5))
        (smith (amb 1 2 3 4 5)))
    (require
     (distinct? (list baker cooper fletcher 
                      miller smith)))
    (require (not (= baker 5)))
    (require (not (= cooper 1)))
    (require (not (= fletcher 5)))
    (require (not (= fletcher 1)))
    (require (> miller cooper))
    (require
     (not (= (abs (- smith fletcher)) 1)))
    (require 
     (not (= (abs (- fletcher cooper)) 1)))
    (list (list 'baker baker)
          (list 'cooper cooper)
          (list 'fletcher fletcher)
          (list 'miller miller)
          (list 'smith smith))))

Mae gwerthuso'r mynegiad (multiple-dwelling) yn cynhyrchu'r canlyniad

((baker 3) (cooper 2) (fletcher 4)
 (miller 5) (smith 1))

Er bod y weithdrefn syml hon yn gweithio, mae'n araf iawn. Mae Ymarfer 4.39 ac Ymarfer 4.40 yn trafod rhai gwelliannau posibl.

Ymarfer 4.38: Addaswch y weithdrefn aml-breswylfa i hepgor y gofyniad nad yw Smith a Fletcher yn byw ar loriau cyfagos. Sawl datrysiad sydd i'r pos wedi'i addasu hwn?

Ymarfer 4.39: A yw trefn y cyfyngiadau yn y weithdrefn aml-breswylfa yn effeithio ar yr ateb? A yw'n effeithio ar yr amser i ganfod ateb? Os credwch ei bod yn bwysig, dangoswch raglen gyflymach a geir o'r un a roddir drwy aildrefnu'r cyfyngiadau. Os credwch nad yw'n bwysig, dadleuwch dros eich safbwynt.

Ymarfer 4.40: Yn y broblem aml-breswylfa, sawl set o aseiniadau pobl i loriau sydd, cyn ac ar ôl y gofyniad bod aseiniadau'r lloriau'n wahanol i'w gilydd? Mae'n aneffeithlon iawn cynhyrchu pob aseiniad posibl o bobl i loriau ac yna gadael i wrthgilio eu dileu. Er enghraifft, dim ond ar un neu ddau o'r newidynnau person–llawr y mae'r rhan fwyaf o'r cyfyngiadau'n dibynnu, ac felly gellir eu gosod cyn dewis lloriau ar gyfer pawb. Ysgrifennwch a dangoswch weithdrefn an-benderfyniaethol lawer mwy effeithlon sy'n datrys y broblem hon drwy gynhyrchu dim ond y posibiliadau hynny nad ydynt eisoes wedi'u diystyru gan gyfyngiadau blaenorol. (Awgrym: Bydd hyn yn gofyn am nyth o fynegiadau let.)

Ymarfer 4.41: Ysgrifennwch raglen Scheme arferol i ddatrys y pos aml-breswylfa.

Ymarfer 4.42: Datryswch y pos “Celwyddogion” canlynol (o Phillips 1934):

Safodd pum merch ysgol arholiad. Roedd eu rhieni—yn eu barn hwy—yn dangos gormod o ddiddordeb yn y canlyniad. Cytunasant felly y dylai pob merch, wrth ysgrifennu adref am yr arholiad, wneud un datganiad gwir ac un datganiad anwir. Dyma'r darnau perthnasol o'u llythyrau:

• Betty: “Roedd Kitty yn ail yn yr arholiad. Dim ond yn drydedd oeddwn i.”
• Ethel: “Byddwch yn falch o glywed fy mod i ar y brig. Roedd Joan yn ail.”
• Joan: “Roeddwn i'n drydedd, ac roedd yr hen Ethel druan yn olaf.”
• Kitty: “Deuthum i'n ail. Dim ond yn bedwaredd oedd Mary.”
• Mary: “Roeddwn i'n bedwaredd. Betty gafodd y safle cyntaf.”

Ym mha drefn y gosodwyd y pum merch mewn gwirionedd?

Ymarfer 4.43: Defnyddiwch y gwerthusydd amb i ddatrys y pos canlynol:²⁵³

Mae gan dad Mary Ann Moore gwch hwylio, ac felly hefyd bob un o'i bedwar ffrind: y Cyrnol Downing, Mr. Hall, Syr Barnacle Hood, a Dr. Parker. Mae gan bob un o'r pump un ferch hefyd, ac mae pob un wedi enwi ei gwch ar ôl merch un o'r lleill. Cwch Syr Barnacle yw'r Gabrielle, Mr. Moore sy'n berchen ar y Lorna; Mr. Hall ar y Rosalind. Mae'r Melissa, sy'n eiddo i'r Cyrnol Downing, wedi'i henwi ar ôl merch Syr Barnacle. Tad Gabrielle sy'n berchen ar y cwch a enwyd ar ôl merch Dr. Parker. Pwy yw tad Lorna?

Ceisiwch ysgrifennu'r rhaglen fel ei bod yn rhedeg yn effeithlon (gweler Ymarfer 4.40). Pennwch hefyd sawl datrysiad sydd os na ddywedir wrthym mai Moore yw cyfenw Mary Ann.

Ymarfer 4.44: Disgrifiodd Ymarfer 2.42 “bos yr wyth brenhines,” sef gosod breninesau ar fwrdd gwyddbwyll fel nad oes dwy yn ymosod ar ei gilydd. Ysgrifennwch raglen an-benderfyniaethol i ddatrys y pos hwn.

Dosrannu iaith naturiol

Mae rhaglenni sydd wedi'u dylunio i dderbyn iaith naturiol fel mewnbwn fel arfer yn dechrau drwy geisio dosrannu'r mewnbwn, hynny yw, paru'r mewnbwn â rhyw strwythur gramadegol. Er enghraifft, gallem geisio adnabod brawddegau Saesneg syml sy'n cynnwys banodolyn wedi'i ddilyn gan enw wedi'i ddilyn gan ferf, megis “The cat eats.” I gyflawni dadansoddiad o'r fath, rhaid inni allu adnabod rhannau ymadrodd geiriau unigol. Gallem ddechrau â rhai rhestrau sy'n dosbarthu gwahanol eiriau:²⁵⁴

(define nouns 
  '(noun student professor cat class))

(define verbs 
  '(verb studies lectures eats sleeps))

(define articles '(article the a))

Mae angen gramadeg arnom hefyd, hynny yw, set o reolau sy'n disgrifio sut y cyfansoddir elfennau gramadegol o elfennau symlach. Gallai gramadeg syml iawn fynnu bod brawddeg bob amser yn cynnwys dau ddarn—ymadrodd enwol wedi'i ddilyn gan ferf—a bod ymadrodd enwol yn cynnwys banodolyn wedi'i ddilyn gan enw. Gyda'r gramadeg hwn, dosrennir y frawddeg “The cat eats” fel a ganlyn:

(sentence
 (noun-phrase (article the) (noun cat))
 (verb eats))

Gallwn gynhyrchu dosraniad o'r fath gyda rhaglen syml sydd â gweithdrefnau ar wahân ar gyfer pob un o'r rheolau gramadegol. I ddosrannu brawddeg, adnabyddwn y ddau ddarn sy'n ei chyfansoddi a dychwelwn restr o'r ddwy elfen hyn, wedi'i thagio â'r symbol sentence:

(define (parse-sentence)
  (list 'sentence
         (parse-noun-phrase)
         (parse-word verbs)))

Yn yr un modd, dosrennir ymadrodd enwol drwy ganfod banodolyn wedi'i ddilyn gan enw:

(define (parse-noun-phrase)
  (list 'noun-phrase
        (parse-word articles)
        (parse-word nouns)))

Ar y lefel isaf, mae dosrannu'n gyfystyr â gwirio dro ar ôl tro fod y gair nesaf sydd heb ei ddosrannu yn aelod o'r rhestr o eiriau ar gyfer y rhan ymadrodd ofynnol. I weithredu hyn, cadwn newidyn byd-eang *unparsed*, sef y mewnbwn sydd heb ei ddosrannu eto. Bob tro y gwiriwn air, mynnwn fod *unparsed* yn ddiwag ac yn dechrau â gair o'r rhestr ddynodedig. Os felly, tynnwn y gair hwnnw o *unparsed* a dychwelwn y gair ynghyd â'i ran ymadrodd (a geir ar ben y rhestr):²⁵⁵

(define (parse-word word-list)
  (require (not (null? *unparsed*)))
  (require (memq (car *unparsed*) 
                 (cdr word-list)))
  (let ((found-word (car *unparsed*)))
    (set! *unparsed* (cdr *unparsed*))
    (list (car word-list) found-word)))

I ddechrau'r dosrannu, y cyfan sydd angen inni ei wneud yw gosod *unparsed* yn fewnbwn cyfan, ceisio dosrannu brawddeg, a gwirio nad oes dim ar ôl:

(define *unparsed* '())
(define (parse input)
  (set! *unparsed* input)
  (let ((sent (parse-sentence)))
    (require (null? *unparsed*))
    sent))

Gallwn nawr roi cynnig ar y dosrannwr a gwirio ei fod yn gweithio ar gyfer ein brawddeg brawf syml:

;;; Amb-Eval input:
(parse '(the cat eats))

;;; Starting a new problem
;;; Amb-Eval value:
(sentence 
 (noun-phrase (article the) (noun cat))
 (verb eats))

Mae'r gwerthusydd amb yn ddefnyddiol yma gan ei bod yn gyfleus mynegi'r cyfyngiadau dosrannu gyda chymorth require. Fodd bynnag, mae chwilio a gwrthgilio awtomatig yn talu ar eu canfed pan ystyriwn ramadegau mwy cymhleth lle mae dewisiadau ynghylch sut y gellir dadelfennu'r unedau.

Gadewch inni ychwanegu rhestr o arddodiaid at ein gramadeg:

(define prepositions 
  '(prep for to in by with))

a diffinio ymadrodd arddodiadol (e.e., “for the cat”) yn arddodiad wedi'i ddilyn gan ymadrodd enwol:

(define (parse-prepositional-phrase)
  (list 'prep-phrase
        (parse-word prepositions)
        (parse-noun-phrase)))

Nawr gallwn ddiffinio brawddeg yn ymadrodd enwol wedi'i ddilyn gan ymadrodd berfol, lle gall ymadrodd berfol fod naill ai'n ferf neu'n ymadrodd berfol wedi'i estyn gan ymadrodd arddodiadol:²⁵⁶

(define (parse-sentence)
  (list 'sentence
         (parse-noun-phrase)
         (parse-verb-phrase)))

(define (parse-verb-phrase)
  (define (maybe-extend verb-phrase)
    (amb 
     verb-phrase
     (maybe-extend 
      (list 'verb-phrase
            verb-phrase
            (parse-prepositional-phrase)))))
  (maybe-extend (parse-word verbs)))

Tra byddwn wrthi, gallwn hefyd ehangu diffiniad ymadroddion enwol i ganiatáu pethau megis “a cat in the class.” Byddwn nawr yn galw'r hyn yr oeddem yn arfer ei alw'n ymadrodd enwol yn ymadrodd enwol syml, a bydd ymadrodd enwol nawr naill ai'n ymadrodd enwol syml neu'n ymadrodd enwol wedi'i estyn gan ymadrodd arddodiadol:

(define (parse-simple-noun-phrase)
  (list 'simple-noun-phrase
        (parse-word articles)
        (parse-word nouns)))

(define (parse-noun-phrase)
  (define (maybe-extend noun-phrase)
    (amb 
     noun-phrase
     (maybe-extend 
      (list 'noun-phrase
            noun-phrase
            (parse-prepositional-phrase)))))
  (maybe-extend (parse-simple-noun-phrase)))

Mae ein gramadeg newydd yn caniatáu inni ddosrannu brawddegau mwy cymhleth. Er enghraifft, mae

(parse '(the student with the cat 
         sleeps in the class))

yn cynhyrchu

(sentence
 (noun-phrase
  (simple-noun-phrase (article the) 
                      (noun student))
  (prep-phrase (prep with)
               (simple-noun-phrase
                (article the)
                (noun cat))))
 (verb-phrase
  (verb sleeps)
  (prep-phrase (prep in)
               (simple-noun-phrase
                (article the)
                (noun class)))))

Sylwch y gall mewnbwn penodol gael mwy nag un dosraniad dilys. Yn y frawddeg “The professor lectures to the student with the cat,” gall fod yr athro'n darlithio gyda'r gath, neu fod y gath gan y myfyriwr. Mae ein rhaglen an-benderfyniaethol yn canfod y ddau bosibilrwydd:

(parse '(the professor lectures to 
         the student with the cat))

yn cynhyrchu

(sentence
 (simple-noun-phrase (article the) 
                     (noun professor))
 (verb-phrase
  (verb-phrase
   (verb lectures)
   (prep-phrase (prep to)
                (simple-noun-phrase
                 (article the) 
                 (noun student))))
  (prep-phrase (prep with)
               (simple-noun-phrase
                (article the) 
                (noun cat)))))

Mae gofyn i'r gwerthusydd roi cynnig arall arni yn rhoi

(sentence
 (simple-noun-phrase (article the) 
                     (noun professor))
 (verb-phrase (verb lectures)
              (prep-phrase 
               (prep to)
               (noun-phrase
                (simple-noun-phrase
                 (article the) 
                 (noun student))
                (prep-phrase 
                 (prep with)
                 (simple-noun-phrase
                  (article the) 
                  (noun cat)))))))

Ymarfer 4.45: Gyda'r gramadeg a roddir uchod, gellir dosrannu'r frawddeg ganlynol mewn pum ffordd wahanol: “The professor lectures to the student in the class with the cat.” Rhowch y pum dosraniad ac eglurwch y gwahaniaethau yn y cysgodion ystyr rhyngddynt.

Ymarfer 4.46: Nid yw'r gwerthusyddion yn 4.1 a 4.2 yn pennu ym mha drefn y gwerthusir operandau. Fe welwn fod y gwerthusydd amb yn eu gwerthuso o'r chwith i'r dde. Eglurwch pam na fyddai ein rhaglen ddosrannu'n gweithio pe gwerthusid yr operandau mewn rhyw drefn arall.

Ymarfer 4.47: Mae Louis Reasoner yn awgrymu, gan fod ymadrodd berfol naill ai'n ferf neu'n ymadrodd berfol wedi'i ddilyn gan ymadrodd arddodiadol, y byddai'n llawer symlach diffinio'r weithdrefn parse-verb-phrase fel a ganlyn (ac yn yr un modd ar gyfer ymadroddion enwol):

(define (parse-verb-phrase)
  (amb (parse-word verbs)
       (list 
        'verb-phrase
        (parse-verb-phrase)
        (parse-prepositional-phrase))))

A yw hyn yn gweithio? A yw ymddygiad y rhaglen yn newid os cyfnewidiwn drefn y mynegiadau yn yr amb?

Ymarfer 4.48: Estynnwch y gramadeg a roddir uchod i ymdrin â brawddegau mwy cymhleth. Er enghraifft, gallech ymestyn ymadroddion enwol a berfol i gynnwys ansoddeiriau ac adferfau, neu gallech ymdrin â brawddegau cyfansawdd.²⁵⁷

Ymarfer 4.49: Mae gan Alyssa P. Hacker fwy o ddiddordeb mewn cynhyrchu brawddegau diddorol nag yn eu dosrannu. Mae'n rhesymu y gallwn, drwy newid y weithdrefn parse-word yn unig fel ei bod yn anwybyddu'r “frawddeg fewnbwn” ac yn lle hynny bob amser yn llwyddo ac yn cynhyrchu gair priodol, ddefnyddio'r rhaglenni a adeiladwyd gennym ar gyfer dosrannu i gynhyrchu yn lle hynny. Gweithredwch syniad Alyssa, a dangoswch yr hanner dwsin cyntaf o frawddegau, neu rywbeth tebyg, a gynhyrchir.²⁵⁸

4.3.3Gweithredu'r Gwerthusydd Amb

Gall gwerthuso mynegiad Scheme arferol ddychwelyd gwerth, gall beidio byth â therfynu, neu gall arwyddo gwall. Yn Scheme an-benderfyniaethol gall gwerthuso mynegiad hefyd arwain at ganfod pen caeedig, ac yn yr achos hwnnw rhaid i'r gwerthuso wrthgilio i bwynt dewis blaenorol. Mae'r achos ychwanegol hwn yn cymhlethu dehongli Scheme an-benderfyniaethol.

Byddwn yn adeiladu'r gwerthusydd amb ar gyfer Scheme an-benderfyniaethol drwy addasu gwerthusydd dadansoddol 4.1.7.²⁵⁹ Fel yn y gwerthusydd dadansoddol, cyflawnir gwerthuso mynegiad drwy alw gweithdrefn weithredu a gynhyrchir drwy ddadansoddi'r mynegiad hwnnw. Bydd y gwahaniaeth rhwng dehongli Scheme arferol a dehongli Scheme an-benderfyniaethol yn gyfan gwbl yn y gweithdrefnau gweithredu.

Gweithdrefnau gweithredu a pharhadau

Cofiwch fod gweithdrefnau gweithredu'r gwerthusydd arferol yn cymryd un arg: amgylchedd y gweithredu. Mewn cyferbyniad, mae gweithdrefnau gweithredu'r gwerthusydd amb yn cymryd tri arg: yr amgylchedd, a dwy weithdrefn a elwir yn weithdrefnau parhad. Bydd gwerthuso mynegiad yn gorffen drwy alw un o'r ddau barhad hyn: Os yw'r gwerthuso'n arwain at werth, gelwir y parhad llwyddiant gyda'r gwerth hwnnw; os yw'r gwerthuso'n arwain at ganfod pen caeedig, gelwir y parhad methiant. Adeiladu a galw parhadau priodol yw'r mecanwaith y mae'r gwerthusydd an-benderfyniaethol yn ei ddefnyddio i weithredu gwrthgilio.

Gwaith y parhad llwyddiant yw derbyn gwerth a bwrw ymlaen â'r cyfrifiad. Ynghyd â'r gwerth hwnnw, trosglwyddir parhad methiant arall i'r parhad llwyddiant, sydd i'w alw'n ddiweddarach os yw defnyddio'r gwerth hwnnw'n arwain at ben caeedig.

Gwaith y parhad methiant yw rhoi cynnig ar gangen arall o'r broses an-benderfyniaethol. Hanfod yr iaith an-benderfyniaethol yw'r ffaith y gall mynegiadau gynrychioli dewisiadau rhwng opsiynau amgen. Rhaid i werthuso mynegiad o'r fath fwrw ymlaen ag un o'r dewisiadau amgen a nodir, er nad yw'n hysbys ymlaen llaw pa ddewisiadau fydd yn arwain at ganlyniadau derbyniol. I ymdrin â hyn, mae'r gwerthusydd yn dewis un o'r opsiynau amgen ac yn trosglwyddo'r gwerth hwn i'r parhad llwyddiant. Ynghyd â'r gwerth hwn, mae'r gwerthusydd yn adeiladu ac yn trosglwyddo parhad methiant y gellir ei alw'n ddiweddarach i ddewis opsiwn amgen gwahanol.

Sbardunir methiant yn ystod gwerthuso (hynny yw, gelwir parhad methiant) pan fydd rhaglen defnyddiwr yn gwrthod y dull cyfredol yn benodol (er enghraifft, gall galwad i require arwain at weithredu (amb), mynegiad sydd bob amser yn methu—gweler 4.3.1). Bydd y parhad methiant sydd ar gael ar y pwynt hwnnw'n achosi i'r pwynt dewis mwyaf diweddar ddewis opsiwn amgen arall. Os nad oes rhagor o opsiynau amgen i'w hystyried yn y pwynt dewis hwnnw, sbardunir methiant mewn pwynt dewis cynharach, ac yn y blaen. Gelwir parhadau methiant hefyd gan y ddolen yrru mewn ymateb i gais try-again, i ganfod gwerth arall i'r mynegiad.

Yn ogystal, os digwydd gweithrediad â sgileffaith (megis aseinio i newidyn) ar gangen o'r broses sy'n deillio o ddewis, efallai y bydd angen, pan fydd y broses yn canfod pen caeedig, ddadwneud y sgileffaith cyn gwneud dewis newydd. Cyflawnir hyn drwy wneud i'r gweithrediad â sgileffaith gynhyrchu parhad methiant sy'n dadwneud y sgileffaith ac yn trosglwyddo'r methiant ymlaen.

I grynhoi, adeiladir parhadau methiant gan

• fynegiadau amb—i ddarparu mecanwaith i wneud dewisiadau amgen os yw'r dewis cyfredol a wnaed gan y mynegiad amb yn arwain at ben caeedig;
• y gyrrwr lefel uchaf—i ddarparu mecanwaith i adrodd methiant pan fydd y dewisiadau wedi darfod;
• aseiniadau—i ryng-gipio methiannau a dadwneud aseiniadau wrth wrthgilio.

Dim ond wrth ddod ar draws pen caeedig y cychwynnir methiannau. Mae hyn yn digwydd

• os yw rhaglen y defnyddiwr yn gweithredu (amb);
• os yw'r defnyddiwr yn teipio try-again wrth y gyrrwr lefel uchaf.

Gelwir parhadau methiant hefyd wrth brosesu methiant:

• Pan fydd y parhad methiant a grëwyd gan aseiniad yn gorffen dadwneud sgileffaith, mae'n galw'r parhad methiant a ryng-gipiodd, er mwyn trosglwyddo'r methiant yn ôl i'r pwynt dewis a arweiniodd at yr aseiniad hwn neu i'r lefel uchaf.
• Pan fydd dewisiadau parhad methiant amb yn darfod, mae'n galw'r parhad methiant a roddwyd i'r amb yn wreiddiol, er mwyn trosglwyddo'r methiant yn ôl i'r pwynt dewis blaenorol neu i'r lefel uchaf.

Strwythur y gwerthusydd

Mae gweithdrefnau cystrawen a chynrychioli data'r gwerthusydd amb, a hefyd y weithdrefn sylfaenol analyze, yn union yr un fath â'r rhai yn werthusydd 4.1.7, ac eithrio'r ffaith bod angen gweithdrefnau cystrawen ychwanegol arnom i adnabod y ffurf arbennig amb:²⁶⁰

(define (amb? exp) (tagged-list? exp 'amb))
(define (amb-choices exp) (cdr exp))

Rhaid inni hefyd ychwanegu at y dethol gweithdrefn yn analyze gymal a fydd yn adnabod y ffurf arbennig hon ac yn cynhyrchu gweithdrefn weithredu briodol:

((amb? exp) (analyze-amb exp))

Mae'r weithdrefn lefel uchaf ambeval (sy'n debyg i'r fersiwn o eval a roddir yn 4.1.7) yn dadansoddi'r mynegiad a roddir ac yn cymhwyso'r weithdrefn weithredu sy'n deillio o hynny i'r amgylchedd a roddir, ynghyd â dau barhad a roddir:

(define (ambeval exp env succeed fail)
  ((analyze exp) env succeed fail))

Gweithdrefn â dau arg yw parhad llwyddiant: y gwerth sydd newydd gael ei ganfod a pharhad methiant arall i'w ddefnyddio os yw'r gwerth hwnnw'n arwain at fethiant dilynol. Gweithdrefn heb argiau yw parhad methiant. Felly ffurf gyffredinol gweithdrefn weithredu yw

(lambda (env succeed fail)
  ;; succeed is (lambda (value fail) …)
  ;; fail is (lambda () …)
  …)

Er enghraifft, bydd gweithredu

(ambeval ⟨exp⟩
         the-global-environment
         (lambda (value fail) value)
         (lambda () 'failed))

yn ceisio gwerthuso'r mynegiad a roddir ac yn dychwelyd naill ai gwerth y mynegiad (os yw'r gwerthuso'n llwyddo) neu'r symbol failed (os yw'r gwerthuso'n methu). Mae'r alwad i ambeval yn y ddolen yrru a ddangosir isod yn defnyddio gweithdrefnau parhad llawer mwy cymhleth, sy'n parhau â'r ddolen ac yn cynnal y cais try-again.

Mae'r rhan fwyaf o gymhlethdod y gwerthusydd amb yn deillio o fecanwaith trosglwyddo'r parhadau o gwmpas wrth i'r gweithdrefnau gweithredu alw ei gilydd. Wrth fynd drwy'r cod canlynol, dylech gymharu pob un o'r gweithdrefnau gweithredu â'r weithdrefn gyfatebol ar gyfer y gwerthusydd arferol a roddir yn 4.1.7.

Mynegiadau syml

Mae'r gweithdrefnau gweithredu ar gyfer y mathau symlaf o fynegiadau yn eu hanfod yr un fath â'r rhai ar gyfer y gwerthusydd arferol, ac eithrio'r angen i reoli'r parhadau. Yn syml, mae'r gweithdrefnau gweithredu'n llwyddo gyda gwerth y mynegiad, gan drosglwyddo ymlaen y parhad methiant a drosglwyddwyd iddynt.

(define (analyze-self-evaluating exp)
  (lambda (env succeed fail)
    (succeed exp fail)))

(define (analyze-quoted exp)
  (let ((qval (text-of-quotation exp)))
    (lambda (env succeed fail)
      (succeed qval fail))))

(define (analyze-variable exp)
  (lambda (env succeed fail)
    (succeed (lookup-variable-value exp env)
             fail)))

(define (analyze-lambda exp)
  (let ((vars (lambda-parameters exp))
        (bproc (analyze-sequence 
                (lambda-body exp))))
    (lambda (env succeed fail)
      (succeed (make-procedure vars bproc env)
               fail))))

Sylwch fod chwilio am newidyn bob amser yn ‘llwyddo.’ Os yw lookup-variable-value yn methu â chanfod y newidyn, mae'n arwyddo gwall, fel arfer. Mae “methiant” o'r fath yn dynodi nam yn y rhaglen—cyfeiriad at newidyn heb ei rwymo; nid yw'n dynodi y dylem roi cynnig ar ddewis an-benderfyniaethol arall yn lle'r un sy'n cael ei brofi ar hyn o bryd.

Mynegiadau amodol a dilyniannau

Ymdrinnir â mynegiadau amodol hefyd mewn ffordd debyg i'r gwerthusydd arferol. Mae'r weithdrefn weithredu a gynhyrchir gan analyze-if yn galw gweithdrefn weithredu'r traethiad pproc gyda pharhad llwyddiant sy'n gwirio a yw gwerth y traethiad yn wir ac yn mynd ymlaen i weithredu naill ai'r canlynydd neu'r dewis amgen. Os yw gweithredu pproc yn methu, gelwir parhad methiant gwreiddiol y mynegiad if.

(define (analyze-if exp)
  (let ((pproc (analyze (if-predicate exp)))
        (cproc (analyze (if-consequent exp)))
        (aproc (analyze (if-alternative exp))))
    (lambda (env succeed fail)
      (pproc env
             ;; success continuation for evaluating
             ;; the predicate to obtain pred-value
             (lambda (pred-value fail2)
               (if (true? pred-value)
                   (cproc env succeed fail2)
                   (aproc env succeed fail2)))
             ;; failure continuation for
             ;; evaluating the predicate
             fail))))

Ymdrinnir â dilyniannau hefyd yn yr un ffordd ag yn y gwerthusydd blaenorol, ac eithrio'r trefniadau yn yr is-weithdrefn sequentially sy'n ofynnol ar gyfer trosglwyddo'r parhadau. Hynny yw, i weithredu a ac yna b yn ddilyniannol, galwn a gyda pharhad llwyddiant sy'n galw b.

(define (analyze-sequence exps)
  (define (sequentially a b)
    (lambda (env succeed fail)
      (a env
         ;; success continuation for calling a
         (lambda (a-value fail2)
           (b env succeed fail2))
         ;; failure continuation for calling a
         fail)))
  (define (loop first-proc rest-procs)
    (if (null? rest-procs)
        first-proc
        (loop (sequentially first-proc 
                            (car rest-procs))
              (cdr rest-procs))))
  (let ((procs (map analyze exps)))
    (if (null? procs)
        (error "Empty sequence: ANALYZE"))
    (loop (car procs) (cdr procs))))

Diffiniadau ac aseiniadau

Mae diffiniadau'n achos arall lle mae'n rhaid inni fynd i rywfaint o drafferth i reoli'r parhadau, oherwydd mae'n angenrheidiol gwerthuso mynegiad gwerth y diffiniad cyn diffinio'r newidyn newydd mewn gwirionedd. I gyflawni hyn, gelwir gweithdrefn weithredu gwerth y diffiniad vproc gyda'r amgylchedd, parhad llwyddiant, a'r parhad methiant. Os yw gweithredu vproc yn llwyddo, gan gael gwerth val ar gyfer y newidyn a ddiffinnir, diffinnir y newidyn a throsglwyddir y llwyddiant ymlaen:

(define (analyze-definition exp)
  (let ((var (definition-variable exp))
        (vproc (analyze 
                (definition-value exp))))
    (lambda (env succeed fail)
      (vproc env
             (lambda (val fail2)
               (define-variable! var val env)
               (succeed 'ok fail2))
             fail))))

Mae aseiniadau'n fwy diddorol. Dyma'r man cyntaf lle rydym wir yn defnyddio'r parhadau, yn hytrach na dim ond eu trosglwyddo o gwmpas. Mae'r weithdrefn weithredu ar gyfer aseiniadau yn dechrau fel yr un ar gyfer diffiniadau. Yn gyntaf mae'n ceisio cael y gwerth newydd sydd i'w aseinio i'r newidyn. Os yw'r gwerthuso hwn o vproc yn methu, mae'r aseiniad yn methu.

Os yw vproc yn llwyddo, fodd bynnag, ac os awn ymlaen i wneud yr aseiniad, rhaid inni ystyried y posibilrwydd y gallai'r gangen hon o'r cyfrifiad fethu'n ddiweddarach, a fydd yn gofyn inni wrthgilio allan o'r aseiniad. Felly, rhaid inni drefnu dadwneud yr aseiniad fel rhan o'r broses wrthgilio.²⁶¹

Cyflawnir hyn drwy roi i vproc barhad llwyddiant (wedi'i farcio â'r sylw “*1*” isod) sy'n cadw hen werth y newidyn cyn aseinio'r gwerth newydd i'r newidyn a bwrw ymlaen o'r aseiniad. Mae'r parhad methiant a drosglwyddir ynghyd â gwerth yr aseiniad (wedi'i farcio â'r sylw “*2*” isod) yn adfer hen werth y newidyn cyn parhau â'r methiant. Hynny yw, mae aseiniad llwyddiannus yn darparu parhad methiant a fydd yn rhyng-gipio methiant dilynol; mae pa fethiant bynnag a fyddai fel arall wedi galw fail2 yn galw'r weithdrefn hon yn lle hynny, i ddadwneud yr aseiniad cyn galw fail2 mewn gwirionedd.

(define (analyze-assignment exp)
  (let ((var (assignment-variable exp))
        (vproc (analyze 
                (assignment-value exp))))
    (lambda (env succeed fail)
      (vproc env
             (lambda (val fail2)    ; *1*
               (let ((old-value
                      (lookup-variable-value 
                       var 
                       env)))
                 (set-variable-value!
                  var 
                  val 
                  env)
                 (succeed 
                  'ok
                  (lambda ()    ; *2*
                    (set-variable-value! 
                     var
                     old-value
                     env)
                    (fail2)))))
               fail))))

Cymhwyso gweithdrefnau

Nid oes syniadau newydd yn y weithdrefn weithredu ar gyfer cymwysiadau heblaw am gymhlethdod technegol rheoli'r parhadau. Mae'r cymhlethdod hwn yn codi yn analyze-application, oherwydd yr angen i gadw cofnod o'r parhadau llwyddiant a methiant wrth inni werthuso'r operandau. Defnyddiwn weithdrefn get-args i werthuso'r rhestr o operandau, yn hytrach na map syml fel yn y gwerthusydd arferol.

(define (analyze-application exp)
  (let ((fproc (analyze (operator exp)))
        (aprocs (map analyze (operands exp))))
    (lambda (env succeed fail)
      (fproc env
             (lambda (proc fail2)
               (get-args 
                aprocs
                env
                (lambda (args fail3)
                  (execute-application
                   proc args succeed fail3))
                fail2))
             fail))))

Yn get-args, sylwch sut y cyflawnir defnyddio cdr i fynd i lawr y rhestr o weithdrefnau gweithredu aproc a defnyddio cons i adeiladu'r rhestr o args sy'n deillio o hynny, drwy alw pob aproc yn y rhestr gyda pharhad llwyddiant sy'n galw get-args yn ddychweliadol. Mae gan bob un o'r galwadau dychweliadol hyn i get-args barhad llwyddiant y mae ei werth yn ganlyniad cons yr arg newydd ei gael ar y rhestr o argiau a gronnwyd:

(define (get-args aprocs env succeed fail)
  (if (null? aprocs)
      (succeed '() fail)
      ((car aprocs) 
       env
       ;; success continuation for this aproc
       (lambda (arg fail2)
         (get-args 
          (cdr aprocs)
          env
          ;; success continuation for
          ;; recursive call to get-args
          (lambda (args fail3)
            (succeed (cons arg args)
                     fail3))
          fail2))
       fail)))

Cyflawnir cymhwyso gwirioneddol y weithdrefn, a wneir gan execute-application, yn yr un ffordd ag ar gyfer y gwerthusydd arferol, ac eithrio'r angen i reoli'r parhadau.

(define (execute-application 
         proc args succeed fail)
  (cond ((primitive-procedure? proc)
         (succeed 
          (apply-primitive-procedure 
           proc args)
          fail))
        ((compound-procedure? proc)
         ((procedure-body proc)
          (extend-environment 
           (procedure-parameters proc)
           args
           (procedure-environment proc))
          succeed
          fail))
        (else (error "Unknown procedure type: 
                      EXECUTE-APPLICATION"
                     proc))))

Gwerthuso mynegiadau amb

Y ffurf arbennig amb yw elfen allweddol yr iaith an-benderfyniaethol. Yma gwelwn hanfod y broses ddehongli a'r rheswm dros gadw cofnod o'r parhadau. Mae'r weithdrefn weithredu ar gyfer amb yn diffinio dolen try-next sy'n cylchu drwy'r gweithdrefnau gweithredu ar gyfer holl werthoedd posibl y mynegiad amb. Gelwir pob gweithdrefn weithredu gyda pharhad methiant a fydd yn rhoi cynnig ar yr un nesaf. Pan nad oes rhagor o ddewisiadau amgen i roi cynnig arnynt, mae'r mynegiad amb cyfan yn methu.

(define (analyze-amb exp)
  (let ((cprocs
         (map analyze (amb-choices exp))))
    (lambda (env succeed fail)
      (define (try-next choices)
        (if (null? choices)
            (fail)
            ((car choices) 
             env
             succeed
             (lambda ()
               (try-next (cdr choices))))))
      (try-next cprocs))))

Y ddolen yrru

Mae dolen yrru'r gwerthusydd amb yn gymhleth, oherwydd y mecanwaith sy'n caniatáu i'r defnyddiwr roi cynnig arall ar werthuso mynegiad. Mae'r gyrrwr yn defnyddio gweithdrefn o'r enw internal-loop, sy'n cymryd gweithdrefn try-again fel arg. Y bwriad yw y dylai galw try-again fynd ymlaen i'r dewis amgen nesaf sydd heb ei brofi yn y gwerthuso an-benderfyniaethol. Mae Internal-loop naill ai'n galw try-again mewn ymateb i'r defnyddiwr yn teipio try-again wrth y ddolen yrru, neu'n dechrau gwerthusiad newydd drwy alw ambeval.

Mae'r parhad methiant ar gyfer yr alwad hon i ambeval yn hysbysu'r defnyddiwr nad oes rhagor o werthoedd ac yn ailalw'r ddolen yrru.

Mae'r parhad llwyddiant ar gyfer yr alwad i ambeval yn fwy cynnil. Argraffwn y gwerth a gafwyd ac yna galwn y ddolen fewnol eto gyda gweithdrefn try-again a fydd yn gallu rhoi cynnig ar y dewis amgen nesaf. Y weithdrefn next-alternative hon yw'r ail arg a drosglwyddwyd i'r parhad llwyddiant. Fel arfer, meddyliwn am yr ail arg hwn fel parhad methiant i'w ddefnyddio os yw'r gangen werthuso gyfredol yn methu'n ddiweddarach. Yn yr achos hwn, fodd bynnag, rydym wedi cwblhau gwerthusiad llwyddiannus, felly gallwn alw'r gangen amgen “methiant” er mwyn chwilio am werthusiadau llwyddiannus ychwanegol.

(define input-prompt  ";;; Amb-Eval input:")
(define output-prompt ";;; Amb-Eval value:")

(define (driver-loop)
  (define (internal-loop try-again)
    (prompt-for-input input-prompt)
    (let ((input (read)))
      (if (eq? input 'try-again)
          (try-again)
          (begin
            (newline)
            (display 
             ";;; Starting a new problem ")
            (ambeval 
             input
             the-global-environment
             ;; ambeval success
             (lambda (val next-alternative)
               (announce-output 
                output-prompt)
               (user-print val)
               (internal-loop 
                next-alternative))
             ;; ambeval failure
             (lambda ()
               (announce-output
                ";;; There are no 
                 more values of")
               (user-print input)
               (driver-loop)))))))
  (internal-loop
   (lambda ()
     (newline)
     (display 
      ";;; There is no current problem")
     (driver-loop))))

Mae'r alwad gychwynnol i internal-loop yn defnyddio gweithdrefn try-again sy'n cwyno nad oes problem gyfredol ac yn ailgychwyn y ddolen yrru. Dyma'r ymddygiad a fydd yn digwydd os yw'r defnyddiwr yn teipio try-again pan nad oes gwerthuso ar waith.

Ymarfer 4.50: Gweithredwch ffurf arbennig newydd ramb sy'n debyg i amb ac eithrio ei bod yn chwilio dewisiadau amgen mewn trefn ar hap, yn hytrach nag o'r chwith i'r dde. Dangoswch sut y gall hyn helpu gyda phroblem Alyssa yn Ymarfer 4.49.

Ymarfer 4.51: Gweithredwch fath newydd o aseiniad o'r enw permanent-set! nad yw'n cael ei ddadwneud wrth fethu. Er enghraifft, gallwn ddewis dwy elfen wahanol o restr a chyfrif nifer y treialon sydd eu hangen i wneud dewis llwyddiannus fel a ganlyn:

(define count 0)
(let ((x (an-element-of '(a b c)))
      (y (an-element-of '(a b c))))
  (permanent-set! count (+ count 1))
  (require (not (eq? x y)))
  (list x y count))

;;; Starting a new problem
;;; Amb-Eval value:
(a b 2)

;;; Amb-Eval input:
try-again

;;; Amb-Eval value:
(a c 3)

Pa werthoedd fyddai wedi'u dangos pe baem wedi defnyddio set! yma yn hytrach nag permanent-set!?

Ymarfer 4.52: Gweithredwch adeiladwaith newydd o'r enw if-fail sy'n caniatáu i'r defnyddiwr ddal methiant mynegiad. Mae If-fail yn cymryd dau fynegiad. Mae'n gwerthuso'r mynegiad cyntaf fel arfer ac yn dychwelyd fel arfer os yw'r gwerthuso'n llwyddo. Os yw'r gwerthuso'n methu, fodd bynnag, dychwelir gwerth yr ail fynegiad, fel yn yr enghraifft ganlynol:

;;; Amb-Eval input:
(if-fail 
 (let ((x (an-element-of '(1 3 5))))
   (require (even? x))
   x)
 'all-odd)

;;; Starting a new problem
;;; Amb-Eval value:
all-odd

;;; Amb-Eval input:
(if-fail
 (let ((x (an-element-of '(1 3 5 8))))
   (require (even? x))
   x)
 'all-odd)

;;; Starting a new problem
;;; Amb-Eval value:
8

Ymarfer 4.53: Gyda permanent-set! fel y'i disgrifir yn Ymarfer 4.51 ac if-fail fel yn Ymarfer 4.52, beth fydd canlyniad gwerthuso

(let ((pairs '()))
  (if-fail 
   (let ((p (prime-sum-pair 
             '(1 3 5 8) 
             '(20 35 110))))
     (permanent-set! pairs 
                     (cons p pairs))
     (amb))
   pairs))

Ymarfer 4.54: Pe na baem wedi sylweddoli y gellid gweithredu require fel gweithdrefn arferol sy'n defnyddio amb, i'w diffinio gan y defnyddiwr fel rhan o raglen an-benderfyniaethol, byddai wedi bod yn rhaid inni ei gweithredu fel ffurf arbennig. Byddai hyn yn gofyn am weithdrefnau cystrawen

(define (require? exp) 
  (tagged-list? exp 'require))

(define (require-predicate exp) 
  (cadr exp))

a chymal newydd yn y dethol gweithdrefn yn analyze

((require? exp) (analyze-require exp))

yn ogystal â'r weithdrefn analyze-require sy'n ymdrin â mynegiadau require. Cwblhewch y diffiniad canlynol o analyze-require.

(define (analyze-require exp)
  (let ((pproc (analyze 
                (require-predicate exp))))
    (lambda (env succeed fail)
      (pproc env
             (lambda (pred-value fail2)
               (if ⟨??⟩
                   ⟨??⟩
                   (succeed 'ok fail2)))
             fail))))

(define (distinct? items)
  (cond ((null? items) true)
        ((null? (cdr items)) true)
        ((member (car items) (cdr items)) false)
        (else (distinct? (cdr items)))))