Zhao Wei

Given the following rule, we want to generate a sentence based on that phrase-structure 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...

(defun sentence ()    (append (noun-phrase) (verb-phrase)))
(defun noun-phrase () (append (Article) (Noun)))
(defun verb-phrase () (append (Verb) (noun-phrase)))
(defun Article ()     (one-of '(the a)))
(defun Noun ()        (one-of '(man ball woman table)))
(defun Verb ()        (one-of '(hit took saw liked)))

In this approach, we create functions accordingto the grammar rules.
In traditional solution, the rules are expressed based on many lisp conventions, such as: case, if, and their order in the evaluation (we use functions’s call to express those rules.).

1. Concentrate on how to make it easy to express rule directly using lisp.
   
2. Worry later about how they will be processed.
   

Consider the rules

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...

We use the following lisp code represent their rules:

(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 grammar used by generate.  Initially, this is
  *simple-grammar*, but we can switch to other grammars.")

(defun rule-lhs (rule)
  "The left hand side of a rule."
  (first rule))

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

(defun rewrites (category)
  "Return a list of the possible rewrites for this category."
  (rule-rhs (assoc category *grammar*)))

(defun generate (phrase)
  "Generate a random sentence or phrase"
  (cond ((listp phrase)
         (mappend #'generate phrase))
        ((rewrites phrase)
         (generate (random-elt (rewrites phrase))))
        (t (list phrase)))) 

(defun mappend (fn lst)
  (apply #'append (mapcar fn lst)))

• append
  

• elt
  

  (elt '(1 2 3 4 5) 2)
  

• random, we use it to implement one-of and random-element
  

  (defun one-of (lst)
    (list (random-element lst)))
  
  (defun random-element (lst)
    (elt lst (random (length lst))))
  

• assoc
  

  (assoc '1 '((1 -> first) (2 -> second) (3 -> third)))
  

• By convention, defvar is used to define var and defparameter is used to define constant. They are all used to define global variable.
  
• To define local variable, use let.
  
• By comparing traditional and data-driven development
  
  • The traditional approach construct different functions and compose them to express the rule directly. It becomes hard to maintain once the rule become complex. Because we are doing straightforward mapping of the problem description into lisp code.
    
  • The rule bsed approach (data-driven) on the other hand:
    
    • First, focus on how to express rules as natual as possible with lisp code.
      
    • Then, define a layer of tools to help to operate on those rules.
      In this step, we are actually writing a simple interpreter for notation introduced from first step.
      
    • Finally, with those tools, we define our final function according to the rules. (These rules are not the primitive rules; they are the rules expressed in lisp code from first step.)
      
  • The idea behind second approach is to work with the problem as much as possible in its own terms, and to minimize the part of the solution that is written directly in Lisp.
    
  • The extra advantages of representing information in declarative form (rules or facts) rather than lisp function is that it can be easier to use the information for multiple purpose. This is called one-data/multiple-program.