Channels ▼

Jocelyn Paine

Dr. Dobb's Bloggers

Jess Johnson's Joke Generator in Lisp

December 13, 2009

In the comments to Mark Colvin's feature Recalling communism through its black jokes for The Punch, someone has posted this Cold War joke:

An American and a Russian were debating who had the better country.
The American says, "My country is so free that I can stand outside the White House and criticise the President of the USA".
The Russian says, "So what? I can stand outside the Kremlin and criticise the President of the USA".
It's a joke that would be an ideal subject for the discipline of computational humour. How can we define the semantics of jokes; and how can we write programs that generate jokes?

I call this joke a "twisted analogy" or a "near-analogy". What is the deviation from a perfect analogy, I ask, that makes us laugh? Because the following version is about as funny as a postal strike:

An American and a Briton were debating who had the better country.
The American says, "My country is so free that I can stand outside the White House and criticise the President of the USA".
The Briton says, "So what? I can stand outside the Houses of Parliament and criticise the Prime Minister of Britain".

My gut feeling — as regular readers will know — is that category theory will be invaluable in understanding such structure. For anyone willing to find out about the necessary mathematics (or to treat it as scenery and assume it will make sense if they ever need it to), there's a thread about category-theoretic formulations of analogy, in the n-Category Café blog at Re: Ulam on Banach; Re: A Categorical Manifesto.

Also useful, I am certain, will be research into analogical reasoning. The Association for the Advancement of Artificial Intelligence give some fairly recent links on their Analogy page; Wikipedia has some in the External References section of its Analogy page; and a Google search for computational analogical reasoning will turn up more.

Some of that research is about abstract models of analogical reasoning; some is about building programs that do analogical reasoning. Building programs is good, because you learn such a lot when trying to explain imperfectly understood ideas to a computer. A good example from the history of AI is James Meehan's 1977 program Tale-Spin, which he describes in TALE-SPIN, An Interactive Program that Writes Stories. The program is a story generator, not a joke generator or an analogical reasoner, but it illustrates my point.

Meehan's paper shows a number of stories generated by Tale-Spin. Here is one piece of sample output, after Tale-Spin's user created two characters and their environment, then gave them each a problem to solve: thirst.

ONCE UPON A TIME GEORGE ANT LIVED NEAR A PATCH OF GROUND. THERE WAS A NEST IN AN ASH TREE. WILMA BIRD LIVED IN THE NEST. THERE WAS SOME WATER IN A RIVER. WILMA KNEW THAT THE WATER WAS IN THE RIVER. GEORGE KNEW THAT THE WATER WAS IN THE RIVER. ONE DAY WlLMA WAS VERY THIRSTY. WILMA WANTED TO GET NEAR SOME wATtR. WILMA FLEW FROM HER NEST ACROSS A MEADOW THROUGH A VALLEY TO THE RIVER. WILMA DRANK THE WATER. WlLMA WASN'T THIRSTY ANY MORE.

GEORGE WAS VERY THIRSTY. GEORGE WANTED TO GET NEAR SOME WATER. GEORGE WALKED FROM HIS PATCH OF GROUND ACROSS THE MEADOW THROUGH THE VALLEY TO A RIVER BANK. GEORGE FELL INTO THE WATER. GEORGE WANTED TO GET NEAR THE VALLEY. GEORGE COULDN'l GET NEAR THE VALLEY. GEORGE WANTED TO GET NEAR THE MEADOW. GEORGE COULDN'T GET NEAR THE MEADOW. WILMA WANTED GEORGE TO GET NEAR THE MEADOW. WILMA WANTED TO GET NEAR GEORGE. WILMA GRABBED GEURGE WITH HER CLAW. WlLMA TOOK GEORGE FROM THE RIVER THROUGH THE VALLEY TO THE MEADOW. GEORGE WAS DEVOTED TO WlLMA. GEORGE OWED EVERYTHING TO WlLMA. WILMA LET GO OF GEORGE. GEORGE FELL TO THE MEADOW. THE END.

