- शुरुआती कंप्यूटरों को stack और heap के बिना भी function call लागू करने पड़ते थे, और compiler parameters, return address और local variables से मेल खाने वाले छिपे हुए global variables के जरिए call state को मैनेज करता था
- caller arguments को save करता, return address variable में वापस लौटने की जगह डालता, फिर function के start point पर jump करता; function calculation के बाद save किए गए address पर फिर से jump करता
- logical local variables भी असल में global storage space इस्तेमाल करते थे, इसलिए बाहर से वे function जैसे दिखते थे, लेकिन अंदरूनी operation fixed memory और
gotoके करीब था - कुछ ABI और processors ने argument passing और return address handling को registers या
branch with linkसे optimize किया, लेकिन बुनियादी constraints वैसे ही रहे - क्योंकि उसी function का return address नई call से overwrite हो जाता था, recursive calls संभव नहीं थीं, और उस समय की languages ने recursion को ban करके या केवल explicitly allow करके इसका सामना किया
Stack के बिना function call बनाने का तरीका
- शुरुआती computer environments में आज जिन्हें हम स्वाभाविक मानते हैं, वे stack या heap नहीं थे
- heap के बिना dynamic memory allocation को fixed-size buffers से replace किया जा सकता था
- variable-size data process करते समय भी पहले से काफी बड़ा fixed buffer reserve किया जाता था
- अगर requested data buffer capacity से ज्यादा हो जाता, तो program fatal error के साथ terminate हो जाता
- ज्यादा friendly implementation compile time पर maximum capacity set करने देती थी
- ज्यादा refined implementation fixed buffer के ऊपर custom allocator रखकर उसे
allocateऔरfreeकी तरह इस्तेमाल करने देती थी
छिपे हुए global variables पर आधारित calling convention
- stack के बिना function call लागू करने के लिए compiler हर function के लिए कई छिपे हुए global variables define करता था
- हर input parameter के लिए global variable
- function का return address रखने वाला global variable
- local variables से मेल खाने वाले global variables
- calling code इस क्रम में execute होता था
- parameter values को संबंधित hidden global variables में store करता
- वापस लौटने की जगह function के return address variable में record करता
- function start location पर
gotojump करता
- function parameters और local variables, दोनों को hidden global variables से read/write करता था
- execution पूरा होने पर return value को return value register में डालता और function के return address variable में stored address पर jump करता
C-जैसा code goto-based code में बदलने का उदाहरण
- उदाहरण function
add_two_values(int a, int b)stack के बिना नीचे जैसे storage space में transform हो सकता हैa2v_a,a2v_barguments store करने के लिए global variables हैंa2v_clocal variablecसे मेल खाने वाला global variable हैa2v_retaddrवापसी address store करने के लिए global variable है
- caller
sample()31415और2718को क्रमशः argument global variables में store करता है - इसके बाद
a2v_retaddrमेंresumelocation डालता है औरadd_two_valuesपर jump करता है add_two_valuescalculation result कोreturn_value_registerमें store करने के बादa2v_retaddrपर return करता हैresumelocation पर लौटने के बाद caller return value register की value कोsample_xमें store करता है
Registers और branch with link से optimization
- यही structure ABI level पर register passing से और तेज बनाया जा सकता है
- कई processors special
link registerऔरbranch with linkinstruction provide करते थेbranch with linkbranch instruction के बाद वाली instruction का address automatically link register में store करता है- caller पहले दो arguments को
argument_register_1,argument_register_2में डाल सकता है - callee function इन register values को अपने hidden global variables में move करके इस्तेमाल कर सकता है
- return address भी
link_registerसे function के return address variable में store किया जा सकता है - यह optimization stack के बिना भी call और return संभव होने की मूल structure को बनाए रखता है
Recursion क्यों रुक जाती है
- इस calling method की मुख्य constraint recursive call संभव न होना है
- recursive call होने पर उसी function का return address variable नई call के return address से overwrite हो जाता है
- outer call खत्म होते समय जिस original location पर return करना था, वह गायब हो जाती है और गलत location पर jump हो जाता है
- उस समय की programming languages ने recursion support न करके इस problem से बचा
- FORTRAN ने शुरुआत में subroutines भी support नहीं किए थे, और subroutines 1958 में add हुए
- FORTRAN में recursion support standard 1991 में बना, और तब भी subroutine को
RECURSIVEसे explicitly mark करना पड़ता था
Self-modifying code और शुरुआती processors के subroutine instructions
- कुछ compilers ने और चालाकी से self-modifying code का उपयोग किया
- function के अंत में jump instruction के अंदर मौजूद address field असल में return address variable की भूमिका निभाता था
- यह तरीका सिर्फ एक simple trick नहीं, बल्कि practical need हो सकता था
- कुछ processors indirect jump support नहीं करते हो सकते थे
- subroutine की practical usefulness मान लिए जाने के बाद कई processors ने dedicated call instruction add किए
- return address को subroutine के first word में store करता
- actual execution second word से start होता
- return करते समय subroutine start label के जरिए indirect jump execute होता
- example assembly में
bsr add_two_valuesadd_two_valuesके first word में return address store करता है, और sacrifice के लिए रखे गएnopके बाद की actual instruction से execution शुरू करता है
1 टिप्पणियां
Hacker News की राय
इस विषय पर The Art of Computer Programming वाकई बहुत अच्छी लगी
ऊपर से देखने में पुरानी लगती है, लेकिन heap या stack से पहले के दौर में dynamically बदलने वाले arrays या data structures को संभालने वाले algorithms इसमें भारी संख्या में हैं
किताब garbage collection और Lisp list implementation तक धीरे-धीरे आगे बढ़ती है, और Knuth से जिस encyclopedic knowledge की उम्मीद होती है, वह पूरी तरह मौजूद है
मेरा खास पसंदीदा उदाहरण वह तरीका है जिसमें दो arrays एक ही space को dynamically share करते हैं। एक array
location#0से आगे की ओर बढ़ता है, और दूसरा arraylocation#Endसे पीछे की ओर बढ़ता है, तो statically allocated space को कुशलता से बांटकर इस्तेमाल किया जाता हैइसे मनमानी संख्या के arrays तक बढ़ाया भी जा सकता है, लेकिन उस स्तर पर बस
MallocऔरReallocइस्तेमाल करना बेहतर है, और वह technique खुद भी malloc जैसी routine के काफी करीब हैinsert और paste में data को shift करने की जरूरत नहीं पड़ती थी, लेकिन navigation के समय पड़ती थी। फिर भी यह अच्छी तरह काम करता था
अगर उतना न मिले, तो preferred से छोटा size लिया जाता था, और minimum भी न मिल पाए तो execution fail हो जाता था
मुझे याद है कि system उस physical RAM के टुकड़े के निचले हिस्से में heap और libraries, और ऊपरी हिस्से में stack रखता था
System 8 के आसपास virtualization layer जुड़ने के बाद इस approach की जरूरत कम हो गई, और MacOS X के दौर में बाकी systems की तरह paging memory इस्तेमाल होने लगी, तो ऐसे करतबों की जरूरत नहीं रही
फिर भी यह सोचकर मजा आता है कि Art of Computer Programming की ऐसी “एक अजीब trick” कभी कई simultaneously running apps के RAM allocation का तरीका हुआ करती थी
एक ऊपर की ओर बढ़ता था और दूसरा नीचे की ओर। architecture आकर्षक था, लेकिन आखिरकार वादा की गई performance नहीं दे पाया
fixed-size page के भीतर offset array आगे की ओर बढ़ता है, और variable-length row values का array अंत से पीछे की ओर बढ़ता है। मेरी समझ में row delete करने पर पीछे वाले array में holes बन सकते हैं
documentation B-tree structure के बारे में TAOCP को cite करती है, इसलिए अगर यह सीधी inspiration रही हो तो हैरानी नहीं होगी
ALGOL में recursive functions जोड़ना काफी विवादास्पद था, और एक रोचक कहानी के रूप में बचा हुआ है: https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...
How recursion got into programming: intrigue, betrayal, and advanced semantics - https://news.ycombinator.com/item?id=33123916 - अक्टूबर 2022, 8 comments
How Recursion Got into Programming (2014) - https://news.ycombinator.com/item?id=23061881 - मई 2020, 47 comments
How recursion got into Algol 60: a comedy of errors - https://news.ycombinator.com/item?id=10131664 - अगस्त 2015, 124 comments
How recursion got into programming: a comedy of errors - https://news.ycombinator.com/item?id=8073361 - जुलाई 2014, 108 comments
SUBLEQ मशीन के लिए Forth इंटरप्रेटर(https://github.com/howerj/subleq) और bit-serial मशीन के लिए इंटरप्रेटर(https://github.com/howerj/bit-serial) लिखे थे, लेकिन दोनों में Forth के लिए जरूरी function call stack नहीं था
SUBLEQ indirect load/store की भी अनुमति नहीं देता, इसलिए थोड़ा भी जटिल काम करने के लिए self-modifying code चाहिए
मैंने दोनों मशीनों के लिए ऐसी क्षमता देने वाली virtual machine बनाई, और उसमें cooperative multithreading भी जोड़ी
heap चाहिए हो तो उसे Forth में लिखता हूँ, और floating-point word set भी Forth में लिखता हूँ। कई MCU में अब भी floating-point instructions नहीं हैं, और इसे implement करने वाले software function calls से संभाला जा सकता है
दूसरे compilers का जिक्र नहीं हुआ है, लेकिन लगता है उन्होंने भी मिलती-जुलती approach अपनाई होगी। कुछ BASIC interpreters ने भी VM implement करके फिर उसी को target किया, और P-Code भी ऐसा ही है
basic system memory का अधिकतर हिस्सा video RAM था, और उसे video chip registers को
poke/peekकरने की काफी झंझट भरी प्रक्रिया से access करना पड़ता थाvideo chip एक auto-increment होने वाला current memory pointer रखती थी, इसलिए लगातार read या write करते समय pointer 1 से बढ़ जाता था, लेकिन system memory के अधिकतर हिस्से को सिर्फ इसी तरीके से access किया जा सकता था—यही बात बड़े programs लिखना मुश्किल बना देती थी
इसलिए TI ने GPL नाम की abstract machine बनाई, जिसने इस video RAM access को ज्यादा natural बनाया। हालांकि यह TMS9900 पर interpreted रूप में चलती थी, इसलिए native code से धीमी थी, और CPU video chip RAM को भी सिर्फ तब access कर सकता था जब chip screen scanout नहीं कर रही होती थी, जैसे horizontal/vertical retrace periods में; इसलिए यह और धीमी हो जाती थी
BASIC code और variables भी पूरी तरह इसी video memory में थे, तो यह साफ है कि TI-99/4A का BASIC interpreter किसमें लिखा गया था। यह बिल्कुल fast नहीं था
दिलचस्प बात यह है कि TMS9900 में असल general-purpose registers नहीं थे। workspace registers WR0~WR15 memory में कहीं रहते थे, और WP workspace pointer register उनकी ओर इशारा करता था
CPU के physical registers सिर्फ तीन थे: PC, WP और status register। नतीजतन बहुत primitive register windowing किया जा सकता था, और
BLWPinstruction से branch करने पर memory के किसी दूसरे स्थान पर मौजूद नया “register” set सक्रिय हो जाता था और return address नए workspace में store हो जाता थाइन दिनों TI-99/4A की बात मैं अक्सर इसलिए करता हूँ क्योंकि एक personal project के तौर पर इस model के लिए assembler बना रहा हूँ
यह बात सही है कि कुछ processors return address को subroutine के पहले instruction से ठीक पहले वाले word में store करते थे, और PDP-8 ऐसा ही करता था
PDP-8 का evolution recursion के लिए hardware support की यात्रा की तरह भी देखा जा सकता है
शुरुआत में
JMSinstruction function के पहले word में return address डाल देता था। अक्सर callerJMSinstruction के बाद arguments रखता था, और callee return instruction के relative offset से arguments पढ़ते हुए उसे हर बार increment करता था, ताकि return address फिर से code location की ओर point करेबाद में auto-increment locations में से एक का इस्तेमाल करके simple stack बनाना काफी common हो गया। PDP-8 में ऐसी 8 memory locations थीं जो pointer के रूप में इस्तेमाल होने पर हर बार increment होती थीं, और function prologue/epilogue इस stack को सीधे manage करते थे, जिससे पूरी recursion संभव हो जाती थी
और बाद में Harris 6120 जैसे microprocessor implementations में hardware stack जोड़ा गया, जिससे performance बेहतर हुई
Rinstruction, यानी return address store करने वाला instruction थायह instruction पहले से increment किए गए
PC+1को target location के instruction address हिस्से में store करता था, और convention के अनुसार वह target subroutine शुरू होने से ठीक पहले वाली unconditional branch instruction होती थीRinstruction के बाद उस subroutine तक जाने वालीUunconditional branch instruction रखी जाती थीsubroutine अपने से पहले वाले address पर branch करके return करती थी, और वहाँ call site के ठीक बाद लौटने वाली unconditional branch मौजूद होती थी
जब तक कोई ज्यादा advanced calling convention न इस्तेमाल किया जाए, recursion संभव नहीं थी। और assembly language में सभी instruction codes एक अक्षर के थे
AVR-8 के लिए लिखे जाने वाले programs में C calling convention का इस्तेमाल करना कभी-कभी पागलपन जैसा लगता है
assembly लिखने पर internal loop variables को बड़े register file के अंदर लगातार रखा जा सकता है, या फिर article में बताए गए तरीकों का इस्तेमाल किया जा सकता है
ऐसी apps में functions को “colour” करने का तरीका भी अच्छा है। अगर पता हो कि red function और green function एक साथ active नहीं होते, तो दोनों के local variables या parameters को reuse किया जा सकता है
पहले जिस microcontroller codebase project से जुड़ा था, उसमें कई developers हफ्तों से कई subsystems में पकड़ में न आने वाले bugs track कर रहे थे
code को move करने पर bug भी उसके साथ move हो जाता था। थोड़ा trace करने और traps लगाने के बाद, हम code की वे locations ढूंढ पाए जहाँ call stack बहुत deep होकर दूसरे data structures को overwrite कर रहा था
जब मैंने पहली बार programming सीखी, तो मुझे बिल्कुल इसी तरह जबरन programming करनी पड़ी थी। 1970s में नहीं, बल्कि 2001 में ऐसा था
क्योंकि मेरा पहला programming अनुभव game development tool RPG Maker 2000 द्वारा दी जाने वाली semi-graphical scripting “language” था
अगर आपने RM2K scripting नहीं देखी है, तो Scratch और Emacs Paredit mode के मिश्रण की कल्पना करें। उदाहरण: https://forums.rpgmakerweb.com/data/attachments/21/21958-f89...
यह text जैसा दिखता था, लेकिन text की तरह edit नहीं किया जा सकता था; इसे सिर्फ property dialog वाले blocks के रूप में edit किया जाता था
जाहिर है RPG Maker की scripting language में stack जैसी कोई fancy चीज़ नहीं थी। अगर reusable subroutine चाहिए होती, तो parameters के लिए छिपे हुए global variables assign करने पड़ते थे, और reentrancy नहीं थी
पीछे मुड़कर देखें तो लगता है कि अगर काफी जिद की जाती, तो RPG Maker 2000 के अंदर registers और runtime stack दोनों implement किए जा सकते थे
शुरुआत में यह आसान लगता है। 6502 के zero page जैसे नकली “registers” बनाए जा सकते हैं, और indirect variable access(https://rpgmaker.net/tutorials/523/) से stack भी बनाया जा सकता है
समस्या यह है कि RM2K में “parallel process” scripts के रूप में concurrency मौजूद है। अगर parallel processes ऐसी abstraction इस्तेमाल करें, तो अलग-अलग “threads” state को बेधड़क overwrite कर देंगे
इसलिए हर “virtual core” के लिए कई zero pages और stacks चाहिए होंगे, और हर parallel script को virtual core allocate/bind/schedule करना होगा। यानी किसी तरह हर script के पास अपना निजी stack pointer होना चाहिए
race conditions के बीच भी इसे stable बनाना हो तो आम तौर पर mutex जैसी चीज़ चाहिए होती है
RPG Maker game developers की जिद को देखते हुए लगता है कि किसी ने runtime feature को trick करके mutex जैसा काम करवाने का तरीका ढूंढ लिया होगा, लेकिन सच कहूं तो उन्होंने असल में क्या किया होगा, यह जानना भी डरावना लगता है
मुझे याद है कि rpgmaker.net से custom battle system implement किया हुआ एक game download किया था। वह built-in battle system को पूरी तरह उन techniques से replace करने वाला implementation था, जैसा आपने बताया
जब मैंने उसे editor में खोलकर देखा कि वह कैसे काम करता है, तो मैं पूरी तरह overwhelmed हो गया था। सैकड़ों “variables” थे, और अगर मुझे ठीक याद है तो केवल i64 allow था, और सैकड़ों “switches” भी थे। switches boolean थे
उस समय मुझे stack, heap, function calls जैसी concepts का बिल्कुल पता नहीं था
उसे बनाने और maintain/debug करने में कितनी energy लगी होगी, इसकी मैं कल्पना भी नहीं कर सकता
अगर मुझे ठीक याद है, तो ZX81 पर BASIC programs लिखते समय मैंने लगभग “बिना stack” वाले तरीके से लिखा था
1 GOTO 3010 LET C = A + B20 RETURN30 LET A = 140 LET B = 250 GOSUB 1060 LET A = C70 LET B = 380 GOSUB 1090 PRINT CRUN6यानी लेख में compiler जो काम करता है, वही मैं खुद कर रहा था। line numbers memory addresses थे, और hidden variables मुझसे छिपे नहीं थे। क्योंकि compiler मैं ही था
interpreter ने केवल एक काम किया:
GOSUBका return address store करनाहालांकि code syntactically गलत हो सकता है या मेरी याददाश्त बिगड़ गई हो सकती है। 40 साल लंबा समय है, लेकिन overall idea सही है
और machine के अंदर Z80 processor में stack management capability थी। BASIC interpreter सच में बहुत simple था, लेकिन उसके पास बहाना था: सिर्फ 1KB RAM और 8KB ROM जिसमें OS, interpreter, सब कुछ था
GOSUB,RETURNके reference के लिए line number या कोई दूसरा reference save करता है, और अगरGOSUBcalls nested हों, तो कई return points याद रखने पड़ते हैं, इसलिए किसी न किसी रूप में stack चाहिएबस कुछ BASIC में general-purpose stack के बजाय return pointers की fixed array और current position index ही होता था, जिससे, उदाहरण के लिए, call depth 7 पर fixed होती थी। programmer के नज़रिए से वह call stack जैसा ही behave करता था
बेशक, यह local variables/parameters वाला “proper” stack नहीं है, जैसा कोई stack कहते समय expect कर सकता है
BBC BASIC के default environment में nested calls, recursion सहित, के दौरान क्या होता है यह दिखाने वाला एक मजेदार demo संभव था। अगर stack location को display memory के बिल्कुल ऊपर set कर दें और उधर कुछ draw न होने दें, तो काम आगे बढ़ते हुए stack को grow करते देखा जा सकता था
screen resolution low होने की वजह से 2-byte return address screen mode 1 या 5 में 8 मोटे pixels जैसा दिखता था। mode 2 में 4 थे, लेकिन blinking colors की वजह से कम अच्छा था, और mode 0, 3, 4, 6 में 16 थे, लेकिन bit-level पर देखना 8 colors की repetition की तुलना में पहचानना मुश्किल था
arbitrarily expandable heap होने से पहले programmers कम से कम थोड़ी engineering judgment लगाते थे
क्योंकि input के probabilistic distribution पर विचार करना होता था, और हर intermediate storage space का size ठीक से तय करना पड़ता था
इसलिए “BUGS AND LIMITATIONS” पैदा हुए
इसलिए सब कुछ compile time पर statically allocate किया जाता है, और यह जानना पड़ता है कि input कितनी memory consume करेगा
लेकिन memory consumption की upper bound जानना application programmer के लिए भी पहले normal बात थी। क्योंकि memory की कमी कभी नहीं चाहिए होती
आजकल लगता है कि memory usage को बस YOLO पर छोड़ दिया जाता है
उदाहरण के लिए sed की maximum command length finite और छोटी होने जैसी limitations की तुलना में यह बड़ा improvement था
फ़ंक्शनल प्रोग्रामिंग बहुत लंबे समय तक करने के कारण, सच में यह सोचना मुश्किल है कि recursion के बिना code कैसे लिखा जाए
तकनीकी तौर पर मुझे पता है कि recursive algorithm को iterative algorithm में कैसे बदला जाता है, और resource constraints वाली जगहों पर ऐसा किया भी है, लेकिन मुझे यह पसंद नहीं है
आम तौर पर recursive वाला तरीका ज़्यादा सुंदर होता है, और 99% मामलों में पर्याप्त तेज़ भी लगता है। अगर compiler tail recursion support करे तो यह 100% के करीब है, लेकिन ज़्यादातर दिलचस्प कामों में वैसे भी stack को खुद maintain करना पड़ता है
कभी-कभी मैं जानबूझकर ऐसे काम करता हूँ ताकि सीख सकूँ कि मेरे जन्म से पहले लोग कैसे करते थे। मैं कभी-कभी Commodore 64 games से छेड़छाड़ कर रहा हूँ, और अब जबकि तेज़, सस्ते और इस्तेमाल में आसान hardware की आदत हो गई है, तो बहुत गहराई से महसूस होता है कि हम कितने ऐश में हैं
ऐसी पुरानी machines पर recursion करने के लिए अपना stack mechanism खुद बनाना पड़ता था, और फिर भी global storage के अलावा मूल रूप से इस्तेमाल करने का कोई तरीका नहीं था, इसलिए हल करने के लिए समस्याएँ बची रहती थीं
मैंने वह दौर देखा है, लेकिन किसी को भी इसकी सलाह नहीं देना चाहूँगा
Enhanced GNU Awk के
@letfeature में, function के बाहर—मसलनBEGINयाENDblock के अंदर—@letblock compiler से गुप्त global variables allocate करवाता थाये variables blocks के बीच जहाँ तक संभव हो reuse किए जाते हैं
$ ./gawk --dump-variables 'BEGIN { @let (a, b, c = 1) { } }'$ cat awkvars.out$let0001: untyped variable$let0002: untyped variable$let0003: 1ARGC: 1ARGIND: 0ARGV: array, 1 elementsBINMODE: 0[ .. snip many ]https://www.kylheku.com/cgit/egawk/about/
pingभी नहीं होता औरnc -z 104.37.63.7 443भी नहीं होताअपडेट: लगता है security infrastructure खराब है। मुझे यह भी नहीं पता कि वह क्या है, और मैं Twitter भी इस्तेमाल नहीं करता। AS check करने पर Google Fiber है
और मैं चाहूँगा कि मेरी निजी जानकारी निकालने की कोशिश न की जाए