Почему в CPython стек «растёт» в обратную сторону?

Question

[Даниил Колесниченко]

Решил попробовать поковыряться с исходниками какого-нибудь большого опенсорсного проекта, выбор пал на CPython. У меня вообще нет опыта ковыряния больших исходников, и я, честно говоря, не знал даже, с чего начинать, поэтому методом тыка выбрал для начала Parser/parser.c. Читаю код, а там стек. Ну окей, стек так стек, смотрю, например, функцию сброса стека:

static void
s_reset(stack *s)
{
    s->s_top = &s->s_base[MAXSTACK];
}

Значит, при сбросе стека s->top, то есть указатель на вершину стека, указывает на элемент массива s->s_base под номером MAXSTACK. Даже из названия переменных становится ясно, что при сбросе указатель указывает не на нулевой элемент массива, а на последний. Из других функций для работы со стеком тоже видно, что при добавлении (push) элементов указатель s->top уменьшается, а при взятии (pop) -- увеличивается. Хотя более естественно выглядит, когда наоборот (т. е. при пустом стеке s->s_top = s->s_base[0], как-то так). Есть ли какое-то логическое обоснование использования такого "обратного" стека, или это как кому нравится?

P. S. Си даётся тяжело, мог сказать какую-нибудь чушь, тапками не бейте

P. P. S. Как вообще читать такие большие исходники? Откуда начинать, например? Или все тоже берут рандомный файл, и дальше уже смотрят по include'ам что откуда пришло?

Answer 1

[Максим Мосейчук]

Обратный стек? Да вы больно шутите. Стек всю жизнь растет снизу вверх. Не путайте стек-контейнер и стек часть архитектуры (а тут как раз таки стек виртуальной машины).

А логическое объяснение такое. Код и данные располагаются в начальных адресах памяти, и первым считается нулевой адрес. Стек расположен в конце той же области памяти, и первым элементом стека является последний адрес памяти. Это позволяет быть стеку наибольшего размера прежде, чем он начнёт затирать код и данные. В современных процессорах со страничной адресацией это не так актуально, но совместимость никуда не выкинешь.

Ещё раз повторю, это не тот стек, в который вы элементы сохраняете, а тот, куда кладутся параметры функций, состояния регистров, адреса возврата и т.д.

Comments

[Даниил Колесниченко]

fshp: спасибо, мне казалось, наоборот
я веб-макака и до всяких (оносительно) низкоуровневых вещей пока не доходил, отсюда и глупые вопросы :)

[Максим Мосейчук]

Даниил Колесниченко: советую потратить пару недель на изучение ассемблера. Например по книге (раньше это было рассылкой) Олега Калашникова. Там ничего страшного нет. И писать на нем потом не придётся. Зато хорошо прочистите мозги и узнаете, как работает компьютер от момента включения до запуска своих любимых игрушек

[Даниил Колесниченко]

fshp: спасибо, после K&R возьмусь за Калашникова тогда

[Saboteur]

есть FIFO и есть LIFO.
В первом случае стек растет вверх, во втором сверху-вниз, освобождаясь назад вверх.

[Максим Мосейчук]

Сергей: стек - по определению LIFO. FIFO это классическая очередь.

[Saboteur]

fshp: "Не путайте стек-контейнер и стек часть архитектуры (а тут как раз таки стек виртуальной машины)."
Слово стек может использоваться в разных контекстах.

[Максим Мосейчук]

Сергей а какая разница? Независимо от контекста и реализации стек останется стеком. Программным, аппаратным - неважно. Упоминание FIFO бессмысленно, т.к. это другая абстракция.