Пока у меня совсем нет времени закончить работу над описанием словарей в форке. Поэтому пока пусть тут полежит набросок
Устройство словарных статей и словарей в форке.
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.
|