Not As Easy As It Looked

Eeny meeny miny moe, which test case do I want to show?

Test Case 0 Failed!!!

Input: Will this test pass?

Output: I’m sorry, could you try rewording that?

Expected: I predict that this test will pass

This doesn’t look so bad. We already wrote a rule for “Is X Y?” so writing a rule for “Will X Y?” should be as easy as copy pasting and switching a few words. Behold!

push(@chatPatterns,
   [qr/\AWill ([a-zA-Z]+) (.+)\?\z/,
      "I predict that UIF0 will UIF1"]);

I’ll just drop that into the rules list right after the “Is X Y?” rule and we should be good to go.

Test Case 0 Failed!!!

Input: Will this test pass?

Output: I predict that this will test pass

Expected: I predict that this test will pass

Uh oh. That didn’t quite work. DELPHI did manage to figure out that test 0 was a “Will X Y?” style question but when generating the answer it put the “will” in the wrong place. Can you figure out why?

[Please use this break in the blog’s flow to consider why this happened.]

The problem here has to do with how we defined the rule. We’ve been calling it “Will X Y?” but the rule is actually more like “Will Noun Verb?” or “Will Noun-Phrase Verb-Phrase?”.

Our current dumb rule assumes that the noun will always be the first word after the word “Will” and that everything else will be part of the verb phrase. This works out great for sentences like “Will Batman catch the villain?” but completely falls apart when you start adding adjectives to the noun and get things like “Will the police catch the villain?”

So what we really need is a “Will” rule that is smart enough to group common adjectives with the noun and treat them all like one big super-noun. Here is a quick first pass (WARNING: WEIRD REGULAR EXPRESSION AHEAD):

/\AWill ((?:(?:this|the|that|a|an) )*[a-zA-Z]+) (.+)\?\z/

Don’t panic just yet, this rule is actually a lot simpler than it looks. But first you need to understand what all those “?:” symbols are doing. Hopefully you remember that parenthesis create capture groups that group patterns together and then store their matches for future use. But sometimes you want to group patterns together without storing them for later. You can accomplish this by starting your capture group with the special symbols “?:”, which then turns of the capturing and lets you use the parenthesis as a simple grouping tool.

This is important for our “Will” rule because we want to capture the entire noun-phrase and the entire verb-phrase but we don’t want to capture any of the individual parts of those phrases. For example, we have improved our noun-phrase by adding in two groups of nested parenthesis for handling common article adjectives. The inner parenthesis match common adjectives and the outer parenthesis make sure there is a space following each adjective. We mark both these rules as “?:” noncapturing because while we certainly do want to match nouns that start with a series of adjectives we only want to capture those adjectives as part of the noun and not on their own.

What would happen without those noncapturing symbols? Well, the first big parenthesis set would capture the entire noun-phrase and substitute it into the output just like we want. But the second capture group wouldn’t be the verb-phrase like we originally wanted. Instead the second capture group would be the inner parenthesis matching the articles leading to all sorts of problems. See for yourself:

Input: Will this test pass?

Output: I predict that this test will this

Expected: I predict that this test will pass

See what I mean? We successfully grabbed “this test” and put it into the answer as a noun-phrase but we then grabbed “this ” as our second capture group while the verb-phrase “pass” got pushed into a later capture group slot. Not what we wanted at all.

Instead we’ll just tell the inner parenthesis not to capture. Now the noun-phrase always goes in slot one and the verb-phrase always goes in slot two and everything works wonderfully.

Test Case 0 Passed

…

Passed 7 out of 11 tests

Wait A Minute, Isn’t This A Problem For “Is” Rules Too?

Clever readers might be asking themselves “If adjectives broke our simple “Will X Y?” rule, then won’t they break our old “Is X Y?” rule too?” Well good job for noticing that clever readers, because that’s the exact problem we see in our next test case:

Test Case 1 Failed!!!

Input: Is the sky blue?

Output: Fate indicates that the is sky blue

Expected: Fate indicates that the sky is blue

Fortunately we can fix it the exact same way:

/\AIs ((?:(?:this|the|that|a|an) )*[a-zA-Z]+) (.+)\?\z/

Test Case 1 Passed

…

Passed 8 out of 11 tests

You Shouldn’t Copy Paste Code

There is one little problem with this approach to adjectives: I’m hard coding a big list of words and then copy pasting it into multiple functions. This will be a real pain if we ever have to update the list in the future. For instance, if we wanted to add possessive adjectives into the list (my, your, his, her, their) we would have to rewrite two different rules. And if we ever decide a third rule needs access to the list we’ll have to copy paste the whole thing.

Much better to turn that portion of the rules into a separate variable that can be included in multiple functions. Which in Perl you can do like this:

#put this before the code starts to build the pattern and response array
my $commonAdjectives=qr/(?:this|the|that|a|an)/;
my $noncaptureAdjectiveChain=qr/(?:$commonAdjectives )*/;

And now we can just update the rules to use these handy variables anywhere we want to match an arbitrarily long chain of adjectives with a single space after every word.

/\AIs ($noncaptureAdjectiveChain[a-zA-Z]+) (.+)\?\z/

/\AWill ($noncaptureAdjectiveChain[a-zA-Z]+) (.+)\?\z/

Those of you following along in a language other than Perl will have to figure out on your own how and if your language handles inserting variables into a regular expression. If all else fails you can always just go back to the copy pasting thing.

Let’s Test By Adding Some More Adjectives

Now that we can add new adjectives to two different rules by just updating a single variable we should write a few new tests and make sure it works. How about these?

