ELIZA in C++

Introduction

ELIZA was a chatterbot program developed by Joseph Weizenbaum at MIT Artificial Intelligence Laboratory in the 1960s. Although very simple in design, Weizenbaum was dismayed to find that people who talked to ELIZA often believed that the program actually understood them, and his secretary even asked to be left alone with ELIZA so that she could have a real conversation.

The original program was written in a variant of LISP, but was later translated to other languages, and became very popular with he rise of personal computers when it appeared in books of BASIC games, which was where I first saw it. This post contains an implementation of the program in C++.

How it works

ELIZA’s operation is based on pattern matching and the selection of ready-made responses. The program has a list of patterns to match with the user input, and for each pattern there are a number of response templates. Below are some examples:

    el.responds_to("Can you (.*)")
        .with("Don't you believe that I can %1%?")
        .with("You want me to be able to %1%?");

    el.responds_to("Can I ([^\\?]*)\\??")
        .with("Perhaps you don't want to %1%.")
        .with("Do you want to be able to %1%?")
        .with("If you could %1%, would you?");

    el.responds_to("You are (.*)")
        .with("Why do you think I am %1%?")
        .with("Does it please you to think that I'm %1%?")
        .with("Perhaps you would like be %1%.")
        .with("Do you sometimes wish you were %1%?");

    el.responds_to("I don'?t (.*)")
        .with("Don't you really %1%?")
        .with("Why don't you %1%?")
        .with("Do you wish to be able to %1%?");

As C++ isn’t very good with data literals I have used some proxy class magic to make a fluent syntax for defining the patterns and response templates.

The response templates contain placeholders for expansion (the %1% symbols) and these are filled in using the text captured by the pattern.

The whole algorithm for processing the input and generating the output requires just two small functions, which are shown below:

std::string eliza::translate(const std::string& input) const
{
    std::vector<std::string> words;
    boost::split(words, input, boost::is_any_of(" \t"));
    for (auto& word : words) {
        boost::algorithm::to_lower(word);
        for (auto& trans : translations_) {
            if (trans.first == word) {
                word = trans.second;
                break;
            }
        }
    }
    return boost::algorithm::join(words, " ");
}

std::string eliza::respond(const std::string& input) const
{
    std::string response;
    for (auto& ex : exchanges_) {
        boost::smatch m;
        if (boost::regex_search(input, m, ex.prompt_)) {
            response = ex.responses_[rand() % ex.responses_.size()];
            if (m.size() > 1 && response.find("%1%") != response.npos) {
                std::string translation = translate(std::string(m[1].first, m[1].second));
                boost::trim_right_if(translation, boost::is_punct());
                response = boost::str(boost::format(response) % translation);
            }
            break;
        }
    }
    return response;
}

The respond() function first goes through the list of patterns and finds the first one that matches. From that it randomly selects a response template. If the pattern captured some text, and the response has placeholders for replacement, these are filled in. Before using the captured text, it is passed to translate(), which converts pronouns, changing "I" to "you" "my" to "your" and so on. It is this translation, and the incorporation of captured phrases from the input in the response, that makes ELIZA surprisingly convincing.

There is a lot of scope for improving the program, not only by adding more patterns and responses, but also by making the parsing more sophisticated (for example collapsing similar inputs to a canonical form), adding a more capable, recursive templating system, and possibly connecting the program to external data sources.

The Code

This is the header file:

#ifndef ELIZA_HPP
#define ELIZA_HPP

#include <string>
#include <vector>
#include <boost/regex.hpp>

namespace MB
{

struct exchange
{
    boost::regex prompt_;
    std::vector<std::string> responses_;
    explicit exchange(const std::string& prompt)
      : prompt_(prompt, boost::regex::icase)
    {
    }
};

class exchange_builder;

class eliza
{
    std::string name_;
    std::vector<exchange> exchanges_;
    std::vector<std::pair<std::string, std::string> > translations_;
public:
    eliza(const std::string& name = "Eliza")
      : name_(name)
    {
        add_translations();
    }
    const std::string& name() const
    {
        return name_;
    }
    exchange_builder responds_to(const std::string& prompt);
    void add_exchange(const exchange& ex)
    {
        exchanges_.push_back(ex);
    }
    std::string respond(const std::string& input) const;
private:
    void add_translations();
    std::string translate(const std::string& input) const;
};

class exchange_builder
{
    friend eliza;
    eliza& eliza_;
    exchange exchange_;

