Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Unidad 2- Programación funcional

No description

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Unidad 2- Programación funcional

Interests
Education
Skills
Experience
References
.
.
Unidad 2 - Programación Funcional.
De aquí que la implementación de un lenguaje que permita crear programas con el enfoque de una función matemática, debía ser basado en el recurso función de los lenguajes de programación.
Si ignoramos cómo un programa computa sus datos y nos fijamos sólo en qué computa, podemos ver al mismo como una función matemática que dada una entrada, devuelve una salida; se representa por Programa : Input -> Output ó output = Programa(input).
Entre la concepción de una función matemática y la de una función en los lenguajes de programación tradicionales, existían diferencias:

Lenguajes de programación: Hay distinción entre la definición de la función (descripción de lo que va a hacer la función mediante los parámetros formales) y la aplicación de la misma (llamada con los parámetros actuales). Las variables refieren una zona de memoria donde se almacena un valor

Matemáticas: La distinción no es clara, a menudo el término " variable independiente " se usa tanto para el parámetro formal como actual.


Programación Funcional
PLATFORMS
Social
SOCIAL
SEO
CMS
Instituto Tecnológico Superior de Zongolica
Programación lógica y funcional
Una función matemática es una regla que asocia a cada x de un conjunto X de valores, un único y de otro conjunto Y de valores; se representa por:

f:X → Y ó por y = f(x)
Por su atención

Muchas Gracias
M.S.C. Norma Leticia Hernández Chaparro
Programación funcional.

Se basa en el concepto de función (que no es más que una evolución de los predicados), de corte más matemático
Características

Los ordenadores se han programado utilizando lenguajes muy cercanos a las peculiaridades de la propia máquina: operaciones aritméticas simples, instrucciones de acceso a memoria, etc.

Un programa escrito de esta manera puede ocultar totalmente su propósito a la comprensión de un ser humano, incluso uno entrenado. Hoy día, estos lenguajes pertenecientes al paradigma de la Programación Imperativa han evolucionado de manera que ya no son tan crípticos.
El hecho de que en los lenguajes funcionales no existen las variables y existe la transparencia referencial, hacen la semántica de los programas funcionales particularmente conveniente:

No existe estado, ya que no existe concepto de localización de memoria ni de variable.
Características generales de la Programación Funcional:

1.- Ausencia de efectos colaterales

Se dice que una función (f x y z) tiene un efecto colateral si los valores de x, y, y/o z cambian en el entorno de llamada durante la aplicación de la función a sus argumentos, o si alguna otra acción ocurre mientras se evalúa f.

Los lenguajes funcionales, en particular Haskell, tienen un rico conjunto de datos atómicos predefinidos, tales como los numéricos int, integer (de mayor precisión que el anterior), float, double, etc., y además los tipos char y bool.
2.2. Funciones - Recursividad
Semántica limpia

Algunas de las características que hacen que un lenguaje sea útil y confiable son en las cuales el lenguaje significa lo que dice -no es ambiguo- y los resultados de un programa pueden verificarse. En un lenguaje funcional, f(3) siempre devolverá el mismo resultado, mientras que en un lenguaje imperativo, como Pascal, éste puede no ser el caso.
El estilo de la programación funcional puede ser usado y lo está siendo cada vez más en lenguajes imperativos por las mismas razones por las cuales el uso de los lenguajes funcionales se ha incrementado: la simplicidad de la semántica y la resultante claridad de los programas.

Ejemplos de lenguajes imperativos:

°BASIC °C °D 1
°Fortran °Pascal °Pauscal en español
°Perl °PHP °Lua
°Java °Python °Go


El requerimiento básico para programar funcionalmente en cualquier lenguaje es que el mismo permita la recursión así como un mecanismo de funciones general y adecuado.
Un problema típico en este estilo de programación es el costo de ejecución de los ciclos mediante la recursión. Incluso con los procesadores modernos, que reducen sustancialmente la sobrecarga de la llamada a procedimiento, las implementaciones recursivas son más lentas que las que usan los ciclos standard.
Resumiendo Características
Los programas escritos en un lenguaje funcional están constituidos únicamente por definiciones de funciones (funciones puramente matemáticas)

Verifican Transparencia referencial (el significado de una expresión depende únicamente del significado de sus subexpresiones)

No hay efectos colaterales

No hay variables

No construcciones estructuradas como la secuencia
o la iteración = funciones recursivas.
Haskell (1/2)

