प्राचीन दुनिया में subroutine call: stack या heap आने से पहले कंप्यूटर

जब कंप्यूटर में stack और heap नहीं थे, तब subroutine call

• आधुनिक computing में stack और heap को स्वाभाविक माना जाता है, लेकिन computing के शुरुआती दौर में कंप्यूटर stack या heap के बिना काम करते थे.
• dynamic memory allocation के बिना computing की कल्पना करना इतना कठिन नहीं है. हर चीज़ के लिए fixed-size memory buffer का उपयोग करना पड़ता था.
• अगर variable-size data को संभालना हो, तो संभावित data को समायोजित करने के लिए पर्याप्त बड़ा fixed-size buffer आरक्षित किया जाता था.
• compile-time settings देकर client को maximum capacity समायोजित करने की सुविधा दी जा सकती थी, या fixed-size buffer से memory को "allocate" और "free" करने वाला custom allocator लिखा जा सकता था.

stack के बिना function call करना

• compiler हर function के inbound parameter, return address, और local variable के लिए गुप्त global variables परिभाषित करता था.
• function call बनाने के लिए compiler parameter values को उन गुप्त global variables में assign करता, return address को function के गुप्त "return address variable" में assign करता, और फिर function की शुरुआत पर jump करता था.
• function, parameter को गुप्त global variables से पढ़ता और logical local variables के अनुरूप पहले से परिभाषित गुप्त global variables का उपयोग करता था.
• function समाप्त होने पर, वह function के गुप्त "return address variable" में मौजूद address पर jump करता था.

ABI optimization

• ABI को optimize करने के लिए कुछ values को global variables की जगह register में pass किया जाता था.
• अधिकांश processors में "link" register और "branch with link" instruction होते हैं, जो अपने-आप link register को "branch with link" instruction के बाद वाले address पर सेट कर देते हैं.
• पहले दो parameters को register में pass करने वाली calling convention को optimize किया गया.

recursive call की असंभवता

• recursive call काम नहीं करता था. recursive call return address variable को recursive call के return address से overwrite कर देता था, इसलिए बाहरी call पूरा होने पर गलत जगह jump हो जाता था.
• उस समय की programming languages ने यह घोषित करके इस समस्या को हल किया कि वे recursion को support नहीं करतीं.

बोनस चर्चा

• कुछ compilers self-modifying code का उपयोग करके और भी चतुराई से काम करते थे: विशेष return address variable वास्तव में function के अंत में मौजूद jump instruction के address field ही होता था.
• जब processor indirect jump को support नहीं करता था, तब यह तरीका व्यावहारिक आवश्यकता के रूप में इस्तेमाल किया जाता था.
• subroutine की व्यावहारिक उपयोगिता पहचाने जाने के बाद, कई processors ने subroutine call instructions जोड़े, जो return address को subroutine के पहले word में store करते थे और subroutine के दूसरे word से execution शुरू करते थे.
• subroutine से return करने के लिए subroutine start label के माध्यम से indirect jump चलाया जाता था.

GN⁺ की राय

• यह लेख शुरुआती computing युग में stack और heap के अभाव में programming कैसे की जाती थी, इसे समझाकर आधुनिक software development में उपयोग होने वाली memory management techniques के विकास को समझने में मदद करता है.
• stack और heap के बिना वाले दौर की programming आधुनिक developers को बहुत अपरिचित और अक्षम लग सकती है, लेकिन यह computing के इतिहास के माध्यम से यह समझने के लिए महत्वपूर्ण पृष्ठभूमि देती है कि तकनीक कैसे विकसित हुई.
• recursive call असंभव होने वाले दौर की programming सीमाएँ, आज recursive algorithms का उपयोग करने वाले developers के लिए एक रोचक ऐतिहासिक तथ्य प्रस्तुत करती हैं.
• आलोचनात्मक दृष्टि से देखें तो, ये शुरुआती programming तरीके यह भी दिखाते हैं कि वे आधुनिक जटिल और विविध आवश्यकताओं को पूरा करने के लिए बहुत सीमित थे.

[GN⁺]

Hacker News राय

• "The Art of Computer Programming" किताब के बारे में सकारात्मक मूल्यांकन

  • यह किताब पुरानी लग सकती है, लेकिन इसमें heap या stack से पहले के दौर के विभिन्न dynamic array और data structure को बदलने वाले algorithm शामिल हैं।
  • किताब garbage collection और Lisp list implementation के बारे में भी बताती है, और Knuth जिस तरह की उम्मीद जगाते हैं वैसा encyclopedic ज्ञान देती है।

