इस स्व-आवेदनशील फैक्टोरियल फ़ंक्शन का प्रकार क्या है?

Question

मैंने सी ++ में एक अज्ञात फैक्टोरियल फ़ंक्शन लिखा और जी ++ 4.9.2 के साथ अपना कोड संकलित किया। यह अच्छी तरह से काम करता है। हालांकि, मुझे अपने फ़ंक्शन के प्रकार को नहीं पता है।

#include<iostream> 
#include<functional> 
using std::function; 
int main() 
{ 
    //tested at g++ 4.9.2 
    //g++ -std=c++1y -o anony anony.cpp 
    auto fac = [](auto self,auto n)->auto{ 
     if(n < 1) 
      return 1; 
     else 
      return n * self(self,n-1); 
    }; 
    std::cout<<fac(fac,3)<<std::endl;//6 
    return 0; 
} 

तो, मुझे आश्चर्य है: क्या fac और self के प्रकार हैं? अगर मैं सिर्फ हास्केल में सी ++ कोड का अनुवाद है, यह संकलन नहीं करेगा क्योंकि यह अनंत प्रकार शामिल है:

fac2 self 0 = 1 
fac2 self n = n * (self self $ n-1) 

और मैं इसे आसपास कुछ पुनरावर्ती प्रकार काम को परिभाषित करने के लिए है:

data Y a = Y ((Y a)->a->a) 
fac2 self 0 = 1 
fac2 self n = n * ((applY self self) (n-1)) 
    where applY (Y f1) f2 = f1 f2 
fact2 = fac2 $ Y fac2 

तो , g ++ को fac फ़ंक्शन का सही प्रकार क्यों मिल सकता है, और g ++ किस प्रकार fac फ़ंक्शन लगता है?

Answer 1

auto fac = के बाद अभिव्यक्ति एक लैम्ब्डा अभिव्यक्ति है, और संकलक स्वचालित रूप से इससे एक बंद ऑब्जेक्ट उत्पन्न करेगा। उस वस्तु का प्रकार अद्वितीय है और केवल संकलक के लिए जाना जाता है।

N4296 से, §5.1.2/3[expr.prim.lambda]

लैम्ब्डा अभिव्यक्ति के प्रकार (जो भी बंद वस्तु के प्रकार है) एक अद्वितीय, अज्ञात गैर-संघ वर्ग प्रकार है - जिसे बंद करने का प्रकार कहा जाता है - जिनकी गुण नीचे वर्णित हैं। यह वर्ग प्रकार न तो कुल (8.5.1) है और न ही एक शाब्दिक प्रकार (3.9) है। क्लोजर प्रकार को सबसे छोटे ब्लॉक स्कोप, क्लास स्कोप, या नेमस्पेस स्कोप में घोषित किया गया है जिसमें संबंधित लैम्ब्डा-अभिव्यक्ति शामिल है।

ध्यान दें कि इसके कारण, यहां तक ​​कि दो समान लैम्ब्डा अभिव्यक्तियों के अलग-अलग प्रकार होंगे। उदाहरण के लिए,

auto l1 = []{}; 
auto l2 = []{}; // l1 and l2 are of different types 

---

आपका लैम्ब्डा अभिव्यक्ति एक सी ++ 14 सामान्य लैम्ब्डा है, और एक वर्ग के लिए संकलक है जो निम्न के जैसा दिखता है के द्वारा अनुवाद किया जाएगा:

struct __unique_name 
{ 
    template<typename Arg1, typename Arg2> 
    auto operator()(Arg1 self, Arg2 n) const 
    { 
     // body of your lambda 
    } 
}; 

मैं टिप्पणी नहीं कर सकता हास्केल भाग पर, लेकिन सी ++ में रिकर्सिव अभिव्यक्ति काम करने का कारण यह है कि आप बस प्रत्येक कॉल में बंद ऑब्जेक्ट इंस्टेंस (fac) की एक प्रति पास कर रहे हैं। operator() एक टेम्पलेट होने के नाते लैम्ब्डा के प्रकार को कम करने में सक्षम है, भले ही यह वह नहीं है जिसे आप अन्यथा नाम दे सकते हैं।

Answer 2

सी ++ fac वास्तव में एक फ़ंक्शन नहीं है, लेकिन एक संरचना जिसमें सदस्य कार्य होता है।

struct aaaa // Not its real name. 
{ 
    template<typename a, typename b> 
    auto operator()(a self, b n) const 
    { 
    } 
}; 

अतिभारित कॉल ऑपरेटर प्रवंचना के कुछ है कि सी ++ क्रम जब आप fac "कॉल" "लैम्ब्डा कार्यों"

को लागू करने में प्रदर्शन छुपाता है, क्या होता है

fac.operator() (fac, 3); 

तो

