0
$\begingroup$

Besides basic instructions for a general-purpose computer (binary arithmetic, move instruction, and jump on condition), it seems you can't implement a universal turing machine (is that even the right term?) without something more. That something is the ability to do arbitrary levels of function calls, I believe, yet how does a CPU implement them?

Setting a return address before jumping to the function code works for one call, but what if there are nested function calls? How will the CPU keep track of all the return addresses?

Is there a return address stack on the CPU (limited to memory on chip), or is it emulated in software at the assembler using regular RAM?

(In case it matters, I'll ask on behalf of Intel 8088 or 80x86 CPUs.)

Thanks!

Improve this question
$\endgroup$
4
  • $\begingroup$ But, as I understand it, such machines are limited to a single function, effectively. $\endgroup$
    – theDoctor
    Nov 12 '21 at 12:22
  • $\begingroup$ You only need one function $\endgroup$
    – user253751
    Nov 12 '21 at 12:28
  • $\begingroup$ @theDoctor Yes, a TM is limited to one specific function, but that function could be "simluate TM number $n$ on input $x$", making the TM universal. Each CPU is similarly limited to computing one specific function: executing machine language, which makes the CPU "universal", in some sense. $\endgroup$
    – chi
    Nov 12 '21 at 12:47
  • $\begingroup$ @user253751 The irony is that Alan Turing probably invented the subroutine. $\endgroup$
    – Pseudonym
    Nov 14 '21 at 5:37
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ (+1), but I feel that referring to "the same way the CPU actually executes them" can only be understood if one already knows how function calls are actually realized on CPUs. The OP is precisely asking to describe that, which you do in the second part of your question. $\endgroup$
    – chi
    Nov 12 '21 at 12:50
  • $\begingroup$ @chi I added (see below) to satisfy you. $\endgroup$
    – user253751
    Nov 12 '21 at 12:51
  • $\begingroup$ Just one more thing: It's worth looking at the assembly output of real programs to learn about how real CPUs handle things such as functions/subroutines. See, for example, godbolt.org $\endgroup$
    – Pseudonym
    Nov 14 '21 at 5:38
2
$\begingroup$

Is there a return address stack on the CPU (limited to memory on chip), or is it emulated in software at the assembler using regular RAM?

Yes.

  • Some processors do not have a stack (and need to emulate it using RAM for everything)
  • Some have a fixed size stack
  • Most use general purpose ram via a stack register
  • Some have a stack that is partially in CPU cache and partially in RAM.

80x86 uses a stack pointer register SS:(E)SP

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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