ericlippert

The "malice" aspect is a great one and I did not go into that in this post because of course back in the 1990s we were not at all concerned that someone would maliciously craft inputs that would slow down this algorithm.

In modern code we'd want to do a threat model that considered the consequences of untrusted inputs.

Hint: what is the correct behaviour of this method when given empty strings? Every string contains the empty string as a substring.

There is a dereference past the bounds of the query in one case in the last code sample, but there is no deference beyond the bounds of the source string.

You're probably thinking in C# or Java; remember that in C the convention is that a zero char ends strings. If the source string is shorter than the query string then the code will encounter a zero char in the source string at the same time as it encounters a non-zero char in the query string, and the inequality will end the loop before the beyond-bounds dereference.

There are other defects; can you find them?

I take your point, but let's be fair. My attitude was "this code is bad and I'm going to demonstrate my skill by improving it" when it should have been "please teach me what design and implementation concerns went into the choice of algorithm here". I was lucky to get a gentle and thoughtful correction for my presumptions.

My blog is about the design and implementation of programming languages; by understanding the causes of past mistakes we can learn to recognize them again today. The best mistakes to learn from are other people's!

WOW. JUST... WOW.

I will definitely try to remember that for next year!

Sure, that's entirely possible.

I'm curious to know if you knew from the moment of your birth that you should look at the operator table in this case, or if you learned that mitigation on a particular day. If the latter, what might you have done before you learned that?

Though I get the humour and agree with the sentiment, the history of C tells us that a language can massively succeed even with constant "breaking changes". One of the things I learned working at Coverity is that there is no such language as C or C++; rather, there are hundreds of mutually incompatible languages with those names. Almost no compilers implement any of the standards exactly, and there are so many standards to choose from. The vast majority of real-world line-of-business C programs are designed to work with a single compiler and are therefore never evaluated in terms of their correctness when ported to another compiler.

That said, the C# compiler team was and continues to be extremely concerned about breaking changes because we very clearly perceived the cost to customers and the barriers to upgrading entailed by breaking changes. I introduced a handful of deliberate breaking changes in my years on the C# design and compiler team, and every one was agonized over for many hours by members of the design team who were experts on the likely customer impacts.

It's rendered using the default WordPress theme ("Twenty Eleven") with the sole customization being that the body text colour is changed to purple. If it is rendering poorly, take it up with either WordPress or your browser provider; there's not much I can do about it.

The problem is "mostly solved" by adding a warning to a single compiler?

Sure, there are plenty of ways to mitigate the problem. That's not the point. The point is that the problem should not have arisen in the first place to require ongoing mitigation fifty years later!

Obviously yes, but that is question-begging. How does the novice programmer know that it is a good practice to use parentheses? x + y == z is correct, so it seems reasonable to conclude that x & y == z is also correct, particularly when the compiler does not complain about it.

And it's back. Thanks to Scott and Dan and all their colleagues for their prompt attention to this matter.

I vividly remember the meeting I went to in 2003 with a bunch of Microsoft bloggers and lawyers -- it was one of the few times Raymond Chen and I were in the same room. :-)

It was astonishing because of what the lawyers said: yes, it is a public relations risk to have ordinary employees communicating directly with the developer community, and we are willing to take on that risk if it dramatically improves our satisfaction metrics in the developer community.

We were basically told "don't be stupid, don't share corporate secrets, comport yourselves professionally, keep it on-topic, and if there are legal problems, legal will handle them appropriately".

I don't know that things would be the same today; it was a different time. But I'd hope so.

I take your point, but VS twitter is this week running a series of short videos with Larry Osterman about how awesome COM is, which seems to argue against this theory.

That said, lots of times Microsoft's left hand does not know what the right hand is doing.

Thanks Dan, much appreciated.

Indeed, Scott has been thoroughly awesome today. :-)

Thank you, that's a kind thing to say. I find that if I cannot explain a topic clearly to someone else, I probably don't understand it very well myself. :-)

By a huge margin! And putting together that beginner course only took me a couple of months working in my spare time, and recording it only took a couple of days in O'Reilly's studio.

I still edit my friend's programming books, but I sure don't do it for the money.

That's terrible. Those comments were alternately hilarious and informative.

The reason for writing this is to gently introduce the general topic of improving how we represent stochastic workflows in mainstream programming languages. Entering that complex topic by exploring just how horrid even the most basic aspects of randomness are represented is an accessible and compelling entry point.

This is part three of a very long series that will explore the connections between LINQ, probability distributions, and the difficulties of sampling from arbitrary distributions.

One of the reasons I wrote this article was because of exactly the problem that you mention, so I am very happy that you found it interesting! I frequently interview recent CS graduates, and ask a technical question about techniques for removing recursions; the people who do well on such questions tend to have practical experience writing compilers. A lot of these basic techniques are not covered in undergraduate courses, but they are crucial to understanding how modern programming languages work under the hood. I still have my notes from my fourth year course in continuation passing style from my undergrad days and it was very helpful to me when we started adding these concepts to C#.

The point is to demonstrate the general truth that any method with a single recursion can be turned into a loop by making a series of small, safe program transformations. It is not intended to be a demonstration of a technique for writing more understandable code.

I discuss tail calls in part two. I am often surprised by the number of people who will criticize part one of an article for omitting certain details before reading the second part. Was "part one" unclear in some way?

You are not the only one who thought that; see the comments to my post. As I note in part two, the point of the article was to show the general method; there are of course many ways to solve the original problem more efficiently. The specific problem is trivial and unimportant.

That's correct. I'll discuss CPS in part two.

My lips are sealed.

Your assumption is pretty good! I won't use continued fractions directly but the Stern-Brocot tree method can be understood in terms of continued fractions.

Yes. There are so many possible biases when interviewing and it is hard to keep them all in mind at once. The practice of science is essentially one long story about overcoming those human tendencies to arrive at the truth.

No, because we are actually building telescopes here, and astronomy PhDs apply, and when they are not actually clear on the difference between a reflector and refractor telescope you realize, hey, this person is going to need to learn so much about the very basics of the field that they're applying for that it's not going to be a good fit.

I've had candidates with PhDs in computer science who thought that pointers on 64 bit operating systems were two bytes wide. Do they believe that there are only 16000 possible allocations before the allocator fails? Not likely, because that's ridiculous. So how could they have that belief? because they understand so little about pointers that they don't understand the implications of their false beliefs.

I need someone who is going to command the salary that a PhD-level candidate will demand to be able to hit the ground running.

The solution to this problem is to follow up the question with "oh, so you're an eight, great, what is something that a seven would have difficulty with?" Make them calibrate the scale for you.