СЛОВАРИ ФОРТА В РЕАЛИЗАЦИИ КОНЕЧНОГО АВТОМАТА

Alex

Иногда на задачи которые мы решаем хорошо посмотреть сквозь автоматную парадигму
В форте есть несколько реализаций конечных автоматов, было некоторое
обсуждение и у нас на форуме
Один из способов представления конечного автомата - в виде таблицы
где строки это состояния автомата, столбцы входные воздействия (события) а в ячейках
зафиксировано слово которое будет выполнено и следующее состояние в которое должен перейти автомат.
Мы попробуем использовать для задания и реализации автомата словарь форта.
В качестве примера возмем демонстрационный автомат описанный
в работах J.V.Noble,который имеет три состояния (0,1,2) и четыре
входных события (d,m,p,e). Автомат предназначен для контроля ввода числа.
Число может быть отрицательным и иметь десятичную точку. Исходное
состояние 0, при поступлении цифры (событие d) либо знака минуса (событие m)
автомат переходит в состояние 1, а при поступлении десятичной точки (событие p)
идет переход в состояние 2. В состоянии 1 ("продолжение ввода") при поступлении
цифр остаемся в этом же состоянии, при поступлении события десятичной точки
идет переход в состояние 2 ("завершение ввода") в этом состоянии
отрабатываются только поступление цифр. Поступление <Enter> (событие e) означает
конец ввода и выход из автомата.

При реализации автомата мы используем не один, а два словаря.
В первом словаре с именем FSM сгруппируем слова определяющие действия и
переходы нашего автомата. Имена этих слов состоят из трех частей

: <evt><cur><nxt> <действия> ; это следует читать так -

" При входном воздействии <evt> для автомата в состоянии <cur>
выполняются <действия> и автомат переходит в состояние <nxt> "

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

Во втором словаре с именем EVENT сгруппируем слова-процедуры
которые анализируют значение на стеке и выдают флаг, а их
имена соответствуют части <evt>.

Код:

S" order.f"          INCLUDED

USER key                   ( input key  )
USER event                 ( event vocs )
USER nfa                   ( nfa fld    )

: SubName ( org len ) CREATE , , DOES> DUP CELL+ @ nfa @ COUNT DROP + SWAP @ ( a u ) ;

0 1 SubName evt
1 1 SubName cur
2 1 SubName nxt

HERE nfa !

CREATE state cur NIP ALLOT     ( cur state  )

: event? ( -- 0 | xt 1 | xt -1 ) evt event @ SEARCH-WORDLIST ;

: state? ( -- f ) state cur SWAP OVER COMPARE 0=  ;

: test? ( xt -- f ) key @ SWAP EXECUTE ;

: INP. key @ EMIT ;

: NXT>CUR  nxt state SWAP CMOVE ;            

: exec!  nfa @ NAME> EXECUTE NXT>CUR ;

: IDENTIFY ( nfa --  )   nfa !

 event? ?DUP 0 = IF nfa @ CDR EXIT THEN         

         1 = IF 
                test?                           
             ELSE 
      ( -1 )    test? state? AND                
             THEN  

      ( f )  IF 
               exec! RDROP EXIT
             ELSE
               nfa @ CDR 
             THEN 
;

: FSEARCH ( wid -- ) 
  @ BEGIN 
     DUP 
    WHILE 
     IDENTIFY 
    REPEAT 
  DROP
;

WORDLIST: EVENT

: d ( C -- f ) [CHAR] 0 [CHAR] 9 1+ WITHIN ;
: m ( C -- f ) [CHAR] - = ;
: p ( C -- f ) [CHAR] . = ;
: e ( C -- f )       13 = ;   IMMEDIATE

WORDLIST;

WORDLIST: FSM

: d01  INP.   ;
: d11  INP.   ;
: d22  INP.   ;

: m01  INP.   ;
\ : m11  NOOP  ;
\ : m22  NOOP  ;

: p02  INP.   ;
: p12  INP.   ;
\ : p22  NOOP  ;

: e**  RDROP RDROP RDROP RDROP ; 

WORDLIST;

: INIT-FSM   BL  key ! state cur NIP [CHAR] 0 FILL  EVENT event ! FSM >ORDER ;

: READ-KEY   KEY key ! ;

: AAA   
   INIT-FSM  
     BEGIN  
        READ-KEY FSM FSEARCH  
     AGAIN   
;

