Forth http://fforum.winglion.ru/ |
|
Минимальный набор слов Форта http://fforum.winglion.ru/viewtopic.php?f=9&t=100 |
Страница 1 из 9 |
Автор: | WingLion [ Вс июл 09, 2006 13:07 ] |
Заголовок сообщения: | Минимальный набор слов Форта |
Вопрос этот уже обсуждался в SU.FORTH когда-то, но те сообщения у меня давно потерялись, поэтому поднимаю сей вопрос уже здесь. Вопросов, как таковых, фактически два: 1. Каков минимальный набор команд Форт-Процессора, которого достаточно для реализации полноценного Форта (скажем, стандарта F83)? 2. Каков минимальный набор слов Форта, на которых можно написать всю остальную Форт-Систему (для четкости, тоже F83)? |
Автор: | Hishnik [ Пн июл 10, 2006 17:45 ] |
Заголовок сообщения: | |
Насчет процессора: Манипуляции со стеками: DUP DROP OVER NIP >R R> Выражаются через них: SWAP ROT Арифметика + - * / AND OR XOR NOT SHL SHR = > < Управление программой JMP IF CALL RET Память @ ! LIT (загрузка литерала) Разновидности @ ! требуются для каждого адресного пространства. |
Автор: | WingLion [ Пн июл 10, 2006 18:07 ] |
Заголовок сообщения: | |
Хищник писал(а): DUP DROP OVER NIP >R R> Выражаются через них: SWAP ROT Для процессора SWAP лучше сразу делать одной командой, а то лишнее время на "сложносочиненное" определение будет. Для реализации SWAP, просто одновременно задействовать "путь данных" от DROP и DUP. И R@ и RDROP надо бы добавить в набор, опять же, чтобы не городить огород там, где его можно не делать. : R@ R> DUP >R ; и : RDROP R> DROP ; -- еще и лишнюю глубину стека данных используют. Хищник писал(а): JMP IF CALL RET Кстати, чистый JMP эквивалентен CALL RDROP, что можно за раз делать, т.е. не кодировать в железе JMP специально. IF - это по идее то же что и ?BRANCH, думаю лучше так назвать эту команду, чтобы не путать с IF-ом языка Хищник писал(а): @ ! LIT
Если C@ и C! нету, то в набор "арифметико-логических" команд надо манипуляцию байтами добавлять. обмен старшего и младшего >< как минимум. |
Автор: | in4 [ Пн июл 10, 2006 18:17 ] |
Заголовок сообщения: | |
WingLion писал(а): Вопрос этот уже обсуждался в SU.FORTH когда-то, но те сообщения у меня давно потерялись Обсуждение (чуть больше года назад) затихло без доказанного минимального набора Судя по вопросу, не будем рассматривать варианты: - однокомандных процов (читал о 2х вариантах, подробности надо искать) - "3х командного Форта" - название автора (чтение байта, запись байта, переход по адресу) Пока напомню основные моменты обсуждения: Dmitry Ponyatov писал(а): (entry) INTERPRET PADsz BL WORDS . H. S. BYE ?EMIT EMIT ?KEY KEY / * - + XOR AND OR NOT > < <> = ! @ DEPTH PICK -ROT ROT OVER SWAP DROP DUP Этот набор команд признали избыточным, с него началось обсуждение. Kirill Timofeev писал(а): ИМХО для постpоения полной фоpт-системы достаточно следующих пpимитивов: !, @, D+, NAND, LIT, <0, EXTERNAL. Если делать виpтуальную машину и запихивать эти слова в опкоды надо добавить еще NOOP. В пpинципе <0 можно pеализовать чеpез дpугие слова, но это pезко снизит и так не высокую скоpостpельность данной системы. Слово EXTERNAL нужно для связи с host-OS, хотя в пpинципе можно сделать это взаимодействие memory-mapped. Для обычной реализации этих слов недостаточно! Ilia Tarasov писал(а): NAND - И-HЕ.(исправлено IN) Получается базис Шеффера, на котором в принципе можно сделать всю логику (а значит, и арифметику). Я бы даже оставил ! @ NAND LIT в качестве базового набора Только это получится совсем уж урезанная система, на которой хорошо заниматься доказательством того, что даже такого минимального набора достаточно. Hо как правило, если уж делается какое-то слово из определенного класса (стековые манипуляции или там арифметика), то очень просто по аналогии сделать и другие несложные слова из этого класса. Трудоемкость мизерная, а выигрыш сразу проявляется. Igor Nikolayenko писал(а): Вот уже определилось, что лучше работать с целыми CELL, а не бить их на
CHAR. Это для минимального набора, м. и не оптимального. Я считаю, что CHAR-адресация нужна, если много строковых операций. Обсуждаемо. Если есть возможность писать в кодах целевой системы, для написания компилятора, похоже (буду еще проверять, потом точно скажу) хватит: для colorForth-а (на нем можно и остальное!) Код: 1, 2, [ ] forth macro : ; ?lit drop ?dup набор примитивов colorForth Мура (и близко к его процам с минимальным набором команд) Код: word; jmp
if jmp if 0 word call -if jmp if >= ; ret @ TOS@ @+ a@++ n dup,TOS=n @r r@ @ ! a! a@ drop !+ !r 2* 2/ - neg and or xor + *+ шаг умножения push a dup over pop a! drop nop [дополнительно] nip swap +! * */ |
Автор: | WingLion [ Пн июл 10, 2006 18:33 ] |
Заголовок сообщения: | |
in4 писал(а): (а значит, и арифметику)
Кстати, совсем не значит. NAND - это побитовое И-НЕ, a в арифметике еще и переносы надо реализовывать. Через NAND можно реализовать арифметику для чисел расположенных поперек ячеек памяти, т.е. одно число в 0-х битах, следующее в 1-х и т.д. И арифметика окажется параллельной для таких блоков из N-чисел, что, в общем-то и особого смысла иметь не будет... |
Автор: | in4 [ Пн июл 10, 2006 18:43 ] |
Заголовок сообщения: | |
WingLion писал(а): Кстати, совсем не значит. NAND - это побитовое И-НЕ, a в арифметике еще и переносы надо реализовывать.
Можно и только логикой и логикой+сдвиги, но я к этому не призываю! Лучше делать нормальный набор. |
Автор: | WingLion [ Пн июл 10, 2006 18:58 ] |
Заголовок сообщения: | |
in4 писал(а): Можно и только логикой и логикой+сдвиги,
Aaaa!... Вот сдвигов-то и не видно в предлагаемом минимальном наборе! |
Автор: | in4 [ Пн июл 10, 2006 19:05 ] |
Заголовок сообщения: | |
Хищник писал(а): Арифметика + - * / AND OR XOR NOT SHL SHR = > < * предполагается аппаратное? нет, можно заменить */ */ вместо или кроме / знаковые/беззнаковые умножение/деление выделять надо? - макс. число (и адрес) будет меньше в 2 раза, если нет беззнаковых значений, такого диапазона хватит для работы? Хищник писал(а): Арифметика = > < поподробнее, что они делают? М. лучше использовать флажки проца? Или очень желательно иметь флаг на стеке? = ведь == AND ? Или лучше четкое FFFF/FFFFFFFF? Хищник писал(а): Управление программой
JMP IF CALL RET Как D+ хорошо сделать без переноса? У Мура 2 перехода, if по =0 и -if по знаку. Из-за D+ мне понадобился по переносу... Даже готов смириться с отсутствием инверсных сравнений. R@ очень желательно, тогда RS можно использовать как локальную переменную Удобны адресный регистр и работа с ним a a! a@+ попробовал реализовать строки - похоже, надо 2 адресных регистра... С этим я еще работаю... |
Автор: | WingLion [ Пн июл 10, 2006 19:38 ] |
Заголовок сообщения: | |
вместо второго адресного регистра можно стек возвратов использовать и сделать команду обмена между R и A... для копорования стрoк просто повтор R@+ A!+ Ну, и обработки их похожим образом делать... "R@+" - это фактически та же железяка, что команду из памяти выбирает |
Автор: | Hishnik [ Пн июл 10, 2006 20:04 ] |
Заголовок сообщения: | |
WingLion писал(а): Для процессора SWAP лучше сразу делать одной командой, а то лишнее время на "сложносочиненное" определение будет. Для реализации SWAP, просто одновременно задействовать "путь данных" от DROP и DUP. Не получается без двух портов на запись. SWAP модифицирует две ячейки стека. ROT - три. Все остальные слова - по одной. WingLion писал(а): И R@ и RDROP надо бы добавить в набор, опять же, чтобы не городить огород там, где его можно не делать. : R@ R> DUP >R ; и : RDROP R> DROP ; -- еще и лишнюю глубину стека данных используют. Тут, кстати, по вкусу. У меня обычно R> >R RDROP R@. WingLion писал(а): Кстати, чистый JMP эквивалентен CALL RDROP, что можно за раз делать, т.е. не кодировать в железе JMP специально. В принципе эквивалентен. Но получается опять-таки две транзакции со стеком возвратов. А если кодировать отдельно, то никаких лишних перестановок данных делать не надо. WingLion писал(а): IF - это по идее то же что и ?BRANCH, думаю лучше так назвать эту команду, чтобы не путать с IF-ом языка Так проще IF переходит, если на стеке ноль. WingLion писал(а): Если C@ и C! нету, то в набор "арифметико-логических" команд надо манипуляцию байтами добавлять. обмен старшего и младшего >< как минимум.
Это уже по вкусу, оно не изменяет общую структуру процессора. |
Автор: | Hishnik [ Пн июл 10, 2006 20:11 ] |
Заголовок сообщения: | |
WingLion писал(а): Кстати, совсем не значит. NAND - это побитовое И-НЕ, a в арифметике еще и переносы надо реализовывать.
Абсолютно все реализуется или через базис Шеффера, или через базис Пирса. Переносы тоже. Для случая сложения 0+0=0, 0+1=1, 1+0=1, 1+1=10 (1 в перенос). Таким образом, бит переноса появляется только если оба аргумента равны 1 - это вентиль 2И. 2И делается из 2И-НЕ и НЕ. |
Автор: | Hishnik [ Пн июл 10, 2006 20:20 ] |
Заголовок сообщения: | |
in4 писал(а): * предполагается аппаратное? нет, можно заменить */ Разумеется! Деление вообще сильно сложнее, и если умножение может делаться выделенным блоком за один такт, то с делением так вытворить существенно сложнее. Как правило, деление делается многотактным автоматом. in4 писал(а): знаковые/беззнаковые умножение/деление выделять надо? - макс. число (и адрес) будет меньше в 2 раза, если нет беззнаковых значений, такого диапазона хватит для работы? В принципе, можно. Но это тонкости. "Естественное" умножение беззнаковое. in4 писал(а): поподробнее, что они делают? М. лучше использовать флажки проца? Или очень желательно иметь флаг на стеке? = ведь == AND ? Или лучше четкое FFFF/FFFFFFFF? Ну в принципе это сравнение. Результат остается на стеке. Флажков у меня вот вообще нет in4 писал(а): Как D+ хорошо сделать без переноса? Гм.. это вопрос. Просто если мне нужна двойная точность, то я просто добавляю регистры нужного размера. Работа с числами двойной длины появляется в том случае, если берется процессор с разрядностью меньшей, чем разрядность данных. В ПЛИС я предпочитаю такого не делать, лучше сразу брать нужную разрядность регистров. Расширение двойной длины - да, видимо, надо. Для этого потребуется флаг переноса. in4 писал(а): Удобны адресный регистр и работа с ним a a! a@+
Регистров можно добавлять по вкусу. Но это уже не минимальный набор. Я вообще исхожу из того, что есть полезные вещи, а есть необходимые. Как там - "не берите то, что вам понадобится, берите то, без чего совершенно не сможете обойтись" Сейчас можно набрать вот таких полезных расширений, но потом получится, что хорошие и эффективные железные и софтварные проекты почему-то обходятся без них. |
Автор: | WingLion [ Пн июл 10, 2006 20:42 ] |
Заголовок сообщения: | |
Хищник писал(а): Не получается без двух портов на запись. SWAP модифицирует две ячейки стека. ROT - три. Все остальные слова - по одной. Хм... А я, когда делал стек на блочной памяти, пару регистров к нему добавлял на вершину - TOP и BOT, и на них-то SWAP без проблем организуется... Хищник писал(а): У меня обычно R> >R RDROP R@. Вот этой группы, и по-моему, достаточно Хищник писал(а): В принципе эквивалентен. Но получается опять-таки две транзакции со стеком возвратов. А если кодировать отдельно, то никаких лишних перестановок данных делать не надо. Соглашусь. Отдельный JMP полезен хотя бы для того, чтобы стек возвратов на лишнюю ячейку не увеличивать. Хищник писал(а): Это уже по вкусу, оно не изменяет общую структуру процессора. Байтовая адресация требует, как минимум, один дополнительный бит адреса. А то и 2 (на 32-хразрядном процессоре). Так что тут вопрос остается, что лучше, усложнение адресации или усложнение командами манипуляции байтами. Последние, впрочем, в любом случае нужны. Хищник писал(а): Абсолютно все реализуется или через базис Шеффера, или через базис Пирса. Переносы тоже. Для случая сложения 0+0=0, 0+1=1, 1+0=1, 1+1=10 (1 в перенос). Таким образом, бит переноса появляется только если оба аргумента равны 1 - это вентиль 2И. 2И делается из 2И-НЕ и НЕ.
Да, с этим и спору нет. Вопрос лишь в том, что получится, когда имеется операция NAND - побитовое И-НЕ с группами битов - aka регистрами. Морока будет страшная... |
Автор: | Hishnik [ Пн июл 10, 2006 21:06 ] |
Заголовок сообщения: | |
WingLion писал(а): Хм... А я, когда делал стек на блочной памяти, пару регистров к нему добавлял на вершину - TOP и BOT, и на них-то SWAP без проблем организуется... У Xilinx есть очень эффективная распределенная. Там регистры не нужны Точнее, их модно добавить, но необязательно. Хотя идея хорошая, надо отметить. WingLion писал(а): Байтовая адресация требует, как минимум, один дополнительный бит адреса. А то и 2 (на 32-хразрядном процессоре). Так что тут вопрос остается, что лучше, усложнение адресации или усложнение командами манипуляции байтами. Последние, впрочем, в любом случае нужны. Кстати да. Какой вариант ни возьми, появляются достоинства и недостатки. WingLion писал(а): Да, с этим и спору нет. Вопрос лишь в том, что получится, когда имеется операция NAND - побитовое И-НЕ с группами битов - aka регистрами. Морока будет страшная...
Ага, есть такое дело Характерно, что минимальный арифметико-логический набор сводится к одной-единственной операции. Вот только пользоваться этим все равно, что выполнять сложение, прибавляя по единичке. Можно с точки зрения теории, но на практике совершенно нереально. В чем и смысл, и даже, я бы сказал, искусство проектирования эффективных чипов. |
Автор: | in4 [ Пн июл 10, 2006 21:48 ] |
Заголовок сообщения: | |
Хищник писал(а): Абсолютно все реализуется или через базис Шеффера, или через базис Пирса. Переносы тоже. Для случая сложения 0+0=0б 0+1=1б 1+0=1б 1+1=10 (1 в перенос). Таким образом, бит переноса появляется только если оба аргумента равны 1 - это вентиль 2И. 2И делается из 2И-НЕ и НЕ.
Сдвиг все равно нужен! Иначе поразрядными операциями не обойтись... cy(x,y)=x & y - выделение битов, из которых есть перенос add(x,y)= (x v y) & ^c - сложение без учета переносов c=y x=add(x,c) И повторять(прибавлять переносы) пока c'<>0 с'=cy(x,c)<<1; x=add(x,c'), максимум разрядность x,y раз В конце x== +(x,y) на Форте Код: : add ( x y -- x+y ) DUP IF OVER OVER AND >R OR R@ INVERT AND R> 1 LSHIFT RECURSE EXIT THEN DROP ; или Код: : add ( x y -- x+y ) BEGIN DUP WHILE OVER OVER AND >R OR R@ INVERT AND R> 1 LSHIFT REPEAT DROP ; проверено на простых примерах Код: 1 1 add 1 add 3 add 2 add 7 add 15 add
|
Страница 1 из 9 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |