2010-08-22 12 views
13

पैरामीटरेटेड प्रकार जैसे सी ++ टेम्पलेट्स एक अच्छी बात है, लेकिन अधिकांश समय वे केवल अन्य प्रकारों द्वारा parametrized किया जा सकता है।क्या कोई प्रोग्रामिंग भाषा है जहां मूल्यों को पैरामीटर द्वारा पैरामीटर किया जा सकता है?

हालांकि, सी ++ में एक विशेष मामला है जहां एक पूर्णांक द्वारा टेम्पलेट को पैरामीट्रिज करना संभव है। उदाहरण के लिए, निश्चित लंबाई सरणियों एक विशिष्ट उपयोग के मामले हैं:

template<typename T, int SIZE> class FixedArray 
{ 
    T m_values[SIZE]; 

public: 
    int getElementCount() const { return SIZE; } 

    T operator[] (int i) const { 
     if (i<0 || i>=SIZE) 
      throw; 
     else 
      return m_values[i]; 
    } 
}; 

void f() 
{ 
    FixedArray<float, 5> float_array; // Declares a fixed array of 5 floats. 
    //The size is known at compile time, and values are allocated on the stack. 
} 

केवल निरंतर पूर्णांकों और संकेत C++ अनुमति है, लेकिन मुझे लगता है कि यह parametrization के लिए किसी भी मूल्य का उपयोग करने के लिए दिलचस्प हो सकता है (तैरता है, वर्ग उदाहरणों, आदि ।)। यह संकलन-समय पर आमतौर पर पूर्व शर्त को व्यक्त करने की अनुमति दे सकता है (आमतौर पर दस्तावेज़ीकरण में अनौपचारिक रूप से निर्दिष्ट), और रनटाइम पर उन्हें स्वचालित रूप से जांचें।

// Interval of type T between TMin and TMax. 
template<typename T, T TMin, T TMax> class Interval 
{ 
    T m_value; 

public: 
    Interval(int val) { *this = val; } 

    Interval& operator = (T val) { 
     //check that 'val is in [TMin, TMax] and set the value if so, throw error if not 
     if (val < TMin || val > TMax) 
      throw; 
     else 
      m_value = val; 

     return *this; 
    }; 

    operator T() const { return m_value; } 
} 

// Now define a f function which is only allowing a float between O and 1 
// Usually, that kind of function is taking a float parameter with the doc saying "the float is in 0-1 range". But with our Interval template we have 
// that constraint expressed in the type directly. 
float f(Interval<float, 0, 1> bounded_value) 
{ 
    // No need to check for boundaries here, since the template asserts at compile-time that the interval is valid 
    return ...; 
} 

// Example usage 
void main(); 
{ 
    float val = 0.5; 

    Interval<float, 0, 1> sample_interval = val; // OK. The boundary check is done once at runtime. 

    f(sample_interval);    // OK. No check, because it is asserted by the type constraint at compile-time. 
           // This can prevent endless precondition testing within an algorithm always using the same interval 

    sample_interval = 3*val;   // Exception at runtime because the constraint is no longer satisfied 

    f(sample_interval);    // If I am here, I am sure that the interval is valid. But it is not the case in that example. 
} 

क्या तब दिलचस्प हो सकता है इन प्रकार के बीच संबंधों को व्यक्त करने के लिए किया जाएगा: उदाहरण के लिए, यहाँ एक काल्पनिक सी ++ बोली में एक "अंतराल" टेम्पलेट है। उदाहरण के लिए, किसी अन्य अंतराल बी के साथ अंतराल ए को अन्य सीमाओं के साथ असाइन करने के लिए नियम व्यक्त करना, या संकलन-समय पर जांच की गई सभी चीज़ों के साथ अंतराल को मान असाइन करने का नियम।

क्या इस तरह के पैरामीट्रिजेशन (या एक समान दृष्टिकोण) के साथ कोई भाषा है, या किसी का अभी भी आविष्कार किया जाना चाहिए? कोई उपयोगी शोध पत्र?

+1

पास्कल में अभिन्न प्रकार के उपन्यास हैं जिन्हें इस विशेष मामले के रूप में देखा जा सकता है। – Joey

उत्तर

13

मूल्य जो पैरामीटर द्वारा मूल्यवान हैं, को dependent types कहा जाता है। आश्रित प्रकारों के विषय पर बहुत सारे शोध हुए हैं, लेकिन उनमें से कुछ "मुख्यधारा की भाषा" तक पहुंच गया है।

