Крошечный язык для инструкций к выключателям

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

Давайте посмотрим на выключатели со схем 1-7. Понятно, что выключатель №1 должен быть подключён по двум контактам (1 и 2), иначе это ошибка. А вот выключатель на схеме 2 (напомню, что штриховая вертикальная линия — это механическая кнопка, замыкающая сразу несколько контактов) должен быть подключён хотя бы по одной из пар 1-2 и 2-4. То есть, можно представить себе ситуацию, когда у нас нет в наличии простых выключателей со схемой 1, но есть ящик выключателей №2. Тогда получается, что мы должны подключать не все контакты, а только часть.

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

SWITCH 1
CHANNEL 1
CHANNEL 2
CHANNEL 3
CHANNEL 4

то обязательность подключения была бы просто битом. И мы могли бы описать всё так:

SWITCH 1
CHANNEL* 1
CHANNEL* 2
CHANNEL 3
CHANNEL 4

что означает — есть 4 контакта, причём первые два обязательно подключать. Но у нас более сложная ситуация — например, на схеме 2 контакт 3 обязательно подключать, если контакт 4 подключён. А вот если контакт 4 не подключён, то и не надо беспокоиться о контакте 3.

Понятно, что в общем случае, у обязательность подключения — это какие-то бинарные функции от уже подключённых контактов:

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

И вот, кмк, разумным приближением является приближение «идеального выключателя» — провода там не взаимодействуют через электрические поля, токи разумные, напряжения тоже, сопротивления проводов принебрежимо малы, нагрева, соответственно, нет. В общем, выключатель в каждом из положений описывается обычным ненаправленным графом. Вершинами этого графа являются соединения проводов (помеченные точками на рисунке).

Разумеется, для каждого типа выключателей таких графов несколько — в зависимости от положения кнопок. Но мы можем «совместить» все эти графы на одном. Это аналогично рассмотрению всех путей в CFG (control flow graph) одновременно, как в dataflow анализе (если бы мы моделировали эти выключатели, скажем, на языке Pascal простейшим образом, у нас бы так и вышло). Картинка становится вот такой:

мы видим, что у нас каждый из этих «совмещённых» электрических графов представляет собой несколько связанных компонент.
И довольно разумно потребовать:

1. Чтобы была подключена хотя бы одна компонента.

2. У каждой из компонент было подключено хотя бы 2 контакта.

Однако, мы сразу же видимо по схеме № 6, что второе требование не очень хорошо — ведь мы можем подключить контакты №2 и №3.

Таким образом, мы видим, что нам нужно различать «входы» и «выходы» у выключателя. То есть, на приведённых схемах левые (входы) и правые (выходы) контакты — это разные типы контактов. Вроде бы это довольно хорошо соотносится с практикой.

Окончательно, совершенно минимальные требования:

1. Чтобы была подключена хотя бы одна компонента.

2. У каждой из компонент было подключено хотя бы 2 контакта, один из которых вход, а другой — выход.

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

Начнём с требования 2 — тут можно написать ограничение в такой форме:

Есть набор входов Inputs, есть набор выходов Outputs.

Если какой-либо вход из Inputs подключён, то должен быть подключён хотя бы один выход из Outputs.

И наоборот, если какой-либо выход из Outputs подключён, то должен быть подключён и хотя бы один вход из Inputs.

«Для простоты» опишем это формулой AnyOf {Inputs} <==> AnyOf {Outputs}.

Теперь заметим, что для того, чтобы описать ограничение через контакты, мы можем потребовать соединение хотя бы одного из контактов, принадлижащих разным компонентам. Причём мы можем взять входы. Пусть это будет формула MustConnectAnyOf {Inputs}.

Соответственно, весь язык — это (фигурные скобки означают, что порядок не важен):

Constraints ::= {Constraints}
Constraint ::= AnyOf {Inputs} <==> AnyOf {Outputs}             
             | MustConnectAnyOf {Inputs}

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

Примеры инструкций:

Схема №1.

MustConnectAnyOf {1}
AnyOf {1} <==> AnyOf {2}

Схема №2.

MustConnectAnyOf {1 3}
AnyOf {1} <==> AnyOf {2}
AnyOf {3} <==> AnyOf {4}

Схема №3.

MustConnectAnyOf {1 3 5}
AnyOf {1} <==> AnyOf {2}
AnyOf {3} <==> AnyOf {4}
AnyOf {5} <==> AnyOf {6}

Схема №4.

MustConnectAnyOf {1 3 5 7}
AnyOf {1} <==> AnyOf {2}
AnyOf {3} <==> AnyOf {4}
AnyOf {5} <==> AnyOf {6}
AnyOf {7} <==> AnyOf {8}

Схема №5.
Тут появляется некоторая неоднозначность. В зависимости от того, хотим ли мы иметь полный переключатель,

MustConnectAnyOf {1}
AnyOf {1} <==> AnyOf {2}
AnyOf {1} <==> AnyOf {3}

или мы можем довольствоваться выключателем с 3 позициями и лишь одной рабочей.

MustConnectAnyOf {1}
AnyOf {1} <==> AnyOf {2 3}

Схема №O5.

MustConnectAnyOf {1}
AnyOf {1} <==> AnyOf {2 3 4}

Схема №6.
Опять неоднозначность. Если мы хотим только вариант полного поключения

MustConnectAnyOf {1}
AnyOf {1} <==> AnyOf {2}
AnyOf {1} <==> AnyOf {3}

а если мы хотим оставить возможность использования в качестве простого выключателя (схема №1).

MustConnectAnyOf {1}
AnyOf {1} <==> AnyOf {2 3}

Схема №6/2.
Тут тоже, в зависимости от того, что же мы считаем правильным. Если мы хотим полного использования всех возможностей выключателя:

MustConnectAnyOf {1}
MustConnectAnyOf {2}
AnyOf {1} <==> AnyOf {3}
AnyOf {1} <==> AnyOf {5}
AnyOf {2} <==> AnyOf {4}
AnyOf {2} <==> AnyOf {6}

Или мы допускаем редукцию до одинарной схемы 6:

MustConnectAnyOf {1 2}
AnyOf {1} <==> AnyOf {3}
AnyOf {1} <==> AnyOf {5}
AnyOf {2} <==> AnyOf {4}
AnyOf {2} <==> AnyOf {6}

Или, например, редукция до совершенно простой схемы 1:

MustConnectAnyOf {1 2}
AnyOf {1} <==> AnyOf {3 5}
AnyOf {2} <==> AnyOf {4 6}

Схема №7.

В самом редуцированном случае

MustConnectAnyOf {1 3}
AnyOf {1 3} <==> {2 4}

В самом полном:

MustConnectAnyOf {1}
MustConnectAnyOf {3}
AnyOf {1} <==> {2}
AnyOf {3} <==> {4}