Textos que cambiaron mi forma de pensar sobre los lenguajes de programación
(bernsteinbear.com)- Presenta varios artículos, papers y videos que cambiaron de raíz su forma de ver los lenguajes de programación y los compiladores
- Son recursos que ampliaron enormemente su comprensión sobre temas prácticos como implementación de GC, diseño de optimizadores, asignación de registros y motores de expresiones regulares
- Explican con ejemplos de código reales, de forma accesible, algoritmos y estructuras usadas en la práctica como Z3 y dominios abstractos, forma SSA y E-Graphs
- Cada recurso descompone conceptos complejos de manera concisa, escalable y fácil de entender
Introducción a los textos que transformaron mi visión sobre lenguajes de programación y compiladores
- A veces encuentro papers, posts de blog o videos sobre lenguajes de programación y compiladores que cambian por completo mi manera de pensar sobre el tema
- En algunos casos el impacto es tan fuerte que ni siquiera recuerdo cómo pensaba antes de leerlos
- A continuación presento algunos de esos materiales (sin orden en particular)
Sobre GC, optimizadores, dominios abstractos y asignación de registros
- a simple semi-space collector de Andy Wingo muestra muy bien cómo llevar a la práctica el concepto de recolector de basura Cheney/copiado/compactación
- La implementación central del GC en el texto es muy concisa, escalable y se puede entender en medio día
- Implementing a Toy Optimizer de CF Bolz-Tereick cambia la forma de entender el enfoque de rewrite de instrucciones en un optimizador
- En lugar de una simple búsqueda y reemplazo, enfatiza el uso de forwarding pointers e introduce la idea de union-find
- Toda la serie del toy optimizer contiene ideas nuevas e interesantes en cada entrega
- A Knownbits Abstract Domain for the Toy Optimizer, Correctly presenta al mismo tiempo un nuevo dominio abstracto y formas de usar Z3
- Muestra no solo cómo Z3 se usa para varias pruebas de operaciones numéricas, sino también ejemplos de su uso como motor de verificación de código Python
- Introduce la idea de que si Z3 no encuentra contraejemplos, entonces se tiene una garantía de corrección del código
- En Cranelift, Part 3: Correctness in Register Allocation Chris Fallin explica un método para demostrar directamente la corrección de la asignación de registros para cada entrada
- En producción, esto permite obtener ya sea una asignación correcta o un crash significativo
- También introduce un enfoque que usa fuzzing para explorar el espacio de estados y detectar bugs
Sobre parsing, intérpretes, JIT y estructuras abstractas
- Regular Expression Matching: the Virtual Machine Approach de Russ Cox presenta una implementación de motor de expresiones regulares en unas 50 líneas de código fácil de leer
- En el proceso también explica de forma muy clara los principios de corutinas, fibras, schedulers y más
- micrograd de Andrej Karpathy es un ejemplo ultrapequeño que hace funcionar una red neuronal sin bibliotecas externas, útil para aprender la estructura y los principios básicos del aprendizaje automático
- How I implement SSA form de Fil Pizlo presenta una nueva forma de mejorar la estructura union-find
- En la transformación a SSA, administra punteros adicionales como un Identity tag dentro del objeto
- Además, ofrece más temas para reflexionar, como Phi/Upsilon form y efectos de heap al estilo TBAA
- Speculation in JavaScriptCore de Fil Pizlo trata en detalle varias formas de implementar optimizadores en JavaScriptCore
- Cada vez que lo releo encuentro ideas nuevas
Diseño de compiladores, parsers, estructura de IR y E-Graphs
- En la charla de Chandler Carruth Modernizing Compiler Design for Carbon Toolchain (alrededor del minuto 29) se explica cómo se definió el objetivo de tiempos de compilación extremadamente rápidos y cómo se diseñó toda la arquitectura
- Desde alrededor del minuto 40 se desglosa la estructura por capas
- A Python Interpreter Written in Python de Allison Kaptur ayuda a entender fácilmente cómo funciona internamente el intérprete de bytecode de CPython
- Parsing expressions by precedence climbing de Eli Bendersky presenta el método de parsing Precedence Climbing, que resulta más fácil de entender y menos costoso de desarrollar que un parser recursivo descendente tradicional
- Ruby JIT Challenge de Takashi Kokubun muestra generación de código y un nuevo método de asignación de registros (stack folding at compile-time)
- An Incremental Approach to Compiler Construction (PDF) de Abdulaziz Ghuloum explica una implementación de una sola pasada que permite entender de una vez el diseño tradicional de compiladores por múltiples etapas
- Adopta un enfoque de agregar cada funcionalidad poco a poco de extremo a extremo
- Lessons from Writing a Compiler de Fernando Borretti explica la estrategia de implementación de compiladores poniéndola en palabras de forma clara
- El paper egg: Fast and extensible equality saturation cambia de raíz la forma de pensar sobre optimizadores y el orden de los passes
- Propone la idea de construir un hipergrafo comprimido con todas las versiones posibles de una expresión y luego elegir la mejor
- Cranelift: Using E-Graphs for Verified, Cooperating Middle-End Optimizations de Chris Fallin demuestra que los e-graphs también funcionan de manera efectiva en compiladores comerciales reales
- Acyclic Egraphs and Smart Constructors de Phil Zucker explora la estructura de e-graphs acíclicos y el uso de smart constructors
- Al principio fue difícil de entender, pero con el tiempo se volvió un texto que se aprecia cada vez más
Almacenamiento de AST, análisis dinámico paralelo a gran escala y otros temas
- este comentario en Reddit de Bob Nystrom y Flattening ASTs de Adrian Sampson
- muestran cómo almacenar un AST casi tan compacto como bytecode, y
- abren una discusión más amplia sobre cómo guardar nodos de IR de esta manera permitiría incluso análisis lock-free masivos en paralelo
- También influyó en esta forma de pensar un comentario de Cliff Click sobre la velocidad de asignación de buffers
1 comentarios
Opinión de Hacker News
Me gusta mucho este post; últimamente he leído bastante investigación en ciencias de la computación, pero aún hay algunas cosas mencionadas aquí con las que no me había topado, y quisiera compartir algunos papers que me gustan y que no aparecen aquí: “Open, Extensible Object Models” de Ian Piumarta trata sobre un sistema metaobjeto orientado a objetos mínimo que le da al programador la máxima libertad; básicamente solo define la operación de envío de mensajes y todo lo demás puede modificarse en tiempo de ejecución, se siente como una versión práctica de “Art of the Metaobject Protocol”; “Scripting: Higher-Level Programming for the 21st Century” de John Ousterhout trata la dicotomía entre lenguajes de programación de sistemas y lenguajes de scripting; siempre queremos un lenguaje multiparadigma perfecto con el que podamos hacer todo rápido y con productividad, pero muchas veces es mejor combinar un lenguaje de sistemas compilado, rápido y complejo con un frontend interpretado, conveniente y flexible; de hecho, muchas veces basta con usar C y Tcl juntos; es una lectura obligada para cualquiera que diseñe lenguajes de programación; Project Oberon de Niklaus Wirth es un ejemplo de implementación de un sistema computacional completo, desde una UI de alto nivel hasta el kernel, el compilador y una arquitectura de CPU similar a RISC; hizo una defensa contundente del “lean software” y además la llevó a la práctica; en una época como la actual, llena de infierno de dependencias y abstracción excesiva, eso se siente como una artesanía perdida
Me gusta mucho este post; los textos sobre lenguajes de programación han cambiado mi forma de ver la programación misma, y a menudo me acuerdo de una cita de “seguridad” en TAPL(Types and Programming Languages): un lenguaje seguro es uno que evita que el programador se dispare en el pie y protege sus abstracciones; es decir, importa la capacidad del lenguaje para garantizar la integridad tanto de las abstracciones que ofrece como de las abstracciones superiores que construye el programador; por ejemplo, si existe la abstracción de un arreglo, debería poder cambiarse solo cuando se actualiza explícitamente, y no debería alterarse por error al tocar otra estructura de datos
Hablando de hábitos de desarrollo interesantes… Aaron Hsu, conocido por APL, escribe código con plumín y en estilo caligráfico cuando quiere ordenar sus ideas; yo hago algo parecido: dibujo con una pluma barata algo como diagramas de flujo de objetos en Python para aclarar mis pensamientos, una especie de UML de bajo presupuesto
Yo también termino buscando un plumín cuando estoy lidiando con los problemas más difíciles; usar uno me hace sentir que entro en un espacio mental completamente distinto; como hay límites para editar, me empuja a pensar de forma más coherente y lineal, pero al mismo tiempo puedo moverme libremente entre inglés, código, matemáticas y diagramas, y eso abre la creatividad
Está demostrado que la escritura a mano sí está relacionada con una mejor memoria; tomar notas en computadora se parece más o menos a dejar huellas digitales en el mango de una herramienta; ojalá el OCR llegue a ser tan bueno que uno pueda registrar todo exclusivamente a mano y aun así guardarlo y buscarlo sin problemas
De verdad recomiendo ver las charlas de Rich Hickey, sobre todo las primeras; a mí también me cambiaron por completo la manera de ver la programación en sí
Para mí, junto con “Programming Perl” de Larry Wall, las charlas de Rich Hickey fueron de lo más influyente
Hasta me dan ganas de bromear con que salten la charla “Simple made easy”, porque todos los ponentes de conferencias la han citado tanto en los últimos diez años que ya se volvió un cliché; personalmente me gusta más “Hammock driven development”, aunque no alcanza como para recomendarla en el trabajo
Qué lástima que Abdulaziz se haya quedado en silencio después de volver a Kuwait; fue intern en Maxine VM en 2009 y era una gran persona; ese paper es una joya de verdad
Hace poco hubo un buen post sobre intérpretes basados en closures para acelerar intérpretes; yo usé esa técnica para hacer un intérprete sencillo de brainfuck y resultó bastante rápido; probablemente no vuelva a usarlo en otro lado, pero como experimento fue útil
Ojalá existiera un post así sobre lenguajes de más alto nivel como JavaScript o .NET; este autor es muy inteligente, pero trabaja en un nivel más bajo que la mayoría de los usuarios (¿o más alto?)
Sus otros posts del blog también son realmente excelentes
Sobre micrograd: me pregunto si existe más documentación además del código fuente del repositorio de Github
Lo digo porque me cae bien esta persona, pero los textos de aquí no son realmente sobre PL (lenguajes de programación) como tal, sino casi todos sobre compiladores (excepto el recolector de basura); claro, los compiladores también me gustan, pero es otro tema distinto de PL