How to share intermediate results of continuations?

Question

Please note that even though the example in this question is encoded in Javascript, the underlying concepts are common in Haskell and I while I prefer to express myself in Javascript I also appreciate answers in Haskell.

In Javascript I use CPS to handle asynchronous computations according to monadic principles. For the sake of simplicity, however, I will use the normal continuation monad for this question.

As soon as my continuation compositions grow, I keep finding myself in a situation where I need access to intermediate results of these compositions. Since Javascript is imperative it is easy to store such results in variables and access them later. But since we're talking about continuations accessing intermediate results means calling functions and accessing them several times means a lot of re-evaluation.

This seems to be well suited for memoization. But how can I memoize a function's return value if that very function doesn't return anything but merely calls its continuation (and btw. as I mentioned before I use asynchronous functions that also don't return anything in the current cycle of Javascript's event loop).

It seems as if I have to extract the right continuation. Maybe this is possible with delimited continuations through shift/reset, but I don't know how to apply these combinators. This issue is probably not that hard to solve and I'm just confused by the magical land of continuation passing style...so please be indulgent with me.

Here is a simplified example of Cont without memoization in Javascript:

const taggedLog = tag => s =>
  (console.log(tag, s), s);

const id = x => x;

const Cont = k => ({
  runCont: k,
  [Symbol.toStringTag]: "Cont"
});

const contAp = tf => tx =>
  Cont(k => tf.runCont(f => tx.runCont(x => k(f(x)))));

const contLiftA2 = f => tx => ty =>
  contAp(contMap(f) (tx)) (ty);

const contOf = x => Cont(k => k(x));

const contMap = f => tx =>
  Cont(k => tx.runCont(x => k(f(x))));
                                  
const contReset = tx => // delimited continuations
  contOf(tx.runCont(id));

const contShift = f => // delimited continuations
  Cont(k => f(k).runCont(id));

const inc = contMap(x => taggedLog("eval inc") (x + 1));
const inc2 = inc(contOf(2));
const inc3 = inc(contOf(3));
const add = contLiftA2(x => y => taggedLog("eval add") (x + y));
const mul = contLiftA2(x => y => taggedLog("eval mul") (x * y));

const intermediateResult = add(inc2) (inc3);

mul(intermediateResult) (intermediateResult).runCont(id);

/*
  should only log four lines:
  eval inc 3
  eval inc 4
  eval add 7
  eval mul 49
*/

Answer 1

Your problems seems to be that your Cont has no monad implementation yet. With that, it's totally simple to access previous results - they're just in scope (as constants) of nested continuation callbacks:

const contChain = tx => f =>
  Cont(k => tx.runCont(r => f(r).runCont(k)));

contChain( add(inc2) (inc3), intermediateResult => {
  const intermediateCont = contOf(intermediateResult);
  return mul(intermediateCont) (intermediateCont);
}).runCont(id);

(Of course it's a little weird that all your functions are already lifted and take Cont values as arguments - they shouldn't do that and simply be functions that return Cont values)

---

Your code in Haskell:

import Control.Monad.Cont
import Control.Applicative

let inc = liftA (+1)
let inc2 = inc $ return 2
let inc3 = inc $ return 3
let add = liftA2 (+)
let mul = liftA2 (*)

(`runCont` id) $ add inc2 inc3 >>= \intermediateResult ->
  let intermediateCont = return intermediateResult
  in mul intermediateCont intermediateCont
-- 49

{- or with do notation: -}

(`runCont` id) $ do
  intermediateResult <- add inc2 inc3
  let intermediateCont = return intermediateResult
  mul intermediateCont intermediateCont
-- 49

(I haven't used monad transformers to make a taggedLog side effect)

Answer 2

It seems that I can't avoid getting impure to obtain the desired behavior. The impurity is only local though, because I just replace the continuation chain with its result value. I can do this without changing the behavior of my program, because this is exactly what referential transparency guarantees us.

Here is the transformation of the Cont constructor:

const Cont = k => ({
  runCont: k,
  [Symbol.toStringTag]: "Cont"
});

// becomes

const Cont = k => thisify(o => { // A
    o.runCont = (res, rej) => k(x => { // B
      o.runCont = l => l(x); // C
      return res(x); // D
    }, rej); // E

    o[Symbol.toStringTag] = "Cont";
    return o;
  });

thisify in line A merely mimics this context, so that the Object to be constructed is aware of itself.

Line B is the decisive change: Instead of just passing res to the continuation k I construct another lambda that stores the result x wrapped in a continuation under the runTask property of the current Task object (C), before it calls res with x (D).

In case of an error rej is just applied to x, as usual (E).

Here is the runnning example from above, now working as expected:

const taggedLog = pre => s =>
  (console.log(pre, s), s);

const id = x => x;

const thisify = f => f({}); // mimics this context

const Cont = k => thisify(o => {
    o.runCont = (res, rej) => k(x => {
      o.runCont = l => l(x);
      return res(x);
    }, rej);
    
    o[Symbol.toStringTag] = "Cont";
    return o;
  });

const contAp = tf => tx =>
  Cont(k => tf.runCont(f => tx.runCont(x => k(f(x)))));

const contLiftA2 = f => tx => ty =>
  contAp(contMap(f) (tx)) (ty);

const contOf = x => Cont(k => k(x));

const contMap = f => tx =>
  Cont(k => tx.runCont(x => k(f(x))));
                                  
const inc = contMap(x => taggedLog("eval inc") (x + 1));
const inc2 = inc(contOf(2));
const inc3 = inc(contOf(3));
const add = contLiftA2(x => y => taggedLog("eval add") (x + y));
const mul = contLiftA2(x => y => taggedLog("eval mul") (x * y));

const intermediateResult = add(inc2) (inc3);

mul(intermediateResult) (intermediateResult).runCont(id);

/* should merely log
eval inc 3
eval inc 4
eval add 7
eval add 49
*/