💻 computer science

Games, mobile processes, and functionss -- alternating, concurrent, and well-bracketed semantics

यह शोध पत्र विभिन्न लेबल वाले ट्रांज़िशन सिस्टम्स (labeled transition systems) में उनके प्रेरित तुल्यात्मकताओं (induced equivalences) के संयोग को प्रदर्शित करके, इंटरनल $\pi$ -कैलकुलस में मिलर के $\lambda$ -कैलकुलस के एनकोडिंग और ऑपरेशनल गेम सेमेंटिक्स के बीच एक घनिष्ठ संबंध स्थापित करता है, जिससे स्टोर वाले $\lambda$ -टर्म्स के लिए पूर्ण अमूर्तता (full abstraction) प्राप्त करने हेतु दोनों मॉडलों के बीच 'अप-टू' (up-to) विधियों और संगतता परिणामों (congruence results) जैसी तकनीकों के हस्तांतरण को सक्षम बनाया जा सके।

मूल लेखक: Guilhem Jaber, Davide Sangiorgi

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

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

CC BY 4.0

मूल लेखक: Guilhem Jaber, Davide Sangiorgi

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

कल्पना कीजिए कि आप यह समझने की कोशिश कर रहे हैं कि एक कंप्यूटर प्रोग्राम कैसे काम करता है। आपके पास उसके व्यवहार का वर्णन करने के लिए दो अलग-अलग "भाषाएँ" या "नक्शे" हैं:

"प्रोसेस" मैप (π-कैलकुलस): इसे एक व्यस्त रेलवे स्टेशन के रूप में सोचें। प्रोग्राम ट्रेनें हैं और वे एक-दूसरे को नोट्स (नाम/चैनल) पास करके संवाद करते हैं। वे एक साथ कई ट्रेनें चला सकते हैं और नोट्स को जटिल, ओवरलैपिंग तरीकों से पास किया जा सकता है।
"गेम" मैप (ऑपरेशनल गेम सिमेंटिक्स): इसे एक टेनिस मैच के रूप में सोचें। प्रोग्राम "खिलाड़ी" (Player) है, और बाहरी दुनिया (उपयोगकर्ता या अन्य प्रोग्राम) "प्रतिद्वंद्वी" (Opponent) है। वे बारी-बारी से गेंद को आगे-पीछे मारते हैं। खेल के नियम तय करते हैं कि खिलाड़ी कब और कैसे गेंद मार सकता है।

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

यहाँ लेखकों द्वारा किए गए कार्यों का सरल उपमाओं के साथ विवरण दिया गया है:

1. जब दो नक्शे मिलते हैं

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

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

2. गेम के तीन संस्करण

यह शोध पत्र गेम मैप के तीन अलग-अलग "नियमसेट्स" की जांच करता है कि क्या वे परिणाम बदलते हैं:

अल्टरनेटिंग (कठोर बारी-बारी): एक औपचारिक बहस की तरह। पहले खिलाड़ी बोलता है, फिर प्रतिद्वंद्वी बोलता है, फिर खिलाड़ी। कोई व्यवधान नहीं।
कन्करेंट (एक पार्टी): एक कॉकटेल पार्टी की तरह। कई बातचीत एक साथ हो सकती हैं। खिलाड़ी एक चीज़ के बारे में प्रतिद्वंद्वी से बात कर सकता है जबकि प्रतिद्वंद्वी दूसरी चीज़ के बारे में पूछ रहा हो।
वेल-ब्रैकेटेड (एक स्टैक): प्लेटों के ढेर की तरह। आप केवल ऊपर वाली प्लेट ही निकाल सकते हैं। आप बीच से कोई प्लेट नहीं उठा सकते। यह "कंट्रोल ट्रिक्स" को रोकता है जहाँ आप कोड में इधर-उधर कूद जाते हैं।

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

3. औजार उधार लेना ("अप-टू" ट्रिक)

शोध पत्र का सबसे दिलचस्प हिस्सा यह है कि कैसे उन्होंने दोनों नक्शों के संबंध का उपयोग कठिन समस्याओं को हल करने के लिए किया।

