How to make monads stack-safe for benchmarking?

kadblas [8:58 PM]
:confused: Ran into a stack overflow error when I was benchmarking the ReaderT and Run approaches to writing a program.

natefaubion [8:59 PM]
@kadblas FYI Run has some benchmarks in the repo
But yeah, with unsafe monadic stuff, you can only test so much

kadblas [9:01 PM]
Hmm… Your code uses runTramploline to make it stack safe.

natefaubion [9:01 PM]
It does different tests
it tests unsafe vs trampoline vs Run

kadblas [9:01 PM]

natefaubion [9:02 PM]
I’ve been meaning to add a different Free implementation, which makes Run faster across the board
Haven’t gotten around to it yet though

kadblas [9:03 PM]
Ah, right. I recall you talking about that earlier.
I’d still like to know how to do this, even if you already have benchmarks.

natefaubion [9:05 PM]
How to do what, specifically?

kadblas [9:06 PM]
Make the code I have stack-safe.

natefaubion [9:06 PM]
naive monadic code is always stack unsafe if it’s evaluated synchronously
given a traditional stackful runtime
The only way to make it safe is to have a data-type that trades stack for heap, like Free
which means you have a way of suspending the continuations in a data type so you can run them in an interpreter loop

kadblas [9:09 PM]

natefaubion [9:10 PM]
So, Reader (ReaderT e Identity) itself is always unsafe give the normal JS runtime
A transformer is only as safe as it’s inner type
There is MonadRec, which represents Monads that can run tail recursive loops
that don’t consume stack

kadblas [9:12 PM]
Ok. I didn’t realize that Identity is always unsafe.
Yeah, MonadRec was my first thought.

natefaubion [9:13 PM]
I personally don’t love MonadRec, but it has it’s utility
You have to be careful with it, you only want to use it for a final interpretation of something
For example, you don’t want to reinterpret Free multiple times with MonadRec, because you get an exponential explosion of binds

kadblas [9:14 PM]
If my “stack” is ReaderT e (StateT s Identity a), what are my options for making that stack safe?

natefaubion [9:16 PM]
You have to swap out Identity for something safe

kadblas [9:16 PM]
Well, that presents problems for my testing approach then, :laughing:

natefaubion [9:17 PM]
It’s not possible to make a base Identity inherently safe
So you just have to test fewer binds

kadblas [9:19 PM]
Well, I’ll start with why I’m even using Identity in the first place. Since my code (the random number game) is essentially a state machine, I’m using Identity to turn my game’s logic into a pure function that I can use QuickCheck to test. This was my “solution” due to not knowing how to use QuickCheck to test things with “monadic effects” (as I think it’s called). I wanted to benchmark the same logic using the different approaches just to see what it would look like (and I guess learn things like this along the way). The benchmark threw an error when the “number of guesses” it had to make was 3000.

natefaubion [9:20 PM]
Trampoline is what you traditionally use to make pure things stack safe
type Trampoline = Free ((->) Unit)
I don’t think the (->) Unit is strictly necessary. Free Identity can also work
in lieu of Identity

kadblas [9:23 PM]
Ok. So my options are:

  • benchmark using a smaller number, so that I don’t need to incur the overhead of Trampoline
  • benchmark using a large number, but incur the overhead of Trampoline because otherwise I’ll get a stackoverflow error

natefaubion [9:23 PM]

1 Like