$testCases[11][0] = "Will his code compile?"
$testCases[11][1] = "I predict that his code will compile";

$testCases[12][0] = "Is this big blue box actually a time machine?";
$testCases[12][1] = "Fate indicates that this big blue box is actually a time machine";

The first test is a straightforward test to make sure we can add possessives to the adjective list. The second test is a little bit more complex, requiring us to not only add two new adjectives to our list (big and blue) but also testing to make sure the code can chain multiple adjectives together into a row.

Of course, right now they both fail. The first test doesn’t recognize “his” as an adjective so it assumes it is a noun and puts the “will” in the wrong place. The second test recognizes “this” as an adjective but not “big” and does the same thing.

Test Case 11 Failed!!!

Input: Will his code compile?

Output: I predict that his will code compile

Expected: I predict that his code will compile

Test Case 12 Failed!!!

Input: Is this big blue box actually a time machine?

Output: Fate indicates that this big is blue box actually a time machine

Expected: Fate indicates that this big blue box is actually a time machine

But after updating our list of adjectives:

my $commonAdjectives=qr/(?:this|the|that|a|an|his|her|my|your|their|big|blue)/;

Test Case 11 Passed

Test Case 12 Passed

——————–

Passed 10 out of 13 tests

Test Failure!!!

How Many Adjectives Do We Need?

DELPHI now knows how to handle 12 different adjectives. And while that is pretty nifty it’s worth pointing out that the English language has a lot more than just 12 adjectives. In fact, English is one of the world’s largest languages* and easily has several tens of thousands of adjectives. Even worse, English allows you to “adjectivify”** other words to creating new adjectives on the spot, like so:

“These new computery phones have a real future-licious feel to them but with the default battery they’re actually kind of brickish.”

My spell checker is convinced that sample sentence shouldn’t exist but even so you probably understood what I meant. Which just goes to show the huge gap in how good humans are at flexible language processing and how bad computers still are.

But what does this mean for DELPHI? Do we need to generate a giant adjective list? Do we need to teach it how to handle nouns and verbs that have been modified to act like adjectives? Do we need to spend twelve years earning multiple PhDs in computer science and linguistics in order to build a more flexible generateResponse function?

Well… no. Remember, our goal isn’t to create a program that can fully understand the human language. We just want a bot that can answer simple questions in an amusing way like some sort of high-tech magic eight ball. As long as DELPHI can handle simple input and gracefully reject complex input it should feel plenty intelligent to the casual user.

Furthermore, we can actually depend on users to play nice with DELPHI. Most people, after being scolded by DELPHI once or twice for trying to be clever will start to automatically pick up on what sorts of inputs do and don’t work. The fact that DELPHI can’t handle obscure adjectives will eventually teach users to stick to straightforward questions.

All things considered we can probably “solve” the adjective problem by teaching DELPHI the hundred most common adjectives in the English language and then hoping that users never bother going beyond that. Later on we can have some test users talk to DELPHI and use their experiences to decide whether or not we need to add more adjectives or build a more complex system.

Conclusion

Today we caught a glimpse of how simple pattern matching chatbots can completely fall apart when confronted with real English. But we also saw a quick way to band-aid over the worst of these problems and we have hope that our bot can be written in such a way that users never noticing that DELPHI is too dumb to understand that “house” and “that big house over there” are actually the same thing.

Next time, more test cases and more examples of English language features that are annoying to program around.

* As the popular saying goes: English has pursued other languages down alleyways to beat them unconscious and rifle their pockets for new vocabulary.

** Look, I just verbed a noun!

There Is More To Life Than Tests

So far we’ve focused entirely on running our chatbot through automated tests. But eventually we’ll want some way for actual users to talk to DELPHI too. And since I just recently finished separating the chat code from the testing code I figure now is a great time to also introduce some user focused code.

Getting DELPHI to talk to a human is pretty easy. The generateResponse function already knows how to… well… generate responses to input. All that’s left is figuring out how to feed it human input instead of test input. Perl let’s us do this in under ten lines (which I put in a file name “chat.pl”):

#! /usr/bin/perl -w

use strict;

require 'DELPHI.pm';

while(<>){
   chomp;
   print "DELPHI: ", DELPHI::generateResponse($_), "\n";
}

You Promised No Tricky Perl!

Oh, I did promise that. So I guess the only honorable thing to do is to write a new version of “chat.pl” that doesn’t use quite so many shortcuts.

#! /usr/bin/perl -w

use strict;

require 'DELPHI.pm';

while( my $userInput = <STDIN> ){
   chomp($userInput); #Remove trailing newline character with chomp
   my $response = DELPHI::generateResponse($userInput);
   print "DELPHI: ", $response, "\n";
}

There, that’s better. Everything is much easier to understand now. We have a simple while loop that grabs lines of input from standard input, letting the user type questions for DELPHI. And then since DELPHI doesn’t like newlines we use the handy Perl function chomp to remove them from the input. Now that we have a user input string with no nasty newline at the end we pass it DELPHI::generateResponse and finally print out DELPHI’s reply for the user to read.

This Is A Horrible User Interface

If you tried to run “chat.pl” as is you probably noticed that it’s not very user friendly. When you first start the program it just sits on the command line and hopes that the user will eventually figure out he’s supposed to type something. And the only way to break out of the loop is to send the end of file character (ctrl-z or ctrl-d depending on your OS). We can do better than this!

#! /usr/bin/perl -w

use strict;

require 'DELPHI.pm';

print "DELPHI: The oracle greets you. What questions are on your mind?\n";
print '>';

