[m-dev.] Automatic generation of map, foldr, foldl

[Fergus Henderson]

On 08-Sep-1998, Lee Naish <Lee.Naish at cs.kuleuven.ac.be> wrote:
> 
> On Wed, 9 Sep 1998, Fergus Henderson wrote:
> 
> > The main drawbacks that I see are that it's complex and rather ad-hoc.
> 
> I've not counted the occurrences of "ad-hoc" in that post, but its "lots".
> The way people program is ad hoc.  The aim of this kind of work is to make
> programming *less* ad hoc.

I understand that, but if the proposal isn't general enough,
then adding support for it now may be premature.

> > Is the list of possible things which one can generate hard-coded?
> > Does this list include anything else other than foldl, foldr, map(1),
> > and map(2)?
> 
> My system currently supports foldl, foldr and map(N), where N is a natural
> number (map0 is the second most common higher order predicate, after map,
> which I have used in recent code).  There may well be other {higher order}
> predicates for which it is useful to generalise to other data types.

OK; will a user be able to add such predicates, or will adding such
predicates require modifying the Mercury compiler?

> >If not, how do we know that this set of four is enough?
> 
> Its not enough; under my proposal Mercury programmers could also define
> their own predicates!

This was not at all clear from your proposal.
Could you give an example?
E.g. suppose foldr wasn't built in, how would I define it?

> > Another drawback is that these declarations define entities without
> > mentioning the names of the defined entities.  This is a bit non-orthogonal
> 
> Ideally they should be called foldl, foldr and mapN, with the compiler
> determining which predicate should be called depending on the type
> information (just as it figures out which equality predicate to call
> currently I suspect).

That sounds good to me.

But there is a problem: what's the arity of these predicates?
Isn't it different for different shapes?  That makes it hard
to fit into the existing type class system.

Equality is a pretty fundamental thing in a logic programming language;
it's clear why it has to be built in.  foldl, foldr, and mapN are not
so fundamental, and it would be better if they could be defined using
Mercury code in the standard library rather than being language builtins.

If they can't be defined using Mercury code, then I suggest that we haven't
found the right primitives yet.

> > Currently it is also very much under-specified.
> > For example, what are the modes and determinism of the generated
> > procedures?  Are the generated procedures exported, or local to the module?
> 
> Their scope should be the same as the type.  The modes and determinism
> should ideally be as flexible as possible.  A starting point could be the
> current Mercury library predicates for lists, though I suspect these are a
> bit ad hoc.  Can map be used with a nondeterministic predicate as the
> higher order argument?  Can map2 (if it is in the library) run in all 8
> reasonable modes (not counting partially instantiated data structures)?
> Can foldr run backwards?  I have found all these to be useful.  One
> advantage of having these predicates more "built in" is the compiler might
> be able to do a better job of generating code for the desired modes and
> determinism rather than relying on a library which has an ad hoc subset
> of the useful cases.

That does raise some potential difficulties for efficient implementation.
Doing decent dead-code elimination on such procedures is tricky,
and if there are lots of modes of lots of shape-polymorphic procedures
for lots of types, this may result in a lot of dead code.
Even if you can eliminate the dead code at link time, it's difficult
to avoid the hit you take in compilation times.

Another point is that if the set of modes in a library is ad-hoc, that
is annoying; you may need to copy the source code of the library and
modify it in order to use it.  But if the set of modes hard-coded into
a compiler is ad-hoc, this is considerably worse; now there's no easy
work-around if the modes don't suit.

> > implement
> > higher-order shape-polymorphic procedures using the meta-programming
> > primitives from std_util.m, such as `deconstruct', `type_of', `index'
> > (actually from builtin.m), and `get_functor', and relying on partial
> > evaluation
> 
> or the tooth fairy
> 
> > to make things efficient.

Partial evaluation is a bit easier to implement than the tooth fairy ;-)

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.