[mercury-users] impose a computational rule

[Fergus Henderson]

Erwan Jahier, you wrote:
> Tyson Richard DOWD wrote:
> 
> > Is there a particular application
> > you have in mind that would benefit from such controls?
>
> Yes : I'd like to adapt in Mercury a program transformation for Prolog
> that permiting to trace Prolog programs. This transformation insert
> instructions (such that "write(call,Pred)") in the source code. It is
> based on the definite search rules of Prolog. That's why, to adapt that
> transformation, I need the clauses not to be reordered.

Ah.

Relying on implicit side-effects is not really a good idea.
Mercury is a pure language, which means that all Mercury predicates
and functions are supposed to have a declarative meaning as mathematical
predicates and functions.  The compiler is allowed to take advantage
of this.  By relying on side-effect I/O, you are in effect lying to
the compiler, and as the saying goes, there is every chance that the
compiler will gets its revenge.  There are lots of things that the
compiler might do other than reordering which would break such code:

	- the compiler might optimize away calls to det goals
	  with no output arguments
	  (and indeed it does, if you specify the `--no-fully-strict'
	  option)

	- the compiler might decide to optimize goals such as
	  `write("failed"), fail' to just plain `fail'
	  (and indeed it does, if you specify the `--no-fully-strict'
	  option)

	- the compiler might optimize away duplicate calls to
	  predicates or functions with the same input arguments
	  (and indeed it does, unless you specify `-O1' or lower
	  [the default is `-O2'], or `--no-optimize-duplicate-calls')

	- the compiler might decide to automatically memoize
	  the results of all goals with no output variables
	  (it doesn't yet, but maybe next release...
	  I think several Haskell compilers do this
	  sort of optimization)

	...

There are several alternatives:

	- transform the code to well-behaved Mercury code,
	  by changing nondet procedures into det procedures that
	  return a list of answers, and adding io__state arguments
	  to procedures that don't have them

	- write a Prolog back-end for the Mercury compiler,
	  that converts the Mercury compiler's high-level
	  intermediate data structure (HLDS) to Prolog
	  (this would not be difficult);
	  then, modify this Prolog back-end to optionally
	  also perform the tracing transformation.

	- write the tracing transformation as an HLDS to HLDS
	  transformation pass for the Mercury compiler;
	  if it is the last such pass invoked before low-level
	  code generation, that would probably avoid most
	  of the issues mentioned above

That said, if you compile with `--strict-sequential' (an abbreviation
for `--no-reorder-conj --no-reorder-disj --fully-strict') and
`--no-optimize-duplicate-call', and implement your non-logical
side-effect I/O using the C interface, then it will probably work,
at least for the current release.

Cheers,
	Fergus.

P.S.

Another more long-term alternative would be to extend the
Mercury support for meta-programming to include support for
a Mercury equivalent to Prolog's clause/1, just as we have
(in our latest development release) added support for Mercury
equivalents to Prolog's functor/3 and arg/3.
Then, you could write a tracing meta-interpreter.

With appropriate compiler optimization (i.e. partial evaluation --
but its really only a relatively small advance on the sort of
cross-module inlining and specialization that the Mercury compiler
already does), the meta-interpreter approach could be made
just as efficient as the transformational approach.

(If anyone is seriously interested interested in pursuing
this idea, contact me and I can give some more details.)

-- 
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.