एक बेकार भाषा कैसे काम करती है?

Question

मैंने बेकार भाषाओं के बारे में सुना है। हालांकि मुझे कोई जानकारी नहीं है कि ऐसी भाषा कैसे लागू की जाएगी। क्या कोई समझा सकता है?

Answer 1

हमारे पास आधुनिक ऑपरेटिंग सिस्टम (विंडोज़, लिनक्स) "बड़े स्टैक मॉडल" के साथ काम करते हैं। और वह मॉडल गलत है, कभी-कभी, और "बेकार" भाषाओं की आवश्यकता को प्रेरित करता है।

"बड़ा स्टैक मॉडल" मानता है कि एक संकलित प्रोग्राम स्टैक पॉइंटर (और वैकल्पिक स्टैक फ्रेम पॉइंटर) वाले रजिस्टरों को समायोजित करने के लिए मशीन निर्देशों का उपयोग करके स्मृति के एक संगत क्षेत्र में फ़ंक्शन कॉल के लिए "स्टैक फ्रेम" आवंटित करेगा। । यह ढेर के लिए एक बड़ा, संगत क्षेत्र होने की कीमत पर तेजी से कार्य कॉल/वापसी की ओर जाता है। चूंकि इन आधुनिक ओएस के तहत चलने वाले सभी कार्यक्रमों का 99.99% बड़े स्टैक मॉडल, कंपाइलर, लोडर और यहां तक ​​कि ओएस को इस स्टैक क्षेत्र के बारे में "पता" के साथ अच्छी तरह से काम करता है।

ऐसे सभी अनुप्रयोगों में एक आम समस्या है, "मेरा ढेर कितना बड़ा होना चाहिए?"। स्मृति गंदगी के साथ सस्ता होने के कारण, ज्यादातर क्या होता है कि स्टैक के लिए एक बड़ा हिस्सा अलग किया जाता है (एमएस डिफ़ॉल्ट रूप से 1 एमबी), और सामान्य अनुप्रयोग कॉल संरचना इसे कभी भी उपयोग करने के करीब कभी नहीं मिलती है। लेकिन यदि कोई एप्लिकेशन इसका उपयोग करता है, तो यह एक अवैध स्मृति संदर्भ के साथ मर जाता है ("मुझे खेद है डेव, मैं ऐसा नहीं कर सकता"), इसके ढेर के अंत तक पहुंचने के आधार पर।

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

1) कार्यक्रम गहरी प्रत्यावर्तन विशिष्ट समस्या यह सुलझाने है, यह एक "बड़ा ढेर" क्षेत्र preallocate बहुत मुश्किल है पर निर्भर करता है:

वहाँ ढेर फ्रेम के लिए ढेर आवंटन प्रयोग करने के लिए कई कारण हैं अग्रिम में क्योंकि आवश्यक आकार ज्ञात नहीं है। कोई भी अजीब तरह से फंक्शन कॉल की व्यवस्था कर सकता है यह देखने के लिए कि क्या पर्याप्त स्टैक बाकी है, और यदि नहीं, तो एक बड़ा हिस्सा पुनः आवंटित करें, पुराने स्टैक की प्रतिलिपि बनाएं और सभी पॉइंटर्स को ढेर में समायोजित करें; यह इतना अजीब है कि मुझे किसी भी कार्यान्वयन की जानकारी नहीं है। स्टैक फ़्रेम आवंटित करने का अर्थ है कि एप्लिकेशन को कभी भी माफ करना नहीं है जब तक कि सचमुच कोई आवंटित स्मृति शेष नहीं है।

2) प्रोग्राम फोर्क सबटास्क। प्रत्येक उपटस्क के लिए अपने स्वयं के ढेर की आवश्यकता होती है, और इसलिए प्रदान किए गए "बड़े ढेर" का उपयोग नहीं कर सकते हैं। इसलिए, प्रत्येक को प्रत्येक उपटस्क के लिए ढेर आवंटित करने की आवश्यकता है। यदि आपके पास हजारों संभावित उप-कार्य हैं, तो आपको अब हजारों "बड़े ढेर" की आवश्यकता हो सकती है, और स्मृति की मांग अचानक हास्यास्पद हो जाती है। स्टैक फ्रेम आवंटित करने से यह समस्या हल हो जाती है। अक्सर उप-कार्य "ढेर" लेक्सिकल स्कोपिंग को लागू करने के लिए मूल कार्यों को संदर्भित करता है; subtasks कांटा के रूप में, "substacks" का एक पेड़ बनाया जाता है जिसे "कैक्टस स्टैक" कहा जाता है।

3) आपकी भाषा में निरंतरताएं हैं। इनकी आवश्यकता है कि मौजूदा फ़ंक्शन के लिए दृश्यमान अक्षीय क्षेत्र में डेटा किसी भी तरह बाद में पुन: उपयोग के लिए संरक्षित किया जाए। इसे पेरेंट स्टैक फ्रेम की प्रतिलिपि बनाकर, कैक्टस स्टैक पर चढ़कर और आगे बढ़कर कार्यान्वित किया जा सकता है।

PARLANSE प्रोग्रामिंग लैंगेज I लागू 1) और 2)। मैं 3 पर काम कर रहा हूँ)।

Answer 2

स्टैकलेस वातावरण में मैं (कमरिंग मशीन, असेंबली और ब्रेनफक) से अधिक या कम परिचित हूं, यह आपके स्वयं के ढेर को लागू करना आम है। भाषा में बने ढेर के बारे में कुछ भी मौलिक नहीं है।

इनमें से सबसे व्यावहारिक में, असेंबली में, आप बस आपके लिए उपलब्ध स्मृति का एक क्षेत्र चुनते हैं, स्टैक रजिस्टर को नीचे इंगित करने के लिए सेट करें, फिर अपने धक्का और पॉप को लागू करने के लिए वृद्धि या कमी करें।

