Re: binary search debugging of compilers

On Monday, May 15, 2023 at 6:54:08 PM UTC-7, Kaz Kylheku wrote:


(snip)


> Say we have a basket of apples with a rotten smell emanating from it.
> We can subdivide it, and smell one half and the other. If both halves
> smell, we know we have two or more rotten apples and they ended up
> in different halves. This doesn't matter. We just pick one half and
> keep subdividing.


But the algorithm described, at least as I remember it, doesn't test both
halves.


Sniffing two baskets doesn't take so long, but two tests might.


I was suspecting that there were more efficient ways than doing
both halves, though didn't try to figure out what they might be.


> As long as we stay on the trail of the rotten scent, we will
> get down to one rotten apple, and we can use that apple to analyze further:
> what kind of mould or bacterium has infected it and so on. Probably
> the other rotten apples have the same root cause. If they have different
root
> causes, we can do another search after fixing the one root cause we have
found.


I don't know apple statistics so well. If you suspect more than one from the
beginning,


As a binary search, it should be 50% probability on each test.
If you see higher than 50% as the tests go on, it might look
suspicious already.

Return to the comp.compilers page.
Search the comp.compilers archives again.