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) արտահայտությունները։