PDF de programación - Programación Funcional Lisp-DrScheme - Primera Parte

Programación Funcional

Lisp-DrScheme
Primera Parte

Dr. Oldemar Rodríguez Rojas
Escuela de Informática
Universidad de Nacional

Programación Funcional

!   La programación funcional es un paradigma de programación

declarativa basado en la utilización de funciones.

!   Los programas escritos en un lenguaje funcional están
constituidos únicamente por definiciones de funciones,
entendiendo éstas no como subprogramas clásicos de un
lenguaje imperativo, sino como funciones puramente
matemáticas, y por tanto, hay la carencia total de efectos
laterales.

!   Otras características propias de estos lenguajes son la no
existencia de asignaciones de variables y la falta de
construcciones estructuradas como la secuencia o la iteración,
lo que obliga en la práctica a que todas las repeticiones de
instrucciones se lleven a cabo por medio de funciones
recursivas.

Scheme

!   Scheme es un lenguaje de programación
(si bien impuro, ya que, por
funcional
ejemplo, sus estructuras de datos no son
inmutables) y un dialecto de Lisp.

!   Fue desarrollado por Guy L. Steele y Gerald
Jay Sussman en la década de los setenta e
introducido en el mundo académico a través
de una serie de artículos conocidos como los
Lambda Papers de Sussman y Steele.

Scheme

!   Scheme, como todos los dialectos de Lisp, tiene una sintaxis
muy reducida, comparado con muchos otros lenguajes. No
necesita reglas de precedencia, ya que, en esencia, carece de
operadores: usa notación prefija para todas las llamadas a
función.

!   Scheme facilita la programación funcional. La programación
funcional pura no precisa de variables globales ni sufre de
efectos secundarios, y es, por tanto, automáticamente segura en
presencia de procesos concurrentes (thread-safe).

!   También permite la creación de procedimientos anónimos.
!   El estándar de Scheme es también minimalista. Ello conlleva
ventajas e inconvenientes. Por ejemplo, escribir un compilador o
intérprete de Scheme que sea fiel al estándar es más fácil que
implementar uno de Common Lisp, uno de sus antesesores.

¿Dónde bajar Scheme?

(PLTScheme ó DrScheme):



http://plt-scheme.org/
http://racket-lang.org/

Ejemplo:
> (+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))
57
> (define tamaño 2)
tamaño
> tamaño
2
> (+ 3 tamaño)
5
> (* 2 tamaño)
4

Definición de Variables
(define Pi 3.14159)
Pi
(define radio 10)
Radio
(define circunferencia (* 2 Pi radio))
circunferencia
> circunferencia
62.8318

Funciones en Lisp

Ejemplo:

(define (cuadrado x) (* x x))

> (cuadrado 2)
4

Ejemplo:
(define (circunferencia radio)


(* Pi radio))



> (circunferencia 4)
12.56636

Sintaxis de las funciones:

(define (<nombre> <parámetros formales>)

(cuerpo))

Ejemplo:

(define (suma_cuadrados x y)
(+ (cuadrado x) (cuadrado y)))

> (suma_cuadrados 2 3)
13

Ejemplo: Composición de Funciones

> (define (f1 a)
(suma_cuadrados (+ a 1) (- a 1)))

> (f 5)
52


El modelo de sustitución para
evaluar funciones

(f1 5)
(suma_cuadrados (+ 5 1) (- 5 1))
(+ (cuadrado (+ 5 1)) (cuadrado (- 5 1)))
(+ (* (+ 5 1) (+ 5 1)) (* (- 5 1) (- 5 1)))
(+ (* 6 6) (* 4 4))
(+ 36 16)
52

Funciones Booleanas

(define (es-5? n)
(= n 5))

> (es-5? 5)
#t
> (es-5? 7)
#f

Funciones Booleanas
(define (esta-entre-5-6? n)
(and (< 5 n) (< n 6)))


(define (esta-entre-5-6-o-sobre-10? n)
(or (esta-entre-5-6? n) (>= n 10)))

Sintaxis del if

(if <predicado> <consecuencia>


<alternativa>)



Ejemplo:

(define (f2 x)
(if (>= x 2) (* x x)
(if (and (< x 2) (> x -2)) (+ x 1)
(/ x 2))))

> (f2 4)
16
> (f2 0)
1

Expresiones condicionales y predicados
Sintaxis del cond

(cond



(<p1> <e1>)
(<p2> <e2>)

(<pn> <en>)
(else <en+1>))

.....

Ejemplo:

(define (f3 x)
(cond ((>= x 2) (+ (* x x) 1))
((= x 0) 2)
(else (* x x x))))

> (f3 3)
10


Expresiones condicionales y predicados
Sintaxis del cond

(cond
[<p1> <e1>]
...
[<pn> <en>]
[else en+1])



Ejemplo:

(define (intereses cantidad)
(cond
[(<= cantidad 1000) 0.040]
[(<= cantidad 5000) 0.045]
[else 0.050]))

Sentencias read y write - Evaluando un documento

(define (calcula-nota x y z)
(/ (+ x y z) 3))

(define (paso? n)
(>= n 70))

(define (nota)
(newline)
(write "Deme las notas")
(newline)
(calcula-nota (read) (read) (read)))

(define (resultado)
(if (paso? (nota)) (write "GANO")
(write "AMPLIACION")))

=>(resultado)

"Deme las notas"
90
80
70
"GANO"

Definiciones Internas:

(define (todo)
(define (calcula-nota x y z)

(/ (+ x y z) 3))
(define (paso? n)

(>= n 70))
(define (nota)

(newline)
(write "Deme las notas")
(newline)
(calcula-nota (read) (read) (read)))

(define (resultado)

(if (paso? (nota)) (write "GANO")
(write "AMPLIACION")))

(resultado))

