4.1 Y gwerthusydd metagylchol

Gweithredir ein gwerthusydd ar gyfer Lisp fel rhaglen Lisp. Gall ymddangos yn gylchol meddwl am werthuso rhaglenni Lisp drwy ddefnyddio gwerthusydd sydd ei hun wedi’i weithredu yn Lisp. Fodd bynnag, proses yw gwerthuso, felly mae’n briodol disgrifio’r broses werthuso gan ddefnyddio Lisp, sydd, wedi’r cyfan, yn offeryn inni ar gyfer disgrifio prosesau.²⁰⁷ Dywedir bod gwerthusydd sydd wedi’i ysgrifennu yn yr un iaith ag y mae’n ei gwerthuso yn fetagylchol.

Yn ei hanfod, ffurfiad yn Scheme o’r model amgylchedd o werthuso a ddisgrifiwyd yn 3.2 yw’r gwerthusydd metagylchol. Cofiwch fod dwy ran sylfaenol i’r model:

1. I werthuso cyfuniad (mynegiad cyfansawdd nad yw’n ffurf arbennig), gwerthuswch yr is-fynegiadau ac yna cymhwyswch werth is-fynegiad y gweithredydd i werthoedd is-fynegiadau’r operandau.
2. I gymhwyso gweithdrefn gyfansawdd i set o argiau, gwerthuswch gorff y weithdrefn mewn amgylchedd newydd. I adeiladu’r amgylchedd hwn, estynnwch ran amgylchedd gwrthrych y weithdrefn â ffrâm lle mae paramedrau ffurfiol y weithdrefn wedi’u rhwymo i’r argiau y cymhwysir y weithdrefn iddynt.

Mae’r ddwy reol hyn yn disgrifio hanfod y broses werthuso: cylch sylfaenol lle lleiheir mynegiadau sydd i’w gwerthuso mewn amgylcheddau i weithdrefnau sydd i’w cymhwyso i argiau; lleiheir y rheini yn eu tro i fynegiadau newydd sydd i’w gwerthuso mewn amgylcheddau newydd, ac yn y blaen, nes cyrraedd symbolau, y chwilir am eu gwerthoedd yn yr amgylchedd, a gweithdrefnau cyntefig, a gymhwysir yn uniongyrchol (gweler Ffigur 4.1).²⁰⁸ Ymgorfforir y cylch gwerthuso hwn yn y cydweithio rhwng dwy weithdrefn allweddol y gwerthusydd, eval ac apply, a ddisgrifir yn 4.1.1 (gweler Ffigur 4.1).

Bydd gweithrediad y gwerthusydd yn dibynnu ar weithdrefnau sy’n diffinio cystrawen y mynegiadau sydd i’w gwerthuso. Defnyddiwn haniaethu data i wneud y gwerthusydd yn annibynnol ar gynrychiolaeth yr iaith. Er enghraifft, yn hytrach nag ymrwymo i’r dewis o gynrychioli aseiniad fel rhestr sy’n dechrau â’r symbol set!, defnyddiwn draethiad haniaethol assignment? i brofi am aseiniad, a defnyddiwn ddetholwyr haniaethol assignment-variable ac assignment-value i gyrchu rhannau aseiniad. Disgrifir gweithredu mynegiadau’n fanwl yn 4.1.2. Ceir hefyd weithrediadau, a ddisgrifir yn 4.1.3, sy’n pennu cynrychiolaeth gweithdrefnau ac amgylcheddau. Er enghraifft, mae make-procedure yn adeiladu gweithdrefnau cyfansawdd, mae lookup-variable-value yn cyrchu gwerthoedd newidynnau, ac mae apply-primitive-procedure yn cymhwyso gweithdrefn gyntefig i restr benodol o argiau.

4.1.1Craidd y gwerthusydd

Gellir disgrifio’r broses werthuso fel cydweithio rhwng dwy weithdrefn: eval ac apply.

Eval

Mae Eval yn cymryd mynegiad ac amgylchedd yn argiau. Mae’n dosbarthu’r mynegiad ac yn cyfarwyddo ei werthuso. Mae Eval wedi’i strwythuro fel dadansoddiad achosion o fath cystrawennol y mynegiad sydd i’w werthuso. Er mwyn cadw’r weithdrefn yn gyffredinol, mynegwn y broses o bennu math mynegiad yn haniaethol, heb ymrwymo i unrhyw gynrychiolaeth benodol ar gyfer y gwahanol fathau o fynegiadau. Mae gan bob math o fynegiad draethiad sy’n profi amdano a dull haniaethol o ddethol ei rannau. Mae’r gystrawen haniaethol hon yn ei gwneud yn hawdd gweld sut y gallwn newid cystrawen yr iaith drwy ddefnyddio’r un gwerthusydd ond casgliad gwahanol o weithdrefnau cystrawen.

Mynegiadau cyntefig

• Ar gyfer mynegiadau sy’n gwerthuso i’w hunain, megis rhifau, mae eval yn dychwelyd y mynegiad ei hun.
• Rhaid i Eval edrych am newidynnau yn yr amgylchedd i ganfod eu gwerthoedd.

Ffurfiau arbennig

• Ar gyfer mynegiadau wedi’u dyfynnu, mae eval yn dychwelyd y mynegiad a ddyfynnwyd.
• Rhaid i aseiniad i newidyn, neu ddiffiniad o newidyn, alw eval yn ddychweliadol i gyfrifo’r gwerth newydd sydd i’w gysylltu â’r newidyn. Rhaid addasu’r amgylchedd i newid, neu greu, rhwymiad y newidyn.
• Mae mynegiad if yn gofyn am brosesu ei rannau mewn ffordd arbennig, er mwyn gwerthuso’r canlyniadol os yw’r traethiad yn wir, a gwerthuso’r dewis arall fel arall.
• Rhaid trawsffurfio mynegiad lambda yn weithdrefn y gellir ei chymhwyso drwy becynnu ynghyd y paramedrau a’r corff a bennir gan y mynegiad lambda ag amgylchedd y gwerthuso.
• Mae mynegiad begin yn gofyn am werthuso ei ddilyniant o fynegiadau yn y drefn y maent yn ymddangos ynddi.
• Trawsffurfir dadansoddiad achosion (cond) yn nyth o fynegiadau if ac yna fe’i gwerthusir.

Cyfuniadau

• Ar gyfer cymhwyso gweithdrefn, rhaid i eval werthuso rhan gweithredydd y cyfuniad a’i operandau yn ddychweliadol. Trosglwyddir y weithdrefn a’r argiau canlyniadol i apply, sy’n trin cymhwyso’r weithdrefn ei hun.

Dyma ddiffiniad eval:

(define (eval exp env)
  (cond ((self-evaluating? exp) 
         exp)
        ((variable? exp) 
         (lookup-variable-value exp env))
        ((quoted? exp) 
         (text-of-quotation exp))
        ((assignment? exp) 
         (eval-assignment exp env))
        ((definition? exp) 
         (eval-definition exp env))
        ((if? exp) 
         (eval-if exp env))
        ((lambda? exp)
         (make-procedure 
          (lambda-parameters exp)
          (lambda-body exp)
          env))
        ((begin? exp)
         (eval-sequence 
          (begin-actions exp) 
          env))
        ((cond? exp) 
         (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values 
                 (operands exp) 
                 env)))
        (else
         (error "Unknown expression 
                 type: EVAL" exp))))

Er eglurder, gweithredwyd eval fel dadansoddiad achosion gan ddefnyddio cond. Anfantais hyn yw mai dim ond ychydig o fathau gwahaniaethadwy o fynegiadau y mae ein gweithdrefn yn eu trin, ac ni ellir diffinio rhai newydd heb olygu diffiniad eval. Yn y rhan fwyaf o weithrediadau Lisp, detholiad gweithdrefn yn ôl math mynegiad a wneir mewn arddull a gyfarwyddir gan ddata. Mae hyn yn caniatáu i ddefnyddiwr ychwanegu mathau newydd o fynegiadau y gall eval eu gwahaniaethu, heb addasu diffiniad eval ei hun. (Gweler Ymarfer 4.3.)

Apply

Mae Apply yn cymryd dau arg: gweithdrefn a rhestr o argiau y dylid cymhwyso’r weithdrefn iddynt. Mae Apply yn dosbarthu gweithdrefnau yn ddau fath: mae’n galw apply-primitive-procedure i gymhwyso gweithdrefnau cyntefig; mae’n cymhwyso gweithdrefnau cyfansawdd drwy werthuso’r mynegiadau sy’n ffurfio corff y weithdrefn yn eu trefn. Adeiledir yr amgylchedd ar gyfer gwerthuso corff gweithdrefn gyfansawdd drwy estyn yr amgylchedd sylfaenol a gludir gan y weithdrefn i gynnwys ffrâm sy’n rhwymo paramedrau’r weithdrefn i’r argiau y cymhwysir y weithdrefn iddynt. Dyma ddiffiniad apply:

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure 
          procedure 
          arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters 
              procedure)
             arguments
             (procedure-environment 
              procedure))))
        (else
         (error "Unknown procedure 
                 type: APPLY" 
                procedure))))

Argiau gweithdrefn

