www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Type system question

reply bearophile <bearophileHUGS lycos.com> writes:
Do you know if someone has created a (small) C++/D - like language designed to
work with a Hindley-Milner type inference algorithm (using it for something
useful)?
Days ago I was thinking about how much good it may come from giving such type
system to D2, but I don't how it can interact with the D templates.

Bye,
bearophile
Dec 09 2008
parent reply "Tim M" <a b.com> writes:
How would that improve on auto?

On Wed, 10 Dec 2008 20:17:24 +1300, bearophile <bearophileHUGS lycos.com>  
wrote:

 Do you know if someone has created a (small) C++/D - like language  
 designed to work with a Hindley-Milner type inference algorithm (using  
 it for something useful)?
 Days ago I was thinking about how much good it may come from giving such  
 type system to D2, but I don't how it can interact with the D templates.

 Bye,
 bearophile

Dec 10 2008
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Tim M:
 How would that improve on auto?

It's like asking how a domestic Flying Disk UFO can improve your bicycle travels to the nearby milk shop :-) The answer is: it can do that and much more. Bye, bearophile
Dec 10 2008
next sibling parent reply BCS <ao pathlink.com> writes:
Reply to bearophile,

 Tim M:
 
 How would that improve on auto?
 

bicycle travels to the nearby milk shop :-) The answer is: it can do that and much more. Bye, bearophile

C++ template are Turing compleat -> D template probably are. What more do you want?
Dec 10 2008
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Bill Baxter:
 I'm curious if such strong type inference ideas could improve D.  It's
 interesting, but really the example I came up with above has done
 little to convice me of the value.  So I'm also hoping, Bearophile,
 that you can provide some convincing examples of the power of stronger
 type inference.

I like to learn and discuss, I'm not here to convince people :-) A strong type inferencer can of course allow the compiler to find by itself all the types used into a function, as in the ML language. An even more complex type inferencer can even infer all the types of your program, this is what ShedSkin (and the Stalin Scheme compiler) does when you feed it with Python code. But such global type inferencing requires a lot of time for the compiler (and such time grows in a superlinear way), so I consider ShedSkin a failed experiment... So my point in a possible more flexible type system was not in creating a new kind of full type inferencer. A flexible type system allows you to do few of the things you can see in the Scala language, or even ones in Haskell. Like managing type classes, etc. This purpose expands the number of things the type system can do for you, but also forces the programmer to learn some new things, that aren't present in C. So the language gets a little (or more than a little) more complex. So you can see at my original "proposal" as the idea of creating a statically compiled language like Scala, that can be used a C too. (But Scala has several things I don't like, so lot of syntax has to be removed and other lower-level things to be added). Note there's already a language a bit like this, the ATS, but for me it's ugly (here there are unusually ugly examples because the author has done any thing to reach the performance of C, the result is much less readable than C itself): http://shootout.alioth.debian.org/u32/ Bye, bearophile
Dec 10 2008
parent Robert Fraser <fraserofthenight gmail.com> writes:
bearophile wrote:
 http://shootout.alioth.debian.org/u32/

Hey, what happened to D? It's not there anymore!
Dec 10 2008
prev sibling next sibling parent reply Robert Fraser <fraserofthenight gmail.com> writes:
Bill Baxter wrote:
 Seriously though, here's an example taken from the wikipedia "Type
 Inference" page
 
 someFunction(x, y) {
     return x+y;
 }
 
 addone(x) {
     val result;  /*inferred-type result (in proposed language)*/
     result = someFunction(x,1);
     return result;
 }
 
 With full type inference, the compiler knows that addone takes an int
 and returns an int.
 How?
 - Because + only adds values of the same type
 - Therefore someFunction takes two values of the same type
 - addone calls someFunction with x and an int.  Since someFunction
 takes two values of the same type, x must be an int too.
 - finally some function returns the same type as its inputs, so
 'result' is also an int.
 - therefore addone is a function that takes an int and returns an int.
 
 And all that was determined by the fact that an integer literal was
 used somewhere in the middle of the function.

I know his is tangential to your point, but Hindley-Milner is actually more versatile than that. addone takes any type which is convertible to a number, and returns that type (in Haskell, the type would be something like "a: Num -> a" IIRC). For example, if you pass a double in there, it will work fine. But that's _precisely_ why it won't work for D without some serious trickery. Since addone will work with integers (4 bytes) or doubles (8 bytes), the compiler can't generate machine code for it (the workaround, as was discussed in a different topic is to make it a "template" and to do code generation at the call site -- but this makes it unusable in libraries without the original code or a special object file format). There's also the issue of class-based inheritance (I think this was discussed in another topic): someFunction(x, y) { x. add(y); } Again, what's the type here? The type of x is "any class/struct which has an add method which takes a y" and the type of y is "anything that can be passed to x's add method". One possibility is to explore all possible combinations thereof (sloooooow compile times). Another is to do a "forward" pass propagating all types actually used (say from a main method) -- but this doesn't work for library functions. So again, the only solution here is "templates" - do the code generation on the call site, and again requires a special object file type or access to the code. And making this into something that could be dynamically linked would require a special (JIT) runtime layer. Oh, and then there's the issue of D being a "systems" language. Occasionally, you'll want to coerce something into a type it's not, especially if working with low-level code, unions, etc.
Dec 10 2008
parent bearophile <bearophileHUGS lycos.com> writes:
Robert Fraser:

Oh, and then there's the issue of D being a "systems" language. Occasionally,
you'll want to coerce something into a type it's not, especially if working
with low-level code, unions, etc.<

This isn't a problem, you can add type annotations where you want. I don't know enough about such advanced type systems yet, so I can't give you good answers. But seeing languages that do something similar (Scala, ATS, BitC) it may be doable. Bye, bearophile
Dec 11 2008
prev sibling parent reply Michel Fortin <michel.fortin michelf.com> writes:
On 2008-12-10 20:17:54 -0500, "Bill Baxter" <wbaxter gmail.com> said:

 someFunction(x, y) {
     return x+y;
 }
 
 addone(x) {
     val result;  /*inferred-type result (in proposed language)*/
     result = someFunction(x,1);
     return result;
 }

Isn't the following already working in D2? (I don't have a D2 compiler at hand right now to check) auto someFunction(X, Y)(X x, Y y) { return x+y; } auto addone(X)(X x) { auto result = someFunction(x, 1); return result; } I agree that the syntax can be improved; I already suggested using "auto" for argument types to create function templates, which would give: auto someFunction(auto x, auto y) { return x+y; } auto addone(auto x) { auto result = someFunction(x, 1); return result; } -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Dec 11 2008
parent Michel Fortin <michel.fortin michelf.com> writes:
On 2008-12-11 21:09:16 -0500, "Bill Baxter" <wbaxter gmail.com> said:

 On Fri, Dec 12, 2008 at 10:58 AM, Michel Fortin
 
 I agree that the syntax can be improved; I already suggested using "auto"
 for argument types to create function templates, which would give:
 
 auto someFunction(auto x, auto y) {
 return x+y;
 }
 
 auto addone(auto x) {
 auto result = someFunction(x, 1);
 return result;
 }

That's a nice suggestion. Doesn't cover all cases, but handles simple templates very nicely.

In a way, it's bringing D closer to scripting languages. The major difference being that any type propagation error in a given code path will be caught at compile-time instead of at runtime.
 I guess the problem is it doesn't mix well with the case where you
 need to specify some constraints on the types.  Like
    someFunc(T,K)(T[K] x, K y)

Hum, well, we could try this: auto someFunc(auto[typeof(y)] x, auto y) { ... } I'll concede that the current template syntax with parametrized types may be better in this case, and that it's absolutely necessary for expressing the constrains in this function: auto someFunc(T,K)(T[K] x, K[T] y) { ... } But anyway, if you prefer to keep things simple, don't specify the constrains. auto someFunc(auto x, auto y) { ... } -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Dec 12 2008
prev sibling next sibling parent "Bill Baxter" <wbaxter gmail.com> writes:
On Thu, Dec 11, 2008 at 9:44 AM, BCS <ao pathlink.com> wrote:
 Reply to bearophile,

 Tim M:

 How would that improve on auto?

bicycle travels to the nearby milk shop :-) The answer is: it can do that and much more. Bye, bearophile

C++ template are Turing compleat -> D template probably are. What more do you want?

CPU instructions typed in binary is Turing complete too. What more do we need? Seriously though, here's an example taken from the wikipedia "Type Inference" page someFunction(x, y) { return x+y; } addone(x) { val result; /*inferred-type result (in proposed language)*/ result = someFunction(x,1); return result; } With full type inference, the compiler knows that addone takes an int and returns an int. How? - Because + only adds values of the same type - Therefore someFunction takes two values of the same type - addone calls someFunction with x and an int. Since someFunction takes two values of the same type, x must be an int too. - finally some function returns the same type as its inputs, so 'result' is also an int. - therefore addone is a function that takes an int and returns an int. And all that was determined by the fact that an integer literal was used somewhere in the middle of the function. Now, whether all this is really a good thing or not I'm not sure. With my code maintainer's hat on it seems very hard to see that addone expects an int. But usually functions in languages with uber type inference are written a little more generically and don't have a literal integer '1' sitting there, killing the generality for no good reason. :-) So what D has is basically the ability to do type inferences in one direction. If you say auto x = somefun(y), it expects the RHS to to have a well-defined type. But with full type inference you can basically have auto anywhere and it can infer it from what happens somewhere after that point in the code. T[] something(T)(T x) { return [x]; } void getValue(ref int v) { v = 1; } void getValue(ref string v) { v = "one"; } .... auto a; getValue(a); int[] x = something(a); there it knows 'a' has to be an int because that's the only thing that is consistent. --bb
Dec 10 2008
prev sibling next sibling parent "Bill Baxter" <wbaxter gmail.com> writes:
 So what D has is basically the ability to do type inferences in one
 direction.

