javascript - How to implement a stack-safe chainRec operator for the continuation monad?

Question

I am currently experimenting with the continuation monad. Cont is actually useful in Javascript, because it abstracts from the callback pattern.

When we deal with monadic recursion, there is always the risk of a stack overflow, because the recursive call isn't in tail position:

const chain = g => f => k =>
  g(x => f(x) (k));

const of = x => k =>
  k(x);
  
const id = x =>
  x;

const inc = x =>
  x + 1;

const repeat = n => f => x => 
  n === 0
    ? of(x)
    : chain(of(f(x))) (repeat(n - 1) (f));

console.log(
  repeat(1e6) (inc) (0) (id) // stack overflow
);

Answer 1

with best wishes,

I think this might be what you're looking for,

const chainRec = f => x =>
  f ( chainRec (f)
    , of
    , x
    )

Implementing repeat is just as you have it – with two exceptions (thanks @Bergi for catching this detail). 1, loop and done are the chaining functions, and so the chainRec callback must return a continuation. And 2, we must tag a function with run so cont knows when we can safely collapse the stack of pending continuations – changes in bold

const repeat_ = n => f => x =>
  chainRec
    ((loop, done, [n, x]) =>
       n === 0
         ? of (x) (done)                // cont chain done
         : of ([ n - 1, f (x) ]) (loop) // cont chain loop
    ([ n, x ])

const repeat = n => f => x =>
  repeat_ (n) (f) (x) (run (identity))

But, if you're using chainRec as we have here, of course there's no reason to define the intermediate repeat_. We can define repeat directly

const repeat = n => f => x =>
  chainRec
    ((loop, done, [n, x]) =>
       n === 0
         ? of (x) (done)
         : of ([ n - 1, f (x) ]) (loop)
    ([ n, x ])
    (run (identity))

Now for it to work, you just need a stack-safe continuation monad – cont (f) constructs a continuation, waiting for action g. If g is tagged with run, then it's time to bounce on the trampoline. Otherwise constructor a new continuation that adds a sequential call for f and g

// not actually stack-safe; we fix this below
const cont = f => g =>
  is (run, g)
    ? trampoline (f (g))
    : cont (k =>
        call (f, x =>
          call (g (x), k)))

const of = x =>
  cont (k => k (x))

Before we go further, we'll verify things are working

const TAG =
  Symbol ()

const tag = (t, x) =>
  Object.assign (x, { [TAG]: t })
  
const is = (t, x) =>
  x && x [TAG] === t

// ----------------------------------------

const cont = f => g =>
  is (run, g)
    ? trampoline (f (g))
    : cont (k =>
        call (f, x =>
          call (g (x), k)))
  
const of = x =>
  cont (k => k (x))

const chainRec = f => x =>
  f ( chainRec (f)
    , of
    , x
    )
  
const run = x =>
  tag (run, x)
  
const call = (f, x) =>
  tag (call, { f, x })  

const trampoline = t =>
{
  let acc = t
  while (is (call, acc))
    acc = acc.f (acc.x)
  return acc
}

// ----------------------------------------

const identity = x =>
  x
  
const inc = x =>
  x + 1

const repeat = n => f => x =>
  chainRec
    ((loop, done, [n, x]) =>
       n === 0
         ? of (x) (done)
         : of ([ n - 1, f (x) ]) (loop))
    ([ n, x ])
    (run (identity))
      
console.log (repeat (1e3) (inc) (0))
// 1000

console.log (repeat (1e6) (inc) (0))
// Error: Uncaught RangeError: Maximum call stack size exceeded