Примеры структур данных

Перейти вниз

Примеры структур данных

Сообщение автор Gudleifr в Вт Янв 23, 2018 10:35 pm

Статья BRAD RODRIQUEZ, PATTERNFORTH: A PATTERN-MATCHING LANGUAGE FOR REAL-TIME CONTROL, MY 1989 M.S. DISSERTATION AT BRADLEY UNIVERSITY валялась у меня в столе уже лет десять. Как пример того, что на базе FORTH можно быстро слепить что-то достаточно мощное. В данном случае - пародию на SNOBOL.
Если угодно, книга Таунсенда и Фохта "Проектирование и программная реализация экспертных систем на персональных ЭВМ" (1990) служит примером того же - там FORTH "доращивают" до пародии на LISP и PROLOG...
Причем, и в рассматриваемой статье, и в упомянутой книге, полученный проблемно-ориентированный язык, служит исключительно демонстрационным целям. Никакого анализа его возможностей не производится. Слова о дальнейшем развитии повисают в воздухе...
Отсутствуют в обоих случаях и чисто-FORTH методы решения задач. Никаких нетривиальных компилирующих слов и/или синтаксических экспериментов почти не предлагается. В тех же случаях, где изобретается некий проблемно-ориентированый синтаксис, он зело страшен. Настолько, что начинаешь думать, что C-реализация всего этого безобразия была бы более естественной.
Может быть, применеие FORTH было попыткой приблизить решение к народу - работающим на самодельных персональных компьютерах программистам-самоучкам?
Или авторами двигало желание не дать FORTH сдохнуть путем демонстрации легкости написания на нем чего угодно?
Рассмотрим по-подробнее.

Оригинал статьи (англ.): DOC, 0.33Мб
Книга: DJVU, 7.32Мб
avatar
Gudleifr
Admin

Сообщения : 908
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Примеры структур данных

Сообщение автор Gudleifr в Вт Янв 23, 2018 10:36 pm

Полный перевод статьи приводить не буду, только чисто технические моменты.

СТРУКТУРА СТАТЬИ
Приоритеты - создание быстродействующего механизма обработки строк для программ реального времени. Автор разбил свою диссертацию на описание последовательности решения четырех больших взаимосвязанных задач - динамического распределения памяти и, основанных на нем системах ассоциативного поиска данных, строковых операций и шаблонов строк.
Решение каждой задачи состоит из трех частей: голой теории (к FORTH отношения не имеющей), записи решения в виде перечисления необходимых FORTH-слов (к сожалению, без описания реализации) и пустопорожних обещаний сделать позднее по-людски. От себя добавлю четвертую часть - попытку хоть какого-то анализа возможностей реализации.
avatar
Gudleifr
Admin

Сообщения : 908
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Примеры структур данных

Сообщение автор Gudleifr в Вт Янв 23, 2018 10:43 pm

"ПАМЯТЬ"

ТЕОРИЯ. Решение предложено самое типовое (см. Кнут "Искусство программирования, т.1" а также Керниган и Ричи "Язык Си"). Все, в общем-то понятно из рисунков.



Большой блок, и из которого будет выделятся память, берется (вне адресного пространства программы) размером, равным максимально возможному значению адреса (для 16-разрядного процессора - 64К байт). Это позволяет избежать проверки указателя при переборе сегментов памяти - достигнув предела, он автоматически обнуляется.
Сначала весь блок - один большой сегмент. После нескольких выделений/освобождений - цепочка занятых/свободных сегментов. Для прохождения этой цепочки вперед/назад в начале и конце каждого сегмента выделяется дополнительно по слову-тэгу. Туда прописываются длина сегмента и флаг занятости.
При освобождении сегмента проверяются оба его соседа и свободные сегменты-соседи сливаются в один.
***

РЕШЕНИЕ. Всего три слова для управления процессом:

\ALLOC ( -- ) Инициализация механизма.
ALLOC ( n -- a 0 ) или ( n -- 1 ) Выделение сегмента (под строку).
RELEASE ( a ) Освобождение сегмента.

И два "внутренних" слова:

$SEG ( -- n ) Адрес/параграф/страница (зависит от "железа") строковой памяти вне обычного FORTH-пространства.
ROVER ( -- a ) Переменная - указатель текущего (свободного) сегмента.
***

ОБЕЩАНИЯ. Поддержка списка свободных сегментов; проверка целостности; выделение памяти страницами/параграфами; работа с расширенной памятью ОС; десегментация памяти (перенос занятых сегментов с целью сбора всех свободных в один большой).
***

РЕАЛИЗАЦИЯ. Предлагаемое решение содержит подвох. Ведь, мы выделяем память за пределами обычного FORTH-пространства. И слова, которые есть в "стандартном FORTH", нас не спасут. Придется лезть в описание "железа" и, весьма вероятно, что-то писать "в кодах".
Надо будет либо создавать набор слов для вытаскивания данных в обычное адресное пространство FORTH (и запихивания обратно), либо слова для обработки данных "где-то там".
Что-то вроде первого, вообще-то говоря, уже было давно реализовано - именно так работает FORTH с памятью блоков (BLOCK)...
В статье же идет речь, скорее, о втором - остальные прорабатываемые задачи, вроде бы, должны работать со строками, как с объектами особого - строкового - типа, т.е. при помощи особого лексикона, который должен уметь работать с данными в отдельной строковой памяти (куда показывает $SEG). Конечно, набор примитивов для такой работы имело бы смысл создать здесь, но автор этого делать не стал.
avatar
Gudleifr
Admin

Сообщения : 908
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Примеры структур данных

Сообщение автор Gudleifr в Вт Янв 23, 2018 10:52 pm

"ХЭШ-ТАБЛИЦЫ"

ТЕОРИЯ. Про сами эти таблицы можно посмотреть в Кнут "Искусство программирования, т.3", Керниган и Пайка "Практика программирования", Ахо, Хопкрофт и Ульман "Построение и анализ вычислительных алгоритмов"... Суть там в том, что из значения каждой строки можно получить достаточно малое число применением какой-либо "хорошо перемешивающей" хэш-функции. В отличие от большого разнообразия строк мы имеем тогда малые числа, которые могут трактоваться, как индексы массива (таблицы). Так как у некоторых строк числа могут совпадать, в ячейках таблицы придется хранить не строки, но списки строк. Если число списков примерно равно числу хранимых строк, то поиск нужной занимает практически не зависящее от числа хранимых строк время: расчет хэш-функции для строки, выбор из таблицы начала списка с этим номером и "чуть более одного" посимвольного сравнения искомой строки с хранящимися в списке.



Для хэш-таблицы (позднее выясняется, что для всех хэш-таблиц) отводится отдельный блок памяти за пределами обычного FORTH-пространства. Этот блок разбивается на массивы, по 8 слов каждый.
Первый вид массивов - деревья хэш-таблиц. Один массив - корень дерева - содержит адреса 8 массивов ветвей 1-го уровня, те еще по 8 адресов... Каждый уровень дерева выбирает одну из восьми ветвей на основании очередных трех битов хэш-суммы. К ветвям последнего уровня "крепятся" списки строк. (Автор считает нормой два уровня дерева и 6-битовую хэш-сумму. Т.е. 64 списка. Автор находится в раздумьях, не добавить ли еще 3 бита к сумме, и еще один уровень к дереву, доведя т.о. число списков до 512).



Вторая разновидность массивов содержит связные списки заголовков строк, хранящихся в динамически выделяемой строковой памяти (из первого раздела). Зачем такие большие заголовки, объясняется ниже.
Третий вид, очевидно, нужен для хранения списка пустых массивов.
И это еще только цветочки! Автор предлагает считать хэш-сумму длиннее на 16 бит, чем нужно для таблицы (т.е. не 6, а 22 бита), и хранить это лишнее контрольное значение в заголовке строки (ascension value). А сами списки упорядочивать по их значению. Также нужно хранить в заголовке длину строк (и тоже сравнивать при поиске). Идея в том, чтобы практически исключить излишние посимвольные сравнения строк. (Сортировка здесь практически не вызывает накладных расходов, т.к. место вставки в список определяется при неуспешном поиске).



Оставшиеся поля заголовка распределяются следующим образом: два слова под значение, которое мы ассоциируем с искомой строкой (ведь зачем-то мы ее ищем), одно слово под значение счетчика ссылок (на случай, если когда-либо будет реализована сборка мусора) и последнее слово... барабанная дробь... под дочернюю хэш-таблицу. Т.е. автору показалось мало просто "поиска по имени" и он ввел многоуровневый поиск по имени! Вложенные хэши!
Последнее - автор решил, что хорошей идеей будет хранить в строковых переменных не адрес сегмента строки, а адрес ее заголовка в хэш-блоке.


***

РЕШЕНИЕ. Наплодив столько структур, автор, разумеется был просто обязан придумать слова для доступа ко всему разнообразию их полей. Их, получилось, опять, на удивление мало. И автор так и не захотел провести хоть какую-то унификацию слов, работающих за пределами FORTH-пространства.

Общедоступные слова:

\HASH ( -- ) Инициализация механизма.
>$ ( a n -- s ) Найти (если нет - разместить) строку a (из FORTH-пространства) длиной n, вернуть адрес заголовка в хэш-пространстве.
" ( <text>" -- s ) Найти (если нет - разместить) строку из потока ввода.
\$ ( a n -- ) Найти и удалить строку.
$TEXT ( s -- a seg n ) Найти строку по заголовку. Возвращает адрес в пространстве строк, адрес строковой памяти ($SEG) и длину строки. Возможно - перенос строки в FORTH-пространство.
$! ( n s -- ) Изменить данные, ассоциированные со строкой. Возможно, с анализом и запоминанием текущего источника и типа данных.
$@ ( s -- n ) Получить данные, ассоциированные со строкой.
TABLE ( s ) Создать для этой строки дочернюю хэш-таблицу.
{ ( s ) Установить дочернюю хэш-таблицу текущей.
} ( -- ) Вернуться к хэш-табблице "по умолчанию".

Внутренние слова:

?HASH ( f ) Аналог ?ABORT, выводящий сообщение "hash space full".
HALLOC ( -- a f ) Ищет свободный 8-словный массив, возвращает адрес в хэш-пространстве и флаг ошибки (для ?HASH).
HASH ( a n -- a n u c ) Считает контрольное значение (16 бит) и хэш-сумму (8? бит) строки. Саму строку не портит.
HFIND ( a n u c -- a n u a' f ) По результатам предыдущего слова ищет заголовок строки.
HINSERT ( u a' A n -- A f ) При неудаче HFIND вставляет строку в хэш-таблицу. (A - адрес в строковой памяти).
HDELETE ( a' ) Удаляет заголовок.
\TABLE ( a -- a ) Создает пустое дерево. a - адрес корня.
HFREE ( -- a ) Переменная - начало списка пустых массивов.
$CONTEXT ( -- a ) Переменная - текущая хэш-таблица.
HSIZE ( -- n ) Размер заголовков (16?).
H0 ( -- n ) Адрес дерева "по умолчанию".
#H ( -- n ) Максимальное число заголовков.
***

ОБЕЩАНИЯ. Хорошая хэш-функция, сборка мусора. Правда, автор замечает, что идеология FORTH не совсем подходит для работы с объектами. Например, как подсчитывать число живых ссылок на объект, если их можно размножать и удалять обычными стековыми операциями? Заводить специальный набор DUP-ов и DROP-ов для работы с объектами?
***

РЕАЛИЗАЦИЯ. Разумеется, FORTH прекрасно ищет строки (в том числе, в разных словарях) и без этого расширения.
Все эти 8-словные массивы и двухуровневые деревья, хотя и поражают на первый взгляд удачным совпадением длин и размеров, но являются лишь грубой попыткой подгона. "Клин да мох, иначе плотник бы сдох..."
Если уж и понадобится работать с хэш-таблицами, то их, все равно, придется рассчитывать "по месту", иначе выигрыша в быстродействии не получиться.
avatar
Gudleifr
Admin

Сообщения : 908
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Примеры структур данных

Сообщение автор Gudleifr в Вт Янв 23, 2018 10:55 pm

ЛИРИЧЕСКОЕ ОТСТУПЛЕНИЕ

До кучи - пример аналогичных решений, принятых в языке Smalltalk-80 (по книге К.Фути и Н.Судзуки "Языки программирования и схемотехника СБИС"). Память там организована по словам (слово - 16 бит).
Любое слово данных там сначала проверяется на четность. Нечетные интерпретируются как маленькие целые (по 15 оставшихся битов), четные - указатели на таблицу объектов.
Таблица содержит по 2 слова на объект: 20 бит - адрес, 8 - счетчик ссылок, остальное - флаги существования, типа и пр. Тут мы видим отсыл к трем из упомянутых выше решений: счетчик ссылок позволяет производить сборку мусора, бит существования - облегчает обработку свободных, использования доступа к объектам только через таблицу позволяет спокойно их перемещать в памяти при ее десегментации.
Для облегчения поиска наиболее подходящего свободного сегмента отдельно поддерживаются 19 списков коротких свободных сегментов - от 2 до 20 слов.
avatar
Gudleifr
Admin

Сообщения : 908
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Примеры структур данных

Сообщение автор Gudleifr в Вт Янв 23, 2018 11:18 pm

Все, конец "общим решениям", следующий кусок будет FORTH-ориентированным. С созданием проблемно-ориентированного языка.

"ШАБЛОНЫ"

ТЕОРИЯ. Шаблоны - это разновидность почти-регулярных выражений. Только вместо стройной теории используются "все пришедшие в голову" подшаблоны элементарных подвыражений, соединенные все теми же стандартными связками - "конкатенация" и "или".



Тут тоже все понятно из рисунков (представление шаблона в виде графа, алгоритм обхода этого графа, стек для запоминания непройденных альтернатив). Единственная хитрость в том, что некоторые подшаблоны тоже должны взаимодействовать со стеком этой "машины" (например, ARB, соответствующий "чему угодно" содержит в себе этакий внутренний "или": 0 символов или 1 символ, или 2 символа.., или все символы). В общем случае, т.к. точка отката к непройденной альтернативе (указатель строки и следующий - альтернативный - способ ее анализа) может лежать как внутри вложенного подшаблона, так и в шаблоне, включающем рассматриваемый, то применяются специальные стековые "заглушки".



На рисунке: при первом вызове подшаблона, он вполне способен вернуться обратно "по правилам языка программирования", но т.к. откат в него (к оставшимся в нем непройденным альтернативам) происходит "немного по-хакерски", то требуется создать видимость "правильного входа в процедуру". Поэтому в конец подшаблона вставляются операторы записи в стек адреса "псевдоальтернативы" - процедуры, восстанавливающей состояние программной структуры вызова подшаблона и переходящей к его настоящим альтернативам.
Конечно, это уже FORTH-ориентированное решение. Не в смысле, что это красиво смотрится, но в смысле, что на нем это возможно реализовать и объяснить достаточно просто. "Запомнить последнее значение на стеке возвратов в служебном стеке, а потом его оттуда восстановить" понять проще, чем "вызвать процедуру по goto, а потом добиться правильного срабатывания return из нее".
Еще один нюанс состоит в том, что, в случае, если подшаблон используется в роли главного, эта "заглушка" создаваться не должна, т.е. требуется проверка глубины вложения подшаблона в данном разборе.



На рисунке: обратная ситуация - откат из подшаблона в главный. "Оказывается", что для правильного перепрыга к альтернативам главного шаблона необходимо еще раз сохранить состояние при входе в подшаблон...
***

РЕШЕНИЕ. Казалось бы, чего проще - размести в памяти граф шаблона и запусти "машину"... Если, к тому же, отказаться от неэлементарных подшаблонов, заменив их подграфами, то можно даже не городить этот огород с "перепрыгами".
Но, нет, автор сделал шаблоны почти честными FORTH-словами. К сожалению, "язык шаблонов" оказался "слишком инфиксным".
Пришлось создать создать компилирующие слова: "скобки" : << и >> ; и "или" - | (компилирующие в слово-шаблон соответственно (<<) и (>>) и (|) ). Конкатенация, к несчастью, не может при этом обеспечиваться обычным "следует за" и должна быть реализована через вложенные друг в друга скобки. Т.е. "a b" должно выглядеть как "<< a >> b". При этом, очевидно, возможны возвраты извне внутрь скобок (выбор другой альтернативы при неудаче в одном из последующих подшаблонов).



В качестве History Stack используется стек данных.

<< ( -- 20 20 ) Открывающая скобка. Нужна для группировки альтернатив "или".
| ( -- a 21 ) Разделитель альтернатив "или".
>> ( 20 20 21 ... 21 -- ) Закрывающая скобка. Самое неприятное, эта скобка не соответствует какой-то одной позиции в строке, т.к. альтернативы могут иметь разную длину.
PAT: ( -- ) Начало определения слова-шаблона.
;PAT ( -- ) Завершение определения шаблона. Получившийся шаблон может затем использоваться как подшаблон в других, более крупных.
EVALUATE ( s a -- f ) Эквивалент EXECUTE для запуска главных шаблонов. Его цель - избежать замусоривания стека нерассмотренными альтернативами. Сохраняет указатель стека данных, выполняет главный шаблон (a), восстанавливает указатель стека, оставляет флаг успеха.

Внутренние слова:

ENTER< ( -- a oip ) (R: ip -- ip a ) Слово, компилируемое в начало шаблона словом PAT: (которое равносильно ": ENTER<"). В стек заносится заглушка FALLOUT для перепрыга к надшаблону. В стек возвратов - текущая позиция в строке.
>EXIT ( a oip -- 1 ) (R: ip a -- ip ) или ( xx -- xx a iip 1 ) (R: ip a -- ip ) Удаляет со стека возвратов текущую позицию. Если на стеке нет никаких никаких намеков на альтернативы (oip по-прежнему на вершине стека), стек очищается, иначе на него выкладывается заглушка FALLIN. Флаг 1 символизирует успех сопоставления, если мы дошли до этого места. Т.о. Слово ;PAT эквивалентно ">EXIT ;".
(<<) ( -- ) (R: ip a -- ip a ) Подновляет текущую позицию сканирования в стеке возврата?
(|) ( 1 -- a ip ) (R: ip a -- ip a ) или ( 0 -- ) (R: ip a -- ip a ) Его задача - перепрыгнуть эту и остальные альтернативы в случае удачи (и оставить на всякий случай на стеке информацию о развилке) или подновить информацию о текущей развилке.
(>>) ( 1 -- ) или ( a ip 0 -- ) Наоборот, ничего не делать при успехе, а при неудаче инициировать откат.
MARK ( -- ) (R: ra -- ra sa ) Используется в EVALUATE для сохранения позиции стека данных в стеке возврата.
RESTORE ( xx ... f -- f ) (R: ra sa -- ra ) Используется там же для финальной очистки стека от информации о невостребованных альтернативах.
(FALLIN) ( a ip ra -- ) (R: -- ra a') Код заглушки. Создает у подшаблона иллюзию, что он вызван "нормально", а не откатом из главного шаблона.
(FALLOUT) ( -- 0 ) (R: ip a -- ) Код заглушки. Обеспечивает нормальное возвращение из подшаблона (с неуспехом).
FAILURE ( -- 0 ) (R: ip a -- ) "Возврат с неуспехом". Ставится в том месте, куда происходит переход при неудаче сопоставления (в (>>)?). В текущей версии идентично (FALLOUT).
SUBJECT ( s -- ) Загрузка строки для разбора (из строкового хранилища).
CURSOR ( -- a ) Смещение текущей позиции в строке от ее начала.
CURADR ( -- a ) Адрес начала строки.
CURSEG ( -- a ) Тоже, что и $SEG - адрес пространства строк в терминах данной машины.
EOS ( -- a ) Смещение конца строки от начала (т.е. длина строки).

Очевидно, в шаблоны можно вставлять и обычные слова (если только они не портят стек), причем, гораздо свободнее, чем подшаблоны и "скобки" (поскольку эти-то стек портят).
Насколько хорошо все это может работать? Автор не привел никаких обоснований, только "правдоподобные рассуждения". Исходники недоступны. С поправкой на ошибки набора и моего перевода - шанс невелик.
До демонстрационной версии дотянуть можно, но, наверное, не дальше.
Стандартные слова-шаблоны.

Пользовательские:

MATCH ( s -- f ) Соответствует такой же строке.
ANY ( s -- f ) Соответствует одной литере, любой из представленых в строке.
LEN ( n -- f ) Соответствует любой строке заданной длины.
LEFT ( -- n ) Не подшаблон. Просто возвращает длину еще не просмотренной части строки.
POS ( n -- f ) Успешен, если текущая позиция в строке равна заданной.
ARB ( -- l ) Соответствует любой подстроке, включая нулевую. Стремится соответствовать самой длинной подстроке из возможных (т.е. перебирает во внутреннем цикле длины от максимальной до нулевой).

Cложные подшаблоны:

REM ( -- l ) Соответсвует остатку строки. Эквивалентен "LEFT LEN".
TAB ( n -- f ) Соответствует подстроке до указанной позиции.
RPOS ( n -- f ) Успешен, если текущая позиция, считая от конца строки, равна заданной.
NOTANY ( s -- f ) Соответствует одной литере, любой, кроме представленных в строке. Эквивалентен "ANY 0=".
ARBNO ( не описано ) Соответствует нескольким (включая ноль) повторениям применения какого-либо другого шаблона.
SPAN ( s -- f ) Результат применения ARBNO к ANY.
BREAK ( s -- f ) Результат применения ARBNO к NOTANY.
FAIL ( -- 0 ) Всегда неуспех.
SUCCEED ( -- 1 ) Всегда успех. Автору очень нравится конструкция "<< BEGIN 1 | AGAIN >>".
не описано - Модификатор для ARB, заставляющий его соответствовать не как можно более длинной строке, а, наоборот, самой короткой.

Внутренние слова для подшаблонов:

(MATCH) ( adr seg n -- f ) Сравнение разбираемой строки со строкой из строкового пространства.
(ANY) ( adr seg n -- f ) Поиск текущей литеры разбираемой строки в строке из строкового пространства.
***

ОБЕЩАНИЯ. Тут, как чисто технические улучшения (избавление от лишних скобок при конкатенации, выбор наиболее удобного места для History Stack), так и философствование о том, куда идти дальше. К генераторам (итераторам) языка Icon, к сопрограммам, к процедурам рекурсивного перебора с откатами...
Очевидно, что, пока речь шла о достижении конкретной цели, все было просто и удобно, но когда речь зашла о работе "впрок", сам FORTH воспротивился.
***

РЕАЛИЗАЦИЯ. Боюсь, красиво совместить в честной польской записи операторы конкатенации, альтернативы и обычного следования слов вряд ли возможно. Поэтому промежуточная запись шаблона в виде специального списка или графа кажется достаточно привлекательной. Особенно, учитывая имеющийся математический аппарат регулярных выражений и конечных автоматов (см. Ахо, Хопкрофт и Ульман "Построение и анализ вычислительных алгоритмов").
Конечно, многое из того, о чем рассказано в статье, придется реализовать и при других подходах к решению проблемы.

С практической точки зрения надо учитывать две вещи:
1. Реализовывать классические регулярные выражения проще, чем свои доморощеные шаблоны.
2. Универсальная реализация шаблонов/регулярных выражений очень редко когда требуется. В каждом конкретном случае присутствуют требования и ограничения, приводящие к необходимости частного решения. Обычно, гораздо более простого.
avatar
Gudleifr
Admin

Сообщения : 908
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Примеры структур данных

Сообщение автор Gudleifr в Вт Янв 23, 2018 11:20 pm

СТРОКОВЫЕ ОПЕРАЦИИ

ТЕОРИЯ отсутствует.
***

РЕШЕНИЕ. Все очевидно:

$TYPE ( s -- ) Вывод строки на экран.
SIZE ( s -- n ) Длина строки.
CONCAT ( s1 s2 -- s3 ) Конкатенация.
SUBST ( s1 ofs n -- s2 ) Вырезание подстроки.
FILLED ( n с -- s ) Размножение символа.
$>N ( s -- n ) Преобразовать строку в число.
N>$ ( n -- s ) Преобразование числа в строку.
RPAD ( не описано ) Добавить пробелы справа.
LPAD ( не описано ) Добавить пробелы слева.
TRIM ( не описано ) Убрать лишние пробелы.
DUPL( не описано ) Размножение строки.
***

ОБЕЩАНИЯ. Добавить типов, операций... Улучшить реализацию...
***

РЕАЛИЗАЦИЯ. Тут все очевидно. Использование универсальной строковой библиотеки - это крайне неудачное решение почти всегда (см. Керниган и Пайк "Практика программирования). Тем более, что автор настаивает на хранении строк в ассоциативной памяти.
Похоже, он добавил этот очевидный кусок "для общей массы".
avatar
Gudleifr
Admin

Сообщения : 908
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Примеры структур данных

Сообщение автор Gudleifr в Вт Янв 23, 2018 11:25 pm

Все, с первой статьей разобрались. Читаем теперь книгу Таунсенда и Фохта "Проектирование и программная реализация экспертных систем на персональных ЭВМ".
Это не фигура речи. До момента написания этих огрызков я ее не читал. Так, просмотрел по диагонали.

ПОЧТИ LISP

Сначала авторы вводят два очевидных слова "общего назначения" - выбор по целому и рекурсию. (Их не было в Форт-83?)

\ МОДИФИЦИРОВАННЫЙ ОПЕРАТОР CASE ДЛЯ ФОРТА ПЕРРИ И ЛЭКСЕНА
: CASE 0 ; IMMEDIATE
: OF COMPILE OVER COMPILE = [COMPILE] IF COMPILE DROP ; IMMEDIATE
: ENDOF [COMPILE] ELSE ; IMMEDIATE
: ENDCASE COMPILE DROP BEGIN ?DUP WHILE [COMPILE] THEN REPATE ; IMMEDIATE

\ СЛОВО, ОСУЩЕСТВЛЯЮЩЕЕ РЕКУРСИЮ
: РЕКУРСИЯ LAST @ NAME> , ; IMMEDIATE

Далее открывается важная тайна: авторы совершенно не собираются честно размещать списки в памяти. Каждый список - просто массив (длина указывается при создании), в первой ячейке которого размещается ссылка на ячейку, содержащую первый элемент списка. Ячейки остальных элементов отсчитываются в сторону начала списка. Признак конца (он же пустой список) - НУЛЬ.

VARIABLE НУЛЬ НУЛЬ НУЛЬ !
: НОВСПИСОК ( #ЭЛЕМЕНТОВ ) CREATE HERE 2+ , НУЛЬ , 2* ALLOT ;
: ПЕРВЫЙ ( @СПИСОК -- @ПЕРВЫЙ ) @ ;
: НОЛЬ ( @СПИСОК -- ФЛАГ ) @ НУЛЬ = ;
: ХВОСТ ( @СПИСОК -- @ПОСЛЕДНИЙ ) DUP НОЛЬ IF @ ELSE 2- THEN ;

Сразу начинается непонятка - @СПИСОК, оказывается, означает не то, что возвращает слово, созданное НОВСПИСОК, а указатель на "очередную" ячейку списка. Иначе слово ХВОСТ не сработает. Еще отметим, что те, кто знает LISP, не удивятся тому, что при расчете ПЕРВЫЙ (car) происходит лишнее разыменование по сравнению с ХВОСТ (cdr).

: ПУСТОЙ ( I ) DUP 2+ DUP ROT ! НУЛЬ SWAP ! ;
: УСТАНОВИТЬ ( I @СПИСОК ) DUP НУЛЬ = IF DROP ПУСТОЙ ELSE SWAP ! THEN ;

А что такое I? А это, как раз, то значение, что возвращает НОВСПИСОК, а, заодно, и другие слова-переменные, в которых может сохранятся @СПИСОК. Т.е. I - адрес ячейки, где хранится @СПИСОК. Пардон, в УСТАНОВИТЬ мы получаем, что I должно быть честно полученным НОВСПИСОК словом (иначе ПУСТОЙ применять нельзя), но присваивать такой "переменной" ссылку на "чужой" @СПИСОК, вместо того, чтобы заполнять элементами "свой" массив, как-то странно. Либо "дыра", либо УСТАНОВИТЬ применяется только для обращения I к "самому себе"?

: СВЯЗЬ ( @ЭЛЕМЕНТ I ) 2 OVER +! @ ! ;
: СПИСОК ( НУЛЬ S1 S2 ... SN I ) >R BEGIN DUP НОЛЬ NOT WHILE
R@ СВЯЗЬ REPEATE R> 2DROP ;

Что же тогда делает СВЯЗЬ? Смотри слово СПИСОК - все ясно - СВЯЗЬ добавляет в список элементы задом наперед!

: 2СОЕД ( @СПИСОК I ) OVER НОЛЬ IF
2DROP ELSE OVER ХВОСТ OVER РЕКУРСИЯ
SWAP ПЕРВЫЙ SWAP СВЯЗЬ THEN ;

Хитрое рекурсивное слияние списков. Не вникая: сначала долго углубляемся в рекурсию, вызывая ХВОСТ от @СПИСОК, а затем (разыменовав эти ХВОСТы при помощи ПЕРВЫЙ) поднимаемся обратно, прицепляя элементы к I. Т.е. при погружении @СПИСОК переворачивается, а при всплытии дописывается к I задом наперед (в лучших традициях LISP). В итоге в I получается список с началом @СПИСОК и концом - старым I.

: АТОМ? ( @ -- ФЛАГ ) BODY> @ ['] НУЛЬ @ = ;

Сравнить значение в сfa, полученного из текущего адреса, трактуемого как pfa, со значением в cfa слова НУЛЬ? Понятно, работает только при применении косвенного шитого кода, как в Форт-83. Проверка того, что данный адрес является pfa переменной (НУЛЬ тут только в качестве примера переменной)? Т.е. в случае если адрес можно трактовать, как @СПИСОК, то получим ложь.

: ВЫДАТЬСП ( @СПИСОК ) CR ." ("
BEGIN DUP ПЕРВЫЙ DUP АТОМ? IF DUP НОЛЬ NOT IF
BODY> >NAME .ID ELSE DROP TNEN ELSE РЕКУРСИЯ THEN
ХВОСТ DUP НОЛЬ UNTIL 8 ( ЗАБОЙ ) EMIT ." )" DROP ;
: ВЫДАТЬ ( @СПИСОК ) DUP @ НОЛЬ IF
DROP CR ." НУЛЬ" ELSE DUP АТОМ? IF
BODY> >NAME .ID ELSE ВЫДАТЬСП THEN THEN ;

Ну, вот, процедура выдачи списка на печать. Смысл перебора ВЫДАТЬСП понятен: по списку от начала до конца и рекурсивно - по вложенным спискам. ВЫДАТЬ лишь добавляет начальную проверку. То что ВЫДАТЬ напечатает "НУЛЬ" и в случае, если на стеке НУЛЬ, и адрес НУЛЬ, и адрес адреса НУЛЬ, больше похоже на перестраховку.
Обратите, кстати, внимание на то, что атомарными выражениями списков здесь служат не значения, но именованные переменные. А если так, то почему, заодно, было не сделать честные списки?

: ЧТСИМ ( -- C ) BEGIN ИСТОЧНИК >IN @ /STRING IF
C@ 1 >IN +! TRUE ELSE
DROP ['] ИСТОЧНИК >BODY @ ['] (ИСТОЧНИК) = IF QUERY ELSE 1 BLK +! 0 >IN ! THEN
FALSE THEN UNTIL ;
: ?CREATE ( -- CFA ) >IN @ DEFINED
IF NIP ELSE DROP >IN ! HERE VARIABLE 4 + NAME> THEN ;
: ЧТСП ( I ) >R BEGIN ЧТСИМ CASE
BL OF FALSE ENDOF
ASCII ( OF НУЛЬ FALSE ENDOF
ASCII ) OF R@ СПИСОК TRUE ENDOF
ASCII @ OF @ FALSE ENDOF
-1 >IN +! ?CREATE EXECUTE FALSE ROT ENDCASE UNTIL R> DROP ;

Понятно, что этот кусок тоже сильно зависит от вида шитого кода. Только зачем было городить этот огород? Зачем этот хитрый формат ввода списка, ничем, по-сути, не отличающийся от обычного потока? Только для демонстрации хитрой возможности создания переменных "на лету"? (Тем более, что для ввода вложенных списков он не пригоден. Например, для ввода (A (B C) D) понадобится сначала засунуть (B C) в I1, а потом набрать "I2 ЧТСП (A I1 @ D)").
Даже не хочу вникать.
***

Затем авторы привели несколько неинтересных примеров дурацких слов для нахождения элементов списка, его длины и т.п. (вполне в духе LISP). Надеюсь, нам хватит и тех, что будут использованы в PROLOG.
***

ВЫВОД. Это, конечно, никаким местом не LISP в понимании парадигмы функционального программирования, но вполне достаточная списковая библиотека для построения такого же демонстрационного почти-PROLOG.
avatar
Gudleifr
Admin

Сообщения : 908
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Примеры структур данных

Сообщение автор Gudleifr в Вт Янв 23, 2018 11:32 pm

ПОЧТИ PROLOG

Алгоритм прост (обратный вывод с возвратами): для всех целей (список ЦЕЛИ) ищем правила-факты (список списков ПРЕДЛОЖЕНИЯ), с них начинающиеся. Найденное предложение-решение помещается в список РЕШЕНИЙ, и добавляет новые цели. При невозможности найти очередную цель происходит откат к предыдущему решению. (На самом деле, немного похоже на обработку шаблонов из предыдущей статьи, только вместо стека - список).

20 НОВСПИСОК ЦЕЛИ
20 НОВСПИСОК РЕШЕНИЯ
200 НОВСПИСОК ПРЕДЛОЖЕНИЯ
: ПОЛУЧИТЬ-ЦЕЛЬ ( -- ЦЕЛЬ ) ЦЕЛИ @ DUP ПЕРВЫЙ SWAP ХВОСТ ЦЕЛИ SWAP УСТАНОВИТЬ ;
: НАЙТИ-ПРЕДЛОЖЕНИЕ ( ЦЕЛЬ @ПРЕДЛОЖЕНИЯ1 -- ЦЕЛЬ @ПРЕДЛОЖЕНИЯ2 ) BEGIN
2DUP ПЕРВЫЙ ПЕРВЫЙ DUP >R = R> НОЛЬ OR NOT WHILE
ХВОСТ REPEAT ;
: НАЙТИ-ПРЕДЛОЖЕНИЕ? ( ЦЕЛЬ @ПРЕДЛОЖЕНИЯ -- ФЛАГ ) НАЙТИ-ПРЕДЛОЖЕНИЕ
DUP НОЛЬ DUP >R IF DROP ELSE РЕШЕНИЯ СВЯЗЬ РЕШЕНИЯ СВЯЗЬ THEN R> NOT ;

Пока, вроде бы, все очевидно. Если, конечно, отслеживать глубину погружения во вложенные списки.

ПОЛУЧИТЬ-ЦЕЛЬ - Отрезать от списка ЦЕЛИ первый элемент и выдать его.
НАЙТИ-ПРЕДЛОЖЕНИЕ - Искать в списке списков ПРЕДЛОЖЕНИЯ цель и соответствующее ей предложение (он далее используется двояко - как список-правило и как указатель в списке ПРЕДЛОЖЕНИЙ).
НАЙТИ-ПРЕДЛОЖЕНИЕ? - Если получилось, запомнить в список РЕШЕНИЯ пару цель-предложение.

Подозрения о применимости слова УСТАНОВИТЬ только в пределах одного списка, вроде, подтверждается.

: ДОБАВИТЬ-ЦЕЛИ РЕШЕНИЯ @ ХВОСТ ПЕРВЫЙ ПЕРВЫЙ ХВОСТ ЦЕЛИ 2СОЕД ;
: ВОЗВРАТ ( -- ФЛАГ ) РЕШЕНИЯ @ DUP ПЕРВЫЙ SWAP
ХВОСТ ПЕРВЫЙ ХВОСТ РЕШЕНИЯ DUP @ ХВОСТ ХВОСТ УСТАНОВИТЬ
НАЙТИ-ПРЕДЛОЖЕНИЕ? DUP IF ДОБАВИТЬ-ЦЕЛИ THEN ;

ДОБАВИТЬ-ЦЕЛИ - Взять первую пару цель-предложение из списка РЕШЕНИЯ и присоединить к списку ЦЕЛИ предложение (без первого элемента - старой цели).
ВОЗВРАТ - Отрезать от списка РЕШЕНИЯ первую пару, искать ее цель, начиная с места указанного ее предложением. В случае успеха - добавить новые цели.

: (ПОИСК) ( -- ФЛАГ-УСПЕХ ФЛАГ-ОСТАНОВ )
ЦЕЛИ @ НОЛЬ NOT IF
ПОЛУЧИТЬ-ЦЕЛЬ ПРЕДЛОЖЕНИЯ @ НАЙТИ ПРЕДЛОЖЕНИЕ? IF
ДОБАВИТЬ-ЦЕЛИ FALSE ELSE
ВОЗВРАТ IF FALSE ELSE FALSE TRUE THEN THEN
ELSE TRUE DUP THEN ;
: ПОИСК ( -- ФЛАГ-УСПЕХ )
BEGIN (ПОИСК) UNTIL ;

Вот и весь "логический" вывод. Авторы еще предлагают некоторый обвес для ввода списка целей и распечатки хода "размышлений", но он очевиден. Да и сама идея подобной реализации вызывает вопросы: с одной стороны разбиение алгоритма на такие слова недостаточно читабельно, с другой - во внутреннем устройстве этих слов тоже не сразу разберешься.
***

Еще один пример PROLOG-алгоритма - унификация. Т.е. не просто сравнить два списка (произвольной глубины вложенности), но и связать их переменные.

: ПЕРСП ( -- PFA+2 ) CREATE HERE 2+ , 0 , DOES> 2+ ;
ПЕРСП FOO ' FOO @ FORGET FOO
: ПЕР? ( С -- F ) DUP @ 0= SWAP 4 - @ [ DUP ] LITERAL = AND ;
DROP

Специальный тип - переменная для связывания. Опять зависимость от типа шитого кода - выяснение адреса кода слова для проверки его типа (как в слове АТОМ?).

: 2АССОЦ ( С СП1 -- СП2 ) DUP НОЛЬ
IF NIP ELSE
2DUP ПЕРВЫЙ =
IF NIP ELSE ХВОСТ ХВОСТ РЕКУРСИЯ THEN THEN ;
: ЗНАЧЕНИЕ ( С @ОКРУЖЕНИЕ -- СП2 ) OVER ПЕР? IF
2DUP 2АССОЦ DUP НОЛЬ IF
2DROP ELSE ROT DROP ХВОСТ ПЕРВЫЙ SWAP РЕКУРСИЯ
THEN ELSE DROP THEN ;
: УНИФИКАЦИЯ ( C1 C2 ОКРУЖЕНИЕ -- F )
DUP >R @ ROT OVER ЗНАЧЕНИЕ OVER -ROT ЗНАЧЕНИЕ OVER
ПЕР? IF НУЛЬ -ROT R> СПИСОК TRUE ELSE
DUP ПЕР? IF SWAP НУЛЬ -ROT R> СПИСОК TRUE ELSE
2DUP АТОМ? SWAP АТОМ? OR NOT IF
2DUP ПЕРВЫЙ SWAP ПЕРВЫЙ SWAP R@ РЕКУРСИЯ IF
ХВОСТ SWAP ХВОСТ SWAP R> РЕКУРСИЯ ELSE
2DROP R> DROP FALSE THEN ELSE R> DROP = THEN THEN THEN ;

Я даже не знаю, чего мне больше не хочется, выяснять, как унификация PROLOG должна работать "на самом деле", или разбираться с тонкостями данной реализации. В общем, все очевидно - параллельно исследуем два списка. Сравнивает и обрабатываем значения голов, если головы списков тоже списки, сравниваем их рекурсивно. Потом рекурсивно сравниваем хвосты...
***

Самое странное - вся мощность языка FORTH не позволила авторам вылезти за рамки книги Левина, Дранга и Эдельсона "Практическое введение в технологию искусственного интеллекта и экспертных систем с иллюстрациями на Бейсике" (ТЕМА #63).
avatar
Gudleifr
Admin

Сообщения : 908
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Примеры структур данных

Сообщение автор Gudleifr в Ср Янв 24, 2018 11:22 am

Теперь, когда мы немножко больше знаем о FORTH (ТЕМА #64), можно по-ному взглянуть на статью PatternForth Родригеса. Методом добавления новых лексиконов (1) он расширил FORTH ассоциативными хранилищами строк, строковыми операциями и операцией сравнения строки с шаблоном.

При всех достоинствах проекта можно отметить следующие очевидные недостатки:
- перевод разговора на обсуждение лексиконов замаскировал тот факт, что задача управления памятью оказалась, по-сути, нерешенной (мол, сами доработайте свой FORTH для работы за пределами 64Kb).
- C-подобный набор строковых операций - вещь совершенно не нужная в реальном программировании.
- предложенный язык шаблонов слишком тяжеловесен.

Попробуем посмотреть, нельзя ли применить другие методы:
(2) - упрятывание в интерпретатор. Конечно! Ведь предложенный механизм работы со строками практически делает работу FIND. Не проще ли переписать свой FORTH так, чтобы словари могли занимать более 64Kb (размещаться по-блочно) и хранить более длинные имена (с пробелами)? Можно и хеширование добавить... И все. Фортер даже не будет знать, что хранение и поиск строк что-то "весят".
(3) - нестандартный интерпретатор. Думаю, можно доказать, что подогнать язык шаблонов под стандарты FORTH-языка невозможно (можно, конечно применить стек приоритетов, как классики делали с инфиксной арифметикой). Но зачем? Интерпретатор для шаблонов давно описан и обсчитан (конечные автоматы). Так добавим к нашей FORTH-системе еще пару процедур - чтения-применения регулярных выражений. Создадим дополнительное хранилище для построенных конечных автоматов...
(4) - несколько интерпретаторов. Возвращаемся к постановке задачи. Не будет ли наш FORTH слишком тяжеловесным, получив "на борт" все эти строковые механизмы? Ведь он должен еще и что-то делать? Так может объединим две FORTH-системы: одна маленькая (на 64Kb) - для работы - и большой строковый процессор. Точнее, даже, наоборот. Большой FORTH-управлятор многими видами памяти (в т.ч. строковыми) будет содержать и рабочую FORTH-систему (которой выделит немного места и пару потоков ввода-вывода). Но, опять же, т.к. теории этого дела нет, фантазировать можно сколько угодно...
avatar
Gudleifr
Admin

Сообщения : 908
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Примеры структур данных

Сообщение автор Спонсируемый контент


Спонсируемый контент


Вернуться к началу Перейти вниз

Вернуться к началу


 
Права доступа к этому форуму:
Вы не можете отвечать на сообщения