दो परत "वाई शैली" संयोजक। क्या यह आम है? क्या इसका आधिकारिक नाम है?

Question

मैं देख रहा हूं कि कैसे भाषाएं उपयोग-पूर्व-डीफ़ को रोकती हैं और इसमें परिवर्तनीय कोशिकाएं नहीं होती हैं (set! या setq) फिर भी रिकर्सन प्रदान कर सकती हैं। मैं निश्चित रूप से भर में भाग गया Y Combinator और दोस्तों, जैसे (प्रसिद्ध कुख्यात?):

• http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html
• http://okmij.org/ftp/Computation/fixed-point-combinators.html
• http://www.angelfire.com/tx4/cus/combinator/birds.html
• http://en.wikipedia.org/wiki/Fixed-point_combinator

जब मैं लागू करने के लिए "चला गया Letrec "इस शैली में अर्थशास्त्र (यानी, एक स्थानीय चर को परिभाषित करने की अनुमति देता है जैसे कि यह एक पुनरावर्ती कार्य हो सकता है, जहां कवर के तहत यह कभी संदर्भ नहीं देता है अपने नाम करने के लिए), Combinator मैं लेखन समाप्त हो गया इस तरह दिखता है:

Y_letrec = λf . (λx.x x) (λs . (λa . (f ((λx.x x) s)) a)) 

या, यू Combinator बाहर बाँटे:

U = λx.x x 
Y_letrec = λf . U (λs . (λa . (f (U s)) a)) 

इस पढ़ें के रूप में: Y_letrec एक समारोह जो करने के लिए एक लेता है -बे-रिकर्स फ़ंक्शन f। f एक एकल-तर्क फ़ंक्शन होना चाहिए जो s स्वीकार करता है, जहां s फ़ंक्शन है f स्वयं-रिकर्सन प्राप्त करने के लिए कॉल कर सकता है। f को को "आंतरिक" फ़ंक्शन परिभाषित करने और वापस करने की उम्मीद है जो "असली" ऑपरेशन करता है। वह आंतरिक कार्य तर्क a (या सामान्य मामले में एक तर्क सूची स्वीकार करता है, लेकिन पारंपरिक नोटेशन में व्यक्त नहीं किया जा सकता है)। Y_letrec को कॉल करने का नतीजा f पर कॉल करने का परिणाम है, और इसे "आंतरिक" फ़ंक्शन माना जाता है, जिसे कॉल करने के लिए तैयार किया जाता है।

कारण मैं चीजों को सेट अप इस तरह से है कि मैं, सीधे होने वाली recursed समारोह की पार्स पेड़ फार्म का उपयोग कर सकता है संशोधन के बिना, केवल परिवर्तन के दौरान इसके चारों ओर एक अतिरिक्त समारोह परत लपेटकर जब letrec से निपटने इसलिए है । जैसे, अगर मूल कोड है:

(letrec ((foo (lambda (a) (foo (cdr a)))))) 

तो तब्दील प्रपत्र की तर्ज पर होगा:

(define foo (Y_letrec (lambda (foo) (lambda (a) (foo (cdr a)))))) 

ध्यान दें कि आंतरिक समारोह शरीर दोनों के बीच समान है।

मेरे प्रश्न हैं:

• मेरी Y_letrec समारोह आमतौर पर इस्तेमाल किया है?
• क्या इसका एक अच्छी तरह से स्थापित नाम है?

नोट: उपरोक्त पहला लिंक "आवेदक-आदेश वाई संयोजक" के रूप में एक समान कार्य ("चरण 5" में) को संदर्भित करता है, हालांकि मुझे उस नामकरण के लिए एक आधिकारिक स्रोत खोजने में परेशानी हो रही है।

अद्यतन 28-अप्रैल 2013:

मैंने महसूस किया कि Y_letrec ऊपर परिभाषित बहुत के करीब लेकिन के रूप में विकिपीडिया में परिभाषित जेड Combinator के समान नहीं है। प्रति विकिपीडिया के अनुसार, जेड संयोजक और "कॉल-बाय-वैल्यू वाई संयोजक" एक ही चीज हैं, और ऐसा लगता है कि वास्तव में यह चीज है जिसे "आवेदक-आदेश वाई संयोजक" कहा जा सकता है।

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

