Действительно ли трюк с продолжением + хвостовой рекурсией обменивает пространство стека на пространство кучи?

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

Возьми пример

let rec count n = 
    if n = 0
      then 0
      else 1 + count (n - 1)

let rec countCPS n cont =
    if n = 0
      then cont 0
      else countCPS (n - 1) (fun ret -> cont (ret + 1))

Первая версия count будет накапливать кадры стека в каждом рекурсивном вызове, вызывая переполнение стека примерно n = 60000 на моем компьютере.

Идея трюка CPS заключается в том, что countCPS реализация является хвостовой рекурсивной, так что вычисление

let f = countCPS 60000

на самом деле будет оптимизирован для запуска в виде цикла и работать без проблем. Вместо стековых фреймов продолжение, которое будет выполняться, будет накапливаться на каждом шаге, но это честный объект в куче, где память не вызывает проблем. Таким образом, стиль CPS, как говорят, обменивает пространство стека на пространство кучи. Но я скептически отношусь к этому.

И вот почему: оценка вычислений путем запуска продолжения как countCPS 60000 (fun x -> x) дует мой стек! Каждый звонок

countCPS (n - 1) (fun ret -> cont (ret + 1))

генерирует новое закрытие продолжения из старого и работает с одним приложением-функцией. Так что при оценке countCPS 60000 (fun x -> x) Мы вызываем вложенную последовательность 60000 замыканий, и, хотя их данные лежат в куче, у нас есть функциональные приложения, поэтому снова появляются кадры стека.

Давайте погрузимся в сгенерированный код, разобранный в C#

За countCPS, мы получаем

public static a countCPS<a>(int n, FSharpFunc<int, a> cont)
{
    while (n != 0)
    {
        int arg_1B_0 = n - 1;
        cont = new Program<a>.countCPS@10(cont);
        n = arg_1B_0;
    }
    return cont.Invoke(0);
}

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

internal class countCPS@10<a> : FSharpFunc<int, a>
{
    public FSharpFunc<int, a> cont;

    internal countCPS@10(FSharpFunc<int, a> cont)
    {
        this.cont = cont;
    }

    public override a Invoke(int ret)
    {
        return this.cont.Invoke(ret + 1);
    }
}

Таким образом, выполнение внешнего закрытия приведет к .Invoke это дочернее закрытие, потом это дочернее закрытие снова и снова... У нас действительно снова 60000 вызовов вложенных функций.

Так что я не понимаю, как трюк с продолжением действительно способен делать то, что рекламируется.

Теперь мы можем утверждать, что this.cont.Invoke это снова вызов хвоста, поэтому ему не нужен стек стека..NET выполняет такую ​​оптимизацию? Как насчет более сложных примеров, таких как

let rec fib_cps n k = match n with
  | 0 | 1 -> k 1
  | n -> fib_cps (n-1) (fun a -> fib_cps (n-2) (fun b -> k (a+b)))

По крайней мере, нам пришлось бы спорить, почему мы можем оптимизировать вызовы вложенных функций, записанные в продолжении.

редактировать 

    interface FSharpFunc<A, B>
    {
        B Invoke(A arg);
    }

    class Closure<A> : FSharpFunc<int, A>
    {
        public FSharpFunc<int, A> cont;

        public Closure(FSharpFunc<int, A> cont)
        {
            this.cont = cont;
        }

        public A Invoke(int arg)
        {
            return cont.Invoke(arg + 1);
        }
    }

    class Identity<A> : FSharpFunc<A, A>
    {
        public A Invoke(A arg)
        {
            return arg;
        }
    }
    static void Main(string[] args)
    {
        FSharpFunc<int, int> computation = new Identity<int>();

        for(int n = 10; n > 0; --n)
            computation = new Closure<int>(computation);

        Console.WriteLine(computation.Invoke(0));
    }

Чтобы быть еще более точным, мы моделируем замыкание, которое функция стиля CPS создает в C#.

Понятно, что данные лежат в куче. Однако, оценивая computation.Invoke(0) приводит к каскаду вложенных Invoke с закрытием ребенка. Просто установите точку останова на Identity.Invoke и посмотрите на трассировку стека! Так как же встроенные вычисления обмениваются стеками на пространство кучи, если на самом деле интенсивно использует оба?

Источник

2 ответа

Решение

Здесь есть ряд понятий.

Для хвостовой рекурсивной функции компилятор может оптимизировать ее в цикл, поэтому ему не требуется стек или куча. Вы можете переписать свой count функция в простой хвостовой рекурсивной функции, написав:

let rec count acc n = 
   if n = 0
      then acc
      else count (acc + 1) (n - 1)

Это будет скомпилировано в метод с while цикл, который не делает рекурсивных вызовов.

Продолжения обычно необходимы, когда функция не может быть написана как хвостовая рекурсия. Затем вам нужно сохранить некоторое состояние либо в стеке, либо в куче. Игнорирование того факта, что fib может быть написано более эффективно, наивная рекурсивная реализация будет:

let fib n = 
  if n <= 1 then 1
  else (fib (n-1)) + (fib (n-2))

Для этого требуется место в стеке, чтобы вспомнить, что должно произойти после того, как первый рекурсивный вызов вернет результат (затем мы должны вызвать другой рекурсивный вызов и добавить результаты). Используя продолжения, вы можете превратить это в функции, выделенные для кучи:

let fib n cont = 
  if n <= 1 then cont 1
  else fib (n-1) (fun r1 -> 
         fib (n-2) (fun r2 -> cont (r1 + r2))

Это выделяет одно продолжение (значение функции) для каждого рекурсивного вызова, но это хвостовая рекурсия, поэтому она не исчерпает доступное пространство стека.

Источник

Сложность этого вопроса в том, что:

  1. Это оформлено как вопрос об общих принципах;
  2. Но все детали о том, как это не работает, неизбежно будут касаться деталей реализации.

Хвостовые вызовы могут быть скомпилированы так, чтобы в стеке или куче не выделялся новый кадр. Объектный код может просто создать кадр стека вызываемого абонента на месте с тем же значением указателя стека и безоговорочно передать управление его подпрограмме объектного кода.

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

Кто-то, кто знает F#, должен будет прокомментировать детали вашего дела, но я могу ответить на вопрос в заголовке вашей заявки:

Действительно ли трюк с продолжением + хвостовой рекурсией обменивает пространство стека на пространство кучи?

Ответ в том, что это полностью зависит от вашей языковой реализации. И, в частности, реализации, которые пытаются обеспечить оптимизацию хвостового вызова на более традиционных виртуальных машинах (например, на виртуальной машине Java), которые не были предназначены для нее, часто предоставляют неполную совокупную стоимость владения, а граничные случаи не работают.

Источник
Другие вопросы по тегам