TypeScript es sorprendentemente bastante bueno incluso para implementar compiladores

 (matklad.github.io)
8 puntos por GN⁺ 2023-08-20 | 1 comentarios | Compartir por WhatsApp
  • Tradicionalmente, el lenguaje de implementación para herramientas tipo compilador se dividía entre OCaml y C++, pero en experimentos pequeños de lenguajes, TypeScript puede ser una opción ligera de usar, parecida a un lenguaje de la familia ML
  • Rust combina las ventajas de ML y C++, y además ofrece multihilo seguro, pero como hay que modelar la disposición física de los datos, puede volverse una carga grande para prototipos pequeños
  • Deno permite empezar rápido con experimentos de lenguaje en TypeScript gracias a su binario único, linting y formateo integrados, ausencia de etapa de compilación, task runner y modo watch
  • El type checker de ejemplo combina AST genérico, tagged unions, visitor y transformaciones bottom-up para convertir Expr<void> en Expr<Type>, e introduce TypeError como valor de tipo para reducir errores en cadena
  • TypeScript puede ser productivo como herramienta para hackear lenguajes pequeños gracias al autocompletado, su sistema de tipos flexible y las características de runtime que permiten salirse hacia un enfoque dinámico cuando hace falta

El panorama tradicional al elegir un lenguaje de implementación

  • Al crear herramientas con forma de compilador, la elección del lenguaje de implementación suele dividirse en dos grandes corrientes
  • Para trabajos enfocados en la implementación y que necesitan estar listos para producción, C++ se elige con frecuencia
    • LLVM, clang, v8 y HotSpot están basados en C++
  • Rust recibió influencia directa de ML y C++, combina ventajas de ambos y además aporta fortalezas propias, como multihilo seguro
    • Aun así, dentro de ese espectro está más inclinado hacia la preparación para producción
    • Un sistema de build que “simplemente funciona” también ayuda al prototipado, pero viene acompañado de la complejidad adicional de tener que modelar la disposición física de los datos

Ventajas del enfoque con índices en Rust y la carga que supone para código pequeño

  • Al hacer compiladores en Rust, un consejo común es evitar punteros y usar índices
  • Los índices tienen varias ventajas en bases de código grandes
    • Permiten ubicar side tables dentro de módulos relacionados, reduciendo el acoplamiento
    • Los índices pueden ser u32 y favorecen una disposición tipo struct-of-arrays, lo que beneficia el rendimiento
    • Facilitan la serialización o la conexión con frameworks de compilación incremental, dando más flexibilidad a la estrategia de cómputo
  • Pero en programación a pequeña escala, el enfoque con índices en sí se vuelve engorroso, y en experimentos de hobby esa carga puede ser fatal
  • OCaml sigue dejando una sensación de antigüedad y, en este contexto, se explora si TypeScript puede servir como una alternativa equivalente a ML

Deno y TypeScript como entorno para experimentar rápido

  • Se usa deno como entorno de arranque
    • Ofrece una experiencia lista para usar con TypeScript directamente
    • En OCaml este punto suele ser doloroso, y aunque Rust es mejor que OCaml o C++, Deno ofrece una experiencia todavía más simple que Rust
  • La experiencia de desarrollo de Deno encaja bien con pequeños hacks de PLT
    • Es un binario único
    • Tiene linting y formateo integrados
    • No requiere una etapa de compilación separada
    • Incluye task runner y modo watch
  • TypeScript en sí ofrece un sistema de tipos suficientemente flexible y con poca carga sintáctica

Patrones de TypeScript vistos a través de un type checker pequeño

  • El AST empieza con expresiones que contienen información de ubicación en archivo
    • Location tiene file, line y column
    • En TypeScript, las cadenas son simplemente string y los números simplemente number, así que no hace falta preocuparse por distinciones como usize y u32
  • Las expresiones separan ubicación y kind, y más adelante se generalizan como datos asociados con la forma Expr<T>
    • Justo después del parsing, las expresiones tienen datos void
    • Las expresiones procesadas por el type checker tienen datos Type
    • La función de inferencia de tipos recibe ast.Expr<void> y devuelve ast.Expr<Type>
  • Como TypeScript no agrega comportamiento de runtime automáticamente, para hacer matching sobre union types hay que introducir información de tipo en runtime manualmente
    • Campos como tag: "binary" y tag: "if" cumplen ese papel
    • tag: "binary" significa que, en runtime, ese valor solo puede ser la cadena "binary"
  • Los literales booleanos e integer tienen formas casi idénticas, así que se abstraen como ExprLiteral<T, V, Tag>
    • ExprBool<T> es ExprLiteral<T, boolean, "bool">
    • ExprInt<T> es ExprLiteral<T, number, "int">
  • Los valores de tipo se dividen en TypeBool y TypeInt, y los valores singleton se ofrecen con los mismos nombres
    • TypeScript elimina completamente los tipos, así que los nombres relacionados con tipos y con valores existen en namespaces separados
    • Esa característica permite definir tipos y valores con el mismo nombre

