Ok (informatika) - Arrow (computer science)

Yilda Kompyuter fanlari, o'qlar yoki murvatlar a turi sinf ichida ishlatilgan dasturlash tasvirlamoq hisoblashlar a toza va deklarativ moda. Dastlab kompyuter olimi tomonidan taklif qilingan Jon Xyuz ning umumlashtirilishi sifatida monadalar, o'qlar a mos ravishda shaffof o'rtasidagi munosabatlarni ifoda etish usuli mantiqiy hisoblash bosqichlari.[1] Monadlardan farqli o'laroq, o'qlar qadamlarni bitta va bitta kirishga cheklab qo'ymaydi. Natijada, ular foydalanishni topdilar funktsional reaktiv dasturlash, nuqtasiz dasturlash va tahlilchilar boshqa ilovalar qatorida.[1][2]

Motivatsiya va tarix

Oklar alohida sinf sifatida tan olinishdan oldin ishlatilgan bo'lsa-da, 2000 yilgacha Jon Xyuz birinchi marta ularga bag'ishlangan tadqiqotlarni nashr etdi. O'sha vaqtga qadar monadalar dastur mantig'ini sof kodda birlashtirishni talab qiladigan ko'plab muammolar uchun etarli ekanligini isbotladilar. Biroq, ba'zi foydali kutubxonalar kabi Fudjetlar uchun kutubxona grafik foydalanuvchi interfeyslari va monadik shaklda qayta yozishga qarshi bo'lgan ba'zi samarali tahlilchilar.[1]

Ushbu istisnolarni monadik kodga tushuntirish uchun o'qlarning rasmiy kontseptsiyasi ishlab chiqilgan va bu jarayonda monadalarning o'zlari kichik to'plam strelkalar.[1] O'shandan beri o'qlar faol tadqiqot yo'nalishi bo'lib kelgan. Ularning asosiy qonunlari va operatsiyalari bir necha bor takomillashtirildi, masalan, o'qlarni hisoblash kabi so'nggi formulalar faqat beshta qonunni talab qiladi.[3]

Kategoriya nazariyasi bilan bog'liqlik

Yilda toifalar nazariyasi, Kleisli toifalari hammasidan monadalar Xyuz o'qlarining to'g'ri pastki qismini tashkil qiladi.[1] Esa Freyd toifalari deb ishonishgan teng bir muddat o'qlarga,[4] shu vaqtdan beri o'qlar yanada umumiy ekanligi isbotlangan. Aslida, o'qlar shunchaki teng emas, balki to'g'ridan-to'g'ri tengdir boyitilgan Freyd toifalari.[5]

Ta'rif

Barcha turdagi sinflar singari, o'qlarni ham har qanday kishiga tatbiq etilishi mumkin bo'lgan fazilatlar to'plami sifatida qarash mumkin ma'lumotlar turi. In Haskell dasturlash tili, o'qlar ruxsat beradi funktsiyalari (Haskell tomonidan namoyish etilgan -> belgi) ni birlashtirish reified shakl. Shu bilan birga, "o'q" atamasi ba'zi (lekin hammasi emas) strelkalar bilan mos kelishidan kelib chiqishi mumkin morfizmlar (toifalar nazariyasida "o'qlar" nomi bilan ham tanilgan) turli xil Kleisli toifalari. Nisbatan yangi kontseptsiya sifatida bitta, standart ta'rif mavjud emas, ammo barcha formulalar mantiqan tengdir, ba'zi kerakli usullarni o'z ichiga oladi va ba'zi matematik qonunlarga qat'iy rioya qiladi.[6]

Vazifalar

Hozirda Haskell tomonidan ishlatiladigan tavsif standart kutubxonalar talab qiladi faqat ikkita asosiy operatsiya:

  • A turi konstruktori arr funktsiyalarni bajaradigan -> har qanday turdan s boshqasiga tva ushbu funktsiyalarni o'qga ko'taradi A ikki tur o'rtasida.[7]
arr (s -> t)        ->   A s t
  • Quvur usuli birinchi o'qni ikki tur o'rtasida olib, orasidagi o'qga aylantiradi koreyslar. Koreyalardagi birinchi elementlar kirish va chiqishning o'zgartirilgan qismini, ikkinchi elementlar esa uchinchi turni ifodalaydi siz hisoblashni chetlab o'tadigan o'zgarmas qismni tavsiflash.[7]
birinchi (A s t)       ->   A (s,siz) (t,siz)

O'qni aniqlash uchun faqat shu ikkita protsedura qat'iy zarur bo'lsa-da, amalda va nazariyada o'qlar bilan ishlashni osonlashtiradigan boshqa usullarni olish mumkin. Barcha o'qlar kabi toifalar, ularning qo'lidan keladi meros toifalar sinfidan uchinchi operatsiya:

  • A tarkibi operator >>> birinchi funktsiya chiqishi va ikkinchisining kiritilishi mos keladigan turlarga ega bo'lsa, ikkinchisiga o'qni qo'shishi mumkin.[7]
    A s t  >>>  A t siz   ->   A s siz

