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.

Java: Անանուն ֆունկցիաները Java 8 լեզվում

Պատահաբար հանդիպեցի Java 8 լեզվում անանուն ֆունկցիաների իրականացման մասին Oracle ֆիրմայի մի հաղորդագրության։ Այդտեղ օրինակներ էր բերված, թե ինչ նպատակների համար են նախատեսված Java 8 լեզվի լյամբդա ֆունկցիաները, և թե ինչպես կարելի է օգտագործել դրանք։
     Իմ բլոգի «Բարձր կարգի ֆունկցիաներ և անանուն ֆունկցիաներ» գրառման մեջ ես ֆունկցիայի ինտեգրալի թվային հաշվման օրինակով համեմատել էի Common Lisp և C++11 լեզվի անանուն ֆունկցիաները։ Այս գրառման մեջ ուզում եմ նույն այդ օրինակը ցույց տալ Java 8 լեզվի անանուն ֆունկցիաների օգտագործմամբ։

Մաթեմատիկական ֆունկցիան, որ կարելի է ինտեգրել, իրականացնում է MathFunc ինտերֆեյսը։ Այն սահմանված է MathFunc.java ֆայլում։

package integral;

public interface MathFunc {
 public double apply( double x );
}

Թվային ինտեգրման մեթոդն իրականացնում է Method ինտերֆեյսը, որը սահմանված է Method.java ֆայլում՝ հետևյալ կերպ։

package integral;

public interface Method {
 public double apply( MathFunc f, double a, double b );
}

Սահմանեմ Integral դասը և սահմանեմ այդ դասի evaluate մեթոդը, որն արգումենտում սպասում է ինտեգրման մեթոդը, ինտեգրվող ֆունկցիան, ինտեգրման միջակայքը և միջակայքի՝ հատվածների տրոհման գործակիցը։ Հաշվելու եղանակը պարզագույնն է. meth օբյեկտի apply մեթոդին են փոխանցվում ինտեգրվող ֆունկցիան և այն փոքր հատվածը, որի վրա նշված թվային մեթոդով հաշվվում է ինտեգրալը։

package integral;

public class Integral {
    public static double evaluate(Method meth, MathFunc func, 
                                double left, double right, double epsilon)
    {
        double result = 0.0;
        for( double x = left; x < right; x += epsilon )
            result += meth.apply(func, x, x + epsilon);
        return result;
    }
}

Որպեսզի, օրինակ, Integral դասի evaluate ստատիկ մեթոդի օգնությամբ հաշվեմ \(f(x)=3x^2-2x+1\) ֆունկցիայի ինտեգրալը, պետք է նախ՝ \(f(x)\) ֆունկցիան սահմանեմ որպես MathFunc ինտերֆեյս իրականացնող օբյեկտ, իսկ ինտեգրման մեթոդը, օրինակ սեղանների կանոնը, սահմանեմ որպես Method ինտերֆեյսն իրականացնող օբյեկտ։
     Սահմանեմ Calc դասը՝ main մուտքի կետով։

package integral;

public class Calc {
    /**/ 
    public static void main( String[] args )
    {
        // ինտեգրման մեթոդ
        Method Simple = new Method() {
            @Override
            public double apply( MathFunc f, double a, double b )
            { return (b - a) * f.apply((b + a) / 2); }
        };

        // ինտեգրվող ֆունկցիա 
        MathFunc Sin = new MathFunc() {
            @Override
            public double apply( double x )
            { return 3*x*x - 2*x + 1; }
        };

        // ինտեգրալի հաշվումն ու արտածումը
        double r0 = Integral.evaluate(Simple, Sin, 0, 1, .0001);
        System.out.println( r0 );
    }
}

Բայց սա հնացած եղանակն է։ Անանուն ֆունկցիաների օգտագործմամբ գրվում է շատ ավելի համառոտ, գեղեցիկ ու հասկանալի կոդ։ Ստորև բերված main ֆունկցիայում ինտեգրման մեթոդն ու ինտեգրվող ֆունկցիան evaluate ֆունկցիային փոխանցված են որպես անանուն ֆունկցիաներ։

package integral;

public class Calc {
    /**/ 
    public static void main( String[] args )
    {
        double r1 = Integral.evaluate( (f,a,b)->(b-a)*f.apply((b+a)/2), 
                                       (x)-> 3*x*x - 2*x + 1, 0, 1, .0001 );
        System.out.println( r1 );
    }
}

* ^* * Java 8 լեզվում անանուն (լյամբդա) ֆունկցիան սահմանվում է հետևյալ քերականությամբ․

(արգումենտների ցուցակ) -> ֆունկցիայի մարմին
Օրինակ, թվային մոտավոր ինտեգրման սեղանների կանոնի բանաձևը վերը բերված օրինակում սահմանված է ահա այսպես․

(f, a, b) -> (b - a) * f.apply((b + a) / 2)

Կարելի է անանուն ֆունկցիան կապել որևէ փոփոխականի հետ, օրինակ, թվային մոտավոր ինտեգրման Սիմպսոնի կանոնի բանաձևը սահմանված է որպես անանուն ֆունկցիա և վերագրված է simpson փոփոխականին․

public static Method simpson = 
   (f, a, b) -> ((b - a) / 6) * (f.apply(a) + f.apply(b) + 4*f.apply((a+b)/2));

Ինտեգրալը հաշվելիս կարելի է evaluate ֆունկցիային փոխանցել simpson փոփոխականը․

