`th-deepstrict`: enforcing deep strictness of datatypes using TH

[TeofilC]

th-deepstrict is a library for enforcing (at compile time) that datatypes are deep strict. Deep strictness allows us to guarantee that evaluating a structure evaluates all thunks in all subparts of the structure. This gives us strong guarantees that a type cannot cause a space leak through excessive laziness.

Take a look at the announcement post for more details:

th-deepstrict

[atravers]

From the Existing tools section:

We say that a type is strict if evaluating that type means no fields are thunks. A type is then deep strict if it is strict and the types of all of its fields are deep strict. In other words, a type is deep strict if evaluating it means that it does not contain any thunks (even transitively).

So what’s the difference between (being) “deep-strict” and hyperstrict?

[TeofilC]

Indeed those definitions look to be equivalent though hyperstrict has a different meaning in the context of GHC’s demand analysis

[atravers]

Using ghc demand analysis hyperstrict as a search term finds this (draft) article: Theory and Practice of Demand Analysis in Haskell (2017) - from section 6.3 on page 21 of 34:

We consider a distinguished projection H, such that H d ≡ ↯ for any d. It is convenient to model a hyperstrict demand. The demand H can be placed on the value d before S if evaluation of d is guaranteed to diverge.

The sentence:

evaluation of d is guaranteed to diverge

would be correct where:

• d = f x
• f is a hyperstrict function
• and ⊥ is a sub-expression of x

So is there another place or article I should be looking at?

[TeofilC]

No that’s right that’s the sense that is used in GHC’s demand analysis.

My understanding is that the sense here of a hyperstrict function is one like:

foo _ = undefined

where we are guaranteed to diverge. Rather than one where we evaluate an argument to normal form.

In any case this is somewhat unrelated to th-deepstrict

[atravers]

Some time ago I suggested adding a primitive hyperstrict-evaluator function to Haskell:

compel :: a -> a

So when I first saw your announcement, I immediately wondered “is that suggestion now redundant?” (perhaps along with deepseq et al ), hence the questions.

[TeofilC]

That makes sense!
I think such a thing would still be helpful, but you can get something similar with this library.
If you use assertDeepStrict on a type and then force it to WHNF then you will end up with something in NF. Of course there’s still types that can’t be deepstrict/hyperstrict, so there’s still a use case for things like deepseq/compel

[tomjaguarpaw]

I love this idea. Thanks for writing the library and the explanation! I hope it will appear on Hackage soon.

[TeofilC]

This is now released on Hackage: th-deepstrict: Check that datatypes are deep strict using Template Haskell.

[tomjaguarpaw]

Great to see this available to all. Sadly it doesn’t work with strict-wrapper due to “The majority of data/type families are currently not supported”.

{-# LANGUAGE TemplateHaskell #-}

import Language.Haskell.TH.DeepStrict
import Data.Strict.Wrapper

$(assertDeepStrict =<< [t| Strict ((), ()) |])

[TeofilC]

Thanks for trying it out! I didn’t have a good reason to add proper support for type families before. I’ll give it a go now.

[TeofilC]

@tomjaguarpaw I’ve uploaded a version to Hackage that should () support data/type families. Let me know if you run into any issues.

th-deepstrict

Support data and type families

[tomjaguarpaw]

Wow, that’s great, thanks! This now works as expected:

{-# LANGUAGE TemplateHaskell #-}

import Language.Haskell.TH.DeepStrict
import Data.Strict.Wrapper

$(assertDeepStrict =<< [t| Strict (Strict (Maybe ()), ()) |])
-- Fine


$(assertDeepStrict =<< [t| Strict (Maybe (), ()) |])
-- Error