И как же это все работает? Когда мы нажимаем клавишу запускается поиск (перебор)
по словарю нашего автомата FSM. Волшебное слово IDENTIFY вычленяет из текущего
имени слова часть evt и проверяет наличие подобного слова в словаре EVENT,
если есть, то выполняет его тем самым проверяя входное событие на соответствие
этому слову, далее проверяет текущее состояние автомата state с частью
имени <cur> и если проверка вернула успех (истину) то выполняет действия этого слова
и меняет состояние автомата, заканчивает перебор. A если проверка не прошла, то
переходим к следующему слову в словаре FSM. В словарях мы перебираем слова от
последнего определенного к первому, а это значит что наша "табличка" в FSM
будет проверятся снизу вверх. Некоторые слова в словаре EVENT могут иметь
признак IMMEDIATE а это является сигналом для IDENTIFY, что не следует
проверять состояние автомата, а сразу выполнить действия, так реализован
выход из автомата в консоль форта.

Обратите внимание на закоментированные слова в словаре FSM
в этих ситуациях автомат не должен делать что-либо, при
табличном представлении они должны быть корректно закодированы
и присутсвовать в таблице, при реализации через словарь мы их
можем просто выбросить. В нашем простейшем примере это треть (33%)

Интересно сработает ли этот набор трюков в умных словарях mOLEGа ?

А может быть можно вообще обойтись без словарей
и реализовать такое техникой NotFound которой в совершенстве владеет Chess ?

dynamic-wind

Alex писал(а):

А может быть можно вообще обойтись без словарей

... чтобы не делать линейный поиск и не парсить имена слов?
Посмотрите на парсер, который выдает lex/yacc. Слабо такое же сделать?

mOleg

Alex писал(а):

Интересно сработает ли этот набор трюков в умных словарях mOLEGа ?

Alex писал(а):

Волшебное слово IDENTIFY вычленяет из текущего
имени слова часть evt и проверяет наличие подобного слова в словаре EVENT

Слишком на мой взгляд сложно.
Чем хуже примерно такой вариант:

VOCABULARY дробные
: 0 ( d --> d ) 10 DS/ ;
: 1 ( d --> d ) 2^32 D+ 10 DS/ ;
: 2 ( d --> d ) 2^33 D+ 10 DS/ ;
...

VOCABULARY целые
: 0 10 * ;
: 1 10 * 1 + ;
: 2 10 * 2 + ;
...
: . 0 0 дробные ;
...

: init 0 целые ;

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

Alex писал(а):

Интересно сработает ли этот набор трюков в умных словарях mOLEGа ?

А какая проблема? Словари, как словари, только устроены внутри скорее как объекты. То есть пользоваться можно и нужно ими в первую очередь обычным образом, а лишь в последующие как более мощным и гибким механизмом.

in4

Код пока не проверял, но как-то так:

Код:

\ 2010.10.30  пример конечного автомата

\ Язык CLCF - ColorLessColorForth
\ В качестве примера возмем демонстрационный автомат описанный
\ в работах J.V.Noble,который имеет три состояния (0,1,2) и четыре
\ входных события (d,m,p,e). Автомат предназначен для контроля ввода числа.
\ Число может быть отрицательным и иметь десятичную точку. Исходное 
\ состояние 0, при поступлении цифры (событие d) либо знака минуса (событие m)
\ автомат переходит в состояние 1, а при поступлении десятичной точки (событие p)
\ идет переход в состояние 2. В состоянии 1 ("продолжение ввода") при поступлении
\ цифр остаемся в этом же состоянии, при поступлении события десятичной точки
\ идет переход в состояние 2 ("завершение ввода") в этом состоянии
\ отрабатываются только поступление цифр. Поступление <Enter> (событие e) означает 
\ конец ввода и выход из автомата.

\ Syntax variant (todo)
d? ( C -- f )  [CHAR] 0 [CHAR] 9 1+ WITHIN ;
m? ( C -- f )  [CHAR] - = ;
p? ( C -- f )  [CHAR] . = ;
e? ( C -- f )        13 = ;


VALUE key

\ Syntax variant simple
d? ( -- f )
   key [CHAR] 0 [CHAR] 9 1+ WITHIN ;
m? ( -- f )
   key [CHAR] - = ;
p? ( -- f )
   key [CHAR] . = ;
e? ( -- f )
   key 13 = ;


key!
   KEY TO key ;

state0
   key!
   d?
      state1 ;
   m?
      state1 ;
   p?
      state2 ;
   e?
