Thursday, December 24, 2015

Ի՞նչ կարդալ ծրագրավորման լեզուների իրականացման մասին

Վերջերս ավելի ու ավելի հաճախ եմ լսում այն հարցը, թե ի՛նչ կարդալ կոմպիլյատորների մասին։ Ծրագրավորման լեզուների նախագծման ու իրականացման մասին գրականության պակաս, իհարկե, չկա։ Սա ինֆորմատիկայի և ծրագրավորման այն ոլորտն է, որը թե՛ գիտական, թե՛ գործնական տեսակետից ակտիվորեն ուսումնասիրվել և ուսումնասիրվում է, հրապարակվում են նոր հետազոտություններ, գրվում են նոր գրքեր։ Այս գրառման մեջ ես ուզում եմ առանաձնացնել մի քանի հանրահայտ աշխատանքներ, որոնք իմ գրադարանում զտվել են վերջին 10 տարիների փնտրտունքների արդյունքում, և որոնք ես օգտագործում եմ թե՛ իմ աշխատանքում, թե՛ մասնավոր հետաքրքրություններում և թե՛ դասավանդման ընթացքում։ (Բնականաբար ոչ մի խոսք չի կարող լինել հայերեն նյութերի մասին․ գրքերը որոնք մատչելի են թղթային կամ էլեկտրական տարբերակով մեծամասամբ անգլերենով կամ ռուսերենով են)։

Բայց ուզում եմ նաև վերաձևակերպել վերը բերված հարցը՝ դարձնելով այն ավելի տարողունակ (միգուցե նաև ավելի ճշգրիտ ու հետաքրքիր)։ Եվ այսպես․ «ի՞նչ կարդալ ծրագրավորման լեզուների և դրանց իրականացման մասին»։

Սկսելու համար, իմ կարծիքով, լավագույնը Jack Crenshaw֊ի «Let's Build a Compiler» հոդվածների շարքն է։ Սա մի հրաշալի ներածություն է կոմպիլյատորներ կառուցելու գործնական կողմի վերաբերյալ։ Հեղինակը, սկսելով պարզ կառուցվածքներից, ստեղծում է «իսկական» կոմպիլյատոր՝ հընթացս մանրամասն մեկնաբանելով իր ամեն մի քայլը։ (Կա նաև ռուսերեն թարգմանությունը․ Д. Креншоу, Пишем компилятор։)

Ծավալով փոքր, բայց տաղադավոր գրված գիրք է Niklaus Wirth֊ի «Compiler Construction»-ը։ Հանրահայտ գիտնականն ու մանկավարժը կարողացել է մոտ 200 էջերի մեջ տեղավորել կոմպիլյատորի կառուցման բոլոր հիմնական սկզբունքներն ու քայլերը և ընթերցողին մատուցել անփոխարինելի մի դասագիրք։ Գրքում Oberon ծրագրավորման լեզվով իրականացվում է նույն Oberon֊ի մի ենթաբազմության՝ Oberon-0֊ի կոմպիլյատորը, որը կոդ է գեներացվում գրքի իններորդ գլխու նկարագրված RISC վիրտուալ մեքենայի համար։ (Գիրքը մատչելի է անգլերենով, ռուսերենով և գերմաներենով։)

Andrew Appel֊ի «Modern Compiler Implementation in C» գիրքը նույնպես ուզում եմ նշել որպես մի հաջող ու հետաքրքիր աշխատանք։ Այն բաժանված է երկու մասերի. առաջինը ներկայացնում է կոմպիլյատորի հիմնական բաղադրիչների իրականացումը, երկրորդում լրացուցիչ թեմանաեր են (աղբի հավաքում, պոլիմորֆիկ տիպեր և այլն)։ Գիրքը հրատարակվել է երեք լեզուների համար՝ C, Java և ML։

Մի քիչ ավելի կոմպակտ աշխատանք է Torben Mogensen֊ի «Introduction to Compiler Design» գիրքը։ Սա նույնպես հարմար է որպես դասագիրք օգտագործելու համար։

Արժե ծանոթանալ նաև Terrence Pratt֊ի և Marvin Zelkovitz-ի հեղինակած «Programming Languages: Design and Implementation» արդեն դասական դարձած գիրքը, որում ներկայացված են ծրագրավորման լեզուների

Ծրագրավորման լեզուների իրականացմանը նվիրված գրքերի մասին խոսելիս, իհարկե, պետք է անպայման նշել Alfred Aho֊ի, Monica Lam֊ի, Ravi Sethi֊ի և Jeffrey Ullman֊ի հռչակավոր «Compilers: Principles, Techniques, & Tool» դասագիրքը։ Այն ընդգրկում է կոմպիլյատորների իրականացմանը վերաբերող բոլոր թեմաները՝ տեսական ու պրակտիկ հարուստ նյութով։ Իմ կարծիքով, սա այն գիրքն է, որը պետք է ինչ֊որ մի պահից դառնա ծրագրավորման լեզուներն ուսումնասիրող մասնագետի սեղանի գիրքը։

Թերևս այսքանն այն մի քանի կարևորագույն գրքերի մասին, որոնցից, իմ կարծիքով, կարելի է և պետք է սկսել ծրագրավորման լեզուների իրականացման հետ շփումը։ Բնականաբար ցանկը կարելի է շարունակել (նույնիսկ կարելի է ճշգրտումներ անել՝ այս կամ այն գրքը մեկ ուրիշով փոխարինելով), բայց սա այն է, ինչ ես կարողացա այս պահին ամփոփել։ Իմ էլեկտրական գրադարանում այս պահին կան թեմային նվիրված մոտ 200 գիրք, դրանցից յուրաքանչյուրն իր առանձնահատկությունն ունի և արժանի է ուշադրության։
* * *

Իսկ ի՞նչ կարդալ ծրագրավորման լեզուների իրականացման մասին՝ նրանց աշխատանքի սկզբունքներին ծանոթանալու համար, կոմպիլյատորները և ինտերպրետատորները որպես գործիք ավելի լավ օգտագործելու համար։ Այս թեմայով ինձ դուր է գալիս Robert Sebesta֊ի «Concepts of Programming Languages» գիրքը (ծանոթ պետք է լինի բոլոր ուսանողներին), որում մանրամասնորեն վերլուծված են բազմաթիվ ծրագրավորման լեզուների զարգացումը, կիրառության ոլորտներն ու առանձնահատկությունները, ինչպես նաև բերված են հետաքրքի համեմատականներ։ Հետո կարելի է կարդալ (կամ աչքի անցկացնել) Alice Fischer֊ի և Frances Grodzinsky֊ի «The Anatomy of Programming Languages» գիրքը։ Այստեղ էլ քննարկվում են տարբեր լեզուների ներքին կառուցվածքը, տիպերի համակարգերի և ծրագրավորման պարադիգմների համեմատությունները։ Վերջերս հայտնաբերել եմ, բայց դեռ խորությամբ չեմ ծանոթացել Daniel Friedman֊ի և Mitchell Wand֊ի «Essentials of Programming Languages» գրքին (թեմաներն ու բերված օրինակները բավականին հետաքրքիր են)։

Saturday, December 12, 2015

Միակապ ցուցակի շրջելը ռեուրսիվ եղանակով

Մի քանի օր առաջ Լիլիթն ինձ առաջարկեց գրել միակապ ցուցակը շրջելու ֆունկցիան՝ օգտագործելով ռեկուրսիվ ալգորիթմ։ Առաջին բանը, որ միտքս եկավ՝ թե ինչպես կարելի է դա ան մի այնպիսի լեզվով, որտեղ ցուցակը ներդրված տիպ է, և արդեն առկա են ցուցակի հետ գործողություններ կատարող ֆունկցիաները։ Օրինակ, Scheme լեզվով գրված պրոցեդուրան կարող է ունենալ այսպիսի տեսք․

(define (reverse-it li)
    (define (reverse-it-rec l r)
        (if (null? l)
            r
            (reverse-it-rec (cdr l) (cons (car l) r))))
    (reverse-it-rec li '()))

Այստեղ reverse-it պրոցեդուրայի մարմնում սահմանված է վերջին կանչի ռեկուրսիա (tail recursive) ունեցող reverse-it-rec պրոցոդուրան, որում էլ հենց կտարվում է տրված ցուցակի շրջելը։ reverse-it-rec֊ն ուն երկու պարամետր՝ ցուցակի չշրջված մասը և արդեն շրջված մասը։ Պարզ է, որ reverse-it֊ում նրան կանչելիս առաջին արգումենտը պետք է լինի շրջվելիք ցուցակը, իսկ երկրորդը՝ դարարկ ցուցակ։ Եթե l֊ը դատարկ է, ապա համարվում է, որ r-ը արդեն շրջված ցուցակն է, և այն վերադարձվում է որպես արդյունք։ Հակառակ դեպքում l֊ի առաջին տարրը կցվում է r-ի սկզբից, և reverse-it-rec ի ռեկուրսիվ կանչը կիրառվում է l֊ի պոչի և այդ նոր r֊ի նկատմամբ։

* * *

Բայց Լիլիթն ուզում էր, որ ես սա գրեմ C++ լեզվով, որից ես շատ քիչ բան եմ հասկանում, և այդ պատճառով էլ որոշեցի գրել C լեզվով։ Սակայն այս դեպքում իրավիճակը բոլորովին այլ է․ C լեզվում չկան ո՛չ ներդրված ցուցակը, ո՛չ էլ դրա հետ աշխատող ֆունկցիաները։ Ես պետք է սկսեմ սկզբից՝ սահմանելով նախ՝ ցուցակը, ապա՝ այն շրջող ֆունկցիան։

Եվ այսպես, սահմանում եմ միակապ ցուցակի մեկ հանգույցը ներկայացնող node ստրուկտուրան։ Այն ունի երկու երկու դաշտ՝ մեկը ինֆորմացիայի համար, մյուսը՝ հաջորդ հանգույցին կապելու։ Պարզության համար ինֆորմացիայի տիպն ընտրել եմ double։

strcut node {
    double data;
    struct node* next;
};

Հանգույցներ կառուցելու համար ինձ պետ է նաև create_node ֆունկցիան, այն ստանում է double թիվ և վերադարձնում է այդ թիվը պարունակող նոր ստեղծված հանգույցի ցուցիչը։

struct node* create_node( double d )
{
    struct node res = malloc(sizeof(struct node));
    res->data = d; res->next = NULL;
    return res;
}

Աշխատանիքի միջանկյալ ու վերջնական արդյունքները տեսնելու համար պետք է գալու նաև ցուցակն արտածող print_list ֆունկցիան։ Դա էլ սահմանեմ․

void print_list_rec( struct node* list )
{
    if( list == NULL ) return;
    printf("%lf ", list->data);
    print_list_rec( list->next );
}

void print_list( struct node* list )
{
    printf("{ ");
    print_list_rec( list );
    printf("}\n");
}

Հիմա ամենահետաքրքիր պահն է։ Ես հանմանում եմ reverse_it և reverse_it_rec ֆունկցիաները՝ փորձելով վերարտադրել վերը բերված Scheme պրոցեդուրայի վարքը։

struct node* reverse_it_rec( struct node* l, struct node* r )
{
    if( l == NULL )  /* երբ ցուցակը դատարկ է */
        return r;    /* արդյունքը կապված է r ցուցիչին */

    struct node* h = l;  /* h֊ը ցուցակի գլուխն է */
    l = l->next; ․       /* l֊ը հիմա ցուցակի պոչն է, դեռ չշրջված */
    հ->next = r;         /* սկզբնական l֊ի առաջին տարրը կապել r֊ին */
    return reverse_it_rec( l, h );
}

Դե իսկ reverse_it ֆունկցաին պարզապես կանչելու է reverse_it_rec֊ը՝ առաջին արգումենտում տալով շրջվելիք ցուցակը, իսկ երկրորդում՝ NULL։

struct node* revers_it( struct node* list )
{
    return reverse_it_rec( list, NULL );
}

Այսքանը։ Հիմա կարող եմ վերը ներկայացված կոդը գրել ֆայլի մեջ, կցել stdio.h և stdlib.h ֆայլերը, օրինակ պատրաստել main ֆունկցիայում և տեսնել, թե ինչպես է աշխատում իմ գրած ֆունկցիան։

Օրինակը շատ պարզ է․ կառուցում եմ ցուցակի հինգ հանգույցներ՝ օգտագործելով create_node ֆունկցիան, ապա դրանք իրար եմ կապում next ցուցիչի օգնությամբ։

struct node* n0 = create_node(1);
struct node* n1 = create_node(2); n0->next = n1;
struct node* n2 = create_node(3); n1->next = n2;
struct node* n3 = create_node(4); n2->next = n3;
struct node* n4 = create_node(5); n3->next = n4;

Ցուցակը տպում եմ, որպեսզի տեսնեմ տարրերի սկզբնական հաջորդականությունը։ Այնուհետև այն շրջում եմ reverse_it ֆուկցիայի օգնությամբ, և նորից տպում եմ ստացված ցուցակը։

print_list(n0);
struct node* rl = reverse_list(n0);
print_list(rl);

Ահա արդյունքը․

{ 1.000000 2.000000 3.000000 4.000000 5.000000 }
{ 5.000000 4.000000 3.000000 2.000000 1.000000 }

Տեսնելու համար, թե ինչ տեսք ունեն l և r ցուցակները ռեկուրսիայի ամեն մի կանչի ժամանակ, կարելի է reverse_it_rec ֆունկցիայի սկզբում ավելացնել print_list(l) և print_list(r) արտահայտությունները։

Friday, October 2, 2015

Ստրուկտուրաներ TCL լեզվի համար

Կուրսային աշխատանքի նախագիծ։

Այս գրառման մեջ ես ուզում եմ TCL լեզվի օրինակով ցույց տալ, թե ինչպես կարելի է ընդլայնել ծրագրավորվող ծրագրավորման լեզուն, և այն ընդլայնումն էլ ուզում եմ ցույց տալ ստրուկտուրաների օրինակով։ Գաղափարները ես փոխառել եմ Common Lisp լեզվից։

Գիտեմ (իհարկե, որոշ վերապահումներով), որ TCL լեզվում բացակայում են ստրուկտուրաների (գրառումների) հետ աշխատելու գործիքները, և TLC լեզվում առկա են ցուցակ և տող տիպերը և դրանց հետ աշխատելու ֆունկցիաները։ Ես պետք է «ստրուկտուրա» (struct, record) և «նմուշ» (instance) գաղափարներն արտապատկերեմ «ցուցակ» (list), միգուցե նաև «տող» (string) գաղափարներին։

Եթե, օրինակ, արդեն սահմանել եմ person (անձ) ստրուկտուրան, ապա 42 տարեկան Վչոյին նկարագրող նմուշը կարող է ունենալ հետևյալ տեսքը։

{person name Վչո age 42}

Այստեղ երևում է, որ person ստրուկտուրայի նմուշը ներկայացված է մի ցուցակով, որի առաջին տարրը ստրուկտուրայի անունն է, իսկ հաջորդ տարրերը կազմում են սլոտ֊արժեք զույգերի հաջորդականություն։ Նմուշի այսպիսի ներկայացման դեպքում, կարծում եմ, արդեն դժվար չէ սահմանել այն գործիքները, որոնցով աշխատելու եմ ստրուկտուրաների ու դրանց նմուշների հետ։

Քանի որ TCL լեզվում ծրագրի կառուցման բլոկը (շինանյութը) պրոցեդուրան է, ապա ստրուկտուրաների և դրանց նմուշների հետ աշխատելու համար պետք է ունենալ ա) ստրուկտուրա սահմանող, բ) ստրուկտուրայի նմուշ ստեղծող, գ) ստրուկտուրայի դաշտերի (սլոտների) արժեքներ կարդացող և փոփոխող պրոցեդուրաներ։

Օգտագործելով person ստրուկտուրայի օրինակը, սկսեմ սահմանել այդ թվարկված պրոցեդուրաները։ Բայց, առաջ անցնելով ենթադրեմ, թե արդեն սահմանված է struct պրոցեդուրան, որը կատարման միջավայրում սահմանում է նոր ստրուկտուրա։ Դրա օգնությամբ սահմանեմ person ստրուկտուրան։

struct person { name gender age }

Թող create_person պրոցեդուրան վերադարձնում է person ստրուկտուրայի չարժեքավորված նմուշ (կոնստրուկտոր պրոցեդուրա է)։

proc create_person {} {
    list person name {} age {}
}

Վարժություն 1։ Սահմանել create_person պրոցեդուրայի մի այլ տարբերակ, որն արգումենտում ստանում է սլոտների սկզբնական արժեքները և ստեղծում է person ստրուկտուրայի արժեքավորված նմուշ։

Այնուհետև, թող person_name պրոցեդուրան արգումենտում ստանում է person նմուշը և վերադարձնում է դրա name սլոտի արժեքը։

proc person_name { inst } {
    set ps [lsearch $inst name]
    lindex $inst [expr {$ps + 1}]
}

person_name֊ին ստիմետրիկ սահմանեմ նաև person_name_set պրոցեդուրան, որը նմուշի name սլոտին վերագրում է նոր արժեք։

proc person_name_set { inst val } {
 upvar $inst obj
 set ps [lsearch $obj name]
 lset obj [expr {$ps + 1}] $val
}

Վարժություն 2։ Ձևափոխել person_name և person_name_set պրոցեդուրաներն այնպես, որ այն ստուգի, թե արդյո՞ք inst֊ը person-ի նմուշ է։

Վարժություն 3։ Սահմանել նաև age սլոտի արժեքը գրող և կարդացող պրոցեդուրաները։

Հիմա վերադառնամ բուն ստրուկտուրան սահմանող struct պրոցեդուրային։ Արդեն պարզ է, որ s0, s1,... sk սլոտներն ունեցող S ստրուկտուրան սահմանել, նշանակում է կատարման միջավայր ներմուծել create_S կոնստրուկտորը, իսկ ամեն մի si սլոտի համար՝ S_si և S_si_set անունով պրոցեդուրաները։ Այլ կերպ ասած, ստրուկտուրաներ սահմանող struct պրոցեդուրան ամեն մի նոր ստրուկտուրայի համար պետք է սահմանի դրա կոնստրուկտոր և սլոտներին դիմող պրոցեեդուրաները, ինչպես նաև նմուշի տիպը հաստատող պրեդիկատ պրոցեդուրան։ Ահա այն․

proc struct { name slots } {
 set slpatt [list $name]
 foreach sl $slots {
  uplevel "proc ${name}_${sl} \{ inst \} \{
          set ps \[lsearch \$inst $sl]
          lindex \$inst \[expr \{\$ps + 1\}\] \}"

  uplevel "proc ${name}_${sl}_set \{ inst val \} \{
          upvar \$inst obj
          set ps \[lsearch \$obj $sl\]
          lset obj \[expr \{\$ps + 1\}\] \$val \}"

  lappend slpatt $sl {}
 }

 uplevel "proc create_$name \{\} \{ list $slpatt \}"

 uplevel "proc is_$name \{ inst \} \{
      string equal $name \[lindex \$inst 0 0\] \}"
}

Չնայած նրա մի քիչ խճճված տեսքին, տրամաբանությունը բավականին պարզ է։ Այն սահմանում է վերը պահանջված պրոցեդուրաները։

Վարժություն 4։ Ստրուկտուրաների սահմանման, դրանց նմուշների ու սլոտների հետ աշխատող պրոցեդուրաները լրացնել (ընդլայնել) սխալների ստուգման մեխանիզմով։

Saturday, September 12, 2015

Ծրագրավորման լեզուն ընդլայնելու մասին

Վերջերս ես հանդիպեցի թե ինչպես են C++ լեզվում ներմուծել հայերեն ծառայողական բառեր։ Դա արվել էր, բնականաբար, նախապրոցեսորի (preprocessor) օգնությամբ։ Պարզապես ամեն մի բառի համար սահմանվել էր նրա համարժեք հայերեն տարբերակը, որն էլ նախամշակման ժամանակ փոխարինվում էր լեզվի իսկական ծառայողական բառով։ Դա ուներ մոտավորապես ուներ այսպիսի տեսք․

#define եթե if 
#define այլապես else 
#define մինչ while 
#define վերադարձնել return 
#define ամբողջ int

Եվ այս սահմանումներով, օրինակ, էվկլիդեսի ալգորիթմը կարելի է գրառել հետևյալ տեսքով․

ամբողջ euclid( ամբողջ n, ամբողջ m ) {
    մինչ( n != m ) {
        եթե( n > m )
            n %= m;
        այլապես
            m %= n;
    }
    վերադարձնել n + m;
}

Երբ հայերեն ծառայողական բառերի սահմանումներն ու դրանց օգտագործմամբ գրված ծրագիրը գրենք *.cpp ֆայլում, և clang++ կոմպիլյատորի նախապրոցեսորին խնդրենք մշակել այդ ֆայլը․

$ clang -E ex0.cpp

Ապա կստանանք «մաքուր» C++ լեզվով գրված կոդ։

int euclid( int n, int m ) {
    while( n != m ) {
        if( n > m )
            n %= m;
         else
            m %= n;
    }
    return n + m;
}

Պարզ է, որ եթե ուզում ենք ծրագրավորել հայերեն բառերով, ապա C++ լեզուն ավելի լավ տարբերակ չի առաջարկում․ կոմպիլյացիայից առաջ ծրագրի տեքստում փոփոխություններ կատարելու միակ հնարավոր եղանակը նախապրոցեսորի օգտագործումն է։ Պարզ է նաև, որ չենք կարող լեզվում նոր ղեկավարող կառուցվածքներ ավելացնել։ Օրինակ, ինչպե՞ս ավելացնել repeat տիպի կրկնման գործողություն։

repeat( 10 ) {
    std::cout << "Ողջո՜ւյն։\n";
}
* * *

Լրիվ այլ պատկեր է այն լեզուներում, որոնց ընդունված է ասել «ծրագրավորվող ծրագրավորման լեզուներ»։ Այդ դասի վառ ներկայացուցիչներ են Lisp ընտանիքի լեզուները՝ մակրոսների սահմանման իրենց հնարավորություններով։ «Ծրագրավորվող» լինելու հատկությամբ է օժտված նաև Tcl լեզուն, որում վերը բերված repeat կառուցվածքը սահմանելը ամենևին էլ բարդ բան չէ։ Ահա այն․

proc repeat { num body } {
    set result {}
    while { $num != 0 } {
        incr num -1
        set result [uplevel $body]
    }
    return $result
}

Նույնիսկ սրա հայերեն տարբերակի սահմանումն է բավականին հետաքրքիր։

proc կրկնել { count անգամ body } {
    if { ${անգամ} ne {անգամ} } then {
        error "Syntax error."
    }
 
    set result {}
    while { $count != 0 } {
        incr count -1
        set result [uplevel $body]
    }
    return $result
}

Այստեղ սահմանված է կրկնել անունով պրոցեդուրան, որը ունի երեք պարամետր։ Պարամետրերից առաջինը կրկնությունների քանակն է, երկրորդը կատարում է անգամ ծառայողական բառի դերը, իսկ երրորդը կրկնման հրամանի մարմինն է։ կրկնել պրոցեդուրայի մարմնում նախ ստուգում եմ, որ երկրորդ պարամետրի արժեքն անպայման լինի անգամ տողը։ Ահա նաև կիրառությունը․

կրկնել 5 անգամ {
    puts Hello!
}

Բայց ինչպե՞ս է սա աշխատում։ Չէ՞ որ Tcl լեզվի proc հրամանը պարզապես սահմանում է նոր ֆունկցիա, և, բոլորս էլ լավ գիտենք, որ ֆունկցիայի կանչի ժամանակ արգումենտները հաշվարկվում են ֆունկցիային փոխանցելուց առաջ։ Եվ, տվյալ դեպքում, «{ puts {Ողջո՜ւյն։} }» արգումենտի արժեքը պետք է հաշվարկվեր և պետք է մի անգամ արտածվեր «Ողջո՜ւյն։» տեքստը։

Բացատրությունը Tcl լեզվի միակ տիպի՝ տողի հաշվարկման կանոնների մեջ է։ Եթե տողը պարփակված է { և } ձևավոր փակագծերում, ապա այն փոխանցվում է այնպես, ինչպես կա (as-is), ոչ մի հաշվարկ չի կատարվում, ոչ մի ձևափոխություն չի կատարվում։ { և } փակագծերը տողը «պաշտպանում» են հաշվարկումից։ Եվ այդ պաշտպանությունը հնարավորություն է տալիս տողը դիտարկել որպես «ղեկավարող կառուցվածքի» բլոկ։

Օգտագործելով Tcl լեզվում պրոցեդուրաներ սահմանելու proc հրամանը և կոդի բլոկը ստեկի մեկ այլ կադրում հաշվարկելու uplevel հրամանը, կարելի է լեզուն ընդլայնել (համալրել) հայերեն ծառայողական բառեր ունեցող ղեկավարող կառուցվածքներով։ Եվ քանի որ նոր կառուցվածքները սահմանվելու են որպես պրոցեդուրաներ, ապա դա հնարավորություն է տալիս կատարել շարահյուսական և իմաստաբանական ստուգումներ։ Դրա օրինակ է վերը սահմանված կրկնել պրոցեդուրայում անգամ բառի առկայության ստուգումը։

* * *

Լեզուն ընդլայնելու (ասում են նաև՝ լեզվի մեջ նոր լեզու սահմանելու) էլ ավելի լայն ու հետաքրքիր հնարավորություններ են ընձեռնում Lisp ընտանիքի Common Lisp և Scheme լեզուները։ Բայց, ինչպես ասում էր Ֆ․ Դոստոևսկին, դա արդեն ուրիշ պատմության նյութ է։

Sunday, August 16, 2015

Ծրագրերի սկզբնային տեքստերի գեղեցկության մասին

Կարելի՞ է արդյոք կոմպյուտերային ծրագրի կոդի մասին խոսելիս ասել, որ այն գեղեցիկ է։ Արդյո՞ք ծրագրի տեքստը կարելի է բնութագրել գեղագիտական հատկանիշներով։ Այս հարցին ես առաջին անգամ առնչվեցի, որբ բակալավրիատում սովորելու առաջին կուրսում, ծրագրավորման գործնական պարապմունքի ժամին դասախոսը՝ Արմեն Անդրեասյանը, ցույց տվեց գրատախտակին գրված ծրագիրը ու ասաց. «Գեղեցիկ է, չէ՞»։ Ինչքան հիշում եմ, թեև հնարավոր է, որ սխալվեմ, այդ ծրագիրը Էվկլիդեսի ալգորիթմն էր՝ գրված C++ լեզվով.

int gcd( int a, int b )
{
  while( a != b )
    if( a > b )
      a -= b;
    else
      b -= a;
  return a;
}

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

Էվկլիդեսի ալգորիթմին վերադառնալով ուզում եմ ասել, որ այն իսկապես գեղեցիկե։ Առավել գեղեցիկ է նրա ռեկուրսիվ իրականացումը, որ ահա գրել եմ Oberon լեզվով․

PROCEDURE Gcd( u, v : INTEGER ) : INTEGER;
VAR
  re : INTEGER;
BEGIN
  IF v = 0 THEN
    re := u
  ELSE
    re := Gcd(v, u MOD v)
  END;
RETURN re END Gcd;

Չէ, իսկապես գեղեցիկ է։ Այս ալգորիթմի համար նույնիսկ կարևոր չէ, թե այն ինչ լեզվով է գրված։ Նրա հիմքում գեղեցիկ մաթեմատիկական միտքն է, այն գեղեցիկ է ստացվելու, երևի թե ցանկացած ծրագրավորման լեզվով գրելիս։ Ճիշտ ինչպես Շիլլերի տողերը, որ միատեսակ գեղեցիկ են ինձ ծանոթ բոլոր լեզուներով։ Բնագիրը.

    Ihr Matten lebt wohl,
    Ihr sonnigen Weiden!
    Der Senn muss scheiden,
    Der Sommer ist hin.
Wir fahren zu Berg, wir kommen wieder,
Wenn der Kuckuck ruft, wenn erwachen die Lieder,
Wenn mit Blumen die Erde sich kleidet neu,
Wenn die Brünnlein fliessen im lieblichen Mai
    Ihr Matten lebt wohl,
    Ihr sonnigen Weiden!
    Der Senne muss scheiden,
    Der Sommer ist hin.

Հայերեն՝ Հ. Թումանյանի թարգմանությամբ.

Մնաք բարով, դո՛ւք, արոտնե՛ր սիրուն,
Ամառն անց կացավ, հոտն իջնում է տուն։

Մենք ետ կըգանք ձեզ նորեկ գարունքին,
Երբ զարթնեն ուրախ երգերը կըրկին,
Երբ որ սարերը զուգվեն կանաչով,
Երբ որ ջըրերը վազեն կարկաչով։

Մնաք բարով, դո՛ւք, արոտնե՛ր սիրուն,
Ամառն անց կացավ, հոտն իջնում է տուն։ 

Ռուսերեն՝ Ն. Սլավյատինսկու թարգմանությամբ.

    Прощайте, луга,
    Багряные зори!
    Разлука нам — горе.
    Ах, лето прошло!
Пора нам в долины... Увидимся снова,
Когда все очнется от сна ледяного
И голос кукушки в лесу зазвучит,
Цветы запестреют, родник зажурчит.
    Прощайте, луга,
    Багряные зори!
    Разлука нам — горе.
    Ах, лето прошло!

Անգլերեն՝ Թ. Մարտինի թարգմանությամբ.

    Farewell, ye green meadows,
    Farewell, sunny shore,
    The herdsman must leave you,
    The summer is o'er.
We go to the hills, but you'll see us again,
When the cuckoo is calling, and wood-notes are gay,
When flowerets are blooming in dingle and plain,
And the brooks sparkle up in the sunshine of May.
    Farewell, ye green meadows,
    Farewell, sunny shore,
    The herdsman must leave you,
    The summer is o'er.

