Generative Grammar

[BIOS]

I've been working on generative Grammar function i found in a textbook. I'm having a problem understanding the exact nature of the recursion in the final function however. Below is all the code involved. I understand function individually but when it is defined in the final function i am slightly confused by the structure. Can anyone here explain?

Code: Select all

(defun mappend (fn the-list)
 "Apply fn to each element of list and append the results."
 (apply #'append (mapcar fn the-list)))

(defun random-elt (choices)
  "Choose an element from a list at random." 
  (elt choices (random (length choices))))

(defun rule-rhs (rule)
  "the right hand side of a rule."
(rest rule))

(defun rewrites (category)
  "return list of possible rewrites for that category."
(rule-rhs (assoc category *grammar*)))


(defparameter *simple-grammar* 
  '((sentence (noun-phrase verb-phrase))
  (noun-phrase (Article Noun)) 
    (verb-phrase (Verb noun-phrase)) 
    (Article the a) 
    (Noun man ball woman table) 
    (Verb hit took saw liked))
"A grammar for a trivial subset of English.")

(defvar *grammar* *simple-grammar* 
"The grammarused by generate. Initially,this is
 *simple-grammar*, but we can switch to other grammars.")

This is the final function which i'm having trouble understanding:

Code: Select all

(defun generate (phrase)
 "Generate a random sentence or phrase"
 (if (listp phrase)
     (mappend #'generate phrase)
     (let ((choices (rewrites phrase)))
       (if (null choices) 
	   (list phrase)
	   (generate (random-elt choices))))))

If someone could explain how the evaluation/recursion works here that would be great

BIOS

[Jasper]

Recursion can be understood by understanding what the function is supposed to do, and then applying that to the use of the function itself to verify that it actually does what it is supposed to do. That would seem circular. (hmm why does it work.. overlooking something)

If the argument is a symbol it is what sort-of-thing or a specific-thing to say. Things that are sort-of-things to say have lists what of those things are in the grammar assoc-list, and if it is in there(As REWRITES looks it up) it picks one of those randomly, and inputs it back to the random generator to again see if it is a sort-of-thing or a specific-thing to say.

If the argument is a list, it is taken to be a sequence of sort-of-things and/or specific-things to say, it do them in order.

All the elements in the assoc list are essentially things to input into the generator. For instance (generate 'noun) is one of man, ball, woman, table, others like (generate 'verb-phrase) use (generate '(verb noun-phrase)) which are then from those lists. (list (generate '(the a)) (generate (...)) and (generate 'sentence) will put together.

Kindah fun to mess around a little with more grammar, everything beyond SENTENCE generates pretty much nonsense though. Are you learning theory behind it, or is it just something you encountered in a book? Anyway, if you didn't already suggest you see if you can make it use adjectives? (Just add a little adjective and adjective-phrase in the grammar, and add to noun-phrase: (article adjective-phrase).

[nuntius]

This is the final function which i'm having trouble understanding:

Code: Select all

(defun generate (phrase)
 "Generate a random sentence or phrase"
 (if (listp phrase)
     (mappend #'generate phrase)
     (let ((choices (rewrites phrase)))
       (if (null choices) 
	   (list phrase)
	   (generate (random-elt choices))))))

In English,
If the phrase is a list, then call generate on each item and return the resulting list.
If there are no choices, then return the phrase unchanged.
If there are choices, then randomly pick one and return (generate choice).

[gugamilare]

Wow! This function is so cool!

Code: Select all

CL-USER> (generate 'sentence)
(A TABLE SAW THE WOMAN)
CL-USER> (generate (list 'sentence 'and 'verb-phrase))
(THE WOMAN TOOK THE BALL AND TOOK THE WOMAN)
CL-USER> (generate (list 'sentence 'and 'verb-phrase))
(THE TABLE LIKED THE TABLE AND HIT A TABLE)

Mostly meaningless sentences, though

Ok, let me try to explain what this function does. For example, consider the call

Code: Select all

(generate 'sentence)

The function generate will see that 'sentence is a symbol, therefore not a list. So it will call (rewrite 'sentence), which will lookup the word sentence in the variable *gramar*. It will find this:

Code: Select all

(sentence (noun-phrase verb-phrase))

The variable choices will then be a list with only one element, which is also a list:

Code: Select all

'((noun-phrase verb-phrase))

The only element of that list, which is '(noun-phrase verb-phrase), is then taken and generate is called with it as argument:

Code: Select all

(generate '(noun-phrase verb-phrase))

The argument is now a list, so generate will call

Code: Select all

(mappend #'generate '(noun-phrase verb-phrase))

which is equivalent to

Code: Select all

(append (generate 'noun-phrase) (generate 'verb-phrase))

and so on. When generate finds a word, for instance:

Code: Select all

(generate 'woman)

then it will do nothing but return 'woman, since it is not a term defined in *grammar*.

Hope that helps!

[Jasper]

nuntius sure said that much better than me.

Code: Select all

(defparameter *grammar*
  '((sentence (affirmative |,| noun verb (pre-adjective adjective)))
    (affirmative yes indeed)
    (noun this that it generative-grammar)
    (verb is)
    (pre-adjective very most nil)
    (adjective cool awesome interesting)))

Hmm this might be very useful for both expressing yourself geekily, and an auto-circle-jerk bot for mockery.

PS mappend == mapcan

[BIOS]

Thanks for all the replies. Glad to see how active the forum is

@Jaspar: yes i'm learning the theory behind it and am interested in learning more about AI. Thought starting with these "simple" AI programs would be a good way.

@Nuntius: A very succinct explanation!

@Gugamilare: Thanks for doing it line by line. It really helps. I almost have it! I'm still unsure of the recursion. Here is how i currently misunderstand the function in action:

Using your example:

Code: Select all

(generate 'sentence)

We make a call to the function generate which performs the following conditional execution:

Code: Select all

(if (listp phrase)
     (mappend #'generate phrase)
     (let ((choices (rewrites phrase)))

'If' tests if phrase is a list. In this case it isn't so we move to 'let' setting the variable 'choices' to the outcome of the rewrite function for 'sentence. Here's where i don't follow what the program does next. I understand at as having to go to the next conditional 'if' as this is part of the 'then' clause of the original 'if' conditional. So it takes us here:

Code: Select all

 (if (null choices) 
	   (list phrase)
	   (generate (random-elt choices))))))

So we test:

Code: Select all

(null (noun-phrase verb-phrase)

This will prove to be non nil so we move to:

Code: Select all

(generate (random-elt choices)

I'm obviously misunderstanding the recursion here

[nuntius]

Read up on the implementation of function calls and stack frames. Recursion is nothing fancy; normally function f() calls function g(); recursion occurs when f() calls f(). Each call gets a separate chunk of memory for its local variables; these chunks are known as frames, and they are stored in a stack for efficiency. So called "tail-call optimization" eliminates the extra stack frame when the caller has no more work to do; the callee simply updates the caller's return address.

Maybe TRACE would help?

Code: Select all

CL-USER> (trace generate)
(GENERATE)
CL-USER> (generate 'sentence)
  0: (GENERATE SENTENCE)
    1: (GENERATE (NOUN-PHRASE VERB-PHRASE))
      2: (GENERATE NOUN-PHRASE)
        3: (GENERATE (ARTICLE NOUN))
          4: (GENERATE ARTICLE)
            5: (GENERATE A)
            5: GENERATE returned (A)
          4: GENERATE returned (A)
          4: (GENERATE NOUN)
            5: (GENERATE TABLE)
            5: GENERATE returned (TABLE)
          4: GENERATE returned (TABLE)
        3: GENERATE returned (A TABLE)
      2: GENERATE returned (A TABLE)
      2: (GENERATE VERB-PHRASE)
        3: (GENERATE (VERB NOUN-PHRASE))
          4: (GENERATE VERB)
            5: (GENERATE SAW)
            5: GENERATE returned (SAW)
          4: GENERATE returned (SAW)
          4: (GENERATE NOUN-PHRASE)
            5: (GENERATE (ARTICLE NOUN))
              6: (GENERATE ARTICLE)
                7: (GENERATE THE)
                7: GENERATE returned (THE)
              6: GENERATE returned (THE)
              6: (GENERATE NOUN)
                7: (GENERATE WOMAN)
                7: GENERATE returned (WOMAN)
              6: GENERATE returned (WOMAN)
            5: GENERATE returned (THE WOMAN)
          4: GENERATE returned (THE WOMAN)
        3: GENERATE returned (SAW THE WOMAN)
      2: GENERATE returned (SAW THE WOMAN)
    1: GENERATE returned (A TABLE SAW THE WOMAN)
  0: GENERATE returned (A TABLE SAW THE WOMAN)
(A TABLE SAW THE WOMAN)

[BIOS]

Cheers Nuntius. This is my first experience of Functions calling themselves. Trying to get my head around it. Can you recommend any reading on this kind of theory?

BIOS

[nuntius]

The Wikipedia article looks pretty good.

Recursive functions are just like normal functions except for one caveat. Be careful that the recursion will stop, otherwise you have an "infinite loop" of function calls (which usually fail by overflowing the stack).

[gugamilare]

[...]

'If' tests if phrase is a list. In this case it isn't so we move to 'let' setting the variable 'choices' to the outcome of the rewrite function for 'sentence. Here's where i don't follow what the program does next. I understand at as having to go to the next conditional 'if' as this is part of the 'then' clause of the original 'if' conditional. So it takes us here:

Code: Select all

 (if (null choices) 
	   (list phrase)
	   (generate (random-elt choices))))))

So we test:

Code: Select all

(null (noun-phrase verb-phrase))

Actually, this is not right. At this point, the variable choices is bound to ((noun-phrase verb-phrase)), not (noun-phrase verb-phrase), since this is what is returned by (rewrites 'sentence). Note the extra parenthesis in the variable *simple-grammar*, compared to, e.g., Article or Noun.

This will prove to be non nil so we move to:

Code: Select all

(generate (random-elt choices))

I'm obviously misunderstanding the recursion here

The call (random-elt choices) has only one possible outcome, because choices has only one element, which happens to be the list (noun-phrase verb-phrase).