Computación y programación funcional. Camilo Chacón Sartori

Capítulo 13. Estructuras de datos

       13.1 Lista

       13.1.1 Búsqueda

       13.1.2 Inserción

       13.1.3 Eliminación

       13.1.4 Filtrado

       13.2 Tabla hash

       13.2.1 Búsqueda

       13.2.2 Inserción

       13.2.3 Eliminación

       13.3 Par

       13.3.1 Operadores de acceso

       13.4 Estructura de tipos

       13.4.1 Operadores de acceso

       13.5 Árbol de búsqueda binario

       13.5.1 Búsqueda

       13.5.2 Cantidad de elementos

       Capítulo 14. Algoritmos

       14.1 Ordenamiento

       14.1.1 Quicksort

       14.1.2 Merge sort

       14.2 Recursividad

       14.2.1 Torre de Hanói

       14.3 Búsqueda de subcadenas

       14.3.1 Karp-Rabin

       14.4 Compresión de datos

       14.4.1 Codificación Huffman

       Capítulo 15. Crear un pequeño lenguaje de programación usando Racket

       15.1 Especificación

       15.2 Analizador léxico

       15.3 Analizador sintáctico

       15.4 Intérprete

       15.4.1 Pruebas

       Epílogo - Lecturas recomendadas

       Agradecimientos

       Apéndice A - Notación Big O

       Apéndice B – Introducción a TLA+ (PlusCal)

       Bibliografía

       Glosario

       PRÓLOGO

      El cálculo automático es una invención con fecha antigua. Hace 2000 años ya se había construido el «mecanismo de Anticitera», un dispositivo que permitía calcular los eclipses lunares. Más tarde, en el siglo XVII, el matemático Wilhelm Schickard desarrolló la primera calculadora mecánica.

      En el siglo XX aparecieron casi concurrentemente los modelos teóricos de la computación y los desarrollos tecnológicos asociados. Muchos de estos últimos estaban basados en la intuición; otros, fundamentados en bases formales. Aparecen los modelos de Church y Turing en el área de la teoría de la computación, y de Chomsky en el área de los lenguajes formales.

      Los tres enfoques, complementados con las ideas y los estudios de muchos científicos y profesionales, fueron el punto de partida de lo que hoy denominamos «Ciencia de la Computación».

      A la par de estos nuevos conocimientos, surgió la necesidad de expresarlos de manera inteligible para el ser humano, y procesables por un sistema automatizado. Esto dio origen a los lenguajes de programación, cada uno con sus enfoques y sus sabores sintácticos. Los procesos involucrados en el análisis de esos lenguajes se fundamentan en los aportes de Chomsky y Backus: las teorías de Chomsky (1956) relativas a los lenguajes formales y las gramáticas y los aportes de Backus relativos a cómo expresar las reglas gramaticales. Backus creó un lenguaje recursivo, que fue denominado «BNF» (Backus Normal Form, 1959) en su honor.

      Los primeros lenguajes de programación surgieron para satisfacer diferentes necesidades: Fortran (1954), para el cálculo numérico; APL (1957) incorporó la computación funcional; Algol (1958) muestra el camino hacia la programación estructurada; Lisp (1958), basado en el cálculo lambda, derivó en el primer lenguaje para inteligencia artificial; Cobol (1959), para el procesamiento masivo de registros, y Simula (1962) introduce el concepto de «clase».

      Sin temor a equivocarnos, podemos afirmar que la mayoría de los paradigmas computacionales actualmente en boga tienen su semilla en las décadas de los 50 y los 60: la programación orientada a objetos, la inteligencia artificial, la computación funcional, el cálculo lambda, la programación estocástica y tantas otras ideas. Las sucesivas encantaciones de dichas creaciones primigenias devienen, gracias a los nuevos aportes, interacciones y experiencias, en el mundo digital que vivimos hoy.

      Los paradigmas reaparecen adaptados y evolucionados para enfrentar necesidades nuevas, tales como los crecientes volúmenes de información y los tamaños de los sistemas computacionales, que en muchos casos superan los millones de líneas de código. Así, por ejemplo, en su momento florece el concepto de programación estructurada como consecuencia del creciente tamaño