Как реализовать безопасный для стека оператор chainRec для продолжения монады?

Я сейчас экспериментирую с монадой продолжения. Cont на самом деле полезен в Javascript, потому что он абстрагируется от шаблона обратного вызова.

Когда мы имеем дело с монадической рекурсией, всегда существует риск переполнения стека, потому что рекурсивный вызов не находится в хвостовой позиции:

const chain = g => f => k =>
  g(x => f(x) (k));

const of = x => k =>
  k(x);
  
const id = x =>
  x;

const inc = x =>
  x + 1;

const repeat = n => f => x => 
  n === 0
    ? of(x)
    : chain(of(f(x))) (repeat(n - 1) (f));

console.log(
  repeat(1e6) (inc) (0) (id) // stack overflow
);

Однако, даже если мы можем преобразовать некоторые случаи в хвостовую рекурсию, мы все равно обречены, потому что у Javascript нет TCO. Следовательно, в какой-то момент мы должны вернуться к петле.

Puresrcipt имеет MonadRec класс типов с tailRecM оператор, который разрешает хвостовые рекурсивные монадические вычисления для некоторых монад. Поэтому я попытался реализовать chainRec в Javascript в основном в соответствии со спецификацией земли фантазии:

const chain = g => f => k => g(x => f(x) (k));
const of = x => k => k(x);
const id = x => x;

const Loop = x =>
  ({value: x, done: false});

const Done = x =>
  ({value: x, done: true});

const chainRec = f => x => {
  let step = f(Loop, Done, x);

  while (!step.done) {
    step = f(Loop, Done, step.value);
  }

  return of(step.value);
};

const repeat_ = n => f => x => 
  chainRec((Loop, Done, [n, x]) => n === 0 ? Done(x) : Loop([n - 1, f(x)])) ([n, x]);

console.log(
  repeat_(1e6) (n => n + 1) (0) (id) // 1000000
);

Это работает, но похоже на обман, потому что кажется, что он обходит монадическую цепочку и таким образом Cont контекст. В этом случае контекст является просто "остальной частью вычисления", т.е. состав функции в обратном порядке и в результате ожидаемое значение возвращается. Но это работает для любой монады?

Чтобы понять, что я имею в виду, взгляните на следующий фрагмент кода из этого выдающегося ответа:

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

const Cont = f => ({
  _runCont: f,
  chain: g =>
    Cont(k =>
      Bounce(f, x =>
        Bounce(g(x)._runCont, k)))
})

// ...

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

Вот chain каким-то образом включен в рекурсивный алгоритм, то есть может возникнуть монадический эффект. К сожалению, я не могу расшифровать этот оператор или согласовать его с небезопасной версией стека (Bounce(g(x)._runCont, k) кажется f(x) (k) часть, хотя).

В конечном счете, мой вопрос, если я испортил реализацию chainRec или неправильно понял спецификацию FL или оба или ничего из этого?


[РЕДАКТИРОВАТЬ]

Оба приведенных ответа очень полезны, если посмотреть на проблему с разных точек зрения и заслуживают принятия. Так как я могу принять только один - эй стекопоток, мир не так прост!!! - Я не приму любой.

2 ответа

Решение

Я испортил реализацию chainRec, или неправильно понял спецификацию FantasyLand, или оба или ничего из этого?

Вероятно, оба или, по крайней мере, первый. Обратите внимание, что тип должен быть

chainRec :: ChainRec m => ((a -> c, b -> c, a) -> m c, a) -> m b

в которой m является Cont а также c ваша оболочка Done/Loop закончилась a или же b:

chainRec :: ((a -> DL a b, b -> DL a b, a) -> Cont (DL a b), a) -> Cont b

Но твой chainRec а также repeat реализации вообще не используют продолжения!

Если мы реализуем только этот тип, без требования, чтобы ему требовалось постоянное пространство стека, это выглядело бы как

const chainRec = f => x => k =>
  f(Loop, Done, x)(step =>
    step.done
      ? k(step.value) // of(step.value)(k)
      : chainRec(f)(step.value)(k)
  );

или если мы отбросим даже требование ленивости (аналогично преобразованию chain от g => f => k => g(x => f(x)(k)) чтобы просто g => f => g(f) (т.е. g => f => k => g(x => f(x))(k))), это будет выглядеть

const chainRec = f => x =>
  f(Loop, Done, x)(step =>
    step.done
      ? of(step.value)
      : chainRec(f)(step.value)
  );

или даже сбросив Done/Loop

const join = chain(id);
const chainRec = f => x => join(f(chainRec(f), of, x));

(Я надеюсь, что я не буду слишком далеко от этого, но это прекрасно отражает идею, лежащую в основе ChainRec)

