Monday, July 9, 2018

IoT: Էլ-փոստով ղեկավարվող լուսավորություն

Ինչ-որ ժամանակ առաջ պիտի գնայինք գյուղ և Յերեվանի տանը մի քանի օր մարդ չէր լինելու։ Մտքովս անցավ մտածել մի սարքավորում, որը հնարավորություն կտա գյուղից, ինչ-որ եղանակով միացնել տան լույսերը (կամ մի այլ սարք)։ Ինտերնետում բավականին քչփորելով գտա մի քանի եղանակներ, որոնք օգտագործում էին օժանդակ ցանցային ծառայություններ։ Վերջապես, համադրելով մի քանի գաղափարներ, կառուցեցի ստորև նկարագրված սարքա-ծրագրային համակարգը։

Աշխատանքի մեխանիզմն այսպիսինն է. Յերեվանի տանը դրած համակարգիչը, օգտագործում եմ Raspberry Pi 1 Model B Rev. 2, ամեն երկու (կամ 1, կամ 5 և այլն) րոպեն մեկ ստոգում է հատուկ այդ նպատակի համար ստեղծված էլ-փոստը։ Հենց որ ստացվում է նոր նամակ՝ ստուգում նամակի վերնագիրը, որում գրված է կոնկրետ առաջադրանքը, օրինակ, «LIGHT ON» կամ «LIGHT OFF»։ Որպեսզի որևէ օտար մարդ չկարողանա համակարգչին առաջադրանք տալ (նամակ ուղարկել), ստուգվում է նաև ուղարկողի հասցեն (միամիտ ու անհուսալի պաշտպանություն է. կարելի է ու պետք է կատարելագործել)։ Եթե ամեն ինչ սպասվածի պես է, ապա համակարգչի միացված ռելեյի միջոցով, օգտագործում եմ KY-019 մոդուլը, միացվում կամ անջատվում է էլեկտրական սարքը։

Էլ֊փոստը կարդալու համար օգտագործում եմ getmail֊ը, իսկ cron֊ը օգտագործում եմ getmail֊ը երկու րոպեն մեկ աշխատեցնելու համար։ getmail֊ը տեղադրել եմ սովորական եղանակով․

$ sudo apt install -y getmail4

Տեղադրելուց հետո այն պետք է կարգավորել այնպես, որ կարդա իմ էլ֊փոստը։ Դրա համար $HOME պանակում ստեղծում եմ .getmail պանակը, իսկ դրա մեջ էլ getmailrc ֆայլը։ Վերջինս էլ հենց getmail֊ի կարգավորումների ֆայլն է։ Ինձ մոտ այն հետևյալ տեքսի է․

[retriever]
type = SimpleIMAPSSLRetriever
server = imap.yandex.com
port = 993
username = __իմ էլ֊փոստի անունը__
password = __իմ էլ֊փոստի գաղտնաբառը__

[options]
read_all = false
delivered_to = false
received = false

[destination]
type = MDA_external
path = ~/Projects/a5/readanddo.sh

retriever բլոկում getmail֊ը կարգավորվում է կոնկրետ փոստարկղի համար։ Կարծում եմ, որ այդ բլոկի պարամետրերը բացատրելու կարիք չկա․ դրանց անուններն ամեն ինչ ասում են իրենց մասին։

options բլոկի read_all = false պարամետրը նշանակում է, որ պետք չէ ամեն անգամ սերվերից կարդալ բոլոր նամակները, այլ կարդալ միայն նորերը։ Եթե delivered_to և received պարամետրերը դրված են true, ապա ստացված նամակի վերնագրին (header) ավելացվում են համապատասխանաբար «Delivered To:» և «Received:» դաշտերը (սրանց իմաստը չեմ հասկանում, պարզապես false եմ դրել ավելորդություններից խուսափելու համար)։

Ամենակարևորն իմ աշխատանքում destination բլոկն է։ Սրա պարամետրերով են որոշվում, թե ինչ պետք է անել փոստարկղի սերվերից ներբեռնված նամակների հետ։ Իմ դեպքում type = MDA_external պարամետրն ասում է, որ նամակները պետք է մշակվեն արտաքին (ոչ ներդրված) MDA ― mail delivery application ծրագրով։ Ամեն անգամ, հենց որ getmail֊ը սերվերից նոր նամակ է կարդում, այն ուղղարկում է path պարամետրով տրված ծրագր (կամ սկրիպտի) ստանդարտ ներմուծման հոսքին։

Ես գրել եմ readanddo.sh սկրիպտը, որը ստուգում է նամակի «From:» և «Subject:» դաշտերը։ Եթե դրանցում գրված են սպավող արժեքները՝ «From:» դաշտում հրամաններ ուղարկող էլ֊փոստի հասցեն, իսկ «Subject:» դաշտում՝ կոնկրետ հրամանը, ապա Raspberry Pi֊ի GPIO֊ին ուղղարկվում է համապատասխան ազդանշանը։

#!/bin/bash

operation=''
commander=''

while read line
do
    if [[ ${line} =~ ^Subject: ]]
    then
        if [[ ${line} =~ DO:LIGHT:ON ]]
        then
            operation="LIGHT:ON"
        elif [[ ${line} =~ DO:LIGHT:OFF ]]
        then
            operation="LIGHT:OFF"
        fi
    fi

    if [[ ${line} =~ ^From: ]]
    then
        if [[ ${line} =~ __իմ էլ֊փոստի հասցեն__ ]]
        then
            commander=${line}
        fi
    fi
done



if [ -z ${commander} ]
then
    exit 0
fi

if [ -z ${operation} ]
then
    exit 0
fi


gpio -g mode 4 out

if [ ${operation} = "LIGHT:ON" ]
then
    gpio -g write 4 1
    exit 0
elif [ ${operation} = "LIGHT:OFF" ]
then
    gpio -g write 4 0
    exit 0
fi

Ռելեյի KY-019 մոդուլն ունի երեք մուտքային ոտիկներ․ «+», «-» և «S»։ «+»-ը միացնում եմ Raspberry Pi-ի 2֊րդ GPIO֊ին՝ 5v, «-»-ը միացնում եմ 6֊րդ GPIO֊ին՝ GND, իսկ «S»֊ը, որը ղեկավարող ազդանշանն է, միացնում եմ 7-րդ GPIO֊ին (ֆիզիկական համարակալմամբ 7֊րդը BCM համարակալմամբ 4֊րդն է)։

Երբ readanddo.sh սկրիպտը համոզվում է, որ հրամանն ուղարկվել է նախապես որոշված հասցեից, և հրամանի ֆորմատն էլ նախապես որոշվածներից մեկն է, RPi֊ի 4֊րդ GPIO֊ի (BCM համարակալմամբ) ուղղությունը դարձնում է «out».

gpio -g mode 4 out
և այդ GPIO֊ի արժեքը դնում է 0 կամ 1.
gpio -g write 4 1
gpio -g write 4 0

Մնում է միայն սահմանել cron֊ի առաջադրանք, որը երկու րոպեն մեկ կգործարկի getmail ծրագիրը։

* * *

Դժվար թե սա կիրառելի լինի իրական կյանքում։ Կարծում եմ, որ կան տանը մարդու ներկայության իմիտացիայի ավելի լավ միջոցներ։

Friday, July 6, 2018

JavaScript: mapcar-ի ևս մի իրականացման մասին

Չեմ հիշում, թե ինչի համար, բայց ինձ պետք էր JavaScript ծրագրում օգտագործել Common Lisp-ի mapcar ֆունկցիայի պես մի ֆունկցիա։ Մի քիչ դեսուդեն քչփորելուց հետո գտա սա. https://www.npmjs.com/package/mapcar։ Իրականացումից շատ բան չհասկացա ու դրա համար էլ որոշեցի գրել ավելի պարզ տարբերակը։
Ահա այն՝ մանրամասն մեկնաբանություններով.
//
// Ֆայլի անունը. mapcar.js
//

//
// Ֆունկցիայի անունը որոշեցի թողնել նույնը, ինչ որ
// Common Lisp լեզվում է՝ mapcar։
//
// mapcar ֆունկցիան սպասում է մեկ և ավելի արգումենտներ։
// Դրանցից առաջինը կիրառվող ֆունկցիան է, մյուսները՝ վեկտորներ են։
//
var mapcar = function( func, ...args ) {
    // համոզվել, որ առաջին արգումենտը ֆունկցիա է
    if( 'function' !== typeof func ) {
        throw 'mapcar-ի առաջին արգումենտը ֆունկցիա չէ։'
    }

    // համոզվել, որ երկրորդ և հաջորդ արգումենտներում վեկտորներ են.
    if( !args.every(Array.isArray) ) {
        throw 'Ոչ բոլոր արգումենտներն են վեկտոր տիպի։'
    }

    // համոզվել, որ ֆունկցիայի պարամետրերի քանակն ու mapcar-ին
    // տրված արգումենտների քանակները նույնն են
    if( func.length != args.length ) {
        throw 'Ֆունկցիայի պարամետրերի քանակն ու վեկտորների քանակը տարբեր են։'
    }

    // mapcar ֆունկցիայի կիրառման արդյունքը վեկտոր է
    let result = []

    // եթե վեկտորների երկարությունները տարբեր են, ապա mapcar—ի
    // արդյունքը ստացվելու է դրանցից ամենակարճի չափով
    const lengths = args.map((e) => e.length)
    const reslen = Math.min.apply(null, lengths)

    // ցիկլը կատարելով վեկտորներից ամենակարճի տարրերի քանակով...
    for( let i = 0; i < reslen; ++i )  {
        // վերցնել բոլոր վեկտորների i-րդ տարրերը, ...
        const atu = args.map((ev) => ev[i])
        // ֆունկցիան կիրառել դրանց նկատմամբ, ...
        const ri = func.apply(null, atu)
        // արդյունքն ավելացնել result վեկտորում
        result.push(ri)
    }

    // վերադարձնել կառուցված արդյունքը
    return result
}

// տրամադրել այս ֆունկցիան արտաքին աշխարհին
module.exports.mapcar = mapcar

  1. every մեթոդը true է վերադարձնում միայն այն դեպքում, երբ զանգվածի բոլոր տարրերը բավարարում են տրված պրեդիկատին։
  2. map մեթոդը վերադարձնում է զանգված բոլոր տարրերի նկատմամբ տրված ֆունկցիայի կիրառումների արդյունքում ստացված արժեքների վեկտորը։
  3. apply մեթոդը հնարավորություն է տալիս ֆունկցիան կանչել արգումենտների վեկտորով։ Օրինակ, եթե սահմանված է var f = function(x, y, z) { ... } , ապա -ը կարելի է օգտագործել այսպես. f.apply(null, [1, 2, 3])։ Հարմար է այն դեպքում, երբ կանչի արգումենտները դինամիկ են ձևավորվում։


Հիշեցի. mapcar-ն ինձ պետք էր zip-ի նման մի ֆունկցիա իրականացնելու համար։
var zip = function(x, y) {
    return mapcar((a, b) => [a, b], x, y)
}

Sunday, June 3, 2018

JavaScript: Լամբդա լեզվի իրականացում (I)

Փորձեր JavaScript-ի և Node.js-ի հետ

JavaScript-ը հերթական ծրագրավորման լեզուն է, որի ուսումնասիրությամբ որոշեցի զբաղվել վերջին մի քանի շաբաթների հանգստյան օրերին։ Քանի որ ինձ մոտ դեռևս կապակցված պատկերացում չկա WEB տեխնոլոգիաների ու դրանց մեջ նաև JavaScript լեզվի դերի մասին, ես ընտրեցի Node.js®-ը։ Այս ընտրությունը ինձ թույլ է տալիս JavaScript ծրագրերը փորձարկել, աշխատեցնել որպես ինքնուրույն ծրագրեր։

Եվ ինչպես միշտ՝ նոր լեզվի ուսումնասիրությունը սկսում եմ մի որևէ փոքր, ոչ բարդ շարահյուսությամբ լեզվի իրականացումով։ Այս անգամ որպես իրականացվող լեզու ընտրել եմ պարզագույն Լամբդա լեզուն։ Ահա դրա քերականությունը.

expression
    = REAL
    | IDENT
    | '(' expression ')'
    | BUILTIN expression+
    | 'if' expression 'then' expression 'else' expression
    | 'lambda' IDENT+ ':' expression
    | 'apply' expression 'to' expression
    .

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

Շարահյուսական վերլուծություն

Լամբդա լեզվով գրված տեքստի վերլուծության parser.js մոդուլը «արտաքին աշխարհին» տրամադրում է (exports) միակ parse ֆունկցիան։ Վերջինս արգումենտում ստանում է վերլուծվող տեքստը և վերադարձնում է աբստրակտ քերականական ծառը։

Նախ՝ տեքստը տրոհվում է լեքսեմների (lexeme) ցուցակի՝ միաժամանակ ամեն մի լեքսեմին կապելով համապատասխան պիտակը (token)։ Այնուհետև շարահյուսական վերլուծիչը, օգտագործելով լեքսեմների ցուցակը, կառուցում է աբստրակտ քերականական ծառը։

Տեքստը լեքսեմների ցուցակի տրոհող scanOne և scanAll ֆունկցիաները գրել եմ ֆունկցիոնալ մոտեցմամբ։ scanOne ֆունկցիան արգումենտում ստանում է տեքստ, և վերադարձնում է եռյակ՝ տեքստի սկզբից «պոկված» լեքսեմը, դրա պիտակը և տեքստի չտրոհված մասը։ Օրինակ, scanOne('if + a b then a else b') կանչի արժեքն է { token: 'IF', value: 'if', rest: ' + a b then a else b'} օբյեկտը։ Տեքստից ինձ հետաքրքրող մասը պոկում եմ կանոնավոր արտահայտություների օգնությամբ։

Կանոնավոր արտահայտությունները JavaScript-ում կարելի է կառուցել կամ RegExp կոնստրուկտորով, կամ օգտագործել դրանց լիտերալային գրառումները։ Օրինակ, ես իդենտիտիֆիկատորները ճանաչող կանոնավոր արտահայտությունը գրել եմ /^[a-zA-z][0-9a-zA-z]*/ տեսքով։ (Տես ECMAScript ստանդարտի RegExp (Regular Expression) Objects բաժինը, ինչպես նաև MDN Web Docs-ի RegExp բաժինը։)

RegExp օբյեկտի exec մեթոդը փորձում է «ճանաչել» տրված տողը։ Եթե այդ փորձը հաջողվում է, ապա մեթոդը վերադարձնում է արդյունքների զանգվածը, հակառակ դեպքում՝ null։ Քանի որ լեքսեմները միշտ փնտրում եմ տրված տողի սկզբում, ապա exec-ի վերադարձրած զանգվածի առաջին տարրը հենց ինձ հետաքրքրող լեքսեմն է։ Որպես վերադարձվող օբյեկտի value սլոթի արժեք վերցնում եմ այդ առաջին տարրը, իսկ տրված տեքստի սկզբից կտրում ու դեն եմ գցում լեքսեմի երկարությամբ հատված։ «Կտրելը» իրականացրել եմ String օբյեկտի substring մեթոդով։

Ահա scanOne ֆունկցիան՝ համապատասխան մեկնաբանություններով.

// Լեզվի ծառայողական բառերի ցուցակը
const keywords = ['if', 'then', 'else', 'lambda', 'apply', 'to', 'and', 'or']

// Տեքստից կարդալ մեկ (թոքեն, լեքսեմ) զույգ
var scanOne = function(text) {
    // եթե տրված տեքստը դատարկ է, ապա վերադարձնել
    // տեքստի վերջը ցույց տվող օբյեկտ
    if( text == '' ) {
        return { token: 'EOS', value:'EOS', rest: '' }
    }

    // երբ տողը սկսվում է բացատանիշերով, ապա դեն նետել
    // դրանք և նօորից կանչել scanOne ֆունկցիան
    let mc = /^[ \n\t\r]+/.exec(text)
    if( mc != null ) {
        return scanOne(text.substring(mc[0].length))
    }

    // եթե տողը տառով սկսվող տառերի ու թվանշանների հաջորդականություն
    // է, ապա հանդիպել է կամ ծառայողական բառ, կամ էլ իդենտիֆիկատոր։
    // եթե լեքսեմը ծառայողական բառերի keywords ցուցակից է, ապա
    // վերադարձվող օբյեկտի token սլոթիի արժեք որոշվում է այդ բառով,
    // հակառակ դեպքում token-ը ստանում է IDENT արժեքը
    mc = /^[a-zA-z][0-9a-zA-z]*/.exec(text)
    if( mc != null ) {
        return {
            token: keywords.includes(mc[0]) ? mc[0].toUpperCase() : 'IDENT',
            value: mc[0],
            rest: text.substring(mc[0].length)
        }
    }

    // իրական թվեր
    mc = /^[0-9]+(\.[0-9]+)?/.exec(text)
    if( mc != null ) {
        return {
            token: 'REAL',
            value: mc[0],
            rest: text.substring(mc[0].length)
        }
    }

    // ծառայողական սիմվոլներ (մետասիմվոլներ) են խմբավորման
    // փակագծերն ու անանուն ֆունկցիայի պարամետրերը մարմնից
    // անջատող երկու կետը
    mc = /^(\(|\)|:)/.exec(text)
    if( mc != null ) {
        return {
            token: mc[0],
            value: mc[0],
            rest: text.substring(mc[0].length)
        }
    }

    // քանի որ լեզվի քերականությունը ներդրված գործողությունները
    // սահմանում է մեկ արտահայտությամբ, ես որոշեցի, որ թվաբանական
    // ու համեմատման գործողությունների նշաններին համապատասխանեցնել
    // մի ընդհանուր OPER պիտակը
    mc = /^(\+|\-|\*|\/|=|<>|>|>=|<|<=)/.exec(text)
    if( mc != null ) {
        return {
            token: 'OPER',
            value: mc[0],
            rest: text.substring(mc[0].length)
        }
    }

    // եթե տրված տեքստը չի համապատասխանում վերը բերված և ոչ մի
    // կանոնի, վերադարձնում եմ UNKNOWN պիտակով օբյեկտ
    return { token: 'UNKNOWN', value: text[0], rest: text }
}

Իսկ scanAll ֆունկցիան կանչում է scanOne ֆունկցիան այնքան ժամանակ, քանի դեռ հերթական կանչի արդյունքում չի ստացվել token == 'EOS' օբյեկտ։

