Alcantara Bustamante 82t Tarea 1 U2.docx

LISP – Unidad II Nombre: Alcántara Bustamante José Luis

Grupo: 82T

INSTITUTO TECNOLÓGICO DE LÁZARO CÁRDENAS

Carrera: Ingeniería en Sistemas Computacionales

Asignatura: Programación Lógica y Funcional Unidad II – Lenguaje LISP

Profesor: José Antonio López Tello

Alumnos: Alcántara Bustamante José Luis

Lugar y Fecha: Cd. Y puerto Lázaro Cárdenas, Michoacán a 05 de marzo del 2019.

Programación Lógica y Funcional

Página 1

LISP – Unidad II Nombre: Alcántara Bustamante José Luis

Grupo: 82T

CONTENIDO 1. El lenguaje LISP ................................................................................................................. 3 1.1. Descripción .................................................................................................................. 3 1.2. Los objetos básicos (s-expresión) ................................................................................ 3 1.2.1. Los átomos. ........................................................................................................... 4 1.2.2. Las listas. .............................................................................................................. 4 1.3. Expresiones .................................................................................................................. 5 1.4. Evaluación ................................................................................................................... 6 1.5 Datos. ............................................................................................................................ 7 1.7 Operaciones básicas con listas. ..................................................................................... 8 1.8 Valores de verdad ......................................................................................................... 9 1.9. Funciones ................................................................................................................... 10 1.9.1. Funciones con nombres. ..................................................................................... 11 1.9.2. Funciones anónimas. .......................................................................................... 11 1.10. Predicados ................................................................................................................ 12 1.10.1. Valores lógicos. ................................................................................................ 12 1.10.2. Predicados de tipos. .......................................................................................... 12 1.10.3. Predicados de igualdad. .................................................................................... 13 1.10.4. Operadores lógicos. .......................................................................................... 14 Bibliografía ........................................................................................................................... 15

Programación Lógica y Funcional

Página 2

LISP – Unidad II Nombre: Alcántara Bustamante José Luis

Grupo: 82T

1. El lenguaje LISP 1.1. Descripción John MacCarthy et. al (1965) señalan que el lenguaje LISP está diseñado principalmente para el procesamiento de datos simbólicos. Ya que se ha utilizado para cálculos simbólicos en cálculo diferencial e integral, teoría de circuitos eléctricos, lógica matemática, juegos y otros campos de inteligencia artificial. LISP es un lenguaje matemático formal, por lo tanto, es posible dar una descripción concisa pero completa de la misma. Tal es el propósito de esta primera sección del manual. Otras secciones describirán las formas de utilizar LISP en forma ventajosa y explicarán las extensiones del lenguaje que lo convierten en un sistema de programación conveniente. LISP se diferencia de la mayoría de los lenguajes de programación en tres formas importantes. La primera forma es en la naturaleza de los datos. En el lenguaje LISP, todos los datos se encuentran en forma de expresiones simbólicas, generalmente denominadas expresiones-S. Las expresiones S son de longitud indefinida y tienen un tipo de estructura de árbol ramificado, de modo que las subexpresiones significativas se pueden aislar fácilmente en el sistema de programación LISP, la mayor parte de la memoria disponible se utiliza para almacenar expresiones S en forma de estructuras de lista. Este tipo de organización de memoria libera al programador de la necesidad de asignar almacenamiento para las diferentes secciones de su programa. 1.2. Los objetos básicos (s-expresión) Alonso (1991) nos señala que los objetos que se usan en Lisp se llaman S–expresiones (por “Symbolic expressions”). Estos objetos se clasifican en los siguientes tipos:

Figura 1. Clasificación de las s-expresiones. Fuente: (Alonso, 1991, pág. 2).

Para referirnos a dichos objetos, usaremos las siguientes abreviaturas:     

s a simb n l

s–expresión atomo síımbolo número lista

Programación Lógica y Funcional

Página 3

LISP – Unidad II Nombre: Alcántara Bustamante José Luis

Grupo: 82T

