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
Copyno tienen restricciones.Copyvuelve 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. Dropes 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 afile.close()y a tratar su error.- Las fugas están permitidas.
mem::forgety los ciclos deRcsignifican 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 unDropque 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
&Tfrente 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
- Wadler, «Linear types can change the world!» (1990).
- Walker, «Substructural Type Systems», en Advanced Topics in Types and Programming Languages (2005): el tutorial estándar.
- Tofte y Talpin, «Region-Based Memory Management» (1997).
- Grossman et al., «Region-Based Memory Management in Cyclone» (PLDI 2002).
- Boyland, «Checking Interference with Fractional Permissions» (2003).
- Clarke, Potter y Noble, «Ownership Types for Flexible Alias Protection» (OOPSLA 1998).
- Weiss et al., «Oxide: The Essence of Rust» (2019).
- Jung, Understanding and Evolving the Rust Programming Language (tesis doctoral, 2020): el mejor documento único sobre los fundamentos de Rust.
- Pierce, Types and Programming Languages: si el progreso, la preservación y los juicios de tipado no te resultan familiares, empieza por aquí.
Ejercicios
- 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. - Amplíalo con una clase (kind)
Copy. ¿Qué regla cambia? - En Rust, aproxima un tipo lineal: un
struct MustClosecuyoDropentre en pánico salvo que se haya llamado aclose(self). Enumera tres formas en que el código seguro puede aun así evitar cerrarlo. - 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.
- 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.¿Qué regla estructural rechaza un sistema de tipos *afín*?
2.¿Por qué se describe a Rust como afín y no como lineal?
3.¿Qué aportó a Rust la gestión de memoria basada en regiones (Tofte y Talpin; Cyclone)?