С ленивым продолжением и нерекурсивным батутом мы бы, однако, написали

const chainRec = f => x => k => {
  let step = Loop(x);
  do {
    step = f(Loop, Done, step.value)(id);
//                                  ^^^^ unwrap Cont
  } while (!step.done)
  return k(step.value); // of(step.value)(k)
};

Синтаксис цикла (инициализация step с f вызов, do/while вместо do) на самом деле не имеет значения, ваш тоже хорошо, но важная часть заключается в том, что f(Loop, Done, v) возвращает продолжение.

Я оставлю реализацию repeat в качестве упражнения для читателя: D
(Подсказка: это может стать более полезным, а также легче понять, если у вас есть повторяющаяся функция f уже пользуюсь продолжениями)

с наилучшими пожеланиями,

Я думаю, что это может быть то, что вы ищете,

const chainRec = f => x =>
  f ( chainRec (f)
    , of
    , x
    )

Внедрение repeat это так, как у вас есть - с двумя исключениями (спасибо @Bergi за то, что выучили эту деталь). 1, loop а также done являются связующими функциями, и поэтому chainRec обратный вызов должен возвращать продолжение. И 2, мы должны пометить функцию с run так cont знает, когда можно безопасно свернуть стопку ожидающих продолжений - изменения выделены жирным шрифтом

