Գրքեր Lisp լեզվի մասին

Վերջին մի քանի տարիներին ես ակտիվորեն ուսումնասիրում եմ Lisp լեզուն, հատկապես նրա Common Lisp և Scheme տարատեսակները։ Եվ այդ ժամանակի ընթացքում հասցրել եմ ուսումնասիրել ավելի քան հարյուր գրքեր ու հոդվածներ՝ սկսած John McCarthy֊ի առաջին հոդվածից, վերջացրած Common Lisp֊ի ստանդարտով ու արհեստական բանականության մասին մենագրություններով։ Սակայն ես ուզում եմ այդ գրքերից առանձնացնել քանիսը, որոնք հատկապես կարևոր են Lisp լեզվի ուսումնասիրությունը սկսելու համար։

1. Practical Common Lisp, Peter Seibel ― հրաշալի գիրք է, գրված կենդանի լեզվով, առանց ավելորդ ճոռոմաբանությունների։ Բավականին շատ օրինակներով, որոնք բացահայտում են լեզվի բազմաթիվ հնարավարությունները և դրանց կիրառման առանձնահատկությունները։ Ազատ հասանելի է։ Մի քանի տարի առաջ թարգմանվել է նաև ռուսերեն՝ Практическое использование Common Lisp վերնագրով։

2. ANSI Common Lisp, Paul Graham ― Գրքի նախաբանում ասվում է, որ այն նախատեսված է Լիսպ լեզուն արագ ու հիմնավոր սովորելու համար։ Գրքի առաջին մասում մանրամասնորեն նկարագրվում են Լիսպ լեզվի հնարավորությունները, իսկ երկրորդ մասում՝ թվարկված և համառոտ նկարագրված է Common Lisp ստանդարտը։ Հեղինակը ՏՏ աշխարհի թերևս ամենահաջողակ մարդկանցից մեկն է։ Գիրքը նույն վերնագրով թարգմանված է ռուսերեն։

3. Common Lisp: the Language, 2nd ed., Guy Steel Jr. ― Այս գիրքը հենց Common Lisp ստանդարտն է։ Դրա ավելի քան 1000 էջերում մանրամասնորեն ու սպառիչ նկարագրված է լեզվի յուրաքանչյուր բաղադրիչ։ Լիսպ լեզվով աշխատելիս շատ օգտակար է մշտապես ձեռքի տակ ունենալ այս գիրքը։ Թարգմանված է ռուսերեն, սակայն հրատարակված չէ թղթի տարբերակով։ Common lisp: the Language գրքի և Common Lisp ստանդարտի հիման վրա պատրաստված է Common Lisp HyperSpec֊ը

4. Land of Lisp, Conrad Barski ― գծանկարներով ու ծաղրանկարներով հարուստ այս գրքում տարատեսակ խաղեր ծրագրավորելու օգնությամբ ու բավականին սրամիտ լեզվով պատմվում է Common Lisp լեզվի մասին։ Շատ հետաքրքիր գիրք է, հատկապես սկսնակների համար։

5. Common Lisp Recipes, Edmund Weitz ― Նոր եմ գտել այս գիրքը, դեռ չեմ հասցրել կարդալ։ Բայց բովանդակության մեջ քննարկված թեմաներից երևում է, որ շատ օգտակար ու հետաքրքիր նյութ է պարունակում։

Սկսելու համար թերևս այսքանը։

Ինչի՞ց սկսել Java լեզվի ուսումնասիրությունը

Իմ ընկերները, ուսանողները և ծանոթները, այն մարդիկ, ովքեր որոշել են սովորել ծրագրավորման Java լեզուն, հաճախ են հարցնում, թե ինչ գրքերից սկսել։ Ստորև ես հավաքել եմ այն մի քանի գրքերը, որոնք ինքս օգտագործել եմ (և օգտագործում եմ) Ջավա լեզվի հետ աշխատելիս։

