[Haskell-cafe] Byte Histogram

[Gábor Lehel]

2011/2/7 Richard O'Keefe <ok at cs.otago.ac.nz>:
>
> 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.