Meehan was experimenting to discover which kinds of knowledge the computer would need in order to generate such stories. Sometimes, he missed something essential, and Tale-Spin generated "mis-spun tales", such as this variant on Aesop's The Fox and the Crow:

Once upon a time there was a dishonest fox and a vain crow. One day the crow was sitting in his tree, holding a piece of cheese in his mouth. He noticed that he was holding the piece of cheese. He became hungry, and swallowed the cheese. The fox walked over to the crow. The end.

What went wrong is that the fox was going to trick the crow out of the cheese. But when he got there, there was no cheese, because the crow had "noticed" the cheese in his mouth, and Tale-Spin had inferred that he'd be hungry so would eat it.

By the way, some of Meehan's mis-spun tales are funny in the way that "idiot" punchlines are funny. They ignore vital pieces of common-sense knowledge. Consider this joke, which I've copied from Wikipedia's An Englishman, an Irishman and a Scotsman page:

An Englishman, a Scotsman, and an Irishman are all builders working on a bridge. The Englishman opens his lunch-box and says, "If I get one more tuna sandwich, I'm going to jump off this bridge." The Scotsman opens his lunch box and says, "If I get one more ham sandwich, I'm going to jump off this bridge." The Irishman then says, "If I get one more egg sandwich, I'm going to jump off this bridge." The next day, all three get the same lunch, all three jump off the bridge, and all three die. At their funeral, the Englishman's wife says, "If only I'd known he didn't like tuna." The Scotsman's wife says, "If only I'd known he didn't like ham." The Irishman's wife says, "I don't understand it. He made his own sandwiches."
Working out how to make Tale-Spin generate funny mis-spun tales would be great fun, and would teach us a lot about humour.

Having explained why exploring AI by building programs is useful, let me introduce Jess Johnson's joke generator. It generates jokes of the form "What do you get when you cross X with Y?", is written in Lisp, and is described very nicely at How to Write Original Jokes (Or Have A Computer Do It For You).

Jess's description includes a link to the source code (in a file called joke.lisp ). Jess walks through the code, explaining how the generator stores vocabulary and relations between words. I won't attempt to improve on this description: instead, I'm going to show you how to run the generator. It seems to need Franz Inc.'s Allegro Common Lisp. If you don't know Lisp, this may be daunting to install and use, so I decided instructions would be useful.

By the way, Lisp programmers might note that a comment by "Claus" following Jess's article suggests one reason for needing Allegro Lisp is that the generator calls MAKE-HASH-TABLE with STRING-EQUAL as a :TEST argument, whereas the Lisp standard allows only EQ, EQL, EQUAL and EQUALP. Jess replies to this that if anyone wants to port the generator to CLISP, it would be very welcome.

Let me now explain how to install and use Allegro Lisp. First, although Franz charge for most of their Lisp implementations, they do offer one free one, the Allegro CL Free Express Edition. To download it, go to www.franz.com/downloads/, and then to the "Download now" link. Tick the licence-agreement box and fill in the survey form, then press Submit.

This brings you to a page with downloads for various operating systems. I downloaded the Windows one. To install it, I just double-clicked the download, and accepted the choices offered by its install wizard, except that I installed into c:\acl81-express\ rather than the directory it suggested, acl81-express under "c:\Program Files". This is because I'd been warned when installing another program that spaces in the name "Program Files" can cause problems. They certainly make it less convenient to command-line one's way to the files.

After installing, I found the menu option "Allegro Common Lisp 8.1 Free Express Edition" on my Windows All Programs menu, and selected the option "Allegro Common Lisp" from it. (There are also options for documentation, technical support, licence stuff, and so on.)

This brought up a window for the Allegro interactive development environment, containing an editor window called "untitled", and a debug window. It also popped up an "Upgrade to a Supported Lisp" nag window, with Upgrade and Continue buttons. Clicking Continue removed the nag window.

When I start Allegro this way now, I also get a "Startup Action" pop-up, with options for opening an existing project, starting a new one, or doing neither. Projects aren't needed to run the joke generator, so I press "Startup Action"'s Cancel button. I can't remember whether this pop-up appeared the first time I ran Allegro.