double r2 = Integral.evaluate( simpson, (x)-> 3*x*x - 2*x + 1, 0, 1, .0001 );

Առայժմ այսքանը։ Ես դեռ նոր եմ ուսումնասիրում Java 8-ի անանուն ֆունկցիաները։ Հետքգայում միգուցե նորից անդրադառնամ այս թեմային ու ներկայացնեմ ավելի հետաքրքիր օրինակներ։

C++11: Տեքստի տրոհումը բառերի՝ istream-ի միջոցով

Իմ բլոգի գրառումներում արդեն երկու անգամ անդրադարձել եմ տրված տեքստի բառերի հաճախության աղյուսակի կառուցման խնդրին։ Մի անգամ Tcl լեզվով և մի անգամ էլ Python լեզվով։ Այս անգամ որոշել էի նույն խնդիրը գրել C++11 լեզվով՝ այդ լեզվի հնարավորություններն ուսումնասիրելու համար։

Խնդիրը բաղկացած է երկու մասից ա) տրված տեքստը տրոհել բառերի, և բ) հաշվել տեքստում ամեն մի բառի հանդիպելու հաճախությունը։

Ֆայլից սիմվոլ առ սիմվոլ տեքստը կարդալու և բառեր կազմելու հավես ես չունեի։ C լեզվի գրադարանային strtok ֆունկցիան էլ տարբեր պատճառներով չէի ուզում օգտագործել։ Նպատակ ունեի օգտագործել C++ լեզվի istream դասը և այդ դասի համար սահմանված operator>> գործողությունը։ Ավելի պարզ ասած, ուզում էի, որ հետևյալ read_file ֆունկցիան filename ֆայլից կկարդա բառերը և կլցնի words վեկտորի մեջ.

void read_file( char* filename, std::vector<std::string>& words )
{
  std::string w{ "" };
  std::ifstream fin{ filename };
  while( !fin.eof() ) {
    fin >> w;
    words.push_back( w );
  }    
  fin.close();
}

Բայց պարզ է, որ words վեկտորը պարզապես լցվելու է տեքստի՝ բացատներով բաժանված հատվածներով, որովհետև լռելությամբ operator>> գործողությունը բաժանիչ (delimiter) է համարում միայն բացատները։
     Իմ խնդրի համար բաժանիչ պետք է համարել այբուբենի մեծատառերից ու փոքրատառերից տարբերովող բոլոր նիշերը։ Եվ istream դասի օբյեկտը պետք է մի որևէ եղանակով կարգավորել այնպես, որ բաժանիչ համարվեն և անտեսվեն բոլոր ոչ պետքական նիշերը։      Ինտերնետում քչփորելուց հետո հասկացա, որ իմ ուզած բաժանիչները սահմանելու համար պետք է ստեղծեմ նոր locale օբյեկտ։ Հետո այդ locale-ի համար էլ սահմանեմ այնպիսի ctype ֆասետ (facet - սրա անունը այդպես էլ չհասկացա), որում արդեն այբուբենի տառերից տարբերվող նիշերին տրված է space դիմակը (mask)։ Ահա այդ նոր սահմանված դասը, որ ժառանգած է std::ctype<char>-ից։

class word_ctype : public std::ctype<char> {
private:
  static const mask* custom_table()
  {
    mask* wcs = new mask[table_size];
    std::copy_n(classic_table(), table_size, wcs);
    for( int c = 32; c < table_size; ++c ) {
      if( isalpha(c) ) continue;
      wcs[c] = (mask)space;
    }
    return wcs;
  }
public:
  word_ctype( std::size_t refs = 0 )
    : ctype(custom_table(), true, refs)
  {}
};

Հետո արդեն ավելի հետաքրքիր մասն է։ Սահմանեցի create_dictionary ֆունկցիան, որի առաջին արգումենտը վերլուծվող ֆայլի անունն է, իսկ երկրորդը՝ կառուցվելիք բառարանի ֆայլի անունն է։ Ստացվեց համարյա ֆունկցիոնալ կոդ։

void create_dictionary( char* infile, char* outfile )
{
  // բառարան է, որը հաշվում է ամեն մի բառի քանակը
  std::map<std::string,int> dict;
  // ընթերցման հոսքի ստեղծում՝ տրված ֆայլի անունով
  std::ifstream fin{infile};
  // ընթերցման հոսքում ներդնել նոր locale օբյեկտ՝ վերը սահմանված facet-ով
  fin.imbue(std::locale{std::locale::classic(), new word_ctype});
  // հոսքից կարդալու երկու իտերատորներ
  std::istream_iterator sbegin(fin), send;
  // կարդալ հոսքը սկզբից մինչև վերջ և բառերն ավելացնել բառարանում
  std::for_each( sbegin, send, [&dict](std::string w){ ++dict[downcase(w)]; } );
  fin.close();
  
  // ստեղծել արտածման հոսք՝ բառարանը գրելու համար
  std::ofstream fout{outfile};
  // բառարանի ամեն մի գրառման համար ...
  for( auto w : dict )
    // ֆայլում գրել բառը և նրա քանակը
    fout << w.first << ',' << w.second << std::endl;
  fout.close();
}

Այս ֆունկցիայում հոսքից կարդացած բառի բոլոր տառերը փոքրատառ դարձնելու համար օգտագործված downcase ֆունկցիան սահմանված է հետևյալ կերպ։

std::string downcase( std::string sr )
{
  std::transform( sr.begin(), sr.end(), sr.begin(), ::tolower );
  return sr;
}

