How to implement guarded recursion in strictly evaluated languages?

Question

I implemented a Scott encoded List type in Javascript along with an overloaded append function that mimics the Semigroup typeclass.

append works just fine but for large lists it will blow the stack. Here is the decisive part of my implementation:

appendAdd("List/List", tx => ty => tx.runList({
  Nil: ty,
  Cons: x => tx_ => Cons(x) (append(tx_) (ty))
}));

Usually I use a trampoline to avoid a growing stack, but this presupposes tail recursion and thus won't work in this case.

Since this implementation is based on Haskell's, I guess lazy evaluation and guarded recursion/tail recursion modulo cons make the difference:

(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

Provided I understand it correctly, due to lazy evaluation (almost) nothing happens in Haskell when I append a list to another, until I actually do something with this new list. In the example below I fold it.

What I don't understand is how guarded recursion can keep the recursion from growing the call stack and whether this behavior can be implemented explicitly in a strictly evaluated language like Javascript.

Hopefully this question isn't too broad.

For a better understanding, here is the full implementation/example:

// type constructor

const Type = name => {
  const Type = tag => Dcons => {
    const t = new Tcons();

    Object.defineProperty(
      t,
      `run${name}`,
      {value: Dcons});

    t[TAG] = tag;
    return t;
  };

  const Tcons =
    Function(`return function ${name}() {}`) ();

  Tcons.prototype[Symbol.toStringTag] = name;
  return Type;
};


const TAG = Symbol("TAG");
const List = Type("List");


// data constructors

const Cons = x => tx => List("Cons") (cases => cases.Cons(x) (tx));
const Nil = List("Nil") (cases => cases.Nil);


// overload binary functions

const overload2 = (name, dispatch) => {
  const pairs = new Map();

  return {
    [`${name}Add`]: (k, v) => pairs.set(k, v),

    [`${name}Lookup`]: k => pairs.get(k),

    [name]: x => y => {
      if (typeof x === "function" && (VALUE in x))
        x = x(y);

      else if (typeof y === "function" && (VALUE in y))
        y = y(x);

      const r = pairs.get(dispatch(x, y));

      if (r === undefined)
        throw new TypeError("...");

      else if (typeof r === "function")
        return r(x) (y);

      else return r;
    }
  }
};


const dispatcher = (...args) => args.map(arg => {
  const tag = Object.prototype.toString.call(arg);
  return tag.slice(tag.lastIndexOf(" ") + 1, -1);
}).join("/");


// Semigroup "typeclass"

const {appendAdd, appendLookup, append} =
  overload2("append", dispatcher);


// List instance for Semigroup

appendAdd("List/List", tx => ty => tx.runList({
  Nil: ty,
  Cons: x => tx_ => Cons(x) (append(tx_) (ty))
}));


// fold

const foldr = f => acc => {
  const aux = tx =>
    tx.runList({
      Nil: acc,
      Cons: x => tx_ => f(x) (aux(tx_))})

  return aux;
};


// data

const tx = Cons(1) (Cons(2) (Nil));
const ty = Cons(3) (Cons(4) (Nil));
const tz = append(tx) (ty);


// run

console.log(
  foldr(x => acc => `${x}${acc}`) (0) (tz) // "12340"
);

"Usually I use a trampoline to avoid a growing stack, but this presupposes tail recursion and thus won't work in this case." Would a `while` loop do the trick? `while (tram != null) { tram = tram(); }`. — Benjamin Hodgson, May 11 '18 at 12:31
But a trampoline is essentially a `while` loop wrapped in a function. To clarify that: I am probably able to define `append` for lists tail recursively (haven't tried it yet) and then use a trampoline. However, I'd like to see if I can follow Haskell's style. This is important to me, because then I could implement a right fold and the recursion schemes and actually use them in real code. — , May 11 '18 at 12:51
The list itself is a stack of deferred calls to `append`, which is what keeps the call stack manageable. — chepner, May 11 '18 at 15:05
You would not want to implement `append` Haskell's way in a strict language. Laziness is precisely what makes that definition efficient -- in a strict functional language you'd use tail recursion and an accumulator. A simple way to fix your issue is to make `Cons` take a thunk as its second argument, but I guess you are specifically trying to avoid that? — luqui, May 11 '18 at 19:53
@luqui Yes, I've tried to avoid thunks. I use the type `Eff = Data("Eff") (Eff => thunk => Eff(thunk))` to defer computations and to make thunks explicit. It looks like I can use either `Eff` or classic tail recursion with accumulators. Either way, I lose a lot of Haskell's elegance. — , May 11 '18 at 20:26

score 1 · Answer 1 · edited May 11 '18 at 15:46

This isn't a real answer but conclusions I drew after further study:

Tail Recursion modulo Cons - TRMC (and "modulo" for other operations) refers only to a strictly evaluated context, whereas guarded recursion refers to a lazy evaluated one
TRMC is an expensive compiler technique and it (probably) doesn't make sense to implement it in userland
TRMC requires the operation to be associative (form at least a Semigroup), so that the parentheses can be rearranged

This Q&A is also helpful: a tail-recursion version list appending function .

How to implement guarded recursion in strictly evaluated languages?

1 Answers1

Linked