निर्भर प्रकारों के साथ बड़ी समस्या यह है कि यदि आपके प्रकार में अभिव्यक्तियां हैं, यानी, कोड के बिट्स, तो टाइप चेकर कोड निष्पादित करने में सक्षम होना चाहिए। यह पूर्ण सामान्यता में नहीं किया जा सकता है: यदि कोड के साइड इफेक्ट्स हैं तो क्या होगा? क्या होगा अगर कोड में अनंत लूप होता है? उदाहरण के लिए, एक सी की तरह वाक्य रचना में निम्नलिखित कार्यक्रम पर विचार (त्रुटि लोप जाँच):

int a, b; 
scanf("%d %d", &a, &b); 
int u[a], v[b]; 

संकलक कैसे पता कर सकता है सरणियों u और v एक ही आकार के हैं या नहीं? यह उपयोगकर्ता द्वारा दर्ज की गई संख्याओं पर निर्भर करता है! एक समाधान अभिव्यक्तियों में साइड इफेक्ट्स को प्रतिबंधित करना है जो कि प्रकारों में दिखाई देते हैं। लेकिन उस चीज़ का ध्यान नहीं ले करता है:

int f(int x) { while (1); } 
int u[f(a)], v[f(b)]; 

संकलक अनंत लूप तय करने के लिए u और v एक ही आकार है की कोशिश कर रहा में जाना जाएगा।

< विस्तार >
तो चलो प्रकार के अंदर दुष्प्रभाव न करे, और सीमा प्रत्यावर्तन और पाशन provably मामलों को समाप्त करे। क्या यह टाइपिंग को जांचने योग्य बनाता है? एक सैद्धांतिक दृष्टिकोण से, हाँ, यह कर सकते हैं।आपके पास Coq proof term जैसा कुछ हो सकता है। समस्या यह है कि टाइप चेकिंग तब आसानी से क्षीण हो सकती है यदि आपके पास पर्याप्त प्रकार की एनोटेशन है (टाइप करें एनोटेशन टाइपिंग जानकारी है जो प्रोग्रामर आपूर्ति करता है)। और यहां पर्याप्त मतलब है। एक बहुत भयानक। जैसा कि, प्रत्येक भाषा संरचना में एनोटेशन टाइप करें, न केवल परिवर्तनीय घोषणाएं बल्कि कॉल, ऑपरेटरों और बाकी सभी को भी कार्य करें। और प्रकार प्रोग्राम आकार के 99.9 999% का प्रतिनिधित्व करेंगे। सी ++ में पूरी चीज लिखना अक्सर तेज़ होगा और पूरे प्रोग्राम को सभी आवश्यक टाइप एनोटेशन के साथ लिखने से डीबग करें।

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

निर्भर प्रकार कभी कभी मुख्यधारा भाषाओं में एक सीमित रूप में दिखाई पड़ता है। उदाहरण के लिए, सी 99 उन सरणी की अनुमति देता है जिनके आकार निरंतर अभिव्यक्ति नहीं हैं; इस तरह के एक सरणी का प्रकार एक निर्भर प्रकार है। अनजाने में सी के लिए, कंपाइलर को ऐसी सरणी पर सीमाओं की जांच करने की आवश्यकता नहीं है, भले ही इसे स्थिर आकार की सरणी के लिए सीमाओं की जांच करने की आवश्यकता हो।

अधिक उपयोगी रूप से, Dependent MLML की एक बोली है जिसे सरल पूर्णांक अभिव्यक्तियों द्वारा अनुक्रमित किया जा सकता है। यह टाइप चेकर को अधिकांश सरणी सीमाओं को स्थिर रूप से जांचने की अनुमति देता है।

निर्भर प्रकार का एक और उदाहरण एमएल के लिए मॉड्यूल सिस्टम में प्रकट होता है। मॉड्यूल और उनके हस्ताक्षर (इंटरफेस भी कहा जाता है) अभिव्यक्तियों और प्रकारों के समान हैं, लेकिन गणनाओं का वर्णन करने के बजाय, वे कार्यक्रम की संरचना का वर्णन करते हैं।

