Tema 3 Clase 3 Paradigma Funcional

Vista previa del material en texto

CLASE 3
MODELO DE DESARROLLO DE PROGRAMAS Y 
PROGRAMACION CONCURRENTE - 2019
FAC.DE INGENIERIA - UNJu
Paradigma Funcional
PROGRAMACION FUNCIONAL
Tiene gran 
flexibilidad, es 
conciso en su 
notación y su 
semántica es 
sencilla
Inconveniente: 
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
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 conj. X se llama dominio de f y el conj. Y se conoce como el rango de f.
• Los progr.,proced.y fciones. se representan x FUNCIONES. La progr. fcional.pura es completa 
en Turing xq cualquier cálculo puede ser descripto usando sólo fciones.
• En1programa: x representa la entr.e y la salida. En1proced./fción,x repres.los parám.e y los 
valores devueltos
NO se distingue entre programa, procedimientos y fciones
Importante: en los lenguajes de programación se debe distinguir entre: 
1) Definición de fción: es1declaración q describe como calcular 1fción usando parámetro
2) Aplicación de función: es1llamada a 1fción usando parámetros o argumentos
PARADIGMA FUNCIONAL
PROGRAMAS COMO FUNCIONES (cont)
• Se elimina la asignación como operación disponible, en 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. 
• P/q las operaciones se repitan en forma secuencial se usa 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 ya q sólo 
del valor de sus argumentos). 1fción transparente referencialmente sin parámetros debe 
siempre devolver el mismo valor y no tiene ninguna diferencia con una constante
• La carencia de asignación y la transparencia referencial hacen que la semántica sea simple: 
no existe una noción explicita de estado, ya q no 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. 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 q pueden ser calculados x otras fciones. y q 
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 es 1fción.que toma 2fciones.como parámetros y produce 
otra como su valor devuelto. Fciones.de este tipo (con parámetros q a su vez son fciones.o q 
producen un resultado q es una fción o ambos) se llaman FUNCIONES DE ORDEN SUPERIOR
PARADIGMA FUNCIONAL
Cualidades de los lenguajes de Programación Funcionales
1) Los proced.son fciones.y distinguen valores de entrada (parám.) de los de salida (result) 
2) No existen variables ni asignaciones. Las variables se reemplazan x Parámetros
3) No existen ciclos, se reemplazan x llamadas recursivas
4) El valor de 1fción depende sólo del valor de sus parámetros y no del orden de Evaluación.
5) Las funciones son valores de primera clase
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 1 mejor simplicidad de su semántica y claridad. El requisito es la disponibilidad de la 
recursión y un mecanismo gral.de fciones.adecuado
2) El problema típico en la progr. fcional es el costo de llevar a cabo todos los ciclos mediante la 
recursión. Existe 1 forma de p/convertir a 1estruct.estándar de ciclo llamada RECURSION TOTAL, 
donde la última operación en 1proced.es llamarse a sí mismo con diferentes argumentos
3) Muchos usos simples de recursión no cumplen con la recursiv.total, x lo q 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 se usen p/escribir progr.fcionales perfectamente puros, los 
leng.imperat.contienen restricciones q dificultan o imposibilitan la interpretación 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 (no es posible escribir fciones de orden superior)
Esto afecta la capacidad de programar en estilo fcional y la forma en la que los métodos 
funcionales pueden ser simulados utilizando constructores imperativos ocasionales
PARADIGMA FUNCIONAL
Programación funcional en un lenguaje imperativo (cont)
En estilo funcional, 1proced.de ordenamiento necesita devolver un arreglo en base a1arreglo de 
entrada. 
En Ada los arreglos pueden ser devueltos como valores de fciones, x ej.:
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
LISP
A fines de los 50 se desarrolla el 1er.leng.q contenía características 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 2tipos: á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 listasEjemplos 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 deben ser evaluados, la semántica se da 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 encontrado, 
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, la fción evalúa a 
1ra.expresión de la lista, y luego se aplica a los valores del resto de la lista
Ej.:42, “hello”, # T y #\ \a se evalúan a sí mismas; a y hello se buscan en el amb. y devuelven sus valores
( + 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 “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. 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 recursivas
La función if es similar al constructor if-then-else
(if (= a 0) 0 If a = 0 entonces devuelve 0 
(/ 1 a)) else devuelve a 1/a
La función cond (conditional) es similar al constructor if –elsif
(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, las demás estructuras deben presentarse 
en forma de listas. 1 lista puede representar 1 arreglo, 1 registro o cualquier otro dato. 
X 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 1 lista de 3 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) q calculan el principio y el final de 1lista 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