FerrousPath

Nivel 5 · Investigación· Lección 1 de 9 · 45 min

La teoría de tipos de la propiedad

Lógicas subestructurales, tipos afines, regiones, y el linaje intelectual de Rust — desde la lógica lineal y Cyclone hasta cálculos formales como Oxide.

El nivel 5 cambia de registro. Los niveles anteriores te enseñaron a usar Rust; este te enseña a razonar sobre él, con el vocabulario de la investigación en lenguajes de programación. Cada lección es una entrada guiada a un cuerpo de literatura, con las fuentes primarias nombradas para que puedas ir a leerlas.

Reglas estructurales

En un sistema de tipos convencional, el contexto de tipado —el conjunto de variables en ámbito con sus tipos— se comporta como un conjunto. Tres reglas estructurales hacen que sea así:

Regla Dice En términos de programación
Intercambio El orden de las hipótesis es irrelevante Las variables pueden usarse en cualquier orden
Debilitamiento Una hipótesis puede quedar sin usar Una variable puede ignorarse
Contracción Una hipótesis puede usarse dos veces Una variable puede duplicarse

Un sistema de tipos subestructural prescinde de una o más de ellas:

Sistema Prescinde de Cada variable se usa
Sin restricciones (ML, Java) nada cualquier número de veces
Afín la contracción como máximo una vez
Relevante el debilitamiento al menos una vez
Lineal la contracción y el debilitamiento exactamente una vez
Ordenado las tres exactamente una vez, en orden

Estos sistemas descienden de la lógica lineal de Girard (1987), en la que las hipótesis son recursos que consumen las demostraciones que los usan. «Linear types can change the world!», de Wadler (1990), sacó la conclusión para la programación: si un valor tiene exactamente una referencia hacia él, puede actualizarse en el sitio y liberarse de forma determinista, sin recolector de basura y sin aliasing observable.

Rust es afín

Un movimiento es el consumo de un recurso afín:

fn consume(s: String) -> usize { s.len() }

fn main() {
    let s = String::from("resource");
    let n = consume(s);        // s se usa una vez: correcto
    // let m = consume(s);     // contracción: ❌ no compilaría (uso de un valor movido)
    let t = String::from("unused"); // no se vuelve a usar: el debilitamiento está permitido
    println!("{n}");
}

Tres refinamientos lo hacen práctico:

  • Los tipos Copy no tienen restricciones. Copy vuelve a habilitar la contracción para los tipos en los que duplicar es inofensivo. En términos de lógica lineal hace el papel del exponencial !A.
  • Drop es un debilitamiento implícito con un efecto. Cuando se descarta un valor afín, el compilador inserta su destructor. Eso es lo que hace funcionar el RAII, y es la razón de que Rust no sea lineal: el sistema de tipos no puede obligarte a llamar a file.close() y a tratar su error.
  • Las fugas están permitidas. mem::forget y los ciclos de Rc significan que ni siquiera el destructor está garantizado. Un tipo verdaderamente lineal —uno que deba consumirse explícitamente— no se puede expresar, aunque se puede aproximar con #[must_use] y un Drop que entre en pánico. Añadir tipos lineales reales, o «de movimiento obligatorio», es un problema de diseño abierto que interactúa mal con los pánicos y con todas las API genéricas existentes.

El problema de la linealidad pura, y el préstamo

Un lenguaje puramente lineal es penoso: para leer un valor tienes que hacerlo pasar por cada función y recuperarlo. La lección 1.4 mostró la forma: fn length(s: String) -> (String, usize).

La literatura ofrece varias formas de relajar temporalmente la linealidad:

  • El let! de Wadler permitía el acceso de solo lectura dentro de un ámbito delimitado.
  • Los permisos fraccionarios (Boyland, 2003): un permiso completo puede dividirse en fracciones; cualquier fracción permite leer, solo el todo permite escribir, y las fracciones pueden recombinarse. Es precisamente la lógica de &T frente a &mut T.
  • Los tipos de propiedad (ownership types; Clarke, Potter y Noble, 1998) restringían estructuralmente el aliasing en los lenguajes orientados a objetos.
  • Las regiones: más abajo.

La respuesta de Rust es el préstamo: una referencia es una capacidad sin propiedad y limitada en el tiempo, derivada de un dueño. Durante el préstamo los derechos del dueño quedan suspendidos (del todo para &mut, en parte para &), y se restauran cuando el préstamo termina. Formalmente, &'a mut T es una capacidad afín sobre un T, válida durante la región 'a; &'a T es una capacidad duplicable (Copy).

El reborrowing (volver a prestar) es lo que hace utilizables las referencias mutables pese a ser afines: pasar r: &mut T a una función no consume r; crea &mut *r, un subpréstamo con un lifetime más corto, y suspende r mientras dura.

fn bump(x: &mut i32) { *x += 1; }

fn main() {
    let mut v = 0;
    let r = &mut v;
    bump(r);      // implícitamente `bump(&mut *r)`: un reborrow, no un movimiento
    bump(r);      // así que `r` se puede seguir usando
    let moved = r; // un enlace explícito con el mismo tipo SÍ mueve
    bump(moved);
    println!("{v}");
}

Regiones

La gestión de memoria basada en regiones (Tofte y Talpin, 1997) daba a cada reserva una región inferida estáticamente; toda la memoria de una región se libera a la vez. El tipo de un puntero nombra su región, las funciones son polimórficas sobre regiones y el sistema de tipos garantiza que ningún puntero sobrevive a su región.

Cyclone (Jim, Grossman, Morrisett y colaboradores, 2002), un dialecto seguro de C, combinó las regiones con punteros únicos y con un subtipado explícito de regiones (una relación de supervivencia). La relación con Rust es directa:

Cyclone / cálculos de regiones Rust
Variable de región ρ Parámetro de lifetime 'a
Polimorfismo de regiones Funciones genéricas sobre lifetimes
Supervivencia de regiones ρ1 :> ρ2 'a: 'b
Punteros únicos Box<T>, movimientos
Subtipado de regiones Varianza y subtipado de lifetimes

La diferencia crucial: en el trabajo clásico, una región es un lugar donde se reserva memoria. En Rust, un lifetime es el intervalo durante el cual un préstamo está vivo. La reserva la gobierna en cambio la propiedad. Ese desplazamiento —de «dónde vive esto» a «durante cuánto tiempo está prestado»— es la idea central del diseño de Rust, y es la razón de que los lifetimes de Rust puedan inferirse dentro del cuerpo de las funciones y no tengan que corresponderse con ninguna estructura en tiempo de ejecución.

Lo que demuestra el sistema de tipos

El enunciado formal estándar de la seguridad de tipos tiene dos partes (Wright y Felleisen, 1994):

  • Progreso: un programa bien tipado o es un valor o puede dar un paso; nunca se queda atascado (nunca llega al comportamiento indefinido).
  • Preservación: si un programa bien tipado da un paso, el resultado está bien tipado.

Para Rust, el teorema que uno quiere es más fuerte y tiene una forma inusual: un programa cuyos bloques unsafe están encapsulados en bibliotecas correctas nunca exhibe comportamiento indefinido. Una demostración puramente sintáctica no puede con eso, porque el código unsafe es por definición código que las reglas sintácticas no comprueban. La lección 5.6 (RustBelt) muestra la técnica semántica que sí puede.