// Կարդալ բոլոր (թոքեն, լեքսեմ) զույգերն ու վերադարձնել ցուցակ
var scanAll = function(text) {
    let res = []
    let ec = scanOne(text)
    while( ec.token != 'EOS' ) {
        res.push({token: ec.token, value: ec.value})
        ec = scanOne(ec.rest)
    }
    res.push({token: 'EOS', value: 'EOS'})
    return res
}

Այս երկու ֆունկցիաները կազմում են Լամբդա լեզվի բառային վերլուծիչը։ Հիմա՝ շարահյուսական վերլուծության մասին։

parse ֆունկցիան scanAll ֆունկցիայով տրոհում է իր արգումենտում ստացված ծրագիրը և լեքսեմների ցուցակը վերագրում է lexemes գլոբալ զանգվածին։ Ըստ էության այս lexemes-ը լեքսեմներ ստեկ է, որից վերլուծիչը տարրերը դուրս է քաշում (pop) ըստ լեզվի քերականական կանոնների։ index գլոբալ հաշվիչը, որը ծառայում է որպես ստեկկի գագաթի ցուցիչ, ստանում է նախնական 0 արժեքը՝ Լամբդա լեզվի բուն շարահյուսական վերլուծիչն իրականացված է expression ֆունկցիայում. parse ֆունկցիան վերադարձնում է հենց վերջինիս արժեքը։

// (թոքեն, լեքսեմ) զույգերի ցուցակ
var lexemes = []
// ընթացիկ օգտագործվող տարր ինդեքսը
var index = 0;

// ծրագրի տեքստի վերլուծություն
var parse = function(text) {
    lexemes = scanAll(text)
    index = 0
    return expression()
}

Բայց, մինչև expression-ին անցնելը, մի քանի օգնական ֆունկցիաների մասին։ have ֆունկցիան վերադարձնում է true, եթե լեքսեմների ստեկի գագաթի տարրի պիտակը հավասար է արգումենտում տրված պիտակին կամ պիտակներից որևէ մեկին։ Այս ֆունկցիայի արգուենտը կարող է լինել ինչպես առանձին պիտակ, այնպես էլ պիտակների վեկտոր։

// ստուգել ցուցակի ընթացիկ տարրը
var have = function(exp) {
    let head = lexemes[index].token

    if( exp instanceof Array )
        return exp.includes(head)

    return head == exp
}

Հաջորդ, next ֆունկցիան մեկով ավելացնում է լեքսեմների ինդեքսը. մոդելավորում է ստեկի pop գործողությունը՝ դիտարկելի դարձնելով լեքսեմների ցուցակի հաջորդ տարրը։ Բայց վերադարձնում է ստեկից հանված տարրի value սլոթի արժեքը։

// անցնել հաջորդին, և վերադարձնել նախորդի արժեքը
var next = function() {
    return lexemes[index++].value
}

match ֆունկցիան համադրում է have և next ֆունկցիաները. եթե լեքսեմների ցուցակի հերթական դիտարկվող տարրի պիտակը հավասաար է match-ի արգումենտին, ապա դիտարկելի դարձնել հաջորդ տարրը։ Եթե հավասար չէ, ապա ազդարարվում է շարահյուսական սխալի մասին։

// ստուգել և անցնել հաջորդին
var match = function(exp) {
    if( have(exp) )
        return next()
    throw `Syntax error: expected ${exp} but got ${lexemes[index].value}`
}

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

// Լամբդա լեզվի արտահայտությունները կարող են սկսվել միայն հետևյալ
// պիտակներով։ Գրականության մեջ այս բազմությունը կոչվում է FIRST.
// FIRST(expression)
const exprFirst = ['REAL', 'IDENT', '(', 'OPER', 'IF', 'LAMBDA', 'APPLY']

// Արտահայտությունների վերլուծությունը
var expression = function() {
    // եթե դիտարկվող լեքսեմը իրական թիվ է,
    // ապա վերադարձնել AST-ի հանգույց, որի
    // տիպը REAL է
    if( have('REAL') ) {
        let vl = next()
        return { kind: 'REAL', value: parseFloat(vl) }
    }

    // եթե լեքսեմը իդենտիֆիկատոր է, ապա կառուցել
    // փոփոխականի (անուն) հղում ներկայացնող հանգույց
    if( have('IDENT') ) {
        let nm = next()
        return { kind: 'VAR', name: nm }
    }

    // եթե լեքսեմը բացվող փակագիծ է, ապա վերադարձնել
    // փակագծերի ներսում գրված արտահայտության ծառը
    if( have('(') ) {
        next()
        let ex = expression()
        match(')')
        return ex
    }

    // Լամբդա լեզվի օգտագործումը մի քիչ ավելի հեշտացնելու
    // համար ես դրանում ավելացրել եմ ներդրված գործողություններ։
    // դրանք պրեֆիքսային են, ինչպես Լիսպում՝ ցուցակի առաջին
    // տարրը գործողության նիշն է, որը կարող է լինել թվաբանական,
    // համեմատման կամ տրամաբանական գործողություն
    if( have('OPER') ) {
        // վերցնել գործողության նիշը
        let op = next()
        // վերլուծել առաջին արտահայտությունը
        let args = [ expression() ]
        // քանի դեռ հերթական լեքսեմը պատկանում է FIRST(expression)
        // բազմությանը, վերլուծել հաջորդ արտահայտությունը
        while( have(exprFirst) )
            args.push(expression())
        // կառուցել լեզվի ներդրված գործողության հանգույցը
        return { kind: 'BUILTIN', operation: op, arguments: args }
    }

    // պայմանական արտահայտությունը բաղկացած է if, then, else
    // ծառայողական բառերով բաժանված երեք արտահայտություններից
    if( have('IF') ) {
        next()
        // վերլուծել պայմանի արտահայտությունը
        let co = expression()
        match('THEN')
        // վերլուծել պայմանի ճիշտ լինելու դեպքում
        // հաշվարկվող արտահայտությունը
        let de = expression()
        match('ELSE')
        // պայմանի կեղծ լինելու դեպքում հաշվարկվող
        // արտահայտությունը
        let al = expression()
        // պայմանակա արտահայտության հանգույցը
        return { kind: 'IF', condition: co, decision: de, alternative: al }
    }

    // անանուն ֆունկցիայի սահմանումը սկսվում է lambda
    // բառով, որին հաջորդում են ֆունկցիայի պարամետրերը,
    // (ֆունկցիան պիտի ունենա գոնե մեկ պարամետր), հետո,
    // «:» նիշից հետո ֆուկցիայի մարմինն է
    if( have('LAMBDA') ) {
        next()
        // պարամետրերը
        let ps = [ match('IDENT') ]
        while( have('IDENT') )
            ps.push(next())
        match(':')
        // մարմինը
        let by = expression()
        // անանուն ֆունկցիայի հանգույցը
        return { kind: 'LAMBDA', parameters: ps, body: by, captures: [] }
    }

    // apply գործողությունը իրեն հաջորդող արտահայտությունը
    // կիրառում է to բառից հետո գրված արտահայտություններին
    if( have('APPLY') ) {
        next()
        // վերլուծել կիրառելի աարտահայտությունը
        let fn = expression()
        match('TO')
        // վերլուծել արգումենտները
        let args = [ expression() ]
        while( have(exprFirst) )
            args.push(expression())
        // ֆունկցիայի կիրառման հանգույցը
        return { kind: 'APPLY', callee: fn, arguments: args }
    }

    // բոլոր այլ դեպքերում ազդարարել շարահյուսական սխալի մասին
    throw 'Syntax error.'
}

Վերջում նշեմ, որ Լամբդա լեզվի վերլուծիչն իրականացրել եմ ռեկուրսիվ վայրէջքի եղանակով։ Այդ մասին կարելի է կարդալ ծրագրավորման լեզուների իրականացմանը նվիրված ցանկացած գրքում։

Աբստրակտ քերականական ծառը

Լամբդա լեզվով գրված ծրագրի վերլուծության արդյունքում կառուցվում է աբստրակտ քերականական ծառ, որի հանգույցների տեսակը որոշվում է kind սլոթով։ Օրինակ, parse('3.14') կիրառման արդյունքում կառուցվում է { kind: 'REAL', value: 3.14 } օբյեկտը, որի kind սլոթի REAL արժեքը ցույց է տալիս, որ սա իրական թիվ ներկայացնող հանգույց է, իսկ value սլոթի արժեքն էլ թվի մեծությունն է։

Մեկ այլ օրինակ, parse('+ 3.14 x') ծրագրի վերլության արդյունքում կառուցվում է հետևյալ օբյեկտը.

{ kind: 'BUILTIN',
  operation: '+',
  arguments: [ { kind: 'REAL', value: 3.14 }, { kind: 'VAR', name: 'x' } ] }

Այստեղ հանգույցի տեսակը BUILTIN է (լեզվի ներդրված գործողություն), գործողության տեսակը՝ operation, գումարումն է, արգումենտների վեկտորն էլ պարունակում է երկու օբյեկտ՝ առաջինը իրկան թիվ ներկայացնող հանգույց է, իսկ երկրորդը փոփոխականի հղում ներկայացնող հանգույց։

lambda x : * x x լամբդա արտահայտության վերլուծության արդյունքում կառուցվում է մի օբյեկտ, որում kind == 'LAMBDA', պարամետրերի ցուցակը պարունակում է միայն x փոփոխականի անունը, իսկ մարմինը բազմապատկման ներդրված գործողությունը ներկայացնող հանգույց է (captures սլոթի մասին կխոսեմ լամբդա արտահայտությունների ինտերպրետացիայի բաժնում)։

