# 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:** 18\
**Page:** 3

<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:57pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/41 "2024-01-27T16:57:17Z")

</div>

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

Lazier-ness in action:

```haskell
ghci> map (const '\a') [let e = error e in e, let s = '\a':s in s]
"\a\a"
ghci> 

```

So `map` is indifferent to its arguments being fully evaluated or not (or partially so). That would be modulated/adjusted/_“fine-tuned”_ by using strictness annotations ( **however they may be implemented** ) as needed to obtain the result desired by the programmer.

---

<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:59pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/42 "2024-01-27T16:59:21Z")

</div>

> [@jaror](#):
>
> And perhaps to variables like:
> 
> ```haskell
> x :: !Int
> x = 1 + 2 + 3
> 
> ```
> 
> But that is difficult if that is a top-level binding […]

So wouldn’t that also be a problem for `-XStrict`?

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [January 27, 2024, 5:06pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/43 "2024-01-27T17:06:14Z")

</div>

> [@jaror](#):
>
> You could only use it on function arguments like this

Regarding this idea specifically, I have [an old article](http://h2.jaguarpaw.co.uk/posts/strictness-in-types/) on a related issue.

---

<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, 5:12pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/44 "2024-01-27T17:12:28Z")

</div>

**State monad - memory exhausted**

- Why did this happen?

- The [simple](https://www.interaction-design.org/literature/article/kiss-keep-it-simple-stupid-a-design-principle) solution?

---

<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, 5:38pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/45 "2024-01-27T17:38:48Z")

</div>

> [@atravers](#):
>
> **Dump the GC** , and maybe even the heap as well:

Pardon my naivety, but the paper is from 2011 and the non-moving GC was merged in 2020, surely those 30 pages of lambda calculus don’t just solve one of the cornerstone problems of compiler design and noone noticed it? I unfortunately don’t have a decade of necessary background to address the paper directly (or to even be able to read it properly).

---

<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, 6:19pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/46 "2024-01-27T18:19:46Z")

</div>

I commented on that paper here [What about having StrictData and non-strict semantics on functions as the default programming style? - #13 by sgraf](http://discourse.haskell.org/t/what-about-having-strictdata-and-non-strict-semantics-on-functions-as-the-default-programming-style/7639/13). TLDR; I don’t think it is of _implementational_ relevance.

---

<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, 6:21pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/47 "2024-01-27T18:21:35Z")

</div>

> [@atravers](#):
>
> So wouldn’t that also be a problem for `-XStrict`?

Yes, -XStrict does nothing with top-level bindings. E.g. this compiles and doesn’t cause infinite loops:

```haskell
{-# LANGUAGE Strict #-}

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

main = print (fibs !! 10)

```

Ah, it’s also in [the documentation](https://downloads.haskell.org/ghc/latest/docs/users_guide/exts/strict.html#extension-Strict):

> **Top level bindings**
> 
> are unaffected by `Strict`. […] Reason: there is no good moment to force them, until first use.

---

<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, 9:56pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/48 "2024-01-27T21:56:56Z")

</div>

> [@BurningWitness](#):
>
> […] surely those 30 pages of lambda calculus don’t just solve one of the cornerstone problems of compiler design and no-one noticed it?

> [@sgraf](#):
>
> I don’t think it is of _implementational_ relevance.

Prior to the appearance of these [these 35 pages](https://www.cs.tufts.edu/comp/150FP/archive/simon-peyton-jones/eval-apply-jfp.pdf) the choice to use the push/enter or eval/apply styles was largely arbitrary. But in GHC, the eval/apply implementation did avoid a irritating source of complexity:

> (page 3)
> 
> push/enter requires a stack like no other: stack-walking is more difficult, and compiling to an intermediate language like C or C-- is awkward or impossible.

and primarily for this reason, the push/enter implementation was abandoned. Now just imagine what could also be abandoned if GHC (like proto-Rust eventually did) no longer had GC…

* * *

> [@jaror](#):
>
> […] `-XStrict` does nothing with top-level bindings.

Alright, back to this example of yours:

> [@jaror](#):
>
> ```haskell
> x :: !Int
> x = 1 + 2 + 3
> 
> ```

…if this was difficult, can I at least assume that something like

```haskell
x :: Int#
x = ...

```

or:

```haskell
x :: Unlifted @!%$&# ...
x = ...

```

would be similarly as awkward?

---

<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, 10:17pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/49 "2024-01-27T22:17:55Z")

</div>

Yes, the unlifted part is what I have worked on ([!10841](https://gitlab.haskell.org/ghc/ghc/-/merge_requests/10841)). The main issue is that unlifted variables must never be thunks, so they need to be fully evaluated before the program starts. And GHC has no way of evaluating code at compile-time in a reliable way (constant propagation and similar optimisations don’t give any guarantees).

So I started out with the idea to allow only constants be bound in this way, so instead of `1 + 2 + 3` you would have to write `I# 6#` (or more precisely the unlifted equivalent of that). Even number literals are a problem because they are desugared to `fromInteger` function calls.

At the moment it has stranded a bit on implementing the required semantics in the GHCi bytecode interpreter, which does not have the ability to allocate a Haskell value as static data. It currently just makes every top-level variable a thunk. The native back end did already have that ability as an optimization, so I initially thought it would be pretty easy.

---

<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, 11:20pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/50 "2024-01-27T23:20:34Z")

</div>

So why are we here **yet again** discussing the relative merits of unlifted/unboxed types vs _“unlifted classes/families”_ vs strictness annotations vs _etc, etc, etc, etc_ :

> **State monad - memory exhausted**

- There is an infinite number of ways for GC-based Haskell programs to _“leak space”_.

- Haskell implementations like GHC are finite programs.

- Therefore it will **never** be possible for any Haskell implementation to _“plug all of those leaks”_.

So if you want a _“leak-free”_ Haskell, then you want a Haskell **without** a garbage-collected heap - all non-trivial attempts to do otherwise will _ultimately_ be futile.

For example, and as successful as it was, optimistic evaluation would still be prone to retaining too much space. If speculative evaluation is interrupted _“too early”_, then an overly-spacious thunk may not be replaced with its more-compact result.

In the context of I/O models:

> [@](#):
>
> (page 2 of 4)
> 
> While concurrency is an important tool in real-time programming, being forced to use it just to circumvent an inappropriate I/O model is not satisfactory.
> 
> [Reactive Objects](https://www.diva-portal.org/smash/get/diva2:1000395/FULLTEXT01.pdf) (2002)

Similarly, needing to use advanced evaluation techniques just to circumvent the **glaring** deficiencies of garbage-collected heaps is also unsatisfactory.

---

<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, 11:45pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/51 "2024-01-27T23:45:44Z")

</div>

I don’t believe it is possible to have a practical Haskell without a garbage collected heap. At least not unless you want to fall back on manual memory management like Rust has.

The only evidence you’ve provided that it would be possible is a paper that describes a “storeless” and “heapless” semantics in a theoretical sense. As far as I understand the semantics they describe are transforming the programs themselves. So instead of allocating to a heap it will just make the program larger. And I see no mention of memory reclamation, so that would be equivalent to simply never running the GC in a Haskell program. Then pretty much every program will be one big leak.

Take for example this trace from Section 2:

 ![image](https://us1.discourse-cdn.com/flex002/uploads/haskell/original/2X/e/eb76d73485a9f877cc6c910ade87c3b0ffda74ab.png)

This is a storeless semantics and as you can see the program pretty much only ever grows. And notice the `y` that is shadowed on the last two lines which could be reclaimed.

They unfortunately don’t show any traces of the actual storeless abstract machine, but I see no reason why it would behave differently in this respect.

---

<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, 11:52pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/52 "2024-01-27T23:52:16Z")

</div>

Now read page 7 of 34…

---

<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, 11:56pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/53 "2024-01-27T23:56:19Z")

</div>

Ah they do mention reclamation:

> This let expression is needed as long as z occurs free in its  
> body; thereafter it can be elided with a garbage-collection rule [18].

So you’re proposing to replace a garbage collected heap by… a garbage collected program?

Unfortunately that cited paper doesn’t seem to be available even in the library of my university or the worldwide libraries I can search.

---

<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 28, 2024, 12:10am UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/54 "2024-01-28T00:10:10Z")

</div>

> Unfortunately that cited paper doesn’t seem to be available even in my university library.

If CSx is working again:

`https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.51.5026&rep=rep1&type=pdf`

…otherwise:

`https://archive.org/download/citeseerx-csx_citegraph.2017-03-31/citeseerx_checksums.tsv.gz`

…then search for `"10.1.1.51.5026"``:-/`

* * *

> … a garbage collected program?

You’ll need to be more specific:

- a program which incrementally _“tidies up”_ after itself as it runs, _“incremental-GC”_ style;

- or a program which never allocates, instead reusing its own heap space:

---

<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 28, 2024, 12:20am UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/55 "2024-01-28T00:20:26Z")

</div>

> [@atravers](#):
>
> You’ll need to be more specific:

I’m asking how you envision an alternative to garbage collection and how that would solve the problems of leaks. But here’s my thoughts on those two options:

> [@atravers](#):
>
> a program which incrementally _“tidies up”_ after itself as it runs, _“incremental-GC”_ style;

I could imagine a Haskell with incremental GC, perhaps using the new reference counting, functional but in place (FBIP), approach. But I fail to see how that would prevent leaks. I believe incremental GC would only really be a solution to GC pauses. It’s not like Haskell programs leak because the GC doesn’t run often enough.

> [@atravers](#):
>
> or a program which never allocates, instead reusing its own heap space:
> 
> - [Lively Linear Lisp – ‘Look Ma, No Garbage!’](https://www.plover.com/~mjd/misc/hbaker-archive/LinearLisp.html) (1991)

I could also imagine a fully linear Haskell, but then that would basically mean manual memory management like Rust has. I wouldn’t want to manually manage my memory like that in all my programs.

---

<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 28, 2024, 12:46am UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/56 "2024-01-28T00:46:09Z")

</div>

Since the SML source code for the prototype is no longer at the URL listed at the bottom of page 4:

`http://www.zerny.dk/def-int-for-call-by-need.html`

…I’m left with no other alternative but to build an all-new prototype - just not in SML, which is also GC-based. It’s another reason for my interest in Rust, and the appearance of its second compiler.

But I’ve been wrong in the past, so why should this time be any different? It could be that sometime in the middle of the year, if I have a working prototype in a non-GC language, it ends up leaking stack space instead of heap space - darn. Fortunately, there’s another option, courtesy of one Robert Ennals:

`https://web.archive.org/web/20130610122750/https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.9.9901&rep=rep1&type=pdf`

…and this was a working system! But for reasons which I’ve yet to see explained satisfactorily, it went nowhere (then Robert went elsewhere). If all the old experimental versions/branches are still available for GHC, I believe `speceval2` contains the actual implementation.

---

<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 28, 2024, 4:42am UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/57 "2024-01-28T04:42:17Z")

</div>

> [@jaror](#):
>
> GHC has no way of evaluating code at compile-time in a reliable way

On a tangent, are there any plans to address this? The inability to type-check and properly pack literals is a very weird pain point, and I don’t like the approach of incorrect instances plus `RULES` pragmas as a solution.

---

<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 28, 2024, 1:10pm UTC](https://discourse.haskell.org/t/state-monad-memory-exhausted/8602/58 "2024-01-28T13:10:47Z")

</div>

Personally, I think Template Haskell is the easiest way to address it. You’d write something like:

```haskell
x = $$(evalTH [|| 1 + 2 + 3 ||])

```

But another option is to identify a subset of the language that can be evaluated at compile time, like [constexpr](https://en.cppreference.com/w/cpp/language/constexpr) in C++ or [constant evaluation](https://doc.rust-lang.org/reference/const_eval.html) in Rust.

But perhaps it would also be interesting to explore the possibility of having actual guarantees about optimisations that GHC performs. Such that we can simply rely on the existing optimisations to do this evaluation for us.

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