Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

lemon.rip

Post reply on HN
Print view View original

41–50 of 257 posts

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

#41

Post by camel-cdr »

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 what I can tell, the only way you could theoretically access an infinite tape is using `fseek` with `SEEK_CUR`.

There might be more shenanigans possible with `stdio.h`, but I'm pretty sure C can't be Turing complete without the `stdio.h` function (assuming no special language extensions).

If anybody is wondering, the preprocessor isn't Turing complete either, because you might theoretically have infinite memory, but then you only have finite recursion, which also isn't enough for Turing completeness. File iteration can have infinite recursion, but can also only carry over finite state between `#include`s.

Edit: I'm not talking about any real world implementation, but rather about the theoretical bounds of the C abstract machine.

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

#43

Post by [deleted] »

ufo wrote: post #11

They mention that while loops are limited because C doesn't have tail recursion. However, in my experience gcc and clang are pretty decent at tail recursion. It happens via the -foptimize-sibling-calls setting, which is enabled by default on -O2 or higher. The caveat is that the standard doesn't guarantee these optimizations. But there are some non-standard __attribute__ declarations that can help with that.

[deleted]

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

#44

Post by einpoklum »

planede wrote: post #38
pjmlp wrote: post #37

Earlier quoted context omitted.

Syntax, no protection against stack corruption,...

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

With VLAs:

1. The stack-smashing pattern is simple, straightforward and sure to be used often. Other ways to smash the stack require some more "effort"...

2. It's not just _you_ who can smash the stack. It's the fact that anyone who calls your function will smash the stack if they pass some large numeric value.

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

#45

Post by chucksmash »

mrkeen wrote: post #28
SavageBeast wrote: post #26

Earlier quoted context omitted.

On the topic of "compile time optimization" ... There was once a merry bunch of very excellent and brilliant crack smokers at Google who created a project called GWT. The raison d'etre of the project was simply "We know you can write JS but Java has more guardrails - why don't you write Java and we'll transpile it down to better JS than you're smart enough to write because JS basically sucks and is always changing an…

> People who seek to write one language and execute another are fundamentally insane. That would be people who use compilers.

You're technically right, which is the best kind of not invited to happy hour.

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

#46

Post by hxtk »

tooltower wrote: post #24
jmount wrote: post #21

Earlier quoted context omitted.

I agree. The incredibly semantics-hostile optimizer ("undefined means I can do anything", whereas in old C "undefined" just mean you were no longer sure what number was the result of an overflow) just takes the cake.

What old C do you mean? I can't think of any version where undefined had a defined meaning

Not defined as part of the standard, but before compilers got as smart about their optimizations, it was easier to have behavior that was technically undefined but could be reasoned about in practice.

Now that compilers know cleverer optimizations, undefined behavior is often impossible to reason about because the compiler can change your logic into something else that is more optimal and is equivalent to your logic only in well-defined cases.

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

#47

Post by ynfnehf »

pjmlp wrote: post #39
ynfnehf wrote: post #31

Earlier quoted context omitted.

This usage of VLAs is once again mandatory for compilers to support, since C23. From Wikipedia: "Variably-modified types (but not VLAs which are automatic variables allocated on the stack) become a mandatory feature".

Oh well...

At least it is still optional to allow for stack allocated VLAs. Which is the attack vector you mentioned.

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

#48

Post by dmitrygr »

camel-cdr wrote: post #41

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…

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 amount of memory that exists we approximate and say they are Turing machines since there is enough memory to do most what we need.

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

#49

Post by munificent »

camel-cdr wrote: post #41

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…

You could just make a doubly-linked list that dynamically grows new nodes (using malloc()) at either end on demand in order to implement an infinite tape.

(Of course on a real machine the malloc() will fail at some point.)

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

#50

Post by arcbyte »

camel-cdr wrote: post #41

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…

You are pedantically correct and wrong. Even with fseek there are only so many atoms in the universe and you'd eventually run into limited memory. Rather than go so esoteric as to say that only programs structured with fseek are Turing complete, we generally just make the jump from languages able to use arbitrarily sized RAM to assuming infinite RAM and say youre turing complete enough for most purposes.
Post reply on HN