निर्भर प्रकार है कि भावना सबसे प्रोग्रामर पहचान में भाषाओं प्रोग्रामिंग नहीं कर रहे हैं भाषाओं में बारी बहुत बार, लेकिन भाषाओं बल्कि साबित कार्यक्रमों (या बस गणितीय प्रमेयों) के गणितीय गुणों के लिए। examples in the wikipedia page में से अधिकांश उस प्रकृति के हैं।

¹ आम तौर पर, प्रकार सिद्धांतकारों के वे Higher-order types (प्रकार से parametrized प्रकार), polymorphism (भाव प्रकार से parametrized), और dependent types (भाव से parametrized प्रकार) है या नहीं अनुसार प्रकार सिस्टम वर्गीकृत करते हैं। इस वर्गीकरण को Barendregt's cube or the lambda cube कहा जाता है। वास्तव में यह एक हाइपरक्यूब है, लेकिन आम तौर पर चौथा आयाम (अभिव्यक्ति द्वारा पैरामीट्रिज्ड अभिव्यक्ति, यानी, कार्य) बिना कहने के चला जाता है।

+0

दिलचस्प!हो सकता है कि टाइप चेकर केवल निरंतर अभिव्यक्तियों और अक्षरों तक ही सीमित हो, संभवतः भाषा के एक गैर-ट्यूरिंग पूर्ण उप-समूह के साथ यह एक भाषा (जैसे मूल पूर्व शर्त और इनवर्सेंट्स को लागू करना) के लिए एक दिलचस्प जोड़ हो सकता है। मैं इस निर्भर प्रकार की चीज़ पर जांच करूंगा। –

+1

@ गैब्रियल: मैं देखता हूं कि मैं बीच में थोड़ी तेजी से चला गया। यहां तक ​​कि प्रकारों के भीतर उपलब्ध अभिव्यक्तियों के काफी प्रतिबंधित सबसेट के साथ, आश्रित प्रकारों के साथ उपयोग करने योग्य प्रोग्रामिंग भाषा होना मुश्किल हो सकता है (मेरा संपादन देखें)। आप दावे को लागू करने के बारे में सही हैं, यह आश्रित प्रकारों के पीछे बड़ी प्रेरणा है। (आपको याद है, यह किसी भी तरह के प्रकार के पीछे बड़ी प्रेरणा है।) – Gilles

+0

दिलचस्प उत्तर। मैं इस तरह के भ्रमित हूं कि सी ++ टेम्पलेट्स इस प्रकार के सिस्टम सिस्टम पर खड़े हैं। वे ओपी के रूप में प्रदान करते हैं, जैसा कि (स्थिर पूर्णांक) मानों के आधार पर प्रकारों की एक धारणा है, इसलिए वे निर्भर टाइपिंग के रूप में योग्य हो सकते हैं। टेम्पलेट्स कम ज्ञात प्रकार के पैरामीटर को भी स्वीकार करते हैं, यानी, टेम्पलेट टेम्पलेट पैरामीटर। इससे उन्हें लचीलापन की एक और डिग्री मिलती है, उन लोगों के पीछे सैद्धांतिक अवधारणा क्या होगी? – user394460

5

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

2

एडा 9 5 जेनेरिक औपचारिक पैरामीटर का समर्थन करता है जो मूल्य हैं। उदाहरण में on this page, Size एक सामान्य औपचारिक पैरामीटर है जिसका मूल्य एक सकारात्मक पूर्णांक होने के लिए आवश्यक है।

+2

क्या ये किसी भी तरह से जांच योग्य हैं या क्या वे रनटाइम दावे के रूप में समाप्त होते हैं? – Gian

+0

मुझे एडीए नहीं पता, लेकिन पहली नज़र में यह गैब्रियल के टेम्पलेट उदाहरण जैसा ही दिखता है, यानी आकार के मूल्य को संकलन समय पर जाना आवश्यक है। – sepp2k

+0

बाधित प्रकारों से जुड़े किसी प्रकार का रूपांतरण Constraint_Error फेंक सकता है, और मुझे कोई कारण नहीं दिख रहा है कि जेनेरिक औपचारिक पैरामीटर के लिए मूल्यों का रूपांतरण अलग क्यों होगा। (ड्राफ्ट 4.0) Ada95 spec में कोई उल्लेख नहीं है कि औपचारिक पैरामीटर मान प्रदान करने वाले अभिव्यक्ति संकलन-समय मूल्यांकन करने की आवश्यकता है। –

संबंधित मुद्दे

 संबंधित मुद्दे