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

[Lee Naish]

Thanks for forwarding this - the internet connection from here to Melbourne
is hopeless.  Sorry about the delay in replying.  You might want to forward
my message to the mercury group also.

   I'm really curious:  what do you mean by "write their own predicates?"
   This, it seems to me, is the key.
Just that, in the way people have been doing for a long time (ie, no use of
these facny primitives).

   > Re iterators:
   > This reminds me of Richard O'Keefe's work on sequences.

   Do you have a reference for this?
I think some might have ended up in The Craft of Prolog, I'm not sure.

   Using map assumes higher order code is efficient (call/N are still a
   bit slow in Mercury, IMHO), or that the compiler specializes HO calls
   (does the Mercury compiler do this yet?).

I was under the impression it did (it was a summer student project a couple
of years ago).  Its much easier than deforrestation.

	   \forall x \in l \as y \in m : p(x,y)

   That's not so exciting, but we don't have to limit ourselves to only
   lists.  We could use the same syntax for mapping over other data
   structures.

Thats basically (the generalised) map.

   The interesting bit, though, comes when we iterate over different
   types of data structures at the same time.  For example, we could
   define

	   x \in \inorder(tree)

   to mean that x is in tree and that the tree is to be traversed
   inorder.  Then

Once you start with different traversal orders it makes it hard to
generate things automatically.

	   \forall x \in \inorder(tree) as y \in l : x = y

Other than the map example I can't see the advantage over converting to
lists. Can you, for example do something like

  \forall x \in \inorder(tree) as y \in \preorder(tree2) : x = y

and if so, what modes can it run in?  Is it any better than:

  inorder(Tree, L), preorder(Tree2, L)


 	   \forall x \in l \as i \in 1..n : x = i
	   \forall x \in l \as i \in 1..n : true

These are instances of map (with the nice .. notation for lists of numbers).

   I think it's better to generalize member to existential
   quantification:

	   \exists x \in l : ...

How does this differ from the existential quantification we already have?

   I don't think we should assume that the functional people will hit on
   the right sorts of HO abstractions for logic programming.

Of course.  One of the points I made in my talk in Pisa was that the
primitives you want in LP are different from FP (for example, in map2 etc
you want all lists to be the same length so its reversible).  However, the
FP ones are a good starting point (at least the best starting point I could
think of).  I collected some stats on my own use of higher order primitives
recently - there is a summary on the slides I used in Pisa - see
http://www.cs.mu.oz.au/~lee/papers/hose.  map is the "winner", map0 comes
in second (applying a pred to each member of a list - not an FP primitive),
next is "split" (basically a combination of map and filter which relies on
predicates being both tests and possible generators), then map2 (in
various modes), then map_acc (which is a combination of map, an instance of
foldr, and accumulators, related to foldl), then foldl, foldr and others.

   This approach won't work, because you can't (easily) convert the
   resulting list into a data structure of the correct shape.  You can
   get away with a lot on lists that you can't on non-flat data
   structures.

Doesn't the same applies to different traversal orders?

	   (\forall x \in l \as y \in m : g(x, y)) \wedge
	   (\forall x \in m \as y \in n : f(x, y))

   is quite easily combined into

	   (\forall x \in l \as y \in m \as z \in n: g(x, y), f(y, z)

This is map again.  The challenge is to do it for other things.

   > whereas if the compiler
   > automatically generates certain predicates from the type definitions it
   > should also be able to determine what laws apply.

   The same argument applies to compiler-generated iterators.

I see no real difference between compiler generated iterators and what I'm
proposing.  They seem to be another higher order primitive which may prove
to be useful.  I have not said that what the functional people have done or
what I have done is the end of the story.  In fact I might well implement
a generalised member in the near future (I have redesigned the data
structure for constraints in my mode checker and am in the process of
changing over - the new type has about a dozen cases and I would like to
automatically generate as much of the code as possible).

There are some other shapely operation which work on multiple data types,
transpose being the canonical(?) example.  From a list of trees which are
the same shape you can get a tree of lists etc.  I've done a bit of work on
how to code this reasonably efficiently (though I think the modes are a bit
too subtle for Mercury).

	      lee