Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 21:01

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
 Заголовок сообщения: Устройство словарных статей и словарей в форке
СообщениеДобавлено: Пн ноя 05, 2012 12:19 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Автор: mOleg
Дата публикации: 2012.11.05
публикуется впервые

Устройство словарных статей и словарей в форке.

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

2. Словарная статья форка.
Так как в словарной статье единственным уникальным полем является поле связи, оно в форке считается главным. То есть, получить адрес любого другого поля возможно, зная именно поле связи. Кроме того, все остальные поля считаются атрибутами слова, и теоретически могут отсутствовать (практически есть ограничения). Для работы с полями словарной статьи имеются следующие слова:
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 ;

В форке добавлен флаг &NON , связанный со словом UNFEASIBLE . Данным признаком отмечаются слова, которые нельзя исполнять из консоли, к примеру: R> >R RDROP.

Аналогичным образом можно устанавливать атрибуты, то есть, устанавливать атрибуты должен уметь сам словарь, 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 .

3. Поиск определений.
Поиск в форке устроен несколько отлично от привычной схемы. Так как главным полем словарной статьи считается поле связи, все слова, производящие поиск в словаре (или словарях) возвращают не привычный адрес поля кода, и не адрес поля имени (либо чего либо еще), а именно адрес поля связи. Механизм поиска удобнее всего описывать снизу, все начинается с поиска определения по его имени с помощью слова 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 ;

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

4. Контекст и текущий словарь.
В файле .\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 находятся основные слова Форт-системы.

5. Словари в форке.
Самое главное отличие от традиционного подхода заключается в том, что поиск определения в словаре ведется самим словарем. Устройство и работа словаря определяется двумя структурами, описанными в .\kernel\vocbase\header.voc .
Структура wordlist хранит уникальные для каждого словаря данные, в то время, как структура vtable хранит данные, разделяемые одним типом словарей, то есть, относящимися к нескольким словарям одновременно. Поля каждой из структур стоит рассмотреть отдельно (перечисление полей идет в порядке их описания). В структуре wordlist имеются следующие поля:
off_vlink    - поле  хранит  адресную  ссылку  на  предыдущий  определенный  в 
системе словарь.
off_mount - поле хранит адресную ссылку на код, выполняющий монтирование,
т.е. подключение словаря в систему. Данный метод вызывается
один раз при первом упоминании словаря, а так же повторно,
если ранее был демонтирован.
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, выше которой данные не располагаются. Кроме того, в памяти системы обычно "дырок" (неиспользуемых участков памяти) не бывает, память занимается только под хранимые данные, слова удалять нельзя. Эта привычная картина не позволяет работать с динамически меняющимися данными и накладывает определенные ограничения при реализации ряда алгоритмов (например генетических). Описанная ситуация терпима, когда речь идет о работе с небольшим по размеру участком памяти, и становится неудобной, а иногда и просто неприемлимой (например при работе с файлами). В форке рассмотренная выше модель использования памяти системы не исключается, но ею не ограничивается работа с системой.

6. О монтировании и демонтировании.
Процесс монтирования словаря происходит автоматически каждый раз при упоминании имени словаря либо вызова исполнимого адреса словаря (что одно и то же по сути). Контролировать повторное монтирование словарь должен самостоятельно, т.к. форт-система о состоянии словаря не знает ничего. Операция размонтирования производится принудительно с помощью вызова операции UMOUNT , однако, необходимо иметь ввиду, что не всем словарям необходима данная процедура. После демонтирования словаря все ссылки в его адресное пространство (если таковое имеется) недопустимы. Перед демонтированием словаря из контекста и из переменной CURRENT должны быть удалены все ссылки на данный словарь.

Литература:

1. Что такое словарь
2. «сначала было слово»
3. Слово о Форте. Попытка формализации сути языка
4. Контекстно-ориентированное программирование.

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


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

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


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

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


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

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