1. Մի քանի տարի առաջ եմ հայտնաբերել Robert Sedgewick-ի, Kevin Wayne֊ի «Introduction to programming in Java», գիրքը, որը նախատեսված է Պրինստոնի համալսարանում ծրագրավորման սկզբնական դասընթացի համար։ Գեղեցիկ ու բազմազան օրինակներով, սխեմաներով ու պատկերներով հարուստ գիրք է։ (Վերջերս այս գիրքը վերահրատարակվել է՝ Java լեզուն Python լեզվով փոխարինված։)

2. Java 8. Руководство для начинающих, Герберт Шилдт ― հաջող գիրք է, հայտնի հեղինակը բավականին մանրամասնորեն շարադրում է Ջավա լեզվի վերջին տարբերակի հնարավորությունները։ Շատ հարմար է սկսելու համար։

3. Java 8. Полное руководство, Герберт Шилдт ― նույն հեղինակի մի ուրիշ գիրք, որն արդեն Ջավա լեզվի սպառիչ տեղեկատու է։ Այս գրքում կարելի է գտնել համարյա ամեն ինչ։

4. Java 7. Наиболее полное руководство, Хабибуллин Ильдар ― էլի լավ գիրք է, բայց սա ես խորհուրդ կտայի պարզապես ձեռքի տակ ունենալ, և եթե ին֊որ բան չես գտնում Շիլդտի գրքերում, նայել այստեղ։

5. Язык программирования Java SE 8. Подробное описание, Джеймс Гослинг, Гай Л. Стил և ուրիշներ ― հզոր գիրք է։ Հեղինակները հենց Ջավա լեզվի հեղինակներն են, ովքեր Ջավայի մասին գիտեն ամեն ինչ։

6. Java. Эффективное программирование, Блох Джошуа ― նորից հետաքրքիր գիրք է, որտեղ քննարկվում են Ջավա լեզվով ծրագրավորման առանձին հարցեր, առաջարկվում են հաճախ հանդիպող խնդիրների արդյունավետ լուծումներ։

7. Алгоритмы на Java, Седжвик Роберт, Уэйн Кевин ― իմ ամենասիրած գրքերից է։ Սա արդեն ոչ թե Ջավա լեզվի մասին է, այլ Ալգորիթմների իրականացման մասին է Ջավա լեզվի օգտագործմամբ։

8. Algorithms (4th Edition), Robert Sedgewick, Kevin Wayne ― նախորդ գրքի անգլերեն (օրիգինալ) տարբերակն է։

---

Բոլոր գրքերը կարելի է գտնել այստեղ։

GNU Emacs֊ի ևս մեկ ընդլայնում

GNU Emacs տեքստային խմբագրիչն իմ ամենօրյա աշխատանքային գործիքն է։ Դրանով եմ ես ծրագրեր գրում, նշումներ անում, OCR արված տեքստեր մաքրագրում և աշխատում իմ սեփական գրքերի ու գրառումների տեքստերի հետ։ Այս բոլոր գործերի մեծամասնությունը հայերեն տեքստերի հետ է կապված։ Եվ, բնականաբար, ինձ պետք է լինում ակտիվորեն օգտագործել Emacs-ի key-binding֊ները՝ ստեղնների համակցությունների հետ կապված գործողությունները։ Օրինակ, նոր ֆայլ ստեղծելու գործողությունը կապված է C-x C-f հաջորդականության հետ, որը նշանակում է․ «սեղմած պահել Control ստեղնը և հաջորդաբար սեղմել x և f ստեղնները»։ Սակայն անհարմարությունն այն է, որ Emacs֊ի բոլոր key-binding֊ները արված են լատինական (անգլերենի այբուբենի) տառերի համար, և հայերեն տեքստերի հետ աշխատելու ժամանակ, երբ մի որևէ գործ է պետք լինում անել, ես ստիպված եմ լինում փոխել ստեղնաշարը հայերենից անգլերենի, կատարել գործողութնունը (օրինակ, պահպանել ֆայլը, նշել տեքստի հատվածը և այլն), ապա վերադառնալ հայերեն դասավորությանն ու շարունակել իմ գործը տեքստի հետ։