{ kind: 'LAMBDA',
  parameters: [ 'x' ],
  body:
   { kind: 'BUILTIN',
     operation: '*',
     arguments: [ [Object], [Object] ] },
  captures: {} }

Ինտերպրետացիա

Լամբդա ծրագրի վերլուծության արդյունքում կառուցված ծառի ինտերպրետացիայի evaluate ֆունկցիան նույնպես կառուցված է ռեկուրսիվ սխեմայով։ Դր առաջին արգումենտը ծրագրի աբստրակտ քերականական ծառն է, իսկ երկրորդը՝ հաշվարկման միջավայրը։ Վերջինս մի արտապատկերում է (map), որում փոփոխականներին համապատասխանեցված են ընթացիկ արժեքները։ Քանի որ Լամբդա լեզվում վերագրման գործողություն չկա, փոփոխականներին արժեքներ կարող են կապվել ֆունկցիայի պարամետրերի օգնությամբ։

var evaluate = function(expr, env) { /* ... */ }

Ինչպես երևում է expression ֆունկցիայից, վերլուծության արդյուքնում կառուցվում են վեց տեսակի հանգույցներ. REAL, VAR, BUILTIN, IF, LAMBDA և APPLY։ evaluate ֆունկցիայում դիտարկվում են այս վեց դեպքերը։ Հիմա ես հերթով ու հնարավորինս մանրամասն կներկայացնեմ նշված վեց հանգույցների հաշվարկման եղանակները։

REAL տիպի հանգույցի հաշվարկման արդյունքը դրա value սլոթի արժեքն է։

if( expr.kind == 'REAL' ) {
    return expr.value
}

VAR տիպի հանգույցի հաշվարկման արժեքը ստանալու համար միջավայրից վերադարձնում եմ name սլոթին կապված արժեքը։

if( expr.kind == 'VAR' ) {
    return env[expr.name]
}

BUILTIN տիպի հանգույցի արժեքը ստանալու համար պետք է նախ հաշվարկել arguments ցուցակի արտահայտությունների արժեքները, ապա գրանց նկատմամբ կիրառել operation սլոթում գրանցված գործողությունը։

if( expr.kind == 'BUILTIN' ) {
    let evags = expr.arguments.map(e => evaluate(e, env))
    return evags.reduce(builtins[expr.operation])
}

IF տիպի հանգույցը, որ պայմանական արտահայտության մոդելն է, հաշվարկելու համար նախ հաշվարկվում է condition սլոթի արժեքը՝ պայմանը։ Եթե այն տարբեր է 0.0 թվային արժեքից՝ ճշմարիտ է, ապա հաշվարկվում և վերադարձվում է decision սլոթի արժեքը։ Եթե condition-ի արժեքը զրո է, ապա հաշվարկվում ու վերադարձվում է alternative սլոթին կապված արտահայտության արժեքը։

if( expr.kind == 'IF' ) {
    let co = evaluate(expr.condition, env)
    if( co !== 0.0 )
        return evaluate(expr.decision, env)
    return evaluate(expr.alternative, env)
}

LAMBDA տիպի հանգույցի հաշվարկման արդյունքում պիտի կառուցվի մի օբյեկտ, որը կոչվում է closure (չգիտեմ, թե հայերեն սրան ինչ են ասում)։ Իմաստն այն է, որ LAMBDA օբյեկտի captures սլոթում գրանցվում են body սլոթին կապված արտահայտության ազատ փոփոխականների արժեքները՝ հաշվարկված ընթացիկ միջավայրում։ Այս կերպ լրացված LAMBDA օբյեկտն արդեն հնարավոր կլինի apply գործողության կիրառել արգումենտների նկատմամբ։ (Արտահայտության մեջ մտնող ազատ փոփոխականների բազմությունը հաշվարկող freeVariables ֆունկցիայի մասին քիչ ավելի ուշ)։

if( expr.kind == 'LAMBDA' ) {
    let clos = Object.assign({}, expr)
    let fvs = freeVariables(clos)
    for( let v of fvs )
        clos.captures[v] = env[v]
    return clos
}

Մի օրինակ. թող որ տրված է lambda y : + x y արտահայտությունը և { 'x': 7 } հաշվարկման միջավայրը։ Ինչպես արդեն նշեցի վերլուծության մասին պատմելիս, այս տրված ծրագրի վերլուծությունը կառուցելու է այսպիսի մի օբյեկտ.

{ kind: 'LAMBDA',
  parameters: [ 'y' ],
  body:
   { kind: 'BUILTIN',
     operation: '+',
     arguments: [ [Object], [Object] ] },
  captures: {} }

Երբ այս օբյեկտը հաշվարկում եմ { 'x': 7 } միջավայրում, ստանում եմ նույն օբյեկտը, բայց արդեն լրացված captures սլոթով։

{ kind: 'LAMBDA',
  parameters: [ 'y' ],
  body:
   { kind: 'BUILTIN',
     operation: '+',
     arguments: [ [Object], [Object] ] },
  captures: { x: 7 } }

