PDF de programación - Tema 1: Introducción a Lisp - Inteligencia artificial I

Inteligencia Artificial I

Curso 2012{2013

Tema 1: Introduccion a Lisp

Jose L. Ruiz Reina

Dpto. de Ciencias de la Computacion e Inteligencia Articial

Universidad de Sevilla

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.1

Introduccion a Lisp

x Historia: John McCarthy, 1958
x LISt Processing
u Lambda calculo
x Lenguaje interpretado
u Bucle lee, evalua, escribe
u Compilador
x Historicamente, uno de los lenguajes de la Inteligencia Articial
u Procesamiento simbolico
x Common Lisp: Clisp, GCL, CMUCL, Allegro. . .
u Usaremos clisp para las practicas

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.2

Introduccion a Lisp

x Prototipado Rapido
x Eciencia
x Paradigma de programacion funcional
u Aunque no es puramente funcional
x Un lenguaje de programacion exible
u Lenguaje de programacion \programable"

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.3

Una sesion con Lisp

objeto Lisp.

x Arrancar un interprete: clisp
x Interactuar con el:
u El usuario escribe una expresion en el interprete.
u El interprete de Lisp reconoce la expresion como la representacion escrita de un
u El objeto es evaluado. Su valor es un objeto Lisp.
u El interprete elige una representacion escrita del valor obtenido.
u El interprete escribe dicha representacion.
x Cerrar el interprete: (exit)
x Compilacion: compile-file

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.4

Introduccion a Lisp

x Expresiones

> 1
1
> (+ 2 3)
5
> (+ (- 5 2) (* 3 3))
12

x Primeras observaciones:
u Notacion preja: funcion y argumentos. Parentesis. Expresiones anidadas
u Atomos y listas
u Sintacticamente simple

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.5

Introduccion a Lisp

x Evaluacion

> (+ (- 5 2) (* 3 3))
12

x Regla de evaluacion (basica)
u Evaluacion de los argumentos
u De izquierda a derecha
u Los valores se pasan a la funcion
x Todo se evalua
u
x Las formas especiales no siguen la regla basica de evaluacion
u Por ejemplo: if, cond,. . .
u Se veran mas adelante

quote para evitar evaluaciones

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.6

Introduccion a Lisp

x La funcion quote:

> (quote (+ (- 5 2) (* 3 3)))
(+ (- 5 2) (* 3 3))

> ’(+ (- 5 2) (* 3 3))
(+ (- 5 2) (* 3 3))

x Otro ejemplo:

> x
*** - EVAL: variable X has no value
1. Break> abort
> ’x
X
> (esto (es) (una lista))
*** - EVAL: undefined function ESTO
1. Break> abort
> ’(esto (es) (una lista))
(ESTO (ES) (UNA LISTA))

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.7

Introduccion a Lisp

x Entrada-Salida frente a evaluacion
x Salida: funcion format

> (format t "~a mas ~a igual a ~a. ~%" 2 3 (+ 2 3))
2 mas 3 igual a 5.
NIL

x Entrada: funcion read

> (defun pide (frase)

(format t "~a " frase)
(read))

PIDE
> (pide "Su edad, por favor:")
Su edad, por favor: 23

23x Algunas observaciones
u Lectura de expresiones Lisp
u Secuencialidad en programas
u Efectos colaterales

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.8

Introduccion a Lisp

x Variables locales y globales

> (let ((x 1) (y 2))

(+ x y))

3
> x
*** - EVAL: variable X has no value
> (setf *glob* 3)
*GLOB*
> *glob*
3

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.9

Introduccion a Lisp

x El paradigma de la programacion funcional
u Valores vs. Modicaciones

> (setf x ’(a b c d))
(A B C D)
> (remove ’b x)
(A C D)
> x
(A B C D)

> (setf x (remove ’b x))
(A C D)
> x
(A C D)

toria

x La programacion sin efectos colaterales es preferible aunque no obliga-
u Los programas se comportan como funciones en el sentido matematico, dependiendo
u Vericacion formal

exclusivamente de sus datos de entrada

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.10

Tipos de datos basicos

x Atomicos:
u numeros: 27, 3.14, . . .
u smbolos: foo, FIRST, +, . . .
u caracteres: #nA, #nSpace
x No atomicos:
u Pares punteados y listas: (a . b), (a b c d e)
u Cadenas: "Buenos das"
u Arrays: #(a b 0 nil), #3A(((0 0) (1 1) (2 2)) ((0 1) (1 2) (2 3)))
u Estructuras:
u Tablas hash

mercedes) :CIUDAD sevilla)