Խմբագրման և գործողությունների հետ կապված անհարմարությունները լուծելու համար ես որոշեցի Emacs֊ի key-binding֊ները լրացնել նաև հայերեն տարբերակներով։ Այսինքն, ես ուզում եմ իմ .emacs ֆայլում ունենալ լատիներեն key-binding֊ներից հայերենի արտապատկերող մի այսպիսի արտահայտություն․

(armenian-keys 
 '(("C-x C-f" . "C-ղ C-ֆ")
   ("C-x C-s" . "C-ղ C-ս")
   ("M-w" . "M-ո")))

որում armenian-keys ֆունկցիան ստանում է կետով զույգերի (dotted pair) ցուցակ, որի տարրերից առաջինը արդեն գոյություն ունեցող համակցությունն է, իսկ երկրորդը դրա հայերեն համարժեքը, որը պետք է ստեղծել։

Արդեն գոյություն ունեցող key-binding֊ները պահվում են current-global-map ֆունկցիայի վերադարձրած օբյեկտում։ Ինձ հետաքրքրող key-binding֊ը վերցնում եմ lookup-key ֆունկցիայով, և global-set-key ֆունկցաիյով կապում եմ հայերեն համակցությանը։

armenian-keys ֆունկցիան սահմանել եմ հետևյալ կերպ․ այն անցնում է տրված ցուցակի տարրերով և ամեն մի զույգի համար կատարում է վերը թվարկված գործողությունները։

(defun armenian-keys (kml)
  (let ((cgm (current-global-map)))
    (dolist (e kml)
      (let ((en (kbd (car e)))
            (hy (kbd (cdr e))))
        (global-set-key hy (lookup-key cgm en))))))

Հիմա ես կարող եմ առանց ստեղնաշարը փոխելու օգտագործել ինձ հարկավոր գործողությունները։

GNU/Emacs֊ի փոքր ընդլայնում

Հայերեն տեքստերը OCR գործիքներով ճանաչելիս բավականին հաճախ է պատահում, որ բառի մեջ հայտնվում են անցանկալի բացատանիշեր։ Դա կապված է, օրինակ հայերեն տառերի պատկերների հետ, երբ տառի ձախ ու աջ կողմերից կան ցցված մասեր։

Երբ մաքրագրում եմ այդպիսի «ցանցառ» տեքստերը, ժամանակիս մեծ մասը ծախսվում է բացատները հեռացնելու վրա։ Հենց այդ պատճառով էլ որոշեցի GNU/Emacs֊ի համար (քանի որ այդ խմբագրիչն եմ առավել հաճախ օգտագործում) գրել մի օժանդակ ֆունկցիա, որը կհեռացնի տեքստնի նշված հատվածի՝ ռեգիոնի բացատները։

Ես պետք է կատարեի հետևյալ քայլերը․ i) վերցնել նշված տեքստը, ii) տեքստից հեռացնել բացատները, iii) հեռացնել հին տեքստը և iv) տեղադրել հեռացված բացատներով տեքստը։ Այս քայլերը պետք է ծրագրավորել որպես Emacs Lisp լեզվի ֆունկցիա, և կապել ստեղնների ինչ֊որ համակցության հետ, որպեսզի հնարավոր լինի այն օգտագործել տեքստի խմբագրման ինտերակտիվ ռեժիմում։

Բնականաբար, գործը սկսվեց ինտերնետում փորփրելուց՝ վերը նշված քայլերը կատարող գործողություների որոնմամբ։ Եվ այսպես․ i) Emacs֊ի բուֆերից՝ խմբագրվող տեքստի տիրույթից տեքստի հատվածը կարելի է վերցնել buffer-substring և buffer-substring-no-properties ֆունկցիաներով։ Սրանցից առաջիննը տեքստը տալիս է ինչ֊որ ատրիբուտների հետ, իսկ երկրորդը՝ առանց ատրիբուտների: ինձ պետք է երկրորդը։ ii) Տեքստը ֆիլտրելու համար նախ պետք է string-to-list ֆունկցիայով նրանից ստանալ ցուցակ, ապա այդ ցուցակից remq ֆունկցիայով հեռացնել ոչ պետքական տարրերը, վերջում էլ ցուցակից նորից ստանալ տող։ iii) Ռեգիոնը բուֆերից հեռացվում է delete-region ֆունկցիայով։ iv) Բուֆերի ընթացիկ կետում (point) տեքստը տեղադրվում է insert ֆունկցիայով։

Իմ գրած remove-region-spaces ֆունկցիան ունի երկու պարամետր՝ նշված տեքստի սկիզբն ու վերջը ցույց տվող ինդեքսները։ Ֆունկցիայի առաջին տողում գրված (interactive "r") արտահայտությունը պահանջում է, որ խմբագրման ինտերակտիվ ռեժիմում այս ֆունկցիան կանչելիս նրան փոխանվեն ռեգիոնի սկիզբն ու վերջը (ավելի ճիշտ՝ mark֊ը և point֊ը)։

(defun remove-region-spaces (begin end)
  (interactive "r")
  (let ((text (buffer-substring-no-properties begin end)))
    (delete-region begin end)
    (insert (apply #'string (remq ?\  (string-to-list text))))))

GNU/Emacs֊ում ստեղնների C-x C-j համադրությունն ազատ է։ remove-region-spaces ֆունկցիան կապում եմ այդ ստեղնների հետ՝ և՛ լատինական և հայերեն տառերի համար։

(global-set-key (kbd "C-x C-j") 'remove-region-spaces)
(global-set-key (kbd "C-ղ C-յ") 'remove-region-spaces)

Այսքանը։ remove-region-spaces ֆունկցիան և այն ստեղնների համադրության հետ կապող արտահայտությունները գրում եմ .emacs ֆայլում, և վերագործարկում եմ խմբագրիչը։

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

Վերջերս ավելի ու ավելի հաճախ եմ լսում այն հարցը, թե ի՛նչ կարդալ կոմպիլյատորների մասին։ Ծրագրավորման լեզուների նախագծման ու իրականացման մասին գրականության պակաս, իհարկե, չկա։ Սա ինֆորմատիկայի և ծրագրավորման այն ոլորտն է, որը թե՛ գիտական, թե՛ գործնական տեսակետից ակտիվորեն ուսումնասիրվել և ուսումնասիրվում է, հրապարակվում են նոր հետազոտություններ, գրվում են նոր գրքեր։ Այս գրառման մեջ ես ուզում եմ առանաձնացնել մի քանի հանրահայտ աշխատանքներ, որոնք իմ գրադարանում զտվել են վերջին 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» գրքին (թեմաներն ու բերված օրինակները բավականին հետաքրքիր են)։

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

Մի քանի օր առաջ Լիլիթն ինձ առաջարկեց գրել միակապ ցուցակը շրջելու ֆունկցիան՝ օգտագործելով ռեկուրսիվ ալգորիթմ։ Առաջին բանը, որ միտքս եկավ՝ թե ինչպես կարելի է դա ան մի այնպիսի լեզվով, որտեղ ցուցակը ներդրված տիպ է, և արդեն առկա են ցուցակի հետ գործողություններ կատարող ֆունկցիաները։ Օրինակ, 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) արտահայտությունները։

Ստրուկտուրաներ 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։ Ստրուկտուրաների սահմանման, դրանց նմուշների ու սլոտների հետ աշխատող պրոցեդուրաները լրացնել (ընդլայնել) սխալների ստուգման մեխանիզմով։