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

231–240 of 257 posts

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

#231

Post by kllrnohj »

dataflow wrote: post #219
ordu wrote: post #218

Earlier quoted context omitted.

If your input is not bounded you can't know in advance the time needed to process it. In other word you cannot be realtime. `cat` can be realtime, but only by fixing the size of its internal buffer where it reads to and writes from. In this case it can in theory bound the time needed to process the fixed block of input. But if for some reason `cat` tried to read/write by lines of unknown in advance size, it would fai…

I think we're not disagreeing on the actual constraints, but the terminology. The "internal buffer" is not part of the system's "input". It's part of the system's "state".

We're talking about function inputs, not system inputs.

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

#232

Post by astrange »

naasking wrote: post #213
astrange wrote: post #198

Earlier quoted context omitted.

They're not unsafe (in the memory sense) as long as they check for overflow and reliably crash if there is one.

If a lot of platforms don't implement this check reliably, then it's unsafe in practice at this time, even if not in theory.

Who out there has a version of stack checking that doesn't actually check the stack…? If it doesn't check by default, as C doesn't, then it's not "as long as".

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

#233

Post by einpoklum »

saagarjha wrote: post #178
einpoklum wrote: post #44

Earlier quoted context omitted.

With VLAs: 1. The stack-smashing pattern is simple, straightforward and sure to be used often. Other ways to smash the stack require some more "effort"... 2. It's not just _you_ who can smash the stack. It's the fact that anyone who calls your function will smash the stack if they pass some large numeric value.

They can overflow the stack. They cannot smash the stack.

Fair enough; I had the mistaken idea that the two terms are interchangeable, but apparently stack smashing is only used for the attack involving the stack:

https://en.wikipedia.org/wiki/Stack_buffer_overflow

so, pretend I said "overflow" instead of "smash" in my post.

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

#234

Post by marssaxman »

tremon wrote: post #147
marssaxman wrote: post #92

Earlier quoted context omitted.

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

> But then you're no longer writing Standard C.

Well, of course not - it didn't exist yet! Or, if it existed, your compiler didn't support it yet; or, even if you had upgraded to a newer compiler which did support it (not a given back then), your codebase and development style preceded the standard, so you continued in the existing style.

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

#235

Post by legalcorrection »

tialaramex wrote: post #227
legalcorrection wrote: post #189

Earlier quoted context omitted.

You are confusing the C standard and actual platforms/C implementations. A lot of things are UB in the standard but perfectly well defined on your platform. Standards don’t compile code, real compilers do. The standard doesn’t provide standard library implementations, the actual platform does. Targeting the standard is nice, but if all of your target platforms guarantee certain behaviors, you might consider using tho…

> A lot of UB in the C standard is perfectly defined and consistent across MSVC, GCC, Clang, and ICC. Do you have examples of this "a lot of UB in the C standard" which is in fact guaranteed to be "perfectly defined and consistent" across all the platforms you listed ? You may need to link the guarantees you're relying on.

Okay so take the two most complained about UBs, improper aliasing and signed integer overflow. Every compiler I’ve ever used lets you turn both into defined behavior.

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

#236

Post by asguy »

Banana699 wrote: post #220
asguy wrote: post #159

Earlier quoted context omitted.

Quoted post unavailable.

The only one coping here is that who doesn't understand VMs and language research enough and retreats into childish "it was just a joke lol" remarks when out of their depth. Incidentally, I write all 3 of C, C++ and x86 assembly, which is why I understand how braindead and unfit for human usage they are.

I didn't say I was "just joking", but calling C++ "unsafe" was definitely something I think was funny to say.

> Incidentally, I write all 3 of C, C++ and x86 assembly, which is why I understand how braindead and unfit for human usage they are.

I can't take you seriously when you make statements like this. You have to be trolling.

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

#237

Post by 10000truths »

mtlmtlmtlmtl wrote: post #201
10000truths wrote: post #162

Earlier quoted context omitted.

It's not strictly necessary precisely because all recursions can be "simulated" with a heap allocated stack. And in fact, the "simulated" approach is almost always better, from both a performance and a maintenance perspective.

This is simply nonsense. In cases with highly complex recursive algorithms, "unrecursing" would make the code a completely unmaintainable mess, requiring an immensely complicated state machine, which is why something like Stockfish doesn't do that in its recursive search function even though the code base is extremely optimised. And yes, some algorithms are inherently recursive, and don't gain any meaningfull perform…

> In cases with highly complex recursive algorithms, "unrecursing" would make the code a completely unmaintainable mess, requiring an immensely complicated state machine

