लैम्ब्डा कैलकुलस: Difference between revisions
| Line 170: | Line 170: | ||
* सबसे बाहरी कोष्ठक हटा दिए जाते हैं: (''M'' ''N'') के अतिरिक्त ''M'' ''N''। | * सबसे बाहरी कोष्ठक हटा दिए जाते हैं: (''M'' ''N'') के अतिरिक्त ''M'' ''N''। | ||
* अनुप्रयोगों को साहचर्य छोड़ दिया जाता है: ((''M'' ''N'') ''P'') के अतिरिक्त MNP लिखा जा सकता है।<ref name="lambda-bound">{{cite web|url=http://www.lambda-bound.com/book/lambdacalc/node27.html|title=Example for Rules of Associativity|publisher=Lambda-bound.com|access-date=2012-06-18}}</ref> | * अनुप्रयोगों को साहचर्य छोड़ दिया जाता है: ((''M'' ''N'') ''P'') के अतिरिक्त MNP लिखा जा सकता है।<ref name="lambda-bound">{{cite web|url=http://www.lambda-bound.com/book/lambdacalc/node27.html|title=Example for Rules of Associativity|publisher=Lambda-bound.com|access-date=2012-06-18}}</ref> | ||
* जब सभी चर एकल-अक्षर वाले हों, तो अनुप्रयोगों में स्थान छोड़ा जा सकता है: MNP के अतिरिक्त M N | * जब सभी चर एकल-अक्षर वाले हों, तो अनुप्रयोगों में स्थान छोड़ा जा सकता है: MNP के अतिरिक्त M N P है।<ref>{{cite web |title=The Basic Grammar of Lambda Expressions |url=https://softoption.us/node/33 |website=SoftOption |quote=Some other systems use juxtaposition to mean application, so 'ab' means 'a@b'. This is fine except that it requires that variables have length one so that we know that 'ab' is two variables juxtaposed not one variable of length 2. But we want to labels like 'firstVariable' to mean a single variable, so we cannot use this juxtaposition convention.}}</ref> | ||
* एक अमूर्त का निकाय नियमित व्यंजक का विस्तार करता है: λx.M N का अर्थ है λx.(M N) और नहीं (λx.M) N | * एक अमूर्त का निकाय नियमित व्यंजक का विस्तार करता है: λx.M N का अर्थ है λx.(M N) और नहीं (λx.M) N है। | ||
* अमूर्तता का एक क्रम संकुचित होता है: λx.λy.λz.N को λxyz.N के रूप में संक्षिप्त किया गया है।<ref name="Selinger">{{Citation|first=Peter|last=Selinger|title=Lecture Notes on the Lambda Calculus|year=2008|page=9|publisher=Department of Mathematics and Statistics, University of Ottawa|url=http://www.mathstat.dal.ca/~selinger/papers/lambdanotes.pdf|bibcode=2008arXiv0804.3434S|volume=0804|arxiv=0804.3434|issue=class: cs.LO}}</ref><ref name="lambda-bound" /> | * अमूर्तता का एक क्रम संकुचित होता है: λx.λy.λz.N को λxyz.N के रूप में संक्षिप्त किया गया है।<ref name="Selinger">{{Citation|first=Peter|last=Selinger|title=Lecture Notes on the Lambda Calculus|year=2008|page=9|publisher=Department of Mathematics and Statistics, University of Ottawa|url=http://www.mathstat.dal.ca/~selinger/papers/lambdanotes.pdf|bibcode=2008arXiv0804.3434S|volume=0804|arxiv=0804.3434|issue=class: cs.LO}}</ref><ref name="lambda-bound" /> | ||
| Line 205: | Line 205: | ||
दूसरा, α-रूपांतरण संभव नहीं है यदि इसके परिणामस्वरूप एक भिन्न अमूर्तता द्वारा एक चर पर प्रग्रहण कर लिया जाएगा। उदाहरण के लिए, यदि हम λx.λy.x में x को y से प्रतिस्थापित करते हैं, तो हमें λy.λy.y मिलता है, जो बहुत समान नहीं है। | दूसरा, α-रूपांतरण संभव नहीं है यदि इसके परिणामस्वरूप एक भिन्न अमूर्तता द्वारा एक चर पर प्रग्रहण कर लिया जाएगा। उदाहरण के लिए, यदि हम λx.λy.x में x को y से प्रतिस्थापित करते हैं, तो हमें λy.λy.y मिलता है, जो बहुत समान नहीं है। | ||
[[नाम संकल्प (प्रोग्रामिंग भाषाएं)|प्रोग्रामिंग भाषाओं]] में स्थिर सीमा के साथ, α-रूपांतरण का उपयोग नाम विभेदन (प्रोग्रामिंग भाषा) को सामान्य बनाने के लिए किया जा सकता है, यह सुनिश्चित करके कि कोई चर नाम किसी नाम को विस्तार [[गुंजाइश (प्रोग्रामिंग)|(प्रोग्रामिंग)]] में नहीं रखता है ( विभेदन को सामान्य बनाने के लिए के लिए α-नामकरण देखें)। | |||
डी ब्रुइज़न इंडेक्स संकेतन में, कोई भी दो α-समतुल्य पद रचना दृष्टि से समान हैं। | डी ब्रुइज़न इंडेक्स संकेतन में, कोई भी दो α-समतुल्य पद रचना दृष्टि से समान हैं। | ||
| Line 277: | Line 277: | ||
: {{Mono|1=MULT := λ''m''.λ''n''.λ''f''.''m'' (''n'' ''f'')}}<ref name="Selinger" />वैकल्पिक | : {{Mono|1=MULT := λ''m''.λ''n''.λ''f''.''m'' (''n'' ''f'')}}<ref name="Selinger" />वैकल्पिक | ||
: {{Mono|1=MULT := λ''m''.λ''n''.''m'' (PLUS ''n'') 0}} | : {{Mono|1=MULT := λ''m''.λ''n''.''m'' (PLUS ''n'') 0}} | ||
गुणा करने के बाद से {{Mono|''m''}} और {{Mono|''n''}} जोड़ने को | गुणा करने के बाद से {{Mono|''m''}} और {{Mono|''n''}} जोड़ने को पुनरावर्ती के समान है {{Mono|''n''}} फलन {{Mono|''m''}} बार और फिर इसे शून्य पर प्रयुक्त करना। घातांक का चर्च अंकों में सामान्य प्रतिपादन है, अर्थात् | ||
: {{Mono|1=POW := λ''b''.λ''e''.''e'' ''b''}}<ref name="BarendregtBarendsen" />द्वारा परिभाषित पूर्ववर्ती फलन {{Mono|1=PRED ''n'' = ''n'' − 1}} एक सकारात्मक पूर्णांक के लिए {{Mono|''n''}} और {{Mono|1=PRED 0 = 0}} | : {{Mono|1=POW := λ''b''.λ''e''.''e'' ''b''}}<ref name="BarendregtBarendsen" /> द्वारा परिभाषित पूर्ववर्ती फलन {{Mono|1=PRED ''n'' = ''n'' − 1}} एक सकारात्मक पूर्णांक के लिए {{Mono|''n''}} और {{Mono|1=PRED 0 = 0}} अपेक्षाकृत अधिक कठिन है। सूत्र | ||
: {{Mono|1=PRED := λ''n''.λ''f''.λ''x''.''n'' (λ''g''.λ''h''.''h'' (''g'' ''f'')) (λ''u''.''x'') (λ''u''.''u'')}} | : {{Mono|1=PRED := λ''n''.λ''f''.λ''x''.''n'' (λ''g''.λ''h''.''h'' (''g'' ''f'')) (λ''u''.''x'') (λ''u''.''u'')}} | ||
आगमनात्मक रूप से दिखा कर मान्य किया जा सकता है कि यदि T दर्शाता है {{Mono|(λ''g''.λ''h''.''h'' (''g'' ''f''))}}, तब {{Mono|1=T<sup>(''n'')</sup>(λ''u''.''x'') = (λ''h''.''h''(''f''<sup>(''n''−1)</sup>(''x'')))}} के लिए {{Mono|''n'' > 0}}. की दो अन्य परिभाषाएँ {{Mono|PRED}} नीचे दिए गए हैं, एक तर्क और दूसरा जोड़ों का उपयोग कर रहा है। पूर्ववर्ती फलन के साथ, व्यवकलन प्रत्यक्ष है। परिभाषित | आगमनात्मक रूप से दिखा कर मान्य किया जा सकता है कि यदि T दर्शाता है {{Mono|(λ''g''.λ''h''.''h'' (''g'' ''f''))}}, तब {{Mono|1=T<sup>(''n'')</sup>(λ''u''.''x'') = (λ''h''.''h''(''f''<sup>(''n''−1)</sup>(''x'')))}} के लिए {{Mono|''n'' > 0}}. की दो अन्य परिभाषाएँ {{Mono|PRED}} नीचे दिए गए हैं, एक तर्क और दूसरा जोड़ों का उपयोग कर रहा है। पूर्ववर्ती फलन के साथ, व्यवकलन प्रत्यक्ष है। परिभाषित | ||
| Line 306: | Line 306: | ||
और {{Mono|1=''m'' = ''n''}}, यदि {{Mono|LEQ ''m'' ''n''}} और {{Mono|LEQ ''n'' ''m''}}, संख्यात्मक समानता के लिए एक निर्धारक का निर्माण करना प्रत्यक्ष है। | और {{Mono|1=''m'' = ''n''}}, यदि {{Mono|LEQ ''m'' ''n''}} और {{Mono|LEQ ''n'' ''m''}}, संख्यात्मक समानता के लिए एक निर्धारक का निर्माण करना प्रत्यक्ष है। | ||
निर्धारक की उपलब्धता और की उपरोक्त परिभाषा {{Mono|TRUE}} और {{Mono|FALSE}} लैम्ब्डा गणना में if-then-else | निर्धारक की उपलब्धता और की उपरोक्त परिभाषा {{Mono|TRUE}} और {{Mono|FALSE}} लैम्ब्डा गणना में if-then-else पद लिखना सुविधाजनक बनाएं। उदाहरण के लिए, पूर्ववर्ती फलन को इस प्रकार परिभाषित किया जा सकता है: | ||
: {{Mono|1=PRED := λ''n''.''n'' (λ''g''.λ''k''.ISZERO (''g'' 1) ''k'' (PLUS (''g'' ''k'') 1)) (λ''v''.0) 0 }} | : {{Mono|1=PRED := λ''n''.''n'' (λ''g''.λ''k''.ISZERO (''g'' 1) ''k'' (PLUS (''g'' ''k'') 1)) (λ''v''.0) 0 }} | ||
जिसे आगमनात्मक रूप से दिखा कर सत्यापित किया जा सकता है {{Mono|''n'' (λ''g''.λ''k''.ISZERO (''g'' 1) ''k'' (PLUS (''g'' ''k'') 1)) (λ''v''.0)}} जोड़ | जिसे आगमनात्मक रूप से दिखा कर सत्यापित किया जा सकता है {{Mono|''n'' (λ''g''.λ''k''.ISZERO (''g'' 1) ''k'' (PLUS (''g'' ''k'') 1)) (λ''v''.0)}} जोड़ {{Mono|''n''}} -1 के लिए फलन {{Mono|''n''}} > 0 है। | ||
=== | === युग्म === | ||
एक | एक युग्म (2-ट्यूपल) {{Mono|TRUE}} और {{Mono|FALSE}}, युग्म के लिए चर्च कोडिंग का उपयोग करके संदर्भ में परिभाषित किया जा सकता है। उदाहरण के लिए, {{Mono|PAIR}} एनकैप्सुलेट ({{Mono|''x''}},{{Mono|''y''}}), {{Mono|FIRST}} जोड़ी का पहला तत्व देता है, और {{Mono|SECOND}} प्रतिफल देते है। | ||
: {{Mono|1=PAIR := λ''x''.λ''y''.λ''f''.''f'' ''x'' ''y''}} | : {{Mono|1=PAIR := λ''x''.λ''y''.λ''f''.''f'' ''x'' ''y''}} | ||
| Line 318: | Line 318: | ||
: {{Mono|1=NIL := λ''x''.TRUE }} | : {{Mono|1=NIL := λ''x''.TRUE }} | ||
: {{Mono|1=NULL := λ''p''.''p'' (λ''x''.λ''y''.FALSE)}} | : {{Mono|1=NULL := λ''p''.''p'' (λ''x''.λ''y''.FALSE)}} | ||
एक लिंक की गई सूची को रिक्त सूची के लिए या तो शून्य के रूप में परिभाषित किया जा सकता है, या {{Mono|PAIR}} | एक लिंक की गई सूची को रिक्त सूची के लिए या तो NIL शून्य के रूप में परिभाषित किया जा सकता है, या {{Mono|PAIR}} और एक छोटी सूची के रूप में परिभाषित किया जा सकता है। निर्धारक {{Mono|NULL}} मूल्य के लिए {{Mono|NIL}} परीक्षण करता है। (वैकल्पिक रूप से, {{Mono|1=NIL := FALSE}} के साथ निर्माण {{Mono|''l'' (λ''h''.λ''t''.λ''z''.deal_with_head_''h''_and_tail_''t'') (deal_with_nil)}} स्पष्ट NULL परीक्षण की आवश्यकता को कम करता है)। | ||
युग्म के उपयोग के एक उदाहरण के रूप में, शिफ्ट-एंड-इन्क्रीमेंट फंक्शन जो चित्रित {{Mono|(''m'', ''n'')}} को {{Mono|(''n'', ''n'' + 1)}} के रूप में परिभाषित किया जा सकता है | |||
: {{Mono|1=Φ := λ''x''.PAIR (SECOND ''x'') (SUCC (SECOND ''x''))}} | : {{Mono|1=Φ := λ''x''.PAIR (SECOND ''x'') (SUCC (SECOND ''x''))}} | ||
जो हमें पूर्ववर्ती फलन का संभव्यता सबसे पारदर्शी संस्करण देने की स्वीकृति देता है: | जो हमें पूर्ववर्ती फलन का संभव्यता सबसे पारदर्शी संस्करण देने की स्वीकृति देता है: | ||
| Line 326: | Line 326: | ||
== अतिरिक्त प्रोग्रामिंग | == अतिरिक्त प्रोग्रामिंग तकनीकें == | ||
लैम्ब्डा गणना के लिए प्रोग्रामिंग | लैम्ब्डा गणना के लिए प्रोग्रामिंग शैली का समूह है। इनमें से कई मूल रूप से सिमेंटिक्स (कंप्यूटर विज्ञान) के लिए एक नींव के रूप में लैम्ब्डा गणना का उपयोग करने के संदर्भ में विकसित किए गए थे, प्रभावी रूप से लैम्ब्डा गणना का उपयोग [[निम्न-स्तरीय प्रोग्रामिंग भाषा]] के रूप में किया गया था। क्योंकि कई प्रोग्रामिंग भाषाओं में लैम्ब्डा गणना (या कुछ समान) को एक खंड के रूप में सम्मिलित किया गया है, इन तकनीकों का उपयोग व्यावहारिक [[प्रोग्रामिंग मुहावरा|प्रोग्रामिंग भाषा]] को भी देखा जाता है, लेकिन तब इसे अस्पष्ट या अयोग्य माना जा सकता है। | ||
=== नामित स्थिरांक === | === नामित स्थिरांक === | ||
| Line 364: | Line 364: | ||
वास्तव में, इसके लिए कई संभावित परिभाषाएँ हैं {{Mono|FIX}} संक्रियक, उनमें से सबसे सामान्य हैं: | वास्तव में, इसके लिए कई संभावित परिभाषाएँ हैं {{Mono|FIX}} संक्रियक, उनमें से सबसे सामान्य हैं: | ||
: | : {{Mono|1='''Y''' := λ''g''.(λ''x''.''g'' (''x'' ''x'')) (λ''x''.''g'' (''x'' ''x''))}} | ||
लैम्ब्डा गणना में, {{Mono|'''Y''' ''g''}}का निश्चित बिन्दु है {{Mono|''g''}}, जैसा कि इसका विस्तार होता है: | लैम्ब्डा गणना में, {{Mono|'''Y''' ''g''}}का निश्चित बिन्दु है {{Mono|''g''}}, जैसा कि इसका विस्तार होता है: | ||
Revision as of 20:36, 23 February 2023
लैम्ब्डा गणना (जिसे λ-गणना के रूप में भी लिखा जाता है) गणितीय तर्क में एक औपचारिक प्रणाली है जो चर(वेरिएबल) बंधन और प्रतिस्थापन का उपयोग करके फलन अमूर्त और अनुप्रयोग के आधार पर अभिकलन व्यक्त करती है। यह संगणना का एक सार्वभौमिक मॉडल है जिसका उपयोग किसी भी ट्यूरिंग मशीन (परिगणन युक्ति) को अनुकरण करने के लिए किया जा सकता है। इसे 1930 के दशक में गणितज्ञ अलोंजो चर्च द्वारा गणित की नींव में अपने शोध के भाग के रूप में प्रस्तुत किया गया था।
लैम्ब्डा गणना में लैम्ब्डा शब्द का निर्माण और उन पर कलन संक्रिया करना सम्मिलित है। लैम्ब्डा गणना के सबसे सामान्य रूप में, केवल निम्नलिखित नियमों का उपयोग करके शब्द बनाए जाते हैं:[lower-alpha 1]
- -चर, एक वर्ण या शृंखला एक पैरामीटर या गणितीय/तार्किक मान का प्रतिनिधित्व करता है।
- – अमूर्तता, फलन परिभाषा ( लैम्ब्डा शब्द है)। चर व्यंजक में बंध जाता है।
- - अनुप्रयोग, फलन को एक तर्क पर प्रयुक्त करने के लिए. और लैम्ब्डा शर्तें हैं।
न्यूनीकरण संक्रिया में सम्मिलित हैं:
- - α-रूपांतरण, व्यंजक में बद्ध चरों का नाम परिवर्तित करना। नाम संघट्टन से बचने के लिए उपयोग किया जाता है।
- - β-अवनति,[lower-alpha 2] अमूर्त के निकाय में तर्क व्यंजक के साथ बद्ध चर को परिवर्तित करना।
यदि डी ब्रुइज़न अनुक्रमण का उपयोग किया जाता है, तो α-रूपांतरण की आवश्यकता नहीं है क्योंकि कोई नाम संघट्टन नहीं होगा। यदि न्यूनीकरण के चरणों का पुनरावृत्त प्रयोग अंततः समाप्त हो जाता है, तो चर्च-रॉसर प्रमेय द्वारा यह एक β-सामान्य रूप उत्पन्न करेगा।
एक सार्वभौमिक लैम्ब्डा फलन का उपयोग करते समय चर नामों की आवश्यकता नहीं होती है, जैसे कि आयोटा और बिन्दु, जो किसी भी फलन गतिविधि को विभिन्न संयोजनों में स्वयं कॉल करके बना सकता है।
स्पष्टीकरण और अनुप्रयोग
लैम्ब्डा गणना ट्यूरिंग पूर्णता है, अर्थात यह गणना का एक सार्वभौमिक मॉडल है जिसका उपयोग किसी भी ट्यूरिंग मशीन को अनुकरण करने के लिए किया जा सकता है।[2] इसका समनाम, ग्रीक अक्षर लैम्ब्डा (λ), लैम्ब्डा व्यंजक और लैम्ब्डा पदों में मुक्त चर (वेरिएबल) और बद्ध चर को एक फलन (गणित) में एक चर को निरूपित करने के लिए उपयोग किया जाता है।
लैम्ब्डा गणना अनटाइप्ड या टाइप किया हुआ हो सकता है। टाइप किए गए लैम्ब्डा गणना में, फलन केवल तभी प्रयुक्त किए जा सकते हैं जब वे दिए गए इनपुट प्रकार के डेटा को स्वीकार करने में सक्षम हों। टाइप की गई लैम्ब्डा कैलकुली, अनटाइप्ड लैम्ब्डा गणना की तुलना में दुर्बल होती है, जो इस लेख का प्राथमिक विषय है, इस अर्थ में कि टाइप की गई लैम्ब्डा कैलकुली अनटाइप्ड गणना की तुलना में कम व्यक्त कर सकती है, लेकिन दूसरी ओर टाइप की गई लैम्ब्डा कैलकुली अधिक वस्तुओ को सिद्ध करने की स्वीकृति देती है; सामान्य टाइप किए गए लैम्ब्डा गणना में, उदाहरण के लिए, यह एक प्रमेय है कि हर सामान्य टाइप किए गए लैम्ब्डा-पद के लिए प्रत्येक मूल्यांकन विधि समाप्त हो जाती है, जबकि एक कारण यह है कि कई अलग-अलग टाइप किए गए लैम्ब्डा कैलकुली, गणना के बारे में प्रबल प्रमेयों को प्रमाणित करने में सक्षम होने के बिना और अधिक करने का विचार रखते हैं।
लैम्ब्डा गणना के गणित, दर्शन,[3] भाषा विज्ञान,[4][5] और कंप्यूटर विज्ञान[6] और कई अलग-अलग क्षेत्रों में अनुप्रयोग हैं। लैंबडा गणना ने प्रोग्रामिंग भाषा सिद्धांत के विकास में महत्वपूर्ण भूमिका निभाई है। कार्यात्मक प्रोग्रामिंग भाषाएं लैम्ब्डा गणना को प्रयुक्त करती हैं। श्रेणी सिद्धांत में लैम्ब्डा गणना भी एक वर्तमान शोध विषय है।[7]
इतिहास
लैम्ब्डा गणना को गणितज्ञ अलोंजो चर्च द्वारा 1930 के दशक में गणित की नींव की जांच के एक भाग के रूप में प्रस्तुत किया गया था।[8][lower-alpha 3] मूल प्रणाली को 1935 में संगति के रूप में दिखाया गया था जब स्टीफन क्लेन और जे.बी. रोसेर ने क्लेन-रोसेर विरोधाभास विकसित किया था।[9][10]
इसके बाद, 1936 में चर्च ने संगणना से संबंधित भाग को ही अलग कर दिया और प्रकाशित कर दिया, जिसे अब अनटाइप्ड लैम्ब्डा गणना कहा जाता है।[11] 1940 में, उन्होंने संगणनात्मक रूप से दुर्बल, लेकिन तार्किक रूप से सुसंगत प्रणाली भी प्रस्तुत की, जिसे सामान्य रूप से टाइप किए गए लैम्ब्डा गणना के रूप में जाना जाता है।[12]
1960 के दशक तक जब प्रोग्रामिंग भाषाओं से इसके संबंध को स्पष्ट किया गया था, लैम्ब्डा गणना केवल एक औपचारिकता थी। प्राकृतिक भाषा के सिमेन्टिक में रिचर्ड मोंटेग और अन्य भाषाविदों के अनुप्रयोगों के लिए धन्यवाद, लैम्ब्डा गणना ने भाषाविज्ञान[13] और कंप्यूटर विज्ञान[14] दोनों में एक सम्मानजनक स्थान प्राप्त करना प्रारंभ कर दिया है।
लैम्ब्डा प्रतीक की उत्पत्ति
चर्च द्वारा ग्रीक अक्षर लैम्ब्डा (λ) के उपयोग के कारण पर कुछ अनिश्चितता है क्योंकि लैम्ब्डा कैलकुस (गणना) में फलन-अमूर्तता के लिए अंकन संभव्यता चर्च द्वारा विरोधाभास स्पष्टीकरण के कारण हो सकता है। कार्डोन और हिंडले (2006) के अनुसार:
हालांकि, चर्च ने "λ" संकेतन क्यों चयन किया? [1964 में हेराल्ड डिक्सन को एक अप्रकाशित पत्र] में उन्होंने स्पष्ट रूप से कहा कि यह व्हाइटहेड और रसेल द्वारा वर्ग-अमूर्तता के लिए उपयोग किए जाने वाले "" अंकन से आया है। "" को पहले "" को संशोधित करके वर्ग-अमूर्तता से फलन-अमूर्तता को अलग करने के लिए, '''' को " से "λ" मे परिवर्तित किया जाता है।
इस उत्पत्ति को [रोसर, 1984, पृष्ठ 338] में भी बताया गया था। दूसरी ओर, अपने बाद के वर्षों में चर्च ने दो जांचकर्ताओं को बताया कि चयन अधिक आकस्मिक था: एक प्रतीक की आवश्यकता थी और λ चयन किया गया।[15]
डाना स्कॉट ने भी विभिन्न सार्वजनिक व्याख्यानों में इस प्रश्न को संबोधित किया है। स्कॉट बताते हैं कि उन्होंने एक बार चर्च के पूर्व छात्र और दामाद जॉन डब्ल्यू एडिसन जूनियर से लैम्ब्डा प्रतीक की उत्पत्ति के बारे में एक प्रश्न किया था, जिन्होंने तब अपने ससुर को एक पोस्टकार्ड लिखा था:
प्रिय प्रोफेसर चर्च,
रसेल के पास आईओटा संक्रियक था, हिल्बर्ट के पास एप्सिलॉन संक्रियक था। आपने अपने संक्रियक के लिए लैम्ब्डा क्यों चुना?
स्कॉट के अनुसार, चर्च की पूरी प्रतिक्रिया में पोस्टकार्ड को निम्नलिखित टिप्पणी "एनी, मीनी, मिनी, मो" के साथ वापस करना सम्मिलित था।
अनौपचारिक विवरण
कारण
संगणनीय फलन कंप्यूटर विज्ञान और गणित के अंदर एक मौलिक अवधारणा है। लैम्ब्डा गणना संगणना के लिए सामान्य अर्थ कंप्यूटर विज्ञान प्रदान करता है जो औपचारिक रूप से अभिकलन के गुणों का अध्ययन करने के लिए उपयोगी होते हैं। लैम्ब्डा गणना में दो सरलीकरण सम्मिलित हैं जो इसके अर्थ को सामान्य बनाते हैं। पहला सरलीकरण यह है कि लैम्ब्डा गणना फलन को नामरहित रूप से मानता है; यह उन्हें स्पष्ट नाम नहीं देता है। उदाहरण के लिए, फलन
के रूप में अस्पष्ट रूप में पुनः लिखा जा सकता है
(जिसे टपल के रूप में पढ़ा जाता है x और y मानचित्रित है ).[lower-alpha 4] इसी प्रकार, फलन
के रूप में अस्पष्ट रूप में पुनः लिखा जा सकता है
जहां इनपुट को केवल उसी के लिए मैप किया जाता है।[lower-alpha 4]
दूसरा सरलीकरण यह है कि लैम्ब्डा गणना केवल एक इनपुट के फलनों का उपयोग करता है। एक सामान्य फलन जिसमें दो इनपुट की आवश्यकता होती है, उदाहरण के लिए फलन, एक समतुल्य फलन में पुनः काम किया जा सकता है जो एकल इनपुट को स्वीकार करता है, और आउटपुट के रूप में एक और फलन देता है, जो बदले में एकल इनपुट स्वीकार करता है। उदाहरण के लिए,
में पुन: फलन किया जा सकता है
यह विधि, जिसे विच्छेदन के रूप में जाना जाता है, एक ऐसे फलन (फलन) को रूपांतरित करती है जो एक तर्क के साथ प्रत्येक फलन की श्रृंखला में कई तर्कों को लेता है।
कार्यात्मक अनुप्रयोग तर्कों के लिए फलन (5, 2), एक बार में प्राप्त होता है
- ,
जबकि विच्छेदन संस्करण के मूल्यांकन के लिए एक और चरण की आवश्यकता है
- // आंतरिक व्यंजक में 5 के साथ x की परिभाषा का प्रयोग किया गया है। यह β-अवनति जैसा है।
- // की परिभाषा का प्रयोग के साथ किया जाता है पुनः, β-अवनति के समान।
समान परिणाम पर पहुंचने के लिए।
लैम्ब्डा गणना
लैम्ब्डा गणना में लैम्ब्डा शर्तों की एक भाषा होती है, जिसे एक निश्चित औपचारिक सिंटैक्स द्वारा परिभाषित किया जाता है, और लैम्ब्डा शर्तों में कुशलतापूर्वक प्रयोग करने के लिए परिवर्तन नियमों का एक समुच्चय होता है। इन परिवर्तन नियमों को एक समान सिद्धांत या परिचालन परिभाषा के रूप में देखा जा सकता है।
जैसा कि ऊपर बताया गया है, कोई नाम नहीं होने के कारण, लैम्ब्डा गणना में सभी फलन अज्ञात फलन हैं। वे केवल एक निविष्ट चर को स्वीकार करते हैं, इसलिए विच्छेदन का उपयोग कई चर के फलनों को प्रयुक्त करने के लिए किया जाता है।
लैम्ब्डा शर्तें
लैम्ब्डा गणना का सिंटैक्स कुछ व्यंजक को वैध लैम्ब्डा गणना व्यंजक के रूप में परिभाषित करता है और कुछ अमान्य के रूप में, जैसे वर्णों के कुछ शृंखला मान्य C(प्रोग्रामिंग भाषा) प्रोग्राम हैं और कुछ नहीं हैं। एक मान्य लैम्ब्डा गणना व्यंजक को लैम्ब्डा शर्ते कहा जाता है।
निम्नलिखित तीन नियम एक आगमनात्मक परिभाषा देते हैं जिसे सभी वाक्यगत रूप से मान्य लैम्ब्डा पदों के निर्माण के लिए प्रयुक्त किया जा सकता है:[lower-alpha 5]
- चर x अपने आप में एक वैध लैम्ब्डा पद है।
- यदि t एक लैम्ब्डा पद है, और x एक चर है, तो [lower-alpha 6] एक लैम्ब्डा पद है (जिसे अमूर्त कहा जाता है);
- यदि t और s लैम्ब्डा पद हैं, फिर एक लैम्ब्डा पद है (जिसे अनुप्रयोग कहा जाता है)।
लैम्ब्डा शब्द और कुछ नहीं है। इस प्रकार एक लैम्ब्डा पद मान्य है यदि और केवल यदि इसे इन तीन नियमों के पुनरावृत्त अनुप्रयोग से प्राप्त किया जा सकता है। हालाँकि, कुछ कोष्ठकों को कुछ नियमों के अनुसार छोड़ा जा सकता है। उदाहरण के लिए, सबसे बाहरी कोष्ठक सामान्य रूप से नहीं लिखे जाते हैं। नीचे संकेतन देखें।
अमूर्तता § अज्ञात फलन को दर्शाता है[lower-alpha 7] जो एकल इनपुट x लेता है और t देता है। उदाहरण के लिए, फलन के लिए एक अमूर्तता है शब्द का उपयोग करके के लिए t नाम अमूर्तता का उपयोग करते समय अनावश्यक है। चर x पद t मे परिबद्ध करता है। अमूर्त के साथ एक फलन की परिभाषा केवल फलन को स्थापित करती है, लेकिन इसे प्रयुक्त नहीं करती है।
अनुप्रयोग इनपुट के लिए फलन के अनुप्रयोग का प्रतिनिधित्व करता है अर्थात उत्पन्न करने के लिए इनपुट s पर फलन t को कॉल करने के लिए फलन का प्रतिनिधित्व करता है।
परिवर्तनीय घोषणा के लैम्ब्डा गणना में कोई अवधारणा नहीं है। एक परिभाषा में जैसे (अर्थात ), लैम्ब्डा गणना में y एक चर है जिसे अभी तक परिभाषित नहीं किया गया है। अमूर्त सिमेन्टिक रूप से मान्य है, और एक ऐसे फलन का प्रतिनिधित्व करता है जो y इनपुट को अभी तक अज्ञात में जोड़ता है।
कोष्ठक का उपयोग किया जा सकता है और शर्तों को स्पष्ट करने के लिए इसकी आवश्यकता हो सकती है। उदाहरण के लिए,
- जो के प्रारूप मे है- एक अमूर्त, और
- जो के प्रारूप मे है- अनुप्रयोग। उदाहरण 1 और 2 अलग-अलग पदों को दर्शाते हैं; हालाँकि उदाहरण 1 एक फलन परिभाषा है, जबकि उदाहरण 2 अनुप्रयोग है।
यहाँ, उदाहरण 1 एक फलन को परिभाषित करता है , जहां है , अनुप्रयोग करने का परिणाम x के लिए, जबकि उदाहरण 2 है; लैम्ब्डा पद है। इनपुट N पर प्रयुक्त किया जाना चाहिए। उदाहरण 1 और 2 सर्वसमिका फलन का मूल्यांकन करेंगे।
फलन जो फलन पर प्रवर्तित करते
लैम्ब्डा गणना में, फलनों को 'प्रथम श्रेणी मान' के रूप में लिया जाता है, इसलिए फलन को इनपुट के रूप में उपयोग किया जा सकता है, या अन्य फलन से आउटपुट के रूप में वापस किया जा सकता है।
उदाहरण के लिए, सर्वसमिका फलन का प्रतिनिधित्व करता है, , और प्रयुक्त किए गए सर्वसमिका फलन का प्रतिनिधित्व करता है इसके अतिरिक्त स्थिर फलन का प्रतिनिधित्व करता है , वह फलन जो हमेशा देता है, फिर इनपुट कोई भी हो। लैम्ब्डा गणना में, फलन अनुप्रयोग को बायाँ साहचर्य के रूप में माना जाता है, ताकि का तात्पर्य हो।
समतुल्यता और अवनति की कई धारणाएँ हैं जो लैम्ब्डा पदों को समतुल्य लैम्ब्डा पदों में कम करने की स्वीकृति देती हैं।
अल्फा तुल्यता
तुल्यता का एक मूल रूप, जिसे लैम्ब्डा पदों पर परिभाषित किया जा सकता है, अल्फा तुल्यता है। यह अंतर्ज्ञान को प्रग्रहण है कि एक बाध्य चर का विशेष विकल्प, एक अमूर्तता में, (सामान्य रूप से) कोई अंतर नहीं है। उदाहरण के लिए, और अल्फा-समतुल्य लैम्ब्डा पद हैं, और वे दोनों एक ही फलन (सर्वसमिका फलन) का प्रतिनिधित्व करते हैं। शर्तें और अल्फा-समतुल्य नहीं हैं, क्योंकि वे एक अमूर्तता में परिबद्ध नहीं हैं। कई प्रस्तुतियों में, अल्फा-समतुल्य लैम्ब्डा पदों की सर्वसमिका करना सामान्य है।
β-अवनति को परिभाषित करने में सक्षम होने के लिए निम्नलिखित परिभाषाएँ आवश्यक हैं:
मुक्त चर
मुक्त चर[lower-alpha 8] एक पद के वे चर हैं जो एक अमूर्तता से परिबद्ध नहीं हैं। किसी व्यंजक के मुक्त चरों के समुच्चय को आगमनात्मक रूप से परिभाषित किया जाता है:
- के मुक्त चर सिर्फ
- के मुक्त चर का समुच्चय सिद्धांत के मुक्त चरों का समुच्चय है , लेकिन को हत्या दिया गया
- के मुक्त चर का समुच्चय सिद्धांत के मुक्त चरों के समुच्चय है और के मुक्त चर का समुच्चय का संयोजन है।
उदाहरण के लिए, सर्वसमिका का प्रतिनिधित्व करने वाला लैम्ब्डा पद कोई मुक्त चर नहीं है, लेकिन फलन एक मुक्त चर है।
प्रग्रहण-परिहरण प्रतिस्थापन
एक मुक्त चर के प्रग्रहण से बचने के लिए चर में एक व्यवस्थित परिवर्तन एक कार्यात्मक प्रोग्रामिंग भाषा में त्रुटि का परिचय दे सकता है, जहां फलन प्रथम श्रेणी के स्थानिक हैं।[16]
मान लीजिए , और लैम्ब्डा शर्तें हैं और और चर हैं। अंकन का प्रतिस्थापन दर्शाता है के लिए में प्रग्रहण से बचने के तरीके में। इसे इस प्रकार परिभाषित किया गया है:
- ; के स्थान पर सिर्फ है,
- यदि ; इसके लिए प्रतिस्थापित गतिविधि करते समय सिर्फ है,
- ; प्रतिस्थापन चर के आगे के अनुप्रयोग के लिए वितरित करता है
- ; यद्यपि पर प्रतिचित्रित किया गया है ,बाद मे सभी को लैम्ब्डा फलन नहीं बदलेगा
- यदि और के मुक्त चरों में नहीं है चर के लिए भिन्न कहा जाता है।
उदाहरण के लिए, , और
नवीनता की स्थिति (उसकी आवश्यकता है का मुक्त और बाध्य चर है) यह सुनिश्चित करने के लिए महत्वपूर्ण है कि प्रतिस्थापन फलनों के अर्थ को नहीं बदलता है। उदाहरण के लिए, एक प्रतिस्थापन जो नवीनता की स्थिति को अनदेखा करता है, त्रुटियों का कारण बन सकता है: . यह प्रतिस्थापन स्थिर फलन सर्वसमिका में प्रतिस्थापन द्वारा को बदल देता है।
सामान्य रूप से, नवीनता की स्थिति को पूरा करने में विफलता को उपयुक्त नए चर के साथ अल्फा-नाम द्वारा संशोधित किया जा सकता है। उदाहरण के लिए, प्रतिस्थापन की हमारी सही धारणा पर वापस स्विच करने, में अमूर्त का नाम बदलकर एक नए चर के साथ किया जा सकता है , प्राप्त करने के लिए , और फलन का अर्थ प्रतिस्थापन द्वारा संरक्षित किया जा सकता है।
β-अवनति
β-अवनति नियम[lower-alpha 2] कहा गया है कि प्रपत्र का अनुप्रयोग अवधि तक कम कर देता है संकेत इंगित करने के लिए प्रयोग किया जाता है β-कम होकर हो जाता है उदाहरण के लिए, प्रत्येक के लिए , यह दर्शाता है कि वास्तव में सर्वसमिका है। इसी प्रकार, , जो यह दर्शाता है एक स्थिर फलन है।
लैम्ब्डा गणना को कार्यात्मक प्रोग्रामिंग भाषा के आदर्श संस्करण के रूप में देखा जा सकता है, जैसे हास्केल (प्रोग्रामिंग भाषा) या मानक एमएल इस दृष्टि के अंतर्गत, β-अवनति एक संगणनात्मक चरण से अनुरूप है। इस चरण को अतिरिक्त β-अवनति द्वारा दोहराया जा सकता है जब तक कि कम करने के लिए कोई और अनुप्रयोग नहीं बचा है। अनटाइप्ड लैम्ब्डा कलन में, जैसा कि यहाँ प्रस्तुत किया गया है, यह कमी प्रक्रिया समाप्त नहीं हो सकती है। इंस्टेंस के लिए, पद यहाँ पर विचार करें, यह शब्द एक β-अवनति में स्वयं को कम कर देता है, और इसलिए कमी की प्रक्रिया कभी समाप्त नहीं होगी।
अनटाइप्ड लैम्ब्डा गणना का एक अन्य स्वरूप यह है कि यह विभिन्न प्रकार के डेटा के बीच अंतर नहीं करता है। इंस्टेंस के लिए, एक ऐसा फलन लिखना वांछनीय हो सकता है जो केवल संख्याओं पर फलन करता हो। हालांकि, अनटाइप्ड लैम्ब्डा गणना में, किसी फलन को सत्य मानों, शृंखला या अन्य गैर-संख्या वस्तुओं पर प्रयुक्त होने से रोकने का कोई तरीका नहीं है।
औपचारिक परिभाषा
परिभाषा
लैम्ब्डा व्यंजक से बना है:
- चर v1, v2, ...;
- अमूर्त प्रतीक λ (लैम्ब्डा) और . (डॉट);
- कोष्ठक ()
लैम्ब्डा व्यंजक का समुच्चय, Λ, पुनरावर्ती परिभाषा हो सकती है:
- यदि x एक चर है, तो x ∈ Λ.
- यदि x एक चर है और M ∈ Λ, तब (λx.M) ∈ Λ.
- यदि M, N ∈ Λ, तब (M N) ∈ Λ.
नियम 2 के उदाहरणों को अमूर्तता के रूप में जाना जाता है और नियम 3 के उदाहरणों को अनुप्रयोग के रूप में जाना जाता है।[17][18]
संकेत पद्धति
लैम्ब्डा व्यंजक के अंकन को सुव्यवस्थित रखने के लिए, सामान्य रूप से निम्नलिखित समागम प्रयुक्त की जाती हैं:
- सबसे बाहरी कोष्ठक हटा दिए जाते हैं: (M N) के अतिरिक्त M N।
- अनुप्रयोगों को साहचर्य छोड़ दिया जाता है: ((M N) P) के अतिरिक्त MNP लिखा जा सकता है।[19]
- जब सभी चर एकल-अक्षर वाले हों, तो अनुप्रयोगों में स्थान छोड़ा जा सकता है: MNP के अतिरिक्त M N P है।[20]
- एक अमूर्त का निकाय नियमित व्यंजक का विस्तार करता है: λx.M N का अर्थ है λx.(M N) और नहीं (λx.M) N है।
- अमूर्तता का एक क्रम संकुचित होता है: λx.λy.λz.N को λxyz.N के रूप में संक्षिप्त किया गया है।[21][19]
मुक्त और बाध्य चर
अमूर्तता संक्रियक, λ, अमूर्तता के निकाय में जहां कहीं भी होता है, उसके चर को परिबद्ध करने के लिए कहा जाता है। अमूर्तता के विस्तार में आने वाले चर को सीमित कहा जाता है। एक व्यंजक λx.M में, भाग λx को प्रायः योजक कहा जाता है, एक संकेत के रूप में कि चर x, λx को M से जोड़कर बाध्य हो रहा है। अन्य सभी चर मुक्त कहलाते हैं। उदाहरण के लिए, व्यंजक λy.x x y में, y एक बाध्य चर है और x एक मुक्त चर है। साथ ही एक चर अपने निकटतम अमूर्तता से परिबद्ध होता है। निम्नलिखित उदाहरण में व्यंजक में x की एकल घटना दूसरे लैम्ब्डा से λx.y (λx.z x) परिबद्ध है।
एक लैम्ब्डा व्यंजक, M के मुक्त चर का समुच्चय, FV(M) के रूप में दर्शाया गया है और पदों की संरचना पर पुनरावर्तन द्वारा परिभाषित किया गया है:
- FV(x) = {x}, जहाँ x एक चर है।
- FV (λx.M) = FV(M) \ {x}।[lower-alpha 9]
- FV(M N) = FV(M) ∪ FV(N).[lower-alpha 10]
एक व्यंजक जिसमें कोई मुक्त चर नहीं होता है, उसे संवृत्त कहा जाता है। संवृत्त लैम्ब्डा व्यंजक को साहचर्य के रूप में भी जाना जाता है और संयोजन तर्क में पदों के समान है।
अवनति
लैम्ब्डा व्यंजक का अर्थ इस बात से परिभाषित होता है कि व्यंजक को कैसे कम किया जा सकता है।[22]
न्यूनीकरण तीन प्रकार की होती है:
- α- रूपांतरण: बाध्य चर परिवर्तित करना;
- β-न्यूनीकरण: फलन को उनके तर्कों पर प्रयुक्त करना;
- η-न्यूनीकरण: जो विस्तार की धारणा को दर्शाता है।
हम परिणामी तुल्यताओं के बारे में भी बात करते हैं: दो व्यंजक α-समतुल्य हैं, यदि उन्हें α-एक ही व्यंजक में परिवर्तित किया जा सकता है। β-तुल्यता और η-तुल्यता को इसी तरह परिभाषित किया गया है।
रेडेक्स पद, लघुकरणीय व्यंजक के लिए छोटा है, उपश्रेणी को संदर्भित करता है जिसे अवनति नियमों में से एक द्वारा कम किया जा सकता है। उदाहरण के लिए, (λx.M) N, M में x के लिए N के प्रतिस्थापन को व्यक्त करने में एक β-रेडेक्स है। एक रेडेक्स जिस व्यंजक को कम करता है उसे उसका अवनति कहा जाता है; (λx.M) N का न्यूनीकरण M[x := N] है।
यदि x, M में मुक्त नहीं है, λx.M x भी एक η-रेडेक्स है, जिसमें M की कमी है।
α-रूपांतरण
α-रूपांतरण, जिसे कभी-कभी α-नाम परिवर्तित करने के रूप में जाना जाता है,[23] बाध्य चर नामों को परिवर्तित करने की स्वीकृति देता है। उदाहरण के लिए, λx.x का α-रूपांतरण λy.y उत्पन्न कर सकता है। वे पद जो केवल α-रूपांतरण से भिन्न होते हैं, α-समतुल्य कहलाते हैं। प्रायः, लैम्ब्डा गणना के उपयोग में, α-समतुल्य पदों को समतुल्य माना जाता है।
α-रूपांतरण के परिशुद्ध नियम पूरी तरह से साधारण नहीं हैं। सबसे पहले, जब α-एक अमूर्तता को परिवर्तित करते हैं, केवल चर घटनाएँ जिनका नाम बदला जाता है, वे हैं जो एक ही अमूर्तता के लिए बाध्य हैं। उदाहरण के लिए, λx.λx.x के α-रूपांतरण का परिणाम λy.λx.x हो सकता है, लेकिन इसका परिणाम λy.λx.y नहीं हो सकता है। उत्तरार्द्ध का मूल से अलग अर्थ है। यह चर छायाकरण की प्रोग्रामिंग धारणा के अनुरूप है।
दूसरा, α-रूपांतरण संभव नहीं है यदि इसके परिणामस्वरूप एक भिन्न अमूर्तता द्वारा एक चर पर प्रग्रहण कर लिया जाएगा। उदाहरण के लिए, यदि हम λx.λy.x में x को y से प्रतिस्थापित करते हैं, तो हमें λy.λy.y मिलता है, जो बहुत समान नहीं है।
प्रोग्रामिंग भाषाओं में स्थिर सीमा के साथ, α-रूपांतरण का उपयोग नाम विभेदन (प्रोग्रामिंग भाषा) को सामान्य बनाने के लिए किया जा सकता है, यह सुनिश्चित करके कि कोई चर नाम किसी नाम को विस्तार (प्रोग्रामिंग) में नहीं रखता है ( विभेदन को सामान्य बनाने के लिए के लिए α-नामकरण देखें)।
डी ब्रुइज़न इंडेक्स संकेतन में, कोई भी दो α-समतुल्य पद रचना दृष्टि से समान हैं।
प्रतिस्थापन
प्रतिस्थापन, लिखित M[x:= N], व्यंजक N के साथ व्यंजक M में चर x की सभी मुक्त उपस्थिति को परिवर्तित करने की प्रक्रिया है। लैम्ब्डा गणना की शर्तों पर प्रतिस्थापन को पदों की संरचना पर पुनरावर्तन द्वारा परिभाषित किया गया है, निम्नानुसार (ध्यान दें: x और y केवल चर हैं जबकि M और N कोई लैम्ब्डा व्यंजक हैं):
- x[x := N] = N
- y[x := N] = y, if x ≠ y
- (M1 M2)[x := N] = M1[x := N] M2[x := N]
- (λx.M)[x := N] = λx.M
- (λy.M)[x := N] = λy.(M[x := N]), if x ≠ y and y ∉ FV(N) FV के लिए ऊपर देखें
एक अमूर्त में स्थानापन्न करने के लिए, कभी-कभी व्यंजक को α-रूपांतरित करना आवश्यक होता है। उदाहरण के लिए, यह (λx.y)[y := x] के लिए λx.x में परिणाम के लिए सही नहीं है, क्योंकि प्रतिस्थापित x मुक्त होना चाहिए था लेकिन बाध्य होने के कारण समाप्त हो गया। इस स्थिति में सही प्रतिस्थापन λz.x है, α-तुल्यता तक है। प्रतिस्थापन को विशिष्ट रूप से α-तुल्यता तक परिभाषित किया गया है।
β-न्यूनीकरण
β-अवनति फलन अनुप्रयोग के विचार को प्रग्रहण करती है। β-न्यूनीकरण को प्रतिस्थापन के संदर्भ में परिभाषित किया गया है: β-न्यूनीकरण (λx.M) N, M[x := N] है।[lower-alpha 2]
उदाहरण के लिए, 2, 7, × के कुछ एन्कोडिंग को मानते हुए, हमारे पास निम्न β-अवनति (λn.n × 2) 7 → 7 × 2 है।
β-न्यूनीकरण को करी-हावर्ड समरूपता के माध्यम से प्राकृतिक अवनति में स्थानीय न्यूनीकरण की अवधारणा के समान देखा जा सकता है।
η-न्यूनीकरण
η-न्यूनीकरण विस्तार के विचार को व्यक्त करता है,[24] जो इस संदर्भ में है कि दो फलन समान हैं यदि और केवल यदि वे सभी तर्कों के लिए समान परिणाम देते हैं। η-अवनति λx.f x और f के बीच परिवर्तित होती है जब भी x f में मुक्त दिखाई नहीं देता है।
η-न्यूनीकरण को करी-हावर्ड समरूपता के माध्यम से प्राकृतिक अवनति में स्थानीय पूर्णता की अवधारणा के समान देखा जा सकता है।
सामान्य रूप और मेल
अनटाइप्ड लैम्ब्डा गणना के लिए, पुनर्लेखन प्रणाली के रूप में β-अवनति न तो दृढ़ता से सामान्यीकरण कर रही है और न ही दुर्बल रूप से सामान्यीकरण कर रही है।
हालांकि, यह दिखाया जा सकता है कि α-रूपांतरण तक काम करते समय β-अवनति मेल (अमूर्त पुनर्लेखन) है (अर्थात हम दो सामान्य रूपों को बराबर मानते हैं यदि α-एक को दूसरे में परिवर्तित करना संभव है)।
इसलिए, दृढ़ता से सामान्यीकृत शर्तों और दुर्बल सामान्यीकरण शर्तों दोनों का एक अद्वितीय सामान्य रूप है। दृढ़ता से सामान्यीकृत शर्तों के लिए, किसी भी अवनति की योजना को सामान्य रूप देने की प्रत्याभूति दी जाती है, जबकि दुर्बल सामान्य शर्तों के लिए, कुछ अवनति की योजना इसे अन्वेषण करने में विफल हो सकती है।
एन्कोडिंग डेटा प्रारूप
मूल लैम्ब्डा गणना का उपयोग बूलियन्स, अंकगणित, डेटा संरचनाओं और पुनरावर्तन को मॉडल करने के लिए किया जा सकता है, जैसा कि निम्नलिखित उप-वर्गों में दिखाया गया है।
लैम्ब्डा गणना में अंकगणित
लैम्ब्डा गणना में प्राकृतिक संख्याओं को परिभाषित करने के कई संभावित तरीके हैं, लेकिन अब तक सबसे सामान्य चर्च अंक हैं, जिन्हें निम्नानुसार परिभाषित किया जा सकता है:
- 0 := λf.λx.x
- 1 := λf.λx.f x
- 2 := λf.λx.f (f x)
- 3 := λf.λx.f (f (f x))
और इसीलिए संकेतन में ऊपर प्रस्तुत वैकल्पिक सिंटैक्स का उपयोग करना:
- 0 := λfx.x
- 1 := λfx.f x
- 2 := λfx.f (f x)
- 3 := λfx.f (f (f x))
एक चर्च अंक एक उच्च-क्रम फलन है यह एक एकल-तर्क फलन f लेता है, और एक और एकल-तर्क फलन देता है। चर्च अंक n एक फलन(फ़ंक्शन) है जो एक फलन f को तर्क के रूप में लेता है और f की nवे रचना को प्रतिवर्ती करता है, अर्थात फलन f जो स्वयं n बार से बना होता है। यह f(n) को निरूपित किया गया है और वास्तव में f की n-वे पावर है (एक संक्रिया के रूप में माना जाता है); f(0) को पहचान फलन के रूप में परिभाषित किया गया है। इस तरह की दोहराई गई रचनाएँ (एकल फलन f की) घातांक के नियमों का अनुसरण करती हैं, यही वजह है कि इन अंकों का उपयोग अंकगणित के लिए किया जा सकता है। (चर्च के मूल लैम्ब्डा गणना में, एक लैम्ब्डा व्यंजक के औपचारिक पैरामीटर को फलन निकाय में कम से कम एक बार होने की आवश्यकता थी, जिसने 0 की उपरोक्त परिभाषा को असंभव बना दिया।)
चर्च अंक के बारे में सोचने का एक तरीका n, जो प्रोग्राम का विश्लेषण करते समय प्रायः उपयोगी होता है, एक निर्देश 'n बार दोहराएं' के रूप में होता है। उदाहरण के लिए, का उपयोग करना PAIR और NIL नीचे परिभाषित फ़ंक्शंस, एक ऐसे फलन को परिभाषित कर सकता है जो n तत्वों की एक (लिंक्ड) सूची बनाता है जो सभी x के बराबर है, एक रिक्त सूची से प्रारंभ करते हुए 'एक और x तत्व को आगे बढ़ाएं' n बार दोहराता है। लैम्ब्डा पद है
- λn.λx.n (PAIR x) NIL
जो दोहराया जा रहा है उसे अलग करके, और जिस तर्क को दोहराया जा रहा है उसे अलग-अलग करके, कई अलग-अलग प्रभावों को प्राप्त किया जा सकता है।
हम एक अनुक्रमिक फलन को परिभाषित कर सकते हैं, जो एक चर्च अंक n लेता है f का एक और अनुप्रयोग जोड़कर n + 1 और प्रतिवर्ती करता है, , जहां '(mf)x' का अर्थ है 'f' फलन 'x' पर 'm' बार प्रयुक्त होता है:
- SUCC := λn.λf.λx.f (n f x)
क्योंकि m-वीं रचना f के साथ n-वीं रचना f देता है m+n-वीं रचना f, जोड़ को निम्नानुसार परिभाषित किया जा सकता है:
- PLUS := λm.λn.λf.λx.m f (n f x)
PLUS दो प्राकृतिक संख्याओं को तर्क के रूप में लेने और एक प्राकृतिक संख्या वापस करने के फलन के रूप में विचार किया जा सकता है; यह सत्यापित किया जा सकता है
- PLUS 2 3
और
- 5
β-समतुल्य लैम्ब्डा व्यंजक हैं। जोड़ने के बाद से m एक संख्या के लिए n 1 जोड़कर पूरा किया जा सकता है m बार, एक वैकल्पिक परिभाषा है:
- PLUS := λm.λn.m SUCC n [25]
इसी प्रकार, गुणा को परिभाषित किया जा सकता है
- MULT := λm.λn.λf.m (n f)[21]वैकल्पिक
- MULT := λm.λn.m (PLUS n) 0
गुणा करने के बाद से m और n जोड़ने को पुनरावर्ती के समान है n फलन m बार और फिर इसे शून्य पर प्रयुक्त करना। घातांक का चर्च अंकों में सामान्य प्रतिपादन है, अर्थात्
- POW := λb.λe.e b[1] द्वारा परिभाषित पूर्ववर्ती फलन PRED n = n − 1 एक सकारात्मक पूर्णांक के लिए n और PRED 0 = 0 अपेक्षाकृत अधिक कठिन है। सूत्र
- PRED := λn.λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u)
आगमनात्मक रूप से दिखा कर मान्य किया जा सकता है कि यदि T दर्शाता है (λg.λh.h (g f)), तब T(n)(λu.x) = (λh.h(f(n−1)(x))) के लिए n > 0. की दो अन्य परिभाषाएँ PRED नीचे दिए गए हैं, एक तर्क और दूसरा जोड़ों का उपयोग कर रहा है। पूर्ववर्ती फलन के साथ, व्यवकलन प्रत्यक्ष है। परिभाषित
- SUB := λm.λn.n PRED m,
SUB m n प्राप्त m − n जब m > n और 0 अन्यथा।
तर्क और निर्धारक
संकेत के अनुसार, निम्नलिखित दो परिभाषाओं (चर्च बूलियन्स के रूप में जाना जाता है) का उपयोग बूलियन मूल्यों के लिए किया जाता है TRUE और FALSE:
- TRUE := λx.λy.x
- FALSE := λx.λy.y
फिर, इन दो लैम्ब्डा पदों के साथ, हम कुछ तार्किक संक्रिया को परिभाषित कर सकते हैं (ये केवल संभव सूत्रीकरण हैं; अन्य व्यंजक समान रूप से सही हैं):
- AND := λp.λq.p q p
- OR := λp.λq.p p q
- NOT := λp.p FALSE TRUE
- IFTHENELSE := λp.λa.λb.p a b
अब हम कुछ तार्किक फलनों की गणना करने में सक्षम हैं, उदाहरण के लिए:
- AND TRUE FALSE
- ≡ (λp.λq.p q p) TRUE FALSE →β TRUE FALSE TRUE
- ≡ (λx.λy.x) FALSE TRUE →β FALSE
और हम देखते हैं AND TRUE FALSE के बराबर है FALSE.
एक निर्धारक एक ऐसा फलन है जो एक बूलियन मान वापस करता है। सबसे मौलिक निर्धारक ISZERO है जो TRUE प्रतिवर्ती है यदि इसका तर्क चर्च अंक 0 है और FALSE यदि इसका तर्क कोई अन्य चर्च अंक है:
- ISZERO := λn.n (λx.FALSE) TRUE
निम्नलिखित निर्धारक परीक्षण करता है कि क्या पहला तर्क दूसरे से कम-से-या-बराबर है:
- LEQ := λm.λn.ISZERO (SUB m n),
और m = n, यदि LEQ m n और LEQ n m, संख्यात्मक समानता के लिए एक निर्धारक का निर्माण करना प्रत्यक्ष है।
निर्धारक की उपलब्धता और की उपरोक्त परिभाषा TRUE और FALSE लैम्ब्डा गणना में if-then-else पद लिखना सुविधाजनक बनाएं। उदाहरण के लिए, पूर्ववर्ती फलन को इस प्रकार परिभाषित किया जा सकता है:
- PRED := λn.n (λg.λk.ISZERO (g 1) k (PLUS (g k) 1)) (λv.0) 0
जिसे आगमनात्मक रूप से दिखा कर सत्यापित किया जा सकता है n (λg.λk.ISZERO (g 1) k (PLUS (g k) 1)) (λv.0) जोड़ n -1 के लिए फलन n > 0 है।
युग्म
एक युग्म (2-ट्यूपल) TRUE और FALSE, युग्म के लिए चर्च कोडिंग का उपयोग करके संदर्भ में परिभाषित किया जा सकता है। उदाहरण के लिए, PAIR एनकैप्सुलेट (x,y), FIRST जोड़ी का पहला तत्व देता है, और SECOND प्रतिफल देते है।
- PAIR := λx.λy.λf.f x y
- FIRST := λp.p TRUE
- SECOND := λp.p FALSE
- NIL := λx.TRUE
- NULL := λp.p (λx.λy.FALSE)
एक लिंक की गई सूची को रिक्त सूची के लिए या तो NIL शून्य के रूप में परिभाषित किया जा सकता है, या PAIR और एक छोटी सूची के रूप में परिभाषित किया जा सकता है। निर्धारक NULL मूल्य के लिए NIL परीक्षण करता है। (वैकल्पिक रूप से, NIL := FALSE के साथ निर्माण l (λh.λt.λz.deal_with_head_h_and_tail_t) (deal_with_nil) स्पष्ट NULL परीक्षण की आवश्यकता को कम करता है)।
युग्म के उपयोग के एक उदाहरण के रूप में, शिफ्ट-एंड-इन्क्रीमेंट फंक्शन जो चित्रित (m, n) को (n, n + 1) के रूप में परिभाषित किया जा सकता है
- Φ := λx.PAIR (SECOND x) (SUCC (SECOND x))
जो हमें पूर्ववर्ती फलन का संभव्यता सबसे पारदर्शी संस्करण देने की स्वीकृति देता है:
- PRED := λn.FIRST (n Φ (PAIR 0 0)).
अतिरिक्त प्रोग्रामिंग तकनीकें
लैम्ब्डा गणना के लिए प्रोग्रामिंग शैली का समूह है। इनमें से कई मूल रूप से सिमेंटिक्स (कंप्यूटर विज्ञान) के लिए एक नींव के रूप में लैम्ब्डा गणना का उपयोग करने के संदर्भ में विकसित किए गए थे, प्रभावी रूप से लैम्ब्डा गणना का उपयोग निम्न-स्तरीय प्रोग्रामिंग भाषा के रूप में किया गया था। क्योंकि कई प्रोग्रामिंग भाषाओं में लैम्ब्डा गणना (या कुछ समान) को एक खंड के रूप में सम्मिलित किया गया है, इन तकनीकों का उपयोग व्यावहारिक प्रोग्रामिंग भाषा को भी देखा जाता है, लेकिन तब इसे अस्पष्ट या अयोग्य माना जा सकता है।
नामित स्थिरांक
लैम्ब्डा गणना में, एक पुस्तकालय (कंप्यूटिंग) पहले से परिभाषित फलनों के संग्रह का रूप लेगा, जो लैम्ब्डा-शब्द के रूप में केवल विशेष स्थिरांक हैं। शुद्ध लैम्ब्डा गणना में नामित स्थिरांक की अवधारणा नहीं है क्योंकि सभी परमाणु लैम्ब्डा-शर्तें चर हैं, लेकिन मुख्य निकाय में उस चर को बांधने के लिए अमूर्तता का उपयोग करके स्थिरांक के नाम के रूप में एक चर को अलग करके नामित स्थिरांक का अनुकरण कर सकते हैं। , और उस अमूर्तता को इच्छित परिभाषा पर प्रयुक्त करें। ऐसे में इस्तेमाल करना f एम में मतलब एन (कुछ स्पष्ट लैम्ब्डा-पद) (एक और लैम्ब्डा-पद, मुख्य कार्यक्रम), कोई कह सकता है
- (λf.M) एन
लेखक प्रायः सिंटैक्टिक शुगर का परिचय देते हैं, जैसे let,[lower-alpha 11] उपरोक्त को अधिक सहज क्रम में लिखने की स्वीकृति देने के लिए
- let f =N in एम
इस तरह की परिभाषाओं का पीछा करते हुए, लैम्ब्डा गणना प्रोग्राम को शून्य या अधिक फलन परिभाषाओं के रूप में लिख सकते हैं, इसके बाद एक लैम्ब्डा-पद उन फलनों का उपयोग कर सकते हैं जो प्रोग्राम के मुख्य निकाय का गठन करते हैं।
इसका एक उल्लेखनीय प्रतिबंध let क्या वह नाम है f एन में परिभाषित नहीं किया जाना चाहिए, एन के लिए अबास्ट्रक्शन बाइंडिंग के विस्तार से बाहर होना चाहिए f; इसका मतलब है कि एक पुनरावर्ती फलन परिभाषा का उपयोग एन के रूप में नहीं किया जा सकता है let. letrecसी}}[lower-alpha 12] निर्माण पुनरावर्ती फलन परिभाषाएँ लिखने की स्वीकृति देगा।
पुनरावर्तन और निश्चित बिंदु
प्रत्यावर्तन फलन का उपयोग करके फलन की परिभाषा है। लैम्ब्डा गणना इसे सीधे तौर पर कुछ अन्य अंकन के रूप में व्यक्त नहीं कर सकता है: लैम्ब्डा गणना में सभी फलन अस्पष्ट हैं, इसलिए हम लैम्ब्डा शब्द के अंदर उसी मान को परिभाषित करने वाले मान का उल्लेख नहीं कर सकते हैं। हालांकि, लैम्ब्डा व्यंजक को अपने तर्क मान के रूप में प्राप्त करने की व्यवस्था करके अभी भी रिकर्सन प्राप्त किया जा सकता है, उदाहरण के लिए (λx.x x) E.
कारख़ाने का फलन पर विचार करें F(n) पुनरावर्ती द्वारा परिभाषित
- F(n) = 1, if n = 0; else n × F(n − 1).
लैम्ब्डा व्यंजक में जो इस फलन का प्रतिनिधित्व करना है, एक पैरामीटर (सामान्य रूप से पहला वाला) लैम्ब्डा व्यंजक को इसके मूल्य के रूप में प्राप्त करने के लिए माना जाएगा, ताकि इसे कॉल करना - इसे तर्क पर प्रयुक्त करना - रिकर्सन की राशि होगी। इस प्रकार पुनरावर्तन प्राप्त करने के लिए, अभिप्रेत-जैसा-स्व-संदर्भित तर्क (कहा जाता है r यहां) हमेशा फलन बॉडी के अंदर कॉल पॉइंट पर पास होना चाहिए:
- G := λr. λn.(1, if n = 0; else n × (r r (n−1)))
- साथ r r x = F x = G r x धारण करना, इसलिए r = G और
- F := G G = (λx.x x) G
स्व-अनुप्रयोग यहां प्रतिकृति प्राप्त करता है, फलन की लैम्ब्डा व्यंजक को तर्क मान के रूप में अगले आमंत्रण पर पास करता है, इसे संदर्भित करने के लिए उपलब्ध कराता है और वहां बुलाया जाता है।
यह इसे हल करता है लेकिन प्रत्येक पुनरावर्ती कॉल को स्व-अनुप्रयोग के रूप में पुनः लिखने की आवश्यकता होती है। हम किसी भी पुनः लिखने की आवश्यकता के बिना एक सामान्य समाधान चाहते हैं:
- G := λr. λn.(1, if n = 0; else n × (r (n−1)))
- साथ r x = F x = G r x धारण करना, इसलिए r = G r =: FIX G और
- F := FIX G कहाँ FIX g := (r where r = g r) = g (FIX g)
- ताकि FIX G = G (FIX G) = (λn.(1, if n = 0; else n × ((FIX G) (n−1))))
रिकर्सिव कॉल का प्रतिनिधित्व करने वाले पहले तर्क के साथ लैम्ब्डा शब्द दिया गया (उदा। G यहाँ), फिक्स्ड-पॉइंट साहचर्य FIX रिकर्सिव फलन का प्रतिनिधित्व करने वाली एक स्व-प्रतिकृति लैम्ब्डा व्यंजक लौटाएगा (यहां, F). फलन को किसी भी बिंदु पर स्पष्ट रूप से स्वयं को पारित करने की आवश्यकता नहीं है, क्योंकि स्व-प्रतिकृति अग्रिम में व्यवस्थित की जाती है, जब इसे बनाया जाता है, इसे हर बार कॉल करने के लिए किया जाता है। इस प्रकार मूल लैम्ब्डा व्यंजक (FIX G) आत्म-संदर्भ प्राप्त करते हुए, कॉल-पॉइंट पर अपने अंदर ही पुनः बनाया जाता है।
वास्तव में, इसके लिए कई संभावित परिभाषाएँ हैं FIX संक्रियक, उनमें से सबसे सामान्य हैं:
- Y := λg.(λx.g (x x)) (λx.g (x x))
लैम्ब्डा गणना में, Y gका निश्चित बिन्दु है g, जैसा कि इसका विस्तार होता है:
- Y g
- (λh.(λx.h (x x)) (λx.h (x x))) g
- (λx.g (x x)) (λx.g (x x))
- g ((λx.g (x x)) (λx.g (x x)))
- g (Y g)
अब, हमारे पुनरावर्ती कॉल को फैक्टोरियल फलन करने के लिए, हम बस कॉल करेंगे (Y G) n, जहां n वह संख्या है जिसके भाज्य की हम गणना कर रहे हैं। दिया गया n = 4, उदाहरण के लिए, यह देता है:
- (Y G) 4
- G (Y G) 4
- (λr.λn.(1, if n = 0; else n × (r (n−1)))) (Y G) 4
- (λn.(1, if n = 0; else n × ((Y G) (n−1)))) 4
- 1, if 4 = 0; else 4 × ((Y G) (4−1))
- 4 × (G (Y G) (4−1))
- 4 × ((λn.(1, if n = 0; else n × ((Y G) (n−1)))) (4−1))
- 4 × (1, if 3 = 0; else 3 × ((Y G) (3−1)))
- 4 × (3 × (G (Y G) (3−1)))
- 4 × (3 × ((λn.(1, if n = 0; else n × ((Y G) (n−1)))) (3−1)))
- 4 × (3 × (1, if 2 = 0; else 2 × ((Y G) (2−1))))
- 4 × (3 × (2 × (G (Y G) (2−1))))
- 4 × (3 × (2 × ((λn.(1, if n = 0; else n × ((Y G) (n−1)))) (2−1))))
- 4 × (3 × (2 × (1, if 1 = 0; else 1 × ((Y G) (1−1)))))
- 4 × (3 × (2 × (1 × (G (Y G) (1−1)))))
- 4 × (3 × (2 × (1 × ((λn.(1, if n = 0; else n × ((Y G) (n−1)))) (1−1)))))
- 4 × (3 × (2 × (1 × (1, if 0 = 0; else 0 × ((Y G) (0−1))))))
- 4 × (3 × (2 × (1 × (1))))
- 24
प्रत्येक पुनरावर्ती परिभाषित फलन को एक अतिरिक्त तर्क के साथ पुनरावर्ती कॉल पर बंद होने वाले कुछ उपयुक्त परिभाषित फलन के निश्चित बिंदु के रूप में देखा जा सकता है, और इसलिए, Yप्रत्येक पुनरावर्ती परिभाषित फलन को लैम्ब्डा व्यंजक के रूप में व्यक्त किया जा सकता है। विशेष रूप से, अब हम पुनरावर्ती रूप से प्राकृतिक संख्याओं के व्यवकलन, गुणन और तुलना निर्धारक को स्पष्ट रूप से परिभाषित कर सकते हैं।
मानक शब्द
कुछ शब्दों के सामान्यतः स्वीकृत नाम हैं:[27][28][29]
- I := λx.x
- S := λx.λy.λz.x z (y z)
- K := λx.λy.x
- B := λx.λy.λz.x (y z)
- C := λx.λy.λz.x z y
- W := λx.λy.x y y
- ω or Δ or U := λx.x x
- Ω := ω ω
I सर्वसमिका फलन है। SK और BCKW फॉर्म कंप्लीट साहचर्य गणना सिस्टम जो किसी भी लैम्ब्डा पद को व्यक्त कर सकता है - देखें
- अमूर्त उन्मूलन। Ω है UU, या YI, सबसे छोटा शब्द जिसका कोई सामान्य रूप नहीं है। Y मानक है और परिभाषित #Y है, और इसे इस रूप में भी परिभाषित किया जा सकता है Y=BU(CBU), ताकि Yf=f(Yf). TRUE और FALSE परिभाषित #तर्क और निर्धारक को सामान्य रूप से संक्षिप्त किया जाता है T और F.
अमूर्त उन्मूलन
यदि N अमूर्तता के बिना एक लैम्ब्डा-पद है, लेकिन संभवतः नामित स्थिरांक (संयोजी तर्क) युक्त है, तो एक लैम्ब्डा-पद टी मौजूद है (x,एन) जो के बराबर है λx.N लेकिन अमूर्तता का अभाव है (नामित स्थिरांक के भाग को छोड़कर, यदि इन्हें गैर-परमाणु माना जाता है)। इसे अज्ञात चर के रूप में भी देखा जा सकता है, क्योंकि T(x,एन) की सभी उपस्थिति को हटा देता है x N से, जबकि अभी भी तर्क मानों को उन स्थितियों में प्रतिस्थापित करने की स्वीकृति है जहाँ N में a सम्मिलित है x. रूपांतरण फलन टी द्वारा परिभाषित किया जा सकता है:
- टी(x, x) := मैं
- टी(x, एन) := 'के' एन यदि x एन में मुक्त नहीं है।
- टी(x, एम एन) := 'एस' टी (x, एम) टी (x, एन)
किसी भी स्थिति में, प्रपत्र T(x,N) P प्रारंभिक साहचर्य 'I', 'K', या 'S' द्वारा तर्क P को हड़पने से कम कर सकता है, ठीक उसी तरह जैसे β-अवनति (λx.N) प करेंगे। 'मैं' वह तर्क देता है। 'क' तर्क को दूर फेंक देता है, जैसे (λx.N) यदि करेंगे x एन में कोई मुक्त घटना नहीं है। 'एस' तर्क को अनुप्रयोग के दोनों उप-पदों पर पास करता है, और फिर पहले के परिणाम को दूसरे के परिणाम पर प्रयुक्त करता है।
संयोजक 'बी' और 'सी' 'एस' के समान हैं, लेकिन एक अनुप्रयोग के केवल एक सबटर्म पर तर्क पारित करते हैं ('बी' तर्क सबटर्म के लिए और 'सी' फलन सबटर्म के लिए), इस प्रकार बाद की बचत 'क' की घटना न हो तो x एक उपपद में। बी और सी की तुलना में, एस साहचर्य वास्तव में दो कार्यात्मकताओं को जोड़ता है: तर्कों को पुनर्व्यवस्थित करना, और एक तर्क को दोहराना ताकि इसे दो स्थानों पर इस्तेमाल किया जा सके। W साहचर्य केवल बाद वाला करता है, एसकेआई साहचर्य गणना के विकल्प के रूप में B, C, K, W सिस्टम की उपज देता है।
टाइप किया हुआ लैम्ब्डा गणना
एक टाइप किया हुआ लैम्ब्डा गणना एक टाइप किया हुआ औपचारिकतावाद (गणित) है जो लैम्ब्डा-प्रतीक का उपयोग करता है () अनाम फलन अमूर्तता को निरूपित करने के लिए। इस संदर्भ में, प्रकार सामान्य रूप से एक वाक्यगत प्रकृति की वस्तुएँ होती हैं जिन्हें लैम्ब्डा शब्दों को सौंपा जाता है; एक प्रकार की परिशुद्ध प्रकृति माने गए गणना पर निर्भर करती है (देखें टाइप किया हुआ लैम्ब्डा गणना#किंड्स ऑफ़ टाइप्ड लैम्ब्डा कैलकुली)। एक निश्चित दृष्टिकोण से, टाइप किए गए लैम्ब्डा कैलकुली को अनटाइप्ड लैम्ब्डा गणना के शोधन के रूप में देखा जा सकता है, लेकिन दूसरे दृष्टिकोण से, उन्हें अधिक मौलिक सिद्धांत और अनटाइप्ड लैम्ब्डा गणना को केवल एक प्रकार के साथ एक विशेष मामला माना जा सकता है।[30] टाइप की गई लैम्ब्डा कैलकुली मूलभूत प्रोग्रामिंग भाषाएं हैं और टाइप की गई कार्यात्मक प्रोग्रामिंग भाषाओं जैसे एमएल प्रोग्रामिंग भाषा और हास्केल (प्रोग्रामिंग भाषा) और अधिक अप्रत्यक्ष रूप से टाइप की गई अनिवार्य प्रोग्रामिंग भाषाओं का आधार हैं। टाइप किए गए लैम्ब्डा कैलकुली प्रोग्रामिंग भाषाओं के लिए टाइप सिस्टम के डिजाइन में एक महत्वपूर्ण भूमिका निभाते हैं; यहाँ टाइपेबिलिटी सामान्य रूप से प्रोग्राम के वांछनीय गुणों को प्रग्रहण करती है, उदा। प्रोग्राम मेमोरी एक्सेस उल्लंघन का कारण नहीं बनेगा।
टाइप किए गए लैम्ब्डा कैलकुली विच्छेदन-हावर्ड आइसोमोर्फिज्म के माध्यम से गणितीय तर्क और प्रमाण सिद्धांत से निकटता से संबंधित हैं और उन्हें श्रेणी सिद्धांत की कक्षाओं की आंतरिक भाषा के रूप में माना जा सकता है, उदा। सामान्य रूप से टाइप की गई लैम्ब्डा गणना कार्तीय बंद श्रेणी (सीसीसी) की भाषा है।
अवनति रणनीतियाँ
कोई शब्द सामान्यीकरण कर रहा है या नहीं, और इसे सामान्य करने में कितना काम करने की आवश्यकता है, यह काफी हद तक उपयोग की जाने वाली कमी की रणनीति पर निर्भर करता है। सामान्य लैम्ब्डा गणना कमी रणनीतियों में सम्मिलित हैं:[31][32][33]
- सामान्य क्रम
- सबसे बाएँ, सबसे बाहरी रिडेक्स को हमेशा पहले घटाया जाता है। यही है, जब भी संभव हो तर्कों को कम करने से पहले तर्कों को अमूर्त के निकाय में प्रतिस्थापित किया जाता है।
- प्रयुक्त करने का क्रम
- सबसे बाएं, अंतरतम रिडेक्स को हमेशा पहले घटाया जाता है। सहज रूप से इसका मतलब है कि फलन के तर्क हमेशा फलन से पहले ही कम हो जाते हैं। व्यावहारिक आदेश हमेशा फलनों को सामान्य रूपों में प्रयुक्त करने का प्रयास करता है, भले ही यह संभव न हो।
- पूर्ण β-अवनति
- किसी भी रेडेक्स को किसी भी समय घटाया जा सकता है। इसका मतलब अनिवार्य रूप से किसी विशेष कमी की रणनीति की कमी है - रिड्यूसबिलिटी के संबंध में, सभी दांव बंद हैं।
लैम्ब्डा अमूर्तता के अंतर्गत दुर्बल कमी की रणनीति कम नहीं होती है:
- मूल्य से कॉल करें
- एक रीडेक्स केवल तभी घटाया जाता है जब उसका दाहिना हाथ एक मान (चर या अमूर्त) तक कम हो जाता है। केवल सबसे बाहरी रेडेक्स कम किए जाते हैं।
- नाम से बुलाओ
- सामान्य क्रम के रूप में, लेकिन अमूर्तता के अंदर कोई अवनति नहीं की जाती है। उदाहरण के लिए, λx.(λy.y)x इस रणनीति के अनुसार सामान्य रूप में है, हालांकि इसमें रेडेक्स सम्मिलित है (λy.y)x.
साझाकरण के साथ रणनीतियाँ उन संगणनाओं को कम करती हैं जो समानांतर में समान हैं:
- इष्टतम कमी
- सामान्य क्रम के रूप में, लेकिन समान लेबल वाली संगणनाएँ एक साथ कम हो जाती हैं।
- आवश्यकता के अनुसार कॉल करें
- नाम से कॉल के रूप में (इसलिए दुर्बल), लेकिन फलन अनुप्रयोग जो शब्दों को डुप्लिकेट करेंगे, इसके अतिरिक्त तर्क को नाम दें, जिसे केवल तभी कम किया जाता है जब इसकी आवश्यकता होती है।
कम्प्यूटेबिलिटी
कोई एल्गोरिथ्म नहीं है जो किसी भी दो लैम्ब्डा व्यंजक और आउटपुट को इनपुट के रूप में लेता है TRUE या FALSE इस पर निर्भर करता है कि एक व्यंजक दूसरे को कम करती है या नहीं।[11]अधिक परिशुद्ध रूप से, कोई भी संगणनीय फलन समस्या का निर्णय नहीं कर सकता है। यह ऐतिहासिक दृष्टि से पहली समस्या थी जिसके लिए अनिश्चयता सिद्ध की जा सकती थी। इस तरह के प्रमाण के लिए हमेशा की तरह, संगणनीय का मतलब गणना के किसी भी मॉडल द्वारा गणना योग्य है जो ट्यूरिंग पूर्ण है। वास्तव में कम्प्यूटेबिलिटी को लैम्ब्डा गणना के माध्यम से परिभाषित किया जा सकता है: प्राकृतिक संख्याओं का एक फलन F: 'N' → 'N' एक संगणनात्मक फलन है यदि और केवल यदि लैम्ब्डा व्यंजक f मौजूद है जैसे कि x, y की प्रत्येक जोड़ी के लिए 'एन', एफ (एक्स) = वाई यदि और केवल यदि एफ x =β y, कहाँ x और y क्रमशः एक्स और वाई के अनुरूप चर्च अंक हैं और =β मतलब β-अवनति के साथ तुल्यता। संगणनीयता और उनकी समानता को परिभाषित करने के अन्य दृष्टिकोणों के लिए चर्च-ट्यूरिंग थीसिस देखें।
चर्च का अगणनीयता का प्रमाण पहले यह निर्धारित करने में समस्या को कम करता है कि दी गई लैम्ब्डा व्यंजक में बीटा सामान्य रूप है या नहीं। तब वह मानता है कि यह निर्धारक संगणनीय है, और इसलिए इसे लैम्ब्डा गणना में व्यक्त किया जा सकता है। क्लेन द्वारा पहले के काम पर निर्माण और लैम्ब्डा व्यंजक के लिए गोडेल नंबरिंग का निर्माण, वह एक लैम्ब्डा व्यंजक बनाता है e जो गोडेल के अपूर्णता प्रमेय के प्रमाण का अनुसरण करता है | गोडेल का पहला अपूर्णता प्रमेय। यदि e अपने स्वयं के गोडेल नंबर पर प्रयुक्त होता है, एक विरोधाभासी परिणाम।
जटिलता
लैम्ब्डा गणना के लिए संगणनात्मक जटिलता सिद्धांत की धारणा थोड़ी मुश्किल है, क्योंकि β-अवनति की लागत इसे प्रयुक्त करने के तरीके के आधार पर भिन्न हो सकती है।[34] परिशुद्ध होने के लिए, किसी को बाध्य चर की सभी उपस्थिति का स्थान ढूंढना चाहिए V व्यंजक में E, एक समय की लागत का अर्थ है, या किसी को किसी तरह से मुक्त चर के स्थानों का ट्रैक रखना चाहिए, एक स्थान लागत का अर्थ है। के स्थानों के लिए एक भोली खोज V में E बिग ओ अंकन है | ओ (एन) की लंबाई एन में E. निर्देशक कड़ी्स एक प्रारंभिक दृष्टिकोण था जिसने द्विघात अंतरिक्ष उपयोग के लिए इस समय की लागत का कारोबार किया।[35] सामान्य रूप से इससे उन प्रणालियों का अध्ययन हुआ है जो स्पष्ट प्रतिस्थापन का उपयोग करते हैं।
2014 में यह दिखाया गया था कि एक शब्द को कम करने के लिए सामान्य क्रम में कमी के द्वारा उठाए गए β-अवनति कदमों की संख्या एक उचित समय लागत मॉडल है, अर्थात, कमी को ट्यूरिंग मशीन पर बहुपद रूप से चरणों की संख्या के अनुपात में सिम्युलेटेड किया जा सकता है। .[36] यह लंबे समय से खुली समस्या थी, आकार विस्फोट के कारण, लैम्ब्डा शब्दों का अस्तित्व जो प्रत्येक β-अवनति के लिए आकार में तेजी से बढ़ता है। कॉम्पैक्ट साझा प्रतिनिधित्व के साथ काम करके परिणाम इसके आसपास हो जाता है। परिणाम स्पष्ट करता है कि लैम्ब्डा शब्द का मूल्यांकन करने के लिए आवश्यक स्थान की मात्रा कमी के दौरान शब्द के आकार के समानुपाती नहीं है। यह वर्तमान में ज्ञात नहीं है कि अंतरिक्ष जटिलता का एक अच्छा उपाय क्या होगा।[37] एक अनुचित मॉडल का अर्थ अनिवार्य रूप से अक्षम नहीं है। अवनति की रणनीति # इष्टतम कमी एक ही लेबल के साथ सभी संगणनाओं को एक चरण में कम कर देती है, डुप्लिकेट फलन से बचती है, लेकिन किसी दिए गए शब्द को सामान्य रूप में कम करने के लिए समानांतर β-अवनति चरणों की संख्या शब्द के आकार में लगभग रैखिक होती है। यह उचित लागत माप के लिए बहुत छोटा है, क्योंकि किसी भी ट्यूरिंग मशीन को लैम्ब्डा गणना में ट्यूरिंग मशीन के आकार के रैखिक रूप से आनुपातिक आकार में एन्कोड किया जा सकता है। लैम्ब्डा शर्तों को कम करने की सही लागत β-अवनति प्रति से के कारण नहीं है, बल्कि β-अवनति के दौरान रिडेक्स के दोहराव से निपटने के कारण है।[38] यह ज्ञात नहीं है कि उचित लागत मॉडल के संबंध में मापे जाने पर इष्टतम अवनति कार्यान्वयन उचित है या नहीं, जैसे कि सामान्य रूप से बाएं-सबसे बाहरी चरणों की संख्या, लेकिन यह लैम्ब्डा गणना के टुकड़ों के लिए दिखाया गया है कि इष्टतम कमी एल्गोरिदम कुशल है और सबसे बाएं-सबसे बाहरी की तुलना में अधिक से अधिक द्विघात ओवरहेड है।[37]इसके अलावा इष्टतम अवनति के बीओएचएम प्रोटोटाइप कार्यान्वयन ने शुद्ध लैम्ब्डा शर्तों पर कैमल और हास्केल (प्रोग्रामिंग भाषा) दोनों से बेहतर प्रदर्शन किया।[38]
लैम्ब्डा गणना और प्रोग्रामिंग भाषाएं
जैसा कि पीटर लैंडिन के 1965 के पेपर ए कॉरेस्पोंडेंस बिटवीन एल्गोल 60 और चर्च के लैम्ब्डा-अंकन द्वारा इंगित किया गया है,[39] अनुक्रमिक प्रक्रियात्मक प्रोग्रामिंग भाषाओं को लैम्ब्डा गणना के संदर्भ में समझा जा सकता है, जो प्रक्रियात्मक अमूर्तता और प्रक्रिया (सबप्रोग्राम) अनुप्रयोग के लिए बुनियादी तंत्र प्रदान करता है।
अनाम फलन
उदाहरण के लिए, पायथन (प्रोग्रामिंग भाषा) में स्क्वायर फलन को लैम्ब्डा व्यंजक के रूप में निम्नानुसार व्यक्त किया जा सकता है:
<वाक्यविन्यास लैंग = पायथन> (लैम्ब्डा एक्स: एक्स ** 2) </वाक्यविन्यास हाइलाइट>
उपरोक्त उदाहरण एक व्यंजक है जो प्रथम श्रेणी के फलन का मूल्यांकन करता है। प्रतीक lambda पैरामीटर नामों की एक सूची दी गई है, एक अज्ञात फलन बनाता है, x - इस स्थिति में केवल एक तर्क, और एक व्यंजक जिसका मूल्यांकन फलन के मुख्य भाग के रूप में किया जाता है, x**2. अज्ञात फलनों को कभी-कभी लैम्ब्डा व्यंजक कहा जाता है।
उदाहरण के लिए, पास्कल (प्रोग्रामिंग भाषा) और कई अन्य अनिवार्य भाषाओं ने फलन पॉइंटर्स के तंत्र के माध्यम से अन्य उपप्रोग्राम के तर्कों के रूप में पासिंग सबप्रोग्राम्स का लंबे समय तक समर्थन किया है। हालाँकि, फलन पॉइंटर्स फ़ंक्शंस के लिए प्रथम श्रेणी के फलन डेटाटाइप होने के लिए पर्याप्त स्थिति नहीं हैं, क्योंकि फलन एक प्रथम श्रेणी डेटाटाइप है यदि और केवल यदि फलन के नए उदाहरण रन-टाइम पर बनाए जा सकते हैं। और फलनों के इस रन-टाइम निर्माण को स्मॉलटाक, जावास्क्रिप्ट और वोल्फ्राम भाषा में समर्थित किया गया है, और हाल ही में स्काला (प्रोग्रामिंग भाषा), एफिल (प्रोग्रामिंग भाषा) (एजेंट), सी शार्प (प्रोग्रामिंग भाषा)|सी# (प्रतिनिधियों) और सी में समर्थित है। सी ++ 11, दूसरों के बीच में।
समानांतरवाद और संगामिति
चर्च-रॉसर प्रमेय | लैम्ब्डा गणना की चर्च-रॉसर संपत्ति का मतलब है कि मूल्यांकन (बीटा-कमी) समानांतर में भी, किसी भी क्रम में किया जा सकता है। इसका मतलब यह है कि विभिन्न मूल्यांकन रणनीति#अनिर्धारक रणनीतियाँ प्रासंगिक हैं। हालाँकि, लैम्ब्डा गणना समानांतर कंप्यूटिंग के लिए कोई स्पष्ट निर्माण प्रदान नहीं करता है। लैम्ब्डा गणना में वायदा और वादे जैसे कंस्ट्रक्शंस को जोड़ा जा सकता है। संचार और संगामिति का वर्णन करने के लिए अन्य प्रक्रिया गणनाएं विकसित की गई हैं।
अर्थ
तथ्य यह है कि लैम्ब्डा गणना शब्द अन्य लैम्ब्डा गणना शर्तों पर फलनों के रूप में फलन करते हैं, और यहां तक कि स्वयं पर भी, लैम्ब्डा गणना के अर्थशास्त्र के बारे में प्रश्नों का नेतृत्व करते हैं। क्या लैम्ब्डा गणना शर्तों को समझदार अर्थ दिया जा सकता है? प्राकृतिक अर्थ को स्वयं के फलनों के फलन स्थान D → D के लिए एक समुच्चय D आइसोमॉर्फिक खोजना था। हालांकि, प्रमुखता बाधाओं के कारण कोई भी गैर- साधारण डी मौजूद नहीं हो सकता है क्योंकि डी से डी के सभी फलनों के समुच्चय में डी की तुलना में अधिक कार्डिनैलिटी है, जब तक कि डी सिंगलटन समुच्चय न हो।
1970 के दशक में, दाना स्कॉट ने दिखाया कि यदि केवल स्कॉट निरंतरता पर विचार किया जाता है, तो आवश्यक संपत्ति के साथ एक समुच्चय या डोमेन सिद्धांत डी पाया जा सकता है, इस प्रकार लैम्ब्डा गणना के लिए एक मॉडल सिद्धांत प्रदान करता है।[40] इस फलन ने प्रोग्रामिंग भाषाओं के सांकेतिक अर्थ के लिए भी आधार बनाया।
रूपांतर और विस्तार
ये एक्सटेंशन लैम्ब्डा घन में हैं:
- टाइप किया हुआ लैम्ब्डा गणना - टाइप किए गए चर (और फ़ंक्शंस) के साथ लैम्ब्डा गणना
- सिस्टम एफ - प्रकार-चर के साथ एक टाइप किया हुआ लैम्ब्डा गणना
- निर्माण की कलन - प्रथम श्रेणी के मान के रूप में टाइप सिस्टम के साथ एक टाइप किया हुआ लैम्ब्डा गणना
ये औपचारिक प्रणालियाँ लैम्ब्डा गणना के विस्तार हैं जो लैम्ब्डा क्यूब में नहीं हैं:
- बाइनरी लैम्ब्डा गणना - बाइनरी I/O के साथ लैम्ब्डा गणना का एक संस्करण, शब्दों का एक बाइनरी एन्कोडिंग और एक निर्दिष्ट यूनिवर्सल मशीन।
- लैम्ब्डा-इन गणना - शास्त्रीय तर्क के इलाज के लिए लैम्ब्डा गणना का विस्तार
ये औपचारिक प्रणालियाँ लैम्ब्डा गणना की विविधताएँ हैं:
- कप्पा गणना - लैम्ब्डा गणना का प्रथम क्रम का एनालॉग
ये औपचारिक प्रणालियाँ लैम्ब्डा गणना से संबंधित हैं:
- संयोजन तर्क - चर के बिना गणितीय तर्क के लिए एक अंकन
- SKI साहचर्य गणना - #S, #K और #I साहचर्य पर आधारित एक संगणनात्मक सिस्टम, लैम्ब्डा गणना के बराबर, लेकिन चर सब्स्टीट्यूशन के बिना लघुकरणीय
यह भी देखें
- एप्लिकेटिव कंप्यूटिंग सिस्टम - लैम्ब्डा कैलकुलस की शैली में वस्तु (कंप्यूटर विज्ञान) का उपचार
- कार्तीय बंद श्रेणी - श्रेणी सिद्धांत में लैम्ब्डा कलन के लिए एक सेटिंग
- श्रेणीबद्ध अमूर्त मशीन - लैम्ब्डा कैलकुस पर लागू गणना का एक मॉडल
- करी-हावर्ड समरूपता - कार्यक्रमों और गणितीय प्रमाण के बीच औपचारिक पत्राचार
- डी ब्रुजन इंडेक्स - अल्फा रूपांतरणों को असंबद्ध करने वाला अंकन
- डी ब्रुइन नोटेशन - पोस्टफिक्स संशोधन कार्यों का उपयोग करके नोटेशन
- डिडक्टिव लैम्ब्डा कैलकुलस - लैम्ब्डा कैलकुलस को डिडक्टिव सिस्टम मानने से जुड़ी समस्याओं पर विचार।
- डोमेन थ्योरी - लैम्ब्डा कैलकुलस के लिए डेनोटेशनल सिमेंटिक्स देने वाले कुछ आंशिक रूप से ऑर्डर किए गए सेट का अध्ययन
- मूल्यांकन रणनीति - प्रोग्रामिंग भाषाओं में अभिव्यक्तियों के मूल्यांकन के नियम
- स्पष्ट प्रतिस्थापन - प्रतिस्थापन का सिद्धांत, जैसा कि #β-कमी|β-कमी में उपयोग किया जाता है
- कार्यात्मक प्रोग्रामिंग
- हैरोप सूत्र - एक प्रकार का रचनात्मक तार्किक सूत्र जैसे कि सबूत लैम्ब्डा शब्द हैं
- इंटरेक्शन नेट
- क्लेन-रोसेर विरोधाभास - एक प्रदर्शन कि लैम्ब्डा कैलकुस का कुछ रूप असंगत है
- लैम्ब्डा कैलकुलस के शूरवीर - एलआईएसपी और स्कीम (प्रोग्रामिंग भाषा) हैकर (प्रोग्रामर उपसंस्कृति) का एक अर्ध-काल्पनिक संगठन
- मशीन घटता है - लैम्ब्डा कैलकुलस में कॉल-बाय-नाम की व्याख्या करने के लिए एक अमूर्त मशीन
- लैम्ब्डा कैलकुलस परिभाषा - लैम्ब्डा कैलकुलस की औपचारिक परिभाषा।
- चलो अभिव्यक्ति - एक अभिव्यक्ति एक अमूर्त से निकटता से संबंधित है।
- न्यूनतमवाद (कंप्यूटिंग)
- पुनर्लेखन - औपचारिक प्रणालियों में सूत्र का परिवर्तन
- SECD मशीन - लैम्ब्डा कैलकुलस के लिए डिज़ाइन की गई एक वर्चुअल मशीन
- स्कॉट-करी प्रमेय - लैम्ब्डा शर्तों के सेट के बारे में एक प्रमेय
- एक मॉकिंगबर्ड का मज़ाक उड़ाना - कॉम्बिनेटरी लॉजिक का परिचय
- यूनिवर्सल ट्यूरिंग मशीन - एक औपचारिक कंप्यूटिंग मशीन जो लैम्ब्डा कैलकुलस के बराबर है
- अनलैम्ब्डा - संयोजन तर्क पर आधारित एक गूढ़ प्रोग्रामिंग भाषा कार्यात्मक प्रोग्रामिंग भाषा
अग्रिम पठन
- Abelson, Harold & Gerald Jay Sussman. Structure and Interpretation of Computer Programs. The MIT Press. ISBN 0-262-51087-1.
- Hendrik Pieter Barendregt Introduction to Lambda Calculus.
- Henk Barendregt, The Impact of the Lambda Calculus in Logic and Computer Science. The Bulletin of Symbolic Logic, Volume 3, Number 2, June 1997.
- Barendregt, Hendrik Pieter, The Type Free Lambda Calculus pp1091–1132 of Handbook of Mathematical Logic, North-Holland (1977) ISBN 0-7204-2285-X
- Cardone and Hindley, 2006. History of Lambda-calculus and Combinatory Logic. In Gabbay and Woods (eds.), Handbook of the History of Logic, vol. 5. Elsevier.
- Church, Alonzo, An unsolvable problem of elementary number theory, American Journal of Mathematics, 58 (1936), pp. 345–363. This paper contains the proof that the equivalence of lambda expressions is in general not decidable.
- Church, Alonzo (1941). The Calculi of Lambda-Conversion. Princeton: Princeton University Press. Retrieved 2020-04-14. (ISBN 978-0-691-08394-0)
- Frink Jr., Orrin (1944). "Review: The Calculi of Lambda-Conversion by Alonzo Church" (PDF). Bull. Amer. Math. Soc. 50 (3): 169–172. doi:10.1090/s0002-9904-1944-08090-7.
- Kleene, Stephen, A theory of positive integers in formal logic, American Journal of Mathematics, 57 (1935), pp. 153–173 and 219–244. Contains the lambda calculus definitions of several familiar functions.
- Landin, Peter, A Correspondence Between ALGOL 60 and Church's Lambda-Notation, Communications of the ACM, vol. 8, no. 2 (1965), pages 89–101. Available from the ACM site. A classic paper highlighting the importance of lambda calculus as a basis for programming languages.
- Larson, Jim, An Introduction to Lambda Calculus and Scheme. A gentle introduction for programmers.
- Michaelson, Greg (10 April 2013). An Introduction to Functional Programming Through Lambda Calculus (in English). Courier Corporation. ISBN 978-0-486-28029-5.[41]
- Schalk, A. and Simmons, H. (2005) An introduction to λ-calculi and arithmetic with a decent selection of exercises. Notes for a course in the Mathematical Logic MSc at Manchester University.
- de Queiroz, Ruy J.G.B. (2008). "On Reduction Rules, Meaning-as-Use and Proof-Theoretic Semantics". Studia Logica. 90 (2): 211–247. doi:10.1007/s11225-008-9150-5. S2CID 11321602. A paper giving a formal underpinning to the idea of 'meaning-is-use' which, even if based on proofs, it is different from proof-theoretic semantics as in the Dummett–Prawitz tradition since it takes reduction as the rules giving meaning.
- Hankin, Chris, An Introduction to Lambda Calculi for Computer Scientists, ISBN 0954300653
- Monographs/textbooks for graduate students
- Morten Heine Sørensen, Paweł Urzyczyn, Lectures on the Curry–Howard isomorphism, Elsevier, 2006, ISBN 0-444-52077-5 is a recent monograph that covers the main topics of lambda calculus from the type-free variety, to most typed lambda calculi, including more recent developments like pure type systems and the lambda cube. It does not cover subtyping extensions.
- Pierce, Benjamin (2002), Types and Programming Languages, MIT Press, ISBN 0-262-16209-1 covers lambda calculi from a practical type system perspective; some topics like dependent types are only mentioned, but subtyping is an important topic.
- Documents
- Achim Jung, A Short Introduction to the Lambda Calculus-(PDF)
- Dana Scott, A timeline of lambda calculus-(PDF)
- Raúl Rojas, A Tutorial Introduction to the Lambda Calculus-(PDF)
- Peter Selinger, Lecture Notes on the Lambda Calculus-(PDF)
- Marius Buliga, Graphic lambda calculus
- Lambda Calculus as a Workflow Model by Peter Kelly, Paul Coddington, and Andrew Wendelborn; mentions graph reduction as a common means of evaluating lambda expressions and discusses the applicability of lambda calculus for distributed computing (due to the Church–Rosser property, which enables parallel graph reduction for lambda expressions).
टिप्पणियाँ
- ↑ These rules produce expressions such as: . Parentheses can be dropped if the expression is unambiguous. For some applications, terms for logical and mathematical constants and operations may be included.
- ↑ 2.0 2.1 2.2 Barendregt,Barendsen (2000) call this form
- axiom β: (λx.M[x]) N = M[N] , rewritten as (λx.M) N = M[x := N], "where [x := N] denotes substitution of N for x".[1]: 7 Also denoted M[N/x], "the substitution of N for x in M". (nlab)
- ↑ For a full history, see Cardone and Hindley's "History of Lambda-calculus and Combinatory Logic" (2006).
- ↑ 4.0 4.1 Note that is pronounced "maps to".
- ↑ The expression e can be: variables x, lambda abstractions, or applications —in BNF, .— from Wikipedia's Simply typed lambda calculus#Syntax for untyped lambda calculus
- ↑ is sometimes written in ASCII as
- ↑ In anonymous form, gets rewritten to .
- ↑ free variables in lambda Notation and its Calculus are comparable to linear algebra and mathematical concepts of the same name
- ↑ The set of free variables of M, but with {x} removed
- ↑ The union of the set of free variables of and the set of free variables of [1]
- ↑ (λf.M) N can be pronounced "let f be N in M".
- ↑ Ariola and Blom[26] employ 1) axioms for a representational calculus using well-formed cyclic lambda graphs extended with letrec, to detect possibly infinite unwinding trees; 2) the representational calculus with β-reduction of scoped lambda graphs constitute Ariola/Blom's cyclic extension of lambda calculus; 3) Ariola/Blom reason about strict languages using § call-by-value, and compare to Moggi's calculus, and to Hasegawa's calculus. Conclusions on p. 111.[26]
संदर्भ
Some parts of this article are based on material from FOLDOC, used with permission.
- ↑ 1.0 1.1 1.2 Barendregt, Henk; Barendsen, Erik (March 2000), Introduction to Lambda Calculus (PDF)
- ↑ Turing, Alan M. (December 1937). "Computability and λ-Definability". The Journal of Symbolic Logic. 2 (4): 153–163. doi:10.2307/2268280. JSTOR 2268280. S2CID 2317046.
- ↑ Coquand, Thierry (8 February 2006). Zalta, Edward N. (ed.). "Type Theory". The Stanford Encyclopedia of Philosophy (Summer 2013 ed.). Retrieved November 17, 2020.
- ↑ Moortgat, Michael (1988). Categorial Investigations: Logical and Linguistic Aspects of the Lambek Calculus. Foris Publications. ISBN 9789067653879.
- ↑ Bunt, Harry; Muskens, Reinhard, eds. (2008). Computing Meaning. Springer. ISBN 978-1-4020-5957-5.
- ↑ Mitchell, John C. (2003). Concepts in Programming Languages. Cambridge University Press. p. 57. ISBN 978-0-521-78098-8..
- ↑ Pierce, Benjamin C. Basic Category Theory for Computer Scientists. p. 53.
- ↑ Church, Alonzo (1932). "A set of postulates for the foundation of logic". Annals of Mathematics. Series 2. 33 (2): 346–366. doi:10.2307/1968337. JSTOR 1968337.
- ↑ Kleene, Stephen C.; Rosser, J. B. (July 1935). "The Inconsistency of Certain Formal Logics". The Annals of Mathematics. 36 (3): 630. doi:10.2307/1968646. JSTOR 1968646.
- ↑ Church, Alonzo (December 1942). "Review of Haskell B. Curry, The Inconsistency of Certain Formal Logics". The Journal of Symbolic Logic. 7 (4): 170–171. doi:10.2307/2268117. JSTOR 2268117.
- ↑ 11.0 11.1 Church, Alonzo (1936). "An unsolvable problem of elementary number theory". American Journal of Mathematics. 58 (2): 345–363. doi:10.2307/2371045. JSTOR 2371045.
- ↑ Church, Alonzo (1940). "A Formulation of the Simple Theory of Types". Journal of Symbolic Logic. 5 (2): 56–68. doi:10.2307/2266170. JSTOR 2266170. S2CID 15889861.
- ↑ Partee, B. B. H.; ter Meulen, A.; Wall, R. E. (1990). Mathematical Methods in Linguistics. Springer. ISBN 9789027722454. Retrieved 29 Dec 2016.
- ↑ Alma, Jesse. Zalta, Edward N. (ed.). "The Lambda Calculus". The Stanford Encyclopedia of Philosophy (Summer 2013 ed.). Retrieved November 17, 2020.
- ↑ Dana Scott, "Looking Backward; Looking Forward", Invited Talk at the Workshop in honour of Dana Scott’s 85th birthday and 50 years of domain theory, 7–8 July, FLoC 2018 (talk 7 July 2018). The relevant passage begins at 32:50. (See also this extract of a May 2016 talk at the University of Birmingham, UK.)
- ↑ "D. A. Turner "Some History of Functional Programming Languages" in an invited lecture TFP12, St Andrews University, 12 June 2012. See the section on Algol 60" (PDF).
- ↑ Barendregt, Hendrik Pieter (1984). The Lambda Calculus: Its Syntax and Semantics. Studies in Logic and the Foundations of Mathematics. Vol. 103 (Revised ed.). North Holland. ISBN 0-444-87508-5.
- ↑ [dead link]Corrections.
- ↑ 19.0 19.1 "Example for Rules of Associativity". Lambda-bound.com. Retrieved 2012-06-18.
- ↑ "The Basic Grammar of Lambda Expressions". SoftOption.
Some other systems use juxtaposition to mean application, so 'ab' means 'a@b'. This is fine except that it requires that variables have length one so that we know that 'ab' is two variables juxtaposed not one variable of length 2. But we want to labels like 'firstVariable' to mean a single variable, so we cannot use this juxtaposition convention.
- ↑ 21.0 21.1 Selinger, Peter (2008), Lecture Notes on the Lambda Calculus (PDF), vol. 0804, Department of Mathematics and Statistics, University of Ottawa, p. 9, arXiv:0804.3434, Bibcode:2008arXiv0804.3434S
- ↑ de Queiroz, Ruy J. G. B. (1988). "A Proof-Theoretic Account of Programming and the Role of Reduction Rules". Dialectica. 42 (4): 265–282. doi:10.1111/j.1746-8361.1988.tb00919.x.
- ↑ Turbak, Franklyn; Gifford, David (2008), Design concepts in programming languages, MIT press, p. 251, ISBN 978-0-262-20175-9
- ↑ Luke Palmer (29 Dec 2010) Haskell-cafe: What's the motivation for η rules?
- ↑ Felleisen, Matthias; Flatt, Matthew (2006), Programming Languages and Lambda Calculi (PDF), p. 26, archived from the original (PDF) on 2009-02-05; A note (accessed 2017) at the original location suggests that the authors consider the work originally referenced to have been superseded by a book.
- ↑ 26.0 26.1 Zena M. Ariola and Stefan Blom, Proc. TACS '94 Sendai, Japan 1997 (1997) Cyclic lambda calculi 114 pages.
- ↑ Ker, Andrew D. "Lambda Calculus and Types" (PDF). p. 6. Retrieved 14 January 2022.
- ↑ Dezani-Ciancaglini, Mariangiola; Ghilezan, Silvia (2014). "Preciseness of Subtyping on Intersection and Union Types" (PDF). Rewriting and Typed Lambda Calculi. Lecture Notes in Computer Science. 8560: 196. doi:10.1007/978-3-319-08918-8_14. hdl:2318/149874. ISBN 978-3-319-08917-1. Retrieved 14 January 2022.
- ↑ Forster, Yannick; Smolka, Gert (August 2019). "Call-by-Value Lambda Calculus as a Model of Computation in Coq" (PDF). Journal of Automated Reasoning. 63 (2): 393–413. doi:10.1007/s10817-018-9484-2. S2CID 53087112. Retrieved 14 January 2022.
- ↑ Types and Programming Languages, p. 273, Benjamin C. Pierce
- ↑ Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press. p. 56. ISBN 0-262-16209-1.
- ↑ Sestoft, Peter (2002). "Demonstrating Lambda Calculus Reduction" (PDF). The Essence of Computation. Lecture Notes in Computer Science. 2566: 420–435. doi:10.1007/3-540-36377-7_19. ISBN 978-3-540-00326-7. Retrieved 22 August 2022.
- ↑ Biernacka, Małgorzata; Charatonik, Witold; Drab, Tomasz (2022). Andronick, June; de Moura, Leonardo (eds.). "The Zoo of Lambda-Calculus Reduction Strategies, And Coq" (PDF). 13th International Conference on Interactive Theorem Proving (ITP 2022). 237: 7:1–7:19. doi:10.4230/LIPIcs.ITP.2022.7. Retrieved 22 August 2022.
- ↑ Frandsen, Gudmund Skovbjerg; Sturtivant, Carl (26 August 1991). "What is an Efficient Implementation of the \lambda-calculus?". Proceedings of the 5th ACM Conference on Functional Programming Languages and Computer Architecture. Lecture Notes in Computer Science. Springer-Verlag. 523: 289–312. CiteSeerX 10.1.1.139.6913. doi:10.1007/3540543961_14. ISBN 9783540543961.
- ↑ Sinot, F.-R. (2005). "Director Strings Revisited: A Generic Approach to the Efficient Representation of Free Variables in Higher-order Rewriting" (PDF). Journal of Logic and Computation. 15 (2): 201–218. doi:10.1093/logcom/exi010.
- ↑ Accattoli, Beniamino; Dal Lago, Ugo (14 July 2014). "Beta reduction is invariant, indeed" (PDF). Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS): 1–10. arXiv:1601.01233. doi:10.1145/2603088.2603105. ISBN 9781450328869. S2CID 11485010.
- ↑ 37.0 37.1 Accattoli, Beniamino (October 2018). "(In)Efficiency and Reasonable Cost Models". Electronic Notes in Theoretical Computer Science. 338: 23–43. doi:10.1016/j.entcs.2018.10.003.
- ↑ 38.0 38.1 Asperti, Andrea (16 Jan 2017). "About the efficient reduction of lambda terms" (PDF). arXiv:1701.04240v1. Retrieved 19 August 2021.
{{cite journal}}: Cite journal requires|journal=(help) - ↑ Landin, P. J. (1965). "A Correspondence between ALGOL 60 and Church's Lambda-notation". Communications of the ACM. 8 (2): 89–101. doi:10.1145/363744.363749. S2CID 6505810.
- ↑ Scott, Dana (1993). "A type-theoretical alternative to ISWIM, CUCH, OWHY" (PDF). Theoretical Computer Science. 121 (1–2): 411–440. doi:10.1016/0304-3975(93)90095-B. Retrieved 2022-12-01. Written 1969, widely circulated as an unpublished manuscript.
- ↑ "Greg Michaelson's Homepage". Mathematical and Computer Sciences. Riccarton, Edinburgh: Heriot-Watt University. Retrieved 6 November 2022.
बाहरी संबंध
- Graham Hutton, Lambda Calculus, a short (12 minutes) Computerphile video on the Lambda Calculus
- Helmut Brandl, Step by Step Introduction to Lambda Calculus
- "Lambda-calculus", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
- David C. Keenan, To Dissect a Mockingbird: A Graphical Notation for the Lambda Calculus with Animated Reduction
- L. Allison, Some executable λ-calculus examples
- Georg P. Loczewski, The Lambda Calculus and A++
- Bret Victor, Alligator Eggs: A Puzzle Game Based on Lambda Calculus
- Lambda Calculus Archived 2012-10-14 at the Wayback Machine on Safalra's Website Archived 2021-05-02 at the Wayback Machine
- LCI Lambda Interpreter a simple yet powerful pure calculus interpreter
- Lambda Calculus links on Lambda-the-Ultimate
- Mike Thyer, Lambda Animator, a graphical Java applet demonstrating alternative reduction strategies.
- Implementing the Lambda calculus using C++ Templates
- Shane Steinert-Threlkeld, "Lambda Calculi", Internet Encyclopedia of Philosophy
- Anton Salikhmetov, Macro Lambda Calculus
