The Need for Code Reuse

At one of my contracting jobs, they had many clients running essentially the same program, but each client needed minor code modifications. Their objective was to maximize code reuse.

What is Code Reuse?

The first question is what does "code reuse" mean? And the answer that seems most logical is function reuse. Where code modifications are required, a new function can be created incorporating those modifications.

Then the remaining task is to bring the proper collection of functions together for each client.

This gets more complicated as several versions of many functions will be produced for various clients that are all available for reuse by the next client. So it's not simply the case that there will be one standard default version of each function, and then several one-off customized versions that each only apply to a single client.

The result of this function combination exercise is a function call graph.

Current Solution Limitations

These solutions are all limited for the same reason. Let's look at another example to see why.

Applying Backward-Chaining to Code Reuse

The next question is how do we use a backward-chaining system to produce function call graphs?

Let's examine, conceptually, what a set of backward-chaining rules would look like to find a solution to this problem. Then we can determine how to turn this into a function call graph.

The following diagram shows goals as dotted line boxes around the rules that prove that goal. In this example, some goals only have one rule and some have two.

We also see how rules link to other goals. For example, rule Use B1 and rule Use B2 both prove the same goal: Find B. But Use B1 links to the Find C goal, while Use B2 links to Find D.

Now we can follow how these rules would be run by the knowledge engine:

• The whole process is kicked off by asking the knowledge engine for a solution to Find A.
• There is only one rule for Find A: Use A1, so the knowledge engine tries this rule.
• Use A1 needs a solution to Find B.
• The knowledge engine tries the first rule for Find B: Use B1.
• Use B1 needs a solution to Find C.
• The knowledge engine tries the only rule for Find C: Use C1, which fails for client3!

The situation now looks like:

Continuing on:

• Since there are no other rules for Find C, the Find C goal fails.
• Which means that the Use B1 rule fails.
• So the knowledge engine tries the next rule for Find B: Use B2.
• Use B2 needs a solution for Find D.
• The knowledge engine tries the first rule for Find D: Use D1, which fails for client3.
• The knowledge engine tries the next rule for Find D: Use D2, which succeeds for client3!
• The Find D goal succeeds.
• The Find B goal succeeds.
• And the Find A goal succeeds.

When we achieve final success, we have the following situation:

What remains is to translate this into a function call graph.

It becomes obvious that we want to attach our python functions directly to the backward-chaining rules:

Pyke KRB Syntax

How does all of this look in Pyke?

Pyke has its own language for rules, which it compiles into python source modules and then imports. This gives a performance boost by circumventing nearly all of the inference engine interpretation logic. It also makes it very easy to embed short python code snippets directly within the rules to help out with the inferencing. This keeps the inference mechanism simpler as it does not have to deal with things that are already easy in a procedural language (like arithmetic and simple list manipulation).

The Pyke rule source files are called knowledge rule bases and have a .krb suffix.

We'll continue with the previous example here.

First, let's look at the rules before we attach the python functions. Here's three of the rules:

use_B2
    use find_B($client)
    when
        check_function($client, B, 2)
        find_D($client)

use_D1
    use find_D($client)
    when
        check_function($client, D, 1)

use_D2
    use find_D($client)
    when
        check_function($client, D, 2)

Note that Pyke uses a $ to indicate pattern variables (anonymous pattern variables start with $_).

The check_function goal checks to see what version of the indicated function should be used for this client. If this is the incorrect version, it fails. If there is no indication for this function, it succeeds to allow guessing.

Attaching Python Functions to Backward-Chaining Rules

Here are the last two rules with the python code added. The rules have the python function attached to them so that the function can be returned from the goal as an additional parameter. Because this parameter does not affect the inferencing process, it is a hidden parameter.

These examples just show one line of python code, but you may have as many lines as you want:

use_D1
    use find_D($client)
    when
        check_function($client, D, 1)
    with
        print "D1"

use_D2
    use find_D($client)
    when
        check_function($client, D, 2)
    with
        print "D2"

Pyke calls the function call graphs plans. This terms applies to both the final top-level call graph, as well as intermediate call graphs.

use_B2
    use find_B($client)
    when
        check_function($client, B, 2)
        find_D($client)
    with
        print "B2"

use_B2
    use find_B($client)
    when
        check_function($client, B, 2)
        find_D($client)
            $$()
    with
        print "B2"

use_B2
    use find_B($client)
    when
        check_function($client, B, 2)
        find_D($client) as $d
    with
        print "B2"
        $d()

Other Capabilities

• Pyke also supports forward-chaining rules:

  fc_rule_name
      foreach
          fact_base_name.fact_name(pattern...)
          ...
      assert
          fact_base_name.fact_name(pattern...)
          ...
  

  • Pyke runs all of the forward-chaining rules whose foreach clause succeeds prior to running any backward-chaining rules. Thus, forward-chaining rules can not call backward-chaining rules and vice versa. But backward-chaining rules can examine facts asserted by forward-chaining rules.

• There are different kinds of knowledge bases:

  • Fact Bases:
    • simply store facts.
  • Rule Bases:
    • store both forward-chaining and backward-chaining rules.
    • can use rule base inheritance to inherit, and build upon, the rules from another rule base.
      • But only single inheritance.
      • Thus each rule base has a unique root rule base.
      • All rule bases that share the same root form a rule base category.
    • allow selection of which rule base(s) to use through rule base activation.
      • But only one rule base per rule base category may be active at one time.
  • Extensibility. You can write your own knowledge bases. These might:
    • look up facts in a database
    • ask users questions
    • probe hardware/software settings

Code Reuse through Automatic Programming

The fundamental lesson learned was that this technique ends up being far more capable than what I had first imagined.

More than producing adaptable libraries capable of using B₁ or B₂ at some point in their call graphs, this approach leads to something more akin to the back-end of a compiler -- except that the compiler front-end does not target a textual language that needs to be written and parsed; but is rather a simple observer of already known facts:

Show me your schema, and I'll build your SQL statements.

Show me your HTML templates, and I'll build the code to populate them for you.

This seems to change the whole concept of code reuse; elevating it from the realm of static libraries, to the realm of dynamic automatic programming.