1.2.1. Los átomos. 1.2.1.1. Los símbolos “Los símbolos son cadenas continuas de caracteres (conteniendo al menos un carácter no numérico). Por ejemplo, AGUA, A12, VAR-AUX, + son símbolos.” (Alonso, 1991, pág. 2). 1.2.1.2. Los números “GCLISP manipula números enteros sobre 16 bits (permitiendo calcular en el intervalo [−215 + 1, 215 − 1], i.e. [-32767, 32767]) y números flotantes sobre 128 bits (permitiendo calcular en el intervalo [-1.0F+38, 1.0F+38]).” (Alonso, 1991, pág. 2). 1.2.1.3. Las cadenas de caracteres. “Una cadena de caracteres es una sucesión de caracteres, con o sin huecos, que comienza y termina por dobles comillas. Por ejemplo, “A 1 23” es una cadena de caracteres.” (Alonso, 1991, pág. 2). En otras palabras, el tipo de s-expresión más elemental es el símbolo atómico, el cual, John et. al (1965) afirman que es una cadena que no puede tener más de treinta caracteres y que, a la vez, siempre debe empezar por una letra, más no por un número o cualquier otro carácter. Por ejemplo: A APPLE PART2 ALCANTARA AABL970311

Esos símbolos son llamados atómicos debido a que se toman como un todo, ya que no pueden dividirse dentro de LISP en caracteres individuales. 1.2.2. Las listas. Una lista es una sucesión ordenada, posiblemente vacía, de objetos. Sintácticamente, se compone de un paréntesis abierto, objetos separados por huecos y un paréntesis cerrado. Por ejemplo: (A,1,B), (), (A(B(C)))

…son listas.

Programación Lógica y Funcional

Página 4

LISP – Unidad II Nombre: Alcántara Bustamante José Luis

Grupo: 82T

1.3. Expresiones La Universidad Veracruzana (2012), señala que el sistema normalmente despliega un indicador llamado prompt (>) señalando que está esperando que una expresión sea escrita. Por ejemplo, si escribimos el entero 1 después del prompt y tecleamos enter, tenemos: > 1 1 >

Al ingresar una expresión el sistema despliega el valor de la expresión que se ingresa, seguida de un nuevo prompt, ya que esto indica que está listo para evaluar una nueva expresión. En este caso, el sistema desplegó lo mismo que tecleamos porque no hay ningún operador en la expresión, es por ello que no había ninguna operación que realizar; asimismo los números, como otras constantes, evalúan a sí mismos. Sin embargo, las cosas son más interesantes cuando una expresión ya posee un operador que necesita ser evaluado, por ejemplo, sumar dos números: > (+ 2 3) 5 >

En la expresión (+ 2 3) el símbolo + es llamado el operador y los números 2 y 3 son sus argumentos. Como el operador viene al principio de la expresión, esta notación se conoce como prefija y aunque parezca extraña, veremos que es muy práctica. Por ejemplo, si queremos sumar tres números en notación infija, necesitaríamos usar dos veces el operador +: 2+3+4. En Lisp, las siguientes sumas son válidas: > (+) 0 > (+ 2) 2 > (+ 2 3) 5 > (+ 2 3 5) 10

Programación Lógica y Funcional

Página 5

LISP – Unidad II Nombre: Alcántara Bustamante José Luis

Grupo: 82T

Como los operadores pueden tomar un número variable de argumentos, es necesario utilizar los paréntesis para indicar donde inicia y donde termina una expresión. Las expresiones pueden anidarse, esto es, el argumento de una expresión puede ser otra expresión compleja. Por ejemplo: > (/ (- 15 1)(- 4 2)) 7

En español esto corresponde a siete menos uno, dividido por cuatro menos dos. Estética minimalista, esto es todo lo que hay que decir sobre la notación en Lisp. Toda expresión Lisp es un átomo, como 1, o bien es una lista que consiste de cero o más expresiones delimitadas por paréntesis. Como veremos, código y datos usan la misma notación en Lisp. 1.4. Evaluación La Universidad Veracruzana (2012), señala que en Lisp, + es una función y (+ 2 3) es una llamada a la función. Cuando Lisp evalúa una llamada a alguna función, lo hace en dos pasos: 1. Los argumentos de la llamada son evaluados de izquierda a derecha. En este caso, los valores de los argumentos son 2 y 3, respectivamente. 2. Los valores de los argumentos son pasados a la función nombrada por el operador. En este caso la función + que regresa 5. Si alguno de los argumentos es a su vez una llamada de función, será evaluado con las mismas reglas. Por ejemplo:Al evaluar la expresión (/ (- 7 1) (- 4 2)) pasa lo siguiente. 1. Lisp evalúa el primer argumento de izquierda a derecha (- 7 1). 7 es evaluado como 7 y 1 como 1. Estos valores son pasados a la función - que regresa 6. 2. El siguiente argumento (- 4 2) es evaluado. 4 es evaluado como 4 y 2 como 2. Estos valores son pasados a la función - que regresa 2. 3. Los valores 6 y 2 son pasados a la función / que regresa 3. Todas las llamadas a función son evaluadas de esta forma, que se conoce como regla de evaluación de Lisp. Sin embargo, no todos los operadores en Lisp son funciones, pero la mayoría lo son.

Programación Lógica y Funcional

Página 6

LISP – Unidad II Nombre: Alcántara Bustamante José Luis

Grupo: 82T

Los operadores que no siguen la regla de evaluación se conocen como operadores especiales. Uno de estos operadores especiales es quote (’). La regla de evaluación de quote es –No evalues nada, despliega lo que el usuario tecleo, verbatim. Por ejemplo: > (quote (+ 2 3)) (+ 2 3) > ’(+ 2 3) (+ 2 3)

Lisp provee el operador quote como una forma de evitar que una expresión sea evaluada. En la siguiente sección veremos porque esta protección puede ser útil. 1.5 Datos. La Universidad Veracruzana (2012), señala que hay dos tipos de datos propios de Lisp son los símbolos y las listas. Los símbolos son palabras. Normalmente se evalúan como si estuvieran escritos en mayúsculas, independientemente de cómo fueron tecleados: > ‘luis LUIS

Los símbolos por lo general no evalúan a sí mismos, así que si es necesario referirse a ellos, se debe usar quote, como en ejemplo anterior, de lo contrario, se producirá un error ya que el símbolo uno no está acotado (no tiene ligado ningún valor en este momento). Las listas se representan como cero o más elementos entre paréntesis. Los elementos pueden ser de cualquier tipo, incluidas las listas. Se debe usar quote con las listas, ya que de otra forma Lisp las tomaría como una llamada a función. Por ejemplo: > ’(Mis 2 "ciudades") (MIS 2 "CIUDADES") > ’(La lista (a b c) tiene 3 elementos) (LA LISTA (A B C) TIENE 3 ELEMENTOS) LUIS

Programación Lógica y Funcional

Página 7

LISP – Unidad II Nombre: Alcántara Bustamante José Luis

Grupo: 82T

Observen que quote protege a toda la expresión, incluidas las sub-expresiones en ella. La lista (a b c), tampoco fue evaluada. También es posible construir listas usando la función list: > (list ’mis (+ 4 6) "bros xD") (MIS 10 BROS XD)

Como se puede observar, Lisp posee una estética minimalista y pragmática, se puede observar que los programas Lisp se representan como listas. Si una lista es precedida por el operador quote, la evaluación regresa la misma lista, en otro caso, la lista es evaluada como si fuese código. Por ejemplo: > (list ’(+ 2 3) (+ 2 3)) ((+ 2 3) 5)

En Lisp hay dos formas de representar la lista vacia, como un par de paréntesis o con el símbolo nil. Por ejemplo: > () NIL

1.7 Operaciones básicas con listas. La Universidad Veracruzana (2012), señala que la función cons construye listas. Si su segundo argumento es una lista, regresa una nueva lista con el primer argumento agregado en el frente. Por ejemplo: > (cons ’a ’(b c d)) (A B C D) > (cons ’a (cons ’b nil)) (A B)

Las funciones primitivas para accesar los elementos de una lista son car y cdr. El car de una lista es su primer elemento (el más a la izquierda) y el cdr es el resto de la lista (menos el primer elemento). Por ejemplo: > (car ’(a b c)) A

Programación Lógica y Funcional

Página 8

LISP – Unidad II Nombre: Alcántara Bustamante José Luis

Grupo: 82T

> (cdr ’(a b c)) (B C)

1.8 Valores de verdad La Universidad Veracruzana (2012) señala que, en Lisp, el símbolo t es la representación por default para verdadero. La representación por default de falso es nil. Ambos evalúan a sí mismos. Por ejemplo, la función listp regresa verdadero si su argumento es una lista: > (listp ’(a b c)) T > (listp 34) NIL

