Make FreeApplicative stack safe
Closed this issue · 8 comments
I would be interested as well, @adelbertc are there any pointers how to do this?
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: sanctuary-js/sanctuary-type-classes#19
but you might have issue with quadratic complexity of free applicative on which here are some related issues:
and helpful links:
Recently I have Implemented FreeApplicative (Par in safareli/free#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 scalaz/scalaz#1301 too
Attn @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].
@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].
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.
how
foldParworks.
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 })