El paradigma funcional (4)

• Capítulo 2.2 Abelson & Sussman
• Capítulo 10 PLP: Functional Languages

• Historia del paradigma funcional
• Características del paradigma funcional puro
• Modelo de computación basado en sustitución
• Características de la programación funcional (LISP, Scheme)

1. Evaluación sin efectos laterales: paradigma declarativo y modelo de sustitución
2. Funciones como tipos de datos de primer orden: forma especial lambda
3. Ámbitos de variables: forma especial let
4. Dualidad entre datos y programas: formas especiales eval y apply
5. Listas como elemento fundamental de procesamiento: parejas, cons, car, cdr
6. Recursión

(define (calculadora)
   (display "Introduce parámetros entre paréntesis: ")
   (define params (read))
   (display "Introduce cuerpo")
   (define cuerpo (read))
   (define func (eval (append '(lambda) (list params) (list cuerpo))))
   (display "Introduce argumentos entre paréntesis: ")
   (define args (read))
   (apply func args))

Nota: Este programa no es funcional; realiza pasos de ejecución para leer las expresiones introducidas por el usuario y para imprimir el resultado de su evaluación.

Es importante darse cuenta de que la expresión

(append '(lambda) (list params) (list cuerpo))

devuelve una lista que es una expresión lambda correcta, cuya evaluación va a crear un procedimiento al que se llama después.

Por ejemplo, supongamos que:

(define params '(x y))
(define cuerpo '(+ x y))

Si hiciéramos (append '(lambda) params cuerpo) obtendríamos una lista con 6 elementos:

(append '(lambda) params cuerpo)
-> (lambda x y + x y)

No es lo que queremos; necesitamos obtener la lista (lambda (x y) (+ x y)), una lista de 3 elementos cuyo segundo y tercer elemento son a su vez listas. Eso es lo que hace la expresión:

(append '(lambda) (list params) (list cuerpo))
-> (lambda (x y) (+ x y))

Después la llamada a eval hace el resto.

El bucle read-eval-print en Scheme:

(define (rep-loop) 
   (display "mi-interprete> ")  ; imprime un prompt
   (let ((expr (read)))            ; lee una expresión 
      (cond 
         ((eq? expr 'adios)        ; el usuario quiere parar?
             (display "saliendo del bucle read-eval-print") 
             (newline))
          (else                         ; en otro caso 
             (write (eval expr))   ; evaluar e imprimir 
             (newline) 
             (rep-loop)))))

• En Scheme es posible crear datos compuestos.
• La forma de hacerlo es definiendo una construcción muy simple y usando esa construcción simple para hacer cosas más complicadas.
• El tipo de dato compuesto más simple es la pareja: una entidad formada por dos elementos.
• Se utiliza la función cons para construirla.

Ejemplo:

(cons 1 2) -> (1 . 2)
(define c (cons 1 2))

• Podemos obtener el elemento correspondiente a la parte izquierda con el operador car y su parte derecha con el operador cdr

Ejemplos:

(define c (cons 1 2))
(car c) -> 1
(cdr c) -> 2

Las funciones cons, car y cdr quedan perfectamente definidas con las siguientes ecuaciones:

(car (cons x y)) = x
(cdr (cons x y)) = y

• ¿De dónde vienen los nombres car y cdr?
• Realmente los nombres eran CAR y CDR (en mayúsculas)
• La historia se remonta al año 1959, en los orígenes del LISP y tiene que ver con el nombre que se les daba a ciertos registros de la memoria del IBM 709.

Explicación completa: http://www.iwriteiam.nl/HaCAR_CDR.html

Es posible construir una pareja con cualquier tipo de datos, mezclando distintos tipos de datos:

(define c (cons 'hola #f))
(car c) -> 'hola
(cdr c) -> #f

(define p1 (cons (lambda (x) (+ x 3))
                 5))

¿Cómo se podría llamar a la función de la parte izquierda de la pareja con la parte derecha como argumento?

((car p1) (cdr p1)) -> 8

Podríamos incluso definir una función que trabajara con esta estructura:

(define (procesa-pareja p)
   ((car p) (cdr p)))

• Seguimos en el paradigma funcional
• Una vez creada una pareja no es posible modificar sus contenidos.
• Scheme tiene primitivas para modificar el contenido de las parejas.

Una pareja es también un tipo de datos de primer orden: puede pasarse como argumento y devolverse como resultado de una función.

• Las parejas pueden formar parte de otras parejas.
• Esta última propiedad se denomina clausura de la operación cons.
• El resultado de un cons puede usarse para construir otros conses (parejas).

Ejemplo:

(define p1 (cons 1 2))
(define p2 (cons 3 4))
(define p (cons p1 p2))

Expresión equivalente

(define p (cons (cons 1 2)
          (cons 3 4)))

Podríamos representar esta estructura de esta forma:

Pero se haría muy complicado representar muchos niveles de anidamiento. Por eso utilizamos la siguiente representación, entendiendo las flechas como contiene y no como referencia.

(define p (cons (cons 1
                      (cons 3 4))
                2))

¿Qué figura representaría la estructura anterior?

(cdr (cdr (car p))) -> 4

Es equivalente a la instrucción cadar de Scheme:

(cddar p) -> 4

• El nombre de la función se obtiene concatenando a la letra "c", las letras "a" o "d" según hagamos un car o un cdr y terminando con la letra "r"
• Hay definidas 2⁴ funciones de este tipo: caaaar, caaadr, …, cddddr.

La función pair? nos dice si un objeto es atómico o es una pareja:

(pair? 3) -> #f
(pair? (cons 3 4)) -> #t

(list 1 2 3 4) -> (1 2 3 4)
'(1 2 3 4) -> (1 2 3 4)

(define hola 1)
(define que 2)
(define tal 3)

(list hola que tal) -> (1 2 3 4)
'(hola que tal) -> (hola que tal)

(define a '(1 2 3))
(car a) -> 1
(cdr a) -> (2 3)
(length a) -> 3
(length '()) -> 0
(append '(1) '(2 3 4) '(5 6 7) '()) -> (1 2 3 4 5 6 7)

Definición recursiva con parejas:

• Una parejas en la que el primer elemento es un dato y el segundo el resto de la lista.
• Un símbolo especial '() que denota la lista vacía

Ejemplo:

(cons (1
      (cons 2
            (cons 3
                  '())))))

Ahora se entiende mejor por qué las funciones que permiten recorrer una lista son car y cdr como en el siguiente ejemplo:

(define lista (cons 1 (cons 2 (cons 3 (cons 4 '())))))
(car lista)
(cdr lista)

> (define l1 '(1 2 3 4))
> (cons 'hola l1)
(hola 1 2 3 4)

Lenguajes y Paradigmas de Programación
Curso 2010-2011
Departamento de Ciencia de la Computación e Inteligencia Artificial
Universidad de Alicante

Sitio web realizado con org-mode y el estilo CSS del proyecto Worg