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

61–70 of 257 posts

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

#61

Post by fhars »

addaon wrote: post #29
charcircuit wrote: post #20

>The astute reader might point out that these two versions of sum are not equivalent because the recursive definition may cause a stack overflow for large enough values of n. This is unfortunately true, and the major hurdle for the practicality of disembodied C, but does not preclude Turing completeness (an ideal Turing machine has infinite memory at its disposal). It does preclude Turing completeness. The stack has…

Does it actually? Or does the number of elements on the stack /that you have taken the address of/ have that upper bound? That is, could you build a compliant C implementation that implements a stack using an infinite memory (e.g. in a delay loop between the user and a mirror moving away through space), where each entry in the stack contains a convenient sized value (word, byte, whatever) and a tag? If the tag is cle…

Yes it does, C is defined in term of implementation defined, but finite sized pointers and integers, so the computational model of C is a finite state machine. But the size of the state space is so friggin' HUGE that that argument is completely irrelevant for all practical purposes.

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

#62

Post by a-dub »

josefx wrote: post #12
AshamedCaptain wrote: post #2

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.

> What may surprise people is how and when these expressions are evaluated since they differ between languages. What could possibly be surprising about reusing the exact same object on every function call, especially when you default to an empty list, set or dict. Getting an actual empty list is as easy as defaulting to None and explicitly checking for it, so there isn't even a reason to do it any differently. /s Who…

i don't think it's a matter of someone thinking it was sane behavior, it's just what falls out from the rest of the rules of the language. it seems that any attempt to fix it would be convenient but inconsistent.

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

#63

Post by Phrodo_00 »

camel-cdr wrote: post #53
arcbyte wrote: post #50

Earlier quoted context omitted.

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.

> 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.

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

#64

Post by jnxx »

> Side note: even though we can't return, main is the exception to the rule that reaching the closing } of a function returning non-void is verboten,

Isn't it legal to fall of the end of the end of a non-void function, only just defined as UB to use the return value?

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

#66

Post by legalcorrection »

a-dub wrote: post #51

the fact that you can do recursion before even entering the function is amusing. not THAT strange though, i imagine the compiler just gloms a preamble onto the executing function's stack frame. amusing to think that the goal of them is probably to make it easier avoid buffer overruns, but then they can just be extended themselves to cause similar problems anyway.

You are entering the function. It's not in the function body in the source file, but the code is almost certainly inserted at the beginning of the function in the compiled output.

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

#68

Post by SavageBeast »

nneonneo wrote: post #36
SavageBeast wrote: post #33

Earlier quoted context omitted.

The fact the array element isn't in quotes bothers me to some degree - with or without its crazy but the fact that the compiler just accepts it as a language construct as opposed to a value makes me want to drink another beer. But again Im thinking dereferencing here - and as you said thats not the case.

It’s not an array element :) The printf statement is part of the length expression, i.e. it’s setting the length of the array to the result of the printf call. So it is indeed a “value”. This isn’t much different from writing something like this in JS: var a = []; a[console.log("Hello"), 1] = 42; except that this indexes the array as opposed to setting its length.

I spent the past 10 minutes figuring out what to search for (C is very rusty here) regarding C arrays and initialization. Now that you point it out, it seems obvious. It certainly wasn't obvious when I read it though. This is some really obtuse use of a language here - hilariously so really. The code in the array is executed as a function that determines the array size and I see that now - thanks. If someone on my team did this for any reason I'm not sure If Id shoot them or put them in charge of something more important. If no other thing - THIS is why code reviews exist. Still it's an impressive use of a compiler. Thanks for nit picking - this has been very entertaining!

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

#69

Post by MayeulC »

omoikane wrote: post #23
AshamedCaptain wrote: post #2

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's not quite the same as default arguments in that default arguments are evaluated at run time, whereas array lengths for C++ (and not C) needs to be a compile time constant expression. #include // "puts" makes "f" not constexpr. constexpr int f() { return puts("hello"); } // error: size of array 'argv' is not an integral constant-expression int main(int argc, char *argv[f()]) {}

As you point out, VLAs in C are evaluated at run time too, making it very similar to abusing default arguments.

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

#70

Post by camel-cdr »

dmitrygr wrote: post #60
camel-cdr wrote: post #57

Earlier quoted context omitted.

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.

You’re spouting nonsense. File offset is guaranteed to be expressible by the integral type off_t. Thus also limited.

You are aware that `off_t` isn't in the C standard?

The standard has `fgetpos`:

> The fgetpos function stores the current values of the parse state (if any) and file position indicator for the stream pointed to by stream in the object pointed to by pos

> If a file can support positioning requests (such as a disk file, as opposed to a terminal), then a file position indicator associated with the stream is positioned at the start (character number zero) of the file, unless the file is opened with append mode in which case it is implementation-defined whether the file position indicator is initially positioned at the beginning or the end of the file.

Meaning `fgetpos` mustn't work for files that don't support `positioning requests`, whiles relative offsets using `fseek` could still work.

Post reply on HN