फिक्स्ड-पॉइंट कॉम्बिनेटर

सामान्यतः गणित और कंप्यूटर विज्ञान में, फंक्शन का एक निश्चित बिंदु (गणित) एक मान होता है। जिसे फंक्शन द्वारा स्वयं मैप किया जाता है।

कंप्यूटर विज्ञान के लिए संयोजन तर्क में, 'नियत-बिंदु संयोजक' (या 'फिक्सपॉइंट संयोजक') उच्च-क्रम ${\textsf {fix}}$ का कार्य है। जो इसके तर्क कार्य के कुछ निश्चित बिंदु लौटाता है। यदि कोई उपस्थित है।

औपचारिक रूप से, यदि फंक्शन f में एक या अधिक निश्चित बिंदु हैं, तो

${\textsf {fix}}\ f=f\ ({\textsf {fix}}\ f)\ ,$

और इसलिए, बार-बार आवेदन करके,

${\textsf {fix}}\ f=f\ (f\ (\ldots f\ ({\textsf {fix}}\ f)\ldots ))\ .$

वाई संयोजक

मौलिक अप्रकाशित लैम्ब्डा कैलकुलस में, प्रत्येक फंक्शन का निश्चित बिंदु होता है।

फिक्स का विशेष कार्यान्वयन है हास्केल करी का विरोधाभासी संयोजक वाई, द्वारा दर्शाया गया है।

${\textsf {Y}}=\lambda f.\ (\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))\ .$

कार्यात्मक प्रोग्रामिंग में, वाई संयोजक का उपयोग प्रोग्रामिंग भाषा में औपचारिक रूप से रिकर्सन (कंप्यूटर विज्ञान) को परिभाषित करने के लिए किया जा सकता है। जो रिकर्सन का समर्थन नहीं करता है।

इस संयोजक का उपयोग करी के विरोधाभास को प्रयुक्त करने में किया जा सकता है। करी के विरोधाभास का दिल यह है कि अनटाइप्ड लैम्ब्डा कैलकुलस डिडक्टिव प्रणाली के रूप में अस्वास्थ्यकर है, और वाई संयोजक अज्ञात अभिव्यक्ति को शून्य, या यहां तक ​​​​कि कई मूल्यों का प्रतिनिधित्व करने की अनुमति देकर इसे प्रदर्शित करता है। यह गणितीय तर्क में असंगत है।

चर के साथ एक फंक्शन पर प्रयुक्त, Y संयोजक सामान्यतः समाप्त नहीं होता है। Y संयोजक को दो या दो से अधिक चर के कार्यों में प्रयुक्त करने से अधिक रोचक परिणाम प्राप्त होते हैं। अतिरिक्त चर का उपयोग काउंटर या इंडेक्स के रूप में किया जा सकता है। परिणामी फंक्शन अनिवार्य भाषा में जबकि या के लिए लूप की तरह व्यवहार करता है।

इस तरह प्रयोग किया जाता है, वाई संयोजक सरल पुनरावर्तन प्रयुक्त करता है। लैम्ब्डा कैलकुस में, नाम से अपने शरीर के अंदर किसी फंक्शन की परिभाषा को संदर्भित करना संभव नहीं है। पुनरावर्तन चूँकि उसी फंक्शन को तर्क के रूप में पारित करके प्राप्त किया जा सकता है, और फिर उस तर्क का उपयोग फंक्शन के स्वयं के नाम का उपयोग करने के अतिरिक्त पुनरावर्ती कॉल करने के लिए किया जाता है, जैसा कि उन भाषाओं में किया जाता है। जो मूल रूप से पुनरावर्तन का समर्थन करते हैं। वाई संयोजक प्रोग्रामिंग की इस शैली को प्रदर्शित करता है।

दो भाषाओं में वाई संयोजक के कार्यान्वयन का उदाहरण नीचे प्रस्तुत किया गया है।

# Y Combinator in Python

Y=lambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))

Y(Y)

// Y Combinator in C++

int main() {
    auto Y = [](auto f) {
        auto f1 = [f](auto x) -> decltype(f) {
            // A print statement may be inserted here,
            // to observe that we get an infinite loop
            // (at least until the stack overflows)
            return f(x(x));
        };
        return f1(f1);
    };

    Y(Y);
}

फिक्स्ड-पॉइंट संयोजक

Y संयोजक लैम्ब्डा कैलकुलस में निश्चित-बिंदु संयोजक का कार्यान्वयन है। फिक्स्ड-पॉइंट संयोजक को अन्य कार्यात्मक और अनिवार्य भाषाओं में भी सरलता से परिभाषित किया जा सकता है। लैम्ब्डा कैलकुलस में सीमाओं के कारण लैम्ब्डा कैलकुलस में कार्यान्वयन अधिक कठिन है।

फिक्स्ड-पॉइंट संयोजक का उपयोग कई अलग-अलग क्षेत्रों में किया जा सकता है।

• अंक शास्त्र
• लैम्ब्डा कैलकुलस टाइप किया
• टाइप लैम्ब्डा कैलकुस
• कार्यात्मक प्रोग्रामिंग
• अनिवार्य प्रोग्रामिंग

