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

[Sebastian Brand]

Hi,

This is a proposal for a new feature in Mercury that would
allow succinct, inline formulations of generic iterations. 
It strictly generalises many common uses of
fold-expressions.

As far as I can see, it fits well within the Mercury
philosophy, and its implementation should be of moderate
difficulty.  Such inline iterations are available in at
least one other LP language, Eclipse, where they are
extensively used by the language and core library
developers as well as by end users.  For my explanation
I'll follow Eclipse's version, and I'll go just a bit into
'localisation' for Mercury for now.


(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)
	),
	...

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

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



(3)  There are a number of possibilities for improving the
readability for humans.  We may define

	foreach(X, List)

to be

	fromto(List, In, Out, [])

with

	In = [X | Out]

added to the iteration body by the compiler.  Similarly,

	for(I, 1, N)

may stand for

	fromto(1, I, I_next, N)

with an extra

	I_next = I+1

in the body.  Parameter passing is done by a fromto(P, P, P, P).  Etc.



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

Cheers,
Sebastian
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------