Generalising the demand analysis to sum types

[Simon Peyton Jones]

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%7cf731333e0c5d45f3
|  298408d33755dc98%7c72f988bf86f141af91ab2d7cd011db47%7c1&sdata=hWHFSUVrr
|  ZQqTPeQsFMQVlveHgV5ozx6%2bdpsylRIwhg%3d