F#: В какой области памяти хранится продолжение: стек или куча?

Question

Вопрос

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

Продолжение - это функция, которая накапливает всю работу, которая еще предстоит сделать. Мне кажется, что с каждым рекурсивным вызовом (или итерацией цикла) продолжение растет. Я хочу знать, где этот растущий набор инструкций хранится в памяти во время выполнения цикла. Насколько я знаю, существуют только две секции памяти, которые могут содержать динамические данные: стек и куча. Я бы исключил стек, потому что размер кадра стека фиксирован, когда он уже выделен. Он не может содержать растущий набор инструкций продолжения, поэтому куча остается. Возможно, кадр стека содержит указатель на адрес памяти, где хранится функция продолжения. Это предположение верно?

пример

Здесь у меня есть простой пример. Это рекурсивная функция, которая не является хвостовой рекурсией:

// bigList: int -> int list
let rec bigList = function
    | 0 -> []
    | n -> 1 :: bigList (n-1)

Когда параметр n маленький, все в порядке:

> bigList 3;;
val it : int list = [1; 1; 1]

Но когда n велико, вы можете получить ошибку stackru:

> bigList 170000;;
Stack overflow in unmanaged: IP: 0x2dcdb0, fault addr: 0xbf759ffc
Stack overflow in unmanaged: IP: 0x2dcdb0, fault addr: 0xbf758ffc
...

Это в основном та же функция, но в стиле передачи продолжения:

// bigListC: int -> (int list -> 'a) -> 'a
let rec bigListC n c =
    match n with 
    | 0 -> c []
    | n -> bigListC (n-1) (fun res -> c (1::res))       

Вы вызываете функцию с функцией идентификации (id):

> bigListC 3 id;;
val it : int list = [1; 1; 1]

Как вы можете видеть, он не страдает от проблем с переполнением стека:

> bigListC 170000 id;;
val it : int list =
   [1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
    1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
    1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
    1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
    ...]

С каждым циклом продолжение немного увеличивается:

// bigListC 1 id:
> (fun res -> id (1::res)) [];;
val it : int list = [1]

// bigListC 2 id:
> (fun res -> (fun res -> id (1::res)) (1::res)) [];;
val it : int list = [1; 1]

// bigListC 3 id:
> (fun res -> (fun res -> (fun res -> id (1::res)) (1::res)) (1::res)) [];;
val it : int list = [1; 1; 1]

Answer 1

Короткий ответ: продолжение представлено объектом, выделенным в куче. Когда вы выполняете код, написанный с использованием стиля передачи продолжения, дерево объектов (в куче), представляющих продолжения, растет.

Однако продолжение не хранит код для запуска - оно просто хранит замыкание (переменные и другое состояние, которое использует код). Код, выполняемый каждым из узлов в дереве продолжений, всегда одинаков (и хранится так же, как и обычные методы.NET).

Допустим, у нас есть что-то очень простое, как это:

let rec factorial n c =
  if n = 0 then c 1
  else factorial (n - 1) (fun r -> c (r * n))

После 3-х рекурсивных шагов factorial 3 id, c значением будет выделенный объект в виде кучи, который выглядит следующим образом:

      +--------+   +--------+   +--------+
      | n = 1  | / | n = 2  | / | n = 3  |
      | c = ----/  | c = ----/  | c = id |
      +--------+   +--------+   +--------+   

Итак, если мой ASCII-арт имеет какой-то смысл, у нас есть 3 выделенных объекта, которые содержат значения, которые необходимы продолжению для запуска тела функции. То есть предыдущий c значение и n значение текущей итерации.