Lisp 2 rules and natural language
Download
Report
Transcript Lisp 2 rules and natural language
LISP – (LISt Processing)
1. Parenthesized prefix notation: (+ 2 4)
2. Expressions can be nested: (- (+ 2 3 4 5) (* 2 5))
3. Evaluation rule:
apply function to value of arguments.
4. Symbolic computation: other types
Quote
Primitive: numbers, characters, strings, symbols.
Compound: lists.
append
(append '(a b) '(c d)) --> (a b c d)
Quote: block the evaluation of the following expression.
'(a b) --> (a b)
(a b) --> error: a undefined function.
5. Self-evaluating types: numbers, characters, strings.
6. Symbols as variables - not case sensitive.
VARIABLES
1. Define new objects in terms of others + name them.
2. (setf p '(a b)) --> (a b)
p --> (a b)
3. Symbols also used to name functions.
Quote
SPECIAL FORMS:
1. Forms not evaluated according to the evaluation rule.
2. Special forms:
defun, defparameter, setf, let, case, if, function, quote.
LISTS
1. Primitive aggregating type.
2. Primitive functions: first, second, ..., length, last. append, cons, list.
DEFINING NEW FUNCTIONS:
1. (defun <name> (<parameters>)
"doc"
<body>)
defun
(defun last-name (name)
"Select last name from a name
represented
as a list."
(first (last name)))
(last-name '(john r vandamme)) --> vandamme
(last-name '(john quirk MD))
--> MD
2. Importance of abstraction.
(defun first-name (name) (first name))
USING FUNCTIONS:
1. (setf names '((john x ford) (peter p rabbit) (fabianna f wayne)))
(mapcar #'last-name names) --> (ford rabbit wayne)
#' from name of function to function object.
mapcar primitive.
2. (defparameter *titles*
'(Mr Mrs Miss Madam Ms Sir Dr Admiral Major General))
defparameter
(defun first-name (name)
"Select first name from a list representing a name."
(if (member (first name) *titles*)
(first-name (rest name))
(first name)))
(if <test> <then-part> <else-part>) ;; explanation of if
;; example of first-name
(first-name '(Madam Major General Paula Jones)) --> Paula
3. Trace functions
Omits all titles from
the name list, returns
the first name.
HIGHER ORDER FUNCTIONS
1. Functions as first-class objects: can be manipulated, created, modified by running code.
2.Apply: (apply #'+ '(1 2 3 4)) --> 10
3. Funcall: (funcall #'+ 1 2) --> 3
(funcall #'+ '(1 2)) -->
error (1 2) is not a number.
4. Function constructor: lambda.
(lambda (parameter ...) body...):
non atomic name of a function.
((lambda (x) (+ x 2)) 4) --> 6
(funcall #'(lambda (x) (* x 2)) 4) --> 8
***Can create functions at run time.***
apply
funcall
lambda
OTHER DATA TYPES
1. Strings: (length "abc") --> 3
2. Many number types.
length
Basic terminology
• Atoms: word-like indivisible objects which can be numbers
or symbols.
• Lists: sentence-like objects formed from atoms or other lists,
and enclosed in parentheses.
• S-expressions: compositions of atoms and lists.
• Procedures: step by step specifications how to do
something.
• Primitives: procedures supplied by the LISP itself
Example: (+ 5 6)
• User-defined procedures: procedures introduced by the
programmer.
Example: (students 'anna)
• Program: a collection of procedures working together.
S-expressions
• An s-expression can have other s-expressions nested in it. Examples:
(+ (* 5 7) ( / 2 4))
(This (is a dog) (or a cat))
• Expressions can be interpreted both, procedurally and declaratively.
• If interpreted procedurally, an expression provides a direction for
doing something. Such an expression is called a form, and its first
element is the name of a procedure to be used to produce the value.
• The process of computing the value of an expression is called
evaluation.
• If interpreted declaratively, expressions represent data.
Data and procedures have the same syntax.
Evaluation of atoms
• The value of a number is the number itself.
Example: 5 ==> 5
• The value of a string is the string itself.
Example: “Nice day” ==> “Nice day”
•
•
•
•
The value of the symbol T is T (true).
The value of the symbol NIL is NIL (false).
The symbol NIL and the empty list ( ) are the same thing.
Variables are names of memory locations. The contents stored in a given
memory cell is the value of the variable serving as a name of this
location.
Example: Let x be a variable, and 5 be the contents of the memory cell called x.
Then, the value of x is 5.
Numbers
•
•
•
•
Integers: 179, 45
Ratio: 5/7, 7/9
Floating point: 5.2, 7.9
Examples:
* (/ 25 5)
5
* (/ 46 9)
46/9
; do not divide evenly
* (float (/ 46 9))
5.111111
* (round (/ 46 9))
5
; the nearest integer
1/9
; the remainder
More numeric primitives
* (- 6)
-6
* (- -6)
6
* (max 5 7 2)
7
* (min 5 7 2)
2
* (sqrt (* (+ 1 3) (* 2 2)))
4.0
* (+ (round (/ 22 7)) (round (/ 7 3)))
5
* (+ 2 2.5)
4.5
* (expt 3 6)
729
* (sqrt 81)
9.0
* (sqrt 82)
9.055386
* (abs 6)
6
* (abs -6)
6
LISP EVALUATION RULE
1. Every expression is either a list or an atom.
2. Every list to be evaluated is either a special form or a function
application.
3. A special form expression is a list whose first element is a special form operator
and is evaluated according to the special rule of that operator.
4. A function application is evaluated by first evaluating the arguments (the rest of
the list) and then finding the function named by the first element of the list and
applying it to the list of evaluated arguments.
5. Every atom is either a symbol or a non-symbol.
6. A symbol evaluates to the most recent value assigned to the variable.
7. A non-symbol atom evaluates to itself.
WHAT MAKES LISP DIFFERENT
1. Built-in support for Lists.
2. Automatic memory management.
3. Dynamic typing.
4. First-class functions.
5. Uniform syntax.
6. Extensibility
Why LISP?
• Especially designed for symbol manipulation.
• Provides built-in support for lists (“everything is a list..”)
• Automatic storage management (no need to keep track of
memory allocation).
• Interactive environment, which allows programs to be
developed step by step. That is, if a change is to be
introduced, only changed functions need to be
recompiled.
Everything's a List!
• Data
(a b c)
• Functions
(defun plus (x y)
(+ x y))
• Simple syntax:
(function-name arg1 arg2 …)
LISP is Interpreted and interactive
• Interpreted
• Interactive
USER(1): 12
12
USER(2): (+ 12 3)
15
USER(3): (setf Almost-age 31)
31
USER(4): Almost-age
31
USER(5): 'Almost-age
ALMOST-AGE
USER(6):
Lisp is Symbolic
• Why do we care about symbols?
• Understand human cognition with a language like
symbolic processing
Physical Symbol System Hypothesis
"A physical symbol system has the necessary and
sufficient means for general intelligent action."
(Newell & Simon 1976)
• Physical symbol system
• Set of entities called symbols - physical patterns that can
occur as components
• Expressions (or symbol structures) built of symbols
Lisp is Dynamic
• Functions are first-class objects
• Pass functions as arguments to other functions
USER(1): (+ 1 2 3)
6
USER(2): (apply #'+ '(1 2 3))
6
Funcall and Lambda – dynamic
• Create functions on the fly
USER(1): (funcall #'(lambda (x y)
(+ x y))
17 14)
31
• Lisp contains itself: eval
Name Calling
• Lisp remembers function names separately from variable names
USER(22): (defun add (x y) (+ x y))
ADD
USER(23): (setf add 9)
9
USER(24): add
9
USER(25): #'add
#<Interpreted Function ADD>
Problems with solutions:
1. Write a function (power 3 2) = 3^2 = 9
2. Write a function that counts the number of atoms in an expression.
(count-atoms '(a (b) c)) --> 3
3. (count-anywhere 'a '(a ((a) b) a)) --> 3
4. (dot-product '(10 20) '(3 4)) --> 10x3 + 20x4 = 110
5. Write a function (flatten '(a (b) () ((c)))) --> (a b c)
which removes all levels of parenthesis and returns a flat list of
atoms.
6. Write a function (remove-dups '(a 1 1 a b 2 b)) --> (a 1 b 2)
which removes all duplicate atoms from a flat list.
(Note: there is a built-in remove-duplicates in Common Lisp, do not
use it).
Solutions 1-3
(defun power (a b)
"compute a^b - (power 3 2) ==> 9"
(if (= b 0) 1
(* a (power a (- b 1)))))
Write a function (power 3 2) = 3^2 = 9
Write a function that counts the number of
atoms in an expression.
(count-atoms '(a (b) c)) --> 3
(defun count-atoms (exp)
"count atoms in expresion - (count-atoms '(a (b) c)) ==> 3"
(cond ((null exp) 0)
((atom exp) 1)
(t (+ (count-atoms (first exp)) (count-atoms (rest exp))))))
(count-anywhere 'a '(a ((a) b) a)) --> 3
(defun count-anywhere (a exp)
"count performances of a in expresion (count-anywhere 'a '(a ((a) b) (a))) ==> 3"
(cond ((null exp) 0)
((atom exp) (if (eq a exp) 1 0))
(t (+ (count-anywhere a (first exp))
(count-anywhere a (rest exp))))))
Solutions
Write a function (flatten '(a (b) () ((c)))) -> (a b c)
which removes all levels of parenthesis
and returns a flat list of
atoms.
(defun flatten (exp)
"removes all levels of paranthesis and returns flat list
of atoms
(flatten '(a (b) () ((c)))) ==> (a b c)"
(cond ((null exp) nil)
((atom exp) (list exp))
(t (append (flatten (first exp))
(flatten (rest exp))))))
EXAMPLE
A tree structure of
nodes for data base
28
Example of interaction with the program that will be shown:
You type
(questions)
Is it a ANIMAL? (yes)
Program responds
Is it a MAMMAL? (yes)
I give up - what is it? (whale)
How it works?
You have some item in
mind, program asks,
you respond.
#S( NODE :NAME WHALE :YES NIL :NO NIL )
(questions)
Program
learned this.
Now it knows
that whale is a
mammal.
Is it a ANIMAL? (no)
Is it a VEGETABLE? (no)
Is it a MINERAL? (no)
I give up - what is it? (fruit)
#S( NODE :NAME FRUIT :YES NIL :NO NIL )
(questions)
Is it a ANIMAL? (no)
Is it a VEGETABLE? (no)
You confirm that the program guessed correctly
Is it a MINERAL? (no)
Is it a FRUIT? (it)
AHA!
Program learned this. Now it knows that
it is a fruit
29
e.g. 3: A tree structure of nodes for data base
A data base called *db*. The data base is organized into a tree structure of nodes.
Each node has three fields:
1.
the name of the object it represents,
2.
a node to go to if the answer is yes,
3.
and a node for when the answer is no.
We traverse the nodes until we either get an “it” reply or have to give up.
“It” means that we found a correct answer in our questioning.
(defstruct node
name
(yes nil)
animal
yes
no
(no nil))
mammal
NODE
(defvar *db*
vegetable
no
(make-node :name 'animal
node-name
node-yes
node-yes
node-no
mineral
:yes (make-node :name 'mammal)
:no (make-node
:name 'vegetable
:no (make-node :name
'mineral))))
*DB*
(defun give-up ()
(format t "~&I give up - what is it?")
(make-node :name (first (read))))
GIVE-UP
Returns name of function as a value
Makes new node in
the tree
(defun questions (&optional (node *db*))
(format t "~&Is it a ~a? " (node-name node))
(case (first (read))
((y yes) (if (not (null (node-yes node)))
Calls itself recursively
(questions (node-yes node))
Sets structure
(setf (node-yes node) (give-up))))
((n no) (if (not (null (node-no node)))
(questions (node-no node))
(setf (node-no node) (give-up))))
(it 'aha!)
(t (format t "reply with YES, NO, or IT if I have guessed it.")
(questions node))))
QUESTIONS
31
Execution results:
(questions)
Is it a ANIMAL? (yes)
Is it a MAMMAL? (yes)
I give up - what is it? (whale)
#S( NODE :NAME WHALE :YES NIL :NO NIL )
(questions)
Is it a ANIMAL? (no)
Is it a VEGETABLE? (no)
Is it a MINERAL? (no)
animal
no
yes
mammal
vegetable
yes
whale
no
yes
I give up - what is it? (fruit)
fruit
#S( NODE :NAME FRUIT :YES NIL :NO NIL )
(questions)
Is it a ANIMAL? (no)
mineral
IT!
Is it a VEGETABLE? (no)
Is it a MINERAL? (no)
Is it a FRUIT? (it)
AHA!
32
EXAMPLE:
A simple lisp program of
generating English sentences
33
e.g. 4: A simple lisp program of generating English sentences
(defun random-elt (choices)
"Choose an element from a list at random"
(elt choices (random (length choices))))
RANDOM-ELT
(defun one-of (set)
"pick one element of set and make a list of it"
(list (random-elt set)))
ONE-OF
(defun Verb ()
(one-of '(hit took saw liked)))
VERB
(defun Noun ()
(one-of '(man ball woman table)))
NOUN
(defun Article ()
(one-of '(the a)))
ARTICLE
34
(defun verb-phrase ()
(append (Verb) (noun-phrase) ))
VERB-PHRASE
(defun noun-phrase ()
(append (Article) (Noun)))
NOUN-PHRASE
(defun sentence ()
(append (noun-phrase ) (verb-phrase)))
SENTENCE
(sentence)
(THE MAN SAW THE TABLE)
(sentence)
(A TABLE SAW THE BALL)
(sentence)
(A MAN SAW THE BALL)
Similarly, you can create “sentences” in
any kind of “structured” set, which is a
language:
1. Motions
2. Facial gestures
3. Pictures drawn by a robot
4. Dances
5. Music composed
35
EXAMPLE:
A rule-based solution of
generating English sentences
36
e.g. 5: A rule-based solution of generating English sentences
(defparameter *simple-grammar*
'((sentence -> (noun-phrase verb-phrase))
(noun-phrase -> (ar Noun))
(verb-phrase -> (Verb noun-phrase))
(ar -> the a)
(Noun -> man ball woman table)
(Verb -> hit took saw liked))
"A grammar for a trivial subset of English.")
*SIMPLE-GRAMMAR*
(defvar *grammar* *simple-grammar*
"The grammar used by generate.
Initially, this is *simple-grammar*,
but we can switch to other grammars.")
*GRAMMAR*
(defun rule-lhs (rule)
"The left-hand side of a rule"
(first rule))
RULE-LHS
37
(defun rule-rhs (rule)
"The right-hand side of a rule"
(rest (rest rule)))
RULE-RHS
(defun rewrite(category)
"return a list of the possible rewritees for this category"
(rule-rhs (assoc category *grammar*)))
REWRITE
(defun random-elt (choices)
"choose an element from a list at random"
(elt choices (random (length choices))))
RANDOM-ELT
(defun mappend (fn the-list)
"Apply fn to each element of list and append the result"
(apply #'append (mapcar fn the-list)))
MAPPEND
38
(defun generate (phrase)
"Generate a random sentence or a phrase"
(cond ((listp phrase)
(mappend #'generate phrase))
((rewrite phrase)
(generate (random-elt (rewrite phrase))))
(t (list phrase))))
GENERATE
(generate 'sentence)
(THE WOMAN LIKED A TABLE)
(generate 'noun-phrase)
(A WOMAN)
(generate 'verb-phrase)
(TOOK A WOMAN)
(generate 'Verb)
(HIT)
(generate 'Noun)
(BALL)
(generate 'Article)
(THE)
39
Exercise Problems
If you have time, try to do the following
exercise problems.
1. Modify e.g.3 and make a data base of English
words: verb (intransitive verb, transitive verb),
noun, article, adjective, adverb, preposition, …,
etc.
2. Write a version of generate function that explicitly
differentiates between terminal symbols (those
with no rewrite rules) and non terminal symbols.
3. Defining a new grammar that includes adjectives,
prepositional phrases, proper names, and pronouns.
40
41
Simple Lisp Programs
References:
http://www-itolab.ics.nitech.ac.jp/LISP/text-contents.html
http://grimpeur.tamu.edu/~colin/lp/lp.html
http://www-2.cs.cmu.edu/Groups/AI/html/cltl/clm/#R
http://www.cs.utsa.edu/research/AI/cltl/clm/clm.html
42
• http://clisp.cons.org/
• http://sourceforge.net/projects/clisp