Understanding Computation
Tom Stuart
- Editorial
- O'Reilly
- Año
- 2013
- Páginas
- ~332
- Nivel
- Básico
De qué trata
Tratado divulgativo y técnico escrito por Tom Stuart que traduce la teoría formal de la computación, tradicionalmente confinada al lenguaje matemático abstracto o a entornos funcionales académicos, a código ejecutable en Ruby (versión 2.0). Está concebido para desarrolladores en activo e ingenieros de software autodidactas que desean entender qué ocurre 'bajo el capó' de los lenguajes de programación, cómo se procesan las instrucciones y cuáles son los límites fundamentales de lo computable, contando únicamente con conocimientos previos básicos de programación.
El recorrido prescinde de librerías externas y se apoya en construcciones idiomáticas puras de Ruby para modelar las distintas facetas del cálculo formal. Cubre la definición de lenguajes mediante sintaxis y semántica operacional (de paso pequeño y de paso grande) y semántica denotacional, autómatas finitos deterministas (DFA) y no deterministas (NFA), autómatas de pila (PDA) para lenguajes libres de contexto, y máquinas de Turing estándar y universales. En su segunda mitad explora el cálculo lambda sin apoyos ('Programming with Nothing', derivando booleanos, números de Church, aritmética y el combinador Y exclusivamente mediante funciones anónimas), sistemas de reescritura de etiquetas ('tag systems'), autómatas celulares como la Regla 110, la indecidibilidad del problema de la parada ('Halting Problem') y la verificación de programas con sistemas de tipos estáticos e interpretación abstracta.
En lugar de listas convencionales de ejercicios, el libro propone la implementación completa y reproducible de máquinas de estados, evaluadores semánticos y simuladores computacionales desde cero en pequeños scripts de Ruby. Es una de las mejores obras para desmitificar compiladores, parsers y modelos de computabilidad, cambiando radicalmente la forma en que un programador concibe el software. Al ser un libro centrado en la teoría pura, no ofrece utilidades prácticas para desarrollo de aplicaciones comerciales ni optimización de código en entornos de producción.
- Ruby
- Teoría de la computación
- Semántica operacional
- Semántica denotacional
- Autómatas finitos
- Autómatas de pila
- Máquinas de Turing
- Cálculo Lambda
- Autómatas celulares
- Problema de la parada
- Sistemas de tipos
¿Cómo enseña?
Con proyectos
- ✗ Sin ejercicios
- ✓ Incluye proyectos
Proyectos
Intérprete y evaluador semántico del lenguaje 'Simple'
Intérprete para un lenguaje imperativo mínimo que implementa su árbol sintáctico abstracto, reglas de reducción de paso pequeño y paso grande, y su traducción a semántica denotacional en Ruby.
Motor de autómatas finitos y expresiones regulares
Simulador de autómatas finitos deterministas (DFA) y no deterministas (NFA) capaz de evaluar transiciones de estado y emparejar patrones de cadenas de texto equivalentes a expresiones regulares.
Simulador de Máquina de Turing Universal
Implementación ejecutable con cinta de memoria infinita, cabezal de lectura/escritura y tabla de transiciones, capaz de emular cualquier cálculo secuencial algorítmico.
Sistema de cálculo lambda puro ('Programming with Nothing')
Entorno computacional construido únicamente con lambdas y funciones anónimas de Ruby, implementando números de Church, operadores booleanos, listas enlazadas y recursión mediante el combinador Y.
