2016-02-17 3:15 GMT-05:00 Joachim Breitner :

BTW, what is the status of https://ghc.haskell.org/trac/ghc/wiki/UnpackedSumTypes ?

It's mostly done, you can try it here: https://github.com/osa1/ghc/tree/unboxed-sums-stg

Hello again, The way I see it, the information would allow us to automatically unbox the arguments to constructors in sum types. For example, with a Maybe Int, you would be able to automatically unpack the Int within the Just constructor whenever the strictness analysis determines that a function is strict in Just's argument. Currently we can't determine any strictness greater than HeadStr for sum types, which would not give us this information (since HeadStr means it's only safe the evaluate up to the outermost constructor; 'Just' in this case). Combining this with the unboxed sums work, the idea is to be able to not only unbox the sum, but the fields of a constructor when possible, removing as many indirections as possible. At least, that's the plan :) Cheers, Jose On Wed, Feb 17, 2016 at 9:09 AM, Simon Peyton Jones wrote:

I think you could do that. The key question is (as someone asked) what use you would make of the information. That is, what's the payoff?

Simon

| -----Original Message----- | From: ghc-devs [mailto:ghc-devs-bounces@haskell.org] On Behalf Of José | Manuel Calderón Trilla | Sent: 17 February 2016 04:50 | To: ghc-devs@haskell.org | Subject: Generalising the demand analysis to sum types | | Hello ghc-devs, | | Apologies for the longish email. | | I'm looking to generalise GHC's demand analysis to work on sum types. | This is in connection with the work on unboxed sums. The idea is that | if the strictness analysis tells us that a sum type is strict in all | the fields of all of its constructors, it is safe to unbox that sum | automatically. We hope for this to feed into a worker/wrapper like | transformation for sum types. | | I am new to the GHC codebase and wanted to make sure that my plan of | attack seemed sensible to you all. | | GHC's current type representing demand is StrDmd, which is defined as | follows: | | data StrDmd | = HyperStrict | | SCall StrDmd | | SProd [ArgStr] | | HeadStr | | I believe that adding sum types will be as simple as adding a single | new constructor for Sums: | | data StrDmd | = HyperStrict | | SCall StrDmd | | SProd [ArgStr] | | SSum [(Tag, StrDmd)] | | HeadStr | | We need the constructor tag so that we can analyze each branch of a | case expression independently before combining the results of each | branch. Since we only care if all fields are strict for all | constructors, we won't actually use the tag information except in the | analysis itself. | | Projection-based strictness analysis on sum types is not new (though | sum types + higher-order seems to be). That being said, all previous | treatments of the subject that I'm aware of forbid polymorphic | recursion. Luckily for us we aren't trying to unbox recursive types, so | for now [1] we will not attempt to analyze recursive types, hence no | SMu or SRec constructor above. | | With the analysis accepting sum types we will be able to analyze | functions with sum types as parameters, as a trivial example: | | fromMaybe2 x y = case x of | Just v -> v | Nothing -> y | | You would get a demand signature like: | | Str=Dmdtype ), ("Nothing", <>)],U> | | Which says that the function is strict in its first argument and that | if the value is a 'Just' then its field is used strictly, if the value | is a 'Nothing' then there is no further demand (a nullary product). | | For those with more experience in these matter, does this seem to be a | sensible approach? | | Thanks in advance for any insight, | | Jose | | | [1]: Those of you who saw my Haskell Symposium talk on implicit | parallelism last year might remember that we will need the analysis to | work on recursive types in order to automatically generate parallel | strategies, but that's for later (I've spoken with Ilya Sergey about | working on that). | _______________________________________________ | ghc-devs mailing list | ghc-devs@haskell.org | https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fmail.ha | skell.org%2fcgi-bin%2fmailman%2flistinfo%2fghc- | devs&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7cf731333e0c5d45f3 | 298408d33755dc98%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=hWHFSUVrr | ZQqTPeQsFMQVlveHgV5ozx6%2bdpsylRIwhg%3d

