Goal driven declarative programming

This page is about the goal driven declarative programming from ShapeLogic 0.2 to 0.8. It is not currently under development, but might be suited for handling reasoning under uncertainty, so the code is left in. The Java package for this is org.shapelogic.logic.

Declarative programming in ShapeLogic 02. to 0.8

  • Goal driven task
  • Artificial Intelligence choice tree integrated with tasks classes
  • Some use of lazy computations
  • Rules were defined using JEXL
  • Rules where mainly defined in Java classes
  • Rules could be saved in a database, but this was not integrated with ImageJ

This was fine for handling simple rules applied to one polygon.

Ideas behind declarative goal driven logic engine

This is the first approach for declarative programming, used until ShapeLogic 0.8.

Influences for goal driven logic engine

  • Prolog language
  • AI choice tree
  • Oz language

Important ideas

  • Tree of task and sub tasks
  • Hierarchical contexts that is binding objects to name
  • Object hypothesis called OH in the code. OH = any match result

Hierarchical contexts

E.g. the context makes it possible to have the string "Letter" bound to both "A" and "B" at the same time in difference context. When matching a letter it will have a context for A and one for B, eventually one will be chosen, and the other discarded. The context is set up a hierarchically, like in most programming languages, so that names bound in a higher context can be seen in a lower one. So the string polygon is set at the root context level and can be seen by all the other context.

This relies on Java Expression Language (JEXL)

Tree of tasks

ShapeLogic is driven by a tree of task, the super class is called BaseTask.

A task can have sub tasks, but also have a context that inherits from the context of the parent task. Not all tasks have their own context.

Example of task hierarchy in letter matching

For examples of simple rules and task hierarchy look in the classes

  • LetterTaskFactory
  • LetterTaskTest

At the top level of the tree there is an Exclusive or task, XOrTask. Underneath is an AndTask for each letter. For each AndTask there are several simple property rules, of type ParametricRuleTask

Each AndTask has its own context that values can be set in, but all the SimpleTasks under an AndTask share a context. When a letter is finally chosen then the context from the chosen context is propagated up.

Example of logic rules in letter matching

The vectorizer will put a MultiLinePolygon object into the string "polygon" in a JEXL context.

Then there are rules that go in and look at the object using reflection. Here is an example of a simple NumericRule:

NumericRule("A", "pointCount", "polygon.getPoints().size()", 5.),

Here is an example of all the rules for a letter:

