Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Ср ноя 13, 2019 18:13

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 10 ] 
Автор Сообщение
 Заголовок сообщения: "Примитивный" Форт
СообщениеДобавлено: Вс апр 08, 2007 05:32 
Не в сети

Зарегистрирован: Сб дек 09, 2006 07:31
Сообщения: 11
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
(звиняюсь, если вдруг запостил не туда, сам в сомнениях)

Началось все с того, что я решил написать компактное форт-ядро для Z80 (сам Форт использовался бы только для логики и экономии памяти, критические участки в любом случае предполагалось реализовать в виде крупных примитивов) - то есть никакого редактора, никакой командной строки (и вообще входного потока), даже словаря - форт-программу предполагалось отлаживать на x86 Форте, а затем генерировать текстовый файл для Z80 кросс-ассемблера.

Таким образом, оставалось написать только основные примитивы и служебные процедуры типа $COL, ;S и NEXT. Первым делом я конечно полез посмотреть исходник ZX-Forth для Спектрума... и пришел в ужас, прикинув его быстродействие! Ну ладно еще неоптимальные примитивы, дело поправимое; но вот NEXT, сжирающий аж 68 тактов - это ни в какие ворота (для сравнения - обычный call+ret - 27 тактов). И тут уж ничего не поделаешь - система команд Z80 не позволяет сделать быстрее (вот на x86 все выглядело естественно).

Вот что там было:

bc = PFA pointer
ix = RP (растет вниз почему-то)

$COL (минимум 134 такта)
dec ix
dec ix
ld (ix+0),c
ld (ix+1),b
ld c,e
ld b,d
jp NEXT

;S (минимум 126 тактов)
ld c,(ix+0)
ld b,(ix+1)
inc ix
inc ix
jp NEXT

NEXT (68 тактов)
ld a,(bc)
ld l,a
inc bc
ld a,(bc)
ld h,a
inc bc
ld e,(hl)
inc hl
ld d,(hl)
inc hl
ex de,hl
jp hl

И тут мне пришло в голову: можно избавиться от лишней операции конвертации ссылки в значение, если упразднить поле команды (пускай в ячейках поля параметров стоят сразу адреса исполняемого кода, а не CFA). То есть фактически все слова считаются "примитивами". Спрашивается, как реализовать реентерабельные процедуры (слова типа : ... ; итп)? А очень просто - весь "код" будет состоять из одной команды "call $COL", а дальше сразу расположен обычный список начальных адресов. Процедура $COL тогда просто снимет новое значение PFA со стека.

Подробнее:

de = PFA pointer
RP растет навстречу SP

call $COL ; вместо адреса $COL в CFA
...
$COL (111 тактов на все, считая call)
ld hl,RP ; никакой выгоды хранить RP в регистре
ld (hl),e
inc l ; уж стеки-то могут быть всегда выровнены
ld (hl),d
inc hl
ld (RP_adr),hl
RESUME
pop hl
ld e,(hl)
inc hl
ld d,(hl)
inc hl
ex de,hl
jp hl

;S (94 такта на все, считая NEXT)
ld hl,(RP_adr)
dec hl
ld d,(hl)
dec l
ld e,(hl)
ld (RP_adr),hl
NEXT (всего 38 тактов!)
ex de,hl
ld e,(hl)
inc hl
ld d,(hl)
inc hl
ex de,hl
jp hl

И теперь еще проще делать кодовые вставки непосредственно в тело форт-процедуры:
"...Adr, Adr, Adr, thisAdr+2, <code>, call RESUME, Adr, Adr, Adr..."
а еще лучше:
"...Adr, Adr, Adr, thisAdr+2, <code>, "ld de,thisAdr+6", "jp"-->, Adr, Adr, Adr..."

А вам всем я хотел бы задать пару вопросов:

1) Не изобрел ли я велосипед, :oops: и если да - где можно почитать о чем-то подобном? Просьба сразу ногами не бить, Фортом занимаюсь эпизодически, времени на предварительный поиск ушло бы много... даже этот форум просматривать некогда. :shuffle;