• इस बारे में विवरण कि कैसे दो array एक ही space को dynamic रूप से साझा कर सकते हैं

  • एक array position #0 से सामान्य रूप से बढ़ता है, और दूसरा position #End से उल्टी दिशा में बढ़ता है, जिससे दोनों array statically allocated space को कुशलता से साझा कर पाते हैं।
  • इस तरीके को कई array तक बढ़ाया जा सकता है, लेकिन उस बिंदु पर शायद Malloc और Realloc का उपयोग करना बेहतर होगा।

• ALGOL भाषा में recursive function को शामिल करना विवादास्पद था—इस पर एक रोचक कहानी का लिंक साझा किया गया

  • लिंक के ज़रिए यह दिलचस्प इतिहास साझा किया गया है कि recursion programming language में कैसे आया।

• SUBLEQ मशीन और bit-serial मशीन के लिए Forth interpreter लिखने का अनुभव साझा किया गया

  • इन दोनों मशीनों में function call stack नहीं होता, जो Forth का एक आवश्यक हिस्सा है।
  • SUBLEQ indirect loading और storage की अनुमति नहीं देता, और असामान्य काम करने के लिए self-modifying code की ज़रूरत होती है।
  • इन क्षमताओं को उपलब्ध कराने और cooperative multithreading को support करने के लिए एक virtual machine बनाई गई।
  • ज़रूरत पड़ने पर heap को Forth में लिखा जाता है, और software function के रूप में implement किए गए floating-point operations भी शामिल होते हैं।

• PDP-8 प्रोसेसर में subroutine call से जुड़ी तकनीकी प्रगति का विवरण

  • शुरुआत में JMS instruction function के पहले word में return address स्टोर करता था।
  • बाद में auto-increment location का उपयोग करके एक साधारण stack बनाया गया, और function prologue/epilogue इस stack को हाथ से manage करके full recursion संभव बनाते थे।
  • बाद में performance सुधारने के लिए microprocessor implementation में hardware stack जोड़ दिया गया।

• लंबे समय से functional programming करने वाले एक उपयोगकर्ता ने recursion के प्रति अपनी पसंद साझा की

  • वे जानते हैं कि recursive algorithm को iterative algorithm में कैसे बदला जाए, लेकिन वे recursion को प्राथमिकता देते हैं।
  • ज़्यादातर मामलों में recursion पर्याप्त तेज़ होता है, और अगर compiler tail recursion support करे तो और भी।
  • वे Commodore 64 games को hack करते हुए यह समझने की कोशिश करते हैं कि पहले programming कैसे की जाती थी।

• 1991 के आसपास RS232 serial multiplexer design करने का अनुभव साझा किया गया

  • Z80 processor, EPROM, और Z80-SIO serial device का उपयोग करके hardware design किया गया था।
  • stack न होने के कारण function call के लिए register pair में return address पहले से लोड करने का तरीका अपनाया गया।

• उस दौर का उल्लेख जब heap को expand नहीं किया जा सकता था, इसलिए programmers को input के संभावित distribution पर विचार करके intermediate storage का आकार ठीक से तय करना पड़ता था

  • इससे "bugs and limitations" पैदा होते थे।

• उस समय का विवरण जब recursion इस्तेमाल नहीं किया जा सकता था, लेकिन tail recursion संभव था

  • शुरुआती call के लिए उपयोग किए गए branch_with_link के अलावा सामान्य branch का उपयोग करना पड़ता था।

• यह विवरण कि Enhanced GNU Awk में compiler function के बाहर मौजूद @let block के लिए गुप्त global variable allocate करता है

  • इन variables को जितना संभव हो उतना reuse किया जाता है।

• "Goto considered harmful" पेपर की दुनिया का वर्णन करने वाली एक पोस्ट का उल्लेख

  • ज़्यादातर लोग सिर्फ शीर्षक जानते हैं, जबकि पेपर subroutine के लिए single entry point देने के पक्ष में तर्क देता है।
  • कभी-कभी assembly code ऐसा लिखा जाता है कि वह किसी दूसरे subroutine में जा गिरे, लेकिन कोई नहीं चाहता कि सारा assembly code ऐसा ही हो।