Lenguajes y Paradigmas de Programación
 

Construcción de tipos de datos

Introducción

Los beneficios de introducir tipos de datos en un lenguaje de programación son muy grandes. Entre ellos se encuentran la posibilidad de detectar y prevenir errores en las llamadas a funciones o en la asignación de valores a variables. En este tema veremos algunas estrategias para introducir tipos de datos en Scheme.

Hemos visto en el tema 4 las ventajas de usar la abstracción de datos, definiendo un nombre para una composición de datos primitivos. Por ejemplo, hemos hecho esto con los árboles o con las cartas. Hemos creado una estructura de datos utilizando parejas (conses) y hemos definido unos constructores y unos selectores. Los constructores son funciones que devuelven un dato compuesto (un árbol o una carta) creado a partir de unos valores dados (que pueden ser también compuestos) y los selectores devuelven los datos elementales que forman el dato compuesto.

Por ejemplo, el constructor

(make-arbol dato hijos)

construye un árbol a partir de un dato y una lista de árboles hijos (que puede ser vacía, para el caso de los nodos hoja). A su vez, los selectores

(dato arbol)
(hijos arbol)

devuelven el dato asociado a un árbol y su lista de hijos.

De esta forma, definiendo constructores y selectores, podemos abstraer el tipo de datos y usarlo sin preocuparnos de la implementación.

Pero esta solución no es perfecta. Su limitación fundamental es que la abstracción que definimos sólo existe en la disciplina del programador, no hay nada en el lenguaje que la refuerce ni la represente. Para Scheme el dato construido sólo es un conjunto de parejas a las que se podría acceder utilizando las funciones para parejas car y cdr. Además, tampoco es posible comprobar si un dato es de un tipo determinado, lo que nos puede llevar a errores como el de llamar a una función usando argumentos que no son del tipo correcto.

El problema de esta solución se debe en parte a que Scheme es un lenguaje débilmente tipeado (weakly typed language en inglés). En Scheme las variables no tienen un tipo asociado. Una variable puede ligarse a un dato de un tipo y después a un dato de otro tipo. Para especificar una función no es necesario definir los tipos de los parámetros ni del valor devuelto. En un lenguaje déblimente tipeado no se comprueban los tipos de las variables en tiempo de compilación o ni siquiera existen. Otros lenguajes débilmente tipeados son Smalltalk o Python.

En el otro extremo se encuentran lenguajes como Pascal o Ada, en los que todas las variables y parámetros tienen asociados un tipo de datos y el compilador comprueba que todas las asignaciones y paso de parámetros son consistentes. A estos lenguajes se les denomina fuertemente tipeados (strongly typed languages en inglés).

Vamos a buscar una solución dinámica a los tipos en Scheme: vamos a hacer que los datos (no las variables) estén tipeados (contenga información de su tipo). O sea, dado un dato podremos consultar de qué tipo de dato es. Esto permitira:

  • chequear que los argumentos se corresponden con los tipos esperados
  • definir procedimentos genéricos o polimórficos (que reciben más de un tipo)

Vamos a hacer esto utilizando principalmente dos estrategias. En la primera, la más sencilla, etiquetaremos los datos con un identificador que definirá su tipo. En la segunda implementaremos los datos como funciones que aceptan mensajes. Será un primer paso para la programación orientada a objetos. A la primera estrategia la denominaremos datos etiquetados y a la segunda paso de mensajes.

Números complejos