Nothing about it is "immensely complicated". Rather than store your recursion state in a call stack, you can store it in a stack of your own, i.e. a heap-allocated container. The state of a cycle of foo(a,b,c) -> bar(d,e,f) -> baz(g,h) -> foo(...) becomes expressible as an array of tagged union of (a,b,c), (d,e,f) and (g,h).

And there is nothing inherently unmaintainable about this approach. I would hope that it's a commonly taught pattern, but even if it's not, that doesn't make it impossible to understand. Picking good names and writing explanatory comments are 90% of the battle of readability.

> which is why something like Stockfish doesn't do that in its recursive search function even though the code base is extremely optimised

I can't speak for what Stockfish devs do, as I have no insight into which particular developers made what set of tradeoffs in which parts of their codebase. But it doesn't change the reality that using your own stack container is almost always more performant and more extensible:

1. Your own stack container can take up less space per element than a call stack does per stack frame. A stack frame has to store all local variables, which is wasteful. The elements of your own stack container can store just the state that is necessary.

2. Your own stack container can recurse much farther. In addition to the previous point, call stacks tend to have relatively small memory limits by default, whereas heap allocations do not. In addition, you can employ tricks like serializing your stack container to disk, to save even more memory and allow you to recurse even farther.

3. Your own stack container can be deallocated, shrunk, or garbage collected to free memory for further use, but a call stack typically only grows.

4. Your own stack container can be easily augmented to allow for introspection, which would require brittle hackery with a traditional call stack. This can be an extremely useful property, e.g. for a language parser resolving ambiguities in context sensitive grammars.

> And yes, some algorithms are inherently recursive, and don't gain any meaningfull performance from the heap stack + state machine approach.

Using a heap-allocated stack container is recursion. It is the state machine. The only fundamental implementation difference between the approach I describe and traditional recursion is that the former relies on the programmer using an array of algorithm state, and the latter relies on the runtime using an array of stack frames.

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

#238

Post by vlovich123 »

msla wrote: post #217
10000truths wrote: post #162

Earlier quoted context omitted.

It's not strictly necessary precisely because all recursions can be "simulated" with a heap allocated stack. And in fact, the "simulated" approach is almost always better, from both a performance and a maintenance perspective.

> It's not strictly necessary precisely because all recursions can be "simulated" with a heap allocated stack. This just moves the problem from a stack blowout to a heap blowout. > And in fact, the "simulated" approach is almost always better, from both a performance and a maintenance perspective. I am unsure about the performance, but turning recursive code implementing a recursive procedure into iterative code whic…

Computers have many GiBs of heap space. Your thread has MiB of stack. Tell me. Which is the bigger problem?

This is also ignoring the fact that the memory usage for recursive algorithms is higher because there’s a bunch of state for doing the function call being pushed onto the stack that you just don’t see (return address, potentially spilling registers depending on the compiler’s ability to optimize, etc). Unless you stick with tail recursion but that’s just a special case where the loop method would be similarly trivial. Case in point. I implemented depth first search initially as a recursive thing and blue out the stack on an embedded system. Switched to an iterated depth first search with no recursion. No problem.

OP said “it’s the only way to solve certain problems”. That’s clearly not true because ALL recursive algorithms can be mapped to non recursive versions.

I never got the fascination with implicit recursion. It’s just a slightly different way to express the solution. Personally I find it usually harder to follow / fully understand than regular iterative methods that describe the recursion state explicitly (ie time and space complexity in particular I find very hard to reason about for recursion.)

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

#239

Post by TazeTSchnitzel »

saagarjha wrote: post #179
TazeTSchnitzel wrote: post #83

Earlier quoted context omitted.

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

Tip: if writing new functions that take things that are not strings, try to avoid C’s mistakes with strncpy and putting “str” in the name.

Those are strings! Null-terminated strings are not special.

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

#240

Post by dataflow »

kllrnohj wrote: post #231
dataflow wrote: post #219

Earlier quoted context omitted.

I think we're not disagreeing on the actual constraints, but the terminology. The "internal buffer" is not part of the system's "input". It's part of the system's "state".

We're talking about function inputs, not system inputs.

Real-time is a property of the whole system though (?) not individual functions. But even if you want to reframe it to be about functions, small input is neither necessary nor sufficient for it being "real time". Like your function might receive an arbitrarily large n-element array a[] and just return a[a[n-1]], and it would be constant time. Again, the size is the simply not the correct property to look at.
Post reply on HN