Статьи

Хаммурапи — двигатель правил Скала

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

Что такое Хаммурапи

Hammurabi — это механизм правил, написанный на Scala, который пытается использовать возможности этого языка, делая его особенно подходящим для реализации чрезвычайно удобочитаемых внутренних языков, специфичных для предметной области. Действительно, что на самом деле отличает Хаммурапи от всех других механизмов правил, так это то, что можно писать и компилировать его правила непосредственно на языке хоста. В любом случае, правила Хаммурапи также имеют важное свойство быть читаемым даже не техническим персоналом. Как обычно, практический пример стоит более тысячи слов.
Проблема игроков в гольф

Эта логическая загадка была взята из первой главы книги «Джесс в действии», написанной Эрнестом Фридманом-Хиллом и изданной Мэннингом. Там это описано следующим образом:

  • Четверка игроков в гольф стоит у тройника, по линии слева направо.
  • Каждый игрок в гольф носит брюки разного цвета; один одет в красные штаны.
  • Игрок в гольф справа от Фреда носит синие штаны.
  • Джо второй в очереди.
  • Боб одет в клетчатые штаны.
  • Том не в положении один или четыре, и он не носит отвратительные оранжевые штаны.
  • В каком порядке будут играть четыре игрока в гольф, и какого цвета штаны каждого игрока в гольф? »

Решение Джесс

Jess написан на Java и является одним из самых популярных движков правил на рынке. Решение проблем игроков в гольф, представленных в упомянутой выше книге, заключается в следующем: сначала необходимо определить структуры данных, представляющие проблему.

(deftemplate pants-color (slot of) (slot is))
(deftemplate position (slot of) (slot is))

Deftemplate немного похож на объявление класса в Java и в этом случае используется для написания первого правила, которое, в свою очередь, создает факты, представляющие каждую из возможных комбинаций игроков в гольф, цвета штанов и позиций:

(defrule generate-possibilities =>
(foreach ?name (create$ Fred Joe Bob Tom)
(foreach ?color (create$ red blue plaid orange)
(assert (pants-color (of ?name)(is ?color)))
)
(foreach ?position (create$ 1 2 3 4)
(assert (position (of ?name)(is ?position)))
)
)
)

После этого можно перевести предложения задачи в соответствующее правило Джесса:

(defrule find-solution
;; There is a golfer named Fred, whose position is ?p1
;; and pants color is ?c1
(position (of Fred) (is ?p1))
(pants-color (of Fred) (is ?c1))

;; The golfer to immediate right of Fred
;; is wearing blue pants.
(position (of ?n&~Fred)(is ?p&:(eq ?p (+ ?p1 1))))
(pants-color (of ?n&~Fred)(is blue&~?c1))

;; Joe is in position #2
(position (of Joe) (is ?p2&2&~?p1))
(pants-color (of Joe) (is ?c2&~?c1))

;; Bob is wearing the plaid pants
(position (of Bob)(is ?p3&~?p1&~?p&~?p2))
(pants-color (of Bob&~?n)(is plaid&?c3&~?c1&~?c2))

;; Tom is not in position 1 or 4
;; and is not wearing orange
(position (of Tom&~?n)(is ?p4&~1&~4&~?p1&~?p2&~?p3))
(pants-color (of Tom)(is ?c4&~orange&~blue&~?c1&~?c2&~?c3))

=>
(printout t Fred " " ?p1 " " ?c1 crlf)
(printout t Joe " " ?p2 " " ?c2 crlf)
(printout t Bob " " ?p3 " " ?c3 crlf)
(printout t Tom " " ?p4 " " ?c4 crlf)
)

где строки начинаются с ;; это просто комментарии. Таким образом, если вы введете код проблемы в Jess, а затем запустите его, вы получите ответ напрямую:

Fred 1 orange
Joe 2 blue
Bob 4 plaid
Tom 3 red