फिक्स्ड-पॉइंट संयोजक को विभिन्न कार्यों की श्रृंखला पर प्रयुक्त किया जा सकता है, किन्तु सामान्यतः तब तक समाप्त नहीं होगा जब तक कोई अतिरिक्त मापदंड न हो जब तय किया जाने वाला फंक्शन इसके मापदंड को संदर्भित करता है, तो फंक्शन के लिए एक और कॉल प्रारंभ हो जाती है। इसलिए गणना कभी प्रारंभ नहीं होती है। इसके अतिरिक्त, गणना की प्रारंभ को ट्रिगर करने के लिए अतिरिक्त मापदंड का उपयोग किया जाता है।

निश्चित बिंदु का प्रकार निश्चित होने वाले फंक्शन का रिटर्न प्रकार है। यह वास्तविक या कार्य या कोई अन्य प्रकार हो सकता है।

अनटाइप्ड लैम्ब्डा कैलकुलस में, फिक्स्ड-पॉइंट संयोजक को प्रयुक्त करने के लिए फंक्शन को एन्कोडिंग का उपयोग करके व्यक्त किया जा सकता है, जैसे चर्च एन्कोडिंग इस स्थिति में विशेष लैम्ब्डा शब्द (जो कार्यों को परिभाषित करते हैं) को मान के रूप में माना जाता है। एन्कोडिंग पर फिक्स्ड-पॉइंट संयोजक चलाना (बीटा कम करना) परिणाम के लिए लैम्ब्डा शब्द देता है। जिसे तब निश्चित-बिंदु मान के रूप में व्याख्या किया जा सकता है।

वैकल्पिक रूप से, फंक्शन को लैम्ब्डा कैलकुस में पूरी तरह परिभाषित लैम्ब्डा शब्द के रूप में माना जा सकता है।

ये अलग-अलग दृष्टिकोण इस बात को प्रभावित करते हैं कि गणितज्ञ और प्रोग्रामर निश्चित-बिंदु संयोजक को कैसे मान सकते हैं। लैम्ब्डा कैलकुलस गणितज्ञ किसी फंक्शन पर प्रयुक्त Y संयोजक को निश्चित-बिंदु समीकरण को संतुष्ट करने वाली अभिव्यक्ति और इसलिए समाधान के रूप में देख सकता है।

इसके विपरीत, व्यक्ति केवल कुछ सामान्य प्रोग्रामिंग कार्य के लिए निश्चित-बिंदु संयोजक प्रयुक्त करना चाहता है। इसे केवल पुनरावर्तन को प्रयुक्त करने के साधन के रूप में देख सकता है।

मान और डोमेन

प्रत्येक अभिव्यक्ति का मूल्य होता है। यह सामान्य गणित में सच है और लैम्ब्डा कैलकुस में यह सच होना चाहिए। इसका कारण यह है कि लैम्ब्डा कैलकुलस में, निश्चित-बिंदु संयोजक को फंक्शन पर प्रयुक्त करने से आपको अभिव्यक्ति मिलती है। जिसका मान फंक्शन का निश्चित बिंदु होता है।

चूँकि, यह डिडक्टिव लैम्ब्डा कैलकुलस सेट सिद्धान्तिक डोमेन में एक मान है। यह फंक्शन के डोमेन में किसी भी मान के अनुरूप नहीं हो सकता है। इसलिए व्यावहारिक अर्थों में यह आवश्यक रूप से फंक्शन का निश्चित बिंदु नहीं है, और केवल में लैम्ब्डा कैलकुस डोमेन यह समीकरण का निश्चित बिंदु है।

उदाहरण के लिए विचार करें

$x^{2}=-1\Rightarrow x={\frac {-1}{x}}\Rightarrow f\ x={\frac {-1}{x}}\land {\mathsf {Y}}\ f=x$

चर्च एन्कोडिंग चर्च एन्कोडिंग का विभाजन हस्ताक्षरित संख्या चर्च एन्कोडिंग में प्रयुक्त की जा सकती है। इसलिए f को लैम्ब्डा शब्द द्वारा दर्शाया जा सकता है। इस समीकरण का वास्तविक संख्याओं में कोई हल नहीं है। परंतु सम्मिश्र संख्याओं के क्षेत्र में i और -i हल हैं। यह दर्शाता है कि दूसरे डोमेन में समीकरण के समाधान हो सकते हैं। चूँकि, उपरोक्त समीकरण के समाधान के लिए लैम्ब्डा शब्द उससे अधिक सही है। लैम्ब्डा शब्द ${\mathsf {Y}}\ f$ उस अवस्था का प्रतिनिधित्व करता है। जहाँ x या तो i या -i हो सकता है, एक मान के रूप में डोमेन के परिवर्तन में इन दो मूल्यों को अलग करने वाली जानकारी खो गई है। ध्यान दें कि यह अभी भी एकल मान के रूप में दर्शाया जा सकता है। यदि तर्क को पैराकंसिस्टेंट तर्क के रूप में विस्तारित किया गया है।

