2011/2/7 Richard O'Keefe
On 8/02/2011, at 3:47 AM, Gábor Lehel wrote:
I dunno. As a language extension, would - let's call it BangTypes - be backwards-incompatible in any way?
Let's look at an intermediate step first, BangFunctions.
What this does is to say that there are two versions of "->":
t1 -> t2
What we have right now, which might be evaluated or not.
!t1 -> t2
The function wants its argument evaluated. Suppose f is a value of this type. Then a use of f is rather like a use of (\x -> x `seq` f x) and we can already write that.
Now if you write
f :: !t1 -> t2 f p1 = e1 ... f pn = en
you're making the function strict whether it would have been strict or lazy. But again, with BangPatterns we can already do that:
f !(p1) = e1 ... f !(pn) = en
The advantage of BangPatterns is that they can be precisely and selectively located.
The advantages of BangFunctions include - the forced strictness is part of the function's (published) *interface*, not its implementation - the question of what happens if some patterns for an argument are banged and some are not does not arise (I *think* that this can avoid some mistakes) - it's compatible with BangTypes but simpler.
So in some sense there is (now) nothing new here *except* putting the information where people can easily see it.
Perhaps the compiler could even do inference, showing bangs on those parameters in which the function is (detectably) always strict? This vaguely reminds me of type elaboration in Disciple (at least, that's where I encountered it), in that even if you manually supply a type signature for your function as Foo -> Bar without bangs, if in practice it is strict in the Foo parameter, the type is actually !Foo -> Bar. And presumably the compiler could infer that -- the strictness properties are orthogonal in a sense to the rest of the type, so underspecifying them is not an error, and the compiler could fill the additional information in automatically where available. (Again this is only if evaluation were to happen implicitly where required by the types, so that !Foo -> Bar would equivalently mean "applying this function to the argument results in the argument being evaluated" whether the bang was supplied or inferred.) Is there any sensible meaning for bangs on return types? I've been trying to think this through but not necessarily succeeding. Perhaps instead of all this inquiring and conjecturing it might be easier to just read up on how Clean does it... :-)
BangTypes could be rather more complicated. Clean 2 offers lazy, head strict spine lazy, head lazy spine strict, head and spine strict, head unboxed spine lazy, head unboxed spine strict for lists, which are all different types; it also offers strictness-polymorphic lists. I never actually made use of this because having so many kinds of list made my head spin. Roughly speading, Clean 1 had BangFunctions, Clean 2 BangTypes.
This does seem a bit excessive. As a start, I don't remember anyone asking for control over (un)boxedness, so hopefully we could jettison that part of it? The dichotomy between head-strict (WHNF) and spine-strict seems potentially more meaningful though. I could easily imagine wanting to specify a type as being WHNF (so as to avoid accumulating thunks) while still allowing it to be spine-lazy; are there any use cases for the reverse, not-necessarily-evaluated but spine-strict-once-evaluated? If there aren't, we could use ! for head-strict, and !! for both head- and spine-strict (to borrow syntax I saw proposed for 'hyperstrictness' somewhere). Maybe this is still more complexity than desirable (ideally there would be only !...), but the problems with insufficient predictability of and control over evaluation seem very real, so if (_if_) this would go a significant way towards alleviating that problem (in particular not having to duplicate code N times for each desired combination of strictness and laziness in container classes seems like it would be a win), then maybe the extra complexity would be worth it.
One of the things that makes me wary of BangPatterns is that it seems as though it's headed in a BangTypes kind of direction.
Oh, by the way, I got the Clean syntax wrong. ![a] means "lazy list evaluated to WHNF"; [a!] means "value is spine strict".
-- Work is punishment for failing to procrastinate effectively.