रिकर्सन लागू करने के लिए कॉल/सीसी का उपयोग करना संभव है?

Question

मुझे आश्चर्य है कि फ़ंक्शन को अपने शरीर में कॉल किए बिना एक पुनरावर्ती फ़ंक्शन को परिभाषित करना संभव है लेकिन किसी भी तरह से कॉल/सीसी का उपयोग कर? धन्यवाद।

Answer 1

आप call/cc, as described here का उपयोग कर एक वाई संयोजक को कार्यान्वित कर सकते हैं। - एक स्पष्ट स्वयं आवेदन के बिना Y Combinator

उपप्रमेय call/cc के माध्यम से 1. Y Combinator: (इस स्वच्छ पद उल्लेख के लिए जॉन कोवान बहुत धन्यवाद) उस पोस्ट का हवाला देते हुए, यहाँ ओलेग के कार्यान्वयन है।

(define (Y f) 
    ((lambda (u) (u (lambda (x) (lambda (n) ((f (u x)) n))))) 
    (call/cc (call/cc (lambda (x) x))))) 

यहाँ, हम एक तथ्य यह है कि

((lambda (u) (u p)) (call/cc call/cc)) 

और

((lambda (u) (u p)) (lambda (x) (x x))) 

observationally बराबर हैं प्रयोग किया जाता है।

Answer 2

आपका प्रश्न थोड़ा अस्पष्ट है। विशेष रूप से, ऐसा लगता है कि आप एक प्रणाली चाहते हैं जो कॉल/सीसी का उपयोग कर सीधे रिकर्सिव कॉल किए बिना मॉडल रिकर्सिव कॉल करता है। हालांकि, यह पता चला है कि आप कॉलर्स/सीसी के बिना रिकर्सिव कॉल और बिना रिकर्सिव कॉल मॉडल कर सकते हैं। उदाहरण के लिए:

#lang racket 

(define (factorial f n) 
    (if (= n 0) 1 (* n (f f (- n 1))))) 

(factorial factorial 3) 

यह धोखाधड़ी की तरह लग सकता है, लेकिन यह वाई संयोजक की नींव है। शायद आप उन प्रतिबंधों के सेट को कस कर सकते हैं जिनके बारे में आप सोच रहे हैं?

पीएस .: अगर यह होमवर्क है, तो कृपया मुझे उद्धृत करें!

Answer 3

मुझे डर है call/cc वास्तव में इसके साथ बहुत कुछ नहीं करना है। रिकर्सिव फ़ंक्शन को परिभाषित करने के केवल दो तरीके हैं:

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

तो factorial के लिए, आप इसे इस प्रकार लिख:

(define (factorial-step recurse n) 
    (if (zero? n) 
     1 
     (* n (recurse (- n 1))))) 

Y Combinator का जादू है कि यह निर्माण करती recurse समारोह है कि factorial-step को खिलाया जा होता है।