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

[Lee Naish]

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.  How many times have you coded an instance of
map?  What were the names and argument orders of all those predicates?
How did you think about the operation they performed.  Wasn't it all
rather ad hoc?  By using map, coding can be less ad hoc.  As map
generalises a very common coding pattern for lists, it too can be
generalised for other data types.  Such abstraction is a good thing and is
better than having programmers re-invent versions of map for different
data types in an ad hoc way (or worse still, repeatedly use the same old
coding patterns which are instances of map).

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

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

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

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

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

> but you've still lost some static checking.

The *only* time I have felt "static type checking is really needed here"
is when I have written complex higher order expessions (and had Prolog
respond "no").
 
> > and have types "inherit" these higher order predicates/functions.
> 
> Well, now I suppose you are talking about something a bit different,
> something similar to `deriving' in Haskell.

Yes, I suppose I was - I should have said "derive" (its independent of
type classes in theory, though in practice perhaps not??).

	lee