    exchange_builder(eliza& el, const std::string& prompt)
      : eliza_(el), exchange_(prompt)
    {
    }

public:
    ~exchange_builder()
    {
        eliza_.add_exchange(exchange_);
    }

    exchange_builder& with(const std::string& response)
    {
        exchange_.responses_.push_back(response);
        return *this;
    }
};

}; // namespace MB

#endif // ELIZA_HPP

The implementation:

#include <cstdlib>

#include <boost/algorithm/string.hpp>
#include <boost/format.hpp>

#include "eliza.hpp"

using namespace MB;

exchange_builder eliza::responds_to(const std::string& prompt)
{
    return exchange_builder(*this, prompt);
}

void eliza::add_translations()
{
    translations_.push_back(std::make_pair("am", "are"));
    translations_.push_back(std::make_pair("was", "were"));
    translations_.push_back(std::make_pair("i" , "you"));
    translations_.push_back(std::make_pair("i'd", "you would"));
    translations_.push_back(std::make_pair("you'd", "I would"));
    translations_.push_back(std::make_pair("you're", "I am"));
    translations_.push_back(std::make_pair("i've", "you have"));
    translations_.push_back(std::make_pair("i'll", "you will"));
    translations_.push_back(std::make_pair("i'm", "you are"));
    translations_.push_back(std::make_pair("my", "your"));
    translations_.push_back(std::make_pair("are", "am"));
    translations_.push_back(std::make_pair("you've", "I have"));
    translations_.push_back(std::make_pair("you'll", "I will"));
    translations_.push_back(std::make_pair("your", "my"));
    translations_.push_back(std::make_pair("yours", "mine"));
    translations_.push_back(std::make_pair("you", "me"));
    translations_.push_back(std::make_pair("me", "you"));
    translations_.push_back(std::make_pair("myself", "yourself"));
    translations_.push_back(std::make_pair("yourself", "myself"));

}

std::string eliza::translate(const std::string& input) const
{
    std::vector<std::string> words;
    boost::split(words, input, boost::is_any_of(" \t"));
    for (auto& word : words) {
        boost::algorithm::to_lower(word);
        for (auto& trans : translations_) {
            if (trans.first == word) {
                word = trans.second;
                break;
            }
        }
    }
    return boost::algorithm::join(words, " ");
}

std::string eliza::respond(const std::string& input) const
{
    std::string response;
    for (auto& ex : exchanges_) {
        boost::smatch m;
        if (boost::regex_search(input, m, ex.prompt_)) {
            response = ex.responses_[rand() % ex.responses_.size()];
            if (m.size() > 1 && response.find("%1%") != response.npos) {
                std::string translation = translate(std::string(m[1].first, m[1].second));
                boost::trim_right_if(translation, boost::is_punct());
                response = boost::str(boost::format(response) % translation);
            }
            break;
        }
    }
    return response;
}

An example program, which includes the initialisation of ELIZA with a default set of patterns and responses:

#include <iostream>

#include "eliza.hpp"

static void add_responses(MB::eliza& el);

int main()
{
    MB::eliza el;

    add_responses(el);

    std::cout << "Hello. I'm " << el.name() << ". How are you feeling today?\n";
    std::string input;
    while (std::getline(std::cin, input) && input != "quit") {
        std::cout << el.respond(input) << "\n";
    }
}

