[p-dev] Resources and higher-order calls

[Paul Bone]

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.


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