हास्केल

Question

में इओटा कार्यान्वित करना Iota केवल एक संयोजक का उपयोग करके एक हास्यास्पद छोटी "प्रोग्रामिंग भाषा" है। मुझे यह समझने में दिलचस्पी है कि यह कैसे काम करता है, लेकिन मुझे उस भाषा में कार्यान्वयन को देखना उपयोगी होगा, जिसे मैं परिचित हूं।

मुझे योजना में लिखित आईओटा प्रोग्रामिंग भाषा का कार्यान्वयन मिला। हालांकि मुझे इसे हास्केल में अनुवाद करने में थोड़ी सी परेशानी हो रही है। यह काफी आसान है, लेकिन मैं हास्केल और योजना दोनों के लिए अपेक्षाकृत नया हूं।

हास्केल में समकक्ष Iota कार्यान्वयन कैसे लिखेंगे?

(let iota() 
    (if (eq? #\* (read-char)) ((iota)(iota)) 
     (lambda (c) ((c (lambda (x) (lambda (y) (lambda (z) ((x z)(y z)))))) 
      (lambda (x) (lambda (y) x)))))) 

Answer 1

मैं अपने आप को इस सामग्री के कुछ शिक्षण किया गया है, तो मुझे यकीन है कि मैं सही निम्नलिखित मिल आशा ...

n.m. के रूप में उल्लेख है कि तथ्य यह है कि हास्केल टाइप किया गया है इस सवाल के लिए बहुत महत्वपूर्ण है; टाइप सिस्टम सिस्टम को किस अभिव्यक्ति का गठन किया जा सकता है, और विशेष रूप से लैम्ब्डा कैलकुलेशन के लिए सबसे बुनियादी प्रकार के सिस्टम स्वयं-अनुप्रयोग को रोकते हैं, जो आपको एक गैर-ट्यूरिंग पूर्ण भाषा प्रदान करता है। ट्यूरिंग पूर्णता को को मूल प्रकार की प्रणाली के शीर्ष पर जोड़ा गया है (या तो fix :: (a -> a) -> a ऑपरेटर या रिकर्सिव प्रकार)।

इसका मतलब यह नहीं है कि आप इसे हास्केल में बिल्कुल लागू नहीं कर सकते हैं, बल्कि इस तरह के कार्यान्वयन में केवल एक ऑपरेटर नहीं होगा।

कार्य # 1:second example one-point combinatory logic basis from here लागू है, और एक fix समारोह जोड़ें:

iota' :: ((t1 -> t2 -> t1) 
      -> ((t5 -> t4 -> t3) -> (t5 -> t4) -> t5 -> t3) 
      -> (t6 -> t7 -> t6) 
      -> t) 
     -> t 
iota' x = x k s k 
    where k x y = x 
      s x y z = x z (y z) 

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

अब आप iota' और fix के मामले में किसी भी प्रोग्राम लिख सकते हैं। समझाते हुए कि यह कैसे काम करता है थोड़ा सा शामिल है। (संपादित करें:।। ध्यान दें कि यह iota' मूल प्रश्न में λx.x S K के रूप में ही नहीं है, जो भी ट्यूरिंग-पूर्ण है यह λx.x K S K है, यह मामला है कि iota' कार्यक्रमों मैंने iota कार्यक्रमों से अलग होने जा रहे हैं है हास्केल में iota = λx.x S K परिभाषा की कोशिश की है, यह typechecks, लेकिन जब आप k = iota (iota (iota iota)) कोशिश करते हैं और s = iota (iota (iota (iota iota))) आप प्रकार त्रुटियों मिल)

कार्य # 2:।

: untyped लैम्ब्डा पथरी denotations इस पुनरावर्ती प्रकार का उपयोग हास्केल में एम्बेड किया जा सकता है

newtype D = In { out :: D -> D } 

D मूल रूप से एक प्रकार है जिसका तत्व D से D से कार्य करता है। D -> D फ़ंक्शन को सादे D, और out :: D -> (D -> D) में विपरीत करने के लिए हमारे पास In :: (D -> D) -> D है। तो अगर हमारे पास x :: D है, तो हम out x x :: D कर इसे स्वयं लागू कर सकते हैं।

कि दो, अब हम लिख सकते हैं:

iota :: D 
iota = In $ \x -> out (out x s) k 
    where k = In $ \x -> In $ \y -> x 
      s = In $ \x -> In $ \y -> In $ \z -> out (out x z) (out y z) 

यह In और out से कुछ 'शोर' की आवश्यकता है; हास्केल अभी भी D को D पर लागू करने के लिए मना कर देता है, लेकिन हम इसके आसपास पाने के लिए In और out का उपयोग कर सकते हैं।आप वास्तव में D के मानों के साथ कुछ भी उपयोगी नहीं कर सकते हैं, लेकिन आप एक ही पैटर्न के आसपास एक उपयोगी प्रकार डिज़ाइन कर सकते हैं।

---

संपादित करें: जरा भी मूल रूप से λx.x S K, जहां K = λx.λy.x और S = λx.λy.λz.x z (y z) है। यानी, iota दो तर्क तर्क लेता है और इसे एस और के लिए लागू करता है; इसलिए एक ऐसा फ़ंक्शन पारित करने से जो आपका पहला तर्क देता है, आपको एस मिलता है, और एक ऐसा फ़ंक्शन पारित करके जो अपना दूसरा तर्क देता है, आपको के. मिलते हैं। इसलिए यदि आप "वापसी पहले तर्क" और "आईओटा के साथ" दूसरी वापसी "लिख सकते हैं, तो आप आईओटा के साथ एस और के लिख सकते हैं। लेकिन S and K are enough to get Turing completeness, तो आप सौदा में ट्यूरिंग पूर्णता भी प्राप्त करते हैं। यह पता चला है कि आप आईओटा के साथ आवश्यक चयनकर्ता कार्य लिख सकते हैं, इसलिए आईओटा पूर्णता के लिए पर्याप्त है।

तो इससे एसके कैलकुलेशन को समझने के लिए आईओटी को समझने की समस्या कम हो जाती है।