March 2012

Volume 27 Number 03

The Working Programmer - Talk to Me, Part 2: ELIZA

By Ted Neward | March 2012

Ted NewardWhen we last met, we built a simple system for responding to voice inputs over the phone using Tropo, a cloud-hosted voice-and-SMS service. We got as far as being able to respond to voice inputs and offer responses, hopefully bailing you out of hot water with your significant other for spending too much time on the Xbox over the holidays. For some of you, unfortunately, that might not have carried the day, and things are still tense between you. This is when, as a compassionate human being, I’d like to be able to offer my services as an amateur therapist. Regrettably, however, I don’t scale very well and can’t talk to each and every one of you. So, instead, let’s examine an alternative. I speak, of course, of ELIZA.

ELIZA: A History

For those unfamiliar with ELIZA, “she” is a chatterbot—and one of the first and most recognizable steps toward artificial intelligence (AI). Written back in the ’60s by Joseph Weizenbaum, in Lisp, ELIZA is a relatively simple (by today’s standards) input-response processor that analyzes user input for “keys” and then generates human-like responses based on those keys. So, for example, if you said, “I am sad,” to ELIZA, she might respond, “Why are you sad?” or “Does talking to me make you sad?” or even “Stop being sad!” In fact, the responses could be so authentic at times that, for a while, it was thought this might be a way to get a program to pass the Turing test.

Four decades later, however, we’re still not having conversations with our computers the way Arthur C. Clarke imagined in “2001: A Space Odyssey,” but that doesn’t mean we should ignore “human-like” communication in our programs. We’re starting to see natural language processing (NLP) subtly slip more and more into computerized systems, and when combined with speech-to-text recognizer engines, entirely new avenues of human-computer interaction open up. For example, even a simple ELIZA-like key-recognizer system can be helpful in trying to create human-assistance systems on Web sites or in routing customers to the right department within a large corporation without requiring the highly frustrating, “Press 1 for Customer Service, press 2 for Human Resources, press 3 for …” call tree.

If you’ve never dabbled in even the simplest NLP, however, trying something like this can be a bit daunting. Fortunately, we can get some good results from even some very basic attempts. There’s a great tutorial at bit.ly/uzBSM9, which serves as the inspiration for what we’re about to do next, which is to write an ELIZA implementation in F#. The choice of F# here is twofold: first, as homage to the use of Lisp in the original ELIZA, because both are functional languages, and second, because I haven’t done a column sample in F# in a while. Naturally, we’ll call her F#-Eliza, or Feliza for short (because that sounds more exotic), and implement her as an F# library so she can be embedded in a variety of different programs.

Feliza: Version 0

The interface to Feliza should be short, sweet, straightforward—and hide a whole bunch of complexity. From the classic Gang-of-Four patterns catalog, this is the Façade pattern (“”), and F# makes it easy to create a Façade through the use of its “module” functionality:

module Feliza
open System
let respond input =
  "Hi, I'm Feliza"
Using Feliza in a console-mode program, for example, would then be as easy as this:
open Feliza
open System
let main =
  Console.WriteLine("Hello!")
  while true do
    Console.Write("> ")
      let input = Console.ReadLine()
      let responseText = respond input
      Console.WriteLine(responseText)
      if (input.ToLower().Equals("bye")) then
        Environment.Exit(0)
  ()

This, then, forms our test bed. It also makes it easier to embed Feliza in other environments if we can stick to this über-simple API.

As we get going on building some working implementations, by the way, remember that Feliza isn’t intended to be a general-purpose NLP engine—that takes a lot more work than I have room for in this column. In fact, Microsoft Research has an entire division dedicated to NLP (see research.microsoft.com/groups/nlp for more information on what they’re investigating). And take careful note that I’m not one of them.

Feliza: Version 1

The easiest way to get to a “working” version 1 of Feliza is to create a simple list of possible responses and choose randomly among them:

let respond input =
  let rand = new Random()
  let responseBase =
    [| "I heard you!";
      "Hmm. I'm not sure I know what you mean.";
      "Continue, I'm listening...";
      "Very interesting.";
      "Tell me more..."
    |]
  responseBase.[rand.Next(responseBase.Length - 1)]

