Coq के लिए नरम परिचय: डेटा संरचनाएं और उच्च-क्रम फ़ंक्शन

जोड़े और सूचियाँ

पिछले भागों में, हमने सीखा कि नए डेटा प्रकार कैसे सेट करें, उनके ऊपर फ़ंक्शंस को परिभाषित करें और सामान्य रणनीति का उपयोग करके उनकी शुद्धता को साबित करें। यह उनके ऊपर कुछ डेटा संरचनाओं और उच्च-क्रम के कार्यों (बाद में एफडब्ल्यूपी) को परिभाषित करने का समय है।


एक आगमनात्मक परिभाषा में, प्रत्येक निर्माता में एक मनमाना संख्या में पैरामीटर हो सकते हैं, उदाहरण के लिए, एक परिभाषा

 आगमनात्मक natprod: प्रकार: = 
   जोड़ी: नट -> नट -> नटप्रोड।

इस तरह से पढ़ें: संख्याओं की एक जोड़ी बनाने का केवल एक ही तरीका है - प्रकार के nat दो तर्कों के लिए pair निर्माता को लागू करें

 में सरल (जोड़ी 1 2)।
 (* ==> जोड़ी 1 2: नेटप्रोड *)

Coq में Notation शर्करा का उपयोग करके Notation कमांड का प्रयोग करने के लिए एक तंत्र है। उदाहरण के लिए, हम उपसर्ग फॉर्म से छुटकारा पा सकते हैं और संख्याओं के जोड़े को इस तरह परिभाषित कर सकते हैं:

 संकेतन "(x, y)": = (जोड़ी xy)।

इस नए संकेतन को अब व्यापक रूप से अभिव्यक्ति और कार्यों और परिभाषाओं के विवरणों में उपयोग किया जा सकता है:

 परिभाषा fst (p: natprod): nat: = 
   मैच पी के साथ 
   |  (x, y) => x 
   अंत। 
 परिभाषा snd (p: natprod): nat: = 
   मैच पी के साथ 
   |  (x, y) => y 
   अंत।
 प्रमेय परीक्षण: forall (ab: nat), 
  (ए, बी) = (एफएसटी (ए, बी), एसएनडी (ए, बी))। 
 सबूत।  रिफ्लेक्सिविटी।  QED।

एक जोड़ी की परिभाषा को संक्षेप में, हम संख्याओं की सूची का भी वर्णन कर सकते हैं:

 आगमनात्मक natlist: प्रकार: = 
   |  nil: नेटलिस्ट 
   |  cons: nat -> नेटलिस्ट -> नेटलिस्ट।
 संकेतन "h :: t": = (cons ht) (स्तर 60 पर, समरूपता)। 
 संकेतन "[]": = नील। 
 संकेतन "[h, .., t]": = (cons h .. (cons t nil) ..)।

प्रस्तुत किए गए वाक्यविन्यास नियमों का उपयोग करके, हम सूचियों को कई तरीकों से परिभाषित कर सकते हैं:

 परिभाषा सूची 1: = 1 :: (2 :: (3 :: नील))। 
 परिभाषा सूची 2: = [1,2,3]।

सूचियों का उपयोग सार्वभौमिक रूप से कार्यात्मक प्रोग्रामिंग भाषाओं में किया जाता है। लेकिन क्या होगा यदि हम पूर्णांक की सूची, तार्किक मूल्यों की सूची बनाने के लिए एक सामान्यीकृत परिभाषा का उपयोग करना चाहते हैं? Coq में बहुरूपी आगमनात्मक प्रकारों को परिभाषित करने के लिए एक तंत्र है:

 आगमनात्मक सूची (X: प्रकार): प्रकार: = 
   |  nil: सूची X 
   |  विपक्ष: एक्स -> सूची एक्स -> सूची एक्स।

यहाँ nil और cons पॉलीमॉर्फिक निर्माणकर्ताओं की भूमिका निभाते हैं। इसी तरह, हम बहुरूपी कार्यों को परिभाषित कर सकते हैं।

FVP

फ़िल्टर

कई आधुनिक प्रोग्रामिंग भाषाओं में, एक फ़ंक्शन या तो एक फ़ंक्शन के रूप में किसी अन्य फ़ंक्शन को स्वीकार कर सकता है या परिणामस्वरूप इसे वापस कर सकता है। इस तरह के कार्यों को उच्च-क्रम फ़ंक्शन कहा जाता है और व्यापक रूप से गणित में उपयोग किया जाता है (उदाहरण के लिए, व्युत्पन्न गणना ऑपरेटर) और प्रोग्रामिंग (उदाहरण के लिए, filter फ़ंक्शन एक विधेय द्वारा सेट के तत्वों को filter करता है):

 फिक्सेपिन इवन (n: nat): बूल: =
   n के साथ मैच
   |  ओ => सत्य
   |  SO => असत्य
   |  एस (एस एन ') => एनबीबी एन'
   अंत।

 Fixpoint फ़िल्टर {X: प्रकार} (परीक्षण: X → बूल) (l: सूची X)
                 : (सूची X): =
   के साथ मैच एल
   |  [] => []
   |  h :: t => यदि परीक्षण h तो h :: (फ़िल्टर परीक्षण t)
                         और फिल्टर परीक्षण टी
   अंत।

 उदाहरण परीक्षण: फ़िल्टर इब [1,2,3,4,5] = [2,4]।
 सबूत।  रिफ्लेक्सिविटी।  QED।

नक्शा

FVP map इस फ़ंक्शन को सूची के प्रत्येक तत्व पर लागू करता है, परिणामों की सूची लौटाता है:

 फिक्सपॉइंट मैप {XY: टाइप} (f: X → Y) (l: लिस्ट X)
              : (सूची वाई): =
   के साथ मैच एल
   |  [] => []
   |  h :: t => (fh) :: (नक्शा फुट)
   अंत।

गीतात्मक विषयांतर

पिछले लेखों में से एक के लिए टिप्पणियों में, यह सवाल पूछा गया था कि मशीन द्वारा साक्ष्य की व्याख्या कैसे होती है।

जैसा कि ज्ञात है, करी-हावर्ड आइसोमोर्फिज्म साक्ष्यों और कार्यक्रमों के बीच पत्राचार को निर्धारित करता है। हम कुछ उपमाएँ बना सकते हैं:

• प्रमेय - प्रकार
• साक्ष्य - शर्तें
• प्रमाण सत्यापन - शब्द प्रकार सत्यापन

इस प्रकार, कॉक सिर्फ एक शब्द है जो शब्दों के प्रकार को प्रदर्शित करता है। उपयोगकर्ता रणनीति का उपयोग करके आउटपुट एल्गोरिदम को संशोधित कर सकता है।