Retro-Haskell: can we get seq somewhat under control?

David Feuer david.feuer at gmail.com
Thu Dec 22 05:13:37 UTC 2016


I don't want to actually put the dictionary there. I want to *pretend* to
put the dictionary there. In testing mode, I want to be able to "take one
out" by making it out of whole cloth; in production mode I want to just
assume there are no bottoms in the constraints and never ever make the
dictionaries. But this all is probably better discussed on the existing
proposal, now that I know it exists. There are some considerable
complications raised there.

On Dec 21, 2016 11:55 PM, "Edward Kmett" <ekmett at gmail.com> wrote:

> Actually, if you go back to the original form of Seq it would translate to
>
> data Seq a => Foo a = Foo !Int !a
>
> which requires resurrecting DatatypeContexts, and not
>
> data Foo a = Seq a => Foo !Int !a
>
> The former requires Seq to call the constructor, but doesn't pack the
> dictionary into the constructor. The latter lets you get the dictionary out
> when you pattern match on it. meaning it has to carry the dictionary around!
>
> Unfortunately, non-trivial functionality is lost. With the old
> DatatypeContext translation you can't always unpack and repack a
> constructor. Whereas with a change to an existential encoding you're
> carrying around a lot of dictionaries in precisely the structures that
> least want to carry extra weight.
>
> Both of these options suck relative to the status quo for different
> reasons.
>
> -Edward
>
> On Wed, Dec 21, 2016 at 2:14 PM, Index Int <vlad.z.4096 at gmail.com> wrote:
>
>> There's a related GHC Proposal:
>> https://github.com/ghc-proposals/ghc-proposals/pull/27
>>
>> On Wed, Dec 21, 2016 at 10:04 PM, David Feuer <david.feuer at gmail.com>
>> wrote:
>> > In the Old Days (some time before Haskell 98), `seq` wasn't fully
>> > polymorphic. It could only be applied to instances of a certain class.
>> > I don't know the name that class had, but let's say Seq. Apparently,
>> > some people didn't like that, and now it's gone. I'd love to be able
>> > to turn on a language extension, use an alternate Prelude, and get it
>> > back. I'm not ready to put up a full-scale proposal yet; I'm hoping
>> > some people may have suggestions for details. Some thoughts:
>> >
>> > 1. Why do you want that crazy thing, David?
>> >
>> > When implementing general-purpose lazy data structures, a *lot* of
>> > things need to be done strictly for efficiency. Often, the easiest way
>> > to do this is using either bang patterns or strict data constructors.
>> > Care is necessary to only ever force pieces of the data structure, and
>> > not the polymorphic data a user has stored in it.
>> >
>> > 2. Why does it need GHC support?
>> >
>> > It would certainly be possible to write alternative versions of `seq`,
>> > `$!`, and `evaluate` to use a user-supplied Seq class. It should even
>> > be possible to deal with strict data constructors by hand or
>> > (probably) using Template Haskell. For instance,
>> >
>> > data Foo a = Foo !Int !a
>> >
>> > would translate to normal GHC Haskell as
>> >
>> > data Foo a = Seq a => Foo !Int !a
>> >
>> > But only GHC can extend this to bang patterns, deal with the
>> > interactions with coercions, and optimize it thoroughly.
>> >
>> > 3. How does Seq interact with coercions and roles?
>> >
>> > I believe we'd probably want a special rule that
>> >
>> > (Seq a, Coercible a b) => Seq b
>> >
>> > Thanks to this rule, a Seq constraint on a type variable shouldn't
>> > prevent it from having a representational role.
>> >
>> > The downside of this rule is that if something *can* be forced, but we
>> > don't *want* it to be, then we have to hide it a little more carefully
>> > than we might like. This shouldn't be too hard, however, using a
>> > newtype defined in a separate module that exports a pattern synonym
>> > instead of a constructor, to hide the coercibility.
>> >
>> > 4. Optimize? What?
>> >
>> > Nobody wants Seq constraints blocking up specialization. Today, a
>> function
>> >
>> > foo :: (Seq a, Foldable f) => f a -> ()
>> >
>> > won't specialize to the Foldable instance if the Seq instance is
>> > unknown. This is lousy. Furthermore, all Seq instances are the same.
>> > The RTS doesn't actually need a dictionary to force something to WHNF.
>> > The situation is somewhat similar to that of Coercible, *but more so*.
>> > Coercible sometimes needs to pass evidence at runtime to maintain type
>> > safety. But Seq carries no type safety hazard whatsoever--when
>> > compiling in "production mode", we can just *assume* that Seq evidence
>> > is valid, and erase it immediately after type checking; the worst
>> > thing that could possibly happen is that someone will force a function
>> > and get weird semantics. Further, we should *unconditionally* erase
>> > Seq evidence from datatypes; this is necessary to maintain
>> > compatibility with the usual data representations. I don't know if
>> > this unconditional erasure could cause "laziness safety" issues, but
>> > the system would be essentially unusable without it.
>> >
>> > 4. What would the language extension do, exactly?
>> >
>> > a. Automatically satisfy Seq for data types and families.
>> > b. Propagate Seq constraints using the usual rules and the special
>> > Coercible rule.
>> > c. Modify the translation of strict fields to add Seq constraints as
>> required.
>> >
>> > David Feuer
>> > _______________________________________________
>> > ghc-devs mailing list
>> > ghc-devs at haskell.org
>> > http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>> _______________________________________________
>> ghc-devs mailing list
>> ghc-devs at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20161222/c900d3d1/attachment.html>


More information about the ghc-devs mailing list