PDF de programación - Capítulo IV: Programación Funcional

CAPÍTULO IV:

Programación Funcional

Prof. Teddy Alfaro

4.1 Introducción a la

Programación Funcional

1

Programación Funcional

Paradigma diferente a los imperativos, que se

aleja de la máquina de von Neumann

Basado en funciones matemática (notación

funcional lambda de Church)

No existen realmente arquitecturas de
computadores que permitan la eficiente
ejecución de programas funcionales

LISP es el primero, del cual derivan Scheme,

Common LISP, ML y Haskell

Funciones Matemáticas

Un función es una proyección de un conjunto

dominio a uno que es el rango

f: D R

La evaluación de funciones está controlada por

recursión y condiciones (imperativos lo hacen
normalmente por secuencias e iteraciones)

Funciones matemáticas entregan siempre el

mismo valor para el mismo conjunto de
argumentos y, por lo tanto, no tiene efectos
laterales.

2

Formas Funcionales

(funciones de orden superior)
Toman funciones como parámetros y/o

producen funciones como resultado

Composición de Funciones

entonces:

h(x) f(g(x))

Construcción. Lista se funciones que se

produce

(f(x), g(x))

Aplicar a todo. Una función se aplica a lista

h f ° g

aplican
[f, g](x)

arg.
(f, (x, y, z))

produce

(f(x), f(y), f(z))

Fundamentos de la PF

La PF pura no usa variables ni asignación
Repetición debe ser lograda con recursión
Un programa consiste de definición de

funciones y aplicación de éstas

La ejecución del programa no es nada más que

la evaluación de funciones

La transparencia referencial se refiere a que la

evaluación de una función simpre produce el
mismo resultado

3

Lenguajes Funcionales

El lenguaje provee algunas funciones básicas,
que son primitivas para construir funciones más
complejas.

Se definen algunas estructuras para representar

datos en los parámetros y resultados de las
funciones.

Normalmente se implementan mediante
interpretadores, pero también se pueden
compilar.

4.2 Introducción al
Lenguaje Scheme

Sintaxis, listas, operadores

básicos, expresiones lambda y

definición de variables

4

Origen de Scheme

Desarrollado en el MIT a mediados del ´70
Es un dialecto de LISP
Usado para enseñanza de programación
Características:

– Pequeño con sintaxis y semántica simple
– Nombres tienen ámbito estático
– Funciones son entitades de primera clase, y

por lo tanto se tratan como cualquier valor

Sintaxis

Palabras claves
Variables
Datos constantes (e.g. números;

caracteres; strings; vectores, listas y
símbolos citados)

Formas estructuradas
Blancos y comentarios (después de ;)

5

Identificadores

Corresponden a palabras claves, variables y
símbolos, que no son sensible a mayúsculas

Se forman de:

– mayúsculas y minúsculas [Á´ .. ´Z´, á´..´z´]
– Dígitos [´0´..´9´]
– Caracteres [? ! . + - * / < = > : $ % ^ & _ ˜ ]

Identificadores no pueden comenzar con ningún
carácter que comienza un número (i.e. dígito, +,
- y .), excepto casos de identificadores como + y
...

Ejemplo de Identificadores

X3 y ?$!!!
Abcd y AbcD
8id

Son válidos
Son el mismo
no es válido

6

Constantes Básicas

String: se escribe usan citado doble (“)

– e.g. “Un string es sensible a Mayusculas”

Un caracter precede de #\

– e.g. #\a

Un número pueden ser enteros, fraccionarios, punto

flotante y en notación científica
– e.g. -365, 1/4, 23.46, 1.3e27

Números complejos en coordenadas rectangulares

y polares
– e.g. 2.7-4.5i [email protected]

Booleanos son los valores #f (falso) y #t (verdadero)

Ambiente Interactivo de Scheme

Corresponde al ciclo: leer, evaluar e imprimir

(denominado REPL).

El sistema entrega un pronto, se ingresa la

expresión, el sistema evalúa y entrega el
resultado.

Ejemplo:

“Hola Scheme”
(Toda constante evalúa en la misma constante)

=> “Hola Scheme”

Es posible cargar y salvar en un archivo para

facilitar el proceso de desarrollo.

7

Listas

Las listas se escriben con paréntesis redondos

(a b c d)

Listas contienen elementos de cualquier tipo, y

se pueden anidar

(lambda (x) (* n n))

Una función se escribe como una lista en

notación prefija, correspondiendo el primer
elemento de la lista a la función y los siguientes
a los argumentos

(+ 3 14) ;=> 17

Funciones Aritméticas

Los nombres +, -, * y / son nombres reservados

para las operaciones aritméticas.

Funciones se escriben como listas en notación

prefija:
;=> 1
(+ 1/2 1/2)
;=> 2/3
(- 2 (* 4 1/3))
(/ (* 6/7 7/2) (- 4.5 1.5)) ;=> 1.0

8

Evaluación de Listas

Toda lista es evaluada, salvo que se especifique

lo contrario con citación simple (quote)

(quote (a b c d)) ;=> (a b c d)
;=> (a b c d)
‘(a b c d)
(a b c d)
;=> ERROR (“a” no es proc.)

Al no usar quote, Scheme trata de evaluar

considerando en el ejemplo a a como variable
de función.

Operadores Básicos de Listas

car devuelve el primer elemento de la lista:

(car ‘(a b c d))

;=> a