Ok
      ." No errors" ;
err
   ." Error" ;
state1
   key!
   d?
      state1 ;
   p?
      state2 ;
   e?
      Ok ;
   err ;
state2
   key!
   d?
      state2 ;
   e?
      Ok ;
   err ;

fsm  \ run fsm
   ." Enter number! >" state0 ;

 fsm  \ really run fsm



\ use convetions
\ >name
\ ==
\ > : name

\ ><TAB>condition
\ ><TAB><TAB>words
\ ><TAB>
\ ==
\ >condition IF
\ >words
\ >THEN

\ >word ;
\ ==
\ >CALL word
\ >RET
\ with tail recursion optimization
\ ==
\ >JMP word

Используются вынесенные из кучи(кодофайла) словари. Определение слова == заданию адреса этого слова в словаре. Т.е. определенное слово получается константой с адресом HERE на момент определения.

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

Да, это сообщение можно считать продолжением 2х половинок статьи об эквивалентности программы на colorForth конечному автомату

Alex

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

Код:

: Кнопка-пуск.закрыто.открыто   заслонку-поднять  ;

По мере заполнения словаря такими определениями формируется
проблемно-ориентированный автоматный DSL

To: in4 я скидывал Вам в лс ссылку по визуальному программированию, дошла ли?

dynamic-wind

Компактнее--это верно.
Можно добавить в такую программу препроцессор (своего рода компилятор),
который, если не жалко памяти, распарсит имена слов-состояний, построит табличку переходов--и дальше запустит табличный алгоритм.

mOleg

Alex писал(а):

Собственно я хотел показать что в форте возможны не только классические реализации конечных автоматов через оператор SWITCH или таблицы, но и своими родными средствами.

Так словари по сути и реализуют конечный автомат (только продвинутый).

Alex

Если код ColorLessColorForth записать так

state0 key! d? state1 ; m? state1 ; p? state2 ; e? Ok ." No errors" ; err ." Error" ;
state1 key! d? state1 ; p? state2 ; e? Ok ; err ;
state2 key! d? state2 ; e? Ok ; err ;

то это напомнило самую первую реализцию конечных автоматов увиденную мною тут

5 STATES DISPLAY

STATE 1 09 01 !S TAB 27 02 !S DROP 01 OR-ELSE EMIT ( только выдача изображений символов )
STATE 2 67 03 !S CLR 80 03 !S DROP 84 05 !S DROP 01 OR-ELSE BAD-CMD ( получен символ ESC )
STATE 3 04 OR-ELSE NOOP ( строка для команды курсора - оставляем на стеке )
STATE 4 01 OR-ELSE !CURSOR ( столбец - устанавливаем позицию )
STATE 5 01 OR-ELSE !TAB ( обновление значения табуляции )

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

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

>mOleg:
>Так словари по сути и реализуют конечный автомат (только продвинутый).

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

надо только ее увидеть и титанический труд ...

В первой ссылке стартового топика есть очень много интересного, особенно в разделе проекты

dynamic-wind

Alex писал(а):

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

