4 ms·

Money quote for those checking the comments first: "Furthermore, we argue that the C standard does not allow Turing complete implementations, and that its eval

by adsche 11y ago

Money quote for those checking the comments first: "Furthermore, we argue that the C standard does not allow Turing complete implementations, and that its evaluation semantics does not preserve typing. Finally, we claim that no strictly conforming programs exist. That is, there is no C program for which the standard can guarantee that it will not crash."

xorblurb 11y ago
Well at least the section explaining why they think C is not Turing complete is beyond ridiculous (TLDR: memory is not infinite so there exist a state machine... WTF????? technically mathematically true but has always been completely irrelevant when talking about real implementations) And it seems to be written with a serious tone, it is probably not even a joke!
- Sniffnoy 11y ago
  The point isn't that memory isn't infinite, but that C's memory model isn't infinite. There are other languages that do have an infinite memory model (for instance, any language with a builtin bignum type). I mean, if you want to judge ridiculousness, then their explanation of why there are no strictly conforming programs (specifically: even a program with an empty main function cannot be guaranteed not to overflow the stack) is also ridiculous, but it's still interesting.
  - mannykannot 11y ago
    I agree that it is interesting. For example, what if you can implement, in C, an interpreter for a language that has a bignum type? I am thinking along the lines of Greenspun's tenth rule (which I realize is not even close to a rigorous argument.)
    - aji 11y ago
      I'd say the interpreter is interpreting a non-Turing complete subset of the bignum language. That said, what is and isn't "Turing complete" is hardly relevant for practical purposes. C has obviously been very useful as a language, despite whatever theoretical statements can be proven about it.
      - mannykannot 11y ago
        It is not clear to me why it would be a subset (I'm assuming proper subset here) or why it would have to be non- Turing-complete. I agree that none of this has any obvious relevance to the practical usefulness of C, but all of us here in this thread have chosen to put that aside, at least for now, in order to contemplate a somewhat esoteric though less practical question.
        aji 11y ago
        The key distinction to note is the one between specifications and implementations. As a small example, consider Brainfuck. The Brainfuck specification (if such a thing exists) has no upper bound on the number of memory cells, but practical implementations generally do have a limit that "useful" Brainfuck programs will rarely hit. The specification describes a TC language, while the implementation does not. Therefore, if a language is TC according to its specification, but has an implementation in a language that is shown to not be TC, then it follows that the implementation must be of a non-TC subset of the language. This is, of course, assuming both that the specification has been proven TC, and that the implementing language has been proven non-TC. I believe the point being made in the paper is that the C specification itself is restrictive enough that it describes a non-TC language. In other words, any implementation of C that is truly Turing complete would be violating the specification in some way. In that case, it follows that a C implementation of a TC language (such as the bignum language) must only be an implementation of a non-TC subset of the language. (As an aside, consider that nothing running on an isolated machine will ever be truly TC, since an isolated machine has a finite amount of memory and so can't be TC. It's not that much of an inferential jump to see that this kind of TC-breaking limitation could end up in the specification of C, a language quite close to the metal.)
- cygx 11y ago
  Their reasoning why there cannot be strictly conforming implementations of the language is also like that: The C standard does not make any guarantees about the size of the call stack. But any program program needs to rely on this implementation-defined property (cf a pathological implementation were the initial call to main() already overflows) and thus cannot be strictly conforming.
  - tachyonbeam 11y ago
    It does come off as a bit pedantic though. What it comes down to, is that this specification was written by engineers and not mathematicians. These engineers didn't really care how (in)convenient it was to write proofs about the C semantics, they cared about the language being fast and easy to implement. In practice, any real-world C implementation will allow you to call the main function without overflowing the stack, and that much is obvious, otherwise nobody would use those implementations, so it should be taken as a a given, an axiom. Why doesn't the C standard guarantee a minimum stack size? Because there could be tiny microcontrollers with just 64 bytes of stack on which you can implement some C subset. At the same time, the standard doesn't want to define specifics of stack frame layouts, so, not knowing how much memory is available on your target machine, and not wanting to constrain how a stack frame for some source function is laid out as part of the C standard, it's impossible to compute how deep you can go on your call stack without architectural details, it's implementation dependent. It makes a lot of sense that the standard is the way it is, from an engineering point of view.
    - abecedarius 11y ago
      The problem with this apology for the standard -- that nobody would interpret it so unreasonably -- is that many programmers (like me) wrote programs assuming what seemed like reasonable bounds on how far compiler writers would go in their language lawyering, which a decade or two later got flouted, making our old code start mysteriously breaking, in a hard-to-figure way, only in the latest versions of the compilers, which at the time were notorious for compiler bugs. If you trust the same compiler writers to respect today's common idea of reasonable engineering tradeoffs, well, I hope it works out better for you.
- cmrx64 11y ago
  Just because it's irrelevant for real implementations doesn't mean it's not theoretically irrelevant. All of our computers can be modeled with sequential logic. That doesn't mean it's worthless to study more abstract properties.
- deadgrey19 11y ago
  Be careful: They did not say that C is not Turing complete. They say that the C Standard does not define a language which is Turing complete. There is a subtle distinction between these two statements, but an important one. The larger point that the paper is making is that the C Standard is full of holes. Thus as a programmer you cannot rely on any compiler that implements this "standard" to do anything (even trivial things like allocate enough memory on the stack). Yes, it probably will work most of the time, but will it work always? No, well, then it's not much of a standard, more of a set of loose guidelines. If you want to write secure, performant portable code: you need an actual standard. I think this is the point that the paper is making. Better still, it is highlighting the places where the standard is poorly defined so that it could be fixed.
cbd1984 11y ago
Next, they proved that the C standard didn't define a programming language but a variety of rutabaga, and died of starvation by trying to eat source code listings. Seriously. There's a basic concept involved here called "Quality Of Implementation" which effectively guarantees that the programs produced by a compiler will work as long as you stay within reasonable bounds. Might those bounds be a bit constrained on embedded systems? Sure. Them's the breaks. However, having a stack size of zero is not worth worrying about.

by adsche 11y ago

xorblurb 11y ago

Well at least the section explaining why they think C is not Turing complete is beyond ridiculous (TLDR: memory is not infinite so there exist a state machine... WTF????? technically mathematically true but has always been completely irrelevant when talking about real implementations) And it seems to be written with a serious tone, it is probably not even a joke!

Sniffnoy 11y ago
The point isn't that memory isn't infinite, but that C's memory model isn't infinite. There are other languages that do have an infinite memory model (for instance, any language with a builtin bignum type). I mean, if you want to judge ridiculousness, then their explanation of why there are no strictly conforming programs (specifically: even a program with an empty main function cannot be guaranteed not to overflow the stack) is also ridiculous, but it's still interesting.
- mannykannot 11y ago
  I agree that it is interesting. For example, what if you can implement, in C, an interpreter for a language that has a bignum type? I am thinking along the lines of Greenspun's tenth rule (which I realize is not even close to a rigorous argument.)
  - aji 11y ago
    I'd say the interpreter is interpreting a non-Turing complete subset of the bignum language. That said, what is and isn't "Turing complete" is hardly relevant for practical purposes. C has obviously been very useful as a language, despite whatever theoretical statements can be proven about it.
    - mannykannot 11y ago
      It is not clear to me why it would be a subset (I'm assuming proper subset here) or why it would have to be non- Turing-complete. I agree that none of this has any obvious relevance to the practical usefulness of C, but all of us here in this thread have chosen to put that aside, at least for now, in order to contemplate a somewhat esoteric though less practical question.
      - aji 11y ago
        The key distinction to note is the one between specifications and implementations. As a small example, consider Brainfuck. The Brainfuck specification (if such a thing exists) has no upper bound on the number of memory cells, but practical implementations generally do have a limit that "useful" Brainfuck programs will rarely hit. The specification describes a TC language, while the implementation does not. Therefore, if a language is TC according to its specification, but has an implementation in a language that is shown to not be TC, then it follows that the implementation must be of a non-TC subset of the language. This is, of course, assuming both that the specification has been proven TC, and that the implementing language has been proven non-TC. I believe the point being made in the paper is that the C specification itself is restrictive enough that it describes a non-TC language. In other words, any implementation of C that is truly Turing complete would be violating the specification in some way. In that case, it follows that a C implementation of a TC language (such as the bignum language) must only be an implementation of a non-TC subset of the language. (As an aside, consider that nothing running on an isolated machine will ever be truly TC, since an isolated machine has a finite amount of memory and so can't be TC. It's not that much of an inferential jump to see that this kind of TC-breaking limitation could end up in the specification of C, a language quite close to the metal.)
cygx 11y ago
Their reasoning why there cannot be strictly conforming implementations of the language is also like that: The C standard does not make any guarantees about the size of the call stack. But any program program needs to rely on this implementation-defined property (cf a pathological implementation were the initial call to main() already overflows) and thus cannot be strictly conforming.
- tachyonbeam 11y ago
  It does come off as a bit pedantic though. What it comes down to, is that this specification was written by engineers and not mathematicians. These engineers didn't really care how (in)convenient it was to write proofs about the C semantics, they cared about the language being fast and easy to implement. In practice, any real-world C implementation will allow you to call the main function without overflowing the stack, and that much is obvious, otherwise nobody would use those implementations, so it should be taken as a a given, an axiom. Why doesn't the C standard guarantee a minimum stack size? Because there could be tiny microcontrollers with just 64 bytes of stack on which you can implement some C subset. At the same time, the standard doesn't want to define specifics of stack frame layouts, so, not knowing how much memory is available on your target machine, and not wanting to constrain how a stack frame for some source function is laid out as part of the C standard, it's impossible to compute how deep you can go on your call stack without architectural details, it's implementation dependent. It makes a lot of sense that the standard is the way it is, from an engineering point of view.
  - abecedarius 11y ago
    The problem with this apology for the standard -- that nobody would interpret it so unreasonably -- is that many programmers (like me) wrote programs assuming what seemed like reasonable bounds on how far compiler writers would go in their language lawyering, which a decade or two later got flouted, making our old code start mysteriously breaking, in a hard-to-figure way, only in the latest versions of the compilers, which at the time were notorious for compiler bugs. If you trust the same compiler writers to respect today's common idea of reasonable engineering tradeoffs, well, I hope it works out better for you.
cmrx64 11y ago
Just because it's irrelevant for real implementations doesn't mean it's not theoretically irrelevant. All of our computers can be modeled with sequential logic. That doesn't mean it's worthless to study more abstract properties.
deadgrey19 11y ago
Be careful: They did not say that C is not Turing complete. They say that the C Standard does not define a language which is Turing complete. There is a subtle distinction between these two statements, but an important one. The larger point that the paper is making is that the C Standard is full of holes. Thus as a programmer you cannot rely on any compiler that implements this "standard" to do anything (even trivial things like allocate enough memory on the stack). Yes, it probably will work most of the time, but will it work always? No, well, then it's not much of a standard, more of a set of loose guidelines. If you want to write secure, performant portable code: you need an actual standard. I think this is the point that the paper is making. Better still, it is highlighting the places where the standard is poorly defined so that it could be fixed.

cbd1984 11y ago

Next, they proved that the C standard didn't define a programming language but a variety of rutabaga, and died of starvation by trying to eat source code listings. Seriously. There's a basic concept involved here called "Quality Of Implementation" which effectively guarantees that the programs produced by a compiler will work as long as you stay within reasonable bounds. Might those bounds be a bit constrained on embedded systems? Sure. Them's the breaks. However, having a stack size of zero is not worth worrying about.