[m-dev.] Feature proposal: generic inline iterations

[Mark Brown]

Hi Sebastian,

Thanks for writing down the details of this proposal; I'm fairly happy
with this kind of language feature being added.  A couple of preliminary
remarks, though:

On 22-Dec-2005, Sebastian Brand <sbrand at csse.unimelb.edu.au> wrote:
> (1) At the core is a predicate do/2 whose first argument consists of
> a sequence of
> 
> 	fromto(First, In, Out, Last)
> 
> expressions, describing the iteration control.  The second argument
> is the iteration body, a sequence of regular Mercury statements. 
> Using infix notation, we have statements
> 
> 	...
> 	(
> 	fromto(First1, In1, Out1, Last1),
> 	fromto(First2, In2, Out2, Last2),
> 	...
> 	fromto(FirstN, InN, OutN, LastN)
> 	do
> 		%  the iteration body is any Mercury code, here
> 		%  exemplified by a single predicate body/2N
> 		%
> 		body(In1, ..., InN, Out1, ..., OutN)
> 	),
> 	...

Note that in order to parse the way we expect it to, do/2 will need to
have a priority greater than 1000 (which is the priority of ','/2).
I have no objection to adding such an operator.

It would be nice if the new feature worked well with state variable syntax.
For example, using the above form, it could be possible to write

	fromto(First1, !Local1, Last1)

but there would be no corresponding way to use a state variable for the
non-local variables.  You would be forced to write

	fromto(!.Nonlocal1, !Local1, !:Nonlocal1)

instead.  Perhaps the argument ordering could be changed to better support
state variable syntax (at the risk of confusing Eclipse users)?

> 
> The iteration shares only the First_i and Last_i variables with the
> context.  The In_i, Out_i are local variables shared between the
> iteration head and the iteration body.
> 
> Operationally, this should behave as follows.  The entire iteration
> statement is replaced by the call
> 
> 	do_XX(First1, ..., FirstN, Last1, ..., LastN)
> 
> were do_XX is a fresh predicate name.  This predicate do_XX is created
> by the compiler during compile time as
> 
> 	do_XX(In1, ..., InN, Last1, ..., LastN) :-
> 		In1 = Last1,
> 		...,
> 		InN = LastN.
> 
> 	do_XX(In1, ..., InN, Last1, ..., LastN) :-
> 		body(In1 ..., InN, Out1, ..., OutN),
> 		do_XX(Out1, ..., OutN, Last1, ..., LastN).
> 
> 
> The determinism of do_XX can ideally be inferred from the body;
> typically it is semidet or det.

I think it would be hard for the compiler to prove this in general.  That
is, it would be hard for the compiler to prove that the above two clauses
are mutually exclusive, so it could only infer that the goal is multi or
nondet.  Maybe the meaning of it should instead be:

	do_XX(In1, ..., InN, Last1, ..., LastN) :-
		(
			In1 = Last1,
			In2 = Last2
		->
			In3 = Last3,
			...,
			InN = LastN
		;
			body(In1, ..., InN, Out1, ..., OutN),
			do_XX(Out1, ..., OutN, Last1, LastN)
		).

where I've assumed that (First1, Last1) and (First2, Last2) have the
(in, in) modes and the others are (in, out) or (out, in).

On the other hand, maybe sometimes you intend for the clauses to be not
mutually exclusive.  That is, do we ever want to write do-goals which are
meant to be nondet even though the body isn't?

The drawback of the if-then-else approach is that the declarative semantics
is not quite as simple, and also that the goal would only work in one mode
(that is, the meaning of the goal would depend on the mode, so it couldn't
always be used in multi-moded predicates).  The drawback of the disjunction
approach is that it would be hard to write goals that are meant to be det or
semidet.

> The modes and types of the arguments
> of do_XX should be inferrred from the uses of the First_i and Last_i
> in the context of the iteration statement.  Typically, there's at
> least one i such that both First_i and Last_i are 'in', the others
> are such that First_j is 'in' and Last_j is 'out', or vice versa.

It would be desirable to be able to specify the modes of the fromto/4
arguments and to specify the determinism of the goal, much as we do for
lambda expressions.  In fact, it may be necessary to do this if mode/detism
inference proves too hard to implement.

For example, the following specifies the modes:

	(
		fromto(First1::in, In1::in, Out1::in, Last1::in),
		fromto(First2::in, In2::in, Out2::out, Last2::out)
	do
		...
	)

but I can't think of a good place to put the determinism.

> 
> These Mercury-specific issues need some examination.  A first
> implementation could just deal with some default iteration classes.
> 
> 
> 
> (2) Here is an example.  We collect the positive elements from a
> given list.
> 
> 	ex(!IO) :-
> 		List = [1, -2, 3, 7, -9, 0],
> 		(
> 		fromto(List,    In1, Out1, []),
> 		fromto(PosList, In2, Out2, [])
> 		do
> 			In1 = [X | Out1],
> 			(X > 0 ->
> 				In2 = [X | Out2]
> 			;
> 				In2 = Out2
> 			)
> 		),
> 		print(PosList, !IO).
> 
> This is treated as
> 
> 	ex(!IO) :-
> 		List = [1, -2, 3, 7, -9, 0],
> 		do_poslist(List, PosList, [], []),
> 		print(PosList, !IO).
> 
> with the new predicate defined as follows:
> 
> 	:- pred do_poslist(list(int)::in, list(int)::out,
> 			list(int)::in, list(int)::int) is det.
> 
> 	do_poslist(In1, In2, Last1, Last2) :-
> 		In1 = Last1,
> 		In2 = Last2.
> 
> 	do_poslist(In1, In2, Last1, Last2) :-
> 		In1 = [X | Out1],
> 		(X > 0 ->
> 			In2 = [X | Out2]
> 		;
> 			In2 = Out2
> 		),
> 		do_poslist(Out1, Out2, Last1, Last2).

This wouldn't compile, since no switch would be detected on any of the
arguments and therefore the determinism could not be proven to be det.
If the compiler was able to infer that the mode of the third argument
was in(empty_list) then it might have a chance to prove it.  But I'm not
sure how well the compiler is able to infer subtype information, and I'm
pretty sure that generally it would be hard to get this to work in practice.

> Parameter passing is done by a fromto(P, P, P, P).  Etc.

It would be nice to be able to use non-local vars in the body.  These would
be processed as extra arguments to the do_XX predicate (similarly to how we
handle non-locals in lambda expressions).

> I'd be curious to hear any comments on this proposal.

There's definitely a few details left to work out, but I think it is worth
pursuing this proposal.

Cheers,
Mark.

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