जीएचसी इतनी उलझन में क्यों ठीक करता है?

Question

GHC स्रोत कोड को देखते हुए मैं देख सकता हूँ कि ठीक के लिए परिभाषा है:

fix :: (a -> a) -> a 
fix f = let x = f x in x 

एक उदाहरण ठीक इस तरह प्रयोग किया जाता है:

fix (\f x -> let x' = x+1 in x:f x') 

यह मूलतः एक दृश्य पैदावार संख्याओं की संख्या जो एक से अनंत तक बढ़ती हैं। ऐसा होने के लिए फिक्स फ़ंक्शन को घुमाने वाला होना चाहिए जो इसे पहले चरण के रूप में उस फ़ंक्शन पर वापस प्राप्त करता है। यह मुझे स्पष्ट नहीं है कि ऊपर सूचीबद्ध की परिभाषा को ठीक कर सकती है।

1. कैसे एक्स कभी आ मतलब करने के लिए करता है ठीक एक्स:

   fix :: (a -> a) -> a 
   fix f = f (fix f) 
   

   तो अब मैं दो प्रश्न हैं:

   इस परिभाषा कैसे मैं समझता हूँ कि कैसे ठीक काम करता आया है पहली परिभाषा में?

2. क्या दूसरे पर पहली परिभाषा का उपयोग करने का कोई फायदा है?

Answer 1

यह देखना आसान है कि यह परिभाषा समीकरण तर्क लागू करके कैसे काम करती है।

fix :: (a -> a) -> a 
fix f = let x = f x in x 

क्या x जब हम fix f मूल्यांकन करने के लिए प्रयास करने के लिए मूल्यांकन करेंगे? इसे f x के रूप में परिभाषित किया गया है, इसलिए fix f = f x। लेकिन x क्या है? यह f x है, जैसा कि पहले था। तो आपको fix f = f x = f (f x) मिलते हैं। इस तरह से आपको f: fix f = f (f (f (f ...))) के अनुप्रयोगों की एक अनंत श्रृंखला मिलती है।

अब, f के लिए (\f x -> let x' = x+1 in x:f x') प्रतिस्थापन आपको मिल

fix (\f x -> let x' = x+1 in x:f x') 
    = (\f x -> let x' = x+1 in x:f x') (f ...) 
    = (\x -> let x' = x+1 in x:((f ...) x')) 
    = (\x -> x:((f ...) x + 1)) 
    = (\x -> x:((\x -> let x' = x+1 in x:(f ...) x') x + 1)) 
    = (\x -> x:((\x -> x:(f ...) x + 1) x + 1)) 
    = (\x -> x:(x + 1):((f ...) x + 1)) 
    = ... 

संपादित: अपने दूसरे प्रश्न के बारे में, @ is7s टिप्पणी में कहा कि पहली परिभाषा बेहतर है क्योंकि यह अधिक प्रभावी है।

पता लगाने के लिए क्यों, के fix1 (:1) !! 10^8 के लिए कोर को देखो:

a_r1Ko :: Type.Integer  
a_r1Ko = __integer 1 

main_x :: [Type.Integer] 
main_x = 
    : @ Type.Integer a_r1Ko main_x 

main3 :: Type.Integer 
main3 = 
    !!_sub @ Type.Integer main_x 100000000 

आप देख सकते हैं, परिवर्तनों के बाद fix1 (1:) अनिवार्य रूप से main_x = 1 : main_x बन गया। ध्यान दें कि यह परिभाषा खुद को कैसे संदर्भित करती है - यही वह है "गाँठ बांधना" का अर्थ है।

अब fix2 (1:) !! 100000000 को देखो:

main6 :: Type.Integer 
main6 = __integer 1 

main5 
    :: [Type.Integer] -> [Type.Integer] 
main5 = : @ Type.Integer main6 

main4 :: [Type.Integer] 
main4 = fix2 @ [Type.Integer] main5 

main3 :: Type.Integer 
main3 = 
    !!_sub @ Type.Integer main4 100000000 

यहाँ fix2 आवेदन वास्तव में संरक्षित है: यह आत्म संदर्भ रनटाइम पर एक सरल सूचक अविवेक के रूप में प्रस्तुत किया जाता है

परिणाम यह है कि दूसरा कार्यक्रम राम सूची के प्रत्येक तत्व के लिए आवंटन करने की जरूरत है (लेकिन जब से सूची तुरंत सेवन किया जाता है, इस कार्यक्रम अभी भी प्रभावी ढंग से निरंतर अंतरिक्ष में चलता है):

$ ./Test2 +RTS -s 
    2,400,047,200 bytes allocated in the heap 
     133,012 bytes copied during GC 
      27,040 bytes maximum residency (1 sample(s)) 
      17,688 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 
[...] 

कि तुलना पहला कार्यक्रम के व्यवहार के लिए:

$ ./Test1 +RTS -s   
      47,168 bytes allocated in the heap 
      1,756 bytes copied during GC 
      42,632 bytes maximum residency (1 sample(s)) 
      18,808 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 
[...] 

Answer 2

एक्स पहली परिभाषा में x को ठीक करने का अर्थ कैसे आता है?