static void add_responses(MB::eliza& el)
{
    el.responds_to("Can you (.*)")
        .with("Don't you believe that I can %1%?")
        .with("You want me to be able to %1%?");

    el.responds_to("Can I ([^\\?]*)\\??")
        .with("Perhaps you don't want to %1%.")
        .with("Do you want to be able to %1%?")
        .with("If you could %1%, would you?");

    el.responds_to("You are (.*)")
        .with("Why do you think I am %1%?")
        .with("Does it please you to think that I'm %1%?")
        .with("Perhaps you would like be %1%.")
        .with("Do you sometimes wish you were %1%?");

    el.responds_to("I don'?t (.*)")
        .with("Don't you really %1%?")
        .with("Why don't you %1%?")
        .with("Do you wish to be able to %1%?");

    el.responds_to("I feel (.*)")
        .with("Does it trouble you to feel %1%?")
        .with("Do you often feel %1%?")
        .with("Do you enjoy feeling %?%")
        .with("When do you usually feel %1%?")
        .with("When you feel %1%, what do you do?");

    el.responds_to("Why don'?t you ([^\\?]*)\\??")
        .with("Do you really believe I don't %1%?")
        .with("Perhaps in good time I will %1%.")
        .with("Do you want me to %1%?");

    el.responds_to("Why can'?t I ([^\\?]*)\\??")
        .with("Do you think you should be able to %1%?")
        .with("Why can't you?");

    el.responds_to("Are you ([^\\?]*)\\??")
        .with("Why are you interested in whether I am %1%?")
        .with("Would you prefer it if I were not %1%?")
        .with("Perhaps in your fantasies I am %1%.");

    el.responds_to("I can'?t (.*)")
        .with("How do you know you can't %1%?")
        .with("Have you tried to %1%?")
        .with("Perhaps now you can %1%");

    el.responds_to("I am (.*)")
        .with("Did you come to me because you are %1%?")
        .with("How long have you been %1%?");

    el.responds_to("I'?m (.*)")
        .with("Do you believe it is normal to be %1%?")
        .with("Do you enjoy being %1%?");

    el.responds_to("You (.*)")
        .with("We were discussing you - not me.")
        .with("Oh, I %1%?");

    el.responds_to("I want (.*)")
        .with("What would it mean to you if you got %1%?")
        .with("Why do you want %1%?")
        .with("Suppose you soon got %1%?")
        .with("What if you never got %1%?")
        .with("I sometimes also want %1%");

    el.responds_to("What (.*)")
        .with("Why do you ask?")
        .with("Does that question interest you?")
        .with("What answer would please you the most?")
        .with("What do you think?")
        .with("Are such questions on your mind often?")
        .with("What is it that you really want to know?")
        .with("Have you asked anyone else?")
        .with("Have you asked such questions before?")
        .with("What else comes to mind when you ask that?");

    el.responds_to("Because")
        .with("Is that the real reason?")
        .with("Don't any other reasons come to mind?")
        .with("Does that reason explain anything else?")
        .with("What other reasons might there be?");

    el.responds_to("Sorry")
        .with("There are many times when no apology is needed.")
        .with("What feelings do you have when you apologize?");

    el.responds_to("Dream")
        .with("What does that dream suggest to you?")
        .with("Do you dream often?")
        .with("What persons appear in your dreams?")
        .with("Are you disturbed by your dreams?");

    el.responds_to("^Hello")
        .with("How do you do... Please state your problem.");

    el.responds_to("^Maybe")
        .with("You don't seem quite certain.")
        .with("Why the uncertain tone?")
        .with("Can't you be more positive?")
        .with("You aren't sure?")
        .with("Don't you know?");

    el.responds_to("^No[.!]?$")
        .with("Are you saying that just to be negative?")
        .with("You are being a bit negative.")
        .with("Why not?")
        .with("Are you sure?")
        .with("Why no?");

    el.responds_to("Your (.*)")
        .with("Why are you concerned about my %1%?")
        .with("What about your own %1%?");

    el.responds_to("Always")
        .with("Can you think of a specific example?")
        .with("When?")
        .with("Really, always?");

    el.responds_to("Think (.*)")
        .with("What are you thinking of?")
        .with("Do you really think so?")
        .with("But you are not sure %1%?")
        .with("Do you doubt %1%?");

    el.responds_to("Alike")
        .with("In what way?")
        .with("What resemblance do you see?")
        .with("What does the similarity suggest to you?")
        .with("what other connections do you see?")
        .with("Could there really be some connection?")
        .with("How?");

    el.responds_to("^Yes[.!]?$")
        .with("You seem quite positive.")
        .with("Are you sure?")
        .with("I see.")
        .with("I understand.");

    el.responds_to("Friend")
        .with("Why do you bring up the topic of friends?")
        .with("Do your friends worry you?")
        .with("Do your friends pick on you?")
        .with("Are you sure you have any friends?")
        .with("Do you impose on your friends?")
        .with("Perhaps your love for friends worries you.");

    el.responds_to("Computer")
        .with("Do computers worry you?")
        .with("Are you talking about me in particular?")
        .with("Are you frightened by machines?")
        .with("Why do you mention computers?")
        .with("What do you think machines have to do with your problem?")
        .with("Don't you think computers can help people?")
        .with("What is it about machines that worries you?");

    el.responds_to("(.*)")
        .with("Say, do you have any psychological problems?")
        .with("What does that suggest to you?")
        .with("I see.")
        .with("I'm not sure I understand you fully.")
        .with("Come come elucidate your thoughts.")
        .with("Can you elaborate on that?")
        .with("That is quite interesting.");
}