cdr devuelve el resto de la lista (sin el primer

elemento):

(cdr ‘(a b c d))

;=> (b c d)

9

Estructura de una Lista

(A (B C) D)

A

B

D

C

Constructores de Listas

cons construye una nueva lista cuyo car y cdr

;=> (a b c d)

son los dos argumentos:
(cons á ´(b c d))
(cons (car ´(a b c))(cdr ´(a b c));=> (a b c)
(cons á ´b)

;=> ?
list construye una lista con todos los

argumentos
(list á ´b ´c ´d)
(list)

;=> (a b c d)
;=> ()

10

Listas Impropias

A

B

D

E

C

(A (B C) D . E) (A . ( (B . (C . ()) . (D . E)))

Variables y Expresiones Let

Let permite definir variable que se ligan a
un valor en la evaluación de expresiones

Sintaxis:

(let ((var1 val1) … ) exp1 exp2 … )

Ejemplo:

(let ((x 2) (y 3))
=> -5

(* (+ x y) (- x y)) )

¡Variables son
sólo visibles
dentro del cuerpo
de LET!

11

Expresiones Lambda

Permite crear un nuevo procedimiento
Sintaxis:

(lambda (var1 var2 … ) exp1 exp2 … )

Ejemplo:

((lambda (x) (* x x)) 3)
;=> 9

¡Una expresión lambda es una objeto tipo procedimiento

que no tiene nombre!

Ejemplo: Expresión Lambda

(let ((square (lambda (x) (* x x))))

(list (square 2)
(square 3)
(square 4)

)

)
;=> (4 9 16)

12

Relación entre Let y Lambda

Nótese que:

(let ((var1 val1) … (varm valm)) exp1 … expn)

equivale a:

((lambda (var1 … varm) exp1 … expn) val1 … valm)

Especificación de Parámetros

Formales

Lista propia de parámetros (var1 var2 ... varn)

((lambda (x y) (list x y)) 1 2)

;=> (1 2)

Parámetros único varr

((lambda x (list x)) 1 2)

;=> ((1 2))

Lista impropia de parámetros (var1 var2 ... varn . varr)

((lambda (x . y) (list x y)) 1 2 3) ;=> (1 (2 3))

13

Definiciones de Nivel Superior

Las variables definidas con let y lambda son
sólo visibles en el cuerpo de las expresiones
(local).

El procedimiento define permite definir variables

de nivel superior (global)

Definiciones de nivel superior permiten

visibilidad en cada expresión donde no sean
escondidas por otro ligado (e.g. Una variable
definida con el mismo nombre mediante let
oculta a la de nivel superior)

Ejemplo de uso de Define

(define pi 3.1416)
;=> pi
(define square (lambda (x) (* x x))))
;=> square
(square 3)
;=> 9
(let ((x 2)(square 4)) (* x square))
;=> 8

14

Abreviación en Definición de

Funciones

La forma:

(define var0 (lambda (var1 … varn) e1 …))

Se puede abreviar como:

(define (var0 var1 … varn) e1 …)

Ejemplo:

equivale a:

(define square (lambda (x) (* x x))))

(define (square x) (* x x))

Expresiones Condicionales

En Scheme también es posible condicionar la

realización de determinada tarea

test consecuencia alternativa)

Sintaxis:

(if

Ejemplo:

(define (abs n) (if (> n 0)
n
(- 0 n)))

(abs -27)

;=> 27

15

Predicados

Procedimientos para expresiones

relacionales

=, <, >, <= y >=

Procedimientos para expresiones lógicos

e.g. (= 3 4)

=> #f

or, and y not

e.g. (and (> 5 2) (< 5 10))

=> #t

Otros Predicados

Lista nula: null?

(null? ´()) => #t

Argumentos equivalentes: eqv?

(eqv? á á)

=> #t

Ejemplo:

(define (reciproco x)

(if (and (number? n) (not (= n 0))

(/ 1 n)
(error ‘reciproco

“reciproco: división no válida”)

)

)

16

Expresión Condicional Múltiple

Scheme provee expresiones que se

evalúan condicionalmente.

Sintaxis:

(cond (test1 exp1) (test2 exp2) … (else expn)

El uso de else es opcional, siendo

equivalente su uso a colocar #t

Ejemplo de Condicional Múltiple

(define abs

(lambda (x)
(cond

)

)

)

((= x 0) 0)

((< x 0) (- 0 x))
(else x)

17

Un ejemplo más complicado

(define nota

(let ((a ((lambda (c)

(lambda (cert lect tar)
(cond
((< c 45) 0)
((> c 60) 0.3)
(else (/ (* 0.3 (- c 45)) 15))

)
) cert)

))
(display "alfa: ") (display a) (newline)
(+ (* a tar)(* (- 1 a) (+(* 0.75 cert) (* 0.25 lect))))

)

)

)
(nota 52.5 60 100)
alfa: .15
;=> 61.21875

Algo más sobre Predicados

Cualquier objeto se interpreta como #t
La lista nula ‘() equivale a #f
Se definen los predicados:

pair? : verifica si es un par (lista propia o

impropia)

number? : verifica si es número
string? : verifica si es un string

18

4.3 Recursión en Scheme

Recursión simple y asignación

Recursión Simple

Un procedimiento recursivo es aquel se

aplica a si mismo.

Ejemplo:

(define length
(lambda (ls)

(if (null? ls)

0
(+ 1 (length (cdr ls))))