Second Lisp Assignment: Random sentences
Dave Matuszek

Your assignment is to write a Lisp program to generate random sentences.

You should have a function named GEN that takes an integer argument N, and does two things:

  1. Prints out your name.
  2. Prints out N randomly generated sentences, one per line.

In Lisp it is better to write lots of small functions than a few big ones. For example, GEN could print out your name and call a second function to do the rest of the work. This second function might recur on N (to get N sentences), call a third function to generate and return one sentence, and print out that sentence. Typically, you would put all your functions in the same .lsp file.

You can generate sentences using a simple context-free grammar. Here are typical abbreviations for a grammar:

Abbreviation Stands for Examples
S sentence the boy sees the big red hairy red troll
N noun boy, ring, hobbit, troll, moon, telescope
V verb hits, runs, sees
ADJ adjective big, red, hairy
ADV adverb quickly, quietly,
DET determiner a, an, the, this, that, each, every
PRON pronoun he, she, it
PREP preposition in, on, around, about
CONJ conjunction and, but
NP noun phrase the boy, the man in the moon
VP verb phrase runs, hits the tree, sees the moon with the telescope
PP prepositional phrase in the moon, with the telescope

In a context-free grammar, these abbreviations would be the nonterminals (things that need to be expanded), and the English words that they expand into are the terminals (because you stop there and don't expand them any further). When you write your program, please start with these abbreviations, but feel free to ignore some of them and/or add new ones of your own. Please use your own vocabulary (words), not just the ones above.

Here are some very simple rules (the vertical bar, |, means "or"--choose just one of the alternatives). Again, start with these, but feel free to add/modify/delete rules as you choose.

Here are some things you need to pay attention to:

Here are some things you should not worry about:

Here are some functions you might find useful (the ones without a defun are built-in functions):

(defun outof (m n)
   (< (random n) m))		 Returns true m times out of n; for example, (outof 1 10) will return true one time in ten (and NIL the rest of the time). If m >= n, outof always returns true.
(defun choose (L)
   (nth (random (length L)) L))		 Returns one randomly chosen element of the list. For example, (choose '(a (b c) (d e) f) ) might return (d e).
(prin1 S) Print the S-expression S, without a newline after it. Like System.out.print(S) in Java.
(print S) Print the S-expression S, followed by a newline. Like System.out.println(S) in Java.
(terpri) Print a newline. Like System.out.println() in Java.

I have gotten questions about how to put the rules into Lisp. One simple way is to define them as functions: for example,

       (defun pron () '(he she it))
    (defun np () '((det n) (det n pp) (det adjlist n)))

Another way is to use setq to make them "constants," for example:

     (setq adj '(big red hairy))
     (setq vp '(v (v np)))

The first way, you would call them as functions; for example, (pron) evaluates to (he she it). The second way, you would use them as variables, for example, adj evaluates to (big red hairy). Either way will work fine. There are two special forms that are especially convenient in this program:

(eval S) Evaluates the expression S. For example, (eval '(car '(a b c))) evaluates the quoted expression (car '(a b c)), giving a. This function is especially useful if you stored your rules using setq.
(apply fun args) Calls the function fun with the argument list args. For example, (apply 'cons '(a (b c))) gives (a b c). This function is especially useful if you stored your rules as functions.

Example of using eval with setq Example of using apply with defun
> (setq adj '(big strong hairy))
(big strong hairy)
Now suppose x has the value 'adj
> x
adj
Then
> (eval x)
(big strong hairy)

(defun n () '(boy girl gorilla))
n
Now suppose y has the value 'n
> y
n
Then
> (apply y ())
(boy girl gorilla)

If you are having trouble getting started, here are some suggestions.

You will need to distinguish between nonterminals (S, NP, ...) from terminals (BOY, EACH, ...). One way to make this distinction is to write a function that, given an atom argument, tests whether that atom is in a list of nonterminals. (It's easier to make a list of nonterminals than a list of terminals, because (1) there are fewer nonterminals, and (2) you are more likely to want to add/change nonterminals (words) than terminals (grammatical categories).

Start with the list '(S), because you want to generate sentences. Write a recursive function (I called mine expand) that finds a rule for each nonterminal and replaces (expands) it. Some rules have only a single alternative, so use that alternative; for example PP --> PREP NP gives you no choice. Some rules have multiple alternatives, such as V --> V | V NP, so use my choose or some similar function to pick one alternative. (By the way, if you give my choose function a list containing only one thing, it picks that one thing, so you don't need to make a special case.)

If you look at the rules above, S --> NP VP says to replace S with NP VP, so change your list from (S) to (NP VP). Next, NP is still a nonterminal, NP --> DET N | DET N PP | DET ADJLIST N, so you need to choose any one of these alternatives, say, DET N PP, and change your list from (NP VP) to (DET N PP VP). Continue in this fashion until you get a list composed entirely of terminals.

Here's a possible sequence (terminals are shown in blue):

Start with: (S)
Use the rule S --> NP VP (NP VP)
Use the rule NP --> DET N PP (DET N PP VP)
Use the rule DET --> EACH (EACH N PP VP)
Use the rule N --> BOY (EACH BOY PP VP)
Use the rule PP --> PREP NP (EACH BOY PREP NP VP)
Use the rule PREP --> IN (EACH BOY IN NP VP)
Use the rule NP --> DET N (EACH BOY IN DET N VP)
Continue... ...
...until you have only terminals left: (EACH BOY IN EVERY RING SEES)

Basically, every time you have a nonterminal, you need to call a recursive function to turn it into a list of terminals. Putting all these terminals together gives you the final list.

Due date: Thursday, January 24, by midnight. Please submit one .lsp file containing all your functions via Blackboard.