Oldingi uchta kombinatsiyadan yana bir foydali usulni olish mumkin:

  • Birlashtiruvchi operator *** Ikkita o'qni, ehtimol turli xil kirish va chiqish turlarini olishi va ularni ikkita birikma turi o'rtasida bitta o'qga birlashtirishi mumkin. Birlashtirish operatori ekanligini unutmang emas albatta kommutativ.[7]
A s t  ***  A siz v   ->   A (s,siz) (t,v)

Ok qonunlari

Yaxshi belgilangan protseduralarga ega bo'lishdan tashqari, o'qlar qo'llanilishi mumkin bo'lgan har qanday turlar uchun ma'lum qoidalarga rioya qilishlari kerak:

  • Oklar har doim barcha turlarini saqlashi kerak ' shaxsiyat id (asosan toifadagi barcha turlar uchun barcha qiymatlarning ta'riflari).[7]
arr id              ==   id
  • Ikki funktsiyani ulashda f & g, kerakli o'q operatsiyalari bajarilishi kerak tarqatmoq chapdagi kompozitsiyalar ustida.[7]
arr (f >>> g)       ==   arr f  >>>  arr gbirinchi (f >>> g)     ==   birinchi f  >>>  birinchi g
  • Oldingi qonunlarda quvurlar to'g'ridan-to'g'ri funktsiyalarga qo'llanilishi mumkin, chunki quvurlar va ko'tarish birgalikda sodir bo'lganda buyurtma ahamiyatsiz bo'lishi kerak.[7]
arr (birinchi f)       ==   birinchi (arr f)

Qolgan qonunlar, truboprovod usuli kompozitsiyaning tartibini o'zgartirganda qanday ishlashini cheklaydi, shuningdek soddalashtirishga imkon beradi iboralar:

  • Agar identifikator o'qni hosil qilish uchun ikkinchi funktsiya bilan birlashtirilsa, uni quvurli funktsiyaga biriktirish kommutativ bo'lishi kerak.[7]
arr (id *** g)  >>>  birinchi f       ==   birinchi f  >>>  arr (id *** g)
  • Turni soddalashtirishdan oldin funktsiyani quvurga keltirish, unsiz funktsiyaga ulanishdan oldin soddalashtirilgan turga teng bo'lishi kerak.[7]
birinchi f  >>>  arr ((s,t) -> s)     ==   arr ((s,t) -> s)  >>>  f
  • Va nihoyat, avval ikki marta funktsiyani quvurga o'tkazish qayta ajratish natijada joylashtirilgan naycha, funktsiyani bitta aylanib o'tishni biriktirishdan oldin, ichki naychani qayta ajratish bilan bir xil bo'lishi kerak. Boshqacha qilib aytganda, stacked bypasslar funktsiyani o'zgartirmasdan ushbu elementlarni birlashtirib, tekislanishi mumkin.[7]
birinchi (birinchi f)  >>>  arr ( ((s,t),siz) -> (s,(t,siz)) )   ==  arr ( ((s,t),siz) -> (s,(t,siz)) )  >>>  birinchi f

Ilovalar

Qo'shimcha operatsiyalar va cheklovlarni belgilash orqali o'qlar muayyan vaziyatlarga mos ravishda kengaytirilishi mumkin. Odatda ishlatiladigan versiyalarda hisoblash uchun imkoniyat beradigan o'q bilan tanlangan o'qlar mavjud shartli qarorlar va o'qlar mulohaza, bu qadam sifatida o'z natijalarini kirish sifatida qabul qilishga imkon beradi. Amalda o'qlar deb nomlanuvchi yana bir o'qlar to'plami amalda kamdan kam qo'llaniladi, chunki ular aslida monadalarga tengdir.[6]

Qulaylik

Oklar bir nechta afzalliklarga ega, asosan dastur mantig'ini aniq, ammo ixcham qilish qobiliyatidan kelib chiqadi. Qochishdan tashqari yon effektlar, sof funktsional dasturlash uchun ko'proq imkoniyatlar yaratadi statik kodni tahlil qilish. Bu o'z navbatida nazariy jihatdan yaxshilanishga olib kelishi mumkin kompilyator optimallashtirishlari, Sekinroq disk raskadrovka va shunga o'xshash xususiyatlar sintaksis shakar.[6]

Garchi biron bir dastur o'qlarni qat'iyan talab qilmasa ham, ular zichlikning ko'p qismini umumlashtiradi funktsiya o'tishi aks holda sof, deklarativ kod kerak bo'ladi. Ular, shuningdek, dalda berishlari mumkin kodni qayta ishlatish dastur bosqichlari o'rtasida umumiy bog'lanishlarni berish orqali o'zlarining sinf ta'riflari. Umumiy ravishda turlarga tatbiq etish qobiliyati ham qayta ishlatishga yordam beradi va saqlaydi interfeyslar oddiy.[6]

