कैसे निरंतरता इकाई

Question

उपयोग करने के लिए सीपीएस शैली gcd गणना कन्वर्ट करने के लिए

हमें निरंतरता इकाई के निम्नलिखित कार्यान्वयन, सीपीएस शैली संगणना उपज और पूर्णांक के लिए पर विचार करें:

module Cont : sig 
    type 'a t = ('a -> int) -> int 
    val return : 'a -> 'a t 
    val bind : 'a t -> ('a -> 'b t) -> 'b t 
    val callCC: (('a -> 'b t) -> 'a t) -> 'a t 
end = struct 
    type 'a t = ('a -> int) -> int 

    let return x = 
    fun cont -> cont x 

    let bind m f = 
    fun cont -> m (fun x -> (f x) cont) 

    let callCC k = 
    fun cont -> k (fun x -> (fun _ -> cont x)) cont 
end 

हम CPS- कैसे पुनर्लेखन कर सकते हैं जीसीडी गणना के शैली कार्यान्वयन (How to memoize recursive functions? देखें) और विशेष रूप से Cont monad का लाभ लेने के लिए ज्ञापन?

# let gcd memo ((a,b):int * int) = 
    Cont.callCC (memo gcd_cont (a,b)) (fun x -> x) 
;; 
    val gcd : 
    (((int * int -> int Cont.t) -> int * int -> int Cont.t) -> 
    int * int -> (int -> 'a Cont.t) -> int Cont.t) -> 
    int * int -> int = <fun> 

हालांकि मैं एक में इस संकेत बारी नहीं कर सका:

let gcd_cont k (a,b) = 
    let (q, r) = (a/b, a mod b) in 
    if r = 0 then Cont.return b else k (b,r) 

परिभाषित करने के बाद मैं प्रकार solver उपयोग करने के लिए मुझे प्रकार है कि Memoization समारोह होना चाहिए के बारे में संकेत देने के लिए करने की कोशिश की वास्तविक कार्यान्वयन क्या कोई ऐसा करने में सक्षम है? ज्ञापन समारोह में "कॉलसीसी" का उपयोग करने के पीछे तर्क यह है कि यदि कैश में कोई मान मिलता है, तो यह प्रारंभिक निकास की स्थिति है।

Answer 1

मुझे लगता है कि समस्या यह है कि How to memoize recursive functions? के जवाब में, माइकल ने सीपीएस शैली को सीपीएस शैली कहा जो सीपीएस शैली नहीं है। सीपीएस शैली में, जब भी कोई मूल्य वापस करना चाहता है तो अतिरिक्त निरंतरता तर्क k का उपयोग किया जाता है - इसके बाद मान k पर लागू होता है।

यह वास्तव में नहीं है क्या हम यहाँ चाहते हैं, और नहीं क्या लागू करता है:

let gcd_cont k (a,b) = 
    let (q, r) = (a/b, a mod b) in 
    if r = 0 then b else k (b,r) 

यहाँ, k लौटने के लिए नहीं किया जाता है (b सीधे लौटा दिया जाता है), यह बजाय एक पुनरावर्ती कॉल प्रदर्शन किया जाता है। यह रिकर्सन को अनदेखा करता है: gcd_cont के भीतर, kgcd_cont के रूप में सोच सकता है, जैसे कि let rec का उपयोग किया गया था। बाद में, gcd_cont वास्तव में एक पुनरावर्ती क्रिया एक fixpoint Combinator का उपयोग कर में बदल सकता है, कि मूल रूप से "यह अपने आप को खिलाती":

let rec fix f x = f (fix f) x 
let gcd = fix gcd_cont 

(इस call समारोह है कि माइकल को परिभाषित करता है के बराबर है) gcd को परिभाषित करने में अंतर let rec का उपयोग करके सीधे यह है कि अनचाहे रिकर्सन वाला संस्करण रिकर्सिव कॉल को "उपकरण" करने की अनुमति देता है, क्योंकि रिकर्सन फ़िक्सपॉइंट संयोजक द्वारा स्वयं किया जाता है। यही वह है जिसे हम याद रखने के लिए चाहते हैं: यदि परिणाम कैश में नहीं है तो हम केवल रिकर्सन करना चाहते हैं। इस प्रकार memo संयोजक की परिभाषा।

यदि फ़ंक्शन को let rec के साथ परिभाषित किया गया है, तो फ़ंक्शन को परिभाषित करने के साथ ही रिकर्सन बंद हो जाता है, इसलिए कोई भी रिकॉर्सेव कॉल-साइट्स को ज्ञापन सम्मिलित करने के लिए उपकरण नहीं दे सकता है।

एक साइड नोट के रूप में, दो उत्तरों मूल रूप से एक ही चीज़ को लागू करते हैं: फिक्सपॉइंट संयोजक में पुनरावृत्ति को लागू करने का एकमात्र अंतर है: माइकल का फिक्सपॉइंट संयोजक let rec का उपयोग करता है, जैक्सन का एक संदर्भ का उपयोग करता है, यानी "लैंडिन का गाँठ" - यदि आपके पास अपनी भाषा में संदर्भ हैं, तो पुनरावृत्ति को लागू करने का एक वैकल्पिक तरीका।

Sooo, निष्कर्ष निकालने के लिए, मैं यह कहता हूं कि निरंतरता में मोनड वास्तव में संभव नहीं है/वास्तव में समझ में नहीं आता है, क्योंकि यह चीज़ पहली जगह सीपीएस नहीं थी।