Nerding about stuff I've found interesting

Una introducción a las estructuras de datos puede darse en una oración y aún así terminará siendo reducida a “la forma en la que se almacenan los datos”, sin embargo, considero que entender cómo funciona una computadora, particularmente cómo es que podemos hacer que la computadora haga cosas por nosotros, es una parte fundamental que se tiene que entender antes de comenzar a trabajar con las estructuras de datos. Durante todo este post vamos a estar hablando acerca de las múltiples abstracciones que existen debajo de nuestro lenguaje de programación, las cuáles nos permiten no tener que preocuparnos por el flujo de 0s y 1s que están viajando dentro de nuestra computadora.

El término computadora puede tener múltiples significados alrededor del mundo, pero el que nos interesa a nosotros es el que la define como una máquina multipropósito, que nos permite darle una serie de instrucciones para realizar cualquier otra tarea. Bajo esta definición una calculadora no es una computadora pero tu smartphone sí lo es.

Gran parte de la forma en que nuestras computadoras funcionan se la debemos a Alan Turing, y no, no por esa “famosa” prueba de Turing que usan los medios de comunicación, las contribuciones de Turing van más allá de los artículos clickbait. Posiblemente el trabajo más importante de Turing surge alrededor del Entscheidungsproblem, posteriormente el halting problem, el cuál se pregunta si dado un programa \(g\) y una entrada \(x\) era posible determinar si \(g(x)\) terminaba o continuaba corriendo para siempre. Para resolver este problema Turing creo un modelo matemático de computación que manipula símbolos en una cinta infinita basado en un tabla de reglas. Hoy en día éste modelo es conocido como máquina de Turing. Y quizá una de las cosas más importantes de éste párrafo es saber que, a pesar de la simplicidad del modelo, cualquier algoritmo de computadora puede ser expresado en una máquina de Turing.

Representación artística de una Máquina de Turing

Posterior al trabjo de Turing, por cierto la respuesta al halting problem es NO, la siguiente pregunta fue ¿Podemos crear una máquina que lea la descripción de cualquier máquina de Turing (y su input) y sea capaz de simular su ejecución? Dicha máquina sería nombrada la Universal Turing Machine (UTM) y fue aquí donde papi von Neumann llegó con la ingeniosa idea que hoy todo mundo conoce como la Arquitectura Von Neumann y de hecho hoy en día todas las computadoras se basan en esta arquitectura.

Dicho lo anterior y habiendo pasado por múltiples UTMs basadas en una arquitectura von Neumann, desde las que usaban tarjetas perforadas hasta las computadoras modernas, llegamos a la famosísima frase "las computadoras sólo entienden \(0s\) y \(1s\)" la cuál sigue siendo verdad el día de hoy. Por ejemplo, y simplificando mucho las cosas, una operación que suma el contenido del registro 1 al contenido del registro 2 luciría como la siguiente:

00111011110101101011    00000001    00000010
#       Add                $1          $2

¡Lo cual está loquísimo! Sí sí, máquinas de Turing y todo pero... ¿Te imaginas escribiendo un programa usando sólo \(0s\) y \(1s\)? O peor aún ¿Te imaginas LEYENDO un programa usando sólo \(0s\) y \(1s\)? Además, los procesadores de hoy en día incluyen cientos, si no es que miles, de instrucciones. Bueno, pues esa fue la primer tarea de los programadores: simplificarse la chamba.

La primera mejora llegó con ensamblador. Ensamblador realmente se reduce a una lista de sinónimos donde cada una de las instrucciones era mapeada a algo más legible, por ejemplo, en lugar de usar `00111011110101101011` para sumar ahora se usará la palabra `add`. Un ejemplo de un programa en ensamblador, para Intel x86, sería el siguiente:

push    %rbp
movq    %rsp, %rbp
movl    $10, -4(%rbp)
movl    $0, %eax
popq    %rbp
ret

El cual se traduce a: 1) Agrega una "función" al stack 2) Asigna el valor \(10\) al registro `rbp` 3) Saca la función del stack 4) Termina.

¿Ya te sientes agradecid@ al saber que tu no tienes que hacer nada de esto? Bueno, deberías: gracias abstracción 💕.

Quizá uno de los cambios más radicales en la forma de escribir programas surgió cuando nació FORTRAN (FORmula TRANslation). FORTRAN, como su nombre lo indica, no era únicamente un conjunto de alias de instrucciones, si no que también permitía correr operaciones de la forma \(c = sqrt(a**2 + b**2)\) además de incluir otras como `IF` y `GOTO`.

FORTRAN trajo consigo una serie de cambios importantísimos en la forma de escribir programas y, así mismo, fue quien dio vida a nuevos lenguajes de programación.

Lenguajes de programación

Como seguramente ya sabes, la representación interna de los tipos de datos primitivos de un lenguaje de programación suele seguir convenciones internacionales, por ejemplo: los enteros con signo son almacenados siguiendo operaciones de complemento a 2 y los flotantes siguen el estándar IEEE-754, etc. Además, algo que todos los primitivos tienen en común es que trabajan en regiones contiguas de memoria, por ejemplo: En C++ un boolean y un char ocupan 1 byte, un int y un float 4 bytes, y un double y un long 8 bytes, por lo que para obtener el conjunto de 0s y 1s que representan a un dato de estos, y después utilizar las convenciones del lenguaje para convertirlo en algo que podemos entender,  lo único que necesitamos saber es la dirección de memoria en la que inicia. Por ejemplo: para obtener los 0s y 1s de un double almacenado en la dirección \(A\), tenemos que obtener todos los valores que se encuentren en el rango \([A, A+t]\) donde \(t\) es el tamaño del tipo de dato, en nuestro caso 8 bytes. Aunque realmente nunca hacemos esto, ¿cierto?, nosotros solo hacemos algo como int a = 10y listo, nuevamente, gracias abstracciones 😘.

Programa primitives.cpp | Imprime el tamaño en memoria de los tipos primitivos de C++

Otro bonito ejemplo de la representación interna de los datos, y que me gusta mucho porque a veces suele generar ese "clic" en las personas, emerge cuando revisamos a detalle los arreglos y notamos que siguen exactamente la misma idea de conjunto de 0s y 1s contiguos en memoria.

Un arreglo (array) de cierto tipo de datos \(T\) con \(N\) elementos siempre ocupará \(N \cdot \mathrm{sizeof}(T)\)  bytes en memoria suponiendo que \( \mathrm{sizeof}() \) nos regresa el tamaño del tipo \(T\) en bytes. De hecho es de estas operaciones que se deriva la constante batalla entre algunos matemáticos y computólogos alrededor de si el 0 es o no considerado un elemento de los números naturales (\( 0 \in \mathbb{N}\)).

Fig 1. Meme 😅

Anteriormente dijimos que lo único que necesitamos saber para obtener el valor de un dato es conocer su dirección inicial y el tamaño del tipo, bueno pues en los arreglos funciona de una forma bastante similar. Al saber que un arreglo que inicia en la dirección \(A\) de la memoria ocupa \(N \cdot \mathrm{sizeof}(T)\) bytes, también sabemos que cada elemento del arreglo inicia a \( m \cdot \mathrm{sizeof}(T)\) bytes de \(A\) donde \(m\) es el número de elementos antes de él. Dicho esto, podemos generalizar una ecuación que nos de la dirección exacta de cada elemento \(i\) de la siguiente manera:

$$A + i \cdot \mathrm{sizeof}(T)$$

Donde si queremos obtener el primer elemento nuestra \(i\) tendría que valer \(0\), para el segundo elemento \(i = 1\), para el tercero \(i=2\) y así sucesivamente. Esto, además de proveer una forma bastante sencilla de generalizar el acceso a los elementos, también expone una operación muy fácil de realizar por un procesador, es por esto que el tiempo que le toma a un lenguaje de programación acceder al i-ésimo elemento de un arreglo se considera constante sin importar que tan grande o pequeño sea este, dicho en otras palabras, y como veremos más adelante, la complejidad en tiempo es de \(O(1)\).

Programa arrays.cpp | Crea un arreglo de tamaño n=5 llamado A={10, 9, 8, -142, 238} y accede a sus valores aplicando la ecuación descrita arriba.
Representación gráfica de arrays.cpp

Siguiendo los principios anteriores podríamos empezar a generar nuestros propios tipos de datos. Por ejemplo: si quisiéramos tener un tipo de dato personalizado (un tipo de dato abstracto) que guarde la información sobre un lugar físico como nombre, hora de apertura, hora de cierre, días en los que está abierto y reputación podríamos llegar a un convenio similar al de los arreglos en donde usamos direcciones contiguas de memoria y sabemos que cada parte de nuestro nuevo tipo de dato siempre se va a encontrar en direcciones conocidas y al alcance de una ecuación.

Lo anterior, aunque seguramente no es la mejor forma de almacenar esos datos, es un ejemplo claro de lo que son las estructuras de datos. Podemos definirlas como, ahora sí, un "convenio" en la organización, manejo y almacenamiento de la información de forma que su acceso y modificación son eficientes.

More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be  applied to the data.

- Wikipedia

Python

Los lenguajes de programación de bajo nivel como C o C++ suelen ser la elección por excelencia para enseñar estructuras de datos. Esto se debe particularmente a que tenemos CONTROL TOTAL sobre lo que está sucediendo en la memoria usando apuntadores. Durante esta serie de posts no estaré usando ninguno de los anteriores principalmente porque no los domino y porque me da muchísima flojera hacerlo, pero como eso suena muy mal mejor usaré el mismo pretexto que usó Canek para enseñarlas con Java, era algo como: "...seguir una tendencia y tomar un enfoque moderno de la enseñanza de Estructuras de Datos..." (no citar).

En lo personal considero que estudiar estos temas usando C/C++ puede brindar al estudiante habilidades muy útiles no sólo respecto al manejo de memoria, sino también en el uso de éstas herramientas, sin embargo también considero que si el estudiante es capaz de entender conceptualmente las estructuras, no es necesario utilizarlas mientras que el alumno las implemente. Es aquí donde la Programación Orientada a Objetos (OOP) nos "tirará paro" y la utilizaremos para diseñar nuestras futuras implementaciones. Por otro lado, aunque Java es el lenguaje OOP por excelencia y puede ser muy útil para aprender este paradigma, es tan verboso (verbose) que sólo nos continuará distrayendo del objetivo principal que es aprender sobre estructuras de datos, no volvernos ingenieros expertos en Java.

En mi curso con Canek en la Facultad de Ciencias he escuchado que "cualquier simio puede usar Python" y creo que justo ese es el punto por el cual DEBE ser usado en esta serie. Entre menos nos preocupemos por los detalles del lenguaje de programación y más nos enfoquemos en las estructuras, mejor. A final de cuentas ¿Cuál es el objetivo de llevar un curso de estructuras de datos si la mayor parte del tiempo te la vas a pasar hablando de los detalles de la implementación pudiendo utilizar ese tiempo profundizando más en el tema?

El el siguiente post voy a escribir brevemente sobre de otro tema introductorio muy importante necesario antes de comenzar con las estructuras de datos: Complejidad Computacional.