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

141–150 of 257 posts

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

#141

Post by jcranmer »

wizofaus wrote: post #119
mjcohen wrote: post #105

Earlier quoted context omitted.

What the heck. It's "moot", not "mute".

I'm curious, are there accents in which those two words are homophones? Given the US tendency to pronounce new/due/tune as noo/doo/toon I can imagine some might say mute as moot but I can't find anything authoritative online.

According to Wikipedia, East Anglia does universal yod-dropping, so mute/moot would be homophonic. (See https://en.wiktionary.org/wiki/Appendix:English_dialect-depe...).

Personally, I haven't come across anyone who pronounces 'mute' without the /j/.

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

#142

Post by cypress66 »

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…

I'm sure someone more knowledgeable will point out the flaw, but couldn't Turing's machine definition be changed from infinite tape, to arbitrarily large tape, and thus solve this technicality?

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

#143

Post by asguy »

Banana699 wrote: post #136
asguy wrote: post #101

Earlier quoted context omitted.

> I haven't thought about C in years ... Im going to stick with my VM over here and call it a day. What's your VM written in?

Safe Rust. https://deno.land/

Except for most of deno that's written in Unsafe C++.

https://v8.dev/

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

#144

Post by Dylan16807 »

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…

How does a huge VLA corrupt the stack? If there's not enough space but code keeps going then isn't that a massive bug with your compiler or runtime?

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

#145

Post by munificent »

camel-cdr wrote: post #55
munificent wrote: post #49

Earlier quoted context omitted.

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

My point was that this isn't possible, because the addressable memory, whiles possible humongous, is always finite, because the sizeof pointers is constant. So at some point `malloc` must return the same address, even if you had theoretically infinite memory available, there is no way to address that in C.

Ah, good point!

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

#146

Post by petters »

Dylan16807 wrote: post #144
rwmj wrote: post #82

Earlier quoted context omitted.

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…

How does a huge VLA corrupt the stack? If there's not enough space but code keeps going then isn't that a massive bug with your compiler or runtime?

Welcome to the world of undefined behavior. Anything can happen....

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

#147

Post by tremon »

marssaxman wrote: post #92
tooltower wrote: post #24

Earlier quoted context omitted.

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…

you could confidently predict what a given compiler would generate, for a given platform

But then you're no longer writing Standard C. You're writing compiler-flavoured C, which is another source of footguns for projects that outlive the compiler (or version) they were originally written for. Which is fine, as you say, for embedded-style projects that only target one processor model and one compiler version. But I don't think that applies to many of today's projects.

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

#148

Post by Banana699 »

asguy wrote: post #143
Banana699 wrote: post #136

Earlier quoted context omitted.

Safe Rust. https://deno.land/

Except for most of deno that's written in Unsafe C++. https://v8.dev/

A JS runtime is a lot more than the core engine, or else nodejs is just a thin wrapper over V8 as well, which is obviously absurd. So without a count of the source lines for each language's portion of the implementation (very rough but acceptable first approximation of how much is implemented in each), you can't claim C++ is doing most of the heavy lifting and be taken seriously.

PS. the worst C++ code is still a hell of a lot more safe than the best C code. This is easy to convince yourself of by noting that C++ mostly supersets C and only deviates to add more safety and static checking, not less. So it's a strict improvment over C, not by a lot, but an improvment nonetheless.

Here are other examples for VMs not written in any of those 2 braindead languages though:

[1] Bun : JS runtime in Zig. https://bun.sh/

[2] Squeak : Smalltalk VM written in Smalltalk. http://www.vpri.org/pdf/tr1997001_backto.pdf

[3] PyPy : Not actually a single VM but an entire framework\toolchain to write VMs, most famous of which is one for Python. The language used to write VMs for the framework is a subset of python called Rpython. https://doc.pypy.org/en/latest/

[4] Maxine Virtual Machine : a JVM written entirely in Java. It's not the only one. https://en.wikipedia.org/wiki/Maxine_Virtual_Machine ; https://news.ycombinator.com/item?id=15733645

Modern VM research is far beyond the 50 year old assembler that thinks itself a programming language. The future is here, just not very evenly distributed.

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

#149

Post by mtlmtlmtlmtl »

zajio1am wrote: post #133
rwmj wrote: post #82

Earlier quoted context omitted.

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…

> stuff like ... leads to a possible exploit where the input is manipulated so n is large The same is true for most recursive calls, should recursion be also banned in programming languages?

That's not really a fair comparison though. Recursion is strictly necessary to implement several algorithms. Even if "banned" from the language, you would have to simulate it using a heap allocated stack or something to do certain things.

None of this applies to VLA arguments.

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

#150

Post by camel-cdr »

cypress66 wrote: post #142
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…

I'm sure someone more knowledgeable will point out the flaw, but couldn't Turing's machine definition be changed from infinite tape, to arbitrarily large tape, and thus solve this technicality?

Let me put it that way.

Given any theoretical C implementation and a strictly confirming program (that doesn't do io) I can theoretically trivially solve the halting problem.

Since the possible memory is constant for any given implementation, I can use the following algorithm:

1. Execute one instruction of the program

2. If the program terminated, goto 4.

3. insert entire program state into a hash table

   if it is already in the hash table, goto 5.

   otherwise, goto 1.
4. The Program terminates

5. The program never terminates

The above algorithm solves the halting problem of any C program with a constant memory bound in finite time.

Post reply on HN