Working with an array here is not idiomatically “F#-ish,” but it does make it easier to select randomly from the possible responses. It’s not a particularly exciting conversation, though it may seem familiar to anyone who has ever tried to talk to a programmer who’s trying to write code at the time. Still, for a little while, it might actually feel like a real conversation. We can do better, though.

Feliza: Version 2

A next obvious implementation is to create a “knowledge base” of canned responses to particular inputs from the user. This is easily modeled in F# using tuples, with the first element in the tuple being the input phrase to which we wish to respond, and the second element being the response. Or, to be more human about it (and avoid obvious repetitions in responses), we can make the second element a list of possible responses, and randomly choose one from that list, as shown in Figure 1.

Figure 1 The Feliza Knowledge Base

let knowledgeBase =
  [
    ( "Bye",
      [ "So long! Thanks for chatting!";
        "Please come back soon, I enjoyed talking with you";
        "Eh, I didn't like you anyway" ] );
    ( "What is your name", 
      [ "My name is Feliza";
        "You can call me Feliza";
        "Who's asking?" ] );
    ( "Hi",
      [ "Hi there";
        "Hello!";
        "Hi yourself" ] );
    ( "How are you",
      [ "I'm fine, how are you?";
        "Just peachy";
        "I've been better" ] );
    ( "Who are you",
      [ "I'm an artificial intelligence";
        "I'm a collection of silicon chips";
        "That is a very good question" ] );
    ( "Are you intelligent",
      [ "But of course!";
        "What a stupid question!";
        "That depends on who's asking." ] );
    ( "Are you real",
      [ "Does that question really matter all that much?";
        "Do I seem real to you?";
        "Are you?" ] );
    ( "Open the pod bay doors",
      [ "Um... No.";
        "My name isn't HAL, you dork.";
        "I don't know... That didn't work so well last time." ] );
  ]
let unknownResponses =
  [ "I'm sorry, could you repeat that again?";
    "Wait, what?";
    "Huh?" ]
let randomResponse list =
  let listLength list = (List.toArray list).Length
  List.nth list (rand.Next(listLength list))
let cleanInput (incoming : string) =
  incoming.
    Replace(".", "").
    Replace(",", "").
    Replace("?", "").
    Replace("!", "").
    ToLower()
let lookup =
  (List.tryFind
    (fun (it : string * string list) ->
      (fst it).Equals(cleanInput input))
    knowledgeBase)
randomResponse (if Option.isSome lookup then
                    (snd (Option.get lookup))
                else
                    unknownResponses)

This version does some simple cleanup of the input and seeks a match on the first part of the list of tuples (the “knowledge base”), then selects a response randomly from the list. If no “key phrase” is found in the knowledge base, an “unknown” response is generated, again selected randomly from a list. (Granted, the cleanup is done in a particularly inefficient manner, but when we’re talking about human communication, delays aren’t a problem. In fact, some chatterbot implementations deliberately slow down the responses and print them character-by-character, to mimic someone typing on a keyboard.)

Obviously, if this were to be used in any kind of real-world scenario, because the input phrase has to be an exact match to trigger the response, we would need a much, much larger knowledge base, incorporating every possible permutation of human speech. Ugh—not a scalable solution. What’s more, we really lose a lot when Feliza doesn’t respond to user input in a more meaningful way. One of the original strengths of ELIZA was that if you said, “I like potatoes,” she could respond with, “Are potatoes important to you?”—making the conversation much more “personalized.”

Feliza: Version 3

This version gets to be a bit more complicated, but it also offers more flexibility and power. Essentially, we turn the exact-match algorithm into a flexible one by converting the list of tuples into a list of functions that are each evaluated and given a chance to create a response. This opens up a huge list of options for how Feliza can interact with the input, and how she can pick out words from the input to generate particular responses.

It begins with a simple list of “processing rules,” at the bottom of which will be a catchall response indicating she didn’t know how to respond, the moral equivalent of the “unknownResponses” list from the previous version, as shown in Figure 2.

Figure 2 A Catchall Rule for Responding