Finally, here is a makefile:

ALL := eliza
all : $(ALL)
eliza : eliza.cpp eliza.hpp main.cpp
$(CXX) $(CXXFLAGS) -g -std=c++11 eliza.cpp main.cpp -o eliza -lboost_regex
.PHONY : clean
clean :
$(RM) $(ALL)

	

BK-Tree in C++

A BK-tree is an efficient data structure for storing items for which there is some concept of distance between them. A common use is to store words for approximate string matching, using the Levenshtein distance metric. Another use is to store phrases using some measure of semantic distance in order to implement an AI system like a chatterbot.

This is a simple implementation of a BK-tree in C++.

#ifndef BK_TREE_HPP
#define BK_TREE_HPP

#include <map>
#include <memory>
#include <type_traits>

namespace MB
{

template <typename T, typename Unit, typename Metric> class bktree;

namespace detail
{

template <typename T, typename Unit, typename Metric>
class bktree_node
{
    friend class bktree<T, Unit, Metric>;
	typedef bktree_node<T, Unit, Metric> node_type;
    typedef std::unique_ptr<node_type> node_ptr_type;
	
	T value_;
	std::map<Unit, node_ptr_type> children_;

	bktree_node(const T &value)
		: value_(value)
    {
    }

	bool insert(const T& value, const Metric& distance)
    {
        bool inserted = false;
		Unit dist = distance(value, this->value_);
		if (dist > 0) {
            // Not already here 
            auto it = children_.find(dist);
            if (it == children_.end()) {
                // Attach a new edge here
                children_.insert(std::make_pair(dist, node_ptr_type(new node_type(value))));
                inserted = true;
            }
            else {
                // Follow existing edge
                inserted = it->second->insert(value, distance);
            }
            return inserted;
        }
	}

    template <class OutputIt>
	OutputIt find(const T &value, const Unit& limit, const Metric& distance, OutputIt it) const
    {
		Unit dist = distance(value, this->value_);
		if (dist <= limit) {
            // Found one
			*it++ = std::make_pair(this->value_, dist);
        }
		for (auto iter = children_.begin(); iter != children_.end(); ++iter) {
            // Follow edges between dist + limit and dist - limit
			if (dist - limit <= iter->first && dist + limit >= iter->first) {
				iter->second->find(value, limit, distance, it);
            }
		}
        return it;
	}
};

}; // namespace detail

template <typename T, typename Unit, typename Metric>
class bktree
{
private:
	typedef typename detail::bktree_node<T, Unit, Metric>::node_type node_type;
    typedef typename detail::bktree_node<T, Unit, Metric>::node_ptr_type node_ptr_type;

    node_ptr_type head_;
    const Metric distance_;
	size_t size_;

public:
	bktree(const Metric& distance = Metric())
        : head_(nullptr), distance_(distance), size_(0L)
    {
        static_assert(std::is_integral<Unit>::value, "Integral unit type required.");
    }

	bool insert(const T &value)
    {
        bool inserted = false;
		if (head_ == nullptr) {
            // Inserting the first value
			head_ = node_ptr_type(new node_type(value));
			size_ = 1;
            inserted = true;
		}
        else if (head_->insert(value, distance_)) {
            ++size_;
            inserted = true;
        }
        return inserted;
	}