2) Какие проблемы (в том числе по совместимости с прочими версиями) могут возникнуть в случае разворачивания описанного ядра в полноценную Форт-систему? (подумываю переделать свой старый досовский Форт в таком духе, хотя на x86 выигрыш меньше). Известно ли, по каким причинам Ч.Мур создал именно то, что создал (а не более эффективный вариант)? Возможно, дело было просто в архитектуре доступных ему на тот момент процессоров?

Заранее спасибо.


Последний раз редактировалось Lethargeek Вт апр 10, 2007 14:22, всего редактировалось 1 раз.

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

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 6812
Благодарил (а): 16 раз.
Поблагодарили: 111 раз.
Все правильно, получается машинный код. Он состоит из словарных статей примитивов, написанных на ассемблере, и слов, написанных на Форте, внутри которых делается call на адреса примитивов и push lit (это условно - код для заталкивания в стек литералов). Такой подход становится удобным, если есть возможность разделить адресные пространства кода и данных (хотя бы разнести их в памяти, если речь идет о Z80). Тогда данные не будут перемежаться с кодом и отпадет необходимость в механизме CFA-PFA. После LFA, NFA можно будет сразу писать машинный код.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вс апр 08, 2007 11:35 
Не в сети

Зарегистрирован: Сб май 06, 2006 12:01
Сообщения: 959
Откуда: Украина, Харьков
Благодарил (а): 2 раз.
Поблагодарили: 7 раз.
Lethargeek писал(а):
где можно почитать о чем-то подобном?

Форт-литература на forth.org.ru
Обязательно прочитать - Язык Форт и его реализации. С.Н. Баранов, Н.Р. Ноздрунов. Там есть примеры для К580 - такой код будет работать и у тебя! Я для изучения использовал Форт для К580 и эту замечательную книгу! Вон она и сейчас недалеко лежит!
Moving Forth. Brad Rodriguez очень желательно, если можешь английский, я уж не помню, на каком сам читал... :( Тут есть особенности реализации для разных типов процов и примеры для них. ОЧЧень познавательно!
Броуди - если хочешь познакомится с историей и улучшить свой стиль программирования на Форте. Эти книги - один из лучших учебников программирования, которые мне попадались!

Если очень надо, поищу эмуляторы 580-го с Форт-системами, можешь погуглить или спросить - найду.
Есть еще Форт-компилятор для РК-86. Жаль, я его поздно увидел. :( Но хочется разобрать его в подробностях.

И, если ты достаточно крут в программировании и английском, могу посоветовать приглянуться к colorForth и моему варианту ColorLessColorForth (CLCF, бесцветный ColorForh)- для автономных небольших систем может быть хорошим решением. Правда, язык отличается от обычного Форта стилем программирования - тут надо думать по-другому! Лично мне эта система кажется очень перспективной. Из людей, о которых я знаю, им занимается не так много. Русскоговорящих знаю только двух кроме себя, один из них - profit - тоже тут на форуме... ;) Пока реализован только на Форт-процессорах и PC... Ну, еще я делал компиляторы для микроконтроллеров... На днях будет очередной для AVR.
Про особенности на русском можно прочитать тут:
Переводы с буржуинского :-)
Новые диалекты Форта. ColorForth и др.

_________________
With best wishes, in4.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вс апр 08, 2007 12:01 
~pinka ещё занимается ForthML. Это тоже идейно близко к colorForth, если не по букве, то по духу -- точно.

А вообще -- in4, я понимаю, вы увлечены темой и хочется заиметь одномышленников, но чего людям сразу под нос тензорный анализ подсовывать (ага, я немножко чуть-чуть слегка знаю что colorForth проще чем Forth, но я то имею в виду не "простоту", а время на освоение)?..

Тема-то не об этом. Я вопрос вижу так: "насколько хороша описанная в начале тема реализация шитого кода?". Всё.

(хорошо бы расписать варианты, плюсы и минусы вариантов шитого кода в каком нибудь удобоваримом для чтения виде, с учётом имеющихся сегодя реализаций...)


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вс апр 08, 2007 14:22 
Не в сети

Зарегистрирован: Сб дек 09, 2006 07:31
Сообщения: 11
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
in4 писал(а):
Moving Forth. Brad Rodriguez...

