Search code examples
ccompiler-construction

What are the minimum requirements for a processor so that a C compiler can be written for it?


I'm curious about the absolute minimum instructions that a processor should support so that a standard C compiler can be written targeted towards it. What are those requirements?


Solution

  • The answer is surprisingly simple. Any Turing complete machine can emulate any other Turing complete machine, machines that can have a C complier written for them are Turing complete, so they can be emulated by any Turing machine.

    I/O from the C standard is quite vague so it doesn't need to be persistent, visible from outside or even do anything other than return errors, so that's not a requirement. Same goes for the time-related functions (I haven't looked at all of them, maybe there's an exception).

    So in theory you can have a single instruction computer that is powerful enough for C. Same goes for most other programming languages, btw. Not very useful without I/O, but it is enough.

    Strictly speaking real physical computers are not Turing complete since they don't have infinte memory, but they are close enough that we squint and pretend it's the same thing.