News for hackers. Stuff that matters.
Re:Offload Mental Simulation by TeMPOraL on Sunday May 30, 2021 @03:58AM (#27331470)
> 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.

Re:Offload Mental Simulation by shalabhc on Tuesday June 01, 2021 @12:06PM (#27356700)
> 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.

Re:Offload Mental Simulation by savingsPossible on Sunday May 30, 2021 @04:41AM (#27331665)
> 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

Re:Offload Mental Simulation by PeterisP on Sunday May 30, 2021 @06:13PM (#27337395)
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.