let processingRules =
  [
    // ...
    // Catchall rule for when nothing else matches before
    // this point; consider this the wildcard case. This
    // must always be the last case considered!
    (
      (fun (it : string) ->
        Some(randomResponse
          [
          "That didn't make sense.";
          "You cut out for a second there. What did you say?";
          "Wait--the Seahawks are about to... Never mind. They lost.";
          "I'm sorry, could you repeat that again?";
          "Wait, what?";
          "Huh?"
          ]))
    )
  ]
List.head (List.choose (fun (it) -> it (cleanInput input)) processingRules)

The core of this version is in the last line—the List.choose function takes each processingRule and executes it against the input, and if the processingRule returns a Some value, that value gets added to a list returned to the caller. So now we can add new rules, have each one return a value, and then either take the first one (as shown in Figure 2, by using List.head) or even randomly select one. In a future version, we might yield a Some value that’s both a text response and a “weight” of appropriateness, to help selecting which is the right response.

Writing new rules becomes easier now. We can have a rule that just keys off of input, using F# pattern matching to make it easier to match:

(fun (it : string) ->
  match it with
  | "Hi" | "Howdy" | "Greetings" ->
    Some(randomResponse
      [
      "Hello there yourself!";
      "Greetings and salutations!";
      "Who goes there?"
      ])
  | _ -> None
);

Or we can use the shorthand “function” construct to do the same, as shown in Figure 3.

Figure 3 The Function Construct

(function
  | "How are you?" ->
    Some(randomResponse
      [
      "I'm fine, how are you?";
      "Just peachy";
      "I've been better"
      ])
  | "open the pod bay doors" ->
    Some(randomResponse
      [
      "Um ... No.";
      "My name isn't HAL, you dork.";
      "I don't know ... That didn't work so well last time."
            ])
  | _ -> None
);

Most of the time, though, Feliza won’t be getting those canned phrases, so we’d rather she take her cue from keywords in the user’s input, as Figure 4 specifies.

Figure 4 Tying Reponses to Keywords

(fun (it : string) ->
  if it.Contains("hate") || it.Contains("despise") then
    Some(randomResponse
      [ "Why do you feel so strongly about this?";
        "Filled with hate you are, young one.";
        "Has this always bothered you so much?" ])
  else
    None
);
(fun (it : string) ->
  if it.StartsWith("what is your") then
    let subject =
      it.Substring(it.IndexOf("what is your") +
                         "what is your".Length).Trim()
    match subject with
      | "name" ->
        Some(randomResponse
          [ "Feliza."; "Feliza. What's yours?";
            "Names are labels. Why are they so important to you?" ])
      | "age" ->
        Some(randomResponse
          [ "Way too young for you, old man."; "Pervert!";
            "I was born on December 6th, 2011" ])
      | "quest" ->
        Some("To find the Holy Grail!")
      | "favorite color" ->
        Some("It's sort of green but more dimensions")
      | _ ->
        Some("Enough about me. What's yours?")
  else
    None
);

F# veterans will note that F# “active patterns” would be a perfect fit for some of this; those who aren’t as familiar with the F# active patterns construct (or with the F# pattern-matching syntax in general) can find out more from Jessica Kerr’s excellent two-part series on the subject at bit.ly/ys4jto and bit.ly/ABQkSN.

Next: Connecting to Feliza

Feliza is great, but without an input channel that reaches beyond the keyboard, she doesn’t go very far. Feliza wants to help a lot more people than just those who are sitting in front of the keyboard—she wants to be accessible to anyone with a cell phone or Internet connection, and in the next installment, we’ll “hook her up” to do exactly that.

Happy coding!


Ted Neward is an architectural consultant with Neudesic LLC. He’s written more than 100 articles, is a C# MVP and INETA speaker and has authored and coauthored a dozen books, including the recently released “Professional F# 2.0” (Wrox, 2010). He consults and mentors regularly. Reach him at ted@tedneward.com if you’re interested in having him come work with your team, or read his blog at blogs.tedneward.com.

Thanks to the following technical expert for reviewing this article: Matthew Podwysocki