while(my $userInput = <STDIN>){
    chomp($userInput); #Remove trailing newline character with chomp
    
    if(lc($userInput) eq 'goodbye' || lc($userInput) eq 'quit'){
        last; #Break out of while loop
    }
    
    my $response = DELPHI::generateResponse($userInput);
    print "DELPHI: ", $response, "\n";
    print '>';
}

print "DELPHI: Come back anytime\n";

Mostly cosmetic changes here. We start the program with some quick text that lets the user know they are dealing with a question answering bot and we end with a friendly farewell. We also put a helpful ‘>’ at the start of every input line so they user knows when they’re supposed to be typing.

I’ve also added the ability to exit the loop by typing “goodbye” or “quit”. To help with this I use the function lc, which returns an all lowercase version of whatever the user types. This way we don’t have to worry about users that capitalize “Goodbye” or people who try to “EXIT” with their caps lock key on. We then break the loop by using the last command which immediately exits the loop.

DELPHI’s First Words

Now DELPHI is currently only passing 6 out of 11 test cases so it’s really not ready for genuine human conversation. But we can still fire up our chat program and at see what happens.

DELPHI: The oracle greets you. What questions are on your mind?

>Is this working?

DELPHI: Fate indicates that this is working

>That’s nice.

DELPHI: I don’t want to talk about that. Please ask me a question

>Goodbye

DELPHI: Come back anytime

Not a wonderful conversation, but it does prove that DELPHI works just as well interactively as it does during tests. Now we can get back to writing more rules and responses in hope of getting DELPHI to perform better the next time we decide to talk to it directly.

Is DELPHI Too Strict?

If you’ve been playing with “chat.pl” you might have noticed that DELPHI is currently really stuck up about how you do or don’t capitalize words. For example:

DELPHI: The oracle greets you. What questions are on your mind?

>is this working?

DELPHI: I’m sorry, could you try rewording that?

>Is this working?

DELPHI: Fate indicates that this is working

I don’t plan to do anything about this problem right now. I just wanted to point it out to everyone so that you won’t think I overlooked this fairly big usability flaw. I’ll (probably) eventually fix this be rewriting DELPHI to care less about case, but for now I’m just going to go back to writing rules.

Low Hanging Fruit

We still have lots of test cases to try and pass. Some of them are easy and some of them will be pretty hard. Today I’m going to knock out a few of the easier ones.

Specifically, I’m going to try to get DELPHI to notice when a user has made a simple grammar mistake in their question. Things like starting a sentence with “Why” but not including a question mark at the end or ending a sentence with a question mark but not beginning with any question words that DELPHI recognizes. When a user makes this kind of mistake we want to point it out to them and give them a quick hint about how to better format their questions to get a good response out of DELPHI.

I Don’t Understand The Question

Here’s the first test case I want to work with:

Test Case 7 Failed!!!

Input: Pumpkin mice word salad?

Output: I don’t want to talk about that. Please ask me a question

Expected: I’m sorry, could you try rewording that?

This test case represents a user who has typed a question that DELPHI doesn’t understand. At least, we think it’s a question since it has a question mark at the end. So we want to suggest to the user that they reword the question in a simpler way. Hopefully this will convince users who type things like “Dodgers win the world series?” to try again with the better formatted “Will the Dodgers win the world series?”

The rule for this is pretty simple. We just create a low priority rule that matches a question mark anywhere in the user’s input. We let the high priority rules catch all the good input with question marks and then use this rule to clean up whatever is left.

push(@chatPatterns, 
        [qr/\?/,
            "I'm sorry, could you try rewording that?"]);

I put his rule in the system right above the final catch all pattern. I’m sure you can figure out why I didn’t try to put it after the catch all pattern. In any case:

Test Case 7 Passed

Is That Supposed To Be A Question?

Here’s the second test case I plan on fixing today:

Test Case 9 Failed!!!

Input: Why do you say things like that

Output: I don’t want to talk about that. Please ask me a question

Expected: Did you forget a question mark? Grammar is important!

This test case is the opposite of the last test case. This time the user input starts with a well recognized question word but it doesn’t end with a question mark. We want to remind the user that question marks are important so they can rewrite the question in a format the DELPHI will understand.

This is another easy low-priority rule. Once again we put it near the end of our rule list to make sure that it only catches question word input that didn’t match any of the previous, better rules.

I am introducing some new regex syntax here though. The ‘|’ symbols stand for “or” and lets us create a regular expression that will match any one item from a list of possibilities. That way we can build one rule to catch lots of different question word beginning inputs.

push(@chatPatterns, 
        [qr/\A(Why|Is|Are|Do|Does|Will)/,
            "Did you forget a question mark? Grammar is important!"]);

Besides the new “or” syntax there shouldn’t be anything surprising here. I start out with the \A anchor to indicate that we’re only looking for input that starts with a question word and then I make a list of all the common question words I expect DELPHI to run into.

I put this low priority rule after the question mark rule I just wrote but still before the catch all rule for the obvious reason that the catch all rule always needs to be last.

Test Case 9 Passed

Conclusion

With these two new rules DELPHI is now ready to criticize the grammar of anyone who dares to try to ask it a poorly formatted question. And our success rate is slowly creeping upwards!

Passed 6 out of 11 tests

Test Failure!!!

Sadly the test cases we are still failing happen to be the tricky ones, so we’re going to have to start doing some clever programming in the near future. But before that let’s take a little detour and build an actual user interface for DELPHI so that we can talk to it. I’m tired of letting the automated tests have all the fun, I want to talk to the chatbot too!

Just Because It Works Doesn’t Mean It’s Good

I’ll be honest, I’m a neat freak. And our current code is starting to get a little messy. Keeping our chatbot code in the same file as all our test code is not neat. Creating our array of chat patterns inside of the generateResponse method is not good. So let’s take just a few minutes and fix both of those problems.

The first thing I’m going to do is separate the test code from the chatbot code by moving generateResponse into a file named DELPHI.pm. Then I’m going to wrap it all inside of a package called DELPHI, which is basically just a way to attach a prefix to a bunch of Perl variables and functions. This will transform generateResponse into DELPHI::generateResponse.

Then I’m going to clean up generateResponse by moving the array of input patterns and responses outside of the function. Now the chat array will be built, once, when the DELPHI.pm file is first referenced. This helps keep generateResponse small and readable; no matter how many rules we add to our chatbot generateResponse will always remain short and easy to understand.

Updating our tests to work with these changes is a pretty simple two line change. First, we need to tell it to load the DELPHI.pm file by adding this simple command near the top of our file:

require 'DELPHI.pm';

The second change is just as easy. Our test code used to directly reference generateResponse, which worked because they were both part of the same file and package. Now that generateResponse lives in it’s own package we’ll have to change the line:

my $output = generateResponse($test->[0]);

Now it needs to be:

my $output = DELPHI::generateResponse($test->[0]);

And that’s all there is to it. Now our test program knows to look for generateResponse inside of the DELPHI package that it grabbed out of the DELPHI.pm file.

Now for the moment of truth… did it work? Did we successfully clean our code without breaking anything? Sounds like a job for our automated tests.

Passed 4 out of 11 tests

Test Failure!!!

That’s a relief! Even after modifying all that code the tests still run, no errors are thrown and we’re passing and failing all the same tests we used to.

The Code So Far

I figure now is a good time for a complete code dump in case anyone wants to run my code themselves and see what I’m doing. On the other hand… maybe you’re from the future where I’ve already finished DELPHI and released the complete code. In that case this old incomplete DELPHI code might be worth a laugh:

First up is DELPHI.pm. Note the “1” at the end of the file. Perl expects all packages to end with something that evaluates to true and the number 1 is the traditional way to do this.

package DELPHI;

my @chatPatterns;

push(@chatPatterns, 
        [qr/[a-zA-Z]+ or [a-zA-Z]+.*\?\z/,
            "Fate indicates the former"]);

push(@chatPatterns, 
        [qr/\AIs ([a-zA-Z]+) (.+)\?\z/, 
            "Fate indicates that UIF0 is UIF1"]);

push(@chatPatterns,
        [qr/\AWhy (.+)\?\z/,
            "Because of reasons"]);

push(@chatPatterns,
        [qr/.*/,
            "I don't want to talk about that. Please ask me a question"]);

sub generateResponse{
    my $userInput = $_[0];

    foreach my $chatPattern (@chatPatterns){
        
        if(my @UIF = ($userInput =~ $chatPattern->[0])){
            my $response = $chatPattern->[1];
            for(my $i=0; $i<@UIF; $i++){
                my $find = "UIF$i";
                my $replace = $UIF[$i];
                $response =~ s/$find/$replace/g;
            }
            return $response;
        }
    }
    return "Base Case Failure Error!";
}

1;

And then here is test.pl

#! /usr/bin/perl -w

use strict;

require 'DELPHI.pm';

my @testCases;

$testCases[0][0] = "Will this test pass?";
$testCases[0][1] = "I predict that this test will pass";

$testCases[1][0] = "Is the sky blue?";
$testCases[1][1] = "Fate indicates that the sky is blue";

$testCases[2][0] = "Does this program work?";
$testCases[2][1] = "Fate indicates that this program works";

$testCases[3][0] = "Do computers compute?";
$testCases[3][1] = "Fate indicates that computers compute";

$testCases[4][0] = "Do my readers enjoy this blog?";
$testCases[4][1] = "Fate indicates that your readers enjoy this blog";

$testCases[5][0] = "Is it better to be loved or feared?";
$testCases[5][1] = "Fate indicates the former";

$testCases[6][0] = "Why is natural language processing so hard?";
$testCases[6][1] = "Because of reasons";

$testCases[7][0] = "Pumpkin mice word salad?";
$testCases[7][1] = "I'm sorry, could you try rewording that?";

$testCases[8][0] = "Pumpkin mice word salad";
$testCases[8][1] = "I don't want to talk about that. Please ask me a question";

$testCases[9][0] = "Why do you say things like that";
$testCases[9][1] = "Did you forget a question mark? Grammar is important!";

$testCases[10][0] = "Is Perl a good choice for this program?";
$testCases[10][1] = "Fate indicates that Perl is a good choice for this program";

my $testCount=0;
my $successCount=0;

foreach my $test (@testCases){
    my $output = DELPHI::generateResponse($test->[0]);
    if( $output ne $test->[1] ){
        print "Test Case $testCount Failed!!!\n";
        print "Input: ".$test->[0]."\n";
        print "Output: $output\n";
        print "Expected: ".$test->[1]."\n";
    }
    else{
        print "Test Case $testCount Passed\n";
        $successCount++;
    }
    
    $testCount++;
}

print "--------------------";
print "\n";
print "Passed $successCount out of $testCount tests\n";
if($testCount == $successCount){
    print "All Tests Passed!\n";
}
else{
    print "Test Failure!!!\n";
}

A Note On Performance

