Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Пт мар 29, 2024 02:07

...
Google Search
Forth-FAQ Spy Grafic

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




Ответить
Имя пользователя:
Заголовок:
Текст сообщения:
Введите текст вашего сообщения. Длина сообщения в символах не более: 60000

Размер шрифта:
Цвет шрифта
Настройки:
BBCode ВКЛЮЧЕН
[img] ВЫКЛЮЧЕН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЕН
Смайлики ВЫКЛЮЧЕНЫ
Отключить в этом сообщении BBCode
Не преобразовывать адреса URL в ссылки
Вопрос
Теперь гостю придется вводить здесь пароль. Не от своей учетной записи, а ПАРОЛЬ ДЛЯ ГОСТЯ, получить который можно после регистрации на форуме через ЛС.:
Этот вопрос предназначен для выявления и предотвращения автоматических регистраций.
   

Обзор темы - Борьба со словарями!
Автор Сообщение
  Заголовок сообщения:  Re: Борьба со словарями!  Ответить с цитатой
В данном случае поиску без разницы т.к. он очень похож на SEARCH-WORDLIST, кроме того после начала поиска уже всё равно какое значение имеет (TREEFIND)
Сообщение Добавлено: Пн авг 30, 2010 15:34
  Заголовок сообщения:  Re: Борьба со словарями!  Ответить с цитатой
стирать тему не стоит.
Новую тему можете открыть самостоятельно.

Единственное замечание - подумайте как вы собираетесь обеспечивать стабильную работу системы в рамках принятой в СПФ многопоточности (т.е. когда несколько потоков будет вести поиск в словарях).
Сообщение Добавлено: Пн авг 30, 2010 15:21
  Заголовок сообщения:  Re: Борьба со словарями!  Ответить с цитатой
Библиотеку нужно вынести в отдельную тему "Библиотека по работе с древовидными словарями" в SPF , а старую стереть за ненадобностью.
Сообщение Добавлено: Пн авг 30, 2010 14:34
  Заголовок сообщения:  Re: Борьба со словарями!  Ответить с цитатой
ВНИМАНИЕ! Библиотека периодически обновляется.
В начале будет указываться дата последнего изменения.

То, что не работает:
Замена основного поиска - т.к. вектор FIND системой не используется, а SFIND, увы, не заменишь.

Слова для использования:
1 : , ; ,;BR

Слова в словаре ---->
В 1 A--------------------------B---C----D
е 2 +--A1---B1---C1
т 3 +-------------A2---B2
в
и
|
|
|
v


с точки зрения обычного словаря
A--A1--B1--C1 A2--B2 B--C--D
Как реализовать такое дерево?

1 Отпочковываем дополнительную ветвь начинающуюся с A1 и приделанную к А
( стандартно ) : A1 DUP SWAP DROP ( затем нестандартное закрытие ) ;BR ( затем точка привязки ) A
2 добавляем следующие определения в словарь
: B1 DUP SWAP DROP ;
: C1 DUP SWAP DROP ;
3 добавляем новую ветку
: A2 DUP SWAP DROP ;BR A1
4 добавляем следующее определение
: B2 DUP SWAP DROP ;
(4 опционально)
BRLAST ( для того, чтобы при вызове TREEFIND не прекращал сразу поиск в связи с 0 адресом, начинал цепочку B2--A2--A1--A--- и.т.д)
5 продлеваем основную цепочку
: B DUP SWAP DROP ;BR A
6 в дальнейшем добавление слов происходит как обычно

2 BRLAST , BRSW ( "name -- )

Т.к. основной поиск всегда происходит с последнего созданного слова, то в данном случае выглядеть он будет D--C--B--A , остальные ветки для него скрыты

TREEFIND'ом можно управлять двумя способами:

BRLAST - во время создания, воткнуть после создания слова, с которого начинается поиск

BRSW - после создания структуры дерева, указать слово после BRSW, с которого начинается поиск

Поиск начинается именно со слова NFA которого в TREEFIND - слова приписанные после него НЕ ПРОСМАТРИВАЮТСЯ. Т.е. можно определять не только ветку для поиска но и положение в ней.

3 BRCH ( "name1" "name2" )

BRCH - меняет привязку слова на ходу, позволяя соединять вместе, разрезать на две, удалять ( в отличие от словарей! ) ветви

"name1" - слово которому меняем привязку

"name2" - слово - новая привязка

Например:

BRCH A2 C1

поменяет привязку A2, ветки сольются, дерево станет таким

Слова в словаре ---->
В 1 A--------------------------B---C----D
е 2 +--A1---B1---C1
т +--A2---B2
в
и
|
|
|
v


точнее таким

Слова в словаре ---->
В 1 A------------------------B---C---D
е 2 +--A1--B1--C1--A2--B2
т
в
и
|
|
|
v


4 BR0 ( "name" -- )

BR0 - обнуляет связь слова на ноль, позволяя создавать отгороженнные от всех остальных слов списки

Пример:

Берём дерево выше и обнуляем A1

BR0 A1

получаем
Слова в словаре ---->
В 1 A------------------------B---C---D
е 2 A1--B1--C1--A2--B2
т
в
и
|
|
|
v

отгороженный список с A1, при TREEFIND'е начиная с В2 получится цепочка

В2--А2--С1--В1--А1 , на А1 поиск обрывается

5 TREEFIND ( addr u -- 0 | xt 1 | xt -1 )

TREEFIND - ищет по текущей ветви и вниз до 0, слово заданное addr и количеством символов u , возвращает 0, если не нашёл , xt и 1 если нашёл, и xt -1 - нашёл слово IMMEDIATE исполнения

Т.к. запись в основной поиск не работает - можно использовать как дополнительный поиск, например, как поиск слов для взаимодействия с пользователем, путём отгораживания нужных слов в отдельную ветвь и использования зануления начала этой ветви
Сообщение Добавлено: Пн авг 30, 2010 14:19
  Заголовок сообщения:  Re: Борьба со словарями!  Ответить с цитатой
Antender писал(а):
Уже есть! Как раз написал.

Хм замечательно, только.... :roll:
Желательно и пример использования изобретения.
Показывающий приимущество данного метода, а... :?:
Сообщение Добавлено: Пн авг 30, 2010 10:03
  Заголовок сообщения:  Re: Борьба со словарями!  Ответить с цитатой
Последняя редакция: 30.07.2010 14:25
Код:
[PRE]
\ Библиотека для работы с древовидными словарями.
\ Позволяет присоединять компилируемые слова к любой части дерева.
\ Для создания новой ветви дерева компилируйте присоединяемое слово при помощи :
\ и ;BR "слово-присоединение" .
\ Все последующие слова можно добавлять через : и ; .
\ Заканчивается создание ветви словом BREND
\ Нисходящий поиск по дереву начинается со слова, NFA которого занесено в переменную (TREEFIND).

\ ----------Переменные-------------------------------------------------
VARIABLE (TREEFIND) \ NFA слова с которого начинается нисходящий поиск по дереву

\ ----------Внутренние слова реализации--------------------------------
: BR ( NFA xt -- ) \ изменить LFA слова c NFA на xt ( для отделения ветви )
NEAR_NFA DROP SWAP NAME>L ! ;

\ ----------Слова доступные для использования--------------------------
: BRCH ( "name1" "name2" ) \ изменить LFA "name1" на NFA "name2"
' NEAR_NFA DROP ' BR ;
: ;BR ( "name" -- ) \ закончить компиляцию новой ветви
POSTPONE ; ' LATEST BR ; IMMEDIATE
: BRLAST  \ делает ветку видимой для поиска
LATEST (TREEFIND) ! ;
: BRSW ( "name" -- ) \ заменяет начальное слово для поиска на "name"
' NEAR_NFA DROP (TREEFIND) ! ;
: BR0 ( "name" )
0 ' NEAR_NFA DROP NAME>L ! ;

\ ----------Внутренние слова реализации---------------------------------
: TREEFIND ( addr u -- 0 | xt 1 | xt -1 ) \ заменяет стандартный FIND
(TREEFIND) @
BEGIN
?DUP
IF >R 2DUP R@ COUNT COMPARE R> SWAP
    IF CDR FALSE
    ELSE NIP NIP DUP NAME> ?IMMEDIATE IF 1 ELSE -1 THEN TRUE
    THEN
ELSE
    DROP DROP 0 TRUE
THEN
UNTIL ;
[/PRE]
Сообщение Добавлено: Вс авг 29, 2010 12:38
  Заголовок сообщения:  Re: Борьба со словарями!  Ответить с цитатой
mOleg писал(а):
Тогда я вообще не вижу причин разведения этого, ээ, обсуждения.

Так ведь тема то какая "борьба со словарями"
Есть ведь мнение что надо с ними бороться :))
Представляю себе на форуме автомобилистов кто нибудь предложил бы бороться с рулем например.
Кстати автор темы давно молчит интересно реализовал он свои идеи?
Интересно бы и на код взглянуть. Как раз это и есть самое ценное (вернее этого пока нет :roll: )
Сообщение Добавлено: Вс авг 29, 2010 11:24
  Заголовок сообщения:  Re: Борьба со словарями!  Ответить с цитатой
chess писал(а):
Если вы сделали вывод, что я против контекста вообще - то вы ошиблись. Я против реализаций контекста, использование которых основаны на задействовании внимания программиста.Во многих языках программирования, и в естественных языках кстати, контекст опирается надолговременную память а не на кратковременную. В этом их принципиальное отличие от фортас его словарями.

Тогда я вообще не вижу причин разведения этого, ээ, обсуждения.
Наличие контекста в любом современном форте не заставляет никого его использовать.
Вы можете как создать свой рабочий словарь и с ним работать, так и располагать все в словаре FORTH.
Если очень мешает, то можно вообще исправить исходник форта и пересобрать с одним единственным словарем, или вообще без словарей.
Сообщение Добавлено: Сб авг 28, 2010 18:26
  Заголовок сообщения:  Re: Борьба со словарями!  Ответить с цитатой
chess писал(а):
Я против реализаций контекста, использование которых основаны на задействовании внимания программиста.

+1. Программист не развлекается с языком, а использует его для решения какой-то задачи.
Сообщение Добавлено: Сб авг 28, 2010 18:23
  Заголовок сообщения:  Re: Борьба со словарями!  Ответить с цитатой
Вообще, любая структура (любой способ организации чего-то) осуществляется в соответствии с некоторым принципом, который находят исходя из некоторой цели (и целесообразности)
Бессмысленно спорить, не исходя из цели ИМХО
Сообщение Добавлено: Сб авг 28, 2010 16:19
  Заголовок сообщения:  Re: Борьба со словарями!  Ответить с цитатой
mOleg писал(а):
В реальном мире мы тоже вынуждены учитывать контекст: общаясь с коллегой мы находимся в одном контексте, с продавцем - другой, внутри семьи - третий, и.т. д.

Если вы сделали вывод, что я против контекста вообще - то вы ошиблись. Я против реализаций контекста, использование которых основаны на задействовании внимания программиста.
Во многих языках программирования, и в естественных языках кстати, контекст опирается на
долговременную память а не на кратковременную. В этом их принципиальное отличие от форта
с его словарями.
Сообщение Добавлено: Сб авг 28, 2010 10:07
  Заголовок сообщения:  Re: Борьба со словарями!  Ответить с цитатой
chess писал(а):
Не знаю, но думаю, что вряд-ли.

по крайней мере раньше я его не встречал.

chess писал(а):
Все описания страдают литьем воды в той или иной степени, а исходников там нет, поэтому ничего конкретно не скажу.

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

chess писал(а):
Цель исключить забивание внимания контекстом. Причем это относится не толькок словарям, но и к стекам и к состоянию форт-системы(компиляция-исполнение), к значению основания системы счисления.Это все контекст.

боюсь, мы не договоримся ни до чего.

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

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

