Re: [Algorithms] Complexity of new hardware

[Sebastian S. <seb...@gm...>]

On Sun, Apr 26, 2009 at 11:30 AM, Nicholas "Indy" Ray <ar...@gm...>wrote:

> On Sun, Apr 26, 2009 at 2:08 AM, Sebastian Sylvan
> <seb...@gm...> wrote:
> > They do actually. Haskell always infers the *most general* type for a
> > function. Adding a type signature can specialize it giving you faster
> code
> > (by avoiding the need for runtime dispatch of any polymorphic functions -
> if
> > the compiler knows that the * always refers to integer multiplication, it
> > can just emit the native honest-to-goodness int multiplication
> instruction
> > directly).
>
> That's in interesting property, I've never seriouslly used Haskell,
> but in ML, even though the * operation can be of type 'a -> 'a the
> compiler will specialiase it to int -> in the cases where the type
> inference allows it to do such, with no dynamic dispatch required
> unless there is the possibility of union/any types running around
> (which I've found to be very rare).


This may require a lot of cross-module optimizations so is a bit harder to
do in general, but yes the specialization can happen at the "use site", but
that requires that the use site itself knows it's using an Int and not "Num
a". So at some point there needs to be something restricting it to a
specific type, and the closer that happens to the implementation, the less
cross-module optimization you need to get it.


> > (e.g. a type of a -> a, has precisely one imlementation, id, whereas a
> type
> > from Integer -> Integer has an infinite number of implementations),
>
> I'm sorry, I don't follow. A function of type 'a -> 'a is a superset
> of int -> int thus implementations must contain the later.


If I (or rather, the context in which a function is called) give you the
type "a->a", and ask you to implement a function satisfying that type, there
is only one implementation (id). Since you know nothing about what type the
parameter passed in has, you can't do anything except just return it back
out. Likewise for "(a,b)->a" (fst).
On the other hand if I give you the type "Integer->Integer" and ask you to
write an implementation, there's an infinite number of possibilities that
can satisfy that type (e.g. +1, +2, etc.).

So the point is that if the expected type of a specific function is
polymorphic, then you have less wiggle room to write something that
satisfies the type - and in some cases the number of implementations that
can satisfy the type is just one, but even when you add some non-polymorphic
stuff to the type every polymorphic part will cut out a "degree of freedom"
from the implementation. The fact that you know something is an Int means
you can "do more" to the variable - if it's fully polymorphic you can't do
anything to it (and likewise if it's "numeric" you can only do maths on it,
and so on).
Thus, the more polymorphic the type, the smaller the valid "implementation
space" is, and therefore the more likely it is that an incorrect
implementation will be caught by the type checker.


> Perhaps, I still don't think that C# is well designed for game
> development and this "something simular" doesn't exist yet and afaict
> no one is working on it. If the language doesn't exist, it's difficult
> to design the hardware to run it well.


Well I wouldn't really consider C++ to be well designed for game development
either, so it's all about the relative merits, I guess. Personally I'd
prefer C# over C++ in 90% of game code, assuming that we get a proper
incremental garbage collector, good static null- and out-of-bounds checking
elimination etc. F# is looking pretty good.


-- 
Sebastian Sylvan
+44(0)7857-300802
UIN: 44640862