apply f to e0 e1 ... en արտահայտության հաշվարկման սեմանտիկան (իմաստը) f ֆունկցիայի՝ e0 e1 ... en արտահայտությունների նկատմամբ կիրառելն է։ Քանի որ, ըստ Լամբդա լեզվի քերականության, f-ը նույնպես արտահայտությունը է, ապա նախ՝ պետք է հաշվարկել այն և համոզվել, որ ստացվել է կիրառելի օբյեկտ՝ closure (թող դա կոչվի f'), որի captures-ը պարունակում է լամբդայի մարմնի ազատ փոփոխականների արժեքները (bindings)։ Հետո պետք է հաշվարկել APPLY օբյեկտի arguments սլոթին կապված ցուցակի արտահայտությունները՝ կիրառման արգումենտները, ու դրանք ըստ հերթականության կապել closure-ի պարամետրերին։ Եվ վերջապես, f' օբյեկտի մարմինը հաշվարկել մի միջավայրում, որը կառուցված է closure-ի captures-ի և պարամետրերի ու արգումենտների արժեքների համադրումով։ (Էս պարբերությունը ոնց որ մի քիչ լավ չստացվեց։)

if( expr.kind == 'APPLY' ) {
    let clos = evaluate(expr.callee, env)
    if( clos.kind != 'LAMBDA' )
        throw 'Evaluation error.'
    let nenv = Object.assign({}, clos.captures)
    let evags = expr.arguments.map(e => evaluate(e, env))
    let count = Math.min(clos.parameters.length, evags.length)
    for( let k = 0; k < count; ++k )
        nenv[clos.parameters[k]] = evags[k]
    return evaluate(clos.body, nenv)
}

Օգտագործումը

Ամեն մի իրեն հարգող ինտերպրետատոր, առավել ևս՝ ֆունկցիոնալ լեզվի իրականացում, պետք է ունենա այսպես կոչված REPL (read-eval-print loop, կարդալ-հաշվարկել-արտածել-կրկնել)։ Դրա իրականացումը օգտագործողին առաջարկում է ներմուծել արտահայտություն, ապա հաշվարկում է այն և արտածում է արժեքը։ Այս երեք քայլերը կրկնվում են այնքան ժամանակ, քանի դեռ օգտագործողը, ի որևէ հատուկ հրամանով, չի ընդհատում աշխատանքը։

Որպես հրավերք ես ընտրել եմ հունարեն λάμδα բառը, իսկ որպես աշխատանքի ավարտի ազդանշան՝ /// նիշերը։ Օգտագործող-ինտերպրետատոր երկխոսության կազմակերպման համար օգտագործել եմ Node.js®-ի readline գրադարանը: Ստորև բերված repl ֆունկցիայի կոդի մասին շատ մանրամասներ չեմ կարող ասել, որովհետև ինքս էլ նոր եմ ծանոթանում դրան ու փորձում եմ հասկանալ պատահար-ների (event) հետ աշխատանքի սկզբունքները։

var repl = function() {
    var rr = rl.createInterface({
        input: process.stdin,
        output: process.stdout,
        prompt: 'λάμδα> ',
        terminal: false
    });

    rr.prompt()

    rr.on('line', (line) => {
        if( line == 'end' ) {
            rr.close()
            return
        }

        console.info(ev.evaluate(ps.parse(line), {}))
        rr.prompt()
    }).on('close', () => {
        console.info('Bye')
        process.exit(0)
    });
}

Բացի երկխոսության ռեժիմից, Լամբդայի ինտերպրետատորը կարելի է աշխատեցնել նաև հրամանային տողում տալով լամբդա արտահայտությունը պարունակող ֆայլը։ evalFile ֆունկցիայւոմ նախ ստուգում եմ տրված ֆայլի գոյությունը, ապա readFileSync ֆունկցիայով կարդում եմ դրա ամբողջ պարունակությունը։ Հաշվարկումը կատարվում է ճիշտ այնպես, ինչպես REPL-ում ներմուծված տողի հաշվարկը։

var evalFile = function(path) {
  if( !fs.existsSync(path) ) return;

  let prog = fs.readFileSync(path, {encoding: 'utf-8'})
  console.info(ev.evaluate(ps.parse(prog), {}))
}

Աշխատանքային ռեժիմի ընտրությունը կատարվում է հրամանային տողում տրված արգումենտների քանակը ստուգելով։ Եթե process.argv.length > 2, ապա ենթադրում եմ, որ հրամանային տողում տրված է ծրագիրը պարունակող ֆայլ, և կանչվում է evalFile ֆունկցիան։ Հակառակ դեպքում գործարկվում է REPL-ը։

if( process.argv.length > 2 ) {
    evalFile(process.argv[2])
}
else {
    repl()
}

Ընդլայնումներ

Չնայած որ իրականացված լեզուն բավարար է թվային ալգորիթմների իրականացման համար, այնուամենայնիվ այն դեռ բավականին «անհարմար» գործիք է։ Օրինակ, ես կարող եմ սահմանել անանուն ֆունկցիաներ ու դրանք կիրառել արգումենտների (արտահայտությունների) նկատմամբ, ինչպես նաև (երևի թե) կարող եմ ռեկուրսիայի օգնությամբ, օգտագործելով որևէ ֆիքսված կետի կոմբինատոր, գրել կրկնություն պարունակող ալգորիթմներ, և այլն։ Ավելի մանրամասն տես, օրինակ, The Lambda Calculus tanford Encyclopedia of Philosophy էջում։ Բայց, քիչ թե շատ հարմար, ընթեռնելի ու հասկանալի ծրագրեր գրելու համար ինձ պետք է, առաջին հերթին, ունենալ սահմանումների մեխանիզմ։ Հենց թեկուզ հանրահայտ let-ը։ Լամբդա լեզվում այն կարող է ունենալ այսպիսի տեսք.

let
  pi is 3.1415
in
  lambda r : * pi r r

Այստեղ նախ՝ pi սիմվոլին կապվում է 3.1415 արժեքը, ապա՝ let-ի մարմնում pi-ն օգտագործվում է արտահայտության մեջ։

Մի այլ օրինակ։ Թվի ֆակտորիալը հաշվող պապենական ֆունկցիան կարող է սահմանվել հետևյալ կերպ.

let
  fact is lambda n : if (= n 1) then 1 else * n (apply fact to - n 1)
in
  apply fact to 10

Այս դեպքում let կառուցվածքի ինտերպրետացիան պետք է կազմակերպել այնպես, որ ապահովվի ռեկուրսիան՝ սահմանման մեջ պետք է թույլատրվի սահմանվող սիմվոլի օգտագործումը։

Լեզվի մեկ այլ ընդլայնում կարող է լինել նոր տիպերի հետ աշխատանքը. օրինակ, տեքստային տիպ և ցուցակներ։ Հենց թեկուզ այս երկու տիպերը կարող են էապես ընդլայնել Լամբդա լեզվով մոդելավորվող ալգորիթմների շրջանակը։

Վերջ

Վերջ՝ չնայած բոլոր թերություններին ու կիսատ-պռատ իրականացված մասերին։ Մի որոշ ժամանակ անց, երբ ավելի լավ կուսումնասիրեմ JavaScript լեզուն, ես կփորձեմ շտկել պակասող մասերն ու ավելի գրագետ իրականացնել վերլուծիչն ու ինտերպրետատորը։

Աղբյուրներ

Ֆունկցիոնալ լեզվի իրականացման հարցերը քննարկվում են շատ գրքերում ու հոդվածներում։ Ես անհրաժեշտ եմ համարում դրանցից մի քանիսի թվարկումը.

  1. Christian Queinnec, Lisp in Small Pieces, Cambridge University Press, 2003.
  2. Peter Norvig, Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp, Morgan Kaufmann, 1991.
  3. Harold Abelson, Jerald Jay Sussman, Julie Sussman, Structure and Interpretation of Computer Programs, 2nd Edition, MIT Press, 1996.
  4. Peter Norvig, (How to Write a (Lisp) Interpreter (in Python)) և (An ((Even Better) Lisp) Interpreter (in Python)).
  5. John McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I.
  6. Paul Graham, The Roots of Lisp.

Saturday, April 21, 2018

Ալգորիթմական լեզվի մասին

Նախաբան

Անցյալ դարի վերջերին միջնակարգ դպրոցի «Ինֆորմատիկա» առարկան, որի լրիվ անունն էր «Ինֆորմատիկայի և հաշվողական տեխնիկայի հիմունքներ», ամբողջությամբ նվիրված էր ծրագրավորմանը։ Իսկ քանի որ դպրոցների հիմնական մասում հմակարգիչներ չկային, մշակվել էր, ինֆորմատիկայի՝ այսպես կոչված «առանց ԷՀՄ»֊ի դասավանդման եղանակը։ Ալգորիթմական մտածելության ու ծրագրավորման հմտությունների զարգացման համար դասագրքերում օգտագործվում էին կա՛մ բլոկ֊սխեմաները, կա՛մ Ալգորիթմական լեզուն։ Առաջինի մասին երևի գիտեն բոլորը, քանի որ նույնիսկ ժամանակակից դասագրքերում դրանք հադիպում են հիմնականում ծրագրավորման լեզուների ղեկավարող կառուցվածքների նշանակությունը բացատրելու համար (այլ ոչ թե ալգորիթմները ներկայացնելու համար)։

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

ալգ իրկ մեծը(իրկ ա, բ)
  արգ ա, բ
սկիզբ
  եթե ա > բ
    ապա արժեք := ա
    այլապես արժեք := բ
  ավարտ
վերջ

Կամ, օրինակ, ամբողջ թվերի զանգվածում տրված արժեքի գծային որոնման ալգորիթմը կարելի է գրել մոտավորապես այսպես․

ալգ ամբ որոնել(ամբ գ, աղյուսակ տ[0:u], ք)
  արգ գ, տ, ք
սկիզբ
  թող ի սկսած 0 մինչև ք
  ցս
    եթե գ = տ[ի]
      ապա արժեք := ի
    ավարտ
  ցվ
վերջ

Ընդհանուր առմամբ ալգորիթմական լեզուն Ալգոլ (Algol) լեզվից ժառանգված մի գործիք էր՝ հարմարեցված ուսումնական նպատակների, և հատկապես «առանց ԷՀՄ» մոտեցմամբ դասավանդման համար։

Պետք է նշել, որ Մոսկվայի պետական համալսարանում ստեղծվել է ալգորիթմական լեզվի իրականացում՝ ռուսերեն ծառայողական բառերով։ Ոչ միայն իրականացում, այլև բավականին հարուստ ու հետաքրքիր ծրագրավորման միջավայր։ Արդեն XXI դարում, ինչ֊որ փորձեր եղան վերակենդանացնել այդ լեզուն КуМир համակարգի տեսքով, բայց չեմ կարծում, թե դա հառողություն կունենա։ Այսօր արդեն շատ են մեկը մեկից գեղեցիկ ու նորարարական ուսուցողական համակարգերը։ Դժվար թե որևէ մեկն ուզենա ծրագրավորում սովորել Scratch-ից, Python֊ից, Racket֊ից ու այլ ժամանակակից լեզուներից նախընտրելով Ալգորիթմական լեզուն կամ КуМир֊ը։ Ալգորիթմական լեզուն այսօր կարող է ունենալ միայն պատմական նշանակություն։

Ընթացիկ պլաններ

Իմ, այսպես ասած, անհատական զարգացման ծրագում վաղուց նախատեսել էի ուսումնասիրել Ջավա վիրտուալ մեքենայի (JVM) հրամանների համակարգը, ու գրել կոդի գեներատոր՝ որևէ պարզ լեզվի համար։ Սովորաբար որպես լեզու ընտրում եմ BASIC֊ի մի պարզեցված տարատեսակ, որում թողնում եմ մեկ կամ երկու պրիմիտիվ տիպեր, հիմնական ղեկավարող կառուցվածքներն ու ենթածրագրերը։ Այս անգամ հիշեցի Ալգորիթմական լեզվի մասին։ Ու քանի որ, մինչև JVM֊ի համար կոդի գեներատոր գրելը, պիտի գրեի ալգորիթմական լեզվի վերլուծիչ, որոշեցի, ձեռքի հետ, քչփորել նաև ANTLR4 parser generator֊ը։

Այսպիսով՝ ձևակերպվեցին հետևյալ խնդիրները․

  1. Կազմել ալգորիթմական լեզվի ֆորմալ քերականությունը, համոզվել, որ դրա համար հնարավոր է գրել քիչ֊թե շատ խելքը գլխին վերլուծիչ։ Խնդիրը սկզբից ինչ֊որ անհարմարություններ էր խոստանում, քանի որ Ալգորիթմական լեզուն հին դասագրքերում օգտագործված է որպես «թղթի վրայի» լեզու, և դասագիրք գրողներն ու թարգմանողները, կարծես թե, այնքան էլ չեն մտածել լեզվի ֆորմալ կողմի մասին։
  2. ANTLR4 գործիքի օգտագործմամբ գրել շարահյուսական վերլուծիչը։ Չնայած ANTLR4֊ի օգտագործումը շատ մոտ է Bison/Yacc գործիքների օգտագործմանը, այնուամենայնիվ, պետք է ժամանակ տրամադրել առանձնահատկությունները հասկանալու ու դրանց ընտելանալու համար։
  3. Սահմանել աբստրակտ քերականական ծառի հանգույցների դասերի հիերարխիան։ Բնականաբար, այդ դասերը պետք է հարմար լինեն ինչպես ANTLR4֊ի գեներացրած վերլուծիչում օգտագործելու համար, այնպես էլ դրանցից JVM կոդ գեներացնելու համար։
  4. Եվ հիմնականը՝ Apache BCEL գրադարանի օգտագործմամբ վերլուծության ծառից գեներացնել կոռեկտ *.class ֆայլ՝ Ջավա վիրտուալ մեքենայի բայթ֊կոդ։ Այս խնդիրը պիտի ամենաժամանակատարը լինի։
  5. Ամբողջ նախագիծն իրականացնել այնպես, որ այն օգտակար լինի վերը շարադրված նյութով հետաքրքրվողներին։

Քերականության մշակումը

Ալգորիթմական լեզվի քերականությունը կառուցում եմ հիմնականում ըստ հայերեն դասագրքի առաջին ու երկրորդ մասերում բերված օրինակների, երբեմն փորձում եմ հաշվի առնել նաև տեքստում տրված բացատրությունները։ Քերականությունը գրում եմ EBNF գրառմամբ՝ ANTLR4-ում իրականացված տարբերակով։ * ետածանցային (postfix) գործողությունը նշանակում է, որ տարրը կարող է կրկնվել զրո և ավելի անգամներ։ + ետածանցային գործողությունը կրկնությունները սահմանում է մեկ և ավելի անգամների համար։ ? ետածանցային գործողությունը ցույց է տալիս տարրի ոչ պարտադիր առկայությունը (զրո կամ մեկ անգամ)։ ( և ) փակագծերով տարրերը խմբավորվում են, իսկ | գործողությամբ նշվում են այնըտրանքները։ Քերականական կանոնների ոչ տերմինալային սիմվոլները պետք է սկսել փոքրատառով, իսկ տերմինալայինները՝ մեծատառով։ Քերակականական հավասարման ձախ ու աջ մասերն անջատվում են : նիշով, իսկ հավասարումն ավարտվում է ; նիշով։ Այս բաժինը նաև ANTLR4 գործիքի հետ աշխատանքի փորձի կուտակում է։

Սկսում եմ ամենախոշոր միավորից. Ալգորիթմական լեզվով գրված ծրագիրը ալգորիթմների հաջորդականություն է։ Ծրագիրը պարունակող ֆայլի սկզբում կարող են լինել դատարկ տողեր։ Այն տեղերում, որտեղ նոր տողի անցման նիշը պարտադիր չէ, ես օգտագործում եմ NL? գրառումը, իսկ որտեղ որ պարտադիր է՝ NL գրառումը։

grammar Alg0;

program
    : NL? algorithm*
    ;

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

algorithm
    : 'ալգ' scalar? IDENT ('(' (parameter (',' parameter)*)? ')')? NL
      arguments? results?
      'սկիզբ' (declaration (',' declaration)*)? NL statement* 'վերջ' NL
    ;

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

scalar
    : 'տրամ' | 'ամբ' | 'իրկ' | 'տեքստ'
    ;

Պարամետրի նկարագրությունը սկսվում է պրիմիտիվ տիպով, որին հետևում է պարամետրի անունների ցուցակ։

parameter
    : scalar paramName (',' paramName)*
    ;

Պարամետրի անունը կարող է լինել կամ իդենտիֆիկատոր՝ պարզ փոփոխականի անուն, կամ աղյուսակի անուն։ Վերջինս սկսվում է աղյուսակ բառով, դրան հետևում է իդենտիֆիկատոր և աղյուսակի չափողականությունների նկարագրությունը։

paramName
    : IDENT
    | 'աղյուսակ' IDENT '[' range (',' range)? ']'
    ;

range
    : (INTEGER | IDENT) ':' (INTEGER | IDENT)
    ;

Ալգորիթմական լեզուն հնարավորություն է տալիս սահմանել միայն միչափանի ու երկչափանի զանգվածներ՝ վեկտորներ և մատրիցներ։ Եվ հնարավորություն է տալիս նշելու տարրերի ինդեքսների միջակայքը։ Օրինակ, հետևյալը ամբողջ թվերի վեկտոր է, որի տարրերն ինդեքսավորվում են 1..8 թվերով․

ամբ աղյուսակ վ[1:8]

Գրքում բերված օրինակներում աղյուսակի ինդեքսների միջակայքը նշելիս հաստատունի հետ միասին օգտագործված է մի որևէ փոփոխական։ Հավանաբար ենթադրվել է, որ «աղյուսակ» օբյեկտից հնարավոր չի ստանալ ինդեքսների միջակայքը։ Օրինակ․

ալգ ֆ(ամբ N, իրկ աղյուսակ ա[2:N])
...

(Սա ավելորդ բան է ու իրականացման անհարմարություններ է ստեղծելու։ Այս մասը պետք է վերանայել ու ավելի հարմար գրառում մշակել։ Հաշվի առնելով նաև այն փաստը, որ աղյուսակները լինելու են ստատիկ և դրանք մոդելավորելու եմ Ջավայի օբյեկտներով, դրանց մասին ամբողջ ինֆորմացիան հնարավոր է լինելու ստանալ հենց աղյուսակի հղումից։)

Արգումենտների թվարկումը սկսվում է արգ բառով, որին հետևում են պարամետրերի ցուցակում թվարկված այն պարամետրերի անունները, որոնք ալգորիթմին են փոխանցվելու ըստ արժեքի (by value)։ Նոր տողից, արդ բառով սկսվում է արդյունք֊պարամետրերի թվարկում, դրան այնպիսիներն են, որոնք ալգորիթմին են փոխանցվելու հղումով (by reference)։

arguments
    : 'արգ' IDENT (',' IDENT)* NL
    ;

results
    : 'արդ' IDENT (',' IDENT)* NL
    ;

(Սա էլ է երևի ավելորդ բան։ Ռուսերեն ավելի ուշ հրատարակված դասագրքերում արգ ու արդ ծառայողական բառերը գրվում են հենց պարամետրերի ցուցակում՝ տիպից առաջ։)

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

declaration
    : scalar declName (',' declName)*
    ;
    
declName
    : IDENT
    | 'աղյուսակ' IDENT '[' INTEGER ':' INTEGER ']'
    | 'աղյուսակ' IDENT '[' INTEGER ':' INTEGER ',' INTEGER ':' INTEGER ']'
    ;

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

statement
    : assign | branch | condLoop | countLoop | select | algCall
    ;

Վերագրման հրամանը թույլ է տալիս := նշանի աջ կողմում գրված արտահայտությոն արժեքը վերագրել փոփոխականին համ զանգվածի տարրին։

assign
    : place ':=' expression NL
    ;

place
    : IDENT
    | IDENT '[' expression ']'
    | IDENT '[' expression ',' expression ']'
    ;

Ճյուղավորման հրամանը սկսվում է եթե բառով և ավարտվում է ավարտ բառով։ Եթե եթե բառին հաջորդող պայմանը ճիշտ է, ապա կատարվում է ապա բառին հաջորդող հրամանների շարքը։ Հակառակ դեպքում կատարվում են այլապես բառին հաջորդող հրամանները։ Հրամանի այլապես բլոկը կարող է բացակայել։

branch
    : 'եթե' expression NL 'ապա' NL? statement* ('այլապես' NL? statement*)? 'ավարտ' NL
    ;

Պայմանով ցիկլը սկսվում է մինչ բառով, որին հետևում է կրկնման պայմանը։ Այնուհետև, նոր տողից ցս (ցիկլի սկիզբ) և ցվ (ցիկլի վերջ) բառերի միջև գրվում են կրկնվող հրամանները։

condLoop
    : 'մինչ' expression NL 'ցս' NL? statement* 'ցվ' NL
    ;

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

countLoop
    : 'թող' IDENT 'սկսած' expression 'մինչև' expression
      ('քայլ' expression)? NL 'ցս' NL? statement* 'ցվ' NL
    ;

Եվ վերջին հրամանը՝ ալգորիթմի կանչը։ Սա ալգորիթմի անունն է, որին հետևում է արգումենտների ցուցակը։ Արգումենտների ցուցակը կարող է դատարկ լինել կամ բացակայել ընդհանրապես։

algCall
    : IDENT ('(' (expression (',' expression)*) ')')? NL
    ;

Ղեկավարող կառուցվածքների մասին այսքանը ես կարողացա դուրս բերել ձեռքիս տակ եղած օրինակներից։ Առ այս պահը չսահմանված են մնացել միայն արտահայտությունները։ Դասագրքում արտահայտությունների համար հիմնականում օգտագործված է ազատ, մաթեմատիկական գրառումը, սակայն պարզ է, որ ծրագրավորման լեզվի համար դա այնքան էլ հարմար չէ, ու պետք է օգտագործել ընդունված տեքստային գրառում։ Արդյունքում կառուցել եմ արտահայտությունների ստորև բերված քքերականությունը։ Այստեղ թվաբանական, համեմատման, տրամաբանական գործողություններն են, ինչպես նաև զանգվածի տարրին դիմելն ու ֆունկցիայի կանչը։

expression
    : simple
    | '(' expression ')'
    | IDENT '[' expression (',' expression)? ']'
    | IDENT '(' (expression (',' expression)*)? ')'
    | ('ոչ' | '-' | '+') expression
    | <assoc=right> expression '**' expression
    | expression ('*' | '/') expression
    | expression ('+' | '-') expression
    | expression ('>' | '>=' | '<' | '<=') expression
    | expression ('=' | '<>') expression
    | expression 'և' expression
    | expression 'կամ' expression
    ;

ANTLR4֊ը պահանջում է, որ արտահայտությունների քերականության մեջ գործողությունները գրվեն ըստ իրենց նախապատվությունների նվազման։ Այս դեպքում, օրինակ, աստիճան բարձրացնելու ** գործողությունն ամենաբարձր նախապատվություն ունեցող բինար գործողությունն է, իսկ ամնեացածր նախապատվություն ունեցողը տրամաբանական կամ գործողությունն է։ Պետք է նկատել նաև, որ <assoc=right> արտահայտությամ ** գործողության համար սահմանվել է աջ բաշխականություն։ Մյուս բինար գործողությունները ձախ֊բաշխական են։

Արտահայտությունների պարզ դեպքերն առանձնացրել եմ simple կանոնի մեջ։ Այստեղ են տեքստային, իրական ամբողջաթիվ ու տրամաբանական լիտերալները, ինչպես նաև պարզ փոփոխականը (IDENT

simple
    : TEXT
    | REAL
    | INTEGER
    | IDENT
    | 'ճիշտ'
    | 'կեղծ'
    ;

Կարծես թե վերջ։ Հիմաա ANTLR4 գործիքով այս քերականությունից պիտի ստանա Ջավա լեզվով գրված կոդ։

Փորձարկում

Բնականաբար, ես չեմ կարծում, թե հենց առաջին փորձից ամեն ինչ աշխատելու է․ կամ ինչ֊որ բան պակաս եմ գրել, կամ ինչ֊որ բան սխալ եմ հասկացել օրինակներից։ Համոզվելու համար պիտի փորձել։

Եվ այսպես, www.antlr.org կայքից ներբեռնում եմ գործիքի 4.7.1 տարբերակը պարունակող antlr-4.7.1-complete.jar ֆայլը ու առայժմ պատճենում եմ այն նույն պանակում, որտեղ քերականության ֆայլն է։ Ի դեպ, քերականությունը պարունակող ֆայլի անունը պետք է համընկնի grammar հրահանգով տրված անվան հետ (իմ դեպքում դա Alg0 է), իսկ ընդլայնումը պետք է լինի *.g4։

Քայլ առաջին։ Ջավայի միջոցով աշխատեցնում եմ ANTLR4 գործիքը․

$ java -cp .:antlr-4.7.1-complete.jar org.antlr.v4.Tool Alg0.g4

Ու միանգամից ստանում եմ հաղորդագրություններ բացթողումների մասին․

warning(125): Alg0.g4:6:6: implicit definition of token NL in parser
warning(125): Alg0.g4:10:20: implicit definition of token IDENT in parser
warning(125): Alg0.g4:29:7: implicit definition of token INTEGER in parser
warning(125): Alg0.g4:108:6: implicit definition of token TEXT in parser
warning(125): Alg0.g4:109:6: implicit definition of token REAL in parser

Իմաստն այն է, որ քերականության կանոններում օգտագործել եմ NL, IDENT, INTEGER, TEXT և REAL տերմինալային սիմվոլները, բայց դրանց տեսքը չեմ սահմանել։ Վերադառնում եմ Alg0.g4 ֆայլին ու դրա պոչից ավելացնում եմ հետևյալ մի քանի սահմանումները։

Իդենտիֆիկատորը հայերեն կամ լատիներեն փոքրատառով սկսվող և նույն տառերից ու թվանշաններց բաղկացած հաջորդականություն է։

IDENT
    : [ա-ևa-z][ա-ևa-z0-9]*
    ;

Իրական թիվը սահմանել եմ որպես . նիշը պարունակող թվանշանների հաջորդականություն։ Սա, իհարկե, լրիվ սահանումը չէ, բայց տվյալ գործի համար լրիվ հերիք է։

REAL
    : [0-9]+'.'[0-9]+?
    ;

Ամբողջ թիվը պարզապես թվանշանների հաջորդականություն է․

INTEGER
    : [0-9]+
    ;

Տեքստային լիտերալը " չակերտների մեջ առնված նիշերի հաջորդականություն է։ Այն չի կարող պարունակել " նիշը։

TEXT
    : '"'~('"')*'"'
    ;

Ալգորիթմական լեզվում ; նիշն ու նոր տողի անցման նիշը համարժեք են։

NL
    : [\n;]+
    ;

ANTLR4֊ի հետևյալ կանոնն էլ ասում է, որ բացատանիշերի հաջորդականությունը պետք է անտեսել։

WS : [ \t\r]+ -> skip
    ;

ANTLR4 գործիքի հաջորդ գործարկումն արդեն հաջող է անցնում, ու գեներացվում են *.java ֆայլերը, որոնք կարելի է կոմպիլյացնել ու ստանալ *.class ֆայլեր։ (Այդ գեներացված ֆայլերի մեջ են Alg0Lexer.java բառային վերլուծիչը, Alg0Parser.java շարահյուսական վերլուծիչը և այլն։ Դրանք բավականին կոկիկ ու ընթեռնելի ծրագրեր են, հետաքրքրության համար կարելի է բացել ու ուսումնասիրել։)

$ javac -cp .:antlr-4.7.1-complete.jar Alg0*.java

Իսկ ինչպե՞ս ստուգել։ ANTLR4֊ն իր մեջ պարունակում է TestRig կոչված ծրագիրը։ Ես դեռ լավ չեմ հասկանում, թե դա ինչ է, բայց կարող եմ ցույց տալ դրա հետ աշխատելու ձևը։ Բայց նախ պատրաստեմ մի օրինակ (դասագրքից), ու այն գրեմ case02.alg ֆայլում։

ալգ փոքրտարր(ամբ k, n, իրկ աղյուսակ a[k:n], ամբ l)
  արգ k, n, a
  արդ l
սկիզբ ամբ i, իրկ փոքր
  փոքր := a[k]
  l := k
  i := k + 1
  մինչ i <= n
  ցս
    եթե փոքր > a[i]
      ապա 
        փոքր := a[i]
        l := i
    ավարտ
    i := i + 1
  ցվ
վերջ

Հետո աշխատեցնում եմ արդեն TestRig֊ը։

$ java -cp .:antlr-4.7.1-complete.jar org.antlr.v4.gui.TestRig Alg0 program -tree < case02.alg

Հրամանում տրված -tree պարամետրը վերլուծության ծառն արտածում է Լիսպ֊ի ցուցակների տեսքով․

(program \n (algorithm ալգ փոքրտարր ( (parameter (scalar ամբ) (paramName k) , (paramName n)) , (parameter (scalar իրկ) (paramName աղյուսակ a [ (range k : n) ])) , (parameter (scalar ամբ) (paramName l)) ) \n (arguments արգ k , n , a \n) (results արդ l \n) սկիզբ (declaration (scalar ամբ) (declName i)) , (declaration (scalar իրկ) (declName փոքր)) \n (statement (assign (place փոքր) := (expression a [ (expression (simple k)) ]) \n)) (statement (assign (place l) := (expression (simple k)) \n)) (statement (assign (place i) := (expression (expression (simple k)) + (expression (simple 1))) \n)) (statement (condLoop մինչ (expression (expression (simple i)) <= (expression (simple n))) \n ցս \n (statement (branch եթե (expression (expression (simple փոքր)) > (expression a [ (expression (simple i)) ])) \n ապա \n (statement (assign (place փոքր) := (expression a [ (expression (simple i)) ]) \n)) (statement (assign (place l) := (expression (simple i)) \n)) ավարտ \n)) (statement (assign (place i) := (expression (expression (simple i)) + (expression (simple 1))) \n)) ցվ \n)) վերջ \n\n))

TestRig֊ին -tree֊ի փոխարեն -gui տալով վերլուծության ծառը կտեսնենք բացված գրաֆիկական պատուհանում։

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

Բայց այդ մասին, ինչպես ասում է կենդանի դասականը, հաջորդ դասին։

Tuesday, December 19, 2017

Երեք պատահական խնդիր

Արտահայտության հապավում

Խնդիրը։ Տրված է ինչ-որ արտահայտություն, օրինակ, «Միացյալ ազգերի կազմակերպություն» և պահանջվում է սրանից ստանալ «ՄԱԿ» հապավումը։

Դպրոցականը կամ ուսանողը, հավանաբար, առաջին լուծումը կտանի այսպես. տողը դարձնել ցուցակ, հետո անցնել տողի վրայով ու հավաքել բոլոր այն տառերը, որոնց նախորդում են տառ չհանդիսացող այլ սիմվոլներ։ Հետո՝ հավաքած տառերը դարձնել մեծատառ ու միավորել մեկ տողի մեջ։

Տողից նիշերի ցուցակ ստացվում է coerce ֆունկցիայով.

(coerce "abcd" 'list)    ; => (#\a #\b #\c #\d)
Նույն coerce ֆունկցիայով նիշերի ցուցակից ստացվում է տող.
(coerce '(#\a #\b #\c #\d) 'string)    ; => "abcd"

Նիշերի ցուցակից բառերի առաջին տառերն ընտրող ֆունկցիան կարելի է գրել ռեկուրսիվ եղանակով։

(defun select-first-letters (sl)
    (if (endp sl)
        '()
        (if (and (not (alpha-char-p (car sl))) (alpha-char-p (cadr sl)))
            (cons (cadr sl) (select-first-letters (cddr sl)))
            (select-first-letters (cdr sl)))))

Դե իսկ հապավում կառուցող ֆունկցիան արդեն կարելի է կառուցել այսպես․

(defun acronym-of (s)
    (string-upcase (coerce (select-first-letters (coerce s 'list)) 'string)))
Բայց այս ֆունկցիան ճիշտ չի աշխատելու, որովհետև տողի առաջին տառը, որը պետք է լինի հապավման առաջին տառը, չի բավարարում select-first-letters ֆունկցիայի 4֊րդ տողում գրված պայմանին։ Այդ թերությունը շտկելու համար պետք է պարզապես տողը նիշերի ցուցակ դարձնելուց հետո դրա սկզբից կցել մի որևէ նիշ։ Այսինքն acronym-of ֆունկցիան սահմանել հետևյալ կերպ․
(defun acronym-of (s)
    (string-upcase (coerce (select-first-letters (cons #\Space (coerce s 'list)) 'string))))
Սրա հետևանքով select-first-letters ֆունկցիայի երկրերդ տողում գրված պայմանը կձևափոխվի․
(defun select-first-letters (sl)
    (if (or (endp sl) (endp (cdr sl)))
        '()
        (if (and (not (alpha-char-p (car sl))) (alpha-char-p (cadr sl)))
            (cons (cadr sl) (select-first-letters (cddr sl)))
            (select-first-letters (cdr sl)))))

* * *

Փորձառու ծրագրավորողն այսպիսի բան, իհարկե, չի գրի։ Նա միանգամից կնկատի, որ արտահայտության հապավումը կառուցելու համար բավական է մեծատառ դարձնել բառերի միայն առաջին տառերը, իսկ մնացածները թողնել փոքրատառ։ Հետո դեն գցել ամեն ինչ՝ բացի մեծատառերից։

(defun acronym (text)
    (remove-if-not #'upper-case-p (string-capitalize text)))
Սա Արդեն ֆունկցիոնալ լուծում է։ string-capitalize ֆունկցիան վերադարձնում է տողը՝ որում բառերի միայն առաջին տառերն են մեծատառ։ remove-if-not ֆունկցիան ֆիլտրող ֆունկցիա է. այն իր երկրորդ արգումենտում տրված հաջորդականությունից դեն է գցում իր առաջին արգումենտում տրված պրեդիկատին չբավարարող տարրերը։

* * *

Տիպիկ C-ական լուծումն էլ այսպիսին կլինի.

void acronym(const char *text, char *acr)
{
    *acr++ = toupper(*text++);
    while( *text != '\0' ) {
        if( isalpha(*text) && !isalpha(*(text-1)) )
            *acr++ = toupper(*text);
        ++text;
    }
    *acr = '\0';
}


 

Բառերի հեմինգյան հեռավորություն

Խնդիրը։ Երկու նույն երկորությունն ունեցող բառերի հեմինգյան հեռավորություն է կոչվում դրանց նույն դիրքերում տարբերվող տառերի քանակը։ Օրինակ, abc և abc բառերի հեմինգյան հեռավորությունը զրո է, իսկ abc և aec բառերի հեմինգյան հեռավորությունը մեկ է, և այլն։

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

(defun hamming-distance (so si)
    (loop for x across so
          for y across si
          when (char-not-equal x y)
          sum 1))

Ֆունկցիոնալ լուծման առաջին մոտարկումը կարող է լինել այսպես. map ֆունկցիայով տրված բառերից կառուցվում է մի ցուցակ, որի i-րդ դիրքում գրված է 0` եթե բառերի i-րդ դիրքերի տառերը հավասար են, և 1՝ հակառակ դեպքում։ Այնուհետև apply ֆունկցիայով + գործողությունը կիրառվում է այդ ցուցակի նկատմամբ՝ վերադարձնելով տարբերվող տառերի քանակը։

(defun hamming-distance (so si)
    (apply #'+ (map 'list #'(lambda (x y) (if (char-equal x y) 0 1))
           so si)))

Վերջնական ֆունկցիոնալ լուծումն ավելի լավն է. նույն map ֆունկցիայով ստեղծվում է char-not-equal ֆունկցիայի արդյունքների ցուցակ՝ կազմված t-երից և nil-երից։ Իսկ հետո count ֆունցիայով հաշվվում է t-երի քանակը, որն էլ հենց տրված բառերի հեմինգյան հեռավորությունն է։

(defun hamming-distance (so si)
    (count t (map 'list #'char-not-equal so si)))

* * *

C-ական իրականացումը պարզապես հաշվում է բառերի նույն դիրքում տարբերվող տառերի քանակը.

unsigned int hamming_distance(const char *so, const char *si)
{
    unsigned int dist = 0;
    while( *so != '\0' && *si != '\0' )
        if( *so++ != *si++ )
            ++dist;
            
    return dist;
}


 

Ենթացուցակի ստուգում

Խնդիրը։ Ստուգել, թե արդյոք s0 ցուցակը s1 ցուցակի ենթացուցակն է։ Օրինակ, [3, 4, 5] ցուցակը [1, 2, 3, 4, 5, 6] ցուցակի ենթացուցակ է։

Միանգամից «ֆունկցիոնալ» լուծումը. s0s1-ի ենթացուցակ է, եթե կա՛մ s0-ն համընկնում է s1-ի սկիզբի հետ՝ նրա պրեֆիքսն է, կա՛մ s0s1-ի պոչի ենթացուցակն է։

Common Lisp լեզվով գրառումը.

(defun is-sublist (so si)
    (or (is-prefix so si)
        (is-sublist so (cdr si))))

is-prefix ֆունկցիայի իրականացումն էլ շատ հետաքրքիր է.

(defun is-prefix (so si)
    (not (member nil (mapcar #'eq so si))))
mapcar ֆունկցիայով կառուցվում է երկու ցուցակների համապատասխան տարրերի՝ իրար հավասար լինելու (կամ չլինելու) ցուցակը։ member ֆունկցիայով այդ ցուցակում որոնվում է որևէ nil արժեք, իսկ not ֆունկցիայով էլ պահանջվում է, որ nil չլինի։

C լեզվով պրեֆիքսի և ենթացուցակի ստուգման ֆունկցիաները կունենան հետևյալ ոչ պակաս հետաքրքիր տեսքը.

Եթե, օրինակ, ցուցակի հանգույցը սահմանված է այսպես.

struct node {
    char data;
    struct node *next; 
};

ապա s ցուցակի՝ l ցուցակի պրեֆիքս լինելը կաստուգվի այսպես.

bool is_prefix(const struct node *s, const struct node *l)
{
    while( NULL != s && NULL != l && s->data == l->data ) {
        s = s->next;
        l = l->next;
    }
    
    return NULL == s;
}

իսկ s ցուցակի՝ l ցուցակի ենթացուցակ լինելն էլ այսպես.

bool is_sublist(const struct node *s, const struct node *l)
{
    if( NULL == s )
        return true;

    if( NULL == l )
        return false;

    return is_prefix(s, l) || is_sublist(s, l->next);
}

Tuesday, December 13, 2016

Միակապ ցուցակի կարգավորումը (Insertion sort)

Վերջերս մի հարցազրույցի ժամանակ խնդիր առաջադրվեց C լեզվով իրականացնել միակապ ցուցակի (singly linked list) կարգավորման ալգորիթմը՝ անպայման ռեկուրսիայի օգտագործմամբ։ Ես ընտրեցի տեղադրումով կարգավորման (insertion sort) մեթոդը։ Ստորև ներկայացնում եմ դա։

Նախ՝ ցուցակի հանգույցի (node) սահմանումը, որտեղ բանալին double տիպի է․
typedef struct _node node;
struct _node {
    double data; /* բանալի */
    node* next;  /* կապ */
};
Հիմա տեղադրումով կարգավորման մասին։ Ալգորիթմի էությունն այն է, որ ամեն մի քայլում հերթական տարրը (իմ դեպքում՝ հանգույցը) տեղադրվում է իր ճիշտ տեղում։ Բնականաբար բուն տեղադրման գործողությունը կարևոր գործողություն է։ Սահմանում եմ insert_into() ֆունկցիան, որը տրված հանգույցը տեղադրում է տրված ցուցակի իր ճիշտ տեղում և վերադարձնում է ձևաձոխված ցուցակը։
node* insert_into( node* n, node* l )
{
    /* եթե ցուցակը դատարկ է, ապա տրված հանգույցը 
       վերադարձնել որպես կարգավորված ցուցակ */
    if( NULL == l ) {
        n->next = NULL;
        return n;
    }

    /* եթե տրված հանգույցի բանալին փոքր է տրված ցուցակի 
       առաջին հանգույցի բանալու արժեքից, ապա տրված 
       հանգույցը կցել ցուցակի սկզբից */
    if( n->data <= l->data ) {
        n->next = l;
        return n;
    }

    /* ռեկուրսիվ կանչով տրված հանգույցը տեղադրել ցոցակի 
       պոչի մեջ, ապա նախնական ցուցակի առաջին հանգույցը 
       կապել ձևափոխված պոչին */
    l->next = insert_into(n, l->next);
    return l;
}
Ցուցակը կարգավորող sort_list() ֆունկցիան պարզապես կանչում է insert_into() ֆունկցիան․
node* sort_list( node* l )
{
    /* ցուցակը դատարկ լինելու դեպքը */
    if( NULL == l )
        return NULL;

    /* ցուցակի առաջին հանգույցը տեղադրել կարգավորված 
       պոչի մեջ՝ ճիշտ տեղում */
    return insert_into(l, sort_list(l->next));
}
Այսքանը։