Modelos formales de (partes de) Rust que merece la pena conocer:

  • Patina (Reed, 2015): una formalización temprana del borrow checker.
  • λRust (RustBelt; Jung et al., POPL 2018): un cálculo núcleo en estilo de paso de continuaciones, cercano a MIR, con una demostración de corrección semántica verificada por máquina en Coq/Iris que se extiende a las bibliotecas unsafe.
  • Oxide (Weiss, Gierczak, Patterson y Ahmed, 2019): un cálculo cercano al Rust de superficie en el que los lifetimes se sustituyen por procedencias (provenances): conjuntos de préstamos de los que puede derivar una referencia. Presenta el borrow checking como un sistema de tipos sintáctico corriente, y su visión de las regiones como conjuntos de préstamos es la misma idea que subyace a Polonius.
  • FR / KRust / RustSEM / el LLBC de Aeneas: semánticas ejecutables u orientadas a la traducción.
  • a-mir-formality: el modelo ejecutable del sistema de tipos de MIR que desarrolla el propio equipo de tipos de Rust, escrito con la intención de llegar a ser normativo.

Parametricidad y teoremas gratis

Una función genérica de Rust no puede inspeccionar su parámetro de tipo (no hay instanceof, y la especialización es inestable). La parametricidad de Reynolds produce entonces «teoremas gratis» (Wadler, 1989): solo a partir del tipo,

fn mystery<T>(x: T) -> T { x }

tiene que ser la identidad (o divergir, o entrar en pánico), y cualquier fn f<T>(v: Vec<T>) -> Vec<T> solo puede reordenar, descartar o —si T: Clone— duplicar elementos; no puede inventar ninguno. La propiedad lo afina: sin T: Clone, el resultado contiene cada elemento de la entrada como máximo una vez. La parametricidad es una razón para mantener al mínimo las restricciones de trait, y su interacción con características como la especialización y Any/TypeId (que la rompen deliberadamente) es un tema recurrente en las discusiones sobre el diseño del lenguaje.

Lista de lecturas

  1. Wadler, «Linear types can change the world!» (1990).
  2. Walker, «Substructural Type Systems», en Advanced Topics in Types and Programming Languages (2005): el tutorial estándar.
  3. Tofte y Talpin, «Region-Based Memory Management» (1997).
  4. Grossman et al., «Region-Based Memory Management in Cyclone» (PLDI 2002).
  5. Boyland, «Checking Interference with Fractional Permissions» (2003).
  6. Clarke, Potter y Noble, «Ownership Types for Flexible Alias Protection» (OOPSLA 1998).
  7. Weiss et al., «Oxide: The Essence of Rust» (2019).
  8. Jung, Understanding and Evolving the Rust Programming Language (tesis doctoral, 2020): el mejor documento único sobre los fundamentos de Rust.
  9. Pierce, Types and Programming Languages: si el progreso, la preservación y los juicios de tipado no te resultan familiares, empieza por aquí.

Ejercicios

  1. Escribe las reglas de tipado (como reglas de inferencia, sobre el papel) de un pequeño cálculo lambda afín con let, pares y aplicación de funciones. Muestra cómo se divide el contexto entre las dos premisas de la aplicación.
  2. Amplíalo con una clase (kind) Copy. ¿Qué regla cambia?
  3. En Rust, aproxima un tipo lineal: un struct MustClose cuyo Drop entre en pánico salvo que se haya llamado a close(self). Enumera tres formas en que el código seguro puede aun así evitar cerrarlo.
  4. Lee la sección del artículo de Oxide sobre préstamos y procedencias. Explica con tus palabras en qué se diferencia una procedencia de un lifetime léxico.
  5. Enuncia el teorema gratis para fn f<T>(a: T, b: T) -> T. ¿Cuántas implementaciones distintas, totales y sin pánicos, existen?

Comprueba lo que has entendido

Elige una respuesta para ver la explicación.

  1. 1.¿Qué regla estructural rechaza un sistema de tipos *afín*?

  2. 2.¿Por qué se describe a Rust como afín y no como lineal?

  3. 3.¿Qué aportó a Rust la gestión de memoria basada en regiones (Tofte y Talpin; Cyclone)?

Términos clave de esta lección

¿Has terminado la lección y los ejercicios?