उपमा: कल्पना कीजिए कि आप यह सिद्ध करने की कोशिश कर रहे हैं कि दो जटिल पहेलियाँ एक ही हैं। "प्रोसेस मैप" (ट्रेन स्टेशन) के पास एक विशेष उपकरण है जिसे "अप-टू तकनीकें" (Up-To Techniques) कहा जाता है। यह उपकरण एक "चीट कोड" की तरह है जो आपको छोटे, दोहराव वाले विवरणों को अनदेखा करने और केवल बड़ी तस्वीर पर ध्यान केंद्रित करने की अनुमति देता है, जिससे प्रमाण बहुत आसान हो जाते हैं।
चाल: "गेम मैप" (टेनिस मैच) के पास अभी तक यह चीट कोड नहीं था। क्योंकि लेखकों ने सिद्ध किया कि दोनों नक्शे समान हैं, उन्होंने प्रोसेस मैप से इस चीट कोड को गेम मैप में आयात (import) कर लिया।
परिणाम: उन्होंने "अप-टू कंपोजिशन" (Up-To Composition) नामक एक नई, शक्तिशाली विधि बनाई। यह उन्हें एक विशाल, जटिल गेम कॉन्फ़िगरेशन को छोटे, प्रबंधनीय टुकड़ों में तोड़ने, टुकड़ों की समानता सिद्ध करने और तुरंत यह जानने की अनुमति देता है कि पूरा हिस्सा भी समान है। यह एक पूरे ऑर्केस्ट्रा के सुर में होने को सिद्ध करने जैसा है—हर एक नोट सुनने के बजाय, केवल प्रत्येक अनुभाग (स्ट्रिंग्स, ब्रास, वुडविंड्स) के सुर को सिद्ध करके।

4. "कम्प्लीट ट्रेस" (खत्म हुआ खेल)

लेखकों ने "कम्प्लीट ट्रेसेस" (Complete Traces) पर भी गौर किया।

उपमा: टेनिस का खेल देखते हुए कल्पना करें। एक "ट्रेस" हिट्स का क्रम है। एक "कम्प्लीट ट्रेस" वह खेल है जो अंतिम अंक बनने और मैच समाप्त होने तक चलता है।
निष्कर्ष: उन्होंने दिखाया कि यदि आप केवल उन खेलों की परवाह करते हैं जो पूरी तरह से समाप्त होते हैं (कोई अनंत लूप नहीं), तो स्ट्रिक्ट टर्न-टेकिंग, पार्टी, और स्टैक के नियम बिल्कुल एक ही प्रकार के समाप्त खेलों की सूची उत्पन्न करते हैं। यह एक बड़ी बात है क्योंकि इसका मतलब है कि आप सबसे जटिल व्यवहारों को समझने के लिए सबसे सरल नियमों (स्टैक) का उपयोग कर सकते हैं, जब तक कि प्रोग्राम समाप्त हो जाता है।

सारांश

संक्षेप में, यह शोध पत्र एक सेतु (bridge) है। यह कंप्यूटर प्रोग्रामों के सोचने के दो प्रमुख तरीकों को जोड़ता है:

"प्रोसेस" दृष्टिकोण (एल्जेब्रा और कई चीजों को एक साथ संभालने के लिए अच्छा)।
"गेम" दृष्टिकोण (यह समझने के लिए कि एक प्रोग्राम दुनिया के साथ कैसे इंटरैक्ट करता है)।

इन दोनों को समान सिद्ध करके, लेखकों ने वैज्ञानिकों को सक्षम बनाया है:

गेम समस्याओं को हल करने के लिए प्रोसेस दुनिया के शक्तिशाली गणितीय उपकरणों का उपयोग करने के लिए।
यह सिद्ध करने के लिए कि "गेम" खेलने के विभिन्न तरीके (सख्त बनाम अराजक) वास्तव में एक ही परिणाम की ओर ले जाते हैं।
दो जटिल प्रोग्रामों की समानता को छोटे टुकड़ों में तोड़कर सिद्ध करने का एक नया, आसान तरीका बनाने के लिए।

उन्होंने यह "कॉल-बाय-वैल्यू" के लिए किया और यह भी बताया कि यह "कॉल-बाय-नेम" (कोड का मूल्यांकन करने का एक थोड़ा अलग तरीका) के लिए कैसे काम करता है, यह दिखाते हुए कि यह सेतु कंप्यूटेशन की मौलिक प्रकृति को समझने के लिए मजबूत और उपयोगी है।

तकनीकी सारांश: गेम्स, मोबाइल प्रोसेसेज और फंक्शन्स

समस्या विवरण (Problem Statement)
यह शोध पत्र उच्च-क्रम भाषाओं (higher-order languages) के दो प्रमुख सिमेंटिक फ्रेमवर्क्स: ऑपरेशनल गेम सेमेंटिक्स (OGS) और $\pi$ -कैलकुलस (विशेष रूप से इंटरनल $\pi$ -कैलकुलस, $I\pi$ ) के बीच एक सटीक, औपचारिक पत्राचार (correspondence) की कमी को संबोधित करता है। जबकि दोनों मॉडल $\lambda$ -कैलकुलस टर्म्स के व्यवहार को लक्षणित करने के लिए उपयोग किए जाते हैं, वे अपने निर्माण में काफी भिन्न हैं। OGS गहन (intensional) मॉडल प्रदान करता है जहाँ प्रोग्राम के अर्थ (denotations) एनवायरनमेंट के साथ अंतःक्रियाओं का प्रतिनिधित्व करने वाले कॉन्फ़िगरेशन से कंपोजिशनल रूप से प्राप्त किए जाते हैं, जो अक्सर अल्टरनेशन (alternation) और वेल-ब्रैकेटिंग (well-bracketing) जैसी विशेषताओं पर जोर देते हैं। इसके विपरीत, $\pi$ -कैलकुलस मिलनर के एनकोडिंग के माध्यम से फंक्शन्स को प्रोसेस के रूप में मॉडल करता है, जो बीजगणितीय संरचनाओं और बिज़िमिलैरिटी (bisimilarity) जैसे प्रोसेस इक्विवेलेंस का लाभ उठाता है। लेखक अनटाइप्ड कॉल-बाय-वैल्यू $\lambda$ -कैलकुलस ( $\Lambda_V$ ) के लिए इन मॉडल्स के बीच एक सटीक ऑपरेशनल पत्राचार स्थापित करने का लक्ष्य रखते हैं, यह प्रदर्शित करते हुए कि वे समान व्यवहार संबंधी तुल्यता (behavioral equivalences) उत्पन्न करते हैं और एक मॉडल की तकनीकों को दूसरे में स्थानांतरित किया जा सकता है।

कार्यप्रणाली (Methodology)
लेखक तीन अलग-अलग OGS वेरिएंट्स और दो $I\pi$ वेरिएंट्स के तहत $\Lambda_V$ के ऑपरेशनल सेमान्टिक्स के तुलनात्मक विश्लेषण का उपयोग करते हैं:

OGS वेरिएंट्स:
- अल्टरनेटिंग OGS (A-OGS): प्रोग्राम (प्लेयर) और एनवायरनमेंट (अपोनेंट) के बीच सख्त अल्टरनेशन लागू करता है।
- कन्करेंट OGS (C-OGS): एक कॉन्फ़िगरेशन के भीतर कई टर्म्स को समानांतर (parallel) रूप से चलने की अनुमति देता है।
- वेल-ब्रैकेटेड OGS (WB-OGS): कंटीन्यूएशंस (continuations) पर एक स्टैक अनुशासन लागू करता है, जो अपोनेंट को लास्ट-इन-फर्स्ट-आउट (LIFO) क्रम में उत्तर देने के लिए प्रतिबंधित करता है।
$I\pi$ वेरिएंट्स:
- स्टैंडर्ड $I\pi$ LTS: इंटरनल $\pi$ -कैलकुलस के लिए मानक लेबल ट्रांजिशन सिस्टम।
- आउटपुट-प्रायोरिटाइज्ड $I\pi$ LTS (opLTS): एक प्रतिबंधित LTS जहाँ इनपुट क्रियाएं केवल तभी दृश्य होती हैं जब कोई आउटपुट या आंतरिक क्रिया लंबित न हो, जो अनुक्रमिक बाधाओं (sequentiality constraints) को लागू करती है।

