क्या जीएचसी वास्तव में मानचित्र, स्कैनल, फ़ोल्डर इत्यादि को कभी भी इनलाइन नहीं कर सकता है?

Question

मैंने देखा है कि GHC manual कहता है "एक आत्म-पुनरावर्ती कार्य के लिए, लूप ब्रेकर केवल फ़ंक्शन ही हो सकता है, इसलिए एक इनलाइन प्रज्ञा हमेशा अनदेखा की जाती है।"

इस तरह map, zip, scan*, fold*, sum, आदि inlined नहीं किया जा सकता आम पुनरावर्ती कार्यात्मक निर्माणों के हर आवेदन कहना नहीं है?

जब आप उन्हें नियोजित करते हैं, उचित सख्त टैग जोड़ते हैं, या शायद "स्ट्रीम फ़्यूज़न" जैसी फैंसी तकनीकों को here की अनुशंसा करते हैं तो आप इन सभी कार्यों को फिर से लिख सकते हैं।

फिर भी, क्या यह नाटकीय रूप से कोड लिखने की हमारी क्षमता को बाधित नहीं करता है जो एक साथ तेजी से और सुरुचिपूर्ण है?

Answer 1

वास्तव में, जीएचसी वर्तमान में इनलाइन रिकर्सिव फ़ंक्शंस नहीं कर सकता है। हालांकि:

• GHC अभी भी पुनरावर्ती कार्यों विशेषज्ञ होंगे। उदाहरण के लिए,

  fac :: (Eq a, Num a) => a -> a 
  fac 0 = 1 
  fac n = n * fac (n-1) 
  
  f :: Int -> Int 
  f x = 1 + fac x 
  

  GHC स्थान मिलेगी कि fac प्रकार Int -> Int में प्रयोग किया जाता है और उस प्रकार है, जो तेजी से पूर्णांक गणित का उपयोग करता है के लिए fac की एक विशेष संस्करण उत्पन्न दिया।

  यह विशेषज्ञता स्वचालित रूप से एक मॉड्यूल के भीतर होती है (उदाहरण के लिए यदि fac और f समान मॉड्यूल में परिभाषित किया गया है)। पार मॉड्यूल विशेषज्ञता (जैसे अगर f और fac विभिन्न मॉड्यूल में परिभाषित कर रहे हैं) के लिए, an INLINABLE pragma साथ होने वाली विशेष समारोह का प्रतीक:

  {-# INLINABLE faC#-} 
  fac :: (Eq a, Num a) => a -> a 
  ... 
  

• मैनुअल परिवर्तनों जो कार्यों nonrecursive कर रहे हैं। सबसे कम-शक्ति तकनीक static argument transformation है, जो तर्कों के साथ पुनरावर्ती कार्यों पर लागू होती है जो रिकर्सिव कॉल पर नहीं बदलती हैं (उदाहरण के लिए map, filter, fold* जैसे कई उच्च-आदेश फ़ंक्शन)। यह परिवर्तन

  map f xs0 = go xs0 
      where 
      go []  = [] 
      go (x:xs) = f x : go xs 
  

  में

  map f []  = [] 
  map f (x:xs) = f x : map f xs 
  

  बदल जाता है ताकि एक फोन जैसे

  g :: [Int] -> [Int] 
  g xs = map (2*) xs 
  

  map inlined है और

  g [] = [] 
  g (x:xs) = 2*x : g xs 
  

  यह transformati बन जाएगा foldr और foldl जैसे प्रीलूड फ़ंक्शंस पर लागू किया गया है।

• फ़्यूज़न तकनीक भी कई कार्यों को गैर-आक्रामक बनाती है, और स्थिर तर्क परिवर्तन से अधिक शक्तिशाली होती हैं। सूचियों के लिए मुख्य दृष्टिकोण, जो प्रीलूड में बनाया गया है, shortcut fusion है। मूल दृष्टिकोण foldr और/या build का उपयोग करने वाले गैर-पुनरावर्ती कार्यों के रूप में जितना संभव हो उतना कार्य लिखना है; तो सभी रिकर्सन foldr में कब्जा कर लिया गया है, और foldr से निपटने के लिए विशेष नियम हैं। इस विलय के

  ले रहा है लाभ सिद्धांत रूप में आसान है:, मैनुअल प्रत्यावर्तन से बचने this list में पुस्तकालय कार्यों जैसे foldr, map, filter, और किसी भी काम करता है पसंद करते हैं।विशेष रूप से, इस शैली में कोड लिखने से कोड उत्पन्न होता है जो "साथ ही तेज़ और सुरुचिपूर्ण" होता है।

• आधुनिक पुस्तकालय जैसे text और vector दृश्यों के पीछे stream fusion का उपयोग करें। डॉन स्टीवर्ट ने ब्लॉग पोस्ट की एक जोड़ी लिखी (1, 2) अब अप्रचलित लाइब्रेरी uvector में कार्रवाई में यह दर्शाती है, लेकिन वही सिद्धांत टेक्स्ट और वेक्टर पर लागू होते हैं।

  शॉर्टकट संलयन के साथ, पाठ और वेक्टर में स्ट्रीम संलयन का लाभ लेना सिद्धांत रूप से आसान है: मैन्युअल रिकर्सन से बचें, पुस्तकालय कार्यों को प्राथमिकता दें जिन्हें "संलयन के अधीन" के रूप में चिह्नित किया गया है।

• रिकर्सिव कार्यों के इनलाइनिंग का समर्थन करने के लिए जीएचसी में सुधार करने पर चल रहे काम चल रहे हैं। यह supercompilation के सामान्य शीर्षक के अंतर्गत आता है, और इस पर हालिया कार्य Max Bolingbroke और Neil Mitchell के नेतृत्व में हुआ है।

Answer 2

एक स्वयं-पुनरावर्ती फ़ंक्शन के लिए, लूप ब्रेकर केवल फ़ंक्शन ही हो सकता है, इसलिए एक इनलाइन प्रज्ञा हमेशा अनदेखा की जाती है।

यदि कुछ रेखांकित है, तो इसे रेखांकित करने के लिए, आपको यह जानना होगा कि इसे संकलित समय पर कितनी बार निष्पादित किया जाता है। यह एक चर लंबाई लंबाई इनपुट होगा, यह संभव नहीं है।

फिर भी, क्या यह नाटकीय रूप से कोड लिखने की हमारी क्षमता को बाधित नहीं करता है जो एक साथ तेजी से और सुरुचिपूर्ण है?

कुछ तकनीकें हैं, हालांकि उनकी सामान्य स्थिति की तुलना में रिकर्सिव कॉल बहुत अधिक तेज हो सकती हैं। उदाहरण के लिए, पूंछ कॉल अनुकूलन SOWiki

Answer 3

संक्षेप में, जितनी बार आप सोचेंगे उतनी बार नहीं। इसका कारण यह है कि पुस्तकालयों को कार्यान्वित करते समय स्ट्रीम फ्यूजन जैसी "फैंसी तकनीकें" नियोजित की जाती हैं, और लाइब्रेरी उपयोगकर्ताओं को उनके बारे में चिंता करने की आवश्यकता नहीं होती है।

Data.List.map पर विचार करें। आधार पैकेज के रूप में

map :: (a -> b) -> [a] -> [b] 
map _ []  = [] 
map f (x:xs) = f x : map f xs 

यह map आत्म पुनरावर्ती है map को परिभाषित करता है, तो GHC यह इनलाइन नहीं होंगे।

हालांकि, base भी निम्न पुनर्लेखन नियमों को परिभाषित करता है:

{-# RULES 
"map"  [~1] forall f xs. map f xs    = build (\c n -> foldr (mapFB c f) n xs) 
"mapList" [1] forall f.  foldr (mapFB (:) f) [] = map f 
"mapFB"  forall c f g.  mapFB (mapFB c f) g  = mapFB c (f.g) 
    #-} 

इस के माध्यम से foldr/build fusion, तो, समारोह इनकार नहीं किया जा सकता है, यह मूल map साथ बदलता है map का उपयोग करता है बदल देता है। चूंकि संलयन स्वचालित रूप से होता है, यह उपयोगकर्ता के बारे में जागरूक होने पर निर्भर नहीं करता है।

सबूत के रूप में यह सब काम करता है, आप जांच सकते हैं कि जीएचसी विशिष्ट इनपुट के लिए क्या उत्पादन करता है।

proc1 = sum . take 10 . map (+1) . map (*2) 

eval1 = proc1 [1..5] 
eval2 = proc1 [1..] 

जब -O2 साथ संकलित, GHC proc1 के सभी एक ही पुनरावर्ती रूप में (के रूप में -ddump-simpl के साथ मुख्य उत्पादन में देखा) फ़्यूज़: इस कार्य के लिए।

बेशक इन तकनीकों को पूरा करने के लिए सीमाएं हैं।उदाहरण के लिए, बेवकूफ औसत कार्य, mean xs = sum xs/length xs आसानी से मैन्युअल रूप से एक गुना में परिवर्तित हो जाता है, और frameworks exist that can do so automatically, हालांकि वर्तमान में मानक कार्यों और संलयन ढांचे के बीच स्वचालित रूप से अनुवाद करने का कोई ज्ञात तरीका नहीं है। तो इस मामले में, उपयोगकर्ता को कंपाइलर-उत्पादित कोड की सीमाओं से अवगत होना चाहिए।

तो कई मामलों में संकलक तेजी से और सुरुचिपूर्ण कोड बनाने के लिए पर्याप्त रूप से उन्नत होते हैं। यह जानकर कि वे ऐसा कब करेंगे, और जब संकलक गिरने की संभावना है, तो आईएमएचओ कुशल हास्केल कोड लिखने के तरीके सीखने का एक बड़ा हिस्सा है।