SCPH --- поиск минимального пути

Сообщение alk » 28 фев 2010, 21:12
Судя по всему, SCPH находится в очень начальной стадии проектирования. Т.к. есть очевидные проблемы с этим примером.

http://www.ostis.net/mediawiki/index.php?title=SCPH-программа_поиска_минимального_пути

Во-первых сразу тривиальные вещи:
1) Контур обозначающий цель должен быть переменным
2) На шаге 8 переменная _n судя по всему должна быть на другом конце ребра, и переменная _а --- инцидентная ему дуга из непросмотренных вершин.

Теперь менее очевидные вещи.

* семантика поисковых операций

На шаге 8 надо искать _все_ возможные значения _n. А также проводить в каждое из них дугу на шаге 10. Но на шаге 20 нам нужно _одно_ из возможных значений _n2. Так что типологию видов поиска еще явно надо прорабатывать. И насколько я помню из своих собственных изысканий, двумя очевидными из этого простого примера видами не обойтись. Похоже, что нужна нормальная поддержка циклов по результатам поиска. А раз так, то и железную параллелизацию надо рассматривать шире -- с учетом распараллеливания этих циклов. На это можно посмотреть и как на \"разветвления\" недетерминированного интерпретатора. Валерьян Петрович может рассказать вам про \"язык циклов\" (или как он там сейчас называется). Похоже, истина где-то там. На менее тривиальных алгоритмах это должно быть заметней.

* метапеременные

Казалось бы при чем здесь они ? А дело в том, что на первом шаге нам надо искать константные дуги везде, _кроме_ дуги из сформированной структуры в _Gj. Эта дуга, если я правильно понимаю семантику ключевых узлов, должна быть переменной.

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

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

В принципе, можно распостранить этот подход и на переменные, и тогда вообще убрать их как тип элемента из SC. Переменные дуги в шаблонах придется кодировать ориентированными парами. На уровне SCg и SCs можно не терять выразительную мощь если добавить простое правило для чтения контуров --- все что с \"константым\" именем -- константа, все остальное -- переменная. Т.к константы без имени не имеют смысла в шаблонах, да и вообще, переменных в шаблонах большинство. Кстати, этот вариант по-моему, самый красивый и практичный. А потеря эффективности из-за кодирования переменных парами, похоже, совсем некритична.

Надеюсь, понятно изложил.

alk


Сообщение LazurkinDA » 01 мар 2010, 17:56
alk писал(а):

    1) Контур обозначающий цель должен быть переменным


Это не ошибка, просто редактор пока не поддерживает переменные контура. Пока это некоторая уступка.

alk писал(а):

    2) На шаге 8 переменная _n судя по всему должна быть на другом конце ребра, и переменная _а --- инцидентная ему дуга из непросмотренных вершин.


Спасибо, исправили.

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

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

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


Про "язык циклов" я не слышал и поэтому обязательно покапаю на мозги Валерьяну Петровичу B). Спасибо.

LazurkinDA


Сообщение Ivashenko » 05 мар 2010, 13:36
Кодирование переменных и метапеременных константами, в т.ч. дуг - узлами, недостаток семантической мощности, слабая типология операторов поиска в нынешней версии SCPH - это всё очевидные и давно высказанные вещи.
\"Мы выиграем в частном, но тогда проигрываем в более общем\" - и могли бы выигрывать в ещё более общем, о чём я уже говорил.

Ivashenko