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

91–100 of 257 posts

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

#91

Post by Izkata »

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.

> Similar to making all your computations in the expressions for default arguments in python

Python default arguments are evaluated only once at function definition, not every function call. It's the source of one interesting WTF for anyone who assumes otherwise:

  def foo(a=[]):
    a.append(1)
    return a

  >>> foo()
  [1]
  >>> foo()
  [1, 1]
  >>> foo()
  [1, 1, 1]

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

#92

Post by marssaxman »

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

It's not that the behavior was defined by the C standard, but that you could confidently predict what a given compiler would generate, for a given platform, so it was quite normal to write programs which made productive use of officially-undefined behavior when that was the behavior you wanted. (It may well have been defined by that particular compiler's documentation.)

Nowadays, people are used to thinking entirely inside the abstraction provided by the language spec, but that was not the case in the '80s and early '90s. The boundary between the C language model and the underlying machine architecture was porous. You would include snippets of assembly language in your C code, if you wanted to do something more quickly than you thought the compiler could do it; and your C code would take full advantage of your knowledge about the underlying memory layouts, calling conventions, register usage, and so forth.

It did not really matter that there were gaps in the "C machine" abstraction because nobody was really programming against the "C machine"; they were programming against their actual hardware, using C as a tool for generating machine code.

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

#93

Post by addaon »

fhars wrote: post #61
addaon wrote: post #29

Earlier quoted context omitted.

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.

Is this true? C is defined in terms of the operations that can be performed on objects in memory, which includes the concept of memory addresses and address manipulation; but I'm not aware of anything that would require that objects that do not have their address taken have unique addresses, or addresses at all. This is the same use of the as-if principle that allows so many local variables to live their entire life in registers. An infinite stack to support unlimited recursion seems possible within the C machine.

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

#94

Post by unnah »

jsmith45 wrote: post #7
jstanley wrote: 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.

VLAs in a prototype are sensible, because they decays to a pointer, and is thus functioning purely as documentation. In the function definition, it seems to basically also decay to a pointer, except that the compiler adds basically an assertion that the value in the brackets is greater than zero to the to the top of the function. That actually seems quite weird to me. I'd have been fine with the VLA acting like a pro…

Note that sizeof is useful on the inner dimensions of multi-dimensional array arguments: the following prints the value of m.

    int foo(int n, int m, double x[n][m]) {
        printf("sizeof(x[0])=%zd\n", sizeof(x[0])/sizeof(double));
    }

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

#95

Post by tjoff »

Excellent, didn't know that you could reference previous function arguments :)

Though I do feel that this is something different from VLAs (no critique of the article though!). In my head at least the key factor about VLA is that you can allocate an array on the stack when the size isn't known at compile time. But that is not what the author does.

A VLA as specified in a function definition or a declaration (such as: void f(int n, float v[n]);) is known at compile time. And even if trickery is used to do a runtime-calculation of [n] the array itself is not allocated on the stack. And thus also not subject of the common criticism of VLAs.

So, at least in my opinion the arguments (discussed in this threadl) regarding VLAs is mostly orthogonal to the syntax (ab)used here.

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

#96

Post by chjj »

rwmj wrote: post #82
planede wrote: post #38

Earlier quoted context omitted.

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

VLAs make it a lot easier to corrupt the stack by accident. Unless you're quite a careful coder, stuff like: f (size_t n) { char str[n]; leads to a possible exploit where the input is manipulated so n is large, causing a DoS attack (at best) or full exploit at worse. I'm not saying that banning VLAs solves every problem though. However the main reason we forbid VLAs in all our code is because thread stacks (particula…

You shouldn't be writing C if you're not a careful coder.

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

#97

Post by camel-cdr »

dmitrygr wrote: post #84
camel-cdr wrote: post #70

Earlier quoted context omitted.

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 a…

ok, that is just more nonsense... but let's go with that. fgetpos stores offset in an fpos_t object...in memory...memory is finite as you admit...thus the length of this fpos_t object must be finite...thus there is a limit to how many bits fpos_t may contain, thus it can address only finite file length...

> ...thus there is a limit to how many bits fpos_t may contain

Yes, but my point was that a `fgetpos` mustn't work for all FILE pointers, take for example `stdin`.

The standard quotes from my above comment show that a FILE pointer mustn't support “positioning requests”, so fgetpos mustn't work.

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

#98

Post by pjmlp »

arinlen wrote: post #71
pjmlp wrote: post #40

Earlier quoted context omitted.

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.

That is like saying if sushi knifes are already sharp enough, there is no issue cutting fish with a samurai sword instead, except at least with the knife maybe the damage isn't as bad.

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

#99

Post by pjmlp »

arinlen wrote: post #75
jstanley wrote: 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.

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

Microsoft saw no value in supporting C when C++ is a better option [0], they caved in because Microsoft Loves Linux (alongside key FOSS projects) implies loving C as well.

Note that they aren't supporting the optional annexes and stuff like C atomics aren't supported.

[0] - https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an...

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

#100

Post by camel-cdr »

jwilk wrote: post #89
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…

See "Subtleties of the ANSI/ISO C standard" https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1637.pdf >, section V "C is not Turing complete". They discuss file I/O briefly too, but I don't follow their reasoning.

Yes, this is basically my argument.

They address that `ftell` must return a finite value, but don't mention that `ftell` can fail for specific FILEs:

> If successful, the ftell function returns the current value of the file position indicator for the stream

But FILEs don't necessarily have a "file position indicator":

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

They don't seem to discuss the topic further.

> Therefore we will here only consider C programs without I/O. (Our argument can be adapted to show that the programs that restrict I/O to reading stdin and writing stdout are Turing incomplete as well, but we will not do so here.)

So they don't address the problem of IO completely.

Post reply on HN