indirect: enums recursivos, árboles y expresiones

Escribe un enum cuyo caso contenga otro valor del mismo enum y el compilador te para en seco. No es un capricho: acabas de pedirle un tipo cuyo tamaño se define en función de sí mismo, una ecuación sin solución finita. La palabra clave indirect es la respuesta de Swift, y entender qué inserta exactamente separa a quien copia la sintaxis de quien entiende el modelo de memoria.

Por qué un valor recursivo no cabe

Los enums y los structs de Swift son tipos valor: su contenido se almacena en línea, dentro del espacio de quien los contiene. Para reservar ese espacio el compilador necesita conocer el tamaño en tiempo de compilación.

Considera una lista enlazada ingenua. Su tamaño sería el máximo entre el caso vacío y el caso con payload, y ese payload contiene otra lista, cuyo tamaño es el máximo entre el caso vacío y otro payload, y así sin fin. La ecuación de tamaño no tiene punto fijo finito.

enum Lista {
    case vacia
    case nodo(Int, Lista)     // error: value type has infinite size
}

El mismo argumento se aplica a los structs, que ni siquiera tienen una palabra clave que lo resuelva: para hacer recursivo un struct hay que introducir a mano una clase o un contenedor que viva en el heap.

indirect: la caja explícita

indirect le pide al compilador que almacene el payload de ese caso en una caja en el heap y guarde en el enum solo un puntero a esa caja. El tamaño vuelve a ser finito y conocido: el de un puntero.

enum Lista {
    case vacia
    indirect case nodo(Int, Lista)     // el payload vive en el heap
}

indirect enum Arbol {                  // aplicado a TODOS los casos con payload
    case hoja
    case nodo(valor: Int, izquierda: Arbol, derecha: Arbol)
}

Marcar el enum completo es cómodo, pero cobra la indirección incluso en casos que no la necesitan. Marcar caso por caso es la opción precisa cuando solo una rama es recursiva.

La caja es un objeto gestionado por ARC. Eso implica tres consecuencias que conviene tener presentes desde el primer día: hay una asignación de heap por nodo construido, hay conteo de referencias en cada copia y destrucción, y la semántica sigue siendo de valor aunque la representación sea de referencia. Copiar un Arbol copia el puntero y sube el contador, pero como el enum es inmutable y no existe forma de mutar la caja desde fuera, nadie puede observar el aliasing. Obtienes semántica de valor con representación compartida: exactamente lo mismo que hace String con su buffer.

flowchart LR
subgraph Pila
  E[Enum Arbol: etiqueta + puntero]
end
subgraph Heap
  B1[Caja: valor 5, izq, der]
  B2[Caja: valor 3, izq, der]
  B3[Caja: valor 9, izq, der]
end
E --> B1
B1 --> B2
B1 --> B3
style E fill:#89b4fa,color:#11111b
style B1 fill:#f9e2af,color:#11111b

Árboles y expresiones

El caso de uso canónico es el árbol de sintaxis abstracta. Un lenguaje de expresiones es literalmente una gramática, y una gramática es una suma de producciones: la correspondencia con el enum es exacta, término a término.

indirect enum Expr {
    case literal(Double)
    case variable(String)
    case suma(Expr, Expr)
    case producto(Expr, Expr)
    case negacion(Expr)
}

El intérprete es una función recursiva sobre la estructura. Como el switch es exhaustivo, añadir una producción a la gramática rompe la compilación de todo lo que la interpreta: el compilador te obliga a completar el intérprete, el impresor y el optimizador.

func evaluar(_ e: Expr, entorno: [String: Double]) throws -> Double {
    switch e {
    case .literal(let x):
        return x
    case .variable(let nombre):
        guard let v = entorno[nombre] else { throw ErrorEval.sinLigar(nombre) }
        return v
    case .suma(let a, let b):
        return try evaluar(a, entorno: entorno) + evaluar(b, entorno: entorno)
    case .producto(let a, let b):
        return try evaluar(a, entorno: entorno) * evaluar(b, entorno: entorno)
    case .negacion(let a):
        return -(try evaluar(a, entorno: entorno))
    }
}

Las transformaciones de árbol —simplificación, plegado de constantes, derivación simbólica— se escriben igual: recursión estructural que devuelve un árbol nuevo.

func plegar(_ e: Expr) -> Expr {
    switch e {
    case .suma(let a, let b):
        switch (plegar(a), plegar(b)) {
        case (.literal(let x), .literal(let y)): return .literal(x + y)
        case (let pa, let pb):                   return .suma(pa, pb)
        }
    default:
        return e
    }
}

El coste de la indirección

La elegancia tiene factura, y a nivel de rendimiento conviene saber cuál.

Cada nodo es una asignación de heap independiente, así que un árbol grande queda esparcido por la memoria y su recorrido es una cadena de fallos de caché. El conteo de referencias añade operaciones atómicas en cada copia y liberación. Y la destrucción es recursiva: liberar un árbol muy profundo puede desbordar la pila si la recursión de ARC no está acotada.