[p-dev] Resources and higher-order calls

[Paul Bone]

On Tue, Aug 29, 2017 at 06:42:09PM +1000, Peter Schachte wrote:
> Hi Paul and Plasmids (is that the appropriate group noun?),
> 
> I have given this a little thought, and tentatively came to the opposite
> conclusion. I've never liked that Haskell has two whole sets of higher
> order functions:  in addition to map, filter, foldl, foldr, zipWith,
> etc, there's also mapM, filterM, foldM, zipWithM, etc. (and for good
> measure mapM_, foldM_, zipWithM_, but not filterM_ or foldrM or
> foldlM).  It's starting to feel like a language without polymorphism).

Right, and Mercury has a similar problem, with map, map2, map3, map4
map2_corresponding2_foldl3 etc.

> So what if we make the higher order operations polymorphic in the
> resourcefulness of their function arguments, as you're suggesting?  Then
> we could allow it to work on a function with or without resources, so a
> single higher order operation could handle both the resourceful and
> resourceless cases.  Good.

Yep.

> But that means every higher order operation we define, if we ever want
> to be able to use it with a resourceful function, needs to be written in
> a different style, laboriously fixing the order of operations.  Suddenly
> higher order code becomes much more onerous to write.  Not good.

I wouldn't say "not good" (at least in the Australian sense ;-))  I would
say "not great", urgh, "it's okay, but could be better".  Basically I don't
think it's bad that people should write more verbose code, provided that the
code is clear and easy to read, it's reading that's important.  However I
agree that this doesn't match many programmer's attitudes, and people will
avoid higher order code, or avoid Plasma, if it feels like more work up
front (writing).  With so many design decisions we have to choose between
the right thing, and the popular thing, this may be one of those decisions.

> The thing is, Haskell only has foldM and not foldlM and foldrM because
> foldrM doesn't make sense (so foldM is a left fold), because you want to
> accumulate the monad on the way down the recursion, not on the way
> back.  In most cases, I think only one order of operations for a
> resourceful higher order operation is going to make sense.  So why force
> programmers to write somewhat painful, ugly code for every higher order
> operation?

Why wouldn't foldrM make sense?  Except that it'd be the same as:

foldrM f a l = foldM f a (reverse l)

:D

I keep telling people that foldl/foldr should be based upon whether your
operation is left or right associative (or non-associative) not on laziness
or tail recursion or other incidental complexity, but that's also because I
dislike lazy-by-default.

> And this is where I haven't finished thinking it through.  The open
> question is:  is there a clear set of rules we can specify that indicate
> how the nice declarative resource-oblivious higher order code will be
> transformed to resource-aware code?

Maybe, first we need that code involving resources has a clear order of
operations, for example expressions are executed out-to-in, left-to-right
(like normal strict languages).  And probably have to say something about
short-circuits, so what happens for:

    r = a || b!()

Does b have an affect if a is true (I hope not).

These orderings aren't visible without effects (or non-termination or
exceptions) so this ordering is irrelevant in code without effects.

Next we can decide if higher order code still needs a ! annotation.

I'm unsure of either of these ideas, sure they make things more concise but
I'm not all that happy about these effects being hidden.

> And is it true that, if the higher
> order function is given a resourceless function argument, then the code
> can be cleanly and simply specialised back into something like the
> original resource-oblivious code, or at least something equally
> efficient and equally optimisable?

That is trivial.  I had intended with the original proposal to compile two
versions of map from one piece of source code, one with resource-friendly
semantics, and one with optimisation-friendly semantics.  In reality they
may be many more versions of this code anyway, due to inlining and
eventually parallelisation specialisation.

I thought of another idea.  A "don't care" resource.  So you declare up
front that the higher order value uses some resource, but we don't care
about its ordering, so its annotations within the function body aren't
necessary (or don't have the "only once per statement" rule applied).  But
anyone looking at the declaration gets a clear idea about what this function
promises (or doesn't promise).

    func map(f : a -> b dont_care r, l : List(a)) -> List(b) dont_care r {
        return switch (l) {
            case [] -> []
            case [x | xs] -> [f(x) | map(f, xs)]
        }
    }

The problem with this is if someone does care about the order their resource
is used, for example if they want to print the entries of their list in
order, then they cannot safely use this version of map.  And their code may
change its behaviour in the future, even if it is applied left-to-right
today.

I think some of these questions would be easier to answer if we actually had
some experience writing Plasma and Wybe programs.  Particularly since Plasma
(I don't remember for Wybe) includes loops.  So people are more-likely to
use a loop rather than map to print out a list of items.

> I'd be happy to get together to brainstorm this some time if you like. 
> It's an interesting question, and could possibly make an interesting
> paper (maybe for PADL?).

Yep, See you tomorrow :D


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