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
- Has aprendido hacer inducción sobre listas y sabes qué es un lema
- Crea un archivo nuevo
Compiler.leany escribe el código siguiente en orden
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:
inductive Expr where
| num : Nat → Expr
| add : Expr → Expr → Expr
| mul : Expr → Expr → Exprinductive define un tipo de dato nuevo, enumerando todas las formas posibles que puede tener.
Calcular directamente el valor de una expresión:
def eval : Expr → Nat
| .num n => n
| .add a b => eval a + eval b
| .mul a b => eval a * eval beval 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:
def demo : Expr := .add (.num 2) (.mul (.num 3) (.num 4))
#eval eval demo14eval democalcula 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:
inductive Instr where
| push : Nat → Instr
| add
| mulpush 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:
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 stackrun 指令 栈 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.
Instryrunno 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:
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:
#eval run (compile demo) [][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:
theorem compile_correct (e : Expr) (s : List Nat) :
run (compile e) s = eval e :: sSe 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.
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_appendpasa
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:
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:
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_correctpasa
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.
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:
unsolved goalsEste 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.leanno da ningún error de principio a fin - Puedo decir qué son
eval,runycompilecada 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
compiley mira de nuevocompile_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 elNat.add_commdel capítulo anterior. ¿Y con la resta? ¿La frase que queda sigue siendo verdadera?