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.

No comments:

Post a Comment