मुख्य कार्यप्रणाली OGS कॉन्फ़िगरेशन (एनवायरनमेंट्स और रनिंग टर्म्स सहित) से $I\pi$ प्रोसेसेज तक एक मैपिंग ( $\mathcal{V}$ ) को परिभाषित करना शामिल है। यह मैपिंग मिलनर के $\lambda$ -टर्म्स के एनकोडिंग का विस्तार करती है। लेखक यह सिद्ध करने के लिए ऑपरेशनल पत्राचार प्रमेय (operational correspondence theorems) का उपयोग करते हैं कि OGS में ट्रांजिशन विशिष्ट स्थितियों के तहत $I\pi$ में ट्रांजिशन के अनुरूप होते हैं (और इसके विपरीत)। महत्वपूर्ण रूप से, वे $I\pi$ से आयात की गई "अप-टू" तकनीकों (विशेष रूप से अप-टू कॉन्टेक्स्ट और अप-टू कंपोजिशन) का उपयोग बिज़िमिलैरिटी प्रमाणों को सरल बनाने के लिए करते हैं। वे ट्रैसेस के इंटरलीविंग को मॉडल करने के लिए OGS कॉन्फ़िगरेशन के लिए एक टेंसर प्रोडक्ट भी पेश करते हैं, जो प्रोसेस कैलकुली में पैरेलल कंपोजिशन के समान है।

प्रमुख योगदान (Key Contributions)

ऑपरेशनल पत्राचार (Operational Correspondence): शोध पत्र निम्नलिखित के बीच सटीक ऑपरेशनल पत्राचार स्थापित करता है:
- आउटपुट-प्रायोरिटाइज्ड LTS (opLTS) के तहत A-OGS और $I\pi$ ।
- स्टैंडर्ड LTS के तहत C-OGS और $I\pi$ ।
  ये पत्राचार स्ट्रॉन्ग और वीक ट्रांजिशन दोनों के लिए मान्य हैं, जो आंतरिक रिडक्शन को ध्यान में रखने के लिए एक्सपेंशन रिलेशन ( $\lesssim$ ) का उपयोग करते हैं।
इक्विवेलेंस कोइंसिडेंस (Equivalence Coincidence): लेखक सिद्ध करते हैं कि इन सभी मॉडल्स द्वारा $\lambda$ -टर्म्स पर प्रेरित व्यवहार संबंधी तुल्यताएँ (behavioral equivalences) मेल खाती हैं। विशेष रूप से:
- A-OGS, C-OGS, और $I\pi$ (दोनों स्टैंडर्ड और opLTS) में ट्रेस इक्वैलेंस और बिज़िमिलैरिटी, $\Lambda_V$ टर्म्स पर एक ही संबंध को परिभाषित करते हैं।
- इस प्रेरित तुल्यता को लैसन के ईगर नॉर्मल-फॉर्म बिज़िमिलैरिटी (जिसे अक्सर लैसन के ट्रीज़ के रूप में विज़ुअलाइज़ किया जाता है) के रूप में पहचाना गया है।
- पूर्ण ट्रैसेस (वे ट्रैसेस जो समाप्त होने वाली अंतःक्रियाओं का वर्णन करते हैं) के लिए, अल्टरनेटिंग, कन्करेंट, और वेल-ब्रैकेटेड OGS का सेमान्टिक्स भी मेल खाता है।
तकनीकों का स्थानांतरण (Transfer of Techniques):
- अप-टू कंपोजिशन: लेखक $I\pi$ से "अप-टू कॉन्टेक्स्ट" और "एक्सपेंशन" तकनीकों को OGS में आयात करते हैं। वे OGS के लिए एक नई तकनीक जिसे "अप-टू कंपोजिशन" कहा जाता है, परिभाषित करते हैं, जो बिज़िमिलैरिटी प्रमाणों को एक जटिल कॉन्फ़िगरेशन को मौलिक घटकों (सिंगलटन कॉन्फ़िगरेशन) में विभाजित करने और उन्हें स्वतंत्र रूप से तर्क करने की अनुमति देती है।
- कंग्रुएंस और कंपोजिशनैलिटी: $I\pi$ के साथ पत्राचार का लाभ उठाते हुए, पेपर OGS के लिए कंग्रुएंस गुणों (जैसे, यदि $M \sim N$ , तो $C[M] \sim C[N]$ ) को व्युत्पन्न करता है और कॉन्फ़िगरेशन के लिए एक टेंसर प्रोडक्ट को परिभाषित करता है जो ट्रैसेस के इंटरलीविंग्स की गणना करता है।
स्टोर के लिए फुल एब्सट्रैक्शन (Full Abstraction for Store): वेल-ब्रैकेटेड OGS में पूर्ण ट्रैसेस का अध्ययन म्यूटेबल स्टोर वाले $\lambda$ -कैलकुली के कॉन्टेक्स्टुअल इक्विवेलेंस से जुड़ा हुआ है। पेपर दिखाता है कि $\lambda$ -टर्म्स का $I\pi$ में एनकोडिंग एक स्टोर के साथ विस्तारित $\lambda$ -कैलकुलस में लिखे गए कॉन्टेक्स्ट्स के सापेक्ष एक फुल एब्सट्रैक्शन परिणाम देता है।
कॉल-बाय-नेम एक्सटेंशन (Call-by-Name Extension): पेपर एक समान पत्राचार का खाका प्रस्तुत करता है, यह दिखाते हुए कि प्रेरित तुल्यता लेवी-लोंगो ट्रीज़ (Lévy-Longo Trees) के साथ मेल खाती है।

