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

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 5 ] 
Автор Сообщение
 Заголовок сообщения: ColorForth и конечные автоматы
СообщениеДобавлено: Сб апр 14, 2007 14:01 
Не в сети

Зарегистрирован: Сб май 06, 2006 12:01
Сообщения: 959
Откуда: Украина, Харьков
Благодарил (а): 2 раз.
Поблагодарили: 7 раз.
Дано хотелось эту статью написать. Только сейчас сподобился...

Программная реализация простого конечного автомата предполагает одну переменную для хранения его состояния и бесконечный цикл множественного выбора действий по значению этой переменной.
Код:
1 CONSTANT Случай1
2 CONSTANT Случай2
3 CONSTANT Случай3
Случай1 VALUE Состояние
: КАвтомат
   Состояние Случай1 = IF Действие1  Случай3 TO Состояние THEN
   Состояние Случай2 = IF Действие2  Случай1 TO Состояние THEN
   Состояние Случай3 = IF Действие3  Случай2 TO Состояние THEN
   ;
: КА-Цикл BEGIN
   КАвтомат
   AGAIN ;

Возможны оптимизации, вид изменится, но принцип такой. Анализируем состояние - выполняем действие - устанавливаем новое состояние.
Если КАвтомат запускать не в цикле КА-Цикл, а во внешнем, то в нем получится "многозадачность" и КА будет работать "параллельно" с другими частями системы.
Почему это возможно? Потому что, независимо от состояний, управление всегда проходит через одну точку - КАвтомат. Разрыв в этой одной точке позволяет легко добавить программе дополнительные "параллельные" ветви.
Далее читаем Броуди и видим, что мы устанавливаем Флаг (переменную Состояние), который потом проверяем. Это сложно. Надо устанавливать значение. А какое значение?
Самое лучшее - сразу устанавливать код, который дожен быть выполнен в следующем состоянии! Делаем следующий шаг и сразу выполняем этот код!
Код:
\ язык CLCF - на нем это видно проще. В обычном Форте посложнее, но тоже можно.
: КА-Цикл  \ множественные точки входа, имя - просто метка, адрес в коде
: Действие1  ( действия Действие1 ) Действие3 ;  \ переход на соотв. слово
: Действие2  ( действия Действие2 ) Действие1 ;
: Действие3  ( действия Действие3 ) Действие2 ;

Получается Форт-программа, эквивалентная коду конечного автомата, но проще! Нет лишних сущностей, не надо придумывать лишних имен!
Единственная проблема - для получения "многозадачности" КА-цикл надо где-то разорвать.
Но теперь нельзя выделить одну точку, через которую управление проходит при любых состояниях. :( (Аналогичная ситуация на уровне слов - нет одной точки для перехвата управления - возникает и при использовании распределенных адресных интерпретаторов, и при использовании нативного кода=>трудно сделать переключение задач на этом уровне)

Что же должен делать такой разрыв?

Он может позволять выполнять еще какой-то код. Тогда он может выглядеть просто как вызов слова.

Он может вернуть управление вызвавшей программе. Но тогда ему надо как-то сохранить свое состояние. Сохранение состояния в стеке возвратов позволит вызвавшей программе продолжить выполнение КА-Цикл с прерванного места просто возвратом. Но это не получится повторить несколько раз... :( Значит, только переменная, в которой будет сохраняться адрес продолжения. Этот вариант больше похож на первоначальный код.

В каких же местах он должен быть?
Добавлять его прийдется либо во все действия ДействияN , либо только в те, которые выполняются долго (это должен знать разработчик) - формального правила, по-видимому, нет... :( Эта же проблема возникнет и при реализации кооперативной многозадачности в рамках одной программы. Где разрывать? Можно ли придумать хорошее формальное правило для таких разрывов?
Что вы думаете по этому поводу?

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

Сам я пока склоняюсь к выборочной вставке выхода с сохранением контекста.

_________________
With best wishes, in4.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб апр 14, 2007 14:43 
Хе-хе.

Это я так понимаю что и моя (одна из) реализаций colorForth'а на конечных автоматах вдохновила в том числе?..

~profit/lib/colorForth/colorSP4th.f.

Поставленный вопрос актуален вообще для всей реализации КА. Я его даже ставил уже в соответствующей теме (см. "вопросы по реализации").

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


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вс апр 15, 2007 19:31 
Не в сети

Зарегистрирован: Сб май 06, 2006 12:01
Сообщения: 959
Откуда: Украина, Харьков
Благодарил (а): 2 раз.
Поблагодарили: 7 раз.
profiT писал(а):
Это я так понимаю что и моя (одна из) реализаций colorForth'а на конечных автоматах вдохновила в том числе?..

Ага! И твои тоже!

Вот мне почему-то конечные автоматы программами на Форте бОльше нравятся... :)
Может, размером? ;) Или понятностью?
Хотя, по-хорошему, смотреть надо и так и так. Просто программа на Форте (особенно пример из Броуди про тарификацию) - это уже оптимизированная реализация КА. :)
А, поскольку большинство стандартных протоколов можно описать КА-ми, то если их записать на Форте - получится бОльшая часть ОС !!

К КА я очень серьезно присмотрелся после статей на softcraft-е. Посмотрел реализации на C...
К этому времени мой коллега буквально заставил меня написать одну программу на Делфи в таком стиле. Бесконечные case-ы с числами-состояниями меня утомили. Было очень похоже на старый Бейсик без renum. Тоже надо было нумеровать состояния не подряд - оставлять места для исправлений и была куча проблем, если дополнение требовало бОльше состояний - приходилось править числа по бОльшому куску кода... :(
Мое естественное желание обозвать состояния константами разбилось о его желание использовать эти числа для ориентации в почти одинаковых участках кода... ;)

Но с символьными метками это показалось мне похожим на что-то знакомое - на Форт! :)
И я уже продумал следующий шаг - сразу выполнять эти новые состояния...
Только что я, наконец (а давно собирался!), убедился, что даже явное сохранение текущего адреса выполнения будет в среднем эффективнее варианта с case и однократным проходом(назовем этот вариант В1).
В самом деле, в В1 есть много проверок - анализ состояния, которые теперь не нужны - мы сразу знаем, куда идти!
Каждая ветвь устанавливает флаг, затем происходит выход. Установка флага, если его размер равен размеру адреса возврата, эквивалентна сохранению самого адреса возврата. Тут В1 может сэкономить, только если использует для флага меньше байтов, чем размер адреса, но это экономия незначительна и может быть сведена на нет компилятором ради эффективности кода (учитывая префиксы и выравнивание), следовательно, ею можно пренебречь (до тестов на реальных примерах). А новый вариант может просто не выходить из некоторых ветвей, сразу выполняя переход на следующую ветвь! Экономим на установке флага и при этом учтем, что переход эффективнее, чем выход+последующий вызов. По размеру кода вызов В1+возвраты из каждой ветви, конечно, короче переходов, но с учетом условных переходов выигрыш будет меньше, а с учетом проверок, выигрыша вообще не будет. Еще случай, где В1 мог бы выигрывать - большое количество состояний с переходом в себя же. В1 может не изменять флаг - состояние. Но размер анализа состояния будет все же больше, чем разница размеров возврата и перехода.
Таким образом, предлагаемый вариант можно оценить как не намного худший в худшем случае и более эффективный в лучшем случае.

У меня есть мысль продолжить дальше идеи Мура в CF (о компиляции при необходимости) и сделать "встраиваемые" и "самоисключающиеся" обработчики событий. Попробую этот стиль на микроконтроллерах... ;)

Например, сделать такой вариант.
Менеджер задач будет иметь несколько списков обработчиков сообщений (для каждой разновидности событий - свой, количество списков - выделяемых разновидностей - может определяться и динамически.
Программа будет добавлять маленькие КА в соответствующие списки обработчиков сообщений, а они уже будут сами работать в соответствии со своей задачей.
Можно сделать несколько "ловителей", если задача должна сработать при различных событиях, которые активируют свою задачу и уберут остальных "ловителей" в других списках. При этом сама задача будет проще закодирована.
Так, например, процесс, ожидающий 4секунды, появится в очереди на выполнение только через 4 секунды, а до этого времени никак не будет занимать процессор.

Хгм, и тогда программа будет состоять из маленьких КА (или эквивалентов на Форте - из слов- как посмотреть).
Что ж! Еще один взгляд на программирование(парадигма) - программа, как связанная группа КА-ов 1:1 ложится на Форт! :)

_________________
With best wishes, in4.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вс апр 15, 2007 22:37 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
in4 писал(а):
Каждая ветвь устанавливает флаг, затем происходит выход. Установка флага, если его размер равен размеру адреса возврата, эквивалентна сохранению самого адреса возврата. Тут В1 может сэкономить, только если использует для флага меньше байтов, чем размер адреса, но это экономия незначительна и может быть сведена на нет компилятором ради эффективности кода (учитывая префиксы и выравнивание), след...

очень похоже на описание работы косвенного шитого кода 8)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн апр 16, 2007 03:55 
Не в сети

Зарегистрирован: Сб май 06, 2006 12:01
Сообщения: 959
Откуда: Украина, Харьков
Благодарил (а): 2 раз.
Поблагодарили: 7 раз.
mOleg писал(а):
очень похоже на описание работы косвенного шитого кода

Я вообще-то о нативном говорил... :shuffle;
Хотя там вид ШК без разницы. Проверки они в любом коде проверки... ;)
А вообще-то это важный для меня теоретический результат! И стабильное данное для дальнейших построений! :)

_________________
With best wishes, in4.


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

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


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

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


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

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