How to make monads stack-safe for benchmarking?

Chatroom Cross-posts
#1

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]
oh

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]
Right.

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]
Right.
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]
Yep

1 Like