My main goal here was to make the code easier to read and manage by separating my chatbot code from my test code and then further separating my response generation code from the response data. Not that my little 150 line script was actually that hard to read and manage in the first place. I probably could have safely procrastinated cleaning it up until I had a few dozen more test cases and a few dozen more rules.

But I was also curious if there would be any performance gain from moving the array creation outside of the generateResponse function. As things were the code had to rebuild the same nested array every time generateResponse was called. Sounds wasteful! Much better to move that array somewhere where it only has to be built once no matter how often generateResponse is called.

On the other hand, people who write compilers and interpreters* are really quite frightfully smart. One of their favorite optimization tricks is to find repetitive bits of code and then turn them into static data. Sometimes you can get away with something stupid like building a static array again and again and just rely on the compiler to fix it for you.

Which made me wonder: Would cleaning up generateResponse speed up my code or was the the system already optimizing my poor design decision? Let’s run some tests!

My particular test was pretty simple. I created a quick little file that included both version of generateResponse, one building the response array inside the method and one building the response array ahead of time. I then had both functions generate a response to a short phrase a million times ina row and kept track of how long it took for them to complete. Here are the results:

The method with array creation took 19.758241891861 seconds

The method without array creation took 9.73499703407288 seconds

So by moving array creation outside of the function we managed to double how fast the function runs. Apparently this particular mistake was too stupid for the compiler to fix on it’s own. Whoops.

Conclusion

A few quick changes and now our code is both cleaner and more efficient. Now to get back to adding new response patterns to DELPHI.

* Perl 5 is both interpreted and compiled depending on how you define interpret and compile.

Quick Review

Before we start writing new input patterns and response templates let’s take a look at the three we already have. If you’ve read this far I assume you understand enough about regular expressions that I don’t need to explain everything. If that is not true consider this a learning experience, like a mother bird pushing her chicks out of the nest and into the wide world of regex to help them learn to fly.

I don’t know if birds really do that, but it’s a nice metaphor. Anyways, on to the regular expressions!

Pattern: /\AIs ([a-zA-Z]+) (.+)\?\z/

Response: Fate indicates that UIF0 is UIF1

This is the basic pattern for finding sentences of the form “Is X Y?” and transforming them into the prediction “X is Y”.

Pattern: /\AWhy (.+)\?\z/

Response: Because I said so

This is the basic pattern for finding “Why X?” questions and then giving an unsatisfying excuse along the lines of “Just because”.

Pattern: qr/.*/

Response: I don’t want to talk about that. Please ask me a question

This is our catch-all base case. It matches anything and makes sure that even if the user types in something completely unexpected DELPHI can still generate a response instead of crashing.

Writing A New Rule

Ok, let’s fire up our automatic test and find a test we’re failing. We’ve barely written any code yet so there should be plenty to choose from.

Hmm… this one looks easy to fix.

Test Case 5 Failed!!!

Input: Is it better to be loved or feared?

Output: Fate indicates that it is better to be loved or feared

Expected: Fate indicates the former

This is the “or” question case and we want DELPHI to give us an answer about which of the two options is best. Instead it looks like DELPHI matched this with the “Is X Y?” pattern, leading to a rather dumb answer.

How to fix this? First, I’ll have to write an “or” pattern and response. Second, I’ll have to make sure that the “or” pattern has a higher priority than the “Is X Y?” pattern. Now please imagine me typing some code for about five minutes. Click click… and done:

$chatPatterns[0][0]=qr/[a-zA_Z]+ or [a-zA-Z]+.*\?\z/;
$chatPatterns[0][1]="Fate indicates the former";

$chatPatterns[1][0]=qr/\AIs ([a-zA-Z]+) (.+)\?\z/;
$chatPatterns[1][1]="Fate indicates that UIF0 is UIF1";

$chatPatterns[2][0]=qr/\AWhy (.+)\?\z/;
$chatPatterns[2][1]="Because I said so";

$chatPatterns[3][0]=qr/.*/;
$chatPatterns[3][1]="I don't want to talk about that. Please ask me a question";

The regex for “or” was pretty simple. We just look for the word “or” with at least one word before it, one word after it and a final ‘?’ at the end. And since we want this rule to be high priority we put it at the very top of our list. Now to see if it worked:

Test Case 5 Passed

…

Passed 3 out of 11 tests

We passed the test case and we didn’t lose either of the two test cases we were already passing. Cool!

Programmer Convenient Syntax

One issue with this latest change was that in order to put the new “or” rule in high priority slot index 0 I had to renumber every other entry in the array. That was kind of annoying and leaves me at risk of accidentally creating two rules with the same index (which would be bad).

So how about we switch to a syntax that let’s me insert new rules wherever I want? And as long as I’m rewriting my rules why I don’t fix the “Why” rule. When I first wrote it I accidentally programmed in a different “because” response than the test was expecting. By replacing the old bad response with a new good response I should be able to get up to passing four tests.

my @chatPatterns;

    push(@chatPatterns, 
            [qr/[a-zA-Z]+ or [a-zA-Z]+.*\?\z/,
                "Fate indicates the former"]);

    push(@chatPatterns, 
            [qr/\AIs ([a-zA-Z]+) (.+)\?\z/, 
                "Fate indicates that UIF0 is UIF1"]);
    
    push(@chatPatterns,
            [qr/\AWhy (.+)\?\z/,
                "Because of reasons"]);

    push(@chatPatterns,
            [qr/.*/,
                "I don't want to talk about that. Please ask me a question"]);

Same rules, but written in a slightly different way. Instead of explicitly choosing an index for each rule I use the push function to just glue new rules onto the end of the list. This means that I can change the priority of rules just by switching their order around, no need to recalculate indexes by hand. This will also make it easier to add new rules to the top or middle of the priority list.

You’ll also notice that I’m using the [ array, items, here ] syntax to build pattern and response arrays right inside of the push command. That feels a lot cleaner to me than trying to do something like this:

my @chatPatterns;

my @orPatternResponse;
$orPatternResponse[0] = qr/[a-zA-Z]+ or [a-zA-Z]+.*\?\z/;
$orPatternResponse[1] = "Fate indicates the former";
push(@chatPatterns, @orPatternResponse);

my @isPatternResponse;
$isPatternResponse[0] = qr/\AIs ([a-zA-Z]+) (.+)\?\z/;
$isPatternResponse[1] = "Fate indicates that UIF0 is UIF1";
push(@chatPatterns, @isPatternResponse);

Yuck! Just look at all those temporary variables I’d have to come up with names for. And I’m not even sure this code would work. I think pushing an array onto an array just glues them together instead of nesting them like we want. Let’s stick with the anonymous array brackets.

Conclusion

After adding the “or” rule and fixing our “why” response we now are passing 4 out of 11 test cases. That’s good progress! But adding more and more rules directly inside the generateResponse function is getting pretty messy. Maybe next time I’ll do something to clean that up.

Demystifying Regular Expressions

The time has finally come to talk about the regular expressions that I’ve been using for the pattern matching part of this pattern matching chatbot. Regular expressions are just a special way to describe patterns of symbols. A regular expression engine, like the one inside Perl, can then compare strings and text to a regular expression and figure out whether they match that pattern or not.

Although regular expressions are really useful they have a bad reputation as being hard to read and write. And to be honest it can be hard to remember all the dozens of rules involved in regex pattern matching. I personally would never dare write anything but the simplest of regex without a cheat sheet on hand.

Even more frustrating is the fact that “wrong” regular expressions don’t throw errors. They just don’t match what you expect them to match. And figuring out why they aren’t matching what you want can be difficult. The worst errors happen when your regex does match everything you want… but also matches things you don’t. So it looks like it’s working properly at first but if it ever comes across a false match your program will suddenly break and you won’t know why.

This is one reason I’m using test driven development for DELPHI. The automatic tests should catch most of my regex mistakes, so I don’t have to worry too much about forgetting a single character and breaking my entire program. The tests will also point out the mistakes as soon as I make them, letting me fix them while the code is still fresh in my mind and before forgetting what the broken regex was supposed to do.

So… Talking About Regular Expressions

I’m going to briefly briefly cover the bare minimum or regex knowledge you need to follow along with me as I program DELPHI. This is a probably a bad idea on my part. If you don’t understand regular expressions this won’t be nearly enough information to teach you how they work. And if you do know how regular expressions work this will be a boring reminder. I honestly should probably have just included a link to a real regular expression tutorial and left it at that.

Well, whatever. This is my Let’s Program. I can waste space talking about regular expressions if I want.

But before we go anywhere we need to cover how to mark a regular experesion in Perl. By default you create a regular expression by putting an ‘/’ symbol before and after the regex pattern you want, very similar to how you mark a string by putting double quotes before and after.

/understand?/

Boring And Simple

The most boring and simple use for regular expressions is to check whether or not a string contains a specific substring. Maybe you’re trying to find every sentence in a book that includes the word “inconceivable”* or are searching through a bunch of code for comments with a “TODO” reminder.

Searching for specific substring is really easy. You just type that substring up as a regex and you’re good to go. Example: /inconceivable/ and /TODO/.

Powerful And Complex

If the only thing regular expressions could do was find specific substrings there would be no reason to use them. We would just use the substring function that almost all languages already have. The real reason to use regular expressions is because of all the powerful tools they give you to find generic patterns instead of specific strings.

Now get ready for a whirlwind tour of the most useful and common regular expression special pattern techniques.

First up are the + and * symbols, which let you find a single symbol or phrase multiple times. So while /abc/ will only match “abc” you can create phrases like /ab+c/ that will match “abc”, “abbc”, “abbbc” and so on. ‘*’ works almost the same as ‘+” except that ‘*’ indicates an optional match. So /ab+c/ and /ab*c/ will both match “abc” and “abbc” but only /ab*c/ will match “ac”.

Next up are anchors, which let you mark when a specific phrase absolutely has to end up at the beginning or end of a string. \A means that the next symbol has to be at the very start while \z means that the previous symbol has to come at the very end.

For example: /\AWhy/ only matches sentences that start with the word “Why”. Having a “Why” in the middle isn’t enough. Similarly “/\?\z/” only matches sentences that end with a question mark. Note that in this case we have to type ‘\?’ instead of just ‘?’ because the plain question mark is actually a special regex symbol**.

Next I want to mention symbol groups and the wild card. These let you search for generic types of symbols instead of specific substrings. You can search for any one digit with [0-9]. You can search for any letter with [a-zA-Z]. Then there is the wildcard ‘.’ that matches just about anything except the newline character. So if you really want a number followed by a letter followed by at least one more something you could write /[0-9][a-zA-Z]./

The last thing I want to mention are parenthesis. Parenthesis let you group multiple other symbols together into one pattern. For example, suppose that you wanted to find sentences where the phrase “abc” repeats. Trying /abc+/ won’t work because that focuses on the ‘c’. It will match “abc” and “abcc” but not “abcabc”.

Instead you want to try something like /(abc)+/. Now the regex engine knows to look for a repeat of the entire group, not just the last word.

And of course you can mix all these things together. /\A(abc)+[0-9][0-9]/ will match with any string that starts with one ore more groupings of “abc” followed by two digits. So “abc11” and “abcabc45” but not “aabc11” or “abc123” or “123abc12”.

Capture Groups

Remember three mini-paragraphs ago*** when I talked about how you can use parenthesis to match entire groups of symbols? Well it turns out that parenthesis have a second purpose too: they set up capture groups.

Capture groups are important because they signal for the regex engine to not just find a match but also to save those matches for later. This is very useful for all sorts of reasons. For instance, it lets you build complex regular expressions that match the same phrase in multiple locations.

/([a-zA-Z]+) is \1/

The \1 means “the same as the first capture group in this regex”, so this pattern will match any string where the text on the left of the word ‘is’ exactly matches the text on the right of the word, like “A is A” or “Perl is Perl”.

But that’s not all capture groups can do. You can also ask the regex system to give a copy of the capture groups to your non-regex code. This lets you pull information out of text patterns and then use the full power of your programming language to interpret and manipulate it as much as you want.

Imagine you were writing a program that was supposed to read scientific papers, look for metric weights and then convert those weights to pounds for your American boss.

First you would use a regular expression to look for numbers followed by metric weights abbreviations (g, kg, mg, etc…). By wrapping this search into a capture group you could then pull those numbers into your program, convert them into pounds and then insert them back into the document.

The regex for this metric conversion system might include something like /([0-9]+)kg/. This pattern doesn’t just match the phrase “500kg”, it extracts the 500 and passes it back to our program. How does it pass it back? That depends on the system. In Perl a pattern with capture groups will store the captures in numeric variables. The first capture goes in $1, the second in $2, the third in $3 and so on.

You can also assign capture groups directly to an array like this:

