Apéndice A · Bootstrap de tres etapas

Este apéndice cuenta cómo se construye el compilador de kaikai desde cero, partiendo de un compilador de C corriente. No lo necesitas para programar en kaikai; es una decisión de ingeniería con consecuencias durables.

¿Por qué importa cómo se compila el compilador? Porque define a quién le crees y por qué. Un lenguaje cuyo compilador se construye desde una cc y nada más es un lenguaje que cualquiera puede auditar, reproducir y mantener.

A.1 El problema del bootstrap

Un compilador es un programa, y como cualquier programa hay que compilarlo para correrlo. Todo compilador nuevo tropieza con la misma paradoja: ¿qué lo compila la primera vez?

Tres respuestas históricas:

• Escribirlo en C (o ensamblador) la primera vez. Es la ruta clásica. GCC, MRI Ruby, CPython, V8 nacieron así. El costo: el compilador del lenguaje nuevo carga con la superficie de C para siempre, o se reescribe en sí mismo más tarde con una migración costosa.
• Escribirlo en un lenguaje existente que ya tenga compilador. Es lo que hizo Rust con OCaml al principio, lo que hizo Swift con C++. Hereda las dependencias del lenguaje huésped: compilar Rust requiere instalar OCaml, hasta que Rust se reescribió en sí mismo.
• Self-hosting incremental. Empezar con un compilador chico (de un subconjunto del lenguaje), escrito en algo portable, usarlo para compilar un compilador más grande (escrito en el lenguaje), y así sucesivamente. Es lo que hace kaikai con sus tres etapas.

A.2 Stage 0: el compilador en C

stage0 es un compilador escrito en C estándar. Su única dependencia es un compilador de C cualquiera:

$ cc stage0/*.c -o kaic0

Sin frameworks, generadores ni bibliotecas exóticas: C plano. El archivo stage0/runtime.h es el runtime de los programas compilados: contadores de referencia, primitivas de listas y strings, panic. Todo eso entra en unos pocos miles de líneas.

¿Qué compila kaic0? kaikai-minimal, un subconjunto deliberado del lenguaje. La gramática y las construcciones que caben en kaikai-minimal están documentadas en docs/kaikai-minimal.md. Quedan fuera los efectos algebraicos, las fibras, los protocolos, los contratos y las unidades de medida: es lo mínimo para escribir un compilador.

Stage 0 está hecho para ser auditable. Si quieres entender qué pasa, puedes leer el código C línea por línea: lexer, parser recursive-descent, chequeo de tipos simple, emisor de C. Cinco archivos.

A.3 Stage 1: el compilador en kaikai-minimal

Con kaic0 funcionando, el siguiente paso es un compilador escrito en kaikai-minimal. Este compilador, stage1, hace algo que kaic0 no puede: compila el lenguaje completo. Efectos, fibras, protocolos, contratos, todo.

$ kaic0 stage1/main.kai -o kaic1

kaic0 compila stage1 produciendo un ejecutable kaic1. A partir de ahí, el compilador de C ya no participa: kaic1 es suficiente para procesar programas que usan todo kaikai.

Es la primera auto-validación: el compilador escrito en kaikai-minimal demuestra que kaikai-minimal es lo bastante expresivo como para implementar un compilador completo. Si no lo fuera, este paso no terminaría.

A.4 Stage 2: kaikai completo, self-hosted

stage2 es la versión definitiva, escrita en kaikai completo (no en el subconjunto minimal) con efectos, fibras y todo lo que el lenguaje ofrece: código kaikai idiomático de extremo a extremo.

$ kaic1 stage2/main.kai -o kaic2

kaic1 compila stage2 y produce kaic2, el compilador que se distribuye. Al instalar kaikai recibes kaic2, no kaic0 ni kaic1.

Las tres etapas, de punta a punta:

Figura A.1 · El bootstrap en tres etapas. Las flechas continuas muestran qué compilador produce cada binario; las flechas punteadas van desde el código fuente de cada stage al binario que termina siendo. Solo cc es externo; una vez existe kaic0, la cadena se autosustenta. El chequeo de punto fijo de la fila inferior (kaic2 compilándose a sí mismo) es lo que cubre §A.5.

A.5 El punto fijo: validación del bootstrap

Al final del proceso hay una verificación crítica:

$ kaic2 stage2/main.kai -o kaic2-self
$ diff kaic2 kaic2-self

Tienen que ser bit por bit idénticos: kaic2 compilado por kaic1 produce exactamente lo mismo que kaic2 compilado por sí mismo. kaic2 es un punto fijo del proceso de compilación.

Importa por dos razones:

• Detección de errores sutiles en el compilador. Si dos versiones del compilador (kaic1 y kaic2) producen binarios distintos a partir del mismo código fuente, una de las dos tiene un bug. El punto fijo confirma que la cadena entera converge a la misma respuesta.
• Una base contra el ataque de Thompson. Ken Thompson publicó en 1984 un ensayo famoso (“Reflections on Trusting Trust”) donde mostraba que un compilador malicioso puede insertar backdoors invisibles que sobreviven a recompilaciones. La defensa conocida es diverse double-compiling (David A. Wheeler, 2005): compilar el fuente del compilador con una segunda cadena independiente y comparar los binarios. El punto fijo por sí solo no protege, porque un compilador troyanizado también se reproduce a sí mismo bit por bit. Lo que aporta es la compilación determinista que esa comparación necesita.

A.6 Reproducible desde una cc

La consecuencia práctica: con solo un compilador de C puedes reconstruir kaikai entero desde el código fuente. No necesitas kaikai instalado, ni confiar en un binario descargado de una página web, ni curl | bash.

$ git clone https://github.com/kaikailang-org/kaikai
$ cd kaikai
$ make

Por dentro, make ejecuta los tres pasos: stage 0 con cc, stage 1 con stage 0, stage 2 con stage 1. Deja un kaic2 en bin/, y la verificación de punto fijo asegura que es el correcto.

Esto es libertad técnica que pocos lenguajes modernos te dan. Rust requiere un Rust previo (descargado como blob). Go requiere un Go previo. Swift requiere un Swift previo. kaikai no: tu compilador de C es el punto de entrada.

A.7 Costos y trade-offs

Como toda decisión de ingeniería, el bootstrap de tres etapas tiene costos:

• Hay que mantener stage 0 cada vez que cambia kaikai-minimal. Si una característica nueva del lenguaje cae dentro del subconjunto minimal, stage 0 tiene que aprenderla. Eso significa código C nuevo, escrito a mano.
• Cuesta agregar dependencias al compilador. Stage 2 podría beneficiarse de una biblioteca externa (parser combinator, estructura de datos exótica). Pero esa biblioteca tendría que estar disponible en stage 1, que solo entiende kaikai-minimal. La presión es hacia mantener stage 2 autosuficiente.
• Compilar todo desde cero toma tiempo. No mucho (los tres pasos juntos toman menos de un minuto en una máquina razonable), pero más que un solo cargo build. En CI continua, importa.

¿Vale la pena? La respuesta del proyecto es sí, y la razón es filosófica: el compilador es la pieza de software más confiada del ecosistema. Si la cadena de confianza se puede auditar de extremo a extremo, partiendo de C plano, entonces el resto sigue.

A.8 Para profundizar

Las decisiones de diseño viven en docs/design.md de github.com/kaikailang-org/kaikai; los archivos, bajo stage0/, stage1/ y stage2/ del repositorio. Si te interesa la justificación filosófica de este enfoque, lee Reflections on Trusting Trust de Ken Thompson (CACM 1984).