Download Programación Scheme - 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
funcional
(si bien impuro, ya que, por
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)
// ERROR
top-level: unbound variable: resultado
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=?
(symbol=?
(symbol=?
(symbol=?
'Hola
'Hola
'Hola
'Hola
'Hola) = true
'Hello) = false
x) = true si x almacena '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:
(lambda (x) (+ x 4))
!   Ejemplo:
=>(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 0.0001)
#[compound 8897184]
GRACIAS…..