javascript - 蹦床递归导致“超出最大调用堆栈大小”

我正在研究区块链，并且正在实现一个非常简单的“工作证明”。

工作证明：

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

我仍然收到“超出最大调用堆栈大小”的错误，甚至踩了mine函数。

我已经阅读了关于StackOverflow的许多其他问题以及各种博客上的文章，但其中许多问题只关注于蹦床或TCE解决问题的“阶乘”或“斐波那契”示例……但事实并非如此。

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

最佳答案

根据您的蹦床-

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编写为单独的函数？您将“检查难度”与“挖掘”混为一谈。这也应该是一个单独的功能-

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

最后，通过将mine调用移到循环外来简化nextNonce

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