संपादित करें: मुझे पता है कि कुछ आर्किटेक्चर में समर्पित ढेर हैं, लेकिन वे आवश्यक नहीं हैं।

Answer 3

Stackless Python अभी भी एक अजगर ढेर है (हालांकि यह पूंछ कॉल अनुकूलन और अन्य कॉल फ्रेम विलय चाल हो सकता है), लेकिन यह पूरी तरह से दुभाषिये की सी ढेर से तलाक है।

हास्केल (आमतौर पर लागू) के पास कॉल स्टैक नहीं है; मूल्यांकन graph reduction पर आधारित है।

Answer 4

http://www.linux-mag.com/cache/7373/1.html पर भाषा ढांचे तोता के बारे में एक अच्छा लेख है। तोता कॉलिंग के लिए ढेर का उपयोग नहीं करता है और यह आलेख तकनीक को थोड़ा सा समझाता है।

Answer 5

एक आसान इस लेख पर निरंतरता का विवरण को समझने के लिए है: http://www.defmacro.org/ramblings/fp.html

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

Answer 6

मुझे प्राचीन कॉल करें, लेकिन मुझे याद है जब फोरट्रान मानकों और कोबोल ने रिकर्सिव कॉल का समर्थन नहीं किया था, और इसलिए एक ढेर की आवश्यकता नहीं थी। दरअसल, मुझे सीडीसी 6000 सीरीज़ मशीनों के लिए कार्यान्वयन याद आते हैं जहां स्टैक नहीं था, और अगर आप एक सबराउटिन को बार-बार कॉल करने का प्रयास करते हैं तो फोरट्रान अजीब चीजें करेगा।

रिकॉर्ड के लिए, कॉल-स्टैक के बजाय, सीडीसी 6000 श्रृंखला निर्देश सेट ने आरजे निर्देश का उपयोग एक सबराउटिन को कॉल करने के लिए किया था। इसने वर्तमान पीसी मान को कॉल लक्ष्य स्थान पर सहेजा और फिर उसके बाद के स्थान पर शाखाएं। अंत में, एक subroutine कॉल लक्ष्य स्थान पर एक अप्रत्यक्ष कूद प्रदर्शन करेगा। वह पुनः लोड किया गया पीसी, प्रभावी ढंग से कॉलर पर लौट रहा है।

जाहिर है, यह रिकर्सिव कॉल के साथ काम नहीं करता है। (और मेरी यादें यह है कि यदि आपने रिकर्सन का प्रयास किया है तो सीडीसी फोरट्रान IV कंपाइलर टूटा कोड उत्पन्न करेगा ...)

Answer 7

अगर मैं गलत हूं तो कृपया मुझे सही करने के लिए स्वतंत्र महसूस करें, लेकिन मुझे लगता है कि ढेर पर स्मृति आवंटित करना प्रत्येक फंक्शन कॉल फ्रेम के लिए चरम स्मृति थ्रैशिंग का कारण बनता है। इस स्मृति को प्रबंधित करने के बाद ऑपरेटिंग सिस्टम करता है। मुझे लगता है कि इस मेमोरी थ्रैशिंग से बचने का तरीका कॉल फ्रेम के लिए कैश होगा। तो अगर आपको किसी कैश की ज़रूरत है, तो हम इसे स्मृति में भी जोड़ सकते हैं और इसे एक ढेर कहते हैं।

a == b 

लेकिन, यह करता है:

Answer 8

आप stackless सी लागू करने के लिए पहली बात यह एहसास है कि यह एक ढेर की जरूरत नहीं है है चाहता था कहो?

isequal(a, b) { return a == b; } 

नहीं। क्योंकि एक स्मार्ट संकलक isequal के लिए कॉल, उन्हें a == b में बदल इनलाइन होगा। तो, क्यों न सिर्फ सब कुछ इनलाइन करें? निश्चित रूप से, आप अधिक कोड उत्पन्न करेंगे लेकिन यदि स्टैक से छुटकारा पा रहा है तो यह आपके लिए लायक है तो यह एक छोटे से व्यापार के साथ आसान है।

रिकर्सन के बारे में क्या? कोई बात नहीं। एक पूंछ पुनरावर्ती समारोह की तरह:

bang(x) { return x == 1 ? 1 : x * bang(x-1); } 

अभी भी inlined जा सकता है, क्योंकि वास्तव में यह भेष में सिर्फ एक पाश के लिए है:

bang(x) { 
    for(int i = x; i >=1; i--) x *= x-1; 
    return x; 
} 

सिद्धांत रूप में एक बहुत स्मार्ट संकलक यह पता लगाने सकता है कि आप के लिए। लेकिन एक कम स्मार्ट एक अभी भी एक गोटो के रूप में यह समतल कर सकते हैं:

ax = x; 
NOTDONE: 
if(ax > 1) { 
    x = x*(--ax); 
    goto NOTDONE; 
} 

एक मामले यदि आप एक छोटे व्यापार बंद करना है, जहां नहीं है। इसे रेखांकित नहीं किया जा सकता है:

fib(n) { return n <= 2 ? n : fib(n-1) + fib(n-2); } 

स्टैकलेस सी बस ऐसा नहीं कर सकता है। क्या आप बहुत कुछ दे रहे हैं? ज़रुरी नहीं। यह कुछ सामान्य सी भी बहुत अच्छा नहीं कर सकता है। अगर आप मुझ पर विश्वास नहीं करते हैं तो बस fib(1000) पर कॉल करें और देखें कि आपके बहुमूल्य कंप्यूटर के साथ क्या होता है।