Una función cuyo valor de regreseo se intérpreta como un valor de verdad (verdadero o falso) se conoce como predicado. En lisp es común que el símbolo de un predicado termine en p. Como nil juega dos roles en Lisp, las funciones null (lista vacía) y not (negación) hacen exactamente lo mismo: > (null nil) T > (not nil) T

El condicional (estructura de control) más simple en Lisp es if. Normalmente toma tres argumentos: una expresión test, una expresión then y una expresión else. La expresión test es evaluada, si su valor es verdadero, la expresión then es evaluada; si su valor es falso, la expresión else es evaluada. Ej. > (if (listp ’(a b c d)) (+ 1 2) (+ 3 4)) 3 > (if (listp 34) (+ 1 2) (+ 3 4)) 7

Programación Lógica y Funcional

Página 9

LISP – Unidad II Nombre: Alcántara Bustamante José Luis

Grupo: 82T

1.9. Funciones La Universidad Veracruzana (2012) señala que es posible definir nuevas funciones con defun que toma normalmente tres argumentos: un nombre, una lista de parámetros y una o más expresiones que conforman el cuerpo de la función. Ej. Así definiríamos third: > (defun tercero (lst) (caddr lst)) TERCERO

El primer argumento de defun indica que el nombre de nuestra función definida será tercero. El segundo argumento (lst) indica que la función tiene un sólo argumento, lst. Un símbolo usado de esta forma se conoce como variable. Cuando la variable representa el argumento de una función, se conoce como parámetro. El resto de la definición indica lo que se debe hacer para calcular el valor de la función, en este caso, para cualquier lst, se calculará el primer elemento, del resto, del resto del parámetro (caddr lst). Ej. > C

(tercero ’(a b c d e))

Substituyendo los números particulares por variables, podemos definir una función que verifica si la suma de sus dos primeros argumentos es mayor que el tercero: > (defun suma-mayor-que (x y z) (> (+ x y) z)) SUMA-MAYOR-QUE > (suma-mayor-que 1 4 3) T

Programación Lógica y Funcional

Página 10

LISP – Unidad II Nombre: Alcántara Bustamante José Luis

Grupo: 82T

1.9.1. Funciones con nombres. Haciendo referencia a José A. Alonso (1991), quien señala que las funciones con nombres con aquellas funciones que poseen un identificador para poder ser invocadas en el cuerpo del programa. Para definir una función con nombre se hace uso de la función defun, para explicarlo de una manera más práctica, a continuación se muestra el siguiente ejemplo: > (DEFUN simb l s1,…, sN)

Dónde:     

defun permite definir nuevas funciones. simb es el nombre de la función definida. l es la lista de parámetros (argumentos); son variables locales que no afectan a posibles valores previos, en general. Si no hay argumentos, es obligatorio poner (). s1,..., sN son las expresiones que definen el cuerpo de la función. Devuelve simb.

> (DEFUN CUADRADO (N) (* N N)) CUADRADO > (CUADRADO 3) 9

1.9.2. Funciones anónimas. Haciendo referencia a José A. Alonso (1991), quien señala que las funciones anónimas son aquellas que no poseen un identificador definido como tal en las funciones, pero que sin embargo, se pueden inicializar en la expresión donde se utilice, de ese modo, en la misma expresión se declara, inicializa e invoca. > ((LAMBDA (var1...varN) s1...sM) val1...valN)

