Capítulo 7: Programación Funcional

Scheme es un leng. de programación con un núcleo estrictamente funcional
y con extensiones que permiten realizar programación imperativa.  En
este capítulo el énfasis va a estar en la parte funcional.

Se trata de un lenguaje minimalista: pocas construcciones fundamentales.
El resto de las características están definidas a partir de las
fundamentales.

En este curso se usará Scheme/Tk que incluye bibliotecas para programar
interfaces gráficas.  Instale en su PC Linux/x86 la siguiente distribución:

http://kaolin.essi.fr/STk/Binary/STk-4.0.1-1.i586.rpm


El primer encuentro: el top level
*********************************

- Para lanzar scheme/tk:

  % stk
  STk>

- Toda implementación de scheme posee un top level a partir del cual
  Ud. podrá:

  + evaluar expresiones
  + definir procedimientos
  + cargar archivos con procedimientos
  + etc.

- Hello world:

  + ingrese:
    STk> (display "hello world")
    hello worldSTK>

    Lamentablemente el prompt queda en la misma línea que hello world

  + ingrese:
    STk> (begin (display "hello world") (newline))
    hello world
    STk>

- Para salir de scheme/tk:

  STk> (exit)
  %

- En Scheme todo tiene valor!

  El top level de Scheme evalúa todas las expresiones que ingrese el usuario.
  Ejemplos:

                            Expresión           Resultado
  STk> 1                    Un entero x
  1                                             x 
  STk> "hello world"        Un string s
  "hello world"                                 s
  STk> +                    Un símbolo
  #[subr +]                                     su contenido
  STk> (+ 1 2)              Una invocación de un procedimiento
  3                                             el resultado de la invocación

- Durante el curso usaremos la notación x => y:

  (+ 1 2) => 3

  y significa: el resultado de evaluar x es y.

Tipos en Scheme
***************

- Booleans: #t  #f

- Números enteros:  0, 1, 123, -5

  No está especificado en número de bits: a veces 30 bits, 32 y a veces
  infinito!

- Números reales: 3.14159

  Típicamente se representan en 64 bits IEEE.

- Strings: "hola que tal", ...

  La evaluación de un string es siempre el mismo string.

- Símbolos: a, b, +, *valor*

  La evaluación de un símbolo es su valor asociado.  Se usan
  como variables en los programas.

- Caracteres: #\a #\;

- Vectores: #(1 #t #\. "hoola" a #(2 3))

  Los vectores son heterogéneos!
  La evaluación de un vector es el mismo vector.

- Listas: (1 #t #\. "hoola" a #(2 3))

  Una lista se evalúa de la siguiente forma:
  + Primero se evalúan todos sus elementos
  + El resultado de evaluar el primer elemento debe ser un procedimiento P
  + El resultado de evaluar los demás elementos son los argumentos
  + Se invoca P sobre los argumentos

  ¡Los programas en Scheme se representan mediante listas!

Quote
*****

- En el top level se puede evitar la evaluación con la forma especial
  quote:

  (quote 1) => 1
  (quote a) => a
  (quote (a b c)) => (a b c)

- Azúcar sintáctico: 'exp es equivalente a (quote exp)

  '1 => 1
  'a => a
  '(a b c) => (a b c)
  ''a => (quote a)
  '''a => (quote quote a))

Variables
*********

- Las variables son símbolos.

- Variables globales: se define con (define var exp)

  Ej. (define pi 3.14159)
      (define msg "hello world)
      (define pi/2 (/ pi 2))

- Variables locales: son los argumentos de un procedimiento.

Procedimientos
**************

- Un procedimiento se denota:

  (lambda (x y z) (+ x y z))

  El resultado de la evaluación de (lambda ...) es un procedimiento.
  Durante la invocación, x, y y z que enlazan con los argumentos de
  la invocación.

  En general:
  (lambda (sym1 sym2 ...) exp1 exp2 ...)

- Típicamente un procedimiento se almacena en una variable global:

  (define suma3 (lambda (x y z) (+ x y z)))

  Lo que es equivalente a (azucar sintáctico):

  (define (suma3 x y z) (+ x y z))

- El paso de parametros es por valor

Condicionales
*************

- Para evaluar en forma condicional se usa la forma especial if:

  (if (> 2 1) (display "si") (display "no")) => "si"

  En general: (if bexp texp fexp)

  + Se evalúa bexp.
  + Si no es #f: se evalúa texp y se entrega su resultado (sin evaluar fexp)
  + En es #f: se evalúa fexp y se entrega su resultado (sin evaluar texp)

- También existe la forma especial cond:

  (cond
    ((< x y) "menor")
    ((> x y) "mayor")
    (else    "igual") )

  En general:
    (cond
      (bexp1  texp1)
      (bexp2  texp2)
      ...
      (else   eexp) )

  Se evalúa bexp1.  Si no es #f se evalúa texp1 y se entrega el resultado.
  En este caso nunca se evalúan bexp2, texp2, etc.  En caso contrario,
  se evalúa bexp2 y se opera como en el caso anterior.  Si todos los
  bexpk son falsos, se evalúa eexp y se entrega el resultado.

Iteración
*********

Hasta la versión 4 no había iteración.
En general se reemplaza por la recursividad.

- Ejemplo: factorial

  (define (fact n)
    (if (= n 0)
       0
       (* (fact (- n 1))) ))

En la versión 5 aparece do.

Variables locales
*****************

- Let: introduce variables locales.

  (let ( (x (+ a b))
         (y (/ c d)) )
    (+ (* x x) (* y y)) )

  En general:
    (let ( (sym1 ini1)
           (sym2 ini2)
           ... )
      exp )

  Introduce las variables sym1 sym2 ... con valores iniciales ini1 ini2.
  El alcance de sym1 sym2 es únicamente exp.  Esto significa que en:

   (let ( (x 1) )         equivale a: (let ( (x0 1) )
     (let ( (x (+ x 2))                 (let ( (x1 (+ x0 2))
            (y (+ x 3)) )                      (y  (+ x0 3)) )
        (+ x y) )                         (+ x1 y) )

  Let no es fundamental, pues se puede reemplazar por lambda:

   (let ((x a) (y b)) (f x y)) <=> ((lambda (x y) (f x y)) a b)


- Let*: parecido a let pero modifica el alcance de las variables

   (let* ( (sym1 ini1)
           (sym2 ini2)
           ... )
      exp)

   Como en let, pero el alcance de sym1 es ini2, ini3, ... y exp.
   El de sym2 es ini3, ini4, ... y exp. Etc.

   (let ( (x 1) )          equivale a: (let ( (x0 1) )
     (let* ( (x (+ x 2))                 (let ( (x1 (+ x0 2))
             (y (+ x 3)) )                      (y  (+ x1 3)) )
        (+ x y) )                          (+ x1 y) )

   Let no es fundamental porque:

   (let* ((x a) (y b)) (f x y)) <=> (let ((x a)) (let (y b) (f x y)))

Procedimientos estándares para manipular números
************************************************

- number?  determina si un objeto es un número (real o entero)
- integer? % pero si es entero

- = < <= > >=  para comparar números

- (max x1 x2 ...)  y (min x1 x2 ...)

- (+ x1 x2 ...) y (* x1 x2 ...)

- (- x1 x2 ...) y (/ x1 x2 ...)

  Ojo: (/ 3 2) => 1.5 pero (quotient 3 2) => 1 y (remainder 3 2) => 1

- sqrt exp log sin cos tan asin acos atan

- (expt x y) calcula x elevado a y

Procedimientos estándares para manipular strings
************************************************

- (make-string 4 #\x) => "xxxx"

- (string #\, #\; #\&) => ",;&"

- (string-length "123") => 3

- (string-append "hola" "que" "tal") => "holaquetal"

- string=? string<? string<=? string>? string>=?  para la comparación de strings

- string-ci=? string-ci<? ... idem pero case insensitive

- (substring "123456789" 5 7) => "67"

- (string-ref "12345" 2) => #\3

- (define s "12345")          => s
  (string-set! s 2 #\a)       => nada
  s                           => "12a45"
  (string-set! "12a45" 2 #\z) => nada
  s                           => "12a45"

  Los strings, vectores y listas son objetos.

Listas
******

En scheme como en los demás dialectos de todo gira en torno a las listas.
Los procedimientos fundamentales son car, cdr y cons:

- (car '(1 2 3)) => 1

- (cdr '(1 2 3)) => (2 3)

- (car '()) o (cdr '())   => error

- (cons 0 '(1 2 3)) => (0 1 2 3)

- (car (cons x l)) <=> x  y  (cdr (cons x l)) <=> l

- (cons 1 2) => ( 1 .  2 )    lo que no es *propiamente* una lista

  En realidad (1 2 3) <=> ( 1 . ( 2 . ( 3 . () ) ) )

  (cdr '( 1 . 2 ) ) => 2

- (list? '(1 . 2)) => #f    verdadero si se trata de una lista *propiamente*

- (pair? '(1 . 2)) => #t

- (null? '())      => #t    falso si no es ()

Otros procedimientos estándares

- (list 'a "hola" 3) => (a "hola" 3)

- (length '(1 2 3)) => 3

- (length '())      => 0

- (append '(a (b)) '((c))) =>  (a (b) (c))  los argumentos deben ser listas

- (reverse '(1 2 3)) => (3 2 1)

- (member 'b '(a b c)) => (b c)             membresía

- (member 'd ('a b c)) => #f

- (assoc 'b '((a 1) (b 2) (c 3))) => (b 2)  manejo de listas de asociación

Programación con listas
***********************

- Sumar los números de una lista.  Ej. (suma-l '(1 2 3)) => 6

  (define (suma-l l)
    (cond
      ((null? l) 0)
      (else      (+ (car l) (suma-l (cdr l)))) ))

- Obtener los valores en una lista de asociación.  Ej.
  (sims '((a 1) (b 2))) => (1 2)

  (define (sims l)
    (cond
      ((null? l) '())
      (else      (cons (cdr (car l)) (sims (cdr l)))) ))

- Invertir una lista, i.e. reverse en base a car, cdr, cons, append

  (define (rev l)
    (cond 
      ((null? l) '())
      (else      (append (rev l) (list (car l)))) ))

  Sol. eficiente:

  (define (rev l) (rev2 l '()))
  (define (rev2 l r)
    (cond
      ((null? l) r)
      (else (rev2 (cdr l) (cons (car l) r))) ))

- Ejercicio: append en base a car, cdr, cons

Map
***
Ej.:  (map f '( 3 5 8)) es la lista ((f 3) (f 5) (f 8))

(define (map proc l)
  (cond
    ((null? l) '())
    (else (cons (proc (car l)) (map proc (cdr l)))) ))