Monday, March 16, 2015

Common Lisp։ Պրոցեդուրային ծրագրավորման մասին

Մի անգամ Կոնֆուցիուսին հարցրեցին.
«Ուսուցիչ, ի՞նչ կարծիքի եք այն մասին, որ Ցզի-Սյուն ծրագրավորում է Lisp լեզվով։»
ՈՒսուցիչը մտածեց և ասաց.
«Ցզին խելացի է։ Նա կարող է գրել Lisp լեզվով։»
Lisp լեզուն մեզ ծանոթ է առավելապես որպես ֆունկցիոնալ ծրագրավորման լեզու։ Բայց ես ուզում եմ այս հոդվածում ներկայացնել Common Lisp լեզվի այն հնարավորությունները, որոնք թույլ են տալիս ծրագրավորել իմպերատիվ ոճով։ Հայտնի է, որ իմպերատիվ եղանակով ցանկացած ալգորիթմ ծրագրավորելու համար պետք են ամենաքիչը չորս ղեկավարող կառուցվածքներ՝ ա) վերագրման հրաման, բ) ճյուղավորման կամ պայմանի հրաման, գ) ցիկլի կամ կրկնման հրաման և դ) հրամանների հաջորդում։ Օրինակ, C++ լեզվում վերագրման հրամանն իրականացվում է «=» սիմվոլով ձևավորվող արտահայտությունների միջոցով, ճյուղավորումները կազմակերպվում են if կամ switch կառուցվածքներով, կրկնությունները կազմակերպվում են for, while և do կառուցվածքներով, իսկ հրամանների հաջորդումը որոշվում է ծրագրի տեքստում նրանց հանդիպելու հերթականությամբ։ Իհարկե, ծրագրերի հարմար կազմակերպման համար պետք է ունենալ ենթածրագրի սահմանման մեխանիզմ, ներածման ու արտածման գործողություններ և այլն։

Սկսենք վերագրման հրամանից։ Common Lisp լեզվում վերագրումները կատարվում են setq հատուկ կառուցվածքով և setf մակրոսով։ Օրինակ, *var-i* դինամիկ փոփոխականին 123 արժեքը կարող ենք վերագրել (setq *var-i* 123) արտահայտությամբ։ Կամ, vec զանգվածի 3-րդ տարրին 3.14 արժեքը կարող ենք վերագրել (setf (aref vec 3) 3.14) արտահայտությամբ։ setq հատուկ կառուցվածքը (ինչպես նաև setf մակրոսը) հնարավորություն ունի կատարել նաև հաջորդական վերագրումներ։ Օրինակ, (setq x 1 y (1+ x) z (* 3 y)) արտահայտությունը համարժեք է (setq x 1), (setq (1+ x)) և (setq z (* 3 y)) արտահայտությունների հաջորդականությանը։ Եթե հարկավոր է կատարել զուգահեռ վերագրումներ, ապա կարող ենք օգտագործել psetq և psetf մակրոսները։ Զուգահեռ վերագրումների դեպքում, բնականաբար, հերթական վերագրման ժամանակ չի կարելի օգտագործել նախորդ վերագրումների արդյունքները։

Ճյուղավորումներ կազմակերպելու համար Common Lisp լեզուն տրմադրում է if հատուկ կառուցվածքը և when, unless, cond մակրոսները։ Ահա նրանց տեսքը.
(if ⟨condition⟩ ⟨then-form⟩ ⟨else-form⟩?)

(when ⟨condition⟩ ⟨form⟩*)

(unless ⟨condition⟩ ⟨form⟩*)

(cond (⟨condition-1⟩ ⟨form-1⟩) (⟨condition-2⟩ ⟨form-2⟩) ...)
Օրինակ, a և b թվերից մեծագույնը c փոփոխականին վերագրելու համար կարող ենք գրել հետևյալ արտահայտություններից որևէ մեկը․
(if (> a b) (setq c a) (setq c b))
կամ
(setq c (if (> a b) a b))
if կառուցվածքը հնարավորություն է տալիս պայմանի ստուգումից հետո կատարել երկու ճյուղերից որևէ մեկը։ Եթե ունենք միայն մեկ ճյուղ, ապա կարող ենք օգտագործել կա՛մ when, կա՛մ unless մակրոսը։ when մակրոսը կատարում է իր մարմինը, երբ պայմանը դրական է, իսկ unless մակրոսը՝ երբ պայմանը բացասական է։ Օրինակ, հետևյալ երկու արտահայտությունների կատարման դեպքում էլ կարտածվի նույն պատասխանը․
(when (> a b) t)
(unless (<= a b) t)
cond մակրոսը կիրառելի է այն ժամանակ, երբ պետք է ընտրություն կատարել երկուսից ավելի ճյուղերի միջև։ Այն իր արգումենտում ստանում է զույգեր, որոնցից առաջին տարրը պայմանն է, իսկ երկրորդը՝ գործողությունը։ Ճյուղավորումն ավարտվում է այն գործողության կատարմամբ, որին համապատասխան պայմանը առաջինն է հաշվարկվում որպես դրական արժեք։ Օրինակ, 0-ից 2 թվերի անուններն արտածելու, իսկ մյուս թվերի համար «more» բառն արտածելու համար կգրենք․
(setq d (parse-integer (read-line)))
(cond ((= d 0) (print "zero"))
      ((= d 1) (print "one"))
      ((= d 2) (print "two"))
      (t (print "more")))
