5 ms·

It's not impossible to write, but just extremely hard for anything that is not trivial. For example take function that takes a byte as an input and has byte as

by anfilt 8y ago

It's not impossible to write, but just extremely hard for anything that is not trivial. For example take function that takes a byte as an input and has byte as an output. Moreover has no external or internal state. You can run through all 256 inputs and check the outputs. However, if the function has 128 bits of input. You could not possibly enumerate all possible inputs and check the output. So it takes other methods to prove it's bug free. This can be hard to find, and there is no way to automate this in all cases. (Halting problem) However, bug free code is not impossible to write. I might say a bug free system is more likely to be impossible since would involve perfect hardware that is also immune to interference, and the physical world can cause a bit to flip while performing a computation.

laumars 8y ago
That code doesn't run independently. You need a compiler, compilers aren't bug free. You need other functions to gain it's input and functions to do something with the output - those might all contain bugs. Even if you're not targeting different OS's or even "POSIX's", and even if you're not targeting different CPU architectures, you still get subtle variations in AMD64 chips that can - if you're working low level enough - throw up some bugs. And if you're not working that low level then you have the entire runtime stack and their bugs to contend with. If computing was still just flipping switches and waiting for LEDs to flash then you might have a point. But in real terms, it's just not possible to write 100% bug free code anymore. The real trick is eliminating all the bugs that people are likely to experience in normal operation and all the bugs that attackers might exploit. Even that is no small feat.
- vfclists 8y ago
  I think Dijkstra put paid to that argument ages ago. The program is an abstract that the compiler implements. If the compiler is faulty that doesn't make the program faulty. It is like arguing that because a ship's navigation system was faulty the directions given for a destination were wrong. To use his words we supply computers to programs, we don't supply programs to computers. or something to that effect. https://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD1036.html https://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD103... Paragraph beginning "But before a computer is ready to perform a class of meaningful manipulations ..."
  - zzzcpan 8y ago
    But you can't make a program without interpreting a spec and making lots of assumptions about the world including the ones about the compiler, that may or may not hold. So you can't make a program guaranteed to be bug free for the world, only for your interpretation of the spec.
  - laumars 8y ago
    I agree with you to an extent but the issue isn't so much who's to blame for unexpected behaviour but rather who's responsible for fixing it. You could make all kinds of reasoned arguments about who's to blame if a compiler optimisation or even outright compiler bug caused good code to behave badly under certain conditions but ultimately the end users don't care as they would still expect the application developers to fix the build scripts and/or project code regardless. To use the ships navigation system example, if you have some kind of "auto-pilot" system that would steer a ship into central London when a bad destination was set, then you'd quickly demand the authors of the auto-pilot to write exceptions for bad destinations. That's the ugly side of development; all too often us developers are having to write code to handle ugly systems. It's not fun but it's usually necessary.
zzzcpan 8y ago
Bug-free code implies perfect understanding of a perfect spec, which is something that cannot exist in the real world. We don't have the capacity to interpret everything perfectly correctly or perfect understanding of the universe. We barely have enough understanding to even make a spec for something. Luckily perfection and correctness are not important. While the desire to mathematically prove things may cloud judgement and waste time seeking mathematically perfect world that doesn't exist, we still can make almost anything work reliably on top of unreliable components with guaranteed probabilities. That's what resilience and fault tolerance are all about and how most of the world works. It's too bad that some of it is touched by this "let's do at least something for security" attitude and stupid perfect correctness ideology that of course never guarantees anything with any certainty, so we have planet scale security vulnerabilities that impact everyone to deal with.
dahart 8y ago
> It’s not impossible to write, but just extremely hard for anything that is not trivial. I think @laumars meant impossible in practice, not impossible in the strict mathematical sense. We can speculate that in theory it’s possible to write bug free programs that are large and complex, but nobody has ever done it. And not for flaky hardware or compiler reasons, all large software has many software defects, bugs in the design. It is not currently possible in practice to write a program like SQLite that is bug free, and no analysis of halting problem or number of input bits will tell us whether it could actually happen. Nobody even uses metrics like that for software stability because they don’t tell us anything practical.

by anfilt 8y ago

laumars 8y ago

That code doesn't run independently. You need a compiler, compilers aren't bug free. You need other functions to gain it's input and functions to do something with the output - those might all contain bugs. Even if you're not targeting different OS's or even "POSIX's", and even if you're not targeting different CPU architectures, you still get subtle variations in AMD64 chips that can - if you're working low level enough - throw up some bugs. And if you're not working that low level then you have the entire runtime stack and their bugs to contend with. If computing was still just flipping switches and waiting for LEDs to flash then you might have a point. But in real terms, it's just not possible to write 100% bug free code anymore. The real trick is eliminating all the bugs that people are likely to experience in normal operation and all the bugs that attackers might exploit. Even that is no small feat.

vfclists 8y ago
I think Dijkstra put paid to that argument ages ago. The program is an abstract that the compiler implements. If the compiler is faulty that doesn't make the program faulty. It is like arguing that because a ship's navigation system was faulty the directions given for a destination were wrong. To use his words we supply computers to programs, we don't supply programs to computers. or something to that effect. https://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD1036.html https://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD103... Paragraph beginning "But before a computer is ready to perform a class of meaningful manipulations ..."
- zzzcpan 8y ago
  But you can't make a program without interpreting a spec and making lots of assumptions about the world including the ones about the compiler, that may or may not hold. So you can't make a program guaranteed to be bug free for the world, only for your interpretation of the spec.
- laumars 8y ago
  I agree with you to an extent but the issue isn't so much who's to blame for unexpected behaviour but rather who's responsible for fixing it. You could make all kinds of reasoned arguments about who's to blame if a compiler optimisation or even outright compiler bug caused good code to behave badly under certain conditions but ultimately the end users don't care as they would still expect the application developers to fix the build scripts and/or project code regardless. To use the ships navigation system example, if you have some kind of "auto-pilot" system that would steer a ship into central London when a bad destination was set, then you'd quickly demand the authors of the auto-pilot to write exceptions for bad destinations. That's the ugly side of development; all too often us developers are having to write code to handle ugly systems. It's not fun but it's usually necessary.

zzzcpan 8y ago

Bug-free code implies perfect understanding of a perfect spec, which is something that cannot exist in the real world. We don't have the capacity to interpret everything perfectly correctly or perfect understanding of the universe. We barely have enough understanding to even make a spec for something. Luckily perfection and correctness are not important. While the desire to mathematically prove things may cloud judgement and waste time seeking mathematically perfect world that doesn't exist, we still can make almost anything work reliably on top of unreliable components with guaranteed probabilities. That's what resilience and fault tolerance are all about and how most of the world works. It's too bad that some of it is touched by this "let's do at least something for security" attitude and stupid perfect correctness ideology that of course never guarantees anything with any certainty, so we have planet scale security vulnerabilities that impact everyone to deal with.

dahart 8y ago

> It’s not impossible to write, but just extremely hard for anything that is not trivial. I think @laumars meant impossible in practice, not impossible in the strict mathematical sense. We can speculate that in theory it’s possible to write bug free programs that are large and complex, but nobody has ever done it. And not for flaky hardware or compiler reasons, all large software has many software defects, bugs in the design. It is not currently possible in practice to write a program like SQLite that is bug free, and no analysis of halting problem or number of input bits will tell us whether it could actually happen. Nobody even uses metrics like that for software stability because they don’t tell us anything practical.