Блог

Я хотел бы знать, есть ли фундаментальная причина для ограничения глубины рекурсии в F # до 10000 или около того, и в идеале, как избежать этого ограничения. Я думаю, что вполне разумно писать код, который использует пространство стека O (n), и был бы признателен, если бы кто-то, кто не согласен, мог объяснить, почему они это делают. Большое спасибо. Я объясняю свое мышление ниже.

Я не вижу никаких причин для того, чтобы не позволять стеку расти до тех пор, пока не будет исчерпана вся доступная память. Это означало бы, что бесконечная рекурсия займет больше времени, чтобы заметить, но это не значит, что мы уже не можем писать программы, которые потребляют бесконечный объем памяти. Я знаю, что можно уменьшить использование стека до O (1), используя продолжения и хвостовую рекурсию, но я не особенно понимаю, как мне полезно делать это все время. Я также не понимаю, как это помогает знать, когда функции, вероятно, потребуется обработать «большой» ввод (ну, по стандартам 8-разрядного микроконтроллера).

Я думаю, что это принципиально отличается от необходимости, например, использовать накапливающиеся параметры, чтобы избежать квадратичного поведения во времени. Хотя это тоже связано с беспокойством о деталях реализации и не обязательно должно выполняться для «небольших» входных данных, оно также сильно отличается тем, что компилятор не может тривиально устранить проблему самостоятельно. Кроме того, он отличается тем, что слегка сложный O (n) код, который был бы O (n ^ 2), если бы был написан наивно, значительно более полезен, чем простая, медленная, удобная для чтения версия. Напротив, код в стиле продолжения имеет точно такую же сложность памяти, что и соответствующая наивная версия, но просто использует другой тип памяти. Это та вещь, о которой компилятор не должен заставлять меня беспокоиться в наши дни?

Хотя я бы «предпочел» теоретическую причину, по которой невозможно иметь глубокий стек, мы могли бы также обсудить практические аспекты. Мне кажется, что стек — это несколько более эффективный способ управления памятью, чем куча, поскольку он не требует сборки мусора и легко освобождается? Я не уверен, что даже вижу, что есть затраты на разрешение глубоких стеков. По общему признанию, ОС должна выделить достаточно виртуального пространства, чтобы вместить всю память, которую вы, возможно, захотите использовать сразу во всей программе для стека каждого потока. Ну и что. Это не значит, что мы, вероятно, исчерпаем распространенный в настоящее время 48-разрядный лимит, сделав это, или что производители оборудования не могут тривиально увеличить этот лимит до 64 бит?

Здесь не так много специфичного для F #. Я ожидаю, что такое же ограничение применяется в C #, и не вижу, что там это больше необходимо, хотя на практике это, очевидно, намного меньше проблем при программировании в императивном стиле.

Большое спасибо за любые ответы / комментарии.

РЕДАКТИРОВАТЬ: я написал краткое изложение ответов ниже.

Безусловно, наиболее веской причиной для F # наследовать ограничения .NET в этом контексте является совместимость. Компиляторы могут и полностью устраняют стек, например, компилятор SML / NJ для стандартного ML автоматически преобразует программы в стиль передачи продолжения. Два основных недостатка заключаются в том, что это требует глобального изменения соглашения о вызовах, которое нарушает совместимость, и что оно существенно менее эффективно. Если бы F # сделал это, чтобы избежать переполнения стека, тогда взаимодействие с C # было бы намного сложнее, а F # было бы намного медленнее.

Еще одна причина, по которой глубокие стеки — плохая идея, — это сборщик мусора. Стеки обрабатываются GCs специально, потому что они гарантированно являются локальными для потока и могут сжиматься без необходимости сбора. .NET GC обходит все стеки потоков всякий раз, когда какой-либо поток использует коллекцию gen0. Следовательно, наличие всего двух спящих потоков с глубокими стеками может привести к тому, что другой поток будет работать в 10 раз медленнее. Представьте, насколько хуже это было бы с гораздо более глубокими стеками. Это можно решить, изменив способ обработки стеков в GC, по сути, превратив их в кучи, но это значительно замедляет работу со стеком.

Теоретически возможно все. Вы могли бы написать компилятор, который использует кучу для управления тем, что традиционно называется «стеком».

На практике производительность (особенно для фундаментальных задач, таких как «вызовы функций») имеет значение. У нас есть полувековой опыт работы с оборудованием и операционной системой, адаптированной / оптимизированной для модели памяти с конечным стеком.

Это та вещь, о которой компилятор не должен заставлять меня беспокоиться в наши дни?

Meh. Сборка мусора — большая победа; управление всей вашей памятью — в основном ненужная рутина, и многие приложения могут пожертвовать некоторой производительностью для производительности программиста. Но я думаю, мало кто считает, что управление стеком / рекурсией человеком имеет огромное значение, даже на функциональном языке, поэтому ценность того, чтобы позволить программисту сорваться с крючка, здесь, ИМО, незначительна.

Обратите внимание, что в частности, в F # вы можете использовать рабочий процесс CPS, который преобразует значительную часть стека в кучу и / или хвостовые вызовы с относительно небольшим изменением стиля программирования / синтаксиса, если вы хотите пойти туда (см., Например, Здесь ).

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

Я могу придумать как минимум две возможные причины:

(1) На многих компьютерных архитектурах трудно увеличить размер, доступный для стека во время выполнения, не перемещая его куда-нибудь еще в адресном пространстве. Как указал @svick в комментариях, .NET в 32-разрядной Windows ограничивает размер стека основного потока до 1 МБ. Изменение размера стека основного потока в Windows требует изменения .EXE-файл.

(2) Гораздо чаще переполнение стека вызвано ошибкой программирования, чем фактическим наличием кода, который действительно должен превышать доступный размер стека. Ограниченный размер стека — очень полезный индикатор для обнаружения ошибок программирования. В 98% случаев, если бы стеку было разрешено расти до доступной памяти, вы бы впервые узнали о своих ошибках программирования, когда исчерпали доступную память.

Я думаю, что теперь на этот вопрос было столько ответов, сколько он получит. Вот краткое изложение:

i) никто не предложил какой-либо фундаментальной причины для ограничения стека ниже общего объема доступной памяти

ii) ответ, который я узнал больше всего, был ответом Брайана (большое спасибо). Я бы настоятельно рекомендовал сообщение в блоге, на которое он ссылался, и остальную часть его блога тоже. Я нашел это более информативным, чем любая из двух хороших книг по F #, которые у меня есть. (Сказав это, вам, вероятно, следует взглянуть на то, что он говорит о том, насколько просто добиться хвостовой рекурсии в части 6 сообщений в блоге о катаморфизмах https://lorgonblog.wordpress.com/2008/06/02/catamorphisms-part-six / прежде чем принять слово «маргинальный», он употребил его за чистую монету 🙂 ).

РЕДАКТИРОВАТЬ: Джон Харроп был очень близким вторым. Большое спасибо.

iii) Свик предложил простой способ увеличения предела на три порядка. Большое спасибо.

iv) Делнан предположил, что наилучшей практикой является просто использовать сгибы / карты везде и определять их хвостовым рекурсивным способом. Это, безусловно, разумный совет для списков, но, возможно, менее применим при обходе графиков. В любом случае, большое спасибо за предложение.

v) Джоэл и Брайан предложили несколько практических причин, почему ограничение является хорошей идеей. Все это были низкоуровневые детали, которые, по моему мнению, должны быть хорошо скрыты языком высокого уровня. Большое спасибо.

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