[p-dev] Resources and higher-order calls

[Peter Schachte]

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

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.

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.

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?

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

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


On 27/8/17 11:36 pm, Paul Bone wrote:
> Hi Plasma Team & Peter.  I'm including Peter since the resources idea came
> from him, and I wonder if he's thought about their use in higher-order code.
>
> I've been working on the resource system.  You now need a ! on the end of a
> call that /uses/ or /observes/ a resource.  You also need to provide the
> resource and declare if you're going to use or just observe it.
>
>     func main(args : List(String)) -> Int uses IO {
>         print!("Hello world\n")
>         return 0
>     }
>
> Pretty clearly, when a call doesn't use or observe a resource it doesn't
> need a bang.
>
>     print!("fib(32) = " ++ int_to_string(fib(23)) ++ "\n")
>
> int_to_string and fib are pure functions.  ++ is also a pure function, for
> now it's a special case but hopefully it'll be less special later.
>
> If we have a higher order function what should happen?  This example also
> has switch used as an expression, which isn't implemented but maybe the
> syntax could be like this.
>
>     func map(f : a -> b, l : List(a)) -> List(b) {
>         return switch (l)
>           case []       -> []
>           case [x | xs] -> [f(x) | map(f, xs)]
>     }
>
> I havn't declared that f uses a resource.  Here is the first decision to
> make, should we make any polymorphic resources explicit?  That might look
> like this:
>
>     func map(f : a -> b using r, l : List(a)) -> List(b) using r {
>         return switch (l)
>           case []       -> []
>           case [x | xs] -> [f!(x) | map!(f, xs)]
>     }
>
> Now the resource variable 'r' is introduced and stands for any resource the
> caller might care to substitute (also no resources).  I've also added bangs
> to the calls to f and map, since they clearly might use a resource.
>
> For anyone wondering about optimisation / parallelism.  Whether polymorphic
> resources are explicit or not, any resource polymorphic code will generate
> at least two versions of the code, one in a sequential order WRT used/used
> and used/observed resources (which reminds me, this code would fail resource
> checking!) and one non-sequential (optimisations that re-order these calls
> are okay).
>
> So this code is actually invalid (this e-mail was going to be somewhat of an
> open question, but it seems to be a debugging teddybear instead).  The 'r'
> resource is used twice within the same statement, which is not allowed
> because I do not want to define an evaluation order within expressions (only
> statements).
>
> So instead we must have:
>
>     func map(f : a -> b using r, l : List(a)) -> List(b) using r {
>         switch (l) {
>           case []       -> {
>             return []
>           }
>           case [x0 | xs0] -> {
>             x = f!(x0)
>             xs = map!(f, xs0)
>             return [x | xs]
>           }
>         }
>     }
>
> Now the two calls with !s (for the same resource) are in different
> statements.
>
> I was going to ask if resource-polymorphic code needed to be explicit about
> the !, and I was going to assume it didn't have to be explicit WRT the type
> signature, since I can generate a safe lower-bound automatically.  However
> to write resource-safe code, you need to see the !, and for that to make
> sense, you need the type signature.  So now I'm leaning to needing these
> things, and code that doesn't have it, like the first version of map in this
> e-mail is _not_ resource-polymorphic.
>
> Here's another example, first the non-polymorphic code.
>
>     # map fused with foldl.
>     func map_foldl(m : a -> b, f : (c, b) -> c, l : List(a), c : c) -> c {
>         return switch (l)
>           case []       -> c
>           case [x | xs] -> map_foldl(m, f, xs, f(c, m(x)))
>     }
>
> Let's add resource polymorphism:
>
>     # map fused with foldl.
>     func map_foldl(m : a -> b uses rm, f : (c, b) -> c uses rf,
>             l : List(a), c0 : c) -> c uses rm, rf
>     {
>         switch (l) {
>           case []       -> { return c0 }
>           case [x0 | xs0] -> {
>             x = m!(x0)
>             c = f!(c0, x)
>             return map_foldl!(m, f, xs, c)
>           }
>         }
>     }
>
> There are two resource variables here, rm and rf.  and map_foldl declares
> that it uses both of them.  Depending on what actual resources are
> substituted here (if any) then the rules for reordering the calls to m and f
> change.  It is not known (from map_foldl alone) that rf and rm are
> unrelated.  It must generate code as if they are the same.  If a
> monomorphism transformation is used (probably) then re-ordering can be
> allowed in some cases.  There are 3^R possible resource monomorphic
> functions (R is the number of resources) but usually fewer actual code
> generation choices.
>
> Anyway.  It seems that we have to make this explicit in the language itself
> in order to make the evaluation order clear.  (We could also choose to not
> specify the evaluation order of higher order calls, but that could lead to
> surprises).  I expect that higher order code will be very common in Haskell,
> so I'm annoyed that this makes it less concise.  But maybe most functional
> code won't ever be used with resources and people will be happy to write it
> without polymorphic resource arguments.  However if you're implementing a
> data structure in some library, it's going to be important to include this.
>
> The usual thoughts/opinions are most welcome.
>
>

-- 
Peter Schachte
Assistant Director, Infrastructure - IT
Melbourne School of Engineering
Senior Lecturer, School of Computing and Information Systems
University of Melbourne
http://bit.ly/peterschachte
Phone: +61 3 8344 1338