Vector to List, Vector to String

Հանդիպեցի մի խնդրի, որտեղ պետք էր Common Lisp վեկտորից (միչափանի զանգված), որի տարրերը (0..255) միջակայքի ամբողջ թվեր են, ստանալ նրա տարրերի ցուցակը և այդ նույն տարրերի տասնվեցական ներկայացումներից բաղկացած տողը։ Օրինակ, վեկտորը կարող է լինել այսպիսին.

(defparameter vec
    #(12 34 210 127 32 7 25 87 193 41 42 200 63 0 137 161))
(print vec)

#(12 34 210 127 32 7 25 87 193 41 42 200 63 0 137 161)

Դե, առաջին միտքն այն էր, որ loop ցիկլով կարելի է անցնել վեկտորի տարրերով և դրանք հավաքել ցուցակի մեջ.

(defparameter veclis
    (loop for e across vec collect e))
(print veclis)

(12 34 210 127 32 7 25 87 193 41 42 200 63 0 137 161)

Իսկ տասնվեցական նիշերից կազմված տողը ստանալու համար կարելի է format ֆունկցիայով ստանալ թվի տասնվեցական ներկայացումը՝ օգտագործելով "~2,'0x" ֆորմատավորման տողը։ Այդ տասնվեցական տեսքերը հավաքել ցուցակի մեջ, ապա այդ ցուցակի նկատմամբ կիրառել concatenate ֆունկցիան, իհարկե, apply ֆունկցիայի միջոցով։

(defparameter vecstr
    (apply #'concatenate 'string 
           (loop for e across vec 
                 collect (format nil "~2,'0x" e))))
(print vecstr)

"0C22D27F20071957C1292AC83F0089A1"

* * * Բայց, սրանք շատ տգեղ պրոցեդուրային լուծումներ են։ Common Lisp լեզվի reduce ֆունկցիան արգումենտում ստանում է բինար ֆունկցիա և մի որևէ հաջորդականություն, իսկ վերադաձնում է մի արդյունք, որը ստացվում է հաջորդականության բոլոր տարրերի միջև կիրառելով տրված բինար գործողությունը։ Օրինակ, եթե վեկտորը պարունակում է 1-ից 9 թվերը, ապա դրանց գումարը հաշվելու համար կարելի է գրել.

(reduce #'+ 
        #(1 2 3 4 5 6 7 8 9)
        :initial-value 0)
45

Իսկ նույն այդ վեկտորի թվերի քառակուսիների գումարը հաշվելու համար՝

(reduce #'(lambda (a b) (+ a (* b b))) 
        #(1 2 3 4 5 6 7 8 9)
        :initial-value 0)
285

Հիմա, վեկտորից ցուցակ ստանալու համար օգտագործենք (lambda (x y) (cons y x)) ֆունկցիան և '() սկզբնական արժեքը։ reduce ֆունկցիայի արժեքը ստացվում է շրջված տեսքով, դրա համար էլ լրացուցիչ կիրառվել է reverse ֆունկցիան։

(defparameter veclis
    (reverse (reduce #'(lambda (x y) (cons y x)) vec :initial-value '())))
(print veclis)

(12 34 210 127 32 7 25 87 193 41 42 200 63 0 137 161)

Տասնվեցական ներկայացումների տողը ստանալու համար կարելի է օգտագործել (lambda (x y) (format nil "~a~2,'0x" x y)) ֆունկցիան։

(defparameter vecstr
    (reduce #'(lambda (x y)
                (format nil "~a~2,'0x" x y))
            vec :initial-value ""))
(print vecstr)

"0C22D27F20071957C1292AC83F0089A1"

Scheme: Չփոփոխվող բինար ծառերի մասին

Շարունակելով իմ նախորդ գրառման բինար որոնման ծառերի թեման, ուզում եմ նույն այդ օրինակով ցույց տալ, թե ինչպես կարելի է ծրագրեր գրել օգտագործելով միայն չփոփոխվող (immutable) տվյալների կառուցվածքներ։ Այս անգամ բինար որոնման ծառերի վարքը ծրագրավորել եմ Scheme լեզվով (այն Lisp ընտանիքի թերևս ամենահայտնի ներկայացուցիչն է)։ Ծառը ներկայացված է ցուցակի տեսքով, որի առաջին տարրը արմատի արժեքն է, երկրորդը՝ ձախ ենթածառն է, իսկ երրորդը՝ աջ ենթածառը։ Տերևներն իրենց աջ ու ձախ ենթածառերի փոխարեն պարունակում են #f արժեքը։ Օրինակ, 23 արժեքով տերևը ներկայանում է (23 #f #f) ցուցակով։ Իսկ ստորև բերված նկարում պատկերված ծառը․

        10
       /  \
      6    20
     / \    \
    4   8    28
            /  \
          23    30
            \
             26

ցուցակային ներկայացմամբ կունենա ահա այսպիսի տեսք․

(10 (6 (4 #f #f) (8 #f #f)) (20 #f (28 (23 #f (26 #f #f)) (30 #f #f))))

(Իհարկե կարելի է տերևները ներկայացնել կա՛մ ատոմներով, կա՛մ մեկ տարր պարունակող ցուցակներով։ Բայց ես ընտրել եմ այս ներկայացումը։)

Նախ ծառում արժեք ավելացնելու օրինակով ցույց տամ փոփոխվող (mutable) և չփոփոխվող (immutable) ծրագրավորելու տարբերությունները։ Ենթադրենք C լեզվով որպես բինար որոնման ծառի հանգույց սահմանված է _node ստրուկտուրան, իր _new_node կոնստրուկտորով.

typedef struct _node {
  int data;
  struct _node* left;
  struct _node* right;
} node;
node* _new_node( int value, node* l, node* r )
{
  node* result = (node*)malloc(sizeof(node));
  result->data = value;
  result->left = l;
  result->right = r;
  return result;
}

Այս տիպի հանգույցներով ծառում արժեք ավելացնելու համար սահմանված է _add_value ռեկուրսիվ ֆունկցիան, որն արգումենտում ստանում է ծառի արմատի ցուցիչի ցուցիչը և ավելացվող արժեքը:

void _add_value( node** tree, int value )
{
  if( *tree == NULL )
    *tree = _new_node( value, NULL, NULL );
  if( value < (*tree)->data )
    _add_value( &((*tree)->left), value );
  if( value > (*tree)->data )
    _add_value( &((*tree)->right), value );
}

Այս ֆունկցիայի համար ծառը փոփոխվող օբյեկտ է։ Այն դեպքում, երբ *tree ցուցիչի արժեքը NULL է, ստեղծվում է նոր հանգույց, և այդ նոր հանգույցի ցուցչիը վերագրվում է *tree ցուցիչին։ Քանի որ tree փոփոխականը ֆունկցիայի արգումենտում հայտարարված է struct _node** tree տեսքով, ապա փոփոխությունը կատարվում է հենց ծառի մեջ։

Չփոփոխվող տվյալներով տարբերակում նոր ստեղծված հանգույցն ավելացվում է ոչ թե ծառի մեջ, այլ տրոհվում է ծառը, ավելացվում է հանգույցը պետք եղած տեղում, ապա ստեղծվում է նոր ծառ։

node* _add_value_i( node* tree, int value )
{
  // եթե ծառը դատարկ է, ապա ստեղծել ու վերադարձնել նոր հանգույց
  if( tree == NULL )
    return _new_node( value, NULL, NULL );

  // տրոհել ծառը արմատի արժեքի, ձախ ու աջ ենթածառերի
  int d = tree->data;
  node* l = tree->left;
  node* r = tree->right;
  // ազատել հանգույցի զբաղեցրած հիշողությունը
  free(tree);
  
  // եթե տրված արժեքը փոքր է արմատի արժեքից, ապա 
  // ապա այն ավելացնել ձախ ենթածառում
  if( value < d )
    l = _add_value_i( l, value );
  // եթե տրված արժեքը մեծ է արմատի արժեքից, ապա 
  // ապա այն ավելացնել աջ ենթածառում
  else if( value > d )
    r = _add_value_i( r, value );
  // ստեղծել նոր արմատ ու վերադարձնել նրա ցուցիչը
  return _new_node( d, l, r );
}

(Պարզ է, որ եթե տրված արժեքը հավասար է արմատի արժեքին, ապա հանգույցը քանդելու կարիք չկա, այլ պետք է այն նույնությամբ վերադարձնել։)

Ծառում արժեք ավելացնող add-value պրոցեդուրայի սահմանումը Scheme լեզվով բերված է ստորև։ Այն համարյա նույնությամբ կրկնում է C լեզվով գրված տարբերակը։

(define add-value
  (lambda (tree val)
    (if tree
        (let ([d (car tree)] [l (cadr tree)] [r (caddr tree)])
          (cond
             [(< val d) (list d (add-value l val) r)]
             [(> val d) (list d l (add-value r val))]
             [else (list d l r)]))
        (list val #f #f))))

Քանի որ Scheme լեզվում ներդրված է աղբի հավաքման մեխանիզմը, այս պրոցեդուրայում կարիք չկա C լեզվի free() ֆունկցիային համարժեք գործողություններ կատարելու։

Ֆունկցիաների սահմանման համար Scheme լեզվում նախաատեսված է նաև (define (function-mane arguments) ...) գրելաձևը։ Բայց ինձ ավելի է դուր գալիս lambda արտահայտությամբ սահմանված (define function-name (lambda (arguments) ...) տարբերակը։ Հաջորդ բոլոր ֆունկցիաները սահմանելիս նույնպես օգտագործել եմ այս վերջին գրելաձևը։

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

(define add-to-tree
  (lambda (tree values)
    (if (empty? values)
        tree
        (add-to-tree (add-value tree (car values)) 
                     (cdr values)))))

Օրինակ, վերևի նկարում պատկերված ծառը կարելի է սահմանել (և սահմանածում համոզվելու համար արտածել) հետևյալ արտահայտություններով.

(define *tr* (add-to-tree #f '(10 6 20 4 8 28 23 30 26)))
(displayln *tr*)

Ծառից որևէ տրված արժեքը պարունակող հանգույցը հեռացնելու համար նույնպես կիրառված է նույն մոտեցումը՝ տրոհվում է ծառը, ապա հետ է հավաքվում, բայց արդեն առանց հեռացվող արժեքի։ Այն դեպքում, երբ ծառը դատարկ չէ, արմատը տրոհվում է d, l և r բաղադրիչների։ Երբ որոնվող արժեքը հավասար է d-ին, դիտարկվում են հետևյալ դեպքերը.

1. Եթե \(r=\varnothing \;\wedge\; l=\varnothing\), ապա վերադարձվում է #f։
2. Եթե \(r=\varnothing \;\vee\; l=\varnothing\), ապա վերադարձվում է համապատասխանաբար ձախ կամ աջ ենթածառը։
3. Եթե \(r\ne\varnothing \;\wedge\; l\ne\varnothing\), ապա հեռացվում է աջ ենթածառի ամենափոքր արժեքը պարունակող հանգույցը, իսկ նրա արժեքը գրվում է արմատի արժեքի փոխարեն։

(define remove-value
  (lambda (tree val)
    (if tree
      (let ([d (car tree)] [l (cadr tree)] [r (caddr tree)])
        (cond
          [(< val d)
           (list d (remove-value l val) r)]
          [(> val d)
           (list d l (remove-value r val))]
          [else
           (cond
             [(and (not l) (not r)) #f]
             [(and l (not r)) l]
             [(and (not l) r) r]
             [else
              (let* ([h (minimum-value r)]
                     [t (remove-value r h)])
                (list h l t))])]))
      #f)))

minimum-value պրոցեդուրան, որ օգտագործված է remove-value պրոցեդուրայում, վերադարձնում է իրեն տրված ծառի ամենափոքր արժեքը, կամ, այլ կերպ ասած, ծառի ամենաձախ հանգույցի արժեքը։

(define minimum-value 
  (lambda (tree)
    (let ([l (cadr tree)])
      (if (not l)
          (car tree)
          (minimum-value l)))))

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

(define contains-value 
  (lambda (tree val)
    (if tree
        (let ([d (car tree)])
          (cond 
            [(= val d) #t]
            [(< val d) (contains-value (cadr tree) val)]
            [(> val d) (contains-value (caddr tree) val)]))
        #f)))

Իսկ inorder-traverse պրոցեդուրան կատարում է ծառի ձախ-արմատ-աջ անցում՝ արմատի արժեքի վրա կիրառելով տրված պրոցեդուրան։

(define inorder-traverse 
  (lambda (tree func)
    (when tree
      (inorder-traverse (cadr tree) func)
      (func (car tree))
      (inorder-traverse (caddr tree) func))))

inorder-modify պրոցեդուրան տրված ծառից կառուցում ու վերադարձնում է մի նոր ծառ, որի հանգույցների արժեքները ձևափոխվել են ըստ տրված գործողության։

(define inorder-modify
  (lambda (tree func)
    (if tree
        (let* ([l (inorder-modify (cadr tree) func)]
               [d (func (car tree))]
               [r (inorder-modify (caddr tree) func)])
          (list d l r))
        #f)))

Այս պրոցեդուրայի աշխատանքի արդյունքը ցուցադրելու համար, օրինակ, տրված ծառից կառուցենք և արտածենք մի նոր ծառ, որի հանգույցների \(x\) արքժեքները փոխարինված են \((x\; \sqrt{x})\) տեսքի զույգերով։

(define *tr* (add-to-tree #f '(10 6 20 4 8 28 23 30 26)))
(displayln *tr*)
(displayln (inorder-modify *tr* (lambda (e) (list e (sqrt e)))))

Ահա նաև արդյունքը.

(10 (6 (4 #f #f) (8 #f #f)) (20 #f (28 (23 #f (26 #f #f)) (30 #f #f))))
((10 3.1622776601683795) ((6 2.449489742783178) ((4 2) #f #f) ((8 2.8284271247461903) #f #f)) ((20 4.47213595499958) #f ((28 5.291502622129181) ((23 4.795831523312719) #f ((26 5.0990195135927845) #f #f)) ((30 5.477225575051661) #f #f))))

C++11: Կապակցված ցուցակներ (II)

Ժամանակ առ ժամանակ ինձ մոտ ցանկություն է առաջանում ծանոթանալ C++ լեզվի C++11 ստանդարտի հնարավորություններին։ Այս գրառման մեջ ես երկկապակցված ցուցակի (doubly linked list) իրականացման օրինակով փորձում եմ ծանոթանալ լեզվի այնպիսի նորամուծություններին, ինչպիսիք են զրոյական ցուցիչի nullptr արժեքը, տիպի դուրսբերման auto եղանակը, արժեքավորող ցուցակով կոնստրուկտորները, մի կոնստրուկտորում մեկ այլ կոնստրուկտորի օգտագործումը, և այլն։

* * * Մինչև ցուցակը նկարագրելը ներկայացնեմ նրա մեկ հանգույցը մոդելավորող Item դասը։ Այն շաբլոնային դաս է, data, prev և next դաշտերով, որոնցից առաջինը նախատեսված է հանգույցում պահվող ինֆորմացիայի համար, երկրորդն ու երրորդն էլ համապատասխանաբար նախորդ ու հաջորդ հանգույցներին կապելու համար։

template<typename T>
class Item {
public:
  T data;
  Item* prev;
  Item* next;
    
public:
  Item( const T& val, Item* pr, Item* nx )
    : data(val), prev(pr), next(nx)
  {}
  Item( const T& val )
    : Item(val, nullptr, nullptr)
  {}
  inline void Print() const
  { std::cout << data << (next != nullptr ? ", " : ""); }
};

Առաջին կոնստրուկտորը երեք դաշտերն էլ արժեքավորում է տրված արժեքներով։ Երկրորդ կոնստրուկտորը կառուցում է տրված ինֆորմացիայով հանգույց, որի prev և next ցուցիչները զրոյական են։ Այս կոնստրուկտորում արդեն երևում են C++11 ստանդարտի երկու նորամուծություններ։ 1. Մի կոնստրուկտորում կարելի է օգտագործել մեկ այլ կոնստրուկտոր՝ կիրառելով այն դաշտերի արժեքավորման ցուցակում։ 2. Զրոյական ցուցիչների համար նախատեսված է nullptr հաստատունը (այն ծառայողական բառ է)։

Print մեթոդը ստանդարտ արտածման հոսքի վրա արտածում է հանգույցի data դաշտի պարունակությունը։ Եթե հանգույցի next ցուցիչը հավասար է nullptr-ի, ապա համարվում է, որ այդ հանգույցը ցուցակի վերջին հանգույցն է և այլևս ոչինչ չի արտածվում։ Եթե next ցուցիչը տարբեր է nullptr-ից, ապա արտածվում է նաև ստորակետ՝ ենթադրելով, որ հաջորդելու են այլ հանգույցների արտածումներ։

* * * Ցուցակը մոդելավորող List շաբլոնային դասն ունի երեք դաշտ. head - ցուցիչ է առաջին հանգույցին, tail - ցուցիչ է վերջին հանգույցին, count - հանգույցների քանակն է։

template<typename T>
class List {
private:
  Item<T>* head;
  Item<T>* tail;
  unsigned int count;

Կոնստրուկտորներից առաջինը ստեղծում է դատարկ ցուցակ՝ առաջին ու վերջին հանգույցների ցրույական ցուցիչներով և տարրերի քանակի զրոյական հաշվիչով։

public:
  List()
    : head(nullptr), tail(nullptr), count(0)
  {}

Երկրորդ կոնստրուկտորը ցուցակը կառուցում է տրված արժեքավորող ցուցակի (initializer list) տարրերից: Օրինակ, եթե պետք է սահմանել մի ցուցակ 1, 2, 3 սկզբնական տարրերով, ապա կարող ենք գրել "List<int> ex0 = {1, 2, 3};": Ահա այս դեպքում է աշխատում հենց ստորև բերված կոնստրուկտորը։ (initializer_list կոնտեյները հայտարարված է ստանդարտ գրադարանի initializer_list ֆայլում։)

  List( std::initializer_list<T> vals )
    : List()
  {
    for( auto v : vals )
      PushBack( v );
  }

Նորամուծություն է նաև ցիկլի կազմակերպման for կառուցվածքի տեսքը։ Այս տեսքով v փոփոխականն անցնում է vars կոնտեյների տարրերով։ auto ծառայողական բառը ցույց է տալիս, որ կոմպիլյատորը v փոփոխականի տիպը ավտոմատ որոշելու է կոմպիլյացիայի ժամանակ։ Եթե գրեինք C++98 ոճով, ապա այս ցիկլը կունենար մոտավորապես հետևյալ տեսքը.

for( std::initalizer_list<T>::iterator v = vals.begin(); v != vals.end(); ++v )
  PushBack( *v );

Front և Back մեթոդները համապատասխանաբար վերադարձնում են ցուցակի առաջին ու վերջին հանգույցների ցուցիչները։ Count մեթոդը վերադարձնում է տարրերի քանակը։ IsEmpty մեթոդը պարզում է ցուցակի դատարկ լինելը։ (Այս ֆունկցիաների իրականացման մեջ որևէ հետաքրքիր բան չկա։)

  Item<T>* Front() const 
  { return head; }
  
  Item<T>* Back() const 
  { return tail; }
  
  unsigned int Count() const
  { return count; }

  bool IsEmpty() const
  { return head == nullptr && tail == nullptr; }

Print մեթոդը ստանդարտ արտածման հոսքին արտածում է ցուցակի տարրերի արժեքները՝ ստորակետերով անջատված։ Ցուցակի ամբողջ պարունակությունն արտածվում է "[" և "]" նիշերի մեջ։ Մեթոդի իրականացումը մի պարզ ցիկլ է, որը, թեևս, բացատրության կարիք չունի։

  void Print() const
  {
    std::cout << "[";
    for( auto p(head); p != nullptr; p = p->next )
      p->Print();
    std::cout << "]";
  } 

* * * Ցուցակում տարրեր ավելացվում են չորս մեթոդների օգնությամբ։ Դրանք են.

• PushFront(v) - ցուցակի սկզբից ավելացնում է տրված v արժեքով հանգույց,
• InsertBefore(v, n) - ցուցակի n հանգույցից առաջ ավելացնում է v արժեքով հանգույց,
• PushBack(v) - ցուցակի վերջից ավելացնում է տրված v արժեքով հանգույց,
• InsertAfter(v, n) - ցուցակի n հանգույցից հետո ավելացնում է v արժեքով հանգույց։

Եթե ցուցակը դատարկ է, ապա PushFront մեթոդը ստեղծում է նոր հանգույց, head և tail ցուցյիչները կապում է նրան, իսկ հանգույցների հաշվիչին վերագրում է 1։ Եթե ցուցակը դատարկ չէ, ապա նոր հանգույցն ավելացվում է InsertBefore մեթոդով։

  void PushFront( const T& val )
  {
    if( IsEmpty() ) {
      head = new Item<T>(val);
      tail = head;
      count = 1;
    }
    else
      InsertBefore( val, head );
  }

InsertBefore մեթոդը արգումենտում ստանում է val արժեքը և node ցուցիչը։ Ապա ստեղծվում է նոր հանգույց՝ val արժեքով, որի prev ցուցիչին վերագրված է node->prev ցուցիչը, իսկ next ցուցիչին՝ node ցուցիչը։ Հաջորդ քայլում նոր ստեղծված temp հանգույցին հաջորդող և նախորդող հանգույցները կապվում են temp-ի հետ։ Եվ վերջապես, ստուգվում է, որ եթե հոր հանգույցն ավելացվել է head-ից առաջ, ապա head տեղաշարժվում է նոր հանգույցի վրա։

  void InsertBefore( const T& val, Item<T>* node )
  {
    auto temp = new Item<T>(val, node->prev, node); // 1
    temp->next->prev = temp; // 2
    if( temp->prev != nullptr )
      temp->prev->next = temp; // 3
    ++count;
    if( node == head )
      head = temp;
  }

PushBack մեթոդը, որ պետք է արժեք ավելացնի ցուցակի պոչից, օգտագործում է տրված հանգույցից հետո նոր հանգույց խցկող InsertAfter մեթոդը։

  void PushBack( const T& val )
  {
    if( IsEmpty() )
      PushFront( val );
    else
      InsertAfter( val, tail );
  }

Իսկ InsertAfter մեթոդն իր հերթին օգտագործում է InsertBefore մեթոդը՝ նոր հանգույցն ավելացնելով ոչ թե տրված հանգույցից առաջ, այլ նրանից հետո, ապա փոխարինելով data դաշտի արժեքները։

  void InsertAfter( const T& val, Item<T>* node )
  {
    InsertBefore( node->data, node );
    node->data = val;
  }

* * * Մեթոդների հաջորդ խումբը նախատեսված է ցուցակից հանգույցներ հեռացնելու համար։ Դրանք են.

• Remove(n) - ցուցակից հեռացնում է տրված n հանգույցը,
• PopFront - հեռացնում է ցուցակի առաջին հանգույցը և վերադարձնում է նրա data դաշտի արժեքը,
• PopBack - հեռացնում է ցուցակի վերջին հանգույցը՝ նույնպես վերադարձնելով նրա data դաշտի արժեքը,

Remove մեթոդի սկզբում նախ ստուգվում է, որ տրված հանգույցի ցուցիչը զրոյական չլինի և ցուցակը դատարկ չլինի։ Երկու դեպքերում էլ գեներացվում է սխալ՝ runtime_error՝ համապատասխան հաղորդագրությամբ։ Այս բացառության դասը նունպես ավելացված է C++11 ստանդարտում և, ի թիվս այլ նոր բացառությունների դասերի, սահմանված է ստանդարտ գրադարանի stdexcept ֆայլում։
  Այնուհետև, եթե հեռացվող հանգույցն ունի հաջորդող հանգույց, ապա դրա prev ցուցիչին վերագրվում է հեռացվող հանգույցի prev ցուցիչի արժեքը։ Համապատասխան գործողությունը կատարվում է նաև հեռացվողին նախորդող հանգույցի հետ։
  Եթե հեռացվող հանգույցը ցուցակի առաջին կամ վերջին հանգույցն է, ապա համապատասխան ձևով վերահաշվարկվում են նաև head և tail ցուցիչները։
Իսկ վերջում համակարգին է վերադարձվում հեռացվող հանգույցի զբաղեցրած հիշողությունն ու մեկով նվազեցվում է հանգույցների քանակի հաշվիչի արժեքը։

  void Remove( Item<T>* node )
  {
    if( node == nullptr )
      throw new std::runtime_error("Null node.");
    if( IsEmpty() )
      throw new std::runtime_error("Empty list.");
    
    if( node->next != nullptr )
      node->next->prev = node->prev;

    if( node->prev != nullptr )
      node->prev->next = node->next;

    if( node == head )
      head = head->next;
    if( node == tail )
      tail = tail->prev;

    delete node;
    --count;
  }

PopFront և PopBack մեթոդները պարզապես օգտագործում են Remove մեթոդը՝ նախապես պահելով և վերադարձնելով առաջին կամ վերջին հանգույցի պարունակած արժեքը։

  T PopFront()
  {
    auto res(head->data);
    Remove(head);
    return res;
  }
  
  T PopBack()
  {
    auto res(tail->data);
    Remove(tail);
    return res;
  }

* * * Ցուցակում որոնում կատարելու համար ես նախատեսել եմ երկու մեթոդներ. FindIf, որը վերադարձնում է տրված պրեդիկատին բավարարող առաջին հանգույցի ցուցիչը, և Find, որը վերադարձնում է տրված արժեքը պարունակող առաջին հանգույցի ցուցիչը։

Պրեդիկատը FindIf մեթոդին փոխանցվում է որպես ստանդարտ գրադարանի function օբյեկտ։ Այս function դասը նույնպես ներմուծված է նոր ստանդարտում և սահմանված է functional ֆայլում։

  Item<T>* FindIf( std::function<bool(T)> pred ) const 
  {
    for( auto p(head); p != nullptr; p = p->next )
      if( pred(p->data) )
        return p;
    return nullptr;
  }

Find մեթոդն օգտագործում է FindIf-ը՝ տրված արժեքով հանգույցը գտնելու համար։ Այս մեթոդում ստեղծվում է մի լյամբդա ֆունկցիա (արտահայտություն), որպես որոնման պրեդիկատ, որը "բռնելով" val փոփոխականը, այն համեմատում է իր արգումենտում տրված արժեքի հետ։

  Item<T>* Find( const T& val ) const
  {
    return FindIf( [&val](T v)->bool { return val == v; } );
  }

Եվ վերջին մեթոդը։ Map մեթոդը արգումենտում ստանում է ցուցակի արժեքը ձևափոխող ֆունկցիա և ներադարձնում է ձևափոխված արժեքներից կառուցած նոր ցուցակի ցուցիչը։

  List<T>* Map( std::function<T(T)> func ) const
  {
    auto result = new List<T>();
    for( auto p(head); p != nullptr; p = p->next )
      result->PushBack( func(p->data) );
    return result;
  }

Օրինակ, այս Map մեթոդով կարելի է ամբողջ թվեր պարունակող ցուցակից կառուցել նույն այդ թվերի քառակուսիները պարունակող ցուցակ։ Ահա այսպես.

  auto ex0 = new List<int>({1, 2, 3, 4});
  List<int>* ex1 = ex0->Map( [](int e)->int { return e * e; } );
  ex1->Print();

* * * List դասի դեստրուկտորը Remove մեթոդի օգնությամբ հեռացնում է բոլոր հանգույցները։

  ~List()
  {
    while( !IsEmpty() )
      Remove( head );
  }
};

Python: Բառարանի օգտագործումը

Այս գրառման մեջ ես առաջարկում եմ ևս մի լուծում իմ նախորդ գրառման մեջ առաջարկված և Tcl լեզվով լուծված խնդրի համար։ Նորից հիշեցնեմ խնդրի ձևակերպումը.

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

Այս անգամ նույն խնդրի լուծումը տալիս եմ Python ծրագրավորման լեզվով։


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

import re

Դատարկ բառարանը ստեղծվում է dict դասի կոնստրուկտորի կանչով։

words = dict()

Տեքստը տող առ տող ֆայլից կարդալու և բառերի տրոհելու համար with հրամանով ստեղծենք կատարման կոնտեքստ, որում fin փոփոխականին կապված է open հրամանով կարդալու համար բացված տեքստային ֆայլը (Ջեկ Լոնդոն, "Մարտին Իդեն"): Կատարման կոնտեքստում for հրամանով իտերացիա կազմակերպենք ֆայլի տողերով։ re մոդուլի sub մեթոդը տրված տողում փոխարինում է տրված կանոնավոր արտահայտությամբ ճանաչված հատվածները մեկ այլ տրված տեքստով։ Փոխարինումից հետո տողի բոլոոր մեծատառերը lower մեթոդով դարձնենք փոքրատառեր ու split մեթոդով տողը կտրտենք բառերի։ if հրամանով ստուգենք որ բառի երկարությունը մեծ լինի մեկից։ Հաջորդ if հրամանով և not in գործողությամբ ստուգենք ընթացիկ բառի առկայությունը բառարանում. եթե այն բացակայում է, ապա ավելացնում ենք՝ հաշվիչի 0 սկզբնական արժեքով։ Հաջորդ քայլում պարզապես հերթական բառի հաշվիչն ավելացնում ենք մեկով։

with open('martin-eden-jack-london.txt') as fin:
  for line in fin:
    line = re.sub('[^a-zA-Z]+', ' ', line)
    for wr in line.lower().split(' '):
      if len(wr) > 1:
        if wr not in words:
          words[wr] = 0
        words[wr] += 1

len ֆունկցիան վերադարձնում է dict օբյեկտի գրառումների քանակը։ մեր դեպքում դա տեքտի իրարից տարբեր բառերի քանակն է։ sum ֆունկցիան վերադարձնում է ցուցակի տարրերի գումարը։ Այստեղ ցուցակը words բառարանի արժեքների ցուցակն է, որի տարրերի գումարը ստացվում է տեքստի բոլոր բառերի քանակը։ format մեթոդը կատարում է տողի ֆորմատավորում, այն նաև տեղադրում է տրված արժեքները տողի նշված տեղերում։

uniwords = len(words)
allwords = sum(words.values())
print('{0} / {1} = {2}'.format(uniwords, allwords, 1.0 * uniwords / allwords))

sorted ներդրված ֆունկցիան վերադարձնում է արգումենտում տրված ցուցակի ըստ աճման կարգավորված տարբերակը։ Եթե reverse անվանված արգումենտը տրված է True, ապա վերադարձնում է ըստ արժեքների նվազման կարգավորված ցուցակը։ dict օբյեկտի values մեթոդը վերադարձնում է բառարանի արժեքների ցուցակը։ Մյուս, items մեթոդը հնարավորություն է տալիս իտերացիա կազմակերպել բառարանի բանալի-արժեք զույգերով։ in գործողությունը ստուգում է տարրի պատկանելիությունը ցուցակին։

tenbignums = sorted(words.values(), reverse=True)[0:10]
for word, count in words.items():
  if count in tenbignums:
    print('{0} : {1}'.format(word, count))

sorted ֆունկցիան key անվանված արգումենտով ստանում է այն բնութագիրը, ըստ որի պետք է համեմատվեն ցուցակի տարրերը։ Այստեղ որպես բնութագիր տրված է մի անանուն ֆունկցիա՝ ստեղծված lambda արտահայտության օգնությամբ, որը վերադարձնում է արգումենտի չափը։ Այս կերպ կարողանում ենք բառարանի բանալիների ցուցակը, որը ստացվում է keys մեթոդով, կարգավորել ըստ տարրերի երկարության։

tenbigwords = sorted(words.keys(), key=lambda w: len(w), reverse=True)[0:10]
for wd in tenbigwords:
  print('{0} : {1}'.format(wd, words[wd]))

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

onlyone = [wd for wd, cnt in words.items() if cnt == 1]
print(onlyone)

* * *

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