Friday, December 13, 2013

Ստեկային մեքենայի մոդել։ Մաս I

Պատկերացենք մի վերացական համակարգիչ, որի պրոցեսորի հրամանները նախատեսված են ստեկային վարքով աշխատելու համար։ Օրինակ ADD հրամանը արգումենտներ չունի, այլ վերցնում է ստեկի գագաթի երկու տարրերը, դրանք գումարում է իրար և արդյունքը նորից գրում է ստեկում։ Ենթադրենք, թե մեքենան կարող է աշխատել միայն ամբողջ թվերի հետ։

Ֆիզիկական կառուցվածքի տեսակետից այդ մեքենան (ստեկային համակարգիչը) ունի ընդհանուր օգտագործման հիշողություն, որում պահվում են կատարվող ծրագիրը, ստատիկ տվյալները, գլոբալ փոփոխականներ, և հենց այդ հիշողության ինչ-որ տիրույթում մոդելավորվում է ստեկը։
(defconstant +size+ 1024 "Հիշողության չափը")
(defparameter *memory* (make-array +size+)
  "Հիշողությունը որպես տրված չափի զանգված")
Մեքենան ունի նաև երեք ռեգիստրներ. ա) հերթական հատարվող հրամանի ցուցիչ՝ IP, բ) ստեկի գագաթի ցուցիչ՝ SP և գ) ստեկի կադրի ցուցիչ՝ FP, որը ֆունկցիաների կանչի ժամանակ օգտագործվում է ֆունկցիայի արգումենտներին և լոկալ փոփոխականների հասցեներին դիմելու համար։
(defparameter *ip* -1 "Հերթական հրամանի ցուցիչ")
(defparameter *sp* -1 "Ստեկի ցուցիչ")
(defparameter *fp* -1 "Ստեկի կադրի ցուցիչ")
Պարզության համար ընդունենք, որ կատարվող ծրագիրը բեռնվում է հիշողության 0 հասցեից։ Ծրագիր զբաղեցրած տիրույթին հաջորդում է ստատիկ տվյալների և գլոբալ փոփոխականների տիրույթը՝ տվյալների սեգմենտը։ Իսկ տվյալների սեգմենտին հաջորդում է ստեկի սեգմենտը։ Օրինակ, եթե հիշողության մեջ բեռնվել է 16 հրամաններից բաղկացած ծրագիր, որում կան 8 գլոբալ փոփոխականներ, ապա կոդի սեգմենտը կսկսվի 0 հասցեից, տվյալների սեգմենտը՝ 16 հասցեից, իսկ ստեկի սեգմենտը՝ 24 հասցեից։

«Ստեկային մեքենայի» հրամանները ստորև կներկայացվեն նրա «ասեմբլերի» լեզվով։ Մեքենայի հիշողություն բեռնվելուց հետո, բնականաբար, հրամանները կունենան այլ տեսք։

Ստեկում հաստատուն թիվ կարելի է ավելացնել PUSH հրամանով։ Օրինակ,
PUSH 777  ; ստեկում ավելացնել 777 արժեքը
Որևէ փոփոխականի արժեք ստեկում ավելացնելու համար նույնպես օգտագործվում է PUSH հրամանը՝ արգումենտում ունենալով փոփոխականի իդենտիֆիկատորը։ Փոփոխականների անունները կարող են սկսվել լատինական փոքրատառով և պարունակել միայն փոքրատառեր և թվանշաններ։ Օրինակ,
PUSH a    ; ստեկում ավելացնել a փոփոխականի զբաղեցրած հասցեում գրված արժեքը
PUSH wu3  ; ստեկում ավելացնել wu3 փոփոխականի զբաղեցրած հասցեում գրված արժեքը
Եթե հարկավոր է ստեկում ավելացնել հենց ռեգիստրի պարունակությունը, ապա ստեկի անունը պետք է սկսել «%» նիշով։ ենթադրենք M-ը ստեկային մեքենայի հիշողությունն է։ Այս դեպքում․
PUSH %FP   ; <=> SP := SP + 1; M[SP] := FP
PUSH %SP   ; <=> SPi := SPo + 1; M[SPi] := SPo
Անուղակի հասցեավորում կարելի է կատարել ռեգիստրի արժեքի օգնությամբ։ Օրինակ,
PUSH FP   ; <=> SP := SP + 1; M[SP] := M[FP]
PUSH FP+3 ; <=> SP := SP + 1; M[SP] := M[FP+3]
Այս չորս տիպի PUSH հրամանները կարելի է իրականացնել հետևյալ կերպ։
(defun push-value (value)
  (setf (aref *memory* (incf *sp*)) value))
(defun push-addr (address)
  (push-value (aref *memory* address)))
(defun push-regv (reg)
  (push-value (case reg (0 *ip*) (1 *sp*) (2 *fp*))))
(defun push-reg (reg &optional (disp 0))
  (let ((bs (case reg (0 *ip*) (1 *sp*) (2 *fp*))))
    (push-addr (+ bs disp))))
Ստեկից տվյալներ հեռացնելու համար է նախատեսված POP հրամանը։ Ստեկի գագաթի տարրը որևէ փոփոխականի վերագրելու համար POP հրամանն արգումենտում ունիփոփոխականի անունը։ Օրինակ.
POP u
Ինչպես PUSH հրամանը, նույնպես էլ POP հրամանը կարող է օգտագործել ռեգիստրի արժեքը՝ անուղակի հասցեավորում կազմակերպելու համար։ Օրինակ.
POP FP+1
POP FP
POP FP-12
Նշված երեք տիպի POP հրամաններն էլ իրականացված են հետևյալ ֆունկցիաներով։
(defun pop-value ()
  (aref *memory* (prog1 *sp* (decf *sp*))))
