4 ms·

IMO the lack of a complexity requirement is a bug in the C standard. And really it’s a bug in the implementation(s?) too. If it can be done on O(1), shame on li

IMO the lack of a complexity requirement is a bug in the C standard. And really it’s a bug in the implementation(s?) too. If it can be done on O(1), shame on library authors for doing it in O(n). If you want programmers to trust library authors, don’t do this to us. Maybe std::from_chars FTW?

ironmagma 6y ago
Shouldn’t we just come clean and admit to ourselves that there is no such thing as the C standard? There is a collection of loosely related languages that look similar and that collectively we call C, but really they’re all completely different and share almost no interoperability or common characteristics. And those standards that do exist provide almost no ability to reason about your code including things like ordering of statements.
- loeg 6y ago
  No, that's complete nonsense. Here's the latest revision of the standard: https://www.iso.org/standard/74528.html https://www.iso.org/standard/74528.html C has had a well-defined memory model since C11, I believe (re: "ordering of statements").
  - ironmagma 6y ago
    > ISO-C11 specifies 203 circumstances that cause undefined behaviors. 203 is enough to make almost every line of code questionable. The result of this is that looking at a simple 3 line C program and being asked whether the program terminates is undecidable without knowing which compiler was used. Null dereference for example is undefined behavior, and could cause a termination or not, depending on the implementation, even if it is known to be standards conforming to C11. [1] https://resources.tasking.com/p/undefined-behaviors-iso-c-their-effect-your-embedded-software-part-1 https://resources.tasking.com/p/undefined-behaviors-iso-c-th...
    - ncmncm 6y ago
      A good argument for compiling your debug builds with "-fsanitize=undefined".
      - loeg 6y ago
        Sure, or use Rust! Rust is great! We can criticize C for its faults without making baseless claims.
      - ironmagma 6y ago
        There is always a fix for your own code but that’s not the problem. The issue is all the millions of lines of code in the wild that are intended to be compiled without that option.
    - loeg 6y ago
      > 203 is enough to make almost every line of code questionable. The result of this is that looking at a simple 3 line C program and being asked whether the program terminates is undecidable without knowing which compiler was used. This is hyperbole to the point of being nonsensical. > Null dereference for example is undefined behavior, and could cause a termination or not, depending on the implementation, even if it is known to be standards conforming to C11. This sentence doesn't make any sense. If your C code has UB, it is wrong. The behavior of particular environments around certain UB is irrelevant to standards-conforming code, because standards-conforming code doesn't have UB.
      - ironmagma 6y ago
        > If your C code has UB, it is wrong. This goes against the sheer notion of UB. If some code was wrong, the standard would say it is not allowed and it would result in a compile error, or at least a runtime error. As it is, the language standards choose to leave it open almost as if to concede that the standard can’t cover every base. UB isn’t wrong, almost by definition. It’s just implementation specific, and that’s my point. We don’t have an overarching C language, we have a hundred or so C dialects.
  - progre 6y ago
    There is a standard, sure. But there are also a lot of compilers out there and I would bet that all but a few has either a "this compiles c11 except for [list of unimplemented features]" caveat or non-standard extensions.
    - loeg 6y ago
      > But there are also a lot of compilers out there and I would bet that all but a few has either a "this compiles c11 except for [list of unimplemented features]" caveat or non-standard extensions. Your statement is broadly reasonable. Here's the GP: > Shouldn’t we just come clean and admit to ourselves that there is no such thing as the C standard? There is a collection of loosely related languages that look similar and that collectively we call C, but really they’re all completely different and share almost no interoperability or common characteristics. And those standards that do exist provide almost no ability to reason about your code including things like ordering of statements. It's just a string of incorrect statements, or at best, extreme hyperbole. 1. There is a C standard. 2. There's only one C language. Implementations differ, but not "completely," and are mostly interoperable. They all have in common the standard language, of course. 3. The C standard provides a fairly strong mental model for reasoning about code. Especially in later revisions, but even in C99. "Almost no ability to reason about" is false. If you think C is fragmented or difficult to reason about, let me introduce you to Python (Python3, Jython, PyPy), Java (Oracle, OpenJDK, Dalvik), C# (Mono, .NET Core, .NET on Windows...), C++ (if you think implementing C99-C18 is hard, check out the stdlib required by modern versions of C++), etc.
      - blackoil 6y ago
        Don't know about C, but In Java/C#/Python, you have a standard, a dominant implementation which is compliant to that standard. Few more independent/niche implementations which may not be 100% compliant. Do we have a similar implementation in C?
        loeg 6y ago
        I think you're maybe overstating the degree of homogeneity in Java/C#/Python. E.g., CPython3 cannot run Python2 code at all, and there are a lot of platform-specific modules and behaviors in the stdlib ("import os"). I don't think Python has any real single standard to the level of detail that C does, although I may be mistaken. For C, on approximately the same platforms, to approximately the same degree: either GCC or Clang would be the corresponding standard-compliant implementation.
