Jess Information

Jess Home
Jess 7 Features
Download Now!
Online Demo

Mailing List
Jess Wiki

More information Related Web Sites
User Contributions
JSR94 Info
Developer's Log
About This Site

JESS ®, the Rule Engine for the JavaTM Platform

Jess Wiki: Ivy On Trees


Wolfgang Laun
Wolfgang Laun a-t thalesgroup com

Name: Ivy On Trees

Intent: Processing facts on a binary tree


This is, perhaps, more of a mental exercise than a design pattern. The essential prerequisite for this pattern to work is that you have facts arranged in a binary sorted tree. Then it's possible to create some "ivy" that clings to the root and sends up sprouts to the tree leaves, doing whatever needs to be done.


As it is presented her, it is restricted to the processing of binary trees. But similar approaches may be considered for more general graphs.


Basic ingredients are facts and lambda expressions. The "inline" definition of actions as lambda expressions requires a Jess command extension for calling a lambda expression. See AddingCommandsToJess.

Sample code:

Notice that this presents two kinds of processings: tree traversal and node insertion. They are essentially different, because a tree traversal ends only after visiting all nodes whereas node insertion ends when the right place has been found.


(load-function at.laune.jess.CallLambda)

;; a tree node
(deftemplate Node
    (slot value (type INTEGER))
    (slot left  (type INTEGER) (default nil))
    (slot right (type INTEGER) (default nil))

;; a sprout of Ivy
(deftemplate Ivy
    (slot current (type INTEGER) (default nil))  ; a node value
    (slot state   (type SYMBOL)  (default sBeg)) ; sBeg sLeft sMid sRight sEnd
    (slot parent  (type ANY)     (default nil))  ; the parent crawler
    (slot act     (type ANY)     (default nil))  ; processing argument
    (slot process (type ANY))                    ; processing function

;; The rule for detecting that a sprout of ivy is on a node and
;; ready to do something.
(defrule atBeg
    ?n <- (Node (value ?value)(left ?left)(right ?right))
    ?c <- (Ivy (current ?value)
               (state ?state & sBeg | sMid | sEnd)
               (process ?process)
               (parent ?parent))
    (lcall ?process ?n ?value ?left ?right ?c ?state ?parent)


;; Creates a sprout of Ivy on a child node.
(deffunction spawn (?c ?curr)
    (bind ?res (neq ?curr nil))
    (if (eq ?res TRUE) then
        (assert (Ivy (current ?curr)
                     (parent  ?c)
                     (act     (fact-slot-value ?c act))
                     (process (fact-slot-value ?c process)))))
    (return ?res))

;; The processing function for traversing a tree.
;; The distinction between pre-, post- and endorder is set by act
;; (but could be coded into the function).
(bind ?pfTraverse
  (lambda (?n ?value ?left ?right ?c ?state ?parent)
    (if (eq ?state sBeg) then
      (modify ?c (state (if (spawn ?c ?left) then sLeft else sMid)))
    (if (eq ?state sMid) then
      (modify ?c (state (if (spawn ?c ?right) then sRight else sEnd)))
    (if (eq ?state sEnd) then
      (if (neq ?parent nil) then
        (modify ?parent
        (state (if (eq (fact-slot-value ?parent state) sLeft) then sMid else sEnd)))
      (retract ?c)
    ;; The action.
    (if (eq ?state (fact-slot-value ?c act)) then
      (printout t "value=" ?value crlf)

;; The processing function for inserting a tree node.
;; The value to be inserted is set by act.
(bind ?pfInsert
  (lambda (?n ?value ?left ?right ?c ?state ?parent)
    (bind ?newval (fact-slot-value ?c act))
    (if (< ?newval ?value) then
      (if (not (spawn ?c ?left)) then
        (modify ?n (left ?newval))
        (assert (Node (value ?newval)))
    (if (> ?newval ?value) then
      (if (not (spawn ?c ?right)) then
        (modify ?n (right ?newval))
        (assert (Node (value ?newval)))
    (retract ?c)

;; The sorted binary tree:
;;                       5
;;                  1         7
;;                     3           10
;;                               9     12

(defglobal ?*root* = 5)

(assert (Node (value  1)(right 3)))
(assert (Node (value  3)))
(assert (Node (value  7)(right 10)))
(assert (Node (value  5)(left 1)(right 7)))  ; root
(assert (Node (value 10)(left 9)(right 12)))
(assert (Node (value  9)))
(assert (Node (value 12)))

;; Display the tree
;; (assert (Ivy (process ?pfTraverse)(current ?*root*)(act sBeg)))
   (assert (Ivy (process ?pfTraverse)(current ?*root*)(act sMid)))
;; (assert (Ivy (process ?pfTraverse)(current ?*root*)(act sEnd)))

;; Insert some new nodes
   (assert (Ivy (process ?pfInsert)(current ?*root*)(act 13)))
   (assert (Ivy (process ?pfInsert)(current ?*root*)(act 4)))

;; Display the tree
   (assert (Ivy (process ?pfTraverse)(current ?*root*)(act sMid)))

Front Page | Sandbox | Recent Changes | Powered by Friki | Last Edited: 27 June 2007