Comment remplacer les boucles while par une alternative de programmation fonctionnelle sans optimisation de l'appel de queue?

un exemple en JavaScript

voici un exemple d'utilisation de JavaScript. À l'heure actuelle, la plupart des navigateurs ne prennent pas en charge l'optimisation de l'appel de queue et, par conséquent, l'extrait suivant échouera

const repeat = n => f => x =>
  n === 0 ? x : repeat (n - 1) (f) (f(x))
  
console.log(repeat(1e3) (x => x + 1) (0)) // 1000
console.log(repeat(1e5) (x => x + 1) (0)) // Error: Uncaught RangeError: Maximum call stack size exceeded

---

Trampolines

nous pouvons contourner cette limitation en changeant la façon dont nous écrivons répéter, mais seulement légèrement. Au lieu de retourner une valeur directement ou immédiatement récurrente, nous retournerons l'un de nos deux types de trampoline, Bounce ou Done . Nous utiliserons alors notre fonction trampoline pour gérer la boucle.

// trampoline
const Bounce = (f,x) => ({ isBounce: true, f, x })

const Done = x => ({ isBounce: false, x })

const trampoline = ({ isBounce, f, x }) => {
  while (isBounce)
    ({ isBounce, f, x } = f(x))
  return x
}

// our revised repeat function, now stack-safe
const repeat = n => f => x =>
  n === 0 ? Done(x) : Bounce(repeat (n - 1) (f), f(x))


// apply trampoline to the result of an ordinary call repeat
let result = trampoline(repeat(1e6) (x => x + 1) (0))

// no more stack overflow
console.log(result) // 1000000

Currying ralentit un peu les choses aussi, mais nous pouvons remédier à cela en utilisant une fonction auxiliaire pour la récursion. C'est agréable aussi parce qu'il cache le trampoline détail de la mise en œuvre et ne s'attend pas à ce que l'appelant rebondisse la valeur de retour. Cela fonctionne environ deux fois plus vite que le ci-dessus repeat

// aux helper hides trampoline implementation detail
// runs about 2x as fast
const repeat = n => f => x => {
  const aux = (n, x) =>
    n === 0 ? Done(x) : Bounce(x => aux (n - 1, x), f (x))
  return trampoline (aux (n, x))
}

---

style Clojure loop / recur

les Trampolines sont agréables et tout mais c'est un peu ennuyeux de devoir s'inquiéter d'appeler trampoline sur la valeur de retour de votre fonction. Nous avons vu que la solution était d'utiliser un aide auxiliaire, mais c'est un peu ennuyeux aussi. Je suis sûr que certains d'entre vous ne sont pas très enthousiastes à propos des emballages Bounce et Done , aussi.

Clojure crée une interface trampoline spécialisée qui utilise une paire de fonctions, loop et recur – cette paire tandem se prête à une expression remarquablement élégante d'un programme

Oh, et il est vraiment rapide, trop

const recur = (...args) =>
  ({ type: recur, args })
  
const loop = f =>
  {
    let acc = f ()
    while (acc && acc.type === recur)
      acc = f (...acc.args)
    return acc
  }

const repeat = $n => $f => $x =>
  loop ((n = $n, f = $f, x = $x) =>
    n === 0
      ? x
      : recur (n - 1, f, f (x)))
 
console.time ('loop/recur')
console.log (repeat (1e6) (x => x + 1) (0)) // 1000000
console.timeEnd ('loop/recur')              // 24 ms

La poursuite monade

C'est l'un de mes sujets favoris tho, donc nous allons voir à quoi ça ressemble avec la suite monad. Nous allons également aller un peu plus loin et cacher le détail de la mise en œuvre du trampoline à l'intérieur de notre repeat fonction en utilisant une fonction auxiliaire ( aux ) de sorte que l'appelant n'a pas à se soucier de rebondir la valeur de retour à chaque fois

// trampoline
const Bounce = (f,x) => ({ isBounce: true, f, x })

const trampoline = t => {
  while (t && t.isBounce)
    t = t.f(t.x)
  return t
}

// Continuation monad; stack-safe implementation
const Cont = f => ({
  _runCont: f,
  chain: g =>
    Cont(k =>
      Bounce(f, x =>
        Bounce(g(x)._runCont, k)))
})

Cont.of = x => Cont(k => k(x))

const runCont = (m,k) =>
  trampoline(Bounce(m._runCont, k))

// repeat now leaks no implementation detail that a trampoline is used
const repeat = n => f => x => {
  const aux = (n,x) =>
    n === 0 ? Cont.of(x) : Cont.of(f(x)).chain(x => aux(n - 1, x))
  return runCont(aux(n,x), x => x)
}

// looks like any other function, still stack-safe
console.log(repeat(1e5) (x => x + 1) (0))

---

Y combinateur

le combinateur Y est mon combinateur d'esprit; cette réponse serait incomplète sans lui donner une place parmi les autres techniques. Cependant, la plupart des implémentations du combinateur Y ne sont pas sûres pour la pile et déborderont si la fonction fournie par l'utilisateur revient trop souvent. Puisque cette réponse est tout au sujet de préserver stack-safe comportement, bien sûr, nous allons mettre en œuvre Y d'une manière sûre – encore une fois, en s'appuyant sur notre trampoline fidèle.

Y démontre la capacité d'étendre facile à l'utilisation, stack-safe, synchrone infinie recursion sans encombrer votre fonction.

const bounce = f => (...xs) =>
  ({ isBounce: true, f, xs })

const trampoline = t => {
  while (t && t.isBounce)
    t = t.f(...t.xs)
  return t
}

// stack-safe Y combinator
const Y = f => {
  const safeY = f =>
    bounce((...xs) => f (safeY (f), ...xs))
  return (...xs) =>
    trampoline (safeY (f) (...xs))
}

// recur safely to your heart's content
const repeat = Y ((recur, n, f, x) =>
  n === 0
    ? x
    : recur (n - 1, f, f (x)))
  
console.log(repeat (1e5, x => x + 1, 0)) // 10000

---

aspect pratique avec while boucle

mais soyons honnête: c'est beaucoup de cérémonie quand nous négligeons l'une des solutions potentielles les plus évidentes: utiliser une boucle for ou while , mais le cacher derrière une interface fonctionnelle

à toutes fins pratiques, cette fonction repeat fonctionne de manière identique à celles fournies ci – dessus-sauf que celle-ci est environ un ou deux milliards de fois plus rapide (à l'exception de la solution loop / recur ). C'est sans doute beaucoup plus facile à lire aussi.

certes, cette fonction est peut – être un exemple artificiel-toutes les fonctions récursives ne peuvent pas être converties en boucle for ou while si facilement, mais dans un tel scénario où c'est possible, il est probablement préférable de le faire simplement comme cela. Sauvez les trampolines et les continuations pour le levage lourd quand une simple boucle ne fera pas l'affaire.

const repeat = n => f => x => {
  let m = n
  while (true) {
    if (m === 0)
      return x
    else
      (m = m - 1, x = f (x))
  }
}

const gadzillionTimes = repeat(1e8)

const add1 = x => x + 1

const result = gadzillionTimes (add1) (0)

console.log(result) // 100000000

---

setTimeout n'est pas une solution au problème de débordement de pile

OK, donc c' ne de travail, mais seulement paradoxalement. Si votre ensemble de données est petit, vous n'avez pas besoin de setTimeout car il n'y aura pas de débordement de la pile. Si votre ensemble de données est grand et que vous utilisez setTimeout comme un mécanisme de récursion sûr, non seulement vous rendez impossible de retourner une valeur de votre fonction de façon synchrone, il sera tellement lent que vous ne voulez même pas utiliser votre fonction

certaines personnes ont trouvé un site de q&r d'entrevue que encourage cette stratégie terrible

ce à quoi ressemblerait notre repeat en utilisant setTimeout - notez qu'il est également défini dans la suite passing style-ie, nous devons appeler repeat avec un rappel ( k ) pour obtenir la valeur finale

// do NOT implement recursion using setTimeout
const repeat = n => f => x => k =>
  n === 0
    ? k (x)
    : setTimeout (x => repeat (n - 1) (f) (x) (k), 0, f (x))
    
// be patient, this one takes about 5 seconds, even for just 1000 recursions
repeat (1e3) (x => x + 1) (0) (console.log)

// comment the next line out for absolute madness
// 10,000 recursions will take ~1 MINUTE to complete
// paradoxically, direct recursion can compute this in a few milliseconds
// setTimeout is NOT a fix for the problem
// -----------------------------------------------------------------------------
// repeat (1e4) (x => x + 1) (0) (console.log)

Je ne peux pas insister assez sur la gravité de la situation. Même 1e5 prend tellement de temps à courir que j'ai arrêté d'essayer de le mesurer. Je n'inclue pas cela dans les points de repère ci-dessous parce que c'est juste trop lent pour être même considéré comme une approche viable.

---

promesses

promesses ont la capacité de chaînes de calculs et sont en sécurité pile. Cependant, la réalisation d'un repeat sans pile à l'aide de promesses signifie que nous devrons renoncer à notre valeur de retour synchrone, de la même façon que nous avons utilisé setTimeout . Je fournis ceci comme une " solution "parce que cela ne résoudre le problème, contrairement à setTimeout , mais d'une manière qui est très simple par rapport au trampoline ou Monad continuation. Comme vous pouvez l'imaginer, la performance est un peu mauvaise, mais loin d'être aussi mauvaise que l'exemple setTimeout ci-dessus

mérite de noter dans cette solution, le détail de mise en œuvre de la promesse est complètement caché de l'appelant. Une suite simple est fournie comme un 4ème argument et son appelé lorsque le calcul est complet.

const repeat = n => f => x => k =>
  n === 0
    ? Promise.resolve(x).then(k)
    : Promise.resolve(f(x)).then(x => repeat (n - 1) (f) (x) (k))
    
// be patient ...
repeat (1e6) (x => x + 1) (0) (x => console.log('done', x))

---

Repères

Sérieusement, le while en boucle est un beaucoup plus vite - comme presque 100 fois plus rapide (lors de la comparaison du meilleur au pire – mais pas y compris async répond: setTimeout et Promise )

// sync
// -----------------------------------------------------------------------------
// repeat implemented with basic trampoline
console.time('A')
console.log(tramprepeat(1e6) (x => x + 1) (0))
console.timeEnd('A')
// 1000000
// A 114 ms

// repeat implemented with basic trampoline and aux helper
console.time('B')
console.log(auxrepeat(1e6) (x => x + 1) (0))
console.timeEnd('B')
// 1000000
// B 64 ms

// repeat implemented with cont monad
console.time('C')
console.log(contrepeat(1e6) (x => x + 1) (0))
console.timeEnd('C')
// 1000000
// C 33 ms

// repeat implemented with Y
console.time('Y')
console.log(yrepeat(1e6) (x => x + 1) (0))
console.timeEnd('Y')
// 1000000
// Y 544 ms

// repeat implemented with while loop
console.time('D')
console.log(whilerepeat(1e6) (x => x + 1) (0))
console.timeEnd('D')
// 1000000
// D 4 ms

// async
// -----------------------------------------------------------------------------

// repeat implemented with Promise
console.time('E')
promiserepeat(1e6) (x => x + 1) (0) (console.log)
console.timeEnd('E')
// 1000000
// E 2224 ms

// repeat implemented with setTimeout; FAILED
console.time('F')
timeoutrepeat(1e6) (x => x + 1) (0) (console.log)
console.timeEnd('F')
// ...
// too slow; didn't finish after 3 minutes

---

Âge De Pierre JavaScript

les techniques ci-dessus sont démontrées en utilisant de nouveaux syntaxes ES6, mais vous pourriez implémenter un trampoline dans la version la plus précoce possible de JavaScript – il ne nécessite que while et des fonctions de première classe

ci-dessous, nous utilisons le javascript de l'âge de pierre pour démontrer une récursion infinie est possible et performant sans nécessairement sacrifiant une valeur de retour synchrone – 100,000,000 récursions sous 6 secondes - il s'agit d'une différence dramatique par rapport à setTimeout qui ne peut que 1,000 récursions dans la même quantité de temps.

function trampoline (t) {
  while (t && t.isBounce)
    t = t.f (t.x);
  return t.x;
}

function bounce (f, x) {
  return { isBounce: true, f: f, x: x };
}

function done (x) {
  return { isBounce: false, x: x };
}

function repeat (n, f, x) {
  function aux (n, x) {
    if (n === 0)
      return done (x);
    else 
      return bounce (function (x) { return aux (n - 1, x); }, f (x));
  }
  return trampoline (aux (n, x));
}

console.time('JS1 100K');
console.log (repeat (1e5, function (x) { return x + 1 }, 0));
console.timeEnd('JS1 100K');
// 100000
// JS1 100K: 15ms

console.time('JS1 100M');
console.log (repeat (1e8, function (x) { return x + 1 }, 0));
console.timeEnd('JS1 100M');
// 100000000
// JS1 100K: 5999ms

Non-bloquant une récursion infinie à l'aide de l'âge de la pierre JavaScript

si , pour une raison quelconque, vous voulez une récursion infinie non-bloquante (asynchrone), nous pouvons compter sur setTimeout pour reporter un single frame au début du calcul. Ce programme utilise également l'âge de Pierre javascript et calcule 100.000.000 récursions en moins de 8 secondes, mais cette fois d'une manière non-bloquante.

cela démontre qu'il n'y a rien de spécial à avoir une exigence de non-blocage. Un while les fonctions de boucle et de première classe sont toujours la seule exigence fondamentale pour obtenir une recursion sans risque de pile sans sacrifier les performances

dans un programme moderne, avec des promesses, nous substituerions l'appel setTimeout pour une seule promesse.

function donek (k, x) {
  return { isBounce: false, k: k, x: x };
}

function bouncek (f, x) {
  return { isBounce: true, f: f, x: x };
}

function trampolinek (t) {
  // setTimeout is called ONCE at the start of the computation
  // NOT once per recursion
  return setTimeout(function () {
    while (t && t.isBounce) {
      t = t.f (t.x);
    }
    return t.k (t.x);
  }, 0);
}

// stack-safe infinite recursion, non-blocking, 100,000,000 recursions in under 8 seconds
// now repeatk expects a 4th-argument callback which is called with the asynchronously computed result
function repeatk (n, f, x, k) {
  function aux (n, x) {
    if (n === 0)
      return donek (k, x);
    else
      return bouncek (function (x) { return aux (n - 1, x); }, f (x));
  }
  return trampolinek (aux (n, x));
}

console.log('non-blocking line 1')
console.time('non-blocking JS1')
repeatk (1e8, function (x) { return x + 1; }, 0, function (result) {
  console.log('non-blocking line 3', result)
  console.timeEnd('non-blocking JS1')
})
console.log('non-blocking line 2')

// non-blocking line 1
// non-blocking line 2
// [ synchronous program stops here ]
// [ below this line, asynchronous program continues ]
// non-blocking line 3 100000000
// non-blocking JS1: 7762ms