Resumen Programacion Logica y Funcional PDF

Preview

Summary

Resumen de la asignatura para rendir examen final ...

Description

Unidad 1: Introducción al Paradigma de Programación Declarativa Programación Declarativa: Este paradigma describe las relaciones entre los datos, sin precisar los algoritmos, describe qué debe ser computado y no cómo debe ser computado. No posee estructuras de control ni variables mutables, ni asignación. En contraste con la programación imperativa no hay un flujo de programa determinado para las acciones. Definición: la programación declarativa es una forma de programa en la que: implica la descripción de un problema dado en lugar de proveer una solución para dicho problema. Utilizando la lógica como lenguaje de programación: un programa es un conjunto de fórmulas lógicas que resultan ser la especificación del problema que se pretende resolver y la computación se entiende como una forma de inferencia o deducción en dicha lógica. Programación Declarativa vs Programación imperativa

PROGRAMA ⇨Transcripción de un algoritmo INSTRUCCIONES ⇨ Órdenes a la máquina MODELO DE COMPUTACIÓN  ⇨  Máquina de estados VARIABLES ⇨ Referencias a la memoria

INSTRUCCIONES ⇨ Fórmulas lógicas MODELO DE COMPUTACIÓN ⇨ Máquina de inferencias VARIABLES ⇨ Variables lógicas

PROGRAMA ⇨ Especificación de un problema

Ventajas: ● Descripciones compactas y muy expresivas. ● Desarrollo del programa no tan orientado a la solución de un único problema. ● Permite al programador concentrarse en la formulación del problema y lo libera del control del algoritmo. ● Los programas son más fáciles de manejar, transformar y verificar. Lenguaje de Programación Declarativa Hay multitud de lenguajes declarativos o con inspiración declarativa (como SQL). Se consideran dos grandes familias de lenguajes declarativos: ● Lenguajes lógicos, cuyo representante más conocido es Prolog. ● Lenguajes funcionales, cuyo representante más puro es Haskell. Características: Los lenguajes declarativos están orientados a buscar la solución del problema, sin preocuparse por la forma de llegar a ello. ✓ Los programas están formados por un conjunto de definiciones o ecuaciones, las cuales describen lo que debe ser calculado, no en sí la forma de hacerlo. ✓ Las variables sólo pueden tener asignado un solo valor a lo largo de la ejecución del programa, lo cual implica que no puede existir asignación destructiva. ✓ El orden de la ejecución no resulta importante debido a que no existen efectos colaterales. ✓ Las expresiones o definiciones pueden ser usadas como valores y por lo tanto se pueden tratar como argumentos de otras definiciones. ✓ El control de la ejecución no es responsabilidad del programador.

Unidad 2: Paradigma Funcional Paradigma Funcional: La programación funcional intenta tratar el problema de la programación desde un punto de vista matemático y utiliza la noción de función como base para la construcción de los algoritmos y estructuras de datos. Visión tradicional Los lenguajes imperativos reflejan en gran medida la arquitectura de las computadoras, y por lo tanto resulta complicado razonar sobre los programas (por ejemplo, conocer sus propiedades) En los lenguajes imperativos existen dos tipos de construcciones: los comandos  y las expresiones .