लैम्ब्डा कैलकुलस गणितज्ञ के लिए, यह लैम्ब्डा कैलकुलस की परिभाषा का परिणाम है। प्रोग्रामर के लिए, इसका कारण है कि लैम्ब्डा शब्द की बीटा कमी सदैव के लिए लूप हो जाएगी | कभी भी सामान्यतः तक नहीं पहुंच पाएगी।

कार्य बनाम कार्यान्वयन

फिक्स्ड-पॉइंट संयोजक को गणित में परिभाषित किया जा सकता है और फिर अन्य भाषाओं में प्रयुक्त किया जा सकता है। सामान्य गणित अपने विस्तार गुणों के आधार पर फंक्शन को परिभाषित करता है। अर्थात्, यदि वे समान मानचित्रण करते हैं तो दो कार्य समान होते हैं। लैम्ब्डा कैलकुलस और प्रोग्रामिंग लैंग्वेज फंक्शन आइडेंटिटी को परिभाषा प्रॉपर्टी के रूप में मानते हैं। किसी फंक्शन की पहचान उसके कार्यान्वयन पर आधारित होती है।

लैम्ब्डा कैलकुस फंक्शन (या टर्म) गणितीय फंक्शन का कार्यान्वयन है। लैम्ब्डा कैलकुलस में कई संयोजक (कार्यान्वयन) हैं जो निश्चित-बिंदु संयोजक की गणितीय परिभाषा को पूरा करते हैं।

संयोजक शब्द की परिभाषा

संयोजन तर्क उच्च-क्रम कार्य सिद्धांत है। संयोजक एक बंद लैम्ब्डा अभिव्यक्ति है, जिसका अर्थ है कि इसमें कोई मुक्त चर नहीं है। कॉम्बिनेटरों को अभिव्यक्ति में उनके सही स्थानों पर सीधे मूल्यों के साथ जोड़ा जा सकता है। उन्हें कभी भी चर के रूप में नाम दिए बिना किया जाता है।

प्रोग्रामिंग में उपयोग

फंक्शन की पुनरावर्ती परिभाषा को प्रयुक्त करने के लिए फिक्स्ड-पॉइंट संयोजक का उपयोग किया जा सकता है। चूँकि, व्यावहारिक प्रोग्रामिंग में उनका उपयोग संभवतः ही कभी किया जाता है। सामान्यतः टाइप किए गए लैम्ब्डा कैलकुस जैसे सामान्यतः सामान्यीकृत प्रकार प्रणाली गैर-समाप्ति को अस्वीकार करते हैं और इसलिए फिक्स्ड-पॉइंट संयोजक को अधिकांशतः एक प्रकार नहीं दिया जा सकता है या जटिल प्रकार प्रणाली सुविधाओं की आवश्यकता नहीं होती है। इसके अतिरिक्त फिक्स्ड-पॉइंट संयोजक अधिकांशतः रिकर्सन को प्रयुक्त करने के लिए अन्य रणनीतियों की तुलना में अक्षम होते हैं | क्योंकि उन्हें अधिक फंक्शन क्षय की आवश्यकता होती है और पारस्परिक रूप से पुनरावर्ती परिभाषाओं के प्रत्येक समूह के लिए टपल का निर्माण और अलग करना पड़ता है।

फैक्टोरियल फंक्शन

फैक्टोरियल फंक्शन एक अच्छा उदाहरण प्रदान करता है कि फिक्स्ड-पॉइंट संयोजक कैसे प्रयुक्त किया जा सकता है। परिणाम सरल पुनरावर्तन प्रदर्शित करता है, जैसा कि अनिवार्य भाषा में लूप में प्रयुक्त किया जाएगा। प्रयुक्त संख्याओं की परिभाषा चर्च कोडिंग में समझाई गई है।

मापदंड के रूप में स्वयं को लेने वाला कार्य है।

$F\ f\ n=(\operatorname {IsZero} \ n)\ 1\ (\operatorname {multiply} \ n\ (f\ (\operatorname {pred} \ n)))\ .$

यह Y F n के रूप में देता है।

${\begin{aligned}{\textsf {fix}}\ F\ n&=F\ ({\textsf {fix}}\ F)\ n\\&=(\operatorname {IsZero} \ n)\ 1\ (\operatorname {multiply} \ n\ (({\textsf {fix}}\ F)\ (\operatorname {pred} \ n)))\ .\end{aligned}}$

सेटिंग ${\textsf {fix}}\ F=\operatorname {fact}$ देता है।

$\operatorname {fact} \ n=(\operatorname {IsZero} \ n)\ 1\ (\operatorname {multiply} \ n\ (\operatorname {fact} \ (\operatorname {pred} \ n)))\ .$

यह परिभाषा F को पुनरावृत्त होने वाले लूप के शरीर की भूमिका में रखती है, और फैक्टोरियल की गणितीय परिभाषा के समान है।

$\operatorname {fact} \ n={\begin{cases}1&{\text{if}}~n=0\\n\times \operatorname {fact} \ (n-1)&{\text{otherwise.}}\end{cases}}$

लैम्ब्डा कैलकुलस में फिक्स्ड-पॉइंट संयोजक

हास्केल बी. करी द्वारा खोजे गए Y संयोजक को इस रूप में परिभाषित किया गया है।

$Y=\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))$

बीटा कमी से हमारे पास है।

$\ \ \ \ Y\ g\$	$=(\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)))\ g$	(वाई की परिभाषा के अनुसार)
	$=(\lambda x.g\ (x\ x))\ (\lambda x.g\ (x\ x))$	(λf की β-कमी द्वारा: Y से g पर प्रयुक्त)
	$=g\ ((\lambda x.g\ (x\ x))\ (\lambda x.g\ (x\ x)))$	(λx की β-कमी द्वारा: बाएं फ़ंक्शन को दाएं फ़ंक्शन पर प्रयुक्त किया गया)
	$=g\ (Y\ g)$	(द्वितीय समानता द्वारा)

बार-बार इस समानता को प्रयुक्त करने से मिलता है।

$Y\ g=g\ (Y\ g)=g\ (g\ (Y\ g))=g\ (\ldots g\ (Y\ g)\ldots )$

(उपरोक्त समानता को बाएं से दाएं बहु-चरण β-क्षय के अनुक्रम के रूप में माना जाना चाहिए। लैम्ब्डा शब्द $g\ (Y\ g)$ हो सकता है। सामान्यतः, β-पद तक कम न हो $Y\ g$. दोनों दिशाओं में जाने की अनुमति देने के लिए बहु-चरण β-क्षय के अतिरिक्त समानता के संकेतों को β-तुल्यता के रूप में व्याख्या कर सकते हैं।)

फिक्स्ड-पॉइंट संयोजक की समतुल्य परिभाषा

इस निश्चित-बिंदु संयोजक को y के रूप में परिभाषित किया जा सकता है।

$x=f\ x\land y\ f=x$

y के लिए अभिव्यक्ति लेट एक्सप्रेशन से नियमों का उपयोग करके प्राप्त की जा सकती है। गणित में परिभाषा दें। सबसे पहले, नियम का उपयोग करता है।

$(\exists xE\land F)\iff \operatorname {let} x:E\operatorname {in} F$

देता है

$\operatorname {let} x=f\ x\operatorname {in} y\ f=x$

साथ ही, प्रयोग कर रहा है।

$x\not \in \operatorname {FV} (E)\land x\in \operatorname {FV} (F)\to \operatorname {let} x:G\operatorname {in} E\ F=E\ (\operatorname {let} x:G\operatorname {in} F)$

देता है।

$y\ f=\operatorname {let} x=f\ x\operatorname {in} x$

और फिर डिडक्टिव लैम्ब्डा कैलकुलस ईटा रिडक्शन को गणित के नियम के रूप में उपयोग करता है।

$f\ x=y\iff f=\lambda x.y$

देता है।

$y=\lambda f.\operatorname {let} x=f\ x\operatorname {in} x$

वाई संयोजक की व्युत्पत्ति

करी के वाई संयोजक को सरलता से वाई की परिभाषा से प्राप्त किया जा सकता है।

हम प्रारंभ करते हैं |

$\lambda f.\operatorname {let} x=f\ x\operatorname {in} x$

लैम्ब्डा अमूर्त प्रयुक्त अभिव्यक्ति में चर नाम के संदर्भ का समर्थन नहीं करता है। इसलिए x को x के मापदंड के रूप में पारित किया जाना चाहिए। हम इसे x के स्थान पर x x के रूप में सोच सकते हैं, किन्तु औपचारिक रूप से यह सही नहीं है। इसके अतिरिक्त y को परिभाषित करना $\forall z,y\ z=x$ देता है।

$\lambda f.\operatorname {let} y\ z=f\ (y\ z)\operatorname {in} y\ z\ .$

लेट एक्सप्रेशन को फंक्शन y की परिभाषा के रूप में माना जा सकता है। जहाँ z मापदंड है। कॉल में y के रूप में तात्कालिकता z देता है।

$\lambda f.\operatorname {let} y\ z=f\ (y\ z)\operatorname {in} y\ y\ .$

और, क्योंकि मापदंड z सदैव फंक्शन y पास करता है।

$\lambda f.\operatorname {let} y\ z=f\ (z\ z)\operatorname {in} y\ y\ .$

डिडक्टिव लैम्ब्डा कैलकुलस ईटा रिडक्शन को गणित के नियम के रूप में उपयोग करता है।

$f\ x=y\equiv f=\lambda x.y\ ,$

देता है।

$\lambda f.\operatorname {let} y=\lambda z.f\ (z\ z)\operatorname {in} y\ y\ .$

ए लेट एक्सप्रेशन लेट डेफिनिशन इन मैथमेटिक्स; का उपयोग करते हुए

$n\not \in FV(E)\to (\operatorname {let} n=E\operatorname {in} L\equiv (\lambda n.L)\ E)$

देता है।

$\lambda f.(\lambda y.y\ y)\ (\lambda z.f\ (z\ z))\ .$

यह संभवतः लैम्ब्डा कैलकुलस में फिक्स्ड-पॉइंट संयोजक का सबसे सरल कार्यान्वयन है। चूँकि, बीटा कमी करी के वाई संयोजक का अधिक सममित रूप देती है:

$\lambda f.(\lambda z.f\ (z\ z))\ (\lambda z.f\ (z\ z))\ .$

लेट एक्सप्रेशन रूपांतरण को लैम्ब्डा एक्सप्रेशन में भी देखें।

अन्य फिक्स्ड-पॉइंट संयोजक

अनटाइप्ड लैम्ब्डा कैलकुलस फिक्स्ड-पॉइंट संयोजक विशेष रूप से दुर्लभ नहीं हैं। वास्तव में उनमें से अपरिमित रूप से बहुत से हैं। 2005 में मेयर गोल्डबर्ग ने दिखाया कि अनटाइप्ड लैम्ब्डा कैलकुलस के फिक्स्ड-पॉइंट कॉम्बिनेटर्स का सेट पुनरावर्ती रूप से गणनीय है।

Y संयोजक को एसकेआई संयोजक कैलकुलस सेल्फ-एप्लीकेशन एंड रिकर्सन एसकेआई-कैलकुलस में व्यक्त किया जा सकता है।

$Y=S(K(SII))(S(S(KS)K)(K(SII)))$

अतिरिक्त संयोजक (बी, सी, के, डब्ल्यू प्रणाली) बहुत छोटी परिभाषा के लिए अनुमति देते हैं। U = SII के साथ स्व-अनुप्रयोग संयोजक, चूंकि S(Kx)yz = x(yz) = Bxyz और Sx(Ky)z = xzy = Cxyz, उपरोक्त बन जाता है।

$Y=S(KU)(SB(KU))=BU(CBU)$

जॉन ट्रोम्प द्वारा खोजे गए एसके-कैलकुलस में सबसे सरल फिक्स्ड-पॉइंट संयोजक है।

$Y'=SSK(S(K(SS(S(SSK))))K)$

चूँकि ध्यान दें कि यह सामान्यतः में नहीं है, जो लंबा है। यह संयोजक लैम्ब्डा एक्सप्रेशन से मेल खाता है

$Y'=(\lambda xy.xyx)(\lambda yx.y(xyx))$

निम्नलिखित निश्चित-बिंदु संयोजक Y संयोजक की तुलना में सरल है, और β-Y संयोजक में कम हो जाता है; इसे कभी-कभी वाई संयोजक के रूप में उद्धृत किया जाता है।

$X=\lambda f.(\lambda x.xx)(\lambda x.f(xx))$

अन्य सामान्य फिक्स्ड-पॉइंट संयोजक ट्यूरिंग फिक्स्ड-पॉइंट संयोजक है।(इसके खोजकर्ता, एलन ट्यूरिंग के नाम पर):

$\Theta =(\lambda xy.y(xxy))\ (\lambda xy.y(xxy))$

इसका लाभ खत्म ${\textsf {Y}}$ यह है कि $\Theta \ f$ बीटा-कम $f\ (\Theta f)$ हो जाता है।

जबकि ${\textsf {Y}}\ f$ और $f\ ({\textsf {Y}}f)$ सामान्य शब्द के लिए केवल बीटा-कम करें।

$\Theta$ साधारण कॉल-बाय-वैल्यू फॉर्म भी है।

$\Theta _{v}=(\lambda xy.y(\lambda z.xxyz))\ (\lambda xy.y(\lambda z.xxyz))$

पारस्परिक पुनरावर्तन के लिए एनालॉग बहुभिन्नरूपी फिक्स-पॉइंट संयोजक है, जिसे Y* निरूपित किया जा सकता है।

अन्य निश्चित-बिंदु संयोजक

निश्चित प्रोग्रामिंग भाषा में Y संयोजक स्टैक ओवरफ्लो तक विस्तारित होगा, या टेल कॉल ऑप्टिमाइज़ेशन के स्थिति में कभी नहीं रुकेगा। जेड संयोजक निश्चित भाषाओं में काम करेगा (जिन्हें उत्सुक भाषाएं भी कहा जाता है, जहां प्रयुक्त मूल्यांकन आदेश प्रयुक्त होता है)। Z संयोजक का अगला तर्क स्पष्ट रूप से परिभाषित है, परिभाषा के दाईं ओर Z g के विस्तार को रोकता है।

$Zgv=g(Zg)v\ .$

और लैम्ब्डा कैलकुलस में यह वाई संयोजक का ईटा-विस्तार है।

$Z=\lambda f.(\lambda x.f(\lambda v.xxv))\ (\lambda x.f(\lambda v.xxv))\ .$

गैर-मानक फिक्स्ड-पॉइंट संयोजक