deleted 6y ago
[deleted]
quelsolaar 6y ago
This is not a complexity issue with the function. The function is linear to the input, as it should be. The problem is that the implementation does more work then it needs to (it doesn't need the length of the string). It should be linear to the end of parsing not the end of string. The complexity in this case comes from the loops calling it.

ironmagma 6y ago

Shouldn’t we just come clean and admit to ourselves that there is no such thing as the C standard? There is a collection of loosely related languages that look similar and that collectively we call C, but really they’re all completely different and share almost no interoperability or common characteristics. And those standards that do exist provide almost no ability to reason about your code including things like ordering of statements.

loeg 6y ago
No, that's complete nonsense. Here's the latest revision of the standard: https://www.iso.org/standard/74528.html https://www.iso.org/standard/74528.html C has had a well-defined memory model since C11, I believe (re: "ordering of statements").
- ironmagma 6y ago
  > ISO-C11 specifies 203 circumstances that cause undefined behaviors. 203 is enough to make almost every line of code questionable. The result of this is that looking at a simple 3 line C program and being asked whether the program terminates is undecidable without knowing which compiler was used. Null dereference for example is undefined behavior, and could cause a termination or not, depending on the implementation, even if it is known to be standards conforming to C11. [1] https://resources.tasking.com/p/undefined-behaviors-iso-c-their-effect-your-embedded-software-part-1 https://resources.tasking.com/p/undefined-behaviors-iso-c-th...
  - ncmncm 6y ago
    A good argument for compiling your debug builds with "-fsanitize=undefined".
    - loeg 6y ago
      Sure, or use Rust! Rust is great! We can criticize C for its faults without making baseless claims.
    - ironmagma 6y ago
      There is always a fix for your own code but that’s not the problem. The issue is all the millions of lines of code in the wild that are intended to be compiled without that option.
  - loeg 6y ago
    > 203 is enough to make almost every line of code questionable. The result of this is that looking at a simple 3 line C program and being asked whether the program terminates is undecidable without knowing which compiler was used. This is hyperbole to the point of being nonsensical. > Null dereference for example is undefined behavior, and could cause a termination or not, depending on the implementation, even if it is known to be standards conforming to C11. This sentence doesn't make any sense. If your C code has UB, it is wrong. The behavior of particular environments around certain UB is irrelevant to standards-conforming code, because standards-conforming code doesn't have UB.
    - ironmagma 6y ago
      > If your C code has UB, it is wrong. This goes against the sheer notion of UB. If some code was wrong, the standard would say it is not allowed and it would result in a compile error, or at least a runtime error. As it is, the language standards choose to leave it open almost as if to concede that the standard can’t cover every base. UB isn’t wrong, almost by definition. It’s just implementation specific, and that’s my point. We don’t have an overarching C language, we have a hundred or so C dialects.
- progre 6y ago
  There is a standard, sure. But there are also a lot of compilers out there and I would bet that all but a few has either a "this compiles c11 except for [list of unimplemented features]" caveat or non-standard extensions.
  - loeg 6y ago
    > But there are also a lot of compilers out there and I would bet that all but a few has either a "this compiles c11 except for [list of unimplemented features]" caveat or non-standard extensions. Your statement is broadly reasonable. Here's the GP: > Shouldn’t we just come clean and admit to ourselves that there is no such thing as the C standard? There is a collection of loosely related languages that look similar and that collectively we call C, but really they’re all completely different and share almost no interoperability or common characteristics. And those standards that do exist provide almost no ability to reason about your code including things like ordering of statements. It's just a string of incorrect statements, or at best, extreme hyperbole. 1. There is a C standard. 2. There's only one C language. Implementations differ, but not "completely," and are mostly interoperable. They all have in common the standard language, of course. 3. The C standard provides a fairly strong mental model for reasoning about code. Especially in later revisions, but even in C99. "Almost no ability to reason about" is false. If you think C is fragmented or difficult to reason about, let me introduce you to Python (Python3, Jython, PyPy), Java (Oracle, OpenJDK, Dalvik), C# (Mono, .NET Core, .NET on Windows...), C++ (if you think implementing C99-C18 is hard, check out the stdlib required by modern versions of C++), etc.
    - blackoil 6y ago
      Don't know about C, but In Java/C#/Python, you have a standard, a dominant implementation which is compliant to that standard. Few more independent/niche implementations which may not be 100% compliant. Do we have a similar implementation in C?
      - loeg 6y ago
        I think you're maybe overstating the degree of homogeneity in Java/C#/Python. E.g., CPython3 cannot run Python2 code at all, and there are a lot of platform-specific modules and behaviors in the stdlib ("import os"). I don't think Python has any real single standard to the level of detail that C does, although I may be mistaken. For C, on approximately the same platforms, to approximately the same degree: either GCC or Clang would be the corresponding standard-compliant implementation.

deleted 6y ago

[deleted]

quelsolaar 6y ago

This is not a complexity issue with the function. The function is linear to the input, as it should be. The problem is that the implementation does more work then it needs to (it doesn't need the length of the string). It should be linear to the end of parsing not the end of string. The complexity in this case comes from the loops calling it.