Make FreeApplicative stack safe

[markus1189]

I would be interested as well, @adelbertc are there any pointers how to do this?

[safareli]

freeAp might have stack size issue when traversing but the issue might be in traverse method of Array which will be solved in this PR: https://github.com/sanctuary-js/sanctuary-type-classes/pull/19

but you might have issue with quadratic complexity of free applicative on which here are some related issues:

• https://github.com/ethul/purescript-freeap/issues/7
• https://github.com/ethul/purescript-freeap/pull/9
• https://github.com/ethul/purescript-freeap/pull/10
• https://github.com/scalaz/scalaz/issues/1301

and helpful links:

• https://www.eyrie.org/~zednenem/2013/05/27/freeapp
• http://www.fceia.unr.edu.ar/~mauro/pubs/Notions_of_Computation_as_Monoids.pdf

[safareli]

Recently I have Implemented FreeApplicative (Par in https://github.com/safareli/free/pull/31) which has O(1) complexity on map/ap and O(n) on fold. Also fold is stacksafe, which was not possible with other optimised implementations out there, as they use functions to build up a structure which requires extra stack on fold, leading to stack overflow. here the Free Applicative structure itself is not using any function, and the fold is written so, that function's stack is not used. I think same technique could be applied to other "lazyish" structures to fix stack issue without need for TCO support in environment.

btw same issue is in https://github.com/scalaz/scalaz/issues/1301 too

[djspiewak]

Attn @edmundnoble

[edmundnoble]

@safareli Can you explain how your Par implementation works, specifically foldPar? The JS is incomprehensible to me. The ADT changes are interesting, because it's the opposite of the direction I've typically gone using RWR, i.e., an explicit Lift case and function from FA[F, A] => FA[F, A => B] => FA[F, B] rather than F[A] => FA[F, A => B] => FA[F, B].

[safareli]

@edmundnoble can you clarify this part:

RWR, i.e., an explicit Lift case and function from FA[F, A] => FA[F, A => B] => FA[F, B] rather than F[A] => FA[F, A => B] => FA[F, B].

[edmundnoble]

Eff's implementation of Free, for example, has something akin to case class Impure[R, X, A](union: Union[R, X], continuation: X => Eff[R, A]) but with RWR on the continuation argument. See https://github.com/atnos-org/eff/blob/master/shared/src/main/scala/org/atnos/eff/Eff.scala#L85. It's not too relevant though; I'm really just wondering how foldPar works.

[safareli]

how foldPar works.

Hope this makes sense if not let me know:

// data Par f a where
//  Pure :: {x :: a} -> Par f a
//  Lift :: {i :: f a} -> Par f a
//  Ap :: {f :: Par f (a -> b), x :: Par f a} -> Par f b
// TypeRep f = { of :: forall a. a -> f a}
// foldPar :: (Applicative g) => Par f a ~> (Ɐ x. f x -> g x, TypeRep g) -> g a
foldPar(f, T) {
  // `argsF` contains Par structures which will eventually be applied to some function
  const argsF = [this /*:: Par f a */]
  // `fns` contains Par structures which resolve to some function
  const fns = []
  // we have a loop which runs until we have something to return 
  while (true) {
    // we pop last Par object from `argsF` 
    // we have guaranty that argsF will not be empty here
    let argF = argsF.pop()
    // if the `argF` is `Ap` node
    if (Ap.is(argF)) {
      // we get length of argsF {{{{{{{TK add why}}}}}}}
      const lengthInitial = argsF.length
      // until `argF` is `Ap`
      while (Ap.is(argF)) {
        // so Ap node of type `Par f b` has structure like this:
        //    {f :: Par f (a -> b), x :: Par f a}
        // so here we try to go dig into `f` part to be able to obtain 
        // function `a -> b` and in this process we push the `x :: Par f a`
        // to `argsF` so if initially `` looked like :
        //    argsF = [Ap(Ap(Pure(x => y => x + y), Pure(1)), Pure(2))]
        //    fns = []
        // after this loop ends we would have
        //    argsF = [Pure(2), Pure(1)]
        //    argF = Pure(x => y => x + y)
        argsF.push(argF.x)
        argF = argF.f
      }
      // now as we went as deep as possible in `f` branch of `Ap` node `argF`
      // is either `Pure` node with function or `Lift` with some instruction
      // in both cases we now need to interpret it i.e create pure value in target
      // structure using `of(val, T)` or cal `f` with instruction which will return
      // interpret the instruction into target structure. in both cases they will 
      // eventually produce some function for which we have arguments in `argsF`
      // so `foldArg(argF, f, T)` transforms  `Free f (a -> b)` into `g (a -> b)`
      // and then we create the internal object which contains the `g (a -> b)` and
      // number of arguments it needs to take by diffing initial length of argsF 
      // (which was 0 for the example case 2 so length will be 2) with current length
      // if `f = x => new Identity(x)) and `T.of = f` then 
      // fns at this point  will be `[Identity(x => y => x + y)]`
      fns.push(Fn(foldArg(argF, f, T), argsF.length - lengthInitial))
      // at this point we have "consumed" top `Ap` node from `argsF` and we `continue`
      // if there will be `Ap` nodes in the `argsF` this part will try to simplify
      // again and again
      continue
    }
    // at this point argT is not Ap node so it's either Pure or Lift which we can
    // interpret into g as we did in `Ap` case
    const argT = foldArg(argF, f, T)
    // if `fns` is empty this means we are done and we return argT
    if (fns.length === 0) {
      return argT
    }
    // at this point we must have a function in fns which we pop
    let fn = fns.pop()
    // and we apply `argT :: g a` to `fn :: g (a -> b)` and we will get `g b`
    let res = ap(fn.f, argT)

    // we check how meny times we needed to apply to the `fn`
    // if it's more then 1 then the `res` contains function (curried) which 
    // wants to take more arguments which would be in the `argsF`
    if (fn.length > 1) {
      // so we need to push  the `res` to the `fns` but with smaller `length`
      // and continue everything
      fns.push(Fn(res, fn.length - 1))
      continue
    }
    // at this point the `fn` has no more arguments so we check if there are other
    // Par objects which evaluate to some function in `fns` and if we have one
    while (fns.length > 0) {
      // we pop it from the `fns`
      fn = fns.pop()
      // and apply `res` to it
      res = ap(fn.f, res)
      // here we check if result will need more arguments
      if (fn.length > 1) {
        // in which case we push it to the `fns` with smaller `length`
        fns.push(Fn(res, fn.length - 1))
        break
      }
    }
    // if we reach this position then and `fns` is empty
    if (fns.length === 0) {
      // then we are done 🎉
      return res
    }
  }
}

// Internal helper function for foldPar it folds only Pure and Lift nodes
const foldArg = (node, f, T) => {
  // check if `node` is `Pure` node and if so
  if (Pure.is(node)) {
    // take it's pure value and put it in T
    // i.e. call `pure`/`return` of the target structure
    return of(T, node.x)
  // if `node` is `Lift` node then
  } else if (Lift.is(node)) {
    // we call `f` with instruction contained in the `Lift` node
    // with interprets the instruction into target structure and we return it
    return f(node.i)
  }
}

// Internal helper structure for foldPar it contains an Applicative containing
// a function and information on how many argument it needs
// type Fn g a b = { fun:: g (a -> b), length:: Number}
const Fn = (f, length) => ({ f, length })