haskell - कॉल/सीसी कार्यान्वयन?

आपने समीकरण के हास्केल पक्ष को सुना है; मैं आपको रैकेट / योजना देता हूं, और जो भी आपके लिए सबसे उपयोगी है, आप इसके साथ चल सकते हैं।

मेरा उत्तर बहुत कम होगा, क्योंकि मुझे लगता है कि एक सरल रैकेट मूल्यांकनकर्ता में कॉल / सीसी के कार्यान्वयन के लिए मैं आपको सबसे अच्छा स्रोत दे सकता हूं , श्रीराम कृष्णमूर्ति की पीएलआई से , विशेष रूप से 20 अनुभाग से। दुभाषिया - यह पृष्ठ 205 पर है - लेकिन कई बार पुन: स्वरूपण करने की कोशिश करने के बाद मैंने फैसला किया कि यह पेज पर अपनी उचित जगह में और अधिक समझ जाएगा।

फिर, मैं कॉल / सीसी के पीछे के विचार को समझाने की कोशिश नहीं कर रहा हूं, बस एक कार्यान्वयन के लिए आपको बताता हूं। आपको ओर कुछ पूछना है तो मुझे बताइए।

call/cc लागू करने के लिए तुच्छ है कठिन हिस्सा पर्यावरण को स्थापित करना है जहां यह लागू करना संभव है।

हमें पहले एक निरंतरता-पारित शैली (सीपीएस) निष्पादन पर्यावरण को परिभाषित करना होगा। इस माहौल में, आपके कार्य (या फ़ंक्शन जैसी चीज़ें) सीधे मूल्यों को वापस नहीं करते हैं; इसके बजाय, वे एक समारोह पारित कर देते हैं जो गणना में 'अगले चरण' का प्रतिनिधित्व करता है - 'निरंतरता' - और वे वहां अपना परिणाम पास करते हैं। हास्केल में, यह इस तरह दिखता है:

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

जैसा कि आप देख सकते हैं, एक Cont मॉनाड एक्शन वास्तव में एक ऐसा कार्य है जो निरंतरता (a -> r) लेता है, परिणाम को निरंतरता से गुजरता है, और r का अंतिम परिणाम वापस ले जाता है, जो इसे केवल अपने कॉलर के माध्यम से गुजरता है ( यानी, एक Cont मोनड एक्शन को जारी रखने के लिए कॉल करना चाहिए) runCont सिर्फ इसे नए प्रकार के आवरण से बाहर ले जाता है - आप इसे किसी विशेष निरंतरता के साथ एक क्रिया को लागू करने के रूप में भी सोच सकते हैं, जैसा कि कुछ runCont someAction someContinuation

फिर हम इसे एक मोनद में बदल सकते हैं:

instance Monad (Cont r) where
    return x = Cont $ \cc -> cc x
    (Cont f) (>>=) g = Cont $ \cc -> f (\r -> runCont (g r) cc)

जैसा कि आप देख सकते हैं, return सिर्फ एक निरंतर cc हो जाता है, और इसके मूल्य को निरंतरता से गुजरता है। (>>=) एक बिट पेचीदरी है, उसे फिर से जारी रखने के साथ f को लागू करना होगा, जो तब g आह्वान करता है, वापस कार्रवाई करता है, और फिर इस नई कार्रवाई के लिए बाहरी निरंतरता को पारित करता है

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

-- Invoke a raw continuation with a given argument, throwing away our normal 
-- continuation
gotoContinuation :: (a -> r) -> a -> Cont r x
gotoContinuation continuation argument = Cont $ \_ -> continuation argument

-- Duplicate the current continuation; wrap one up in an easy-to-use action, and
-- the other stays the normal continuation for f
callCC f = Cont $ \cc -> runCont (f (gotoContinuation cc)) cc

सरल, नहीं?

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

ऑफ-भाषा होने का जोखिम मुझे लगता है कि स्मॉलटाक जारी रखने के लिए सबसे आसान और लागू किया जा सकता है इसका कारण यह है कि स्मालटाक में निष्पादन स्टैक सामान्य वस्तुओं से बनता है जो कि किसी अन्य ऑब्जेक्ट की तरह पहुँचा जा सकता है और हेरफेर किया जा सकता है।

एक सरल निरंतरता ऑब्जेक्ट को लागू करने के लिए निम्नलिखित दो विधियां आवश्यक हैं पहली पद्धति में हम अभिभावक (प्रेषक) फ्रेम (संदर्भों) पर पुनरावृत्त करके और उनके राज्य (कार्यक्रम काउंटर, अस्थायी, तर्क) की प्रतिलिपि प्रारंभ करते हैं:

