Trampoline 递归导致 "Maximum call stack size exceeded"

Question

我正在研究区块链，我正在实现一个非常简单的 "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));

}

蹦床：

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

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

  return result;
}

我仍然得到 "Maximum call stack size exceeded" 错误，即使是 trampolining mine 函数。

我已经阅读了很多关于 Whosebug 的其他问题和各种博客上的文章，但其中很多只关注 "factorial" 或 "fibonacci" 示例，其中 trampolines 或 TCE 解决了问题...但事实并非如此。

我正在使用 Node 10，所以如果这在浏览器中不起作用我不介意。

Answer 1

基于你的蹦床 -

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

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

  return result;
}

你可能打算 -

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));
}

但不要就此止步。 difficulty 被不必要地遮蔽了。它是 mine 的参数，但它在重复调用中永远不会改变。你可以删除它

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)) // <--
}

看看你是如何把calculateHash写成一个单独的函数的？您将 "checking difficulty" 的顾虑与 "mining" 混为一谈。这也应该是一个单独的功能 -

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)) // <--
}

另外关注更新随机数和哈希值 -

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)) // <--
}

最后，通过将 nextNonce 调用移出循环

来简化 mine

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)) // <--
}

这些只是您可以在沙子上画出的可能条线。希望这能让您了解如何开始改进您的程序。您可以选择绘制不同的线条，这没关系。

我们现在可以使用一个简单的 while 循环 -

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

或者完全不同的蹦床 -

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))
    )

Trampoline 递归导致 "Maximum call stack size exceeded"

Trampoline recursion causes "Maximum call stack size exceeded"

javascript

node.js

recursion

functional-programming

trampolines