Nota: Esto es parte de la serie «Composing Software» (¡ahora un libro!) sobre el aprendizaje de la programación funcional y las técnicas de composición de software en JavaScriptES6+ desde cero. Manténgase en sintonía. ¡Hay mucho más de esto por venir!
Comprar el libro | Índice | < Anterior | Siguiente >
No confundir con:
Tipos de datos algebraicos (a veces abreviados ADT o AlgDT). Los tipos de datos algebraicos se refieren a tipos complejos en lenguajes de programación (por ejemplo, Rust, Haskell, F#) que muestran algunas propiedades de estructuras algebraicas específicas. por ejemplo, tipos suma y tipos producto.
Estructuras algebraicas. Las estructuras algebraicas son estudiadas y aplicadas desde el álgebra abstracta, que al igual que las ADTs, también son comúnmente especificadas en términos de descripciones algebraicas de axiomas, pero aplicables mucho más allá del mundo de las computadoras y el código. Puede existir una estructura algebraica que sea imposible de modelar en el software por completo. Por el contrario, los Tipos de Datos Abstractos sirven como especificación y guía para verificar formalmente el software que funciona.
Un Tipo de Datos Abstracto (ADT) es un concepto abstracto definido por axiomas que representan algunos datos y operaciones sobre esos datos. Los ADTs no se definen en términos de instancias concretas y no especifican los tipos de datos concretos, estructuras o algoritmos utilizados en las implementaciones. En su lugar, los ADTs definen los tipos de datos sólo en términos de sus operaciones, y los axiomas a los que esas operaciones deben adherirse.
Ejemplos de ADTs comunes
- Lista
- Pila
- Cola
- Mapa
- Flujo
- Sobrepasado en el presupuesto
- Tarde
- Falla
- Falta de requisitos
- Difícil de mantener
- Formal. Las especificaciones deben ser formales. El significado de cada elemento de la especificación debe definirse con suficiente detalle para que el público objetivo tenga una oportunidad razonablemente buena de construir una implementación conforme a la especificación. Debe ser posible implementar una prueba algebraica en código para cada axioma de la especificación.
- Aplicable. Las ADTs deben ser ampliamente aplicables. Un ADT debe ser generalmente reutilizable para muchos casos de uso concretos diferentes. Un ADT que describe una implementación particular en un lenguaje particular en una parte particular del código es probablemente sobre-especificar las cosas. En cambio, las ADTs son más adecuadas para describir el comportamiento de estructuras de datos comunes, componentes de bibliotecas, módulos, características del lenguaje de programación, etc. Por ejemplo, un ADT que describa las operaciones de la pila, o un ADT que describa el comportamiento de una promesa.
- Mínimo. Las especificaciones de ADT deben ser mínimas. La especificación debe incluir las partes interesantes y ampliamente aplicables del comportamiento y nada más. Cada comportamiento debe ser descrito con precisión y sin ambigüedades, pero con el menor detalle específico o concreto posible. La mayoría de las especificaciones de las ADTs deberían ser demostrables utilizando un puñado de axiomas.
- Extensible. Las ADT deben ser extensibles. Un pequeño cambio en un requisito debe conducir a sólo un pequeño cambio en la especificación.
- Declarativo. Las especificaciones declarativas describen el qué, no el cómo. Las ADTs deben describirse en términos de lo que son las cosas, y los mapeos de relación entre las entradas y salidas, no los pasos para crear estructuras de datos o los pasos específicos que cada operación debe llevar a cabo.
- Descripción legible por humanos. Los ADTs pueden ser bastante escuetos si no van acompañados de alguna descripción legible por humanos. La descripción en lenguaje natural, combinada con las definiciones algebraicas, pueden actuar como controles entre sí para aclarar cualquier error en la especificación o ambigüedad en la comprensión de la misma por parte del lector.
- Definiciones. Defina claramente cualquier término utilizado en la especificación para evitar cualquier ambigüedad.
- Firmas abstractas. Describe las entradas y salidas esperadas sin vincularlas a tipos o estructuras de datos concretas.
- Axiomas. Algebraic definitions of the axiom invariants used to prove that an implementation has satisfied the requirements of the specification.
-
a: Any type -
b: Any type -
item: Any type -
stack(): an empty stack -
stack(a): a stack ofa -
: a pair ofitemandstack stack(...items) => stack(...items)push(item, stack()) => stack(item)pop(stack) =>
Los ADTs pueden representar cualquier conjunto de operaciones sobre cualquier tipo de datos. En otras palabras, la lista exhaustiva de todos los ADTs posibles es infinita por la misma razón que la lista exhaustiva de todas las frases posibles en inglés es infinita. Las TAD son el concepto abstracto de un conjunto de operaciones sobre datos no especificados, no un conjunto específico de tipos de datos concretos. Un error común es pensar que los ejemplos específicos de TAD que se enseñan en muchos cursos universitarios y libros de texto sobre estructuras de datos son lo que son las TAD. Muchos de estos textos etiquetan las estructuras de datos como «ADTs» y luego omiten el ADT y describen las estructuras de datos en términos concretos en su lugar, sin exponer nunca al estudiante a una representación abstracta real del tipo de datos. Los ADTs pueden expresar muchas estructuras algebraicas útiles, incluyendo semigrupos, monoides, funtores, mónadas, etc. La especificación Fantasyland es un catálogo útil de estructuras algebraicas descritas por ADTs para fomentar las implementaciones interoperables en JavaScript. Los creadores de bibliotecas pueden verificar sus implementaciones utilizando los axiomas suministrados.
¿Por qué ADTs?
Los Tipos de Datos Abstractos son útiles porque nos proporcionan una manera de definir formalmente módulos reutilizables de una manera que es matemáticamente sólida, precisa y sin ambigüedades. Esto nos permite compartir un lenguaje común para referirnos a un amplio vocabulario de bloques de construcción de software útiles: Ideas que son útiles para aprender y llevar con nosotros a medida que nos movemos entre dominios, marcos, e incluso lenguajes de programación.
Historia de las ADTs
En la década de 1960 y principios de 1970, muchos programadores e investigadores de ciencias de la computación estaban interesados en la crisis del software. Como dijo Edsger Dijkstra en su conferencia del premio Turing:
«¡La principal causa de la crisis del software es que las máquinas se han vuelto varios órdenes de magnitud más potentes! Para decirlo sin rodeos: mientras no había máquinas, la programación no era ningún problema; cuando tuvimos unos pocos ordenadores débiles, la programación se convirtió en un problema leve, y ahora tenemos ordenadores gigantescos, la programación se ha convertido en un problema igualmente gigantesco.»
El problema al que se refiere es que el software es muy complicado. Una versión impresa del módulo lunar Apolo y del sistema de guía de la NASA tiene la altura de un archivador. Eso es mucho código. Imagina intentar leer y entender cada línea de eso.
El software moderno es órdenes de magnitud más complicados. Facebook tenía aproximadamente 62 millones de líneas de código en 2015. Si imprimieras 50 líneas por página, llenarías 1,24 millones de páginas. Si apilas esas páginas, obtendrías unas 1.800 páginas por pie, o 688 pies. Eso es más alto que la Torre Millenium de San Francisco, el edificio residencial más alto de San Francisco en el momento de escribir este artículo.
La gestión de la complejidad del software es uno de los principales retos a los que se enfrentan prácticamente todos los desarrolladores de software. En los años sesenta y setenta, no disponían de los lenguajes, patrones o herramientas que hoy damos por sentado. Cosas como los linters, el intellisense e incluso las herramientas de análisis estático aún no se habían inventado.
Muchos ingenieros de software observaron que el hardware sobre el que construían cosas funcionaba en su mayoría. Pero el software, la mayoría de las veces, era complejo, enmarañado y frágil. El software era comúnmente:
Si sólo se pudiera pensar en el software en piezas modulares, no se necesitaría entender todo el sistema para comprender cómo hacer que una parte del sistema funcione. Ese principio de diseño de software se conoce como localidad. Para conseguir la localidad, se necesitan módulos que se puedan entender de forma aislada del resto del sistema. Debes ser capaz de describir un módulo de forma inequívoca sin sobreespecificar su implementación. Ese es el problema que resuelven las ADTs.
Desde la década de los 60 casi hasta la actualidad, avanzar en el estado de la modularidad del software era una preocupación central. Fue con esos problemas en mente que personas como Barbara Liskov (la misma Liskov a la que se hace referencia en el Principio de Sustitución Liskov de los principios de diseño OO de SOLID), Alan Kay, Bertrand Meyer y otras leyendas de la informática trabajaron en la descripción y especificación de varias herramientas para permitir el software modular, incluyendo las ADTs, la programación orientada a objetos y el diseño por contrato, respectivamente.
Las ADTs surgieron del trabajo de Liskov y sus estudiantes en el lenguaje de programación CLU entre 1974 y 1975. Contribuyeron significativamente al estado del arte de la especificación de módulos de software, el lenguaje que utilizamos para describir las interfaces que permiten que los módulos de software interactúen. El cumplimiento formalmente demostrable de las interfaces nos acerca significativamente a la modularidad e interoperabilidad del software.
Liskov fue galardonada con el premio Turing por su trabajo sobre abstracción de datos, tolerancia a fallos y computación distribuida en 2008. Las ADTs jugaron un papel importante en ese logro, y hoy en día, prácticamente todos los cursos universitarios de ciencias de la computación incluyen ADTs en el plan de estudios.
La crisis del software nunca se resolvió por completo, y muchos de los problemas descritos anteriormente deberían ser familiares para cualquier desarrollador profesional, pero aprender a utilizar herramientas como objetos, módulos y ADTs ciertamente ayuda.
Especificaciones para ADTs
Se pueden utilizar varios criterios para juzgar la idoneidad de una especificación ADT. Yo llamo a estos criterios FAMED, pero sólo he inventado la nemotecnia. Los criterios originales fueron publicados por Liskov y Zilles en su famoso artículo de 1975, «Specification Techniques for Data Abstractions»
Una buena ADT debe incluir:
Stack ADT Example
A stack is a Last In, First Out (LIFO) pile of items which allows users to interact with the stack by pushing a new item to the top of the stack, or popping the most recently pushed item from the top of the stack.
Stacks are commonly used in parsing, sorting, and data collation algorithms.
Definitions
Abstract Signatures
The stack operation takes any number of items and returns a stack of those items. Typically, the abstract signature for a constructor is defined in terms of itself. Please don’t confuse this with a recursive function.
Stack Operations (operations which return a stack)
Axioms
The stack axioms deal primarily with stack and item identity, the sequence of the stack items, and the behavior of pop when the stack is empty.
Identity
Pushing and popping have no side-effects. If you push to a stack and immediately pop from the same stack, the stack should be in the state it was before you pushed.
pop(push(a, stack())) =
- Given: push
ato the stack and immediately pop from the stack - Should: return a pair of
aandstack().
Sequence
Popping from the stack should respect the sequence: Last In, First Out (LIFO).
pop(push(b, push(a, stack())) =
- Given: push
ato the stack, then pushbto the stack, then pop from the stack - Should: return a pair of
bandstack(a).
Empty
Popping from an empty stack results in an undefined item value. In concrete terms, this could be defined with a Maybe(item), Nothing, or Either. In JavaScript, it’s customary to use undefined. Popping from an empty stack should not change the stack.
pop(stack()) =
- Given: pop from an empty stack
- Should: return a pair of undefined and
stack().
Concrete Implementations
An abstract data type could have many concrete implementations, in different languages, libraries, frameworks, etc. Here is one implementation of the above stack ADT, using an encapsulated object, and pure functions over that object:
const stack = (...items) => ({
push: item => stack(...items, item),
pop: () => {
// create a item list
const newItems = ; // remove the last item from the list and
// assign it to a variable
const = newItems.splice(-1); // return the pair
return ;
},
// So we can compare stacks in our assert function
toString: () => `stack(${ items.join(',') })`
});const push = (item, stack) => stack.push(item);
const pop = stack => stack.pop();
And another that implements the stack operations in terms of pure functions over JavaScript’s existing Array type:
const stack = (...elements) => ;const push = (a, stack) => stack.concat();const pop = stack => {
const newStack = stack.slice(0);
const item = newStack.pop();
return ;
};
Both versions satisfy the following axiom proofs:
// A simple assert function which will display the results
// of the axiom tests, or throw a descriptive error if an
// implementation fails to satisfy an axiom.
const assert = ({given, should, actual, expected}) => {
const stringify = value => Array.isArray(value) ?
`` :
`${ value }`;
const actualString = stringify(actual);
const expectedString = stringify(expected);
if (actualString === expectedString) {
console.log(`OK:
given: ${ given }
should: ${ should }
actual: ${ actualString }
expected: ${ expectedString }
`);
} else {
throw new Error(`NOT OK:
given ${ given }
should ${ should }
actual: ${ actualString }
expected: ${ expectedString }
`);
}
};// Concrete values to pass to the functions:
const a = 'a';
const b = 'b';// Proofs
assert({
given: 'push `a` to the stack and immediately pop from the stack',
should: 'return a pair of `a` and `stack()`',
actual: pop(push(a, stack())),
expected:
})assert({
given: 'push `a` to the stack, then push `b` to the stack, then pop from the stack',
should: 'return a pair of `b` and `stack(a)`.',
actual: pop(push(b, push(a, stack()))),
expected:
});assert({
given: 'pop from an empty stack',
should: 'return a pair of undefined, stack()',
actual: pop(stack()),
expected:
});
Conclusion
- An Abstract Data Type (ADT) is an abstract concept defined by axioms which represent some data and operations on that data.
- Los Tipos de Datos Abstractos se centran en el qué, no en el cómo (están enmarcados de forma declarativa, y no especifican algoritmos o estructuras de datos).
- Los ejemplos más comunes incluyen listas, pilas, conjuntos, etc.
- Las ADTs proporcionan una manera de definir formalmente los módulos reutilizables de una manera que es matemáticamente sólida, precisa y sin ambigüedades.
- Las ADTs surgieron del trabajo de Liskov y sus estudiantes en el lenguaje de programación CLU en la década de 1970.
- Las ADTs deben ser FAMED. Formales, ampliamente aplicables, mínimas, extensibles y declarativas.
- Las ADTs deben incluir una descripción legible por humanos, definiciones, firmas abstractas y axiomas formalmente verificables.
- Los axiomas son afirmaciones matemáticamente sólidas que deben cumplirse.
- Matemáticamente sólidos significa que cada término está bien definido matemáticamente para que sea posible escribir afirmaciones de hecho inequívocas y demostrables basadas en ellos.
Consejo de bonificación: Si no estás seguro de si debes encapsular o no una función, pregúntate si la incluirías en una ADT para tu componente. Recuerda que los ADTs deben ser mínimos, así que si no es esencial, carece de cohesión con el resto de operaciones, o su especificación es susceptible de cambiar, encapsúlala.
Glosario
Siguientes pasos
EricElliottJS.com cuenta con muchas horas de lecciones en vídeo y ejercicios interactivos sobre temas como este. Si te gusta este contenido, por favor considera unirte.