A Calculus of Inheritance

El artículo presenta el cálculo de herencia, un fundamento para la programación declarativa que unifica clases, métodos y objetos bajo una abstracción de registro donde la herencia se modela como unión de conjuntos, eliminando así los problemas de linealización y ofreciendo una semántica de punto fijo que resulta más expresiva que el cálculo $\lambda$.

Lo esencial

Imagina que el mundo de la programación es como la construcción de casas.

Durante décadas, los arquitectos (los programadores) han usado un solo tipo de plano: el Cálculo Lambda (la base de la programación funcional). Este plano es genial, pero es como si solo pudieras construir casas usando recetas de cocina. Si quieres cambiar un ingrediente, tienes que reescribir toda la receta desde el principio. Es poderoso, pero rígido.

Por otro lado, en el mundo de la configuración de sistemas (como configurar un servidor o un sistema operativo), la gente ha estado usando un enfoque diferente: la herencia. Es como si pudieras tomar una casa base, añadirle una habitación, luego añadirle un jardín, y luego añadirle un techo, sin tener que rediseñar los planos originales. Pero hasta ahora, nadie había escrito las "leyes de la física" que explicaran por qué esto funciona tan bien, ni cómo hacerlo sin que las habitaciones choquen entre sí.

Este artículo, escrito por Bo Yang, presenta algo llamado "Cálculo de Herencia". Es como descubrir que la programación declarativa (configurar cosas) tiene sus propias leyes fundamentales, tan elegantes como las de la física, pero basadas en la idea de mezclar y unir.

Aquí tienes la explicación con analogías sencillas:

1. Los tres bloques de Lego

El autor dice que, así como la programación funcional se basa en tres cosas (abstracción, aplicación, variable), la programación declarativa solo necesita tres bloques de construcción:

1. Registro (Record): Una caja con etiquetas (como un formulario).
2. Definición: Poner un valor en una etiqueta.
3. Herencia: Pegar una caja sobre otra para combinarlas.

La analogía: Imagina que tienes un set de LEGO. En lugar de tener que construir un coche nuevo desde cero cada vez que quieres uno rojo, solo tomas un coche azul y le pegas una pieza roja encima. El resultado es un coche rojo. Si luego le pegas una pieza azul, ahora es un coche morado. No importa el orden en que pegues las piezas (es conmutativo): rojo sobre azul es lo mismo que azul sobre rojo. No importa si pegas la misma pieza dos veces (es idempotente): pegar una rueda roja dos veces no te da dos ruedas rojas, sigue siendo una.

2. El problema de los "caminos múltiples" (y cómo se resuelve)

En la programación tradicional (como en Java o Scala), si dos personas te dan instrucciones contradictorias sobre cómo construir algo, el sistema se rompe o tiene que elegir una ruta arbitraria (como decidir si el techo va a la izquierda o a la derecha). Esto se llama el "problema de la linealización".

La solución del Cálculo de Herencia:
Imagina que eres un detective que busca información en una biblioteca. Si dos personas te dan el mismo libro, en lugar de pelear por quién tiene el original, el sistema dice: "¡Genial! Tenemos dos copias. Vamos a leer ambas y unir lo que dicen".
Si dos módulos diferentes dicen "la puerta es roja" y "la puerta es azul", el sistema no entra en pánico. Como la herencia es una unión de conjuntos, simplemente entiende que la puerta tiene ambas propiedades o las fusiona inteligentemente. Esto elimina los conflictos de forma natural.

3. La magia de la "Caja de Herramientas" (El Problema de la Expresión)

En programación, existe un problema famoso llamado el "Problema de la Expresión": es difícil añadir nuevas características a un programa sin tener que reescribir todo el código antiguo.

• En el mundo tradicional: Si tienes un programa que suma números y quieres que también reste, a menudo tienes que tocar el código original.
• En este nuevo cálculo: Imagina que tienes un programa como un edificio con huecos vacíos (slots). Puedes añadir un "piso de resta" encima del "piso de suma" sin tocar ni un solo ladrillo del piso de abajo. El edificio simplemente se vuelve más alto y más capaz.
  El autor demuestra que con este sistema, puedes añadir nuevas funciones y nuevos tipos de datos infinitamente sin romper nada. Es como si tuvieras un traje que se adapta automáticamente a cualquier clima que le pongas encima.

4. ¿Qué pasa con las matemáticas y la lógica?

El paper muestra algo asombroso: si tomas operaciones matemáticas simples (como sumar 1 + 2) y las tratas con las reglas de este nuevo cálculo, ¡de repente empiezan a comportarse como lógica de bases de datos!

