4 ms·

"That is said a lot, but what are actual desicions that are made to conform to the C model?" Among other things, special instructions to support a function cal

"That is said a lot, but what are actual desicions that are made to conform to the C model?" Among other things, special instructions to support a function call stack, which is very much specific to the C model. In Lisp the call stack is unnecessary because of the use of continuation passing style, which implies that all function calls are tail calls and mostly requires that everything be heap-allocated (many compilers will use a call stack as an optimization to avoid excessive garbage collections; unlike C, it is not a fundamental part of the lower level semantics). If you wanted to design a CPU for Lisp or functional languages, you would probably choose to provide special instructions to support continuation passing style or normal order evaluation. You could also imagine a CPU that does not support general pointer arithmetic or which has some form of built-in array bounds checks, which would all be fine if supporting C were not a requirement.

slededit 8y ago
X86 does have array bounds checking now with MPX. Further everything you've mentioned is useful to all languages including the stack. Can you give an example of a negative trade off made for C?
- jstimpfle 8y ago
  Right. That's what I actually wanted to ask with my first question (but didn't).
- betterunix2 8y ago
  In some languages a call stack is only useful as an optimization and some other form of control flow must be emitted for certain constructs that violate the stack paradigm (e.g. call/cc in Scheme, conditions/restarts in Common Lisp). C is also one of the only languages where general pointer arithmetic is necessary; in most languages used today more restricted forms of pointer arithmetic would be more than adequate. I am not saying these are negative tradeoffs as far as the ISA goes, but it is absolutely the case that modern CPUs are designed with C (or some similar language) in mind.
  - slededit 8y ago
    Processors exist to run code quickly. Slow ones don't sell very well, so we'd see stack oriented opcodes regardless of C's existence. You would also still use functions like lea, and indexed moves in any language with the concept of an array so that too is not strictly related to C. Most of the X86's CISC "style" predates C, and the reverse is mostly true - C was heavily inspired by the PDP's instruction set. When the 8086 came out originally BASIC was a far more important language for the class of processor it was. "Serious" software was much more likely to be raw assembler than C. The processor was just too small and compilers weren't good enough.
Rusky 8y ago
> unlike C, it is not a fundamental part of the lower level semantics I don't think this is an accurate characterization of C, actually. Unless I'm forgetting something, an implementation of C that heap-allocated automatic storage and used continuation passing style could still be conforming. Or in other words, the C standard doesn't specify anything about the memory layout of the stack- the word "stack" isn't even in there!
- betterunix2 8y ago
  Sure, you can apply a CPS conversion to a C program, but what you would get would actually be a (abstract) function call stack because there is nothing in C that breaks the call stack paradigm (setjmp/longjmp come close but the semantics are carefully defined to avoid breaking the semantics of a call stack; in particular they cannot be used to "restore" stack frames that were previously destroyed by a return statement or a call to longjmp). In some languages (like Scheme) it is possible to write code that will not have that "de facto" call stack because there is first-class support for things that completely break the call stack paradigm (e.g. call/cc).
  - Rusky 8y ago
    Okay, but most Scheme code doesn't use call/cc, and even when it does the vast majority of the continuations in use are also "abstract function call stacks." You said it yourself- a stack is a useful tool for implementing these non-C-like languages. Its presence does not force you to "buy into the C model to some extent."
jstimpfle 8y ago
> You could also imagine a CPU that does not support general pointer arithmetic or which has some form of built-in array bounds checks, which would all be fine if supporting C were not a requirement. I am happy to correct you, C does not require that. But also, array bounds checks are not a thing that you can implement physically. There is not necessarily corresponding only a single array length to any given address. Imagine a virtual machine that just allocates a chunk of ram using malloc to provide virtual memory to the emulated machine. Now add another level of memory management on top. Or imagime a function tha gets just a subrange of an array, for example to search an element therein. But the actual "array" might be much larger. It might be unclear even to the compiler how large the array is!

slededit 8y ago

X86 does have array bounds checking now with MPX. Further everything you've mentioned is useful to all languages including the stack. Can you give an example of a negative trade off made for C?

jstimpfle 8y ago
Right. That's what I actually wanted to ask with my first question (but didn't).
betterunix2 8y ago
In some languages a call stack is only useful as an optimization and some other form of control flow must be emitted for certain constructs that violate the stack paradigm (e.g. call/cc in Scheme, conditions/restarts in Common Lisp). C is also one of the only languages where general pointer arithmetic is necessary; in most languages used today more restricted forms of pointer arithmetic would be more than adequate. I am not saying these are negative tradeoffs as far as the ISA goes, but it is absolutely the case that modern CPUs are designed with C (or some similar language) in mind.
- slededit 8y ago
  Processors exist to run code quickly. Slow ones don't sell very well, so we'd see stack oriented opcodes regardless of C's existence. You would also still use functions like lea, and indexed moves in any language with the concept of an array so that too is not strictly related to C. Most of the X86's CISC "style" predates C, and the reverse is mostly true - C was heavily inspired by the PDP's instruction set. When the 8086 came out originally BASIC was a far more important language for the class of processor it was. "Serious" software was much more likely to be raw assembler than C. The processor was just too small and compilers weren't good enough.

Rusky 8y ago

> unlike C, it is not a fundamental part of the lower level semantics I don't think this is an accurate characterization of C, actually. Unless I'm forgetting something, an implementation of C that heap-allocated automatic storage and used continuation passing style could still be conforming. Or in other words, the C standard doesn't specify anything about the memory layout of the stack- the word "stack" isn't even in there!

betterunix2 8y ago
Sure, you can apply a CPS conversion to a C program, but what you would get would actually be a (abstract) function call stack because there is nothing in C that breaks the call stack paradigm (setjmp/longjmp come close but the semantics are carefully defined to avoid breaking the semantics of a call stack; in particular they cannot be used to "restore" stack frames that were previously destroyed by a return statement or a call to longjmp). In some languages (like Scheme) it is possible to write code that will not have that "de facto" call stack because there is first-class support for things that completely break the call stack paradigm (e.g. call/cc).
- Rusky 8y ago
  Okay, but most Scheme code doesn't use call/cc, and even when it does the vast majority of the continuations in use are also "abstract function call stacks." You said it yourself- a stack is a useful tool for implementing these non-C-like languages. Its presence does not force you to "buy into the C model to some extent."

jstimpfle 8y ago

> You could also imagine a CPU that does not support general pointer arithmetic or which has some form of built-in array bounds checks, which would all be fine if supporting C were not a requirement. I am happy to correct you, C does not require that. But also, array bounds checks are not a thing that you can implement physically. There is not necessarily corresponding only a single array length to any given address. Imagine a virtual machine that just allocates a chunk of ram using malloc to provide virtual memory to the emulated machine. Now add another level of memory management on top. Or imagime a function tha gets just a subrange of an array, for example to search an element therein. But the actual "array" might be much larger. It might be unclear even to the compiler how large the array is!