Pan fydd eval yn prosesu cymhwysiad gweithdrefn, mae’n defnyddio list-of-values i gynhyrchu’r rhestr o argiau y cymhwysir y weithdrefn iddynt. Mae List-of-values yn cymryd operandau’r cyfuniad yn arg. Mae’n gwerthuso pob operand ac yn dychwelyd rhestr o’r gwerthoedd cyfatebol:²⁰⁹

(define (list-of-values exps env)
  (if (no-operands? exps)
      '()
      (cons (eval (first-operand exps) env)
            (list-of-values 
             (rest-operands exps) 
             env))))

Mynegiadau amodol

Mae Eval-if yn gwerthuso rhan draethol mynegiad if yn yr amgylchedd a roddwyd. Os yw’r canlyniad yn wir, mae eval-if yn gwerthuso’r canlyniadol; fel arall mae’n gwerthuso’r dewis arall:

(define (eval-if exp env)
  (if (true? (eval (if-predicate exp) env))
      (eval (if-consequent exp) env)
      (eval (if-alternative exp) env)))

Mae defnyddio true? yn eval-if yn amlygu’r cysylltiad rhwng iaith sy’n cael ei gweithredu ac iaith y gweithrediad. Gwerthusir if-predicate yn yr iaith sy’n cael ei gweithredu, ac felly mae’n cynhyrchu gwerth yn yr iaith honno. Mae traethiad y dehonglydd true? yn trosi’r gwerth hwnnw yn werth y gellir ei brofi gan if yn iaith y gweithrediad: gallai’r gynrychiolaeth fetagylchol o wirionedd fod yn wahanol i gynrychiolaeth y Scheme sylfaenol.²¹⁰

Dilyniannau

Defnyddir Eval-sequence gan apply i werthuso’r dilyniant o fynegiadau yng nghorff gweithdrefn, a chan eval i werthuso’r dilyniant o fynegiadau mewn mynegiad begin. Mae’n cymryd dilyniant o fynegiadau ac amgylchedd yn argiau, ac yn gwerthuso’r mynegiadau yn y drefn y maent yn ymddangos ynddi. Y gwerth a ddychwelir yw gwerth y mynegiad olaf.

(define (eval-sequence exps env)
  (cond ((last-exp? exps) 
         (eval (first-exp exps) env))
        (else 
         (eval (first-exp exps) env)
         (eval-sequence (rest-exps exps) 
                        env))))

Aseiniadau a diffiniadau

Mae’r weithdrefn ganlynol yn trin aseiniadau i newidynnau. Mae’n galw eval i ganfod y gwerth sydd i’w aseinio, ac yn trosglwyddo’r newidyn a’r gwerth canlyniadol i set-variable-value! i’w gosod yn yr amgylchedd penodedig.

