[mercury-users] goal manipulation

[Fergus Henderson]

On 18-Jun-2003, Alan Baljeu <alanb at cornerstonemold.com> wrote:
> I have a prolog program which I'm looking at rewriting.
> I was thinking Mercury might be the way to go.
> 
> A critical feature of my program is that it looks at a collection of non-deterministic
> goals which are generated at run-time, analyzes them, and reorders them for evaluation.
> This is not unlike Mercury's mode analysis, but it is not the same thing so I need to code
> the algorithm to do this myself.  After this, I need to execute the goals in sequence.
> 
> What approach would you recommend to achieve this task in Mercury?

I would probably use an ordinary Mercury data type,
probably a discriminated union type, to represent these goals.

Then, I'd write a Mercury predicate to evaluate such goals.
Since the goals are represented as an ordinary Mercury data
type, analyzing them and reordering them is straight-forward.
The only vaguely tricky bit is executing them.
But that's not too hard: can write an interpreter for your goals.

For example, here's some code from samples/calculator.m
which defines an "expr" type, and an interpreter which
evaluates terms of that type:

	:- import_module int.

	:- type expr
		--->	number(int)
		;	plus(expr, expr)
		;       minus(expr, expr)
		;       times(expr, expr)
		;       div(expr, expr).

	:- func evalexpr(expr) = int.
	evalexpr(number(Num)) = Num.
	evalexpr(plus(X,Y)) = evalexpr(X) + evalexpr(Y).
	evalexpr(minus(X,Y)) = evalexpr(X) - evalexpr(Y).
	evalexpr(times(X,Y)) = evalexpr(X) * evalexpr(Y).
	evalexpr(div(X,Y)) = evalexpr(X) // evalexpr(Y).

If you want to have nondeterministic goals, you can still do
something similar.  For example, suppose we replace the
`number(Num)' alternative above with `range(Low, High)',
which can evaluate to any value within the range.

	:- import_module list, int.

	:- type nondet_expr
		--->	range(int, int)
		;	plus(nondet_expr, nondet_expr)
		;       minus(nondet_expr, nondet_expr)
		;       times(nondet_expr, nondet_expr)
		;       div(nondet_expr, nondet_expr).

Then we can provide a nondeterministic interpreter for our
nondeterministic expressions:

	:- pred eval(nondet_expr, num).
	:- mode eval(in, out) is nondet.
	eval(range(Min, Max), X) :- X `member` Min..Max.
	eval(plus(X,Y),  EX + EY) :- eval(X, EX), eval(Y, EY).
	eval(minus(X,Y), EX - EY) :- eval(X, EX), eval(Y, EY).
	eval(times(X,Y), EX * EY) :- eval(X, EX), eval(Y, EY).
	eval(div(X,Y),   EX + EY) :- eval(X, EX), eval(Y, EY).

I don't know what sort of forms your nondeterministic goals will take,
but I suspect that you can use something similar to the approach used
above for nondet_expr.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------