Forth http://fforum.winglion.ru/ |
|
что же такое стек? http://fforum.winglion.ru/viewtopic.php?f=36&t=2239 |
Страница 2 из 4 |
Автор: | fplab [ Пн авг 17, 2009 09:25 ] |
Заголовок сообщения: | |
Из классики: "Стек – это линейный список, в котором все операции вставки и удаления (и, как правило, операции доступа к данным) выполняются только на одном из концов списка" Д.Э.Кнут "Искусство программирования" А действительно, для чего весь этот поиск определения ? |
Автор: | avl [ Пн авг 17, 2009 09:47 ] |
Заголовок сообщения: | |
WingLion писал(а): Однако, и в определение стека подобное ограничение вписывать нельзя, потому что в этом случае и все программные стеки пойдут лесом, и даже обычный стек процессора x86 окажется не стеком
А так и есть! Вот в х87 стек — стек, но кольцевой. И в большинстве процессоров стек реализован с помощью массива (оперативной памяти) и двух переменных (регистров), а такое решение избыточно. А стек — одна длинная переменная (регистр) в (из) которую одним сдвигом заталкивается (выталкивается) N бит информации. А вот на одном массиве или очереди можно реализовать любое (счетное) количество стеков. Чтобы реализовать массив или очередь достаточно два стека с контролем пустоты. |
Автор: | mOleg [ Пн авг 17, 2009 09:49 ] |
Заголовок сообщения: | |
avl писал(а): Чтобы реализовать массив или очередь достаточно два стека с контролем пустоты.
и еще один регистр между ними правда доступ будет не random... |
Автор: | Wlad [ Пн авг 17, 2009 12:55 ] |
Заголовок сообщения: | |
Так я и списком могу те же операции реализовать! Более того, как на мой взгляд, так для построения больших и сложных программно-аппаратных комплексов, как раз такая структура, как в Смолток-машине - более "удобна", формализуема и легка в реализации (процессор Катана, например). |
Автор: | avl [ Пн авг 17, 2009 14:07 ] |
Заголовок сообщения: | |
mOleg писал(а): и еще один регистр между ними А вот и нет! Доказывается, что если есть конструкция, которая может заменить обязательную переменную-счетчик (её инкремент-декремент) которая в свою очередь является номером ячейки массива то замена двух стеков на массив делается элементарно. Например один из трех стеков используется в качестве счетчика... А вот для двух стеков без контроля пустоты, действительно, проблема открыта — если кто-то сможет — аплодисменты, я не смог в отличие от первого случая Wlad писал(а): Так я и списком могу те же операции реализовать!
Правильно! Потому что список более "сильная" конструкция и она в простейшем случае эквивалентна очереди которая "сильнее" стека. |
Автор: | Wlad [ Пн авг 17, 2009 22:44 ] |
Заголовок сообщения: | |
avl писал(а): А вот для двух стеков без контроля пустоты, действительно, проблема открыта — если кто-то сможет — аплодисменты, я не смог в отличие от первого случая Надо у Котова с Сабельфельдом посмотреть... avl писал(а): список более "сильная" конструкция и она в простейшем случае эквивалентна очереди которая "сильнее" стека.
Критерий "сильноты" не озвучите? Я просто к тому, что я примерно могу объяснить подобный критерий минимумом операций с привлечением АЛУ для адресной навигации по адресуемым элементам (в обе стороны, - реализация "+"/"-" в смысле продвижения по элементам ДАННОЙ структуры), но дальше этого - и лень, и времени нет заниматься. Насколько я помню, в Эльбрусе (и в уже упомянутом Катане) было подобным образом реализовано понятие "текущий контекст исполнения". Но тогда ещё с кэшами проблемы были - дорого было. |
Автор: | Hishnik [ Вт авг 18, 2009 00:22 ] |
Заголовок сообщения: | |
Код: #define STACKSIZE 2048
int Depth = 0; int Dstack [STACKSIZE]; int PopStack() { Depth--; return Dstack[Depth]; } void PushStack(int x) { Dstack[Depth] = x; Depth ++; } |
Автор: | mOleg [ Вт авг 18, 2009 02:38 ] |
Заголовок сообщения: | |
avl писал(а): mOleg писал(а):и еще один регистр между ними
А вот и нет! я имел ввиду регистр для промежуточного хранения данных, так как вершина стека не читаема Ж8) |
Автор: | WingLion [ Вт авг 18, 2009 06:27 ] |
Заголовок сообщения: | |
Нечитаемость вершины стека - это какое-то непонятное ограничение. (от интеля наверно, у которого вершина стека POPой читается) Элементарный ход POP+PUSH - и вершина прочитана. А в железяке она торчит на выходе стека постоянно. |
Автор: | mOleg [ Вт авг 18, 2009 06:33 ] |
Заголовок сообщения: | |
WingLion писал(а): Нечитаемость вершины стека - это какое-то непонятное ограничение.
вот именно этот момент меня заставил открыть тему! Именно поэтому я искал четкое определение того, что есть стек! По сути, стек, это название некой абстракции (математической\алгоритмической) а не реальное устройство. И у абстракции должно быть четкое описание. Проще говоря, если верхнее значение со стека нельзя прочесть, то однозначно части ФМ TOS и SUB, а так же IP и RTOS - являются регистрами! Еще раз, вопрос возник из-за терминологической неразберихи, которая увы, пока не исчезла 8(( |
Автор: | mOleg [ Вт авг 18, 2009 06:51 ] |
Заголовок сообщения: | |
иначе говоря, физическая реализация математической абстракции может быть в некоторой степени иной, то есть позволять, к примеру, делать больше, нежели это зафиксировано в мат.описании, конечно, при условии соблюдения основных свойств мат.абстракции. иными словами, стек, как математическая абстракция может поддерживать всего две опреации: заталкивание и извлечение, в то время как физическая реализация стека дает информацию не только о верхнем элементе стека, но и о глубине стека, и о каждом элементе стека. |
Автор: | mOleg [ Вт авг 18, 2009 07:05 ] |
Заголовок сообщения: | |
кстати, хочу обратить внимание на то, что хотя стек достаточно легко строится на основе массива регистров (особенно в HDL), сам стек является цельным, то есть неделимым устройством. Иначе говоря стек может не состоять из регистров, а значит не иметь дополнительных свойств, предлагаемых регистровой реализацией, и это нормально! Поэтому, я считаю, что "невозможность чтения и записи верхнего элемента стека" согласуется с его природой согласно Бритвы Оккама . |
Автор: | WingLion [ Вт авг 18, 2009 07:14 ] |
Заголовок сообщения: | |
Ох, блин. И как же любят эти японцы головы рубить! И Оккам не исключение. Зачем нам безголовый стек? Чтобы выглядел по-абстрактнее? Или для запутывания вероятного сишника? Пусть нет регистров, будут пули в магазине АК-74. Но и там можно увидеть верхнюю, а если приглядеться, то ту, что под ней - тоже видно. Так что, ограничение сие совершенно ненужное... |
Автор: | avl [ Вт авг 18, 2009 10:12 ] |
Заголовок сообщения: | |
Wlad писал(а): Надо у Котова с Сабельфельдом посмотреть... А там, вообще, насколько я помню, проблема двух стеков объявлена как нерешенная, но время то шло... Wlad писал(а): Критерий "сильноты" не озвучите? Надо у Котова с Сабельфельдом посмотреть... mOleg писал(а): кстати, хочу обратить внимание на то, что хотя стек достаточно легко строится на основе массива регистров (особенно в HDL), сам стек является цельным, то есть неделимым устройством. Иначе говоря стек может не состоять из регистров, а значит не иметь дополнительных свойств, предлагаемых регистровой реализацией, и это нормально!
Правильно! Обычно стек и не является массивом переменных (регистров). А на массиве можно задать любое, наперед заданное количество стеков (и даже массивов) — например по ячейкам с номерами вида kn "бегает" первый стек, по kn+1 второй, по kn+2 третий и т. д. до k2n-1 И действительно, обычный стек "безголовый", как Вы изволили выразится, а для DUP, SWAP, ROT и т. п. в таком случае нужны дополнительные регистры или другое его устройство. |
Автор: | Kamikaze [ Вт авг 18, 2009 19:58 ] |
Заголовок сообщения: | |
О, стек!!! В форте ведь нет ограничений "на помечтать"? Пытаюсь сейчас стек строк от ~day использовать под одну задачку - и так понравилось, что захотелось "многостаночности" - отдельные стеки под адреса, под данные, под строки и т.п. Вплоть до того, что для каждого типа данных свой стек. Вобщем - стекоориентированную среду программирования. |
Страница 2 из 4 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |