Jak zastąpić pętle while alternatywą programowania funkcyjnego bez optymalizacji wywołania ogonowego?

Przykład w języku JavaScript

Oto przykład użycia JavaScript. Obecnie większość przeglądarek nie obsługuje optymalizacji wywołań ogonowych, dlatego następujący fragment nie powiedzie się

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

Trampoliny

Możemy obejść to ograniczenie, zmieniając sposób zapisu powtarzania, ale tylko nieznacznie. Zamiast zwracać wartość bezpośrednio lub natychmiast powtarzające, zwrócimy jeden z naszych dwóch typów trampolina, Bounce lub Done. Następnie użyjemy naszej trampoline funkcji do obsługi pętli.

// 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 spowalnia też trochę sprawy, ale możemy temu zaradzić używając funkcji pomocniczej do rekurencji. Jest to również miłe, ponieważ ukrywa szczegóły implementacji trampoliny i nie oczekuje, że wywołujący odbije wartość zwracaną. To działa około dwa razy szybciej niż powyżej 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))
}

Clojure-styl loop/recur

Trampoliny są ładne i w ogóle, ale to trochę denerwujące, że trzeba się martwić wywołaniem trampoline na wartość zwracaną funkcji. Widzieliśmy, że alternatywą było użycie pomocniczego pomocnika, ale to też trochę denerwujące. Jestem pewien, że niektórzy z Was nie przepadają za opakowaniami Bounce i Done.

Clojure tworzy wyspecjalizowany interfejs trampoliny, który wykorzystuje parę funkcji, loop i {[17] – - Ta para tandemów nadaje się do niezwykle eleganckie wyrażenie programu

Oh and it ' s really fast, too

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

Kontynuacja monady

To jeden z moich ulubionych tematów, więc zobaczymy jak to będzie wyglądało w kontynuacji monady. Pójdziemy również krok dalej i ukryjemy szczegóły implementacji trampoliny wewnątrz naszej funkcji repeat za pomocą funkcji pomocniczej (aux), aby rozmówca nie musiał się martwić o odbicie wartość zwracana za każdym razem

// 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 kombinator

Kombinator Y jest moim kombinatorem ducha; ta odpowiedź byłaby niekompletna, nie dając jej miejsca wśród innych technik. Większość implementacji kombinatora Y nie jest jednak bezpieczna dla stosu i przepełni się, jeśli dostarczona przez użytkownika funkcja powtarza się zbyt wiele razy. Ponieważ ta odpowiedź dotyczy zachowania bezpiecznego stosu, oczywiście zaimplementujemy Y w bezpieczny sposób-ponownie, polegając na naszej zaufanej trampolinie.

Y demonstruje możliwość rozszerzenia łatwej w użyciu, bezpiecznej dla stosu, synchronicznej nieskończonej rekurencji bez zaśmiecania funkcji.

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

Praktyczność z pętlą while

Ale bądźmy szczerzy: to dużo ceremonii, gdy pomijamy jedno z bardziej oczywistych potencjalnych rozwiązań: użyj pętli for lub while, ale ukryj ją za funkcjonalnym interfejs

Dla wszystkich intencji i celów, ta repeat funkcja działa identycznie do tych podanych powyżej-z tym, że ta jest około jeden lub dwa razy szybsza (z wyjątkiem loop/recur rozwiązanie). Heck, to jest prawdopodobnie dużo łatwiejsze do odczytania zbyt.

Oczywiście, funkcja ta jest być może wymyślonym przykładem – nie wszystkie funkcje rekurencyjne można tak łatwo przekształcić w pętlę for lub while, ale w takim scenariuszu, w którym jest to możliwe, prawdopodobnie najlepiej jest po prostu zrób to tak. Zapisz trampoliny i kontynuacje do ciężkiego podnoszenia, gdy prosta pętla nie wystarczy.

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 nie jest rozwiązaniem problemu przepełnienia stosu

OK, więc to działa , ale tylko paradoksalnie. Jeśli twój zestaw danych jest mały, nie potrzebujesz setTimeout, ponieważ nie będzie przepełnienia stosu. Jeśli twój zbiór danych jest duży i używasz setTimeout jako bezpiecznego mechanizmu rekurencji, nie tylko uniemożliwiasz synchronicznie Zwraca wartość z funkcji, będzie ona tak wolna, że nawet nie będziesz chciał jej używać]}

Niektórzy ludzie znaleźli stronę z pytaniami o wywiad, która zachęca do tej strasznej strategii {59]}

Jak wyglądałby nasz repeat używając setTimeout - zauważ, że jest on również zdefiniowany w stylu continuation passing-ie, musimy wywołać repeat z wywołaniem zwrotnym (k), aby uzyskać ostateczną wartość

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

Nie mogę wystarczająco podkreślić, jak źle to jest. Nawet bieganie trwa tak długo, że przestałem próbować go zmierzyć. Nie uwzględniam tego w poniższych benchmarkach, ponieważ jest to po prostu zbyt powolne, aby nawet uznać je za realne podejście.

Obietnice

Obietnice mają możliwość łączenia obliczeń i są bezpieczne dla stosu. Jednak osiągnięcie bezpiecznego stosu repeat przy użyciu obietnic oznacza, że będziemy musieli zrezygnować z synchronicznej wartości zwracanej, tak samo jak przy użyciu setTimeout. Podaję to jako "rozwiązanie", ponieważ rozwiązuje problem, w przeciwieństwie do setTimeout, ale w sposób bardzo prosty w porównaniu z trampoliną lub kontynuacją monady. Jak można sobie wyobrazić, wydajność jest nieco zła, ale nigdzie nie jest tak zła, jak w powyższym przykładzie setTimeout {59]}

Warto zauważyć w tym rozwiązaniu, szczegóły implementacji obietnicy są całkowicie ukryte przed rozmówcą. Pojedyncza kontynuacja jest dostarczana jako czwarty argument i jest wywoływana, gdy obliczenia są kompletna.

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

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

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

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