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
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 "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
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 parent reply BCS <ao pathlink.com> writes:
Reply to bearophile,


 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


C++ template are Turing compleat -> D template probably are. What more do 
you want?
Dec 10 2008
next sibling parent reply "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?


 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


 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
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 reply 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
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 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 reply "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
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 parent reply "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
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 reply 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
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