@captureArray = ($string =~ /(regex) (with) (captures)/

You’ll notice that this is the method I use in DELPHI.

Speaking of DELPHI, capture groups are a key component to our chatbot. By using capture groups we can extract useful bits of the user’s original input and use them to customize the chatbot’s output and make it seem more human.

So when the user asks “Is regex awesome?” DELPHI doesn’t just answer “Yes/No”, it uses capture groups to grab “regex” and “awesome” and glues them together to create the intelligent answer: “Regex is awesome.”.

Dissecting A Regular Expression

Feeling a little more comfortable with regular expressions? No? Then let’s spend some time dissecting a regular expression symbol by symbol.

/\AWhy (.+)\?\z/

You might recognize this as one of the three basic rules that I programmed into DELPHI when first testing the response generating system. Now let’d look at it’s individual parts.

The regex starts with \AWhy . The ‘\A’ means that the pattern has to happen at the beginning of the string. The ‘Why’ just means the exact phrase ‘Why’. Together this means that this regex pattern only matches phrases that start with ‘Why’.

After that there is a blank space. This tells the regex to match an actual blank space. So this means that there has to be a space directly after the ‘Why’.

After the space we get to (.+). The wildcard matches anything and the plus sign means that we want to match at least one thing. So the idea here is that after the ‘Why ‘ we want to see at least one more symbol. After all, a good question should be “Why something?” not just plain “Why?”.**** We also wrap this bit in a capture group in case we want to further analyze the exact sort of why question the user was asking.

Finally we have /\?\z/, indicating that matching strings absolutely have to end with a question mark.

Add them together and this pattern more or less matches any sentence of the pattern “Why X?”. Things like “Why is the sky blue?” or “Why are we using regex?”. But it will not match things like “Why?” (which doesn’t have enough text after the Why). It also won’t match “Why is this wrong” (no question mark) or “I wonder why this is wrong?” (doesn’t start with Why).

Conclusion

Congratulations, you’ve survived an entire article about regular expressions. Hopefully you’re feeling ready for the next post of this Let’s Program where I start writing new regular expressions to help DELPHI react to new communication patterns.

* I do not think it means what you think it means

** ? in regex means “find the previous symbol zero or one times but never more than once”.

*** If you can’t remember something you read three paragraphs ago you may want to consider seeing a doctor about your short term memory problems.

**** On second thought, maybe we should have a response pattern specifically for plain “Why?”. Let’s see if you can figure out the regex for that before I officially add it to the bot.

When Perl != Perl

It just occurred to me that before I go any further I should probably mention that when I say I’m using “Perl” I mean Perl 5. More specifically, Perl 5 version 14 subversion 2 (5.14.2).

This is important because there is a major project called Perl 6 in the works that will change so many features of Perl that it could really be considered a new language instead of an upgrade. This means that Perl 5 code probably won’t work with a Perl 6 system.

So if you’re reading this in a Perl 6 dominated future be warned that you’ll also need Perl 5 if you want to follow along with my sample code. Or you could just rewrite all the sample code in Perl 6 as you read along.

Starting The Chatbot With generateResponse

We’re finally finished with all the design work, tests and background knowledge needed to really start the programming portion of this Let’s Program. So let’s get started!

The core of our system is going to be a function called “generateResponse”. It will be given strings representing user input and then generate a response based off of DELPHI’s pattern matching rules. It will then return this response to whatever piece of code called the “generateResponse” function in the first place.

Last post, as part of our test driven development, we created an empty “generateResponse” function for the testing software to talk to. Today’s goal is to fill that function in.

The Basics Of A Perl Function

One of the more unusual aspects of writing Perl functions is that you don’t have to explicitly list the arguments that will be passed to the function. Instead you are given the freedom to pass as many arguments as you want. Perl then packages those arguments into an array called “@_” for the function to use.

Here’s an example of what I mean:

In C you would define an addition function like this:

int add (int arg1, int arg2)
{
    return arg1 + arg2;
}

But in Perl you would do something more like this:

sub add{
    my $num1 = $_[0];
    my $num2 = $_[1];
    return num1 + num2;
}

or maybe even this

sub add{
    return $_[0] + $_[1];
}

Packaging arguments into an array allows for a lot of really cool tricks, like writing flexible functions that can sort or process unlimited numbers of arguments. But none of that really matters right now because “generateResponse” needs to be passed exactly one input. No flexibility needed (although it’s good to know that’s an option if we change our mind).

To function properly “generateResponse” will also need access to our list of DELPHI input patterns and response patterns. For now I’m just going to include those patterns inside of the function*. This will probably change later on, especially as the list starts getting bigger.

 sub generateResponse{
    my $userInput = $_[0];
    my @chatPatterns;

    $chatPatterns[0][0]=qr/\AIs ([a-zA-Z]+) (.+)\?\z/;
    $chatPatterns[0][1]="Fate indicates that UIF0 is UIF1";

    $chatPatterns[1][0]=qr/\AWhy (.+)\?\z/;
    $chatPatterns[1][1]="Because I said so";

    $chatPatterns[2][0]=qr/.*/;
    $chatPatterns[2][1]="I don't want to talk about that. Please ask me a question";

    #Pattern Processing Code Goes Here
}

Following along so far? We grab the string input argument with $_[0] and set up our array of regular expressions and output patterns. Don’t worry if the regular expressions still look like gibberish, I’ll go over it more in depth next time.

Looping And Comparing

We have the user input and the list of patterns to match. All that’s left to do is compare the input to the patterns until we find a match. Which makes this an obvious place for a foreach loop.

As for printing out the response, we actually already wrote code for that back in the experimental “Should we use Perl?” stage of this project. All it takes is a little modification for that code to fit perfectly.

sub generateResponse{
    my $userInput = $_[0];
    my @chatPatterns;

    $chatPatterns[0][0]=qr/\AIs ([a-zA-Z]+) (.+)\?\z/;
    $chatPatterns[0][1]="Fate indicates that UIF0 is UIF1";

    $chatPatterns[1][0]=qr/\AWhy (.+)\?\z/;
    $chatPatterns[1][1]="Because I said so";

    $chatPatterns[2][0]=qr/.*/;
    $chatPatterns[2][1]="I don't want to talk about that. Please ask me a question";

    foreach my $chatPattern (@chatPatterns){

        if(my @UIF = ($userInput =~ $chatPattern->[0])){
            my $response = $chatPattern->[1];
            for(my $i=0; $i<@UIF; $i++){
                my $find = "UIF$i";
                my $replace = $UIF[$i];
                $response =~ s/$find/$replace/g;
            }
            return $response;
        }
    }
    return "Base Case Failure Error!";
}

Let’s walk through this code really quick. The foreach grabs items out of the test pattern array and stores them in the $chatPattern variable. We then use an if-statement and the regex equals (=~) to try and match the regex pattern inside the first half of $chatPattern against the user’s input inside of $userInput.

If we don’t find a match then we start the loop over, grab the next pattern in the array and try again. If we go through the entire list without ever finding a match we warn the user that something has gone wrong since the pattern matching list should have at least one emergency base case that will match anything.

Things get a bit more complicated when there is a match. First, we pull some User Input Fragments of the input and place them in the @UIF array using some regular expression magic that I’ll cover in the next post. We then look for UIF keywords in our output pattern and replace them with the proper bits of user input. For example, if the output pattern has the string “UIF0” inside of it we replace it with the first entry in the @UIF array. This lets us create chatbot responses that include some of the same words as the user’s input. Once we’re finished searching and substituting we break out of the loop and return the now complete response string.

Breaking out of the loop is very important. Remember that DELPHI is supposed to use prioritized pattern matching to break ties. We can achieve this by placing high priority items near the beginning of our array and then stopping the pattern search the first time we find a match. This means that when an input matches more than one pattern it will naturally match against the highest priority pattern without ever even seeing the lower priority pattern it also would have matched.

The Sweet Smell of Successful Tests

Now that we’ve filled in generateResponse with some guts it’s time to run our tests…

Passed 2 out of 11 tests
Test Failure!!!

Two successes! More specifically the tests we are passing is the “nonsense” test and the basic “Yes/No” question test.

Input: Pumpkin mice word salad

Output: I don’t want to talk about that. Please ask me a question

Input: Is Perl a good choice for this program?

Output: Fate indicates that Perl is a good choice for this program

Anybody that was confused by the User Input Fragments idea during response generation should take a close look at the second test case. When the user asks DELPHI “Is Perl a good choice for this program?” their input gets split into fragments: “Perl” and “a good choice for this program”. We can then glue those into the output pattern of “Fate indicates that UIF0 is UIF1” to create an intelligent response of “Fate indicates that Perl is a good choice for this program”.

Conclusion

Believe it or not I’m now done with almost 50% of this project’s Perl code. Most of the real work on DELPHI will actually come from thinking up all the regular expressions that we’re going to use to pattern-match the user input.

Which is why next post is going to jump into regular expressions, analyzing the three rules I’ve already presented and writing one or two more.

* Bonus points** to anyone who can point out why declaring and populating a predictable array in the middle of a function that’s going to be called dozens or hundreds of times is a bad idea.

** Bonus points are not redeemable for cash or prizes and do not, in fact, exist.