(define (eval-assignment exp env)
  (set-variable-value! 
   (assignment-variable exp)
   (eval (assignment-value exp) env)
   env)
  'ok)

Trinnir diffiniadau o newidynnau mewn ffordd debyg.²¹¹

(define (eval-definition exp env)
  (define-variable! 
    (definition-variable exp)
    (eval (definition-value exp) env)
    env)
  'ok)

Rydym wedi dewis yma ddychwelyd y symbol ok fel gwerth aseiniad neu ddiffiniad.²¹²

Ymarfer 4.1: Sylwch na allwn ddweud a yw’r gwerthusydd metagylchol yn gwerthuso operandau o’r chwith i’r dde neu o’r dde i’r chwith. Etifeddir ei drefn werthuso o’r Lisp sylfaenol: os gwerthusir yr argiau i cons yn list-of-values o’r chwith i’r dde, yna bydd list-of-values yn gwerthuso operandau o’r chwith i’r dde; ac os gwerthusir yr argiau i cons o’r dde i’r chwith, yna bydd list-of-values yn gwerthuso operandau o’r dde i’r chwith.

Ysgrifennwch fersiwn o list-of-values sy’n gwerthuso operandau o’r chwith i’r dde, waeth beth fo trefn werthuso’r Lisp sylfaenol. Ysgrifennwch hefyd fersiwn o list-of-values sy’n gwerthuso operandau o’r dde i’r chwith.

4.1.2Cynrychioli mynegiadau

Mae’r gwerthusydd yn atgoffa rhywun o’r rhaglen differu symbolaidd a drafodwyd yn 2.3.2. Mae’r ddwy raglen yn gweithredu ar fynegiadau symbolaidd. Yn y ddwy raglen, pennir canlyniad gweithredu ar fynegiad cyfansawdd drwy weithredu’n ddychweliadol ar rannau’r mynegiad a chyfuno’r canlyniadau mewn ffordd sy’n dibynnu ar fath y mynegiad. Yn y ddwy raglen defnyddiwyd haniaethu data i wahanu rheolau cyffredinol y gweithredu oddi wrth fanylion cynrychioli mynegiadau. Yn y rhaglen ddifferu, golygai hyn y gallai’r un weithdrefn ddifferu ymdrin â mynegiadau algebraidd mewn ffurf ragddodol, mewn ffurf fewnddodol, neu mewn rhyw ffurf arall. I’r gwerthusydd, mae hyn yn golygu mai’r gweithdrefnau sy’n dosbarthu ac yn echdynnu rhannau o fynegiadau yn unig sy’n pennu cystrawen yr iaith a werthusir.

Dyma fanyleb cystrawen ein hiaith:

• Rhifau a llinynnau yw’r unig eitemau sy’n gwerthuso i’w hunain:

  (define (self-evaluating? exp)
    (cond ((number? exp) true)
          ((string? exp) true)
          (else false)))

• Cynrychiolir newidynnau gan symbolau:

  (define (variable? exp) (symbol? exp))

• Mae dyfyniadau ar y ffurf (quote ⟨text-of-quotation⟩):²¹³

  (define (quoted? exp)
    (tagged-list? exp 'quote))
  
  (define (text-of-quotation exp)
    (cadr exp))

  Diffinnir Quoted? yn nhermau’r weithdrefn tagged-list?, sy’n adnabod rhestrau sy’n dechrau â symbol penodedig:

  (define (tagged-list? exp tag)
    (if (pair? exp)
        (eq? (car exp) tag)
        false))

• Mae aseiniadau ar y ffurf (set! ⟨var⟩ ⟨value⟩):

  (define (assignment? exp)
    (tagged-list? exp 'set!))
  
  (define (assignment-variable exp) 
    (cadr exp))
  
  (define (assignment-value exp) (caddr exp))

• Mae diffiniadau ar y ffurf

  (define ⟨var⟩ ⟨value⟩)

  neu ar y ffurf

  (define (⟨var⟩ ⟨param₁⟩ … ⟨paramₙ⟩)
    ⟨body⟩)

  Siwgr cystrawennol yw’r ail ffurf (diffiniad gweithdrefn safonol) ar gyfer

  (define ⟨var⟩
    (lambda (⟨param₁⟩ … ⟨paramₙ⟩)
      ⟨body⟩))

  Dyma’r gweithdrefnau cystrawen cyfatebol:

  (define (definition? exp)
    (tagged-list? exp 'define))
  
  (define (definition-variable exp)
    (if (symbol? (cadr exp))
        (cadr exp)
        (caadr exp)))
  
  (define (definition-value exp)
    (if (symbol? (cadr exp))
        (caddr exp)
        (make-lambda 
         (cdadr exp)   ; formal parameters
         (cddr exp)))) ; body
  

• Rhestrau sy’n dechrau â’r symbol lambda yw mynegiadau Lambda:

  (define (lambda? exp) 
    (tagged-list? exp 'lambda))
  (define (lambda-parameters exp) (cadr exp))
  (define (lambda-body exp) (cddr exp))

  Darparwn hefyd adeiladydd ar gyfer mynegiadau lambda, a ddefnyddir gan definition-value uchod:

  (define (make-lambda parameters body)
    (cons 'lambda (cons parameters body)))

• Mae mynegiadau amodol yn dechrau ag if ac yn cynnwys traethiad, canlyniadol, a dewis arall (dewisol). Os nad oes gan y mynegiad ran ar gyfer y dewis arall, darparwn false yn ddewis arall.²¹⁴

  (define (if? exp) (tagged-list? exp 'if))
  (define (if-predicate exp) (cadr exp))
  (define (if-consequent exp) (caddr exp))
  (define (if-alternative exp)
    (if (not (null? (cdddr exp)))
        (cadddr exp)
        'false))

  Darparwn hefyd adeiladydd ar gyfer mynegiadau if, i’w ddefnyddio gan cond->if i drawsffurfio mynegiadau cond yn fynegiadau if:

  (define (make-if predicate 
                   consequent 
                   alternative)
    (list 'if 
          predicate 
          consequent 
          alternative))

• Mae Begin yn pecynnu dilyniant o fynegiadau yn un mynegiad. Cynhwyswn weithrediadau cystrawen ar fynegiadau begin i echdynnu’r dilyniant ei hun o’r mynegiad begin, yn ogystal â detholwyr sy’n dychwelyd y mynegiad cyntaf a gweddill mynegiadau’r dilyniant.²¹⁵

  (define (begin? exp) 
    (tagged-list? exp 'begin))
  (define (begin-actions exp) (cdr exp))
  (define (last-exp? seq) (null? (cdr seq)))
  (define (first-exp seq) (car seq))
  (define (rest-exps seq) (cdr seq))

  Cynhwyswn hefyd adeiladydd sequence->exp (i’w ddefnyddio gan cond->if) sy’n trawsffurfio dilyniant yn un mynegiad, gan ddefnyddio begin os oes angen:

  (define (sequence->exp seq)
    (cond ((null? seq) seq)
          ((last-exp? seq) (first-exp seq))
          (else (make-begin seq))))
  
  (define (make-begin seq) (cons 'begin seq))

• Cymhwysiad gweithdrefn yw unrhyw fynegiad cyfansawdd nad yw’n un o’r mathau uchod o fynegiadau. car y mynegiad yw’r gweithredydd, ac cdr yw’r rhestr o operandau:

  (define (application? exp) (pair? exp))
  (define (operator exp) (car exp))
  (define (operands exp) (cdr exp))
  (define (no-operands? ops) (null? ops))
  (define (first-operand ops) (car ops))
  (define (rest-operands ops) (cdr ops))

Mynegiadau deilliedig

Gellir diffinio rhai ffurfiau arbennig yn ein hiaith yn nhermau mynegiadau sy’n cynnwys ffurfiau arbennig eraill, yn hytrach na’u gweithredu’n uniongyrchol. Un enghraifft yw cond, y gellir ei weithredu fel nyth o fynegiadau if. Er enghraifft, gallwn leihau’r broblem o werthuso’r mynegiad

(cond ((> x 0) x)
      ((= x 0) (display 'zero) 0)
      (else (- x)))

i’r broblem o werthuso’r mynegiad canlynol sy’n cynnwys mynegiadau if ac begin:

(if (> x 0)
    x
    (if (= x 0)
        (begin (display 'zero) 0)
        (- x)))

Mae gweithredu gwerthuso cond yn y ffordd hon yn symleiddio’r gwerthusydd, gan ei fod yn lleihau nifer y ffurfiau arbennig y mae’n rhaid pennu eu proses werthuso yn benodol.

Cynhwyswn weithdrefnau cystrawen sy’n echdynnu rhannau mynegiad cond, a gweithdrefn cond->if sy’n trawsffurfio mynegiadau cond yn fynegiadau if. Mae dadansoddiad achosion yn dechrau ag cond ac yn cynnwys rhestr o gymalau traethiad–gweithrediad. Mae cymal yn gymal else os mai’r symbol else yw ei draethiad.²¹⁶

(define (cond? exp) 
  (tagged-list? exp 'cond))
(define (cond-clauses exp) (cdr exp))
(define (cond-else-clause? clause)
  (eq? (cond-predicate clause) 'else))
(define (cond-predicate clause) 
  (car clause))
(define (cond-actions clause) 
  (cdr clause))
(define (cond->if exp)
  (expand-clauses (cond-clauses exp)))
(define (expand-clauses clauses)
  (if (null? clauses)
      'false     ; no else clause
      (let ((first (car clauses))
            (rest (cdr clauses)))
        (if (cond-else-clause? first)
            (if (null? rest)
                (sequence->exp 
                 (cond-actions first))
                (error "ELSE clause isn't 
                        last: COND->IF"
                       clauses))
            (make-if (cond-predicate first)
                     (sequence->exp 
                      (cond-actions first))
                     (expand-clauses 
                      rest))))))

Gelwir mynegiadau (megis cond) y dewiswn eu gweithredu fel trawsffurfiadau cystrawennol yn fynegiadau deilliedig. Mae mynegiadau Let hefyd yn fynegiadau deilliedig (gweler Ymarfer 4.6).²¹⁷

Ymarfer 4.2: Mae Louis Reasoner yn bwriadu aildrefnu cymalau cond yn eval fel bod y cymal ar gyfer cymwysiadau gweithdrefn yn ymddangos cyn y cymal ar gyfer aseiniadau. Mae’n dadlau y bydd hyn yn gwneud y dehonglydd yn fwy effeithlon: gan fod rhaglenni fel arfer yn cynnwys mwy o gymwysiadau nag o aseiniadau, diffiniadau ac ati, bydd ei eval addasedig fel arfer yn gwirio llai o gymalau na’r eval gwreiddiol cyn adnabod math mynegiad.

1. Beth sydd o’i le ar gynllun Louis? (Awgrym: beth fydd gwerthusydd Louis yn ei wneud â’r mynegiad (define x 3)?)
2. Mae Louis yn siomedig na weithiodd ei gynllun. Mae’n barod i wneud unrhyw beth i beri i’w werthusydd adnabod cymwysiadau gweithdrefn cyn iddo wirio am y rhan fwyaf o’r mathau eraill o fynegiadau. Helpwch ef drwy newid cystrawen yr iaith a werthusir fel bod cymwysiadau gweithdrefn yn dechrau ag call. Er enghraifft, yn lle (factorial 3) bydd yn rhaid inni bellach ysgrifennu (call factorial 3), ac yn lle (+ 1 2) bydd yn rhaid inni ysgrifennu (call + 1 2).

Ymarfer 4.3: Ailysgrifennwch eval fel y detholer y weithdrefn mewn arddull a gyfarwyddir gan ddata. Cymharwch hyn â’r weithdrefn ddifferu a gyfarwyddir gan ddata yn Ymarfer 2.73. (Cewch ddefnyddio car mynegiad cyfansawdd fel math y mynegiad, fel sy’n briodol i’r gystrawen a weithredir yn yr adran hon.)

Ymarfer 4.4: Cofiwch ddiffiniadau’r ffurfiau arbennig and ac or o Bennod 1:

• and: Gwerthusir y mynegiadau o’r chwith i’r dde. Os yw unrhyw fynegiad yn gwerthuso i anwir, dychwelir anwir; ni werthusir unrhyw fynegiadau sy’n weddill. Os yw pob mynegiad yn gwerthuso i werth gwir, dychwelir gwerth y mynegiad olaf. Os nad oes mynegiadau, dychwelir gwir.
• or: Gwerthusir y mynegiadau o’r chwith i’r dde. Os yw unrhyw fynegiad yn gwerthuso i werth gwir, dychwelir y gwerth hwnnw; ni werthusir unrhyw fynegiadau sy’n weddill. Os yw pob mynegiad yn gwerthuso i anwir, neu os nad oes mynegiadau, dychwelir anwir.

Gosodwch and ac or yn ffurfiau arbennig newydd i’r gwerthusydd drwy ddiffinio gweithdrefnau cystrawen priodol a gweithdrefnau gwerthuso eval-and ac eval-or. Fel dewis arall, dangoswch sut i weithredu and ac or fel mynegiadau deilliedig.

Ymarfer 4.5: Mae Scheme yn caniatáu cystrawen ychwanegol ar gyfer cymalau cond, sef (⟨test⟩ => ⟨recipient⟩). Os yw ⟨test⟩ yn gwerthuso i werth gwir, yna gwerthusir ⟨recipient⟩. Rhaid i’w werth fod yn weithdrefn un arg; yna gelwir y weithdrefn hon ar werth ⟨test⟩, a dychwelir y canlyniad fel gwerth y mynegiad cond. Er enghraifft

(cond ((assoc 'b '((a 1) (b 2))) => cadr)
      (else false))

mae hyn yn dychwelyd 2. Addaswch y ffordd y trinnir cond fel ei bod yn cefnogi’r gystrawen estynedig hon.

Ymarfer 4.6: Mynegiadau deilliedig yw mynegiadau Let, oherwydd mae

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

yn gyfwerth â

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

Gweithredwch drawsffurfiad cystrawennol let->combination sy’n lleihau gwerthuso mynegiadau let i werthuso cyfuniadau o’r math a ddangosir uchod, ac ychwanegwch y cymal priodol at eval i drin mynegiadau let.

Ymarfer 4.7: Mae Let* yn debyg i let, ac eithrio bod rhwymiadau newidynnau let* yn cael eu gwneud yn eu trefn o’r chwith i’r dde, a gwneir pob rhwymiad mewn amgylchedd lle mae’r holl rwymiadau blaenorol yn weladwy. Er enghraifft

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

mae hyn yn dychwelyd 39. Esboniwch sut y gellir ailysgrifennu mynegiad let* fel set o fynegiadau let nythol, ac ysgrifennwch weithdrefn let*->nested-lets sy’n cyflawni’r trawsffurfiad hwn. Os ydym eisoes wedi gweithredu let (Ymarfer 4.6) ac am estyn y gwerthusydd i drin let*, a yw’n ddigon ychwanegu cymal at eval a’i weithrediad yn

(eval (let*->nested-lets exp) env)

neu a oes rhaid inni ehangu let* yn benodol yn nhermau mynegiadau nad ydynt yn ddeilliedig?

Ymarfer 4.8: Amrywiad ar let sydd ar y ffurf ganlynol yw “let wedi’i enwi”

(let ⟨var⟩ ⟨bindings⟩ ⟨body⟩)

Mae ⟨bindings⟩ ac ⟨body⟩ yn union fel mewn let arferol, ac eithrio bod ⟨var⟩ wedi’i rwymo o fewn ⟨body⟩ i weithdrefn y mae ei chorff yn ⟨body⟩ a’i pharamedrau yn newidynnau ⟨bindings⟩. Felly gellir rhedeg ⟨body⟩ dro ar ôl tro drwy alw’r weithdrefn o’r enw ⟨var⟩. Er enghraifft, gellir ailysgrifennu’r weithdrefn Fibonacci sy’n iteru (1.2.2) gan ddefnyddio let wedi’i enwi fel a ganlyn:

(define (fib n)
  (let fib-iter ((a 1) (b 0) (count n))
    (if (= count 0)
        b
        (fib-iter (+ a b) 
                  a 
                  (- count 1)))))

Addaswch let->combination yn Ymarfer 4.6 i gefnogi let wedi’i enwi hefyd.

Ymarfer 4.9: Mae llawer o ieithoedd yn cefnogi amrywiaeth o gystrawennau iteru, megis do, for, while ac until. Yn Scheme, gellir mynegi prosesau iteru yn nhermau galwadau gweithdrefn arferol, felly nid yw cystrawennau iteru arbennig yn ychwanegu dim at y pŵer cyfrifiannu hanfodol. Ar y llaw arall, mae cystrawennau o’r fath yn aml yn gyfleus. Dyluniwch rai cystrawennau iteru, rhowch enghreifftiau o’u defnydd, a dangoswch sut i’w gweithredu fel mynegiadau deilliedig.

Ymarfer 4.10: Drwy ddefnyddio haniaethu data, llwyddwyd i ysgrifennu gweithdrefn eval sy’n annibynnol ar gystrawen benodol yr iaith sydd i’w gwerthuso. I ddangos hyn, dyluniwch a gweithredwch gystrawen newydd ar gyfer Scheme drwy addasu’r gweithdrefnau yn yr adran hon, heb newid eval nac apply.

4.1.3Strwythurau data’r gwerthusydd

Yn ogystal â diffinio cystrawen allanol mynegiadau, rhaid i weithrediad y gwerthusydd hefyd ddiffinio’r strwythurau data y mae’r gwerthusydd yn eu trin yn fewnol fel rhan o redeg rhaglen, megis cynrychiolaeth gweithdrefnau ac amgylcheddau a chynrychiolaeth gwir ac anwir.

Profi traethiadau

Ar gyfer mynegiadau amodol, derbyniwn yn wir unrhyw beth nad yw’n wrthrych false penodol.

(define (true? x)
  (not (eq? x false)))

(define (false? x)
  (eq? x false))

Cynrychioli gweithdrefnau

I drin gweithdrefnau cyntefig, tybiwn fod y gweithdrefnau canlynol ar gael:

• (apply-primitive-procedure ⟨proc⟩ ⟨args⟩)

  yn cymhwyso’r weithdrefn gyntefig a roddwyd i’r gwerthoedd arg yn y rhestr ⟨args⟩ ac yn dychwelyd canlyniad y cymhwyso.

• (primitive-procedure? ⟨proc⟩)

  yn profi a yw ⟨proc⟩ yn weithdrefn gyntefig.

Disgrifir y mecanweithiau hyn ar gyfer trin gweithdrefnau cyntefig ymhellach yn 4.1.4.

Adeiledir gweithdrefnau cyfansawdd o baramedrau, cyrff gweithdrefnau ac amgylcheddau gan ddefnyddio’r adeiladydd make-procedure:

(define (make-procedure parameters body env)
  (list 'procedure parameters body env))
(define (compound-procedure? p)
  (tagged-list? p 'procedure))
(define (procedure-parameters p) (cadr p))
(define (procedure-body p) (caddr p))
(define (procedure-environment p) (cadddr p))

Gweithrediadau ar amgylcheddau

Mae angen gweithrediadau ar y gwerthusydd i drin amgylcheddau. Fel yr esboniwyd yn 3.2, dilyniant o fframiau yw amgylchedd, lle mae pob ffrâm yn dabl o rwymiadau sy’n cysylltu newidynnau â’u gwerthoedd cyfatebol. Defnyddiwn y gweithrediadau canlynol i drin amgylcheddau:

• (lookup-variable-value ⟨var⟩ ⟨env⟩)

  yn dychwelyd y gwerth sydd wedi’i rwymo i’r symbol ⟨var⟩ yn yr amgylchedd ⟨env⟩, neu’n arwyddo gwall os yw’r newidyn yn ddi-rwym.

• (extend-environment ⟨variables⟩ ⟨values⟩ ⟨base-env⟩)

  yn dychwelyd amgylchedd newydd, sy’n cynnwys ffrâm newydd lle mae’r symbolau yn y rhestr ⟨variables⟩ wedi’u rhwymo i’r elfennau cyfatebol yn y rhestr ⟨values⟩, a’r amgylchedd amgylchynol yw’r amgylchedd ⟨base-env⟩.

• (define-variable! ⟨var⟩ ⟨value⟩ ⟨env⟩)

  yn ychwanegu at ffrâm gyntaf yr amgylchedd ⟨env⟩ rwymiad newydd sy’n cysylltu’r newidyn ⟨var⟩ â’r gwerth ⟨value⟩.

• (set-variable-value! ⟨var⟩ ⟨value⟩ ⟨env⟩)

  yn newid rhwymiad y newidyn ⟨var⟩ yn yr amgylchedd ⟨env⟩ fel bod y newidyn bellach wedi’i rwymo i’r gwerth ⟨value⟩, neu’n arwyddo gwall os yw’r newidyn yn ddi-rwym.

I weithredu’r gweithrediadau hyn, cynrychiolwn amgylchedd fel rhestr o fframiau. Amgylchedd amgylchynol amgylchedd yw cdr y rhestr. Yr amgylchedd gwag yw’r rhestr wag yn unig.

(define (enclosing-environment env) (cdr env))
(define (first-frame env) (car env))
(define the-empty-environment '())

Cynrychiolir pob ffrâm mewn amgylchedd fel pâr o restrau: rhestr o’r newidynnau sydd wedi’u rhwymo yn y ffrâm honno, a rhestr o’r gwerthoedd cysylltiedig.²¹⁸

(define (make-frame variables values)
  (cons variables values))
(define (frame-variables frame) (car frame))
(define (frame-values frame) (cdr frame))
(define (add-binding-to-frame! var val frame)
  (set-car! frame (cons var (car frame)))
  (set-cdr! frame (cons val (cdr frame))))

I estyn amgylchedd â ffrâm newydd sy’n cysylltu newidynnau â gwerthoedd, gwnawn ffrâm sy’n cynnwys y rhestr o newidynnau a’r rhestr o werthoedd, ac ychwanegwn hon at yr amgylchedd. Arwyddwn wall os nad yw nifer y newidynnau yn cyfateb i nifer y gwerthoedd.

(define (extend-environment vars vals base-env)
  (if (= (length vars) (length vals))
      (cons (make-frame vars vals) base-env)
      (if (< (length vars) (length vals))
          (error "Too many arguments supplied" 
                 vars 
                 vals)
          (error "Too few arguments supplied" 
                 vars 
                 vals))))

I chwilio am newidyn mewn amgylchedd, sganiwn restr y newidynnau yn y ffrâm gyntaf. Os canfyddwn y newidyn a geisir, dychwelwn yr elfen gyfatebol yn y rhestr o werthoedd. Os na chanfyddwn y newidyn yn y ffrâm gyfredol, chwiliwn yn yr amgylchedd amgylchynol, ac yn y blaen. Os cyrhaeddwn yr amgylchedd gwag, arwyddwn wall “newidyn di-rwym”.

(define (lookup-variable-value var env)
  (define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars)
             (env-loop 
              (enclosing-environment env)))
            ((eq? var (car vars))
             (car vals))
            (else (scan (cdr vars) 
                        (cdr vals)))))
    (if (eq? env the-empty-environment)
        (error "Unbound variable" var)
        (let ((frame (first-frame env)))
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))

I osod gwerth newydd i newidyn mewn amgylchedd penodedig, sganiwn am y newidyn, yn union fel yn lookup-variable-value, a newidiwn y gwerth cyfatebol pan ganfyddwn ef.

(define (set-variable-value! var val env)
  (define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars)
             (env-loop 
              (enclosing-environment env)))
            ((eq? var (car vars))
             (set-car! vals val))
            (else (scan (cdr vars) 
                        (cdr vals)))))
    (if (eq? env the-empty-environment)
        (error "Unbound variable: SET!" var)
        (let ((frame (first-frame env)))
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))

I ddiffinio newidyn, chwiliwn y ffrâm gyntaf am rwymiad i’r newidyn, a newidiwn y rhwymiad os yw’n bodoli (yn union fel yn set-variable-value!). Os nad oes rhwymiad o’r fath, ychwanegwn un at y ffrâm gyntaf.

(define (define-variable! var val env)
  (let ((frame (first-frame env)))
    (define (scan vars vals)
      (cond ((null? vars)
             (add-binding-to-frame! 
              var val frame))
            ((eq? var (car vars))
             (set-car! vals val))
            (else (scan (cdr vars) 
                        (cdr vals)))))
    (scan (frame-variables frame)
          (frame-values frame))))

Dim ond un o lawer o ffyrdd credadwy o gynrychioli amgylcheddau yw’r dull a ddisgrifir yma. Gan inni ddefnyddio haniaethu data i ynysu gweddill y gwerthusydd oddi wrth fanylion y dewis o gynrychiolaeth, gallem newid cynrychiolaeth yr amgylchedd pe dymunem. (Gweler Ymarfer 4.11.) Mewn system Lisp o ansawdd cynhyrchu, mae cyflymder gweithrediadau amgylchedd y gwerthusydd—yn enwedig chwilio am newidynnau—yn cael effaith fawr ar berfformiad y system. Er bod y gynrychiolaeth a ddisgrifir yma’n syml yn gysyniadol, nid yw’n effeithlon ac ni fyddai fel arfer yn cael ei defnyddio mewn system gynhyrchu.²¹⁹

Ymarfer 4.11: Yn lle cynrychioli ffrâm fel pâr o restrau, gallwn gynrychioli ffrâm fel rhestr o rwymiadau, lle mae pob rhwymiad yn bâr enw–gwerth. Ailysgrifennwch y gweithrediadau amgylchedd i ddefnyddio’r gynrychiolaeth amgen hon.

Ymarfer 4.12: Gellir mynegi’r gweithdrefnau define-variable!, set-variable-value! ac lookup-variable-value yn nhermau gweithdrefnau mwy haniaethol ar gyfer tramwyo strwythur yr amgylchedd. Diffiniwch haniaethau sy’n dal y patrymau cyffredin, ac ailddiffiniwch y tair gweithdrefn yn nhermau’r haniaethau hyn.

Ymarfer 4.13: Mae Scheme yn ein galluogi i greu rhwymiadau newydd i newidynnau drwy define, ond nid yw’n darparu ffordd o gael gwared ar rwymiadau. Gweithredwch ffurf arbennig make-unbound! ar gyfer y gwerthusydd sy’n dileu rhwymiad symbol penodol o’r amgylchedd lle gwerthusir y mynegiad make-unbound!. Nid yw’r broblem hon wedi’i phennu’n llawn. Er enghraifft, ai dim ond y rhwymiad yn ffrâm gyntaf yr amgylchedd y dylem ei ddileu? Cwblhewch y fanyleb a chyfiawnhewch unrhyw ddewisiadau a wnewch.

4.1.4Rhedeg y gwerthusydd fel rhaglen

Gyda’r gwerthusydd, mae gennym ddisgrifiad (wedi’i fynegi yn Lisp) o’r broses sy’n gwerthuso mynegiadau Lisp. Un fantais mynegi’r gwerthusydd fel rhaglen yw y gallwn redeg y rhaglen. Mae hyn yn rhoi inni, yn rhedeg o fewn Lisp, fodel gweithredol o’r ffordd y mae Lisp ei hun yn gwerthuso mynegiadau. Gall hyn fod yn fframwaith ar gyfer arbrofi â rheolau gwerthuso, fel y gwnawn yn ddiweddarach yn y bennod hon.

Mae ein rhaglen gwerthusydd yn lleihau mynegiadau yn y pen draw i gymhwyso gweithdrefnau cyntefig. Felly, y cyfan sydd ei angen arnom i redeg y gwerthusydd yw creu mecanwaith sy’n galw ar y system Lisp sylfaenol i fodelu cymhwyso gweithdrefnau cyntefig.

Rhaid cael rhwymiad i enw pob gweithdrefn gyntefig, fel y bydd eval, wrth werthuso gweithredydd cymhwysiad gweithdrefn gyntefig, yn dod o hyd i wrthrych i’w drosglwyddo i apply. Felly sefydlwn amgylchedd byd-eang sy’n cysylltu gwrthrychau unigryw ag enwau’r gweithdrefnau cyntefig a all ymddangos yn y mynegiadau y byddwn yn eu gwerthuso. Mae’r amgylchedd byd-eang hefyd yn cynnwys rhwymiadau i’r symbolau true ac false, fel y gellir eu defnyddio’n newidynnau mewn mynegiadau sydd i’w gwerthuso.

(define (setup-environment)
  (let ((initial-env
         (extend-environment 
          (primitive-procedure-names)
          (primitive-procedure-objects)
          the-empty-environment)))
    (define-variable! 'true true initial-env)
    (define-variable! 'false false initial-env)
    initial-env))

(define the-global-environment 
  (setup-environment))

Nid oes gwahaniaeth sut y cynrychiolwn wrthrychau’r gweithdrefnau cyntefig, cyhyd ag y gall apply eu hadnabod a’u cymhwyso drwy ddefnyddio’r gweithdrefnau primitive-procedure? ac apply-primitive-procedure. Rydym wedi dewis cynrychioli gweithdrefn gyntefig fel rhestr sy’n dechrau â’r symbol primitive ac yn cynnwys gweithdrefn yn y Lisp sylfaenol sy’n gweithredu’r weithdrefn gyntefig honno.

(define (primitive-procedure? proc)
  (tagged-list? proc 'primitive))

(define (primitive-implementation proc) 
  (cadr proc))

Bydd Setup-environment yn cael enwau’r gweithdrefnau cyntefig a’u gweithdrefnau gweithredu o restr:²²⁰

(define primitive-procedures
  (list (list 'car car)
        (list 'cdr cdr)
        (list 'cons cons)
        (list 'null? null?)
        ⟨more primitives⟩ ))

(define (primitive-procedure-names)
  (map car primitive-procedures))

(define (primitive-procedure-objects)
  (map (lambda (proc) 
         (list 'primitive (cadr proc)))
       primitive-procedures))

I gymhwyso gweithdrefn gyntefig, cymhwyswn ei gweithdrefn weithredu i’r argiau, gan ddefnyddio’r system Lisp sylfaenol:²²¹

(define (apply-primitive-procedure proc args)
  (apply-in-underlying-scheme
   (primitive-implementation proc) args))

Er hwylustod wrth redeg y gwerthusydd metagylchol, darparwn ddolen yrru sy’n modelu dolen darllen–gwerthuso–argraffu’r system Lisp sylfaenol. Mae’n argraffu anogwr, yn darllen mynegiad mewnbwn, yn gwerthuso’r mynegiad hwn yn yr amgylchedd byd-eang, ac yn argraffu’r canlyniad. Rhoir anogwr allbwn o flaen pob canlyniad a argreffir er mwyn gwahaniaethu gwerth y mynegiad oddi wrth allbwn arall a all gael ei argraffu.²²²

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

(define (driver-loop)
  (prompt-for-input input-prompt)
  (let ((input (read)))
    (let ((output 
           (eval input 
                 the-global-environment)))
      (announce-output output-prompt)
      (user-print output)))
  (driver-loop))

(define (prompt-for-input string)
  (newline) (newline) 
  (display string) (newline))

(define (announce-output string)
  (newline) (display string) (newline))

Defnyddiwn weithdrefn argraffu arbennig, user-print, i osgoi argraffu rhan amgylchedd gweithdrefn gyfansawdd, a all fod yn rhestr hir iawn (neu hyd yn oed gynnwys cylchoedd).

(define (user-print object)
  (if (compound-procedure? object)
      (display 
       (list 'compound-procedure
             (procedure-parameters object)
             (procedure-body object)
             '<procedure-env>))
      (display object)))

Bellach, y cyfan sydd angen inni ei wneud i redeg y gwerthusydd yw cychwyn yr amgylchedd byd-eang a dechrau’r ddolen yrru. Dyma enghraifft o ryngweithio:

(define the-global-environment 
  (setup-environment))

(driver-loop)

;;; M-Eval input:
(define (append x y)
  (if (null? x)
      y
      (cons (car x) (append (cdr x) y))))

;;; M-Eval value:
ok

;;; M-Eval input:
(append '(a b c) '(d e f))

;;; M-Eval value:
(a b c d e f)

Ymarfer 4.14: Mae Eva Lu Ator a Louis Reasoner ill dau yn arbrofi â’r gwerthusydd metagylchol. Mae Eva yn teipio diffiniad map ac yn rhedeg rhai rhaglenni prawf sy’n ei ddefnyddio. Maent yn gweithio’n iawn. Mewn cyferbyniad, mae Louis wedi gosod fersiwn y system o map yn weithdrefn gyntefig i’r gwerthusydd metagylchol. Pan mae’n rhoi cynnig arno, mae pethau’n mynd yn ofnadwy o chwith. Esboniwch pam mae map Louis yn methu er bod un Eva yn gweithio.

4.1.5Data fel rhaglenni

Wrth feddwl am raglen Lisp sy’n gwerthuso mynegiadau Lisp, gallai cyfatebiaeth fod o gymorth. Un golwg weithredol ar ystyr rhaglen yw bod rhaglen yn ddisgrifiad o beiriant haniaethol (a all fod yn anfeidrol fawr). Er enghraifft, ystyriwch y rhaglen gyfarwydd i gyfrifo ffactorialau:

(define (factorial n)
  (if (= n 1)
      1
      (* (factorial (- n 1)) n)))

Gallwn ystyried y rhaglen hon yn ddisgrifiad o beiriant sy’n cynnwys rhannau sy’n lleihau un, yn lluosi ac yn profi am hafaledd, ynghyd â switsh dau safle a pheiriant ffactorial arall. (Mae’r peiriant ffactorial yn anfeidrol oherwydd ei fod yn cynnwys peiriant ffactorial arall ynddo.) Diagram llif o’r peiriant ffactorial yw Ffigur 4.2, sy’n dangos sut mae’r rhannau wedi’u cysylltu â’i gilydd.

Mewn ffordd debyg, gallwn ystyried y gwerthusydd yn beiriant arbennig iawn sy’n cymryd disgrifiad o beiriant yn fewnbwn. O gael y mewnbwn hwn, mae’r gwerthusydd yn ei ffurfweddu ei hun i efelychu’r peiriant a ddisgrifir. Er enghraifft, os rhown ddiffiniad factorial i’n gwerthusydd, fel y dangosir yn Ffigur 4.3, bydd y gwerthusydd yn gallu cyfrifo ffactorialau.

O’r safbwynt hwn, gwelir bod ein gwerthusydd yn beiriant cyffredinol. Mae’n dynwared peiriannau eraill pan gânt eu disgrifio fel rhaglenni Lisp.²²³ Mae hyn yn drawiadol. Ceisiwch ddychmygu gwerthusydd cyfatebol ar gyfer cylchedau trydanol. Byddai hwn yn gylched sy’n cymryd, yn fewnbwn, signal sy’n amgodio cynlluniau rhyw gylched arall, megis hidlydd. O gael y mewnbwn hwn, byddai gwerthusydd y gylched wedyn yn ymddwyn fel hidlydd â’r un disgrifiad. Mae cylched drydanol gyffredinol o’r fath bron yn annirnadwy o gymhleth. Mae’n rhyfeddol bod y gwerthusydd rhaglenni yn rhaglen gymharol syml.²²⁴

Agwedd drawiadol arall ar y gwerthusydd yw ei fod yn bont rhwng y gwrthrychau data a drinnir gan ein hiaith raglennu a’r iaith raglennu ei hun. Dychmygwch fod rhaglen y gwerthusydd (wedi’i gweithredu yn Lisp) yn rhedeg, a bod defnyddiwr yn teipio mynegiadau i’r gwerthusydd ac yn arsylwi ar y canlyniadau. O safbwynt y defnyddiwr, mae mynegiad mewnbwn megis (* x x) yn fynegiad yn yr iaith raglennu, y dylai’r gwerthusydd ei redeg. O safbwynt y gwerthusydd, fodd bynnag, dim ond rhestr yw’r mynegiad (yn yr achos hwn, rhestr o dri symbol: *, x ac x) sydd i’w thrin yn ôl set o reolau wedi’u diffinio’n dda.

Nid oes rhaid i’r ffaith mai rhaglenni’r defnyddiwr yw data’r gwerthusydd achosi dryswch. Yn wir, weithiau mae’n gyfleus anwybyddu’r gwahaniaeth hwn a rhoi’r gallu i’r defnyddiwr werthuso gwrthrych data yn benodol fel mynegiad Lisp, drwy ddarparu eval i’w ddefnyddio mewn rhaglenni. Mae llawer o dafodieithoedd Lisp yn darparu gweithdrefn gyntefig eval sy’n cymryd mynegiad ac amgylchedd yn argiau ac yn gwerthuso’r mynegiad mewn perthynas â’r amgylchedd.²²⁵ Felly, bydd

(eval '(* 5 5) user-initial-environment)

a

(eval (cons '* (list 5 5)) 
      user-initial-environment)

ill dau yn dychwelyd 25.²²⁶

Ymarfer 4.15: O gael gweithdrefn un arg p a gwrthrych a, dywedir bod p yn “terfynu” ar a os yw gwerthuso’r mynegiad (p a) yn dychwelyd gwerth (yn hytrach na gorffen â neges wall neu redeg am byth). Dangoswch ei bod yn amhosibl ysgrifennu gweithdrefn halts? sy’n pennu’n gywir a yw p yn terfynu ar a ar gyfer unrhyw weithdrefn p a gwrthrych a. Defnyddiwch yr ymresymiad canlynol: pe bai gennych weithdrefn o’r fath halts?, gallech weithredu’r rhaglen ganlynol:

(define (run-forever)
  (run-forever))

(define (try p)
  (if (halts? p p)
      (run-forever)
      'halted))

Ystyriwch yn awr werthuso’r mynegiad (try try) a dangoswch fod unrhyw ganlyniad posibl (naill ai terfynu neu redeg am byth) yn torri ymddygiad bwriadedig halts?.²²⁷

4.1.6Diffiniadau mewnol

Mae ein model amgylchedd o werthuso a’n gwerthusydd metagylchol yn gweithredu diffiniadau yn eu trefn, gan estyn ffrâm yr amgylchedd un diffiniad ar y tro. Mae hyn yn arbennig o gyfleus ar gyfer datblygu rhaglenni’n rhyngweithiol, lle mae angen i’r rhaglennydd gymysgu cymhwyso gweithdrefnau â diffinio gweithdrefnau newydd yn rhydd. Fodd bynnag, os meddyliwn yn ofalus am y diffiniadau mewnol a ddefnyddir i weithredu strwythur blociau (a gyflwynwyd yn 1.1.8), cawn nad estyn yr amgylchedd enw wrth enw yw’r ffordd orau o ddiffinio newidynnau lleol o reidrwydd.

Ystyriwch weithdrefn â diffiniadau mewnol, megis

(define (f x)
  (define (even? n)
    (if (= n 0)
        true
        (odd? (- n 1))))
  (define (odd? n)
    (if (= n 0)
        false
        (even? (- n 1))))
  ⟨rest of body of f⟩)

Ein bwriad yma yw y dylai’r enw odd? yng nghorff y weithdrefn even? gyfeirio at y weithdrefn odd? a ddiffinnir ar ôl even?. Cwmpas yr enw odd? yw corff cyfan f, nid dim ond y rhan o gorff f sy’n dechrau yn y man lle mae’r define ar gyfer odd? yn ymddangos. Yn wir, pan ystyriwn fod odd? ei hun wedi’i ddiffinio yn nhermau even?—fel bod even? ac odd? yn weithdrefnau cyd-ddychweliadol—gwelwn mai’r unig ddehongliad boddhaol o’r ddau define yw eu hystyried fel pe bai’r enwau even? ac odd? yn cael eu hychwanegu at yr amgylchedd ar yr un pryd. Yn fwy cyffredinol, mewn strwythur blociau, cwmpas enw lleol yw corff cyfan y weithdrefn lle gwerthusir y define.

Fel mae’n digwydd, bydd ein dehonglydd yn gwerthuso galwadau i f yn gywir, ond am reswm “damweiniol”: gan fod diffiniadau’r gweithdrefnau mewnol yn dod yn gyntaf, ni werthusir unrhyw alwadau i’r gweithdrefnau hyn nes bod pob un wedi’i diffinio. Felly, bydd odd? wedi’i ddiffinio erbyn i even? gael ei redeg. Yn wir, bydd ein mecanwaith gwerthuso dilyniannol yn rhoi’r un canlyniad â mecanwaith sy’n gweithredu diffinio cydamserol yn uniongyrchol ar gyfer unrhyw weithdrefn lle mae’r diffiniadau mewnol yn dod yn gyntaf yn y corff, ac nad yw gwerthuso’r mynegiadau gwerth ar gyfer y newidynnau a ddiffinnir yn defnyddio unrhyw un o’r newidynnau a ddiffinnir mewn gwirionedd. (Am enghraifft o weithdrefn nad yw’n ufuddhau i’r cyfyngiadau hyn, fel nad yw diffinio dilyniannol yn gyfwerth â diffinio cydamserol, gweler Ymarfer 4.19.)²²⁸

Fodd bynnag, mae ffordd syml o drin diffiniadau fel bod gan enwau a ddiffinnir yn fewnol gwmpas cydamserol go iawn: crëwch yr holl newidynnau lleol a fydd yn yr amgylchedd cyfredol cyn gwerthuso unrhyw un o’r mynegiadau gwerth. Un ffordd o wneud hyn yw drwy drawsffurfiad cystrawen ar fynegiadau lambda. Cyn gwerthuso corff mynegiad lambda, rydym yn “sganio allan” ac yn dileu’r holl ddiffiniadau mewnol yn y corff. Crëir y newidynnau a ddiffinnir yn fewnol ag let ac yna gosodir eu gwerthoedd drwy aseinio. Er enghraifft, byddai’r weithdrefn

(lambda ⟨vars⟩
  (define u ⟨e1⟩)
  (define v ⟨e2⟩)
  ⟨e3⟩)

yn cael ei thrawsffurfio’n

(lambda ⟨vars⟩
  (let ((u '*unassigned*)
        (v '*unassigned*))
    (set! u ⟨e1⟩)
    (set! v ⟨e2⟩)
    ⟨e3⟩))

lle mae *unassigned* yn symbol arbennig sy’n peri i chwilio am newidyn arwyddo gwall os ceisir defnyddio gwerth y newidyn cyn iddo gael ei aseinio.

Dangosir strategaeth amgen ar gyfer sganio diffiniadau mewnol allan yn Ymarfer 4.18. Yn wahanol i’r trawsffurfiad uchod, mae hon yn gorfodi’r cyfyngiad y gellir gwerthuso gwerthoedd y newidynnau a ddiffinnir heb ddefnyddio unrhyw un o werthoedd y newidynnau.²²⁹

Ymarfer 4.16: Yn yr ymarfer hwn, gweithredwn y dull sydd newydd gael ei ddisgrifio ar gyfer dehongli diffiniadau mewnol. Tybiwn fod y gwerthusydd yn cefnogi let (gweler Ymarfer 4.6).

1. Newidiwch lookup-variable-value (4.1.3) i arwyddo gwall os mai’r symbol *unassigned* yw’r gwerth y mae’n ei ganfod.
2. Ysgrifennwch weithdrefn scan-out-defines sy’n cymryd corff gweithdrefn ac yn dychwelyd un cyfwerth heb ddiffiniadau mewnol, drwy gyflawni’r trawsffurfiad a ddisgrifir uchod.
3. Gosodwch scan-out-defines yn y dehonglydd, naill ai yn make-procedure neu yn procedure-body (gweler 4.1.3). Pa fan sy’n well? Pam?

Ymarfer 4.17: Lluniwch ddiagramau o’r amgylchedd sydd mewn grym wrth werthuso’r mynegiad ⟨e3⟩ yn y weithdrefn yn y testun, gan gymharu ei strwythur pan ddehonglir diffiniadau’n ddilyniannol â’i strwythur os sganiwyd y diffiniadau allan fel y disgrifir. Pam mae ffrâm ychwanegol yn y rhaglen a drawsffurfiwyd? Esboniwch pam na all y gwahaniaeth hwn yn strwythur yr amgylchedd byth newid ymddygiad rhaglen gywir. Dyluniwch ffordd i’r dehonglydd weithredu’r rheol cwmpas “cydamserol” ar gyfer diffiniadau mewnol heb adeiladu’r ffrâm ychwanegol.

Ymarfer 4.18: Ystyriwch strategaeth amgen ar gyfer sganio diffiniadau allan sy’n trosi’r enghraifft yn y testun yn

(lambda ⟨vars⟩
  (let ((u '*unassigned*)
        (v '*unassigned*))
    (let ((a ⟨e1⟩)
          (b ⟨e2⟩))
      (set! u a)
      (set! v b))
    ⟨e3⟩))

Yma, bwriedir i a ac b gynrychioli enwau newidynnau newydd, a grëir gan y dehonglydd, nad ydynt yn ymddangos yn rhaglen y defnyddiwr. Ystyriwch y weithdrefn solve o 3.5.4:

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

A fydd y weithdrefn hon yn gweithio os sganiwyd diffiniadau mewnol allan fel y dangosir yn yr ymarfer hwn? Beth os cânt eu sganio allan fel y dangosir yn y testun? Esboniwch.

Ymarfer 4.19: Mae Ben Bitdiddle, Alyssa P. Hacker ac Eva Lu Ator yn dadlau ynghylch y canlyniad dymunol wrth werthuso’r mynegiad

(let ((a 1))
  (define (f x)
    (define b (+ a x))
    (define a 5)
    (+ a b))
  (f 10))

Mae Ben yn honni y dylid cael y canlyniad drwy ddefnyddio’r rheol ddilyniannol ar gyfer define: diffinnir b yn 11, yna diffinnir a yn 5, felly’r canlyniad yw 16. Mae Alyssa yn gwrthwynebu, gan ddweud bod cyd-ddychweliad yn gofyn am y rheol cwmpas cydamserol ar gyfer diffiniadau gweithdrefn mewnol, a’i bod yn afresymol trin enwau gweithdrefnau’n wahanol i enwau eraill. Felly mae hi’n dadlau o blaid y mecanwaith a weithredir yn Ymarfer 4.16. Byddai hyn yn golygu bod a heb ei aseinio pan fydd gwerth b i’w gyfrifo. Felly, ym marn Alyssa, dylai’r weithdrefn gynhyrchu gwall. Mae gan Eva drydedd farn. Mae hi’n dweud, os mai’r bwriad mewn gwirionedd yw bod diffiniadau a ac b yn gydamserol, yna dylid defnyddio gwerth 5 ar gyfer a wrth werthuso b. Felly, ym marn Eva, dylai a fod yn 5, dylai b fod yn 15, a dylai’r canlyniad fod yn 20. Pa un o’r safbwyntiau hyn, os o gwbl, yr ydych yn ei gefnogi? A allwch ddyfeisio ffordd o weithredu diffiniadau mewnol fel eu bod yn ymddwyn fel y mae Eva yn ei ffafrio?²³⁰

Ymarfer 4.20: Gan fod diffiniadau mewnol yn edrych yn ddilyniannol ond mewn gwirionedd yn gydamserol, mae’n well gan rai pobl eu hosgoi’n llwyr a defnyddio’r ffurf arbennig letrec yn eu lle. Mae Letrec yn edrych fel let, felly nid yw’n syndod bod y newidynnau y mae’n eu rhwymo wedi’u rhwymo ar yr un pryd a bod ganddynt yr un cwmpas â’i gilydd. Gellir ysgrifennu’r weithdrefn enghreifftiol f uchod heb ddiffiniadau mewnol, ond â’r union un ystyr, fel

(define (f x)
  (letrec
      ((even?
        (lambda (n)
          (if (= n 0)
              true
              (odd? (- n 1)))))
       (odd?
        (lambda (n)
          (if (= n 0)
              false
              (even? (- n 1))))))
    ⟨rest of body of f⟩))

Mae mynegiadau Letrec, sydd ar y ffurf

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

yn amrywiad ar let lle gwerthusir y mynegiadau $⟨ex{p}_k⟩$ sy’n darparu’r gwerthoedd cychwynnol ar gyfer y newidynnau $⟨va{r}_k⟩$ mewn amgylchedd sy’n cynnwys holl rwymiadau letrec. Mae hyn yn caniatáu dychweliad yn y rhwymiadau, megis cyd-ddychweliad even? ac odd? yn yr enghraifft uchod, neu werthuso 10 ffactorial ag

(letrec
    ((fact
      (lambda (n)
        (if (= n 1)
            1
            (* n (fact (- n 1)))))))
  (fact 10))

1. Gweithredwch letrec fel mynegiad deilliedig drwy drawsffurfio mynegiad letrec yn fynegiad let fel y dangosir yn y testun uchod neu yn Ymarfer 4.18. Hynny yw, dylid creu’r newidynnau letrec ag let ac yna aseinio eu gwerthoedd ag set!.
2. Mae’r holl ffwdan ynghylch diffiniadau mewnol yn drysu Louis Reasoner. Fel y mae ef yn ei weld, os nad ydych yn hoffi defnyddio define y tu mewn i weithdrefn, gallwch ddefnyddio let yn syml. Dangoswch beth sy’n ddiffygiol yn ei ymresymiad drwy lunio diagram amgylchedd sy’n dangos yr amgylchedd lle gwerthusir ⟨rest of body of f⟩ wrth werthuso’r mynegiad (f 5), gydag f wedi’i ddiffinio fel yn yr ymarfer hwn. Lluniwch ddiagram amgylchedd ar gyfer yr un gwerthusiad, ond gydag let yn lle letrec yn niffiniad f.

Ymarfer 4.21: Yn rhyfeddol, mae greddf Louis yn Ymarfer 4.20 yn gywir. Mae’n bosibl yn wir bennu gweithdrefnau dychweliadol heb ddefnyddio letrec (na hyd yn oed define), er bod y dull o gyflawni hyn yn llawer mwy cynnil nag y dychmygodd Louis. Mae’r mynegiad canlynol yn cyfrifo 10 ffactorial drwy gymhwyso gweithdrefn ffactorial ddychweliadol:²³¹

((lambda (n)
   ((lambda (fact) (fact fact n))
    (lambda (ft k)
      (if (= k 1)
          1
          (* k (ft ft (- k 1)))))))
 10)

1. Gwiriwch, drwy werthuso’r mynegiad, ei fod yn cyfrifo ffactorialau mewn gwirionedd. Dyfeisiwch fynegiad cyfatebol ar gyfer cyfrifo rhifau Fibonacci.
2. Ystyriwch y weithdrefn ganlynol, sy’n cynnwys diffiniadau mewnol cyd-ddychweliadol:

   (define (f x)
     (define (even? n)
       (if (= n 0)
           true
           (odd? (- n 1))))
     (define (odd? n)
       (if (= n 0)
           false
           (even? (- n 1))))
     (even? x))

   Llenwch y mynegiadau coll i gwblhau diffiniad amgen o f nad yw’n defnyddio diffiniadau mewnol nac letrec:

   (define (f x)
     ((lambda (even? odd?)
        (even? even? odd? x))
      (lambda (ev? od? n)
        (if (= n 0) 
            true 
            (od? ⟨??⟩ ⟨??⟩ ⟨??⟩)))
      (lambda (ev? od? n)
        (if (= n 0) 
            false 
            (ev? ⟨??⟩ ⟨??⟩ ⟨??⟩)))))

4.1.7Gwahanu dadansoddi cystrawennol oddi wrth redeg

Mae’r gwerthusydd a weithredwyd uchod yn syml, ond mae’n aneffeithlon iawn, oherwydd plethir dadansoddi cystrawennol mynegiadau â’u rhedeg. Felly, os rhedir rhaglen lawer gwaith, dadansoddir ei chystrawen lawer gwaith. Ystyriwch, er enghraifft, werthuso (factorial 4) gan ddefnyddio’r diffiniad canlynol o factorial:

(define (factorial n)
  (if (= n 1)
      1
      (* (factorial (- n 1)) n)))

Bob tro y gelwir factorial, rhaid i’r gwerthusydd bennu mai mynegiad if yw’r corff ac echdynnu’r traethiad. Dim ond wedyn y gall werthuso’r traethiad a dewis yn ôl ei werth. Bob tro y mae’n gwerthuso’r mynegiad (* (factorial (- n 1)) n), neu’r is-fynegiadau (factorial (- n 1)) ac (- n 1), rhaid i’r gwerthusydd gyflawni’r dadansoddiad achosion yn eval i bennu mai cymhwysiad yw’r mynegiad, a rhaid iddo echdynnu ei weithredydd a’i operandau. Mae’r dadansoddiad hwn yn gostus. Mae ei gyflawni dro ar ôl tro yn wastraffus.

Gallwn drawsffurfio’r gwerthusydd i fod yn sylweddol fwy effeithlon drwy drefnu pethau fel mai unwaith yn unig y cyflawnir y dadansoddi cystrawennol.²³² Rhannwn eval, sy’n cymryd mynegiad ac amgylchedd, yn ddwy ran. Dim ond y mynegiad y mae’r weithdrefn analyze yn ei gymryd. Mae’n cyflawni’r dadansoddi cystrawennol ac yn dychwelyd gweithdrefn newydd, sef y weithdrefn redeg, sy’n amgáu’r gwaith sydd i’w wneud wrth redeg y mynegiad a ddadansoddwyd. Mae’r weithdrefn redeg yn cymryd amgylchedd yn arg ac yn cwblhau’r gwerthuso. Mae hyn yn arbed gwaith gan mai dim ond unwaith y gelwir analyze ar fynegiad, tra gellir galw’r weithdrefn redeg lawer gwaith.

Ar ôl gwahanu dadansoddi a rhedeg, daw eval bellach yn

(define (eval exp env) ((analyze exp) env))

Canlyniad galw analyze yw’r weithdrefn redeg sydd i’w chymhwyso i’r amgylchedd. Yr un dadansoddiad achosion ag a gyflawnir gan yr eval gwreiddiol yn 4.1.1 yw’r weithdrefn analyze, ac eithrio mai dim ond dadansoddi, yn hytrach na gwerthuso llawn, y mae’r gweithdrefnau a ddewisir yn ei gyflawni:

(define (analyze exp)
  (cond ((self-evaluating? exp)
         (analyze-self-evaluating exp))
        ((quoted? exp) 
         (analyze-quoted exp))
        ((variable? exp) 
         (analyze-variable exp))
        ((assignment? exp) 
         (analyze-assignment exp))
        ((definition? exp) 
         (analyze-definition exp))
        ((if? exp) 
         (analyze-if exp))
        ((lambda? exp) 
         (analyze-lambda exp))
        ((begin? exp) 
         (analyze-sequence 
          (begin-actions exp)))
        ((cond? exp) 
         (analyze (cond->if exp)))
        ((application? exp) 
         (analyze-application exp))
        (else
         (error "Unknown expression 
                 type: ANALYZE" 
                exp))))

Dyma’r weithdrefn dadansoddi cystrawennol symlaf, sy’n trin mynegiadau sy’n gwerthuso i’w hunain. Mae’n dychwelyd gweithdrefn redeg sy’n anwybyddu ei harg amgylchedd ac yn dychwelyd y mynegiad yn unig:

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

Ar gyfer mynegiad wedi’i ddyfynnu, gallwn ennill ychydig o effeithlonrwydd drwy echdynnu testun y dyfyniad unwaith yn unig, yn y cam dadansoddi yn hytrach nag yn y cam rhedeg.

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

Rhaid dal i chwilio am werth newidyn yn y cam rhedeg, gan fod hyn yn dibynnu ar wybod yr amgylchedd.²³³

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

Rhaid i Analyze-assignment hefyd ohirio gosod y newidyn ei hun tan y cam rhedeg, pan fydd yr amgylchedd wedi’i ddarparu. Fodd bynnag, mae’r ffaith y gellir dadansoddi’r mynegiad assignment-value yn ddychweliadol yn ystod y dadansoddi yn fantais fawr o ran effeithlonrwydd, oherwydd dadansoddir y mynegiad assignment-value unwaith yn unig bellach. Mae’r un peth yn wir am ddiffiniadau.

(define (analyze-assignment exp)
  (let ((var (assignment-variable exp))
        (vproc (analyze 
                (assignment-value exp))))
    (lambda (env)
      (set-variable-value! 
       var (vproc env) env)
      'ok)))

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

Ar gyfer mynegiadau if, echdynnwn a dadansoddwn y traethiad, y canlyniadol a’r dewis arall adeg dadansoddi.

(define (analyze-if exp)
  (let ((pproc (analyze (if-predicate exp)))
        (cproc (analyze (if-consequent exp)))
        (aproc (analyze (if-alternative exp))))
    (lambda (env)
      (if (true? (pproc env))
          (cproc env)
          (aproc env)))))

Mae dadansoddi mynegiad lambda hefyd yn sicrhau mantais fawr o ran effeithlonrwydd: dadansoddwn gorff lambda unwaith yn unig, er y gellir cymhwyso gweithdrefnau sy’n deillio o werthuso’r lambda lawer gwaith.

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

Mae dadansoddi dilyniant o fynegiadau, fel mewn begin neu gorff mynegiad lambda, yn fwy cymhleth.²³⁴ Dadansoddir pob mynegiad yn y dilyniant, gan gynhyrchu gweithdrefn redeg. Cyfunir y gweithdrefnau rhedeg hyn i gynhyrchu gweithdrefn redeg sy’n cymryd amgylchedd yn arg ac yn galw pob gweithdrefn redeg unigol yn ei threfn, gyda’r amgylchedd yn arg.

(define (analyze-sequence exps)
  (define (sequentially proc1 proc2)
    (lambda (env) (proc1 env) (proc2 env)))
  (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))))

I ddadansoddi cymhwysiad, dadansoddwn y gweithredydd a’r operandau ac adeiladwn weithdrefn redeg sy’n galw gweithdrefn redeg y gweithredydd (i gael y weithdrefn ei hun sydd i’w chymhwyso) a gweithdrefnau rhedeg yr operandau (i gael yr argiau eu hunain). Yna trosglwyddwn y rhain i execute-application, sy’n cyfateb i apply yn 4.1.1. Mae Execute-application yn wahanol i apply gan fod corff gweithdrefn gyfansawdd eisoes wedi’i ddadansoddi, felly nid oes angen dadansoddi pellach. Yn lle hynny, galwn weithdrefn redeg y corff ar yr amgylchedd estynedig.

(define (analyze-application exp)
  (let ((fproc (analyze (operator exp)))
        (aprocs (map analyze (operands exp))))
    (lambda (env)
      (execute-application 
       (fproc env)
       (map (lambda (aproc) (aproc env))
            aprocs)))))

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

Mae ein gwerthusydd newydd yn defnyddio’r un strwythurau data, gweithdrefnau cystrawen a gweithdrefnau cymorth adeg rhedeg ag yn 4.1.2, 4.1.3 a 4.1.4.

Ymarfer 4.22: Estynnwch y gwerthusydd yn yr adran hon i gefnogi’r ffurf arbennig let. (Gweler Ymarfer 4.6.)

Ymarfer 4.23: Nid yw Alyssa P. Hacker yn deall pam mae angen i analyze-sequence fod mor gymhleth. Mae’r holl weithdrefnau dadansoddi eraill yn drawsffurfiadau syml o’r gweithdrefnau gwerthuso cyfatebol (neu gymalau eval) yn 4.1.1. Roedd hi’n disgwyl i analyze-sequence edrych fel hyn:

(define (analyze-sequence exps)
  (define (execute-sequence procs env)
    (cond ((null? (cdr procs)) 
           ((car procs) env))
          (else ((car procs) env)
                (execute-sequence 
                 (cdr procs) env))))
  (let ((procs (map analyze exps)))
    (if (null? procs)
        (error "Empty sequence: 
                ANALYZE"))
    (lambda (env) 
      (execute-sequence procs env))))

Mae Eva Lu Ator yn esbonio wrth Alyssa fod y fersiwn yn y testun yn gwneud mwy o’r gwaith o werthuso dilyniant adeg dadansoddi. Yn lle bod y galwadau i’r gweithdrefnau rhedeg unigol wedi’u hymgorffori ynddi, mae gweithdrefn rhedeg dilyniant Alyssa yn dolennu drwy’r gweithdrefnau er mwyn eu galw: mewn gwirionedd, er bod mynegiadau unigol y dilyniant wedi’u dadansoddi, nid yw’r dilyniant ei hun wedi’i ddadansoddi.

Cymharwch y ddwy fersiwn o analyze-sequence. Er enghraifft, ystyriwch yr achos cyffredin, sy’n nodweddiadol o gyrff gweithdrefnau, lle mai dim ond un mynegiad sydd yn y dilyniant. Pa waith fydd y weithdrefn redeg a gynhyrchir gan raglen Alyssa yn ei wneud? Beth am y weithdrefn redeg a gynhyrchir gan y rhaglen yn y testun uchod? Sut mae’r ddwy fersiwn yn cymharu ar gyfer dilyniant â dau fynegiad?

Ymarfer 4.24: Dyluniwch a chyflawnwch rai arbrofion i gymharu cyflymder y gwerthusydd metagylchol gwreiddiol â’r fersiwn yn yr adran hon. Defnyddiwch eich canlyniadau i amcangyfrif y gyfran o amser a dreulir yn dadansoddi o’i chymharu â rhedeg ar gyfer gwahanol weithdrefnau.

(define apply-in-underlying-scheme apply)