अनटाइप्ड लैम्ब्डा कैलकुलस में ऐसे शब्द होते हैं | जिनमें फिक्स्ड-पॉइंट संयोजक के रूप में एक ही बोहम ट्री होता है, अर्थात उनका एक ही अनंत विस्तार λx.x (x (x ... )) होता है। इन्हें गैर-मानक निश्चित-बिंदु संयोजक कहा जाता है। कोई भी निश्चित-बिंदु संयोजक भी गैर-मानक है, किन्तु सभी गैर-मानक निश्चित-बिंदु संयोजक निश्चित-बिंदु संयोजक नहीं हैं | क्योंकि उनमें से कुछ मानक को परिभाषित करने वाले समीकरण को संतुष्ट करने में विफल रहते हैं। इन अजीब कॉम्बिनेटरों को कड़ाई से गैर-मानक फिक्स्ड-पॉइंट संयोजक कहा जाता है। उदाहरण निम्नलिखित संयोजक है।

$N=BM(B(BM)B)$

जहाँ

$B=\lambda xyz.x(yz)$

$M=\lambda x.xx\ .$

गैर-मानक फिक्स्ड-पॉइंट कॉम्बिनेटर्स का सेट पुनरावर्ती गणना योग्य नहीं है।

अन्य भाषाओं में कार्यान्वयन

(Y संयोजक लैम्ब्डा कैलकुलस में फिक्स्ड-पॉइंट संयोजक का विशेष कार्यान्वयन है। इसकी संरचना लैम्ब्डा कैलकुलस की सीमाओं द्वारा निर्धारित की जाती है। अन्य भाषाओं में फिक्स्ड-पॉइंट संयोजक को प्रयुक्त करने में इस संरचना का उपयोग करना आवश्यक या सहायक नहीं है। )

कुछ प्रोग्रामिंग प्रतिमान में प्रयुक्त फिक्स्ड-पॉइंट कॉम्बिनेटर्स के सरल उदाहरण नीचे दिए गए हैं।

कार्यात्मक कार्यान्वयन

ऐसी भाषा में जो मूल्यांकन का समर्थन करती है, जैसे हास्केल (प्रोग्रामिंग भाषा) में, फिक्स्ड-पॉइंट संयोजक के परिभाषित समीकरण का उपयोग करके निश्चित-बिंदु संयोजक को परिभाषित करना संभव है। जिसे पारंपरिक रूप से नामित किया गया है। fix. चूंकि हास्केल में डेटाटाइप हैं, इसलिए इस संयोजक का उपयोग डेटा कंस्ट्रक्टर के निश्चित बिंदुओं को परिभाषित करने के लिए भी किया जा सकता है (और न केवल पुनरावर्ती कार्यों को प्रयुक्त करने के लिए)। परिभाषा यहां दी गई है, इसके बाद कुछ उपयोग उदाहरण दिए गए हैं। हैकेज में, मूल नमूना है।

fix, fix' :: (a -> a) -> a
fix f = let x = f x in x         -- Lambda dropped. Sharing.
                                 -- Original definition in Data.Function.
-- alternative:
fix' f = f (fix' f)              -- Lambda lifted. Non-sharing.

fix (\x -> 9)                    -- this evaluates to 9

fix (\x -> 3:x)                  -- evaluates to the lazy infinite list [3,3,3,...]

fact = fix fac                   -- evaluates to the factorial function
  where fac f 0 = 1
        fac f x = x * f (x-1)

fact 5                           -- evaluates to 120

निश्चित कार्यात्मक कार्यान्वयन

निश्चित कार्यात्मक भाषा में, जैसा कि ओ कैमल के साथ नीचे दिखाया गया है। f का तर्क पहले से विस्तारित है। अनंत कॉल अनुक्रम उत्पन्न करता है।

$f\ (f...(f\ ({\mathsf {fix}}\ f))...)\ x$.

इसे अतिरिक्त मापदंड के साथ फ़िक्स को परिभाषित करके हल किया जा सकता है।

let rec fix f x = f (fix f) x (* note the extra x; here fix f = \x-> f (fix f) x *)

let factabs fact = function   (* factabs has extra level of lambda abstraction *)
   0 -> 1
 | x -> x * fact (x-1)

let _ = (fix factabs) 5       (* evaluates to "120" *)

बहु-प्रतिमान कार्यात्मक भाषा में (अनिवार्य सुविधाओं से सजाया गया), जैसे लिस्प (प्रोग्रामिंग भाषा), लैंडिन (1963) फिक्स्ड-पॉइंट संयोजक बनाने के लिए वेरिएबल असाइनमेंट के उपयोग का सुझाव देता है, जैसा कि स्कीम (प्रोग्रामिंग लैंग्वेज) का उपयोग करते हुए नीचे दिए गए उदाहरण में दिया गया है।