Continuation>>initializeFromContext: aContext
    context := aContext.
    stream := WriteStream on: (Array new: 200).
    [ context notNil ] whileTrue: [
        stream nextPut: context.
        1 to: context class instSize do: [ :index |
            stream nextPut: (context instVarAt: index) ].
        1 to: context size do: [ :index |
            stream nextPut: (context at: index) ].
        context := context sender ].
    values := stream contents

दूसरा तरीका निष्पादन को फिर से शुरू करना है: पहले हम वर्तमान स्टैक को खोलना (फिर से सिर्फ निष्पादन स्टैक पर एक सरल लूप है), फिर हम कब्जा किए गए स्टैक फ़्रेम को पुनर्स्थापित करते हैं, उन्हें वर्तमान स्टैक फ्रेम पर पुनः thisContext और निष्पादन को फिर से शुरू करें तर्क anObject :

Continuation>>value: anObject
    self terminate: thisContext.
    stream := values readStream.
    [ stream atEnd ] whileFalse: [
        context := stream next.
        1 to: context class instSize do: [ :index |
            context instVarAt: index put: stream next ].
        1 to: context size do: [ :index |
            context at: index put: stream next ] ]
    thisContext swapSender: values first.
    ^ anObject

इन दो विधियों के साथ हम आसानी से callCC बना सकते हैं:

Continuation class>>callCC: aBlock
    ^ aBlock value: (self new initializeFromContext: thisContext sender)

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

उपरोक्त कोड समुद्र तटीय वेब-फ़्रेमवर्क से है। कोड के साथ खेलने के लिए आप तैयार वितरण का उपयोग करना चाहते हैं और कक्षाएं WAContinuation और WAContinuationTest ब्राउज़ कर सकते हैं

" call/cc कार्यान्वित करना" वास्तव में उस परत पर नहीं समझ पा रहा है, जिस पर आप काम कर रहे हैं; अगर आप किसी भाषा में call/cc लागू कर सकते हैं, तो इसका मतलब है कि इसमें कम से कम शक्तिशाली call/cc रूप में एक अंतर्निर्मित निर्माण किया गया है। भाषा के स्तर पर, call/cc मूल रूप से एक आदिम नियंत्रण प्रवाह ऑपरेटर है, जैसे कि कुछ प्रकार की शाखाएं होनी चाहिए।

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

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

तकनीकी तौर पर, callCC की वह परिभाषा टाइप करती है अगर आप runCont और runCont के अनुप्रयोगों को हटा दें लेकिन यह आपको समझने में मदद नहीं करेगा कि यह Cont मॉडेड के संदर्भ में कैसे काम करता है, तो इसकी बजाय इसकी परिभाषा को देखते हैं। (यह परिभाषा मौजूदा मोनाद ट्रांसफार्मर लाइब्रेरी में इस्तेमाल नहीं की गई है, क्योंकि इसमें सभी मॉडेड अपने ट्रांसफार्मर संस्करण के शीर्ष पर बनाए गए हैं, लेकिन यह स्निपेट के Cont के प्रयोग से मेल खाता है (जो केवल पुराने संस्करण के साथ काम करता है), और बातें नाटकीय रूप से सरल करता है।)

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

ठीक है, तो Cont ra बस (a -> r) -> r , और runCont हमें इस Cont ra मान से इस फ़ंक्शन को प्राप्त करने देता है। काफी सरल। लेकिन इसका मतलब क्या है?

Cont ra एक अंतिम परिणाम r साथ एक निरंतरता-उत्तीर्ण गणना है, और परिणामस्वरूप a । अंतिम परिणाम का क्या अर्थ है? ठीक है, चलो runCont का प्रकार लिखें और स्पष्ट रूप से बाहर लिखें:

runCont :: Cont r a -> (a -> r) -> r

इसलिए, जैसा कि हम देख सकते हैं, "अंतिम परिणाम" वह मूल्य है जिसे हम runCont से बाहर runCont । अब, हम Cont साथ कम्प्यूटेशन कैसे बना सकते हैं? मोनड का उदाहरण ज्ञानवान है:

instance Monad (Cont r) where
  return a = Cont (\k -> k a)
  m >>= f = Cont (\k -> runCont m (\result -> runCont (f result) k))

