SICP · Yr ail argraffiad · Scheme

5.2 Efelychydd Peiriannau Cofrestri

Harold Abelson a Gerald Jay Sussman gyda Julie Sussman · Cyfieithiad Cymraeg

Er mwyn cael dealltwriaeth dda o ddylunio peiriannau cofrestri, rhaid inni brofi'r peiriannau a ddyluniwn i weld a ydynt yn gweithredu fel y disgwylir. Un ffordd o brofi dyluniad yw efelychu gweithrediad y rheolydd â llaw, fel yn Ymarfer 5.5. Ond mae hyn yn hynod ddiflas ar gyfer pob peiriant heblaw'r rhai symlaf. Yn yr adran hon adeiladwn efelychydd ar gyfer peiriannau a ddisgrifir yn yr iaith peiriannau cofrestri. Rhaglen Scheme â phedair gweithdrefn rhyngwyneb yw'r efelychydd. Mae'r gyntaf yn defnyddio disgrifiad o beiriant cofrestri i adeiladu model o'r peiriant (strwythur data y mae ei rannau'n cyfateb i rannau'r peiriant sydd i'w efelychu), ac mae'r tair arall yn caniatáu inni efelychu'r peiriant drwy drin y model:

(make-machine ⟨register-names⟩
              ⟨operations⟩
              ⟨controller⟩)
yn adeiladu ac yn dychwelyd model o'r peiriant â'r cofrestri, y gweithrediadau, a'r rheolydd a roddwyd.
(set-register-contents! ⟨machine-model⟩ 
                        ⟨register-name⟩ 
                        ⟨value⟩)
yn storio gwerth mewn cofrestr wedi'i hefelychu yn y peiriant penodol.
(get-register-contents ⟨machine-model⟩
                       ⟨register-name⟩)
yn dychwelyd cynnwys cofrestr wedi'i hefelychu yn y peiriant penodol.
(start ⟨machine-model⟩)
yn efelychu gweithrediad y peiriant penodol, gan ddechrau ar ddechrau dilyniant y rheolydd a stopio pan gyrhaeddir diwedd y dilyniant.

Fel enghraifft o sut y defnyddir y gweithdrefnau hyn, gallwn ddiffinio gcd-machine yn fodel o beiriant GCD 5.1.1 fel a ganlyn:

(define gcd-machine
  (make-machine
   '(a b t)
   (list (list 'rem remainder) (list '= =))
   '(test-b
       (test (op =) (reg b) (const 0))
       (branch (label gcd-done))
       (assign t (op rem) (reg a) (reg b))
       (assign a (reg b))
       (assign b (reg t))
       (goto (label test-b))
     gcd-done)))

Yr arg cyntaf i make-machine yw rhestr o enwau cofrestri. Yr arg nesaf yw tabl (rhestr o restrau dwy elfen) sy'n paru enw pob gweithrediad â gweithdrefn Scheme sy'n gweithredu'r gweithrediad (hynny yw, sy'n cynhyrchu'r un gwerth allbwn o gael yr un gwerthoedd mewnbwn). Mae'r arg olaf yn pennu'r rheolydd fel rhestr o labeli a chyfarwyddiadau peiriant, fel yn 5.1.

I gyfrifiannu GCD â'r peiriant hwn, gosodwn y cofrestri mewnbwn, dechreuwn y peiriant, ac archwiliwn y canlyniad pan fydd yr efelychiad yn terfynu:

