On Fri, Feb 20, 2015 at 4:26 PM, Keean Schupke <[email protected]> wrote:
>> > 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.
And then what happens when you call the HOF with a function that's a
subtype of the one it expects?
> - 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).
And if it's not within the module, you wait till link time? So in
other words we specialize the HOF to avoid using the subsumption rule?
You have to admit, that's a pretty weird way to use subtyping. Anyway,
in that case, it might work, and it might in fact be doing the same
thing as Shap's version. Since it's so weird, it's not easy for me to
convince myself that this scheme fully works.
> 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.
Are you saying I did that? You'd better not be. I was only talking
about subsumptions using _your_ subtyping relation. (Once I reversed
it to make it work.)
> If we don't care about allocations--
We do.
> 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.
Not quite as efficiently, but at least it doesn't allocate. If you
thought uncurried functions were no faster to fully apply, why did you
propose specializing definitions to be uncurried in the previous
email?
Note that allowing curried and "less-curried" functions to be used by
the same less-curried application is what Shap's proposal does too.
>> > 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.
Constraining what function? (fn 'a 'a -> 'a)? It makes no sense to
constrain that, since it's already a concrete function type.
> 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?
I think there's been a misunderstanding. There's no such thing as an
abstract arity. Shap's proposal uses arity-abstract types, which have
had the (concrete) arity abstracted out of them.
>> > 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?
In Shap's proposal this is a unification error. (f 1) constrains the
type of f to have an arity of at most 1. I currently don't understand
the details of the notation, so I don't know how you'd read that
constraint from a type, but here we can infer it. But f has arity 2.
> 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.
That's the implementation of what Shap calls accumulator lambdas. You
are right that we must not insert code to use them, but since your
example is rejected, we don't.
> The other way around, applying more arguments to a curried function is
> trivial to see requires no additional allocations.
Right, and Shap's proposal is designed to allow that.
_______________________________________________
bitc-dev mailing list
[email protected]
http://www.coyotos.org/mailman/listinfo/bitc-dev