OK yes, once we have unboxed sums, then we can in principle at least, do worker/wrapper on arguments of sum type. So then we need strictness analysis on sumtypes, for which your proposed extension of StrDmd looks plausible. Don't forget AbsDmd too! Do start a wiki page to explain all this. Simon | -----Original Message----- | From: José Manuel Calderón Trilla [mailto:jmct@jmct.cc] | Sent: 20 February 2016 23:02 | To: Simon Peyton Jones ; Joachim Breitner | ; Ömer Sinan Ağacan | Cc: ghc-devs@haskell.org | Subject: Re: Generalising the demand analysis to sum types | | Hello again, | | The way I see it, the information would allow us to automatically unbox | the arguments to constructors in sum types. | | For example, with a Maybe Int, you would be able to automatically | unpack the Int within the Just constructor whenever the strictness | analysis determines that a function is strict in Just's argument. | Currently we can't determine any strictness greater than HeadStr for | sum types, which would not give us this information (since HeadStr | means it's only safe the evaluate up to the outermost constructor; | 'Just' in this case). | | Combining this with the unboxed sums work, the idea is to be able to | not only unbox the sum, but the fields of a constructor when possible, | removing as many indirections as possible. | | At least, that's the plan :) | | Cheers, | | Jose | | | On Wed, Feb 17, 2016 at 9:09 AM, Simon Peyton Jones | wrote: | > I think you could do that. The key question is (as someone asked) | what use you would make of the information. That is, what's the | payoff? | > | > Simon | > | > | -----Original Message----- | > | From: ghc-devs [mailto:ghc-devs-bounces@haskell.org] On Behalf Of | > | José Manuel Calderón Trilla | > | Sent: 17 February 2016 04:50 | > | To: ghc-devs@haskell.org | > | Subject: Generalising the demand analysis to sum types | > | | > | Hello ghc-devs, | > | | > | Apologies for the longish email. | > | | > | I'm looking to generalise GHC's demand analysis to work on sum | types. | > | This is in connection with the work on unboxed sums. The idea is | > | that if the strictness analysis tells us that a sum type is strict | > | in all the fields of all of its constructors, it is safe to unbox | > | that sum automatically. We hope for this to feed into a | > | worker/wrapper like transformation for sum types. | > | | > | I am new to the GHC codebase and wanted to make sure that my plan | > | of attack seemed sensible to you all. | > | | > | GHC's current type representing demand is StrDmd, which is defined | > | as | > | follows: | > | | > | data StrDmd | > | = HyperStrict | > | | SCall StrDmd | > | | SProd [ArgStr] | > | | HeadStr | > | | > | I believe that adding sum types will be as simple as adding a | > | single new constructor for Sums: | > | | > | data StrDmd | > | = HyperStrict | > | | SCall StrDmd | > | | SProd [ArgStr] | > | | SSum [(Tag, StrDmd)] | > | | HeadStr | > | | > | We need the constructor tag so that we can analyze each branch of | a | > | case expression independently before combining the results of each | > | branch. Since we only care if all fields are strict for all | > | constructors, we won't actually use the tag information except in | > | the analysis itself. | > | | > | Projection-based strictness analysis on sum types is not new | > | (though sum types + higher-order seems to be). That being said, | all | > | previous treatments of the subject that I'm aware of forbid | > | polymorphic recursion. Luckily for us we aren't trying to unbox | > | recursive types, so for now [1] we will not attempt to analyze | > | recursive types, hence no SMu or SRec constructor above. | > | | > | With the analysis accepting sum types we will be able to analyze | > | functions with sum types as parameters, as a trivial example: | > | | > | fromMaybe2 x y = case x of | > | Just v -> v | > | Nothing -> y | > | | > | You would get a demand signature like: | > | | > | Str=Dmdtype ), ("Nothing", <>)],U> | > | | > | Which says that the function is strict in its first argument and | > | that if the value is a 'Just' then its field is used strictly, if | > | the value is a 'Nothing' then there is no further demand (a | nullary product). | > | | > | For those with more experience in these matter, does this seem to | > | be a sensible approach? | > | | > | Thanks in advance for any insight, | > | | > | Jose | > | | > | | > | [1]: Those of you who saw my Haskell Symposium talk on implicit | > | parallelism last year might remember that we will need the analysis | > | to work on recursive types in order to automatically generate | > | parallel strategies, but that's for later (I've spoken with Ilya | > | Sergey about working on that). | > | _______________________________________________ | > | ghc-devs mailing list | > | ghc-devs@haskell.org | > | | > | | https://na01.safelinks.protection.outlook.com/?url=http%3a%2f%2fmail | > | .ha | > | skell.org%2fcgi-bin%2fmailman%2flistinfo%2fghc- | > | | > | | devs&data=01%7c01%7csimonpj%40064d.mgd.microsoft.com%7cf731333e0c5d4 | > | 5f3 | > | | 298408d33755dc98%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=hWHFSU | > | Vrr ZQqTPeQsFMQVlveHgV5ozx6%2bdpsylRIwhg%3d

| current thought is that you collect the usage demands on the fields of | the constructor for the alternative you're analysing (let's say it's | tag 1) and insert that into a USum where the usage demands on all the | other constructors (all the tags except 1) is UHead. I'm not sure you really need that. You could instead say that USum xs implies at least UHead on all the other tags not mentioned in xs. Simon | -----Original Message----- | From: José Manuel Calderón Trilla [mailto:jmct@jmct.cc] | Sent: 03 March 2016 04:53 | To: Simon Peyton Jones | Cc: Joachim Breitner ; Ömer Sinan Ağacan | ; ghc-devs@haskell.org | Subject: Re: Generalising the demand analysis to sum types | | Hello again, | | On Tue, Mar 1, 2016 at 11:56 AM, Simon Peyton Jones | wrote: | > | > Don't forget AbsDmd too! | > | | Yes, we're working on this too. Currently we're doing something | analogous to what we're doing with StrDmd: | | data UseDmd | = UCall Count UseDmd | | UProd [ArgUse] | | USum [(Tag, UseDmd)] | | UHead | | Used | | The big question deals with how to 'insert' a usage demand on an | alternative of a case into a usage demand on the entire sum. The | current thought is that you collect the usage demands on the fields of | the constructor for the alternative you're analysing (let's say it's | tag 1) and insert that into a USum where the usage demands on all the | other constructors (all the tags except 1) is UHead. The rational | behind using UHead is that the constructor itself is demanded at UHead | by the case expression. Once you have one of these for every | alternative, you lub them together appropriately, so anywhere you | actually used a field would be represented in the final demand on the | sum since UHead `lubUse` u = u | | | > Do start a wiki page to explain all this. | > | | Definitely. | | Cheers, | | Jose