5 ms·

I would argue that C's fundamental mistake (well, more like limitation due to hardware of the time) was allowing arrays to decay to pointers; arrays hold valua

I would argue that C's fundamental mistake (well, more like limitation due to hardware of the time) was allowing arrays to decay to pointers; arrays hold valuable type information (the length!) that is lost once converted to a pointer. C99 came so very very close with VLAs. You can declare a function like: int main(int argc, char *argv[argc]) { ... } But C99 requires the compiler to discard the type annotations and treat the declaration as equivalent to: int main(int argc, char **argv) { ... } Imagine a world where the C string functions were declared as: char *strndup(s, n) const char *s[n]; size_t n; { /* now we can do sizeof(s) and bounds checking! */ } (You'd have to use K&R style declarations to get around the fact that the pointer argument comes before the length argument, alas.) Edit: and then C11 made VLA support optional, since the feature didn't get used much, because the feature was only half-baked to begin with... sigh.

moonchild 6y ago
It's because to get that to actually work you need dependent types. Which—it's not gonna happen.
- kiwidrew 6y ago
  But the caller to strnlen() has already provided both the (pointer to the) array and the length! Note that C99 does permit declaring a VLA in the body of the function: char *strndup(size_t n; const char *s[n], size_t n) { char buf[n]; /* alloc a temporary VLA */ assert(sizeof(buf) == n); /* yep! */ assert(sizeof(s) == n); /* nope, sizeof(s) == 1 */ } So there's absolutely no reason (other than being in violation of the C99 specification) for the compiler to refuse to let you make the assertion that sizeof(s) == n. And given the prototype for this VLA-enhanced strndup(), a smart C compiler could catch errors like this: char * bugged_func() { char buf[20]; /* do stuff with buf, e.g. snprintf() into it */ return strndup(buf, 30); /* error: 30 > sizeof(buf) */ } Since of course within a function the C type system is already tracking the size of an array -- so no additional type information is required, and certainly not dependent types!
  - moonchild 6y ago
    With standard VLAs, you always have a guarantee of being able to access sizeof(buf) bytes from buf, for any variable buf. With your syntax, that guarantee would no longer hold, unless c had dependent types that could prove said guarantee.
    - kiwidrew 6y ago
      Well, given that C is fundamentally about separate compilation and external linkage, most "guarantees" in the language are really just promises or contracts. As demonstrated in david2ndaccount's comment, standard C already handles VLA function arguments just fine (without any need for dependent types). The only issue is that C99 insists that the first dimension of an array argument must decay to a pointer, discarding the associated type information of that array's dimension.
- ufo 6y ago
  We wouldn't need to go all the way to dependent types, which would guarantee at compile-time that array accesses are safe. Even if all the bounds checking happened at run-time it would still be tremendously helpful.
  - moonchild 6y ago
    Bounds checking can be done, and it doesn't need any special language features. Tcc does it, as do some of the sanitizers (present in gcc and clang).
    - ufo 6y ago
      Can you bounds check dynamically sized arrays? For example, a function that receives the size as a separate argument? double f(double *xs, int n){ return xs[g()]; }
      - kiwidrew 6y ago
        Yes. In my hypothetical world where the C compiler makes use of the VLA declaration in the function arguments, it would certainly be possible for the compiler to insert automatic bounds checking in this case: double f(xs, n) double xs[n]; size_t n; { size_t _tmp0 = g(); /* temporary var created by compiler */ assert(_tmp0 < n); /* bounds check inserted by compiler */ return xs[_tmp0]; } The key to making this possible is telling the compiler about the relationship between double* xs and size_t n; once the compiler has the knowledge that the type of xs is double [n] (array of double with first dimension n) it would be able to automatically insert dynamic bounds checks.
      - moonchild 6y ago
        > dynamically sized arrays Yes. What you can't do is associate bounds information with some specific pointer to an array, but this will work, for instance: int *x = malloc(2 * sizeof(int)); x[1]; //ok x[2]; //runtime error
MaxBarraclough 6y ago
See WalterBright's 2009 blog post, C’s Biggest Mistake, about exactly this. https://digitalmars.com/articles/C-biggest-mistake.html https://digitalmars.com/articles/C-biggest-mistake.html
- kiwidrew 6y ago
  Ah, indeed! Thanks for the link. I think many of the "safe C" variants get tripped up by starting with fat pointers (length + pointer as an atomic value) and then have trouble (rightly so!) when trying to squeeze them through the C standard ABI; it's a square peg in round hole sort of situation. The key observation from WalterBright's post is that the C standard ABI already has a way to pass fat pointers, using a pair of arguments (size_t and char *) in an ad-hoc manner. It's the not-useful-but-legal C99 VLA declaration in the function prototype that could, if one is willing to violate the C99 spec, allow a compiler to automatically derive a fat pointer inside the body of a function in a manner that is backwards-compatible with the C standard ABI.