Oklarning ba'zi bir kamchiliklari bor, shu jumladan o'q qonunlarini qondiradigan o'qni aniqlash uchun dastlabki harakatlar. Monadalarni amalga oshirish odatda osonroq bo'lganligi va o'qlarning qo'shimcha funktsiyalari keraksiz bo'lishi mumkinligi sababli, ko'pincha monadadan foydalanish afzalroqdir.[6] Ko'pchilikka tegishli bo'lgan yana bir masala funktsional dasturlash tuzadi, samarali kompilyatsiya qilish ichiga o'qlar bilan kod majburiy kompyuter tomonidan ishlatiladigan uslub ko'rsatmalar to'plamlari.[iqtibos kerak ]

Cheklovlar

Ni belgilash kerak bo'lgan talab tufayli arr sof funktsiyalarni ko'tarish funktsiyasi, o'qlarning qo'llanilishi cheklangan. Masalan, ikki tomonlama transformatsiyalar o'qlar bo'lishi mumkin emas, chunki foydalanishda faqat sof funktsiyani emas, balki uning teskarisini ham ta'minlash kerak bo'ladi. arr.[8] Bu shuningdek, keraksiz tarqalishni to'xtatadigan surish asosidagi reaktiv ramkalarni tasvirlash uchun o'qlardan foydalanishni cheklaydi. Xuddi shunday, qadriyatlarni birlashtirish uchun juftliklardan foydalanish qiyin kodlash uslubini keltirib chiqaradi, bu esa qiymatlarni qayta guruhlash uchun qo'shimcha kombinatorlarni talab qiladi va turli xil usullar bilan guruhlangan o'qlarning ekvivalenti to'g'risida asosiy savollarni tug'diradi. Ushbu cheklovlar ochiq muammo bo'lib qolmoqda va Umumlashtirilgan o'qlar kabi kengaytmalar[8] va N-ary FRP[9] ushbu muammolarni o'rganing.

Adabiyotlar

  1. ^ a b v d e Xyuz, Jon (2000 yil may). "Monadlarni o'qlarga umumlashtirish". Kompyuter dasturlash fanlari. 37 (1–3): 67–111. doi:10.1016 / S0167-6423 (99) 00023-4. ISSN  0167-6423.
  2. ^ Paterson, Ross (2003 yil 27 mart). "10-bob: Oklar va hisoblash" (PS.GZ). Gibbonlarda Jeremi; de Moor, Oege (tahrir). Dasturlashning zavqi. Palgrave Makmillan. 201-222 betlar. ISBN  978-1403907721. Olingan 10 iyun 2012.
  3. ^ Lindli, Sem; Vadler, Filip; Yallop, Jeremi (2010 yil yanvar). "Ok o'qi" (PDF). Funktsional dasturlash jurnali. 20 (1): 51–69. doi:10.1017 / S095679680999027X. hdl:1842/3716. ISSN  0956-7968. Olingan 10 iyun 2012.
  4. ^ Jeykobs, Bart; Xenen, Kris; Hasuo, Ichiro (2009). "Oklar uchun kategorik semantika". Funktsional dasturlash jurnali. 19 (3–4): 403–438. doi:10.1017 / S0956796809007308. hdl:2066/75278.
  5. ^ Atkey, Robert (2011 yil 8 mart). "Oklarning kategorik modeli nima?". Nazariy kompyuter fanidagi elektron yozuvlar. 229 (5): 19–37. doi:10.1016 / j.entcs.2011.02.014. ISSN  1571-0661.
  6. ^ a b v d e Xuz, Jon (2005). "Oklar bilan dasturlash" (PDF). Murakkab funktsional dasturlash. Murakkab funktsional dasturlash bo'yicha 5-Xalqaro yozgi maktab. 2004 yil 14–21 avgust. Tartu, Estoniya. Springer. 73–129 betlar. doi:10.1007/11546382_2. ISBN  978-3-540-28540-3. Olingan 10 iyun 2012.
  7. ^ a b v d e f g h men j Paterson, Ross (2002). "Control.Arrow". bazasi-4.5.0.0: Asosiy kutubxonalar. haskell.org. Arxivlandi asl nusxasi 2006 yil 13 fevralda. Olingan 10 iyun 2012.
  8. ^ a b Jozef, Adam Megacz (2014). "Umumlashtirilgan o'qlar" (PDF). UCB / EECS-2014-130-sonli texnik hisobot. EECS bo'limi, Kaliforniya universiteti, Berkli. Olingan 20 oktyabr 2018.
  9. ^ Sculthorpe, Neil (2011). Xavfsiz va samarali funktsional reaktiv dasturlash tomon (PDF) (PhD). Nottingem universiteti.

Tashqi havolalar