Generalising the demand analysis to sum types

[José Manuel Calderón Trilla]

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