La parte más interesante de Haskell en relación con los tipos son
los constructores, las tuplas y las listas. Una tupla es un dato
compuesto donde el tipo de cada componente puede ser distinto.
Haskell (1/2)
Las listas son colecciones de cero o más elementos de un mismo tipo (a diferencia de las tuplas que pueden tenerlos de diferentes). Los operadores utilizados son el [] y (:).
El primero representa una lista vacía, y el segundo denominado cons o constructor, permite añadir un elemento al principio de una lista, construyendo la lista en función de agregar elementos a la misma, por ejemplo:

4 : 2 : 3 : []

da lugar a la lista [4, 2, 3]. Su asociatividad es hacia la derecha. Un tipo
particular de lista son las cadenas de caracteres.

El constructor utilizado para declarar el tipo correspondiente a las distintas funciones es el símbolo →.


2.2. Funciones.
Funciones de orden superior

Los lenguajes funcionales modernos utilizan una poderosa
herramienta de programación: las funciones de orden superior.
Haskell en particular considera que las funciones pueden aparecer en cualquier lugar donde aparezca un dato de otro tipo (por ejemplo permitiendo que sean almacenadas en estructuras de datos, que sean pasadas como argumentos de funciones y que sean devueltas como resultados).
En el paradigma de la programación funcional, un programa se considera una función matemática, la cual describe una relación entre una entrada y una salida y donde el concepto de estado o variable se elimina completamente
Ejemplo:

Si se tiene la expresión "Sea x tal que f(x) = 2 “ , no se distingue con claridad si se refiere a la definición de la función constante de valor 2 o al punto x específico en el que una función f ya definida toma el valor 2. Las variables siempre se refieren a un valor y no a una localización de memoria. No hay concepto de localización de memoria y por tanto la expr. x=x+1 no tiene sentido.
La programación funcional debe por esto eliminar el concepto de variable excepto como nombre de un valor. Por lo anterior, se concibió que en la Programación Funcional la asignación no fuera permitida como instrucción.
Como no hay variables ni asignación, tampoco existen los ciclos al estilo de los de los lenguajes tradicionales ya que los mismos trabajan con una variable de control que se va reasignando (decrementando o incrementando). Esto se logra en un lenguaje funcional mediante la recursión.
En programación funcional pura no existen variables, sólo existen
Constantes
Parámetros y
Valores

En la práctica la mayoría de los lenguajes de programación funcionales no son puros pues retienen algunas nociones de variables y asignaciones
Si lo programamos funcionalmente en un lenguaje procedural como ADA, quedaría como sigue :

procedure MCD(u,v:integer):integer;
begin
if (v=0) then return u
else
return MCD(v,u mod v);
end; {MCD}
Consecuencias de ausencia de variables y asignación

El valor de cualquier función depende solamente de los valores de sus parámetros y no de llamados previos a otras o a la misma función

Así como que el valor de cualquier función no depende del orden de evaluación de sus parámetros, lo cual se conoce por el nombre de transparencia referencial,

Lo que facilita el empleo de la programación funcional se utiliza en aplicaciones concurrentes
El ambiente de ejecución asocia valores con nombres, no con localizaciones de memoria; una vez que un nombre entra al ambiente, su valor no cambia. Es por esto que se habla en este caso de semántica de valores, para distinguir este tipo de semántica de la usual (semántica de almacenamiento o semántica de apuntadores).

En la programación funcional, debemos estar listos para manipular funciones sin restricciones arbitrarias. En particular, las funciones deben ser vistas como valores en sí ellas, las cuales pueden ser ejecutadas por otras funciones y las cuales pueden ser también parámetros de otras funciones, esto se expresa diciendo que estas funciones son valores de primera clase.
2.- El valor de una expresión solo depende de los valores de sus sub expresiones, si las tiene.

Una función definida con todos los parámetros por valor y donde no se hacen asignaciones a las variables globales, no tiene efectos colaterales.

La mayoría de las implementaciones de LISP incorporan algunos efectos colaterales y tipos de datos integrados. Éstos han sido incluidos para hacer más sencillo un código fácilmente legible y las implementaciones eficientes.
El manejo del almacenamiento de los datos es implícito, ciertas operaciones asignan almacenamiento en el momento necesario y cuando se vuelve inaccesible o no referenciado se libera automáticamente, con uso de recolección de basuras, código de programa más simple y corto.

Las funciones son valores de primera clase. Eso significa que las funciones tienen la misma jerarquía que cualquier otro valor. Una función puede ser el valor de una expresión, puede pasarse como argumento y puede colocarse en una estructura de datos.
EXPRESIONES LÓGICAS
La expresión lógica (conocida también como expresión booleana) es una de las más útiles para procesar información en un procedimiento.
Forma parte de una sentencia de programa que realiza preguntas de tipo verdadero o falso sobre una propiedad, una variable o algún otro tipo de datos en el código del programa.
Una expresión lógica es cualquiera que pueda evaluarse como verdadera o falsa.

Por ejemplo:
Hoy es Sábado
Edad < 18
A + B = 7

Todas estas expresiones se pueden evaluar como verdaderas o falsas, por lo tanto son expresiones lógicas o booleanas.

OPERADORES LOGICOS
AND
OR
NOT
OPERADORES LOGICOS
Visual Basic te permite comparar más de una expresión lógica o evaluar más de un criterio en una sola instrucción.
Para enlazar expresiones se utilizan los operadores lógicos

AND (Y CONJUNCION)
Sólo si todas las expresiones son verdaderas el resultado de la expresión es verdadero. Si una sola de las expresiones es falsa, toda la expresión es falsa.

TABLA DE VERDAD
NOT (NEGACION)
Operador utilizado para indicar la negación lógica de una expresión, de tal forma que si dicha expresión es por sí sola evaluada como verdadera al anteponer el operador NOT será evaluada como falsa y viceversa.

NOT(Edad > 18). Si la edad no es mayor que 18, la expresión es verdadera.

^
TABLA DE VERDAD
1.3 DEFINICIÓN DE FUNCIONES
En programación, una función es una sección de un programa que calcula un valor de manera independiente al resto del programa.
Es una subrutina o subprograma (también llamada procedimiento, función o rutina), como idea general, se presenta como un sub-algoritmo que forma parte del algoritmo principal, el cual permite resolver una tarea específica.
Una función tiene cuatro componentes importantes:

Los  parámetros, que son los valores que recibe la función como entrada;

El  código de la función, que son las operaciones que hace la función; y

El  resultado (o valor de retorno), que es el valor final que entrega la función.

En esencia, una función es un mini-programa. Sus tres componentes son análogos a la entrada, el proceso y la salida de un programa.
1.4 Disciplina de Tipos
Disciplina:
Es la coordinación de actitudes con las cuales se instruye para desarrollar habilidades, o para seguir un determinado código de conducta u "orden".
En los lenguajes de programación con disciplina de tipos, cada tipo representa una colección de valores o datos similares.

El conocer los tipos de las funciones ayuda a documentar los programas y evitar errores en tiempo de ejecución.

Un lenguaje tiene disciplina de tipos si los errores de tipos se detectan siempre y cuando es necesario determinar los tipos de todos los operandos, ya sea en tiempo de compilación o de ejecución.
Java
*Tiene disciplina de tipos

