Re: specifications (was Re: Languages: The Bigger the Uglier)

jgj@ssd.hcsc.com (Jeff Jackson) writes:


>Perhaps I'm being incredibly dense here (wouldn't be the first time),
>but I don't see why the "standard" implementation must execute all
>possible interleavings. It would only have to be random. Thus if you
>have a program that works on compiler A, but not on compiler B because
>of a dependency on the implementation's execution order (I'm not
>familiar enough with ADA to provide concrete example), running the
>program with the standard compiler would tell you that the program is
>not standard conforming and thus compiler B is not broken.


That's not correct, because the program might succeed with all
possible interleavings except the one that compiler B chooses.


>While a single run does not tell you anything, you can
>determine a program is standard conforming with a given certainty by
>doing enough runs.


That is incorrect statistical reasoning. The only thing you can be
sure of with a given certainty based on the number of random-choice
test runs is the probability that the program will pass the next
random-choice test run. There's no direct relationship between that
probability and the probability that the program is standard
conforming, or that it will pass a non-random-choice test, such as
being run on an actual compiler.


It would not be hard to write a program that passes a random-choice
implementation test with a probability as close to 100% as you care to
get, yet fails every time when run on some real implementations.
--
Fergus Henderson WWW: http://www.cs.mu.oz.au/~fjh
fjh@cs.mu.oz.au PGP: finger fjh@128.250.37.3
--

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