(define Y!
  (lambda (f)
    ((lambda (i)                       
       (set! i (f (lambda (x) (i x)))) ;; (set! i expr) assigns i the value of expr
       i)                              ;; replacing it in the present lexical scope
     #f)))

असाइनमेंट स्टेटमेंट के लिए स्वयंसिद्धों के साथ लैम्ब्डा कैलकुलस का उपयोग करके, यह दिखाया जा सकता है। Y! कॉल-बाय-वैल्यू वाई संयोजक के समान निश्चित-बिंदु कानून को संतुष्ट करता है।

$({\textsf {Y}}_{!}\ \lambda x.e)e'=(\lambda x.e)\ ({\textsf {Y}}_{!}\ \lambda x.e)e'$

अधिक आधुनिक लिस्प उपयोग में, यह सामान्यतः लेक्सिकली स्कॉप्ड लेबल (ए let अभिव्यक्ति), क्योंकि 1970 के दशक तक लिस्प को शाब्दिक सीमा प्रस्तुत नहीं किया गया था |

(define Y*
  (lambda (f)
    ((lambda (i)
       (let ((i (f (lambda (x) (i x))))) ;; (let ((i expr)) i) locally defines i as expr
	     i))                             ;; non-recursively: thus i in expr is not expr
     #f)))

या आंतरिक लेबल के बिना है।

(define Y
  (lambda (f)
    ((lambda (i) (i i))
     (lambda (i)
       (f (lambda (x)
	        (apply (i i) x)))))))

अनिवार्य भाषा कार्यान्वयन

यह उदाहरण फिक्स्ड-पॉइंट संयोजक का थोड़ा व्याख्यात्मक कार्यान्वयन है। फिक्स फंक्शन को सम्मिलित करने के लिए वर्ग का उपयोग किया जाता है। जिसे फिक्सर कहा जाता है। तय किया जाने वाला कार्य उस वर्ग में समाहित है जो फिक्सर से विरासत में मिला है। फिक्स फंक्शन फंक्शन को वर्चुअल फंक्शन के रूप में ठीक करने के लिए एक्सेस करता है। निश्चित कार्यात्मक परिभाषा के लिए, फिक्स को स्पष्ट रूप से अतिरिक्त मापदंड x दिया गया है। जिसका अर्थ है कि मूल्यांकन की आवश्यकता नहीं है।

template <typename R, typename D>
class fixer
{
public:
    R fix(D x)
    {
        return f(x);
    }
private:
    virtual R f(D) = 0;
};

class fact : public fixer<long, long>
{
    virtual long f(long x)
    {
        if (x == 0)
        {
            return 1;
        }
        return x * fix(x-1);
    }
};

long result = fact().fix(5);

टाइपिंग

प्रणाली एफ (पॉलीमॉर्फिक लैम्ब्डा कैलकुलस) में पॉलीमॉर्फिक फिक्स्ड-पॉइंट संयोजक का प्रकार होता है।

∀a.(a → a) → a

जहां a प्रकार चर है। यही है, फिक्स एक फंक्शन लेता है, जो a → a मैप करता है और इसका उपयोग टाइप ए के मान को वापस करने के लिए करता है।

पुनरावर्ती डेटा प्रकार के साथ सरल रूप से टाइप किए गए लैम्ब्डा कैलकुलस में, फिक्स्ड-पॉइंट ऑपरेटर लिखे जा सकते हैं, किन्तु एक उपयोगी फिक्स्ड-पॉइंट ऑपरेटर (जिसका एप्लिकेशन सदैव वापस आता है) का प्रकार प्रतिबंधित हो सकता है।

सरल टाइप किए गए लैम्ब्डा कैलकुस में, फिक्स्ड-पॉइंट संयोजक वाई को एक प्रकार नहीं दिया जा सकता है। क्योंकि किसी बिंदु पर यह स्व-अनुप्रयोग उप-अवधि से निपटेगा $x~x$ आवेदन नियम द्वारा:

${\Gamma \vdash x\!:\!t_{1}\to t_{2}\quad \Gamma \vdash x\!:\!t_{1}} \over {\Gamma \vdash x~x\!:\!t_{2}}$

जहाँ $x$ अनंत प्रकार $t_{1}=t_{1}\to t_{2}$ है। वास्तव में कोई फिक्स-पॉइंट संयोजक टाइप नहीं किया जा सकता है। उन प्रणालियों में, पुनरावर्तन के लिए किसी भी समर्थन को भाषा में स्पष्ट रूप से जोड़ा जाना चाहिए।

वाई संयोजक के लिए टाइप करें

प्रोग्रामिंग भाषाओं में जो पुनरावर्ती डेटा प्रकारों का समर्थन करते हैं, टाइप स्तर पर रिकर्सन के लिए उचित रूप से लेखांकन करके वाई संयोजक टाइप करना संभव है। चर x को स्व-प्रयुक्त करने की आवश्यकता को एक प्रकार का उपयोग करके प्रबंधित किया जा सकता है। (Rec a), जिसे आइसोमोर्फिक (Rec a -> a). के रूप में परिभाषित किया गया है।

उदाहरण के लिए, निम्नलिखित हास्केल कोड में, हमारे पास है। In और out समरूपतावाद की दो दिशाओं के नाम, प्रकारों के साथ है।

In :: (Rec a -> a) -> Rec a
out :: Rec a -> (Rec a -> a)

जो हमें लिखने देता है।

newtype Rec a = In { out :: Rec a -> a }

y :: (a -> a) -> a
y = \f -> (\x -> f (out x x)) (In (\x -> f (out x x)))

या समकक्ष ओ कैमल में:

type 'a recc = In of ('a recc -> 'a)
let out (In x) = x

let y f = (fun x a -> f (out x x) a) (In (fun x a -> f (out x x) a))

वैकल्पिक रूप से:

let y f = (fun x -> f (fun z -> out x x z)) (In (fun x -> f (fun z -> out x x z)))

सामान्य जानकारी

चूंकि रिकर्सन को प्रयुक्त करने के लिए फिक्स्ड-पॉइंट संयोजक का उपयोग किया जा सकता है। इसलिए विशिष्ट प्रकार के रिकर्सिव कंप्यूटेशंस का वर्णन करने के लिए उनका उपयोग करना संभव है। जैसे फिक्स्ड-पॉइंट पुनरावृत्ति, पुनरावृत्ति विधियों, संबंध का डेटाबेस में रिकर्सिव जॉइन, डेटा-फ्लो विश्लेषण, सबसे पहले और गैर-टर्मिनलों के संदर्भ-मुक्त व्याकरण, सकर्मक समापन और अन्य प्रकार के समापन (गणित) संचालन में अनुसरण करें।

फंक्शन जिसके लिए प्रत्येक इनपुट एक निश्चित बिंदु है। पहचान फंक्शन कहलाता है। औपचारिक रूप से:

$\forall x(f\ x=x)$

सभी पर सार्वभौमिक परिमाणीकरण के विपरीत $x$, निश्चित-बिंदु संयोजक एक मान बनाता है जो कि $f$ एक निश्चित बिंदु है। फिक्स्ड-पॉइंट संयोजक की उल्लेखनीय संपत्ति यह है कि यह इच्छानुसार से दिए गए फंक्शन के लिए एक निश्चित बिंदु $f$ बनाता है।

अन्य कार्यों में यह विशेष गुण होता है कि एक बार प्रयुक्त होने के बाद आगे के अनुप्रयोगों का कोई प्रभाव नहीं पड़ता है। अधिक औपचारिक रूप से:

$\forall x(f\ (f\ x)=f\ x)$

ऐसे कार्यों को प्रोजेक्शन कहा जाता है (प्रोजेक्शन (गणित) भी देखें)। ऐसे फंक्शन का उदाहरण वह फंक्शन है। जो सभी सम पूर्णांकों के लिए 0 और सभी विषम पूर्णांकों के लिए 1 देता है।

लैम्ब्डा कैलकुस में, कम्प्यूटेशनल दृष्टिकोण से, निश्चित-बिंदु संयोजक को एक पहचान फंक्शन या इम्पोटेंट फंक्शन पर प्रयुक्त करने से सामान्यतः नॉन-टर्मिनेटिंग कम्प्यूटेशन होता है। उदाहरण के लिए, हम प्राप्त करते हैं |

$(Y\ \lambda x.x)=(\lambda x.(xx)\ \lambda x.(xx))$

जहां परिणामी शब्द केवल अपने आप को कम कर सकता है और अनंत लूप का प्रतिनिधित्व करता है।

कम्प्यूटेशन के अधिक प्रतिबंधात्मक मॉडल में फिक्स्ड-पॉइंट संयोजक आवश्यक रूप से उपस्थित नहीं हैं। उदाहरण के लिए, वे केवल टाइप किए गए लैम्ब्डा कैलकुलस में उपस्थित नहीं हैं।

वाई संयोजक पुनरावर्तन (कंप्यूटर विज्ञान) को उत्पादन (कंप्यूटर विज्ञान) के सेट के रूप में परिभाषित करने की अनुमति देता है, भाषा में देशी पुनरावर्तन समर्थन की आवश्यकता के बिना अज्ञात कार्यों का समर्थन करने वाली प्रोग्रामिंग भाषाओं में, फिक्स्ड-पॉइंट संयोजक अज्ञात पुनरावर्तन की परिभाषा और उपयोग की अनुमति देते हैं, अर्थात ऐसे कार्यों को पहचानकर्ताओं के लिए बाध्य किए बिना इस सेटिंग में, फिक्स्ड-पॉइंट कॉम्बिनेटर्स के उपयोग को कभी-कभी अज्ञात पुनरावर्तन कहा जाता है।

यह भी देखें

• अज्ञात फ़ंक्शन
• फिक्स्ड-पॉइंट पुनरावृत्ति
• लैम्ब्डा कैलकुस रिकर्सन और निश्चित बिंदु
• लैम्ब्डा उठाना
• लेट अभिव्यक्ति

संदर्भ

• Werner Kluge, Abstract computing machines: a lambda calculus perspective, Springer, 2005, ISBN 3-540-21146-2, pp. 73–77
• Mayer Goldberg, (2005) On the Recursive Enumerability of Fixed-Point Combinators, BRICS Report RS-05-1, University of Aarhus
• Matthias Felleisen, A Lecture on the Why of Y.

बाहरी संबंध

• Recursion Theory and Joy, Manfred von Thun, (2002 or earlier)
• The Lambda Calculus - notes by Don Blaheta, October 12, 2000
• Y Combinator
• "A Use of the Y Combinator in Ruby"
• "Functional programming in Ada"
• Rosetta code - Y combinator