We take stacks and heaps for granted nowadays, but back in the very old days of computing, computers operated without a stack or a heap.<\/p>\n
Tell a recent college graduate this, and you may as well tell them that there was a time when you didn’t have instant access to millions of cat videos.<\/p>\n
It’s not too hard to imagine computing without dynamic memory allocation. You just have to use fixed-size memory buffers for everything. If you have to operate on variable-sized data, you reserved a fixed-size buffer of some capacity that is large enough to accommodate any data you would reasonably be expected to process, and if somebody asked for more, you just exited the program with a fatal error. If you were really nice, you would provide a compile-time configuration so your clients could adjust the maximum capacity to suit their datasets. And if you were really fancy, you wrote a custom allocator that operated on that fixed-size buffer so people could “allocate” and “free” memory from the buffer.<\/p>\n
But operating without a stack? How did you call a function if you didn’t have a stack for the return address or local variables?<\/p>\n
Here’s how it worked.<\/p>\n
First, the compiler defined a secret global variable for each inbound function parameter, plus another secret global variable for each function to hold the return address. It also defined a secret global variable for each of the function’s local variables.<\/p>\n
To generate a function call, the compiler assigned the parameter values to the corresponding secret global variables, assigned the return address to the function’s secret “return address variable”, and then jumped to the start of the function.<\/p>\n
The function read its parameters from its secret global variables, and used the pre-defined secret global variables that corresponded to its logically local variables. When the function was finished, it jumped to the address held in the function’s secret “return address variable.”<\/p>\n
For example, suppose you had code like this, written in a C-like language:<\/p>\n
int add_two_values(int a, int b)\r\n{\r\n int c = a + b;\r\n return c;\r\n}\r\n\r\nvoid sample()\r\n{\r\n int x = add_two_values(31415, 2718);\r\n}\r\n<\/pre>\nThis would be transformed by the compiler into something like this:<\/p>\n
int a2v_a;\r\nint a2v_b;\r\nint a2v_c;\r\nvoid* a2v_retaddr;\r\n\r\nint add_two_values()\r\n{\r\n a2v_c = a2v_a + a2v_b;\r\n\r\n return_value_register = a2v_c;\r\n goto a2v_retaddr;\r\n}\r\n\r\nint sample_x;\r\nvoid sample()\r\n{\r\n a2v_a = 31415;\r\n a2v_b = 2718;\r\n a2v_retaddr = &resume;\r\n goto add_two_values;\r\nresume:\r\n sample_x = return_value_register;\r\n}\r\n<\/pre>\nCheck it out: We did a function call and return without a stack!<\/p>\n
Now, you can optimize the ABI by, say, passing some of these values in registers rather than globals. For example, most processors had a special “link” register and a special instruction “branch with link” that automatically set the link register equal to the address of the instruction after the “branch with link” instruction, And maybe you optimize the calling convention to pass the first two parameters in registers, resulting in this:<\/p>\n
int a2v_a;\r\nint a2v_b;\r\nint a2v_c;\r\nvoid* a2v_retaddr;\r\n\r\nint add_two_values()\r\n{\r\n a2v_a = argument_register_1;\r\n a2v_b = argument_register_2;\r\n a2v_retaddr = link_register;\r\n\r\n a2v_c = a2v_a + a2v_b;\r\n\r\n return_value_register = a2v_c;\r\n goto a2v_retaddr;\r\n}\r\n\r\nint sample_x;\r\nvoid sample()\r\n{\r\n argument_register_1 = 31415;\r\n argument_register_2 = 2718;\r\n branch_with_link add_two_values;\r\n sample_x = return_value_register;\r\n}\r\n<\/pre>\nThere was just one catch: You can’t do recursion.<\/p>\n
Recursion doesn’t work because a recursive call would overwrite the return-address variable with the return address of the recursive call, and when the outer call completed, it would jump to the wrong place.<\/p>\n
The programming languages of the day solved this problem by simply declaring it illegal: They didn’t support recursion.\u00b9<\/p>\n
Bonus chatter<\/b>: Some compilers were even sneakier and used self-modifying code: The special return-address variable was really the address field of the jump instruction at the end of the function!<\/p>\n