david2ndaccount 6y ago
What you want works, you just used the wrong syntax: #include <stdio.h> void foo(int len, const char (*str)[len]){ printf("%zu\n", sizeof(*str)); printf("%.*s", len, *str); } int main(void){ // note: not nul-terminated const char text[] = {'h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', '!', '\n'}; // prints 13, then 'hello world!' foo(sizeof(text), &text); return 0; }
- kiwidrew 6y ago
  Why yes, yes it does! I did know (but seem to have forgotten) that it's only the first level of array-ness that decays to a pointer. It's unfortunate that the resulting VLA-enhanced function is no longer compatible with the original: /* original function */ void foo(size_t len, const char *str); /* compatible signature but str[] decays to sizeless pointer */ void foo(size_t len, const char str[len]); /* allowed but signature is no longer compatible with original */ void foo_improved(size_t len, const char (*str)[len]); /* (this is how the non-VLA caller would see the signature) */ void foo_improved(size_t len, const char **str); So what your example does show is that existing compilers already support this concept (no need for fancy dependent types) but the C99 standard explicitly prohibits compilers from acting on the VLA information contained within the const char str[len] declaration.
int_19h 6y ago
It wasn't a limitation due to hardware of the time. It was a deliberate choice due to C's ancestry as a derivative of B. In B, thee was only one data type: machine word. The actual meaning was determined by the operators used on it. Thus, given x, (x + 1) would be integer addition, but *x would dereference it as a pointer (to another word). There was no need to distinguish between integer and pointer arithmetic, because their semantics was the same - pointers were not memory addresses of bytes, but of words, and thus (x + 1) would also mean "the next element after x", if x is actually a pointer. When it came to arrays, B didn't have them as a type at all. It did have array declarations - but what they did was allocate the memory, and give you a variable of the usual word type pointing at that memory (which could be reassigned!). Thus, arrays "decayed" to pointers, but in a broader sense they did in C. This all works fine on machine where everything is a word, and only words are addressable. But C needed to run on byte-addressable architectures, hence why it needed different types, and specifically pointer types to allow for pointer arithmetic - as something like (p + 1) needs to shift the address by more than 1 byte, depending on the type of p. But they still tried to preserve the original B behavior of being able to treat arrays as pointers seamlessly, hence the decay semantics. BTW, this ancestry explains some other idiosyncracies of C. For example, the fact that array/pointer indexing operator can have its operands ordered either way - both a[42] and 42[a] are equally valid - is also straight from B. A more obvious example, the reason why C originally allowed you to omit variable types altogether, and assumed int in that case, is because int is basically the "word type" of B, and thus C code written in this manner very much resembles B. And then there's "auto" which was needed in B to declare locals because there was no type, but became redundant (and yet preserved) in C. https://en.wikipedia.org/wiki/B_(programming_language)#Examples https://en.wikipedia.org/wiki/B_(programming_language)#Examp...

moonchild 6y ago

It's because to get that to actually work you need dependent types. Which—it's not gonna happen.

kiwidrew 6y ago
But the caller to strnlen() has already provided both the (pointer to the) array and the length! Note that C99 does permit declaring a VLA in the body of the function: char *strndup(size_t n; const char *s[n], size_t n) { char buf[n]; /* alloc a temporary VLA */ assert(sizeof(buf) == n); /* yep! */ assert(sizeof(s) == n); /* nope, sizeof(s) == 1 */ } So there's absolutely no reason (other than being in violation of the C99 specification) for the compiler to refuse to let you make the assertion that sizeof(s) == n. And given the prototype for this VLA-enhanced strndup(), a smart C compiler could catch errors like this: char * bugged_func() { char buf[20]; /* do stuff with buf, e.g. snprintf() into it */ return strndup(buf, 30); /* error: 30 > sizeof(buf) */ } Since of course within a function the C type system is already tracking the size of an array -- so no additional type information is required, and certainly not dependent types!
- moonchild 6y ago
  With standard VLAs, you always have a guarantee of being able to access sizeof(buf) bytes from buf, for any variable buf. With your syntax, that guarantee would no longer hold, unless c had dependent types that could prove said guarantee.
  - kiwidrew 6y ago
    Well, given that C is fundamentally about separate compilation and external linkage, most "guarantees" in the language are really just promises or contracts. As demonstrated in david2ndaccount's comment, standard C already handles VLA function arguments just fine (without any need for dependent types). The only issue is that C99 insists that the first dimension of an array argument must decay to a pointer, discarding the associated type information of that array's dimension.
