TechNeilogy

Looking at the tiny expert system in the previous post reveals some obvious problems. Perhaps worst among them, the system will continue to ask for values even when it is obvious that a conjunction will fail. Most of these problems could be solved by the clever use of intermediate hypotheses and by paying careful attention to the ordering of the hypotheses. However, there’s a better way: construct a tiny inference engine.

Before I show that, let me say some things about what this is not and what it is. First, this is not necessarily the best way to build an inference engine; it is not even necessarily the best way to build a toy inference engine. Second, it is not a compendium of F# design patterns or best practices. Third, it is not thoroughly checked for quality or errors, it is a bit of weekend fun – use it at your own risk. Here’s what it is: it was a fun exercise in learning some things about F#. In particular, it shows how F# can easily be used as a framework for constructing domain and application-specific languages.

The tiny inference engine is made up of three things:

Consider and ConsiderImmediate – functions which define and instantiate hyptheses. Note that these are functionally very simple; most of the code in them is for readability and reporting.

ConjoinPossible, ConjoinEval, and Conjoin – functions which combine hypotheses conjunctively (i.e. using “and”). The first two functions are helpers. ConjoinPossible determines whether a conjunction is still possible given the current state of the evidence. ConjoinEval performs an actual conjunction. Conjoin groups the previous functions into a neat package.

DisjoinPossible, DisjoinEval, and Disjoin – equivalents of the conjunctive functions which combine hypotheses disjunctively (i.e. using “or”).

There is also a small sample set of rules which reason about the color of a thing. Rather than query the user, I hard-coded the values for the root hypotheses. This simplifies testing. Also, please note that the code is specially formatted to fit the narrow blog window.

// Note: formatted for blog width.

// Lazy evaluation of an hypothesis.
// Everything except the return
// is just for information.
let Consider s (b:Lazy<bool>) = lazy ( 
  printf "Considering: "
  printfn s
  match b.Value with 
    | false -> printf "Rejecting: "
    | true -> printf "Accepting: "
  printfn s
  b.Value)

// Immediate evaluation of an hypothesis.
// Everything except the return
// is just for information.
let ConsiderImmediate s (b:Lazy<bool>) =
  printf "Considering: "
  printfn s
  match b.Value with 
    | false -> printf "Rejecting: "
    | true -> printf "Accepting: "
  printfn s
  b

// This set of functions handles conjunction.

// True on all true or unknown.
let rec ConjoinPossible (l:Lazy<bool> list) =
  match l with
    | [] -> true
    | h::t -> 
        if (h.IsValueCreated) 
          then (h.Value && ConjoinPossible(t)) 
          else ConjoinPossible(t)

// Conjoin with short-circuit on false.
let rec ConjoinEval (l:Lazy<bool> list) =
  match l with
    | [] -> true
    | h::t -> h.Value && ConjoinEval(t)

// Conjoin if possible.
let rec Conjoin (l:Lazy<bool> list) = lazy (
  ConjoinPossible(l) &&
  ConjoinEval(l))

// This set of functions handles disjunction.

// True on at least one true or unknown.
let rec DisjoinPossible (l:Lazy<bool> list) =
  match l with
    | [] -> false
    | h::t -> 
        if (h.IsValueCreated) 
          then (h.Value || DisjoinPossible(t)) 
          else true

// Disjoin with short-circuit on true.
let rec DisjoinEval (l:Lazy<bool> list) =
  match l with
    | [] -> false
    | h::t -> h.Value || DisjoinEval(t)

// Disjoin if possible.
let rec Disjoin (l:Lazy<bool> list) = lazy (
  DisjoinPossible(l) &&
  DisjoinEval(l))

// Here are some test hypotheses.

// This first block contains hard coded values.
// In real life, these would be input data.
// They are hard-coded here to simplify testing.

let black = 
  Consider "black" (lazy true) 

let blue = 
  ConsiderImmediate "blue" (lazy true)

let orange = 
  Consider "orange" (lazy false)

let white =  
  Consider "white" (lazy true)

// This second block is the logic.

let blackAndOrange = 
  Consider 
    "blackAndOrange" 
    (Conjoin [ 
      black; 
      orange ])

let blackAndOrangeOrBlue = 
  Consider 
    "blackAndOrangeOrBlue" 
    (Disjoin [ 
      blackAndOrange; 
      blue ]) 

let whiteAndBlack =   
  Consider 
    "whiteAndBlack" 
    (Conjoin [ 
      white; 
      black ]) 

let color =  
  ConsiderImmediate 
    "color" 
    (Disjoin [ 
      blackAndOrange; 
      blackAndOrangeOrBlue; 
      whiteAndBlack ]) 
      
// Run the system.

open System

Console.ReadLine() |> ignore

So what’s next? I’m not sure. For one thing, I’d like to add certainty factors. This may entail a more complex record type. In the interests of exercise particular F# features, I will likely base this on records or discriminated unions rather than classes. Stay tuned.