New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Template Declarations #540

Open
DavePearce opened this Issue Sep 18, 2015 · 22 comments

Comments

Projects
None yet
2 participants
@DavePearce
Member

DavePearce commented Sep 18, 2015

This is in essence a WSR --- Whiley Specification Request.

Template Declarations

Based on the current directions of Whiley (i.e. focusing on being a systems language), I believe that template functions (rather than generic functions) make sense. This follows C++ and also now Rust generics (which are statically instantiated). Like Rust, some concept of trait is really needed to ensure type safety (i.e. comparable to a type bound in Java).

Some example syntax would be:

template<T> 
function reverse(T[] items) -> (T[] result)
ensures |items| == |result|:
    ...

The other option would be just to embed the generic declaration into the function declaration. Perhaps, like this:

template function reverse<T>(T[] items) -> (T[] result)
ensures |items| == |result|:
    ...

In principle, you could drop the template keyword altogether, but I'm not sure whether this is a good idea or not.

Every template must be explicitly instantiated. The syntax for this could be something like this:

instantiate whiley.lang.Array.reverse(int[])

This instance declaration essentially gives an appropriate name for the function. It could correspond to an actual instantiation (i.e. inlining) of the code, but doesn't necessarily have to.

@DavePearce

This comment has been minimized.

Show comment
Hide comment
@DavePearce

DavePearce May 3, 2016

Member

Given the recent extension to support lifetimes (see #642), the question is how this interacts with template declarations. The basic issue is that lifetimes also use the < > notation for parameters. This would look something like this:

template<T>
function swap<l>(&l:T r1, &l:T r2):
    int tmp = *r1
    *r1 = *r2
    *r2 = tmp

So, we've got a "doubling up" of angle brackets...

Member

DavePearce commented May 3, 2016

Given the recent extension to support lifetimes (see #642), the question is how this interacts with template declarations. The basic issue is that lifetimes also use the < > notation for parameters. This would look something like this:

template<T>
function swap<l>(&l:T r1, &l:T r2):
    int tmp = *r1
    *r1 = *r2
    *r2 = tmp

So, we've got a "doubling up" of angle brackets...

@bambinella

This comment has been minimized.

Show comment
Hide comment
@bambinella

bambinella May 7, 2017

When you add templating then I think it would be a good idea to consider the overall homogeneity of the language.

In C++ I personally like using "std::array<T,N>" over "T arr[N]" because it fits better in with the rest of the ADTs for the language.

So if you add templates you might simplify the syntax for arrays to a templated syntax.
Same with references.

It makes generic programming much easier and readable.

Doesn't prevent syntactical sugar using the more conventional notation, but if you add matching on templates it makes a difference that you have a "canonical form" that is homogeneous across types.

In C++ you now have templates as parameters and then this becomes rather important I think. E.g. CONTAINER<T,N> could be array<T,N> or queue<T,N>

bambinella commented May 7, 2017

When you add templating then I think it would be a good idea to consider the overall homogeneity of the language.

In C++ I personally like using "std::array<T,N>" over "T arr[N]" because it fits better in with the rest of the ADTs for the language.

So if you add templates you might simplify the syntax for arrays to a templated syntax.
Same with references.

It makes generic programming much easier and readable.

Doesn't prevent syntactical sugar using the more conventional notation, but if you add matching on templates it makes a difference that you have a "canonical form" that is homogeneous across types.

In C++ you now have templates as parameters and then this becomes rather important I think. E.g. CONTAINER<T,N> could be array<T,N> or queue<T,N>

@DavePearce

This comment has been minimized.

Show comment
Hide comment
@DavePearce

DavePearce May 7, 2017

Member

Hey,

So if you add templates you might simplify the syntax for arrays to a templated syntax.

Well, I understand what you're saying and I think it's interesting. But, it is a significant departure from what a lot of other languages to. I think it pushes the language too far from current syntax, and that's detrimental to uptake by people from other languages.

That said, ensuring that the template system would allow us to define a template array<T,N> that compiled down to T[N] seems reasonable for people that would prefer to do that.

Member

DavePearce commented May 7, 2017

Hey,

So if you add templates you might simplify the syntax for arrays to a templated syntax.

Well, I understand what you're saying and I think it's interesting. But, it is a significant departure from what a lot of other languages to. I think it pushes the language too far from current syntax, and that's detrimental to uptake by people from other languages.

That said, ensuring that the template system would allow us to define a template array<T,N> that compiled down to T[N] seems reasonable for people that would prefer to do that.

@bambinella

This comment has been minimized.

Show comment
Hide comment
@bambinella

bambinella May 7, 2017

That said, ensuring that the template system would allow us to define a template array<T,N> that compiled down to T[N] seems reasonable for people that would prefer to do that.

What I mean't is that T[N] could be available as syntactical sugar and compiled down to array<T,N>

That way "something<array<T,N>>" and "something<T[N]>" would be equivalent.

Going the other way means you end up in the same special cased mess that C++ and their descendants have as people start to do more advanced generic programming.

That said, ensuring that the template system would allow us to define a template array<T,N> that compiled down to T[N] seems reasonable for people that would prefer to do that.

What I mean't is that T[N] could be available as syntactical sugar and compiled down to array<T,N>

That way "something<array<T,N>>" and "something<T[N]>" would be equivalent.

Going the other way means you end up in the same special cased mess that C++ and their descendants have as people start to do more advanced generic programming.

@DavePearce

This comment has been minimized.

Show comment
Hide comment
@DavePearce

DavePearce May 7, 2017

Member

What I mean't is that T[N] could be available as syntactical sugar and compiled down to array<T,N>

Right I see. Yeah, that can work. The only slight issue is that it means the compiler depends on the standard library somehow. Hmmm, or maybe that certain template names are "special" ?

Member

DavePearce commented May 7, 2017

What I mean't is that T[N] could be available as syntactical sugar and compiled down to array<T,N>

Right I see. Yeah, that can work. The only slight issue is that it means the compiler depends on the standard library somehow. Hmmm, or maybe that certain template names are "special" ?

@bambinella

This comment has been minimized.

Show comment
Hide comment
@bambinella

bambinella May 8, 2017

I guess templated types would be nominal and not structural, or? So then it would be the main mechanism to get nominal types? Or am I mistaken? Not sure how you plan on dealing with nominal vs structural typing.

I guess templated types would be nominal and not structural, or? So then it would be the main mechanism to get nominal types? Or am I mistaken? Not sure how you plan on dealing with nominal vs structural typing.

@bambinella

This comment has been minimized.

Show comment
Hide comment
@bambinella

bambinella May 8, 2017

I don't understand why you need explicit instancing? Why can't it be implict?
Do you need instancing to allow querying?

I am also not sure why you need

function f(T x, T y)....

Isn't the follow sufficient (+ some missing syntax) with requires overloading:

function f(x,y) requires same_type(x,y)

I don't understand why you need explicit instancing? Why can't it be implict?
Do you need instancing to allow querying?

I am also not sure why you need

function f(T x, T y)....

Isn't the follow sufficient (+ some missing syntax) with requires overloading:

function f(x,y) requires same_type(x,y)

@bambinella

This comment has been minimized.

Show comment
Hide comment
@bambinella

bambinella May 8, 2017

I would also like to see logic-programming like "head-clauses"

So I could have

stuff<substuff,N> = ...
stuff<substuff,3> = ...

Then maybe if one could define some constraints on stuff and substuff that give them "methods".

Querying is also interesting. Being able to ask for all the T's that could be instantiated in this program... but hard to get right.

bambinella commented May 8, 2017

I would also like to see logic-programming like "head-clauses"

So I could have

stuff<substuff,N> = ...
stuff<substuff,3> = ...

Then maybe if one could define some constraints on stuff and substuff that give them "methods".

Querying is also interesting. Being able to ask for all the T's that could be instantiated in this program... but hard to get right.

@DavePearce

This comment has been minimized.

Show comment
Hide comment
@DavePearce

DavePearce May 8, 2017

Member

Hey,

I don't understand why you need explicit instancing?

Hmmm, not sure exactly what you mean by this.

Isn't the follow sufficient (+ some missing syntax) with requires overloading:

No, since you have to give types on parameters. This is part of the complete separation between typing and verification within the compiler. That's a choice I've made, though it's certainly not the only one.

Member

DavePearce commented May 8, 2017

Hey,

I don't understand why you need explicit instancing?

Hmmm, not sure exactly what you mean by this.

Isn't the follow sufficient (+ some missing syntax) with requires overloading:

No, since you have to give types on parameters. This is part of the complete separation between typing and verification within the compiler. That's a choice I've made, though it's certainly not the only one.

@bambinella

This comment has been minimized.

Show comment
Hide comment
@bambinella

bambinella May 8, 2017

I don't understand why you have to do this:
instantiate whiley.lang.Array.reverse(int[])

Why can't you just execute it inside a method/function and let the compiler figure out that it has to be instantiated? E.g.:
whiley.lang.Array.reverse(a)

bambinella commented May 8, 2017

I don't understand why you have to do this:
instantiate whiley.lang.Array.reverse(int[])

Why can't you just execute it inside a method/function and let the compiler figure out that it has to be instantiated? E.g.:
whiley.lang.Array.reverse(a)

@DavePearce

This comment has been minimized.

Show comment
Hide comment
@DavePearce

DavePearce May 9, 2017

Member

Why can't you just execute it inside a method/function and let the compiler figure out that it has to be instantiated?

Right, you could do this. But, this is just a language design choice. Basically, it avoids the "template instantiation problem" found in e.g. C++. See this for more:

Oh, and look there ... g++ supports extern template as a solution which is comparable to what I'm suggesting above (and I didn't know that until just now :) Interesting and there's a compiler switch -fno-implicit-templates which moves the language into what is effectively my model above.

The other issue with allowing automatic instantiation is actually one of syntax (perhaps surprisingly). In your example you wrote reverse(a). That will be fine in most cases and relies on the compiler to infer the appropriate template instantiation. But, for me being who I am, I absolutely would want a fall back plan. That is, some way to communicate explicitly to the compiler what instantiation to use. The syntax for this could be, for example, reverse<int[]>(a).

I have spent a lot of time thinking about the right syntax for reverse<int[]>(a). Basically, this syntax is hard to parse. See what Java did here:

http://stackoverflow.com/questions/3012781/java-syntax-for-explicitly-specifiying-generic-arguments-in-method-calls

In C++, I think you can say reverse<int[]>(a). But, the problem is that this requires arbitrary lookahead when parsing and, well, it's already known that parsing C++ is super hard. This is something I want to avoid.

Member

DavePearce commented May 9, 2017

Why can't you just execute it inside a method/function and let the compiler figure out that it has to be instantiated?

Right, you could do this. But, this is just a language design choice. Basically, it avoids the "template instantiation problem" found in e.g. C++. See this for more:

Oh, and look there ... g++ supports extern template as a solution which is comparable to what I'm suggesting above (and I didn't know that until just now :) Interesting and there's a compiler switch -fno-implicit-templates which moves the language into what is effectively my model above.

The other issue with allowing automatic instantiation is actually one of syntax (perhaps surprisingly). In your example you wrote reverse(a). That will be fine in most cases and relies on the compiler to infer the appropriate template instantiation. But, for me being who I am, I absolutely would want a fall back plan. That is, some way to communicate explicitly to the compiler what instantiation to use. The syntax for this could be, for example, reverse<int[]>(a).

I have spent a lot of time thinking about the right syntax for reverse<int[]>(a). Basically, this syntax is hard to parse. See what Java did here:

http://stackoverflow.com/questions/3012781/java-syntax-for-explicitly-specifiying-generic-arguments-in-method-calls

In C++, I think you can say reverse<int[]>(a). But, the problem is that this requires arbitrary lookahead when parsing and, well, it's already known that parsing C++ is super hard. This is something I want to avoid.

@bambinella

This comment has been minimized.

Show comment
Hide comment
@bambinella

bambinella May 9, 2017

Ok, I have to think a little bit more about this, I guess. I am not saying the following is a choice that Whiley should follow, but in my own sketches I have thought that if ":" always indicates a description of the left side then you could have reverse(a:int[]).

Nevertheless, I guess this issue with instantiation can be modified at a later state if deemed necessary. I assume that templating, as you envision it, doesn't affect the IR at all?

Ok, I have to think a little bit more about this, I guess. I am not saying the following is a choice that Whiley should follow, but in my own sketches I have thought that if ":" always indicates a description of the left side then you could have reverse(a:int[]).

Nevertheless, I guess this issue with instantiation can be modified at a later state if deemed necessary. I assume that templating, as you envision it, doesn't affect the IR at all?

@DavePearce

This comment has been minimized.

Show comment
Hide comment
@DavePearce

DavePearce May 9, 2017

Member

Yes, there are certainly alternative syntax which could be used that are easier to parse. I think your suggestion reverse(a:int[]) would work. Likewise, something weird like reverse#int[]#(a) would work (but is of course ugly).

In the end, this is what I decided that worked the best for me. Having just read yet more about what C++ does here, I am actually more convinced now this is the right approach.

Member

DavePearce commented May 9, 2017

Yes, there are certainly alternative syntax which could be used that are easier to parse. I think your suggestion reverse(a:int[]) would work. Likewise, something weird like reverse#int[]#(a) would work (but is of course ugly).

In the end, this is what I decided that worked the best for me. Having just read yet more about what C++ does here, I am actually more convinced now this is the right approach.

@DavePearce

This comment has been minimized.

Show comment
Hide comment
@DavePearce

