Comment by ivanstojic | Hacker News Reader

Comment by ivanstojic | Hacker News Reader

Parent Full thread

There’s probably a practical argument to be made against the theoretical possibility of building such a system: I think that just the halting problem is proof that we cannot implement a system that does this.

But I think there are two arguments that might be worth more from a practical perspective: first, there are certainly programs with sections that could be optimized if you knew of some restriction on inputs. However, you could do that with tools available today (turn a variable parameter to a function into a constant, then compile and decompile the program). But by extension there must be programs whose representation is already the simplest form of expressing the computation they do (eg. hailstone sequence).

Second, there are real world influences that reduce a program from theoretical computation to the practice of it (I/O considerations are just one example).

The language that could be fully analyzed would have to strip some of that complexity and in process become sub-Turing-complete.

Since my team at work maintains something like a data flow language, I always find a different question that interests me: what if we selectively gave up Turing completeness? What if we embraced pure functional languages for more of our work? What could that buy us in terms of maintainability/quality of software?

> There’s probably a practical argument to be made against the theoretical possibility of building such a system: I think that just the halting problem is proof that we cannot implement a system that does this.

I think the halting problem only tells you that you cannot, in general, opinionate on what the program does, without expending an amount of computational effort equivalent to running that program. A better counterpoint is that you can't know ahead of time what values will be returned by IO calls.

But then, none of that really matters, because aiming for perfection is the wrong approach. You can make a tool described by the article, if you accept that it'll need to be advised sometimes. That is, at any point where the tool can't compute something - a value of a variable taken from the network, a function to call through a pointer indirection, etc. - it can ask you to give it a default value, give it additional assumption.

You'd also bound it using explicit heuristics, so it doesn't e.g. get stuck in long loops. Simulation of a marked bit of code takes more than 10ms? "Sorry, nope, can't process that." Then you could add options to annotate the offending loop, telling the simulator to finish it after at most 20 iterations. Or something like this. This tool would be a dialogue with code, not a batch job.

We know it's doable, because all such tool would do is to automate the thing we do when looking at code - running pieces of it in our head. In a way, it's just a different interface for doing the same thing you might be doing with unit tests - except it would be transient, and free to exercise any internal code in your program, not just poke at public module interfaces.

> We know it's doable, because all such tool would do is to automate the thing we do when looking at code - running pieces of it in our head.

Yes exactly. Except it would be much faster, more precise and with more coverage than what we get with mental execution. It still wont give you total coverage, but it would be able to show where it doesn't have coverage.

> In a way, it's just a different interface for doing the same thing you might be doing with unit tests - except it would be transient, and free to exercise any internal code in your program, not just poke at public module interfaces.

Yes. One additional aspect would be the ability to run with partial information. Eg. if a function needs three arguments, you need all three to run a test. However in abstract interpretation, you could just specify one argument and still trace the execution to some degree.

> I think the halting problem only tells you that you cannot, in general, opinionate on what the program does, without expending an amount of computational effort equivalent to running that program. A better counterpoint is that you can't know ahead of time what values will be returned by IO calls.

One corolary of the non-computability of the halting problem is that the problem "does this line ever run" is also non-computable

The halting problem only means that the problem "does this line ever run" is not computable for every case, since it's possible to construct undecidable cases. However, not all cases are undecidable and for most lines of most programs simple static analysis can indeed determine that certain lines will definitely run and certain lines won't.

As long as you accept that the solution won't give a yes/no answer but yes/no/maybe, an automated system definitely can opiniate on what the program does; for example, by actually attempting to run the involved fragments for a limited time.

Reply on news.ycombinator.com