Ага, таки открыл америку. :oops: И как мне раньше этот текст не попался? :roll:

То, что мне нужно, там называется DTC (мне в принципе и STC в голову приходил, но я не рискнул его Фортом называть). :) Правда, поверхностно изучив источник, кое-с-чем уже не согласен... бум думать. Мне интересно, какие "подводные камни" возникают из-за особенностей реализации (особенно при всяких издевательствах над словарем).

Вот видимо оно:
"[LOE81] Loeliger, R. G., Threaded Interpretive Languages, BYTE Publications (1981), ISBN 0-07-038360-X. May be the only book ever written on the subject of creating a Forth-like kernel (the example used is the Z80). Worth it if you can find a copy."
...однако аннотация оптимизма не внушает. Она вообще где-нить есть в электронном виде? Английский не проблема.

P.S. За ColorForth итд еще возьмусь, ежели время будет. Увы, сейчас почти вся нервная энергия уходит в другом направлении.


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

Зарегистрирован: Сб май 06, 2006 12:01
Сообщения: 959
Откуда: Украина, Харьков
Благодарил (а): 2 раз.
Поблагодарили: 7 раз.
Lethargeek писал(а):
Ага, таки открыл америку.

Молодец! Главное - сам! :) Я тоже сделал много таких открытий! :)
Lethargeek писал(а):
Мне интересно, какие "подводные камни" возникают из-за особенностей реализации (особенно при всяких издевательствах над словарем).

Да, вроде, только скорость и удобство/размер реализации. Мне для 16-разрядных версий хватало обычного односвязного списка из Баранова...
Если нужна более сложная работа - несколько словарей, увеличение скорости поиска, отображение сложных структур данных на словари, ооп на словарях - см. SPF - тут есть несколько мощных реализаций.
А для маленьких систем снова прорекламирую... ;) Сейчас я использую выделенные в отдельной области словари фиксированного размера, как в ColorForth-е - можно делать слова с несколькими точками входа. Текущая реализация немного хромает - она больше похожа на обычную - имя 14 байт с дополнением \0 и точка входа 2 байта. Начало всегда выровнено на 16 байт, поэтому красиво выглядит на дампе. Свою задачу - какое нибудь работающее решение - этот вариант выполняет!
А на будущее я подумываю о базе данных с несколькими индексами и хранением не только кода/исходников, но и другой связанной информации- рисунков, схем, звуков, урл-ов.
Lethargeek писал(а):
P.S. За ColorForth итд еще возьмусь, ежели время будет. Увы, сейчас почти вся нервная энергия уходит в другом направлении.

Можно не торопиться, если надо будет, сам к этому прийдешь! ;)

_________________
With best wishes, in4.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср авг 15, 2007 06:36 
Не в сети

Зарегистрирован: Сб дек 09, 2006 07:31
Сообщения: 11
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Провел в свободное время кучу самых диких экспериментов, в итоге оказалось по скорости (а часто и по размеру) самое выгодное - оптимизирующий компилятор на основе STC, но при этом использующий машинный стек Z80 именно как стек данных (либо сразу после входа адрес снимается, либо нужные параметры перед вызовом примитива). Недостаток - тормозные "высокоуровневые" слова, использующие стек возвратов. Однако во многих случаях (когда не предусматривается повторной входимости) стек возвратов не особенно-то и нужен, гораздо быстрее сохранять адрес в теле самой процедуры. В связи с этим вопрос: существуют ли более-менее стандартные реализации нереентрабельных процедур, какие-нить договоренности итд? В указанной литературе ничего не нашел (если проглядел, ткните носом) :shuffle;


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

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

Для сравнения 'америк' код Z80 из исходников форта для Спринтера:

Код:
;**************************
execute_execute:
   POP HL      ; CFA
   EI
   JP NEXT2

DOES_EXE:               ; <- CALL из WORDxx
   POP HL      ; адрес возврата - новый адрес интерпретации
   PUSH DE      ; в стек попадает PFA слова
   EX DE,HL   ; DE - адрес интерпретации