\ поиск lfa словарной статьи с именем asc # в указанном vid словаре
: SEARCH-NAME ( asc # vid --> lfa | 0 ) DUP off_quest PERFORM ;

А то, как ищет словарь имя и как устроен сам словарь - его личное дело, а это позволяет использовать в качестве имен произвольные данные, иметь различные методы поиска для разных словарей, работать с неперечислимыми именами и т.д.

chess писал(а):
Но это дело десятое, как я уже говорил, главное в том, что не будет контекста в памяти программиста.

В реальном мире мы тоже вынуждены учитывать контекст: общаясь с коллегой мы находимся в одном контексте, с продавцем - другой, внутри семьи - третий, и.т. д.
Сообщение Добавлено: Пт авг 27, 2010 18:55
  Заголовок сообщения:  Re: Борьба со словарями!  Ответить с цитатой
mOleg писал(а):
вы создатель этого потнятия

Не знаю, но думаю, что вряд-ли.
mOleg писал(а):
хотя, в том же СПФе локальные переменные подобным образом реализованы.

Нет у меня сделано абсолютно по-другому.
mOleg писал(а):
во время поиска контекст не переключается, поиск слов может быть очень быстрым (почитайте, как поиск реализован в СМАЛ32 - там скорость поиска от количества словарей в контексте практически не зависит), к тому же не забывайте, что подавляющее большиство слов находится в верхнем контекстном словаре (вобщем, имхо, проблема из пальца).

Все описания страдают литьем воды в той или иной степени, а исходников там нет, поэтому ничего конкретно не скажу.
Тут надо расставить точки над i - ускорение поиска не самоцель, это лишь следствие. Ну не ускорился бы поиск ну и ладно. Даже
бы если и замедлился все равно нормально. Цель исключить забивание внимания контекстом. Причем это относится не только
к словарям, но и к стекам и к состоянию форт-системы(компиляция-исполнение), к значению основания системы счисления.
Это все контекст.

Что касается конкретно ускорения поиска в результате перехода к одному словарю, то:
Код:
USER-CREATE S-O 16 CELLS TC-USER-ALLOT
USER-VALUE CONTEXT

: SFIND ( addr u -- addr u 0 | xt 1 | xt -1 )
  S-O 1- CONTEXT
  DO
    2DUP I @ SEARCH-WORDLIST
    DUP IF 2SWAP 2DROP UNLOOP EXIT THEN DROP
   I S-O = IF LEAVE THEN
   1 CELLS NEGATE
  +LOOP 0 ;

: FIND1 ( c-addr -- c-addr 0 | xt 1 | xt -1 )
  DUP >R COUNT SFIND
  DUP 0= IF NIP NIP R> SWAP ELSE RDROP THEN  ;


SFIND сводится только к SEARCH-WORDLIST(при одном словаре)
а для SEARCH-WORDLIST время поиска не будет зависеть от количества слов
в единственном словаре(в случае использования быстрого алгоритма поиска).
В общем случае, суммарное время поиска при компиляции программ при этом будет
заведомо меньше, чем при наличии нескольких словарей.

Но это дело десятое, как я уже говорил, главное в том, что не будет контекста в памяти программиста.
Сообщение Добавлено: Пт авг 27, 2010 16:36
  Заголовок сообщения:  Re: Борьба со словарями!  Ответить с цитатой
mOleg писал(а):
подавляющее большиство слов находится в верхнем контекстном словаре (вобщем, имхо, проблема из пальца).

Точнее сказать обычно наверху тот словарь где и предполагается искать слова и значит они находятсся быстро. Хотя скорость их нахождения в большинстве применений и не важна вовсе.
Сообщение Добавлено: Пт авг 27, 2010 00:29
  Заголовок сообщения:  Re: Борьба со словарями!  Ответить с цитатой
chess писал(а):
Я вот тоже не пойму почему вы никак не поймете, что если-бы у разных процедур были-бы разные имена, тонадобности в контекстных словарях не было-бы в принципе.

может потому что я делал как минимум несколько ЦК, и еще один сильно под свои нужды пререрабатывал,
а может потому, что реализоваывал нескольк вариантов наборов имен для упрощения описания аппаратуры, предварительно намучившись с одним словарем, имли потому что пользовался фортом 83 стандарта и знаю, как с одним деревом бывает тяжело добиться результата. Или потому что очень долго думал над тем, как лучше организовать словарь изнутри, чтобы использовать весь возможный потенциал стандартными средствами, и таки сделал пока что устраивающий меня вариант.

chess писал(а):
Локальный словарь(не знаю есть такое общеупотребительное понятие или нет)

вы создатель этого потнятия 8)

chess писал(а):
действует применительно к фортув рамках одного определения. О локальных словах я уже писал.

хотя, в том же СПФе локальные переменные подобным образом реализованы.

chess писал(а):
Это время поиска для одного словаря в абсолютном выражении будет меньше чем для набора словарей из-за наличиямеханизма переключения контекста.

во время поиска контекст не переключается, поиск слов может быть очень быстрым (почитайте, как поиск реализован в СМАЛ32 - там скорость поиска от количества словарей в контексте практически не зависит), к тому же не забывайте, что подавляющее большиство слов находится в верхнем контекстном словаре (вобщем, имхо, проблема из пальца).
Сообщение Добавлено: Чт авг 26, 2010 16:56

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


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