ufo 6y ago
We wouldn't need to go all the way to dependent types, which would guarantee at compile-time that array accesses are safe. Even if all the bounds checking happened at run-time it would still be tremendously helpful.
- moonchild 6y ago
  Bounds checking can be done, and it doesn't need any special language features. Tcc does it, as do some of the sanitizers (present in gcc and clang).
  - ufo 6y ago
    Can you bounds check dynamically sized arrays? For example, a function that receives the size as a separate argument? double f(double *xs, int n){ return xs[g()]; }
    - kiwidrew 6y ago
      Yes. In my hypothetical world where the C compiler makes use of the VLA declaration in the function arguments, it would certainly be possible for the compiler to insert automatic bounds checking in this case: double f(xs, n) double xs[n]; size_t n; { size_t _tmp0 = g(); /* temporary var created by compiler */ assert(_tmp0 < n); /* bounds check inserted by compiler */ return xs[_tmp0]; } The key to making this possible is telling the compiler about the relationship between double* xs and size_t n; once the compiler has the knowledge that the type of xs is double [n] (array of double with first dimension n) it would be able to automatically insert dynamic bounds checks.
    - moonchild 6y ago
      > dynamically sized arrays Yes. What you can't do is associate bounds information with some specific pointer to an array, but this will work, for instance: int *x = malloc(2 * sizeof(int)); x[1]; //ok x[2]; //runtime error

MaxBarraclough 6y ago

See WalterBright's 2009 blog post, C’s Biggest Mistake, about exactly this. https://digitalmars.com/articles/C-biggest-mistake.html https://digitalmars.com/articles/C-biggest-mistake.html

kiwidrew 6y ago
Ah, indeed! Thanks for the link. I think many of the "safe C" variants get tripped up by starting with fat pointers (length + pointer as an atomic value) and then have trouble (rightly so!) when trying to squeeze them through the C standard ABI; it's a square peg in round hole sort of situation. The key observation from WalterBright's post is that the C standard ABI already has a way to pass fat pointers, using a pair of arguments (size_t and char *) in an ad-hoc manner. It's the not-useful-but-legal C99 VLA declaration in the function prototype that could, if one is willing to violate the C99 spec, allow a compiler to automatically derive a fat pointer inside the body of a function in a manner that is backwards-compatible with the C standard ABI.

david2ndaccount 6y ago

What you want works, you just used the wrong syntax: #include <stdio.h> void foo(int len, const char (*str)[len]){ printf("%zu\n", sizeof(*str)); printf("%.*s", len, *str); } int main(void){ // note: not nul-terminated const char text[] = {'h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', '!', '\n'}; // prints 13, then 'hello world!' foo(sizeof(text), &text); return 0; }

kiwidrew 6y ago
Why yes, yes it does! I did know (but seem to have forgotten) that it's only the first level of array-ness that decays to a pointer. It's unfortunate that the resulting VLA-enhanced function is no longer compatible with the original: /* original function */ void foo(size_t len, const char *str); /* compatible signature but str[] decays to sizeless pointer */ void foo(size_t len, const char str[len]); /* allowed but signature is no longer compatible with original */ void foo_improved(size_t len, const char (*str)[len]); /* (this is how the non-VLA caller would see the signature) */ void foo_improved(size_t len, const char **str); So what your example does show is that existing compilers already support this concept (no need for fancy dependent types) but the C99 standard explicitly prohibits compilers from acting on the VLA information contained within the const char str[len] declaration.

int_19h 6y ago

It wasn't a limitation due to hardware of the time. It was a deliberate choice due to C's ancestry as a derivative of B. In B, thee was only one data type: machine word. The actual meaning was determined by the operators used on it. Thus, given x, (x + 1) would be integer addition, but *x would dereference it as a pointer (to another word). There was no need to distinguish between integer and pointer arithmetic, because their semantics was the same - pointers were not memory addresses of bytes, but of words, and thus (x + 1) would also mean "the next element after x", if x is actually a pointer. When it came to arrays, B didn't have them as a type at all. It did have array declarations - but what they did was allocate the memory, and give you a variable of the usual word type pointing at that memory (which could be reassigned!). Thus, arrays "decayed" to pointers, but in a broader sense they did in C. This all works fine on machine where everything is a word, and only words are addressable. But C needed to run on byte-addressable architectures, hence why it needed different types, and specifically pointer types to allow for pointer arithmetic - as something like (p + 1) needs to shift the address by more than 1 byte, depending on the type of p. But they still tried to preserve the original B behavior of being able to treat arrays as pointers seamlessly, hence the decay semantics. BTW, this ancestry explains some other idiosyncracies of C. For example, the fact that array/pointer indexing operator can have its operands ordered either way - both a[42] and 42[a] are equally valid - is also straight from B. A more obvious example, the reason why C originally allowed you to omit variable types altogether, and assumed int in that case, is because int is basically the "word type" of B, and thus C code written in this manner very much resembles B. And then there's "auto" which was needed in B to declare locals because there was no type, but became redundant (and yet preserved) in C. https://en.wikipedia.org/wiki/B_(programming_language)#Examples https://en.wikipedia.org/wiki/B_(programming_language)#Examp...