Los comandos permiten manejar explícitamente el flujo de control y las expresiones son utilizadas para calcular valores. Los lenguajes imperativos poseen la característica de poder realizar modificaciones implícitas a la memoria de la computadora. Esas modificaciones se denominan: “efectos laterales” los cuales no son claramente visibles en el código del programa, y tienen consecuencias no deseables para el razonamiento de propiedades. ¿Cuál es el modelo en el que se basan los lenguajes imperativos? ⇨ Existen dos componentes fundamentales: la unidad de procesamiento (CPU) y la memoria, y ambas están conectadas de manera de poder intercambiar información ⇨ La CPU entiende instrucciones que le permiten modificar la memoria, y las mismas deben tener un orden determinado (secuencia explícita de instrucciones) para poder conocer con exactitud los cambios a realizar ⇨ La memoria determina la existencia de un estado implícito, que puede ser alterado, dando por resultado un lenguaje dinámico ⇨ Al finalizar la ejecución de un programa, el estado implícito contiene el valor de resultado (además de muchos otros valores, irrelevantes al resultado del cálculo que se quería realizar) Programación Funcional: Lenguaje Estático En matemáticas no existe la noción de estado implícito que puede ser modificado, haciendo innecesaria la presencia de instrucciones. Existen valores que pueden ser expresados de maneras complejas mediante expresiones; el conjunto de valores conocidos conforman de esta manera un estado explícito, dando como resultado un lenguaje estático. Transparencia Referencial En este paradigma el cálculo de los valores se realiza mediante un proceso de reemplazo de subexpresiones que no tienen un orden preestablecido, dando como resultado un control implícito de operación. Al no existir efectos laterales, dos expresiones sintácticamente iguales darán el mismo valor, propiedad conocida como transparencia referencial. E sta es una propiedad donde todas sus expresiones pueden ser reemplazadas con su resultado sin que cambie el comportamiento del programa resultante. ⇨ esta propiedad es el pilar de la habilidad de razonamiento ⇨ El resultado de la evaluación de una función, es independiente del momento y lugar desde el que se la referencia. Además cada expresión designa un único valor independientemente del modo en que se evalúa. Ej.: Como podemos observar, la función triple se puede definir de diferentes formas, pero gracias a esta propiedad el resultado será el mismo ya que en sí se trata de la misma función. triple x = 3 * x triple’ x = x + x + x Función En un lenguaje funcional programar consiste en construir definiciones y, utilizando la computadora, evaluar expresiones. En el caso de este paradigma, debe incorporarse la noción de función como un concepto primitivo del lenguaje, las cuales se agregan para suprimir las instrucciones . - Esta función, que puede involucrar un cierto número de otras funciones, se expresa en notación basada en principios matemáticos normales. Las expresiones que contienen ocurrencias de nombres de funciones definidas por el programador se evalúan usando las definiciones dadas como reglas de simplificación o reducción que convierten expresiones en formas imprimibles. Una característica de la programación funcional es que si una expresión posee un valor bien definido, entonces el orden en el cual la computadora lleve a cabo la evaluación no afecta el resultado. Ej.: En el siguiente ejemplo podemos ver en el lenguaje funcional la definición de la función tamanio, la cual dada una lista me retorna la cantidad de elementos que posee. tamanio [] = 0 tamanio (x:xs) = 1 + tamanio xs Script ¿Cómo construimos definiciones de funciones? Construyendo scripts; Un script es una lista de definiciones Por ejemplo: cuadrado z = z * z.

La función cuadrado toma un valor z como argumento y retorna el valor de z multiplicado por sí mismo como resultado. Estas expresiones pueden contener variables y la definición introduce un binding (o ligadura) entre un nombre y un valor dado. Expresiones y Valores La característica más importante de la notación matemática es que una expresión se usa para denotar (o describir) un valor. El valor de una expresión depende de los valores de las expresiones que la constituyen (si es que existen) y estas sub-expresiones pueden reemplazarse libremente por otras que posean el mismo valor. Reducción La computadora evalúa una expresión reduciéndola a su forma equivalente más simple e imprimiendo su resultado. Esto se conoce como proceso de evaluación, simplificación y reducción Ejemplo: Reducir la expresión cuadrado (3+4) Una forma sería: ⇨cuadrado(3+4) ⇨ cuadrado 7 (+) ⇨ 7 x 7 (cuadrado) ⇨ 49 (x)

⇨cuadrado (3+4) ⇨ (3+4)x(3+4) (cuadrado) ⇨7 x (3+4) (+) ⇨7 x 7 (+) ⇨49 (x)