NumericRule[] numericRulesForA = {
    new NumericRule("A", POINT_COUNT, POINT_COUNT_EX, 5.),
    new NumericRule("A", LINE_COUNT, LINE_COUNT_EX, 5.),
    new NumericRule("A", HORIZONTAL_LINE_COUNT, HORIZONTAL_LINE_COUNT_EX, 1.),
    new NumericRule("A", VERTICAL_LINE_COUNT, VERTICAL_LINE_COUNT_EX, 0.),
    new NumericRule("A", END_POINT_COUNT, END_POINT_COUNT_EX, 2.),

where

POINT_COUNT = "pointCount";
POINT_COUNT_EX = "polygon.getPoints().size()"

All these rules are combined into an AndTask. A whole letter match will then be an XOrTask with an AndTask for each letter.

Influences for the declarative goal driven logic engine

Here is a little more of about the influence for declarative goal driven logic engine.

Prolog

Up till ShapeLogic v 0.9 goal driven tasks with subtasks was a corner stone in the logic for image processing. Starting in ShapeLogic v 1.0 this is getting replace by a lazy stream based approach that is simpler and more powerful.

Prolog history

Prolog was all the rage in the early 1980s, the Japanese 5 generation project was mainly based on Prolog. It turned out that it did not scale well to real world problems, partly because it was only good at handling symbolic information and not doing computations, and Prolog fell out of favor.

Despite this, I still think programming in Prolog is almost as simple as SQL.

ShapeLogic is trying to preserve this simplicity of Prolog, while maintaining ability to do efficient numerical calculations.

ShapeLogic is not using backtracking or unification, 2 of the main components in Prolog, but shares the idea of programming as goals and tasks with sub goals or horn clauses

AI choice tree

Unlike Prolog, ShapeLogic can have multiple values for a name at the same time, and can explore different choices at the same time.

Oz

Oz is an experimental language boasting:

  • Declarative programming
  • Functional programming
  • Object-oriented programming
  • Constraint programming
  • Fast concurrent programming

ShapeLogic merges contexts when faced with different options in a similar way to Oz, though this is not fully implemented yet.

Logic expressions in goal driven tasks approach

There are currently 3 main places where logic expressions can be placed:

  1. The rules are living in a Prolog like hierarchy of tasks and sub tasks
    1. And tasks
    2. Exclusive Or tasks
    3. Or tasks
    4. Not tasks
    5. Simple tasks
  2. The simple tasks

    Found named values are set in a JEXL context and expressions can be evaluated here too.

    1. Parametric Rule Tasks: Any expressions in evaluated to a value that are then compared to an expected value
    2. BooleanTask: Any expressions in evaluated to a boolean value
  3. Filter Tasks

    They are sub class of the Parametric Rule Tasks. They come in 2 flavors now:

    1. Filter that runs over all the points in the polygon
    2. Filter that runs over all the lines in the polygon

    You can also do logical combinations of the filter tasks:

    So if you have one class with a filter criteria that is filtering:

    • Points in the upper half of the bounding box of the polygon
    • Points that are T junctions

You can combine them with and and to get a filter that filters, T junctions in the upper half.

Example of logic language in the ShapeLogic letter matching example

This is how the rules for matching the letter A looks in ShapeLogic v 0.8

The rules for all the capital letters can be found in the class: LetterTaskFactory.java

So each line will be translated into one task / goal.

new NumericRule("A", POINT_COUNT, polygon, VAR_SIZE_START + POINT_COUNT_EX + VAR_SIZE_END,"==", 5.),
new NumericRule("A", HOLE_COUNT, polygon, VAR + HOLE_COUNT_EX, "==", 1.),
new NumericRule("A", T_JUNCTION_LEFT_POINT_COUNT, polygon, FILTER_START + T_JUNCTION_LEFT_POINT_COUNT_EX + FILTER_END,"==", 1.),
new NumericRule("A", T_JUNCTION_RIGHT_POINT_COUNT, polygon, filter(T_JUNCTION_RIGHT_POINT_COUNT_EX),"==", 1.),
new NumericRule("A", END_POINT_BOTTOM_POINT_COUNT, polygon, filter(END_POINT_BOTTOM_POINT_COUNT_EX), "==", 2.),
new NumericRule("A", HORIZONTAL_LINE_COUNT, polygon, size(HORIZONTAL_LINE_COUNT_EX), "==", 1.),
new NumericRule("A", VERTICAL_LINE_COUNT, polygon, size(VERTICAL_LINE_COUNT_EX), "==", 0.),
new NumericRule("A", END_POINT_COUNT, polygon, VAR + END_POINT_COUNT_EX, "==", 2.),
new NumericRule("A", SOFT_POINT_COUNT, polygon, size(SOFT_POINT_COUNT_ANN_EX), "==", 0.),

All rules work in a JEXL context.

How values are set in the JEXL context when running letter match

Steps when running letter match:

  1. The vectorizer, first finds a raw polygon
  2. Sets the raw polygon in the JEXL context of the root task under the name: "raw_polygon"
  3. Transforms the raw polygon into a cleaned up polygon
  4. Sets the cleaned up polygon in JEXL context of the root task under the name: "polygon"

Example of how a rule is evaluated

Hole count rule
new NumericRule("A", HOLE_COUNT, polygon, VAR + HOLE_COUNT_EX, "==", 1.),
Sequence of actions generated from hole count rule

This will be transformed into a task that:

  1. First the expression is: VAR + HOLE_COUNT_EX = "#.holeCount"
  2. Substituted the third argument, "polygon", for "#", to get expression: "ploygon.holeCount"
  3. Evaluated the resulting expression "ploygon.holeCount" in the JEXL context to a number
  4. Take the expected value, here 1
  5. Use the the given predicate to do a comparison. Here the predicate is: "=="
  6. If the predicate return true then the task succeeds, else it fails
  7. In order for the letter A to be matched all the rules need to succeed

Explanation of each field in the constructor for NumericRule

  1. The name of the OH, Object Hypothesis, they are all A.
  2. That is the name of the rule. This is not used for anything now and has no effect.
  3. Name of the variable in the task's JEXL context that you want the rule to work on.
  4. The is the expression that you want to evaluate the task's JEXL context.

    It is using # as a place holder for the name of the variable from last field.

  5. What relations that you want to check.
  6. The expected value.

The 4 main forms of access in a rule that is translated into a Parametric Rule Task

  1. Raw expressions. If you do not need a variable, then all you need is an expression.

    E.g. "ploygon.holeCount"

  2. VAR + HOLE_COUNT_EX,

    Takes the variable coming in from the third field and add that to the expression in HOLE_COUNT_EX.

  3. Size expressions: E.g. size(VERTICAL_LINE_COUNT_EX)

    Evaluate the expression that the string constant VERTICAL_LINE_COUNT_EX.

    This will return a collection of lines.

    Then does a size() call on that to see how many element there are in it.

  4. Filter expressions: E.g. filter(END_POINT_BOTTOM_POINT_COUNT_EX)

    When you need filter a collection with the criteria expression inside the filter.

    And then see how many elements the filter returns.

    So in this case you start with all the points in the polygon.

    The string: END_POINT_BOTTOM_POINT_COUNT_EX has the value:

    "PointOfTypeFilter(PointType.END_POINT) && PointBelowFilter(0.5)"

    This is a composite criteria that checks that the point is an end point and that it is in the lower half of the bounding box for the polygon.

    You can use the normal boolean operators in the filter expression: and, or, not.