Visitor, transform, tipo de error y desugaring

  • Como switch en TypeScript es una sentencia y no una expresión, se define un visitor para manejar cómodamente los kind de expresiones
    • Los métodos bool, int, binary e if procesan cada kind correspondiente
    • El autocompletado del editor ayuda tanto con los casos de switch como con la implementación del visitor
  • transform<U, V> es una función de recorrido generalizada que convierte Expr<U> en Expr<V>
    • La transformación se ejecuta bottom-up
    • Al visitar nodos internos, las subexpresiones ya fueron transformadas, por lo que el tipo del visitor pasa a ser Visitor<V, V> y no Visitor<U, V>
  • Aprovechando que TypeScript es un lenguaje de tipos dinámicos en runtime, también se puede crear un recorrido más general con Object.keys
    • Incluso en ese caso se puede mantener una firma estática de función
    • En el ejemplo no es estrictamente necesario, pero queda abierta la posibilidad de recurrir a un enfoque dinámico cuando haga falta
  • Los errores de tipo no se acumulan como efecto secundario en un arreglo, sino que se representan mediante el tipo TypeError
    • Type pasa a ser TypeBool | TypeInt | TypeError
    • TypeError tiene tag: "Error", location y message
    • type_equal devuelve true si alguno de los lados es Error, para evitar fallos en cascada
  • El type checker final valida expresiones binary e if
    • Si los tipos de los operandos izquierdo y derecho de una expresión binary no coinciden, devuelve el error "binary expression operands have different types"
    • Si la condición de una expresión if no es booleana, devuelve "if condition is not a boolean"
    • Si los tipos de las ramas then y else no coinciden, devuelve "if branches have different types"
  • El resultado requiere algo de tipado, pero el autocompletado compensa bastante, hay menos sensación de pelearse con el lenguaje y se adapta de forma natural a la forma del problema
  • Las razones por las que TypeScript resulta productivo como herramienta para hackear lenguajes pequeños se resumen en tres puntos
    • Deno es un runtime de scripting pequeño, autocontenido, potente y optimizado para un flujo de desarrollo eficaz
    • Las herramientas de TypeScript son útiles y productivas en el IDE, y gracias a Deno no requieren configuración
    • El lenguaje es potente tanto en runtime como en compile time, permite expresiones bastante sofisticadas con tipos y, si hace falta, también permite caer en un enfoque dinámico
  • Como idea adicional, también es posible desugar mucho azúcar sintáctico de forma type-safe
    • Expr y ExprKind se parametrizan recursivamente no por datos asociados, sino sobre todo el ExprKind
    • ExprKindCore representa el conjunto de expresiones base
    • ExprKindSugar incluye expresiones base o expresiones que pueden desugarse a expresiones base
    • desugar(expr: ExprSugar): ExprCore reduce una expresión con azúcar sintáctico a una expresión núcleo
    • desugar_one(expr: ExprKindSugar<ExprCore>): ExprKindCore<ExprCore> realiza una transformación de un paso cuando las subexpresiones ya están desugarizadas

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-08-20
Opiniones de Hacker News

  • TypeScript es, en general, un lenguaje excelente, y está subestimado el hecho de que las funciones sean objetos que pueden tener propiedades/métodos.
    Puedes ejecutar un arreglo de funciones como si fueran comandos y luego agregarles descripciones como help, o añadir estado mediante closures/aplicación parcial, así que no hace falta definir apresuradamente clases como Command.
    Creo que en la programación orientada a objetos poner nombres demasiado pronto genera muchos conflictos, y que es más natural pasarle a una función los valores necesarios que usar una estructura como VideoCompressor#compress().

    • Para ser precisos, es más una característica de JavaScript que de TypeScript.
      Otros lenguajes que admiten objetos que se comportan como funciones están recopilados en https://en.wikipedia.org/wiki/Function_object.
    • En Go también se pueden adjuntar métodos a funciones y, de hecho, prácticamente a cualquier tipo.
      Como con los handlers de net/http, una struct puede implementar un método serve, o una función handler puede llamarse a sí misma para satisfacer una interfaz.
      En Clojure, se puede hacer algo parecido adjuntando metadatos al var de una función y, al ser Lisp, con macros se puede hacer casi cualquier cosa.
      Además, los canales CSP de core/async separan ejecución y comunicación, lo que permite evitar el problema del color de las funciones de callbacks/promesas/async/await; los comandos pueden comportarse como productores que envían resultados a un canal.
    • Con las interfaces de un solo método de Java también se puede lograr un efecto similar.
      Se pueden usar en un contexto de función sin importar cuál sea el nombre del método, y no hace falta referirse al nombre concreto del método.
      Sin embargo, no me gusta que una función tenga propiedades, contenga estado y pueda cambiar su comportamiento aunque se la llame con los mismos argumentos. Creo que una gran ventaja de la programación funcional está en alejarse del estado al estilo de la orientación a objetos.
    • Python soporta bien este enfoque porque todo es un objeto.
    • En C# también se puede expresar algo parecido con Func para funciones con valor de retorno y Action para funciones sin valor de retorno.
      Las expresiones lambda de JavaScript se parecen bastante a las de C#, y las firmas de función de TypeScript y C# también son bastante similares.
      También hay un pequeño repositorio que muestra las similitudes entre JavaScript, TypeScript y C#: https://github.com/CharlieDigital/js-ts-csharp
      Captura que muestra la misma lógica lado a lado en JS/TS/C#: https://github.com/CharlieDigital/js-ts-csharp/blob/main/js-...

  • No es tan sorprendente. Al final, veo a TypeScript como otro lenguaje que incorporó con dificultad una buena parte de las funciones de la familia ML.
    Al no tener verdadero pattern matching, es más incómodo que OCaml, pero comparado con lenguajes como C#, Swift, Dart o Kotlin, está en un nivel aceptable.

    • Es una comparación vista desde un nivel demasiado alto. La experiencia real de uso es bastante distinta.
      TypeScript tiene un sistema de tipos potente, pero la biblioteca estándar base y el propio lenguaje dejan que desear, y no tiene pattern matching ni expresiones switch.
      Dart tiene un modelo de objetos cerrado, con menos libertad dinámica; su sistema de tipos y sus expresiones también son más débiles, y casi no tiene mecanismos de metaprogramación, por lo que termina dependiendo de boilerplate al estilo Java y generadores de código.
      C# es, entre los lenguajes mencionados, el más cercano a las funciones de ML, pero a diferencia de TypeScript no tiene tipos suma, lo que vuelve muchas cosas más engorrosas.
    • En un compilador educativo estilo Pascal-C que hice antes en Haskell, los parser combinators permitían expresar la gramática directamente en código de una forma parecida a BNF.
      Por ejemplo, se podía combinar un parser que reconoce { ... } con otros parsers, y definir una sentencia como una de varias opciones: flujo de control, declaración o asignación.
      El procesamiento de listas y el pattern matching al estilo ML eran muy expresivos al manejar la representación intermedia.
    • Cuando necesito pattern matching en TypeScript, suelo usar esta biblioteca: https://github.com/gvergnaud/ts-pattern
    • Es difícil decir que TypeScript haya tomado la mayoría de las funciones de ML.
      Incluso en el texto principal, como switch no es una expresión, hubo que esquivarlo con el patrón visitor, y el soporte de iteradores de JavaScript también es extrañamente limitado.
      Existe .map(), pero solo funciona con arreglos y no se puede aplicar directamente a iteradores generales.
    • Si usas TypeScript y kotlin-js, ambos lenguajes se sienten bastante cercanos.
      Hay muchas diferencias, pero no es difícil pasar de uno a otro, y aunque personalmente prefiero Kotlin, puedo usar ambos.
      Me pregunto qué pasaría si TypeScript se apartara de la compatibilidad con JavaScript y compilara a WASM. Kotlin está agregando un compilador a WASM y ya tiene un transpiler a JS; el mismo código carga de forma más pequeña y rápida en WASM.
      JavaScript en el navegador no es un buen objetivo de compilación y, a medida que más proyectos nuevos empiezan desde cero con TypeScript, también se debilita cada vez más la razón de tener que facilitar la transición desde JavaScript existente.

  • Al alternar entre Rust y TypeScript, se nota con mucha claridad cuánto se extrañan funciones como los enums etiquetados.
    La propuesta de enums ADT parece estar detenida; me pregunto si hay otros esfuerzos: https://github.com/Jack-Works/proposal-enum/discussions/19

    • Para usos similares, creo que las uniones discriminadas funcionan bastante bien

  • El sistema de tipos de TypeScript es interesante, pero uno se pregunta qué tan rápido sería si el compilador estuviera escrito en un lenguaje compilado
    Claro, hace falta la gran premisa de que sea una “buena implementación”

    • swc y esbuild no son buenos puntos de comparación. Buena parte de la mejora de velocidad se debe a que eliminan la sintaxis específica de TypeScript para generar JavaScript
      tsc tiende a ser lento solo en la primera ejecución y, si se usa la bandera incremental o el modo de vigilancia --transpile-only, normalmente el tiempo de compilación baja de 100 ms, así que casi no hay diferencia perceptible frente a SWC o ESBuild
    • Hay una respuesta del equipo de TypeScript: https://twitter.com/drosenwasser/status/1260723846534979584
      La idea es que, si la verificación de tipos de un programa mediano tarda 20 segundos, por lo general no es por estar en JS, sino porque los tipos provocan una explosión combinatoria
      Otros runtimes pueden aportar beneficios en paralelismo o tiempo de arranque, pero dice que no ha visto benchmarks centrados en CPU que respalden una mejora general de 20 veces en velocidad
    • El sistema de tipos es divertido hasta que empiezas a exprimirlo al máximo con genéricos
      Luego pasas todo el día depurando 5 líneas de lógica de tipos y terminas preguntándote cómo llegaste hasta ahí
    • Ya no hace falta solo imaginarlo: https://github.com/dudykr/stc
      Es un proyecto escrito en Rust por uno de los principales desarrolladores de SWC: SWC compila TS a JS y STC verifica los tipos de TS
    • El rendimiento reciente del compilador de TypeScript mejoró mucho
      Dicen que el futuro isolated declaration mode puede reducir los tiempos de compilación hasta en 75%: https://github.com/microsoft/TypeScript/pull/53463#issuecomm...

  • Para quienes apenas empiezan a aprender sobre compiladores, recomiendo este libro: https://keleshev.com/compiling-to-assembly-from-scratch/
    El autor crea un compilador a ensamblador ARM de 32 bits usando un subconjunto de TypeScript, y explica que se ve casi como pseudocódigo, lo que lo hace accesible

    • También recomiendo mucho Crafting Interpreters: https://craftinginterpreters.com/
      El libro está dividido en dos partes: en la primera se construye un intérprete de lenguaje en Java; en la segunda se compila el mismo lenguaje a bytecode y luego se implementa una máquina virtual de bytecode en C
      Todas las líneas de código de la implementación aparecen referenciadas en el libro

  • Para evitar el patrón visitor, se puede usar una función utilitaria run con un switch estilo IIFE
    Es decir, usar switch dentro de una función ejecutada inmediatamente y dejar que se infiera el tipo de retorno

    • Escribí sobre este patrón aquí: https://maxgreenwald.me/blog/do-more-with-run
    • En realidad, ni siquiera hace falta tanto: si simplemente llamas una función de inmediato, se infiere el tipo de retorno
      Si quieres evitar una IIFE porque no te gusta el () del final, puedes definir la función aparte y luego llamarla

  • Estoy escribiendo un compilador en TypeScript y coincido en que no es tan malo como pensaba
    Al principio, como el autor, empecé con Deno, pero al final me pasé a Bun; aunque tiene partes ásperas, me resulta más satisfactorio que Deno y es muy rápido
    Como frontend estándar de generador de parsers, Ohm-js es bastante cómodo: https://ohmjs.org/
    El compilador oficial tsc es demasiado enorme, así que no recomiendo leerlo; para ver cómo funciona tsc, mini-typescript es mejor: https://github.com/sandersn/mini-typescript/
    En particular, la rama centi-typescript ayuda mucho: https://github.com/sandersn/mini-typescript/tree/centi-types...
    Espero que en WASM se habiliten GC y acceso al DOM

    • Me da curiosidad por qué te pasaste a Bun

  • Pensé que TypeScript tendría una sobrecarga adicional por las interfaces, así que me sorprende
    Me pregunto si se podría aplicar a otros ámbitos; por ejemplo, si también sería bueno para parseo de lenguajes

    • En runtime, la sobrecarga de las interfaces es 0
      Desaparecen por completo durante la compilación

  • El resultado no es tan sorprendente. Después de todo, el propio compilador de TypeScript está escrito en TypeScript
    TypeScript como ML ya se valida todos los días en entornos de producción pesados

  • He escrito un compilador en C#, y lo que aquí parece especial son más que nada los tipos unión
    Personalmente decidí evitar la verbosidad del patrón visitor, y estoy esperando una funcionalidad de enums cerrados para poder verificar exhaustividad en tiempo de compilación

    • Cuando usas un lenguaje sin tipos unión ni enums al estilo Rust, esa funcionalidad se extraña mucho
      Las alternativas suelen ser incómodas: tener N propiedades nullable en una clase que representa un tipo suma y depender de la condición documentada de que “siempre solo una sea non-null”, o hacer que varias clases hereden de una clase común; ambas se sienten pesadas
      Si quieres crear varios tipos unión que se solapen, en ambos enfoques terminas necesitando duplicación o combinaciones ingeniosas