    template <class OutputIt>
	OutputIt find(const T& value, const Unit& limit, OutputIt it) const
    {
		return head_->find(value, limit, distance_, it);
	}

	size_t size() const
    {
		return size_;
	}
};

}; // namespace MB

#endif // BK_TREE_HPP

Here is an example program. It loads a dictionary from a file, and then prompts the user to enter words and a limit on distance, and it will return all words within that Levenshtein distance of the word entered. I used this dictionary with it:

#include <fstream>
#include <iostream>
#include <string>

#include "bk_tree.hpp"
#include "levenshtein_distance.hpp"

int main()
{
    const char filename[] = "dictionary.txt";
    std::ifstream ifs(filename);
    if (!ifs) {
        std::cerr << "Couldn't open " << filename << " for reading\n";
        return 1;
    }
    MB::bktree<std::string, int, levenshtein_distance> tree;
    std::string word;
    while (ifs >> word) {
        tree.insert(word);
    }
    std::cout << "Inserted " << tree.size() << " words\n";
    std::vector<std::pair<std::string, int> > results;
    do {
        std::cout << "Enter a word (\"quit!\" to quit)> ";
        std::cin >> word;
        if (word != "quit!") {
            int limit;
            std::cout << "Enter a limit> ";
            std::cin >> limit;
            tree.find(word, limit, std::back_inserter(results));
            for (auto it = results.begin(); it != results.end(); ++it) {
                std::cout << it->first << "(distance " << it->second << ")\n";
            }
            results.clear();
        }
    }  while (word != "quit!");
}

Example run:

$ ./dictionary
Inserted 127142 words
Enter a word ("quit!" to quit)> mispelling
Enter a limit> 2
spelling(distance 2)
misdealing(distance 2)
impelling(distance 2)
miscalling(distance 2)
mispenning(distance 2)
misrelying(distance 2)
respelling(distance 2)
dispelling(distance 1)
misbilling(distance 2)
misspelling(distance 1)
misspellings(distance 2)
Enter a word ("quit!" to quit)> quit!
$

Here is an implementation of the Levenshtein distance:

#include <string>
#include <vector>
#include <algorithm>

namespace MB
{

namespace detail
{

template <typename T>
T min3(const T& a, const T& b, const T& c)
{
   return std::min(std::min(a, b), c);
}

}; // namespace detail

class levenshtein_distance 
{
    mutable std::vector<std::vector<unsigned int> > matrix_;

public:
    explicit levenshtein_distance(size_t initial_size = 8)
        : matrix_(initial_size, std::vector<unsigned int>(initial_size))
    {
    }

    unsigned int operator()(const std::string& s, const std::string& t) const
    {
        const size_t m = s.size();
        const size_t n = t.size();
        // The distance between a string and the empty string is the string's length
        if (m == 0) {
            return n;
        }
        if (n == 0) {
            return m;
        }
        // Size the matrix as necessary
        if (matrix_.size() < m + 1) {
            matrix_.resize(m + 1, matrix_[0]);
        }
        if (matrix_[0].size() < n + 1) {
            for (auto& mat : matrix_) {
                mat.resize(n + 1);
            }
        }
        // The top row and left column are prefixes that can be reached by
        // insertions and deletions alone
        unsigned int i, j;
        for (i = 1;  i <= m; ++i) {
            matrix_[i][0] = i;
        }
        for (j = 1; j <= n; ++j) {
            matrix_[0][j] = j;
        }
        // Fill in the rest of the matrix
        for (j = 1; j <= n; ++j) {
            for (i = 1; i <= m; ++i) {
                unsigned int substitution_cost = s[i - 1] == t[j - 1] ? 0 : 1;
                matrix_[i][j] =
                    detail::min3(matrix_[i - 1][j] + 1,         // Deletion
                    matrix_[i][j - 1] + 1,                      // Insertion
                    matrix_[i - 1][j - 1] + substitution_cost); // Substitution
            }
        }
        return matrix_[m][n];
    }
};

}; // namespace MB