const repeat_ = n => f => x =>
  chainRec
    ((loop, done, [n, x]) =>
       n === 0
         ? of (x) (done)                // cont chain done
         : of ([ n - 1, f (x) ]) (loop) // cont chain loop
    ([ n, x ])

const repeat = n => f => x =>
  repeat_ (n) (f) (x) (run (identity))

Но если вы используете chainRec как у нас здесь, конечно, нет оснований для определения промежуточного repeat_, Мы можем определить repeat непосредственно

const repeat = n => f => x =>
  chainRec
    ((loop, done, [n, x]) =>
       n === 0
         ? of (x) (done)
         : of ([ n - 1, f (x) ]) (loop)
    ([ n, x ])
    (run (identity))

Теперь, чтобы все заработало, вам просто нужна монада продолжения в стеке - cont (f) создает продолжение, ожидая действий g, Если g помечен run то пришло время отскочить на trampoline, В противном случае создайте новое продолжение, которое добавляет последовательный call за f а также g

// not actually stack-safe; we fix this below
const cont = f => g =>
  is (run, g)
    ? trampoline (f (g))
    : cont (k =>
        call (f, x =>
          call (g (x), k)))

const of = x =>
  cont (k => k (x))

Прежде чем идти дальше, мы проверим, что все работает

const TAG =
  Symbol ()

const tag = (t, x) =>
  Object.assign (x, { [TAG]: t })
  
const is = (t, x) =>
  x && x [TAG] === t

// ----------------------------------------

const cont = f => g =>
  is (run, g)
    ? trampoline (f (g))
    : cont (k =>
        call (f, x =>
          call (g (x), k)))
  
const of = x =>
  cont (k => k (x))

const chainRec = f => x =>
  f ( chainRec (f)
    , of
    , x
    )
  
const run = x =>
  tag (run, x)
  
const call = (f, x) =>
  tag (call, { f, x })  

const trampoline = t =>
{
  let acc = t
  while (is (call, acc))
    acc = acc.f (acc.x)
  return acc
}

// ----------------------------------------

const identity = x =>
  x
  
const inc = x =>
  x + 1

const repeat = n => f => x =>
  chainRec
    ((loop, done, [n, x]) =>
       n === 0
         ? of (x) (done)
         : of ([ n - 1, f (x) ]) (loop))
    ([ n, x ])
    (run (identity))
      
console.log (repeat (1e3) (inc) (0))
// 1000

console.log (repeat (1e6) (inc) (0))
// Error: Uncaught RangeError: Maximum call stack size exceeded

где ошибка?

Представленные две реализации содержат критическое различие. В частности, это g(x)._runCont немного, что выравнивает структуру. Эта задача тривиальна, используя кодировку JS Object Cont как мы можем сгладить, просто читая ._runCont собственностью g(x)

const Cont = f =>
  ({ _runCont: f
   , chain: g =>
       Cont (k =>
         Bounce (f, x =>
          // g(x) returns a Cont, flatten it
          Bounce (g(x)._runCont, k))) 
   })

В нашей новой кодировке мы используем функцию для представления cont и если мы не предоставим другой специальный сигнал (как мы сделали с run) нет доступа f вне cont как только это было частично применено - посмотрите на g (x) ниже

const cont = f => g =>
  is (run, g)
    ? trampoline (f (g))
    : cont (k =>
        call (f, x =>
          // g (x) returns partially-applied `cont`, how to flatten?
          call (g (x), k))) 

Выше, g (x) вернет частично примененный cont, (т.е. cont (something)), но это означает, что весь cont функция может вкладываться бесконечно. Вместо cont -wrapped something мы только хотим something,

По крайней мере, 50% времени, которое я потратил на этот ответ, приходилось придумывать различные способы выравнивания частично примененных cont, Это решение не особенно изящно, но оно выполняет свою работу и подчеркивает, что именно должно произойти. Мне действительно любопытно посмотреть, какие еще кодировки вы можете найти - изменения, выделенные жирным шрифтом

const FLATTEN =
  Symbol ()

const cont = f => g =>
  g === FLATTEN
    ? f
    : is (run, g)
      ? trampoline (f (g))
      : cont (k =>
          call (f, x =>
            call (g (x) (FLATTEN), k)))

все системы онлайн, капитан

С cont исправление на месте, все остальное работает. Теперь посмотрим chainRec сделать миллион итераций...

const TAG =
  Symbol ()

const tag = (t, x) =>
  Object.assign (x, { [TAG]: t })
  
const is = (t, x) =>
  x && x [TAG] === t

// ----------------------------------------

const FLATTEN =
  Symbol ()

const cont = f => g =>
  g === FLATTEN
    ? f
    : is (run, g)
      ? trampoline (f (g))
      : cont (k =>
          call (f, x =>
            call (g (x) (FLATTEN), k)))
  
const of = x =>
  cont (k => k (x))

const chainRec = f => x =>
  f ( chainRec (f)
    , of
    , x
    )
  
const run = x =>
  tag (run, x)
  
const call = (f, x) =>
  tag (call, { f, x })  

const trampoline = t =>
{
  let acc = t
  while (is (call, acc))
    acc = acc.f (acc.x)
  return acc
}

// ----------------------------------------

const identity = x =>
  x
  
const inc = x =>
  x + 1

const repeat = n => f => x =>
  chainRec
    ((loop, done, [n, x]) =>
       n === 0
         ? of (x) (done)
         : of ([ n - 1, f (x) ]) (loop))
    ([ n, x ])
    (run (identity))
      
console.log (repeat (1e6) (inc) (0))
// 1000000

эволюция продолжение

Когда мы ввели cont в приведенном выше коде не сразу очевидно, как была получена такая кодировка. Я надеюсь пролить свет на это. Мы начнем с того, как мы хотели бы определить cont

const cont = f => g =>
  cont (comp (g,f))

const comp = (f, g) =>
  x => f (g (x))

В этой форме cont будет бесконечно откладывать оценку. Единственное, что мы можем сделать, это подать заявку g который всегда создает другое cont и откладывает наше действие. Мы добавляем аварийный люк, run, который сигнализирует cont что мы не хотим больше откладывать.

const cont = f => g =>
  is (run, g)
    ? f (g)
    : cont (comp (g,f))

const is = ...

const run = ...

const square = x =>
  of (x * x)

of (4) (square) (square) (run (console.log))
// 256

square (4) (square) (run (console.log))
// 256

Выше, мы можем начать видеть, как cont умеет выражать красивые и чистые программы. Однако в среде без исключения хвостовых вызовов это все же позволяет программам создавать последовательности отложенных функций, которые превышают предел стека оценщика. comp непосредственно цепочки функций, так что это за кадром. Вместо этого мы упорядочим функции, используя call механизм собственного изготовления. Когда программа сигнализирует run мы свернем стек вызовов, используя trampoline,

Ниже мы приходим к форме, которая была у нас до применения исправления сглаживания

const cont = f => g =>
  is (run, g)
    ? trampoline (f (g))
    : cont (comp (g,f))
    : cont (k =>
        call (f, x =>
          call (g (x), k)))

const trampoline = ...

const call = ...

желаемое за действительное

Другая техника, которую мы использовали выше, является одной из моих любимых. Когда я пишу is (run, g) Я не знаю, как я буду представлять is или же run сразу, но я могу понять это позже. Я использую то же самое желаемое за trampoline а также call,

Я подчеркиваю это, потому что это означает, что я могу сохранить всю эту сложность вне cont и просто сосредоточиться на его элементарной структуре. Я закончил с набором функций, которые дали мне это поведение "пометки"

// tag contract
// is (t, tag (t, value)) == true

const TAG =
  Symbol ()

const tag = (t, x) =>
  Object.assign (x, { [TAG]: t })

const is = (t, x) =>
  x && x [TAG] === t

const run = x =>
  tag (run, x)

const call = (f, x) =>
  tag (call, { f, x })

Желаемое мышление - это все о написании желаемой программы и воплощении ваших желаний в жизнь. Как только вы выполняете все свои желания, ваша программа просто волшебным образом работает!

Другие вопросы по тегам