21 ms·
C99 doesn't need function bodies, or 'VLAs are Turing complete'
- AshamedCaptain 4y agoSimilar 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.
- jstanley 4y agoIt 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.
- jsmith45 4y agoVLAs 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 proper local VLA with respect to things like sizeof, in which case the assertion makes sense. Or I'd have also been fine with it totally decaying to a pointer, making it just documentation. This half-way in between state is quite weird.
- unnah 4y agoNote 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)); }
- silon42 4y agoor RIIR is suddenly preferable.
- AlotOfReading 4y agoSerious question, but what "purists" remain on ANSI C? Even Linux has abandoned it as of 5.19. The only times I use it are when I'm writing something that requires ridiculous portability even to bizarre platforms and compilers. C99 is far more ergonomic in comparison, even if you have to avoid using some of the truly terrible design decisions that came along for the ride.
- alar44 4y agoEmbedded probably.
- AlotOfReading 4y agoThat's where I work. I haven't seen c89 in years outside those "extreme portability" projects like Linux and curl.
- arinlen 4y ago> Serious question, but what "purists" remain on ANSI C? It means nothing. It's a baseless attemt at an appeal to authority that has no merit.
- MayeulC 4y agoOh, but designated initializers are so useful!
- arinlen 4y ago> 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-support-arriving-in-msvc/ 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 beyond C89.
- pjmlp 4y agoMicrosoft 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-and-c99/ https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an...
- Koshkin 4y ago> purists stick to C89 But the true Scotsman… uh, purist sticks to the K&R C as C89 has already lost some of the original elegance and simplicity. (Never mind that it’s a challenge since the general community has moved on.)
- josefx 4y ago> What may surprise people is how and when these expressions are evaluated since they differ between languages. What could possibly be surprising about reusing the exact same object on every function call, especially when you default to an empty list, set or dict. Getting an actual empty list is as easy as defaulting to None and explicitly checking for it, so there isn't even a reason to do it any differently. /s Who the hell thought that this was sane behavior in a language with mostly mutable objects?
- omoikane 4y agoIt'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 <stdio.h> // "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()]) {}
- MayeulC 4y agoAs you point out, VLAs in C are evaluated at run time too, making it very similar to abusing default arguments.
- planede 4y agoC++ doesn't allow accessing other function arguments in a default argument, is in some sense the VLA trick is more powerful.
- Izkata 4y ago> 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]
- ynfnehf 4y agoI once implemented FizzBuzz using this trick https://www.reddit.com/r/C_Programming/comments/qqazh8/fizzbuzz_contained_entirely_within_the_parameter/ https://www.reddit.com/r/C_Programming/comments/qqazh8/fizzb...
- inglor_cz 4y agoWow, this is wizardry.
- beeforpork 4y agoBut 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?
- mananaysiempre 4y agoYou can try trawling through the document log[1], but a big part of the C99 deliberations is either inaccessible or (like the drafts) explicitly kept secret from anyone but the committee. [1] https://www.open-std.org/jtc1/sc22/wg14/www/wg14_document_log.htm https://www.open-std.org/jtc1/sc22/wg14/www/wg14_document_lo...
- ufo 4y agoI speculate it's for consistency with VLAs that are not function arguments, which is the more common use for VLAs. The original purpose of VLAs is to let you stack-allocate an array with a length that is not known at compile time. In ANSI C you must heap-allocate such arrays, using malloc.
- kllrnohj 4y agoseems 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.
- TazeTSchnitzel 4y agoAllowing 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.
- saagarjha 4y ago
- pjmlp 4y agoThanks to them being yet another attack vector and funny stuff like on this post, got demoted to optional on C11. Additionally Google spent several years paying to clean up the Linux kernel from all VLA occurrences. https://www.phoronix.com/news/Linux-Kills-The-VLA https://www.phoronix.com/news/Linux-Kills-The-VLA
- option_key 4y ago>Thanks to them being yet another attack vector and funny stuff like on this post, got demoted to optional on C11. Sadly, the C committee doesn't really understand what was wrong with VLAs and a sizable group of its members wants to make them mandatory again: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2921.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2921.pdf ("Does WG14 want to make VLAs fully mandatory in C23")
- planede 4y agoWhat's wrong with VLAs is their syntax. It really shouldn't use the same syntax as regular C arrays, otherwise they would be fine, maybe with a scary enough keyword. They are more generic than alloca too, alloca being scoped to the function, while VLAs being scoped to the innermost block scope that contains them.
- svnpenn 4y agoThis 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 going to be that.
- jmount 4y agoI 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.
- tooltower 4y agoWhat old C do you mean? I can't think of any version where undefined had a defined meaning
- hxtk 4y agoNot defined as part of the standard, but before compilers got as smart about their optimizations, it was easier to have behavior that was technically undefined but could be reasoned about in practice. Now that compilers know cleverer optimizations, undefined behavior is often impossible to reason about because the compiler can change your logic into something else that is more optimal and is equivalent to your logic only in well-defined cases.
- astrange 4y agoModern compilers also come with UBSan. Either run it through that, or just always build with it enabled.
- badsectoracula 4y agoYou 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 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."
- ufo 4y agoThey 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.
- monkpit 4y ago> opiltimization Is this some portmanteau for “compile time optimization”?
- ufo 4y agoNah, it was just a typo. But I like your idea!
- SavageBeast 4y agoOn 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.
- mrkeen 4y ago
- SavageBeast 4y agoI 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.
- nneonneo 4y agoNit: 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.
- SavageBeast 4y agoThe fact the array element isn't in quotes bothers me to some degree - with or without its crazy but the fact that the compiler just accepts it as a language construct as opposed to a value makes me want to drink another beer. But again Im thinking dereferencing here - and as you said thats not the case.
- nneonneo 4y agoIt’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.
- SavageBeast 4y agoI 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 team did this for any reason I'm not sure If Id shoot them or put them in charge of something more important. If no other thing - THIS is why code reviews exist. Still it's an impressive use of a compiler. Thanks for nit picking - this has been very entertaining!
- charcircuit 4y ago>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 an upperbound of the size of a pointer times the word size.
- addaon 4y agoDoes 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.
- fhars 4y agoYes 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.
- addaon 4y agoIs 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.
- jmount 4y agoWowzers, I thought that was gong to be some template re-write expansion trick. Nope, just willing to run nearly arbitrary code if you wrap it correctly (not a complaint!).
- camel-cdr 4y agoThis 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 what I can tell, the only way you could theoretically access an infinite tape is using `fseek` with `SEEK_CUR`. There might be more shenanigans possible with `stdio.h`, but I'm pretty sure C can't be Turing complete without the `stdio.h` function (assuming no special language extensions). If anybody is wondering, the preprocessor isn't Turing complete either, because you might theoretically have infinite memory, but then you only have finite recursion, which also isn't enough for Turing completeness. File iteration can have infinite recursion, but can also only carry over finite state between `#include`s. Edit: I'm not talking about any real world implementation, but rather about the theoretical bounds of the C abstract machine.
- dmitrygr 4y agoYour argument sort of imploded on itself…your claim that only a file can be considered tape is insane because memory is just as usable as tape and you can keep extending memory available to you using sbrk() . If you’re going to claim the memory is finite, well so are files. (Also lseek is not part of any C spec) And yes neither is infinite, so every computer is just a DFA, and lseek changes nothing. But given the amount of memory that exists we approximate and say they are Turing machines since there is enough memory to do most what we need.
- camel-cdr 4y agoMy 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.
- dmitrygr 4y agoPointer++ Pointer—- These do the same to pointers…
- jimmaswell 4y ago> that declaration is functionally equivalent, and compatible to the following: Nice to see some vindication - I remember saying this and IRC pedants trying to argue up and down that they're absolutely not the same
- a-dub 4y agothe 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.
- legalcorrection 4y agoYou 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 4y ago[deleted]
- google234123 4y agoWhat is the best alternative when I want to allocate some reasonably sized array on the stack and don’t want to always reserve the worst case size? alloca?
- tedunangst 4y agoReserve the maximum every time.
- cozzyd 4y agoThat has cache friendliness implications though, doesn't it? Seems better to just cap the size of the allocation and use a VLA.
- enriquto 4y agoYou don't need an alternative. VLAs are perfectly appropriate for that use case.
- jnxx 4y ago> Side note: even though we can't return, main is the exception to the rule that reaching the closing } of a function returning non-void is verboten, Isn't it legal to fall of the end of the end of a non-void function, only just defined as UB to use the return value?
- tedunangst 4y agoCorrect. > If the } that terminates a function is reached, and the value of the function call is used by the caller, the behavior is undefined.
- planede 4y agoInterestingly C++ makes this UB. > Otherwise, flowing off the end of a function other than main or a coroutine ([dcl.fct.def.coroutine]) results in undefined behavior. https://timsong-cpp.github.io/cppwp/n4868/stmt.return#2.sentence-9 https://timsong-cpp.github.io/cppwp/n4868/stmt.return#2.sent... edit: This also manifests in compiler optimizations, at least in gcc https://godbolt.org/z/GhxjdWqGb https://godbolt.org/z/GhxjdWqGb
- ezoe 4y agoThis is just too much of insanity I can witness today.
- tjoff 4y agoExcellent, 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.
- noobermin 4y agoThis is such a fantastic write up. Also, a missed opportunity for a smashing submission to ioccc
- tstanisl 4y agoThere are multiple false myths about VLAs. Please known that VLA is about the typing not about the storage. The line: typedef int T[n]; is the essence of VLA-ness, not `int A[n]`. The array of VLA type can have any kind of storage one wants. It can be stack T a; It can be heap T *a = malloc(sizeof *a); It can be even infamous alloca() T *a = alloca(sizeof *a); Please stop talking about this "VLA is stack-base vector" crap because it means that one does not understand what VLAs are about. I admin that automatic VLAs are pretty much always wrong but this use case is a tiny bit of the realy functionality of VLA types. VLA were added to language to handle multidimensional arrays. And the really shine at this task. Even C++ has not good alternative for it. Vector of vectors is a really crappy data structure. A few examples when working with square matrices: - allocation on stack float A[n][n]; - allocation on heap float (*A)[n] = malloc(sizeof(int[n][n])); ... free(A); - indexing A[i][j] - passing to functions: void add(int n, float A[static n][n], float B[static n][n], float RES[restrict static n][n]); ... Please show me something as simple, effective, self-documenting and elegant in C++.