Stack-safe mutual recursion without leaking implementation details on the call side

Question

I generalized clojure's loop/recur trampoline so that it works with indirect recursion:

const trampoline = f => (...args) => {
  let acc = f(...args);

  while (acc && acc.type === recur) {
    let [f, ...args_] = acc.args;
    acc = f(...args_);
  }

  return acc;
};

const recur = (...args) =>
  ({type: recur, args});

const even = n =>
  n === 0
    ? true
    : recur(odd, n - 1);

const odd = n =>
  n === 0
    ? false
    : recur(even, n - 1);


console.log(
  trampoline(even) (1e5 + 1)); // false

However, I have to call the trampoline explicitly on the call side. Is there a way to make it implicit again, as with loop/recur?

Btw., here is loop/recur:

const loop = f => {
  let acc = f();

  while (acc && acc.type === recur)
    acc = f(...acc.args);

  return acc;
};


const recur = (...args) =>
  ({type: recur, args});

So you want to be able to pass functions that mutually recurse without them being aware of the `recur()` function? — Patrick Roberts, Apr 04 '19 at 20:11
Have you by any chance seen [this answer](https://stackoverflow.com/a/43596323/1541563)? Not sure if it will be helpful to you or not, but the code there looks almost identical to yours. — Patrick Roberts, Apr 04 '19 at 20:18
No, this is not possible - apart from implementing your own wrapper function `even` that calls a trampolined internal `even` function. At some place, you must explicitly introduce the trampoline, there's no way around it. — Bergi, Apr 04 '19 at 21:49

score 1 · Answer 1 · answered Apr 04 '19 at 20:29

Clearly since you want the trampolining to be called, it can't be skipped altogether. The simplest thing would simply be to wrap those trampolined calls in the API you want, perhaps something like this:

// Utility code
const trampoline = f => (...args) => {
  let acc = f(...args);

  while (acc && acc.type === recur) {
    let [f, ...args_] = acc.args;
    acc = f(...args_);
  }

  return acc;
};

const recur = (...args) =>
  ({type: recur, args});

// Private implementation
const _even = n =>
  n === 0
    ? true
    : recur(_odd, n - 1);

const _odd = n =>
  n === 0
    ? false
    : recur(_even, n - 1);

// Public API
const even = trampoline(_even);

const odd = trampoline(_odd);

// Demo code
console.log(
  even (1e5 + 1)); // false

console.log(
  odd (1e5 + 1)); // true

Stack-safe mutual recursion without leaking implementation details on the call side

1 Answers1