#S(PERSONA :NOMBRE (ana maria) :ESTADO casado :CALLE (reina

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.11

Pares y listas

x Pares punteados:
u Construtor: cons
u Ejemplo: (cons 1 2) se evalua al par (1 . 2)

x Listas
u Un tipo especial de par punteado (pero el tipo de dato no atomico mas comun)
u Ejemplo: la lista (1 2 3)

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.12

12123nilFunciones de construccion de listas

x Funciones basicas de creacion

* (CONS X Y)

(cons ’a ’b)
(cons ’a ’(b c))
(cons ’a (cons ’b (cons ’c ’())))
(cons ’(a b) ’(c d))

=> (A . B)
=> (A B C)
=> (A B C)
=> ((A B) C D)

* (LIST X-1 ... X-N)

(list ’a ’b ’c)
(list ’(a b) ’(c d))
(list)
(list (list ’a ’b)

=> (A B C)
=> ((A B) (C D))
=> NIL

(list ’c ’d ’e))

=> ((A B) (C D))

* (APPEND L-1 ... L-N)

(append ’(a) ’(b) ’(c) ’(x y))
(append ’(a b) ’(c d))

=> (A B C X Y)
=> (A B C D)

* (REVERSE L)

(reverse ’(a (b c) d))

=> (D (B C) A)

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.13

Funciones de acceso a listas

* (FIRST L), (CAR L)

(first ’(a b c))
(first ())

* (REST L), (CDR L)

(rest ’(a b c))
(rest ())

* (SECOND L)

(second ’(a b c d))
(second ’(a))

=> A
=> NIL

=> (B C)
=> NIL

=> B
=> NIL

* (NTH N L)

(nth 2 ’(a b c d))

=> C

* (LENGTH L)

(length ’(a (b c) d))

=> 3

* (SUBSEQ L I J)

(subseq ’(a b c d e f g h) 2 5) => (C D E)

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.14

Numeros

x Existen distintos tipos de numeros:
u Enteros: 14, 0, -7
u Racionales: 4/5, -2/1
u Coma otante: 4.634, -.543
u Complejos: #C(3 46), #C(3.2, -5)

> (/ 22 7)
22/7
> (round (/ 22 7))
3 ;
1/7
> (float (/ 22 7))
3.142857
> #c(2 0)
2

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.15

Funciones aritmeticas

* (+ X-1 ... X-N)

(+ 3 7 5)

=> 15

* (- X-1 ... X-N)
(- 123 7 5)
(- 3)

111

=>
=> -3

* (* X-1 ... X-N)

(* 2 7 5)

=> 70

* (/ X Y)

(/ 6 2)
(/ 5 2.0)

=> 3
=> 2.5

* (MOD X Y)

(mod 7 2)

=> 1

* (EXPT X Y)

(expt 2 3)

=> 8

* (SQRT X)

(sqrt 16)

=> 4

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.16

Valores logicos: T y NIL
x El smbolo NIL tiene asociado el valor logico "falso".
u
() ’() NIL
x El smbolo T tiene asociado el valor logico "verdadero".
u Pero en general, cualquier elemento distinto de NIL tiene el valor logico "verdadero".
x Un predicado es una funcion que devuelve un valor de verdad.

