Unpacking multi-type constructors

[Don Stewart]

Might be interesting to try the transformation manually and benchmark?

simonpj:
> Nice idea, but I’m not yet convinced that it would work well in practice.
> 
>  
> 
> First, there’s an exponential explosion in the number of constructors
> required.  Anything with an exponential is worrying.
> 
>  
> 
> Second, you presumably do not want massive code duplication.  So I assume that
> if you start with
> 
>  
> 
> case x of { Node i n2 n2) -> e
> 
>  
> 
> then you’ll desugar to something like this:
> 
>  
> 
>                 let fj i n1 n2 = e
> 
>                 in
> 
>                 case x of
> 
>                                 Node1 I -> fj i Nothing Nothing
> 
>                                 Node2 I n1 -> fj I (Just n1) Nothing
> 
>                                 … etc for other cases…
> 
>  
> 
> This doesn’t look like a win, because you end up allocating the (Just n1)
> things anyway! 
> 
>  
> 
> So maybe you want to *duplicate* e, so you generate
> 
>                 case x of
> 
>                                 Node1 I -> e[Nothing/n1, Nothing/n2]
> 
>                                 Node2 I n1 -> e[Just n1/n1, Nothing/n2]
> 
>                                 … etc for other cases…
> 
>  
> 
> But now you not only have an exponential number of branches: in each of those
> branches you duplicate an arbitrarily large expression e. That doesn’t look
> attractive to me.
> 
>  
> 
> Simon
> 
>  
> 
> From: glasgow-haskell-users-bounces at haskell.org
> [mailto:glasgow-haskell-users-bounces at haskell.org] On Behalf Of Louis Wasserman
> Sent: 21 July 2009 00:20
> To: glasgow-haskell-users at haskell.org
> Subject: Unpacking multi-type constructors
> 
>  
> 
> I think this is a feasible idea.  Whether this is in fact a good idea is an
> entirely separate question, however, and I want feedback.
> 
> Currently, I believe that an UNPACK pragma used on a multi-constructor type has
> no effect.  For example,
> 
> data Node = Node Int {-# UNPACK #-} !(Maybe Node) {-# UNPACK #-} !(Maybe Node)
> 
> is the same as
> 
> data Node = Node Int !(Maybe Node) !(Maybe Node)
> 
> What I'd like is for this to translate into four constructors, one for each
> combination of constructors for the UNPACK'd fields:
> 
> data Node = Node0 Int -- Nothing, Nothing
> 
> | Node1 Int Node -- Just, Nothing
> | Node2 Int Node -- Nothing, Just
> | Node3 Int Node Node -- Just, Just
> 
> The primary counterargument I can think of is that this can result in a
> single-constructor type being turned into a multi-constructor type, which runs
> the risk of interfering with GHC's sexcellent handling of single-constructor
> types.
> 
> The countercounterargument is, of course, that the {-# UNPACK #-} pragma
> already behaves differently depending on the single-constructorness of the
> underlying type, and that the obligation is already on the programmer to check
> such things.
> 
> For reference, could somebody point me to the place in GHC that currently takes
> care of {-# UNPACK #-} pragmas, so I could -- for instance -- figure out
> whether or not there's another reason that this idea isn't in place already?
> 
> Louis Wasserman
> wasserman.louis at gmail.com
> 

> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users