Почему в Racket нет переполнения стека?

Во-первых, немного терминологии: для выполнения не-хвостового вызова требуется контекстный фрейм для хранения локальных переменных, родительского адреса возврата и т. д. Таким образом, вопрос заключается в том, как представить произвольно большой контекст. «Стек» (или стек вызовов) — это всего лишь одна (правда, распространенная) стратегия реализации контекста.

Вот несколько стратегий реализации для глубокой рекурсии (т. е. больших контекстов):

• Выделите кадры контекста в куче и позвольте сборщику мусора нести ответственность за их очистку. (Это красиво и просто, но, вероятно, относительно медленно, хотя люди будут спорить с этим.)
• Выделите кадры контекста в стеке. Когда стек заполнится, скопируйте кадры, находящиеся в настоящее время в стеке, в кучу, очистите стек и сбросьте указатель стека вниз. При возврате, если стек пуст, копировать кадры из кучи обратно в стек. (Это означает, что у вас не может быть указателей на объекты, размещенные в стеке, поскольку объекты перемещаются.)
• Выделите кадры контекста в стеке. Когда стек заполнен, выделите новый большой кусок памяти, назовите его новым стеком (т.е. установите указатель стека) и продолжайте работу. (Это может потребовать mprotect или других операций, чтобы убедить ОС в том, что новый блок памяти можно рассматривать как стек вызовов.)
• Выделите кадры контекста в стеке. Когда стек заполнен, создайте новый поток, чтобы продолжить вычисления, дождитесь завершения потока и организуйте получение возвращаемого значения из него, чтобы вернуться в стек старого потока. (Эта стратегия может быть полезна на таких платформах, как JVM, которые не позволяют напрямую управлять стеком, указателем стека и т. д. С другой стороны, она усложняет такие функции, как локальное хранилище потока и т. д.)
• ... и другие варианты описанных выше стратегий.

Поддержка глубокой рекурсии часто совпадает с поддержкой первоклассных продолжений. В общем, реализация первоклассных продолжений означает, что вы почти автоматически получаете поддержку глубокой рекурсии. Есть хорошая статья под названием Implementation Strategies for First-class Continuations, написанная Will Clinger et al. др. с более подробной информацией и сравнением различных стратегий.

В этом ответе есть две части.

Во-первых, в Racket и других функциональных языках хвостовые вызовы не создают дополнительных кадров стека. То есть такая петля, как

(define (f x) (f x))

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

ОДНАКО, комментарий, на который вы ссылаетесь, не ограничивается только хвостовым вызовом; Racket допускает очень глубокое вложение кадров стека.

Ваш вопрос хороший: почему другие языки не допускают глубоко вложенных кадров стека? Я написал короткий тест, и он выглядит так, как будто C бесцеремонно сбрасывает ядро ​​​​на глубине между 262 000 и 263 000. Я написал простой рэкет-тест, который делает то же самое (следя за тем, чтобы рекурсивный вызов не был в хвостовой позиции), и я прервал его на глубине 48 000 000 без каких-либо видимых побочных эффектов (за исключением, предположительно, довольно большого стека времени выполнения). ).

Чтобы ответить на ваш вопрос напрямую, нет причин, по которым я знаю, что C не может допускать гораздо более глубоко вложенные стеки, но я думаю, что для большинства программистов на C достаточно глубины рекурсии 262 КБ.

Но не для нас!

Вот мой код C:

#include <stdio.h>

int f(int depth){
  if ((depth % 1000) == 0) {
    printf("%d\n",depth);
  }
  return f(depth+1);
}

int main() {
  return f(0);
}

... и код моей ракетки:

#lang racket

(define (f depth)
  (when (= (modulo depth 1000) 0)
    (printf "~v\n" depth))
  (f (add1 depth))
  (printf "this will never print..."))


(f 0)

РЕДАКТИРОВАТЬ: вот версия, которая использует случайность на выходе, чтобы заблокировать возможные оптимизации:

#lang racket

(define (f depth)
  (when (= (modulo depth 1000000) 0)
    (printf "~v\n" depth))
  (when (< depth 50000000)
    (f (add1 depth)))
  (when (< (random) (/ 1.0 100000))
    (printf "X")))

(f 0)

Кроме того, мои наблюдения относительно размера процесса согласуются с кадром стека размером около 16 байт плюс-минус; 50M * 16 байт = 800 мегабайт, а наблюдаемый размер стека составляет около 1,2 гигабайта.