Otra forma sería: No importa la forma que utilizamos, siempre el resultado final es el mismo. El proceso para evaluar una expresión básicamente es simple: sustituir y simplificar usando reglas primitivas y reglas definidas por el programador en forma de definiciones. De aquí surge el concepto de expresión canónica, una expresión es canónica (o está en forma normal) si no puede reducirse. Tipos de Reducción Existen dos formas de reducción las cuales se denominan: Orden aplicativo (o ansioso): Aunque no sea necesario, se deben evaluar todos los argumentos. Orden normal (o "lazy", perezoso): Esta técnica consiste en que la expresión no es evaluada hasta que su valor no se necesita. La desventaja de este esquema en los lenguajes imperativos es que cada vez que un mismo parámetro formal es encontrado debe ser reevaluado. Tipos de Datos Existen dos clases de tipos: ▪ Tipos básicos: Los tipos básicos son aquellos cuyos valores son primitivos. Ej.: num (números), bool (valores de verdad), char (caracteres). ▪ Tipos compuestos o derivados: Los tipos derivados o compuestos son aquellos cuyos valores se construyen de otros tipos. Ej.: (num, char), el tipo de pares de valores donde la primer componente es un número y la segunda es un char; (num->num), el tipo de funciones cuyos argumentos son números y retornan otro número; [num], una lista de números. Funciones y Definiciones El valor más importante en la programación funcional es el valor de una función. Matemáticamente hablando, una función es una regla de correspondencia que asocia cada elemento de un tipo dado A a un único miembro de un segundo tipo B, f: A →B. Si x denota un elemento de A, f(x) denota el resultado de aplicar la función f a x. Existe una diferencia entre el valor de una función y la definición de ella, para una misma función pueden existir muchas definiciones. Por ejemplo: double x = x + x y double’ x = 2 * x Las dos definiciones describen distintos procedimientos para obtener la correspondencia pero double y double’ denotan la misma función (Transparencia referencial). Si no se ingresa nada con respecto al tipo, éste puede inferirse: dado que la operación * (multiplicación) está permitida para los números (tipo num).

Formas de Definición Existen diferentes mecanismos para definir funciones: ▪ Ecuaciones simples: se define una función mediante una única ecuación. Ej.: cuadrado x = x * x ▪ Análisis por casos: Esta definición consiste de varias expresiones, cada una de las cuales se distingue por expresiones booleanas llamadas “guardas”. Las guardas agotan todas las posibilidades y deben ser disjuntas además se asume que existe un orden en la evaluación. Ej.: min x y : |si xy = y ▪ Definiciones locales: estas funciones me permiten definir valores o expresiones localmente durante la ejecución de la función. La palabra where se utiliza para introducir una definición local cuyo alcance es la expresión del lado derecho de la definición de f Ej.: f x y : |si x>10 = x + a |otherwise = x - a, where a= cuadrado(y + 1) ▪ Patrones (pattern matching): Es posible definir funciones usando los patrones, estos deben ser completos, cubrir todos los casos y ser disjuntos, dos patrones no pueden ser verdaderos al mismo tiempo, además que debemos agregarlos en un orden correcto ya que el sistema unifica con la primera igualdad encontrada. Ej.: Esta función lo que me permite es retornar el segundo elemento de una lista, en caso de ser lista vacía se unificará con el patrón [ ], y en caso contrario la lista se igualará de acuerdo a los parámetros nombrados, donde _ será el primer elemento aunque como no necesito conocer su valor lo ignoro, luego y unificara con el segundo valor de la lista que incluso este puede ser [ ] y luego xs a modo de ejemplo unificará con todo el resto de la lista. segundoElemento [] = [] segundoElemento (_:y:xs) = y ▪ Funciones recursivas: Como lo indica su nombre la función debe contar con las características de una función recursiva como ser contar con el caso base y el caso recursivo. Ej.: La función factorial donde: fac 0 = 1 //caso base fac (n+1)=(n+1) * fac (n) // caso recursivo ▪

Funciones de alto orden o de orden superior: Son aquellas funciones que manipulan otras funciones ya sea como argumentos o retornando otra función. (Concepto ligado a la parcialización)

