1
$\begingroup$

The stack allows subroutines to be used. It can store return address for "return from subroutine" instruction (RTN) and also arguments for the function.

It is not possible to store return address in the program instruction list itself, because the subroutine might be called from many different places in the program, and the return address will differ.

The same with arguments, the argument passed to the subroutine differs.

Without stack, the subroutine as a whole would have to be printed out multiple times in the program instruction sequence (i.e., there would not be subroutines. )

So is the reason a stack architecture was developed/designed originally (and still to this day) to reduce the size of the program mainly?

There might be more reasons than arguments and return addresses for stack, but those are as much as I understand so far.

Improve this question
$\endgroup$

4 Answers 4

Reset to default
5
$\begingroup$

The reason for having a stack is recursion. You don’t need a stack if you don’t have recursion. CDC super computers in the 70s worked just fine without a stack - until they implemented Pascal.

On these machines the "Subroutine call" instruction stored a "Jump" instruction just before the start of the called subroutine. Which means only one call to any subroutine could be running at any time (recursion means one function is called again from a different location while it is running. A call from the same location would actually work, but the first recursively called function must have two calls from different locations, so the first Jump instruction would be overwritten with a different one). No limit on the number of subroutines being called. And no recursion means all variables can be stored at fixed addresses.

Improve this answer
$\endgroup$
4
  • $\begingroup$ If you would like to elaborate in your answer on why that is the case, feel free. I can see how stack provides return address when doing nested subroutine calls (otherwise a single register is enough, but for arbitrary many levels deep nested calls), and also when needing different arguments depending on what calls the subroutine. Would happily see your point of view but need a bit more. Any major difference between nested subroutine calls (subroutine calling other subroutine), and recursive calls (subroutine calling itself) in how it uses stack/needs stack? $\endgroup$
    – BipedalJoe
    Commented Dec 9, 2022 at 6:31
  • $\begingroup$ if recursion was much bigger reason than nested functions, then either 1) recursion must have different requirements that needs stack more, or 2) recursion is just used a lot more. for 1), I do not see why. and for 2), I use much more nested functions than recursive functions myself in my very short programming experience, and iteration rather than recursion, so if you want to clarify that recursion is used a lot more then feel free. $\endgroup$
    – BipedalJoe
    Commented Dec 9, 2022 at 7:18
  • $\begingroup$ Re, Computers in the 70s. You don't need a hardware stack to implement a language that allows reentrant subroutine calls. It's just an optimization. The caller always knows the location to which it wants a call to return. On a machine with no hardware stack, the caller can explicitly push the return address onto a software stack before jumping to the subroutine, and the subroutine can explicitly pop the return address and jump to it. $\endgroup$
    – Solomon Slow
    Commented Dec 12, 2022 at 19:35
  • $\begingroup$ @gnasher729 I understand the reentrancy issue and how stack was required for reentrant subroutines now. Thanks for your answer. $\endgroup$
    – BipedalJoe
    Commented Dec 12, 2022 at 19:52
1
$\begingroup$

No, a compelling reason is that you can't predict the call pattern of the functions. In particular, you cannot predict the recursion depth so it is impossible to preallocate.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Thanks. I asked a related question on Stack Overflow (asking in chat seems to be usually not appreciated per rules, if it is like a "new question"), and I think that call pattern of recursive functions actually is predictable. Just not call depth. Is that not true? The answer (in comment) on the other question was function pointers. And I agree there the call pattern is not predictable. Also wrote answer with a minimal example showing that, stackoverflow.com/questions/74758523/…. $\endgroup$
    – BipedalJoe
    Commented Dec 12, 2022 at 9:45
  • $\begingroup$ I do not see that function pointers would motivate stack being invented/developed originally, it seems like something that would have come later, but that is just my intuition. I can't know for sure at this point. Innovations are usually for simple reasons at first, then more complex using what was innovated for the simple reason. So I can't rule out my premise, that it was to save program space, yet. Thanks for your answer anyway, I know now about function pointers. Very helpful. $\endgroup$
    – BipedalJoe
    Commented Dec 12, 2022 at 9:48
  • $\begingroup$ @BipedalJoe: you could indeed arrange all function frames as a FIFO list, with preallocation of... a certain number of each. But the links have to be adjusted dynamically. $\endgroup$
    – user16034
    Commented Dec 12, 2022 at 10:16
  • $\begingroup$ I might misunderstand what the recursive function example you mean does, but it seems to me that it is possible to write it all out beforehand, and then just run the program up until whatever depth it wants to do. While for function pointers, that does seem impossible. But I might miss something, I have shallow understanding, but it is what it seems like to me. $\endgroup$
    – BipedalJoe
    Commented Dec 12, 2022 at 10:19
  • $\begingroup$ @BipedalJoe: "write it all": write what ??? $\endgroup$
    – user16034
    Commented Dec 12, 2022 at 10:20
1
$\begingroup$

Alan Turing defined a stack in 1946 (article) and that it provided a way to save the return address of all active subroutines, thereby allowing code to be simplified into reusable subroutines. The stack was expanded on with the work of Klaus Samelson and Friedrich Bauer in 1955 (Wikipedia), that focused on locally declared data within scopes. This latter service is what stack is most indispensable for, reentrant functions need to have local variables for each iteration of the function being called. The storage of return addresses can be handled without a stack (although Turing himself did conceptualize a stack for this reason, and it is a logical architecture to manage that), so to be a bit pedantic, the stack is mostly indispensable for recursive functions, but, one reason for it is to allow subroutines, and thereby shrink and simplify the code.

Improve this answer
$\endgroup$
1
$\begingroup$

Without stack, the subroutine as a whole would have to be printed out multiple times in the program instruction sequence (i.e., there would not be subroutines. )

No. One can easily write the equivalent of a non-reentrant subroutine by storing the return address and the arguments in the "subroutine" itself:

          STORE_IMMEDIATE FAKE_SUB      .+4
          STORE           FAKE_SUB+1    ARG_1
          STORE           FAKE_SUB+2    ARG_2
          GOTO            FAKE_SUB+3
          …

FAKE_SUB  DATA            0
          DATA            0
          DATA            0
          …
          GOTO            *FAKE_SUB

Alternatively, the args could be stored in the caller's space, and the "subroutine" could access them relative to the return address.

So is the reason a stack architecture was developed/designed originally (and still to this day) to reduce the size of the program mainly?

I don't know about mainly, but having a stack definitely makes that easier.

Consider having several subroutines, each of which needs to use a large array in which to manipulate data. With subroutines, those arrays can be allocated on the stack ("auto" in C), and so will make use of the same overlapping temporary memory rather than permanently allocating space for each subroutine.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.