परिणाम (Results)

थ्योरम 6.7 और 7.3: संबंधित LTSs के तहत OGS कॉन्फ़िगरेशन और $I\pi$ प्रोसेसेज के बीच ऑपरेशनल पत्राचार स्थापित करते हैं।
कोरोलरी 6.12 और 7.7: यह प्रदर्शित करते हैं कि $\lambda$ -टर्म्स के लिए A-OGS, C-OGS, और $I\pi$ (दोनों स्टैंडर्ड और opLTS) में ट्रेस इक्वैलेंस और बिज़िमिलैरिटी समान हैं।
थ्योरम 8.1: "अप-टू कंपोजिशन" तकनीक का उपयोग करके सीधे तौर पर सिद्ध करता है कि C-OGS बिज़िमिलैरिटी, लैसन के ईगर नॉर्मल-फॉर्म बिज़िमिलैरिटी के साथ मेल खाती है।
थ्योरम 12.2: सिद्ध करता है कि पूर्ण-ट्रेस इक्वैलेंस, WB-OGS, A-OGS, और C-OGS के बीच समान है।
लेम्मा 7.16 और थ्योरम 7.17: C-OGS के लिए "बिज़िमिलिएशन अप-टू रिडक्शन एंड कंपोजिशन" की सुदृढ़ता (soundness) को सिद्ध करते हैं, जिसे $I\pi$ से आयात किया गया है।

महत्व (Significance)
पेपर का दावा है कि इसका प्राथमिक महत्व OGS और $\pi$ -कैलकुलस के बीच एक "सटीक और गहरा पत्राचार" स्थापित करने में निहित है। यह संबंध दोनों मॉडल्स के बीच परिणामों और तकनीकों के स्थानांतरण की अनुमति देता है। विशेष रूप से:

यह OGS को $\pi$ -कैलकुलस की समृद्ध बीजगणितीय संरचना और शक्तिशाली प्रमाण तकनीकों (जैसे अप-टू तकनीक) का लाभ उठाने की अनुमति देता है, जिन्हें सीधे गेम-थ्योरेटिक फ्रेमवर्क के भीतर विकसित करना अक्सर कठिन होता है।
यह $\pi$ -कैलकुलस को सोर्स लैंग्वेज के करीब होने और विशिष्ट कंप्यूटेशनल इफेक्ट्स (जैसे कंट्रोल ऑपरेटर्स या स्टोर) को मॉडल करने की लचीलापन का लाभ उठाने की अनुमति देता है।
यह $\lambda$ -कैलकुलस के लिए एक एकीकृत दृष्टिकोण प्रदान करता है, यह दिखाते हुए कि OGS में "सेमान्टिक क्यूब" की शर्तें (अल्टरनेशन, वेल-ब्रैकेटिंग) और $I\pi$ में अनुक्रमिक बाधाएं (opLTS के माध्यम से) एक ही सिक्के के दो पहलू हैं, जो दोनों एक ही अंतर्निहित व्यवहार संबंधी तुल्यता (कॉल-बाय-वैल्यू के लिए लैसन के ट्रीज़) को लक्षणित करते हैं।

लेखक नोट करते हैं कि हालांकि गेम सेमान्टिक्स और प्रोसेस कैलकुली के बीच समानताएं पहले भी खोजी गई हैं (उदाहरण के लिए, रणनीतियों को प्रोसेसेज में अनुवादित करना), यह कार्य उनके फंक्शन के प्रत्यक्ष तुलना और नए परिणाम प्राप्त करने के लिए प्रमाण तकनीकों के व्यवस्थित स्थानांतरण में विशिष्ट है।