[m-dev.] Adding Loops to Mercury

[Paul Bone]

I'm beginning to change my initial opinion.  I think that there are some
motivating reasons (as Matt showed) about why we would want this (cleaner
syntax etc).  I think it's also desirable as Peter Wang said for types other
than lists, for instance integers or other sequence-ish types.

There is another reason I'd like to add in to the discussion, I apologise
if someone has said this already.  We have many predicates such as foldl,
foldl2, foldl3 etc in the list module of the standard library. We also have
map_corresponding and numerous other predicates, each predicate has a
number of different modes.  It can be painful when you need to use a
predicate that fits one of these patterns in some ways, but doesn't fit the
number of accumulators, number of output or input lists (map_corresponding)
etc.  This is particularly bad when the ADT is abstract (like maps, but
unlike list) where you cannot write such a predicate without modifying the
standard library.

The Mercury contributors (including myself) are in a position where this is
less of a problem.  When working on the compiler it is easy to also
introduce a new predicate like this into the standard library.  But for
users of Mercury, especially those that do not contribute at all or
regularly to the compiler this must be a PITA.  As Mercury contributors we
must try to consider Mercury users who are not also contributors.

I now think that compiler support for loops and other patterns would really
help.

I think that the solution should be something smiliar to Matt's proposal
(below) that can also work on integers.  Peter Schachte's paper may also be
useful but I've not read it, John's reference to Visual Prolog might also be
useful.  Additionally, one case where I've seen this done before was SISAL,
a pure single assignment language that used loops that looked similar to
imperative loops http://en.wikipedia.org/wiki/SISAL.  Ultimately SISAL was
not adopted by the programming community because Fortran programmers found
it difficult to adjust to declrative programming.  More about SISAL:
http://www2.cmp.uea.ac.uk/~jrwg/Sisal/00.Contents.html  Matt: is there
something like this in Mars that we should also read?

On Fri, Jan 03, 2014 at 11:14:29AM +1100, Matt Giuca wrote:
> I would propose a for loop syntax for Mercury which can be used something
> like this:
> 
> :- pred print_key_values(assoc_list(string, string)::in, io::di, io::uo) is
> det.
> print_key_values(List, !IO) :-
>     for X-Y in List [!IO] (
>         io.write_string(X, !IO),
>         io.write_string(" = ", !IO),
>         io.write_string(Y, !IO),
>         io.nl(!IO)
>     ).
> 
> The features of this syntax are:
> 
>    1. Clearly shows that X-Y is the elements of List, and that List is the
>    list being iterated over.
>    2. Only need to specify the accumulators once (!IO), instead of
>    specifying them both in the predicate head and as separate arguments.
>    3. Works naturally with the !S state variable notation, not requiring
>    the user to break the illusion of S being a single variable and specify !.S
>    and !:S.
>    4. Does not allow the "invention" of new accumulator names; instead, you
>    are merely specifying existing variables from the outer scope (typically
>    state variables) that may be updated in the body of the loop.
>    5. Does not require the user to have to decide whether to use foldl,
>    foldl2, foldl3, etc. It works for any number of accumulator variables.
>    6. It keeps the idea that the user must explicitly specify which
>    variables can be updated by the loop body. You can't just go updating any
>    state variable in the outer scope, for example.
> 

This seems good to me, I would like to extend it though so that:

    7.  It can handle any number of input lists.  (like map_corresponding).
    8.  It can handle things other than lists (I have some ideas about how to
        do this that I can describe later).
    9.  It can handle multiple outputs (not just accumoators) like list.map
        does.
    10. Guards can be added to support filtering.

    I spoke off-list with Mark Brown and some of these thoughts are his.

Consider Matt's example, except in this case we construct a list of strings:

:- pred print_key_values(assoc_list(string, string)::in, list(string)::out) is det.
print_key_values(List0, List) :-
    loop X-Y in List0 returning String in List (
        String = format("%s = %s\n", [s(X), s(Y)])
    ).

This shows something like map.

> This is intended to be a syntactic sugar around list.foldl:

To make this as useful as possible I would like to see the compiler generate
code for the right data type, number of input and output arguments, and
number of accumulators and any filters.

We can quibble/bikeshed about syntax in a new thread.

> 
> Now having said all of this, I agree with some of the sentiments expressed
> above that such a feature does not "feel" like it belongs in Mercury. I
> wouldn't be surprised if this was deemed "un-Mercurial" for being too
> imperative. But I'm just saying that I would have found it useful all over
> the place (which perhaps speaks more about the way I think when I write
> code -- imperatively). And it does kind of fit with the existing state
> variable notation, as well as some of the existing quantifying goals like
> 'some'.

SISAL was a pure language that had structures like this that were used for
looping and such more often than recursion.  This and your own work show
that the imperative/declarative dichotomy really is a false one (yes, I
deliberately paraphrased one of your titles).

Also, because you, and I'm sure others, would have found such a feature
useful in Mercury means that it is valuable.  If there are good ideas whose
effort to implement and maintain are worthwhile then there's no reason we
should reject them.

Thanks.


-- 
Paul Bone
http://www.bone.id.au