Revamping the numeric classes

Marcin 'Qrczak' Kowalczyk qrczak@knm.org.pl
9 Feb 2001 19:16:25 GMT


Fri, 9 Feb 2001 15:21:45 +0100 (MET), Bjorn Lisper <lisper@it.kth.se> pisze:

> No, the transformation is a single step procedure where a term
> is transformed into a typeable term (if possible) with a minimal
> amount of lifting. You don't compose transformations.

So functions implicitly lifted can't be used in the same ways as
functions originally defined as lifted (namely, they can't be lifted
again)... This is bad.

> Due to the principle of minimal lifting (which implies already
> well-typed terms should not be transformed) a call to a polymorphic
> function should not be transformed unless there is a dependence
> between the type variable(s) of the function and of the argument(s)
> in the application.

Does
    f x y = (x, x + y)
has type
    Num a => a -> a -> (a, a)
and thus it cannot be used on the type
    Int -> [Int] -> (Int, [Int])
even though if its body was inlined into an expression requiring that
type, it could (by lifting x+y to map (x+) y)?

You can't lift arbitrary function of type Int -> Int -> (Int, Int)
into Int -> [Int] -> (Int, [Int]) without knowing its defintion.
Try it with g x y = (y, x).

This is bad: I cannot always take a subexpression and move it into
a separate function.

> >With your rules a programmer writes code which is meant to implicitly
> >convert a value to a single-element list, because something tries
> >to iterate over it like on a list. Unfortunately the element happens
> >to be a string, and he gets iteration over its characters. And if it
> >works the other way, another programmer meant iteration over characters
> >and got iteration over a single string. You can't tell which was meant.
> 
> I don't think there will be any ambiguities here. The overloading
> is resolved statically, at compile-time, for each call to the
> function. Calls to polymorphic functions are not transformed
> (except for cases like I showed above).

Suppose there is a function
    fancyPrint :: Printable a => [a] -> IO ()
which applies some fancy printing rules to a list of printable values.

A programmer knows that this function can be used on lists as well
as on single elements, because those elements will be promoted to
single-element lists as necessary. So far so good.

Then he applies it to a single String. Guess what? It is not
promoted to a single-element list, but each character is printed
separately. Oops!

The rule that fancyPrint works for single printable objects is valid
as long as this single element is *not* a list.

Your rules create many opportunites for functions which work on
a certain well-described domain *except* some specific types on which
they break.

> >It's not enough, because the least lifted type is not the most general
> >answer. Answers for different amounts of liftedness are incompatible
> >with that answer - they are not its instances as in the HM typing.
> 
> It does not matter that they are not instances.

It does. It's not enough to check that there exists a set of places
to insert map or zipWith which transforms what is written to what I
need. Because there can be a different, incompatible set of places,
which is considered "better" by the compiler and my set is not
obtainable from what the compiled has done. See the first example
above.

The HM type system does have the property that I can think about more
specific types than ones inferred by the compiler, and as long as the
program can be typed under stricter assumptions, it works as expected.
The compiler may infer more general types than I thought about, but in
such case my type is an instance of the compiler's type and the result
is the same.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK