Proposal for the definition domain extension
in Haskell language.
To separate a sublanguage of Haskell given by the corresponding
compilation key (say, -domExt ) or, maybe, by the compiler pragma.
This sublanguage allows the compiler to replace any function f with
the function f' being the extension for f.
A function (program) f' is called an extension of f if the
definition domain D(f') includes the definition domain D(f)
and the (mathematical) map of f' coincides with the map of f at
D(f).
The definition domain D(f) is the set of values at which f produces
a definite value (a value different from `undefined').
Example 1. take'' is an extension for take':
take' n xs = case (compare n 0, xs) of
(EQ, _ ) -> []
(GT, x:ys) -> x:(take' (n-1) ys)
(GT, _ ) -> error "...too short list"
_ -> error "...negative n"
take'' n xs = case (compare n 0, xs) of
(GT, x:ys) -> x:(take'' (n-1) ys)
_ -> []
--------------------------------------------------------------------
Motivation for proposal.
*
My colleagues that deal with the FP program transformer, consider
the domain extension as an old-known, evidently necessary tool. And
they say, the "lazy" programmers are even more likely to apply the
definition domain extension.
*
Some people say the Mercury language preserves such possibility.
*
In the -domExt mode, the compiler may transform a program ignoring
(in some sense) the possibility of _|_ (`bottom',`undefined') value.
Example 2. x - x :: Int can be transformed to 0 :: Int
under the -domExt mode.
After the program was compiled both under the default mode and
-domExt mode, the user decides whether the given input data for the
program is likely to be "bottom-critical". If it is not, then apply
-domExt version of the program - because it was compiled with more
optimizations.
Example 3.
Suppose the program contains things like
mM*(inverseMatrix mM) :: Matrix Rational
and it is compiled under -domExt.
Then, it is natural to replace such expressions with
unityMatrix :: Matrix Rational
(imagine the _rules_ for this).
Then, if the user is sure that det(mM) /= 0
for some particular argument value mM, one runs the -domExt version
of the program. Otherwise, run the regular version, because -domExt
one would give a dangerously wrong answer. Because for det(mM) = 0,
inverseMatrix mM is likely to return `undefined'.
Example 4.
Imagine several naturally written sorting programs and `minimum'.
Then, putting all the below functions to be of type
:: [Char] -> Char,
has the compiler right to replace the following four functions
with each other:
head . sortByInsertion . ('b':),
head . mergeSort . ('b':),
head . quickSort . ('b':),
minimum . ('b':)
?
('b' is prepended to avoid the situation of minimum [] ).
I suspect that it has not.
And under the -domExt mode, it, probably, may extend all of them to
one function.
But I am not so sure. Do I mistake?
Who could, please, comment on all this?
------------------
Sergey Mechveliani
[EMAIL PROTECTED]