है फ़ंक्शन के लिए तर्क स्वयं कार्य नहीं है, लेकिन एक ऑब्जेक्ट जिसमें सदस्य के रूप में है।
इसका एक प्रभाव यह है कि फ़ंक्शन का प्रकार (यानी operator() का प्रकार) operator() फ़ंक्शन के प्रकार में नहीं होता है।
(self का प्रकार वह संरचना है जो फ़ंक्शन को परिभाषित करता है।)

टेम्पलेट भाग इस काम के लिए आवश्यक नहीं है; इस fac "समारोह" की एक गैर जेनेरिक वर्जन है:

struct F 
{ 
    int operator()(const F& self, int n) const 
    { 
     // ... 
    } 
}; 

F fac; 
fac(fac, 3); 

अगर हम टेम्पलेट रखने के लिए और नाम बदलने operator()applY रहे हैं:

// The Y type 
template<typename a> 
struct Y 
{ 
    // The wrapped function has type (Y<a>, a) -> a 
    a applY(const Y<a>& self, a n) const 
    { 
     if(n < 1) 
      return 1; 
     else 
      return n * self.applY(self, n-1); 
    } 
}; 

template<typename a> 
a fac(a n) 
{ 
    Y<a> y; 
    return y.applY(y, n); 
} 

हम देखते हैं कि आपके काम कर हास्केल कार्यक्रम और अपने सी ++ प्रोग्राम बहुत समान हैं - मतभेद मुख्य रूप से विराम चिह्न हैं।

इसके विपरीत, हास्केल

fac2 self 0 = 1 
fac2 self n = n * (self self $ n-1) 

selfमें एक समारोह है, और fac2 के प्रकार

X -> Int -> Int 

कुछ X के लिए

होना जरूरी होगा।
self एक समारोह है, और self self $ n-1 एक इंट है, self का प्रकार भी X -> Int -> Int है।

लेकिन X क्या हो सकता है?
यह self के प्रकार के समान होना चाहिए, i.e X -> Int -> Int।
लेकिन इसका मतलब है कि है कि self के प्रकार (X के लिए प्रतिस्थापन):

(X -> Int -> Int) -> Int -> Int 

तो प्रकार X भी

(X -> Int -> Int) -> Int -> Int 

होना चाहिए, ताकि self के प्रकार होना चाहिए

((X -> Int -> Int) -> Int -> Int) -> Int -> Int 

और इसी तरह, विज्ञापन infinitum।
वह हैस्केल में प्रकार अनंत होगा।

हास्केल के लिए आपका समाधान अनिवार्य रूप से आवश्यक संकेत प्रदान करता है कि सी ++ सदस्य संरचना के साथ अपनी संरचना के माध्यम से उत्पन्न करता है।

Answer 3

जैसा कि अन्य ने बताया, लैम्ब्डा एक टेम्पलेट से युक्त संरचना के रूप में कार्य करता है।सवाल तब बन जाता है: क्यों Haskell स्वयं अनुप्रयोग टाइप नहीं कर सकता है, जबकि सी ++ कर सकते हैं?

उत्तर सी ++ टेम्पलेट्स और हास्केल पॉलिमॉर्फिक कार्यों के बीच अंतर पर है। इनकी तुलना करें:

-- valid Haskell 
foo :: forall a b. a -> b -> a 
foo x y = x 

// valid C++ 
template <typename a, typename b> 
a foo(a x, b y) { return x; } 

हालांकि वे लगभग बराबर दिख सकते हैं, वे वास्तव में ऐसा नहीं हैं।

जब हास्केल प्रकार उपर्युक्त घोषणा की जांच करता है, तो यह जांचता है कि परिभाषा किसी प्रकार के a,b के लिए सुरक्षित है। यही है, अगर हम किसी भी दो प्रकार के साथ a,b को प्रतिस्थापित करते हैं, तो फ़ंक्शन को अच्छी तरह से परिभाषित किया जाना चाहिए।

सी ++ एक और दृष्टिकोण का पालन करता है। टेम्पलेट परिभाषा पर, यह जांच नहीं की गई है कि a,b के लिए कोई भी प्रतिस्थापन सही होगा। यह चेक टेम्पलेट के उपयोग के बिंदु पर स्थगित है, यानी तत्काल समय पर। बिंदु पर जोर करने के लिए, चलो हमारे कोड में एक +1 जोड़ें:

-- INVALID Haskell 
foo :: forall a b. a -> b -> a 
foo x y = x+1 

// valid C++ 
template <typename a, typename b> 
a foo(a x, b y) { return x+1; } 

हास्केल परिभाषा प्रकार की जांच नहीं करेगा: कोई गारंटी नहीं है कि आप x+1 प्रदर्शन कर सकते हैं जब x एक मनमाना प्रकार का है नहीं है। सी ++ कोड ठीक है, इसके बजाए। तथ्य यह है कि a के कुछ प्रतिस्थापन गलत कोड पर ले जाते हैं, अभी अप्रासंगिक है।

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