Revamping the numeric classes

[Marcin 'Qrczak' Kowalczyk]

Mon, 12 Feb 2001 00:02:00 +0100 (MET), Bjorn Lisper <lisper@it.kth.se> pisze:

> Functions themselves are never lifted. They just appear to be lifted
> when applied to arguments of certain types, and then the function
> application is always statically resolved into an expression where
> the function has its original type.

This does not solve the problems. Instead of composed liftings I will
split the code into separate bindings. Suppose I write:

    let
        g x y = x + y
        f x y = g x y
        in f [1, 2] [10, 20] :: [[Int]]

What does it mean? I could mean this:

    let
        g :: Int -> Int
        g x y = x + y
        f :: Int -> [Int] -> [Int]
        f x y = g x y
        in f [1, 2] [10, 20] :: [[Int]]

which results in [[11, 21], [12, 22]], or this:

    let
        g :: Int -> Int
        g x y = x + y
        f :: [Int] -> Int -> [Int]
        f x y = g x y
        in f [1, 2] [10, 20] :: [[Int]]

which results in [[11, 12], [21, 22]]. Anyway, somebody loses (one
who thought that his version would be chosen by the compiler).

If you think that the fact that bodies of let-bound variables are
typechecked prior to their usage help, let's transform let to lambdas
(it's not used polymorphically so it's possible):

    (\g -> (\f -> f [1, 2] [10, 20] :: [[Int]]) (\x y -> g x y))
    (\x y -> x + y)

Now it is not clear in what order this should be typechecked, and
different orders give different results.

It can be beta/eta-reduced to
    [1, 2] + [10, 20] :: [[Int]]
and I really don't know what meaning would you give to it.

Anyway, examples are pointless. Functional programming, as opposed to
imperative programming, leads to more common use of lists and functions
as values (instead of repeated stateful calls you return all elements
in a list to process them later), also Maybes, tuples etc. Function
explicitly take as arguments things they depend on, explicitly return
things they modify, functions are curried, there are combinators like
(.) or curry which manipulate functions without applying them...

All this means that there are many more places when somebody can
make a type error by mismatching levels of lifting functions or
lifting repetition.

When I am making a type error, the last thing I want from a compiler
is to guess what I could mean and silently compile incorrect code
basing on this assumption. I could have done the error in a different
place!

> >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)?
> 
> Your function has its polymorphism constrained to the Num class. So we could
> allow elemental overloading (on the uncurried form of f) as long as [Int] is
> not an instance of Num.

Suppose [Int] is not Num. I want to treat f as if it meant
    f :: Int -> [Int] -> (Int, [Int])
    f x y = (x, map (x+) y)
because you told me that map is optional: it will be inserted
automatically when necessary.

> BTW, the type signature for your "lifted f" (if it existed) should be
> (Int,[Int]) -> [(Int, Int)]. See second example below.

I want to lift (+) used inside f. Haskell does not require from me
to write all type signatures so I haven't write one in this case,
because I know that Haskell's type system recovers principal types
automatically (except ambiguities related to classes).

> The rewrite of the overloaded application is guided only by type
> information.

Often there is no any type information at a given place. Only at some
later point, when we are considering a toplevel definition with a
type signature. Usually types are inferred from definitions and usages
of each identifier, and a mismatch means that there is a type error.
There is no attempt to guess how to fix it automatically because the
error might be detected at a different place than the change really
should be made.

> So with these rules alone fancyPrint 17 would not be rewritten into
> fancyPrint (repeat 17). But the rules can of course be extended to
> cover this case.

I thought it was rewritten to fancyPrint [17], as this is the obvious
way to convert a scalar to a list...

See, it cannot be implicit, because different people mean different
things.

> >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!
> 
> Which is the original meaning of fancyPrint applied to a string. Why "oops"?

Because I forgot that String is a list, did not treat it as a list,
but as a scalar. I can do it now - except a few cases, but when I
can't (some instances) the compiler will remind me by an error. This
is not the case with your proposal.

> fancyPrint will always be a function over lists, no matter whether
> its use is overloaded on arguments of other types or not.

Similarly, (+) will always be a function over scalars, unless you
make Num instances for lists.

> Of course, the use of the overloading I have described (and any
> kind of overloading) is justified only if the overloading matches
> the intuition of the programmer.  If it misleads you then it is
> harmful. Regarding elemental overloading, my experience is that
> data parallel programmers quickly develop a strong intuition for it.

Perhaps because they don't use higher order functions and arrays they
use always represent arrays of the problem domain, and not a way to
produce multuple results together?

It's a very specific need. And a request for convenience, not
a functional feature. I'm sure it does not make sense to ever change
the Haskell's type system in sush radical way. When Int is unified with
[Int], it's simply an error.

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