Ցիկլերի կազմակերպման համար Common Lisp լեզուն ունի այնպիսի հնարավորություններ, որ ցանկացած այլ լեզու միայն կարող է նախանձել։ Դիտարկենք dotimes, dolist և loop մակրոսների որոշ հնարավորություններ։ dotimes մակորսը պարզագույն հաշվիչով ցիկլ է։ Օրինակ, 0-ից 100 միջակայքի 20 պատահական թվերի ցուցակ կառուցելու համար կարող ենք գրել․
(setq rnums '())
(dotimes (j 20)
  (push (random 100) rnums))
dolist մակրոսը նման է dotimes մակրոսին, բայց սա իտերացիա է կատարում ցուցակի տարրերով։ Օրինակ, նախորդ օրինակում կառուցված պատահական թվերի ցուցակի տարրերի գումարը կարող ենք հաշվել և արտածել հետևյալ կերպ․
(setq rsum 0)
(dolist (e rnums)
  (incf rsum e))
(print rsum)
loop մակրոսով կարելի է 20 պատահական թվերի ցուցակը կազմել ահա այսպես.
(setq rnums (loop repeat 20 collect (random 100)))
Իսկ rnums ցուցակի տարրերի գումարը կարելի է հաշվել հետևյալ արտահայտությամբ.
(print (loop for e in rnums summing e))
Պրոցեդուրային լեզուների while ցիկլը նույնպես կարելի է գրել loop մակրոսի օգնությամբ։ Օրինակ, 1-ից 20 թվերը հակառակ հաջորդականությամբ տպելու համար կարող ենք գրել.
(setq a 20)
(loop while (> a 0)
      do (print a)
         (incf a -1))
Հրամանների հաջորդման համար Common Lisp լեզվում առկա են progn հատուկ կառուցվածքը և prog1, prog2 մակրոսները։ progn կառուցվածքը հերթականորեն հաշվարկում է իր արգումենտները և վերադարձնում է դրանցից վերջինի արժեքը։ prog1 և prog2 մակրոսները համապատասխանաբար վերադարձնում են առաջին և երկրորդ արգումենտների արժեքները։ Սրանք ինչ-որ իմաստով նման են պրոցեդուրային լեզուներում բլոկների կազմակերպման մեխանիզզմներին (ինչպես օրինակ Pascal լեզվի begin-end բլոկները)։ Լեզվի շատ ֆունկցիաներ ու մակրոսներ ունեն ոչ բացահայտ progn, այսինքն կարելի է պարզապես իրար հետևից գրել արտահայտությունները՝ առանց progn կառուցվածքի օգտագործման։ Օրինակ, while և unless մակրոսների կիրառման դեպքում progn պետք չէ, իսկ if հատուկ կառուցվածքի մարմնում պետք է։

Գլոբալ ֆունկցիաները Common Lisp լեզվում սահմանվում են defun մակրոսով։ Այն ստանում է սահմանվող ֆունկցիայի անունը, պարամետրերի ցուցակը և ֆունկցիայի մարմինը։ Օրինակ, հետևյալ ֆունկցիան իրար է գումարում արգումենտում ստացած երկու թվերը․
(defun add-two-num (a b)
  (+ a b))
Ֆունկցիայի վերադարձրած արժեք է համարվում նրա մարմնում հաշվարկված վերջին արտահայտության արժեքը։ Եվ վերջապես որպես օրինակ դիտարկենք տրված վեկտորի ամենամեծ ու ամենափոքր տարրը որոշող ալգորիթմը։ C++ լեզվով այն կարող ենք գրել հետևյալ կերպ․
template
std::tuple min_and_max( std::vector vec )
{
  T mn(vec.at(0));
  T mx(vec.at(0));
  for( auto e : vec ) {
    if( mn > e ) mn = e;
    if( mx < e ) mx = e;
  }
  return std::make_tuple(mn, mx);
}
Սա մի ֆունկցիա է, որը արգումենտում ստանում է վեկտոր, և վերադարձնում է երկու թիվ՝ վեկտորի տարրերից ամենամեծն ու ամենափոքրը։ Հիմա տեսնենք, թե Common Lisp լեզվով ինչպես կարելի է ծրագրավորել այս նույն ալգորիթմը։ Շաբլոնների կարիքը չունենք, որովհետև Lisp-ը տիպերի դինամիկ ստուգմամբ լեզու է (թեև հայտարարությունների օգնությամբ կարող ենք կոմպիլյատորին հուշել փոփոխականի տիպը)։ min-and-max ֆունկցիան, տիպիկ պրոցեդուրային ոճով, կունենա մոտավորապես հետևյալ տեսքը․
(defun min-and-max (vec)
  (declare (type array vec))
  (let ((mn (aref vec 0))
        (mx (aref vec 1)))
    (loop for e across vec
     do
       (if (> mn e) (setf mn e))
       (if (< mx e) (setf mx e)))
    (values mn mx)))
Բայց․․․ բայց բարեբախտաբար Lisp լեզուն նախատեսված չէ այս ոճի կոպիտ ծրագրեր գրելու համար։ (Ես պատկերացնում եմ, որ եթե Lisp-ինտերպրետատորը կարողանար ծիծանել, ապա այն ինչպիսի քրքջոց կբարձրացներ այս ֆունկցիան կարդալու ժամանակ։)