Լամբդա արտահայտություն

Լյամբդա արտահայտություն-ը (λ-արտահայտություն) մշակվել է ամերիկացի մաթեմատիկոս Ալոնզո Չարչի կողմից՝ հաշվարկելիության գաղափարը վերլուծելու համար։ Այն նկարագրում է ալգորիթմի հասկացությունը։

Մինչև համակարգիչների ի հայտ գալը, 20-րդ դարի 30-ականներին, մաթեմատիկոսներին հետաքրքրում էր այն հարցը, թե կարելի է արդյոք ստեղծել ալգորիթմ, որը կկարողանա տրված աքսիոմների հիման վրա որոշել ճի՞շտ է արդյոք տրված տրամաբանական արտահայտությունը։ Դրա համար առաջին հերթին պետք է հասկանալ, թե ինչ է ալգորիթմը։

Այդ հարցի պատասխանը տվեցին Ալոնզո Չարչը (Alonzo Church) և Ալան Թյուրինգը (Alan Turing)։ Չարչը մշակեց լյամբդա արտահայտությունը, իսկ Թյուրինգը՝ Թյուրինգի մեքենայի մեթոդը։

Թերմեր

λ-արտահայտության մեջ թերմերը սահմանվում են հետևյալ կերպ.

• բոլոր փոփոխականները թերմեր են,
• եթե A-ն և B-ն թերմեր են, ապա (AB)-ն ևս թերմ է,
• եթե A-ն թերմ է, իսկ x-ը փոփոխական, ապա (λx. A)-ն թերմ է։

Ապլիկացիա և աբստրակցիա

λ-արտահայտության հիմքում ընկած են երկու հիմնական գործողություններ.

• Ապլիկացիա (լատ. aplicatio – կցում, միացում) նշանակում է ֆունկցիայի կիրառում կամ կանչ տրված փոփոխականի համար։ Այն սովորաբար նշանակում են f a, որտեղ f-ը ֆունկցիա է, իսկ a-ն արգումենտ։ Դա համապատասխանում է f(a) մաթեմատիկական նշանակմանը, սակայն λ արտահայտության համար կարևոր է այն, որ f-ը մեկնաբանվում է որպես ալգորիթմ, որը տրված մուտքային արժեքի համար հաշվում է արդյունք։ Այս իմաստով f-ի ապլիկացիան դիտարկվում է երկիմաստ.

