Transcript Artificial Intelligence

Artificial Intelligence
LISP
TES3111 October 2001
Lisp resources
• We will use an implementation of LISP called
Allegro Common LISP.
• Different LISP interpreters include - Eg
interpreter: Allegro LISP, Harlequin LISP,
Corman Lisp.
Text books:
ANSI Common LISP, P.Graham, Prentice Hall, 1995
(recommended)
Common LISP:the language, G.L. Steele, Digital Press,
1990 (2nd Edition)
TES3111 October 2001
Lisp resources-cont
Common LISP: A gentle introduction to Symbolic
Computing, David Touretzky, Addison Wesley, 1990.
Paradigms of Artificial Intelligence Programming: Case
Studies in Common LISP, Peter Norvig, Academic
Press/Morgan Kaufmann, 1992.
TES3111 October 2001
Useful websites for LISP
• Allegro Lisp download
– http://www.franz.com/downloads/
• Association of LISP users
– http://www.alu.org
• Common LISP Open Code Collection
– http://clocc.sourceforge.net
• AI special interest group of the ACM – http://www.sigart.acm.org
TES3111 October 2001
1. Lisp is interactive
• There is an interpreter that evaluates inputs. An
input is processes in 3 steps:
1. Reads input and construct expression from the input.
2. Evaluates the expression for meaning.
3. Prints the results of the evaluation, including signaling
of erros if necessary.
• These 3 steps can be customized by the
programmer.
TES3111 October 2001
2. Lisp is a dynamic language
• Programs are developed incrementally, by making
small changes to the source code.
• Interpreter evaluates the changed definitions and
then immediately run the results.
• New definitions and data structures can be added
at any time.
• This features are ideal for prototyping.
TES3111 October 2001
3. Lisp has symbols
• Symbols are the basic type of data in use.
• Symbols are used to build bigger, more
complex expressions.
• Example of symbols:
– HELLO
– 23-worldofsports
TES3111 October 2001
4. LISP has lists
• Lists are delimited using parenthesis (…).
Anything can be placed in a list, including other
lists (nested lists). For example:
(1 orange 2 3)
(once (upon a) time)
• Empty list is represented as ()
• Caution: elements within a list are separated with
a white space, and NOT a comma ,
TES3111 October 2001
5. Lisp classifies data
• It does not classify variables.
• A variable is just a symbol. It can hold any type of
value.
• A variable do not have to be declared before it is
used.
• Lisp defines different types of data (rather than
defining different types of variables)
TES3111 October 2001
5. Lisp classifies data - contd
Lisp Expression
number
symbol
sequence
keyword
float
integer
list
vector
ratio
string
TES3111 October 2001
5. Lisp classifies data - contd
•
•
•
•
•
•
•
•
Integer - a counting number like 1, 2 ,3 …100, -23
float - real number. Example 1.59, -100.3
ratio - a fraction, example 99/23, 4/5
symbol - a sequence of alphanumeric characters, eg: BOO,
ID4…
keyword - a symbol prefixed with a colon. Eg- :BOO, :ID4
list - a collection of zero or m ore expressions inside (..)
vector - 1 dimensional collection of expressions in
sequential memory
string - a vector of 0 or more characters inside “ ”
TES3111 October 2001
6. Lisp uses prefix notation
• Operators appear in front of their operands.
• The infix (10 + 3) is written as (+ 10 3)
TES3111 October 2001
7. Lisp is functional
• Lisp functions take data, operates on it, and return the
results. The returned results are called function values.
• Functions can return any number of values.
• To call a function, place it as the first element of an input
list, followed by its operands. Example:
(+ 100 99 88)
(setf x (+ 2 3))
• All operations are done through functions
TES3111 October 2001
8. Programs and data
• Lisp makes no distinction between programs and data.
• A program can be treated as a set of instruction or as a list
of symbols.
• This makes it possible to write programs that generate
another program, or programs that analyze other programs.
TES3111 October 2001
9. Lisp evaluation is easy to understand
• Rule 1 :
If an expression is a constant, the interpreter will return the value of
the constant. No more rules apply.
Examples: ‘socrates, 4.5
• Rule 2:
If Rule 1 is not applicable, and the expression is a symbol, then Lisp
treats the symbol as a variable and no more rules are considered. If
the variable has a value, Lisp will return that value. Otherwise it
will report an error.
TES3111 October 2001
9. Lisp evaluation is easy to understand
• Rule 3:
If Rule 1 and Rule 2 do not apply and the expression is a LIST, then
Lisp treats it as a function call and no more rules are considered.
– You should at this point remember that the first element in the list
is assumed to be a defined a function. The remaining elements are
data. Each expression in the data is evaluated left to right.
• Rule 4:
If Rules 1 to 3 do not apply, then there is an error!
TES3111 October 2001
10. Lisp is easy to learn???
• How to study and program in Lisp?
– Read the first few chapters of a good introductory Lisp
book.
– Read up the definition of each Lisp function that you
encounter.
– Start developing a good programming style from the
very start!
TES3111 October 2001
Data Structures
S-Expression - Symbolic expression. It can
be an Atom, a List or a collection of SExpression enclosed by (…)
Atom - String of characters beginning with a
letter, digit. Eg:
Artificial, intelligence, 31416..etc.
TES3111 October 2001
Data Structures
List - a collection of S-Expression enclosed
by ( …. ). Eg:
(One of these days)
(one ((two) three) four)
TES3111 October 2001
Basic Operations
 A LISP program contains functions applied to its
arguments.
 Functions return LISP objects.
 2 types of functions - PREDICATE and
COMMANDS
TES3111 October 2001
Predicate
A function that tests for some condition involving its
arguments and returns
– Nil if the condition is FALSE (Nil stands for FALSE)
– True for any other case. In LISP TRUE is represented
using a special LISP variable T.
TES3111 October 2001
Command
• A command performs operations on its arguments
and returns an S-expression.
• Format of a command is:
(<Command> Arg1 Arg2 … Argn)
Note: All commands and predicates must be
enclosed in (…). To differentiate from lists… a
list is preceded with a single quote ‘
Eg : (CAR a b c) versus ‘(CAR a b c)
TES3111 October 2001
Function - CAR
CAR - returns the first element of a list. Examples:
• (CAR ‘(a b c d e))
• (CAR ‘((an orange) a day))
• (CAR '(1 (2 3 (4 5)) 6))
• (CAR ‘())
Note that in the last example, the argument to CAR is a nulllist.
TES3111 October 2001