Tema_3_Clase_2_Paradigma_Funcional

Vista previa del material en texto

CLASE 2
MODELO DE DESARROLLO DE PROGRAMAS Y 
PROGRAMACION CONCURRENTE
FAC.DE INGENIERIA - UNJu
Paradigma Funcional
PROGRAMACION FUNCIONAL
1Leng de progr.func. 
tiene gran flexibilidad, 
es conciso en su 
notación y su 
semántica es sencilla
Inconveniente 
de estos leng: 
ineficiencia en 
la ejecución
Poderosos mecanismos 
p/controlar la complejidad y 
estructurar el código: son más 
abstractos y matemáticos y no 
pueden manejarse tan fácilmente
PARADIGMA FUNCIONAL
Florencia
Resaltado
Florencia
Resaltado
PARADIGMA FUNCIONAL
PROGRAMAS COMO FUNCIONES
• 1 PROGR.es 1 descripción de 1 cálculo específico, es equivalente a 1 fción matemát. y= f(x) o f:X -> Y. 
El conjunto X se llama el dominio de f, en tanto que el conjunto Y se conoce como el rango de f.
• Se debe pensar en progr.,proced.y fciones.en 1 leng.progr.representado x el concepto matem.de fción
La progr.fcional.pura es completa en Turing xq cualquier cálculo puede ser descripto usando sólo fciones
• En1progr: x representa la entr.e y la salida. En1proced./fción,x repres.los parám.e y los valores devueltos
NO se hace distinción entre progr., proced.y fciones
Importante: en los lenguajes de programación se debe distinguir entre: 
1) Definición de fción: es1declaración que describe la forma en la q debe calcularse una fción
utilizando parámetro
2) Aplicación de función: es1llamada a 1fción declarada utilizando parámetros reales o argumentos
PARADIGMA FUNCIONAL
PROGRAMAS COMO FUNCIONES (cont)
• En la progr.fcional se elimina la asignación como operación disponible, como consecuencia tampoco 
pueden existir ciclos. Un lazo debe tener una variable de control que es reasignada conforme se 
ejecuta el lazo o ciclo, y esto no es posible sin la asignación. 
• Para que las operaciones se repitan en forma secuencia se utiliza la RECURSION, por ej.
void gcd (int u, int v, int* x)
{ int y, t, z ;
Z=u ; y=v; 
While (y !=0)
t=y;
Y= z / y;
Z= t;
}*x=z;
Versión imperativa utilizando un ciclo
int gcd ( int u, int v)
{ if (v==0)return u
else return gcd (v, u / v);
}
Versión funcional con recursión
PARADIGMA FUNCIONAL
PROGRAMAS COMO FUNCIONES (cont)
• Transparencia Referencial: prop.de 1fción.de q su valor depende sólo de los valores de sus argumentos 
y de sus constantes no locales (gcd es transparente referencialmente puesto que su valor depende sólo 
del valor de sus argumentos). 1fción transparente referencialmente sin parámetros deberá siempre 
devolver el mismo valor y por lo tanto no tiene ninguna diferencia con una constante
• La carencia de asignación y la transparencia referencial de la programación funcional hacen que la 
semántica de los programas funcionales resulte particularmente simple: no existe una noción explicita 
de estado, ya que no hay concepto de localizaciones en la memoria con valores cambiantes(una 
localización de memoria implicaría la existencia de una variable) 
• El ambiente de ejecución asocia nombres sólo a valores (y no a localizaciones de memoria) y una vez 
introducido un nombre en el ambiente, su valor no puede cambiar jamás. Esta idea de semántica se 
conoce como semántica de valor, a fin de distinguirla de la semántica de almacenamiento más usual
PARADIGMA FUNCIONAL
PROGRAMAS COMO FUNCIONES (cont)
• Las fciones.deben considerarse como valores que pueden ser calculados por otras fciones. y que 
también pueden ser parámetros de fcionesLas funciones son valores de primera clase
• Composición: es 1de las operac.esenciales de las fciones.. Matemáticamente se define el operador 
de composición “o” como: si f:X -> Y y g:Y-> Z, entonces g o f::X -> Z está dado por (g o f)(x) = g(f(x))
La composición es en sí misma 1fción.que toma 2fciones.como parámetros y produce otra como su 
valor devuelto. Fciones.de este tipo (que tienen parámetros que a su vez son fciones.o que producen 
un resultado que es una fción o ambos) se llaman FUNCIONES DE ORDEN SUPERIOR
PARADIGMA FUNCIONAL
Resumen de las cualidades de los lenguajes de Programación Funcionales
1) Todos los proced.son fciones.y distinguen valores de entrada (parámetros) de los de salida (result) 
2) No existen variables ni asignaciones. Las variables han sido reemplazadas por Parámetros
3) No existen ciclos, estos han sido reemplazados por llamadas recursivas
4) El valor de una función depende sólo del valor de sus parámetros y no del orden de Evaluación o 
de la trayectoria de ejecución que llevó a la llamada
5) Las funciones son valores de primera clase
Florencia
Resaltado
Florencia
Resaltado
Florencia
Resaltado
PARADIGMA FUNCIONAL
Programación funcional en un lenguaje imperativo
1) El estilo y técn.de la progr.fcional pueden usarse en 1leng.Imperativo como C o Pascal, logrando progr. 
con 1 mejor simplicidad de su semántica y claridad. El requisito básico en cualquier leng.de progr.es la 
disponibilidad de la recursión y un mecanismo gral.de fciones.adecuado
2) El problema típico en la progr.de estilo fcional es el costo de llevar a cabo todos los ciclos mediante la 
recursión. Existe 1 forma de p/convertir a una estruct.estándar de ciclo llamada RECURSION TOTAL, 
donde la última operación en un procedim.es llamarse a sí mismo con diferentes argumentos
3) Muchos usos simples de recursión no cumplen con la recursiv.total. Como consec.se inventaron técn. 
p/convertir fciones a fciones recursivas totales mediante parám.de acumulac.q se usan p/pre-calcular 
las operac.q se efectuarán después de la llamada recursiva y pasar los result.a la llamada recurs
PARADIGMA FUNCIONAL
Programación funcional en un lenguaje imperativo (cont)
4) P/evitar que leng.como C o Ada pueden ser usados p/escribir progr.fcionales perfectamente puros, los 
leng.imperat.contienen restricciones q dificultan o imposibilitan la interpretación de progr.en este estilo:
o Valores estructurados como arreglos y registros no pueden ser valores devueltos de las fciones
o No existe forma de construir un valor de un tipo estructurado de manera directa
o Las fciones.no son valores de 1ra.clase, por lo q no es posible escribir fciones de orden superior
Estas restricciones afectan la capacidad de programar en estilo fcional y la forma en la que los métodos 
funcionales pueden ser simulados utilizando constructores imperativos ocasionales
Por ej.en estilo funcional, 1proced.de ordenamiento necesita devolver un arreglo en base a un arreglo de 
entrada. En Ada donde los arreglos pueden ser devueltos como valores de fciones, se puede escribir:
function intsort(A: in IntArray) return Int Array is
-- escriba IntArray es arreglo (parámetro de eentero <>) de inicio de entero …………. End intSort;
En C 1arreglo no puede ser el valor devuelto de 1fción. Además el tamaño de un parámetro de arreglo no 
puede determinarse en C, x lo q debe ser pasado por separado. La fción Int Sort debe declararse:
void IntSort (int a [¨], int b [¨], int size ) {
. . . . . . } 
PARADIGMA FUNCIONAL
SCHEME
A fines de los 50 se desarrolla el 1er.leng.q contenía muchas de las caract.de los leng. fcionales
modernos: LISP (LISt Procesor) en vista de que su estruct.de datos básica es1lista
Representación 
uniforme de 
progr.y datos 
usando 1 sola 
estructura 
gral.de datos
LISTA
La definic.del
leng.usa1intérpre
te escrito en el 
leng.mismo, 
llamado 
intérprete meta-
circular
Dialectos de Lisp:
Common Lisp, 
desarrollado en la 
década del 80 y 
Scheme realizado a 
principios de los 70.
Administración 
automática de 
toda la 
memoria x
parte del sist.en
tiempo de 
ejecución
PARADIGMA FUNCIONAL
Elementos de Scheme
En Scheme todos los progr.y los datos son expresiones y estas son de dos tipos: átomos y listas
Los átomos son 
como las 
constantes y los 
identificadores 
de un leng. 
imperat: incluyen 
nros, cadenas, 
lnombres, las 
fciones y otros 
constructores 
Una lista es 1 
secuencia de 
expresiones 
separadas por 
espacios y 
rodeadas por 
paréntesis
Sintaxis de scheme:
expresión-> átomo | lista
átomo -> número | cadena |
identif.| carácter | booleano
lista -> ‘(expresión –secuencia’)’
PARADIGMA FUNCIONAL
Elementos de Scheme (cont)
Ejemplos de átomos en Scheme:
42 -un número 
“hola” -una cadena
#T - el valor booleano verdadero
# \ a - el carácter ‘a’
Ejemplos de listas en Scheme:
(2.1.2.2.3.1) - una lista de números
(+ 2 3) - una lista formada por el identificador “+” y dos números
(* (+ 2 3) (/ 6 2)) -una lista formada por un identificador seguido por dos listas
Ejemplos de identificadores en Scheme:
a -otro identificador
hola -otro identificador
PARADIGMA FUNCIONAL
Características de Scheme
FORMA PREFIJA: Es la regla de evaluación de Scheme para todas las expresiones
REGLA DE EVALUACION: los progr.son expresiones y necesitan ser evaluados, la semántica está dada x:
1. Los átomos constantes, como números y cadenas se evalúan a sí mismos
2. Los identificad. se buscan en el ambiente actual y se reemplazan x el valor allí encontrado, el 
ambiente en Scheme es 1 tabla de símbolos dinámicamente mantenida q asocia identificad.con valores
3. C/elemento de la lista se evalúa recursivamente como1expresión (en algún orden no 
especificado), la 1ra.expresión de la lista debe evaluarse a 1fción, esta fción se aplica entonces a los 
valores evaluados del resto de la lista
Analizando los ej. anteriores: 
42, “hello”, # T y #\ \a se evalúan a sí mismas; a y hello son buscados en el ambiente y sus valores son 
devueltos 
( + 2 3) se evalúa buscando el valor de “+” en el ambiente-devuelve un valor de fción. La fción de adición 
está predefinida y después aplicando esta función de Adición a los valores de 2 y 3. Devuelve el valor 5
De manera similar (* ( + 2 3) (/ 6 2)) se evalúa y devuelve 15
La Lista (2. 1.2.2.3.1) NO puede evaluarse ya que su 1ra.expresión 2. es una constante que no es función
PARADIGMA FUNCIONAL
Comparación de expresiones entre C y Scheme
“C” SCHEME
3 + 4 *5 ( + 3 ( * 4 5 ))
(a == b) && (a! = 0) (and(= a b ) (not (= a 0)))
gcd(10,35) (gcd 10 35)
Gcd gcd
Getchar() (read-char)
La regla de eval.de Scheme es de orden aplicativo: todas las sub-expresiones se evalúan 
1ro.de modo q el árbol de la expresión resulta evaluado desde las hojas hasta la raíz. Por ej. en 
la expresión (* (+ 2 3) (+ 4 5 ) ) se evalúa 1ro.las2adiciones y después las expresión resultantes, 
es decir el producto (* 5 9) . 
PARADIGMA FUNCIONAL
Control de la ejecución
Los ciclos se pueden realizar x llamadas recurs.pero la selección debe ser provista por fciones explícitas
Las fciones.básicas q se ocupan de esto es la función if que es similar al constructor if-then-else, así 
como la función cond (conditional) que es similar al constructor if –elsif
(if (= a 0) 0 If a = 0 entonces devuelve 0 
(/ 1 a)) else devuelve a 1/a
(cond(( = a 0) 0) If a=0 entonces devuelve 0
(( = a 1 ) 1) elsif a=1 entonces devuelve 1
(else (/1 a))) else devuelve 1/a
PARADIGMA FUNCIONAL
La estructura de datos básica en Scheme es la lista, todas las otras estructuras deben presentarse en 
forma de listas. Una lista puede representar un arreglo, un registro o cualquier otro dato. 
Por ej. se muestra una representación de lista de un árbol de búsqueda binario formado por:
(“caballo”(“vaca”() (“perro” () () ))
(“cebra” (“bisonte” () () ) () ))
Un nodo de este árbol es una lista de tres elementos (name left right) donde name es una 
cadena, y left y right son lo árboles hijos que también son listas. 
Por lo tanto la lista dada representa el árbol: 
Estructuras de Datos en Scheme
PARADIGMA FUNCIONAL
Scheme tiene muchas fciones de lista predefinidas, pero las funciones básicas comunes a todos los 
sistemas LISP son las de selector car (contenido del registro de direcciones) y cdr (contenido del registro 
de decremento) que calculan el principio y el final de una lista y las funciones de constructor cons, que 
añade un nuevo elemento al principio de una lista existente. Por ej.
Si L es la lista (1 2 3) entonces:
(car L)
 1
(cdr L)
 (2 3 )
(cons 4 L)
 (4 1 2 3 )
Una lista L es un puntero a una caja de dos punteros: uno dirigido a su car y el otro a su cdr.
Funciones para el manejo de listas en Scheme