Tiny Expert System using Monads

“I suppose it is tempting, if the only tool you have is a hammer, to treat everything as if it were a nail.”
– Abraham Maslow

“If your only problem is a nail, every tool tends to look like a hammer.”
– Rainer L. Price

I’ve been wanting to learn more about monads and their F# implementation as computation expressions. Inspired by the contagious enthusiasm in this video, last night I started reading chapter 12 in Real World Functional Programming by Tomas Petricek and Jon Skeet.

About halfway through, it occurred to me: “You could write a simple expert system using monads!” One of my stated goals for this blog is to use various “toy” A.I. and computer science problems to learn F#. I’ve strayed from that a bit, so this is a bit of a return.

Below is a tiny expert system implemented using computation expressions. I managed to find a way to use the following computation expression methods: Bind, Delay, and Return. I don’t claim that this is a good way to build an expert system; it’s cumbersome, lacks features like memoization, and probably isn’t even the best way to do it using computation expressions. But it was a nice baby step towards overcoming my unfamiliarity with monads.

(And, as always, presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

Here are the computation expression classes. There is one for conjunctions (and-type logic) and one for disjunctions (or-type) logic. The most important features of each are the ability to short circuit when a threshold (th) in the certainty is reached, and to delay computation. Conjunction short-circuits when certainty falls below the threshold, while Disjunction short-circuits when certainty exceeds the threshold. Coupled with Delay for lazy evaluation, this permits operation based on something more rational that exhaustive search. (For convenience, the classes also encapsulate the respective probability operators on the range 0-100 as static members.)

type Conjoin (th) =

  static member And a b =

    (a*b+49)/100

  member this.Bind(a,f) =

    if a<th 

      then a

      else f a

  member this.Delay f =

    fun () -> f()

  member this.Return v = v

type Disjoin (th) =

  static member Or a b =

    (10000-((100-a)*(100-b))+49)/100

  member this.Bind(a,f) =

    if a>th 

      then a

      else f a

  member this.Delay f =

    fun () -> f()

  member this.Return v = v

And here is a simple knowledge base. In case there is still any confusion about the characteristics of certain animals, I have again chosen that as my domain. The conclusions are reported by side effect.

let conjoin = Conjoin(20)

let disjoin = Disjoin(80)

let white = 80

let orange = 40

let black = 100

let striped = 35

let spotted = 100

let whiteAndBlack = 

  conjoin {

    let! x0 = white

    let! x1 = Conjoin.And x0 black

    return x1 }

let orangeAndBlack = 

  conjoin {

    let! x0 = orange

    let! x1 = Conjoin.And x0 black

    return x1 }

let tiger = 

  conjoin {

    let! x0 = orangeAndBlack()

    let! x1 = Conjoin.And x0 striped

    printfn "tiger %i" x1

    return x1 }

let zebra = 

  conjoin {

    let! x0 = whiteAndBlack()

    let! x1 = Conjoin.And x0 striped

    printfn "zebra %i" x1

    return x1 }

let leopard = 

  conjoin {

    let! x0 = orangeAndBlack()

    let! x1 = Conjoin.And x0 spotted

    printfn "leopard %i" x1

    return x1 }

let animal = 

  disjoin {

    let! x0 = tiger()

    let! x1 = Disjoin.Or x0 (zebra())

    let! x2 = Disjoin.Or x1 (leopard())

    return x2 }

animal() |> ignore

System.Console.ReadLine() |> ignore

When the code is run, the result is as follows.

zebra 28
leopard 40

It’s not exactly fifth-generation A.I., but it was a fun way to reinforce my reading about computation expressions. And it shows Rainer was right, if your only problem is a nail, even a monad can look like a hammer.

-Neil

p.s. I’m trying a new source-code formatter which preserves syntax highlighting. If you cut and paste the code into Visual Studio, you’ll see that the line breaks have been removed. This can usually be solved by an intermediate paste and cut into a text editor such as Word or WordPad.