La extensión WebAssembly Garbage Collection (WASM GC) introduce tipos de datos complejos en el ecosistema WASM, incluyendo structs, arrays y funciones, con soporte para subtipos y recursión. La especificación WASM, aunque funcional, carece de una guía explícita para la gestión declarativa de estos tipos, lo que dificulta su uso en compiladores y herramientas de alto nivel. Este artículo aborda el problema fundamental de cómo representar y generar de manera eficiente tipos recursivos y sus relaciones de subtipo, garantizando la deduplicación y la coherencia en el formato lineal de WASM.
El desafío principal radica en la naturaleza lineal del formato WASM, donde los tipos complejos deben ser declarados y referenciados por índice antes de su uso. Esto es particularmente problemático para tipos recursivos o mutuamente recursivos, donde las referencias circulares deben resolverse sin caer en recursión infinita o dependencias cíclicas irresolubles. La solución propuesta se centra en un modelo declarativo que permite definir tipos con referencias a sí mismos o a otros tipos dentro de un grupo recursivo, y luego transformar esta representación en la secuencia lineal requerida por WASM.
Arquitectura del Sistema
La arquitectura del sistema se basa en una serie de estructuras de datos Haskell para modelar los tipos WASM y un mecanismo de generación de índices para la deduplicación. El componente central es GenIdx, una estructura que mapea valores a sus índices y metadatos, permitiendo la deduplicación por valor. Los tipos se clasifican en WTyp (tipos de stack), HTyp (tipos de heap), CTyp (tipos compuestos: structs, arrays, funciones) y RTyp (tipos recursivos).
RTyp es la abstracción clave para manejar la recursión. Un tipo recursivo se modela como un nombre (Name) dentro de un mapa de subtipos (Map Name SubTyp), donde cada SubTyp es un CTyp con información adicional sobre si es final y de qué otro RTyp extiende. Las referencias dentro de un grupo recursivo se manejan con RRef Name, que se "promociona" a RTyp al extraer un subtipo del mapa. La generación de tipos en el formato WASM implica un proceso de dos fases: primero, se recopilan todos los imports, y luego se genera el módulo completo con los imports pre-sembrados. Para los tipos recursivos, se utiliza un algoritmo de toposort para ordenar las dependencias de subtipos, asegurando que los tipos base se declaren antes que sus extensiones. La deduplicación se realiza a nivel de RTyp completo, y se utilizan dos índices (types y typeGroups) para gestionar la deduplicación de tipos compuestos individuales y grupos recursivos, respectivamente.
Generación de Tipos Recursivos en WASM
- 1 Definir RTyp Modelar el grupo recursivo como `RTyp Name (Map Name SubTyp)`
- 2 Generar Subtipos Procesar cada `SubTyp` dentro del grupo, resolviendo `RRef` a `RTyp`
- 3 Toposort Dependencias Ordenar los subtipos por relaciones de herencia (`stExtends`) para asegurar u...
- 4 Reservar Índices Usar `reserveNForSure` para asignar índices en la tabla de tipos WASM
- 5 Generar Sintaxis Producir la representación lineal de los tipos WASM
- 6 Actualizar GenIdx Registrar los tipos generados en los índices `types` y `typeGroups`
| Capa | Tecnología | Justificación |
|---|---|---|
| data-processing | Haskell | Lenguaje de implementación para el sistema declarativo de tipos y la lógica de generación. vs Rust, OCaml |
| storage | Map (Haskell) | Utilizado en `GenIdx` para deduplicar valores y almacenar índices, y en `RTyp` para modelar grupos de subtipos. vs HashMap |
Trade-offs
Ganancias
- ▲ Declaratividad y legibilidad del código fuente
- ▲ Deduplicación automática de tipos
- ▲ Manejo robusto de tipos recursivos
Costes
- ▲ Complejidad en la lógica de generación (requiere toposort y gestión de múltiples índices)
- △ Posible sobrecarga de rendimiento en la fase de compilación debido a la doble pasada y toposort
data GenIdx meta val = GenIdx
!(Map val (Int, meta))
![(val, meta)] -- reverse order
gen :: forall meta val. Ord val => GenIdx meta val -> val -> meta -> (GenIdx meta val, Int, meta)
gen (GenIdx validx stack) val newMeta =
case Map.lookup val validx of
Just (idx, oldMeta) -> (GenIdx validx stack, idx, oldMeta)
Nothing ->
let idx = Map.size validx
g' = GenIdx (Map.insert val (idx, newMeta) validx) ((val, newMeta) : stack)
in (g', idx, newMeta)-- Toposort in 5 lines of code
toposort :: forall k. Ord k => NFData k => Map k (Set k) -> [k]
toposort = join . reverse . go [] where
go :: [[k]] -> Map k (Set k) -> [[k]]
go acc entries = let (sel, remaining) = Map.partition Set.null entries
in if Map.null sel then acc else
go (Map.keys sel : acc) (remaining <&> (Set.\ Map.keysSet sel))Fundamentos Teóricos
El problema de la gestión de tipos recursivos en un sistema de tipos lineales y referenciados por índice tiene paralelos con la teoría de tipos y los sistemas de inferencia de tipos en lenguajes de programación funcionales. La necesidad de ordenar las declaraciones de tipos con dependencias cíclicas se relaciona con el concepto de "least fixed point" en la semántica denotacional y la resolución de ecuaciones de tipos. El uso de un algoritmo de toposort para resolver las dependencias de subtipos es una aplicación directa de la teoría de grafos, donde los nodos son los tipos y los bordes representan las relaciones de subtipo. Este enfoque es similar a cómo los compiladores de lenguajes con tipos algebraicos recursivos (como Haskell o ML) resuelven las dependencias entre definiciones de tipos. La deduplicación de tipos por valor, utilizando un mapa para almacenar los índices, es una técnica común en la optimización de compiladores para reducir el tamaño del código generado y mejorar el rendimiento de la búsqueda, análogo a la canonicalización de términos en sistemas de reescritura.