fix f = let x = f x in x 

चलो हास्केल में बाइंडिंग हैं पुनरावर्ती

सबसे पहले, पता है कि हास्केल पुनरावर्ती लेट बाइंडिंग अनुमति देता है। हास्केल ने "चलो" क्या कहा, कुछ अन्य भाषाएं "लेट्रेक" कहती हैं। यह फ़ंक्शन परिभाषाओं के लिए बहुत सामान्य लगता है। उदाहरण के लिए:

ghci> let fac n = if n == 0 then 1 else n * fac (n - 1) in fac 5 
120 

लेकिन यह मूल्य परिभाषाओं के लिए बहुत अजीब लग सकता है। फिर भी, हास्केल की गैर-कठोरता के कारण मूल्यों को पुन: परिभाषित किया जा सकता है।

ghci> take 5 (let ones = 1 : ones in ones) 
[1,1,1,1,1] 

हास्केल के आलस्य के बारे में अधिक विस्तार के लिए A gentle introduction to Haskell वर्गों 3.3 और 3.4 देखें। एक वादा गणना प्रदर्शन करने के लिए:

Thunks GHC

GHC में, एक रूप में अभी तक unevaluated अभिव्यक्ति एक "thunk" में लपेटा जाता है। Thunks का मूल्यांकन केवल तभी किया जाता है जब वे बिल्कुल होना चाहिए। मान लीजिए कि हम fix someFunction चाहते हैं। fix की परिभाषा के अनुसार, कि

let x = someFunction x in x 

अब, क्या GHC देखता है कुछ इस तरह है।

let x = MAKE A THUNK in x 

तो यह खुशी से आप के लिए एक thunk बना देता है और जब तक आप को पता है कि x वास्तव में है की मांग सही साथ ले जाता है।

नमूना मूल्यांकन

thunk की अभिव्यक्ति सिर्फ खुद को संदर्भित करने के लिए होता है। आइए ones उदाहरण लें और fix का उपयोग करने के लिए इसे फिर से लिखें।

ghci> take 5 (let ones recur = 1 : recur in fix ones) 
[1,1,1,1,1] 

तो यह थंक कैसा दिखता है?
हम एक स्पष्ट प्रदर्शन के लिए अज्ञात फ़ंक्शन \recur -> 1 : recur के रूप में ones इनलाइन कर सकते हैं।

take 5 (fix (\recur -> 1 : recur)) 

-- expand definition of fix 
take 5 (let x = (\recur -> 1 : recur) x in x) 

अब तो, क्या x है? ठीक है, भले ही हम काफी यकीन है कि क्या x है नहीं कर रहे हैं, हम अभी भी के माध्यम से समारोह आवेदन के साथ जा सकते हैं:

take 5 (let x = 1 : x in x) 

अरे देखो, हम परिभाषा हम पहले था पर वापस आ गए हैं।

take 5 (let ones = 1 : ones in ones) 

तो अगर आपको लगता है कि आप समझते हैं कि कि एक काम करता है, तो आप कैसे fix काम करता है की एक अच्छी लग रहा है।

---

कोई लाभ दूसरा पहले ओवर परिभाषा का उपयोग करने के लिए है?

हां। समस्या यह है कि दूसरा संस्करण अनुकूलन के साथ भी स्पेस लीक का कारण बन सकता है। forever की परिभाषा के साथ एक ही समस्या के लिए GHC trac ticket #5205 देखें। यही कारण है कि मैंने थंक्स का उल्लेख किया: क्योंकि let x = f x in x केवल एक थंक आवंटित करता है: x थंक।

Answer 3

अंतर बनाम प्रतिलिपि साझा करने में अंतर है।

fix1 f = x where x = f x -- more visually apparent way to write the same thing 

fix2 f = f (fix2 f) 

हम खुद में परिभाषा स्थानापन्न हैं, दोनों एक ही अनंत आवेदन श्रृंखला f (f (f (f (f ...)))) के रूप में कम कर रहे हैं। लेकिन पहली परिभाषा स्पष्ट नामकरण का उपयोग करती है; हास्केल में (जैसा कि अधिकांश अन्य भाषाओं में) साझा करना चीजों को नाम देने की क्षमता द्वारा सक्षम किया जाता है: एक नाम "इकाई" (यहां, x) को संदर्भित करने के लिए कम या कम गारंटी है। दूसरी परिभाषा किसी भी साझाकरण की गारंटी नहीं देती है - कॉल fix2 f का परिणाम अभिव्यक्ति में प्रतिस्थापित किया गया है, इसलिए इसे मूल्य के रूप में भी प्रतिस्थापित किया जा सकता है।

लेकिन एक दिए गए कंपाइलर सिद्धांत में इसके बारे में स्मार्ट हो सकते हैं और दूसरे मामले में भी साझाकरण का उपयोग कर सकते हैं।

संबंधित समस्या "वाई संयोजक" है। untyped लैम्ब्डा पथरी में जहां कोई निर्माणों (और इस प्रकार कोई स्वयं -reference), वाई Combinator परिभाषा के लिए व्यवस्था करने से आत्म संदर्भ emulates नामकरण कॉपी करने के लिए, तो प्रति स्वयं की हो जाता है की चर्चा करते हुए मुमकिन। लेकिन कार्यान्वयन में जो भाषा में नामित इकाइयों की अनुमति देने के लिए पर्यावरण मॉडल का उपयोग करते हैं, नाम से प्रत्यक्ष संदर्भ संभव हो जाता है।

दो परिभाषा के बीच एक और अधिक कठोर अंतर देखने के लिए, की तुलना

fibs1 = fix1 ((0:) . (1:) . g) where g (a:t@(b:_)) = (a+b):g t 
fibs2 = fix2 ((0:) . (1:) . g) where g (a:t@(b:_)) = (a+b):g t 

यह भी देखें:

• In Scheme, how do you use lambda to create a recursive function?
• Y combinator discussion in "The Little Schemer"
• Can fold be used to create infinite lists?

(विशेष रूप से उपरोक्त अंतिम लिंक में अंतिम दो परिभाषाओं को काम करने का प्रयास करें)।

---

परिभाषाओं से काम करते हुए, अपने उदाहरण fix (\g x -> let x2 = x+1 in x : g x2) के लिए हम

fix1 (\g x -> let x2 = x+1 in x : g x2) 
= fix1 (\g x -> x : g (x+1)) 
= fix1 f where {f = \g x -> x : g (x+1)} 
= fix1 f where {f g x = x : g (x+1)} 
= x  where {x = f x ; f g x = x : g (x+1)} 
= g  where {g = f g ; f g x = x : g (x+1)} -- both g in {g = f g} are the same g 
= g  where {g = \x -> x : g (x+1)}   -- and so, here as well 
= g  where {g x = x : g (x+1)} 

मिलता है और इस तरह g के लिए एक उचित पुनरावर्ती परिभाषा वास्तव में बनाया जाता है। (उपर्युक्त में, हम ....x.... where {x = ...}let {x = ...} in ....x.... के लिए, योग्यता के लिए लिखते हैं)।

लेकिन दूसरे व्युत्पत्ति, वापस एक नाम एक मूल्य प्रतिस्थापन, नहीं का एक महत्वपूर्ण अंतर के साथ आगे बढ़ता है के रूप में

fix2 (\g x -> x : g (x+1)) 
= fix2 f    where {f g x = x : g (x+1)} 
= f (fix2 f)   where {f g x = x : g (x+1)} 
= (\x-> x : g (x+1)) where {g = fix2 f ; f g x = x : g (x+1)} 
= h     where {h x = x : g (x+1) ; g = fix2 f ; f g x = x : g (x+1)} 

ताकि वास्तविक कॉल जैसे के रूप में आगे बढ़ेंगे

take 3 $ fix2 (\g x -> x : g (x+1)) 10 
= take 3 (h 10)  where {h x = x : g (x+1) ; g = fix2 f ; f g x = x : g (x+1)} 
= take 3 (x:g (x+1)) where {x = 10 ;    g = fix2 f ; f g x = x : g (x+1)} 
= x:take 2 (g x2) where {x2 = x+1 ; x = 10 ; g = fix2 f ; f g x = x : g (x+1)} 
= x:take 2 (g x2) where {x2 = x+1 ; x = 10 ; g = f (fix2 f) ; f g x = x : g (x+1)} 
= x:take 2 (x2 : g2 (x2+1)) where {    g2 = fix2 f ; 
          x2 = x+1 ; x = 10 ;     f g x = x : g (x+1)} 
= ...... 

और हम है कि एक नई बजाय पिछले एक की (g2 के लिए) बाध्यकारी यहाँ स्थापित है, (g के लिए) fix1 परिभाषा के साथ के रूप में reused किया जा रहा है देखते हैं।

Answer 4

मेरे पास शायद थोड़ा सा सरलीकृत स्पष्टीकरण है जो inlining अनुकूलन से आता है। अगर हम

fix :: (a -> a) -> a 
fix f = f (fix f) 

है तो fix एक पुनरावर्ती समारोह है और इसका मतलब है कि यह स्थानों पर जहां यह प्रयोग किया जाता है में inlined नहीं किया जा सकता है (एक INLINE pragma, नजरअंदाज कर दिया जाएगा, तो दिए गए)।

हालांकि

fix' f = let x = f x in x 

नहीं एक पुनरावर्ती समारोह है - यह अपने आप कॉल कभी नहीं। केवल x अंदर रिकर्सिव है।तो जब

fix' (\r x -> let x' = x+1 in x:r x') 

बुला संकलक

(\f -> (let y = f y in y)) (\r x -> let x' = x+1 in x:r x') 

में इनलाइन कर सकते हैं और फिर इसे सरल बनाने के लिए जारी, उदाहरण के लिए

let y = (\r x -> let x' = x+1 in x:r x') y in y 
let y = (\ x -> let x' = x+1 in x:y x') in y 

है जो बस के रूप में समारोह अगर परिभाषित किया गया मानक का उपयोग fix:

y  x = let x' = x+1 in x:y x' 

के बिना रिकर्सिव नोटेशन