ट्यूरिंग पूर्ण प्रकार की प्रणाली का कारण क्या है

Question

स्कैला और हास्केल के पास "पूर्ण प्रकार के सिस्टम ट्यूरिंग" हैं। आमतौर पर, ट्यूरिंग पूर्णता computations and languages को संदर्भित करती है। प्रकारों के संदर्भ में इसका वास्तव में क्या अर्थ है?

क्या कोई इस बात का उदाहरण दे सकता है कि प्रोग्रामर इससे कैसे लाभ उठा सकता है?

पीएस मैं हास्केल बनाम स्कैला के प्रकार सिस्टम की तुलना नहीं करना चाहता। यह सामान्य रूप से शब्द के बारे में अधिक है।

पीएसएस यदि यह संभव है तो स्कैला उदाहरण।

Answer 1

प्रकारों के संदर्भ में इसका वास्तव में क्या अर्थ है?

इसका मतलब है कि टाइप सिस्टम में मनमाने ढंग से गणना करने के लिए इसमें पर्याप्त सुविधाएं हैं। एक बहुत ही कम प्रमाण के रूप में, मैं SK कैलकुस के प्रकार के स्तर के कार्यान्वयन के नीचे प्रस्तुत करता हूं; ऐसे कई स्थान हैं जो इस गणित की ट्यूरिंग-पूर्णता और इसका क्या अर्थ है, इस पर चर्चा करते हैं, इसलिए मैं इसे यहां वापस नहीं लाऊंगा।

{-# LANGUAGE DataKinds #-} 
{-# LANGUAGE TypeFamilies #-} 
{-# LANGUAGE UndecidableInstances #-} 
{-# LANGUAGE TypeOperators #-} 

infixl 1 `App` 
data Term = S | K | App Term Term 

type family Reduce t where 
    Reduce S = S 
    Reduce K = K 
    Reduce (S `App` x `App` y `App` z) = Reduce (x `App` z `App` (y `App` z)) 
    Reduce (K `App` x `App` y) = Reduce x 
    Reduce (x `App` y) = Reduce (Reduce x `App` y) 

आप इसे एक ghci प्रॉम्प्ट पर कार्रवाई में देख सकते हैं; उदाहरण के लिए, SK पथरी में, शब्द SKSK कम कर देता है (अंततः) करने के लिए सिर्फ K:

> :kind! Reduce (S `App` K `App` S `App` K) 
Reduce (S `App` K `App` S `App` K) :: Term 
= 'K 

यहाँ के रूप में अच्छी कोशिश करने के लिए एक मजेदार एक है:

> type I = S `App` K `App` K 
> type Rep = S `App` I `App` I 
> :kind! Reduce (Rep `App` Rep) 

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

क्या कोई ऐसा उदाहरण दे सकता है कि प्रोग्रामर इससे कैसे लाभ उठा सकता है?

मनमाना प्रकार-स्तर की गणना आपको अपने प्रकारों पर मनमाने ढंग से आविष्कार व्यक्त करने की अनुमति देती है, और संकलक सत्यापित करता है (संकलन समय पर) जिसे वे संरक्षित करते हैं। एक लाल-काले पेड़ चाहते हैं? एक लाल-काले पेड़ के बारे में कैसे है जो संकलक जांच सकता है लाल-काले-पेड़ के आविष्कारों को संरक्षित करता है? यह आसान होगा, ठीक है, क्योंकि यह कार्यान्वयन कीड़े की पूरी कक्षा के नियमों का पालन करता है? XML मानों के लिए एक प्रकार के बारे में जो किसी विशेष स्कीमा से मेल खाने के लिए स्थिर रूप से जाना जाता है? असल में, एक कदम आगे क्यों न जाएं और एक पैरामीटरयुक्त प्रकार लिखें जिसका पैरामीटर स्कीमा का प्रतिनिधित्व करता है? फिर आप रनटाइम पर एक स्कीमा में पढ़ सकते हैं, और आपके संकलन-समय की जांच गारंटी है कि आपका पैरामीटरयुक्त मान केवल उस स्कीमा में अच्छी तरह से गठित मूल्यों का प्रतिनिधित्व कर सकता है। अच्छा!

या शायद, एक और संभावित उदाहरण: क्या होगा यदि आप अपने कंपाइलर को यह जांचना चाहते थे कि आपने कभी भी उस कुंजी के साथ अपने शब्दकोश को अनुक्रमित नहीं किया है जो वहां नहीं था? एक पर्याप्त उन्नत प्रकार प्रणाली के साथ, आप कर सकते हैं।

बेशक, हमेशा एक कीमत होती है। हास्केल (और शायद स्कैला?) में, बहुत ही रोमांचक संकलन-समय की जांच की कीमत प्रोग्रामर समय और प्रयास का एक बड़ा सौदा खर्च कर रही है जो संकलक को आश्वस्त करती है कि जो चीज आप जांच रहे हैं वह सच है - और यह अक्सर उच्च होता है ऊपर की लागत के साथ ही एक उच्च चल रहे रखरखाव लागत।