Lenguajes y Paradigmas de Programación
 

Abstracción de datos

Nota
Lectura:
Abelson & Sussman, apartado 2.1 y 2.2.1 (páginas 79--106)

Parejas en Scheme

Hemos comentado que una de las características fundamentales de los lenguajes de programación es la posibilidad de agregar datos simples para formar estructuras más complicadas. Muchos lenguajes de programación proporcionan la idea de un array en el que poder almacenar un número de elementos. En Scheme la forma más sencilla de acumulación es la pareja (pair).

La clase pasada vimos cómo se podían construir listas en Scheme (con la instrucción list). Pero veremos en el tema de esta semana que una lista es un tipo particular de estructura de datos que se puede construir usando las parejas.

La función que construye una pareja es la función cons:

(cons x y)

donde x e y son dos datos cualquiera. El resultado es un nuevo dato de Scheme que es una pareja. Por ejemplo, a continuación vemos algunos ejemplos de uso de cons:

> (cons 1 2)
(1 . 2)
> (cons 'hola #f)
(hola . #f)

La expresión (1 . 2) es la forma que tiene Scheme de representar una pareja formada por el número 1 y el 2. Una pareja es un dato agregado que es también un dato de primera clase en Scheme. Puede ser el valor de una variable, puede ser el argumento de una función, puede ser devuelto por una función y puede ser parte de una estructura mayor. ¿Qué podemos hacer con una pareja? ¿Cuáles son las funciones que podemos usar sobre parejas? Existen dos, y te puedes imaginar para qué sirven:

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

Las funciones de acceso a la pareja, que permiten obtener los valores que la componen, son car y cdr. Con la función car obtenemos el primer elemento de una pareja y con la función cdr el segundo.

Nota
¿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.

Puedes encontrar una explicación completa en: http://home.planet.nl/~faase009/HaCAR_CDR.html

Al ser las parejas objetos de primer orden, también pueden usarse como elementos de otras parejas. Por ejemplo, podemos construir dos parejas que guarden dos números y que nos sirvan para definir dos puntos de dos dimensiones, y después definir un segmento que va del primer punto al segundo:

(define p1 (cons 2.0 3.0))
(define p2 (cons 0.0 0.0))
(define s1 (cons p1 p2))

Por último, existe una función que nos permite saber si un objeto es atómico o es una pareja: pair?. Ya veremos en el tema siguiente la necesidad de esta función para poder recorrer estructuras jerárquicas formadas por parejas de parejas. Un ejemplo de su utilización es el siguiente código:

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

Consultar los ejemplos del libro en los que se usan parejas para representar distintos tipos abstractos de datos: números racionales (numerador y denominador), números complejos (partes real e imaginaria), puntos (coordenadas x e y), intervalos (límites inferior y superior) y segmentos de líneas (punto inicial y final). Es importante darse cuenta de que en el caso de los segmentos de rectas pensamos en la representación como una pareja que contiene dos puntos, no como tres parejas que contienen cuatro números (eso es lo que significa respetar la abstracción de datos).

Los siguientes diagramas se denominan diagramas "box-and-pointer" (caja y puntero) y sirven para representar los objetos pareja. El nombre a la izquierda de la pareja representa el nombre (variable) que le hemos dado a la pareja y la caja dividida en dos representa el contenido de la pareja.

La agregación de datos no tiene por qué ser primitiva

En la mayoría de lenguajes de programación el mecanismo de agregación de datos (el array o lo que sea) parece que debería ser una parte necesaria del núcleo del lenguaje, no algo que pudieras implementar como un usuario del lenguaje. Pero si tenemos un lenguaje en el que las funciones son objetos de primera clase podríamos usar una función para representar una pareja:

(define (cons x y)
  (lambda (which)
    (cond ((equal? which 'car) x)
          ((equal? which 'cdr) y)
          (else (error "Bad message to CONS" message)) )))

(define (car pair)
  (pair 'car))

(define (cdr pair)
  (pair 'cdr))

La llamada a cons devuelve un objeto (una función) que puede responder a dos mensajes (usaremos más esta terminología cuando hablemos de programación orientada a objetos). El objeto funciona correctamente, porque podemos construir una pareja con el procedimiento cons y podemos extraer sus componentes con car y cdr. O sea, que teniendo la lambda como una primitiva, podríamos prescindir de otras formas de construir estructuras de datos. En la realidad no es así por motivos de eficiencia.

Abstracción de datos y barrera de abstracción

Si estamos tratando con un tipo particular de datos, queremos hablar sobre ellos en términos de su significado, y no en términos de cómo se representan en el ordenador.

Por ejemplo, supongamos que estamos escribiendo un programa para jugar a las cartas y que en un momento dado necesitamos una función que calcule la puntuación total de una mano de cartas. Supongamos que escribimos el siguiente código:

(define (total mano)
  (if (equal? mano '())
      0
      (+ (butlast (car mano))
         (total (cdr mano)) )))

(total '(3o 10c 4b))
17

Esta definición de la función total es absolutamente críptica. ¿Cuál es el problema de fondo? Fíjate en que para entender cómo se calcula el valor total de la mano de cartas debemos entender cómo está implementada la mano de cartas. Si miramos en el ejemplo en el que se llama a la función total nos damos cuenta de que una mano de cartas es una lista de identificadores. Y también nos damos cuenta de que los identificadores están formados por un número que representa el valor de la carta y un carácter que representa su palo. Así, por ejemplo, '12c representa el 12 de copas o '3o representa el 3 de oros.

Ahora ya se puede entender un poco mejor el código: con (car mano) se obtiene el primer elemento de la lista mano y con butlast se quita el último carácter para quedarnos sólo con el número de la primera carta. Y después se hace una llamada recursiva para que se calcule el total del resto de la mano. Pero aún así el código sigue siendo poco legible, porque se incumple una regla fundamental de la programación:

Aviso
REGLA DE PROGRAMACIÓN

Debemos usar la abstracción para crear tipos de datos. Un tipo de datos cumple dos funciones: acercar el programa al dominio que estamos programando y ocultar la implementación con una barrera de abstracción.

En este caso, el dominio es el juego de cartas. Podemos entonces usar la abstracción para definir las funciones valor y palo del tipo de dato carta:

(define (valor carta)
   (butlast carta))

(define (palo carta)
   (cond 
      ((equal? (last carta) 'o) 'oros)
      ((equal? (last carta) 'c) 'copas)
      ((equal? (last carta) 'e) 'espadas)
      ((equal? (last carta) 'b) 'bastos)
      (else (error "carta mal definida:" carta))))

Y podemos definir las funciones una-carta, resto-cartas y mano-sin-cartas? del tipo de datos mano:

(define (una-carta mano)
   (car mano))

(define (resto-cartas mano)
   (cdr mano))

(define (mano-sin-cartas? mano)
   (equal? mano '())

Acabamos de crear una barrera de abstracción. Si usamos las funciones valor, palo, una-carta, resto-cartas y mano-sin-cartas? nos estamos acercando más al dominio del programa (juego de cartas) y no nos ligamos a una implementación concreta de nuestras estructuras de datos. La función total quedaría como sigue:

(define (total mano)
  (if (mano-sin-cartas? mano)
      0
      (+ (valor (una-carta mano))
         (total (resto-cartas mano)) )))

Esta versión es mucho más legible. Además, la ocultación de la información proporcionada por la barrera de abstracción de las funciones valor, mano-sin-cartas, una-carta y resto-cartas independiza la función total de la implementación del tipo de dato. Si por alguna razón quisiéramos modificar en el programa la representación de las cartas o de las manos no tendríamos que cambiar la función total.

Los procedimientos auxiliares como valor se denominan selectores (selectors) porque seleccionan un componente de un dato multi-valor.

Realmente, estamos violando la abstracción de datos cuando escribimos una mano de cartas como '(3h 10c 4d) porque eso asume que sabemos cómo se representan las cartas; esto es, como palabras en las que se combina el valor de la carta y una letra que representa el palo. Si queremos ir a más en la ocultación de la representación, necesitamos procedimientos constructores (constructors) además de los selectores:

(define (make-carta valor palo)
  (word valor (first palo)) )

(define make-mano list)

(total (make-mano (make-card 3 'oros)
                  (make-card 10 'copas)
                  (make-card 4 'bastos) ))
17

En el momento que usamos abstracciones de datos, podemos cambiar la implementación del tipo de datos sin afectar en absoluto a los programas que usan ese tipo de datos. Esto significa que podemos cambiar cómo representar una carta, por ejemplo, sin rescribir total:

(define (make-carta valor palo)
  (cond ((equal? palo 'copas) valor)
        ((equal? palo 'oros) (+ valor 13))
        ((equal? palo 'bastos) (+ valor 26))
        ((equal? palo 'espadas) (+ valor 39))
        (else (error "palo incorrecto:" palo)) ))

(define (valor carta)
  (remainder carta 13))

(define (palo carta)
  (nth (truncate (/ (-1+ carta) 13)) '(copas oros bastos espadas)))

Hemos cambiado la representación interna, de forma que ahora la carta es únicamente un número entre 1 y 52, pero no hemos cambiado en absoluto la conducta (behavior) del programa. Podemos seguir llamando a total de la misma forma.

Podemos representar la barrera de abstracción con la siguiente figura:

A continuación podemos ver otro ejemplo: los números racionales.

(define (make-rat numer denom) 
   (cons numer denom)) 
 
(define (numer rat) 
   (car rat)) 
    
(define (denom rat) 
   (cdr rat)) 
    
(define (add-rat x y) 
   (make-rat (+ (* (numer x) (denom y)) 
                (* (numer y) (denom x))) 
             (* (denom x) (denom y)))) 
 
(define (sub-rat x y) 
   (make-rat (- (* (numer x) (denom y)) 
                (* (numer y) (denom x))) 
             (* (denom x) (denom y)))) 
 
(define (mul-rat x y) 
   (make-rat (* (numer x) (numer y)) 
             (* (denom x) (denom y)))) 
              
(define (div-rat x y) 
   (make-rat (* (numer x) (denom y)) 
             (* (denom x) (numer y)))) 
  
(define (equal-rat? x y)    
   (= (* (numer x) (denom y)) 
      (* (denom x) (numer y)))) 

Vemos que en el ejemplo hay dos niveles de funciones en el tipo de datos, por un lado se encuentran los selectores numer y denom que devuelven el numerador y el denominador del número racional. Y por otro lado se encuentran el resto de operaciones que usan estos selectores y que también son parte de la barrera de abstracción del tipo de datos.

Datos jerárquicos y la propiedad de la clausura

La posibilidad de que cons pueda construir parejas con datos de cualquier tipo es fundamental para la construcción de tipos abstractos de datos más elaborados, ya que permite que cualquiera de los datos sea un propio cons. La propiedad de que a los datos producidos por una operación también se les pueda aplicar esa misma operación se denomina clausura (el nombre viene del álgebra).

Las siguientes imágenes representan, en lo que se denominan diagramas box-and-pointer, tres datos obtenidos con cons:

(cons 5 2)

(cons (cons 1 2)
      (cons 3 4))
           
(cons (cons 1 
           (cons 3 4))
      2)

Tipo abstracto de datos secuencia (o lista)

Una lista se puede construir mediante una secuencia de cons como ilustra la siguiente figura:

El cdr de la última pareja señala el final de la lista apuntando a un valor especial que no es otra pareja, que en los diagramas box-and-pointer se representa como una diagonal y en los programas Scheme con el valor de la variable nil. La lista se construye con la llamada anidada a operaciones cons:

(cons 1
      (cons 2
            (cons 3
                      (cons 4 nil))))

Una vez que sabemos cómo representar internamente el tipo abstracto lista, ¿cuáles deberían ser los constructores y los selectores? Lo más obvio es tener un constructor que toma cualquier número de argumentos y devuelva una lista con esos argumentos, y un selector que tome un número y una lista como argumentos y devuelva el elemento n de la lista. Scheme proporciona para ello las siguientes funciones.

  • (list obj ...): crea una lista con un número variable de datos que recibe como argumentos
  • (list-ref list k): devuelve el elemento k de la lista list (empezando a contar por 0)

Por ejemplo:

> (define lista (list 1 2 3 4 'hola 'adios))
> lista
(1 2 3 4 hola adios)
> (list-ref lista 4)
hola

A menudo resulta más útil seleccionar elementos de una lista de una forma distinta, con un selector para el primer elemento y otro para el resto de la lista. Esta forma es más apropiada si vamos a escribir funciones recursivas que recorran la lista Estos constructores son los propios car y cdr. Otro constructor es append con el que se concatenan listas.

Otros operadores sobre listas que se definen en Scheme son los siguientes.

  • (length list): devuelve el numero de elementos de una lista
  • (list-tail list k): devuelve la sublista de list omitiendo los primeros k elementos
  • (append list1 list2...): construye una nueva lista concatenando los elementos de las listas que se pasan como parámetros
  • (reverse list): invierte una lista
  • (map func list): construye una lista con los elementos que resultan de aplicar func a cada uno de los elementos de list

Algunas de estas funciones se implementarían en el propio Scheme de la siguiente forma.

(define (list-tail lista k)
   (if (= 0 k)
       lista
       (list-tail (cdr lista) (- k 1))))
  
(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))

(define (map f list)
   (if (null? list)
       '()
       (cons (f (car list))
             (map f (cdr list)))))

(define (reverse l)
     (if (null? l) '()
      (append (reverse (cdr l)) (list (car l)))))	     

Este tipo abstracto de datos tiene un status especial en el propio intérprete de Scheme, debido a que las listas se leen y escriben usando una notación especial. Si Scheme sólo supiera de las parejas, y no de las listas, cuando construimos la lista (1 2 3) la imprimiría como (1 . (2 . (3 . ())))

Más sobre los diagramas box-and-pointer

He aquí unos pocos detalles acerca de los que la gente suele confundirse:

1. Una flecha no puede apuntar a la mitad de una pareja. Si una flecha toca una pareja, está apuntando a la pareja en su totalidad y no importa en qué posición exacta toca la flecha. Si ves algo como:

(define x (car y)) 

donde y es una pareja, la flecha para x debería apuntar a lo que apunte el car de y, y no a la mitad izquierda del rectángulo:

2. La dirección de las flechas (arriba, abajo, izquierda, derecha) es irrelevante. Puedes dibujarlas como quieras para hacer que se vea clara la estructura de las parejas. ¡Por esta razón es por la que nunca debes olvidar el dibujar las cabezas de las flechas!

3. Debe haber una flecha de alto nivel que apunte al comienzo de la estructura de datos.

¿Cómo dibujar un diagrama para una lista complicada? Tomemos este ejemplo

'((a b) c (d (e f)))

Debes comenzar preguntándote cuántos elementos tiene la lista. En este caso tiene tres elementos: primero (a b), luego c, y luego el resto. Por eso deberías dibujar una lista inicial con tres parejas:

Sólo cuando has dibujado este nivel superior debes preocuparte en conseguir que los cars de las tres parejas apunten a los tres elementos que constituyen la lista.