Обратите внимание, что факты, что игроки в гольф находятся в разных положениях и носят брюки разных цветов, не выражены в явном правиле, но должны быть распространены и повторены во многих утверждениях. Очевидно, что это решение трудно поддерживать, и оно плохо масштабируется, что подчеркивается последним условным оператором, утверждающим, что позиция? P4 Тома — это? P4 & ~ 1 & ~ 4 & ~? P1 & ~? P2 & ~? P3, где ~ означает не в язык Джесс. Другими словами, это говорит о том, что позиция Тома не только отличается от позиции 1 и 4, но также отличается от позиций всех других игроков в гольф (названных один за другим), определенных ранее. На самом деле необходимость описать положение игрока в гольф также как отрицание позиций всех других игроков в гольф подразумевает нечто еще худшее:невозможно перевести каждое предложение задачи в другое правило, но их необходимо объединить в одно большое правило. После этой огромной части if ее секция then (одна после символа =>) распечатывает таблицу, содержащую набор переменных? P1 …? P4 и? C1 …? C4, которые решают проблему.

Раствор Хаммурапи

Как и во время представления решения Jess, также с Хаммурапи первое, что нужно сделать, это определить область проблемы. Чтобы сделать это, поскольку правила Хаммурапи являются действительными операторами Scala, достаточно создать простой класс Scala Person, имеющий в качестве атрибутов имя, положение и цвет брюк гольфиста, которые он представляет:

class Person(n: String) {
val name = n
var pos: Int = _
var color: String = _
}

Затем мы можем смоделировать тот факт, что все игроки в гольф должны иметь разную позицию и цвет штанов, поместив их в 2 разных набора:

var availablePos = (1 to 4).toSet
var availableColors = Set("blue", "plaid", "red", "orange")

и напишите два небольших метода, которые извлекают их из соответствующего набора, как только они назначены определенному игроку в гольф:

val assign = new {
def color(color: String) = new {
def to(person: Person) = {
person.color = color
availableColors = availableColors - color
}
}

def position(pos: Int) = new {
def to(person: Person) = {
person.pos = pos
availablePos = availablePos - pos
}
}
}

Эти методы написаны довольно странным образом, чтобы сделать еще более читабельным DSL, который будет использоваться для определения правил, и подчеркнуть идею о том, что можно написать правила в допустимом Scala, который может быть легко понят человек Конечно, легко пойти еще дальше, заключив другие понятия в некоторые удобные методы, как это было сделано выше. Теперь все готово для написания набора правил, описывающих проблему игроков в гольф:

val ruleSet = Set(
rule ("Unique positions") let {
val p = any(kindOf[Person])
when {
(availablePos.size equals 1) and (p.pos equals 0)
} then {
assign position availablePos.head to p
}
},

rule ("Unique colors") let {
val p = any(kindOf[Person])
when {
(availableColors.size equals 1) and (p.color == null)
} then {
assign color availableColors.head to p
}
},

rule ("Joe is in position 2") let {
val p = any(kindOf[Person])
when {
p.name equals "Joe"
} then {
assign position 2 to p
}
},

rule ("Person to Fred’s immediate right is wearing blue pants") let {
val p1 = any(kindOf[Person])
val p2 = any(kindOf[Person])
when {
(p1.name equals "Fred") and (p2.pos equals p1.pos + 1)
} then {
assign color "blue" to p2
}
},

rule ("Fred isn't in position 4") let {
val possibleFredPos = availablePos - 4
val p = any(kindOf[Person])
when {
(p.name equals "Fred") and (possibleFredPos.size == 1)
} then {
assign position possibleFredPos.head to p
}
},

rule ("Tom isn't in position 1 or 4") let {
val possibleTomPos = availablePos - 1 - 4
val p = any(kindOf[Person])
when {
(p.name equals "Tom") and (possibleTomPos.size equals 1)
} then {
assign position possibleTomPos.head to p
}
},

rule ("Bob is wearing plaid pants") let {
val p = any(kindOf[Person])
when {
p.name equals "Bob"
} then {
assign color "plaid" to p
}
},

rule ("Tom isn't wearing orange pants") let {
val possibleTomColors = availableColors - "orange"
val p = any(kindOf[Person])
when {
(p.name equals "Tom") and (possibleTomColors.size equals 1)
} then {
assign color possibleTomColors.head to p
}
}
)

