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

21–30 of 257 posts

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

#21

Post by jmount »

svnpenn wrote: post #9

This kind of insanity is exactly why I don't use stuff like C anymore. It's a landmark and incredible language, but it's chock full of potholes and foot-shotguns (footguns that blow off your entire leg). Even huge companies can't get it right, which makes sense. It started as a language basically without guardrails, and because of the extreme deference to the holy backward compatibility, it's more or less always goin…

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.

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

#23

Post by omoikane »

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()]) {}

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

#24

Post by tooltower »

jmount wrote: post #21
svnpenn wrote: post #9

This kind of insanity is exactly why I don't use stuff like C anymore. It's a landmark and incredible language, but it's chock full of potholes and foot-shotguns (footguns that blow off your entire leg). Even huge companies can't get it right, which makes sense. It started as a language basically without guardrails, and because of the extreme deference to the holy backward compatibility, it's more or less always goin…

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

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

#25

Post by ufo »

monkpit wrote: post #15
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.

> opiltimization Is this some portmanteau for “compile time optimization”?

Nah, it was just a typo. But I like your idea!

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

#26

Post by SavageBeast »

monkpit wrote: post #15
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.

> opiltimization Is this some portmanteau for “compile time optimization”?

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 and browsers are F'd".

Before it was all said and done you could enable a "deep compile" option that would even look at your java code for cases that would never execute - rarely execute (you're a dumb human right?) - etc and build an opinionated JS runtime around it for performance and size (size complexity? Space-Time-Trade-Off).

I was enamored with GWT for quite some time and developed a high level of skill using the tool. I still miss it frankly. People who seek to write one language and execute another are fundamentally insane. Even though this is basically necessary with a lang like C (one step above shifting bits and understanding instructions etc) those people still amaze me.

I'm glad I wasn't born with the requisite intellect to go down such rabbit holes myself. This makes me feel dumb and be OK with it at the same time.

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

#27

Post by kllrnohj »

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?

seems like to avoid the introduction of constant expressions (constexpr) like is in C++. Which is why c++ doesn't have this issue, even though it can also take expressions as the expressions must be resolvable at compile-time.

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

#28

Post by mrkeen »

SavageBeast wrote: post #26
monkpit wrote: post #15

Earlier quoted context omitted.

> opiltimization Is this some portmanteau for “compile time optimization”?

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.

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

#29

Post by addaon »

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 clear, the value the contained directly in the infinite memory; if the tag is set, then the value is indirected into a fixed-sized memory. On taking the address of an item on the stack, if it is not already indirected, relocate it and indirect.

Of course the mechanism for doing stack unwinding on return needs to use relative operations ("drop five elements") and not chase frame pointers, but that seems trivial.

I admit I'm not super-familiar with all the details of the C specification, but it's not obvious to me that this would violate spec, and it would be Turing complete.

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

#30

Post by nneonneo »

SavageBeast wrote: post #19

I haven't thought about C in years - that one where author passes in a printf as a char array element and de-references it to execute it ... gives me chills. Y'all kids have fun - Im going to stick with my VM over here and call it a day. This makes even modern JS look sane by comparison. Excellent write up too.

Nit: the char array doesn’t get dereferenced at all. The entire computation happens as a side effect of computing the length of the array. This is more of a case where there’s an unexpected expression context that can be abused for fun.
Post reply on HN