Trampoline recursion causes "Maximum call stack size exceeded"

I am studying blockchain and I am implementing a really simple "proof of work".

Proof of work:

export function mineBlock(difficulty: number, block) {
  const prefix = Array(difficulty + 1).join("0");

  function mine(block, difficulty) {
    const nonce = block.nonce + 1;
    const newBlock = {...block, nonce};
    const hash = calculateHash(newBlock);

    return hash.substring(0, difficulty) === prefix
                ? {...newBlock, hash}
                : mine({...newBlock, hash}, difficulty);
  }

  return trampoline(mine(block, difficulty));

}

Trampoline:

export function trampoline(func) {
  let result = func;

  while(result && typeof(result) === "function") {
    result = result();
  }

  return result;
}

I still get "Maximum call stack size exceeded" error, even trampolining mine function.

I've read a lot of other questions on StackOverflow and articles on various blog, but a lot of them only focus on "factorial" or "fibonacci" examples, where trampolines or TCE solves the problem... but that's not the case.

I am working with Node 10, so I don't mind if this doesn't work in browsers.

Based on your trampoline -

export function trampoline(func) {
  let result = func;

  while(result && typeof(result) === "function") { // <--
    result = result();
  }

  return result;
}

You probably intended -

function mineBlock(difficulty, block) {
  const prefix = Array(difficulty + 1).join("0");

  function mine(block, difficulty) {
    const nonce = block.nonce + 1;
    const newBlock = {...block, nonce};
    const hash = calculateHash(newBlock);

    return hash.substring(0, difficulty) === prefix
                ? {...newBlock, hash}
                  // add `() => ...`
                : () => mine({...newBlock, hash}, difficulty); // <--
  }

  return trampoline(mine(block, difficulty));
}

---

But don't stop there. difficulty is shadowed unnecessarily. It's an argument of mine, but it never changes in the recurring call. You can remove it

function mineBlock(difficulty, block) {
  const prefix = Array(difficulty + 1).join("0")

  function mine(block) { // <--
    const nonce = block.nonce + 1
    const newBlock = {...block, nonce}
    const hash = calculateHash(newBlock)

    return hash.substring(0, difficulty) === prefix
                ? {...newBlock, hash}
                : () => mine({...newBlock, hash}) // <--
  }

  return trampoline(mine(block)) // <--
}

See how you write calculateHash as a separate function? You've mixed concerns of "checking difficulty" in with "mining". This should be a separate function too -

function checkDifficulty(n, hash) {
  return hash.substr(0,n) === "0".repeat(n)
}

function mineBlock(difficulty, block) {
  function mine(block) { 
    const nonce = block.nonce + 1
    const newBlock = {...block, nonce}
    const hash = calculateHash(newBlock)

    return checkDifficulty(difficulty, hash) // <--
                ? {...newBlock, hash}
                : () => mine({...newBlock, hash})
  }

  return trampoline(mine(block)) // <--
}

Separate concern of updating the nonce and hash as well -

function checkDifficulty(n, hash) {
  return hash.substr(0,n) === "0".repeat(n)
}

function nextNonce(block) {
  return updateHash({ ...block, nonce: block.nonce + 1 })
}

function updateHash(block) {
  return { ...block, hash: calculateHash(block) }
}

function mineBlock(difficulty, block) {
  function mine(block) {
    const newBlock = nextNonce(block) // <--

    return checkDifficulty(difficulty, newBlock.hash)
                ? newBlock
                : () => mine(newBlock)
  }

  return trampoline(mine(block)) // <--
}

Lastly, simplify mine by moving the nextNonce call outside of the loop

function checkDifficulty(n, hash) {
  return hash.substr(0,n) === "0".repeat(n)
}

function nextNonce(block) {
  return updateHash({ ...block, nonce: block.nonce + 1 })
}

function updateHash(block) {
  return { ...block, hash: calculateHash(block) }
}

function mineBlock(difficulty, block) {
  function mine(b) {
    return checkDifficulty(difficulty, b.hash)
                ? b
                : () => mine(nextNonce(b)) // <--
  }

  return trampoline(mine(nextNonce(block)) // <--
}

These are just possible lines you can draw in the sand. Hopefully this gives you an idea of how you can begin to make improvements to your program. You might chose to draw different lines and that's okay.

We might use a simple while loop now -

function mineBlock(difficulty, block) {
  let b = block
  while (!checkDifficulty(difficulty, b.hash))
    b = nextNonce(b)
  return b
}

Or an entirely different trampoline -

const loop = f =>
{ let a = f ()
  while (a && a.recur === recur)
    a = f (...a.values)
  return a
}

const recur = (...values) =>
  ({ recur, values })

const mineBlock = (difficulty, block) =>
  loop
    ( (b = block) =>
        checkDifficulty (difficulty, b)
          ? b
          : recur (nextNonce (b))
    )