b"\n_START_ARTICLE_\nKalkulong lambda\n_START_PARAGRAPH_\nSa lohikang matematikal at agham pangkompyuter, ang kalkulong lambda na isinusulat ding \xce\xbb-kalkulo ang pormal na sistema para sa paglalarawan ng punsiyon, aplikasyon ng punsiyon at rekursiyon. Ang bahagi ng kalkulong lambda na mahalaga sa komputasyon ay tinatawag na walang-tayp na kalkulong lambda(untyped lambda calculus). Sa parehong may-tayp at walang-tayp na mga bersiyon, ang mga ideya mula sa kalkulong lambda ay nakatagpo ng aplikasyon sa larangan ng lohika, teoriya ng rekursiyon(komputabilidad) at linguistiks at may mahalagang papel na ginagampanan sa pagkakalikha ng teoriya ng mga wikang pamprograma kung saan ang walang-tayp ng kalkulong lambda ang orihinal na inspirasyon para sa pagpoprogramang punsiyonal partikular na ang Lisp at ang may-tayp na kalkulong lambda ay nagsisilbing pundasyon ng modernong mga sistemang tayp.\n_START_SECTION_\nPagkakatumbas na Alpha\n_START_PARAGRAPH_\nAng basikong anyon ng pagkakatumbas na mailalarawan sa mga terminong lambda ang pagkakatumbas na alpha. Ito ay nagsasaad na ang partikular na mapagpipilian ng binibigkis na bariabulo sa abstraksiyong lambda ay karaniwang hindi mahalaga._NEWLINE_Halimbawa, ang \xce\xbbx.x at \xce\xbby.y ay magkatumbas-na-alpha na mga terminong lambda na kumakatawan sa parehong punsiyong identidad._NEWLINE_Pansinin na ang mga terminong x at y ay hindi magkatumbas na alpha dahil ang mga ito ay hindi binibigkis sa isang abstraksiyong lambda. _NEWLINE_Sa maramign mga presentasyon, karaniwan na tinutukoy ang mga magkatumbas na alpha na mga terminong lambda._NEWLINE_Ang mga sumusunod na depinisyon ay kinakailangan upang mailarawan ang reduksiyong beta.\n_START_SECTION_\nMga malayang bariabulo\n_START_PARAGRAPH_\nAng mga malayang bariabulo ng isang termino ang mga bariabulo na hindi binibigkis sa isang abstraksiyong lambda. Ang ibig sabihin nito, ang mga malayang bariabulo ng x ay tanging x; ang mga malayang bariabulo ng \xce\xbbx.t ang mga malayang bariabulo ng  t na ang x ay inalis at ang mga malayang bariabulo ng ts ang unyon ng mga malayang bariabulo ng t at s._NEWLINE_Halimbawa, ang terminong lambda na kumakatawan sa identidad na \xce\xbbx.x ay walang mga malayang bariabulo ngunit ang konstanteng punsiyon na  \xce\xbbx.y ay may isang malayang bariabulo na y.\n_START_SECTION_\nReduksiyong beta\n_START_PARAGRAPH_\nAng reduksiyong beta ay nagsasaad na ang ang aplikasyong may anyong (\xce\xbbx.t)s ay lumiliit sa t[x\xc2\xa0:= s] (isinusulat ang (\xce\xbbx.t)s \xe2\x86\x92 t[x\xc2\xa0:= s] bilang konbinyenteng maiklingkamay(shorthand) para sa \xe2\x80\x9c(\xce\xbbx.t)s ay lumiliit sa beta sat[x\xc2\xa0:= s]\xe2\x80\x9d)._NEWLINE_Halimbawa, sa bawat s meron tayong (\xce\xbbx.x)s \xe2\x86\x92 x[x\xc2\xa0:= s] = s na nagpapakitang ang \xce\xbbx.x ang talagang identidad._NEWLINE_Gayundin, ang (\xce\xbbx.y)s \xe2\x86\x92 y[x\xc2\xa0:= s] = y ay nagpapakitang ang \xce\xbbx.y ay talagang isang konstanteng punsiyon._NEWLINE_Ang kalkulong lambda ay maaaring maunawaan bilang ginawang ideyal na wika ng pagpoprogramang punsiyonal gaya ng Haskell o Pamantayang ML._NEWLINE_Sa ilalim ng pananaw na ito, ang reduksiyong beta ay tumutugon sa hakbang komputasyon at sa walang-tayp na kalkulong lambda na ipinapakita rito, ang reduksiyon ay hindi kailangang magwakas. _NEWLINE_Halimbawa, tingnan ang terminong (\xce\xbbx.xx)(\xce\xbbx.xx)._NEWLINE_Dito, meron tayong (\xce\xbbx.xx)(\xce\xbbx.xx) \xe2\x86\x92 (xx)[x\xc2\xa0:= \xce\xbbx.xx] = (x[x\xc2\xa0:= \xce\xbbx.xx])(x[x\xc2\xa0:= \xce\xbbx.xx]) = (\xce\xbbx.xx)(\xce\xbbx.xx)._NEWLINE_Na ang ibig sabihin, ang termino ay lumiliit sa isang reduksiyong beta kaya ang reduksiyon ay hindi magwawakas._NEWLINE_Ang isa pang problem sa walang-tayp na kalkulong lambda ang kawalang kakayahan na makilala ang pagkakaiba sa pagitan ng iba't ibang uri ng data._NEWLINE_Halimbawa, maaari tayong magsulat ng punsiyon na tanging nagsasagawa ng operasyon sa mga bilang. Ngunit sa walang-tayp na kalkulong lambda, walang paraan upang maiwasan ang ating punsiyon na mailapat halimbawa sa mga katotohanang halaga(truth value) o mga tali(strings)._NEWLINE_Ang may-tayp na kalkulong lambda na ay nagtatangkang alisin ang mga hindi nag-aasal na mga termino hangga't posible.\n_START_SECTION_\n\xce\xb1-konbersiyon\n_START_PARAGRAPH_\nAng Alpha-konbersiyon na minsang kilala bilang alpha-renaming(alpha-muling pagpapangalan), ay pumapayag sa mga pangalan ng mga nakabigkis(bound) na bariabulo na mabago. Halimbawa, ang alpha-konbersiyon ng \xce\xbbx.x ay maaaring magbigay ng \xce\xbby.y. Ang terminong tanging magkaiba sa alpha-konbersiyon ay tinatawag na  \xce\xb1-magkatumbas. Sa kalimitang mga gamit sa kalkulong lambda, ang mga terminong \xce\xb1-magkatumbas ay tinuturing na magkatumbas._NEWLINE_Ang tiyak na mga patakaran para sa alpha-konbersiyon ay hindi buong walang kahalagahan. Una, kung alpha-kinokonberte(binabago) ang isang abstraksiyon, ang tanging mga bariabulong makikita na muling pinangalanan ang mga nakabigkis sa parehong abstraksiyon. Halimbawa, ang alpha-konbersiyon ng  \xce\xbbx.\xce\xbbx.x ay maaaring magresulta ng \xce\xbby.\xce\xbbx.x, ngunit hindi ito maaaring magresulta ng \xce\xbby.\xce\xbbx.y.  Ang huli ay may ibang kahulugan sa orihinal._NEWLINE_Ikalawa, ang ang alpha-konbersiyon ay hindi posible kung ito ay magreresulta sa bariabulong mabibihag ng ibang abstraksiyon. Halimbawa, kung papalitan natin ang x ng y sa \xce\xbbx.\xce\xbby.x, ating makukuha ang \xce\xbby.\xce\xbby.y, na hindi pareho._NEWLINE_Sa mga wikang pamprograma na may statikong(hindi nagbabagong) sakop, ang alpha-konbersiyon ay maaaring gamitin upang gawin ang resolusyon ng pangalan na mas simple sa pamamagitan ng pagsisiguro na walang pangalan ng bariabulo ang nagtatakip(ang bariabulong idineklara sa isang loob na sakop(scope) ay may parehong pangalan sa panlabas na sakop) ng pangalan sa naglalamang sakop(scope).\n_START_SECTION_\n\xce\xb2-reduksiyon\n_START_PARAGRAPH_\nAng beta-reduksiyon ay bumibihag ng ideyang ng aplikasyon ng punsiyon. ang beta-reduksiyon ay inilalarawan sa mga termino ng substitusyon: ang beta-reduksiyon ng _NEWLINE_B\xc2\xa0((\xce\xbbV.E) E\xe2\x80\xb2)\xc2\xa0 is E[V\xc2\xa0:= E\xe2\x80\xb2]._NEWLINE_Halimbawa, kung ipagpalagay ang ilang pagkakoda ng 2, 7, *, meron tayong sumusunod na mga \xce\xb2-reduksiyon: ((\xce\xbbn.n*2) 7) \xe2\x86\x92 7*2.\n_START_SECTION_\n\xce\xb7-konbersiyon\n_START_PARAGRAPH_\nAng eta-konbersiyon ay naghahayag ng ideya ng ekstensiyonalidad na sa kontekstong ito ay ang dalawang mga punsiyon ay pareho kung at tanging kung ang mga ito ay nagbibigay ng parehong resulta sa lahat ng mga argumento. Ang eta-konbersiyon ay nag-kokonberte sa pagitan ng \xce\xbbx.f x at f sa tuwing ang x ay hindi lumalabas na malaya sa f.\n_START_SECTION_\nMga anyong normal at konpluwensiya\n_START_PARAGRAPH_\nPara sa walang-tayp ng kalkulong lambda, ang \xce\xb2-reduksiyon bilang patakarang muling pagsulat ay hindi malakas na nagnonormalisa ni mahinang nagnonormalisa._NEWLINE_Gayunpaman, ang parehong malakas na nagnonormalisang mga termino at mga mahinang nagnonormalisang mga termino ay may unikong(unique o walang katulad) na anyong normal. Para sa mga malakas na nagnonormalisang mga termino, ang anumang stratehiyang reduksiyon ay ginagarantiya na magbibigay ng anyong normal samantalang para sa mahinang nagnonormalisang mga termino, ang ilang stratehiyang reduksiyon ay maaaring mabigong mahanap ito.\n_START_SECTION_\nPagkokoda ng mga tayp(type) ng data\n_START_PARAGRAPH_\nAng basikong kalkulong lambda ay maaaring gamitin upang imodelo ang mga boolean, aritmetika, mga straktura ng data, at rekursiyon gaya ng ipinapakita sa mga sumusunod na pang-ilalim na seksiyon."