To be fair, D can do some other kinds of inference too, as in selecting template type parameters using IFTI, and inferring which overload of a function you want based on argument types, and the is() expression can do some type deduction tricks too. I'm curious if such strong type inference ideas could improve D. It's interesting, but really the example I came up with above has done little to convice me of the value. So I'm also hoping, Bearophile, that you can provide some convincing examples of the power of stronger type inference. --bb
Dec 10 2008
prev sibling next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Tim M Wrote:
 Do what?

Never mind, in the meantime I have found an answer to my original question (with it you can type inference all the types used inside functions, and it allows more things, like type classes, etc.) Scala language shows it's doable. Bye, bearophile
Dec 10 2008
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Thu, 11 Dec 2008 06:14:26 +0300, Robert Fraser <fraserofthenight gmail.com>
wrote:

 bearophile wrote:
 http://shootout.alioth.debian.org/u32/

Hey, what happened to D? It's not there anymore!

IIRC, when moving to new system the maintainer tried to compile code samples with GDC but failed and gave up :(
Dec 10 2008
prev sibling parent "Tim M" <a b.com> writes:
But extra features isn't necessarily a good thing. (Multiple Inheritance  
for example). Can you prove that a new and improved type inference will  
not be counter productive or any other disadvantages.


  On Fri, 12 Dec 2008 01:06:34 +1300, bearophile <bearophileHUGS lycos.com>  
wrote:

 Robert Fraser:

 Oh, and then there's the issue of D being a "systems" language.  
 Occasionally, you'll want to coerce something into a type it's not,  
 especially if working with low-level code, unions, etc.<

This isn't a problem, you can add type annotations where you want. I don't know enough about such advanced type systems yet, so I can't give you good answers. But seeing languages that do something similar (Scala, ATS, BitC) it may be doable. Bye, bearophile

Dec 11 2008
prev sibling next sibling parent "Tim M" <a b.com> writes:
Do what? Currently it is possible to do something like:

auto j = someMethodThatReturnsAnObject();

Can you post an example of the syntax you think would be able to do 'much  
more' and/or explain how it does more.


On Thu, 11 Dec 2008 04:24:15 +1300, bearophile <bearophileHUGS lycos.com>  
wrote:

 Tim M:
 How would that improve on auto?

It's like asking how a domestic Flying Disk UFO can improve your bicycle travels to the nearby milk shop :-) The answer is: it can do that and much more. Bye, bearophile

Dec 10 2008
prev sibling parent "Bill Baxter" <wbaxter gmail.com> writes:
On Fri, Dec 12, 2008 at 10:58 AM, Michel Fortin
<michel.fortin michelf.com> wrote:
 On 2008-12-10 20:17:54 -0500, "Bill Baxter" <wbaxter gmail.com> said:

 someFunction(x, y) {
    return x+y;
 }

 addone(x) {
    val result;  /*inferred-type result (in proposed language)*/
    result = someFunction(x,1);
    return result;
 }

Isn't the following already working in D2? (I don't have a D2 compiler at hand right now to check) auto someFunction(X, Y)(X x, Y y) { return x+y; } auto addone(X)(X x) { auto result = someFunction(x, 1); return result; }

Does it? Didn't know. Won't have much use for D2 till it's got DWT.
 I agree that the syntax can be improved; I already suggested using "auto"
 for argument types to create function templates, which would give:

        auto someFunction(auto x, auto y) {
                return x+y;
        }

        auto addone(auto x) {
                auto result = someFunction(x, 1);
                return result;
        }

That's a nice suggestion. Doesn't cover all cases, but handles simple templates very nicely. I guess the problem is it doesn't mix well with the case where you need to specify some constraints on the types. Like someFunc(T,K)(T[K] x, K y) --bb
Dec 11 2008