[p-dev] Resources and higher-order calls

[Paul Bone]

On Thu, Sep 07, 2017 at 03:34:22PM +1000, Peter Schachte wrote:
> On 1/9/17 11:53 pm, Paul Bone wrote:
> > Implicit resources
> > ------------------
> >
> > Peter feels that developers that don't imagine their code being used with
> > resources simply wont write the resource declarations or ! on the calls.  I
> > agree.  Peter continues by saying that therefore the resource unaware code
> > should work with resources anyway, but the ordering of how the resource is
> > used is either undefined or defined in a possibly not-obvious way.
> 
> Not undefined, but implicitly defined in some cases.  See below.
> 
> > So
> > developers wouldn't have to use ! or say "uses r" and yet their code would
> > handle resources implicitly.  I'm leaning towards "no".
> >
> > Evaluation order
> > ----------------
> >
> > Another idea is that just as statements have the declarative semantics of
> > being executed one at a time, top to bottom, but that this is not
> > necessarily their operational semantics, that expressions could have a
> > similar declarative semantics.  And therefore you could have multiple uses
> > of a single resource in a single statement
> 
> In some cases, ordering is implicitly but unambiguously defined.  For
> example, if f and g both use and modify a common resource, and f is
> eager, then f(g(x)) must unambiguously execute g before f, so this could
> be allowed without confusing anyone.  This would also apply in cases
> like if-then-else, where the condition is unambiguously executed before
> the then or else branch, and similarly for switches, and lets and wheres
> would execute the definitions before the body, and would execute the
> definitions in the order written.

My concern with this is that it's only unambiguous after you think about it
(not that thinking is bad or I want to encourage laziness).  However it's
nice to understand the effects of something at a glance, rather than knowing
which rule to apply.

    f!(x) + g!(x)

If I tell you that effects are executed left-to-right in expressions then
this is okay.  Until we see this:

    f!(g!(x))

Now someone could get a surprise if they're not thinking critically and
apply the left-to-right rule.  What I'd prefer (if possible) is fewer rules
for people to apply in their minds when they read some code.

> Another case would be if resources could be declared to be commutative,
> by which I mean that all primitive operations on those resources are
> commutative, and mutually commutative.  For example, a counter resource
> with only an operation to increment it, and to get the final value of
> the count after a computation, could be declared commutative.  Then
> (again supposing f and g use and modify the counter resource) although
> f(x) + g(x) could be implemented in two different ways and the internal
> behaviour would be different, the result is the same either way, so we
> shouldn't have to be explicit about the order of the operations.

I was already thinking of taking advantage of laws like commutativity for
parallel execution of loops (probably based on meetings you and I had years
ago) but I hadn't yet applied it to resources.  I don't think this feature
is necessary, but it is definitely nice to have!

> My final case is more controversial.  I would argue that the compiler
> would like to implement as many recursions as possible as tail
> recursions, and therefore it makes sense to say that a singly-recursive
> definition should make the recursive call last if that doesn't conflict
> with the first rule.  Therefore:
> 
> >     func map(f : a -> b uses r, l : List(a)) -> List(b) uses r {
> >         return switch (l) {
> >             case [] -> []
> >             case [x | xs] -> [f!(x) | map!(f, xs)]
> >         }
> >     }
> 
> Is valid.

So my f!(x) + g!(x) example has an undefined order, but this doesn't because
one of the two calls is a self-recursive call?  Does that apply to mutual
recursions and is the programmer always aware of which calls are mutual
recursions?

I think I'd prefer a "left-to-right" rule for evaluating arguments of a
function/operator.  Here that operator is cons.  That works until one day
you make a cons-list with the head and tail arguments reversed and don't get
tail recursion in resource-friendly code.  That could be a surprise.

> I hope that this is enough to make most cases not require any special
> annotations.
> 
> I would also argue that rather than making all functions types look like
> a -> b uses r (I think we agreed that HO code should by default allow
> resourceful function arguments, so uses r is implicit),

Maybe we did, but I gave it some more thought and I'd like to add that there
are definitely situations when you want to override that.  Like you know
you're going to do something with a specific type of resource.

write_to_file(filename : String
              writer: (f : File) -> Result uses File(f))
    -> Result uses IO

(I also introduced a potential syntax for linking resources to values.)  In
this example the higher order argument has a very specific resource
declaration, it does not make sense for it to be polymorphic, but we can
still allow higher order arguments without one to be polymorphic.

Also there's the question of what happens to the polymorphic resource in the
declaration of the caller.  Firstly we can't have:

    func map(f : a -> b, l : List(a)) -> List(b) uses r

Where did r come from, what is it linked to?  It isn't useful to have it on
map's declaration without also having it on the first argument's type.  So:

    func map(f : a -> b, l : List(a)) -> List(b);

That seems okay,  Until we have.

    func foo(f : a -> b, g : a -> b, a : a) -> b {
        return f(a)
    }

The resource usage of f is important, because it is foo's resource usage.
But g isn't, because it's not called by foo.  But this is not visible from
the declaration, which is something I don't like.

Now if you have the declaration only:

    bar(f : a -> b, a : a) -> b

We might not actually know whether bar uses or observes the same resource as
it's argument.  Both are reasonable assumptions.

Also does the implicit resource also apply to function types within other
types (such as regular data types).

> and therefore
> requiring bangs all over the place in case the HO argument is
> resourceful, it's better to be silent about the resources, and have the
> compiler warn if the rules above aren't enough to make the resource
> threading unambiguous.  In that case, the HO function should enforce
> that the HO argument must be resourceless in any call.  And perhaps
> there should be a way to declare a HO type to be resourceless, to shut
> up the warning, but still prevent supplying a resourceful argument to
> the HO operation.  The intention of this is not to allow resources to
> make HO code onerous to write or use, but also to ensure an unambiguous
> execution order of resource operations when that makes a difference to
> denotation.

A resourceless call type should use a new keyword.  'pure'.

I agree that HO code should be straightfoward to write.  And I will think
more about allowing it to be skipped in the obvious cases (like our map
example) but not in the trickier cases.  But I'm not convinced that it can
be done in a satisfactory way.  I'll be thinking about it some more.

> > Placement of !
> > --------------
> >
> > There are two other ideas I discussed Peter and others recently.
> >
> > The ! referring to an affect could be written before the statement as a
> > whole, out-dented from the current block:
> >
> >     x = calc_something()
> >   ! do_something(x)
> >     y = calc_something_else()
> >   ! ok = do_something_with_result(x, y)
> >
> > But in our map example this is far away from the actual effects.
> >
> >     func map(f : a -> b uses r, l : List(a)) -> List(b) uses r {
> >       ! return switch (l) {
> >             case [] -> []
> >             case [x | xs] -> [f(x) | map(f, xs)]
> >         }
> >     }
> >
> > There's only one per statement and it still means "there's something to be
> > aware of here".
> 
> A little more than that:  it means a resource can be modified in there.

Ah sorry, I've had an idea in the back of my head that ! means 'beware' and
might be used for other things, such as array update.  But as we discussed
the other week that can just be another type of resource.

> I admit in that case the ! is uncomfortably far removed from the actual
> modifications.  The problem with putting it where the modification
> happens is that it's pretty invisible.  Choosing between being able to
> see it, but having to look closely to see where it applies, and having
> to look closely at every function call to see where changes can happen,
> I'd prefer the former.

I'd prefer the latter, but I'm assuming my editor is going to paint it red
with syntax highlighting.  There are clear benefits of both and they're so
hard to measure (like all of this discussion!).

> Another option is not to allow users to nest resourceful calls inside
> other calls.

What.  like this?

    y = f(g!(x))

How about within operators?

    return [f!(x) | map!(f, xs)]

I think you'd have to ban them all (and include if expressions etc) to make
the rules simple to use without really thinking of every little rule.  But
then you're back to writing:

    x = f!(x0)
    xs = map!(f, xs0)
    return [x | xs]


> > Placement of uses/observes
> > --------------------------
> >
> > The other idea is that the uses/observes clause should be moved closer to
> > the 'arrow'.
> >
> >     func map(f: (a) uses r -> b, l : List(a)) uses r -> List(a)
> >
> > It doesn't 'look' right yet, but I think this helps.  This also helps when a
> > function returns a function.
> 
> I was arguing that resources should not be part of the type system, so a
> function a->b is just a->b, no 'uses' necessary.  Instead resources are
> just part of function/procedure declarations.

This was a discussion I had with another colleague.  He kept thinking that
the resource was part of the return type.  This aims to show that it's part
of the function call (but not necessarily the type).  It could be part of
the type system, or a desperate system, I think you could get the same
semantics either way.  But we both prefer that it's not to keep separate
concerns separate, and I think to apply different coercion rules.

> > Higher order specialisation
> > ---------------------------
> >
> > Oh Peter, here's a reason why you won't be able to optimize away all the
> > higher order calls: people can put them into structures then map over them
> > applying them to some single data term:
> >
> >     x = ...
> >     ys = map(\f -> f(x), functions)
> 
> Well, maybe.  As I mentioned, Wybe doesn't have any HO capability at all
> yet, so that might just not be permitted.  I might not even allow
> functions to be stored in structures at all, or to be returned as
> function results.  I'm just not sure how important that is.  In any
> case, I could implement all ordinary downward-only HO procedures by
> expansion, at least if code bloat isn't too bad, and handle other cases
> in the orthodox way.

Wow!  You technically wouldn't have a functional language then, and can't
sit with the functional programming people in the lunch room :P  These are
less important than taking a function as an argument, but maybe you're
right, maybe they're not critically important.

I doubt it'd pay of any more than higher-order specialisation optimisation
already does.  But I'm just guessing.

Cheers.


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