[mercury-users] Appreciate some help: #2

[Thomas Charles CONWAY]

tcklnbrg, you write:
> % I get the error that main needs to be det or semidet,
> % but changing it returns that is needs to be the cc_multi
> % why would main ever be cc_multi?

Main must always be guarenteed to have at least one solution.
It is not legal to have a Mercury program which can fail at
the top level without having yielded a solution.

Multi is a determinism which requires that there be at least one
solution. For example:

:- pred p(int).
:- mode p(out) is multi.

p(1).
p(2).

Now, for main, we don't allow more than one solution since that
could require backtracking the state of the world (io__state),
which is impossible, so we allow a determinism of det (no more
than 1 solution, can't fail without producing a solution) or
cc_multi (at least one solution, but we only want the first one).

Given all this, consider your program.

The call to greaterThanZero could fail, so main could fail, therefore
it is considered illegal, and you get the error message you observed.
How then, can you write any programs that contain nondeterminism or
failure?

First, you can handle failure using if-then-else (or -> ; ):

main -->
	( { greaterThanZero(2) } ->
		io__write_string("2 is greater than zero\n\n")
	;
		io__write_string("2 is not greater than zero\n\n")
	).

There are two ways of handling nondeterminism:
If the nondeterministic goal has no bindings visible from the outside,
then from the outside it may be considered semideterminsitic: since
Mercury programs may not have any side effects, a nondeterministic goal
with no output bindings can only be observed to succeed or fail:

main -->
	(
		{ between(0, 7, X) },	% the condition of this if-then-else
		{ X = 3 }		% is nondet, but has no outputs
	->
		io__write_string("good. 0 =< 3 =< 7\n")
	;
		io__write_string("bad. 0 =< 3 =< 7 isn't true!\n")
	).

:- pred between(int, int, int).
:- mode between(in, in, out) is nondet.
...

This is all well and good if there are no output bindings, but say
that there are and you want to see them? solutions/2 is made for you!

main -->
	{ solutions(path(1, 3), Paths) },
	(
		{ Paths = [FirstPath|_] },
		io__write(FirstPath), io__nl
	;
		{ Paths = [] },
		io__write_string("there was no path\n")
	).

:- pred path(int, int, list(int)).
:- mode path(in, in, out) is nondet.

path(X, Y, [X, Y]) :-
	edge(X, Y).
path(X, Z, [X|Rest]) :-
	edge(X, Y),
	path(Y, Z, Rest).

:- pred edge(int, int).
:- mode edge(in, in) is semidet.
:- mode edge(out, out) is multi.

edge(1, 2).
edge(2, 4).
edge(2, 5).
edge(4, 5).
edge(5, 3).

The first argument to solutions is a higher order predicate closure
that has one output argument and is nondet or multi. solutions finds
all the solutions and returns them in a list that is sorted and has
any duplicates removed.

In the above example, I arguably misnamed the variable FirstPath -
it is first only in the sense that is was first in the sorted list.
Because Mercury is purely declarative, and it doesn't use a static
computation rule (in the sense that Prolog does), asking for the
first solution (in the Prolog sense) isn't all that meaningful,
since the clauses may be executed in any order, and conjunctions in
any well-moded order, however if we really wanted "a path" rather
than "the first path" (whatever that means), then there is an
alternative approach available by making main cc_multi rather than
det:

main -->
	(
		{ path(1, 3, [FirstPath|_]) }
	->
		io__write(FirstPath), io__nl
	;
		io__write_string("there was no path\n")
	).

...

Here, the fact that path is nondet is okay (so long as main is cc_multi),
because if it fails, main will still succeed, and any extra solutions
wil be pruned. Note that we may get any of the possible solutions, since
the program may be executed in any well-moded order.

BTW, If you're writing a template driven compiler, then the achitecture
I'd use is:

lexer -> parser -> checking -> code-gen

lexer: turn the list of characters into a list of tokens

parser: turn the list of tokens into an abstract syntax tree (AST)

checking: annotate/check the AST.

code-gen: use solutions/2 to match your templates against the AST,
	and choose from among the available code fragments.

Thomas
-- 
Thomas Conway <conway at cs.mu.oz.au>
Nail here [] for new monitor.  )O+