Utilizamos como ejemplo el problema de la representación de números complejos (consultar en http://es.wikipedia.org/wiki/Número_complejo). Un número complejo se puede representar de dos formas:

  • Representación rectangular mediante una parte real y una parte imaginaria (a,b), siendo ambas números reales. El número complejo se puede representar en un sistema de coordenadas definido por el eje real (vertical) y el eje imaginario (horizontal), en la posición definida por sus dos componentes. Este plano se denomina el plano de los números complejos.
  • Representación polar mediante una magnitud y un ángulo (r,alfa). Si tomamos el punto que define la representación de un número en el plano complejo, su magnitud corresponde con la distancia del punto al origen de coordenadas y su ángulo con el ángulo del eje horizontal al segmento que va del origen de coordenadas al punto.

En la siguiente figura se muestra la representación rectangular y polar de un número complejo.

Es sencillo convertir un número de una representación a otra. De rectangular a polar:

r = sqrt (a^2 + b^2) alfa = atan(b,a)

De polar a rectangular:

a = r * cos(alfa) b = r * sin(alfa)

Definimos las siguientes funciones de Scheme que realizan esta transformación:

(define (magnitude-from-real-imag real imag)
   (sqrt (+ (square real) (square imag))))

(define (angle-from-real-imag real imag)
   (atan imag real))

(define (real-from-mag-ang r a)
   (* r (cos a)))

(define (imag-from-mag-ang r a)
   (* r (sin a)))

Operaciones con números complejos

Vamos a considerar la suma y la multiplicación de números complejos. La suma de dos números complejos es muy sencilla utilizando una representación rectangular, mientras que para la multiplicación es conveniente utilizar la notación polar.

Dados dos números z1=(a1,b1) y z2=(a2,b2) en representación rectangular, su suma se calcula como:

z1+z2 = (a1+a2, b1+b2)

Dados dos números z1=(r1,alfa1) y z2=(r2,alfa2) en representación polar, su multiplicación se calcula como:

z1*z2 = (r1*r2, alfa1+alfa2)

Tipos de datos etiquetados

En este apartado explicaremos cómo representar tipos de datos utilizando datos etiquetados. Vamos a utilizar el problema de la representación de números complejos como ejemplo.

Representación de tipos datos con etiquetas

La primera estrategia que vamos a definir para representar tipos de datos es muy sencilla. Consiste en añadirle a todos los datos una etiqueta con un identificador del tipo de dato. Para implementarlo en Scheme construimos una pareja (cons) cuya parte izquierda es el identificador del tipo de dato y cuya parte derecha es el dato propiamente dicho.

Para implementar esta estrategia definimos tres funciones en Scheme. La función (attach type-tag contents) recibe como parámetros una etiqueta de tipo y un dato y devuelve un dato etiquteado. La función (type-tag datum) toma como parámetro un dato etiquetado y devuelve su tipo. Por último, la función (contents datum) toma como parámetro un dato etiquetado y devuelve el dato propiamente dicho.

(define (attach-tag type-tag contents)
  (cons type-tag contents))

(define (type-tag datum)
  (if (pair? datum)
      (car datum)
      (error "error en type-tag" datum " no es un dato etiquetado")))

(define (contents datum)
  (if (pair? datum)
      (cdr datum)
      (error "error en contents" datum " no es un dato etiqueteado")))

Un ejemplo de utilización es el siguiente, aplicado al ejemplo de las cartas de la baraja del tema 4:

(define c1 (attach-tag 'carta (make-carta 5 'oros)))
(type-tag c1) -> 'carta
(contents c1) -> la carta propiamente dicha

Programando con números complejos

En el apartado anterior veíamos que es posible representar los números complejos con dos notaciones y que dependiendo de qué operaciones se realizan con los números complejos es conveniente usar una representación u otra.

Si queremos escribir un programa en Scheme que utilice números complejos podríamos pensar que tenemos que decidirnos por una representación. Pero en programación debemos retrasar este tipo de decisiones el máximo tiempo posible. Es más, deberíamos buscar una forma de hacer posible cambiar de decisión en el último momento, cuando tengamos el programa terminado y las pruebas nos indican que una notación es preferible a otra (por cuestiones de eficiencia, por ejemplo).