1. որպես f-ի` a-ի նկատմամբ կիրառման արդյունք,
2. որպես f-ի հաշվարկ ըստ a-ի։

• Աբստրակցիան կամ λ աբստրակցիան (լատ. abstraction – հեռացում, բաժանում) իր հերթին կառուցում է ֆունկցիաներ ըստ տրված արտահայտությունների։ λx. t[x] գրառումը նշանակում է λ ֆունկցիա x փոփոխականից, որն ունի t[x] տեսքը։

Փակագծերի վերաբերյալ պայմանավորվածություն

Թերմի արտաքին փակագծերը սովորաբար բաց են թողնվում։ Բացի այդ ((X₁ X₂)X₃)...Xn)-ի փոխարեն գրվում է X₁X₂X₃...Xn (փակագծերը խմբավորվում են ձախ կողմից), λ.(AB)-ի փոխարեն՝ λ.AB (ապլիկացիան ունի ավելի մեծ առաջնայնություն, քան λ-ն) և (λX₁.(λX₂.(...λXn.A)...))-ի փոխարեն՝ λX₁X₂...Xn.A:

α – ձևափոխություն

Տեղադրման ընթացքում պետք է հետևել, որ ավելորդ կապված փոփոխականներ չառաջանան։ Օրինակ հետևյալ արտահայտության մեջ

( λxy.x ) y

տեղադրման գործողությունից հետո կստացվի

λy.y

y-ը մինչ տեղադրությունը անկախ փոփոխական էր, իսկ տեղադրությունից հետո դառնում է կախյալ։ Անհրաժեշտ է բացառել նման դեպքերը։ Փոխարինելով y-ը z-ով կստանանք

( λxz.x ) y

Տեղադրությունից հետո արդյունքն այլ է՝

λz.y 

Այդպիսի ձևափոխությունը կոչվում է α – ձևափոխություն։

β - ռեդուկցիա

Ֆունկցիայում փոփոխականի արժեքի տեղադրման գործողությունը կոչվում է β – ռեդուկցիա։ Տեղադրման կանոնները հետևյալն են.

1. X [x = N] => N
2. Y [x = N] => y
3. (λx.P)[x = N] => (λy.P[x = N]), y ∉ FV(N)
4. (λx.P)[x = N] => (λx.P)

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

y ∉ FV(N) պայմանը նշանակում է, որ պետք է հետևել, որպեսզի N անկախ փոփոխականը (թերմը) չպարունակի կախյալ փոփոխականը (y-ը)։ Հակառակ դեպքում տեղադրությունից հետո այն կդառնա կախյալ։ Եթե, այնուամենայնիվ, այդպիսի դեպք լինի, ապա պետք է կատարել α ձևափոխություն

Վերջին կանոնի մեջ ոչինչ չի փոխվում, քանի որ x-ը կախյալ փոփոխական է, իսկ տեղադրություն կատարվում է միայն անկախ փոփոխականների փոխարփն։ Ոչ բոլոր թերմերը կարելի է հաշվել։ Օրինակ հետևյալ տեսքի թերմի համար

(λ x. x x) (λ x. x x)

ամեն քայլից հետո նորից վերադառնում ենք նախնական տեսքին։

Կապը ռեկուրսիվ ֆունկցիաների հետ

Լամբդա արտահայտության մեջ բոլոր ֆունկցիաներն անանուն են։ Դա նշանակում է, որ ֆունկցիայի մարմնում մենք չենք կարող կանչել այդ ֆունկցիան, քանի որ չենք կարող հղվել նրա վրա։ Թվում է, թե հնարավոր չէ կառուցել ռեկուրսիա։ Սակայն դա այդպես չէ։ Խնդիրը լուծվում է անշարժ կետի կոմբինատորի միջոցով։Դրա համար F թերմի համար անհրաժեշտ է գտնել այնպիսի X, որ

FX = X

Գոյություն ունեն բազմաթիվ անշարժ կետի կոմբինատորներ։ Դիտարկենք Y կոմբինատորը՝

Y = λf.(λx.f(xx))(λx.f(xx))

Պետք է համոզվել, որ ցանկացած F թերմի համար F(YF)=YF պայմանը ճիշտ է։

YF = (λx.F(xx))(λx.F(xx)) = F(λx.F(xx))(λx.F(xx)) = F(YF)

Այդպես Y կոմբինատորի օգնությամբ կարելի է կազմել ռեկուրսիվ ֆունկցիաներ։

Լամբդա արտահայտության ընդլայնում

Ենթադրենք որոշել ենք լամբդա արտահայտության հիման վրա գրել ծրագրավորման լեզու։ Թվերը կարելի է ստանալ հարցում կատարելով պրոցեսորին և ստալալ պատասխանը շատ արագ։ Այս դեպքում օգտվում են լամբդա արտահայտության ընդլայնված տարբերակից։ Դրանում կա երկու տիպի տարր՝

• փոփոխականներ
• հաստատուններ

Հաստատունների համար մենք կարող ենք սահմանել ռեդուկցիայի հատուկ կանոններ։ Օրինակ կարող ենք լրացնել լամբդա արտահայտությունը հաստատուններով.

+, *, 0, 1, 2, ...

և սահմանել դրանց համար ռեդուկցիայի կանոններ, որոնք արժեք ստանալու համար հարցում կկատարեն պրոցեսորից.

a + b = AddWithCPU(a, b)
a * b = MulWithCPU(a, b)

Կարելի է սահմանել հաստատուններ նաև տրամաբանական արտահայտությունների համար.

True, False, If, Not, And, Or

և սահմանել ռեդուկցիայի կանոններ

If True a b = a
If False a b =	b
Not True = False
Not False = True
Add False a = False
Add True b = b
…

Այդպիսի օրենքները կոչվում են δ-ռեդուկցիա(դելտա-ռեդուկցիա)։

Հղումներ

Վիքիպահեստն ունի նյութեր, որոնք վերաբերում են «Լամբդա արտահայտություն» հոդվածին։