Y_letrec = λf . (λx.x x) (λs . (λa . (f ((λx.x x) s)) a)) 

भीतरी यू लागू करें::

Y_letrec = λf . (λx.x x) (λs . (λa . (f (s s)) a)) 

लागू बाहरी यू:

के साथ शुरू:

Y_letrec = λf . (λs . (λa . (f (s s)) a)) (λs . (λa . (f (s s)) a)) 

नाम बदलें विकिपीडिया की परिभाषा से मेल करने के यहाँ कैसे मैं तुलना किया है जेड संयोजक का:

Y_letrec = λf . (λx . (λv . (f (x x)) v)) (λx . (λv . (f (x x)) v)) 

विकिपीडिया के जेड Combinator को यह तुलना करें: जहां समारोह f लागू किया जा रहा है

Z  = λf . (λx . f (λv . ((x x) v))) (λx . f (λv . ((x x) v))) 

मुख्य अंतर है। फर्क पड़ता है क्या? क्या ये अंतर इस अंतर के बावजूद बराबर हैं?

Answer 1

हां, यह एक आवेदक-आदेश वाई संयोजक है। यू के अंदर यू का उपयोग करना बिल्कुल ठीक है, मैंने यह भी किया (सीएफ fixed point combinator in lisp)। चाहे यू को छोटा करने के लिए कोड का नाम हो या नहीं, मुझे ऐसा नहीं लगता है। यह सिर्फ लैम्ब्डा-टर्म का एक आवेदन है, और हां, यह इसे स्पष्ट आईएमओ भी बनाता है।

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

यू के साथ के माध्यम से आवेदन किया है और के माध्यम से और ईटा-कमी अपने कोड पर प्रदर्शन ((λa.(f (s s)) a) ==>f (s s)), यह परिचित सामान्य आदेश Y Combinator हो जाता है - यानी ऐसी है कि सामान्य आदेश मूल्यांकन, जहां तर्क 'मूल्यों के तहत काम करता कार्यात्मक आवेदन से पहले की मांग की नहीं कर रहे हैं, अंत में हो सकता है उन्हें जरूरत नहीं है (या उनमें से कुछ) सब के बाद:

Y = λf . (λs.f (s s)) (λs.f (s s)) 

BTW देरी से थोड़ा अलग तरीके से लागू किया जा सकता,

Y_ = λf . (λx.x x) (λs.f (λa.(s s) a)) 

जो आवेदक-आदेश मूल्यांकन नियमों के तहत भी काम करता है।

क्या अंतर है? चलो कमी अनुक्रमों की तुलना करें। आपका संस्करण,

Y_ = λf . (λx . (λv . (f (x x)) v)) (λx . (λv . (f (x x)) v)) 

((Y_ f) a) = 
    = ((λx . (λv . (f (x x)) v)) (λx . (λv . (f (x x)) v))) a 
    = (λv . (f (x x)) v) a { x := (λx . (λv . (f (x x)) v)) } 
    = (f (x x)) a 
    = | ; here (f (x x)) application must be evaluated, so 
    | ; the value of (x x) is first determined 
    | (x x) 
    | = ((λx . (λv . (f (x x)) v)) (λx . (λv . (f (x x)) v))) 
    | = (λv . (f (x x)) v)  { x := (λx . (λv . (f (x x)) v)) } 

और यहां f दर्ज किया गया है। तो यहां भी, अच्छी तरह से व्यवहार किया गया कार्य f अपना पहला तर्क प्राप्त करता है और ऐसा माना जाता है कि इसके साथ कुछ भी नहीं करना है। तो शायद दोनों ठीक बाद के बराबर हैं।

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

टीएल; डीआर: हालांकि भाषा परिभाषित की जा रही है, असाइनमेंट और पॉइंटर समानता के रूप में ऐसी मजेदार सामग्री से रहित हो सकती है, जिस भाषा में हम इसे परिभाषित करते हैं, उनमें निश्चित रूप से उन लोगों की आवश्यकता होती है, क्योंकि हमें उन्हें दक्षता की आवश्यकता होती है। कम से कम, कार्यान्वयन उनके पास हुड के नीचे होगा।

यह भी देखें: fixed point combinator in lisp, esp। In Scheme, how do you use lambda to create a recursive function?।