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

Ответ 1

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

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

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

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

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

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

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

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

PARLANSE программирование langauge я реализовано 1) и 2). Я работаю над 3).

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

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

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

Ответ 5

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

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

Ответ 6

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

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

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

Ответ 7

Предположим, вы хотели внедрить стекируемый 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) и узнайте, что происходит с вашим драгоценным компьютером.

Ответ 8

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