Հիմա արդեն, ծրագրային կոդերի հետ աշխատանքի ավելի քան տաս տարիների փորձն ամփոփելով, կարող եմ ինքս ինձ համար պնդել, որ այո՛, կոմպյուտերային ծրագրի տեքստը (սկզբնային տեքստ, source code) նույնպես կարող է գեղեցիկ լինել։ Ավելին, հուսալի ու արդյունավետ կարող են աշխատել միայն այնպիսի ծրագրերը, որոնք գեղեցիկ տեքստ ունեն։ Համարյա ինչպես ավիացիայում. ասում են, որ լավ է թռչում միայն գեղեցիկ ինքնաթիռը։ Օրինակ, МиГ-29 կործանիչը։ Ես կարող եմ ժամերով նայել այս ինքնաթիռի թռիչքին։ Այն թռչում է ինչպես բալետի պարուհին է պարում բեմի վրա, ինչպես գեղասահորդը սահում է սառույցին։ Եվ երբ նայում եմ այդ ինքնաթիռի գծապատկերին, տեսնում եմ նույն պարուհուն կամ գեղասահորդին:

Նույնպիսի համեմատություն կարող եմ անել Դ. Կնուտի (D. Knuth) TeX և METAFONT ծրագրերի համար։ Այդ երկու ծրագրերն էլ գրված են Literate Programming մեթոդով. կարծես գեղարվեստական ստեղծագործություն լինեն։ Դե, իսկ ո՞ւմ չէ հայտնի TeX-ով պատրաստված տեքստերի և METAFONT-ով պատրաստված տպատառերի գեղեցկությունը։

Կան նաև տգեղ ծրագրեր։ Բառացիորեն վերջերս իմ աշխատանքում պետք եղավ C++ լեզվով գրել ծրագրի մի հատված, որտեղ օբյեկտները բնութագրող տողերի զույգերից պետք էր կառուցել օբյեկտների բառարան (map): Տողերի զույգի առաջին տարրը բառարանի բանալին է, իսկ երկրորդ տարրից պետք է կառուցել բանալուն համապատասխանեցված արժեքը։ Ծրագրի բնույթն այնպիսին է, որ տողերի զույգերը ժամանակի ընթացքում ավելանալու են։ Սկզբում, երբ զույգերը դեռ քիչ էին, գրել էի մի այսպիսի տեքստ (պարզեցված տարբերակով, իհարկե).

std::vector keys;
std::map dict;
keys.push_back("k0");
dict["k0"] = new Descriptor("v0");
keys.push_back("k1");
dict["k1"] = new Descriptor("v1");
keys.push_back("k2");
dict["k2"] = new Descriptor("v2");

Չնայած, որ բնութագրող տողերի փոքր քանակի համար սա ընդունելի է, այնուամենայնիվ, ես համարում եմ, որ այս կոդը տգեղ է։ Հենց թեկուզ այն պատճառով, որ տվյալները «կորել» են լեզվի արտահայտությունների մեջ։

Հետո, երբ բնութագրիչների քանակներն ավելանան, ես keys և dict կոնտեյներները լրացնելու համար կոդը ձևափոխեցի հետևյալ տեսքին.

using pair_t = std::pair;
std::list cpairs = {
    { "k0", "v0" },
    { "k1", "v1" },
    { "k2", "v2" },
    // ....
    { "k12", "v12" }
};
auto maker_f = [&]( pair_t e ) { 
                   keys.push_back(e.first);
                   dict[e.first] = new descriptor(e.second);
               };
std::vector keys;
std::map dict;
std::for_each( cpairs.begin(), cpairs.end(), maker_f );

Մի քիչ երկար է, բայց այս դեպքում, եթե նոր տվյալներ ավելացնեմ, ապա դրանք ավելացնելու եմ միայն cpairs ցուցակում, իսկ տվյալների մշակման մասն արդեն անփոփոխ է մնալու։ Պետք է նշել, որ այս գեղեցիկ տեքստը ես ստացել եմ C++11 ստանդարտում ավելացված հնարավորությունների շնորհիվ։ Եթե ես այս կոդը գրեի, C++98 ստանդարտի հնարավորություններով, ապա ստանալու էի մի կոդ, որին ես գեղեցիկ ասել չեմ կարող.

typedef std::pair pair_t;
std::list cpairs;
cpairs.push_back( std::make_pair( "k0", "v0" ) );
cpairs.push_back( std::make_pair( "k1", "v1" ) );
cpairs.push_back( std::make_pair( "k2", "v2" ) );
// ....
cpairs.push_back( std::make_pair( "k12", "v12" ) );

std::vector names;
std::map dict;
for( std::list::iterator it = cpairs.begin(); it != cpairs.end(); ++it ) {
    names.push_back( it->first );
    dict[it->first] = new Descriptor(it->second);
}

Ցանկացած ծրագրում կարելի է գտնել այսպիսի օրինակներ։ Ցանկացած այսպիսի օրինակի գեղեցկության կամ տգեղության մասին կարելի է վիճել։ Բայց ինձ համար մի բան հաստատ է. ծրագրավորումը կարելի է համարել կիրառական արվեստի մի ճյուղ։ Եվ տեղին է այդ արվեստի նմուշների համար օգտագործել գեղեցիկ և տգեղ բնութագրումները։ Իսկ ծրագրավորողներին ու թեսթավորողներին, այն մարդկանց, ովքեր իրենք առօրյա աշխատանքում գրում ու կարդում են հարյուրավոր ու հազարավոր տողերով ծրագրային տեքստ, մնում է այդ գործում գտնել ու գնահատել գեղեցիկը։

Saturday, August 1, 2015

Տեքստի հավասարեցում ըստ էջի լայնության

«Этюды для программистов» (Чарльз Уэзерелл, ― «Etudes for Programmers», Charles Wetherell) գրքի չորրորդ էտյուդն առաջարկում է գրել տեքստի ֆորմատավորման ծրագիր, որի պահանջներից մեկը տողի բառերի արանքներում բացատներ ավելացնելով տեքստը ըստ էջի լայնության հավասարացնելն է։ Տեքստի ֆորմատավորման այս մասնակի խնդիրն է նկարագրված նաև, օրինակ, «100 задач по программированию» գրքի (հեղինակներ՝ Дагене В. А., Григас Г. К., Аугутис К. Ф.) 78-րդ առաջադրանքում, որ կոչվում է «Տեքստի տեխնիկական խմբագրում»։

Մի կողմից կարող է այս խնդիրը, գործնական տեսակետից, հնացած թվալ, մյուս կողմից էլ, սակայն, ժամանակակից տեքստային խմբագրիչներում և տեքստային պրոցեսորներում նույնպես կիրառվում են տեքստի հավասարեցման գործողություններ։ Օրինակ, LibreOffice Writer ծրագիրը հավասարեցումը կատարում է ոչ թե բացատների քանակն ավելացնելով, այլ դրանց չափերն ավելացնելով։ Կամ, TeX տեքստային պրոցեսորում ընդհանրապես բացակայում է բացատ նիշը, իսկ հավասարեցման համար բառերի արանքները լցվում են «սոսինձ» կոչվող ազատ տարածությամբ։

Խնդրի լուծման ընթացքը կարող է լինել այսպիսին (որ նույնպես կարդացել եմ ինչ-որ գրքում, արդեն չեմ հիշում, թե՝ որ). ա) տրված տեքստը տրոհել առավելագույնը n երկարությամբ տողերի՝ չթույլատրելով բառի տրոհում, բ) եթե արդյունքում տողի երկարությունն ավելի կարճ է ստացվում, քան n թիվը, ապա պատահական բառերի արանքներում ավելացնել այնքան բացատներ, որ տողի երկարությունը դառնա n-ի հավասար։ Հավասարեցման գործողությունը պետք չէ կիրառել վերջին տողի նկատմամբ։

Այս գրառման մեջ ես պատմում եմ, թե ինչպես եմ C լեզվով ծրագրավորել տեքստն ըստ լայնության հավասարեցման գործողությունը։ Ստորև բերված ծրագրում ես դիտարկում եմ տեքստի հետ կապված մի քանի հասկացություններ. բառ, տող և պարագրաֆ։ Տվյալների կառուցվածքների տեսակետից տեքստը պարագրաֆների հաջորդականություն է։ Պարագրաֆը տողերի կապակցված ցուցակ է։ Տողը բառերի կապակցված ցուցակ է։

#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <time.h>

Տեքստի մեկ բառը ներկայացնելու համար նախատեսել եմ word ստրուկտուրան։ Սրա w դաշտը բառի տեքստն է, l դաշտը բառի երկարությունն է, s դաշտը բառին հաջորդող բացատների քանակն է, իսկ n դաշտը հաջորդ բառի ցուցիչն է։

/* տեքստի բառի ներկայացումը */
struct word {
  char* w;        /* պարունակությունը */
  size_t l; /* երկարությունը */
  size_t s; /* հաջորդող բացատների քանակը */
  struct word* n; /* հաջորդ բառի ցուցիչը */
};

Իմ առաջին խնդիրն է const char* text ցուցիչով տրված տողի սկզբից առանձնացնել len երկարությամբ հատված, և կազմել այդ հատվածի բառերի կապակցված ցուցակը։ split_to_words ֆունկցիան ստանում է տողի ցուցիչը, դիտարկվող հատվածի երկարությունը և վերադարձնում է կառուցված ցուցակի առաջին տարրի ցուցիչը։ (Բայց քանի որ տողը բառերի տրոհելու ընթացքում բառերի ցուցակը կառուցվում է գլխիվայր, առաջին բառի ցուցիչը վերադարձնելուց առաջ նախ պետք է շրջել կառուցված ցուցակը։) Բոլոր լրացուցիչ բացատրությունները գրված են ֆունկցիայի մարմնում՝ C լեզվի մեկնաբանությունների տեսքով։

/* Տրոհել տեքստը և կառուցել բառերի կապակցված ցուցակ։ 
   Վերադարձնում է առաջին բառի ցուցիչը։ */
struct word* split_to_words( const char* text, size_t len )
{
  /* բառերի ցուցակը */
  struct word* res = NULL;

  /* տրոհել տողը */
  const char* end = text + len; /* դիտարկվող հատվածի վերջը */
  /* քանի դեռ text ցուցիչը չի հասել հատվածի վերջին */
  while( text != end ) {
    /* անցնել բացատների վրայով */
    while( isspace(*text) ) ++text;
    /* text-ը ցույց է տալիս բառի սկիզբը, 
       p ցուցիչը որոնում է բառի վերջը */
    const char* p = text;
    /* քանի դեռ բացատ չէ և տողն ավարտող 0 նիշը չէ,
       առաջ տանել p-ն */
    while( !isspace(*p) && *p != '\0' ) ++p;
    /* բառի ստրուկտուրայի նմուշի համար վերցնել հիշողություն */
    struct word* wo = malloc(sizeof(struct word));
    /* բառի չափը նրա վերջն ու սկիզբը ցույց տվող ցուցիչների 
       դիրքերի տարբերությունն է */
    wo->l = p - text;
    /* հիշղություն վերցնել բառի պարունակության համար */
    wo->w = malloc(1 + wo->l);
    /* պատճենել գտված բառը ստրուկտուրայի մեջ */
    strncpy(wo->w, text, wo->l);
    /* բառի վերջում ավելացնել 0 նիշը */
    wo->w[wo->l] = '\0';
    /* բառին հաջորդում է 1 բացատ */
    wo->s = 1;
    /* նոր ստեղծվող բառը կցել ցուցակի սկզբից */
    wo->n = res;
    /* ցուցակի սկիզբ համարել նոր ավելացրած բառը */
    res = wo;
    /* անցնել հաջորդ բառի որոնմանը */
    text = p;
  }
  /* վերջին բառին հաջորդող բացատների քանակը նշել զրո */
  res->s = 0;

  /* շրջել բառերի միակապ ցուցակը */
  struct word* pp = NULL;
  struct word* nn = res->n;
  while( nn != NULL ) {
    res->n = pp;
    pp = res;
    res = nn;
    nn = nn->n;
  }
  res->n = pp;

  /* վերադարձնել կառուցված ցուցակը */
  return res;
}

Տեքստի մեկ տողը ներկայացնելու համար սահմանել եմ line ստրուկտուրան։ Սրա w դաշտը կապված է տվյալ տողի բառերի ցուցակի առաջին տարրին, c դաշտում պահվում է տողի բառերի քանակը, l դաշտը ցույց է տալիս տողի երկարությունը, իսկ n դաշտը հաջորդ տողի ցուցիչն է։

/* տեքստի տողի ներկայացումը */
struct line {
  struct word* w; /* բառերի ցուցակ */
  size_t c; /* բառերի քանակ */
  size_t l; /* տողի երկարություն */
  struct line* n; /* հաջորդ տողի ցուցիչ */
};

Տեքստի տողը, ինչպես վերն ասացի՝ բառերի կապակցված ցուցակ է, կառուցվում է create_line ֆունկցիայով։ Սա ստանում է տեքստի ցուցիչը և մեկ տողի առավելագույն երկարությունը։

/* Կառուցել տրված երկորությամբ տող */
struct line* create_line( const char* str, size_t len )
{
  /* կառուցել բառերի ցուցակը */
  struct line* res = malloc(sizeof(struct line));
  res->w = split_to_words( str, len );
  /* բառերի քանակն ու տողի երկարությունը դեռ զրո են */
  res->c = 0; res->l = 0;
  /* սկսել առաջին բառից */
  struct word* i = res->w;
  /* քանի դեռ բառերը չեն վերջացել */
  while( i != NULL ) {
    /* ավելացնել բառերի հաշվիչը */
    ++res->c;
    /* հաշվել տողի ընթացիկ երկարությունը */
    res->l += i->l + i->s;
    /* անցնել հաջորդ բառին */
    i = i->n;
  }
  /* հաջորդ տողի ցուցիչը դեռ դատարկ է */
  res->n = NULL;
  /* վերադարձնել կառուցված օբյեկտը */
  return res;
}

Քանի որ տողերի ցուցակի կառուցման համար էլ է օգտագործվում դինամիկ առանձնացված հիշողություն, պետք է նախատեսել նաև այդ հիշողությունը խնամքով ազատելու և համակարգին վերադարձնելու միջոցը։ Դա արվել է destroy_words ֆունկցիայով։

/* քանդել տողերի ցուցակը */
void destroy_words( struct word* l )
{
  /* եթե ցուցակը դատարկ չէ */
  if( l != NULL ) {
    /* ռեկուրսիվ կանչ ցուցակի պոչի համար */
    destroy_words( l->n );
    /* ազատել բառի տեեքստի տեղը */
    free(l->w);
    /* ազատել բառի ստրուկտուրայի տեղը */
    free(l);
  }
}

Տողերի ցուցակ կազմելու համար պետք է append_line ֆունկցիայով տրված տողի n ցուցիչին կապել ևս մի տող։ Սա մի հասարակ ռեկուրսիվ ֆունկցիա է։

/* տողերի ցուցակի պոչից կցել ևս մի տող */
void append_line( struct line** dest, struct line* src )
{
  if( *dest == NULL )
    *dest = src;
  else
    append_line( &((*dest)->n), src );
}

Պարագրաֆը տողերի ցուցակ է (տողն էլ իր հերթին՝ բառերի ցուցակ է)։ create_paragraph ֆունկցիան ստանում է նախնական տողի ցուցիչը և ֆորմատավորվող տեքստի նպատակային լայնությունը։ Ինչպես վերևում՝ լրացուցիչ բացատրությունները ծրագրի տեքստում են։

/* տրված տեքստից կառուցել տրված երկարությունը չգերազանցող տողերի ցուցակ */
struct line* create_paragraph( const char* text, size_t width )
{
  /* արդյունքի ցուցիչը */
  struct line* res = NULL;
  /* դիտարկվողղ տողի սկիզբն ու վերջը ցույց տվող ինդեքսներ */
  size_t begin = 0, end = strlen(text);
  /* քանի դեռ տեքստի վերջը չէ */
  while( begin < end ) {
    /* հաշվել հերթական հատվածի վերջը */
    size_t pos = begin + width;
    /* ճշտվում է վերջին հատվածի եզրը */
    if( pos > end ) pos = end;
    /* հատվածի աջ եզրից հետ գալ՝ կիսատ բառը չվերցնելու համար */
    while( !isspace(text[pos]) && text[pos] != '\0' ) --pos;
    /* կառուցել նոր տող և կցել տողերի ցուցակի պոչից */
    append_line( &res, create_line( text + begin, pos - begin ) );
    /* անցնել տեքստի հաջորդ հատվածին */
    begin = pos;
  }
  /* վերադարձնել պարագրաֆների ցուցակը */
  return res;
}

Պարագրաֆի համար առանձնացված հիշողության դինամիկ տիրույթը համակարգին է վերադարձվում destroy_lines ֆունկցիայի օգնությամբ։

/* ազատել պարագրաֆի զբաղեցրած հիշողությունը */
void destroy_lines( struct line* p )
{
  /* եթե տողերի ցուցակը դատարկ չէ */
  if( p != NULL ) {
    /* ռեկուրսիվ կանչ պոչի համար */
    destroy_lines(p->n);
    /* քանդել բառերի ցուցակը */
    destroy_words(p->w);
    /* ազատել տողի ստրուկտուրայի տեղը */
    free(p);
  }
}

Պարագրաֆի տողերը արտածման ստանդարտ հոսքին են դուրս բերվում print_lines ֆունկցիայով։ Այն նախ տպում է բառը, իսկ հետո՝ դրան հաջորդող բացատաները՝ հարկավոր քանակով։ Արտածվելիք բացատների քանակը պահվում է word ստրուկտուրայի s դաշտում։ print_lines ֆունկցիայում սահմանված spaces ստատիկ հաստատունը պարունակում է բառից հետո արտածվող բացատների ենթադրվող առավելագույն երկարությամբ տողը, իսկ scount փոփոխականը՝ այդ տողի երկարությունը։ k->w բառն արտածելուց հետո պարզապես պետք է արտածել նաև spaces տողի վերջին k->s հատվածը։

/* արտածել տողերը */
void print_lines( struct line* lines )
{
  /* բացատների տող, և բացատների քանակ */
  static const char* spaces = "                   ";
  static const size_t scount = 20;

  /* քանի դեռ ցուցակի վերջը չէ */
  while( lines != NULL ) {
    /* k-ն ցուցակի աչաջին բառն է */
    struct word* k = lines->w;
    /* քանի դեռ k-ն չի հասել բառերի ցուցակի վերջին */
    while( k != NULL ) {
      /* արտածել բառը դրան հաջորդող բացատները */
      printf( "%s%s", k->w, spaces + scount - k->s );
      /* անցնել հաջորդ բառին */
      k = k->n;
    }
    /* արտածել նոր տողին անցնելու նիշը */
    putchar('\n');
    /* անցնել պարագրաֆի հաջորդ տողին */
    lines = lines->n;
  }
}

Տողի հավասարեցման մարտավարությունը հետևյալն է․ քանի դեռ հացասարեցվող տողի երկարությունը, որը ցույց է տալիս line ստրուկտուրայի l դաշտը, փոքր է պահաջվածից, տողում ընտրել պատահական մի բառ (բացի վերջինից) և դրան հաջորդող բացատների քանակն ավելացնել մեկով։

Տողի n-րդ բառի ցուցիչը վերցնելու համար է նախատեսված nth ֆունկցիան։ Եթե տողում բառերի քանակը ավելի քիչ է, քան տրված n թիվը, ապա, բնականաբար, վերադարձվում է NULL։

/* Վերադարձնում է բառերի ցուցակի n-րդ տարրը։ */
struct word* nth( struct word* list, size_t n )
{
  struct word* res = list;
  while( n-- > 0 ) {
    res = res->n;
    if( res == NULL )
      return NULL;
  }
  return res;
}

Վերջապես ամեն ինչ պատրաստ է՝ պարագրաֆը տրված լայնությամբ հավասարեցնելու համար։ justify_paragraph ֆունկցիան ստանում է տողերի ցուցակն ու տողի հարկավոր width լայնությունը։ Այնուհետև, անցնելով ցուցակի բոլոր տարրերով, բառերի արանքներում բացատներ է ավելացնում այնքան ժամանակ, քանի դեռ տողի երկարությունը չի հասել width թվին։

/* տողերը հավասարեցնել՝ բառերի արանքներում
   ներմուծելով լրացուցիչ բացատներ */
void justify_paragraph( struct line* par, size_t width )
{
  /* քանի դեռ ցուցակի նախավերջին տողը չէ */
  while( par->n != NULL ) {
    /* քանի դեռ տողի երկարությունը փոքր է width-ից */
    while( par->l < width ) {
      /* ընտրել պատահական ինդեքս */
      int po = rand() % (par->c - 1);
      /* վերցնել տողի՝ այդ ինդեքսով բառը */
      struct word* wd = nth( par->w, po );
      /* 1-ով ավելացնել բառի բացատների քանակը */
      ++wd->s;
      /* 1-ով ավելացնել տողի ընդհանուր երկարությունը */
      ++par->l;
    }
    /* անցնել հաջորդ տողին */
    par = par->n;
  }
}

Ահա այսքանը։ Մնում է միայն կազմակերպել ծրագրի մուտքի կետը՝ main ֆունկցիան, որպեսզի հնարավոր լինի ծրագիրն օգտագործել իր նշանակությամբ։ Նախատեսված է, որ ծրագիրը տեքստը կարդում է ներմուծման ստանդարտ հոսքից, իսկ ֆորմատավորված արդյունքը դուրս է բերում արտածման ստանդարտ հոսքին։

int main( int argc, char** argv )
{
  /* ծրագիրը որպես պարամետր սպասում է միայն
     տեքստի լայնությունը */
  if( argc != 1 && argc != 3 )
    return 1;

  /* եթե լայնությունը տրված չէ՝ այն համարել 40 */
  size_t length = 40;
  /* հրամանային տողից կարդալ length-ի նոր արժեքը */
  if( argc == 3 )
    if( argv[1][0] == '-' && argv[1][1] == 'w' )
      sscanf(argv[2], "%d", &length);

  /* արժեքավորել պատահական թվերի գեներատորը */
  srand(time(0));

  /* նախնական տեքստի բուֆերի չափը */
  const size_t bsize = 4096;
  /* դինամիկ բուֆեր՝ տեքստի համար */
  char* text = calloc(bsize, sizeof(char));
  /* քանի դեռ stdin-ի վրա կարդալու բան կա,
     կարդալ այն text բուֆերի մեջ */
  while( fgets(text, bsize, stdin ) != NULL ) {
    /* կարդացած տեքստից կառուցել տողերի ցուցակ */
    struct line* u = create_paragraph( text, length );
    /* հավասարեցնել պարագրաֆը տրված լայնությամբ */
    justify_paragraph( u, length );
    /* արտածել պարագրաֆի տողերը */
    print_lines( u );
    /* ազատել պարագրաֆի զբաղեցրած հիշողությունը */
    destroy_lines( u );
  }
  /* ազատել բուֆերի զբաղեցրած հիշողությունը */
  free(text);

  return 0;
}

Ծրագիրը կոմպիլյացնելու համար կարելի է օտագործել gcc կամ clang կոմպիլյատորները․

$ gcc -std=c11 -o splitext splitext.c

Իսկ test1.txt ֆայլում պարունակվող տեքստը, օրինակ, 30 նիշ լայնությամբ տողերով ֆորմատավորելու համար պետք է գրել։

$ ./splittext -w 30 < text1.txt

Նույն արդյունքը կարելի է ստանալ նաև հետևյալ հրամանով․

$ cat test1.txt | ./splittext -w 30

Sunday, July 12, 2015

Հեշավորում (թարգմանության փորձ)

Թարգմանված է Նիկլաուս Վիրտի «Ալգորիթմներ
և տվյալների կառուցվածքներ» գրքից։

5 Բանալիների բաշխում (Հեշավորում)

5.1 Ներածություն

Չորրորդ գլխում քննարկվող սկզբունքային հարցը հետևյալն էր․ եթե տրված է բանալիով (key) բնութագրվող տարրերի բազմություն (բանալու վրա սահմանված է նաև կարգի հարաբերություն), ապա ինչպե՞ս կազմակերպել այդ բազմությունը, որպեսզի տրված բանալիով տարրին դիպելու համար պահանջվի նվազագույն ջանք։ Պարզ է, որ կոմպյուտերի հոշողության մեջ գտնվող որևէ տարրին դիմելու համար պետք է ունենալ նրա հասցեն։ Հետևաբար, նշված խնդիրը բերվում է K բանալիները A հասցեներին արտապատկերող H ֆունկցիայի սահմանմանը։

H: K → A

Չորրորդ գլխում այդ արտապատկերումը իրականացվում էր զանազան տվյալների կառուցվածքների վրա հիմնված ցուցակներում և ծառերում որոնման տարբեր ալգորիթմներով։ Այստեղ ներկայացնում ենք ըստ էութան պարզ և շատ դեպքերում արդյունավետ ևս մի եղանակ։ Այնուհետև կքննարկենք նաև այդ եղանակի որոշ թերություններ։

Այս մոտցման մեջ տվյալները կազմակերպվում են զանգվածի տեսքով։ Այս դեպքում H֊ը բանալիները զանգվածի ինդեքսներին բաշխող արտապատկերում է, որտեղից էլ հենց առաջացել է այս մեթոդի համար օգտագործվող բանալիների բաշխում անվանումը։ Պետք է նշել, որ այս դեպքում կարիք չունենք հիշողության դինամիկ առանձնացնող գործողությունների․ զանգվածը մեկն է հիմնարար, ստատիկ կառուցվածքներից։ ?? Բանալիների բաշխման մեթոդը հաճախ օգտագործվում է այն խնդիրներում, որտեղ մոտավորապես նույն հաջողությամբ կարելի է օգտագործել նաև ծառաձև կառուցվածքները։

Բանալիների բաշխման եղանակն օգտագործելիս հիմնական դժվարությունն այն է, որ թույլատրելի բանալիների բազմությունն էապես ավելի մեծ է, քան հիշողության մատչելի հասցեները (զանգվածի ինդեքսները)։ Որպես բանալի վերցնենք, օրինակ, մինչև 16 նիշ պարունակող անունները, որոնք հազարավոր մարդկանց մեջ նույնականացնում են առանձին անհատների։ Այսինքն, գոյություն ունեն 26^16 հնարավոր բանալիներ, որոնք պետք է արտապատկերել 10^3 հնարավոր ինդեքսների։ Ակնհայտ է, որ այս դեպքում H֊ը շատը֊մեկին ֆունկցիա է։ Եթե տրված է k բանալին, ապա որոնման գործողության առաջին քայլը h=H(k) ինդեքսի հաշվարկումն է, իսկ երկրորդ, ակնհայտորեն պարտադիր, քայլը ստուգելն է, թե արդյո՞ք k բանալիով տարրը համապատասխանում է T զանգվածի (աղյուսակի) h ինդեքսով տարրին, այսինքն, ստուգել T[H(k)].key = k հավասարությունը։ Անմիջապես հանդիպում ենք հետևյալ երկու հարցերին․

  1. Ինչպիսի՞ն պետք է լինի H ֆունկցիան։
  2. Ի՞նչ անել, եթե H ֆունկցիան չի կարողացել հաշվել որոնելի տարրի դիրքը։

Երկրորդ հարցի պատասխանը կայանում է նրանում, որ պետք է ունենալ մի մեթոդ, որը վերադարձնում է այլընտրանաքային դիրք, ասենք h', եթե այդ նոր դիրքն էլ նորից չի պարունակում որոնելի տարրը, ապա վերադարձնում է h'' դիրքը, և այդպես շարունակ։ ?? Եթե հաշվարկված դիրքում գտնվում է որոնելի տարրից տարբերվող մի այլ տարր, ապա այդ իրավիճակը կոչվում է կիլիզիա (collision), իսկ այլընտրանքային դիրքի հաշվարկը՝ կոլիզիայի լուծում։ Ստորև կքննարկենք բանալիների բաշխման ֆունկցիայի ընտրությունը և կոլիզիայի լուծման եղանակները։

5.2 Հեշավորող ֆունկցիայի ընտրությունը

Լավ բաշխման ֆունկցիայի համար կարևոր նախապայմանն է, որ այն կարողանա բանալիների բազմությունը հնարավորինս հավասարաչափ բաշխել ինդեքսների արժեքների ամբողջ միջակայքին։ Այս պայմանից բացի բաշխման համար այլ սահմանափակումներ չկա, սակայն իրականում ցանկալի է, որ այն նման լինի պատահական բաշխման։ Այսպիսի առանձնահատկությունը բանալիների բաշխման մեթոդին տվել է թերևս ոչ֊գիտական մի անվանում՝ հեշավորում (hashing), այսինքն՝ արգումենտի կտրտում, վերածում ինչ֊որ «խյուսի»։ ?? H֊ն էլ կոչվում է հեշավորող ֆունկցիա (հեշ֊ֆունկցիա)։ Պարզ է, որ H֊ը պետք է լինի էֆեկտիվ հաշվարկվող, այսինքն՝ բաղկացած լինի շատ քիչ թվով թվաբանական գործողություններից։

Դիցուք կարող ենք օգտագործել ORD(k) ֆունկցիան, որը վերադարձնում է k բանալու հերթական համարը՝ կարգաթիվը, բոլոր հնարավոր բանալիների բազմության մեջ։ Ենթադրենք նաև, որ զնգվածի i ինդեքսը տարածվում է 0֊ից մինչև N-1, որտեղ N֊ը զանգվածի տարրերի քանակն է։ Այս դեպքում ընտրությունն ակնհայտ է․

H(k) = ORD(k) MOD N

Այս ֆունկցիան ապահովում է բանալիների հավասարաչափ բաշխումն ինդեքսների ամբողջ միջակայքում և հենց դրա համար էլ օգտագործվում է շատ հեշ֊ֆունկցիաներում։ Այն նաև շատ արդյունավետ հաշվարկվում է, եթե N֊ը երկուսի աստիճան է։ Սակայն եթե բանալին տառերի հաջորդականություն է, ապա հենց այսպիսի ֆունկցիայից պետք է խուսափել։ Բանն այն է, որ այս դեպքում բոլոր բանալիների՝ հույն հավանականությամբ հանդիպելու ենթադրությունը սխալ է։ Իրականում բառերը, որոնք տարբերվում են միայն մի քանի տառերով, մեծ հավանականությամբ կարող են արտապատկերվել դույն ինդեքսին, որն էլ կստեղծի խիստ անհավասարաչափ բաշխում։ Այս պատճառով էլ գործնականում խորհուրդ է տրվում N֊ը վերցնել մի որևէ պարզ թիվ [5-2]։ Որպես հետևանք արդեն հարկ է լինում օգտագործել լրիվ բաժանման գործողություն, որը հնարավոր չէ փոխարինել երկուական թվանշանների կրճատումով։ Սակայն ժամանակակից կոմպյուտերներում սա դժվար խնդիր չէ, քանի որ դրանցում առկա է ներդրված բաժանման գործողություն։ ??

Հաճախ օգտագործվում են բանալու որևէ հատվածի երկուական ներկայացման վրա կիրառվող տրամաբանական գործողություններից կառուցված հեշավորող ֆունկցիաներ (այդպիսի գործողություններից է, օրինակ, «բացառող կամ»-ը)։ ?? Որոշ կոմպյուտերների վրա այս գործողությունները կարող են կատարվել ավելի արագ, քան բաժանումը, բայց հաճախ դրանք բերում են ինդեքսերի միջակայքում բանալիների զարմանալի անհավասարաչափ բաշխման։ Այդ պատճառով էլ ձեռնպահ կմնանք այդպիսի մեթոդների հետագա քննարկումից։

5.3 Կոլիզիաների լուծումը

Եթե պարզվում է, որ աղյուսակի՝ տրված բանալուն համապատասխանեցված տարրը որոնելին չէ, ապա տեղի ունի կոլիզիա, այսինքն՝ երկու տարբեր տարրերի բանալիներ արտապատկերվում են նույն ինդեքսին։ Այս դեպքում անհրաժեշտ է երկրորդ փորձը՝ տրված բանալուց խիստ որոշակի եղանակով ստացվող ինդեքսի օգտագործմամբ։ ?? Գոյություն ունեն երկրորդային ինդեքսների հաշվարկման մի քանի մեթոդներ։ Ակնհայտ եղանակ է՝ կապակցված ցուցակում հավաքել նույն H(k) առաջնային ինդեքս ունեցող տարրերը։ Սա կոչվում է ուղիղ կապակցում (direct chaining)։ Այս ցուցակի տարրերը կարող են առաջնային աղյուսակում լինել կամ չլինել, երկրորդ դեպքում դրանց զբաղեցրած հիշողության տիրույթը կոչվում է գերբեռնվածության տիրույթ (overflow area)։ Այս հնարքի թերությունն այն է, որ պետք է կազմակերպել երկրորդային ցուցակների հետ աշխատանքը, ինչպես նաև աղյուսակի ամեն մի տարրը պետք է ցուցիչ (կամ ինդեքս) ունենա խնդրահարույց տարրերի ցուցակի համար։

Կոլիզիաների լուծման այլընտրանքային եղանակ է՝ ընդհանրապես հրաժարվել ցուցակներից և պարզապես դիտարկել նույն աղյուսակի մյուս տարրերը, մինչև կգտնվի տարրը կամ կգտնվի ազատ դիրք։ Վերջին դեպքում համարում ենք, որ որոնվող տարրն աղյուսակում բացակայում է։ Այս եղանակը կոչվում է բաց հասցեավորում (open addressing) [5-3]։ Բնականաբար, տրված բանալու համար երկրորդային փորձերի ինդեքսների հաջորդականությունը միշտ պետք է նույնը լինի։ Ըստ ասվածի, որոնման ալգորիթմը կարող է ունենալ հետևյալ տեսքը․

h := H(k); i := 0;
REPEAT
  IF T[h].key = k THEN տարր գտնված է
  ELSIF T[h].key = free THEN տարրն աղյուսակում չէ
  ELSE (* կոլիզիա *)
    i := i+1; h := H(k) + G(i)
  END
UNTIL գտնված կամ աղյուսակում չէ (կամ աղյուսակը լիքն է)

Կոլիզիաների լուծման տարբեր եղանակներ են առաջարկվլ գրականության մեջ։ Մորիսի (Morris) կողմից 1968-ին թեմայի ուսումնասիրությունը [5-2] բավականին աշխուժություն բերեց ոլորտ։ Ամենապարզ ձևը՝ դիտարկել աղյուսակի հերթական տարրը (համարենք աղյուսակը շրջանաձև), մինչև կգտնվի տրված բանալիով տարրը կամ կգտնվի դատարկ տեղ։ Այսպիսով, G(i) = i, իսկ հաջորդկան փորձերի համար օգտագործվող h_i ինդեքսները որոշվում են հետևյալ կերպ․

h_0 = H(k)
h_i = (h_i-1 + i) MOD N,    i = 1 ... N-1

Սա կոչվում է գծային փորձերի եղանակ (linear probing)։ Նրա թերությունն այն է, որ տարրերը ձգտում են կուտակվել առաջնային բանալիների շուրջը (այսինքն՝ այն բանալիների շուրջը, որոնք ավելացնելիս կոլիզիա չի առաջացել)։ Իհարկե, իդեալական դեպքում G ֆունկցիան էլ պետք է բանալիները հավասարաչափ բաշխի ազատ դիրքերի բազմության վրա։ Սակայն գործնականում բավականին դժվար է ապահովել այդ պահանջը, և այս դեպքում նախընտրում են փոխզիջումային մեթոդներ, որոնք պահանջում են բարդ հաշվարկներ, բայց ավելի լավն են քան գծային ֆունկցիան։ Դրանցից մեկում օգտագործվում է քառակուսային ֆունկցիան այնպես, որ հաջորդական փորձերի ինդեքսները որոշվում են հետևյալ կերպ․

h_0 = H(k)
h_i = (h_0-1 + i^2) MOD N,    i > 0

Նկատենք, որ հերթական ինդեքսը հաշվելիս կարելի է ազատվել քառակուսի բարձրացնելու գործողությունից, եթե h_i = i^2 և d_i = 2i + 1 համար օգտագործենք հետևյալ անդրադարձ առնչությունները․

h_i+1 = h_i + d_i
d_i+1 = d_i + 2,    i >0

որտեղ h_0 = 0 և d_0 = 1։ Սա կոչվում է քառակուսային փորձերի մեթոդ (quadratic probing), և ըհդհանուր դեպքում այն շրջանցում է վերը նշված կուտակումների խնդիրը՝ գործնականում չպահանջելով լրացուցիչ հաշվարկներ։ Մի փոքր թերությունն այն է, որ հաջորդական փորձերի ժամանակ աղյուսակի ոչ բոլոր տարրերն են ստուգվում, այսինքն տարրն ավելացնելիս հնարավոր է չնկատել ազատ դիրքը, թեև աղյուսակում այդպիսիք կան։ Իրականում, եթե N-ը պարզ թիվ է, ապա քառակուսային փորձերի մեթոդով ստուգում է աղյուսակի ամենաքիչը կեսը։ Այս պնդումը կարելի է դուրս բերոլ հետևյալ կերպ։ Այն փաստը, որ i-րդ և j-րդ փորձերը բերում են այսուսակի նույն տարրին, արտահայտվում է հետևյալ հավասարությամբ․

i^2 MOD N = j^2 MOD N
(i^2 - j^2) ≡ 0 (modullo N)

Քառակուսիների տարբերությունն արտահայտելով երկու արտադրիչներով ստանում ենք․

(i + j)(i - j) ≡ 0 (modulo N)

և քանի որ i ≠ j, ապա եզրակացնում ենք, որ i և j թվերից գոնե մեկը պետք է փոքր լինի N/2-ից, որպեսզի ամբողջաթիվ c-ի համար ստանանք i + j = c * N։ Գործականում այս թերությունն էական չէ, քանի որ կոլիզիայի լուծման համար N/2 փորձեր հազվադեպ են կատարվում, այն էլ միայն այն դեպքում, երբ աղյուսակը համարյա լիքն է։

Որպես քննարկված տեխնիկայի կիրառություն բերված է 4.4.3 բաժնի խաչաձև հղումներ գեներացնող ծրագրի ձևափոխությունը։ ?? Հիմնական տարբերությունները search պրոցեդուրայում են և T գլոբալ հեշ աղյուսակի Node ցուցաչային տիպի փոխարինելում։ ?? Հեշ-ֆունկցիա H-ը հաշվարկվում է որպես աղյուսակի չափի վրա բաժանման մնացորդ (modulus)։ Կոլիզիաների լուծման համար օգտագործված է քառակուսային փորձերի մեթոդը։ Նշենք նաև, որ լավ արտադրողականության համար շատ կարևոր է աղյուսակի չափի պարզ թիվ լինելը։

Չնայած որ այս խնդրի համար հեշավորման մեթոդը բավականին արդյունավետ է, նույնիսկ ավելի արդյունավետ, քան ծառաձև կառուցվածքները, այն ունի նաև թերություններ։ Տեքստը կարդալուց և բառերն առանձնացնելուց հետո մենք, հավանաբար, կուզենանք դրանք դասավորել այբբենական կարգով։ Դա դժվար չէ, եթե օգտագործվում են ծառաձև կառուցվածքներ, քանի որ կարգավորվածությունն ընկած է ծառաձև կառուցվածքների հիմքում։ ?? Սակայն գործը դժվարանում է բանալիների բաշխում օգտագործելիս։ ?? Այստեղ է, որ բացահայտվում է «հեշավորում» բառի ամբողջ իմաստը։ Աղյուսակն արտածելու համար պետք է ոչ միայն այն կարգավորել (այդ կտորն այստեղ բաց է թողնված), այլև բացահայտ հետևել աղյուսակում ավելացվող բանալիներին՝ դրանք հավաքելով կապակցված ցուցակում։ Այդ պատճառով էլ հեշավորման ժամանակ որոնման բարձր արագությունը մասնակիորեն փոխհատուցվում է լրացուցիչ գործողություններով, որոնք հարկավոր են խաչաձև հղումների խնդիրն ամբողջությամբ լուծելու համար։

CONST N = 997; (* պարզ թիվ, աղյուսակի չափը *)
  WordLen = 32; (* բանալիների առավելագույն երկարությունը *)
  Noc = 16; (* տարրերի առավ․ քանակը մեկ բառում *)

TYPE
  Word = ARRAY WordLen OF CHAR;
  Table = POINTER TO ARRAY N OF
    RECORD key: Word; n: INTEGER;
      lno: ARRAY Noc OF INTEGER
    END;

VAR line: INTEGER;

PROCEDURE search (T: Table; VAR a: Word);
  VAR i, d: INTEGER; h: LONGINT; found: BOOLEAN;
BEGIN (* հաշվել h հեշ ինդեքսը a-ի համար; օգտագործում է line գլոբալ փոփոխականը*)
  i := 0; h := 0;
  WHILE a[i] > 0X DO h := (256*h + ORD(a[i])) MOD N; INC(i) END;
  d := 1; found := FALSE;
  REPEAT
    IF T[h].key = a THEN (* համընկնում *)
      found := TRUE; T[h].lno[T[h].n] := line;
      IF T[h].n < Noc THEN INC(T[h].n) END
    ELSIF T[h].key[0] = " " THEN (* աղյուսակի նոր տարր *)
      found := TRUE; COPY(a, T[h].key); T[h].lno[0] := line; T[h].n := 1
    ELSE (* կոլիզիա *) h := h+d; d := d+2;
      IF h >= N THEN h := h-N END;
      IF d =N THEN
        Texts.WriteString(W," Աղյուսակը գերբեռնված է"); HALT(88)
      END
    END
  UNTIL found
END search;

PROCEDURE Tabulate (T: Table); (* օգտագործվում է W գլոբալ օբյեկտը *)
  VAR i, k: INTEGER;
BEGIN
  FOR k := 0 TO N-1 DO
    IF T[k].key[0] # " " THEN
      Texts.WriteString(W, T[k].key); Texts.Write(W, TAB);
      FOR i := 0 TO T[k].n -1 DO Texts.WriteInt(W, T[k].lno[i], 4) END;
      Texts.WriteLn(W)
   END
  END
END Tabulate;

PROCEDURE CrossRef (VAR R: Texts.Reader);
  VAR i: INTEGER; ch: CHAR; w: Word;
    H: Table;
BEGIN
  NEW(H); (* ստեղծել հեշ աղյուսակը *)
  FOR i := 0 TO N-1 DO H[i].key[0] := " " END;
  line := 0;
  Texts.WriteInt(W, 0, 6); Texts.Write(W, TAB); Texts.Read(R, ch);
  WHILE ~R.eot DO
    IF ch = 0DX THEN (*line end*) Texts.WriteLn(W);
      INC(line); Texts.WriteInt(W, line, 6); Texts.Write(W, 9X); Texts.Read(R, ch)
    ELSIF ("A" <= ch) & (ch <= "Z") OR ("a" <= ch) & (ch <= "z") THEN
      i := 0;
      REPEAT
        IF i < WordLen-1 THEN w[i] := ch; INC(i) END;
        Texts.Write(W, ch); Texts.Read(R, ch)
      UNTIL (i = WordLen-1) OR ~(("A" <= ch) & (ch <= "Z")) &
            ~(("a" <= ch) & (ch <= "z")) & ~(("0" <= ch) & (ch <= "9"));
      w[i] := 0X; (*string terminator*)
      search(H, w)
    ELSE Texts.Write(W, ch); Texts.Read(R, ch)
    END;
    Texts.WriteLn(W); Texts.WriteLn(W); Tabulate(H)
  END
END CrossRef

5.4 Բանալիների բաշխման մեթոդի վերլուծությունը

Բանալիների բաշխման մեթոդի վատագույն դեպքում բանալին ավելացնելու և որոնելու արտադրողականությունը սարսափելի է։ Լրիվ հնարավոր է, որ որոնման արգումենտնը փորձերի ժամանակ անցնի բոլոր զբաղված դիրքերով՝ ոչ մի անգամ չընկնելով աղյուսակի անհրաժեշտ (կամ ազատ) դիրքի վրա։ ?? Հեշավորման տեխնիկան օգտագործելու համար պետք է բավականաչափ վստահ լինել հավանականության տեսության օրենքներին։ Մենք պարզապես ուզում ենք համոզված լինել, որ փորձերի միջին թիվը փոքր է։ Ստորև բերված հավանակային փաստարկներն ցույց են տալիս, որ այդ թիվը ոչ թե փոքր է, այլ շատ փոքր է։

Մեկ անգամ էլ ենթադրենք, որ բոլոր բանալիների հանդիպելու հավանականությունը հավասար է, իս H հեշ-ֆունկցիան դրանք հավասարաչափ բաշխում է աղյուսակի ինդեքսների միջակայքի վրա։ Ենթադրենք նաև, թե բանալին պետք է ավելացվի արդեն k հատ տարրեր պարունակող և N չափ ունեցող աղյուսակի մեջ։ Այդ դեպքում առաջին փորձից ազատ դիրքի վրա ընկնելու հավանականությունը (N-k)/N է։ Սա նաև միայն մեկ համեմատում կատարելու p_1 հավանականությունն է։ Հավանականությունը, որ պետք կլինի ճիշտ մեկ երկրորդային փորձ, հավասար է առաձին փորձում կոլիզիայի հավանականությանը՝ բազմապատկած երկրորդ փորձում ազատ դիրքի վրա ընկնելու հավանականությանը։ Այսպիսով, ստանում ենք ճիշտ i փորձեր կատարելու p_i հավանականության հաշվման հետևյալ եղանակը․

p_1 = (N-k)/N
p_2 = (k/N) × (N-k)/(N-1)
p_3 = (k/N) × (k-1)/(N-1) × (N-k)/(N-2)
..........
p_i = (k/N) × (k-1)/(N-1) × (k-2)/(N-2) × ... × (N-k)/(N-(i-1))

Այստեղից էլ աղյուսակում k+1-րդ բանալին ավելացնելու փորձերի E քանակը հավասար է․ ??

E_k+1 = __S__i: 1 ≤ i ≤ k+1 : i × pi = 1 × (N-k)/N + 2 × (k/N) × (N-k)/(N-1) + ... + (k+1) * (k/N) × (k-1)/(N-1) × (k-2)/(N-2) × ... × 1/(N-(k-1)) = (N+1) / (N-(k-1))

Քանի որ տարրն աղյուսակում ավելացնելու փորձերի քանակը հավասար է նրա որոնման փորձերի քանակին, այս արդյունքը կարելի է օգտագործել աղյուսակում պատահական բանալին գտնելու փորձերի E քանակը հաշվելու համար։ Թող նորից N-ը ցույց տա աղյուսակի տարրերի քանակը, և թող m-ը լինի աղյուսակում առկա բանալիների քանակը։ Այդ դեպքում․

E = (Sk: 1 ≤ k ≤ m : Ek) / m = (N+1) × (Sk: 1 ≤ k ≤ m : 1/(N-k+2))/m = (N+1) × (HN+1 - HN-m+1)

որտեղ H-ը հարմոնիկ ֆունկցիան է։ H-ը կարելի է մոտարկել որպես H_N = ln(N) + g, որտեղ g-ն Էյլերի հաստատունն է։ Այնուհետև, եթե m/(N+1)-ը փոխարինենք a-ով, կստանանք․

E = (ln(N+1) - ln(N-m+1))/a = ln((N+1)/(N-m+1))/a = -ln(1-a)/a

a-ն մոտավորապես աղյուսակի զբաղված և ազատ դիրքերի քանակների հարաբերությունն է, որ կոչվում է լրացվածության գործակից (load factor)։ a=0-ն նշանակում է դատարկ աղյուսակ, իսկ a= N/(N+1) ≈ 1-ը՝ լցված աղյուսակ։ Պատահական բանալին աղյուսկում ավելացնելու կամ որոնելու փորձերի E միջին քանակը Աղյուսակ 5.1-ում թվարկված է որպես լրացվածության գործակցի ֆունկցիա։

a      E
0.1    1.05
0.25   1.15
0.5    1.39
0.75   1.85
0.9    2.56
0.95   3.15
0.99   4.66

Աղյուսակ 5.1։ Փորձերի ակնկալվող թիվը որպես լրացվածության գործակցի ֆունկցիա։

Զարմանալի թվեր են ստացվել և դրանք բացատրում են բանալիների բաշխման մեթոդի բացառիկ բարձր արտադրողականությունը։ Նույնիսկ եթե աղյուսակը 90%-ով լիքն է, միջինում 2.56 փորձ է հարկավոր՝ բանալին կամ դատարկ տեղ գտնելու համար։ Հատուկ նշենք, որ այս թիվը կախված է միայն լրացվածության գործակցից և ոչ բանալիների ընդհանուր քանակից։

Բերված վերլուծությունը հիմնված է աղյուսակի ազատ դիրքերի վրա բանալիները հավասարաչափ բաշխող կոլիզիաները լուծող մեթոդի վրա։ ?? Գործնականում օգտագործվող մեթոդները տալիս են քիչ ավելի վատ արդյունք։ Գծային փորձերի մեթոդի մանրամասն վերլուծությունը փորձերի միջին թվի համար տալիս է հետևյալ արդյունքը․

E = (1 - a/2) / (1 - a)

Որոշ թվային արդյունքներ բերված են Աղյուսակ 5.2-ում [5.4].

a     E
0.1   1.06
0.25  1.17
0.5   1.50
0.75  2.50
0.9   5.50
0.95  10.50

Աղյուսակ 5.2. Ակնկալվող փորձերի քանակը գծային փորձերի համար։

Կոլիզիաների լուծման նույնիսկ ամենապարզ մեթոդի արդյունքներն այնքան լավն են, որ գոյթակղություն է առաջանում հեշավորման մեթոդն օգտագործել որպես կյանքի բոլոր դեպքերի փրկարակ միջոց։ Մասնավորապես այն պատճառով, որ նրա արտադրողականությունը գերազանցում է նույնիսկ ամենակատարյալ ծառաձև կառուցվածքներով մեթոդներինը, հենց միայն տարրը որնելու և ավելացնելու համար համեմատությունների տեսակետից։ ?? Եվ հենց այս տեսակետից է կարևոր նշել հեշավորման մի քանի թերությունները, եթե նույնիսկ դրանք ակնհայտ են անշահախնդիր վերլուծության ժամանակ։

Իհարկե, հիշողության դինամիկ կառավարում օգտագործող մեթոդների համեմատությամբ գլխավոր թերությունը աղյուսակի ֆիքսված չափն է, որը չի կարող փոխվել ըստ անհրաժեշտության։ Այդ պատճառով էլ, եթե անընդունելի է հոշողության ոչ-խնայողական օգտագործումը կամ ցածր արտադրողականությունը (կամ աղյուսակի գերբեռնվածությունը), ապա հարկավոր է մշակվող տվյալների տարրերի քանակի բավականաչափ լավ նախնական վերլուծություն։ Նույնիսկ եթե տարրերի քանակը չիշտ հայտնի է, որ հազվադեպ է պատահում, լավ արտադրողականության համար ձգտումը ստիպում է ընտրել քիչ ավելի մեծ (ասենք, 10%) աղյուսակ։

Բաշխման մեթոդների երկրորդ մեծ թերություն ակնհայտ է դառնում, երբ աղյուսակում պետք է ոչ միայն որոնել կամ ավելացնել տարրը, այլև հեռացնել այն։ Հեշ-աղյուսակից տարրերի հեռացնելը չափազանց ծանր է, եթե միայն առանձին գերբեռնվածության տիրույթում ուղիղ կամապցումը չէ օգտագործված։ Այդ պատճառով էլ արդարացի կլինի նշել, որ ծառաձև կառուցվածքների օգտագործումը դեռևս ավելի գայթակղիչ է, հույնիսկ ավելի նախընտրելի է, եթե մշակվող տվյալների ծավալն ակնկանխատեսելի է, խիստ տատանվում է իսկ երբեմն նաև պակասում է։

Sunday, July 5, 2015

1.8 Որոնում (թարգմանության փորձ)

Թարգմանված է Նիկլաուս Վիրտի «Ալգորիթմներ
և տվյալների կառուցվածքներ» գրքից։

Որոնումը կոմպյուտերային ծրագրավորման ամենից շատ հանդիպող գործողություններից է։ Այն նաև իդեալական խնդիր է զանազան տվյալների կառուցվածքները փորձարկելու համար։ ?? Գոյություն ունեն որոնման թեմայի մի քանի վարաիցիաներ, և մշակված են բազմաթիվ ալգորիթմներ։ Հետևյալ քննարկումներում ենթադրվում է, որ տվյալների հավաքածուն, որի մեջ որոնվելու է տրված տարրը, ֆիքսված է։ Կհամարենք, որ N տարրերի բազմությունը տրված է, օրինակ, զանգվածի տեսքով․

a : ARRAY N OF Item

Սովորաբար Item տիպը նկարագրված է որպես գրառում (record), որի դաշտերից մեկը բանալին (key) է։ Խնդիրը բերվում է այն տարրի գտնելուն, որի բանալին հավասար է x որոնման արգումենտին։ Արդյունքում ստացված i ինդեքսը, որ բավարարում է a[i].key = x պայմանին, հնարավորություն է տալիս դիմելու գտնված տարրի մյուս դաշտերին։ Քանի որ մեզ հետաքրքրում է միայն որոնման խնդիրը, և առայժմ չենք մտածում այն մյուս տվյալների մասին, որոնց համար որոնվում էր տարրը, կենթադրենք, որ Item տիպը պարունակում է միայն բանալին, այսինքն այն ինքը հենց բանալին է։

1.8.1 Գծային որոնում

Եթե որոնվող տվյալների մասին այլ լրացուցիչ տեղեկություններ տրված չեն, ապա ակնհայտ մոտեցումը զանգվածի տարրերի հաջորդական դիտարկումն է, քայլ առ քայլ մեծացնելուվ նրա այն հատվածի չափը, որտեղ որոնվող տարրը հայտնաբերված չէ։ Այս մոտեցումը կոչվում է գծային որոնում։ Որոնման ավարտի պայմանները երկուսն են․

  1. Տարրը գտնված է, այնսինքն՝ a[i] = x։
  2. Դիտարկված է ամբողջ զանգվածը և համընկնում չի հայտնաբերված։

Ստացվում է հետևյալ ալգորիթմը․