> (listp ’(a b c))
T
> (listp 27)
NIL
> (and 3 4 5)
5

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.17

Predicados aritmeticos

x Predicados aritmeticos:

* (= X-1 ... X-N)

(= 2 2.0 (+ 1 1))
(= 1 2 1)

=> T
=> NIL

* (> X-1 ... X-N)
(> 4 3 2 1)
(> 4 3 3 2)

* (>= X-1 ... X-N)
(>= 4 3 3 2)
(>= 4 3 3 5)

* (< X-1 ... X-N)

* (<= X-1 ... X-N)

=> T
=> NIL

=> T
=> NIL

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.18

Predicados de tipos

* (ATOM X)

(atom 3)
(atom ’hola)
(atom ’(1 2 3))

=> T
=> T
=>

NIL

* (SYMBOLP X)

(symbolp ’a)
(symbolp 3)

=> T
=> NIL

* (NUMBERP X)

(numberp 4)
(numberp 3.4)
(numberp ’(1))

=> T
=> T
=> NIL

* (CONSP X)

(consp ’(1 . 2))
(consp nil)
(consp ’(2 5))

=> T
=> NIL
=> T

* (NULL X)

(null (rest ’(a b)))
(null (rest ’(a)))

=> NIL
=> T
CcIa

IA-I 2012{2013

Introduccion a Lisp

1.19

Predicados de igualdad

* (EQ X Y)

(eq 3 3)
(eq 3 3.0)
(eq 3.0 3.0)
(eq (first ’(a b c)) ’a)
(eq (cons ’a ’(b c)) ’(a b c))

=> T
=> NIL
=> NIL
=> T
=> NIL

* (EQL X Y)

(eql 3.0 3.0)
(eql (cons ’a ’(b)) (cons ’a ’(b)))

=> T
=> NIL

* (EQUAL X Y)

(equal (cons ’a ’(b)) (cons ’a ’(b))) =>

T

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.20

Expresiones condicionales

x La forma especial IF:

(IF <condicion>

<consecuencia>
<alternativa>)

x Mecanismo de evaluacion de un IF (forma especial):
u Evalua <condicion>:
u Si el valor es distinto de NIL ("verdadero") devuelve el valor de <consecuencia>,
u en caso contrario devuelve el valor de <alternativa>.
x Ejemplo: (if (= y 0) 9999999 (/ x y))

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.21

Expresiones condicionales

x La forma especial COND:
u

(COND <pares>)

<pares>: sucesion de expresiones de la forma
(<condicion><consecuencias>)
siendo <consecuencias> una sucesion de expresiones Lisp.

x Evaluacion de un COND (forma especial):
u Evalua los elemento <condicion> hasta que aparece un valor distinto de NIL ("ver-
u Evalua la correspondiente <consecuencias>. Evalua cada una de las expresiones que
u Ejemplo:

la componen, devolviendo como el valor el ultimo obtenido.

dadero").

(cond

((< x 3) (format t "Es pequeño") x)
((< x 5) (format t "Es mediano") (* x 2))
(t (* x x)))

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.22

Condicionales

* (IF TEST ENTONCES [EN-CASO-CONTRARIO])

(if (> 2 1)
(if (> 1 2) 1)

1 2)

=> 1
=> NIL

* (WHEN TEST E-1 ... E-N)

(when (= 1 1) 1 2 3) =>
(when (= 1 2) 1 2 3) =>

3
NIL

* (UNLESS TEST E-1 ... E-N)

(unless (= 1 1)
(unless (= 1 2) 1 2 3) =>

1 2 3)

=> NIL

3

* (COND L-1 ... L-N)

> (defun notas (n)

(cond ((< n 5) ’suspenso)
((< n 7) ’aprobado)
((< n 9) ’notable)
(t ’sobresaliente) ))

NOTAS
> (notas 8)
NOTABLE

IA-I 2012{2013

CcIa

Introduccion a Lisp

1.23

Oper