Para poder usar ambos tipos de datos simultáneamente usamos la siguiente estrategia:

  1. Definimos ambas representaciones mediante dos tipos de datos: rectangular y polar. Ambos tipos de datos tienen una barrera de abstracción común, aunque especializada en datos del tipo correspondiente.

    Así, definimos para el tipo de dato rectangular las siguientes funciones:

    • (make-from-real-imag-rectangular real imag)
    • (make-from-mag-angle-rectangular mag ang)
    • (real-part-rectangular z-rectangular)
    • (imag-part-rectangular z-rectangular)
    • (magnitude-rectangular z-rectangular)
    • (angle-rectangular z-rectangular)

    Y para el tipo de dato polar definimos las funciones:

    • (make-from-real-imag-polar real imag)
    • (make-from-mag-angle-polar mag ang)
    • (real-part-polar z-polar)
    • (imag-part-polar z-polar)
    • (magnitude-polar z-polar)
    • (angle-polar z-polar)
  2. Definimos una barrera de abstracción genérica que permita utilizar ambos tipos de datos de forma indistinta:
    • (make-from-real-imag-complex real imag)
    • (make-from-mag-angle-complex mag ang)
    • (real-part-complex z)
    • (imag-part-complex z)
    • (magnitude-complex z)
    • (angle-complex z)
  3. Por último, definimos una barrera de abstracción de más alto nivel que define operaciones sobre números complejos utilizando la barrera de abstracción anterior:

    • (add-complex z1 z2)
    • (sub-complex z1 z2)
    • (mult-complex z1 z2)
    • (div-complex z1 z2)

Para poder definir las funciones genéricas es necesario reconocer el tipo de dato que llega como parámetro. En la función genérica se recibirá un dato de tipo rectangular o polar y se deberá llamar a la función específica correspondiente. Para ello usamos la estrategia de tipos etiquetados, y en los constructores añadimos una etiqueta al dato indicando de que tipo es. Todas las funciones trabajan con datos etiquetados.

La implementación de los números complejos con la representación rectangular es la siguiente.