DavePearce May 9, 2017

Member

Really, the big question with this issue is not the syntax as defined above. But, what level of meta-programming do we want to support with it. For example, what can be used to instantiate a template? I like in C++ that you can use concrete values for example...

Member

DavePearce commented May 9, 2017

Really, the big question with this issue is not the syntax as defined above. But, what level of meta-programming do we want to support with it. For example, what can be used to instantiate a template? I like in C++ that you can use concrete values for example...

@DavePearce

This comment has been minimized.

Show comment
Hide comment
@DavePearce

DavePearce May 9, 2017

Member

Nevertheless, I guess this issue with instantiation can be modified at a later state if deemed necessary. I assume that templating, as you envision it, doesn't affect the IR at all?

It will affect the IR in that templates and the explicit instantiate declarations will be present. But, that's not really a big deal.

Member

DavePearce commented May 9, 2017

Nevertheless, I guess this issue with instantiation can be modified at a later state if deemed necessary. I assume that templating, as you envision it, doesn't affect the IR at all?

It will affect the IR in that templates and the explicit instantiate declarations will be present. But, that's not really a big deal.

@bambinella

This comment has been minimized.

Show comment
Hide comment
@bambinella

bambinella May 9, 2017

Having just read yet more about what C++ does here, I am actually more convinced now this is the right approach.

When you get C++ programmers in here they sure will complain... Just saying. This used to be a problem in C++, but modern compilers no longer does it the old way. So it could make Whiley look a bit dated in the eyes of C++14 programmers. (I feel pretty confident about that, but I could be wrong, I guess)

bambinella commented May 9, 2017

Having just read yet more about what C++ does here, I am actually more convinced now this is the right approach.

When you get C++ programmers in here they sure will complain... Just saying. This used to be a problem in C++, but modern compilers no longer does it the old way. So it could make Whiley look a bit dated in the eyes of C++14 programmers. (I feel pretty confident about that, but I could be wrong, I guess)

@DavePearce

This comment has been minimized.

Show comment
Hide comment
@DavePearce

DavePearce May 11, 2017

Member

This is from @bambinella in #723:

Before adding templates I think it would be worthwhile to take an open-minded look at what C++ has done with concepts:

http://en.cppreference.com/w/cpp/language/constraints

And what haskell has done with type classes:

https://www.haskell.org/tutorial/classes.html

Member

DavePearce commented May 11, 2017

This is from @bambinella in #723:

Before adding templates I think it would be worthwhile to take an open-minded look at what C++ has done with concepts:

http://en.cppreference.com/w/cpp/language/constraints

And what haskell has done with type classes:

https://www.haskell.org/tutorial/classes.html

@bambinella

This comment has been minimized.

Show comment
Hide comment
@bambinella

bambinella May 23, 2017

Seems like Rust is doing a little bit of flow typing in backwards direction on generics based on method parameters being used? https://doc.rust-lang.org/book/generics.html#resolving-ambiguities.

Seems like Rust is doing a little bit of flow typing in backwards direction on generics based on method parameters being used? https://doc.rust-lang.org/book/generics.html#resolving-ambiguities.

@DavePearce

This comment has been minimized.

Show comment
Hide comment
@DavePearce

DavePearce May 23, 2017

Member
Member

DavePearce commented May 23, 2017

@bambinella

This comment has been minimized.

Show comment
Hide comment
@bambinella

bambinella May 24, 2017

Right, I added it to this wiki page:
https://github.com/Whiley/WhileyCompiler/wiki/Type-Inference-and-Overloading-Mechanisms

I guess it fits under generics, but thought I could collect type-inference-like features from other languages in one place.

bambinella commented May 24, 2017

Right, I added it to this wiki page:
https://github.com/Whiley/WhileyCompiler/wiki/Type-Inference-and-Overloading-Mechanisms

I guess it fits under generics, but thought I could collect type-inference-like features from other languages in one place.

@DavePearce

This comment has been minimized.

Show comment
Hide comment
@DavePearce

DavePearce May 31, 2017

Member

Apparently, D is worth looking at regarding meta-programming:

https://dlang.org/templates-revisited.html

Member

DavePearce commented May 31, 2017

Apparently, D is worth looking at regarding meta-programming:

https://dlang.org/templates-revisited.html

@bambinella

This comment has been minimized.

Show comment
Hide comment
@bambinella

bambinella May 31, 2017

I am not sure if D is the best example. I get a semi-typed macro-like feel from it. No deduction as far as I can tell.

I am not sure if D is the best example. I get a semi-typed macro-like feel from it. No deduction as far as I can tell.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment