Как работает язык без стека?

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

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

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

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

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

EDIT: я знаю некоторые архитектуры имеют выделенные стеки, но они не являются необходимыми.

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

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

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

a == b

но так ли это?

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

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

насчет рекурсии? Не проблема. Один хвост-рекурсивная функция типа:

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

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

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

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

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 будет генерировать сломанный код, если вы попытаетесь рекурсию ...)

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