Lisp in Small Parts

Eliza Chatbot

This is a psychotherapist chatbot called Eliza. It's a simple version of the classic artificial intelligence program ELIZA, written by Joseph Weizenbaum between 1964 and 1966 at the MIT Artificial Intelligence Laboratory ^[1], which can reasonably claim to be the mother of all chatbots.

Like a good psychotherapist, Eliza generally attempts to turn around what you say to it, and give it back to you, to sound like it has human understanding but without giving you any real information. The program here has an initial set of rules, but can easily be extended to give Eliza more topics of conversation.

Sample output

Here's some sample output from the Eliza chatbot. The human input is written after the "}" prompt, and the computer's replies are in brackets:

} hello
hello. how can i help ? 
} I hate my computer
what makes you hate your computer ? 
} I wish it would run faster
why would it be better if it would run faster ? 
} I feel I waste a lot of time
do you often feel you waste a lot of time ? 
} most days
you say most days ? 
} yes
tell me more. 
} bye

With the small sample set of rules it will soon start to repeat itself, but you can easily add more rules to extend its repertoire.

The program

The main routine in the program is the pattern matching routine, match, which looks for patterns in the user's input. It takes a pattern string and an input string, and returns t if they match and nil otherwise:

> (match '(all is well) '(all is well))
t

> (match '(all is well) '(all not well))
nil

> (match '(* x chase * y) '(dogs chase cats and sheep))
t

> *bindings*
((X DOGS) (Y CATS AND SHEEP))

Here's the definition of match:

(defun match (pat in)
  (if (null pat) 
      (null in)
    (if (eq (first pat) '*)
        (wildcard pat in)
      (if (eq (first pat) (first in))
          (match (rest pat) (rest in))
        nil))))

The routine match works as follows:

• If the pattern is nil, it succeeeds if the input is nil.
• Otherwise if the first element of the pattern is '* it calls wildcard.
• Otherwise if the first elements of the pattern and input match it calls match on the rest of the pattern and input.
• Otherwise the match fails.

Here's the definition of wildcard to handle the wildcard match:

(defun wildcard (pat in)
  (if (match (rest (rest pat)) in)
      (progn (setf *bindings*
                   (bind (first (rest pat)) nil *bindings*)) t)
   (if (null in)
       nil 
     (if (match pat (rest in))
         (progn (setf *bindings* 
                      (bind (first (rest pat)) (first in) *bindings*)) t)
       nil))))

The routine wildcard calls bind to make the bindings in *bindings*.

(defun bind (var value bindings)
  (if (null bindings) 
      (list (if value (list var value) (list var)))
    (let* ((key (first (first bindings)))
           (values (rest (first bindings)))
           (new (swap value)))
      (if (eq var key)
          (cons (cons key (cons new values)) (rest bindings))
        (cons (first bindings) (bind var new (rest bindings)))))))

The bindings in *bindings* consists of a series of lists, each of which consists of a variable followed by its value. For example:

((X DOGS) (Y CATS AND SHEEP))

This specifies that the value of X is (DOGS) and the value of Y is (CATS AND SHEEP).

The bind routine takes a list of the existing bindings, and returns a new list with value added to the list of values for var:

CL-USER > (bind 'x 'cat '((x dog) (y sheep)))
((X CAT DOG) (Y SHEEP))

The bind routine does one other thing; when it adds a value it calls swap on it to change the viewpoint by the substitution of words from the list of word pairs in *viewpoint*:

(defvar *viewpoint* '((I you) (you I) (me you) (am are) (was were) (my your)))

This gets the matched strings ready to be echoed back by the program. Here's the definition of swap:

(defun swap (value)
  (let* ((a (lookup value *viewpoint*)))
    (if a (first (rest a)) value)))

It uses a routine lookup:

(defun lookup (key alist)
  (if (null alist) nil
    (if (eq (first (first alist)) key)
        (first alist)
      (lookup key (rest alist)))))

The routine subs takes a list and substitutes the values of the variables from *bindings*. So, assuming the value of *bindings* shown above we could write:

CL-USER > (subs '(I think y are chased by x))
(I THINK CATS AND SHEEP ARE CHASED BY DOGS)

Here's subs, which also uses lookup:

(defun subs (list)
  (if (null list)
      nil
    (let* ((a (lookup (first list) *bindings*)))
      (if a
          (append (rest a) (subs (rest list)))
        (cons (first list) (subs (rest list)))))))

The Eliza rules are defined in the variable *rules*:

(defparameter *rules*
  '(((* x hello * y) (hello. how can I help ?))
    ((* x i want * y) (what would it mean if you got y ?) (why do you want y ?))
    ((* x i wish * y) (why would it be better if y ?))
    ((* x i hate * y) (what makes you hate y ?))
    ((* x if * y)
     (do you really think it is likely that y)
     (what do you think about y))
    ((* x no * y) (why not?))
    ((* x i was * y) (why do you say x you were y ?))
    ((* x i feel * y) (do you often feel y ?))
    ((* x i felt * y) (what other feelings do you have?))
    ((* x) (you say x ?) (tell me more.))))

Each rule consists of:

A pattern: for example:

(* x i want * y)

A list of one or more responses: for example:

(what would it mean if you got y ?)
(why do you want y ?)

The program finds the first rule that matches, and then chooses one of the responses at random, using the routine random-elt:

(defun random-elt (list)
  (nth (random (length list)) list))

Finally, here's the program that runs Eliza:

(defun eliza ()
  (loop
   (princ "} ")
   (let* ((line (read-line))
          (input (read-from-string (concatenate 'string "(" line ")"))))
     (when (string= line "bye") (return))
     (setq *bindings* nil)
     (format t "~{~(~a ~)~}~%"
             (dolist (r *rules*)
               (when (match (first r) input)
                 (return 
                  (subs (random-elt (rest r))))))))))

It loops around, repeatedly doing the following:

• Read the user's input line.
• Convert it into a list by adding brackets to it and using procedure we haven't mentioned before, read-from-string.
• Clear the bindings in *bindings*.
• Find the first rule in *rules* that matches.
• Substitute the values from *bindings* into a randomly-selected reply.
• Print the reply using format.

The format pattern we are using is:

"~{~(~a ~)~}~%"

This consists of the following components:

• ~{ ... ~} prints each element in a list.
• ~( ... ~) converts upper-case letters to lower-case.
• ~a prints the element.
• ~% prints a newline.

Run the whole program it by typing:

(eliza)

Here's the whole Eliza program in a single file: Eliza Chatbot Listing.

1. ^ ELIZA on Wikipedia.