> > Now we would like to be able to call functions with some flexibility,
> but we
> > have to consider that we do not want silent allocations. We cannot allow
> > curried application of a non-curried function as that would require
> > allocations, but it seems okay to allow non-curried use of a curried
> > function. To achieve this all we need is a subtyping relationship
> defined on
> > function types such that more curried is a subtype of less curried.
>
> Yes. Very interesting. Since you're about to make a small error, let's
> just clarify that
> fn 'a -> fn 'a -> 'a
> is more curried than
> fn 'a 'a -> 'a
>
more curried is a subtype because we can always apply a more curried
function where we expect a less curried one, following the Leskov
substitution principle, so I don't see any errors so far.
>
> > for example:
> >
> > fn 'a 'a 'a -> 'a :< fn 'a 'a -> fn'a -> 'a
> > fn 'a 'a 'a -> 'a :< fn 'a -> fn 'a 'a -> 'a
> > fn 'a 'a -> fn'a -> 'a :< fn 'a -> fn 'a -> fn 'a -> a
> > fn 'a -> fn 'a 'a -> 'a :< fn 'a -> fn 'a -> fn 'a -> a
>
So 'a'a'a :> 'a -> 'a -> 'a
Yes, I got the order backwards.
> > We are find
> > to just let applications type check, and simply generate the correct
> number
> > of applications when emitting the code for the function as we always have
> > the concrete arities from the definition/import and the application.
>
> No. Here's where it all goes wrong. You _don't_ necessarily have the
> concrete arity when you compile an application. The example we keep
> giving you is a higher-order function calling its parameter.
>
I think you are missing the point:
- If you are exporting or importing the higher order function you _must_
give it a concrete explicit type (not inferred) so you _do_ know the
concrete arity.
- If the application is within the same module you can analyse the
call-site of the higher-order function to see what type it is passed (and
hence the concrete application type). You can trace this my whole-module
compilation (you don't need to look outside the module because all
imported/exported types must be explicit and have a concrete arity).
So I don't think it goes wrong at all.
The cool thing is how close to right it would be to just compile the
> application at whatever type it needs. This is ostensibly all wrong,
> given the subtyping, but if we treat the subtyping as coercion
> subtyping, it works. The only problem is that these coercions
> introduce at least one closure allocation unless they all get inlined
> right where the application finally occurs. Optimizing together all
> the coercions and the application gets you exactly the specialized
> application from Shap's scheme, I figure. This is an argument for
> arity-concrete/abstract being the right way to do this. We want one
> big jump from the original concrete type to the abstract type we
> apply. We cannot afford to spread this out over multiple subsumptions
> and a separate application.
>
I don't see how you can pass call a less curried concrete type with less
arguments, you will need to allocate a thunk which violates the no
allocation principle, and its not going to be good for performance in a
systems programming language in any case.
If we don't care about allocations then I think you can do it both ways and
call curried functions with more arguments, and uncurried functions with
less arguments.
However defining curried functions is inefficient - people will avoid
curried definitions to reduce function calls (and stack allocations). My
proposal of allowing less-curried application of curried functions by
specialisation removes the argument for defining less-curried functions, as
the curried versions can be applied just as efficiently by providing all
the arguments.
> > As an optimisation, if we have access to the function definition, we can
> > generate 'uncurried' specialisations of function definitions to make
> calls
> > more efficient.
>
> This sounds like another way of looking at the dual arity
> specialization where arity is chosen by the application.
>
Might be.
> > Abstract Arities
> > --------------------
> >
> > So there are no abstract-arities in this description, and if I think of
> an
> > abstract arity like a type class:
> >
> > Arity 2 => fn 'a 'a -> 'a -- It seems an abstract arity is simply the
> > argument count of the function for its least-curried application?
>
> I have no idea what that type is supposed to mean. I've never seen
> that notation before.
>
Well "Arity" is a type class like think constraining the function to an
abstract arity. As an abstract arity ignores currying, it is simply a count
of the arguments, Ie a concrete arity of (1, 1) and (2) both have an
abstract arity of 2. What other sense would you use abstract-arity?
> > It allows for more-curried applications of less-curried functions which
> is
> > not allowed as it introduces allocations.
>
> You mean Shap's proposal could introduce an allocation? I don't think
> you're right. Can you give an example?
>
If I have a function:
f x y = 1 + 2
and I have
g = f 1
what does "g" return? It has to return the partially applied "f", but "f"
has no curried definition so we cannot partially apply it. The only
solution is to allocate a thunk, basically a structure in which we package
the function and the argument like this:
struct thunk {
x = 1
f -- this is a reference to the uncurried definition of f.
}
Then when you get the second argument you can pull the function and the
first argument from the thunk and apply both as required by the concrete
uncurried type.
The other way around, applying more arguments to a curried function is
trivial to see requires no additional allocations.
Keean.
_______________________________________________
bitc-dev mailing list
[email protected]
http://www.coyotos.org/mailman/listinfo/bitc-dev
