5 -ma'ruza. Qiymatlar fazosida λ-kesishuv nazariyasi. Λl – to’plamni qurish algoritmlari. Reja

5 -ma'ruza . Qiymatlar fazosida λ-kesishuv nazariyasi. Λl – to’plamni qurish algoritmlari.
REJA:
Qiymatlar fazosidagi λ-kesishmalar nazariyasi.
Lambda ifodalari
Dasturlashda anonim funksiya
Lambda funksiyalaridan foydalanishga misollar

Tayanch tushunchalar: Lambda-hisoblash, λ-hisob, qoʻllash, abstraksiya, bogʻlangan oʻzgaruvchilar, tiplashtirilgan lambda-hisoblash, namunaviy λ-hisob, lambda ifodalari, lambda-notatsiya (yozuvi), formal notatsiya, anonim funksiya, tutashuv.

1.Qiymatlar fazosidagi λ-kesishmalar nazariyasi.
Sof λ-hisoblash, shuningdek ob'ektlar deb ataluvchi termlar yoki λ-term deb ham ataladi, u o’zgaruvchilarni ifodalash qoidalarini istisno qilgan holda va abstraktsiya yordamida quriladi. Dastlab, har qanday konstantalarning mavjudligi hisobga olinmaydi.
λ-hisobning asosida ikkita fundamental operatsiya yotadi:
- Applikatsiya ( lot. applicatio - biriktirilgan, bog’langan) berilgan qiymatga nisbatan ilova yoki funksiya chaqiruvini bildiradi. U odatda bilan belgilanadi, bu yerda - funktsiya, -esa argument. Bu umumiy qabul qilingan matematik yozuv ga mos keladi, ammo, λ-hisoblash uchun muhim bo'lgan narsa shundaki, berilgan kirish qiymatidan natijani hisoblaydigan algoritm sifatida qaraladi.
- Abstraktsiya yoki λ-abstraksiya ( lot. abstractio - chalg'itish, ajratish) o'z navbatida berilgan ifodalarga muvofiq funksiyalarni quradi. Ya'ni, agar erkin argument x-ni o'z ichiga olgan ifoda bo'lsa, u holda yozuvi quyidagilarni bildiradi: - ko'rinishga ega bo'lgan argumentining funksiyasi bo’lib, ko’rinishda belgilanadi. Shunday qilib, abstraktsiya yordamida yangi funksiyalarni qurish mumkin. ning ga erkin kiritilishi talabi unchalik muhim emas - agar u bo'lmasa, deb faraz qilish kifoya.
Lambda ifodasi (inglizcha λ-term) quyidagi grammatikani qanoatlantiradigan ifodadir:
Λ→V
Λ→Λ
ΛΛ→λV.
ΛΛ→VΛ→Λ ΛΛ→λVΛ
Bu yerda V - belgilangan alifbodagi barcha satrlar to'plami Σ∖{"λ"," ", "."}.
Ikkinchi qoidadagi bo'sh joy grammatikaning terminalidir. U baʼzan ifodadagi boshqa belgilar bilan qoʻshilib ketmasligi uchun @ sifatida belgilanadi.
Birinchi holda, funksiya oddiy o'zgaruvchi hisoblanadi. Ikkinchisida bir funksiyaning boshqasiga applikatsiyasi (qo'llanilishi) yuzaga keladi. Bu o'ng operand- argumentida funksiya-chap operandni baholashga o'xshaydi. Uchinchisida - o'zgaruvchi bo'yicha abstraksiya. Bunda bitta argumentning funksiyasi berilgan argument nomi va funksiya tanasi bilan yaratiladi.
Tiplashtirilgan lyamda-hisoblash – λ-hisoblashning bir versiyaisi bo’lib, λ-termlariga turlar deb ataladigan maxsus sintaksis bilan yoziladi. Bunday belgilarni qurish va belgilash uchun turli xil qoidalar to'plamiga ruxsat beriladi va ular turli xil tiplashtirish tizimlarini keltirib chiqaradi.
Namunaviy λ-hisoblash fundamental primitiv dasturlash tillari hisoblanib, ular umumiy funksional dasturlash tillari - amaliy dasturlash tillari, jumladan ML va Haskel, shuningdek, umumiy imperativ dasturlash tillari uchun asos yaratadi.
Bir nuqtai nazardan qaralganda, namunaviy λ-hisoblashni tiplashmagan λ-hisoblashning ixtisoslashuvi deb hisoblash mumkin, boshqa nuqtai nazardan esa, aksincha, tiplashmagan tillarni xususiy hol deb hisoblab, tiplashgan tillarni fundamental til sifatida olish mumkin.
Turlarga ega bo'lgan (tiplashgan) λ-hisoblash dasturlash tillari uchun yangi tiplash tizimlarini ishlab chiqish uchun asos bo'lib xizmat qiladi, chunki ular o'rtasidagi turlar va bog'liqliklar orqali dasturlarning kerakli xususiyatlari ifodalanadi. Dasturlashda kuchli tiplashishga ega dasturlash tillarining mustaqil hisoblash bloklari (funksiyalari, protseduralari, metodlari) odatiy λ-ifodalarga mos keladi.