Sunday, July 12, 2020

Haskell: Օր առաջին. Ֆակտորիալ

Այս կիրակի ես վերջապես որոշեցի սկսել ծանոթությունը Haskell լեզվի հետ։ Haskel-ը ֆունկցիանալ լեզու է. երբեմն ասում են, որ այն ֆունկցիոնալների մեջ ամենաֆունկցիոնալն է։ Ես, ինչ-որ տարրական պատկերացում ունենալով ֆունկցիոնալ ծրագրավորման մասին, ինձ համար սահմանեցի հետևյալ առաջին խնդիրը.

Ֆակտորիալ։ Գրել ծրագիր, որ հրամանային տողից ստանում է որևէ դրական ամբողջ թիվ, ապա հաշվարկում և արտածում է այդ թվի ֆակտորիալը։

Բայց, մինչև խնդրի լուծմանն անցնելը, ես պիտի պատրաստեմ Haskell լեզվի միջավայրը, որում աշխատեցնելու եմ իմ գրած ծրագրերը։ Կարելի է, իհարկե, օգտագործել որևէ առցանց ծառայություն, ինչպիսիք են, օրինակ, www.tutorialspoint.com-ը կամ https://repl.it-ը, բայց ես նախընտրում եմ ամեն ինչ ունենալ ձեռքի տակ՝ իմ մեքենայի վրա։

