[m-dev.] switch detection and calls

[Fergus Henderson]

Hi,

It seems that the current compiler's switch detection looks past calls.
This has unfortunate semantic consequences.
For example, when you compile and execute the following module with
`--strict-sequential' enabled, it prints out "222" rather than executing
in a strict left-to-right manner (modulo mode reordering) and thus
printing out "side effect" and then going into an into an infinite loop,
as the "Semantics" chapter of the Mercury language reference manual requires.

	:- module test.
	:- interface.
	:- import_module io.

	:- impure pred main(state::di, state::uo) is cc_multi.

	:- implementation.
	:- import_module require, bool.

	main -->
		( { impure p(no, Z) } ->
			print(Z), nl
		;
			print("p failed.\n")
		).

	:- impure pred p(bool, int).
	:- mode p(in, out) is cc_nondet.
	p(X, Y) :-
		(
			impure side_effect,
			loop,
			X = yes,
			Y = 111
		;
			X = no, 
			Y = 222
		).

	loop :- loop.

	:- impure pred side_effect is det.
	:- pragma c_code(side_effect, [will_not_call_mercury], "
		printf(""This is a side effect.\\n"");
	").

The compiler's switch detection used to stop as soon as it got to a call,
which meant that it used to handle cases like that one in the way that the
"Semantics" chapter specified.

I recall Tom Conway proposing that we allow switch detection to
look past function calls.  But I don't remember that proposal obtaining
a concensus (in particular, IIRC I myself did not agree with it).
So I'm surprised to find that the compiler behaves in this way.
Did this change just get in there accidentally?

I had a look at the mail archives and the cvs logs and diffs, and from
what I can gather, I think this change was introduced by Simon Taylor.
The mail message on Aug 26th 1998 describe the change as

 | Fix a bug which resulted from switch_detection and cse_detection differing
 | on what they considered to be a common deconstruction. The code to handle
 | complete one-arm switches leaves them alone, expecting cse_detection to move
 | the deconstruction out of the disjunction and rerun switch_detection. The
 | symptom is that a complete multi-arm switch is not found and a determinism
 | error is reported.
 | 
 | compiler/switch_detection.m
 |         Generalise the find_bind_var predicates so that they can be used
 |         by cse_detection.m.
 | 
 | compiler/cse_detection.m
 |         Use switch_detection:find_bind_var rather than similar code
 |         in cse_detection.m.
 | 
 | tests/valid/switch_detection_bug2.m
 |         Test case.

but the log message actually committed described it differently:

 | Fix a bug where cse_detection failed to hoist a common deconstruction for
 | a one-armed switch out where switch_detection expected it to, due to a
 | call getting in the way. This resulted in switch_detection not finding
 | a switch necessary to prove determinism correctness.
 | 
 | compiler/switch_detection.m:
 | compiler/cse_detection.m:
 |         Make both modules use the same code to find deconstructions of
 |         non-local variables of disjunctions.
 | 
 | tests/valid/switch_detection_bug2.m:
 |         Test case, taken from samples/diff.

This was committed just before 0.8 was released.

If you take the example given above, delete the occurrences of
`impure', and compile it with 0.7, it prints out "side effect"
and the loops until it runs out of stack space (tail recursion
optimization was broken in 0.7).  That is what the reference manual
says it is supposed to do.  If you compile with 0.8.1 or mercury-latest,
it prints out "222".  But there may have been some other changes
between 0.7 and 0.8 other than that one which affected this.

Comments?

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------