Live data from Hacker News

C99 doesn't need function bodies, or 'VLAs are Turing complete'

lemon.rip

71–80 of 257 posts

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#71
post #40
post #38

Earlier quoted context omitted.

You can corrupt the stack without VLAs just fine. What else?

What about not adding even more ways how we should avoid using C?

> What about not adding even more ways how we should avoid using C?

That's a mute point for C's target audience because they already understand that they need to be mindful of what the language does.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#72

Earlier quoted context omitted.

> Even with fseek there are only so many atoms in the universe and you'd eventually run into limited memory I should've explained that I'm not talking about a physical implementation, but about the theoretical bounds of the C abstract machine.

Talking theoretically, since size_t is defined as: > size_t can store the maximum size of a theoretically possible object of any type (including array). In a proper theoretical turing machine, size_t would allow you to create and address arbitrarily large arrays too.

`sizeof(size_t)` and `size_t x; sizeof x` must be constant expressions. It is possible to create a c implementation where the size of a pointer is arbitrarily large, but it can't grow/isn't infinite.

For any give C implementation, it is thus trivial to theoretically solve the halting problem (assuming no stdio.h stuff is used).

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#73
post #3

Similar to making all your computations in the expressions for default arguments in python (and/or C++) and leaving the function bodies empty. Fancy, but not that mindboggling. What may surprise people is how and when these expressions are evaluated since they differ between languages.

It might not be mind-boggling , but it is highly unusual to people who "think in C". This is not C! This kind of stuff is why purists stick to C89. I'm uneasy about variable-length arrays at the best of times. It hadn't even occurred to me that you might have a variable-length array as a function argument.

Oh, but designated initializers are so useful!

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#74

Earlier quoted context omitted.

Pointer++ Pointer—- These do the same to pointers…

No, pointers always have a finite size, because sizeof is a constant expression. A theoretically fseek isn't bound by this, the compiler could implement it with an infinite tape.

A pointer is just a number that points to addressable memory. Pointers don't even point to actual memory these days anyways. They're just glorified indices into OS tables that eventually map to actual memory. You can increase a pointer to be 128 bits big, or 256 bits big if you wanted to. It doesn't change anything, because it's just an index.

Here's a clarification on Wikipedia that expands on this:

> nearly all programming languages are Turing complete if the limitations of finite memory are ignored.

And files are just as finite as a pointer. You can't address a location in a file bigger than sizeof(void*) on a modern computer. If you wanted to, you would need to add special support[1] and doing this is equivalent to what you would do to support a bigger memory range for pointers.

I'm curious, do you think other languages are Turing complete? As far as I know, all modern programming languages use a 64 bit addressable memory space maximum.

[0]: https://en.m.wikipedia.org/wiki/Turing_machine

[1]: https://stackoverflow.com/questions/4933561/what-is-the-rela...

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#75
post #3

Similar to making all your computations in the expressions for default arguments in python (and/or C++) and leaving the function bodies empty. Fancy, but not that mindboggling. What may surprise people is how and when these expressions are evaluated since they differ between languages.

It might not be mind-boggling , but it is highly unusual to people who "think in C". This is not C! This kind of stuff is why purists stick to C89. I'm uneasy about variable-length arrays at the best of times. It hadn't even occurred to me that you might have a variable-length array as a function argument.

> This is not C! This kind of stuff is why purists stick to C89.

This personal assertion holds no water.

People hold/held onto C89 because compilers like Visual Studio's C compiler failed to support anything beyond C89 for ages.

https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-...

It's my understanding that Microsoft adopted a role in the C standardization committee that was a kin to sabotaging any update beyond C89.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#76

This is only tangential to the article: C isn't Turing complete without `fseek` (as far as I can tell). Turing completes requires you to be able to read/write from an infinite tape (essentially infinite memory). This isn't possible in C, because `sizeof` is a constant expression, thus limiting the size of any type, and importantly also pointer type, to a finite number, thus making the addressable memory finite. From…

[deleted]

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#78

Earlier quoted context omitted.

Your argument sort of imploded on itself…your claim that only a file can be considered tape is insane because memory is just as usable as tape and you can keep extending memory available to you using sbrk() . If you’re going to claim the memory is finite, well so are files. (Also lseek is not part of any C spec) And yes neither is infinite, so every computer is just a DFA, and lseek changes nothing. But given the amo…

My argument is that `fseek` (not `lseek`) is the only way for standard C to access a infinite tape, because it allows relative seeking in a file. `fseek(file, 1, SEEK_CUR)` to advance and `fseek(file, -1, SEEK_CUR)` to go back.

The tape wouldn't have to be provided as a single flat file. You could, for instance, use something like a pair of files, one for control and one for data:

    fputc('L', tape_control);
    c = fgetc(tape_data);
    fputc(d, tape_data);
or a single file with controls disjoint from the tape symbols.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#79
post #3

Earlier quoted context omitted.

It might not be mind-boggling , but it is highly unusual to people who "think in C". This is not C! This kind of stuff is why purists stick to C89. I'm uneasy about variable-length arrays at the best of times. It hadn't even occurred to me that you might have a variable-length array as a function argument.

Serious question, but what "purists" remain on ANSI C? Even Linux has abandoned it as of 5.19. The only times I use it are when I'm writing something that requires ridiculous portability even to bizarre platforms and compilers. C99 is far more ergonomic in comparison, even if you have to avoid using some of the truly terrible design decisions that came along for the ride.

> Serious question, but what "purists" remain on ANSI C?

It means nothing. It's a baseless attemt at an appeal to authority that has no merit.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#80
post #9

This kind of insanity is exactly why I don't use stuff like C anymore. It's a landmark and incredible language, but it's chock full of potholes and foot-shotguns (footguns that blow off your entire leg). Even huge companies can't get it right, which makes sense. It started as a language basically without guardrails, and because of the extreme deference to the holy backward compatibility, it's more or less always goin…

I think that's more of an issue with C++.

Usually developers stick to known patterns and subsets. Sure, you can write "clever" code that's more aproppriate for IOCCC than as system-critical code, but that's the case with most programming languages.

There is such a thing as "bad code" and "good code". A lot of code linters can catch "code smells", and features can often be disabled at the compiler level.

On the other hand, not having to resort to inline assembler or writing 500x the amount of code in some cases is why we have such features. Complex features are useful in some (complex) cases, but are not to be overused.

Post reply on HN