Strictness (was: Is this tail recursive?)

[Jay Cox]

On Wed, 13 Mar 2002, Bjorn Lisper wrote:

> Hal Daume III:
> >Here's the basic idea.  Suppose we have the function:
> >
> >> sum [] acc = acc
> >> sum (x:xs) acc = sum xs (acc+x)
> >
> >This is tail recursive, but not strict in the accumulator argument.
> ...
>
> Just a nitpick here. sum is indeed strict in its second argument (given that
> (+) is strict in its first argument). That is, sum l _|_ = _|_ for all
> possible lists l.


Do you really know that? all you know is

(+):: Num a => a -> a -> a therefore sum :: Num a => [a] -> a -> a
now, for any conceivable sum, you generally need both arguments to compute
it (or am I wrong?), so i guess you could say (+) should probably be
strict for both arguments.  But how would you tell the compiler that?

oh wait.
. o O 0  church numerals... peano numerals....

data Peano = Zero | Succ (Peano)

sumpeano blah (Succ x) = sumpeano (Succ blah) x
sumpeano blah Zero     = blah

sumpeano not strict on first argument.
define instance Num for Peano.

I dont even know if you could talk about strictness in either argument
with church numerals. (and I'm to lazy to remind myself what a church
numeral looks like precisely so that I could find out.)






Perhaps what could be done about this strictness business is to make a
kind of strictness annotation.  Perhaps something that says (force the
second argument of function F before every call to F (including any time F
calls itself)).

Then perhaps one could define a strict_foldl = foldl but the strictness
annotations basically "inserts" the proper seq expression or $! into the
redefinition
of foldl.

here's a rough example.  !a mean !a will be forced at its application (for
not knowing proper language to call it).

strict_foldl :: (a -> b -> a) -> !a -> [b] -> a
strict_foldl = foldl

of course, there has to be a number of things that must be propagated
whence you start adding these things. like for instance.

if
f:: !a ->b ->c
f x y = ....
then (flip f) should have type  b ->!a ->c

and then there might be times when you want to ah, lazify, a strict
function. maybe that would be taken care of by giving the type without the
strictness annotation (explicitly giving the type but removing all "!")

How about it?  Has there been any other proposals? (like maybe going as
far as a "Strictness Type" system?)


Thanks,

Jay Cox

P.S. I do wonder if my message will even get to Björn Lisper.  His
mailserver apparently dumps anything sent with a yahoo.com in the From:
header.  (and unfortunately given how much spam comes from yahoo I can see
why).