Հիշող սարք և տեստային ալգորիթմ

Ուսանողական առաջադրանքներից մեկում ես հանձնարարել էի գրել մի կոմպիլյատոր, որը թվային հիշող սարքի և տեստավորման ալգորիթմի տեքստային ներկայացումից կոմպիլյացնում է տեստավորող մեքենային կոդ։ Նկարագրման լեզվի քերականությունը մոտավորապես հետևյալն էր․

     script = { memory | algorithm | test }.
     memory = 'Memory' IDENT '{' 'Rows' '=' NUMBER 'Columns' '=' NUMBER '}'.
  algorithm = 'Algorithm' IDENT '{' { element } '}'.
    element = ('->'|'<-') '(' operation {',' operation } ')'.
  operation = (W|R)('0'|'1').
       test = 'Test' IDENT 'With' IDENT.

Այս քերականությամբ, օրինակ, կարելի է նկարագրել \(3\times2\) չափի հիշողության մատրից և նրա վրա գործարկել \(\Uparrow(W0);\Downarrow(W1,R1)\) պարզագույն տեստը։

  Memory r3c2 {
    Rows = 3
    Columns = 2
  }

  Algorithm A0 {
    ->(W0)
    <-(W1,R1)
  }

  Test r3c2 With A0

Այս սկրիպտի կոմպիլյացիայից հետո պետք է կառուցվեր տեստավորող մեքենայի՝ սիմուլյատորի մի այստպիսի կոդ․

  0 0 W 0
  0 1 W 0
  1 0 W 0
  1 1 W 0
  2 0 W 0
  2 1 W 0
  0 0 W 1
  0 0 R 1
  0 1 W 1
  0 1 R 1
  1 0 W 1
  1 0 R 1
  1 1 W 1
  1 1 R 1
  2 0 W 1
  2 0 R 1
  2 1 W 1
  2 1 R 1

Քառյակի առաջին տարրը տողի հասցեն է, երկրորդը՝ սյան, երրորդ տարրը գործողությունն է՝ W - գրել, R - կարդալ, չորրորդ տարրը գործողության արգումենտն է։

Այս քառյակները հիշողության սարքի մոդելի վրա սիմուլյացնելու համար պետք է նախ՝ ստեղծել փչացած բջիջներ պարունակող հիշողության մոդել, ապա քառյակների սիմուլյացիայի արդյունքում պարզել, թե որ հասցեում է տեստավորման ալգորիթմը ձախողվում։ * * * Սիմուլյատորի հիմնական գաղափարը հիշող սարքի բջիջն է, որում կարելի արժեք արժեք գրել և կարդալ սպասվող արժեք։ Այդ երկու գործողություններն ունեն այսպիսի ինտերֆեյս.

(defgeneric write-cell (c v))
(defgeneric read-cell (c))

Ճիշտ աշխատող բջիջը նկարագրել եմ cell անունով դասով․

(defclass cell ()
  ((value :initform 0
          :initarg :value
          :accessor cell-value)))

Որի համար գրելու գործողությունը տրված արժեքը վերագրում է value սլոտին, իսկ կարդալու գործողությունը վերադարձնում է value սլոտի արժեքը։

(defmethod write-cell ((c cell) v)
  (setf (cell-value c) v))
(defmethod read-cell ((c cell) v)
  (cell-value c))

Որպես օրինակ cell դասն ընդլայնել եմ և ստեղծել եմ cell-co դասը, որի կարդալու գործողությունը միշտ վերադարձնում է նախապես տրված հաստատուն արժեքը։

(defclass cell-co (cell) 
  ((coval :initform 0
          :initarg :coval
          :accessor cell-co-val)))

(defmethod read-cell ((c cell-co) v)
  (cell-co-val c))

Հիշող սարքի մոդելը երեք սլոտներով մի ստրուկտուա է․

(defstruct memory
  (rows 0)
  (columns 0)
  (matrix nil))

Հիշողության մոդելի կոնստրուկտորը մատրիցի բջիջները լրացնում է cell դասի օբյեկտներով։

(defun create-memory (row col)
  (let ((res (make-memory :rows row :columns col
                          :matrix (make-array (list row col)))))
    (dotimes (r (memory-rows res))
      (dotimes (c (memory-columns res))
        (setf (aref (memory-matrix res) r c)
              (make-instance 'cell :value 0))))
    res))

Հիշողության մոդելի համար նույնպես իրականացրել եմ գրելու և կարդալու գործողությունները։ Գրելու գործողությունը տրված արժեքը գրում է մատրիցի տրված կոորդինատներով բջջի մեջ, իսկ կարդալու գործողությունը տրված արժեքը համեմատում է մատրիցի տրված բջջի արժեքի հետ։ Քանի որ սա տեստավորման ալգորիթմները փորձարկելու համար նախատեսված մոդել է, այսպիսի վարքը լրիվ արդարացված է։

(defmethod write-memory ((m memory) r c v)
  (write-cell (aref (memory-matrix m) r c) v))
(defmethod read-memory ((m memory) r c v)
  (= (read-cell (aref (memory-matrix m) r c)) v))

Կոմպիլյացված ալգորիթմը հիշող սարքի մոդելի վրա գործարկելու համար նախատեսել եմ run-algorithm-on ֆունկցիան։ Այն արգումենտում ստանում է հիշողության մոդելը և քառյակների ֆայլը։

(defun run-algorithm-on (mem alg)
  (dolist (co (read-whole-algorithm alg))
    (let ((r (first co)) (c (second co)) (a (fourth co)))
      (if (eql 'W (third co))
        (write-memory mem r c a)
        (unless (read-memory mem r c a)
          (format t "ՍԽԱԼ։ Տեստը ձախողվեց (~D, ~D) բջջի վրա։~%" r c))))))

run-algorithm-on ֆունկցիայում քառյակների ֆայլը բեռնվում է որպես Lisp լեզվի ցուցակ read-whole-algorithm ֆունկցիայով։

(defun read-whole-algorithm (src)
  (labels
    ((read-one-command (cs)
       (let ((s (read-line cs nil)))
         (when s
           (read-from-string (concatenate 'string "(" s ")")))))
     (read-all-commands (cs res)
       (let ((c (read-one-command cs)))
         (if (null c)
           res
           (read-all-commands cs (cons c res))))))
  (with-open-file (inp src :direction :input)
    (reverse (read-all-commands inp '())))))

Հիմա մի օրինակ։ Ենթադրենք \(3\times2\) չափի հիշողության \((1,1)\) բջիջը անսարք է և բոլոր կարդալու գործողությունների ժամանակ վերադարձնում է \(0\) արժեքը։

(defvar *m* (create-memory 3 2))
(setf (aref (memory-matrix *m*) 1 1) (make-instance 'cell-co :coval 0))
(run-algorithm-on *m* "test1.alg")

Վերը բերված ալգորիթմը փչացած բջջով մոդելի վրա աշխատեցնելուց հետո ստանում եմ այսպիսի պատասխան․

ՍԽԱԼ։ Տեստը ձախողվեց (1, 1) բջջի վրա։

Որից երևում է, որ ալգորիթմը բջնում է անսարքությունը և սիմուլյատորն էլ անում է իր գործը։