(define (make-from-real-imag-rectangular x y)
  (attach-tag 'rectangular (cons x y)))

(define (make-from-mag-ang-rectangular r a) 
  (attach-tag 'rectangular
              (cons (real-from-mag-ang r a)
                    (imag-from-mag-ang r a))))

(define (real-part-rectangular z) (car (contents z)))

(define (imag-part-rectangular z) (cdr (contents z)))

(define (magnitude-rectangular z)
  (magnitude-from-real-imag (real-part-rectangular z)
                            (imag-part-rectangular z)))

(define (angle-rectangular z)
  (angle-from-real-imag (real-part-rectangular z)
                        (imag-part-rectangular z)))

La implementación de los números complejos con la representación polar es la siguiente.

(define (make-from-real-imag-polar x y) 
  (attach-tag 'polar
               (cons (magnitude-from-real-imag x y)
                     (angle-from-real-imag x y))))

(define (make-from-mag-ang-polar r a)
  (attach-tag 'polar (cons r a)))

(define (magnitude-polar z) (car (contents z)))

(define (angle-polar z) (cdr (contents z)))

(define (real-part-polar z)
  (real-from-mag-ang (magnitude-polar z) (angle-polar z)))

(define (imag-part-polar z)
  (imag-from-mag-ang (magnitude-polar z) (angle-polar z)))

Las funciones genéricas de nivel más bajo se implementan como sigue.

(define (rectangular? z)
  (eq? (type-tag z) 'rectangular))

(define (polar? z)
  (eq? (type-tag z) 'polar))

(define (real-part z)
  (cond ((rectangular? z) 
         (real-part-rectangular z))
        ((polar? z)
         (real-part-polar z))
        (else (error "Unknown type -- REAL-PART" z))))

(define (imag-part z)
  (cond ((rectangular? z)
         (imag-part-rectangular z))
        ((polar? z)
         (imag-part-polar z))
        (else (error "Unknown type -- IMAG-PART" z))))

(define (magnitude z)
  (cond ((rectangular? z)
         (magnitude-rectangular z))
        ((polar? z)
         (magnitude-polar z))
        (else (error "Unknown type -- MAGNITUDE" z))))

(define (angle z)
  (cond ((rectangular? z)
         (angle-rectangular z))
        ((polar? z)
         (angle-polar z))
        (else (error "Unknown type -- ANGLE" z))))
;
; Constructores
;

(define (make-from-real-imag x y)
  (make-from-real-imag-rectangular x y))

(define (make-from-mag-ang r a)
  (make-from-mag-ang-polar r a))

Las funciones genéricas de alto nivel se implementan a continuación.

(define (add-complex z1 z2)
  (make-from-real-imag (+ (real-part z1) (real-part z2))
                       (+ (imag-part z1) (imag-part z2))))

(define (sub-complex z1 z2)
  (make-from-real-imag (- (real-part z1) (real-part z2))
                       (- (imag-part z1) (imag-part z2))))

(define (mul-complex z1 z2)
  (make-from-mag-ang (* (magnitude z1) (magnitude z2))
                     (+ (angle z1) (angle z2))))

(define (div-complex z1 z2)
  (make-from-mag-ang (/ (magnitude z1) (magnitude z2))
                     (- (angle z1) (angle z2))))

Programación dirigida por los datos

Necesitamos una tabla hash global indexada por dos claves para guardar en ella las funciones específicas. Esta tabla se implementa en Scheme con las siguientes funciones. No nos interesa la implementación, sino los ejemplos finales en los que se muestra cómo usar las funciones put y get que guardan y recuperan datos en la tabla global.

(define nil '())
    
(define (get-primitive key)
  (let ((record (assq key (cdr the-table))))
    (if (not record)
    nil
    (cdr record))))

(define (put-primitive key value)
  (let ((record (assq key (cdr the-table))))
    (if (not record)
    (set-cdr! the-table
          (cons (cons key value)
            (cdr the-table)))
    (set-cdr! record value)))
  'ok)

(define the-table (list '*table*))

(define (search-value key list)
   (cond 
      ((null? list) #f)
      ((equal? key (car (car list))) (cdr (car list)))
      (else (search-value key (cdr list)))))

(define (put key1 key2 value)
   (let ((l-value (get-primitive key1)))
      (if (pair? l-value)
         (put-primitive key1 (cons (cons key2 value) l-value))
         (put-primitive key1 (list (cons key2 value))))))

(define (get key1 key2)
   (let ((l-value (get-primitive key1)))
      (search-value key2 l-value)))


; Ejemplos de uso de estas funciones

(put 'a 'a 10)
(put 'a 'b 20)
(put 'b 'b 30)
(get 'a 'a)
(get 'a 'b)
(get 'b 'b)
(put 'b 'b (get 'a 'a))
(get 'b 'b)

Usamos la tabla global para guardar las funciones específicas de los distintos tipos de datos. Asociamos cada función específica a la función genérica que implementa y al tipo de dato del argumento de la función.

(put 'real-part 'rectangular real-part-rectangular)
(put 'imag-part 'rectangular imag-part-rectangular)
(put 'magnitude 'rectangular magnitude-rectangular)
(put 'angle 'rectangular angle-rectangular)
(put 'make-from-real-imag 'rectangular make-from-real-imag-rectangular)
(put 'make-from-mag-ang 'rectangular make-from-mag-ang-rectangular)

(put 'real-part 'polar real-part-polar)
(put 'imag-part 'polar imag-part-polar)
(put 'magnitude 'polar magnitude-polar)
(put 'angle 'polar angle-polar)
(put 'make-from-real-imag 'polar make-from-real-imag-polar)
(put 'make-from-mag-ang 'polar make-from-mag-ang-polar)

Teniendo esta tabla es muy sencillo definir una función operate que tiene como argumento un nombre de función genérica y un tipo de dato y devuelve la función específica a aplicar a ese tipo de dato para implementar la función genérica.

(define (operate op obj)
  (let ((proc (get op (type-tag obj))))
    (if proc
       (proc (contents obj))
       (error "Unknown operator for type"))))

Una vez implementada la función operate hay que reescribir las funciones genéricas como llamadas a esta función. De esta forma la barrera de abstracción de los datos continua siendo la misma.

(define (real-part z) (operate 'real-part z))
(define (imag-part z) (operate 'imag-part z))
(define (magnitude z) (operate 'magnitude z))
(define (angle z) (operate 'angle z))
(define (type z) (operate 'type z))

Por último, para los constructores accedemos directamente a la tabla:

(define (make-from-mag-ang r a)
   ((get 'make-from-mag-ang 'polar) r a))

(define (make-from-real-imag x y)
   ((get 'make-from-real-imag 'rectangular) x y))

Paso de mensajes

La estrategia del paso de mensajes para codificar los tipos de datos es la segunda que vamos a ver. Es una estrategia radicalmente distinta

;; Paquete representacion rectangular

(define (make-from-real-imag x y)
  (lambda (op)
    (cond ((eq? op 'real-part) x)
          ((eq? op 'imag-part) y)
          ((eq? op 'magnitude) 
           (magnitude-from-real-imag x y))
          ((eq? op 'angle) 
           (angle-from-real-imag x y))
          ((eq? op 'type) 'rectangular)
          (else
           (error "Unknown op -- MAKE-FROM-REAL-IMAG" op)))))

;; Paquete representación polar
(define (make-from-mag-ang  r a)
  (lambda (op)
    (cond ((eq? op 'real-part) 
           (real-from-mag-ang r a))
          ((eq? op 'imag-part)
           (imag-from-mag-ang r a))
          ((eq? op 'magnitude) r)
          ((eq? op 'angle) a)
          ((eq? op 'type) 'polar)
          (else
           (error "Unknown op -- MAKE-FROM-REAL-IMAG" op)))))


;; Funciones genericas que funcionan con culauier tipo de datos

(define (real-part z) (z 'real-part))
(define (imag-part z) (z 'imag-part))
(define (magnitude z) (z 'magnitude))
(define (angle z) (z 'angle))
(define (type z) (z 'type))

;
; código que prueba el módulo
;

(define z1 (make-from-real-imag 5 10))
(magnitude z1)
(angle z1)
(define z2 (make-from-mag-ang (magnitude z1) (angle z1)))
(real-part z2)
(imag-part z2)
(define z3 (add-complex z1 z2))
(real-part z3)
(imag-part z3)

Estructuras en MzScheme

MzScheme es la versión de Scheme que se define en DrScheme. En esta versión se definen extensiones del lenguaje básico como son las estructuras, la programación orientada a objetos o las comunicaciones de red

En MzScheme se pueden construir estructuras con campos. Definimos la estructura complex-rect y se definen automáticamente el constructor y las funciones de acceso a los campos real e imag.

(define-struct complex-rect (real imag))

(define c1 (make-complex-rect 5 3))
(complex-rect-real c1) -> 5
(complex-rect-imag c1) -> 3

Ahora definimos las funciones que obtienen la magnitud y el ángulo del número complejo: complex-rect-mag y complex-rect-ang que usan las funciones auxiliares definidas previamente:

(define (complex-rect-mag z)
   (magnitude-from-real-imag (complex-rect-real z)
                             (complex-rect-imag z)))
(define (complex-rect-ang z)
   (angle-from-real-imag (complex-rect-real z) (complex-rect-imag z)))

(complex-rect-mag c1) -> 5.830951894845301
(complex-rect-ang c1) -> 0.5404195002705842

Definimos la estructura complex-polar con los campos mag y ang que representa el número imaginario en forma polar. Definimos también las funciones complex-polar-real y complex-polar-imag que obtienen la parte real e imaginaria del número imaginario usando las funciones auxiliares definidas al principio del tema.

(define-struct complex-polar (mag ang))

(define (complex-polar-real z)
   (real-from-mag-ang (complex-polar-mag z) (complex-polar-ang z)))

(define (complex-polar-imag z)
   (imag-from-mag-ang (complex-polar-mag z) (complex-polar-ang z)))

; ejemplos de uso

(define c2 (make-complex-polar 5.830951894845301 0.5404195002705842))
(complex-polar-real c2) -> 5.0
(complex-polar-imag c2) -> 3.0000000000000004