www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Idea: Reverse Type Inference

reply Sebastiaan Koppe <mail skoppe.eu> writes:
I work with Scala professionally. I often feel its type inference 
for generics/templates is better than D's; as long as it can find 
a type _anywhere_ it will use that, no matter where it needs to 
pull it from.

Over the past weeks I have been noticing a specific case where it 
happens. I call it reverse type inference, simply because it goes 
against the normal evaluation order.

While it is only syntactic sugar, I think it would be nice to 
have in D and I want to know what you guys think about it.

Some examples:

---

T convert(T)(string s) { ... }

auto dec = "1234".convert!int;   // normal
int dec = "1234".convert;        // T of convert is inferred due 
to type declaration of dec

int square(int t) { ... }

auto a = "1234".convert.square;  // since square accepts int, T 
of convert is inferred to be int

---

p.s. I am not asking anyone to build it. I just want to have the 
idea out there. And if time allows I might take a stab at 
implementing it.
May 22 2017
next sibling parent Moritz Maxeiner <moritz ucworks.org> writes:
On Monday, 22 May 2017 at 10:13:02 UTC, Sebastiaan Koppe wrote:
 I work with Scala professionally. I often feel its type 
 inference for generics/templates is better than D's; as long as 
 it can find a type _anywhere_ it will use that, no matter where 
 it needs to pull it from.

 Over the past weeks I have been noticing a specific case where 
 it happens. I call it reverse type inference, simply because it 
 goes against the normal evaluation order.

 While it is only syntactic sugar, I think it would be nice to 
 have in D and I want to know what you guys think about it.

 Some examples:

 ---

 T convert(T)(string s) { ... }

 auto dec = "1234".convert!int;   // normal
 int dec = "1234".convert;        // T of convert is inferred 
 due to type declaration of dec

 int square(int t) { ... }

 auto a = "1234".convert.square;  // since square accepts int, T 
 of convert is inferred to be int

 ---

 p.s. I am not asking anyone to build it. I just want to have 
 the idea out there. And if time allows I might take a stab at 
 implementing it.
AFAICT this should be possible purely with changes to the compiler frontend (no language changes), yes? Regardless, this would be nice to have, because imho this (from your examples): --- int dec = "1234".convert; --- is easier to review than this: --- auto dec = "1234".convert!int; and I'm all for making code more readable. I must object against usage of this though: --- auto a = "1234".convert.square; --- No way for a reviewer to easily guess the type of a without inspecting all functions.
May 22 2017
prev sibling next sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Monday, 22 May 2017 at 10:13:02 UTC, Sebastiaan Koppe wrote:
 I work with Scala professionally. I often feel its type 
 inference for generics/templates is better than D's; as long as 
 it can find a type _anywhere_ it will use that, no matter where 
 it needs to pull it from.
And how long does that code take to compile ? type inference is not magic, it's a search for a pattern over the syntax (sub)tree. Hence it can have quadratic time/memory complexity. Additionally it's harder to prove sound, i.e. there is more potential for undetected bugs, As well as making it more surprising when the inference fails.
May 22 2017
next sibling parent Guillaume Boucher <guillaume.boucher.d outlook.com> writes:
On Monday, 22 May 2017 at 13:20:41 UTC, Stefan Koch wrote:
 type inference is not magic, it's a search for a pattern over 
 the syntax (sub)tree.
 Hence it can have quadratic time/memory complexity.
Well, the type system of Scala is turing complete, hence it can take arbitrarily long: https://michid.wordpress.com/2010/01/29/scala-type-level-encoding-of-the-ski-calculus/
May 22 2017
prev sibling parent bachmeier <no spam.net> writes:
On Monday, 22 May 2017 at 13:20:41 UTC, Stefan Koch wrote:

 And how long does that code take to compile ?
+1 My immediate thought was one of horror - Scala's compilation times are a sufficient reason to avoid the language. I also think it would make D code harder to read. Not a problem in some cases, but in others it would add a lot of complexity.
May 22 2017
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 22.05.2017 12:13, Sebastiaan Koppe wrote:
 I work with Scala professionally. I often feel its type inference for
 generics/templates is better than D's; as long as it can find a type
 _anywhere_ it will use that, no matter where it needs to pull it from.

 Over the past weeks I have been noticing a specific case where it
 happens. I call it reverse type inference, simply because it goes
 against the normal evaluation order.

 While it is only syntactic sugar,
(It's not.)
 I think it would be nice to have in D
 and I want to know what you guys think about it.

 Some examples:

 ---

 T convert(T)(string s) { ... }

 auto dec = "1234".convert!int;   // normal
 int dec = "1234".convert;        // T of convert is inferred due to type
 declaration of dec

 int square(int t) { ... }

 auto a = "1234".convert.square;  // since square accepts int, T of
 convert is inferred to be int

 ---

 p.s. I am not asking anyone to build it. I just want to have the idea
 out there. And if time allows I might take a stab at implementing it.
I'm in favour. Note that this already happens in some circumstances, e.g. the parameter type of the delegate is inferred here from the expected type: int delegate(int) dg = x=>x; I suspect your enhancement might actually be easy to implement by reusing the same mechanism in the compiler. (I.e. defer the template instantiation if forward inference is incomplete, and then deduce the remaining template arguments in "matchType".) Another annoying case: alias Fun(A,B) = B delegate(A); B apply(A,B)(Fun!(A,B) f, A a){ return f(a); } void main(){ apply(x=>x,2); // error }
May 22 2017
parent reply Petar Kirov [ZombineDev] <petar.p.kirov gmail.com> writes:
On Monday, 22 May 2017 at 13:39:46 UTC, Timon Gehr wrote:
 On 22.05.2017 12:13, Sebastiaan Koppe wrote:
 I work with Scala professionally. I often feel its type 
 inference for
 generics/templates is better than D's; as long as it can find 
 a type
 _anywhere_ it will use that, no matter where it needs to pull 
 it from.

 Over the past weeks I have been noticing a specific case where 
 it
 happens. I call it reverse type inference, simply because it 
 goes
 against the normal evaluation order.

 While it is only syntactic sugar,
(It's not.)
 I think it would be nice to have in D
 and I want to know what you guys think about it.

 Some examples:

 ---

 T convert(T)(string s) { ... }

 auto dec = "1234".convert!int;   // normal
 int dec = "1234".convert;        // T of convert is inferred 
 due to type
 declaration of dec

 int square(int t) { ... }

 auto a = "1234".convert.square;  // since square accepts int, 
 T of
 convert is inferred to be int

 ---

 p.s. I am not asking anyone to build it. I just want to have 
 the idea
 out there. And if time allows I might take a stab at 
 implementing it.
I'm in favour. Note that this already happens in some circumstances, e.g. the parameter type of the delegate is inferred here from the expected type: int delegate(int) dg = x=>x; I suspect your enhancement might actually be easy to implement by reusing the same mechanism in the compiler. (I.e. defer the template instantiation if forward inference is incomplete, and then deduce the remaining template arguments in "matchType".) Another annoying case: alias Fun(A,B) = B delegate(A); B apply(A,B)(Fun!(A,B) f, A a){ return f(a); } void main(){ apply(x=>x,2); // error }
Interesting. BTW, what do you think about this feature being extended to implicit template instantiations a la Rust: https://doc.rust-lang.org/book/generics.html#resolving-ambiguities ? In Kotlin they have a related feature called smart casts: https://kotlinlang.org/docs/reference/typecasts.html (also briefly shown here https://www.youtube.com/watch?v=X1RVYt2QKQE&t=1569s) Which of course is a subset of the more general area of control flow based type analysis. Typescript is good example of bringing those things to the JS world: https://www.youtube.com/watch?v=d1f6VBmWg6o&t=39m39s https://blog.mariusschulz.com/2016/09/30/typescript-2-0-control-flow-based-type-analysis
May 23 2017
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 23.05.2017 16:55, Petar Kirov [ZombineDev] wrote:
 On Monday, 22 May 2017 at 13:39:46 UTC, Timon Gehr wrote:
 ...
 Another annoying case:

 alias Fun(A,B) = B delegate(A);

 B apply(A,B)(Fun!(A,B) f, A a){ return f(a); }

 void main(){
     apply(x=>x,2); // error
 }
Interesting. BTW, what do you think about this feature being extended to implicit template instantiations a la Rust: https://doc.rust-lang.org/book/generics.html#resolving-ambiguities ? ...
This is easier to pull off in Rust, where generics are more limited and there are no implicit conversions, but it could work, to a useful extent. It's less likely to happen though, because so far, all type deduction happens locally (except attributes). I don't think the compiler is set up to very easily migrate to a system where type deduction and implicit template instantiation can happen at a distance.
 In Kotlin they have a related feature called smart casts:
 https://kotlinlang.org/docs/reference/typecasts.html
 (also briefly shown here 
 https://www.youtube.com/watch?v=X1RVYt2QKQE&t=1569s)
 ...
This is cheap for them to support, as everything is a class reference and they do null safety the same way. In D, not every type is a class, and language magic causes friction, so user-defined types would need to be able to customize such an analysis in some way. (E.g. typestate.)
 Which of course is a subset of the more general area of control flow 
 based type analysis. Typescript is good example of bringing those things 
 to the JS world: https://www.youtube.com/watch?v=d1f6VBmWg6o&t=39m39s
 https://blog.mariusschulz.com/2016/09/30/typescript-2-0-control-flow
based-type-analysis 
 
This only works really well if types do not implicitly affect execution. D has e.g. opAssign, based on the assumption that types of variables do not change. Also, in D, types are used to determine memory layout. They don't seem to take it very far though. (E.g. it does not seem to support polymorphic record updates from what I can see).
May 23 2017
prev sibling parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Monday, 22 May 2017 at 10:13:02 UTC, Sebastiaan Koppe wrote:
 Over the past weeks I have been noticing a specific case where 
 it happens. I call it reverse type inference, simply because it 
 goes against the normal evaluation order.
I think what you want, in the general sense, is basically overloading based on return-type. Which I think is a very useful and cool feature. But D moste likely follows C++ by doing resolution bottom-up (starting from the leaves of the AST). For the requested feature you need to do resolution top-down (which I believe Ada does). The downside of this is when you hit ambiguities, thanks to implicit conversion/coercion (which I think is mostly a mal-feature and a source for bugs). One solution to this is to give preference to the match that use the fewest implicit conversions. But I think the better solution is to: 1. remove implicit type conversion 2. add a more compact notation for indicating desired type so that you can call the desired function without using the return value. (i.e. "f(x):int" to request the version of f(x) that returns int) You might hack together a solution just for templates, but it makes the language even less orthogonal than it is. So I think D is better off doing it in a manner that is consistent and avoids more special cases.
May 23 2017
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 5/23/17 5:20 AM, Ola Fosheim Grøstad wrote:
 On Monday, 22 May 2017 at 10:13:02 UTC, Sebastiaan Koppe wrote:
 Over the past weeks I have been noticing a specific case where it
 happens. I call it reverse type inference, simply because it goes
 against the normal evaluation order.
I think what you want, in the general sense, is basically overloading based on return-type. Which I think is a very useful and cool feature.
This is different. It's IFTI based on return type. BTW, swift does this too, and I have to say it's useful in a lot of cases. For example, any time you have a variant-like interface, and an already existing type, something like this looks so much cleaner. struct Point { int x; int y; } auto row = getRowFromDB(); auto p = Point(row.get!int("x"), row.get!int("y")); // currently required auto p = Point(row.get!(typeof(Point.x))("x"), row.get!(typeof(Point.y))("y")); // more generic, but horribly ugly. auto p = Point(row.get("x"), row.get("y")); // with better IFTI -Steve
May 24 2017
parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Wednesday, 24 May 2017 at 13:03:37 UTC, Steven Schveighoffer 
wrote:
 This is different. It's IFTI based on return type.
Well, the way I see it it is a special case of top-down type inference. Yes, you also have to instantiate the template, but I assume that happens after type inference is complete? So my point was more: why not cover the general case, if you are going to add it as a feature?
 auto p = Point(row.get("x"), row.get("y")); // with better IFTI
Ok, well, I see templates in this context as a variation of overloading, just with the template parametric type being a set of types i.e. all types that the program provides, minus the ones prevented by contraints. I guess it is a matter of vantage point. It would be odd to allow this for templates only and not provide it for functions...
May 24 2017
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 5/24/17 10:28 AM, Ola Fosheim Grøstad wrote:
 On Wednesday, 24 May 2017 at 13:03:37 UTC, Steven Schveighoffer wrote:
 This is different. It's IFTI based on return type.
Well, the way I see it it is a special case of top-down type inference. Yes, you also have to instantiate the template, but I assume that happens after type inference is complete? So my point was more: why not cover the general case, if you are going to add it as a feature?
 auto p = Point(row.get("x"), row.get("y")); // with better IFTI
Ok, well, I see templates in this context as a variation of overloading, just with the template parametric type being a set of types i.e. all types that the program provides, minus the ones prevented by contraints. I guess it is a matter of vantage point. It would be odd to allow this for templates only and not provide it for functions...
I believe that IFTI would be much more straightforward than overloading, because there is no concern about implicit conversion. -Steve
May 24 2017
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 5/24/17 10:58 AM, Steven Schveighoffer wrote:
 On 5/24/17 10:28 AM, Ola Fosheim Grøstad wrote:
 Ok, well, I see templates in this context as a variation of overloading,
 just with the template parametric type being a set of types i.e. all
 types that the program provides, minus the ones prevented by
 contraints.  I guess it is a matter of vantage point.

 It would be odd to allow this for templates only and not provide it for
 functions...
I believe that IFTI would be much more straightforward than overloading, because there is no concern about implicit conversion.
In fact, you could simulate overloading of return values based on IFTI instantiation: void fooImpl(ref int retval, int x) { ... } void fooImpl(ref string retval, int x) { ... } T foo(T)(int x) { T t; fooImpl(t, x); return t; } int x = foo(1); string y = foo(2); -Steve
May 24 2017
parent reply Enamex <enamex+d outlook.com> writes:
On Wednesday, 24 May 2017 at 15:02:05 UTC, Steven Schveighoffer 
wrote:
 In fact, you could simulate overloading of return values based 
 on IFTI instantiation:

 void fooImpl(ref int retval, int x) { ... }
 void fooImpl(ref string retval, int x) { ... }

 T foo(T)(int x) { T t; fooImpl(t, x); return t; }
 int x = foo(1);
 string y = foo(2);

 -Steve
https://dpaste.dzfl.pl/7d8351fe2f07 What am I doing wrong?
Jun 03 2017
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 6/3/17 7:37 PM, Enamex wrote:
 On Wednesday, 24 May 2017 at 15:02:05 UTC, Steven Schveighoffer wrote:
 In fact, you could simulate overloading of return values based on IFTI
 instantiation:

 void fooImpl(ref int retval, int x) { ... }
 void fooImpl(ref string retval, int x) { ... }

 T foo(T)(int x) { T t; fooImpl(t, x); return t; }
 int x = foo(1);
 string y = foo(2);
https://dpaste.dzfl.pl/7d8351fe2f07 What am I doing wrong?
You are not realizing that my example requires IFTI on return types, something that I proposed but is not implemented ;) -Steve
Jun 05 2017