Батутная рекурсия вызывает «Превышен максимальный размер стека вызовов» - PullRequest
Новая
       41

Батутная рекурсия вызывает «Превышен максимальный размер стека вызовов»

0 голосов
/ 19 апреля 2019

Я изучаю блокчейн и реализую очень простое «доказательство работы».

Доказательство работы: 

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 и статьях в различных блогах, но многие из них сосредоточены только на примерах "factorial" или "fibonacci", где батуты или TCE решают проблему ... но это не так дело.

Я работаю с Node 10, поэтому я не против, если это не работает в браузерах.

1 Ответ

2 голосов
/ 19 апреля 2019

На основе вашего батута - 

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

Отдельная забота об обновлении nonce и hash - 

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