4 ms·
It was hard for a moment to get my head around the idea of static activation records. That makes “procedure call” simply into a goto. I guess I tend to write a
by gumby 7y ago
It was hard for a moment to get my head around the idea of static activation records. That makes “procedure call” simply into a goto. I guess I tend to write assembly code this way though.
Ironic that almost 20 years later the idea of dynamic activation had been so well absorbed that it was possible to write an influential paper all about how procedure call (and lambda) could be considered a goto (via tail recursion)!
- Stratoscope 7y agoYes, imagine that a function looks like this in memory: +-----------------+ | return address | +-----------------+ | executable code | +-----------------+ The way you call a function is to store your desired return address in the first slot, and jump to the code in the second slot. The function jumps to the saved return address when it's done. We did it this way for years. Now given that mindset, how could you even contemplate recursion? Where would you put all the return addresses?
- mark-r 7y agoThat's the way the Control Data Cybers worked, except that it wasn't just a return address - it was a complete jump instruction. You needed to start your function with a no-op of the correct length, and it was overwritten by the caller. Then to return from your function you simply jumped back to the beginning.
- zozbot234 7y agoNice. Basically, the caller uses self-modifying code to set up the correct continuation ("self-modifying code" and "continuation" being somewhat closely-related concepts, after all), and then has the callee jump to it. Makes a lot of sense.
- Sniffnoy 7y agoWhat's a little confusing here is that they talk about "static allocation" vs "dynamic allocation"; but these days, use of the stack is referred to as static allocation! Even if it's not as fully static as the old way. The shift in terminology makes the old debate opaque for the modern reader, and without your comment (and some similar ones) I wouldn't have known what was going on.
- gumby 7y agoI have never seen that usage — in what community is it common? Thanks!
- deleted 7y ago[deleted]
- kragen 7y agoI haven't seen that usage anywhere.
- deleted 7y ago[deleted]
- gowld 7y agoSniffjoy is referring to static allocation of local variables on the stack (vs dynamically on the heap), not static allocation of the stack itself.
- kragen 7y agoReferring to stack allocation as "static allocation" is just not something I've seen before. I suspect you're simply in error; maybe you misheard someone saying the phrase "stack allocation", or you've been talking to somebody who misheard it that way. You can statically allocate a local variable in C, for example: static char *err = NULL; But that specifically does not allocate it on the stack. Both heap allocation and stack allocation are dynamic, not static. There are things that are a bit more of a gray area in C and Unix and Win32/64 — are "statically allocated" variables of a shared library really statically allocated if they aren't there when the program starts up and they may be at some unexpected address? — but this is not one of them.
- Someone 7y agoNitpick: you also stored the function’s arguments there (if the language supported function arguments. I think most did, but am not sure about COBOL) On the plus side, languages at the time (FORTRAN, COBOL) also required array sizes to be known at compile time, and memory allocators didn’t exist, so programs never ran out of memory (but would abort if an input file was larger than expected, even if the machine had plenty of memory available) Consequently, CPU support for stacks was weak, because languages had no good use for them. In theory, optimizers could do away with (part of) the activation record in cases where a function was called from only one place, or where arguments always were the same. I don’t know whether compilers that did that existed.
- dreamcompiler 7y agoEven without tail recursion, conventional procedure calls are still just gotos plus an automatically-managed stack. Which fits the author's thesis that higher-level memory models are what distinguishes higher-level programming. The aspect of this that bothers me is that automatically-managed stacks are not the only way to call procedures. Continuations for example are another way; actors yet another. But because automatically-managed stacks are present in virtually every CPU at the ISA level, many programmers never venture outside that model and have trouble understanding that others even exist, much less what advantages they might bring.
- CyberDildonics 7y agoAnd what are those advantages? Function call ABIs are a standard way to change what is executing and come back when it is done. Does that really need to change? Other software architecture can be built on top of that, you don't need to change the way you call a function with assembly to structure software differently.
- kragen 7y agoThe advantages are that you can do threads, exceptions, lazy sequences, backtracking, tail-call elimination for state machines, and so on. (The disadvantages are the same.) Yes, you can emulate these on top of function-call-based ABIs, but you incur the usual emulation overhead.
- cat199 7y agothis sub-discussion about tail calls, etc. is in reference to: https://dspace.mit.edu/bitstream/handle/1721.1/5753/AIM-443.pdf https://dspace.mit.edu/bitstream/handle/1721.1/5753/AIM-443.... that series of papers was released adjacent to the development of the scheme language which will generally optimize out the need for a call stack and replace it with essentially goto in certain cases. as for 'changing the way you call a function' this subtopic is primarily of importance for language/compiler implementers; while you don't "need" to change the way you call a function, often doing so can speed up the program hugely, or allow things that were not otherwise possible (e.g. infinite recursion without stack overflow)
- kragen 7y agoI'm guessing that everyone here explaining to you how procedure calls work has, at some point, used a procedure call and return sequence that you implemented or debugged in GCC :)
- gumby 7y agoHa ha true, though there’s always something to learn. Even the first machine I ever programmed, the KA-10, had stack manipulation instructions though any location in memory could be a stack (which came with base and bounds for free) so threading was easy to write in assembly code. There was no difference between a call stack and a stack data structure — we called them all “push down list”