ठीक है, ठीक है, यदि आप पहले से ही जानते हैं कि इसका क्या मतलब है, तो यह प्रबुद्ध है। महत्वपूर्ण बात यह है कि जब आप Cont (\k -> ...) लिखते हैं Cont (\k -> ...) , k बाकी की गणना है - यह उम्मीद करता है कि आप इसे एक मूल्य दें, और तब आपको गणना की अंतिम परिणाम देगा प्रकार r , याद रखना) वापस, जो आप फिर अपने स्वयं के रिटर्न मान के रूप में उपयोग कर सकते हैं क्योंकि आपका रिटर्न टाइप भी r है वाह! और जब हम रन Cont साथ एक Cont गणन runCont , तो हम बस अंतिम k निर्दिष्ट कर रहे हैं - अंतिम परिणाम का उत्पादन करने वाले कंप्यूटेशन के "शीर्ष स्तर"

यह "बाकी गणना" क्या है? एक निरंतरता, क्योंकि यह गणना की निरंतरता है!

(>>=) वास्तव में बहुत सरल है: हम बाईं ओर अभिकलन चलाते हैं, यह हमारे अपने -बाकी-गणना की जाती है यह बाकी की गणना सिर्फ मान में f को f , जो अपनी कम्प्यूटेशन का उत्पादन करती है। हम उस कम्प्यूटेशन को चलाते हैं, इसे बाकी की गणना में खिलाते हैं कि हमारी संयुक्त कार्रवाई की गई है। इस तरह, हम Cont में एक साथ कंप्यूटेशन धागा सकते हैं:

computeFirst >>= \a ->
computeSecond >>= \b ->
return (a + b)

या, अधिक परिचित नोटेशन में:

do a <- computeFirst
   b <- computeSecond
   return (a + b)

हम फिर रन runCont साथ इन कम्प्यूटेशंस को चला सकते हैं - ज्यादातर समय, runCont foo id तरह कुछ runCont foo id ठीक काम करेगी, उसी परिणाम के साथ foo को बदलकर अंतिम परिणाम का परिणाम इसके परिणाम में बदल देगा।

अब तक सब ठीक है. अब चीजों को भ्रमित करने दो।

wtf :: Cont String Int
wtf = Cont (\k -> "eek!")

aargh :: Cont String Int
aargh = do
  a <- return 1
  b <- wtf
  c <- return 2
  return (a + b + c)

यहाँ क्या चल रहा है?! wtf अंतिम परिणाम String और परिणाम Int साथ एक Cont गणना है, लेकिन कोई Int नहीं दृष्टि में है।

जब हम हर चलाते हैं तो क्या होता है, रन के साथ runCont aargh show - यानी, कम्प्यूटेशन चलाएं, और अंतिम परिणामों का निर्माण करने के लिए एक String रूप में इसका Int परिणाम show ?

हम "eek!" वापस।

याद रखें कि "गणना के बाकी" k कैसे है? क्या हमने wtf में किया है, यह चालाकी से नहीं कहता, और इसके बजाय हमारे अपने अंतिम परिणाम की आपूर्ति करता है - जो तब ठीक हो जाता है, ठीक है, अंतिम!

यह सिर्फ पहली चीज है जो जारी रख सकती है। कंटिव की तरह कुछ Cont (\k -> k 1 + k 2) बाकी की गणना को इस तरह से चलाता है जैसे कि वह 1 लौटा और फिर जैसे 2 लौटा, और दो अंतिम परिणाम एक साथ जोड़ता है! निरंतरता मूल रूप से मनमाने ढंग से जटिल गैर-स्थानीय नियंत्रण प्रवाह को अभिव्यक्त करने की अनुमति देती है , जिससे उन्हें भ्रामक रूप में शक्तिशाली बना दिया जाता है। दरअसल, निरंतरता इतनी सामान्य है कि, एक अर्थ में, प्रत्येक मोनद एक विशेष मामले का है । दरअसल, आप (>>=) बारे में सोच सकते हैं सामान्य रूप से निरंतरता-गुजर शैली का उपयोग कर:

