Re: binary search debugging of compilers

On Sunday, May 14, 2023 at 9:20:54 AM UTC-7, Kaz Kylheku wrote:


(snip)


> Setup:
>
> We can (somehow) enumerate the N entities with integers, which we
> express using a pure binary enumeration. Then, we can discover the
> number of an erroneously processed element, one bit at a time.
>
> Procedure:
>
> First we treat all elements numbered ..XXXXXX0 using the new technique
> technique, and all others using the the old technique. If the
> system fails, we know that it's the ..XXXXX0 set which has one or more
> badly processed elements. Otherwise it's the other set, whose
> enumerations end in a 1. Either way, we have discovered the identity of
> the last bit.


There is the assumtion that only one of the N is in error.


Reminds me of ECC memory, which can correct one bit errors, and detect
two bit errors. After log(N) tests, you find the one that it is
supposed to be, fix it, and it either works or doesn't.


Then you work on a new set of tests.


Or start out with a more complicated set, which can learn more in one set.

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