# State monad - memory exhausted

**URL:** <https://discourse.haskell.org/t/state-monad-memory-exhausted/8602>\
**Category:** Uncategorized\
**Created:** [January 19, 2024, 8:46pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602 "2024-01-19T20:46:37Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![sgraf](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/sgraf/32/392_2.png) [@sgraf](https://discourse.haskell.org/u/sgraf)\
**Post date:** [January 21, 2024, 1:08pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/21 "2024-01-21T13:08:39Z")

</div>

Just a few notes while skimming the thread:

> > Tangentially, I never understood why GHC can’t rewrite functions to `go` form by itself.
> 
> You can enable it manually with [`-fstatic-argument-transformation`](https://downloads.haskell.org/ghc/9.8.1/docs/users_guide/using-optimisation.html#ghc-flag--fstatic-argument-transformation) (although for some reason it doesn’t seem to work in this case) . If the function is not inlined then it will a have to allocate a closure for that `go` function. @sgraf is working on improving it though. I believe the latest idea was to only apply this transformation if it makes it possible to inline the function.

Yes, there’s [#18962: SAT should only influence the unfolding · Issues · Glasgow Haskell Compiler / GHC · GitLab](https://gitlab.haskell.org/ghc/ghc/-/issues/18962) and the prototype in [!4553: WIP: SAT: Attach SAT'd definition as INLINABLE unfolding · Merge requests · Glasgow Haskell Compiler / GHC · GitLab](https://gitlab.haskell.org/ghc/ghc/-/merge_requests/4553). Sadly, I continually lack the time and priority to fix the (conceptually unrelated) regressions it introduces. If I were to implement GHC on a green field, this would definitely have been the way I’d have implmented SAT in the first place.

> Kind of, but I think in most cases the thunks are forced rather quickly and no leak occurs. So you’d get a lot of false positives. Edsko de Vries from Well-Typed has written the `nothunks` library which can give warnings if there are thunks in your code: [Being lazy without getting bloated - Well-Typed: The Haskell Consultants](https://well-typed.com/blog/2020/09/nothunks/).

Edit: I confused `nothunks` with the purported `noupdate` primitive/Edsko’s `dupIO` package. `nothunks` seems like an adequate runtime verification procedure, but a static anlysis would far more helpful. I’ll leave the following 2 paras untouched, but bear in mind that they relate to omitting of update frames with `noupdate`.

Note that in this case, the _closure_ of the thunk retains the chain of `+ 1`s. I’d hypothesize that omitting the update frame here would not improve anything because that thunk is never evaluated before memory runs out.

And _if_ it were evaluated multiple times, I’d rather have updated to a `I# 9000#` than retain the chain of closures for the next eval… That would be an example where `nothunk`/`noupdate` would make things worse.

> Do you think it is acceptable, that ghc provides no warning (albeit noisy), of this situation occuring?

I don’t think it’s acceptable, but I wouldn’t pin it on GHC, either.  
But perhaps a linter like `hlint` could implement a pass that warns about these situations, or flags places where a thunk/data structure is retained over a potentially very long function call.  
Alas, my interests are as expansive as my time to pursue them (e.g., during my PhD) is finite.  
Perhaps someone else would be interested in writing such a static analysis; I think we could get really cool results quite fast. Definitely worth a publication.

---

<div class="post-metadata">

**Author:** ![ajbarber](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/ajbarber/32/2648_2.png) [@ajbarber](https://discourse.haskell.org/u/ajbarber)\
**Post date:** [January 21, 2024, 1:43pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/22 "2024-01-21T13:43:59Z")

</div>

> [@sgraf](#):
>
> , but I wouldn’t pin it on GHC, either.

Why is that? (Post must be 20 chars).

---

<div class="post-metadata">

**Author:** ![sgraf](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/sgraf/32/392_2.png) [@sgraf](https://discourse.haskell.org/u/sgraf)\
**Post date:** [January 21, 2024, 4:14pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/23 "2024-01-21T16:14:15Z")

</div>

It’s fair to expect GHC to produce warnings if it fits into its compilation pipeline. But above I sketched an entirely new static analysis that is not relevant to compilation in any way, yet requires its own pass (multiple, probably) over the whole program. There’s no reason to burden development and every run of the compiler with this overhead; rather I’d expect some kind of static analysis tool to be run (perhaps nightly) by CI. That’s good: Such a tool (`hlint`, `stan` or a Core plugin) is not subject to the same stability requirements as GHC.

GHC has (semantic, hence non-trivial) analyses which are non-essential to compilation such as pattern-match coverage checking. But that analysis fits quite neatly into the structure of the desugaring pass. Even then, for some complicated test inputs you can observe a significant drop in compilation performance entirely due to coverage checking. I suggest we do not add to that.

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [January 22, 2024, 12:54am UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/24 "2024-01-22T00:54:37Z")

</div>

> [@](#):
>
> Everybody complains about the weather, but nobody does anything about it.
> 
> Charles Dudley Warner

- 

> [@](#):
>
> [hasufell:](http://discourse.haskell.org/t/the-strengths-of-haskell-42-strengths-listed-so-far/3347/6)
> 
> > Lazy Evaluation […]
> 
> Is a great source of space leaks […]

- 

> [@](#):
>
> [limazy:](http://discourse.haskell.org/t/statet-performance-benchmarks/7439/14)
> 
> Space-leaking monad transformers have been a huge gripe of mine traditionally; i.e, Haskell really emphasizes its monads and unperformant monads with huge performance penalties are somewhat embarrassing.

- 

> [@](#):
>
> [ReleaseCandidate:](http://discourse.haskell.org/t/why-is-haskell-good-for-compiler-development/7567/4)
> 
> […] Haskell’s problems (two non-working package managers, slow compiler, higher memory usage, space leaks, buggy LSP).

- 

> [@](#):
>
> [danidiaz:](http://discourse.haskell.org/t/haskell-implementors-workshop-2023-individual-talk-videos-on-youtube/8221/2)
> 
> […] laziness still plagues the Haskell heap!

- 

> [@](#):
>
> [tomjaguarpaw:](http://discourse.haskell.org/t/state-monad-memory-exhausted/8602/20)
> 
> So what exactly do I find unacceptable? Our ecosystem has 100 laziness footguns, `foldl`, `modifyIORef`, `Control.Monad.Trans.State.Strict.modify`, all of `Control.Monad.Trans.State` (i.e. not `.Strict`), all of `Data.Map.Lazy`, … .

…amongst others, here and elsewhere! But as it happens, maybe something can be done ~~_about the weather_~~ :

- [The Halting Problem Does Not Matter](https://academic.oup.com/comjnl/article-pdf/27/4/376/948588/270376.pdf) (1984)

If the observations made in those articles:

1. can be verified for the halting problem,

2. then extended to [Rice’s theorem](https://web.archive.org/web/20181222211221/https://people.cs.aau.dk/~hans/ANoteOnRicesTheorem.pdf),

it could be possible to _“have it all”_. Otherwise:

- [On Inter-deriving Small-step and Big-step Semantics: A Case Study for Storeless Call-by-need Evaluation](http://www.zerny.dk/danvy-al-tcs12.pdf) (2011).

…or revitalising Robert Ennal’s previous work:

- [Optimistic evaluation: an adaptive evaluation strategy for non-strict programs.](https://web.archive.org/web/20130610122750/https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.9.9901&rep=rep1&type=pdf) (2003).

---

<div class="post-metadata">

**Author:** ![ajbarber](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/ajbarber/32/2648_2.png) [@ajbarber](https://discourse.haskell.org/u/ajbarber)\
**Post date:** [January 22, 2024, 8:00am UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/25 "2024-01-22T08:00:29Z")

</div>

So performance reasons essentially? Comparing to C, `gcc -fanalyzer` is expensive, but opt in.

[https://gcc.gnu.org/onlinedocs/gcc-13.2.0/gcc/Static-Analyzer-Options.html](https://gcc.gnu.org/onlinedocs/gcc-13.2.0/gcc/Static-Analyzer-Options.html)

---

<div class="post-metadata">

**Author:** ![sgraf](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/sgraf/32/392_2.png) [@sgraf](https://discourse.haskell.org/u/sgraf)\
**Post date:** [January 22, 2024, 9:00am UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/26 "2024-01-22T09:00:17Z")

</div>

Yes, perf and stability. Personal opinion: Contributing to GHC, fulfilling as it might be, has lost quite a bit of momentum in recent years due to maturity of the project, multiplied with the churn introduced by such a large code base.

---

<div class="post-metadata">

**Author:** ![doyougnu](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/doyougnu/32/2248_2.png) [@doyougnu](https://discourse.haskell.org/u/doyougnu)\
**Post date:** [January 24, 2024, 8:54pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/27 "2024-01-24T20:54:08Z")

</div>

> Edsko de Vries from Well-Typed has written the `nothunks` library which can give warnings if there are thunks in your code:

`nothunks` is great and I’m happy to have it, but IMHO its using the typeclass system to overcome a feature deficiency in GHC. If I could have my way, I would transform `nothunk` uses into `Unlifted` types. This way the my types just feel cleaner because `Foo :: a` isn’t masquerading as something (a thing that can be a thunk, and therefore includes \bot) as something that it isn’t (a thing that does not contain \bot as a value). So I would find this approach cleaner because I have type level witnesses instead of typeclass constraints that serve as witnesses. I guess I should help @jaror improving the ergonomics of `Unlifted`.

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [January 24, 2024, 9:09pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/28 "2024-01-24T21:09:10Z")

</div>

What about extending the use of strictness annotations to type signatures?

```haskell
foo :: !T
foo = ...

```

---

<div class="post-metadata">

**Author:** ![sgraf](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/sgraf/32/392_2.png) [@sgraf](https://discourse.haskell.org/u/sgraf)\
**Post date:** [January 25, 2024, 9:30pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/29 "2024-01-25T21:30:32Z")

</div>

Would you expect this to type-check?

```haskell
xs :: [!Int]
xs = map (+ 1) [error "blah"]

```

If so, what code would you generate for `Data.List.map`?

Essentially, `!` in type signature is just syntactic sugar for a zero cost coercion into `UnliftedType` kind, and it is not entirely trivial to embrace that in our compilation pipeline.

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [January 27, 2024, 7:57am UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/30 "2024-01-27T07:57:40Z")

</div>

> […] what code would you generate […]?

Something like the code that presumably would be generated for:

```haskell
xs :: [Int]
xs = map (+ 1) [error "blah"]

```

when using `-XStrict` in GHC.

* * *

> [@](#):
>
> Essentially, `!` in type signature is just syntactic sugar for a zero cost coercion into `UnliftedType` kind, and it is not entirely trivial to embrace that in our compilation pipeline.

Well, you could try approaching the problem from the _“other direction”_ :

[Lazy Evaluation for the Lazy: Automatically Transforming Call-by-Value into Call-by-Need](https://homepages.dcc.ufmg.br/~fernando/publications/papers/CC23_Breno.pdf) (2023)

---

<div class="post-metadata">

**Author:** ![sgraf](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/sgraf/32/392_2.png) [@sgraf](https://discourse.haskell.org/u/sgraf)\
**Post date:** [January 27, 2024, 10:08am UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/31 "2024-01-27T10:08:20Z")

</div>

> [@atravers](#):
>
> when using `-XStrict` in GHC.

But `map` has not been compiled with `-XStrict`, so it won’t evaluate the list cells it returns.  
Hence `[!Int]` (which to me says “When you evalute to `(x:_)::[!Int]`, then `x` is also evaluated”) would be very misleading, because that is not at all what is guaranteed by what is returned by `map`.

The solution is that you need two versions of `map`: one that you call when the list cells are “lazy” (lifted) and one in which the list cells are “strict” (unlifted). With that in mind, `map` is actually pretty much an overloaded function. Of course, we wouldn’t want to pay for overloading, so we’d probably specialise every “levity polymorphic” function. But `map` has type `forall a b. (a -> b) -> [a] -> [b]` and we so far have only discussed levity polymorphism in `b`. What about levity polymorphism in `a`? That would lead to 4 specialisations for the same `map` function. Fortunately, it is OK to simply presume that `a` is lifted and insert an eval just in case (think of `UnliftedType` as a subtype of `LiftedType` with a zero-cost coercion), so 2 specialisations suffice, but that is not true in general and you can see why this doesn’t scale.

All that to say: It’s not as simple as “proposing” `!` in types; that’s merely a piece of syntax without a specification of its non-compositional semantics.

Incidentally, we could make `[]` levity polymorphic today, e.g. `[] :: forall (l::Levity). TYPE (BoxedRep l) -> LiftedType`. This `l` defaults to `Lifted` anywhere it can’t be inferred, that would mean most written code out there should keep compiling. So actually we could write `[!Int]` as `[Strict Int]`, where `Strict :: LiftedType -> UnliftedType` such as in [Data.Elevator](https://hackage.haskell.org/package/data-elevator-0.1.0.1/docs/Data-Elevator.html#t:Strict). So `!a` could just be syntactic sugar today, for `Strict Int`. But that does not help, because we can’t reuse all the existing definitions working just on the lifted variant of `map`.

While some functions, such as `foldr`, can easily be made levity polymorphic in the list element type parameter without requiring separate specialisations (`foldl'` even in both type params, I think, [#15532: Relaxing Levity-Polymorphic Binder Check for Lifted vs Unlifted pointers · Issues · Glasgow Haskell Compiler / GHC · GitLab](https://gitlab.haskell.org/ghc/ghc/-/issues/15532)), in other cases such as `map` we can’t get around to generating twice the amount of code (or suffer from unknown calls to a dictionary carrying around the implementation of `seq` (unlifted) / `flip const` (lifted)). I argue that we’d require opt-in from the user to do so via a change in the type signature (`map :: LevPoly l => forall a (b::TYPE (BoxedRep l)). (a -> b) -> [a] -> [b]`).

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [January 27, 2024, 3:46pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/32 "2024-01-27T15:46:24Z")

</div>

> But `map` has not been compiled with `-XStrict`, so it won’t evaluate the list cells it returns.

It shouldn’t need to - the call to `map` would be _“strictness-lifted”_ by the implementation implicitly to provide that strict version of `map`, in a similar fashion to how e.g. the strict `Complex a` constructor `(:+)` is really a lazy constructor which has been _“strictness-lifted”_ through the use of extra calls for evaluating its components.

* * *

> All that to say: […]

…people are being annoyed by _“type acrobatics”_ :

- `Monad`, I Love You […] (2022)  
`https://www.youtube.com/watch?v=2PxsyWqZ5dI`

> [@](#):
>
> Dijkstra used to say “beauty is our business”, to which I would add that life is too short, and bright minds too precious, to waste on ugly things.
> 
> [Robert Harper](https://existentialtype.wordpress.com/2011/04/16/modules-matter-most)

---

<div class="post-metadata">

**Author:** ![BurningWitness](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/burningwitness/32/3665_2.png) [@BurningWitness](https://discourse.haskell.org/u/BurningWitness)\
**Post date:** [January 27, 2024, 3:54pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/33 "2024-01-27T15:54:07Z")

</div>

> [@atravers](#):
>
> the call to `map` would be _“strictness-lifted”_ by the implementation implicitly to provide that strict version of `map`

Wouldn’t that mean every function needs to have 2args versions for each choice of levity downstream? Isn’t proper levity polymorphism support a way more straightforward solution at that point?

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [January 27, 2024, 4:16pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/34 "2024-01-27T16:16:05Z")

</div>

> [@BurningWitness](#):
>
> Isn’t proper levity polymorphism support a way more straightforward solution […]

…not according to the OP here, and others:

- [New type of `($)` operator in GHC 8.0 is problematic](https://mail.haskell.org/pipermail/ghc-devs/2016-February/011268.html) (2016)

* * *

> Wouldn’t that mean every function needs to have 2args versions for each choice of levity downstream?

That’s more of a _“provide-it-all-now”_ solution. I’m thinking more _“provide-only-as-needed”_, where strictness annotations would be expanded as they are encountered by adding the extra calls needed to evaluate (sub)terms.

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [January 27, 2024, 4:22pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/35 "2024-01-27T16:22:22Z")

</div>

> [@atravers](#):
>
> the extra calls needed

But calls to what? There is currently no strict version of `Data.List.map` (and no mechanism to select such versions either).

Or are you saying that it should insert calls to some standard evaluation function for each data type like `deepseq` before or after the map?

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [January 27, 2024, 4:27pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/36 "2024-01-27T16:27:34Z")

</div>

- At this point in time - the (mis-named) `Prelude.seq`;
- In the future - who knows; maybe strict patterns will be the basic mechanism, rather that calling a primitive definition…

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [January 27, 2024, 4:31pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/37 "2024-01-27T16:31:00Z")

</div>

Here’s another way to think about it - right now the _strictness propagator_ (of which _strictness analysis_ is a crucial part) uses evidence gleaned from the program. The strictness annotation would just be a form of evidence provided directly by the programmer.

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [January 27, 2024, 4:37pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/38 "2024-01-27T16:37:25Z")

</div>

Ah, but how do you apply `seq` inside arbitrary data structures like lists? I think that’s what @sgraf was asking with this example:

> [@sgraf](#):
>
> ```haskell
> xs :: [!Int]
> xs = map (+ 1) [error "blah"]
> 
> ```

The `seq` strategy could work for the top level arguments of a function, but it seems more difficult to do it efficiently for types that are deeper inside other data structures.

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [January 27, 2024, 4:40pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/39 "2024-01-27T16:40:11Z")

</div>

I thought we were discussing matters pertaining to (ordinary) strictness, not [hyper-strictness](https://foldoc.org/hyperstrict)…

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [January 27, 2024, 4:53pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/40 "2024-01-27T16:53:54Z")

</div>

Ah, then I think this whole discussion has been one big misunderstanding. The answer to @sgraf’s question:

> [@sgraf](#):
>
> Would you expect this to type-check?
> 
> ```haskell
> xs :: [!Int]
> xs = map (+ 1) [error "blah"]
> 
> ```

Is simply that you aren’t allowed to put the annotions nested in a data type like that.

You could only use it on function arguments like this:

```haskell
tuple :: !Int -> !Int -> (Int, Int)
tuple x y = (x, y)

```

And perhaps to variables like:

```haskell
x :: !Int
x = 1 + 2 + 3

```

But that is difficult if that is a top-level binding (I have worked on that problem during my internship with Well-Typed).

[Previous page](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602.md?page=1)

[Next page](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602.md?page=3)