Haskell
Los tipos de parámetros de las funciones (y de estas mismas) se conocen en tiempo de compilación (ya sea por declaración del usuario o por inferencia de tipos.

C
No tiene disciplina de tipos por:
Permite funciones con parámetros sobre los que no se realiza comprobación de tipos.
Los programas bien tipados se pueden reconocer en tiempo de compilación, un programa bien tipado se puede utilizar sin efectuar comprobaciones de tipo en tiempo de ejecución.
Estando garantizado que no se producirán errores de tipo durante el computo.

*Polimorfismo: Permite que una misma función se pueda aplicar a parámetros de diferentes tipos, dependiendo del contexto en el que la función se utilice.
*Disciplina estática de tipos:
1.5 TIPOS DE DATOS
Los tipos de datos hacen referencia al tipo de información que se trabaja, donde la unidad mínima de almacenamiento es el dato, también se puede considerar como el rango de valores que puede tomar una variable durante la ejecución del programa.

TIPOS DE DATOS PRIMITIVOS
El tipo de dato carácter es un dígito individual el cual se puede representar como numéricos
(0 al 9), letras (a-z) y símbolo ($,_).
NOTA: En lenguaje java la codificación
Unicode permite trabajar con todos los caracteres de distintos idiomas
Tipo de dato Rango Tamaño de bits
char 0 a 65535 16 bits

CARACTERES
Este tipo de dato puede ser real o entero, dependiendo del tipo de dato que se vaya a utilizar.

Enteros: son los valores que no tienen punto decimal, pueden ser positivos o negativos y el cero.
tipo de dato: byte tamaño= 8 bits
tipo de dato: short tamaño= 16 bits
tipo de dato: int tamaño= 32 bits
tipo de dato: long tamaño= 64 bits

NUMÉRICOS
Este tipo de dato se emplea para valores lógicos, los podemos definir como datos comparativos dicha comparación devuelve resultados lógicos.

tipo de dato: boolean Rango= true - false

BOOLEANOS
2.1. El tipo de datos.
El sistema de tipos de Haskell es uno de los más sofisticados que existen. Es un sistema polimórfico, que permite una gran flexibilidad de programación, pero a la vez mantiene la correctitud de los programas.
Haskell utiliza un sistema de inferencias de
tipos, es decir sabe el tipo resultante de una expresión, por lo que las anotaciones de tipo en un programa son opcionales.

Una de las utilidades de este tipo de datos es cuando una función tiene que
devolver más de un valor:
predSuc :: Integer → (Integer,Integer)
predSuc x = (x-1,x+1)
Por ejemplo consideremos la siguiente función

dosVeces :: (Integer → Integer) → Integer → Integer
dosVeces f x = f ( f x )

Entonces al evaluar las siguientes funciones, obtenemos:

MAIN> dosVeces (*2) 10
40:: Integer
MAIN> dosVeces inc 10
12:: Integer
Las funciones en Haskell se definen en dos partes.
– La primera identifica el nombre, el dominio y el
intervalo de la función.
– La segunda describe el significado de la función

Si omitimos la primera línea, Haskell deriva la primera
línea dándole en sentido más amplio posible.
Esta función max3 es un ejemplo de función polimórfica.
• Una función polimórfica es aquella que se aplica bien a argumentos de varios tipos.
2.1. El tipo de datos.
Tipos de Datos Simples
2.2. Funciones
Caracteres
Cadenas
Tipos numéricos: Int, Float
2.2 Funciones
Una función es un grupo de instrucciones con un objetivo en particular y que se ejecuta al ser llamada desde otra función o procedimiento. Una función puede llamarse múltiples veces e incluso llamarse a sí misma (función recurrente).
Componentes
• Los parámetros, que son los valores que recibe la función como entrada;
• El código de la función, que son las operaciones que hace la función; y
• El resultado (o valor de retorno), que es el valor final que entrega la función.
Funciones de orden superior
Una función es de orden superior si toma una función como argumento o devuelve una función como resultado.
2.3. Intervalos
Un intervalo es un espacio métrico comprendido entre dos valores. Los intervalos pueden referirse al intervalo de una variable o al intervalo de un array
El intervalo de una variable está definido como la diferencia entre el valor más alto y el valor más bajo que esa variable puede guardar.
En el caso de una variable entera, la definición está restringida a números enteros, y el intervalo cubrirá todos los números dentro de su intervalo (incluyendo el máximo y el mínimo).
El intervalo de un array son los límites superior e inferior del mismo.
2.4 Operadores
Es un símbolo que indica que debe ser llevada a cabo una operación especificada sobre un cierto número de operandos (número, función, vector, etc.).
Operadores Principales
Operadores Unarios
Operadores De Multiplicación
Operadores Aditivos
Operadores De Desplazamiento
Operadores Relacionales Y De Tipo
Operadores De Igualdad
Operadores Lógicos, Condicionales Y Null
Operadores De Asignación Y Anónimos
2.5 Aplicaciones de las listas
Funciones elementales sobre Listas LISP dispone de las siguientes funciones para manipular listas:
 -(CAR List) Retorna el primer elemento de la lista List.
 -(CDR List) Retorna la cola de la lista List.

Constructores de Listas
Constructores de Listas Como las listas desempeñan un papel central en LISP , existen múltiples formas de construir una lista:
 -(APPEND List 1 List 2… List n) Esta función concatena las listas List 1, List2 , …, List n.
-(CONS Elem List) Retorna una lista cuyo primer elemento es Elem y cuya cola es List.
 -(LIST Elem1 Elem2 … Elem n) Esta función retorna una lista formada por los elementos Elem 1, Elem 2, …, Elem n.
Árboles
Un árbol es ordenado si el valor de cada nodo es mayor que los de su subárbol izquierdo y mayor que los de su subárbol derecho.
Definiciones de distintos tipos de árboles
Full transcript