BAL paper available

Marcin 'Qrczak' Kowalczyk qrczak@knm.org.pl
15 May 2001 19:11:49 GMT


Tue, 15 May 2001 16:10:20 +0400, S.D.Mechveliani <mechvel@math.botik.ru> pisze:

> The matter was always in parametric domains ...

The solution is simple: don't model domains as types. Model them
as values (records with operations).

Some simple domains can be also modelled as types for convenience.
But it doesn't work in general. Similarly as standard
    sort :: (Ord a) => [a] -> [a]
is not as expressive as
    soryBy :: (a -> a -> Ordering) -> [a] -> [a]
even though it's more convenient in case it works.

It doesn't work when various instances of the same kind of algebraic
structure over the same carrier set are considered. And it doesn't
work when a domain should be parametrized by something which is hard
to express by a type. And it constrains programs which want to choose
the domain dynamically.

Carrier sets are modelled as types, OK. But it won't work for all
algebraic structures.

About program transformation possibility: I don't see how it would be
applied in practice. There is no use of associativity of (+) for the
compiler. It can do many optimizations, but it won't rewrite x+(y+z)
to (x+y)+z nor vice versa.

Sample arguments are ugly, almost always unnecessary, and constrain
interfaces (functions like 'sum :: Num a => [a] -> a' would have to
have a different intreface). They are a solution to a wrong problem:
some domains should not have been modelled as types in the first place.

Algebraic operations don't belong to elements of algebras; they belong
to algebras. In simple cases they can be deduced from the types of
elements if the given carrier has a reasonable default interpretation
of these operations (e.g. (+) on Integers), but it's not general.

I don't believe that dependent types would come into Haskell in the
near future. And they are unnecessary for the discussed purpose:
domains which would require them should not be modelled as types.
Don't abuse types to model values. Haskell's types are too static
for that.

The class hierarchy is unacceptable for me as standard Haskell.
It's way too complex. Currently I have to define instances of Eq,
Show, Num and Fractional to have field operations. With BAL I would
have to define instances of Eq, Show, Set, Additive, AddSemigroup,
AddGroup, Multiplicative, MulSemigroup, Ring, CommutativeRing, GCDRing,
EuclideanRing, FactorizationRing and Field. They require such things
as specifying an arbitrarily chosen set of properties of the domain
and partially defined versions of most operations...

The hierarchy contains many unnecessary superclass relationships. For
example Show, specifying bounds and conversion from 'Expression String'
are not necessary for Ord, where your classes artificially require
them.

There are no class synonyms in Haskell, so classes like OrdAddGroup
can't be treated as implicit.

Later parts are too heavy for me to understand them well, but I see
some ugly points, like abusing Char arguments to virtually extend the
function name, or requirement to provide reflection capabilities at
the very beginning by every type wanting to use overloading of basic
operations, or requirement that the programmer knows more advanced
math than should be necessary to use Haskell.

I hope that a similar proposal won't go into standard Haskell.

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