Некоторое время назад я написал блог о нашем новом алгоритме: http://blog.athico.com/2013/11/rip-rete-time-to-get-phreaky.html
Кто-то спросил меня о новой системе на основе стека и о том, как работает обратное связывание. Я ответил на них по электронной почте, но я подумал, что другие могут найти это полезным, поэтому вставил его ниже. Это написано прямо из моего мозга на страницу, так что это немного сырые места .; но я надеюсь, что некоторые найдут это полезным, несмотря ни на что.
—
Когда правило оценивается, оно оценивается от корня до кончика.
Для каждого узла он оценивает все возможные соединения и создает набор кортежей. Этот набор дочерних кортежей затем передается дочернему узлу. Переданный набор кортежей называется srcTupleSet (для имени переменной), после чего все дочерние элементы помещаются в trgTupleSet. TrgTupleSet передается дочернему узлу, где он становится srcTupleSet.
Строка 245 показывает этот цикл: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/phreak/RuleNetworkEvaluator.java#L245
|
1
|
srcTuples = trgTuples; // previous target, is now the source |
Когда узел вводится, он имеет ряд переменных, которые необходимы для оценки узла. Идентификатор узла, память узла, память сегмента, srcTupleSet trgTupleSet. Любой узел можно приостановить и возобновить (выполнить оценку позднее), создав StackEntry, который ссылается на эти значения. StackEntry помещается в стек. Вот класс StackEntry: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/phreak/StackEntry.java
Это необходимо по двум причинам: обратное связывание и подсети. Обратная цепочка выполняется через узел запроса.
Когда распространение достигает узла запроса, ему необходимо приостановить оценку текущего правила — поэтому он создает StackEntry и помещает его в стек.
Запрос — это просто правило без RHS, без последствий. Он собирает все результаты, которые достигают терминального узла, и возвращает их вызывающей стороне. Узел запроса позволяет правилу вызывать запрос, передавая аргументы. Вызов запроса выполняется путем вставки объекта DroolsQuery, который соответствует корневому шаблону и запускает распространение:
см. строку 67: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/phreak/PhreakQueryNode.java
|
1
|
LeftInputAdapterNode.doInsertObject(handle, pCtx, lian, wm, lm, false, dquery.isOpen()); |
Как и пролог, аргументы могут быть связаны или не связаны. Связанный аргумент — это переменная, а несвязанный аргумент — это переменная. В случае реализации мы не применяем ограничения к несвязанным аргументам. Это позволяет выполнять классический тип запроса «транзитивное замыкание». И хотя правило может вызывать запрос, запрос также может вызывать запрос (у нас нет табуляции для обнаружения бесконечных циклов).
|
1
2
3
4
5
|
query isContainedIn( String x, String y ) Location( x, y; ) or ( Location( z, y; ) and isContainedIn( x, z; ) )end |
Примечание drools поддерживает позиционные и щелевые аргументы в шаблонах. Это делается путем сопоставления всех позиций в слоте.
Пошаговое руководство, показывающее вышеуказанный запрос в действии, для реактивных и нереактивных транзитивных замыканий, можно найти здесь: https://www.youtube.com/watch?v=fCjIRVSRFvA
Для оценочного запроса, когда trgTulupleSet достигает терминального узла, он выполняет итерацию и добавляет каждый кортеж в «сборщик».
см. строку 65: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/phreak/PhreakQueryTerminalNode.java#L65
Сборщик создает специальный дочерний кортеж, который можно добавить в вызывающего родителя.
см. строку 343: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/reteoo/QueryElementNode.java#L343
Как только запрос закончил оценку, он возвращается. Затем процесс перенастройки позволяет выполнению посетить стек, где он выталкивает StackEntry и возобновляет оценку — но теперь результаты запроса доступны.
см. строки 166 и 173: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/phreak/RuleNetworkEvaluator.java
Запрос может быть вызван реактивно и нереактивно. Неактивно означает, что не осталось левой памяти, а запрос не оставлен открытым. Реактивно означает, что осталась память, а запрос оставлен открытым. Реактивный запрос является полностью инкрементным и поддерживает обновления и удаления:
см. строки 143 и 169: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/phreak/PhreakQueryNode.java#L143
Структуры данных, которые мы используем для кортежей и «вложенных» (результат запроса), эффективны и «свободны от копирования» и «свободны от поиска» — все это списки с двойными связями. Это было необходимо для повышения эффективности дополнительных запросов.
Подсети используют аналогичную технику. В момент достижения подсети внешнее правило приостанавливается (помещается в стек) и создается оценка внутренней сети.
см. строки 593 и 604: https://github.com/droolsjbpm/drools/blob/master/drools-core/src/main/java/org/drools/core/phreak/RuleNetworkEvaluator.java
Как только подсеть закончена, внешнее правило возобновляет и помещает результаты в правый вход внешнего дочернего узла:
Как уже упоминалось ранее, мы предоставляем ленивую оценку правил, но не добавочную оценку правил. Как только начинается оценка правила, создаются все кортежи. Однако, поскольку запись в стеке может быть приостановлена и возобновлена на любом узле, она также может быть использована для обеспечения инкрементальной оценки правил — хотя мы сейчас этого не делаем. По сути, вы «берете» X количество объектов на правом входе — это может быть 1, или 5, или 25, или 100. Это число позволяет вам настроить задержку по сравнению с пропускной способностью. После получения, если все еще не оценены правильные входные данные, вы создаете StackEntry, который вызывает переоценку этого узла после завершения текущего распространения.