I just refuse to do interviews like that any more.
If you can convince someone in a position of authority that they’re wrong about something technical without upsetting them then you’re probably a good culture fit and someone who can raise the average effectiveness of your team.
"What does this produce?" and expecting an answer of "17" is a bad question even if UB didn't mean the expected answer is wrong.
Having an understanding of how the code gets transformed into machine code helps. For this case, there's the basic idea that `a++` will boil down to three basic conceptual operations: fetch, add, and store, and those can be potentially interleaved with other parts of the statement. In something like `a++ + ++b` the interleaving doesn't affect the outcome no matter how it's done. In `a++ + ++b` the interleaving can affect the outcome, and that's your sign that something might be wrong.
Any memory safety issue in C code had to involve UB at some point. And you can see how prevalent those are, and deduce how not-particularly-great we are at keeping track of UB.
I'm not sure about that. Knowing assembly is not a substitute for knowing how the language is defined. Sometimes C/C++ programmers with some assembly knowledge reason themselves into thinking that what they're asking of the language must have well-defined behaviour, when in fact it's undefined behaviour. It doesn't really matter whether interleaving order can change the output. (++i)++ is, apparently [0], undefined behaviour in C but has well defined behaviour in C++.
No, that's not right. It's undefined behaviour, not merely an unspecified order of evaluation. Roughly speaking, the behaviour of the entire program is unconstrained by the language standard after execution of that statement. It could crash the whole process, for instance, or go haywire.
(Again, that's in C, apparently, but not in C++.)
Anyway, I didn't mean to imply that things behaved as written aside from ordering issues. I only meant that this sort of principle can help you remember where UB lurks. Generally, where a kind C compiler might just mess with your numbers a bit, an evil C compiler can legally make demons fly out of your nose.
Heh, yes that's exactly what I was thinking when I put roughly speaking.
> where a kind C compiler might just mess with your numbers a bit, an evil C compiler can legally make demons fly out of your nose
Yes, signed integer overflow being another. Presumably it's defined that way as it's simpler than trying to spell out all the behaviours the compiler is permitted to implement, and on top of that there are trap representations to worry about. I doubt modern compilers get much optimization benefit from it though. There's a StackOverflow thread discussing the reasons it's defined this way: https://stackoverflow.com/q/1860461
I tried googling but couldn't find hard numbers on the performance impact of GCC's -fwrapv flag. As you'd imagine, it forces wrapping for overflowing arithmetic on signed integer types. [0]
I also have to wonder how instructive that would be anyway. The GCC devs presumably don't prioritise the performance impact of that flag. If the C language mandated it, they might find other ways to achieve similar optimisation.
This page [1] looks at the related flag for trap-on-signed-overflow, and found an impact of very roughly 6%.
See also: John Regehr's posts on this topic. [2][3] He dislikes Java's implicit wrap behaviour, as it's rarely what the programmer wants to happen. Java programmers almost never use the addExact method, [4] as it's so syntactically clumsy.
> surely it's UB because some systems trapped on overflow, or produced different results due to using 1's complement, and the optimization side of the rule was a happy accident
Per this StackOverflow answer [5] I think you have it right.
[0] https://gcc.gnu.org/onlinedocs/gcc/Code-Gen-Options.html
[1] https://danluu.com/integer-overflow/
[2] https://blog.regehr.org/archives/1401
[3] https://blog.regehr.org/archives/1154
[4] https://docs.oracle.com/en/java/javase/25/docs/api/java.base...
I would argue that most languages only have one compiler so it doesn't matter what is in the specification.
I write "in general" because, as with other forms of memory reinterpretation (memcpy or copy through a character type), evaluating a trap representation triggers UB.
[0] the C meaning of an object, not the C++ one
These sorts of things are neat trivia to learn about things like sequence points but 99.9% of the time if it matters in your codebase you're writing something unmaintainable.
That's half of a reasonable answer. The other half is "but I do know the answer so if I see it when reviewing or working on someone else's code I can flag it or rewrite it, and explain to them why it is bad".
That's the feedback I would want, and it's the feedback I give to my colleagues in reviews. Actually I tend to be too verbose, so you might get a full paragraph explaining what the ISO document says and that you shouldn't assume it does whatever it is your compiler says.
My actual feelings for this specific case are that the language is defective, but if we're wedded to a defective language then the reviews need to call out such usage.
> Actually I tend to be too verbose, so you might get a full paragraph explaining what the ISO document
Verbosity isn't bad. Not everything needs to be a fucking tweet
The behavior of "int a = 5; a = a++ + ++a;" is undefined. There is no guarantee of a numeric result, because there is no guarantee of anything.
A conforming implementation could reject it at compile time, or generate code that traps, or generate code that set a to 137, or, in principle, generate code that reformats your hard drive. Some of these behaviors are unlikely, but none are forbidden by the language standard.
I was looking at this:
https://en.cppreference.com/cpp/language/eval_order
I'm not sure where precisely this sequencing exception to the default "eval order undefined" rule is given, but after the 24(!) sequencing rules they do give this "++i + i++" as an explicit example of undefined behavior.
Interestingly that page says that since C++17 f(++i, ++i) is "unspecified" rather than "undefined", whatever that means, and presumably plus(++i, i++) would be too, which seems a bit inconsistent.
I think the objection thaumasiotes has raised there is valid and I have made an attempt to answer it as well in the same thread.
Susam's post doesn't make this clear. The quotes from K&R say that the modifications to the variable may take place in any order, but they don't directly say that doing this is Undefined Behavior, which would make it permissible to do anything, including e.g. interpreting the increments as decrements.
The C99 standard is quoted saying this:
>> Between the previous and next sequence point an object shall have its stored value modified at most once by the evaluation of an expression.
It's possible that something else in the standard defines noncompliance with this clause as Undefined Behavior. But that's not the most intuitive interpretation; what this seems to say, to me, is that the line of code `a = a++ + ++a` should fail to compile, because it's not in compliance with a requirement of the language. Compilers that produce any result at all are suffering from a bug.
(It seems more likely that the actual intent is to specify that, given the line of code `b = a++ + ++a`, with a initially equal to 5, the compiler is required to ensure that the value stored at the address of a is never equal to 6 - that it begins at 5, and at some indefinite point it becomes 7, but that there is no intermediate stage between them. But I find the 'compiler failure on attempt to put multiple modifications between two sequence points' interpretation preferable.)
> 2. If a ‘‘shall’’ or ‘‘shall not’’requirement that appears outside of a constraint is violated, the behavior is undefined. Undefined behavior is otherwise indicated in this International Standard by the words ‘‘undefined behavior’’ or by the omission of any explicit definition of behavior. There is no difference in emphasis among these three; they all describe ‘‘behavior that is undefined’’.
Compilers will not refuse to compile the code, indeed the blog post we are all commenting on reports the results from a bunch of different compilers. Historically the reason the C standard specified a lot of undefined behavior is that the actually existing C compilers at the time compiled the code but disagreed about the output.
Yes, I see that. I just said they should refuse.
edit: apparently Wunsequenced is enabled by default so clang should warn you out of the box.
Also, imagine a situation where the line of code actually lists three different variables, but all three of them are passed in by address. It quickly becomes impossible for the compiler to know you violated the spec by reusing the same variable. And even optimizations that make sense here could corrupt the value pretty badly and possibly lead to worse errors.
OK. What is the value of a spec to which compliance is impossible?
It lets you tell people you have a spec? It makes it easy for compiler developers to dismiss bug reports with "your code violated the spec"?
The concept of "compiling a program that doesn't comply with the spec" doesn't even exist! A text file that doesn't comply with the C spec isn't a C program. That's what it means to be "the spec".
The mechanism in the ISO document is phrases of the form "Ill-formed, No Diagnostic Required" which is often shortened to IFNDR. Lets break that down. "Ill-formed" means this is not a valid C++ program. On its own that means the compiler should provide a diagnostic (an error messag) explaining that your program isn't valid. For example if the program text were to just consist of the word "fuck" that's ill-formed and will be diagnosed. "No Diagnostic Required" says in this case though, we don't require the compiler to report this problem.
Why do that? So originally there's a purely practical reason, but ultimately there's a philosophical one. C++ like C before it wants to translate many individual program files and then somehow cobble the resulting output into a single executable. So this means function A over here, using type T from a different file cannot know for sure about type T, instead C++ has a thing called the "One Definition Rule" which says you must somewhat define T each time it's needed, but all the definitions must be the same. What if you don't (by mistake or on purpose)? Well that will cause chaos, so, IFNDR.
Philosophically IFNDR is a way to resolve the dilemma from Rice's Theorem. Back in about 1950 this guy named Henry Rice got his PhD for proving that any non-trivial semantic property of a program is Undecidable. This isn't "Oh no, it's quite hard to do this" it's a straight up mathematical proof that it can't be done. Deciding reliably whether a program has any† semantic property isn't possible. Sometimes we're sure, and that's fine, but the dilemma is for the tricky cases: What do we do when we're not sure?
IFNDR is C++ choosing "Fuck it, it's fine" for this case. Maybe your program is nonsense, it might do absolutely anything, but you don't get even a warning from the compiler. This is Chandler's "false positive".
Rust chooses the opposite. When the compiler can't see why your program is sense it will be rejected, even if you and a room full of compiler experts agree it should work too bad, it doesn't compile. You get a diagnostic explaining why your program was rejected.
† Trivial means either all programs have the property or none do and so isn't interesting. As a result the restriction to "non-trivial" properties isn't much help.
Wrong. Lots of spec violations only happen at runtime and can't be predicted at compile time.
Here's an easy example. You're the compiler. I hand you what appears to be valid C code that allocates an array and then asks the user which slot to use. It doesn't verify the slot is in bounds, just puts a number in array[slot], does some math with it, and then prints the result. Does my program comply with the spec? Do you compile it?
For example if you attempt an equivalent mistake in WUFFS that will be rejected.
Your WUFFS compiler will say this variable named slot must be a non-negative integer smaller than the length of the array, but as far as it can tell you didn't ensure that was true, therefore this code is nonsense, do better.
As I explained in my sister reply, in a broader context some of these are semantic properties and so there's a dilemma and C++ chooses to resolve that dilemma by accepting nonsense programs, but that wasn't the only available resolution and I am confident it's the wrong choice.
Yes.
> and not compile programs that don't.
No, there is no limitation on what a compiler does in this case.
> The concept of "compiling a program that doesn't comply with the spec" doesn't even exist!
It does, it is called "undefined behaviour".
> A text file that doesn't comply with the C spec isn't a C program.
That's the point. A program that contains UB is not a valid C program. That's what UB means.
C++ has an even more trivial example: To be a valid C++ program, all loops without side-effects must terminate. Thus determining if some C++ programs are valid would require solving the halting problem.
But more seriously it's the job of the program to not do undefined things.
What's the undefined behavior in assembly?
Probably more important, way too many things in assembly vary by exact model. Can you name a portable language that fits those criteria?
Are you saying, what's the value of a language spec that allows undefined behavior, as C does?
Well, it's that it allows for compiler implementations that aren't too hard to implement and maintain.
It allows for a language that's close enough to hardware (and allows you to do programming on a low level), while still offering a reasonable amount of abstraction to be useful (and usable).
It's also difficult to define a formal system that won't have undefined expressions. Mathematics itself is full of them (in logic, "this sentence is a lie" has no truth value; you can't define the set of all sets, or a set of sets that don't contain themselves; etc).
That said, I think we've settled on a rather silly choice here with the "++" operator.
Personally, I'd do away with the ++ operator in either pre- or post- increment forms, or at least disallow it in arithmetic expressions.
The only thing having it realistically accomplished is saving a few characters when writing a for-loop in C.
Even for that it's not necessary.
The problem with it is that, unlike normal arithmetic operators, it both returns a value and assigns one, which means that you can assign values to several variables in a single arithmetic expression, as in
a = b++;
a = (b = b + 1);
Now, I have the following religious belief, and it's that arithmetic operators shouldn't have side effects. That's to say, assignment and evaluation should be separate.
So that when I write
x = (arithmetic);
Perhaps calling the function sqrt(x) would summon Cthulhu — I'll read the documentation for it to be sure. But in general, I'd hope that calling abs(x) wouldn't change the value of x to |x| in addition to returning it.
But K&R decided to have fun by saying that "x = 5;" is both an assignment and an expression with a value. Which allows one to write:
x = y = z = 5;
That's it, that's the only utility.
Instead of defining this as a special initialization syntax and otherwise disallowing it (as Pyhthon does), they went YOLO and made assignment an expression rather than a mere statement.
Which means that the very useful statement "increase the value of this variable by one" became two expressions with different values.
In an ideal world, the following would be equivalent, and would not evaluate to anything you can assign to a variable:
++x;
x += 1;
x = x + 1;
And that's how it is in Go. Thompson fixed the design mistake after 4-5 decades of it giving everyone headaches.
Sadly, C++, Java, C# all wanted to be "like C" in basic syntax, so we're stuck with puzzles like this to this day.
TL;DR: if you're asking "what's the value of the spec that makes assignment an expression", i.e. why is making "a = (b = c + d);" valid syntax a good idea, the answer is:
It isn't. It's a bad decision made in 1970s that modern languages like Go no longer support.
``` target[i++] = source1[j++] + source2[k++]; ``` That's idiomatic, it shows the intent to read and consume the value in a single expression. You can write it longer, but not more clearly.
It's only when you assign to the same variable multiple times, or read it after it was assigned, that it introduces ordering issues.
A single `i++` or `++i`/`i += 1` is safe and useful.
Sure, and you don't need the assignment to be an expression with a value for it to be useful.
>target[i++] = source1[j++] + source2[k++]; That's idiomatic
That's idiomatic to C for sure.
Also idiomatically horrible. Why are you using three index variables here?
>You can write it longer, but not more clearly.
target[i] = source1[i] + source2[i];
i++;
You can't forget to increase one if the indices when all three are meant to go in lockstep.
It's longer by one semicolon, and requires far less cognitive overload to parse.
There's a reason why they did away with it in Go. What do you think that reason was if it's so useful?
> You can't forget to increase one if the indices when all three are meant to go in lockstep.
Obviously they are not in this example.
The next line might contain:
i++; j *= 42; k = srandom (k), random ();...of utter insanity which doesn't belong in any real world code.
It just keeps getting worse, and shows why it was a horrible idea to allow this in the first place.
>The next line might contain:
i++; j *= 42; k = srandom (k), random ();
You're already doing it there, why do you need to do an assignment inside the brackets?
(This was a rhetorical question. You don't).
It is useful to distinguish between consuming an element and only jumping to it. So you would have an ptr[i++] for consuming the current token, but not, when you are switching to another token.
A grouping of index and array modification also provides clarity about the intention. It would read very annoying if that constantly would be split into two steps, and also provides more room for error.
It's obvious that you do prefer the stylistic choices Go made, but that doesn't mean everyone does.
So, it's trivial to do it with a function. Or a macro.
int adv(int *i){
int t = *i;
(*i) = t + 1;
return t;
}
while(i < 10)
printf("%d\n", adv(&i));
The point is, you don't need assignment to return a value to have this.
Can you give a non-contrived example where you really need it?
>It's obvious that you do prefer the stylistic choices Go made, but that doesn't mean everyone does.
It's not that I "prefer stylistic choices of Go", it's that I hate to have undefined behavior in language spec which is easy to stumble into - the cost of the "stylistic choice" that C made doesn't make that choice justified.
> It allows for a language that's close enough to hardware (and allows you to do programming on a low level), while still offering a reasonable amount of abstraction to be useful (and usable).
I can see the first of these. The second appears to be untrue; if you removed the concept of undefined behavior from C, it wouldn't get farther away from the hardware.
Is that first point actually something that somebody wants? Who benefits from the idea that it's easy to write a "standards-compliant" compiler, because you are technically "standards-compliant" whether you comply with the standard or not?
At that point, you've given up on having a standard, and the interviewers Susam calls out, who say that the correct answer is whatever their compiler says it is, are correct in fact. Susam is the one who's wrong, for reading the standard.
You can run a language that way just fine. I had the impression that Perl was defined by a reference implementation. But it's the opposite of having a standard.
My understanding is that even common CPU instruction sets can have undefined behavior[1].
When C was written, the CPU architectures were more of a Wild West. It might have made sense to leave some parts up to the compiler authors on a particular architecture.
>Is that first point actually something that somebody wants?
When C was written — absolutely.
Portability of C code is almost taken for granted these days.
Things were different then. Portability was a big challenge.
All that said, this is my non-authoritative understanding of the reasons why it's a thing. Take it with a grain of salt.
>At that point, you've given up on having a standard
Sure. Just treat C as a family of languages which have a common standardized part.
Proprietary compiler extensions are/were common anyway, so that's not an unusual situation.
[1] https://www.os2museum.com/wp/undefined-isnt-unpredictable/
> The precedence and associativity of operators is fully specified, but the order of evaluation of expressions is, with certain exceptions, undefined, even if the subexpressions involve side effects. That is, unless the definition of the operator guarantees that its operands are evaluated in a particular order, the implementation is free to evaluate operands in any order, or even to interleave their evaluation. However, each operator combines the values produced by its operands in a way compatible with the parsing of the expression in which it appears. This rule revokes the previous freedom to reorder expressions with operators that are mathematically commutative and associative, but can fail to be computationally associative. The change affects only floating-point computations near the limits of their accuracy, and situations where overflow is possible.
So I think, the text in K&R serves as warning against writing such code, at best. The C99 draft has more relevant language. From § 4. Conformance:
> If a "shall" or "shall not" requirement that appears outside of a constraint is violated, the behavior is undefined. Undefined behavior is otherwise indicated in this International Standard by the words "undefined behavior" or by the omission of any explicit definition of behavior. There is no difference in emphasis among these three; they all describe "behavior that is undefined".
This along with the § 6.5 excerpt already mentioned in my post implies a += a++ + a++ to be undefined. When I get some more time later, I'll make an update to my post to include the § 4. Conformance language too for completeness.
Thank you for the nice comment!
> The other half is "but I do know the answer
If you claim to know the answer you've made a grave mistake and fooled yourself.
If you ran the code in a compiler and used that to conclude "this is the answer" rather than "this is an answer" then now is a great time to learn how easy it is to fool yourself. You just need you ask yourself what assumptions you made. I'll wager you assumed all compilers process this line in the same way.
Or just RTFA, or Susam's, as that's exactly what they are about. They explain why this is undefined behavior.
| The first principle is that you must not fool yourself — and you are the easiest person to fool.
- FeynmanYou would lose that wager.
What I mean by "I do know the answer" is that I know that this is undefined behavior and why it is undefined behavior and that different compilers can give different results and also that even if I test the compiler I use to see what it does I can't count on that not changing any time the compiler gets updated.
Except you can do, because "The answer is that this isn't a valid C program." is a sentence you can know.
I am not sure this code could be interpreted the same by different programmers and compilers alike. So I would never write it.
It's common for interview questions to explore unusual code, perhaps poor quality code, that hinges on edge cases of the language. A candidate with a strong understanding of the language would be expected to take the opportunity to demonstrate it.
I still believe it's a good piece on your powerpoint if you want to teach. It's easy to fall, easy to grasp, and easy to unroll all the rules - that is, if the rules are actually set in stone.
On the other hand I've been through couple FAANG interviews, and twice I was presented with something similar and after I glanced at it for a half a minute the interviewer quickly proceed to "a ha!, you don't know! the interview is over , but I'm happy to tell you the right answer".
That part is not cool.
In the vast majority of the programming languages, the order of evaluation for the actual parameters passed to a function is undefined. In the few programming languages where the order of evaluation is defined, that is actually a mistake in the design of that programming language.
This is something about which any programmer must be well aware, because when composing function invocations it is very easy to write a function invocation where the result would depend on the order of evaluation of the expressions passed as actual parameters. The arithmetic operators are also function invocations, so that applies to them too.
this simply means your functions aren't pure functions, and is doing side effects. If you rewrite those functions to not have side effects (including ones being used to generate the parameters), there would be zero issues of such nature.
[1] By which I mean predicting the behavior of error-prone code that requires good knowledge of all the quirks of the language to correctly answer.
Other than the job for most programmers having nothing to do with whether they know the outcome, because hopefully they'd never write something like it or clean it up. And IF they found it they'd hopefully test it - given that it appears to be compiler dependent anyways.
Are you referring to the type of interview questions where the question is ill-defined and no one should know the answer, or the type where the question is reasonable and well-defined, but the interviewer doesn't know the answer?
I had a phone screen with Google once where they asked how to determine the length of a stretch of contiguous 1s within an infinite array of 0s. I suggested that, given the starting index i, you can check the index i+2 and then repeatedly square it until you find yourself among the zeroes, after which you can do binary search to find the transition from ones to zeroes.
The interviewer objected that this will grow the candidate end index too quickly, and the correct thing to do is to check index i+1 and then successively double it until you find the zeroes. We moved on.
I passed that phone screen. But I still resent it, because I checked the math later and "successive squaring followed by binary search" and "successive doubling followed by binary search" take exactly the same amount of time.
Your phone screen story is quite nice. When I read your question, I would have answered with successive doubling as well. In fact, I faced the same question at an AWS interview a long time ago. The question was mathematically the same question but formulated differently. I answered with the doubling solution too, which leads to an O(log n) time solution, asymptotically. Your interviewer's immediate objection to your squaring solution seems like a major failure in their intuition. When I read your solution, purely by intuition, that is, without resorting to any rigorous reasoning, I felt: wow, that's interesting, your solution would land on the zero region in merely O(log log n) time. Why didn't I think of it? I think your solution should spark interest rather than dismissal in a curious person. Of course, the binary search after that to find the exact transition point blows up the time consumed back to O(log n).
Once again, thanks for these really interesting comments!
I would be 100% behind a movement to replace interviewer freedom with externally-set, vetted questions.
Yes the first one was probably written in C, however long ago. Not super relevant now though.
JVM/JRE, probably a different story
No, and it's also well defined in languages like C#.
If we're talking about this specific example at least. No sequence point issues like that in Java.
The ++x is a "pre-increment", meaning the value of the variable is incremented prior to evaluating the expression, while the "post-increment" "x++" is the other way around: the expression evaluates to x, then x is incremented afterwards.
All expressions are left-to-right.
The reason the question is tricky is because those operators change the value of a as the full expression is progressively executed.
It's not immediately clear to me what the answer in Java would be.
Just take a++ + ++a for example:
If the value if `a` is hoisted by the jvm then it could be 5++ + ++5, so 5 + 6.
But if it's executed left to right and `a` is looked up every time, then it becomes 5++ + ++6, so 5 + 7.
The semantics of Java is not undefined on multiple assignments to the same variable in an expression, so it can't hoist something if it would change the outcome.
Now, I don't actually know what the outcome is, because I don't remember whether `a += e` reads the value of `a` before or after evaluating `e`. The code is still confusing and unreadable to humans, so you shouldn't write it, but the compiler behavior is not undefined.
And if your variable is accessed from multiple threads, it may be undefined which intermediate values night be seen.
$ cat a.java
class a {
public static void main (String[] args) {
int a = 4;
int b = a++ + ++a;
System.out.println(b);
System.out.println(a);
}
}
$ javac a.java
$ java a
10
6but still, if it were, it was and remained, as gp points out, bad practice...
$ /bin/cat x.c; gcc -w -o x x.c; ./x
#include <stdio.h>
int main()
{
int a = 5;
a += a++ + a++;
printf("a = %d\n", a);
}
a = 18
- The first a++ expression results in 5, after a = 6 - The second a++ expression results in 6, after a = 7 - Only then the LHS a is evaluated for the addition-assignment, so we get: a = 7 + 5 + 6 = 18
<source>:5:10: warning: multiple unsequenced modifications to 'a' [-Wunsequenced]
5 | a = a++ + ++a;
|
<source>:5:7: warning: operation on 'a' may be undefined [-Wsequence-point]
5 | a = a++ + ++a;
| ~~^~~~~~~~~~~
The moment such a question appeared, your chances of answering it in a way that would satisfy the interviewer immediately dropped to somewhere around 20%. Probably even lower. And if you decided to answer truthfully, the odds are even worse because most interviewers I stumbled upon did not care about or understand 'undefined behaviour' or 'sequence points'. I chose to answer truthfully every single time and, more than once, that left the interviewer flummoxed.
I am very glad these types of interview questions have become less prevalent these days. They have, right? Right?