Sistemas de Tipos Como todos los lenguajes de programación, estos cuentan con un sistema de tipos el cual es el mecanismo por para formalizar la introducción de tipos de datos. Definiendo cada uno de los tipos de datos que aceptará dicho lenguajes y las operaciones ligados a los mismos. La propiedad más importante de un sistema de tipos en programación funcional es que es posible determinar el tipo de una expresión sin evaluarla. Ya que como sabemos en Haskell, se puede saber que tipo de función es mediante una secuencia de comandos. En caso de no definir el tipo de función Haskell le asignará el tipo de datos más genérico posible en base a los operadores que contenga la definición. Por ej.: Si no definimos el tipo de función que sería último, Haskell automáticamente asignará ultimo:  [a] -> [a], utilizando la variable de tipo genérica. Pero tomando como ejemplo la segunda definición, al haber operadores matemáticos Haskell determinara que se trata de una función que manipula números por lo que le asignara ultimo :: [Int] -> [Int]. ultimo [] = [] ultimo [] = [] ultimo (_:y) = y+1*3 ultimo (_:y) = y

Polimorfismo El concepto de polimorfismo se define en contraposición con monomorfismo donde un objeto pertenece a un solo tipo. Los sistemas de tipos polimórficos tienen la capacidad de definir variables de tipo que identifican genéricamente a cualquier tipo con el que se pueda instanciar. Como el caso del ejemplo anterior, una seria una función polimórfica y la otra definición seria monomórfica.

Estructuras de Datos: Listas, Tuplas, Funciones Listas Una lista es una colección ordenada de valores donde todos los elementos de una lista deben ser del mismo tipo. Además pueden existir listas de listas. Ej.: Una lista formada por los enteros 1 al 5 sería: [1, 2, 3, 4, 5] ó [1..5] ó [1, 2, ..5]. Listas por Compresión Representan otra notación para las listas, se emplea una sintaxis adoptada de la forma convencional para escribir conjuntos en matemáticas: [|;.....] En donde denota una expresión arbitraria y es una expresión booleana o un generador. Ej.: xs = [x| x ← xs] Operaciones Estas listas vienen ligadas a un conjunto básico de operaciones: ▪ Concatenación: Dos listas pueden ser concatenadas para formar una lista más larga ▪ Longitud: La longitud de una lista es el número de elementos que ésta contiene. ▪ Head y Tail: Permiten tomar tanto el elemento de la cola como de la cabecera ▪ Take: Me permite toma una cantidad X de argumentos de una lista ▪ Takewhile: Similar al take, solo que este toma como argumento principal una condicion bool. ▪ Map y Filter: La función map no permite aplicar una función a cada elemento de una lista produciendo una nueva. La función filter toma un predicado y una lista y retorna una nueva lista con los elementos que cumpla dicho predicado Expresiones lambda Calculo Lambda: La principal base teórica del paradigma funcional es el Cálculo Lambda desarrollado en la década de los 30 por Alonzo Church como modelo de computación con el mismo poder computacional que una Máquina de Turing. El cálculo lambda proporciona una notación muy simple de definición de funciones matemáticas y establece una sintaxis para representar expresiones y unas reglas de reducción o evaluación para transformarlas. Sólo son necesarias tres reglas sintácticas para definir las expresiones del cálculo lambda: ● Expresión lambda para definir funciones sin nombre, se refiere a la sintaxis para determinar estas. expresión-λ ::= variable | constante | abstracción | aplicación ● Abstracción para dar un nombre a una expresión lambda y permitir poder abstraerla para luego representar otras expresiones a partir de esta. abstracción ::= \variable.expresión-λ ● Aplicación para evaluar una expresión lambda, como lo indica su nombre es el mecanismo el cual me permite evaluar a la expresión. Esta se consigue reemplazando el argumento formal por el argumento actual dentro del cuerpo de la expresión. aplicación ::= (expresión-λ)expresión-λ Ej.: Aquí surge el concepto de función anónima, es aquella la cual podemos construirla sin ser nombrada ya que mediante las expresiones lambda podemos representarla. Ya que estamos manipulando dos parámetros es necesario que la expresión lambda contenga todas las variables. Definición sin λ: sumarDiezVeces x y = x*10 + y*10 Definición con λ:  diezVeces = (\x y -> x*10 + y*10)