Но ведь Ваш способ задает КА (В состоянии X делай Y, затем под воздействиями Z{i} переключись в новое состояние X'{i}), верно? Он только медленный. Но автоматическими средствами его всегда можно преобразовать в табличную форму с быстродействием переключения O(1).

вопрос

dynamic-wind писал(а):

Alex писал(а):

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

Но ведь Ваш способ задает КА (В состоянии X делай Y, затем под воздействиями Z{i} переключись в новое состояние X'{i}), верно? Он только медленный. Но автоматическими средствами его всегда можно преобразовать в табличную форму с быстродействием переключения O(1).

Кстати, наглядность реализации и многоразовость использования вновь принесены в жертву простоте разработки

in4

dynamic-wind писал(а):

Он только медленный. Но автоматическими средствами его всегда можно преобразовать в табличную форму с быстродействием переключения O(1).

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

Alex писал(а):

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

Ну это пока нет. Доказательство того, что она не существует, не проведено...

Решения нет или его трудно найти, если оставаться в рамках принятой системы. Если выйти за рамки, использовать то, что ранее не входило в решение, тогда можно и решить...

chess

mOleg писал(а):

Так словари по сути и реализуют конечный автомат (только продвинутый).

Через словари медленно,
Проще разнести автомат на две части:
1-часть - назовем ее генератор событий,
2-часть - обработчик событий,
тогда все независимые события легко перечисляются в генераторе,
а в обработчике перечисляются отдельные действия как реакция на события с учетом
состояния автомата. После обработки очередного события обнуляем код события и обращаемся в генератор за очередным.
Если событий нет - ничего не делаем или выполняем фон. задачу.
По сути набор отдельных событий связывается с набором отдельных действий.
пс. Так я писал программы для некоторых контроллеров.

Код:

0 VALUE evt
0 VALUE key
0 VALUE st

: get-event         KEY TO key
  key 45 =          IF 1 TO evt EXIT THEN
  key 48 58 WITHIN  IF 2 TO evt EXIT THEN
  key 46 =          IF 3 TO evt EXIT THEN
  key 13 =          IF 4 TO evt THEN
;
: hnd-event
  evt 1 = evt 2 = OR st 0= AND  IF key EMIT  1 TO st 0 TO evt THEN
  evt 2 = st 1 = st 2 = OR AND  IF key EMIT          0 TO evt THEN
  evt 3 = st 1 = AND            IF key EMIT  2 TO st 0 TO evt THEN
  evt 4 = st 2 = AND            IF key EMIT  3 TO st THEN
;
\ ввод правильного числа
: INP-Q
  BEGIN get-event hnd-event st 3 = UNTIL
;

STARTLOG
INP-Q

лог

Код:

-12345.5678

 Ok

mOleg

chess писал(а):

mOleg писал(а):
Так словари по сути и реализуют конечный автомат (только продвинутый).
Через словари медленно,

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

Alex

Мда .... структуризация имени, два словаря ... бред

Вообщем еще один вариант конечного автомата, используется
тот факт что если мы находимся в каком-то определении то значит и так находимся
в каком-то состоянии ну и переходы ( по мотивам примера от in4 )

Код:

USER key                   

: key! KEY key ! ;
: INP. key @ EMIT ;

USER x0
USER x1
USER x2

: ->0 RDROP x0 @ >R ;
: ->1 RDROP x1 @ >R ;
: ->2 RDROP x2 @ >R ;

: d? (  -- f ) key @ [CHAR] 0 [CHAR] 9 1+ WITHIN ;
: m? (  -- f ) key @ [CHAR] - = ;
: p? (  -- f ) key @ [CHAR] . = ;
: e? (  -- f ) key @       13 = ;   

: state0    d? IF INP. key! ->1 EXIT THEN  
            m? IF INP. key! ->1 EXIT THEN 
            p? IF INP. key! ->2 EXIT THEN
            e? IF RDROP RDROP   EXIT THEN  key! ->0 ;

: state1    d? IF INP. key! ->1 EXIT THEN  
            p? IF INP. key! ->2 EXIT THEN
            e? IF RDROP RDROP   EXIT THEN  key! ->1 ;

: state2    d? IF INP. key! ->2 EXIT THEN  
            e? IF RDROP RDROP   EXIT THEN  key! ->2 ;

: ini ['] state0 x0 ! ['] state1 x1 ! ['] state2 x2 !  ;

: test  ini key! state0 ;

Ну вот и есть маленький положительный результат - еще 2 варианта этот и от chessа !!!

Alex

А используя стек возвратов вместо переменных получим :

Код:

0 VALUE key                   

: key! KEY DUP 13 = IF DROP 4 RFREE EXIT ELSE TO key THEN ;

: ->0  RDROP 0 RP+@ >R ;
: ->1  RDROP 4 RP+@ >R ;
: ->2  RDROP 8 RP+@ >R ;

: d? (  -- f ) key [CHAR] 0 [CHAR] 9 1+ WITHIN ;
: m? (  -- f ) key [CHAR] - = ;
: p? (  -- f ) key [CHAR] . = ;

: state0  key!  d? IF key EMIT ->1 EXIT THEN  
                m? IF key EMIT ->1 EXIT THEN 
                p? IF key EMIT ->2 EXIT THEN  ->0 ;
           
: state1  key!  d? IF key EMIT ->1 EXIT THEN  
                p? IF key EMIT ->2 EXIT THEN  ->1 ;

: state2  key!  d? IF key EMIT ->2 EXIT THEN  ->2 ;

: test ['] state2 >R ['] state1 >R ['] state0 DUP >R >R  ;

СЛОВАРИ ФОРТА В РЕАЛИЗАЦИИ КОНЕЧНОГО АВТОМАТА

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