Минимальный набор слов Форта

WingLion

Вопрос этот уже обсуждался в SU.FORTH когда-то, но те сообщения у меня давно потерялись, поэтому поднимаю сей вопрос уже здесь.

Вопросов, как таковых, фактически два:

1. Каков минимальный набор команд Форт-Процессора, которого достаточно для реализации полноценного Форта (скажем, стандарта F83)?

2. Каков минимальный набор слов Форта, на которых можно написать всю остальную Форт-Систему (для четкости, тоже F83)?

Hishnik

Насчет процессора:

Манипуляции со стеками:
DUP DROP OVER NIP >R R> Выражаются через них: SWAP ROT
Арифметика
+ - * / AND OR XOR NOT SHL SHR = > <
Управление программой
JMP IF CALL RET
Память
@ ! LIT (загрузка литерала)
Разновидности @ ! требуются для каждого адресного пространства.

WingLion

Хищник писал(а):

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

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

in4 писал(а):

(а значит, и арифметику)

Кстати, совсем не значит. NAND - это побитовое И-НЕ, a в арифметике еще и переносы надо реализовывать.

Через NAND можно реализовать арифметику для чисел расположенных поперек ячеек памяти, т.е. одно число в 0-х битах, следующее в 1-х и т.д. И арифметика окажется параллельной для таких блоков из N-чисел, что, в общем-то и особого смысла иметь не будет...

in4

WingLion писал(а):

Кстати, совсем не значит. NAND - это побитовое И-НЕ, a в арифметике еще и переносы надо реализовывать.

Можно и только логикой и логикой+сдвиги, но я к этому не призываю! Лучше делать нормальный набор.

WingLion

in4 писал(а):

Можно и только логикой и логикой+сдвиги,

Aaaa!...
Вот сдвигов-то и не видно в предлагаемом минимальном наборе!

in4

Хищник писал(а):

Арифметика
+ - * / 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

вместо второго адресного регистра можно стек возвратов использовать и сделать команду обмена между R и A...
для копорования стрoк просто повтор R@+ A!+
Ну, и обработки их похожим образом делать...

"R@+" - это фактически та же железяка, что команду из памяти выбирает

Hishnik

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

WingLion писал(а):

Кстати, совсем не значит. NAND - это побитовое И-НЕ, a в арифметике еще и переносы надо реализовывать.

Абсолютно все реализуется или через базис Шеффера, или через базис Пирса. Переносы тоже. Для случая сложения 0+0=0, 0+1=1, 1+0=1, 1+1=10 (1 в перенос). Таким образом, бит переноса появляется только если оба аргумента равны 1 - это вентиль 2И. 2И делается из 2И-НЕ и НЕ.

Hishnik

in4 писал(а):

* предполагается аппаратное? нет, можно заменить */

Разумеется! Деление вообще сильно сложнее, и если умножение может делаться выделенным блоком за один такт, то с делением так вытворить существенно сложнее. Как правило, деление делается многотактным автоматом.

in4 писал(а):

знаковые/беззнаковые умножение/деление выделять надо? - макс. число (и адрес) будет меньше в 2 раза, если нет беззнаковых значений, такого диапазона хватит для работы?

В принципе, можно. Но это тонкости. "Естественное" умножение беззнаковое.

in4 писал(а):

поподробнее, что они делают? М. лучше использовать флажки проца? Или очень желательно иметь флаг на стеке?
= ведь == AND ? Или лучше четкое FFFF/FFFFFFFF?

Ну в принципе это сравнение. Результат остается на стеке. Флажков у меня вот вообще нет

in4 писал(а):

Как D+ хорошо сделать без переноса?

Гм.. это вопрос. Просто если мне нужна двойная точность, то я просто добавляю регистры нужного размера. Работа с числами двойной длины появляется в том случае, если берется процессор с разрядностью меньшей, чем разрядность данных. В ПЛИС я предпочитаю такого не делать, лучше сразу брать нужную разрядность регистров. Расширение двойной длины - да, видимо, надо. Для этого потребуется флаг переноса.

in4 писал(а):

Удобны адресный регистр и работа с ним a a! a@+

Регистров можно добавлять по вкусу. Но это уже не минимальный набор. Я вообще исхожу из того, что есть полезные вещи, а есть необходимые. Как там - "не берите то, что вам понадобится, берите то, без чего совершенно не сможете обойтись"

Сейчас можно набрать вот таких полезных расширений, но потом получится, что хорошие и эффективные железные и софтварные проекты почему-то обходятся без них. :lol:

WingLion

Хищник писал(а):

Не получается без двух портов на запись. 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

WingLion писал(а):

Хм... А я, когда делал стек на блочной памяти, пару регистров к нему добавлял на вершину - TOP и BOT, и на них-то SWAP без проблем организуется...

У Xilinx есть очень эффективная распределенная. Там регистры не нужны

Точнее, их модно добавить, но необязательно. Хотя идея хорошая, надо отметить.

WingLion писал(а):

Байтовая адресация требует, как минимум, один дополнительный бит адреса. А то и 2 (на 32-хразрядном процессоре).
Так что тут вопрос остается, что лучше, усложнение адресации или усложнение командами манипуляции байтами. Последние, впрочем, в любом случае нужны.

Кстати да. Какой вариант ни возьми, появляются достоинства и недостатки.

WingLion писал(а):

Да, с этим и спору нет. Вопрос лишь в том, что получится, когда имеется операция NAND - побитовое И-НЕ с группами битов - aka регистрами. Морока будет страшная...

Ага, есть такое дело

Характерно, что минимальный арифметико-логический набор сводится к одной-единственной операции. Вот только пользоваться этим все равно, что выполнять сложение, прибавляя по единичке. Можно с точки зрения теории, но на практике совершенно нереально. В чем и смысл, и даже, я бы сказал, искусство проектирования эффективных чипов.

in4

Хищник писал(а):

Абсолютно все реализуется или через базис Шеффера, или через базис Пирса. Переносы тоже. Для случая сложения 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

Минимальный набор слов Форта

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