Let's now test Allegro Lisp. Its debug window contains an Allegro welcome message, licence info and version numbers, and at its end, the prompt "CG-USER(1):". Typing 1 at this prompt and pressing Enter displays the answer 1 followed by a new prompt, "CG-USER(2):". This is the Lisp evaluator telling me that 1 evaluates to 1, which seems a good beginning.

As another little test, type

(+ 1 2)
at this new prompt, and press Enter. The answer 3 will appear, followed by a new prompt. The evaluator is telling me that 1+2 equals 3. I'll mention that in Lisp, we have to code function calls as lists. Their first element is the name of the function (or, more generally, an expression that evaluates to a function). The other elements are the function's arguments. If you don't know Lisp, and just want to run the joke generator and admire what comes out, this will explain why I'll soon ask you to type:
(generate)

If your Allegro worked as above, you are nearly ready to run the joke generator. So download it from the source code, and save as a plain-text file joke.lisp .

Next, I suggest editing it to change the lines at the top to:

(setq *debug* nil)
(setq *test-know* nil)
The first line sets a global variable that controls the generator's debug output. If this is "t" (Lisp for TRUE), the generator will swamp you with diagnostics. Making it "nil" (Lisp for FALSE) prevents this. The second line tells the generator whether to use the full knowledge base or a small test version. The latter is uninteresting data about parrots, and didn't seem to generate any jokes. When the variable is nil, the generator uses the full knowledge base.

You can edit the file in the Allegro text editor, but if you don't know Allegro, using your customary editor is easier. Next, you must compile it. From Allegro's File menu, choose Compile. This will display a file dialogue, from which you should open the joke.lisp you've just edited. When I did this, Allegro displayed another file dialogue, which asked me to save a file called joke.fasl . This is the compiled version of joke.lisp : "fasl" stands for "fast loading".

When I did this, I got lots of warning messages in Allegro's debug window, and also a "Compilation Messages for joke.lisp" pop-up. These don't matter: press OK on the pop-up to dismiss it.

Having created a fasl file, now load it into Allegro. Choose Load on the File menu, and select joke.fasl from the resulting file dialogue. This will give a "Fast loading C:\dobbs\joke.fasl" message in the debug window.

Now in the debug window, press Enter to get a prompt. You should see one such as "CG-USER(1):". And finally, type:

(generate)
followed by Enter. And then will appear your jokes:
WHAT DO YOU GET WHEN YOU CROSS JAM WITH A TROUT?
jellyfish

WHAT DO YOU GET WHEN YOU CROSS A BAD COW WITH A CANNED HAT?
banned cat

WHAT DO YOU GET WHEN YOU CROSS A COW WITH A LEMON?
sour milk

WHAT DO YOU GET WHEN YOU CROSS A CRAZY COW WITH A BANNED PARROT?
canned carrot

WHAT DO YOU GET WHEN YOU CROSS A PIG WITH A NINJA?
pork chops

Do Americans call "jam" "jelly"? To me they're different things, but it would explain the first joke. Anyway, the generator takes a long time to work through all its jokes, but once it has finished, you can copy and paste them from the debug window. You can interrupt it by selecting Interrupt from Allegro's Run menu. This will pop up a "Restart for Listener 1" window, which offers four choices of what to do next. The first choice, "return from break", will resume the generator if you then press the "Invoke Selected Restart" button. The second choice, "Return to Top Level (an "abort" restart)", will quit the generator and give a new debug-window prompt if you then press the "Invoke Selected Restart" button. The other two probably aren't useful.

If you want to run the generator again while still in Allegro, type:

(generate)
and Enter once more. If you leave Allegro, and later decide to restart it and rerun, you won't need to recompile the generator, but can just Load joke.fasl again and run that.

Naturally, I hope some readers will feel inspired to try modifying the generator. A good start would be to make it produce a version of this joke more apposite to 2009:

WHAT DO YOU GET WHEN YOU CROSS A BANK WITH A SKUNK?
dollars and scents
I don't know whether the generator can do "What do you get when you cross X with X?"

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video