(set-register-contents! gcd-machine 'a 206)
done

(set-register-contents! gcd-machine 'b 40)
done

(start gcd-machine)
done

(get-register-contents gcd-machine 'a)
2

Bydd y cyfrifiad hwn yn rhedeg yn llawer arafach na gweithdrefn gcd a ysgrifennwyd yn Scheme, oherwydd byddwn yn efelychu cyfarwyddiadau peiriant lefel isel, megis assign, drwy weithrediadau llawer mwy cymhleth.

Ymarfer 5.7: Defnyddiwch yr efelychydd i brofi'r peiriannau a ddyluniasoch yn Ymarfer 5.4.

5.2.1Model y Peiriant

Cynrychiolir model y peiriant a gynhyrchir gan make-machine fel gweithdrefn â chyflwr lleol, gan ddefnyddio'r technegau trosglwyddo negeseuon a ddatblygwyd ym Mhennod 3. I adeiladu'r model hwn, mae make-machine yn dechrau drwy alw'r weithdrefn make-new-machine i adeiladu'r rhannau o fodel y peiriant sy'n gyffredin i bob peiriant cofrestri. Yn ei hanfod, mae'r model peiriant sylfaenol hwn a adeiladir gan make-new-machine yn gynhwysydd ar gyfer rhai cofrestri a phentwr, ynghyd â mecanwaith gweithredu sy'n prosesu cyfarwyddiadau'r rheolydd fesul un.

Yna mae Make-machine yn ymestyn y model sylfaenol hwn (drwy anfon negeseuon ato) i gynnwys cofrestri, gweithrediadau, a rheolydd y peiriant penodol sy'n cael ei ddiffinio. Yn gyntaf, mae'n dyrannu cofrestr yn y peiriant newydd ar gyfer pob un o'r enwau cofrestri a ddarparwyd ac yn gosod y gweithrediadau dynodedig yn y peiriant. Yna mae'n defnyddio cydosodydd (a ddisgrifir isod yn 5.2.2) i drawsffurfio rhestr y rheolydd yn gyfarwyddiadau ar gyfer y peiriant newydd ac yn gosod y rhain yn ddilyniant cyfarwyddiadau'r peiriant. Mae Make-machine yn dychwelyd model addasedig y peiriant yn werth.

(define (make-machine register-names 
                      ops 
                      controller-text)
  (let ((machine (make-new-machine)))
    (for-each (lambda (register-name)
                ((machine 'allocate-register) 
                 register-name))
              register-names)
    ((machine 'install-operations) ops)
    ((machine 'install-instruction-sequence)
     (assemble controller-text machine))
    machine))

Cofrestri

Byddwn yn cynrychioli cofrestr fel gweithdrefn â chyflwr lleol, fel ym Mhennod 3. Mae'r weithdrefn make-register yn creu cofrestr sy'n dal gwerth y gellir ei gyrchu neu ei newid:

(define (make-register name)
  (let ((contents '*unassigned*))
    (define (dispatch message)
      (cond ((eq? message 'get) contents)
            ((eq? message 'set)
             (lambda (value) 
               (set! contents value)))
            (else
             (error "Unknown request: 
                     REGISTER"
                    message))))
    dispatch))

Defnyddir y gweithdrefnau canlynol i gyrchu cofrestri:

(define (get-contents register)
  (register 'get))

(define (set-contents! register value)
  ((register 'set) value))

Y pentwr

Gallwn hefyd gynrychioli pentwr fel gweithdrefn â chyflwr lleol. Mae'r weithdrefn make-stack yn creu pentwr y mae ei gyflwr lleol yn cynnwys rhestr o'r eitemau ar y pentwr. Mae pentwr yn derbyn ceisiadau i wthio eitem ar y pentwr drwy push, i dynnu'r eitem uchaf oddi ar y pentwr a'i dychwelyd drwy pop, ac i gychwyn y pentwr yn wag drwy initialize.

(define (make-stack)
  (let ((s '()))
    (define (push x)
      (set! s (cons x s)))
    (define (pop)
      (if (null? s)
          (error "Empty stack: POP")
          (let ((top (car s)))
            (set! s (cdr s))
            top)))
    (define (initialize)
      (set! s '())
      'done)
    (define (dispatch message)
      (cond ((eq? message 'push) push)
            ((eq? message 'pop) (pop))
            ((eq? message 'initialize) 
             (initialize))
            (else 
             (error "Unknown request: STACK"
                    message))))
    dispatch))

Defnyddir y gweithdrefnau canlynol i gyrchu pentyrrau:

(define (pop stack) (stack 'pop))
(define (push stack value)
  ((stack 'push) value))

Y peiriant sylfaenol

Mae'r weithdrefn make-new-machine, a ddangosir yn Ffigur 5.13, yn adeiladu gwrthrych y mae ei gyflwr lleol yn cynnwys pentwr, dilyniant cyfarwyddiadau sy'n wag i ddechrau, rhestr o weithrediadau sydd i ddechrau'n cynnwys gweithrediad i gychwyn y pentwr, a thabl cofrestri sydd i ddechrau'n cynnwys dwy gofrestr, o'r enwau flag ac pc (ar gyfer “rhifydd rhaglen”). Mae'r weithdrefn fewnol allocate-register yn ychwanegu cofnodion newydd at y tabl cofrestri, ac mae'r weithdrefn fewnol lookup-register yn chwilio am gofrestri yn y tabl.

Ffigur 5.13: $↓$ Y weithdrefn make-new-machine, sy'n gweithredu model sylfaenol y peiriant.

(define (make-new-machine)
  (let ((pc (make-register 'pc))
        (flag (make-register 'flag))
        (stack (make-stack))
        (the-instruction-sequence '()))
    (let ((the-ops
           (list 
            (list 'initialize-stack
                  (lambda () 
                    (stack 'initialize)))))
          (register-table
           (list (list 'pc pc) 
                 (list 'flag flag))))
      (define (allocate-register name)
        (if (assoc name register-table)
            (error 
             "Multiply defined register: " 
             name)
            (set! register-table
                  (cons 
                   (list name 
                         (make-register name))
                   register-table)))
        'register-allocated)
      (define (lookup-register name)
        (let ((val 
               (assoc name register-table)))
          (if val
              (cadr val)
              (error "Unknown register:" 
                     name))))
      (define (execute)
        (let ((insts (get-contents pc)))
          (if (null? insts)
              'done
              (begin
                ((instruction-execution-proc 
                  (car insts)))
                (execute)))))
      (define (dispatch message)
        (cond ((eq? message 'start)
               (set-contents! 
                pc
                the-instruction-sequence)
               (execute))
              ((eq? 
                message 
                'install-instruction-sequence)
               (lambda (seq) 
                 (set! 
                  the-instruction-sequence 
                  seq)))
              ((eq? message 
                    'allocate-register) 
               allocate-register)
              ((eq? message 'get-register) 
               lookup-register)
              ((eq? message 
                    'install-operations)
               (lambda (ops) 
                 (set! the-ops 
                       (append the-ops ops))))
              ((eq? message 'stack) stack)
              ((eq? message 'operations) 
               the-ops)
              (else (error "Unknown request: 
                            MACHINE"
                           message))))
      dispatch)))

Defnyddir y gofrestr flag i reoli canghennu yn y peiriant wedi'i efelychu. Mae cyfarwyddiadau Test yn gosod cynnwys flag i ganlyniad y prawf (gwir neu anwir). Mae cyfarwyddiadau Branch yn penderfynu a ddylid canghennu drwy archwilio cynnwys flag.

Mae'r gofrestr pc yn pennu trefn y cyfarwyddiadau wrth i'r peiriant redeg. Gweithredir y drefn hon gan y weithdrefn fewnol execute. Yn y model efelychu, mae pob cyfarwyddyd peiriant yn strwythur data sy'n cynnwys gweithdrefn heb argiau, a elwir yn weithdrefn gweithredu cyfarwyddyd, fel bod galw'r weithdrefn hon yn efelychu gweithredu'r cyfarwyddyd. Wrth i'r efelychiad redeg, mae pc yn pwyntio at y man yn y dilyniant cyfarwyddiadau sy'n dechrau â'r cyfarwyddyd nesaf i'w weithredu. Mae Execute yn cael y cyfarwyddyd hwnnw, yn ei weithredu drwy alw'r weithdrefn gweithredu cyfarwyddyd, ac yn ailadrodd y cylch hwn nes nad oes rhagor o gyfarwyddiadau i'w gweithredu (h.y., nes bod pc yn pwyntio at ddiwedd y dilyniant cyfarwyddiadau).

Fel rhan o'i gweithrediad, mae pob gweithdrefn gweithredu cyfarwyddyd yn addasu pc i ddangos y cyfarwyddyd nesaf i'w weithredu. Mae cyfarwyddiadau Branch ac goto yn newid pc i bwyntio at y cyrchfan newydd. Mae pob cyfarwyddyd arall yn symud pc ymlaen yn syml, gan wneud iddo bwyntio at y cyfarwyddyd nesaf yn y dilyniant. Sylwch fod pob galwad i execute yn galw execute eto, ond nid yw hyn yn cynhyrchu dolen anfeidraidd oherwydd bod rhedeg y weithdrefn gweithredu cyfarwyddyd yn newid cynnwys pc.

Mae Make-new-machine yn dychwelyd gweithdrefn dispatch sy'n gweithredu mynediad drwy drosglwyddo negeseuon at y cyflwr mewnol. Sylwch y cyflawnir dechrau'r peiriant drwy osod pc i ddechrau'r dilyniant cyfarwyddiadau a galw execute.

Er hwylustod, darparwn ryngwyneb gweithdrefnol amgen i weithrediad start peiriant, yn ogystal â gweithdrefnau i osod ac archwilio cynnwys cofrestri, fel y pennwyd ar ddechrau 5.2:

(define (start machine)
  (machine 'start))

(define (get-register-contents 
         machine register-name)
  (get-contents 
   (get-register machine register-name)))

(define (set-register-contents! 
         machine register-name value)
  (set-contents! 
   (get-register machine register-name) 
   value)
  'done)

Mae'r gweithdrefnau hyn (a llawer o weithdrefnau yn 5.2.2 a 5.2.3) yn defnyddio'r canlynol i chwilio am y gofrestr ag enw penodol mewn peiriant penodol:

(define (get-register machine reg-name)
  ((machine 'get-register) reg-name))

5.2.2Y Cydosodydd

Mae'r cydosodydd yn trawsffurfio dilyniant mynegiadau rheolydd peiriant yn rhestr gyfatebol o gyfarwyddiadau peiriant, pob un â'i weithdrefn weithredu. Yn gyffredinol, mae'r cydosodydd yn debyg iawn i'r gwerthuswyr a astudiasom ym Mhennod 4—mae iaith fewnbwn (yr iaith peiriannau cofrestri yn yr achos hwn) a rhaid inni gyflawni gweithred briodol ar gyfer pob math o fynegiad yn yr iaith.

Mae'r dechneg o gynhyrchu gweithdrefn weithredu ar gyfer pob cyfarwyddyd yn union yr hyn a ddefnyddiasom yn 4.1.7 i gyflymu'r gwerthusydd drwy wahanu dadansoddi oddi wrth weithredu adeg rhedeg. Fel y gwelsom ym Mhennod 4, gellid cyflawni llawer o ddadansoddi defnyddiol ar fynegiadau Scheme heb wybod gwerthoedd gwirioneddol newidynnau. Yma, yn gyfatebol, gellir cyflawni llawer o ddadansoddi defnyddiol ar fynegiadau'r iaith peiriannau cofrestri heb wybod cynnwys gwirioneddol cofrestri'r peiriant. Er enghraifft, gallwn roi pwyntyddion at wrthrychau'r cofrestri yn lle cyfeiriadau at gofrestri, a gallwn roi pwyntyddion at y man yn y dilyniant cyfarwyddiadau a ddynodir gan label yn lle cyfeiriadau at labeli.

Cyn y gall gynhyrchu'r gweithdrefnau gweithredu cyfarwyddiadau, rhaid i'r cydosodydd wybod at beth mae'r holl labeli'n cyfeirio, felly mae'n dechrau drwy sganio testun y rheolydd i wahanu'r labeli oddi wrth y cyfarwyddiadau. Wrth sganio'r testun, mae'n adeiladu rhestr o gyfarwyddiadau a thabl sy'n cysylltu pob label â phwyntydd i mewn i'r rhestr honno. Yna mae'r cydosodydd yn ychwanegu at y rhestr gyfarwyddiadau drwy fewnosod y weithdrefn weithredu ar gyfer pob cyfarwyddyd.

Y weithdrefn assemble yw prif bwynt mynediad y cydosodydd. Mae'n cymryd testun y rheolydd a model y peiriant yn argiau ac yn dychwelyd y dilyniant cyfarwyddiadau sydd i'w storio yn y model. Mae Assemble yn galw extract-labels i adeiladu'r rhestr gyfarwyddiadau gychwynnol a'r tabl labeli o destun y rheolydd a ddarparwyd. Yr ail arg i extract-labels yw gweithdrefn i'w galw i brosesu'r canlyniadau hyn: mae'r weithdrefn hon yn defnyddio update-insts! i gynhyrchu'r gweithdrefnau gweithredu cyfarwyddiadau a'u mewnosod yn y rhestr gyfarwyddiadau, ac yn dychwelyd y rhestr addasedig.

(define (assemble controller-text machine)
  (extract-labels controller-text
    (lambda (insts labels)
      (update-insts! insts labels machine)
      insts)))

Mae Extract-labels yn cymryd rhestr text (dilyniant mynegiadau cyfarwyddiadau'r rheolydd) a gweithdrefn receive yn argiau. Gelwir Receive â dau werth: (1) rhestr insts o strwythurau data cyfarwyddiadau, pob un yn cynnwys cyfarwyddyd o text; a (2) tabl o'r enw labels, sy'n cysylltu pob label o text â'r safle yn y rhestr insts a ddynodir gan y label.

(define (extract-labels text receive)
  (if (null? text)
      (receive '() '())
      (extract-labels 
       (cdr text)
       (lambda (insts labels)
         (let ((next-inst (car text)))
           (if (symbol? next-inst)
               (receive 
                   insts
                   (cons 
                    (make-label-entry 
                     next-inst
                     insts)
                    labels))
               (receive 
                   (cons (make-instruction 
                          next-inst)
                         insts)
                   labels)))))))

Mae Extract-labels yn gweithio drwy sganio elfennau'r text yn eu trefn a chasglu'r insts a'r labels. Os yw elfen yn symbol (ac felly'n label), ychwanegir cofnod priodol at y tabl labels. Fel arall, cesglir yr elfen ar y rhestr insts.²⁸⁹

Mae Update-insts! yn addasu'r rhestr gyfarwyddiadau, sydd i ddechrau'n cynnwys testun y cyfarwyddiadau yn unig, i gynnwys y gweithdrefnau gweithredu cyfatebol:

(define (update-insts! insts labels machine)
  (let ((pc (get-register machine 'pc))
        (flag (get-register machine 'flag))
        (stack (machine 'stack))
        (ops (machine 'operations)))
    (for-each
     (lambda (inst)
       (set-instruction-execution-proc!
        inst
        (make-execution-procedure
         (instruction-text inst) 
         labels
         machine
         pc
         flag
         stack
         ops)))
     insts)))

Yn syml, mae strwythur data cyfarwyddyd peiriant yn paru testun y cyfarwyddyd â'r weithdrefn weithredu gyfatebol. Nid yw'r weithdrefn weithredu ar gael eto pan fydd extract-labels yn adeiladu'r cyfarwyddyd, ac fe'i mewnosodir yn ddiweddarach gan update-insts!.

(define (make-instruction text)
  (cons text '()))
(define (instruction-text inst) (car inst))
(define (instruction-execution-proc inst)
  (cdr inst))
(define (set-instruction-execution-proc!
         inst
         proc)
  (set-cdr! inst proc))

Nid yw ein hefelychydd yn defnyddio testun y cyfarwyddyd, ond mae'n ddefnyddiol ei gadw ar gyfer dadfygio (gweler Ymarfer 5.16).

Parau yw elfennau'r tabl labeli:

(define (make-label-entry label-name insts)
  (cons label-name insts))

Chwilir am gofnodion yn y tabl drwy

(define (lookup-label labels label-name)
  (let ((val (assoc label-name labels)))
    (if val
        (cdr val)
        (error "Undefined label: ASSEMBLE" 
               label-name))))

Ymarfer 5.8: Mae'r cod peiriant cofrestri canlynol yn amwys, oherwydd bod y label here wedi'i ddiffinio fwy nag unwaith:
start
  (goto (label here))
here
  (assign a (const 3))
  (goto (label there))
here
  (assign a (const 4))
  (goto (label there))
there
Gyda'r efelychydd fel y'i hysgrifennwyd, beth fydd cynnwys cofrestr a pan fydd rheolaeth yn cyrraedd there? Addaswch y weithdrefn extract-labels fel y bydd y cydosodydd yn rhoi signal gwall os defnyddir yr un enw label i ddynodi dau leoliad gwahanol.

5.2.3Cynhyrchu Gweithdrefnau Gweithredu ar gyfer Cyfarwyddiadau

Mae'r cydosodydd yn galw make-execution-procedure i gynhyrchu'r weithdrefn weithredu ar gyfer cyfarwyddyd. Fel y weithdrefn analyze yng ngwerthusydd 4.1.7, mae hon yn dewis gweithdrefn yn ôl math y cyfarwyddyd er mwyn cynhyrchu'r weithdrefn weithredu briodol.

(define (make-execution-procedure 
         inst labels machine pc flag stack ops)
  (cond ((eq? (car inst) 'assign)
         (make-assign 
          inst machine labels ops pc))
        ((eq? (car inst) 'test)
         (make-test 
          inst machine labels ops flag pc))
        ((eq? (car inst) 'branch)
         (make-branch 
          inst machine labels flag pc))
        ((eq? (car inst) 'goto)
         (make-goto inst machine labels pc))
        ((eq? (car inst) 'save)
         (make-save inst machine stack pc))
        ((eq? (car inst) 'restore)
         (make-restore inst machine stack pc))
        ((eq? (car inst) 'perform)
         (make-perform
          inst machine labels ops pc))
        (else (error "Unknown instruction 
                      type: ASSEMBLE"
                     inst))))

Ar gyfer pob math o gyfarwyddyd yn yr iaith peiriannau cofrestri, ceir cynhyrchydd sy'n adeiladu gweithdrefn weithredu briodol. Mae manylion y gweithdrefnau hyn yn pennu cystrawen ac ystyr y cyfarwyddiadau unigol yn yr iaith peiriannau cofrestri. Defnyddiwn haniaethu data i ynysu cystrawen fanwl mynegiadau peiriannau cofrestri oddi wrth y mecanwaith gweithredu cyffredinol, fel y gwnaethom ar gyfer gwerthuswyr yn 4.1.2, drwy ddefnyddio gweithdrefnau cystrawen i echdynnu a dosbarthu rhannau cyfarwyddyd.

Cyfarwyddiadau `Assign`

Mae'r weithdrefn make-assign yn ymdrin â chyfarwyddiadau assign:

(define (make-assign 
         inst machine labels operations pc)
  (let ((target 
         (get-register 
          machine 
          (assign-reg-name inst)))
        (value-exp (assign-value-exp inst)))
    (let ((value-proc
           (if (operation-exp? value-exp)
               (make-operation-exp
                value-exp 
                machine
                labels
                operations)
               (make-primitive-exp
                (car value-exp)
                machine
                labels))))
      (lambda ()   ; execution procedure
                   ; for assign
        (set-contents! target (value-proc))
        (advance-pc pc)))))

Mae Make-assign yn echdynnu enw'r gofrestr darged (ail elfen y cyfarwyddyd) a'r mynegiad gwerth (gweddill y rhestr sy'n ffurfio'r cyfarwyddyd) o'r cyfarwyddyd assign gan ddefnyddio'r detholwyr

(define (assign-reg-name assign-instruction)
  (cadr assign-instruction))
(define (assign-value-exp assign-instruction)
  (cddr assign-instruction))

Chwilir am enw'r gofrestr drwy get-register i gael gwrthrych y gofrestr darged. Trosglwyddir y mynegiad gwerth i make-operation-exp os yw'r gwerth yn ganlyniad gweithrediad, ac i make-primitive-exp fel arall. Mae'r gweithdrefnau hyn (a ddangosir isod) yn dosrannu'r mynegiad gwerth ac yn cynhyrchu gweithdrefn weithredu ar gyfer y gwerth. Gweithdrefn heb argiau yw hon, o'r enw value-proc, a werthusir yn ystod yr efelychiad i gynhyrchu'r gwerth gwirioneddol sydd i'w aseinio i'r gofrestr. Sylwch mai dim ond unwaith, adeg cydosod, y cyflawnir y gwaith o chwilio am enw'r gofrestr a dosrannu'r mynegiad gwerth, nid bob tro y mae'r cyfarwyddyd yn cael ei efelychu. Yr arbediad gwaith hwn yw'r rheswm dros ddefnyddio gweithdrefnau gweithredu, ac mae'n cyfateb yn uniongyrchol i'r arbediad gwaith a gawsom drwy wahanu dadansoddi rhaglen oddi wrth ei gweithredu yng ngwerthusydd 4.1.7.

Y canlyniad a ddychwelir gan make-assign yw gweithdrefn weithredu'r cyfarwyddyd assign. Pan elwir y weithdrefn hon (gan weithdrefn execute model y peiriant), mae'n gosod cynnwys y gofrestr darged i'r canlyniad a geir drwy weithredu value-proc. Yna mae'n symud y pc ymlaen at y cyfarwyddyd nesaf drwy redeg y weithdrefn

(define (advance-pc pc)
  (set-contents! pc (cdr (get-contents pc))))

Advance-pc yw'r terfyniad arferol ar gyfer pob cyfarwyddyd heblaw branch ac goto.

Cyfarwyddiadau `Test`, `branch`, ac `goto`

Mae Make-test yn ymdrin â chyfarwyddiadau test mewn ffordd debyg. Mae'n echdynnu'r mynegiad sy'n pennu'r amod sydd i'w brofi ac yn cynhyrchu gweithdrefn weithredu ar ei gyfer. Adeg efelychu, gelwir gweithdrefn yr amod, aseinir y canlyniad i'r gofrestr flag, a symudir y pc ymlaen:

(define 
  (make-test 
   inst machine labels operations flag pc)
  (let ((condition (test-condition inst)))
    (if (operation-exp? condition)
        (let ((condition-proc
               (make-operation-exp
                condition 
                machine
                labels
                operations)))
          (lambda () 
            (set-contents! 
             flag (condition-proc))
            (advance-pc pc)))
        (error "Bad TEST instruction: 
                ASSEMBLE" inst))))

(define (test-condition test-instruction)
  (cdr test-instruction))

Mae gweithdrefn weithredu cyfarwyddyd branch yn gwirio cynnwys y gofrestr flag ac yn gosod cynnwys y pc i gyrchfan y gangen (os cymerir y gangen) neu'n symud y pc ymlaen yn unig (os na chymerir y gangen). Sylwch fod yn rhaid i'r cyrchfan a ddangosir mewn cyfarwyddyd branch fod yn label, ac mae'r weithdrefn make-branch yn gorfodi hyn. Sylwch hefyd y chwilir am y label adeg cydosod, nid bob tro y mae'r cyfarwyddyd branch yn cael ei efelychu.

(define 
  (make-branch 
   inst machine labels flag pc)
  (let ((dest (branch-dest inst)))
    (if (label-exp? dest)
        (let ((insts
               (lookup-label 
                labels 
                (label-exp-label dest))))
          (lambda ()
            (if (get-contents flag)
                (set-contents! pc insts)
                (advance-pc pc))))
        (error "Bad BRANCH instruction: 
                ASSEMBLE"
               inst))))

(define (branch-dest branch-instruction)
  (cadr branch-instruction))

Mae cyfarwyddyd goto yn debyg i gangen, heblaw y gellir pennu'r cyrchfan naill ai fel label neu fel cofrestr, ac nad oes amod i'w wirio—gosodir y pc i'r cyrchfan newydd bob amser.

(define (make-goto inst machine labels pc)
  (let ((dest (goto-dest inst)))
    (cond ((label-exp? dest)
           (let ((insts
                  (lookup-label 
                   labels
                   (label-exp-label dest))))
             (lambda () 
               (set-contents! pc insts))))
          ((register-exp? dest)
           (let ((reg
                  (get-register 
                   machine
                   (register-exp-reg dest))))
             (lambda ()
               (set-contents! 
                pc
                (get-contents reg)))))
          (else (error "Bad GOTO instruction: 
                        ASSEMBLE"
                       inst)))))

(define (goto-dest goto-instruction)
  (cadr goto-instruction))

Cyfarwyddiadau eraill

Yn syml, mae'r cyfarwyddiadau pentwr save ac restore yn defnyddio'r pentwr gyda'r gofrestr ddynodedig ac yn symud y pc ymlaen:

(define (make-save inst machine stack pc)
  (let ((reg (get-register 
              machine
              (stack-inst-reg-name inst))))
    (lambda ()
      (push stack (get-contents reg))
      (advance-pc pc))))

(define (make-restore inst machine stack pc)
  (let ((reg (get-register
              machine
              (stack-inst-reg-name inst))))
    (lambda ()
      (set-contents! reg (pop stack))
      (advance-pc pc))))

(define (stack-inst-reg-name 
         stack-instruction)
  (cadr stack-instruction))

Mae'r math olaf o gyfarwyddyd, yr ymdrinnir ag ef gan make-perform, yn cynhyrchu gweithdrefn weithredu ar gyfer y weithred sydd i'w chyflawni. Adeg efelychu, gweithredir gweithdrefn y weithred a symudir y pc ymlaen.

(define (make-perform 
         inst machine labels operations pc)
  (let ((action (perform-action inst)))
    (if (operation-exp? action)
        (let ((action-proc
               (make-operation-exp
                action
                machine
                labels
                operations)))
          (lambda ()
            (action-proc)
            (advance-pc pc)))
        (error "Bad PERFORM instruction: 
                ASSEMBLE"
               inst))))

(define (perform-action inst) (cdr inst))

Gweithdrefnau gweithredu ar gyfer isfynegiadau

Gall fod angen gwerth mynegiad reg, label, neu const i'w aseinio i gofrestr (make-assign) neu i fod yn fewnbwn i weithrediad (make-operation-exp, isod). Mae'r weithdrefn ganlynol yn cynhyrchu gweithdrefnau gweithredu i gynhyrchu gwerthoedd ar gyfer y mynegiadau hyn yn ystod yr efelychiad:

(define (make-primitive-exp exp machine labels)
  (cond ((constant-exp? exp)
         (let ((c (constant-exp-value exp)))
           (lambda () c)))
        ((label-exp? exp)
         (let ((insts
                (lookup-label 
                 labels
                 (label-exp-label exp))))
           (lambda () insts)))
        ((register-exp? exp)
         (let ((r (get-register
                   machine
                   (register-exp-reg exp))))
           (lambda () (get-contents r))))
        (else (error "Unknown expression type: 
                      ASSEMBLE"
                     exp))))

Pennir cystrawen mynegiadau reg, label, ac const gan

(define (register-exp? exp)
  (tagged-list? exp 'reg))
(define (register-exp-reg exp)
  (cadr exp))
(define (constant-exp? exp)
  (tagged-list? exp 'const))
(define (constant-exp-value exp)
  (cadr exp))
(define (label-exp? exp)
  (tagged-list? exp 'label))
(define (label-exp-label exp) 
  (cadr exp))

Gall cyfarwyddiadau Assign, perform, ac test gynnwys cymhwyso gweithrediad peiriant (a bennir gan fynegiad op) i rai operandau (a bennir gan fynegiadau reg ac const). Mae'r weithdrefn ganlynol yn cynhyrchu gweithdrefn weithredu ar gyfer “mynegiad gweithrediad”—rhestr sy'n cynnwys mynegiadau'r gweithrediad a'r operandau o'r cyfarwyddyd:

(define (make-operation-exp
         exp machine labels operations)
  (let ((op (lookup-prim 
             (operation-exp-op exp)
             operations))
        (aprocs
         (map (lambda (e)
                (make-primitive-exp 
                 e machine labels))
              (operation-exp-operands exp))))
    (lambda () (apply op (map (lambda (p) (p))
                              aprocs)))))

Pennir cystrawen mynegiadau gweithrediad gan

(define (operation-exp? exp)
  (and (pair? exp)
       (tagged-list? (car exp) 'op)))
(define (operation-exp-op operation-exp)
  (cadr (car operation-exp)))
(define (operation-exp-operands operation-exp)
  (cdr operation-exp))

Sylwch fod y ffordd yr ymdrinnir â mynegiadau gweithrediad yn debyg iawn i'r ffordd y mae'r weithdrefn analyze-application yng ngwerthusydd 4.1.7 yn ymdrin â chymwysiadau gweithdrefn, gan ein bod yn cynhyrchu gweithdrefn weithredu ar gyfer pob operand. Adeg efelychu, galwn weithdrefnau'r operandau a chymhwyswn y weithdrefn Scheme sy'n efelychu'r gweithrediad i'r gwerthoedd a geir. Canfyddir y weithdrefn efelychu drwy chwilio am enw'r gweithrediad yn nhabl gweithrediadau'r peiriant:

(define (lookup-prim symbol operations)
  (let ((val (assoc symbol operations)))
    (if val
        (cadr val)
        (error "Unknown operation: ASSEMBLE"
               symbol))))

Ymarfer 5.9: Mae'r ffordd yr ymdrinnir â gweithrediadau peiriant uchod yn caniatáu iddynt weithredu ar labeli yn ogystal ag ar gysonion a chynnwys cofrestri. Addaswch y gweithdrefnau prosesu mynegiadau i orfodi'r amod mai dim ond gyda chofrestri a chysonion y gellir defnyddio gweithrediadau.

Ymarfer 5.10: Dyluniwch gystrawen newydd ar gyfer cyfarwyddiadau peiriant cofrestri ac addaswch yr efelychydd i ddefnyddio eich cystrawen newydd. A allwch weithredu eich cystrawen newydd heb newid unrhyw ran o'r efelychydd heblaw'r gweithdrefnau cystrawen yn yr adran hon?

Ymarfer 5.11: Pan gyflwynasom save ac restore yn 5.1.4, ni phennasom beth fyddai'n digwydd pe baech yn ceisio adfer cofrestr nad honno oedd yr olaf i'w chadw, fel yn y dilyniant
(save y)
(save x)
(restore y)
Mae sawl posibilrwydd rhesymol ar gyfer ystyr restore:

Mae (restore y) yn rhoi yn y y gwerth olaf a gadwyd ar y pentwr, waeth o ba gofrestr y daeth y gwerth hwnnw. Dyma sut mae ein hefelychydd yn ymddwyn. Dangoswch sut i fanteisio ar yr ymddygiad hwn i ddileu un cyfarwyddyd o beiriant Fibonacci 5.1.4 (Ffigur 5.12).
Mae (restore y) yn rhoi yn y y gwerth olaf a gadwyd ar y pentwr, ond dim ond os cadwyd y gwerth hwnnw o y; fel arall, mae'n rhoi signal gwall. Addaswch yr efelychydd i ymddwyn fel hyn. Bydd yn rhaid newid save i roi enw'r gofrestr ar y pentwr ynghyd â'r gwerth.
Mae (restore y) yn rhoi yn y y gwerth olaf a gadwyd o y waeth pa gofrestri eraill a gadwyd ar ôl y ac na chawsant eu hadfer. Addaswch yr efelychydd i ymddwyn fel hyn. Bydd yn rhaid cysylltu pentwr ar wahân â phob cofrestr. Dylech wneud i'r gweithrediad initialize-stack gychwyn holl bentyrrau'r cofrestri.

Ymarfer 5.12: Gellir defnyddio'r efelychydd i helpu i bennu'r llwybrau data sydd eu hangen i weithredu peiriant â rheolydd penodol. Ymestynnwch y cydosodydd i storio'r wybodaeth ganlynol ym model y peiriant:

rhestr o'r holl gyfarwyddiadau, gyda dyblygiadau wedi'u tynnu, wedi'u didoli yn ôl math y cyfarwyddyd (assign, goto, ac ati);
rhestr (heb ddyblygiadau) o'r cofrestri a ddefnyddir i ddal pwyntiau mynediad (dyma'r cofrestri y cyfeirir atynt gan gyfarwyddiadau goto);
rhestr (heb ddyblygiadau) o'r cofrestri a gedwir drwy save neu a adferir drwy restore;
ar gyfer pob cofrestr, rhestr (heb ddyblygiadau) o'r ffynonellau yr aseinir iddi ohonynt (er enghraifft, ffynonellau cofrestr val ym mheiriant ffactorial Ffigur 5.11 yw (const 1) ac ((op *) (reg n) (reg val))).

Ymestynnwch ryngwyneb trosglwyddo negeseuon y peiriant i ddarparu mynediad at y wybodaeth newydd hon. I brofi eich dadansoddwr, diffiniwch y peiriant Fibonacci o Ffigur 5.12 ac archwiliwch y rhestrau a adeiladasoch.

Ymarfer 5.13: Addaswch yr efelychydd fel ei fod yn defnyddio dilyniant y rheolydd i bennu pa gofrestri sydd gan y peiriant yn hytrach na gofyn am restr o gofrestri yn arg i make-machine. Yn hytrach na dyrannu'r cofrestri ymlaen llaw yn make-machine, gallwch eu dyrannu fesul un pan welir hwy gyntaf wrth gydosod y cyfarwyddiadau.

5.2.4Monitro Perfformiad Peiriant

Mae efelychu'n ddefnyddiol nid yn unig ar gyfer gwirio cywirdeb dyluniad peiriant arfaethedig ond hefyd ar gyfer mesur perfformiad y peiriant. Er enghraifft, gallwn osod yn ein rhaglen efelychu “fesurydd” sy'n mesur nifer y gweithrediadau pentwr a ddefnyddir mewn cyfrifiad. I wneud hyn, addaswn ein pentwr wedi'i efelychu i gadw cofnod o nifer yr adegau y cedwir cofrestri ar y pentwr a'r dyfnder mwyaf a gyrhaeddir gan y pentwr, ac ychwanegwn neges at ryngwyneb y pentwr sy'n argraffu'r ystadegau, fel y dangosir isod. Ychwanegwn hefyd weithrediad at fodel sylfaenol y peiriant i argraffu ystadegau'r pentwr, drwy gychwyn the-ops yn make-new-machine i

(list (list 'initialize-stack
            (lambda () 
              (stack 'initialize)))
      (list 'print-stack-statistics
            (lambda () 
              (stack 'print-statistics))))

Dyma'r fersiwn newydd o make-stack:

(define (make-stack)
  (let ((s '())
        (number-pushes 0)
        (max-depth 0)
        (current-depth 0))
    (define (push x)
      (set! s (cons x s))
      (set! number-pushes (+ 1 number-pushes))
      (set! current-depth (+ 1 current-depth))
      (set! max-depth 
            (max current-depth max-depth)))
    (define (pop)
      (if (null? s)
          (error "Empty stack: POP")
          (let ((top (car s)))
            (set! s (cdr s))
            (set! current-depth
                  (- current-depth 1))
            top)))
    (define (initialize)
      (set! s '())
      (set! number-pushes 0)
      (set! max-depth 0)
      (set! current-depth 0)
      'done)

    (define (print-statistics)
      (newline)
      (display (list 'total-pushes 
                     '= 
                     number-pushes
                     'maximum-depth
                     '=
                     max-depth)))
    (define (dispatch message)
      (cond ((eq? message 'push) push)
            ((eq? message 'pop) (pop))
            ((eq? message 'initialize)
             (initialize))
            ((eq? message 'print-statistics)
             (print-statistics))
            (else
             (error "Unknown request: STACK"
                    message))))
    dispatch))

Mae Ymarfer 5.15 hyd at Ymarfer 5.19 yn disgrifio nodweddion monitro a dadfygio defnyddiol eraill y gellir eu hychwanegu at yr efelychydd peiriannau cofrestri.

Ymarfer 5.14: Mesurwch nifer y gwthiadau a dyfnder mwyaf y pentwr sydd eu hangen i gyfrifiannu $n!$ ar gyfer amrywiol werthoedd bach o $n$ gan ddefnyddio'r peiriant ffactorial a ddangosir yn Ffigur 5.11. O'ch data, pennwch fformiwlâu yn nhermau $n$ ar gyfer cyfanswm nifer y gweithrediadau gwthio a dyfnder mwyaf y pentwr a ddefnyddir wrth gyfrifiannu $n!$ ar gyfer unrhyw $n > 1$ . Sylwch fod pob un o'r rhain yn ffwythiant llinol o $n$ ac felly'n cael ei bennu gan ddau gysonyn. Er mwyn argraffu'r ystadegau, bydd yn rhaid ychwanegu cyfarwyddiadau at y peiriant ffactorial i gychwyn y pentwr ac argraffu'r ystadegau. Efallai y byddwch hefyd am addasu'r peiriant fel ei fod yn darllen gwerth ar gyfer $n$ , yn cyfrifiannu'r ffactorial, ac yn argraffu'r canlyniad dro ar ôl tro (fel y gwnaethom ar gyfer y peiriant GCD yn Ffigur 5.4), fel na fydd yn rhaid ichi alw get-register-contents, set-register-contents!, ac start dro ar ôl tro.

Ymarfer 5.15: Ychwanegwch gyfrif cyfarwyddiadau at yr efelychiad peiriant cofrestri. Hynny yw, gwnewch i fodel y peiriant gadw cofnod o nifer y cyfarwyddiadau a weithredwyd. Ymestynnwch ryngwyneb model y peiriant i dderbyn neges newydd sy'n argraffu gwerth y cyfrif cyfarwyddiadau ac yn ailosod y cyfrif i sero.

Ymarfer 5.16: Ychwanegwch at yr efelychydd i ddarparu olrhain cyfarwyddiadau. Hynny yw, cyn gweithredu pob cyfarwyddyd, dylai'r efelychydd argraffu testun y cyfarwyddyd. Gwnewch i fodel y peiriant dderbyn negeseuon trace-on ac trace-off i droi olrhain ymlaen ac i ffwrdd.

Ymarfer 5.17: Ymestynnwch olrhain cyfarwyddiadau Ymarfer 5.16 fel bod yr efelychydd, cyn argraffu cyfarwyddyd, yn argraffu unrhyw labeli sy'n rhagflaenu'r cyfarwyddyd hwnnw'n uniongyrchol yn nilyniant y rheolydd. Byddwch yn ofalus i wneud hyn mewn ffordd nad yw'n amharu ar gyfrif cyfarwyddiadau (Ymarfer 5.15). Bydd yn rhaid gwneud i'r efelychydd gadw'r wybodaeth angenrheidiol am y labeli.

Ymarfer 5.18: Addaswch weithdrefn make-register 5.2.1 fel y gellir olrhain cofrestri. Dylai cofrestri dderbyn negeseuon sy'n troi olrhain ymlaen ac i ffwrdd. Wrth olrhain cofrestr, dylai aseinio gwerth iddi argraffu enw'r gofrestr, ei hen gynnwys, a'r cynnwys newydd sy'n cael ei aseinio. Ymestynnwch y rhyngwyneb at fodel y peiriant i ganiatáu ichi droi olrhain ymlaen ac i ffwrdd ar gyfer cofrestri peiriant penodol.

Ymarfer 5.19: Mae Alyssa P. Hacker am gael nodwedd torbwynt yn yr efelychydd i'w helpu i ddadfygio dyluniadau ei pheiriannau. Fe'ch cyflogwyd i osod y nodwedd hon iddi. Mae am allu pennu man yn nilyniant y rheolydd lle bydd yr efelychydd yn stopio ac yn caniatáu iddi archwilio cyflwr y peiriant. Eich tasg yw gweithredu gweithdrefn
(set-breakpoint ⟨machine⟩ ⟨label⟩ ⟨n⟩)
sy'n gosod torbwynt yn union cyn cyfarwyddyd rhif $n^{fed}$ ar ôl y label a roddwyd. Er enghraifft, mae
(set-breakpoint gcd-machine 'test-b 4)
yn gosod torbwynt yn gcd-machine yn union cyn yr aseiniad i gofrestr a. Pan fydd yr efelychydd yn cyrraedd y torbwynt, dylai argraffu label a gwrthbwyso'r torbwynt a stopio gweithredu cyfarwyddiadau. Yna gall Alyssa ddefnyddio get-register-contents ac set-register-contents! i drin cyflwr y peiriant wedi'i efelychu. Dylai wedyn allu parhau i weithredu drwy ddweud
(proceed-machine ⟨machine⟩)
Dylai hefyd allu dileu torbwynt penodol drwy
(cancel-breakpoint ⟨machine⟩ ⟨label⟩ ⟨n⟩)
neu ddileu pob torbwynt drwy
(cancel-all-breakpoints ⟨machine⟩)

Troednodiadau

²⁸⁹ Mae defnyddio'r weithdrefn receive yma yn ffordd o wneud i extract-labels ddychwelyd dau werth i bob pwrpas—labels ac insts—heb greu strwythur data cyfansawdd penodol i'w dal. Gweithrediad amgen, sy'n dychwelyd pâr penodol o werthoedd, yw

(define (extract-labels text)
  (if (null? text)
      (cons '() '())
      (let ((result 
             (extract-labels (cdr text))))
        (let ((insts (car result))
              (labels (cdr result)))
          (let ((next-inst (car text)))
            (if (symbol? next-inst)
                (cons 
                 insts
                 (cons 
                  (make-label-entry 
                   next-inst insts) 
                  labels))
                (cons 
                 (cons 
                  (make-instruction next-inst) 
                  insts)
                 labels)))))))

a fyddai'n cael ei alw gan assemble fel a ganlyn:

(define (assemble controller-text machine)
  (let ((result 
         (extract-labels controller-text)))
    (let ((insts (car result))
          (labels (cdr result)))
      (update-insts! insts labels machine)
      insts)))

Gallwch ystyried ein defnydd o receive yn arddangosiad o ffordd gain o ddychwelyd gwerthoedd lluosog, neu'n syml yn esgus i ddangos tric rhaglennu. Gelwir arg megis receive, sef y weithdrefn nesaf i'w galw, yn “barhad.” Cofiwch inni hefyd ddefnyddio parhadau i weithredu'r strwythur rheoli gwrthgilio yn y gwerthusydd amb yn 4.3.3.