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.
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
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 (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)))
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
(cond (<p1> <e1>) (<p2> <e2>) ..... (<pn> <en>) (else <en+1>))
Sintaxis del cond
Expresiones condicionales y predicados
(cond [<p1> <e1>] ... [<pn> <en>] [else en+1])
Sintaxis del cond
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=? '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]))
! 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)
! 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))))
! 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))
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]