i := 0;
WHILE (i < N) & (a[i] # x) DO INC(i) END

ՈՒշադրություն դարձրեք, որ բուլյան արտահայտության մեջ ենթաարտահայտությունների կարգը կարևոր է։

Ցիկլի ինվարիանտը, այսինքն այն պայմանը, որը ճշմարիտ է ցիկլի ամեն մի իտերացիայի սկզբում և վերջում, այսպիսինն է․

(0 ≤ i < N) & (Ak: 0 ≤ k < i: a[k] ≠ x)

Այն ցույց է տալիս, որ k֊ից փոքր բոլոր i֊երի համար համընկնումներ չեն եղել։ ՈՒշադրություն դարձնենք նաև, որ ցիկլի ամեն մի իտերացիայից առաջ և հետո i֊ի արժեքները տարբեր են։ Այնուամենայնիվ, ինվարիանտը պահպանվում է ցիկլի պայմանում։

Այս ասվածից և այն փաստից, որ որոնումն ավարտվում է միայն այն ժամանակ, երբ ցիկլի պայմանը տեղի չունի (կեղծ է), կարելի է դուրս բերել վերջնական պամանը․

((i = N) OR (a[i] = x)) & (Ak: 0 ≤ k < i: a[k] ≠ x)

Այս պայմանը ոչ միայն մեր ցանկալի արդյունքն է, այլ դրանից նաև հետևում է, որ եթե ալգորիթմը գտել է համընկնում, ապա այն գտել է ամենքփոքր ինդեքսովը, այսինքն՝ առաջինը որոնվող տարրերից։ i = N հավասարությունը ցույց է տալիս, որ համընկնումներ չեն հայտնաբերվել։

Ցիկլի կրկնությունների ավարտը ակնհայտորեն երաշխավորված է, որովհետև ամեն մի քայլում i֊ի արժեքն աճում է, հետևաբար այն, իհարկե, վերջավոր քայլերից հետո կհասնի N֊ին։ Իրականում, եթե համընկնումներ չեն եղել, ապա դա տեղի կունենա N քայլից հետո։

Պարզ է, որ յուրաքանչյուր քայլում պահանջվում է մեծացնել ինդեքսը և հաշվել բուլյան արտահայտությունը։ Կարելի՞ է արդյոք այս խնդիրը պարզեցնել, և դրանով պարզեցնել նաև որոնման գործողությունը։ Միակ հնարավորությունը երկու կտորից բաղկացած բուլյան արտահայտությունը պարզեցնելու մեջ է։ Հետևաբար, միակ տարբերակը այնպիսի ավելի պարզ պայմանի ձևակերպումն է, որը համարժեք է մեր ունեցած բարդ պայմանին։ Դա հնարավոր է, եթե երաշխավորենք, որ համընկնում միշտ տեղի է ունենալու, որին կարելի է հասնել զանգվածի վերջում x արժեքով լրացուցիչ տարր ավելացնելով։ Այս լրացուցիչ տարրը կանվանենք պատնեշ (sentinel), որովհետև այն ինդեքսին արգելում է դուրս ելնել զանգված սահմաններից։ Այժմ a զանգվածը սահմանված է որպես․

a: ARRAY N+1 OF INTEGER

իսկ գծային որոնման ալգորիթմը, պատնեշի օգտագործմամբ, կունենա հետևյալ տեսքը․

a[N] := x; i := 0;
WHILE a[i] # x DO INC(i) END

Նույն ինվարիանտից դուրս բերված վերջնական պայմանը կլինի․

(a[i] = x) & (Ak: 0 ≤ k < i: a[k] ≠ x)

Պարզ է, որ i = N պայմանը ցույց է տալիս համընկնումներ չեն եղել՝ բացառությամբ պատնեշի հետ համընկնելը։

1.8.2 Որոնում կիսման եղանակով (բինար որոնում)

Լրիվ ակնհայտ է, որ այլևս հնարավորություն չկա արագացնելու որոնման գործողությունև, եթե միայն որոնվող տարրերի մասին տրված չեն լրացուցիչ տեղեկություններ։ Հայտնի է, որ որոնումը կարելի է ավելի արդյունավետ դարձնել, եթե տվյալները կարգավորված են։ Պատկերացրեք, օրինակ, մի հեռախոսագիրք, որում անունները այբբենական կարգով դասավորված չեն։ Դա լրիվ անպետք բան է։ Մենք կներկայացնենք ալգորիթմ՝ հիմնված a զանգվածում տարրերի կարգավորված լինելու փաստի վրա, այսինքն՝ հաշվի առնելով հետևյալ պայմանը․

Ak: 1 ≤ k < N: a[k-1] ≤ a[k]

Հիմնական գաղափարն է՝ վերցնել մի պատահական տարր, օրինակ, a[m] և այն համեմատել x որոնման արգումենտի հետ։ Եթե այն հավասար է x֊ին, ապա որոնումն ավարտվում է, եթե այն փոքր է x֊ից, ապա m֊ից փոքր կամ հավասար ինդեքս ունեցող բոլոր տարրերը կարելի է բացառել հետագա որոնումից, և եթե այն մեծ է x֊ից, ապա կարելի է բացառել m֊ից մեծ և հավասար ինդեքս ունեցող տարրերը։ Ասվածից հանգում ենք կիսման եղանակով որոնման ալգորիթմին։ Այն օգտագործում է L և R ինդեքսային փոփոխականները, որոնք ցույց են տալիս զանգվածի այն հատվածի ձախ և աջ սահմանները, որոնցում դեռ կարող է հայտնաբերվել որոնվող տարրը։

L := 0; R := N - 1;
m := L֊ի և R֊ի միջև ընկած որևէ տարր;
WHILE (L <= R) & (a[m] # x) DO
  IF a[m] < x THEN
    L := m + 1
  ELSE
    R := m - 1
  END;
  m := L֊ի և R֊ի միջև ընկած որևէ տարր
END

ՈՒշադրություն դարձրեք այս ալգորիթմի և նախորդ բաժնում նկարագրված գծային որոնման ալգորիթմի հիմնական կառուցվածքային նմանությանը․ այստեղ i ինդեքսի դերկ կատարում է L, m, R եռյակը։ Այդ նմանությունը բացատրելու, և, այնուհետև, ցիկլի կոռեկտության մեջ ավելի լավ համոզվելու համար, մենք ձեռնպահ մնացինք փոքրիկ օպտիմիզացիայից, որը կբացառեր m֊ի երկու նույնական վերագրումները։

Ցիկլի ինվարիանտը, այսինքն՝ ամեմ մի քայլից առաջ ու հետո տեղի ունեցող պայմանը, հետևյալն է․

(Ak: 0 ≤ k < L: a[k] < x) & (Ak: R < k < N: a[k] > x)

որից դուրս է բերված հետևյալ արդյունքը․

((L > R) OR (a[m] = x)) & (Ak: 0 ≤ k < L: a[k] < x) & (Ak: R < k < N: a[k] > x)

որից էլ հետևում է․

((L > R) & (Ak: 0 ≤ k < N: a[k] ≠ x)) OR (a[m] = x)

m ինդեքսի ընտրությունը բոլորովին կամայական է այն իմաստով, որ ալգորիթմի կոռեկտությունը դրանից կախված չէ։ Բայց m֊ի ընտրությունն ազդում է ալգորիթմի արդյունավետության վրա։ Պարզ է, որ մեր նպատակն է ցիկլի ամեն մի քայլում հետագա որոնումից բացառել որքան հնարավոր է շատ տարրեր՝ անկախ համեմատման արդյունքից։ Լավագույն լուծումը կենտրոնական տարրի ընտրությունն է, որովհետև ամեն մի քայլում այն բացառում է զանգվածի տարրերի կեսը։ Արդյունքում քայլերի առավելագույն քանակը հավասար է log2 N, կլորացված վերև՝ մինչև ամենամոտիկ ամբողջ թիվը։ Այսպիսով, այս ալգորիթմը էականորեն շահեկան է գծային որոնման ալգորիթմից, որում համեմատությունների սպասվող քանակը N/2 է։

Արդյունավետությունը կարելի է մի քիչ լավացնել, տեղերով փոխելով ցիկլի մարմնի IF պայմանները։ Հավասարությունը պետք է ստուգել երկրորդ հերթին, որովհետև այն հանդիպում է միայն մեկ անգամ և բերում է ցիկլի ավարտին։ Բայց ավելի կարևոր է այն հարցը, թե արդյոք, ինչպես գծային որոնման դեպքում, հնարավո՞ր է գտնել ցիլի ավարտը որոշող ավելի պարզ պայման։ Իսկապես մենք գտնում ենք այդպիսի արագ ալգորիթմ, հենց որ հրաժարվում ենք որոնման ցիկլը տարրերի համընկնումով ավարտելու միամիտ ցանկությունից։ Առաջին հայացքից սա տարօրինակ է թվում, բայց ավելի ուշադիր ուսումնասիրությամբ բացահայտվում է, որ ամեն մի քայլում արդյունավետության շահն ավելին է, քան մի քանի լրացուցիչ տարրերի համեմատումից ստացված կորուստները։ Հիշենք, որ քայլերի առավելագույն քանակը log N է։

Արագ լուծումը հիմնված է հետևյալ ինվերիանտի վրա․

(Ak: 0 ≤ k < L: a[k] < x) & (Ak: R ≤ k < N: a[k] ≥ x)

և որոնումը շարունակովում է այնքան ժամանակ, քանի դեռ երկու հատվածները չեն ծածկել ամբողջ զանգվածը։

L := 0; R := 0;
WHILE L < R DO
  m := (L + R) DIV 2;
  IF a[m] < x THEN L := m + 1 ELSE R := m END
END

Ավարտի պայմանն է L ≥ R։ Բայց հասանելի՞ է արդյոք այն։ Այս պնդումն ապացուցելու համար պետք է ցույց տանք, որ բոլոր դեպքերում R - L տարբերությունը նվազում է ամեն մի քայլից հետո։ L < R տեղի ունի յուրաքանչյուր քայլ սկզբում։ m թվաբանական միջինի կամար ճշմարիտ է L ≤ m < R։ Հետևաբար, տարբերությունն իրոք նվազում է L֊ին m+1 վերգրելով (Լ-ը մեծացնելով), կամ R֊ին m վերագրելով (R֊ը նվազեցնելով), և ցիկլի կրկնությունն ավարտվում է L = R պայմանով։

Այնուամենայնիվ, մեր ինվարիանտը և L = R պայմանը դեռևս համընկնում չեն նշանակում։ Իհարկե, եթե R = N, ապա համընկնում չկա։ Այլապես պետք է հաշվի առնենք, որ a[R] տարրը երբեք չի համեմատվել։ Հետևաբար, մի լրացուցիչ a[R] = x հավասարության ստուգումն անհրաժեշտ է։ Ի տարբերություն առաջին լուծման, այս ալգորիթմը, ինչպես և գծային որոնումը, գտնում է ամենափոքր ինդեքսով համընկնող տարրը։

1.8.3 Որոնում աղյուսակում

Զանգվածում որոնումը երբեմն անվանում են նաև որոնում աղյուսակում, հատկապես եթե բանալիները բաղադրյալ օբյեկտներ են, ինչպես օրինակ թվերի կամ նիշերի զանգվածը։ Վերջինս հոնդիպում է ավելի հաճախ․ նիշերի զնգվածներն անվանում են տողեր կամ բառեր։ Սահմանենք String տիպը հետևյալ կերպ․

String = ARRAY M OF CHAR

իսկ x և y տողերի միջև կարգը սահանենք հետևյալ կերպ․

(x = y) ≡ (Aj: 0 ≤ j < M : x[j] = y[j])

(x < y) ≡ Ei: 0 ≤ i < N : ((Aj: 0 ≤ j < i : x[j] = y[j]) & (x[i] < y[i]))

Ակնհայտ է, որ համընկնումը հաստատելու համար, պետք է համոզվենք, որ համեմատվող տողերի բոլոր նիշերը համընկնում են։ Բաղադրյալ օպերանդների այսպիսի համեմատումը բերվում է օպերանդներում չհամընկնող մասերի հայտնաբերմանը, այսինքն՝ անհավասարության որոնման։ Եթե գոյություն չունի չհամընկնող մասեր, ապա հավասարությունը հաստատված է։ Ենթադրենք բառերի երկարությունը բավականաչափ փոքր է, ասենք 30֊ից փոքր, այդ դեպքում կօգտագործենք գծային որոնումը։

Շատ գործնական կիրառություններում ցանկալի է ընդունել, որ տողն ունի փոփոխական երկարություն։ Սա ենթադրում է, որ յուրաքանչյուր տողի հետ պահվում է նաև իր երկարությունը։ Օգտագործելով վերը սահմանված String տիպը, այդ երկարությունը չպետք է գերազանցի M առավելագույն արժեքը։ Այս սխեման բավականաչափ ճկուն է և ընդունելի է շատ դեպքերում, ինչպես նաև ազատում է դինամիկ հիշողության հետ աշխատելու դժվարություններից։ Լայնորեն օգտագործվում են տողի երկարությունը ներկայացնելու երկու ներկայացումներ․

  1. Երկարությունը բացահայտ նշվում է տողի վերջում մի հատուկ նիշ կցելով, որը այլ տեղերում չի հանդիպում։ Սովորաբար դա 0X չարտածվող արժեքն է։ (Հետագա կիրառություններում կարևոր է, որ այդ հատուկ նիշը նիշերի բազմության ամենափոքր տարրն է։)
  2. Երկարությունը բացահայտ նշվում է զանգվածի առաջին տարրում, այսինքն տողն ունի հետևյալ տեսքը․
s = s[0], s[1], s[2], ..., s[N-1]

որտեղ s[1]...s[N-1] տողի նիշերն ենմ և s[0] = CHR(N)։ Այս եղանակի առավելությունն այն է, որ երկարությունն ուղղակի մատչելի է, իսկ թերությունն այն է, որ տողի երկարությունը սահմանափակված է նիշերի բազմության հզորությամբ, այն է՝ 256 նիշ՝ ASCII կոդավորման դեպքում։

Ստորև բերված որոնման ալգորիթմում նախապատվությունը կտանք առաջին սխեմային։ Այդ դեպքում տողերի համեմատումն ընդունում է հետևյալ տեսքը․

i := 0;
WHILE (x[i] # 0X) & (x[i] = y[i]) DO i := i + 1 END

Այստեղ եզրափակող նիշը կատարում է պատնեշի դերը։ Ցիկլի ինվարիանտն է․

Aj: 0 ≤ j < i : x[j] = y[j] ≠ 0X

Իսկ վերջնական պայմանն ունի հետևյալ տեսքը․

((x[i] = 0X) OR (x[i] ≠ y[i])) & (Aj: 0 ≤ j < i : x[j] = y[j] ≠ 0X)

Այս պայմանը հաստատում է x և y տողերի հավասարությունը, երբ x[i] = y[i], և հաստատում է x < y պայմանը, եթե x[i] < y[i]։

Հիմա արդեն պատրաստ ենք վերադառնալու աղյուսակում որոնման խնդրին։ Այն պահանջվում է ներդրված որոնումներ, ավելի ճիշտ՝ որոնում աղյուսակի տարրերով, իսկ ամեն մի տարրի համար՝ կոմպոնենտների համեմատումների հաջորդականություն։ Օրինակ, թող որ T աղյուսակը և x որոնման արգումենտը սահմանված են այսպես․

T: ARRAY N OF String;
x: String

Ենթադրելով որ N֊ը բավականաչափ մեծ է և աղյուսակի տարրերը կարգավորված են այբբենական կարգով, կօգտագործենք որոնման կիսման մեթոդը։ Օգտագործելով բինար որոնման և տողերի համեմատման վերը մշակված ալգորիթմները, ստանում ենք ծրագրի հետևյալ հատվածը։

i := -1;
L := 0; R := N;
WHILE L < R DO
  m := (L + R) DIV 2;
  i := 0;
  WHILE (x[i] # 0X) & (T[m,i] = x[i]) DO i := i + 1 END;
  IF T[m,i] < x[i] THEN L := m + 1 ELSE R := m END
END;
IF R < N THEN
  i := 0;
  WHILE (x[i] # 0X) & (T[R,i] = x[i]) DO i := i + 1 END
END
(* (R < N) & (T[R,i] = x[i]) պայմանը որոշում է համընկնումը *)

Saturday, June 6, 2015

March թեսթի իրականացումը Java լեզվով

Այս գրառումը կիսատ է թողնված հավես չունենալու
պատճառով։ Ցանկացողները կարող են շարունակել այն։
Կարծում եմ, որ, զարգացնելու դեպքում, կարող է լավ
կուրսային աշխատանք լինել։


Հիշող սարքերի ներդրված թեսթավորման տարածված եղանակներից մեկը March թեսթերի կիրառումն է։ Այս գրառման մեջ ես ուզում եմ պատմել հիշող սարքի մոդելի, անսարքության մոդելի, ինչպես նաև March թեսթի մոդելի իրականացման մասին։

Ընդհանուր առմամբ գաղափարը հետևյալն է․ a) սահմանել տրված չափերով հիշող սարք, b) նրանում ներմուծել որոշ տիպի անսարքություններ, c) կազմել March թեսթեր, d) գործարկել թեսթերը հիշող սարքի մոդելի վրա և գրանցել արդյունքները։

Նշված տիպի մոդելավորումն օգտագործվում է March թեսթերի մշակման համար։ Մոդելավորման օգնությամբ ստեղծվում են թեսթեր, որոնք պետք է հիշող սարքի վրա հայտնաբերեն թեսթավորողին հայտնի անսարքությունները։

Հիշող սարքը

Սովորական և անսարք բջջի մոդելը

Հիշող սարքը մեկ բիթ ինֆորմացիա պահող հիշող տարրերի՝ բջիջների մատրից է։ Այդ բջջի մոդելը ես իրականացրել եմ Cell դասով։ Այս Cell-ը սարքին բջջի մոդելն է։
package memory;

/**
 * Հիշող բջջի մոդելը
 */
class Cell {
    // տվյալ բջիջը պարունակող մատրիցը
    private Memory parent = null;
    // տողը և սյունը
    private int row = 0, column = 0;
    // բջջի արժեքը
    private char value = 'x';

    // կոնստրուկտորը
    public Cell(Memory p, int r, int c)
    {
        parent = p;
        row = r;
        column = c;
    }

    // վերադարձնում է արժեքը
    public char read()
    {
        return value;
    }

    // փոխում է արժեքը
    public void write(char v)
    {
        value = v;
    }
}
Այս դասի parent անդամը այն հիշող սարքի մոդելի հղում է, որը պարունակում է տվյալ բջիջը։ row և column ինդեքսները ցույց են տալիս, թե հիշող սարքի մատրիցի որ տողում և սյունում է տեղադրված բջիջը։ Այս երեք հատկությունները հնարավորություն են տալիս մոդելավորել այնպիսի անսարքություններ, որտեղ մի բջջի ոչ սարքին լինելը ազդում է մեկ այլ սարքին բջջի պարունակության վրա։

Հիշող բջջի հետ կապված անսարքությունները մոդելավորելու համար պետք է ընդլայնել Cell դասը։ Օրինակ, հաճախ են հանդիպում այնպիսի բջջիջներ, որոնց կարդալու գործողությունը վերադարձնում է հաստատուն 0 կամ 1 արժեքը։ Հաստատուն զրո վերադարձնող բջիջը կարելի է մոդելավորել, օրինակ, ConstZero դասով։
package memory;

/**
 * Մշտական '0' վերադարձնող անսարք բջիջ
 */
public class ConstZero extends Cell {
    public ConstZero(Memory p, int r, int c)
    {
        super(p, r, c);
    }

    @Override
    public char read()
    {
        return '0';
    }
}

Բջիջների մատրիցը

Հիշող սարքը, որը հիշող բջիջների մատրից է մոդելավորված է Memory դասով։ Այն պարունակում է տողերի ու սյուների քանակները ցույց տվող rows և columns անդամները, և Cell օբյեկտների matrix մատրիցը։
package memory;

/**
 * Հիշողղ սարքի մոդելը
 */
public class Memory {
    // տողերի քանակը
    public int rows = 0;
    // սյուների քանակը
    public int columns = 0;
    // բջիջների մատրիցը
    private Cell[][] matrix = null;

    // կոնստրուկտորը
    public Memory(int r, int c)
    {
        rows = r;
        columns = c;
        matrix = new Cell[rows][columns];

        for( int i = 0; i < rows; ++i )
            for( int j = 0; j < columns; ++j )
                matrix[i][j] = new Cell(this, i, j);
    }

    // անսարքություն մոդելավորելու համար
    // տրված դիրքում տեղադրել տրված բջիջը
    public void replaceCell(int r, int c, cell cl)
    {
        matrix[r][c] = cl;
    }

    // կարդալ, տրված է գծային հասցեն
    public char read(int addr)
    {
        return read(addr / rows, addr % rows);
    }
    // կարդալ, տրված է ֆիզիկական հասցեն
    private char read(int r, int c)
    {
        return matrix[r][c].read();
    }

    // գրել, տրված է գծային հասցեն
    public void write(int addr, char d)
    {
        write(addr / rows, addr % rows, d);
    }
    // գրել, տրված է ֆիզիկական հասցեն
    private void write(int r, int c, char d)
    {
        matrix[r][c].write(d);
    }

    // արտածել մատրիցի պարունակությունը
    public void Print()
    {
        for( int r = 0; r < rows; ++r ) {
            System.out.printf("%x: ");
            for( int c = 0; c < columns; ++c )
                System.out.print(read(r,c));
            System.out.println();
        }
        System.out.println();
    }
}
Կոնստրուկտորում matrix մատրիցը արժեքավորվում է «սարքին» բջիջներով։ Իսկ replaceCell մեթոդը հնարավորություն է տալիս մատրիցի տրված դիրքի բջիջը փոխարինել նոր տրվածով։ replaceCell մեթոդին տրվում են բջջի ֆիզիկական հասցեները՝ տողը և սյունը, քանի որ հաճախ հիշող սարքերում կիրառվում է ավելի բարդ հասցեավորում քան գծայինն է, և հարմար է անսարք բջիջը տեղադրել ըստ ֆիզիկական դիրքի։

Հիմա, օրինակ, կարող եմ ստեղծել 8 տողեր և 4 սյուներ ունեցող հիշող սարք և դրա երկրորդ տողի առաջին բջջում տեղադրել մի անսարք բջիջ։
Memory mem = new Memory(8, 4);
mem.replaceCell(1, 0, new ConstZero(mem, 1, 0));
Կամ, քանի որ Java լեզուն հնարավորություն է տալիս օբյեկտի ստեղծման ժամանակ վերասահմանել նրա մեթոդները, կարող եմ ConsOne տիպի անսարքություն մոդելավորել այսպես․
mem.replaceCell(1, 1, new Cell(mem, 1, 1) {
    @Override
    public byte read() { return '1'; }
});

March թեսթը

March թեսթը March ալգորիթմների շարք է, որոնք հաջորդաբար գործարկվում են հիշող սարքի մոդելի վրա և ստեղծում են թեսթավորման արդյունքներ։ Ալգորիթմն իր հերթին March էլեմենտների շարք է, իսկ այս վերջինն էլ March գործողությունների շարք է։

Ես դիտարկում եմ միայն պարզագույն March թեսթերը, որոնցում հանդիպում են միայն գրելու և կարդալու գործողություններ։ Եվ որպեսզի March թեսթը նկարագրելիս ավելի անսխալ լինեմ, բերեմ դրա EBNF քերականությունը։
MarchTest = { Algorithm }.
Algorithm = IDENT '{' Element { ';' Element } '}'.
  Element = ('=>' | '<=') '(' Operation { ',' Operation } ')'.
Operation = ('W' | 'R') ('0' | '1').

March գործողություն

Տվյալ կոնտեքստում կան երկու March գործողություններ․ բջջում տրված արժեքը գրողW (write) գործողությունը, և բջջից տրված սպասվող արժեքը կարդացող R (read) գործողությունը։

Ես ուզում եմ նշված երկու գործողությունները մոդելավարել Operation դասով։ Վերջինիս code անդամը գործողության տեսակն է՝ R կամ W, իսկ data անդամը՝ այն արժեքը, որը պետք է գրել բջջում, կամ պետք է սպասել բջջից կարդալիս։
package march;

import memory.*;

public class Operation {
    // գործողությունը
    private char code = 'X';
    // գրելու կամ կարդալու տվյալը
    private char data = '?';

    public Operation(char c, byte d)
    {
        code = c;
        data = d;
    }
March գործողությունը Memory օբյեկտի վրա գործարկելու համար սահմանեմ runOn մեթոդը, որը ստանում է թեսթավորվող հիշող սարքի հղումը և այն գծային հասցեն, որում գտնվող բջջի նկատմամբ կիրառվում է գործողությունը։
    public boolean runOn(Memory mem, int addr)
    {
        boolean status = true;

        if( opcode == 'W' )
            mem.write(addr, value);
        else if( opcode == 'R' )
            status = value == mem.read(addr);

        if( !status )
            System.out.printf("'%s' գործողությունը ձախողվեց %d հասցեի վրա։",
                              toString(), addr);

        return status;
    }
Եվ վերջապես, ToString մեթոդը, որը վերադարձնում է գործողության տեքստային տեսքը։
    @Override
    public String toString()
    {
        return Character.toString(opcode) + Character.toString(value);
    }
}

March էլեմենտ

March էլեմենտն ունի երկու բաղադրիչ․ a) հասցեների թվարկման ուղղությունը՝ որոշվող => և <= սիմվոլներով, և b) March գործողությունների շղթան։
package march;

