Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 17:55

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 48 ]  На страницу Пред.  1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения:
СообщениеДобавлено: Пн авг 17, 2009 09:25 
Не в сети

Зарегистрирован: Вт авг 08, 2006 13:49
Сообщения: 47
Благодарил (а): 2 раз.
Поблагодарили: 1 раз.
Из классики:

"Стек – это линейный список, в котором все операции вставки и удаления (и, как правило, операции доступа к данным) выполняются только на одном из концов списка"

Д.Э.Кнут "Искусство программирования"

А действительно, для чего весь этот поиск определения ?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн авг 17, 2009 09:47 
Не в сети
Аватара пользователя

Зарегистрирован: Чт май 18, 2006 08:55
Сообщения: 30
Откуда: Мелмак, Гидра Кентавра
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
WingLion писал(а):
Однако, и в определение стека подобное ограничение вписывать нельзя, потому что в этом случае и все программные стеки пойдут лесом, и даже обычный стек процессора x86 окажется не стеком

А так и есть! Вот в х87 стек — стек, но кольцевой. И в большинстве процессоров стек реализован с помощью массива (оперативной памяти) и двух переменных (регистров), а такое решение избыточно.
А стек — одна длинная переменная (регистр) в (из) которую одним сдвигом заталкивается (выталкивается) N бит информации. А вот на одном массиве или очереди можно реализовать любое (счетное) количество стеков. Чтобы реализовать массив или очередь достаточно два стека с контролем пустоты.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн авг 17, 2009 09:49 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
avl писал(а):
Чтобы реализовать массив или очередь достаточно два стека с контролем пустоты.

и еще один регистр между ними :)
правда доступ будет не random...

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн авг 17, 2009 12:55 
Не в сети
Аватара пользователя

Зарегистрирован: Чт апр 26, 2007 21:09
Сообщения: 303
Благодарил (а): 12 раз.
Поблагодарили: 10 раз.
Так я и списком могу те же операции реализовать!
Более того, как на мой взгляд, так для построения больших и сложных программно-аппаратных комплексов, как раз такая структура, как в Смолток-машине - более "удобна", формализуема и легка в реализации (процессор Катана, например).


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн авг 17, 2009 14:07 
Не в сети
Аватара пользователя

Зарегистрирован: Чт май 18, 2006 08:55
Сообщения: 30
Откуда: Мелмак, Гидра Кентавра
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
mOleg писал(а):
и еще один регистр между ними

А вот и нет!
Доказывается, что если есть конструкция, которая может заменить обязательную переменную-счетчик (её инкремент-декремент) которая в свою очередь является номером ячейки массива то замена двух стеков на массив делается элементарно. Например один из трех стеков используется в качестве счетчика... А вот для двух стеков без контроля пустоты, действительно, проблема открыта — если кто-то сможет — аплодисменты, я не смог :( в отличие от первого случая ;)

Wlad писал(а):
Так я и списком могу те же операции реализовать!

Правильно! Потому что список более "сильная" конструкция и она в простейшем случае эквивалентна очереди которая "сильнее" стека.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн авг 17, 2009 22:44 
Не в сети
Аватара пользователя

Зарегистрирован: Чт апр 26, 2007 21:09
Сообщения: 303
Благодарил (а): 12 раз.
Поблагодарили: 10 раз.
avl писал(а):
А вот для двух стеков без контроля пустоты, действительно, проблема открыта — если кто-то сможет — аплодисменты, я не смог :( в отличие от первого случая ;)

Надо у Котова с Сабельфельдом посмотреть...

avl писал(а):
список более "сильная" конструкция и она в простейшем случае эквивалентна очереди которая "сильнее" стека.

Критерий "сильноты" не озвучите? Я просто к тому, что я примерно могу объяснить подобный критерий минимумом операций с привлечением АЛУ для адресной навигации по адресуемым элементам (в обе стороны, - реализация "+"/"-" в смысле продвижения по элементам ДАННОЙ структуры), но дальше этого - и лень, и времени нет заниматься.
Насколько я помню, в Эльбрусе (и в уже упомянутом Катане) было подобным образом реализовано понятие "текущий контекст исполнения". Но тогда ещё с кэшами проблемы были - дорого было.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт авг 18, 2009 00:22 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
Код:
#define STACKSIZE 2048
int Depth = 0;
int Dstack [STACKSIZE];

int PopStack()
{
    Depth--;
    return Dstack[Depth];
}