(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

दूसरा तर्क एक निरंतरता है जो पहली गणना का परिणाम लेता है और बाकी की गणना को चलाना है।

लेकिन मैंने अभी भी इस प्रश्न का उत्तर नहीं दिया है कि उस callCC साथ क्या हो रहा है? खैर, यह फ़ंक्शन आपको वर्तमान निरंतरता के साथ देते हैं। लेकिन एक दूसरे पर लटका, यह नहीं है कि क्या हम Cont पहले ही कर रहे थे? हाँ, लेकिन प्रकारों की तुलना करें:

Cont   :: ((a -> r)        -> r)        -> Cont r a
callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a

हुह। आप देखते हैं, Cont साथ समस्या यह है कि हम उस फ़ंक्शन के अंदर से क्रियाओं को अनुक्रमित नहीं कर सकते जो हम पास करते हैं - हम सिर्फ एक r परिणाम शुद्ध तरीके से बनाते हैं। callCC निरंतरता तक पहुंचा देता है, चारों ओर पारित किया जाता है, और आम तौर पर अंदर Cont कंप्यूटेशंस के साथ घूमता रहता है। जब हम रखते है

do a <- callCC (\cc -> ...)
   foo ...

आप कल्पना कर सकते हैं कि cc एक फ़ंक्शन होने पर हम फ़ंक्शन के अंदर किसी भी मूल्य के साथ कॉल कर सकते हैं ताकि callCC (\cc -> ...) के callCC (\cc -> ...) मूल्य का callCC (\cc -> ...) किया जा सके । या, ज़ाहिर है, हम केवल सामान्य रूप से एक मूल्य वापस कर सकते हैं, लेकिन फिर callCC को पहली जगह पर callCC थोड़ा व्यर्थ होगा :)

रहस्यमय b लिए, यह सिर्फ इसलिए है क्योंकि आप किसी भी प्रकार की गणना के लिए cc foo का उपयोग कर सकते हैं, क्योंकि यह सामान्य नियंत्रण प्रवाह से बच जाता है और जैसे मैंने कहा, तुरंत इसका उपयोग पूरी callCC (\cc -> ...) के परिणाम के रूप में करता है callCC (\cc -> ...) । इसलिए जब से यह वास्तव में किसी मूल्य का उत्पादन नहीं कर पाता है, तब वह किसी भी प्रकार के वैल्यू को लौटा सकता है जिससे वह चाहता है। ख़ुशामदी!

जो हमें वास्तविक क्रियान्वयन के लिए लाता है:

callCC f = Cont (\k -> runCont (f (\a -> Cont (\_ -> k a))) k)

सबसे पहले, हमें संपूर्ण शेष गणना मिलती है, और इसे k कहते हैं। लेकिन इसके बारे में f (\a -> Cont (\_ -> ka)) क्या है? खैर, हम जानते हैं कि f एक प्रकार का मान लेता है (a -> Cont rb) , और वह यही है जो लैम्ब्डा है - एक फ़ंक्शन जो callCC f के परिणाम के रूप में उपयोग करने के लिए मान लेता है, और एक callCC f गणना करता है जो इसकी उपेक्षा करता है निरंतरता और बस के माध्यम से कि मूल्य - "गणना के बाकी" callCC f के नजरिए से। ठीक है, इसलिए उस फोन कॉल का नतीजा एक और Cont गणना है, जिसे हमें चलने के लिए निरंतरता देने की आवश्यकता होगी। हम केवल उसी निरंतरता से गुजरते हैं, अगर सब कुछ सामान्य रूप से चला जाता है, तो हम चाहते हैं कि गणना जो भी हो, हमारे रिटर्न वैल्यू हो और आम तौर पर जारी रहे। (वास्तव में, किसी अन्य मूल्य से गुजरना मतलब नहीं होता - यह " वर्तमान निरंतरता के साथ कॉल करता है", "आप वास्तव में मेरे साथ चल रहे एक के अलावा किसी निरंतरता के साथ कॉल करें"।)

सब कुछ, मुझे आशा है कि आप इसे प्रबुद्ध के रूप में पाया क्योंकि यह बहुत लंबा है निरंतरता बहुत शक्तिशाली हैं, लेकिन यह कैसे काम करता है इसके लिए एक अंतर्ज्ञान प्राप्त करने में बहुत समय लग सकता है। मैं Cont साथ खेलने का सुझाव देता हूं (जो आपको मौजूदा एमटीएल के साथ काम करने के लिए cont पर कॉल करना होगा) और काम कर रहे हैं कि आप नियंत्रण प्रवाह के लिए महसूस करने के लिए आपके परिणाम कैसे प्राप्त करते हैं

जारी रखने पर आगे की सिफारिश की गई:

• सभी मोनाद की मां (पहले जुड़े हुए)
• हास्कल विकीबूक की निरंतरता शैली अध्याय
• नियंत्रण के त्वरित और गंदा पुनर्मूल्यांकन (निरंतरता के "वास्तविक-विश्व" उपयोग को दर्शाता है)
• Oleg Kiselyov की साइट की निरंतरता और सीमांकित नियंत्रण अनुभाग