Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Вт мар 19, 2024 11:02

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 131 ]  На страницу 1, 2, 3, 4, 5 ... 9  След.
Автор Сообщение
 Заголовок сообщения: Минимальный набор слов Форта
СообщениеДобавлено: Вс июл 09, 2006 13:07 
Не в сети
Administrator
Administrator
Аватара пользователя

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

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

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

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

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


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

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7958
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
Насчет процессора:

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


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

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
Хищник писал(а):
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! нету, то в набор "арифметико-логических" команд надо манипуляцию байтами добавлять. обмен старшего и младшего >< как минимум.

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


Последний раз редактировалось WingLion Пн июл 10, 2006 18:18, всего редактировалось 1 раз.

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

Зарегистрирован: Сб май 06, 2006 12:01
Сообщения: 959
Откуда: Украина, Харьков
Благодарил (а): 2 раз.
Поблагодарили: 7 раз.
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
+!
*
*/

_________________
With best wishes, in4.


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

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
in4 писал(а):
(а значит, и арифметику)


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

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

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


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

Зарегистрирован: Сб май 06, 2006 12:01
Сообщения: 959
Откуда: Украина, Харьков
Благодарил (а): 2 раз.
Поблагодарили: 7 раз.
WingLion писал(а):
Кстати, совсем не значит. NAND - это побитовое И-НЕ, a в арифметике еще и переносы надо реализовывать.

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

_________________
With best wishes, in4.


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

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
in4 писал(а):
Можно и только логикой и логикой+сдвиги,

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

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн июл 10, 2006 19:05 
Не в сети

Зарегистрирован: Сб май 06, 2006 12:01
Сообщения: 959
Откуда: Украина, Харьков
Благодарил (а): 2 раз.
Поблагодарили: 7 раз.
Хищник писал(а):
Арифметика
+ - * / 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 адресных регистра... :( С этим я еще работаю...

_________________
With best wishes, in4.


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

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
вместо второго адресного регистра можно стек возвратов использовать и сделать команду обмена между R и A...
для копорования стрoк просто повтор R@+ A!+
Ну, и обработки их похожим образом делать...

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

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


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

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7958
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
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! нету, то в набор "арифметико-логических" команд надо манипуляцию байтами добавлять. обмен старшего и младшего >< как минимум.

Это уже по вкусу, оно не изменяет общую структуру процессора.


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

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7958
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
WingLion писал(а):
Кстати, совсем не значит. NAND - это побитовое И-НЕ, a в арифметике еще и переносы надо реализовывать.

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


Последний раз редактировалось Hishnik Пн июл 10, 2006 20:21, всего редактировалось 1 раз.

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

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7958
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
in4 писал(а):
* предполагается аппаратное? нет, можно заменить */

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

В принципе, можно. Но это тонкости. "Естественное" умножение беззнаковое.
in4 писал(а):
поподробнее, что они делают? М. лучше использовать флажки проца? Или очень желательно иметь флаг на стеке?
= ведь == AND ? Или лучше четкое FFFF/FFFFFFFF?

Ну в принципе это сравнение. Результат остается на стеке. Флажков у меня вот вообще нет :)
in4 писал(а):
Как D+ хорошо сделать без переноса?

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

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


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

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
Хищник писал(а):
Не получается без двух портов на запись. 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 регистрами. Морока будет страшная...

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


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

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7958
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
WingLion писал(а):
Хм... А я, когда делал стек на блочной памяти, пару регистров к нему добавлял на вершину - TOP и BOT, и на них-то SWAP без проблем организуется...

У Xilinx есть очень эффективная распределенная. Там регистры не нужны :) Точнее, их модно добавить, но необязательно. Хотя идея хорошая, надо отметить.


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

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

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн июл 10, 2006 21:48 
Не в сети

Зарегистрирован: Сб май 06, 2006 12:01
Сообщения: 959
Откуда: Украина, Харьков
Благодарил (а): 2 раз.
Поблагодарили: 7 раз.
Хищник писал(а):
Абсолютно все реализуется или через базис Шеффера, или через базис Пирса. Переносы тоже. Для случая сложения 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

_________________
With best wishes, in4.


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

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


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

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


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

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