Сделал конкретный примерчик схем и таблиц, как обобщение изложенного здесь и в теме про "Схемы в описании программ".
В
посте выше была представлена схематическая таблица, на счёт "агрегатного" алгоритма. Раскроем суть подробнее.
Пусть имеются два типа данных: Magic и Melee, обобщённые под общим типом Attack (реализованных по средствам классов, trait-ов и т.п., не важно как именно). Для каждого типа определена функция "power" (в данном случае реализации ф-ций просты, возвращают константы). А также заданы и соответствующие функции "damage" в двух вариантах (здесь уже чуть сложнее вычисления). Ставится задача показать обобщённый алгоритм ф-ции "damage" как одновременное отражение всех вариантов вычислений, определенных в системе.
Ниже рисунок, где определены:
- Р-схемы, выражающие типы и все функции, включая и агрегатную модель ф-ции "damage" (на схеме она указана без префикса типа и содержит уже три параметра, где первый аргумент ссылается на тип/класс);
- реализация ф-ции "damage" в виде:
* алгоритмической таблицы
* схематической таблицы в стиле Р-схем
* исходный схематической таблицы (для сопоставления).
Примечание. Не рассматривается оптимальность алгоритмов (более подробные обобщения и пр.), также есть и алгоритмические огрехи, например, встречается анализ результата вычислений, где включаются "<= 0 и >= 1", но не ясно, чего делать между 0 и 1. В общем, всё подогнано под уже имеющийся рисунок исходной схематической таблицы (также нет дополнительных подписей, но, вроде, и так понятно, что где):
Вложение:
agr_schems.PNG [ 145.08 КБ | Просмотров: 15709 ]
С Р-схемами всё должно быть ясно. Алгоритмическая таблица содержит:
* в верхней части - входные аргументы функции;
* середина - собраны все условия из "тела" ф-ции;
* ниже - содержательное тело алгоритма
* завершает таблицу - выходные результаты
Принципиальное её свойство - сборник "правил" алгоритма (по столбцам): соотношение "условия" -> "действия". При этом задействован "goto" - для перехода на смежные таблицы, для циклов и для нарезки алгоритма на блоки в контексте "правил", чтобы отражать всю его семантику. В примере выделены явно столбцы "assert" и "variant", что необязательно.
Схематическая таблица в стиле Р-схем - это повёрнутая на бок исходная таблица, где измерения поменялись местами: по горизонтали - действия, по вертикали - предикаты. В остальном - всё тоже: слева аргументы ф-ции, далее по конвейеру - тело функции, и завершает "out" - результат.
И, естественно, все таблицы (как и схемы) подходят для всех алгоритмов, не обязательно "обобщённых". Это лишь ещё один пример, в очередной раз намекающий о соседстве декомпозиции и агрегатных моделей (всё в одном флаконе).
Конечно, схемы и таблицы оформлены отвратительно из-за отсутствия инструментария. Даже "древние рукописи" и то более наглядны, компактны, удобны:
Вложение:
r_tbl.PNG [ 34.7 КБ | Просмотров: 15709 ]
На рисунке выше есть примечательные элементы:
- верхняя схемка (спецификация данных) и содержательная схема - очень похожи, и в то же время сразу отличаются в соответствие со своим типом;
- используются "комментарии", которые также можно втыкать и в таблицы;
- ниже пример записи таблицы (решения) через сами Р-схемы.
До кучи, ещё примерчики, лишний раз демонстрирующие, что Р-схемы применимы и для алгоритмов, и для процессов, и для данных, и т.д.:
Вложение:
r_data.PNG [ 79.12 КБ | Просмотров: 15709 ]
И ещё одно важное замечание. Во всех своих примерах автор исходных схематических таблиц нигде не акцентирует внимание на циклах, и думаю, не беспочвенно. В нашем же "Р-случае" на помощь приходят всё те же "скудные" Р-схемы. Рисунок выше напоминает, что в алгоритмах частенько используется "спецдуга" для циклов. Берём её, и в гармонии с алгоритмическими таблицами используем "goto"-принцип. А также, не пропадать же ведь и обратным дугам: раз они указывают на обратное направление, противоположное конвейеру, в сторону входных аргументов и дальше - до "вызывающих органов", значит и будем отражать через них соответствующие продвижение - "вылеты" из функции/процедуры. Конкретно - "assert"-ы и "ошибки" ("exception"-ы).
На счёт обработки ошибок. В примере ниже используется парадигма "conditions and restarts" ("условия и перезапуск"), популярные в "лиспах". Похожа на типовую модель вида "try-except/catch/finally", но с принципиальными отличиями: при обработке ошибок не выполняется раскрутка стека (с соответствующей потерей контекста), и принятие решения о применении предопределенной политики восстановления вычислений выносится наверх (выше уровни).
Модифицируем предыдущий пример. Пусть имеется некая ф-ция "set_damage", принимающая список объектов типа Attack, плюс и другие данные. Эта функция теперь устанавливает свойство "damage", имеющееся у объектов, по алгоритмам выше. Псевдокод:
Код:
type Attack = {damage: float}
type Magic = extend Attack {...}
type Melee = extend Attack {...}
error InvalidVal(float) = SetVal(float) | Ignore
set_damage: ([Attack]!, Bool, Int) => ! with InvalidVal
set_damage = (attacks!, surprise, defense) -> loop'(attacks)
where loop' = ([ ]) -> !
([attack!, ...atks]) ~>
case attack of
Magic => power = 5
Melee => power = 4
effectiveness = (power * 3) if surprise else (power * 2)
case attack of
Magic => set_magic(attack, effectiveness)
Melee => attack.damage = effectiveness / defense * 2
loop'(atks)
set_magic = (attack!, effectiveness) ->
damage = effectiveness - defense
case of
| damage <= 0 => attack.damage = 0
| damage >= 1 => attack.damage = damage
| _ =>
try fail(InvalidVal damage) handle
SetVal(x) => attack.damage = x
Ignore => _
do ->
attacks = [...]
try set_damage(attacks, true, 234.78) with
InvalidVal(x) => SetVal(x*0.66 - x)
Ф-ция "set_damage" принимает изменяемый (!) список объектов, не возвращает значения. В спецификации указано, что ф-ция "отправляет" сигнал об ошибке вида "InvalidVal". В реализации видно, что ошибка возникает как раз при неопределенности в анализе результатов. В примере вызова ф-ции указано, что необходимо применить политику "SetVal" (другая политика - для игнорирования значения, и соответствующий объект не обновляется). Само тело функции реализовано через цикл в виде рекурсивного вызова встроенной функции, причём строго "хвостовой".
Итак, также из таблицы удалим вертикальные линии, которые создают эффект "циклограммы" (имеющийся и в исходных таблицах), и остальной мусор, возьмём "Р-стандарт" (предикаты - вверху, действия - внизу), в общем, приведём всё к классическому аскетичному Р-виду:
Вложение:
set_damage.PNG [ 29.22 КБ | Просмотров: 15709 ]
Эта таблица не содержит последнего "out"-столбца. Переходы - спецдуги - м.б. осуществлены не только на начало ф-ции, и заданы в произвольном месте. В примере под обратной дугой - обработка сигнала ошибки. Также возможно указание условий (как предикат) для явных "assert"-ов - в этом случае не будет обработки под обратной дугой, и при срабатывании предиката - "вылет". В левом нижнем углу - дуга как спец-случай для аргумента функции, что означает прямой пролёт через конвейер - немедленный выход из процедуры.
Итого, целью этого сообщения было более детальное знакомство с принципами Р-схематичных таблиц, как самое мощное алгоритмическое (и не только) оружие массового поражения в рамках потенциального Р-стека. Таблицы, конечно, как и схемы, требуют адекватного форматирования. Им не чужды все те интерактивные (и не только) помогалки, которые можно наблюдать в демонстрациях к исходным схематическим таблицам. Р-таблица одновременно м.б. выражена и в виде алгоритмической таблицы, у которой есть и свои сложности, и достоинства: явное выделение "правил" алгоритма, плюс она однородна с другими таблицами решений и их модификациями (и, в целом, с таблицами). Ну и сами Р-помощники-схемы тоже не лишние.
А также этот пост связан и с иными темами ("Схемы в описании программ", "задача на перспективу...", и др.). Через схемы и таблицы -- данные, процессы, алгоритмы (в т.ч. и управляющие или координирующие), "ошибки" и "assert"-ы выше -- координации в оргдеятельности, действующие лица - через аргументы функций или иные переменные и т.д. (не забываем, что даже конструктор данных - та же функция).
В общем, всё однородно, полиморфно, декомпозиция и агрегатные модели, "немногое о многом"...