Re: What good is halting prob?

[mab@dst17.wdl.loral.com (Mark A Biggar)]

In article <3n429h$pvu@acmex.gatech.edu> gt2782a@prism.gatech.edu (Richard Ladd Kirkham) writes:
>In article <1995Apr19.204744.21914@wdl.loral.com> mab@dst17.wdl.loral.com (Mark A Biggar) writes:
>>
>>Another example: determining if changing the parameter passing method from
>>by-refernece to copy-in-copy-out and vis-versa changes the behaviour of
>>your program is also equivalent to the Halting Problem.  The Ada83 LRM
>>says that such programs are erroneous, but the above result means that
>>detecting such programs at compile time is not possible in gerneral.
>I don't get this.  *What* programs is the LRM calling erroneous?  Also,
>aside from a hardware failure or hardware inadequacy, wouldn't two other
>wise identical programs, one using by-reference and the other copy-in-copy
>back, behave identically?

No they don't behave identically.

The whole point is that it IS possible to write programs where the choice of
parameter passing method results in different behaviour.  This usually
happens with multiply aliased parameters, for example:

subtype name is string(1..3);
var: name := "abc";
procedure test(a,b: in out name) is
begin
	a(1) := 'd';
	if b(1) = 'd' then raise constraint_error end if;
end test;

Now look at the call "test(var, var);": if the parameter passing method is
by-reference then the call will raise constraint_error, but if 
copy-in-copy-back is used it won't raise the exception because the 
assignemnt to a(1) is made to a different copy then the test on b(1).

The Ada83 LRM calls such code erroneous, while the Ada95 LRM makes it only
a bounded error as there are only 2 possible results and both are well
defined.  But you can't require the complier to detect such code as doing
so can be shown to be reducable to the halting problem.  There is a paper
is a early issue of Ada Letters about this.

--
Mark Biggar
mab@wdl.loral.com