void PushStack(int x)
{
    Dstack[Depth] = x;
    Depth ++;
}


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт авг 18, 2009 02:38 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
avl писал(а):
mOleg писал(а):и еще один регистр между ними
А вот и нет!

я имел ввиду регистр для промежуточного хранения данных, так как вершина стека не читаема Ж8)

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт авг 18, 2009 06:27 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
Нечитаемость вершины стека - это какое-то непонятное ограничение.
(от интеля наверно, у которого вершина стека POPой читается)
Элементарный ход POP+PUSH - и вершина прочитана.
А в железяке она торчит на выходе стека постоянно.

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт авг 18, 2009 06:33 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
WingLion писал(а):
Нечитаемость вершины стека - это какое-то непонятное ограничение.

вот именно этот момент меня заставил открыть тему!
Именно поэтому я искал четкое определение того, что есть стек!
По сути, стек, это название некой абстракции (математической\алгоритмической) а не реальное устройство. И у абстракции должно быть четкое описание. Проще говоря, если верхнее значение со стека нельзя прочесть, то однозначно части ФМ TOS и SUB, а так же IP и RTOS - являются регистрами! Еще раз, вопрос возник из-за терминологической неразберихи, которая увы, пока не исчезла 8((

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт авг 18, 2009 06:51 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
иначе говоря, физическая реализация математической абстракции может быть в некоторой степени иной, то есть позволять, к примеру, делать больше, нежели это зафиксировано в мат.описании, конечно, при условии соблюдения основных свойств мат.абстракции.

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

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт авг 18, 2009 07:05 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
кстати, хочу обратить внимание на то, что хотя стек достаточно легко строится на основе массива регистров (особенно в HDL), сам стек является цельным, то есть неделимым устройством. Иначе говоря стек может не состоять из регистров, а значит не иметь дополнительных свойств, предлагаемых регистровой реализацией, и это нормально!
Поэтому, я считаю, что "невозможность чтения и записи верхнего элемента стека" согласуется с его природой согласно Бритвы Оккама 8).

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт авг 18, 2009 07:14 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
Ох, блин. И как же любят эти японцы головы рубить!
И Оккам не исключение.
Зачем нам безголовый стек? Чтобы выглядел по-абстрактнее?
Или для запутывания вероятного сишника?

Пусть нет регистров, будут пули в магазине АК-74.
Но и там можно увидеть верхнюю, а если приглядеться, то ту, что под ней - тоже видно.

Так что, ограничение сие совершенно ненужное...

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт авг 18, 2009 10:12 
Не в сети
Аватара пользователя

Зарегистрирован: Чт май 18, 2006 08:55
Сообщения: 30
Откуда: Мелмак, Гидра Кентавра
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Wlad писал(а):
Надо у Котова с Сабельфельдом посмотреть...

А там, вообще, насколько я помню, проблема двух стеков объявлена как нерешенная, но время то шло...
Wlad писал(а):
Критерий "сильноты" не озвучите?

Надо у Котова с Сабельфельдом посмотреть... ;)

mOleg писал(а):
кстати, хочу обратить внимание на то, что хотя стек достаточно легко строится на основе массива регистров (особенно в HDL), сам стек является цельным, то есть неделимым устройством. Иначе говоря стек может не состоять из регистров, а значит не иметь дополнительных свойств, предлагаемых регистровой реализацией, и это нормально!


Правильно!
Обычно стек и не является массивом переменных (регистров). А на массиве можно задать любое, наперед заданное количество стеков (и даже массивов) — например по ячейкам с номерами вида kn "бегает" первый стек, по kn+1 второй, по kn+2 третий и т. д. до k2n-1
И действительно, обычный стек "безголовый", как Вы изволили выразится, а для DUP, SWAP, ROT и т. п. в таком случае нужны дополнительные регистры или другое его устройство.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт авг 18, 2009 19:58 
Не в сети
Аватара пользователя

Зарегистрирован: Вс май 07, 2006 11:38
Сообщения: 279
Откуда: Slavyansk, Ukraine
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
О, стек!!! В форте ведь нет ограничений "на помечтать"? 8)
Пытаюсь сейчас стек строк от ~day использовать под одну задачку - и так понравилось, что захотелось "многостаночности" - отдельные стеки под адреса, под данные, под строки и т.п. Вплоть до того, что для каждого типа данных свой стек. Вобщем - стекоориентированную среду программирования.

_________________
Банзай!


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 48 ]  На страницу Пред.  1, 2, 3, 4  След.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 9


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB