Sobre los Tipos de Datos Algebraicos y la Abstracción

Desde el comienzo de la computación electrónica ha habido dos campos en el desarrollo de los lenguajes de programación: los que buscan velocidad y los que buscan expresividad. Los primeros se caracterizan por su poco nivel de abstracción. Las características del equipo donde corren son visibles al programador y este, en su trabajo, debe preocuparse por ellos. El ejemplo clásico es el lenguaje C.

El otro tipo de lenguajes, representados por scheme, lisp, haskell y varios lenguajes de scripts, busca la abstracción. El programador debe preocuparse por expresar el problema en los términos mas cercanos al mismo, sin hacer consideraciones o concesiones a la plataforma.

Para alcanzar tan loable objetivo, pocas herramientas son tan útiles como los Tipos de Datos Algebraicos o ADT, por sus siglas en ingles. La idea de los tipos algebraicos es permitirle al programador definir nuevos valores primitivos y a partir de ellos generar nuevos tipos, combinando los valores, bien sea por medio de la unión de conjuntos o su producto.

Un ejemplo permitirá mostrar el valor de los ADT como medio de abstracción, comparando la solución a un problema en C, Haskell y, por diversion, BASIC.

Si bien BASIC sería bajo los estándares actuales un lenguaje de script, y por lo tanto mas abstracto, me referiré en cambio a las primeras versiones de BASIC, antes de Visual Basic o Turbo BASIC; un lenguaje mas cercano a la idea original, para correr en una maquina con menores recursos. Hablemos del BASIC que corría en un equipo como el Commode 64 o el Sinclair ZX Spectrum.

El problema en cuestión es extremadamente simple: representar un mazo de cartas. Cada carta tiene una pinta que puede ser corazón, pica, diamante o trébol y un "numero" que puede ser los números del 2 al 10, las letras "A", "J", "Q" o "K".

En un lenguaje de programación contemporáneo una carta podría ser representada por un registro o un objeto, de acuerdo al paradigma para el cual el lenguaje este optimizado. En el BASIC que tengo en mente, conceptos como registros y objetos son términos muy avanzados. Como se representa un registro en tal BASIC? Fácil: con variables separadas, siendo responsabilidad del programador mantener en su cabeza la asociación entre tales variables. Así la J de trébol podría representarse como:

10 c1p = 4
20 c1n = 11

El 10 y el 20 son los "números de linea". Cada linea del programa debía tener un numero, el cual era usado como medio para acceder a la misma por los primitivos editores que era menester hacer caber en 8KB de memoria o menos.

Sin embargo esta solución es suboptima. Los números mágicos 4 y 11 son una mala señal. En un lenguaje cuyos únicos tipos son los números reales, los arreglos y las cadenas de caracteres es poco lo que se puede hacer, mas allá de representar las pintas y los "numeros" especiales de las cartas con constantes:

10 c1p = 4
20 c1n = 11
10 CPCORAZON = 0
20 CPPICA = 1
30 CPDIAMANTE = 2
40 CPTREBOL = 3
50 CNA = 1
60 CNJ = 11
70 CNQ = 12
80 CNK = 13
...
500 c1p = CPTREBOL
510 c1n = CNJ

Mencione que la mayoría de los BASIC de esa época eran insensibles a las mayúsculas y minúsculas y que tenían un limite en el tamaño del nombre de las variables?

Ahora, para representar a un mazo de cartas, se necesita un arreglo... mejor dicho dos arreglos. De nuevo, hay que mantener separados las pintas de los números y hacer la asociación mental durante la escritura del programa.

590 rem el comando dim crea un arreglo
600 dim mp(52)
610 dim mn(52)

Para inicializar los arreglos, es útil el hecho de que la representación elegida para las pintas y los "números" son ambas numéricas, y como cada carta es diferente puede establecerse una correspondencia entre los naturales y estas:

700 for x = 0 to 51
705 rem cada 13 cartas cambia la pinta
710 mp(x) = int(x/13)
720 mn(x) = (x mod 13) + 1
730 next x

La solución en BASIC es engorrosa. Parte del problema no esta reflejado directamente en el programa, sino que debe ser sobreentendido, en particular la necesidad de usar arreglos diferentes para una sola entidad, o la representación numérica de entes como la pinta y el "numero" de la carta.

La solución en C es mas avanzada. El C nos ofrece ENUMs que es una forma básica de representar tipos de datos no númericos.

enum pinta {Corazon, Pica, Diamante, Trebol};
enum numero {As, Dos, Tres, Cuatro, Cinco,
Seis, Siete, Ocho, Nueve, Diez,
Jack, Queen, King};

Tambien permite definir estructuras (registros), con lo que se solventa el problema de mas de una variable para un solo ente.

struct { enum pinta pinta;
enum numero numero; } carta;

Una solución mucho mas elegante que la elaborada en BASIC, pero no mucho mas abstracta. Un enum es poco mas o menos que un conjunto de constantes con valores enteros creados automáticamente. En nuestro caso, Corazon es solo una forma de decir 0 y Trebol es 3. De hecho, una variable declarada como enum puede contener cualquier valor entero, mas allá de los cuatro valores permitidos.

Una estructura tiene también una representación de bajo nivel que puede ser accedida por el programador. Para un compilador especifico el "numero" de una carta puede estar almacenado cuatro bytes después de su pinta, por lo que obteniendo la dirección de esta, se puede modificar aquella.

En resumen, se ha ganado algo de abstracción, pero solo en la forma. Si el programador se compromete a no efectuar ninguna operación sobre las estructuras básicas subyacentes, es probable que todo le salga bien...

Veamos ahora la solución en Haskell, el único de los lenguajes mencionados en este articulo que tiene ADT. Primero creamos un nuevo tipo de datos algebraico para la pinta y el "numero" de la carta:

data Pinta = Corazon | Pica | Diamante | Trebol
data Numero = As | Dos | Tres | Cuatro | Cinco
| Seis | Siete | Ocho | Nueve | Diez
| Jack | Queen | King

Y luego creamos otro tipo algebraico con el producto cartesiano de los dos antes definidos:

data Carta = Carta Numero Pinta

Igual a lo expresado en C? Solo superficialmente. Pinta es un nuevo tipo de datos, no un entero. Su representación interna por el compilador es desconocida. Tal vez sería una buena adivinanza suponer que es representado por un entero de un byte. Pero adivinar sería fútil, ya que el saberlo es irrelevante: la única forma de operar sobre un tipo algebraico es con las operaciones explícitamente definidas por el programador. Lo mismo ocurre con el tipo Carta. Si, de seguro durante la compilación nuestro tipo algebraico se convierte en una estructura equivalente a la del C, pero eso es un asunto entre el compilador y la CPU. Para el programador es un ítem único e indivisible.

También esta el aspecto sicológico. En el caso del C el programador esta definiendo un layout de memoria y unas constantes enteras. En Haskell, el programador esta declarando que una carta es representada por un "numero" y una pinta, y que la pinta puede tomar solo estos valores y que un "numero" en este contexto son tales otros.

Este aspecto sicológico es un subproducto de la mayor capacidad de abstracción del lenguaje, y es una de las mas importantes contribuciones para el programador.