🔢 mathematics

A proof-theoretic approach to abstract interpretation

यह शोध पत्र व्यवस्थित रूप से उन तार्किक प्रणालियों का निर्माण करके एब्स्ट्रैक्ट इंटरप्रिटेशन (abstract interpretation) के लिए एक प्रमाण-सिद्धांतिक ढांचा स्थापित करता है जिनके बीजगणितीय संरचनाएं दिए गए एब्स्ट्रैक्ट लैट्टिस (abstract lattices) के अनुरूप होती हैं, जिससे ध्वनि और पूर्णता (soundness and completeness) के परिणामों के माध्यम से प्रोग्राम विश्लेषण को प्रमाण सिद्धांत और बीजगणितीय तर्क के साथ एकीकृत किया जा सके।

मूल लेखक: Vijay D'Silva, Alessandra Palmigiano, Apostolos Tzimoulis, Caterina Urban

प्रकाशित 2026-05-27

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Vijay D'Silva, Alessandra Palmigiano, Apostolos Tzimoulis, Caterina Urban

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप अपने एक मित्र को, जो केवल एक सरल, प्रतीकात्मक भाषा (अमूर्त दुनिया - abstract world) बोलता है, एक विशाल, अराजक शहर (कंक्रीट दुनिया - concrete world) का वर्णन करने की कोशिश कर रहे हैं। उस शहर में अनंत सड़कें, इमारतें और जटिल पैटर्न में चलते लोग हैं। आपका मित्र इतनी अधिक विस्तृत जानकारी को नहीं संभाल सकता, इसलिए आपको शहर के व्यवहार का सारांश देने का एक तरीका चाहिए बिना उसके बारे में झूठ बोले। यह एब्स्ट्रैक्ट इंटरप्रिटेशन (Abstract Interpretation) की मूल समस्या है: एक जटिल वास्तविकता का एक सुरक्षित, सरल मानचित्र बनाना।

यह शोध पत्र उस "व्याकरण" या तर्क (logic) को बनाने का एक नया तरीका प्रस्तावित करता है जो उस सरल मानचित्र का आधार होगा। केवल यह अनुमान लगाने के बजाय कि मानचित्र को किन नियमों का पालन करना चाहिए, लेखक एक यांत्रिक विधि (mechanical recipe) का सुझाव देते हैं जो एक सटीक तर्क प्रणाली उत्पन्न करती है जो मानचित्र से पूरी तरह मेल खाती है।

यहाँ उनके विचारों का रोजमर्रा के उदाहरणों के माध्यम से विवरण दिया गया है:

1. अनुवादक और मानचित्र (The Translator and the Map)

जटिल शहर को सभी संभावित परिदृश्यों के एक विशाल सेट के रूप में सोचें। "एब्स्ट्रैक्ट लैटिस (Abstract Lattice)" गुणों की एक सीमित, प्रबंधनीय चेकलिस्ट है (जैसे, "क्या ट्रैफिक लाइट लाल है?" "क्या पुल खुला है?")।

शहर को चेकलिस्ट से जोड़ने के लिए, आपको दो अनुवादकों की आवश्यकता है:

ऊपर की ओर अनुवादक (Abstraction/अमूर्तीकरण): एक अव्यवस्थित वास्तविक स्थिति को लेता है और कहता है, "यह श्रेणी A में फिट बैठता है।"
नीचे की ओर अनुवादक (Concretization/मूर्तता): चेकलिस्ट की एक श्रेणी को लेता है और कहता है, "यह उन सभी वास्तविक दुनिया की स्थितियों का प्रतिनिधित्व करता है जो यहाँ फिट बैठती हैं।"

लेखकों का लक्ष्य एक लॉजिक (Logic/तर्क) बनाना है (तर्क के लिए नियमों का एक सेट) जहाँ उस तर्क का "शब्दकोश" चेकलिस्ट के बिल्कुल समान हो। यदि चेकलिस्ट कहती है "A का अर्थ है B," तो तर्क को बिना किसी विफलता के सिद्ध करना चाहिए कि "A का अर्थ है B।"

2. कस्टम लॉजिक के लिए रेसिपी (The Recipe for a Custom Logic)

यह पत्र किसी भी सीमित चेकलिस्ट के लिए इस तर्क को बनाने का एक चरण-दर-चरण "नुस्खा" प्रदान करता है:

उपकरण चुनें: चेकलिस्ट को देखें। कौन से उपकरण (जैसे "AND," "OR," "NOT") शहर और चेकलिस्ट के बीच आगे-पीछे अनुवाद करते समय सही ढंग से काम करते हैं? केवल उन्हीं को रखें।
वस्तुओं को नाम दें: चेकलिस्ट की प्रत्येक वस्तु को एक नाम दें (जैसे बॉक्स पर लगा लेबल)।
नियम लिखें:
- यदि चेकलिस्ट कहती है "बॉक्स A, बॉक्स B का उपसमुच्चय (subset) है," तो तर्क में एक नियम लिखें: "यदि आपके पास A है, तो आपके पास B है।"
- यदि चेकलिस्ट कहती है "बॉक्स A और बॉक्स B को मिलाने से बॉक्स C बनता है," तो एक नियम लिखें: "A AND B बराबर C है।"
परिणाम: लेखक सिद्ध करते हैं कि यदि आप इस रेसिपी का पालन करते हैं, तो परिणामी तर्क प्रणाली सत्यनिष्ठ (sound) है (यह शहर के बारे में कभी झूठ नहीं बोलती) और पूर्ण (complete) है (यह चेकलिस्ट के बारे में हर उस चीज़ को सिद्ध कर सकती है जो सत्य है)।

"नाइव" (Naive) चेतावनी: लेखक स्वीकार करते हैं कि यह रेसिपी अखरोट तोड़ने के लिए हथौड़े का उपयोग करने जैसी है। यह किसी भी चेकलिस्ट के लिए काम करती है, लेकिन यह बहुत अधिक नियम बना सकती है, जिनमें से कुछ अनावश्यक हो सकते हैं। यह एक "ब्रूट फोर्स" (brate force) विधि है जो शुद्धता की गारंटी देती है लेकिन सबसे कुशल तरीका नहीं है।

3. "कार्टेशियन" बनाम "गैर-कार्टेशियन" पहेली (The "Cartesian" vs. "Non-Cartesian" Puzzle)

इसके बाद शोध पत्र एक विशिष्ट समस्या को देखता है: क्या होता है जब आपके पास दो चर (variables), जैसे $x$ और $y$ होते हैं?

कार्टेशियन दृष्टिकोण (ग्रिड): कल्पना करें कि एक ग्रिड है जहाँ आप $x$ और $y$ को स्वतंत्र रूप से जाँचते हैं। यह रसोई और बेडरूम के तापमान को स्वतंत्र रूप से जाँचने जैसा है। इसे संभालना आसान है क्योंकि पूरे ग्रिड के नियम रसोई और बेडरूम के नियमों के योग मात्र हैं।
गैर-कार्टेशियन दृष्टिकोण (आकार): कभी-कभी, $x$ और $y$ एक अजीब आकार में जुड़े होते हैं। उदाहरण के लिए, " $x$ और $y$ का योग 10 से कम होना चाहिए।" यह ग्रिड के आर-पार एक तिरछा कट बनाता है। आप केवल $x$ और $y$ को अलग-अलग नहीं देख सकते; आपको उस आकार को देखना होगा जो वे मिलकर बनाते हैं।

लेखक देखते हैं कि इन "अजीब आकारों" (गैर-कार्टेशियन एब्स्ट्रैक्शन) को एक साधारण ग्रिड में बदलने के बजाय उनके लॉजिक-बिल्डिंग रेसिपी के लिए संभालना वास्तव में आसान है। वे एक रणनीति का सुझाव देते हैं: पहले जटिल, जुड़े हुए आकारों के लिए सिद्धांत बनाएँ, और फिर देखें कि सरल ग्रिड का मामला उसमें कैसे फिट बैठता है।

4. अष्टकोण (Octagon) का उदाहरण

अपने सिद्धांत का परीक्षण करने के लिए, उन्होंने "अष्टकोण" (octagons - जैसे $x + y \geq 5$ ) नामक आकार के एक विशिष्ट प्रकार को देखा।

उन्होंने पाया कि जबकि आप आसानी से "NOT ( $x+y \geq 5$ )" कह सकते हैं, आप उनके विशिष्ट नियमों का उपयोग करके आसानी से "( $x+y \geq 5$ ) AND ( $x-y \geq 5$ )" नहीं कह सकते, क्योंकि उन दो आकारों का प्रतिच्छेदन (intersection) उनके सरल "लाइन" प्रारूप में फिट नहीं बैठता है।
इसने एक सीमा को उजागर किया: यदि आप केवल "NOT" की अनुमति देते हैं और "AND" की नहीं, तो आपका तर्क बहुत कमजोर है।
समाधान: उन्होंने "AND" और "OR" को मेटा-नियमों (नियमों के बारे में नियम) के रूप में अनुमति देने का प्रस्ताव दिया, न कि सख्त चेकलिस्ट के हिस्से के रूप में। यह उन्हें जटिल विरोधाभासों (जैसे यह सिद्ध करना कि एक स्थिति असंभव है) को संभालने में मदद करता है बिना उनके सिस्टम को तोड़े।

सारांश

सरल शब्दोंми में, यह शोध पत्र एक कस्टम भाषा बनाने का ब्लूप्रिंट है जो कंप्यूटर प्रोग्राम के सरलीकृत मॉडल से पूरी तरह मेल खाती है।

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

यह पत्र सभी सॉफ़्टवेयर बग्स को हल करने या भविष्य के चिकित्सा परिणामों की भविष्यवाणी करने का दावा नहीं करता है; यह सख्ती से वह गणितीय मशीनरी प्रदान करता है जो यह सुनिश्चित करती है कि सत्यापन के लिए उपयोग किए जाने वाले "सरलीकृत मानचित्रों" के पास तार्किक नियमों का एक सुसंगत और विश्वसनीय सेट हो।

तकनीकी सारांश: अमूर्त व्याख्या (Abstract Interpretation) के लिए एक प्रमाण-सिद्धांतिक दृष्टिकोण

समस्या विवरण
अमूर्त व्याख्या (Abstract interpretation) औपचारिक प्रोग्राम सत्यापन (formal program verification) के लिए एक आधारभूत सिद्धांत है, जिसे अनिर्णय योग्य (undecidable) या गणनात्मक रूप से कठिन समस्याओं को हल करने के लिए प्रोग्राम अर्थविज्ञान (program semantics) के सुदृढ़ सन्निकटन (sound approximations) उत्पन्न करने के लिए डिज़ाइन किया गया है। पारंपरिक रूप से, यह सिद्धांत एक जटिल मूर्त मॉडल (जैसे, प्रोग्राम निष्पादन का पॉवरसेट $P(\Sigma)$ ) को एक परिमित अमूर्त लैटिस (finite abstract lattice) $A$ से एक एडजॉइंट जोड़ी (adjoint pair) के माध्यम से जोड़ता है: एक कॉंक्रेटाइजेशन मैप (concretization map) $\gamma$ और एक एब्स्ट्रैक्शन मैप $\alpha$ । यद्यपि अमूर्त व्याख्या और तर्क (logic) के बीच संबंध को इसके inception के समय से ही पहचाना गया है, लेकिन इसे हाल ही में व्यवस्थित किया गया है। पूर्ववर्ती कार्यों (जैसे, [5], [3]) ने एक एब्स्ट्रैक्शन के लिए "आंतरिक तर्क" (internal logic) की अवधारणा पेश की और विशिष्ट एब्स्ट्रैक्शंस के अंतर्निहित तर्कों की पहचान की। हालाँकि, किसी भी मनमाने एब्स्ट्रैक्शन के लिए उसके आंतरिक तर्क और एक संगत प्रमाण प्रणाली (proof system) को उत्पन्न करने की एक सामान्य, प्रक्रियात्मक विधि एक खुला प्रश्न बना हुआ है।

कार्यप्रणाली (Methodology)
लेखक एक परिमित एब्स्ट्रैक्शन $A = (A, \sqsubseteq, Op_A)$ के अनुरूप एक तर्क $L_A$ उत्पन्न करने के लिए एक सामान्य प्रक्रिया प्रस्तावित करते हैं, जहाँ कॉंक्रेटाइजेशन मैप $\gamma: A \to (P(\text{Struct}), \subseteq, Op_c)$ है। कार्यप्रणाली इस प्रकार निर्मित होती है कि $L_A$ का लिंडेनबॉम-टार्शकी बीजगणक (Lindenbaum-Tarski algebra) अमूर्त बीजगणक $A$ के समरूप (isomorphic) हो। निर्माण निम्नलिखित चरणों के माध्यम से आगे बढ़ता है:

कनेक्टिव्स (Connectives): $L_A$ के तार्किक कनेक्टिव्स उन ऑपरेशन्स के रूप में परिभाषित किए जाते हैं जो कॉंक्रेटाइजेशन मैप $\gamma$ द्वारा संरक्षित (preserved) होते हैं। यदि $A$ एक परिमित डिस्ट्रीब्यूटिव लैटिस है, तो यह एक बी-हेयटिंग अलजेब्रा (bi-Heyting algebra) है, जिससे इम्प्लिकेशन (implication) और को-इम्प्लिकेशन (co-implication) उपलब्ध संभावित उम्मीदवार बन जाते हैं।
प्रेडिकेट्स (Predicates): प्रत्येक तत्व $a \in A$ के लिए, भाषा में एक यूनरी प्रेडिकेट सिंबल $a(x)$ जोड़ा जाता है।
इंट्रोडक्शन रूल्स (Introduction Rules): प्रत्येक कनेक्टिव जो $\gamma$ द्वारा संरक्षित है, उसके लिए उपयुक्त इंट्रोडक्शन रूल्स जोड़े जाते हैं।
एक्सिओमैटिक रूल्स (Axiomatic Rules):
- बाइनरी कनेक्टिव $\star$ के लिए जहाँ $a \star b = c$ , नियम $a(x) \star b(x) \dashv\vdash c(x)$ जोड़ा जाता है।
- यूनरी कनेक्टिव $\star$ के लिए जहाँ $\star a = b$ , नियम $\star a(x) \dashv\vdash b(x)$ जोड़ा जाता है।
- ऑर्डर रिलेशंस के लिए जहाँ $a \leq b$ , नियम $a(x) \vdash b(x)$ जोड़ा जाता है।

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

प्रमुख परिणाम और सैद्धांतिक निष्कर्ष
यह शोध पत्र निर्मित तर्क $L_A$ के संबंध में तीन प्राथमिक लेम्मा (lemmas) स्थापित करता है:

सुदृढ़ता (Soundness - Lemma 1): तर्क $L_A$ , कॉंक्रेटाइजेशन $\gamma$ के प्रति सुदृढ़ है। इसे प्रमाण की गहराई (proof depth) पर इंडक्शन के माध्यम से सिद्ध किया गया है, जो इस तथ्य पर निर्भर करता है कि $\gamma$ कनेक्टिव्स को संरक्षित करता है और एक्सिओम्स मूर्त बीजगणक (concrete algebra) में संबंधों को दर्शाते हैं।
समरूपता (Isomorphism - Lemma 2): $L_A$ का लिंडेनबॉम-टार्शकी बीजगणक $L$ , अमूर्त बीजगणक $A$ के समरूप है। मैपिंग $e: A \to L$ , जो $e(a) = [a(x)]$ (प्रेडिकेट का इक्विवेलेंस क्लास) द्वारा परिभाषित है, एक सर्जेक्टिव, इंजेक्टिव ऑर्डर-एम्बेडिंग और होमॉमॉर्फिज्म के रूप में दिखाई गई है।
पूर्णता (Completeness - Lemma 3): यदि $\gamma$ एक ऑर्डर-एम्बेडिंग है, तो $L_A$ , कॉंक्रेटाइजेशन के प्रति पूर्ण है। यह परिणाम $\gamma$ को एक इंजेक्टिव राइट एडजॉइंट से केवल एक ऑर्डर-एम्बेडिंग तक सरल बनाकर पिछले निष्कर्षों (विशेष रूप से [5, Proposition 5]) को सुदृढ़ करता है।

केस स्टडीज और विस्तार
यह शोध पत्र विशिष्ट परिदृश्यों पर इस ढांचे को लागू करता है:

कार्टेशियन उत्पाद (Cartesian Products): कार्यप्रणाली $n$ वेरिएबल्स के लिए सामान्यीकृत होती है। जब प्रेडिकेट्स को सिंगल-वेरिएबल प्रेडिकेट्स के कंजंक्शन (conjunctions) द्वारा बनाया जाता है ( $\phi_i(x) = \bigwedge \psi^i_k(x_k)$ ), तो परिणामी लैटिस सिंगल-वेरिएबल लैटिस का कार्टेशियन उत्पाद होता है। कॉंक्रेटाइजेशन मैप $n$ -डायमेंशनल रेक्टेंगल को सेट्स असाइन करने के अनुरूप होता है।
ऑक्टागन्स का तर्क (Logic of Octagons): लेखक $\pm x \pm y \geq c$ के रूप में प्रेडिकेट्स का विश्लेषण करते हैं। वे देखते हैं कि जबकि $\gamma$ नेगेशन (negation) को संरक्षित करता है, यह कंजंक्शन या डिसजंक्शन को संरक्षित नहीं करता है (क्योंकि ऐसे प्रेडिकेट्स का इंटरसेक्शन अक्सर उन ज्यामितीय आकृतियों में बदल जाता है जो लैटिस में एकल प्रेडिकेट द्वारा प्रतिनिधित्व योग्य नहीं होती हैं)। फलस्वरूप, केवल क्लासिकल नेगेशन पर निर्भर तर्क कमजोर है। इसे संबोधित करने के लिए, लेखक अनुक्रमों (sequents) को संभालने के लिए कंजंक्शन और डिसजंक्शन को मेटा-कनेक्टिव्स के रूप में उपयोग करने का प्रस्ताव करते हैं, साथ ही यह भी नोट करते हैं कि ऑक्टागन्स की लैटिस संरचना में मीट- और जॉइन-इरेड्यूसिबल एलिमेंट्स (टॉप और बॉटम को छोड़कर) होते हैं, जो एक इनवोल्यूटिव नेगेशन (involutive negation) की अनुमति देते हैं।

महत्व और दावे
यह शोध पत्र स्वयं को चल रहे कार्य के प्रारंभिक परिणामों और अवलोकनों के संग्रह के रूप में प्रस्तुत करता है। इसका प्राथमिक महत्व निम्नलिखित में निहित है:

सामान्यीकरण (Generalization): [3] के परिणामों को किसी भी परिमित एब्स्ट्रैक्शन के आंतरिक तर्क को उत्पन्न करने के लिए एक सामान्य प्रक्रिया प्रदान करने हेतु विस्तारित करना।
व्यवस्थित निर्माण (Systematic Construction): एक ऐसी प्रमाण प्रणाली उत्पन्न करने के लिए एक ठोस, भले ही नाइव, एल्गोरिदम प्रदान करना जहाँ तर्क की बीजगणिक संरचना गारंटी के साथ अबस्ट्रैक्ट डोमेन के समरूप हो।
सिद्धांत का परिशोधन (Refinement of Theory): कॉंक्रेटाइजेशन मैप्स के ऑर्डर-थ्योरेटिक गुणों और संबद्ध तर्क की पूर्णता के बीच सैद्धांतिक संबंध को मजबूत करना।

लेखक स्पष्ट रूप से कहते हैं कि वर्तमान प्रक्रिया अक्षम है और गणनात्मक सीमाओं की अनदेखी करती है, जो इस कार्य को एक तैयार-उपयोग (ready-to-use) सत्यापन उपकरण के बजाय, इस बात के लक्षण वर्णन की ओर एक आधारभूत कदम के रूप में फ्रेम करता है कि कौन से गुण गैर-कार्टेशियन एब्स्ट्रैक्शंस से कार्टेशियन मामलों में "परकोलेट" (percolate) होते हैं।

1. अनुवादक और मानचित्र (The Translator and the Map)

2. कस्टम लॉजिक के लिए रेसिपी (The Recipe for a Custom Logic)

3. "कार्टेशियन" बनाम "गैर-कार्टेशियन" पहेली (The "Cartesian" vs. "Non-Cartesian" Puzzle)

4. अष्टकोण (Octagon) का उदाहरण

सारांश

इसी तरह के और पेपर