todo
=>(todo)
"Deme las notas"
90
40
50
"AMPLIACION“

=>(resultado)
top-level: unbound variable: resultado

// ERROR



Procesamiento simbólico
!  Un símbolo es una secuencia de

caracteres precedida por un signo de
comillas simple:

!  Ejemplos:

'El 'perro 'comio 'un 'gato 'chocolate
'dos^3 'y%en%lo?

Procesamiento simbólico
! Scheme tiene una sola operación básica de

manipulación de símbolos: symbol=?,

!   Es una operación de comparación, recibe dos
símbolos y produce true si y sólo si los dos
símbolos son idénticos:

!   Ejemplos;

!   (symbol=? 'Hola 'Hola) = true
!   (symbol=? 'Hola 'Hello) = false
!   (symbol=? 'Hola x) = true si x almacena 'Hola
!   (symbol=? 'Hola x) = false si x almacena 'Hello

Procesamiento simbólico
!   Los símbolos fueron introducidos a la computación por los
investigadores en inteligencia artificial que querían diseñar
programas que pudieran tener conversaciones con la gente.

!   Por ejemplo la función respuesta, que responde con alguna

observación a los diferentes saludos:

(define (respuesta s)
(cond
[(symbol=? s 'buenos-dias) 'Hola]
[(symbol=? s 'como-esta?) 'bien]
[(symbol=? s 'buenas-tardes) 'buenas]
[(symbol=? s 'buenas-noches) 'estoy-cansado]))

Recursión y Recursión Lineal

!  Ejemplo:

! Versión Recursiva

(define (factorial n)
(if (or (= n 0) (= n 1))
1
(* n (factorial (- n 1)))))

! Versión Recursiva Lineal (Recursión Lineal)

(define (factorial1 n)
(fac-iter 1 1 n))

(define (fac-iter resultado i n)
(if (> i n)
resultado
(fac-iter (* resultado i) (+ i 1) n)))

Modelo de Sustitución

(factorial1 4)
(fac-iter 1 1 4)
(fac-iter 1 2 4)
(fac-iter 2 3 4)
(fac-iter 6 4 4)
(fac-iter 24 5 4)


!  Ejemplo 2:

! Versión Recursiva

(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1)) (fib (- n 2))))))

(define (fib1 n)
(fib-iter1 0 1 0 n))

(define (fib-iter1 ant res i n)
(if (>= i n)
ant
(fib-iter1 res (+ res ant) (+ i 1) n)))

! Versión Recursiva Lineal (Recursión Lineal)

(define (fib1 n)
(fib-iter 1 0 n))

(define (fib-iter a b n)
(if (= n 0)
b
(fib-iter (+ a b) a (- n 1))))

Ejemplo 3:

Funciones como Parámetro

!  Ejemplo 1:

(define (serie1 a n)
(if (> a n)
0
(+ a (serie1 (+ a 1) n))))


!  Ejemplo 2:

define (serie2 a n)
(if (> a n)
0
(+ (* a a) (serie2 (+ a 1) n))))

!  Ejemplo 3:

(define (serie3 a n)
(if (> a n)
0
(+ (/ 1 (+ (* a a) 1)) (serie3 (+ a 1) n))))



! Toda serie es de la forma:

! Programa general

(define (serie f a n)
(if (> a n)
0
(+ (f a) (serie f (+ a 1) n))))


!   Ejemplo:



(define (cuadrado a)


(* a a))



(define (sum f a n)

(if (> a n)
0


(+ (f a) (sum f (+ a 1) n))))



(define (serie2 a n)


(sum cuadrado a n))

(define (termino i)


(/ i (+ (cubo i) 1)))

(define (serie3 a n)


(sum termino a n))

Funciones Lambda

!  Las funciones Lambda permiten definir
Funciones Anónimas, con la siguiente
sintaxis:

!  (lambda (<parámetros>) <cuerpo>)

!   Ejemplo:

!   Ejemplo:

(lambda (x) (+ x 4))

=>(define cubo
(lambda (x) (* x x x)))
cubo
=>(cubo 3)
27

!  Ejemplo:

(define (serie f a n)
(if (> a n)
0
(+ (f a) (serie f (+ a 1) n))))

(define (serie4 a n)
(serie (lambda (i) (/ i (+ (cubo i) 1))) a n))


Uso del let

! Sintaxis:



(let ((<var1> <exp1>)
(<var2> <exp2>)



<varn> <expn>))


<cuerpo>)

. . . . . .

Ejemplo: Una función que calcula el sueldo
neto:

!  sueldo=HT*SPH - 20% deducciones

(define (salario HT SPH)
(let ((sal-bruto (* HT SPH))
(deduccion (* (* HT SPH) 0.2)))
(- sal-bruto deduccion)))

Funciones que retornan funciones
! Ejemplo: Escriba una función que recibe HT, SPH y retorna

una función que recibe como parámetro el porcentaje de
deducción para calcular el salario neto:


(define (salario2 HT SPH)
(lambda (x)
(- (* HT SPH) (* (* HT SPH) x))))

=>((salario 10 100) 0.2)
800.0
=>(salario 10 100)
#[compound 8896152]

! Ejemplo: Escribiremos una función que
calcula la derivada de una función, que
como se sabe es una función definida como
sigue:

cuando h es pequeño.

Código:

(define (derivada f h)
(lambda (x)
(/ (- (f (+ x h)) (f x)) h)))

=>((derivada cubo 0.0001) 5)
75.0015000099324
=>(derivada cubo