Embed Size (px)
Citation preview
Mg. Samuel Oporto Díaz
LISP
INTELIGENCIA ARTIFICIAL
22/37/37
Mapa Conceptual del Curso
Inteligencia Artificial y Robótica
Lenguaje Simbólico
LISP
Búsqueda
Búsqueda Ciega
Búsqueda Heurística
Robótica
Cálculo Vectorial
Cinemática
Movimiento
Inteligencia Artificial
Conceptos Generales
Conocimiento
Agentes
Lenguaje Simbólico
LISP
Lenguaje Simbólico
LISP
Búsqueda
Búsqueda Ciega
Búsqueda Heurística
Búsqueda
Búsqueda Ciega
Búsqueda Heurística
Robótica
Cálculo Vectorial
Cinemática
Movimiento
Robótica
Cálculo Vectorial
Cinemática
Movimiento
Inteligencia Artificial
Conceptos Generales
Conocimiento
Agentes
Inteligencia Artificial
Conceptos Generales
Conocimiento
Agentes
33/37/37
Tabla de Contenido
1. Procesamiento Básico
2. Funciones en LISP
3. Recursión
4. Ejemplos
5. Conclusiones
6. Bibliografía
44/37/37
Objetivos• Exponer los conceptos básicos del LISP.• Presentar las expresiones-s, los átomos y las listas.• Presentar las funciones básicas del LISP.• Crear nuevas funciones en LISP.• Recursión.
55/37/37
LISP un lenguaje simple1. Únicamente dos tipos de objetos:
– átomos (identificadores/constantes) robot green 12.5– listas (de átomos o listas) (1 2 3.14) (robot (color green) (weight 100))
Las listas almacenan diferentes tipos de datos, no contiguos y sin acceso aleatorio)
2. Las funciones y llamadas a funciones son representadas como listas (programa = data) – (define (square x) (* x x))
3. Todos los cálculos son ejecutados mediante la aplicación de funciones a sus argumentos, como listas:– (+ 2 3) > 5– (square 5) > 25– (car (reverse '(a b c))) > c
66/37/37
PROCESAMIENTO BÁSICO DE LISTAS
77/37/37
Procesamiento Básico de Listas• FIRST (CAR).- toma una lista como argumento y regresa el
primer elemento
• REST (CDR).- toma una lista como argumento y regresa una lista sin el primer elemento
• CONS.- toma dos argumentos (normalmente el segundo es una lista) y regresa una lista con el primer argumento como primer elemento de la lista.
• NULL.- checa si una lista está vacía
• LISTP.- checa si el argumento es una lista o no.
88/37/37
Procesamiento Básico de Listas> (first ‘(a b))
a
> (first ‘((a) (b) (c)))
> (first ‘(+ b c))
+
> (rest ‘(a b))
(b)
> (rest ‘(a b c))
(b c)
> (last ‘(a b c))
(c)
> (first (last ‘(a b c)))
c
99/37/37
Ejercicio 1
Escriba una expresión Lisp aplicando first y rests a la siguiente lista de tal manera que se obtenga el símbolo X y el símbolo Y
1.(A (B ((X))) (C) (((Y)) E ))
2.((A B) (C D) (E F) (H (I X)(J L) Y))
3.(A B (C D E (F G H) (I J X (L M Y))))
4.(A B C (() () ((nil (X)))) ()()(((Y)))())
1010/37/37
Ejercicios 2• Represente el siguiente árbol mediante una lista.• Extraiga mediante las funciones FIRST Y REST, las
ocurrencias del número 6
+
9 6 2 *
-3 5
6 2
6
1111/37/37
Construcción de ListasCrear una lista, desde un átomo y una lista(cons a L)
(cons 'h '(o l a))
Crear una lista, con los átomos de dos o + listas(append L L)
(append '(e s t a m o s) '(f e l i c e s))
Crear una lista, con dos o + listas(list a a)
(list 'd 'e 'c 'o 'n 'o 'c 'e 'r 'e 'l 'l 'i 's 'p)
1212/37/37
Construcción de Listas> (cons ‘a ‘(b c d)) (a b c d)
> (cons nil '(a b c)) (NIL A B C)
> (append ‘(a b) ‘(c d)) (a b c d)
> (append '() '(a b c)) (A B C)
> (append nil '(a b c)) (A B C)
> (list ‘(a b) ‘(c d)) ((a b) (c d))
> (list '(a b) nil '(c d)) ((a b) nil (c d))
> (list '(a b) '() '(c d)) ((a b) nil (c d))
1313/37/37
Ejercicio 3• Construye las listas de los siguientes árboles y luego
“arma” la siguiente lista, haga uso de las funciones para construir listas
/
*
-3 5
6 -
6
6 2
*
6 2 /
- +
6 2 6 2
/
+ -
A B A B
A B
1414/37/37
Asignación de valores• La programación funcional del LISP no permite la
asignación de valores a variables, pueden existir programas donde no aparecen.
• La forma habitual es el uso de la vinculación en lugar de la asignación.– Parámetros de funciones.– Variables locales.
1515/37/37
Asignación de valoresAsignación de valores a variables
> (setq x 4 y 2 z 4)
> (setq a (1+ b) b (1+ a) c (+ a b))
Cambio de lugares (places)
> (setq var '(1 2 3 4 5))
(1 2 3 4 5)
> (setf (rest var) '(5 4))
(5 4)
> var
(1 5 4)
1616/37/37
Ejemplo> (setq x (cons 'a 'b) y (list 1 2 3))
(1 2 3)
> (setf (car x) 'x (cdr y) (car x))
X
> x
(X . B)
> y
(1 . X)
1717/37/37
CREACIÓN DE FUNCIONES EN LISP
1818/37/37
Definición de Funciones• LISP permite definir funciones y asignarles un nombre.
defun
• defun asocia a un símbolo (la función) un conjunto de sentencias, en las cuales se pueden utilizar una serie de parámetros formales declarados al inicio de la función.
• Al llamar a la función definida con defun se debe proporcionar los valores concretos con los que sustituir esos parámetros formales en la evaluación de las sentencias del cuerpo de la función.
• Tras terminar la evaluación del cuerpo de la función, el control del programa vuelve al lugar en donde se realizó la llamada.
1919/37/37
Definición de funciones en LISP(defun <function-name> (<par-1> .... <par-n>)
<S-expression-1>
<S-expression-2>
....
<S-expression-m>
)
2020/37/37
Ejemplo de Función
(defun tercer_elemento (items)
(first (rest (rest items))))
> (tercer_elemento ‘(1 2 3 4 5))
3
2121/37/37
Condiciones(cond (<test-1> <action-1.1> .... <action-1.n1>)
(<test-2> <action-2.1> .... <action-2.n2>)
....
(<test-m> <action-m.1> .... <action-m.nm>)
)
2222/37/37
Funciones Lógicas• not toma un argumento y regresa t si es nil, o regresa nil
de otra manera.
• and toma cualquier número de argumentos y regresa nil si alguno de sus argumentos es nil, de otra manera regresa un no-nil.
• or toma cualquier número de argumentos y regresa nil si todos sus argumentos son nil, de otra manera regresa un no-nil.
2323/37/37
Ejemplo• Construir una función para calcular las raíces de una
ecuación cuadrática.• (raiz ‘(2 3 4))
• (defun raiz (a b c)• (list (/ (+ (- b) ((sqrt (- (* b b) (* 4 a c))) (* 2 a))• (/ (- (- b) ((sqrt (- (* b b) (* 4 a c))) (* 2 a))
• )• )
2424/37/37
RECURSION
2525/37/37
RecursiónAl construir una función, es posible confiar en esa definición para usarla como parámetro en la misma función.
(defun (multiply (x y)
(cond ((= x 0) 0)
(t (+ y (multiply (- x 1) y)
)
)
)
)
2626/37/37
Recursión
(defun ismemberof (item list)
(cond ((null list) nil)
((equal item (first list)) t)
(t (ismemberof item (rest list)))
)
)
2727/37/37
Funciones Simples de LISP
• SYMBOLP
• CONSP
• ATOM
• LISTP
• EQUAL
• EQL
• NULL
2828/37/37
Funciones Simples de LISP• ZEROP
• >
• <
• FIRST
• REST
• CONS
• LIST
2929/37/37
Funciones Simples de LISP• APPEND
• REMOVE
• LAST
• ARITMETICAS: -, MAX, MIN, /, +, *, 1+, 1-
3030/37/37
EJEMPLOS
3131/37/37
Ejercicio 4 (LENGTH)• Implemente la función LENGTH usando sólo las funciones
de manipulación de listas y aritméticas
(defun len (L) (len-sub L 0))
(defun len-sub (L S) (cond ((null L) S ) (t (len-sub (cdr L) (+ S 1)) ) ))
3232/37/37
Ejercicio 5 (REMOVE)• Implemente la función REMOVE usando sólo las funciones
de manipulación de listas y aritméticas.
(defun remov (L a) (remov-sub L a nil))
(defun remov-sub (L a S) (cond ((null L) S ) ((equal a (first L)) (remov-sub (rest L) a S) ) ( t (remov-sub (rest L) a (append S (list (first L)))) ) ))
3333/37/37
Ejercicio 6 (APPEND)• Implemente la función APPEND usando sólo las funciones
de manipulación de listas y aritméticas.
3434/37/37
Ejercicio 7 (COUNT-A)• Construya una función llamada COUNT_A que tome un
argumento (que puede ser lista o átomo) y regrese un número entero que indique el número de elemento atómicos que existe en la estructura.
3535/37/37
CONCLUSIONES
3636/37/37
Conclusiones LISP es un lenguaje de alto nivel de tipo funcional que es LISP es un lenguaje de alto nivel de tipo funcional que es
utilizado en múltiples aplicaciones de IAutilizado en múltiples aplicaciones de IA
LISP se basa en manejo de listas y tiene desde LISP se basa en manejo de listas y tiene desde funciones simples hasta estructuras de datosfunciones simples hasta estructuras de datos
3737/37/37
Bibliografía• LISP
Winston and HornAddison Wesley
• The Little LisperDaniel Friedman and Mathias FelleisenSRA
• Apuntes de LISPGraeme Ritchie
3838/37/37
PREGUNTAS