Здесь первые 2 правила явно используют уникальность позиций и цветов брюк, присваивая последние доступные из них единственному человеку, у которого его еще нет. Другие правила просто соответствуют одно за другим предложениям задачи, как она была определена. Теперь можно заставить Хаммурапи решить проблему, создав четырех игроков в гольф:

val tom = new Person("Tom")
val joe = new Person("Joe")
val fred = new Person("Fred")
val bob = new Person("Bob")

добавьте их в рабочую память (набор объектов, по которым механизм правил будет оценивать и запускать правила):

val workingMemory = WorkingMemory(tom, joe, fred, bob)

и позволить механизму правил, инициализированному ранее определенным набором правил, работать над ним:

RuleEngine(ruleSet) execOn workingMemory

Работа с неизменяемыми структурами данных

Неизменность — это, вероятно, не то, что должно быть применено любой ценой в Хаммурапи по очень простой причине: большая часть времени выполнения тратится Хаммурапи, как и все другие механизмы правил, на поиск правил, которые на самом деле могут быть выполнены (запущены) т. е. те, для которых выполняется условие когда. На этом этапе данные только читаются и никогда не записываются, поэтому неизменность вообще не имеет значения, и все правила, которые могут быть применены, включаются в повестку дня. На последующем этапе правила в повестке дня ДОЛЖНЫ выполняться по одному, поскольку выполнение одного из них может привести к ложному выполнению условия другого. Это означает, что отсутствие неизменности не должно препятствовать безопасной работе механизма правил во время фазы обнаружения. Это сказало,также возможно получить тот же результат, работая с неизменяемыми структурами данных. Например, имея неизменного человека:

case class Person(name: String, pos: Int = 0, color: String = null)

достаточно переписать методы, которые назначают позицию и цвет штанов для игроков в гольф следующим образом:

val assign = new {
  def color(color: String) = new {
    def to(person: Person) = {
      remove(person)
      produce(person.copy(color = color))
      availableColors = availableColors - color
    }
  }

  def position(pos: Int) = new {
    def to(person: Person) = {
      remove(person)
      produce(person.copy(pos = pos))
      availablePos = availablePos - pos
    }
  }
}

оставив все правила без изменений. Таким образом, старая версия Person удаляется из рабочей памяти, а новая, с позицией или цветом, установленным в соответствии с правилом срабатывания, создается и затем добавляется в саму рабочую память. Методы удаления и создания действительно могут использоваться соответственно для удаления объектов из рабочей памяти и создания новых объектов, которые затем могут использоваться для оценки и запуска других правил.

Хаммурапи внутренности

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

Все правила выполняются в произвольном порядке, если для некоторых из них не указан другой приоритет. Действительно, поскольку иногда может возникнуть необходимость рассматривать некоторые правила как особые случаи, у них есть необязательное свойство, называемое значимостью, которое действует как параметр приоритета для этого правила, чтобы активированные правила с наивысшей значимостью всегда срабатывали первыми, а затем следуют правила низкая значимость. По умолчанию все правила имеют значение 0, но вы можете изменить его в определении правила следующим образом:

rule ("Important rule") withSalience 10 let { ... }
rule ("Negligible rule") withSalience -5 let { ... }

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

Дальнейшие реализации и улучшения

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

val p = any(kindOf[Person])

Другие механизмы для классификации и выбора этих объектов более точным способом находятся на стадии оценки, даже если уже возможно ограничить их с помощью булевой функции, как в следующем примере:

val p = kindOf[Person] having (_.name == "Joe")

Это полезно также с точки зрения производительности, поскольку значительно снижает количество комбинаций, которые механизм проверки правил должен проверить перед тем, как найти правило, которое можно запустить. Например, правило «Человек справа от Фреда носит синие штаны» может быть переписано следующим образом: число комбинаций, которое нужно попробовать, должно быть увеличено с 16 до 4:

rule ("Person to Fred’s immediate right is wearing blue pants") let {
  val p1 = kindOf[Person] having (_.name == "Fred")
  val p2 = any(kindOf[Person])
  when {
   p2.pos equals p1.pos + 1
  } then {
    assign color "blue" to p2
  }
}

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

Версия 0.1 механизма правил Hammurabi была только что выпущена и доступна здесь .