Իսկ իմ մեքենան Raspberry Pi է` Debian-ի հիման վրա կառուցված օպերացիոն համակարգով։ Haskell Platformէջից գտա, թե ինչպես է պետք տեղադրել Haskell-ի կոմպիլյատորն ու ինտերպրետատորը.

$ sudo apt-get install haskell-platform

Haskel Platform-ի կոմպիլյատորի և ինտերպրետատորի հաջող տեղադրված լինելը ստուգելու համար նախ հրամանային տողից աշխատեցեմ ghci ինտերպրետատորը.

$ ghci
GHCi, version 8.4.4: http://www.haskell.org/ghc/  :? for help
Prelude>

Հրավերքի տողում Prelude ցույց է տալիս, որ ինտերպրետատորը գործարկվել է և ակտիվ է Prelude փաթեթը։ Խնդրեմ Հասկելին ցույց տալ π թվի արժեքը.

Prelude> pi
3.141592653589793

Կարծես թե աշխատում է։ Փորձեմ հենց այստեղ սահմանել ֆակտորիալը հաշվող ֆունկցիան՝ ամենապարզ մոտեցմամբ.

Prelude> factorial n = if n == 1 then 1 else n * factorial (n - 1)

Մի քանի օրինակներով համոզվեմ, որ սահմանած ֆունկցիան աշխատում է.

Prelude> factorial 1
1
Prelude> factorial 5
120
Prelude> factorial 10
3628800
Prelude> factorial 100
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Հիմա այս ֆունկցիան գրեմ մի ֆայլի մեջ, օրինակ, ex0.hs անունով, ու փորձեմ այդ ֆայլը թարգմանել Հասկելի կոմպիլյատորով։

-- Իմ առաջին ծրագիրը

factorial :: Integer -> Integer
factorial n = if n == 1 then 1 else n * factorial (n - 1)

Այստեղ ֆունկցիայի սահմանումից առաջ ավելացրել եմ նաև դրա վերնագիրը (կամ նկարագրությունը)։ Այդ նկարագրությամբ տրվում է ֆունկցիայի տիպը. :: սիմվոլից ձախ գրված է ֆունկցիայի անունը՝ factorial, իսկ աջ կողմում՝ արգումենտի ու վերադարձվող արժեքի տիպերը։ Այսինքն՝ ֆունկցիան ստանում է Integer տիպի արգումենտ և վերադարձնում է Integer տիպի արժեք։ Երկրորդ տողում հենց ֆունկցիայի սահմանումն է. = սիմվոլից ձախ ֆունկցիայի անունն ու արգումենտն է, իսկ աջ կողմում՝ մարմինը, որը տվյալ դեպքում պարզ ճյուղավորման արտահայտություն է։

Haskell Platform-ում կոմպիլյատորը ghc—ն է։ Աշխատեցնում եմ՝ մուտքին տալով ex0.hs ֆայլը.

$ ghc ex0.hs
[1 of 1] Compiling Main             ( ex0.hs, ex0.o )

ex0.hs:1:1: error:
    The IO action ‘main’ is not defined in module ‘Main’
  |
1 |
  | ^

Սխալի հաղորդագրությունն ասում է, որ Main մոդուլում սահմանված չէ main գործողությունը։ Բանից պարզվում է, որ Հասկելի կոմպիլյատորը նույնպես (ինչպես, օրինակ, Սի լեզվի կոմպիլյատորը) որպես մուտքի կետ է համարում main գործողությունը։ Հիմա ex0.hs ֆայլում ավելացնում եմ main գործողությունն այնպես, որ այն արտածի 12-ի ֆակտորիալը.

-- Իմ առաջին ծրագիրը
factorial n = if n == 1 then 1 else n * factorial (n - 1)

-- Մուտքի կետը
main =
    print (factorial 12)

Նորից փորձեմ թարգմանել։ Ի դեպ, Հասկել լզվում -- սիմվոլով սկսվում են մեկնաբանությունները։

$ ghc ex0.hs
[1 of 1] Compiling Main             ( ex0.hs, ex0.o )
Linking ex0 ...

Արդեն ամեն ինչ լավ է։ Իմ գրած ծրագիրը թարգմանվեց (compile), կապակցվեց (link), և հիմա կարող եմ աշխատեցնել ու տեսնել արդյունքը.

$ ./ex0
479001600

Բայց այս ծրագիրը կարողանում է հաշվել ու տպել միայն 12-ի ֆակտորիալը։ Իսկ ես ուզում եմ, որ այն կարողանա հաշվել հրամանային տողում տրված թվի ֆակտորիալը։ ՄԻ քիչ քչփորելուց հետո պարզեցի, որ Հասկել ծրագրում գրամանային տողի պարամետրերը կարելի է վերցնել System.Environment մոդուլի getArgs գործողությամբ։ Օրինակ, հետևյալ ծրագիրը (գրառված ex1.hs ֆայլում) արտածում է հրամանային տողում տրված պարամետրերի ցուցակը.

-- Հրամանային տողի պարամետրերի ցուցադրություն

import System.Environment

main = do
    args <- getArgs
    print args

Ահա թարգմանության ու կատարման մի քանի օրինակ.

$ ./ex1
[]
$ ./ex1 a
["a"]
$ ./ex1 a bb
["a","bb"]
$ ./ex1 a bb ccc
["a","bb","ccc"]
$ ./ex1 1 22 333
["1","22","333"]

Այստեղից երևում է, որ հրամանային տողի պարամետրերը ծրագրում երևում են տեքստային արժեքների ցուցակի տեսքով։ Ես պետք է թվի տեքստային ներկայացումից ստանամ դրա թվային արժեքը, ապա այդ արժեքի նկատմամբ կիրառեմ factorial ֆունկցիան:

Հասկելի read ֆուկցիան տեքսից «կարդում» է որևէ տիպի արժեք։ Այդ տիպը տրվում է ֆունկցիայի կանչի հետ՝ :: սիմվոլոլից հետո։ Օրինակ, «read "12" :: Int» արտահայտությունը "12" տողից կարդում է Int տիպի 12 արժեքը։ «read "12" :: Float» արտահայտությունը նույն տողից կարդում է 12.0 արժեքը՝ Float տիպի։

Այսպիսով, ես պետք է վերցնեմ հրամանային տողի պարամետրերի ցուցակի առաջին տարրը (head ֆունկցիայիով), դրա նկատմամբ կիրառեմ read ֆունկցիան՝ Integer տիպի համար, ստացված արժեքի նկատմամբ կիրառեմ factorial-ը ու տպեմ ստացված արժեքը։ Ահա այսպիսի մի արտահայտություն main ֆունկցիայում.

print (factorial (read (head args) :: Integer))

Ձևափոխված ex0.hs ծրագիրը կունենա հետևյալ վերջնական տեսքը.

import System.Environment

-- Ֆակտորիալի հաշվարկը
factorial :: Integer -> Integer
factorial n = 
    if n == 1 
    then 1
    else n * factorial (n - 1)

-- Մուտքի կետ
main :: IO ()
main = do
    args <- getArgs
    print (factorial (read (head args) :: Integer))

Լավ. տեսնենք, թե սա ինչպես է աշխատում։

$ ghc ex0.hs
[1 of 1] Compiling Main             ( ex0.hs, ex0.o )
Linking ex0 ...
$ ./ex0 2
2
$ ./ex0 12
479001600
$ ./ex0 20
2432902008176640000
$ ./ex0 40
815915283247897734345611269596115894272000000000

Լավ էլ աշխատում է։ Բայց, իհարկե, թերություններ կան։ Առաջին թերությունը տեխնիկական է. դիտարկված չէ այն դեպքը, երբ հրամանային տողում ոչինչ տրված չէ։ Օրինակ, եթե աշխատեցնեմ ծրագիրը՝ հրամանային տողում ոչինչ չտալով, ապա կստանամ հաղորդագրություն այն մասին, որ head ֆունկցիային տրված է դատարկ ցուցակ.

$ ./ex0
ex0: Prelude.head: empty list

Սա պետք է ուղղել՝ main գործողության մեջ պայման գրելով։ Այսպես.

main = do
    args <- getArgs
    if not (null args)
    then print (factorial (read (head args) :: Integer))
    else putStrLn "Ոչինչ տրված չէ։"

Հիմա եթե ծրագիրն աշխատեցնեմ դատարկ հրամանային տողով, ապա որպես պատասխան կստանամ «Ոչինչ տրված չէ։»։

Հաջորդիվ. թերևս Հասկել լեզվով գրող ոչ մի ծրագրավորող թվի ֆակտորիալը հաշվող ֆունկցիան չի գրի այնպես, ինչպես ես գրել եմ։ Վարպետ Հասկել-ծրագրավորողը պարզապես կգրի.

factorial :: Integer -> Integer
factorial n = product [1 .. n]

Եվ վերջ։ Այստեղ գրված է ֆակտորիալի բառացի սահմանումը՝ այն 1-ից n թվերի ([1 .. n]) արտադրյալն է (product):

Monday, April 6, 2020

Գրաֆի գագաթների տոպոլոգիական թվարկման մասին

Նախ նկարագրեմ ուղղորդված գրաֆի (directed graph, digraph) մոդելը որպես digraph դասի կաղապար։ Այս կաղապարի պարամետրն այն տիպն է, որ նմուշը գրառվելու է գրավի գագաթում։ Այդ տիպի վրա դրված մակ պահանջն այն է, որ նրա համար սահմանված լինի հավասարության ստուգման == գործողությունը։ Այդ գործողությունն օգտագործելու եմ տրված տվյալը պարունակող գագաթի ինդեքսը որոնելու համար։
template<typename Y>
class digraph {
    /// ...
};
Գրաֆի ներքին ներկայացման համար ընտրել եմ գագաթների հարևանության ցուցակների եղանակը։ Գագաթները հերթականությամբ ավելացնում եմ միաչափ զանգվածում (vector): Իսկ ամեն մի գագաթի (vertex) համապատասխանեցնում եմ նրան հարևան գագաթների ինդեքսների ցուցակը։ Քանի որ որոշել եմ գագաթում գրառել կաղապարի պարամետրով տրված ցանկացած տիպի օբյեկտ, մի գագաթի նկարագրությունը սահմանել եմ vertex տիպով.
using index = int;
using index_list = std::vector<index>;
using vertex = std::pair<Y,index_list>;
Դե իսկ գրաֆի գագաթների ցուցակն էլ արդեն կսահմանեմ հետևյալ կերպ.
std::vector<vertex> _vertices;
Գրաֆը կառուցելու եմ կողերը հաջորդաբար ավելացնելով։ add_edge մեթոդը ստանում է կաղապարի Y տիպի երկու արժեք և գրաֆում կոդ է ավելացնում այդ արժեքները պարունակող գագաթների միջև։ Եթե այդպիսի գագաթներ դեռ չկան, ապա գրաֆում ավելացնում է նաև գագաթները։
void add_vertex(const Y& u, const Y& v)
{
    auto ui = add_vertex(u);
    auto vi = add_vertex(v);
    _vertices[ui].second.push_back(vi);
}
Այստեղ օգտագործված add_vertex մեթոդը գրաֆում ավելացնում է տրված արժեքը պարունակող գագաթ։ Եթե այդպիսին արդեն կա, ապա վերադարձնում է դրա ինդեքսը։
index add_vertex(const Y& v)
{
    // որոնել
    for( index ix = 0; ix < _vertices.size(); ++ix )
        if( _vertices[ix].first == v )
            return ix;

    // ավելացնել
    _vertices.push_back(v, {});
    return _vertices.size() - 1;
}
Այսքանը լրիվ հերիք է գրաֆի կառուցման համար։ Թերևս կարելի է ավելացնել to_string մեթոդը, որը կվերադարձնի գրաֆի ինչ-որ տեքստային ներկայացում. պարզապես շտկումների համար։
std::string to_string()
{
    std::ostringstream oss;
    for( auto& e : _vertices ) {
        oss << e.first << " -> { ";
        for( auto& i : e.second )
            oss << _vertices[i].first << ' ';
        oss << '}' << std::endl;
    }
    return oss.str();
}
Այս մեթոդը պահանջում է, որ կաղապարի Y տիպի համար սահմանված լինի արտածման հոսքի մեջ ուղարկելու գործողությունը՝ operator<<։ Անցնեմ գրաֆի գագաթների տոպոլոգիական թվարկման իրականացմանը։ Տոպոլոգիական կարգավորման մասին բան չեմ գրի. կարելի է կարդալ, օրինակ, Ուիքիփեդիայի Topological Sorting էջը։ Միայն ասեմ, որ իրականացման համար ընտրել եմ Kahn-ի ալգորիթմը։ Մի քանի բառով դրա էությունը հետևյալն է. ամենասկզբում ստեկի մեջ են ավելացնում (push) բոլոր այն գագաթները, որոնք նախորդող չունեն (աղեղները դրանցից միայն դուրս են գալիս)։ Այնուհետև, քանի դեռ ստեկը դատարկ չէ, ստեկից հանում ենք u գագաթը, ապա գրաֆից հեռացնում ենք (pop) u գագաթից դուրս եկող բոլոր կողերը։ Եթե այս գործողության արդյունքում հայտնվում է գագաթ, որը դեպի իրեն եկող կող չունի, ապա այդ գագաթն ավելացնում ենք (push) ստեկում։ Քանի որ գրաֆից կող հեռացնելը կվնասեր մեր սկզբնական գրաֆը, այդ «կող հեռացնել» գործողությունը մոդելավորվում է մի վեկտորով, որում ամեն մի գագաթի համար պահվում է դեպի իրեն եկող կողերի քանակը։ Գրաֆի գագաթների՝ տոպոլոգիական կարգով թվարկումը իրականացրել եմ enumerate մեթոդում, որի պարամետրը ֆունկցիա է։ Այս ֆունկցիայով տրվում է այն գործողությունը, որը պետք է կատարվի գրաֆի թվարկվող հերթական գագաթի հետ։ Ավելի մանրամասն՝ մեկնաբանություններում.
void enumerate(std::function f)
{
    // գրաֆի գագաթների քանակը
    const std::size_t sz = _vertices.size();

    // degrees զանգվածում գրաֆի ամեն մի գագաթի համար
    // հաշվում ենք դեպի այն եկող կողերի քանակը
    std::vector<std::size_t> degrees(sz);
    for( auto& e : _vertices )
        for( auto& n : e.second )
            degrees[n] += 1;

    // նախապես S ստեկում ավելացնում ենք այն գագաթները,
    // որոնք նախորդող չունեն
    std::stack<index> S;
    for( std::size_t i = 0; i < degrees.size(); ++i )
        if( degrees[i] == 0 )
            S.push(i);

    // իտերացիա գագաթներով
    while( !S.empty() ) { // քանի դեռ ստեկը դատարկ չէ
        // վերցնել գագաթի տարրը
        index ix = S.top();
        S.pop();

        // տրված գործողությունը կատարել գագաթում գրառված
        // տվյալների հետ
        f(_vertices[ix].first);

        // դիտարկվող գագաթի բոլոր հարևանների համար...
        for( auto& vi : _vertices[ix].second ) {
            // ... եթե այդ հարևանը նախորդոնղեր չունի, ապա
            // այն արդեն մասնակցել է թվարկմանը, ...
            if( degrees[vi] == 0 )
                continue;

            // «կողը հեռացնելու» գործողության մոդելը.
            // պակասեցնում ենք հաշվիչը, ...
            degrees[vi] -= 1;
            // ... եթե հաշվիչը դառնում է զրո, ապա այդ գագաթը
            // ավելացնում ենք ստեկում
            if( degrees[vi] == 0 )
                S.push(vi);
        }
    }
}
Փորձարկենք ալգորիթմը ստորև բերված գրաֆի վրա՝ որպես թվարկման գործողություն տալով պարզապես գագաթի պարունակությունը տպող որևէ ֆունկցիա։
Սահմանում եմ գրաֆ, դրանում ավելացնում եմ նկարի գրաֆի կողերը, հետո to_string մեթոդով տպում եմ գրաֆի տեքստային ներկայացումը։ Թեսթավորման համար պարզապես ուզում եմ տպել գագաթները տոպոլոգիական կարգով։ Դրա համար enumerate մեթոդի արգումենտում տալիս եմ լամբդա-ֆունկցիա, որը պարզապես արտածում է իր արգումենտը։
int main()
{
    graphs::digraph<std::string> g0;
    g0.add_edge("a", "q0");
    g0.add_edge("b", "q0");
    g0.add_edge("b", "q1");
    g0.add_edge("c", "q1");
    g0.add_edge("q0", "x");
    g0.add_edge("q1", "x");
    g0.add_edge("q0", "y");
    g0.add_edge("q1", "y");

    std::cout << "Graph: " << std::endl << g0.to_string() << std::endl;

    std::cout << "Topological order of vertices: " << std::endl;
    g0.enumerate([&](auto& s) {std::cout << s << ' '; });
}
Կատարման արդյունքում արտածվում է հետևյալը.
Graph:
a -> { q0 }
q0 -> { x y }
b -> { q0 q1 }
q1 -> { x y }
c -> { q1 }
x -> { }
y -> { }

Topological order of vertices:
c b q1 a q0 y x
Լավ է։ Բայց ես ուզում եմ գրաֆի համար իրականացնել նրա գանաթերը տոպոլոգիական կարգով թվարկող իտերատոր. այնպիսին, ինչպիսիք սահմանված են STL-ում։ Այդ տիպի իտերատորի առկայության դեպքում կարող եմ գրել այսպիսի կոդ.
for( auto& v : g0 )
    std::cout << v << ' ';
Պարզ է, որ այդ իտերատորի մեթոդների իրականացումը պետք է արտացոլի նույն enumerate մեթոդի վարքը։ digraph դասում սահմանում եմ ներդրված iterator դասը։ range-for-ի աշխատանքն ապահովելու համար իտերատորում պետք է իրականացնել operator*, operator++ և operator!= գործողությունները։ Իտերատորի կոնստրուկտորում հաշվարկվում են բոլոր գագաթների մուտքային կիսաաստիճանները՝ տվյալ գագաթին ուղղված կողերի քանակը, ապա ստեկի մեջ են ավելացվում այն գագաթների ինդեքսները, դեպի որոնց եկող կողեր չկան։ operator*-ը վերադարձնում է հղում հերթական գագաթում գրառված տվյալին։ operator++-ը իտերատորը փոխանցում է հաջորդ գագաթին։ operator!=-ը համեմատում է երկու իտերատորների հերթական գագաթները։ Նորից՝ մանրամասները կոդի մեկնաբանություններում։
template
class digraph {
    // ...
    public:
        class iterator {
        public:
            using iterator_category = std::forward_iterator_tag;
            using value_type = Y;

            //
            iterator(const digraph& g, bool init)
                : _ref{g}
            {
                if( init ) {
                    // հաշվարկվում են մուտքային կիսաաստիճանները
                    _degrees.resize(_ref._vertices.size());
                    for( auto& e : _ref._vertices )
                        for( auto& n : e.second )
                            _degrees[n] += 1;

                    // ստեկում ավելացնել բոլոր «սկզբնական» գագաթների ինդեքսները
                    for( std::size_t i = 0; i < _degrees.size(); ++i )
                        if( _degrees[i] == 0 )
                            _S.push(i);

                    // կատարել առաջին քայլը՝ արժեքավորել դիտարկվող գագաթի ինդեքսը
                    this->operator++();
                }
            }

            //
            iterator& operator++()
            {
                // եթե ստեկը դատարկ չէ, ապա անցնել հերթական գագաթին, հակառակ
                // դեպքում հերթական գագաթի ինդեքսին վերագրել -1
                if( !_S.empty() ) {
                    _current = _S.top();
                    _S.pop();

                    for( auto& vi : _ref._vertices[_current].second ) {
                        if( _degrees[vi] == 0 )
                            continue;

                        _degrees[vi] -= 1;
                        if( _degrees[vi] == 0 )
                            _S.push(vi);
                    }
                }
                else
                    _current = -1;

                return *this;
            }

            //
            bool operator!=(const iterator& other)
            {
                // համեմատել երկու իտերատորներում ընթացիկ գագաթի ինդեքսը
                return _current != other._current;
            }

            //
            const value_type& operator*() const
            {
                // վերադարձնել ընթացիկ գագաթում պահվող տվյալը
                return _ref._vertices[_current].first;
            }

        private:
            const digraph& _ref; // հղում գրաֆին
            index _current = -1; // հերթական դիտարկվող գագաթի ինդեքսը
            std::vector<std::size_t> _degrees; // գագափթների մուտքային կիսաաստիճանները
            std::stack<index> _S; // ինդեքսների ստեկը
        };
};
Մնում է հիմա digraph դասի համար իրականացնել իտերատոր վերադարձնող begin և end մեթոդները։
iterator begin()
{
    return iterator(*this, true);
}

iterator end()
{
    return iterator(*this, false);
}
Իտերատորի բերված իրականացումը և digraph դասի begin և end մեթոդներն այն նվազագույնն են, որոնք ապահովում են range-for տիպի ցիկլի աշխատանքը։

Tuesday, November 19, 2019

Էսսե տեղադրությունների մասին

— Ուսուցի՛չ,— ասաց Ուաո Գոն,— ինչպե՞ս կարելի է գեներացնել տողի բոլոր տեղադրությունները (permutations):

Կոնֆուցիոսը մի քիչ մտածեց ու հիշեց, որ այդ մասին կարդացել է Կնուտի «Ծրագրավորման արվեսստը» գրքի չորրորդ հատորում (Donald Knuth, «The Art of Computer Programming», vol. 4A)։ Այդ գրքի 7.2.1.2 Generating all permutations բաժնում պատմվում է տեղադրությունները գեներացնելու զանազան ալգորիթմների մասին. ինչպես միշտ՝ Կնուտն իր բարձունքի վրա է։

— Չգիտեմ։ Կարդացեք դասականներին,— ասաց Կոնֆուցիոսը մի քիչ էլ մտածելուց հետո։

* * *

Հաջորդ օրը Կոնֆուցիոսը տաճար մտավ ու տեսավ Ուաո Գոին աղոթելիս։ Կանչեց նրան իր սեղանի մոտ ու ցույց տվեց տախտակների վրա գրված այս տեքստը.

(defun insert-at (e l i)
    (if (zerop i)
        (cons e l)
        (cons (car l) (insert-at e (cdr l) (1- i)))))

(defun range (e r)
    (if (= 0 e)
        (cons 0 r)
        (range (1- e) (cons e r))))
(defun insert-at-all (e l)
    (mapcar #'(lambda (i) (insert-at e l i))
        (range (length l) '())))

(defun insert-to-all-items (e ls)
    (apply #'append (mapcar #'(lambda (q) (insert-at-all e q)) ls)))

(defun permutations-of (l)
    (if (null (cdr l))
        (list l)
        (insert-to-all-items (car l) (permutations-of (cdr l)))))

— Ի՞նչ է սա, ուսուցի՛չ,— հարցրեց Ուաո Գոն։

permutations-of-string-ը գեներացնում է տրված տողի բոլոր տեղադրությունները։

— Ինչպե՞ս։

— Տե՛ս։ Մի որևէ հաջորդականության բոլոր տեղադրությունները ստանալու համար կարելի է առանձնացնել դրա տարրերից մեկը, օրինակ առաջինը, ապա, ռեկուրսիվ եղանակով, հաշվել մյուս տարրերի հաջորդականության բոլոր տեղադրությունները և վերջում առանձնացված տարրը «խցկել» կառուցված տեղադրությունների բոլոր հնարավոր դիրքերում՝ ամեն մի «խցկելու» գործողությամբ գեներացնելով նոր տեղադրություն։ Պա՞րզ է։

— Լավ կլիներ օրինակ բերեիք, ուսուցի՛չ։

— Լավ։ Վերցնենք {a, b, c}։ Առաձնացնենք դրա առաջին տարրը՝ a-ն, մնացած տարրերի հաջորդականությունը կլինի {b, c}: Այս վերջինիս բոլոր հնարավոր տեղադրություններն են.

{(b, c), (c, b)}

Հիմա առանձնացված a տարրը տեղադրենք այս բազմության բոլոր տարրերի բոլոր դիրքերում։ (b, c)-ի համար կստանանք.

(a, b, c), (b, a, c), (b, c, a)

իսկ (c, b)-ի համար էլ.

(a, c, b), (c, a, b), (c, b, a)

Ահա սրանց միավորումն էլ հենց {a, b, c} հաջորդականության բոլոր տեղադրություններն են.

{(a, b, c), (b, a, c), (b, c, a), (a, c, b), (c, a, b), (c, b, a)}

— Ուսուցի՛չ, ո՞րն է ռեկուրսիայի տարրական դեպքը։

— Դա միայն մեկ տարր ունեցող հաջորդականությունն է։ Օրինակ, {a}-ի բոլոր տեղադրությունների բազմությունն է. {(a)}։

— Իսկ ի՞նչ հեզվով են գրված ձեր տախտակները, ուսուցի՛չ։

— Օ՜, դա Լիսպն է, լեզուների մեջ վեհագույնը։

— Թույլ տվեք մի անգամ էլ նայել տախտակներին,— խնդրեց Ուաո Գոն։

— Ահա՛։

— Թարգմանեք, խնդրում եմ, շատ հետաքրքիր է։

— Լավ։ Սկսենք առաջին տախտակից՝ ամենապարզից։ Ինչպես տեսար, տեղադրություններ կառուցելու տարրական գործողությունը տրված հաորդականության տրված դիրքում մի որևէ տարր խցկելն է։ Օրինակ, եթե հաջորդականությունն ունի երեք տարր՝ abc, ապա գոյություն ունեն նոր տարրը խցկելու 4 հնարավոր դիրքեր՝ ₀a₁b₂c₃։ insert-at գործողությունը e տարրը տեղադրում է l ցուցակի i-րդ դիրքում։

(defun insert-at (e l i)
    (if (zerop i)
        (cons e l)
        (cons (car l) (insert-at e (cdr l) (1- i)))))

Հաջորդ տախտակի վրա գրված insert-at-all գործողությունը e տարրը խցկում է l ցուցակի բոլոր թույլատրելի դիրքերում (դրանք |l|+1 հատ են), և վերադարձնում է խցկելու յուրաքանչյուր գործողությունից «ծնված» ցուցակների ցուցակը։ range օժանդակ ֆունկցիան պարզապես կառուցում է տարրը տեղադրելու ինդեքսների ցուցակը։

(defun range (e r)
    (if (= 0 e)
        (cons 0 r)
        (range (1- e) (cons e r))))
(defun insert-at-all (e l)
    (mapcar #'(lambda (i) (insert-at e l i))
        (range (length l) '())))

Երրորդ տախտակի insert-to-all-items գործողությունը insert-at-all ֆունկցիան կիրառում է ls ցուցակի բոլոր տարրերի նկատմամբ, և այդ կիրառություններից ստացված բոլոր ցուցակները միավորում է մի ընդհանուրի մեջ։

(defun insert-to-all-items (e ls)
    (apply #'append (mapcar #'(lambda (q) (insert-at-all e q)) ls)))

Դե, իսկ չորրորդ տախտակին գրված permutations-of գործողությունը հենց խնդրի բուն լուծումն է՝ ռեկուրսիայի կազմակերպմամբ։ Եթե տրված l ցուցակը միայն մի տարր ունի, ապա պատասխանը հենց այդ ցուցակը պարունակող ցուցակն է։ Ռեկուրսիայի քայլում կառուցվում է ցուցակի պոչի տեղադրությունների բազմությունը, ապա՝ insert-to-all-items նախնական ցուցակի առաջին տարրը ավելացվում է բոլոր այդ տեղադրություններին։

(defun permutations-of (l)
    (if (null (cdr l))
        (list l)
        (insert-to-all-items (car l) (permutations-of (cdr l)))))

— Իսկ ինչպե՞ս ենք կառուցելու _տողի_ բոլոր տեղադրությունների բազմությունը, ուսուցի՛չ։

— Դրա համար պետք է տողից կառուցենք նրա տառերի ցուցակը, կառուցենք այդ ցուցակի բոլոր տեղադրությունների բազմությունը, ապա ամեն մի տեղադրությունից ստանանք նոր տող։ Տո՛ւր ինձ մի մաքուր տախտակ։

Կոնֆուցիոսը վերցրեց Ուաո Գոի մեկնած տախտակն ու դրա վրա գրեց.

(defun permutations-of-string (s)
    (mapcar #'(lambda (e) (format nil "~(~{~C~}~)" e))
            (permutations-of (coerce s 'list))))

— Հիմա, Ուաո Գո՛, գնա ու շարունակիր աղոթքդ,— ասաց Կոնֆուցիոսը։

Ուաո Գոն խոնարհվեց ուսոցչին ու խնդրեց.

— Թույլ տուր մի անգամ էլ նայեմ տախտակներին։

Thursday, May 23, 2019

Go: Quick Sort-ի ևս մի ներկայացում

Կարգավորման ալգորիթմներից գեղեցկագույնի՝ QuickSort-ի մասին գրված է ծրագրավորման ալգորիթմներին վերաբերող համարյա բոլոր գրքերում։ Բայց արժե առանձնացնել հատկապես Robert Sedgewick, Kevin Wayne, «Algorithms, 4th Edition» գրքի իլյուստրացիան, որից օգտվելով էլ (ինչպես նաև Go լեզվի sort փաթեթի կոդից) կառուցել եմ ստորև բերվող իրականացումը։ Սակայն իմ նպատակը QuickSort-ի վերլուծությունը չէ. ես ուզում եմ դրա օրինակով ներկայացնել, թե ինչպես կարելի է Go լեզվով իրականացնել ընդհանրացված (generic) ալգորիթմ։

Սկսեմ պարզ դեպքից։ Ենթադրենք գրել եմ quick փաթեթը, որի Sort ֆունկցիան կարգավորում է ամբողջ թվերի զանգվածը.

package quick

// Sort ֆունկցիան կարգավորում է ամբողջ թվերի տրված զանգվածը
func Sort(arr []int) {
 quickSort(arr, 0, len(arr)-1)
}

func quickSort(arr []int, low, high int) {
 if low < high {
  m := partition(arr, low, high)
  quickSort(arr, low, m-1)
  quickSort(arr, m+1, high)
 }
}

func partition(arr []int, low, high int) int {
 p := low
 i, j := low+1, high
 for {
  for i != high && arr[i] < arr[p] {
   i++
  }
  for arr[p] < arr[j] {
   j--
  }
  if i >= j {
   break
  }
  arr[i], arr[j] = arr[j], arr[i]
 }
 arr[p], arr[j] = arr[j], arr[p]
 return j
}

Իմ նպատակն է նույն այս իրականացումն օգտագործել int-երից բացի այլ տիպերի համար։ Այսինքն՝ Sort ֆունկցիան պետք է սահմանել այնպիսի պարամետրով, որ հնարավոր լինի այն կիրառել կամայական տիպի տարրերի զանգվածի նկատմամբ։ Ուշադիր նայելով []int տիպի համար իրականացմանը, տեսնում եմ, որ զանգվածի հետ կատարվում են երեք գործողություններ. ա) ստանալ զանգվածի չափը՝ len(arr), բ) համեմատել զանգվածի տարրերը՝ arr[i] < arr[p], գ) մեկը մյուսով փոխարինել զանգվածի տարրերը՝ arr[i], arr[j] = arr[j], arr[i]։ Սահմանեմ (quick փաթեթում) Sortable ինտերֆեյսը՝ այս երեք գործողություններտ ներկայացնող մեթոդներով.

package quick

// Sortable ինտերֆեյսով որոշվում է «կարգավորելի» զանգվածը
type Sortable interface {
    Size() int           // զանգվածի չափը
    Less(i, j int) bool  // a[i] < a[j] համեմատումը
    Swap(i, j int)       // a[i] <-> a[j] փոխատեղումը
}

Հիմա արդեն կարող եմ հերթով ձևափոխել Sort, quickSort և `partition` ֆունկցիաները։ Առաջինում պետք է փոխել պարամետրի տիպը և len(arr)-ը փոխարինել arr.Size()-ով։

// Sort ֆունկցիան կարգավորում է ամբողջ թվերի տրված զանգվածը
func Sort(arr Sortable) {
 quickSort(arr, 0, arr.Size()-1)
}

Պարզվում է, որ quickSort ֆունկցիայում փոխելու բան չկա։

partition ֆունկցիայում տարրերի համեմատությունները պետք է փոխարինել Less մեթոդի կիրառությամբ, իսկ տարրերի փոխատեղման վերագրումները՝ Swap մեթոդի կիրառությամբ։

func partition(arr Sortable, low, high int) int {
 pv := low
 i, j := low+1, high
 for {
  for i != high && arr.Less(i, pv) {
   i++
  }
  for arr.Less(pv, j) {
   j--
  }
  if i >= j {
   break
  }
  arr.Swap(i, j)
 }
 arr.Swap(pv, j)
 return j
}

Պատրաստ է։ Հիմա տեսնենք, թե ինչպես է այս նոր իրականացումն օգտագործվելու։ Սկսենք արդեն աշխատող տարբերակից. ենթադրենք ուզում եմ կարգավորել int-երի զանգված։ Պետք է իրականացնեմ Sortable ինտերֆեյսը.

type integers []int

func (a integers) Size() int {
    return len(a)
}
func (a integers) Less(i, j int) bool {
    return a[i] < a[j]
}
func (a integers) Swap(i, j) {
    a[i], a[j] = a[j], a[i]
}

Հետո արդեն կարող եմ Sort ֆունկցիան կիրառել `integers` զանգվածի նկատմամբ։

// ...
a0 := integers{4, 1, 9, 2, 3, 8, 5, 6}
quick.Sort(a0)
fmt.Println(a0)
// ...
Հարց։ Եթե մի որևէ ֆունկցիա վերադարձնում է []int զանգված, ապա դրա արդյունքի վրա ո՞նց է կիրառվելու Sort ֆունկցիան։

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.