Re: [Algorithms] Complexity of new hardware

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

On Sun, Apr 26, 2009 at 10:17 PM, Nicholas "Indy" Ray <ar...@gm...>wrote:

> On Sun, Apr 26, 2009 at 3:59 AM, Sebastian Sylvan
> <seb...@gm...> wrote:
> > 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.
>
> Ahh, I understand, And I feel this is the beauty of type inference, as
> the simple act of providing an implementation for a function
> automatically specializes it. in caml for instance I do not have to
> provide any type annotations for the function let f(x, y , z) = x +. y
> +. z;; in order for the compiler to know that it is of type float ->
> float and thus the only time you encounter an a' -> a' is for
> identity, which doesn't occur very often.
>

Well the context in which the function is used can constrain (or generalize,
depending on your perspective) it to be more polymorphic (e.g. it may be
used for both floats and ints). I guess my point is that if the language
encourages you to write polymorphic code (in fact, makes it the default),
then the amount of "slack" in the implementation space that will still
satisfy the type checker is reduced which leads to the "works once the
compiler stops complaining" effect.

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