Generalising the demand analysis to sum types

[Simon Peyton Jones]

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 at jmct.cc]
|  Sent: 20 February 2016 23:02
|  To: Simon Peyton Jones <simonpj at microsoft.com>; Joachim Breitner
|  <mail at joachim-breitner.de>; Ömer Sinan Ağacan <omeragacan at gmail.com>
|  Cc: ghc-devs at 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
|  <simonpj at microsoft.com> 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 at haskell.org] On Behalf Of
|  > | José  Manuel Calderón Trilla
|  > |  Sent: 17 February 2016 04:50
|  > |  To: ghc-devs at 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 <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
|  > |  ghc-devs at 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