Type system question

Robert Fraser fraserofthenight at gmail.com
Wed Dec 10 19:09:11 PST 2008

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.

More information about the Digitalmars-d mailing list