Skip to content

Demostrar que un compilador es correcto ​

Este es el proyecto de fin de curso. Al terminar esta sección, tendrás en tus manos un mini compilador y un teorema verificado por Lean: para cualquier expresión, el resultado calculado por las instrucciones compiladas es el mismo que calcular la expresión directamente.

No es "probamos muchas expresiones y todas estaban bien", es todas.

Todo lo que se usa ya lo aprendiste antes: definir funciones, hacer inducción sobre estructuras y buscar lemas cuando te atascas.

Antes de empezar ​

Paso 1: definir las expresiones y cuánto "debería" valer cada una ​

Una expresión es o bien un número, o bien la suma de dos expresiones, o bien el producto de dos expresiones:

lean
inductive Expr where
  | num : Nat → Expr
  | add : Expr → Expr → Expr
  | mul : Expr → Expr → Expr

inductive define un tipo de dato nuevo, enumerando todas las formas posibles que puede tener.

Calcular directamente el valor de una expresión:

lean
def eval : Expr → Nat
  | .num n => n
  | .add a b => eval a + eval b
  | .mul a b => eval a * eval b

eval es la definición de la "respuesta correcta". Si el compilador de más adelante es correcto o no, se decide con respecto a ella.

Prueba con 2 + 3 × 4:

lean
def demo : Expr := .add (.num 2) (.mul (.num 3) (.num 4))

#eval eval demo
text
14
  • eval demo calcula 14

Paso 2: definir una máquina que solo reconoce tres instrucciones ​

Esta máquina tiene una pila, es decir, una columna de números donde solo se puede poner y sacar por arriba. Hay tres instrucciones:

lean
inductive Instr where
  | push : Nat → Instr
  | add
  | mul
  • push n: pone n en la cima de la pila.
  • add: saca los dos números de la cima y pone su suma.
  • mul: saca los dos números de la cima y pone su producto.

Ejecutar una secuencia de instrucciones:

lean
def run : List Instr → List Nat → List Nat
  | [], stack => stack
  | .push n :: rest, stack => run rest (n :: stack)
  | .add :: rest, b :: a :: stack => run rest ((a + b) :: stack)
  | .mul :: rest, b :: a :: stack => run rest ((a * b) :: stack)
  | _ :: rest, stack => run rest stack

run 指令 栈 devuelve la pila después de la ejecución. La última línea maneja el caso en que la pila no tiene al menos dos números: se salta esa instrucción.

  • Instr y run no dan errores

Paso 3: escribir el compilador ​

Traduce una expresión a instrucciones. Un número es simplemente push; la suma es calcular primero el lado izquierdo, luego el derecho y al final add:

lean
def compile : Expr → List Instr
  | .num n => [.push n]
  | .add a b => compile a ++ compile b ++ [.add]
  | .mul a b => compile a ++ compile b ++ [.mul]

Compila la expresión de antes y ejecútala sobre la pila vacía:

lean
#eval run (compile demo) []
text
[14]

La cima de la pila es 14, igual que eval demo. Pero esto es solo una expresión.

  • run (compile demo) [] da [14]

Paso 4: escribir la frase que hay que demostrar ​

"El compilador es correcto" hay que decir primero con claridad qué significa:

text
theorem compile_correct (e : Expr) (s : List Nat) :
    run (compile e) s = eval e :: s

Se lee así: para cualquier expresión e y cualquier pila inicial s, ejecutar las instrucciones compiladas de e da como resultado la pila s con un número más encima, y ese número es precisamente eval e.

Este paso importa más que la demostración misma. Como se dijo en la primera sección: Lean verifica la frase que tú escribas. Si la frase está bien escrita, la demostración tiene sentido.

Observa que dice "cualquier pila inicial s", no solo la pila vacía. La razón se verá enseguida.

  • Puedo explicar con mis propias palabras qué afirma compile_correct

Paso 5: demostrar primero el ayudante ​

El resultado de compile son varios segmentos de instrucciones concatenados. Para razonar sobre ello, hay que saber primero: ejecutar dos segmentos concatenados equivale a ejecutar primero el primer segmento y luego el segundo sobre la pila que aquel deja.

lean
theorem run_append (p q : List Instr) (s : List Nat) :
    run (p ++ q) s = run q (run p s) := by
  induction p generalizing s with
  | nil =>
    rfl
  | cons i rest ih =>
    cases i <;> rcases s with _ | ⟨b, _ | ⟨a, s⟩⟩ <;> simp [run, ih]

Esto es una inducción sobre la lista de instrucciones p. Hay dos cosas nuevas:

  • generalizing s: hace que la hipótesis de inducción valga para cualquier pila. La pila cambia con cada instrucción ejecutada, así que una hipótesis que solo vale para una pila fija no sirve. Esta es también la razón por la que el teorema del paso anterior dice "cualquier pila s".
  • La última línea: según cuál sea la primera instrucción y según que la pila tenga cero, uno o al menos dos números, enumera todos los casos y entrega cada uno a simp. <;> significa "haz el paso siguiente con cada objetivo que aparezca".

No hace falta entender del todo esta línea ahora. Con saber que hace "dividir en casos y simplificar cada uno" basta.

  • run_append pasa

Paso 6: demostrar que el compilador es correcto ​

Se hace inducción sobre la forma de la expresión. Hay tres formas, así que hay tres ramas; la suma y el producto tienen cada una dos subexpresiones, así que cada una tiene dos hipótesis de inducción. Recórrelo tú mismo:

Demostrar en la prácticaDemostrar que el compilador es correctoEl estado y los errores provienen de Lean 4.35.0 Generar
theorem compile_correct (e : Expr) (s : List Nat) : run (compile e) s = eval e :: s := by
  induction e generalizing s with
  | num n =>
    rfl
  | add a b iha ihb =>
    simp [compile, run_append, iha, ihb, run, eval]
  | mul a b iha ihb =>
    simp [compile, run_append, iha, ihb, run, eval]

Escríbelo en el archivo:

lean
theorem compile_correct (e : Expr) (s : List Nat) :
    run (compile e) s = eval e :: s := by
  induction e generalizing s with
  | num n =>
    rfl
  | add a b iha ihb =>
    simp [compile, run_append, iha, ihb, run, eval]
  | mul a b iha ihb =>
    simp [compile, run_append, iha, ihb, run, eval]

Deberías ver: ningún error.

Lo que ocurre en la rama de la suma: compile se despliega en tres segmentos de instrucciones; run_append descompone "ejecutar tres segmentos" en ejecutarlos uno por uno; iha dice que tras el primer segmento la cima tiene eval a de más, ihb dice que tras el segundo segmento tiene eval b de más; el add final los suma, que es exactamente eval (.add a b).

  • compile_correct pasa

Paso 7: escribir a propósito un compilador incorrecto ​

Para ver si la verificación sirve, hay que ver si atrapa errores. Compila mal la suma: la expresión de la derecha no se compila y la de la izquierda se compila dos veces.

lean
def badCompile : Expr → List Instr
  | .num n => [.push n]
  | .add a _ => badCompile a ++ badCompile a ++ [.add]
  | .mul a b => badCompile a ++ badCompile b ++ [.mul]

theorem bad_correct (e : Expr) (s : List Nat) :
    run (badCompile e) s = eval e :: s := by
  induction e generalizing s with
  | num n =>
    rfl
  | add a b iha ihb =>
    simp [badCompile, run_append, iha, ihb, run, eval]
  | mul a b iha ihb =>
    simp [badCompile, run_append, iha, ihb, run, eval]

Deberías ver: la rama de la suma no se puede demostrar, y el error empieza con esta línea:

text
unsolved goals

Este compilador incorrecto da resultados correctos para expresiones como 1 + 1 o 2 + 2, donde los dos lados son iguales. Si solo se prueban estas, el test pasa. La demostración, no.

  • Vi que el compilador incorrecto no se puede demostrar

Punto de control ​

  • Mi Compiler.lean no da ningún error de principio a fin
  • Puedo decir qué son eval, run y compile cada uno
  • Puedo leer el significado de la frase compile_correct
  • Sé por qué se necesita el lema run_append
  • He visto un error que un test puede dejar pasar pero una demostración no

¿No funcionó? ​

compile_correct da un error diciendo que no conoce run_append. El lema debe escribirse antes.

Quedan objetivos sin demostrar en la rama de la suma. Compara con los seis elementos entre corchetes de simp; no puede faltar ni uno. Sobre todo run_append: sin él, las instrucciones concatenadas no se pueden descomponer.

La hipótesis de inducción no se puede usar. Mira si después de induction e está escrito generalizing s.

Qué lograste ​

Definiste el significado de un pequeño lenguaje, escribiste un compilador y demostraste que preserva el significado. Verificar un programa consiste siempre en estas tres cosas: escribir qué significa "correcto", escribir el programa y demostrar que el programa lo cumple.

Lo que puedes probar por tu cuenta a continuación:

  • Añade una forma más a Expr, por ejemplo la resta. Lean te dirá qué funciones y demostraciones necesitan una rama nueva.
  • Intercambia el orden de a y b en compile y mira de nuevo compile_correct. En la rama de la suma quedará un objetivo: eval b + eval a = eval a + eval b. Esta frase es verdadera y se puede completar con el Nat.add_comm del capítulo anterior. ¿Y con la resta? ¿La frase que queda sigue siendo verdadera?
gaodong.aiAboutPrivacyContact

Independent tutorials, not affiliated with any product mentioned. Product names and trademarks belong to their owners. Check official pages for prices and policies.