Reducción o evaluación Este es el mecanismo para evaluar las expresiones lambda y se consigue cuando en el cuerpo de la expresión (\x -> e) se aplica a un parámetro actual dado por la expresión s, resultando la expresión (\x -> e) s cuyo valor se calcula reemplazando el parámetro formal x por el parámetro actual s dentro del cuerpo e y operando la expresión resultante.

Ejemplo de evaluación de expresiones-λ de un solo argumento: (\x -> 2*x+1) (5+3) 2*(5+3)+1 2*8+1 16+1 17

(\x -> (\y -> (x*10 + y*10)) 3 (3*2) (\y -> (3*10 + y*10)) (3*2) (\y -> (3*10 + (3*2)*10)) (\y -> (300 + 600)) 900

(\x y -> x*10 + y*10) 3 (3*2) Como se observa al ir reemplazando el argumento actual más a la izquierda en el cuerpo de la expresión lambda se irá aplicando la evaluación e irán desapareciendo las variables. Parcialización o aplicación parcial Este es un mecanismo que permite representar funciones de varios argumentos mediante funciones de un único argumento. Consiste en realizar la llamada a una función utilizando sólo algunos de los parámetros que están más a la izquierda permitiendo que esta retorne una nueva función a la cual solo le faltan los argumentos que no fueron enviados. Ej.: Una función la cual recibe 3 argumentos y realiza diversas operaciones. fun :: Int → Int → Int → Int fun x y z = x * (2 * y + z ) fun 2 -> fun y z = 2 *(2 * y + z) fun 2 4 -> fun z = 2*(2 * 4 + z) fun 2 4 3 -> 22 Como observamos al mandar el argumento 2, la función se aplica de manera parcial y retornará una función la cual solo recibe 2 argumentos para completar su expresión. En el segundo caso, recibe dos argumentos y retorna una función que recibe dos argumentos. Y en el último caso al mandar los 3 parámetros se aplican de manera total y retorna el valor de la expresión resultante. Funciones de orden superior Son aquellas funciones que manejan funciones, estas toman una función como parámetro o devuelve una función como resultado. Las expresiones lambda son útiles para representar argumentos de funciones de orden superior. Ej.: función que devuelve el resultado de aplicar dos veces la función que recibe. dosVeces:: (Int-> Int) -> Int-> Int dosVeces f x = f (f x) Por ejemplo usando como argumento la función inc x = x + 1 (con expresión lamba: (\x -> x + 1)), y algún parametro x podemos representarla la función de orden superior mediante una expresión lambda. (\f x -> f (f x)))

(\f -> (\x -> f (f x))) (\f -> (\x -> f (f x))) inc 10 (\x -> inc (inc x))) 10 (\x -> (\x’ -> (inc x) + 1)) 10 (\x -> (\x’ -> (\x’’ -> x + 1) + 1)) 10 (\x -> (\x’ -> (\x’’ -> 10 + 1) + 1)) (\x -> (\x’ -> 11 + 1)) 12 Tipos Genéricos Son aquellas definiciones de funciones que aceptan como parametro cualquier tipo de datos ósea la variable de tipo. Ej.: Tomemos en cuenta la función head definida en el estándar Prelude de Haskell. Esta función me permite retornar el primer elemento de una lista, ya que estas listas pueden ser de números, booleanos, de caracteres, de tuplas o incluso listas de listas se utiliza la variable de tipo “a”. head ::[a]->a head (x:xs)=x Principio de inducción La recursividad se apoya en el principio de inducción, este principio es ampliamente utilizado en matemáticas para demostrar que se cumple una propiedad para cualquier valor del ámbito que se esté tratando (1) La afirmación P es cierta para un valor inicial n0 (caso base). (2) P será cierta para un valor n > n0, si es cierta para el valor anterior a n, es decir, si P es cierta para (n-1) entonces lo será para n. Recursión en listas Al no existir estructuras repetitivas, la mani...