It seems like everywhere I go these days I’m talking to a bot. Now don’t get me wrong, I’m all for technology that keeps me from having to interact with actual humans. And truth be told, they’re getting pretty good — talking to Alexa has just become something I do without thinking about it. But it super-annoys me when I visit some random website and their chatbot pops up in my face pretending to be a real person (I’m looking at you, oreilly.com).

I think it’s good for us to know when we’re talking to a computer and when we’re not. And that’s not only some squishy ethical thing — it just works better. I have different expectations talking to a bot than I do to a human, and I’m more than happy to adjust my speaking pattern to increase the chances of success. For example, I know that “shuffle” and “album” are Alexa keywords for music, so I ask her to “shuffle album Cake and Pie” (which works) rather than “please play Cake and Pie in random order” (sad Alexa noise).

And you know what? This is fine! Speech recognition aside (amazing stuff there), we use specialized and restricted dialects for specialized purposes all the time, even between humans. Curlers yell “clean” or “hurry” and the sweepers immediately know what they mean. I tell the guy at the lumber yard that I put “16 feet of 2×12 treated” into my car and he knows what to charge me. This kind of jargon removes ambiguity from communication, and that’s a big plus when you’re trying to get something done together.

So what’s my point? There’s an interesting dichotomy here, because the hype around chatbots is all about artificial intelligence, but the reality is that it’s much more about the creation of purpose-built “little languages.” Those are way more interesting to me, so that’s what I’m going to dig into today.

Little Languages

Jon Bently wrote an incredible pair of books in Programming Pearls and More Programming Pearls. Both are essential reading for anyone who cares about software, even though some (not all!) of the specific technology is showing its age. They’re entertaining too, thanks to the way he weaves together anecdotes and concrete code. What I’m saying here is, buy the books.

Anyways, I first encountered “little languages” in More Programming Pearls, but you can read the original article about them online here. Bentley was part of the UNIX crowd at Bell Labs and loved (as all good programmers do) the idea of pipelines — how programs can work together to do increasingly complex things (really just top-down-design in different clothes, but since pretty much all problems converge back to TDD that’s cool by me). In the article, he demonstrates the concept using picture generators that used to be (maybe still are?) commonly used for technical papers. For example, the chem language allows folks to concisely describe and depict chemical structures. Here’s LSD:

.cstart
B:  benzene pointing right
F:  flatring5 pointing left put N at 5 double 3,4 with .V1 at B.V2
    H below F.N
R:  ring pointing right with .V4 at B.V6
    front bond right from R.V6 ; H
R:  ring pointing right with .V2 at R.V6 put N at 1 double 3,4
    bond right from R.N ; CH3
    back bond -60 from R.V5 ; H
    bond up from R.V5 ; CO
    bond right ; N(C2H5)2
.cend

You can run this yourself on most Linux systems; if it’s not there already, use your package manager to install groff (groff is the GNU version of the typesetting app troff). Save the code above as lsd.chem and use the command:

cat lsd.chem | chem | pic | groff -Tpdf > lsd.pdf

This has always stuck with me because it’s such a beautiful specialized-to-generic pipeline:

• chem lets you easily specify chemical structures, generating input for
• pic, which creates any kind of picture, generating input for
• groff, which formats any kind of document for presentation.

Adventure

Bentley’s little languages are primarily static, used as Input to an interpreter. But the concept applies equally well to conversations, and we’ve been having conversations with computers for a long time. Exhibit A is Colossal Cave Adventure, the granddaddy of “interactive fiction.” If you had access to a computer in the seventies or eighties there’s a 100% chance you played it or one of its descendants like Zork or the early Roberta Williams titles. Interactive fiction today generally uses point-and-click, but you can very much still feel the connection to their early, text-based ancestors.

In Adventure, the computer acts as a dungeon master, describing your location and acting on your instructions (“go north”, “take lamp”, “fight dragon,” and so on). Your goal is to explore a network of underground caves (based on the real Mammoth Cave), accumulating gold and treasure along the way. You can give it a try yourself in the browser — I recommend keeping track of where you are by building up a map on paper along the way.

There are a million versions of the game. The one I first played was written by Don Woods as a modification of the original by Will Crowther. The FORTRAN code for the original Crowther version is on github (of course it is). The “little language” implemented there is shockingly expressive given its tiny vocabulary of 192 words.

• In the GETIN subroutine, an input line is broken into one or two words: a VERB and an optional OBJECT. Each is truncated to five characters for processing, but extra characters are retained for display purposes.
• Starting at label 2020, the words are matched to entries in the 192-word vocabulary table which are implicitly associated with classes (motion/action/special for verbs, normal/treasure for objects) based on their assigned number.
• The verb is then dispatched to the correct handler. Most action verbs are handled using special-case logic, but motion verbs run through a state machine defined in the motion table. If you think about the cave as a graph, each row in the motion table is an edge that describes the verbs and game state required to move the player from the location in the first column to the location in the second.

Of course there’s a lot more to it than that. If you want to really dig into the code, there is a well-commented copy of the Woods version at the Interactive Fiction Archive, downloadable as a zipped tarball. You’ll still have to brush up on your FORTRAN to really get it, but who doesn’t love a good DO/CONTINUE loop packed with GOTO statements?

If you’ve played the game, it’s impossible not to be impressed with how immersive it is. With nothing more than VERB/OBJECT pairs, you can explore a world, solve puzzles, and even kill a dragon (with what? your bare hands?). I hope you get so sucked into the cave that you don’t come back to this post for a month.

Late breaking news: turns out this post is pretty timely, because Ken and Roberta Williams just announced that they are rebooting Colossal Cave for a new generation of folks … WOOT!

ELIZA the DOCTOR

Rogerian psychology is serious stuff. In (very) short, the goal is help patients understand themselves through a self-driven, internal dialogue. The therapist is there to provide safety and empathy, and to reflect back the observations and themes they are hearing. It has helped millions of people. But it’s also the easy butt of jokes, because on the surface it seems that the therapist isn’t really doing anything:

• How many Rogerian therapists does it take to change a lightbulb?
• I hear you wanting to know how many Rogerian therapists it takes to change a lightbulb.

Way back in 1965, Joseph Weizenbaum created ELIZA and DOCTOR, an engine and script respectively that do a remarkably good job of emulating a conversation with that satirized therapist. If you’ve never heard of ELIZA, you definitely should click on over to this site and say hello to her; she’s actually pretty impressive, especially when you consider that there is absolutely zero contextual “understanding” under the covers.

ELIZA’s little language is quite different from Adventure’s. Her goal is to transform input into responses that will seem relevant and appropriate to a human observer, especially one primed to expect a Rogerian conversation. The original source is available, but it’s written in MAD-SLIP and that one is even too arcane for me. Instead I’ll refer to Weizenbaum’s original paper in the ACM which is pretty great and totally worth reading.

The language is primarily defined by rules for recognizing input patterns and transforming them into responses. For example, suppose we receive the input “why do you hate me” and want to respond with “Why do you think I hate you.”

1. The decomposition rule (0 you 0 me) is matched against the input. It’s basically a proto-regex. The number 0 means “match any 0 or more words,” while the alphabetic strings must match exactly. If the pattern matches, each section of the rule is “assigned” text from the input. In this case it would match as ((why do) (you) (hate) (me)).
2. An associated recomposition rule (why do you think I 3 you) is used as a template to generate the response. Numbers are replaced with the Nth input grouping generated during decomposition (3 = “hate” in this example) to create the desired response: why do you think I hate you?

Note that even this simple pair of rules provides significant flexibility in our ability to respond to arbitrary input:

• Why do you hate me / Why do you think I hate you
• It seems that you no longer care about me / Why do you think I no longer care about you
• You love me / Why do you think I love you
• Apparently you are bananas for me / Why do you think I are bananas for you

Whoops! That last one uncovered a flaw in our engine — the second person singular “are” should have been transformed into the first person singular “am.” ELIZA uses additional rules called transforms to fix this up. There are also a bunch of other interesting details that make her respond in a mostly-believable way; a few examples:

• Decomposition rules can have multiple possible recomposition rules; ELIZA selects from the list randomly but with minimal repetition.
• Decomposition rules are associated with keywords that have a ranked order. In this way, more specific or interesting responses can be preferred over simpler ones. (This keyword-to-rule association was created primarily as a performance benefit to account for the limited processing power of the day, but the ranking is a nice side benefit.)
• Fallback rules keep the conversation moving when no decomposition rules match successfully.
• A “memory” feature keeps a short stack of important phrases used in the conversation that can be inserted to enhance a sense of continuity.

The actual syntax used to express the language is pretty hairy — basically a nest of parenthesized lists, just as you’d expect from a LISP variant. Here’s a short snip from DOCTOR that I’ve indented to be a tiny bit more readable; the full script is included at the end of the paper:

(CANT = CAN'T)
(WONT = WON'T)
(REMEMBER 5 
	((0 YOU REMEMBER 0) 
		(DO YOU OFTEN THINK OF 4)
		(DOES THINKING OF 4 BRING ANYTHING ELSE TO MIND)
		(WHAT ELSE OO YOU REMEMBER)
		(WHY DO YOU REMEMBER 4 JUST NOW)
		(WHAT IN THE PRESENT SITUATION REMINDS YOU OF 4)
		(WHAT IS THE CONNECTION BETWEEN ME AND 4))

It turns out that Charles Hayden reimplemented Eliza in Java and dramatically improved the little language. But aesthetics aside, just like Adventure, the ELIZA script language packs a great deal of smarts using a quite restricted syntax. Truth be told, I’d definitely choose to talk to her than to most of the marketing bots that get up in my face on the web every day.

Today’s Conversation Models

Modern little languages certainly look fancier than these early examples. If you’ve been reading this blog for awhile, you may recall my experience writing an Alexa “skill” to manage stuff in my house. I won’t repeat all the details here, but in short an Alexa “Interaction Model” include the following elements:

• Intents: things that the user wants to do (e.g. turn on a particular configuration of lights).
• Utterances: one or more template phrases that capture an intent (e.g., “turn family room lights on”).
• Slots: placeholders in an utterance that capture meaningful parameters in the user’s request (e.g., “turn ROOM_SLOT ACTION_SLOT”).

Azure provides basically the same functionality in its Conversational Language Understanding suite (this is a new version of what used to be LUIS; it’s hard to keep up).

Feeling a little Deja Vu? Intents are basically ELIZA keywords. Utterances are decomposition rules. Slots are the numeric placeholders used in recomposition. It’s actually kind of startling just how similar they are. Of course there’s a ton of advanced processing now that notably improves the matching process — it would be wrong to minimize the advances there. But let’s give the old guys some credit, hey?

Hunt the Wumpus (by Text!)

When I started writing this article, the plan was to dig go pretty deep into the details of implementing a “bot” using the Microsoft Bot Framework. But as I look up from the keyboard, I’m two thousand words in already and haven’t even started that … so maybe better to save it for next time. But I’d hate to leave you without at least a little something concrete, so let’s at least introduce the WumpusBot and give it a spin.

Hunt the Wumpus is actually the very first computer game I ever played, over a printing teletype connected from my elementary school to a central PDP-11 somewhere. The goal is to explore a series of connected rooms, trying to shoot the “Wumpus” before he eats you or you fall into a bottomless pit. Along the way, bats may pick you up and move you randomly to another room. In the original game, you had magic “crooked arrows” that could travel between many rooms, but I chose to implement the simpler version described here where you can just shoot into any adjacent room.

Anyways, take out your trusty smartphone and text “play” to 706-943-3865 to give it a try for real. WumpusBot will reply with some instructions to get you started — its language is little indeed, pretty much just “move” and “shoot.”

The game logic is in Wumpus.java, and the bot innards are all in this directory. The cool thing about the Bot Framework is that it can multiplex your logic across a ton of “channels” — web chat, SMS, Teams, Slack, Facebook, and a bunch more. WumpusBot consists of:

• Game logic in an Azure Function that uses the Bot Framework SDK to accept and respond to messages.
• A Twilio SMS account which provides the phone number and gets texts onto and off of the mobile network.
• An Azure Bot registration that coordinates the linkage between them.

Anyways, for now just enjoy the game — we’ll get into the details and the usual Microsoft devex bashing next time. Pro tip: whenever you feel a draft or smell something rotten, just backtrack and approach from a different room … unless a bat does you wrong, you’ll get him every time.