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

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
 Заголовок сообщения: набросок о словарях форка
СообщениеДобавлено: Вс июл 31, 2011 16:55 
Не в сети
Moderator
Moderator
Аватара пользователя

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


1. Традиционный подход.

Словарная статья представляется записью в базе данных, построенной по
сетевой модели. Каждая запись в этой БД традиционно состоит из четырех полей:
- поля связи (link field) как минимум хранит адресную ссылку на
предыдущее созданное определение;
- поля имени (name field) обычно состоит из счетчика длины имени и
последовательности ключевых символов, идентифицирующих слово;
- поля флагов (flag's field) обычно хранит битовые значения двух флагов:
immediate и smudge ,
- поля данных (code field) в зависимости от методики организации
виртуальной Форт машины (ВФМ) может содержать адресную ссылку, либо
ассемблерный код,
- поля параметров (parameter field) в зависимости от методики
организации ФВМ может содержать данные, код, адреса, но может и
отсутствовать.
Встречаются системы с большим количеством полей в одной записи БД. Вся
совокупность полей, относящихся к одному определению и называется словарной
статьей.
В различных ситуациях любое из перечисленных полей, кроме поля связи,
может содержать не уникальное значение, например, поле имени может относиться
к двум различным записям. Так же, возможна ситуация, когда у одного и того же
кода и данных имеется еще одно имя, то есть такая запись, которая кроме
собственных полей: связи, флагов, имени ссылается на чужие данные и код. Поле
флагов же обычно совпадает у почти всех слов в словаре. Традиционно,
количество полей фиксировано, и, хотя, храниться они могут отдельно друг от
друга структура у всех словарных статей традиционно одинакова (в рамках одной
форт-системы).

?. Словарная статья форка.

Так как в словарной статье единственным уникальным полем является поле
связи, оно в форке считается главным. То есть, получить адрес любого другого
поля возможно, зная именно поле связи. Кроме того, все остальные поля
считаются атрибутами слова, и теоретически могут отсутствовать (практически
есть ограничения). Для работы с полями словарной статьи имеются следующие
слова:
GET-ATTR ( lfa u --> attr 0 | err ) - получить указанный u атрибут слова,
идентифицируемого своим lfa полем связи.
SET-ATTR ( attr lfa u --> 0 | attr err ) - изменить\добавить указанный u
атрибут слова, если это возможно.
В обоих случаях судить об успешности операции можно по возвращаемому
коду err. Атрибутом не обязательно будет одно число - это может быть и число,
и строка, и исполнимый адрес и вообще произвольное количество данных. SET-ATTR
и GET-ATTR - это методы, вызывающие соответствующие процедуры, уникальные для
каждого словаря (или группы словарей). Первые 12 атрибутов зафиксированы за
системой: 8 однобитовых полей:
0. &SMG - признак недоступности слова для find
1. &NON - признак неисполнимости слова
2. &DAS - слово создано с помощью DOES>
3. &VOC - признак того, что слово является словарем
4. &IMM - признак немедленности исполнения слова
5. &ALS - признак слова-заголовка nickname
6. &PRI - слово - примитив
7. &UNUSED - не используется
и четыре основных атрибута, содержащие привычные поля слов:
8. &code - адрес поля кода слова
9. &name - адрес и длину идентификатора id>asc
10. &size - размер слова
11. &prev - адрес предыдущего слова в словаре
Остальные номера свободны для использования.

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

\ получить атрибут идентифицируемый n слова lfa
: (get-attr) ( lfa # --> attr )
DUP SWITCH: (invalid)
(flag) (flag) (flag) (flag)
(flag) (flag) (flag) (flag)
(code) (name) (size) (prev)
;SWITCH ;

именно приведенный метод вызывается словом GET-ATTR при работе со статическим
словарем FORTH. Параметр # в дальнейшем может использоваться, поэтому сохраняется
его копия с помощью DUP .

Получение имени слова реализовано следующим образом:

: ID>ASC ( lfa --> asc # | 0 ) &name GET-ATTR IF FALSE THEN ;

Определение исполнимого адреса:

: LINK>C ( lfa --> xt | 0 ) &code GET-ATTR IF FALSE THEN ;

Получение lfa предыдущего определенного имени:

: LINK> ( lfa --> lfa | 0 ) &prev GET-ATTR IF FALSE THEN ;

Получение битовых атрибутов (immediate, smudge, других):

: ?IMMEDIATE ( lfa --> 1\-1 )
&IMM GET-ATTR THROW
IF imm_word ;THEN
std_word ;

: ?SMUDGED ( lfa --> flag ) &SMG GET-ATTR IF FALSE THEN ;

Аналогичным образом можно устанавливать атрибуты, то есть, устанавливать
атрибуты должен уметь сам словарь, SET-ATTR может попытаться установить
заданный атрибут, но, если словарь не знает, как это делается, операция
вызовет ошибку. Базовый формат словарной статьи описан в
.\kernel\vocbase\header.wrd , там же определены константы, позволяющие
получать стандартные атрибуты.

Формат словарной статьи для статических словарей следующий:
to_link - поле связи, состоящее из следующих адресных полей:
off_link - ссылка на предыдущее определенное в данном словаре слово,
off_vocid - ссылка на родительский словарь,
off_thread - ссылка на предыдущее на треде слово (хешированный поиск),
off_code - ссылка на поле кода (то есть на off_cfa),
to_flag - поле флагов:
off_flags - битовых: &SMG &NON &DAS &VOC &IMM &ALS &PRI ,
off_eow - размер определения (всего два байта),
to_name - поле имени,
off_report - количество ссылок на определение (опциональное поле),
off_name - строка со счетчиком, хранящее идентификатор слова,
причем, идентификатором может быть набор данных произвольной
длины.
off_cfa - поле кода (сюда указывает ссылка из lfa),
off_pfa - поле параметров (следует сразу за полем кода).

Описанный формат словарной статьи на самом деле не важен, он может
меняться от словаря к словарю. Именно для сокрытия устройства словарной статьи
используются слова SET-ATTR и GET-ATTR, а так же использующие их LINK> LINK>C
ID>ASC и т.п. SET-ATTR и GET-ATTR привязаны к словарю. Если посмотреть на
устройство, к примеру, GET-ATTR:

: GET-ATTR ( lfa # --> attr 0 | err )
OVER off_vocid A@ \ --> lfa n vid
*IF off_get-attr A@ CATCH
*IF NIP NIP THEN
;THEN TDROP
NOTICE" атрибут слова получить нельзя" ;

можно увидеть, во-первых, что в качестве параметров используются поле
связи слова lfa и затребуемый номер атрибута #. Так же видно, что ссылка на
родительский словарь используется для ускорения определения имени
родительского словаря. Может случиться так, что слово не связано с каким-то
словарем, тогда атрибуты слова будут недоступны, а так как в форке атрибутами
считаются все поля данных, что либо сделать с таким словом будет нельзя. Таким
образом, абсолютно необходимыми полями в форке являются: _link и _vocid . Все
остальное может быть в зависимости от словаря изменено. Когда родительский
словарь определен, в записи словаря берется значение, хранимое в off_get-attr
и ему передается управление. Структура описателя словаря находится в
.\kernel\vocbase\header.voc .

?. Поиск определений.

Поиск в форке устроен несколько отлично от привычной схемы. Так как
главным полем словарной статьи считается поле связи, все слова, производящие
поиск в словаре (или словарях) возвращают не привычный адрес поля кода, и не
адрес поля имени (либо чего либо еще), а именно адрес поля связи. Механизм
поиска удобнее всего описывать снизу, все начинается с поиска определения по
его имени с помощью слова SEARCH-NAME в единственном указанном словаре:

: SEARCH-NAME ( asc # vid --> lfa | 0 ) DUP off_quest PERFORM ;

то есть, поиска как такового в словаре нет! - есть вызов метода поиска в
словаре. В случае успеха SEARCH-NAME возвращает lfa найденного определения. По
известному lfа с помощью LINK>XTI запрашивается исполнимый адрес xt
определения и признак немедленности исполнения imm :

: LINK>XTI ( lfa | 0 --> xt imm | 0 ) *IF DUP LINK>C SWAP ?IMMEDIATE THEN ;

Явно видно, что, если, определение найдено, т.е. на входе действительный lfa
определения, у словаря сначала запрашивается адрес исполнимого кода ( LINK>C ),
затем признак немедленности исполнения.

С поиском в контексте (т.е. списке словарей) дело обстоит подобным же образом:

: QUEST ( [vid]u asc # --> asc # 0 | lfa )
D>L >R BEGIN R@ WHILE -1 R+
DL@ ROT SEARCH-NAME
*IF >L R> nDROP L> LDROP LDROP ;THEN DROP
REPEAT DL> R> ;

Слово QUEST ищет lfa слова в указанном перечислении словарей [vid]u с
именем, заданным в виде asc # (которое может быть не только текстовой строкой,
а, собственно говоря, вообще чем угодно, единственным ограничением является
количество параметров ключа, т.е. 2). В случае успешного нахождения
возвращается только lfa найденного слова. Поиск в текущем контексте ведется с
помощью:

: SFINDLFA ( asc # --> asc # 0 | lfa ) D>L GET-ORDER DL> QUEST ;

SFINDLFA в явном виде берет содержимое текущего контекста. Ну, и сравнительно
привычный SFIND определен совсем просто:

: SFIND ( asc # --> asc # 0 | xt imm ) SFINDLFA LINK>XTI ;

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

?. Контекст и текущий словарь.

В файле .\kernel\vocbase\context.f реализован стек контекста и ряд самых
необходимых слов для работы с ним. Стек контекста определен в
пользовательской области памяти, это значит, что у каждого потока может быть
задана собственная последовательность поиска. Максимальное количество
словарей в контексте задается в .\options.f с помощью константы #vocabularies.
Определить из системы допустимое количество словарей в контексте можно с
помощью константы WORDLISTS. Работа с контекстом реализована с помощью двух
определений GET-ORDER и SET-ORDER , все остальные определения, работающие с
контекстом реализованы через них.

Кроме GET-ORDER и SET-ORDER в ядре определены следующие слова:
ALSO - аналог DUP для стека данных, копирует верхний словарь на вершине
контекста, таким образом на вершине стека контекста оказывается две копии vid
одного и того же словаря.
only - очищает содержимое контекста, оставляя в нем только самый нижний
словарь. only не стоит путать с ONLY, последний после выполнения
"сбрасывает" состояние контекста в начальное: FORTH NUMBERS ROOT .
WITH - заменяет верхний контекстный словарь указанным (vid).
PREVIOUS - аналог DROP для стека данных, удаляет vid верхнего словаря в
контексте. В случае переопустошения контекста вызывается исключение,
содержимое контекста устанавливается в начальное : FORTH NUMBERS ROOT .

В файле .\kernel\vocbase\current.f описаны определения для работы с
текущим ( CURRENT ) словарем, т.е. словарем в который добавляются новые
определения. Переменная CURRENT так же является пользовательской и в каждом
потоке может быть собственной, для избежания возможного внедрения в процесс
сборки новых определений из конкурирующего потока в системе предусмотрен
механизм блокировки одновременного доступа из разных потоков к одному типу
ресурсов.

Как уже отмечалось, в контексте при инициализации оказывается три
словаря: FORTH NUMBERS ROOT . В словаре ROOT, находящемся на самом дне
контекста находятся необходимые для работы с контекстом слова, а так же другие
определения необходимые для удобной работы с системой. Словарь NUMBERS
распознает числа, а в словаре FORTH находятся основные слова Форт-системы.


?. Словари в форке.

Самое главное отличие от традиционного подхода заключается в том, что
поиск определения в словаре ведется самим словарем. Устройство и работа
словаря определяется двумя структурами, описанными в
.\kernel\vocbase\header.voc .
Структура wordlist хранит уникальные для каждого словаря данные, в то
время, как структура vtable хранит данные, разделяемые одним типом словарей,
то есть, относящимися к нескольким словарям одновременно. Поля каждой из
структур стоит рассмотреть отдельно (перечисление полей идет в порядке их
описания). В структуре wordlist имеются следующие поля:

off_vlink - поле хранит адресную ссылку на предыдущий определенный в
системе словарь.
off_mount - поле хранит адресную ссылку на код, выполняющий монтирование,
т.е. подключение словаря в систему. Данный метод вызывается
один раз при первом подключении словаря, а так же повторно,
если ранее был выполнен метод off_umount.
off_umount - поле хранит адресную ссылку на код, выполняющий демонтирование,
т.е. отключение словаря из форт-системы, (последнее не всегда
возможно), метод может вызываться автоматически при исключении
словаря из контекста форт-системы (данное поведение пока не
реализовано).
off_quest - поле хранит адресную ссылку на код, выполняющий поиск в словаре,
см. SEARCH-NAME
off_vtable - поле хранит адресную ссылку на начало записи структуры vtable.
off_get-attr - поле хранит адресную ссылку на код, выполняющий поиск по заданному
lfa слова (определенного в данном словаре) одного из атрибутов
определения.
off_linkvoc - хранит адресную ссылку на код, выполняющий связь в цепочку
off_vlink словаря, создаваемого данном (т.е. наследника), так
же может использоваться для обеспечения наследования.
off_vname - поле хранит собственное lfa словаря, по которому можно определить
где сам словарь определен.
off_last - хранит адресную ссылку на последнее созданное в словаре слово,
если в словаре слов нет, хранит 0.
off_latest - хранит адресную ссылку на код, возвращающий значение адресной
ссылки на последнее созданное определение.
off_specific - поле может хранить произвольные данные, используется специфически
каждым видом словаре.
off_temp - поле для временного хранения данных.
off_vflags - поле хранит бинарные флаги словаря (размер поля 8 бит).
off_threads# - поле хранит количество тред в текущем словаре, минимальное значение = 1.
off_threads - поле хранит список адресов начала тред, количество адресов определяется
значением, хранимыми в поле off_threads#.

Структура vtable содержит следующие поля:
off_access - мьютекс блокировка доступа к пространству памяти словаря(словарей),
блокирует одновременный доступ из разных потоков к одному типу словарей.
off_allot - поле хранит адрес кода, выполняющего резервирование пространства
для сохранения данных в пространстве словаря (группы словарей).
off_header - поле хранит адрес кода, добавляющего заголовок в словарь(один из группы).
off_conclude - поле хранит адрес кода, завершающего процесс добавления определения
в словарь.
off_vdp - поле хранит адрес первой неиспользованной ячейки в пространстве
словаря (группы словарей), впрочем, последнее действительно только
для статических (обычных для форта) словарей.
off_vdpl - хранит адрес начала кода последнего определяемого слова.
off_set-attr - хранит адрес кода, выполняющего установку\изменение аттрибута слова.
off_align# - поле хранит значение "выравнивания" данных.

Поля off_vdp и off_vdpl стоит рассмотреть отдельно.
В случае привычного (статического) словаря память распределяется из
одного и того же источника (оперативной памяти системы) в одном направлении
(снизу вверх) заданными порциями с помощью ALLOT, то есть, всегда имеется
некая граница памяти DP, выше которой данные не располагаются. Кроме того, в
памяти системы обычно "дырок" (неиспользуемых участков памяти) не бывает,
память занимается только под хранимые данные, слова удалять нельзя. Эта
привычная картина не позволяет работать с динамически меняющимися данными и
накладывает определенные ограничения при реализации ряда алгоритмов (например
генетических). Описанная ситуация терпима, когда речь идет о работе с
небольшим по размеру участком памяти, и становится неудобной, а иногда и
просто неприемлимой (например при работе с файлами).
В форке рассмотренная выше модель использования памяти системы не исключается,
но ею не ограничивается работа с системой. Для примера удобно рассмотреть реализацию
динамических словарей, т.е. таких словарей словарные статьи которых располагаются
в HEAP.

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


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

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


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

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


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

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