Sintaxis y Semantica 3. El Problema de la Expresion — por que no puedes tenerlo todo

En la Parte 1, vimos que cada enum y sealed trait es una gramatica formal: define la sintaxis de tu dominio. En la Parte 2, dimos significado a esas estructuras a traves de la semantica: brazos de match, funciones puras, contratos a nivel de tipos. Ahora hacemos una pregunta mas dificil: que pasa cuando necesitas extender ambos?

Tienes un tipo de dato. Tienes operaciones sobre el. Entonces llega un nuevo requerimiento: una nueva variante, o una nueva operacion, o ambas. Cuanto de tu codigo existente tienes que tocar?

Philip Wadler planteo esto como un desafio preciso en 1998, basandose en trabajo previo de John Reynolds (1975) y William Cook (1990): definir un tipo de dato por casos donde se pueda agregar nuevos casos y nuevas funciones sobre el tipo de dato, sin recompilar el codigo existente, manteniendo la seguridad de tipos estatica. Lo llamo el Expression Problem.

La matriz

#

El Expression Problem se aclara cuando piensas en tu codigo como una matriz bidimensional. Las filas son variantes de datos, la sintaxis, lo que puede existir. Las columnas son operaciones, la semantica, lo que puedes hacer con lo que existe.

                    Operations (Semantics)
                    eval()    print()    optimize()
          ┌─────────┬─────────┬───────────┐
Num(n)    │  n      │  "n"    │  Num(n)   │
          ├─────────┼─────────┼───────────┤
Add(l,r)  │  l+r    │  "l+r"  │  ...      │
          ├─────────┼─────────┼───────────┤
Mul(l,r)  │  l*r    │  "l*r"  │  ...      │
          └─────────┴─────────┴───────────┘

Adding a row    = new syntax   (new variant)
Adding a column = new semantics (new operation)

Cada celda en la matriz es una pieza de logica: que hace esta operacion para esta variante? La matriz completa debe estar llena. Ninguna celda puede dejarse en blanco; el compilador insiste en la exhaustividad, de una forma u otra.

La pregunta es: puedes agregar tanto una fila como una columna libremente, sin tocar las celdas existentes? La respuesta, con herramientas estandar, es no. Debes elegir que eje es facil.

Rust: facil agregar columnas, dificil agregar filas

#

El enum mas match de Rust organiza el codigo por operacion. Cada funcion contiene una expresion match que maneja cada variante. La logica para una sola operacion vive en un solo lugar.

enum Expr {
    Num(f64),
    Add(Box<Expr>, Box<Expr>),
}

fn eval(e: &Expr) -> f64 {
    match e {
        Expr::Num(n) => *n,
        Expr::Add(l, r) => eval(l) + eval(r),
    }
}

fn print_expr(e: &Expr) -> String {
    match e {
        Expr::Num(n) => n.to_string(),
        Expr::Add(l, r) => format!("({} + {})", print_expr(l), print_expr(r)),
    }
}

Agregar una nueva columna, una nueva operacion, es trivial. Escribe una nueva funcion con su propio match. Ningun codigo existente cambia:

// New operation: easy. Zero changes to existing code.
fn optimize(e: &Expr) -> Expr {
    match e {
        Expr::Num(n) => Expr::Num(*n),
        Expr::Add(l, r) => {
            let l = optimize(l);
            let r = optimize(r);
            match (&l, &r) {
                (Expr::Num(a), Expr::Num(b)) => Expr::Num(a + b),
                _ => Expr::Add(Box::new(l), Box::new(r)),
            }
        }
    }
}

Ahora agrega una nueva fila. Agrega Mul(Box<Expr>, Box<Expr>) al enum. El compilador inmediatamente marca cada match existente como no exhaustivo: eval, print_expr, optimize, todos ellos. El numero de funciones que debes actualizar es proporcional al numero de operaciones existentes. El matching exhaustivo de Rust garantiza que no olvidaras un caso, lo cual es valioso. Pero el trabajo es real. Agregar una fila toca cada columna.

Scala: facil agregar filas, dificil agregar columnas

#

El estilo OOP de Scala, un trait con metodos, implementado por case classes, organiza el codigo por variante. Cada clase contiene la logica para cada operacion. La logica para una sola variante vive en un solo lugar.

trait Expr {
  def eval: Double
  def printExpr: String
}

case class Num(n: Double) extends Expr {
  def eval: Double = n
  def printExpr: String = n.toString
}

case class Add(l: Expr, r: Expr) extends Expr {
  def eval: Double = l.eval + r.eval
  def printExpr: String = s"(${l.printExpr} + ${r.printExpr})"
}

Agregar una nueva fila, una nueva variante, es trivial. Escribe una nueva case class que implemente el trait. Ningun codigo existente cambia:

// New variant: easy. Zero changes to existing code.
case class Mul(l: Expr, r: Expr) extends Expr {
  def eval: Double = l.eval * r.eval
  def printExpr: String = s"(${l.printExpr} * ${r.printExpr})"
}

Ahora agrega una nueva columna. Agrega def optimize: Expr al trait Expr. Cada clase existente, Num, Add, Mul, debe actualizarse para proporcionar una implementacion. El numero de clases que debes modificar es proporcional al numero de variantes existentes. Agregar una columna toca cada fila.

Una nota: Scala tambien soporta el estilo FP, sealed trait con pattern matching externo. Cuando usas ese enfoque, los compromisos de extension se invierten y se comportan exactamente como los de Rust. El estilo OOP (metodos en el trait) es lo que le da a Scala el sesgo opuesto.

La tension fundamental

#

Esto no es un bug en Rust o Scala. No es algo que una caracteristica del lenguaje suficientemente ingeniosa hara desaparecer. Es una consecuencia de como se organiza el codigo en dos dimensiones.

Organizar por columnas (una funcion por operacion, haciendo match con todas las variantes) hace barato agregar una nueva columna. Organizar por filas (una clase por variante, implementando todas las operaciones) hace barato agregar una nueva fila. Puedes elegir un eje, pero no puedes elegir ambos simultaneamente, ni con ADTs concretos ni con jerarquias de clases concretas. Cualquier solucion que pretenda resolver ambos ejes introduce alguna forma de indireccion o abstraccion.

Wadler lo expreso con precision:

“The goal is to define a datatype by cases, where one can add new cases to the datatype and new functions over the datatype, without recompiling existing code, and while retaining static type safety.”

Reynolds vio la dualidad en 1975. Cook formalizo la relacion entre tipos abstractos y objetos en 1990. Wadler nombro el problema en 1998. La tension es fundamental. La pregunta no es si existe un compromiso, sino si la abstraccion que lo resuelve vale su costo.

La resolucion existe

#

Hay una tecnica que resuelve el Expression Problem de manera limpia. La idea clave es esta: hacer la sintaxis abstracta. En vez de un enum concreto o un sealed trait concreto, define la gramatica como una type class (Rust) o un trait abstracto parametrizado por un constructor de tipos (Scala). Cada operacion se convierte en una implementacion de esa abstraccion. Cada nueva variante extiende la abstraccion sin tocar las implementaciones existentes.

Esta tecnica se llama tagless final. No es un truco. Es semantica denotacional aplicada a la construccion de programas: la sintaxis nunca se materializa como una estructura de datos. En su lugar, se interpreta directamente en su significado. Nuevas variantes y nuevas operaciones extienden el sistema sin recompilacion, sin perder seguridad de tipos, y sin modificar codigo existente.

Cubrimos tagless final en detalle completo, con codigo funcional en Rust y Scala, en el post dedicado.

Cierre de la serie

#

Tres posts, un hilo conductor. Trazamos la conexion desde las gramaticas formales hasta tus tipos de dominio, desde la semantica formal hasta tu pattern matching e implementaciones de traits, y desde el Expression Problem hasta la tension fundamental entre extender lo que puede decirse y extender lo que significa. La sintaxis define el espacio. La semantica asigna significado. El Expression Problem pregunta si puedes crecer ambos sin romper lo que ya funciona. La respuesta es si, pero solo si estas dispuesto a hacer la sintaxis abstracta.