import memory.*;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * March էլէմենտը
 */
public class Element {
    // հասցեները նվազում են
    public static final int DEC = -1;
    // հասցեներն աճում են
    public static final int INC = 1;

    // հասցեի թվարկման ուղղությունը
    private int direction = 0;
    // գործողությունների շարքը
    private List<Operation> operations = null;

    public Element(int dir, List<Operation> opers)
    {
        direction = dir;
        operations = new ArrayList<Operation>();
        operations.addAll(opers);
    }
March էլեմենտի գործարկումը հիշող սարքի մոդելի վրա կատարվում է runOn մեթոդով։ Քանի որ հասցեների թվարկման ուղղությունը կարող է լինել ինչպես աճող այնպես էլ նվազող, ապա begin և end փոփոխականներում հաշվում եմ առաջին ու վերջին հասցեն։ Հետո while ցիկլի մարմինը կատարվում է այնքան ժամանակ, քանի դեռ begin փոփոխվող հասցեն չի հասել end հասցեին։ Ցիլկի մարմնում մի ուրիշ for ցիկլ է, որը հիշող սարքի մոդելի վրա հերթականորեն աշխատեցնում է March գործողությունները և status բուլյան փոփոխականի մեջ է կուտակում հաջողությունների ու ձախողումների արդյունքը։
    public boolean runOn(Memory mem)
    {
        // ամենամեծ հասցեն
        final int maxaddr = mem.rows * mem.columns - 1;

        // առաջին հասցեն
        int begin = direction == INC ? 0 : maxaddr;
        // վերջին հասցեն
        int end = direction == INC ? maxaddr : 0;

        boolean status = true;
        while( begin != end + direction ) {
            for( Operation op : operations ) {
                boolean opok = op.runOn(mem, begin);
                status = status && opok;
            }
            begin += direction;
        }

        return status;
    }
Էլեմենտի տեքստային ներկայացումը ստանալու համար գրել եմ toString մեթոդը։
@Override
    public String toString()
    {
        String ops = operations.stream()
                               .map(Operation::toString)
                               .collect(Collectors.joining(","));
        String dr = (direction == INC ? "=>" : "<=");
        return String.format("%s(%s)", dr, ops);
    }
}

March ալգորիթմ

March ալգորիթմը March էլեմենտների հավաքածու է՝ խմբավորված ինչ-որ անունի տակ։ Algorithm դասով մոդելավորել եմ March ալգորիթմը։
package march;

import memory.*;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * March ալգորիթմի մոդելը
 */
public class Algorithm {
    // ալգորիթմի անունը
    private String name = "";
    // էլեմենտների ցուցակը
    private List<Element< elements = null;

    /**/
    public Algorithm(String nm, List<Element> elems)
    {
        name = nm;
        elements = new ArrayList<Element>();
        elements.addAll(elems);
    }
Ալգորիթմը հիշող սարքի մոդելի վրա գործարկվում է նորից runOn անունն ունեցող մեթոդի միջոցով։ for ցիկլը անցնում է բոլոր էլեմենտներով և դրանք գործարկում է՝ արգումենտում տալով հիշող սարքի հղումը։ Կատարման կումուլյատիվ արդյունքը ձևավորվում է status փոփոխականում։
    public boolean runOn(Memory mem)
    {
        boolean status = true;

        for( Element el : elements ) {
            boolean elok = el.runOn(mem);
            status = status && elok;
        }

        if( !status )
            System.out.printf("'%s' ալգորիթմի կատարումը ձախողվեց։\n",
                     toString());

        return status;
    }
Վերջապես toString մեթոդը վերադարձնում է ալգորիթմի տեքստային ներկայացումը։
 @Override
    public String toString()
    {
        String estr = elements.stream()
                              .map(Element::toString)
                              .collect(Collectors.joining(";"));
        return String.format("%s { %s }", name, estr);
    }
}

Ալգորիթմների կառուցումը

Ես արդեն պատմեցի Operation, Element և Algorithm դասերի մասին։ Դրանցով կարելի է կազմել թեսթավորման ալգորիթմներ և դրանք գործարկել անսարքությունների մոդելներ պարունակող հիշող սարքի մոդելի վրա։ Բայց միայն նշված դասերի կոնստրուկտորներն օգտագործելով անհարմար է կառուցել մեծ ալգորիթմներ։ Օրինակ, միայն A0 { =>(W0); =>(W1,R1) } ալգորիթմը կառուցելու համար պետք է գրել հետևյալ Java կոդը։
List<Operation> ops0 = new ArrayList<>();
ops0.add( new Operation('W', '0') );

List ops1 = new ArrayList<>();
ops1.add( new Operation('W', '1') );
ops1.add( new Operation('R', '1') );

Element el0 = new Element(Element.INC, ops0);
Element el1 = new Element(Element.INC, ops1);

List els0 = new ArrayList<>();
els0.add(el0);
els0.add(el1);

Algorijthm al0 = new Algorithm("A0", els0);
Շատ ավելի հարմար կլիներ, որ ալգորիթմը կառուցվեր մարդուն հարմար տեքստային ներկայացումից։ Դրա համար march փաթեթում ավելացրել եմ Parser դասը, որի parse մեթոդը ստանում է March ալգորիթմի տեքստային ներկայացումը և վերադարձնում է կառուցված Algorithm օբյեկտի հղումը։
package march;

import java.util.ArrayList;
import java.util.List;

public class Parser {
    private char[] source = null;
    private int position = 0;

    public Algorithm parse(String src) throws Exception
    {
        source = src.replaceAll("\\s+", "").toCharArray();
        position = 0;

        return parseAlgorithm();
    }
Parser դասը մի պարզագույն քերականական վերլուծիչ է, որը «ճանաչում» է March ալգորիթմի վերը բերված քերականությունը․
Algorithm = IDENT '{' Element { ';' Element } '}'.
  Element = ('=>' | '<=') '(' Operation { ',' Operation } ')'.
Operation = ('W' | 'R') ('0' | '1').
Քերականական երեք կանոններից յուրաքանչյուրի համար ստեղծված են համապատասխան մեթոդները՝ parseAlgorithm, parseElement և parseOperation։ Սրանցից ամեն մեկը վերլուծում է քերականությամբ իր համար որոշված հատվածը և վերադարձնում է Algorithm, Element կամ Operation օբյկտի հղում։
    private Algorithm parseAlgorithm() throws Exception
    {
        char[] name = {0, 0};
        if( !Character.isUpperCase(source[position]) )
            throw new Exception("Սպասվում է լատիներեն մեծատառ։");
        name[0] = source[position++];
        if( !Character.isDigit(source[position]) )
            throw new Exception("Սպասվում է թվանշան։");
        name[1] = source[position++];

        if( source[position++] != '{' )
            throw new Exception("Սպասվում է '{'։");

        List<Element> elements = new ArrayList<>();
        elements.add(parseElement());
        while( source[position] == ';' ) {
            ++position;
            elements.add(parseElement());
        }

        if( source[position++] != '}' )
            throw new Exception("Սպասվում է '}'։");

        return new Algorithm(new String(name), elements);
    }

    private Element parseElement() throws Exception
    {
        int direction = 0;
        if( source[position] == '=' && source[position+1] == '>' )
            direction = 1;
        else if( source[position] == '<' && source[position+1] == '=' )
            direction = -1;
        else
            throw new Exception("Սպասվում է '=>' կամ '<=։");

        position += 2;

        if( source[position++] != '(' )
            throw new Exception("Սպասվում է '('։");

        List<Operation> operations = new ArrayList<>();
        operations.add(parseOperation());
        while( source[position] == ',' ) {
            ++position;
            operations.add(parseOperation());
        }

        if( source[position++] != ')' )
            throw new Exception("Սպասվում է ')'։");

        return new Element(direction, operations);
    }

    private Operation parseOperation() throws Exception
    {
        char code = source[position++];
        if( code != 'W' && code != 'R' )
            throw new Exception("Անծանոթ գործողություն");
        char data = source[position++];
        if( data != '0' && data != '1' )
            throw new Exception("Գործողության սխալ արժեք");

        return new Operation(code, data);
    }
Իհարկե, հարմար կլիներ Parser դասին ավելացնել ևս մի parse մեթոդ, որը ստանա ալգորիթմների ցուցակ և վերադարձնի Algorithm օբյեկտների հղումների ցուցակ։

Friday, May 15, 2015

C++11: Իտերացիա ֆայլային հոսքով

Բազմաթիվ ընթերցողների խնդրանքով այս
գրառումը նվիրում եմ Քիմ Քարդաշյանին։


C++11 լեզվում ներմուծված է նոր `for` հրամանը (range-based for loop), որը հնարավորություն է տալիս իտերացիա կատարել օբյեկտի `begin()`֊ից `end()` միջակայքում։ Օգտագործելով այդ `for` հրամանը, ուզում եմ հերթականությամբ թվարկել `ifstream` հոսքի նիշերը։ Ավելի պարզ ասած՝ ուզում եմ գրել այսպիսի մի կոդ․
// ...
std::ifstream inp(name);
// ...
for( char c : obj )
    std::cout << c;
// ...
Որտեղ `obj`-ը պիտի ստացվի `inp`֊ի հետ ինչ֊որ մանիպուլյացիաների արդյունքում։

Նոր `for` հրամանն օգտագործելու համար նրան տրվող օբյեկտը (որով պետք է իտերացիա կատարվի), պետք է ունենա `begin()` և `end()` մեթոդները։ Մի քիչ քչփորելուց հետո պատրաստեցի `IterableFile` դասը, որն ընդլայնում է `ifstream`-ը՝ ավելացնելով ֆայլի սկզբի հետ կապված իտերատորը վերադարձնող `begin()` մեթոդը և դատարկ իտերատոր վերադարձնող `end()` մեթոդը։
class IterableFile : public std::ifstream {
public:
  IterableFile( const char* name )
    : std::ifstream{name}
  {
    // պահպանել բացատանիշերը
    unsetf(std::ios_base::skipws); 
  }
  std::istream_iterator<char> begin()
  {
    // սկսել ֆայլի սկզբից
    clear(); seekg(0, std::ios::beg);
    return std::istream_iterator<char>(*this);
  }
  const std::istream_iterator<char> end()
  {
    return std::istream_iterator<char>();
  }
};
`IterableFile` դասի նմուշն արդեն կարելի է օգտագործել `for` իտերատորի մեջ, օրինակ, այսպես․
  IterableFile fin("ex0.cpp");

  for( char c : fin )
    std::cout << c;

  fin.close();
Շատ հարմար կլիներ, եթե նույն էֆեկտը ստանայի առանց նոր դաս գրելու, միայն STL֊ի հնարավորություններով, բայց կարծես թե դա չի ստացվում։ (Հաստատ չեմ կարող ասել։)

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-ինտերպրետատորը կարողանար ծիծանել, ապա այն ինչպիսի քրքջոց կբարձրացներ այս ֆունկցիան կարդալու ժամանակ։)