Note that Turing machines don't have any function calls, and they work just fine as Turing machines. Function calls are not a necessity for Turing-completeness. All non-recursive function calls can simply be inlined. Recursive functions can be translated to loops using an explicit stack, the same way the CPU actually executes them (see below).
A typical 32-bit CALL instruction simply does the following:
- Decrement the stack pointer by 4
- Write the address of the next instruction at the address stored in the stack pointer (i.e.
WriteMemory(ESP, EIP);
- EIP having already been incremented to the next instruction)
- Set the program counter to the address being called (i.e.
EIP := Operand;
)
and the RET (return) instruction does the following:
- Set the program counter to the value stored in memory at the address stored in the stack pointer (i.e.
EIP := ReadMemory(ESP);
)
- Increment the stack pointer by 4
(On a general-purpose CPU) There is no special hardware stack. There are instructions designed for use with a stack in normal memory (PUSH
, POP
, CALL
, RET
, ENTER
, LEAVE
, and the ESP
and EBP
registers and associated addressing modes). It's the software's responsibility to set aside some memory space for the stack. Software is also mostly responsible for deciding how to use it - if you want to write a program with no function calls, more power to you. There are some cases where the CPU will use the stack anyway - like interrupt handling - so even if you didn't use the stack in your software you'd want to set aside a small amount of space for interrupts. Interrupts are not required for Turing-completeness. Other architectures, like ARM, don't need a stack for interrupts - it's purely a design choice.
Modern CPUs do also remember the last several return addresses in a special stack memory unit on the CPU. However, this is purely for speculative execution - an optimization. The CPU will start speculatively executing the code at the address stored in its own stack, while it waits to read the real address from memory. If it gets the address right, it has a head start.
Some non-von-Neumann machines, like some small microcontrollers, do have a special stack memory unit that is the only place the return addresses are stored. However, those aren't the general-purpose CPUs you're thinking of.