(defun pop-addr (address)
  (setf (aref *memory* address) (pop-value)))
(defun pop-regv (reg)
  (let ((vl (pop-value)))
    (case reg 
      (0 (setf *ip* vl))
      (1 (setf *sp* vl))
      (2 (setf *fp* vl)))))
(defun pop-reg (reg &optional (disp 0))
  (let ((bs (case reg (0 *ip*) (1 *sp*) (2 *fp*))))
    (pop-addr (+ bs disp))))
Օգտագործողի կողմից տվյալները ներմուծվում են IN հրամանով, որը ներմուծած թիվը գրում է ստեկի գագաթում։ Իսկ գործողությունների արդյունքն օգտագործողի համար արտածվում են OUT հրամանով, որը հեռացնում է ստեկի գագթի արժեքը և արտածում է ստանդարտ արտածման հոսքին։ Հետևյալ երկու ֆունկցիաներն այդ հրամանների իրականացումներն են.
(defun input-num ()
  (format t "? ")
  (push-value (parse-integer (read-line))))
(defun output-num ()
  (format t "> ~d~%" (pop-value)))
Ստեկային մեքենայի հրամանների համակարգում նախատեսված են նաև թվաբանական ու համեմատման գործողություններ, ինչպիսիք են գումարում, հանում, հավասարության ստուգում և այլն։ Բայց նախ սահմանենք binary-op և unary-op ֆունկցիաները, որոնց օգնությամբ կսահմանենք կոնկրետ բինար և ունար գործողություններ։
(defun binary-op (operation)
  (let* ((ao (pop-value))
         (ai (pop-value)))
    (push-value (funcall operation ai ao))))
(defun unary-op (operation)
  (let ((ao (pop-value)))
    (push-value (funcall operation ao))))
Հետո նոր սահմանենք ADD, SUB, MUL, DIV, MOD, EQ, NE, GT, GE, LT, LE բինար գործողությունները, ինչպես նաև NEG և NOT ունար գործողությունները։
(defun op-add () (binary-op #'+))
(defun op-sub () (binary-op #'-))
(defun op-mul () (binary-op #'*))
(defun op-div () (binary-op #'/))
(defun op-mod () (binary-op #'rem))
(defun op-eq () (binary-op #'=))
(defun op-ne () (binary-op #'/=))
(defun op-gt () (binary-op #'>))
(defun op-ge () (binary-op #'>=))
(defun op-lt () (binary-op #'<))
(defun op-le () (binary-op #'<=))
(defun op-not () (unary-op #'not))
(defun op-neg () (unary-op #'(lambda (x) (* x -1))))
Մինչև այս պահը թվարկված հրամաններով կարելի է կառուցել միայն գծային ալգորիթմներ։ Որպեսզի հնարավոր լինի ծրագրավորել ճյուղավորվող ու կրկնվող ալգորիթմներ, մեքենան պետք է ունենա անցման հրամաններ։ Ստեկային մեքենայի մոդելում JZ հրամանը անցում է կատարում տրված հասցեով հրամանին, եթե ստեկի գագաթի տարրը զրո է։ Նմանապես JNZ հրամանը անցում է կատարում տրված հասցեով հրամանին, եթե ստեկի գագաթում զրոյից տարբեր արժեք է։ Այս երկու հրամաններն էլ հեռացնում են ստեկի գագաթի տարրը։ Իսկ JUMP հրամանը պարզապես առանց պայմանի անցում է։ Բոլոր երեք հրամաններն էլ փոխում են IP ռեգիստրի արժեքը։
(defun jump (address)
  (setf *ip* address))
(defun jump-true (address)
  (when (pop-value) (jump address)))
(defun jump-false (address)
  (unless (pop-value) (jump address)))
Ասեմբլերային ծրագրի տեքստում նշիչներ (անցման կետեր) սահմանելու համար է LABEL փսևդոհրամանը։ Այն կատարվող հրամանի չի թարգմանվում, պարզապես իր արգումենտում տրված իդենտիֆիկատորին կապում է IP ռեգիստրի ընթացիկ արժեքը՝ հետագա հղումների համար։
LABEL wb0
;...
JUMP wb0
Եվս երկու հրամաններ, որոնք ապահովելու են ֆունկցիայի կանչ և վերադարձ ֆունկցիայից։ CALL հրամանի արգումենտը LABEL փսևդոհրամանով սահմանված իդենտիֆիկատոր է։
(defun call-func (address)
  (push-value 0)       ; ֆունկցիայի վերադարձրած արժեքի տեղը
  (push-value *ip*)    ; վերադարձի հասցեն, IP ռեգիստրի արժեքը
  (push-value *fp*)    ; ստեկի կադրի հին արժեքը
  (setf *fp* *sp*)     ; ստեկի կադրի ընթացիկ արժեքը
  (setf *ip* address)) ; IP ռեգիստրի նոր արժեքը
Ֆունկցիայից վերադարձի համար է նախատեսված RET հրամանը։ Այն տեղափոխում է ստեկի գագաէի տարրը վերադարձվող արժեքի համար նախատեսված տեսը։ վերականգնում է ստեկի ցուցիչի ռգիստրի հին արժեքը և IP ռեգիստրին վերագրում է CALL հրամանի նախատեսած վերադարձի հասցեն։
(defun return-func ()
  (pop-addr (- *fp* 2))    ; վերադարձվող արժեքը
  (setf *fp* (pop-value))  ; ստեկի կադրի ռեգիստրի վերականգնում
  (setf *ip* (pop-value))) ; վերադարձի հասցե

Ամբողջական կոդը տես github կայքում։