Asocia los valores val1,..., valN a las variables var1,..., varN; evalúa las expresiones s1,..., sM y devuelve el valor de sM. Por ejemplo: > ((LAMBDA (M N) (+ M N)) 2 3) ---> 5 (MAPCAR #’(LAMBDA (N) (* 2 N)) ’(1 2 3)) ---> (2 4 6)

Programación Lógica y Funcional

Página 11

LISP – Unidad II Nombre: Alcántara Bustamante José Luis

Grupo: 82T

1.10. Predicados 1.10.1. Valores lógicos. José A. Alonso (1991) señala que hay dos tipos de valores lógicos, como se mencionó previamente por otro autor; los cuales son:  

NIL: su valor es NIL y representa “lo falso”. Puede escribirse como (). T: Su valor es T y representa “verdadero”.

1.10.2. Predicados de tipos. Asimismo, José A. Alonso (1991) también señala que Lisp cuenta con seis predicados de tipos, los cuales son los siguientes: 

NULL: devuelve T, si s es NIL y NIL, si no.



ATOM: devuelve T, si s es un átomo y NIL, si no. > (ATOM 12) ---> T (ATOM ’ABC) ---> T (ATOM "A B") ---> T (ATOM A) ---> ERROR (ATOM ’(A B)) ---> NIL (ATOM NIL) ---> T



SYMBOLP: devuelve T, si s es un símbolo y NIL, si no. > (SYMBOLP 12) ---> NIL (SYMBOLP ’ABC) ---> T (SYMBOLP "A B") ---> NIL (SYMBOLP A) ---> ERROR (SYMBOLP ’(A B)) ---> NIL (SYMBOLP NIL) ---> T



NUMBERP: devuelve T, si s es un número y NIL, si no. > (NUMBERP 123) ---> T (NUMBERP ’A) ---> NIL (SETQ A 3) ---> 3 (NUMBERP A) ---> T

Programación Lógica y Funcional

Página 12

LISP – Unidad II Nombre: Alcántara Bustamante José Luis



Grupo: 82T

CONSP: devuelve T, si s es una lista no vacía y NIL, si no. > (CONSP 23) ---> NIL (CONSP ’(A B)) ---> T (CONSP ()) ---> NIL



LISTP: devuelve T, si s es una lista y NIL, si no. > (LISTP 23) ---> NIL (LISTP ’(A B)) ---> T (LISTP ()) ---> T

1.10.3. Predicados de igualdad. Por otro lado, el mismo autor José A. Alonso (1991) señala que Lisp cuenta con dos predicados de igualdad, los cuales son los siguientes: 

EQ: devuelve T si s1 y s2 son el mismo símbolo y NIL en caso contrario. > (EQ ’LISP ’LISP) ---> T (EQ ’LISP ’LISA) ---> NIL (EQ (CAR ’(A B C)) ’A) ---> T



EQUAL: devuelve T, si s1 y s2 tienen el mismo valor y NIL, si no. > (EQUAL 3 (+ 1 2)) ---> T (EQUAL 3 3.0) ---> NIL (EQUAL (CONS ’A ’(B C)) (CONS ’A ’(B C))) ---> NI

Programación Lógica y Funcional

Página 13

LISP – Unidad II Nombre: Alcántara Bustamante José Luis

Grupo: 82T

1.10.4. Operadores lógicos. De igual manera, basándonos en José A. Alonso (1991), aseguro que existen tres operadores lógicos, los cuales son los siguientes: 

NOT: devuelve T, si s es NIL; NIL, si no.



OR: evalúa sucesivamente s1,..., sN hasta que una de dichas expresiones tenga un valor distinto de NIL. OR devuelve este valor. Si el valor de todas las expresiones es NIL, entonces OR devuelve NIL. > (OR NIL 2 3) ---> 2



AND: evalúa sucesivamente s1,..., sN hasta que el valor de una de dichas expresiones sea NIL; en cuyo caso, AND devuelve NIL. Si el valor de todas las expresiones es distinto de NIL, entonces AND devuelve el valor de sN. > (AND 1 2 3) ---> 3 (AND 1 NIL 3) ---> NIL

Programación Lógica y Funcional

Página 14

LISP – Unidad II Nombre: Alcántara Bustamante José Luis

Grupo: 82T

Bibliografía McCarthy, J., & Levin, M. I. (1965). LISP 1.5 programmer's manual. MIT press. Recuperado de: https://books.google.com.mx/books?hl=es&lr=&id=68j6lEJjMQwC&oi=fnd&pg=PA1&dq =lisp&ots=Ikv0l4Zyxq&sig=n9G0tDxQjZqP-Pj6mwssvT5dDsA José A. Alonso Jiménez. (1991). Manual de Lisp. Sevilla, España: Dpto. de Álgebra, Computación, Geometría y Topología de la Universidad de Sevilla. Recuperado de: http://www.cs.us.es/~jalonso/pub/1991-Lisp-manual.pdf Universidad Veracruzana. (2012). Introducción a Lisp. Veracruz, México. Recuperado de: https://www.uv.mx/aguerra/documents/2012-mpii-02.pdf

Programación Lógica y Funcional

Página 15