ADR_INTERPRET:      ; IX - return_stack
   EI      ; SP - data_stack
         ; BC - interpret_adress
         ; DE - вершина стека данных???
;   POP DE      ; вытащить адрес новый интерпретации
   DEC IX
   LD (IX),B   ; забить BC в стек возвратов
   DEC IX
   LD (IX),C
   LD C,E
   LD B,D      ; забить поле параметров статьи в адрес интерпретации
   JR NEXT

NEXT_V:
   PUSH DE


NEXT:
   EI
   LD A,(BC)
   LD L,A
   INC BC
   LD A,(BC)   ; BC - адрес поля кода
   LD H,A
   INC BC      ; HL - указывает на адрес поля кода
         ; следующей исполняемой статьи
NEXT2:         ; (для форт-определений это ADR_INT)
   LD E,(HL)
   INC HL
   LD D,(HL)
   INC HL
   EX DE,HL   ; DE - адрес поля параметров исполняемого слова
;   PUSH DE      ; вершина стека - DE - адрес поля параметров
   DI
   JP (HL)      ; HL - исполняемый адрес

;**************************


Такты не считал, т.к. уже не помню все.
Кажущиеся лишними EI,DI в коде были для чего-то принципиальны.

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


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

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 4997
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 20 раз.
Поблагодарили: 58 раз.
Lethargeek писал(а):
Провел в свободное время кучу самых диких экспериментов, в итоге оказалось по скорости (а часто и по размеру) самое выгодное - оптимизирующий компилятор на основе STC,

гм, а примеры можно?
кстати если можно то сравнение по скорости STC\DTC\ITC ?
собственно более всего интересует на сколько STC выигрывает у DTC ?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт авг 16, 2007 07:57 
Не в сети

Зарегистрирован: Сб дек 09, 2006 07:31
Сообщения: 11
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
mOleg писал(а):
гм, а примеры можно?
кстати если можно то сравнение по скорости STC\DTC\ITC ?
собственно более всего интересует на сколько STC выигрывает у DTC ?


"Примеры" чего, компилятора? Он пока существует только в виде кучки макросов для кросс-ассемблера (так было проще тестировать), и весьма далек от завершения... если интересуют отдельные примитивы в качестве, то чуть попозже.

Пока, чтобы не загромождать кодом, даю сводную таблицу по скорости некоторых примитивов и логики шитого кода (Reenter - стандартный вызов процедуры со стеком возвратов, Enter - однократный вход-выход с запоминанием адреса в теле процедуры), NEXT (где он есть) засчитан как часть примитива. STC - "чистый" без разворачивания, только call и jmp; NCC (native code compiler) в таблице - без оптимизации. ITC за давностью уже не нашел.

Код:
                DTC    STC     NCC

NEXT             38     27    0/27/39

Reenter (+ ;S ) 205     27      95
Enter   (+back) 112      -      53

lit              83     68      21
?branch          78     69      28
dup              49     51      11
drop             48     51      10
swap             67     71      25
@                66     63      24
!                86     71      44
+                67     67      25
-                75     71      33
1+               44     33       6
>r              104     62      69
r>              105     61      70


DTC     IP=de, TOS=bc, PSP=sp, RSP=mem
STC     IP=pc, TOS=de, PSP=hl, RSP=sp
NCC     IP=pc, TOS=de, PSP=sp, RSP=bc


Как видно, на длинных цепочках примитивов STC из-за неэффективности программной эмуляции стека параметров не дает почти никаких преимуществ над DTC, однако сильно выигрывает при большой вложенности "высокоуровневых процедур". А вот с NCC картина совершенно другая - выигрыш в разы по примитивам у обоих методов и по процедурам у DTC (причем по размеру NCC будет мало отличаться от STC, благо на Z80 куча 1-2-3-байтных команд).

Еще больший выигрыш (и по скорости, и по размеру) даст оптимизация по двум направлениям:
1) Разные варианты макросов в зависимости от известного состояния регистров
2) Замена (через откат назад) известных сочетаний типа "- NEG", "LIT @", "<LOp> ?BRANCH" итд соответствующими "скрытыми" примитивами


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

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


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

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


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

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