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

[Fergus Henderson]

On 06-Sep-1998, Lee Naish <Lee.Naish at cs.kuleuven.ac.be> wrote:
> 
> I have been doing some (Prolog) hacking based on
> http://www.cs.mu.oz.au/~lee/papers/hose/ which
> discusses automatically generating various higher
> order predicates from the data type.  From a type 
> definition such as
> 
> :- type tree(T) ---> leaf(T); t(tree(T),tree(T)).
> 
> you can generate some Horn clauses:
> 
> tree(A, leaf(B)) :-
>         call(A, B).
> tree(A, t(B, C)) :-
>         tree(A, B),
>         tree(A, C).
> 
> tree_any(leaf(A)).
> tree_any(t(A, B)) :-
>         tree_any(A),
>         tree_any(B).
> 
> And with another declaration like
> 
> :- skeleton tree_any/1 generates foldl, foldr, map(1), map(2).
> 
> generate
> 
[...]
> 
> I figured it would be nice to incorporate such a mechanism 
> into Mercury.

Well, perhaps.  Let me play devil's advocate for a moment, though,
and describe some of the potential drawbacks.

The main drawbacks that I see are that it's complex and rather ad-hoc.
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)?  If not, how do we know that this set of four is enough?

Another drawback is that these declarations define entities without
mentioning the names of the defined entities.  This is a bit non-orthogonal
and makes it harder to use tools like grep and mtags.

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?

An alternative to all this would be to take the high road: 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 to make things efficient.

For example, something like this rough sketch...

	general_foldr(Fs, X, A0, A) :-
		index(X, FunctorNum),
		get_functor(type_of(X), FunctorNum, _Name, _Arity, ArgTypes),
		list__index1_det(Fs, FunctorNum, F),
		deconstruct(X, _FName, _FArity, Args),
		pick_recursive_args(ArgTypes, Args, RecArgs, NonRecArgs),
		list__foldr(RecArgs, general_foldr(Fs), A0, A1),
		F(NonRecArgs, A1, A).

This kind of approach would make things a lot less ad-hoc.

A drawback is that since the type system doesn't really support
shape-polymorphism functions like the one above end up using `univ'
(dynamic typing).  Of course partial evaluation can at least in
theory optimize it all away, but you've still lost some static checking.

> It should be possible to incorporate this kind
> of thing into the type class mechanism I would have thought,
> 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.  This is considerably
less complex for the user, but still ad hoc.

I think you still run into similar problems here because the type system
doesn't really support shape-polymorphism.

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