Post on 21-Feb-2015
Mg. Samuel Oporto Díaz Lima, 3 de Octubre 2005
LISP
INTELIGENCIA ARTIFICIAL
22/47/47
Mapa Conceptual del Curso
Inteligencia Artificial y Sistemas Expertos
Lenguaje Simbólico
LISP
Búsqueda
Búsqueda Ciega
Búsqueda Heurística
Planeación
Lógica y Razonamiento
Lógica Proposicional
Lógica de Predicados
Inferencia y Razonamiento
Inteligencia Artificial
Conceptos Generales
Conocimiento
Agentes
33/47/47
Tabla de Contenido
1. Historia.
2. Introducción
3. Expresiones y Átomos
4. Listas
5. Funciones
6. Evaluación de Expresiones
7. Conclusiones
8. Bibliografía
44/47/47
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.
55/47/47
HISTORIA
66/47/47
Historia• Creado por John McCarthy• Responsable de introducir el término “inteligencia Artificial”,
lo hizo en la Conferencia de Dartmouth en 1955• McCarthy inventó el lenguaje de programación Lisp y
publicó su diseño en Comunicaciones del ACM en 1960 • El primer Lisp se desarrolló en una IBM-704, y en 1962
apareció la versión 1.5. • A mediados de los 60's, MIT desarrolló MacLisp, Xerox -
Interlisp, Stanford - UCI Lisp. • En los 70's, G. Steele y G. Sussman - Scheme. • En los 80's - Common Lisp.
77/47/47
INTRODUCCION
88/47/47
Aspectos Generales• LISP es un lenguaje:
– orientado a computación no-numérica – lenguaje interactivo– No visual
• La programación funcional usa definiciones de funciones y llamadas de funciones como las únicas construcciones de programación.
• Una función pura toma ciertos argumentos y regresa un resultado nada más (no tiene efectos secundarios en el ambiente).
(función arg1 arg2 ...)
99/47/47
Aspectos Generales• LISP puede usa recursión, evita datos y asignaciones
globales, pero la I/O es difícil.
• Basado en el cálculo Lambda (A. Church) e.g.,
LISP (LISt Processor)
1010/47/47
Ejercicio 1Convierta en notación lambda las siguientes expresiones en notación infija.
1. λ(x, y).(3x + xy - x/y)
2. λ(x).(3x3 + x2 + 5x -5)
3. λ(x, y).(3x + xy - x/y)
4. λ(x, y, z).(2+3*x/y –x*y*z +z3)
1111/47/47
Ejercicio 2Convierta a notación prefija las siguientes expresiones:
a. (2+3-4)/(4*4+5)
b. (2*34 - 3(3*5 - 1)+4/3)/(2*4(3-4+5*6)+3)
c. (3 – 4 – 6 - 4*5)/((2 + 3/4)*(3*5/2 + 1)/(2 + 4 + 3))
d. (2*3 – 4 + (5*6)/(4 - 6) - 3*55/(3 + 4 - 5*7))/(4+2)
1212/47/47
¿Por qué Lisp?• En LISP los programas y datos usan la misma estructura, lo
que permite escribir programas que escriban programas.
• Se pueden desarrollar prototipos rápidamente. • Se pueden probar programas y funciones aisladas.
• En otros lenguajes las variables tienen un tipo asociado (no se puede usar una variable sin especificar su tipo).
• En LISP los valores tienen tipos no las variables (manifest typing) a diferencia (implicit typing).
• Tiene un garbage collector o recolector de basura y manejo de memoria automático.
1313/47/47
¿Por qué Lisp?• Se pueden escribir programas que realicen tareas que no
se pueden hacer en otros lenguajes,
> (defun sumaN (n) Se crea una función
#'(lambda(x) (+ x n))) > (setf suma3 (sumaN 3)) Se asigna a una variable
> (funcall suma3 4) 7 Se llamar a la variable
• Se ha utilizado en el desarrollo de sistemas complejos: EMACS, AutoCad, MACSYMA, etc.
FUNCALL llama a una función con varias entradas(funcall #'cons 'a '(b c))
(A B C)
1414/47/47
Computación Simbólica• Las reglas léxicas son mucho más simples en LISP.
1. Solo existen paréntesis, comillas (sencilla y doble), espacios y comas.
2. El punto y coma no separa expresiones (no es necesario debido a los paréntesis) sino que inicia comentarios.
• LISP permite la manipulación de símbolos, y la construcción de estructuras de datos complejas a partir de ellos.
> (append '(Carlos Antonio) '(Carmen Rosa))(CARLOS ANTONIO CARMEN ROSA)
1515/47/47
Computación Simbólica• La parte extraña es el ('), que sirve para bloquear la
evaluación de una expresión y devolverla literalmente.
> '(Carlos Antonio)CARLOS ANTONIO
> 'AA
> '22
> A
Error: A is not a bound variable
> (Luis ‘Maria)Error: Luis is not a function
> 22
> '(+ 2 2)(+ 2 2)
> (+ 2 2)4
1616/47/47
Computación Simbólica• Los cálculos simbólicos y numéricos se pueden mezclar.> (+ 2 (length '(a b c d)))
6
• LISP no otorga semántica a los símbolos que manipula.• LISP contiene un conjunto de funciones predefinidas que es
necesario conocer. Como +, append, length
• Los símbolos en LISP no son casesensitive.
• Muchos signos de puntuación son autorizados para formar parte de los símbolos: '?!$/<=>'
1717/47/47
Ejercicio 3• ¿Diga que entrega el LISP cuando se le entrega las
siguientes expresiones?:
123 ‘1233 ABC ‘ABC ‘(123) (ABC) ‘(ABC) (+ 12 3) ‘(+ 12 3) page
1818/47/47
Ejercicio 3• ¿Diga que entrega el LISP cuando se le entrega las
siguientes expresiones?:
123 123 ‘1233 123 ABC the variable ABC is unbound ‘ABC ABC ‘(123) (123) (ABC) Undefind function ABC called ‘(ABC) (ABC) (+ 12 3) 15 ‘(+ 12 3) (+ 12 3)
1919/47/47
EXPRESIONES-S Y ATOMOS
2020/47/47
Expresiones-S• Son estructuras con la que trabaja LISP y están formadas
por:1. Átomos
2. Estructuras de la forma (S1 . S2):Cada celda tiene dos partes llamadas:CAR (S1) y CDR (S2).
(1 .2)(1 .(2 .3))
(D1 .(D2 .(D3 .... .(DN.())))
2121/47/47
Expresiones-S• Hay una notación abreviada:
– Los elementos no están en parejas, es decir desaparecen los ( )
– El punto se sustituye por un espacio en blanco
– Se obvia la segunda parte de la cadena de estructuras simbólicas que contiene NIL.
(D1 D2 D3 ... DN)
2222/47/47
Átomos• En general, en Lisp se tiene ó átomos ó listas. • Son uno de los posibles componentes de una S-expression.• Esta formado por una cadena de caracteres que comienza
con una letra, o un dígito o un carácter especial distinto de los paréntesis “(“ , “)”
Ejemplos:
Asunto C.P. Pi 3.1415927
2323/47/47
LISTAS
2424/47/47
Listas• Las listas permiten representar una gran cantidad de cosas.
Inclusive los programas en Lisp se expresan como listas.• Las listas tienen una representación escrita e interna. • La representación interna son cadenas de celdas cons. (a b c) (uno) (esto es 1 lista)
• Corresponden a una colección de expresiones-s encerradas entre paréntesis y separadas por uno o más espacios.
• Formalmente, una lista es una expresión tal que es:– Un átomo, nil o () es una lista.– Una lista (S1 .S2) , donde S2 es una lista.‘(1 .(2 .(3 ))) (1 2 3)
2525/47/47
Ejemplos de Listas> (1 2 3)> ((a b) (c d) (e f))> (a (1 2 3) d) > ((1 uno) (2 dos) (3 tres))
> ‘(1 .(2))(1 2)
> ‘(1 .(2 .(())))(1 2 nil)
> (Dos .(hombres .(y .(un .(destino . nil)))))(Dos hombre y un destino)
> (300000 .((masa . nil) .(velocidad . nil) .(luz . nil)))(300000 ((masa) velocidad) luz)
2626/47/47
Representación de Listas
(setf lista-ejemplo 666)(setf lista-ejemplo .(666))
2727/47/47
Lista vacía o nula• Las listas pueden ser Vacías o No vacías
Listas vacías:• S-expresión especial que es a la vez un átomo y una lista• Se representa por NIL o “( )”• Representación tradicional:
• Para diferenciar las listas de las funciones, se empieza la lista con el signo del apóstrofe ´
2828/47/47
Listas no vacías• La más sencilla es la que tiene un único elemento.
• Cualquier lista no vacía de n elementos se puede ver como una estructura en la que se repite n veces la estructura de la lista con un único elemento.
• La lista elemental de un solo elemento, tiene dos tipos de información:– El dato correspondiente a esa posición de la lista.– El dato correspondiente al siguiente elemento de la lista.
2929/47/47
Listas no vacías• Variable lista-ejemplolista-ejemplo que tiene un único elemento 666:
• (setf lista-ejemplo '(666))
3030/47/47
Listas• Ejemplo de la variable vocales que tiene como valor la lista
LISP (a e i o u):
> (setf lista '(a e i o u))
(A E I O U)
3131/47/47
FUNCIONES
3232/47/47
Funciones con Números• Funciones aritméticas simples: suma, resta, multiplicación y
división:
Clases de números• Enteros: números sin decimales• Punto flotante: siempre se escribe con un punto decimal• Ratios (fracciones): simplifica automáticamente las
fracciones para usar un denominador los mas pequeño posible.
5
611
3333/47/47
Orden de las entradas• La primera entrada de una función: flecha mas alta de la
caja• La segunda entrada: la flecha de mas abajo.
(8/2) (2/8)
8 2
4 1/4
2 8
3434/47/47
Símbolos• Son otra clase de datos en Lisp• Pueden contener cualquier combinación de letras y
números, y algunos caracteres especiales.
• Ejemplos:
BANANAS
COMPUTADOR
• Símbolos especiales T y NIL– T Verdadero, Yes – NIL Falso, No, Vacío
3535/47/47
Operaciones(+ n1 n2 ... nN) retorna la suma n1+n2+…+nN. Si N = 0, da 0.
(+) 0
(+ 3) 3
(+ 3 7 5) 15
(+ 32000 32000) ERROR (*)
(+ 32000.0 32000) 64000.0
(- n1 n2 ... nN) retorna el valor de n1-n2-….-nN. Si N = 1, da -n1
(- 3) -3
(- 123 7 5) 111
(ABS n) devuelve el valor absoluto de n.
(ABS 3) 3
(ABS -3.6) 3.6
3636/47/47
Operaciones(/ n1 n2) devuelve el valor de dividir n1 por n2.(/ 6 2) 3.0 (/ 5 2) 2.5
(/ n) es lo mismo que (/ 1 n); es decir, devuelve el inverso de n.(/ 2) 0.5 (/ 0.5) 2.0
(MOD n1 n2) devuelve el resto de la división entera de n1 por n2.(MOD 7 2) ---> 1
(MAX n1 ... nN) devuelve el mayor valor de n1,..., nN.(MAX 3) 3 (MAX 1 2 3 4 5 2) 5(MAX -2.3 7 0) 7.0
(MIN n1 ... nN) devuelve el menor valor de n1,..., nN.(MIN 3) 3 (MIN 1 2 3 4 5 2) 1(MIN -2.3 7 0) -2.3
3737/47/47
Indicar qué retorna el LISP para las siguientes expresiones:
1. (+ 2 3) 2. (* 2 (+ 4 6)) 3. (+ 2/7 7/67) 4. (- 8 6) 5. (* 2/7 6/5) 6. (/ 4 5) 7. (exp 9) 8. (expt 2 4) 9. (sqrt 11)
Ejercicio 4
3838/47/47
Calcular2*(4 - 1)*6 + (8 - 6)*7 18
Solución:> (+ (* 2 (- 4 1) (/ 6 18)) (* (- 8 6) 7))> 16.0
> (+ (* 2 (- 4 1) (/ 6 18)) (* (- 8 6) 7))> 16.0
Ejercicio 5
3939/47/47
Número de entradas en una función• Muchas funciones aceptan un numero variable de entradas
• Ejemplo:
(+ 4 3 2) (+ (+ 4 3) 2) 9(- 4 3 2) (- (- 4 3) 2) -1(* 4 3 2) (*(* 4 3) 2) 24(/ 6 3 2) (/ (/ 6 3) 2) 1.0(- 4) -4
(/ 4) 0.25 (su reciproco)
4040/47/47
EVALUACION DE EXPRESIONES
4141/47/47
Evaluación• La evaluación de las expresiones S se lleva a cabo
siguiendo el algoritmo de la función Eval.
IF L is atomic THEN IF L is numeric THEN result is corresponding number ELSE IF L currently has value V THEN result is V ELSE error- unbound variable ELSE IF L is a call of a known function F THEN determine which arguments are to be evaluated apply EVAL to appropriate arguments apply F to accumulated results ELSE error - undefined function
4242/47/47
Función especial QUOTEEsta función toma un argumento y NO lo evalúa
Ejemplo:
> (quote (+ 2 3))
> (+ 2 3)
La función quote puede ser sustituida por un el símbolo ’
> ’(+ 2 3)
4343/47/47
Ejercicios 3• Indique lo que aparecería después de teclear lo siguiente
(* 8 9)
'(* 8 9)
(+ (* 1 2) (+ 3 4))
(+ '(* 1 2) '(+ 3 4))
(+ '(* 1 2) (+ 3 4))
'(+ (* 1 2) (+ 3 4))
'(+ '(* 1 2) (+ 3 4))
4444/47/47
CONCLUSIONES
4545/47/47
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 funciones LISP se basa en manejo de listas y tiene desde funciones simples hasta estructuras de datossimples hasta estructuras de datos
4646/47/47
Bibliografía• LISP
Winston and HornAddison Wesley
• The Little LisperDaniel Friedman and Mathias FelleisenSRA
• Apuntes de LISPGraeme Ritchie
4747/47/47
PREGUNTAS