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:[email protected]] | Sent: 20 February 2016 23:02 | To: Simon Peyton Jones <[email protected]>; Joachim Breitner | <[email protected]>; Ömer Sinan Ağacan <[email protected]> | Cc: [email protected] | 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 | <[email protected]> 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:[email protected]] On Behalf Of | > | José Manuel Calderón Trilla | > | Sent: 17 February 2016 04:50 | > | To: [email protected] | > | 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 <S[("Just", <S,U>), ("Nothing", <>)],U><L,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 | > | [email protected] | > | | > | | 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 _______________________________________________ ghc-devs mailing list [email protected] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
