Как работает бесуровневый язык?

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

«Модель большого стека» предполагает, что скомпилированная программа будет выделять «стоковые кадры» для вызовов функций в смежном регионе памяти, используя машинные инструкции для быстрой настройки регистров, содержащих указатель стека (и дополнительный указатель фрейма стека). Это приводит к быстрому вызову / возврату функции, по цене наличия большой смежной области для стека. Поскольку 99,99% всех программ, работающих под этими современными операционными системами, хорошо работают с большой моделью стека, компиляторы, загрузчики и даже ОС «знают» об этой области стека.

Одна из распространенных проблем, с которыми сталкиваются все такие приложения, – «насколько большой должен быть мой стек?» , Поскольку память дешевле, в основном, происходит то, что большой кусок выделяется для стека (MS по умолчанию составляет 1 Мб), а типичная структура вызовов приложений никогда не приближается к ее использованию. Но если приложение действительно использует все это, оно умирает с незаконной ссылкой на память («Мне жаль, Дэйв, я не могу этого сделать»), благодаря достижению конца его стека.

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

Существует несколько причин использования распределения кучи для кадров стека:

1) Если программа выполняет глубокую рекурсию, зависящую от конкретной проблемы, которую она решает, очень сложно заранее выделить область «большого стека» заранее, потому что необходимый размер неизвестен. Можно неудобно организовать вызовы функций, чтобы проверить, осталось ли достаточно стека, а если нет, перераспределите больший fragment, скопируйте старый стек и скорректируйте все указатели в стек; это так неудобно, что я не знаю никаких реализаций. Выделение стековых фреймов означает, что приложение никогда не должно огорчаться, пока в памяти не останется выделенной памяти.

2) Программа forks подзадач. Каждая подзадача требует своего собственного стека и поэтому не может использовать один «большой стек». Таким образом, нужно выделять стеки для каждой подзадачи. Если у вас есть тысячи возможных подзадач, вам могут понадобиться тысячи «больших стеков», и спрос на память внезапно становится нелепым. Выделение стековых фреймов решает эту проблему. Часто подзадачи «стеки» относятся к родительским задачам для реализации лексического охвата; в качестве подзадач fork создается дерево «substacks», называемое «стеклом кактуса».

3) У вашего языка есть продолжения. Они требуют, чтобы данные в лексической области, видимые для текущей функции, каким-то образом сохранялись для последующего повторного использования. Это может быть реализовано путем копирования родительских стековых фреймов, поднятия стека кактусов и продолжения.

Выбранный мной программный пакет PARLANSE 1) и 2). Я работаю над 3).

У Stackless Python все еще есть стек Python (хотя у него может быть оптимизация хвостового вызова и другие трюки с подключением к кадру), но он полностью отделен от стека C интерпретатора.

Haskell (как обычно реализуется) не имеет стека вызовов; оценка основана на сокращении графика .

Существует хорошая статья о языковой среде Parrot на http://www.linux-mag.com/cache/7373/1.html . Parrot не использует стек для вызова, и эта статья немного объясняет эту технику.

В бесконтактных средах я более или менее знаком с (машиной Тьюринга, сборкой и Brainfuck), обычно используется собственный стек. Нет ничего принципиального в том, что в язык встроен стек.

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

EDIT: Я знаю, что в некоторых архитектурах есть выделенные стеки, но они не нужны.

Существует легкое для понимания описание продолжений в этой статье: http://www.defmacro.org/ramblings/fp.html

Продолжения – это то, что вы можете передать в функцию на языке на основе стека, но которое также может использоваться собственной семантикой языка, чтобы сделать ее «неустойчивой». Конечно, стек все еще есть, но, как описала Ира Бакстер, это не один большой смежный сегмент.

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

a == b 

Но так ли?

 isequal(a, b) { return a == b; } 

Нет. Поскольку интеллектуальный компилятор будет встраивать вызовы в isequal , превращая их в a == b . Итак, почему бы не просто вставить все? Конечно, вы будете генерировать больше кода, но если избавиться от стека стоит того, что вам нужно, это легко с небольшим компромиссом.

Как насчет рекурсии? Нет проблем. Рекурсивная функция:

 bang(x) { return x == 1 ? 1 : x * bang(x-1); } 

Может все еще быть встроенным, потому что на самом деле это всего лишь зацикливание:

 bang(x) { for(int i = x; i >=1; i--) x *= x-1; return x; } 

Теоретически действительно умный компилятор мог бы это понять. Но менее умный человек все еще может сгладить его как goto:

 ax = x; NOTDONE: if(ax > 1) { x = x*(--ax); goto NOTDONE; } 

Есть один случай, когда вам нужно сделать небольшой компромисс. Это не может быть включено:

 fib(n) { return n <= 2 ? n : fib(n-1) + fib(n-2); } 

Stackless C просто не может этого сделать. Вы много отказываетесь? На самом деле, нет. Это то, что нормальный C тоже не может преуспеть. Если вы не верите мне, просто назовите fib(1000) и посмотрите, что происходит с вашим драгоценным компьютером.

Назовите меня древним, но я помню, когда стандарты FORTRAN и COBOL не поддерживали рекурсивные вызовы и поэтому не требовали стека. В самом деле, я вспоминаю реализации машин серии CDC 6000, где не было стека, и FORTRAN будет делать странные вещи, если вы попытаетесь вызвать подпрограмму рекурсивно.

Для записи вместо набора вызовов набор инструкций серии CDC 6000 использовал инструкцию RJ для вызова подпрограммы. Это сохранили текущее значение ПК в целевом местоположении вызова и затем ответили на следующее место. В конце подпрограмма выполнила бы косвенный переход к месту назначения вызова. Этот перезагруженный сохраненный ПК, эффективно возвращаясь к вызывающему.

Очевидно, что это не работает с рекурсивными вызовами. (И мое воспоминание состоит в том, что компилятор CDC FORTRAN IV генерирует сломанный код, если вы попытаетесь выполнить рекурсию …)

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