C99 doesn't need function bodies, or 'VLAs are Turing complete' • Hacker News Board

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

#81

Post by lololol0l » Thu, Aug 04, 2022, 6:01 PM UTC

SavageBeast wrote: post #68

nneonneo wrote: post #36

Earlier quoted context omitted.

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

No post body was provided.

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

#82

Post by rwmj » Thu, Aug 04, 2022, 6:03 PM UTC

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?

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 (particularly on 32 bit or in kernel) are quite limited in depth and so you want to be careful with stack frame size. VLAs make it harder to compute and thus check stack frame sizes at compile time, making the -Wstack-usage warning less effective. Large arrays get allocated on the heap instead.

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

#83

Post by TazeTSchnitzel » Thu, Aug 04, 2022, 6:03 PM UTC

beeforpork wrote: post #5

But why? Why is this VLA parameter defined this way? It seems totally bizarre and unnecessary, but I suppose it must have been added to the standard to solve some kind of problem? Is the proposal for this feature available and gives some insight?

Allowing arbitrary expressions allows self-documenting signatures:

  void concat_strs(
    int str1_len,
    const char str1[str1_len],
    int str2_len,
    const char str2[str2_len],
    char out_str[str1_len + str2_len],
  );
  
  void manipulate_array(
    array_dim dim,
    int arr[dim.x][dim.y],
  );

Supporting things like printf() was probably not specifically desired, but it would be difficult to define it in such a way that it accepts all reasonable expressions and doesn't accept any "unreasonable" ones.

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

#84

Post by dmitrygr » Thu, Aug 04, 2022, 6:04 PM UTC

camel-cdr wrote: post #70

dmitrygr wrote: post #60

Earlier quoted context omitted.

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

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

#85

Post by camel-cdr » Thu, Aug 04, 2022, 6:04 PM UTC

kps wrote: post #78

camel-cdr wrote: post #52

Earlier quoted context omitted.

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.

This would be possible, but it feels like cheating :-)

Idk how to express this properly, but I feel like there is a difference between this and the fseek approach.

In a similar vain, you could say that a certain kind of undefined behavior controls the tape, or writing to a specific part of memory does.

I suppose this would fall under adding additional compiler extension.

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

#86

Post by [deleted] » Thu, Aug 04, 2022, 6:06 PM UTC

legalcorrection wrote: post #66

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.

[deleted]

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

#87

Post by camel-cdr » Thu, Aug 04, 2022, 6:12 PM UTC

_gabe_ wrote: post #74

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.

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

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

Yes, you can increase the pointer size arbitrarily, but it is always constant for a single C implementation, you can't increase the pointer size at run time.

Essentially you recompiling and running a program and choosing an implementation with a successively larger pointer size is Turing complete, but it requires you as a special actor, and I'm only concerned for a what a single implementation can do.

To put it in another way, solving the halting problem is trivial for any C program + a fixed C implementation, that doesn't have special language extensions.

> I'm curious, do you think other languages are Turing complete?

The easiest example would be brainfuck, because you can just move the tape around in it, and a theoretical implementation could trivially be hoked up to a theoretical infinite tape.

> As far as I know, all modern programming languages use a 64 bit addressable memory space maximum

I don't know enough about how other languages are defined, but I could imagine that Java allows for an implementation with infinite memory, because it doesn't impose any requirements on how the pointers are implemented under the hood.

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

#88

Post by badsectoracula » Thu, Aug 04, 2022, 6:12 PM UTC

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

You can read the C89 rationale here[0] but in general the point of undefined behavior was (and maybe still is, i didn't check other rationales) partly to let implementations not bother with catching hard-to-catch errors for things that could actually happen and partly to allow for implementation extensions for things they didn't want to or couldn't define.

In addition the entire idea of introducing undefined, unspecified and implementation-defined behaviors was to let existing implementations do, for the most part, whatever they were already doing while still being standards conformant (ok, the rationale's exact words is to "allow a certain variety among implementations", but in practice C compilers already existed in 1989 and the companies behind them most likely wanted to call them as "C89 conformant" without having to make significant changes).

C89 didn't define undefined behavior because that wouldn't make sense, but it did define what it means and going by the C89 rationale about what it was meant to be used for, clearly the idea wasn't the extremist "breaking your code at the slight whiff of UB because optimizations" but "letting you do things that we can't or don't want to define while keeping our own hands clear".

The "letting you" bit is important which is why they have the distinction between "strictly conforming program" and "conforming program" (i.e. minus the "strict") - which essentially has the former only be for "maximally portable" programs and the latter being "whatever conforming implementations accept", with conforming implementations being any C implementation that can compile strictly conforming programs - regardless of any extensions the implementation may have as long as these do not affect the strictly conforming programs.

In other words it was C89 Committee's way of saying "a (conforming) C program is basically anything a C compiler compiles as long as said C compiler also compiles C programs that adhere to the strict conformance we defined here" - which BTW flies in the face of the entire idea that introducing a single instance of "undefined behavior" makes the entire program not "valid C" anymore (after all program with undefined behavior can still be a conforming program as long as it is accepted by a compiler that also accepts strictly conforming programs).

This is the sort of circular self-referencing logic you get when committees try to standardize something that already has a bunch of not necessarily compatible implementations while also trying to not ruffle the feathers of the companies behind them too much.

It'd be an amusing tale if only some people (who you can ignore anyway) didn't get into fights about what page x, paragraph y, verse z of the Standard[1] say and decades later funneling that logic into compilers (which are somewhat harder to ignore) that break existing working code while Bible thumping their standards book whenever someone goes "WTF, this thing used to work before i upgraded the compiler"[3]

[0] http://www.lysator.liu.se/c/rat/title.html

[1] Capitalization Intentional

[2] Yes, C was considered one at some point :-P

[3] "No, it is not valid C, it couldn't have worked. You clearly imagined it."

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

#89

Post by jwilk » Thu, Aug 04, 2022, 6:13 PM UTC

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.

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

#90

Post by kps » Thu, Aug 04, 2022, 6:15 PM UTC

camel-cdr wrote: post #85

kps wrote: post #78

Earlier quoted context omitted.

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.

This would be possible, but it feels like cheating :-) Idk how to express this properly, but I feel like there is a difference between this and the fseek approach. In a similar vain, you could say that a certain kind of undefined behavior controls the tape, or writing to a specific part of memory does. I suppose this would fall under adding additional compiler extension.

> … or writing to a specific part of memory does.

Memory-mapped devices are pretty common. C's original platform controlled tape drives by writing to memory: https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/sys/dev/tc...