Jon Bentley, the writer of Programming Pearls, gave the task of writing an ordinary binary search to a group of professional programmers at IBM, and found that 90% of their implementations contained bugs. The most common one seems to have been accidentally running into an infinite loop. To be fair, this was back in the day when integer overflows had to be explicitly guarded against - but even then, it's a surprising number.
[1]: https://hiandrewquinn.github.io/til-site/posts/binary-search...
That they work for binary search is a very strong signal to people not familiar with them that they work for nearly everything (they do).
https://research.google/blog/extra-extra-read-all-about-it-n...
I think part of reason is that most people were taught a bad interface. Even the code on Wikipedia says “Set L to 0 and R to n-1”. That is, R is an inclusive bound. But we’ve learned that for most string algorithms, it is better when your upper bound is an exclusive bound, that is, n.
I’ve wanted to do an experiment testing that hypothesis. That is, ask a large number of people to write it with different function prototypes and initial calls and see how many buggy implementations I get with inclusive vs exclusive upperbound vs length.
L
== L[0:len(L)]
== L[0:l] + L[l:len(L)]
== L[0:l] + L[l:r] + L[r:len(L)]
I'd be interested to know why you feel that this is a useful interview question.
Implementing a well-known and widely implemented algorithm under stressful interview conditions wouldn't seem to me to demonstrate much about a candidate. In that situation I'd much rather be given a printout of some code and asked to talk around the implementation - how the code maps to the abstract algorithm, implementation trade-offs, readability, etc.
Prompt:
Please write a bug free binary search in python
Answer:
def binary_search(arr, target):
"""
Performs binary search on a sorted array.
Args:
arr: A sorted list of comparable elements
target: The element to search for
Returns:
The index of target if found, -1 otherwise
"""
left = 0
right = len(arr) - 1
while left <= right:
# Avoid potential overflow by using this formula
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
print(binary_search(test_array, 7)) # Output: 3
print(binary_search(test_array, 1)) # Output: 0
print(binary_search(test_array, 15)) # Output: 7
print(binary_search(test_array, 4)) # Output: -1
print(binary_search([], 5)) # Output: -1
print(binary_search([5], 5)) # Output: 0
print(binary_search([5], 3)) # Output: -1 mid = left + (right - left) // 2
Imagine, say, that left is 1 and right is 2^63 - 1. In Python left + right will just give you 2^63, no big deal. In C, left + right will overflow and produce undefined behavior; in practice it usually gives you I think -2^63, which is obviously going to screw up the bsearch a bit. It isn't wrong, just slightly less idiomatic for the language.
Python's interpreter may or may not be able to recognize and refactor the slight inefficiency of the extra arithmetic operation out. I will only point out that most of the time when we write our own bsearch it's because we want to optimize something really fundamental to the codebase. Any time you have to whip up your own algorithm it's prima facie evidence that that part of the code might be good to profile.
while (l < r)
{
//find the midpoint
auto mp = l + (l-r)/2;
if (nums[mp] == target) { prior = target;
#ifdef upper_bound
l = target + 1; // move the left bound up, maybe there's more up there we can look for!
#else
//lower bound, we found the highest known instance of target, but let's look in the exclusive left half a bit more
r = target - 1;
#endif
}
excuse the terrible formatting, it's been a long day grinding leetcode after getting laid off...
I have my rightmost code at part III of the miniseries, [1]. It loks quite similar, but I save the -1 for the very end return.
def rightmost_bsearch(L, T):
l, r = 0, len(L)
while l < r:
# Loop invariants. Always true! Comment out in production!
for somewhat_smol in L[0:l]:
assert somewhat_smol <= T # Note: Weak inequality now.
for lorg in L[r:len(L)]:
assert lorg > T
mid = (l + r) // 2
if L[mid] > T:
r = mid
else:
l = mid + 1
return r - 1 # return the first element AFTER L[r:len(L)].
[1]: https://hiandrewquinn.github.io/til-site/posts/binary-search...
When do you write code that doesn't need to search? (Unless you hand it all to the database, in which case... sure, you're good)
What was helping me was that before I wrote a single expression, I thought about it carefully in my head and where it would lead before putting pen to paper, because I didn't want to make a bunch of messy scratch out marks on it. Or, sometimes, I'd use a healthy amount of throwaway scratch paper if allowed. Once my path was fully formed in my head I'd begin writing, and it resulted in far fewer mistakes.
I don't always take this approach to writing code but often I do formulate a pretty clear picture in my head of how it is going to look and how I know it will work before I start.
In addition to pre-conditions and post-conditions, I would like to emphasize that loop invariants and structural induction are powerful techniques in CS proofs. https://en.wikipedia.org/wiki/Loop_invariant , https://en.wikipedia.org/wiki/Structural_induction
These notes from UofT's CSC236H are on-topic: https://www.cs.toronto.edu/~david/course-notes/csc236.pdf#pa...
So OpenAPI/GraphQL, tests and types and proof that the system works like intended. Always start with that before writing code. The specification is a solid base that doesn't change a lot if you start with it. How the code works, you can refactor it, and proof with the specification if it sill does the same like before.
Code is less important than the specifications.
OpenAPI and GraphQL have exceedingly poor types, and will not bring us there unless they make a fifty year leap forward.
Easier said than done. It is certainly feasible on greenfield projects where all the code is written by you (recently), and you have a complete mental model of the data layout and code dependencies. It's much harder to prove stuff this way when you call foo(), bar() and baz() across unit boundaries, when they modify global state and are written by different developers.
1. Progressively reducing the number of holes in your invariants
2. Building them such that there's a pit of success (engineers coming after you are aware of the invariants and "nudged" in the direction of using the pathways that maintain them). Documentation can help here, but how you structure your code also plays a part (and is in my experience the more important factor)
If, instead, you make the global variable immutable, make the state variable into a function argument, or even wrap the mutable global state in some kind of helper class, then you only need to know what the callers of certain functions are doing. The visibility of those functions can be limited. Caller behavior can be further constrained with assertions inside the function. All of these (can) make it easier to prove that the reader is correct.
I think most programmers already do this, actually; they just don't think of their decisions this way.
I think this reinforces the article's point.
Code like this is much more likely to contain bugs and be harder to maintain without introducing more bugs, than programs written from the outset with this goal of "provability".
I went in with 3 tickets in mind to fix. I found half a dozen more while I was down there, and created 2 myself. I don't know if I got off easy or I was distracted and missed things.
The other project I'm working on is not dissimilar. Hey did you guys know you have a massive memory leak?
Once cancer has metastasized, the treatment plans are more aggressive and less pleasant. The patient can still be saved in many cases, but that depends on a lot of external factors.
I wonder if someone like a John Carmack is just like… yeah I got it or he also is constantly feeling like he was bad 5 years ago and is doing it “better” now.
On a slightly related note… Competitive programming is surprisingly good at teaching you the right set of techniques to make sure your code is correct. You won’t progress beyond certain stage unless you pick them up.
Code for which there is not even a toehold for an imagined proof might be worth cordoning off from better code.
Appropriate abstractions (i.e., "idiomatic code for the language and codebase") make program verification easy. If you are hand-weaving an appropriately-abstracted program, there's little benefit to thinking about loop invariants and pre-post conditions, since they don't exist at that level of generality: correct proofs follow directly from correct code.
I highly recommend reading the book, it explains concept of writing idiomatic code way better than I ever could.
But writing clean and clear code in the hopes that it's good aesthetics will result in correctness would be cargo culting. (Writing clean code is still worthwhile of course, and clean code + code review is likely to result in better correctness.)
Form follows function, not the other way around.
I especially remember how learning the equivalence of recursion and induction immediately eliminated the “frustrated trial and error” approach for making recursive algorithms that work.
I learn more from these concrete case studies than from general principles (though I agree those are important too).
One of my most recent bugs was a crash bug in a thread-pool that used garbage-collected objects (this is in C++) to manage network connections. Sometimes, during marking, one of the objects I was trying to mark would be already freed, and we crashed.
My first thought was that this was a concurrency problem. We're supposed to stop all threads (stop the world) during marking, but what if a thread was not stopped? Or what if we got an event on an IO completion port somehow during marking?
I was sure that it had to be a concurrency problem because (a) it was intermittent and (b) it frequently happened after a connection was closed. Maybe an object was getting deleted during marking?
The only thing that was weird was that the bug didn't happen under stress (I tried stress testing the system, but couldn't reproduce it). In fact, it seemed to happen most often at startup, when there weren't too many connections or threads running.
Eventually I proved to myself that all threads were paused properly during marking. And with sufficient logging, I proved that an object was not being deleted during marking, but the marking thread crashed anyway.
[Quick aside: I tried to get ChatGPT to help--o3 pro--and it kept on suggesting a concurrency problem. I could never really convince it that all threads were stopped. It always insisted on adding a lock around marking to protect it against other threads.]
The one thing I didn't consider was that maybe an object was not getting marked properly and was getting deleted even though it was still in use. I didn't consider it because the crash was in the marking code! Clearly we're marking objects!
But of course, that was the bug. Looking at the code I saw that an object was marked by a connection but not by the listener it belonged to. That meant that, as long as there was a connection active, everything worked fine. But if ever there were no connections active, and if we waited a sufficient amount of time, the object would get deleted by GC because the listener had forgotten to mark it.
Then a connection would use this stale object and on the next marking pass, it would crash.
I know I already posted it moons ago but... Around 1991 I made a little game, similar to Canon Ball on the MSX (which later on Pang / Buster Bros did copy).
I had one weird case where sometimes the game would crash. Plain crash. But sometimes after playing for 15 minutes and already passing several levels. I just couldn't find it. I couldn't reason about it. I was stuck.
So I decided to rewrite not the entire game but the part dealing with the inputs / game logic to make it 100% deterministic. It took me a long time to do that. Then eventually I could record myself playing: I've record only the player inputs and at which moment they'd happen, which would make for tiny savefiles btw.
And eventually while I was playing and recording, the crash occured. I tried my replay: it worked... It replayed the savefile flawlessly and the game crashed again.
At that point I knew the bug was gone: being able to reproduce a bug in a deterministic way means I was going to fix it.
Turns out it was a dangling pointer (ah, C...): when the hero would catch an extra allowing him to fire two shots at once on screen (usually he'd only be allowed one) and would the first shot kill the last ball on screen, then on the next level the second shot would somehow (due to an error on my part) continue to live its live, eventually corrupting memory.
Fun stuff.
FWIW having deterministic game engines wasn't a thing back then. It became common later on, with games like Age of Empires and Warcraft III etc. using them: it was obvious for savefiles allowing to replay/exchangs games were tinier than tiny: they'd only save at which frame a player input happened and they'd replay the entire game from there [1]
I still have the code to that game, it was surprisingly fun. Someone here already offered help in the past to get it back on its feet. I've also got an executable that runs. I just don't remember how the tooling worked. Still have the BAT files etc. to build it, but not the tools. I really should look into that one of these days but I'm kinda busy with other projects / life.
[1] which also raised another issue: when game engines were upgraded, you could have savefiles only playing on older version of the game, so players would exchanges games and add the version of the game they were destined to
Nice story.
function simplifyTree(root: Node): Node {
let newChildren = [] as Array<Node>;
for (const child of root.children) {
const simplifiedChild = simplifyGraph(child);
if (shouldContract(simplifiedChild)) {
for (const grandChild of simplifiedChild.children) {
newChildren.push(grandChild);
}
} else {
newChildren.push(simplifiedChild);
}
}
root.children = newChildren;
return root;
}This should be obvious, right? This is how you are supposed to write code. You are supposed to have a simple proposition about what each chunk of your code does.
When done well, every test you write before you see it fail and then you write the barest amount of code that you think will make it pass is a mini-proof. Your test setup and assertions are what cover your pre/post conditions. Base cases are the invariant.
The key here is to be disciplined, write the simplest test you can, see the test fail before writing code, write the smallest amount of code possible to make the test pass. Repeat.
The next level is how cohesive or tightly coupled your tests are. Being able to make changes with minimal test breakage "blast radius" increases my confidence of a design.
Having your invariants and pre/post conditions correct is not enough. You also need to do the right thing. For example, you have a function that adds two durations in the form hh:mm:ss, you have mm <= 60 and ss <= 60 as an invariant, testing it is a good thing, but it won't tell you that your addition is correct. Imagine your result is always 1s too much, you can even test associativity and commutativity and it will pass. Having these correct is necessary but not sufficient.
Problem is, when you write tests first, especially tight, easy to run unit tests, you will be tempted to write code that pass the tests, not code that does the right thing. Like throwing stuff at your tests and see what sticks.
I much prefer the traditional approach of first solving the problem the best you can, which may of may not involve thinking about invariants, but always with the end result in mind. And only when you are reasonably confident with your code, you can start testing. If it fails, you will have the same temptation to just pass the test, but at least, you wrote it at least once without help from the tests.
Maybe that's just me, but when I tried the "tests first" approach, the end result got pretty bad.
Tests do not ensure that your functions are correct; they ensure that you are alerted when their behavior changes.
Second, TDD is a way to force dogfooding: having to use the functions you’re going to write, before you write them, helps you design good interfaces.
- Write a test that demonstrates that it is doing the wrong thing
- Watch it fail
- Change the code to do the right thing
- Ensure the test passes
And in return I get regression prevention and verified documentation (the hopefully well structured and descriptive test class) for almost free.
I don't think any amount of testing absolves the programmer from writing clear, intention-revealing code that is correct. TDD is just a tool that helps ensure the programmers understanding of the code evolves with code. There have been so many times where I write code and expect a test to fail/pass and it doesn't. This detects subtle minute drift in understanding.
> Problem is, when you write tests first, especially tight, easy to run unit tests, you will be tempted to write code that pass the tests, not code that does the right thing. Like throwing stuff at your tests and see what sticks.
I never had that problem, but I knew how to code before I started TDD.
The most complex piece of code I have ever written, as a relevant story, took me a month to prove to everyone that it was correct. We then sent it off to multiple external auditors, one of which who had designed tooling that would let them do abstract interpretation with recursion, to verify I hadn't made any incorrect assumptions. The auditors were confused, as the code we sent them didn't do anything at all, as it had a stupid typo in a variable name... I had never managed to figure out how to run it ;P. But... they found no other bugs!
In truth, the people whom I have met whom are, by far, the worst at this, are the people who rely on testing, as they seem to have entirely atrophied the ability to verify correctness by reading the code and modeling it in some mathematical way. They certainly have no typos in their code ;P, but because a test isn't a proof, they always make assumptions in the test suite which are never challenged.
Actually, a test _is_ a proof! Or more specifically, a traditional test case is a narrow, specific proposition. For example, the test `length([1, 2, 3]) = 3` is a proposition about the behavior of the `length` function on a concrete input value. The proof of this proposition is _automatically generated_ by the runtime, i.e., the proof that this proposition holds is the execution of the left-hand side of the equality and observing it is identical to the right-hand side. In this sense, the runtime serves as an automated theorem prover (and is, perhaps, why test cases are the most accessible form of formal reasoning available to a programmer).
What we colloquially consider "proof" are really more abstract propositions (e.g., using first-order logic) that require reasoning beyond simple program execution. While the difference is, in some sense, academic, it is important to observe that testing and proving (in that colloquial sense) are, at their core, the same endeavor.
My thought here is that since proofs are logic and so is code you can't have a proof that can't be represented in code. Now admittedly this might look very different than typical say JUnit unit tests but it would still be a test validating logic. I am not saying every system is easily testable or deterministic but overall, all else equal, the more tested and testable a system is the better it is.
IME things that are very hard to test are often just poorly designed.
You'll know quickly where you're going wrong because if you struggle to write the test first, it's a symptom of a design issue for example.
That being said, I wouldn't use it as dogma, like everything else in CS, it should be used at the right time and in the right context.
I tend to go the other way, I don't use TDD when I am playing around/exploring as much as when I am more confident in the direction I want to go.
Leaving a failing test at the end of the day as a breadcrumb for me to get started on in the morning has been a favored practice of mine. Really helps get the engine running and back into flow state first thing.
The dopamine loop of Red -> Green -> Refactor also helps break through slumps in otherwise tedious features.
- In the case of search or sort algorithms, where the primary concern is the speed of computation, undesirable states would be performing unnecessary or duplicate computations.
- In the case of encryption algorithms, undesirable states would be those that leak encrypted data.
- In the case of an order shipping and fulfillment system, an undesirable state would be marking an order as fulfilled when not all of the items have been delivered.
The more care that is taken to prevent undesirable states, the more the program takes on an algorithmic style. And the only way you can be sure that those undesirable states are impossible is to think in terms of proofs and invariants.
I also think things get complicated with holding things constant as a necessity. Often times, the best way to find a bug is to ask not "how was this possible?" but "why would another part of the system modify this data?"
Obviously, if you can make things reference capable data, you should do so. But, all too often "this data being X" has a somewhat self evident explanation that can help. And just "copy so I don't have to worry about it" lands you squarely in "why is my copy out of date?"
For embedded control I'm finding the blackboard pattern with single assignment to be super useful.
So more practical type systems can be viewed as "little" theorem provers in the sense the author is describing. "Thinking in types" so to speak, is mathematically equivalent to "writing little proofs in your head". I would also add that merely using types is not equivalent to "thinking in types" as one would be required to do writing a sufficiently advanced Haskell program.
Having an advanced type system does seem to encourage this sort of informal proof oriented thinking more than imperative and somewhat typeless languages do, though, since preconditions and postconditions and loop invariants and inductive proofs on loops are things you have to do yourself entirely in your head.
I believe programmers should learn a bit about programming language theory, mostly the bits about what is a language. Then how to recognize the things behind the labels, and how they morph (either from an operation or from a translation between contexts). Then it's a matter of using the knowledge to move from the environment to a DSL that can express the business rules.
Architecture is the draft for the above, defining the starting point and a direction. And design is where you start to make decisions following the plan. For someone that have an idea of the destination, they can judge both.
Tossing out a few observations:
1. People make mistakes. Your strategy needs to account for that (resilient runtime, heavy type-checking, convenient and often-used REPL, etc).
2. Above a certain project size, nobody remembers everything. Your strategy needs to account for that (excellent multifaceted documentation, disallow long-range interactions in your code, etc).
3. Dependencies have a vastly higher cost than you expect, even in the short term. Plan for that (vendor more things, in-house more things, allocate resources to dependency management, cut scope, etc).
I could go on. The core point is that certain properties of projects are "plainly" true to most people who have been around any length of time. I don't think we're yet at a point where we can often predict anything meaningful about some specific new technology, but a mental framework of "this succeeded/failed _because_ of {xyz}" helps tremendously in figuring out if/how that new idea will fit into your current workplace.
For what is to be proved, try to use divide and conquor to make the whole proof consist of separate steps, each of which gets a short proof and each of those steps might become a subroutine (whatever the terminology and functionality of the programming language and environment).
Several programming languages and libraries support Design-by-Contract (https://en.wikipedia.org/wiki/Design_by_contract) which lets you specify preconditions, postconditions, and invariants directly in your code.
Those predicates can be checked in various ways (depending on how deeply Design-by-Contract is supported) to help you know that your code is working correctly.
Ada supports Design-by-Contract as part of the language: https://learn.adacore.com/courses/intro-to-ada/chapters/cont...
SPARK extends Ada Design-by-Contract into full proofs: https://learn.adacore.com/courses/intro-to-spark/index.html
Rust has the Contracts crate: https://docs.rs/contracts/latest/contracts/
Other programming languages have various levels of support or libraries for Design-by-Contract: https://en.wikipedia.org/wiki/Design_by_contract#Language_su...
Many Design-by-Contract implementations are nicer than standard assertions because they help to express intent better and easily refer to the 'old' value of a parameter to verify desired results.
Also farthest in math/physics I got was intro to quantum mechanics which the multiple-pages to solve a problem lost me
Being a good programmer... I don't have a degree so I've never really tried to get into FAANG. I also am aware after trying Leetcode, I'm not an algorithm person.
What's funny is at my current job which it's a multi-national huge entity thing but I have to try and push people to do code reviews or fix small errors that make something look bad (like a button being shorter than an input next to it).
I am self-aware with true skill, I can make things, but I don't think I'd ever be a John Carmack. If you follow a framework's pattern are you a good developer? I can see tangible metrics like performance/some slow thing, someone better makes it faster.
Recently someone forked a repo of a hardware project I made. It's fun watching them change it, to understand what I wrote and then change it to fit their needs.
When I see my old code I do recognize how it was verbose/could be much simpler.
Bentley’s anecdote is a perfect illustration of how writing "correct" code often depends more on reasoning rigor than language syntax. Loop invariants, like you mentioned, are key here — they help anchor the logic through each iteration. It’s one of those patterns that separates surface-level understanding from deep intuition.
I also like how languages like Rust (with its strong type system) or Python (with clarity) can highlight these logic gaps early, especially in interviews or algorithmic codebases.
If you’ve got the link to your example post handy, I’d love to give it a read.
It made me think a lot more about every line of code I wrote and definitely helped me become a better programmer.
So many communication issues on teams occur when people are using the same words to mean different things.
Just to be clear, I wasn't claiming that "communicating clearly" is a new idea in software engineering, I'm mainly commenting on how effective embracing it can be.
When doing math, pretty much every term is "load-bearing" in that arguments will make use of specific aspects of a concept and how it relates to other concepts.
If you look at most graduate-level math textbooks or papers, they typically start with a whole bunch of numbered definitions that reference each other, followed by some simple lemmas or propositions that establish simple relationships between them before diving into more complex theorems and proofs.
The best software projects I've seen follow a roughly similar pattern: there are several "core" functions or libraries with a streamlined API, good docs, and solid testing; on top of that there are more complex processes that treat these as black-boxes and can rely on their behavior being well-defined and consistent.
Probably the common thread between math and programming is both lean heavily on abstraction as a core principle.
I'm curious though. When you're coding, do you actually pause and think through the logic first, or is it more like writing and fixing along the way?
For me, the best "trick" is to start with pseudocode.
The Isolation part is understandable and supports the philosophy:
> When requirements change, you extend the behavior of [your program] by adding new code, not by changing old code that already works.
- formal properties help one understand their own code better. This holds even more true when the properties are high level.
- they are useful to make sure the code behaves as expected, but not only. During the development, it notably helps finding better implementations and reviewing incremental changes.
- the process of outlining properties and drafting their proofs is already valuable, even without formally doing the proofs. It often prompts ideas about more properties and potential bugs.
- a great code is one that makes its rules and invariants obvious. This usually correlates well with general readability.
I notice you didn't really talk much about types. When I think of proofs in code my mind goes straight to types because they literally are proofs. Richer typed languages move even more in that direction.
One caveat I would add is it is not always desirable to be forced to think through every little scenario and detail. Sometimes it's better to ship faster than write 100% sound code.
And as an industry, as much as I hate it, the preference is for languages and code that is extremely imperative and brittle. Very few companies want to be writing code in Idris or Haskell on a daily basis.
Could anyone, please, explain me the meaning ? I can't get it.
It might help to think of this almost as debugging your program as you write it rather than only after you run it. Debugging a program is essentially the same process of trying to figure out why the program isn't doing what you think of doing. While there's information you can get by inspecting a running program or its outputs, there's often some amount of consideration you need to do in order to figure out why you think certain behavior might be happening. There's no fundamental reason this consideration can't happen before you actually run the program; even as you're writing the code, you can think about all the ways it could potentially go wrong, and why you're confident that this isn't the case. If you can't come up with a strong argument for that, it's a good sign you might need to reconsider your approach!
That's all there is.
You want to get better at something? Do it all day every day.
How to Think About Algorithms by Jeff Edmonds.
Persuasive Programming by Jerud Mead and Anil Shinde.
// x == 0 && (y == 0 || y == x + 1) && a[x + y] != 0
... code here ...
// x == 0 && (y == x + 1) && ...
---
Let me elaborate: there is a huge history of dubious allegations of what constitutes "a real programmer" or stuff that makes you "a better programmer".
Combobulation and descombobulation of McGuffins is often the best analogy though. Not to dismerit other kinds of thinkings, but already dismeriting them, that's what this is all about. When in doubt, showing the code is often what works.
In the merry software world, the challenges of improving our potential replacements are far too interesting and satisfying to leave room for any worry about consequences! :)