• La analogía: Imagina que tienes una caja con los números {1, 2} y otra con {3, 4}. Si las "mezclas" (heredan) y las sumas, no obtienes un solo número. Obtienes todas las combinaciones posibles: {4, 5, 6}.
  Esto significa que el mismo código que hace matemáticas simples también puede resolver problemas complejos de lógica y bases de datos sin cambiar una sola línea. Es como si un martillo pudiera usarse para clavar un clavo, pero también para romper una nuez y abrir una botella, todo sin cambiar la herramienta.

5. ¿Por qué es importante esto?

El autor dice que este sistema es más poderoso que la programación funcional tradicional (el Cálculo Lambda).

• El Cálculo Lambda es como un motor de coche muy eficiente, pero solo puede ir en línea recta.
• El Cálculo de Herencia es como un vehículo todoterreno. Puede hacer todo lo que hace el coche (es Turing-completo, es decir, puede calcular cualquier cosa), pero además puede navegar por terrenos difíciles (configuraciones complejas, sistemas operativos, bases de datos) sin atascarse.

En resumen

Este paper nos dice que la forma en que configuramos y construimos software (como en NixOS, donde se definen sistemas operativos enteros) no es solo un "parche" o un truco. Tiene una base matemática sólida y elegante.

La idea central es: No necesitas funciones complejas para programar. Solo necesitas cajas que se pueden pegar unas sobre otras de forma inteligente. Al hacerlo, los conflictos desaparecen, el código se vuelve más flexible y, de repente, las matemáticas simples pueden resolver problemas de lógica compleja.

Es como descubrir que el secreto para construir cualquier cosa no es tener herramientas más complicadas, sino saber cómo apilar bloques de LEGO de tal manera que siempre encajen, sin importar el orden en que los pongas.

Resumen técnico

Aquí presento un resumen técnico detallado del artículo "A Calculus of Inheritance" (Un Cálculo de Herencia) de Bo Yang, estructurado según los puntos solicitados.

1. El Problema

El artículo identifica una brecha fundamental en la teoría de la computación: mientras que el cálculo $\lambda$ sirve como modelo computacional fundacional para la programación funcional, no existe un cálculo análogo para la programación declarativa y los lenguajes de configuración.

Los desafíos específicos que aborda el autor son:

• Incompatibilidad de paradigmas: Los lenguajes de configuración (como NixOS, Jsonnet, CUE) son inherentemente declarativos (valores inmutables, sin funciones de primera clase), lo que parece incompatible con la completitud de Turing bajo los modelos clásicos (Máquinas de Turing requieren estado mutable; el $\lambda$-cálculo requiere funciones de primera clase).
• El Problema de la Expresión: La extensibilidad en sistemas existentes es a menudo "opt-in" (requiere mecanismos complejos como patrones Visitor o álgebras de objetos). No existe un modelo donde la extensión sea estructuralmente inherente y universal.
• Problemas de Herencia Múltiple: En la programación orientada a objetos y sistemas de mixins, la herencia múltiple genera problemas de linealización (determinar el orden de resolución) y conflictos de resolución de self (referencias a sí mismo) cuando existen múltiples rutas de herencia. Sistemas como Scala o el sistema de módulos de NixOS rechazan o fallan ante estas situaciones de "múltiples rutas".
• Semántica de Alta Orden: Las semánticas existentes para el $\lambda$-cálculo (denotacional, basada en juegos) dependen de espacios de funciones de orden superior, lo que complica la comprensión y la implementación de sistemas puramente declarativos.

2. Metodología

El autor propone y formaliza el Cálculo de Herencia (Inheritance-calculus), un modelo computacional minimalista derivado de la implementación práctica MIXINv2.

• Primitivas Fundamentales: El cálculo se basa en solo tres primitivas, análogas a las del $\lambda$-cálculo:
  1. Registro (Record): La unidad básica de datos.
  2. Definición (Definition): Asignación de una propiedad a un valor (ℓ ↦→ e).
  3. Herencia (Inheritance): Referencia que navega la jerarquía de alcance y proyecta propiedades ([ℓup.this. | ↑n.] ℓdown...).
• Abstracción Unificada: Unifica clases, métodos, objetos y propiedades bajo una sola abstracción: el mixin. No hay métodos opacos; todos los valores son registros transparentes.
• Semántica Observacional y de Primer Orden:
  • La computación se impulsa mediante la observación de rutas (paths) en un árbol de mixins construido perezosamente (lazy).
  • La semántica se define mediante seis ecuaciones recursivas de primer orden (sobre conjuntos de rutas y etiquetas), sin espacios de funciones ni sustitución de variables.
  • Se utiliza un operador de consecuencia inmediata ($T_P$) y su punto fijo mínimo (lfp) para definir la semántica denotacional, permitiendo la convergencia de programas recursivos que divergirían bajo reducción $\beta$.
• Mecanismo de Fusión Profunda (Deep Merge): La composición de mixins se realiza mediante la unión de conjuntos (set union). Esto hace que la herencia sea inherentemente conmutativa, idempotente y asociativa, eliminando la necesidad de algoritmos de linealización.
• Resolución de this Multirruta: A diferencia de sistemas que asumen una única ruta de herencia, el cálculo utiliza una resolución de this basada en conjuntos (frontier sets) que permite que una referencia a sí mismo se resuelva en múltiples objetos simultáneamente si existen múltiples rutas de herencia.

3. Contribuciones Clave

1. Cálculo de Herencia: Presentación de un modelo computacional minimalista para la programación declarativa que es Turing-completo y se basa exclusivamente en registros y herencia.
2. Unificación de Conceptos: Demostración de que mixins, clases y objetos pueden unificarse bajo una sola abstracción de "fusión profunda", resolviendo el problema de la linealización de mixins.
3. Semántica de Primer Orden para el $\lambda$-Cálculo: Se demuestra que el $\lambda$-cálculo (en forma normal A) se puede macro-expresar en el cálculo de herencia. Esto otorga al $\lambda$-cálculo una semántica de primer orden basada en ecuaciones de conjuntos, donde la equivalencia de árboles de Böhm se preserva.
4. Asimetría Expresiva: Se prueba que el cálculo de herencia es estrictamente más expresivo que el $\lambda$-cálculo perezoso (en el sentido de Felleisen). Mientras que el $\lambda$-cálculo puede expresarse en el cálculo de herencia, la inversa no es cierta: el cálculo de herencia permite extensiones abiertas que cambian la equivalencia operacional de términos $\lambda$ existentes sin modificarlos.
5. Inmunidad a la No-Extensibilidad: El diseño estructural del cálculo garantiza que ningún programa sea "no extensible". Cualquier propiedad puede ser extendida mediante herencia, resolviendo el Problema de la Expresión de forma nativa.
6. Semántica Relacional Emergente: Se demuestra que la aritmética y la lógica booleana implementadas en este cálculo generan automáticamente la semántica de la programación lógica (relacional) y productos cartesianos sin mecanismos adicionales, debido a la distribución de operaciones sobre conjuntos de rutas.

4. Resultados

• Convergencia de Programas Recursivos: El cálculo permite que programas recursivos que divergen bajo reducción $\beta$ (como let x = x in x) converjan bajo la semántica de punto fijo ($lfp(T_P)$), proporcionando una semántica más definida para la recursión en contextos declarativos.
• Resolución de Múltiples Rutas: En el estudio de caso de aritmética de números naturales (Nat), se demostró que operaciones independientes (como Plus y Equal) pueden componerse sin conflictos, incluso cuando heredan de la misma estructura base por rutas diferentes. El sistema fusiona los resultados en lugar de generar errores de "tipos base conflictivos" (como ocurre en Scala o NixOS).
• Cálculo de Productos Cartesianos: Al heredar dos valores numéricos (ej. {1, 2}) y aplicar una operación, el resultado es automáticamente el conjunto de todas las combinaciones posibles ({4, 5, 6}), implementando semántica relacional de forma natural.
• Ceguera al Color de Función (Function Color Blindness): El mismo código MIXINv2 puede ejecutarse en entornos síncronos y asíncronos sin modificaciones, ya que la lógica de negocio declara slots abstractos que se llenan mediante herencia en tiempo de ensamblaje, desacoplando la lógica de los efectos secundarios.

5. Significado

El trabajo tiene un impacto profundo en la teoría de lenguajes de programación y la ingeniería de software:

• Fundamento Teórico para Configuración: Proporciona la primera base teórica rigurosa para los lenguajes de configuración modernos (como NixOS), explicando por qué sus mecanismos de fusión recursiva son tan expresivos y potentes.
• Superación de Limitaciones de OOP: Ofrece una alternativa a la herencia de clases tradicional, eliminando la complejidad de la herencia múltiple y los problemas de resolución de self, permitiendo una composición de software más flexible y robusta.
• Nueva Perspectiva sobre el $\lambda$-Cálculo: Al mostrar que el $\lambda$-cálculo es un subconjunto del cálculo de herencia, sugiere que la función es simplemente un azúcar sintáctico para la herencia, y que la computación puede modelarse completamente sin espacios de funciones de orden superior.
• Resolución del Problema de la Expresión: Demuestra que la extensibilidad no requiere patrones complejos (como Visitor o Álgebras de Objetos) si el mecanismo de composición subyacente es la fusión profunda de registros.
• Puente entre Paradigmas: Une la programación funcional, la orientada a objetos y la lógica declarativa bajo un único marco semántico, sugiriendo que la distinción entre estos paradigmas es menos fundamental de lo que se creía.

En resumen, el Cálculo de Herencia propone un nuevo paradigma donde la composición de software se basa en la unión de estructuras de datos (registros) y la resolución de referencias a través de árboles de herencia, logrando una expresividad superior y una semántica más simple y robusta que los modelos tradicionales.