Gestión Declarativa de Tipos Recursivos en WebAssembly GC

La extensión de WebAssembly con Garbage Collection (WASM GC) introduce tipos de datos complejos, incluyendo estructuras, arrays y funciones, que pueden ser recursivos. La especificación de WASM, aunque funcional, carece de una interfaz declarativa para la gestión de estos tipos, lo que dificulta su definición y deduplicación. Este problema fundamental de la computación, la representación y gestión de tipos recursivos en un sistema de tipos lineal e indexado, se agrava con la necesidad de manejar relaciones de subtipos y mutabilidad. La solución propuesta busca simplificar la interacción con el sistema de tipos de WASM GC, permitiendo a los desarrolladores definir tipos complejos de manera intuitiva y declarativa, sin preocuparse por la asignación manual de índices o la resolución de dependencias recursivas. Esto es crucial para la adopción de WASM GC en lenguajes de alto nivel que requieren sistemas de tipos ricos.

Históricamente, la gestión de tipos recursivos ha sido un desafío en la teoría de tipos y la implementación de compiladores. Lenguajes como ML o Haskell resuelven esto a nivel de lenguaje, pero la capa de bajo nivel de WASM requiere un enfoque explícito. La necesidad de un sistema declarativo surge de la naturaleza de WASM como un formato binario de bajo nivel, donde los tipos se definen en secciones separadas y se referencian por índice. La extensión GC añade la complejidad de tipos de heap, subtipos y grupos recursivos, haciendo que la gestión manual sea propensa a errores y tediosa.

Arquitectura del Sistema

El sistema propuesto se basa en una serie de ADTs (Algebraic Data Types) en Haskell para representar los tipos de WASM de manera declarativa. La pieza central es el GenIdx, una estructura de datos que gestiona la deduplicación de valores y la asignación de índices lineales. Este GenIdx utiliza un Map val (Int, meta) para almacenar los valores ya procesados junto con su índice y metadatos, y una lista [(val, meta)] para mantener el orden de inserción inverso.

Los tipos se clasifican en WTyp (tipos de stack) y HTyp (tipos de heap). WTyp incluye tipos primitivos (i32, f64) y referencias a HTyp. HTyp abarca clasificadores abstractos (HCls como any, struct, array), el tipo especial HI31, y los tipos recursivos HRTyp. Los tipos compuestos (CTyp) como struct, array y func son representados por WS, WA y WF respectivamente, y pueden contener información de mutabilidad (Mut/Imm).

La gestión de tipos recursivos se realiza a través del ADT RTyp, que puede ser un CTyp simple, un RRef (referencia recursiva dentro de un grupo) o un RTyp !Name !(Map Name SubTyp) que representa un grupo recursivo completo con nombres locales. Cada SubTyp encapsula un CTyp con metadatos adicionales como stFinal (si es final) y stExtends (si extiende otro tipo). Para resolver las dependencias de subtipos y asegurar un orden válido para la generación de índices, se emplea un algoritmo de toposort sobre el grafo de relaciones de subtipos. El proceso de generación de un módulo WASM se realiza en dos pasadas: una para recolectar importaciones y otra para generar el módulo final con los índices pre-sembrados, asegurando que todas las referencias se alineen correctamente.

data WTyp
  = WF64 | WF32
  | WI64 | WI32
  | WI16 | WI8
  | WV128
  | WR !Nul !HTyp

data HTyp
  = HCls !HCls
  | HRTyp !RTyp
  | HI31

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 :: 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 y la deduplicación de estructuras de datos es un tema recurrente en la informática teórica y la ingeniería de compiladores. La representación de tipos recursivos en un sistema de tipos lineal se relaciona con el concepto de 'fixed-point types' en la teoría de tipos, donde un tipo se define en términos de sí mismo. La necesidad de un toposort para resolver las dependencias de subtipos es una aplicación directa de la teoría de grafos, específicamente la ordenación topológica de un grafo dirigido acíclico (DAG). Este algoritmo es fundamental para la resolución de dependencias en sistemas de construcción, compiladores y bases de datos.

El uso de un sistema de índices para referenciar tipos y la deduplicación por valor es un patrón común en la representación intermedia de compiladores y en formatos de serialización binaria. Conceptos como el 'hash consing' (compartir estructuras de datos idénticas para ahorrar memoria y permitir comparaciones rápidas) son relevantes aquí, aunque el enfoque se centra más en la asignación de índices únicos. La idea de generar el módulo en dos pasadas para resolver dependencias hacia adelante (como las importaciones) es una técnica clásica en el diseño de enlazadores y compiladores, similar a cómo se resuelven las referencias 'forward' en lenguajes ensamblador o C/C++.